Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src/usr.bin/make Readd optimization last night. Problems earlie...
details: https://anonhg.NetBSD.org/src/rev/185eed90462a
branches: trunk
changeset: 487674:185eed90462a
user: mycroft <mycroft%NetBSD.org@localhost>
date: Sun Jun 11 07:39:52 2000 +0000
description:
Readd optimization last night. Problems earlier were partially due to the
arguments names on one function being swapped (by a previous author).
Do not do any duplicate suppression when a source list is created. Instead:
* OP_MADE protects against trying to make the source multiple times.
* A new OP_MARK flag is introduced to suppress duplicates while expanding
the .ALLSRC variable and .USE targets.
This turns the O(n^2) insertion into O(n) in most cases.
This is tested with a `make build' and some special test cases.
diffstat:
usr.bin/make/make.c | 49 +++++++++++++++++++++++++++++++++++++------------
usr.bin/make/make.h | 3 ++-
usr.bin/make/parse.c | 16 +++++++---------
usr.bin/make/suff.c | 29 ++++++++++++-----------------
4 files changed, 58 insertions(+), 39 deletions(-)
diffs (246 lines):
diff -r 5d39e79a7aaa -r 185eed90462a usr.bin/make/make.c
--- a/usr.bin/make/make.c Sun Jun 11 07:16:20 2000 +0000
+++ b/usr.bin/make/make.c Sun Jun 11 07:39:52 2000 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: make.c,v 1.30 2000/06/10 22:28:33 mycroft Exp $ */
+/* $NetBSD: make.c,v 1.31 2000/06/11 07:39:52 mycroft Exp $ */
/*
* Copyright (c) 1988, 1989, 1990, 1993
@@ -39,14 +39,14 @@
*/
#ifdef MAKE_BOOTSTRAP
-static char rcsid[] = "$NetBSD: make.c,v 1.30 2000/06/10 22:28:33 mycroft Exp $";
+static char rcsid[] = "$NetBSD: make.c,v 1.31 2000/06/11 07:39:52 mycroft Exp $";
#else
#include <sys/cdefs.h>
#ifndef lint
#if 0
static char sccsid[] = "@(#)make.c 8.1 (Berkeley) 6/6/93";
#else
-__RCSID("$NetBSD: make.c,v 1.30 2000/06/10 22:28:33 mycroft Exp $");
+__RCSID("$NetBSD: make.c,v 1.31 2000/06/11 07:39:52 mycroft Exp $");
#endif
#endif /* not lint */
#endif
@@ -102,6 +102,7 @@
static int MakeAddChild __P((ClientData, ClientData));
static int MakeFindChild __P((ClientData, ClientData));
+static int MakeUnmark __P((ClientData, ClientData));
static int MakeAddAllSrc __P((ClientData, ClientData));
static int MakeTimeStamp __P((ClientData, ClientData));
static int MakeHandleUse __P((ClientData, ClientData));
@@ -410,11 +411,9 @@
gn = tgn;
}
- if (Lst_Member (pgn->children, gn) == NILLNODE) {
- (void) Lst_AtEnd (pgn->children, gn);
- (void) Lst_AtEnd (gn->parents, pgn);
- pgn->unmade += 1;
- }
+ (void) Lst_AtEnd (pgn->children, gn);
+ (void) Lst_AtEnd (gn->parents, pgn);
+ pgn->unmade += 1;
}
Lst_Close (cgn->children);
}
@@ -436,12 +435,20 @@
}
return (0);
}
+
static int
-MakeHandleUse (pgn, cgn)
- ClientData pgn; /* the current parent */
- ClientData cgn; /* the child we've just examined */
+MakeHandleUse (cgnp, pgnp)
+ ClientData cgnp; /* the child we've just examined */
+ ClientData pgnp; /* the current parent */
{
- return Make_HandleUse((GNode *) pgn, (GNode *) cgn);
+ GNode *cgn = (GNode *) cgnp;
+ GNode *pgn = (GNode *) pgnp;
+
+ if (cgn->type & OP_MARK)
+ return (0);
+ cgn->type |= OP_MARK;
+
+ return Make_HandleUse(cgn, pgn);
}
@@ -669,6 +676,17 @@
*-----------------------------------------------------------------------
*/
static int
+MakeUnmark (cgnp, pgnp)
+ ClientData cgnp;
+ ClientData pgnp;
+{
+ GNode *cgn = (GNode *) cgnp;
+
+ cgn->type &= ~OP_MARK;
+ return (0);
+}
+
+static int
MakeAddAllSrc (cgnp, pgnp)
ClientData cgnp; /* The child to add */
ClientData pgnp; /* The parent to whose ALLSRC variable it should be */
@@ -676,6 +694,11 @@
{
GNode *cgn = (GNode *) cgnp;
GNode *pgn = (GNode *) pgnp;
+
+ if (cgn->type & OP_MARK)
+ return (0);
+ cgn->type |= OP_MARK;
+
if ((cgn->type & (OP_EXEC|OP_USE|OP_INVISIBLE)) == 0) {
char *child;
char *p1 = NULL;
@@ -742,6 +765,7 @@
Make_DoAllVar (gn)
GNode *gn;
{
+ Lst_ForEach (gn->children, MakeUnmark, (ClientData) gn);
Lst_ForEach (gn->children, MakeAddAllSrc, (ClientData) gn);
if (!Var_Exists (OODATE, gn)) {
@@ -968,6 +992,7 @@
(void)Dir_MTime(gn);
Var_Set (TARGET, gn->path ? gn->path : gn->name, gn);
+ Lst_ForEach (gn->children, MakeUnmark, (ClientData)gn);
Lst_ForEach (gn->children, MakeHandleUse, (ClientData)gn);
Suff_FindDeps (gn);
diff -r 5d39e79a7aaa -r 185eed90462a usr.bin/make/make.h
--- a/usr.bin/make/make.h Sun Jun 11 07:16:20 2000 +0000
+++ b/usr.bin/make/make.h Sun Jun 11 07:39:52 2000 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: make.h,v 1.28 2000/06/10 22:28:33 mycroft Exp $ */
+/* $NetBSD: make.h,v 1.29 2000/06/11 07:39:53 mycroft Exp $ */
/*
* Copyright (c) 1988, 1989, 1990, 1993
@@ -230,6 +230,7 @@
* commands for a target */
#define OP_SAVE_CMDS 0x04000000 /* Saving commands on .END (Compat) */
#define OP_DEPS_FOUND 0x02000000 /* Already processed by Suff_FindDeps */
+#define OP_MARK 0x01000000 /* Node found while expanding .ALLSRC */
/*
* OP_NOP will return TRUE if the node with the given type was not the
diff -r 5d39e79a7aaa -r 185eed90462a usr.bin/make/parse.c
--- a/usr.bin/make/parse.c Sun Jun 11 07:16:20 2000 +0000
+++ b/usr.bin/make/parse.c Sun Jun 11 07:39:52 2000 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: parse.c,v 1.51 2000/06/10 22:28:34 mycroft Exp $ */
+/* $NetBSD: parse.c,v 1.52 2000/06/11 07:39:53 mycroft Exp $ */
/*
* Copyright (c) 1988, 1989, 1990, 1993
@@ -39,14 +39,14 @@
*/
#ifdef MAKE_BOOTSTRAP
-static char rcsid[] = "$NetBSD: parse.c,v 1.51 2000/06/10 22:28:34 mycroft Exp $";
+static char rcsid[] = "$NetBSD: parse.c,v 1.52 2000/06/11 07:39:53 mycroft Exp $";
#else
#include <sys/cdefs.h>
#ifndef lint
#if 0
static char sccsid[] = "@(#)parse.c 8.3 (Berkeley) 3/19/94";
#else
-__RCSID("$NetBSD: parse.c,v 1.51 2000/06/10 22:28:34 mycroft Exp $");
+__RCSID("$NetBSD: parse.c,v 1.52 2000/06/11 07:39:53 mycroft Exp $");
#endif
#endif /* not lint */
#endif
@@ -443,15 +443,13 @@
{
GNode *pgn = (GNode *) pgnp;
GNode *cgn = (GNode *) cgnp;
+
if ((pgn->type & OP_DOUBLEDEP) && !Lst_IsEmpty (pgn->cohorts))
pgn = (GNode *) Lst_Datum (Lst_Last (pgn->cohorts));
- if (Lst_Member (pgn->children, (ClientData)cgn) == NILLNODE) {
- (void)Lst_AtEnd (pgn->children, (ClientData)cgn);
- if (specType == Not) {
+ (void)Lst_AtEnd (pgn->children, (ClientData)cgn);
+ if (specType == Not)
(void)Lst_AtEnd (cgn->parents, (ClientData)pgn);
- }
- pgn->unmade += 1;
- }
+ pgn->unmade += 1;
return (0);
}
diff -r 5d39e79a7aaa -r 185eed90462a usr.bin/make/suff.c
--- a/usr.bin/make/suff.c Sun Jun 11 07:16:20 2000 +0000
+++ b/usr.bin/make/suff.c Sun Jun 11 07:39:52 2000 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: suff.c,v 1.30 2000/06/10 22:28:34 mycroft Exp $ */
+/* $NetBSD: suff.c,v 1.31 2000/06/11 07:39:53 mycroft Exp $ */
/*
* Copyright (c) 1988, 1989, 1990, 1993
@@ -39,14 +39,14 @@
*/
#ifdef MAKE_BOOTSTRAP
-static char rcsid[] = "$NetBSD: suff.c,v 1.30 2000/06/10 22:28:34 mycroft Exp $";
+static char rcsid[] = "$NetBSD: suff.c,v 1.31 2000/06/11 07:39:53 mycroft Exp $";
#else
#include <sys/cdefs.h>
#ifndef lint
#if 0
static char sccsid[] = "@(#)suff.c 8.4 (Berkeley) 3/21/94";
#else
-__RCSID("$NetBSD: suff.c,v 1.30 2000/06/10 22:28:34 mycroft Exp $");
+__RCSID("$NetBSD: suff.c,v 1.31 2000/06/11 07:39:53 mycroft Exp $");
#endif
#endif /* not lint */
#endif
@@ -1680,15 +1680,12 @@
char *tname; /* Name of transformation rule */
GNode *gn; /* Node for same */
- if (Lst_Member(tGn->children, (ClientData)sGn) == NILLNODE) {
- /*
- * Not already linked, so form the proper links between the
- * target and source.
- */
- (void)Lst_AtEnd(tGn->children, (ClientData)sGn);
- (void)Lst_AtEnd(sGn->parents, (ClientData)tGn);
- tGn->unmade += 1;
- }
+ /*
+ * Form the proper links between the target and source.
+ */
+ (void)Lst_AtEnd(tGn->children, (ClientData)sGn);
+ (void)Lst_AtEnd(sGn->parents, (ClientData)tGn);
+ tGn->unmade += 1;
/*
* Locate the transformation rule itself
@@ -1800,11 +1797,9 @@
/*
* Create the link between the two nodes right off
*/
- if (Lst_Member(gn->children, (ClientData)mem) == NILLNODE) {
- (void)Lst_AtEnd(gn->children, (ClientData)mem);
- (void)Lst_AtEnd(mem->parents, (ClientData)gn);
- gn->unmade += 1;
- }
+ (void)Lst_AtEnd(gn->children, (ClientData)mem);
+ (void)Lst_AtEnd(mem->parents, (ClientData)gn);
+ gn->unmade += 1;
/*
* Copy in the variables from the member node to this one.
Home |
Main Index |
Thread Index |
Old Index