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