| /* |
| * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) |
| * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. |
| * |
| * Permission is hereby granted, free of charge, to any person obtaining a |
| * copy of this software and associated documentation files (the "Software"), |
| * to deal in the Software without restriction, including without limitation |
| * the rights to use, copy, modify, merge, publish, distribute, sublicense, |
| * and/or sell copies of the Software, and to permit persons to whom the |
| * Software is furnished to do so, subject to the following conditions: |
| * |
| * The above copyright notice including the dates of first publication and |
| * either this permission notice or a reference to |
| * http://oss.sgi.com/projects/FreeB/ |
| * shall be included in all copies or substantial portions of the Software. |
| * |
| * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS |
| * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
| * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, |
| * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF |
| * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE |
| * SOFTWARE. |
| * |
| * Except as contained in this notice, the name of Silicon Graphics, Inc. |
| * shall not be used in advertising or otherwise to promote the sale, use or |
| * other dealings in this Software without prior written authorization from |
| * Silicon Graphics, Inc. |
| */ |
| /* |
| ** Author: Eric Veach, July 1994. |
| ** |
| */ |
| |
| #include <stdarg.h> |
| #include <assert.h> |
| #include <limits.h> /* LONG_MAX */ |
| |
| #include "windef.h" |
| #include "winbase.h" |
| #include "tess.h" |
| |
| /* Include all the code for the regular heap-based queue here. */ |
| |
| typedef struct PriorityQHeap PriorityQHeap; |
| typedef struct { PQhandle handle; } PQnode; |
| typedef struct { PQkey key; PQhandle node; } PQhandleElem; |
| |
| struct PriorityQHeap { |
| PQnode *nodes; |
| PQhandleElem *handles; |
| long size, max; |
| PQhandle freeList; |
| int initialized; |
| int (*leq)(PQkey key1, PQkey key2); |
| }; |
| |
| #define __gl_pqHeapMinimum(pq) ((pq)->handles[(pq)->nodes[1].handle].key) |
| #define __gl_pqHeapIsEmpty(pq) ((pq)->size == 0) |
| |
| #define INIT_SIZE 32 |
| |
| /* Violates modularity, but a little faster */ |
| #define LEQ(x,y) VertLeq((GLUvertex *)x, (GLUvertex *)y) |
| |
| static PriorityQHeap *__gl_pqHeapNewPriorityQ( int (*leq)(PQkey key1, PQkey key2) ) |
| { |
| PriorityQHeap *pq = HeapAlloc( GetProcessHeap(), 0, sizeof( PriorityQHeap )); |
| if (pq == NULL) return NULL; |
| |
| pq->size = 0; |
| pq->max = INIT_SIZE; |
| pq->nodes = HeapAlloc( GetProcessHeap(), 0, (INIT_SIZE + 1) * sizeof(pq->nodes[0]) ); |
| if (pq->nodes == NULL) { |
| HeapFree( GetProcessHeap(), 0, pq ); |
| return NULL; |
| } |
| |
| pq->handles = HeapAlloc( GetProcessHeap(), 0, (INIT_SIZE + 1) * sizeof(pq->handles[0]) ); |
| if (pq->handles == NULL) { |
| HeapFree( GetProcessHeap(), 0, pq->nodes ); |
| HeapFree( GetProcessHeap(), 0, pq ); |
| return NULL; |
| } |
| |
| pq->initialized = FALSE; |
| pq->freeList = 0; |
| pq->leq = leq; |
| |
| pq->nodes[1].handle = 1; /* so that Minimum() returns NULL */ |
| pq->handles[1].key = NULL; |
| return pq; |
| } |
| |
| static void __gl_pqHeapDeletePriorityQ( PriorityQHeap *pq ) |
| { |
| HeapFree( GetProcessHeap(), 0, pq->handles ); |
| HeapFree( GetProcessHeap(), 0, pq->nodes ); |
| HeapFree( GetProcessHeap(), 0, pq ); |
| } |
| |
| |
| static void FloatDown( PriorityQHeap *pq, long curr ) |
| { |
| PQnode *n = pq->nodes; |
| PQhandleElem *h = pq->handles; |
| PQhandle hCurr, hChild; |
| long child; |
| |
| hCurr = n[curr].handle; |
| for( ;; ) { |
| child = curr << 1; |
| if( child < pq->size && LEQ( h[n[child+1].handle].key, |
| h[n[child].handle].key )) { |
| ++child; |
| } |
| |
| assert(child <= pq->max); |
| |
| hChild = n[child].handle; |
| if( child > pq->size || LEQ( h[hCurr].key, h[hChild].key )) { |
| n[curr].handle = hCurr; |
| h[hCurr].node = curr; |
| break; |
| } |
| n[curr].handle = hChild; |
| h[hChild].node = curr; |
| curr = child; |
| } |
| } |
| |
| |
| static void FloatUp( PriorityQHeap *pq, long curr ) |
| { |
| PQnode *n = pq->nodes; |
| PQhandleElem *h = pq->handles; |
| PQhandle hCurr, hParent; |
| long parent; |
| |
| hCurr = n[curr].handle; |
| for( ;; ) { |
| parent = curr >> 1; |
| hParent = n[parent].handle; |
| if( parent == 0 || LEQ( h[hParent].key, h[hCurr].key )) { |
| n[curr].handle = hCurr; |
| h[hCurr].node = curr; |
| break; |
| } |
| n[curr].handle = hParent; |
| h[hParent].node = curr; |
| curr = parent; |
| } |
| } |
| |
| static void __gl_pqHeapInit( PriorityQHeap *pq ) |
| { |
| long i; |
| |
| /* This method of building a heap is O(n), rather than O(n lg n). */ |
| |
| for( i = pq->size; i >= 1; --i ) { |
| FloatDown( pq, i ); |
| } |
| pq->initialized = TRUE; |
| } |
| |
| /* returns LONG_MAX iff out of memory */ |
| static PQhandle __gl_pqHeapInsert( PriorityQHeap *pq, PQkey keyNew ) |
| { |
| long curr; |
| PQhandle free_handle; |
| |
| curr = ++ pq->size; |
| if( (curr*2) > pq->max ) { |
| PQnode *saveNodes= pq->nodes; |
| PQhandleElem *saveHandles= pq->handles; |
| |
| /* If the heap overflows, double its size. */ |
| pq->max <<= 1; |
| pq->nodes = HeapReAlloc( GetProcessHeap(), 0, pq->nodes, |
| (size_t) |
| ((pq->max + 1) * sizeof( pq->nodes[0] ))); |
| if (pq->nodes == NULL) { |
| pq->nodes = saveNodes; /* restore ptr to free upon return */ |
| return LONG_MAX; |
| } |
| pq->handles = HeapReAlloc( GetProcessHeap(), 0, pq->handles, |
| (size_t) |
| ((pq->max + 1) * |
| sizeof( pq->handles[0] ))); |
| if (pq->handles == NULL) { |
| pq->handles = saveHandles; /* restore ptr to free upon return */ |
| return LONG_MAX; |
| } |
| } |
| |
| if( pq->freeList == 0 ) { |
| free_handle = curr; |
| } else { |
| free_handle = pq->freeList; |
| pq->freeList = pq->handles[free_handle].node; |
| } |
| |
| pq->nodes[curr].handle = free_handle; |
| pq->handles[free_handle].node = curr; |
| pq->handles[free_handle].key = keyNew; |
| |
| if( pq->initialized ) { |
| FloatUp( pq, curr ); |
| } |
| assert(free_handle != LONG_MAX); |
| return free_handle; |
| } |
| |
| static PQkey __gl_pqHeapExtractMin( PriorityQHeap *pq ) |
| { |
| PQnode *n = pq->nodes; |
| PQhandleElem *h = pq->handles; |
| PQhandle hMin = n[1].handle; |
| PQkey min = h[hMin].key; |
| |
| if( pq->size > 0 ) { |
| n[1].handle = n[pq->size].handle; |
| h[n[1].handle].node = 1; |
| |
| h[hMin].key = NULL; |
| h[hMin].node = pq->freeList; |
| pq->freeList = hMin; |
| |
| if( -- pq->size > 0 ) { |
| FloatDown( pq, 1 ); |
| } |
| } |
| return min; |
| } |
| |
| static void __gl_pqHeapDelete( PriorityQHeap *pq, PQhandle hCurr ) |
| { |
| PQnode *n = pq->nodes; |
| PQhandleElem *h = pq->handles; |
| long curr; |
| |
| assert( hCurr >= 1 && hCurr <= pq->max && h[hCurr].key != NULL ); |
| |
| curr = h[hCurr].node; |
| n[curr].handle = n[pq->size].handle; |
| h[n[curr].handle].node = curr; |
| |
| if( curr <= -- pq->size ) { |
| if( curr <= 1 || LEQ( h[n[curr>>1].handle].key, h[n[curr].handle].key )) { |
| FloatDown( pq, curr ); |
| } else { |
| FloatUp( pq, curr ); |
| } |
| } |
| h[hCurr].key = NULL; |
| h[hCurr].node = pq->freeList; |
| pq->freeList = hCurr; |
| } |
| |
| /* Now redefine all the function names to map to their "Sort" versions. */ |
| |
| struct PriorityQSort { |
| PriorityQHeap *heap; |
| PQkey *keys; |
| PQkey **order; |
| PQhandle size, max; |
| int initialized; |
| int (*leq)(PQkey key1, PQkey key2); |
| }; |
| |
| PriorityQSort *__gl_pqSortNewPriorityQ( int (*leq)(PQkey key1, PQkey key2) ) |
| { |
| PriorityQSort *pq = HeapAlloc( GetProcessHeap(), 0, sizeof( PriorityQSort )); |
| if (pq == NULL) return NULL; |
| |
| pq->heap = __gl_pqHeapNewPriorityQ( leq ); |
| if (pq->heap == NULL) { |
| HeapFree( GetProcessHeap(), 0, pq ); |
| return NULL; |
| } |
| |
| pq->keys = HeapAlloc( GetProcessHeap(), 0, INIT_SIZE * sizeof(pq->keys[0]) ); |
| if (pq->keys == NULL) { |
| __gl_pqHeapDeletePriorityQ(pq->heap); |
| HeapFree( GetProcessHeap(), 0, pq ); |
| return NULL; |
| } |
| |
| pq->size = 0; |
| pq->max = INIT_SIZE; |
| pq->initialized = FALSE; |
| pq->leq = leq; |
| return pq; |
| } |
| |
| void __gl_pqSortDeletePriorityQ( PriorityQSort *pq ) |
| { |
| assert(pq != NULL); |
| if (pq->heap != NULL) __gl_pqHeapDeletePriorityQ( pq->heap ); |
| HeapFree( GetProcessHeap(), 0, pq->order ); |
| HeapFree( GetProcessHeap(), 0, pq->keys ); |
| HeapFree( GetProcessHeap(), 0, pq ); |
| } |
| |
| |
| #define LT(x,y) (! LEQ(y,x)) |
| #define GT(x,y) (! LEQ(x,y)) |
| #define Swap(a,b) do{PQkey *tmp = *a; *a = *b; *b = tmp;}while(0) |
| |
| int __gl_pqSortInit( PriorityQSort *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 = HeapAlloc( GetProcessHeap(), 0, (size_t) |
| (pq->size * sizeof(pq->order[0])) ); |
| 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; |
| } |
| |
| /* returns LONG_MAX iff out of memory */ |
| PQhandle __gl_pqSortInsert( PriorityQSort *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 = HeapReAlloc( GetProcessHeap(), 0, 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); |
| } |
| |
| PQkey __gl_pqSortExtractMin( PriorityQSort *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; |
| } |
| |
| PQkey __gl_pqSortMinimum( PriorityQSort *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; |
| } |
| |
| int __gl_pqSortIsEmpty( PriorityQSort *pq ) |
| { |
| return (pq->size == 0) && __gl_pqHeapIsEmpty( pq->heap ); |
| } |
| |
| void __gl_pqSortDelete( PriorityQSort *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; |
| } |
| } |