reactos/lib/rtl/splaytree.c

   1 /*
   2  * COPYRIGHT:         See COPYING in the top level directory
   3  * PROJECT:           ReactOS system libraries
   4  * PURPOSE:           Splay-Tree implementation
   5  * FILE:              lib/rtl/splaytree.c
   6  * PROGRAMMER:
   7  */
   8
   9 /* INCLUDES *****************************************************************/
  10
  11 #include <rtl.h>
  12
  13 #define NDEBUG
  14 #include <debug.h>
  15
  16 /* FUNCTIONS ***************************************************************/
  17
  18 /*
  19 * @unimplemented
  20 */
  21 PRTL_SPLAY_LINKS
  22 NTAPI
  23 RtlDelete (
  24         PRTL_SPLAY_LINKS Links
  25         )
  26 {
  27         UNIMPLEMENTED;
  28         return 0;
  29 }
  30
  31 /*
  32 * @unimplemented
  33 */
  34 VOID
  35 NTAPI
  36 RtlDeleteNoSplay (
  37         PRTL_SPLAY_LINKS Links,
  38         PRTL_SPLAY_LINKS *Root
  39         )
  40 {
  41         UNIMPLEMENTED;
  42 }
  43
  44
  45 /*
  46 * @unimplemented
  47 */
  48 PRTL_SPLAY_LINKS
  49 NTAPI
  50 RtlRealPredecessor (
  51         PRTL_SPLAY_LINKS Links
  52         )
  53 {
  54         UNIMPLEMENTED;
  55         return 0;
  56 }
  57
  58 /*
  59 * @unimplemented
  60 */
  61 PRTL_SPLAY_LINKS
  62 NTAPI
  63 RtlRealSuccessor (
  64         PRTL_SPLAY_LINKS Links
  65         )
  66 {
  67         UNIMPLEMENTED;
  68         return 0;
  69 }
  70
  71 /*
  72 * @unimplemented
  73 */
  74 PRTL_SPLAY_LINKS
  75 NTAPI
  76 RtlSplay(PRTL_SPLAY_LINKS Links)
  77 {
  78     /*
  79      * Implementation Notes (http://en.wikipedia.org/wiki/Splay_tree):
  80      *
  81      * To do a splay, we carry out a sequence of rotations,
  82      * each of which moves the target node N closer to the root.
  83      *
  84      * Each particular step depends on only two factors:
  85      *  - Whether N is the left or right child of its parent node, P,
  86      *  - Whether P is the left or right child of its parent, G (for grandparent node).
  87      *
  88      * Thus, there are four cases:
  89      *  - Case 1: N is the left child of P and P is the left child of G.
  90      *            In this case we perform a double right rotation, so that
  91      *            P becomes N's right child, and G becomes P's right child.
  92      *
  93      *  - Case 2: N is the right child of P and P is the right child of G.
  94      *            In this case we perform a double left rotation, so that
  95      *            P becomes N's left child, and G becomes P's left child.
  96      *
  97      *  - Case 3: N is the left child of P and P is the right child of G.
  98      *            In this case we perform a rotation so that
  99      *            G becomes N's left child, and P becomes N's right child.
 100      *
 101      *  - Case 4: N is the right child of P and P is the left child of G.
 102      *            In this case we perform a rotation so that
 103      *            P becomes N's left child, and G becomes N's right child.
 104      *
 105      * Finally, if N doesn't have a grandparent node, we simply perform a
 106      * left or right rotation to move it to the root.
 107      *
 108      * By performing a splay on the node of interest after every operation,
 109      * we keep recently accessed nodes near the root and keep the tree
 110      * roughly balanced, so that we achieve the desired amortized time bounds.
 111      */
 112         UNIMPLEMENTED;
 113         return 0;
 114 }
 115
 116
 117 /*
 118 * @implemented
 119 */
 120 PRTL_SPLAY_LINKS NTAPI
 121 RtlSubtreePredecessor (IN PRTL_SPLAY_LINKS Links)
 122 {
 123    PRTL_SPLAY_LINKS Child;
 124
 125    Child = Links->RightChild;
 126    if (Child == NULL)
 127       return NULL;
 128
 129    if (Child->LeftChild == NULL)
 130       return Child;
 131
 132    /* Get left-most child */
 133    while (Child->LeftChild != NULL)
 134       Child = Child->LeftChild;
 135
 136    return Child;
 137 }
 138
 139 /*
 140 * @implemented
 141 */
 142 PRTL_SPLAY_LINKS NTAPI
 143 RtlSubtreeSuccessor (IN PRTL_SPLAY_LINKS Links)
 144 {
 145    PRTL_SPLAY_LINKS Child;
 146
 147    Child = Links->LeftChild;
 148    if (Child == NULL)
 149       return NULL;
 150
 151    if (Child->RightChild == NULL)
 152       return Child;
 153
 154    /* Get right-most child */
 155    while (Child->RightChild != NULL)
 156       Child = Child->RightChild;
 157
 158    return Child;
 159 }
 160
 161 /* EOF */