1 /* $OpenBSD: hash.c,v 1.9 2000/11/15 01:49:52 angelos Exp $ */ 2 /* $NetBSD: hash.c,v 1.4 1996/11/07 22:59:43 gwr Exp $ */ 3 4 /* 5 * Copyright (c) 1992, 1993 6 * The Regents of the University of California. All rights reserved. 7 * 8 * This software was developed by the Computer Systems Engineering group 9 * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and 10 * contributed to Berkeley. 11 * 12 * All advertising materials mentioning features or use of this software 13 * must display the following acknowledgement: 14 * This product includes software developed by the University of 15 * California, Lawrence Berkeley Laboratories. 16 * 17 * Redistribution and use in source and binary forms, with or without 18 * modification, are permitted provided that the following conditions 19 * are met: 20 * 1. Redistributions of source code must retain the above copyright 21 * notice, this list of conditions and the following disclaimer. 22 * 2. Redistributions in binary form must reproduce the above copyright 23 * notice, this list of conditions and the following disclaimer in the 24 * documentation and/or other materials provided with the distribution. 25 * 3. All advertising materials mentioning features or use of this software 26 * must display the following acknowledgement: 27 * This product includes software developed by the University of 28 * California, Berkeley and its contributors. 29 * 4. Neither the name of the University nor the names of its contributors 30 * may be used to endorse or promote products derived from this software 31 * without specific prior written permission. 32 * 33 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 34 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 35 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 36 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 37 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 38 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 39 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 40 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 41 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 42 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 43 * SUCH DAMAGE. 44 * 45 * from: @(#)hash.c 8.1 (Berkeley) 6/6/93 46 */ 47 48 #include <sys/param.h> 49 #include <stdlib.h> 50 #include <string.h> 51 #include "config.h" 52 53 /* 54 * These are really for MAKE_BOOTSTRAP but harmless. 55 * XXX - Why not just use malloc in here, anyway? 56 */ 57 #ifndef ALIGNBYTES 58 #define ALIGNBYTES 3 59 #endif 60 #ifndef ALIGN 61 #define ALIGN(p) (((long)(p) + ALIGNBYTES) &~ ALIGNBYTES) 62 #endif 63 64 /* 65 * Interned strings are kept in a hash table. By making each string 66 * unique, the program can compare strings by comparing pointers. 67 */ 68 struct hashent { 69 struct hashent *h_next; /* hash buckets are chained */ 70 const char *h_name; /* the string */ 71 u_int h_hash; /* its hash value */ 72 void *h_value; /* other values (for name=value) */ 73 }; 74 struct hashtab { 75 size_t ht_size; /* size (power of 2) */ 76 u_int ht_mask; /* == ht_size - 1 */ 77 u_int ht_used; /* number of entries used */ 78 u_int ht_lim; /* when to expand */ 79 struct hashent **ht_tab; /* base of table */ 80 }; 81 static struct hashtab strings; 82 83 /* 84 * HASHFRACTION controls ht_lim, which in turn controls the average chain 85 * length. We allow a few entries, on average, as comparing them is usually 86 * cheap (the h_hash values prevent a strcmp). 87 */ 88 #define HASHFRACTION(sz) ((sz) * 3 / 2) 89 90 /* round up to next multiple of y, where y is a power of 2 */ 91 #define ROUND(x, y) (((x) + (y) - 1) & ~((y) - 1)) 92 93 /* 94 * Allocate space that will never be freed. 95 */ 96 static void * 97 poolalloc(size) 98 size_t size; 99 { 100 register char *p; 101 register size_t alloc; 102 static char *pool; 103 static size_t nleft; 104 105 if (nleft < size) { 106 /* 107 * Compute a `good' size to allocate via malloc. 108 * 16384 is a guess at a good page size for malloc; 109 * 32 is a guess at malloc's overhead. 110 */ 111 alloc = ROUND(size + 32, 16384) - 32; 112 p = emalloc(alloc); 113 nleft = alloc - size; 114 } else { 115 p = pool; 116 nleft -= size; 117 } 118 pool = p + size; 119 return (p); 120 } 121 122 /* 123 * Initialize a new hash table. The size must be a power of 2. 124 */ 125 static void 126 ht_init(ht, sz) 127 register struct hashtab *ht; 128 size_t sz; 129 { 130 register struct hashent **h; 131 register u_int n; 132 133 h = emalloc(sz * sizeof *h); 134 ht->ht_tab = h; 135 ht->ht_size = sz; 136 ht->ht_mask = sz - 1; 137 for (n = 0; n < sz; n++) 138 *h++ = NULL; 139 ht->ht_used = 0; 140 ht->ht_lim = HASHFRACTION(sz); 141 } 142 143 /* 144 * Expand an existing hash table. 145 */ 146 static void 147 ht_expand(ht) 148 register struct hashtab *ht; 149 { 150 register struct hashent *p, **h, **oldh, *q; 151 register u_int n, i; 152 153 n = ht->ht_size * 2; 154 h = emalloc(n * sizeof *h); 155 for (i = 0; i < n; i++) 156 h[i] = NULL; 157 oldh = ht->ht_tab; 158 n--; 159 for (i = ht->ht_size; i != 0; i--) { 160 for (p = *oldh++; p != NULL; p = q) { 161 q = p->h_next; 162 p->h_next = h[p->h_hash & n]; 163 h[p->h_hash & n] = p; 164 } 165 } 166 free(ht->ht_tab); 167 ht->ht_tab = h; 168 ht->ht_mask = n; 169 ht->ht_size = ++n; 170 ht->ht_lim = HASHFRACTION(n); 171 } 172 173 /* 174 * Make a new hash entry, setting its h_next to NULL. 175 */ 176 static inline struct hashent * 177 newhashent(name, h) 178 const char *name; 179 u_int h; 180 { 181 register struct hashent *hp; 182 register char *m; 183 184 m = poolalloc(sizeof(*hp) + ALIGNBYTES); 185 hp = (struct hashent *)ALIGN(m); 186 hp->h_name = name; 187 hp->h_hash = h; 188 hp->h_next = NULL; 189 return (hp); 190 } 191 192 /* 193 * Hash a string. 194 */ 195 static inline u_int 196 hash(str) 197 register const char *str; 198 { 199 register u_int h; 200 201 for (h = 0; *str;) 202 h = (h << 5) + h + *str++; 203 return (h); 204 } 205 206 void 207 initintern() 208 { 209 210 ht_init(&strings, 128); 211 } 212 213 /* 214 * Generate a single unique copy of the given string. We expect this 215 * function to be used frequently, so it should be fast. 216 */ 217 const char * 218 intern(s) 219 register const char *s; 220 { 221 register struct hashtab *ht; 222 register struct hashent *hp, **hpp; 223 register u_int h; 224 register char *p; 225 register size_t l; 226 227 ht = &strings; 228 h = hash(s); 229 hpp = &ht->ht_tab[h & ht->ht_mask]; 230 for (; (hp = *hpp) != NULL; hpp = &hp->h_next) 231 if (hp->h_hash == h && strcmp(hp->h_name, s) == 0) 232 return (hp->h_name); 233 l = strlen(s) + 1; 234 p = poolalloc(l); 235 bcopy(s, p, l); 236 *hpp = newhashent(p, h); 237 if (++ht->ht_used > ht->ht_lim) 238 ht_expand(ht); 239 return (p); 240 } 241 242 struct hashtab * 243 ht_new() 244 { 245 register struct hashtab *ht; 246 247 ht = emalloc(sizeof *ht); 248 ht_init(ht, 8); 249 return (ht); 250 } 251 252 /* 253 * Remove. 254 */ 255 int 256 ht_remove(ht, nam) 257 register struct hashtab *ht; 258 register const char *nam; 259 { 260 register struct hashent *hp, *thp; 261 register u_int h; 262 263 h = hash(nam); 264 hp = ht->ht_tab[h & ht->ht_mask]; 265 while (hp && hp->h_name == nam) { 266 ht->ht_tab[h & ht->ht_mask] = hp->h_next; 267 /* XXX free hp ? */ 268 hp = ht->ht_tab[h & ht->ht_mask]; 269 } 270 271 if ((hp = ht->ht_tab[h & ht->ht_mask]) == NULL) 272 return (0); 273 274 for (thp = hp->h_next; thp != NULL; thp = hp->h_next) { 275 if (thp->h_name == nam) { 276 hp->h_next = thp->h_next; 277 /* XXX free thp ? */ 278 } else 279 hp = thp; 280 } 281 282 return (0); 283 } 284 285 /* 286 * Insert and/or replace. 287 */ 288 int 289 ht_insrep(ht, nam, val, replace) 290 register struct hashtab *ht; 291 register const char *nam; 292 void *val; 293 int replace; 294 { 295 register struct hashent *hp, **hpp; 296 register u_int h; 297 298 h = hash(nam); 299 hpp = &ht->ht_tab[h & ht->ht_mask]; 300 for (; (hp = *hpp) != NULL; hpp = &hp->h_next) { 301 if (hp->h_name == nam) { 302 if (replace) 303 hp->h_value = val; 304 return (1); 305 } 306 } 307 *hpp = hp = newhashent(nam, h); 308 hp->h_value = val; 309 if (++ht->ht_used > ht->ht_lim) 310 ht_expand(ht); 311 return (0); 312 } 313 314 void * 315 ht_lookup(ht, nam) 316 register struct hashtab *ht; 317 register const char *nam; 318 { 319 register struct hashent *hp, **hpp; 320 register u_int h; 321 322 h = hash(nam); 323 hpp = &ht->ht_tab[h & ht->ht_mask]; 324 for (; (hp = *hpp) != NULL; hpp = &hp->h_next) 325 if (hp->h_name == nam) 326 return (hp->h_value); 327 return (NULL); 328 } 329