2004-12-27 H.J. Lu <hongjiu.lu@intel.com>

[pf3gnuchains/gcc-fork.git] / libiberty / splay-tree.c

diff --git a/libiberty/splay-tree.c b/libiberty/splay-tree.c
index 3227ed3..b1410aa 100644 (file)
--- 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;
 
-  if (sp->delete_key)
-    (*sp->delete_key)(node->key);
-  if (sp->delete_value)
-    (*sp->delete_value)(node->value);
+  /* 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 (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
@@ -234,7 +275,7 @@ splay_tree_xmalloc_allocate (size, data)
      int size;
      void *data ATTRIBUTE_UNUSED;
 {
-  return xmalloc (size);
+  return (void *) xmalloc (size);
 }
 
 static void
@@ -472,7 +513,7 @@ splay_tree_predecessor (sp, key)
   if (comparison < 0)
     return sp->root;
 
-  /* Otherwise, find the leftmost element of the right subtree.  */
+  /* Otherwise, find the rightmost element of the left subtree.  */
   node = sp->root->left;
   if (node)
     while (node->right)
@@ -505,7 +546,7 @@ splay_tree_successor (sp, key)
   if (comparison > 0)
     return sp->root;
 
-  /* Otherwise, find the rightmost element of the left subtree.  */
+  /* Otherwise, find the leftmost element of the right subtree.  */
   node = sp->root->right;
   if (node)
     while (node->left)