#include <stdlib.h>

Classes
struct	s_hash_key
struct	s_hash_entry
struct	ght_iterator_t
struct	ght_hash_table_t

Macros
#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 struct s_hash_key	ght_hash_key_t
typedef struct 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, const 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, const void *p_key_data)
void *	ght_replace (ght_hash_table_t p_ht, void p_entry_data, unsigned int i_key_size, const void *p_key_data)
void *	ght_get (ght_hash_table_t p_ht, unsigned int i_key_size, const void p_key_data)
void *	ght_remove (ght_hash_table_t p_ht, unsigned int i_key_size, const void p_key_data)
void *	ght_first (ght_hash_table_t p_ht, ght_iterator_t p_iterator, const void **pp_key)
void *	ght_first_keysize (ght_hash_table_t p_ht, ght_iterator_t p_iterator, const void *pp_key, unsigned int size)
void *	ght_next (ght_hash_table_t p_ht, ght_iterator_t p_iterator, const void **pp_key)
void *	ght_next_keysize (ght_hash_table_t p_ht, ght_iterator_t p_iterator, const void *pp_key, unsigned int size)
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:

Both the data stored and the keys are of void type, which means that you can store any kind of data.
The only functions you probably will need to start is:
- ght_create(), which creates a new hash table.
- ght_insert(), which inserts a new entry into a table.
- ght_get(), which searches for an entry.
- ght_remove(), which removes and entry.
- ght_finalize(), which destroys a hash table.
Inserting entries is done without first creating a key, i.e. you insert with the data, the datasize, the key and the key size directly.
The hash table copies the key data when inserting new entries. This means that you should not malloc() the key before inserting a new entry.

Typedef Documentation

◆ ght_fn_alloc_t

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.

◆ ght_fn_bucket_free_callback_t

typedef void(*) ght_fn_bucket_free_callback_t(void *data, const void *key)

Definition of bounded bucket free callback function pointers.

The keys is passed back as const, since it was accepted by ght_insert() as const, but if the callback function knows that a non-const pointer was passed in, it can cast it back to non-const.

◆ ght_fn_free_t

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.

◆ ght_fn_hash_t

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

◆ ght_hash_key_t

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.

◆ ght_uint32_t

typedef unsigned int ght_uint32_t

unsigned 32 bit integer.

Function Documentation

◆ ght_crc_hash()

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 spamb.nosp@m.ait@.nosp@m.lemle.nosp@m.y.ne.nosp@m.t.

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

References ght_crc_hash().

Referenced by ght_crc_hash().

◆ ght_create()

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.

References ght_create().

Referenced by ght_create().

◆ ght_finalize()

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.

References ght_finalize().

Referenced by ght_finalize().

◆ ght_first()

void * ght_first	(	ght_hash_table_t *	p_ht,
		ght_iterator_t *	p_iterator,
		const 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(). The order of the entries will be from the oldest inserted entry to the newest inserted entry. 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()

References ght_first().

Referenced by ght_first().

◆ ght_first_keysize()

void * ght_first_keysize	(	ght_hash_table_t *	p_ht,
		ght_iterator_t *	p_iterator,
		const void **	pp_key,
		unsigned int *	size )

See ght_first() detailed description. This function augments ght_first() by providing a facility to get the size of the keys also. This interface is beneficial for hashtables which use variable length keys.

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).
size	a pointer to the size of the key pointer to by pp_key.

Returns: a pointer to the first entry in the table or NULL if there are no entries.

See also: ght_next()

References ght_first_keysize().

Referenced by ght_first_keysize().

◆ ght_get()

void * ght_get	(	ght_hash_table_t *	p_ht,
		unsigned int	i_key_size,
		const 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.

References ght_get().

Referenced by ght_get().

◆ ght_insert()

int ght_insert	(	ght_hash_table_t *	p_ht,
		void *	p_entry_data,
		unsigned int	i_key_size,
		const 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 '\0'-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.

References ght_insert().

Referenced by ght_insert().

◆ ght_next()

void * ght_next	(	ght_hash_table_t *	p_ht,
		ght_iterator_t *	p_iterator,
		const 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()

References ght_next().

Referenced by ght_next().

◆ ght_next_keysize()

void * ght_next_keysize	(	ght_hash_table_t *	p_ht,
		ght_iterator_t *	p_iterator,
		const void **	pp_key,
		unsigned int *	size )

This functions works just like ght_next() but also returns the keysize. This is beneficial for users of the hash table which use variable length keys.

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).
size	a pointer to the size of the key pointer to by pp_key.

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

References ght_next_keysize().

Referenced by ght_next_keysize().

◆ ght_one_at_a_time_hash()

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

References ght_one_at_a_time_hash().

Referenced by ght_one_at_a_time_hash().

◆ ght_rehash()

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

References ght_rehash().

Referenced by ght_rehash().

◆ ght_remove()

void * ght_remove	(	ght_hash_table_t *	p_ht,
		unsigned int	i_key_size,
		const 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.

References ght_remove().

Referenced by ght_remove().

◆ ght_replace()

void * ght_replace	(	ght_hash_table_t *	p_ht,
		void *	p_entry_data,
		unsigned int	i_key_size,
		const 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. Replacing an entry does not affect its iteration order.

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.

References ght_replace().

Referenced by ght_replace().

◆ ght_rotating_hash()

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

References ght_rotating_hash().

Referenced by ght_rotating_hash().

◆ ght_set_alloc()

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.

References ght_set_alloc().

Referenced by ght_set_alloc().

◆ ght_set_bounded_buckets()

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.

References ght_set_bounded_buckets().

Referenced by ght_set_bounded_buckets().

◆ ght_set_hash()

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.

References ght_set_hash().

Referenced by ght_set_hash().

◆ ght_set_heuristics()

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.

References ght_set_heuristics().

Referenced by ght_set_heuristics().

◆ ght_set_rehash()

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.

References ght_set_rehash().

Referenced by ght_set_rehash().

◆ ght_size()

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.

References ght_size().

Referenced by ght_size().

◆ ght_table_size()

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.

References ght_table_size().

Referenced by ght_table_size().

Classes

Macros

Typedefs

Functions

Detailed Description

Typedef Documentation

◆ ght_fn_alloc_t

◆ ght_fn_bucket_free_callback_t

◆ ght_fn_free_t

◆ ght_fn_hash_t

◆ ght_hash_key_t

◆ ght_uint32_t

Function Documentation

◆ ght_crc_hash()

◆ ght_create()

◆ ght_finalize()

◆ ght_first()

◆ ght_first_keysize()

◆ ght_get()

◆ ght_insert()

◆ ght_next()

◆ ght_next_keysize()

◆ ght_one_at_a_time_hash()

◆ ght_rehash()

◆ ght_remove()

◆ ght_replace()

◆ ght_rotating_hash()

◆ ght_set_alloc()

◆ ght_set_bounded_buckets()

◆ ght_set_hash()

◆ ght_set_heuristics()

◆ ght_set_rehash()

◆ ght_size()

◆ ght_table_size()