diff options
author | Richard Henderson <rth@cygnus.com> | 2000-04-05 17:13:50 -0700 |
---|---|---|
committer | Richard Henderson <rth@gcc.gnu.org> | 2000-04-05 17:13:50 -0700 |
commit | dc17cc7bec37abf304ec63ab053a5f8a47d2aeb9 (patch) | |
tree | 3ef40d517c63bc11ebd2b75d3f99de5009ce3c18 | |
parent | aa5a5f0272e1ca829e8fd9ade1e3eea5b0926f46 (diff) | |
download | gcc-dc17cc7bec37abf304ec63ab053a5f8a47d2aeb9.zip gcc-dc17cc7bec37abf304ec63ab053a5f8a47d2aeb9.tar.gz gcc-dc17cc7bec37abf304ec63ab053a5f8a47d2aeb9.tar.bz2 |
* splay-tree.c (splay_tree_remove): New.
From-SVN: r32949
-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. */ |