- Implement RtlSplay skeleton cases.
authorAlex Ionescu <aionescu@gmail.com>
Tue, 8 Nov 2005 22:54:39 +0000 (22:54 +0000)
committerAlex Ionescu <aionescu@gmail.com>
Tue, 8 Nov 2005 22:54:39 +0000 (22:54 +0000)
svn path=/trunk/; revision=19072

reactos/include/ndk/rtlfuncs.h
reactos/lib/rtl/splaytree.c

index 5ec42c4..ccc8d31 100644 (file)
@@ -24,6 +24,9 @@
 #define RtlIsLeftChild(Links) \
     (RtlLeftChild(RtlParent(Links)) == (PRTL_SPLAY_LINKS)(Links))
 
+#define RtlIsRightChild(Links) \
+    (RtlRightChild(RtlParent(Links)) == (PRTL_SPLAY_LINKS)(Links))
+
 #define RtlRightChild(Links) \
     ((PRTL_SPLAY_LINKS)(Links))->RightChild
 
index b023f4c..ec3a11a 100644 (file)
@@ -109,8 +109,60 @@ RtlSplay(PRTL_SPLAY_LINKS Links)
      * we keep recently accessed nodes near the root and keep the tree
      * roughly balanced, so that we achieve the desired amortized time bounds.
      */
-       UNIMPLEMENTED;
-       return 0;
+    PRTL_SPLAY_LINKS N, P, G;
+
+    /* N is the item we'll be playing with */
+    N = Links;
+
+    /* Let the algorithm run until N becomes the root entry */
+    while (!RtlIsRoot(N))
+    {
+        /* Now get the parent and grand-parent */
+        P = RtlParent(N);
+        G = RtlParent(P);
+
+        /* Case 1 & 3: N is left child of P */
+        if (RtlIsLeftChild(N))
+        {
+            /* Case 1: P is the left child of G */
+            if (RtlIsLeftChild(P))
+            {
+
+            }
+            /* Case 3: P is the right child of G */
+            else if (RtlIsRightChild(P))
+            {
+
+            }
+            /* "Finally" case: N doesn't have a grandparent => P is root */
+            else
+            {
+
+            }
+        }
+        /* Case 2 & 4: N is right child of P */
+        else
+        {
+            /* Case 2: P is the left child of G */
+            if (RtlIsLeftChild(P))
+            {
+
+            }
+            /* Case 4: P is the right child of G */
+            else if (RtlIsRightChild(P))
+            {
+
+            }
+            /* "Finally" case: N doesn't have a grandparent => P is root */
+            else
+            {
+
+            }
+        }
+    }
+
+       /* Return the root entry */
+       return N;
 }