1141104Sharti/*- 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$"); 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 */ 52141104Sharti 53141104Sharti#include <stdlib.h> 54141104Sharti#include <string.h> 5580381Ssheldonh#include <unistd.h> 56141104Sharti 57141104Sharti#include "hash.h" 58141104Sharti#include "util.h" 591590Srgrimes 601590Srgrimes/* 611590Srgrimes * Forward references to local procedures that are used before they're 621590Srgrimes * defined: 631590Srgrimes */ 6492921Simpstatic void RebuildTable(Hash_Table *); 651590Srgrimes 668874Srgrimes/* 671590Srgrimes * The following defines the ratio of # entries to # buckets 681590Srgrimes * at which we rebuild the table to make it larger. 691590Srgrimes */ 701590Srgrimes 71103503Sjmallett#define rebuildLimit 8 721590Srgrimes 731590Srgrimes/* 741590Srgrimes *--------------------------------------------------------- 758874Srgrimes * 761590Srgrimes * Hash_InitTable -- 77138232Sharti * 78104696Sjmallett * Set up the hash table t with a given number of buckets, or a 79104696Sjmallett * reasonable default if the number requested is less than or 80104696Sjmallett * equal to zero. Hash tables will grow in size as needed. 811590Srgrimes * 821590Srgrimes * 838874Srgrimes * Results: 841590Srgrimes * None. 851590Srgrimes * 861590Srgrimes * Side Effects: 871590Srgrimes * Memory is allocated for the initial bucket area. 881590Srgrimes * 891590Srgrimes *--------------------------------------------------------- 901590Srgrimes */ 911590Srgrimesvoid 92104696SjmallettHash_InitTable(Hash_Table *t, int numBuckets) 931590Srgrimes{ 9494584Sobrien int i; 9594584Sobrien struct Hash_Entry **hp; 961590Srgrimes 971590Srgrimes /* 988874Srgrimes * Round up the size to a power of two. 991590Srgrimes */ 1001590Srgrimes if (numBuckets <= 0) 1011590Srgrimes i = 16; 1021590Srgrimes else { 1031590Srgrimes for (i = 2; i < numBuckets; i <<= 1) 1041590Srgrimes continue; 1051590Srgrimes } 1061590Srgrimes t->numEntries = 0; 1071590Srgrimes t->size = i; 1081590Srgrimes t->mask = i - 1; 109138264Sharti t->bucketPtr = hp = emalloc(sizeof(*hp) * i); 1101590Srgrimes while (--i >= 0) 1111590Srgrimes *hp++ = NULL; 1121590Srgrimes} 1131590Srgrimes 1141590Srgrimes/* 1151590Srgrimes *--------------------------------------------------------- 1161590Srgrimes * 1171590Srgrimes * Hash_DeleteTable -- 1181590Srgrimes * 1191590Srgrimes * This routine removes everything from a hash table 1201590Srgrimes * and frees up the memory space it occupied (except for 1211590Srgrimes * the space in the Hash_Table structure). 1221590Srgrimes * 1238874Srgrimes * Results: 1241590Srgrimes * None. 1251590Srgrimes * 1261590Srgrimes * Side Effects: 1271590Srgrimes * Lots of memory is freed up. 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; 140138264Sharti free(h); 1411590Srgrimes } 1421590Srgrimes } 143138264Sharti free(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 */ 1691590SrgrimesHash_Entry * 170138435ShartiHash_FindEntry(const Hash_Table *t, const char *key) 1711590Srgrimes{ 17294584Sobrien Hash_Entry *e; 17394584Sobrien unsigned h; 174138435Sharti const char *p; 1751590Srgrimes 1761590Srgrimes for (h = 0, p = key; *p;) 1771590Srgrimes h = (h << 5) - h + *p++; 1781590Srgrimes p = key; 1791590Srgrimes for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) 1801590Srgrimes if (e->namehash == h && strcmp(e->name, p) == 0) 1811590Srgrimes return (e); 1821590Srgrimes return (NULL); 1831590Srgrimes} 1841590Srgrimes 1851590Srgrimes/* 1861590Srgrimes *--------------------------------------------------------- 1871590Srgrimes * 1881590Srgrimes * Hash_CreateEntry -- 1891590Srgrimes * 1901590Srgrimes * Searches a hash table for an entry corresponding to 1911590Srgrimes * key. If no entry is found, then one is created. 1921590Srgrimes * 1931590Srgrimes * Results: 1941590Srgrimes * The return value is a pointer to the entry. If *newPtr 1951590Srgrimes * isn't NULL, then *newPtr is filled in with TRUE if a 1961590Srgrimes * new entry was created, and FALSE if an entry already existed 1971590Srgrimes * with the given key. 1981590Srgrimes * 1991590Srgrimes * Side Effects: 2001590Srgrimes * Memory may be allocated, and the hash buckets may be modified. 2011590Srgrimes *--------------------------------------------------------- 2021590Srgrimes */ 2031590SrgrimesHash_Entry * 204138435ShartiHash_CreateEntry(Hash_Table *t, const char *key, Boolean *newPtr) 2051590Srgrimes{ 20694584Sobrien Hash_Entry *e; 207104696Sjmallett unsigned int h; 208138435Sharti const char *p; 2091590Srgrimes int keylen; 2101590Srgrimes struct Hash_Entry **hp; 2111590Srgrimes 2121590Srgrimes /* 2131590Srgrimes * Hash the key. As a side effect, save the length (strlen) of the 2141590Srgrimes * key in case we need to create the entry. 2151590Srgrimes */ 2161590Srgrimes for (h = 0, p = key; *p;) 2171590Srgrimes h = (h << 5) - h + *p++; 2181590Srgrimes keylen = p - key; 2191590Srgrimes p = key; 2201590Srgrimes for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) { 2211590Srgrimes if (e->namehash == h && strcmp(e->name, p) == 0) { 2221590Srgrimes if (newPtr != NULL) 2231590Srgrimes *newPtr = FALSE; 2241590Srgrimes return (e); 2251590Srgrimes } 2261590Srgrimes } 2271590Srgrimes 2281590Srgrimes /* 2291590Srgrimes * The desired entry isn't there. Before allocating a new entry, 2301590Srgrimes * expand the table if necessary (and this changes the resulting 2318874Srgrimes * bucket chain). 2321590Srgrimes */ 2331590Srgrimes if (t->numEntries >= rebuildLimit * t->size) 2341590Srgrimes RebuildTable(t); 235138264Sharti e = emalloc(sizeof(*e) + keylen); 2361590Srgrimes hp = &t->bucketPtr[h & t->mask]; 2371590Srgrimes e->next = *hp; 2381590Srgrimes *hp = e; 2391590Srgrimes e->clientData = NULL; 2401590Srgrimes e->namehash = h; 241138232Sharti strcpy(e->name, p); 2421590Srgrimes t->numEntries++; 2431590Srgrimes 2441590Srgrimes if (newPtr != NULL) 2451590Srgrimes *newPtr = TRUE; 2461590Srgrimes return (e); 2471590Srgrimes} 2481590Srgrimes 2491590Srgrimes/* 2501590Srgrimes *--------------------------------------------------------- 2511590Srgrimes * 2521590Srgrimes * Hash_DeleteEntry -- 2531590Srgrimes * 2541590Srgrimes * Delete the given hash table entry and free memory associated with 2551590Srgrimes * it. 2561590Srgrimes * 2571590Srgrimes * Results: 2581590Srgrimes * None. 2591590Srgrimes * 2601590Srgrimes * Side Effects: 2611590Srgrimes * Hash chain that entry lives in is modified and memory is freed. 2621590Srgrimes * 2631590Srgrimes *--------------------------------------------------------- 2641590Srgrimes */ 2651590Srgrimesvoid 266104696SjmallettHash_DeleteEntry(Hash_Table *t, Hash_Entry *e) 2671590Srgrimes{ 26894584Sobrien Hash_Entry **hp, *p; 2691590Srgrimes 2701590Srgrimes if (e == NULL) 2711590Srgrimes return; 2721590Srgrimes for (hp = &t->bucketPtr[e->namehash & t->mask]; 2731590Srgrimes (p = *hp) != NULL; hp = &p->next) { 2741590Srgrimes if (p == e) { 2751590Srgrimes *hp = p->next; 276138264Sharti free(p); 2771590Srgrimes t->numEntries--; 2781590Srgrimes return; 2791590Srgrimes } 2801590Srgrimes } 281138232Sharti write(STDERR_FILENO, "bad call to Hash_DeleteEntry\n", 29); 2821590Srgrimes abort(); 2831590Srgrimes} 2841590Srgrimes 2851590Srgrimes/* 2861590Srgrimes *--------------------------------------------------------- 2871590Srgrimes * 2881590Srgrimes * Hash_EnumFirst -- 2891590Srgrimes * This procedure sets things up for a complete search 2901590Srgrimes * of all entries recorded in the hash table. 2911590Srgrimes * 2928874Srgrimes * Results: 2931590Srgrimes * The return value is the address of the first entry in 2941590Srgrimes * the hash table, or NULL if the table is empty. 2951590Srgrimes * 2961590Srgrimes * Side Effects: 2971590Srgrimes * The information in searchPtr is initialized so that successive 2981590Srgrimes * calls to Hash_Next will return successive HashEntry's 2991590Srgrimes * from the table. 3001590Srgrimes * 3011590Srgrimes *--------------------------------------------------------- 3021590Srgrimes */ 3031590SrgrimesHash_Entry * 304138455ShartiHash_EnumFirst(const Hash_Table *t, Hash_Search *searchPtr) 3051590Srgrimes{ 306138232Sharti 3071590Srgrimes searchPtr->tablePtr = t; 3081590Srgrimes searchPtr->nextIndex = 0; 3091590Srgrimes searchPtr->hashEntryPtr = NULL; 310138232Sharti return (Hash_EnumNext(searchPtr)); 3111590Srgrimes} 3121590Srgrimes 3131590Srgrimes/* 3141590Srgrimes *--------------------------------------------------------- 3151590Srgrimes * 3161590Srgrimes * Hash_EnumNext -- 3171590Srgrimes * This procedure returns successive entries in the hash table. 3181590Srgrimes * 3191590Srgrimes * Results: 3201590Srgrimes * The return value is a pointer to the next HashEntry 3211590Srgrimes * in the table, or NULL when the end of the table is 3221590Srgrimes * reached. 3231590Srgrimes * 3241590Srgrimes * Side Effects: 3251590Srgrimes * The information in searchPtr is modified to advance to the 3261590Srgrimes * next entry. 3271590Srgrimes * 3281590Srgrimes *--------------------------------------------------------- 3291590Srgrimes */ 3301590SrgrimesHash_Entry * 331104696SjmallettHash_EnumNext(Hash_Search *searchPtr) 3321590Srgrimes{ 33394584Sobrien Hash_Entry *e; 334138455Sharti const Hash_Table *t = searchPtr->tablePtr; 3351590Srgrimes 3361590Srgrimes /* 3371590Srgrimes * The hashEntryPtr field points to the most recently returned 33869527Swill * entry, or is NULL if we are starting up. If not NULL, we have 3391590Srgrimes * to start at the next one in the chain. 3401590Srgrimes */ 3411590Srgrimes e = searchPtr->hashEntryPtr; 3421590Srgrimes if (e != NULL) 3431590Srgrimes e = e->next; 3441590Srgrimes /* 3451590Srgrimes * If the chain ran out, or if we are starting up, we need to 3461590Srgrimes * find the next nonempty chain. 3471590Srgrimes */ 3481590Srgrimes while (e == NULL) { 3491590Srgrimes if (searchPtr->nextIndex >= t->size) 3501590Srgrimes return (NULL); 3511590Srgrimes e = t->bucketPtr[searchPtr->nextIndex++]; 3521590Srgrimes } 3531590Srgrimes searchPtr->hashEntryPtr = e; 3541590Srgrimes return (e); 3551590Srgrimes} 3561590Srgrimes 3571590Srgrimes/* 3581590Srgrimes *--------------------------------------------------------- 3591590Srgrimes * 3601590Srgrimes * RebuildTable -- 3611590Srgrimes * This local routine makes a new hash table that 3621590Srgrimes * is larger than the old one. 3631590Srgrimes * 3648874Srgrimes * Results: 3651590Srgrimes * None. 3661590Srgrimes * 3671590Srgrimes * Side Effects: 3681590Srgrimes * The entire hash table is moved, so any bucket numbers 3691590Srgrimes * from the old table are invalid. 3701590Srgrimes * 3711590Srgrimes *--------------------------------------------------------- 3721590Srgrimes */ 3731590Srgrimesstatic void 374104696SjmallettRebuildTable(Hash_Table *t) 3751590Srgrimes{ 37694584Sobrien Hash_Entry *e, *next = NULL, **hp, **xp; 37794584Sobrien int i, mask; 37894584Sobrien Hash_Entry **oldhp; 3791590Srgrimes int oldsize; 3801590Srgrimes 3811590Srgrimes oldhp = t->bucketPtr; 3821590Srgrimes oldsize = i = t->size; 3831590Srgrimes i <<= 1; 3841590Srgrimes t->size = i; 3851590Srgrimes t->mask = mask = i - 1; 386138264Sharti t->bucketPtr = hp = emalloc(sizeof(*hp) * i); 3871590Srgrimes while (--i >= 0) 3881590Srgrimes *hp++ = NULL; 3891590Srgrimes for (hp = oldhp, i = oldsize; --i >= 0;) { 3901590Srgrimes for (e = *hp++; e != NULL; e = next) { 3911590Srgrimes next = e->next; 3921590Srgrimes xp = &t->bucketPtr[e->namehash & mask]; 3931590Srgrimes e->next = *xp; 3941590Srgrimes *xp = e; 3951590Srgrimes } 3961590Srgrimes } 397138264Sharti free(oldhp); 3981590Srgrimes} 399