qLibc

Macros | Functions
qhashtbl.c File Reference

Hash-table container implementation. More...

Go to the source code of this file.

## 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 a integer into this table as string type.
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 as string type.
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 hash table for debugging purpose
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(): De-allocate hash table

## Detailed Description

Hash-table container implementation.

qhashtbl implements a hash table, which maps keys to values. Key is a unique string and value is any non-null object. The creator qhashtbl() has a parameter that affect its performance: 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 slots stores multiple elements using 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 memalloced
free(sample1);
// release table
tbl->free(tbl);
qhashtbl
qhashtbl_t * qhashtbl(size_t range, int options)
Initialize hash table.
Definition qhashtbl.c:127

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
  a pointer of malloced qhashtbl_t, otherwise returns NULL.

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 if successful, otherwise returns 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 if successful, otherwise returns 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 if successful, otherwise returns 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 a integer into this table as string type.

Parameters

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

Returns
  true if successful, otherwise returns 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, oject size will be stored.
  newmem | whether or not to allocate memory for the data.

Returns
  a pointer of data if the key is found, otherwise returns NULL.

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 malloced and should be deallocated by user. Otherwise returned pointer will point internal buffer directly and should not be de-allocated 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 as string type.

Parameters

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

Returns
  a pointer of data if the key is found, otherwise returns NULL.

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 malloced 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
  value integer if successful, otherwise(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 if successful, otherwise(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 returns 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 on user code when all element scan must be guaranteed where multiple threads concurrently update the table. It's ok not to lock the table on the user code even in thread condition, when concurreny is importand and all element scan in a path doesn't need to be guaranteed. In this case, new data inserted during the traversal will be show up in this scan or next scan. Make sure 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 hash table for debugging purpose

Parameters

  tbl | qhashtbl_t container pointer.
  out | output stream

Returns
  true if successful, otherwise returns 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(): De-allocate hash table

Parameters

  tbl | qhashtbl_t container pointer.

Definition at line 708 of file qhashtbl.c.