1276305Sngie/* $NetBSD: hash.c,v 1.20 2013/11/14 00:27:05 sjg Exp $ */ 2236769Sobrien 3236769Sobrien/* 4236769Sobrien * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. 5236769Sobrien * All rights reserved. 6236769Sobrien * 7236769Sobrien * This code is derived from software contributed to Berkeley by 8236769Sobrien * Adam de Boor. 9236769Sobrien * 10236769Sobrien * Redistribution and use in source and binary forms, with or without 11236769Sobrien * modification, are permitted provided that the following conditions 12236769Sobrien * are met: 13236769Sobrien * 1. Redistributions of source code must retain the above copyright 14236769Sobrien * notice, this list of conditions and the following disclaimer. 15236769Sobrien * 2. Redistributions in binary form must reproduce the above copyright 16236769Sobrien * notice, this list of conditions and the following disclaimer in the 17236769Sobrien * documentation and/or other materials provided with the distribution. 18236769Sobrien * 3. Neither the name of the University nor the names of its contributors 19236769Sobrien * may be used to endorse or promote products derived from this software 20236769Sobrien * without specific prior written permission. 21236769Sobrien * 22236769Sobrien * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23236769Sobrien * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24236769Sobrien * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25236769Sobrien * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26236769Sobrien * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27236769Sobrien * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28236769Sobrien * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29236769Sobrien * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30236769Sobrien * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31236769Sobrien * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32236769Sobrien * SUCH DAMAGE. 33236769Sobrien */ 34236769Sobrien 35236769Sobrien/* 36236769Sobrien * Copyright (c) 1988, 1989 by Adam de Boor 37236769Sobrien * Copyright (c) 1989 by Berkeley Softworks 38236769Sobrien * All rights reserved. 39236769Sobrien * 40236769Sobrien * This code is derived from software contributed to Berkeley by 41236769Sobrien * Adam de Boor. 42236769Sobrien * 43236769Sobrien * Redistribution and use in source and binary forms, with or without 44236769Sobrien * modification, are permitted provided that the following conditions 45236769Sobrien * are met: 46236769Sobrien * 1. Redistributions of source code must retain the above copyright 47236769Sobrien * notice, this list of conditions and the following disclaimer. 48236769Sobrien * 2. Redistributions in binary form must reproduce the above copyright 49236769Sobrien * notice, this list of conditions and the following disclaimer in the 50236769Sobrien * documentation and/or other materials provided with the distribution. 51236769Sobrien * 3. All advertising materials mentioning features or use of this software 52236769Sobrien * must display the following acknowledgement: 53236769Sobrien * This product includes software developed by the University of 54236769Sobrien * California, Berkeley and its contributors. 55236769Sobrien * 4. Neither the name of the University nor the names of its contributors 56236769Sobrien * may be used to endorse or promote products derived from this software 57236769Sobrien * without specific prior written permission. 58236769Sobrien * 59236769Sobrien * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 60236769Sobrien * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 61236769Sobrien * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 62236769Sobrien * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 63236769Sobrien * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 64236769Sobrien * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 65236769Sobrien * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 66236769Sobrien * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 67236769Sobrien * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 68236769Sobrien * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 69236769Sobrien * SUCH DAMAGE. 70236769Sobrien */ 71236769Sobrien 72236769Sobrien#ifndef MAKE_NATIVE 73276305Sngiestatic char rcsid[] = "$NetBSD: hash.c,v 1.20 2013/11/14 00:27:05 sjg Exp $"; 74236769Sobrien#else 75236769Sobrien#include <sys/cdefs.h> 76236769Sobrien#ifndef lint 77236769Sobrien#if 0 78236769Sobrienstatic char sccsid[] = "@(#)hash.c 8.1 (Berkeley) 6/6/93"; 79236769Sobrien#else 80276305Sngie__RCSID("$NetBSD: hash.c,v 1.20 2013/11/14 00:27:05 sjg Exp $"); 81236769Sobrien#endif 82236769Sobrien#endif /* not lint */ 83236769Sobrien#endif 84236769Sobrien 85236769Sobrien/* hash.c -- 86236769Sobrien * 87236769Sobrien * This module contains routines to manipulate a hash table. 88236769Sobrien * See hash.h for a definition of the structure of the hash 89236769Sobrien * table. Hash tables grow automatically as the amount of 90236769Sobrien * information increases. 91236769Sobrien */ 92236769Sobrien#include "sprite.h" 93236769Sobrien#include "make.h" 94236769Sobrien#include "hash.h" 95236769Sobrien 96236769Sobrien/* 97236769Sobrien * Forward references to local procedures that are used before they're 98236769Sobrien * defined: 99236769Sobrien */ 100236769Sobrien 101236769Sobrienstatic void RebuildTable(Hash_Table *); 102236769Sobrien 103236769Sobrien/* 104236769Sobrien * The following defines the ratio of # entries to # buckets 105236769Sobrien * at which we rebuild the table to make it larger. 106236769Sobrien */ 107236769Sobrien 108236769Sobrien#define rebuildLimit 3 109236769Sobrien 110236769Sobrien/* 111236769Sobrien *--------------------------------------------------------- 112236769Sobrien * 113236769Sobrien * Hash_InitTable -- 114236769Sobrien * 115236769Sobrien * This routine just sets up the hash table. 116236769Sobrien * 117236769Sobrien * Input: 118236769Sobrien * t Structure to to hold table. 119236769Sobrien * numBuckets How many buckets to create for starters. This 120236769Sobrien * number is rounded up to a power of two. If 121236769Sobrien * <= 0, a reasonable default is chosen. The 122236769Sobrien * table will grow in size later as needed. 123236769Sobrien * 124236769Sobrien * Results: 125236769Sobrien * None. 126236769Sobrien * 127236769Sobrien * Side Effects: 128236769Sobrien * Memory is allocated for the initial bucket area. 129236769Sobrien * 130236769Sobrien *--------------------------------------------------------- 131236769Sobrien */ 132236769Sobrien 133236769Sobrienvoid 134236769SobrienHash_InitTable(Hash_Table *t, int numBuckets) 135236769Sobrien{ 136236769Sobrien int i; 137236769Sobrien struct Hash_Entry **hp; 138236769Sobrien 139236769Sobrien /* 140236769Sobrien * Round up the size to a power of two. 141236769Sobrien */ 142236769Sobrien if (numBuckets <= 0) 143236769Sobrien i = 16; 144236769Sobrien else { 145236769Sobrien for (i = 2; i < numBuckets; i <<= 1) 146236769Sobrien continue; 147236769Sobrien } 148236769Sobrien t->numEntries = 0; 149236769Sobrien t->size = i; 150236769Sobrien t->mask = i - 1; 151236769Sobrien t->bucketPtr = hp = bmake_malloc(sizeof(*hp) * i); 152236769Sobrien while (--i >= 0) 153236769Sobrien *hp++ = NULL; 154236769Sobrien} 155236769Sobrien 156236769Sobrien/* 157236769Sobrien *--------------------------------------------------------- 158236769Sobrien * 159236769Sobrien * Hash_DeleteTable -- 160236769Sobrien * 161236769Sobrien * This routine removes everything from a hash table 162236769Sobrien * and frees up the memory space it occupied (except for 163236769Sobrien * the space in the Hash_Table structure). 164236769Sobrien * 165236769Sobrien * Results: 166236769Sobrien * None. 167236769Sobrien * 168236769Sobrien * Side Effects: 169236769Sobrien * Lots of memory is freed up. 170236769Sobrien * 171236769Sobrien *--------------------------------------------------------- 172236769Sobrien */ 173236769Sobrien 174236769Sobrienvoid 175236769SobrienHash_DeleteTable(Hash_Table *t) 176236769Sobrien{ 177236769Sobrien struct Hash_Entry **hp, *h, *nexth = NULL; 178236769Sobrien int i; 179236769Sobrien 180236769Sobrien for (hp = t->bucketPtr, i = t->size; --i >= 0;) { 181236769Sobrien for (h = *hp++; h != NULL; h = nexth) { 182236769Sobrien nexth = h->next; 183236769Sobrien free(h); 184236769Sobrien } 185236769Sobrien } 186236769Sobrien free(t->bucketPtr); 187236769Sobrien 188236769Sobrien /* 189236769Sobrien * Set up the hash table to cause memory faults on any future access 190236769Sobrien * attempts until re-initialization. 191236769Sobrien */ 192236769Sobrien t->bucketPtr = NULL; 193236769Sobrien} 194236769Sobrien 195236769Sobrien/* 196236769Sobrien *--------------------------------------------------------- 197236769Sobrien * 198236769Sobrien * Hash_FindEntry -- 199236769Sobrien * 200236769Sobrien * Searches a hash table for an entry corresponding to key. 201236769Sobrien * 202236769Sobrien * Input: 203236769Sobrien * t Hash table to search. 204236769Sobrien * key A hash key. 205236769Sobrien * 206236769Sobrien * Results: 207236769Sobrien * The return value is a pointer to the entry for key, 208236769Sobrien * if key was present in the table. If key was not 209236769Sobrien * present, NULL is returned. 210236769Sobrien * 211236769Sobrien * Side Effects: 212236769Sobrien * None. 213236769Sobrien * 214236769Sobrien *--------------------------------------------------------- 215236769Sobrien */ 216236769Sobrien 217236769SobrienHash_Entry * 218236769SobrienHash_FindEntry(Hash_Table *t, const char *key) 219236769Sobrien{ 220236769Sobrien Hash_Entry *e; 221236769Sobrien unsigned h; 222236769Sobrien const char *p; 223236769Sobrien 224276305Sngie if (t == NULL || t->bucketPtr == NULL) { 225276305Sngie return NULL; 226276305Sngie } 227236769Sobrien for (h = 0, p = key; *p;) 228236769Sobrien h = (h << 5) - h + *p++; 229236769Sobrien p = key; 230236769Sobrien for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) 231236769Sobrien if (e->namehash == h && strcmp(e->name, p) == 0) 232236769Sobrien return (e); 233236769Sobrien return NULL; 234236769Sobrien} 235236769Sobrien 236236769Sobrien/* 237236769Sobrien *--------------------------------------------------------- 238236769Sobrien * 239236769Sobrien * Hash_CreateEntry -- 240236769Sobrien * 241236769Sobrien * Searches a hash table for an entry corresponding to 242236769Sobrien * key. If no entry is found, then one is created. 243236769Sobrien * 244236769Sobrien * Input: 245236769Sobrien * t Hash table to search. 246236769Sobrien * key A hash key. 247236769Sobrien * newPtr Filled in with TRUE if new entry created, 248236769Sobrien * FALSE otherwise. 249236769Sobrien * 250236769Sobrien * Results: 251236769Sobrien * The return value is a pointer to the entry. If *newPtr 252236769Sobrien * isn't NULL, then *newPtr is filled in with TRUE if a 253236769Sobrien * new entry was created, and FALSE if an entry already existed 254236769Sobrien * with the given key. 255236769Sobrien * 256236769Sobrien * Side Effects: 257236769Sobrien * Memory may be allocated, and the hash buckets may be modified. 258236769Sobrien *--------------------------------------------------------- 259236769Sobrien */ 260236769Sobrien 261236769SobrienHash_Entry * 262236769SobrienHash_CreateEntry(Hash_Table *t, const char *key, Boolean *newPtr) 263236769Sobrien{ 264236769Sobrien Hash_Entry *e; 265236769Sobrien unsigned h; 266236769Sobrien const char *p; 267236769Sobrien int keylen; 268236769Sobrien struct Hash_Entry **hp; 269236769Sobrien 270236769Sobrien /* 271236769Sobrien * Hash the key. As a side effect, save the length (strlen) of the 272236769Sobrien * key in case we need to create the entry. 273236769Sobrien */ 274236769Sobrien for (h = 0, p = key; *p;) 275236769Sobrien h = (h << 5) - h + *p++; 276236769Sobrien keylen = p - key; 277236769Sobrien p = key; 278236769Sobrien for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) { 279236769Sobrien if (e->namehash == h && strcmp(e->name, p) == 0) { 280236769Sobrien if (newPtr != NULL) 281236769Sobrien *newPtr = FALSE; 282236769Sobrien return (e); 283236769Sobrien } 284236769Sobrien } 285236769Sobrien 286236769Sobrien /* 287236769Sobrien * The desired entry isn't there. Before allocating a new entry, 288236769Sobrien * expand the table if necessary (and this changes the resulting 289236769Sobrien * bucket chain). 290236769Sobrien */ 291236769Sobrien if (t->numEntries >= rebuildLimit * t->size) 292236769Sobrien RebuildTable(t); 293236769Sobrien e = bmake_malloc(sizeof(*e) + keylen); 294236769Sobrien hp = &t->bucketPtr[h & t->mask]; 295236769Sobrien e->next = *hp; 296236769Sobrien *hp = e; 297236769Sobrien Hash_SetValue(e, NULL); 298236769Sobrien e->namehash = h; 299236769Sobrien (void)strcpy(e->name, p); 300236769Sobrien t->numEntries++; 301236769Sobrien 302236769Sobrien if (newPtr != NULL) 303236769Sobrien *newPtr = TRUE; 304236769Sobrien return (e); 305236769Sobrien} 306236769Sobrien 307236769Sobrien/* 308236769Sobrien *--------------------------------------------------------- 309236769Sobrien * 310236769Sobrien * Hash_DeleteEntry -- 311236769Sobrien * 312236769Sobrien * Delete the given hash table entry and free memory associated with 313236769Sobrien * it. 314236769Sobrien * 315236769Sobrien * Results: 316236769Sobrien * None. 317236769Sobrien * 318236769Sobrien * Side Effects: 319236769Sobrien * Hash chain that entry lives in is modified and memory is freed. 320236769Sobrien * 321236769Sobrien *--------------------------------------------------------- 322236769Sobrien */ 323236769Sobrien 324236769Sobrienvoid 325236769SobrienHash_DeleteEntry(Hash_Table *t, Hash_Entry *e) 326236769Sobrien{ 327236769Sobrien Hash_Entry **hp, *p; 328236769Sobrien 329236769Sobrien if (e == NULL) 330236769Sobrien return; 331236769Sobrien for (hp = &t->bucketPtr[e->namehash & t->mask]; 332236769Sobrien (p = *hp) != NULL; hp = &p->next) { 333236769Sobrien if (p == e) { 334236769Sobrien *hp = p->next; 335236769Sobrien free(p); 336236769Sobrien t->numEntries--; 337236769Sobrien return; 338236769Sobrien } 339236769Sobrien } 340236769Sobrien (void)write(2, "bad call to Hash_DeleteEntry\n", 29); 341236769Sobrien abort(); 342236769Sobrien} 343236769Sobrien 344236769Sobrien/* 345236769Sobrien *--------------------------------------------------------- 346236769Sobrien * 347236769Sobrien * Hash_EnumFirst -- 348236769Sobrien * This procedure sets things up for a complete search 349236769Sobrien * of all entries recorded in the hash table. 350236769Sobrien * 351236769Sobrien * Input: 352236769Sobrien * t Table to be searched. 353236769Sobrien * searchPtr Area in which to keep state about search. 354236769Sobrien * 355236769Sobrien * Results: 356236769Sobrien * The return value is the address of the first entry in 357236769Sobrien * the hash table, or NULL if the table is empty. 358236769Sobrien * 359236769Sobrien * Side Effects: 360236769Sobrien * The information in searchPtr is initialized so that successive 361236769Sobrien * calls to Hash_Next will return successive HashEntry's 362236769Sobrien * from the table. 363236769Sobrien * 364236769Sobrien *--------------------------------------------------------- 365236769Sobrien */ 366236769Sobrien 367236769SobrienHash_Entry * 368236769SobrienHash_EnumFirst(Hash_Table *t, Hash_Search *searchPtr) 369236769Sobrien{ 370236769Sobrien searchPtr->tablePtr = t; 371236769Sobrien searchPtr->nextIndex = 0; 372236769Sobrien searchPtr->hashEntryPtr = NULL; 373236769Sobrien return Hash_EnumNext(searchPtr); 374236769Sobrien} 375236769Sobrien 376236769Sobrien/* 377236769Sobrien *--------------------------------------------------------- 378236769Sobrien * 379236769Sobrien * Hash_EnumNext -- 380236769Sobrien * This procedure returns successive entries in the hash table. 381236769Sobrien * 382236769Sobrien * Input: 383236769Sobrien * searchPtr Area used to keep state about search. 384236769Sobrien * 385236769Sobrien * Results: 386236769Sobrien * The return value is a pointer to the next HashEntry 387236769Sobrien * in the table, or NULL when the end of the table is 388236769Sobrien * reached. 389236769Sobrien * 390236769Sobrien * Side Effects: 391236769Sobrien * The information in searchPtr is modified to advance to the 392236769Sobrien * next entry. 393236769Sobrien * 394236769Sobrien *--------------------------------------------------------- 395236769Sobrien */ 396236769Sobrien 397236769SobrienHash_Entry * 398236769SobrienHash_EnumNext(Hash_Search *searchPtr) 399236769Sobrien{ 400236769Sobrien Hash_Entry *e; 401236769Sobrien Hash_Table *t = searchPtr->tablePtr; 402236769Sobrien 403236769Sobrien /* 404236769Sobrien * The hashEntryPtr field points to the most recently returned 405236769Sobrien * entry, or is nil if we are starting up. If not nil, we have 406236769Sobrien * to start at the next one in the chain. 407236769Sobrien */ 408236769Sobrien e = searchPtr->hashEntryPtr; 409236769Sobrien if (e != NULL) 410236769Sobrien e = e->next; 411236769Sobrien /* 412236769Sobrien * If the chain ran out, or if we are starting up, we need to 413236769Sobrien * find the next nonempty chain. 414236769Sobrien */ 415236769Sobrien while (e == NULL) { 416236769Sobrien if (searchPtr->nextIndex >= t->size) 417236769Sobrien return NULL; 418236769Sobrien e = t->bucketPtr[searchPtr->nextIndex++]; 419236769Sobrien } 420236769Sobrien searchPtr->hashEntryPtr = e; 421236769Sobrien return (e); 422236769Sobrien} 423236769Sobrien 424236769Sobrien/* 425236769Sobrien *--------------------------------------------------------- 426236769Sobrien * 427236769Sobrien * RebuildTable -- 428236769Sobrien * This local routine makes a new hash table that 429236769Sobrien * is larger than the old one. 430236769Sobrien * 431236769Sobrien * Results: 432236769Sobrien * None. 433236769Sobrien * 434236769Sobrien * Side Effects: 435236769Sobrien * The entire hash table is moved, so any bucket numbers 436236769Sobrien * from the old table are invalid. 437236769Sobrien * 438236769Sobrien *--------------------------------------------------------- 439236769Sobrien */ 440236769Sobrien 441236769Sobrienstatic void 442236769SobrienRebuildTable(Hash_Table *t) 443236769Sobrien{ 444236769Sobrien Hash_Entry *e, *next = NULL, **hp, **xp; 445236769Sobrien int i, mask; 446236769Sobrien Hash_Entry **oldhp; 447236769Sobrien int oldsize; 448236769Sobrien 449236769Sobrien oldhp = t->bucketPtr; 450236769Sobrien oldsize = i = t->size; 451236769Sobrien i <<= 1; 452236769Sobrien t->size = i; 453236769Sobrien t->mask = mask = i - 1; 454236769Sobrien t->bucketPtr = hp = bmake_malloc(sizeof(*hp) * i); 455236769Sobrien while (--i >= 0) 456236769Sobrien *hp++ = NULL; 457236769Sobrien for (hp = oldhp, i = oldsize; --i >= 0;) { 458236769Sobrien for (e = *hp++; e != NULL; e = next) { 459236769Sobrien next = e->next; 460236769Sobrien xp = &t->bucketPtr[e->namehash & mask]; 461236769Sobrien e->next = *xp; 462236769Sobrien *xp = e; 463236769Sobrien } 464236769Sobrien } 465236769Sobrien free(oldhp); 466236769Sobrien} 467