svn merge ^/trunk/blender -r48592:HEAD
[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         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 #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 // #define HEAP_EQUALS(a, b) (a->value == b->value) // UNUSED
62 #define HEAP_SWAP(heap, i, j) \
63         {                                                                            \
64                 SWAP(int, heap->tree[i]->index, heap->tree[j]->index);                   \
65                 SWAP(HeapNode *, heap->tree[i], heap->tree[j]);                          \
66         } (void)0
67
68 /***/
69
70 Heap *BLI_heap_new(void)
71 {
72         Heap *heap = (Heap *)MEM_callocN(sizeof(Heap), __func__);
73         heap->bufsize = 1;
74         heap->tree = (HeapNode **)MEM_mallocN(sizeof(HeapNode *), "BLIHeapTree");
75         heap->arena = BLI_memarena_new(1 << 16, "heap arena");
76
77         return heap;
78 }
79
80 void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp)
81 {
82         int i;
83
84         if (ptrfreefp)
85                 for (i = 0; i < heap->size; i++)
86                         ptrfreefp(heap->tree[i]->ptr);
87
88         MEM_freeN(heap->tree);
89         BLI_memarena_free(heap->arena);
90         MEM_freeN(heap);
91 }
92
93 static void BLI_heap_down(Heap *heap, int i)
94 {
95         while (1) {
96                 int size = heap->size, smallest;
97                 int l = HEAP_LEFT(i);
98                 int r = HEAP_RIGHT(i);
99
100                 smallest = ((l < size) && HEAP_COMPARE(heap->tree[l], heap->tree[i])) ? l : i;
101
102                 if ((r < size) && HEAP_COMPARE(heap->tree[r], heap->tree[smallest]))
103                         smallest = r;
104
105                 if (smallest == i)
106                         break;
107
108                 HEAP_SWAP(heap, i, smallest);
109                 i = smallest;
110         }
111 }
112
113 static void BLI_heap_up(Heap *heap, int i)
114 {
115         while (i > 0) {
116                 int p = HEAP_PARENT(i);
117
118                 if (HEAP_COMPARE(heap->tree[p], heap->tree[i]))
119                         break;
120
121                 HEAP_SWAP(heap, p, i);
122                 i = p;
123         }
124 }
125
126 HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr)
127 {
128         HeapNode *node;
129
130         if ((heap->size + 1) > heap->bufsize) {
131                 int newsize = heap->bufsize * 2;
132                 HeapNode **newtree;
133
134                 newtree = (HeapNode **)MEM_mallocN(newsize * sizeof(*newtree), __func__);
135                 memcpy(newtree, heap->tree, sizeof(HeapNode *) * heap->size);
136                 MEM_freeN(heap->tree);
137
138                 heap->tree = newtree;
139                 heap->bufsize = newsize;
140         }
141
142         if (heap->freenodes) {
143                 node = heap->freenodes;
144                 heap->freenodes = (HeapNode *)(((HeapNode *)heap->freenodes)->ptr);
145         }
146         else
147                 node = (HeapNode *)BLI_memarena_alloc(heap->arena, sizeof *node);
148
149         node->value = value;
150         node->ptr = ptr;
151         node->index = heap->size;
152
153         heap->tree[node->index] = node;
154
155         heap->size++;
156
157         BLI_heap_up(heap, heap->size - 1);
158
159         return node;
160 }
161
162 int BLI_heap_empty(Heap *heap)
163 {
164         return (heap->size == 0);
165 }
166
167 int BLI_heap_size(Heap *heap)
168 {
169         return heap->size;
170 }
171
172 HeapNode *BLI_heap_top(Heap *heap)
173 {
174         return heap->tree[0];
175 }
176
177 void *BLI_heap_popmin(Heap *heap)
178 {
179         void *ptr = heap->tree[0]->ptr;
180
181         heap->tree[0]->ptr = heap->freenodes;
182         heap->freenodes = heap->tree[0];
183
184         if (heap->size == 1)
185                 heap->size--;
186         else {
187                 HEAP_SWAP(heap, 0, heap->size - 1);
188                 heap->size--;
189
190                 BLI_heap_down(heap, 0);
191         }
192
193         return ptr;
194 }
195
196 void BLI_heap_remove(Heap *heap, HeapNode *node)
197 {
198         int i = node->index;
199
200         while (i > 0) {
201                 int p = HEAP_PARENT(i);
202
203                 HEAP_SWAP(heap, p, i);
204                 i = p;
205         }
206
207         BLI_heap_popmin(heap);
208 }
209
210 float BLI_heap_node_value(HeapNode *node)
211 {
212         return node->value;
213 }
214
215 void *BLI_heap_node_ptr(HeapNode *node)
216 {
217         return node->ptr;
218 }
219