dlls/glu32/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 <stdarg.h>
  36 #include <assert.h>
  37 #include <limits.h>             /* LONG_MAX */
  38
  39 #include "windef.h"
  40 #include "winbase.h"
  41 #include "tess.h"
  42
  43 /* Include all the code for the regular heap-based queue here. */
  44
  45 typedef struct PriorityQHeap PriorityQHeap;
  46 typedef struct { PQhandle handle; } PQnode;
  47 typedef struct { PQkey key; PQhandle node; } PQhandleElem;
  48
  49 struct PriorityQHeap {
  50   PQnode        *nodes;
  51   PQhandleElem  *handles;
  52   long          size, max;
  53   PQhandle      freeList;
  54   int           initialized;
  55   int           (*leq)(PQkey key1, PQkey key2);
  56 };
  57
  58 #define __gl_pqHeapMinimum(pq)  ((pq)->handles[(pq)->nodes[1].handle].key)
  59 #define __gl_pqHeapIsEmpty(pq)  ((pq)->size == 0)
  60
  61 #define INIT_SIZE       32
  62
  63 /* Violates modularity, but a little faster */
  64 #define LEQ(x,y)        VertLeq((GLUvertex *)x, (GLUvertex *)y)
  65
  66 static PriorityQHeap *__gl_pqHeapNewPriorityQ( int (*leq)(PQkey key1, PQkey key2) )
  67 {
  68   PriorityQHeap *pq = HeapAlloc( GetProcessHeap(), 0, sizeof( PriorityQHeap ));
  69   if (pq == NULL) return NULL;
  70
  71   pq->size = 0;
  72   pq->max = INIT_SIZE;
  73   pq->nodes = HeapAlloc( GetProcessHeap(), 0, (INIT_SIZE + 1) * sizeof(pq->nodes[0]) );
  74   if (pq->nodes == NULL) {
  75      HeapFree( GetProcessHeap(), 0, pq );
  76      return NULL;
  77   }
  78
  79   pq->handles = HeapAlloc( GetProcessHeap(), 0, (INIT_SIZE + 1) * sizeof(pq->handles[0]) );
  80   if (pq->handles == NULL) {
  81      HeapFree( GetProcessHeap(), 0, pq->nodes );
  82      HeapFree( GetProcessHeap(), 0, pq );
  83      return NULL;
  84   }
  85
  86   pq->initialized = FALSE;
  87   pq->freeList = 0;
  88   pq->leq = leq;
  89
  90   pq->nodes[1].handle = 1;      /* so that Minimum() returns NULL */
  91   pq->handles[1].key = NULL;
  92   return pq;
  93 }
  94
  95 static void __gl_pqHeapDeletePriorityQ( PriorityQHeap *pq )
  96 {
  97   HeapFree( GetProcessHeap(), 0, pq->handles );
  98   HeapFree( GetProcessHeap(), 0, pq->nodes );
  99   HeapFree( GetProcessHeap(), 0, pq );
 100 }
 101
 102
 103 static void FloatDown( PriorityQHeap *pq, long curr )
 104 {
 105   PQnode *n = pq->nodes;
 106   PQhandleElem *h = pq->handles;
 107   PQhandle hCurr, hChild;
 108   long child;
 109
 110   hCurr = n[curr].handle;
 111   for( ;; ) {
 112     child = curr << 1;
 113     if( child < pq->size && LEQ( h[n[child+1].handle].key,
 114                                  h[n[child].handle].key )) {
 115       ++child;
 116     }
 117
 118     assert(child <= pq->max);
 119
 120     hChild = n[child].handle;
 121     if( child > pq->size || LEQ( h[hCurr].key, h[hChild].key )) {
 122       n[curr].handle = hCurr;
 123       h[hCurr].node = curr;
 124       break;
 125     }
 126     n[curr].handle = hChild;
 127     h[hChild].node = curr;
 128     curr = child;
 129   }
 130 }
 131
 132
 133 static void FloatUp( PriorityQHeap *pq, long curr )
 134 {
 135   PQnode *n = pq->nodes;
 136   PQhandleElem *h = pq->handles;
 137   PQhandle hCurr, hParent;
 138   long parent;
 139
 140   hCurr = n[curr].handle;
 141   for( ;; ) {
 142     parent = curr >> 1;
 143     hParent = n[parent].handle;
 144     if( parent == 0 || LEQ( h[hParent].key, h[hCurr].key )) {
 145       n[curr].handle = hCurr;
 146       h[hCurr].node = curr;
 147       break;
 148     }
 149     n[curr].handle = hParent;
 150     h[hParent].node = curr;
 151     curr = parent;
 152   }
 153 }
 154
 155 static void __gl_pqHeapInit( PriorityQHeap *pq )
 156 {
 157   long i;
 158
 159   /* This method of building a heap is O(n), rather than O(n lg n). */
 160
 161   for( i = pq->size; i >= 1; --i ) {
 162     FloatDown( pq, i );
 163   }
 164   pq->initialized = TRUE;
 165 }
 166
 167 /* returns LONG_MAX iff out of memory */
 168 static PQhandle __gl_pqHeapInsert( PriorityQHeap *pq, PQkey keyNew )
 169 {
 170   long curr;
 171   PQhandle free_handle;
 172
 173   curr = ++ pq->size;
 174   if( (curr*2) > pq->max ) {
 175     PQnode *saveNodes= pq->nodes;
 176     PQhandleElem *saveHandles= pq->handles;
 177
 178     /* If the heap overflows, double its size. */
 179     pq->max <<= 1;
 180     pq->nodes = HeapReAlloc( GetProcessHeap(), 0, pq->nodes,
 181                                      (size_t)
 182                                      ((pq->max + 1) * sizeof( pq->nodes[0] )));
 183     if (pq->nodes == NULL) {
 184        pq->nodes = saveNodes;   /* restore ptr to free upon return */
 185        return LONG_MAX;
 186     }
 187     pq->handles = HeapReAlloc( GetProcessHeap(), 0, pq->handles,
 188                                              (size_t)
 189                                               ((pq->max + 1) *
 190                                                sizeof( pq->handles[0] )));
 191     if (pq->handles == NULL) {
 192        pq->handles = saveHandles; /* restore ptr to free upon return */
 193        return LONG_MAX;
 194     }
 195   }
 196
 197   if( pq->freeList == 0 ) {
 198     free_handle = curr;
 199   } else {
 200     free_handle = pq->freeList;
 201     pq->freeList = pq->handles[free_handle].node;
 202   }
 203
 204   pq->nodes[curr].handle = free_handle;
 205   pq->handles[free_handle].node = curr;
 206   pq->handles[free_handle].key = keyNew;
 207
 208   if( pq->initialized ) {
 209     FloatUp( pq, curr );
 210   }
 211   assert(free_handle != LONG_MAX);
 212   return free_handle;
 213 }
 214
 215 static PQkey __gl_pqHeapExtractMin( PriorityQHeap *pq )
 216 {
 217   PQnode *n = pq->nodes;
 218   PQhandleElem *h = pq->handles;
 219   PQhandle hMin = n[1].handle;
 220   PQkey min = h[hMin].key;
 221
 222   if( pq->size > 0 ) {
 223     n[1].handle = n[pq->size].handle;
 224     h[n[1].handle].node = 1;
 225
 226     h[hMin].key = NULL;
 227     h[hMin].node = pq->freeList;
 228     pq->freeList = hMin;
 229
 230     if( -- pq->size > 0 ) {
 231       FloatDown( pq, 1 );
 232     }
 233   }
 234   return min;
 235 }
 236
 237 static void __gl_pqHeapDelete( PriorityQHeap *pq, PQhandle hCurr )
 238 {
 239   PQnode *n = pq->nodes;
 240   PQhandleElem *h = pq->handles;
 241   long curr;
 242
 243   assert( hCurr >= 1 && hCurr <= pq->max && h[hCurr].key != NULL );
 244
 245   curr = h[hCurr].node;
 246   n[curr].handle = n[pq->size].handle;
 247   h[n[curr].handle].node = curr;
 248
 249   if( curr <= -- pq->size ) {
 250     if( curr <= 1 || LEQ( h[n[curr>>1].handle].key, h[n[curr].handle].key )) {
 251       FloatDown( pq, curr );
 252     } else {
 253       FloatUp( pq, curr );
 254     }
 255   }
 256   h[hCurr].key = NULL;
 257   h[hCurr].node = pq->freeList;
 258   pq->freeList = hCurr;
 259 }
 260
 261 /* Now redefine all the function names to map to their "Sort" versions. */
 262
 263 struct PriorityQSort {
 264   PriorityQHeap *heap;
 265   PQkey         *keys;
 266   PQkey         **order;
 267   PQhandle      size, max;
 268   int           initialized;
 269   int           (*leq)(PQkey key1, PQkey key2);
 270 };
 271
 272 PriorityQSort *__gl_pqSortNewPriorityQ( int (*leq)(PQkey key1, PQkey key2) )
 273 {
 274   PriorityQSort *pq = HeapAlloc( GetProcessHeap(), 0, sizeof( PriorityQSort ));
 275   if (pq == NULL) return NULL;
 276
 277   pq->heap = __gl_pqHeapNewPriorityQ( leq );
 278   if (pq->heap == NULL) {
 279      HeapFree( GetProcessHeap(), 0, pq );
 280      return NULL;
 281   }
 282
 283   pq->keys = HeapAlloc( GetProcessHeap(), 0, INIT_SIZE * sizeof(pq->keys[0]) );
 284   if (pq->keys == NULL) {
 285      __gl_pqHeapDeletePriorityQ(pq->heap);
 286      HeapFree( GetProcessHeap(), 0, pq );
 287      return NULL;
 288   }
 289
 290   pq->size = 0;
 291   pq->max = INIT_SIZE;
 292   pq->initialized = FALSE;
 293   pq->leq = leq;
 294   return pq;
 295 }
 296
 297 void __gl_pqSortDeletePriorityQ( PriorityQSort *pq )
 298 {
 299   assert(pq != NULL);
 300   if (pq->heap != NULL) __gl_pqHeapDeletePriorityQ( pq->heap );
 301   HeapFree( GetProcessHeap(), 0, pq->order );
 302   HeapFree( GetProcessHeap(), 0, pq->keys );
 303   HeapFree( GetProcessHeap(), 0, pq );
 304 }
 305
 306
 307 #define LT(x,y)         (! LEQ(y,x))
 308 #define GT(x,y)         (! LEQ(x,y))
 309 #define Swap(a,b)       do{PQkey *tmp = *a; *a = *b; *b = tmp;}while(0)
 310
 311 int __gl_pqSortInit( PriorityQSort *pq )
 312 {
 313   PQkey **p, **r, **i, **j, *piv;
 314   struct { PQkey **p, **r; } Stack[50], *top = Stack;
 315   unsigned long seed = 2016473283;
 316
 317   /* Create an array of indirect pointers to the keys, so that we
 318    * the handles we have returned are still valid.
 319    */
 320   pq->order = HeapAlloc( GetProcessHeap(), 0, (size_t)
 321                                   (pq->size * sizeof(pq->order[0])) );
 322   if (pq->order == NULL) return 0;
 323
 324   p = pq->order;
 325   r = p + pq->size - 1;
 326   for( piv = pq->keys, i = p; i <= r; ++piv, ++i ) {
 327     *i = piv;
 328   }
 329
 330   /* Sort the indirect pointers in descending order,
 331    * using randomized Quicksort
 332    */
 333   top->p = p; top->r = r; ++top;
 334   while( --top >= Stack ) {
 335     p = top->p;
 336     r = top->r;
 337     while( r > p + 10 ) {
 338       seed = seed * 1539415821 + 1;
 339       i = p + seed % (r - p + 1);
 340       piv = *i;
 341       *i = *p;
 342       *p = piv;
 343       i = p - 1;
 344       j = r + 1;
 345       do {
 346         do { ++i; } while( GT( **i, *piv ));
 347         do { --j; } while( LT( **j, *piv ));
 348         Swap( i, j );
 349       } while( i < j );
 350       Swap( i, j );     /* Undo last swap */
 351       if( i - p < r - j ) {
 352         top->p = j+1; top->r = r; ++top;
 353         r = i-1;
 354       } else {
 355         top->p = p; top->r = i-1; ++top;
 356         p = j+1;
 357       }
 358     }
 359     /* Insertion sort small lists */
 360     for( i = p+1; i <= r; ++i ) {
 361       piv = *i;
 362       for( j = i; j > p && LT( **(j-1), *piv ); --j ) {
 363         *j = *(j-1);
 364       }
 365       *j = piv;
 366     }
 367   }
 368   pq->max = pq->size;
 369   pq->initialized = TRUE;
 370   __gl_pqHeapInit( pq->heap );  /* always succeeds */
 371
 372 #ifndef NDEBUG
 373   p = pq->order;
 374   r = p + pq->size - 1;
 375   for( i = p; i < r; ++i ) {
 376     assert( LEQ( **(i+1), **i ));
 377   }
 378 #endif
 379
 380   return 1;
 381 }
 382
 383 /* returns LONG_MAX iff out of memory */
 384 PQhandle __gl_pqSortInsert( PriorityQSort *pq, PQkey keyNew )
 385 {
 386   long curr;
 387
 388   if( pq->initialized ) {
 389     return __gl_pqHeapInsert( pq->heap, keyNew );
 390   }
 391   curr = pq->size;
 392   if( ++ pq->size >= pq->max ) {
 393     PQkey *saveKey= pq->keys;
 394
 395     /* If the heap overflows, double its size. */
 396     pq->max <<= 1;
 397     pq->keys = HeapReAlloc( GetProcessHeap(), 0, pq->keys,
 398                                         (size_t)
 399                                          (pq->max * sizeof( pq->keys[0] )));
 400     if (pq->keys == NULL) {
 401        pq->keys = saveKey;      /* restore ptr to free upon return */
 402        return LONG_MAX;
 403     }
 404   }
 405   assert(curr != LONG_MAX);
 406   pq->keys[curr] = keyNew;
 407
 408   /* Negative handles index the sorted array. */
 409   return -(curr+1);
 410 }
 411
 412 PQkey __gl_pqSortExtractMin( PriorityQSort *pq )
 413 {
 414   PQkey sortMin, heapMin;
 415
 416   if( pq->size == 0 ) {
 417     return __gl_pqHeapExtractMin( pq->heap );
 418   }
 419   sortMin = *(pq->order[pq->size-1]);
 420   if( ! __gl_pqHeapIsEmpty( pq->heap )) {
 421     heapMin = __gl_pqHeapMinimum( pq->heap );
 422     if( LEQ( heapMin, sortMin )) {
 423       return __gl_pqHeapExtractMin( pq->heap );
 424     }
 425   }
 426   do {
 427     -- pq->size;
 428   } while( pq->size > 0 && *(pq->order[pq->size-1]) == NULL );
 429   return sortMin;
 430 }
 431
 432 PQkey __gl_pqSortMinimum( PriorityQSort *pq )
 433 {
 434   PQkey sortMin, heapMin;
 435
 436   if( pq->size == 0 ) {
 437     return __gl_pqHeapMinimum( pq->heap );
 438   }
 439   sortMin = *(pq->order[pq->size-1]);
 440   if( ! __gl_pqHeapIsEmpty( pq->heap )) {
 441     heapMin = __gl_pqHeapMinimum( pq->heap );
 442     if( LEQ( heapMin, sortMin )) {
 443       return heapMin;
 444     }
 445   }
 446   return sortMin;
 447 }
 448
 449 int __gl_pqSortIsEmpty( PriorityQSort *pq )
 450 {
 451   return (pq->size == 0) && __gl_pqHeapIsEmpty( pq->heap );
 452 }
 453
 454 void __gl_pqSortDelete( PriorityQSort *pq, PQhandle curr )
 455 {
 456   if( curr >= 0 ) {
 457     __gl_pqHeapDelete( pq->heap, curr );
 458     return;
 459   }
 460   curr = -(curr+1);
 461   assert( curr < pq->max && pq->keys[curr] != NULL );
 462
 463   pq->keys[curr] = NULL;
 464   while( pq->size > 0 && *(pq->order[pq->size-1]) == NULL ) {
 465     -- pq->size;
 466   }
 467 }