1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
|
/* SPDX-License-Identifier: GPL-2.0-or-later
* Copyright 2001-2002 NaN Holding BV. All rights reserved. */
#pragma once
/** \file
* \ingroup bli
* \brief BLI_LINKSTACK_*** wrapper macros for using a \a LinkNode
* to store a stack of pointers, using a single linked list
* allocated from a mempool.
*
* \note These macros follow STACK_* macros defined in 'BLI_utildefines.h'
* and should be kept (mostly) interchangeable.
*
* \note `_##var##_type` is a dummy variable only used for type-checks.
*/
/* -------------------------------------------------------------------- */
/** \name Linked Stack (mempool)
*
* Uses #BLI_mempool for storage.
* \{ */
#define BLI_LINKSTACK_DECLARE(var, type) \
LinkNode *var; \
BLI_mempool *var##_pool_; \
type var##_type_
#define BLI_LINKSTACK_INIT(var) \
{ \
var = NULL; \
var##_pool_ = BLI_mempool_create(sizeof(LinkNode), 0, 64, BLI_MEMPOOL_NOP); \
} \
(void)0
#define BLI_LINKSTACK_SIZE(var) BLI_mempool_len(var##_pool_)
/* check for typeof() */
#ifdef __GNUC__
# define BLI_LINKSTACK_PUSH(var, ptr) \
(CHECK_TYPE_INLINE(ptr, typeof(var##_type_)), \
BLI_linklist_prepend_pool(&(var), ptr, var##_pool_))
# define BLI_LINKSTACK_POP(var) \
(var ? (typeof(var##_type_))BLI_linklist_pop_pool(&(var), var##_pool_) : NULL)
# define BLI_LINKSTACK_POP_DEFAULT(var, r) \
(var ? (typeof(var##_type_))BLI_linklist_pop_pool(&(var), var##_pool_) : r)
#else /* non gcc */
# define BLI_LINKSTACK_PUSH(var, ptr) (BLI_linklist_prepend_pool(&(var), ptr, var##_pool_))
# define BLI_LINKSTACK_POP(var) (var ? BLI_linklist_pop_pool(&(var), var##_pool_) : NULL)
# define BLI_LINKSTACK_POP_DEFAULT(var, r) (var ? BLI_linklist_pop_pool(&(var), var##_pool_) : r)
#endif /* gcc check */
#define BLI_LINKSTACK_SWAP(var_a, var_b) \
{ \
CHECK_TYPE_PAIR(var_a##_type_, var_b##_type_); \
SWAP(LinkNode *, var_a, var_b); \
SWAP(BLI_mempool *, var_a##_pool_, var_b##_pool_); \
} \
(void)0
#define BLI_LINKSTACK_FREE(var) \
{ \
BLI_mempool_destroy(var##_pool_); \
var##_pool_ = NULL; \
(void)var##_pool_; \
var = NULL; \
(void)var; \
(void)&(var##_type_); \
} \
(void)0
#include "BLI_linklist.h"
#include "BLI_mempool.h"
/** \} */
/* -------------------------------------------------------------------- */
/** \name Linked Stack (alloca)
*
* Linked Stack, using stack memory (alloca).
*
* alloca never frees, pop'd items are stored in a free-list for reuse.
* only use for lists small enough to fit on the stack.
* \{ */
#ifdef __GNUC__
# define _BLI_SMALLSTACK_CAST(var) (typeof(_##var##_type))
#else
# define _BLI_SMALLSTACK_CAST(var)
#endif
#define _BLI_SMALLSTACK_FAKEUSER(var) (void)(&(_##var##_type))
#define BLI_SMALLSTACK_DECLARE(var, type) \
LinkNode *_##var##_stack = NULL, *_##var##_free = NULL, *_##var##_temp = NULL; \
type _##var##_type
#define BLI_SMALLSTACK_PUSH(var, data) \
{ \
CHECK_TYPE_PAIR(data, _##var##_type); \
if (_##var##_free) { \
_##var##_temp = _##var##_free; \
_##var##_free = _##var##_free->next; \
} \
else { \
_##var##_temp = (LinkNode *)alloca(sizeof(LinkNode)); \
} \
_##var##_temp->next = _##var##_stack; \
_##var##_temp->link = data; \
_##var##_stack = _##var##_temp; \
_BLI_SMALLSTACK_FAKEUSER(var); \
} \
(void)0
/* internal use, no null check */
#define _BLI_SMALLSTACK_DEL_EX(var_src, var_dst) \
(void)(_BLI_SMALLSTACK_FAKEUSER(var_src), \
_BLI_SMALLSTACK_FAKEUSER(var_dst), \
(_##var_src##_temp = _##var_src##_stack->next), \
(_##var_src##_stack->next = _##var_dst##_free), \
(_##var_dst##_free = _##var_src##_stack), \
(_##var_src##_stack = _##var_src##_temp))
#define _BLI_SMALLSTACK_DEL(var) _BLI_SMALLSTACK_DEL_EX(var, var)
/* check for typeof() */
#define BLI_SMALLSTACK_POP(var) \
(_BLI_SMALLSTACK_CAST(var)( \
(_##var##_stack) ? (_BLI_SMALLSTACK_DEL(var), (_##var##_free->link)) : NULL))
/* support to put the free-node into another stack */
#define BLI_SMALLSTACK_POP_EX(var_src, var_dst) \
(_BLI_SMALLSTACK_CAST(var_src)( \
(_##var_src##_stack) ? \
(_BLI_SMALLSTACK_DEL_EX(var_src, var_dst), (_##var_dst##_free->link)) : \
NULL))
#define BLI_SMALLSTACK_PEEK(var) \
(_BLI_SMALLSTACK_CAST(var)((_##var##_stack) ? _##var##_stack->link : NULL))
#define BLI_SMALLSTACK_IS_EMPTY(var) ((_BLI_SMALLSTACK_CAST(var) _##var##_stack) == NULL)
/* fill in a lookup table */
#define BLI_SMALLSTACK_AS_TABLE(var, data) \
{ \
LinkNode *_##var##_iter; \
unsigned int i; \
for (_##var##_iter = _##var##_stack, i = 0; _##var##_iter; \
_##var##_iter = _##var##_iter->next, i++) { \
(data)[i] = _BLI_SMALLSTACK_CAST(var)(_##var##_iter->link); \
} \
} \
((void)0)
/* loop over stack members last-added-first */
#define BLI_SMALLSTACK_ITER_BEGIN(var, item) \
{ \
LinkNode *_##var##_iter; \
for (_##var##_iter = _##var##_stack; _##var##_iter; _##var##_iter = _##var##_iter->next) { \
item = _BLI_SMALLSTACK_CAST(var)(_##var##_iter->link);
#define BLI_SMALLSTACK_ITER_END \
} \
} \
(void)0
#define BLI_SMALLSTACK_SWAP(var_a, var_b) \
{ \
CHECK_TYPE_PAIR(_##var_a##_type, _##var_b##_type); \
SWAP(LinkNode *, _##var_a##_stack, _##var_b##_stack); \
SWAP(LinkNode *, _##var_a##_free, _##var_b##_free); \
} \
(void)0
/** \} */
|
