Module Name: othersrc
Committed By: dholland
Date: Sat Mar 23 21:33:28 UTC 2013
Modified Files:
othersrc/usr.bin/dholland-make2: make.c
Log Message:
Improve the toBeMade queue code so it doesn't do bulk array shifts
every time you remove something from the queue head. If this turns out
not to be good enough it can be tuned and/or made into a circular
queue later.
(Also, in the long run, the non-tail insertions may go away; they seem
to chiefly be associated with the .ORDER implementation and may not be
needed after the primary graph structure gets some strengthening.)
To generate a diff of this commit:
cvs rdiff -u -r1.12 -r1.13 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.12 othersrc/usr.bin/dholland-make2/make.c:1.13
--- othersrc/usr.bin/dholland-make2/make.c:1.12 Sat Mar 23 21:29:11 2013
+++ othersrc/usr.bin/dholland-make2/make.c Sat Mar 23 21:33:28 2013
@@ -1,4 +1,4 @@
-/* $NetBSD: make.c,v 1.12 2013/03/23 21:29:11 dholland Exp $ */
+/* $NetBSD: make.c,v 1.13 2013/03/23 21:33:28 dholland Exp $ */
/*
* Copyright (c) 1988, 1989, 1990, 1993
@@ -111,11 +111,12 @@
#include "dir.h"
#include "job.h"
-MAKE_RCSID("$NetBSD: make.c,v 1.12 2013/03/23 21:29:11 dholland Exp $");
+MAKE_RCSID("$NetBSD: make.c,v 1.13 2013/03/23 21:33:28 dholland Exp $");
typedef struct {
GList nodes;
GList insertions;
+ unsigned firstnode;
Boolean inserting;
} MakeQ;
@@ -148,13 +149,15 @@ MakeQ_Init(MakeQ *q)
{
glist_init(&q->nodes);
glist_init(&q->insertions);
+ q->firstnode = 0;
q->inserting = FALSE;
}
static Boolean
MakeQ_IsEmpty(MakeQ *q)
{
- return glist_num(&q->nodes) == 0 && glist_num(&q->insertions) == 0;
+ assert(q->inserting == FALSE);
+ return glist_num(&q->nodes) == 0;
}
static void
@@ -181,7 +184,8 @@ MakeQ_BeginInsertions(MakeQ *q)
static void
MakeQ_EndInsertions(MakeQ *q)
{
- unsigned i, num, ninsertions;
+ unsigned i, num, ninsertions, growth;
+ GNode *gn;
assert(q->inserting);
q->inserting = FALSE;
@@ -191,13 +195,25 @@ MakeQ_EndInsertions(MakeQ *q)
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));
+ if (ninsertions <= q->firstnode) {
+ /* do not need to move the existing elements */
+ q->firstnode -= ninsertions;
+ } else {
+ /* need to shift the existing elements up */
+
+ growth = ninsertions - q->firstnode;
+ glist_setsize(&q->nodes, growth + num);
+
+ /* ranges may overlap, so run this loop backwards */
+ for (i=num; i-- > 0; ) {
+ gn = glist_get(&q->nodes, q->firstnode + i);
+ glist_set(&q->nodes, ninsertions + i, gn);
+ }
+ q->firstnode = 0;
}
for (i=0; i<ninsertions; i++) {
- glist_set(&q->nodes, i, glist_get(&q->insertions, i));
+ gn = glist_get(&q->insertions, i);
+ glist_set(&q->nodes, q->firstnode + i, gn);
}
glist_setsize(&q->insertions, 0);
}
@@ -205,15 +221,26 @@ MakeQ_EndInsertions(MakeQ *q)
static GNode *
MakeQ_PopHead(MakeQ *q)
{
+ unsigned num;
GNode *ret;
assert(q->inserting == FALSE);
- if (glist_num(&q->nodes) == 0) {
+ num = glist_num(&q->nodes);
+ assert(q->firstnode <= num);
+
+ if (q->firstnode == num) {
+ assert(num == 0);
return NULL;
}
- ret = glist_get(&q->nodes, 0);
- glist_remove(&q->nodes, 0);
+
+ ret = glist_get(&q->nodes, q->firstnode);
+ q->firstnode++;
+ if (q->firstnode == num) {
+ /* we've taken everything out, slide back to the beginning */
+ glist_setsize(&q->nodes, 0);
+ q->firstnode = 0;
+ }
return ret;
}
