Use the new hash scheme to store the target nodes.

Scrap the list of all targets: it only slows make down.
The only visible difference is that the list of all targets is not
shown in order when debugging.

5 files changed, 96 insertions, 142 deletions

diff --git a/usr.bin/make/extern.h b/usr.bin/make/extern.h
index 0afd9d673a5..1569bf277a3 100644
--- a/usr.bin/make/extern.h
+++ b/usr.bin/make/extern.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: extern.h,v 1.31 2000/09/14 13:35:38 espie Exp $	*/
+/*	$OpenBSD: extern.h,v 1.32 2000/09/14 13:40:03 espie Exp $	*/
 /*	$NetBSD: nonints.h,v 1.12 1996/11/06 17:59:19 christos Exp $	*/
 
 /*-
@@ -131,8 +131,8 @@ extern void Suff_PrintAll __P((void));
 /* targ.c */
 extern void Targ_Init __P((void));
 extern void Targ_End __P((void));
-extern GNode *Targ_NewGN __P((char *));
-extern GNode *Targ_FindNode __P((char *, int));
+extern GNode *Targ_NewGN __P((const char *, const char *));
+extern GNode *Targ_FindNode __P((const char *, int));
 extern void Targ_FindList __P((Lst, Lst));
 extern Boolean Targ_Ignore __P((GNode *));
 extern Boolean Targ_Silent __P((GNode *));
diff --git a/usr.bin/make/make.h b/usr.bin/make/make.h
index 1e95e09ff21..386ba0b8c65 100644
--- a/usr.bin/make/make.h
+++ b/usr.bin/make/make.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: make.h,v 1.25 2000/09/14 13:32:07 espie Exp $	*/
+/*	$OpenBSD: make.h,v 1.26 2000/09/14 13:40:03 espie Exp $	*/
 /*	$NetBSD: make.h,v 1.15 1997/03/10 21:20:00 christos Exp $	*/
 
 /*
@@ -139,8 +139,7 @@ typedef struct hash GSymT;
  *	17) a Lst of strings that are commands to be given to a shell
  *	   to create this target.
  */
-typedef struct GNode {
-    char            *name;     	/* The target's name */
+typedef struct GNode_ {
     char    	    *path;     	/* The full pathname of the file */
     int             type;      	/* Its type (see the OP flags, below) */
     int		    order;	/* Its wait weight */
@@ -193,6 +192,7 @@ typedef struct GNode {
     struct _Suff    *suffix;	/* Suffix for the node (determined by
 				 * Suff_FindDeps and opaque to everyone
 				 * but the Suff module) */
+    char      name[1];     	/* The target's name */
 } GNode;
 
 /*
diff --git a/usr.bin/make/parse.c b/usr.bin/make/parse.c
index 9f3c4a8e587..b68f85b013b 100644
--- a/usr.bin/make/parse.c
+++ b/usr.bin/make/parse.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: parse.c,v 1.54 2000/09/14 13:36:46 espie Exp $	*/
+/*	$OpenBSD: parse.c,v 1.55 2000/09/14 13:40:03 espie Exp $	*/
 /*	$NetBSD: parse.c,v 1.29 1997/03/10 21:20:04 christos Exp $	*/
 
 /*
@@ -102,7 +102,7 @@
 static char sccsid[] = "@(#)parse.c	8.3 (Berkeley) 3/19/94";
 #else
 UNUSED
-static char rcsid[] = "$OpenBSD: parse.c,v 1.54 2000/09/14 13:36:46 espie Exp $";
+static char rcsid[] = "$OpenBSD: parse.c,v 1.55 2000/09/14 13:40:03 espie Exp $";
 #endif
 #endif /* not lint */
 
@@ -343,7 +343,7 @@ ParseDoOp (gnp, opp)
 	register GNode	*cohort;
 	LstNode	    	ln;
 
-	cohort = Targ_NewGN(gn->name);
+	cohort = Targ_NewGN(gn->name, NULL);
 	/*
 	 * Duplicate links to parents so graph traversal is simple. Perhaps
 	 * some type bits should be duplicated?
@@ -794,7 +794,7 @@ ParseDoDependency (line)
 			Lst_AtEnd(&targets, gn);
 			break;
 		    case Default:
-			gn = Targ_NewGN(".DEFAULT");
+			gn = Targ_NewGN(".DEFAULT", NULL);
 			gn->type |= (OP_NOTMAIN|OP_TRANSFORM);
 			Lst_AtEnd(&targets, gn);
 			DEFAULT = gn;
diff --git a/usr.bin/make/suff.c b/usr.bin/make/suff.c
index 4c32f092417..26541b915fc 100644
--- a/usr.bin/make/suff.c
+++ b/usr.bin/make/suff.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: suff.c,v 1.36 2000/09/14 13:32:07 espie Exp $	*/
+/*	$OpenBSD: suff.c,v 1.37 2000/09/14 13:40:03 espie Exp $	*/
 /*	$NetBSD: suff.c,v 1.13 1996/11/06 17:59:25 christos Exp $	*/
 
 /*
@@ -100,7 +100,7 @@
 static char sccsid[] = "@(#)suff.c	8.4 (Berkeley) 3/21/94";
 #else
 UNUSED
-static char rcsid[] = "$OpenBSD: suff.c,v 1.36 2000/09/14 13:32:07 espie Exp $";
+static char rcsid[] = "$OpenBSD: suff.c,v 1.37 2000/09/14 13:40:03 espie Exp $";
 #endif
 #endif /* not lint */
 
@@ -567,7 +567,7 @@ Suff_AddTransform (line)
 	 * Make a new graph node for the transformation. It will be filled in
 	 * by the Parse module.
 	 */
-	gn = Targ_NewGN (line);
+	gn = Targ_NewGN(line, NULL);
 	Lst_AtEnd(&transforms, gn);
     } else {
 	/*
diff --git a/usr.bin/make/targ.c b/usr.bin/make/targ.c
index b0ed4c1e5c5..5abf9aa147e 100644
--- a/usr.bin/make/targ.c
+++ b/usr.bin/make/targ.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: targ.c,v 1.26 2000/09/14 13:32:08 espie Exp $	*/
+/*	$OpenBSD: targ.c,v 1.27 2000/09/14 13:40:03 espie Exp $	*/
 /*	$NetBSD: targ.c,v 1.11 1997/02/20 16:51:50 christos Exp $	*/
 
 /*
@@ -41,9 +41,7 @@
 
 /*-
  * targ.c --
- *	Functions for maintaining the Lst allTargets. Target nodes are
- * kept in two structures: a Lst, maintained by the list library, and a
- * hash table, maintained by the hash library.
+ *		Target nodes are kept into a hash table.
  *
  * Interface:
  *	Targ_Init 	    	Initialization procedure.
@@ -77,10 +75,12 @@
  *	    	  	    	print something for suffixes, too, but...
  */
 
+#include	  <stddef.h>
 #include	  <stdio.h>
 #include	  <time.h>
 #include	  "make.h"
-#include	  "hash.h"
+#include	  "ohash.h"
+#include 	  "hash.h"
 #include	  "dir.h"
 
 #ifndef lint
@@ -88,21 +88,21 @@
 static char sccsid[] = "@(#)targ.c	8.2 (Berkeley) 3/19/94";
 #else
 UNUSED
-static char *rcsid = "$OpenBSD: targ.c,v 1.26 2000/09/14 13:32:08 espie Exp $";
+static char *rcsid = "$OpenBSD: targ.c,v 1.27 2000/09/14 13:40:03 espie Exp $";
 #endif
 #endif /* not lint */
 
-static LIST       allTargets;	/* the list of all targets found so far */
 #ifdef CLEANUP
 static LIST	  allGNs;	/* List of all the GNodes */
 #endif
-static Hash_Table targets;	/* a hash table of same */
+static struct hash targets; 	/* a hash table of same */
+static struct hash_info gnode_info = { 
+	offsetof(GNode, name), 
+    NULL, hash_alloc, hash_free, element_alloc };
 
-#define HTSIZE	191		/* initial size of hash table */
-
-static void TargPrintOnlySrc __P((void *));
+static void TargPrintOnlySrc __P((GNode *));
 static void TargPrintName __P((void *));
-static void TargPrintNode __P((void *, void *));
+static void TargPrintNode __P((GNode *, int));
 #ifdef CLEANUP
 static void TargFreeGN __P((void *));
 #endif
@@ -113,7 +113,7 @@ static void TargFreeGN __P((void *));
  *	Initialize this module
  *
 * Side Effects:
- *	The allTargets list and the targets hash table are initialized
+ *	The targets hash table is initialized
  *-----------------------------------------------------------------------
  */
 void
@@ -122,8 +122,8 @@ Targ_Init()
 #ifdef CLEANUP
     Lst_Init(&allGNs);
 #endif
-    Lst_Init(&allTargets);
-    Hash_InitTable(&targets, HTSIZE);
+    /* A small make file already creates 200 targets.  */
+    hash_init(&targets, 10, &gnode_info);
 }
 
 /*-
@@ -131,9 +131,6 @@ Targ_Init()
  * Targ_End --
  *	Finalize this module
  *
- * Results:
- *	None
- *
  * Side Effects:
  *	All lists and gnodes are cleared
  *-----------------------------------------------------------------------
@@ -142,9 +139,8 @@ void
 Targ_End ()
 {
 #ifdef CLEANUP
-    Lst_Destroy(&allTargets, NOFREE);
     Lst_Destroy(&allGNs, TargFreeGN);
-    Hash_DeleteTable(&targets);
+    hash_delete(&targets);
 #endif
 }
 
@@ -158,18 +154,18 @@ Targ_End ()
  *	of the passed name
  *
  * Side Effects:
- *	The gnode is added to the list of all gnodes.
+ *	The gnode is added to the set of all gnodes.
  *-----------------------------------------------------------------------
  */
 GNode *
-Targ_NewGN (name)
-    char           *name;	/* the name to stick in the new node */
+Targ_NewGN(name, end)
+    const char		*name;	/* the name to stick in the new node */
+    const char 		*end;
 {
-    register GNode *gn;
+    GNode 		*gn;
 
-    gn = (GNode *) emalloc (sizeof (GNode));
-    gn->name = estrdup (name);
-    gn->path = (char *) 0;
+    gn = hash_create_entry(&gnode_info, name, &end);
+    gn->path = NULL;
     if (name[0] == '-' && name[1] == 'l') {
 	gn->type = OP_LIB;
     } else {
@@ -197,7 +193,7 @@ Targ_NewGN (name)
     Lst_AtEnd(&allGNs, gn);
 #endif
 
-    return (gn);
+    return gn;
 }
 
 #ifdef CLEANUP
@@ -219,8 +215,6 @@ TargFreeGN(gnp)
 {
     GNode *gn = (GNode *) gnp;
 
-
-    free(gn->name);
     efree(gn->path);
     Lst_Destroy(&gn->iParents, NOFREE);
     Lst_Destroy(&gn->cohorts, NOFREE);
@@ -250,33 +244,25 @@ TargFreeGN(gnp)
  *-----------------------------------------------------------------------
  */
 GNode *
-Targ_FindNode (name, flags)
-    char           *name;	/* the name to find */
-    int             flags;	/* flags governing events when target not
+Targ_FindNode(name, flags)
+    const char		*name;	/* the name to find */
+    int			flags;	/* flags governing events when target not
 				 * found */
 {
-    GNode         *gn;	      /* node in that element */
-    Hash_Entry	  *he;	      /* New or used hash entry for node */
-    Boolean	  isNew;      /* Set TRUE if Hash_CreateEntry had to create */
-			      /* an entry for the node */
-
-
-    if (flags & TARG_CREATE) {
-	he = Hash_CreateEntry (&targets, name, &isNew);
-	if (isNew) {
-	    gn = Targ_NewGN (name);
-	    Hash_SetValue (he, gn);
-	    Lst_AtEnd(&allTargets, gn);
-	}
-    } else {
-	he = Hash_FindEntry (&targets, name);
-    }
+    const char		*end = NULL;
+    GNode         	*gn;	/* node in that element */
+    unsigned int	slot;
 
-    if (he == NULL) {
-	return (NULL);
-    } else {
-	return ((GNode *) Hash_GetValue (he));
+    slot = hash_qlookupi(&targets, name, &end);
+
+    gn = hash_find(&targets, slot);
+    
+    if (gn == NULL && (flags & TARG_CREATE)) {
+    	gn = Targ_NewGN(name, end);
+	hash_insert(&targets, slot, gn);
     }
+
+    return gn;
 }
 
 /*-
@@ -319,69 +305,48 @@ Targ_FindList(nodes, names)
  *-----------------------------------------------------------------------
  * Targ_Ignore  --
  *	Return true if should ignore errors when creating gn
- *
- * Results:
- *	TRUE if should ignore errors
- *
- * Side Effects:
- *	None
  *-----------------------------------------------------------------------
  */
 Boolean
-Targ_Ignore (gn)
+Targ_Ignore(gn)
     GNode          *gn;		/* node to check for */
 {
-    if (ignoreErrors || gn->type & OP_IGNORE) {
-	return (TRUE);
-    } else {
-	return (FALSE);
-    }
+    if (ignoreErrors || gn->type & OP_IGNORE)
+	return TRUE;
+    else
+	return FALSE;
 }
 
 /*-
  *-----------------------------------------------------------------------
  * Targ_Silent  --
  *	Return true if be silent when creating gn
- *
- * Results:
- *	TRUE if should be silent
- *
- * Side Effects:
- *	None
  *-----------------------------------------------------------------------
  */
 Boolean
-Targ_Silent (gn)
+Targ_Silent(gn)
     GNode          *gn;		/* node to check for */
 {
-    if (beSilent || gn->type & OP_SILENT) {
-	return (TRUE);
-    } else {
-	return (FALSE);
-    }
+    if (beSilent || gn->type & OP_SILENT)
+	return TRUE;
+    else
+	return FALSE;
 }
 
 /*-
  *-----------------------------------------------------------------------
  * Targ_Precious --
  *	See if the given target is precious
- *
- * Results:
- *	TRUE if it is precious. FALSE otherwise
- *
- * Side Effects:
- *	None
  *-----------------------------------------------------------------------
  */
 Boolean
 Targ_Precious (gn)
     GNode          *gn;		/* the node to check */
 {
-    if (allPrecious || (gn->type & (OP_PRECIOUS|OP_DOUBLEDEP))) {
-	return (TRUE);
-    } else {
-	return (FALSE);
-    }
+    if (allPrecious || (gn->type & (OP_PRECIOUS|OP_DOUBLEDEP)))
+	return TRUE;
+    else
+	return FALSE;
 }
 
 /******************* DEBUG INFO PRINTING ****************/
@@ -393,15 +358,12 @@ static GNode	  *mainTarg;	/* the main target, as set by Targ_SetMain */
  *	Set our idea of the main target we'll be creating. Used for
  *	debugging output.
  *
- * Results:
- *	None.
- *
  * Side Effects:
  *	"mainTarg" is set to the main target's node.
  *-----------------------------------------------------------------------
  */
 void
-Targ_SetMain (gn)
+Targ_SetMain(gn)
     GNode   *gn;  	/* The main target we'll create */
 {
     mainTarg = gn;
@@ -439,11 +401,11 @@ Targ_PrintCmd(cmd)
  *-----------------------------------------------------------------------
  */
 char *
-Targ_FmtTime (time)
+Targ_FmtTime(time)
     time_t    time;
 {
     struct tm	  	*parts;
-    static char			buf[128];
+    static char		buf[128];
 
     parts = localtime(&time);
     strftime(buf, sizeof buf, "%k:%M:%S %b %d, %Y", parts);
@@ -456,18 +418,13 @@ Targ_FmtTime (time)
  * Targ_PrintType --
  *	Print out a type field giving only those attributes the user can
  *	set.
- *
- * Results:
- *
- * Side Effects:
- *
  *-----------------------------------------------------------------------
  */
 void
-Targ_PrintType (type)
-    register int    type;
+Targ_PrintType(type)
+    int    type;
 {
-    register int    tbit;
+    int    tbit;
 
 #ifdef __STDC__
 #define PRINTBIT(attr)	case CONCAT(OP_,attr): printf("." #attr " "); break
@@ -509,12 +466,10 @@ Targ_PrintType (type)
  *-----------------------------------------------------------------------
  */
 static void
-TargPrintNode(gnp, passp)
-    void *gnp;
-    void *passp;
+TargPrintNode(gn, pass)
+    GNode 	*gn;
+    int  	pass;
 {
-    GNode         *gn = (GNode *)gnp;
-    int	    	  pass = *(int *)passp;
     if (!OP_NOP(gn->type)) {
 	printf("#\n");
 	if (gn == mainTarg)
@@ -567,8 +522,12 @@ TargPrintNode(gnp, passp)
 	fputc('\n', stdout);
 	Lst_Every(&gn->commands, Targ_PrintCmd);
 	printf("\n\n");
-	if (gn->type & OP_DOUBLEDEP)
-	    Lst_ForEach(&gn->cohorts, TargPrintNode, &pass);
+	if (gn->type & OP_DOUBLEDEP) {
+	    LstNode ln;
+	    
+	    for (ln = Lst_First(&gn->cohorts); ln != NULL; ln = Lst_Adv(ln)) 
+		    TargPrintNode((GNode *)Lst_Datum(ln), pass);
+	}
     }
 }
 
@@ -576,18 +535,12 @@ TargPrintNode(gnp, passp)
  *-----------------------------------------------------------------------
  * TargPrintOnlySrc --
  *	Print only those targets that are just a source.
- *
- * Side Effects:
- *	The name of each file is printed preceeded by #\t
- *
  *-----------------------------------------------------------------------
  */
 static void
-TargPrintOnlySrc(gnp)
-    void *gnp;
+TargPrintOnlySrc(gn)
+    GNode 	*gn;
 {
-    GNode   	  *gn = (GNode *)gnp;
-
     if (OP_NOP(gn->type))
 	printf("#\t%s [%s]\n", gn->name, gn->path ? gn->path : gn->name);
 }
@@ -595,25 +548,26 @@ TargPrintOnlySrc(gnp)
 /*-
  *-----------------------------------------------------------------------
  * Targ_PrintGraph --
- *	print the entire graph. heh heh
- *
- * Results:
- *	none
- *
- * Side Effects:
- *	lots o' output
+ *	print the entire graph.
  *-----------------------------------------------------------------------
  */
 void
-Targ_PrintGraph (pass)
-    int	    pass; 	/* Which pass this is. 1 => no processing
-			 * 2 => processing done */
+Targ_PrintGraph(pass)
+    int	    		pass; 	/* Which pass this is. 1 => no processing
+			 	 * 2 => processing done */
 {
+    GNode		*gn;
+    unsigned int	i;
+
     printf("#*** Input graph:\n");
-    Lst_ForEach(&allTargets, TargPrintNode, &pass);
+    for (gn = hash_first(&targets, &i); gn != NULL; 
+	gn = hash_next(&targets, &i))
+	    TargPrintNode(gn, pass);
     printf("\n\n");
     printf("#\n#   Files that are only sources:\n");
-    Lst_Every(&allTargets, TargPrintOnlySrc);
+    for (gn = hash_first(&targets, &i); gn != NULL; 
+	gn = hash_next(&targets, &i))
+		TargPrintOnlySrc(gn);
     printf("#*** Global Variables:\n");
     Var_Dump(VAR_GLOBAL);
     printf("#*** Command-line Variables:\n");