[C++] use hash-table for namespace contents

2017-10-06  Nathan Sidwell  <nathan@acm.org>

	Use hash_table for namespace bindings
	* cp-tree.h (struct named_decl_hash): New.
	(lang_decl_ns): Change type of bindings field.
	* lex.c (maybe_add_lang_decl_raw): Adjust.
	* name-lookup.c (find_namespace_slot): Adjust.
	(do_pushdecl): Push NULL-named namespace.
	(do_push_nested_namespace): Adjust.
	(push_namespace): Push anonymous namespace as NULL name.

Index: cp-tree.h
===================================================================
--- cp-tree.h	(revision 253485)
+++ cp-tree.h	(working copy)
@@ -828,6 +828,25 @@  class lkp_iterator : public ovl_iterator
   }
 };
 
+/* hash traits for declarations.  Hashes potential overload sets via
+   DECL_NAME.  */
+
+struct named_decl_hash : ggc_remove <tree>
+{
+  typedef tree value_type; /* A DECL or OVERLOAD  */
+  typedef tree compare_type; /* An identifier.  */
+
+  inline static hashval_t hash (const value_type decl);
+  inline static bool equal (const value_type existing, compare_type candidate);
+
+  static inline void mark_empty (value_type &p) {p = NULL_TREE;}
+  static inline bool is_empty (value_type p) {return !p;}
+
+  /* Nothing is deletable.  Everything is insertable.  */
+  static bool is_deleted (value_type) { return false; }
+  static void mark_deleted (value_type) { gcc_unreachable (); }
+};
+
 struct GTY(()) tree_template_decl {
   struct tree_decl_common common;
   tree arguments;
@@ -2548,10 +2567,10 @@  struct GTY(()) lang_decl_ns {
   vec<tree, va_gc> *usings;
   vec<tree, va_gc> *inlinees;
 
-  /* Map from IDENTIFIER nodes to DECLS.  It'd be nice to have this
-     inline, but as the hash_map has a dtor, we can't then put this
-     struct into a union (until moving to c++11).  */
-  hash_map<lang_identifier *, tree> *bindings;
+  /* Hash table of bound decls. It'd be nice to have this inline, but
+     as the hash_map has a dtor, we can't then put this struct into a
+     union (until moving to c++11).  */
+  hash_table<named_decl_hash> *bindings;
 };
 
 /* DECL_LANG_SPECIFIC for parameters.  */
@@ -7370,6 +7389,20 @@  type_unknown_p (const_tree expr)
   return TREE_TYPE (expr) == unknown_type_node;
 }
 
+inline hashval_t
+named_decl_hash::hash (const value_type decl)
+{
+  tree name = OVL_NAME (decl);
+  return name ? IDENTIFIER_HASH_VALUE (name) : 0;
+}
+
+inline bool
+named_decl_hash::equal (const value_type existing, compare_type candidate)
+{
+  tree name = OVL_NAME (existing);
+  return candidate == name;
+}
+
 /* -- end of C++ */
 
 #endif /* ! GCC_CP_TREE_H */
Index: lex.c
===================================================================
--- lex.c	(revision 253485)
+++ lex.c	(working copy)
@@ -651,7 +651,7 @@  maybe_add_lang_decl_raw (tree t, bool de
 
   if (sel == lds_ns)
     /* Who'd create a namespace, only to put nothing in it?  */
-    ld->u.ns.bindings = hash_map<lang_identifier *, tree>::create_ggc (499);
+    ld->u.ns.bindings = hash_table<named_decl_hash>::create_ggc (499);
 
   if (GATHER_STATISTICS)
     {
Index: name-lookup.c
===================================================================
--- name-lookup.c	(revision 253485)
+++ name-lookup.c	(working copy)
@@ -86,17 +86,9 @@  create_local_binding (cp_binding_level *
 static tree *
 find_namespace_slot (tree ns, tree name, bool create_p = false)
 {
-  tree *slot;
-
-  if (create_p)
-    {
-      bool existed;
-      slot = &DECL_NAMESPACE_BINDINGS (ns)->get_or_insert (name, &existed);
-      if (!existed)
-	*slot = NULL_TREE;
-    }
-  else
-    slot = DECL_NAMESPACE_BINDINGS (ns)->get (name);
+  tree *slot = DECL_NAMESPACE_BINDINGS (ns)
+    ->find_slot_with_hash (name, name ? IDENTIFIER_HASH_VALUE (name) : 0,
+			   create_p ? INSERT : NO_INSERT);
   return slot;
 }
 
@@ -2950,7 +2942,10 @@  do_pushdecl (tree decl, bool is_friend)
   while (level->kind == sk_class)
     level = level->level_chain;
 
-  if (tree name = DECL_NAME (decl))
+  /* An anonymous namespace has a NULL DECL_NAME, but we still want to
+     insert it.  Other NULL-named decls, not so much.  */
+  tree name = DECL_NAME (decl);
+  if (name || TREE_CODE (decl) == NAMESPACE_DECL)
     {
       cxx_binding *binding = NULL; /* Local scope binding.  */
       tree ns = NULL_TREE; /* Searched namespace.  */
@@ -6615,9 +6610,7 @@  do_push_nested_namespace (tree ns)
     {
       do_push_nested_namespace (CP_DECL_CONTEXT (ns));
       gcc_checking_assert
-	(find_namespace_value (current_namespace,
-			       DECL_NAME (ns) ? DECL_NAME (ns)
-			       : anon_identifier) == ns);
+	(find_namespace_value (current_namespace, DECL_NAME (ns)) == ns);
       resume_scope (NAMESPACE_LEVEL (ns));
       current_namespace = ns;
     }
@@ -6775,10 +6768,7 @@  push_namespace (tree name, bool make_inl
   /* We should not get here if the global_namespace is not yet constructed
      nor if NAME designates the global namespace:  The global scope is
      constructed elsewhere.  */
-  gcc_assert (global_namespace != NULL && name != global_identifier);
-
-  if (!name)
-    name = anon_identifier;
+  gcc_checking_assert (global_namespace != NULL && name != global_identifier);
 
   tree ns = NULL_TREE;
   {
@@ -6824,11 +6814,9 @@  push_namespace (tree name, bool make_inl
 	ns = NULL_TREE;
       else
 	{
-	  if (name == anon_identifier)
+	  if (!name)
 	    {
-	      /* Clear DECL_NAME for the benefit of debugging back ends.  */
-	      SET_DECL_ASSEMBLER_NAME (ns, name);
-	      DECL_NAME (ns) = NULL_TREE;
+	      SET_DECL_ASSEMBLER_NAME (ns, anon_identifier);
 
 	      if (!make_inline)
 		add_using_namespace (DECL_NAMESPACE_USING (current_namespace),
@@ -6843,7 +6831,7 @@  push_namespace (tree name, bool make_inl
 	      vec_safe_push (DECL_NAMESPACE_INLINEES (current_namespace), ns);
 	    }
 
-	  if (name == anon_identifier || make_inline)
+	  if (!name || make_inline)
 	    emit_debug_info_using_namespace (current_namespace, ns, true);
 	}
     }