base/libs/qdecoder/qHasharr.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include "qDecoder.h"
#include "qInternal.h"

Include dependency graph for qHasharr.c:

Go to the source code of this file.

FunctionsTitleTestFour
bool	qHasharrClear (Q_HASHARR *tbl)
void *	qHasharrGet (Q_HASHARR *tbl, const char *key, int *size)
const char *	qHasharrGetFirstKey (Q_HASHARR *tbl, int *idx)
int	qHasharrGetInt (Q_HASHARR *tbl, const char *key)
const char *	qHasharrGetNextKey (Q_HASHARR *tbl, int *idx)
char *	qHasharrGetStr (Q_HASHARR *tbl, const char *key)
int	qHasharrInit (Q_HASHARR *tbl, size_t memsize)
bool	qHasharrPrint (Q_HASHARR *tbl, FILE *out)
bool	qHasharrPut (Q_HASHARR *tbl, const char *key, const void *value, int size)
bool	qHasharrPutInt (Q_HASHARR *tbl, const char *key, int value)
bool	qHasharrPutStr (Q_HASHARR *tbl, const char *key, const char *value)
bool	qHasharrRemove (Q_HASHARR *tbl, const char *key)
size_t	qHasharrSize (int max)
bool	qHasharrStatus (Q_HASHARR *tbl, int *used, int *max)

---

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);

Definition in file qHasharr.c.