1/*	$NetBSD: hash.c,v 1.1.1.1 1999/11/19 04:30:56 mrg Exp $	*/
2
3/*-
4 * SPDX-License-Identifier: BSD-4-Clause
5 *
6 * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
7 * Copyright (c) 1988, 1989 by Adam de Boor
8 * Copyright (c) 1989 by Berkeley Softworks
9 * All rights reserved.
10 *
11 * This code is derived from software contributed to Berkeley by
12 * Adam de Boor.
13 *
14 * Redistribution and use in source and binary forms, with or without
15 * modification, are permitted provided that the following conditions
16 * are met:
17 * 1. Redistributions of source code must retain the above copyright
18 *    notice, this list of conditions and the following disclaimer.
19 * 2. Redistributions in binary form must reproduce the above copyright
20 *    notice, this list of conditions and the following disclaimer in the
21 *    documentation and/or other materials provided with the distribution.
22 * 3. All advertising materials mentioning features or use of this software
23 *    must display the following acknowledgement:
24 *	This product includes software developed by the University of
25 *	California, Berkeley and its contributors.
26 * 4. Neither the name of the University nor the names of its contributors
27 *    may be used to endorse or promote products derived from this software
28 *    without specific prior written permission.
29 *
30 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
31 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
32 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
34 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
35 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
36 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
37 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
38 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
39 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
40 * SUCH DAMAGE.
41 */
42
43#include <sys/types.h>
44
45#include <stdlib.h>
46#include <string.h>
47#include <unistd.h>
48
49/* hash.c --
50 *
51 * 	This module contains routines to manipulate a hash table.
52 * 	See hash.h for a definition of the structure of the hash
53 * 	table.  Hash tables grow automatically as the amount of
54 * 	information increases.
55 */
56#include "sprite.h"
57#ifndef ORDER
58#include "make.h"
59#endif /* ORDER */
60#include "hash.h"
61#include "ealloc.h"
62
63/*
64 * Forward references to local procedures that are used before they're
65 * defined:
66 */
67
68static void RebuildTable(Hash_Table *);
69
70/*
71 * The following defines the ratio of # entries to # buckets
72 * at which we rebuild the table to make it larger.
73 */
74
75#define rebuildLimit 8
76
77/*
78 *---------------------------------------------------------
79 *
80 * Hash_InitTable --
81 *
82 *	This routine just sets up the hash table.
83 *
84 * Results:
85 *	None.
86 *
87 * Side Effects:
88 *	Memory is allocated for the initial bucket area.
89 *
90 *---------------------------------------------------------
91 */
92
93void
94Hash_InitTable(
95	register Hash_Table *t,	/* Structure to use to hold table. */
96	int numBuckets)		/* How many buckets to create for starters.
97				 * This number is rounded up to a power of
98				 * two.   If <= 0, a reasonable default is
99				 * chosen. The table will grow in size later
100				 * as needed. */
101{
102	register int i;
103	register struct Hash_Entry **hp;
104
105	/*
106	 * Round up the size to a power of two.
107	 */
108	if (numBuckets <= 0)
109		i = 16;
110	else {
111		for (i = 2; i < numBuckets; i <<= 1)
112			 continue;
113	}
114	t->numEntries = 0;
115	t->size = i;
116	t->mask = i - 1;
117	t->bucketPtr = hp = (struct Hash_Entry **)emalloc(sizeof(*hp) * i);
118	while (--i >= 0)
119		*hp++ = NULL;
120}
121
122/*
123 *---------------------------------------------------------
124 *
125 * Hash_DeleteTable --
126 *
127 *	This routine removes everything from a hash table
128 *	and frees up the memory space it occupied (except for
129 *	the space in the Hash_Table structure).
130 *
131 * Results:
132 *	None.
133 *
134 * Side Effects:
135 *	Lots of memory is freed up.
136 *
137 *---------------------------------------------------------
138 */
139
140void
141Hash_DeleteTable(Hash_Table *t)
142{
143	register struct Hash_Entry **hp, *h, *nexth = NULL;
144	register int i;
145
146	for (hp = t->bucketPtr, i = t->size; --i >= 0;) {
147		for (h = *hp++; h != NULL; h = nexth) {
148			nexth = h->next;
149			free((char *)h);
150		}
151	}
152	free((char *)t->bucketPtr);
153
154	/*
155	 * Set up the hash table to cause memory faults on any future access
156	 * attempts until re-initialization.
157	 */
158	t->bucketPtr = NULL;
159}
160
161/*
162 *---------------------------------------------------------
163 *
164 * Hash_FindEntry --
165 *
166 * 	Searches a hash table for an entry corresponding to key.
167 *
168 * Results:
169 *	The return value is a pointer to the entry for key,
170 *	if key was present in the table.  If key was not
171 *	present, NULL is returned.
172 *
173 * Side Effects:
174 *	None.
175 *
176 *---------------------------------------------------------
177 */
178
179Hash_Entry *
180Hash_FindEntry(
181	Hash_Table *t,		/* Hash table to search. */
182	char *key)		/* A hash key. */
183{
184	register Hash_Entry *e;
185	register unsigned h;
186	register char *p;
187
188	for (h = 0, p = key; *p;)
189		h = (h << 5) - h + *p++;
190	p = key;
191	for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next)
192		if (e->namehash == h && strcmp(e->name, p) == 0)
193			return (e);
194	return (NULL);
195}
196
197/*
198 *---------------------------------------------------------
199 *
200 * Hash_CreateEntry --
201 *
202 *	Searches a hash table for an entry corresponding to
203 *	key.  If no entry is found, then one is created.
204 *
205 * Results:
206 *	The return value is a pointer to the entry.  If *newPtr
207 *	isn't NULL, then *newPtr is filled in with TRUE if a
208 *	new entry was created, and FALSE if an entry already existed
209 *	with the given key.
210 *
211 * Side Effects:
212 *	Memory may be allocated, and the hash buckets may be modified.
213 *---------------------------------------------------------
214 */
215
216Hash_Entry *
217Hash_CreateEntry(
218	register Hash_Table *t,	/* Hash table to search. */
219	char *key,		/* A hash key. */
220	Boolean *newPtr)	/* Filled in with TRUE if new entry created,
221				 * FALSE otherwise. */
222{
223	register Hash_Entry *e;
224	register unsigned h;
225	register char *p;
226	int keylen;
227	struct Hash_Entry **hp;
228
229	/*
230	 * Hash the key.  As a side effect, save the length (strlen) of the
231	 * key in case we need to create the entry.
232	 */
233	for (h = 0, p = key; *p;)
234		h = (h << 5) - h + *p++;
235	keylen = p - key;
236	p = key;
237	for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) {
238		if (e->namehash == h && strcmp(e->name, p) == 0) {
239			if (newPtr != NULL)
240				*newPtr = FALSE;
241			return (e);
242		}
243	}
244
245	/*
246	 * The desired entry isn't there.  Before allocating a new entry,
247	 * expand the table if necessary (and this changes the resulting
248	 * bucket chain).
249	 */
250	if (t->numEntries >= rebuildLimit * t->size)
251		RebuildTable(t);
252	e = (Hash_Entry *) emalloc(sizeof(*e) + keylen);
253	hp = &t->bucketPtr[h & t->mask];
254	e->next = *hp;
255	*hp = e;
256	e->clientData = NULL;
257	e->namehash = h;
258	(void) strcpy(e->name, p);
259	t->numEntries++;
260
261	if (newPtr != NULL)
262		*newPtr = TRUE;
263	return (e);
264}
265
266/*
267 *---------------------------------------------------------
268 *
269 * Hash_DeleteEntry --
270 *
271 * 	Delete the given hash table entry and free memory associated with
272 *	it.
273 *
274 * Results:
275 *	None.
276 *
277 * Side Effects:
278 *	Hash chain that entry lives in is modified and memory is freed.
279 *
280 *---------------------------------------------------------
281 */
282
283void
284Hash_DeleteEntry(Hash_Table *t, Hash_Entry *e)
285{
286	register Hash_Entry **hp, *p;
287
288	if (e == NULL)
289		return;
290	for (hp = &t->bucketPtr[e->namehash & t->mask];
291	     (p = *hp) != NULL; hp = &p->next) {
292		if (p == e) {
293			*hp = p->next;
294			free((char *)p);
295			t->numEntries--;
296			return;
297		}
298	}
299	(void)write(2, "bad call to Hash_DeleteEntry\n", 29);
300	abort();
301}
302
303/*
304 *---------------------------------------------------------
305 *
306 * Hash_EnumFirst --
307 *	This procedure sets things up for a complete search
308 *	of all entries recorded in the hash table.
309 *
310 * Results:
311 *	The return value is the address of the first entry in
312 *	the hash table, or NULL if the table is empty.
313 *
314 * Side Effects:
315 *	The information in searchPtr is initialized so that successive
316 *	calls to Hash_Next will return successive HashEntry's
317 *	from the table.
318 *
319 *---------------------------------------------------------
320 */
321
322Hash_Entry *
323Hash_EnumFirst(
324	Hash_Table *t,			/* Table to be searched. */
325	register Hash_Search *searchPtr)/* Area in which to keep state
326					 * about search.*/
327{
328	searchPtr->tablePtr = t;
329	searchPtr->nextIndex = 0;
330	searchPtr->hashEntryPtr = NULL;
331	return Hash_EnumNext(searchPtr);
332}
333
334/*
335 *---------------------------------------------------------
336 *
337 * Hash_EnumNext --
338 *    This procedure returns successive entries in the hash table.
339 *
340 * Results:
341 *    The return value is a pointer to the next HashEntry
342 *    in the table, or NULL when the end of the table is
343 *    reached.
344 *
345 * Side Effects:
346 *    The information in searchPtr is modified to advance to the
347 *    next entry.
348 *
349 *---------------------------------------------------------
350 */
351
352Hash_Entry *
353Hash_EnumNext(
354	register Hash_Search *searchPtr) /* Area used to keep state about
355					    search. */
356{
357	register Hash_Entry *e;
358	Hash_Table *t = searchPtr->tablePtr;
359
360	/*
361	 * The hashEntryPtr field points to the most recently returned
362	 * entry, or is nil if we are starting up.  If not nil, we have
363	 * to start at the next one in the chain.
364	 */
365	e = searchPtr->hashEntryPtr;
366	if (e != NULL)
367		e = e->next;
368	/*
369	 * If the chain ran out, or if we are starting up, we need to
370	 * find the next nonempty chain.
371	 */
372	while (e == NULL) {
373		if (searchPtr->nextIndex >= t->size)
374			return (NULL);
375		e = t->bucketPtr[searchPtr->nextIndex++];
376	}
377	searchPtr->hashEntryPtr = e;
378	return (e);
379}
380
381/*
382 *---------------------------------------------------------
383 *
384 * RebuildTable --
385 *	This local routine makes a new hash table that
386 *	is larger than the old one.
387 *
388 * Results:
389 * 	None.
390 *
391 * Side Effects:
392 *	The entire hash table is moved, so any bucket numbers
393 *	from the old table are invalid.
394 *
395 *---------------------------------------------------------
396 */
397
398static void
399RebuildTable(register Hash_Table *t)
400{
401	register Hash_Entry *e, *next = NULL, **hp, **xp;
402	register int i, mask;
403        register Hash_Entry **oldhp;
404	int oldsize;
405
406	oldhp = t->bucketPtr;
407	oldsize = i = t->size;
408	i <<= 1;
409	t->size = i;
410	t->mask = mask = i - 1;
411	t->bucketPtr = hp = (struct Hash_Entry **) emalloc(sizeof(*hp) * i);
412	while (--i >= 0)
413		*hp++ = NULL;
414	for (hp = oldhp, i = oldsize; --i >= 0;) {
415		for (e = *hp++; e != NULL; e = next) {
416			next = e->next;
417			xp = &t->bucketPtr[e->namehash & mask];
418			e->next = *xp;
419			*xp = e;
420		}
421	}
422	free((char *)oldhp);
423}
424