[ros-diffs] [ion] 19076: - Implement cases 2 & 4 of RtlSplayTree

- Implement cases 2 & 4 of RtlSplayTree
Modified: trunk/reactos/lib/rtl/splaytree.c
  _____  

Modified: trunk/reactos/lib/rtl/splaytree.c
--- trunk/reactos/lib/rtl/splaytree.c	2005-11-08 23:42:40 UTC (rev
19075)
+++ trunk/reactos/lib/rtl/splaytree.c	2005-11-08 23:47:25 UTC (rev
19076)
@@ -258,12 +258,124 @@

             /* Case 2: P is the right child of G */
             if (RtlIsRightChild(P))
             {
+                /*
+                 * P's left-child becomes G's right child and
+                 * N's left-child becomes P's right child.
+                 */
+                RtlRightChild(G) = RtlLeftChild(P);
+                RtlRightChild(P) = RtlLeftChild(N);
 
+                /*
+                 * If they exist, update their parent pointers too, 
+                 * since they've changed trees.
+                 */
+                if (RtlRightChild(G)) RtlParent(RtlRightChild(G)) = G;
+                if (RtlRightChild(P)) RtlParent(RtlRightChild(P)) = P;
+
+                /*
+                 * Now we'll shove N all the way to the top.
+                 * Check if G is the root first.
+                 */
+                if (RtlIsRoot(G))
+                {
+                    /* G doesn't have a parent, so N will become the
root! */
+                    RtlParent(N) = N;
+                }
+                else
+                {
+                    /* G has a parent, so inherit it since we take G's
place */
+                    RtlParent(N) = RtlParent(G);
+
+                    /*
+                     * Now find out who was referencing G and have it
reference
+                     * N instead, since we're taking G's place.
+                     */
+                    if (RtlIsLeftChild(G))
+                    {
+                        /*
+                         * G was a left child, so change its parent's
left
+                         * child link to point to N now.
+                         */
+                        RtlLeftChild(RtlParent(G)) = N;
+                    }
+                    else
+                    {
+                        /*
+                         * G was a right child, so change its parent's
right
+                         * child link to point to N now.
+                         */
+                        RtlLeftChild(RtlParent(G)) = N;
+                    }
+                }
+
+                /* Now N is on top, so P has become its child. */
+                RtlLeftChild(N) = P;
+                RtlParent(P) = N;
+
+                /* N is on top, P is its child, so G is grandchild. */
+                RtlLeftChild(P) = G;
+                RtlParent(G) = P;
             }
             /* Case 4: P is the left child of G */
             else if (RtlIsLeftChild(P))
             {
+                /*
+                 * N's left-child becomes G's right child and
+                 * N's right-child becomes P's left child.
+                 */
+                RtlRightChild(P) = RtlLeftChild(N);
+                RtlLeftChild(G) = RtlRightChild(N);
 
+                /*
+                 * If they exist, update their parent pointers too, 
+                 * since they've changed trees.
+                 */
+                if (RtlRightChild(P)) RtlParent(RtlRightChild(P)) = P;
+                if (RtlLeftChild(G)) RtlParent(RtlLeftChild(G)) = G;
+
+                /*
+                 * Now we'll shove N all the way to the top.
+                 * Check if G is the root first.
+                 */
+                if (RtlIsRoot(G))
+                {
+                    /* G doesn't have a parent, so N will become the
root! */
+                    RtlParent(N) = N;
+                }
+                else
+                {
+                    /* G has a parent, so inherit it since we take G's
place */
+                    RtlParent(N) = RtlParent(G);
+
+                    /*
+                     * Now find out who was referencing G and have it
reference
+                     * N instead, since we're taking G's place.
+                     */
+                    if (RtlIsLeftChild(G))
+                    {
+                        /*
+                         * G was a left child, so change its parent's
left
+                         * child link to point to N now.
+                         */
+                        RtlLeftChild(RtlParent(G)) = N;
+                    }
+                    else
+                    {
+                        /*
+                         * G was a right child, so change its parent's
right
+                         * child link to point to N now.
+                         */
+                        RtlLeftChild(RtlParent(G)) = N;
+                    }
+                }
+
+                /* Now N is on top, so P has become its left child. */
+                RtlLeftChild(N) = P;
+                RtlParent(G) = N;
+
+                /* N is on top, P is its left child, so G is right
child. */
+                RtlRightChild(N) = G;
+                RtlParent(P) = N;
             }
             /* "Finally" case: N doesn't have a grandparent => P is
root */
             else