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

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

Temporary backup checkin.
File size: 23.1 KB
Line 
1/* $Id: avl.c,v 1.2 2000-01-22 18:21:02 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 helper macros.
17 */
18#define AVL_HEIGHTOF(pNode) ((unsigned char)((pNode) != NULL ? pNode->uchHeight : 0))
19#define max(a,b) (((a) > (b)) ? (a) : (b))
20
21
22/*******************************************************************************
23* Internal Functions *
24*******************************************************************************/
25#include <os2.h>
26#include "avl.h"
27#include "dev32.h"
28
29#include <builtin.h>
30#define assert(a) ((a) ? (void)0 : __interrupt(3))
31
32
33/*******************************************************************************
34* Structures and Typedefs *
35*******************************************************************************/
36/*
37 * A stack used to avoid recursive calls...
38 */
39typedef struct _AVLStack
40{
41 unsigned cEntries;
42 PPAVLNODECORE aEntries[AVL_MAX_HEIGHT];
43} AVLSTACK, *PAVLSTACK;
44typedef struct _AVLStack2
45{
46 unsigned cEntries;
47 PAVLNODECORE aEntries[AVL_MAX_HEIGHT];
48 char achFlags[AVL_MAX_HEIGHT];
49} AVLSTACK2, *PAVLSTACK2;
50
51
52/*******************************************************************************
53* Internal Functions *
54*******************************************************************************/
55_Inline void AVLRebalance(PAVLSTACK pStack);
56
57
58/**
59 * Inserts a node into the AVL-tree.
60 * @param ppTree Pointer to the AVL-tree root node pointer.
61 * @param pNode Pointer to the node which is to be added.
62 * @sketch Find the location of the node (using binary three algorithm.):
63 * LOOP until NULL leaf pointer
64 * BEGIN
65 * Add node pointer pointer to the AVL-stack.
66 * IF new-node-key < node key THEN
67 * left
68 * ELSE
69 * right
70 * END
71 * Fill in leaf node and insert it.
72 * Rebalance the tree.
73 * @status completely implemented.
74 * @author knut st. osmundsen
75 */
76void AVLInsert(PPAVLNODECORE ppTree, PAVLNODECORE pNode)
77{
78 AVLSTACK AVLStack;
79 PPAVLNODECORE ppCurNode = ppTree;
80 register AVLKEY Key = pNode->Key;
81 register PAVLNODECORE pCurNode;
82
83 AVLStack.cEntries = 0;
84
85 while ((pCurNode = *ppCurNode) != NULL)
86 {
87 assert(AVLStack.cEntries < AVL_MAX_HEIGHT);
88 AVLStack.aEntries[AVLStack.cEntries++] = ppCurNode;
89 if (pCurNode->Key > Key)
90 ppCurNode = &pCurNode->pLeft;
91 else
92 ppCurNode = &pCurNode->pRight;
93 }
94
95 pNode->pLeft = pNode->pRight = NULL;
96 pNode->uchHeight = 1;
97 *ppCurNode = pNode;
98
99 AVLRebalance(SSToDS(&AVLStack));
100}
101
102
103/**
104 * Removes a node from the AVL-tree.
105 * @returns Pointer to the node.
106 * @param ppTree Pointer to the AVL-tree root node pointer.
107 * @param Key Key value of the node which is to be removed.
108 * @sketch Find the node which is to be removed:
109 * LOOP until not found
110 * BEGIN
111 * Add node pointer pointer to the AVL-stack.
112 * IF the keys matches THEN break!
113 * IF remove key < node key THEN
114 * left
115 * ELSE
116 * right
117 * END
118 * IF found THEN
119 * BEGIN
120 * IF left node not empty THEN
121 * BEGIN
122 * Find the right most node in the left tree while adding the pointer to the pointer to it's parent to the stack:
123 * Start at left node.
124 * LOOP until right node is empty
125 * BEGIN
126 * Add to stack.
127 * go right.
128 * END
129 * Link out the found node.
130 * Replace the node which is to be removed with the found node.
131 * Correct the stack entry for the pointer to the left tree.
132 * END
133 * ELSE
134 * BEGIN
135 * Move up right node.
136 * Remove last stack entry.
137 * END
138 * Balance tree using stack.
139 * END
140 * return pointer to the removed node (if found).
141 * @status completely implemented.
142 * @author knut st. osmundsen
143 */
144PAVLNODECORE AVLRemove(PPAVLNODECORE ppTree, AVLKEY Key)
145{
146 AVLSTACK AVLStack;
147 PPAVLNODECORE ppDeleteNode = ppTree;
148 register PAVLNODECORE pDeleteNode;
149
150 AVLStack.cEntries = 0;
151
152 while ((pDeleteNode = *ppDeleteNode) != NULL)
153 {
154 assert(AVLStack.cEntries < AVL_MAX_HEIGHT);
155 AVLStack.aEntries[AVLStack.cEntries++] = ppDeleteNode;
156 if (pDeleteNode->Key == Key)
157 break;
158
159 if (pDeleteNode->Key > Key)
160 ppDeleteNode = &pDeleteNode->pLeft;
161 else
162 ppDeleteNode = &pDeleteNode->pRight;
163 }
164
165 if (pDeleteNode != NULL)
166 {
167 if (pDeleteNode->pLeft != NULL)
168 {
169 unsigned iStackEntry = AVLStack.cEntries;
170 PPAVLNODECORE ppLeftLeast = &pDeleteNode->pLeft;
171 register PAVLNODECORE pLeftLeast;
172
173 while ((pLeftLeast = *ppLeftLeast)->pRight != NULL) /* Left most node. */
174 {
175 assert(AVLStack.cEntries < AVL_MAX_HEIGHT);
176 AVLStack.aEntries[AVLStack.cEntries++] = ppLeftLeast;
177 ppLeftLeast = &pLeftLeast->pRight;
178 pLeftLeast = pLeftLeast->pRight;
179 }
180
181 /* link out pLeftLeast */
182 *ppLeftLeast = pLeftLeast->pLeft;
183
184 /* link in place of the delete node. */
185 pLeftLeast->pLeft = pDeleteNode->pLeft;
186 pLeftLeast->pRight = pDeleteNode->pRight;
187 pLeftLeast->uchHeight = pDeleteNode->uchHeight;
188 *ppDeleteNode = pLeftLeast;
189 AVLStack.aEntries[iStackEntry] = &pLeftLeast->pLeft;
190 }
191 else
192 {
193 *ppDeleteNode = pDeleteNode->pRight;
194 AVLStack.cEntries--;
195 }
196
197 AVLRebalance(SSToDS(&AVLStack));
198 }
199
200 return pDeleteNode;
201}
202
203
204/**
205 * Gets a node from the tree (does not remove it!)
206 * @returns Pointer to the node holding the given key.
207 * @param ppTree Pointer to the AVL-tree root node pointer.
208 * @param Key Key value of the node which is to be found.
209 * @sketch
210 * @status completely implemented.
211 * @author knut st. osmundsen
212 */
213PAVLNODECORE AVLGet(PPAVLNODECORE ppTree, AVLKEY Key)
214{
215 register PAVLNODECORE pNode = *ppTree;
216
217 while (pNode != NULL && pNode->Key != Key)
218 {
219 if (pNode->Key > Key)
220 pNode = pNode->pLeft;
221 else
222 pNode = pNode->pRight;
223 }
224
225 return pNode;
226}
227
228
229
230/**
231 * Gets a node from the tree and its parent node (if any) (does not remove any nodes!)
232 * @returns Pointer to the node holding the given key.
233 * @param ppTree Pointer to the AVL-tree root node pointer.
234 * @param ppParent Pointer to a variable which will hold the pointer to the partent node on
235 * return. When no node is found, this will hold the last searched node.
236 * @param Key Key value of the node which is to be found.
237 * @sketch
238 * @status completely implemented.
239 * @author knut st. osmundsen
240 */
241PAVLNODECORE AVLGetWithParent(PPAVLNODECORE ppTree, PPAVLNODECORE ppParent, AVLKEY Key)
242{
243 register PAVLNODECORE pNode = *ppTree;
244 register PAVLNODECORE pParent = NULL;
245
246 while (pNode != NULL && pNode->Key != Key)
247 {
248 pParent = pNode;
249 if (pNode->Key > Key)
250 pNode = pNode->pLeft;
251 else
252 pNode = pNode->pRight;
253 }
254
255 *ppParent = pParent;
256 return pNode;
257}
258
259
260
261/**
262 * Gets node from the tree (does not remove it!) and it's adjecent (by key value) nodes.
263 * @returns Pointer to the node holding the given key.
264 * @param ppTree Pointer to the AVL-tree root node pointer.
265 * @param Key Key value of the node which is to be found.
266 * @param ppLeft Pointer to left node pointer.
267 * @param ppRight Pointer to right node pointer.
268 * @sketch Find node with the given key, record search path on the stack.
269 * IF found THEN
270 * BEGIN
271 * Find the right-most node in the left subtree.
272 * Find the left-most node in the right subtree.
273 * Rewind the stack while searching for more adjecent nodes.
274 * END
275 * return node with adjecent nodes.
276 * @status completely implemented.
277 * @author knut st. osmundsen
278 */
279PAVLNODECORE AVLGetWithAdjecentNodes(PPAVLNODECORE ppTree, AVLKEY Key, PPAVLNODECORE ppLeft, PPAVLNODECORE ppRight)
280{
281 AVLSTACK AVLStack;
282 PPAVLNODECORE ppNode = ppTree;
283 PAVLNODECORE pNode;
284
285 AVLStack.cEntries = 0;
286
287 while ((pNode = *ppNode) != NULL && pNode->Key != Key)
288 {
289 assert(AVLStack.cEntries < AVL_MAX_HEIGHT);
290 AVLStack.aEntries[AVLStack.cEntries++] = ppNode;
291 if (pNode->Key > Key)
292 ppNode = &pNode->pLeft;
293 else
294 ppNode = &pNode->pRight;
295 }
296
297 if (pNode != NULL)
298 {
299 PAVLNODECORE pCurNode;
300
301 /* find rigth-most node in left subtree. */
302 pCurNode = pNode->pLeft;
303 if (pCurNode != NULL)
304 while (pCurNode->pRight != NULL)
305 pCurNode = pCurNode->pRight;
306 *ppLeft = pCurNode;
307
308 /* find left-most node in right subtree. */
309 pCurNode = pNode->pRight;
310 if (pCurNode != NULL)
311 while (pCurNode->pLeft != NULL)
312 pCurNode = pCurNode->pLeft;
313 *ppRight = pCurNode;
314
315 /* rewind stack */
316 while (AVLStack.cEntries-- > 0)
317 {
318 pCurNode = *AVLStack.aEntries[AVLStack.cEntries];
319 if (pCurNode->Key < Key && (*ppLeft == NULL || pCurNode->Key > (*ppLeft)->Key))
320 *ppLeft = pCurNode;
321 else if (pCurNode->Key > Key && (*ppRight == NULL || pCurNode->Key < (*ppRight)->Key))
322 *ppRight = pCurNode;
323 }
324 }
325 else
326 *ppLeft = *ppRight = NULL;
327
328 return pNode;
329}
330
331
332/**
333 * Iterates tru all nodes in the given tree.
334 * @returns 0 on success. Return from callback on failiure.
335 * @param ppTree Pointer to the AVL-tree root node pointer.
336 * @param fFromLeft TRUE: Left to right.
337 * FALSE: Right to left.
338 * @param pfnCallBack Pointer to callback function.
339 * @param pvParam Userparameter passed on to the callback function.
340 * @status completely implemented.
341 * @author knut st. osmundsen
342 */
343unsigned AVLDoWithAll(PPAVLNODECORE ppTree, int fFromLeft, PAVLCALLBACK pfnCallBack, void *pvParam)
344{
345 AVLSTACK2 AVLStack;
346 PAVLNODECORE pNode;
347 unsigned rc;
348
349 if (*ppTree == NULL)
350 return 0;
351
352 AVLStack.cEntries = 1;
353 AVLStack.achFlags[0] = 0;
354 AVLStack.aEntries[0] = *ppTree;
355
356 if (fFromLeft)
357 { /* from left */
358 while (AVLStack.cEntries > 0)
359 {
360 pNode = AVLStack.aEntries[AVLStack.cEntries - 1];
361
362 /* left */
363 if (!AVLStack.achFlags[AVLStack.cEntries - 1]++)
364 {
365 if (pNode->pLeft != NULL)
366 {
367 AVLStack.achFlags[AVLStack.cEntries] = 0; /* 0 first, 1 last */
368 AVLStack.aEntries[AVLStack.cEntries++] = pNode->pLeft;
369 continue;
370 }
371 }
372
373 /* center */
374 rc = pfnCallBack(pNode, pvParam);
375 if (rc != 0)
376 return rc;
377
378 /* right */
379 AVLStack.cEntries--;
380 if (pNode->pRight != NULL)
381 {
382 AVLStack.achFlags[AVLStack.cEntries] = 0;
383 AVLStack.aEntries[AVLStack.cEntries++] = pNode->pRight;
384 }
385 } /* while */
386 }
387 else
388 { /* from right */
389 while (AVLStack.cEntries > 0)
390 {
391 pNode = AVLStack.aEntries[AVLStack.cEntries - 1];
392
393
394 /* right */
395 if (!AVLStack.achFlags[AVLStack.cEntries - 1]++)
396 {
397 if (pNode->pRight != NULL)
398 {
399 AVLStack.achFlags[AVLStack.cEntries] = 0; /* 0 first, 1 last */
400 AVLStack.aEntries[AVLStack.cEntries++] = pNode->pRight;
401 continue;
402 }
403 }
404
405 /* center */
406 rc = pfnCallBack(pNode, pvParam);
407 if (rc != 0)
408 return rc;
409
410 /* left */
411 AVLStack.cEntries--;
412 if (pNode->pLeft != NULL)
413 {
414 AVLStack.achFlags[AVLStack.cEntries] = 0;
415 AVLStack.aEntries[AVLStack.cEntries++] = pNode->pLeft;
416 }
417 } /* while */
418 }
419
420 return 0;
421}
422
423
424/**
425 * Starts an enumeration of all nodes in the given AVL tree.
426 * @returns Pointer to the first node in the tree.
427 * @param ppTree Pointer to the AVL-tree root node pointer.
428 * @param pEnumData Pointer to enumeration control data.
429 * @param fFromLeft TRUE: Left to right.
430 * FALSE: Right to left.
431 * @status completely implemented.
432 * @author knut st. osmundsen
433 */
434PAVLNODECORE AVLBeginEnumTree(PPAVLNODECORE ppTree, PAVLENUMDATA pEnumData, int fFromLeft)
435{
436 if (*ppTree != NULL)
437 {
438 pEnumData->fFromLeft = fFromLeft;
439 pEnumData->cEntries = 1;
440 pEnumData->aEntries[0] = *ppTree;
441 pEnumData->achFlags[0] = 0;
442 }
443 else
444 pEnumData->cEntries = 0;
445
446 return AVLGetNextNode(pEnumData);
447}
448
449
450/**
451 * Get the next node in the tree enumeration.
452 * @returns Pointer to the first node in the tree.
453 * @param pEnumData Pointer to enumeration control data.
454 * @status completely implemented.
455 * @author knut st. osmundsen
456 */
457PAVLNODECORE AVLGetNextNode(PAVLENUMDATA pEnumData)
458{
459 PAVLNODECORE pNode;
460
461 if (pEnumData->fFromLeft)
462 { /* from left */
463 while (pEnumData->cEntries > 0)
464 {
465 pNode = pEnumData->aEntries[pEnumData->cEntries - 1];
466
467 /* left */
468 if (pEnumData->achFlags[pEnumData->cEntries - 1] == 0)
469 {
470 pEnumData->achFlags[pEnumData->cEntries - 1]++;
471 if (pNode->pLeft != NULL)
472 {
473 pEnumData->achFlags[pEnumData->cEntries] = 0; /* 0 left, 1 center, 2 right */
474 pEnumData->aEntries[pEnumData->cEntries++] = pNode->pLeft;
475 continue;
476 }
477 }
478
479 /* center */
480 if (pEnumData->achFlags[pEnumData->cEntries - 1] == 1)
481 {
482 pEnumData->achFlags[pEnumData->cEntries - 1]++;
483 return pNode;
484 }
485
486 /* right */
487 pEnumData->cEntries--;
488 if (pNode->pRight != NULL)
489 {
490 pEnumData->achFlags[pEnumData->cEntries] = 0;
491 pEnumData->aEntries[pEnumData->cEntries++] = pNode->pRight;
492 }
493 } /* while */
494 }
495 else
496 { /* from right */
497 while (pEnumData->cEntries > 0)
498 {
499 pNode = pEnumData->aEntries[pEnumData->cEntries - 1];
500
501
502 /* right */
503 if (pEnumData->achFlags[pEnumData->cEntries - 1] == 0)
504 {
505 pEnumData->achFlags[pEnumData->cEntries - 1]++;
506 if (pNode->pRight != NULL)
507 {
508 pEnumData->achFlags[pEnumData->cEntries] = 0; /* 0 right, 1 center, 2 left */
509 pEnumData->aEntries[pEnumData->cEntries++] = pNode->pRight;
510 continue;
511 }
512 }
513
514 /* center */
515 if (pEnumData->achFlags[pEnumData->cEntries - 1] == 1)
516 {
517 pEnumData->achFlags[pEnumData->cEntries - 1]++;
518 return pNode;
519 }
520
521 /* left */
522 pEnumData->cEntries--;
523 if (pNode->pLeft != NULL)
524 {
525 pEnumData->achFlags[pEnumData->cEntries] = 0;
526 pEnumData->aEntries[pEnumData->cEntries++] = pNode->pLeft;
527 }
528 } /* while */
529 }
530
531 return NULL;
532
533}
534
535
536
537
538/**
539 * Finds the best fitting node in the tree for the given Key value.
540 * @returns Pointer to the best fitting node found.
541 * @param ppTree Pointer to Pointer to the tree root node.
542 * @param Key The Key of which is to be found a best fitting match for..
543 * @param fAbove TRUE: Returned node is have the closest key to Key from above.
544 * FALSE: Returned node is have the closest key to Key from below.
545 * @status completely implemented.
546 * @sketch The best fitting node is always located in the searchpath above you.
547 * >= (above): The node where you last turned left.
548 * <= (below): the node where you last turned right.
549 * @author knut st. osmundsen
550 */
551PAVLNODECORE AVLGetBestFit(PPAVLNODECORE ppTree, AVLKEY Key, int fAbove)
552{
553 register PAVLNODECORE pNode = *ppTree;
554 PAVLNODECORE pNodeLast = NULL;
555
556 if (fAbove)
557 { /* pNode->Key >= Key */
558 while (pNode != NULL && pNode->Key != Key)
559 {
560 if (pNode->Key > Key)
561 {
562 pNodeLast = pNode;
563 pNode = pNode->pLeft;
564 }
565 else
566 pNode = pNode->pRight;
567 }
568 }
569 else
570 { /* pNode->Key <= Key */
571 while (pNode != NULL && pNode->Key != Key)
572 {
573 if (pNode->Key < Key)
574 {
575 pNodeLast = pNode;
576 pNode = pNode->pRight;
577 }
578 else
579 pNode = pNode->pLeft;
580 }
581 }
582
583 return pNode == NULL ? pNodeLast /* best fit */ : pNode /* perfect match */;
584}
585
586
587/**
588 * Rewindes a stack of pointer to pointers to nodes, rebalancing the tree.
589 * @param pStack Pointer to stack to rewind.
590 * @sketch LOOP thru all stack entries
591 * BEGIN
592 * Get pointer to pointer to node (and pointer to node) from stack.
593 * IF 2 higher left subtree than in right subtree THEN
594 * BEGIN
595 * IF higher (or equal) left-sub-subtree than right-sub-subtree THEN
596 * * n+2|n+3
597 * / \ / \
598 * n+2 n ==> n+1 n+1|n+2
599 * / \ / \
600 * n+1 n|n+1 n|n+1 n
601 *
602 * Or with keys:
603 *
604 * 4 2
605 * / \ / \
606 * 2 5 ==> 1 4
607 * / \ / \
608 * 1 3 3 5
609 *
610 * ELSE
611 * * n+2
612 * / \ / \
613 * n+2 n n+1 n+1
614 * / \ ==> / \ / \
615 * n n+1 n L R n
616 * / \
617 * L R
618 *
619 * Or with keys:
620 * 6 4
621 * / \ / \
622 * 2 7 ==> 2 6
623 * / \ / \ / \
624 * 1 4 1 3 5 7
625 * / \
626 * 3 5
627 * END
628 * ELSE IF 2 higher in right subtree than in left subtree THEN
629 * BEGIN
630 * Same as above but left <==> right. (invert the picture)
631 * ELSE
632 * IF correct height THEN break
633 * ELSE correct height.
634 * END
635 * @status
636 * @author knut st. osmundsen
637 * @remark
638 */
639_Inline void AVLRebalance(PAVLSTACK pStack)
640{
641 while (pStack->cEntries > 0)
642 {
643 PPAVLNODECORE ppNode = pStack->aEntries[--pStack->cEntries];
644 PAVLNODECORE pNode = *ppNode;
645 PAVLNODECORE pLeftNode = pNode->pLeft;
646 unsigned char uchLeftHeight = AVL_HEIGHTOF(pLeftNode);
647 PAVLNODECORE pRightNode = pNode->pRight;
648 unsigned char uchRightHeight = AVL_HEIGHTOF(pRightNode);
649
650 if (uchRightHeight + 1 < uchLeftHeight)
651 {
652 PAVLNODECORE pLeftLeftNode = pLeftNode->pLeft;
653 PAVLNODECORE pLeftRightNode = pLeftNode->pRight;
654 unsigned char uchLeftRightHeight = AVL_HEIGHTOF(pLeftRightNode);
655
656 if (AVL_HEIGHTOF(pLeftLeftNode) >= uchLeftRightHeight)
657 {
658 pNode->pLeft = pLeftRightNode;
659 pLeftNode->pRight = pNode;
660 pLeftNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchLeftRightHeight)));
661 *ppNode = pLeftNode;
662 }
663 else
664 {
665 pLeftNode->pRight = pLeftRightNode->pLeft;
666 pNode->pLeft = pLeftRightNode->pRight;
667 pLeftRightNode->pLeft = pLeftNode;
668 pLeftRightNode->pRight = pNode;
669 pLeftNode->uchHeight = pNode->uchHeight = uchLeftRightHeight;
670 pLeftRightNode->uchHeight = uchLeftHeight;
671 *ppNode = pLeftRightNode;
672 }
673 }
674 else if (uchLeftHeight + 1 < uchRightHeight)
675 {
676 PAVLNODECORE pRightLeftNode = pRightNode->pLeft;
677 unsigned char uchRightLeftHeight = AVL_HEIGHTOF(pRightLeftNode);
678 PAVLNODECORE pRightRightNode = pRightNode->pRight;
679
680 if (AVL_HEIGHTOF(pRightRightNode) >= uchRightLeftHeight)
681 {
682 pNode->pRight = pRightLeftNode;
683 pRightNode->pLeft = pNode;
684 pRightNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchRightLeftHeight)));
685 *ppNode = pRightNode;
686 }
687 else
688 {
689 pRightNode->pLeft = pRightLeftNode->pRight;
690 pNode->pRight = pRightLeftNode->pLeft;
691 pRightLeftNode->pRight = pRightNode;
692 pRightLeftNode->pLeft = pNode;
693 pRightNode->uchHeight = pNode->uchHeight = uchRightLeftHeight;
694 pRightLeftNode->uchHeight = uchRightHeight;
695 *ppNode = pRightLeftNode;
696 }
697 }
698 else
699 {
700 register unsigned char uchHeight = (unsigned char)(max(uchLeftHeight, uchRightHeight) + 1);
701 if (uchHeight == pNode->uchHeight)
702 break;
703 pNode->uchHeight = uchHeight;
704 }
705 }
706}
707
Note: See TracBrowser for help on using the repository browser.