tommyhashdyn.h File Reference

#include "tommyhash.h"

Go to the source code of this file.

Classes
struct	tommy_hashdyn_struct

Macros
#define	TOMMY_HASHDYN_BIT   4

Typedefs
typedef tommy_node	tommy_hashdyn_node
typedef struct tommy_hashdyn_struct	tommy_hashdyn

Functions
void	tommy_hashdyn_init (tommy_hashdyn *hashdyn)
void	tommy_hashdyn_done (tommy_hashdyn *hashdyn)
void	tommy_hashdyn_insert (tommy_hashdyn *hashdyn, tommy_hashdyn_node *node, void *data, tommy_hash_t hash)
void *	tommy_hashdyn_remove (tommy_hashdyn *hashdyn, tommy_search_func *cmp, const void *cmp_arg, tommy_hash_t hash)
tommy_inline tommy_hashdyn_node *	tommy_hashdyn_bucket (tommy_hashdyn *hashdyn, tommy_hash_t hash)
tommy_inline void *	tommy_hashdyn_search (tommy_hashdyn *hashdyn, tommy_search_func *cmp, const void *cmp_arg, tommy_hash_t hash)
void *	tommy_hashdyn_remove_existing (tommy_hashdyn *hashdyn, tommy_hashdyn_node *node)
void	tommy_hashdyn_foreach (tommy_hashdyn *hashdyn, tommy_foreach_func *func)
void	tommy_hashdyn_foreach_arg (tommy_hashdyn *hashdyn, tommy_foreach_arg_func *func, void *arg)
tommy_inline tommy_count_t	tommy_hashdyn_count (tommy_hashdyn *hashdyn)
tommy_size_t	tommy_hashdyn_memory_usage (tommy_hashdyn *hashdyn)

Detailed Description

Dynamic chained hashtable.

This hashtable resizes dynamically. 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.

All the elements are reallocated in a single resize operation done inside tommy_hashdyn_insert() or tommy_hashdyn_remove().

Note that the resize operation takes approximatively 100 [ms] with 1 million of elements, and 1 [second] with 10 millions. This could be a problem in real-time applications.

The resize also fragment the heap, as it involves allocating a double-sized table, copy elements, and deallocating the older table. Leaving a big hole in the heap.

The ::tommy_hashlin hashtable fixes both problems.

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

tommy_hashslin hashdyn;

tommy_hashdyn_init(&hashdyn);

To insert elements in the hashtable you have to call tommy_hashdyn_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 {
    tommy_node node;
    // other fields
    int value;
};

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

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

tommy_hashdyn_insert(&hashdyn, &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_hashdyn_search(&hashdyn, 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_hashdyn_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_hashdyn_bucket(&hashdyn, 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_hashdyn_remove() providing a comparison function, its argument, and the hash of the key to search and remove.

struct object* obj = tommy_hashdyn_remove(&hashdyn, 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_hashdyn_done().

tommy_hashdyn_done(&hashdyn);

If you need to iterate over all the elements in the hashtable, you can use tommy_hashdyn_foreach() or tommy_hashdyn_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 multiindex example for more detail.

Definition in file tommyhashdyn.h.

Macro Definition Documentation

TOMMY_HASHDYN_BIT

#define TOMMY_HASHDYN_BIT   4

Definition at line 149 of file tommyhashdyn.h.

Typedef Documentation

tommy_hashdyn

typedef struct tommy_hashdyn_struct tommy_hashdyn

Hashtable container type.

Note

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

tommy_hashdyn_node

typedef tommy_node tommy_hashdyn_node

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

Definition at line 155 of file tommyhashdyn.h.

Function Documentation

tommy_hashdyn_bucket()

tommy_inline tommy_hashdyn_node* tommy_hashdyn_bucket	(	tommy_hashdyn *	hashdyn,
		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

hash	Hash of the element to find.

Returns

The head of the bucket, or 0 if empty.

Definition at line 208 of file tommyhashdyn.h.

tommy_hashdyn_count()

tommy_inline tommy_count_t tommy_hashdyn_count

(

tommy_hashdyn *

hashdyn

)

Gets the number of elements.

Definition at line 283 of file tommyhashdyn.h.

tommy_hashdyn_done()

void tommy_hashdyn_done

(

tommy_hashdyn *

hashdyn

)

Deinitializes the hashtable.

You can call this function with elements still contained, but such elements are not going to be freed by this call.

tommy_hashdyn_foreach()

void tommy_hashdyn_foreach	(	tommy_hashdyn *	hashdyn,
		tommy_foreach_func *	func
	)

Calls the specified function for each element in the hashtable.

You can use this function to deallocate all the elements inserted.

tommy_hashdyn hashdyn;

// initializes the hashtable
tommy_hashdyn_init(&hashdyn);

...

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

...

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

...

// deallocates all the objects iterating the hashtable
tommy_hashdyn_foreach(&hashdyn, free);

// deallocates the hashtable
tommy_hashdyn_done(&hashdyn);

tommy_hashdyn_foreach_arg()

void tommy_hashdyn_foreach_arg	(	tommy_hashdyn *	hashdyn,
		tommy_foreach_arg_func *	func,
		void *	arg
	)

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

tommy_hashdyn_init()

void tommy_hashdyn_init

(

tommy_hashdyn *

hashdyn

)

Initializes the hashtable.

tommy_hashdyn_insert()

void tommy_hashdyn_insert	(	tommy_hashdyn *	hashdyn,
		tommy_hashdyn_node *	node,
		void *	data,
		tommy_hash_t	hash
	)

Inserts an element in the hashtable.

tommy_hashdyn_memory_usage()

tommy_size_t tommy_hashdyn_memory_usage

(

tommy_hashdyn *

hashdyn

)

Gets the size of allocated memory. It includes the size of the tommy_hashdyn_node of the stored elements.

tommy_hashdyn_remove()

void* tommy_hashdyn_remove	(	tommy_hashdyn *	hashdyn,
		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

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.

Returns

The removed element, or 0 if not found.

tommy_hashdyn_remove_existing()

void* tommy_hashdyn_remove_existing	(	tommy_hashdyn *	hashdyn,
		tommy_hashdyn_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.

tommy_hashdyn_search()

tommy_inline void* tommy_hashdyn_search	(	tommy_hashdyn *	hashdyn,
		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

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.

Returns

The first element found, or 0 if none.

Definition at line 223 of file tommyhashdyn.h.