xref: /freebsd/sbin/rcorder/hash.c (revision 9d62501fd8278c7cde01dcb4d0f2b3c7c757bf86)
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