1 /* $NetBSD: hash.c,v 1.10 2002/06/15 18:24:56 wiz Exp $ */ 2 3 /* 4 * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. 5 * Copyright (c) 1988, 1989 by Adam de Boor 6 * Copyright (c) 1989 by Berkeley Softworks 7 * All rights reserved. 8 * 9 * This code is derived from software contributed to Berkeley by 10 * Adam de Boor. 11 * 12 * Redistribution and use in source and binary forms, with or without 13 * modification, are permitted provided that the following conditions 14 * are met: 15 * 1. Redistributions of source code must retain the above copyright 16 * notice, this list of conditions and the following disclaimer. 17 * 2. Redistributions in binary form must reproduce the above copyright 18 * notice, this list of conditions and the following disclaimer in the 19 * documentation and/or other materials provided with the distribution. 20 * 3. All advertising materials mentioning features or use of this software 21 * must display the following acknowledgement: 22 * This product includes software developed by the University of 23 * California, Berkeley and its contributors. 24 * 4. Neither the name of the University nor the names of its contributors 25 * may be used to endorse or promote products derived from this software 26 * without specific prior written permission. 27 * 28 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 29 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 30 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 31 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 32 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 33 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 34 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 35 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 36 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 37 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 38 * SUCH DAMAGE. 39 */ 40 41 #ifdef MAKE_BOOTSTRAP 42 static char rcsid[] = "$NetBSD: hash.c,v 1.10 2002/06/15 18:24:56 wiz Exp $"; 43 #else 44 #include <sys/cdefs.h> 45 #ifndef lint 46 #if 0 47 static char sccsid[] = "@(#)hash.c 8.1 (Berkeley) 6/6/93"; 48 #else 49 __RCSID("$NetBSD: hash.c,v 1.10 2002/06/15 18:24:56 wiz Exp $"); 50 #endif 51 #endif /* not lint */ 52 #endif 53 54 /* hash.c -- 55 * 56 * This module contains routines to manipulate a hash table. 57 * See hash.h for a definition of the structure of the hash 58 * table. Hash tables grow automatically as the amount of 59 * information increases. 60 */ 61 #include "sprite.h" 62 #include "make.h" 63 #include "hash.h" 64 65 /* 66 * Forward references to local procedures that are used before they're 67 * defined: 68 */ 69 70 static void RebuildTable(Hash_Table *); 71 72 /* 73 * The following defines the ratio of # entries to # buckets 74 * at which we rebuild the table to make it larger. 75 */ 76 77 #define rebuildLimit 3 78 79 /* 80 *--------------------------------------------------------- 81 * 82 * Hash_InitTable -- 83 * 84 * This routine just sets up the hash table. 85 * 86 * Input: 87 * t Structure to to hold table. 88 * numBuckets How many buckets to create for starters. This 89 * number is rounded up to a power of two. If 90 * <= 0, a reasonable default is chosen. The 91 * table will grow in size later as needed. 92 * 93 * Results: 94 * None. 95 * 96 * Side Effects: 97 * Memory is allocated for the initial bucket area. 98 * 99 *--------------------------------------------------------- 100 */ 101 102 void 103 Hash_InitTable(Hash_Table *t, int numBuckets) 104 { 105 int i; 106 struct Hash_Entry **hp; 107 108 /* 109 * Round up the size to a power of two. 110 */ 111 if (numBuckets <= 0) 112 i = 16; 113 else { 114 for (i = 2; i < numBuckets; i <<= 1) 115 continue; 116 } 117 t->numEntries = 0; 118 t->size = i; 119 t->mask = i - 1; 120 t->bucketPtr = hp = (struct Hash_Entry **)emalloc(sizeof(*hp) * i); 121 while (--i >= 0) 122 *hp++ = NULL; 123 } 124 125 /* 126 *--------------------------------------------------------- 127 * 128 * Hash_DeleteTable -- 129 * 130 * This routine removes everything from a hash table 131 * and frees up the memory space it occupied (except for 132 * the space in the Hash_Table structure). 133 * 134 * Results: 135 * None. 136 * 137 * Side Effects: 138 * Lots of memory is freed up. 139 * 140 *--------------------------------------------------------- 141 */ 142 143 void 144 Hash_DeleteTable(Hash_Table *t) 145 { 146 struct Hash_Entry **hp, *h, *nexth = NULL; 147 int i; 148 149 for (hp = t->bucketPtr, i = t->size; --i >= 0;) { 150 for (h = *hp++; h != NULL; h = nexth) { 151 nexth = h->next; 152 free((char *)h); 153 } 154 } 155 free((char *)t->bucketPtr); 156 157 /* 158 * Set up the hash table to cause memory faults on any future access 159 * attempts until re-initialization. 160 */ 161 t->bucketPtr = NULL; 162 } 163 164 /* 165 *--------------------------------------------------------- 166 * 167 * Hash_FindEntry -- 168 * 169 * Searches a hash table for an entry corresponding to key. 170 * 171 * Input: 172 * t Hash table to search. 173 * key A hash key. 174 * 175 * Results: 176 * The return value is a pointer to the entry for key, 177 * if key was present in the table. If key was not 178 * present, NULL is returned. 179 * 180 * Side Effects: 181 * None. 182 * 183 *--------------------------------------------------------- 184 */ 185 186 Hash_Entry * 187 Hash_FindEntry(Hash_Table *t, char *key) 188 { 189 Hash_Entry *e; 190 unsigned h; 191 char *p; 192 193 for (h = 0, p = key; *p;) 194 h = (h << 5) - h + *p++; 195 p = key; 196 for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) 197 if (e->namehash == h && strcmp(e->name, p) == 0) 198 return (e); 199 return (NULL); 200 } 201 202 /* 203 *--------------------------------------------------------- 204 * 205 * Hash_CreateEntry -- 206 * 207 * Searches a hash table for an entry corresponding to 208 * key. If no entry is found, then one is created. 209 * 210 * Input: 211 * t Hash table to search. 212 * key A hash key. 213 * newPtr Filled in with TRUE if new entry created, 214 * FALSE otherwise. 215 * 216 * Results: 217 * The return value is a pointer to the entry. If *newPtr 218 * isn't NULL, then *newPtr is filled in with TRUE if a 219 * new entry was created, and FALSE if an entry already existed 220 * with the given key. 221 * 222 * Side Effects: 223 * Memory may be allocated, and the hash buckets may be modified. 224 *--------------------------------------------------------- 225 */ 226 227 Hash_Entry * 228 Hash_CreateEntry(Hash_Table *t, char *key, Boolean *newPtr) 229 { 230 Hash_Entry *e; 231 unsigned h; 232 char *p; 233 int keylen; 234 struct Hash_Entry **hp; 235 236 /* 237 * Hash the key. As a side effect, save the length (strlen) of the 238 * key in case we need to create the entry. 239 */ 240 for (h = 0, p = key; *p;) 241 h = (h << 5) - h + *p++; 242 keylen = p - key; 243 p = key; 244 for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) { 245 if (e->namehash == h && strcmp(e->name, p) == 0) { 246 if (newPtr != NULL) 247 *newPtr = FALSE; 248 return (e); 249 } 250 } 251 252 /* 253 * The desired entry isn't there. Before allocating a new entry, 254 * expand the table if necessary (and this changes the resulting 255 * bucket chain). 256 */ 257 if (t->numEntries >= rebuildLimit * t->size) 258 RebuildTable(t); 259 e = (Hash_Entry *) emalloc(sizeof(*e) + keylen); 260 hp = &t->bucketPtr[h & t->mask]; 261 e->next = *hp; 262 *hp = e; 263 e->clientData = NULL; 264 e->namehash = h; 265 (void) strcpy(e->name, p); 266 t->numEntries++; 267 268 if (newPtr != NULL) 269 *newPtr = TRUE; 270 return (e); 271 } 272 273 /* 274 *--------------------------------------------------------- 275 * 276 * Hash_DeleteEntry -- 277 * 278 * Delete the given hash table entry and free memory associated with 279 * it. 280 * 281 * Results: 282 * None. 283 * 284 * Side Effects: 285 * Hash chain that entry lives in is modified and memory is freed. 286 * 287 *--------------------------------------------------------- 288 */ 289 290 void 291 Hash_DeleteEntry(Hash_Table *t, Hash_Entry *e) 292 { 293 Hash_Entry **hp, *p; 294 295 if (e == NULL) 296 return; 297 for (hp = &t->bucketPtr[e->namehash & t->mask]; 298 (p = *hp) != NULL; hp = &p->next) { 299 if (p == e) { 300 *hp = p->next; 301 free((char *)p); 302 t->numEntries--; 303 return; 304 } 305 } 306 (void) write(2, "bad call to Hash_DeleteEntry\n", 29); 307 abort(); 308 } 309 310 /* 311 *--------------------------------------------------------- 312 * 313 * Hash_EnumFirst -- 314 * This procedure sets things up for a complete search 315 * of all entries recorded in the hash table. 316 * 317 * Input: 318 * t Table to be searched. 319 * searchPtr Area in which to keep state about search. 320 * 321 * Results: 322 * The return value is the address of the first entry in 323 * the hash table, or NULL if the table is empty. 324 * 325 * Side Effects: 326 * The information in searchPtr is initialized so that successive 327 * calls to Hash_Next will return successive HashEntry's 328 * from the table. 329 * 330 *--------------------------------------------------------- 331 */ 332 333 Hash_Entry * 334 Hash_EnumFirst(Hash_Table *t, Hash_Search *searchPtr) 335 { 336 searchPtr->tablePtr = t; 337 searchPtr->nextIndex = 0; 338 searchPtr->hashEntryPtr = NULL; 339 return Hash_EnumNext(searchPtr); 340 } 341 342 /* 343 *--------------------------------------------------------- 344 * 345 * Hash_EnumNext -- 346 * This procedure returns successive entries in the hash table. 347 * 348 * Input: 349 * searchPtr Area used to keep state about search. 350 * 351 * Results: 352 * The return value is a pointer to the next HashEntry 353 * in the table, or NULL when the end of the table is 354 * reached. 355 * 356 * Side Effects: 357 * The information in searchPtr is modified to advance to the 358 * next entry. 359 * 360 *--------------------------------------------------------- 361 */ 362 363 Hash_Entry * 364 Hash_EnumNext(Hash_Search *searchPtr) 365 { 366 Hash_Entry *e; 367 Hash_Table *t = searchPtr->tablePtr; 368 369 /* 370 * The hashEntryPtr field points to the most recently returned 371 * entry, or is nil if we are starting up. If not nil, we have 372 * to start at the next one in the chain. 373 */ 374 e = searchPtr->hashEntryPtr; 375 if (e != NULL) 376 e = e->next; 377 /* 378 * If the chain ran out, or if we are starting up, we need to 379 * find the next nonempty chain. 380 */ 381 while (e == NULL) { 382 if (searchPtr->nextIndex >= t->size) 383 return (NULL); 384 e = t->bucketPtr[searchPtr->nextIndex++]; 385 } 386 searchPtr->hashEntryPtr = e; 387 return (e); 388 } 389 390 /* 391 *--------------------------------------------------------- 392 * 393 * RebuildTable -- 394 * This local routine makes a new hash table that 395 * is larger than the old one. 396 * 397 * Results: 398 * None. 399 * 400 * Side Effects: 401 * The entire hash table is moved, so any bucket numbers 402 * from the old table are invalid. 403 * 404 *--------------------------------------------------------- 405 */ 406 407 static void 408 RebuildTable(Hash_Table *t) 409 { 410 Hash_Entry *e, *next = NULL, **hp, **xp; 411 int i, mask; 412 Hash_Entry **oldhp; 413 int oldsize; 414 415 oldhp = t->bucketPtr; 416 oldsize = i = t->size; 417 i <<= 1; 418 t->size = i; 419 t->mask = mask = i - 1; 420 t->bucketPtr = hp = (struct Hash_Entry **) emalloc(sizeof(*hp) * i); 421 while (--i >= 0) 422 *hp++ = NULL; 423 for (hp = oldhp, i = oldsize; --i >= 0;) { 424 for (e = *hp++; e != NULL; e = next) { 425 next = e->next; 426 xp = &t->bucketPtr[e->namehash & mask]; 427 e->next = *xp; 428 *xp = e; 429 } 430 } 431 free((char *)oldhp); 432 } 433