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