From 7341ae280d0331b32fe3d1f40dc276575110d706 Mon Sep 17 00:00:00 2001 From: Matthew Fernandez Date: Thu, 3 Feb 2022 15:37:13 +1100 Subject: [PATCH] cgraph: implement a generic stack abstraction Similar to prior abstractions like `bitarray_t`, this is implemented header-only so as to be usable throughout the Graphviz tree, even by code that is not linking against cgraph. Given this implementation is header-only, it is natural to wonder why the type needs a `gv_` prefix. The answer is that one of the macOS system headers flouts the rule of `__` prefixing symbols that are part of the implementation and defines a typedef of `__darwin_sigaltstack` under the name `stack_t`. Hence this name is not usable by us. Gitlab: #1793, #2222 --- lib/cgraph/CMakeLists.txt | 1 + lib/cgraph/Makefile.am | 2 +- lib/cgraph/cgraph.vcxproj | 1 + lib/cgraph/cgraph.vcxproj.filters | 3 + lib/cgraph/stack.h | 95 +++++++++++++++++++++++++++ lib/cgraph/test_stack.c | 104 ++++++++++++++++++++++++++++++ rtest/test_c_utils.py | 2 +- 7 files changed, 206 insertions(+), 2 deletions(-) create mode 100644 lib/cgraph/stack.h create mode 100644 lib/cgraph/test_stack.c diff --git a/lib/cgraph/CMakeLists.txt b/lib/cgraph/CMakeLists.txt index ac298b7f9..1380c4784 100644 --- a/lib/cgraph/CMakeLists.txt +++ b/lib/cgraph/CMakeLists.txt @@ -21,6 +21,7 @@ add_library(cgraph SHARED likely.h prisize_t.h sprint.h + stack.h strcasecmp.h unreachable.h diff --git a/lib/cgraph/Makefile.am b/lib/cgraph/Makefile.am index 8dca83d78..9075016ef 100644 --- a/lib/cgraph/Makefile.am +++ b/lib/cgraph/Makefile.am @@ -13,7 +13,7 @@ endif pkginclude_HEADERS = cgraph.h noinst_HEADERS = agxbuf.h alloc.h bitarray.h cghdr.h exit.h itos.h likely.h \ - prisize_t.h sprint.h strcasecmp.h unreachable.h + prisize_t.h sprint.h stack.h strcasecmp.h unreachable.h noinst_LTLIBRARIES = libcgraph_C.la lib_LTLIBRARIES = libcgraph.la pkgconfig_DATA = libcgraph.pc diff --git a/lib/cgraph/cgraph.vcxproj b/lib/cgraph/cgraph.vcxproj index 4118f3dbd..272f365d5 100644 --- a/lib/cgraph/cgraph.vcxproj +++ b/lib/cgraph/cgraph.vcxproj @@ -107,6 +107,7 @@ win_flex -oscan.c scan.l + diff --git a/lib/cgraph/cgraph.vcxproj.filters b/lib/cgraph/cgraph.vcxproj.filters index 6606fd72a..c51a3dae1 100644 --- a/lib/cgraph/cgraph.vcxproj.filters +++ b/lib/cgraph/cgraph.vcxproj.filters @@ -45,6 +45,9 @@ Header Files + + Header Files + Header Files diff --git a/lib/cgraph/stack.h b/lib/cgraph/stack.h new file mode 100644 index 000000000..e7fd7431c --- /dev/null +++ b/lib/cgraph/stack.h @@ -0,0 +1,95 @@ +/// \file +/// \brief Implementation of a dynamically expanding stack data structure + +#pragma once + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +typedef struct { + void **base; ///< underlying store of contained elements + size_t size; ///< number of elements on the stack + size_t capacity; ///< total number of elements that can fit without expansion +} gv_stack_t; + +static inline size_t stack_size(const gv_stack_t *stack) { + assert(stack != NULL); + return stack->size; +} + +static inline bool stack_is_empty(const gv_stack_t *stack) { + assert(stack != NULL); + return stack_size(stack) == 0; +} + +static inline int stack_push(gv_stack_t *stack, void *item) { + + assert(stack != NULL); + + // do we need to expand the stack to make room for this item? + if (stack->size == stack->capacity) { + + // Capacity to allocate on the first push to a `gv_stack_t`. We pick + // something that works out to an allocation of 4KB, a common page size on + // multiple platforms, as a reasonably efficient default. + enum { FIRST_ALLOCATION = 4096 / sizeof(void *) }; + + // will our resize calculation overflow? + if (UNLIKELY(SIZE_MAX / 2 < stack->capacity)) { + return EOVERFLOW; + } + + size_t c = stack->capacity == 0 ? FIRST_ALLOCATION : (2 * stack->capacity); + void **b = realloc(stack->base, sizeof(b[0]) * c); + if (UNLIKELY(b == NULL)) { + return ENOMEM; + } + stack->capacity = c; + stack->base = b; + } + + assert(stack->base != NULL); + assert(stack->capacity > stack->size); + + // insert the new item + stack->base[stack->size] = item; + ++stack->size; + + return 0; +} + +static inline void stack_push_or_exit(gv_stack_t *stack, void *item) { + + assert(stack != NULL); + + int r = stack_push(stack, item); + if (UNLIKELY(r != 0)) { + fprintf(stderr, "stack_push failed: %s\n", strerror(r)); + graphviz_exit(EXIT_FAILURE); + } +} + +static inline void *stack_pop(gv_stack_t *stack) { + + assert(stack != NULL); + assert(!stack_is_empty(stack) && "pop from an empty stack"); + + void *top = stack->base[stack->size - 1]; + --stack->size; + return top; +} + +static inline void stack_reset(gv_stack_t *stack) { + + assert(stack != NULL); + + free(stack->base); + memset(stack, 0, sizeof(*stack)); +} diff --git a/lib/cgraph/test_stack.c b/lib/cgraph/test_stack.c new file mode 100644 index 000000000..61bc27740 --- /dev/null +++ b/lib/cgraph/test_stack.c @@ -0,0 +1,104 @@ +// basic unit tester for stack.h + +#ifdef NDEBUG +#error this is not intended to be compiled with assertions off +#endif + +#include +#include +#include +#include +#include + +// an stack should start in a known initial state +static void test_init(void) { + gv_stack_t s = {0}; + assert(stack_is_empty(&s)); + assert(stack_size(&s) == 0); +} + +// reset of an initialized stack should be OK and idempotent +static void test_init_reset(void) { + gv_stack_t s = {0}; + stack_reset(&s); + stack_reset(&s); + stack_reset(&s); +} + +// basic push then pop +static void test_push_one(void) { + gv_stack_t s = {0}; + void *arbitrary = (void *)0x42; + int r = stack_push(&s, arbitrary); + assert(r == 0); + assert(stack_size(&s) == 1); + void *top = stack_pop(&s); + assert(top == arbitrary); + assert(stack_is_empty(&s)); + stack_reset(&s); +} + +static void push_then_pop(size_t count) { + gv_stack_t s = {0}; + for (uintptr_t i = 0; i < (uintptr_t)count; ++i) { + int r = stack_push(&s, (void *)i); + assert(r == 0); + assert(stack_size(&s) == (size_t)i + 1); + } + for (uintptr_t i = (uintptr_t)count - 1;; --i) { + assert(stack_size(&s) == (size_t)i + 1); + void *p = stack_pop(&s); + assert((uintptr_t)p == i); + if (i == 0) { + break; + } + } + stack_reset(&s); +} + +// push a series of items +static void test_push_then_pop_ten(void) { push_then_pop(10); } + +// push enough to cause an expansion +static void test_push_then_pop_many(void) { push_then_pop(4096); } + +// interleave some push and pop operations +static void test_push_pop_interleaved(void) { + gv_stack_t s = {0}; + size_t size = 0; + for (uintptr_t i = 0; i < 4096; ++i) { + if (i % 3 == 1) { + void *p = stack_pop(&s); + assert((uintptr_t)p == i - 1); + --size; + } else { + int r = stack_push(&s, (void *)i); + assert(r == 0); + ++size; + } + assert(stack_size(&s) == size); + } + stack_reset(&s); +} + +int main(void) { + +#define RUN(t) \ + do { \ + printf("running test_%s... ", #t); \ + fflush(stdout); \ + test_##t(); \ + printf("OK\n"); \ + } while (0) + + RUN(init); + RUN(init_reset); + RUN(push_one); + RUN(push_then_pop_ten); + RUN(push_then_pop_many); + RUN(push_pop_interleaved); + +#undef RUN + + return EXIT_SUCCESS; +} diff --git a/rtest/test_c_utils.py b/rtest/test_c_utils.py index b303357c0..0fbe1df5a 100644 --- a/rtest/test_c_utils.py +++ b/rtest/test_c_utils.py @@ -9,7 +9,7 @@ import pytest sys.path.append(os.path.dirname(__file__)) from gvtest import run_c #pylint: disable=C0413 -@pytest.mark.parametrize("utility", ("bitarray", "sprint")) +@pytest.mark.parametrize("utility", ("bitarray", "sprint", "stack")) def test_utility(utility: str): """run the given utility’s unit tests""" -- 2.40.0