--- a/libiberty/splay-tree.c	Tue May 25 18:58:51 2010 +0900
+++ b/libiberty/splay-tree.c	Tue Mar 22 17:18:12 2011 +0900
@@ -1,5 +1,6 @@
 /* A splay-tree datatype.  
-   Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
+   Copyright (C) 1998, 1999, 2000, 2001, 2009,
+   2010, 2011 Free Software Foundation, Inc.
    Contributed by Mark Mitchell (mark@markmitchell.com).
 
 This file is part of GNU CC.
@@ -43,7 +44,7 @@
 static inline void rotate_right (splay_tree_node *,
 				splay_tree_node, splay_tree_node);
 static void splay_tree_splay (splay_tree, splay_tree_key);
-static int splay_tree_foreach_helper (splay_tree, splay_tree_node,
+static int splay_tree_foreach_helper (splay_tree_node,
                                       splay_tree_foreach_fn, void*);
 
 /* Deallocate NODE (a member of SP), and all its sub-trees.  */
@@ -203,26 +204,52 @@
    value is returned.  Otherwise, this function returns 0.  */
 
 static int
-splay_tree_foreach_helper (splay_tree sp, splay_tree_node node,
+splay_tree_foreach_helper (splay_tree_node node,
                            splay_tree_foreach_fn fn, void *data)
 {
   int val;
-
-  if (!node)
-    return 0;
+  splay_tree_node *stack;
+  int stack_ptr, stack_size;
 
-  val = splay_tree_foreach_helper (sp, node->left, fn, data);
-  if (val)
-    return val;
+  /* 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.  */
+
+#define INITIAL_STACK_SIZE 100
+  stack_size = INITIAL_STACK_SIZE;
+  stack_ptr = 0;
+  stack = XNEWVEC (splay_tree_node, stack_size);
+  val = 0;
 
-  val = (*fn)(node, data);
-  if (val)
-    return val;
+  for (;;)
+    {
+      while (node != NULL)
+	{
+	  if (stack_ptr == stack_size)
+	    {
+	      stack_size *= 2;
+	      stack = XRESIZEVEC (splay_tree_node, stack, stack_size);
+	    }
+	  stack[stack_ptr++] = node;
+	  node = node->left;
+	}
 
-  return splay_tree_foreach_helper (sp, node->right, fn, data);
+      if (stack_ptr == 0)
+	break;
+
+      node = stack[--stack_ptr];
+
+      val = (*fn) (node, data);
+      if (val)
+	break;
+
+      node = node->right;
+    }
+
+  XDELETEVEC (stack);
+  return val;
 }
 
-
 /* An allocator and deallocator based on xmalloc.  */
 static void *
 splay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED)
@@ -265,13 +292,53 @@
                                splay_tree_deallocate_fn deallocate_fn,
                                void *allocate_data)
 {
-  splay_tree sp = (splay_tree) (*allocate_fn) (sizeof (struct splay_tree_s),
-                                               allocate_data);
+  return
+    splay_tree_new_typed_alloc (compare_fn, delete_key_fn, delete_value_fn,
+				allocate_fn, allocate_fn, deallocate_fn,
+				allocate_data);
+}
+
+/*
+
+@deftypefn Supplemental splay_tree splay_tree_new_with_typed_alloc @
+(splay_tree_compare_fn @var{compare_fn}, @
+splay_tree_delete_key_fn @var{delete_key_fn}, @
+splay_tree_delete_value_fn @var{delete_value_fn}, @
+splay_tree_allocate_fn @var{tree_allocate_fn}, @
+splay_tree_allocate_fn @var{node_allocate_fn}, @
+splay_tree_deallocate_fn @var{deallocate_fn}, @
+void * @var{allocate_data})
+
+This function creates a splay tree that uses two different allocators
+@var{tree_allocate_fn} and @var{node_allocate_fn} to use for allocating the
+tree itself and its nodes respectively.  This is useful when variables of
+different types need to be allocated with different allocators.
+
+The splay tree will use @var{compare_fn} to compare nodes,
+@var{delete_key_fn} to deallocate keys, and @var{delete_value_fn} to
+deallocate values.
+
+@end deftypefn
+
+*/
+
+splay_tree
+splay_tree_new_typed_alloc (splay_tree_compare_fn compare_fn,
+			    splay_tree_delete_key_fn delete_key_fn,
+			    splay_tree_delete_value_fn delete_value_fn,
+			    splay_tree_allocate_fn tree_allocate_fn,
+			    splay_tree_allocate_fn node_allocate_fn,
+			    splay_tree_deallocate_fn deallocate_fn,
+			    void * allocate_data)
+{
+  splay_tree sp = (splay_tree) (*tree_allocate_fn)
+    (sizeof (struct splay_tree_s), allocate_data);
+
   sp->root = 0;
   sp->comp = compare_fn;
   sp->delete_key = delete_key_fn;
   sp->delete_value = delete_value_fn;
-  sp->allocate = allocate_fn;
+  sp->allocate = node_allocate_fn;
   sp->deallocate = deallocate_fn;
   sp->allocate_data = allocate_data;
 
@@ -313,10 +380,10 @@
     {
       /* Create a new node, and insert it at the root.  */
       splay_tree_node node;
-      
+
       node = ((splay_tree_node)
-              (*sp->allocate) (sizeof (struct splay_tree_node_s),
-                               sp->allocate_data));
+	      (*sp->allocate) (sizeof (struct splay_tree_node_s),
+			       sp->allocate_data));
       node->key = key;
       node->value = value;
       
@@ -496,7 +563,7 @@
 int
 splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data)
 {
-  return splay_tree_foreach_helper (sp, sp->root, fn, data);
+  return splay_tree_foreach_helper (sp->root, fn, data);
 }
 
 /* Splay-tree comparison function, treating the keys as ints.  */