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

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

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