sdk/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:        Alex Ionescu (alex@relsoft.net)
   7  */
   8
   9 /* INCLUDES *****************************************************************/
  10
  11 #include <rtl.h>
  12
  13 #define NDEBUG
  14 #include <debug.h>
  15
  16 //#define VERIFY_SWAP_SPLAY_LINKS
  17
  18 /* FUNCTIONS ***************************************************************/
  19
  20 static
  21 VOID
  22 FixupChildLinks(PRTL_SPLAY_LINKS Links, BOOLEAN Root, BOOLEAN LeftChild)
  23 {
  24     if (RtlLeftChild(Links))
  25     {
  26         RtlInsertAsLeftChild(Links, RtlLeftChild(Links));
  27     }
  28
  29     if (RtlRightChild(Links))
  30     {
  31         RtlInsertAsRightChild(Links, RtlRightChild(Links));
  32     }
  33
  34     if (!Root)
  35     {
  36         if (LeftChild)
  37         {
  38             RtlInsertAsLeftChild(RtlParent(Links), Links);
  39         }
  40         else
  41         {
  42             RtlInsertAsRightChild(RtlParent(Links), Links);
  43         }
  44     }
  45 }
  46
  47 /*
  48
  49 Given the tree:
  50    D
  51  B   F
  52 A C E G
  53
  54 Swap(Q,S):
  55
  56 Q S   Q.P Q.L Q.R S.P S.L S.R
  57 A C   S.P S.L S.R Q.P Q.L Q.R
  58 B A   S   S.L S.R Q.P Q   Q.R
  59 B C   S   S.L S.R Q.P Q.L Q
  60 D A   S.P S.L S.R S   Q.L Q.R
  61 D B   S   S.L S.R S   Q   Q.R
  62 D F   S   S.L S.R S   Q.L Q
  63
  64 When Q is the immediate parent of S,
  65   Set Q's parent to S, and the proper child ptr of S to Q
  66 When Q is the root,
  67   Set S's parent to S
  68
  69 */
  70
  71 static
  72 VOID
  73 SwapSplayLinks(PRTL_SPLAY_LINKS LinkA,
  74                PRTL_SPLAY_LINKS LinkB)
  75 {
  76     if (RtlParent(LinkA) == LinkB || RtlIsRoot(LinkB))
  77     {
  78         PRTL_SPLAY_LINKS Tmp = LinkA;
  79         LinkA = LinkB;
  80         LinkB = Tmp;
  81     }
  82
  83     {
  84         RTL_SPLAY_LINKS Ta = *LinkA, Tb = *LinkB;
  85         BOOLEAN RootA = RtlIsRoot(LinkA),
  86                 LeftA = RtlIsLeftChild(LinkA),
  87                 LeftB = RtlIsLeftChild(LinkB);
  88
  89         *LinkB = Ta; *LinkA = Tb;
  90
  91         // A was parent of B is a special case: A->Parent is now B
  92         if (RtlParent(&Tb) == LinkA)
  93         {
  94             if (!RootA)
  95             {
  96                 if (LeftA)
  97                 {
  98                     RtlInsertAsLeftChild(RtlParent(&Ta), LinkB);
  99                 }
 100                 else
 101                 {
 102                     RtlInsertAsRightChild(RtlParent(&Ta), LinkB);
 103                 }
 104             }
 105
 106             if (LeftB)
 107             {
 108                 RtlInsertAsLeftChild(LinkB, LinkA);
 109             }
 110             else
 111             {
 112                 RtlInsertAsRightChild(LinkB, LinkA);
 113             }
 114         }
 115
 116         FixupChildLinks(LinkA, FALSE, LeftB);
 117         FixupChildLinks(LinkB, RootA, LeftA);
 118
 119         // A was root is a special case: B->Parent is now B
 120         if (RootA)
 121             RtlParent(LinkB) = LinkB;
 122
 123 #ifdef VERIFY_SWAP_SPLAY_LINKS
 124         // Verify the distinct cases of node swap
 125         if (RootA)
 126         {
 127             if (RtlParent(&Tb) == LinkA)
 128             {
 129                 // LinkA = D, LinkB = B
 130                 // D B   S   S.L S.R S   Q   Q.R
 131                 ASSERT(RtlParent(LinkA) == LinkB);
 132                 ASSERT(RtlLeftChild(LinkA) == RtlLeftChild(&Tb));
 133                 ASSERT(RtlRightChild(LinkA) == RtlRightChild(&Tb));
 134                 ASSERT(RtlParent(LinkB) == LinkB);
 135                 ASSERT(RtlLeftChild(LinkB) == (LeftB ? LinkA : RtlLeftChild(&Ta)));
 136                 ASSERT(RtlRightChild(LinkB) == (LeftB ? RtlRightChild(&Ta) : LinkA));
 137             }
 138             else
 139             {
 140                 // LinkA = D, LinkB = A
 141                 // D A   S.P S.L S.R S   Q.L Q.R
 142                 ASSERT(RtlParent(LinkA) == RtlParent(&Tb));
 143                 ASSERT(RtlLeftChild(LinkA) == RtlLeftChild(&Tb));
 144                 ASSERT(RtlRightChild(LinkA) == RtlRightChild(&Tb));
 145                 ASSERT(RtlParent(LinkB) == LinkB);
 146                 ASSERT(RtlLeftChild(LinkB) == RtlLeftChild(&Ta));
 147                 ASSERT(RtlRightChild(LinkB) == RtlRightChild(&Ta));
 148             }
 149         }
 150         else
 151         {
 152             if (RtlParent(&Tb) == LinkA)
 153             {
 154                 // LinkA = B, LinkB = A
 155                 // B A   S   S.L S.R Q.P Q   Q.R
 156                 ASSERT(RtlParent(LinkA) == LinkB);
 157                 ASSERT(RtlLeftChild(LinkA) == RtlLeftChild(&Tb));
 158                 ASSERT(RtlRightChild(LinkA) == RtlRightChild(&Tb));
 159                 ASSERT(RtlParent(LinkB) == RtlParent(&Ta));
 160                 ASSERT(RtlLeftChild(LinkB) == (LeftB ? LinkA : RtlLeftChild(&Ta)));
 161                 ASSERT(RtlRightChild(LinkB) == (LeftB ? RtlRightChild(&Ta) : LinkA));
 162             }
 163             else
 164             {
 165                 // LinkA = A, LinkB = C
 166                 // A C   S.P S.L S.R Q.P Q.L Q.R
 167                 ASSERT(!memcmp(LinkA, &Tb, sizeof(Tb)));
 168                 ASSERT(!memcmp(LinkB, &Ta, sizeof(Ta)));
 169             }
 170         }
 171 #endif
 172     }
 173 }
 174
 175 /*
 176  * @implemented
 177  */
 178 PRTL_SPLAY_LINKS
 179 NTAPI
 180 RtlDelete(PRTL_SPLAY_LINKS Links)
 181 {
 182     PRTL_SPLAY_LINKS N, P, C, SP;
 183     N = Links;
 184
 185     /* Check if we have two children */
 186     if (RtlLeftChild(N) && RtlRightChild(N))
 187     {
 188         /* Get the predecessor */
 189         SP = RtlSubtreePredecessor(N);
 190
 191         /* Swap it with N, this will guarantee that N will only have a child */
 192         SwapSplayLinks(SP, N);
 193     }
 194
 195     /* Check if we have no children */
 196     if (!RtlLeftChild(N) && !RtlRightChild(N))
 197     {
 198         /* If we are also the root, then the tree is gone */
 199         if (RtlIsRoot(N)) return NULL;
 200
 201         /* Get our parent */
 202         P = RtlParent(N);
 203
 204         /* Find out who is referencing us and delete the reference */
 205         if (RtlIsLeftChild(N))
 206         {
 207             /* N was a left child, so erase its parent's left child link */
 208             RtlLeftChild(P) = NULL;
 209         }
 210         else
 211         {
 212             /* N was a right child, so erase its parent's right child link */
 213             RtlRightChild(P) = NULL;
 214         }
 215
 216         /* And finally splay the parent */
 217         return RtlSplay(P);
 218     }
 219
 220     /* If we got here, we have a child (not two: we swapped above!) */
 221     if (RtlLeftChild(N))
 222     {
 223         /* We have a left child, so get it */
 224         C = RtlLeftChild(N);
 225     }
 226     else
 227     {
 228         /* We have a right child, get it instead */
 229         C = RtlRightChild(N);
 230     }
 231
 232     /* Check if we are the root entry */
 233     if (RtlIsRoot(N))
 234     {
 235         /* Our child is now root, return it */
 236         RtlParent(C) = C;
 237         return C;
 238     }
 239
 240     /* Get our parent */
 241     P = RtlParent(N);
 242
 243     /* Find out who is referencing us and link to our child instead */
 244     if (RtlIsLeftChild(N))
 245     {
 246         /* N was a left child, so set its parent's left child as our child */
 247         RtlLeftChild(P) = C;
 248     }
 249     else
 250     {
 251         /* N was a right child, so set its parent's right child as our child */
 252         RtlRightChild(P) = C;
 253     }
 254
 255     /* Finally, inherit our parent and splay the parent */
 256     RtlParent(C) = P;
 257     return RtlSplay(P);
 258 }
 259
 260 /*
 261  * @implemented
 262  */
 263 VOID
 264 NTAPI
 265 RtlDeleteNoSplay(PRTL_SPLAY_LINKS Links,
 266                  PRTL_SPLAY_LINKS *Root)
 267 {
 268     PRTL_SPLAY_LINKS N, P, C, SP;
 269     N = Links;
 270
 271     /* Check if we have two children */
 272     if (RtlLeftChild(N) && RtlRightChild(N))
 273     {
 274         /* Get the predecessor */
 275         SP = RtlSubtreePredecessor(N);
 276
 277         /* If we are the root, the new root will be our predecessor after swapping */
 278         if (RtlIsRoot(N)) *Root = SP;
 279
 280         /* Swap the predecessor with N, this will guarantee that N will only have a child */
 281         SwapSplayLinks(SP, N);
 282     }
 283
 284     /* Check if we have no children */
 285     if (!RtlLeftChild(N) && !RtlRightChild(N))
 286     {
 287         /* If we are also the root, then the tree is gone */
 288         if (RtlIsRoot(N))
 289         {
 290             *Root = NULL;
 291             return;
 292         }
 293
 294         /* Get our parent */
 295         P = RtlParent(N);
 296
 297         /* Find out who is referencing us and delete the reference */
 298         if (RtlIsLeftChild(N))
 299         {
 300             /* N was a left child, so erase its parent's left child link */
 301             RtlLeftChild(P) = NULL;
 302         }
 303         else
 304         {
 305             /* N was a right child, so erase its parent's right child link */
 306             RtlRightChild(P) = NULL;
 307         }
 308
 309         /* We are done */
 310         return;
 311     }
 312
 313     /* If we got here, we have a child (not two: we swapped above!) */
 314     if (RtlLeftChild(N))
 315     {
 316         /* We have a left child, so get it */
 317         C = RtlLeftChild(N);
 318     }
 319     else
 320     {
 321         /* We have a right child, get it instead */
 322         C = RtlRightChild(N);
 323     }
 324
 325     /* Check if we are the root entry */
 326     if (RtlIsRoot(N))
 327     {
 328         /* Our child is now root, return it */
 329         RtlParent(C) = C;
 330         *Root = C;
 331         return;
 332     }
 333
 334     /* Get our parent */
 335     P = RtlParent(N);
 336
 337     /* Find out who is referencing us and link to our child instead */
 338     if (RtlIsLeftChild(N))
 339     {
 340         /* N was a left child, so set its parent's left child as our child */
 341         RtlLeftChild(P) = C;
 342     }
 343     else
 344     {
 345         /* N was a right child, so set its parent's right child as our child */
 346         RtlRightChild(P) = C;
 347     }
 348
 349     /* Finally, inherit our parent and we are done */
 350     RtlParent(C) = P;
 351     return;
 352 }
 353
 354 /*
 355  * @implemented
 356  */
 357 PRTL_SPLAY_LINKS
 358 NTAPI
 359 RtlRealPredecessor(PRTL_SPLAY_LINKS Links)
 360 {
 361     PRTL_SPLAY_LINKS Child;
 362
 363     /* Get the left child */
 364     Child = RtlLeftChild(Links);
 365     if (Child)
 366     {
 367         /* Get right-most child */
 368         while (RtlRightChild(Child)) Child = RtlRightChild(Child);
 369         return Child;
 370     }
 371
 372     /* We don't have a left child, keep looping until we find our parent */
 373     Child = Links;
 374     while (RtlIsLeftChild(Child)) Child = RtlParent(Child);
 375
 376     /* The parent should be a right child, return the real predecessor */
 377     if (RtlIsRightChild(Child)) return RtlParent(Child);
 378
 379     /* The parent isn't a right child, so no real precessor for us */
 380     return NULL;
 381 }
 382
 383 /*
 384  * @implemented
 385  */
 386 PRTL_SPLAY_LINKS
 387 NTAPI
 388 RtlRealSuccessor(PRTL_SPLAY_LINKS Links)
 389 {
 390     PRTL_SPLAY_LINKS Child;
 391
 392     /* Get the right child */
 393     Child = RtlRightChild(Links);
 394     if (Child)
 395     {
 396         /* Get left-most child */
 397         while (RtlLeftChild(Child)) Child = RtlLeftChild(Child);
 398         return Child;
 399     }
 400
 401     /* We don't have a right child, keep looping until we find our parent */
 402     Child = Links;
 403     while (RtlIsRightChild(Child)) Child = RtlParent(Child);
 404
 405     /* The parent should be a left child, return the real successor */
 406     if (RtlIsLeftChild(Child)) return RtlParent(Child);
 407
 408     /* The parent isn't a right child, so no real successor for us */
 409     return NULL;
 410 }
 411
 412 /*
 413  * @implemented
 414  */
 415 PRTL_SPLAY_LINKS
 416 NTAPI
 417 RtlSplay(PRTL_SPLAY_LINKS Links)
 418 {
 419     /*
 420      * Implementation Notes (http://en.wikipedia.org/wiki/Splay_tree):
 421      *
 422      * To do a splay, we carry out a sequence of rotations,
 423      * each of which moves the target node N closer to the root.
 424      *
 425      * Each particular step depends on only two factors:
 426      *  - Whether N is the left or right child of its parent node, P,
 427      *  - Whether P is the left or right child of its parent, G (for grandparent node).
 428      *
 429      * Thus, there are four cases:
 430      *  - Case 1: N is the left child of P and P is the left child of G.
 431      *            In this case we perform a double right rotation, so that
 432      *            P becomes N's right child, and G becomes P's right child.
 433      *
 434      *  - Case 2: N is the right child of P and P is the right child of G.
 435      *            In this case we perform a double left rotation, so that
 436      *            P becomes N's left child, and G becomes P's left child.
 437      *
 438      *  - Case 3: N is the left child of P and P is the right child of G.
 439      *            In this case we perform a rotation so that
 440      *            G becomes N's left child, and P becomes N's right child.
 441      *
 442      *  - Case 4: N is the right child of P and P is the left child of G.
 443      *            In this case we perform a rotation so that
 444      *            P becomes N's left child, and G becomes N's right child.
 445      *
 446      * Finally, if N doesn't have a grandparent node, we simply perform a
 447      * left or right rotation to move it to the root.
 448      *
 449      * By performing a splay on the node of interest after every operation,
 450      * we keep recently accessed nodes near the root and keep the tree
 451      * roughly balanced, so that we achieve the desired amortized time bounds.
 452      */
 453     PRTL_SPLAY_LINKS N, P, G;
 454
 455     /* N is the item we'll be playing with */
 456     N = Links;
 457
 458     /* Let the algorithm run until N becomes the root entry */
 459     while (!RtlIsRoot(N))
 460     {
 461         /* Now get the parent and grand-parent */
 462         P = RtlParent(N);
 463         G = RtlParent(P);
 464
 465         /* Case 1 & 3: N is left child of P */
 466         if (RtlIsLeftChild(N))
 467         {
 468             /* Case 1: P is the left child of G */
 469             if (RtlIsLeftChild(P))
 470             {
 471                 /*
 472                  * N's right-child becomes P's left child and
 473                  * P's right-child becomes G's left child.
 474                  */
 475                 RtlLeftChild(P) = RtlRightChild(N);
 476                 RtlLeftChild(G) = RtlRightChild(P);
 477
 478                 /*
 479                  * If they exist, update their parent pointers too,
 480                  * since they've changed trees.
 481                  */
 482                 if (RtlLeftChild(P)) RtlParent(RtlLeftChild(P)) = P;
 483                 if (RtlLeftChild(G)) RtlParent(RtlLeftChild(G)) = G;
 484
 485                 /*
 486                  * Now we'll shove N all the way to the top.
 487                  * Check if G is the root first.
 488                  */
 489                 if (RtlIsRoot(G))
 490                 {
 491                     /* G doesn't have a parent, so N will become the root! */
 492                     RtlParent(N) = N;
 493                 }
 494                 else
 495                 {
 496                     /* G has a parent, so inherit it since we take G's place */
 497                     RtlParent(N) = RtlParent(G);
 498
 499                     /*
 500                      * Now find out who was referencing G and have it reference
 501                      * N instead, since we're taking G's place.
 502                      */
 503                     if (RtlIsLeftChild(G))
 504                     {
 505                         /*
 506                          * G was a left child, so change its parent's left
 507                          * child link to point to N now.
 508                          */
 509                         RtlLeftChild(RtlParent(G)) = N;
 510                     }
 511                     else
 512                     {
 513                         /*
 514                          * G was a right child, so change its parent's right
 515                          * child link to point to N now.
 516                          */
 517                         RtlRightChild(RtlParent(G)) = N;
 518                     }
 519                 }
 520
 521                 /* Now N is on top, so P has become its child. */
 522                 RtlRightChild(N) = P;
 523                 RtlParent(P) = N;
 524
 525                 /* N is on top, P is its child, so G is grandchild. */
 526                 RtlRightChild(P) = G;
 527                 RtlParent(G) = P;
 528             }
 529             /* Case 3: P is the right child of G */
 530             else if (RtlIsRightChild(P))
 531             {
 532                 /*
 533                  * N's left-child becomes G's right child and
 534                  * N's right-child becomes P's left child.
 535                  */
 536                 RtlRightChild(G) = RtlLeftChild(N);
 537                 RtlLeftChild(P) = RtlRightChild(N);
 538
 539                 /*
 540                  * If they exist, update their parent pointers too,
 541                  * since they've changed trees.
 542                  */
 543                 if (RtlRightChild(G)) RtlParent(RtlRightChild(G)) = G;
 544                 if (RtlLeftChild(P)) RtlParent(RtlLeftChild(P)) = P;
 545
 546                 /*
 547                  * Now we'll shove N all the way to the top.
 548                  * Check if G is the root first.
 549                  */
 550                 if (RtlIsRoot(G))
 551                 {
 552                     /* G doesn't have a parent, so N will become the root! */
 553                     RtlParent(N) = N;
 554                 }
 555                 else
 556                 {
 557                     /* G has a parent, so inherit it since we take G's place */
 558                     RtlParent(N) = RtlParent(G);
 559
 560                     /*
 561                      * Now find out who was referencing G and have it reference
 562                      * N instead, since we're taking G's place.
 563                      */
 564                     if (RtlIsLeftChild(G))
 565                     {
 566                         /*
 567                          * G was a left child, so change its parent's left
 568                          * child link to point to N now.
 569                          */
 570                         RtlLeftChild(RtlParent(G)) = N;
 571                     }
 572                     else
 573                     {
 574                         /*
 575                          * G was a right child, so change its parent's right
 576                          * child link to point to N now.
 577                          */
 578                         RtlRightChild(RtlParent(G)) = N;
 579                     }
 580                 }
 581
 582                 /* Now N is on top, so G has become its left child. */
 583                 RtlLeftChild(N) = G;
 584                 RtlParent(G) = N;
 585
 586                 /* N is on top, G is its left child, so P is right child. */
 587                 RtlRightChild(N) = P;
 588                 RtlParent(P) = N;
 589             }
 590             /* "Finally" case: N doesn't have a grandparent => P is root */
 591             else
 592             {
 593                 /* P's left-child becomes N's right child */
 594                 RtlLeftChild(P) = RtlRightChild(N);
 595
 596                 /* If it exists, update its parent pointer too */
 597                 if (RtlLeftChild(P)) RtlParent(RtlLeftChild(P)) = P;
 598
 599                 /* Now make N the root, no need to worry about references */
 600                 N->Parent = N;
 601
 602                 /* And make P its right child */
 603                 N->RightChild = P;
 604                 P->Parent = N;
 605             }
 606         }
 607         /* Case 2 & 4: N is right child of P */
 608         else
 609         {
 610             /* Case 2: P is the right child of G */
 611             if (RtlIsRightChild(P))
 612             {
 613                 /*
 614                  * P's left-child becomes G's right child and
 615                  * N's left-child becomes P's right child.
 616                  */
 617                 RtlRightChild(G) = RtlLeftChild(P);
 618                 RtlRightChild(P) = RtlLeftChild(N);
 619
 620                 /*
 621                  * If they exist, update their parent pointers too,
 622                  * since they've changed trees.
 623                  */
 624                 if (RtlRightChild(G)) RtlParent(RtlRightChild(G)) = G;
 625                 if (RtlRightChild(P)) RtlParent(RtlRightChild(P)) = P;
 626
 627                 /*
 628                  * Now we'll shove N all the way to the top.
 629                  * Check if G is the root first.
 630                  */
 631                 if (RtlIsRoot(G))
 632                 {
 633                     /* G doesn't have a parent, so N will become the root! */
 634                     RtlParent(N) = N;
 635                 }
 636                 else
 637                 {
 638                     /* G has a parent, so inherit it since we take G's place */
 639                     RtlParent(N) = RtlParent(G);
 640
 641                     /*
 642                      * Now find out who was referencing G and have it reference
 643                      * N instead, since we're taking G's place.
 644                      */
 645                     if (RtlIsLeftChild(G))
 646                     {
 647                         /*
 648                          * G was a left child, so change its parent's left
 649                          * child link to point to N now.
 650                          */
 651                         RtlLeftChild(RtlParent(G)) = N;
 652                     }
 653                     else
 654                     {
 655                         /*
 656                          * G was a right child, so change its parent's right
 657                          * child link to point to N now.
 658                          */
 659                         RtlRightChild(RtlParent(G)) = N;
 660                     }
 661                 }
 662
 663                 /* Now N is on top, so P has become its child. */
 664                 RtlLeftChild(N) = P;
 665                 RtlParent(P) = N;
 666
 667                 /* N is on top, P is its child, so G is grandchild. */
 668                 RtlLeftChild(P) = G;
 669                 RtlParent(G) = P;
 670             }
 671             /* Case 4: P is the left child of G */
 672             else if (RtlIsLeftChild(P))
 673             {
 674                 /*
 675                  * N's left-child becomes G's right child and
 676                  * N's right-child becomes P's left child.
 677                  */
 678                 RtlRightChild(P) = RtlLeftChild(N);
 679                 RtlLeftChild(G) = RtlRightChild(N);
 680
 681                 /*
 682                  * If they exist, update their parent pointers too,
 683                  * since they've changed trees.
 684                  */
 685                 if (RtlRightChild(P)) RtlParent(RtlRightChild(P)) = P;
 686                 if (RtlLeftChild(G)) RtlParent(RtlLeftChild(G)) = G;
 687
 688                 /*
 689                  * Now we'll shove N all the way to the top.
 690                  * Check if G is the root first.
 691                  */
 692                 if (RtlIsRoot(G))
 693                 {
 694                     /* G doesn't have a parent, so N will become the root! */
 695                     RtlParent(N) = N;
 696                 }
 697                 else
 698                 {
 699                     /* G has a parent, so inherit it since we take G's place */
 700                     RtlParent(N) = RtlParent(G);
 701
 702                     /*
 703                      * Now find out who was referencing G and have it reference
 704                      * N instead, since we're taking G's place.
 705                      */
 706                     if (RtlIsLeftChild(G))
 707                     {
 708                         /*
 709                          * G was a left child, so change its parent's left
 710                          * child link to point to N now.
 711                          */
 712                         RtlLeftChild(RtlParent(G)) = N;
 713                     }
 714                     else
 715                     {
 716                         /*
 717                          * G was a right child, so change its parent's right
 718                          * child link to point to N now.
 719                          */
 720                         RtlRightChild(RtlParent(G)) = N;
 721                     }
 722                 }
 723
 724                 /* Now N is on top, so P has become its left child. */
 725                 RtlLeftChild(N) = P;
 726                 RtlParent(G) = N;
 727
 728                 /* N is on top, P is its left child, so G is right child. */
 729                 RtlRightChild(N) = G;
 730                 RtlParent(P) = N;
 731             }
 732             /* "Finally" case: N doesn't have a grandparent => P is root */
 733             else
 734             {
 735                 /* P's right-child becomes N's left child */
 736                 RtlRightChild(P) = RtlLeftChild(N);
 737
 738                 /* If it exists, update its parent pointer too */
 739                 if (RtlRightChild(P)) RtlParent(RtlRightChild(P)) = P;
 740
 741                 /* Now make N the root, no need to worry about references */
 742                 N->Parent = N;
 743
 744                 /* And make P its left child */
 745                 N->LeftChild = P;
 746                 P->Parent = N;
 747             }
 748         }
 749     }
 750
 751     /* Return the root entry */
 752     ASSERT(RtlIsRoot(N));
 753     return N;
 754 }
 755
 756 /*
 757  * @implemented
 758  */
 759 PRTL_SPLAY_LINKS
 760 NTAPI
 761 RtlSubtreePredecessor(IN PRTL_SPLAY_LINKS Links)
 762 {
 763     PRTL_SPLAY_LINKS Child;
 764
 765     /* Get the left child */
 766     Child = RtlLeftChild(Links);
 767     if (!Child) return NULL;
 768
 769     /* Get right-most child */
 770     while (RtlRightChild(Child)) Child = RtlRightChild(Child);
 771
 772     /* Return it */
 773     return Child;
 774 }
 775
 776 /*
 777  * @implemented
 778  */
 779 PRTL_SPLAY_LINKS
 780 NTAPI
 781 RtlSubtreeSuccessor(IN PRTL_SPLAY_LINKS Links)
 782 {
 783     PRTL_SPLAY_LINKS Child;
 784
 785     /* Get the right child */
 786     Child = RtlRightChild(Links);
 787     if (!Child) return NULL;
 788
 789     /* Get left-most child */
 790     while (RtlLeftChild(Child)) Child = RtlLeftChild(Child);
 791
 792     /* Return it */
 793     return Child;
 794 }
 795
 796 /* EOF */