1 /*
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:
9 **
10 ** http://oss.sgi.com/projects/FreeB
11 **
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.
17 **
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.
23 **
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.
33 **
34 */
35 /*
36 ** Author: Eric Veach, July 1994.
37 **
38 ** $Date$ $Revision$
39 ** $Header: //depot/main/gfx/lib/glu/libtess/priorityq.c#5 $
40 */
41
42 #include "gluos.h"
43 #include <stddef.h>
44 #include <assert.h>
45 #include <limits.h> /* LONG_MAX */
46 #include "memalloc.h"
47
48 /* Include all the code for the regular heap-based queue here. */
49
50 #include "priorityq-heap.c"
51
52 /* Now redefine all the function names to map to their "Sort" versions. */
53
54 #include "priorityq-sort.h"
55
56 /* really __gl_pqSortNewPriorityQ */
pqNewPriorityQ(int (* leq)(PQkey key1,PQkey key2))57 PriorityQ *pqNewPriorityQ( int (*leq)(PQkey key1, PQkey key2) )
58 {
59 PriorityQ *pq = (PriorityQ *)memAlloc( sizeof( PriorityQ ));
60 if (pq == NULL) return NULL;
61
62 pq->heap = __gl_pqHeapNewPriorityQ( leq );
63 if (pq->heap == NULL) {
64 memFree(pq);
65 return NULL;
66 }
67
68 pq->keys = (PQHeapKey *)memAlloc( INIT_SIZE * sizeof(pq->keys[0]) );
69 if (pq->keys == NULL) {
70 __gl_pqHeapDeletePriorityQ(pq->heap);
71 memFree(pq);
72 return NULL;
73 }
74
75 pq->size = 0;
76 pq->max = INIT_SIZE;
77 pq->initialized = FALSE;
78 pq->leq = leq;
79 return pq;
80 }
81
82 /* really __gl_pqSortDeletePriorityQ */
pqDeletePriorityQ(PriorityQ * pq)83 void pqDeletePriorityQ( PriorityQ *pq )
84 {
85 assert(pq != NULL);
86 if (pq->heap != NULL) __gl_pqHeapDeletePriorityQ( pq->heap );
87 if (pq->order != NULL) memFree( pq->order );
88 if (pq->keys != NULL) memFree( pq->keys );
89 memFree( pq );
90 }
91
92
93 #define LT(x,y) (! LEQ(y,x))
94 #define GT(x,y) (! LEQ(x,y))
95 #define Swap(a,b) do{PQkey *tmp = *a; *a = *b; *b = tmp;}while(0)
96
97 /* really __gl_pqSortInit */
pqInit(PriorityQ * pq)98 int pqInit( PriorityQ *pq )
99 {
100 PQkey **p, **r, **i, **j, *piv;
101 struct { PQkey **p, **r; } Stack[50], *top = Stack;
102 unsigned long seed = 2016473283;
103
104 /* Create an array of indirect pointers to the keys, so that we
105 * the handles we have returned are still valid.
106 */
107 /*
108 pq->order = (PQHeapKey **)memAlloc( (size_t)
109 (pq->size * sizeof(pq->order[0])) );
110 */
111 pq->order = (PQHeapKey **)memAlloc( (size_t)
112 ((pq->size+1) * sizeof(pq->order[0])) );
113 /* the previous line is a patch to compensate for the fact that IBM */
114 /* machines return a null on a malloc of zero bytes (unlike SGI), */
115 /* so we have to put in this defense to guard against a memory */
116 /* fault four lines down. from fossum@austin.ibm.com. */
117 if (pq->order == NULL) return 0;
118
119 p = pq->order;
120 r = p + pq->size - 1;
121 for( piv = pq->keys, i = p; i <= r; ++piv, ++i ) {
122 *i = piv;
123 }
124
125 /* Sort the indirect pointers in descending order,
126 * using randomized Quicksort
127 */
128 top->p = p; top->r = r; ++top;
129 while( --top >= Stack ) {
130 p = top->p;
131 r = top->r;
132 while( r > p + 10 ) {
133 seed = seed * 1539415821 + 1;
134 i = p + seed % (r - p + 1);
135 piv = *i;
136 *i = *p;
137 *p = piv;
138 i = p - 1;
139 j = r + 1;
140 do {
141 do { ++i; } while( GT( **i, *piv ));
142 do { --j; } while( LT( **j, *piv ));
143 Swap( i, j );
144 } while( i < j );
145 Swap( i, j ); /* Undo last swap */
146 if( i - p < r - j ) {
147 top->p = j+1; top->r = r; ++top;
148 r = i-1;
149 } else {
150 top->p = p; top->r = i-1; ++top;
151 p = j+1;
152 }
153 }
154 /* Insertion sort small lists */
155 for( i = p+1; i <= r; ++i ) {
156 piv = *i;
157 for( j = i; j > p && LT( **(j-1), *piv ); --j ) {
158 *j = *(j-1);
159 }
160 *j = piv;
161 }
162 }
163 pq->max = pq->size;
164 pq->initialized = TRUE;
165 __gl_pqHeapInit( pq->heap ); /* always succeeds */
166
167 #ifndef NDEBUG
168 p = pq->order;
169 r = p + pq->size - 1;
170 for( i = p; i < r; ++i ) {
171 assert( LEQ( **(i+1), **i ));
172 }
173 #endif
174
175 return 1;
176 }
177
178 /* really __gl_pqSortInsert */
179 /* returns LONG_MAX iff out of memory */
pqInsert(PriorityQ * pq,PQkey keyNew)180 PQhandle pqInsert( PriorityQ *pq, PQkey keyNew )
181 {
182 long curr;
183
184 if( pq->initialized ) {
185 return __gl_pqHeapInsert( pq->heap, keyNew );
186 }
187 curr = pq->size;
188 if( ++ pq->size >= pq->max ) {
189 PQkey *saveKey= pq->keys;
190
191 /* If the heap overflows, double its size. */
192 pq->max <<= 1;
193 pq->keys = (PQHeapKey *)memRealloc( pq->keys,
194 (size_t)
195 (pq->max * sizeof( pq->keys[0] )));
196 if (pq->keys == NULL) {
197 pq->keys = saveKey; /* restore ptr to free upon return */
198 return LONG_MAX;
199 }
200 }
201 assert(curr != LONG_MAX);
202 pq->keys[curr] = keyNew;
203
204 /* Negative handles index the sorted array. */
205 return -(curr+1);
206 }
207
208 /* really __gl_pqSortExtractMin */
pqExtractMin(PriorityQ * pq)209 PQkey pqExtractMin( PriorityQ *pq )
210 {
211 PQkey sortMin, heapMin;
212
213 if( pq->size == 0 ) {
214 return __gl_pqHeapExtractMin( pq->heap );
215 }
216 sortMin = *(pq->order[pq->size-1]);
217 if( ! __gl_pqHeapIsEmpty( pq->heap )) {
218 heapMin = __gl_pqHeapMinimum( pq->heap );
219 if( LEQ( heapMin, sortMin )) {
220 return __gl_pqHeapExtractMin( pq->heap );
221 }
222 }
223 do {
224 -- pq->size;
225 } while( pq->size > 0 && *(pq->order[pq->size-1]) == NULL );
226 return sortMin;
227 }
228
229 /* really __gl_pqSortMinimum */
pqMinimum(PriorityQ * pq)230 PQkey pqMinimum( PriorityQ *pq )
231 {
232 PQkey sortMin, heapMin;
233
234 if( pq->size == 0 ) {
235 return __gl_pqHeapMinimum( pq->heap );
236 }
237 sortMin = *(pq->order[pq->size-1]);
238 if( ! __gl_pqHeapIsEmpty( pq->heap )) {
239 heapMin = __gl_pqHeapMinimum( pq->heap );
240 if( LEQ( heapMin, sortMin )) {
241 return heapMin;
242 }
243 }
244 return sortMin;
245 }
246
247 /* really __gl_pqSortIsEmpty */
pqIsEmpty(PriorityQ * pq)248 int pqIsEmpty( PriorityQ *pq )
249 {
250 return (pq->size == 0) && __gl_pqHeapIsEmpty( pq->heap );
251 }
252
253 /* really __gl_pqSortDelete */
pqDelete(PriorityQ * pq,PQhandle curr)254 void pqDelete( PriorityQ *pq, PQhandle curr )
255 {
256 if( curr >= 0 ) {
257 __gl_pqHeapDelete( pq->heap, curr );
258 return;
259 }
260 curr = -(curr+1);
261 assert( curr < pq->max && pq->keys[curr] != NULL );
262
263 pq->keys[curr] = NULL;
264 while( pq->size > 0 && *(pq->order[pq->size-1]) == NULL ) {
265 -- pq->size;
266 }
267 }
268