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

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

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