1173412Skevlo/* $FreeBSD$ */ 278344Sobrien/* $NetBSD: hash.c,v 1.1.1.1 1999/11/19 04:30:56 mrg Exp $ */ 378344Sobrien 478344Sobrien/* 578344Sobrien * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. 678344Sobrien * Copyright (c) 1988, 1989 by Adam de Boor 778344Sobrien * Copyright (c) 1989 by Berkeley Softworks 878344Sobrien * All rights reserved. 978344Sobrien * 1078344Sobrien * This code is derived from software contributed to Berkeley by 1178344Sobrien * Adam de Boor. 1278344Sobrien * 1378344Sobrien * Redistribution and use in source and binary forms, with or without 1478344Sobrien * modification, are permitted provided that the following conditions 1578344Sobrien * are met: 1678344Sobrien * 1. Redistributions of source code must retain the above copyright 1778344Sobrien * notice, this list of conditions and the following disclaimer. 1878344Sobrien * 2. Redistributions in binary form must reproduce the above copyright 1978344Sobrien * notice, this list of conditions and the following disclaimer in the 2078344Sobrien * documentation and/or other materials provided with the distribution. 2178344Sobrien * 3. All advertising materials mentioning features or use of this software 2278344Sobrien * must display the following acknowledgement: 2378344Sobrien * This product includes software developed by the University of 2478344Sobrien * California, Berkeley and its contributors. 2578344Sobrien * 4. Neither the name of the University nor the names of its contributors 2678344Sobrien * may be used to endorse or promote products derived from this software 2778344Sobrien * without specific prior written permission. 2878344Sobrien * 2978344Sobrien * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 3078344Sobrien * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 3178344Sobrien * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 3278344Sobrien * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 3378344Sobrien * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 3478344Sobrien * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 3578344Sobrien * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 3678344Sobrien * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 3778344Sobrien * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 3878344Sobrien * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 3978344Sobrien * SUCH DAMAGE. 4078344Sobrien */ 4178344Sobrien 4278344Sobrien#ifdef MAKE_BOOTSTRAP 4378344Sobrienstatic char rcsid[] = "$NetBSD: hash.c,v 1.1.1.1 1999/11/19 04:30:56 mrg Exp $"; 4478344Sobrien#else 4578344Sobrien#include <sys/cdefs.h> 4678344Sobrien#ifndef lint 4778344Sobrien#if 0 4878344Sobrienstatic char sccsid[] = "@(#)hash.c 8.1 (Berkeley) 6/6/93"; 4978344Sobrien#else 5078344Sobrien__RCSID("$NetBSD: hash.c,v 1.1.1.1 1999/11/19 04:30:56 mrg Exp $"); 5178344Sobrien#endif 5278344Sobrien#endif /* not lint */ 5378344Sobrien#endif 5478344Sobrien 5578344Sobrien#include <sys/types.h> 5678344Sobrien 5778344Sobrien#include <stdlib.h> 5878344Sobrien#include <string.h> 5978344Sobrien#include <unistd.h> 6078344Sobrien 6178344Sobrien/* hash.c -- 6278344Sobrien * 6378344Sobrien * This module contains routines to manipulate a hash table. 6478344Sobrien * See hash.h for a definition of the structure of the hash 6578344Sobrien * table. Hash tables grow automatically as the amount of 6678344Sobrien * information increases. 6778344Sobrien */ 6878344Sobrien#include "sprite.h" 6978344Sobrien#ifndef ORDER 7078344Sobrien#include "make.h" 7178344Sobrien#endif /* ORDER */ 7278344Sobrien#include "hash.h" 7378344Sobrien#include "ealloc.h" 7478344Sobrien 7578344Sobrien/* 7678344Sobrien * Forward references to local procedures that are used before they're 7778344Sobrien * defined: 7878344Sobrien */ 7978344Sobrien 80173412Skevlostatic void RebuildTable(Hash_Table *); 8178344Sobrien 8278344Sobrien/* 8378344Sobrien * The following defines the ratio of # entries to # buckets 8478344Sobrien * at which we rebuild the table to make it larger. 8578344Sobrien */ 8678344Sobrien 8778344Sobrien#define rebuildLimit 8 8878344Sobrien 8978344Sobrien/* 9078344Sobrien *--------------------------------------------------------- 9178344Sobrien * 9278344Sobrien * Hash_InitTable -- 9378344Sobrien * 9478344Sobrien * This routine just sets up the hash table. 9578344Sobrien * 9678344Sobrien * Results: 9778344Sobrien * None. 9878344Sobrien * 9978344Sobrien * Side Effects: 10078344Sobrien * Memory is allocated for the initial bucket area. 10178344Sobrien * 10278344Sobrien *--------------------------------------------------------- 10378344Sobrien */ 10478344Sobrien 10578344Sobrienvoid 106201227SedHash_InitTable( 107201227Sed register Hash_Table *t, /* Structure to use to hold table. */ 108201227Sed int numBuckets) /* How many buckets to create for starters. 10978344Sobrien * This number is rounded up to a power of 11078344Sobrien * two. If <= 0, a reasonable default is 11178344Sobrien * chosen. The table will grow in size later 11278344Sobrien * as needed. */ 11378344Sobrien{ 11478344Sobrien register int i; 11578344Sobrien register struct Hash_Entry **hp; 11678344Sobrien 11778344Sobrien /* 11878344Sobrien * Round up the size to a power of two. 11978344Sobrien */ 12078344Sobrien if (numBuckets <= 0) 12178344Sobrien i = 16; 12278344Sobrien else { 12378344Sobrien for (i = 2; i < numBuckets; i <<= 1) 12478344Sobrien continue; 12578344Sobrien } 12678344Sobrien t->numEntries = 0; 12778344Sobrien t->size = i; 12878344Sobrien t->mask = i - 1; 12978344Sobrien t->bucketPtr = hp = (struct Hash_Entry **)emalloc(sizeof(*hp) * i); 13078344Sobrien while (--i >= 0) 13178344Sobrien *hp++ = NULL; 13278344Sobrien} 13378344Sobrien 13478344Sobrien/* 13578344Sobrien *--------------------------------------------------------- 13678344Sobrien * 13778344Sobrien * Hash_DeleteTable -- 13878344Sobrien * 13978344Sobrien * This routine removes everything from a hash table 14078344Sobrien * and frees up the memory space it occupied (except for 14178344Sobrien * the space in the Hash_Table structure). 14278344Sobrien * 14378344Sobrien * Results: 14478344Sobrien * None. 14578344Sobrien * 14678344Sobrien * Side Effects: 14778344Sobrien * Lots of memory is freed up. 14878344Sobrien * 14978344Sobrien *--------------------------------------------------------- 15078344Sobrien */ 15178344Sobrien 15278344Sobrienvoid 153201227SedHash_DeleteTable(Hash_Table *t) 15478344Sobrien{ 15578344Sobrien register struct Hash_Entry **hp, *h, *nexth = NULL; 15678344Sobrien register int i; 15778344Sobrien 15878344Sobrien for (hp = t->bucketPtr, i = t->size; --i >= 0;) { 15978344Sobrien for (h = *hp++; h != NULL; h = nexth) { 16078344Sobrien nexth = h->next; 16178344Sobrien free((char *)h); 16278344Sobrien } 16378344Sobrien } 16478344Sobrien free((char *)t->bucketPtr); 16578344Sobrien 16678344Sobrien /* 16778344Sobrien * Set up the hash table to cause memory faults on any future access 16878344Sobrien * attempts until re-initialization. 16978344Sobrien */ 17078344Sobrien t->bucketPtr = NULL; 17178344Sobrien} 17278344Sobrien 17378344Sobrien/* 17478344Sobrien *--------------------------------------------------------- 17578344Sobrien * 17678344Sobrien * Hash_FindEntry -- 17778344Sobrien * 17878344Sobrien * Searches a hash table for an entry corresponding to key. 17978344Sobrien * 18078344Sobrien * Results: 18178344Sobrien * The return value is a pointer to the entry for key, 18278344Sobrien * if key was present in the table. If key was not 18378344Sobrien * present, NULL is returned. 18478344Sobrien * 18578344Sobrien * Side Effects: 18678344Sobrien * None. 18778344Sobrien * 18878344Sobrien *--------------------------------------------------------- 18978344Sobrien */ 19078344Sobrien 19178344SobrienHash_Entry * 192201227SedHash_FindEntry( 193201227Sed Hash_Table *t, /* Hash table to search. */ 194201227Sed char *key) /* A hash key. */ 19578344Sobrien{ 19678344Sobrien register Hash_Entry *e; 19778344Sobrien register unsigned h; 19878344Sobrien register char *p; 19978344Sobrien 20078344Sobrien for (h = 0, p = key; *p;) 20178344Sobrien h = (h << 5) - h + *p++; 20278344Sobrien p = key; 20378344Sobrien for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) 20478344Sobrien if (e->namehash == h && strcmp(e->name, p) == 0) 20578344Sobrien return (e); 20678344Sobrien return (NULL); 20778344Sobrien} 20878344Sobrien 20978344Sobrien/* 21078344Sobrien *--------------------------------------------------------- 21178344Sobrien * 21278344Sobrien * Hash_CreateEntry -- 21378344Sobrien * 21478344Sobrien * Searches a hash table for an entry corresponding to 21578344Sobrien * key. If no entry is found, then one is created. 21678344Sobrien * 21778344Sobrien * Results: 21878344Sobrien * The return value is a pointer to the entry. If *newPtr 21978344Sobrien * isn't NULL, then *newPtr is filled in with TRUE if a 22078344Sobrien * new entry was created, and FALSE if an entry already existed 22178344Sobrien * with the given key. 22278344Sobrien * 22378344Sobrien * Side Effects: 22478344Sobrien * Memory may be allocated, and the hash buckets may be modified. 22578344Sobrien *--------------------------------------------------------- 22678344Sobrien */ 22778344Sobrien 22878344SobrienHash_Entry * 229201227SedHash_CreateEntry( 230201227Sed register Hash_Table *t, /* Hash table to search. */ 231201227Sed char *key, /* A hash key. */ 232201227Sed Boolean *newPtr) /* Filled in with TRUE if new entry created, 23378344Sobrien * FALSE otherwise. */ 23478344Sobrien{ 23578344Sobrien register Hash_Entry *e; 23678344Sobrien register unsigned h; 23778344Sobrien register char *p; 23878344Sobrien int keylen; 23978344Sobrien struct Hash_Entry **hp; 24078344Sobrien 24178344Sobrien /* 24278344Sobrien * Hash the key. As a side effect, save the length (strlen) of the 24378344Sobrien * key in case we need to create the entry. 24478344Sobrien */ 24578344Sobrien for (h = 0, p = key; *p;) 24678344Sobrien h = (h << 5) - h + *p++; 24778344Sobrien keylen = p - key; 24878344Sobrien p = key; 24978344Sobrien for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) { 25078344Sobrien if (e->namehash == h && strcmp(e->name, p) == 0) { 25178344Sobrien if (newPtr != NULL) 25278344Sobrien *newPtr = FALSE; 25378344Sobrien return (e); 25478344Sobrien } 25578344Sobrien } 25678344Sobrien 25778344Sobrien /* 25878344Sobrien * The desired entry isn't there. Before allocating a new entry, 25978344Sobrien * expand the table if necessary (and this changes the resulting 26078344Sobrien * bucket chain). 26178344Sobrien */ 26278344Sobrien if (t->numEntries >= rebuildLimit * t->size) 26378344Sobrien RebuildTable(t); 26478344Sobrien e = (Hash_Entry *) emalloc(sizeof(*e) + keylen); 26578344Sobrien hp = &t->bucketPtr[h & t->mask]; 26678344Sobrien e->next = *hp; 26778344Sobrien *hp = e; 26878344Sobrien e->clientData = NULL; 26978344Sobrien e->namehash = h; 27078344Sobrien (void) strcpy(e->name, p); 27178344Sobrien t->numEntries++; 27278344Sobrien 27378344Sobrien if (newPtr != NULL) 27478344Sobrien *newPtr = TRUE; 27578344Sobrien return (e); 27678344Sobrien} 27778344Sobrien 27878344Sobrien/* 27978344Sobrien *--------------------------------------------------------- 28078344Sobrien * 28178344Sobrien * Hash_DeleteEntry -- 28278344Sobrien * 28378344Sobrien * Delete the given hash table entry and free memory associated with 28478344Sobrien * it. 28578344Sobrien * 28678344Sobrien * Results: 28778344Sobrien * None. 28878344Sobrien * 28978344Sobrien * Side Effects: 29078344Sobrien * Hash chain that entry lives in is modified and memory is freed. 29178344Sobrien * 29278344Sobrien *--------------------------------------------------------- 29378344Sobrien */ 29478344Sobrien 29578344Sobrienvoid 296201227SedHash_DeleteEntry(Hash_Table *t, Hash_Entry *e) 29778344Sobrien{ 29878344Sobrien register Hash_Entry **hp, *p; 29978344Sobrien 30078344Sobrien if (e == NULL) 30178344Sobrien return; 30278344Sobrien for (hp = &t->bucketPtr[e->namehash & t->mask]; 30378344Sobrien (p = *hp) != NULL; hp = &p->next) { 30478344Sobrien if (p == e) { 30578344Sobrien *hp = p->next; 30678344Sobrien free((char *)p); 30778344Sobrien t->numEntries--; 30878344Sobrien return; 30978344Sobrien } 31078344Sobrien } 31178344Sobrien (void)write(2, "bad call to Hash_DeleteEntry\n", 29); 31278344Sobrien abort(); 31378344Sobrien} 31478344Sobrien 31578344Sobrien/* 31678344Sobrien *--------------------------------------------------------- 31778344Sobrien * 31878344Sobrien * Hash_EnumFirst -- 31978344Sobrien * This procedure sets things up for a complete search 32078344Sobrien * of all entries recorded in the hash table. 32178344Sobrien * 32278344Sobrien * Results: 32378344Sobrien * The return value is the address of the first entry in 32478344Sobrien * the hash table, or NULL if the table is empty. 32578344Sobrien * 32678344Sobrien * Side Effects: 32778344Sobrien * The information in searchPtr is initialized so that successive 32878344Sobrien * calls to Hash_Next will return successive HashEntry's 32978344Sobrien * from the table. 33078344Sobrien * 33178344Sobrien *--------------------------------------------------------- 33278344Sobrien */ 33378344Sobrien 33478344SobrienHash_Entry * 335201227SedHash_EnumFirst( 336201227Sed Hash_Table *t, /* Table to be searched. */ 337201227Sed register Hash_Search *searchPtr)/* Area in which to keep state 33878344Sobrien * about search.*/ 33978344Sobrien{ 34078344Sobrien searchPtr->tablePtr = t; 34178344Sobrien searchPtr->nextIndex = 0; 34278344Sobrien searchPtr->hashEntryPtr = NULL; 34378344Sobrien return Hash_EnumNext(searchPtr); 34478344Sobrien} 34578344Sobrien 34678344Sobrien/* 34778344Sobrien *--------------------------------------------------------- 34878344Sobrien * 34978344Sobrien * Hash_EnumNext -- 35078344Sobrien * This procedure returns successive entries in the hash table. 35178344Sobrien * 35278344Sobrien * Results: 35378344Sobrien * The return value is a pointer to the next HashEntry 35478344Sobrien * in the table, or NULL when the end of the table is 35578344Sobrien * reached. 35678344Sobrien * 35778344Sobrien * Side Effects: 35878344Sobrien * The information in searchPtr is modified to advance to the 35978344Sobrien * next entry. 36078344Sobrien * 36178344Sobrien *--------------------------------------------------------- 36278344Sobrien */ 36378344Sobrien 36478344SobrienHash_Entry * 365201227SedHash_EnumNext( 366201227Sed register Hash_Search *searchPtr) /* Area used to keep state about 36778344Sobrien search. */ 36878344Sobrien{ 36978344Sobrien register Hash_Entry *e; 37078344Sobrien Hash_Table *t = searchPtr->tablePtr; 37178344Sobrien 37278344Sobrien /* 37378344Sobrien * The hashEntryPtr field points to the most recently returned 37478344Sobrien * entry, or is nil if we are starting up. If not nil, we have 37578344Sobrien * to start at the next one in the chain. 37678344Sobrien */ 37778344Sobrien e = searchPtr->hashEntryPtr; 37878344Sobrien if (e != NULL) 37978344Sobrien e = e->next; 38078344Sobrien /* 38178344Sobrien * If the chain ran out, or if we are starting up, we need to 38278344Sobrien * find the next nonempty chain. 38378344Sobrien */ 38478344Sobrien while (e == NULL) { 38578344Sobrien if (searchPtr->nextIndex >= t->size) 38678344Sobrien return (NULL); 38778344Sobrien e = t->bucketPtr[searchPtr->nextIndex++]; 38878344Sobrien } 38978344Sobrien searchPtr->hashEntryPtr = e; 39078344Sobrien return (e); 39178344Sobrien} 39278344Sobrien 39378344Sobrien/* 39478344Sobrien *--------------------------------------------------------- 39578344Sobrien * 39678344Sobrien * RebuildTable -- 39778344Sobrien * This local routine makes a new hash table that 39878344Sobrien * is larger than the old one. 39978344Sobrien * 40078344Sobrien * Results: 40178344Sobrien * None. 40278344Sobrien * 40378344Sobrien * Side Effects: 40478344Sobrien * The entire hash table is moved, so any bucket numbers 40578344Sobrien * from the old table are invalid. 40678344Sobrien * 40778344Sobrien *--------------------------------------------------------- 40878344Sobrien */ 40978344Sobrien 41078344Sobrienstatic void 411201227SedRebuildTable(register Hash_Table *t) 41278344Sobrien{ 41378344Sobrien register Hash_Entry *e, *next = NULL, **hp, **xp; 41478344Sobrien register int i, mask; 41578344Sobrien register Hash_Entry **oldhp; 41678344Sobrien int oldsize; 41778344Sobrien 41878344Sobrien oldhp = t->bucketPtr; 41978344Sobrien oldsize = i = t->size; 42078344Sobrien i <<= 1; 42178344Sobrien t->size = i; 42278344Sobrien t->mask = mask = i - 1; 42378344Sobrien t->bucketPtr = hp = (struct Hash_Entry **) emalloc(sizeof(*hp) * i); 42478344Sobrien while (--i >= 0) 42578344Sobrien *hp++ = NULL; 42678344Sobrien for (hp = oldhp, i = oldsize; --i >= 0;) { 42778344Sobrien for (e = *hp++; e != NULL; e = next) { 42878344Sobrien next = e->next; 42978344Sobrien xp = &t->bucketPtr[e->namehash & mask]; 43078344Sobrien e->next = *xp; 43178344Sobrien *xp = e; 43278344Sobrien } 43378344Sobrien } 43478344Sobrien free((char *)oldhp); 43578344Sobrien} 436