ReactOS 0.4.15-dev-7887-g64a59a1
priorityq.c File Reference
#include "gluos.h"
#include <assert.h>
#include "memalloc.h"
#include "priorityq-heap.c"
#include "priorityq-sort.h"
Include dependency graph for priorityq.c:

Go to the source code of this file.

Macros

#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)
 

Functions

PriorityQpqNewPriorityQ (int(*leq)(PQkey key1, PQkey key2))
 
void pqDeletePriorityQ (PriorityQ *pq)
 
int pqInit (PriorityQ *pq)
 
PQhandle pqInsert (PriorityQ *pq, PQkey keyNew)
 
PQkey pqExtractMin (PriorityQ *pq)
 
PQkey pqMinimum (PriorityQ *pq)
 
int pqIsEmpty (PriorityQ *pq)
 
void pqDelete (PriorityQ *pq, PQhandle curr)
 

Macro Definition Documentation

◆ GT

#define GT (   x,
  y 
)    (! LEQ(x,y))

Definition at line 88 of file priorityq.c.

◆ LT

#define LT (   x,
  y 
)    (! LEQ(y,x))

Definition at line 87 of file priorityq.c.

◆ Swap

#define Swap (   a,
  b 
)    do{PQkey *tmp = *a; *a = *b; *b = tmp;}while(0)

Definition at line 89 of file priorityq.c.

Function Documentation

◆ pqDelete()

void pqDelete ( PriorityQ pq,
PQhandle  curr 
)

Definition at line 248 of file priorityq.c.

249{
250 if( curr >= 0 ) {
251 __gl_pqHeapDelete( pq->heap, curr );
252 return;
253 }
254 curr = -(curr+1);
255 assert( curr < pq->max && pq->keys[curr] != NULL );
256
257 pq->keys[curr] = NULL;
258 while( pq->size > 0 && *(pq->order[pq->size-1]) == NULL ) {
259 -- pq->size;
260 }
261}
#define NULL
Definition: types.h:112
#define assert(x)
Definition: debug.h:53
PriorityQHeap * heap
PQkey ** order
PQkey * keys
#define max(a, b)
Definition: svc.c:63

◆ pqDeletePriorityQ()

void pqDeletePriorityQ ( PriorityQ pq)

Definition at line 77 of file priorityq.c.

78{
79 assert(pq != NULL);
80 if (pq->heap != NULL) __gl_pqHeapDeletePriorityQ( pq->heap );
81 if (pq->order != NULL) memFree( pq->order );
82 if (pq->keys != NULL) memFree( pq->keys );
83 memFree( pq );
84}
#define memFree
Definition: memalloc.h:41

◆ pqExtractMin()

PQkey pqExtractMin ( PriorityQ pq)

Definition at line 203 of file priorityq.c.

204{
205 PQkey sortMin, heapMin;
206
207 if( pq->size == 0 ) {
208 return __gl_pqHeapExtractMin( pq->heap );
209 }
210 sortMin = *(pq->order[pq->size-1]);
211 if( ! __gl_pqHeapIsEmpty( pq->heap )) {
212 heapMin = __gl_pqHeapMinimum( pq->heap );
213 if( LEQ( heapMin, sortMin )) {
214 return __gl_pqHeapExtractMin( pq->heap );
215 }
216 }
217 do {
218 -- pq->size;
219 } while( pq->size > 0 && *(pq->order[pq->size-1]) == NULL );
220 return sortMin;
221}
#define LEQ(x, y)
#define __gl_pqHeapMinimum(pq)
#define __gl_pqHeapIsEmpty(pq)

◆ pqInit()

int pqInit ( PriorityQ pq)

Definition at line 92 of file priorityq.c.

93{
94 PQkey **p, **r, **i, **j, *piv;
95 struct { PQkey **p, **r; } Stack[50], *top = Stack;
96 unsigned long seed = 2016473283;
97
98 /* Create an array of indirect pointers to the keys, so that we
99 * the handles we have returned are still valid.
100 */
101/*
102 pq->order = (PQHeapKey **)memAlloc( (size_t)
103 (pq->size * sizeof(pq->order[0])) );
104*/
105 pq->order = (PQHeapKey **)memAlloc( (size_t)
106 ((pq->size+1) * sizeof(pq->order[0])) );
107/* the previous line is a patch to compensate for the fact that IBM */
108/* machines return a null on a malloc of zero bytes (unlike SGI), */
109/* so we have to put in this defense to guard against a memory */
110/* fault four lines down. from fossum@austin.ibm.com. */
111 if (pq->order == NULL) return 0;
112
113 p = pq->order;
114 r = p + pq->size - 1;
115 for( piv = pq->keys, i = p; i <= r; ++piv, ++i ) {
116 *i = piv;
117 }
118
119 /* Sort the indirect pointers in descending order,
120 * using randomized Quicksort
121 */
122 top->p = p; top->r = r; ++top;
123 while( --top >= Stack ) {
124 p = top->p;
125 r = top->r;
126 while( r > p + 10 ) {
127 seed = seed * 1539415821 + 1;
128 i = p + seed % (r - p + 1);
129 piv = *i;
130 *i = *p;
131 *p = piv;
132 i = p - 1;
133 j = r + 1;
134 do {
135 do { ++i; } while( GT( **i, *piv ));
136 do { --j; } while( LT( **j, *piv ));
137 Swap( i, j );
138 } while( i < j );
139 Swap( i, j ); /* Undo last swap */
140 if( i - p < r - j ) {
141 top->p = j+1; top->r = r; ++top;
142 r = i-1;
143 } else {
144 top->p = p; top->r = i-1; ++top;
145 p = j+1;
146 }
147 }
148 /* Insertion sort small lists */
149 for( i = p+1; i <= r; ++i ) {
150 piv = *i;
151 for( j = i; j > p && LT( **(j-1), *piv ); --j ) {
152 *j = *(j-1);
153 }
154 *j = piv;
155 }
156 }
157 pq->max = pq->size;
158 pq->initialized = TRUE;
159 __gl_pqHeapInit( pq->heap ); /* always succeeds */
160
161#ifndef NDEBUG
162 p = pq->order;
163 r = p + pq->size - 1;
164 for( i = p; i < r; ++i ) {
165 assert( LEQ( **(i+1), **i ));
166 }
167#endif
168
169 return 1;
170}
#define TRUE
Definition: types.h:120
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
GLdouble GLdouble GLdouble GLdouble top
Definition: glext.h:10859
GLfloat GLfloat p
Definition: glext.h:8902
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint GLint GLint j
Definition: glfuncs.h:250
#define memAlloc
Definition: memalloc.h:48
#define LT(x, y)
Definition: priorityq.c:87
#define GT(x, y)
Definition: priorityq.c:88
#define Swap(a, b)
Definition: priorityq.c:89
_In_ WDFREQUEST _In_ PIO_STACK_LOCATION Stack
Definition: wdfrequest.h:639

◆ pqInsert()

PQhandle pqInsert ( PriorityQ pq,
PQkey  keyNew 
)

Definition at line 174 of file priorityq.c.

175{
176 long curr;
177
178 if( pq->initialized ) {
179 return __gl_pqHeapInsert( pq->heap, keyNew );
180 }
181 curr = pq->size;
182 if( ++ pq->size >= pq->max ) {
183 PQkey *saveKey= pq->keys;
184
185 /* If the heap overflows, double its size. */
186 pq->max <<= 1;
187 pq->keys = (PQHeapKey *)memRealloc( pq->keys,
188 (size_t)
189 (pq->max * sizeof( pq->keys[0] )));
190 if (pq->keys == NULL) {
191 pq->keys = saveKey; /* restore ptr to free upon return */
192 return LONG_MAX;
193 }
194 }
195 assert(curr != LONG_MAX);
196 pq->keys[curr] = keyNew;
197
198 /* Negative handles index the sorted array. */
199 return -(curr+1);
200}
#define LONG_MAX
Definition: limits.h:43
#define memRealloc
Definition: memalloc.h:40

◆ pqIsEmpty()

int pqIsEmpty ( PriorityQ pq)

Definition at line 242 of file priorityq.c.

243{
244 return (pq->size == 0) && __gl_pqHeapIsEmpty( pq->heap );
245}

◆ pqMinimum()

PQkey pqMinimum ( PriorityQ pq)

Definition at line 224 of file priorityq.c.

225{
226 PQkey sortMin, heapMin;
227
228 if( pq->size == 0 ) {
229 return __gl_pqHeapMinimum( pq->heap );
230 }
231 sortMin = *(pq->order[pq->size-1]);
232 if( ! __gl_pqHeapIsEmpty( pq->heap )) {
233 heapMin = __gl_pqHeapMinimum( pq->heap );
234 if( LEQ( heapMin, sortMin )) {
235 return heapMin;
236 }
237 }
238 return sortMin;
239}

◆ pqNewPriorityQ()

PriorityQ * pqNewPriorityQ ( int(*)(PQkey key1, PQkey key2)  leq)

Definition at line 50 of file priorityq.c.

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->order = NULL;
69 pq->size = 0;
70 pq->max = INIT_SIZE;
71 pq->initialized = FALSE;
72 pq->leq = leq;
73 return pq;
74}
#define FALSE
Definition: types.h:117
#define INIT_SIZE
int(* leq)(PQkey key1, PQkey key2)