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