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