* splay-tree.h (splay_tree_max): New function.

	(splay_tree_min): Likewise.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@41895 138bc75d-0d04-0410-961f-82ee72b054a4

6 files changed, 90 insertions, 8 deletions

diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog
index 9030ae68f1d..37acdde8e69 100644
--- a/gcc/cp/ChangeLog
+++ b/gcc/cp/ChangeLog
@@ -1,3 +1,8 @@
+2001-05-07  Mark Mitchell  <mark@codesourcery.com>
+
+	* splay-tree.h (splay_tree_max): New function.
+	(splay_tree_min): Likewise.
+
 2001-05-03  Geoffrey Keating  <geoffk@redhat.com>
 
 	* cp-tree.h (enum cp_tree_index): Add CPTI_PFN_VFLAG_IDENTIFIER.
diff --git a/gcc/cp/class.c b/gcc/cp/class.c
index 17bf6211a95..52c43c38ba3 100644
--- a/gcc/cp/class.c
+++ b/gcc/cp/class.c
@@ -208,7 +208,7 @@ static tree dfs_get_primary_binfo PARAMS ((tree, void*));
 static int record_subobject_offset PARAMS ((tree, tree, splay_tree));
 static int check_subobject_offset PARAMS ((tree, tree, splay_tree));
 static int walk_subobject_offsets PARAMS ((tree, subobject_offset_fn,
-					   tree, splay_tree, int));
+					   tree, splay_tree, tree, int));
 static void record_subobject_offsets PARAMS ((tree, tree, splay_tree, int));
 static int layout_conflict_p PARAMS ((tree, tree, splay_tree, int));
 static int splay_tree_compare_integer_csts PARAMS ((splay_tree_key k1,
@@ -3822,20 +3822,30 @@ check_subobject_offset (type, offset, offsets)
 /* Walk through all the subobjects of TYPE (located at OFFSET).  Call
    F for every subobject, passing it the type, offset, and table of
    OFFSETS.  If VBASES_P is non-zero, then even virtual non-primary
-   bases should be traversed; otherwise, they are ignored.  If F
-   returns a non-zero value, the traversal ceases, and that value is
-   returned.  Otherwise, returns zero.  */
+   bases should be traversed; otherwise, they are ignored.  
+
+   If MAX_OFFSET is non-NULL, then subobjects with an offset greater
+   than MAX_OFFSET will not be walked.
+
+   If F returns a non-zero value, the traversal ceases, and that value
+   is returned.  Otherwise, returns zero.  */
 
 static int
-walk_subobject_offsets (type, f, offset, offsets, vbases_p)
+walk_subobject_offsets (type, f, offset, offsets, max_offset, vbases_p)
      tree type;
      subobject_offset_fn f;
      tree offset;
      splay_tree offsets;
+     tree max_offset;
      int vbases_p;
 {
   int r = 0;
 
+  /* If this OFFSET is bigger than the MAX_OFFSET, then we should
+     stop.  */
+  if (max_offset && INT_CST_LT (max_offset, offset))
+    return 0;
+
   if (CLASS_TYPE_P (type))
     {
       tree field;
@@ -3862,6 +3872,7 @@ walk_subobject_offsets (type, f, offset, offsets, vbases_p)
 						  offset,
 						  BINFO_OFFSET (binfo)),
 				      offsets,
+				      max_offset,
 				      vbases_p);
 	  if (r)
 	    return r;
@@ -3877,6 +3888,7 @@ walk_subobject_offsets (type, f, offset, offsets, vbases_p)
 						    offset,
 						    DECL_FIELD_OFFSET (field)),
 					offsets,
+					max_offset,
 					/*vbases_p=*/1);
 	    if (r)
 	      return r;
@@ -3896,11 +3908,17 @@ walk_subobject_offsets (type, f, offset, offsets, vbases_p)
 				      f,
 				      offset,
 				      offsets,
+				      max_offset,
 				      /*vbases_p=*/1);
 	  if (r)
 	    return r;
 	  offset = size_binop (PLUS_EXPR, offset, 
 			       TYPE_SIZE_UNIT (TREE_TYPE (type)));
+	  /* If this new OFFSET is bigger than the MAX_OFFSET, then
+	     there's no point in iterating through the remaining
+	     elements of the array.  */
+	  if (max_offset && INT_CST_LT (max_offset, offset))
+	    break;
 	}
     }
 
@@ -3919,7 +3937,7 @@ record_subobject_offsets (type, offset, offsets, vbases_p)
      int vbases_p;
 {
   walk_subobject_offsets (type, record_subobject_offset, offset,
-			  offsets, vbases_p);
+			  offsets, /*max_offset=*/NULL_TREE, vbases_p);
 }
 
 /* Returns non-zero if any of the empty subobjects of TYPE (located at
@@ -3933,8 +3951,19 @@ layout_conflict_p (type, offset, offsets, vbases_p)
      splay_tree offsets;
      int vbases_p;
 {
+  splay_tree_node max_node;
+
+  /* Get the node in OFFSETS that indicates the maximum offset where
+     an empty subobject is located.  */
+  max_node = splay_tree_max (offsets);
+  /* If there aren't any empty subobjects, then there's no point in
+     performing this check.  */
+  if (!max_node)
+    return 0;
+
   return walk_subobject_offsets (type, check_subobject_offset, offset,
-				 offsets, vbases_p);
+				 offsets, (tree) (max_node->key),
+				 vbases_p);
 }
 
 /* DECL is a FIELD_DECL corresponding either to a base subobject of a
diff --git a/include/ChangeLog b/include/ChangeLog
index f0a166c1766..e441ba93814 100644
--- a/include/ChangeLog
+++ b/include/ChangeLog
@@ -1,3 +1,8 @@
+2001-05-07  Mark Mitchell  <mark@codesourcery.com>
+
+	* splay-tree.h (splay_tree_max): New function.
+	(splay_tree_min): Likewise.
+
 2001-04-15  Daniel Berlin  <dan@cgsoftware.com>
 
 	* ternary.h: New file - Ternary search tree header.
diff --git a/include/splay-tree.h b/include/splay-tree.h
index e43d4b62eaa..37e9a35937f 100644
--- a/include/splay-tree.h
+++ b/include/splay-tree.h
@@ -110,6 +110,10 @@ extern splay_tree_node splay_tree_predecessor
 extern splay_tree_node splay_tree_successor
                                         PARAMS((splay_tree,
 						splay_tree_key));
+extern splay_tree_node splay_tree_max
+                                        PARAMS((splay_tree));
+extern splay_tree_node splay_tree_min
+                                        PARAMS((splay_tree));
 extern int splay_tree_foreach           PARAMS((splay_tree,
 					        splay_tree_foreach_fn,
 					        void*));
diff --git a/libiberty/ChangeLog b/libiberty/ChangeLog
index 53e4290dd30..9f635430edc 100644
--- a/libiberty/ChangeLog
+++ b/libiberty/ChangeLog
@@ -1,3 +1,8 @@
+2001-05-07  Mark Mitchell  <mark@codesourcery.com>
+
+	* splay-tree.h (splay_tree_max): New function.
+	(splay_tree_min): Likewise.
+
 2001-04-15  Daniel Berlin  <dan@cgsoftware.com>
 
 	* ternary.c: New file - Ternary search tree implementation.
diff --git a/libiberty/splay-tree.c b/libiberty/splay-tree.c
index 52b57c088a7..a7123952671 100644
--- a/libiberty/splay-tree.c
+++ b/libiberty/splay-tree.c
@@ -1,5 +1,5 @@
 /* A splay-tree datatype.  
-   Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
+   Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
    Contributed by Mark Mitchell (mark@markmitchell.com).
 
 This file is part of GNU CC.
@@ -368,6 +368,40 @@ splay_tree_lookup (sp, key)
     return 0;
 }
 
+/* Return the node in SP with the greatest key.  */
+
+splay_tree_node
+splay_tree_max (sp)
+     splay_tree sp;
+{
+  splay_tree_node n = sp->root;
+
+  if (!n)
+    return NULL;
+
+  while (n->right)
+    n = n->right;
+
+  return n;
+}
+
+/* Return the node in SP with the smallest key.  */
+
+splay_tree_node
+splay_tree_min (sp)
+     splay_tree sp;
+{
+  splay_tree_node n = sp->root;
+
+  if (!n)
+    return NULL;
+
+  while (n->left)
+    n = n->left;
+
+  return n;
+}
+
 /* Return the immediate predecessor KEY, or NULL if there is no
    predecessor.  KEY need not be present in the tree.  */