reactos/dll/win32/glu32/libtess/priorityq.c

   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: 1.1 $
  39 ** $Header: /cygdrive/c/RCVS/CVS/ReactOS/reactos/lib/glu32/libtess/priorityq.c,v 1.1 2004/02/02 16:39:15 navaraf Exp $
  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)       if(1){PQkey *tmp = *a; *a = *b; *b = tmp;}else
  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@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 }