1#define _GNU_SOURCE
2#include <stdlib.h>
3#include <string.h>
4#include <search.h>
5
6/*
7open addressing hash table with 2^n table size
8quadratic probing is used in case of hash collision
9tab indices and hash are size_t
10after resize fails with ENOMEM the state of tab is still usable
11
12with the posix api items cannot be iterated and length cannot be queried
13*/
14
15#define MINSIZE 8
16#define MAXSIZE ((size_t)-1/2 + 1)
17
18struct __tab {
19 ENTRY *entries;
20 size_t mask;
21 size_t used;
22};
23
24static struct hsearch_data htab;
25
26static int __hcreate_r(size_t, struct hsearch_data *);
27static void __hdestroy_r(struct hsearch_data *);
28static int __hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *);
29
30static size_t keyhash(char *k)
31{
32 unsigned char *p = (void *)k;
33 size_t h = 0;
34
35 while (*p)
36 h = 31*h + *p++;
37 return h;
38}
39
40static int resize(size_t nel, struct hsearch_data *htab)
41{
42 size_t newsize;
43 size_t i, j;
44 size_t oldsize = htab->__tab->mask + 1;
45 ENTRY *e, *newe;
46 ENTRY *oldtab = htab->__tab->entries;
47
48 if (nel > MAXSIZE)
49 nel = MAXSIZE;
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;
54 return 0;
55 }
56 htab->__tab->mask = newsize - 1;
57 if (!oldtab)
58 return 1;
59 for (e = oldtab; e < oldtab + oldsize; e++)
60 if (e->key) {
61 for (i=keyhash(e->key),j=1; ; i+=j++) {
62 newe = htab->__tab->entries + (i & htab->__tab->mask);
63 if (!newe->key)
64 break;
65 }
66 *newe = *e;
67 }
68 free(oldtab);
69 return 1;
70}
71
72int hcreate(size_t nel)
73{
74 return __hcreate_r(nel, &htab);
75}
76
77void hdestroy(void)
78{
79 __hdestroy_r(&htab);
80}
81
82static ENTRY *lookup(char *key, size_t hash, struct hsearch_data *htab)
83{
84 size_t i, j;
85 ENTRY *e;
86
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)
90 break;
91 }
92 return e;
93}
94
95ENTRY *hsearch(ENTRY item, ACTION action)
96{
97 ENTRY *e;
98
99 __hsearch_r(item, action, &e, &htab);
100 return e;
101}
102
103static int __hcreate_r(size_t nel, struct hsearch_data *htab)
104{
105 int r;
106
107 htab->__tab = calloc(1, sizeof *htab->__tab);
108 if (!htab->__tab)
109 return 0;
110 r = resize(nel, htab);
111 if (r == 0) {
112 free(htab->__tab);
113 htab->__tab = 0;
114 }
115 return r;
116}
117weak_alias(__hcreate_r, hcreate_r);
118
119static void __hdestroy_r(struct hsearch_data *htab)
120{
121 if (htab->__tab) free(htab->__tab->entries);
122 free(htab->__tab);
123 htab->__tab = 0;
124}
125weak_alias(__hdestroy_r, hdestroy_r);
126
127static int __hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab)
128{
129 size_t hash = keyhash(item.key);
130 ENTRY *e = lookup(item.key, hash, htab);
131
132 if (e->key) {
133 *retval = e;
134 return 1;
135 }
136 if (action == FIND) {
137 *retval = 0;
138 return 0;
139 }
140 *e = item;
141 if (++htab->__tab->used > htab->__tab->mask - htab->__tab->mask/4) {
142 if (!resize(2*htab->__tab->used, htab)) {
143 htab->__tab->used--;
144 e->key = 0;
145 *retval = 0;
146 return 0;
147 }
148 e = lookup(item.key, hash, htab);
149 }
150 *retval = e;
151 return 1;
152}
153weak_alias(__hsearch_r, hsearch_r);