aboutsummaryrefslogtreecommitdiff
path: root/libiberty/splay-tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'libiberty/splay-tree.c')
-rw-r--r--libiberty/splay-tree.c55
1 files changed, 48 insertions, 7 deletions
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