diff options
Diffstat (limited to 'libiberty/splay-tree.c')
| -rw-r--r-- | libiberty/splay-tree.c | 55 |
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 |