text: /*
  ** License Applicability. Except to the extent portions of this file are
  ** made subject to an alternative license as permitted in the SGI Free
  ** Software License B, Version 1.1 (the "License"), the contents of this
  ** file are subject only to the provisions of the License. You may not use
  ** this file except in compliance with the License. You may obtain a copy
  ** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
  ** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
  ** 
  ** http://oss.sgi.com/projects/FreeB
  ** 
  ** Note that, as provided in the License, the Software is distributed on an
  ** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
  ** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
  ** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
  ** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
  ** 
  ** Original Code. The Original Code is: OpenGL Sample Implementation,
  ** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
  ** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
  ** Copyright in any portions created by third parties is as indicated
  ** elsewhere herein. All Rights Reserved.
  ** 
  ** Additional Notice Provisions: The application programming interfaces
  ** established by SGI in conjunction with the Original Code are The
  ** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
  ** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
  ** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
  ** Window System(R) (Version 1.3), released October 19, 1998. This software
  ** was created using the OpenGL(R) version 1.2.1 Sample Implementation
  ** published by SGI, but has not been independently verified as being
  ** compliant with the OpenGL(R) version 1.2.1 Specification.
  **
  */
  /*
  ** Author: Eric Veach, July 1994.
  **
  ** $Date: 2004/03/14 08:29:11 $ $Revision: 1.1.1.4 $
  ** $Header: /cvs/xorg/xc/extras/ogl-sample/main/gfx/lib/glu/libtess/priorityq.c,v 1.1.1.4 2004/03/14 08:29:11 eich Exp $
  */
  
  #include "gluos.h"
  #include <stddef.h>
  #include <assert.h>
  #include <limits.h>		/* LONG_MAX */
  #include "memalloc.h"
  
  /* Include all the code for the regular heap-based queue here. */
  
  #include "priorityq-heap.c"
  
  /* Now redefine all the function names to map to their "Sort" versions. */
  
  #include "priorityq-sort.h"
  
  /* really __gl_pqSortNewPriorityQ */
  PriorityQ *pqNewPriorityQ( int (*leq)(PQkey key1, PQkey key2) )
  {
    PriorityQ *pq = (PriorityQ *)memAlloc( sizeof( PriorityQ ));
    if (pq == NULL) return NULL;
  
    pq->heap = __gl_pqHeapNewPriorityQ( leq );
    if (pq->heap == NULL) {
       memFree(pq);
       return NULL;
    }
  
    pq->keys = (PQHeapKey *)memAlloc( INIT_SIZE * sizeof(pq->keys[0]) );
    if (pq->keys == NULL) {
       __gl_pqHeapDeletePriorityQ(pq->heap);
       memFree(pq);
       return NULL;
    }
  
    pq->size = 0;
    pq->max = INIT_SIZE;
    pq->initialized = FALSE;
    pq->leq = leq;
    return pq;
  }
  
  /* really __gl_pqSortDeletePriorityQ */
  void pqDeletePriorityQ( PriorityQ *pq )
  {
    assert(pq != NULL); 
    if (pq->heap != NULL) __gl_pqHeapDeletePriorityQ( pq->heap );
    if (pq->order != NULL) memFree( pq->order );
    if (pq->keys != NULL) memFree( pq->keys );
    memFree( pq );
  }
  
  
  #define LT(x,y)		(! LEQ(y,x))
  #define GT(x,y)		(! LEQ(x,y))
  #define Swap(a,b)	if(1){PQkey *tmp = *a; *a = *b; *b = tmp;}else
  
  /* really __gl_pqSortInit */
  int pqInit( PriorityQ *pq )
  {
    PQkey **p, **r, **i, **j, *piv;
    struct { PQkey **p, **r; } Stack[50], *top = Stack;
    unsigned long seed = 2016473283;
  
    /* Create an array of indirect pointers to the keys, so that we
     * the handles we have returned are still valid.
     */
  /*
    pq->order = (PQHeapKey **)memAlloc( (size_t)
                                    (pq->size * sizeof(pq->order[0])) );
  */
    pq->order = (PQHeapKey **)memAlloc( (size_t)
                                    ((pq->size+1) * sizeof(pq->order[0])) );
  /* the previous line is a patch to compensate for the fact that IBM */
  /* machines return a null on a malloc of zero bytes (unlike SGI),   */
  /* so we have to put in this defense to guard against a memory      */
  /* fault four lines down. from fossum@austin.ibm.com.               */
    if (pq->order == NULL) return 0;
  
    p = pq->order;
    r = p + pq->size - 1;
    for( piv = pq->keys, i = p; i <= r; ++piv, ++i ) {
      *i = piv;
    }
  
    /* Sort the indirect pointers in descending order,
     * using randomized Quicksort
     */
    top->p = p; top->r = r; ++top;
    while( --top >= Stack ) {
      p = top->p;
      r = top->r;
      while( r > p + 10 ) {
        seed = seed * 1539415821 + 1;
        i = p + seed % (r - p + 1);
        piv = *i;
        *i = *p;
        *p = piv;
        i = p - 1;
        j = r + 1;
        do {
  	do { ++i; } while( GT( **i, *piv ));
  	do { --j; } while( LT( **j, *piv ));
  	Swap( i, j );
        } while( i < j );
        Swap( i, j );	/* Undo last swap */
        if( i - p < r - j ) {
  	top->p = j+1; top->r = r; ++top;
  	r = i-1;
        } else {
  	top->p = p; top->r = i-1; ++top;
  	p = j+1;
        }
      }
      /* Insertion sort small lists */
      for( i = p+1; i <= r; ++i ) {
        piv = *i;
        for( j = i; j > p && LT( **(j-1), *piv ); --j ) {
  	*j = *(j-1);
        }
        *j = piv;
      }
    }
    pq->max = pq->size;
    pq->initialized = TRUE;
    __gl_pqHeapInit( pq->heap );	/* always succeeds */
  
  #ifndef NDEBUG
    p = pq->order;
    r = p + pq->size - 1;
    for( i = p; i < r; ++i ) {
      assert( LEQ( **(i+1), **i ));
    }
  #endif
  
    return 1;
  }
  
  /* really __gl_pqSortInsert */
  /* returns LONG_MAX iff out of memory */ 
  PQhandle pqInsert( PriorityQ *pq, PQkey keyNew )
  {
    long curr;
  
    if( pq->initialized ) {
      return __gl_pqHeapInsert( pq->heap, keyNew );
    }
    curr = pq->size;
    if( ++ pq->size >= pq->max ) {
      PQkey *saveKey= pq->keys;
  
      /* If the heap overflows, double its size. */
      pq->max <<= 1;
      pq->keys = (PQHeapKey *)memRealloc( pq->keys, 
  	 	                        (size_t)
  	                                 (pq->max * sizeof( pq->keys[0] )));
      if (pq->keys == NULL) {	
         pq->keys = saveKey;	/* restore ptr to free upon return */
         return LONG_MAX;
      }
    }
    assert(curr != LONG_MAX);	
    pq->keys[curr] = keyNew;
  
    /* Negative handles index the sorted array. */
    return -(curr+1);
  }
  
  /* really __gl_pqSortExtractMin */
  PQkey pqExtractMin( PriorityQ *pq )
  {
    PQkey sortMin, heapMin;
  
    if( pq->size == 0 ) {
      return __gl_pqHeapExtractMin( pq->heap );
    }
    sortMin = *(pq->order[pq->size-1]);
    if( ! __gl_pqHeapIsEmpty( pq->heap )) {
      heapMin = __gl_pqHeapMinimum( pq->heap );
      if( LEQ( heapMin, sortMin )) {
        return __gl_pqHeapExtractMin( pq->heap );
      }
    }
    do {
      -- pq->size;
    } while( pq->size > 0 && *(pq->order[pq->size-1]) == NULL );
    return sortMin;
  }
  
  /* really __gl_pqSortMinimum */
  PQkey pqMinimum( PriorityQ *pq )
  {
    PQkey sortMin, heapMin;
  
    if( pq->size == 0 ) {
      return __gl_pqHeapMinimum( pq->heap );
    }
    sortMin = *(pq->order[pq->size-1]);
    if( ! __gl_pqHeapIsEmpty( pq->heap )) {
      heapMin = __gl_pqHeapMinimum( pq->heap );
      if( LEQ( heapMin, sortMin )) {
        return heapMin;
      }
    }
    return sortMin;
  }
  
  /* really __gl_pqSortIsEmpty */
  int pqIsEmpty( PriorityQ *pq )
  {
    return (pq->size == 0) && __gl_pqHeapIsEmpty( pq->heap );
  }
  
  /* really __gl_pqSortDelete */
  void pqDelete( PriorityQ *pq, PQhandle curr )
  {
    if( curr >= 0 ) {
      __gl_pqHeapDelete( pq->heap, curr );
      return;
    }
    curr = -(curr+1);
    assert( curr < pq->max && pq->keys[curr] != NULL );
  
    pq->keys[curr] = NULL;
    while( pq->size > 0 && *(pq->order[pq->size-1]) == NULL ) {
      -- pq->size;
    }
  }
  