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 */ 797