Cleanup: Remove more #if 0 blocks
[blender.git] / source / blender / blenlib / intern / BLI_heap.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): Brecht Van Lommel
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/blenlib/intern/BLI_heap.c
24  *  \ingroup bli
25  *
26  * A min-heap / priority queue ADT.
27  */
28
29 #include <stdlib.h>
30 #include <string.h>
31
32 #include "MEM_guardedalloc.h"
33
34 #include "BLI_utildefines.h"
35 #include "BLI_heap.h"
36 #include "BLI_strict_flags.h"
37
38 /***/
39
40 struct HeapNode {
41         void *ptr;
42         float value;
43         uint  index;
44 };
45
46 struct HeapNode_Chunk {
47         struct HeapNode_Chunk *prev;
48         uint size;
49         uint bufsize;
50         struct HeapNode buf[0];
51 };
52
53 /**
54  * Number of nodes to include per #HeapNode_Chunk when no reserved size is passed,
55  * or we allocate past the reserved number.
56  *
57  * \note Optimize number for 64kb allocs.
58  * \note keep type in sync with tot_nodes in heap_node_alloc_chunk.
59  */
60 #define HEAP_CHUNK_DEFAULT_NUM \
61         ((uint)((MEM_SIZE_OPTIMAL((1 << 16) - sizeof(struct HeapNode_Chunk))) / sizeof(HeapNode)))
62
63 struct Heap {
64         uint size;
65         uint bufsize;
66         HeapNode **tree;
67
68         struct {
69                 /* Always keep at least one chunk (never NULL) */
70                 struct HeapNode_Chunk *chunk;
71                 /* when NULL, allocate a new chunk */
72                 HeapNode *free;
73         } nodes;
74 };
75
76 /** \name Internal Functions
77  * \{ */
78
79 #define HEAP_PARENT(i) (((i) - 1) >> 1)
80 #define HEAP_LEFT(i)   (((i) << 1) + 1)
81 #define HEAP_RIGHT(i)  (((i) << 1) + 2)
82 #define HEAP_COMPARE(a, b) ((a)->value < (b)->value)
83
84 #if 0  /* UNUSED */
85 #define HEAP_EQUALS(a, b) ((a)->value == (b)->value)
86 #endif
87
88 BLI_INLINE void heap_swap(Heap *heap, const uint i, const uint j)
89 {
90         HeapNode **tree = heap->tree;
91         union {
92                 uint  index;
93                 HeapNode     *node;
94         } tmp;
95         SWAP_TVAL(tmp.index, tree[i]->index, tree[j]->index);
96         SWAP_TVAL(tmp.node,  tree[i],        tree[j]);
97 }
98
99 static void heap_down(Heap *heap, uint i)
100 {
101         /* size won't change in the loop */
102         const uint size = heap->size;
103
104         while (1) {
105                 const uint l = HEAP_LEFT(i);
106                 const uint r = HEAP_RIGHT(i);
107                 uint smallest = i;
108
109                 if ((l < size) && HEAP_COMPARE(heap->tree[l], heap->tree[smallest])) {
110                         smallest = l;
111                 }
112                 if ((r < size) && HEAP_COMPARE(heap->tree[r], heap->tree[smallest])) {
113                         smallest = r;
114                 }
115
116                 if (smallest == i) {
117                         break;
118                 }
119
120                 heap_swap(heap, i, smallest);
121                 i = smallest;
122         }
123 }
124
125 static void heap_up(Heap *heap, uint i)
126 {
127         while (i > 0) {
128                 const uint p = HEAP_PARENT(i);
129
130                 if (HEAP_COMPARE(heap->tree[p], heap->tree[i])) {
131                         break;
132                 }
133                 heap_swap(heap, p, i);
134                 i = p;
135         }
136 }
137
138 /** \} */
139
140
141 /** \name Internal Memory Management
142  * \{ */
143
144 static struct HeapNode_Chunk *heap_node_alloc_chunk(
145         uint tot_nodes, struct HeapNode_Chunk *chunk_prev)
146 {
147         struct HeapNode_Chunk *chunk = MEM_mallocN(
148                 sizeof(struct HeapNode_Chunk) + (sizeof(HeapNode) * tot_nodes), __func__);
149         chunk->prev = chunk_prev;
150         chunk->bufsize = tot_nodes;
151         chunk->size = 0;
152         return chunk;
153 }
154
155 static struct HeapNode *heap_node_alloc(Heap *heap)
156 {
157         HeapNode *node;
158
159         if (heap->nodes.free) {
160                 node = heap->nodes.free;
161                 heap->nodes.free = heap->nodes.free->ptr;
162         }
163         else {
164                 struct HeapNode_Chunk *chunk = heap->nodes.chunk;
165                 if (UNLIKELY(chunk->size == chunk->bufsize)) {
166                         chunk = heap->nodes.chunk = heap_node_alloc_chunk(HEAP_CHUNK_DEFAULT_NUM, chunk);
167                 }
168                 node = &chunk->buf[chunk->size++];
169         }
170
171         return node;
172 }
173
174 static void heap_node_free(Heap *heap, HeapNode *node)
175 {
176         node->ptr = heap->nodes.free;
177         heap->nodes.free = node;
178 }
179
180 /** \} */
181
182
183 /** \name Public Heap API
184  * \{ */
185
186 /**
187  * Creates a new heap. Removed nodes are recycled, so memory usage will not shrink.
188  *
189  * \note Use when the size of the heap is known in advance.
190  */
191 Heap *BLI_heap_new_ex(uint tot_reserve)
192 {
193         Heap *heap = MEM_mallocN(sizeof(Heap), __func__);
194         /* ensure we have at least one so we can keep doubling it */
195         heap->size = 0;
196         heap->bufsize = MAX2(1u, tot_reserve);
197         heap->tree = MEM_mallocN(heap->bufsize * sizeof(HeapNode *), "BLIHeapTree");
198
199         heap->nodes.chunk = heap_node_alloc_chunk((tot_reserve > 1) ? tot_reserve : HEAP_CHUNK_DEFAULT_NUM, NULL);
200         heap->nodes.free = NULL;
201
202         return heap;
203 }
204
205 Heap *BLI_heap_new(void)
206 {
207         return BLI_heap_new_ex(1);
208 }
209
210 void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp)
211 {
212         if (ptrfreefp) {
213                 uint i;
214
215                 for (i = 0; i < heap->size; i++) {
216                         ptrfreefp(heap->tree[i]->ptr);
217                 }
218         }
219
220         struct HeapNode_Chunk *chunk = heap->nodes.chunk;
221         do {
222                 struct HeapNode_Chunk *chunk_prev;
223                 chunk_prev = chunk->prev;
224                 MEM_freeN(chunk);
225                 chunk = chunk_prev;
226         } while (chunk);
227
228         MEM_freeN(heap->tree);
229         MEM_freeN(heap);
230 }
231
232 void BLI_heap_clear(Heap *heap, HeapFreeFP ptrfreefp)
233 {
234         if (ptrfreefp) {
235                 uint i;
236
237                 for (i = 0; i < heap->size; i++) {
238                         ptrfreefp(heap->tree[i]->ptr);
239                 }
240         }
241         heap->size = 0;
242
243         /* Remove all except the last chunk */
244         while (heap->nodes.chunk->prev) {
245                 struct HeapNode_Chunk *chunk_prev = heap->nodes.chunk->prev;
246                 MEM_freeN(heap->nodes.chunk);
247                 heap->nodes.chunk = chunk_prev;
248         }
249         heap->nodes.chunk->size = 0;
250         heap->nodes.free = NULL;
251 }
252
253 /**
254  * Insert heap node with a value (often a 'cost') and pointer into the heap,
255  * duplicate values are allowed.
256  */
257 HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr)
258 {
259         HeapNode *node;
260
261         if (UNLIKELY(heap->size >= heap->bufsize)) {
262                 heap->bufsize *= 2;
263                 heap->tree = MEM_reallocN(heap->tree, heap->bufsize * sizeof(*heap->tree));
264         }
265
266         node = heap_node_alloc(heap);
267
268         node->ptr = ptr;
269         node->value = value;
270         node->index = heap->size;
271
272         heap->tree[node->index] = node;
273
274         heap->size++;
275
276         heap_up(heap, node->index);
277
278         return node;
279 }
280
281 /**
282  * Convenience function since this is a common pattern.
283  */
284 void BLI_heap_insert_or_update(Heap *heap, HeapNode **node_p, float value, void *ptr)
285 {
286         if (*node_p == NULL) {
287                 *node_p = BLI_heap_insert(heap, value, ptr);
288         }
289         else {
290                 BLI_heap_node_value_update_ptr(heap, *node_p, value, ptr);
291         }
292 }
293
294
295 bool BLI_heap_is_empty(const Heap *heap)
296 {
297         return (heap->size == 0);
298 }
299
300 uint BLI_heap_len(const Heap *heap)
301 {
302         return heap->size;
303 }
304
305 /**
306  * Return the top node of the heap.
307  * This is the node with the lowest value.
308  */
309 HeapNode *BLI_heap_top(const Heap *heap)
310 {
311         return heap->tree[0];
312 }
313
314 /**
315  * Pop the top node off the heap and return it's pointer.
316  */
317 void *BLI_heap_pop_min(Heap *heap)
318 {
319         BLI_assert(heap->size != 0);
320
321         void *ptr = heap->tree[0]->ptr;
322
323         heap_node_free(heap, heap->tree[0]);
324
325         if (--heap->size) {
326                 heap_swap(heap, 0, heap->size);
327                 heap_down(heap, 0);
328         }
329
330         return ptr;
331 }
332
333 void BLI_heap_remove(Heap *heap, HeapNode *node)
334 {
335         BLI_assert(heap->size != 0);
336
337         uint i = node->index;
338
339         while (i > 0) {
340                 uint p = HEAP_PARENT(i);
341                 heap_swap(heap, p, i);
342                 i = p;
343         }
344
345         BLI_heap_pop_min(heap);
346 }
347
348 /**
349  * Can be used to avoid #BLI_heap_remove, #BLI_heap_insert calls,
350  * balancing the tree still has a performance cost,
351  * but is often much less than remove/insert, difference is most noticable with large heaps.
352  */
353 void BLI_heap_node_value_update(Heap *heap, HeapNode *node, float value)
354 {
355         if (value < node->value) {
356                 node->value = value;
357                 heap_up(heap, node->index);
358         }
359         else if (value > node->value) {
360                 node->value = value;
361                 heap_down(heap, node->index);
362         }
363 }
364
365 void BLI_heap_node_value_update_ptr(Heap *heap, HeapNode *node, float value, void *ptr)
366 {
367         node->ptr = ptr; /* only difference */
368         if (value < node->value) {
369                 node->value = value;
370                 heap_up(heap, node->index);
371         }
372         else if (value > node->value) {
373                 node->value = value;
374                 heap_down(heap, node->index);
375         }
376 }
377
378 float BLI_heap_node_value(const HeapNode *node)
379 {
380         return node->value;
381 }
382
383 void *BLI_heap_node_ptr(const HeapNode *node)
384 {
385         return node->ptr;
386 }
387
388 static bool heap_is_minheap(const Heap *heap, uint root)
389 {
390         if (root < heap->size) {
391                 const uint l = HEAP_LEFT(root);
392                 if (l < heap->size) {
393                         if (HEAP_COMPARE(heap->tree[l], heap->tree[root]) || !heap_is_minheap(heap, l)) {
394                                 return false;
395                         }
396                 }
397                 const uint r = HEAP_RIGHT(root);
398                 if (r < heap->size) {
399                         if (HEAP_COMPARE(heap->tree[r], heap->tree[root]) || !heap_is_minheap(heap, r)) {
400                                 return false;
401                         }
402                 }
403         }
404         return true;
405 }
406 /**
407  * Only for checking internal errors (gtest).
408  */
409 bool BLI_heap_is_valid(const Heap *heap)
410 {
411         return heap_is_minheap(heap, 0);
412 }
413
414 /** \} */