Module Name: othersrc Committed By: dholland Date: Mon Mar 4 23:03:42 UTC 2013
Modified Files: othersrc/usr.bin/dholland-make2: arch.c compat.c graph.h job.c make.c parse.c suff.c targ.c Log Message: Use arrays instead of lists for graph links. To generate a diff of this commit: cvs rdiff -u -r1.2 -r1.3 othersrc/usr.bin/dholland-make2/arch.c \ othersrc/usr.bin/dholland-make2/job.c cvs rdiff -u -r1.4 -r1.5 othersrc/usr.bin/dholland-make2/compat.c \ othersrc/usr.bin/dholland-make2/make.c \ othersrc/usr.bin/dholland-make2/suff.c \ othersrc/usr.bin/dholland-make2/targ.c cvs rdiff -u -r1.3 -r1.4 othersrc/usr.bin/dholland-make2/graph.h \ othersrc/usr.bin/dholland-make2/parse.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/arch.c diff -u othersrc/usr.bin/dholland-make2/arch.c:1.2 othersrc/usr.bin/dholland-make2/arch.c:1.3 --- othersrc/usr.bin/dholland-make2/arch.c:1.2 Mon Feb 25 03:39:28 2013 +++ othersrc/usr.bin/dholland-make2/arch.c Mon Mar 4 23:03:41 2013 @@ -1,4 +1,4 @@ -/* $NetBSD: arch.c,v 1.2 2013/02/25 03:39:28 dholland Exp $ */ +/* $NetBSD: arch.c,v 1.3 2013/03/04 23:03:41 dholland Exp $ */ /* * Copyright (c) 1988, 1989, 1990, 1993 @@ -137,7 +137,7 @@ #include "dir.h" #include "config.h" -MAKE_RCSID("$NetBSD: arch.c,v 1.2 2013/02/25 03:39:28 dholland Exp $"); +MAKE_RCSID("$NetBSD: arch.c,v 1.3 2013/03/04 23:03:41 dholland Exp $"); #ifdef TARGET_MACHINE @@ -1105,17 +1105,16 @@ Arch_MTime(GNode *gn) time_t Arch_MemMTime(GNode *gn) { - LstNode ln; GNode *pgn; char *nameStart, *nameEnd; + unsigned i; - if (Lst_Open(gn->parents) != SUCCESS) { - gn->mtime = 0; - return (0); - } - while ((ln = Lst_Next(gn->parents)) != NULL) { - pgn = (GNode *)Lst_Datum(ln); + /* by default, in case parents[] is empty (I think) */ + gn->mtime = 0; + + for (i=0; i<glist_num(&gn->parents); i++) { + pgn = glist_get(&gn->parents, i); if (pgn->type & OP_ARCHV) { /* @@ -1142,8 +1141,6 @@ Arch_MemMTime(GNode *gn) } } - Lst_Close(gn->parents); - return (gn->mtime); } @@ -1237,9 +1234,9 @@ Arch_LibOODate(GNode *gn) if (gn->type & OP_PHONY) { oodate = TRUE; - } else if (OP_NOP(gn->type) && Lst_IsEmpty(gn->children)) { + } else if (OP_NOP(gn->type) && glist_num(&gn->children) == 0) { oodate = FALSE; - } else if ((!Lst_IsEmpty(gn->children) && gn->cmgn == NULL) || + } else if ((glist_num(&gn->children) > 0 && gn->cmgn == NULL) || (gn->mtime > now) || (gn->cmgn != NULL && gn->mtime < gn->cmgn->mtime)) { oodate = TRUE; Index: othersrc/usr.bin/dholland-make2/job.c diff -u othersrc/usr.bin/dholland-make2/job.c:1.2 othersrc/usr.bin/dholland-make2/job.c:1.3 --- othersrc/usr.bin/dholland-make2/job.c:1.2 Mon Feb 25 03:39:28 2013 +++ othersrc/usr.bin/dholland-make2/job.c Mon Mar 4 23:03:42 2013 @@ -1,4 +1,4 @@ -/* $NetBSD: job.c,v 1.2 2013/02/25 03:39:28 dholland Exp $ */ +/* $NetBSD: job.c,v 1.3 2013/03/04 23:03:42 dholland Exp $ */ /* * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. @@ -149,7 +149,7 @@ #include "trace.h" # define STATIC static -MAKE_RCSID("$NetBSD: job.c,v 1.2 2013/02/25 03:39:28 dholland Exp $"); +MAKE_RCSID("$NetBSD: job.c,v 1.3 2013/03/04 23:03:42 dholland Exp $"); /* * error handling variables @@ -1193,7 +1193,7 @@ Boolean Job_CheckCommands(GNode *gn, void (*abortProc)(const char *, ...)) { if (OP_NOP(gn->type) && Lst_IsEmpty(gn->commands) && - ((gn->type & OP_LIB) == 0 || Lst_IsEmpty(gn->children))) { + ((gn->type & OP_LIB) == 0 || glist_num(&gn->children) == 0)) { /* * No commands. Look for .DEFAULT rule from which we might infer * commands @@ -2585,7 +2585,7 @@ Job_Finish(void) { if (postCommands != NULL && (!Lst_IsEmpty(postCommands->commands) || - !Lst_IsEmpty(postCommands->children))) { + glist_num(&postCommands->children) > 0)) { if (errors) { Error("Errors reported so .END ignored"); } else { Index: othersrc/usr.bin/dholland-make2/compat.c diff -u othersrc/usr.bin/dholland-make2/compat.c:1.4 othersrc/usr.bin/dholland-make2/compat.c:1.5 --- othersrc/usr.bin/dholland-make2/compat.c:1.4 Mon Mar 4 08:47:08 2013 +++ othersrc/usr.bin/dholland-make2/compat.c Mon Mar 4 23:03:41 2013 @@ -1,4 +1,4 @@ -/* $NetBSD: compat.c,v 1.4 2013/03/04 08:47:08 dholland Exp $ */ +/* $NetBSD: compat.c,v 1.5 2013/03/04 23:03:41 dholland Exp $ */ /* * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. @@ -101,7 +101,7 @@ #include "job.h" #include "pathnames.h" -MAKE_RCSID("$NetBSD: compat.c,v 1.4 2013/03/04 08:47:08 dholland Exp $"); +MAKE_RCSID("$NetBSD: compat.c,v 1.5 2013/03/04 23:03:41 dholland Exp $"); /* * The following array is used to make a fast determination of which @@ -512,7 +512,13 @@ Compat_Make(void *gnp, void *pgnp) gn->made = BEINGMADE; if ((gn->type & OP_MADE) == 0) Suff_FindDeps(gn); - Lst_ForEach(gn->children, Compat_Make, gn); + { + unsigned i; + + for (i=0; i<glist_num(&gn->children); i++) { + Compat_Make(glist_get(&gn->children, i), gn); + } + } if ((gn->flags & REMAKE) == 0) { gn->made = ABORTED; pgn->flags &= ~REMAKE; Index: othersrc/usr.bin/dholland-make2/make.c diff -u othersrc/usr.bin/dholland-make2/make.c:1.4 othersrc/usr.bin/dholland-make2/make.c:1.5 --- othersrc/usr.bin/dholland-make2/make.c:1.4 Mon Mar 4 08:47:08 2013 +++ othersrc/usr.bin/dholland-make2/make.c Mon Mar 4 23:03:42 2013 @@ -1,4 +1,4 @@ -/* $NetBSD: make.c,v 1.4 2013/03/04 08:47:08 dholland Exp $ */ +/* $NetBSD: make.c,v 1.5 2013/03/04 23:03:42 dholland Exp $ */ /* * Copyright (c) 1988, 1989, 1990, 1993 @@ -111,7 +111,7 @@ #include "dir.h" #include "job.h" -MAKE_RCSID("$NetBSD: make.c,v 1.4 2013/03/04 08:47:08 dholland Exp $"); +MAKE_RCSID("$NetBSD: make.c,v 1.5 2013/03/04 23:03:42 dholland Exp $"); static unsigned int checked = 1;/* Sequence # to detect recursion */ static Lst toBeMade; /* The current fringe of the graph. These @@ -129,6 +129,7 @@ static int MakeHandleUse(void *, void *) static Boolean MakeStartJobs(void); static int MakePrintStatus(void *, void *); static int MakeCheckOrder(void *, void *); +static int DoMakeCheckOrder(GList *); static int MakeBuildChild(void *, void *); static int MakeBuildParent(void *, void *); @@ -338,7 +339,11 @@ Make_OODate(GNode *gn) * thinking they're out-of-date. */ if (!oodate) { - Lst_ForEach(gn->parents, MakeTimeStamp, gn); + unsigned i; + + for (i=0; i<glist_num(&gn->parents); i++) { + MakeTimeStamp(glist_get(&gn->parents, i), gn); + } } return (oodate); @@ -454,7 +459,6 @@ MakeFindChild(void *gnp, void *pgnp) void Make_HandleUse(GNode *cgn, GNode *pgn) { - LstNode ln; /* An element in the children list */ #ifdef DEBUG_SRC if ((cgn->type & (OP_USE|OP_USEBEFORE|OP_TRANSFORM)) == 0) { @@ -482,9 +486,12 @@ Make_HandleUse(GNode *cgn, GNode *pgn) } } - if (Lst_Open(cgn->children) == SUCCESS) { - while ((ln = Lst_Next(cgn->children)) != NULL) { - GNode *tgn, *gn = (GNode *)Lst_Datum(ln); + { + unsigned i; + GNode *tgn, *gn; + + for (i=0; i<glist_num(&cgn->children); i++) { + gn = glist_get(&cgn->children, i); /* * Expand variables in the .USE node's name @@ -506,11 +513,10 @@ Make_HandleUse(GNode *cgn, GNode *pgn) gn = tgn; } - (void)Lst_AtEnd(pgn->children, gn); - (void)Lst_AtEnd(gn->parents, pgn); + glist_add(&pgn->children, gn, NULL); + glist_add(&gn->parents, pgn, NULL); pgn->unmade += 1; } - Lst_Close(cgn->children); } pgn->type |= cgn->type & ~(OP_OPMASK|OP_USE|OP_USEBEFORE|OP_TRANSFORM); @@ -542,7 +548,6 @@ MakeHandleUse(void *cgnp, void *pgnp) { GNode *cgn = (GNode *)cgnp; GNode *pgn = (GNode *)pgnp; - LstNode ln; /* An element in the children list */ int unmarked; unmarked = ((cgn->type & OP_MARK) == 0); @@ -561,8 +566,8 @@ MakeHandleUse(void *cgnp, void *pgnp) * children the parent has. This is used by Make_Run to decide * whether to queue the parent or examine its children... */ - if ((ln = Lst_Member(pgn->children, cgn)) != NULL) { - Lst_Remove(pgn->children, ln); + if (glist_contains(&pgn->children, cgn)) { + glist_removeval(&pgn->children, cgn); pgn->unmade--; } return (0); @@ -695,10 +700,9 @@ Make_Update(GNode *cgn) { GNode *pgn; /* the parent node */ char *cname; /* the child's name */ - LstNode ln; /* Element in parents and iParents lists */ time_t mtime = -1; char *p1; - Lst parents; + GList *parents; GNode *centurion; /* It is save to re-examine any nodes again */ @@ -725,7 +729,7 @@ Make_Update(GNode *cgn) * which is where all parents are linked. */ if ((centurion = cgn->centurion) != NULL) { - if (!Lst_IsEmpty(cgn->parents)) + if (glist_num(&cgn->parents) > 0) Punt("%s%s: cohort has parents", cgn->name, cgn->cohort_num); centurion->unmade_cohorts -= 1; if (centurion->unmade_cohorts < 0) @@ -733,15 +737,27 @@ Make_Update(GNode *cgn) } else { centurion = cgn; } - parents = centurion->parents; + parents = ¢urion->parents; /* If this was a .ORDER node, schedule the RHS */ - Lst_ForEach(centurion->order_succ, MakeBuildParent, Lst_First(toBeMade)); + { + unsigned i; + GNode *succ; + + for (i=0; i<glist_num(¢urion->order_succ); i++) { + succ = glist_get(¢urion->order_succ, i); + if (MakeBuildParent(succ, Lst_First(toBeMade))) { + break; + } + } + } /* Now mark all the parents as having one less unmade child */ - if (Lst_Open(parents) == SUCCESS) { - while ((ln = Lst_Next(parents)) != NULL) { - pgn = (GNode *)Lst_Datum(ln); + { + unsigned i; + + for (i=0; i<glist_num(parents); i++) { + pgn = glist_get(parents, i); if (DEBUG(MAKE)) fprintf(debug_file, "inspect parent %s%s: flags %x, " "type %x, made %d, unmade %d ", @@ -817,8 +833,7 @@ Make_Update(GNode *cgn) fprintf(debug_file, "- not deferred\n"); continue; } - if (pgn->order_pred - && Lst_ForEach(pgn->order_pred, MakeCheckOrder, 0)) { + if (DoMakeCheckOrder(&pgn->order_pred)) { /* A .ORDER rule stops us building this */ continue; } @@ -833,7 +848,6 @@ Make_Update(GNode *cgn) pgn->made = REQUESTED; (void)Lst_EnQueue(toBeMade, pgn); } - Lst_Close(parents); } /* @@ -979,11 +993,22 @@ MakeAddAllSrc(void *cgnp, void *pgnp) void Make_DoAllVar(GNode *gn) { + unsigned i; + if (gn->flags & DONE_ALLSRC) return; - - Lst_ForEach(gn->children, MakeUnmark, gn); - Lst_ForEach(gn->children, MakeAddAllSrc, gn); + + for (i=0; i<glist_num(&gn->children); i++) { + if (MakeUnmark(glist_get(&gn->children, i), gn)) { + break; + } + } + /* XXX: does this need to be a separate loop? */ + for (i=0; i<glist_num(&gn->children); i++) { + if (MakeAddAllSrc(glist_get(&gn->children, i), gn)) { + break; + } + } if (!Var_Exists (OODATE, gn)) { Var_Set(OODATE, "", gn, 0); @@ -1032,6 +1057,27 @@ MakeCheckOrder(void *v_bn, void *ignore } static int +DoMakeCheckOrder(GList *order_pred) +{ + unsigned i, n; + + /* + * With the list library, where order_pred is a Lst: + * return order_pred && Lst_ForEach(order_pred, MakeCheckOrder, 0) + */ + n = glist_num(order_pred); + if (n == 0) { + return 0; + } + for (i=0; i<n; i++) { + if (MakeCheckOrder(glist_get(order_pred, i), 0)) { + return 1; + } + } + return 0; +} + +static int MakeBuildChild(void *v_cn, void *toBeMade_next) { GNode *cn = v_cn; @@ -1043,7 +1089,7 @@ MakeBuildChild(void *v_cn, void *toBeMad return 0; /* If this node is on the RHS of a .ORDER, check LHSs. */ - if (cn->order_pred && Lst_ForEach(cn->order_pred, MakeCheckOrder, 0)) { + if (DoMakeCheckOrder(&cn->order_pred)) { /* Can't build this (or anything else in this child list) yet */ cn->made = DEFERRED; return 0; /* but keep looking */ @@ -1098,6 +1144,7 @@ MakeStartJobs(void) { GNode *gn; int have_token = 0; + unsigned i; while (!Lst_IsEmpty (toBeMade)) { /* Get token now to avoid cycling job-list when we only have 1 token */ @@ -1133,7 +1180,11 @@ MakeStartJobs(void) * just before the current first element. */ gn->made = DEFERRED; - Lst_ForEach(gn->children, MakeBuildChild, Lst_First(toBeMade)); + for (i=0; i<glist_num(&gn->children); i++) { + if (MakeBuildChild(glist_get(&gn->children, i), Lst_First(toBeMade))) { + break; + } + } /* and drop this node on the floor */ if (DEBUG(MAKE)) fprintf(debug_file, "dropped %s%s\n", gn->name, gn->cohort_num); @@ -1223,6 +1274,7 @@ MakePrintStatus(void *gnp, void *v_error { GNode *gn = (GNode *)gnp; int *errors = v_errors; + unsigned i; if (gn->flags & DONECYCLE) /* We've completely processed this node before, don't do it again. */ @@ -1248,7 +1300,9 @@ MakePrintStatus(void *gnp, void *v_error "`%s%s' was not built (made %d, flags %x, type %x)!\n", gn->name, gn->cohort_num, gn->made, gn->flags, gn->type); /* Most likely problem is actually caused by .ORDER */ - Lst_ForEach(gn->order_pred, MakePrintStatusOrder, gn); + for (i=0; i<glist_num(&gn->order_pred); i++) { + MakePrintStatusOrder(glist_get(&gn->order_pred, i), gn); + } break; default: /* Errors - already counted */ @@ -1272,7 +1326,11 @@ MakePrintStatus(void *gnp, void *v_error if (!(gn->flags & CYCLE)) { /* Fist time we've seen this node, check all children */ gn->flags |= CYCLE; - Lst_ForEach(gn->children, MakePrintStatus, errors); + for (i=0; i<glist_num(&gn->children); i++) { + if (MakePrintStatus(glist_get(&gn->children, i), errors)) { + break; + } + } /* Mark that this node needn't be processed again */ gn->flags |= DONECYCLE; return 0; @@ -1286,7 +1344,12 @@ MakePrintStatus(void *gnp, void *v_error return 1; /* Reporting for our children will give the rest of the loop */ - Lst_ForEach(gn->children, MakePrintStatus, errors); + for (i=0; i<glist_num(&gn->children); i++) { + if (MakePrintStatus(glist_get(&gn->children, i), errors)) { + /* XXX: should this be break or return 1? */ + break; + } + } return 0; } @@ -1307,6 +1370,7 @@ Make_ExpandUse(Lst targs) { GNode *gn; /* a temporary pointer */ GList examine; /* List of targets to examine */ + unsigned i; glist_init(&examine); Lst_IntoArray(targs, &examine.arr); /* XXX not typesafe */ @@ -1341,8 +1405,6 @@ Make_ExpandUse(Lst targs) * XXX: this is a silly way of doing things when examine is * an array. */ - unsigned i; - for (i=glist_num(&gn->cohorts); i-- > 0; ) { glist_insert(&examine, 0); glist_set(&examine, 0, glist_get(&gn->cohorts, i)); @@ -1371,21 +1433,31 @@ Make_ExpandUse(Lst targs) (void)Dir_MTime(gn, 0); Var_Set(TARGET, gn->path ? gn->path : gn->name, gn, 0); - Lst_ForEach(gn->children, MakeUnmark, gn); - Lst_ForEach(gn->children, MakeHandleUse, gn); + for (i=0; i<glist_num(&gn->children); i++) { + MakeUnmark(glist_get(&gn->children, i), gn); + } + /* XXX: does this need to be a separate loop? */ + for (i=0; i<glist_num(&gn->children); i++) { + MakeHandleUse(glist_get(&gn->children, i), gn); + } if ((gn->type & OP_MADE) == 0) Suff_FindDeps(gn); else { /* Pretend we made all this node's children */ - Lst_ForEach(gn->children, MakeFindChild, gn); + for (i=0; i<glist_num(&gn->children); i++) { + MakeFindChild(glist_get(&gn->children, i), gn); + } if (gn->unmade != 0) printf("Warning: %s%s still has %d unmade children\n", gn->name, gn->cohort_num, gn->unmade); } - if (gn->unmade != 0) - Lst_ForEach(gn->children, MakeAddChild2, &examine); + if (gn->unmade != 0) { + for (i=0; i<glist_num(&gn->children); i++) { + MakeAddChild2(glist_get(&gn->children, i), &examine); + } + } } glist_setsize(&examine, 0); @@ -1409,8 +1481,8 @@ link_parent(void *cnp, void *pnp) GNode *cn = cnp; GNode *pn = pnp; - Lst_AtEnd(pn->children, cn); - Lst_AtEnd(cn->parents, pn); + glist_add(&pn->children, cn, NULL); + glist_add(&cn->parents, pn, NULL); pn->unmade++; return 0; } @@ -1432,9 +1504,9 @@ add_wait_dep(void *v_cn, void *v_wn) fprintf(debug_file, ".WAIT: add dependency %s%s -> %s\n", cn->name, cn->cohort_num, wn->name); - Lst_AtEnd(wn->children, cn); + glist_add(&wn->children, cn, NULL); + glist_add(&cn->parents, wn, NULL); wn->unmade++; - Lst_AtEnd(cn->parents, wn); return 0; } @@ -1443,9 +1515,8 @@ Make_ProcessWait(Lst targs) { GNode *pgn; /* 'parent' node we are examining */ GNode *cgn; /* Each child in turn */ - LstNode owln; /* Previous .WAIT node */ GList examine; /* List of targets to examine */ - LstNode ln; + unsigned start, i, j; /* * We need all the nodes to have a common parent in order for the @@ -1496,19 +1567,21 @@ Make_ProcessWait(Lst targs) } } - owln = Lst_First(pgn->children); - Lst_Open(pgn->children); - for (; (ln = Lst_Next(pgn->children)) != NULL; ) { - cgn = Lst_Datum(ln); + start = 0; + for (i=0; i<glist_num(&pgn->children); i++) { + cgn = glist_get(&pgn->children, i); if (cgn->type & OP_WAIT) { /* Make the .WAIT node depend on the previous children */ - Lst_ForEachFrom(pgn->children, owln, add_wait_dep, cgn); - owln = ln; + for (j=start; j<glist_num(&pgn->children); j++) { + if (add_wait_dep(glist_get(&pgn->children, j), cgn)) { + break; + } + } + start = i; } else { glist_add(&examine, cgn, NULL); } } - Lst_Close(pgn->children); } glist_setsize(&examine, 0); Index: othersrc/usr.bin/dholland-make2/suff.c diff -u othersrc/usr.bin/dholland-make2/suff.c:1.4 othersrc/usr.bin/dholland-make2/suff.c:1.5 --- othersrc/usr.bin/dholland-make2/suff.c:1.4 Mon Mar 4 08:47:08 2013 +++ othersrc/usr.bin/dholland-make2/suff.c Mon Mar 4 23:03:42 2013 @@ -1,4 +1,4 @@ -/* $NetBSD: suff.c,v 1.4 2013/03/04 08:47:08 dholland Exp $ */ +/* $NetBSD: suff.c,v 1.5 2013/03/04 23:03:42 dholland Exp $ */ /* * Copyright (c) 1988, 1989, 1990, 1993 @@ -131,7 +131,7 @@ #include "hash.h" #include "dir.h" -MAKE_RCSID("$NetBSD: suff.c,v 1.4 2013/03/04 08:47:08 dholland Exp $"); +MAKE_RCSID("$NetBSD: suff.c,v 1.5 2013/03/04 23:03:42 dholland Exp $"); static Lst sufflist; /* Lst of suffixes */ #ifdef CLEANUP @@ -223,8 +223,8 @@ static int SuffRemoveSrc(Lst); static void SuffAddLevel(Lst, Src *); static Src *SuffFindThem(Lst, Lst); static Src *SuffFindCmds(Src *, Lst); -static void SuffExpandChildren(LstNode, GNode *); -static void SuffExpandWildcards(LstNode, GNode *); +static unsigned SuffExpandChildren(GNode *, unsigned, GNode *); +static unsigned SuffExpandWildcards(GNode *, unsigned, GNode *); static Boolean SuffApplyTransform(GNode *, GNode *, Suff *, Suff *); static void SuffFindDeps(GNode *, Lst); static void SuffFindArchiveDeps(GNode *, Lst); @@ -698,9 +698,8 @@ Suff_AddTransform(char *line) */ gn = (GNode *)Lst_Datum(ln); Lst_Destroy(gn->commands, NULL); - Lst_Destroy(gn->children, NULL); gn->commands = Lst_Init(FALSE); - gn->children = Lst_Init(FALSE); + glist_setsize(&gn->children, 0); } gn->type = OP_TRANSFORM; @@ -750,7 +749,7 @@ Suff_EndTransform(void *gnp, void *dummy gn = glist_get(&gn->cohorts, glist_num(&gn->cohorts) - 1); } if ((gn->type & OP_TRANSFORM) && Lst_IsEmpty(gn->commands) && - Lst_IsEmpty(gn->children)) + glist_num(&gn->children) == 0) { Suff *s, *t; @@ -916,8 +915,7 @@ SuffScanTargets(void *targetp, void *gsp *gs->gn = NULL; Targ_SetMain(NULL); } - Lst_Destroy(target->children, NULL); - target->children = Lst_Init(FALSE); + glist_setsize(&target->children, 0); target->type = OP_TRANSFORM; /* * link the two together in the proper relationship and order @@ -1403,25 +1401,25 @@ SuffFindThem(Lst srcs, Lst slst) static Src * SuffFindCmds(Src *targ, Lst slst) { - LstNode ln; /* General-purpose list node */ + LstNode ln; /* General-purpose list node */ GNode *t, /* Target GNode */ *s; /* Source GNode */ int prefLen;/* The length of the defined prefix */ Suff *suff; /* Suffix on matching beastie */ Src *ret; /* Return value */ char *cp; + unsigned i; t = targ->node; - (void)Lst_Open(t->children); prefLen = strlen(targ->pref); + i = 0; for (;;) { - ln = Lst_Next(t->children); - if (ln == NULL) { - Lst_Close(t->children); + if (i >= glist_num(&t->children)) { return NULL; } - s = (GNode *)Lst_Datum(ln); + s = glist_get(&t->children, i); + i++; if (s->type & OP_OPTIONAL && Lst_IsEmpty(t->commands)) { /* @@ -1495,33 +1493,48 @@ SuffFindCmds(Src *targ, Lst slst) * variable invocations or file wildcards into actual targets. * * Input: - * cln Child to examine + * cgn Child to examine + * cindex Index of child in parent's children array * pgn Parent node being processed * * Results: - * === 0 (continue) + * Value for cindex + 1, taking insertions into account. + * + * Because this function removes cgn, the increment of cindex is + * built into it in case cindex is 0; that avoids generating + * negative offsets and potentially tripping on them. + * + * This code demonstrates the intended invariant: + * node = pgn->children[cindex]; + * nextnode = pgn->children[cindex + 1]; + * cindex = SuffExpandChildren(node, cindex, parent); + * assert(pgn->children[cindex] == nextnode); * * Side Effects: * The expanded node is removed from the parent's list of children, * and the parent's unmade counter is decremented, but other nodes * may be added. * + * XXX this should be rewritten to shift from one array to another + * instead of juggling a single array. + * *----------------------------------------------------------------------- */ -static void -SuffExpandChildren(LstNode cln, GNode *pgn) +static unsigned +SuffExpandChildren(GNode *cgn, unsigned cindex, GNode *pgn) { - GNode *cgn = (GNode *)Lst_Datum(cln); GNode *gn; /* New source 8) */ char *cp; /* Expanded value */ - if (!Lst_IsEmpty(cgn->order_pred) || !Lst_IsEmpty(cgn->order_succ)) + assert(glist_get(&pgn->children, cindex) == cgn); + + if (glist_num(&cgn->order_pred) > 0 || glist_num(&cgn->order_succ) > 0) /* It is all too hard to process the result of .ORDER */ - return; + return cindex + 1; if (cgn->type & OP_WAIT) /* Ignore these (& OP_PHONY ?) */ - return; + return cindex + 1; /* * First do variable expansion -- this takes precedence over @@ -1530,8 +1543,7 @@ SuffExpandChildren(LstNode cln, GNode *p * the children list. */ if (strchr(cgn->name, '$') == NULL) { - SuffExpandWildcards(cln, pgn); - return; + return SuffExpandWildcards(cgn, cindex, pgn); } if (DEBUG(SUFF)) { @@ -1628,12 +1640,18 @@ SuffExpandChildren(LstNode cln, GNode *p if (DEBUG(SUFF)) { fprintf(debug_file, "%s...", gn->name); } + /* Add gn to the parents child list before the original child */ - (void)Lst_InsertBefore(pgn->children, cln, gn); - (void)Lst_AtEnd(gn->parents, pgn); + glist_insert(&pgn->children, cindex); + glist_set(&pgn->children, cindex, gn); + cindex++; + + glist_add(&gn->parents, pgn, NULL); pgn->unmade++; + /* Expand wildcards on new node */ - SuffExpandWildcards(Lst_Prev(cln), pgn); + cindex = SuffExpandWildcards(gn, cindex - 1, pgn); + assert(glist_get(&pgn->children, cindex) == cgn); } Lst_Destroy(members, NULL); @@ -1646,25 +1664,34 @@ SuffExpandChildren(LstNode cln, GNode *p fprintf(debug_file, "\n"); } + assert(glist_get(&pgn->children, cindex) == cgn); + /* * Now the source is expanded, remove it from the list of children to * keep it from being processed. */ pgn->unmade--; - Lst_Remove(pgn->children, cln); - Lst_Remove(cgn->parents, Lst_Member(cgn->parents, pgn)); + glist_remove(&pgn->children, cindex); + glist_removeval(&cgn->parents, pgn); + + /* + * We return the index of the *next* element in the children + * array, which is now cindex. + */ + return cindex; } -static void -SuffExpandWildcards(LstNode cln, GNode *pgn) +static unsigned +SuffExpandWildcards(GNode *cgn, unsigned cindex, GNode *pgn) { - GNode *cgn = (GNode *)Lst_Datum(cln); GNode *gn; /* New source 8) */ char *cp; /* Expanded value */ Lst explist; /* List of expansions */ + assert(glist_get(&pgn->children, cindex) == cgn); + if (!Dir_HasWildcards(cgn->name)) - return; + return cindex + 1; /* * Expand the word along the chosen path @@ -1684,8 +1711,11 @@ SuffExpandWildcards(LstNode cln, GNode * gn = Targ_FindNode(cp, TARG_CREATE); /* Add gn to the parents child list before the original child */ - (void)Lst_InsertBefore(pgn->children, cln, gn); - (void)Lst_AtEnd(gn->parents, pgn); + glist_insert(&pgn->children, cindex); + glist_set(&pgn->children, cindex, gn); + cindex++; + + glist_add(&gn->parents, pgn, NULL); pgn->unmade++; } @@ -1698,13 +1728,21 @@ SuffExpandWildcards(LstNode cln, GNode * fprintf(debug_file, "\n"); } + assert(glist_get(&pgn->children, cindex) == cgn); + /* * Now the source is expanded, remove it from the list of children to * keep it from being processed. */ pgn->unmade--; - Lst_Remove(pgn->children, cln); - Lst_Remove(cgn->parents, Lst_Member(cgn->parents, pgn)); + glist_remove(&pgn->children, cindex); + glist_removeval(&cgn->parents, pgn); + + /* + * We return the index of the *next* element in the children + * array, which is now cindex. + */ + return cindex; } /*- @@ -1787,15 +1825,16 @@ Suff_FindPath(GNode* gn) static Boolean SuffApplyTransform(GNode *tGn, GNode *sGn, Suff *t, Suff *s) { - LstNode ln, nln; /* General node */ + LstNode ln; /* General node */ char *tname; /* Name of transformation rule */ GNode *gn; /* Node for same */ + unsigned pos, i; /* * Form the proper links between the target and source. */ - (void)Lst_AtEnd(tGn->children, sGn); - (void)Lst_AtEnd(sGn->parents, tGn); + glist_add(&tGn->children, sGn, NULL); + glist_add(&sGn->parents, tGn, NULL); tGn->unmade += 1; /* @@ -1823,7 +1862,7 @@ SuffApplyTransform(GNode *tGn, GNode *sG /* * Record last child for expansion purposes */ - ln = Lst_Last(tGn->children); + pos = glist_num(&tGn->children); /* * Pass the buck to Make_HandleUse to apply the rule @@ -1833,9 +1872,12 @@ SuffApplyTransform(GNode *tGn, GNode *sG /* * Deal with wildcards and variables in any acquired sources */ - for (ln = Lst_Succ(ln); ln != NULL; ln = nln) { - nln = Lst_Succ(ln); - SuffExpandChildren(ln, tGn); + for (i=pos; i<glist_num(&tGn->children); ) { + GNode *child; + + child = glist_get(&tGn->children, i); + i = SuffExpandChildren(child, i, tGn); + /* SuffExpandChildren subsumes the i++ */ } /* @@ -1904,8 +1946,8 @@ SuffFindArchiveDeps(GNode *gn, Lst slst) /* * Create the link between the two nodes right off */ - (void)Lst_AtEnd(gn->children, mem); - (void)Lst_AtEnd(mem->parents, gn); + glist_add(&gn->children, mem, NULL); + glist_add(&mem->parents, gn, NULL); gn->unmade += 1; /* @@ -2010,7 +2052,7 @@ SuffFindNormalDeps(GNode *gn, Lst slst) { char *eoname; /* End of name */ char *sopref; /* Start of prefix */ - LstNode ln, nln; /* Next suffix node to check */ + LstNode ln; /* Next suffix node to check */ Lst srcs; /* List of sources at which to look */ Lst targs; /* List of targets to which things can be * transformed. They all have the same file, @@ -2175,9 +2217,15 @@ SuffFindNormalDeps(GNode *gn, Lst slst) * Now we've got the important local variables set, expand any sources * that still contain variables or wildcards in their names. */ - for (ln = Lst_First(gn->children); ln != NULL; ln = nln) { - nln = Lst_Succ(ln); - SuffExpandChildren(ln, gn); + { + unsigned i; + GNode *child; + + for (i=0; i<glist_num(&gn->children); ) { + child = glist_get(&gn->children, i); + i = SuffExpandChildren(child, i, gn); + /* SuffExpandChildren subsumes the i++ */ + } } if (targ == NULL) { @@ -2258,7 +2306,7 @@ sfnd_abort: /* * Check for overriding transformation rule implied by sources */ - if (!Lst_IsEmpty(gn->children)) { + if (glist_num(&gn->children) > 0) { src = SuffFindCmds(targ, slst); if (src != NULL) { Index: othersrc/usr.bin/dholland-make2/targ.c diff -u othersrc/usr.bin/dholland-make2/targ.c:1.4 othersrc/usr.bin/dholland-make2/targ.c:1.5 --- othersrc/usr.bin/dholland-make2/targ.c:1.4 Mon Mar 4 08:47:08 2013 +++ othersrc/usr.bin/dholland-make2/targ.c Mon Mar 4 23:03:42 2013 @@ -1,4 +1,4 @@ -/* $NetBSD: targ.c,v 1.4 2013/03/04 08:47:08 dholland Exp $ */ +/* $NetBSD: targ.c,v 1.5 2013/03/04 23:03:42 dholland Exp $ */ /* * Copyright (c) 1988, 1989, 1990, 1993 @@ -127,7 +127,7 @@ #include "hash.h" #include "dir.h" -MAKE_RCSID("$NetBSD: targ.c,v 1.4 2013/03/04 08:47:08 dholland Exp $"); +MAKE_RCSID("$NetBSD: targ.c,v 1.5 2013/03/04 23:03:42 dholland Exp $"); static Lst allTargets; /* the list of all targets found so far */ #ifdef CLEANUP @@ -246,10 +246,10 @@ Targ_NewGN(const char *name) gn->cmgn = NULL; glist_init(&gn->iParents); glist_init(&gn->cohorts); - gn->parents = Lst_Init(FALSE); - gn->children = Lst_Init(FALSE); - gn->order_pred = Lst_Init(FALSE); - gn->order_succ = Lst_Init(FALSE); + glist_init(&gn->parents); + glist_init(&gn->children); + glist_init(&gn->order_pred); + glist_init(&gn->order_succ); Hash_InitTable(&gn->context, 0); gn->commands = Lst_Init(FALSE); gn->suffix = NULL; @@ -295,10 +295,14 @@ TargFreeGN(void *gnp) glist_cleanup(&gn->iParents); glist_setsize(&gn->cohorts, 0); glist_cleanup(&gn->cohorts); - Lst_Destroy(gn->parents, NULL); - Lst_Destroy(gn->children, NULL); - Lst_Destroy(gn->order_succ, NULL); - Lst_Destroy(gn->order_pred, NULL); + glist_setsize(&gn->parents, 0); + glist_cleanup(&gn->parents); + glist_setsize(&gn->children, 0); + glist_cleanup(&gn->children); + glist_setsize(&gn->order_pred, 0); + glist_cleanup(&gn->order_pred); + glist_setsize(&gn->order_succ, 0); + glist_cleanup(&gn->order_succ); Hash_DeleteTable(&gn->context); Lst_Destroy(gn->commands, NULL); free(gn); @@ -665,19 +669,31 @@ Targ_PrintNode(void *gnp, void *passp) if (gn->unmade) fprintf(debug_file, "# %d unmade children\n", gn->unmade); } - if (!Lst_IsEmpty (gn->parents)) { + if (glist_num(&gn->parents) > 0) { + unsigned i; + fprintf(debug_file, "# parents: "); - Lst_ForEach(gn->parents, TargPrintName, NULL); + for (i=0; i<glist_num(&gn->parents); i++) { + TargPrintName(glist_get(&gn->parents, i), NULL); + } fprintf(debug_file, "\n"); } - if (!Lst_IsEmpty (gn->order_pred)) { + if (glist_num(&gn->order_pred) > 0) { + unsigned i; + fprintf(debug_file, "# order_pred: "); - Lst_ForEach(gn->order_pred, TargPrintName, NULL); + for (i=0; i<glist_num(&gn->order_pred); i++) { + TargPrintName(glist_get(&gn->order_pred, i), NULL); + } fprintf(debug_file, "\n"); } - if (!Lst_IsEmpty (gn->order_succ)) { + if (glist_num(&gn->order_succ) > 0) { + unsigned i; + fprintf(debug_file, "# order_succ: "); - Lst_ForEach(gn->order_succ, TargPrintName, NULL); + for (i=0; i<glist_num(&gn->order_succ); i++) { + TargPrintName(glist_get(&gn->order_succ, i), NULL); + } fprintf(debug_file, "\n"); } @@ -691,7 +707,13 @@ Targ_PrintNode(void *gnp, void *passp) fprintf(debug_file, ":: "); break; } Targ_PrintType(gn->type); - Lst_ForEach(gn->children, TargPrintName, NULL); + { + unsigned i; + + for (i=0; i<glist_num(&gn->children); i++) { + TargPrintName(glist_get(&gn->children, i), NULL); + } + } fprintf(debug_file, "\n"); Lst_ForEach(gn->commands, Targ_PrintCmd, NULL); fprintf(debug_file, "\n\n"); Index: othersrc/usr.bin/dholland-make2/graph.h diff -u othersrc/usr.bin/dholland-make2/graph.h:1.3 othersrc/usr.bin/dholland-make2/graph.h:1.4 --- othersrc/usr.bin/dholland-make2/graph.h:1.3 Mon Mar 4 08:47:08 2013 +++ othersrc/usr.bin/dholland-make2/graph.h Mon Mar 4 23:03:41 2013 @@ -1,4 +1,4 @@ -/* $NetBSD: graph.h,v 1.3 2013/03/04 08:47:08 dholland Exp $ */ +/* $NetBSD: graph.h,v 1.4 2013/03/04 23:03:41 dholland Exp $ */ /* * Copyright (c) 1988, 1989, 1990, 1993 @@ -159,10 +159,10 @@ struct GNode { GList iParents; /* Links to parents for which this is an * implied source, if any */ GList cohorts; /* Other nodes for the :: operator */ - Lst parents; /* Nodes that depend on this one */ - Lst children; /* Nodes on which this one depends */ - Lst order_pred; /* .ORDER nodes we need made */ - Lst order_succ; /* .ORDER nodes who need us */ + GList parents; /* Nodes that depend on this one */ + GList children; /* Nodes on which this one depends */ + GList order_pred; /* .ORDER nodes we need made */ + GList order_succ; /* .ORDER nodes who need us */ char cohort_num[8]; /* #n for this cohort */ int unmade_cohorts;/* # of unmade instances on the Index: othersrc/usr.bin/dholland-make2/parse.c diff -u othersrc/usr.bin/dholland-make2/parse.c:1.3 othersrc/usr.bin/dholland-make2/parse.c:1.4 --- othersrc/usr.bin/dholland-make2/parse.c:1.3 Mon Mar 4 08:47:08 2013 +++ othersrc/usr.bin/dholland-make2/parse.c Mon Mar 4 23:03:42 2013 @@ -1,4 +1,4 @@ -/* $NetBSD: parse.c,v 1.3 2013/03/04 08:47:08 dholland Exp $ */ +/* $NetBSD: parse.c,v 1.4 2013/03/04 23:03:42 dholland Exp $ */ /* * Copyright (c) 1988, 1989, 1990, 1993 @@ -138,7 +138,7 @@ #include "buf.h" #include "pathnames.h" -MAKE_RCSID("$NetBSD: parse.c,v 1.3 2013/03/04 08:47:08 dholland Exp $"); +MAKE_RCSID("$NetBSD: parse.c,v 1.4 2013/03/04 23:03:42 dholland Exp $"); //////////////////////////////////////////////////////////// // types and constants @@ -832,9 +832,9 @@ ParseLinkSrc(void *pgnp, void *cgnp) if ((pgn->type & OP_DOUBLEDEP) && glist_num(&pgn->cohorts) > 0) { pgn = glist_get(&pgn->cohorts, glist_num(&pgn->cohorts) - 1); } - (void)Lst_AtEnd(pgn->children, cgn); + glist_add(&pgn->children, cgn, NULL); if (specType == Not) - (void)Lst_AtEnd(cgn->parents, pgn); + glist_add(&cgn->parents, pgn, NULL); pgn->unmade += 1; if (DEBUG(PARSE)) { fprintf(debug_file, "# ParseLinkSrc: added child %s - %s\n", pgn->name, cgn->name); @@ -1003,8 +1003,8 @@ ParseDoSrc(int tOp, const char *src) */ gn = Targ_FindNode(src, TARG_CREATE); if (predecessor != NULL) { - (void)Lst_AtEnd(predecessor->order_succ, gn); - (void)Lst_AtEnd(gn->order_pred, predecessor); + glist_add(&predecessor->order_succ, gn, NULL); + glist_add(&gn->order_pred, predecessor, NULL); if (DEBUG(PARSE)) { fprintf(debug_file, "# ParseDoSrc: added Order dependency %s - %s\n", predecessor->name, gn->name);