From 508f18c8cfcf812f41173c35b744d20f6a4fd1e6 Mon Sep 17 00:00:00 2001
From: mmitchel
Date: Sun, 10 Sep 2000 21:28:21 +0000
Subject: [PATCH] * 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.
--
2.11.0