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