diff options
| -rw-r--r-- | libiberty/ChangeLog | 4 | ||||
| -rw-r--r-- | libiberty/splay-tree.c | 41 |
2 files changed, 45 insertions, 0 deletions
diff --git a/libiberty/ChangeLog b/libiberty/ChangeLog index e51cea6..d78a86a 100644 --- a/libiberty/ChangeLog +++ b/libiberty/ChangeLog @@ -1,3 +1,7 @@ +2000-04-05 Richard Henderson <rth@cygnus.com> + + * splay-tree.c (splay_tree_remove): New. + 2000-03-30 Mark Mitchell <mark@codesourcery.com> * hashtab.c (find_empty_slot_for_expand): Use hashval_t for hash diff --git a/libiberty/splay-tree.c b/libiberty/splay-tree.c index 22ea07d..de66d11 100644 --- a/libiberty/splay-tree.c +++ b/libiberty/splay-tree.c @@ -309,6 +309,47 @@ splay_tree_insert (sp, key, value) return sp->root; } +/* Remove KEY from SP. It is not an error if it did not exist. */ + +void +splay_tree_remove (sp, key) + splay_tree sp; + splay_tree_key key; +{ + splay_tree_splay (sp, key); + + if (sp->root && (*sp->comp) (sp->root->key, key) == 0) + { + splay_tree_node left, right; + + left = sp->root->left; + right = sp->root->right; + + /* Delete the root node itself. */ + if (sp->delete_value) + (*sp->delete_value) (sp->root->value); + free (sp->root); + + /* One of the children is now the root. Doesn't matter much + which, so long as we preserve the properties of the tree. */ + if (left) + { + sp->root = left; + + /* If there was a right child as well, hang it off the + right-most leaf of the left child. */ + if (right) + { + while (left->right) + left = left->right; + left->right = right; + } + } + else + sp->root = right; + } +} + /* Lookup KEY in SP, returning VALUE if present, and NULL otherwise. */ |