7 open addressing hash table with 2^n table size
8 quadratic probing is used in case of hash collision
9 tab indices and hash are size_t
10 after resize fails with ENOMEM the state of tab is still usable
12 with the posix api items cannot be iterated and length cannot be queried
16 #define MAXSIZE ((size_t)-1/2 + 1)
24 static struct hsearch_data htab;
26 static int __hcreate_r(size_t, struct hsearch_data *);
27 static void __hdestroy_r(struct hsearch_data *);
28 static int __hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *);
30 static size_t keyhash(char *k)
32 unsigned char *p = (void *)k;
40 static int resize(size_t nel, struct hsearch_data *htab)
44 size_t oldsize = htab->__tab->mask + 1;
46 ENTRY *oldtab = htab->__tab->entries;
50 for (newsize = MINSIZE; newsize < nel; newsize *= 2);
51 htab->__tab->entries = calloc(newsize, sizeof *htab->__tab->entries);
52 if (!htab->__tab->entries) {
53 htab->__tab->entries = oldtab;
56 htab->__tab->mask = newsize - 1;
59 for (e = oldtab; e < oldtab + oldsize; e++)
61 for (i=keyhash(e->key),j=1; ; i+=j++) {
62 newe = htab->__tab->entries + (i & htab->__tab->mask);
72 int hcreate(size_t nel)
74 return __hcreate_r(nel, &htab);
82 static ENTRY *lookup(char *key, size_t hash, struct hsearch_data *htab)
87 for (i=hash,j=1; ; i+=j++) {
88 e = htab->__tab->entries + (i & htab->__tab->mask);
89 if (!e->key || strcmp(e->key, key) == 0)
95 ENTRY *hsearch(ENTRY item, ACTION action)
99 __hsearch_r(item, action, &e, &htab);
103 static int __hcreate_r(size_t nel, struct hsearch_data *htab)
107 htab->__tab = calloc(1, sizeof *htab->__tab);
110 r = resize(nel, htab);
117 weak_alias(__hcreate_r, hcreate_r);
119 static void __hdestroy_r(struct hsearch_data *htab)
121 if (htab->__tab) free(htab->__tab->entries);
125 weak_alias(__hdestroy_r, hdestroy_r);
127 static int __hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab)
129 size_t hash = keyhash(item.key);
130 ENTRY *e = lookup(item.key, hash, htab);
136 if (action == FIND) {
141 if (++htab->__tab->used > htab->__tab->mask - htab->__tab->mask/4) {
142 if (!resize(2*htab->__tab->used, htab)) {
148 e = lookup(item.key, hash, htab);
153 weak_alias(__hsearch_r, hsearch_r);