svn merge -r 23207:23528 https://svn.blender.org/svnroot/bf-blender/trunk/blender
[blender.git] / source / blender / blenlib / intern / BLI_heap.c
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19  *
20  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
21  * All rights reserved.
22  *
23  * The Original Code is: none of this file.
24  *
25  * Contributor(s): Brecht Van Lommel
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  * A heap / priority queue ADT.
29  */
30
31 #include <stdlib.h>
32 #include <string.h>
33
34 #include "MEM_guardedalloc.h"
35 #include "BLI_memarena.h"
36 #include "BLI_heap.h"
37
38 /***/
39
40 struct HeapNode {
41         void *ptr;
42         float value;
43         int index;
44 };
45
46 struct Heap {
47         unsigned int size;
48         unsigned int bufsize;
49         MemArena *arena;
50         HeapNode *freenodes;
51         HeapNode *nodes;
52         HeapNode **tree;
53 };
54
55 #define SWAP(type, a, b) \
56         { type sw_ap; sw_ap=(a); (a)=(b); (b)=sw_ap; }
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)
62 #define HEAP_SWAP(heap, i, j) \
63         { SWAP(int, heap->tree[i]->index, heap->tree[j]->index); \
64           SWAP(HeapNode*, heap->tree[i], heap->tree[j]);  }
65
66 /***/
67
68 Heap *BLI_heap_new()
69 {
70         Heap *heap = (Heap*)MEM_callocN(sizeof(Heap), "BLIHeap");
71         heap->bufsize = 1;
72         heap->tree = (HeapNode**)MEM_mallocN(sizeof(HeapNode*), "BLIHeapTree");
73         heap->arena = BLI_memarena_new(1<<16);
74
75         return heap;
76 }
77
78 void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp)
79 {
80         int i;
81
82         if (ptrfreefp)
83                 for (i = 0; i < heap->size; i++)
84                         ptrfreefp(heap->tree[i]->ptr);
85         
86         MEM_freeN(heap->tree);
87         BLI_memarena_free(heap->arena);
88         MEM_freeN(heap);
89 }
90
91 static void BLI_heap_down(Heap *heap, int i)
92 {
93         while (1) {
94                 int size = heap->size, smallest;
95                 int l = HEAP_LEFT(i);
96                 int r = HEAP_RIGHT(i);
97
98                 smallest = ((l < size) && HEAP_COMPARE(heap->tree[l], heap->tree[i]))? l: i;
99
100                 if ((r < size) && HEAP_COMPARE(heap->tree[r], heap->tree[smallest]))
101                         smallest = r;
102                 
103                 if (smallest == i)
104                         break;
105
106                 HEAP_SWAP(heap, i, smallest);
107                 i = smallest;
108         }
109 }
110
111 static void BLI_heap_up(Heap *heap, int i)
112 {
113         while (i > 0) {
114                 int p = HEAP_PARENT(i);
115
116                 if (HEAP_COMPARE(heap->tree[p], heap->tree[i]))
117                         break;
118
119                 HEAP_SWAP(heap, p, i);
120                 i = p;
121         }
122 }
123
124 HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr)
125 {
126         HeapNode *node;
127
128         if ((heap->size + 1) > heap->bufsize) {
129                 int newsize = heap->bufsize*2;
130                 HeapNode **newtree;
131
132                 newtree = (HeapNode**)MEM_mallocN(newsize*sizeof(*newtree), "BLIHeapTree");
133                 memcpy(newtree, heap->tree, sizeof(HeapNode*)*heap->size);
134                 MEM_freeN(heap->tree);
135
136                 heap->tree = newtree;
137                 heap->bufsize = newsize;
138         }
139
140         if (heap->freenodes) {
141                 node = heap->freenodes;
142                 heap->freenodes = (HeapNode*)(((HeapNode*)heap->freenodes)->ptr);
143         }
144         else
145                 node = (HeapNode*)BLI_memarena_alloc(heap->arena, sizeof *node);
146
147         node->value = value;
148         node->ptr = ptr;
149         node->index = heap->size;
150
151         heap->tree[node->index] = node;
152
153         heap->size++;
154
155         BLI_heap_up(heap, heap->size-1);
156
157         return node;
158 }
159
160 int BLI_heap_empty(Heap *heap)
161 {
162         return (heap->size == 0);
163 }
164
165 int BLI_heap_size(Heap *heap)
166 {
167         return heap->size;
168 }
169
170 HeapNode *BLI_heap_top(Heap *heap)
171 {
172         return heap->tree[0];
173 }
174
175 void *BLI_heap_popmin(Heap *heap)
176 {
177         void *ptr = heap->tree[0]->ptr;
178
179         heap->tree[0]->ptr = heap->freenodes;
180         heap->freenodes = heap->tree[0];
181
182         if (heap->size == 1)
183                 heap->size--;
184         else {
185                 HEAP_SWAP(heap, 0, heap->size-1);
186                 heap->size--;
187
188                 BLI_heap_down(heap, 0);
189         }
190
191         return ptr;
192 }
193
194 void BLI_heap_remove(Heap *heap, HeapNode *node)
195 {
196         int i = node->index;
197
198         while (i > 0) {
199                 int p = HEAP_PARENT(i);
200
201                 HEAP_SWAP(heap, p, i);
202                 i = p;
203         }
204
205         BLI_heap_popmin(heap);
206 }
207
208 float BLI_heap_node_value(HeapNode *node)
209 {
210         return node->value;
211 }
212
213 void *BLI_heap_node_ptr(HeapNode *node)
214 {
215         return node->ptr;
216 }
217