FreeWRL / FreeX3D 4.3.0
priorityq-heap.c
1/*
2 * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
3 * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved.
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
11 *
12 * The above copyright notice including the dates of first publication and
13 * either this permission notice or a reference to
14 * http://oss.sgi.com/projects/FreeB/
15 * shall be included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
18 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
20 * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
21 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
22 * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 * SOFTWARE.
24 *
25 * Except as contained in this notice, the name of Silicon Graphics, Inc.
26 * shall not be used in advertising or otherwise to promote the sale, use or
27 * other dealings in this Software without prior written authorization from
28 * Silicon Graphics, Inc.
29 */
30/*
31** Author: Eric Veach, July 1994.
32**
33*/
34
35//JAS 2012 - this file is "included", should not be automatically included in
36//an automated build process, so have added the #ifdef IN_PRIORITY_QUEUE here and in
37//priorityq.c
38
39#ifdef IN_PRIORITY_QUEUE
40
41#include <stddef.h>
42#include <assert.h>
43#include "priorityq-heap.h"
44#include "memalloc.h"
45
46
47
48#define INIT_SIZE 32
49
50#define TRUE 1
51#define FALSE 0
52
53#ifdef FOR_TRITE_TEST_PROGRAM
54#define LEQ(x,y) (*pq->leq)(x,y)
55#else
56/* Violates modularity, but a little faster */
57#include "geom.h"
58#define LEQ(x,y) VertLeq((GLUvertex *)x, (GLUvertex *)y)
59#endif
60
61/* really __gl_pqHeapNewPriorityQ */
62PriorityQ *pqNewPriorityQ( int (*leq)(PQkey key1, PQkey key2) )
63{
64 PriorityQ *pq = (PriorityQ *)memAlloc( sizeof( PriorityQ ));
65 if (pq == NULL) return NULL;
66
67 pq->size = 0;
68 pq->max = INIT_SIZE;
69 pq->nodes = (PQnode *)memAlloc( (INIT_SIZE + 1) * sizeof(pq->nodes[0]) );
70 if (pq->nodes == NULL) {
71 memFree(pq);
72 return NULL;
73 }
74
75 pq->handles = (PQhandleElem *)memAlloc( (INIT_SIZE + 1) * sizeof(pq->handles[0]) );
76 if (pq->handles == NULL) {
77 memFree(pq->nodes);
78 memFree(pq);
79 return NULL;
80 }
81
82 pq->initialized = FALSE;
83 pq->freeList = 0;
84 pq->leq = leq;
85
86 pq->nodes[1].handle = 1; /* so that Minimum() returns NULL */
87 pq->handles[1].key = NULL;
88 return pq;
89}
90
91/* really __gl_pqHeapDeletePriorityQ */
92void pqDeletePriorityQ( PriorityQ *pq )
93{
94 memFree( pq->handles );
95 memFree( pq->nodes );
96 memFree( pq );
97}
98
99
100static void FloatDown( PriorityQ *pq, long curr )
101{
102 PQnode *n = pq->nodes;
103 PQhandleElem *h = pq->handles;
104 PQhandle hCurr, hChild;
105 long child;
106
107 hCurr = n[curr].handle;
108 for( ;; ) {
109 child = curr << 1;
110 if( child < pq->size && LEQ( h[n[child+1].handle].key,
111 h[n[child].handle].key )) {
112 ++child;
113 }
114
115 assert(child <= pq->max);
116
117 hChild = n[child].handle;
118 if( child > pq->size || LEQ( h[hCurr].key, h[hChild].key )) {
119 n[curr].handle = hCurr;
120 h[hCurr].node = curr;
121 break;
122 }
123 n[curr].handle = hChild;
124 h[hChild].node = curr;
125 curr = child;
126 }
127}
128
129
130static void FloatUp( PriorityQ *pq, long curr )
131{
132 PQnode *n = pq->nodes;
133 PQhandleElem *h = pq->handles;
134 PQhandle hCurr, hParent;
135 long parent;
136
137 hCurr = n[curr].handle;
138 for( ;; ) {
139 parent = curr >> 1;
140 hParent = n[parent].handle;
141 if( parent == 0 || LEQ( h[hParent].key, h[hCurr].key )) {
142 n[curr].handle = hCurr;
143 h[hCurr].node = curr;
144 break;
145 }
146 n[curr].handle = hParent;
147 h[hParent].node = curr;
148 curr = parent;
149 }
150}
151
152/* really __gl_pqHeapInit */
153void pqInit( PriorityQ *pq )
154{
155 long i;
156
157 /* This method of building a heap is O(n), rather than O(n lg n). */
158
159 for( i = pq->size; i >= 1; --i ) {
160 FloatDown( pq, i );
161 }
162 pq->initialized = TRUE;
163}
164
165/* really __gl_pqHeapInsert */
166/* returns LONG_MAX iff out of memory */
167PQhandle pqInsert( PriorityQ *pq, PQkey keyNew )
168{
169 long curr;
170 PQhandle free;
171
172 curr = ++ pq->size;
173 if( (curr*2) > pq->max ) {
174 PQnode *saveNodes= pq->nodes;
175 PQhandleElem *saveHandles= pq->handles;
176
177 /* If the heap overflows, double its size. */
178 pq->max <<= 1;
179 pq->nodes = (PQnode *)memRealloc( pq->nodes,
180 (size_t)
181 ((pq->max + 1) * sizeof( pq->nodes[0] )));
182 if (pq->nodes == NULL) {
183 pq->nodes = saveNodes; /* restore ptr to free upon return */
184 return LONG_MAX;
185 }
186 pq->handles = (PQhandleElem *)memRealloc( pq->handles,
187 (size_t)
188 ((pq->max + 1) *
189 sizeof( pq->handles[0] )));
190 if (pq->handles == NULL) {
191 pq->handles = saveHandles; /* restore ptr to free upon return */
192 return LONG_MAX;
193 }
194 }
195
196 if( pq->freeList == 0 ) {
197 free = curr;
198 } else {
199 free = pq->freeList;
200 pq->freeList = pq->handles[free].node;
201 }
202
203 pq->nodes[curr].handle = free;
204 pq->handles[free].node = curr;
205 pq->handles[free].key = keyNew;
206
207 if( pq->initialized ) {
208 FloatUp( pq, curr );
209 }
210 assert(free != LONG_MAX);
211 return free;
212}
213
214/* really __gl_pqHeapExtractMin */
215PQkey pqExtractMin( PriorityQ *pq )
216{
217 PQnode *n = pq->nodes;
218 PQhandleElem *h = pq->handles;
219 PQhandle hMin = n[1].handle;
220 PQkey min = h[hMin].key;
221
222 if( pq->size > 0 ) {
223 n[1].handle = n[pq->size].handle;
224 h[n[1].handle].node = 1;
225
226 h[hMin].key = NULL;
227 h[hMin].node = pq->freeList;
228 pq->freeList = hMin;
229
230 if( -- pq->size > 0 ) {
231 FloatDown( pq, 1 );
232 }
233 }
234 return min;
235}
236
237/* really __gl_pqHeapDelete */
238void pqDelete( PriorityQ *pq, PQhandle hCurr )
239{
240 PQnode *n = pq->nodes;
241 PQhandleElem *h = pq->handles;
242 long curr;
243
244 assert( hCurr >= 1 && hCurr <= pq->max && h[hCurr].key != NULL );
245
246 curr = h[hCurr].node;
247 n[curr].handle = n[pq->size].handle;
248 h[n[curr].handle].node = curr;
249
250 if( curr <= -- pq->size ) {
251 if( curr <= 1 || LEQ( h[n[curr>>1].handle].key, h[n[curr].handle].key )) {
252 FloatDown( pq, curr );
253 } else {
254 FloatUp( pq, curr );
255 }
256 }
257 h[hCurr].key = NULL;
258 h[hCurr].node = pq->freeList;
259 pq->freeList = hCurr;
260}
261
262#endif //IN_PRIORITY_QUEUE
263
Definition Viewer.h:139