[src/trunk]: src/usr.bin/make make(1): use a stack instead of a list for the ...

[rillig <rillig%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/e4f56c79a9bc
branches:  trunk
changeset: 943480:e4f56c79a9bc
user:      rillig <rillig%NetBSD.org@localhost>
date:      Fri Sep 04 17:59:36 2020 +0000

description:
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.

diffstat:

 usr.bin/make/lst.c   |  42 +++++++++++++++++++++++++++++++++++++++---
 usr.bin/make/lst.h   |  16 +++++++++++++++-
 usr.bin/make/parse.c |  37 +++++++++++++++----------------------
 3 files changed, 69 insertions(+), 26 deletions(-)

diffs (198 lines):

diff -r 6875f9f0bef1 -r e4f56c79a9bc usr.bin/make/lst.c
--- a/usr.bin/make/lst.c        Fri Sep 04 17:35:00 2020 +0000
+++ b/usr.bin/make/lst.c        Fri Sep 04 17:59:36 2020 +0000
@@ -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 @@
     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);
+}
diff -r 6875f9f0bef1 -r e4f56c79a9bc usr.bin/make/lst.h
--- a/usr.bin/make/lst.h        Fri Sep 04 17:35:00 2020 +0000
+++ b/usr.bin/make/lst.h        Fri Sep 04 17:59:36 2020 +0000
@@ -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 @@
 /* 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 */
diff -r 6875f9f0bef1 -r e4f56c79a9bc usr.bin/make/parse.c
--- a/usr.bin/make/parse.c      Fri Sep 04 17:35:00 2020 +0000
+++ b/usr.bin/make/parse.c      Fri Sep 04 17:59:36 2020 +0000
@@ -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 @@
 /* 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 @@
 }
 
 
-/*-
- *---------------------------------------------------------------------
- * Parse_setInput  --
- *     Start Parsing from the given source
+/* Start Parsing from the given source.
  *
- * Results:
- *     None
- *
- * 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 @@
 
     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 @@
     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 @@
        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 @@
     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 @@
     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
 }