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)
30 static struct hsearch_data htab;
32 int __hcreate_r(size_t, struct hsearch_data *);
33 void __hdestroy_r(struct hsearch_data *);
34 int __hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *);
36 static size_t keyhash(char *k)
38 unsigned char *p = (void *)k;
46 static int resize(size_t nel, struct hsearch_data *htab)
50 struct elem *e, *newe;
51 struct elem *oldtab = htab->__tab->elems;
52 struct elem *oldend = htab->__tab->elems + htab->__tab->mask + 1;
56 for (newsize = MINSIZE; newsize < nel; newsize *= 2);
57 htab->__tab->elems = calloc(newsize, sizeof *htab->__tab->elems);
58 if (!htab->__tab->elems) {
59 htab->__tab->elems = oldtab;
62 htab->__tab->mask = newsize - 1;
65 for (e = oldtab; e < oldend; e++)
67 for (i=e->hash,j=1; ; i+=j++) {
68 newe = htab->__tab->elems + (i & htab->__tab->mask);
78 int hcreate(size_t nel)
80 return __hcreate_r(nel, &htab);
88 static struct elem *lookup(char *key, size_t hash, struct hsearch_data *htab)
93 for (i=hash,j=1; ; i+=j++) {
94 e = htab->__tab->elems + (i & htab->__tab->mask);
96 (e->hash==hash && strcmp(e->item.key, key)==0))
102 ENTRY *hsearch(ENTRY item, ACTION action)
106 __hsearch_r(item, action, &e, &htab);
110 int __hcreate_r(size_t nel, struct hsearch_data *htab)
114 htab->__tab = calloc(1, sizeof *htab->__tab);
117 r = resize(nel, htab);
124 weak_alias(__hcreate_r, hcreate_r);
126 void __hdestroy_r(struct hsearch_data *htab)
128 if (htab->__tab) free(htab->__tab->elems);
132 weak_alias(__hdestroy_r, hdestroy_r);
134 int __hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab)
136 size_t hash = keyhash(item.key);
137 struct elem *e = lookup(item.key, hash, htab);
143 if (action == FIND) {
149 if (++htab->__tab->used > htab->__tab->mask - htab->__tab->mask/4) {
150 if (!resize(2*htab->__tab->used, htab)) {
156 e = lookup(item.key, hash, htab);
161 weak_alias(__hsearch_r, hsearch_r);