QuakeForge  0.7.2.210-815cf
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Modules Pages
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_tHash_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
tabthe table to be added to
elethe 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
tabthe table to be added to
elethe 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
bufthe buffer to hash
lenthe 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
tabthe table to remove the element from
keythe 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
tabthe table to remove the element from
eleelement 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
tabthe table to be deleted
void* Hash_Find ( hashtab_t tab,
const char *  key 
)

find an element within a hash table.

Parameters
tabthe table to search
keythe 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
tabthe table to search
eleelement 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
tabthe table to search
eleelement 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
tabthe table to search
keythe 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
tabthe table to be cleared
void Hash_Free ( hashtab_t tab,
void *  ele 
)

calls the free element function for the supplied ele

Parameters
tabthe table associated with the element (for the free function)
elethe 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
tabthe 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
tsizetable size. larger values will give better distribution, but use more memory.
gka 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.
fa 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.
uduser 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
tabthe 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
tabthe table configure
ghtakes the same parameters as gk in Hash_NewTable
cmpis element 1, element 2, userdata
void Hash_Stats ( hashtab_t tab)

dump statistics about the hash table

Parameters
tabthe table to dump
unsigned long Hash_String ( const char *  str)

hash a string.

Parameters
strthe string to hash
Returns
the hash value of the string.

this is the same function as used internally.