 @@ -1,14 +1,14 @@
-/*	$NetBSD: hash.c,v 1.27 2020/08/26 23:00:47 rillig Exp $	*/
+/*	$NetBSD: hash.c,v 1.28 2020/08/28 20:16:19 rillig Exp $	*/
 /*
  * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
  * All rights reserved.
+ *
  * This code is derived from software contributed to Berkeley by
  * Adam de Boor.
+ *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
 @@ -60,34 +60,34 @@
  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  */
 #ifndef MAKE_NATIVE
-static char rcsid[] = "$NetBSD: hash.c,v 1.27 2020/08/26 23:00:47 rillig Exp $";
+static char rcsid[] = "$NetBSD: hash.c,v 1.28 2020/08/28 20:16:19 rillig Exp $";
 #else
 #include <sys/cdefs.h>
 #ifndef lint
 #if 0
 static char sccsid[] = "@(#)hash.c	8.1 (Berkeley) 6/6/93";
 #else
-__RCSID("$NetBSD: hash.c,v 1.27 2020/08/26 23:00:47 rillig Exp $");
+__RCSID("$NetBSD: hash.c,v 1.28 2020/08/28 20:16:19 rillig Exp $");
 #endif
 #endif /* not lint */
 #endif
 /* hash.c --
+ *
  * 	This module contains routines to manipulate a hash table.
  * 	See hash.h for a definition of the structure of the hash
  * 	table.  Hash tables grow automatically as the amount of
  * 	information increases.
  */
 #include "make.h"
 @@ -106,134 +106,92 @@ static void RebuildTable(Hash_Table *);
 #define rebuildLimit 3
 /* The hash function(s) */
 #ifndef HASH
 /* The default: this one matches Gosling's emacs */
 #define HASH(h, key, p) do { \
 	for (h = 0, p = key; *p;) \
 		h = (h << 5) - h + *p++; \
 	} while (0)
 #endif
-/*
+/* Sets up the hash table.
  *---------------------------------------------------------
  * Hash_InitTable --
  *	This routine just sets up the hash table.
+ *
  * Input:
- *	t		Structure to to hold table.
+ *	t		Structure to to hold the table.
  *	numBuckets	How many buckets to create for starters. This
  *			number is rounded up to a power of two.   If
  *			<= 0, a reasonable default is chosen. The
  *			table will grow in size later as needed.
  * Results:
  *	None.
  * Side Effects:
  *	Memory is allocated for the initial bucket area.
  *---------------------------------------------------------
  */
 void
 Hash_InitTable(Hash_Table *t, int numBuckets)
+{
 	int i;
 	struct Hash_Entry **hp;
 	/*
 	 * Round up the size to a power of two.
 	 */
 	if (numBuckets <= 0)
 		i = 16;
 	else {
 		for (i = 2; i < numBuckets; i <<= 1)
 			 continue;
+	}
 	t->numEntries = 0;
 	t->maxchain = 0;
 	t->size = i;
 	t->mask = i - 1;
 	t->bucketPtr = hp = bmake_malloc(sizeof(*hp) * i);
 	while (--i >= 0)
 		*hp++ = NULL;
+}
-/*
+/* Removes everything from the hash table and frees up the memory space it
- *---------------------------------------------------------
+ * occupied (except for the space in the Hash_Table structure). */
  * Hash_DeleteTable --
  *	This routine removes everything from a hash table
  *	and frees up the memory space it occupied (except for
  *	the space in the Hash_Table structure).
  * Results:
  *	None.
  * Side Effects:
  *	Lots of memory is freed up.
  *---------------------------------------------------------
  */
 void
 Hash_DeleteTable(Hash_Table *t)
+{
 	struct Hash_Entry **hp, *h, *nexth = NULL;
 	int i;
 	for (hp = t->bucketPtr, i = t->size; --i >= 0;) {
 		for (h = *hp++; h != NULL; h = nexth) {
 			nexth = h->next;
 			free(h);
+		}
+	}
 	free(t->bucketPtr);
 	/*
 	 * Set up the hash table to cause memory faults on any future access
 	 * attempts until re-initialization.
 	 */
 	t->bucketPtr = NULL;
+}
-/*
+/* Searches the hash table for an entry corresponding to the key.
  *---------------------------------------------------------
  * Hash_FindEntry --
  * 	Searches a hash table for an entry corresponding to key.
+ *
  * Input:
  *	t		Hash table to search.
  *	key		A hash key.
+ *
  * Results:
- *	The return value is a pointer to the entry for key,
+ *	Returns a pointer to the entry for key, or NULL if the table contains
- *	if key was present in the table.  If key was not
+ *	no entry for the key.
  *	present, NULL is returned.
  * Side Effects:
  *	None.
  *---------------------------------------------------------
  */
 Hash_Entry *
 Hash_FindEntry(Hash_Table *t, const char *key)
+{
 	Hash_Entry *e;
 	unsigned h;
 	const char *p;
 	int chainlen;
 	if (t == NULL || t->bucketPtr == NULL) {
 	    return NULL;
+	}
 	HASH(h, key, p);
 	p = key;
 @@ -243,51 +201,35 @@ Hash_FindEntry(Hash_Table *t, const char
 		fprintf(debug_file, "%s: %p h=%x key=%s\n", __func__,
 		    t, h, key);
 #endif
 	for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) {
 		chainlen++;
 		if (e->namehash == h && strcmp(e->name, p) == 0)
 			break;
+	}
 	if (chainlen > t->maxchain)
 		t->maxchain = chainlen;
 	return e;
+}
-/*
+/* Searches the hash table for an entry corresponding to the key.
- *---------------------------------------------------------
+ * If no entry is found, then one is created.
  * Hash_CreateEntry --
  *	Searches a hash table for an entry corresponding to
  *	key.  If no entry is found, then one is created.
+ *
  * Input:
  *	t		Hash table to search.
  *	key		A hash key.
- *	newPtr		Filled in with TRUE if new entry created,
+ *	newPtr		Filled with TRUE if new entry created,
  *			FALSE otherwise.
  * Results:
  *	The return value is a pointer to the entry.  If *newPtr
  *	isn't NULL, then *newPtr is filled in with TRUE if a
  *	new entry was created, and FALSE if an entry already existed
  *	with the given key.
  * Side Effects:
  *	Memory may be allocated, and the hash buckets may be modified.
  *---------------------------------------------------------
  */
 Hash_Entry *
 Hash_CreateEntry(Hash_Table *t, const char *key, Boolean *newPtr)
+{
 	Hash_Entry *e;
 	unsigned h;
 	const char *p;
 	int keylen;
 	int chainlen;
 	struct Hash_Entry **hp;
 	/*
 	 * Hash the key.  As a side effect, save the length (strlen) of the
 	 * key in case we need to create the entry.
 @@ -325,116 +267,72 @@ Hash_CreateEntry(Hash_Table *t, const ch
 	hp = &t->bucketPtr[h & t->mask];
 	e->next = *hp;
 	*hp = e;
 	Hash_SetValue(e, NULL);
 	e->namehash = h;
 	(void)strcpy(e->name, p);
 	t->numEntries++;
 	if (newPtr != NULL)
 		*newPtr = TRUE;
 	return e;
+}
-/*
+/* Delete the given hash table entry and free memory associated with it. */
  *---------------------------------------------------------
  * Hash_DeleteEntry --
  * 	Delete the given hash table entry and free memory associated with
  *	it.
  * Results:
  *	None.
  * Side Effects:
  *	Hash chain that entry lives in is modified and memory is freed.
  *---------------------------------------------------------
  */
 void
 Hash_DeleteEntry(Hash_Table *t, Hash_Entry *e)
+{
 	Hash_Entry **hp, *p;
 	if (e == NULL)
 		return;
 	for (hp = &t->bucketPtr[e->namehash & t->mask];
 	     (p = *hp) != NULL; hp = &p->next) {
 		if (p == e) {
 			*hp = p->next;
 			free(p);
 			t->numEntries--;
 			return;
+		}
+	}
 	(void)write(2, "bad call to Hash_DeleteEntry\n", 29);
 	abort();
+}
-/*
+/* Sets things up for enumerating all entries in the hash table.
  *---------------------------------------------------------
  * Hash_EnumFirst --
  *	This procedure sets things up for a complete search
  *	of all entries recorded in the hash table.
+ *
  * Input:
  *	t		Table to be searched.
  *	searchPtr	Area in which to keep state about search.
+ *
  * Results:
  *	The return value is the address of the first entry in
  *	the hash table, or NULL if the table is empty.
  * Side Effects:
  *	The information in searchPtr is initialized so that successive
  *	calls to Hash_Next will return successive HashEntry's
  *	from the table.
  *---------------------------------------------------------
  */
 Hash_Entry *
 Hash_EnumFirst(Hash_Table *t, Hash_Search *searchPtr)
+{
 	searchPtr->tablePtr = t;
 	searchPtr->nextIndex = 0;
 	searchPtr->hashEntryPtr = NULL;
 	return Hash_EnumNext(searchPtr);
+}
-/*
+/* Returns the next entry in the hash table, or NULL if the end of the table
- *---------------------------------------------------------
+ * is reached.
  * Hash_EnumNext --
  *    This procedure returns successive entries in the hash table.
+ *
  * Input:
  *	searchPtr	Area used to keep state about search.
  * Results:
  *    The return value is a pointer to the next HashEntry
  *    in the table, or NULL when the end of the table is
  *    reached.
  * Side Effects:
  *    The information in searchPtr is modified to advance to the
  *    next entry.
  *---------------------------------------------------------
  */
 Hash_Entry *
 Hash_EnumNext(Hash_Search *searchPtr)
+{
 	Hash_Entry *e;
 	Hash_Table *t = searchPtr->tablePtr;
 	/*
 	 * The hashEntryPtr field points to the most recently returned
 	 * entry, or is nil if we are starting up.  If not nil, we have
 	 * to start at the next one in the chain.
 	 */
 	e = searchPtr->hashEntryPtr;
 	if (e != NULL)
 @@ -442,43 +340,28 @@ Hash_EnumNext(Hash_Search *searchPtr)
 	/*
 	 * If the chain ran out, or if we are starting up, we need to
 	 * find the next nonempty chain.
 	 */
 	while (e == NULL) {
 		if (searchPtr->nextIndex >= t->size)
 			return NULL;
 		e = t->bucketPtr[searchPtr->nextIndex++];
+	}
 	searchPtr->hashEntryPtr = e;
 	return e;
+}
-/*
+/* Makes a new hash table that is larger than the old one. The entire hash
- *---------------------------------------------------------
+ * table is moved, so any bucket numbers from the old table become invalid. */
  * RebuildTable --
  *	This local routine makes a new hash table that
  *	is larger than the old one.
  * Results:
  * 	None.
  * Side Effects:
  *	The entire hash table is moved, so any bucket numbers
  *	from the old table are invalid.
  *---------------------------------------------------------
  */
 static void
 RebuildTable(Hash_Table *t)
+{
 	Hash_Entry *e, *next = NULL, **hp, **xp;
 	int i, mask;
 	Hash_Entry **oldhp;
 	int oldsize;
 	oldhp = t->bucketPtr;
 	oldsize = i = t->size;
 	i <<= 1;
 	t->size = i;
 	t->mask = mask = i - 1;
 @@ -490,27 +373,28 @@ RebuildTable(Hash_Table *t)
 			next = e->next;
 			xp = &t->bucketPtr[e->namehash & mask];
 			e->next = *xp;
 			*xp = e;
+		}
+	}
 	free(oldhp);
 	if (DEBUG(HASH))
 		fprintf(debug_file, "%s: %p size=%d entries=%d maxchain=%d\n",
 		    __func__, t, t->size, t->numEntries, t->maxchain);
 	t->maxchain = 0;
+}
-void Hash_ForEach(Hash_Table *t, void (*action)(void *, void *), void *data)
+void
 Hash_ForEach(Hash_Table *t, void (*action)(void *, void *), void *data)
+{
 	Hash_Search search;
 	Hash_Entry *e;
 	for (e = Hash_EnumFirst(t, &search);
 	     e != NULL;
 	     e = Hash_EnumNext(&search))
 		action(Hash_GetValue(e), data);
+}
 void
 Hash_DebugStats(Hash_Table *t, const char *name)
+{