blob: 9808e825d2123736e8266d0c37b2940c92013ced [file] [log] [blame]
// Splay tree utilities -*- C++ -*-
// Copyright (C) 2020-2021 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;
}