1 /*
2 * COPYRIGHT: See COPYING in the top level directory
3 * PROJECT: ReactOS system libraries
4 * PURPOSE: Splay-Tree implementation
5 * FILE: lib/rtl/splaytree.c
6 * PROGRAMMER: Alex Ionescu (alex@relsoft.net)
7 */
8
9 /* INCLUDES *****************************************************************/
10
11 #include <rtl.h>
12
13 #define NDEBUG
14 #include <debug.h>
15
16 //#define VERIFY_SWAP_SPLAY_LINKS
17
18 /* FUNCTIONS ***************************************************************/
19
20 static
21 VOID
FixupChildLinks(PRTL_SPLAY_LINKS Links,BOOLEAN Root,BOOLEAN LeftChild)22 FixupChildLinks(PRTL_SPLAY_LINKS Links, BOOLEAN Root, BOOLEAN LeftChild)
23 {
24 if (RtlLeftChild(Links))
25 {
26 RtlInsertAsLeftChild(Links, RtlLeftChild(Links));
27 }
28
29 if (RtlRightChild(Links))
30 {
31 RtlInsertAsRightChild(Links, RtlRightChild(Links));
32 }
33
34 if (!Root)
35 {
36 if (LeftChild)
37 {
38 RtlInsertAsLeftChild(RtlParent(Links), Links);
39 }
40 else
41 {
42 RtlInsertAsRightChild(RtlParent(Links), Links);
43 }
44 }
45 }
46
47 /*
48
49 Given the tree:
50 D
51 B F
52 A C E G
53
54 Swap(Q,S):
55
56 Q S Q.P Q.L Q.R S.P S.L S.R
57 A C S.P S.L S.R Q.P Q.L Q.R
58 B A S S.L S.R Q.P Q Q.R
59 B C S S.L S.R Q.P Q.L Q
60 D A S.P S.L S.R S Q.L Q.R
61 D B S S.L S.R S Q Q.R
62 D F S S.L S.R S Q.L Q
63
64 When Q is the immediate parent of S,
65 Set Q's parent to S, and the proper child ptr of S to Q
66 When Q is the root,
67 Set S's parent to S
68
69 */
70
71 static
72 VOID
SwapSplayLinks(PRTL_SPLAY_LINKS LinkA,PRTL_SPLAY_LINKS LinkB)73 SwapSplayLinks(PRTL_SPLAY_LINKS LinkA,
74 PRTL_SPLAY_LINKS LinkB)
75 {
76 if (RtlParent(LinkA) == LinkB || RtlIsRoot(LinkB))
77 {
78 PRTL_SPLAY_LINKS Tmp = LinkA;
79 LinkA = LinkB;
80 LinkB = Tmp;
81 }
82
83 {
84 RTL_SPLAY_LINKS Ta = *LinkA, Tb = *LinkB;
85 BOOLEAN RootA = RtlIsRoot(LinkA),
86 LeftA = RtlIsLeftChild(LinkA),
87 LeftB = RtlIsLeftChild(LinkB);
88
89 *LinkB = Ta; *LinkA = Tb;
90
91 // A was parent of B is a special case: A->Parent is now B
92 if (RtlParent(&Tb) == LinkA)
93 {
94 if (!RootA)
95 {
96 if (LeftA)
97 {
98 RtlInsertAsLeftChild(RtlParent(&Ta), LinkB);
99 }
100 else
101 {
102 RtlInsertAsRightChild(RtlParent(&Ta), LinkB);
103 }
104 }
105
106 if (LeftB)
107 {
108 RtlInsertAsLeftChild(LinkB, LinkA);
109 }
110 else
111 {
112 RtlInsertAsRightChild(LinkB, LinkA);
113 }
114 }
115
116 FixupChildLinks(LinkA, FALSE, LeftB);
117 FixupChildLinks(LinkB, RootA, LeftA);
118
119 // A was root is a special case: B->Parent is now B
120 if (RootA)
121 RtlParent(LinkB) = LinkB;
122
123 #ifdef VERIFY_SWAP_SPLAY_LINKS
124 // Verify the distinct cases of node swap
125 if (RootA)
126 {
127 if (RtlParent(&Tb) == LinkA)
128 {
129 // LinkA = D, LinkB = B
130 // D B S S.L S.R S Q Q.R
131 ASSERT(RtlParent(LinkA) == LinkB);
132 ASSERT(RtlLeftChild(LinkA) == RtlLeftChild(&Tb));
133 ASSERT(RtlRightChild(LinkA) == RtlRightChild(&Tb));
134 ASSERT(RtlParent(LinkB) == LinkB);
135 ASSERT(RtlLeftChild(LinkB) == (LeftB ? LinkA : RtlLeftChild(&Ta)));
136 ASSERT(RtlRightChild(LinkB) == (LeftB ? RtlRightChild(&Ta) : LinkA));
137 }
138 else
139 {
140 // LinkA = D, LinkB = A
141 // D A S.P S.L S.R S Q.L Q.R
142 ASSERT(RtlParent(LinkA) == RtlParent(&Tb));
143 ASSERT(RtlLeftChild(LinkA) == RtlLeftChild(&Tb));
144 ASSERT(RtlRightChild(LinkA) == RtlRightChild(&Tb));
145 ASSERT(RtlParent(LinkB) == LinkB);
146 ASSERT(RtlLeftChild(LinkB) == RtlLeftChild(&Ta));
147 ASSERT(RtlRightChild(LinkB) == RtlRightChild(&Ta));
148 }
149 }
150 else
151 {
152 if (RtlParent(&Tb) == LinkA)
153 {
154 // LinkA = B, LinkB = A
155 // B A S S.L S.R Q.P Q Q.R
156 ASSERT(RtlParent(LinkA) == LinkB);
157 ASSERT(RtlLeftChild(LinkA) == RtlLeftChild(&Tb));
158 ASSERT(RtlRightChild(LinkA) == RtlRightChild(&Tb));
159 ASSERT(RtlParent(LinkB) == RtlParent(&Ta));
160 ASSERT(RtlLeftChild(LinkB) == (LeftB ? LinkA : RtlLeftChild(&Ta)));
161 ASSERT(RtlRightChild(LinkB) == (LeftB ? RtlRightChild(&Ta) : LinkA));
162 }
163 else
164 {
165 // LinkA = A, LinkB = C
166 // A C S.P S.L S.R Q.P Q.L Q.R
167 ASSERT(!memcmp(LinkA, &Tb, sizeof(Tb)));
168 ASSERT(!memcmp(LinkB, &Ta, sizeof(Ta)));
169 }
170 }
171 #endif
172 }
173 }
174
175 /*
176 * @implemented
177 */
178 PRTL_SPLAY_LINKS
179 NTAPI
RtlDelete(PRTL_SPLAY_LINKS Links)180 RtlDelete(PRTL_SPLAY_LINKS Links)
181 {
182 PRTL_SPLAY_LINKS N, P, C, SP;
183 N = Links;
184
185 /* Check if we have two children */
186 if (RtlLeftChild(N) && RtlRightChild(N))
187 {
188 /* Get the predecessor */
189 SP = RtlSubtreePredecessor(N);
190
191 /* Swap it with N, this will guarantee that N will only have a child */
192 SwapSplayLinks(SP, N);
193 }
194
195 /* Check if we have no children */
196 if (!RtlLeftChild(N) && !RtlRightChild(N))
197 {
198 /* If we are also the root, then the tree is gone */
199 if (RtlIsRoot(N)) return NULL;
200
201 /* Get our parent */
202 P = RtlParent(N);
203
204 /* Find out who is referencing us and delete the reference */
205 if (RtlIsLeftChild(N))
206 {
207 /* N was a left child, so erase its parent's left child link */
208 RtlLeftChild(P) = NULL;
209 }
210 else
211 {
212 /* N was a right child, so erase its parent's right child link */
213 RtlRightChild(P) = NULL;
214 }
215
216 /* And finally splay the parent */
217 return RtlSplay(P);
218 }
219
220 /* If we got here, we have a child (not two: we swapped above!) */
221 if (RtlLeftChild(N))
222 {
223 /* We have a left child, so get it */
224 C = RtlLeftChild(N);
225 }
226 else
227 {
228 /* We have a right child, get it instead */
229 C = RtlRightChild(N);
230 }
231
232 /* Check if we are the root entry */
233 if (RtlIsRoot(N))
234 {
235 /* Our child is now root, return it */
236 RtlParent(C) = C;
237 return C;
238 }
239
240 /* Get our parent */
241 P = RtlParent(N);
242
243 /* Find out who is referencing us and link to our child instead */
244 if (RtlIsLeftChild(N))
245 {
246 /* N was a left child, so set its parent's left child as our child */
247 RtlLeftChild(P) = C;
248 }
249 else
250 {
251 /* N was a right child, so set its parent's right child as our child */
252 RtlRightChild(P) = C;
253 }
254
255 /* Finally, inherit our parent and splay the parent */
256 RtlParent(C) = P;
257 return RtlSplay(P);
258 }
259
260 /*
261 * @implemented
262 */
263 VOID
264 NTAPI
RtlDeleteNoSplay(PRTL_SPLAY_LINKS Links,PRTL_SPLAY_LINKS * Root)265 RtlDeleteNoSplay(PRTL_SPLAY_LINKS Links,
266 PRTL_SPLAY_LINKS *Root)
267 {
268 PRTL_SPLAY_LINKS N, P, C, SP;
269 N = Links;
270
271 /* Check if we have two children */
272 if (RtlLeftChild(N) && RtlRightChild(N))
273 {
274 /* Get the predecessor */
275 SP = RtlSubtreePredecessor(N);
276
277 /* If we are the root, the new root will be our predecessor after swapping */
278 if (RtlIsRoot(N)) *Root = SP;
279
280 /* Swap the predecessor with N, this will guarantee that N will only have a child */
281 SwapSplayLinks(SP, N);
282 }
283
284 /* Check if we have no children */
285 if (!RtlLeftChild(N) && !RtlRightChild(N))
286 {
287 /* If we are also the root, then the tree is gone */
288 if (RtlIsRoot(N))
289 {
290 *Root = NULL;
291 return;
292 }
293
294 /* Get our parent */
295 P = RtlParent(N);
296
297 /* Find out who is referencing us and delete the reference */
298 if (RtlIsLeftChild(N))
299 {
300 /* N was a left child, so erase its parent's left child link */
301 RtlLeftChild(P) = NULL;
302 }
303 else
304 {
305 /* N was a right child, so erase its parent's right child link */
306 RtlRightChild(P) = NULL;
307 }
308
309 /* We are done */
310 return;
311 }
312
313 /* If we got here, we have a child (not two: we swapped above!) */
314 if (RtlLeftChild(N))
315 {
316 /* We have a left child, so get it */
317 C = RtlLeftChild(N);
318 }
319 else
320 {
321 /* We have a right child, get it instead */
322 C = RtlRightChild(N);
323 }
324
325 /* Check if we are the root entry */
326 if (RtlIsRoot(N))
327 {
328 /* Our child is now root, return it */
329 RtlParent(C) = C;
330 *Root = C;
331 return;
332 }
333
334 /* Get our parent */
335 P = RtlParent(N);
336
337 /* Find out who is referencing us and link to our child instead */
338 if (RtlIsLeftChild(N))
339 {
340 /* N was a left child, so set its parent's left child as our child */
341 RtlLeftChild(P) = C;
342 }
343 else
344 {
345 /* N was a right child, so set its parent's right child as our child */
346 RtlRightChild(P) = C;
347 }
348
349 /* Finally, inherit our parent and we are done */
350 RtlParent(C) = P;
351 return;
352 }
353
354 /*
355 * @implemented
356 */
357 PRTL_SPLAY_LINKS
358 NTAPI
RtlRealPredecessor(PRTL_SPLAY_LINKS Links)359 RtlRealPredecessor(PRTL_SPLAY_LINKS Links)
360 {
361 PRTL_SPLAY_LINKS Child;
362
363 /* Get the left child */
364 Child = RtlLeftChild(Links);
365 if (Child)
366 {
367 /* Get right-most child */
368 while (RtlRightChild(Child)) Child = RtlRightChild(Child);
369 return Child;
370 }
371
372 /* We don't have a left child, keep looping until we find our parent */
373 Child = Links;
374 while (RtlIsLeftChild(Child)) Child = RtlParent(Child);
375
376 /* The parent should be a right child, return the real predecessor */
377 if (RtlIsRightChild(Child)) return RtlParent(Child);
378
379 /* The parent isn't a right child, so no real precessor for us */
380 return NULL;
381 }
382
383 /*
384 * @implemented
385 */
386 PRTL_SPLAY_LINKS
387 NTAPI
RtlRealSuccessor(PRTL_SPLAY_LINKS Links)388 RtlRealSuccessor(PRTL_SPLAY_LINKS Links)
389 {
390 PRTL_SPLAY_LINKS Child;
391
392 /* Get the right child */
393 Child = RtlRightChild(Links);
394 if (Child)
395 {
396 /* Get left-most child */
397 while (RtlLeftChild(Child)) Child = RtlLeftChild(Child);
398 return Child;
399 }
400
401 /* We don't have a right child, keep looping until we find our parent */
402 Child = Links;
403 while (RtlIsRightChild(Child)) Child = RtlParent(Child);
404
405 /* The parent should be a left child, return the real successor */
406 if (RtlIsLeftChild(Child)) return RtlParent(Child);
407
408 /* The parent isn't a right child, so no real successor for us */
409 return NULL;
410 }
411
412 /*
413 * @implemented
414 */
415 PRTL_SPLAY_LINKS
416 NTAPI
RtlSplay(PRTL_SPLAY_LINKS Links)417 RtlSplay(PRTL_SPLAY_LINKS Links)
418 {
419 /*
420 * Implementation Notes (http://en.wikipedia.org/wiki/Splay_tree):
421 *
422 * To do a splay, we carry out a sequence of rotations,
423 * each of which moves the target node N closer to the root.
424 *
425 * Each particular step depends on only two factors:
426 * - Whether N is the left or right child of its parent node, P,
427 * - Whether P is the left or right child of its parent, G (for grandparent node).
428 *
429 * Thus, there are four cases:
430 * - Case 1: N is the left child of P and P is the left child of G.
431 * In this case we perform a double right rotation, so that
432 * P becomes N's right child, and G becomes P's right child.
433 *
434 * - Case 2: N is the right child of P and P is the right child of G.
435 * In this case we perform a double left rotation, so that
436 * P becomes N's left child, and G becomes P's left child.
437 *
438 * - Case 3: N is the left child of P and P is the right child of G.
439 * In this case we perform a rotation so that
440 * G becomes N's left child, and P becomes N's right child.
441 *
442 * - Case 4: N is the right child of P and P is the left child of G.
443 * In this case we perform a rotation so that
444 * P becomes N's left child, and G becomes N's right child.
445 *
446 * Finally, if N doesn't have a grandparent node, we simply perform a
447 * left or right rotation to move it to the root.
448 *
449 * By performing a splay on the node of interest after every operation,
450 * we keep recently accessed nodes near the root and keep the tree
451 * roughly balanced, so that we achieve the desired amortized time bounds.
452 */
453 PRTL_SPLAY_LINKS N, P, G;
454
455 /* N is the item we'll be playing with */
456 N = Links;
457
458 /* Let the algorithm run until N becomes the root entry */
459 while (!RtlIsRoot(N))
460 {
461 /* Now get the parent and grand-parent */
462 P = RtlParent(N);
463 G = RtlParent(P);
464
465 /* Case 1 & 3: N is left child of P */
466 if (RtlIsLeftChild(N))
467 {
468 /* Case 1: P is the left child of G */
469 if (RtlIsLeftChild(P))
470 {
471 /*
472 * N's right-child becomes P's left child and
473 * P's right-child becomes G's left child.
474 */
475 RtlLeftChild(P) = RtlRightChild(N);
476 RtlLeftChild(G) = RtlRightChild(P);
477
478 /*
479 * If they exist, update their parent pointers too,
480 * since they've changed trees.
481 */
482 if (RtlLeftChild(P)) RtlParent(RtlLeftChild(P)) = P;
483 if (RtlLeftChild(G)) RtlParent(RtlLeftChild(G)) = G;
484
485 /*
486 * Now we'll shove N all the way to the top.
487 * Check if G is the root first.
488 */
489 if (RtlIsRoot(G))
490 {
491 /* G doesn't have a parent, so N will become the root! */
492 RtlParent(N) = N;
493 }
494 else
495 {
496 /* G has a parent, so inherit it since we take G's place */
497 RtlParent(N) = RtlParent(G);
498
499 /*
500 * Now find out who was referencing G and have it reference
501 * N instead, since we're taking G's place.
502 */
503 if (RtlIsLeftChild(G))
504 {
505 /*
506 * G was a left child, so change its parent's left
507 * child link to point to N now.
508 */
509 RtlLeftChild(RtlParent(G)) = N;
510 }
511 else
512 {
513 /*
514 * G was a right child, so change its parent's right
515 * child link to point to N now.
516 */
517 RtlRightChild(RtlParent(G)) = N;
518 }
519 }
520
521 /* Now N is on top, so P has become its child. */
522 RtlRightChild(N) = P;
523 RtlParent(P) = N;
524
525 /* N is on top, P is its child, so G is grandchild. */
526 RtlRightChild(P) = G;
527 RtlParent(G) = P;
528 }
529 /* Case 3: P is the right child of G */
530 else if (RtlIsRightChild(P))
531 {
532 /*
533 * N's left-child becomes G's right child and
534 * N's right-child becomes P's left child.
535 */
536 RtlRightChild(G) = RtlLeftChild(N);
537 RtlLeftChild(P) = RtlRightChild(N);
538
539 /*
540 * If they exist, update their parent pointers too,
541 * since they've changed trees.
542 */
543 if (RtlRightChild(G)) RtlParent(RtlRightChild(G)) = G;
544 if (RtlLeftChild(P)) RtlParent(RtlLeftChild(P)) = P;
545
546 /*
547 * Now we'll shove N all the way to the top.
548 * Check if G is the root first.
549 */
550 if (RtlIsRoot(G))
551 {
552 /* G doesn't have a parent, so N will become the root! */
553 RtlParent(N) = N;
554 }
555 else
556 {
557 /* G has a parent, so inherit it since we take G's place */
558 RtlParent(N) = RtlParent(G);
559
560 /*
561 * Now find out who was referencing G and have it reference
562 * N instead, since we're taking G's place.
563 */
564 if (RtlIsLeftChild(G))
565 {
566 /*
567 * G was a left child, so change its parent's left
568 * child link to point to N now.
569 */
570 RtlLeftChild(RtlParent(G)) = N;
571 }
572 else
573 {
574 /*
575 * G was a right child, so change its parent's right
576 * child link to point to N now.
577 */
578 RtlRightChild(RtlParent(G)) = N;
579 }
580 }
581
582 /* Now N is on top, so G has become its left child. */
583 RtlLeftChild(N) = G;
584 RtlParent(G) = N;
585
586 /* N is on top, G is its left child, so P is right child. */
587 RtlRightChild(N) = P;
588 RtlParent(P) = N;
589 }
590 /* "Finally" case: N doesn't have a grandparent => P is root */
591 else
592 {
593 /* P's left-child becomes N's right child */
594 RtlLeftChild(P) = RtlRightChild(N);
595
596 /* If it exists, update its parent pointer too */
597 if (RtlLeftChild(P)) RtlParent(RtlLeftChild(P)) = P;
598
599 /* Now make N the root, no need to worry about references */
600 N->Parent = N;
601
602 /* And make P its right child */
603 N->RightChild = P;
604 P->Parent = N;
605 }
606 }
607 /* Case 2 & 4: N is right child of P */
608 else
609 {
610 /* Case 2: P is the right child of G */
611 if (RtlIsRightChild(P))
612 {
613 /*
614 * P's left-child becomes G's right child and
615 * N's left-child becomes P's right child.
616 */
617 RtlRightChild(G) = RtlLeftChild(P);
618 RtlRightChild(P) = RtlLeftChild(N);
619
620 /*
621 * If they exist, update their parent pointers too,
622 * since they've changed trees.
623 */
624 if (RtlRightChild(G)) RtlParent(RtlRightChild(G)) = G;
625 if (RtlRightChild(P)) RtlParent(RtlRightChild(P)) = P;
626
627 /*
628 * Now we'll shove N all the way to the top.
629 * Check if G is the root first.
630 */
631 if (RtlIsRoot(G))
632 {
633 /* G doesn't have a parent, so N will become the root! */
634 RtlParent(N) = N;
635 }
636 else
637 {
638 /* G has a parent, so inherit it since we take G's place */
639 RtlParent(N) = RtlParent(G);
640
641 /*
642 * Now find out who was referencing G and have it reference
643 * N instead, since we're taking G's place.
644 */
645 if (RtlIsLeftChild(G))
646 {
647 /*
648 * G was a left child, so change its parent's left
649 * child link to point to N now.
650 */
651 RtlLeftChild(RtlParent(G)) = N;
652 }
653 else
654 {
655 /*
656 * G was a right child, so change its parent's right
657 * child link to point to N now.
658 */
659 RtlRightChild(RtlParent(G)) = N;
660 }
661 }
662
663 /* Now N is on top, so P has become its child. */
664 RtlLeftChild(N) = P;
665 RtlParent(P) = N;
666
667 /* N is on top, P is its child, so G is grandchild. */
668 RtlLeftChild(P) = G;
669 RtlParent(G) = P;
670 }
671 /* Case 4: P is the left child of G */
672 else if (RtlIsLeftChild(P))
673 {
674 /*
675 * N's left-child becomes G's right child and
676 * N's right-child becomes P's left child.
677 */
678 RtlRightChild(P) = RtlLeftChild(N);
679 RtlLeftChild(G) = RtlRightChild(N);
680
681 /*
682 * If they exist, update their parent pointers too,
683 * since they've changed trees.
684 */
685 if (RtlRightChild(P)) RtlParent(RtlRightChild(P)) = P;
686 if (RtlLeftChild(G)) RtlParent(RtlLeftChild(G)) = G;
687
688 /*
689 * Now we'll shove N all the way to the top.
690 * Check if G is the root first.
691 */
692 if (RtlIsRoot(G))
693 {
694 /* G doesn't have a parent, so N will become the root! */
695 RtlParent(N) = N;
696 }
697 else
698 {
699 /* G has a parent, so inherit it since we take G's place */
700 RtlParent(N) = RtlParent(G);
701
702 /*
703 * Now find out who was referencing G and have it reference
704 * N instead, since we're taking G's place.
705 */
706 if (RtlIsLeftChild(G))
707 {
708 /*
709 * G was a left child, so change its parent's left
710 * child link to point to N now.
711 */
712 RtlLeftChild(RtlParent(G)) = N;
713 }
714 else
715 {
716 /*
717 * G was a right child, so change its parent's right
718 * child link to point to N now.
719 */
720 RtlRightChild(RtlParent(G)) = N;
721 }
722 }
723
724 /* Now N is on top, so P has become its left child. */
725 RtlLeftChild(N) = P;
726 RtlParent(G) = N;
727
728 /* N is on top, P is its left child, so G is right child. */
729 RtlRightChild(N) = G;
730 RtlParent(P) = N;
731 }
732 /* "Finally" case: N doesn't have a grandparent => P is root */
733 else
734 {
735 /* P's right-child becomes N's left child */
736 RtlRightChild(P) = RtlLeftChild(N);
737
738 /* If it exists, update its parent pointer too */
739 if (RtlRightChild(P)) RtlParent(RtlRightChild(P)) = P;
740
741 /* Now make N the root, no need to worry about references */
742 N->Parent = N;
743
744 /* And make P its left child */
745 N->LeftChild = P;
746 P->Parent = N;
747 }
748 }
749 }
750
751 /* Return the root entry */
752 ASSERT(RtlIsRoot(N));
753 return N;
754 }
755
756 /*
757 * @implemented
758 */
759 PRTL_SPLAY_LINKS
760 NTAPI
RtlSubtreePredecessor(IN PRTL_SPLAY_LINKS Links)761 RtlSubtreePredecessor(IN PRTL_SPLAY_LINKS Links)
762 {
763 PRTL_SPLAY_LINKS Child;
764
765 /* Get the left child */
766 Child = RtlLeftChild(Links);
767 if (!Child) return NULL;
768
769 /* Get right-most child */
770 while (RtlRightChild(Child)) Child = RtlRightChild(Child);
771
772 /* Return it */
773 return Child;
774 }
775
776 /*
777 * @implemented
778 */
779 PRTL_SPLAY_LINKS
780 NTAPI
RtlSubtreeSuccessor(IN PRTL_SPLAY_LINKS Links)781 RtlSubtreeSuccessor(IN PRTL_SPLAY_LINKS Links)
782 {
783 PRTL_SPLAY_LINKS Child;
784
785 /* Get the right child */
786 Child = RtlRightChild(Links);
787 if (!Child) return NULL;
788
789 /* Get left-most child */
790 while (RtlLeftChild(Child)) Child = RtlLeftChild(Child);
791
792 /* Return it */
793 return Child;
794 }
795
796 /* EOF */
797