hash.c revision 69527
11590Srgrimes/* 25814Sjkh * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. 35814Sjkh * Copyright (c) 1988, 1989 by Adam de Boor 41590Srgrimes * Copyright (c) 1989 by Berkeley Softworks 51590Srgrimes * All rights reserved. 61590Srgrimes * 71590Srgrimes * This code is derived from software contributed to Berkeley by 81590Srgrimes * Adam de Boor. 91590Srgrimes * 101590Srgrimes * Redistribution and use in source and binary forms, with or without 111590Srgrimes * modification, are permitted provided that the following conditions 121590Srgrimes * are met: 131590Srgrimes * 1. Redistributions of source code must retain the above copyright 141590Srgrimes * notice, this list of conditions and the following disclaimer. 151590Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 161590Srgrimes * notice, this list of conditions and the following disclaimer in the 171590Srgrimes * documentation and/or other materials provided with the distribution. 181590Srgrimes * 3. All advertising materials mentioning features or use of this software 191590Srgrimes * must display the following acknowledgement: 201590Srgrimes * This product includes software developed by the University of 211590Srgrimes * California, Berkeley and its contributors. 221590Srgrimes * 4. Neither the name of the University nor the names of its contributors 231590Srgrimes * may be used to endorse or promote products derived from this software 241590Srgrimes * without specific prior written permission. 251590Srgrimes * 261590Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 271590Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 281590Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 291590Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 301590Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 311590Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 321590Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 331590Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 341590Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 351590Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 361590Srgrimes * SUCH DAMAGE. 3762833Swsanchez * 3862833Swsanchez * @(#)hash.c 8.1 (Berkeley) 6/6/93 391590Srgrimes */ 401590Srgrimes 411590Srgrimes#ifndef lint 4262833Swsanchez#include <sys/cdefs.h> 4362833Swsanchez__RCSID("$FreeBSD: head/usr.bin/make/hash.c 69527 2000-12-02 18:58:01Z will $"); 441590Srgrimes#endif /* not lint */ 451590Srgrimes 461590Srgrimes/* hash.c -- 471590Srgrimes * 481590Srgrimes * This module contains routines to manipulate a hash table. 491590Srgrimes * See hash.h for a definition of the structure of the hash 501590Srgrimes * table. Hash tables grow automatically as the amount of 511590Srgrimes * information increases. 521590Srgrimes */ 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 621590Srgrimesstatic void RebuildTable __P((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 691590Srgrimes#define rebuildLimit 8 701590Srgrimes 711590Srgrimes/* 721590Srgrimes *--------------------------------------------------------- 738874Srgrimes * 741590Srgrimes * Hash_InitTable -- 751590Srgrimes * 761590Srgrimes * This routine just sets up the hash table. 771590Srgrimes * 788874Srgrimes * Results: 791590Srgrimes * None. 801590Srgrimes * 811590Srgrimes * Side Effects: 821590Srgrimes * Memory is allocated for the initial bucket area. 831590Srgrimes * 841590Srgrimes *--------------------------------------------------------- 851590Srgrimes */ 861590Srgrimes 871590Srgrimesvoid 881590SrgrimesHash_InitTable(t, numBuckets) 891590Srgrimes register Hash_Table *t; /* Structure to use to hold table. */ 901590Srgrimes int numBuckets; /* How many buckets to create for starters. 911590Srgrimes * This number is rounded up to a power of 921590Srgrimes * two. If <= 0, a reasonable default is 931590Srgrimes * chosen. The table will grow in size later 941590Srgrimes * as needed. */ 951590Srgrimes{ 961590Srgrimes register int i; 971590Srgrimes register struct Hash_Entry **hp; 981590Srgrimes 991590Srgrimes /* 1008874Srgrimes * Round up the size to a power of two. 1011590Srgrimes */ 1021590Srgrimes if (numBuckets <= 0) 1031590Srgrimes i = 16; 1041590Srgrimes else { 1051590Srgrimes for (i = 2; i < numBuckets; i <<= 1) 1061590Srgrimes continue; 1071590Srgrimes } 1081590Srgrimes t->numEntries = 0; 1091590Srgrimes t->size = i; 1101590Srgrimes t->mask = i - 1; 1111590Srgrimes t->bucketPtr = hp = (struct Hash_Entry **)emalloc(sizeof(*hp) * i); 1121590Srgrimes while (--i >= 0) 1131590Srgrimes *hp++ = NULL; 1141590Srgrimes} 1151590Srgrimes 1161590Srgrimes/* 1171590Srgrimes *--------------------------------------------------------- 1181590Srgrimes * 1191590Srgrimes * Hash_DeleteTable -- 1201590Srgrimes * 1211590Srgrimes * This routine removes everything from a hash table 1221590Srgrimes * and frees up the memory space it occupied (except for 1231590Srgrimes * the space in the Hash_Table structure). 1241590Srgrimes * 1258874Srgrimes * Results: 1261590Srgrimes * None. 1271590Srgrimes * 1281590Srgrimes * Side Effects: 1291590Srgrimes * Lots of memory is freed up. 1301590Srgrimes * 1311590Srgrimes *--------------------------------------------------------- 1321590Srgrimes */ 1331590Srgrimes 1341590Srgrimesvoid 1351590SrgrimesHash_DeleteTable(t) 1361590Srgrimes Hash_Table *t; 1371590Srgrimes{ 1381590Srgrimes register struct Hash_Entry **hp, *h, *nexth = NULL; 1391590Srgrimes register int i; 1401590Srgrimes 1411590Srgrimes for (hp = t->bucketPtr, i = t->size; --i >= 0;) { 1421590Srgrimes for (h = *hp++; h != NULL; h = nexth) { 1431590Srgrimes nexth = h->next; 1441590Srgrimes free((char *)h); 1451590Srgrimes } 1461590Srgrimes } 1471590Srgrimes free((char *)t->bucketPtr); 1481590Srgrimes 1491590Srgrimes /* 1501590Srgrimes * Set up the hash table to cause memory faults on any future access 1518874Srgrimes * attempts until re-initialization. 1521590Srgrimes */ 1531590Srgrimes t->bucketPtr = NULL; 1541590Srgrimes} 1551590Srgrimes 1561590Srgrimes/* 1571590Srgrimes *--------------------------------------------------------- 1581590Srgrimes * 1591590Srgrimes * Hash_FindEntry -- 1601590Srgrimes * 1611590Srgrimes * Searches a hash table for an entry corresponding to key. 1621590Srgrimes * 1631590Srgrimes * Results: 1641590Srgrimes * The return value is a pointer to the entry for key, 1651590Srgrimes * if key was present in the table. If key was not 1661590Srgrimes * present, NULL is returned. 1671590Srgrimes * 1681590Srgrimes * Side Effects: 1691590Srgrimes * None. 1701590Srgrimes * 1711590Srgrimes *--------------------------------------------------------- 1721590Srgrimes */ 1731590Srgrimes 1741590SrgrimesHash_Entry * 1751590SrgrimesHash_FindEntry(t, key) 1761590Srgrimes Hash_Table *t; /* Hash table to search. */ 1771590Srgrimes char *key; /* A hash key. */ 1781590Srgrimes{ 1791590Srgrimes register Hash_Entry *e; 1801590Srgrimes register unsigned h; 1811590Srgrimes register char *p; 1821590Srgrimes 1831590Srgrimes for (h = 0, p = key; *p;) 1841590Srgrimes h = (h << 5) - h + *p++; 1851590Srgrimes p = key; 1861590Srgrimes for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) 1871590Srgrimes if (e->namehash == h && strcmp(e->name, p) == 0) 1881590Srgrimes return (e); 1891590Srgrimes return (NULL); 1901590Srgrimes} 1911590Srgrimes 1921590Srgrimes/* 1931590Srgrimes *--------------------------------------------------------- 1941590Srgrimes * 1951590Srgrimes * Hash_CreateEntry -- 1961590Srgrimes * 1971590Srgrimes * Searches a hash table for an entry corresponding to 1981590Srgrimes * key. If no entry is found, then one is created. 1991590Srgrimes * 2001590Srgrimes * Results: 2011590Srgrimes * The return value is a pointer to the entry. If *newPtr 2021590Srgrimes * isn't NULL, then *newPtr is filled in with TRUE if a 2031590Srgrimes * new entry was created, and FALSE if an entry already existed 2041590Srgrimes * with the given key. 2051590Srgrimes * 2061590Srgrimes * Side Effects: 2071590Srgrimes * Memory may be allocated, and the hash buckets may be modified. 2081590Srgrimes *--------------------------------------------------------- 2091590Srgrimes */ 2101590Srgrimes 2111590SrgrimesHash_Entry * 2121590SrgrimesHash_CreateEntry(t, key, newPtr) 2131590Srgrimes register Hash_Table *t; /* Hash table to search. */ 2141590Srgrimes char *key; /* A hash key. */ 2151590Srgrimes Boolean *newPtr; /* Filled in with TRUE if new entry created, 2161590Srgrimes * FALSE otherwise. */ 2171590Srgrimes{ 2181590Srgrimes register Hash_Entry *e; 2191590Srgrimes register unsigned h; 2201590Srgrimes register char *p; 2211590Srgrimes int keylen; 2221590Srgrimes struct Hash_Entry **hp; 2231590Srgrimes 2241590Srgrimes /* 2251590Srgrimes * Hash the key. As a side effect, save the length (strlen) of the 2261590Srgrimes * key in case we need to create the entry. 2271590Srgrimes */ 2281590Srgrimes for (h = 0, p = key; *p;) 2291590Srgrimes h = (h << 5) - h + *p++; 2301590Srgrimes keylen = p - key; 2311590Srgrimes p = key; 2321590Srgrimes for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) { 2331590Srgrimes if (e->namehash == h && strcmp(e->name, p) == 0) { 2341590Srgrimes if (newPtr != NULL) 2351590Srgrimes *newPtr = FALSE; 2361590Srgrimes return (e); 2371590Srgrimes } 2381590Srgrimes } 2391590Srgrimes 2401590Srgrimes /* 2411590Srgrimes * The desired entry isn't there. Before allocating a new entry, 2421590Srgrimes * expand the table if necessary (and this changes the resulting 2438874Srgrimes * bucket chain). 2441590Srgrimes */ 2451590Srgrimes if (t->numEntries >= rebuildLimit * t->size) 2461590Srgrimes RebuildTable(t); 2471590Srgrimes e = (Hash_Entry *) emalloc(sizeof(*e) + keylen); 2481590Srgrimes hp = &t->bucketPtr[h & t->mask]; 2491590Srgrimes e->next = *hp; 2501590Srgrimes *hp = e; 2511590Srgrimes e->clientData = NULL; 2521590Srgrimes e->namehash = h; 2531590Srgrimes (void) strcpy(e->name, p); 2541590Srgrimes t->numEntries++; 2551590Srgrimes 2561590Srgrimes if (newPtr != NULL) 2571590Srgrimes *newPtr = TRUE; 2581590Srgrimes return (e); 2591590Srgrimes} 2601590Srgrimes 2611590Srgrimes/* 2621590Srgrimes *--------------------------------------------------------- 2631590Srgrimes * 2641590Srgrimes * Hash_DeleteEntry -- 2651590Srgrimes * 2661590Srgrimes * Delete the given hash table entry and free memory associated with 2671590Srgrimes * it. 2681590Srgrimes * 2691590Srgrimes * Results: 2701590Srgrimes * None. 2711590Srgrimes * 2721590Srgrimes * Side Effects: 2731590Srgrimes * Hash chain that entry lives in is modified and memory is freed. 2741590Srgrimes * 2751590Srgrimes *--------------------------------------------------------- 2761590Srgrimes */ 2771590Srgrimes 2781590Srgrimesvoid 2791590SrgrimesHash_DeleteEntry(t, e) 2801590Srgrimes Hash_Table *t; 2811590Srgrimes Hash_Entry *e; 2821590Srgrimes{ 2831590Srgrimes register Hash_Entry **hp, *p; 2841590Srgrimes 2851590Srgrimes if (e == NULL) 2861590Srgrimes return; 2871590Srgrimes for (hp = &t->bucketPtr[e->namehash & t->mask]; 2881590Srgrimes (p = *hp) != NULL; hp = &p->next) { 2891590Srgrimes if (p == e) { 2901590Srgrimes *hp = p->next; 2911590Srgrimes free((char *)p); 2921590Srgrimes t->numEntries--; 2931590Srgrimes return; 2941590Srgrimes } 2951590Srgrimes } 2961590Srgrimes (void) write(2, "bad call to Hash_DeleteEntry\n", 29); 2971590Srgrimes abort(); 2981590Srgrimes} 2991590Srgrimes 3001590Srgrimes/* 3011590Srgrimes *--------------------------------------------------------- 3021590Srgrimes * 3031590Srgrimes * Hash_EnumFirst -- 3041590Srgrimes * This procedure sets things up for a complete search 3051590Srgrimes * of all entries recorded in the hash table. 3061590Srgrimes * 3078874Srgrimes * Results: 3081590Srgrimes * The return value is the address of the first entry in 3091590Srgrimes * the hash table, or NULL if the table is empty. 3101590Srgrimes * 3111590Srgrimes * Side Effects: 3121590Srgrimes * The information in searchPtr is initialized so that successive 3131590Srgrimes * calls to Hash_Next will return successive HashEntry's 3141590Srgrimes * from the table. 3151590Srgrimes * 3161590Srgrimes *--------------------------------------------------------- 3171590Srgrimes */ 3181590Srgrimes 3191590SrgrimesHash_Entry * 3201590SrgrimesHash_EnumFirst(t, searchPtr) 3211590Srgrimes Hash_Table *t; /* Table to be searched. */ 3228874Srgrimes register Hash_Search *searchPtr;/* Area in which to keep state 3231590Srgrimes * about search.*/ 3241590Srgrimes{ 3251590Srgrimes searchPtr->tablePtr = t; 3261590Srgrimes searchPtr->nextIndex = 0; 3271590Srgrimes searchPtr->hashEntryPtr = NULL; 3281590Srgrimes return Hash_EnumNext(searchPtr); 3291590Srgrimes} 3301590Srgrimes 3311590Srgrimes/* 3321590Srgrimes *--------------------------------------------------------- 3331590Srgrimes * 3341590Srgrimes * Hash_EnumNext -- 3351590Srgrimes * This procedure returns successive entries in the hash table. 3361590Srgrimes * 3371590Srgrimes * Results: 3381590Srgrimes * The return value is a pointer to the next HashEntry 3391590Srgrimes * in the table, or NULL when the end of the table is 3401590Srgrimes * reached. 3411590Srgrimes * 3421590Srgrimes * Side Effects: 3431590Srgrimes * The information in searchPtr is modified to advance to the 3441590Srgrimes * next entry. 3451590Srgrimes * 3461590Srgrimes *--------------------------------------------------------- 3471590Srgrimes */ 3481590Srgrimes 3491590SrgrimesHash_Entry * 3501590SrgrimesHash_EnumNext(searchPtr) 3518874Srgrimes register Hash_Search *searchPtr; /* Area used to keep state about 3521590Srgrimes search. */ 3531590Srgrimes{ 3541590Srgrimes register Hash_Entry *e; 3551590Srgrimes Hash_Table *t = searchPtr->tablePtr; 3561590Srgrimes 3571590Srgrimes /* 3581590Srgrimes * The hashEntryPtr field points to the most recently returned 35969527Swill * entry, or is NULL if we are starting up. If not NULL, we have 3601590Srgrimes * to start at the next one in the chain. 3611590Srgrimes */ 3621590Srgrimes e = searchPtr->hashEntryPtr; 3631590Srgrimes if (e != NULL) 3641590Srgrimes e = e->next; 3651590Srgrimes /* 3661590Srgrimes * If the chain ran out, or if we are starting up, we need to 3671590Srgrimes * find the next nonempty chain. 3681590Srgrimes */ 3691590Srgrimes while (e == NULL) { 3701590Srgrimes if (searchPtr->nextIndex >= t->size) 3711590Srgrimes return (NULL); 3721590Srgrimes e = t->bucketPtr[searchPtr->nextIndex++]; 3731590Srgrimes } 3741590Srgrimes searchPtr->hashEntryPtr = e; 3751590Srgrimes return (e); 3761590Srgrimes} 3771590Srgrimes 3781590Srgrimes/* 3791590Srgrimes *--------------------------------------------------------- 3801590Srgrimes * 3811590Srgrimes * RebuildTable -- 3821590Srgrimes * This local routine makes a new hash table that 3831590Srgrimes * is larger than the old one. 3841590Srgrimes * 3858874Srgrimes * Results: 3861590Srgrimes * None. 3871590Srgrimes * 3881590Srgrimes * Side Effects: 3891590Srgrimes * The entire hash table is moved, so any bucket numbers 3901590Srgrimes * from the old table are invalid. 3911590Srgrimes * 3921590Srgrimes *--------------------------------------------------------- 3931590Srgrimes */ 3941590Srgrimes 3951590Srgrimesstatic void 3961590SrgrimesRebuildTable(t) 3971590Srgrimes register Hash_Table *t; 3981590Srgrimes{ 3991590Srgrimes register Hash_Entry *e, *next = NULL, **hp, **xp; 4001590Srgrimes register int i, mask; 4011590Srgrimes register Hash_Entry **oldhp; 4021590Srgrimes int oldsize; 4031590Srgrimes 4041590Srgrimes oldhp = t->bucketPtr; 4051590Srgrimes oldsize = i = t->size; 4061590Srgrimes i <<= 1; 4071590Srgrimes t->size = i; 4081590Srgrimes t->mask = mask = i - 1; 4091590Srgrimes t->bucketPtr = hp = (struct Hash_Entry **) emalloc(sizeof(*hp) * i); 4101590Srgrimes while (--i >= 0) 4111590Srgrimes *hp++ = NULL; 4121590Srgrimes for (hp = oldhp, i = oldsize; --i >= 0;) { 4131590Srgrimes for (e = *hp++; e != NULL; e = next) { 4141590Srgrimes next = e->next; 4151590Srgrimes xp = &t->bucketPtr[e->namehash & mask]; 4161590Srgrimes e->next = *xp; 4171590Srgrimes *xp = e; 4181590Srgrimes } 4191590Srgrimes } 4201590Srgrimes free((char *)oldhp); 4211590Srgrimes} 422