← Back to branch summary

~ubuntu-branches/ubuntu/gutsy/blender/gutsy-security

« back to all changes in this revision

Viewing changes to source/blender/blenlib/intern/BLI_heap.c

  • Committer: Bazaar Package Importer
  • Author(s): Lukas Fittl
  • Date: 2006-09-20 01:57:27 UTC
  • mfrom: (1.2.4 upstream)
  • Revision ID: james.westby@ubuntu.com-20060920015727-gmoqlxwstx9wwqs3
Tags: 2.42a-1ubuntu1
* Merge from Debian unstable (Closes: Malone #55903). Remaining changes:
  - debian/genpot: Add python scripts from Lee June <blender@eyou.com> to
    generate a reasonable PO template from the sources. Since gettext is used
    in a highly nonstandard way, xgettext does not work for this job.
  - debian/rules: Call the scripts, generate po/blender.pot, and clean it up
    in the clean target.
  - Add a proper header to the generated PO template.
* debian/control: Build depend on libavformat-dev >= 3:0.cvs20060823-3.1,
  otherwise this package will FTBFS

Show diffs side-by-side

added added

removed removed

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