[ros-diffs] [ion] 19071: - Add implementation notes for RtlSplayTree

- Add implementation notes for RtlSplayTree
Modified: trunk/reactos/lib/rtl/splaytree.c
  _____  

Modified: trunk/reactos/lib/rtl/splaytree.c
--- trunk/reactos/lib/rtl/splaytree.c	2005-11-08 22:25:29 UTC (rev
19070)
+++ trunk/reactos/lib/rtl/splaytree.c	2005-11-08 22:45:45 UTC (rev
19071)
@@ -73,10 +73,42 @@

 */
 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;
 }