Hash tables

Typedefs
typedef struct hashtab_s	hashtab_t

Functions
int	Hash_Add (hashtab_t *tab, void *ele)
	add an entry to a hash table. More...
int	Hash_AddElement (hashtab_t *tab, void *ele)
	add an entry to a hash table. More...
unsigned long	Hash_Buffer (const void *buf, int len)
	hash a buffer. More...
void *	Hash_Del (hashtab_t *tab, const char *key)
	delete an element from a hash table. More...
void *	Hash_DelElement (hashtab_t *tab, void *ele)
	delete an element from a hash table. More...
void	Hash_DelTable (hashtab_t *tab)
	delete a hash table. More...
void *	Hash_Find (hashtab_t *tab, const char *key)
	find an element within a hash table. More...
void *	Hash_FindElement (hashtab_t *tab, const void *ele)
	find an element within a hash table. More...
void **	Hash_FindElementList (hashtab_t *tab, void *ele)
	find a list of elements within a hash table. More...
void **	Hash_FindList (hashtab_t *tab, const char *key)
	find a list of elements within a hash table. More...
void	Hash_FlushTable (hashtab_t *tab)
	clean out all the entries from a hash table, starting over again. More...
void	Hash_Free (hashtab_t *tab, void *ele)
	calls the free element function for the supplied ele More...
void **	Hash_GetList (hashtab_t *tab)
	list of all elements in the table. More...
hashtab_t *	Hash_NewTable (int tsize, const char *(*gk)(const void *, void *), void(*f)(void *, void *), void *ud)
	create a new hash table. More...
size_t	Hash_NumElements (hashtab_t *tab)
	get the size of the table More...
void	Hash_SetHashCompare (hashtab_t *tab, uintptr_t(*gh)(const void *, void *), int(*cmp)(const void *, const void *, void *))
	change the hash and compare functions used by the Hash_*Element functions. More...
void	Hash_Stats (hashtab_t *tab)
	dump statistics about the hash table More...
unsigned long	Hash_String (const char *str)
	hash a string. More...

Detailed Description

Typedef Documentation

typedef struct hashtab_s hashtab_t

Function Documentation

int Hash_Add	(	hashtab_t *	tab,
		void *	ele
	)

add an entry to a hash table.

Parameters

tab	the table to be added to
ele	the element to add to the table

Returns

0 for success, -1 for error.

int Hash_AddElement	(	hashtab_t *	tab,
		void *	ele
	)

add an entry to a hash table.

Parameters

tab	the table to be added to
ele	the element to add to the table

Returns

0 for success, -1 for error.

unsigned long Hash_Buffer	(	const void *	buf,
		int	len
	)

hash a buffer.

Parameters

buf	the buffer to hash
len	the size of the buffer

Returns

the hash value of the string.

void* Hash_Del	(	hashtab_t *	tab,
		const char *	key
	)

delete an element from a hash table.

Parameters

tab	the table to remove the element from
key	the key string identifying the element to be deleted

Returns

a pointer to the element on success, 0 if the element could not be found.

Does NOT call the free element function. That is the caller's responsibility.

void* Hash_DelElement	(	hashtab_t *	tab,
		void *	ele
	)

delete an element from a hash table.

Parameters

tab	the table to remove the element from
ele	element with info identifying the element to be deleted

Returns

a pointer to the element on success, 0 if the element could not be found.

Does NOT call the free element function. That is the caller's responsibility.

void Hash_DelTable

(

hashtab_t *

tab

)

delete a hash table.

Parameters

tab	the table to be deleted

void* Hash_Find	(	hashtab_t *	tab,
		const char *	key
	)

find an element within a hash table.

Parameters

tab	the table to search
key	the key string identifying the element being searched for

Returns

pointer to the element if found, otherwise 0.

void* Hash_FindElement	(	hashtab_t *	tab,
		const void *	ele
	)

find an element within a hash table.

Parameters

tab	the table to search
ele	element with info identifying the element being searched for

Returns

pointer to the element if found, otherwise 0.

void** Hash_FindElementList	(	hashtab_t *	tab,
		void *	ele
	)

find a list of elements within a hash table.

Parameters

tab	the table to search
ele	element with info identifying the elements being searched for

Returns

a null terminated list of element pointers if at least one found, otherwise 0.

Note

it is the caller's responsibilty to free() the list.

returned list is guaranteed to be in reverse order of insertion. ie, deleting items from the list in list order will delete the correct items.

void** Hash_FindList	(	hashtab_t *	tab,
		const char *	key
	)

find a list of elements within a hash table.

Parameters

tab	the table to search
key	the key string identifying the elements being searched for

Returns

a null terminated list of element pointers if at least one found, otherwise 0.

Note

it is the caller's responsibilty to free() the list.

returned list is guaranteed to be in reverse order of insertion. ie, deleting items from the list in list order will delete the correct items.

void Hash_FlushTable

(

hashtab_t *

tab

)

clean out all the entries from a hash table, starting over again.

Parameters

tab	the table to be cleared

void Hash_Free	(	hashtab_t *	tab,
		void *	ele
	)

calls the free element function for the supplied ele

Parameters

tab	the table associated with the element (for the free function)
ele	the element to be freed

Example:

Hash_Free (tab, Hash_Del (tab, key));

void** Hash_GetList

(

hashtab_t *

tab

)

list of all elements in the table.

Parameters

tab	the table to list

Returns

a null terminated list of element pointers for all elements in the table

Note

it is the caller's responsibilty to free() the list.

returned list is guaranteed to be in reverse order of insertion for elements with the same key. ie, deleting items from the list in list order will delete the correct items.

hashtab_t* Hash_NewTable	(	int	tsize,
		const char *(*)(const void *, void *)	gk,
		void(*)(void *, void *)	f,
		void *	ud
	)

create a new hash table.

Parameters

tsize	table size. larger values will give better distribution, but use more memory.
gk	a function that returns a string to be used as the key for inserting or finding the element. First parameter is a pointer to the element from which to extract the key, the second is the user data pointer.
f	a function to free the element. Only ever called from Hash_FlushTable and Hash_DelTable. The first parameter is the element to be freed and the second is the user data pointer.
ud	user data pointer. set to whatever you want, it will be passed to the get key and free functions as the second parameter.

Returns

pointer to the hash table (to be passed to the other functions) or 0 on error.

Hash_Add(), Hash_Find(), Hash_FindList() and Hash_Del() use gk and strcmp.

multiple inserions of the same key are fine; later insertions override previous ones until the later one is removed (Hash_Del).

size_t Hash_NumElements

(

hashtab_t *

tab

)

get the size of the table

Parameters

tab	the table in question

Returns

the number of elements in the table.

void Hash_SetHashCompare	(	hashtab_t *	tab,
		uintptr_t(*)(const void *, void *)	gh,
		int(*)(const void *, const void *, void *)	cmp
	)

change the hash and compare functions used by the Hash_*Element functions.

the default hash function just returns the address of the element, and the default compare just compares the addresses. compare is to return 0 for not equal and non-0 otherwise.

With suitably crafted gh and cmp functions, Hash_*Element functions can be mixed with the non-element functions, but by default the results will be undefined.

Parameters

tab	the table configure
gh	takes the same parameters as gk in Hash_NewTable
cmp	is element 1, element 2, userdata

void Hash_Stats

(

hashtab_t *

tab

)

dump statistics about the hash table

Parameters

tab	the table to dump

unsigned long Hash_String

(

const char *

str

)

hash a string.

Parameters

str	the string to hash

Returns

the hash value of the string.

this is the same function as used internally.