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