BLI_stack: various small additions
[blender.git] / source / blender / blenlib / intern / stack.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (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, write to the Free Software  Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * Contributor(s): Nicholas Bishop
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  *
22  */
23
24 /** \file blender/blenlib/intern/stack.c
25  *  \ingroup bli
26  */
27
28 #include <string.h>
29 #include <stdlib.h>  /* abort() */
30
31 #include "BLI_utildefines.h"
32 #include "MEM_guardedalloc.h"
33
34 #include "BLI_stack.h"  /* own include */
35
36 #include "BLI_strict_flags.h"
37
38 #define USE_TOTELEM
39
40 #define CHUNK_EMPTY ((size_t)-1)
41 /* target chunks size: 64kb */
42 #define CHUNK_SIZE_DEFAULT (1 << 16)
43 /* ensure we get at least this many elems per chunk */
44 #define CHUNK_ELEM_MIN     32
45
46 /* Gets the last element in the stack */
47 #define CHUNK_LAST_ELEM(_stack) \
48         ((void)0, (((char *)(_stack)->chunk_curr->data) + \
49                    ((_stack)->elem_size * (_stack)->chunk_index)))
50
51 #define IS_POW2(a) (((a) & ((a) - 1)) == 0)
52
53 struct StackChunk {
54         struct StackChunk *next;
55         char data[0];
56 };
57
58 struct BLI_Stack {
59         struct StackChunk *chunk_curr;      /* currently active chunk */
60         struct StackChunk *chunk_free;      /* free chunks */
61         size_t             chunk_index;     /* index into 'chunk_curr' */
62         size_t             chunk_elem_max;  /* number of elements per chunk */
63         size_t elem_size;
64 #ifdef USE_TOTELEM
65         size_t totelem;
66 #endif
67 };
68
69 /**
70  * \return number of elements per chunk, optimized for slop-space.
71  */
72 static size_t stack_chunk_elem_max_calc(const size_t elem_size, size_t chunk_size)
73 {
74         /* get at least this number of elems per chunk */
75         const size_t elem_size_min = elem_size * CHUNK_ELEM_MIN;
76
77         BLI_assert((elem_size != 0) && (chunk_size != 0));
78
79         while (UNLIKELY(chunk_size <= elem_size_min)) {
80                 chunk_size <<= 1;
81         }
82
83         /* account for slop-space */
84         chunk_size -= (sizeof(struct StackChunk) + MEM_SIZE_OVERHEAD);
85
86         return chunk_size / elem_size;
87 }
88
89 BLI_Stack *BLI_stack_new_ex(const size_t elem_size, const char *description,
90                             const size_t chunk_size)
91 {
92         BLI_Stack *stack = MEM_callocN(sizeof(*stack), description);
93
94         stack->chunk_elem_max = stack_chunk_elem_max_calc(elem_size, chunk_size);
95         stack->elem_size = elem_size;
96         /* force init */
97         stack->chunk_index = stack->chunk_elem_max - 1;
98
99         /* ensure we have a correctly rounded size */
100         BLI_assert((IS_POW2(stack->elem_size) == 0) ||
101                    (IS_POW2((stack->chunk_elem_max * stack->elem_size) +
102                             (sizeof(struct StackChunk) + MEM_SIZE_OVERHEAD))));
103
104         return stack;
105 }
106
107 /**
108  * Create a new homogeneous stack with elements of 'elem_size' bytes.
109  */
110 BLI_Stack *BLI_stack_new(const size_t elem_size, const char *description)
111 {
112         return BLI_stack_new_ex(elem_size, description, CHUNK_SIZE_DEFAULT);
113 }
114
115 static void stack_free_chunks(struct StackChunk *data)
116 {
117         while (data) {
118                 struct StackChunk *data_next = data->next;
119                 MEM_freeN(data);
120                 data = data_next;
121         }
122 }
123
124 /**
125  * Free the stack's data and the stack itself
126  */
127 void BLI_stack_free(BLI_Stack *stack)
128 {
129         stack_free_chunks(stack->chunk_curr);
130         stack_free_chunks(stack->chunk_free);
131         MEM_freeN(stack);
132 }
133
134 /**
135  * Copies the source value onto the stack (note that it copies
136  * elem_size bytes from 'src', the pointer itself is not stored)
137  */
138 void *BLI_stack_push_r(BLI_Stack *stack)
139 {
140         stack->chunk_index++;
141
142         if (UNLIKELY(stack->chunk_index == stack->chunk_elem_max)) {
143                 struct StackChunk *chunk;
144                 if (stack->chunk_free) {
145                         chunk = stack->chunk_free;
146                         stack->chunk_free = chunk->next;
147                 }
148                 else {
149                         chunk = MEM_mallocN(
150                                 sizeof(*chunk) + (stack->elem_size * stack->chunk_elem_max),
151                                 __func__);
152                 }
153                 chunk->next = stack->chunk_curr;
154                 stack->chunk_curr = chunk;
155                 stack->chunk_index = 0;
156         }
157
158         BLI_assert(stack->chunk_index < stack->chunk_elem_max);
159
160 #ifdef USE_TOTELEM
161         stack->totelem++;
162 #endif
163
164         /* Return end of stack */
165         return CHUNK_LAST_ELEM(stack);
166 }
167
168 void BLI_stack_push(BLI_Stack *stack, const void *src)
169 {
170         void *dst = BLI_stack_push_r(stack);
171         memcpy(dst, src, stack->elem_size);
172 }
173
174 /**
175  * Retrieves and removes the top element from the stack.
176  * The value is copies to \a dst, which must be at least \a elem_size bytes.
177  *
178  * Does not reduce amount of allocated memory.
179  */
180 void BLI_stack_pop(BLI_Stack *stack, void *dst)
181 {
182         BLI_assert(BLI_stack_is_empty(stack) == false);
183
184         memcpy(dst, CHUNK_LAST_ELEM(stack), stack->elem_size);
185 #ifdef USE_TOTELEM
186         stack->totelem--;
187 #endif
188         if (--stack->chunk_index == CHUNK_EMPTY) {
189                 struct StackChunk *chunk_free;
190
191                 chunk_free        = stack->chunk_curr;
192                 stack->chunk_curr = stack->chunk_curr->next;
193
194                 chunk_free->next  = stack->chunk_free;
195                 stack->chunk_free = chunk_free;
196
197                 stack->chunk_index = stack->chunk_elem_max - 1;
198         }
199 }
200
201 void BLI_stack_pop_n(BLI_Stack *stack, void *dst, unsigned int n)
202 {
203         BLI_assert(n <= BLI_stack_count(stack));
204
205         while (n--) {
206                 BLI_stack_pop(stack, dst);
207                 dst = (void *)((char *)dst + stack->elem_size);
208         }
209 }
210
211 size_t BLI_stack_count(const BLI_Stack *stack)
212 {
213 #ifdef USE_TOTELEM
214         return stack->totelem;
215 #else
216         struct StackChunk *data = stack->chunk_curr;
217         size_t totelem = stack->chunk_index + 1;
218         size_t i;
219         if (totelem != stack->chunk_elem_max) {
220                 data = data->next;
221         }
222         else {
223                 totelem = 0;
224         }
225         for (i = 0; data; data = data->next) {
226                 i++;
227         }
228         totelem += stack->chunk_elem_max * i;
229         return totelem;
230 #endif
231 }
232
233 /**
234  * Returns true if the stack is empty, false otherwise
235  */
236 bool BLI_stack_is_empty(const BLI_Stack *stack)
237 {
238 #ifdef USE_TOTELEM
239         BLI_assert((stack->chunk_curr == NULL) == (stack->totelem == 0));
240 #endif
241         return (stack->chunk_curr == NULL);
242 }