3 /*-
4  * SPDX-License-Identifier: BSD-4-Clause
49 /* hash.c --
78  *---------------------------------------------------------
80  * Hash_InitTable --
82  *	This routine just sets up the hash table.
90  *---------------------------------------------------------
97 				 * This number is rounded up to a power of  in Hash_InitTable()
106 	 * Round up the size to a power of two.  in Hash_InitTable()
114 	t->numEntries = 0;  in Hash_InitTable()
115 	t->size = i;  in Hash_InitTable()
116 	t->mask = i - 1;  in Hash_InitTable()
117 	t->bucketPtr = hp = (struct Hash_Entry **)emalloc(sizeof(*hp) * i);  in Hash_InitTable()
118 	while (--i >= 0)  in Hash_InitTable()
123  *---------------------------------------------------------
125  * Hash_DeleteTable --
128  *	and frees up the memory space it occupied (except for
135  *	Lots of memory is freed up.
137  *---------------------------------------------------------
146 	for (hp = t->bucketPtr, i = t->size; --i >= 0;) {  in Hash_DeleteTable()
148 			nexth = h->next;  in Hash_DeleteTable()
152 	free((char *)t->bucketPtr);  in Hash_DeleteTable()
155 	 * Set up the hash table to cause memory faults on any future access  in Hash_DeleteTable()
156 	 * attempts until re-initialization.  in Hash_DeleteTable()
158 	t->bucketPtr = NULL;  in Hash_DeleteTable()
162  *---------------------------------------------------------
164  * Hash_FindEntry --
166  * 	Searches a hash table for an entry corresponding to key.
169  *	The return value is a pointer to the entry for key,
170  *	if key was present in the table.  If key was not
176  *---------------------------------------------------------
182 	char *key)		/* A hash key. */  in Hash_FindEntry()  argument
188 	for (h = 0, p = key; *p;)  in Hash_FindEntry()
189 		h = (h << 5) - h + *p++;  in Hash_FindEntry()
190 	p = key;  in Hash_FindEntry()
191 	for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next)  in Hash_FindEntry()
192 		if (e->namehash == h && strcmp(e->name, p) == 0)  in Hash_FindEntry()
198  *---------------------------------------------------------
200  * Hash_CreateEntry --
203  *	key.  If no entry is found, then one is created.
209  *	with the given key.
213  *---------------------------------------------------------
219 	char *key,		/* A hash key. */  in Hash_CreateEntry()  argument
230 	 * Hash the key.  As a side effect, save the length (strlen) of the  in Hash_CreateEntry()
231 	 * key in case we need to create the entry.  in Hash_CreateEntry()
233 	for (h = 0, p = key; *p;)  in Hash_CreateEntry()
234 		h = (h << 5) - h + *p++;  in Hash_CreateEntry()
235 	keylen = p - key;  in Hash_CreateEntry()
236 	p = key;  in Hash_CreateEntry()
237 	for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) {  in Hash_CreateEntry()
238 		if (e->namehash == h && strcmp(e->name, p) == 0) {  in Hash_CreateEntry()
250 	if (t->numEntries >= rebuildLimit * t->size)  in Hash_CreateEntry()
253 	hp = &t->bucketPtr[h & t->mask];  in Hash_CreateEntry()
254 	e->next = *hp;  in Hash_CreateEntry()
256 	e->clientData = NULL;  in Hash_CreateEntry()
257 	e->namehash = h;  in Hash_CreateEntry()
258 	(void) strcpy(e->name, p);  in Hash_CreateEntry()
259 	t->numEntries++;  in Hash_CreateEntry()
267  *---------------------------------------------------------
269  * Hash_DeleteEntry --
280  *---------------------------------------------------------
290 	for (hp = &t->bucketPtr[e->namehash & t->mask];  in Hash_DeleteEntry()
291 	     (p = *hp) != NULL; hp = &p->next) {  in Hash_DeleteEntry()
293 			*hp = p->next;  in Hash_DeleteEntry()
295 			t->numEntries--;  in Hash_DeleteEntry()
304  *---------------------------------------------------------
306  * Hash_EnumFirst --
307  *	This procedure sets things up for a complete search
319  *---------------------------------------------------------
328 	searchPtr->tablePtr = t;  in Hash_EnumFirst()
329 	searchPtr->nextIndex = 0;  in Hash_EnumFirst()
330 	searchPtr->hashEntryPtr = NULL;  in Hash_EnumFirst()
335  *---------------------------------------------------------
337  * Hash_EnumNext --
349  *---------------------------------------------------------
358 	Hash_Table *t = searchPtr->tablePtr;  in Hash_EnumNext()
362 	 * entry, or is nil if we are starting up.  If not nil, we have  in Hash_EnumNext()
365 	e = searchPtr->hashEntryPtr;  in Hash_EnumNext()
367 		e = e->next;  in Hash_EnumNext()
369 	 * If the chain ran out, or if we are starting up, we need to  in Hash_EnumNext()
373 		if (searchPtr->nextIndex >= t->size)  in Hash_EnumNext()
375 		e = t->bucketPtr[searchPtr->nextIndex++];  in Hash_EnumNext()
377 	searchPtr->hashEntryPtr = e;  in Hash_EnumNext()
382  *---------------------------------------------------------
384  * RebuildTable --
395  *---------------------------------------------------------
406 	oldhp = t->bucketPtr;  in RebuildTable()
407 	oldsize = i = t->size;  in RebuildTable()
409 	t->size = i;  in RebuildTable()
410 	t->mask = mask = i - 1;  in RebuildTable()
411 	t->bucketPtr = hp = (struct Hash_Entry **) emalloc(sizeof(*hp) * i);  in RebuildTable()
412 	while (--i >= 0)  in RebuildTable()
414 	for (hp = oldhp, i = oldsize; --i >= 0;) {  in RebuildTable()
416 			next = e->next;  in RebuildTable()
417 			xp = &t->bucketPtr[e->namehash & mask];  in RebuildTable()
418 			e->next = *xp;  in RebuildTable()