Hash Table

Macros
#define	PJ_HASH_KEY_STRING   ((unsigned)-1)
#define	PJ_HASH_ENTRY_BUF_SIZE   (3*sizeof(void*) + 2*sizeof(pj_uint32_t))

Typedefs
typedef void *	pj_hash_entry_buf[((3 *sizeof(void *)+2 *sizeof(pj_uint32_t))+sizeof(void *) -1)/(sizeof(void *))]

Functions
pj_uint32_t	pj_hash_calc (pj_uint32_t hval, const void *key, unsigned keylen)
pj_uint32_t	pj_hash_calc_tolower (pj_uint32_t hval, char *result, const pj_str_t *key)
pj_hash_table_t *	pj_hash_create (pj_pool_t *pool, unsigned size)
void *	pj_hash_get (pj_hash_table_t *ht, const void *key, unsigned keylen, pj_uint32_t *hval)
void *	pj_hash_get_lower (pj_hash_table_t *ht, const void *key, unsigned keylen, pj_uint32_t *hval)
void	pj_hash_set (pj_pool_t *pool, pj_hash_table_t *ht, const void *key, unsigned keylen, pj_uint32_t hval, void *value)
void	pj_hash_set_lower (pj_pool_t *pool, pj_hash_table_t *ht, const void *key, unsigned keylen, pj_uint32_t hval, void *value)
void	pj_hash_set_np (pj_hash_table_t *ht, const void *key, unsigned keylen, pj_uint32_t hval, pj_hash_entry_buf entry_buf, void *value)
void	pj_hash_set_np_lower (pj_hash_table_t *ht, const void *key, unsigned keylen, pj_uint32_t hval, pj_hash_entry_buf entry_buf, void *value)
unsigned	pj_hash_count (pj_hash_table_t *ht)
pj_hash_iterator_t *	pj_hash_first (pj_hash_table_t *ht, pj_hash_iterator_t *it)
pj_hash_iterator_t *	pj_hash_next (pj_hash_table_t *ht, pj_hash_iterator_t *it)
void *	pj_hash_this (pj_hash_table_t *ht, pj_hash_iterator_t *it)

Detailed Description

A hash table is a dictionary in which keys are mapped to array positions by hash functions. Having the keys of more than one item map to the same position is called a collision. In this library, we will chain the nodes that have the same key in a list.

Macro Definition Documentation

PJ_HASH_ENTRY_BUF_SIZE

#define PJ_HASH_ENTRY_BUF_SIZE   (3*sizeof(void*) + 2*sizeof(pj_uint32_t))

This indicates the size of of each hash entry.

PJ_HASH_KEY_STRING

#define PJ_HASH_KEY_STRING   ((unsigned)-1)

If this constant is used as keylen, then the key is interpreted as NULL terminated string.

Typedef Documentation

pj_hash_entry_buf

typedef void* pj_hash_entry_buf[((3 *sizeof(void *)+2 *sizeof(pj_uint32_t))+sizeof(void *) -1)/(sizeof(void *))]

Type declaration for entry buffer, used by pj_hash_set_np()

Function Documentation

pj_hash_calc()

pj_uint32_t pj_hash_calc	(	pj_uint32_t	hval,
		const void *	key,
		unsigned	keylen
	)

This is the function that is used by the hash table to calculate hash value of the specified key.

Parameters

hval	the initial hash value, or zero.
key	the key to calculate.
keylen	the length of the key, or PJ_HASH_KEY_STRING to treat the key as null terminated string.

Returns

the hash value.

pj_hash_calc_tolower()

pj_uint32_t pj_hash_calc_tolower	(	pj_uint32_t	hval,
		char *	result,
		const pj_str_t *	key
	)

Convert the key to lowercase and calculate the hash value. The resulting string is stored in result.

Parameters

hval	The initial hash value, normally zero.
result	Optional. Buffer to store the result, which must be enough to hold the string.
key	The input key to be converted and calculated.

Returns

The hash value.

pj_hash_count()

unsigned pj_hash_count

(

pj_hash_table_t *

ht

)

Get the total number of entries in the hash table.

Parameters

ht	the hash table.

Returns

the number of entries in the hash table.

pj_hash_create()

pj_hash_table_t * pj_hash_create	(	pj_pool_t *	pool,
		unsigned	size
	)

Create a hash table with the specified 'bucket' size.

Parameters

pool	the pool from which the hash table will be allocated from.
size	the bucket size, which will be round-up to the nearest 2^n-1

Returns

the hash table.

pj_hash_first()

pj_hash_iterator_t * pj_hash_first	(	pj_hash_table_t *	ht,
		pj_hash_iterator_t *	it
	)

Get the iterator to the first element in the hash table.

Parameters

ht	the hash table.
it	the iterator for iterating hash elements.

Returns

the iterator to the hash element, or NULL if no element presents.

pj_hash_get()

void * pj_hash_get	(	pj_hash_table_t *	ht,
		const void *	key,
		unsigned	keylen,
		pj_uint32_t *	hval
	)

Get the value associated with the specified key.

Parameters

ht	the hash table.
key	the key to look for.
keylen	the length of the key, or PJ_HASH_KEY_STRING to use the string length of the key.
hval	if this argument is not NULL and the value is not zero, the value will be used as the computed hash value. If the argument is not NULL and the value is zero, it will be filled with the computed hash upon return.

Returns

the value associated with the key, or NULL if the key is not found.

pj_hash_get_lower()

void * pj_hash_get_lower	(	pj_hash_table_t *	ht,
		const void *	key,
		unsigned	keylen,
		pj_uint32_t *	hval
	)

Variant of pj_hash_get() with the key being converted to lowercase when calculating the hash value.

See also

pj_hash_get()

pj_hash_next()

pj_hash_iterator_t * pj_hash_next	(	pj_hash_table_t *	ht,
		pj_hash_iterator_t *	it
	)

Get the next element from the iterator.

Parameters

ht	the hash table.
it	the hash iterator.

Returns

the next iterator, or NULL if there's no more element.

pj_hash_set()

void pj_hash_set	(	pj_pool_t *	pool,
		pj_hash_table_t *	ht,
		const void *	key,
		unsigned	keylen,
		pj_uint32_t	hval,
		void *	value
	)

Associate/disassociate a value with the specified key. If value is not NULL and entry already exists, the entry's value will be overwritten. If value is not NULL and entry does not exist, a new one will be created with the specified pool. Otherwise if value is NULL, entry will be deleted if it exists.

Parameters

pool	the pool to allocate the new entry if a new entry has to be created.
ht	the hash table.
key	the key. If pool is not specified, the key MUST point to buffer that remains valid for the duration of the entry.
keylen	the length of the key, or PJ_HASH_KEY_STRING to use the string length of the key.
hval	if the value is not zero, then the hash table will use this value to search the entry's index, otherwise it will compute the key. This value can be obtained when calling pj_hash_get().
value	value to be associated, or NULL to delete the entry with the specified key.

pj_hash_set_lower()

void pj_hash_set_lower	(	pj_pool_t *	pool,
		pj_hash_table_t *	ht,
		const void *	key,
		unsigned	keylen,
		pj_uint32_t	hval,
		void *	value
	)

Variant of pj_hash_set() with the key being converted to lowercase when calculating the hash value.

See also

pj_hash_set()

pj_hash_set_np()

void pj_hash_set_np	(	pj_hash_table_t *	ht,
		const void *	key,
		unsigned	keylen,
		pj_uint32_t	hval,
		pj_hash_entry_buf	entry_buf,
		void *	value
	)

Associate/disassociate a value with the specified key. This function works like pj_hash_set(), except that it doesn't use pool (hence the np – no pool suffix). If new entry needs to be allocated, it will use the entry_buf.

Parameters

ht	the hash table.
key	the key.
keylen	the length of the key, or PJ_HASH_KEY_STRING to use the string length of the key.
hval	if the value is not zero, then the hash table will use this value to search the entry's index, otherwise it will compute the key. This value can be obtained when calling pj_hash_get().
entry_buf	Buffer which will be used for the new entry, when one needs to be created.
value	value to be associated, or NULL to delete the entry with the specified key.

pj_hash_set_np_lower()

void pj_hash_set_np_lower	(	pj_hash_table_t *	ht,
		const void *	key,
		unsigned	keylen,
		pj_uint32_t	hval,
		pj_hash_entry_buf	entry_buf,
		void *	value
	)

Variant of pj_hash_set_np() with the key being converted to lowercase when calculating the hash value.

See also

pj_hash_set_np()

pj_hash_this()

void * pj_hash_this	(	pj_hash_table_t *	ht,
		pj_hash_iterator_t *	it
	)

Get the value associated with a hash iterator.

Parameters

ht	the hash table.
it	the hash iterator.

Returns

the value associated with the current element in iterator.