|
4223
|
1 #include "config.h"
|
|
|
2 #include "hash.h"
|
|
|
3 #include "main.h"
|
|
|
4 #include "main_opt.h"
|
|
|
5 #include "random.h"
|
|
|
6 #include "xmalloc.h"
|
|
|
7
|
|
|
8 #include <errno.h>
|
|
|
9 #include <stddef.h>
|
|
|
10 #include <stdio.h>
|
|
|
11 #include <assert.h>
|
|
|
12
|
|
|
13 struct h_entry {
|
|
|
14 size_t hash;
|
|
|
15 void *key;
|
|
|
16 void *value;
|
|
|
17 };
|
|
|
18
|
|
|
19 struct h_node {
|
|
|
20 struct h_entry entry;
|
|
|
21 struct h_node *next;
|
|
|
22 };
|
|
|
23
|
|
|
24 enum {MAGIC = 112};
|
|
|
25
|
|
|
26 void h_init(
|
|
|
27 Hash *h,
|
|
|
28 size_t (*hash)(const void *, size_t),
|
|
|
29 int (*cmp)(const void *, const void *),
|
|
|
30 void (*delk)(void *),
|
|
|
31 void (*delv)(void *)
|
|
|
32 ) {
|
|
|
33 size_t i;
|
|
|
34
|
|
|
35 h->entries = 0;
|
|
|
36 h->brk = -1;
|
|
|
37 h->iter = -1;
|
|
|
38 h->iterptr = NULL;
|
|
|
39 h->seed = randval() * (size_t)-1;
|
|
|
40 h->delk = delk;
|
|
|
41 h->delv = delv;
|
|
|
42 assert(hash != NULL);
|
|
|
43 h->hash = hash;
|
|
|
44 assert(cmp != NULL);
|
|
|
45 h->cmp = cmp;
|
|
|
46 h->table = xmalloc(h->newsize = h->size = MAGIC, sizeof *h->table);
|
|
|
47 for (i = 0; i < h->size; ++i) {
|
|
|
48 h->table[i] = NULL;
|
|
|
49 }
|
|
|
50 }
|
|
|
51
|
|
|
52 #define DELKV(p) \
|
|
|
53 do { \
|
|
|
54 if (h->delk) { \
|
|
|
55 h->delk((p)->entry.key); \
|
|
|
56 } \
|
|
|
57 if (h->delv) { \
|
|
|
58 h->delv((p)->entry.value); \
|
|
|
59 } \
|
|
|
60 } while (0)
|
|
|
61
|
|
|
62 void h_end(Hash *h) {
|
|
|
63 size_t size, b;
|
|
|
64
|
|
|
65 if (!h->table)
|
|
|
66 return;
|
|
|
67
|
|
|
68 for (b = 0, size = h->newsize; h->newsize; h->newsize--) {
|
|
|
69 struct h_node *p;
|
|
|
70
|
|
|
71 if ((p = h->table[h->newsize - 1])) {
|
|
|
72 ++b;
|
|
|
73 for (; p; p = h->table[h->newsize - 1]) {
|
|
|
74 h->table[h->newsize - 1] = p->next;
|
|
|
75 DELKV(p);
|
|
|
76 xfree(p);
|
|
|
77 }
|
|
|
78 }
|
|
|
79 }
|
|
|
80 xfree(h->table);
|
|
|
81 h->table = NULL;
|
|
|
82
|
|
|
83 if (Opt.debug & DBG_HASH) {
|
|
|
84 fprintf(stderr, "%s: hash[%lu/%lu/%lu]\n", Prog, (unsigned long)h->entries, (unsigned long)b, (unsigned long)size);
|
|
|
85 }
|
|
|
86 }
|
|
|
87
|
|
|
88 ATTR_PURE
|
|
|
89 static size_t xclip(const Hash *h, const size_t hash_unc) {
|
|
|
90 size_t hash;
|
|
|
91
|
|
|
92 hash = hash_unc % h->size;
|
|
|
93 if (hash > h->brk) {
|
|
|
94 hash = hash_unc % h->newsize;
|
|
|
95 }
|
|
|
96
|
|
|
97 return hash;
|
|
|
98 }
|
|
|
99
|
|
|
100 #if 0
|
|
|
101 ATTR_PURE
|
|
|
102 static size_t xhash(const Hash *h, const void *key) {
|
|
|
103 return xclip(h, h->hash(key, h->seed));
|
|
|
104 }
|
|
|
105 #endif
|
|
|
106
|
|
|
107 #define XRESIZN(h) ((h)->brk + 1u)
|
|
|
108 #define XSTEP(h) do { if (XRESIZN(h)) xstep(h); } while (0)
|
|
|
109
|
|
|
110 static void xstep(Hash *h) {
|
|
|
111 struct h_node *rev = NULL;
|
|
|
112 struct h_node *p;
|
|
|
113 struct h_node *tmp;
|
|
|
114
|
|
|
115 assert(h->table != NULL);
|
|
|
116
|
|
|
117 for (p = h->table[h->brk]; p; p = tmp) {
|
|
|
118 tmp = p->next;
|
|
|
119 p->next = rev;
|
|
|
120 rev = p;
|
|
|
121 }
|
|
|
122 h->table[h->brk--] = NULL;
|
|
|
123
|
|
|
124 if (!XRESIZN(h)) {
|
|
|
125 h->size = h->newsize;
|
|
|
126 }
|
|
|
127
|
|
|
128 for (p = rev; p; p = tmp) {
|
|
|
129 const size_t i = xclip(h, p->entry.hash);
|
|
|
130 tmp = p->next;
|
|
|
131 p->next = h->table[i];
|
|
|
132 h->table[i] = p;
|
|
|
133 }
|
|
|
134 }
|
|
|
135
|
|
|
136 static void xincentries(Hash *h) {
|
|
|
137 h->entries++;
|
|
|
138 if (!(XRESIZN(h)) && h->entries / h->size > 3u) {
|
|
|
139 size_t i;
|
|
|
140 h->table = xrealloc(h->table, h->newsize = h->size * 2u + 1u);
|
|
|
141 for (i = h->size; i < h->newsize; ++i) {
|
|
|
142 h->table[i] = NULL;
|
|
|
143 }
|
|
|
144 h->brk = h->size - 1u;
|
|
|
145 xstep(h);
|
|
|
146 }
|
|
|
147 }
|
|
|
148
|
|
|
149 int h_get(Hash *h, const void *key, void **res) {
|
|
|
150 XSTEP(h);
|
|
|
151 {
|
|
|
152 const size_t hash_unc = h->hash(key, h->seed);
|
|
|
153 const size_t hash = xclip(h, hash_unc);
|
|
|
154 struct h_node *p;
|
|
|
155
|
|
|
156 for (p = h->table[hash]; p; p = p->next) {
|
|
|
157 if (hash_unc == p->entry.hash && h->cmp(p->entry.key, key) == 0) {
|
|
|
158 if (res) {
|
|
|
159 *res = p->entry.value;
|
|
|
160 }
|
|
|
161 return H_OK;
|
|
|
162 }
|
|
|
163 }
|
|
|
164 }
|
|
|
165 return H_NOENT;
|
|
|
166 }
|
|
|
167
|
|
|
168 int h_del(Hash *h, const void *key) {
|
|
|
169 XSTEP(h);
|
|
|
170 {
|
|
|
171 const size_t hash_unc = h->hash(key, h->seed);
|
|
|
172 const size_t hash = xclip(h, hash_unc);
|
|
|
173 struct h_node **p;
|
|
|
174
|
|
|
175 for (p = &h->table[hash]; *p; p = &(*p)->next) {
|
|
|
176 if (hash_unc == (*p)->entry.hash && h->cmp((*p)->entry.key, key) == 0) {
|
|
|
177 struct h_node *tmp = *p;
|
|
|
178 *p = (*p)->next;
|
|
|
179 DELKV(tmp);
|
|
|
180 xfree(tmp);
|
|
|
181 h->entries--;
|
|
|
182 return H_OK;
|
|
|
183 }
|
|
|
184 }
|
|
|
185 }
|
|
|
186
|
|
|
187 return H_NOENT;
|
|
|
188 }
|
|
|
189
|
|
|
190 #if 0
|
|
|
191 void h_push(Hash *h, void *key, void *val) {
|
|
|
192 XSTEP(h);
|
|
|
193 {
|
|
|
194 const size_t hash_unc = h->hash(key, h->seed);
|
|
|
195 const size_t hash = xclip(h, hash_unc);
|
|
|
196 struct h_node *p;
|
|
|
197
|
|
|
198 p = xmalloc(1, sizeof *p);
|
|
|
199 p->entry.hash = hash_unc;
|
|
|
200 p->entry.key = key;
|
|
|
201 p->entry.value = val;
|
|
|
202 p->next = h->table[hash];
|
|
|
203 h->table[hash] = p;
|
|
|
204
|
|
|
205 xincentries(h);
|
|
|
206 }
|
|
|
207 }
|
|
|
208 #endif
|
|
|
209
|
|
|
210 int h_put(Hash *h, void *key, void *val, int replace) {
|
|
|
211 XSTEP(h);
|
|
|
212 {
|
|
|
213 const size_t hash_unc = h->hash(key, h->seed);
|
|
|
214 const size_t hash = xclip(h, hash_unc);
|
|
|
215 struct h_node **p;
|
|
|
216
|
|
|
217 for (p = &h->table[hash]; *p; p = &(*p)->next) {
|
|
|
218 if (hash_unc == (*p)->entry.hash && h->cmp((*p)->entry.key, key) == 0) {
|
|
|
219 if (replace) {
|
|
|
220 DELKV(*p);
|
|
|
221 (*p)->entry.key = key;
|
|
|
222 (*p)->entry.value = val;
|
|
|
223 return H_OK;
|
|
|
224 } else {
|
|
|
225 return H_EXIST;
|
|
|
226 }
|
|
|
227 }
|
|
|
228 }
|
|
|
229
|
|
|
230 *p = xmalloc(1, sizeof **p);
|
|
|
231
|
|
|
232 (*p)->entry.hash = hash_unc;
|
|
|
233 (*p)->entry.key = key;
|
|
|
234 (*p)->entry.value = val;
|
|
|
235 (*p)->next = NULL;
|
|
|
236
|
|
|
237 xincentries(h);
|
|
|
238 }
|
|
|
239
|
|
|
240 return H_OK;
|
|
|
241 }
|
|
|
242
|
|
|
243 void h_reset(Hash *h) {
|
|
|
244 h->iter = -1;
|
|
|
245 h->iterptr = NULL;
|
|
|
246 }
|
|
|
247
|
|
|
248 int h_nextkv(Hash *h, void **k, void **v) {
|
|
|
249 if (h->iterptr) {
|
|
|
250 *k = h->iterptr->entry.key;
|
|
|
251 *v = h->iterptr->entry.value;
|
|
|
252 h->iterptr = h->iterptr->next;
|
|
|
253 return H_OK;
|
|
|
254 }
|
|
|
255
|
|
|
256 for (h->iter++; h->iter < h->newsize; h->iter++) {
|
|
|
257 if ((h->iterptr = h->table[h->iter])) {
|
|
|
258 *k = h->iterptr->entry.key;
|
|
|
259 *v = h->iterptr->entry.value;
|
|
|
260 h->iterptr = h->iterptr->next;
|
|
|
261 return H_OK;
|
|
|
262 }
|
|
|
263 }
|
|
|
264
|
|
|
265 h->iter = -1;
|
|
|
266 return H_NOENT;
|
|
|
267 }
|
|
|
268
|
|
|
269 #if 0
|
|
|
270 size_t (h_entries)(const Hash *h) {
|
|
|
271 return h_entries(h);
|
|
|
272 }
|
|
|
273 #endif
|
