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