splay-tree.c (splay_tree_delete_helper): Redesign the logic so that recursion (and thus large stack space) is not needed.

* splay-tree.c (splay_tree_delete_helper): Redesign the logic so
that recursion (and thus large stack space) is not needed.

From-SVN: r91815

1 files changed, 48 insertions, 7 deletions

diff --git a/libiberty/splay-tree.c b/libiberty/splay-tree.c
index fc98db167f3..b1410aa3005 100644
--- a/libiberty/splay-tree.c
+++ b/libiberty/splay-tree.c
@@ -59,18 +59,59 @@ splay_tree_delete_helper (sp, node)
      splay_tree sp;
      splay_tree_node node;
 {
+  splay_tree_node pending = 0;
+  splay_tree_node active = 0;
+
   if (!node)
     return;
 
-  splay_tree_delete_helper (sp, node->left);
-  splay_tree_delete_helper (sp, node->right);
+#define KDEL(x)  if (sp->delete_key) (*sp->delete_key)(x);
+#define VDEL(x)  if (sp->delete_value) (*sp->delete_value)(x);
+
+  KDEL (node->key);
+  VDEL (node->value);
+
+  /* We use the "key" field to hold the "next" pointer.  */
+  node->key = (splay_tree_key)pending;
+  pending = (splay_tree_node)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 = 0;
+      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 (sp->delete_key)
-    (*sp->delete_key)(node->key);
-  if (sp->delete_value)
-    (*sp->delete_value)(node->value);
+	  if (active->left)
+	    {
+	      KDEL (active->left->key);
+	      VDEL (active->left->value);
+	      active->left->key = (splay_tree_key)pending;
+	      pending = (splay_tree_node)(active->left);
+	    }
+	  if (active->right)
+	    {
+	      KDEL (active->right->key);
+	      VDEL (active->right->value);
+	      active->right->key = (splay_tree_key)pending;
+	      pending = (splay_tree_node)(active->right);
+	    }
 
-  (*sp->deallocate) ((char*) node, sp->allocate_data);
+	  temp = active;
+	  active = (splay_tree_node)(temp->key);
+	  (*sp->deallocate) ((char*) temp, sp->allocate_data);
+	}
+    }
+#undef KDEL
+#undef VDEL
 }
 
 /* Help splay SP around KEY.  PARENT and GRANDPARENT are the parent