Cleanup: remove redundant doxygen \file argument
[blender.git] / source / blender / blenlib / intern / BLI_memiter.c
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
17 /** \file \ingroup bli
18  *
19  * Simple, fast memory allocator for allocating many small elements of different sizes
20  * in fixed size memory chunks,
21  * although allocations bigger than the chunk size are supported.
22  * They will reduce the efficiency of this data-structure.
23  * Elements are pointer aligned.
24  *
25  * Supports:
26  *
27  * - Allocation of mixed sizes.
28  * - Iterating over allocations in-order.
29  * - Clearing for re-use.
30  *
31  * Unsupported:
32  *
33  * - Freeing individual elements.
34  *
35  * \note We could inline iteration stepping,
36  * but tests show this doesn't give noticeable speedup.
37  */
38
39 #include <string.h>
40 #include <stdlib.h>
41
42 #include "BLI_utildefines.h"
43
44 #include "BLI_memiter.h" /* own include */
45
46 #include "MEM_guardedalloc.h"
47
48 #include "BLI_strict_flags.h" /* keep last */
49
50 typedef uintptr_t data_t;
51 typedef intptr_t offset_t;
52
53 /* Write the chunk terminator on adding each element.
54  * typically we rely on the 'count' to avoid iterating past the end. */
55 // #define USE_TERMINATE_PARANOID
56
57 /* Currently totalloc isnt used. */
58  // #define USE_TOTALLOC
59
60 /* pad must be power of two */
61 #define PADUP(num, pad) (((num) + ((pad) - 1)) & ~((pad) - 1))
62
63 typedef struct BLI_memiter_elem {
64         offset_t size;
65         data_t data[0];
66 } BLI_memiter_elem;
67
68 typedef struct BLI_memiter_chunk {
69         struct BLI_memiter_chunk *next;
70         /**
71          * internal format is:
72          * ``[next_pointer, size:data, size:data, ..., negative_offset]``
73          *
74          * Where negative offset rewinds to the start.
75          */
76         data_t data[0];
77 } BLI_memiter_chunk;
78
79 typedef struct BLI_memiter {
80         /* A pointer to 'head' is needed so we can iterate in the order allocated. */
81         struct BLI_memiter_chunk *head, *tail;
82         data_t *data_curr;
83         data_t *data_last;
84         /* Used unless a large element is requested.
85          * (which should be very rare!). */
86         uint chunk_size_in_bytes_min;
87         uint count;
88 #ifdef USE_TOTALLOC
89         uint totalloc;
90 #endif
91 } BLI_memiter;
92
93
94 BLI_INLINE uint data_offset_from_size(uint size)
95 {
96         return (PADUP(size, (uint)sizeof(data_t))) / (uint)sizeof(data_t);
97 }
98
99 static void memiter_set_rewind_offset(BLI_memiter *mi)
100 {
101         BLI_memiter_elem *elem = (BLI_memiter_elem *)mi->data_curr;
102         elem->size = (offset_t)(((data_t *)mi->tail) - mi->data_curr);
103         BLI_assert(elem->size < 0);
104 }
105
106 static void memiter_init(BLI_memiter *mi)
107 {
108         mi->head = NULL;
109         mi->tail = NULL;
110         mi->data_curr = NULL;
111         mi->data_last = NULL;
112         mi->count = 0;
113 #ifdef USE_TOTALLOC
114         mi->totalloc = 0;
115 #endif
116 }
117
118 /* -------------------------------------------------------------------- */
119 /** \name Public API's
120  * \{ */
121
122 /**
123  * \param chunk_size_min: Should be a power of two and
124  * significantly larger than the average element size used.
125  *
126  * While allocations of any size are supported, they won't be efficient
127  * (effectively becoming a single-linked list).
128  *
129  * Its intended that many elements can be stored per chunk.
130  */
131 BLI_memiter *BLI_memiter_create(uint chunk_size_min)
132 {
133         BLI_memiter *mi = MEM_mallocN(sizeof(BLI_memiter), "BLI_memiter");
134         memiter_init(mi);
135
136         /* Small values are used for tests to check for correctness,
137          * but otherwise not that useful. */
138         const uint slop_space = (sizeof(BLI_memiter_chunk) + MEM_SIZE_OVERHEAD);
139         if (chunk_size_min >= 1024) {
140                 /* As long as the input is a power of 2, this will give efficient sizes. */
141                 chunk_size_min -= slop_space;
142         }
143
144         mi->chunk_size_in_bytes_min = chunk_size_min;
145         return mi;
146 }
147
148 void *BLI_memiter_alloc(BLI_memiter *mi, uint elem_size)
149 {
150         const uint data_offset = data_offset_from_size(elem_size);
151         data_t *data_curr_next = mi->data_curr + (1 + data_offset);
152
153         if (UNLIKELY(mi->data_curr == NULL) || (data_curr_next > mi->data_last)) {
154
155 #ifndef USE_TERMINATE_PARANOID
156                 if (mi->data_curr != NULL) {
157                         memiter_set_rewind_offset(mi);
158                 }
159 #endif
160
161                 uint chunk_size_in_bytes = mi->chunk_size_in_bytes_min;
162                 if (UNLIKELY(chunk_size_in_bytes < elem_size + (uint)sizeof(data_t[2]))) {
163                         chunk_size_in_bytes = elem_size + (uint)sizeof(data_t[2]);
164                 }
165                 uint chunk_size = data_offset_from_size(chunk_size_in_bytes);
166                 BLI_memiter_chunk *chunk = MEM_mallocN(
167                         sizeof(BLI_memiter_chunk) +
168                         (chunk_size * sizeof(data_t)),
169                         "BLI_memiter_chunk");
170
171                 if (mi->head == NULL) {
172                         BLI_assert(mi->tail == NULL);
173                         mi->head = chunk;
174                 }
175                 else {
176                         mi->tail->next = chunk;
177                 }
178                 mi->tail = chunk;
179                 chunk->next = NULL;
180
181                 mi->data_curr = chunk->data;
182                 mi->data_last = chunk->data + (chunk_size - 1);
183                 data_curr_next = mi->data_curr + (1 + data_offset);
184         }
185
186         BLI_assert(data_curr_next <= mi->data_last);
187
188         BLI_memiter_elem *elem      = (BLI_memiter_elem *)mi->data_curr;
189         elem->size = (offset_t)elem_size;
190         mi->data_curr = data_curr_next;
191
192 #ifdef USE_TERMINATE_PARANOID
193         memiter_set_rewind_offset(mi);
194 #endif
195
196         mi->count += 1;
197
198 #ifdef USE_TOTALLOC
199         mi->totalloc += elem_size;
200 #endif
201
202         return elem->data;
203 }
204
205 void *BLI_memiter_calloc(BLI_memiter *mi, uint elem_size)
206 {
207         void *data = BLI_memiter_alloc(mi, elem_size);
208         memset(data, 0, elem_size);
209         return data;
210 }
211
212 void BLI_memiter_alloc_from(BLI_memiter *mi, uint elem_size, const void *data_from)
213 {
214         void *data = BLI_memiter_alloc(mi, elem_size);
215         memcpy(data, data_from, elem_size);
216 }
217
218 static void memiter_free_data(BLI_memiter *mi)
219 {
220         BLI_memiter_chunk *chunk = mi->head;
221         while (chunk) {
222                 BLI_memiter_chunk *chunk_next = chunk->next;
223                 MEM_freeN(chunk);
224                 chunk = chunk_next;
225         }
226 }
227
228 void BLI_memiter_destroy(BLI_memiter *mi)
229 {
230         memiter_free_data(mi);
231         MEM_freeN(mi);
232 }
233
234 void BLI_memiter_clear(BLI_memiter *mi)
235 {
236         memiter_free_data(mi);
237         memiter_init(mi);
238 }
239
240 uint BLI_memiter_count(const BLI_memiter *mi)
241 {
242         return mi->count;
243 }
244
245 /** \} */
246
247
248 /* -------------------------------------------------------------------- */
249 /** \name Helper API's
250  * \{ */
251
252 /* Support direct lookup for first. */
253 void *BLI_memiter_elem_first(BLI_memiter *mi)
254 {
255         if (mi->head != NULL) {
256                 BLI_memiter_chunk *chunk = mi->head;
257                 BLI_memiter_elem *elem = (BLI_memiter_elem *)chunk->data;
258                 return elem->data;
259         }
260         else {
261                 return NULL;
262         }
263 }
264
265 void *BLI_memiter_elem_first_size(BLI_memiter *mi, uint *r_size)
266 {
267         if (mi->head != NULL) {
268                 BLI_memiter_chunk *chunk = mi->head;
269                 BLI_memiter_elem *elem = (BLI_memiter_elem *)chunk->data;
270                 *r_size = (uint)elem->size;
271                 return elem->data;
272         }
273         else {
274                 return NULL;
275         }
276 }
277
278 /** \} */
279
280
281 /* -------------------------------------------------------------------- */
282 /** \name Iterator API's
283  *
284  * \note We could loop over elements until a NULL chunk is found,
285  * however this means every allocation needs to preemptively run
286  * #memiter_set_rewind_offset (see #USE_TERMINATE_PARANOID).
287  * Unless we have a call to finalize allocation (which complicates usage).
288  * So use a counter instead.
289  *
290  * \{ */
291
292 void BLI_memiter_iter_init(BLI_memiter *mi, BLI_memiter_handle *iter)
293 {
294         iter->elem = mi->head ? (BLI_memiter_elem *)mi->head->data : NULL;
295         iter->elem_left = mi->count;
296 }
297
298 bool BLI_memiter_iter_done(const BLI_memiter_handle *iter)
299 {
300         return iter->elem_left != 0;
301 }
302
303 BLI_INLINE void memiter_chunk_step(BLI_memiter_handle *iter)
304 {
305         BLI_assert(iter->elem->size < 0);
306         BLI_memiter_chunk *chunk = (BLI_memiter_chunk *)(((data_t *)iter->elem) + iter->elem->size);
307         chunk = chunk->next;
308         iter->elem = chunk ? (BLI_memiter_elem *)chunk->data : NULL;
309         BLI_assert(iter->elem == NULL || iter->elem->size >= 0);
310 }
311
312 void *BLI_memiter_iter_step_size(BLI_memiter_handle *iter, uint *r_size)
313 {
314         if (iter->elem_left != 0) {
315                 iter->elem_left -= 1;
316                 if (UNLIKELY(iter->elem->size < 0)) {
317                         memiter_chunk_step(iter);
318                 }
319                 BLI_assert(iter->elem->size >= 0);
320                 uint size = (uint)iter->elem->size;
321                 *r_size = size;  /* <-- only difference */
322                 data_t *data = iter->elem->data;
323                 iter->elem = (BLI_memiter_elem *)&data[data_offset_from_size(size)];
324                 return (void *)data;
325         }
326         else {
327                 return NULL;
328         }
329 }
330
331 void *BLI_memiter_iter_step(BLI_memiter_handle *iter)
332 {
333         if (iter->elem_left != 0) {
334                 iter->elem_left -= 1;
335                 if (UNLIKELY(iter->elem->size < 0)) {
336                         memiter_chunk_step(iter);
337                 }
338                 BLI_assert(iter->elem->size >= 0);
339                 uint size = (uint)iter->elem->size;
340                 data_t *data = iter->elem->data;
341                 iter->elem = (BLI_memiter_elem *)&data[data_offset_from_size(size)];
342                 return (void *)data;
343         }
344         else {
345                 return NULL;
346         }
347 }
348
349 /** \} */