1 /* $NetBSD: hash.c,v 1.11 2014/10/29 17:14:50 christos Exp $ */
2
3 /*
4 * Copyright (c) 1992, 1993
5 * The Regents of the University of California. All rights reserved.
6 *
7 * This software was developed by the Computer Systems Engineering group
8 * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and
9 * contributed to Berkeley.
10 *
11 * All advertising materials mentioning features or use of this software
12 * must display the following acknowledgement:
13 * This product includes software developed by the University of
14 * California, Lawrence Berkeley Laboratories.
15 *
16 * Redistribution and use in source and binary forms, with or without
17 * modification, are permitted provided that the following conditions
18 * are met:
19 * 1. Redistributions of source code must retain the above copyright
20 * notice, this list of conditions and the following disclaimer.
21 * 2. Redistributions in binary form must reproduce the above copyright
22 * notice, this list of conditions and the following disclaimer in the
23 * documentation and/or other materials provided with the distribution.
24 * 3. Neither the name of the University nor the names of its contributors
25 * may be used to endorse or promote products derived from this software
26 * without specific prior written permission.
27 *
28 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
29 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
30 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
31 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
32 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
33 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
34 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
35 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
36 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
37 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
38 * SUCH DAMAGE.
39 *
40 * from: @(#)hash.c 8.1 (Berkeley) 6/6/93
41 */
42
43 #if HAVE_NBTOOL_CONFIG_H
44 #include "nbtool_config.h"
45 #endif
46
47 #include <sys/cdefs.h>
48 __RCSID("$NetBSD: hash.c,v 1.11 2014/10/29 17:14:50 christos Exp $");
49
50 #include <sys/param.h>
51 #include <assert.h>
52 #include <stdlib.h>
53 #include <string.h>
54 #include <util.h>
55 #include "defs.h"
56
57 /*
58 * Interned strings are kept in a hash table. By making each string
59 * unique, the program can compare strings by comparing pointers.
60 */
61 struct hashent {
62 // XXXLUKEM: a SIMPLEQ might be more appropriate
63 TAILQ_ENTRY(hashent) h_next;
64 const char *h_names[2]; /* the string */
65 #define h_name1 h_names[0]
66 #define h_name2 h_names[1]
67 #define h_name h_name1
68 u_int h_hash; /* its hash value */
69 void *h_value; /* other values (for name=value) */
70 };
71 struct hashtab {
72 size_t ht_size; /* size (power of 2) */
73 size_t ht_mask; /* == ht_size - 1 */
74 size_t ht_used; /* number of entries used */
75 size_t ht_lim; /* when to expand */
76 TAILQ_HEAD(hashenthead, hashent) *ht_tab;
77 };
78
79 static struct hashtab strings;
80
81 /*
82 * HASHFRACTION controls ht_lim, which in turn controls the average chain
83 * length. We allow a few entries, on average, as comparing them is usually
84 * cheap (the h_hash values prevent a strcmp).
85 */
86 #define HASHFRACTION(sz) ((sz) * 3 / 2)
87
88 static void ht_expand(struct hashtab *);
89 static void ht_init(struct hashtab *, size_t);
90 static inline u_int hash(u_int, const char *);
91 static inline u_int hash2(u_int, const char *, const char *);
92 static inline struct hashent *newhashent(const char *, u_int);
93
94 /*
95 * Initialize a new hash table. The size must be a power of 2.
96 */
97 static void
ht_init(struct hashtab * ht,size_t sz)98 ht_init(struct hashtab *ht, size_t sz)
99 {
100 u_int n;
101
102 ht->ht_tab = emalloc(sz * sizeof (ht->ht_tab[0]));
103 ht->ht_size = sz;
104 ht->ht_mask = sz - 1;
105 for (n = 0; n < sz; n++)
106 TAILQ_INIT(&ht->ht_tab[n]);
107 ht->ht_used = 0;
108 ht->ht_lim = HASHFRACTION(sz);
109 }
110
111 /*
112 * Expand an existing hash table.
113 */
114 static void
ht_expand(struct hashtab * ht)115 ht_expand(struct hashtab *ht)
116 {
117 struct hashenthead *h, *oldh;
118 struct hashent *p;
119 size_t n, i;
120
121 n = ht->ht_size * 2;
122 h = emalloc(n * sizeof *h);
123 for (i = 0; i < n; i++)
124 TAILQ_INIT(&h[i]);
125 oldh = ht->ht_tab;
126 n--;
127 for (i = 0; i < ht->ht_size; i++) {
128 while ((p = TAILQ_FIRST(&oldh[i])) != NULL) {
129 TAILQ_REMOVE(&oldh[i], p, h_next);
130 // XXXLUKEM: really should be TAILQ_INSERT_TAIL
131 TAILQ_INSERT_HEAD(&h[p->h_hash & n], p, h_next);
132 }
133 }
134 free(ht->ht_tab);
135 ht->ht_tab = h;
136 ht->ht_mask = n;
137 ht->ht_size = ++n;
138 ht->ht_lim = HASHFRACTION(n);
139 }
140
141 /*
142 * Make a new hash entry, setting its h_next to NULL.
143 * If the free list is not empty, use the first entry from there,
144 * otherwise allocate a new entry.
145 */
146 static inline struct hashent *
newhashent2(const char * name1,const char * name2,u_int h)147 newhashent2(const char *name1, const char *name2, u_int h)
148 {
149 struct hashent *hp;
150
151 hp = ecalloc(1, sizeof(*hp));
152
153 hp->h_name1 = name1;
154 hp->h_name2 = name2;
155 hp->h_hash = h;
156 return (hp);
157 }
158
159 static inline struct hashent *
newhashent(const char * name,u_int h)160 newhashent(const char *name, u_int h)
161 {
162 return newhashent2(name, NULL, h);
163 }
164
165 static inline u_int
hv(u_int h,char c)166 hv(u_int h, char c)
167 {
168 return (h << 5) + h + (unsigned char)c;
169 }
170
171 /*
172 * Hash a string.
173 */
174 static inline u_int
hash(u_int h,const char * str)175 hash(u_int h, const char *str)
176 {
177
178 while (str && *str)
179 h = hv(h, *str++);
180 return (h);
181 }
182
183 #define HASH2DELIM ' '
184
185 static inline u_int
hash2(u_int h,const char * str1,const char * str2)186 hash2(u_int h, const char *str1, const char *str2)
187 {
188
189 h = hash(h, str1);
190 h = hv(h, HASH2DELIM);
191 h = hash(h, str2);
192 return (h);
193 }
194
195 void
initintern(void)196 initintern(void)
197 {
198
199 ht_init(&strings, 128);
200 }
201
202 /*
203 * Generate a single unique copy of the given string. We expect this
204 * function to be used frequently, so it should be fast.
205 */
206 const char *
intern(const char * s)207 intern(const char *s)
208 {
209 struct hashtab *ht;
210 struct hashent *hp;
211 struct hashenthead *hpp;
212 u_int h;
213 char *p;
214
215 ht = &strings;
216 h = hash2(0, s, NULL);
217 hpp = &ht->ht_tab[h & ht->ht_mask];
218 TAILQ_FOREACH(hp, hpp, h_next) {
219 if (hp->h_hash == h && strcmp(hp->h_name, s) == 0)
220 return (hp->h_name);
221 }
222 p = estrdup(s);
223 hp = newhashent(p, h);
224 TAILQ_INSERT_TAIL(hpp, hp, h_next);
225 if (++ht->ht_used > ht->ht_lim)
226 ht_expand(ht);
227 return (p);
228 }
229
230 struct hashtab *
ht_new(void)231 ht_new(void)
232 {
233 struct hashtab *ht;
234
235 ht = ecalloc(1, sizeof *ht);
236 ht_init(ht, 8);
237 return (ht);
238 }
239
240 void
ht_free(struct hashtab * ht)241 ht_free(struct hashtab *ht)
242 {
243 size_t i;
244 struct hashent *hp;
245 struct hashenthead *hpp;
246
247 for (i = 0; i < ht->ht_size; i++) {
248 hpp = &ht->ht_tab[i];
249 while ((hp = TAILQ_FIRST(hpp)) != NULL) {
250 TAILQ_REMOVE(hpp, hp, h_next);
251 free(hp);
252 ht->ht_used--;
253 }
254 }
255
256 assert(ht->ht_used == 0);
257 free(ht->ht_tab);
258 free(ht);
259 }
260
261 /*
262 * Insert and/or replace.
263 */
264 int
ht_insrep2(struct hashtab * ht,const char * nam1,const char * nam2,void * val,int replace)265 ht_insrep2(struct hashtab *ht, const char *nam1, const char *nam2, void *val, int replace)
266 {
267 struct hashent *hp;
268 struct hashenthead *hpp;
269 u_int h;
270
271 h = hash2(0, nam1, nam2);
272 hpp = &ht->ht_tab[h & ht->ht_mask];
273 TAILQ_FOREACH(hp, hpp, h_next) {
274 if (hp->h_name1 == nam1 &&
275 hp->h_name2 == nam2) {
276 if (replace)
277 hp->h_value = val;
278 return (1);
279 }
280 }
281 hp = newhashent2(nam1, nam2, h);
282 TAILQ_INSERT_TAIL(hpp, hp, h_next);
283 hp->h_value = val;
284 if (++ht->ht_used > ht->ht_lim)
285 ht_expand(ht);
286 return (0);
287 }
288
289 int
ht_insrep(struct hashtab * ht,const char * nam,void * val,int replace)290 ht_insrep(struct hashtab *ht, const char *nam, void *val, int replace)
291 {
292 return ht_insrep2(ht, nam, NULL, val, replace);
293 }
294
295 /*
296 * Remove.
297 */
298 int
ht_remove2(struct hashtab * ht,const char * name1,const char * name2)299 ht_remove2(struct hashtab *ht, const char *name1, const char *name2)
300 {
301 struct hashent *hp;
302 struct hashenthead *hpp;
303 u_int h;
304
305 h = hash2(0, name1, name2);
306 hpp = &ht->ht_tab[h & ht->ht_mask];
307
308 TAILQ_FOREACH(hp, hpp, h_next) {
309 if (hp->h_name1 != name1 || hp->h_name2 != name2)
310 continue;
311 TAILQ_REMOVE(hpp, hp, h_next);
312
313 free(hp);
314 ht->ht_used--;
315 return (0);
316 }
317 return (1);
318 }
319
320 int
ht_remove(struct hashtab * ht,const char * name)321 ht_remove(struct hashtab *ht, const char *name)
322 {
323 return ht_remove2(ht, name, NULL);
324 }
325
326 void *
ht_lookup2(struct hashtab * ht,const char * nam1,const char * nam2)327 ht_lookup2(struct hashtab *ht, const char *nam1, const char *nam2)
328 {
329 struct hashent *hp;
330 struct hashenthead *hpp;
331 u_int h;
332
333 h = hash2(0, nam1, nam2);
334 hpp = &ht->ht_tab[h & ht->ht_mask];
335 TAILQ_FOREACH(hp, hpp, h_next)
336 if (hp->h_name == nam1)
337 return (hp->h_value);
338 return (NULL);
339 }
340
341 void *
ht_lookup(struct hashtab * ht,const char * nam)342 ht_lookup(struct hashtab *ht, const char *nam)
343 {
344 return ht_lookup2(ht, nam, NULL);
345 }
346
347 /*
348 * first parameter to callback is the entry name from the hash table
349 * second parameter is the value from the hash table
350 * third argument is passed through from the "arg" parameter to ht_enumerate()
351 */
352
353 int
ht_enumerate2(struct hashtab * ht,ht_callback2 cbfunc2,void * arg)354 ht_enumerate2(struct hashtab *ht, ht_callback2 cbfunc2, void *arg)
355 {
356 struct hashent *hp;
357 struct hashenthead *hpp;
358 size_t i;
359 int rval = 0;
360
361 for (i = 0; i < ht->ht_size; i++) {
362 hpp = &ht->ht_tab[i];
363 TAILQ_FOREACH(hp, hpp, h_next)
364 rval += (*cbfunc2)(hp->h_name1, hp->h_name2, hp->h_value, arg);
365 }
366 return rval;
367 }
368
369 int
ht_enumerate(struct hashtab * ht,ht_callback cbfunc,void * arg)370 ht_enumerate(struct hashtab *ht, ht_callback cbfunc, void *arg)
371 {
372 struct hashent *hp;
373 struct hashenthead *hpp;
374 size_t i;
375 int rval = 0;
376
377 for (i = 0; i < ht->ht_size; i++) {
378 hpp = &ht->ht_tab[i];
379 TAILQ_FOREACH(hp, hpp, h_next)
380 rval += (*cbfunc)(hp->h_name, hp->h_value, arg);
381 }
382 return rval;
383 }
384
385 /************************************************************/
386
387 /*
388 * Type-safe wrappers.
389 */
390
391 #define DEFHASH(HT, VT) \
392 struct HT { \
393 struct hashtab imp; \
394 }; \
395 \
396 struct HT * \
397 HT##_create(void) \
398 { \
399 struct HT *tbl; \
400 \
401 tbl = ecalloc(1, sizeof(*tbl)); \
402 ht_init(&tbl->imp, 8); \
403 return tbl; \
404 } \
405 \
406 int \
407 HT##_insert(struct HT *tbl, const char *name, struct VT *val) \
408 { \
409 return ht_insert(&tbl->imp, name, val); \
410 } \
411 \
412 int \
413 HT##_replace(struct HT *tbl, const char *name, struct VT *val) \
414 { \
415 return ht_replace(&tbl->imp, name, val); \
416 } \
417 \
418 int \
419 HT##_remove(struct HT *tbl, const char *name) \
420 { \
421 return ht_remove(&tbl->imp, name); \
422 } \
423 \
424 struct VT * \
425 HT##_lookup(struct HT *tbl, const char *name) \
426 { \
427 return ht_lookup(&tbl->imp, name); \
428 } \
429 \
430 struct HT##_enumcontext { \
431 int (*func)(const char *, struct VT *, void *); \
432 void *userctx; \
433 }; \
434 \
435 static int \
436 HT##_enumerate_thunk(const char *name, void *value, void *voidctx) \
437 { \
438 struct HT##_enumcontext *ctx = voidctx; \
439 \
440 return ctx->func(name, value, ctx->userctx); \
441 } \
442 \
443 int \
444 HT##_enumerate(struct HT *tbl, \
445 int (*func)(const char *, struct VT *, void *), \
446 void *userctx) \
447 { \
448 struct HT##_enumcontext ctx; \
449 \
450 ctx.func = func; \
451 ctx.userctx = userctx; \
452 return ht_enumerate(&tbl->imp, HT##_enumerate_thunk, &ctx); \
453 }
454
455 DEFHASH(nvhash, nvlist);
456 DEFHASH(dlhash, defoptlist);
457