From c449d60058f4a5806729ec76779fbb050890ddaf Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20Nieper-Wi=C3=9Fkirchen?= 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 + + 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 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 . */ + +/* Written by Marc Nieper-Wißkirchen , 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 "" + #include "" + #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 . */ + +/* Written by Marc Nieper-Wißkirchen , 2020. */ + +#include + +#include +#include +#include +#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