Module Name: othersrc
Committed By: dholland
Date: Sat Mar 23 21:29:11 UTC 2013
Modified Files:
othersrc/usr.bin/dholland-make2: make.c
Log Message:
Improve the toBeMade logic: collect the non-tail insertions in a
separate array and stuff them into the main queue all at once.
To generate a diff of this commit:
cvs rdiff -u -r1.11 -r1.12 othersrc/usr.bin/dholland-make2/make.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: othersrc/usr.bin/dholland-make2/make.c
diff -u othersrc/usr.bin/dholland-make2/make.c:1.11 othersrc/usr.bin/dholland-make2/make.c:1.12
--- othersrc/usr.bin/dholland-make2/make.c:1.11 Sat Mar 23 21:28:04 2013
+++ othersrc/usr.bin/dholland-make2/make.c Sat Mar 23 21:29:11 2013
@@ -1,4 +1,4 @@
-/* $NetBSD: make.c,v 1.11 2013/03/23 21:28:04 dholland Exp $ */
+/* $NetBSD: make.c,v 1.12 2013/03/23 21:29:11 dholland Exp $ */
/*
* Copyright (c) 1988, 1989, 1990, 1993
@@ -111,12 +111,12 @@
#include "dir.h"
#include "job.h"
-MAKE_RCSID("$NetBSD: make.c,v 1.11 2013/03/23 21:28:04 dholland Exp $");
+MAKE_RCSID("$NetBSD: make.c,v 1.12 2013/03/23 21:29:11 dholland Exp $");
typedef struct {
- GList data;
- Boolean hasmark;
- unsigned markpos;
+ GList nodes;
+ GList insertions;
+ Boolean inserting;
} MakeQ;
static unsigned int checked = 1;/* Sequence # to detect recursion */
@@ -146,54 +146,60 @@ static void MakeBuildParent(GNode *, Boo
static void
MakeQ_Init(MakeQ *q)
{
- glist_init(&q->data);
- q->hasmark = FALSE;
- q->markpos = 0;
+ glist_init(&q->nodes);
+ glist_init(&q->insertions);
+ q->inserting = FALSE;
}
static Boolean
MakeQ_IsEmpty(MakeQ *q)
{
- return glist_num(&q->data) == 0;
+ return glist_num(&q->nodes) == 0 && glist_num(&q->insertions) == 0;
}
static void
MakeQ_AddTail(MakeQ *q, GNode *gn)
{
- if (q->hasmark && q->markpos >= glist_num(&q->data)) {
- q->markpos++;
- }
- glist_add(&q->data, gn, NULL);
+ glist_add(&q->nodes, gn, NULL);
}
static void
-MakeQ_AddBeforeMark(MakeQ *q, GNode *gn)
+MakeQ_Insert(MakeQ *q, GNode *gn)
{
- assert(q->hasmark);
- if (q->markpos >= glist_num(&q->data)) {
- glist_add(&q->data, gn, NULL);
- q->markpos++;
- } else {
- glist_insert(&q->data, q->markpos);
- glist_set(&q->data, q->markpos, gn);
- q->markpos++;
- }
+ assert(q->inserting);
+ glist_add(&q->insertions, gn, NULL);
}
static void
-MakeQ_SetMark(MakeQ *q)
+MakeQ_BeginInsertions(MakeQ *q)
{
- assert(!q->hasmark);
- q->hasmark = TRUE;
- q->markpos = 0;
+ assert(!q->inserting);
+ assert(glist_num(&q->insertions) == 0);
+ q->inserting = TRUE;
}
static void
-MakeQ_ClearMark(MakeQ *q)
+MakeQ_EndInsertions(MakeQ *q)
{
- assert(q->hasmark);
- q->hasmark = FALSE;
- q->markpos = 0;
+ unsigned i, num, ninsertions;
+
+ assert(q->inserting);
+ q->inserting = FALSE;
+
+ /* prepend insertions[] to nodes[] */
+
+ num = glist_num(&q->nodes);
+ ninsertions = glist_num(&q->insertions);
+
+ glist_setsize(&q->nodes, ninsertions + num);
+ /* must run this loop backwards */
+ for (i=num; i-- > 0; ) {
+ glist_set(&q->nodes, ninsertions + i, glist_get(&q->nodes, i));
+ }
+ for (i=0; i<ninsertions; i++) {
+ glist_set(&q->nodes, i, glist_get(&q->insertions, i));
+ }
+ glist_setsize(&q->insertions, 0);
}
static GNode *
@@ -201,11 +207,13 @@ MakeQ_PopHead(MakeQ *q)
{
GNode *ret;
- if (glist_num(&q->data) == 0) {
+ assert(q->inserting == FALSE);
+
+ if (glist_num(&q->nodes) == 0) {
return NULL;
}
- ret = glist_get(&q->data, 0);
- glist_remove(&q->data, 0);
+ ret = glist_get(&q->nodes, 0);
+ glist_remove(&q->nodes, 0);
return ret;
}
@@ -214,9 +222,11 @@ MakeQ_ForEach(MakeQ *q, int (*func)(void
{
unsigned i, num;
- num = glist_num(&q->data);
+ assert(q->inserting == FALSE);
+
+ num = glist_num(&q->nodes);
for (i=0; i<num; i++) {
- func(glist_get(&q->data, i), ptr);
+ func(glist_get(&q->nodes, i), ptr);
}
}
@@ -816,9 +826,9 @@ Make_Update(GNode *cgn)
for (i=0; i<glist_num(¢urion->order_succ); i++) {
succ = glist_get(¢urion->order_succ, i);
- MakeQ_SetMark(&toBeMade);
+ MakeQ_BeginInsertions(&toBeMade);
MakeBuildParent(succ, TRUE);
- MakeQ_ClearMark(&toBeMade);
+ MakeQ_EndInsertions(&toBeMade);
}
}
@@ -1135,7 +1145,7 @@ DoMakeCheckOrder(GList *order_pred)
}
static int
-MakeBuildChild(GNode *cn, Boolean usemark)
+MakeBuildChild(GNode *cn, Boolean doinsert)
{
if (DEBUG(MAKE))
fprintf(debug_file, "MakeBuildChild: inspect %s%s, made %d, type %x\n",
@@ -1155,16 +1165,16 @@ MakeBuildChild(GNode *cn, Boolean usemar
cn->name, cn->cohort_num);
cn->made = REQUESTED;
- if (usemark == FALSE)
- MakeQ_AddTail(&toBeMade, cn);
+ if (doinsert)
+ MakeQ_Insert(&toBeMade, cn);
else
- MakeQ_AddBeforeMark(&toBeMade, cn);
+ MakeQ_AddTail(&toBeMade, cn);
if (cn->unmade_cohorts != 0) {
unsigned i;
for (i=0; i<glist_num(&cn->cohorts); i++) {
- if (MakeBuildChild(glist_get(&cn->cohorts, i), usemark)) {
+ if (MakeBuildChild(glist_get(&cn->cohorts, i), doinsert)) {
break;
}
}
@@ -1179,12 +1189,12 @@ MakeBuildChild(GNode *cn, Boolean usemar
/* When a .ORDER LHS node completes we do this on each RHS */
static void
-MakeBuildParent(GNode *pn, Boolean usemark)
+MakeBuildParent(GNode *pn, Boolean doinsert)
{
if (pn->made != DEFERRED)
return;
- if (MakeBuildChild(pn, usemark) == 0) {
+ if (MakeBuildChild(pn, doinsert) == 0) {
/* Mark so that when this node is built we reschedule its parents */
pn->flags |= DONE_ORDER;
}
@@ -1232,12 +1242,12 @@ MakeStartJobs(void)
*/
gn->made = DEFERRED;
for (i=0; i<glist_num(&gn->children); i++) {
- MakeQ_SetMark(&toBeMade);
+ MakeQ_BeginInsertions(&toBeMade);
if (MakeBuildChild(glist_get(&gn->children, i), TRUE)) {
- MakeQ_ClearMark(&toBeMade);
+ MakeQ_EndInsertions(&toBeMade);
break;
}
- MakeQ_ClearMark(&toBeMade);
+ MakeQ_EndInsertions(&toBeMade);
}
/* and drop this node on the floor */
if (DEBUG(MAKE))
