8 open addressing hash table with 2^n table size
9 quadratic probing is used in case of hash collision
10 tab indices and hash are size_t
11 after resize fails with ENOMEM the state of tab is still usable
13 with the posix api items cannot be iterated and length cannot be queried
17 #define MAXSIZE ((size_t)-1/2 + 1)
25 static struct hsearch_data htab;
27 int __hcreate_r(size_t, struct hsearch_data *);
28 void __hdestroy_r(struct hsearch_data *);
29 int __hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *);
31 static size_t keyhash(char *k)
33 unsigned char *p = (void *)k;
41 static int resize(size_t nel, struct hsearch_data *htab)
46 ENTRY *oldtab = htab->__tab->entries;
47 ENTRY *oldend = htab->__tab->entries + htab->__tab->mask + 1;
51 for (newsize = MINSIZE; newsize < nel; newsize *= 2);
52 htab->__tab->entries = calloc(newsize, sizeof *htab->__tab->entries);
53 if (!htab->__tab->entries) {
54 htab->__tab->entries = oldtab;
57 htab->__tab->mask = newsize - 1;
60 for (e = oldtab; e < oldend; e++)
62 for (i=keyhash(e->key),j=1; ; i+=j++) {
63 newe = htab->__tab->entries + (i & htab->__tab->mask);
73 int hcreate(size_t nel)
75 return __hcreate_r(nel, &htab);
83 static ENTRY *lookup(char *key, size_t hash, struct hsearch_data *htab)
88 for (i=hash,j=1; ; i+=j++) {
89 e = htab->__tab->entries + (i & htab->__tab->mask);
90 if (!e->key || strcmp(e->key, key) == 0)
96 ENTRY *hsearch(ENTRY item, ACTION action)
100 __hsearch_r(item, action, &e, &htab);
104 int __hcreate_r(size_t nel, struct hsearch_data *htab)
108 htab->__tab = calloc(1, sizeof *htab->__tab);
111 r = resize(nel, htab);
118 weak_alias(__hcreate_r, hcreate_r);
120 void __hdestroy_r(struct hsearch_data *htab)
122 if (htab->__tab) free(htab->__tab->entries);
126 weak_alias(__hdestroy_r, hdestroy_r);
128 int __hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab)
130 size_t hash = keyhash(item.key);
131 ENTRY *e = lookup(item.key, hash, htab);
137 if (action == FIND) {
142 if (++htab->__tab->used > htab->__tab->mask - htab->__tab->mask/4) {
143 if (!resize(2*htab->__tab->used, htab)) {
149 e = lookup(item.key, hash, htab);
154 weak_alias(__hsearch_r, hsearch_r);