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