ReactOS 0.4.15-dev-5666-gc548b97
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 */
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
96static 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
126static 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 */
149void 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 }
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 */
234void 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 NULL
Definition: types.h:112
BOOL free_handle(HINTERNET hinternet)
Definition: handle.c:123
#define assert(x)
Definition: debug.h:53
r parent
Definition: btrfs.c:3010
GLsizeiptr size
Definition: glext.h:5919
GLdouble n
Definition: glext.h:7729
GLuint64EXT GLuint GLuint GLenum GLenum GLuint GLuint GLenum GLuint GLuint key1
Definition: glext.h:10608
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
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 LONG_MAX
Definition: limits.h:43
#define memAlloc
Definition: memalloc.h:48
#define memRealloc
Definition: memalloc.h:40
#define memFree
Definition: memalloc.h:41
static HTREEITEM hChild
Definition: treeview.c:381
static HWND child
Definition: cursoricon.c:298
#define min(a, b)
Definition: monoChain.cc:55
#define LEQ(x, y)
static void FloatDown(PriorityQ *pq, long curr)
#define INIT_SIZE
#define TRUE
#define FALSE
static void FloatUp(PriorityQ *pq, long curr)
#define pqNewPriorityQ(leq)
#define pqDeletePriorityQ(pq)
#define pqInit(pq)
long PQhandle
#define pqDelete(pq, handle)
#define pqExtractMin(pq)
#define pqInsert(pq, key)
PQhandle node
PQhandle handle
PQnode * nodes
PQhandleElem * handles
PQhandle freeList
int(* leq)(PQkey key1, PQkey key2)
Definition: copy.c:22
#define max(a, b)
Definition: svc.c:63