Data Structures | Typedefs | Functions

tommyds/tommyhashlin.h File Reference

Linear chained hashtable. More...

Go to the source code of this file.

Data Structures

struct  tommy_hashlin_struct
 Hashtable container type. More...

Typedefs

typedef tommy_node tommy_hashlin_node
 Hashtable node.
typedef struct tommy_hashlin_struct tommy_hashlin
 Hashtable container type.

Functions

void tommy_hashlin_init (tommy_hashlin *hashlin)
 Initializes the hashtable.
void tommy_hashlin_done (tommy_hashlin *hashlin)
 Deinitializes the hashtable.
void tommy_hashlin_insert (tommy_hashlin *hashlin, tommy_hashlin_node *node, void *data, tommy_hash_t hash)
 Inserts an element in the hashtable.
void * tommy_hashlin_remove (tommy_hashlin *hashlin, tommy_search_func *cmp, const void *cmp_arg, tommy_hash_t hash)
 Searches and removes an element from the hashtable.
tommy_hashlin_nodetommy_hashlin_bucket (tommy_hashlin *hashlin, tommy_hash_t hash)
 Gets the bucket of the specified hash.
void * tommy_hashlin_search (tommy_hashlin *hashlin, tommy_search_func *cmp, const void *cmp_arg, tommy_hash_t hash)
 Searches an element in the hashtable.
void * tommy_hashlin_remove_existing (tommy_hashlin *hashlin, tommy_hashlin_node *node)
 Removes an element from the hashtable.
void tommy_hashlin_foreach (tommy_hashlin *hashlin, tommy_foreach_func *func)
 Calls the specified function for each element in the hashtable.
void tommy_hashlin_foreach_arg (tommy_hashlin *hashlin, tommy_foreach_arg_func *func, void *arg)
 Calls the specified function with an argument for each element in the hashtable.
tommy_count_t tommy_hashlin_count (tommy_hashlin *hashlin)
 Gets the number of elements.
tommy_size_t tommy_hashlin_memory_usage (tommy_hashlin *hashlin)
 Gets the size of allocated memory.

Detailed Description

Linear chained hashtable.

This hashtable resizes dynamically and progressively using a variation of the linear hashing algorithm described in http://en.wikipedia.org/wiki/Linear_hashing

It starts with the minimal size of 16 buckets, it doubles the size then it reaches a load factor greater than 0.5 and it halves the size with a load factor lower than 0.125.

The progressive resize is good for real-time and interactive applications as it makes insert and delete operations taking always the same time.

For resizing it's used a dynamic array that supports access to not contigous segments. In this way we only allocate additional table segments on the heap, without freeing the previous table, and then not increasing the heap fragmentation.

The resize takes place inside tommy_hashlin_insert() and tommy_hashlin_remove(). No resize is done in the tommy_hashlin_search() operation.

To initialize the hashtable you have to call tommy_hashlin_init().

 tommy_hashslin hashlin;

 tommy_hashlin_init(&hashlin);

To insert elements in the hashtable you have to call tommy_hashlin_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.

 struct object {
     int value;
     // other fields
     tommy_node node;
 };

 struct object* obj = malloc(sizeof(struct object)); // creates the object

 obj->value = ...; // initializes the object

 tommy_hashlin_insert(&hashlin, &obj->node, obj, tommy_inthash_u32(obj->value)); // inserts the object

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.

 int compare(const void* arg, const void* obj)
 {
     return *(const int*)arg != ((const struct object*)obj)->value;
 }

 int value_to_find = 1;
 struct object* obj = tommy_hashlin_search(&hashlin, compare, &value_to_find, tommy_inthash_u32(value_to_find));
 if (!obj) {
     // not found
 } else {
     // found
 }

To iterate over all the elements in the hashtable with the same key, you have to use tommy_hashlin_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.

 int value_to_find = 1;
 tommy_node* i = tommy_hashlin_bucket(&hashlin, tommy_inthash_u32(value_to_find));
 while (i) {
     struct object* obj = i->data; // gets the object pointer

     if (obj->value == value_to_find) {
         printf("%d\n", obj->value); // process the object
     }

     i = i->next; // goes to the next element
 }

To remove an element from the hashtable you have to call tommy_hashlin_remove() providing a comparison function, its argument, and the hash of the key to search and remove.

 struct object* obj = tommy_hashlin_remove(&hashlin, compare, &value_to_remove, tommy_inthash_u32(value_to_remove));
 if (obj) {
     free(obj); // frees the object allocated memory
 }

To destroy the hashtable you have to remove all the elements, and deinitialize the hashtable calling tommy_hashlin_done().

 tommy_hashlin_done(&hashlin);

If you need to iterate over all the elements in the hashtable, you can use tommy_hashlin_foreach() or tommy_hashlin_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 Documentation

Hashtable node.

This is the node that you have to include inside your objects.

Hashtable container type.

Note:
Don't use internal fields directly, but access the container only using functions.

Function Documentation

void tommy_hashlin_init ( tommy_hashlin hashlin)

Initializes the hashtable.

void tommy_hashlin_done ( tommy_hashlin hashlin)

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_hashlin_insert ( tommy_hashlin hashlin,
tommy_hashlin_node node,
void *  data,
tommy_hash_t  hash 
)

Inserts an element in the hashtable.

void* tommy_hashlin_remove ( tommy_hashlin hashlin,
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.

Parameters:
cmpCompare 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_argCompare argument passed as first argument of the compare function.
hashHash of the element to find and remove.
Returns:
The removed element, or 0 if not found.
tommy_hashlin_node* tommy_hashlin_bucket ( tommy_hashlin hashlin,
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.

Parameters:
hashHash of the element to find.
Returns:
The head of the bucket, or 0 if empty.
void* tommy_hashlin_search ( tommy_hashlin hashlin,
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.

Parameters:
cmpCompare 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_argCompare argument passed as first argument of the compare function.
hashHash of the element to find.
Returns:
The first element found, or 0 if none.
void* tommy_hashlin_remove_existing ( tommy_hashlin hashlin,
tommy_hashlin_node node 
)

Removes an element from the hashtable.

You must already have the address of the element to remove.

Returns:
The tommy_node::data field of the node removed.
void tommy_hashlin_foreach ( tommy_hashlin hashlin,
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.

 tommy_hashlin hashlin;

 // initializes the hashtable
 tommy_hashlin_init(&hashlin);

 ...

 // creates an object
 struct object* obj = malloc(sizeof(struct object));

 ...

 // insert it in the hashtable
 tommy_hashlin_insert(&hashlin, &obj->node, obj, tommy_inthash_u32(obj->value));

 ...

 // deallocates all the objects iterating the hashtable
 tommy_hashlin_foreach(&hashlin, free);

 // deallocates the hashtable
 tommy_hashlin_done(&hashlin);
void tommy_hashlin_foreach_arg ( tommy_hashlin hashlin,
tommy_foreach_arg_func func,
void *  arg 
)

Calls the specified function with an argument for each element in the hashtable.

tommy_count_t tommy_hashlin_count ( tommy_hashlin hashlin)

Gets the number of elements.

tommy_size_t tommy_hashlin_memory_usage ( tommy_hashlin hashlin)

Gets the size of allocated memory.

It includes the size of the tommy_hashlin_node of the stored elements.