diff options
author | Richard Henderson <rth@redhat.com> | 2000-04-06 00:16:01 +0000 |
---|---|---|
committer | Richard Henderson <rth@redhat.com> | 2000-04-06 00:16:01 +0000 |
commit | afe36a788b035d8f582e69c2727385f33589004e (patch) | |
tree | bdb9ffd4904bf472e777bb31e722f79fde46b630 /libiberty | |
parent | 2664c1f9facea8d0b7f5a31f4822ff268ede3a8d (diff) | |
download | gdb-afe36a788b035d8f582e69c2727385f33589004e.zip gdb-afe36a788b035d8f582e69c2727385f33589004e.tar.gz gdb-afe36a788b035d8f582e69c2727385f33589004e.tar.bz2 |
* splay-tree.c (splay_tree_remove): New.
Diffstat (limited to 'libiberty')
-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 c858409..37c5658 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. + Thu Mar 16 01:33:58 2000 Jeffrey A Law (law@cygnus.com) * Makefile.in (partition.o): Depend on config.h 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. */ |