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