From: Alex Ionescu
Date: Tue, 8 Nov 2005 22:45:45 +0000 (+0000)
Subject: - Add implementation notes for RtlSplayTree
X-Git-Tag: backups/ros-branch-0_2_9@19949~829
X-Git-Url: https://git.reactos.org/?p=reactos.git;a=commitdiff_plain;h=bc90bf5915bb92c69a2e154774fc5017908049bb
- Add implementation notes for RtlSplayTree
svn path=/trunk/; revision=19071
---
diff --git a/reactos/lib/rtl/splaytree.c b/reactos/lib/rtl/splaytree.c
index 83ff4c0136c..b023f4c600b 100644
--- a/reactos/lib/rtl/splaytree.c
+++ b/reactos/lib/rtl/splaytree.c
@@ -73,10 +73,42 @@ RtlRealSuccessor (
*/
PRTL_SPLAY_LINKS
NTAPI
-RtlSplay (
- PRTL_SPLAY_LINKS Links
- )
+RtlSplay(PRTL_SPLAY_LINKS Links)
{
+ /*
+ * Implementation Notes (http://en.wikipedia.org/wiki/Splay_tree):
+ *
+ * To do a splay, we carry out a sequence of rotations,
+ * each of which moves the target node N closer to the root.
+ *
+ * Each particular step depends on only two factors:
+ * - Whether N is the left or right child of its parent node, P,
+ * - Whether P is the left or right child of its parent, G (for grandparent node).
+ *
+ * Thus, there are four cases:
+ * - Case 1: N is the left child of P and P is the left child of G.
+ * In this case we perform a double right rotation, so that
+ * P becomes N's right child, and G becomes P's right child.
+ *
+ * - Case 2: N is the right child of P and P is the right child of G.
+ * In this case we perform a double left rotation, so that
+ * P becomes N's left child, and G becomes P's left child.
+ *
+ * - Case 3: N is the left child of P and P is the right child of G.
+ * In this case we perform a rotation so that
+ * G becomes N's left child, and P becomes N's right child.
+ *
+ * - Case 4: N is the right child of P and P is the left child of G.
+ * In this case we perform a rotation so that
+ * P becomes N's left child, and G becomes N's right child.
+ *
+ * Finally, if N doesn't have a grandparent node, we simply perform a
+ * left or right rotation to move it to the root.
+ *
+ * By performing a splay on the node of interest after every operation,
+ * 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;
}