Logo ROOT  
Reference Guide
priorityq-heap.c
Go to the documentation of this file.
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#include <stddef.h>
36#include <assert.h>
37#include "priorityq-heap.h"
38#include "memalloc.h"
39
40#define INIT_SIZE 32
41
42#ifndef TRUE
43#define TRUE 1
44#endif
45#ifndef FALSE
46#define FALSE 0
47#endif
48
49#ifdef FOR_TRITE_TEST_PROGRAM
50#define LEQ(x,y) (*pq->leq)(x,y)
51#else
52/* Violates modularity, but a little faster */
53#include "geom.h"
54#define LEQ(x,y) VertLeq((GLUvertex *)x, (GLUvertex *)y)
55#endif
56
57/* really __gl_pqHeapNewPriorityQ */
58PriorityQ *pqNewPriorityQ( int (*leq)(PQkey key1, PQkey key2) )
59{
60 PriorityQ *pq = (PriorityQ *)memAlloc( sizeof( PriorityQ ));
61 if (pq == NULL) return NULL;
62
63 pq->size = 0;
64 pq->max = INIT_SIZE;
65 pq->nodes = (PQnode *)memAlloc( (INIT_SIZE + 1) * sizeof(pq->nodes[0]) );
66 if (pq->nodes == NULL) {
67 memFree(pq);
68 return NULL;
69 }
70
71 pq->handles = (PQhandleElem *)memAlloc( (INIT_SIZE + 1) * sizeof(pq->handles[0]) );
72 if (pq->handles == NULL) {
73 memFree(pq->nodes);
74 memFree(pq);
75 return NULL;
76 }
77
78 pq->initialized = FALSE;
79 pq->freeList = 0;
80 pq->leq = leq;
81
82 pq->nodes[1].handle = 1; /* so that Minimum() returns NULL */
83 pq->handles[1].key = NULL;
84 return pq;
85}
86
87/* really __gl_pqHeapDeletePriorityQ */
89{
90 memFree( pq->handles );
91 memFree( pq->nodes );
92 memFree( pq );
93}
94
95
96static void FloatDown( PriorityQ *pq, long curr )
97{
98 PQnode *n = pq->nodes;
99 PQhandleElem *h = pq->handles;
100 PQhandle hCurr, hChild;
101 long child;
102
103 hCurr = n[curr].handle;
104 for( ;; ) {
105 child = curr << 1;
106 if( child < pq->size && LEQ( h[n[child+1].handle].key,
107 h[n[child].handle].key )) {
108 ++child;
109 }
110
111 assert(child <= pq->max);
112
113 hChild = n[child].handle;
114 if( child > pq->size || LEQ( h[hCurr].key, h[hChild].key )) {
115 n[curr].handle = hCurr;
116 h[hCurr].node = curr;
117 break;
118 }
119 n[curr].handle = hChild;
120 h[hChild].node = curr;
121 curr = child;
122 }
123}
124
125
126static void FloatUp( PriorityQ *pq, long curr )
127{
128 PQnode *n = pq->nodes;
129 PQhandleElem *h = pq->handles;
130 PQhandle hCurr, hParent;
131 long parent;
132
133 hCurr = n[curr].handle;
134 for( ;; ) {
135 parent = curr >> 1;
136 hParent = n[parent].handle;
137 if( parent == 0 || LEQ( h[hParent].key, h[hCurr].key )) {
138 n[curr].handle = hCurr;
139 h[hCurr].node = curr;
140 break;
141 }
142 n[curr].handle = hParent;
143 h[hParent].node = curr;
144 curr = parent;
145 }
146}
147
148/* really __gl_pqHeapInit */
149void pqInit( PriorityQ *pq )
150{
151 long i;
152
153 /* This method of building a heap is O(n), rather than O(n lg n). */
154
155 for( i = pq->size; i >= 1; --i ) {
156 FloatDown( pq, i );
157 }
158 pq->initialized = TRUE;
159}
160
161/* really __gl_pqHeapInsert */
162/* returns LONG_MAX iff out of memory */
164{
165 long curr;
166 PQhandle free_handle;
167
168 curr = ++ pq->size;
169 if( (curr*2) > pq->max ) {
170 PQnode *saveNodes= pq->nodes;
171 PQhandleElem *saveHandles= pq->handles;
172
173 /* If the heap overflows, double its size. */
174 pq->max <<= 1;
175 pq->nodes = (PQnode *)memRealloc( pq->nodes,
176 (size_t)
177 ((pq->max + 1) * sizeof( pq->nodes[0] )));
178 if (pq->nodes == NULL) {
179 pq->nodes = saveNodes; /* restore ptr to free upon return */
180 return LONG_MAX;
181 }
183 (size_t)
184 ((pq->max + 1) *
185 sizeof( pq->handles[0] )));
186 if (pq->handles == NULL) {
187 pq->handles = saveHandles; /* restore ptr to free upon return */
188 return LONG_MAX;
189 }
190 }
191
192 if( pq->freeList == 0 ) {
193 free_handle = curr;
194 } else {
195 free_handle = pq->freeList;
196 pq->freeList = pq->handles[free_handle].node;
197 }
198
199 pq->nodes[curr].handle = free_handle;
200 pq->handles[free_handle].node = curr;
201 pq->handles[free_handle].key = keyNew;
202
203 if( pq->initialized ) {
204 FloatUp( pq, curr );
205 }
206 assert(free_handle != LONG_MAX);
207 return free_handle;
208}
209
210/* really __gl_pqHeapExtractMin */
212{
213 PQnode *n = pq->nodes;
214 PQhandleElem *h = pq->handles;
215 PQhandle hMin = n[1].handle;
216 PQkey min = h[hMin].key;
217
218 if( pq->size > 0 ) {
219 n[1].handle = n[pq->size].handle;
220 h[n[1].handle].node = 1;
221
222 h[hMin].key = NULL;
223 h[hMin].node = pq->freeList;
224 pq->freeList = hMin;
225
226 if( -- pq->size > 0 ) {
227 FloatDown( pq, 1 );
228 }
229 }
230 return min;
231}
232
233/* really __gl_pqHeapDelete */
234void pqDelete( PriorityQ *pq, PQhandle hCurr )
235{
236 PQnode *n = pq->nodes;
237 PQhandleElem *h = pq->handles;
238 long curr;
239
240 assert( hCurr >= 1 && hCurr <= pq->max && h[hCurr].key != NULL );
241
242 curr = h[hCurr].node;
243 n[curr].handle = n[pq->size].handle;
244 h[n[curr].handle].node = curr;
245
246 if( curr <= -- pq->size ) {
247 if( curr <= 1 || LEQ( h[n[curr>>1].handle].key, h[n[curr].handle].key )) {
248 FloatDown( pq, curr );
249 } else {
250 FloatUp( pq, curr );
251 }
252 }
253 h[hCurr].key = NULL;
254 h[hCurr].node = pq->freeList;
255 pq->freeList = hCurr;
256}
#define h(i)
Definition: RSha256.hxx:106
const Int_t n
Definition: legend1.C:16
#define memAlloc
Definition: memalloc.h:48
#define memRealloc
Definition: memalloc.h:40
#define memFree
Definition: memalloc.h:41
void pqInit(PriorityQ *pq)
#define LEQ(x, y)
static void FloatDown(PriorityQ *pq, long curr)
void pqDeletePriorityQ(PriorityQ *pq)
#define INIT_SIZE
#define TRUE
#define FALSE
PriorityQ * pqNewPriorityQ(int(*leq)(PQkey key1, PQkey key2))
static void FloatUp(PriorityQ *pq, long curr)
void pqDelete(PriorityQ *pq, PQhandle hCurr)
PQkey pqExtractMin(PriorityQ *pq)
PQhandle pqInsert(PriorityQ *pq, PQkey keyNew)
long PQhandle
void * PQkey
PQhandle node
PQhandle handle
PQnode * nodes
PQhandleElem * handles
PQhandle freeList
int(* leq)(PQkey key1, PQkey key2)