The qDecoder Project

qHasharr.c File Reference

Array based Hash-table Data Structure API. More...


Functions

size_t qHasharrSize (int max)
 Get how much memory is needed for N entries.
int qHasharrInit (Q_HASHARR *tbl, size_t memsize)
 Initialize array-hash table.
bool qHasharrClear (Q_HASHARR *tbl)
 Reset array-hash table.
bool qHasharrPut (Q_HASHARR *tbl, const char *key, const void *value, int size)
 Put object into hash table.
bool qHasharrPutStr (Q_HASHARR *tbl, const char *key, const char *value)
 Put string into hash table.
bool qHasharrPutInt (Q_HASHARR *tbl, const char *key, int value)
 Put integer into hash table.
void * qHasharrGet (Q_HASHARR *tbl, const char *key, int *size)
 Get object from hash table.
char * qHasharrGetStr (Q_HASHARR *tbl, const char *key)
 Get string from hash table.
int qHasharrGetInt (Q_HASHARR *tbl, const char *key)
 Get integer from hash table.
const char * qHasharrGetFirstKey (Q_HASHARR *tbl, int *idx)
 Get first key name.
const char * qHasharrGetNextKey (Q_HASHARR *tbl, int *idx)
 Get next key name.
bool qHasharrRemove (Q_HASHARR *tbl, const char *key)
 Remove key from hash table.
bool qHasharrPrint (Q_HASHARR *tbl, FILE *out)
 Print hash table for debugging purpose.
bool qHasharrStatus (Q_HASHARR *tbl, int *used, int *max)
 Get hash table internal status.


Detailed Description

Array based Hash-table Data Structure API.

Note:
In this array hash-table, we use some technics to effectively use memory. To verify key we use two way, if the key is smaller than (_Q_HASHARR_MAX_KEYSIZE - 1), we compare key itself. But if the key is bigger than (_Q_HASHARR_MAX_KEYSIZE - 1), we compare md5 of key and key length. If the key length and md5 of key are same we consider it's same key. So we don't need to store full key string. Actually it's not necessary to keep original key string, but we keep this because of two reasons. 1) if the length of the key is smaller than 16, it will be little bit quicker to compare key. 2) debugging reason.
Basically this hash-table based on array defines small size slot then it can links several slot for one data. This mechanism can save some wastes of memory. You can adjust default slot size to modify _Q_HASHARR_DEF_VALUESIZE.

   int maxkeys = 1000;

   // calculate how many memory do we need
   size_t memsize = qHasharrSize(maxkeys * 2); // generally allocate double size of max to decrease hash collision

   // allocate memory
   Q_HASHARR *hasharr = (Q_HASHARR *)malloc(memsize);

   // initialize hash-table
   if(qHasharrInit(hasharr, memsize) == 0) return -1;

   // put some sample data
   if(qHasharrPut(hasharr, "sample1", "binary", 6) == false) return -1; // hash-table full
   if(qHasharrPutStr(hasharr, "sample2", "string") == false) return -1; // hash-table full
   if(qHasharrPutInt(hasharr, "sample3", 3) == false) return -1; // hash-table full

   // fetch data
   int size;
   char *sample_bin = qHasharrGet(hasharr, "sample1", &size);
   char *sample_str = qHasharrGetStr(hasharr, "sample2");
   int  sample_int  = qHasharrGetInt(hasharr, "sample3");

Another simple way to initialize hash-table.

   // define data memory as much as you needed.
   char datamem[10 * 1024];

   // just set the Q_HASHARR points to data memory.
   Q_HASHARR *hasharr = (Q_HASHARR *)datamem;

   // initialize hash-table.
   if(qHasharrInit(hasharr, sizeof(datamem)) == 0) return -1;

   (...your codes here...)

   // no need to free unless you use malloc()

You can create hash table on shared memory like below.

   int maxkeys = 1000;
   int memsize = qHasharrSize(maxkeys * 2);

   // create shared memory
   int shmid = qShmInit(g_conf.szEgisdavdPidfile, 's', memsize, true);
   if(shmid < 0) return -1; // creation failed
   Q_HASHARR *hasharr = (Q_HASHARR *)qShmGet(shmid);

   // initialize hash-table
   if(qHasharrInit(hasharr, memsize) == 0) return -1;

   (...your codes here...)

   // destroy shared memory
   qShmFree(shmid);

Function Documentation

size_t qHasharrSize ( int  max  ) 

Get how much memory is needed for N entries.

Parameters:
max a number of maximum internal slots
Returns:
memory size needed
Note:
This is useful when you decide how much memory(shared-memory) required for N object entries. Be sure, a single object can be stored in several slots. So you need to consider additional slots if some data is bigger than _Q_HASHARR_DEF_VALUESIZE. By default, _Q_HASHARR_DEF_VALUESIZE is 32. This means if the size of object is bigger than 32 bytes it will use another slot.

int qHasharrInit ( Q_HASHARR tbl,
size_t  memsize 
)

Initialize array-hash table.

Parameters:
tbl a pointer of Q_HASHARR
memsize actual size of Q_HASHARR
Returns:
maximum number of available slots if successful, otherwise returns 0
   // allocate memory
   size_t memsize = qHasharrSize(100);
   Q_HASHARR *hasharr = (Q_HASHARR *)malloc(memsize);

   // initialize hash-table
   if(qHasharrInit(hasharr, memsize) == 0) return -1;

bool qHasharrClear ( Q_HASHARR tbl  ) 

Reset array-hash table.

Parameters:
tbl a pointer of Q_HASHARR
Returns:
true if successful, otherwise returns false
Note:
You do not need to call this, after qHasharrInit(). This is useful when you reset all of data in the hash table.

bool qHasharrPut ( Q_HASHARR tbl,
const char *  key,
const void *  value,
int  size 
)

Put object into hash table.

Parameters:
tbl a pointer of Q_HASHARR
key key string
value value object data
size size of value
Returns:
true if successful, otherwise returns false

bool qHasharrPutStr ( Q_HASHARR tbl,
const char *  key,
const char *  value 
)

Put string into hash table.

Parameters:
tbl a pointer of Q_HASHARR
key key string
value value string
Returns:
true if successful, otherwise returns false

bool qHasharrPutInt ( Q_HASHARR tbl,
const char *  key,
int  value 
)

Put integer into hash table.

Parameters:
tbl a pointer of Q_HASHARR
key key string
value value integer
Returns:
true if successful, otherwise returns false

void* qHasharrGet ( Q_HASHARR tbl,
const char *  key,
int *  size 
)

Get object from hash table.

Parameters:
tbl a pointer of Q_HASHARR
key key string
size if not NULL, oject size will be stored
Returns:
malloced object pointer if successful, otherwise(not found) returns NULL
Note:
returned object must be freed after done using.

char* qHasharrGetStr ( Q_HASHARR tbl,
const char *  key 
)

Get string from hash table.

Parameters:
tbl a pointer of Q_HASHARR
key key string
Returns:
string pointer if successful, otherwise(not found) returns NULL
Note:
returned object must be freed after done using.

int qHasharrGetInt ( Q_HASHARR tbl,
const char *  key 
)

Get integer from hash table.

Parameters:
tbl a pointer of Q_HASHARR
key key string
Returns:
value integer if successful, otherwise(not found) returns 0

const char* qHasharrGetFirstKey ( Q_HASHARR tbl,
int *  idx 
)

Get first key name.

Parameters:
tbl a pointer of Q_HASHARR
idx index pointer
Returns:
key name string if successful, otherwise returns NULL
Note:
Do not free returned key string.
   char *key;
   int idx;
   for(key = qHasharrGetFirstKey(tbl, &idx); key != NULL; key = qHasharrGetNextKey(tbl, &idx) {
     char *value = qHasharrGetStr(tbl, key);
     if(value != NULL) free(value);
   }

const char* qHasharrGetNextKey ( Q_HASHARR tbl,
int *  idx 
)

Get next key name.

Parameters:
tbl a pointer of Q_HASHARR
idx index pointer
Returns:
key name string if successful, otherwise(end of table) returns NULL
Note:
Do not free returned key string.

bool qHasharrRemove ( Q_HASHARR tbl,
const char *  key 
)

Remove key from hash table.

Parameters:
tbl a pointer of Q_HASHARR
key key string
Returns:
true if successful, otherwise(not found) returns false

bool qHasharrPrint ( Q_HASHARR tbl,
FILE *  out 
)

Print hash table for debugging purpose.

Parameters:
tbl a pointer of Q_HASHARR
out output stream
Returns:
true if successful, otherwise returns false

bool qHasharrStatus ( Q_HASHARR tbl,
int *  used,
int *  max 
)

Get hash table internal status.

Parameters:
tbl a pointer of Q_HASHARR
used if not NULL, a number of used slots(not a number of key) will be stored
max if not NULL, the maximum number of slots will be stored
Returns:
true if successful, otherwise returns false
Note:
It is different from dynamic hash-table. In array-hash table, a value object can be stored in several slots if the size of the object is bigger than the size of slot. So used and max slot number is not equal to actual stored and maximum storable objects number.


[Home] [About] [Examples] [Changes] [Download] [SVN Repository] [Install] [Reference]