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