← Back to branch summary

~ubuntu-branches/ubuntu/gutsy/vnc4/gutsy

« back to all changes in this revision

Viewing changes to unix/xc/extras/ogl-sample/main/gfx/lib/glu/libtess/priorityq.c

  • Committer: Bazaar Package Importer
  • Author(s): Ola Lundqvist
  • Date: 2006-05-15 20:35:17 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20060515203517-l4lre1ku942mn26k
Tags: 4.1.1+X4.3.0-10
* Correction of critical security issue. Thanks to Martin Kogler
  <e9925248@student.tuwien.ac.at> that informed me about the issue,
  and provided the patch.
  This flaw was originally found by Steve Wiseman of intelliadmin.com.
* Applied patch from Javier Kohen <jkohen@users.sourceforge.net> that
  inform the user that only 8 first characters of the password will
  actually be used when typing more than 8 characters, closes:
  #355619.

Show diffs side-by-side

added added

removed removed

Lines of Context:
unix/xc/extras/ogl-sample/main/gfx/lib/glu/libtess/priorityq.c
 
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 */
 
57
PriorityQ *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 */
 
83
void 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)       if(1){PQkey *tmp = *a; *a = *b; *b = tmp;}else
 
96
 
 
97
/* really __gl_pqSortInit */
 
98
int 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 */ 
 
180
PQhandle 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 */
 
209
PQkey 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 */
 
230
PQkey 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 */
 
248
int pqIsEmpty( PriorityQ *pq )
 
249
{
 
250
  return (pq->size == 0) && __gl_pqHeapIsEmpty( pq->heap );
 
251
}
 
252
 
 
253
/* really __gl_pqSortDelete */
 
254
void 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
}