qLibc

Macros | Functions
qhasharr.c File Reference

Static(array) hash-table implementation. More...

Go to the source code of this file.

## Macros
#define | COLLISION_MARK (-1)
#define | EXTBLOCK_MARK (-2)

## Functions
size_t | qhasharr_calculate_memsize (int max)
| Get how much memory is needed for N slots.
qhasharr_t * | qhasharr (void *memory, size_t memsize)
| Initialize static hash table.
bool | qhasharr_put (qhasharr_t *tbl, const char *name, const void *data, size_t datasize)
| qhasharr->put(): Put an object into this table.
bool | qhasharr_putstr (qhasharr_t *tbl, const char *name, const char *data)
| qhasharr->putstr(): Put a string into this table
bool | qhasharr_putstrf (qhasharr_t *tbl, const char *name, const char *format,...)
| qhasharr->putstrf(): Put a formatted string into this table.
bool | qhasharr_put_by_obj (qhasharr_t *tbl, const void *name, size_t namesize, const void *data, size_t datasize)
| qhasharr->put_by_obj(): ut an object into this table by key object.
void * | qhasharr_get (qhasharr_t *tbl, const char *name, size_t *datasize)
| qhasharr->get(): Get an object from this table
char * | qhasharr_getstr (qhasharr_t *tbl, const char *name)
| qhasharr->getstr(): Finds an object with given name and returns as string type.
void * | qhasharr_get_by_obj (qhasharr_t *tbl, const void *name, size_t namesize, size_t *datasize)
| qhasharr->get_by_object(): Get an object from this table by key object
bool | qhasharr_remove (qhasharr_t *tbl, const char *name)
| qhasharr->remove(): Remove an object from this table.
bool | qhasharr_remove_by_obj (qhasharr_t *tbl, const char *name, size_t namesize)
| qhasharr->remove_by_obj(): Remove an object from this table by key object
bool | qhasharr_remove_by_idx (qhasharr_t *tbl, int idx)
| qhasharr->remove_by_idx(): Remove an object from this table by index number.
bool | qhasharr_getnext (qhasharr_t *tbl, qhasharr_obj_t *obj, int *idx)
| qhasharr->getnext(): Get next element.
int | qhasharr_size (qhasharr_t *tbl, int *maxslots, int *usedslots)
| qhasharr->size(): Returns the number of objects in this table.
void | qhasharr_clear (qhasharr_t *tbl)
| qhasharr->clear(): Clears this table so that it contains no keys.
bool | qhasharr_debug (qhasharr_t *tbl, FILE *out)
| qhasharr->debug(): Print hash table for debugging purpose
void | qhasharr_free (qhasharr_t *tbl)
| qhasharr->free(): De-allocate table reference object.

## Detailed Description

Static(array) hash-table implementation.

qhasharr implements a hash-table which maps keys to values and stores into fixed size static memory like shared-memory and memory-mapped file. The creator qhasharr() initializes static memory to makes small slots in it. The default slot size factors are defined in Q_HASHARR_NAMESIZE and Q_HASHARR_DATASIZE. And they are applied at compile time.

The value part of an element will be stored across several slots if it's size exceeds the slot size. But the key part of an element will be truncated if the size exceeds and it's length and more complex MD5 hash value will be stored with the key. So to look up a particular key, first we find an element which has same hash value. If the key was not truncated, we just do key comparison. But if the key was truncated because it's length exceeds, we do both md5 and key comparison(only stored size) to verify that the key is same. So please be aware of that, theoretically there is a possibility we pick wrong element in case a key exceeds the limit, has same length and MD5 hash with lookup key. But this possibility is very low and almost zero in practice.

qhasharr hash-table does not provide thread-safe handling intentionally and let users determine whether to provide locking mechanism or not, depending on the use cases. When there's race conditions expected, you should provide a shared resource control using mutex or semaphore to make sure data gets updated by one instance at a time.

[Data Structure Diagram]
+--[Static Flat Memory Area]-----------------------------------------------+
| +-[Header]---------+ +-[Slot 0]---+ +-[Slot 1]---+ +-[Slot N]---+ |
| |Private table data| |KEY A|DATA A| |KEY B|DATA B| .... |KEY N|DATA N| |
| +------------------+ +------------+ +------------+ +------------+ |
+--------------------------------------------------------------------------+
Below diagram shows how a big value is stored.
+--[Static Flat Memory Area------------------------------------------------+
| +--------+ +-[Slot 0]---+ +-[Slot 1]---+ +-[Slot 2]---+ +-[Slot 3]-----+ |
| |TBL INFO| |KEY A|DATA A| |DATA A cont.| |KEY B|DATA B| |DATA A cont. | |
| +--------+ +------------+ +------------+ +------------+ +--------------+ |
| ^~~link~~^ ^~~~~~~~~~link~~~~~~~~~^ |
+--------------------------------------------------------------------------+
// initialize hash-table.
char memory[1000 * 10];
qhasharr_t *tbl = qhasharr(memory, sizeof(memory));
if(tbl == NULL) return;
// insert elements (key duplication does not allowed)
tbl->putstr(tbl, "e1", "a");
tbl->putstr(tbl, "e2", "b");
tbl->putstr(tbl, "e3", "c");
// debug print out
tbl->debug(tbl, stdout);
char *e2 = tbl->getstr(tbl, "e2");
if(e2 != NULL) {
printf("getstr('e2') : %s\n", e2);
free(e2);
}
// Release reference object.
tbl->free(tbl);
qhasharr
qhasharr_t * qhasharr(void *memory, size_t memsize)
Initialize static hash table.
Definition qhasharr.c:208

An example for using hash table over shared memory.

[CREATOR SIDE]
int maxslots = 1000;
int memsize = qhasharr_calculate_memsize(maxslots);
// create shared memory
int shmid = qshm_init("/tmp/some_id_file", 'q', memsize, true);
if(shmid < 0) return -1; // creation failed
void *memory = qshm_get(shmid);
// initialize hash-table
qhasharr_t *tbl = qhasharr(memory, memsize);
if(hasharr == NULL) return -1;
(...your codes with your own locking mechanism...)
// Release reference object
tbl->free(tbl);
// destroy shared memory
qshm_free(shmid);
[USER SIDE]
int shmid = qshm_getid("/tmp/some_id_file", 'q');
// get shared memory
void *memory = qshm_get(shmid);
// map existing memory into table
qhasharr_t *tbl = qhasharr(memory, 0);
(...your codes with your own locking mechanism...)
// Release reference object
tbl->free(tbl);
qhasharr_calculate_memsize
size_t qhasharr_calculate_memsize(int max)
Get how much memory is needed for N slots.
Definition qhasharr.c:179
qshm_get
void * qshm_get(int shmid)
Get a pointer of shared memory.
Definition qshm.c:149
qshm_init
int qshm_init(const char *keyfile, int keyid, size_t size, bool recreate)
Initialize shared-memory.
Definition qshm.c:91
qshm_getid
int qshm_getid(const char *keyfile, int keyid)
Get shared memory identifier by keyfile and keyid for existing shared memory.
Definition qshm.c:127
qshm_free
bool qshm_free(int shmid)
De-allocate shared memory.
Definition qshm.c:167

Definition in file qhasharr.c.

## Macro Definition Documentation

## ◆ COLLISION_MARK

#define COLLISION_MARK (-1)

Definition at line 150 of file qhasharr.c.

## ◆ EXTBLOCK_MARK

#define EXTBLOCK_MARK (-2)

Definition at line 151 of file qhasharr.c.

## Function Documentation

## ◆ qhasharr_calculate_memsize()

size_t qhasharr_calculate_memsize | ( | int | max | ) |

Get how much memory is needed for N slots.

Parameters

  max | a number of maximum internal slots

Returns
  memory size needed

Note
  This can be used for calculating minimum memory size for N slots.

Definition at line 179 of file qhasharr.c.

## ◆ qhasharr()

qhasharr_t * qhasharr | ( | void * | memory,
|  | size_t | memsize
| ) |  |

Initialize static hash table.

Parameters

  memory | a pointer of data memory.
  memsize | a size of data memory, 0 for using existing data.

Returns
  qhasharr_t container pointer, otherwise returns NULL.

Return values

  errno | will be set in error condition. EINVAL : Assigned memory is too small. It must bigger enough to allocate at least 1 slot.

// initialize hash-table with 100 slots.
// A single element can take several slots.
char memory[112 * 100];
// Initialize new table.
qhasharr_t *tbl = qhasharr(memory, sizeof(memory));
// Use existing table.
qhasharr_t *tbl2 = qhasharr(memory, 0);

Definition at line 208 of file qhasharr.c.

## ◆ qhasharr_put()

bool qhasharr_put | ( | qhasharr_t * | tbl,
|  | const char * | name,
|  | const void * | data,
|  | size_t | datasize
| ) |  |

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

Parameters

  tbl | qhasharr_t container pointer.
  key | key string
  value | value object data
  size | size of value

Returns
  true if successful, otherwise returns false

Return values

  errno | will be set in error condition. ENOBUFS : Table doesn't have enough space to store the object. EINVAL : Invalid argument. EFAULT : Unexpected error. Data structure is not constant.

Definition at line 278 of file qhasharr.c.

## ◆ qhasharr_putstr()

bool qhasharr_putstr | ( | qhasharr_t * | tbl,
|  | const char * | name,
|  | const char * | data
| ) |  |

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

Parameters

  tbl | qhasharr_t container pointer.
  name | key string.
  data | value string.

Returns
  true if successful, otherwise returns false

Return values

  errno | will be set in error condition. ENOBUFS : Table doesn't have enough space to store the object. EINVAL : Invalid argument. EFAULT : Unexpected error. Data structure is not constant.

Definition at line 297 of file qhasharr.c.

## ◆ qhasharr_putstrf()

bool qhasharr_putstrf | ( | qhasharr_t * | tbl,
|  | const char * | name,
|  | const char * | format,
|  |  | ...
| ) |  |

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

Parameters

  tbl | qhasharr_t container pointer.
  name | key string
  format | formatted string data.

Returns
  true if successful, otherwise returns false.

Return values

  errno | will be set in error condition. ENOBUFS : Table doesn't have enough space to store the object. ENOMEM : System memory allocation failure. EINVAL : Invalid argument. EFAULT : Unexpected error. Data structure is not constant.

Definition at line 316 of file qhasharr.c.

## ◆ qhasharr_put_by_obj()

bool qhasharr_put_by_obj | ( | qhasharr_t * | tbl,
|  | const void * | name,
|  | size_t | namesize,
|  | const void * | data,
|  | size_t | datasize
| ) |  |

qhasharr->put_by_obj(): ut an object into this table by key object.

Parameters

  tbl | qhasharr_t container pointer.
  name | key data
  namesize | size of key
  data | data
  datasize | size of data

Returns
  true if successful, otherwise returns false

Return values

  errno | will be set in error condition. ENOBUFS : Table doesn't have enough space to store the object. EINVAL : Invalid argument. EFAULT : Unexpected error. Data structure is not constant.

Definition at line 344 of file qhasharr.c.

## ◆ qhasharr_get()

void * qhasharr_get | ( | qhasharr_t * | tbl,
|  | const char * | name,
|  | size_t * | datasize
| ) |  |

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

Parameters

  tbl | qhasharr_t container pointer.
  name | key string
  datasize | if not NULL, returned object size will be stored

Returns
  malloced object pointer if successful, otherwise(not found) returns NULL

Return values

  errno | will be set in error condition. ENOENT : No such key found. EINVAL : Invalid argument. ENOMEM : Memory allocation failed.

Note
  returned object must be freed after done using.

Definition at line 444 of file qhasharr.c.

## ◆ qhasharr_getstr()

char * qhasharr_getstr | ( | qhasharr_t * | tbl,
|  | const char * | name
| ) |  |

qhasharr->getstr(): Finds an object with given name and returns as string type.

Parameters

  tbl | qhasharr_t container pointer.
  name | key string

Returns
  string pointer if successful, otherwise(not found) returns NULL

Return values

  errno | will be set in error condition. ENOENT : No such key found. EINVAL : Invalid argument. ENOMEM : Memory allocation failed.

Note
  returned object must be freed after done using.

Definition at line 464 of file qhasharr.c.

## ◆ qhasharr_get_by_obj()

void * qhasharr_get_by_obj | ( | qhasharr_t * | tbl,
|  | const void * | name,
|  | size_t | namesize,
|  | size_t * | datasize
| ) |  |

qhasharr->get_by_object(): Get an object from this table by key object

Parameters

  tbl | qhasharr_t container pointer.
  name | key data
  namesize | size of key
  datasize | if not NULL, returned object size will be stored

Returns
  malloced object pointer if successful, otherwise(not found) returns NULL

Return values

  errno | will be set in error condition. ENOENT : No such key found. EINVAL : Invalid argument. ENOMEM : Memory allocation failed.

Note
  returned object must be freed after done using.

Definition at line 486 of file qhasharr.c.

## ◆ qhasharr_remove()

bool qhasharr_remove | ( | qhasharr_t * | tbl,
|  | const char * | name
| ) |  |

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

Parameters

  tbl | qhasharr_t container pointer.
  name | key string

Returns
  true if successful, otherwise(not found) returns false

Return values

  errno | will be set in error condition. ENOENT : No such key found. EINVAL : Invald argument. EFAULT : Unexpected error. Data structure is not constant.

Definition at line 518 of file qhasharr.c.

## ◆ qhasharr_remove_by_obj()

bool qhasharr_remove_by_obj | ( | qhasharr_t * | tbl,
|  | const char * | name,
|  | size_t | namesize
| ) |  |

qhasharr->remove_by_obj(): Remove an object from this table by key object

Parameters

  tbl | qhasharr_t container pointer.
  name | key data
  namesize | size of key

Returns
  true if successful, otherwise(not found) returns false

Return values

  errno | will be set in error condition. ENOENT : No such key found. EINVAL : Invald argument. EFAULT : Unexpected error. Data structure is not constant.

Definition at line 535 of file qhasharr.c.

## ◆ qhasharr_remove_by_idx()

bool qhasharr_remove_by_idx | ( | qhasharr_t * | tbl,
|  | int | idx
| ) |  |

qhasharr->remove_by_idx(): Remove an object from this table by index number.

Parameters

  tbl | qhasharr_t container pointer.
  idx | slot index number

Returns
  true if successful, otherwise(not found) returns false

Return values

  errno | will be set in error condition. ENOENT : Index is not pointing a valid object. EINVAL : Invald argument. EFAULT : Unexpected error. Data structure is not constant.

int idx = 0;
qhasharr_obj_t obj;
while(tbl->getnext(tbl, &obj, &idx) == true) {
if (condition_to_remove) {
idx--; // adjust index by -1
remove_by_idx(idx);
}
free(obj.name);
free(obj.data);
}

Note
  This function is to remove an object in getnext() traversal loop without knowing the object name but index value. When key names are longer than defined size, the keys are stored with truncation with their fingerprint, so this method provides a way to remove those keys. getnext() returns actual index + 1(pointing next slot of current finding), so you need to adjust it by -1 for the valid index number. And once you remove object by this method, rewind idx by -1 before calling getnext() because collision objects can be moved back to removed index again, so by adjusting index by -1, getnext() can continue search from the removed slot index again. Please refer an example code.

Definition at line 591 of file qhasharr.c.

## ◆ qhasharr_getnext()

bool qhasharr_getnext | ( | qhasharr_t * | tbl,
|  | qhasharr_obj_t * | obj,
|  | int * | idx
| ) |  |

qhasharr->getnext(): Get next element.

Parameters

  tbl | qhasharr_t container pointer.
  idx | index pointer

Returns
  key name string if successful, otherwise(end of table) returns NULL

Return values

  errno | will be set in error condition. ENOENT : No next element. EINVAL : Invald argument. ENOMEM : Memory allocation failed.

int idx = 0;
qhasharr_obj_t obj;
while(tbl->getnext(tbl, &obj, &idx) == true) {
printf("NAMESIZE=%zu, DATASIZE=%zu\n",
obj.namesize, obj.datasize);
free(obj.name); // key name
free(obj.data); // value data
}

Note
  Please be aware a key name will be returned with truncated length because key name gets truncated if it doesn't fit into slot size, Q_HASHARR_NAMESIZE.

Definition at line 676 of file qhasharr.c.

## ◆ qhasharr_size()

int qhasharr_size | ( | qhasharr_t * | tbl,
|  | int * | maxslots,
|  | int * | usedslots
| ) |  |

qhasharr->size(): Returns the number of objects in this table.

Parameters

  tbl | qhasharr_t container pointer.
  maxslots | if not NULL, total number of slots will be stored.
  usedslots | if not NULL, total number of used slots will be stored.

Returns
  a number of elements stored.

Definition at line 727 of file qhasharr.c.

## ◆ qhasharr_clear()

void qhasharr_clear | ( | qhasharr_t * | tbl | ) |

qhasharr->clear(): Clears this table so that it contains no keys.

Parameters

  tbl | qhasharr_t container pointer.

Returns
  true if successful, otherwise returns false.

Definition at line 750 of file qhasharr.c.

## ◆ qhasharr_debug()

bool qhasharr_debug | ( | qhasharr_t * | tbl,
|  | FILE * | out
| ) |  |

qhasharr->debug(): Print hash table for debugging purpose

Parameters

  tbl | qhasharr_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 780 of file qhasharr.c.

## ◆ qhasharr_free()

void qhasharr_free | ( | qhasharr_t * | tbl | ) |

qhasharr->free(): De-allocate table reference object.

Parameters

  tbl | qhashtbl_t container pointer.

Note
  This does not de-allocate the data memory but only the memory of qhasharr struct. User provided data memory must be de-allocated by user.

Definition at line 862 of file qhasharr.c.