usr.bin/config/hash.c

   1 /*      $NetBSD: hash.c,v 1.5 2006/12/27 17:50:27 alc 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/param.h>
  48 #include <assert.h>
  49 #include <stdlib.h>
  50 #include <string.h>
  51 #include <util.h>
  52 #include "defs.h"
  53
  54 /*
  55  * Interned strings are kept in a hash table.  By making each string
  56  * unique, the program can compare strings by comparing pointers.
  57  */
  58 struct hashent {
  59         // XXXLUKEM: a SIMPLEQ might be more appropriate
  60         TAILQ_ENTRY(hashent) h_next;
  61         const char *h_name;             /* the string */
  62         u_int   h_hash;                 /* its hash value */
  63         void    *h_value;               /* other values (for name=value) */
  64 };
  65 struct hashtab {
  66         size_t  ht_size;                /* size (power of 2) */
  67         u_int   ht_mask;                /* == ht_size - 1 */
  68         u_int   ht_used;                /* number of entries used */
  69         u_int   ht_lim;                 /* when to expand */
  70         TAILQ_HEAD(hashenthead, hashent) *ht_tab;
  71 };
  72
  73 static struct hashtab strings;
  74
  75 /*
  76  * HASHFRACTION controls ht_lim, which in turn controls the average chain
  77  * length.  We allow a few entries, on average, as comparing them is usually
  78  * cheap (the h_hash values prevent a strcmp).
  79  */
  80 #define HASHFRACTION(sz) ((sz) * 3 / 2)
  81
  82 static void                     ht_expand(struct hashtab *);
  83 static void                     ht_init(struct hashtab *, size_t);
  84 static inline u_int             hash(const char *);
  85 static inline struct hashent   *newhashent(const char *, u_int);
  86
  87 /*
  88  * Initialize a new hash table.  The size must be a power of 2.
  89  */
  90 static void
  91 ht_init(struct hashtab *ht, size_t sz)
  92 {
  93         u_int n;
  94
  95         ht->ht_tab = emalloc(sz * sizeof (ht->ht_tab[0]));
  96         ht->ht_size = sz;
  97         ht->ht_mask = sz - 1;
  98         for (n = 0; n < sz; n++)
  99                 TAILQ_INIT(&ht->ht_tab[n]);
 100         ht->ht_used = 0;
 101         ht->ht_lim = HASHFRACTION(sz);
 102 }
 103
 104 /*
 105  * Expand an existing hash table.
 106  */
 107 static void
 108 ht_expand(struct hashtab *ht)
 109 {
 110         struct hashenthead *h, *oldh;
 111         struct hashent *p;
 112         u_int n, i;
 113
 114         n = ht->ht_size * 2;
 115         h = emalloc(n * sizeof *h);
 116         for (i = 0; i < n; i++)
 117                 TAILQ_INIT(&h[i]);
 118         oldh = ht->ht_tab;
 119         n--;
 120         for (i = 0; i < ht->ht_size; i++) {
 121                 while ((p = TAILQ_FIRST(&oldh[i])) != NULL) {
 122                         TAILQ_REMOVE(&oldh[i], p, h_next);
 123                                 // XXXLUKEM: really should be TAILQ_INSERT_TAIL
 124                         TAILQ_INSERT_HEAD(&h[p->h_hash & n], p, h_next);
 125                 }
 126         }
 127         free(ht->ht_tab);
 128         ht->ht_tab = h;
 129         ht->ht_mask = n;
 130         ht->ht_size = ++n;
 131         ht->ht_lim = HASHFRACTION(n);
 132 }
 133
 134 /*
 135  * Make a new hash entry, setting its h_next to NULL.
 136  * If the free list is not empty, use the first entry from there,
 137  * otherwise allocate a new entry.
 138  */
 139 static inline struct hashent *
 140 newhashent(const char *name, u_int h)
 141 {
 142         struct hashent *hp;
 143
 144         hp = ecalloc(1, sizeof(*hp));
 145
 146         hp->h_name = name;
 147         hp->h_hash = h;
 148         return (hp);
 149 }
 150
 151 /*
 152  * Hash a string.
 153  */
 154 static inline u_int
 155 hash(const char *str)
 156 {
 157         u_int h;
 158
 159         for (h = 0; *str;)
 160                 h = (h << 5) + h + *str++;
 161         return (h);
 162 }
 163
 164 void
 165 initintern(void)
 166 {
 167
 168         ht_init(&strings, 128);
 169 }
 170
 171 /*
 172  * Generate a single unique copy of the given string.  We expect this
 173  * function to be used frequently, so it should be fast.
 174  */
 175 const char *
 176 intern(const char *s)
 177 {
 178         struct hashtab *ht;
 179         struct hashent *hp;
 180         struct hashenthead *hpp;
 181         u_int h;
 182         char *p;
 183
 184         ht = &strings;
 185         h = hash(s);
 186         hpp = &ht->ht_tab[h & ht->ht_mask];
 187         TAILQ_FOREACH(hp, hpp, h_next) {
 188                 if (hp->h_hash == h && strcmp(hp->h_name, s) == 0)
 189                         return (hp->h_name);
 190         }
 191         p = estrdup(s);
 192         hp = newhashent(p, h);
 193         TAILQ_INSERT_TAIL(hpp, hp, h_next);
 194         if (++ht->ht_used > ht->ht_lim)
 195                 ht_expand(ht);
 196         return (p);
 197 }
 198
 199 struct hashtab *
 200 ht_new(void)
 201 {
 202         struct hashtab *ht;
 203
 204         ht = ecalloc(1, sizeof *ht);
 205         ht_init(ht, 8);
 206         return (ht);
 207 }
 208
 209 void
 210 ht_free(struct hashtab *ht)
 211 {
 212         size_t i;
 213         struct hashent *hp;
 214         struct hashenthead *hpp;
 215
 216         for (i = 0; i < ht->ht_size; i++) {
 217                 hpp = &ht->ht_tab[i];
 218                 while ((hp = TAILQ_FIRST(hpp)) != NULL) {
 219                         TAILQ_REMOVE(hpp, hp, h_next);
 220                         free(hp);
 221                         ht->ht_used--;
 222                 }
 223         }
 224
 225         assert(ht->ht_used == 0);
 226         free(ht->ht_tab);
 227         free(ht);
 228 }
 229
 230 /*
 231  * Insert and/or replace.
 232  */
 233 int
 234 ht_insrep(struct hashtab *ht, const char *nam, void *val, int replace)
 235 {
 236         struct hashent *hp;
 237         struct hashenthead *hpp;
 238         u_int h;
 239
 240         h = hash(nam);
 241         hpp = &ht->ht_tab[h & ht->ht_mask];
 242         TAILQ_FOREACH(hp, hpp, h_next) {
 243                 if (hp->h_name == nam) {
 244                         if (replace)
 245                                 hp->h_value = val;
 246                         return (1);
 247                 }
 248         }
 249         hp = newhashent(nam, h);
 250         TAILQ_INSERT_TAIL(hpp, hp, h_next);
 251         hp->h_value = val;
 252         if (++ht->ht_used > ht->ht_lim)
 253                 ht_expand(ht);
 254         return (0);
 255 }
 256
 257 /*
 258  * Remove.
 259  */
 260 int
 261 ht_remove(struct hashtab *ht, const char *name)
 262 {
 263         struct hashent *hp;
 264         struct hashenthead *hpp;
 265         u_int h;
 266
 267         h = hash(name);
 268         hpp = &ht->ht_tab[h & ht->ht_mask];
 269
 270         TAILQ_FOREACH(hp, hpp, h_next) {
 271                 if (hp->h_name != name)
 272                         continue;
 273                 TAILQ_REMOVE(hpp, hp, h_next);
 274
 275                 free(hp);
 276                 ht->ht_used--;
 277                 return (0);
 278         }
 279         return (1);
 280 }
 281
 282 void *
 283 ht_lookup(struct hashtab *ht, const char *nam)
 284 {
 285         struct hashent *hp;
 286         struct hashenthead *hpp;
 287         u_int h;
 288
 289         h = hash(nam);
 290         hpp = &ht->ht_tab[h & ht->ht_mask];
 291         TAILQ_FOREACH(hp, hpp, h_next)
 292                 if (hp->h_name == nam)
 293                         return (hp->h_value);
 294         return (NULL);
 295 }
 296
 297 /*
 298  * first parameter to callback is the entry name from the hash table
 299  * second parameter is the value from the hash table
 300  * third argument is passed through from the "arg" parameter to ht_enumerate()
 301  */
 302
 303 int
 304 ht_enumerate(struct hashtab *ht, ht_callback cbfunc, void *arg)
 305 {
 306         struct hashent *hp;
 307         struct hashenthead *hpp;
 308         size_t i;
 309         int rval = 0;
 310
 311         for (i = 0; i < ht->ht_size; i++) {
 312                 hpp = &ht->ht_tab[i];
 313                 TAILQ_FOREACH(hp, hpp, h_next)
 314                         rval += (*cbfunc)(hp->h_name, hp->h_value, arg);
 315         }
 316         return rval;
 317 }