Merge branch 'master' into blender2.8
[blender.git] / source / blender / blenlib / intern / BLI_heap_simple.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  * ***** END GPL LICENSE BLOCK *****
19  */
20
21 /** \file blender/blenlib/intern/BLI_heap_simple.c
22  *  \ingroup bli
23  *
24  * A min-heap / priority queue ADT.
25  *
26  * Simplified version of the heap that only supports insertion and removal from top.
27  *
28  * See BLI_heap.c for a more full featured heap implementation.
29  */
30
31 #include <stdlib.h>
32 #include <string.h>
33
34 #include "MEM_guardedalloc.h"
35
36 #include "BLI_utildefines.h"
37 #include "BLI_heap_simple.h"
38 #include "BLI_strict_flags.h"
39
40 #define HEAP_PARENT(i) (((i) - 1) >> 1)
41
42 /* -------------------------------------------------------------------- */
43 /** \name HeapSimple Internal Structs
44  * \{ */
45
46 typedef struct HeapSimpleNode {
47         float value;
48         void *ptr;
49 } HeapSimpleNode;
50
51 struct HeapSimple {
52         uint size;
53         uint bufsize;
54         HeapSimpleNode *tree;
55 };
56
57 /** \} */
58
59 /* -------------------------------------------------------------------- */
60 /** \name HeapSimple Internal Functions
61  * \{ */
62
63 static void heapsimple_down(HeapSimple *heap, uint start_i, const HeapSimpleNode *init)
64 {
65 #if 1
66         /* The compiler isn't smart enough to realize that all computations
67          * using index here can be modified to work with byte offset. */
68         uint8_t * const tree_buf = (uint8_t *)heap->tree;
69
70 #define OFFSET(i) (i * (uint)sizeof(HeapSimpleNode))
71 #define NODE(offset) (*(HeapSimpleNode*)(tree_buf + (offset)))
72 #else
73         HeapSimpleNode *const tree = heap->tree;
74
75 #define OFFSET(i) (i)
76 #define NODE(i) tree[i]
77 #endif
78
79 #define HEAP_LEFT_OFFSET(i) (((i) << 1) + OFFSET(1))
80
81         const uint size = OFFSET(heap->size);
82
83         /* Pull the active node values into locals. This allows spilling
84          * the data from registers instead of literally swapping nodes. */
85         float active_val = init->value;
86         void *active_ptr = init->ptr;
87
88         /* Prepare the first iteration and spill value. */
89         uint i = OFFSET(start_i);
90
91         NODE(i).value = active_val;
92
93         for (;;) {
94                 const uint l = HEAP_LEFT_OFFSET(i);
95                 const uint r = l + OFFSET(1); /* right */
96
97                 /* Find the child with the smallest value. */
98                 uint smallest = i;
99
100                 if (LIKELY(l < size) && NODE(l).value < active_val) {
101                         smallest = l;
102                 }
103                 if (LIKELY(r < size) && NODE(r).value < NODE(smallest).value) {
104                         smallest = r;
105                 }
106
107                 if (UNLIKELY(smallest == i)) {
108                         break;
109                 }
110
111                 /* Move the smallest child into the current node.
112                  * Skip padding: for some reason that makes it faster here. */
113                 NODE(i).value = NODE(smallest).value;
114                 NODE(i).ptr = NODE(smallest).ptr;
115
116                 /* Proceed to next iteration and spill value. */
117                 i = smallest;
118                 NODE(i).value = active_val;
119         }
120
121         /* Spill the pointer into the final position of the node. */
122         NODE(i).ptr = active_ptr;
123
124 #undef NODE
125 #undef OFFSET
126 #undef HEAP_LEFT_OFFSET
127 }
128
129 static void heapsimple_up(HeapSimple *heap, uint i, float active_val, void *active_ptr)
130 {
131         HeapSimpleNode *const tree = heap->tree;
132
133         while (LIKELY(i > 0)) {
134                 const uint p = HEAP_PARENT(i);
135
136                 if (active_val >= tree[p].value) {
137                         break;
138                 }
139
140                 tree[i] = tree[p];
141                 i = p;
142         }
143
144         tree[i].value = active_val;
145         tree[i].ptr = active_ptr;
146 }
147
148 /** \} */
149
150 /* -------------------------------------------------------------------- */
151 /** \name Public HeapSimple API
152  * \{ */
153
154 /**
155  * Creates a new simple heap, which only supports insertion and removal from top.
156  *
157  * \note Use when the size of the heap is known in advance.
158  */
159 HeapSimple *BLI_heapsimple_new_ex(uint tot_reserve)
160 {
161         HeapSimple *heap = MEM_mallocN(sizeof(HeapSimple), __func__);
162         /* ensure we have at least one so we can keep doubling it */
163         heap->size = 0;
164         heap->bufsize = MAX2(1u, tot_reserve);
165         heap->tree = MEM_mallocN(heap->bufsize * sizeof(HeapSimpleNode), "BLIHeapSimpleTree");
166         return heap;
167 }
168
169 HeapSimple *BLI_heapsimple_new(void)
170 {
171         return BLI_heapsimple_new_ex(1);
172 }
173
174 void BLI_heapsimple_free(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp)
175 {
176         if (ptrfreefp) {
177                 for (uint i = 0; i < heap->size; i++) {
178                         ptrfreefp(heap->tree[i].ptr);
179                 }
180         }
181
182         MEM_freeN(heap->tree);
183         MEM_freeN(heap);
184 }
185
186 void BLI_heapsimple_clear(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp)
187 {
188         if (ptrfreefp) {
189                 for (uint i = 0; i < heap->size; i++) {
190                         ptrfreefp(heap->tree[i].ptr);
191                 }
192         }
193
194         heap->size = 0;
195 }
196
197 /**
198  * Insert heap node with a value (often a 'cost') and pointer into the heap,
199  * duplicate values are allowed.
200  */
201 void BLI_heapsimple_insert(HeapSimple *heap, float value, void *ptr)
202 {
203         if (UNLIKELY(heap->size >= heap->bufsize)) {
204                 heap->bufsize *= 2;
205                 heap->tree = MEM_reallocN(heap->tree, heap->bufsize * sizeof(*heap->tree));
206         }
207
208         heapsimple_up(heap, heap->size++, value, ptr);
209 }
210
211 bool BLI_heapsimple_is_empty(const HeapSimple *heap)
212 {
213         return (heap->size == 0);
214 }
215
216 uint BLI_heapsimple_len(const HeapSimple *heap)
217 {
218         return heap->size;
219 }
220
221 /**
222  * Return the lowest value of the heap.
223  */
224 float BLI_heapsimple_top_value(const HeapSimple *heap)
225 {
226         BLI_assert(heap->size != 0);
227
228         return heap->tree[0].value;
229 }
230
231 /**
232  * Pop the top node off the heap and return it's pointer.
233  */
234 void *BLI_heapsimple_pop_min(HeapSimple *heap)
235 {
236         BLI_assert(heap->size != 0);
237
238         void *ptr = heap->tree[0].ptr;
239
240         if (--heap->size) {
241                 heapsimple_down(heap, 0, &heap->tree[heap->size]);
242         }
243
244         return ptr;
245 }
246
247 /** \} */