This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
(C++) use binary search in lookups
- To: egcs-patches at egcs dot cygnus dot com
- Subject: (C++) use binary search in lookups
- From: Jason Merrill <jason at cygnus dot com>
- Date: Fri, 9 Jul 1999 16:14:00 -0700
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.
Index: class.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/cp/class.c,v
retrieving revision 1.164
diff -c -p -r1.164 class.c
*** class.c 1999/07/09 12:44:29 1.164
--- class.c 1999/07/09 22:58:11
*************** static void modify_all_indirect_vtables
*** 130,135 ****
--- 130,137 ----
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));
*************** maybe_warn_about_overly_private_class (t
*** 2004,2010 ****
--- 2006,2045 ----
}
}
+ /* 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.
*************** maybe_warn_about_overly_private_class (t
*** 2019,2029 ****
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. */
static void
finish_struct_methods (t)
--- 2054,2065 ----
If there are any constructors/destructors, they are moved to the
front of the list. This makes pushclass more efficient.
+
+ @@ 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)
*************** finish_struct_methods (t)
*** 2032,2037 ****
--- 2068,2074 ----
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). */
*************** finish_struct_methods (t)
*** 2089,2095 ****
/* 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);
}
/* Emit error when a duplicate definition of a type is seen. Patch up. */
--- 2126,2153 ----
/* 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);
!
! 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. */
*************** finish_struct_anon (t)
*** 2950,2955 ****
--- 3008,3014 ----
tree t;
{
tree field;
+
for (field = TYPE_FIELDS (t); field; field = TREE_CHAIN (field))
{
if (TREE_STATIC (field))
*************** finish_struct_anon (t)
*** 2960,2991 ****
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))
{
! if (DECL_ARTIFICIAL (*uelt))
continue;
! if (DECL_NAME (*uelt) == constructor_name (t))
cp_pedwarn_at ("ANSI C++ forbids member `%D' with same name as enclosing class",
! *uelt);
! if (TREE_CODE (*uelt) != FIELD_DECL)
{
cp_pedwarn_at ("`%#D' invalid; an anonymous union can only have non-static data members",
! *uelt);
continue;
}
! if (TREE_PRIVATE (*uelt))
cp_pedwarn_at ("private member `%#D' in anonymous union",
! *uelt);
! else if (TREE_PROTECTED (*uelt))
cp_pedwarn_at ("protected member `%#D' in anonymous union",
! *uelt);
! TREE_PRIVATE (*uelt) = TREE_PRIVATE (field);
! TREE_PROTECTED (*uelt) = TREE_PROTECTED (field);
}
}
}
--- 3019,3050 ----
if (DECL_NAME (field) == NULL_TREE
&& ANON_AGGR_TYPE_P (TREE_TYPE (field)))
{
! tree elt = TYPE_FIELDS (TREE_TYPE (field));
! for (; elt; elt = TREE_CHAIN (elt))
{
! if (DECL_ARTIFICIAL (elt))
continue;
! if (DECL_NAME (elt) == constructor_name (t))
cp_pedwarn_at ("ANSI C++ forbids member `%D' with same name as enclosing class",
! elt);
! if (TREE_CODE (elt) != FIELD_DECL)
{
cp_pedwarn_at ("`%#D' invalid; an anonymous union can only have non-static data members",
! elt);
continue;
}
! if (TREE_PRIVATE (elt))
cp_pedwarn_at ("private member `%#D' in anonymous union",
! elt);
! else if (TREE_PROTECTED (elt))
cp_pedwarn_at ("protected member `%#D' in anonymous union",
! elt);
! TREE_PRIVATE (elt) = TREE_PRIVATE (field);
! TREE_PROTECTED (elt) = TREE_PROTECTED (field);
}
}
}
*************** add_implicitly_declared_members (t, cant
*** 3077,3082 ****
--- 3136,3179 ----
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).
*************** finish_struct_1 (t, warn_anon)
*** 3125,3130 ****
--- 3222,3228 ----
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. */
*************** finish_struct_1 (t, warn_anon)
*** 4006,4011 ****
--- 4104,4131 ----
DECL_MODE (x) = TYPE_MODE (t);
make_decl_rtl (x, NULL, 0);
}
+ }
+
+ /* 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))
Index: cp-tree.h
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/cp/cp-tree.h,v
retrieving revision 1.241
diff -c -p -r1.241 cp-tree.h
*** cp-tree.h 1999/07/09 12:44:31 1.241
--- cp-tree.h 1999/07/09 22:58:11
*************** struct lang_decl
*** 1194,1200 ****
tree main_decl_variant;
tree befriending_classes;
! struct pending_inline *pending_inline_info;
};
/* Non-zero if NODE is a _DECL with TREE_READONLY set. */
--- 1194,1204 ----
tree main_decl_variant;
tree befriending_classes;
! union
! {
! tree sorted_fields;
! struct pending_inline *pending_inline_info;
! } u;
};
/* Non-zero if NODE is a _DECL with TREE_READONLY set. */
*************** struct lang_decl
*** 1379,1385 ****
/* 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)
/* True if on the saved_inlines (see decl2.c) list. */
#define DECL_SAVED_INLINE(DECL) \
--- 1383,1393 ----
/* 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)->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) \
Index: ptree.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/cp/ptree.c,v
retrieving revision 1.18
diff -c -p -r1.18 ptree.c
*** ptree.c 1999/07/09 11:05:15 1.18
--- ptree.c 1999/07/09 22:58:11
*************** print_lang_decl (file, node, indent)
*** 48,57 ****
fprintf (file, " decl-main-variant ");
fprintf (file, HOST_PTR_PRINTF, DECL_MAIN_VARIANT (node));
}
! if (DECL_PENDING_INLINE_INFO (node))
{
fprintf (file, " pending-inline-info ");
fprintf (file, HOST_PTR_PRINTF, DECL_PENDING_INLINE_INFO (node));
}
if (DECL_TEMPLATE_INFO (node))
{
--- 48,64 ----
fprintf (file, " decl-main-variant ");
fprintf (file, HOST_PTR_PRINTF, DECL_MAIN_VARIANT (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))
{
Index: search.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/cp/search.c,v
retrieving revision 1.108
diff -c -p -r1.108 search.c
*** search.c 1999/07/09 11:05:18 1.108
--- search.c 1999/07/09 22:58:12
*************** lookup_field_1 (type, name)
*** 522,527 ****
--- 522,553 ----
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
*************** int
*** 1502,1562 ****
lookup_fnfields_1 (type, name)
tree type, name;
{
! register tree method_vec
= CLASS_TYPE_P (type) ? CLASSTYPE_METHOD_VEC (type) : NULL_TREE;
if (method_vec != 0)
{
register tree *methods = &TREE_VEC_ELT (method_vec, 0);
! register tree *end = TREE_VEC_END (method_vec);
#ifdef GATHER_STATISTICS
n_calls_lookup_fnfields_1++;
#endif /* GATHER_STATISTICS */
/* Constructors are first... */
! if (*methods && name == ctor_identifier)
! return 0;
/* and destructors are second. */
! if (*++methods && name == dtor_identifier)
! return 1;
! while (++methods != end && *methods)
{
#ifdef GATHER_STATISTICS
n_outer_fields_searched++;
#endif /* GATHER_STATISTICS */
! if (DECL_NAME (OVL_CURRENT (*methods)) == name)
! 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))
{
! methods = &TREE_VEC_ELT (method_vec, 0) + 1;
!
! while (++methods != end && *methods)
{
! tree method_name = DECL_NAME (OVL_CURRENT (*methods));
!
! if (!IDENTIFIER_TYPENAME_P (method_name))
{
/* 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;
}
}
-
- if (methods != end && *methods)
- return methods - &TREE_VEC_ELT (method_vec, 0);
}
return -1;
--- 1528,1611 ----
lookup_fnfields_1 (type, name)
tree type, name;
{
! 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);
! int len = TREE_VEC_LENGTH (method_vec);
! tree tmp;
#ifdef GATHER_STATISTICS
n_calls_lookup_fnfields_1++;
#endif /* GATHER_STATISTICS */
/* Constructors are first... */
! if (name == ctor_identifier)
! return methods[0] ? 0 : -1;
/* and destructors are second. */
! if (name == dtor_identifier)
! return methods[1] ? 1 : -1;
! for (i = 2; i < len && methods[i]; ++i)
{
#ifdef GATHER_STATISTICS
n_outer_fields_searched++;
#endif /* GATHER_STATISTICS */
!
! 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 (IDENTIFIER_TYPENAME_P (name))
{
! for (i = 2; i < len && methods[i]; ++i)
{
! tmp = OVL_CURRENT (methods[i]);
! if (! DECL_CONV_FN_P (tmp))
{
/* Since all conversion operators come first, we know
there is no such operator. */
break;
}
! else if (TREE_CODE (tmp) == TEMPLATE_DECL)
! return i;
}
}
}
return -1;