From b11939ad4328ebce40fa4bfa26b959cd546571ac Mon Sep 17 00:00:00 2001 From: Alex Ionescu Date: Tue, 8 Nov 2005 23:51:46 +0000 Subject: [PATCH] - Finish implementing RtlSplayTree svn path=/trunk/; revision=19077 --- reactos/lib/rtl/splaytree.c | 24 +++++++++++++++++++++++- 1 file changed, 23 insertions(+), 1 deletion(-) diff --git a/reactos/lib/rtl/splaytree.c b/reactos/lib/rtl/splaytree.c index 6f3ea5b22a9..5bb38fca44c 100644 --- a/reactos/lib/rtl/splaytree.c +++ b/reactos/lib/rtl/splaytree.c @@ -69,7 +69,7 @@ RtlRealSuccessor ( } /* -* @unimplemented +* @implemented */ PRTL_SPLAY_LINKS NTAPI @@ -249,7 +249,18 @@ RtlSplay(PRTL_SPLAY_LINKS Links) /* "Finally" case: N doesn't have a grandparent => P is root */ else { + /* P's left-child becomes N's right child */ + RtlLeftChild(P) = RtlRightChild(N); + + /* If it exists, update its parent pointer too */ + if (RtlLeftChild(P)) RtlParent(RtlLeftChild(P)) = P; + /* Now make N the root, no need to worry about references */ + N->Parent = N; + + /* And make P its right child */ + N->RightChild = P; + P->Parent = N; } } /* Case 2 & 4: N is right child of P */ @@ -380,7 +391,18 @@ RtlSplay(PRTL_SPLAY_LINKS Links) /* "Finally" case: N doesn't have a grandparent => P is root */ else { + /* P's right-child becomes N's left child */ + RtlRightChild(P) = RtlLeftChild(N); + + /* If it exists, update its parent pointer too */ + if (RtlRightChild(P)) RtlParent(RtlRightChild(P)) = P; + + /* Now make N the root, no need to worry about references */ + N->Parent = N; + /* And make P its left child */ + N->LeftChild = P; + P->Parent = N; } } } -- 2.17.1