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