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

1 files changed, 67 insertions, 0 deletions

diff --git a/gcc/c-common.c b/gcc/c-common.c
index b122f9b..ba0138d 100644
--- a/gcc/c-common.c
+++ b/gcc/c-common.c
@@ -776,6 +776,7 @@ static void check_function_nonnull (tree, tree);
 static void check_nonnull_arg (void *, tree, unsigned HOST_WIDE_INT);
 static bool nonnull_check_p (tree, unsigned HOST_WIDE_INT);
 static bool get_nonnull_operand (tree, unsigned HOST_WIDE_INT *);
+static int resort_field_decl_cmp (const void *, const void *);
 
 /* Table of machine-independent attributes common to all C-like languages.  */
 const struct attribute_spec c_common_attribute_table[] =
@@ -5882,6 +5883,72 @@ check_function_arguments_recurse (void (*callback)
   (*callback) (ctx, param, param_num);
 }
 
+/* Function to help qsort sort FIELD_DECLs by name order.  */
+
+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 (TREE_CODE (*y) == TYPE_DECL) - (TREE_CODE (*x) == TYPE_DECL);
+  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 (TREE_CODE (*y) == TYPE_DECL) - (TREE_CODE (*x) == TYPE_DECL);
+  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)
+{
+  struct sorted_fields_type *sf = obj;
+  resort_data.new_value = new_value;
+  resort_data.cookie = cookie;
+  qsort (&sf->elts[0], sf->len, sizeof (tree),
+         resort_field_decl_cmp);
+}
+
 /* Used by estimate_num_insns.  Estimate number of instructions seen
    by given statement.  */
 static tree