diff options
Diffstat (limited to 'libiberty/splay-tree.c')
| -rw-r--r-- | libiberty/splay-tree.c | 72 |
1 files changed, 69 insertions, 3 deletions
diff --git a/libiberty/splay-tree.c b/libiberty/splay-tree.c index 609cd68..52b57c0 100644 --- a/libiberty/splay-tree.c +++ b/libiberty/splay-tree.c @@ -1,5 +1,5 @@ /* A splay-tree datatype. - Copyright (C) 1998, 1999 Free Software Foundation, Inc. + Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc. Contributed by Mark Mitchell (mark@markmitchell.com). This file is part of GNU CC. @@ -305,8 +305,8 @@ splay_tree_insert (sp, key, value) node->right->left = 0; } - sp->root = node; - } + sp->root = node; + } return sp->root; } @@ -368,6 +368,72 @@ splay_tree_lookup (sp, key) return 0; } +/* Return the immediate predecessor KEY, or NULL if there is no + predecessor. KEY need not be present in the tree. */ + +splay_tree_node +splay_tree_predecessor (sp, key) + splay_tree sp; + splay_tree_key key; +{ + int comparison; + splay_tree_node node; + + /* If the tree is empty, there is certainly no predecessor. */ + if (!sp->root) + return NULL; + + /* Splay the tree around KEY. That will leave either the KEY + itself, its predecessor, or its successor at the root. */ + splay_tree_splay (sp, key); + comparison = (*sp->comp)(sp->root->key, key); + + /* If the predecessor is at the root, just return it. */ + if (comparison < 0) + return sp->root; + + /* Otherwise, find the leftmost element of the right subtree. */ + node = sp->root->left; + if (node) + while (node->right) + node = node->right; + + return node; +} + +/* Return the immediate successor KEY, or NULL if there is no + predecessor. KEY need not be present in the tree. */ + +splay_tree_node +splay_tree_successor (sp, key) + splay_tree sp; + splay_tree_key key; +{ + int comparison; + splay_tree_node node; + + /* If the tree is empty, there is certainly no predecessor. */ + if (!sp->root) + return NULL; + + /* Splay the tree around KEY. That will leave either the KEY + itself, its predecessor, or its successor at the root. */ + splay_tree_splay (sp, key); + comparison = (*sp->comp)(sp->root->key, key); + + /* If the successor is at the root, just return it. */ + if (comparison > 0) + return sp->root; + + /* Otherwise, find the rightmost element of the left subtree. */ + node = sp->root->right; + if (node) + while (node->left) + node = node->left; + + return node; +} + /* Call FN, passing it the DATA, for every node in SP, following an in-order traversal. If FN every returns a non-zero value, the iteration ceases immediately, and the value is returned. |