aboutsummaryrefslogtreecommitdiff
path: root/libiberty
diff options
context:
space:
mode:
authorDJ Delorie <dj@redhat.com>2004-12-07 20:02:09 +0000
committerDJ Delorie <dj@redhat.com>2004-12-07 20:02:09 +0000
commit9923bc337ee5e5b60737d770281d42a157c24c81 (patch)
tree87a7e6ebb41457d292cddfdbc460c731111e1691 /libiberty
parenta7be7fa8ef6853dcaf3f609ee31725423a7674ef (diff)
downloadgdb-9923bc337ee5e5b60737d770281d42a157c24c81.zip
gdb-9923bc337ee5e5b60737d770281d42a157c24c81.tar.gz
gdb-9923bc337ee5e5b60737d770281d42a157c24c81.tar.bz2
merge from gcc
Diffstat (limited to 'libiberty')
-rw-r--r--libiberty/ChangeLog5
-rw-r--r--libiberty/splay-tree.c55
2 files changed, 53 insertions, 7 deletions
diff --git a/libiberty/ChangeLog b/libiberty/ChangeLog
index b053857..378ee0a 100644
--- a/libiberty/ChangeLog
+++ b/libiberty/ChangeLog
@@ -1,3 +1,8 @@
+2004-12-07 DJ Delorie <dj@redhat.com>
+
+ * splay-tree.c (splay_tree_delete_helper): Redesign the logic so
+ that recursion (and thus large stack space) is not needed.
+
2004-11-29 Matt Kraai <kraai@alumni.cmu.edu>
* pex-unix.c: Fix the spelling of longjmp.
diff --git a/libiberty/splay-tree.c b/libiberty/splay-tree.c
index fc98db1..b1410aa 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