[PATCH] stack: New module.

[Marc Nieper-Wißkirchen]

From: Marc Nieper-Wißkirchen <marc@nieper-wisskirchen.de>

* MODULES.html.sh: Add entry for the stack module.
* modules/stack: New file.
* modules/stack-tests: New file.
* lib/stack.h: New file.
* tests/test-stack.c: New file.
---
 ChangeLog           |   9 +++
 MODULES.html.sh     |   1 +
 lib/stack.h         | 165 ++++++++++++++++++++++++++++++++++++++++++++
 modules/stack       |  25 +++++++
 modules/stack-tests |  13 ++++
 tests/test-stack.c  |  74 ++++++++++++++++++++
 6 files changed, 287 insertions(+)
 create mode 100644 lib/stack.h
 create mode 100644 modules/stack
 create mode 100644 modules/stack-tests
 create mode 100644 tests/test-stack.c

diff --git a/ChangeLog b/ChangeLog
index b479cf0c7..f496c8345 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,12 @@
+2020-10-10  Marc Nieper-Wißkirchen  <marc@nieper-wisskirchen.de>
+
+       stack: New module.
+       * MODULES.html.sh: Add entry for the stack module.
+       * modules/stack: New file.
+       * modules/stack-tests: New file.
+       * lib/stack.h: New file.
+       * tests/test-stack.c: New file.
+
 2020-10-10  Paul Eggert  <eggert@cs.ucla.edu>
 
        attribute: improve const, pure doc
diff --git a/MODULES.html.sh b/MODULES.html.sh
index a8a629e29..7e7cdae3e 100755
--- a/MODULES.html.sh
+++ b/MODULES.html.sh
@@ -2031,6 +2031,7 @@ func_all_modules ()
   func_module readline
   func_module readtokens
   func_module readtokens0
+  func_module stack
   func_module strverscmp
   func_module filevercmp
   func_end_table
diff --git a/lib/stack.h b/lib/stack.h
new file mode 100644
index 000000000..5d803901c
--- /dev/null
+++ b/lib/stack.h
@@ -0,0 +1,165 @@
+/* Type-safe stack data type.
+   Copyright (C) 2020 Free Software Foundation, Inc.
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
+
+/* Written by Marc Nieper-Wißkirchen <marc@nieper-wisskirchen.de>, 2020.  */
+
+/* This header file does not have include-guards as it is meant to be
+   includeable multiple times as long as the necessary defines have
+   been set up.
+
+   A stack is implemented with a homogenous array of elements in
+   memory, which will be resized (and moved) as needed.  Elements are
+   passed by value and it is the responsibility of the user-code to
+   free any resources associated with individual elements.
+
+   The exported names are all prefixed by ‘stack’ (e.g. stack_init),
+   but this can be changed by setting an appropriate define.
+     Type:               stack_type
+     Initialization:     stack_init (&stack);
+     De-initialization:  stack_destroy (&stack);
+     Predicate:          bool res = stack_empty (&stack);
+     Introspection:      ELEMENT *base = stack_base (&stack);
+     Pushing:            stack_push (&stack, element);
+     Popping:            ELEMENT element = stack_pop (&stack);
+     Discarding:         stack_discard (&stack);
+     Top-of-stack:       ELEMENT element = stack_top (&stack);
+     Size:               size_t size = stack_size (&stack);
+
+   Here, ELEMENT is the type to which GL_STACK_ELEMENT was defined when
+   this file was included.
+*/
+
+/* Before including this file, you need to define:
+     GL_STACK_ELEMENT       The type of the elements on the stack.
+     GL_STACK_STORAGECLASS  (Optional) The storage class specifier (e.g. 
static)
+                            to use in the function definitions.
+     GL_STACK_NAME          (Optional) The prefix to use for the type names
+                            and functions definitions instead of the default
+                            ‘stack’.
+
+   After including this file, these names will be undefined.
+
+   Before including this file, you also need to include:
+     #include "<stdbool.h>"
+     #include "<stdlib.h>"
+     #include "assure.h"
+     #include "xalloc.h"
+*/
+
+#ifndef GL_STACK_ELEMENT
+# error "Please define GL_STACK_ELEMENT first."
+#endif
+
+#ifndef GL_STACK_STORAGECLASS
+# define GL_STACK_STORAGECLASS
+#endif
+
+#ifndef GL_STACK_NAME
+# define GL_STACK_NAME stack
+#endif
+
+#define _GL_STACK_PREFIX(name) _GL_CONCAT(GL_STACK_NAME, _GL_CONCAT(_, name))
+#define _GL_STACK_TYPE _GL_STACK_PREFIX(type)
+
+typedef struct
+{
+  GL_STACK_ELEMENT *base;
+  size_t size;
+  size_t allocated;
+} _GL_STACK_TYPE;
+
+/* Initialize a stack.  */
+GL_STACK_STORAGECLASS void
+_GL_STACK_PREFIX (init) (_GL_STACK_TYPE *stack)
+{
+  stack->base = NULL;
+  stack->size = 0;
+  stack->allocated = 0;
+}
+
+/* Destroy a stack by freeing the allocated space.  */
+GL_STACK_STORAGECLASS void
+_GL_STACK_PREFIX (destroy) (_GL_STACK_TYPE *stack)
+{
+  free (stack->base);
+}
+
+/* Return true if the stack currently holds no element.  */
+GL_STACK_STORAGECLASS _GL_ATTRIBUTE_PURE bool
+_GL_STACK_PREFIX (empty) (const _GL_STACK_TYPE *stack)
+{
+  return stack->size == 0;
+}
+
+/* Return the current address of the array of stack elements.
+
+   The result is invalidated as soon as an element is added or removed
+   from the stack.  */
+GL_STACK_STORAGECLASS _GL_ATTRIBUTE_PURE GL_STACK_ELEMENT *
+_GL_STACK_PREFIX (current_base) (const _GL_STACK_TYPE *stack)
+{
+  return stack->base;
+}
+
+/* Push an element to the top of the stack.  */
+GL_STACK_STORAGECLASS void
+_GL_STACK_PREFIX (push) (_GL_STACK_TYPE *stack, GL_STACK_ELEMENT item)
+{
+  if (stack->size == stack->allocated)
+    stack->base = x2nrealloc (stack->base, &stack->allocated,
+                              sizeof (GL_STACK_ELEMENT));
+  stack->base [stack->size++] = item;
+}
+
+/* Pop the element from the top of the stack, which must be non-empty,
+   and return it. */
+GL_STACK_STORAGECLASS GL_STACK_ELEMENT
+_GL_STACK_PREFIX (pop) (_GL_STACK_TYPE *stack)
+{
+  affirm (!_GL_STACK_PREFIX (empty) (stack));
+  return stack->base [--stack->size];
+}
+
+/* Pop the element from the top of the stack, which must be
+   non-empty.  */
+GL_STACK_STORAGECLASS void
+_GL_STACK_PREFIX (discard) (_GL_STACK_TYPE *stack)
+{
+  affirm (!_GL_STACK_PREFIX (empty) (stack));
+  --stack->size;
+}
+
+/* Return the element from the top of the stack, which must be
+   non-empty.  */
+GL_STACK_STORAGECLASS GL_STACK_ELEMENT
+_GL_STACK_PREFIX (top) (const _GL_STACK_TYPE *stack)
+{
+  affirm (!_GL_STACK_PREFIX (empty) (stack));
+  return stack->base [stack->size - 1];
+}
+
+/* Return the currently stored number of elements in the stack.  */
+GL_STACK_STORAGECLASS _GL_ATTRIBUTE_PURE size_t
+_GL_STACK_PREFIX (size) (const _GL_STACK_TYPE *stack)
+{
+  return stack->size;
+}
+
+#undef GL_STACK_ELEMENT
+#undef GL_STACK_STORAGECLASS
+#undef GL_STACK_NAME
+#undef _GL_STACK_PREFIX
+#undef _GL_STACK_TYPE
diff --git a/modules/stack b/modules/stack
new file mode 100644
index 000000000..95f2ce9b9
--- /dev/null
+++ b/modules/stack
@@ -0,0 +1,25 @@
+Description:
+Type-safe stack data type.
+
+Files:
+lib/stack.h
+
+Depends-on:
+assure
+stdbool
+stdlib
+xalloc
+
+configure.ac:
+
+Makefile.am:
+lib_SOURCES += stack.h
+
+Include:
+"stack.h"
+
+License:
+GPL
+
+Maintainer:
+Marc Nieper-Wißkirchen
diff --git a/modules/stack-tests b/modules/stack-tests
new file mode 100644
index 000000000..308d7258e
--- /dev/null
+++ b/modules/stack-tests
@@ -0,0 +1,13 @@
+Files:
+tests/test-stack.c
+tests/macros.h
+
+Depends-on:
+string
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-stack
+check_PROGRAMS += test-stack
+test_stack_SOURCES = test-stack.c
diff --git a/tests/test-stack.c b/tests/test-stack.c
new file mode 100644
index 000000000..dbf4e19a3
--- /dev/null
+++ b/tests/test-stack.c
@@ -0,0 +1,74 @@
+/* Test of the type-safe stack data type.
+   Copyright (C) 2020 Free Software Foundation, Inc.
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
+
+/* Written by Marc Nieper-Wißkirchen <marc@nieper-wisskirchen.de>, 2020.  */
+
+#include <config.h>
+
+#include <stdbool.h>
+#include <stdlib.h>
+#include <string.h>
+#include "assure.h"
+#include "xalloc.h"
+
+#include "macros.h"
+
+#define GL_STACK_ELEMENT int
+#define GL_STACK_STORAGECLASS static
+#include "stack.h"
+
+#define GL_STACK_ELEMENT const char *
+#define GL_STACK_STORAGECLASS static
+#define GL_STACK_NAME string_stack
+#include "stack.h"
+
+int
+main (void)
+{
+  stack_type int_stack;
+  stack_init (&int_stack);
+  ASSERT (stack_size (&int_stack) == 0);
+  ASSERT (stack_empty (&int_stack));
+  stack_push (&int_stack, 0);
+  stack_push (&int_stack, 1);
+  stack_push (&int_stack, 2);
+  stack_push (&int_stack, 3);
+  stack_push (&int_stack, 4);
+  stack_push (&int_stack, 5);
+  stack_push (&int_stack, 6);
+  stack_push (&int_stack, 7);
+  stack_push (&int_stack, 8);
+  stack_push (&int_stack, 9);
+  ASSERT (stack_size (&int_stack) == 10);
+  ASSERT (!stack_empty (&int_stack));
+  ASSERT (stack_top (&int_stack) == 9);
+  ASSERT (stack_size (&int_stack) == 10);
+  ASSERT (stack_pop (&int_stack) == 9);
+  ASSERT (stack_size (&int_stack) == 9);
+  stack_discard (&int_stack);
+  ASSERT (stack_size (&int_stack) == 8);
+  ASSERT (stack_top (&int_stack) == 7);
+  stack_destroy (&int_stack);
+
+  string_stack_type string_stack [1];
+  string_stack_init (string_stack);
+  string_stack_push (string_stack, "foo");
+  ASSERT (STREQ (string_stack_pop (string_stack), "foo"));
+  ASSERT (string_stack_empty (string_stack));
+  string_stack_destroy (string_stack);
+
+  return EXIT_SUCCESS;
+}
-- 
2.25.1