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

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

Speed optimizations. Using an AVL tree to cache the files which we have found,
we'll check this tree before we issue a DosQueryPathInfo. The function
pathlistFindFile is still the slowest function...
File size: 23.6 KB
Line 
1/* $Id: avl.c,v 1.1 2000-03-16 21:10:10 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.