c6b99cce55200f85daada9db4b01823964821f99
2 * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
3 * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved.
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:
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.
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
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.
31 ** Author: Eric Veach, July 1994.
38 #include <limits.h> /* LONG_MAX */
41 /* Include all the code for the regular heap-based queue here. */
43 #include "priorityq-heap.c"
45 /* Now redefine all the function names to map to their "Sort" versions. */
47 #include "priorityq-sort.h"
49 /* really __gl_pqSortNewPriorityQ */
50 PriorityQ
*pqNewPriorityQ( int (*leq
)(PQkey key1
, PQkey key2
) )
52 PriorityQ
*pq
= (PriorityQ
*)memAlloc( sizeof( PriorityQ
));
53 if (pq
== NULL
) return NULL
;
55 pq
->heap
= __gl_pqHeapNewPriorityQ( leq
);
56 if (pq
->heap
== NULL
) {
61 pq
->keys
= (PQHeapKey
*)memAlloc( INIT_SIZE
* sizeof(pq
->keys
[0]) );
62 if (pq
->keys
== NULL
) {
63 __gl_pqHeapDeletePriorityQ(pq
->heap
);
70 pq
->initialized
= FALSE
;
75 /* really __gl_pqSortDeletePriorityQ */
76 void pqDeletePriorityQ( PriorityQ
*pq
)
79 if (pq
->heap
!= NULL
) __gl_pqHeapDeletePriorityQ( pq
->heap
);
80 if (pq
->order
!= NULL
) memFree( pq
->order
);
81 if (pq
->keys
!= NULL
) memFree( pq
->keys
);
86 #define LT(x,y) (! LEQ(y,x))
87 #define GT(x,y) (! LEQ(x,y))
88 #define Swap(a,b) do{PQkey *tmp = *a; *a = *b; *b = tmp;}while(0)
90 /* really __gl_pqSortInit */
91 int pqInit( PriorityQ
*pq
)
93 PQkey
**p
, **r
, **i
, **j
, *piv
;
94 struct { PQkey
**p
, **r
; } Stack
[50], *top
= Stack
;
95 unsigned long seed
= 2016473283;
97 /* Create an array of indirect pointers to the keys, so that we
98 * the handles we have returned are still valid.
101 pq->order = (PQHeapKey **)memAlloc( (size_t)
102 (pq->size * sizeof(pq->order[0])) );
104 pq
->order
= (PQHeapKey
**)memAlloc( (size_t)
105 ((pq
->size
+1) * sizeof(pq
->order
[0])) );
106 /* the previous line is a patch to compensate for the fact that IBM */
107 /* machines return a null on a malloc of zero bytes (unlike SGI), */
108 /* so we have to put in this defense to guard against a memory */
109 /* fault four lines down. from fossum@austin.ibm.com. */
110 if (pq
->order
== NULL
) return 0;
113 r
= p
+ pq
->size
- 1;
114 for( piv
= pq
->keys
, i
= p
; i
<= r
; ++piv
, ++i
) {
118 /* Sort the indirect pointers in descending order,
119 * using randomized Quicksort
121 top
->p
= p
; top
->r
= r
; ++top
;
122 while( --top
>= Stack
) {
125 while( r
> p
+ 10 ) {
126 seed
= seed
* 1539415821 + 1;
127 i
= p
+ seed
% (r
- p
+ 1);
134 do { ++i
; } while( GT( **i
, *piv
));
135 do { --j
; } while( LT( **j
, *piv
));
138 Swap( i
, j
); /* Undo last swap */
139 if( i
- p
< r
- j
) {
140 top
->p
= j
+1; top
->r
= r
; ++top
;
143 top
->p
= p
; top
->r
= i
-1; ++top
;
147 /* Insertion sort small lists */
148 for( i
= p
+1; i
<= r
; ++i
) {
150 for( j
= i
; j
> p
&& LT( **(j
-1), *piv
); --j
) {
157 pq
->initialized
= TRUE
;
158 __gl_pqHeapInit( pq
->heap
); /* always succeeds */
162 r
= p
+ pq
->size
- 1;
163 for( i
= p
; i
< r
; ++i
) {
164 assert( LEQ( **(i
+1), **i
));
171 /* really __gl_pqSortInsert */
172 /* returns LONG_MAX iff out of memory */
173 PQhandle
pqInsert( PriorityQ
*pq
, PQkey keyNew
)
177 if( pq
->initialized
) {
178 return __gl_pqHeapInsert( pq
->heap
, keyNew
);
181 if( ++ pq
->size
>= pq
->max
) {
182 PQkey
*saveKey
= pq
->keys
;
184 /* If the heap overflows, double its size. */
186 pq
->keys
= (PQHeapKey
*)memRealloc( pq
->keys
,
188 (pq
->max
* sizeof( pq
->keys
[0] )));
189 if (pq
->keys
== NULL
) {
190 pq
->keys
= saveKey
; /* restore ptr to free upon return */
194 assert(curr
!= LONG_MAX
);
195 pq
->keys
[curr
] = keyNew
;
197 /* Negative handles index the sorted array. */
201 /* really __gl_pqSortExtractMin */
202 PQkey
pqExtractMin( PriorityQ
*pq
)
204 PQkey sortMin
, heapMin
;
206 if( pq
->size
== 0 ) {
207 return __gl_pqHeapExtractMin( pq
->heap
);
209 sortMin
= *(pq
->order
[pq
->size
-1]);
210 if( ! __gl_pqHeapIsEmpty( pq
->heap
)) {
211 heapMin
= __gl_pqHeapMinimum( pq
->heap
);
212 if( LEQ( heapMin
, sortMin
)) {
213 return __gl_pqHeapExtractMin( pq
->heap
);
218 } while( pq
->size
> 0 && *(pq
->order
[pq
->size
-1]) == NULL
);
222 /* really __gl_pqSortMinimum */
223 PQkey
pqMinimum( PriorityQ
*pq
)
225 PQkey sortMin
, heapMin
;
227 if( pq
->size
== 0 ) {
228 return __gl_pqHeapMinimum( pq
->heap
);
230 sortMin
= *(pq
->order
[pq
->size
-1]);
231 if( ! __gl_pqHeapIsEmpty( pq
->heap
)) {
232 heapMin
= __gl_pqHeapMinimum( pq
->heap
);
233 if( LEQ( heapMin
, sortMin
)) {
240 /* really __gl_pqSortIsEmpty */
241 int pqIsEmpty( PriorityQ
*pq
)
243 return (pq
->size
== 0) && __gl_pqHeapIsEmpty( pq
->heap
);
246 /* really __gl_pqSortDelete */
247 void pqDelete( PriorityQ
*pq
, PQhandle curr
)
250 __gl_pqHeapDelete( pq
->heap
, curr
);
254 assert( curr
< pq
->max
&& pq
->keys
[curr
] != NULL
);
256 pq
->keys
[curr
] = NULL
;
257 while( pq
->size
> 0 && *(pq
->order
[pq
->size
-1]) == NULL
) {