5 typedef struct xhn_struct
8 struct xhn_struct *next;
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.
23 int _xhter(const char *s)
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;
30 { /* do some fancy bitwanking on the string */
31 h = (h << 4) + (unsigned long)(*name++);
32 if ((g = (h & 0xF0000000UL))!=0)
42 xhn _xht_node_find(xhn n, const char *key)
44 for(;n != 0; n = n->next)
45 if(n->key != 0 && strcmp(key, n->key) == 0)
51 xht xht_new(int prime)
55 xnew = (xht)malloc(sizeof(struct xht_struct));
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);
62 /* does the set work, used by xht_set and xht_store */
63 void _xht_set(xht h, char *key, void *val, char flag)
68 /* get our index for this key */
69 i = _xhter(key) % h->prime;
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)
77 /* if none, make a new one, link into this index */
80 n = (xhn)malloc(sizeof(struct xhn_struct));
81 n->next = h->zen[i].next;
85 /* when flag is set, we manage their mem and free em first */
97 void xht_set(xht h, char *key, void *val)
99 if(h == 0 || key == 0)
101 _xht_set(h, key, val, 0);
104 void xht_store(xht h, const char *key, int klen, void *val, int vlen)
108 if(h == 0 || key == 0 || klen == 0)
111 ckey = (char*)malloc(klen+1);
112 memcpy(ckey,key,klen);
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);
121 void *xht_get(xht h, const char *key)
125 if(h == 0 || key == 0 || (n = _xht_node_find(&h->zen[_xhter(key) % h->prime], key)) == 0)
139 for(i = 0; i < h->prime; i++)
140 for(n = (&h->zen[i])->next; n != 0;)
156 void xht_walk(xht h, xht_walker w, void *arg)
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);