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