cleanup: style
[blender-staging.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 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_memarena.h"
36 #include "BLI_heap.h"
37 #include "BLI_strict_flags.h"
38
39 /***/
40
41 struct HeapNode {
42         void        *ptr;
43         float        value;
44         unsigned int index;
45 };
46
47 struct Heap {
48         unsigned int size;
49         unsigned int bufsize;
50         MemArena *arena;
51         HeapNode *freenodes;
52         HeapNode **tree;
53 };
54
55 /* internal functions */
56
57 #define HEAP_PARENT(i) ((i - 1) >> 1)
58 #define HEAP_LEFT(i)   ((i << 1) + 1)
59 #define HEAP_RIGHT(i)  ((i << 1) + 2)
60 #define HEAP_COMPARE(a, b) (a->value < b->value)
61
62 #if 0  /* UNUSED */
63 #define HEAP_EQUALS(a, b) (a->value == b->value)
64 #endif
65
66 BLI_INLINE void heap_swap(Heap *heap, const unsigned int i, const unsigned int j)
67 {
68
69 #if 0
70         SWAP(unsigned int,  heap->tree[i]->index, heap->tree[j]->index);
71         SWAP(HeapNode *,    heap->tree[i],        heap->tree[j]);
72 #else
73         HeapNode **tree = heap->tree;
74         union {
75                 unsigned int  index;
76                 HeapNode     *node;
77         } tmp;
78         SWAP_TVAL(tmp.index, tree[i]->index, tree[j]->index);
79         SWAP_TVAL(tmp.node,  tree[i],        tree[j]);
80 #endif
81 }
82
83 static void heap_down(Heap *heap, unsigned int i)
84 {
85         /* size won't change in the loop */
86         const unsigned int size = heap->size;
87
88         while (1) {
89                 const unsigned int l = HEAP_LEFT(i);
90                 const unsigned int r = HEAP_RIGHT(i);
91                 unsigned int smallest;
92
93                 smallest = ((l < size) && HEAP_COMPARE(heap->tree[l], heap->tree[i])) ? l : i;
94
95                 if ((r < size) && HEAP_COMPARE(heap->tree[r], heap->tree[smallest]))
96                         smallest = r;
97
98                 if (smallest == i)
99                         break;
100
101                 heap_swap(heap, i, smallest);
102                 i = smallest;
103         }
104 }
105
106 static void heap_up(Heap *heap, unsigned int i)
107 {
108         while (i > 0) {
109                 const unsigned int p = HEAP_PARENT(i);
110
111                 if (HEAP_COMPARE(heap->tree[p], heap->tree[i]))
112                         break;
113
114                 heap_swap(heap, p, i);
115                 i = p;
116         }
117 }
118
119
120 /***/
121
122 /* use when the size of the heap is known in advance */
123 Heap *BLI_heap_new_ex(unsigned int tot_reserve)
124 {
125         Heap *heap = (Heap *)MEM_callocN(sizeof(Heap), __func__);
126         /* ensure we have at least one so we can keep doubling it */
127         heap->bufsize = MAX2(1u, tot_reserve);
128         heap->tree = (HeapNode **)MEM_mallocN(heap->bufsize * sizeof(HeapNode *), "BLIHeapTree");
129         heap->arena = BLI_memarena_new(MEM_SIZE_OPTIMAL(1 << 16), "heap arena");
130
131         return heap;
132 }
133
134 Heap *BLI_heap_new(void)
135 {
136         return BLI_heap_new_ex(1);
137 }
138
139 void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp)
140 {
141         if (ptrfreefp) {
142                 unsigned int i;
143
144                 for (i = 0; i < heap->size; i++) {
145                         ptrfreefp(heap->tree[i]->ptr);
146                 }
147         }
148
149         MEM_freeN(heap->tree);
150         BLI_memarena_free(heap->arena);
151         MEM_freeN(heap);
152 }
153
154 void BLI_heap_clear(Heap *heap, HeapFreeFP ptrfreefp)
155 {
156         if (ptrfreefp) {
157                 unsigned int i;
158
159                 for (i = 0; i < heap->size; i++) {
160                         ptrfreefp(heap->tree[i]->ptr);
161                 }
162         }
163
164         heap->size = 0;
165         BLI_memarena_clear(heap->arena);
166         heap->freenodes = NULL;
167 }
168
169 HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr)
170 {
171         HeapNode *node;
172
173         if (UNLIKELY(heap->size >= heap->bufsize)) {
174                 heap->bufsize *= 2;
175                 heap->tree = MEM_reallocN(heap->tree, heap->bufsize * sizeof(*heap->tree));
176         }
177
178         if (heap->freenodes) {
179                 node = heap->freenodes;
180                 heap->freenodes = heap->freenodes->ptr;
181         }
182         else {
183                 node = (HeapNode *)BLI_memarena_alloc(heap->arena, sizeof(*node));
184         }
185
186         node->value = value;
187         node->ptr = ptr;
188         node->index = heap->size;
189
190         heap->tree[node->index] = node;
191
192         heap->size++;
193
194         heap_up(heap, node->index);
195
196         return node;
197 }
198
199 bool BLI_heap_is_empty(Heap *heap)
200 {
201         return (heap->size == 0);
202 }
203
204 unsigned int BLI_heap_size(Heap *heap)
205 {
206         return heap->size;
207 }
208
209 HeapNode *BLI_heap_top(Heap *heap)
210 {
211         return heap->tree[0];
212 }
213
214 void *BLI_heap_popmin(Heap *heap)
215 {
216         void *ptr = heap->tree[0]->ptr;
217
218         BLI_assert(heap->size != 0);
219
220         heap->tree[0]->ptr = heap->freenodes;
221         heap->freenodes = heap->tree[0];
222
223         if (--heap->size) {
224                 heap_swap(heap, 0, heap->size);
225                 heap_down(heap, 0);
226         }
227
228         return ptr;
229 }
230
231 void BLI_heap_remove(Heap *heap, HeapNode *node)
232 {
233         unsigned int i = node->index;
234
235         BLI_assert(heap->size != 0);
236
237         while (i > 0) {
238                 unsigned int p = HEAP_PARENT(i);
239
240                 heap_swap(heap, p, i);
241                 i = p;
242         }
243
244         BLI_heap_popmin(heap);
245 }
246
247 float BLI_heap_node_value(HeapNode *node)
248 {
249         return node->value;
250 }
251
252 void *BLI_heap_node_ptr(HeapNode *node)
253 {
254         return node->ptr;
255 }
256