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_t * | ght_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... |
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:
|
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.
|
|
The structure for hash keys. You should not care about this structure unless you plan to write your own hash functions. |
|
unsigned 32 bit integer.
|
|
CRC32 hash. CRC32 hash is a good hash function. This came from Dru Lemley <spambait@lemley.net>.
|
|
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:
|
|
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);
|
|
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] }
|
|
Lookup an entry in the hash table. The entry is not removed from the table.
|
|
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);
|
|
Return the next entry in the hash table. This function should be used for iteration, and must be called after ght_first().
|
|
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
|
|
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
|
|
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).
|
|
Rotating hash. Not so good hash function. This was found in a DrDobbs article, see http://burtleburtle.net/bob/hash/doobs.html
|