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