1 /* 2 * This program is free software; you can redistribute it and/or 3 * modify it under the terms of the GNU General Public License 4 * as published by the Free Software Foundation; either version 2 5 * of the License, or (at your option) any later version. 6 * 7 * This program is distributed in the hope that it will be useful, 8 * but WITHOUT ANY WARRANTY; without even the implied warranty of 9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 10 * GNU General Public License for more details. 11 * 12 * You should have received a copy of the GNU General Public License 13 * along with this program; if not, write to the Free Software Foundation, 14 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 15 * 16 * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. 17 * All rights reserved. 18 */ 19 20 #pragma once 21 22 /** \file 23 * \ingroup bli 24 * \brief BLI_LINKSTACK_*** wrapper macros for using a \a LinkNode 25 * to store a stack of pointers, using a single linked list 26 * allocated from a mempool. 27 * 28 * \note These macros follow STACK_* macros defined in 'BLI_utildefines.h' 29 * and should be kept (mostly) interchangeable. 30 * 31 * \note ``_##var##_type`` is a dummy variable only used for typechecks. 32 */ 33 34 /* -------------------------------------------------------------------- */ 35 /* Linked Stack using BLI_mempool 36 * 37 * Uses mempool for storage. 38 */ 39 40 /** \name Linked Stack (mempool) 41 * \{ */ 42 43 #define BLI_LINKSTACK_DECLARE(var, type) \ 44 LinkNode *var; \ 45 BLI_mempool *var##_pool_; \ 46 type var##_type_ 47 48 #define BLI_LINKSTACK_INIT(var) \ 49 { \ 50 var = NULL; \ 51 var##_pool_ = BLI_mempool_create(sizeof(LinkNode), 0, 64, BLI_MEMPOOL_NOP); \ 52 } \ 53 (void)0 54 55 #define BLI_LINKSTACK_SIZE(var) BLI_mempool_len(var##_pool_) 56 57 /* check for typeof() */ 58 #ifdef __GNUC__ 59 # define BLI_LINKSTACK_PUSH(var, ptr) \ 60 (CHECK_TYPE_INLINE(ptr, typeof(var##_type_)), \ 61 BLI_linklist_prepend_pool(&(var), ptr, var##_pool_)) 62 # define BLI_LINKSTACK_POP(var) \ 63 (var ? (typeof(var##_type_))BLI_linklist_pop_pool(&(var), var##_pool_) : NULL) 64 # define BLI_LINKSTACK_POP_DEFAULT(var, r) \ 65 (var ? (typeof(var##_type_))BLI_linklist_pop_pool(&(var), var##_pool_) : r) 66 #else /* non gcc */ 67 # define BLI_LINKSTACK_PUSH(var, ptr) (BLI_linklist_prepend_pool(&(var), ptr, var##_pool_)) 68 # define BLI_LINKSTACK_POP(var) (var ? BLI_linklist_pop_pool(&(var), var##_pool_) : NULL) 69 # define BLI_LINKSTACK_POP_DEFAULT(var, r) (var ? BLI_linklist_pop_pool(&(var), var##_pool_) : r) 70 #endif /* gcc check */ 71 72 #define BLI_LINKSTACK_SWAP(var_a, var_b) \ 73 { \ 74 CHECK_TYPE_PAIR(var_a##_type_, var_b##_type_); \ 75 SWAP(LinkNode *, var_a, var_b); \ 76 SWAP(BLI_mempool *, var_a##_pool_, var_b##_pool_); \ 77 } \ 78 (void)0 79 80 #define BLI_LINKSTACK_FREE(var) \ 81 { \ 82 BLI_mempool_destroy(var##_pool_); \ 83 var##_pool_ = NULL; \ 84 (void)var##_pool_; \ 85 var = NULL; \ 86 (void)var; \ 87 (void)&(var##_type_); \ 88 } \ 89 (void)0 90 91 #include "BLI_linklist.h" 92 #include "BLI_mempool.h" 93 94 /** \} */ 95 96 /* -------------------------------------------------------------------- */ 97 /* Linked Stack, using stack memory (alloca) 98 * 99 * alloca never frees, pop'd items are stored in a free-list for reuse. 100 * only use for lists small enough to fit on the stack. 101 */ 102 103 /** \name Linked Stack (alloca) 104 * \{ */ 105 106 #ifdef __GNUC__ 107 # define _BLI_SMALLSTACK_CAST(var) (typeof(_##var##_type)) 108 #else 109 # define _BLI_SMALLSTACK_CAST(var) 110 #endif 111 112 #define _BLI_SMALLSTACK_FAKEUSER(var) (void)(&(_##var##_type)) 113 114 #define BLI_SMALLSTACK_DECLARE(var, type) \ 115 LinkNode *_##var##_stack = NULL, *_##var##_free = NULL, *_##var##_temp = NULL; \ 116 type _##var##_type 117 118 #define BLI_SMALLSTACK_PUSH(var, data) \ 119 { \ 120 CHECK_TYPE_PAIR(data, _##var##_type); \ 121 if (_##var##_free) { \ 122 _##var##_temp = _##var##_free; \ 123 _##var##_free = _##var##_free->next; \ 124 } \ 125 else { \ 126 _##var##_temp = alloca(sizeof(LinkNode)); \ 127 } \ 128 _##var##_temp->next = _##var##_stack; \ 129 _##var##_temp->link = data; \ 130 _##var##_stack = _##var##_temp; \ 131 _BLI_SMALLSTACK_FAKEUSER(var); \ 132 } \ 133 (void)0 134 135 /* internal use, no null check */ 136 #define _BLI_SMALLSTACK_DEL_EX(var_src, var_dst) \ 137 (void)(_BLI_SMALLSTACK_FAKEUSER(var_src), \ 138 _BLI_SMALLSTACK_FAKEUSER(var_dst), \ 139 (_##var_src##_temp = _##var_src##_stack->next), \ 140 (_##var_src##_stack->next = _##var_dst##_free), \ 141 (_##var_dst##_free = _##var_src##_stack), \ 142 (_##var_src##_stack = _##var_src##_temp)) 143 144 #define _BLI_SMALLSTACK_DEL(var) _BLI_SMALLSTACK_DEL_EX(var, var) 145 146 /* check for typeof() */ 147 #define BLI_SMALLSTACK_POP(var) \ 148 (_BLI_SMALLSTACK_CAST(var)( \ 149 (_##var##_stack) ? (_BLI_SMALLSTACK_DEL(var), (_##var##_free->link)) : NULL)) 150 151 /* support to put the free-node into another stack */ 152 #define BLI_SMALLSTACK_POP_EX(var_src, var_dst) \ 153 (_BLI_SMALLSTACK_CAST(var_src)( \ 154 (_##var_src##_stack) ? \ 155 (_BLI_SMALLSTACK_DEL_EX(var_src, var_dst), (_##var_dst##_free->link)) : \ 156 NULL)) 157 158 #define BLI_SMALLSTACK_PEEK(var) \ 159 (_BLI_SMALLSTACK_CAST(var)((_##var##_stack) ? _##var##_stack->link : NULL)) 160 161 #define BLI_SMALLSTACK_IS_EMPTY(var) ((_BLI_SMALLSTACK_CAST(var) _##var##_stack) == NULL) 162 163 /* fill in a lookup table */ 164 #define BLI_SMALLSTACK_AS_TABLE(var, data) \ 165 { \ 166 LinkNode *_##var##_iter; \ 167 unsigned int i; \ 168 for (_##var##_iter = _##var##_stack, i = 0; _##var##_iter; \ 169 _##var##_iter = _##var##_iter->next, i++) { \ 170 (data)[i] = _BLI_SMALLSTACK_CAST(var)(_##var##_iter->link); \ 171 } \ 172 } \ 173 ((void)0) 174 175 /* loop over stack members last-added-first */ 176 #define BLI_SMALLSTACK_ITER_BEGIN(var, item) \ 177 { \ 178 LinkNode *_##var##_iter; \ 179 for (_##var##_iter = _##var##_stack; _##var##_iter; _##var##_iter = _##var##_iter->next) { \ 180 item = _BLI_SMALLSTACK_CAST(var)(_##var##_iter->link); 181 182 #define BLI_SMALLSTACK_ITER_END \ 183 } \ 184 } \ 185 (void)0 186 187 #define BLI_SMALLSTACK_SWAP(var_a, var_b) \ 188 { \ 189 CHECK_TYPE_PAIR(_##var_a##_type, _##var_b##_type); \ 190 SWAP(LinkNode *, _##var_a##_stack, _##var_b##_stack); \ 191 SWAP(LinkNode *, _##var_a##_free, _##var_b##_free); \ 192 } \ 193 (void)0 194 195 /** \} */ 196