1 /* $NetBSD: hash.c,v 1.12 2025/01/07 14:21:11 joe 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.12 2025/01/07 14:21:11 joe 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 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 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 * 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 * 160 newhashent(const char *name, u_int h) 161 { 162 return newhashent2(name, NULL, h); 163 } 164 165 static inline u_int 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 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 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 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 * 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 * 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 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 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 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 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 321 ht_remove(struct hashtab *ht, const char *name) 322 { 323 return ht_remove2(ht, name, NULL); 324 } 325 326 void * 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 * 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 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 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
Indexes created Sat Sep 20 22:09:52 GMT 2025