ReactOS 0.4.15-dev-7659-ga55345b
priorityq-heap.c File Reference
#include "priorityq-heap.h"
#include "geom.h"
Include dependency graph for priorityq-heap.c:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros

#define INIT_SIZE   32
 
#define TRUE   1
 
#define FALSE   0
 
#define LEQ(x, y)   VertLeq((GLUvertex *)x, (GLUvertex *)y)
 

Functions

PriorityQpqNewPriorityQ (int(*leq)(PQkey key1, PQkey key2))
 
void pqDeletePriorityQ (PriorityQ *pq)
 
static void FloatDown (PriorityQ *pq, long curr)
 
static void FloatUp (PriorityQ *pq, long curr)
 
void pqInit (PriorityQ *pq)
 
PQhandle pqInsert (PriorityQ *pq, PQkey keyNew)
 
PQkey pqExtractMin (PriorityQ *pq)
 
void pqDelete (PriorityQ *pq, PQhandle hCurr)
 

Macro Definition Documentation

◆ FALSE

#define FALSE   0

Definition at line 46 of file priorityq-heap.c.

◆ INIT_SIZE

#define INIT_SIZE   32

Definition at line 40 of file priorityq-heap.c.

◆ LEQ

#define LEQ (   x,
  y 
)    VertLeq((GLUvertex *)x, (GLUvertex *)y)

Definition at line 54 of file priorityq-heap.c.

◆ TRUE

#define TRUE   1

Definition at line 43 of file priorityq-heap.c.

Function Documentation

◆ FloatDown()

static void FloatDown ( PriorityQ pq,
long  curr 
)
static

Definition at line 96 of file priorityq-heap.c.

97{
98 PQnode *n = pq->nodes;
99 PQhandleElem *h = pq->handles;
100 PQhandle hCurr, hChild;
101 long child;
102
103 hCurr = n[curr].handle;
104 for( ;; ) {
105 child = curr << 1;
106 if( child < pq->size && LEQ( h[n[child+1].handle].key,
107 h[n[child].handle].key )) {
108 ++child;
109 }
110
111 assert(child <= pq->max);
112
113 hChild = n[child].handle;
114 if( child > pq->size || LEQ( h[hCurr].key, h[hChild].key )) {
115 n[curr].handle = hCurr;
116 h[hCurr].node = curr;
117 break;
118 }
119 n[curr].handle = hChild;
120 h[hChild].node = curr;
121 curr = child;
122 }
123}
#define assert(x)
Definition: debug.h:53
GLsizeiptr size
Definition: glext.h:5919
GLdouble n
Definition: glext.h:7729
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
static HTREEITEM hChild
Definition: treeview.c:381
static HWND child
Definition: cursoricon.c:298
#define LEQ(x, y)
long PQhandle
PQnode * nodes
PQhandleElem * handles
Definition: copy.c:22
#define max(a, b)
Definition: svc.c:63

Referenced by pqDelete(), pqExtractMin(), and pqInit().

◆ FloatUp()

static void FloatUp ( PriorityQ pq,
long  curr 
)
static

Definition at line 126 of file priorityq-heap.c.

127{
128 PQnode *n = pq->nodes;
129 PQhandleElem *h = pq->handles;
130 PQhandle hCurr, hParent;
131 long parent;
132
133 hCurr = n[curr].handle;
134 for( ;; ) {
135 parent = curr >> 1;
136 hParent = n[parent].handle;
137 if( parent == 0 || LEQ( h[hParent].key, h[hCurr].key )) {
138 n[curr].handle = hCurr;
139 h[hCurr].node = curr;
140 break;
141 }
142 n[curr].handle = hParent;
143 h[hParent].node = curr;
144 curr = parent;
145 }
146}
r parent
Definition: btrfs.c:3010

Referenced by pqDelete(), and pqInsert().

◆ pqDelete()

void pqDelete ( PriorityQ pq,
PQhandle  hCurr 
)

Definition at line 234 of file priorityq-heap.c.

235{
236 PQnode *n = pq->nodes;
237 PQhandleElem *h = pq->handles;
238 long curr;
239
240 assert( hCurr >= 1 && hCurr <= pq->max && h[hCurr].key != NULL );
241
242 curr = h[hCurr].node;
243 n[curr].handle = n[pq->size].handle;
244 h[n[curr].handle].node = curr;
245
246 if( curr <= -- pq->size ) {
247 if( curr <= 1 || LEQ( h[n[curr>>1].handle].key, h[n[curr].handle].key )) {
248 FloatDown( pq, curr );
249 } else {
250 FloatUp( pq, curr );
251 }
252 }
253 h[hCurr].key = NULL;
254 h[hCurr].node = pq->freeList;
255 pq->freeList = hCurr;
256}
#define NULL
Definition: types.h:112
static void FloatDown(PriorityQ *pq, long curr)
static void FloatUp(PriorityQ *pq, long curr)
PQhandle freeList

◆ pqDeletePriorityQ()

void pqDeletePriorityQ ( PriorityQ pq)

Definition at line 88 of file priorityq-heap.c.

89{
90 memFree( pq->handles );
91 memFree( pq->nodes );
92 memFree( pq );
93}
#define memFree
Definition: memalloc.h:41

◆ pqExtractMin()

PQkey pqExtractMin ( PriorityQ pq)

Definition at line 211 of file priorityq-heap.c.

212{
213 PQnode *n = pq->nodes;
214 PQhandleElem *h = pq->handles;
215 PQhandle hMin = n[1].handle;
216 PQkey min = h[hMin].key;
217
218 if( pq->size > 0 ) {
219 n[1].handle = n[pq->size].handle;
220 h[n[1].handle].node = 1;
221
222 h[hMin].key = NULL;
223 h[hMin].node = pq->freeList;
224 pq->freeList = hMin;
225
226 if( -- pq->size > 0 ) {
227 FloatDown( pq, 1 );
228 }
229 }
230 return min;
231}
#define min(a, b)
Definition: monoChain.cc:55

◆ pqInit()

void pqInit ( PriorityQ pq)

Definition at line 149 of file priorityq-heap.c.

150{
151 long i;
152
153 /* This method of building a heap is O(n), rather than O(n lg n). */
154
155 for( i = pq->size; i >= 1; --i ) {
156 FloatDown( pq, i );
157 }
158 pq->initialized = TRUE;
159}
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
#define TRUE

◆ pqInsert()

PQhandle pqInsert ( PriorityQ pq,
PQkey  keyNew 
)

Definition at line 163 of file priorityq-heap.c.

164{
165 long curr;
167
168 curr = ++ pq->size;
169 if( (curr*2) > pq->max ) {
170 PQnode *saveNodes= pq->nodes;
171 PQhandleElem *saveHandles= pq->handles;
172
173 /* If the heap overflows, double its size. */
174 pq->max <<= 1;
175 pq->nodes = (PQnode *)memRealloc( pq->nodes,
176 (size_t)
177 ((pq->max + 1) * sizeof( pq->nodes[0] )));
178 if (pq->nodes == NULL) {
179 pq->nodes = saveNodes; /* restore ptr to free upon return */
180 return LONG_MAX;
181 }
183 (size_t)
184 ((pq->max + 1) *
185 sizeof( pq->handles[0] )));
186 if (pq->handles == NULL) {
187 pq->handles = saveHandles; /* restore ptr to free upon return */
188 return LONG_MAX;
189 }
190 }
191
192 if( pq->freeList == 0 ) {
193 free_handle = curr;
194 } else {
195 free_handle = pq->freeList;
196 pq->freeList = pq->handles[free_handle].node;
197 }
198
199 pq->nodes[curr].handle = free_handle;
200 pq->handles[free_handle].node = curr;
201 pq->handles[free_handle].key = keyNew;
202
203 if( pq->initialized ) {
204 FloatUp( pq, curr );
205 }
207 return free_handle;
208}
BOOL free_handle(HINTERNET hinternet)
Definition: handle.c:123
#define LONG_MAX
Definition: limits.h:43
#define memRealloc
Definition: memalloc.h:40
PQhandle node
PQhandle handle

◆ pqNewPriorityQ()

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

Definition at line 58 of file priorityq-heap.c.

59{
60 PriorityQ *pq = (PriorityQ *)memAlloc( sizeof( PriorityQ ));
61 if (pq == NULL) return NULL;
62
63 pq->size = 0;
64 pq->max = INIT_SIZE;
65 pq->nodes = (PQnode *)memAlloc( (INIT_SIZE + 1) * sizeof(pq->nodes[0]) );
66 if (pq->nodes == NULL) {
67 memFree(pq);
68 return NULL;
69 }
70
71 pq->handles = (PQhandleElem *)memAlloc( (INIT_SIZE + 1) * sizeof(pq->handles[0]) );
72 if (pq->handles == NULL) {
73 memFree(pq->nodes);
74 memFree(pq);
75 return NULL;
76 }
77
78 pq->initialized = FALSE;
79 pq->freeList = 0;
80 pq->leq = leq;
81
82 pq->nodes[1].handle = 1; /* so that Minimum() returns NULL */
83 pq->handles[1].key = NULL;
84 return pq;
85}
#define memAlloc
Definition: memalloc.h:48
#define INIT_SIZE
#define FALSE
int(* leq)(PQkey key1, PQkey key2)