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