xht.c

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