Collaboration diagram for API_LowLvl::lib::hash:

Data Structures
union	_Union1_IPTR_HASH_

struct	SprHtblIptr1El

union	_Union2_IPTR_HASH_

struct	SprHtblIptr2El

struct	SprHtblIptrNEl

union	SprHtblIptrEl

struct	SprHtblIptrTbl

struct	SprHtblIptrTblIter

struct	SprStrHashEl

struct	SprStrHashTbl

Typedefs
typedef unsigned int(*	_FuncPtr1_STR_HASH_ )(const char *)

typedef int(*	_FuncPtr2_STR_HASH_ )(const char , const char )

Functions
SprHtblIptrTbl *	spr_htbl_iptr_tbl_free (SprHtblIptrTbl *hash_tbl)

SprHtblIptrTbl *	spr_htbl_iptr_tbl_alloc (SprHtblIptrTbl *hash_tbl_in, unsigned int N, unsigned int size, unsigned int data_size)

void	spr_htbl_stats_iptr_tbl (SprHtblIptrTbl hash_tbl, SprMsgId routine)

SprHtblIptrEl *	spr_htbl_add_iptr1_el (SprHtblIptrTbl hash_tbl, SprHtblIptrEl el)

SprHtblIptrEl *	spr_htbl_add_iptr2_el (SprHtblIptrTbl hash_tbl, SprHtblIptrEl el)

SprHtblIptrEl *	spr_htbl_add_iptrN_el (SprHtblIptrTbl hash_tbl, SprHtblIptrEl el)

void	spr_htbl_istep_iptr_tbl (const SprHtblIptrTbl hash_tbl, SprHtblIptrTblIter iter)
	Initialize an iterator over the hash table. More...

SprHtblIptrEl *	spr_htbl_step_iptr_tbl (SprHtblIptrTblIter *iter)

SprHtblIptrEl *	spr_htbl_add_iptr1 (SprHtblIptrTbl *hash_tbl, uintptr_t key)

SprHtblIptrEl *	spr_htbl_cadd_iptr1 (SprHtblIptrTbl *hash_tbl, uintptr_t key, int nf_null)

SprHtblIptrEl *	spr_htbl_cadd_iptr1_el (SprHtblIptrTbl hash_tbl, SprHtblIptrEl el)

const SprHtblIptrEl *	spr_htbl_find_iptr1_el (const SprHtblIptrTbl *hash_tbl, uintptr_t key)

void *	spr_htbl_rm_iptr1 (SprHtblIptrTbl *hash_tbl, uintptr_t key)

SprHtblIptrEl *	spr_htbl_rm_iptr1_el (SprHtblIptrTbl *hash_tbl, uintptr_t key)

void	spr_htbl_unlink_iptr1 (SprHtblIptrTbl hash_tbl, SprHtblIptrEl el)

void	spr_htbl_unlink_iptr1_el (SprHtblIptrTbl hash_tbl, SprHtblIptrEl el)

SprHtblIptrEl *	spr_htbl_add_iptr2 (SprHtblIptrTbl *hash_tbl, uintptr_t key1, uintptr_t key2)

SprHtblIptrEl *	spr_htbl_cadd_iptr2 (SprHtblIptrTbl *hash_tbl, uintptr_t key1, uintptr_t key2, int nf_null)

SprHtblIptrEl *	spr_htbl_cadd_iptr2_el (SprHtblIptrTbl hash_tbl, SprHtblIptrEl el)

const SprHtblIptrEl *	spr_htbl_find_iptr2_el (const SprHtblIptrTbl *hash_tbl, uintptr_t key1, uintptr_t key2)

void *	spr_htbl_rm_iptr2 (SprHtblIptrTbl *hash_tbl, uintptr_t key1, uintptr_t key2)

SprHtblIptrEl *	spr_htbl_rm_iptr2_el (SprHtblIptrTbl *hash_tbl, uintptr_t key1, uintptr_t key2)

void	spr_htbl_unlink_iptr2 (SprHtblIptrTbl hash_tbl, SprHtblIptrEl el)

void	spr_htbl_unlink_iptr2_el (SprHtblIptrTbl hash_tbl, SprHtblIptrEl el)

SprHtblIptrEl *	spr_htbl_add_iptrN (SprHtblIptrTbl *hash_tbl, uintptr_t key,...)

const SprHtblIptrEl *	spr_htbl_cadd_iptrN (SprHtblIptrTbl *hash_tbl, int nf_null, uintptr_t key,...)

const SprHtblIptrEl *	spr_htbl_cadd_iptrN_el (SprHtblIptrTbl hash_tbl, SprHtblIptrEl el)

const SprHtblIptrEl *	spr_htbl_find_iptrN_el (const SprHtblIptrTbl *hash_tbl, uintptr_t key,...)

void *	spr_htbl_rm_iptrN (SprHtblIptrTbl *hash_tbl, uintptr_t key,...)

SprHtblIptrEl *	spr_htbl_rm_iptrN_el (SprHtblIptrTbl *hash_tbl, uintptr_t key,...)

void	spr_htbl_unlink_iptrN (SprHtblIptrTbl hash_tbl, SprHtblIptrEl el)

void	spr_htbl_unlink_iptrN_el (SprHtblIptrTbl hash_tbl, SprHtblIptrEl el)

SprStrHashTbl *	spr_str_hash_tbl_free (SprStrHashTbl hash_tbl, const int content_flags, SprMsgId routine)

SprStrHashTbl *	spr_str_hash_tbl_alloc (SprStrHashTbl hash_tbl_in, unsigned int size, unsigned int prefix_len, unsigned int(hash_func)(const char ), int(cmp_func)(const char , const char ))

int	spr_str_hash_tbl_add_str (SprStrHashTbl const hash_tbl, const char const str)

int	spr_str_hash_tbl_find_str (const SprStrHashTbl hash_tbl, const char str)

SprStrHashEl *	spr_str_hash_tbl_find_el (const SprStrHashTbl hash_tbl, const SprStrHashEl el)

char *	spr_str_hash_tbl_find_str_el (const SprStrHashTbl hash_tbl, const char str)

int	spr_str_hash_tbl_rm_el (SprStrHashTbl hash_tbl, const char str, int free_flag)

const char *	spr_str_hash_tbl_iterate (const SprStrHashTbl hash_tbl, int iterator)

SprStrHashTbl *	spr_str_hash_tbl_read (SprStrHashTbl hash_tbl, const char fname, const char *up_till)

void	spr_str_hash_tbl_sort (SprStrHashTbl *hash_tbl, int check_rm)

Variables
const SprHtblIptrTbl	spr_htbl_empty_iptr_tbl

const SprStrHashTbl	spr_str_hash_tbl_empty

Detailed Description

Typedef Documentation

typedef unsigned int(* _FuncPtr1_STR_HASH_)(const char *)

typedef int(* _FuncPtr2_STR_HASH_)(const char *,const char *)

Function Documentation

SprHtblIptrTbl* spr_htbl_iptr_tbl_free ( SprHtblIptrTbl * hash_tbl )

Free the hash table.

Note: Only the elements managed by the hash table itself will be deallocated. See alloc_iptrX_hash_tbl() and add_iptrX_el_to_hash_tbl() for more details.

SprHtblIptrTbl* spr_htbl_iptr_tbl_alloc	(	SprHtblIptrTbl *	hash_tbl_in,
		unsigned int	N,
		unsigned int	size,
		unsigned int	data_size
	)

Allocate a hash table of a given initial length size. The key(s) consist of a sequence of N pointers/integers. If an input hash table hash_tbl_in is specified, this one will be initialized, otherwise a new table will be allocated and initialized. The size of the extra data data_size can be set to 0 if the caller will do all necesary memory management.

Parameters

hash_tbl_in	use this table instead of allocating a new one
N	number of keys to hash
size	best guess for the size
data_size	size of the extra data elements

void spr_htbl_stats_iptr_tbl	(	SprHtblIptrTbl *	hash_tbl,
		SprMsgId *	routine
	)

Print some basic statistics about the hash table about fill rate and efficiency.

SprHtblIptrEl * spr_htbl_add_iptr1_el	(	SprHtblIptrTbl *	hash_tbl,
		SprHtblIptrEl *	el
	)

Add a given element to the hash table. The memory for the new hash element is allocated and managed by the caller.

Returns: A pointer to the element.

SprHtblIptrEl * spr_htbl_add_iptr2_el	(	SprHtblIptrTbl *	hash_tbl,
		SprHtblIptrEl *	el
	)

Add a given element to the hash table. The memory for the new hash element is allocated and managed by the caller.

Returns: A pointer to the element.

SprHtblIptrEl * spr_htbl_add_iptrN_el	(	SprHtblIptrTbl *	hash_tbl,
		SprHtblIptrEl *	el
	)

Add a given element to the hash table. The memory for the new hash element is allocated and managed by the caller.

Returns: A pointer to the element.

void spr_htbl_istep_iptr_tbl	(	const SprHtblIptrTbl *	hash_tbl,
		SprHtblIptrTblIter *	iter
	)

Initialize an iterator over the hash table.

SprHtblIptrEl* spr_htbl_step_iptr_tbl ( SprHtblIptrTblIter * iter )

Get the next element from the hash table.

A normal loop looks like: {IptrHashTblIter iter; IptrHashEl *el; for(istep_iptr_hash_tbl(htbl,&iter);(el=step_iptr_hash_tbl(&iter))!=NULL; ) do_whatever; }

Note: the only modification permited during the loop is removing the current element. All other operations will result in undetermined behaviour (usually segmentation fault).

SprHtblIptrEl* spr_htbl_add_iptr1	(	SprHtblIptrTbl *	hash_tbl,
		uintptr_t	key
	)

Create a new hash element for the given key. The memory for the new hash element will be allocated and managed by the hash functions.

Returns: A pointer the newly created hash element on success and (NULL) on failure.

SprHtblIptrEl* spr_htbl_cadd_iptr1	(	SprHtblIptrTbl *	hash_tbl,
		uintptr_t	key,
		int	nf_null
	)

Same as add_iptr1_to_hash_tbl() except that this routine will first test if there is already an element with the given key. If so, a pointer to the existing element will be returned (nf_null == 0) or a NULL pointer will be returned (nf_null != 0). If the element is not already present, a new one will be created.

SprHtblIptrEl* spr_htbl_cadd_iptr1_el	(	SprHtblIptrTbl *	hash_tbl,
		SprHtblIptrEl *	el
	)

Same as add_iptr1_el_to_hash_tbl() except that this routine will first test if there is already an element with the given key. If so, a NULL pointer will be returned. If the element is not already present, the given element will be added to the hash table.

const SprHtblIptrEl* spr_htbl_find_iptr1_el	(	const SprHtblIptrTbl *	hash_tbl,
		uintptr_t	key
	)

Search the element matching the given key key in the hash table. If found, a pointer to the matching element is returned. If not found, a NULL is returned.

void* spr_htbl_rm_iptr1	(	SprHtblIptrTbl *	hash_tbl,
		uintptr_t	key
	)

Search the element matching the given key key in the hash table. If found, the element is removed and a non NULL pointer is returned. If not found, a NULL pointer is returned. The memory for the element is assumed to be managed by the hash table, i.e. it should have been added to the hash table by a add_iptr1_to_hash_tbl() call.

Note: If multiple elements match, only the first matching element is removed.

SprHtblIptrEl* spr_htbl_rm_iptr1_el	(	SprHtblIptrTbl *	hash_tbl,
		uintptr_t	key
	)

Search the element matching the given key key in the hash table. If found, the element is removed from the hash table and a pointer the matching element is returned. If not found, a NULL pointer is returned. The memory for the element is assumed to be managed by the caller, i.e. it should have been added to the hash table by a add_iptr1_el_to_hash_tbl() call.

Note: If multiple elements match, only the first matching element is removed and returned.

void spr_htbl_unlink_iptr1	(	SprHtblIptrTbl *	hash_tbl,
		SprHtblIptrEl *	el
	)

Remove the given element el from the hash table. The memory for the element is assumed to be managed by the hash table, i.e. it should have been added to the hash table by a add_iptr1_to_hash_tbl() call.

void spr_htbl_unlink_iptr1_el	(	SprHtblIptrTbl *	hash_tbl,
		SprHtblIptrEl *	el
	)

Remove the given element el from the hash table. The memory for the element is assumed to be managed by the caller, i.e. it should have been added to the hash table by a add_iptr1_el_to_hash_tbl() call.

SprHtblIptrEl* spr_htbl_add_iptr2	(	SprHtblIptrTbl *	hash_tbl,
		uintptr_t	key1,
		uintptr_t	key2
	)

Create a new hash element for the given keys. The memory for the new hash element will be allocated and managed by the hash functions.

Returns: A pointer the newly created hash element on success and (NULL) on failure.

SprHtblIptrEl* spr_htbl_cadd_iptr2	(	SprHtblIptrTbl *	hash_tbl,
		uintptr_t	key1,
		uintptr_t	key2,
		int	nf_null
	)

Same as add_iptr2_to_hash_tbl() except that this routine will first test if there is already an element with the given keys. If so, a pointer to the existing element will be returned (nf_null == 0) or a NULL pointer will be returned (nf_null != 0). If the element is not already present, a new one will be created.

SprHtblIptrEl* spr_htbl_cadd_iptr2_el	(	SprHtblIptrTbl *	hash_tbl,
		SprHtblIptrEl *	el
	)

Same as add_iptr2_el_to_hash_tbl() except that this routine will first test if there is already an element with the given keys. If so, a NULL pointer will be returned. If the element is not already present, the given element will be added to the hash table.

const SprHtblIptrEl* spr_htbl_find_iptr2_el	(	const SprHtblIptrTbl *	hash_tbl,
		uintptr_t	key1,
		uintptr_t	key2
	)

Search the element matching the given key {key1,key2} in the hash table. If found, a pointer to the matching element is returned. If not found, a NULL is returned.

void* spr_htbl_rm_iptr2	(	SprHtblIptrTbl *	hash_tbl,
		uintptr_t	key1,
		uintptr_t	key2
	)

Search the element matching the given key {key1,key2} in the hash table. If found, the element is removed and a non NULL pointer is returned. If not found, a NULL pointer is returned. The memory for the element is assumed to be managed by the hash table, i.e. it should have been added to the hash table by a add_iptr2_to_hash_tbl() call.

Note: If multiple elements match, only the first matching element is removed.

SprHtblIptrEl* spr_htbl_rm_iptr2_el	(	SprHtblIptrTbl *	hash_tbl,
		uintptr_t	key1,
		uintptr_t	key2
	)

Search the element matching the given key {key1,key2} in the hash table. If found, the element is removed from the hash table and a pointer the matching element is returned. If not found, a NULL pointer is returned. The memory for the element is assumed to be managed by the caller, i.e. it should have been added to the hash table by a add_iptr2_el_to_hash_tbl() call.

Note: If multiple elements match, only the first matching element is removed and returned.

void spr_htbl_unlink_iptr2	(	SprHtblIptrTbl *	hash_tbl,
		SprHtblIptrEl *	el
	)

Remove the given element el from the hash table. The memory for the element is assumed to be managed by the hash table, i.e. it should have been added to the hash table by a add_iptr1_to_hash_tbl() call.

void spr_htbl_unlink_iptr2_el	(	SprHtblIptrTbl *	hash_tbl,
		SprHtblIptrEl *	el
	)

Remove the given element el from the hash table. The memory for the element is assumed to be managed by the caller, i.e. it should have been added to the hash table by a add_iptr1_el_to_hash_tbl() call.

SprHtblIptrEl* spr_htbl_add_iptrN	(	SprHtblIptrTbl *	hash_tbl,
		uintptr_t	key,
			...
	)

Create a new hash element for the given keys. The memory for the new hash element will be allocated and managed by the hash functions.

Returns: A pointer the newly created hash element on success and (NULL) on failure.

const SprHtblIptrEl* spr_htbl_cadd_iptrN	(	SprHtblIptrTbl *	hash_tbl,
		int	nf_null,
		uintptr_t	key,
			...
	)

Same as add_iptrN_to_hash_tbl() except that this routine will first test if there is already an element with the given keys. If so, a pointer to the existing element will be returned (nf_null == 0) or a NULL pointer will be returned (nf_null != 0). If the element is not already present, a new one will be created.

const SprHtblIptrEl* spr_htbl_cadd_iptrN_el	(	SprHtblIptrTbl *	hash_tbl,
		SprHtblIptrEl *	el
	)

Same as add_iptrN_el_to_hash_tbl() except that this routine will first test if there is already an element with the given keys. If so, a NULL pointer will be returned. If the element is not already present, the given element will be added to the hash table.

const SprHtblIptrEl* spr_htbl_find_iptrN_el	(	const SprHtblIptrTbl *	hash_tbl,
		uintptr_t	key,
			...
	)

Search the element matching the given keys {key,...} in the hash table. If found, a pointer to the matching element is returned. If not found, a NULL is returned.

void* spr_htbl_rm_iptrN	(	SprHtblIptrTbl *	hash_tbl,
		uintptr_t	key,
			...
	)

Search the element matching the given keys {key,...} in the hash table. If found, the element is removed and a non NULL pointer is returned. If not found, a NULL pointer is returned. The memory for the element is assumed to be managed by the hash table, i.e. it should have been added to the hash table by a add_iptrN_to_hash_tbl() call.

Note: If multiple elements match, only the first matching element is removed.

SprHtblIptrEl* spr_htbl_rm_iptrN_el	(	SprHtblIptrTbl *	hash_tbl,
		uintptr_t	key,
			...
	)

Search the element matching the given keys {key,...} in the hash table. If found, the element is removed from the hash table and a pointer the matching element is returned. If not found, a NULL pointer is returned. The memory for the element is assumed to be managed by the caller, i.e. it should have been added to the hash table by a add_iptrN_el_to_hash_tbl() call.

Note: If multiple elements match, only the first matching element is removed and returned.

void spr_htbl_unlink_iptrN	(	SprHtblIptrTbl *	hash_tbl,
		SprHtblIptrEl *	el
	)

Remove the given element el from the hash table. The memory for the element is assumed to be managed by the hash table, i.e. it should have been added to the hash table by a add_iptr1_to_hash_tbl() call.

void spr_htbl_unlink_iptrN_el	(	SprHtblIptrTbl *	hash_tbl,
		SprHtblIptrEl *	el
	)

Remove the given element el from the hash table. The memory for the element is assumed to be managed by the caller, i.e. it should have been added to the hash table by a add_iptr1_el_to_hash_tbl() call.

SprStrHashTbl* spr_str_hash_tbl_free	(	SprStrHashTbl *	hash_tbl,
		const int	content_flags,
		SprMsgId *	routine
	)

Free the string hash table. When the first bit in the content_flags is set, the main structure hash_tbl will NOT be deallocated. This allows for a hash table as local variable on the stack. If the second bit is set, the content (the strings added to the hash table) will NOT be deallocated.

SprStrHashTbl* spr_str_hash_tbl_alloc	(	SprStrHashTbl *	hash_tbl_in,
		unsigned int	size,
		unsigned int	prefix_len,
		unsigned int()(const char )	hash_func,
		int()(const char , const char *)	cmp_func
	)

Allocate a string hash table of a given (maximum) length size. Note that the table can be resized later on (but this is rather slow). The hash key is located at offset prefix_len, this allows for elements in the hash-elements that is not used to calculate the hashing index. Both the hash_func and the cmp_func may be NULL, resulting in a case sensitive hasing and comparison of strings.

int spr_str_hash_tbl_add_str	(	SprStrHashTbl *const	hash_tbl,
		const char *const	str
	)

Add a given string/structure to the hash table. Note that the string/structure must be allocated using malloc_() and that the pointer must be shifted by 'prefix_len' bytes as specified in alloc_str_hash_tbl(). From now on the string/structure belongs to the hash table. Returns the index of the hash element on success or (-1) on failure.

int spr_str_hash_tbl_find_str	(	const SprStrHashTbl *	hash_tbl,
		const char *	str
	)

Find a given string in the hash table. As result the index of the string in the hash table is returned (or -1 if the string is not found). The index in the hash table is equal to the rank order in which the strings were added to the hash table.
The requested string can be found as follows:

hash_tbl->list[ndx].str

This also works for index (-1), and will result in the NULL string.

SprStrHashEl* spr_str_hash_tbl_find_el	(	const SprStrHashTbl *	hash_tbl,
		const SprStrHashEl *	el
	)

Test if a given element is part of the hash table (not removed). Returns NULL if the element is NOT present (== removed).

char* spr_str_hash_tbl_find_str_el	(	const SprStrHashTbl *	hash_tbl,
		const char *	str
	)

Same as find_str_in_hash_tbl(), except that a pointer to the matching element (string/hash-field) is returned.

int spr_str_hash_tbl_rm_el	(	SprStrHashTbl *	hash_tbl,
		const char *	str,
		int	free_flag
	)

Find a given string in the hash table and, if found, remove the element. If a certain key was added multiple times, only the last one is removed. If the free_flag is set, the content of the hash element will deallocated (cf. free_str_hash_tbl).

Returns: 1 when the element was found and removed, 0 otherwise.

const char* spr_str_hash_tbl_iterate	(	const SprStrHashTbl *	hash_tbl,
		int *	iterator
	)

Iterate over all keys of the hash table.
Return (NULL) of no more elements are available.
Warning: The iterator is not safe against the compact_str_hash_tbl() routine.

SprStrHashTbl* spr_str_hash_tbl_read	(	SprStrHashTbl *	hash_tbl,
		const char *	fname,
		const char *	up_till
	)

Read a list words from the specified file fname and store the words in the given EMPTY hash_tbl hash_tbl (or allocate a hash table if hash_tbl equals NULL). The file fname must contain a standard key-header. The field 'NENTRY' specifies the number of words. Each word consist of a single line (leading + trailing space is removed). If the up_till string is specified, the words are only copied up till the first first occurence of one of the characters in the up_till string (see strcspn()).

void spr_str_hash_tbl_sort	(	SprStrHashTbl *	hash_tbl,
		int	check_rm
	)

Sort the content (strings) of the hash table. If any of the elements may have been removed, the check_rm must be non zero!

Variable Documentation

const SprHtblIptrTbl spr_htbl_empty_iptr_tbl

const SprStrHashTbl spr_str_hash_tbl_empty

Data Structures

Typedefs

Functions

Variables

Detailed Description

Typedef Documentation

Function Documentation

Variable Documentation