aboutsummaryrefslogtreecommitdiff
path: root/libiberty/splay-tree.c
diff options
context:
space:
mode:
authorRichard Henderson <rth@redhat.com>2000-04-06 00:16:01 +0000
committerRichard Henderson <rth@redhat.com>2000-04-06 00:16:01 +0000
commitafe36a788b035d8f582e69c2727385f33589004e (patch)
treebdb9ffd4904bf472e777bb31e722f79fde46b630 /libiberty/splay-tree.c
parent2664c1f9facea8d0b7f5a31f4822ff268ede3a8d (diff)
downloadgdb-afe36a788b035d8f582e69c2727385f33589004e.zip
gdb-afe36a788b035d8f582e69c2727385f33589004e.tar.gz
gdb-afe36a788b035d8f582e69c2727385f33589004e.tar.bz2
* splay-tree.c (splay_tree_remove): New.
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 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. */