2 ** License Applicability. Except to the extent portions of this file are
3 ** made subject to an alternative license as permitted in the SGI Free
4 ** Software License B, Version 1.1 (the "License"), the contents of this
5 ** file are subject only to the provisions of the License. You may not use
6 ** this file except in compliance with the License. You may obtain a copy
7 ** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
8 ** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
10 ** http://oss.sgi.com/projects/FreeB
12 ** Note that, as provided in the License, the Software is distributed on an
13 ** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
14 ** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
15 ** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
16 ** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
18 ** Original Code. The Original Code is: OpenGL Sample Implementation,
19 ** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
20 ** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
21 ** Copyright in any portions created by third parties is as indicated
22 ** elsewhere herein. All Rights Reserved.
24 ** Additional Notice Provisions: The application programming interfaces
25 ** established by SGI in conjunction with the Original Code are The
26 ** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
27 ** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
28 ** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
29 ** Window System(R) (Version 1.3), released October 19, 1998. This software
30 ** was created using the OpenGL(R) version 1.2.1 Sample Implementation
31 ** published by SGI, but has not been independently verified as being
32 ** compliant with the OpenGL(R) version 1.2.1 Specification.
36 ** Author: Eric Veach, July 1994.
42 #include "priorityq-heap.h"
50 #ifdef FOR_TRITE_TEST_PROGRAM
51 #define LEQ(x,y) (*pq->leq)(x,y)
53 /* Violates modularity, but a little faster */
55 #define LEQ(x,y) VertLeq((GLUvertex *)x, (GLUvertex *)y)
58 /* really __gl_pqHeapNewPriorityQ */
59 PriorityQ
*pqNewPriorityQ( int (*leq
)(PQkey key1
, PQkey key2
) )
61 PriorityQ
*pq
= (PriorityQ
*)memAlloc( sizeof( PriorityQ
));
62 if (pq
== NULL
) return NULL
;
66 pq
->nodes
= (PQnode
*)memAlloc( (INIT_SIZE
+ 1) * sizeof(pq
->nodes
[0]) );
67 if (pq
->nodes
== NULL
) {
72 pq
->handles
= (PQhandleElem
*)memAlloc( (INIT_SIZE
+ 1) * sizeof(pq
->handles
[0]) );
73 if (pq
->handles
== NULL
) {
79 pq
->initialized
= FALSE
;
83 pq
->nodes
[1].handle
= 1; /* so that Minimum() returns NULL */
84 pq
->handles
[1].key
= NULL
;
88 /* really __gl_pqHeapDeletePriorityQ */
89 void pqDeletePriorityQ( PriorityQ
*pq
)
91 memFree( pq
->handles
);
97 static void FloatDown( PriorityQ
*pq
, long curr
)
99 PQnode
*n
= pq
->nodes
;
100 PQhandleElem
*h
= pq
->handles
;
101 PQhandle hCurr
, hChild
;
104 hCurr
= n
[curr
].handle
;
107 if( child
< pq
->size
&& LEQ( h
[n
[child
+1].handle
].key
,
108 h
[n
[child
].handle
].key
)) {
112 assert(child
<= pq
->max
);
114 hChild
= n
[child
].handle
;
115 if( child
> pq
->size
|| LEQ( h
[hCurr
].key
, h
[hChild
].key
)) {
116 n
[curr
].handle
= hCurr
;
117 h
[hCurr
].node
= curr
;
120 n
[curr
].handle
= hChild
;
121 h
[hChild
].node
= curr
;
127 static void FloatUp( PriorityQ
*pq
, long curr
)
129 PQnode
*n
= pq
->nodes
;
130 PQhandleElem
*h
= pq
->handles
;
131 PQhandle hCurr
, hParent
;
134 hCurr
= n
[curr
].handle
;
137 hParent
= n
[parent
].handle
;
138 if( parent
== 0 || LEQ( h
[hParent
].key
, h
[hCurr
].key
)) {
139 n
[curr
].handle
= hCurr
;
140 h
[hCurr
].node
= curr
;
143 n
[curr
].handle
= hParent
;
144 h
[hParent
].node
= curr
;
149 /* really __gl_pqHeapInit */
150 void pqInit( PriorityQ
*pq
)
154 /* This method of building a heap is O(n), rather than O(n lg n). */
156 for( i
= pq
->size
; i
>= 1; --i
) {
159 pq
->initialized
= TRUE
;
162 /* really __gl_pqHeapInsert */
163 /* returns LONG_MAX iff out of memory */
164 PQhandle
pqInsert( PriorityQ
*pq
, PQkey keyNew
)
170 if( (curr
*2) > pq
->max
) {
171 PQnode
*saveNodes
= pq
->nodes
;
172 PQhandleElem
*saveHandles
= pq
->handles
;
174 /* If the heap overflows, double its size. */
176 pq
->nodes
= (PQnode
*)memRealloc( pq
->nodes
,
178 ((pq
->max
+ 1) * sizeof( pq
->nodes
[0] )));
179 if (pq
->nodes
== NULL
) {
180 pq
->nodes
= saveNodes
; /* restore ptr to free upon return */
183 pq
->handles
= (PQhandleElem
*)memRealloc( pq
->handles
,
186 sizeof( pq
->handles
[0] )));
187 if (pq
->handles
== NULL
) {
188 pq
->handles
= saveHandles
; /* restore ptr to free upon return */
193 if( pq
->freeList
== 0 ) {
197 pq
->freeList
= pq
->handles
[free
].node
;
200 pq
->nodes
[curr
].handle
= free
;
201 pq
->handles
[free
].node
= curr
;
202 pq
->handles
[free
].key
= keyNew
;
204 if( pq
->initialized
) {
207 assert(free
!= LONG_MAX
);
211 /* really __gl_pqHeapExtractMin */
212 PQkey
pqExtractMin( PriorityQ
*pq
)
214 PQnode
*n
= pq
->nodes
;
215 PQhandleElem
*h
= pq
->handles
;
216 PQhandle hMin
= n
[1].handle
;
217 PQkey min
= h
[hMin
].key
;
220 n
[1].handle
= n
[pq
->size
].handle
;
221 h
[n
[1].handle
].node
= 1;
224 h
[hMin
].node
= pq
->freeList
;
227 if( -- pq
->size
> 0 ) {
234 /* really __gl_pqHeapDelete */
235 void pqDelete( PriorityQ
*pq
, PQhandle hCurr
)
237 PQnode
*n
= pq
->nodes
;
238 PQhandleElem
*h
= pq
->handles
;
241 assert( hCurr
>= 1 && hCurr
<= pq
->max
&& h
[hCurr
].key
!= NULL
);
243 curr
= h
[hCurr
].node
;
244 n
[curr
].handle
= n
[pq
->size
].handle
;
245 h
[n
[curr
].handle
].node
= curr
;
247 if( curr
<= -- pq
->size
) {
248 if( curr
<= 1 || LEQ( h
[n
[curr
>>1].handle
].key
, h
[n
[curr
].handle
].key
)) {
249 FloatDown( pq
, curr
);
255 h
[hCurr
].node
= pq
->freeList
;
256 pq
->freeList
= hCurr
;