From 508f18c8cfcf812f41173c35b744d20f6a4fd1e6 Mon Sep 17 00:00:00 2001 From: mmitchel Date: Sun, 10 Sep 2000 21:28:21 +0000 Subject: * splay-tree.h (splay_tree_predecessor): Declare. * splay-tree.c (splay_tree_predecessor): New function. (splay_tree_successor): Likewise. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@36304 138bc75d-0d04-0410-961f-82ee72b054a4 --- include/ChangeLog | 4 +++ include/splay-tree.h | 8 +++++- libiberty/ChangeLog | 5 ++++ libiberty/splay-tree.c | 68 +++++++++++++++++++++++++++++++++++++++++++++++++- 4 files changed, 83 insertions(+), 2 deletions(-) diff --git a/include/ChangeLog b/include/ChangeLog index 95a00be6eef..30f281e11a7 100644 --- a/include/ChangeLog +++ b/include/ChangeLog @@ -1,3 +1,7 @@ +2000-09-10 Mark Mitchell + + * splay-tree.h (splay_tree_predecessor): Declare. + 2000-09-05 John David Anglin * md5.h (md5_uint32): Choose via INT_MAX instead of UINT_MAX. diff --git a/include/splay-tree.h b/include/splay-tree.h index 39882a4beac..f53f855767b 100644 --- a/include/splay-tree.h +++ b/include/splay-tree.h @@ -1,5 +1,5 @@ /* A splay-tree datatype. - Copyright (C) 1998 Free Software Foundation, Inc. + Copyright (C) 1998, 2000 Free Software Foundation, Inc. Contributed by Mark Mitchell (mark@markmitchell.com). This file is part of GNU CC. @@ -104,6 +104,12 @@ extern void splay_tree_remove PARAMS((splay_tree, extern splay_tree_node splay_tree_lookup PARAMS((splay_tree, splay_tree_key)); +extern splay_tree_node splay_tree_predecessor + PARAMS((splay_tree, + splay_tree_key)); +extern splay_tree_node splay_tree_successor + PARAMS((splay_tree, + splay_tree_key)); extern int splay_tree_foreach PARAMS((splay_tree, splay_tree_foreach_fn, void*)); diff --git a/libiberty/ChangeLog b/libiberty/ChangeLog index 4b5923e284b..ee879c4ca8b 100644 --- a/libiberty/ChangeLog +++ b/libiberty/ChangeLog @@ -1,3 +1,8 @@ +2000-09-10 Mark Mitchell + + * splay-tree.c (splay_tree_predecessor): New function. + (splay_tree_successor): Likewise. + 2000-09-10 Hans-Peter Nilsson * testsuite/demangle-expected: Add four tests for type_info diff --git a/libiberty/splay-tree.c b/libiberty/splay-tree.c index de66d11bf56..9a684899d4a 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. @@ -366,6 +366,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 rightmost element of the left 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. -- cgit v1.2.3