hash.c revision 104696
11590Srgrimes/* 294589Sobrien * Copyright (c) 1988, 1989, 1990, 1993 394589Sobrien * The Regents of the University of California. All rights reserved. 45814Sjkh * Copyright (c) 1988, 1989 by Adam de Boor 51590Srgrimes * Copyright (c) 1989 by Berkeley Softworks 61590Srgrimes * All rights reserved. 71590Srgrimes * 81590Srgrimes * This code is derived from software contributed to Berkeley by 91590Srgrimes * Adam de Boor. 101590Srgrimes * 111590Srgrimes * Redistribution and use in source and binary forms, with or without 121590Srgrimes * modification, are permitted provided that the following conditions 131590Srgrimes * are met: 141590Srgrimes * 1. Redistributions of source code must retain the above copyright 151590Srgrimes * notice, this list of conditions and the following disclaimer. 161590Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 171590Srgrimes * notice, this list of conditions and the following disclaimer in the 181590Srgrimes * documentation and/or other materials provided with the distribution. 191590Srgrimes * 3. All advertising materials mentioning features or use of this software 201590Srgrimes * must display the following acknowledgement: 211590Srgrimes * This product includes software developed by the University of 221590Srgrimes * California, Berkeley and its contributors. 231590Srgrimes * 4. Neither the name of the University nor the names of its contributors 241590Srgrimes * may be used to endorse or promote products derived from this software 251590Srgrimes * without specific prior written permission. 261590Srgrimes * 271590Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 281590Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 291590Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 301590Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 311590Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 321590Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 331590Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 341590Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 351590Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 361590Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 371590Srgrimes * SUCH DAMAGE. 3862833Swsanchez * 3962833Swsanchez * @(#)hash.c 8.1 (Berkeley) 6/6/93 401590Srgrimes */ 411590Srgrimes 4262833Swsanchez#include <sys/cdefs.h> 4394587Sobrien__FBSDID("$FreeBSD: head/usr.bin/make/hash.c 104696 2002-10-09 03:42:10Z jmallett $"); 441590Srgrimes 451590Srgrimes/* hash.c -- 461590Srgrimes * 471590Srgrimes * This module contains routines to manipulate a hash table. 481590Srgrimes * See hash.h for a definition of the structure of the hash 491590Srgrimes * table. Hash tables grow automatically as the amount of 501590Srgrimes * information increases. 511590Srgrimes */ 5280381Ssheldonh#include <unistd.h> 531590Srgrimes#include "sprite.h" 541590Srgrimes#include "make.h" 551590Srgrimes#include "hash.h" 561590Srgrimes 571590Srgrimes/* 581590Srgrimes * Forward references to local procedures that are used before they're 591590Srgrimes * defined: 601590Srgrimes */ 611590Srgrimes 6292921Simpstatic void RebuildTable(Hash_Table *); 631590Srgrimes 648874Srgrimes/* 651590Srgrimes * The following defines the ratio of # entries to # buckets 661590Srgrimes * at which we rebuild the table to make it larger. 671590Srgrimes */ 681590Srgrimes 69103503Sjmallett#define rebuildLimit 8 701590Srgrimes 711590Srgrimes/* 721590Srgrimes *--------------------------------------------------------- 738874Srgrimes * 741590Srgrimes * Hash_InitTable -- 75104696Sjmallett * 76104696Sjmallett * Set up the hash table t with a given number of buckets, or a 77104696Sjmallett * reasonable default if the number requested is less than or 78104696Sjmallett * equal to zero. Hash tables will grow in size as needed. 791590Srgrimes * 801590Srgrimes * 818874Srgrimes * Results: 821590Srgrimes * None. 831590Srgrimes * 841590Srgrimes * Side Effects: 851590Srgrimes * Memory is allocated for the initial bucket area. 861590Srgrimes * 871590Srgrimes *--------------------------------------------------------- 881590Srgrimes */ 891590Srgrimes 901590Srgrimesvoid 91104696SjmallettHash_InitTable(Hash_Table *t, int numBuckets) 921590Srgrimes{ 9394584Sobrien int i; 9494584Sobrien struct Hash_Entry **hp; 951590Srgrimes 961590Srgrimes /* 978874Srgrimes * Round up the size to a power of two. 981590Srgrimes */ 991590Srgrimes if (numBuckets <= 0) 1001590Srgrimes i = 16; 1011590Srgrimes else { 1021590Srgrimes for (i = 2; i < numBuckets; i <<= 1) 1031590Srgrimes continue; 1041590Srgrimes } 1051590Srgrimes t->numEntries = 0; 1061590Srgrimes t->size = i; 1071590Srgrimes t->mask = i - 1; 1081590Srgrimes t->bucketPtr = hp = (struct Hash_Entry **)emalloc(sizeof(*hp) * i); 1091590Srgrimes while (--i >= 0) 1101590Srgrimes *hp++ = NULL; 1111590Srgrimes} 1121590Srgrimes 1131590Srgrimes/* 1141590Srgrimes *--------------------------------------------------------- 1151590Srgrimes * 1161590Srgrimes * Hash_DeleteTable -- 1171590Srgrimes * 1181590Srgrimes * This routine removes everything from a hash table 1191590Srgrimes * and frees up the memory space it occupied (except for 1201590Srgrimes * the space in the Hash_Table structure). 1211590Srgrimes * 1228874Srgrimes * Results: 1231590Srgrimes * None. 1241590Srgrimes * 1251590Srgrimes * Side Effects: 1261590Srgrimes * Lots of memory is freed up. 1271590Srgrimes * 1281590Srgrimes *--------------------------------------------------------- 1291590Srgrimes */ 1301590Srgrimes 1311590Srgrimesvoid 132104696SjmallettHash_DeleteTable(Hash_Table *t) 1331590Srgrimes{ 13494584Sobrien struct Hash_Entry **hp, *h, *nexth = NULL; 13594584Sobrien int i; 1361590Srgrimes 1371590Srgrimes for (hp = t->bucketPtr, i = t->size; --i >= 0;) { 1381590Srgrimes for (h = *hp++; h != NULL; h = nexth) { 1391590Srgrimes nexth = h->next; 1401590Srgrimes free((char *)h); 1411590Srgrimes } 1421590Srgrimes } 1431590Srgrimes free((char *)t->bucketPtr); 1441590Srgrimes 1451590Srgrimes /* 1461590Srgrimes * Set up the hash table to cause memory faults on any future access 1478874Srgrimes * attempts until re-initialization. 1481590Srgrimes */ 1491590Srgrimes t->bucketPtr = NULL; 1501590Srgrimes} 1511590Srgrimes 1521590Srgrimes/* 1531590Srgrimes *--------------------------------------------------------- 1541590Srgrimes * 1551590Srgrimes * Hash_FindEntry -- 1561590Srgrimes * 1571590Srgrimes * Searches a hash table for an entry corresponding to key. 1581590Srgrimes * 1591590Srgrimes * Results: 1601590Srgrimes * The return value is a pointer to the entry for key, 1611590Srgrimes * if key was present in the table. If key was not 1621590Srgrimes * present, NULL is returned. 1631590Srgrimes * 1641590Srgrimes * Side Effects: 1651590Srgrimes * None. 1661590Srgrimes * 1671590Srgrimes *--------------------------------------------------------- 1681590Srgrimes */ 1691590Srgrimes 1701590SrgrimesHash_Entry * 171104696SjmallettHash_FindEntry(Hash_Table *t, char *key) 1721590Srgrimes{ 17394584Sobrien Hash_Entry *e; 17494584Sobrien unsigned h; 17594584Sobrien char *p; 1761590Srgrimes 1771590Srgrimes for (h = 0, p = key; *p;) 1781590Srgrimes h = (h << 5) - h + *p++; 1791590Srgrimes p = key; 1801590Srgrimes for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) 1811590Srgrimes if (e->namehash == h && strcmp(e->name, p) == 0) 1821590Srgrimes return (e); 1831590Srgrimes return (NULL); 1841590Srgrimes} 1851590Srgrimes 1861590Srgrimes/* 1871590Srgrimes *--------------------------------------------------------- 1881590Srgrimes * 1891590Srgrimes * Hash_CreateEntry -- 1901590Srgrimes * 1911590Srgrimes * Searches a hash table for an entry corresponding to 1921590Srgrimes * key. If no entry is found, then one is created. 1931590Srgrimes * 1941590Srgrimes * Results: 1951590Srgrimes * The return value is a pointer to the entry. If *newPtr 1961590Srgrimes * isn't NULL, then *newPtr is filled in with TRUE if a 1971590Srgrimes * new entry was created, and FALSE if an entry already existed 1981590Srgrimes * with the given key. 1991590Srgrimes * 2001590Srgrimes * Side Effects: 2011590Srgrimes * Memory may be allocated, and the hash buckets may be modified. 2021590Srgrimes *--------------------------------------------------------- 2031590Srgrimes */ 2041590Srgrimes 2051590SrgrimesHash_Entry * 206104696SjmallettHash_CreateEntry(Hash_Table *t, char *key, Boolean *newPtr) 2071590Srgrimes{ 20894584Sobrien Hash_Entry *e; 209104696Sjmallett unsigned int h; 21094584Sobrien char *p; 2111590Srgrimes int keylen; 2121590Srgrimes struct Hash_Entry **hp; 2131590Srgrimes 2141590Srgrimes /* 2151590Srgrimes * Hash the key. As a side effect, save the length (strlen) of the 2161590Srgrimes * key in case we need to create the entry. 2171590Srgrimes */ 2181590Srgrimes for (h = 0, p = key; *p;) 2191590Srgrimes h = (h << 5) - h + *p++; 2201590Srgrimes keylen = p - key; 2211590Srgrimes p = key; 2221590Srgrimes for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) { 2231590Srgrimes if (e->namehash == h && strcmp(e->name, p) == 0) { 2241590Srgrimes if (newPtr != NULL) 2251590Srgrimes *newPtr = FALSE; 2261590Srgrimes return (e); 2271590Srgrimes } 2281590Srgrimes } 2291590Srgrimes 2301590Srgrimes /* 2311590Srgrimes * The desired entry isn't there. Before allocating a new entry, 2321590Srgrimes * expand the table if necessary (and this changes the resulting 2338874Srgrimes * bucket chain). 2341590Srgrimes */ 2351590Srgrimes if (t->numEntries >= rebuildLimit * t->size) 2361590Srgrimes RebuildTable(t); 2371590Srgrimes e = (Hash_Entry *) emalloc(sizeof(*e) + keylen); 2381590Srgrimes hp = &t->bucketPtr[h & t->mask]; 2391590Srgrimes e->next = *hp; 2401590Srgrimes *hp = e; 2411590Srgrimes e->clientData = NULL; 2421590Srgrimes e->namehash = h; 2431590Srgrimes (void) strcpy(e->name, p); 2441590Srgrimes t->numEntries++; 2451590Srgrimes 2461590Srgrimes if (newPtr != NULL) 2471590Srgrimes *newPtr = TRUE; 2481590Srgrimes return (e); 2491590Srgrimes} 2501590Srgrimes 2511590Srgrimes/* 2521590Srgrimes *--------------------------------------------------------- 2531590Srgrimes * 2541590Srgrimes * Hash_DeleteEntry -- 2551590Srgrimes * 2561590Srgrimes * Delete the given hash table entry and free memory associated with 2571590Srgrimes * it. 2581590Srgrimes * 2591590Srgrimes * Results: 2601590Srgrimes * None. 2611590Srgrimes * 2621590Srgrimes * Side Effects: 2631590Srgrimes * Hash chain that entry lives in is modified and memory is freed. 2641590Srgrimes * 2651590Srgrimes *--------------------------------------------------------- 2661590Srgrimes */ 2671590Srgrimes 2681590Srgrimesvoid 269104696SjmallettHash_DeleteEntry(Hash_Table *t, Hash_Entry *e) 2701590Srgrimes{ 27194584Sobrien Hash_Entry **hp, *p; 2721590Srgrimes 2731590Srgrimes if (e == NULL) 2741590Srgrimes return; 2751590Srgrimes for (hp = &t->bucketPtr[e->namehash & t->mask]; 2761590Srgrimes (p = *hp) != NULL; hp = &p->next) { 2771590Srgrimes if (p == e) { 2781590Srgrimes *hp = p->next; 2791590Srgrimes free((char *)p); 2801590Srgrimes t->numEntries--; 2811590Srgrimes return; 2821590Srgrimes } 2831590Srgrimes } 28480381Ssheldonh (void) write(STDERR_FILENO, "bad call to Hash_DeleteEntry\n", 29); 2851590Srgrimes abort(); 2861590Srgrimes} 2871590Srgrimes 2881590Srgrimes/* 2891590Srgrimes *--------------------------------------------------------- 2901590Srgrimes * 2911590Srgrimes * Hash_EnumFirst -- 2921590Srgrimes * This procedure sets things up for a complete search 2931590Srgrimes * of all entries recorded in the hash table. 2941590Srgrimes * 2958874Srgrimes * Results: 2961590Srgrimes * The return value is the address of the first entry in 2971590Srgrimes * the hash table, or NULL if the table is empty. 2981590Srgrimes * 2991590Srgrimes * Side Effects: 3001590Srgrimes * The information in searchPtr is initialized so that successive 3011590Srgrimes * calls to Hash_Next will return successive HashEntry's 3021590Srgrimes * from the table. 3031590Srgrimes * 3041590Srgrimes *--------------------------------------------------------- 3051590Srgrimes */ 3061590Srgrimes 3071590SrgrimesHash_Entry * 308104696SjmallettHash_EnumFirst(Hash_Table *t, Hash_Search *searchPtr) 3091590Srgrimes{ 3101590Srgrimes searchPtr->tablePtr = t; 3111590Srgrimes searchPtr->nextIndex = 0; 3121590Srgrimes searchPtr->hashEntryPtr = NULL; 3131590Srgrimes return Hash_EnumNext(searchPtr); 3141590Srgrimes} 3151590Srgrimes 3161590Srgrimes/* 3171590Srgrimes *--------------------------------------------------------- 3181590Srgrimes * 3191590Srgrimes * Hash_EnumNext -- 3201590Srgrimes * This procedure returns successive entries in the hash table. 3211590Srgrimes * 3221590Srgrimes * Results: 3231590Srgrimes * The return value is a pointer to the next HashEntry 3241590Srgrimes * in the table, or NULL when the end of the table is 3251590Srgrimes * reached. 3261590Srgrimes * 3271590Srgrimes * Side Effects: 3281590Srgrimes * The information in searchPtr is modified to advance to the 3291590Srgrimes * next entry. 3301590Srgrimes * 3311590Srgrimes *--------------------------------------------------------- 3321590Srgrimes */ 3331590Srgrimes 3341590SrgrimesHash_Entry * 335104696SjmallettHash_EnumNext(Hash_Search *searchPtr) 3361590Srgrimes{ 33794584Sobrien Hash_Entry *e; 3381590Srgrimes Hash_Table *t = searchPtr->tablePtr; 3391590Srgrimes 3401590Srgrimes /* 3411590Srgrimes * The hashEntryPtr field points to the most recently returned 34269527Swill * entry, or is NULL if we are starting up. If not NULL, we have 3431590Srgrimes * to start at the next one in the chain. 3441590Srgrimes */ 3451590Srgrimes e = searchPtr->hashEntryPtr; 3461590Srgrimes if (e != NULL) 3471590Srgrimes e = e->next; 3481590Srgrimes /* 3491590Srgrimes * If the chain ran out, or if we are starting up, we need to 3501590Srgrimes * find the next nonempty chain. 3511590Srgrimes */ 3521590Srgrimes while (e == NULL) { 3531590Srgrimes if (searchPtr->nextIndex >= t->size) 3541590Srgrimes return (NULL); 3551590Srgrimes e = t->bucketPtr[searchPtr->nextIndex++]; 3561590Srgrimes } 3571590Srgrimes searchPtr->hashEntryPtr = e; 3581590Srgrimes return (e); 3591590Srgrimes} 3601590Srgrimes 3611590Srgrimes/* 3621590Srgrimes *--------------------------------------------------------- 3631590Srgrimes * 3641590Srgrimes * RebuildTable -- 3651590Srgrimes * This local routine makes a new hash table that 3661590Srgrimes * is larger than the old one. 3671590Srgrimes * 3688874Srgrimes * Results: 3691590Srgrimes * None. 3701590Srgrimes * 3711590Srgrimes * Side Effects: 3721590Srgrimes * The entire hash table is moved, so any bucket numbers 3731590Srgrimes * from the old table are invalid. 3741590Srgrimes * 3751590Srgrimes *--------------------------------------------------------- 3761590Srgrimes */ 3771590Srgrimes 3781590Srgrimesstatic void 379104696SjmallettRebuildTable(Hash_Table *t) 3801590Srgrimes{ 38194584Sobrien Hash_Entry *e, *next = NULL, **hp, **xp; 38294584Sobrien int i, mask; 38394584Sobrien Hash_Entry **oldhp; 3841590Srgrimes int oldsize; 3851590Srgrimes 3861590Srgrimes oldhp = t->bucketPtr; 3871590Srgrimes oldsize = i = t->size; 3881590Srgrimes i <<= 1; 3891590Srgrimes t->size = i; 3901590Srgrimes t->mask = mask = i - 1; 3911590Srgrimes t->bucketPtr = hp = (struct Hash_Entry **) emalloc(sizeof(*hp) * i); 3921590Srgrimes while (--i >= 0) 3931590Srgrimes *hp++ = NULL; 3941590Srgrimes for (hp = oldhp, i = oldsize; --i >= 0;) { 3951590Srgrimes for (e = *hp++; e != NULL; e = next) { 3961590Srgrimes next = e->next; 3971590Srgrimes xp = &t->bucketPtr[e->namehash & mask]; 3981590Srgrimes e->next = *xp; 3991590Srgrimes *xp = e; 4001590Srgrimes } 4011590Srgrimes } 4021590Srgrimes free((char *)oldhp); 4031590Srgrimes} 404