hashtableqs

A hashtable consisting of a table of indices to objects. More...

Data Structures
struct	util_hashtableqs
	Structure for hastableqs, see also hashtableqs. More...

Macros
#define	COMPUTE_HASHTABLEQS_SIZE(num)   (sizeof(struct util_hashtableqs) + sizeof(unsigned int)*(num))
	Helper macro to compute the hashtable size. More...
#define	UTIL_HASHTABLEQS_ITERATOR_INVALID   -1
	Identifier for invalid util_hashtableqs_iterator. More...
#define	util_hashtableqs_foreach(it, ht)   for (it = util_hashtableqs_iterator_first(ht); it != -1; it = util_hashtableqs_iterator_next(ht, it))
	Foreach loop for iterating through a hashtableqs. More...

Typedefs
typedef int64_t	util_hashtableqs_iterator
	Iterator for hashtableqs. More...

Functions
size_t	util_hashtableqs_size (unsigned int num_elements)
	Computes the size in bytes for num_elements hashtable entries. More...
struct util_hashtableqs *	util_hashtableqs_init (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_hashtableqs_add (struct util_hashtableqs *ht, const void *key, unsigned int value)
	Adds a new key/value pair to the hashtable. More...
unsigned int	util_hashtableqs_lookup (struct util_hashtableqs *ht, const void *key)
	Hashtable lookup function. More...
static unsigned int	util_hashtableqs_get (struct util_hashtableqs *ht, int idx)
util_hashtableqs_iterator	util_hashtableqs_iterator_first (struct util_hashtableqs *ht)
	Get an iterator to the first element of the hashtableqs ht. More...
util_hashtableqs_iterator	util_hashtableqs_iterator_next (struct util_hashtableqs *ht, util_hashtableqs_iterator it)
	Get an iterator to the next element. More...
unsigned int	util_hashtableqs_iterator_value (struct util_hashtableqs *ht, util_hashtableqs_iterator it)
	Get the valueindex for an iterator it.

Detailed Description

A hashtable consisting of a table of indices to objects.

This table uses indices instead of pointers to make the hashtable relocatable. A table of objects must be stored outside if this datastructure. This hashtable only stores the indices to this table. It uses quadratic probing for resolving hash collisions. Note, that this means you can only add elements to this table, but cannot remove them anymore. This is mainly useful for static address spaces. Use util_hashtable instead if you need to be able to remove values again.

Macro Definition Documentation

#define COMPUTE_HASHTABLEQS_SIZE

(

num

)

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

Helper macro to compute the hashtable size.

Parameters

num	number of objects

#define util_hashtableqs_foreach	(		it,
			ht
	)		for (it = util_hashtableqs_iterator_first(ht); it != -1; it = util_hashtableqs_iterator_next(ht, it))

Foreach loop for iterating through a hashtableqs.

Parameters

it	util_hashtableqs_iterator to access current element.
ht	Hashtableqs to iterate through.

#define UTIL_HASHTABLEQS_ITERATOR_INVALID   -1

Identifier for invalid util_hashtableqs_iterator.

Typedef Documentation

typedef int64_t util_hashtableqs_iterator

Iterator for hashtableqs.

Function Documentation

int util_hashtableqs_add	(	struct util_hashtableqs *	ht,
		const void *	key,
		unsigned int	value
	)

Adds a new key/value pair to the hashtable.

Parameters

ht	pointer to hash table object
key	pointer to key, which uniquely identifies the value
value	index to value object

Returns

A positive hashtable index on success, or -1 of the table is full.

static unsigned int util_hashtableqs_get ( struct util_hashtableqs *  ht, int  idx  )

inlinestatic

struct util_hashtableqs* util_hashtableqs_init	(	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_HASHTABLEQS_SIZE(100)];
static struct util_hashtableqs *g_hashtable;

static const void *my_get_key(unsigned int value)
{
    ...
}
static int my_key_compar(const void *key1, const void *key2)
{
    ...
}
static unsigned int my_hash(const void *key, void *userdata)
{
    ...
}

void init(void)
{
    size_t size = util_hashtableqs_size(100);
    g_hashtable = hashtableqs_init(100, my_get_key, my_key_compare, my_hash, g_hashtabledata, size, NULL);
}

TODO: replace code with real snippet from unit test

Parameters

num	number of elements in the table
get_key	function pointer to function which returns the key for a given node
data	memory area to be used for the hashtable

Returns

Pointer to initialized hashtable.

util_hashtableqs_iterator util_hashtableqs_iterator_first

(

struct util_hashtableqs *

ht

)

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

Returns

Iterator or UTIL_HASHTABLEQS_ITERATOR_INVALID if hashtable is empty.

util_hashtableqs_iterator util_hashtableqs_iterator_next	(	struct util_hashtableqs *	ht,
		util_hashtableqs_iterator	it
	)

Get an iterator to the next element.

Parameters

ht	Hashtableqs.
it	Iterator to current element.

Returns

Iterator or UTIL_HASHTABLEQS_ITERATOR_INVALID if hashtable has no more elements.

unsigned int util_hashtableqs_lookup	(	struct util_hashtableqs *	ht,
		const void *	key
	)

Hashtable lookup function.

Parameters

ht	Pointer to hashtable object
key	Key to search for

Returns

A valid value index on success, or UTIL_HT_KEY_NOT_FOUND if the key was not found.

size_t util_hashtableqs_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_hashtableqs_init.