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$ $Revision$
39** $Header: //depot/main/gfx/lib/glu/libtess/priorityq.c#5 $
40*/
41
42#include "gluos.h"
43#include <stddef.h>
44#include <assert.h>
45#include <limits.h>		/* LONG_MAX */
46#include "memalloc.h"
47
48/* Include all the code for the regular heap-based queue here. */
49
50#include "priorityq-heap.c"
51
52/* Now redefine all the function names to map to their "Sort" versions. */
53
54#include "priorityq-sort.h"
55
56/* really __gl_pqSortNewPriorityQ */
57PriorityQ *pqNewPriorityQ( int (*leq)(PQkey key1, PQkey key2) )
58{
59  PriorityQ *pq = (PriorityQ *)memAlloc( sizeof( PriorityQ ));
60  if (pq == NULL) return NULL;
61
62  pq->heap = __gl_pqHeapNewPriorityQ( leq );
63  if (pq->heap == NULL) {
64     memFree(pq);
65     return NULL;
66  }
67
68  pq->keys = (PQHeapKey *)memAlloc( INIT_SIZE * sizeof(pq->keys[0]) );
69  if (pq->keys == NULL) {
70     __gl_pqHeapDeletePriorityQ(pq->heap);
71     memFree(pq);
72     return NULL;
73  }
74
75  pq->size = 0;
76  pq->max = INIT_SIZE;
77  pq->initialized = FALSE;
78  pq->leq = leq;
79  return pq;
80}
81
82/* really __gl_pqSortDeletePriorityQ */
83void pqDeletePriorityQ( PriorityQ *pq )
84{
85  assert(pq != NULL);
86  if (pq->heap != NULL) __gl_pqHeapDeletePriorityQ( pq->heap );
87  if (pq->order != NULL) memFree( pq->order );
88  if (pq->keys != NULL) memFree( pq->keys );
89  memFree( pq );
90}
91
92
93#define LT(x,y)		(! LEQ(y,x))
94#define GT(x,y)		(! LEQ(x,y))
95#define Swap(a,b)	do{PQkey *tmp = *a; *a = *b; *b = tmp;}while(0)
96
97/* really __gl_pqSortInit */
98int pqInit( PriorityQ *pq )
99{
100  PQkey **p, **r, **i, **j, *piv;
101  struct { PQkey **p, **r; } Stack[50], *top = Stack;
102  unsigned long seed = 2016473283;
103
104  /* Create an array of indirect pointers to the keys, so that we
105   * the handles we have returned are still valid.
106   */
107/*
108  pq->order = (PQHeapKey **)memAlloc( (size_t)
109                                  (pq->size * sizeof(pq->order[0])) );
110*/
111  pq->order = (PQHeapKey **)memAlloc( (size_t)
112                                  ((pq->size+1) * sizeof(pq->order[0])) );
113/* the previous line is a patch to compensate for the fact that IBM */
114/* machines return a null on a malloc of zero bytes (unlike SGI),   */
115/* so we have to put in this defense to guard against a memory      */
116/* fault four lines down. from fossum@austin.ibm.com.               */
117  if (pq->order == NULL) return 0;
118
119  p = pq->order;
120  r = p + pq->size - 1;
121  for( piv = pq->keys, i = p; i <= r; ++piv, ++i ) {
122    *i = piv;
123  }
124
125  /* Sort the indirect pointers in descending order,
126   * using randomized Quicksort
127   */
128  top->p = p; top->r = r; ++top;
129  while( --top >= Stack ) {
130    p = top->p;
131    r = top->r;
132    while( r > p + 10 ) {
133      seed = seed * 1539415821 + 1;
134      i = p + seed % (r - p + 1);
135      piv = *i;
136      *i = *p;
137      *p = piv;
138      i = p - 1;
139      j = r + 1;
140      do {
141	do { ++i; } while( GT( **i, *piv ));
142	do { --j; } while( LT( **j, *piv ));
143	Swap( i, j );
144      } while( i < j );
145      Swap( i, j );	/* Undo last swap */
146      if( i - p < r - j ) {
147	top->p = j+1; top->r = r; ++top;
148	r = i-1;
149      } else {
150	top->p = p; top->r = i-1; ++top;
151	p = j+1;
152      }
153    }
154    /* Insertion sort small lists */
155    for( i = p+1; i <= r; ++i ) {
156      piv = *i;
157      for( j = i; j > p && LT( **(j-1), *piv ); --j ) {
158	*j = *(j-1);
159      }
160      *j = piv;
161    }
162  }
163  pq->max = pq->size;
164  pq->initialized = TRUE;
165  __gl_pqHeapInit( pq->heap );	/* always succeeds */
166
167#ifndef NDEBUG
168  p = pq->order;
169  r = p + pq->size - 1;
170  for( i = p; i < r; ++i ) {
171    assert( LEQ( **(i+1), **i ));
172  }
173#endif
174
175  return 1;
176}
177
178/* really __gl_pqSortInsert */
179/* returns LONG_MAX iff out of memory */
180PQhandle pqInsert( PriorityQ *pq, PQkey keyNew )
181{
182  long curr;
183
184  if( pq->initialized ) {
185    return __gl_pqHeapInsert( pq->heap, keyNew );
186  }
187  curr = pq->size;
188  if( ++ pq->size >= pq->max ) {
189    PQkey *saveKey= pq->keys;
190
191    /* If the heap overflows, double its size. */
192    pq->max <<= 1;
193    pq->keys = (PQHeapKey *)memRealloc( pq->keys,
194	 	                        (size_t)
195	                                 (pq->max * sizeof( pq->keys[0] )));
196    if (pq->keys == NULL) {
197       pq->keys = saveKey;	/* restore ptr to free upon return */
198       return LONG_MAX;
199    }
200  }
201  assert(curr != LONG_MAX);
202  pq->keys[curr] = keyNew;
203
204  /* Negative handles index the sorted array. */
205  return -(curr+1);
206}
207
208/* really __gl_pqSortExtractMin */
209PQkey pqExtractMin( PriorityQ *pq )
210{
211  PQkey sortMin, heapMin;
212
213  if( pq->size == 0 ) {
214    return __gl_pqHeapExtractMin( pq->heap );
215  }
216  sortMin = *(pq->order[pq->size-1]);
217  if( ! __gl_pqHeapIsEmpty( pq->heap )) {
218    heapMin = __gl_pqHeapMinimum( pq->heap );
219    if( LEQ( heapMin, sortMin )) {
220      return __gl_pqHeapExtractMin( pq->heap );
221    }
222  }
223  do {
224    -- pq->size;
225  } while( pq->size > 0 && *(pq->order[pq->size-1]) == NULL );
226  return sortMin;
227}
228
229/* really __gl_pqSortMinimum */
230PQkey pqMinimum( PriorityQ *pq )
231{
232  PQkey sortMin, heapMin;
233
234  if( pq->size == 0 ) {
235    return __gl_pqHeapMinimum( pq->heap );
236  }
237  sortMin = *(pq->order[pq->size-1]);
238  if( ! __gl_pqHeapIsEmpty( pq->heap )) {
239    heapMin = __gl_pqHeapMinimum( pq->heap );
240    if( LEQ( heapMin, sortMin )) {
241      return heapMin;
242    }
243  }
244  return sortMin;
245}
246
247/* really __gl_pqSortIsEmpty */
248int pqIsEmpty( PriorityQ *pq )
249{
250  return (pq->size == 0) && __gl_pqHeapIsEmpty( pq->heap );
251}
252
253/* really __gl_pqSortDelete */
254void pqDelete( PriorityQ *pq, PQhandle curr )
255{
256  if( curr >= 0 ) {
257    __gl_pqHeapDelete( pq->heap, curr );
258    return;
259  }
260  curr = -(curr+1);
261  assert( curr < pq->max && pq->keys[curr] != NULL );
262
263  pq->keys[curr] = NULL;
264  while( pq->size > 0 && *(pq->order[pq->size-1]) == NULL ) {
265    -- pq->size;
266  }
267}
268