source: trunk/src/win32k/misc/avl.c@ 1467

Last change on this file since 1467 was 1467, checked in by bird, 26 years ago

Corrections to make win32k work.
(And now it does work, at least at my test machine...)
File size: 14.4 KB
Line 
1/* $Id: avl.c,v 1.1 1999-10-27 02:02:59 bird Exp $
2 *
3 * AVL-Tree (lookalike) implementation.
4 *
5 * Copyright (c) 1999 knut st. osmundsen
6 *
7 * Project Odin Software License can be found in LICENSE.TXT
8 *
9 */
10
11/*******************************************************************************
12* Defined Constants And Macros *
13*******************************************************************************/
14
15/*
16 * AVL configuration.
17 */
18#define AVL_MAX_HEIGHT 19 /* Up to 2^16 nodes. */
19#define assert
20
21/*
22 * AVL helper macros.
23 */
24#define AVL_HEIGHTOF(pNode) ((pNode) != NULL ? pNode->uchHeight : 0UL)
25#define max(a,b) (((a) > (b)) ? (a) : (b))
26
27
28/*******************************************************************************
29* Internal Functions *
30*******************************************************************************/
31#include <os2.h>
32#include "avl.h"
33#include "dev32.h"
34
35
36/*******************************************************************************
37* Structures and Typedefs *
38*******************************************************************************/
39/*
40 * A stack used to avoid recursive calls...
41 */
42typedef struct _AVLStack
43{
44 unsigned cEntries;
45 PPAVLNODECORE aEntries[AVL_MAX_HEIGHT];
46} AVLSTACK, *PAVLSTACK;
47
48
49/*******************************************************************************
50* Internal Functions *
51*******************************************************************************/
52_Inline void AVLRebalance(PAVLSTACK pStack);
53
54
55/**
56 * Inserts a node into the AVL-tree.
57 * @param ppTree Pointer to the AVL-tree root node pointer.
58 * @param pNode Pointer to the node which is to be added.
59 * @sketch Find the location of the node (using binary three algorithm.):
60 * LOOP until NULL leaf pointer
61 * BEGIN
62 * Add node pointer pointer to the AVL-stack.
63 * IF new-node-key < node key THEN
64 * left
65 * ELSE
66 * right
67 * END
68 * Fill in leaf node and insert it.
69 * Rebalance the tree.
70 * @status completely implemented.
71 * @author knut st. osmundsen
72 */
73void AVLInsert(PPAVLNODECORE ppTree, PAVLNODECORE pNode)
74{
75 AVLSTACK AVLStack;
76 PPAVLNODECORE ppCurNode = ppTree;
77 register AVLKEY Key = pNode->Key;
78 register PAVLNODECORE pCurNode;
79
80 AVLStack.cEntries = 0;
81
82 while ((pCurNode = *ppCurNode) != NULL)
83 {
84 assert(AVLStack.cEntries < AVL_MAX_HEIGHT);
85 AVLStack.aEntries[AVLStack.cEntries++] = ppCurNode;
86 if (pCurNode->Key > Key)
87 ppCurNode = &pCurNode->pLeft;
88 else
89 ppCurNode = &pCurNode->pRight;
90 }
91
92 pNode->pLeft = pNode->pRight = NULL;
93 pNode->uchHeight = 1;
94 *ppCurNode = pNode;
95
96 AVLRebalance(SSToDS(&AVLStack));
97}
98
99
100/**
101 * Removes a node from the AVL-tree.
102 * @returns Pointer to the node.
103 * @param ppTree Pointer to the AVL-tree root node pointer.
104 * @param Key Key value of the node which is to be removed.
105 * @sketch Find the node which is to be removed:
106 * LOOP until not found
107 * BEGIN
108 * Add node pointer pointer to the AVL-stack.
109 * IF the keys matches THEN break!
110 * IF remove key < node key THEN
111 * left
112 * ELSE
113 * right
114 * END
115 * IF found THEN
116 * BEGIN
117 * IF left node not empty THEN
118 * BEGIN
119 * Find the right most node in the left tree while adding the pointer to the pointer to it's parent to the stack:
120 * Start at left node.
121 * LOOP until right node is empty
122 * BEGIN
123 * Add to stack.
124 * go right.
125 * END
126 * Link out the found node.
127 * Replace the node which is to be removed with the found node.
128 * Correct the stack entry for the pointer to the left tree.
129 * END
130 * ELSE
131 * BEGIN
132 * Move up right node.
133 * Remove last stack entry.
134 * END
135 * Balance tree using stack.
136 * END
137 * return pointer to the removed node (if found).
138 * @status completely implemented.
139 * @author knut st. osmundsen
140 */
141PAVLNODECORE AVLRemove(PPAVLNODECORE ppTree, AVLKEY Key)
142{
143 AVLSTACK AVLStack;
144 PPAVLNODECORE ppDeleteNode = ppTree;
145 register PAVLNODECORE pDeleteNode;
146
147 AVLStack.cEntries = 0;
148
149 while ((pDeleteNode = *ppDeleteNode) != NULL)
150 {
151 assert(AVLStack.cEntries < AVL_MAX_HEIGHT);
152 AVLStack.aEntries[AVLStack.cEntries++] = ppDeleteNode;
153 if (pDeleteNode->Key == Key)
154 break;
155
156 if (pDeleteNode->Key > Key)
157 ppDeleteNode = &pDeleteNode->pLeft;
158 else
159 ppDeleteNode = &pDeleteNode->pRight;
160 }
161
162 if (pDeleteNode != NULL)
163 {
164 if (pDeleteNode->pLeft != NULL)
165 {
166 unsigned iStackEntry = AVLStack.cEntries;
167 PPAVLNODECORE ppLeftLeast = &pDeleteNode->pLeft;
168 register PAVLNODECORE pLeftLeast;
169
170 while ((pLeftLeast = *ppLeftLeast)->pRight != NULL) /* Left most node. */
171 {
172 assert(AVLStack.cEntries < AVL_MAX_HEIGHT);
173 AVLStack.aEntries[AVLStack.cEntries++] = ppLeftLeast;
174 ppLeftLeast = &pLeftLeast->pRight;
175 pLeftLeast = pLeftLeast->pRight;
176 }
177
178 /* link out pLeftLeast */
179 *ppLeftLeast = pLeftLeast->pLeft;
180
181 /* link in place of the delete node. */
182 pLeftLeast->pLeft = pDeleteNode->pLeft;
183 pLeftLeast->pRight = pDeleteNode->pRight;
184 pLeftLeast->uchHeight = pDeleteNode->uchHeight;
185 *ppDeleteNode = pLeftLeast;
186 AVLStack.aEntries[iStackEntry] = &pLeftLeast->pLeft;
187 }
188 else
189 {
190 *ppDeleteNode = pDeleteNode->pRight;
191 AVLStack.cEntries--;
192 }
193
194 AVLRebalance(SSToDS(&AVLStack));
195 }
196
197 return pDeleteNode;
198}
199
200
201/**
202 * Gets node from the tree (does not remove it!)
203 * @returns Pointer to the node holding the given key.
204 * @param ppTree Pointer to the AVL-tree root node pointer.
205 * @param Key Key value of the node which is to be found.
206 * @sketch
207 * @status completely implemented.
208 * @author knut st. osmundsen
209 */
210PAVLNODECORE AVLGet(PPAVLNODECORE ppTree, AVLKEY Key)
211{
212 register PAVLNODECORE pNode = *ppTree;
213
214 while (pNode != NULL && pNode->Key != Key)
215 {
216 if (pNode->Key > Key)
217 pNode = pNode->pLeft;
218 else
219 pNode = pNode->pRight;
220 }
221
222 return pNode;
223}
224
225
226/**
227 * Gets node from the tree (does not remove it!) and it's adjecent (by key value) nodes.
228 * @returns Pointer to the node holding the given key.
229 * @param ppTree Pointer to the AVL-tree root node pointer.
230 * @param Key Key value of the node which is to be found.
231 * @param ppLeft Pointer to left node pointer.
232 * @param ppRight Pointer to right node pointer.
233 * @sketch Find node with the given key, record search path on the stack.
234 * IF found THEN
235 * BEGIN
236 * Find the right-most node in the left subtree.
237 * Find the left-most node in the right subtree.
238 * Rewind the stack while searching for more adjecent nodes.
239 * END
240 * return node with adjecent nodes.
241 * @status completely implemented.
242 * @author knut st. osmundsen
243 */
244PAVLNODECORE AVLGetWithAdjecentNodes(PPAVLNODECORE ppTree, AVLKEY Key, PPAVLNODECORE ppLeft, PPAVLNODECORE ppRight)
245{
246 AVLSTACK AVLStack;
247 PPAVLNODECORE ppNode = ppTree;
248 PAVLNODECORE pNode;
249
250 AVLStack.cEntries = 0;
251
252 while ((pNode = *ppNode) != NULL && pNode->Key != Key)
253 {
254 assert(AVLStack.cEntries < AVL_MAX_HEIGHT);
255 AVLStack.aEntries[AVLStack.cEntries++] = ppNode;
256 if (pNode->Key > Key)
257 ppNode = &pNode->pLeft;
258 else
259 ppNode = &pNode->pRight;
260 }
261
262 if (pNode != NULL)
263 {
264 PAVLNODECORE pCurNode;
265
266 /* find rigth-most node in left subtree. */
267 pCurNode = pNode->pLeft;
268 if (pCurNode != NULL)
269 while (pCurNode->pRight != NULL)
270 pCurNode = pCurNode->pRight;
271 *ppLeft = pCurNode;
272
273 /* find left-most node in right subtree. */
274 pCurNode = pNode->pRight;
275 if (pCurNode != NULL)
276 while (pCurNode->pLeft != NULL)
277 pCurNode = pCurNode->pLeft;
278 *ppRight = pCurNode;
279
280 /* rewind stack */
281 while (AVLStack.cEntries-- > 0)
282 {
283 pCurNode = *AVLStack.aEntries[AVLStack.cEntries];
284 if (pCurNode->Key < Key && (*ppLeft == NULL || pCurNode->Key > (*ppLeft)->Key))
285 *ppLeft = pCurNode;
286 else if (pCurNode->Key > Key && (*ppRight == NULL || pCurNode->Key < (*ppRight)->Key))
287 *ppRight = pCurNode;
288 }
289 }
290 else
291 *ppLeft = *ppRight = NULL;
292
293 return pNode;
294}
295
296
297/**
298 * Rewindes a stack of pointer to pointers to nodes, rebalancing the tree.
299 * @param pStack Pointer to stack to rewind.
300 * @sketch LOOP thru all stack entries
301 * BEGIN
302 * Get pointer to pointer to node (and pointer to node) from stack.
303 * IF 2 higher left subtree than in right subtree THEN
304 * BEGIN
305 * IF higher (or equal) left-sub-subtree than right-sub-subtree THEN
306 * * n+2|n+3
307 * / \ / \
308 * n+2 n ==> n+1 n+1|n+2
309 * / \ / \
310 * n+1 n|n+1 n|n+1 n
311 *
312 * Or with keys:
313 *
314 * 4 2
315 * / \ / \
316 * 2 5 ==> 1 4
317 * / \ / \
318 * 1 3 3 5
319 *
320 * ELSE
321 * * n+2
322 * / \ / \
323 * n+2 n n+1 n+1
324 * / \ ==> / \ / \
325 * n n+1 n L R n
326 * / \
327 * L R
328 *
329 * Or with keys:
330 * 6 4
331 * / \ / \
332 * 2 7 ==> 2 6
333 * / \ / \ / \
334 * 1 4 1 3 5 7
335 * / \
336 * 3 5
337 * END
338 * ELSE IF 2 higher in right subtree than in left subtree THEN
339 * BEGIN
340 * Same as above but left <==> right. (invert the picture)
341 * ELSE
342 * IF correct height THEN break
343 * ELSE correct height.
344 * END
345 * @status
346 * @author knut st. osmundsen
347 * @remark
348 */
349_Inline void AVLRebalance(PAVLSTACK pStack)
350{
351 while (pStack->cEntries > 0)
352 {
353 PPAVLNODECORE ppNode = pStack->aEntries[--pStack->cEntries];
354 PAVLNODECORE pNode = *ppNode;
355 PAVLNODECORE pLeftNode = pNode->pLeft;
356 unsigned uLeftHeight = AVL_HEIGHTOF(pLeftNode);
357 PAVLNODECORE pRightNode = pNode->pRight;
358 unsigned uRightHeight = AVL_HEIGHTOF(pRightNode);
359
360 if (uRightHeight + 1 < uLeftHeight)
361 {
362 PAVLNODECORE pLeftLeftNode = pLeftNode->pLeft;
363 PAVLNODECORE pLeftRightNode = pLeftNode->pRight;
364 unsigned uLeftRightHeight = AVL_HEIGHTOF(pLeftRightNode);
365
366 if (AVL_HEIGHTOF(pLeftLeftNode) >= uLeftRightHeight)
367 {
368 pNode->pLeft = pLeftRightNode;
369 pLeftNode->pRight = pNode;
370 pLeftNode->uchHeight = 1 + (pNode->uchHeight = 1 + uLeftRightHeight);
371 *ppNode = pLeftNode;
372 }
373 else
374 {
375 pLeftNode->pRight = pLeftRightNode->pLeft;
376 pNode->pLeft = pLeftRightNode->pRight;
377 pLeftRightNode->pLeft = pLeftNode;
378 pLeftRightNode->pRight = pNode;
379 pLeftNode->uchHeight = pNode->uchHeight = uLeftRightHeight;
380 pLeftRightNode->uchHeight = uLeftHeight;
381 *ppNode = pLeftRightNode;
382 }
383 }
384 else if (uLeftHeight + 1 < uRightHeight)
385 {
386 PAVLNODECORE pRightLeftNode = pRightNode->pLeft;
387 unsigned uRightLeftHeight = AVL_HEIGHTOF(pRightLeftNode);
388 PAVLNODECORE pRightRightNode = pRightNode->pRight;
389
390 if (AVL_HEIGHTOF(pRightRightNode) >= uRightLeftHeight)
391 {
392 pNode->pRight = pRightLeftNode;
393 pRightNode->pLeft = pNode;
394 pRightNode->uchHeight = 1 + (pNode->uchHeight = 1 + uRightLeftHeight);
395 *ppNode = pRightNode;
396 }
397 else
398 {
399 pRightNode->pLeft = pRightLeftNode->pRight;
400 pNode->pRight = pRightLeftNode->pLeft;
401 pRightLeftNode->pRight = pRightNode;
402 pRightLeftNode->pLeft = pNode;
403 pRightNode->uchHeight = pNode->uchHeight = uRightLeftHeight;
404 pRightLeftNode->uchHeight = uRightHeight;
405 *ppNode = pRightLeftNode;
406 }
407 }
408 else
409 {
410 register unsigned uHeight = max(uLeftHeight, uRightHeight) + 1;
411 if (uHeight == pNode->uchHeight)
412 break;
413 pNode->uchHeight = uHeight;
414 }
415 }
416}
417
Note: See TracBrowser for help on using the repository browser.