xht.c

   1 #include "xht.h"
   2
   3 typedef struct xhn_struct
   4 {
   5     char flag;
   6     struct xhn_struct *next;
   7     const char *key;
   8     void *val;
   9 } *xhn;
  10
  11 struct xht_struct
  12 {
  13     int prime;
  14     xhn zen;
  15 };
  16
  17 /* Generates a hash code for a string.
  18  * This function uses the ELF hashing algorithm as reprinted in
  19  * Andrew Binstock, "Hashing Rehashed," Dr. Dobb's Journal, April 1996.
  20  */
  21 int _xhter(const char *s)
  22 {
  23     /* ELF hash uses unsigned chars and unsigned arithmetic for portability */
  24     const unsigned char *name = (const unsigned char *)s;
  25     unsigned long h = 0, g;
  26
  27     while (*name)
  28     { /* do some fancy bitwanking on the string */
  29         h = (h << 4) + (unsigned long)(*name++);
  30         if ((g = (h & 0xF0000000UL))!=0)
  31             h ^= (g >> 24);
  32         h &= ~g;
  33
  34     }
  35
  36     return (int)h;
  37 }
  38
  39
  40 xhn _xht_node_find(xhn n, const char *key)
  41 {
  42     for(;n != 0; n = n->next)
  43         if(n->key != 0 && strcmp(key, n->key) == 0)
  44             return n;
  45     return 0;
  46 }
  47
  48
  49 xht xht_new(int prime)
  50 {
  51     xht xnew;
  52
  53     xnew = (xht)malloc(sizeof(struct xht_struct));
  54     xnew->prime = prime;
  55     xnew->zen = (xhn)malloc(sizeof(struct xhn_struct)*prime); /* array of xhn size of prime */
  56     bzero(xnew->zen,sizeof(struct xhn_struct)*prime);
  57     return xnew;
  58 }
  59
  60 /* does the set work, used by xht_set and xht_store */
  61 xhn _xht_set(xht h, const char *key, void *val, char flag)
  62 {
  63     int i;
  64     xhn n;
  65
  66     /* get our index for this key */
  67     i = _xhter(key) % h->prime;
  68
  69     /* check for existing key first, or find an empty one */
  70     if((n = _xht_node_find(&h->zen[i], key)) == 0)
  71         for(n = &h->zen[i]; n != 0; n = n->next)
  72             if(n->val == 0)
  73                 break;
  74
  75     /* if none, make a new one, link into this index */
  76     if(n == 0)
  77     {
  78         n = (xhn)malloc(sizeof(struct xhn_struct));
  79         n->next = h->zen[i].next;
  80         h->zen[i].next = n;
  81     }
  82
  83     /* when flag is set, we manage their mem and free em first */
  84     if(n->flag)
  85     {
  86         free(n->key);
  87         free(n->val);
  88     }
  89
  90     n->flag = flag;
  91     n->key = key;
  92     n->val = val;
  93 }
  94
  95 void xht_set(xht h, const char *key, void *val)
  96 {
  97     if(h == 0 || key == 0)
  98         return;
  99     _xht_set(h, key, val, 0);
 100 }
 101
 102 void xht_store(xht h, const char *key, int klen, void *val, int vlen)
 103 {
 104     char *ckey, *cval;
 105
 106     if(h == 0 || key == 0 || klen == 0)
 107         return;
 108
 109     ckey = (char*)malloc(klen+1);
 110     memcpy(ckey,key,klen);
 111     ckey[klen] = '\0';
 112     cval = (void*)malloc(vlen+1);
 113     memcpy(cval,val,vlen);
 114     cval[vlen] = '\0'; /* convenience, in case it was a string too */
 115     _xht_set(h, ckey, cval, 1);
 116 }
 117
 118
 119 void *xht_get(xht h, const char *key)
 120 {
 121     xhn n;
 122
 123     if(h == 0 || key == 0 || (n = _xht_node_find(&h->zen[_xhter(key) % h->prime], key)) == 0)
 124         return 0;
 125
 126     return n->val;
 127 }
 128
 129
 130 void xht_free(xht h)
 131 {
 132     xhn n, f;
 133     int i;
 134
 135     if(h == 0) return;
 136
 137     for(i = 0; i < h->prime; i++)
 138         for(n = (&h->zen[i])->next; n != 0;)
 139         {
 140             f = n->next;
 141             if(n->flag)
 142             {
 143                 free(n->key);
 144                 free(n->val);
 145             }
 146             free(n);
 147             n = f;
 148         }
 149
 150     free(h->zen);
 151     free(h);
 152 }
 153
 154 void xht_walk(xht h, xht_walker w, void *arg)
 155 {
 156     int i;
 157     xhn n;
 158
 159     if(h == 0 || w == 0)
 160         return;
 161
 162     for(i = 0; i < h->prime; i++)
 163         for(n = &h->zen[i]; n != 0; n = n->next)
 164             if(n->key != 0 && n->val != 0)
 165                 (*w)(h, n->key, n->val, arg);
 166 }
 167