6 open addressing hash table with 2^n table size
7 quadratic probing is used in case of hash collision
8 tab indices and hash are size_t
9 after resize fails with ENOMEM the state of tab is still usable
11 with the posix api items cannot be iterated and length cannot be queried
15 #define MAXSIZE ((size_t)-1/2 + 1)
24 static struct entry *tab;
26 static size_t keyhash(char *k)
28 unsigned char *p = (void *)k;
36 static int resize(size_t nel)
40 struct entry *e, *newe;
41 struct entry *oldtab = tab;
42 struct entry *oldend = tab + mask + 1;
46 for (newsize = MINSIZE; newsize < nel; newsize *= 2);
47 tab = calloc(newsize, sizeof *tab);
55 for (e = oldtab; e < oldend; e++)
57 for (i=e->hash,j=1; ; i+=j++) {
58 newe = tab + (i & mask);
68 int hcreate(size_t nel)
84 static struct entry *lookup(char *key, size_t hash)
89 for (i=hash,j=1; ; i+=j++) {
92 (e->hash==hash && strcmp(e->item.key, key)==0))
98 ENTRY *hsearch(ENTRY item, ACTION action)
100 size_t hash = keyhash(item.key);
101 struct entry *e = lookup(item.key, hash);
109 if (++used > mask - mask/4) {
110 if (!resize(2*used)) {
115 e = lookup(item.key, hash);