hashtable

A table for hashable objects. More...

Data Structures
struct	util_hashnode
	Structure to include as first field in your custom struct. More...
struct	util_hashtable
	Structure for the hashtable, see also hashtable. More...

Macros
#define	COMPUTE_HASHTABLE_SIZE(num)   (sizeof(struct util_hashtable) + sizeof(unsigned int)*(num))
	Helper macro to compute the hashtable size. More...
#define	UTIL_HASHTABLE_ITERATOR_INVALID   -1
	Identifier for invalid util_hashtable_iterator. More...
#define	util_hashtable_foreach(it, ht)   for (it = util_hashtable_iterator_first(ht); it != -1; it = util_hashtable_iterator_next(ht, it))
	Foreach loop for iterating through a hashtable. More...

Typedefs
typedef struct util_hashnode *(*	Tget_hashnode )(unsigned int valueindex, void *userdata)
	Function which returns the hashnode for a given value. More...
typedef int64_t	util_hashtable_iterator
	Iterator for hashtable. More...

Functions
size_t	util_hashtable_size (unsigned int num_elements)
	Computes the size in bytes for num_elements hashtable entries. More...
struct util_hashtable *	util_hashtable_init (Tget_hashnode get_hashnode, util_hashtable_get_key get_key, util_hashtable_key_compar key_compar, util_hashtable_hash hash, void *data, size_t size, void *userdata)
	Initializes the given memory data as hash table. More...
int	util_hashtable_add (struct util_hashtable *ht, const void *key, unsigned int valueindex)
	Insert a new object into a hashtable. More...
int	util_hashtable_remove (struct util_hashtable *ht, const void *key)
	Remove the object key from the hashtable ht. More...
unsigned int	util_hashtable_lookup (struct util_hashtable *ht, const void *key)
	Lookup an object in the hashtable. More...
util_hashtable_iterator	util_hashtable_iterator_first (struct util_hashtable *ht)
	Get an iterator to the first element of the hashtable ht. More...
util_hashtable_iterator	util_hashtable_iterator_next (struct util_hashtable *ht, util_hashtable_iterator it)
	Get an iterator to the next element. More...
unsigned int	util_hashtable_iterator_value (struct util_hashtable *ht, util_hashtable_iterator it)
	Get the valueindex for an iterator it.
unsigned int	util_hashtable_iterator_remove (struct util_hashtable *ht, util_hashtable_iterator it)
	Remove the element represented by an interator it. More...
unsigned int	util_hashtable_collisions (const struct util_hashtable *ht)
	Computes the number of collisions in the hashtable. More...

Detailed Description

A table for hashable objects.

The objects must have a fixed index, this can be achieved by storing the objects in an array or objectpool.

The objects can be of arbitrary type, but must contain the util_hashnode as member at any position. Think of <yourtype> is derived from util_hashnode.

struct mystruct {
    struct util_hashnode header;
    int foo;
    float bar;
}

Macro Definition Documentation

#define COMPUTE_HASHTABLE_SIZE

(

num

)

(sizeof(struct util_hashtable) + sizeof(unsigned int)*(num))

Helper macro to compute the hashtable size.

Parameters

num	number of objects

#define util_hashtable_foreach	(		it,
			ht
	)		for (it = util_hashtable_iterator_first(ht); it != -1; it = util_hashtable_iterator_next(ht, it))

Foreach loop for iterating through a hashtable.

Parameters

it	util_hashtable_iterator to access current element.
ht	Hashtable to iterate through.

#define UTIL_HASHTABLE_ITERATOR_INVALID   -1

Identifier for invalid util_hashtable_iterator.

Typedef Documentation

typedef struct util_hashnode*(* Tget_hashnode)(unsigned int valueindex, void *userdata)

Function which returns the hashnode for a given value.

typedef int64_t util_hashtable_iterator

Iterator for hashtable.

Function Documentation

int util_hashtable_add	(	struct util_hashtable *	ht,
		const void *	key,
		unsigned int	valueindex
	)

Insert a new object into a hashtable.

Parameters

ht	Hashtable to add object to.
key	Object to add, must be derived from util_hashnode.
valueindex	Index to identify the object.

Returns

Index of the object in the hashtable.

unsigned int util_hashtable_collisions

(

const struct util_hashtable *

ht

)

Computes the number of collisions in the hashtable.

This is only diagnostic information.

Returns

Number of collisions in hashtable;

struct util_hashtable* util_hashtable_init	(	Tget_hashnode	get_hashnode,
		util_hashtable_get_key	get_key,
		util_hashtable_key_compar	key_compar,
		util_hashtable_hash	hash,
		void *	data,
		size_t	size,
		void *	userdata
	)

Initializes the given memory data as hash table.

The size of data must be big enough to hold num_objects*object_size+ sizeof(struct objectpool).

Usage:

static unsigned char g_hashtabledata[COMPUTE_HASHTABLE_SIZE(100)];
static struct hashtable *g_hashtable;

struct my_data {
    struct util_hashnode hashnode;
    const char *key;
    int value;
};

static struct util_hashnode my_get_hashnode(unsigned int valueindex, void *userdata)
{
    const my_data *data = objectpool_get(userdata, valueindex);
    return &data->hashnode;
}

static const void *my_get_key(unsigned int valueindex, void *userdata)
{
    const my_data *data = objectpool_get(userdata, valueindex);
    return data->key;
}

static int my_key_compar(const void *key1, const void *key2, void *userdata)
{
    return strcmp(key1, key2);
}

static unsigned int my_hash(const void *key, void *userdata)
{
    size_t len = strlen(key);
    return util_rotating_hash(key, len);
}

void init(void)
{
    g_hashtable = hashtable_init(my_get_hashnode, my_get_key, my_key_compar, my_hash, g_hashtabledata, sizeof(g_hashtabledata), NULL);
}

Parameters

git_hashnode	Function which returns util_hashnode element of the indexed data. This is used to resolve hash collissions using a linked list.
get_key	Function which returns the key for a given node.
key_compar	Function for comparing two indexed elements.
hash	Function for computing the elements hash value.
data	memory area to be used for the hashtable
size	size of the data in bytes
userdata	userdata pointer that is returned in all callbacks

Returns

Pointer to initialized hashtable.

util_hashtable_iterator util_hashtable_iterator_first

(

struct util_hashtable *

ht

)

Get an iterator to the first element of the hashtable ht.

Returns

Iterator or negative value if hashtable is empty.

util_hashtable_iterator util_hashtable_iterator_next	(	struct util_hashtable *	ht,
		util_hashtable_iterator	it
	)

Get an iterator to the next element.

Parameters

ht	Hashtable.
it	Iterator to current element.

Returns

Iterator or negative value if hashtable has no more elements.

unsigned int util_hashtable_iterator_remove	(	struct util_hashtable *	ht,
		util_hashtable_iterator	it
	)

Remove the element represented by an interator it.

unsigned int util_hashtable_lookup	(	struct util_hashtable *	ht,
		const void *	key
	)

Lookup an object in the hashtable.

Parameters

ht	Hashtable to lookup object.
key	Object to lookup.

Returns

Valueindex of the object or UTIL_HT_KEY_NOT_FOUND if not found.

int util_hashtable_remove	(	struct util_hashtable *	ht,
		const void *	key
	)

Remove the object key from the hashtable ht.

Returns

Zero on success or errorcode on failure.

size_t util_hashtable_size

(

unsigned int

num_elements

)

Computes the size in bytes for num_elements hashtable entries.

This can be used by the called to allocate the correct amount of memory for util_hashtable_init.