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.
43 #include <limits.h> /* LONG_MAX */
46 /* Include all the code for the regular heap-based queue here. */
48 #include "priorityq-heap.c"
50 /* Now redefine all the function names to map to their "Sort" versions. */
52 #include "priorityq-sort.h"
54 /* really __gl_pqSortNewPriorityQ */
55 PriorityQ
*pqNewPriorityQ( int (*leq
)(PQkey key1
, PQkey key2
) )
57 PriorityQ
*pq
= (PriorityQ
*)memAlloc( sizeof( PriorityQ
));
58 if (pq
== NULL
) return NULL
;
60 pq
->heap
= __gl_pqHeapNewPriorityQ( leq
);
61 if (pq
->heap
== NULL
) {
66 pq
->keys
= (PQHeapKey
*)memAlloc( INIT_SIZE
* sizeof(pq
->keys
[0]) );
67 if (pq
->keys
== NULL
) {
68 __gl_pqHeapDeletePriorityQ(pq
->heap
);
75 pq
->initialized
= FALSE
;
80 /* really __gl_pqSortDeletePriorityQ */
81 void pqDeletePriorityQ( PriorityQ
*pq
)
84 if (pq
->heap
!= NULL
) __gl_pqHeapDeletePriorityQ( pq
->heap
);
85 if (pq
->order
!= NULL
) memFree( pq
->order
);
86 if (pq
->keys
!= NULL
) memFree( pq
->keys
);
91 #define LT(x,y) (! LEQ(y,x))
92 #define GT(x,y) (! LEQ(x,y))
93 #define Swap(a,b) if(1){PQkey *tmp = *a; *a = *b; *b = tmp;}else
95 /* really __gl_pqSortInit */
96 int pqInit( PriorityQ
*pq
)
98 PQkey
**p
, **r
, **i
, **j
, *piv
;
99 struct { PQkey
**p
, **r
; } Stack
[50], *top
= Stack
;
100 unsigned long seed
= 2016473283;
102 /* Create an array of indirect pointers to the keys, so that we
103 * the handles we have returned are still valid.
106 pq->order = (PQHeapKey **)memAlloc( (size_t)
107 (pq->size * sizeof(pq->order[0])) );
109 pq
->order
= (PQHeapKey
**)memAlloc( (size_t)
110 ((pq
->size
+1) * sizeof(pq
->order
[0])) );
111 /* the previous line is a patch to compensate for the fact that IBM */
112 /* machines return a null on a malloc of zero bytes (unlike SGI), */
113 /* so we have to put in this defense to guard against a memory */
114 /* fault four lines down. from fossum@austin.ibm.com. */
115 if (pq
->order
== NULL
) return 0;
118 r
= p
+ pq
->size
- 1;
119 for( piv
= pq
->keys
, i
= p
; i
<= r
; ++piv
, ++i
) {
123 /* Sort the indirect pointers in descending order,
124 * using randomized Quicksort
126 top
->p
= p
; top
->r
= r
; ++top
;
127 while( --top
>= Stack
) {
130 while( r
> p
+ 10 ) {
131 seed
= seed
* 1539415821 + 1;
132 i
= p
+ seed
% (r
- p
+ 1);
139 do { ++i
; } while( GT( **i
, *piv
));
140 do { --j
; } while( LT( **j
, *piv
));
143 Swap( i
, j
); /* Undo last swap */
144 if( i
- p
< r
- j
) {
145 top
->p
= j
+1; top
->r
= r
; ++top
;
148 top
->p
= p
; top
->r
= i
-1; ++top
;
152 /* Insertion sort small lists */
153 for( i
= p
+1; i
<= r
; ++i
) {
155 for( j
= i
; j
> p
&& LT( **(j
-1), *piv
); --j
) {
162 pq
->initialized
= TRUE
;
163 __gl_pqHeapInit( pq
->heap
); /* always succeeds */
167 r
= p
+ pq
->size
- 1;
168 for( i
= p
; i
< r
; ++i
) {
169 assert( LEQ( **(i
+1), **i
));
176 /* really __gl_pqSortInsert */
177 /* returns LONG_MAX iff out of memory */
178 PQhandle
pqInsert( PriorityQ
*pq
, PQkey keyNew
)
182 if( pq
->initialized
) {
183 return __gl_pqHeapInsert( pq
->heap
, keyNew
);
186 if( ++ pq
->size
>= pq
->max
) {
187 PQkey
*saveKey
= pq
->keys
;
189 /* If the heap overflows, double its size. */
191 pq
->keys
= (PQHeapKey
*)memRealloc( pq
->keys
,
193 (pq
->max
* sizeof( pq
->keys
[0] )));
194 if (pq
->keys
== NULL
) {
195 pq
->keys
= saveKey
; /* restore ptr to free upon return */
199 assert(curr
!= LONG_MAX
);
200 pq
->keys
[curr
] = keyNew
;
202 /* Negative handles index the sorted array. */
206 /* really __gl_pqSortExtractMin */
207 PQkey
pqExtractMin( PriorityQ
*pq
)
209 PQkey sortMin
, heapMin
;
211 if( pq
->size
== 0 ) {
212 return __gl_pqHeapExtractMin( pq
->heap
);
214 sortMin
= *(pq
->order
[pq
->size
-1]);
215 if( ! __gl_pqHeapIsEmpty( pq
->heap
)) {
216 heapMin
= __gl_pqHeapMinimum( pq
->heap
);
217 if( LEQ( heapMin
, sortMin
)) {
218 return __gl_pqHeapExtractMin( pq
->heap
);
223 } while( pq
->size
> 0 && *(pq
->order
[pq
->size
-1]) == NULL
);
227 /* really __gl_pqSortMinimum */
228 PQkey
pqMinimum( PriorityQ
*pq
)
230 PQkey sortMin
, heapMin
;
232 if( pq
->size
== 0 ) {
233 return __gl_pqHeapMinimum( pq
->heap
);
235 sortMin
= *(pq
->order
[pq
->size
-1]);
236 if( ! __gl_pqHeapIsEmpty( pq
->heap
)) {
237 heapMin
= __gl_pqHeapMinimum( pq
->heap
);
238 if( LEQ( heapMin
, sortMin
)) {
245 /* really __gl_pqSortIsEmpty */
246 int pqIsEmpty( PriorityQ
*pq
)
248 return (pq
->size
== 0) && __gl_pqHeapIsEmpty( pq
->heap
);
251 /* really __gl_pqSortDelete */
252 void pqDelete( PriorityQ
*pq
, PQhandle curr
)
255 __gl_pqHeapDelete( pq
->heap
, curr
);
259 assert( curr
< pq
->max
&& pq
->keys
[curr
] != NULL
);
261 pq
->keys
[curr
] = NULL
;
262 while( pq
->size
> 0 && *(pq
->order
[pq
->size
-1]) == NULL
) {