- Add implementation notes for RtlSplayTree

[reactos.git] / reactos / lib / rtl / splaytree.c

diff --git a/reactos/lib/rtl/splaytree.c b/reactos/lib/rtl/splaytree.c
index a466d6c..b023f4c 100644 (file)
--- a/reactos/lib/rtl/splaytree.c
+++ b/reactos/lib/rtl/splaytree.c
@@ -1,42 +1,25 @@
 /*
- *  ReactOS kernel
- *  Copyright (C) 2003 ReactOS Team
- *
- *  This program is free software; you can redistribute it and/or modify
- *  it under the terms of the GNU General Public License as published by
- *  the Free Software Foundation; either version 2 of the License, or
- *  (at your option) any later version.
- *
- *  This program is distributed in the hope that it will be useful,
- *  but WITHOUT ANY WARRANTY; without even the implied warranty of
- *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- *  GNU General Public License for more details.
- *
- *  You should have received a copy of the GNU General Public License
- *  along with this program; if not, write to the Free Software
- *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
- */
-/* $Id$
- *
  * COPYRIGHT:         See COPYING in the top level directory
  * PROJECT:           ReactOS system libraries
  * PURPOSE:           Splay-Tree implementation
  * FILE:              lib/rtl/splaytree.c
+ * PROGRAMMER:        
  */
 
-#include <ddk/ntddk.h>
+/* INCLUDES *****************************************************************/
+
+#include <rtl.h>
 
 #define NDEBUG
 #include <debug.h>
 
-
-/* FUNCTIONS *****************************************************************/
+/* FUNCTIONS ***************************************************************/
 
 /*
 * @unimplemented
 */
 PRTL_SPLAY_LINKS
-STDCALL
+NTAPI
 RtlDelete (
        PRTL_SPLAY_LINKS Links
        )
@@ -49,7 +32,7 @@ RtlDelete (
 * @unimplemented
 */
 VOID
-STDCALL
+NTAPI
 RtlDeleteNoSplay (
        PRTL_SPLAY_LINKS Links,
        PRTL_SPLAY_LINKS *Root
@@ -63,7 +46,7 @@ RtlDeleteNoSplay (
 * @unimplemented
 */
 PRTL_SPLAY_LINKS
-STDCALL
+NTAPI
 RtlRealPredecessor (
        PRTL_SPLAY_LINKS Links
        )
@@ -76,7 +59,7 @@ RtlRealPredecessor (
 * @unimplemented
 */
 PRTL_SPLAY_LINKS
-STDCALL
+NTAPI
 RtlRealSuccessor (
        PRTL_SPLAY_LINKS Links
        )
@@ -89,11 +72,43 @@ RtlRealSuccessor (
 * @unimplemented
 */
 PRTL_SPLAY_LINKS
-STDCALL
-RtlSplay (
-       PRTL_SPLAY_LINKS Links
-       )
+NTAPI
+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;
 }
@@ -102,7 +117,7 @@ RtlSplay (
 /*
 * @implemented
 */
-PRTL_SPLAY_LINKS STDCALL
+PRTL_SPLAY_LINKS NTAPI
 RtlSubtreePredecessor (IN PRTL_SPLAY_LINKS Links)
 {
    PRTL_SPLAY_LINKS Child;
@@ -124,7 +139,7 @@ RtlSubtreePredecessor (IN PRTL_SPLAY_LINKS Links)
 /*
 * @implemented
 */
-PRTL_SPLAY_LINKS STDCALL
+PRTL_SPLAY_LINKS NTAPI
 RtlSubtreeSuccessor (IN PRTL_SPLAY_LINKS Links)
 {
    PRTL_SPLAY_LINKS Child;