aboutsummaryrefslogtreecommitdiff
path: root/libiberty/splay-tree.c
diff options
context:
space:
mode:
authorrth <rth@138bc75d-0d04-0410-961f-82ee72b054a4>2000-04-06 00:13:50 +0000
committerrth <rth@138bc75d-0d04-0410-961f-82ee72b054a4>2000-04-06 00:13:50 +0000
commit105211e51a9a46a5c59208118b83b880c31609d8 (patch)
tree3ef40d517c63bc11ebd2b75d3f99de5009ce3c18 /libiberty/splay-tree.c
parent4d92a225a02db2dc004391f9266c4b3b40bdf744 (diff)
* splay-tree.c (splay_tree_remove): New.
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@32949 138bc75d-0d04-0410-961f-82ee72b054a4
Diffstat (limited to 'libiberty/splay-tree.c')
-rw-r--r--libiberty/splay-tree.c41
1 files changed, 41 insertions, 0 deletions
diff --git a/libiberty/splay-tree.c b/libiberty/splay-tree.c
index 22ea07d84ad..de66d11bf56 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. */