gcc/splay-tree-utils.tcc

   1 // Splay tree utilities                                             -*- C++ -*-
   2 // Copyright (C) 2020-2021 Free Software Foundation, Inc.
   3 //
   4 // This file is part of GCC.
   5 //
   6 // GCC is free software; you can redistribute it and/or modify it under
   7 // the terms of the GNU General Public License as published by the Free
   8 // Software Foundation; either version 3, or (at your option) any later
   9 // version.
  10 //
  11 // GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 // WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 // FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 // for more details.
  15 //
  16 // You should have received a copy of the GNU General Public License
  17 // along with GCC; see the file COPYING3.  If not see
  18 // <http://www.gnu.org/licenses/>.
  19
  20 // INDEX is either 0 or 1.  If it is 0, return NODE's left child,
  21 // otherwise return NODE's right child.
  22 template<typename Accessors>
  23 inline typename base_splay_tree<Accessors>::node_type
  24 base_splay_tree<Accessors>::get_child (node_type node, unsigned int index)
  25 {
  26   return Accessors::child (node, index);
  27 }
  28
  29 // INDEX is either 0 or 1.  If it is 0, change NODE's left child to CHILD,
  30 // otherwise change NODE's right child to CHILD.  If CHILD has a parent
  31 // field, record that its parent is now NODE.
  32 template<typename Accessors>
  33 inline void
  34 base_splay_tree<Accessors>::set_child (node_type node, unsigned int index,
  35                                        node_type child)
  36 {
  37   Accessors::child (node, index) = child;
  38   if (child)
  39     set_parent (child, node);
  40 }
  41
  42 // Rotate the tree to promote child number INDEX of NODE, so that that
  43 // child becomes a parent of NODE.  Return the promoted node.
  44 //
  45 // The caller has the responsibility of assigning a correct parent
  46 // to the returned node.
  47 template<typename Accessors>
  48 inline typename base_splay_tree<Accessors>::node_type
  49 base_splay_tree<Accessors>::promote_child (node_type node, unsigned int index)
  50 {
  51   node_type promoted = get_child (node, index);
  52   set_child (node, index, get_child (promoted, 1 - index));
  53   set_child (promoted, 1 - index, node);
  54   return promoted;
  55 }
  56
  57 // Treat child number INDEX of NODE as being CHILD and rotate the tree
  58 // so that CHILD becomes a parent of NODE.
  59 //
  60 // The caller has the responsibility of assigning a correct parent to CHILD.
  61 template<typename Accessors>
  62 inline void
  63 base_splay_tree<Accessors>::promote_child (node_type node, unsigned int index,
  64                                            node_type child)
  65 {
  66   set_child (node, index, get_child (child, 1 - index));
  67   set_child (child, 1 - index, node);
  68 }
  69
  70 // Print NODE to PP, using PRINTER (PP, N) to print the contents of node N.
  71 // Prefix each new line with INDENT_STRING.  CODE is 'T' if NODE is the root
  72 // node, 'L' if NODE is the left child of its parent, or 'R' if NODE is the
  73 // right child of its parent.
  74 template<typename Accessors>
  75 template<typename Printer>
  76 void
  77 base_splay_tree<Accessors>::print (pretty_printer *pp, node_type node,
  78                                    Printer printer, char code,
  79                                    vec<char> &indent_string)
  80 {
  81   // In the comments below, PREFIX refers to the incoming contents
  82   // of INDENT_STRING.
  83   node_type left = get_child (node, 0);
  84   node_type right = get_child (node, 1);
  85
  86   auto orig_indent_len = indent_string.length ();
  87   indent_string.safe_grow (orig_indent_len + 3);
  88   char *extra_indent = indent_string.address () + orig_indent_len;
  89
  90   // Print [T], [L], or [R].
  91   extra_indent[0] = '[';
  92   extra_indent[1] = code;
  93   extra_indent[2] = ']';
  94   pp_append_text (pp, extra_indent, indent_string.end ());
  95   pp_space (pp);
  96
  97   // Print the node itself, using PREFIX + " | " or PREFIX + "   " to indent
  98   // new lines under the "[_]" that we just printed.
  99   extra_indent[0] = ' ';
 100   extra_indent[1] = (left || right ? '|' : ' ');
 101   extra_indent[2] = ' ';
 102   {
 103     pretty_printer sub_pp;
 104     printer (&sub_pp, node);
 105     const char *text = pp_formatted_text (&sub_pp);
 106     while (const char *end = strchr (text, '\n'))
 107       {
 108         pp_append_text (pp, text, end);
 109         pp_newline_and_indent (pp, 0);
 110         pp_append_text (pp, indent_string.begin (), indent_string.end ());
 111         text = end + 1;
 112       }
 113     pp_string (pp, text);
 114   }
 115
 116   if (left)
 117     {
 118       // Print PREFIX + " +-" for the first line of the left subtree,
 119       // to be followed by "[L]".
 120       extra_indent[1] = '+';
 121       extra_indent[2] = '-';
 122       pp_newline_and_indent (pp, 0);
 123       pp_append_text (pp, indent_string.begin (), indent_string.end ());
 124
 125       // Print the left subtree, using PREFIX + " | " or PREFIX + "   "
 126       // to indent under the PREFIX + " +-" that we just printed.
 127       extra_indent[1] = right ? '|' : ' ';
 128       extra_indent[2] = ' ';
 129       print (pp, left, printer, 'L', indent_string);
 130       extra_indent = indent_string.address () + orig_indent_len;
 131
 132       // If LEFT is not a leaf and we also have a right subtree, use a
 133       // PREFIX + " |" line to separate them.
 134       if (right && (get_child (left, 0) || get_child (left, 1)))
 135         {
 136           pp_newline_and_indent (pp, 0);
 137           pp_append_text (pp, indent_string.begin (), &extra_indent[2]);
 138         }
 139     }
 140   if (right)
 141     {
 142       // Print PREFIX + " +-" for the first line of the right subtree,
 143       // to be followed by "[R]".
 144       extra_indent[1] = '+';
 145       extra_indent[2] = '-';
 146       pp_newline_and_indent (pp, 0);
 147       pp_append_text (pp, indent_string.begin (), indent_string.end ());
 148
 149       // Print the right subtree, using PREFIX + "   " to indent under the
 150       // PREFIX + " +-" that we just printed.
 151       extra_indent[1] = ' ';
 152       extra_indent[2] = ' ';
 153       print (pp, right, printer, 'R', indent_string);
 154     }
 155   indent_string.truncate (orig_indent_len);
 156 }
 157
 158 // See the comment above the declaration.
 159 template<typename Accessors>
 160 template<typename Printer>
 161 void
 162 base_splay_tree<Accessors>::print (pretty_printer *pp, node_type node,
 163                                    Printer printer)
 164 {
 165   if (!node)
 166     {
 167       pp_string (pp, "null");
 168       return;
 169     }
 170   auto_vec<char, 64> indent_string;
 171   print (pp, node, printer, 'T', indent_string);
 172 }
 173
 174 // If N is 1, splay the last (rightmost) node reachable from START
 175 // to the position that START current holds and return the splayed node.
 176 // START is not itself the last node.
 177 //
 178 // If N is 0, splay the first (leftmost) node reachable from START
 179 // to the position that START current holds and return the splayed node.
 180 // START is not itself the first node.
 181 //
 182 // The caller has the responsibility of updating the parent of the
 183 // returned node.
 184 template<typename Accessors>
 185 template<unsigned int N>
 186 typename base_splay_tree<Accessors>::node_type
 187 base_splay_tree<Accessors>::splay_limit (node_type start)
 188 {
 189   // This essentially follows the simpilfied top-down method described
 190   // in Sleator and Tarjan's "Self-adjusting Binary Search Trees", but
 191   // specialized for the case in which the comparison result is fixed.
 192   // The first iteration is peeled to avoid the need for stack temporaries.
 193   //
 194   // The comments and names reflect the behavior for N == 1, but the
 195   // N == 0 case behaves analogously.
 196
 197   // Rotate the tree to promote the right child of START to the root.
 198   node_type node = promote_child (start, N);
 199   if (node_type right = get_child (node, N))
 200     {
 201       // Perform the link left step, which for this first iteration
 202       // means making NODE the root of the left tree.
 203       //
 204       // NODE will become left child of the final node.  For a right
 205       // spine starting at NODE of the form:
 206       //
 207       //  1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> ... -> N
 208       //  |    |    |    |    |    |    |           |
 209       //  V    V    V    V    V    V    V           V
 210       //  A    B    C    D    E    F    G           NL
 211       //
 212       // the next step is to create a subtree of N whose right spine contains
 213       // the odd-numbered nodes, as follows:
 214       //
 215       //  N
 216       //  |
 217       //  V
 218       //  1 ------> 3 ------> 5 ------> 7 -> .... -> NL
 219       //  |         |         |         |
 220       //  V         V         V         V
 221       //  A         2 -> C    4 -> E    6 -> G
 222       //            |         |         |
 223       //            V         V         V
 224       //            B         D         F
 225       //
 226       // First record 1 as the left child of the final root (N) and move
 227       // on to node 2.
 228       node_type final_child = node;
 229       node_type new_spine_end = node;
 230       node = right;
 231       while (node_type right = get_child (node, N))
 232         {
 233           // Perform another rotate left step.
 234           //
 235           // We've built the tree rooted at 1 in the diagram above up to,
 236           // but not including, an even-numbered node NODE on the original
 237           // right spine.  Rotate the tree at NODE to promote the following
 238           // odd-numbered node.
 239           promote_child (node, N, right);
 240           node = right;
 241           if (node_type right = get_child (node, N))
 242             {
 243               // Perform another link left step.
 244               //
 245               // Add the promoted odd-numbered node to the right spine of the
 246               // tree rooted at 1 and move on to the next even-numbered node.
 247               set_child (new_spine_end, N, node);
 248               new_spine_end = node;
 249               node = right;
 250             }
 251         }
 252       // Perform the assembly step.
 253       //
 254       // Add NL to the new spine and make N the new root.
 255       set_child (new_spine_end, N, get_child (node, 1 - N));
 256       set_child (node, 1 - N, final_child);
 257     }
 258   return node;
 259 }
 260
 261 // Remove NODE from its position in the splay tree.  If NODE has at least
 262 // one child node, return the node that should now hold NODE's position in
 263 // the splay tree.  If NODE has no children, return null.
 264 //
 265 // The caller has the responsibility of updating the parent of the
 266 // returned node.
 267 template<typename Accessors>
 268 inline typename base_splay_tree<Accessors>::node_type
 269 base_splay_tree<Accessors>::remove_node_internal (node_type node)
 270 {
 271   node_type left = get_child (node, 0);
 272   node_type right = get_child (node, 1);
 273   if (!left)
 274     return right;
 275
 276   if (!right)
 277     return left;
 278
 279   if (get_child (left, 1))
 280     {
 281       left = splay_limit<1> (left);
 282       gcc_checking_assert (!get_child (left, 1));
 283     }
 284   set_child (left, 1, right);
 285   return left;
 286 }
 287
 288 // See the comment above the declaration.
 289 template<typename Accessors>
 290 inline void
 291 base_splay_tree<Accessors>::insert_child (node_type node, unsigned int index,
 292                                           node_type child)
 293 {
 294   gcc_checking_assert (!get_child (child, 0) && !get_child (child, 1));
 295   set_child (child, index, get_child (node, index));
 296   set_child (node, index, child);
 297 }
 298
 299 // Implement splay_next_node if N == 1 and splay_prev_node if N == 0.
 300 template<typename Accessors>
 301 template<unsigned int N>
 302 bool
 303 rooted_splay_tree<Accessors>::splay_neighbor ()
 304 {
 305   node_type node = m_root;
 306   node_type new_root = get_child (node, N);
 307   if (!new_root)
 308     return false;
 309
 310   if (get_child (new_root, 1 - N))
 311     {
 312       // NEW_ROOT is not itself the required node, so splay the required
 313       // node into its place.
 314       new_root = parent::template splay_limit<1 - N> (new_root);
 315       gcc_checking_assert (!get_child (new_root, 1 - N));
 316       set_child (node, N, node_type ());
 317       set_child (new_root, 1 - N, node);
 318     }
 319   else
 320     promote_child (node, N, new_root);
 321   set_parent (new_root, node_type ());
 322   m_root = new_root;
 323   return true;
 324 }
 325
 326 // See the comment above the declaration.
 327 template<typename Accessors>
 328 template<typename Comparator>
 329 bool
 330 rooted_splay_tree<Accessors>::insert (node_type new_node, Comparator compare)
 331 {
 332   gcc_checking_assert (!get_child (new_node, 0) && !get_child (new_node, 1));
 333   if (!m_root)
 334     {
 335       m_root = new_node;
 336       return true;
 337     }
 338
 339   int comparison = lookup (compare);
 340   if (comparison == 0)
 341     return false;
 342
 343   // Insert NEW_NODE before M_ROOT if COMPARISON < 0 and after M_ROOT
 344   // otherwise.
 345   set_child (new_node, comparison < 0, m_root);
 346   set_child (new_node, comparison > 0, get_child (m_root, comparison > 0));
 347   set_child (m_root, comparison > 0, nullptr);
 348   m_root = new_node;
 349   return true;
 350 }
 351
 352 // See the comment above the declaration.
 353 template<typename Accessors>
 354 inline void
 355 rooted_splay_tree<Accessors>::insert_max_node (node_type new_node)
 356 {
 357   gcc_checking_assert (!get_child (new_node, 0) && !get_child (new_node, 1));
 358   set_child (new_node, 0, m_root);
 359   m_root = new_node;
 360 }
 361
 362 // See the comment above the declaration.
 363 template<typename Accessors>
 364 inline void
 365 rooted_splay_tree<Accessors>::splice_next_tree (rooted_splay_tree next_tree)
 366 {
 367   splay_max_node ();
 368   set_child (m_root, 1, next_tree.m_root);
 369 }
 370
 371 // See the comment above the declaration.
 372 template<typename Accessors>
 373 inline void
 374 rooted_splay_tree<Accessors>::replace_max_node_at_root (node_type new_node)
 375 {
 376   node_type old_node = m_root;
 377   gcc_checking_assert (!get_child (new_node, 0)
 378                        && !get_child (new_node, 1)
 379                        && !get_child (old_node, 1));
 380   set_child (new_node, 0, get_child (old_node, 0));
 381   // Clear the links from OLD_NODE.  Its parent and right child are
 382   // already node_type ().
 383   set_child (old_node, 0, node_type ());
 384   m_root = new_node;
 385 }
 386
 387 // See the comment above the declaration.
 388 template<typename Accessors>
 389 inline void
 390 rooted_splay_tree<Accessors>::remove_root ()
 391 {
 392   node_type node = m_root;
 393   m_root = parent::remove_node_internal (node);
 394   if (m_root)
 395     set_parent (m_root, node_type ());
 396   // Clear the links from NODE.  Its parent is already node_type ().
 397   set_child (node, 0, node_type ());
 398   set_child (node, 1, node_type ());
 399 }
 400
 401 // See the comment above the declaration.
 402 template<typename Accessors>
 403 inline rooted_splay_tree<Accessors>
 404 rooted_splay_tree<Accessors>::split_before_root ()
 405 {
 406   node_type new_root = get_child (m_root, 0);
 407   set_child (m_root, 0, node_type ());
 408   set_parent (new_root, node_type ());
 409   return new_root;
 410 }
 411
 412 // See the comment above the declaration.
 413 template<typename Accessors>
 414 inline rooted_splay_tree<Accessors>
 415 rooted_splay_tree<Accessors>::split_after_root ()
 416 {
 417   node_type new_root = get_child (m_root, 1);
 418   set_child (m_root, 1, node_type ());
 419   set_parent (new_root, node_type ());
 420   return new_root;
 421 }
 422
 423 // See the comment above the declaration.
 424 template<typename Accessors>
 425 inline bool
 426 rooted_splay_tree<Accessors>::splay_prev_node ()
 427 {
 428   return splay_neighbor<0> ();
 429 }
 430
 431 // See the comment above the declaration.
 432 template<typename Accessors>
 433 inline bool
 434 rooted_splay_tree<Accessors>::splay_next_node ()
 435 {
 436   return splay_neighbor<1> ();
 437 }
 438
 439 // See the comment above the declaration.
 440 template<typename Accessors>
 441 inline void
 442 rooted_splay_tree<Accessors>::splay_min_node ()
 443 {
 444   if (m_root && get_child (m_root, 0))
 445     {
 446       m_root = parent::template splay_limit<0> (m_root);
 447       set_parent (m_root, node_type ());
 448     }
 449 }
 450
 451 // See the comment above the declaration.
 452 template<typename Accessors>
 453 inline void
 454 rooted_splay_tree<Accessors>::splay_max_node ()
 455 {
 456   if (m_root && get_child (m_root, 1))
 457     {
 458       m_root = parent::template splay_limit<1> (m_root);
 459       set_parent (m_root, node_type ());
 460     }
 461 }
 462
 463 // See the comment above the declaration.
 464 template<typename Accessors>
 465 inline typename rooted_splay_tree<Accessors>::node_type
 466 rooted_splay_tree<Accessors>::min_node ()
 467 {
 468   splay_min_node ();
 469   return m_root;
 470 }
 471
 472 // See the comment above the declaration.
 473 template<typename Accessors>
 474 inline typename rooted_splay_tree<Accessors>::node_type
 475 rooted_splay_tree<Accessors>::max_node ()
 476 {
 477   splay_max_node ();
 478   return m_root;
 479 }
 480
 481 // See the comment above the declaration.
 482 template<typename Accessors>
 483 template<typename Comparator>
 484 auto
 485 rooted_splay_tree<Accessors>::lookup (Comparator compare)
 486   -> decltype (compare (m_root))
 487 {
 488   // This essentially follows the simpilfied top-down method described
 489   // in Sleator and Tarjan's "Self-adjusting Binary Search Trees", but
 490   // with the complication that the comparisons are done only once.
 491   using result_type = decltype (compare (m_root));
 492
 493   // The roots of the left and right trees.
 494   node_type link_left_root = node_type ();
 495   node_type link_right_root = node_type ();
 496
 497   // Where to add new nodes to the left and right trees.
 498   node_type *link_left_ptr = &link_left_root;
 499   node_type *link_right_ptr = &link_right_root;
 500
 501   // The nodes that contain *LINK_LEFT_PTR and *LINK_RIGHT_PTR,
 502   // once they no longer point to the roots above.
 503   node_type link_left_parent = node_type ();
 504   node_type link_right_parent = node_type ();
 505
 506   auto link_left = [&](node_type node)
 507     {
 508       *link_left_ptr = node;
 509       link_left_ptr = &Accessors::child (node, 1);
 510       set_parent (node, link_left_parent);
 511       link_left_parent = node;
 512     };
 513
 514   auto link_right = [&](node_type node)
 515     {
 516       *link_right_ptr = node;
 517       link_right_ptr = &Accessors::child (node, 0);
 518       set_parent (node, link_right_parent);
 519       link_right_parent = node;
 520     };
 521
 522   node_type node = m_root;
 523   node_type parent = node_type ();
 524   result_type result;
 525   result_type old_result = 0;
 526   while (1)
 527     {
 528       // OLD_RESULT is 0 if NODE is the root of the middle tree.
 529       // Otherwise, PARENT is the root of the middle tree and OLD_RESULT
 530       // is how it compared.
 531       //
 532       // Results are:
 533       // < 0 if we want something smaller.
 534       // = 0 if we found the right node.
 535       // > 0 if we want something bigger.
 536       result = compare (node);
 537       if (old_result < 0)
 538         {
 539           if (result < 0)
 540             {
 541               // SEARCH < NODE < PARENT
 542               //
 543               // Promote NODE (rotate right).
 544               promote_child (parent, 0, node);
 545               node_type next = get_child (node, 0);
 546               if (!next)
 547                 break;
 548
 549               link_right (node);
 550
 551               // NEXT is now the root of the middle tree.
 552               node = next;
 553               old_result = 0;
 554               continue;
 555             }
 556
 557           // SEARCH >= NODE, NODE < PARENT
 558           link_right (parent);
 559         }
 560       else if (old_result > 0)
 561         {
 562           if (result > 0)
 563             {
 564               // SEARCH > NODE > PARENT
 565               //
 566               // Promote NODE (rotate left).
 567               promote_child (parent, 1, node);
 568               node_type next = get_child (node, 1);
 569               if (!next)
 570                 break;
 571
 572               link_left (node);
 573
 574               // NEXT is now the root of the middle tree.
 575               node = next;
 576               old_result = 0;
 577               continue;
 578             }
 579
 580           // SEARCH <= NODE, NODE > PARENT
 581           link_left (parent);
 582         }
 583
 584       // Microoptimization to allow NODE to be read even if RESULT == 0.
 585       node_type next = get_child (node, result >= 0);
 586       if (result == 0 || !next)
 587         break;
 588
 589       // NODE is now the root of the tree.
 590       parent = node;
 591       node = next;
 592       old_result = result;
 593     }
 594
 595   node_type new_left = link_left_root;
 596   node_type new_right = link_right_root;
 597
 598   if (new_left)
 599     {
 600       node_type old_left = get_child (node, 0);
 601       *link_left_ptr = old_left;
 602       if (old_left)
 603         set_parent (old_left, link_left_parent);
 604       set_child (node, 0, new_left);
 605     }
 606
 607   if (new_right)
 608     {
 609       node_type old_right = get_child (node, 1);
 610       *link_right_ptr = old_right;
 611       if (old_right)
 612         set_parent (old_right, link_right_parent);
 613       set_child (node, 1, new_right);
 614     }
 615
 616   set_parent (node, node_type ());
 617   m_root = node;
 618   return result;
 619 }
 620
 621 // See the comment above the declaration.
 622 template<typename Accessors>
 623 template<typename LeftPredicate, typename RightPredicate>
 624 int
 625 rooted_splay_tree<Accessors>::lookup (LeftPredicate want_something_smaller,
 626                                       RightPredicate want_something_bigger)
 627 {
 628   // This essentially follows the simpilfied top-down method described
 629   // in Sleator and Tarjan's "Self-adjusting Binary Search Trees"
 630   // (and follows it more closely than the single-comparator version above).
 631
 632   // The roots of the left and right trees.
 633   node_type link_left_root = node_type ();
 634   node_type link_right_root = node_type ();
 635
 636   // Where to add new nodes to the left and right trees.
 637   node_type *link_left_ptr = &link_left_root;
 638   node_type *link_right_ptr = &link_right_root;
 639
 640   // The nodes that contain *LINK_LEFT_PTR and *LINK_RIGHT_PTR,
 641   // once they no longer point to the roots above.
 642   node_type link_left_parent = node_type ();
 643   node_type link_right_parent = node_type ();
 644
 645   node_type node = m_root;
 646   int result;
 647   for (;;)
 648     {
 649       // NODE is the root of the middle tree.
 650       if (want_something_smaller (node))
 651         {
 652           result = -1;
 653           node_type next = get_child (node, 0);
 654           if (!next)
 655             break;
 656
 657           if (want_something_smaller (next))
 658             {
 659               // Promote NODE (rotate right).
 660               promote_child (node, 0, next);
 661               node = next;
 662               next = get_child (node, 0);
 663               if (!next)
 664                 break;
 665             }
 666
 667           // Add NODE to the right tree (link right).
 668           *link_right_ptr = node;
 669           link_right_ptr = &Accessors::child (node, 0);
 670           set_parent (node, link_right_parent);
 671           link_right_parent = node;
 672
 673           node = next;
 674         }
 675       else if (want_something_bigger (node))
 676         {
 677           result = 1;
 678           node_type next = get_child (node, 1);
 679           if (!next)
 680             break;
 681
 682           if (want_something_bigger (next))
 683             {
 684               // Promote NODE (rotate left).
 685               promote_child (node, 1, next);
 686               node = next;
 687               next = get_child (node, 1);
 688               if (!next)
 689                 break;
 690             }
 691
 692           // Add NODE to the left tree (link left).
 693           *link_left_ptr = node;
 694           link_left_ptr = &Accessors::child (node, 1);
 695           set_parent (node, link_left_parent);
 696           link_left_parent = node;
 697
 698           node = next;
 699         }
 700       else
 701         {
 702           result = 0;
 703           break;
 704         }
 705     }
 706
 707   node_type new_left = link_left_root;
 708   node_type new_right = link_right_root;
 709
 710   if (new_left)
 711     {
 712       node_type old_left = get_child (node, 0);
 713       *link_left_ptr = old_left;
 714       if (old_left)
 715         set_parent (old_left, link_left_parent);
 716       set_child (node, 0, new_left);
 717     }
 718
 719   if (new_right)
 720     {
 721       node_type old_right = get_child (node, 1);
 722       *link_right_ptr = old_right;
 723       if (old_right)
 724         set_parent (old_right, link_right_parent);
 725       set_child (node, 1, new_right);
 726     }
 727
 728   set_parent (node, node_type ());
 729   m_root = node;
 730   return result;
 731 }
 732
 733 // See the comment above the declaration.
 734 template<typename Accessors>
 735 template<typename Printer>
 736 inline void
 737 rooted_splay_tree<Accessors>::print (pretty_printer *pp, Printer printer) const
 738 {
 739   print (pp, m_root, printer);
 740 }
 741
 742 // Return NODE's current parent.
 743 template<typename Accessors>
 744 inline typename rootless_splay_tree<Accessors>::node_type
 745 rootless_splay_tree<Accessors>::get_parent (node_type node)
 746 {
 747   return Accessors::parent (node);
 748 }
 749
 750 // CHILD is known to be a child of PARENT.  Return which index it has.
 751 template<typename Accessors>
 752 inline unsigned int
 753 rootless_splay_tree<Accessors>::child_index (node_type parent, node_type child)
 754 {
 755   return get_child (parent, 1) == child;
 756 }
 757
 758 // If N == 1, implement splay_known_max_node, otherwise implement
 759 // splay_known_min_node.
 760 template<typename Accessors>
 761 template<unsigned int N>
 762 inline void
 763 rootless_splay_tree<Accessors>::splay_known_limit (node_type node)
 764 {
 765   node_type child = node;
 766   node_type parent = get_parent (child);
 767   if (!parent)
 768     return;
 769
 770   do
 771     // At this point, NODE conceptually replaces CHILD as a child of
 772     // PARENT, but we haven't yet updated PARENT accordingly.
 773     if (node_type grandparent = get_parent (parent))
 774       {
 775         node_type greatgrandparent = get_parent (grandparent);
 776         promote_child (grandparent, N, parent);
 777         promote_child (parent, N, node);
 778         child = grandparent;
 779         parent = greatgrandparent;
 780       }
 781     else
 782       {
 783         promote_child (parent, N, node);
 784         break;
 785       }
 786   while (parent);
 787   set_parent (node, node_type ());
 788 }
 789
 790 // See the comment above the declaration.
 791 template<typename Accessors>
 792 typename rootless_splay_tree<Accessors>::node_type
 793 rootless_splay_tree<Accessors>::remove_node (node_type node)
 794 {
 795   node_type replacement = parent::remove_node_internal (node);
 796   if (node_type parent = get_parent (node))
 797     set_child (parent, child_index (parent, node), replacement);
 798   else if (replacement)
 799     set_parent (replacement, node_type ());
 800   // Clear the links from NODE.
 801   set_parent (node, node_type ());
 802   set_child (node, 0, node_type ());
 803   set_child (node, 1, node_type ());
 804   return replacement;
 805 }
 806
 807 // See the comment above the declaration.
 808 template<typename Accessors>
 809 void
 810 rootless_splay_tree<Accessors>::splay (node_type node)
 811 {
 812   node_type child = node;
 813   node_type parent = get_parent (child);
 814   if (!parent)
 815     return;
 816
 817   do
 818     {
 819       // At this point, NODE conceptually replaces CHILD as a child of
 820       // PARENT, but we haven't yet updated PARENT accordingly.
 821       unsigned int index = child_index (parent, child);
 822       if (node_type grandparent = get_parent (parent))
 823         {
 824           node_type greatgrandparent = get_parent (grandparent);
 825           unsigned int parent_index = child_index (grandparent, parent);
 826           if (index == parent_index)
 827             {
 828               promote_child (grandparent, parent_index, parent);
 829               promote_child (parent, index, node);
 830             }
 831           else
 832             {
 833               promote_child (parent, index, node);
 834               promote_child (grandparent, parent_index, node);
 835             }
 836           child = grandparent;
 837           parent = greatgrandparent;
 838         }
 839       else
 840         {
 841           promote_child (parent, index, node);
 842           break;
 843         }
 844     }
 845   while (parent);
 846   set_parent (node, node_type ());
 847 }
 848
 849 // See the comment above the declaration.
 850 template<typename Accessors>
 851 inline void
 852 rootless_splay_tree<Accessors>::splay_known_min_node (node_type node)
 853 {
 854   splay_known_limit<0> (node);
 855 }
 856
 857 // See the comment above the declaration.
 858 template<typename Accessors>
 859 inline void
 860 rootless_splay_tree<Accessors>::splay_known_max_node (node_type node)
 861 {
 862   splay_known_limit<1> (node);
 863 }
 864
 865 // See the comment above the declaration.
 866 template<typename Accessors>
 867 template<typename DefaultResult, typename Predicate>
 868 auto
 869 rootless_splay_tree<Accessors>::
 870 splay_and_search (node_type node, DefaultResult default_result,
 871                   Predicate predicate)
 872   -> decltype (predicate (node, 0))
 873 {
 874   using Result = decltype (predicate (node, 0));
 875
 876   node_type child = node;
 877   node_type parent = get_parent (child);
 878   if (!parent)
 879     return default_result;
 880
 881   do
 882     {
 883       // At this point, NODE conceptually replaces CHILD as a child of
 884       // PARENT, but we haven't yet updated PARENT accordingly.
 885       unsigned int index = child_index (parent, child);
 886       if (Result result = predicate (parent, index))
 887         {
 888           set_child (parent, index, node);
 889           return result;
 890         }
 891       if (node_type grandparent = get_parent (parent))
 892         {
 893           node_type greatgrandparent = get_parent (grandparent);
 894           unsigned int parent_index = child_index (grandparent, parent);
 895           if (Result result = predicate (grandparent, parent_index))
 896             {
 897               set_child (parent, index, node);
 898               return result;
 899             }
 900           if (index == parent_index)
 901             {
 902               promote_child (grandparent, parent_index, parent);
 903               promote_child (parent, index, node);
 904             }
 905           else
 906             {
 907               promote_child (parent, index, node);
 908               promote_child (grandparent, parent_index, node);
 909             }
 910           child = grandparent;
 911           parent = greatgrandparent;
 912         }
 913       else
 914         {
 915           promote_child (parent, index, node);
 916           break;
 917         }
 918     }
 919   while (parent);
 920   set_parent (node, node_type ());
 921   return default_result;
 922 }
 923
 924 // Splay NODE1 looking to see if one of its ancestors is NODE2.  If it is,
 925 // return -1 if NODE1 comes before NODE2 or 1 if NODE1 comes after NODE2.
 926 // Return 0 if NODE2 is not an ancestor of NODE1.
 927 template<typename Accessors>
 928 int
 929 rootless_splay_tree<Accessors>::compare_nodes_one_way (node_type node1,
 930                                                        node_type node2)
 931 {
 932   auto compare = [&](node_type parent, unsigned int index) -> int
 933     {
 934       if (parent == node2)
 935         return index ? 1 : -1;
 936       return 0;
 937     };
 938   return splay_and_search (node1, 0, compare);
 939 }
 940
 941 // See the comment above the declaration.
 942 template<typename Accessors>
 943 int
 944 rootless_splay_tree<Accessors>::compare_nodes (node_type node1,
 945                                                node_type node2)
 946 {
 947   if (node1 == node2)
 948     return 0;
 949
 950   // Splay NODE1 looking for NODE2.
 951   int cmp = compare_nodes_one_way (node1, node2);
 952   if (cmp)
 953     return cmp;
 954
 955   // That failed, but NODE1 is now the root of the tree.  Splay NODE2
 956   // to see on which side of NODE1 it falls.
 957   cmp = compare_nodes_one_way (node2, node1);
 958   gcc_checking_assert (cmp);
 959   return -cmp;
 960 }