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 */ 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 */ 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 */ 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 (at) 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 */ 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 */ 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 */ 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 */ 248 int pqIsEmpty( PriorityQ *pq ) 249 { 250 return (pq->size == 0) && __gl_pqHeapIsEmpty( pq->heap ); 251 } 252 253 /* really __gl_pqSortDelete */ 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
