3 typedef struct xhn_struct
6 struct xhn_struct *next;
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.
21 int _xhter(const char *s)
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;
28 { /* do some fancy bitwanking on the string */
29 h = (h << 4) + (unsigned long)(*name++);
30 if ((g = (h & 0xF0000000UL))!=0)
40 xhn _xht_node_find(xhn n, const char *key)
42 for(;n != 0; n = n->next)
43 if(n->key != 0 && strcmp(key, n->key) == 0)
49 xht xht_new(int prime)
53 xnew = (xht)malloc(sizeof(struct xht_struct));
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);
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)
66 /* get our index for this key */
67 i = _xhter(key) % h->prime;
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)
75 /* if none, make a new one, link into this index */
78 n = (xhn)malloc(sizeof(struct xhn_struct));
79 n->next = h->zen[i].next;
83 /* when flag is set, we manage their mem and free em first */
95 void xht_set(xht h, const char *key, void *val)
97 if(h == 0 || key == 0)
99 _xht_set(h, key, val, 0);
102 void xht_store(xht h, const char *key, int klen, void *val, int vlen)
106 if(h == 0 || key == 0 || klen == 0)
109 ckey = (char*)malloc(klen+1);
110 memcpy(ckey,key,klen);
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);
119 void *xht_get(xht h, const char *key)
123 if(h == 0 || key == 0 || (n = _xht_node_find(&h->zen[_xhter(key) % h->prime], key)) == 0)
137 for(i = 0; i < h->prime; i++)
138 for(n = (&h->zen[i])->next; n != 0;)
154 void xht_walk(xht h, xht_walker w, void *arg)
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);