hash.c revision 173412
1173412Skevlo/* $FreeBSD: head/sbin/rcorder/hash.c 173412 2007-11-07 10:53:41Z kevlo $ */ 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 10678344SobrienHash_InitTable(t, numBuckets) 10778344Sobrien register Hash_Table *t; /* Structure to use to hold table. */ 10878344Sobrien 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 15378344SobrienHash_DeleteTable(t) 15478344Sobrien Hash_Table *t; 15578344Sobrien{ 15678344Sobrien register struct Hash_Entry **hp, *h, *nexth = NULL; 15778344Sobrien register int i; 15878344Sobrien 15978344Sobrien for (hp = t->bucketPtr, i = t->size; --i >= 0;) { 16078344Sobrien for (h = *hp++; h != NULL; h = nexth) { 16178344Sobrien nexth = h->next; 16278344Sobrien free((char *)h); 16378344Sobrien } 16478344Sobrien } 16578344Sobrien free((char *)t->bucketPtr); 16678344Sobrien 16778344Sobrien /* 16878344Sobrien * Set up the hash table to cause memory faults on any future access 16978344Sobrien * attempts until re-initialization. 17078344Sobrien */ 17178344Sobrien t->bucketPtr = NULL; 17278344Sobrien} 17378344Sobrien 17478344Sobrien/* 17578344Sobrien *--------------------------------------------------------- 17678344Sobrien * 17778344Sobrien * Hash_FindEntry -- 17878344Sobrien * 17978344Sobrien * Searches a hash table for an entry corresponding to key. 18078344Sobrien * 18178344Sobrien * Results: 18278344Sobrien * The return value is a pointer to the entry for key, 18378344Sobrien * if key was present in the table. If key was not 18478344Sobrien * present, NULL is returned. 18578344Sobrien * 18678344Sobrien * Side Effects: 18778344Sobrien * None. 18878344Sobrien * 18978344Sobrien *--------------------------------------------------------- 19078344Sobrien */ 19178344Sobrien 19278344SobrienHash_Entry * 19378344SobrienHash_FindEntry(t, key) 19478344Sobrien Hash_Table *t; /* Hash table to search. */ 19578344Sobrien char *key; /* A hash key. */ 19678344Sobrien{ 19778344Sobrien register Hash_Entry *e; 19878344Sobrien register unsigned h; 19978344Sobrien register char *p; 20078344Sobrien 20178344Sobrien for (h = 0, p = key; *p;) 20278344Sobrien h = (h << 5) - h + *p++; 20378344Sobrien p = key; 20478344Sobrien for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) 20578344Sobrien if (e->namehash == h && strcmp(e->name, p) == 0) 20678344Sobrien return (e); 20778344Sobrien return (NULL); 20878344Sobrien} 20978344Sobrien 21078344Sobrien/* 21178344Sobrien *--------------------------------------------------------- 21278344Sobrien * 21378344Sobrien * Hash_CreateEntry -- 21478344Sobrien * 21578344Sobrien * Searches a hash table for an entry corresponding to 21678344Sobrien * key. If no entry is found, then one is created. 21778344Sobrien * 21878344Sobrien * Results: 21978344Sobrien * The return value is a pointer to the entry. If *newPtr 22078344Sobrien * isn't NULL, then *newPtr is filled in with TRUE if a 22178344Sobrien * new entry was created, and FALSE if an entry already existed 22278344Sobrien * with the given key. 22378344Sobrien * 22478344Sobrien * Side Effects: 22578344Sobrien * Memory may be allocated, and the hash buckets may be modified. 22678344Sobrien *--------------------------------------------------------- 22778344Sobrien */ 22878344Sobrien 22978344SobrienHash_Entry * 23078344SobrienHash_CreateEntry(t, key, newPtr) 23178344Sobrien register Hash_Table *t; /* Hash table to search. */ 23278344Sobrien char *key; /* A hash key. */ 23378344Sobrien Boolean *newPtr; /* Filled in with TRUE if new entry created, 23478344Sobrien * FALSE otherwise. */ 23578344Sobrien{ 23678344Sobrien register Hash_Entry *e; 23778344Sobrien register unsigned h; 23878344Sobrien register char *p; 23978344Sobrien int keylen; 24078344Sobrien struct Hash_Entry **hp; 24178344Sobrien 24278344Sobrien /* 24378344Sobrien * Hash the key. As a side effect, save the length (strlen) of the 24478344Sobrien * key in case we need to create the entry. 24578344Sobrien */ 24678344Sobrien for (h = 0, p = key; *p;) 24778344Sobrien h = (h << 5) - h + *p++; 24878344Sobrien keylen = p - key; 24978344Sobrien p = key; 25078344Sobrien for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) { 25178344Sobrien if (e->namehash == h && strcmp(e->name, p) == 0) { 25278344Sobrien if (newPtr != NULL) 25378344Sobrien *newPtr = FALSE; 25478344Sobrien return (e); 25578344Sobrien } 25678344Sobrien } 25778344Sobrien 25878344Sobrien /* 25978344Sobrien * The desired entry isn't there. Before allocating a new entry, 26078344Sobrien * expand the table if necessary (and this changes the resulting 26178344Sobrien * bucket chain). 26278344Sobrien */ 26378344Sobrien if (t->numEntries >= rebuildLimit * t->size) 26478344Sobrien RebuildTable(t); 26578344Sobrien e = (Hash_Entry *) emalloc(sizeof(*e) + keylen); 26678344Sobrien hp = &t->bucketPtr[h & t->mask]; 26778344Sobrien e->next = *hp; 26878344Sobrien *hp = e; 26978344Sobrien e->clientData = NULL; 27078344Sobrien e->namehash = h; 27178344Sobrien (void) strcpy(e->name, p); 27278344Sobrien t->numEntries++; 27378344Sobrien 27478344Sobrien if (newPtr != NULL) 27578344Sobrien *newPtr = TRUE; 27678344Sobrien return (e); 27778344Sobrien} 27878344Sobrien 27978344Sobrien/* 28078344Sobrien *--------------------------------------------------------- 28178344Sobrien * 28278344Sobrien * Hash_DeleteEntry -- 28378344Sobrien * 28478344Sobrien * Delete the given hash table entry and free memory associated with 28578344Sobrien * it. 28678344Sobrien * 28778344Sobrien * Results: 28878344Sobrien * None. 28978344Sobrien * 29078344Sobrien * Side Effects: 29178344Sobrien * Hash chain that entry lives in is modified and memory is freed. 29278344Sobrien * 29378344Sobrien *--------------------------------------------------------- 29478344Sobrien */ 29578344Sobrien 29678344Sobrienvoid 29778344SobrienHash_DeleteEntry(t, e) 29878344Sobrien Hash_Table *t; 29978344Sobrien Hash_Entry *e; 30078344Sobrien{ 30178344Sobrien register Hash_Entry **hp, *p; 30278344Sobrien 30378344Sobrien if (e == NULL) 30478344Sobrien return; 30578344Sobrien for (hp = &t->bucketPtr[e->namehash & t->mask]; 30678344Sobrien (p = *hp) != NULL; hp = &p->next) { 30778344Sobrien if (p == e) { 30878344Sobrien *hp = p->next; 30978344Sobrien free((char *)p); 31078344Sobrien t->numEntries--; 31178344Sobrien return; 31278344Sobrien } 31378344Sobrien } 31478344Sobrien (void)write(2, "bad call to Hash_DeleteEntry\n", 29); 31578344Sobrien abort(); 31678344Sobrien} 31778344Sobrien 31878344Sobrien/* 31978344Sobrien *--------------------------------------------------------- 32078344Sobrien * 32178344Sobrien * Hash_EnumFirst -- 32278344Sobrien * This procedure sets things up for a complete search 32378344Sobrien * of all entries recorded in the hash table. 32478344Sobrien * 32578344Sobrien * Results: 32678344Sobrien * The return value is the address of the first entry in 32778344Sobrien * the hash table, or NULL if the table is empty. 32878344Sobrien * 32978344Sobrien * Side Effects: 33078344Sobrien * The information in searchPtr is initialized so that successive 33178344Sobrien * calls to Hash_Next will return successive HashEntry's 33278344Sobrien * from the table. 33378344Sobrien * 33478344Sobrien *--------------------------------------------------------- 33578344Sobrien */ 33678344Sobrien 33778344SobrienHash_Entry * 33878344SobrienHash_EnumFirst(t, searchPtr) 33978344Sobrien Hash_Table *t; /* Table to be searched. */ 34078344Sobrien register Hash_Search *searchPtr;/* Area in which to keep state 34178344Sobrien * about search.*/ 34278344Sobrien{ 34378344Sobrien searchPtr->tablePtr = t; 34478344Sobrien searchPtr->nextIndex = 0; 34578344Sobrien searchPtr->hashEntryPtr = NULL; 34678344Sobrien return Hash_EnumNext(searchPtr); 34778344Sobrien} 34878344Sobrien 34978344Sobrien/* 35078344Sobrien *--------------------------------------------------------- 35178344Sobrien * 35278344Sobrien * Hash_EnumNext -- 35378344Sobrien * This procedure returns successive entries in the hash table. 35478344Sobrien * 35578344Sobrien * Results: 35678344Sobrien * The return value is a pointer to the next HashEntry 35778344Sobrien * in the table, or NULL when the end of the table is 35878344Sobrien * reached. 35978344Sobrien * 36078344Sobrien * Side Effects: 36178344Sobrien * The information in searchPtr is modified to advance to the 36278344Sobrien * next entry. 36378344Sobrien * 36478344Sobrien *--------------------------------------------------------- 36578344Sobrien */ 36678344Sobrien 36778344SobrienHash_Entry * 36878344SobrienHash_EnumNext(searchPtr) 36978344Sobrien register Hash_Search *searchPtr; /* Area used to keep state about 37078344Sobrien search. */ 37178344Sobrien{ 37278344Sobrien register Hash_Entry *e; 37378344Sobrien Hash_Table *t = searchPtr->tablePtr; 37478344Sobrien 37578344Sobrien /* 37678344Sobrien * The hashEntryPtr field points to the most recently returned 37778344Sobrien * entry, or is nil if we are starting up. If not nil, we have 37878344Sobrien * to start at the next one in the chain. 37978344Sobrien */ 38078344Sobrien e = searchPtr->hashEntryPtr; 38178344Sobrien if (e != NULL) 38278344Sobrien e = e->next; 38378344Sobrien /* 38478344Sobrien * If the chain ran out, or if we are starting up, we need to 38578344Sobrien * find the next nonempty chain. 38678344Sobrien */ 38778344Sobrien while (e == NULL) { 38878344Sobrien if (searchPtr->nextIndex >= t->size) 38978344Sobrien return (NULL); 39078344Sobrien e = t->bucketPtr[searchPtr->nextIndex++]; 39178344Sobrien } 39278344Sobrien searchPtr->hashEntryPtr = e; 39378344Sobrien return (e); 39478344Sobrien} 39578344Sobrien 39678344Sobrien/* 39778344Sobrien *--------------------------------------------------------- 39878344Sobrien * 39978344Sobrien * RebuildTable -- 40078344Sobrien * This local routine makes a new hash table that 40178344Sobrien * is larger than the old one. 40278344Sobrien * 40378344Sobrien * Results: 40478344Sobrien * None. 40578344Sobrien * 40678344Sobrien * Side Effects: 40778344Sobrien * The entire hash table is moved, so any bucket numbers 40878344Sobrien * from the old table are invalid. 40978344Sobrien * 41078344Sobrien *--------------------------------------------------------- 41178344Sobrien */ 41278344Sobrien 41378344Sobrienstatic void 41478344SobrienRebuildTable(t) 41578344Sobrien register Hash_Table *t; 41678344Sobrien{ 41778344Sobrien register Hash_Entry *e, *next = NULL, **hp, **xp; 41878344Sobrien register int i, mask; 41978344Sobrien register Hash_Entry **oldhp; 42078344Sobrien int oldsize; 42178344Sobrien 42278344Sobrien oldhp = t->bucketPtr; 42378344Sobrien oldsize = i = t->size; 42478344Sobrien i <<= 1; 42578344Sobrien t->size = i; 42678344Sobrien t->mask = mask = i - 1; 42778344Sobrien t->bucketPtr = hp = (struct Hash_Entry **) emalloc(sizeof(*hp) * i); 42878344Sobrien while (--i >= 0) 42978344Sobrien *hp++ = NULL; 43078344Sobrien for (hp = oldhp, i = oldsize; --i >= 0;) { 43178344Sobrien for (e = *hp++; e != NULL; e = next) { 43278344Sobrien next = e->next; 43378344Sobrien xp = &t->bucketPtr[e->namehash & mask]; 43478344Sobrien e->next = *xp; 43578344Sobrien *xp = e; 43678344Sobrien } 43778344Sobrien } 43878344Sobrien free((char *)oldhp); 43978344Sobrien} 440