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 */
58 PriorityQ *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 */
88 void pqDeletePriorityQ( PriorityQ *pq )
89 {
90   memFree( pq->handles );
91   memFree( pq->nodes );
92   memFree( pq );
93 }
94 
95 
96 static 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 
126 static 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 */
149 void 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 */
163 PQhandle pqInsert( PriorityQ *pq, PQkey keyNew )
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     }
182     pq->handles = (PQhandleElem *)memRealloc( pq->handles,
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 */
211 PQkey pqExtractMin( PriorityQ *pq )
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 */
234 void 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 }
257