Re: stack module

["Marc Nieper-Wißkirchen" <marc.nieper+gnu@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 1572 bytes --]

Dear Bruno,

please see the attached patch for the new module.

Thanks,

Marc

Am Mi., 7. Okt. 2020 um 11:01 Uhr schrieb Marc Nieper-Wißkirchen
<marc.nieper+gnu@gmail.com>:
>
> Hi Bruno,
>
> I am finally finishing my work on the stack module.
>
> Am Do., 23. Juli 2020 um 12:36 Uhr schrieb Bruno Haible <bruno@clisp.org>:
>
> [...]
>
> > This is perfectly acceptable for Gnulib. It has debuggability and type safety.
> >
> > You have precedent e.g. in lib/diffseq.h and lib/aligned-malloc.h.
> >
> > You can even omit the 'GL_' prefix from the macro names. The user can #undef
> > the macros after including the file; therefore there is nearly no risk of
> > collision with macros defined by other code.
>
> After I have given it a bit more thought, I see a different type of
> collision possibility, namely if some header file uses the stack
> header file. It will leak the macro names. Assume that the stack
> module accepts the macro name ELEMENT for the element type. A
> hypothetical header for the frob type may be implemented as:
>
> #ifndef FROB_H
> #define FROB_H
> ...
> #define ELEMENT int
> #define STORAGECLASS static inline
> #include "stack.h"
> ...
> struct frob
> {
>   stack frob_stack;
>   ...
> };
> ...
> #endif /* FROB_H */
>
> Now, user code cannot do:
>
> #define ELEMENT hydrogen
> #include "frob.h"
> ...
>
> (The ELEMENT definition in the first line could in fact be exported by
> some other header file.)
>
> Therefore, I think I prefer to use prefixed names.
>
> Cheers,
>
> Marc

[-- Attachment #2: 0001-Type-safe-stack-data-type.patch --]
[-- Type: text/x-patch, Size: 10525 bytes --]

From c449d60058f4a5806729ec76779fbb050890ddaf Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Marc=20Nieper-Wi=C3=9Fkirchen?= <marc@nieper-wisskirchen.de>
Date: Wed, 7 Oct 2020 13:29:10 +0200
Subject: [PATCH] Type-safe stack data type. * 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         | 163 ++++++++++++++++++++++++++++++++++++++++++++
 modules/stack       |  25 +++++++
 modules/stack-tests |  13 ++++
 tests/test-stack.c  |  74 ++++++++++++++++++++
 6 files changed, 285 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 875f3551a..b64689f73 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,12 @@
+2020-10-07  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-05  Paul Eggert  <eggert@cs.ucla.edu>
 
 	thread: pacify GCC on Solaris 10
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..22e976952
--- /dev/null
+++ b/lib/stack.h
@@ -0,0 +1,163 @@
+/* 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 allocate and 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);
+*/
+
+/* 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