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

Last change on this file was 21916, checked in by dmik, 14 years ago

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