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