1236769Sobrien/* $NetBSD: hash.c,v 1.19 2009/01/24 10:59:09 dsl Exp $ */ 2236769Sobrien 3236769Sobrien/* 4236769Sobrien * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. 5236769Sobrien * All rights reserved. 6236769Sobrien * 7236769Sobrien * This code is derived from software contributed to Berkeley by 8236769Sobrien * Adam de Boor. 9236769Sobrien * 10236769Sobrien * Redistribution and use in source and binary forms, with or without 11236769Sobrien * modification, are permitted provided that the following conditions 12236769Sobrien * are met: 13236769Sobrien * 1. Redistributions of source code must retain the above copyright 14236769Sobrien * notice, this list of conditions and the following disclaimer. 15236769Sobrien * 2. Redistributions in binary form must reproduce the above copyright 16236769Sobrien * notice, this list of conditions and the following disclaimer in the 17236769Sobrien * documentation and/or other materials provided with the distribution. 18236769Sobrien * 3. Neither the name of the University nor the names of its contributors 19236769Sobrien * may be used to endorse or promote products derived from this software 20236769Sobrien * without specific prior written permission. 21236769Sobrien * 22236769Sobrien * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23236769Sobrien * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24236769Sobrien * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25236769Sobrien * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26236769Sobrien * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27236769Sobrien * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28236769Sobrien * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29236769Sobrien * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30236769Sobrien * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31236769Sobrien * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32236769Sobrien * SUCH DAMAGE. 33236769Sobrien */ 34236769Sobrien 35236769Sobrien/* 36236769Sobrien * Copyright (c) 1988, 1989 by Adam de Boor 37236769Sobrien * Copyright (c) 1989 by Berkeley Softworks 38236769Sobrien * All rights reserved. 39236769Sobrien * 40236769Sobrien * This code is derived from software contributed to Berkeley by 41236769Sobrien * Adam de Boor. 42236769Sobrien * 43236769Sobrien * Redistribution and use in source and binary forms, with or without 44236769Sobrien * modification, are permitted provided that the following conditions 45236769Sobrien * are met: 46236769Sobrien * 1. Redistributions of source code must retain the above copyright 47236769Sobrien * notice, this list of conditions and the following disclaimer. 48236769Sobrien * 2. Redistributions in binary form must reproduce the above copyright 49236769Sobrien * notice, this list of conditions and the following disclaimer in the 50236769Sobrien * documentation and/or other materials provided with the distribution. 51236769Sobrien * 3. All advertising materials mentioning features or use of this software 52236769Sobrien * must display the following acknowledgement: 53236769Sobrien * This product includes software developed by the University of 54236769Sobrien * California, Berkeley and its contributors. 55236769Sobrien * 4. Neither the name of the University nor the names of its contributors 56236769Sobrien * may be used to endorse or promote products derived from this software 57236769Sobrien * without specific prior written permission. 58236769Sobrien * 59236769Sobrien * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 60236769Sobrien * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 61236769Sobrien * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 62236769Sobrien * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 63236769Sobrien * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 64236769Sobrien * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 65236769Sobrien * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 66236769Sobrien * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 67236769Sobrien * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 68236769Sobrien * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 69236769Sobrien * SUCH DAMAGE. 70236769Sobrien */ 71236769Sobrien 72236769Sobrien#ifndef MAKE_NATIVE 73236769Sobrienstatic char rcsid[] = "$NetBSD: hash.c,v 1.19 2009/01/24 10:59:09 dsl Exp $"; 74236769Sobrien#else 75236769Sobrien#include <sys/cdefs.h> 76236769Sobrien#ifndef lint 77236769Sobrien#if 0 78236769Sobrienstatic char sccsid[] = "@(#)hash.c 8.1 (Berkeley) 6/6/93"; 79236769Sobrien#else 80236769Sobrien__RCSID("$NetBSD: hash.c,v 1.19 2009/01/24 10:59:09 dsl Exp $"); 81236769Sobrien#endif 82236769Sobrien#endif /* not lint */ 83236769Sobrien#endif 84236769Sobrien 85236769Sobrien/* hash.c -- 86236769Sobrien * 87236769Sobrien * This module contains routines to manipulate a hash table. 88236769Sobrien * See hash.h for a definition of the structure of the hash 89236769Sobrien * table. Hash tables grow automatically as the amount of 90236769Sobrien * information increases. 91236769Sobrien */ 92236769Sobrien#include "sprite.h" 93236769Sobrien#include "make.h" 94236769Sobrien#include "hash.h" 95236769Sobrien 96236769Sobrien/* 97236769Sobrien * Forward references to local procedures that are used before they're 98236769Sobrien * defined: 99236769Sobrien */ 100236769Sobrien 101236769Sobrienstatic void RebuildTable(Hash_Table *); 102236769Sobrien 103236769Sobrien/* 104236769Sobrien * The following defines the ratio of # entries to # buckets 105236769Sobrien * at which we rebuild the table to make it larger. 106236769Sobrien */ 107236769Sobrien 108236769Sobrien#define rebuildLimit 3 109236769Sobrien 110236769Sobrien/* 111236769Sobrien *--------------------------------------------------------- 112236769Sobrien * 113236769Sobrien * Hash_InitTable -- 114236769Sobrien * 115236769Sobrien * This routine just sets up the hash table. 116236769Sobrien * 117236769Sobrien * Input: 118236769Sobrien * t Structure to to hold table. 119236769Sobrien * numBuckets How many buckets to create for starters. This 120236769Sobrien * number is rounded up to a power of two. If 121236769Sobrien * <= 0, a reasonable default is chosen. The 122236769Sobrien * table will grow in size later as needed. 123236769Sobrien * 124236769Sobrien * Results: 125236769Sobrien * None. 126236769Sobrien * 127236769Sobrien * Side Effects: 128236769Sobrien * Memory is allocated for the initial bucket area. 129236769Sobrien * 130236769Sobrien *--------------------------------------------------------- 131236769Sobrien */ 132236769Sobrien 133236769Sobrienvoid 134236769SobrienHash_InitTable(Hash_Table *t, int numBuckets) 135236769Sobrien{ 136236769Sobrien int i; 137236769Sobrien struct Hash_Entry **hp; 138236769Sobrien 139236769Sobrien /* 140236769Sobrien * Round up the size to a power of two. 141236769Sobrien */ 142236769Sobrien if (numBuckets <= 0) 143236769Sobrien i = 16; 144236769Sobrien else { 145236769Sobrien for (i = 2; i < numBuckets; i <<= 1) 146236769Sobrien continue; 147236769Sobrien } 148236769Sobrien t->numEntries = 0; 149236769Sobrien t->size = i; 150236769Sobrien t->mask = i - 1; 151236769Sobrien t->bucketPtr = hp = bmake_malloc(sizeof(*hp) * i); 152236769Sobrien while (--i >= 0) 153236769Sobrien *hp++ = NULL; 154236769Sobrien} 155236769Sobrien 156236769Sobrien/* 157236769Sobrien *--------------------------------------------------------- 158236769Sobrien * 159236769Sobrien * Hash_DeleteTable -- 160236769Sobrien * 161236769Sobrien * This routine removes everything from a hash table 162236769Sobrien * and frees up the memory space it occupied (except for 163236769Sobrien * the space in the Hash_Table structure). 164236769Sobrien * 165236769Sobrien * Results: 166236769Sobrien * None. 167236769Sobrien * 168236769Sobrien * Side Effects: 169236769Sobrien * Lots of memory is freed up. 170236769Sobrien * 171236769Sobrien *--------------------------------------------------------- 172236769Sobrien */ 173236769Sobrien 174236769Sobrienvoid 175236769SobrienHash_DeleteTable(Hash_Table *t) 176236769Sobrien{ 177236769Sobrien struct Hash_Entry **hp, *h, *nexth = NULL; 178236769Sobrien int i; 179236769Sobrien 180236769Sobrien for (hp = t->bucketPtr, i = t->size; --i >= 0;) { 181236769Sobrien for (h = *hp++; h != NULL; h = nexth) { 182236769Sobrien nexth = h->next; 183236769Sobrien free(h); 184236769Sobrien } 185236769Sobrien } 186236769Sobrien free(t->bucketPtr); 187236769Sobrien 188236769Sobrien /* 189236769Sobrien * Set up the hash table to cause memory faults on any future access 190236769Sobrien * attempts until re-initialization. 191236769Sobrien */ 192236769Sobrien t->bucketPtr = NULL; 193236769Sobrien} 194236769Sobrien 195236769Sobrien/* 196236769Sobrien *--------------------------------------------------------- 197236769Sobrien * 198236769Sobrien * Hash_FindEntry -- 199236769Sobrien * 200236769Sobrien * Searches a hash table for an entry corresponding to key. 201236769Sobrien * 202236769Sobrien * Input: 203236769Sobrien * t Hash table to search. 204236769Sobrien * key A hash key. 205236769Sobrien * 206236769Sobrien * Results: 207236769Sobrien * The return value is a pointer to the entry for key, 208236769Sobrien * if key was present in the table. If key was not 209236769Sobrien * present, NULL is returned. 210236769Sobrien * 211236769Sobrien * Side Effects: 212236769Sobrien * None. 213236769Sobrien * 214236769Sobrien *--------------------------------------------------------- 215236769Sobrien */ 216236769Sobrien 217236769SobrienHash_Entry * 218236769SobrienHash_FindEntry(Hash_Table *t, const char *key) 219236769Sobrien{ 220236769Sobrien Hash_Entry *e; 221236769Sobrien unsigned h; 222236769Sobrien const char *p; 223236769Sobrien 224236769Sobrien for (h = 0, p = key; *p;) 225236769Sobrien h = (h << 5) - h + *p++; 226236769Sobrien p = key; 227236769Sobrien for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) 228236769Sobrien if (e->namehash == h && strcmp(e->name, p) == 0) 229236769Sobrien return (e); 230236769Sobrien return NULL; 231236769Sobrien} 232236769Sobrien 233236769Sobrien/* 234236769Sobrien *--------------------------------------------------------- 235236769Sobrien * 236236769Sobrien * Hash_CreateEntry -- 237236769Sobrien * 238236769Sobrien * Searches a hash table for an entry corresponding to 239236769Sobrien * key. If no entry is found, then one is created. 240236769Sobrien * 241236769Sobrien * Input: 242236769Sobrien * t Hash table to search. 243236769Sobrien * key A hash key. 244236769Sobrien * newPtr Filled in with TRUE if new entry created, 245236769Sobrien * FALSE otherwise. 246236769Sobrien * 247236769Sobrien * Results: 248236769Sobrien * The return value is a pointer to the entry. If *newPtr 249236769Sobrien * isn't NULL, then *newPtr is filled in with TRUE if a 250236769Sobrien * new entry was created, and FALSE if an entry already existed 251236769Sobrien * with the given key. 252236769Sobrien * 253236769Sobrien * Side Effects: 254236769Sobrien * Memory may be allocated, and the hash buckets may be modified. 255236769Sobrien *--------------------------------------------------------- 256236769Sobrien */ 257236769Sobrien 258236769SobrienHash_Entry * 259236769SobrienHash_CreateEntry(Hash_Table *t, const char *key, Boolean *newPtr) 260236769Sobrien{ 261236769Sobrien Hash_Entry *e; 262236769Sobrien unsigned h; 263236769Sobrien const char *p; 264236769Sobrien int keylen; 265236769Sobrien struct Hash_Entry **hp; 266236769Sobrien 267236769Sobrien /* 268236769Sobrien * Hash the key. As a side effect, save the length (strlen) of the 269236769Sobrien * key in case we need to create the entry. 270236769Sobrien */ 271236769Sobrien for (h = 0, p = key; *p;) 272236769Sobrien h = (h << 5) - h + *p++; 273236769Sobrien keylen = p - key; 274236769Sobrien p = key; 275236769Sobrien for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) { 276236769Sobrien if (e->namehash == h && strcmp(e->name, p) == 0) { 277236769Sobrien if (newPtr != NULL) 278236769Sobrien *newPtr = FALSE; 279236769Sobrien return (e); 280236769Sobrien } 281236769Sobrien } 282236769Sobrien 283236769Sobrien /* 284236769Sobrien * The desired entry isn't there. Before allocating a new entry, 285236769Sobrien * expand the table if necessary (and this changes the resulting 286236769Sobrien * bucket chain). 287236769Sobrien */ 288236769Sobrien if (t->numEntries >= rebuildLimit * t->size) 289236769Sobrien RebuildTable(t); 290236769Sobrien e = bmake_malloc(sizeof(*e) + keylen); 291236769Sobrien hp = &t->bucketPtr[h & t->mask]; 292236769Sobrien e->next = *hp; 293236769Sobrien *hp = e; 294236769Sobrien Hash_SetValue(e, NULL); 295236769Sobrien e->namehash = h; 296236769Sobrien (void)strcpy(e->name, p); 297236769Sobrien t->numEntries++; 298236769Sobrien 299236769Sobrien if (newPtr != NULL) 300236769Sobrien *newPtr = TRUE; 301236769Sobrien return (e); 302236769Sobrien} 303236769Sobrien 304236769Sobrien/* 305236769Sobrien *--------------------------------------------------------- 306236769Sobrien * 307236769Sobrien * Hash_DeleteEntry -- 308236769Sobrien * 309236769Sobrien * Delete the given hash table entry and free memory associated with 310236769Sobrien * it. 311236769Sobrien * 312236769Sobrien * Results: 313236769Sobrien * None. 314236769Sobrien * 315236769Sobrien * Side Effects: 316236769Sobrien * Hash chain that entry lives in is modified and memory is freed. 317236769Sobrien * 318236769Sobrien *--------------------------------------------------------- 319236769Sobrien */ 320236769Sobrien 321236769Sobrienvoid 322236769SobrienHash_DeleteEntry(Hash_Table *t, Hash_Entry *e) 323236769Sobrien{ 324236769Sobrien Hash_Entry **hp, *p; 325236769Sobrien 326236769Sobrien if (e == NULL) 327236769Sobrien return; 328236769Sobrien for (hp = &t->bucketPtr[e->namehash & t->mask]; 329236769Sobrien (p = *hp) != NULL; hp = &p->next) { 330236769Sobrien if (p == e) { 331236769Sobrien *hp = p->next; 332236769Sobrien free(p); 333236769Sobrien t->numEntries--; 334236769Sobrien return; 335236769Sobrien } 336236769Sobrien } 337236769Sobrien (void)write(2, "bad call to Hash_DeleteEntry\n", 29); 338236769Sobrien abort(); 339236769Sobrien} 340236769Sobrien 341236769Sobrien/* 342236769Sobrien *--------------------------------------------------------- 343236769Sobrien * 344236769Sobrien * Hash_EnumFirst -- 345236769Sobrien * This procedure sets things up for a complete search 346236769Sobrien * of all entries recorded in the hash table. 347236769Sobrien * 348236769Sobrien * Input: 349236769Sobrien * t Table to be searched. 350236769Sobrien * searchPtr Area in which to keep state about search. 351236769Sobrien * 352236769Sobrien * Results: 353236769Sobrien * The return value is the address of the first entry in 354236769Sobrien * the hash table, or NULL if the table is empty. 355236769Sobrien * 356236769Sobrien * Side Effects: 357236769Sobrien * The information in searchPtr is initialized so that successive 358236769Sobrien * calls to Hash_Next will return successive HashEntry's 359236769Sobrien * from the table. 360236769Sobrien * 361236769Sobrien *--------------------------------------------------------- 362236769Sobrien */ 363236769Sobrien 364236769SobrienHash_Entry * 365236769SobrienHash_EnumFirst(Hash_Table *t, Hash_Search *searchPtr) 366236769Sobrien{ 367236769Sobrien searchPtr->tablePtr = t; 368236769Sobrien searchPtr->nextIndex = 0; 369236769Sobrien searchPtr->hashEntryPtr = NULL; 370236769Sobrien return Hash_EnumNext(searchPtr); 371236769Sobrien} 372236769Sobrien 373236769Sobrien/* 374236769Sobrien *--------------------------------------------------------- 375236769Sobrien * 376236769Sobrien * Hash_EnumNext -- 377236769Sobrien * This procedure returns successive entries in the hash table. 378236769Sobrien * 379236769Sobrien * Input: 380236769Sobrien * searchPtr Area used to keep state about search. 381236769Sobrien * 382236769Sobrien * Results: 383236769Sobrien * The return value is a pointer to the next HashEntry 384236769Sobrien * in the table, or NULL when the end of the table is 385236769Sobrien * reached. 386236769Sobrien * 387236769Sobrien * Side Effects: 388236769Sobrien * The information in searchPtr is modified to advance to the 389236769Sobrien * next entry. 390236769Sobrien * 391236769Sobrien *--------------------------------------------------------- 392236769Sobrien */ 393236769Sobrien 394236769SobrienHash_Entry * 395236769SobrienHash_EnumNext(Hash_Search *searchPtr) 396236769Sobrien{ 397236769Sobrien Hash_Entry *e; 398236769Sobrien Hash_Table *t = searchPtr->tablePtr; 399236769Sobrien 400236769Sobrien /* 401236769Sobrien * The hashEntryPtr field points to the most recently returned 402236769Sobrien * entry, or is nil if we are starting up. If not nil, we have 403236769Sobrien * to start at the next one in the chain. 404236769Sobrien */ 405236769Sobrien e = searchPtr->hashEntryPtr; 406236769Sobrien if (e != NULL) 407236769Sobrien e = e->next; 408236769Sobrien /* 409236769Sobrien * If the chain ran out, or if we are starting up, we need to 410236769Sobrien * find the next nonempty chain. 411236769Sobrien */ 412236769Sobrien while (e == NULL) { 413236769Sobrien if (searchPtr->nextIndex >= t->size) 414236769Sobrien return NULL; 415236769Sobrien e = t->bucketPtr[searchPtr->nextIndex++]; 416236769Sobrien } 417236769Sobrien searchPtr->hashEntryPtr = e; 418236769Sobrien return (e); 419236769Sobrien} 420236769Sobrien 421236769Sobrien/* 422236769Sobrien *--------------------------------------------------------- 423236769Sobrien * 424236769Sobrien * RebuildTable -- 425236769Sobrien * This local routine makes a new hash table that 426236769Sobrien * is larger than the old one. 427236769Sobrien * 428236769Sobrien * Results: 429236769Sobrien * None. 430236769Sobrien * 431236769Sobrien * Side Effects: 432236769Sobrien * The entire hash table is moved, so any bucket numbers 433236769Sobrien * from the old table are invalid. 434236769Sobrien * 435236769Sobrien *--------------------------------------------------------- 436236769Sobrien */ 437236769Sobrien 438236769Sobrienstatic void 439236769SobrienRebuildTable(Hash_Table *t) 440236769Sobrien{ 441236769Sobrien Hash_Entry *e, *next = NULL, **hp, **xp; 442236769Sobrien int i, mask; 443236769Sobrien Hash_Entry **oldhp; 444236769Sobrien int oldsize; 445236769Sobrien 446236769Sobrien oldhp = t->bucketPtr; 447236769Sobrien oldsize = i = t->size; 448236769Sobrien i <<= 1; 449236769Sobrien t->size = i; 450236769Sobrien t->mask = mask = i - 1; 451236769Sobrien t->bucketPtr = hp = bmake_malloc(sizeof(*hp) * i); 452236769Sobrien while (--i >= 0) 453236769Sobrien *hp++ = NULL; 454236769Sobrien for (hp = oldhp, i = oldsize; --i >= 0;) { 455236769Sobrien for (e = *hp++; e != NULL; e = next) { 456236769Sobrien next = e->next; 457236769Sobrien xp = &t->bucketPtr[e->namehash & mask]; 458236769Sobrien e->next = *xp; 459236769Sobrien *xp = e; 460236769Sobrien } 461236769Sobrien } 462236769Sobrien free(oldhp); 463236769Sobrien} 464