This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
PATCH: Splay tree enhancements
- To: gcc-patches at gcc dot gnu dot org
- Subject: PATCH: Splay tree enhancements
- From: Mark Mitchell <mark at codesourcery dot com>
- Date: Sun, 10 Sep 2000 14:29:33 -0700
- Organization: CodeSourcery, LLC
This patch adds a little additional functionality to the splay-tree
implementation in libiberty. This stuff is required for my next
patch.
Bootstrapped, tested on i686-pc-linux-gnu.
--
Mark Mitchell mark@codesourcery.com
CodeSourcery, LLC http://www.codesourcery.com
2000-09-10 Mark Mitchell <mark@codesourcery.com>
* splay-tree.h (splay_tree_predecessor): Declare.
2000-09-10 Mark Mitchell <mark@codesourcery.com>
* splay-tree.c (splay_tree_predecessor): New function.
(splay_tree_successor): Likewise.
Index: include/splay-tree.h
===================================================================
RCS file: /cvs/gcc/egcs/include/splay-tree.h,v
retrieving revision 1.11
diff -c -p -r1.11 splay-tree.h
*** splay-tree.h 2000/04/06 00:12:41 1.11
--- splay-tree.h 2000/09/10 21:23:18
***************
*** 1,5 ****
/* A splay-tree datatype.
! Copyright (C) 1998 Free Software Foundation, Inc.
Contributed by Mark Mitchell (mark@markmitchell.com).
This file is part of GNU CC.
--- 1,5 ----
/* A splay-tree datatype.
! Copyright (C) 1998, 2000 Free Software Foundation, Inc.
Contributed by Mark Mitchell (mark@markmitchell.com).
This file is part of GNU CC.
*************** extern void splay_tree_remove PARAMS((s
*** 104,109 ****
--- 104,115 ----
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*));
Index: libiberty/splay-tree.c
===================================================================
RCS file: /cvs/gcc/egcs/libiberty/splay-tree.c,v
retrieving revision 1.13
diff -c -p -r1.13 splay-tree.c
*** splay-tree.c 2000/04/06 00:13:50 1.13
--- splay-tree.c 2000/09/10 21:23:18
***************
*** 1,5 ****
/* A splay-tree datatype.
! Copyright (C) 1998, 1999 Free Software Foundation, Inc.
Contributed by Mark Mitchell (mark@markmitchell.com).
This file is part of GNU CC.
--- 1,5 ----
/* A splay-tree datatype.
! Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
Contributed by Mark Mitchell (mark@markmitchell.com).
This file is part of GNU CC.
*************** splay_tree_lookup (sp, key)
*** 364,369 ****
--- 364,435 ----
return sp->root;
else
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