Cleanup: doxygen comments
[blender-staging.git] / extern / curve_fit_nd / intern / generic_heap.c
1 /*
2  * Copyright (c) 2016, Blender Foundation.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions are met:
6  *     * Redistributions of source code must retain the above copyright
7  *       notice, this list of conditions and the following disclaimer.
8  *     * Redistributions in binary form must reproduce the above copyright
9  *       notice, this list of conditions and the following disclaimer in the
10  *       documentation and/or other materials provided with the distribution.
11  *     * Neither the name of the <organization> nor the
12  *       names of its contributors may be used to endorse or promote products
13  *       derived from this software without specific prior written permission.
14  *
15  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
16  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
17  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
18  * DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
19  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
20  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
21  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
22  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  */
26
27 /** \file generic_heap.c
28  *  \ingroup curve_fit
29  */
30
31 #include <stdlib.h>
32 #include <string.h>
33 #include <stdbool.h>
34 #include <assert.h>
35
36 #include "generic_heap.h"
37
38 /* swap with a temp value */
39 #define SWAP_TVAL(tval, a, b)  {  \
40         (tval) = (a);                 \
41         (a) = (b);                    \
42         (b) = (tval);                 \
43 } (void)0
44
45 #ifdef __GNUC__
46 #  define UNLIKELY(x)     __builtin_expect(!!(x), 0)
47 #else
48 #  define UNLIKELY(x)     (x)
49 #endif
50
51 typedef unsigned int uint;
52
53 /***/
54
55 struct HeapNode {
56         void   *ptr;
57         double  value;
58         uint    index;
59 };
60
61 /* heap_* pool allocator */
62 #define TPOOL_IMPL_PREFIX  heap
63 #define TPOOL_ALLOC_TYPE   HeapNode
64 #define TPOOL_STRUCT       HeapMemPool
65 #include "generic_alloc_impl.h"
66 #undef TPOOL_IMPL_PREFIX
67 #undef TPOOL_ALLOC_TYPE
68 #undef TPOOL_STRUCT
69
70 struct Heap {
71         uint size;
72         uint bufsize;
73         HeapNode **tree;
74
75         struct HeapMemPool pool;
76 };
77
78 /** \name Internal Functions
79  * \{ */
80
81 #define HEAP_PARENT(i) (((i) - 1) >> 1)
82 #define HEAP_LEFT(i)   (((i) << 1) + 1)
83 #define HEAP_RIGHT(i)  (((i) << 1) + 2)
84 #define HEAP_COMPARE(a, b) ((a)->value < (b)->value)
85
86 #if 0  /* UNUSED */
87 #define HEAP_EQUALS(a, b) ((a)->value == (b)->value)
88 #endif
89
90 static void heap_swap(Heap *heap, const uint i, const uint j)
91 {
92
93 #if 0
94         SWAP(uint,       heap->tree[i]->index, heap->tree[j]->index);
95         SWAP(HeapNode *, heap->tree[i],        heap->tree[j]);
96 #else
97         HeapNode **tree = heap->tree;
98         union {
99                 uint      index;
100                 HeapNode *node;
101         } tmp;
102         SWAP_TVAL(tmp.index, tree[i]->index, tree[j]->index);
103         SWAP_TVAL(tmp.node,  tree[i],        tree[j]);
104 #endif
105 }
106
107 static void heap_down(Heap *heap, uint i)
108 {
109         /* size won't change in the loop */
110         const uint size = heap->size;
111
112         while (1) {
113                 const uint l = HEAP_LEFT(i);
114                 const uint r = HEAP_RIGHT(i);
115                 uint smallest;
116
117                 smallest = ((l < size) && HEAP_COMPARE(heap->tree[l], heap->tree[i])) ? l : i;
118
119                 if ((r < size) && HEAP_COMPARE(heap->tree[r], heap->tree[smallest])) {
120                         smallest = r;
121                 }
122
123                 if (smallest == i) {
124                         break;
125                 }
126
127                 heap_swap(heap, i, smallest);
128                 i = smallest;
129         }
130 }
131
132 static void heap_up(Heap *heap, uint i)
133 {
134         while (i > 0) {
135                 const uint p = HEAP_PARENT(i);
136
137                 if (HEAP_COMPARE(heap->tree[p], heap->tree[i])) {
138                         break;
139                 }
140                 heap_swap(heap, p, i);
141                 i = p;
142         }
143 }
144
145 /** \} */
146
147
148 /** \name Public Heap API
149  * \{ */
150
151 /* use when the size of the heap is known in advance */
152 Heap *HEAP_new(uint tot_reserve)
153 {
154         Heap *heap = malloc(sizeof(Heap));
155         /* ensure we have at least one so we can keep doubling it */
156         heap->size = 0;
157         heap->bufsize = tot_reserve ? tot_reserve : 1;
158         heap->tree = malloc(heap->bufsize * sizeof(HeapNode *));
159
160         heap_pool_create(&heap->pool, tot_reserve);
161
162         return heap;
163 }
164
165 void HEAP_free(Heap *heap, HeapFreeFP ptrfreefp)
166 {
167         if (ptrfreefp) {
168                 uint i;
169
170                 for (i = 0; i < heap->size; i++) {
171                         ptrfreefp(heap->tree[i]->ptr);
172                 }
173         }
174
175         heap_pool_destroy(&heap->pool);
176
177         free(heap->tree);
178         free(heap);
179 }
180
181 void HEAP_clear(Heap *heap, HeapFreeFP ptrfreefp)
182 {
183         if (ptrfreefp) {
184                 uint i;
185
186                 for (i = 0; i < heap->size; i++) {
187                         ptrfreefp(heap->tree[i]->ptr);
188                 }
189         }
190         heap->size = 0;
191
192         heap_pool_clear(&heap->pool);
193 }
194
195 HeapNode *HEAP_insert(Heap *heap, double value, void *ptr)
196 {
197         HeapNode *node;
198
199         if (UNLIKELY(heap->size >= heap->bufsize)) {
200                 heap->bufsize *= 2;
201                 heap->tree = realloc(heap->tree, heap->bufsize * sizeof(*heap->tree));
202         }
203
204         node = heap_pool_elem_alloc(&heap->pool);
205
206         node->ptr = ptr;
207         node->value = value;
208         node->index = heap->size;
209
210         heap->tree[node->index] = node;
211
212         heap->size++;
213
214         heap_up(heap, node->index);
215
216         return node;
217 }
218
219 void HEAP_insert_or_update(Heap *heap, HeapNode **node_p, double value, void *ptr)
220 {
221         if (*node_p == NULL) {
222                 *node_p = HEAP_insert(heap, value, ptr);
223         }
224         else {
225                 HEAP_node_value_update_ptr(heap, *node_p, value, ptr);
226         }
227 }
228
229 bool HEAP_is_empty(const Heap *heap)
230 {
231         return (heap->size == 0);
232 }
233
234 uint HEAP_size(const Heap *heap)
235 {
236         return heap->size;
237 }
238
239 HeapNode *HEAP_top(Heap *heap)
240 {
241         return heap->tree[0];
242 }
243
244 double HEAP_top_value(const Heap *heap)
245 {
246         return heap->tree[0]->value;
247 }
248
249 void *HEAP_popmin(Heap *heap)
250 {
251         void *ptr = heap->tree[0]->ptr;
252
253         assert(heap->size != 0);
254
255         heap_pool_elem_free(&heap->pool, heap->tree[0]);
256
257         if (--heap->size) {
258                 heap_swap(heap, 0, heap->size);
259                 heap_down(heap, 0);
260         }
261
262         return ptr;
263 }
264
265 void HEAP_remove(Heap *heap, HeapNode *node)
266 {
267         uint i = node->index;
268
269         assert(heap->size != 0);
270
271         while (i > 0) {
272                 uint p = HEAP_PARENT(i);
273
274                 heap_swap(heap, p, i);
275                 i = p;
276         }
277
278         HEAP_popmin(heap);
279 }
280
281 void HEAP_node_value_update(Heap *heap, HeapNode *node, double value)
282 {
283         assert(heap->size != 0);
284         if (node->value == value) {
285                 return;
286         }
287         node->value = value;
288         /* Can be called in either order, makes no difference. */
289         heap_up(heap, node->index);
290         heap_down(heap, node->index);
291 }
292
293 void HEAP_node_value_update_ptr(Heap *heap, HeapNode *node, double value, void *ptr)
294 {
295         node->ptr = ptr;
296         HEAP_node_value_update(heap, node, value);
297 }
298
299 double HEAP_node_value(const HeapNode *node)
300 {
301         return node->value;
302 }
303
304 void *HEAP_node_ptr(HeapNode *node)
305 {
306         return node->ptr;
307 }
308
309 /** \} */