Fixed size chained hashtable. More...
Go to the source code of this file.
Data Structures | |
struct | tommy_hashtable_struct |
Hashtable container type. More... | |
Typedefs | |
typedef tommy_node | tommy_hashtable_node |
Hashtable node. More... | |
typedef struct tommy_hashtable_struct | tommy_hashtable |
Hashtable container type. More... | |
Functions | |
void | tommy_hashtable_init (tommy_hashtable *hashtable, tommy_count_t bucket_max) |
Initializes the hashtable. More... | |
void | tommy_hashtable_done (tommy_hashtable *hashtable) |
Deinitializes the hashtable. More... | |
void | tommy_hashtable_insert (tommy_hashtable *hashtable, tommy_hashtable_node *node, void *data, tommy_hash_t hash) |
Inserts an element in the hashtable. More... | |
void * | tommy_hashtable_remove (tommy_hashtable *hashtable, tommy_search_func *cmp, const void *cmp_arg, tommy_hash_t hash) |
Searches and removes an element from the hashtable. More... | |
tommy_hashtable_node * | tommy_hashtable_bucket (tommy_hashtable *hashtable, tommy_hash_t hash) |
Gets the bucket of the specified hash. More... | |
void * | tommy_hashtable_search (tommy_hashtable *hashtable, tommy_search_func *cmp, const void *cmp_arg, tommy_hash_t hash) |
Searches an element in the hashtable. More... | |
void * | tommy_hashtable_remove_existing (tommy_hashtable *hashtable, tommy_hashtable_node *node) |
Removes an element from the hashtable. More... | |
void | tommy_hashtable_foreach (tommy_hashtable *hashtable, tommy_foreach_func *func) |
Calls the specified function for each element in the hashtable. More... | |
void | tommy_hashtable_foreach_arg (tommy_hashtable *hashtable, tommy_foreach_arg_func *func, void *arg) |
Calls the specified function with an argument for each element in the hashtable. More... | |
tommy_count_t | tommy_hashtable_count (tommy_hashtable *hashtable) |
Gets the number of elements. More... | |
tommy_size_t | tommy_hashtable_memory_usage (tommy_hashtable *hashtable) |
Gets the size of allocated memory. More... | |
Fixed size chained hashtable.
This hashtable is a standard implementation of a chained hashtable with a fixed size.
Note that performances starts to degenerate after reaching a load factor greater than 0.75. The tommy_hashdyn and tommy_hashlin hashtables fix this problem growing dynamically.
To initialize the hashtable you have to call tommy_hashtable_init() specifing the fixed bucket size.
To insert elements in the hashtable you have to call tommy_hashtable_insert() for each element. In the insertion call you have to specify the address of the node, the address of the object, and the hash value of the key to use. The address of the object is used to initialize the tommy_node::data field of the node, and the hash to initialize the tommy_node::key field.
To find and element in the hashtable you have to call tommy_hashtable_search() providing a comparison function, its argument, and the hash of the key to search.
To iterate over all the elements in the hashtable with the same key, you have to use tommy_hashtable_bucket() and follow the tommy_node::next pointer until NULL. You have also to check explicitely for the key, as the bucket may contains different keys.
To remove an element from the hashtable you have to call tommy_hashtable_remove() providing a comparison function, its argument, and the hash of the key to search and remove.
To destroy the hashtable you have to remove all the elements, and deinitialize the hashtable calling tommy_hashtable_done().
If you need to iterate over all the elements in the hashtable, you can use tommy_hashtable_foreach() or tommy_hashtable_foreach_arg(). If you need a more precise control with a real iteration, you have to insert all the elements also in a tommy_list, and use the list to iterate. See the Tommy Multi Indexing example for more detail.
typedef tommy_node tommy_hashtable_node |
Hashtable node.
This is the node that you have to include inside your objects.
typedef struct tommy_hashtable_struct tommy_hashtable |
Hashtable container type.
void tommy_hashtable_init | ( | tommy_hashtable * | hashtable, |
tommy_count_t | bucket_max | ||
) |
Initializes the hashtable.
buckets | Minimum number of buckets to allocate. The effective number used is the next power of 2. |
void tommy_hashtable_done | ( | tommy_hashtable * | hashtable | ) |
Deinitializes the hashtable.
You can call this function with elements still contained, but such elements are not going to be freed by this call.
void tommy_hashtable_insert | ( | tommy_hashtable * | hashtable, |
tommy_hashtable_node * | node, | ||
void * | data, | ||
tommy_hash_t | hash | ||
) |
Inserts an element in the hashtable.
void* tommy_hashtable_remove | ( | tommy_hashtable * | hashtable, |
tommy_search_func * | cmp, | ||
const void * | cmp_arg, | ||
tommy_hash_t | hash | ||
) |
Searches and removes an element from the hashtable.
You have to provide a compare function and the hash of the element you want to remove. If the element is not found, 0 is returned. If more equal elements are present, the first one is removed.
cmp | Compare function called with cmp_arg as first argument and with the element to compare as a second one. The function should return 0 for equal elements, anything other for different elements. |
cmp_arg | Compare argument passed as first argument of the compare function. |
hash | Hash of the element to find and remove. |
tommy_hashtable_node* tommy_hashtable_bucket | ( | tommy_hashtable * | hashtable, |
tommy_hash_t | hash | ||
) |
Gets the bucket of the specified hash.
The bucket is guaranteed to contain ALL the elements with the specified hash, but it can contain also others. You can access elements in the bucket following the ::next pointer until 0.
hash | Hash of the element to find. |
void* tommy_hashtable_search | ( | tommy_hashtable * | hashtable, |
tommy_search_func * | cmp, | ||
const void * | cmp_arg, | ||
tommy_hash_t | hash | ||
) |
Searches an element in the hashtable.
You have to provide a compare function and the hash of the element you want to find. If more equal elements are present, the first one is returned.
cmp | Compare function called with cmp_arg as first argument and with the element to compare as a second one. The function should return 0 for equal elements, anything other for different elements. |
cmp_arg | Compare argument passed as first argument of the compare function. |
hash | Hash of the element to find. |
void* tommy_hashtable_remove_existing | ( | tommy_hashtable * | hashtable, |
tommy_hashtable_node * | node | ||
) |
Removes an element from the hashtable.
You must already have the address of the element to remove.
void tommy_hashtable_foreach | ( | tommy_hashtable * | hashtable, |
tommy_foreach_func * | func | ||
) |
Calls the specified function for each element in the hashtable.
You cannot add or remove elements from the inside of the callback, but can use it to deallocate them.
void tommy_hashtable_foreach_arg | ( | tommy_hashtable * | hashtable, |
tommy_foreach_arg_func * | func, | ||
void * | arg | ||
) |
Calls the specified function with an argument for each element in the hashtable.
tommy_count_t tommy_hashtable_count | ( | tommy_hashtable * | hashtable | ) |
Gets the number of elements.
tommy_size_t tommy_hashtable_memory_usage | ( | tommy_hashtable * | hashtable | ) |
Gets the size of allocated memory.
It includes the size of the tommy_hashtable_node of the stored elements.