This kills the last old hashing table, in arch.c

Slight optimizations: instead of storing archive members, just keep
the modification time, as we don't care for the rest of the archive
information. Lazily compute mtime, stash ascii date instead, and convert
to mtime when needed (storing an out_of_date value to mark the unconverted
values).

Archive handling is atrocious and need some clean-up.

Thanks to miod@ who took the time to review those patches.

4 files changed, 127 insertions, 642 deletions

diff --git a/usr.bin/make/Makefile b/usr.bin/make/Makefile
index 4fc77dcace0..47c2912f9b9 100644
--- a/usr.bin/make/Makefile
+++ b/usr.bin/make/Makefile
@@ -1,4 +1,4 @@
-#	$OpenBSD: Makefile,v 1.22 2000/09/14 13:32:05 espie Exp $
+#	$OpenBSD: Makefile,v 1.23 2000/09/14 13:56:14 espie Exp $
 
 PROG=	make
 CFLAGS+= -I${.OBJDIR} -I${.CURDIR} -Wall -Wno-char-subscripts -Wstrict-prototypes
@@ -7,7 +7,7 @@ CFLAGS+= -I${.OBJDIR} -I${.CURDIR} -Wall -Wno-char-subscripts -Wstrict-prototype
 CFLAGS+=-O0
 .endif
 
-SRCS=	arch.c buf.c compat.c cond.c dir.c error.c for.c hash.c job.c lowparse.c \
+SRCS=	arch.c buf.c compat.c cond.c dir.c error.c for.c job.c lowparse.c \
 	main.c make.c parse.c str.c suff.c targ.c var.c varmodifiers.c #util.c 
 SRCS+=	lstAppend.c lstAtEnd.c lstAtFront.c lstClose.c lstConcat.c \
 	lstConcatDestroy.c lstDeQueue.c lstDestroy.c lstDupl.c lstEnQueue.c \
diff --git a/usr.bin/make/arch.c b/usr.bin/make/arch.c
index 30df6314ee0..7f1a2aefdcc 100644
--- a/usr.bin/make/arch.c
+++ b/usr.bin/make/arch.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: arch.c,v 1.34 2000/09/14 13:52:41 espie Exp $	*/
+/*	$OpenBSD: arch.c,v 1.35 2000/09/14 13:56:14 espie Exp $	*/
 /*	$NetBSD: arch.c,v 1.17 1996/11/06 17:58:59 christos Exp $	*/
 
 /*
@@ -100,7 +100,6 @@
 #include    <fcntl.h>
 #include    "make.h"
 #include    "ohash.h"
-#include    "hash.h"
 #include    "dir.h"
 #include    "config.h"
 
@@ -109,7 +108,7 @@
 static char sccsid[] = "@(#)arch.c	8.2 (Berkeley) 1/2/94";
 #else
 UNUSED
-static char rcsid[] = "$OpenBSD: arch.c,v 1.34 2000/09/14 13:52:41 espie Exp $";
+static char rcsid[] = "$OpenBSD: arch.c,v 1.35 2000/09/14 13:56:14 espie Exp $";
 #endif
 #endif /* not lint */
 
@@ -124,19 +123,41 @@ static char rcsid[] = "$OpenBSD: arch.c,v 1.34 2000/09/14 13:52:41 espie Exp $";
 
 static LIST	  archives;   /* Lst of archives we've already examined */
 
-typedef struct Arch {
+typedef struct Arch_ {
     char	  *name;      /* Name of archive */
-    Hash_Table	  members;    /* All the members of the archive described
-			       * by <name, struct ar_hdr *> key/value pairs */
+    struct hash	  members;    /* All the members of this archive, as
+     			       * struct arch_member entries.  */
     char	  *fnametab;  /* Extended name table strings */
     size_t	  fnamesize;  /* Size of the string table */
 } Arch;
 
+/* Used to get to ar's field sizes.  */
+static struct ar_hdr *dummy;
+#define AR_NAME_SIZE	    	(sizeof(dummy->ar_name))
+#define AR_DATE_SIZE		(sizeof(dummy->ar_date))
+
+/* Each archive member is tied to an arch_member structure, 
+ * suitable for hashing.  */
+struct arch_member {
+    TIMESTAMP	  mtime;	/* Member modification date.  */
+    char   	  date[AR_DATE_SIZE+1];
+    				/* Same, before conversion to numeric value.  */
+    char	  name[1];	/* Member name.  */
+};
+
+static struct hash_info members_info = {
+    offsetof(struct arch_member, name), NULL, 
+    hash_alloc, hash_free, element_alloc 
+};
+
+static struct arch_member *new_arch_member __P((struct ar_hdr *, const char *));
+static TIMESTAMP mtime_of_member __P((struct arch_member *));
+
 static int ArchFindArchive __P((void *, void *));
 #ifdef CLEANUP
 static void ArchFree __P((void *));
 #endif
-static struct ar_hdr *ArchStatMember __P((char *, char *, Boolean));
+static TIMESTAMP ArchMTimeMember __P((char *, char *, Boolean));
 static FILE *ArchFindMember __P((char *, char *, struct ar_hdr *, char *));
 #if defined(__svr4__) || defined(__SVR4) || \
     (defined(__OpenBSD__) && defined(__mips__)) || \
@@ -145,6 +166,32 @@ static FILE *ArchFindMember __P((char *, char *, struct ar_hdr *, char *));
 static int ArchSVR4Entry __P((Arch *, char *, size_t, FILE *));
 #endif
 
+static struct arch_member *
+new_arch_member(hdr, name)
+    struct ar_hdr *hdr;
+    const char *name;
+{
+    const char *end = NULL;
+    struct arch_member *n;
+
+    n = hash_create_entry(&members_info, name, &end);
+    /* XXX ar entries are NOT null terminated.  */
+    memcpy(n->date, &(hdr->ar_date), AR_DATE_SIZE);
+    n->date[AR_DATE_SIZE] = '\0';
+    /* Don't compute mtime before it is needed. */
+    set_out_of_date(n->mtime);
+    return n;
+}
+
+static TIMESTAMP
+mtime_of_member(m)
+    struct arch_member *m;
+{
+    if (is_out_of_date(m->mtime))
+    	grab_date((time_t) strtol(m->date, NULL, 10), m->mtime);
+    return m->mtime;
+}
+
 #ifdef CLEANUP
 /*-
  *-----------------------------------------------------------------------
@@ -164,18 +211,17 @@ ArchFree(ap)
     void *ap;
 {
     Arch *a = (Arch *) ap;
-    Hash_Search	  search;
-    Hash_Entry	  *entry;
+    struct arch_member *mem;
+    unsigned i;
 
     /* Free memory from hash entries */
-    for (entry = Hash_EnumFirst(&a->members, &search);
-	 entry != NULL;
-	 entry = Hash_EnumNext(&search))
-	free(Hash_GetValue(entry));
+    for (mem = hash_first(&a->members, &i); mem != NULL;
+    	mem = hash_next(&a->members, &i))
+	free(mem);
 
     free(a->name);
     efree(a->fnametab);
-    Hash_DeleteTable(&a->members);
+    hash_delete(&a->members);
     free(a);
 }
 #endif
@@ -435,18 +481,14 @@ Arch_ParseArchive(linePtr, nodeLst, ctxt)
  *-----------------------------------------------------------------------
  * ArchFindArchive --
  *	See if the given archive is the one we are looking for. Called
- *	From ArchStatMember and ArchFindMember via Lst_Find.
+ *	From ArchMTimeMember and ArchFindMember via Lst_Find.
  *
  * Results:
  *	0 if it is, non-zero if it isn't.
- *
- * Side Effects:
- *	None.
- *
  *-----------------------------------------------------------------------
  */
 static int
-ArchFindArchive (ar, archName)
+ArchFindArchive(ar, archName)
     void *ar;	      	  /* Current list element */
     void *archName;  	  /* Name we want */
 {
@@ -455,7 +497,7 @@ ArchFindArchive (ar, archName)
 
 /*-
  *-----------------------------------------------------------------------
- * ArchStatMember --
+ * ArchMTimeMember --
  *	Locate a member of an archive, given the path of the archive and
  *	the path of the desired member.
  *
@@ -470,8 +512,8 @@ ArchFindArchive (ar, archName)
  *
  *-----------------------------------------------------------------------
  */
-static struct ar_hdr *
-ArchStatMember (archive, member, hash)
+static TIMESTAMP
+ArchMTimeMember(archive, member, hash)
     char	  *archive;   /* Path to the archive */
     char	  *member;    /* Name of member. If it is a path, only the
 			       * last component is used. */
@@ -485,10 +527,14 @@ ArchStatMember (archive, member, hash)
     char	  magic[SARMAG];
     LstNode	  ln;	      /* Lst member containing archive descriptor */
     Arch	  *ar;	      /* Archive descriptor */
-    Hash_Entry	  *he;	      /* Entry containing member's description */
+    struct arch_member *he;   /* Entry containing member's description */
     struct ar_hdr arh;        /* archive-member header for reading archive */
     char	  memName[MAXPATHLEN+1];
     	    	    	    /* Current member name while hashing. */
+    const char 	  *end = NULL;
+    TIMESTAMP	  result;
+
+    set_out_of_date(result);
 
     /*
      * Because of space constraints and similar things, files are archived
@@ -496,31 +542,28 @@ ArchStatMember (archive, member, hash)
      * to point 'member' to the final component, if there is one, to make
      * the comparisons easier...
      */
-    cp = strrchr (member, '/');
+    cp = strrchr(member, '/');
     if (cp != NULL)
 	member = cp + 1;
 
     ln = Lst_Find(&archives, ArchFindArchive, archive);
     if (ln != NULL) {
 	ar = (Arch *)Lst_Datum(ln);
-
-	he = Hash_FindEntry (&ar->members, member);
-
-	if (he != NULL) {
-	    return ((struct ar_hdr *) Hash_GetValue (he));
-	} else {
-	    /* Try truncated name */
-	    char copy[AR_MAX_NAME_LEN+1];
-	    int len = strlen (member);
-
-	    if (len > AR_MAX_NAME_LEN) {
-		len = AR_MAX_NAME_LEN;
-		strncpy(copy, member, AR_MAX_NAME_LEN);
-		copy[AR_MAX_NAME_LEN] = '\0';
+	end = NULL;
+	he = hash_find(&ar->members, hash_qlookupi(&ar->members, member, &end));
+	if (he != NULL)
+	    return mtime_of_member(he);
+	else {
+	    if (end - member > AR_NAME_SIZE) {
+		/* Try truncated name */
+	    	end = member + AR_NAME_SIZE;
+
+		he = hash_find(&ar->members,
+		    hash_qlookupi(&ar->members, member, &end));
+		if (he != NULL)
+		    return mtime_of_member(he);
 	    }
-	    if ((he = Hash_FindEntry (&ar->members, copy)) != NULL)
-		return ((struct ar_hdr *) Hash_GetValue (he));
-	    return (NULL);
+	    return result;
 	}
     }
 
@@ -536,11 +579,12 @@ ArchStatMember (archive, member, hash)
 
 	 arch = ArchFindMember(archive, member, &sarh, "r");
 
-	if (arch == NULL) {
-	    return (NULL);
-	} else {
+	if (arch == NULL)
+	    return NULL;
+	else {
 	    fclose(arch);
-	    return (&sarh);
+	    grab_date( (time_t)strtol(sarh.ar_date, NULL, 10), result);
+	    return result;
 	}
     }
 
@@ -548,30 +592,29 @@ ArchStatMember (archive, member, hash)
      * We don't have this archive on the list yet, so we want to find out
      * everything that's in it and cache it so we can get at it quickly.
      */
-    arch = fopen (archive, "r");
-    if (arch == NULL) {
+    arch = fopen(archive, "r");
+    if (arch == NULL)
 	return (NULL);
-    }
 
     /*
      * We use the ARMAG string to make sure this is an archive we
      * can handle...
      */
-    if ((fread (magic, SARMAG, 1, arch) != 1) ||
-    	(strncmp (magic, ARMAG, SARMAG) != 0)) {
-	    fclose (arch);
-	    return (NULL);
+    if ((fread(magic, SARMAG, 1, arch) != 1) ||
+    	(strncmp(magic, ARMAG, SARMAG) != 0)) {
+	    fclose(arch);
+	    return NULL;
     }
 
-    ar = (Arch *)emalloc (sizeof (Arch));
-    ar->name = estrdup (archive);
+    ar = (Arch *)emalloc(sizeof (Arch));
+    ar->name = estrdup(archive);
     ar->fnametab = NULL;
     ar->fnamesize = 0;
-    Hash_InitTable (&ar->members, -1);
+    hash_init(&ar->members, 8, &members_info);
     memName[AR_MAX_NAME_LEN] = '\0';
 
-    while (fread ((char *)&arh, sizeof (struct ar_hdr), 1, arch) == 1) {
-	if (strncmp ( arh.ar_fmag, ARFMAG, sizeof (arh.ar_fmag)) != 0) {
+    while (fread((char *)&arh, sizeof (struct ar_hdr), 1, arch) == 1) {
+	if (strncmp( arh.ar_fmag, ARFMAG, sizeof (arh.ar_fmag)) != 0) {
 	    /*
 	     * The header is bogus, so the archive is bad
 	     * and there's no way we can recover...
@@ -587,7 +630,7 @@ ArchStatMember (archive, member, hash)
 	    arh.ar_size[sizeof(arh.ar_size)-1] = '\0';
 	    size = (int) strtol(arh.ar_size, NULL, 10);
 
-	    (void) strncpy (memName, arh.ar_name, sizeof(arh.ar_name));
+	    (void) strncpy(memName, arh.ar_name, sizeof(arh.ar_name));
 	    for (cp = &memName[AR_MAX_NAME_LEN]; *cp == ' '; cp--) {
 		continue;
 	    }
@@ -631,21 +674,21 @@ ArchStatMember (archive, member, hash)
 		if (fread (memName, elen, 1, arch) != 1)
 			goto badarch;
 		memName[elen] = '\0';
-		fseek (arch, -elen, SEEK_CUR);
+		fseek(arch, -elen, SEEK_CUR);
 		if (DEBUG(ARCH) || DEBUG(MAKE)) {
 		    printf("ArchStat: Extended format entry for %s\n", memName);
 		}
 	    }
 #endif
 
-	    he = Hash_CreateEntry(&ar->members, memName, NULL);
-	    Hash_SetValue(he, emalloc(sizeof(struct ar_hdr)));
-	    memcpy(Hash_GetValue(he), &arh, sizeof(struct ar_hdr));
+	    hash_insert(&ar->members,
+		hash_qlookup(&ar->members, memName),
+		    new_arch_member(&arh, memName));
 	}
-	fseek (arch, (size + 1) & ~1, SEEK_CUR);
+	fseek(arch, (size + 1) & ~1, SEEK_CUR);
     }
 
-    fclose (arch);
+    fclose(arch);
 
     Lst_AtEnd(&archives, ar);
 
@@ -653,20 +696,20 @@ ArchStatMember (archive, member, hash)
      * Now that the archive has been read and cached, we can look into
      * the hash table to find the desired member's header.
      */
-    he = Hash_FindEntry (&ar->members, member);
+    he = hash_find(&ar->members,
+	hash_qlookupi(&ar->members, member, &end));
 
-    if (he != NULL) {
-	return ((struct ar_hdr *) Hash_GetValue (he));
-    } else {
-	return (NULL);
-    }
+    if (he != NULL)
+	return mtime_of_member(he);
+    else
+	return result;
 
 badarch:
     fclose(arch);
-    Hash_DeleteTable(&ar->members);
+    hash_delete(&ar->members);
     efree(ar->fnametab);
     free(ar);
-    return NULL;
+    return result;
 }
 
 #ifdef SVR4ARCHIVES
@@ -1006,18 +1049,13 @@ Arch_TouchLib (gn)
  *-----------------------------------------------------------------------
  */
 TIMESTAMP
-Arch_MTime (gn)
+Arch_MTime(gn)
     GNode	  *gn;	      /* Node describing archive member */
 {
-    struct ar_hdr *arhPtr;    /* Header of desired member */
+    gn->mtime = ArchMTimeMember(Varq_Value(ARCHIVE_INDEX, gn),
+	Varq_Value(MEMBER_INDEX, gn),
+	TRUE);
 
-    arhPtr = ArchStatMember(Varq_Value(ARCHIVE_INDEX, gn),
-			     Varq_Value(MEMBER_INDEX, gn),
-			     TRUE);
-    if (arhPtr != NULL)
-	gn->mtime = (time_t) strtol(arhPtr->ar_date, NULL, 10);
-    else
-    	gn->mtime = OUT_OF_DATE;
     return gn->mtime;
 }
 
@@ -1175,25 +1213,20 @@ Arch_LibOODate (gn)
 	    oodate = TRUE;
     } else {
 #ifdef RANLIBMAG
-	struct ar_hdr  	*arhPtr;    /* Header for __.SYMDEF */
 	time_t 	  	modTimeTOC; /* The table-of-contents's mod time */
 
-	arhPtr = ArchStatMember (gn->path, RANLIBMAG, FALSE);
-
-	if (arhPtr != NULL) {
-	    modTimeTOC = (time_t) strtol(arhPtr->ar_date, NULL, 10);
+	modTimeTOC = ArchMTimeMember(gn->path, RANLIBMAG, FALSE);
 
-	    if (DEBUG(ARCH) || DEBUG(MAKE)) {
+	if (!is_out_of_date(modTimeTOC)) {
+	    if (DEBUG(ARCH) || DEBUG(MAKE))
 		printf("%s modified %s...", RANLIBMAG, Targ_FmtTime(modTimeTOC));
-	    }
-	    oodate = (gn->cmtime > modTimeTOC);
+	    oodate = is_before(modTimeTOC, gn->cmtime);
 	} else {
 	    /*
 	     * A library w/o a table of contents is out-of-date
 	     */
-	    if (DEBUG(ARCH) || DEBUG(MAKE)) {
+	    if (DEBUG(ARCH) || DEBUG(MAKE))
 		printf("No t.o.c....");
-	    }
 	    oodate = TRUE;
 	}
 #else
@@ -1208,9 +1241,6 @@ Arch_LibOODate (gn)
  * Arch_Init --
  *	Initialize things for this module.
  *
- * Results:
- *	None.
- *
  * Side Effects:
  *	The 'archives' list is initialized.
  *
diff --git a/usr.bin/make/hash.c b/usr.bin/make/hash.c
deleted file mode 100644
index 9a135f37744..00000000000
--- a/usr.bin/make/hash.c
+++ /dev/null
@@ -1,426 +0,0 @@
-/*	$OpenBSD: hash.c,v 1.6 2000/09/14 13:32:06 espie Exp $	*/
-/*	$NetBSD: hash.c,v 1.6 1996/11/06 17:59:06 christos Exp $	*/
-
-/*
- * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
- * Copyright (c) 1988, 1989 by Adam de Boor
- * Copyright (c) 1989 by Berkeley Softworks
- * 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.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *	This product includes software developed by the University of
- *	California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * 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.
- */
-
-/* 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 "sprite.h"
-#include "make.h"
-#include "hash.h"
-
-#ifndef lint
-#if 0
-static char sccsid[] = "@(#)hash.c	8.1 (Berkeley) 6/6/93";
-#else
-UNUSED
-static char rcsid[] = "$OpenBSD: hash.c,v 1.6 2000/09/14 13:32:06 espie Exp $";
-#endif
-#endif /* not lint */
-
-/*
- * Forward references to local procedures that are used before they're
- * defined:
- */
-
-static void RebuildTable __P((Hash_Table *));
-
-/*
- * The following defines the ratio of # entries to # buckets
- * at which we rebuild the table to make it larger.
- */
-
-#define rebuildLimit 8
-
-/*
- *---------------------------------------------------------
- *
- * Hash_InitTable --
- *
- *	This routine just sets up the hash table.
- *
- * Results:
- *	None.
- *
- * Side Effects:
- *	Memory is allocated for the initial bucket area.
- *
- *---------------------------------------------------------
- */
-
-void
-Hash_InitTable(t, numBuckets)
-	register Hash_Table *t;	/* Structure to use to hold table. */
-	int 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. */
-{
-	register int i;
-	register 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->size = i;
-	t->mask = i - 1;
-	t->bucketPtr = hp = (struct Hash_Entry **)emalloc(sizeof(*hp) * i);
-	while (--i >= 0)
-		*hp++ = NULL;
-}
-
-/*
- *---------------------------------------------------------
- *
- * 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(t)
-	Hash_Table *t;
-{
-	register struct Hash_Entry **hp, *h, *nexth = NULL;
-	register int i;
-
-	for (hp = t->bucketPtr, i = t->size; --i >= 0;) {
-		for (h = *hp++; h != NULL; h = nexth) {
-			nexth = h->next;
-			free((char *)h);
-		}
-	}
-	free((char *)t->bucketPtr);
-
-	/*
-	 * Set up the hash table to cause memory faults on any future access
-	 * attempts until re-initialization.
-	 */
-	t->bucketPtr = NULL;
-}
-
-/*
- *---------------------------------------------------------
- *
- * Hash_FindEntry --
- *
- * 	Searches a hash table for an entry corresponding to key.
- *
- * Results:
- *	The return value is a pointer to the entry for key,
- *	if key was present in the table.  If key was not
- *	present, NULL is returned.
- *
- * Side Effects:
- *	None.
- *
- *---------------------------------------------------------
- */
-
-Hash_Entry *
-Hash_FindEntry(t, key)
-	Hash_Table *t;		/* Hash table to search. */
-	char *key;		/* A hash key. */
-{
-	register Hash_Entry *e;
-	register unsigned h;
-	register char *p;
-
-	for (h = 0, p = key; *p;)
-		h = (h << 5) - h + *p++;
-	p = key;
-	for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next)
-		if (e->namehash == h && strcmp(e->name, p) == 0)
-			return (e);
-	return (NULL);
-}
-
-/*
- *---------------------------------------------------------
- *
- * Hash_CreateEntry --
- *
- *	Searches a hash table for an entry corresponding to
- *	key.  If no entry is found, then one is created.
- *
- * 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(t, key, newPtr)
-	register Hash_Table *t;	/* Hash table to search. */
-	char *key;		/* A hash key. */
-	Boolean *newPtr;	/* Filled in with TRUE if new entry created,
-				 * FALSE otherwise. */
-{
-	register Hash_Entry *e;
-	register unsigned h;
-	register char *p;
-	int keylen;
-	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.
-	 */
-	for (h = 0, p = key; *p;)
-		h = (h << 5) - h + *p++;
-	keylen = p - key;
-	p = key;
-	for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) {
-		if (e->namehash == h && strcmp(e->name, p) == 0) {
-			if (newPtr != NULL)
-				*newPtr = FALSE;
-			return (e);
-		}
-	}
-
-	/*
-	 * The desired entry isn't there.  Before allocating a new entry,
-	 * expand the table if necessary (and this changes the resulting
-	 * bucket chain).
-	 */
-	if (t->numEntries >= rebuildLimit * t->size)
-		RebuildTable(t);
-	e = (Hash_Entry *) emalloc(sizeof(*e) + keylen);
-	hp = &t->bucketPtr[h & t->mask];
-	e->next = *hp;
-	*hp = e;
-	e->clientData = NULL;
-	e->namehash = h;
-	(void) strcpy(e->name, p);
-	t->numEntries++;
-
-	if (newPtr != NULL)
-		*newPtr = TRUE;
-	return (e);
-}
-
-/*
- *---------------------------------------------------------
- *
- * 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(t, e)
-	Hash_Table *t;
-	Hash_Entry *e;
-{
-	register 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((char *)p);
-			t->numEntries--;
-			return;
-		}
-	}
-	(void) write(2, "bad call to Hash_DeleteEntry\n", 29);
-	abort();
-}
-
-/*
- *---------------------------------------------------------
- *
- * Hash_EnumFirst --
- *	This procedure sets things up for a complete search
- *	of all entries recorded in the hash table.
- *
- * 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(t, searchPtr)
-	Hash_Table *t;			/* Table to be searched. */
-	register Hash_Search *searchPtr;/* Area in which to keep state
-					 * about search.*/
-{
-	searchPtr->tablePtr = t;
-	searchPtr->nextIndex = 0;
-	searchPtr->hashEntryPtr = NULL;
-	return Hash_EnumNext(searchPtr);
-}
-
-/*
- *---------------------------------------------------------
- *
- * Hash_EnumNext --
- *    This procedure returns successive entries in the hash table.
- *
- * 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(searchPtr)
-	register Hash_Search *searchPtr; /* Area used to keep state about
-					    search. */
-{
-	register Hash_Entry *e;
-	Hash_Table *t = searchPtr->tablePtr;
-
-	/*
-	 * The hashEntryPtr field points to the most recently returned
-	 * entry, or is null if we are starting up.  If not null, we have
-	 * to start at the next one in the chain.
-	 */
-	e = searchPtr->hashEntryPtr;
-	if (e != NULL)
-		e = e->next;
-	/*
-	 * 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);
-}
-
-/*
- *---------------------------------------------------------
- *
- * 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(t)
-	register Hash_Table *t;
-{
-	register Hash_Entry *e, *next = NULL, **hp, **xp;
-	register int i, mask;
-        register Hash_Entry **oldhp;
-	int oldsize;
-
-	oldhp = t->bucketPtr;
-	oldsize = i = t->size;
-	i <<= 1;
-	t->size = i;
-	t->mask = mask = i - 1;
-	t->bucketPtr = hp = (struct Hash_Entry **) emalloc(sizeof(*hp) * i);
-	while (--i >= 0)
-		*hp++ = NULL;
-	for (hp = oldhp, i = oldsize; --i >= 0;) {
-		for (e = *hp++; e != NULL; e = next) {
-			next = e->next;
-			xp = &t->bucketPtr[e->namehash & mask];
-			e->next = *xp;
-			*xp = e;
-		}
-	}
-	free((char *)oldhp);
-}
diff --git a/usr.bin/make/hash.h b/usr.bin/make/hash.h
deleted file mode 100644
index d43f8678b66..00000000000
--- a/usr.bin/make/hash.h
+++ /dev/null
@@ -1,119 +0,0 @@
-/*	$OpenBSD: hash.h,v 1.6 2000/06/10 01:41:05 espie Exp $	*/
-/*	$NetBSD: hash.h,v 1.5 1996/11/06 17:59:07 christos Exp $	*/
-
-/*
- * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
- * Copyright (c) 1988, 1989 by Adam de Boor
- * Copyright (c) 1989 by Berkeley Softworks
- * 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.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *	This product includes software developed by the University of
- *	California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * 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.
- *
- *	from: @(#)hash.h	8.1 (Berkeley) 6/6/93
- */
-
-/* hash.h --
- *
- * 	This file contains definitions used by the hash module,
- * 	which maintains hash tables.
- */
-
-#ifndef	_HASH
-#define	_HASH
-
-/*
- * The following defines one entry in the hash table.
- */
-
-typedef struct Hash_Entry {
-    struct Hash_Entry *next;		/* Used to link together all the
-    					 * entries associated with the same
-					 * bucket. */
-    void 	      *clientData;	/* Arbitrary piece of data associated
-    					 * with key. */
-    unsigned	      namehash;		/* hash value of key */
-    char	      name[1];		/* key string */
-} Hash_Entry;
-
-typedef struct Hash_Table {
-    struct Hash_Entry **bucketPtr;/* Pointers to Hash_Entry, one
-    				 * for each bucket in the table. */
-    int 	size;		/* Actual size of array. */
-    int 	numEntries;	/* Number of entries in the table. */
-    int 	mask;		/* Used to select bits for hashing. */
-} Hash_Table;
-
-/*
- * The following structure is used by the searching routines
- * to record where we are in the search.
- */
-
-typedef struct Hash_Search {
-    Hash_Table  *tablePtr;	/* Table being searched. */
-    int 	nextIndex;	/* Next bucket to check (after current). */
-    Hash_Entry 	*hashEntryPtr;	/* Next entry to check in current bucket. */
-} Hash_Search;
-
-/*
- * Macros.
- */
-
-/*
- * void *Hash_GetValue(h)
- *     Hash_Entry *h;
- */
-
-#define Hash_GetValue(h) ((h)->clientData)
-
-/*
- * Hash_SetValue(h, val);
- *     Hash_Entry *h;
- *     char *val;
- */
-
-#define Hash_SetValue(h, val) ((h)->clientData = (val))
-
-/*
- * Hash_Size(n) returns the number of words in an object of n bytes
- */
-
-#define	Hash_Size(n)	(((n) + sizeof (int) - 1) / sizeof (int))
-
-void Hash_InitTable __P((Hash_Table *, int));
-void Hash_DeleteTable __P((Hash_Table *));
-Hash_Entry *Hash_FindEntry __P((Hash_Table *, char *));
-Hash_Entry *Hash_CreateEntry __P((Hash_Table *, char *, Boolean *));
-void Hash_DeleteEntry __P((Hash_Table *, Hash_Entry *));
-Hash_Entry *Hash_EnumFirst __P((Hash_Table *, Hash_Search *));
-Hash_Entry *Hash_EnumNext __P((Hash_Search *));
-
-#endif /* _HASH */