Module Name: src
Committed By: rillig
Date: Fri Sep 4 17:59:37 UTC 2020
Modified Files:
src/usr.bin/make: lst.c lst.h parse.c
Log Message:
make(1): use a stack instead of a list for the nested include path
By using a Stack instead of a Lst, the available API is reduced to the
very few functions that are really needed for a stack. This prevents
accidental misuse (such as confusing Lst_Append with Lst_Prepend) and
clearly communicates what the expected behavior is.
A stack also needs fewer calls to bmake_malloc than an equally-sized
list, and the memory is contiguous. For the nested include path, all
this doesn't matter, but the type is so generic that it may be used in
other places as well.
To generate a diff of this commit:
cvs rdiff -u -r1.60 -r1.61 src/usr.bin/make/lst.c src/usr.bin/make/lst.h
cvs rdiff -u -r1.275 -r1.276 src/usr.bin/make/parse.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/usr.bin/make/lst.c
diff -u src/usr.bin/make/lst.c:1.60 src/usr.bin/make/lst.c:1.61
--- src/usr.bin/make/lst.c:1.60 Mon Aug 31 05:56:02 2020
+++ src/usr.bin/make/lst.c Fri Sep 4 17:59:36 2020
@@ -1,4 +1,4 @@
-/* $NetBSD: lst.c,v 1.60 2020/08/31 05:56:02 rillig Exp $ */
+/* $NetBSD: lst.c,v 1.61 2020/09/04 17:59:36 rillig Exp $ */
/*
* Copyright (c) 1988, 1989, 1990, 1993
@@ -37,11 +37,11 @@
#include "make.h"
#ifndef MAKE_NATIVE
-static char rcsid[] = "$NetBSD: lst.c,v 1.60 2020/08/31 05:56:02 rillig Exp $";
+static char rcsid[] = "$NetBSD: lst.c,v 1.61 2020/09/04 17:59:36 rillig Exp $";
#else
#include <sys/cdefs.h>
#ifndef lint
-__RCSID("$NetBSD: lst.c,v 1.60 2020/08/31 05:56:02 rillig Exp $");
+__RCSID("$NetBSD: lst.c,v 1.61 2020/09/04 17:59:36 rillig Exp $");
#endif /* not lint */
#endif
@@ -631,3 +631,39 @@ Lst_Dequeue(Lst list)
assert(datum != NULL);
return datum;
}
+
+void
+Stack_Init(Stack *stack)
+{
+ stack->len = 0;
+ stack->cap = 10;
+ stack->items = bmake_malloc(stack->cap * sizeof stack->items[0]);
+}
+
+Boolean Stack_IsEmpty(Stack *stack)
+{
+ return stack->len == 0;
+}
+
+void Stack_Push(Stack *stack, void *datum)
+{
+ if (stack->len >= stack->cap) {
+ stack->cap *= 2;
+ stack->items = bmake_realloc(stack->items,
+ stack->cap * sizeof stack->items[0]);
+ }
+ stack->items[stack->len] = datum;
+ stack->len++;
+}
+
+void *Stack_Pop(Stack *stack)
+{
+ assert(stack->len > 0);
+ stack->len--;
+ return stack->items[stack->len];
+}
+
+void Stack_Done(Stack *stack)
+{
+ free(stack->items);
+}
Index: src/usr.bin/make/lst.h
diff -u src/usr.bin/make/lst.h:1.60 src/usr.bin/make/lst.h:1.61
--- src/usr.bin/make/lst.h:1.60 Wed Sep 2 23:33:13 2020
+++ src/usr.bin/make/lst.h Fri Sep 4 17:59:36 2020
@@ -1,4 +1,4 @@
-/* $NetBSD: lst.h,v 1.60 2020/09/02 23:33:13 rillig Exp $ */
+/* $NetBSD: lst.h,v 1.61 2020/09/04 17:59:36 rillig Exp $ */
/*
* Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
@@ -176,4 +176,18 @@ void Lst_Enqueue(Lst, void *);
/* Remove the head node of the queue and return its datum. */
void *Lst_Dequeue(Lst);
+/* A stack is a very simple collection of items that only allows access to the
+ * top-most item. */
+typedef struct {
+ void **items;
+ size_t len;
+ size_t cap;
+} Stack;
+
+void Stack_Init(Stack *);
+Boolean Stack_IsEmpty(Stack *);
+void Stack_Push(Stack *, void *);
+void *Stack_Pop(Stack *);
+void Stack_Done(Stack *);
+
#endif /* MAKE_LST_H */
Index: src/usr.bin/make/parse.c
diff -u src/usr.bin/make/parse.c:1.275 src/usr.bin/make/parse.c:1.276
--- src/usr.bin/make/parse.c:1.275 Tue Sep 1 17:38:26 2020
+++ src/usr.bin/make/parse.c Fri Sep 4 17:59:36 2020
@@ -1,4 +1,4 @@
-/* $NetBSD: parse.c,v 1.275 2020/09/01 17:38:26 rillig Exp $ */
+/* $NetBSD: parse.c,v 1.276 2020/09/04 17:59:36 rillig Exp $ */
/*
* Copyright (c) 1988, 1989, 1990, 1993
@@ -69,14 +69,14 @@
*/
#ifndef MAKE_NATIVE
-static char rcsid[] = "$NetBSD: parse.c,v 1.275 2020/09/01 17:38:26 rillig Exp $";
+static char rcsid[] = "$NetBSD: parse.c,v 1.276 2020/09/04 17:59:36 rillig 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.275 2020/09/01 17:38:26 rillig Exp $");
+__RCSID("$NetBSD: parse.c,v 1.276 2020/09/04 17:59:36 rillig Exp $");
#endif
#endif /* not lint */
#endif
@@ -267,8 +267,10 @@ static int fatals = 0;
/* current file being read */
static IFile *curFile;
-/* stack of IFiles generated by .includes */
-static Lst includes;
+/* The current file from the command line (at the bottom of the stack) and
+ * further up all the files that are currently being read due to nested
+ * .include directives. */
+static Stack /* of *IFile */ includes;
/* include paths (lists of directories) */
Lst parseIncPath; /* dirs for "..." includes */
@@ -2442,19 +2444,9 @@ ParseTrackInput(const char *name)
}
-/*-
- *---------------------------------------------------------------------
- * Parse_setInput --
- * Start Parsing from the given source
- *
- * Results:
- * None
+/* Start Parsing from the given source.
*
- * Side Effects:
- * A structure is added to the includes Lst and readProc, lineno,
- * fname and curFile are altered for the new file
- *---------------------------------------------------------------------
- */
+ * The given file is added to the includes stack. */
void
Parse_SetInput(const char *name, int line, int fd,
char *(*nextbuf)(void *, size_t *), void *arg)
@@ -2477,7 +2469,7 @@ Parse_SetInput(const char *name, int lin
if (curFile != NULL)
/* Save exiting file info */
- Lst_Prepend(includes, curFile);
+ Stack_Push(&includes, curFile);
/* Allocate and fill in new structure */
curFile = bmake_malloc(sizeof *curFile);
@@ -2743,7 +2735,7 @@ ParseEOF(void)
free(curFile->P_str);
free(curFile);
- if (Lst_IsEmpty(includes)) {
+ if (Stack_IsEmpty(&includes)) {
curFile = NULL;
/* We've run out of input */
Var_Delete(".PARSEDIR", VAR_GLOBAL);
@@ -2753,7 +2745,7 @@ ParseEOF(void)
return DONE;
}
- curFile = Lst_Dequeue(includes);
+ curFile = Stack_Pop(&includes);
if (DEBUG(PARSE))
fprintf(debug_file, "ParseEOF: returning to file %s, line %d\n",
curFile->fname, curFile->lineno);
@@ -3287,7 +3279,7 @@ Parse_Init(void)
parseIncPath = Lst_Init();
sysIncPath = Lst_Init();
defIncPath = Lst_Init();
- includes = Lst_Init();
+ Stack_Init(&includes);
#ifdef CLEANUP
targCmds = Lst_Init();
#endif
@@ -3303,7 +3295,8 @@ Parse_End(void)
Lst_Destroy(defIncPath, Dir_Destroy);
Lst_Destroy(sysIncPath, Dir_Destroy);
Lst_Destroy(parseIncPath, Dir_Destroy);
- Lst_Free(includes); /* Should be empty now */
+ assert(Stack_IsEmpty(&includes));
+ Stack_Done(&includes);
#endif
}
