typed-splay-tree.h (typed_splay_tree::remove): New function.

2018-06-15  Bernd Edlinger  <bernd.edlinger@hotmail.de>

        * typed-splay-tree.h (typed_splay_tree::remove): New function.
        (typed_splay_tree::closure,
        typed_splay_tree::inner_foreach_fn, typed_splay_tree::m_inner): Deleted.
        (typed_splay_tree::typed_splay_tree,
        typed_splay_tree::operator =): Declared private.
        (typed_splay_tree::splay_tree_key, typed_splay_tree::splay_tree_value,
        typed_splay_tree::splay_tree_node_s, typed_splay_tree::KDEL,
        typed_splay_tree::VDEL, typed_splay_tree::splay_tree_delete_helper,
        typed_splay_tree::rotate_left, typed_splay_tree::rotate_right,
        typed_splay_tree::splay_tree_splay,
        typed_splay_tree::splay_tree_foreach_helper,
        typed_splay_tree::splay_tree_insert,
        typed_splay_tree::splay_tree_remove,
        typed_splay_tree::splay_tree_lookup,
        typed_splay_tree::splay_tree_predecessor,
        typed_splay_tree::splay_tree_successor,
        typed_splay_tree::splay_tree_min,
        typed_splay_tree::splay_tree_max): Took over from splay-tree.c/.h.
        (typed_splay_tree::root, typed_splay_tree::comp,
        typed_splay_tree::delete_key,
        typed_splay_tree::delete_value): New data members.
        * typed-splay-tree.c (selftest::test_str_to_int): Add a test for
        typed_splay_tree::remove.

From-SVN: r261645

3 files changed, 527 insertions, 46 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 83e297e..c91c81e 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,29 @@
+2018-06-15  Bernd Edlinger  <bernd.edlinger@hotmail.de>
+
+	* typed-splay-tree.h (typed_splay_tree::remove): New function.
+	(typed_splay_tree::closure,
+	typed_splay_tree::inner_foreach_fn, typed_splay_tree::m_inner): Deleted.
+	(typed_splay_tree::typed_splay_tree,
+	typed_splay_tree::operator =): Declared private.
+	(typed_splay_tree::splay_tree_key, typed_splay_tree::splay_tree_value,
+	typed_splay_tree::splay_tree_node_s, typed_splay_tree::KDEL,
+	typed_splay_tree::VDEL, typed_splay_tree::splay_tree_delete_helper,
+	typed_splay_tree::rotate_left, typed_splay_tree::rotate_right,
+	typed_splay_tree::splay_tree_splay,
+	typed_splay_tree::splay_tree_foreach_helper,
+	typed_splay_tree::splay_tree_insert,
+	typed_splay_tree::splay_tree_remove,
+	typed_splay_tree::splay_tree_lookup,
+	typed_splay_tree::splay_tree_predecessor,
+	typed_splay_tree::splay_tree_successor,
+	typed_splay_tree::splay_tree_min,
+	typed_splay_tree::splay_tree_max): Took over from splay-tree.c/.h.
+	(typed_splay_tree::root, typed_splay_tree::comp,
+	typed_splay_tree::delete_key,
+	typed_splay_tree::delete_value): New data members.
+	* typed-splay-tree.c (selftest::test_str_to_int): Add a test for
+	typed_splay_tree::remove.
+
 2018-06-15  Matthew Fortune  <matthew.fortune@mips.com>
 
 	* config/mips/mips.h (ASM_SPEC): Pass through -mcrc, -mno-crc,
diff --git a/gcc/typed-splay-tree.c b/gcc/typed-splay-tree.c
index 5d3ffd7..344920f 100644
--- a/gcc/typed-splay-tree.c
+++ b/gcc/typed-splay-tree.c
@@ -47,6 +47,9 @@ test_str_to_int ()
   t.insert ("a", 1);
   t.insert ("b", 2);
   t.insert ("c", 3);
+  t.insert ("d", 4);
+
+  t.remove ("d");
 
   ASSERT_EQ (1, t.lookup ("a"));
   ASSERT_EQ (2, t.lookup ("b"));
diff --git a/gcc/typed-splay-tree.h b/gcc/typed-splay-tree.h
index 95c2f5f..e8ba219 100644
--- a/gcc/typed-splay-tree.h
+++ b/gcc/typed-splay-tree.h
@@ -20,8 +20,6 @@ along with GCC; see the file COPYING3.  If not see
 #ifndef GCC_TYPED_SPLAY_TREE_H
 #define GCC_TYPED_SPLAY_TREE_H
 
-#include "splay-tree.h"
-
 /* Typesafe wrapper around libiberty's splay-tree.h.  */
 template <typename KEY_TYPE, typename VALUE_TYPE>
 class typed_splay_tree
@@ -44,27 +42,66 @@ class typed_splay_tree
   value_type predecessor (key_type k);
   value_type successor (key_type k);
   void insert (key_type k, value_type v);
+  void remove (key_type k);
   value_type max ();
   value_type min ();
   int foreach (foreach_fn, void *);
 
  private:
-  /* Helper type for typed_splay_tree::foreach.  */
-  struct closure
-  {
-    closure (foreach_fn outer_cb, void *outer_user_data)
-    : m_outer_cb (outer_cb), m_outer_user_data (outer_user_data) {}
-
-    foreach_fn m_outer_cb;
-    void *m_outer_user_data;
-  };
+  /* Copy and assignment ops are not supported.  */
+  typed_splay_tree (const typed_splay_tree &);
+  typed_splay_tree & operator = (const typed_splay_tree &);
+
+  typedef key_type splay_tree_key;
+  typedef value_type splay_tree_value;
+
+  /* The nodes in the splay tree.  */
+  struct splay_tree_node_s {
+    /* The key.  */
+    splay_tree_key key;
+
+    /* The value.  */
+    splay_tree_value value;
 
-  static int inner_foreach_fn (splay_tree_node node, void *user_data);
+    /* The left and right children, respectively.  */
+    splay_tree_node_s *left, *right;
+
+    /* Used as temporary value for tree traversals.  */
+    splay_tree_node_s *back;
+  };
+  typedef splay_tree_node_s *splay_tree_node;
+
+  inline void KDEL (splay_tree_key);
+  inline void VDEL (splay_tree_value);
+  void splay_tree_delete_helper (splay_tree_node);
+  static inline void rotate_left (splay_tree_node *,
+				  splay_tree_node, splay_tree_node);
+  static inline void rotate_right (splay_tree_node *,
+				   splay_tree_node, splay_tree_node);
+  void splay_tree_splay (splay_tree_key);
+  static int splay_tree_foreach_helper (splay_tree_node,
+					foreach_fn, void*);
+  splay_tree_node splay_tree_insert (splay_tree_key, splay_tree_value);
+  void splay_tree_remove (splay_tree_key key);
+  splay_tree_node splay_tree_lookup (splay_tree_key key);
+  splay_tree_node splay_tree_predecessor (splay_tree_key);
+  splay_tree_node splay_tree_successor (splay_tree_key);
+  splay_tree_node splay_tree_max ();
+  splay_tree_node splay_tree_min ();
 
   static value_type node_to_value (splay_tree_node node);
 
- private:
-  ::splay_tree m_inner;
+  /* The root of the tree.  */
+  splay_tree_node root;
+
+  /* The comparision function.  */
+  compare_fn comp;
+
+  /* The deallocate-key function.  NULL if no cleanup is necessary.  */
+  delete_key_fn delete_key;
+
+  /* The deallocate-value function.  NULL if no cleanup is necessary.  */
+  delete_value_fn delete_value;
 };
 
 /* Constructor for typed_splay_tree <K, V>.  */
@@ -75,12 +112,10 @@ inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>::
 		    delete_key_fn delete_key_fn,
 		    delete_value_fn delete_value_fn)
 {
-  m_inner = splay_tree_new ((splay_tree_compare_fn)
-			    (void (*) (void)) compare_fn,
-			    (splay_tree_delete_key_fn)
-			    (void (*) (void)) delete_key_fn,
-			    (splay_tree_delete_value_fn)
-			    (void (*) (void)) delete_value_fn);
+  root = NULL;
+  comp = compare_fn;
+  delete_key = delete_key_fn;
+  delete_value = delete_value_fn;
 }
 
 /* Destructor for typed_splay_tree <K, V>.  */
@@ -89,7 +124,7 @@ template <typename KEY_TYPE, typename VALUE_TYPE>
 inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>::
   ~typed_splay_tree ()
 {
-  splay_tree_delete (m_inner);
+  splay_tree_delete_helper (root);
 }
 
 /* Lookup KEY, returning a value if present, and NULL
@@ -99,7 +134,7 @@ template <typename KEY_TYPE, typename VALUE_TYPE>
 inline VALUE_TYPE
 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::lookup (key_type key)
 {
-  splay_tree_node node = splay_tree_lookup (m_inner, (splay_tree_key)key);
+  splay_tree_node node = splay_tree_lookup (key);
   return node_to_value (node);
 }
 
@@ -110,7 +145,7 @@ template <typename KEY_TYPE, typename VALUE_TYPE>
 inline VALUE_TYPE
 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::predecessor (key_type key)
 {
-  splay_tree_node node = splay_tree_predecessor (m_inner, (splay_tree_key)key);
+  splay_tree_node node = splay_tree_predecessor (key);
   return node_to_value (node);
 }
 
@@ -119,9 +154,9 @@ typed_splay_tree<KEY_TYPE, VALUE_TYPE>::predecessor (key_type key)
 
 template <typename KEY_TYPE, typename VALUE_TYPE>
 inline VALUE_TYPE
-typed_splay_tree<KEY_TYPE, VALUE_TYPE>::successor (key_type k)
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::successor (key_type key)
 {
-  splay_tree_node node = splay_tree_successor (m_inner, (splay_tree_key)k);
+  splay_tree_node node = splay_tree_successor (key);
   return node_to_value (node);
 }
 
@@ -134,9 +169,16 @@ inline void
 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::insert (key_type key,
 						value_type value)
 {
-  splay_tree_insert (m_inner,
-		     (splay_tree_key)key,
-		     (splay_tree_value)value);
+  splay_tree_insert (key, value);
+}
+
+/* Remove a node (associating KEY with VALUE).  */
+
+template <typename KEY_TYPE, typename VALUE_TYPE>
+inline void
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::remove (key_type key)
+{
+  splay_tree_remove (key);
 }
 
 /* Get the value with maximal key.  */
@@ -145,7 +187,7 @@ template <typename KEY_TYPE, typename VALUE_TYPE>
 inline VALUE_TYPE
 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::max ()
 {
-  return node_to_value (splay_tree_max (m_inner));
+  return node_to_value (splay_tree_max ());
 }
 
 /* Get the value with minimal key.  */
@@ -154,7 +196,7 @@ template <typename KEY_TYPE, typename VALUE_TYPE>
 inline VALUE_TYPE
 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::min ()
 {
-  return node_to_value (splay_tree_min (m_inner));
+  return node_to_value (splay_tree_min ());
 }
 
 /* Call OUTER_CB, passing it the OUTER_USER_DATA, for every node,
@@ -164,37 +206,447 @@ typed_splay_tree<KEY_TYPE, VALUE_TYPE>::min ()
 
 template <typename KEY_TYPE, typename VALUE_TYPE>
 inline int
-typed_splay_tree<KEY_TYPE, VALUE_TYPE>::foreach (foreach_fn outer_cb,
-						 void *outer_user_data)
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::foreach (foreach_fn foreach_fn,
+						 void *user_data)
 {
-  closure c (outer_cb, outer_user_data);
+  return splay_tree_foreach_helper (root, foreach_fn, user_data);
+}
 
-  return splay_tree_foreach (m_inner, inner_foreach_fn, &c);
+/* Internal function for converting from splay_tree_node to
+   VALUE_TYPE.  */
+template <typename KEY_TYPE, typename VALUE_TYPE>
+inline VALUE_TYPE
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::node_to_value (splay_tree_node node)
+{
+  if (node)
+    return node->value;
+  else
+    return 0;
 }
 
-/* Helper function for typed_splay_tree::foreach.  */
+template <typename KEY_TYPE, typename VALUE_TYPE>
+inline void
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::KDEL(splay_tree_key x)
+{
+  if (delete_key)
+    (*delete_key)(x);
+}
+
+template <typename KEY_TYPE, typename VALUE_TYPE>
+inline void
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::VDEL(splay_tree_value x)
+{
+  if (delete_value)
+    (*delete_value)(x);
+}
+
+/* Deallocate NODE (a member of SP), and all its sub-trees.  */
+
+template <typename KEY_TYPE, typename VALUE_TYPE>
+void
+typed_splay_tree<KEY_TYPE,
+		 VALUE_TYPE>::splay_tree_delete_helper (splay_tree_node node)
+{
+  splay_tree_node pending = NULL;
+  splay_tree_node active = NULL;
+
+  if (!node)
+    return;
+
+  KDEL (node->key);
+  VDEL (node->value);
+
+  /* We use the "back" field to hold the "next" pointer.  */
+  node->back = pending;
+  pending = node;
+
+  /* Now, keep processing the pending list until there aren't any
+     more.  This is a little more complicated than just recursing, but
+     it doesn't toast the stack for large trees.  */
+
+  while (pending)
+    {
+      active = pending;
+      pending = NULL;
+      while (active)
+	{
+	  splay_tree_node temp;
+
+	  /* active points to a node which has its key and value
+	     deallocated, we just need to process left and right.  */
+
+	  if (active->left)
+	    {
+	      KDEL (active->left->key);
+	      VDEL (active->left->value);
+	      active->left->back = pending;
+	      pending = active->left;
+	    }
+	  if (active->right)
+	    {
+	      KDEL (active->right->key);
+	      VDEL (active->right->value);
+	      active->right->back = pending;
+	      pending = active->right;
+	    }
+
+	  temp = active;
+	  active = temp->back;
+	  delete temp;
+	}
+    }
+}
+
+/* Rotate the edge joining the left child N with its parent P.  PP is the
+   grandparents' pointer to P.  */
+
+template <typename KEY_TYPE, typename VALUE_TYPE>
+inline void
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::rotate_left (splay_tree_node *pp,
+						     splay_tree_node p,
+						     splay_tree_node n)
+{
+  splay_tree_node tmp;
+  tmp = n->right;
+  n->right = p;
+  p->left = tmp;
+  *pp = n;
+}
+
+/* Rotate the edge joining the right child N with its parent P.  PP is the
+   grandparents' pointer to P.  */
+
+template <typename KEY_TYPE, typename VALUE_TYPE>
+inline void
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::rotate_right (splay_tree_node *pp,
+						      splay_tree_node p,
+						      splay_tree_node n)
+{
+  splay_tree_node tmp;
+  tmp = n->left;
+  n->left = p;
+  p->right = tmp;
+  *pp = n;
+}
+
+/* Bottom up splay of key.  */
+
+template <typename KEY_TYPE, typename VALUE_TYPE>
+void
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_splay (splay_tree_key key)
+{
+  if (root == NULL)
+    return;
+
+  do {
+    int cmp1, cmp2;
+    splay_tree_node n, c;
+
+    n = root;
+    cmp1 = (*comp) (key, n->key);
+
+    /* Found.  */
+    if (cmp1 == 0)
+      return;
+
+    /* Left or right?  If no child, then we're done.  */
+    if (cmp1 < 0)
+      c = n->left;
+    else
+      c = n->right;
+    if (!c)
+      return;
+
+    /* Next one left or right?  If found or no child, we're done
+       after one rotation.  */
+    cmp2 = (*comp) (key, c->key);
+    if (cmp2 == 0
+	|| (cmp2 < 0 && !c->left)
+	|| (cmp2 > 0 && !c->right))
+      {
+	if (cmp1 < 0)
+	  rotate_left (&root, n, c);
+	else
+	  rotate_right (&root, n, c);
+	return;
+      }
+
+    /* Now we have the four cases of double-rotation.  */
+    if (cmp1 < 0 && cmp2 < 0)
+      {
+	rotate_left (&n->left, c, c->left);
+	rotate_left (&root, n, n->left);
+      }
+    else if (cmp1 > 0 && cmp2 > 0)
+      {
+	rotate_right (&n->right, c, c->right);
+	rotate_right (&root, n, n->right);
+      }
+    else if (cmp1 < 0 && cmp2 > 0)
+      {
+	rotate_right (&n->left, c, c->right);
+	rotate_left (&root, n, n->left);
+      }
+    else if (cmp1 > 0 && cmp2 < 0)
+      {
+	rotate_left (&n->right, c, c->left);
+	rotate_right (&root, n, n->right);
+      }
+  } while (1);
+}
+
+/* Call FN, passing it the DATA, for every node below NODE, all of
+   which are from SP, following an in-order traversal.  If FN every
+   returns a non-zero value, the iteration ceases immediately, and the
+   value is returned.  Otherwise, this function returns 0.  */
 
 template <typename KEY_TYPE, typename VALUE_TYPE>
 int
-typed_splay_tree<KEY_TYPE, VALUE_TYPE>::inner_foreach_fn (splay_tree_node node,
-							  void *user_data)
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_foreach_helper (
+						splay_tree_node node,
+						foreach_fn fn, void *data)
 {
-  closure *c = (closure *)user_data;
+  int val;
+  splay_tree_node stack;
+
+  /* A non-recursive implementation is used to avoid filling the stack
+     for large trees.  Splay trees are worst case O(n) in the depth of
+     the tree.  */
+
+  stack = NULL;
+  val = 0;
+
+  for (;;)
+    {
+      while (node != NULL)
+	{
+	  node->back = stack;
+	  stack = node;
+	  node = node->left;
+	}
+
+      if (stack == NULL)
+	break;
+
+      node = stack;
+      stack = stack->back;
+
+      val = (*fn) (node->key, node->value, data);
+      if (val)
+	break;
 
-  return c->m_outer_cb ((KEY_TYPE)node->key, (VALUE_TYPE)node->value,
-			c->m_outer_user_data);
+      node = node->right;
+    }
+
+  return val;
 }
 
-/* Internal function for converting from splay_tree_node to
-   VALUE_TYPE.  */
+/* Insert a new node (associating KEY with DATA) into SP.  If a
+   previous node with the indicated KEY exists, its data is replaced
+   with the new value.  Returns the new node.  */
+
 template <typename KEY_TYPE, typename VALUE_TYPE>
-inline VALUE_TYPE
-typed_splay_tree<KEY_TYPE, VALUE_TYPE>::node_to_value (splay_tree_node node)
+typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_insert (
+						splay_tree_key key,
+						splay_tree_value value)
 {
-  if (node)
-    return (value_type)node->value;
+  int comparison = 0;
+
+  splay_tree_splay (key);
+
+  if (root)
+    comparison = (*comp)(root->key, key);
+
+  if (root && comparison == 0)
+    {
+      /* If the root of the tree already has the indicated KEY, just
+	 replace the value with VALUE.  */
+      VDEL(root->value);
+      root->value = value;
+    }
+  else
+    {
+      /* Create a new node, and insert it at the root.  */
+      splay_tree_node node;
+
+      node = new splay_tree_node_s;
+      node->key = key;
+      node->value = value;
+
+      if (!root)
+	node->left = node->right = 0;
+      else if (comparison < 0)
+	{
+	  node->left = root;
+	  node->right = node->left->right;
+	  node->left->right = 0;
+	}
+      else
+	{
+	  node->right = root;
+	  node->left = node->right->left;
+	  node->right->left = 0;
+	}
+
+      root = node;
+    }
+
+  return root;
+}
+
+/* Remove KEY from SP.  It is not an error if it did not exist.  */
+
+template <typename KEY_TYPE, typename VALUE_TYPE>
+void
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_remove (splay_tree_key key)
+{
+  splay_tree_splay (key);
+
+  if (root && (*comp) (root->key, key) == 0)
+    {
+      splay_tree_node left, right;
+
+      left = root->left;
+      right = root->right;
+
+      /* Delete the root node itself.  */
+      VDEL (root->value);
+      delete root;
+
+      /* One of the children is now the root.  Doesn't matter much
+	 which, so long as we preserve the properties of the tree.  */
+      if (left)
+	{
+	  root = left;
+
+	  /* If there was a right child as well, hang it off the
+	     right-most leaf of the left child.  */
+	  if (right)
+	    {
+	      while (left->right)
+		left = left->right;
+	      left->right = right;
+	    }
+	}
+      else
+	root = right;
+    }
+}
+
+/* Lookup KEY in SP, returning VALUE if present, and NULL
+   otherwise.  */
+
+template <typename KEY_TYPE, typename VALUE_TYPE>
+typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_lookup (splay_tree_key key)
+{
+  splay_tree_splay (key);
+
+  if (root && (*comp)(root->key, key) == 0)
+    return root;
   else
     return 0;
 }
 
+/* Return the node in SP with the greatest key.  */
+
+template <typename KEY_TYPE, typename VALUE_TYPE>
+typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_max ()
+{
+  splay_tree_node n = root;
+
+  if (!n)
+    return NULL;
+
+  while (n->right)
+    n = n->right;
+
+  return n;
+}
+
+/* Return the node in SP with the smallest key.  */
+
+template <typename KEY_TYPE, typename VALUE_TYPE>
+typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_min ()
+{
+  splay_tree_node n = root;
+
+  if (!n)
+    return NULL;
+
+  while (n->left)
+    n = n->left;
+
+  return n;
+}
+
+/* Return the immediate predecessor KEY, or NULL if there is no
+   predecessor.  KEY need not be present in the tree.  */
+
+template <typename KEY_TYPE, typename VALUE_TYPE>
+typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
+typed_splay_tree<KEY_TYPE,
+		 VALUE_TYPE>::splay_tree_predecessor (splay_tree_key key)
+{
+  int comparison;
+  splay_tree_node node;
+
+  /* If the tree is empty, there is certainly no predecessor.  */
+  if (!root)
+    return NULL;
+
+  /* Splay the tree around KEY.  That will leave either the KEY
+     itself, its predecessor, or its successor at the root.  */
+  splay_tree_splay (key);
+  comparison = (*comp)(root->key, key);
+
+  /* If the predecessor is at the root, just return it.  */
+  if (comparison < 0)
+    return root;
+
+  /* Otherwise, find the rightmost element of the left subtree.  */
+  node = root->left;
+  if (node)
+    while (node->right)
+      node = node->right;
+
+  return node;
+}
+
+/* Return the immediate successor KEY, or NULL if there is no
+   successor.  KEY need not be present in the tree.  */
+
+template <typename KEY_TYPE, typename VALUE_TYPE>
+typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
+typed_splay_tree<KEY_TYPE,
+		 VALUE_TYPE>::splay_tree_successor (splay_tree_key key)
+{
+  int comparison;
+  splay_tree_node node;
+
+  /* If the tree is empty, there is certainly no successor.  */
+  if (!root)
+    return NULL;
+
+  /* Splay the tree around KEY.  That will leave either the KEY
+     itself, its predecessor, or its successor at the root.  */
+  splay_tree_splay (key);
+  comparison = (*comp)(root->key, key);
+
+  /* If the successor is at the root, just return it.  */
+  if (comparison > 0)
+    return root;
+
+  /* Otherwise, find the leftmost element of the right subtree.  */
+  node = root->right;
+  if (node)
+    while (node->left)
+      node = node->left;
+
+  return node;
+}
+
 #endif  /* GCC_TYPED_SPLAY_TREE_H  */