cogl/tesselator/priorityq-heap.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 <stddef.h>
  36 #include <assert.h>
  37 #include "priorityq-heap.h"
  38 #include "memalloc.h"
  39
  40 #define INIT_SIZE       32
  41
  42 #ifndef TRUE
  43 #define TRUE 1
  44 #endif
  45 #ifndef FALSE
  46 #define FALSE 0
  47 #endif
  48
  49 #ifdef FOR_TRITE_TEST_PROGRAM
  50 #define LEQ(x,y)        (*pq->leq)(x,y)
  51 #else
  52 /* Violates modularity, but a little faster */
  53 #include "geom.h"
  54 #define LEQ(x,y)        VertLeq((GLUvertex *)x, (GLUvertex *)y)
  55 #endif
  56
  57 /* really __gl_pqHeapNewPriorityQ */
  58 PriorityQ *pqNewPriorityQ( int (*leq)(PQkey key1, PQkey key2) )
  59 {
  60   PriorityQ *pq = (PriorityQ *)memAlloc( sizeof( PriorityQ ));
  61   if (pq == NULL) return NULL;
  62
  63   pq->size = 0;
  64   pq->max = INIT_SIZE;
  65   pq->nodes = (PQnode *)memAlloc( (INIT_SIZE + 1) * sizeof(pq->nodes[0]) );
  66   if (pq->nodes == NULL) {
  67      memFree(pq);
  68      return NULL;
  69   }
  70
  71   pq->handles = (PQhandleElem *)memAlloc( (INIT_SIZE + 1) * sizeof(pq->handles[0]) );
  72   if (pq->handles == NULL) {
  73      memFree(pq->nodes);
  74      memFree(pq);
  75      return NULL;
  76   }
  77
  78   pq->initialized = FALSE;
  79   pq->freeList = 0;
  80   pq->leq = leq;
  81
  82   pq->nodes[1].handle = 1;      /* so that Minimum() returns NULL */
  83   pq->handles[1].key = NULL;
  84   return pq;
  85 }
  86
  87 /* really __gl_pqHeapDeletePriorityQ */
  88 void pqDeletePriorityQ( PriorityQ *pq )
  89 {
  90   memFree( pq->handles );
  91   memFree( pq->nodes );
  92   memFree( pq );
  93 }
  94
  95
  96 static void FloatDown( PriorityQ *pq, long curr )
  97 {
  98   PQnode *n = pq->nodes;
  99   PQhandleElem *h = pq->handles;
 100   PQhandle hCurr, hChild;
 101   long child;
 102
 103   hCurr = n[curr].handle;
 104   for( ;; ) {
 105     child = curr << 1;
 106     if( child < pq->size && LEQ( h[n[child+1].handle].key,
 107                                  h[n[child].handle].key )) {
 108       ++child;
 109     }
 110
 111     assert(child <= pq->max);
 112
 113     hChild = n[child].handle;
 114     if( child > pq->size || LEQ( h[hCurr].key, h[hChild].key )) {
 115       n[curr].handle = hCurr;
 116       h[hCurr].node = curr;
 117       break;
 118     }
 119     n[curr].handle = hChild;
 120     h[hChild].node = curr;
 121     curr = child;
 122   }
 123 }
 124
 125
 126 static void FloatUp( PriorityQ *pq, long curr )
 127 {
 128   PQnode *n = pq->nodes;
 129   PQhandleElem *h = pq->handles;
 130   PQhandle hCurr, hParent;
 131   long parent;
 132
 133   hCurr = n[curr].handle;
 134   for( ;; ) {
 135     parent = curr >> 1;
 136     hParent = n[parent].handle;
 137     if( parent == 0 || LEQ( h[hParent].key, h[hCurr].key )) {
 138       n[curr].handle = hCurr;
 139       h[hCurr].node = curr;
 140       break;
 141     }
 142     n[curr].handle = hParent;
 143     h[hParent].node = curr;
 144     curr = parent;
 145   }
 146 }
 147
 148 /* really __gl_pqHeapInit */
 149 void pqInit( PriorityQ *pq )
 150 {
 151   long i;
 152
 153   /* This method of building a heap is O(n), rather than O(n lg n). */
 154
 155   for( i = pq->size; i >= 1; --i ) {
 156     FloatDown( pq, i );
 157   }
 158   pq->initialized = TRUE;
 159 }
 160
 161 /* really __gl_pqHeapInsert */
 162 /* returns LONG_MAX iff out of memory */
 163 PQhandle pqInsert( PriorityQ *pq, PQkey keyNew )
 164 {
 165   long curr;
 166   PQhandle free_handle;
 167
 168   curr = ++ pq->size;
 169   if( (curr*2) > pq->max ) {
 170     PQnode *saveNodes= pq->nodes;
 171     PQhandleElem *saveHandles= pq->handles;
 172
 173     /* If the heap overflows, double its size. */
 174     pq->max <<= 1;
 175     pq->nodes = (PQnode *)memRealloc( pq->nodes,
 176                                      (size_t)
 177                                      ((pq->max + 1) * sizeof( pq->nodes[0] )));
 178     if (pq->nodes == NULL) {
 179        pq->nodes = saveNodes;   /* restore ptr to free upon return */
 180        return LONG_MAX;
 181     }
 182     pq->handles = (PQhandleElem *)memRealloc( pq->handles,
 183                                              (size_t)
 184                                               ((pq->max + 1) *
 185                                                sizeof( pq->handles[0] )));
 186     if (pq->handles == NULL) {
 187        pq->handles = saveHandles; /* restore ptr to free upon return */
 188        return LONG_MAX;
 189     }
 190   }
 191
 192   if( pq->freeList == 0 ) {
 193     free_handle = curr;
 194   } else {
 195     free_handle = pq->freeList;
 196     pq->freeList = pq->handles[free_handle].node;
 197   }
 198
 199   pq->nodes[curr].handle = free_handle;
 200   pq->handles[free_handle].node = curr;
 201   pq->handles[free_handle].key = keyNew;
 202
 203   if( pq->initialized ) {
 204     FloatUp( pq, curr );
 205   }
 206   assert(free_handle != LONG_MAX);
 207   return free_handle;
 208 }
 209
 210 /* really __gl_pqHeapExtractMin */
 211 PQkey pqExtractMin( PriorityQ *pq )
 212 {
 213   PQnode *n = pq->nodes;
 214   PQhandleElem *h = pq->handles;
 215   PQhandle hMin = n[1].handle;
 216   PQkey min = h[hMin].key;
 217
 218   if( pq->size > 0 ) {
 219     n[1].handle = n[pq->size].handle;
 220     h[n[1].handle].node = 1;
 221
 222     h[hMin].key = NULL;
 223     h[hMin].node = pq->freeList;
 224     pq->freeList = hMin;
 225
 226     if( -- pq->size > 0 ) {
 227       FloatDown( pq, 1 );
 228     }
 229   }
 230   return min;
 231 }
 232
 233 /* really __gl_pqHeapDelete */
 234 void pqDelete( PriorityQ *pq, PQhandle hCurr )
 235 {
 236   PQnode *n = pq->nodes;
 237   PQhandleElem *h = pq->handles;
 238   long curr;
 239
 240   assert( hCurr >= 1 && hCurr <= pq->max && h[hCurr].key != NULL );
 241
 242   curr = h[hCurr].node;
 243   n[curr].handle = n[pq->size].handle;
 244   h[n[curr].handle].node = curr;
 245
 246   if( curr <= -- pq->size ) {
 247     if( curr <= 1 || LEQ( h[n[curr>>1].handle].key, h[n[curr].handle].key )) {
 248       FloatDown( pq, curr );
 249     } else {
 250       FloatUp( pq, curr );
 251     }
 252   }
 253   h[hCurr].key = NULL;
 254   h[hCurr].node = pq->freeList;
 255   pq->freeList = hCurr;
 256 }