gcc/splay-tree-utils.tcc

// Splay tree utilities                                             -*- C++ -*-
// Copyright (C) 2020-2024 Free Software Foundation, Inc.
//
// This file is part of GCC.
//
// GCC is free software; you can redistribute it and/or modify it under
// the terms of the GNU General Public License as published by the Free
// Software Foundation; either version 3, or (at your option) any later
// version.
//
// GCC is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
// for more details.
//
// You should have received a copy of the GNU General Public License
// along with GCC; see the file COPYING3.  If not see
// <http://www.gnu.org/licenses/>.

// INDEX is either 0 or 1.  If it is 0, return NODE's left child,
// otherwise return NODE's right child.
template<typename Accessors>
inline typename base_splay_tree<Accessors>::node_type
base_splay_tree<Accessors>::get_child (node_type node, unsigned int index)
{
  return Accessors::child (node, index);
}

// INDEX is either 0 or 1.  If it is 0, change NODE's left child to CHILD,
// otherwise change NODE's right child to CHILD.  If CHILD has a parent
// field, record that its parent is now NODE.
template<typename Accessors>
inline void
base_splay_tree<Accessors>::set_child (node_type node, unsigned int index,
				       node_type child)
{
  Accessors::child (node, index) = child;
  if (child)
    set_parent (child, node);
}

// Rotate the tree to promote child number INDEX of NODE, so that that
// child becomes a parent of NODE.  Return the promoted node.
//
// The caller has the responsibility of assigning a correct parent
// to the returned node.
template<typename Accessors>
inline typename base_splay_tree<Accessors>::node_type
base_splay_tree<Accessors>::promote_child (node_type node, unsigned int index)
{
  node_type promoted = get_child (node, index);
  set_child (node, index, get_child (promoted, 1 - index));
  set_child (promoted, 1 - index, node);
  return promoted;
}

// Treat child number INDEX of NODE as being CHILD and rotate the tree
// so that CHILD becomes a parent of NODE.
//
// The caller has the responsibility of assigning a correct parent to CHILD.
template<typename Accessors>
inline void
base_splay_tree<Accessors>::promote_child (node_type node, unsigned int index,
					   node_type child)
{
  set_child (node, index, get_child (child, 1 - index));
  set_child (child, 1 - index, node);
}

// Print NODE to PP, using PRINTER (PP, N) to print the contents of node N.
// Prefix each new line with INDENT_STRING.  CODE is 'T' if NODE is the root
// node, 'L' if NODE is the left child of its parent, or 'R' if NODE is the
// right child of its parent.
template<typename Accessors>
template<typename Printer>
void
base_splay_tree<Accessors>::print (pretty_printer *pp, node_type node,
				   Printer printer, char code,
				   vec<char> &indent_string)
{
  // In the comments below, PREFIX refers to the incoming contents
  // of INDENT_STRING.
  node_type left = get_child (node, 0);
  node_type right = get_child (node, 1);

  auto orig_indent_len = indent_string.length ();
  indent_string.safe_grow (orig_indent_len + 3);
  char *extra_indent = indent_string.address () + orig_indent_len;

  // Print [T], [L], or [R].
  extra_indent[0] = '[';
  extra_indent[1] = code;
  extra_indent[2] = ']';
  pp_append_text (pp, extra_indent, indent_string.end ());
  pp_space (pp);

  // Print the node itself, using PREFIX + " | " or PREFIX + "   " to indent
  // new lines under the "[_]" that we just printed.
  extra_indent[0] = ' ';
  extra_indent[1] = (left || right ? '|' : ' ');
  extra_indent[2] = ' ';
  {
    pretty_printer sub_pp;
    printer (&sub_pp, node);
    const char *text = pp_formatted_text (&sub_pp);
    while (const char *end = strchr (text, '\n'))
      {
	pp_append_text (pp, text, end);
	pp_newline_and_indent (pp, 0);
	pp_append_text (pp, indent_string.begin (), indent_string.end ());
	text = end + 1;
      }
    pp_string (pp, text);
  }

  if (left)
    {
      // Print PREFIX + " +-" for the first line of the left subtree,
      // to be followed by "[L]".
      extra_indent[1] = '+';
      extra_indent[2] = '-';
      pp_newline_and_indent (pp, 0);
      pp_append_text (pp, indent_string.begin (), indent_string.end ());

      // Print the left subtree, using PREFIX + " | " or PREFIX + "   "
      // to indent under the PREFIX + " +-" that we just printed.
      extra_indent[1] = right ? '|' : ' ';
      extra_indent[2] = ' ';
      print (pp, left, printer, 'L', indent_string);
      extra_indent = indent_string.address () + orig_indent_len;

      // If LEFT is not a leaf and we also have a right subtree, use a
      // PREFIX + " |" line to separate them.
      if (right && (get_child (left, 0) || get_child (left, 1)))
	{
	  pp_newline_and_indent (pp, 0);
	  pp_append_text (pp, indent_string.begin (), &extra_indent[2]);
	}
    }
  if (right)
    {
      // Print PREFIX + " +-" for the first line of the right subtree,
      // to be followed by "[R]".
      extra_indent[1] = '+';
      extra_indent[2] = '-';
      pp_newline_and_indent (pp, 0);
      pp_append_text (pp, indent_string.begin (), indent_string.end ());

      // Print the right subtree, using PREFIX + "   " to indent under the
      // PREFIX + " +-" that we just printed.
      extra_indent[1] = ' ';
      extra_indent[2] = ' ';
      print (pp, right, printer, 'R', indent_string);
    }
  indent_string.truncate (orig_indent_len);
}

// See the comment above the declaration.
template<typename Accessors>
template<typename Printer>
void
base_splay_tree<Accessors>::print (pretty_printer *pp, node_type node,
				   Printer printer)
{
  if (!node)
    {
      pp_string (pp, "null");
      return;
    }
  auto_vec<char, 64> indent_string;
  print (pp, node, printer, 'T', indent_string);
}

// If N is 1, splay the last (rightmost) node reachable from START
// to the position that START current holds and return the splayed node.
// START is not itself the last node.
//
// If N is 0, splay the first (leftmost) node reachable from START
// to the position that START current holds and return the splayed node.
// START is not itself the first node.
//
// The caller has the responsibility of updating the parent of the
// returned node.
template<typename Accessors>
template<unsigned int N>
typename base_splay_tree<Accessors>::node_type
base_splay_tree<Accessors>::splay_limit (node_type start)
{
  // This essentially follows the simpilfied top-down method described
  // in Sleator and Tarjan's "Self-adjusting Binary Search Trees", but
  // specialized for the case in which the comparison result is fixed.
  // The first iteration is peeled to avoid the need for stack temporaries.
  //
  // The comments and names reflect the behavior for N == 1, but the
  // N == 0 case behaves analogously.

  // Rotate the tree to promote the right child of START to the root.
  node_type node = promote_child (start, N);
  if (node_type right = get_child (node, N))
    {
      // Perform the link left step, which for this first iteration
      // means making NODE the root of the left tree.
      //
      // NODE will become left child of the final node.  For a right
      // spine starting at NODE of the form:
      //
      //  1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> ... -> N
      //  |    |    |    |    |    |    |           |
      //  V    V    V    V    V    V    V           V
      //  A    B    C    D    E    F    G           NL
      //
      // the next step is to create a subtree of N whose right spine contains
      // the odd-numbered nodes, as follows:
      //
      //  N
      //  |
      //  V
      //  1 ------> 3 ------> 5 ------> 7 -> .... -> NL
      //  |         |         |         |
      //  V         V         V         V
      //  A         2 -> C    4 -> E    6 -> G
      //            |         |         |
      //            V         V         V
      //            B         D         F
      //
      // First record 1 as the left child of the final root (N) and move
      // on to node 2.
      node_type final_child = node;
      node_type new_spine_end = node;
      node = right;
      while (node_type right = get_child (node, N))
	{
	  // Perform another rotate left step.
	  //
	  // We've built the tree rooted at 1 in the diagram above up to,
	  // but not including, an even-numbered node NODE on the original
	  // right spine.  Rotate the tree at NODE to promote the following
	  // odd-numbered node.
	  promote_child (node, N, right);
	  node = right;
	  if (node_type right = get_child (node, N))
	    {
	      // Perform another link left step.
	      //
	      // Add the promoted odd-numbered node to the right spine of the
	      // tree rooted at 1 and move on to the next even-numbered node.
	      set_child (new_spine_end, N, node);
	      new_spine_end = node;
	      node = right;
	    }
	}
      // Perform the assembly step.
      //
      // Add NL to the new spine and make N the new root.
      set_child (new_spine_end, N, get_child (node, 1 - N));
      set_child (node, 1 - N, final_child);
    }
  return node;
}

// Remove NODE from its position in the splay tree.  If NODE has at least
// one child node, return the node that should now hold NODE's position in
// the splay tree.  If NODE has no children, return null.
//
// The caller has the responsibility of updating the parent of the
// returned node.
template<typename Accessors>
inline typename base_splay_tree<Accessors>::node_type
base_splay_tree<Accessors>::remove_node_internal (node_type node)
{
  node_type left = get_child (node, 0);
  node_type right = get_child (node, 1);
  if (!left)
    return right;

  if (!right)
    return left;

  if (get_child (left, 1))
    {
      left = splay_limit<1> (left);
      gcc_checking_assert (!get_child (left, 1));
    }
  set_child (left, 1, right);
  return left;
}

// See the comment above the declaration.
template<typename Accessors>
inline void
base_splay_tree<Accessors>::insert_child (node_type node, unsigned int index,
					  node_type child)
{
  gcc_checking_assert (!get_child (child, 0) && !get_child (child, 1));
  set_child (child, index, get_child (node, index));
  set_child (node, index, child);
}

// Implement splay_next_node if N == 1 and splay_prev_node if N == 0.
template<typename Accessors>
template<unsigned int N>
bool
rooted_splay_tree<Accessors>::splay_neighbor ()
{
  node_type node = m_root;
  node_type new_root = get_child (node, N);
  if (!new_root)
    return false;

  if (get_child (new_root, 1 - N))
    {
      // NEW_ROOT is not itself the required node, so splay the required
      // node into its place.
      new_root = parent::template splay_limit<1 - N> (new_root);
      gcc_checking_assert (!get_child (new_root, 1 - N));
      set_child (node, N, node_type ());
      set_child (new_root, 1 - N, node);
    }
  else
    promote_child (node, N, new_root);
  set_parent (new_root, node_type ());
  m_root = new_root;
  return true;
}

// See the comment above the declaration.
template<typename Accessors>
template<typename Comparator>
bool
rooted_splay_tree<Accessors>::insert (node_type new_node, Comparator compare)
{
  gcc_checking_assert (!get_child (new_node, 0) && !get_child (new_node, 1));
  if (!m_root)
    {
      m_root = new_node;
      return true;
    }

  int comparison = lookup (compare);
  if (comparison == 0)
    return false;

  // Insert NEW_NODE before M_ROOT if COMPARISON < 0 and after M_ROOT
  // otherwise.
  set_child (new_node, comparison < 0, m_root);
  set_child (new_node, comparison > 0, get_child (m_root, comparison > 0));
  set_child (m_root, comparison > 0, nullptr);
  m_root = new_node;
  return true;
}

// See the comment above the declaration.
template<typename Accessors>
inline void
rooted_splay_tree<Accessors>::insert_max_node (node_type new_node)
{
  gcc_checking_assert (!get_child (new_node, 0) && !get_child (new_node, 1));
  set_child (new_node, 0, m_root);
  m_root = new_node;
}

// See the comment above the declaration.
template<typename Accessors>
inline void
rooted_splay_tree<Accessors>::splice_next_tree (rooted_splay_tree next_tree)
{
  splay_max_node ();
  set_child (m_root, 1, next_tree.m_root);
}

// See the comment above the declaration.
template<typename Accessors>
inline void
rooted_splay_tree<Accessors>::replace_max_node_at_root (node_type new_node)
{
  node_type old_node = m_root;
  gcc_checking_assert (!get_child (new_node, 0)
		       && !get_child (new_node, 1)
		       && !get_child (old_node, 1));
  set_child (new_node, 0, get_child (old_node, 0));
  // Clear the links from OLD_NODE.  Its parent and right child are
  // already node_type ().
  set_child (old_node, 0, node_type ());
  m_root = new_node;
}

// See the comment above the declaration.
template<typename Accessors>
inline void
rooted_splay_tree<Accessors>::remove_root ()
{
  node_type node = m_root;
  m_root = parent::remove_node_internal (node);
  if (m_root)
    set_parent (m_root, node_type ());
  // Clear the links from NODE.  Its parent is already node_type ().
  set_child (node, 0, node_type ());
  set_child (node, 1, node_type ());
}

// See the comment above the declaration.
template<typename Accessors>
inline rooted_splay_tree<Accessors>
rooted_splay_tree<Accessors>::split_before_root ()
{
  node_type new_root = get_child (m_root, 0);
  set_child (m_root, 0, node_type ());
  set_parent (new_root, node_type ());
  return new_root;
}

// See the comment above the declaration.
template<typename Accessors>
inline rooted_splay_tree<Accessors>
rooted_splay_tree<Accessors>::split_after_root ()
{
  node_type new_root = get_child (m_root, 1);
  set_child (m_root, 1, node_type ());
  set_parent (new_root, node_type ());
  return new_root;
}

// See the comment above the declaration.
template<typename Accessors>
inline bool
rooted_splay_tree<Accessors>::splay_prev_node ()
{
  return splay_neighbor<0> ();
}

// See the comment above the declaration.
template<typename Accessors>
inline bool
rooted_splay_tree<Accessors>::splay_next_node ()
{
  return splay_neighbor<1> ();
}

// See the comment above the declaration.
template<typename Accessors>
inline void
rooted_splay_tree<Accessors>::splay_min_node ()
{
  if (m_root && get_child (m_root, 0))
    {
      m_root = parent::template splay_limit<0> (m_root);
      set_parent (m_root, node_type ());
    }
}

// See the comment above the declaration.
template<typename Accessors>
inline void
rooted_splay_tree<Accessors>::splay_max_node ()
{
  if (m_root && get_child (m_root, 1))
    {
      m_root = parent::template splay_limit<1> (m_root);
      set_parent (m_root, node_type ());
    }
}

// See the comment above the declaration.
template<typename Accessors>
inline typename rooted_splay_tree<Accessors>::node_type
rooted_splay_tree<Accessors>::min_node ()
{
  splay_min_node ();
  return m_root;
}

// See the comment above the declaration.
template<typename Accessors>
inline typename rooted_splay_tree<Accessors>::node_type
rooted_splay_tree<Accessors>::max_node ()
{
  splay_max_node ();
  return m_root;
}

// See the comment above the declaration.
template<typename Accessors>
template<typename Comparator>
auto
rooted_splay_tree<Accessors>::lookup (Comparator compare)
  -> decltype (compare (m_root))
{
  // This essentially follows the simpilfied top-down method described
  // in Sleator and Tarjan's "Self-adjusting Binary Search Trees", but
  // with the complication that the comparisons are done only once.
  using result_type = decltype (compare (m_root));

  // The roots of the left and right trees.
  node_type link_left_root = node_type ();
  node_type link_right_root = node_type ();

  // Where to add new nodes to the left and right trees.
  node_type *link_left_ptr = &link_left_root;
  node_type *link_right_ptr = &link_right_root;

  // The nodes that contain *LINK_LEFT_PTR and *LINK_RIGHT_PTR,
  // once they no longer point to the roots above.
  node_type link_left_parent = node_type ();
  node_type link_right_parent = node_type ();

  auto link_left = [&](node_type node)
    {
      *link_left_ptr = node;
      link_left_ptr = &Accessors::child (node, 1);
      set_parent (node, link_left_parent);
      link_left_parent = node;
    };

  auto link_right = [&](node_type node)
    {
      *link_right_ptr = node;
      link_right_ptr = &Accessors::child (node, 0);
      set_parent (node, link_right_parent);
      link_right_parent = node;
    };

  node_type node = m_root;
  node_type parent = node_type ();
  result_type result;
  result_type old_result = 0;
  while (1)
    {
      // OLD_RESULT is 0 if NODE is the root of the middle tree.
      // Otherwise, PARENT is the root of the middle tree and OLD_RESULT
      // is how it compared.
      //
      // Results are:
      // < 0 if we want something smaller.
      // = 0 if we found the right node.
      // > 0 if we want something bigger.
      result = compare (node);
      if (old_result < 0)
	{
	  if (result < 0)
	    {
	      // SEARCH < NODE < PARENT
	      //
	      // Promote NODE (rotate right).
	      promote_child (parent, 0, node);
	      node_type next = get_child (node, 0);
	      if (!next)
		break;

	      link_right (node);

	      // NEXT is now the root of the middle tree.
	      node = next;
	      old_result = 0;
	      continue;
	    }

	  // SEARCH >= NODE, NODE < PARENT
	  link_right (parent);
	}
      else if (old_result > 0)
	{
	  if (result > 0)
	    {
	      // SEARCH > NODE > PARENT
	      //
	      // Promote NODE (rotate left).
	      promote_child (parent, 1, node);
	      node_type next = get_child (node, 1);
	      if (!next)
		break;

	      link_left (node);

	      // NEXT is now the root of the middle tree.
	      node = next;
	      old_result = 0;
	      continue;
	    }

	  // SEARCH <= NODE, NODE > PARENT
	  link_left (parent);
	}

      // Microoptimization to allow NODE to be read even if RESULT == 0.
      node_type next = get_child (node, result >= 0);
      if (result == 0 || !next)
	break;

      // NODE is now the root of the tree.
      parent = node;
      node = next;
      old_result = result;
    }

  node_type new_left = link_left_root;
  node_type new_right = link_right_root;

  if (new_left)
    {
      node_type old_left = get_child (node, 0);
      *link_left_ptr = old_left;
      if (old_left)
	set_parent (old_left, link_left_parent);
      set_child (node, 0, new_left);
    }

  if (new_right)
    {
      node_type old_right = get_child (node, 1);
      *link_right_ptr = old_right;
      if (old_right)
	set_parent (old_right, link_right_parent);
      set_child (node, 1, new_right);
    }

  set_parent (node, node_type ());
  m_root = node;
  return result;
}

// See the comment above the declaration.
template<typename Accessors>
template<typename LeftPredicate, typename RightPredicate>
int
rooted_splay_tree<Accessors>::lookup (LeftPredicate want_something_smaller,
				      RightPredicate want_something_bigger)
{
  // This essentially follows the simpilfied top-down method described
  // in Sleator and Tarjan's "Self-adjusting Binary Search Trees"
  // (and follows it more closely than the single-comparator version above).

  // The roots of the left and right trees.
  node_type link_left_root = node_type ();
  node_type link_right_root = node_type ();

  // Where to add new nodes to the left and right trees.
  node_type *link_left_ptr = &link_left_root;
  node_type *link_right_ptr = &link_right_root;

  // The nodes that contain *LINK_LEFT_PTR and *LINK_RIGHT_PTR,
  // once they no longer point to the roots above.
  node_type link_left_parent = node_type ();
  node_type link_right_parent = node_type ();

  node_type node = m_root;
  int result;
  for (;;)
    {
      // NODE is the root of the middle tree.
      if (want_something_smaller (node))
	{
	  result = -1;
	  node_type next = get_child (node, 0);
	  if (!next)
	    break;

	  if (want_something_smaller (next))
	    {
	      // Promote NODE (rotate right).
	      promote_child (node, 0, next);
	      node = next;
	      next = get_child (node, 0);
	      if (!next)
		break;
	    }

	  // Add NODE to the right tree (link right).
	  *link_right_ptr = node;
	  link_right_ptr = &Accessors::child (node, 0);
	  set_parent (node, link_right_parent);
	  link_right_parent = node;

	  node = next;
	}
      else if (want_something_bigger (node))
	{
	  result = 1;
	  node_type next = get_child (node, 1);
	  if (!next)
	    break;

	  if (want_something_bigger (next))
	    {
	      // Promote NODE (rotate left).
	      promote_child (node, 1, next);
	      node = next;
	      next = get_child (node, 1);
	      if (!next)
		break;
	    }

	  // Add NODE to the left tree (link left).
	  *link_left_ptr = node;
	  link_left_ptr = &Accessors::child (node, 1);
	  set_parent (node, link_left_parent);
	  link_left_parent = node;

	  node = next;
	}
      else
	{
	  result = 0;
	  break;
	}
    }

  node_type new_left = link_left_root;
  node_type new_right = link_right_root;

  if (new_left)
    {
      node_type old_left = get_child (node, 0);
      *link_left_ptr = old_left;
      if (old_left)
	set_parent (old_left, link_left_parent);
      set_child (node, 0, new_left);
    }

  if (new_right)
    {
      node_type old_right = get_child (node, 1);
      *link_right_ptr = old_right;
      if (old_right)
	set_parent (old_right, link_right_parent);
      set_child (node, 1, new_right);
    }

  set_parent (node, node_type ());
  m_root = node;
  return result;
}

// See the comment above the declaration.
template<typename Accessors>
template<typename Printer>
inline void
rooted_splay_tree<Accessors>::print (pretty_printer *pp, Printer printer) const
{
  print (pp, m_root, printer);
}

// Return NODE's current parent.
template<typename Accessors>
inline typename rootless_splay_tree<Accessors>::node_type
rootless_splay_tree<Accessors>::get_parent (node_type node)
{
  return Accessors::parent (node);
}

// CHILD is known to be a child of PARENT.  Return which index it has.
template<typename Accessors>
inline unsigned int
rootless_splay_tree<Accessors>::child_index (node_type parent, node_type child)
{
  return get_child (parent, 1) == child;
}

// If N == 1, implement splay_known_max_node, otherwise implement
// splay_known_min_node.
template<typename Accessors>
template<unsigned int N>
inline void
rootless_splay_tree<Accessors>::splay_known_limit (node_type node)
{
  node_type child = node;
  node_type parent = get_parent (child);
  if (!parent)
    return;

  do
    // At this point, NODE conceptually replaces CHILD as a child of
    // PARENT, but we haven't yet updated PARENT accordingly.
    if (node_type grandparent = get_parent (parent))
      {
	node_type greatgrandparent = get_parent (grandparent);
	promote_child (grandparent, N, parent);
	promote_child (parent, N, node);
	child = grandparent;
	parent = greatgrandparent;
      }
    else
      {
	promote_child (parent, N, node);
	break;
      }
  while (parent);
  set_parent (node, node_type ());
}

// See the comment above the declaration.
template<typename Accessors>
typename rootless_splay_tree<Accessors>::node_type
rootless_splay_tree<Accessors>::remove_node (node_type node)
{
  node_type replacement = parent::remove_node_internal (node);
  if (node_type parent = get_parent (node))
    set_child (parent, child_index (parent, node), replacement);
  else if (replacement)
    set_parent (replacement, node_type ());
  // Clear the links from NODE.
  set_parent (node, node_type ());
  set_child (node, 0, node_type ());
  set_child (node, 1, node_type ());
  return replacement;
}

// See the comment above the declaration.
template<typename Accessors>
void
rootless_splay_tree<Accessors>::splay (node_type node)
{
  node_type child = node;
  node_type parent = get_parent (child);
  if (!parent)
    return;

  do
    {
      // At this point, NODE conceptually replaces CHILD as a child of
      // PARENT, but we haven't yet updated PARENT accordingly.
      unsigned int index = child_index (parent, child);
      if (node_type grandparent = get_parent (parent))
	{
	  node_type greatgrandparent = get_parent (grandparent);
	  unsigned int parent_index = child_index (grandparent, parent);
	  if (index == parent_index)
	    {
	      promote_child (grandparent, parent_index, parent);
	      promote_child (parent, index, node);
	    }
	  else
	    {
	      promote_child (parent, index, node);
	      promote_child (grandparent, parent_index, node);
	    }
	  child = grandparent;
	  parent = greatgrandparent;
	}
      else
	{
	  promote_child (parent, index, node);
	  break;
	}
    }
  while (parent);
  set_parent (node, node_type ());
}

// See the comment above the declaration.
template<typename Accessors>
inline void
rootless_splay_tree<Accessors>::splay_known_min_node (node_type node)
{
  splay_known_limit<0> (node);
}

// See the comment above the declaration.
template<typename Accessors>
inline void
rootless_splay_tree<Accessors>::splay_known_max_node (node_type node)
{
  splay_known_limit<1> (node);
}

// See the comment above the declaration.
template<typename Accessors>
template<typename DefaultResult, typename Predicate>
auto
rootless_splay_tree<Accessors>::
splay_and_search (node_type node, DefaultResult default_result,
		  Predicate predicate)
  -> decltype (predicate (node, 0))
{
  using Result = decltype (predicate (node, 0));

  node_type child = node;
  node_type parent = get_parent (child);
  if (!parent)
    return default_result;

  do
    {
      // At this point, NODE conceptually replaces CHILD as a child of
      // PARENT, but we haven't yet updated PARENT accordingly.
      unsigned int index = child_index (parent, child);
      if (Result result = predicate (parent, index))
	{
	  set_child (parent, index, node);
	  return result;
	}
      if (node_type grandparent = get_parent (parent))
	{
	  node_type greatgrandparent = get_parent (grandparent);
	  unsigned int parent_index = child_index (grandparent, parent);
	  if (Result result = predicate (grandparent, parent_index))
	    {
	      set_child (parent, index, node);
	      return result;
	    }
	  if (index == parent_index)
	    {
	      promote_child (grandparent, parent_index, parent);
	      promote_child (parent, index, node);
	    }
	  else
	    {
	      promote_child (parent, index, node);
	      promote_child (grandparent, parent_index, node);
	    }
	  child = grandparent;
	  parent = greatgrandparent;
	}
      else
	{
	  promote_child (parent, index, node);
	  break;
	}
    }
  while (parent);
  set_parent (node, node_type ());
  return default_result;
}

// Splay NODE1 looking to see if one of its ancestors is NODE2.  If it is,
// return -1 if NODE1 comes before NODE2 or 1 if NODE1 comes after NODE2.
// Return 0 if NODE2 is not an ancestor of NODE1.
template<typename Accessors>
int
rootless_splay_tree<Accessors>::compare_nodes_one_way (node_type node1,
						       node_type node2)
{
  auto compare = [&](node_type parent, unsigned int index) -> int
    {
      if (parent == node2)
	return index ? 1 : -1;
      return 0;
    };
  return splay_and_search (node1, 0, compare);
}

// See the comment above the declaration.
template<typename Accessors>
int
rootless_splay_tree<Accessors>::compare_nodes (node_type node1,
					       node_type node2)
{
  if (node1 == node2)
    return 0;

  // Splay NODE1 looking for NODE2.
  int cmp = compare_nodes_one_way (node1, node2);
  if (cmp)
    return cmp;

  // That failed, but NODE1 is now the root of the tree.  Splay NODE2
  // to see on which side of NODE1 it falls.
  cmp = compare_nodes_one_way (node2, node1);
  gcc_checking_assert (cmp);
  return -cmp;
}