Main Page   Data Structures   File List   Data Fields   Globals  

ght_hash_table.h File Reference

libghthash is a generic hash table used for storing arbitrary data. More...


Data Structures

struct  ght_hash_table_t
 The hash table structure. More...

struct  ght_iterator_t
struct  s_hash_entry
struct  s_hash_key
 The structure for hash keys. More...


Typedefs

typedef unsigned int ght_uint32_t
 unsigned 32 bit integer. More...

typedef s_hash_key ght_hash_key_t
 The structure for hash keys. More...

typedef ght_uint32_t(* ght_fn_hash_t )(ght_hash_key_t *p_key)
 Definition of the hash function pointers. More...


Functions

ght_hash_table_tght_create (unsigned int i_size, ght_fn_hash_t fn_hash, int i_flags)
 Create a new hash table. More...

int ght_insert (ght_hash_table_t *p_ht, void *p_entry_data, unsigned int i_key_size, void *p_key_data)
 Insert an entry into the hash table. More...

void * ght_get (ght_hash_table_t *p_ht, unsigned int i_key_size, void *p_key_data)
 Lookup an entry in the hash table. More...

void * ght_remove (ght_hash_table_t *p_ht, unsigned int i_key_size, void *p_key_data)
 Remove an entry from the hash table. More...

void * ght_first (ght_hash_table_t *p_ht, ght_iterator_t *p_iterator)
 Return the first entry in the hash table. More...

void * ght_next (ght_hash_table_t *p_ht, ght_iterator_t *p_iterator)
 Return the next entry in the hash table. More...

void ght_rehash (ght_hash_table_t *p_ht, unsigned int i_size)
 Rehash the hash table. More...

void ght_finalize (ght_hash_table_t *p_ht)
 Free the hash table. More...

ght_uint32_t ght_one_at_a_time_hash (ght_hash_key_t *p_key)
 One-at-a-time-hash. More...

ght_uint32_t ght_rotating_hash (ght_hash_key_t *p_key)
 Rotating hash. More...

ght_uint32_t ght_crc_hash (ght_hash_key_t *p_key)
 CRC32 hash. More...


Detailed Description

libghthash is a generic hash table used for storing arbitrary data.

Libghthash really stores pointers to data - the hash table knows nothing about the actual type of the data.

A simple example to get started can be found in the simple.c file found in the distribution. hash_test.c provides a more comlpete example.

The MK2 version of the library should be more simple to use with fewer exported function calls and fewer structs. The usage have changed a bit since the first version though:

Some basic properties of the hash table are:


Typedef Documentation

typedef ght_uint32_t(* ght_fn_hash_t)(ght_hash_key_t *p_key)
 

Definition of the hash function pointers.

ght_fn_hash_t should be used when implementing new hash functions. Look at the supplied hash functions, like ght_one_at_a_time_hash(), for examples of hash functions.

Parameters:
p_key  the key to calculate the hash value for.
Returns:
a 32 bit hash value.
See also:
ght_one_at_a_time_hash(), ght_rotating_hash(), ght_crc_hash()

typedef struct s_hash_key ght_hash_key_t
 

The structure for hash keys.

You should not care about this structure unless you plan to write your own hash functions.

typedef unsigned int ght_uint32_t
 

unsigned 32 bit integer.


Function Documentation

ght_uint32_t ght_crc_hash ght_hash_key_t   p_key
 

CRC32 hash.

CRC32 hash is a good hash function. This came from Dru Lemley <spambait@lemley.net>.

Warning:
Don't call this function directly, it is only meant to be used as a callback for the hash table.
See also:
ght_fn_hash_t , ght_one_at_a_time_hash(), ght_rotating_hash()

ght_hash_table_t* ght_create unsigned int    i_size,
ght_fn_hash_t    fn_hash,
int    i_flags
 

Create a new hash table.

The number of buckets should be about as big as the number of elements you wish to store in the table for good performance. The number of buckets is rounded to the next higher power of two.

The possible flags are:

  • GHT_HEURISTICS_TRANSPOSE: Use transposing heuristics. An accessed element will move one step up in the bucket-list with this method. Cannot be combined with GHT_HEURISTICS_MOVE_TO_FRONT.
  • GHT_HEURISTICS_MOVE_TO_FRONT: Use move-to-front heuristics. An accessed element will be moved the front of the bucket list with this method. Cannot be combined with GHT_HEURISTICS_TRANSPOSE.
  • GHT_AUTOMATIC_REHASH: Perform automatic rehashing when the number of elements in the table are twice as many as the number of buckets. You should note that automatic rehashing will cause your application to be really slow when the table is rehashing (which might happen at times when you need speed), you should * therefore be careful with this in time-constrainted applications.
Parameters:
i_size  the number of buckets in the hash table. Giving a non-power of two here will round the size up to the next power of two.
fn_hash  the hash function to use (NULL for default). You can define own hash functions to use here, see the implementation of ght_one_at_a_time_hash() in hash_table.c for an example.
i_flags  specify the flags to use. This should be bitwise or:ed. note that some options are mutually exclusive.
See also:
ght_one_at_a_time_hash(), ght_rotating_hash(), ght_crc_hash()
Returns:
a pointer to the hash table or NULL upon error.

void ght_finalize ght_hash_table_t   p_ht
 

Free the hash table.

ght_finalize() should typically be called at the end of the program. Note that only the metadata and the keys of the table is freed, not the entries. If you want to free the entries when removing the table, the entries will have to be manually freed before ght_finalize() is called like:

 ght_iterator_t iterator;
 void *p_e;

 for(p_e = ght_first(p_table, &iterator); p_e; p_e = ght_next(p_table, &iterator))
   {
     free(p_e);
   }

 ght_finalize(p_table);
 
Parameters:
p_ht  the table to remove.

void* ght_first ght_hash_table_t   p_ht,
ght_iterator_t *    p_iterator
 

Return the first entry in the hash table.

This function should be used for iteration and is used together with ght_next(). Note that you cannot assume anything about the order in which the entries are accessed. If an entry is inserted during an iteration, the entry might or might not occur in the iteration.

The use of the ght_iterator_t allows for several concurrent iterations, where you would use one ght_iterator_t for each iteration. In threaded environments, you should still lock access to the hash table for insertion and removal.

A typical example might look as follows:

 ght_hash_table_t *p_table;
 ght_iterator_t iterator;
 void *p_e;

 [Create table etc...]
 for(p_e = ght_first(p_table, &iterator); p_e; p_e = ght_next(p_table, &iterator))
   {
      [Do something with the current entry p_e]
   }
 
Parameters:
p_ht  the hash table to iterate through.
p_iterator  the iterator to use. The value of the structure is filled in by this function and may be stack allocated.
Returns:
a pointer to the first entry in the table or NULL if there are no entries.
See also:
ght_next()

void* ght_get ght_hash_table_t   p_ht,
unsigned int    i_key_size,
void *    p_key_data
 

Lookup an entry in the hash table.

The entry is not removed from the table.

Parameters:
p_ht  the hash table to search in.
i_key_size  the size of the key to search with (in bytes).
p_key_data  the key to search for.
Returns:
a pointer to the found entry or NULL if no entry could be found.

int ght_insert ght_hash_table_t   p_ht,
void *    p_entry_data,
unsigned int    i_key_size,
void *    p_key_data
 

Insert an entry into the hash table.

Prior to inserting anything, make sure that the table is created with ght_create(). If an element with the same key as this one already exists in the table, the insertion will fail and -1 is returned.

A typical example is shown below, where the string "blabla" is used as a key for the integer 15.

 ght_hash_table_t *p_table;
 char *p_key_data;
 int *p_data;

 [Create p_table etc...]
 p_data = malloc(sizeof(int));
 p_key_data = "blabla";
 *p_data = 15;

 ght_insert(p_table,
            p_data,
            sizeof(char)*strlen(p_key_data), p_key_data);
 
Parameters:
p_ht  the hash table to insert into.
p_entry_data  the data to insert.
i_key_size  the size of the key to associate the data with (in bytes).
p_key_data  the key to use. The value will be copied, and it is therefore OK to use a stack-allocated entry here.
Returns:
0 if the element could be inserted, -1 otherwise.

void* ght_next ght_hash_table_t   p_ht,
ght_iterator_t *    p_iterator
 

Return the next entry in the hash table.

This function should be used for iteration, and must be called after ght_first().

Warning:
calling this without first having called ght_first will give undefined results (probably a crash), since p_iterator isn't filled correctly.
Parameters:
p_ht  the hash table to iterate through.
p_iterator  the iterator to use.
Returns:
a pointer to the next entry in the table or NULL if there are no more entries in the table.
See also:
ght_first()

ght_uint32_t ght_one_at_a_time_hash ght_hash_key_t   p_key
 

One-at-a-time-hash.

One-at-a-time-hash is a good hash function, and is the default when ght_create() is called with NULL as the fn_hash parameter. This was found in a DrDobbs article, see http://burtleburtle.net/bob/hash/doobs.html

Warning:
Don't call this function directly, it is only meant to be used as a callback for the hash table.
See also:
ght_fn_hash_t , ght_rotating_hash(), ght_crc_hash()

void ght_rehash ght_hash_table_t   p_ht,
unsigned int    i_size
 

Rehash the hash table.

Rehashing will change the size of the hash table, retaining all elements. This is very costly and should be avoided unless really needed. If GHT_AUTOMATIC_REHASH is specified in the flag parameter when ght_create() is called, the hash table is automatically rehashed when the number of stored elements exceeds two times the number of buckets in the table (making calls to this function unessessary).

Parameters:
p_ht  the hash table to rehash.
i_size  the new size of the table.
See also:
ght_create()

void* ght_remove ght_hash_table_t   p_ht,
unsigned int    i_key_size,
void *    p_key_data
 

Remove an entry from the hash table.

The entry is removed from the table, but not freed (that is, the data stored is not freed).

Parameters:
p_ht  the hash table to use.
i_key_size  the size of the key to search with (in bytes).
p_key_data  the key to search for.
Returns:
a pointer to the removed entry or NULL if the entry could be found.

ght_uint32_t ght_rotating_hash ght_hash_key_t   p_key
 

Rotating hash.

Not so good hash function. This was found in a DrDobbs article, see http://burtleburtle.net/bob/hash/doobs.html

Warning:
Don't call this function directly, it is only meant to be used as a callback for the hash table.
See also:
ght_fn_hash_t , ght_one_at_a_time_hash(), ght_crc_hash()


Generated on Sun Mar 24 13:07:43 2002 for libghthash by doxygen1.2.12 written by Dimitri van Heesch, © 1997-2001