1192067Snwhitehorn/* $NetBSD: hash.c,v 1.10 2014/10/12 05:25:21 uebayasi Exp $ */ 2236098Sraj 3192067Snwhitehorn/* 4192067Snwhitehorn * Copyright (c) 1992, 1993 5192067Snwhitehorn * The Regents of the University of California. All rights reserved. 6192067Snwhitehorn * 7192067Snwhitehorn * This software was developed by the Computer Systems Engineering group 8192067Snwhitehorn * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and 9192067Snwhitehorn * contributed to Berkeley. 10192067Snwhitehorn * 11192067Snwhitehorn * All advertising materials mentioning features or use of this software 12192067Snwhitehorn * must display the following acknowledgement: 13192067Snwhitehorn * This product includes software developed by the University of 14192067Snwhitehorn * California, Lawrence Berkeley Laboratories. 15192067Snwhitehorn * 16192067Snwhitehorn * Redistribution and use in source and binary forms, with or without 17192067Snwhitehorn * modification, are permitted provided that the following conditions 18192067Snwhitehorn * are met: 19192067Snwhitehorn * 1. Redistributions of source code must retain the above copyright 20192067Snwhitehorn * notice, this list of conditions and the following disclaimer. 21192067Snwhitehorn * 2. Redistributions in binary form must reproduce the above copyright 22192067Snwhitehorn * notice, this list of conditions and the following disclaimer in the 23192067Snwhitehorn * documentation and/or other materials provided with the distribution. 24192067Snwhitehorn * 3. Neither the name of the University nor the names of its contributors 25192067Snwhitehorn * may be used to endorse or promote products derived from this software 26192067Snwhitehorn * without specific prior written permission. 27192067Snwhitehorn * 28192067Snwhitehorn * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 29192067Snwhitehorn * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 30192067Snwhitehorn * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 31192067Snwhitehorn * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 32192067Snwhitehorn * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 33192067Snwhitehorn * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 34192067Snwhitehorn * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 35192067Snwhitehorn * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 36192067Snwhitehorn * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 37192067Snwhitehorn * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 38192067Snwhitehorn * SUCH DAMAGE. 39192067Snwhitehorn * 40192067Snwhitehorn * from: @(#)hash.c 8.1 (Berkeley) 6/6/93 41192067Snwhitehorn */ 42192067Snwhitehorn 43192067Snwhitehorn#if HAVE_NBTOOL_CONFIG_H 44192067Snwhitehorn#include "nbtool_config.h" 45192067Snwhitehorn#endif 46192067Snwhitehorn 47209908Sraj#include <sys/cdefs.h> 48209908Sraj__RCSID("$NetBSD$"); 49209908Sraj 50209908Sraj#include <sys/param.h> 51209908Sraj#include <assert.h> 52192067Snwhitehorn#include <stdlib.h> 53192067Snwhitehorn#include <string.h> 54192067Snwhitehorn#include <util.h> 55192067Snwhitehorn#include "defs.h" 56192532Sraj 57192532Sraj/* 58242526Smarcel * Interned strings are kept in a hash table. By making each string 59192532Sraj * unique, the program can compare strings by comparing pointers. 60242526Smarcel */ 61242526Smarcelstruct hashent { 62242526Smarcel // XXXLUKEM: a SIMPLEQ might be more appropriate 63192532Sraj TAILQ_ENTRY(hashent) h_next; 64192532Sraj const char *h_names[2]; /* the string */ 65217523Smarcel#define h_name1 h_names[0] 66217523Smarcel#define h_name2 h_names[1] 67193492Sraj#define h_name h_name1 68192067Snwhitehorn u_int h_hash; /* its hash value */ 69192067Snwhitehorn void *h_value; /* other values (for name=value) */ 70192067Snwhitehorn}; 71192067Snwhitehornstruct hashtab { 72192067Snwhitehorn size_t ht_size; /* size (power of 2) */ 73192067Snwhitehorn size_t ht_mask; /* == ht_size - 1 */ 74192067Snwhitehorn size_t ht_used; /* number of entries used */ 75192067Snwhitehorn size_t ht_lim; /* when to expand */ 76192067Snwhitehorn TAILQ_HEAD(hashenthead, hashent) *ht_tab; 77192067Snwhitehorn}; 78236097Sraj 79212054Snwhitehornstatic struct hashtab strings; 80192067Snwhitehorn 81236325Sraj/* 82192067Snwhitehorn * HASHFRACTION controls ht_lim, which in turn controls the average chain 83192067Snwhitehorn * length. We allow a few entries, on average, as comparing them is usually 84192067Snwhitehorn * cheap (the h_hash values prevent a strcmp). 85192067Snwhitehorn */ 86192067Snwhitehorn#define HASHFRACTION(sz) ((sz) * 3 / 2) 87192067Snwhitehorn 88192067Snwhitehornstatic void ht_expand(struct hashtab *); 89192067Snwhitehornstatic void ht_init(struct hashtab *, size_t); 90236097Srajstatic inline u_int hash(u_int, const char *); 91212054Snwhitehornstatic inline u_int hash2(u_int, const char *, const char *); 92192067Snwhitehornstatic inline struct hashent *newhashent(const char *, u_int); 93192067Snwhitehorn 94192067Snwhitehorn/* 95192067Snwhitehorn * Initialize a new hash table. The size must be a power of 2. 96192067Snwhitehorn */ 97192067Snwhitehornstatic void 98192067Snwhitehornht_init(struct hashtab *ht, size_t sz) 99192067Snwhitehorn{ 100192067Snwhitehorn u_int n; 101192067Snwhitehorn 102192067Snwhitehorn ht->ht_tab = emalloc(sz * sizeof (ht->ht_tab[0])); 103192067Snwhitehorn ht->ht_size = sz; 104192067Snwhitehorn ht->ht_mask = sz - 1; 105192067Snwhitehorn for (n = 0; n < sz; n++) 106236098Sraj TAILQ_INIT(&ht->ht_tab[n]); 107236098Sraj ht->ht_used = 0; 108209908Sraj ht->ht_lim = HASHFRACTION(sz); 109192067Snwhitehorn} 110236098Sraj 111236098Sraj/* 112236098Sraj * Expand an existing hash table. 113236098Sraj */ 114236098Srajstatic void 115193492Srajht_expand(struct hashtab *ht) 116193492Sraj{ 117209908Sraj struct hashenthead *h, *oldh; 118209908Sraj struct hashent *p; 119209908Sraj size_t n, i; 120209908Sraj 121209908Sraj n = ht->ht_size * 2; 122209908Sraj h = emalloc(n * sizeof *h); 123209908Sraj for (i = 0; i < n; i++) 124209908Sraj TAILQ_INIT(&h[i]); 125209908Sraj oldh = ht->ht_tab; 126209908Sraj n--; 127209908Sraj for (i = 0; i < ht->ht_size; i++) { 128209908Sraj while ((p = TAILQ_FIRST(&oldh[i])) != NULL) { 129209908Sraj TAILQ_REMOVE(&oldh[i], p, h_next); 130209908Sraj // XXXLUKEM: really should be TAILQ_INSERT_TAIL 131209908Sraj TAILQ_INSERT_HEAD(&h[p->h_hash & n], p, h_next); 132209908Sraj } 133209908Sraj } 134192067Snwhitehorn free(ht->ht_tab); 135192067Snwhitehorn ht->ht_tab = h; 136192067Snwhitehorn ht->ht_mask = n; 137192067Snwhitehorn ht->ht_size = ++n; 138192067Snwhitehorn ht->ht_lim = HASHFRACTION(n); 139192067Snwhitehorn} 140192067Snwhitehorn 141192067Snwhitehorn/* 142192067Snwhitehorn * Make a new hash entry, setting its h_next to NULL. 143192067Snwhitehorn * If the free list is not empty, use the first entry from there, 144209908Sraj * otherwise allocate a new entry. 145209908Sraj */ 146192067Snwhitehornstatic inline struct hashent * 147209908Srajnewhashent2(const char *name1, const char *name2, u_int h) 148209908Sraj{ 149236325Sraj struct hashent *hp; 150236325Sraj 151209908Sraj hp = ecalloc(1, sizeof(*hp)); 152209908Sraj 153209908Sraj hp->h_name1 = name1; 154209908Sraj hp->h_name2 = name2; 155209908Sraj hp->h_hash = h; 156209908Sraj return (hp); 157192067Snwhitehorn} 158192067Snwhitehorn 159192067Snwhitehornstatic inline struct hashent * 160192067Snwhitehornnewhashent(const char *name, u_int h) 161192067Snwhitehorn{ 162192067Snwhitehorn return newhashent2(name, NULL, h); 163192067Snwhitehorn} 164192067Snwhitehorn 165192067Snwhitehornstatic inline u_int 166192067Snwhitehornhv(u_int h, char c) 167192067Snwhitehorn{ 168192067Snwhitehorn return (h << 5) + h + (unsigned char)c; 169192067Snwhitehorn} 170217523Smarcel 171209908Sraj/* 172209908Sraj * Hash a string. 173192067Snwhitehorn */ 174224618Smarcelstatic inline u_int 175224611Smarcelhash(u_int h, const char *str) 176224611Smarcel{ 177224611Smarcel 178224611Smarcel while (str && *str) 179224618Smarcel h = hv(h, *str++); 180224611Smarcel return (h); 181224618Smarcel} 182222327Smarcel 183222327Smarcel#define HASH2DELIM ' ' 184217523Smarcel 185228201Sjchandrastatic inline u_int 186209908Srajhash2(u_int h, const char *str1, const char *str2) 187209908Sraj{ 188209908Sraj 189209908Sraj h = hash(h, str1); 190209908Sraj h = hv(h, HASH2DELIM); 191217523Smarcel h = hash(h, str2); 192209908Sraj return (h); 193209908Sraj} 194209908Sraj 195217523Smarcelvoid 196192067Snwhitehorninitintern(void) 197192067Snwhitehorn{ 198192067Snwhitehorn 199192067Snwhitehorn ht_init(&strings, 128); 200217523Smarcel} 201217523Smarcel 202217523Smarcel/* 203209908Sraj * Generate a single unique copy of the given string. We expect this 204192067Snwhitehorn * function to be used frequently, so it should be fast. 205192067Snwhitehorn */ 206192067Snwhitehornconst char * 207192067Snwhitehornintern(const char *s) 208192067Snwhitehorn{ 209192067Snwhitehorn struct hashtab *ht; 210192067Snwhitehorn struct hashent *hp; 211192067Snwhitehorn struct hashenthead *hpp; 212192067Snwhitehorn u_int h; 213192067Snwhitehorn char *p; 214192067Snwhitehorn 215192067Snwhitehorn ht = &strings; 216192067Snwhitehorn h = hash2(0, s, NULL); 217192067Snwhitehorn hpp = &ht->ht_tab[h & ht->ht_mask]; 218192067Snwhitehorn TAILQ_FOREACH(hp, hpp, h_next) { 219192067Snwhitehorn if (hp->h_hash == h && strcmp(hp->h_name, s) == 0) 220192067Snwhitehorn return (hp->h_name); 221192067Snwhitehorn } 222192067Snwhitehorn p = estrdup(s); 223192067Snwhitehorn hp = newhashent(p, h); 224192067Snwhitehorn TAILQ_INSERT_TAIL(hpp, hp, h_next); 225192067Snwhitehorn if (++ht->ht_used > ht->ht_lim) 226192067Snwhitehorn ht_expand(ht); 227192067Snwhitehorn return (p); 228193492Sraj} 229192067Snwhitehorn 230192067Snwhitehornstruct hashtab * 231192067Snwhitehornht_new(void) 232192067Snwhitehorn{ 233192067Snwhitehorn struct hashtab *ht; 234192067Snwhitehorn 235192067Snwhitehorn ht = ecalloc(1, sizeof *ht); 236192067Snwhitehorn ht_init(ht, 8); 237192067Snwhitehorn return (ht); 238192067Snwhitehorn} 239192067Snwhitehorn 240192067Snwhitehornvoid 241192067Snwhitehornht_free(struct hashtab *ht) 242192067Snwhitehorn{ 243192067Snwhitehorn size_t i; 244192067Snwhitehorn struct hashent *hp; 245192067Snwhitehorn struct hashenthead *hpp; 246192067Snwhitehorn 247192067Snwhitehorn for (i = 0; i < ht->ht_size; i++) { 248192067Snwhitehorn hpp = &ht->ht_tab[i]; 249192067Snwhitehorn while ((hp = TAILQ_FIRST(hpp)) != NULL) { 250192067Snwhitehorn TAILQ_REMOVE(hpp, hp, h_next); 251192067Snwhitehorn free(hp); 252192532Sraj ht->ht_used--; 253242526Smarcel } 254192532Sraj } 255242526Smarcel 256192067Snwhitehorn assert(ht->ht_used == 0); 257192532Sraj free(ht->ht_tab); 258222813Sattilio free(ht); 259235932Smarcel} 260235932Smarcel 261192532Sraj/* 262192532Sraj * Insert and/or replace. 263192532Sraj */ 264192532Srajint 265192532Srajht_insrep2(struct hashtab *ht, const char *nam1, const char *nam2, void *val, int replace) 266242526Smarcel{ 267242526Smarcel struct hashent *hp; 268242526Smarcel struct hashenthead *hpp; 269242526Smarcel u_int h; 270242526Smarcel 271242526Smarcel h = hash2(0, nam1, nam2); 272242526Smarcel hpp = &ht->ht_tab[h & ht->ht_mask]; 273242526Smarcel TAILQ_FOREACH(hp, hpp, h_next) { 274242526Smarcel if (hp->h_name1 == nam1 && 275242526Smarcel hp->h_name2 == nam2) { 276242526Smarcel if (replace) 277242526Smarcel hp->h_value = val; 278242526Smarcel return (1); 279242526Smarcel } 280192532Sraj } 281192532Sraj hp = newhashent2(nam1, nam2, h); 282192532Sraj TAILQ_INSERT_TAIL(hpp, hp, h_next); 283242526Smarcel hp->h_value = val; 284242526Smarcel if (++ht->ht_used > ht->ht_lim) 285242526Smarcel ht_expand(ht); 286242526Smarcel return (0); 287242526Smarcel} 288242526Smarcel 289192532Srajint 290242526Smarcelht_insrep(struct hashtab *ht, const char *nam, void *val, int replace) 291242526Smarcel{ 292242526Smarcel return ht_insrep2(ht, nam, NULL, val, replace); 293192532Sraj} 294192532Sraj 295192532Sraj/* 296222813Sattilio * Remove. 297192532Sraj */ 298192532Srajint 299192532Srajht_remove2(struct hashtab *ht, const char *name1, const char *name2) 300192532Sraj{ 301192532Sraj struct hashent *hp; 302192532Sraj struct hashenthead *hpp; 303192532Sraj u_int h; 304235932Smarcel 305235932Smarcel h = hash2(0, name1, name2); 306235932Smarcel hpp = &ht->ht_tab[h & ht->ht_mask]; 307235932Smarcel 308235932Smarcel TAILQ_FOREACH(hp, hpp, h_next) { 309235932Smarcel if (hp->h_name1 != name1 || hp->h_name2 != name2) 310242526Smarcel continue; 311235932Smarcel TAILQ_REMOVE(hpp, hp, h_next); 312235932Smarcel 313242526Smarcel free(hp); 314192532Sraj ht->ht_used--; 315192532Sraj return (0); 316192067Snwhitehorn } 317192067Snwhitehorn return (1); 318192532Sraj} 319192067Snwhitehorn 320212054Snwhitehornint 321212054Snwhitehornht_remove(struct hashtab *ht, const char *name) 322236097Sraj{ 323212054Snwhitehorn return ht_remove2(ht, name, NULL); 324212054Snwhitehorn} 325222392Smarcel 326222392Smarcelvoid * 327222392Smarcelht_lookup2(struct hashtab *ht, const char *nam1, const char *nam2) 328222392Smarcel{ 329222392Smarcel struct hashent *hp; 330222392Smarcel struct hashenthead *hpp; 331212054Snwhitehorn u_int h; 332222392Smarcel 333222392Smarcel h = hash2(0, nam1, nam2); 334222392Smarcel hpp = &ht->ht_tab[h & ht->ht_mask]; 335212054Snwhitehorn TAILQ_FOREACH(hp, hpp, h_next) 336222392Smarcel if (hp->h_name == nam1) 337222392Smarcel return (hp->h_value); 338212054Snwhitehorn return (NULL); 339222392Smarcel} 340222392Smarcel 341222392Smarcelvoid * 342212054Snwhitehornht_lookup(struct hashtab *ht, const char *nam) 343236097Sraj{ 344236097Sraj return ht_lookup2(ht, nam, NULL); 345212054Snwhitehorn} 346212054Snwhitehorn 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 353int 354ht_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 369int 370ht_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 455DEFHASH(nvhash, nvlist); 456DEFHASH(dlhash, defoptlist); 457