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