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     PRTL_SPLAY_LINKS N, P, G;
 113
 114     /* N is the item we'll be playing with */
 115     N = Links;
 116
 117     /* Let the algorithm run until N becomes the root entry */
 118     while (!RtlIsRoot(N))
 119     {
 120         /* Now get the parent and grand-parent */
 121         P = RtlParent(N);
 122         G = RtlParent(P);
 123
 124         /* Case 1 & 3: N is left child of P */
 125         if (RtlIsLeftChild(N))
 126         {
 127             /* Case 1: P is the left child of G */
 128             if (RtlIsLeftChild(P))
 129             {
 130
 131             }
 132             /* Case 3: P is the right child of G */
 133             else if (RtlIsRightChild(P))
 134             {
 135
 136             }
 137             /* "Finally" case: N doesn't have a grandparent => P is root */
 138             else
 139             {
 140
 141             }
 142         }
 143         /* Case 2 & 4: N is right child of P */
 144         else
 145         {
 146             /* Case 2: P is the left child of G */
 147             if (RtlIsLeftChild(P))
 148             {
 149
 150             }
 151             /* Case 4: P is the right child of G */
 152             else if (RtlIsRightChild(P))
 153             {
 154
 155             }
 156             /* "Finally" case: N doesn't have a grandparent => P is root */
 157             else
 158             {
 159
 160             }
 161         }
 162     }
 163
 164         /* Return the root entry */
 165         return N;
 166 }
 167
 168
 169 /*
 170 * @implemented
 171 */
 172 PRTL_SPLAY_LINKS NTAPI
 173 RtlSubtreePredecessor (IN PRTL_SPLAY_LINKS Links)
 174 {
 175    PRTL_SPLAY_LINKS Child;
 176
 177    Child = Links->RightChild;
 178    if (Child == NULL)
 179       return NULL;
 180
 181    if (Child->LeftChild == NULL)
 182       return Child;
 183
 184    /* Get left-most child */
 185    while (Child->LeftChild != NULL)
 186       Child = Child->LeftChild;
 187
 188    return Child;
 189 }
 190
 191 /*
 192 * @implemented
 193 */
 194 PRTL_SPLAY_LINKS NTAPI
 195 RtlSubtreeSuccessor (IN PRTL_SPLAY_LINKS Links)
 196 {
 197    PRTL_SPLAY_LINKS Child;
 198
 199    Child = Links->LeftChild;
 200    if (Child == NULL)
 201       return NULL;
 202
 203    if (Child->RightChild == NULL)
 204       return Child;
 205
 206    /* Get right-most child */
 207    while (Child->RightChild != NULL)
 208       Child = Child->RightChild;
 209
 210    return Child;
 211 }
 212
 213 /* EOF */