This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

PATCH: Splay tree enhancements



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

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]