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