1 /* 2 * Copyright (c) 1992, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * This software was developed by the Computer Systems Engineering group 6 * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and 7 * contributed to Berkeley. 8 * 9 * All advertising materials mentioning features or use of this software 10 * must display the following acknowledgement: 11 * This product includes software developed by the University of 12 * California, Lawrence Berkeley Laboratories. 13 * 14 * %sccs.include.redist.c% 15 * 16 * @(#)hash.c 8.1 (Berkeley) 06/06/93 17 */ 18 19 #include <sys/param.h> 20 #include <stdlib.h> 21 #include <string.h> 22 #include "config.h" 23 24 /* 25 * Interned strings are kept in a hash table. By making each string 26 * unique, the program can compare strings by comparing pointers. 27 */ 28 struct hashent { 29 struct hashent *h_next; /* hash buckets are chained */ 30 const char *h_name; /* the string */ 31 u_int h_hash; /* its hash value */ 32 void *h_value; /* other values (for name=value) */ 33 }; 34 struct hashtab { 35 size_t ht_size; /* size (power of 2) */ 36 u_int ht_mask; /* == ht_size - 1 */ 37 u_int ht_used; /* number of entries used */ 38 u_int ht_lim; /* when to expand */ 39 struct hashent **ht_tab; /* base of table */ 40 }; 41 static struct hashtab strings; 42 43 /* 44 * HASHFRACTION controls ht_lim, which in turn controls the average chain 45 * length. We allow a few entries, on average, as comparing them is usually 46 * cheap (the h_hash values prevent a strcmp). 47 */ 48 #define HASHFRACTION(sz) ((sz) * 3 / 2) 49 50 /* round up to next multiple of y, where y is a power of 2 */ 51 #define ROUND(x, y) (((x) + (y) - 1) & ~((y) - 1)) 52 53 /* 54 * Allocate space that will never be freed. 55 */ 56 static void * 57 poolalloc(size) 58 size_t size; 59 { 60 register char *p; 61 register size_t alloc; 62 static char *pool; 63 static size_t nleft; 64 65 if (nleft < size) { 66 /* 67 * Compute a `good' size to allocate via malloc. 68 * 16384 is a guess at a good page size for malloc; 69 * 32 is a guess at malloc's overhead. 70 */ 71 alloc = ROUND(size + 32, 16384) - 32; 72 p = emalloc(alloc); 73 nleft = alloc - size; 74 } else { 75 p = pool; 76 nleft -= size; 77 } 78 pool = p + size; 79 return (p); 80 } 81 82 /* 83 * Initialize a new hash table. The size must be a power of 2. 84 */ 85 static void 86 ht_init(ht, sz) 87 register struct hashtab *ht; 88 size_t sz; 89 { 90 register struct hashent **h; 91 register u_int n; 92 93 h = emalloc(sz * sizeof *h); 94 ht->ht_tab = h; 95 ht->ht_size = sz; 96 ht->ht_mask = sz - 1; 97 for (n = 0; n < sz; n++) 98 *h++ = NULL; 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(ht) 108 register struct hashtab *ht; 109 { 110 register struct hashent *p, **h, **oldh, *q; 111 register 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 h[i] = NULL; 117 oldh = ht->ht_tab; 118 n--; 119 for (i = ht->ht_size; i != 0; i--) { 120 for (p = *oldh++; p != NULL; p = q) { 121 q = p->h_next; 122 p->h_next = h[p->h_hash & n]; 123 h[p->h_hash & n] = p; 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 */ 136 static inline struct hashent * 137 newhashent(name, h) 138 const char *name; 139 u_int h; 140 { 141 register struct hashent *hp; 142 register char *m; 143 144 m = poolalloc(sizeof(*hp) + ALIGNBYTES); 145 hp = (struct hashent *)ALIGN(m); 146 hp->h_name = name; 147 hp->h_hash = h; 148 hp->h_next = NULL; 149 return (hp); 150 } 151 152 /* 153 * Hash a string. 154 */ 155 static inline u_int 156 hash(str) 157 register const char *str; 158 { 159 register u_int h; 160 161 for (h = 0; *str;) 162 h = (h << 5) + h + *str++; 163 return (h); 164 } 165 166 void 167 initintern() 168 { 169 170 ht_init(&strings, 128); 171 } 172 173 /* 174 * Generate a single unique copy of the given string. We expect this 175 * function to be used frequently, so it should be fast. 176 */ 177 const char * 178 intern(s) 179 register const char *s; 180 { 181 register struct hashtab *ht; 182 register struct hashent *hp, **hpp; 183 register u_int h; 184 register char *p; 185 register size_t l; 186 187 ht = &strings; 188 h = hash(s); 189 hpp = &ht->ht_tab[h & ht->ht_mask]; 190 for (; (hp = *hpp) != NULL; hpp = &hp->h_next) 191 if (hp->h_hash == h && strcmp(hp->h_name, s) == 0) 192 return (hp->h_name); 193 l = strlen(s) + 1; 194 p = poolalloc(l); 195 bcopy(s, p, l); 196 *hpp = newhashent(p, h); 197 if (++ht->ht_used > ht->ht_lim) 198 ht_expand(ht); 199 return (p); 200 } 201 202 struct hashtab * 203 ht_new() 204 { 205 register struct hashtab *ht; 206 207 ht = emalloc(sizeof *ht); 208 ht_init(ht, 8); 209 return (ht); 210 } 211 212 /* 213 * Insert and/or replace. 214 */ 215 int 216 ht_insrep(ht, nam, val, replace) 217 register struct hashtab *ht; 218 register const char *nam; 219 void *val; 220 int replace; 221 { 222 register struct hashent *hp, **hpp; 223 register u_int h; 224 225 h = hash(nam); 226 hpp = &ht->ht_tab[h & ht->ht_mask]; 227 for (; (hp = *hpp) != NULL; hpp = &hp->h_next) { 228 if (hp->h_name == nam) { 229 if (replace) 230 hp->h_value = val; 231 return (1); 232 } 233 } 234 *hpp = hp = newhashent(nam, h); 235 hp->h_value = val; 236 return (0); 237 } 238 239 void * 240 ht_lookup(ht, nam) 241 register struct hashtab *ht; 242 register const char *nam; 243 { 244 register struct hashent *hp, **hpp; 245 register u_int h; 246 247 h = hash(nam); 248 hpp = &ht->ht_tab[h & ht->ht_mask]; 249 for (; (hp = *hpp) != NULL; hpp = &hp->h_next) 250 if (hp->h_name == nam) 251 return (hp->h_value); 252 return (NULL); 253 } 254