re PR c/10962 (lookup_field is a linear search on a linked list (can be slow if large struct))

2003-07-16  Andrew Pinski  <pinskia@physics.uc.edu>
ChangeLog:
        PR c/10962
        * ggc.h: Add header guards.
        * c-decl.c (finish_struct): Sort fields if
        number greater than 15 and there are no
        anonymous structs/unions.
        * c-common.h: Include ggc.h.
        (sorted_fields_type): New struct.
        (field_decl_cmp): New prototype.
        (resort_sorted_fields): New prototype.
        (DECL_DECLARES_TYPE_NON_TEMPLATE_P): New macro.
        * c-tree.h: (lang_type): Use pointer to sorted_fields_type
        as s, removing other fields.
        * c-typeck.c (lookup_field): Use s in lang_type.
        These were mostly moved from cp/class.c:
        * c-common.c (field_decl_cmp): New static function.
        (field_decl_cmp): New function.
        (resort_sorted_fields): New function.
cp/ChangeLog:
        * class.c (field_decl_cmp): Remove.
        (resort_field_decl_cmp): Remove.
        (resort_sorted_fields): Remove.
        (add_fields_to_vec): Rename to ...
        (add_fields_to_record_type): this.
        (finish_struct_1): Change to be using
        sorted_fields_type's fields.
        * cp-tree.h (lang_decl): In lang_decl_u3
        change sorted_fields to be a pointer to
        sorted_fields_type.
        (resort_sorted_fields): Remove prototype.
        * search.c (lookup_field_1): Change to be using
        sorted_fields_type's fields.

From-SVN: r69470

4 files changed, 30 insertions, 76 deletions

diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog
index 68bcb3a..e231e8b 100644
--- a/gcc/cp/ChangeLog
+++ b/gcc/cp/ChangeLog
@@ -1,3 +1,20 @@
+2003-07-16  Andrew Pinski  <pinskia@physics.uc.edu>
+
+	PR c/10962
+	* class.c (field_decl_cmp): Remove.
+	(resort_field_decl_cmp): Remove.
+	(resort_sorted_fields): Remove.
+	(add_fields_to_vec): Rename to ...
+	(add_fields_to_record_type): this.
+	(finish_struct_1): Change to be using
+	sorted_fields_type's fields.
+	* cp-tree.h (lang_decl): In lang_decl_u3
+	change sorted_fields to be a pointer to
+	sorted_fields_type.
+	(resort_sorted_fields): Remove prototype.
+	* search.c (lookup_field_1): Change to be using
+	sorted_fields_type's fields.
+
 2003-07-16  Kriang Lerdsuwanakij  <lerdsuwa@users.sourceforge.net>
 
 	PR c++/5421
diff --git a/gcc/cp/class.c b/gcc/cp/class.c
index 5674590..ca22d82 100644
--- a/gcc/cp/class.c
+++ b/gcc/cp/class.c
@@ -124,8 +124,6 @@ static tree modify_all_vtables (tree, tree);
 static void determine_primary_base (tree);
 static void finish_struct_methods (tree);
 static void maybe_warn_about_overly_private_class (tree);
-static int field_decl_cmp (const void *, const void *);
-static int resort_field_decl_cmp (const void *, const void *);
 static int method_name_cmp (const void *, const void *);
 static int resort_method_name_cmp (const void *, const void *);
 static void add_implicitly_declared_members (tree, int, int, int);
@@ -136,7 +134,7 @@ static tree build_vtable_entry_ref (tree, tree, tree);
 static tree build_vtbl_ref_1 (tree, tree);
 static tree build_vtbl_initializer (tree, tree, tree, tree, int *);
 static int count_fields (tree);
-static int add_fields_to_vec (tree, tree, int);
+static int add_fields_to_record_type (tree, struct sorted_fields_type*, int);
 static void check_bitfield_decl (tree);
 static void check_field_decl (tree, tree, int *, int *, int *, int *);
 static void check_field_decls (tree, tree *, int *, int *, int *);
@@ -1711,72 +1709,11 @@ maybe_warn_about_overly_private_class (tree t)
     }
 }
 
-/* Function to help qsort sort FIELD_DECLs by name order.  */
-
-static int
-field_decl_cmp (const void* x_p, const void* y_p)
-{
-  const tree *const x = x_p;
-  const tree *const y = y_p;
-  if (DECL_NAME (*x) == DECL_NAME (*y))
-    /* A nontype is "greater" than a type.  */
-    return DECL_DECLARES_TYPE_P (*y) - DECL_DECLARES_TYPE_P (*x);
-  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;
-}
-
 static struct {
   gt_pointer_operator new_value;
   void *cookie;
 } resort_data;
 
-/* This routine compares two fields like field_decl_cmp but using the
-   pointer operator in resort_data.  */
-
-static int
-resort_field_decl_cmp (const void* x_p, const void* y_p)
-{
-  const tree *const x = x_p;
-  const tree *const y = y_p;
-
-  if (DECL_NAME (*x) == DECL_NAME (*y))
-    /* A nontype is "greater" than a type.  */
-    return DECL_DECLARES_TYPE_P (*y) - DECL_DECLARES_TYPE_P (*x);
-  if (DECL_NAME (*x) == NULL_TREE)
-    return -1;
-  if (DECL_NAME (*y) == NULL_TREE)
-    return 1;
-  {
-    tree d1 = DECL_NAME (*x);
-    tree d2 = DECL_NAME (*y);
-    resort_data.new_value (&d1, resort_data.cookie);
-    resort_data.new_value (&d2, resort_data.cookie);
-    if (d1 < d2)
-      return -1;
-  }
-  return 1;
-}
-
-/* Resort DECL_SORTED_FIELDS because pointers have been reordered.  */
-
-void 
-resort_sorted_fields (void* obj, 
-                      void* orig_obj ATTRIBUTE_UNUSED , 
-                      gt_pointer_operator new_value, 
-                      void* cookie)
-{
-  tree sf = obj;
-  resort_data.new_value = new_value;
-  resort_data.cookie = cookie;
-  qsort (&TREE_VEC_ELT (sf, 0), TREE_VEC_LENGTH (sf), sizeof (tree),
-	 resort_field_decl_cmp);
-}
-
 /* Comparison function to compare two TYPE_METHOD_VEC entries by name.  */
 
 static int
@@ -2786,18 +2723,18 @@ count_fields (tree 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.  */
+   TREE_LIST FIELDS to the SORTED_FIELDS_TYPE elts, starting at offset IDX.  */
 
 static int
-add_fields_to_vec (tree fields, tree field_vec, int idx)
+add_fields_to_record_type (tree fields, struct sorted_fields_type *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);
+	idx = add_fields_to_record_type (TYPE_FIELDS (TREE_TYPE (x)), field_vec, idx);
       else
-	TREE_VEC_ELT (field_vec, idx++) = x;
+	field_vec->elts[idx++] = x;
     }
   return idx;
 }
@@ -5160,9 +5097,11 @@ finish_struct_1 (tree t)
   n_fields = count_fields (TYPE_FIELDS (t));
   if (n_fields > 7)
     {
-      tree field_vec = make_tree_vec (n_fields);
-      add_fields_to_vec (TYPE_FIELDS (t), field_vec, 0);
-      qsort (&TREE_VEC_ELT (field_vec, 0), n_fields, sizeof (tree),
+      struct sorted_fields_type *field_vec = ggc_alloc (sizeof (struct sorted_fields_type) 
+	+ n_fields * sizeof (tree));
+      field_vec->len = n_fields;
+      add_fields_to_record_type (TYPE_FIELDS (t), field_vec, 0);
+      qsort (field_vec->elts, n_fields, sizeof (tree),
 	     field_decl_cmp);
       if (! DECL_LANG_SPECIFIC (TYPE_MAIN_DECL (t)))
 	retrofit_lang_decl (TYPE_MAIN_DECL (t));
diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index 8272adc..40f3784f 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -1727,7 +1727,7 @@ struct lang_decl GTY(())
 	
 	union lang_decl_u3
 	{
-	  tree GTY ((tag ("0"), reorder ("resort_sorted_fields"))) 
+	  struct sorted_fields_type * GTY ((tag ("0"), reorder ("resort_sorted_fields"))) 
 	       sorted_fields;
  	  struct cp_token_cache * GTY ((tag ("2"))) pending_inline_info;
 	  struct language_function * GTY ((tag ("1"))) 
@@ -3553,8 +3553,6 @@ extern tree convert_to_base                     (tree, tree, bool);
 extern tree build_vtbl_ref			(tree, tree);
 extern tree build_vfn_ref			(tree, tree);
 extern tree get_vtable_decl                     (tree, int);
-extern void resort_sorted_fields 
-  (void *, void *, gt_pointer_operator, void *);
 extern void resort_type_method_vec
   (void *, void *, gt_pointer_operator, void *);
 extern void add_method				(tree, tree, int);
diff --git a/gcc/cp/search.c b/gcc/cp/search.c
index 1161084..10b5216 100644
--- a/gcc/cp/search.c
+++ b/gcc/cp/search.c
@@ -432,8 +432,8 @@ lookup_field_1 (tree type, tree name, bool want_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)));
+      tree *fields = &DECL_SORTED_FIELDS (TYPE_NAME (type))->elts[0];
+      int lo = 0, hi = DECL_SORTED_FIELDS (TYPE_NAME (type))->len;
       int i;
 
       while (lo < hi)