19d62501fSDavid E. O'Brien /* $NetBSD: hash.c,v 1.1.1.1 1999/11/19 04:30:56 mrg Exp $ */ 29d62501fSDavid E. O'Brien 39d62501fSDavid E. O'Brien /* 49d62501fSDavid E. O'Brien * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. 59d62501fSDavid E. O'Brien * Copyright (c) 1988, 1989 by Adam de Boor 69d62501fSDavid E. O'Brien * Copyright (c) 1989 by Berkeley Softworks 79d62501fSDavid E. O'Brien * All rights reserved. 89d62501fSDavid E. O'Brien * 99d62501fSDavid E. O'Brien * This code is derived from software contributed to Berkeley by 109d62501fSDavid E. O'Brien * Adam de Boor. 119d62501fSDavid E. O'Brien * 129d62501fSDavid E. O'Brien * Redistribution and use in source and binary forms, with or without 139d62501fSDavid E. O'Brien * modification, are permitted provided that the following conditions 149d62501fSDavid E. O'Brien * are met: 159d62501fSDavid E. O'Brien * 1. Redistributions of source code must retain the above copyright 169d62501fSDavid E. O'Brien * notice, this list of conditions and the following disclaimer. 179d62501fSDavid E. O'Brien * 2. Redistributions in binary form must reproduce the above copyright 189d62501fSDavid E. O'Brien * notice, this list of conditions and the following disclaimer in the 199d62501fSDavid E. O'Brien * documentation and/or other materials provided with the distribution. 209d62501fSDavid E. O'Brien * 3. All advertising materials mentioning features or use of this software 219d62501fSDavid E. O'Brien * must display the following acknowledgement: 229d62501fSDavid E. O'Brien * This product includes software developed by the University of 239d62501fSDavid E. O'Brien * California, Berkeley and its contributors. 249d62501fSDavid E. O'Brien * 4. Neither the name of the University nor the names of its contributors 259d62501fSDavid E. O'Brien * may be used to endorse or promote products derived from this software 269d62501fSDavid E. O'Brien * without specific prior written permission. 279d62501fSDavid E. O'Brien * 289d62501fSDavid E. O'Brien * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 299d62501fSDavid E. O'Brien * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 309d62501fSDavid E. O'Brien * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 319d62501fSDavid E. O'Brien * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 329d62501fSDavid E. O'Brien * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 339d62501fSDavid E. O'Brien * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 349d62501fSDavid E. O'Brien * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 359d62501fSDavid E. O'Brien * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 369d62501fSDavid E. O'Brien * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 379d62501fSDavid E. O'Brien * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 389d62501fSDavid E. O'Brien * SUCH DAMAGE. 399d62501fSDavid E. O'Brien */ 409d62501fSDavid E. O'Brien 419d62501fSDavid E. O'Brien #ifdef MAKE_BOOTSTRAP 429d62501fSDavid E. O'Brien static char rcsid[] = "$NetBSD: hash.c,v 1.1.1.1 1999/11/19 04:30:56 mrg Exp $"; 439d62501fSDavid E. O'Brien #else 449d62501fSDavid E. O'Brien #include <sys/cdefs.h> 459d62501fSDavid E. O'Brien #ifndef lint 469d62501fSDavid E. O'Brien #if 0 479d62501fSDavid E. O'Brien static char sccsid[] = "@(#)hash.c 8.1 (Berkeley) 6/6/93"; 489d62501fSDavid E. O'Brien #else 499d62501fSDavid E. O'Brien __RCSID("$NetBSD: hash.c,v 1.1.1.1 1999/11/19 04:30:56 mrg Exp $"); 509d62501fSDavid E. O'Brien #endif 519d62501fSDavid E. O'Brien #endif /* not lint */ 529d62501fSDavid E. O'Brien #endif 539d62501fSDavid E. O'Brien 549d62501fSDavid E. O'Brien #include <sys/types.h> 559d62501fSDavid E. O'Brien 569d62501fSDavid E. O'Brien #include <stdlib.h> 579d62501fSDavid E. O'Brien #include <string.h> 589d62501fSDavid E. O'Brien #include <unistd.h> 599d62501fSDavid E. O'Brien 609d62501fSDavid E. O'Brien /* hash.c -- 619d62501fSDavid E. O'Brien * 629d62501fSDavid E. O'Brien * This module contains routines to manipulate a hash table. 639d62501fSDavid E. O'Brien * See hash.h for a definition of the structure of the hash 649d62501fSDavid E. O'Brien * table. Hash tables grow automatically as the amount of 659d62501fSDavid E. O'Brien * information increases. 669d62501fSDavid E. O'Brien */ 679d62501fSDavid E. O'Brien #include "sprite.h" 689d62501fSDavid E. O'Brien #ifndef ORDER 699d62501fSDavid E. O'Brien #include "make.h" 709d62501fSDavid E. O'Brien #endif /* ORDER */ 719d62501fSDavid E. O'Brien #include "hash.h" 729d62501fSDavid E. O'Brien #include "ealloc.h" 739d62501fSDavid E. O'Brien 749d62501fSDavid E. O'Brien /* 759d62501fSDavid E. O'Brien * Forward references to local procedures that are used before they're 769d62501fSDavid E. O'Brien * defined: 779d62501fSDavid E. O'Brien */ 789d62501fSDavid E. O'Brien 799d62501fSDavid E. O'Brien static void RebuildTable __P((Hash_Table *)); 809d62501fSDavid E. O'Brien 819d62501fSDavid E. O'Brien /* 829d62501fSDavid E. O'Brien * The following defines the ratio of # entries to # buckets 839d62501fSDavid E. O'Brien * at which we rebuild the table to make it larger. 849d62501fSDavid E. O'Brien */ 859d62501fSDavid E. O'Brien 869d62501fSDavid E. O'Brien #define rebuildLimit 8 879d62501fSDavid E. O'Brien 889d62501fSDavid E. O'Brien /* 899d62501fSDavid E. O'Brien *--------------------------------------------------------- 909d62501fSDavid E. O'Brien * 919d62501fSDavid E. O'Brien * Hash_InitTable -- 929d62501fSDavid E. O'Brien * 939d62501fSDavid E. O'Brien * This routine just sets up the hash table. 949d62501fSDavid E. O'Brien * 959d62501fSDavid E. O'Brien * Results: 969d62501fSDavid E. O'Brien * None. 979d62501fSDavid E. O'Brien * 989d62501fSDavid E. O'Brien * Side Effects: 999d62501fSDavid E. O'Brien * Memory is allocated for the initial bucket area. 1009d62501fSDavid E. O'Brien * 1019d62501fSDavid E. O'Brien *--------------------------------------------------------- 1029d62501fSDavid E. O'Brien */ 1039d62501fSDavid E. O'Brien 1049d62501fSDavid E. O'Brien void 1059d62501fSDavid E. O'Brien Hash_InitTable(t, numBuckets) 1069d62501fSDavid E. O'Brien register Hash_Table *t; /* Structure to use to hold table. */ 1079d62501fSDavid E. O'Brien int numBuckets; /* How many buckets to create for starters. 1089d62501fSDavid E. O'Brien * This number is rounded up to a power of 1099d62501fSDavid E. O'Brien * two. If <= 0, a reasonable default is 1109d62501fSDavid E. O'Brien * chosen. The table will grow in size later 1119d62501fSDavid E. O'Brien * as needed. */ 1129d62501fSDavid E. O'Brien { 1139d62501fSDavid E. O'Brien register int i; 1149d62501fSDavid E. O'Brien register struct Hash_Entry **hp; 1159d62501fSDavid E. O'Brien 1169d62501fSDavid E. O'Brien /* 1179d62501fSDavid E. O'Brien * Round up the size to a power of two. 1189d62501fSDavid E. O'Brien */ 1199d62501fSDavid E. O'Brien if (numBuckets <= 0) 1209d62501fSDavid E. O'Brien i = 16; 1219d62501fSDavid E. O'Brien else { 1229d62501fSDavid E. O'Brien for (i = 2; i < numBuckets; i <<= 1) 1239d62501fSDavid E. O'Brien continue; 1249d62501fSDavid E. O'Brien } 1259d62501fSDavid E. O'Brien t->numEntries = 0; 1269d62501fSDavid E. O'Brien t->size = i; 1279d62501fSDavid E. O'Brien t->mask = i - 1; 1289d62501fSDavid E. O'Brien t->bucketPtr = hp = (struct Hash_Entry **)emalloc(sizeof(*hp) * i); 1299d62501fSDavid E. O'Brien while (--i >= 0) 1309d62501fSDavid E. O'Brien *hp++ = NULL; 1319d62501fSDavid E. O'Brien } 1329d62501fSDavid E. O'Brien 1339d62501fSDavid E. O'Brien /* 1349d62501fSDavid E. O'Brien *--------------------------------------------------------- 1359d62501fSDavid E. O'Brien * 1369d62501fSDavid E. O'Brien * Hash_DeleteTable -- 1379d62501fSDavid E. O'Brien * 1389d62501fSDavid E. O'Brien * This routine removes everything from a hash table 1399d62501fSDavid E. O'Brien * and frees up the memory space it occupied (except for 1409d62501fSDavid E. O'Brien * the space in the Hash_Table structure). 1419d62501fSDavid E. O'Brien * 1429d62501fSDavid E. O'Brien * Results: 1439d62501fSDavid E. O'Brien * None. 1449d62501fSDavid E. O'Brien * 1459d62501fSDavid E. O'Brien * Side Effects: 1469d62501fSDavid E. O'Brien * Lots of memory is freed up. 1479d62501fSDavid E. O'Brien * 1489d62501fSDavid E. O'Brien *--------------------------------------------------------- 1499d62501fSDavid E. O'Brien */ 1509d62501fSDavid E. O'Brien 1519d62501fSDavid E. O'Brien void 1529d62501fSDavid E. O'Brien Hash_DeleteTable(t) 1539d62501fSDavid E. O'Brien Hash_Table *t; 1549d62501fSDavid E. O'Brien { 1559d62501fSDavid E. O'Brien register struct Hash_Entry **hp, *h, *nexth = NULL; 1569d62501fSDavid E. O'Brien register int i; 1579d62501fSDavid E. O'Brien 1589d62501fSDavid E. O'Brien for (hp = t->bucketPtr, i = t->size; --i >= 0;) { 1599d62501fSDavid E. O'Brien for (h = *hp++; h != NULL; h = nexth) { 1609d62501fSDavid E. O'Brien nexth = h->next; 1619d62501fSDavid E. O'Brien free((char *)h); 1629d62501fSDavid E. O'Brien } 1639d62501fSDavid E. O'Brien } 1649d62501fSDavid E. O'Brien free((char *)t->bucketPtr); 1659d62501fSDavid E. O'Brien 1669d62501fSDavid E. O'Brien /* 1679d62501fSDavid E. O'Brien * Set up the hash table to cause memory faults on any future access 1689d62501fSDavid E. O'Brien * attempts until re-initialization. 1699d62501fSDavid E. O'Brien */ 1709d62501fSDavid E. O'Brien t->bucketPtr = NULL; 1719d62501fSDavid E. O'Brien } 1729d62501fSDavid E. O'Brien 1739d62501fSDavid E. O'Brien /* 1749d62501fSDavid E. O'Brien *--------------------------------------------------------- 1759d62501fSDavid E. O'Brien * 1769d62501fSDavid E. O'Brien * Hash_FindEntry -- 1779d62501fSDavid E. O'Brien * 1789d62501fSDavid E. O'Brien * Searches a hash table for an entry corresponding to key. 1799d62501fSDavid E. O'Brien * 1809d62501fSDavid E. O'Brien * Results: 1819d62501fSDavid E. O'Brien * The return value is a pointer to the entry for key, 1829d62501fSDavid E. O'Brien * if key was present in the table. If key was not 1839d62501fSDavid E. O'Brien * present, NULL is returned. 1849d62501fSDavid E. O'Brien * 1859d62501fSDavid E. O'Brien * Side Effects: 1869d62501fSDavid E. O'Brien * None. 1879d62501fSDavid E. O'Brien * 1889d62501fSDavid E. O'Brien *--------------------------------------------------------- 1899d62501fSDavid E. O'Brien */ 1909d62501fSDavid E. O'Brien 1919d62501fSDavid E. O'Brien Hash_Entry * 1929d62501fSDavid E. O'Brien Hash_FindEntry(t, key) 1939d62501fSDavid E. O'Brien Hash_Table *t; /* Hash table to search. */ 1949d62501fSDavid E. O'Brien char *key; /* A hash key. */ 1959d62501fSDavid E. O'Brien { 1969d62501fSDavid E. O'Brien register Hash_Entry *e; 1979d62501fSDavid E. O'Brien register unsigned h; 1989d62501fSDavid E. O'Brien register char *p; 1999d62501fSDavid E. O'Brien 2009d62501fSDavid E. O'Brien for (h = 0, p = key; *p;) 2019d62501fSDavid E. O'Brien h = (h << 5) - h + *p++; 2029d62501fSDavid E. O'Brien p = key; 2039d62501fSDavid E. O'Brien for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) 2049d62501fSDavid E. O'Brien if (e->namehash == h && strcmp(e->name, p) == 0) 2059d62501fSDavid E. O'Brien return (e); 2069d62501fSDavid E. O'Brien return (NULL); 2079d62501fSDavid E. O'Brien } 2089d62501fSDavid E. O'Brien 2099d62501fSDavid E. O'Brien /* 2109d62501fSDavid E. O'Brien *--------------------------------------------------------- 2119d62501fSDavid E. O'Brien * 2129d62501fSDavid E. O'Brien * Hash_CreateEntry -- 2139d62501fSDavid E. O'Brien * 2149d62501fSDavid E. O'Brien * Searches a hash table for an entry corresponding to 2159d62501fSDavid E. O'Brien * key. If no entry is found, then one is created. 2169d62501fSDavid E. O'Brien * 2179d62501fSDavid E. O'Brien * Results: 2189d62501fSDavid E. O'Brien * The return value is a pointer to the entry. If *newPtr 2199d62501fSDavid E. O'Brien * isn't NULL, then *newPtr is filled in with TRUE if a 2209d62501fSDavid E. O'Brien * new entry was created, and FALSE if an entry already existed 2219d62501fSDavid E. O'Brien * with the given key. 2229d62501fSDavid E. O'Brien * 2239d62501fSDavid E. O'Brien * Side Effects: 2249d62501fSDavid E. O'Brien * Memory may be allocated, and the hash buckets may be modified. 2259d62501fSDavid E. O'Brien *--------------------------------------------------------- 2269d62501fSDavid E. O'Brien */ 2279d62501fSDavid E. O'Brien 2289d62501fSDavid E. O'Brien Hash_Entry * 2299d62501fSDavid E. O'Brien Hash_CreateEntry(t, key, newPtr) 2309d62501fSDavid E. O'Brien register Hash_Table *t; /* Hash table to search. */ 2319d62501fSDavid E. O'Brien char *key; /* A hash key. */ 2329d62501fSDavid E. O'Brien Boolean *newPtr; /* Filled in with TRUE if new entry created, 2339d62501fSDavid E. O'Brien * FALSE otherwise. */ 2349d62501fSDavid E. O'Brien { 2359d62501fSDavid E. O'Brien register Hash_Entry *e; 2369d62501fSDavid E. O'Brien register unsigned h; 2379d62501fSDavid E. O'Brien register char *p; 2389d62501fSDavid E. O'Brien int keylen; 2399d62501fSDavid E. O'Brien struct Hash_Entry **hp; 2409d62501fSDavid E. O'Brien 2419d62501fSDavid E. O'Brien /* 2429d62501fSDavid E. O'Brien * Hash the key. As a side effect, save the length (strlen) of the 2439d62501fSDavid E. O'Brien * key in case we need to create the entry. 2449d62501fSDavid E. O'Brien */ 2459d62501fSDavid E. O'Brien for (h = 0, p = key; *p;) 2469d62501fSDavid E. O'Brien h = (h << 5) - h + *p++; 2479d62501fSDavid E. O'Brien keylen = p - key; 2489d62501fSDavid E. O'Brien p = key; 2499d62501fSDavid E. O'Brien for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) { 2509d62501fSDavid E. O'Brien if (e->namehash == h && strcmp(e->name, p) == 0) { 2519d62501fSDavid E. O'Brien if (newPtr != NULL) 2529d62501fSDavid E. O'Brien *newPtr = FALSE; 2539d62501fSDavid E. O'Brien return (e); 2549d62501fSDavid E. O'Brien } 2559d62501fSDavid E. O'Brien } 2569d62501fSDavid E. O'Brien 2579d62501fSDavid E. O'Brien /* 2589d62501fSDavid E. O'Brien * The desired entry isn't there. Before allocating a new entry, 2599d62501fSDavid E. O'Brien * expand the table if necessary (and this changes the resulting 2609d62501fSDavid E. O'Brien * bucket chain). 2619d62501fSDavid E. O'Brien */ 2629d62501fSDavid E. O'Brien if (t->numEntries >= rebuildLimit * t->size) 2639d62501fSDavid E. O'Brien RebuildTable(t); 2649d62501fSDavid E. O'Brien e = (Hash_Entry *) emalloc(sizeof(*e) + keylen); 2659d62501fSDavid E. O'Brien hp = &t->bucketPtr[h & t->mask]; 2669d62501fSDavid E. O'Brien e->next = *hp; 2679d62501fSDavid E. O'Brien *hp = e; 2689d62501fSDavid E. O'Brien e->clientData = NULL; 2699d62501fSDavid E. O'Brien e->namehash = h; 2709d62501fSDavid E. O'Brien (void) strcpy(e->name, p); 2719d62501fSDavid E. O'Brien t->numEntries++; 2729d62501fSDavid E. O'Brien 2739d62501fSDavid E. O'Brien if (newPtr != NULL) 2749d62501fSDavid E. O'Brien *newPtr = TRUE; 2759d62501fSDavid E. O'Brien return (e); 2769d62501fSDavid E. O'Brien } 2779d62501fSDavid E. O'Brien 2789d62501fSDavid E. O'Brien /* 2799d62501fSDavid E. O'Brien *--------------------------------------------------------- 2809d62501fSDavid E. O'Brien * 2819d62501fSDavid E. O'Brien * Hash_DeleteEntry -- 2829d62501fSDavid E. O'Brien * 2839d62501fSDavid E. O'Brien * Delete the given hash table entry and free memory associated with 2849d62501fSDavid E. O'Brien * it. 2859d62501fSDavid E. O'Brien * 2869d62501fSDavid E. O'Brien * Results: 2879d62501fSDavid E. O'Brien * None. 2889d62501fSDavid E. O'Brien * 2899d62501fSDavid E. O'Brien * Side Effects: 2909d62501fSDavid E. O'Brien * Hash chain that entry lives in is modified and memory is freed. 2919d62501fSDavid E. O'Brien * 2929d62501fSDavid E. O'Brien *--------------------------------------------------------- 2939d62501fSDavid E. O'Brien */ 2949d62501fSDavid E. O'Brien 2959d62501fSDavid E. O'Brien void 2969d62501fSDavid E. O'Brien Hash_DeleteEntry(t, e) 2979d62501fSDavid E. O'Brien Hash_Table *t; 2989d62501fSDavid E. O'Brien Hash_Entry *e; 2999d62501fSDavid E. O'Brien { 3009d62501fSDavid E. O'Brien register Hash_Entry **hp, *p; 3019d62501fSDavid E. O'Brien 3029d62501fSDavid E. O'Brien if (e == NULL) 3039d62501fSDavid E. O'Brien return; 3049d62501fSDavid E. O'Brien for (hp = &t->bucketPtr[e->namehash & t->mask]; 3059d62501fSDavid E. O'Brien (p = *hp) != NULL; hp = &p->next) { 3069d62501fSDavid E. O'Brien if (p == e) { 3079d62501fSDavid E. O'Brien *hp = p->next; 3089d62501fSDavid E. O'Brien free((char *)p); 3099d62501fSDavid E. O'Brien t->numEntries--; 3109d62501fSDavid E. O'Brien return; 3119d62501fSDavid E. O'Brien } 3129d62501fSDavid E. O'Brien } 3139d62501fSDavid E. O'Brien (void)write(2, "bad call to Hash_DeleteEntry\n", 29); 3149d62501fSDavid E. O'Brien abort(); 3159d62501fSDavid E. O'Brien } 3169d62501fSDavid E. O'Brien 3179d62501fSDavid E. O'Brien /* 3189d62501fSDavid E. O'Brien *--------------------------------------------------------- 3199d62501fSDavid E. O'Brien * 3209d62501fSDavid E. O'Brien * Hash_EnumFirst -- 3219d62501fSDavid E. O'Brien * This procedure sets things up for a complete search 3229d62501fSDavid E. O'Brien * of all entries recorded in the hash table. 3239d62501fSDavid E. O'Brien * 3249d62501fSDavid E. O'Brien * Results: 3259d62501fSDavid E. O'Brien * The return value is the address of the first entry in 3269d62501fSDavid E. O'Brien * the hash table, or NULL if the table is empty. 3279d62501fSDavid E. O'Brien * 3289d62501fSDavid E. O'Brien * Side Effects: 3299d62501fSDavid E. O'Brien * The information in searchPtr is initialized so that successive 3309d62501fSDavid E. O'Brien * calls to Hash_Next will return successive HashEntry's 3319d62501fSDavid E. O'Brien * from the table. 3329d62501fSDavid E. O'Brien * 3339d62501fSDavid E. O'Brien *--------------------------------------------------------- 3349d62501fSDavid E. O'Brien */ 3359d62501fSDavid E. O'Brien 3369d62501fSDavid E. O'Brien Hash_Entry * 3379d62501fSDavid E. O'Brien Hash_EnumFirst(t, searchPtr) 3389d62501fSDavid E. O'Brien Hash_Table *t; /* Table to be searched. */ 3399d62501fSDavid E. O'Brien register Hash_Search *searchPtr;/* Area in which to keep state 3409d62501fSDavid E. O'Brien * about search.*/ 3419d62501fSDavid E. O'Brien { 3429d62501fSDavid E. O'Brien searchPtr->tablePtr = t; 3439d62501fSDavid E. O'Brien searchPtr->nextIndex = 0; 3449d62501fSDavid E. O'Brien searchPtr->hashEntryPtr = NULL; 3459d62501fSDavid E. O'Brien return Hash_EnumNext(searchPtr); 3469d62501fSDavid E. O'Brien } 3479d62501fSDavid E. O'Brien 3489d62501fSDavid E. O'Brien /* 3499d62501fSDavid E. O'Brien *--------------------------------------------------------- 3509d62501fSDavid E. O'Brien * 3519d62501fSDavid E. O'Brien * Hash_EnumNext -- 3529d62501fSDavid E. O'Brien * This procedure returns successive entries in the hash table. 3539d62501fSDavid E. O'Brien * 3549d62501fSDavid E. O'Brien * Results: 3559d62501fSDavid E. O'Brien * The return value is a pointer to the next HashEntry 3569d62501fSDavid E. O'Brien * in the table, or NULL when the end of the table is 3579d62501fSDavid E. O'Brien * reached. 3589d62501fSDavid E. O'Brien * 3599d62501fSDavid E. O'Brien * Side Effects: 3609d62501fSDavid E. O'Brien * The information in searchPtr is modified to advance to the 3619d62501fSDavid E. O'Brien * next entry. 3629d62501fSDavid E. O'Brien * 3639d62501fSDavid E. O'Brien *--------------------------------------------------------- 3649d62501fSDavid E. O'Brien */ 3659d62501fSDavid E. O'Brien 3669d62501fSDavid E. O'Brien Hash_Entry * 3679d62501fSDavid E. O'Brien Hash_EnumNext(searchPtr) 3689d62501fSDavid E. O'Brien register Hash_Search *searchPtr; /* Area used to keep state about 3699d62501fSDavid E. O'Brien search. */ 3709d62501fSDavid E. O'Brien { 3719d62501fSDavid E. O'Brien register Hash_Entry *e; 3729d62501fSDavid E. O'Brien Hash_Table *t = searchPtr->tablePtr; 3739d62501fSDavid E. O'Brien 3749d62501fSDavid E. O'Brien /* 3759d62501fSDavid E. O'Brien * The hashEntryPtr field points to the most recently returned 3769d62501fSDavid E. O'Brien * entry, or is nil if we are starting up. If not nil, we have 3779d62501fSDavid E. O'Brien * to start at the next one in the chain. 3789d62501fSDavid E. O'Brien */ 3799d62501fSDavid E. O'Brien e = searchPtr->hashEntryPtr; 3809d62501fSDavid E. O'Brien if (e != NULL) 3819d62501fSDavid E. O'Brien e = e->next; 3829d62501fSDavid E. O'Brien /* 3839d62501fSDavid E. O'Brien * If the chain ran out, or if we are starting up, we need to 3849d62501fSDavid E. O'Brien * find the next nonempty chain. 3859d62501fSDavid E. O'Brien */ 3869d62501fSDavid E. O'Brien while (e == NULL) { 3879d62501fSDavid E. O'Brien if (searchPtr->nextIndex >= t->size) 3889d62501fSDavid E. O'Brien return (NULL); 3899d62501fSDavid E. O'Brien e = t->bucketPtr[searchPtr->nextIndex++]; 3909d62501fSDavid E. O'Brien } 3919d62501fSDavid E. O'Brien searchPtr->hashEntryPtr = e; 3929d62501fSDavid E. O'Brien return (e); 3939d62501fSDavid E. O'Brien } 3949d62501fSDavid E. O'Brien 3959d62501fSDavid E. O'Brien /* 3969d62501fSDavid E. O'Brien *--------------------------------------------------------- 3979d62501fSDavid E. O'Brien * 3989d62501fSDavid E. O'Brien * RebuildTable -- 3999d62501fSDavid E. O'Brien * This local routine makes a new hash table that 4009d62501fSDavid E. O'Brien * is larger than the old one. 4019d62501fSDavid E. O'Brien * 4029d62501fSDavid E. O'Brien * Results: 4039d62501fSDavid E. O'Brien * None. 4049d62501fSDavid E. O'Brien * 4059d62501fSDavid E. O'Brien * Side Effects: 4069d62501fSDavid E. O'Brien * The entire hash table is moved, so any bucket numbers 4079d62501fSDavid E. O'Brien * from the old table are invalid. 4089d62501fSDavid E. O'Brien * 4099d62501fSDavid E. O'Brien *--------------------------------------------------------- 4109d62501fSDavid E. O'Brien */ 4119d62501fSDavid E. O'Brien 4129d62501fSDavid E. O'Brien static void 4139d62501fSDavid E. O'Brien RebuildTable(t) 4149d62501fSDavid E. O'Brien register Hash_Table *t; 4159d62501fSDavid E. O'Brien { 4169d62501fSDavid E. O'Brien register Hash_Entry *e, *next = NULL, **hp, **xp; 4179d62501fSDavid E. O'Brien register int i, mask; 4189d62501fSDavid E. O'Brien register Hash_Entry **oldhp; 4199d62501fSDavid E. O'Brien int oldsize; 4209d62501fSDavid E. O'Brien 4219d62501fSDavid E. O'Brien oldhp = t->bucketPtr; 4229d62501fSDavid E. O'Brien oldsize = i = t->size; 4239d62501fSDavid E. O'Brien i <<= 1; 4249d62501fSDavid E. O'Brien t->size = i; 4259d62501fSDavid E. O'Brien t->mask = mask = i - 1; 4269d62501fSDavid E. O'Brien t->bucketPtr = hp = (struct Hash_Entry **) emalloc(sizeof(*hp) * i); 4279d62501fSDavid E. O'Brien while (--i >= 0) 4289d62501fSDavid E. O'Brien *hp++ = NULL; 4299d62501fSDavid E. O'Brien for (hp = oldhp, i = oldsize; --i >= 0;) { 4309d62501fSDavid E. O'Brien for (e = *hp++; e != NULL; e = next) { 4319d62501fSDavid E. O'Brien next = e->next; 4329d62501fSDavid E. O'Brien xp = &t->bucketPtr[e->namehash & mask]; 4339d62501fSDavid E. O'Brien e->next = *xp; 4349d62501fSDavid E. O'Brien *xp = e; 4359d62501fSDavid E. O'Brien } 4369d62501fSDavid E. O'Brien } 4379d62501fSDavid E. O'Brien free((char *)oldhp); 4389d62501fSDavid E. O'Brien } 439