ReactOS  0.4.14-dev-1115-gebeeb9d
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 max(a, b)
Definition: svc.c:63
static HTREEITEM hChild
Definition: treeview.c:381
PQhandleElem * handles
GLdouble n
Definition: glext.h:7729
#define assert(x)
Definition: debug.h:53
static HWND child
Definition: cursoricon.c:298
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
#define LEQ(x, y)
PQnode * nodes
GLsizeiptr size
Definition: glext.h:5919
long PQhandle
Definition: path.c:41

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 }
PQhandleElem * handles
GLdouble n
Definition: glext.h:7729
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
#define LEQ(x, y)
PQnode * nodes
r parent
Definition: btrfs.c:2869
long PQhandle
const DOCKBAR PVOID HWND hParent
Definition: tooldock.h:22
Definition: path.c:41

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 max(a, b)
Definition: svc.c:63
PQhandleElem * handles
GLdouble n
Definition: glext.h:7729
static void FloatUp(PriorityQ *pq, long curr)
#define assert(x)
Definition: debug.h:53
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
smooth NULL
Definition: ftsmooth.c:416
#define LEQ(x, y)
PQnode * nodes
GLsizeiptr size
Definition: glext.h:5919
PQhandle freeList
Definition: path.c:41
static void FloatDown(PriorityQ *pq, long curr)

◆ 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 }
PQhandleElem * handles
PQnode * nodes
#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 }
PQhandleElem * handles
GLdouble n
Definition: glext.h:7729
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
smooth NULL
Definition: ftsmooth.c:416
PQnode * nodes
long PQhandle
PQhandle freeList
#define min(a, b)
Definition: monoChain.cc:55
static void FloatDown(PriorityQ *pq, long curr)

◆ 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 }
#define TRUE
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
static void FloatDown(PriorityQ *pq, long curr)

◆ 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  }
182  pq->handles = (PQhandleElem *)memRealloc( pq->handles,
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 }
PQhandleElem * handles
static void FloatUp(PriorityQ *pq, long curr)
#define assert(x)
Definition: debug.h:53
#define memRealloc
Definition: memalloc.h:40
smooth NULL
Definition: ftsmooth.c:416
PQnode * nodes
long PQhandle
#define LONG_MAX
Definition: limits.h:43
PQhandle freeList
BOOL free_handle(HINTERNET hinternet)
Definition: handle.c:123
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 }
PQhandleElem * handles
#define INIT_SIZE
#define FALSE
smooth NULL
Definition: ftsmooth.c:416
PQnode * nodes
PQhandle freeList
int(* leq)(PQkey key1, PQkey key2)
#define memFree
Definition: memalloc.h:41
PQhandle handle
#define memAlloc
Definition: memalloc.h:48