Blender V5.3
stack.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include <cstdlib> /* abort() */
10#include <cstring>
11
12#include "BLI_utildefines.hh"
13#include "MEM_guardedalloc.h"
14
15#include "BLI_stack_c.hh" /* own include */
16
17#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
18
19namespace blender {
20
21#define USE_TOTELEM
22
23#define CHUNK_EMPTY size_t(-1)
24/* target chunks size: 64kb */
25#define CHUNK_SIZE_DEFAULT (1 << 16)
26/* ensure we get at least this many elems per chunk */
27#define CHUNK_ELEM_MIN 32
28
29struct StackChunk {
31 char data[0];
32};
33
34struct BLI_Stack {
35 StackChunk *chunk_curr; /* currently active chunk */
36 StackChunk *chunk_free; /* free chunks */
37 size_t chunk_index; /* index into 'chunk_curr' */
38 size_t chunk_elem_max; /* number of elements per chunk */
39 size_t elem_size;
40#ifdef USE_TOTELEM
41 size_t elem_num;
42#endif
43};
44
45static void *stack_get_last_elem(BLI_Stack *stack)
46{
47 return (static_cast<char *>((stack)->chunk_curr->data)) +
48 ((stack)->elem_size * (stack)->chunk_index);
49}
50
54static size_t stack_chunk_elem_max_calc(const size_t elem_size, size_t chunk_size)
55{
56 /* get at least this number of elems per chunk */
57 const size_t elem_size_min = elem_size * CHUNK_ELEM_MIN;
58
59 BLI_assert((elem_size != 0) && (chunk_size != 0));
60
61 while (chunk_size <= elem_size_min) [[unlikely]] {
62 chunk_size <<= 1;
63 }
64
65 /* account for slop-space */
66 chunk_size -= (sizeof(StackChunk) + MEM_SIZE_OVERHEAD);
67
68 return chunk_size / elem_size;
69}
70
71BLI_Stack *BLI_stack_new_ex(const size_t elem_size,
72 const char *description,
73 const size_t chunk_size)
74{
75 BLI_Stack *stack = MEM_new_zeroed<BLI_Stack>(description);
76
77 stack->chunk_elem_max = stack_chunk_elem_max_calc(elem_size, chunk_size);
78 stack->elem_size = elem_size;
79 /* force init */
80 stack->chunk_index = stack->chunk_elem_max - 1;
81
82 return stack;
83}
84
85BLI_Stack *BLI_stack_new(const size_t elem_size, const char *description)
86{
87 return BLI_stack_new_ex(elem_size, description, CHUNK_SIZE_DEFAULT);
88}
89
91{
92 while (data) {
93 StackChunk *data_next = data->next;
94 MEM_delete(data);
95 data = data_next;
96 }
97}
98
100{
103 MEM_delete(stack);
104}
105
107{
108 stack->chunk_index++;
109
110 if (stack->chunk_index == stack->chunk_elem_max) [[unlikely]] {
111 StackChunk *chunk;
112 if (stack->chunk_free) {
113 chunk = stack->chunk_free;
114 stack->chunk_free = chunk->next;
115 }
116 else {
117 chunk = static_cast<StackChunk *>(MEM_new_uninitialized(
118 sizeof(*chunk) + (stack->elem_size * stack->chunk_elem_max), __func__));
119 }
120 chunk->next = stack->chunk_curr;
121 stack->chunk_curr = chunk;
122 stack->chunk_index = 0;
123 }
124
125 BLI_assert(stack->chunk_index < stack->chunk_elem_max);
126
127#ifdef USE_TOTELEM
128 stack->elem_num++;
129#endif
130
131 /* Return end of stack */
132 return stack_get_last_elem(stack);
133}
134
135void BLI_stack_push(BLI_Stack *stack, const void *src)
136{
137 void *dst = BLI_stack_push_r(stack);
138 memcpy(dst, src, stack->elem_size);
139}
140
141void BLI_stack_pop(BLI_Stack *stack, void *dst)
142{
143 BLI_assert(BLI_stack_is_empty(stack) == false);
144
145 memcpy(dst, stack_get_last_elem(stack), stack->elem_size);
146
147 BLI_stack_discard(stack);
148}
149
150void BLI_stack_pop_n(BLI_Stack *stack, void *dst, uint n)
151{
152 BLI_assert(n <= BLI_stack_count(stack));
153
154 while (n--) {
155 BLI_stack_pop(stack, dst);
156 dst = static_cast<void *>(static_cast<char *>(dst) + stack->elem_size);
157 }
158}
159
160void BLI_stack_pop_n_reverse(BLI_Stack *stack, void *dst, uint n)
161{
162 BLI_assert(n <= BLI_stack_count(stack));
163
164 dst = static_cast<void *>(static_cast<char *>(dst) + (stack->elem_size * n));
165
166 while (n--) {
167 dst = static_cast<void *>(static_cast<char *>(dst) - stack->elem_size);
168 BLI_stack_pop(stack, dst);
169 }
170}
171
173{
174 BLI_assert(BLI_stack_is_empty(stack) == false);
175
176 return stack_get_last_elem(stack);
177}
178
180{
181 BLI_assert(BLI_stack_is_empty(stack) == false);
182
183#ifdef USE_TOTELEM
184 stack->elem_num--;
185#endif
186 if (--stack->chunk_index == CHUNK_EMPTY) [[unlikely]] {
187 StackChunk *chunk_free;
188
189 chunk_free = stack->chunk_curr;
190 stack->chunk_curr = stack->chunk_curr->next;
191
192 chunk_free->next = stack->chunk_free;
193 stack->chunk_free = chunk_free;
194
195 stack->chunk_index = stack->chunk_elem_max - 1;
196 }
197}
198
200{
201#ifdef USE_TOTELEM
202 if (stack->elem_num == 0) [[unlikely]] {
203 return;
204 }
205 stack->elem_num = 0;
206#else
207 if (stack->chunk_curr == nullptr) [[unlikely]] {
208 return;
209 }
210#endif
211
212 stack->chunk_index = stack->chunk_elem_max - 1;
213
214 if (stack->chunk_free) {
215 if (stack->chunk_curr) {
216 /* move all used chunks into tail of free list */
217 StackChunk *chunk_free_last = stack->chunk_free;
218 while (chunk_free_last->next) {
219 chunk_free_last = chunk_free_last->next;
220 }
221 chunk_free_last->next = stack->chunk_curr;
222 stack->chunk_curr = nullptr;
223 }
224 }
225 else {
226 stack->chunk_free = stack->chunk_curr;
227 stack->chunk_curr = nullptr;
228 }
229}
230
231size_t BLI_stack_count(const BLI_Stack *stack)
232{
233#ifdef USE_TOTELEM
234 return stack->elem_num;
235#else
236 StackChunk *data = stack->chunk_curr;
237 size_t elem_num = stack->chunk_index + 1;
238 size_t i;
239 if (elem_num != stack->chunk_elem_max) {
240 data = data->next;
241 }
242 else {
243 elem_num = 0;
244 }
245 for (i = 0; data; data = data->next) {
246 i++;
247 }
248 elem_num += stack->chunk_elem_max * i;
249 return elem_num;
250#endif
251}
252
254{
255#ifdef USE_TOTELEM
256 BLI_assert((stack->chunk_curr == nullptr) == (stack->elem_num == 0));
257#endif
258 return (stack->chunk_curr == nullptr);
259}
260
261} // namespace blender
Read Blender memory allocation and freeing.
#define MEM_SIZE_OVERHEAD
#define CHUNK_ELEM_MIN
Definition gsqueue.cc:26
#define CHUNK_SIZE_DEFAULT
Definition gsqueue.cc:24
BMesh Iterators.
void * MEM_new_uninitialized(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void BLI_stack_clear(BLI_Stack *stack) ATTR_NONNULL()
Definition stack.cc:199
bool BLI_stack_is_empty(const BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition stack.cc:253
unsigned int uint
Definition BKE_text.h:55
void BLI_stack_free(BLI_Stack *stack) ATTR_NONNULL()
Definition stack.cc:99
void BLI_stack_pop(BLI_Stack *stack, void *dst) ATTR_NONNULL()
Definition stack.cc:141
static void * stack_get_last_elem(BLI_Stack *stack)
Definition stack.cc:45
void BLI_stack_discard(BLI_Stack *stack) ATTR_NONNULL()
Definition stack.cc:179
void * BLI_stack_push_r(BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition stack.cc:106
void * MEM_new_zeroed(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
static void stack_free_chunks(StackChunk *data)
Definition stack.cc:90
size_t BLI_stack_count(const BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition stack.cc:231
BMesh const char void * data
BLI_Stack * BLI_stack_new_ex(size_t elem_size, const char *description, size_t chunk_size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition stack.cc:71
void * BLI_stack_peek(BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition stack.cc:172
void BLI_stack_pop_n_reverse(BLI_Stack *stack, void *dst, unsigned int n) ATTR_NONNULL()
Definition stack.cc:160
static size_t stack_chunk_elem_max_calc(const size_t elem_size, size_t chunk_size)
Definition stack.cc:54
void BLI_stack_push(BLI_Stack *stack, const void *src) ATTR_NONNULL()
Definition stack.cc:135
void BLI_stack_pop_n(BLI_Stack *stack, void *dst, unsigned int n) ATTR_NONNULL()
Definition stack.cc:150
BLI_Stack * BLI_stack_new(size_t elem_size, const char *description) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition stack.cc:85
#define CHUNK_EMPTY
Definition stack.cc:23
size_t elem_num
Definition stack.cc:41
StackChunk * chunk_free
Definition stack.cc:36
size_t chunk_index
Definition stack.cc:37
StackChunk * chunk_curr
Definition stack.cc:35
size_t elem_size
Definition stack.cc:39
size_t chunk_elem_max
Definition stack.cc:38
StackChunk * next
Definition stack.cc:30