1 /* Type-safe stack data type. 2 Copyright (C) 2020-2021 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 idx_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 = xpalloc (stack->base, &stack->allocated, 1, -1, 123 sizeof *stack->base); 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