2017-09-01 Nathan Sidwell <nathan@acm.org>
Revert 2017-08-28 Nathan Sidwell <nathan@acm.org>
Restore sorted_fields vector.
* cp-tree.h (lang_type): Restore sorted_fields vector.
(CLASSTYPE_SORTED_FIELDS): Restore.
(CLASSTYPE_BINDINGS): Delete.
* name-lookup.c (lookup_field_1): Restore binary search.
(sorted_fields_type_new, count_fields,
add_fields_to_record_type, add_enum_fields_to_record_type): Restore
(set_class_bindings): Revert.
(insert_late_enum_def_binding): Restore field_vec insertion.
===================================================================
@@ -2007,10 +2007,10 @@ struct GTY(()) lang_type {
as a list of adopted protocols or a pointer to a corresponding
@interface. See objc/objc-act.h for details. */
tree objc_info;
-
- /* Map from IDENTIFIER nodes to DECLS. */
- hash_map<lang_identifier *, tree> *bindings;
-
+ /* sorted_fields is sorted based on a pointer, so we need to be able
+ to resort it if pointers get rearranged. */
+ struct sorted_fields_type * GTY ((reorder ("resort_sorted_fields")))
+ sorted_fields;
/* FIXME reuse another field? */
tree lambda_expr;
};
@@ -3236,9 +3236,10 @@ extern void decl_shadowed_for_var_insert
&& TREE_CODE (TYPE_NAME (NODE)) == TYPE_DECL \
&& TYPE_DECL_ALIAS_P (TYPE_NAME (NODE)))
-/* The binding map for a class (not always present). */
-#define CLASSTYPE_BINDINGS(NODE) \
- (LANG_TYPE_CLASS_CHECK (NODE)->bindings)
+/* For a class type: if this structure has many fields, we'll sort them
+ and put them into a TREE_VEC. */
+#define CLASSTYPE_SORTED_FIELDS(NODE) \
+ (LANG_TYPE_CLASS_CHECK (NODE)->sorted_fields)
/* If non-NULL for a VAR_DECL, FUNCTION_DECL, TYPE_DECL or
TEMPLATE_DECL, the entity is either a template specialization (if
===================================================================
@@ -1183,33 +1183,58 @@ lookup_fnfields_slot_nolazy (tree type,
tree
lookup_field_1 (tree type, tree name, bool want_type)
{
- tree field = NULL_TREE;
+ tree field;
gcc_assert (identifier_p (name) && RECORD_OR_UNION_TYPE_P (type));
- if (CLASSTYPE_BINDINGS (type))
+ if (CLASSTYPE_SORTED_FIELDS (type))
{
- tree *slot = CLASSTYPE_BINDINGS (type)->get (name);
-
- if (slot)
- {
- field = *slot;
-
- if (STAT_HACK_P (field))
+ tree *fields = &CLASSTYPE_SORTED_FIELDS (type)->elts[0];
+ int lo = 0, hi = CLASSTYPE_SORTED_FIELDS (type)->len;
+ int i;
+
+ while (lo < hi)
+ {
+ i = (lo + hi) / 2;
+
+ if (DECL_NAME (fields[i]) > name)
+ hi = i;
+ else if (DECL_NAME (fields[i]) < name)
+ lo = i + 1;
+ else
{
+ field = NULL_TREE;
+
+ /* We might have a nested class and a field with the
+ same name; we sorted them appropriately via
+ field_decl_cmp, so just look for the first or last
+ field with this name. */
if (want_type)
- field = STAT_TYPE (field);
+ {
+ do
+ field = fields[i--];
+ while (i >= lo && DECL_NAME (fields[i]) == name);
+ if (!DECL_DECLARES_TYPE_P (field))
+ field = NULL_TREE;
+ }
else
- field = STAT_DECL (field);
- }
+ {
+ do
+ field = fields[i++];
+ while (i < hi && DECL_NAME (fields[i]) == name);
+ }
+
+ if (field)
+ {
+ field = strip_using_decl (field);
+ if (is_overloaded_fn (field))
+ field = NULL_TREE;
+ }
- field = strip_using_decl (field);
- if (OVL_P (field))
- field = NULL_TREE;
- else if (want_type && !DECL_DECLARES_TYPE_P (field))
- field = NULL_TREE;
+ return field;
+ }
}
- return field;
+ return NULL_TREE;
}
field = TYPE_FIELDS (type);
@@ -1287,62 +1312,113 @@ lookup_fnfields_slot (tree type, tree na
return lookup_fnfields_slot_nolazy (type, name);
}
-/* Add DECL into MAP under NAME. Collisions fail silently. Doesn't
- do sophisticated collision checking. Deals with STAT_HACK. */
+/* Allocate and return an instance of struct sorted_fields_type with
+ N fields. */
-static void
-add_class_member (hash_map<lang_identifier *, tree> *map, tree name, tree decl)
+static struct sorted_fields_type *
+sorted_fields_type_new (int n)
{
- bool existed;
- tree *slot = &map->get_or_insert (name, &existed);
- if (!existed)
- *slot = decl;
- else if (TREE_CODE (*slot) == TYPE_DECL && DECL_ARTIFICIAL (*slot))
- *slot = stat_hack (decl, *slot);
- else if (TREE_CODE (decl) == TYPE_DECL && DECL_ARTIFICIAL (decl))
- *slot = stat_hack (*slot, decl);
+ struct sorted_fields_type *sft;
+ sft = (sorted_fields_type *) ggc_internal_alloc (sizeof (sorted_fields_type)
+ + n * sizeof (tree));
+ sft->len = n;
- /* Else ignore collision. */
+ return sft;
}
-/* Insert the chain FIELDS into MAP. */
+/* Subroutine of insert_into_classtype_sorted_fields. Recursively
+ count the number of fields in TYPE, including anonymous union
+ members. */
-static void
-add_class_members (hash_map<lang_identifier *, tree> *map, tree fields)
+static int
+count_fields (tree fields)
{
- for (tree field = fields; field; field = DECL_CHAIN (field))
+ tree x;
+ int n_fields = 0;
+ for (x = fields; x; x = DECL_CHAIN (x))
{
- if (TREE_CODE (field) == FIELD_DECL
- && ANON_AGGR_TYPE_P (TREE_TYPE (field)))
- add_class_members (map, TYPE_FIELDS (TREE_TYPE (field)));
- else if (DECL_NAME (field))
- add_class_member (map, DECL_NAME (field), field);
+ if (DECL_DECLARES_FUNCTION_P (x))
+ /* Functions are dealt with separately. */;
+ else 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;
}
-/* Create the binding map of KLASS and insert FIELDS. */
+/* Subroutine of insert_into_classtype_sorted_fields. Recursively add
+ all the fields in the TREE_LIST FIELDS to the SORTED_FIELDS_TYPE
+ elts, starting at offset IDX. */
+
+static int
+add_fields_to_record_type (tree fields, struct sorted_fields_type *field_vec,
+ int idx)
+{
+ tree x;
+ for (x = fields; x; x = DECL_CHAIN (x))
+ {
+ if (DECL_DECLARES_FUNCTION_P (x))
+ /* Functions are handled separately. */;
+ else if (TREE_CODE (x) == FIELD_DECL && ANON_AGGR_TYPE_P (TREE_TYPE (x)))
+ idx = add_fields_to_record_type (TYPE_FIELDS (TREE_TYPE (x)), field_vec, idx);
+ else
+ field_vec->elts[idx++] = x;
+ }
+ return idx;
+}
+
+/* Add all of the enum values of ENUMTYPE, to the FIELD_VEC elts,
+ starting at offset IDX. */
+
+static int
+add_enum_fields_to_record_type (tree enumtype,
+ struct sorted_fields_type *field_vec,
+ int idx)
+{
+ tree values;
+ for (values = TYPE_VALUES (enumtype); values; values = TREE_CHAIN (values))
+ field_vec->elts[idx++] = TREE_VALUE (values);
+ return idx;
+}
+
+/* Insert FIELDS into KLASS for the sorted case if the FIELDS count is
+ big enough. */
void
set_class_bindings (tree klass, tree fields)
{
- gcc_assert (!CLASSTYPE_BINDINGS (klass));
-
- CLASSTYPE_BINDINGS (klass)
- = hash_map<lang_identifier *, tree>::create_ggc (8);
- add_class_members (CLASSTYPE_BINDINGS (klass), fields);
+ int n_fields = count_fields (fields);
+ if (n_fields >= 8)
+ {
+ struct sorted_fields_type *field_vec = sorted_fields_type_new (n_fields);
+ add_fields_to_record_type (fields, field_vec, 0);
+ qsort (field_vec->elts, n_fields, sizeof (tree), field_decl_cmp);
+ CLASSTYPE_SORTED_FIELDS (klass) = field_vec;
+ }
}
-/* Insert lately defined enum ENUMTYPE into T for the sorted case. */
+/* Insert lately defined enum ENUMTYPE into KLASS for the sorted case. */
void
insert_late_enum_def_bindings (tree klass, tree enumtype)
{
- hash_map<lang_identifier *, tree> *map = CLASSTYPE_BINDINGS (klass);
-
- for (tree values = TYPE_VALUES (enumtype);
- values; values = TREE_CHAIN (values))
- add_class_member (map, DECL_NAME (TREE_VALUE (values)),
- TREE_VALUE (values));
+ struct sorted_fields_type *sorted_fields = CLASSTYPE_SORTED_FIELDS (klass);
+ if (sorted_fields)
+ {
+ int i;
+ int n_fields
+ = list_length (TYPE_VALUES (enumtype)) + sorted_fields->len;
+ struct sorted_fields_type *field_vec = sorted_fields_type_new (n_fields);
+
+ for (i = 0; i < sorted_fields->len; ++i)
+ field_vec->elts[i] = sorted_fields->elts[i];
+
+ add_enum_fields_to_record_type (enumtype, field_vec,
+ sorted_fields->len);
+ qsort (field_vec->elts, n_fields, sizeof (tree), field_decl_cmp);
+ CLASSTYPE_SORTED_FIELDS (klass) = field_vec;
+ }
}
/* Compute the chain index of a binding_entry given the HASH value of its