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