Hash-table container implementation. More...

Macros
#define	DEFAULT_INDEX_RANGE (1000)

Functions
qhashtbl_t *	qhashtbl (size_t range, int options)
	Initialize hash table.
bool	qhashtbl_put (qhashtbl_t tbl, const char name, const void *data, size_t size)
	qhashtbl->put(): Put an object into this table.
bool	qhashtbl_putstr (qhashtbl_t tbl, const char name, const char *str)
	qhashtbl->putstr(): Put a string into this table.
bool	qhashtbl_putstrf (qhashtbl_t tbl, const char name, const char *format,...)
	qhashtbl->putstrf(): Put a formatted string into this table.
bool	qhashtbl_putint (qhashtbl_t tbl, const char name, const int64_t num)
	qhashtbl->putint(): Put an integer into this table as a string.
void *	qhashtbl_get (qhashtbl_t tbl, const char name, size_t *size, bool newmem)
	qhashtbl->get(): Get an object from this table.
char *	qhashtbl_getstr (qhashtbl_t tbl, const char name, const bool newmem)
	qhashtbl->getstr(): Finds an object and returns it as a string.
int64_t	qhashtbl_getint (qhashtbl_t tbl, const char name)
	qhashtbl->getint(): Finds an object with given name and returns as integer type.
bool	qhashtbl_remove (qhashtbl_t tbl, const char name)
	qhashtbl->remove(): Remove an object from this table.
bool	qhashtbl_getnext (qhashtbl_t tbl, qhashtbl_obj_t obj, const bool newmem)
	qhashtbl->getnext(): Get next element.
size_t	qhashtbl_size (qhashtbl_t *tbl)
	qhashtbl->size(): Returns the number of keys in this hashtable.
void	qhashtbl_clear (qhashtbl_t *tbl)
	qhashtbl->clear(): Clears this hashtable so that it contains no keys.
bool	qhashtbl_debug (qhashtbl_t tbl, FILE out)
	qhashtbl->debug(): Print the hash table for debugging purposes.
void	qhashtbl_lock (qhashtbl_t *tbl)
	qhashtbl->lock(): Enter critical section.
void	qhashtbl_unlock (qhashtbl_t *tbl)
	qhashtbl->unlock(): Leave critical section.
void	qhashtbl_free (qhashtbl_t *tbl)
	qhashtbl->free(): Free hash table

Detailed Description

Hash-table container implementation.

qhashtbl implements a hash table, which maps keys to values. Keys are unique strings and values are any non-null objects. The creator qhashtbl() has a parameter that affects its performance: the initial hash range. The hash range is the number of slots (pointers) in the hash table. In the case of a hash collision, a single slot stores multiple elements using a linked-list structure, which must be searched sequentially. So lower range than the number of elements decreases the space overhead but increases the number of hash collisions and consequently it increases the time cost to look up an element.

[Internal Structure Example for 10-slot hash table]
 
RANGE    NAMED-OBJECT-LIST
=====    =================
[ 0 ] -> [hash=320,key3=value] -> [hash=210,key5=value] -> [hash=110,...]
[ 1 ] -> [hash=1,key1=value]
[ 2 ]
[ 3 ] -> [hash=873,key4=value]
[ 4 ] -> [hash=2674,key11=value] -> [hash=214,key5=value]
[ 5 ] -> [hash=8545,key10=value]
[ 6 ] -> [hash=9226,key9=value]
[ 7 ]
[ 8 ] -> [hash=8,key6=value] -> [hash=88,key8=value]
[ 9 ] -> [hash=12439,key7=value]

// create a hash-table with 10 hash-index range.
// Please be aware, the hash-index range 10 does not mean the number of
// objects which can be stored. You can put as many as you want but if
// this range is too small, hash conflict will happen and fetch time will
// slightly increase.
qhashtbl_t *tbl = qhashtbl(0, QHASHTBL_THREADSAFE);
 
// put objects into table.
tbl->put(tbl, "sample1", "binary", 6);
tbl->putstr(tbl, "sample2", "string");
tbl->putint(tbl, "sample3", 1);
 
// debug print out
tbl->debug(tbl, stdout, true);
 
// get objects
void *sample1 = tbl->get(tbl, "sample1", &size, true);
char *sample2 = tbl->getstr(tbl, "sample2", false);
int  sample3  = tbl->getint(tbl, "sample3");
 
// sample1 is meallocated
free(sample1);
 
// release table
tbl->free(tbl);

Definition in file qhashtbl.c.

Macro Definition Documentation

◆ DEFAULT_INDEX_RANGE

#define DEFAULT_INDEX_RANGE (1000)

default value of hash-index range

Definition at line 101 of file qhashtbl.c.

Function Documentation

◆ qhashtbl()

qhashtbl_t * qhashtbl	(	size_t	range,
		int	options )

Initialize hash table.

Parameters

range	initial size of index range. Value of 0 will use default value, DEFAULT_INDEX_RANGE;
options	combination of initialization options.

Returns: pointer to allocated qhashtbl_t on success, or NULL on failure.

Return values

errno

will be set in error condition.

ENOMEM : Memory allocation failure.

// create a hash-table.
qhashtbl_t *basic_hashtbl = qhashtbl(0, 0);
 
// create a large hash-table for millions of keys with thread-safe option.
qhashtbl_t *small_hashtbl = qhashtbl(1000000, QHASHTBL_THREADSAFE);

Note

Setting the right range is a magic. In practice, pick a value between (total keys / 3) ~ (total keys * 2). Available options:

QHASHTBL_THREADSAFE - make it thread-safe.

Definition at line 127 of file qhashtbl.c.

◆ qhashtbl_put()

bool qhashtbl_put	(	qhashtbl_t *	tbl,
		const char *	name,
		const void *	data,
		size_t	size )

qhashtbl->put(): Put an object into this table.

Parameters

tbl	qhashtbl_t container pointer.
name	key name
data	data object
size	size of data object

Returns: true on success, otherwise false

Return values

errno

will be set in error condition.

EINVAL : Invalid argument.
ENOMEM : Memory allocation failure.

Definition at line 198 of file qhashtbl.c.

◆ qhashtbl_putstr()

bool qhashtbl_putstr	(	qhashtbl_t *	tbl,
		const char *	name,
		const char *	str )

qhashtbl->putstr(): Put a string into this table.

Parameters

tbl	qhashtbl_t container pointer.
name	key name.
str	string data.

Returns: true on success, otherwise false.

Return values

errno

will be set in error condition.

EINVAL : Invalid argument.
ENOMEM : Memory allocation failure.

Definition at line 279 of file qhashtbl.c.

◆ qhashtbl_putstrf()

bool qhashtbl_putstrf	(	qhashtbl_t *	tbl,
		const char *	name,
		const char *	format,
			... )

qhashtbl->putstrf(): Put a formatted string into this table.

Parameters

tbl	qhashtbl_t container pointer.
name	key name.
format	formatted string data.

Returns: true on success, otherwise false.

Return values

errno

will be set in error condition.

EINVAL : Invalid argument.
ENOMEM : Memory allocation failure.

Definition at line 295 of file qhashtbl.c.

◆ qhashtbl_putint()

bool qhashtbl_putint	(	qhashtbl_t *	tbl,
		const char *	name,
		const int64_t	num )

qhashtbl->putint(): Put an integer into this table as a string.

Parameters

tbl	qhashtbl_t container pointer.
name	key name.
num	integer data.

Returns: true on success, otherwise false.

Return values

errno

will be set in error condition.

EINVAL : Invalid argument.
ENOMEM : Memory allocation failure.

Note: The integer will be converted to a string object and stored as string object.

Definition at line 323 of file qhashtbl.c.

◆ qhashtbl_get()

void * qhashtbl_get	(	qhashtbl_t *	tbl,
		const char *	name,
		size_t *	size,
		bool	newmem )

qhashtbl->get(): Get an object from this table.

Parameters

tbl	qhashtbl_t container pointer.
name	key name.
size	if not NULL, object size will be stored.
newmem	whether or not to allocate memory for the data.

Returns: pointer to data if the key is found on success, or NULL on failure.

Return values

errno

will be set in error condition.

ENOENT : No such key found.
EINVAL : Invalid argument.
ENOMEM : Memory allocation failure.

qhashtbl_t *tbl = qhashtbl(0, 0);
(...codes...)
 
// with newmem flag unset
size_t size;
void *data = (struct myobj*)tbl->get(tbl, "key_name", &size, false);
 
// with newmem flag set
size_t size;
void *data  = (struct myobj*)tbl->get(tbl, "key_name", &size, true);
free(data);

Note: If newmem flag is set, returned data will be allocated and should be deallocated by user. Otherwise returned pointer will point internal buffer directly and should not be freed by user. In thread-safe mode, newmem flag must be set to true always.

Definition at line 363 of file qhashtbl.c.

◆ qhashtbl_getstr()

char * qhashtbl_getstr	(	qhashtbl_t *	tbl,
		const char *	name,
		const bool	newmem )

qhashtbl->getstr(): Finds an object and returns it as a string.

Parameters

tbl	qhashtbl_t container pointer.
name	key name
newmem	whether or not to allocate memory for the data.

Returns: pointer to data if the key is found on success, or NULL on failure.

Return values

errno

will be set in error condition.

ENOENT : No such key found.
EINVAL : Invalid argument.
ENOMEM : Memory allocation failure.

Note: If newmem flag is set, returned data will be allocated and should be deallocated by user.

Definition at line 422 of file qhashtbl.c.

◆ qhashtbl_getint()

int64_t qhashtbl_getint	(	qhashtbl_t *	tbl,
		const char *	name )

qhashtbl->getint(): Finds an object with given name and returns as integer type.

Parameters

tbl	qhashtbl_t container pointer.
name	key name

Returns: the integer value on success; otherwise (if not found), returns 0.

Return values

errno

will be set in error condition.

ENOENT : No such key found.
EINVAL : Invalid argument.
ENOMEM : Memory allocation failure.

Definition at line 439 of file qhashtbl.c.

◆ qhashtbl_remove()

bool qhashtbl_remove	(	qhashtbl_t *	tbl,
		const char *	name )

qhashtbl->remove(): Remove an object from this table.

Parameters

tbl	qhashtbl_t container pointer.
name	key name

Returns: true on success; otherwise (if not found), returns false.

Return values

errno

will be set in error condition.

ENOENT : No such key found.
EINVAL : Invalid argument.

Definition at line 461 of file qhashtbl.c.

◆ qhashtbl_getnext()

bool qhashtbl_getnext	(	qhashtbl_t *	tbl,
		qhashtbl_obj_t *	obj,
		const bool	newmem )

qhashtbl->getnext(): Get next element.

Parameters

tbl	qhashtbl_t container pointer.
obj	found data will be stored in this object
newmem	whether or not to allocate memory for the data.

Returns: true if found otherwise false

Return values

errno

will be set in error condition.

ENOENT : No next element.
EINVAL : Invalid argument.
ENOMEM : Memory allocation failure.

qhashtbl_t *tbl = qhashtbl(0, 0);
(...add data into list...)
 
qhashtbl_obj_t obj;
memset((void*)&obj, 0, sizeof(obj)); // must be cleared before call
tbl->lock(tbl);  // lock it when thread condition is expected
while(tbl->getnext(tbl, &obj, false) == true) {  // newmem is false
   printf("NAME=%s, DATA=%s, SIZE=%zu\n",
   obj.name, (char*)obj.data, obj.size);
   // do free obj.name and obj.data if newmem was set to true;
}
tbl->unlock(tbl);

Note: locking must be provided in user code when a full element scan must be guaranteed while multiple threads concurrently update the table. It's OK not to lock the table in user code even in multi-threaded conditions when concurrency is important and a full element scan in a pass does not need to be guaranteed. In this case, new data inserted during the traversal will show up in this scan or the next scan. Make sure the newmem flag is set if deletion is expected during the scan. Object obj should be initialized with 0 by using memset() before first call.

Definition at line 543 of file qhashtbl.c.

◆ qhashtbl_size()

size_t qhashtbl_size ( qhashtbl_t * tbl )

qhashtbl->size(): Returns the number of keys in this hashtable.

Parameters

tbl	qhashtbl_t container pointer.

Returns: number of elements stored

Definition at line 613 of file qhashtbl.c.

◆ qhashtbl_clear()

void qhashtbl_clear ( qhashtbl_t * tbl )

qhashtbl->clear(): Clears this hashtable so that it contains no keys.

Parameters

tbl	qhashtbl_t container pointer.

Definition at line 622 of file qhashtbl.c.

◆ qhashtbl_debug()

bool qhashtbl_debug	(	qhashtbl_t *	tbl,
		FILE *	out )

qhashtbl->debug(): Print the hash table for debugging purposes.

Parameters

tbl	qhashtbl_t container pointer.
out	output stream such as stdout or stderr.

Returns: true on success, otherwise false.

Return values

errno

will be set in error condition.

EIO : Invalid output stream.

Definition at line 654 of file qhashtbl.c.

◆ qhashtbl_lock()

void qhashtbl_lock ( qhashtbl_t * tbl )

qhashtbl->lock(): Enter critical section.

Parameters

tbl	qhashtbl_t container pointer.

Note: From user side, normally locking operation is only needed when traverse all elements using qhashtbl->getnext().; This operation will do nothing if QHASHTBL_THREADSAFE option was not given at the initialization time.

Definition at line 686 of file qhashtbl.c.

◆ qhashtbl_unlock()

void qhashtbl_unlock ( qhashtbl_t * tbl )

qhashtbl->unlock(): Leave critical section.

Parameters

tbl	qhashtbl_t container pointer.

Note: This operation will do nothing if QHASHTBL_THREADSAFE option was not given at the initialization time.

Definition at line 699 of file qhashtbl.c.

◆ qhashtbl_free()

void qhashtbl_free ( qhashtbl_t * tbl )

qhashtbl->free(): Free hash table

Parameters

tbl	qhashtbl_t container pointer.

Definition at line 708 of file qhashtbl.c.

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ DEFAULT_INDEX_RANGE

Function Documentation

◆ qhashtbl()

◆ qhashtbl_put()

◆ qhashtbl_putstr()

◆ qhashtbl_putstrf()

◆ qhashtbl_putint()

◆ qhashtbl_get()

◆ qhashtbl_getstr()

◆ qhashtbl_getint()

◆ qhashtbl_remove()

◆ qhashtbl_getnext()

◆ qhashtbl_size()

◆ qhashtbl_clear()

◆ qhashtbl_debug()

◆ qhashtbl_lock()

◆ qhashtbl_unlock()

◆ qhashtbl_free()