cp-tree.h (struct lang_decl): Added field for storing sorted FIELD_DECLs (used in TYPE_DECLs).

	* cp-tree.h (struct lang_decl): Added field for storing sorted
	FIELD_DECLs (used in TYPE_DECLs).
	(DECL_PENDING_INLINE_INFO): Adjusted to use 'u' union.
	(DECL_SORTED_FIELDS): New macro.
	* class.c (method_name_cmp): New function.
	(finish_struct_methods): Modified to support sorting and searching
	methods.
	(finish_struct_anon): Changed code in inner loop to use ELT rather
	than UELT (which required an extra indirection for every reference).
	(field_decl_cmp): New function to support sorting FIELD_DECLs.
	(finish_struct_1): Sort fields.
	* search.c (lookup_field_1): Use DECL_SORTED_FIELDS if we have them.
	(lookup_fnfields_1): Search sorted methods in METHOD_VEC.
	Also, switch to using array indexing rather than a changing pointer.
	* ptree.c (print_lang_decl): Handle TYPE_DECLs that have
	DECL_SORTED_FIELDS.

Co-Authored-By: Jason Merrill <jason@yorick.cygnus.com>

From-SVN: r28046

5 files changed, 248 insertions, 44 deletions

diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog
index ff27a47..6edfa5f 100644
--- a/gcc/cp/ChangeLog
+++ b/gcc/cp/ChangeLog
@@ -1,3 +1,23 @@
+1999-07-09  Michael Tiemann  <tiemann@happy.cygnus.com>
+	    Jason Merrill  <jason@yorick.cygnus.com>
+
+	* cp-tree.h (struct lang_decl): Added field for storing sorted
+	FIELD_DECLs (used in TYPE_DECLs).
+	(DECL_PENDING_INLINE_INFO): Adjusted to use 'u' union.
+	(DECL_SORTED_FIELDS): New macro.
+	* class.c (method_name_cmp): New function.
+	(finish_struct_methods): Modified to support sorting and searching
+	methods.
+	(finish_struct_anon): Changed code in inner loop to use ELT rather 
+	than UELT (which required an extra indirection for every reference).
+	(field_decl_cmp): New function to support sorting FIELD_DECLs.
+	(finish_struct_1): Sort fields.
+	* search.c (lookup_field_1): Use DECL_SORTED_FIELDS if we have them.
+	(lookup_fnfields_1): Search sorted methods in METHOD_VEC.
+	Also, switch to using array indexing rather than a changing pointer.
+	* ptree.c (print_lang_decl): Handle TYPE_DECLs that have
+	DECL_SORTED_FIELDS.
+
 1999-07-09  Jason Merrill  <jason@yorick.cygnus.com>
 
 	* decl2.c (reparse_absdcl_as_casts): Don't warn about old-style
diff --git a/gcc/cp/class.c b/gcc/cp/class.c
index 4d00dfb..6a25b59 100644
--- a/gcc/cp/class.c
+++ b/gcc/cp/class.c
@@ -130,6 +130,8 @@ static void modify_all_indirect_vtables PROTO((tree, int, int, tree,
 static int finish_base_struct PROTO((tree, struct base_info *));
 static void finish_struct_methods PROTO((tree));
 static void maybe_warn_about_overly_private_class PROTO ((tree));
+static int field_decl_cmp PROTO ((const tree *, const tree *));
+static int method_name_cmp PROTO ((const tree *, const tree *));
 static tree make_method_vec PROTO((int));
 static void free_method_vec PROTO((tree));
 static tree add_implicitly_declared_members PROTO((tree, int, int, int));
@@ -2004,6 +2006,39 @@ maybe_warn_about_overly_private_class (t)
     }
 }
 
+/* Function to help qsort sort FIELD_DECLs by name order.  */
+
+static int
+field_decl_cmp (x, y)
+     const tree *x, *y;
+{
+  if (DECL_NAME (*x) == DECL_NAME (*y))
+    return 0;
+  if (DECL_NAME (*x) == NULL_TREE)
+    return -1;
+  if (DECL_NAME (*y) == NULL_TREE)
+    return 1;
+  if (DECL_NAME (*x) < DECL_NAME (*y))
+    return -1;
+  return 1;
+}
+
+/* Comparison function to compare two TYPE_METHOD_VEC entries by name.  */
+
+static int
+method_name_cmp (m1, m2)
+     const tree *m1, *m2;
+{
+  if (*m1 == NULL_TREE && *m2 == NULL_TREE)
+    return 0;
+  if (*m1 == NULL_TREE)
+    return -1;
+  if (*m2 == NULL_TREE)
+    return 1;
+  if (DECL_NAME (OVL_CURRENT (*m1)) < DECL_NAME (OVL_CURRENT (*m2)))
+    return -1;
+  return 1;
+}
 
 /* Warn about duplicate methods in fn_fields.  Also compact method
    lists so that lookup can be made faster.
@@ -2020,10 +2055,11 @@ maybe_warn_about_overly_private_class (t)
    If there are any constructors/destructors, they are moved to the
    front of the list.  This makes pushclass more efficient.
 
-   We also link each field which has shares a name with its baseclass
-   to the head of the list of fields for that base class.  This allows
-   us to reduce search time in places like `build_method_call' to
-   consider only reasonably likely functions.   */
+   @@ The above comment is obsolete.  It mostly describes what add_method
+   @@ and add_implicitly_declared_members do.
+
+   Sort methods that are not special (i.e., constructors, destructors, and
+   type conversion operators) so that we can find them faster in search.  */
 
 static void
 finish_struct_methods (t)
@@ -2032,6 +2068,7 @@ finish_struct_methods (t)
   tree fn_fields;
   tree method_vec = CLASSTYPE_METHOD_VEC (t);
   tree ctor_name = constructor_name (t);
+  int slot, len = method_vec ? TREE_VEC_LENGTH (method_vec) : 0;
 
   /* First fill in entry 0 with the constructors, entry 1 with destructors,
      and the next few with type conversion operators (if any).  */
@@ -2089,7 +2126,28 @@ finish_struct_methods (t)
     
   /* Issue warnings about private constructors and such.  If there are
      no methods, then some public defaults are generated.  */
-  maybe_warn_about_overly_private_class (t); 
+  maybe_warn_about_overly_private_class (t);
+
+  if (method_vec == NULL_TREE)
+    return;
+
+  /* Now sort the methods.  */
+  while (len > 2 && TREE_VEC_ELT (method_vec, len-1) == NULL_TREE)
+    len--;
+  TREE_VEC_LENGTH (method_vec) = len;
+
+  /* The type conversion ops have to live at the front of the vec, so we
+     can't sort them.  */
+  for (slot = 2; slot < len; ++slot)
+    {
+      tree fn = TREE_VEC_ELT (method_vec, slot);
+  
+      if (!DECL_CONV_FN_P (OVL_CURRENT (fn)))
+	break;
+    }
+  if (len - slot > 1)
+    qsort (&TREE_VEC_ELT (method_vec, slot), len-slot, sizeof (tree),
+	   (int (*)(const void *, const void *))method_name_cmp);
 }
 
 /* Emit error when a duplicate definition of a type is seen.  Patch up.  */
@@ -2950,6 +3008,7 @@ finish_struct_anon (t)
      tree t;
 {
   tree field;
+
   for (field = TYPE_FIELDS (t); field; field = TREE_CHAIN (field))
     {
       if (TREE_STATIC (field))
@@ -2960,32 +3019,32 @@ finish_struct_anon (t)
       if (DECL_NAME (field) == NULL_TREE
 	  && ANON_AGGR_TYPE_P (TREE_TYPE (field)))
 	{
-	  tree* uelt = &TYPE_FIELDS (TREE_TYPE (field));
-	  for (; *uelt; uelt = &TREE_CHAIN (*uelt))
+	  tree elt = TYPE_FIELDS (TREE_TYPE (field));
+	  for (; elt; elt = TREE_CHAIN (elt))
 	    {
-	      if (DECL_ARTIFICIAL (*uelt))
+	      if (DECL_ARTIFICIAL (elt))
 		continue;
 
-	      if (DECL_NAME (*uelt) == constructor_name (t))
+	      if (DECL_NAME (elt) == constructor_name (t))
 		cp_pedwarn_at ("ANSI C++ forbids member `%D' with same name as enclosing class",
-			       *uelt);
+			       elt);
 
-	      if (TREE_CODE (*uelt) != FIELD_DECL)
+	      if (TREE_CODE (elt) != FIELD_DECL)
 		{
 		  cp_pedwarn_at ("`%#D' invalid; an anonymous union can only have non-static data members",
-				 *uelt);
+				 elt);
 		  continue;
 		}
 
-	      if (TREE_PRIVATE (*uelt))
+	      if (TREE_PRIVATE (elt))
 		cp_pedwarn_at ("private member `%#D' in anonymous union",
-			       *uelt);
-	      else if (TREE_PROTECTED (*uelt))
+			       elt);
+	      else if (TREE_PROTECTED (elt))
 		cp_pedwarn_at ("protected member `%#D' in anonymous union",
-			       *uelt);
+			       elt);
 
-	      TREE_PRIVATE (*uelt) = TREE_PRIVATE (field);
-	      TREE_PROTECTED (*uelt) = TREE_PROTECTED (field);
+	      TREE_PRIVATE (elt) = TREE_PRIVATE (field);
+	      TREE_PROTECTED (elt) = TREE_PROTECTED (field);
 	    }
 	}
     }
@@ -3077,6 +3136,44 @@ add_implicitly_declared_members (t, cant_have_default_ctor,
   return virtual_dtor;
 }
 
+/* Subroutine of finish_struct_1.  Recursively count the number of fields
+   in TYPE, including anonymous union members.  */
+
+static int
+count_fields (fields)
+     tree fields;
+{
+  tree x;
+  int n_fields = 0;
+  for (x = fields; x; x = TREE_CHAIN (x))
+    {
+      if (TREE_CODE (x) == FIELD_DECL && ANON_AGGR_TYPE_P (TREE_TYPE (x)))
+	n_fields += count_fields (TYPE_FIELDS (TREE_TYPE (x)));
+      else
+	n_fields += 1;
+    }
+  return n_fields;
+}
+
+/* Subroutine of finish_struct_1.  Recursively add all the fields in the
+   TREE_LIST FIELDS to the TREE_VEC FIELD_VEC, starting at offset IDX.  */
+
+static int
+add_fields_to_vec (fields, field_vec, idx)
+     tree fields, field_vec;
+     int idx;
+{
+  tree x;
+  for (x = fields; x; x = TREE_CHAIN (x))
+    {
+      if (TREE_CODE (x) == FIELD_DECL && ANON_AGGR_TYPE_P (TREE_TYPE (x)))
+	idx = add_fields_to_vec (TYPE_FIELDS (TREE_TYPE (x)), field_vec, idx);
+      else
+	TREE_VEC_ELT (field_vec, idx++) = x;
+    }
+  return idx;
+}
+
 /* Create a RECORD_TYPE or UNION_TYPE node for a C struct or union declaration
    (or C++ class declaration).
 
@@ -3125,6 +3222,7 @@ finish_struct_1 (t, warn_anon)
   int cant_have_const_ctor;
   int no_const_asn_ref;
   int has_mutable = 0;
+  int n_fields = 0;
 
   /* The index of the first base class which has virtual
      functions.  Only applied to non-virtual baseclasses.  */
@@ -4008,6 +4106,28 @@ finish_struct_1 (t, warn_anon)
 	}
     }
 
+  /* Done with FIELDS...now decide whether to sort these for
+     faster lookups later.  Don't worry about optimizing
+     for structs only declared in inline functions...they're
+     not going to be referenced anywhere else.
+
+     The C front-end only does this when n_fields > 15.  We use
+     a smaller number because most searches fail (succeeding
+     ultimately as the search bores through the inheritance
+     hierarchy), and we want this failure to occur quickly.  */
+
+  n_fields = count_fields (fields);
+  if (n_fields > 7 && !allocation_temporary_p ())
+    {
+      tree field_vec = make_tree_vec (n_fields);
+      add_fields_to_vec (fields, field_vec, 0);
+      qsort (&TREE_VEC_ELT (field_vec, 0), n_fields, sizeof (tree),
+	     (int (*)(const void *, const void *))field_decl_cmp);
+      if (! DECL_LANG_SPECIFIC (TYPE_MAIN_DECL (t)))
+	retrofit_lang_decl (TYPE_MAIN_DECL (t));
+      DECL_SORTED_FIELDS (TYPE_MAIN_DECL (t)) = field_vec;
+    }
+
   if (TYPE_HAS_CONSTRUCTOR (t))
     {
       tree vfields = CLASSTYPE_VFIELDS (t);
diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index cfbe202..f32eea8 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -1194,7 +1194,11 @@ struct lang_decl
 
   tree main_decl_variant;
   tree befriending_classes;
-  struct pending_inline *pending_inline_info;
+  union
+  {
+    tree sorted_fields;
+    struct pending_inline *pending_inline_info;
+  } u;
 };
 
 /* Non-zero if NODE is a _DECL with TREE_READONLY set.  */
@@ -1379,7 +1383,11 @@ struct lang_decl
 /* For a FUNCTION_DECL: if this function was declared inline inside of
    a class declaration, this is where the text for the function is
    squirreled away.  */
-#define DECL_PENDING_INLINE_INFO(NODE) (DECL_LANG_SPECIFIC(NODE)->pending_inline_info)
+#define DECL_PENDING_INLINE_INFO(NODE) (DECL_LANG_SPECIFIC(NODE)->u.pending_inline_info)
+
+/* For a TYPE_DECL: if this function has many fields, we'll sort them
+   and put them into a TREE_VEC. */
+#define DECL_SORTED_FIELDS(NODE) (DECL_LANG_SPECIFIC(NODE)->u.sorted_fields)
 
 /* True if on the saved_inlines (see decl2.c) list.  */
 #define DECL_SAVED_INLINE(DECL) \
diff --git a/gcc/cp/ptree.c b/gcc/cp/ptree.c
index 4008e39..3c84864 100644
--- a/gcc/cp/ptree.c
+++ b/gcc/cp/ptree.c
@@ -48,11 +48,18 @@ print_lang_decl (file, node, indent)
       fprintf (file, " decl-main-variant ");
       fprintf (file, HOST_PTR_PRINTF, DECL_MAIN_VARIANT (node));
     }
-  if (DECL_PENDING_INLINE_INFO (node))
+  if (TREE_CODE (node) == FUNCTION_DECL
+      && DECL_PENDING_INLINE_INFO (node))
     {
       fprintf (file, " pending-inline-info ");
       fprintf (file, HOST_PTR_PRINTF, DECL_PENDING_INLINE_INFO (node));
     }
+  if (TREE_CODE (node) == TYPE_DECL
+      && DECL_SORTED_FIELDS (node))
+    {
+      fprintf (file, " sorted-fields ");
+      fprintf (file, HOST_PTR_PRINTF, DECL_SORTED_FIELDS (node));
+    }
   if (DECL_TEMPLATE_INFO (node))
     {
       fprintf (file, " template-info ");
diff --git a/gcc/cp/search.c b/gcc/cp/search.c
index f2e9aa7..0fe5cf4 100644
--- a/gcc/cp/search.c
+++ b/gcc/cp/search.c
@@ -522,6 +522,32 @@ lookup_field_1 (type, name)
        of fields!)  */
     return NULL_TREE;
 
+  if (TYPE_NAME (type)
+      && DECL_LANG_SPECIFIC (TYPE_NAME (type))
+      && DECL_SORTED_FIELDS (TYPE_NAME (type)))
+    {
+      tree *fields = &TREE_VEC_ELT (DECL_SORTED_FIELDS (TYPE_NAME (type)), 0);
+      int lo = 0, hi = TREE_VEC_LENGTH (DECL_SORTED_FIELDS (TYPE_NAME (type)));
+      int i;
+
+      while (lo < hi)
+	{
+	  i = (lo + hi) / 2;
+
+#ifdef GATHER_STATISTICS
+	  n_fields_searched++;
+#endif /* GATHER_STATISTICS */
+
+	  if (DECL_NAME (fields[i]) > name)
+	    hi = i;
+	  else if (DECL_NAME (fields[i]) < name)
+	    lo = i + 1;
+	  else
+	    return fields[i];
+	}
+      return NULL_TREE;
+    }
+
   field = TYPE_FIELDS (type);
 
 #ifdef GATHER_STATISTICS
@@ -1502,61 +1528,84 @@ int
 lookup_fnfields_1 (type, name)
      tree type, name;
 {
-  register tree method_vec 
+  tree method_vec 
     = CLASS_TYPE_P (type) ? CLASSTYPE_METHOD_VEC (type) : NULL_TREE;
 
   if (method_vec != 0)
     {
+      register int i;
       register tree *methods = &TREE_VEC_ELT (method_vec, 0);
-      register tree *end = TREE_VEC_END (method_vec);
+      int len = TREE_VEC_LENGTH (method_vec);
+      tree tmp;
 
 #ifdef GATHER_STATISTICS
       n_calls_lookup_fnfields_1++;
 #endif /* GATHER_STATISTICS */
 
       /* Constructors are first...  */
-      if (*methods && name == ctor_identifier)
-	return 0;
+      if (name == ctor_identifier)
+	return methods[0] ? 0 : -1;
 
       /* and destructors are second.  */
-      if (*++methods && name == dtor_identifier)
-	return 1;
+      if (name == dtor_identifier)
+	return methods[1] ? 1 : -1;
 
-      while (++methods != end && *methods)
+      for (i = 2; i < len && methods[i]; ++i)
 	{
 #ifdef GATHER_STATISTICS
 	  n_outer_fields_searched++;
 #endif /* GATHER_STATISTICS */
-	  if (DECL_NAME (OVL_CURRENT (*methods)) == name)
-	    break;
+
+	  tmp = OVL_CURRENT (methods[i]);
+	  if (DECL_NAME (tmp) == name)
+	    return i;
+
+	  /* If the type is complete and we're past the conversion ops,
+	     switch to binary search.  */
+	  if (! DECL_CONV_FN_P (tmp)
+	      && TYPE_SIZE (type))
+	    {
+	      int lo = i + 1, hi = len;
+
+	      while (lo < hi)
+		{
+		  i = (lo + hi) / 2;
+
+#ifdef GATHER_STATISTICS
+		  n_outer_fields_searched++;
+#endif /* GATHER_STATISTICS */
+
+		  tmp = DECL_NAME (OVL_CURRENT (methods[i]));
+
+		  if (tmp > name)
+		    hi = i;
+		  else if (tmp < name)
+		    lo = i + 1;
+		  else
+		    return i;
+		}
+	      break;
+	    }
 	}
 
       /* If we didn't find it, it might have been a template
 	 conversion operator.  (Note that we don't look for this case
 	 above so that we will always find specializations first.)  */
-      if ((methods == end || !*methods)
-	  && IDENTIFIER_TYPENAME_P (name)) 
+      if (IDENTIFIER_TYPENAME_P (name)) 
 	{
-	  methods = &TREE_VEC_ELT (method_vec, 0) + 1;
-	  
-	  while (++methods != end && *methods)
+	  for (i = 2; i < len && methods[i]; ++i)
 	    {
-	      tree method_name = DECL_NAME (OVL_CURRENT (*methods));
-
-	      if (!IDENTIFIER_TYPENAME_P (method_name))
+	      tmp = OVL_CURRENT (methods[i]);
+	      if (! DECL_CONV_FN_P (tmp))
 		{
 		  /* Since all conversion operators come first, we know
 		     there is no such operator.  */
-		  methods = end;
 		  break;
 		}
-	      else if (TREE_CODE (OVL_CURRENT (*methods)) == TEMPLATE_DECL)
-		break;
+	      else if (TREE_CODE (tmp) == TEMPLATE_DECL)
+		return i;
 	    }
 	}
-
-      if (methods != end && *methods)
-	return methods - &TREE_VEC_ELT (method_vec, 0);
     }
 
   return -1;