Cleanup: remove redundant doxygen \file argument
[blender.git] / source / blender / blenlib / intern / BLI_mempool.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  * The Original Code is Copyright (C) 2008 by Blender Foundation.
17  * All rights reserved.
18  */
19
20 /** \file \ingroup bli
21  *
22  * Simple, fast memory allocator for allocating many elements of the same size.
23  *
24  * Supports:
25  *
26  * - Freeing chunks.
27  * - Iterating over allocated chunks
28  *   (optionally when using the #BLI_MEMPOOL_ALLOW_ITER flag).
29  */
30
31 #include <string.h>
32 #include <stdlib.h>
33
34 #include "atomic_ops.h"
35
36 #include "BLI_utildefines.h"
37
38 #include "BLI_mempool.h" /* own include */
39
40 #include "MEM_guardedalloc.h"
41
42 #include "BLI_strict_flags.h"  /* keep last */
43
44 #ifdef WITH_MEM_VALGRIND
45 #  include "valgrind/memcheck.h"
46 #endif
47
48 /* note: copied from BLO_blend_defs.h, don't use here because we're in BLI */
49 #ifdef __BIG_ENDIAN__
50 /* Big Endian */
51 #  define MAKE_ID(a, b, c, d) ( (int)(a) << 24 | (int)(b) << 16 | (c) << 8 | (d) )
52 #  define MAKE_ID_8(a, b, c, d, e, f, g, h) \
53         ((int64_t)(a) << 56 | (int64_t)(b) << 48 | (int64_t)(c) << 40 | (int64_t)(d) << 32 | \
54          (int64_t)(e) << 24 | (int64_t)(f) << 16 | (int64_t)(g) <<  8 | (h) )
55 #else
56 /* Little Endian */
57 #  define MAKE_ID(a, b, c, d) ( (int)(d) << 24 | (int)(c) << 16 | (b) << 8 | (a) )
58 #  define MAKE_ID_8(a, b, c, d, e, f, g, h) \
59         ((int64_t)(h) << 56 | (int64_t)(g) << 48 | (int64_t)(f) << 40 | (int64_t)(e) << 32 | \
60          (int64_t)(d) << 24 | (int64_t)(c) << 16 | (int64_t)(b) <<  8 | (a) )
61 #endif
62
63 /**
64  * Important that this value is an is _not_  aligned with ``sizeof(void *)``.
65  * So having a pointer to 2/4/8... aligned memory is enough to ensure the freeword will never be used.
66  * To be safe, use a word thats the same in both directions.
67  */
68 #define FREEWORD ((sizeof(void *) > sizeof(int32_t)) ? \
69         MAKE_ID_8('e', 'e', 'r', 'f', 'f', 'r', 'e', 'e') : \
70           MAKE_ID('e',           'f', 'f',           'e'))
71
72 /**
73  * The 'used' word just needs to be set to something besides FREEWORD.
74  */
75 #define USEDWORD MAKE_ID('u', 's', 'e', 'd')
76
77 /* currently totalloc isnt used */
78 // #define USE_TOTALLOC
79
80 /* when undefined, merge the allocs for BLI_mempool_chunk and its data */
81 // #define USE_DATA_PTR
82
83 /* optimize pool size */
84 #define USE_CHUNK_POW2
85
86
87 #ifndef NDEBUG
88 static bool mempool_debug_memset = false;
89 #endif
90
91 /**
92  * A free element from #BLI_mempool_chunk. Data is cast to this type and stored in
93  * #BLI_mempool.free as a single linked list, each item #BLI_mempool.esize large.
94  *
95  * Each element represents a block which BLI_mempool_alloc may return.
96  */
97 typedef struct BLI_freenode {
98         struct BLI_freenode *next;
99         intptr_t freeword; /* used to identify this as a freed node */
100 } BLI_freenode;
101
102 /**
103  * A chunk of memory in the mempool stored in
104  * #BLI_mempool.chunks as a double linked list.
105  */
106 typedef struct BLI_mempool_chunk {
107         struct BLI_mempool_chunk *next;
108 #ifdef USE_DATA_PTR
109         void *_data;
110 #endif
111 } BLI_mempool_chunk;
112
113 /**
114  * The mempool, stores and tracks memory \a chunks and elements within those chunks \a free.
115  */
116 struct BLI_mempool {
117         BLI_mempool_chunk *chunks;  /* single linked list of allocated chunks */
118         /* keep a pointer to the last, so we can append new chunks there
119          * this is needed for iteration so we can loop over chunks in the order added */
120         BLI_mempool_chunk *chunk_tail;
121
122         uint esize;         /* element size in bytes */
123         uint csize;         /* chunk size in bytes */
124         uint pchunk;        /* number of elements per chunk */
125         uint flag;
126         /* keeps aligned to 16 bits */
127
128         BLI_freenode *free;         /* free element list. Interleaved into chunk datas. */
129         uint maxchunks;     /* use to know how many chunks to keep for BLI_mempool_clear */
130         uint totused;       /* number of elements currently in use */
131 #ifdef USE_TOTALLOC
132         uint totalloc;          /* number of elements allocated in total */
133 #endif
134 };
135
136 #define MEMPOOL_ELEM_SIZE_MIN (sizeof(void *) * 2)
137
138 #ifdef USE_DATA_PTR
139 #  define CHUNK_DATA(chunk) (chunk)->_data
140 #else
141 #  define CHUNK_DATA(chunk) (CHECK_TYPE_INLINE(chunk, BLI_mempool_chunk *), (void *)((chunk) + 1))
142 #endif
143
144 #define NODE_STEP_NEXT(node)  ((void *)((char *)(node) + esize))
145 #define NODE_STEP_PREV(node)  ((void *)((char *)(node) - esize))
146
147 /* extra bytes implicitly used for every chunk alloc */
148 #ifdef USE_DATA_PTR
149 #  define CHUNK_OVERHEAD (uint)(MEM_SIZE_OVERHEAD + sizeof(BLI_mempool_chunk))
150 #else
151 #  define CHUNK_OVERHEAD (uint)(MEM_SIZE_OVERHEAD)
152 #endif
153
154 #ifdef USE_CHUNK_POW2
155 static uint power_of_2_max_u(uint x)
156 {
157         x -= 1;
158         x = x | (x >> 1);
159         x = x | (x >> 2);
160         x = x | (x >> 4);
161         x = x | (x >> 8);
162         x = x | (x >> 16);
163         return x + 1;
164 }
165 #endif
166
167 BLI_INLINE BLI_mempool_chunk *mempool_chunk_find(BLI_mempool_chunk *head, uint index)
168 {
169         while (index-- && head) {
170                 head = head->next;
171         }
172         return head;
173 }
174
175 /**
176  * \return the number of chunks to allocate based on how many elements are needed.
177  *
178  * \note for small pools 1 is a good default, the elements need to be initialized,
179  * adding overhead on creation which is redundant if they aren't used.
180  */
181 BLI_INLINE uint mempool_maxchunks(const uint totelem, const uint pchunk)
182 {
183         return (totelem <= pchunk) ? 1 : ((totelem / pchunk) + 1);
184 }
185
186 static BLI_mempool_chunk *mempool_chunk_alloc(BLI_mempool *pool)
187 {
188         BLI_mempool_chunk *mpchunk;
189 #ifdef USE_DATA_PTR
190         mpchunk = MEM_mallocN(sizeof(BLI_mempool_chunk), "BLI_Mempool Chunk");
191         CHUNK_DATA(mpchunk) = MEM_mallocN((size_t)pool->csize, "BLI Mempool Chunk Data");
192 #else
193         mpchunk = MEM_mallocN(sizeof(BLI_mempool_chunk) + (size_t)pool->csize, "BLI_Mempool Chunk");
194 #endif
195
196         return mpchunk;
197 }
198
199 /**
200  * Initialize a chunk and add into \a pool->chunks
201  *
202  * \param pool: The pool to add the chunk into.
203  * \param mpchunk: The new uninitialized chunk (can be malloc'd)
204  * \param lasttail: The last element of the previous chunk
205  * (used when building free chunks initially)
206  * \return The last chunk,
207  */
208 static BLI_freenode *mempool_chunk_add(BLI_mempool *pool, BLI_mempool_chunk *mpchunk,
209                                        BLI_freenode *lasttail)
210 {
211         const uint esize = pool->esize;
212         BLI_freenode *curnode = CHUNK_DATA(mpchunk);
213         uint j;
214
215         /* append */
216         if (pool->chunk_tail) {
217                 pool->chunk_tail->next = mpchunk;
218         }
219         else {
220                 BLI_assert(pool->chunks == NULL);
221                 pool->chunks = mpchunk;
222         }
223
224         mpchunk->next = NULL;
225         pool->chunk_tail = mpchunk;
226
227         if (UNLIKELY(pool->free == NULL)) {
228                 pool->free = curnode;
229         }
230
231         /* loop through the allocated data, building the pointer structures */
232         j = pool->pchunk;
233         if (pool->flag & BLI_MEMPOOL_ALLOW_ITER) {
234                 while (j--) {
235                         curnode->next = NODE_STEP_NEXT(curnode);
236                         curnode->freeword = FREEWORD;
237                         curnode = curnode->next;
238                 }
239         }
240         else {
241                 while (j--) {
242                         curnode->next = NODE_STEP_NEXT(curnode);
243                         curnode = curnode->next;
244                 }
245         }
246
247         /* terminate the list (rewind one)
248          * will be overwritten if 'curnode' gets passed in again as 'lasttail' */
249         curnode = NODE_STEP_PREV(curnode);
250         curnode->next = NULL;
251
252 #ifdef USE_TOTALLOC
253         pool->totalloc += pool->pchunk;
254 #endif
255
256         /* final pointer in the previously allocated chunk is wrong */
257         if (lasttail) {
258                 lasttail->next = CHUNK_DATA(mpchunk);
259         }
260
261         return curnode;
262 }
263
264 static void mempool_chunk_free(BLI_mempool_chunk *mpchunk)
265 {
266
267 #ifdef USE_DATA_PTR
268         MEM_freeN(CHUNK_DATA(mpchunk));
269 #endif
270         MEM_freeN(mpchunk);
271 }
272
273 static void mempool_chunk_free_all(BLI_mempool_chunk *mpchunk)
274 {
275         BLI_mempool_chunk *mpchunk_next;
276
277         for (; mpchunk; mpchunk = mpchunk_next) {
278                 mpchunk_next = mpchunk->next;
279                 mempool_chunk_free(mpchunk);
280         }
281 }
282
283 BLI_mempool *BLI_mempool_create(uint esize, uint totelem,
284                                 uint pchunk, uint flag)
285 {
286         BLI_mempool *pool;
287         BLI_freenode *lasttail = NULL;
288         uint i, maxchunks;
289
290         /* allocate the pool structure */
291         pool = MEM_mallocN(sizeof(BLI_mempool), "memory pool");
292
293         /* set the elem size */
294         if (esize < (int)MEMPOOL_ELEM_SIZE_MIN) {
295                 esize = (int)MEMPOOL_ELEM_SIZE_MIN;
296         }
297
298         if (flag & BLI_MEMPOOL_ALLOW_ITER) {
299                 esize = MAX2(esize, (uint)sizeof(BLI_freenode));
300         }
301
302         maxchunks = mempool_maxchunks(totelem, pchunk);
303
304         pool->chunks = NULL;
305         pool->chunk_tail = NULL;
306         pool->esize = esize;
307         pool->csize = esize * pchunk;
308
309
310         /* Optimize chunk size to powers of 2, accounting for slop-space */
311 #ifdef USE_CHUNK_POW2
312         {
313                 BLI_assert(pool->csize > CHUNK_OVERHEAD);
314                 pool->csize = power_of_2_max_u(pool->csize) - CHUNK_OVERHEAD;
315                 pchunk = pool->csize / esize;
316         }
317 #endif
318
319
320         pool->pchunk = pchunk;
321         pool->flag = flag;
322         pool->free = NULL;  /* mempool_chunk_add assigns */
323         pool->maxchunks = maxchunks;
324 #ifdef USE_TOTALLOC
325         pool->totalloc = 0;
326 #endif
327         pool->totused = 0;
328
329         if (totelem) {
330                 /* allocate the actual chunks */
331                 for (i = 0; i < maxchunks; i++) {
332                         BLI_mempool_chunk *mpchunk = mempool_chunk_alloc(pool);
333                         lasttail = mempool_chunk_add(pool, mpchunk, lasttail);
334                 }
335         }
336
337 #ifdef WITH_MEM_VALGRIND
338         VALGRIND_CREATE_MEMPOOL(pool, 0, false);
339 #endif
340
341         return pool;
342 }
343
344 void *BLI_mempool_alloc(BLI_mempool *pool)
345 {
346         BLI_freenode *free_pop;
347
348         if (UNLIKELY(pool->free == NULL)) {
349                 /* need to allocate a new chunk */
350                 BLI_mempool_chunk *mpchunk = mempool_chunk_alloc(pool);
351                 mempool_chunk_add(pool, mpchunk, NULL);
352         }
353
354         free_pop = pool->free;
355
356         BLI_assert(pool->chunk_tail->next == NULL);
357
358         if (pool->flag & BLI_MEMPOOL_ALLOW_ITER) {
359                 free_pop->freeword = USEDWORD;
360         }
361
362         pool->free = free_pop->next;
363         pool->totused++;
364
365 #ifdef WITH_MEM_VALGRIND
366         VALGRIND_MEMPOOL_ALLOC(pool, free_pop, pool->esize);
367 #endif
368
369         return (void *)free_pop;
370 }
371
372 void *BLI_mempool_calloc(BLI_mempool *pool)
373 {
374         void *retval = BLI_mempool_alloc(pool);
375         memset(retval, 0, (size_t)pool->esize);
376         return retval;
377 }
378
379 /**
380  * Free an element from the mempool.
381  *
382  * \note doesnt protect against double frees, don't be stupid!
383  */
384 void BLI_mempool_free(BLI_mempool *pool, void *addr)
385 {
386         BLI_freenode *newhead = addr;
387
388 #ifndef NDEBUG
389         {
390                 BLI_mempool_chunk *chunk;
391                 bool found = false;
392                 for (chunk = pool->chunks; chunk; chunk = chunk->next) {
393                         if (ARRAY_HAS_ITEM((char *)addr, (char *)CHUNK_DATA(chunk), pool->csize)) {
394                                 found = true;
395                                 break;
396                         }
397                 }
398                 if (!found) {
399                         BLI_assert(!"Attempt to free data which is not in pool.\n");
400                 }
401         }
402
403         /* enable for debugging */
404         if (UNLIKELY(mempool_debug_memset)) {
405                 memset(addr, 255, pool->esize);
406         }
407 #endif
408
409         if (pool->flag & BLI_MEMPOOL_ALLOW_ITER) {
410 #ifndef NDEBUG
411                 /* this will detect double free's */
412                 BLI_assert(newhead->freeword != FREEWORD);
413 #endif
414                 newhead->freeword = FREEWORD;
415         }
416
417         newhead->next = pool->free;
418         pool->free = newhead;
419
420         pool->totused--;
421
422 #ifdef WITH_MEM_VALGRIND
423         VALGRIND_MEMPOOL_FREE(pool, addr);
424 #endif
425
426         /* nothing is in use; free all the chunks except the first */
427         if (UNLIKELY(pool->totused == 0) &&
428             (pool->chunks->next))
429         {
430                 const uint esize = pool->esize;
431                 BLI_freenode *curnode;
432                 uint j;
433                 BLI_mempool_chunk *first;
434
435                 first = pool->chunks;
436                 mempool_chunk_free_all(first->next);
437                 first->next = NULL;
438                 pool->chunk_tail = first;
439
440 #ifdef USE_TOTALLOC
441                 pool->totalloc = pool->pchunk;
442 #endif
443
444                 /* temp alloc so valgrind doesn't complain when setting free'd blocks 'next' */
445 #ifdef WITH_MEM_VALGRIND
446                 VALGRIND_MEMPOOL_ALLOC(pool, CHUNK_DATA(first), pool->csize);
447 #endif
448
449                 curnode = CHUNK_DATA(first);
450                 pool->free = curnode;
451
452                 j = pool->pchunk;
453                 while (j--) {
454                         curnode->next = NODE_STEP_NEXT(curnode);
455                         curnode = curnode->next;
456                 }
457                 curnode = NODE_STEP_PREV(curnode);
458                 curnode->next = NULL; /* terminate the list */
459
460 #ifdef WITH_MEM_VALGRIND
461                 VALGRIND_MEMPOOL_FREE(pool, CHUNK_DATA(first));
462 #endif
463         }
464 }
465
466 int BLI_mempool_len(BLI_mempool *pool)
467 {
468         return (int)pool->totused;
469 }
470
471 void *BLI_mempool_findelem(BLI_mempool *pool, uint index)
472 {
473         BLI_assert(pool->flag & BLI_MEMPOOL_ALLOW_ITER);
474
475         if (index < pool->totused) {
476                 /* we could have some faster mem chunk stepping code inline */
477                 BLI_mempool_iter iter;
478                 void *elem;
479                 BLI_mempool_iternew(pool, &iter);
480                 for (elem = BLI_mempool_iterstep(&iter); index-- != 0; elem = BLI_mempool_iterstep(&iter)) {
481                         /* do nothing */
482                 }
483                 return elem;
484         }
485
486         return NULL;
487 }
488
489 /**
490  * Fill in \a data with pointers to each element of the mempool,
491  * to create lookup table.
492  *
493  * \param pool: Pool to create a table from.
494  * \param data: array of pointers at least the size of 'pool->totused'
495  */
496 void BLI_mempool_as_table(BLI_mempool *pool, void **data)
497 {
498         BLI_mempool_iter iter;
499         void *elem;
500         void **p = data;
501         BLI_assert(pool->flag & BLI_MEMPOOL_ALLOW_ITER);
502         BLI_mempool_iternew(pool, &iter);
503         while ((elem = BLI_mempool_iterstep(&iter))) {
504                 *p++ = elem;
505         }
506         BLI_assert((uint)(p - data) == pool->totused);
507 }
508
509 /**
510  * A version of #BLI_mempool_as_table that allocates and returns the data.
511  */
512 void **BLI_mempool_as_tableN(BLI_mempool *pool, const char *allocstr)
513 {
514         void **data = MEM_mallocN((size_t)pool->totused * sizeof(void *), allocstr);
515         BLI_mempool_as_table(pool, data);
516         return data;
517 }
518
519 /**
520  * Fill in \a data with the contents of the mempool.
521  */
522 void BLI_mempool_as_array(BLI_mempool *pool, void *data)
523 {
524         const uint esize = pool->esize;
525         BLI_mempool_iter iter;
526         char *elem, *p = data;
527         BLI_assert(pool->flag & BLI_MEMPOOL_ALLOW_ITER);
528         BLI_mempool_iternew(pool, &iter);
529         while ((elem = BLI_mempool_iterstep(&iter))) {
530                 memcpy(p, elem, (size_t)esize);
531                 p = NODE_STEP_NEXT(p);
532         }
533         BLI_assert((uint)(p - (char *)data) == pool->totused * esize);
534 }
535
536 /**
537  * A version of #BLI_mempool_as_array that allocates and returns the data.
538  */
539 void *BLI_mempool_as_arrayN(BLI_mempool *pool, const char *allocstr)
540 {
541         char *data = MEM_mallocN((size_t)(pool->totused * pool->esize), allocstr);
542         BLI_mempool_as_array(pool, data);
543         return data;
544 }
545
546 /**
547  * Initialize a new mempool iterator, \a BLI_MEMPOOL_ALLOW_ITER flag must be set.
548  */
549 void BLI_mempool_iternew(BLI_mempool *pool, BLI_mempool_iter *iter)
550 {
551         BLI_assert(pool->flag & BLI_MEMPOOL_ALLOW_ITER);
552
553         iter->pool = pool;
554         iter->curchunk = pool->chunks;
555         iter->curindex = 0;
556
557         iter->curchunk_threaded_shared = NULL;
558 }
559
560 /**
561  * Initialize an array of mempool iterators, \a BLI_MEMPOOL_ALLOW_ITER flag must be set.
562  *
563  * This is used in threaded code, to generate as much iterators as needed (each task should have its own),
564  * such that each iterator goes over its own single chunk, and only getting the next chunk to iterate over has to be
565  * protected against concurrency (which can be done in a lockless way).
566  *
567  * To be used when creating a task for each single item in the pool is totally overkill.
568  *
569  * See BLI_task_parallel_mempool implementation for detailed usage example.
570  */
571 BLI_mempool_iter *BLI_mempool_iter_threadsafe_create(BLI_mempool *pool, const size_t num_iter)
572 {
573         BLI_assert(pool->flag & BLI_MEMPOOL_ALLOW_ITER);
574
575         BLI_mempool_iter *iter_arr = MEM_mallocN(sizeof(*iter_arr) * num_iter, __func__);
576         BLI_mempool_chunk **curchunk_threaded_shared = MEM_mallocN(sizeof(void *), __func__);
577
578         BLI_mempool_iternew(pool, iter_arr);
579
580         *curchunk_threaded_shared = iter_arr->curchunk;
581         iter_arr->curchunk_threaded_shared = curchunk_threaded_shared;
582
583         for (size_t i = 1; i < num_iter; i++) {
584                 iter_arr[i] = iter_arr[0];
585                 *curchunk_threaded_shared = iter_arr[i].curchunk = (*curchunk_threaded_shared) ? (*curchunk_threaded_shared)->next : NULL;
586         }
587
588         return iter_arr;
589 }
590
591 void  BLI_mempool_iter_threadsafe_free(BLI_mempool_iter *iter_arr)
592 {
593         BLI_assert(iter_arr->curchunk_threaded_shared != NULL);
594
595         MEM_freeN(iter_arr->curchunk_threaded_shared);
596         MEM_freeN(iter_arr);
597 }
598
599 #if 0
600 /* unoptimized, more readable */
601
602 static void *bli_mempool_iternext(BLI_mempool_iter *iter)
603 {
604         void *ret = NULL;
605
606         if (iter->curchunk == NULL || !iter->pool->totused) {
607                 return ret;
608         }
609
610         ret = ((char *)CHUNK_DATA(iter->curchunk)) + (iter->pool->esize * iter->curindex);
611
612         iter->curindex++;
613
614         if (iter->curindex == iter->pool->pchunk) {
615                 iter->curindex = 0;
616                 if (iter->curchunk_threaded_shared) {
617                         while (1) {
618                                 iter->curchunk = *iter->curchunk_threaded_shared;
619                                 if (iter->curchunk == NULL) {
620                                         return ret;
621                                 }
622                                 if (atomic_cas_ptr((void **)iter->curchunk_threaded_shared, iter->curchunk, iter->curchunk->next) == iter->curchunk) {
623                                         break;
624                                 }
625                         }
626                 }
627                 iter->curchunk = iter->curchunk->next;
628         }
629
630         return ret;
631 }
632
633 void *BLI_mempool_iterstep(BLI_mempool_iter *iter)
634 {
635         BLI_freenode *ret;
636
637         do {
638                 ret = bli_mempool_iternext(iter);
639         } while (ret && ret->freeword == FREEWORD);
640
641         return ret;
642 }
643
644 #else
645
646 /* optimized version of code above */
647
648 /**
649  * Step over the iterator, returning the mempool item or NULL.
650  */
651 void *BLI_mempool_iterstep(BLI_mempool_iter *iter)
652 {
653         if (UNLIKELY(iter->curchunk == NULL)) {
654                 return NULL;
655         }
656
657         const uint esize = iter->pool->esize;
658         BLI_freenode *curnode = POINTER_OFFSET(CHUNK_DATA(iter->curchunk), (esize * iter->curindex));
659         BLI_freenode *ret;
660         do {
661                 ret = curnode;
662
663                 if (++iter->curindex != iter->pool->pchunk) {
664                         curnode = POINTER_OFFSET(curnode, esize);
665                 }
666                 else {
667                         iter->curindex = 0;
668                         if (iter->curchunk_threaded_shared) {
669                                 for (iter->curchunk = *iter->curchunk_threaded_shared;
670                                      (iter->curchunk != NULL) &&
671                                      (atomic_cas_ptr((void **)iter->curchunk_threaded_shared, iter->curchunk, iter->curchunk->next) != iter->curchunk);
672                                      iter->curchunk = *iter->curchunk_threaded_shared);
673
674                                 if (UNLIKELY(iter->curchunk == NULL)) {
675                                         return (ret->freeword == FREEWORD) ? NULL : ret;
676                                 }
677                         }
678                         iter->curchunk = iter->curchunk->next;
679                         if (UNLIKELY(iter->curchunk == NULL)) {
680                                 return (ret->freeword == FREEWORD) ? NULL : ret;
681                         }
682                         curnode = CHUNK_DATA(iter->curchunk);
683                 }
684         } while (ret->freeword == FREEWORD);
685
686         return ret;
687 }
688
689 #endif
690
691 /**
692  * Empty the pool, as if it were just created.
693  *
694  * \param pool: The pool to clear.
695  * \param totelem_reserve: Optionally reserve how many items should be kept from clearing.
696  */
697 void BLI_mempool_clear_ex(BLI_mempool *pool, const int totelem_reserve)
698 {
699         BLI_mempool_chunk *mpchunk;
700         BLI_mempool_chunk *mpchunk_next;
701         uint maxchunks;
702
703         BLI_mempool_chunk *chunks_temp;
704         BLI_freenode *lasttail = NULL;
705
706 #ifdef WITH_MEM_VALGRIND
707         VALGRIND_DESTROY_MEMPOOL(pool);
708         VALGRIND_CREATE_MEMPOOL(pool, 0, false);
709 #endif
710
711         if (totelem_reserve == -1) {
712                 maxchunks = pool->maxchunks;
713         }
714         else {
715                 maxchunks = mempool_maxchunks((uint)totelem_reserve, pool->pchunk);
716         }
717
718         /* free all after pool->maxchunks  */
719         mpchunk = mempool_chunk_find(pool->chunks, maxchunks - 1);
720         if (mpchunk && mpchunk->next) {
721                 /* terminate */
722                 mpchunk_next = mpchunk->next;
723                 mpchunk->next = NULL;
724                 mpchunk = mpchunk_next;
725
726                 do {
727                         mpchunk_next = mpchunk->next;
728                         mempool_chunk_free(mpchunk);
729                 } while ((mpchunk = mpchunk_next));
730         }
731
732         /* re-initialize */
733         pool->free = NULL;
734         pool->totused = 0;
735 #ifdef USE_TOTALLOC
736         pool->totalloc = 0;
737 #endif
738
739         chunks_temp = pool->chunks;
740         pool->chunks = NULL;
741         pool->chunk_tail = NULL;
742
743         while ((mpchunk = chunks_temp)) {
744                 chunks_temp = mpchunk->next;
745                 lasttail = mempool_chunk_add(pool, mpchunk, lasttail);
746         }
747 }
748
749 /**
750  * Wrap #BLI_mempool_clear_ex with no reserve set.
751  */
752 void BLI_mempool_clear(BLI_mempool *pool)
753 {
754         BLI_mempool_clear_ex(pool, -1);
755 }
756
757 /**
758  * Free the mempool its self (and all elements).
759  */
760 void BLI_mempool_destroy(BLI_mempool *pool)
761 {
762         mempool_chunk_free_all(pool->chunks);
763
764 #ifdef WITH_MEM_VALGRIND
765         VALGRIND_DESTROY_MEMPOOL(pool);
766 #endif
767
768         MEM_freeN(pool);
769 }
770
771 #ifndef NDEBUG
772 void BLI_mempool_set_memory_debug(void)
773 {
774         mempool_debug_memset = true;
775 }
776 #endif