1 /* $OpenBSD: hash.c,v 1.18 2015/01/17 07:37:14 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> /* ALIGNBYTES */ 45 46 #include <stdlib.h> 47 #include <string.h> 48 49 #include "config.h" 50 51 /* 52 * Interned strings are kept in a hash table. By making each string 53 * unique, the program can compare strings by comparing pointers. 54 */ 55 struct hashent { 56 struct hashent *h_next; /* hash buckets are chained */ 57 const char *h_name; /* the string */ 58 u_int h_hash; /* its hash value */ 59 void *h_value; /* other values (for name=value) */ 60 }; 61 struct hashtab { 62 size_t ht_size; /* size (power of 2) */ 63 u_int ht_mask; /* == ht_size - 1 */ 64 u_int ht_used; /* number of entries used */ 65 u_int ht_lim; /* when to expand */ 66 struct hashent **ht_tab; /* base of table */ 67 }; 68 static struct hashtab strings; 69 70 /* 71 * HASHFRACTION controls ht_lim, which in turn controls the average chain 72 * length. We allow a few entries, on average, as comparing them is usually 73 * cheap (the h_hash values prevent a strcmp). 74 */ 75 #define HASHFRACTION(sz) ((sz) * 3 / 2) 76 77 /* round up to next multiple of y, where y is a power of 2 */ 78 #define ROUND(x, y) (((x) + (y) - 1) & ~((y) - 1)) 79 80 static void *poolalloc(size_t); 81 static void ht_init(struct hashtab *, size_t); 82 static void ht_expand(struct hashtab *); 83 /* 84 * Allocate space that will never be freed. 85 */ 86 static void * 87 poolalloc(size_t size) 88 { 89 char *p; 90 size_t alloc; 91 static char *pool; 92 static size_t nleft; 93 94 if (nleft < size) { 95 /* 96 * Compute a `good' size to allocate via malloc. 97 * 16384 is a guess at a good page size for malloc; 98 * 32 is a guess at malloc's overhead. 99 */ 100 alloc = ROUND(size + 32, 16384) - 32; 101 p = emalloc(alloc); 102 nleft = alloc - size; 103 } else { 104 p = pool; 105 nleft -= size; 106 } 107 pool = p + size; 108 return (p); 109 } 110 111 /* 112 * Initialize a new hash table. The size must be a power of 2. 113 */ 114 static void 115 ht_init(struct hashtab *ht, size_t sz) 116 { 117 struct hashent **h; 118 u_int n; 119 120 h = ereallocarray(NULL, sz, sizeof *h); 121 ht->ht_tab = h; 122 ht->ht_size = sz; 123 ht->ht_mask = sz - 1; 124 for (n = 0; n < sz; n++) 125 *h++ = NULL; 126 ht->ht_used = 0; 127 ht->ht_lim = HASHFRACTION(sz); 128 } 129 130 /* 131 * Expand an existing hash table. 132 */ 133 static void 134 ht_expand(struct hashtab *ht) 135 { 136 struct hashent *p, **h, **oldh, *q; 137 u_int n, i; 138 139 n = ht->ht_size * 2; 140 h = ecalloc(n, sizeof *h); 141 oldh = ht->ht_tab; 142 n--; 143 for (i = ht->ht_size; i != 0; i--) { 144 for (p = *oldh++; p != NULL; p = q) { 145 q = p->h_next; 146 p->h_next = h[p->h_hash & n]; 147 h[p->h_hash & n] = p; 148 } 149 } 150 free(ht->ht_tab); 151 ht->ht_tab = h; 152 ht->ht_mask = n; 153 ht->ht_size = ++n; 154 ht->ht_lim = HASHFRACTION(n); 155 } 156 157 /* 158 * Make a new hash entry, setting its h_next to NULL. 159 */ 160 static __inline struct hashent * 161 newhashent(const char *name, u_int h) 162 { 163 struct hashent *hp; 164 char *m; 165 166 m = poolalloc(sizeof(*hp) + ALIGNBYTES); 167 hp = (struct hashent *)ALIGN(m); 168 hp->h_name = name; 169 hp->h_hash = h; 170 hp->h_next = NULL; 171 return (hp); 172 } 173 174 /* 175 * Hash a string. 176 */ 177 static __inline u_int 178 hash(const char *str) 179 { 180 u_int h; 181 182 for (h = 0; *str;) 183 h = (h << 5) + h + *str++; 184 return (h); 185 } 186 187 void 188 initintern(void) 189 { 190 191 ht_init(&strings, 128); 192 } 193 194 /* 195 * Generate a single unique copy of the given string. We expect this 196 * function to be used frequently, so it should be fast. 197 */ 198 const char * 199 intern(const char *s) 200 { 201 struct hashtab *ht; 202 struct hashent *hp, **hpp; 203 u_int h; 204 char *p; 205 size_t l; 206 207 ht = &strings; 208 h = hash(s); 209 hpp = &ht->ht_tab[h & ht->ht_mask]; 210 for (; (hp = *hpp) != NULL; hpp = &hp->h_next) 211 if (hp->h_hash == h && strcmp(hp->h_name, s) == 0) 212 return (hp->h_name); 213 l = strlen(s) + 1; 214 p = poolalloc(l); 215 bcopy(s, p, l); 216 *hpp = newhashent(p, h); 217 if (++ht->ht_used > ht->ht_lim) 218 ht_expand(ht); 219 return (p); 220 } 221 222 struct hashtab * 223 ht_new(void) 224 { 225 struct hashtab *ht; 226 227 ht = emalloc(sizeof *ht); 228 ht_init(ht, 8); 229 return (ht); 230 } 231 232 /* 233 * Remove. 234 */ 235 int 236 ht_remove(struct hashtab *ht, const char *nam) 237 { 238 struct hashent *hp, *thp; 239 u_int h; 240 241 h = hash(nam); 242 hp = ht->ht_tab[h & ht->ht_mask]; 243 while (hp && hp->h_name == nam) { 244 ht->ht_tab[h & ht->ht_mask] = hp->h_next; 245 /* XXX free hp ? */ 246 hp = ht->ht_tab[h & ht->ht_mask]; 247 } 248 249 if ((hp = ht->ht_tab[h & ht->ht_mask]) == NULL) 250 return (0); 251 252 for (thp = hp->h_next; thp != NULL; thp = hp->h_next) { 253 if (thp->h_name == nam) { 254 hp->h_next = thp->h_next; 255 /* XXX free thp ? */ 256 } else 257 hp = thp; 258 } 259 260 return (0); 261 } 262 263 /* 264 * Insert and/or replace. 265 */ 266 int 267 ht_insrep(struct hashtab *ht, const char *nam, void *val, int replace) 268 { 269 struct hashent *hp, **hpp; 270 u_int h; 271 272 h = hash(nam); 273 hpp = &ht->ht_tab[h & ht->ht_mask]; 274 for (; (hp = *hpp) != NULL; hpp = &hp->h_next) { 275 if (hp->h_name == nam) { 276 if (replace) 277 hp->h_value = val; 278 return (1); 279 } 280 } 281 *hpp = hp = newhashent(nam, h); 282 hp->h_value = val; 283 if (++ht->ht_used > ht->ht_lim) 284 ht_expand(ht); 285 return (0); 286 } 287 288 void * 289 ht_lookup(struct hashtab *ht, const char *nam) 290 { 291 struct hashent *hp, **hpp; 292 u_int h; 293 294 h = hash(nam); 295 hpp = &ht->ht_tab[h & ht->ht_mask]; 296 for (; (hp = *hpp) != NULL; hpp = &hp->h_next) 297 if (hp->h_name == nam) 298 return (hp->h_value); 299 return (NULL); 300 } 301