lib/stack.h

   1 /* Type-safe stack data type.
   2    Copyright (C) 2020 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  16
  17 /* Written by Marc Nieper-Wißkirchen <marc@nieper-wisskirchen.de>, 2020.  */
  18
  19 /* This header file does not have include-guards as it is meant to be
  20    includeable multiple times as long as the necessary defines have
  21    been set up.
  22
  23    A stack is implemented with a homogenous array of elements in
  24    memory, which will be resized (and moved) as needed.  Elements are
  25    passed by value and it is the responsibility of the user-code to
  26    free any resources associated with individual elements.
  27
  28    The exported names are all prefixed by ‘stack’ (e.g. stack_init),
  29    but this can be changed by setting an appropriate define.
  30      Type:               stack_type
  31      Initialization:     stack_init (&stack);
  32      De-initialization:  stack_destroy (&stack);
  33      Predicate:          bool res = stack_empty (&stack);
  34      Introspection:      ELEMENT *base = stack_base (&stack);
  35      Pushing:            stack_push (&stack, element);
  36      Popping:            ELEMENT element = stack_pop (&stack);
  37      Discarding:         stack_discard (&stack);
  38      Top-of-stack:       ELEMENT element = stack_top (&stack);
  39      Size:               size_t size = stack_size (&stack);
  40
  41    Here, ELEMENT is the type to which GL_STACK_ELEMENT was defined when
  42    this file was included.
  43 */
  44
  45 /* Before including this file, you need to define:
  46      GL_STACK_ELEMENT       The type of the elements on the stack.
  47      GL_STACK_STORAGECLASS  (Optional) The storage class specifier (e.g. static)
  48                             to use in the function definitions.
  49      GL_STACK_NAME          (Optional) The prefix to use for the type names
  50                             and functions definitions instead of the default
  51                             ‘stack’.
  52
  53    After including this file, these names will be undefined.
  54
  55    Before including this file, you also need to include:
  56      #include <stdbool.h>
  57      #include <stdlib.h>
  58      #include "assure.h"
  59      #include "xalloc.h"
  60 */
  61
  62 #ifndef GL_STACK_ELEMENT
  63 # error "Please define GL_STACK_ELEMENT first."
  64 #endif
  65
  66 #ifndef GL_STACK_STORAGECLASS
  67 # define GL_STACK_STORAGECLASS
  68 #endif
  69
  70 #ifndef GL_STACK_NAME
  71 # define GL_STACK_NAME stack
  72 #endif
  73
  74 #define _GL_STACK_PREFIX(name) _GL_CONCAT(GL_STACK_NAME, _GL_CONCAT(_, name))
  75 #define _GL_STACK_TYPE _GL_STACK_PREFIX(type)
  76
  77 typedef struct
  78 {
  79   GL_STACK_ELEMENT *base;
  80   size_t size;
  81   size_t allocated;
  82 } _GL_STACK_TYPE;
  83
  84 /* Initialize a stack.  */
  85 GL_STACK_STORAGECLASS void
  86 _GL_STACK_PREFIX (init) (_GL_STACK_TYPE *stack)
  87 {
  88   stack->base = NULL;
  89   stack->size = 0;
  90   stack->allocated = 0;
  91 }
  92
  93 /* Destroy a stack by freeing the allocated space.  */
  94 GL_STACK_STORAGECLASS void
  95 _GL_STACK_PREFIX (destroy) (_GL_STACK_TYPE *stack)
  96 {
  97   free (stack->base);
  98 }
  99
 100 /* Return true if the stack currently holds no element.  */
 101 GL_STACK_STORAGECLASS _GL_ATTRIBUTE_PURE bool
 102 _GL_STACK_PREFIX (empty) (const _GL_STACK_TYPE *stack)
 103 {
 104   return stack->size == 0;
 105 }
 106
 107 /* Return the current address of the array of stack elements.
 108
 109    The result is invalidated as soon as an element is added or removed
 110    from the stack.  */
 111 GL_STACK_STORAGECLASS _GL_ATTRIBUTE_PURE GL_STACK_ELEMENT *
 112 _GL_STACK_PREFIX (current_base) (const _GL_STACK_TYPE *stack)
 113 {
 114   return stack->base;
 115 }
 116
 117 /* Push an element to the top of the stack.  */
 118 GL_STACK_STORAGECLASS void
 119 _GL_STACK_PREFIX (push) (_GL_STACK_TYPE *stack, GL_STACK_ELEMENT item)
 120 {
 121   if (stack->size == stack->allocated)
 122     stack->base = x2nrealloc (stack->base, &stack->allocated,
 123                               sizeof (GL_STACK_ELEMENT));
 124   stack->base [stack->size++] = item;
 125 }
 126
 127 /* Pop the element from the top of the stack, which must be non-empty,
 128    and return it. */
 129 GL_STACK_STORAGECLASS GL_STACK_ELEMENT
 130 _GL_STACK_PREFIX (pop) (_GL_STACK_TYPE *stack)
 131 {
 132   affirm (!_GL_STACK_PREFIX (empty) (stack));
 133   return stack->base [--stack->size];
 134 }
 135
 136 /* Pop the element from the top of the stack, which must be
 137    non-empty.  */
 138 GL_STACK_STORAGECLASS void
 139 _GL_STACK_PREFIX (discard) (_GL_STACK_TYPE *stack)
 140 {
 141   affirm (!_GL_STACK_PREFIX (empty) (stack));
 142   --stack->size;
 143 }
 144
 145 /* Return the element from the top of the stack, which must be
 146    non-empty.  */
 147 GL_STACK_STORAGECLASS GL_STACK_ELEMENT
 148 _GL_STACK_PREFIX (top) (const _GL_STACK_TYPE *stack)
 149 {
 150   affirm (!_GL_STACK_PREFIX (empty) (stack));
 151   return stack->base [stack->size - 1];
 152 }
 153
 154 /* Return the currently stored number of elements in the stack.  */
 155 GL_STACK_STORAGECLASS _GL_ATTRIBUTE_PURE size_t
 156 _GL_STACK_PREFIX (size) (const _GL_STACK_TYPE *stack)
 157 {
 158   return stack->size;
 159 }
 160
 161 #undef GL_STACK_ELEMENT
 162 #undef GL_STACK_STORAGECLASS
 163 #undef GL_STACK_NAME
 164 #undef _GL_STACK_PREFIX
 165 #undef _GL_STACK_TYPE