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  * @implemented
  20  */
  21 PRTL_SPLAY_LINKS
  22 NTAPI
  23 RtlDelete(PRTL_SPLAY_LINKS Links)
  24 {
  25     PRTL_SPLAY_LINKS N, P, C, SP;
  26     N = Links;
  27
  28     /* Check if we have two children */
  29     if ((RtlLeftChild(N)) && (RtlRightChild(N)))
  30     {
  31         /* Get the predecessor */
  32         SP = RtlSubtreePredecessor(N);
  33
  34         /* Swap it with N, this will guarantee that N will have only a child */
  35         //SwapSplayLinks(SP, N);
  36         DPRINT1("UNIMPLEMENTED!\n");
  37     }
  38
  39     /* Check if we have no children */
  40     if (!(RtlLeftChild(N)) && !(RtlRightChild(N)))
  41     {
  42         /* If we are also the root, then the tree is gone */
  43         return NULL;
  44
  45         /* Get our parent */
  46         P = RtlParent(N);
  47
  48         /* Find out who is referencing us and delete the reference */
  49         if (RtlIsLeftChild(N))
  50         {
  51             /* N was a left child, so erase its parent's left child link */
  52             RtlLeftChild(RtlParent(N)) = NULL;
  53         }
  54         else
  55         {
  56             /* N was a right child, so erase its parent's right child link */
  57             RtlRightChild(RtlParent(N)) = NULL;
  58         }
  59
  60         /* And finally splay the parent */
  61         return RtlSplay(P);
  62     }
  63
  64     /* If we got here, we have a child (not two: we swapped above!) */
  65     if (RtlLeftChild(N))
  66     {
  67         /* We have a left child, so get it */
  68         C = RtlLeftChild(N);
  69     }
  70     else
  71     {
  72         /* We have a right child, get him instead */
  73         C = RtlRightChild(N);
  74     }
  75
  76     /* Check if we are the root entry */
  77     if (RtlIsRoot(N))
  78     {
  79         /* Our child is now root, return him */
  80         C->Parent = C;
  81         return C;
  82     }
  83
  84     /* Find out who is referencing us and link to our child instead */
  85     if (RtlIsLeftChild(N))
  86     {
  87         /* N was a left child, so set its parent's left child as our child */
  88         RtlLeftChild(RtlParent(N)) = C;
  89     }
  90     else
  91     {
  92         /* N was a right child, so set its parent's right child as our child */
  93         RtlRightChild(RtlParent(N)) = C;
  94     }
  95
  96     /* Finally, inherit our parent and splay the parent */
  97     C->Parent = N->Parent;
  98     return RtlSplay(RtlParent(C));
  99 }
 100
 101 /*
 102 * @unimplemented
 103 */
 104 VOID
 105 NTAPI
 106 RtlDeleteNoSplay (
 107         PRTL_SPLAY_LINKS Links,
 108         PRTL_SPLAY_LINKS *Root
 109         )
 110 {
 111         UNIMPLEMENTED;
 112 }
 113
 114 /*
 115 * @implemented
 116 */
 117 PRTL_SPLAY_LINKS
 118 NTAPI
 119 RtlRealPredecessor(PRTL_SPLAY_LINKS Links)
 120 {
 121     PRTL_SPLAY_LINKS Child;
 122
 123     /* Get the left child */
 124     Child = RtlLeftChild(Links);
 125     if (Child)
 126     {
 127         /* Get right-most child */
 128         while (RtlRightChild(Child)) Child = RtlRightChild(Child);
 129         return Child;
 130     }
 131
 132     /* We don't have a left child, keep looping until we find our parent */
 133     Child = Links;
 134     while (RtlIsLeftChild(Child)) Child = RtlParent(Child);
 135
 136     /* The parent should be a right child, return the real predecessor */
 137     if (RtlIsRightChild(Child)) return RtlParent(Child);
 138
 139     /* The parent isn't a right child, so no real precessor for us */
 140     return NULL;
 141 }
 142
 143 /*
 144 * @implemented
 145 */
 146 PRTL_SPLAY_LINKS
 147 NTAPI
 148 RtlRealSuccessor(PRTL_SPLAY_LINKS Links)
 149 {
 150     PRTL_SPLAY_LINKS Child;
 151
 152     /* Get the right child */
 153     Child = RtlRightChild(Links);
 154     if (Child)
 155     {
 156         /* Get left-most child */
 157         while (RtlLeftChild(Child)) Child = RtlLeftChild(Child);
 158         return Child;
 159     }
 160
 161     /* We don't have a right child, keep looping until we find our parent */
 162     Child = Links;
 163     while (RtlIsRightChild(Child)) Child = RtlParent(Child);
 164
 165     /* The parent should be a left child, return the real successor */
 166     if (RtlIsLeftChild(Child)) return RtlParent(Child);
 167
 168     /* The parent isn't a right child, so no real successor for us */
 169     return NULL;
 170 }
 171
 172 /*
 173 * @implemented
 174 */
 175 PRTL_SPLAY_LINKS
 176 NTAPI
 177 RtlSplay(PRTL_SPLAY_LINKS Links)
 178 {
 179     /*
 180      * Implementation Notes (http://en.wikipedia.org/wiki/Splay_tree):
 181      *
 182      * To do a splay, we carry out a sequence of rotations,
 183      * each of which moves the target node N closer to the root.
 184      *
 185      * Each particular step depends on only two factors:
 186      *  - Whether N is the left or right child of its parent node, P,
 187      *  - Whether P is the left or right child of its parent, G (for grandparent node).
 188      *
 189      * Thus, there are four cases:
 190      *  - Case 1: N is the left child of P and P is the left child of G.
 191      *            In this case we perform a double right rotation, so that
 192      *            P becomes N's right child, and G becomes P's right child.
 193      *
 194      *  - Case 2: N is the right child of P and P is the right child of G.
 195      *            In this case we perform a double left rotation, so that
 196      *            P becomes N's left child, and G becomes P's left child.
 197      *
 198      *  - Case 3: N is the left child of P and P is the right child of G.
 199      *            In this case we perform a rotation so that
 200      *            G becomes N's left child, and P becomes N's right child.
 201      *
 202      *  - Case 4: N is the right child of P and P is the left child of G.
 203      *            In this case we perform a rotation so that
 204      *            P becomes N's left child, and G becomes N's right child.
 205      *
 206      * Finally, if N doesn't have a grandparent node, we simply perform a
 207      * left or right rotation to move it to the root.
 208      *
 209      * By performing a splay on the node of interest after every operation,
 210      * we keep recently accessed nodes near the root and keep the tree
 211      * roughly balanced, so that we achieve the desired amortized time bounds.
 212      */
 213     PRTL_SPLAY_LINKS N, P, G;
 214
 215     /* N is the item we'll be playing with */
 216     N = Links;
 217
 218     /* Let the algorithm run until N becomes the root entry */
 219     while (!RtlIsRoot(N))
 220     {
 221         /* Now get the parent and grand-parent */
 222         P = RtlParent(N);
 223         G = RtlParent(P);
 224
 225         /* Case 1 & 3: N is left child of P */
 226         if (RtlIsLeftChild(N))
 227         {
 228             /* Case 1: P is the left child of G */
 229             if (RtlIsLeftChild(P))
 230             {
 231                 /*
 232                  * N's right-child becomes P's left child and
 233                  * P's right-child becomes G's left child.
 234                  */
 235                 RtlLeftChild(P) = RtlRightChild(N);
 236                 RtlLeftChild(G) = RtlRightChild(P);
 237
 238                 /*
 239                  * If they exist, update their parent pointers too,
 240                  * since they've changed trees.
 241                  */
 242                 if (RtlLeftChild(P)) RtlParent(RtlLeftChild(P)) = P;
 243                 if (RtlLeftChild(G)) RtlParent(RtlLeftChild(G)) = G;
 244
 245                 /*
 246                  * Now we'll shove N all the way to the top.
 247                  * Check if G is the root first.
 248                  */
 249                 if (RtlIsRoot(G))
 250                 {
 251                     /* G doesn't have a parent, so N will become the root! */
 252                     RtlParent(N) = N;
 253                 }
 254                 else
 255                 {
 256                     /* G has a parent, so inherit it since we take G's place */
 257                     RtlParent(N) = RtlParent(G);
 258
 259                     /*
 260                      * Now find out who was referencing G and have it reference
 261                      * N instead, since we're taking G's place.
 262                      */
 263                     if (RtlIsLeftChild(G))
 264                     {
 265                         /*
 266                          * G was a left child, so change its parent's left
 267                          * child link to point to N now.
 268                          */
 269                         RtlLeftChild(RtlParent(G)) = N;
 270                     }
 271                     else
 272                     {
 273                         /*
 274                          * G was a right child, so change its parent's right
 275                          * child link to point to N now.
 276                          */
 277                         RtlLeftChild(RtlParent(G)) = N;
 278                     }
 279                 }
 280
 281                 /* Now N is on top, so P has become its child. */
 282                 RtlRightChild(N) = P;
 283                 RtlParent(P) = N;
 284
 285                 /* N is on top, P is its child, so G is grandchild. */
 286                 RtlRightChild(P) = G;
 287                 RtlParent(G) = P;
 288             }
 289             /* Case 3: P is the right child of G */
 290             else if (RtlIsRightChild(P))
 291             {
 292                 /*
 293                  * N's left-child becomes G's right child and
 294                  * N's right-child becomes P's left child.
 295                  */
 296                 RtlRightChild(G) = RtlLeftChild(N);
 297                 RtlLeftChild(P) = RtlRightChild(N);
 298
 299                 /*
 300                  * If they exist, update their parent pointers too,
 301                  * since they've changed trees.
 302                  */
 303                 if (RtlRightChild(G)) RtlParent(RtlRightChild(G)) = G;
 304                 if (RtlLeftChild(P)) RtlParent(RtlLeftChild(P)) = P;
 305
 306                 /*
 307                  * Now we'll shove N all the way to the top.
 308                  * Check if G is the root first.
 309                  */
 310                 if (RtlIsRoot(G))
 311                 {
 312                     /* G doesn't have a parent, so N will become the root! */
 313                     RtlParent(N) = N;
 314                 }
 315                 else
 316                 {
 317                     /* G has a parent, so inherit it since we take G's place */
 318                     RtlParent(N) = RtlParent(G);
 319
 320                     /*
 321                      * Now find out who was referencing G and have it reference
 322                      * N instead, since we're taking G's place.
 323                      */
 324                     if (RtlIsLeftChild(G))
 325                     {
 326                         /*
 327                          * G was a left child, so change its parent's left
 328                          * child link to point to N now.
 329                          */
 330                         RtlLeftChild(RtlParent(G)) = N;
 331                     }
 332                     else
 333                     {
 334                         /*
 335                          * G was a right child, so change its parent's right
 336                          * child link to point to N now.
 337                          */
 338                         RtlLeftChild(RtlParent(G)) = N;
 339                     }
 340                 }
 341
 342                 /* Now N is on top, so G has become its left child. */
 343                 RtlLeftChild(N) = G;
 344                 RtlParent(G) = N;
 345
 346                 /* N is on top, G is its left child, so P is right child. */
 347                 RtlRightChild(N) = P;
 348                 RtlParent(P) = N;
 349             }
 350             /* "Finally" case: N doesn't have a grandparent => P is root */
 351             else
 352             {
 353                 /* P's left-child becomes N's right child */
 354                 RtlLeftChild(P) = RtlRightChild(N);
 355
 356                 /* If it exists, update its parent pointer too */
 357                 if (RtlLeftChild(P)) RtlParent(RtlLeftChild(P)) = P;
 358
 359                 /* Now make N the root, no need to worry about references */
 360                 N->Parent = N;
 361
 362                 /* And make P its right child */
 363                 N->RightChild = P;
 364                 P->Parent = N;
 365             }
 366         }
 367         /* Case 2 & 4: N is right child of P */
 368         else
 369         {
 370             /* Case 2: P is the right child of G */
 371             if (RtlIsRightChild(P))
 372             {
 373                 /*
 374                  * P's left-child becomes G's right child and
 375                  * N's left-child becomes P's right child.
 376                  */
 377                 RtlRightChild(G) = RtlLeftChild(P);
 378                 RtlRightChild(P) = RtlLeftChild(N);
 379
 380                 /*
 381                  * If they exist, update their parent pointers too,
 382                  * since they've changed trees.
 383                  */
 384                 if (RtlRightChild(G)) RtlParent(RtlRightChild(G)) = G;
 385                 if (RtlRightChild(P)) RtlParent(RtlRightChild(P)) = P;
 386
 387                 /*
 388                  * Now we'll shove N all the way to the top.
 389                  * Check if G is the root first.
 390                  */
 391                 if (RtlIsRoot(G))
 392                 {
 393                     /* G doesn't have a parent, so N will become the root! */
 394                     RtlParent(N) = N;
 395                 }
 396                 else
 397                 {
 398                     /* G has a parent, so inherit it since we take G's place */
 399                     RtlParent(N) = RtlParent(G);
 400
 401                     /*
 402                      * Now find out who was referencing G and have it reference
 403                      * N instead, since we're taking G's place.
 404                      */
 405                     if (RtlIsLeftChild(G))
 406                     {
 407                         /*
 408                          * G was a left child, so change its parent's left
 409                          * child link to point to N now.
 410                          */
 411                         RtlLeftChild(RtlParent(G)) = N;
 412                     }
 413                     else
 414                     {
 415                         /*
 416                          * G was a right child, so change its parent's right
 417                          * child link to point to N now.
 418                          */
 419                         RtlLeftChild(RtlParent(G)) = N;
 420                     }
 421                 }
 422
 423                 /* Now N is on top, so P has become its child. */
 424                 RtlLeftChild(N) = P;
 425                 RtlParent(P) = N;
 426
 427                 /* N is on top, P is its child, so G is grandchild. */
 428                 RtlLeftChild(P) = G;
 429                 RtlParent(G) = P;
 430             }
 431             /* Case 4: P is the left child of G */
 432             else if (RtlIsLeftChild(P))
 433             {
 434                 /*
 435                  * N's left-child becomes G's right child and
 436                  * N's right-child becomes P's left child.
 437                  */
 438                 RtlRightChild(P) = RtlLeftChild(N);
 439                 RtlLeftChild(G) = RtlRightChild(N);
 440
 441                 /*
 442                  * If they exist, update their parent pointers too,
 443                  * since they've changed trees.
 444                  */
 445                 if (RtlRightChild(P)) RtlParent(RtlRightChild(P)) = P;
 446                 if (RtlLeftChild(G)) RtlParent(RtlLeftChild(G)) = G;
 447
 448                 /*
 449                  * Now we'll shove N all the way to the top.
 450                  * Check if G is the root first.
 451                  */
 452                 if (RtlIsRoot(G))
 453                 {
 454                     /* G doesn't have a parent, so N will become the root! */
 455                     RtlParent(N) = N;
 456                 }
 457                 else
 458                 {
 459                     /* G has a parent, so inherit it since we take G's place */
 460                     RtlParent(N) = RtlParent(G);
 461
 462                     /*
 463                      * Now find out who was referencing G and have it reference
 464                      * N instead, since we're taking G's place.
 465                      */
 466                     if (RtlIsLeftChild(G))
 467                     {
 468                         /*
 469                          * G was a left child, so change its parent's left
 470                          * child link to point to N now.
 471                          */
 472                         RtlLeftChild(RtlParent(G)) = N;
 473                     }
 474                     else
 475                     {
 476                         /*
 477                          * G was a right child, so change its parent's right
 478                          * child link to point to N now.
 479                          */
 480                         RtlLeftChild(RtlParent(G)) = N;
 481                     }
 482                 }
 483
 484                 /* Now N is on top, so P has become its left child. */
 485                 RtlLeftChild(N) = P;
 486                 RtlParent(G) = N;
 487
 488                 /* N is on top, P is its left child, so G is right child. */
 489                 RtlRightChild(N) = G;
 490                 RtlParent(P) = N;
 491             }
 492             /* "Finally" case: N doesn't have a grandparent => P is root */
 493             else
 494             {
 495                 /* P's right-child becomes N's left child */
 496                 RtlRightChild(P) = RtlLeftChild(N);
 497
 498                 /* If it exists, update its parent pointer too */
 499                 if (RtlRightChild(P)) RtlParent(RtlRightChild(P)) = P;
 500
 501                 /* Now make N the root, no need to worry about references */
 502                 N->Parent = N;
 503
 504                 /* And make P its left child */
 505                 N->LeftChild = P;
 506                 P->Parent = N;
 507             }
 508         }
 509     }
 510
 511         /* Return the root entry */
 512         return N;
 513 }
 514
 515 /*
 516 * @implemented
 517 */
 518 PRTL_SPLAY_LINKS
 519 NTAPI
 520 RtlSubtreePredecessor(IN PRTL_SPLAY_LINKS Links)
 521 {
 522     PRTL_SPLAY_LINKS Child;
 523
 524     /* Get the left child */
 525     Child = RtlLeftChild(Links);
 526     if (!Child) return NULL;
 527
 528     /* Get right-most child */
 529     while (RtlRightChild(Child)) Child = RtlRightChild(Child);
 530
 531     /* Return it */
 532     return Child;
 533 }
 534
 535 /*
 536 * @implemented
 537 */
 538 PRTL_SPLAY_LINKS
 539 NTAPI
 540 RtlSubtreeSuccessor(IN PRTL_SPLAY_LINKS Links)
 541 {
 542     PRTL_SPLAY_LINKS Child;
 543
 544     /* Get the right child */
 545     Child = RtlRightChild(Links);
 546     if (!Child) return NULL;
 547
 548     /* Get left-most child */
 549     while (RtlLeftChild(Child)) Child = RtlLeftChild(Child);
 550
 551     /* Return it */
 552     return Child;
 553 }
 554
 555 /* EOF */