source: trunk/tools/fastdep/avl.c@ 4653

Last change on this file since 4653 was 4653, checked in by bird, 25 years ago

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