← Back to branch summary

~ubuntu-branches/ubuntu/precise/stellarium/precise

« back to all changes in this revision

Viewing changes to src/external/glues_stel/source/libtess/priorityq.c

  • Committer: Bazaar Package Importer
  • Author(s): Scott Howard
  • Date: 2010-02-15 20:48:39 UTC
  • mfrom: (1.1.9 upstream)
  • Revision ID: james.westby@ubuntu.com-20100215204839-u3qgbv60rho997yk
Tags: 0.10.3-0ubuntu1
https://launchpad.net/bugs/480553
* New upstream release.
  - fixes intel rendering bug (LP: #480553)

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/external/glues_stel/source/libtess/priorityq.c
 
1
/*
 
2
 * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
 
3
 * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved.
 
4
 *
 
5
 * Permission is hereby granted, free of charge, to any person obtaining a
 
6
 * copy of this software and associated documentation files (the "Software"),
 
7
 * to deal in the Software without restriction, including without limitation
 
8
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 
9
 * and/or sell copies of the Software, and to permit persons to whom the
 
10
 * Software is furnished to do so, subject to the following conditions:
 
11
 *
 
12
 * The above copyright notice including the dates of first publication and
 
13
 * either this permission notice or a reference to
 
14
 * http://oss.sgi.com/projects/FreeB/
 
15
 * shall be included in all copies or substantial portions of the Software.
 
16
 *
 
17
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 
18
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 
19
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 
20
 * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 
21
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
 
22
 * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 
23
 * SOFTWARE.
 
24
 *
 
25
 * Except as contained in this notice, the name of Silicon Graphics, Inc.
 
26
 * shall not be used in advertising or otherwise to promote the sale, use or
 
27
 * other dealings in this Software without prior written authorization from
 
28
 * Silicon Graphics, Inc.
 
29
 */
 
30
/*
 
31
** Author: Eric Veach, July 1994.
 
32
**
 
33
*/
 
34
 
 
35
#include <stddef.h>
 
36
#include <assert.h>
 
37
#include <limits.h>     /* LONG_MAX */
 
38
#include "memalloc.h"
 
39
 
 
40
/* Include all the code for the regular heap-based queue here. */
 
41
 
 
42
#include "priorityq-heap.i"
 
43
 
 
44
/* Now redefine all the function names to map to their "Sort" versions. */
 
45
 
 
46
#include "priorityq-sort.h"
 
47
 
 
48
/* really __gl_pqSortNewPriorityQ */
 
49
PriorityQ* pqNewPriorityQ(int (*leq)(PQkey key1, PQkey key2))
 
50
{
 
51
   PriorityQ* pq=(PriorityQ*)memAlloc(sizeof(PriorityQ));
 
52
   if (pq==NULL)
 
53
   {
 
54
          return NULL;
 
55
   }
 
56
 
 
57
   pq->heap=__gl_pqHeapNewPriorityQ(leq);
 
58
   if (pq->heap==NULL)
 
59
   {
 
60
          memFree(pq);
 
61
          return NULL;
 
62
   }
 
63
 
 
64
   pq->keys=(PQHeapKey*)memAlloc(INIT_SIZE*sizeof(pq->keys[0]));
 
65
   if (pq->keys==NULL)
 
66
   {
 
67
          __gl_pqHeapDeletePriorityQ(pq->heap);
 
68
          memFree(pq);
 
69
          return NULL;
 
70
   }
 
71
 
 
72
   pq->size=0;
 
73
   pq->max=INIT_SIZE;
 
74
   pq->initialized=FALSE;
 
75
   pq->leq=leq;
 
76
 
 
77
   return pq;
 
78
}
 
79
 
 
80
/* really __gl_pqSortDeletePriorityQ */
 
81
void pqDeletePriorityQ(PriorityQ* pq)
 
82
{
 
83
   assert(pq!=NULL);
 
84
   if (pq->heap!=NULL)
 
85
   {
 
86
          __gl_pqHeapDeletePriorityQ(pq->heap);
 
87
   }
 
88
   if (pq->order!=NULL)
 
89
   {
 
90
          memFree(pq->order);
 
91
   }
 
92
   if (pq->keys!=NULL)
 
93
   {
 
94
          memFree(pq->keys);
 
95
   }
 
96
   memFree(pq);
 
97
}
 
98
 
 
99
#define LT(x,y)   (!LEQ(y,x))
 
100
#define GT(x,y)   (!LEQ(x,y))
 
101
#define Swap(a, b) if(1) { PQkey* tmp=*a; *a=*b; *b=tmp; } else {;}
 
102
 
 
103
/* really __gl_pqSortInit */
 
104
int pqInit(PriorityQ* pq)
 
105
{
 
106
   PQkey**p, **r, **i, **j, *piv;
 
107
   struct
 
108
   {
 
109
          PQkey** p;
 
110
          PQkey** r;
 
111
   } Stack[50], *top=Stack;
 
112
   unsigned long seed=2016473283;
 
113
 
 
114
   /* Create an array of indirect pointers to the keys, so that we
 
115
        * the handles we have returned are still valid.
 
116
        */
 
117
   /*
 
118
   pq->order = (PQHeapKey **)memAlloc( (size_t)
 
119
                                                                  (pq->size * sizeof(pq->order[0])) );
 
120
   */
 
121
   pq->order=(PQHeapKey**)memAlloc((size_t)((pq->size+1)*sizeof(pq->order[0])));
 
122
   /* the previous line is a patch to compensate for the fact that IBM */
 
123
   /* machines return a null on a malloc of zero bytes (unlike SGI),   */
 
124
   /* so we have to put in this defense to guard against a memory      */
 
125
   /* fault four lines down. from fossum@austin.ibm.com.               */
 
126
   if (pq->order==NULL)
 
127
   {
 
128
          return 0;
 
129
   }
 
130
 
 
131
   p=pq->order;
 
132
   r=p+pq->size-1;
 
133
   for (piv=pq->keys, i=p; i<=r; ++piv, ++i)
 
134
   {
 
135
          *i=piv;
 
136
   }
 
137
 
 
138
   /* Sort the indirect pointers in descending order,
 
139
        * using randomized Quicksort
 
140
        */
 
141
   top->p=p; top->r=r; ++top;
 
142
   while (--top>=Stack)
 
143
   {
 
144
          p=top->p;
 
145
          r=top->r;
 
146
          while (r>p+10)
 
147
          {
 
148
                 seed=seed*1539415821+1;
 
149
                 i=p+seed%(r-p+1);
 
150
                 piv=*i;
 
151
                 *i=*p;
 
152
                 *p=piv;
 
153
                 i=p-1;
 
154
                 j=r+1;
 
155
                 do {
 
156
                        do {
 
157
                           ++i;
 
158
                        } while(GT(**i, *piv));
 
159
                        do {
 
160
                           --j;
 
161
                        } while(LT(**j, *piv));
 
162
                        Swap(i, j);
 
163
                 } while(i<j);
 
164
                 Swap(i, j);       /* Undo last swap */
 
165
                 if (i-p<r-j)
 
166
                 {
 
167
                        top->p=j+1;
 
168
                        top->r=r;
 
169
                        ++top;
 
170
                        r=i-1;
 
171
                 }
 
172
                 else
 
173
                 {
 
174
                        top->p=p;
 
175
                        top->r=i-1;
 
176
                        ++top;
 
177
                        p=j+1;
 
178
                 }
 
179
          }
 
180
 
 
181
          /* Insertion sort small lists */
 
182
          for (i=p+1; i<=r; ++i)
 
183
          {
 
184
                 piv=*i;
 
185
                 for (j=i; j>p && LT(**(j-1), *piv); --j)
 
186
                 {
 
187
                        *j=*(j-1);
 
188
                 }
 
189
                 *j=piv;
 
190
          }
 
191
   }
 
192
 
 
193
   pq->max=pq->size;
 
194
   pq->initialized=TRUE;
 
195
   __gl_pqHeapInit(pq->heap);   /* always succeeds */
 
196
 
 
197
#ifndef NDEBUG
 
198
   p=pq->order;
 
199
   r=p+pq->size-1;
 
200
 
 
201
   for (i=p; i<r; ++i)
 
202
   {
 
203
          assert(LEQ(**(i+1), **i));
 
204
   }
 
205
#endif
 
206
 
 
207
   return 1;
 
208
}
 
209
 
 
210
/* really __gl_pqSortInsert */
 
211
/* returns LONG_MAX iff out of memory */
 
212
PQhandle pqInsert(PriorityQ* pq, PQkey keyNew)
 
213
{
 
214
   long curr;
 
215
 
 
216
   if (pq->initialized)
 
217
   {
 
218
          return __gl_pqHeapInsert(pq->heap, keyNew);
 
219
   }
 
220
 
 
221
   curr=pq->size;
 
222
   if (++pq->size>=pq->max)
 
223
   {
 
224
          PQkey* saveKey=pq->keys;
 
225
 
 
226
          /* If the heap overflows, double its size. */
 
227
          pq->max<<=1;
 
228
          pq->keys=(PQHeapKey*)memRealloc(pq->keys, (size_t)(pq->max*sizeof(pq->keys[0])));
 
229
          if (pq->keys==NULL)
 
230
          {
 
231
                 /* restore ptr to free upon return */
 
232
                 pq->keys=saveKey;
 
233
                 return LONG_MAX;
 
234
          }
 
235
   }
 
236
   assert(curr!=LONG_MAX);
 
237
   pq->keys[curr]=keyNew;
 
238
 
 
239
   /* Negative handles index the sorted array. */
 
240
   return -(curr+1);
 
241
}
 
242
 
 
243
/* really __gl_pqSortExtractMin */
 
244
PQkey pqExtractMin(PriorityQ* pq)
 
245
{
 
246
   PQkey sortMin, heapMin;
 
247
 
 
248
   if (pq->size==0)
 
249
   {
 
250
          return __gl_pqHeapExtractMin(pq->heap);
 
251
   }
 
252
 
 
253
   sortMin=*(pq->order[pq->size-1]);
 
254
   if (!__gl_pqHeapIsEmpty(pq->heap))
 
255
   {
 
256
          heapMin=__gl_pqHeapMinimum(pq->heap);
 
257
          if (LEQ(heapMin, sortMin))
 
258
          {
 
259
                 return __gl_pqHeapExtractMin(pq->heap);
 
260
          }
 
261
   }
 
262
   do {
 
263
          --pq->size;
 
264
   } while(pq->size>0 && *(pq->order[pq->size-1])==NULL);
 
265
 
 
266
   return sortMin;
 
267
}
 
268
 
 
269
/* really __gl_pqSortMinimum */
 
270
PQkey pqMinimum(PriorityQ* pq)
 
271
{
 
272
   PQkey sortMin, heapMin;
 
273
 
 
274
   if (pq->size==0)
 
275
   {
 
276
          return __gl_pqHeapMinimum(pq->heap);
 
277
   }
 
278
 
 
279
   sortMin=*(pq->order[pq->size-1]);
 
280
   if (!__gl_pqHeapIsEmpty(pq->heap))
 
281
   {
 
282
          heapMin=__gl_pqHeapMinimum(pq->heap);
 
283
          if (LEQ(heapMin, sortMin))
 
284
          {
 
285
                 return heapMin;
 
286
          }
 
287
   }
 
288
 
 
289
   return sortMin;
 
290
}
 
291
 
 
292
/* really __gl_pqSortIsEmpty */
 
293
int pqIsEmpty(PriorityQ* pq)
 
294
{
 
295
   return (pq->size==0) && __gl_pqHeapIsEmpty(pq->heap);
 
296
}
 
297
 
 
298
/* really __gl_pqSortDelete */
 
299
void pqDelete(PriorityQ* pq, PQhandle curr)
 
300
{
 
301
   if (curr>=0)
 
302
   {
 
303
          __gl_pqHeapDelete(pq->heap, curr);
 
304
          return;
 
305
   }
 
306
 
 
307
   curr=-(curr+1);
 
308
   assert(curr<pq->max && pq->keys[curr]!=NULL);
 
309
 
 
310
   pq->keys[curr]=NULL;
 
311
 
 
312
   while(pq->size>0 && *(pq->order[pq->size-1])==NULL)
 
313
   {
 
314
          --pq->size;
 
315
   }
 
316
}