1 /* $OpenBSD: hash.c,v 1.19 2021/11/28 19:26:03 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/types.h> 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 ht_init(struct hashtab *, size_t); 81 static void ht_expand(struct hashtab *); 82 83 /* 84 * Initialize a new hash table. The size must be a power of 2. 85 */ 86 static void 87 ht_init(struct hashtab *ht, size_t sz) 88 { 89 struct hashent **h; 90 u_int n; 91 92 h = ereallocarray(NULL, sz, sizeof *h); 93 ht->ht_tab = h; 94 ht->ht_size = sz; 95 ht->ht_mask = sz - 1; 96 for (n = 0; n < sz; n++) 97 *h++ = NULL; 98 ht->ht_used = 0; 99 ht->ht_lim = HASHFRACTION(sz); 100 } 101 102 /* 103 * Expand an existing hash table. 104 */ 105 static void 106 ht_expand(struct hashtab *ht) 107 { 108 struct hashent *p, **h, **oldh, *q; 109 u_int n, i; 110 111 n = ht->ht_size * 2; 112 h = ecalloc(n, sizeof *h); 113 oldh = ht->ht_tab; 114 n--; 115 for (i = ht->ht_size; i != 0; i--) { 116 for (p = *oldh++; p != NULL; p = q) { 117 q = p->h_next; 118 p->h_next = h[p->h_hash & n]; 119 h[p->h_hash & n] = p; 120 } 121 } 122 free(ht->ht_tab); 123 ht->ht_tab = h; 124 ht->ht_mask = n; 125 ht->ht_size = ++n; 126 ht->ht_lim = HASHFRACTION(n); 127 } 128 129 /* 130 * Make a new hash entry, setting its h_next to NULL. 131 */ 132 static __inline struct hashent * 133 newhashent(const char *name, u_int h) 134 { 135 struct hashent *hp; 136 137 hp = emalloc(sizeof(*hp)); 138 hp->h_name = name; 139 hp->h_hash = h; 140 hp->h_next = NULL; 141 return (hp); 142 } 143 144 /* 145 * Hash a string. 146 */ 147 static __inline u_int 148 hash(const char *str) 149 { 150 u_int h; 151 152 for (h = 0; *str;) 153 h = (h << 5) + h + *str++; 154 return (h); 155 } 156 157 void 158 initintern(void) 159 { 160 161 ht_init(&strings, 128); 162 } 163 164 /* 165 * Generate a single unique copy of the given string. We expect this 166 * function to be used frequently, so it should be fast. 167 */ 168 const char * 169 intern(const char *s) 170 { 171 struct hashtab *ht; 172 struct hashent *hp, **hpp; 173 u_int h; 174 char *p; 175 size_t l; 176 177 ht = &strings; 178 h = hash(s); 179 hpp = &ht->ht_tab[h & ht->ht_mask]; 180 for (; (hp = *hpp) != NULL; hpp = &hp->h_next) 181 if (hp->h_hash == h && strcmp(hp->h_name, s) == 0) 182 return (hp->h_name); 183 l = strlen(s) + 1; 184 p = malloc(l); 185 bcopy(s, p, l); 186 *hpp = newhashent(p, h); 187 if (++ht->ht_used > ht->ht_lim) 188 ht_expand(ht); 189 return (p); 190 } 191 192 struct hashtab * 193 ht_new(void) 194 { 195 struct hashtab *ht; 196 197 ht = emalloc(sizeof *ht); 198 ht_init(ht, 8); 199 return (ht); 200 } 201 202 /* 203 * Remove. 204 */ 205 int 206 ht_remove(struct hashtab *ht, const char *nam) 207 { 208 struct hashent *hp, *thp; 209 u_int h; 210 211 h = hash(nam); 212 hp = ht->ht_tab[h & ht->ht_mask]; 213 while (hp && hp->h_name == nam) { 214 ht->ht_tab[h & ht->ht_mask] = hp->h_next; 215 /* XXX free hp ? */ 216 hp = ht->ht_tab[h & ht->ht_mask]; 217 } 218 219 if ((hp = ht->ht_tab[h & ht->ht_mask]) == NULL) 220 return (0); 221 222 for (thp = hp->h_next; thp != NULL; thp = hp->h_next) { 223 if (thp->h_name == nam) { 224 hp->h_next = thp->h_next; 225 /* XXX free thp ? */ 226 } else 227 hp = thp; 228 } 229 230 return (0); 231 } 232 233 /* 234 * Insert and/or replace. 235 */ 236 int 237 ht_insrep(struct hashtab *ht, const char *nam, void *val, int replace) 238 { 239 struct hashent *hp, **hpp; 240 u_int h; 241 242 h = hash(nam); 243 hpp = &ht->ht_tab[h & ht->ht_mask]; 244 for (; (hp = *hpp) != NULL; hpp = &hp->h_next) { 245 if (hp->h_name == nam) { 246 if (replace) 247 hp->h_value = val; 248 return (1); 249 } 250 } 251 *hpp = hp = newhashent(nam, h); 252 hp->h_value = val; 253 if (++ht->ht_used > ht->ht_lim) 254 ht_expand(ht); 255 return (0); 256 } 257 258 void * 259 ht_lookup(struct hashtab *ht, const char *nam) 260 { 261 struct hashent *hp, **hpp; 262 u_int h; 263 264 h = hash(nam); 265 hpp = &ht->ht_tab[h & ht->ht_mask]; 266 for (; (hp = *hpp) != NULL; hpp = &hp->h_next) 267 if (hp->h_name == nam) 268 return (hp->h_value); 269 return (NULL); 270 } 271