I was sure I had committed this already, grrrr.

Anyways, switch to a growable array for job to do.
Allows us to randomize it.
fix manpage.
do not add delay if just one job to run.

5 files changed, 77 insertions, 25 deletions

diff --git a/usr.bin/make/garray.h b/usr.bin/make/garray.h
index 7cc3562b4b4..91d085e26f7 100644
--- a/usr.bin/make/garray.h
+++ b/usr.bin/make/garray.h
@@ -2,7 +2,7 @@
 #define GARRAY_H
 
 /* $OpenPackages$ */
-/* $OpenBSD: garray.h,v 1.3 2007/09/17 10:12:35 espie Exp $ */
+/* $OpenBSD: garray.h,v 1.4 2007/12/01 15:14:34 espie Exp $ */
 /* Growable array implementation */
 
 /*
@@ -60,6 +60,21 @@ do { 							\
 	(l)->a[(l)->n++] = (gn); 			\
 } while (0)
 
+#define Array_Push(l, gn)	Array_AtEnd(l, gn)
+
+#define Array_Pop(l) \
+	((l)->n > 0 ?  (l)->a[--(l)->n] : NULL)
+
+#define Array_PushNew(l, gn) \
+do {						\
+	unsigned int i;				\
+	for (i = 0; i < (l)->n; i++)		\
+		if ((l)->a[i] == (gn))		\
+		    break;			\
+	if (i == (l)->n)			\
+		Array_Push(l, gn);		\
+} while (0)
+
 #define Array_Find(l, func, v)			\
 do {						\
 	unsigned int i;				\
diff --git a/usr.bin/make/job.c b/usr.bin/make/job.c
index 0124a7afbb4..7fe27c1c026 100644
--- a/usr.bin/make/job.c
+++ b/usr.bin/make/job.c
@@ -1,5 +1,5 @@
 /*	$OpenPackages$ */
-/*	$OpenBSD: job.c,v 1.109 2007/11/28 09:40:08 espie Exp $	*/
+/*	$OpenBSD: job.c,v 1.110 2007/12/01 15:14:34 espie Exp $	*/
 /*	$NetBSD: job.c,v 1.16 1996/11/06 17:59:08 christos Exp $	*/
 
 /*
@@ -764,7 +764,8 @@ JobExec(Job *job)
 #endif /* USE_PGRP */
 
 		if (random_delay)
-			usleep(random() % random_delay);
+			if (!(nJobs == 1 && no_jobs_left()))
+				usleep(random() % random_delay);
 
 		/* most cases won't return, but will exit directly */
 		result = run_gnode(job->node, 1);
diff --git a/usr.bin/make/make.1 b/usr.bin/make/make.1
index 69d356b90f1..8e9c1337240 100644
--- a/usr.bin/make/make.1
+++ b/usr.bin/make/make.1
@@ -1,4 +1,4 @@
-.\"	$OpenBSD: make.1,v 1.75 2007/11/28 09:40:08 espie Exp $
+.\"	$OpenBSD: make.1,v 1.76 2007/12/01 15:14:34 espie Exp $
 .\"	$OpenPackages$
 .\"	$NetBSD: make.1,v 1.18 1997/03/10 21:19:53 christos Exp $
 .\"
@@ -31,7 +31,7 @@
 .\"
 .\"	from: @(#)make.1	8.4 (Berkeley) 3/19/94
 .\"
-.Dd $Mdocdate: November 28 2007 $
+.Dd $Mdocdate: December 1 2007 $
 .Dt MAKE 1
 .Os
 .Sh NAME
@@ -175,14 +175,15 @@ Also known as loud behavior.
 Print debugging information about making targets, including modification
 dates.
 .It Ar p
-Help finding concurrency issues for parallel make by adding some randomization.
+Help finding concurrency issues for parallel make by adding some 
+randomization.
 If
 .Va RANDOM_ORDER
 is defined,
 targets will be shuffled before being built.
 If
 .Va RANDOM_DELAY
-is defined, 
+is defined,
 .Nm
 will wait between 0 and ${RANDOM_DELAY} seconds at the start of each job.
 A given random seed can be forced by setting
diff --git a/usr.bin/make/make.c b/usr.bin/make/make.c
index 450ba011b11..0e669352313 100644
--- a/usr.bin/make/make.c
+++ b/usr.bin/make/make.c
@@ -1,5 +1,5 @@
 /*	$OpenPackages$ */
-/*	$OpenBSD: make.c,v 1.55 2007/11/28 09:41:03 espie Exp $	*/
+/*	$OpenBSD: make.c,v 1.56 2007/12/01 15:14:34 espie Exp $	*/
 /*	$NetBSD: make.c,v 1.10 1996/11/06 17:59:15 christos Exp $	*/
 
 /*
@@ -78,12 +78,18 @@
 #include "engine.h"
 #include "lst.h"
 #include "targ.h"
+#include "garray.h"
+#include "memory.h"
+
+/* what gets added each time. Kept as one static array so that it doesn't
+ * get resized every time.
+ */
+static struct growableArray examine;
+/* The current fringe of the graph. These are nodes which await examination by
+ * MakeOODate. It is added to by Make_Update and subtracted from by
+ * MakeStartJobs */
+static struct growableArray toBeMade;	
 
-static LIST	toBeMade;	/* The current fringe of the graph. These
-				 * are nodes which await examination by
-				 * MakeOODate. It is added to by
-				 * Make_Update and subtracted from by
-				 * MakeStartJobs */
 static struct ohash targets;	/* stuff we must build */
 
 static void MakeAddChild(void *, void *);
@@ -100,6 +106,12 @@ static void random_setup(void);
 static bool randomize_queue;
 long random_delay = 0;
 
+bool 
+no_jobs_left()
+{
+	return Array_IsEmpty(&toBeMade);
+}
+
 static void
 random_setup()
 {
@@ -123,6 +135,25 @@ random_setup()
 	}
 }
 
+static void
+randomize_garray(struct growableArray *g)
+{
+	/* This is a fairly standard algorithm to randomize an array. */
+	unsigned int i, v;
+	GNode *e;
+
+	for (i = g->n; i > 0; i--) {
+		v = random() % i;
+		if (v == i-1)
+			continue;
+		else {
+			e = g->a[i-1];
+			g->a[i-1] = g->a[v];
+			g->a[v] = e;
+		}
+	}
+}
+
 static bool
 has_unmade_predecessor(GNode *gn)
 {
@@ -158,7 +189,7 @@ requeue_successors(GNode *gn)
 
 		if (succ->must_make && succ->unmade == 0 
 		    && succ->built_status == UNKNOWN)
-			(void)Lst_QueueNew(&toBeMade, succ);
+			Array_PushNew(&toBeMade, succ);
 	}
 }
 
@@ -245,7 +276,7 @@ Make_Update(GNode *cgn)	/* the child node */
 				 */
 				if (DEBUG(MAKE))
 					printf("QUEUING ");
-				Lst_Push(&toBeMade, pgn);
+				Array_Push(&toBeMade, pgn);
 			} else if (pgn->unmade < 0) {
 				Error("Child %s discovered graph cycles through %s", cgn->name, pgn->name);
 			}
@@ -266,7 +297,7 @@ try_to_make_node(GNode *gn)
 		if (DEBUG(MAKE))
 			printf(" Requeuing (%d)\n", gn->unmade);
 		add_targets_to_make(&gn->children);
-		Lst_Push(&toBeMade, gn);
+		Array_Push(&toBeMade, gn);
 		return false;
 	}
 	if (has_been_built(gn)) {
@@ -334,7 +365,7 @@ MakeStartJobs(void)
 {
 	GNode	*gn;
 
-	while (!Job_Full() && (gn = (GNode *)Lst_Pop(&toBeMade)) != NULL) {
+	while (!Job_Full() && (gn = Array_Pop(&toBeMade)) != NULL) {
 		if (try_to_make_node(gn))
 			return true;
 	}
@@ -394,12 +425,12 @@ MakePrintStatus(
 
 
 static void
-MakeAddChild(void *to_addp, void *lp)
+MakeAddChild(void *to_addp, void *ap)
 {
 	GNode *gn = (GNode *)to_addp;
 
 	if (!gn->must_make && !(gn->type & OP_USE))
-		Lst_Push((Lst)lp, gn);
+		Array_Push((struct growableArray *)ap, gn);
 }
 
 static void
@@ -416,12 +447,12 @@ static void
 add_targets_to_make(Lst todo)
 {
 	GNode *gn;
-	LIST examine;
+
 	unsigned int slot;
 
-	Lst_Clone(&examine, todo, NOCOPY);
+	AppendList2Array(todo, &examine);
 
-	while ((gn = (GNode *)Lst_Pop(&examine)) != NULL) {
+	while ((gn = Array_Pop(&examine)) != NULL) {
 		if (gn->must_make) 	/* already known */
 			continue;
 		gn->must_make = true;
@@ -449,9 +480,11 @@ add_targets_to_make(Lst todo)
 		} else {
 			if (DEBUG(MAKE))
 				printf("%s: queuing\n", gn->name);
-			Lst_Push(&toBeMade, gn);
+			Array_Push(&toBeMade, gn);
 		}
 	}
+	if (randomize_queue)
+		randomize_garray(&toBeMade);
 }
 
 /*-
@@ -483,8 +516,9 @@ Make_Run(Lst targs)		/* the initial list of targets */
 	unsigned int i;
 	bool cycle;
 
-	Static_Lst_Init(&toBeMade);
 	/* wild guess at initial sizes */
+	Array_Init(&toBeMade, 500);
+	Array_Init(&examine, 150);
 	ohash_init(&targets, 10, &gnode_info);
 	if (DEBUG(PARALLEL))
 		random_setup();
diff --git a/usr.bin/make/make.h b/usr.bin/make/make.h
index 63281c25da3..fb7e8e12718 100644
--- a/usr.bin/make/make.h
+++ b/usr.bin/make/make.h
@@ -2,7 +2,7 @@
 #define _MAKE_H_
 
 /*	$OpenPackages$ */
-/*	$OpenBSD: make.h,v 1.35 2007/11/28 09:40:08 espie Exp $ */
+/*	$OpenBSD: make.h,v 1.36 2007/12/01 15:14:34 espie Exp $ */
 /*	$NetBSD: make.h,v 1.15 1997/03/10 21:20:00 christos Exp $	*/
 
 /*
@@ -44,5 +44,6 @@
 extern void Make_Update(GNode *);
 extern bool Make_Run(Lst);
 extern long random_delay;
+extern bool no_jobs_left(void);
 
 #endif /* _MAKE_H_ */