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 */ 50 PriorityQ *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 */ 77 void pqDeletePriorityQ( PriorityQ *pq ) 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 */ 92 int 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 */ 174 PQhandle pqInsert( PriorityQ *pq, PQkey keyNew ) 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 */ 203 PQkey pqExtractMin( PriorityQ *pq ) 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 */ 224 PQkey pqMinimum( PriorityQ *pq ) 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 */ 242 int pqIsEmpty( PriorityQ *pq ) 243 { 244 return (pq->size == 0) && __gl_pqHeapIsEmpty( pq->heap ); 245 } 246 247 /* really __gl_pqSortDelete */ 248 void 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 } 262