ReactOS  0.4.14-dev-1115-gebeeb9d
priorityq-heap.c
Go to the documentation of this file.
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 <stddef.h>
36 //#include <assert.h>
37 #include "priorityq-heap.h"
38 //#include "memalloc.h"
39 
40 #define INIT_SIZE 32
41 
42 #ifndef TRUE
43 #define TRUE 1
44 #endif
45 #ifndef FALSE
46 #define FALSE 0
47 #endif
48 
49 #ifdef FOR_TRITE_TEST_PROGRAM
50 #define LEQ(x,y) (*pq->leq)(x,y)
51 #else
52 /* Violates modularity, but a little faster */
53 #include "geom.h"
54 #define LEQ(x,y) VertLeq((GLUvertex *)x, (GLUvertex *)y)
55 #endif
56 
57 /* really __gl_pqHeapNewPriorityQ */
58 PriorityQ *pqNewPriorityQ( int (*leq)(PQkey key1, PQkey key2) )
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 }
86 
87 /* really __gl_pqHeapDeletePriorityQ */
89 {
90  memFree( pq->handles );
91  memFree( pq->nodes );
92  memFree( pq );
93 }
94 
95 
96 static void FloatDown( PriorityQ *pq, long curr )
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 }
124 
125 
126 static void FloatUp( PriorityQ *pq, long curr )
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 }
147 
148 /* really __gl_pqHeapInit */
149 void pqInit( PriorityQ *pq )
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 }
160 
161 /* really __gl_pqHeapInsert */
162 /* returns LONG_MAX iff out of memory */
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 }
209 
210 /* really __gl_pqHeapExtractMin */
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 }
232 
233 /* really __gl_pqHeapDelete */
234 void pqDelete( PriorityQ *pq, PQhandle hCurr )
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
GLuint64EXT GLuint GLuint GLenum GLenum GLuint GLuint GLenum GLuint GLuint key1
Definition: glext.h:10608
static HTREEITEM hChild
Definition: treeview.c:381
PQhandleElem * handles
PriorityQ * pqNewPriorityQ(int(*leq)(PQkey key1, PQkey key2))
GLdouble n
Definition: glext.h:7729
static void FloatUp(PriorityQ *pq, long curr)
#define assert(x)
Definition: debug.h:53
#define INIT_SIZE
PQhandle pqInsert(PriorityQ *pq, PQkey keyNew)
#define TRUE
#define FALSE
static HWND child
Definition: cursoricon.c:298
#define memRealloc
Definition: memalloc.h:40
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
void pqDelete(PriorityQ *pq, PQhandle hCurr)
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
smooth NULL
Definition: ftsmooth.c:416
#define LEQ(x, y)
PQnode * nodes
PQkey pqExtractMin(PriorityQ *pq)
GLsizeiptr size
Definition: glext.h:5919
r parent
Definition: btrfs.c:2869
long PQhandle
void pqInit(PriorityQ *pq)
void pqDeletePriorityQ(PriorityQ *pq)
#define LONG_MAX
Definition: limits.h:43
PQhandle freeList
const DOCKBAR PVOID HWND hParent
Definition: tooldock.h:22
BOOL free_handle(HINTERNET hinternet)
Definition: handle.c:123
int(* leq)(PQkey key1, PQkey key2)
#define memFree
Definition: memalloc.h:41
PQhandle node
#define min(a, b)
Definition: monoChain.cc:55
PQhandle handle
#define memAlloc
Definition: memalloc.h:48
Definition: path.c:41
static void FloatDown(PriorityQ *pq, long curr)