hashtable.h (struct ht_identifier): Add data member "hash_value".

	* hashtable.h (struct ht_identifier): Add data member "hash_value".
	* hashtable.c (ht_lookup): Use it when searching, remember.
	(ht_expand): Do not recompute.
	* tree.h (IDENTIFIER_HASH_VALUE): New macro.

cp/
	* cp-tree.h (struct lang_type_class): Replace data member tags
	with hash-table nested_udts.
	(CLASSTYPE_NESTED_UTDS): Rename from CLASSTYPE_TAGS.
	* class.c (unreverse_member_declarations): Don't touch
	CLASSTYPE_TAGS.
	(pushclass): Use cxx_remember_type_decls.
	* decl.c (struct cp_binding_level): Replace data member tags with
	hash-table type_decls.
	(pop_binding_level): Handle level->type_decls.
	(kept_level_p): Adjust.
	(poplevel): Remove unused local variable.
	(bt_print_entry): New function.
	(print_binding_level): Use it.
	(push_namespace): Build current_binding_level->type_decls.
	(maybe_process_template_type_declaration): Adjust.
	(pushtag): Likewise.
	(clear_anon_tags): Use binding_table_remove_anonymous_types.
	(gettags): Remove.
	(cxx_remember_type_decls):  Rename from storetags.  Adjust.
	(lookup_tag): Use binding_table_find_anon_type.  Tidy.
	(lookup_tag_reverse): Use binding_table_reverse_maybe_remap.
	(cxx_init_decl_processing): Build global_binding_level->type_decls.
	(store_parm_decls): Remove pointless code.
	* name-lookup.c (free_binding_entry): New variable.
	(ENTRY_INDEX): New macro.
	(struct binding_table_s): New datatype.
	(binding_entry_make): New function.
	(binding_entry_free): Likewise.
	(binding_table_construct): Likewise.
	(binding_table_free): Likewise.
	(binding_table_new): Likewise.
	(binding_table_expand): Likewise.
	(binding_table_insert): Likewise.
	(binding_table_find): Likewise.
	(binding_table_find_anon_type): Likewise.
	(binding_table_reverse_maybe_remap): Likewise.
	(binding_table_remove_anonymous_types): Likewise.
	(binding_table_foreach): Likewise.
	* name-lookup.h (binding_table): New type.
	(binding_entry): Likewise.
	(bt_foreach_proc): Likewise.
	(struct binding_entry_s): New datatype.
	(SCOPE_DEFAULT_HT_SIZE): New macro.
	(CLASS_SCOPE_HT_SIZE): Likewise.
	(NAMESPACE_ORDINARY_HT_SIZE): Likewise.
	(NAMESPACE_STD_HT_SIZE): Likewise.
	(GLOBAL_SCOPE_HT_SIZE): Likewise.
	(binding_table_new): Declare.
	(binding_table_free): Likewise.
	(binding_table_insert): Likewise.
	(binding_table_find_anon_type): Likewise.
	(binding_table_reverse_maybe_remap): Likewise.
	(binding_table_remove_anonymous_types): Likewise.
	(binding_table_foreach): Likewise.
	(binding_table_find): Likewise.
	(cxx_remember_type_decls): Likewise.
	* pt.c (bt_instantiate_type_proc): New function.
	(do_type_instantiation): Use it.
	* search.c (lookup_field_r): Use binding_table_find.

From-SVN: r66930

8 files changed, 460 insertions, 124 deletions

diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog
index bf1c262..5226756 100644
--- a/gcc/cp/ChangeLog
+++ b/gcc/cp/ChangeLog
@@ -1,3 +1,65 @@
+2003-05-18  Gabriel Dos Reis  <gdr@integrable-solutions.net>
+
+	* cp-tree.h (struct lang_type_class): Replace data member tags
+	with hash-table nested_udts.
+	(CLASSTYPE_NESTED_UTDS): Rename from CLASSTYPE_TAGS.
+	* class.c (unreverse_member_declarations): Don't touch
+	CLASSTYPE_TAGS. 
+	(pushclass): Use cxx_remember_type_decls.
+	* decl.c (struct cp_binding_level): Replace data member tags with
+	hash-table type_decls.
+	(pop_binding_level): Handle level->type_decls.
+	(kept_level_p): Adjust.
+	(poplevel): Remove unused local variable.
+	(bt_print_entry): New function.
+	(print_binding_level): Use it.
+	(push_namespace): Build current_binding_level->type_decls.
+	(maybe_process_template_type_declaration): Adjust.
+	(pushtag): Likewise.
+	(clear_anon_tags): Use binding_table_remove_anonymous_types.
+	(gettags): Remove.
+	(cxx_remember_type_decls):  Rename from storetags.  Adjust.
+	(lookup_tag): Use binding_table_find_anon_type.  Tidy.
+	(lookup_tag_reverse): Use binding_table_reverse_maybe_remap.
+	(cxx_init_decl_processing): Build global_binding_level->type_decls.
+	(store_parm_decls): Remove pointless code.
+	* name-lookup.c (free_binding_entry): New variable.
+	(ENTRY_INDEX): New macro.
+	(struct binding_table_s): New datatype.
+	(binding_entry_make): New function.
+	(binding_entry_free): Likewise.
+	(binding_table_construct): Likewise.
+	(binding_table_free): Likewise.
+	(binding_table_new): Likewise.
+	(binding_table_expand): Likewise.
+	(binding_table_insert): Likewise.
+	(binding_table_find): Likewise.
+	(binding_table_find_anon_type): Likewise.
+	(binding_table_reverse_maybe_remap): Likewise.
+	(binding_table_remove_anonymous_types): Likewise.
+	(binding_table_foreach): Likewise.
+	* name-lookup.h (binding_table): New type.
+	(binding_entry): Likewise.
+	(bt_foreach_proc): Likewise.
+	(struct binding_entry_s): New datatype.
+	(SCOPE_DEFAULT_HT_SIZE): New macro.
+	(CLASS_SCOPE_HT_SIZE): Likewise.
+	(NAMESPACE_ORDINARY_HT_SIZE): Likewise.
+	(NAMESPACE_STD_HT_SIZE): Likewise.
+	(GLOBAL_SCOPE_HT_SIZE): Likewise.
+	(binding_table_new): Declare.
+	(binding_table_free): Likewise.
+	(binding_table_insert): Likewise.
+	(binding_table_find_anon_type): Likewise.
+	(binding_table_reverse_maybe_remap): Likewise.
+	(binding_table_remove_anonymous_types): Likewise.
+	(binding_table_foreach): Likewise.
+	(binding_table_find): Likewise.
+	(cxx_remember_type_decls): Likewise.
+	* pt.c (bt_instantiate_type_proc): New function.
+	(do_type_instantiation): Use it.
+	* search.c (lookup_field_r): Use binding_table_find.
+
 2003-05-18  Kriang Lerdsuwanakij  <lerdsuwa@users.sourceforge.net>
 
 	* semantics.c (perform_deferred_access_checks): Don't discard
diff --git a/gcc/cp/class.c b/gcc/cp/class.c
index 773577d..a8a0188 100644
--- a/gcc/cp/class.c
+++ b/gcc/cp/class.c
@@ -5226,7 +5226,6 @@ unreverse_member_declarations (tree t)
   /* The following lists are all in reverse order.  Put them in
      declaration order now.  */
   TYPE_METHODS (t) = nreverse (TYPE_METHODS (t));
-  CLASSTYPE_TAGS (t) = nreverse (CLASSTYPE_TAGS (t));
   CLASSTYPE_DECL_LIST (t) = nreverse (CLASSTYPE_DECL_LIST (t));
 
   /* Actually, for the TYPE_FIELDS, only the non TYPE_DECLs are in
@@ -5561,7 +5560,7 @@ pushclass (tree type, bool modify)
 	  unuse_fields (type);
 	}
 
-      storetags (CLASSTYPE_TAGS (type));
+      cxx_remember_type_decls (CLASSTYPE_NESTED_UTDS (type));
     }
 }
 
diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index 6bb2e0d..0fecbea 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -1098,7 +1098,7 @@ struct lang_type_class GTY(())
   tree vtables;
   tree typeinfo_var;
   tree vbases;
-  tree tags;
+  binding_table nested_udts;
   tree as_base;
   tree pure_virtuals;
   tree friend_classes;
@@ -1310,11 +1310,11 @@ struct lang_type GTY(())
 #define SET_CLASSTYPE_MARKED6(NODE)   SET_CLASSTYPE_MARKED_N (NODE, 5)
 #define CLEAR_CLASSTYPE_MARKED6(NODE) CLEAR_CLASSTYPE_MARKED_N (NODE, 5)
 
-/* A list of the nested tag-types (class, struct, union, or enum)
-   found within this class.  The TREE_PURPOSE of each node is the name
-   of the type; the TREE_VALUE is the type itself.  This list includes
-   nested member class templates.  */
-#define CLASSTYPE_TAGS(NODE)		(LANG_TYPE_CLASS_CHECK (NODE)->tags)
+/* A dictionary of the nested user-defined-types (class-types, or enums)
+   found within this class.  This table includes nested member class
+   templates.  */
+#define CLASSTYPE_NESTED_UTDS(NODE) \
+   (LANG_TYPE_CLASS_CHECK (NODE)->nested_udts)
 
 /* Nonzero if NODE has a primary base class, i.e., a base class with
    which it shares the virtual function table pointer.  */
diff --git a/gcc/cp/decl.c b/gcc/cp/decl.c
index 4bec8a6..48f4a8c 100644
--- a/gcc/cp/decl.c
+++ b/gcc/cp/decl.c
@@ -331,15 +331,8 @@ struct cp_binding_level GTY(())
     /* A chain of VTABLE_DECL nodes.  */
     tree vtables; 
 
-    /* A list of structure, union and enum definitions, for looking up
-       tag names.
-       It is a chain of TREE_LIST nodes, each of whose TREE_PURPOSE is a name,
-       or NULL_TREE; and whose TREE_VALUE is a RECORD_TYPE, UNION_TYPE,
-       or ENUMERAL_TYPE node.
-
-       C++: the TREE_VALUE nodes can be simple types for
-       component_bindings.  */
-    tree tags;
+    /* A dictionary for looking up user-defined-types.  */
+    binding_table type_decls;
 
     /* A list of USING_DECL nodes.  */
     tree usings;
@@ -544,6 +537,10 @@ pop_binding_level (void)
     register struct cp_binding_level *level = current_binding_level;
     current_binding_level = current_binding_level->level_chain;
     level->level_chain = free_binding_level;
+    if (level->parm_flag == 2)
+      level->type_decls = NULL;
+    else
+      binding_table_free (level->type_decls);
 #if 0 /* defined(DEBUG_BINDING_LEVELS) */
     if (level->binding_depth != binding_depth)
       abort ();
@@ -678,7 +675,7 @@ kept_level_p (void)
   return (current_binding_level->blocks != NULL_TREE
 	  || current_binding_level->keep
 	  || current_binding_level->names != NULL_TREE
-	  || (current_binding_level->tags != NULL_TREE
+	  || (current_binding_level->type_decls != NULL
 	      && !current_binding_level->tag_transparent));
 }
 
@@ -1215,7 +1212,6 @@ poplevel (int keep, int reverse, int functionbody)
   tree decls;
   int tmp = functionbody;
   int real_functionbody;
-  tree tags;
   tree subblocks;
   tree block = NULL_TREE;
   tree decl;
@@ -1230,7 +1226,6 @@ poplevel (int keep, int reverse, int functionbody)
 
   real_functionbody = (current_binding_level->keep == 2
 		       ? ((functionbody = 0), tmp) : functionbody);
-  tags = functionbody >= 0 ? current_binding_level->tags : 0;
   subblocks = functionbody >= 0 ? current_binding_level->blocks : 0;
 
   my_friendly_assert (!current_binding_level->class_shadowed,
@@ -1853,6 +1848,45 @@ wrapup_globals_for_namespace (tree namespace, void* data)
 static int no_print_functions = 0;
 static int no_print_builtins = 0;
 
+/* Called from print_binding_level through binding_table_foreach to
+   print the content of binding ENTRY.  DATA is a pointer to line offset
+   marker.  */
+static void
+bt_print_entry (binding_entry entry, void *data)
+{
+  int *p = (int *) data;
+  int len;
+
+  if (entry->name == NULL)
+    len = 3;
+  else if (entry->name == TYPE_IDENTIFIER (entry->type))
+    len = 2;
+  else
+    len = 4;
+    len = 4;
+
+  *p += len;
+
+  if (*p > 5)
+    {
+      fprintf (stderr, "\n\t");
+      *p = len;
+    }
+  if (entry->name == NULL)
+    {
+      print_node_brief (stderr, "<unnamed-typedef", entry->type, 0);
+      fprintf (stderr, ">");
+    }
+  else if (entry->name == TYPE_IDENTIFIER (entry->type))
+    print_node_brief (stderr, "", entry->type, 0);
+  else
+    {
+      print_node_brief (stderr, "<typedef", entry->name, 0);
+      print_node_brief (stderr, "", entry->type, 0);
+      fprintf (stderr, ">");
+    }
+}
+
 void
 print_binding_level (struct cp_binding_level* lvl)
 {
@@ -1898,38 +1932,11 @@ print_binding_level (struct cp_binding_level* lvl)
       if (i)
         fprintf (stderr, "\n");
     }
-  if (lvl->tags)
+  if (lvl->type_decls)
     {
       fprintf (stderr, " tags:\t");
       i = 0;
-      for (t = lvl->tags; t; t = TREE_CHAIN (t))
-	{
-	  if (TREE_PURPOSE (t) == NULL_TREE)
-	    len = 3;
-	  else if (TREE_PURPOSE (t) == TYPE_IDENTIFIER (TREE_VALUE (t)))
-	    len = 2;
-	  else
-	    len = 4;
-	  i += len;
-	  if (i > 5)
-	    {
-	      fprintf (stderr, "\n\t");
-	      i = len;
-	    }
-	  if (TREE_PURPOSE (t) == NULL_TREE)
-	    {
-	      print_node_brief (stderr, "<unnamed-typedef", TREE_VALUE (t), 0);
-	      fprintf (stderr, ">");
-	    }
-	  else if (TREE_PURPOSE (t) == TYPE_IDENTIFIER (TREE_VALUE (t)))
-	    print_node_brief (stderr, "", TREE_VALUE (t), 0);
-	  else
-	    {
-	      print_node_brief (stderr, "<typedef", TREE_PURPOSE (t), 0);
-	      print_node_brief (stderr, "", TREE_VALUE (t), 0);
-	      fprintf (stderr, ">");
-	    }
-	}
+      binding_table_foreach (lvl->type_decls, bt_print_entry, &i);
       if (i)
 	fprintf (stderr, "\n");
     }
@@ -2059,6 +2066,10 @@ push_namespace (tree name)
 	  pushlevel (0);
 	  declare_namespace_level ();
 	  NAMESPACE_LEVEL (d) = current_binding_level;
+          current_binding_level->type_decls =
+            binding_table_new (name == std_identifier
+                               ? NAMESPACE_STD_HT_SIZE
+                               : NAMESPACE_ORDINARY_HT_SIZE);
 	  VARRAY_TREE_INIT (current_binding_level->static_decls,
 			    name != std_identifier ? 10 : 200,
 			    "Static declarations");
@@ -2427,16 +2438,19 @@ maybe_process_template_type_declaration (tree type,
 	      && b->level_chain->parm_flag == 2)
 	    {
 	      finish_member_declaration (CLASSTYPE_TI_TEMPLATE (type));
-	      /* Put this tag on the list of tags for the class, since
+	      /* Put this UDT in the table of UDTs for the class, since
 		 that won't happen below because B is not the class
 		 binding level, but is instead the pseudo-global level.  */
-	      b->level_chain->tags =
-		tree_cons (name, type, b->level_chain->tags);
+              if (b->level_chain->type_decls == NULL)
+                b->level_chain->type_decls =
+                  binding_table_new (SCOPE_DEFAULT_HT_SIZE);
+              binding_table_insert (b->level_chain->type_decls, name, type);
 	      if (!COMPLETE_TYPE_P (current_class_type))
 		{
 		  maybe_add_class_template_decl_list (current_class_type,
 						      type, /*friend_p=*/0);
-		  CLASSTYPE_TAGS (current_class_type) = b->level_chain->tags;
+		  CLASSTYPE_NESTED_UTDS (current_class_type) =
+                    b->level_chain->type_decls;
 		}
 	    }
 	}
@@ -2526,7 +2540,9 @@ pushtag (tree name, tree type, int globalize)
 		 || COMPLETE_TYPE_P (b->this_class))))
     b = b->level_chain;
 
-  b->tags = tree_cons (name, type, b->tags);
+  if (b->type_decls == NULL)
+    b->type_decls = binding_table_new (SCOPE_DEFAULT_HT_SIZE);
+  binding_table_insert (b->type_decls, name, type);
 
   if (name)
     {
@@ -2603,7 +2619,7 @@ pushtag (tree name, tree type, int globalize)
 	    {
 	      maybe_add_class_template_decl_list (current_class_type,
 						  type, /*friend_p=*/0);
-	      CLASSTYPE_TAGS (current_class_type) = b->tags;
+	      CLASSTYPE_NESTED_UTDS (current_class_type) = b->type_decls;
 	    }
 	}
     }
@@ -2643,14 +2659,13 @@ make_anon_name (void)
   return get_identifier (buf);
 }
 
-/* Clear the TREE_PURPOSE slot of tags which have anonymous typenames.
+/* Clear the TREE_PURPOSE slot of UTDs which have anonymous typenames.
    This keeps dbxout from getting confused.  */
 
 void
 clear_anon_tags (void)
 {
   register struct cp_binding_level *b;
-  register tree tags;
   static int last_cnt = 0;
 
   /* Fast out if no new anon names were declared.  */
@@ -2660,17 +2675,8 @@ clear_anon_tags (void)
   b = current_binding_level;
   while (b->tag_transparent)
     b = b->level_chain;
-  tags = b->tags;
-  while (tags)
-    {
-      /* A NULL purpose means we have already processed all tags
-	 from here to the end of the list.  */
-      if (TREE_PURPOSE (tags) == NULL_TREE)
-	break;
-      if (ANON_AGGRNAME_P (TREE_PURPOSE (tags)))
-	TREE_PURPOSE (tags) = NULL_TREE;
-      tags = TREE_CHAIN (tags);
-    }
+  if (b->type_decls != NULL)
+    binding_table_remove_anonymous_types (b->type_decls);
   last_cnt = anon_cnt;
 }
 
@@ -5032,14 +5038,6 @@ getdecls (void)
   return current_binding_level->names;
 }
 
-/* Return the list of type-tags (for structs, etc) of the current level.  */
-
-tree
-gettags (void)
-{
-  return current_binding_level->tags;
-}
-
 /* Store the list of declarations of the current level.
    This is done for the parameter declarations of a function being defined,
    after they are modified in the light of any missing parameters.  */
@@ -5050,12 +5048,13 @@ storedecls (tree decls)
   current_binding_level->names = decls;
 }
 
-/* Similarly, store the list of tags of the current level.  */
-
+/* Set the current binding TABLE for type declarations..  This is a
+   temporary workaround of the fact that the data structure classtypes
+   does not currently carry its allocated cxx_scope structure.  */
 void
-storetags (tree tags)
+cxx_remember_type_decls (binding_table table)
 {
-  current_binding_level->tags = tags;
+  current_binding_level->type_decls = table;
 }
 
 /* Return the type that should be used when TYPE's name is preceded
@@ -5117,19 +5116,20 @@ lookup_tag (enum tree_code form, tree name,
   /* Nonzero if, we should look past a template parameter level, even
      if THISLEVEL_ONLY.  */
   int allow_template_parms_p = 1;
+  bool type_is_anonymous = ANON_AGGRNAME_P (name);
 
   timevar_push (TV_NAME_LOOKUP);
   for (level = binding_level; level; level = level->level_chain)
     {
       register tree tail;
-      if (ANON_AGGRNAME_P (name))
-	for (tail = level->tags; tail; tail = TREE_CHAIN (tail))
-	  {
-	    /* There's no need for error checking here, because
-	       anon names are unique throughout the compilation.  */
-	    if (TYPE_IDENTIFIER (TREE_VALUE (tail)) == name)
-	      POP_TIMEVAR_AND_RETURN (TV_NAME_LOOKUP, TREE_VALUE (tail));
-	  }
+      if (type_is_anonymous && level->type_decls != NULL)
+        {
+          tree type = binding_table_find_anon_type (level->type_decls, name);
+          /* There is no need for error checking here, because
+           anon names are unique throughout the compilation.  */
+          if (type != NULL)
+            POP_TIMEVAR_AND_RETURN (TV_NAME_LOOKUP, type);
+        }
       else if (level->namespace_p)
 	/* Do namespace lookup.  */
 	for (tail = current_namespace; 1; tail = CP_DECL_CONTEXT (tail))
@@ -5171,22 +5171,22 @@ lookup_tag (enum tree_code form, tree name,
 	    if (thislevel_only || tail == global_namespace)
 	      POP_TIMEVAR_AND_RETURN (TV_NAME_LOOKUP, NULL_TREE);
 	  }
-      else
-	for (tail = level->tags; tail; tail = TREE_CHAIN (tail))
-	  {
-	    if (TREE_PURPOSE (tail) == name)
-	      {
-		enum tree_code code = TREE_CODE (TREE_VALUE (tail));
+      else if (level->type_decls != NULL)
+        {
+          binding_entry entry = binding_table_find (level->type_decls, name);
+          if (entry != NULL)
+            {
+              enum tree_code code = TREE_CODE (entry->type);
 		
-		if (code != form
-		    && (form == ENUMERAL_TYPE || code == ENUMERAL_TYPE))
-		  {
-		    /* Definition isn't the kind we were looking for.  */
-		    error ("`%#D' redeclared as %C", TREE_VALUE (tail), form);
-		    POP_TIMEVAR_AND_RETURN (TV_NAME_LOOKUP, NULL_TREE);
-		  }
-		POP_TIMEVAR_AND_RETURN (TV_NAME_LOOKUP, TREE_VALUE (tail));
-	      }
+              if (code != form
+                  && (form == ENUMERAL_TYPE || code == ENUMERAL_TYPE))
+                {
+                  /* Definition isn't the kind we were looking for.  */
+                  error ("`%#D' redeclared as %C", entry->type, form);
+                  POP_TIMEVAR_AND_RETURN (TV_NAME_LOOKUP, NULL_TREE);
+                }
+              POP_TIMEVAR_AND_RETURN (TV_NAME_LOOKUP, entry->type);
+            }
 	  }
       if (thislevel_only && ! level->tag_transparent)
 	{
@@ -5228,16 +5228,11 @@ lookup_tag_reverse (tree type, tree name)
   timevar_push (TV_NAME_LOOKUP);
   for (level = current_binding_level; level; level = level->level_chain)
     {
-      register tree tail;
-      for (tail = level->tags; tail; tail = TREE_CHAIN (tail))
-	{
-	  if (TREE_VALUE (tail) == type)
-	    {
-	      if (name)
-		TREE_PURPOSE (tail) = name;
-	      POP_TIMEVAR_AND_RETURN (TV_NAME_LOOKUP, TREE_PURPOSE (tail));
-	    }
-	}
+      binding_entry entry = level->type_decls == NULL
+        ? NULL
+        : binding_table_reverse_maybe_remap (level->type_decls, type, name);
+      if (entry)
+        POP_TIMEVAR_AND_RETURN (TV_NAME_LOOKUP, entry->name);
     }
   POP_TIMEVAR_AND_RETURN (TV_NAME_LOOKUP, NULL_TREE);
 }
@@ -6193,6 +6188,7 @@ cxx_init_decl_processing (void)
   /* Make the binding_level structure for global names.  */
   pushlevel (0);
   global_binding_level = current_binding_level;
+  global_binding_level->type_decls = binding_table_new (GLOBAL_SCOPE_HT_SIZE);
   /* The global level is the namespace level of ::.  */
   NAMESPACE_LEVEL (global_namespace) = global_binding_level;
   declare_namespace_level ();
@@ -13700,7 +13696,6 @@ store_parm_decls (tree current_function_parms)
 	 function.  This is all and only the PARM_DECLs that were
 	 pushed into scope by the loop above.  */
       DECL_ARGUMENTS (fndecl) = getdecls ();
-      storetags (gettags ());
     }
   else
     DECL_ARGUMENTS (fndecl) = NULL_TREE;
diff --git a/gcc/cp/name-lookup.c b/gcc/cp/name-lookup.c
index 0e39a9a..bead072 100644
--- a/gcc/cp/name-lookup.c
+++ b/gcc/cp/name-lookup.c
@@ -28,6 +28,241 @@ Boston, MA 02111-1307, USA.  */
 #include "name-lookup.h"
 #include "timevar.h"
 
+/* Compute the chain index of a binding_entry given the HASH value of its
+   name and the total COUNT of chains.  COUNT is assumed to be a power
+   of 2.  */
+#define ENTRY_INDEX(HASH, COUNT) (((HASH) >> 3) & ((COUNT) - 1))
+
+/* A free list of "binding_entry"s awaiting for re-use.  */
+static binding_entry GTY((deletable(""))) free_binding_entry;
+
+/* Create a binding_entry object for (NAME, TYPE).  */
+static inline binding_entry
+binding_entry_make (tree name, tree type)
+{
+  binding_entry entry;
+
+  if (free_binding_entry)
+    {
+      entry = free_binding_entry;
+      free_binding_entry = entry->chain;
+    }
+  else
+    entry = ggc_alloc (sizeof (struct binding_entry_s));
+
+  entry->name = name;
+  entry->type = type;
+
+  return entry;
+}
+
+/* Put ENTRY back on the free list.  */
+static inline void
+binding_entry_free (binding_entry entry)
+{
+  entry->chain = free_binding_entry;
+  free_binding_entry = entry;
+}
+
+/* The datatype used to implement the mapping from names to types at
+   a given scope.  */
+struct binding_table_s GTY(())
+{
+  /* Array of chains of "binding_entry"s  */
+  binding_entry * GTY((length ("%h.chain_count"))) chain;
+
+  /* The number of chains in this table.  This is the length of the
+     the member "chaiin" considered as an array.  */
+  size_t chain_count;
+
+  /* Number of "binding_entry"s in this table.  */
+  size_t entry_count;
+};
+
+/* Construct TABLE with an initial CHAIN_COUNT.  */
+static inline void
+binding_table_construct (binding_table table, size_t chain_count)
+{
+  table->chain_count = chain_count;
+  table->entry_count = 0;
+  table->chain = ggc_alloc_cleared
+    (table->chain_count * sizeof (binding_entry));
+}
+
+/* Free TABLE by making its entries ready for reuse. */
+void
+binding_table_free (binding_table table)
+{
+  size_t i;
+  if (table == NULL)
+    return;
+
+  for (i = 0; i < table->chain_count; ++i)
+    {
+      while (table->chain[i] != NULL)
+        {
+          binding_entry entry = table->chain[i];
+          table->chain[i] = entry->chain;
+          binding_entry_free (entry);
+        }
+    }
+  table->entry_count = 0;
+}
+
+/* Allocate a table with CHAIN_COUNT, assumed to be a power of two.  */
+binding_table
+binding_table_new (size_t chain_count)
+{
+  binding_table table = ggc_alloc (sizeof (struct binding_table_s));
+  binding_table_construct (table, chain_count);
+  return table;
+}
+
+/* Expand TABLE to twice its current chain_count.  */
+static void
+binding_table_expand (binding_table table)
+{
+  const size_t old_chain_count = table->chain_count;
+  const size_t old_entry_count = table->entry_count;
+  const size_t new_chain_count = 2 * old_chain_count;
+  binding_entry *old_chains = table->chain;
+  size_t i;
+
+  binding_table_construct (table, new_chain_count);
+  for (i = 0; i < old_chain_count; ++i)
+    {
+      binding_entry entry = old_chains[i];
+      for (; entry != NULL; entry = old_chains[i])
+        {
+          const unsigned int hash = IDENTIFIER_HASH_VALUE (entry->name);
+          const size_t j = ENTRY_INDEX (hash, new_chain_count);
+
+          old_chains[i] = entry->chain;
+          entry->chain = table->chain[j];
+          table->chain[j] = entry;
+        }
+    }
+  table->entry_count = old_entry_count;
+}
+
+/* Insert a binding for NAME to TYPe into TABLE.  */
+void
+binding_table_insert (binding_table table, tree name, tree type)
+{
+  const unsigned int hash = IDENTIFIER_HASH_VALUE (name);
+  const size_t i = ENTRY_INDEX (hash, table->chain_count);
+  binding_entry entry = binding_entry_make (name, type);
+
+  entry->chain = table->chain[i];
+  table->chain[i] = entry;
+  ++table->entry_count;
+
+  if (3 * table->chain_count < 5 * table->entry_count)
+    binding_table_expand (table);
+}
+
+/* Return the binding_entry, if any, that maps NAME.  */
+binding_entry
+binding_table_find (binding_table table, tree name)
+{
+  const unsigned int hash = IDENTIFIER_HASH_VALUE (name);
+  binding_entry entry = table->chain[ENTRY_INDEX (hash, table->chain_count)];
+
+  while (entry != NULL && entry->name != name)
+    entry = entry->chain;
+
+  return entry;
+}
+
+/* Return the binding_entry, if any, that maps name to an anonymous type.  */
+tree
+binding_table_find_anon_type (binding_table table, tree name)
+{
+  const unsigned int hash = IDENTIFIER_HASH_VALUE (name);
+  binding_entry entry = table->chain[ENTRY_INDEX (hash, table->chain_count)];
+
+  while (entry != NULL && TYPE_IDENTIFIER (entry->type) != name)
+    entry = entry->chain;
+
+  return entry ? entry->type : NULL;
+}
+
+/* Return the binding_entry, if any, that has TYPE as target.  If NAME
+   is non-null, then set the domain and rehash that entry.  */
+binding_entry
+binding_table_reverse_maybe_remap (binding_table table, tree type, tree name)
+{
+  const size_t chain_count = table->chain_count;
+  binding_entry entry = NULL;
+  binding_entry *p = NULL;
+  size_t i;
+
+  for (i = 0; i < chain_count && entry == NULL; ++i)
+    {
+      p = &table->chain[i];
+      while (*p != NULL && entry == NULL)
+        if ((*p)->type == type)
+          entry = *p;
+        else
+          p = &(*p)->chain;
+    }
+
+  if (entry != NULL && name != NULL && entry->name != name)
+    {
+      /* Remove the bucket from the previous chain.  */
+      *p = (*p)->chain;
+
+      /* Remap the name type to type.  */
+      i = ENTRY_INDEX (IDENTIFIER_HASH_VALUE (name), chain_count);
+      entry->chain = table->chain[i];
+      entry->name = name;
+      table->chain[i] = entry;
+    }
+
+  return entry;
+}
+
+/* Remove from TABLE all entries that map to anonymous enums or
+   class-types.  */
+void
+binding_table_remove_anonymous_types (binding_table table)
+{
+  const size_t chain_count = table->chain_count;
+  size_t i;
+
+  for (i = 0; i < chain_count; ++i)
+    {
+      binding_entry *p = &table->chain[i];
+
+      while (*p != NULL)
+        if (ANON_AGGRNAME_P ((*p)->name))
+          {
+            binding_entry e = *p;
+            *p = (*p)->chain;
+            --table->entry_count;
+            binding_entry_free (e);
+          }
+        else
+          p = &(*p)->chain;
+    }
+}
+
+/* Apply PROC -- with DATA -- to all entries in TABLE.  */
+void
+binding_table_foreach (binding_table table, bt_foreach_proc proc, void *data)
+{
+  const size_t chain_count = table->chain_count;
+  size_t i;
+
+  for (i = 0; i < chain_count; ++i)
+    {
+      binding_entry entry = table->chain[i];
+      for (; entry != NULL; entry = entry->chain)
+        proc (entry, data);
+    }
+}
+
+
 /* A free list of "cxx_binding"s, connected by their PREVIOUS.  */
 static GTY((deletable (""))) cxx_binding *free_bindings;
 
diff --git a/gcc/cp/name-lookup.h b/gcc/cp/name-lookup.h
index f6a4131..1222f5e 100644
--- a/gcc/cp/name-lookup.h
+++ b/gcc/cp/name-lookup.h
@@ -24,6 +24,39 @@ Boston, MA 02111-1307, USA.  */
 
 #include "c-common.h"
 
+/* The type of dictionary used to map names to types declared at
+   a given scope.  */
+typedef struct binding_table_s *binding_table;
+typedef struct binding_entry_s *binding_entry;
+
+/* The type of a routine repeatedly called by binding_table_foreach.  */
+typedef void (*bt_foreach_proc) (binding_entry, void *);
+
+struct binding_entry_s GTY(())
+{
+  binding_entry chain;
+  tree name;
+  tree type;
+};
+
+/* These macros indicate the initial chains count for binding_table.  */
+#define SCOPE_DEFAULT_HT_SIZE                        (1 << 3)
+#define CLASS_SCOPE_HT_SIZE                          (1 << 3)
+#define NAMESPACE_ORDINARY_HT_SIZE                   (1 << 5)
+#define NAMESPACE_STD_HT_SIZE                        (1 << 8)
+#define GLOBAL_SCOPE_HT_SIZE                         (1 << 8)
+
+extern binding_table binding_table_new (size_t);
+extern void binding_table_free (binding_table);
+extern void binding_table_insert (binding_table, tree, tree);
+extern tree binding_table_find_anon_type (binding_table, tree);
+extern binding_entry binding_table_reverse_maybe_remap (binding_table,
+                                                        tree, tree);
+extern void binding_table_remove_anonymous_types (binding_table);
+extern void binding_table_foreach (binding_table, bt_foreach_proc, void *);
+extern binding_entry binding_table_find (binding_table, tree);
+extern void cxx_remember_type_decls (binding_table);
+
 /* Datatype used to temporarily save C++ bindings (for implicit
    instantiations purposes and like).  Implemented in decl.c.  */
 typedef struct cxx_saved_binding cxx_saved_binding;
diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index efc3774..e7feab6 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -5393,7 +5393,7 @@ instantiate_class_template (type)
 	{
 	  if (TYPE_P (t))
 	    {
-	      /* Build new CLASSTYPE_TAGS.  */
+	      /* Build new CLASSTYPE_NESTED_UTDS.  */
 
 	      tree tag = t;
 	      tree name = TYPE_IDENTIFIER (tag);
@@ -5486,7 +5486,7 @@ instantiate_class_template (type)
 		  /* If it is a TYPE_DECL for a class-scoped ENUMERAL_TYPE,
 		     such a thing will already have been added to the field
 		     list by tsubst_enum in finish_member_declaration in the
-		     CLASSTYPE_TAGS case above.  */
+		     CLASSTYPE_NESTED_UTDS case above.  */
 		  if (!(TREE_CODE (r) == TYPE_DECL
 			&& TREE_CODE (TREE_TYPE (r)) == ENUMERAL_TYPE
 			&& TYPE_CONTEXT (TREE_TYPE (r)) == type))
@@ -10470,6 +10470,18 @@ mark_class_instantiated (t, extern_p)
     }
 }     
 
+/* Called from do_type_instantiation through binding_table_foreach to
+   do recursive instantiation for the type bound in ENTRY.   */
+static void
+bt_instantiate_type_proc (binding_entry entry, void *data)
+{
+  tree storage = *(tree *) data;
+
+  if (IS_AGGR_TYPE (entry->type)
+      && !uses_template_parms (CLASSTYPE_TI_ARGS (entry->type)))
+    do_type_instantiation (TYPE_MAIN_DECL (entry->type), storage, 0);
+}
+
 /* Perform an explicit instantiation of template class T.  STORAGE, if
    non-null, is the RID for extern, inline or static.  COMPLAIN is
    nonzero if this is called from the parser, zero if called recursively,
@@ -10610,10 +10622,9 @@ do_type_instantiation (t, storage, complain)
 	    instantiate_decl (tmp, /*defer_ok=*/1);
 	}
 
-    for (tmp = CLASSTYPE_TAGS (t); tmp; tmp = TREE_CHAIN (tmp))
-      if (IS_AGGR_TYPE (TREE_VALUE (tmp))
-	  && !uses_template_parms (CLASSTYPE_TI_ARGS (TREE_VALUE (tmp))))
-	do_type_instantiation (TYPE_MAIN_DECL (TREE_VALUE (tmp)), storage, 0);
+    if (CLASSTYPE_NESTED_UTDS (t))
+      binding_table_foreach (CLASSTYPE_NESTED_UTDS (t),
+                             bt_instantiate_type_proc, &storage);
   }
 }
 
diff --git a/gcc/cp/search.c b/gcc/cp/search.c
index f9fa166..7bab0b1 100644
--- a/gcc/cp/search.c
+++ b/gcc/cp/search.c
@@ -1117,11 +1117,12 @@ lookup_field_r (tree binfo, void *data)
 	}
       else
 	nval = NULL_TREE;
-      if (!nval)
+      if (!nval && CLASSTYPE_NESTED_UTDS (type) != NULL)
 	{
-	  nval = purpose_member (lfi->name, CLASSTYPE_TAGS (type));
-	  if (nval)
-	    nval = TYPE_MAIN_DECL (TREE_VALUE (nval));
+          binding_entry e = binding_table_find (CLASSTYPE_NESTED_UTDS (type),
+                                                lfi->name);
+	  if (e != NULL)
+	    nval = TYPE_MAIN_DECL (e->type);
 	  else 
 	    return NULL_TREE;
 	}