Main Page | Class List | Directories | File List | Class Members | File Members
src

ght_hash_table.h File Reference

#include <stdlib.h>

Go to the source code of this file.

Defines

#define GHT_HEURISTICS_NONE   0
#define GHT_HEURISTICS_TRANSPOSE   1
#define GHT_HEURISTICS_MOVE_TO_FRONT   2
#define GHT_AUTOMATIC_REHASH   4
#define TRUE   1
#define FALSE   0

Typedefs

typedef unsigned int ght_uint32_t
typedef s_hash_key ght_hash_key_t
typedef s_hash_entry ght_hash_entry_t
typedef ght_uint32_t(* ght_fn_hash_t )(ght_hash_key_t *p_key)
typedef void *(* ght_fn_alloc_t )(size_t size)
typedef void(* ght_fn_free_t )(void *ptr)
typedef void(* ght_fn_bucket_free_callback_t )(void *data, void *key)

Functions

ght_hash_table_t * ght_create (unsigned int i_size)
void ght_set_alloc (ght_hash_table_t *p_ht, ght_fn_alloc_t fn_alloc, ght_fn_free_t fn_free)
void ght_set_hash (ght_hash_table_t *p_ht, ght_fn_hash_t fn_hash)
void ght_set_heuristics (ght_hash_table_t *p_ht, int i_heuristics)
void ght_set_rehash (ght_hash_table_t *p_ht, int b_rehash)
void ght_set_bounded_buckets (ght_hash_table_t *p_ht, unsigned int limit, ght_fn_bucket_free_callback_t fn)
unsigned int ght_size (ght_hash_table_t *p_ht)
unsigned int ght_table_size (ght_hash_table_t *p_ht)
int ght_insert (ght_hash_table_t *p_ht, void *p_entry_data, unsigned int i_key_size, void *p_key_data)
void * ght_replace (ght_hash_table_t *p_ht, void *p_entry_data, unsigned int i_key_size, void *p_key_data)
void * ght_get (ght_hash_table_t *p_ht, unsigned int i_key_size, void *p_key_data)
void * ght_remove (ght_hash_table_t *p_ht, unsigned int i_key_size, void *p_key_data)
void * ght_first (ght_hash_table_t *p_ht, ght_iterator_t *p_iterator, void **pp_key)
void * ght_next (ght_hash_table_t *p_ht, ght_iterator_t *p_iterator, void **pp_key)
void ght_rehash (ght_hash_table_t *p_ht, unsigned int i_size)
void ght_finalize (ght_hash_table_t *p_ht)
ght_uint32_t ght_one_at_a_time_hash (ght_hash_key_t *p_key)
ght_uint32_t ght_rotating_hash (ght_hash_key_t *p_key)
ght_uint32_t ght_crc_hash (ght_hash_key_t *p_key)

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 example/simple.c file found in the distribution. hash_test.c provides a more comlpete example.

Some basic properties of the hash table are:

Typedef Documentation

typedef void*(* ght_fn_alloc_t)(size_t size)
 

Definition of the allocation function pointers. This is simply the same definition as malloc().

Parameters:
size the size to allocate. This will always be sizeof(ght_hash_entry_t) + key_size.
Returns:
a pointer to the allocated region, or NULL if the allocation failed.

typedef void(* ght_fn_free_t)(void *ptr)
 

Definition of the deallocation function pointers. This is simply the same definition as free().

Parameters:
ptr a pointer to the region to free.

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  ) 
 

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 hash table is created with ght_one_at_a_time_hash() as hash function, automatic rehashing disabled, malloc() as the memory allocator and no heuristics.

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.
See also:
ght_set_hash(), ght_set_heuristics(), ght_set_rehash(),

ght_set_alloc()

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_key;
 void *p_e;

 for(p_e = ght_first(p_table, &iterator, &p_key); p_e; p_e = ght_next(p_table, &iterator, &p_key))
   {
     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,
void **  pp_key
) 
 

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. Note that removal during an iteration is only safe for the current entry or an entry which has already been iterated over.

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_key;
 void *p_e;

 [Create table etc...]
 for(p_e = ght_first(p_table, &iterator, &p_key); p_e; p_e = ght_next(p_table, &iterator, &p_key))
   {
      [Do something with the current entry p_e and it's key p_key]
   }

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.
pp_key a pointer to the pointer of the key (NULL if none).
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" (including the ''-terminator) is used as a key for the integer 15.

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

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

 ret = ght_insert(p_table,
                  p_data,
                  sizeof(char)*(strlen(p_key_data)+1), 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,
void **  pp_key
) 
 

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.
pp_key a pointer to the pointer of the key (NULL if none).
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.

void* ght_replace (  ght_hash_table_t *  p_ht,
void *  p_entry_data,
unsigned int  i_key_size,
void *  p_key_data
) 
 

Replace an entry in the hash table. This function will return an error if the entry to be replaced does not exist, i.e. it cannot be used to insert new entries.

Parameters:
p_ht the hash table to search in.
p_entry_data the new data for the key.
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 old value or NULL if the operation failed.

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()

void ght_set_alloc (  ght_hash_table_t *  p_ht,
ght_fn_alloc_t  fn_alloc,
ght_fn_free_t  fn_free
) 
 

Set the allocation/freeing functions to use for a hash table. The allocation function will only be called when a new entry is inserted.

The allocation size will always be sizeof(ght_hash_entry_t) + sizeof(ght_hash_key_t) + key_size. The actual size varies with the key size.

If this function is not called, malloc() and free() will be used for allocation and freeing.

Warning:
Always call this function before any entries are inserted into the table. Otherwise, the new free() might be called on something that were allocated with another allocation function.
Parameters:
p_ht the hash table to set the memory management functions for.
fn_alloc the allocation function to use.
fn_free the deallocation function to use.

void ght_set_bounded_buckets (  ght_hash_table_t *  p_ht,
unsigned int  limit,
ght_fn_bucket_free_callback_t  fn
) 
 

Enable or disable bounded buckets.

With bounded buckets, the hash table will act as a cache, only holding a fixed number of elements per bucket. limit specifies the limit of elements per bucket. When inserting elements with ght_insert into a bounded table, the last entry in the bucket chain will be free:d. libghthash will then call the callback function fn, which allow the user of the library to dispose of the key and data.

Bounded buckets are disabled by default.

Parameters:
p_ht the hash table to set the bounded buckets for.
limit the maximum number of items in each bucket. If limit is set to 0, bounded buckets are disabled.
fn a pointer to a callback function that is called when an entry is free:d. The function should return 0 if the entry can be freed, or -1 otherwise. If -1 is returned, libghthash will select the second last entry and call the callback with that instead.

void ght_set_hash (  ght_hash_table_t *  p_ht,
ght_fn_hash_t  fn_hash
) 
 

Set the hash function to use for a hash table.

Warning:
Always call this function before any entries are inserted into the table. Otherwise, it will not be possible to find entries that were inserted before this function was called.
Parameters:
p_ht the hash table set the hash function for.
fn_hash the hash function.

void ght_set_heuristics (  ght_hash_table_t *  p_ht,
int  i_heuristics
) 
 

Set the heuristics to use for the hash table. The possible values are:

  • GHT_HEURISTICS_NONE: Don't use any heuristics.
  • 0: Same as above.
  • GHT_HEURISTICS_TRANSPOSE: Use transposing heuristics. An accessed element will move one step up in the bucket-list with this method.
  • 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.

Parameters:
p_ht the hash table set the heuristics for.
i_heuristics the heuristics to use.

void ght_set_rehash (  ght_hash_table_t *  p_ht,
int  b_rehash
) 
 

Enable or disable automatic rehashing.

With automatic rehashing, the table will rehash itself 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:
p_ht the hash table to set rehashing for.
b_rehash TRUE if rehashing should be used or FALSE if it should not be used.

unsigned int ght_size (  ght_hash_table_t *  p_ht  ) 
 

Get the size (the number of items) of the hash table.

Parameters:
p_ht the hash table to get the size for.
Returns:
the number of items in the hash table.

unsigned int ght_table_size (  ght_hash_table_t *  p_ht  ) 
 

Get the table size (the number of buckets) of the hash table.

Parameters:
p_ht the hash table to get the table size for.
Returns:
the number of buckets in the hash table.

Generated on Sun Nov 27 10:49:06 2005 for libghthash by  doxygen 1.4.2