Fork GCC's hash-table.h for use in GDBusers/cbiesinger/hashtable

And use it at one callsite in dwarf2read.

7 files changed, 1875 insertions, 14 deletions

diff --git a/gdb/Makefile.in b/gdb/Makefile.in
index 877a9ccd6bd..b702166f7b9 100644
--- a/gdb/Makefile.in
+++ b/gdb/Makefile.in
@@ -1037,6 +1037,7 @@ COMMON_SFILES = \
 	go-lang.c \
 	go-typeprint.c \
 	go-valprint.c \
+	hash-table.c \
 	inf-child.c \
 	inf-loop.c \
 	infcall.c \
diff --git a/gdb/dwarf2read.c b/gdb/dwarf2read.c
index 1052501c351..7175c80b359 100644
--- a/gdb/dwarf2read.c
+++ b/gdb/dwarf2read.c
@@ -90,6 +90,7 @@
 #include <forward_list>
 #include "rust-lang.h"
 #include "gdbsupport/pathstuff.h"
+#include "hash-map.h"
 
 /* When == 1, print basic high level tracing messages.
    When > 1, be more verbose.
@@ -5076,12 +5077,8 @@ dw_expand_symtabs_matching_file_matcher
 
   objfile *const objfile = dwarf2_per_objfile->objfile;
 
-  htab_up visited_found (htab_create_alloc (10, htab_hash_pointer,
-					    htab_eq_pointer,
-					    NULL, xcalloc, xfree));
-  htab_up visited_not_found (htab_create_alloc (10, htab_hash_pointer,
-						htab_eq_pointer,
-						NULL, xcalloc, xfree));
+  hash_table<nofree_ptr_hash <quick_file_names>> visited_found (10);
+  hash_table<nofree_ptr_hash <quick_file_names>> visited_not_found (10);
 
   /* The rule is CUs specify all the files, including those used by
      any TU, so there's no need to scan TUs here.  */
@@ -5100,9 +5097,9 @@ dw_expand_symtabs_matching_file_matcher
       if (file_data == NULL)
 	continue;
 
-      if (htab_find (visited_not_found.get (), file_data) != NULL)
+      if (visited_not_found.find_slot (file_data, NO_INSERT) != NULL)
 	continue;
-      else if (htab_find (visited_found.get (), file_data) != NULL)
+      else if (visited_found.find_slot (file_data, NO_INSERT) != NULL)
 	{
 	  per_cu->v.quick->mark = 1;
 	  continue;
@@ -5132,12 +5129,10 @@ dw_expand_symtabs_matching_file_matcher
 	      break;
 	    }
 	}
-
-      void **slot = htab_find_slot (per_cu->v.quick->mark
-				    ? visited_found.get ()
-				    : visited_not_found.get (),
-				    file_data, INSERT);
-      *slot = file_data;
+      if (per_cu->v.quick->mark)
+	*visited_found.find_slot (file_data, INSERT) = file_data;
+      else
+	*visited_not_found.find_slot (file_data, INSERT) = file_data;
     }
 }
 
diff --git a/gdb/hash-map-traits.h b/gdb/hash-map-traits.h
new file mode 100644
index 00000000000..af66018e92c
--- /dev/null
+++ b/gdb/hash-map-traits.h
@@ -0,0 +1,188 @@
+/* A hash map traits.
+   Copyright (C) 2015-2019 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef HASH_MAP_TRAITS_H
+#define HASH_MAP_TRAITS_H
+
+/* Bacause mem-stats.h uses default hashmap traits, we have to
+   put the class to this separate header file.  */
+
+#include "hash-traits.h"
+
+/* Implement hash_map traits for a key with hash traits H.  Empty and
+   deleted map entries are represented as empty and deleted keys.  */
+
+template <typename H, typename Value>
+struct simple_hashmap_traits
+{
+  typedef typename H::value_type key_type;
+  static const bool maybe_mx = true;
+  static inline hashval_t hash (const key_type &);
+  static inline bool equal_keys (const key_type &, const key_type &);
+  template <typename T> static inline void remove (T &);
+  template <typename T> static inline bool is_empty (const T &);
+  template <typename T> static inline bool is_deleted (const T &);
+  template <typename T> static inline void mark_empty (T &);
+  template <typename T> static inline void mark_deleted (T &);
+};
+
+template <typename H, typename Value>
+inline hashval_t
+simple_hashmap_traits <H, Value>::hash (const key_type &h)
+{
+  return H::hash (h);
+}
+
+template <typename H, typename Value>
+inline bool
+simple_hashmap_traits <H, Value>::equal_keys (const key_type &k1,
+					      const key_type &k2)
+{
+  return H::equal (k1, k2);
+}
+
+template <typename H, typename Value>
+template <typename T>
+inline void
+simple_hashmap_traits <H, Value>::remove (T &entry)
+{
+  H::remove (entry.m_key);
+  entry.m_value.~Value ();
+}
+
+template <typename H, typename Value>
+template <typename T>
+inline bool
+simple_hashmap_traits <H, Value>::is_empty (const T &entry)
+{
+  return H::is_empty (entry.m_key);
+}
+
+template <typename H, typename Value>
+template <typename T>
+inline bool
+simple_hashmap_traits <H, Value>::is_deleted (const T &entry)
+{
+  return H::is_deleted (entry.m_key);
+}
+
+template <typename H, typename Value>
+template <typename T>
+inline void
+simple_hashmap_traits <H, Value>::mark_empty (T &entry)
+{
+  H::mark_empty (entry.m_key);
+}
+
+template <typename H, typename Value>
+template <typename T>
+inline void
+simple_hashmap_traits <H, Value>::mark_deleted (T &entry)
+{
+  H::mark_deleted (entry.m_key);
+}
+
+template <typename H, typename Value>
+struct simple_cache_map_traits: public simple_hashmap_traits<H,Value>
+{
+  static const bool maybe_mx = false;
+};
+
+/* Implement traits for a hash_map with values of type Value for cases
+   in which the key cannot represent empty and deleted slots.  Instead
+   record empty and deleted entries in Value.  Derived classes must
+   implement the hash and equal_keys functions.  */
+
+template <typename Value>
+struct unbounded_hashmap_traits
+{
+  template <typename T> static inline void remove (T &);
+  template <typename T> static inline bool is_empty (const T &);
+  template <typename T> static inline bool is_deleted (const T &);
+  template <typename T> static inline void mark_empty (T &);
+  template <typename T> static inline void mark_deleted (T &);
+};
+
+template <typename Value>
+template <typename T>
+inline void
+unbounded_hashmap_traits <Value>::remove (T &entry)
+{
+  default_hash_traits <Value>::remove (entry.m_value);
+}
+
+template <typename Value>
+template <typename T>
+inline bool
+unbounded_hashmap_traits <Value>::is_empty (const T &entry)
+{
+  return default_hash_traits <Value>::is_empty (entry.m_value);
+}
+
+template <typename Value>
+template <typename T>
+inline bool
+unbounded_hashmap_traits <Value>::is_deleted (const T &entry)
+{
+  return default_hash_traits <Value>::is_deleted (entry.m_value);
+}
+
+template <typename Value>
+template <typename T>
+inline void
+unbounded_hashmap_traits <Value>::mark_empty (T &entry)
+{
+  default_hash_traits <Value>::mark_empty (entry.m_value);
+}
+
+template <typename Value>
+template <typename T>
+inline void
+unbounded_hashmap_traits <Value>::mark_deleted (T &entry)
+{
+  default_hash_traits <Value>::mark_deleted (entry.m_value);
+}
+
+/* Implement traits for a hash_map from integer type Key to Value in
+   cases where Key has no spare values for recording empty and deleted
+   slots.  */
+
+template <typename Key, typename Value>
+struct unbounded_int_hashmap_traits : unbounded_hashmap_traits <Value>
+{
+  typedef Key key_type;
+  static inline hashval_t hash (Key);
+  static inline bool equal_keys (Key, Key);
+};
+
+template <typename Key, typename Value>
+inline hashval_t
+unbounded_int_hashmap_traits <Key, Value>::hash (Key k)
+{
+  return k;
+}
+
+template <typename Key, typename Value>
+inline bool
+unbounded_int_hashmap_traits <Key, Value>::equal_keys (Key k1, Key k2)
+{
+  return k1 == k2;
+}
+
+#endif // HASH_MAP_TRAITS_H
diff --git a/gdb/hash-map.h b/gdb/hash-map.h
new file mode 100644
index 00000000000..d479196a4ff
--- /dev/null
+++ b/gdb/hash-map.h
@@ -0,0 +1,220 @@
+/* A type-safe hash map.
+   Copyright (C) 2014-2019 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+
+#ifndef hash_map_h
+#define hash_map_h
+
+#include "hash-table.h"
+
+/* Class hash_map is a hash-value based container mapping objects of
+   KeyId type to those of the Value type.
+   Both KeyId and Value may be non-trivial (non-POD) types provided
+   a suitabe Traits class.  A few default Traits specializations are
+   provided for basic types such as integers, pointers, and std::pair.
+   Inserted elements are value-initialized either to zero for POD types
+   or by invoking their default ctor.  Removed elements are destroyed
+   by invoking their dtor.   On hash_map destruction all elements are
+   removed.  Objects of hash_map type are copy-constructible but not
+   assignable.  */
+
+template<typename KeyId, typename Value,
+	 typename Traits /* = simple_hashmap_traits<default_hash_traits<Key>,
+			                            Value> */>
+class hash_map
+{
+  typedef typename Traits::key_type Key;
+  struct hash_entry
+  {
+    Key m_key;
+    Value m_value;
+
+    typedef hash_entry value_type;
+    typedef Key compare_type;
+
+    static hashval_t hash (const hash_entry &e)
+      {
+       	return Traits::hash (e.m_key);
+      }
+
+    static bool equal (const hash_entry &a, const Key &b)
+       	{
+	  return Traits::equal_keys (a.m_key, b);
+       	}
+
+    static void remove (hash_entry &e) { Traits::remove (e); }
+
+    static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); }
+
+    static bool is_deleted (const hash_entry &e)
+      {
+       	return Traits::is_deleted (e);
+      }
+
+    static void mark_empty (hash_entry &e) { Traits::mark_empty (e); }
+    static bool is_empty (const hash_entry &e) { return Traits::is_empty (e); }
+  };
+
+public:
+  explicit hash_map (size_t n = 13,
+		     bool sanitize_eq_and_hash = true)
+    : m_table (n, sanitize_eq_and_hash)
+  {
+  }
+
+  explicit hash_map (const hash_map &h,
+		     bool sanitize_eq_and_hash = true)
+    : m_table (h.m_table, sanitize_eq_and_hash) {}
+
+  /* If key k isn't already in the map add key k with value v to the map, and
+     return false.  Otherwise set the value of the entry for key k to be v and
+     return true.  */
+
+  bool put (const Key &k, const Value &v)
+    {
+      hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
+						   INSERT);
+      bool ins = hash_entry::is_empty (*e);
+      if (ins)
+	{
+	  e->m_key = k;
+	  new ((void *) &e->m_value) Value (v);
+	}
+      else
+	e->m_value = v;
+
+      return !ins;
+    }
+
+  /* if the passed in key is in the map return its value otherwise NULL.  */
+
+  Value *get (const Key &k)
+    {
+      hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
+      return Traits::is_empty (e) ? NULL : &e.m_value;
+    }
+
+  /* Return a reference to the value for the passed in key, creating the entry
+     if it doesn't already exist.  If existed is not NULL then it is set to
+     false if the key was not previously in the map, and true otherwise.  */
+
+  Value &get_or_insert (const Key &k, bool *existed = NULL)
+    {
+      hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
+						   INSERT);
+      bool ins = Traits::is_empty (*e);
+      if (ins)
+	{
+	  e->m_key = k;
+	  new ((void *)&e->m_value) Value ();
+	}
+
+      if (existed != NULL)
+	*existed = !ins;
+
+      return e->m_value;
+    }
+
+  void remove (const Key &k)
+    {
+      m_table.remove_elt_with_hash (k, Traits::hash (k));
+    }
+
+  /* Call the call back on each pair of key and value with the passed in
+     arg.  */
+
+  template<typename Arg, bool (*f)(const typename Traits::key_type &,
+				   const Value &, Arg)>
+  void traverse (Arg a) const
+    {
+      for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
+	   iter != m_table.end (); ++iter)
+	f ((*iter).m_key, (*iter).m_value, a);
+    }
+
+  template<typename Arg, bool (*f)(const typename Traits::key_type &,
+				   Value *, Arg)>
+  void traverse (Arg a) const
+    {
+      for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
+	   iter != m_table.end (); ++iter)
+	if (!f ((*iter).m_key, &(*iter).m_value, a))
+	  break;
+    }
+
+  size_t elements () const { return m_table.elements (); }
+
+  void empty () { m_table.empty(); }
+
+  /* Return true when there are no elements in this hash map.  */
+  bool is_empty () const { return m_table.is_empty (); }
+
+  class iterator
+  {
+  public:
+    explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
+      m_iter (iter) {}
+
+    iterator &operator++ ()
+    {
+      ++m_iter;
+      return *this;
+    }
+
+    /* Can't use std::pair here, because GCC before 4.3 don't handle
+       std::pair where template parameters are references well.
+       See PR86739.  */
+    class reference_pair {
+    public:
+      const Key &first;
+      Value &second;
+
+      reference_pair (const Key &key, Value &value) : first (key), second (value) {}
+
+      template <typename K, typename V>
+      operator std::pair<K, V> () const { return std::pair<K, V> (first, second); }
+    };
+
+    reference_pair operator* ()
+    {
+      hash_entry &e = *m_iter;
+      return reference_pair (e.m_key, e.m_value);
+    }
+
+    bool
+    operator != (const iterator &other) const
+    {
+      return m_iter != other.m_iter;
+    }
+
+  private:
+    typename hash_table<hash_entry>::iterator m_iter;
+  };
+
+  /* Standard iterator retrieval methods.  */
+
+  iterator  begin () const { return iterator (m_table.begin ()); }
+  iterator end () const { return iterator (m_table.end ()); }
+
+private:
+
+  hash_table<hash_entry> m_table;
+};
+
+#endif
diff --git a/gdb/hash-table.c b/gdb/hash-table.c
new file mode 100644
index 00000000000..56aeb142f43
--- /dev/null
+++ b/gdb/hash-table.c
@@ -0,0 +1,97 @@
+/* A type-safe hash table template.
+   Copyright (C) 2012-2019 Free Software Foundation, Inc.
+   Contributed by Lawrence Crowl <crowl@google.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+
+/* This file implements a typed hash table.
+   The implementation borrows from libiberty's hashtab.  */
+
+#include "defs.h"
+#include "gdbtypes.h"
+#include "hash-table.h"
+
+/* Table of primes and multiplicative inverses.
+
+   Note that these are not minimally reduced inverses.  Unlike when generating
+   code to divide by a constant, we want to be able to use the same algorithm
+   all the time.  All of these inverses (are implied to) have bit 32 set.
+
+   For the record, here's the function that computed the table; it's a 
+   vastly simplified version of the function of the same name from gcc.  */
+
+struct prime_ent const prime_tab[] = {
+  {          7, 0x24924925, 0x9999999b, 2 },
+  {         13, 0x3b13b13c, 0x745d1747, 3 },
+  {         31, 0x08421085, 0x1a7b9612, 4 },
+  {         61, 0x0c9714fc, 0x15b1e5f8, 5 },
+  {        127, 0x02040811, 0x0624dd30, 6 },
+  {        251, 0x05197f7e, 0x073260a5, 7 },
+  {        509, 0x01824366, 0x02864fc8, 8 },
+  {       1021, 0x00c0906d, 0x014191f7, 9 },
+  {       2039, 0x0121456f, 0x0161e69e, 10 },
+  {       4093, 0x00300902, 0x00501908, 11 },
+  {       8191, 0x00080041, 0x00180241, 12 },
+  {      16381, 0x000c0091, 0x00140191, 13 },
+  {      32749, 0x002605a5, 0x002a06e6, 14 },
+  {      65521, 0x000f00e2, 0x00110122, 15 },
+  {     131071, 0x00008001, 0x00018003, 16 },
+  {     262139, 0x00014002, 0x0001c004, 17 },
+  {     524287, 0x00002001, 0x00006001, 18 },
+  {    1048573, 0x00003001, 0x00005001, 19 },
+  {    2097143, 0x00004801, 0x00005801, 20 },
+  {    4194301, 0x00000c01, 0x00001401, 21 },
+  {    8388593, 0x00001e01, 0x00002201, 22 },
+  {   16777213, 0x00000301, 0x00000501, 23 },
+  {   33554393, 0x00001381, 0x00001481, 24 },
+  {   67108859, 0x00000141, 0x000001c1, 25 },
+  {  134217689, 0x000004e1, 0x00000521, 26 },
+  {  268435399, 0x00000391, 0x000003b1, 27 },
+  {  536870909, 0x00000019, 0x00000029, 28 },
+  { 1073741789, 0x0000008d, 0x00000095, 29 },
+  { 2147483647, 0x00000003, 0x00000007, 30 },
+  /* Avoid "decimal constant so large it is unsigned" for 4294967291.  */
+  { 0xfffffffb, 0x00000006, 0x00000008, 31 }
+};
+
+/* Limit number of comparisons when calling hash_table<>::verify.  */
+unsigned int hash_table_sanitize_eq_limit;
+
+/* The following function returns an index into the above table of the
+   nearest prime number which is greater than N, and near a power of two. */
+
+unsigned int
+hash_table_higher_prime_index (unsigned long n)
+{
+  unsigned int low = 0;
+  unsigned int high = sizeof (prime_tab) / sizeof (prime_tab[0]);
+
+  while (low != high)
+    {
+      unsigned int mid = low + (high - low) / 2;
+      if (n > prime_tab[mid].prime)
+	low = mid + 1;
+      else
+	high = mid;
+    }
+
+  /* If we've run out of primes, abort.  */
+  gdb_assert (n <= prime_tab[low].prime);
+
+  return low;
+}
diff --git a/gdb/hash-table.h b/gdb/hash-table.h
new file mode 100644
index 00000000000..3427fc79bda
--- /dev/null
+++ b/gdb/hash-table.h
@@ -0,0 +1,1038 @@
+/* A type-safe hash table template.
+   Copyright (C) 2012-2019 Free Software Foundation, Inc.
+   Contributed by Lawrence Crowl <crowl@google.com>
+
+This file is part of GDB. It was forked from GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+
+/* This file implements a typed hash table.
+   The implementation borrows from libiberty's htab_t in hashtab.h.
+
+
+   INTRODUCTION TO TYPES
+
+   Users of the hash table generally need to be aware of three types.
+
+      1. The type being placed into the hash table.  This type is called
+      the value type.
+
+      2. The type used to describe how to handle the value type within
+      the hash table.  This descriptor type provides the hash table with
+      several things.
+
+         - A typedef named 'value_type' to the value type (from above).
+	 Provided a suitable Descriptor class it may be a user-defined,
+	 non-POD type.
+
+         - A static member function named 'hash' that takes a value_type
+         (or 'const value_type &') and returns a hashval_t value.
+
+         - A typedef named 'compare_type' that is used to test when a value
+	 is found.  This type is the comparison type.  Usually, it will be
+	 the same as value_type and may be a user-defined, non-POD type.
+	 If it is not the same type, you must generally explicitly compute
+	 hash values and pass them to the hash table.
+
+         - A static member function named 'equal' that takes a value_type
+         and a compare_type, and returns a bool.  Both arguments can be
+         const references.
+
+         - A static function named 'remove' that takes an value_type pointer
+         and frees the memory allocated by it.  This function is used when
+         individual elements of the table need to be disposed of (e.g.,
+         when deleting a hash table, removing elements from the table, etc).
+
+	 - An optional static function named 'keep_cache_entry'.  This
+	 function is provided only for garbage-collected elements that
+	 are not marked by the normal gc mark pass.  It describes what
+	 what should happen to the element at the end of the gc mark phase.
+	 The return value should be:
+	   - 0 if the element should be deleted
+	   - 1 if the element should be kept and needs to be marked
+	   - -1 if the element should be kept and is already marked.
+	 Returning -1 rather than 1 is purely an optimization.
+
+      3. The type of the hash table itself.  (More later.)
+
+   In very special circumstances, users may need to know about a fourth type.
+
+      4. The template type used to describe how hash table memory
+      is allocated.  This type is called the allocator type.  It is
+      parameterized on the value type.  It provides two functions:
+
+         - A static member function named 'data_alloc'.  This function
+         allocates the data elements in the table.
+
+         - A static member function named 'data_free'.  This function
+         deallocates the data elements in the table.
+
+   Hash table are instantiated with two type arguments.
+
+      * The descriptor type, (2) above.
+
+      * The allocator type, (4) above.  In general, you will not need to
+      provide your own allocator type.  By default, hash tables will use
+      the class template xcallocator, which uses malloc/free for allocation.
+
+
+   DEFINING A DESCRIPTOR TYPE
+
+   The first task in using the hash table is to describe the element type.
+   We compose this into a few steps.
+
+      1. Decide on a removal policy for values stored in the table.
+         hash-traits.h provides class templates for the four most common
+         policies:
+
+         * typed_free_remove implements the static 'remove' member function
+         by calling free().
+
+         * typed_noop_remove implements the static 'remove' member function
+         by doing nothing.
+
+         You can use these policies by simply deriving the descriptor type
+         from one of those class template, with the appropriate argument.
+
+         Otherwise, you need to write the static 'remove' member function
+         in the descriptor class.
+
+      2. Choose a hash function.  Write the static 'hash' member function.
+
+      3. Decide whether the lookup function should take as input an object
+	 of type value_type or something more restricted.  Define compare_type
+	 accordingly.
+
+      4. Choose an equality testing function 'equal' that compares a value_type
+	 and a compare_type.
+
+   If your elements are pointers, it is usually easiest to start with one
+   of the generic pointer descriptors described below and override the bits
+   you need to change.
+
+   AN EXAMPLE DESCRIPTOR TYPE
+
+   Suppose you want to put some_type into the hash table.  You could define
+   the descriptor type as follows.
+
+      struct some_type_hasher : nofree_ptr_hash <some_type>
+      // Deriving from nofree_ptr_hash means that we get a 'remove' that does
+      // nothing.  This choice is good for raw values.
+      {
+        static inline hashval_t hash (const value_type *);
+        static inline bool equal (const value_type *, const compare_type *);
+      };
+
+      inline hashval_t
+      some_type_hasher::hash (const value_type *e)
+      { ... compute and return a hash value for E ... }
+
+      inline bool
+      some_type_hasher::equal (const value_type *p1, const compare_type *p2)
+      { ... compare P1 vs P2.  Return true if they are the 'same' ... }
+
+
+   AN EXAMPLE HASH_TABLE DECLARATION
+
+   To instantiate a hash table for some_type:
+
+      hash_table <some_type_hasher> some_type_hash_table;
+
+   There is no need to mention some_type directly, as the hash table will
+   obtain it using some_type_hasher::value_type.
+
+   You can then use any of the functions in hash_table's public interface.
+   See hash_table for details.  The interface is very similar to libiberty's
+   htab_t.
+
+   If a hash table is used only in some rare cases, it is possible
+   to construct the hash_table lazily before first use.  This is done
+   through:
+
+      hash_table <some_type_hasher, true> some_type_hash_table;
+
+   which will cause whatever methods actually need the allocated entries
+   array to allocate it later.
+
+
+   EASY DESCRIPTORS FOR POINTERS
+
+   There are four descriptors for pointer elements, one for each of
+   the removal policies above:
+
+   * nofree_ptr_hash (based on typed_noop_remove)
+   * free_ptr_hash (based on typed_free_remove)
+
+   These descriptors hash and compare elements by their pointer value,
+   rather than what they point to.  So, to instantiate a hash table over
+   pointers to whatever_type, without freeing the whatever_types, use:
+
+      hash_table <nofree_ptr_hash <whatever_type> > whatever_type_hash_table;
+
+
+   HASH TABLE ITERATORS
+
+   The hash table provides standard C++ iterators.  For example, consider a
+   hash table of some_info.  We wish to consume each element of the table:
+
+      extern void consume (some_info *);
+
+   We define a convenience typedef and the hash table:
+
+      typedef hash_table <some_info_hasher> info_table_type;
+      info_table_type info_table;
+
+   Then we write the loop in typical C++ style:
+
+      for (info_table_type::iterator iter = info_table.begin ();
+           iter != info_table.end ();
+           ++iter)
+        if ((*iter).status == INFO_READY)
+          consume (&*iter);
+
+   Or with common sub-expression elimination:
+
+      for (info_table_type::iterator iter = info_table.begin ();
+           iter != info_table.end ();
+           ++iter)
+        {
+          some_info &elem = *iter;
+          if (elem.status == INFO_READY)
+            consume (&elem);
+        }
+
+   One can also use a more typical GCC style:
+
+      typedef some_info *some_info_p;
+      some_info *elem_ptr;
+      info_table_type::iterator iter;
+      FOR_EACH_HASH_TABLE_ELEMENT (info_table, elem_ptr, some_info_p, iter)
+        if (elem_ptr->status == INFO_READY)
+          consume (elem_ptr);
+
+*/
+
+
+#ifndef TYPED_HASHTAB_H
+#define TYPED_HASHTAB_H
+
+#include "hashtab.h"
+#include "hash-traits.h"
+#include "hash-map-traits.h"
+
+template<typename, typename, typename> class hash_map;
+template<typename, bool, typename> class hash_set;
+
+/* The ordinary memory allocator.  */
+/* FIXME (crowl): This allocator may be extracted for wider sharing later.  */
+
+template <typename Type>
+struct xcallocator
+{
+  static Type *data_alloc (size_t count);
+  static void data_free (Type *memory);
+};
+
+
+/* Allocate memory for COUNT data blocks.  */
+
+template <typename Type>
+inline Type *
+xcallocator <Type>::data_alloc (size_t count)
+{
+  return static_cast <Type *> (xcalloc (count, sizeof (Type)));
+}
+
+
+/* Free memory for data blocks.  */
+
+template <typename Type>
+inline void
+xcallocator <Type>::data_free (Type *memory)
+{
+  return ::free (memory);
+}
+
+
+/* Table of primes and their inversion information.  */
+
+struct prime_ent
+{
+  hashval_t prime;
+  hashval_t inv;
+  hashval_t inv_m2;     /* inverse of prime-2 */
+  hashval_t shift;
+};
+
+extern struct prime_ent const prime_tab[];
+
+/* Limit number of comparisons when calling hash_table<>::verify.  */
+extern unsigned int hash_table_sanitize_eq_limit;
+
+/* Functions for computing hash table indexes.  */
+
+extern unsigned int hash_table_higher_prime_index (unsigned long n)
+   ATTRIBUTE_PURE;
+
+extern ATTRIBUTE_NORETURN ATTRIBUTE_COLD void hashtab_chk_error ();
+
+/* Return X % Y using multiplicative inverse values INV and SHIFT.
+
+   The multiplicative inverses computed above are for 32-bit types,
+   and requires that we be able to compute a highpart multiply.
+
+   FIX: I am not at all convinced that
+     3 loads, 2 multiplications, 3 shifts, and 3 additions
+   will be faster than
+     1 load and 1 modulus
+   on modern systems running a compiler.  */
+
+inline hashval_t
+mul_mod (hashval_t x, hashval_t y, hashval_t inv, int shift)
+{
+   hashval_t t1, t2, t3, t4, q, r;
+
+   t1 = ((uint64_t)x * inv) >> 32;
+   t2 = x - t1;
+   t3 = t2 >> 1;
+   t4 = t1 + t3;
+   q  = t4 >> shift;
+   r  = x - (q * y);
+
+   return r;
+}
+
+/* Compute the primary table index for HASH given current prime index.  */
+
+inline hashval_t
+hash_table_mod1 (hashval_t hash, unsigned int index)
+{
+  const struct prime_ent *p = &prime_tab[index];
+  gdb_assert (sizeof (hashval_t) * CHAR_BIT <= 32);
+  return mul_mod (hash, p->prime, p->inv, p->shift);
+}
+
+/* Compute the secondary table index for HASH given current prime index.  */
+
+inline hashval_t
+hash_table_mod2 (hashval_t hash, unsigned int index)
+{
+  const struct prime_ent *p = &prime_tab[index];
+  gdb_assert (sizeof (hashval_t) * CHAR_BIT <= 32);
+  return 1 + mul_mod (hash, p->prime - 2, p->inv_m2, p->shift);
+}
+
+class mem_usage;
+
+/* User-facing hash table type.
+
+   The table stores elements of type Descriptor::value_type and uses
+   the static descriptor functions described at the top of the file
+   to hash, compare and remove elements.
+
+   Specify the template Allocator to allocate and free memory.
+     The default is xcallocator.
+
+     Storage is an implementation detail and should not be used outside the
+     hash table code.
+
+*/
+template <typename Descriptor, bool Lazy = false,
+	  template<typename Type> class Allocator = xcallocator>
+class hash_table
+{
+  typedef typename Descriptor::value_type value_type;
+  typedef typename Descriptor::compare_type compare_type;
+
+public:
+  explicit hash_table (size_t,
+		       bool sanitize_eq_and_hash = true);
+  explicit hash_table (const hash_table &,
+		       bool sanitize_eq_and_hash = true);
+  ~hash_table ();
+
+  /* Current size (in entries) of the hash table.  */
+  size_t size () const { return m_size; }
+
+  /* Return the current number of elements in this hash table. */
+  size_t elements () const { return m_n_elements - m_n_deleted; }
+
+  /* Return the current number of elements in this hash table. */
+  size_t elements_with_deleted () const { return m_n_elements; }
+
+  /* This function clears all entries in this hash table.  */
+  void empty () { if (elements ()) empty_slow (); }
+
+  /* Return true when there are no elements in this hash table.  */
+  bool is_empty () const { return elements () == 0; }
+
+  /* This function clears a specified SLOT in a hash table.  It is
+     useful when you've already done the lookup and don't want to do it
+     again. */
+  void clear_slot (value_type *);
+
+  /* This function searches for a hash table entry equal to the given
+     COMPARABLE element starting with the given HASH value.  It cannot
+     be used to insert or delete an element. */
+  value_type &find_with_hash (const compare_type &, hashval_t);
+
+  /* Like find_slot_with_hash, but compute the hash value from the element.  */
+  value_type &find (const value_type &value)
+    {
+      return find_with_hash (value, Descriptor::hash (value));
+    }
+
+  value_type *find_slot (const value_type &value, insert_option insert)
+    {
+      return find_slot_with_hash (value, Descriptor::hash (value), insert);
+    }
+
+  /* This function searches for a hash table slot containing an entry
+     equal to the given COMPARABLE element and starting with the given
+     HASH.  To delete an entry, call this with insert=NO_INSERT, then
+     call clear_slot on the slot returned (possibly after doing some
+     checks).  To insert an entry, call this with insert=INSERT, then
+     write the value you want into the returned slot.  When inserting an
+     entry, NULL may be returned if memory allocation fails. */
+  value_type *find_slot_with_hash (const compare_type &comparable,
+				   hashval_t hash, enum insert_option insert);
+
+  /* This function deletes an element with the given COMPARABLE value
+     from hash table starting with the given HASH.  If there is no
+     matching element in the hash table, this function does nothing. */
+  void remove_elt_with_hash (const compare_type &, hashval_t);
+
+  /* Like remove_elt_with_hash, but compute the hash value from the
+     element.  */
+  void remove_elt (const value_type &value)
+    {
+      remove_elt_with_hash (value, Descriptor::hash (value));
+    }
+
+  /* This function scans over the entire hash table calling CALLBACK for
+     each live entry.  If CALLBACK returns false, the iteration stops.
+     ARGUMENT is passed as CALLBACK's second argument. */
+  template <typename Argument,
+	    int (*Callback) (value_type *slot, Argument argument)>
+  void traverse_noresize (Argument argument);
+
+  /* Like traverse_noresize, but does resize the table when it is too empty
+     to improve effectivity of subsequent calls.  */
+  template <typename Argument,
+	    int (*Callback) (value_type *slot, Argument argument)>
+  void traverse (Argument argument);
+
+  class iterator
+  {
+  public:
+    iterator () : m_slot (NULL), m_limit (NULL) {}
+
+    iterator (value_type *slot, value_type *limit) :
+      m_slot (slot), m_limit (limit) {}
+
+    inline value_type &operator * () { return *m_slot; }
+    void slide ();
+    inline iterator &operator ++ ();
+    bool operator != (const iterator &other) const
+      {
+	return m_slot != other.m_slot || m_limit != other.m_limit;
+      }
+
+  private:
+    value_type *m_slot;
+    value_type *m_limit;
+  };
+
+  iterator begin () const
+    {
+      if (Lazy && m_entries == NULL)
+	return iterator ();
+      iterator iter (m_entries, m_entries + m_size);
+      iter.slide ();
+      return iter;
+    }
+
+  iterator end () const { return iterator (); }
+
+  double collisions () const
+    {
+      return m_searches ? static_cast <double> (m_collisions) / m_searches : 0;
+    }
+
+private:
+  /* FIXME: Make the class assignable.  See pr90959.  */
+  void operator= (hash_table&);
+
+  void empty_slow ();
+
+  value_type *alloc_entries (size_t n) const;
+  value_type *find_empty_slot_for_expand (hashval_t);
+  void verify (const compare_type &comparable, hashval_t hash);
+  bool too_empty_p (unsigned int);
+  void expand ();
+  static bool is_deleted (value_type &v)
+  {
+    return Descriptor::is_deleted (v);
+  }
+
+  static bool is_empty (value_type &v)
+  {
+    return Descriptor::is_empty (v);
+  }
+
+  static void mark_deleted (value_type &v)
+  {
+    Descriptor::mark_deleted (v);
+  }
+
+  static void mark_empty (value_type &v)
+  {
+    Descriptor::mark_empty (v);
+  }
+
+  /* Table itself.  */
+  typename Descriptor::value_type *m_entries;
+
+  size_t m_size;
+
+  /* Current number of elements including also deleted elements.  */
+  size_t m_n_elements;
+
+  /* Current number of deleted elements in the table.  */
+  size_t m_n_deleted;
+
+  /* The following member is used for debugging. Its value is number
+     of all calls of `htab_find_slot' for the hash table. */
+  unsigned int m_searches;
+
+  /* The following member is used for debugging.  Its value is number
+     of collisions fixed for time of work with the hash table. */
+  unsigned int m_collisions;
+
+  /* Current size (in entries) of the hash table, as an index into the
+     table of primes.  */
+  unsigned int m_size_prime_index;
+
+  /* True if the table should be sanitized for equal and hash functions.  */
+  bool m_sanitize_eq_and_hash;
+};
+
+/* As mem-stats.h heavily utilizes hash maps (hash tables), we have to include
+   mem-stats.h after hash_table declaration.  */
+
+#include "hash-map.h"
+
+/* Support function for statistics.  */
+extern void dump_hash_table_loc_statistics (void);
+
+template<typename Descriptor, bool Lazy,
+	 template<typename Type> class Allocator>
+hash_table<Descriptor, Lazy, Allocator>::hash_table (size_t size,
+						     bool sanitize_eq_and_hash) :
+  m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
+  m_sanitize_eq_and_hash (sanitize_eq_and_hash)
+{
+  unsigned int size_prime_index;
+
+  size_prime_index = hash_table_higher_prime_index (size);
+  size = prime_tab[size_prime_index].prime;
+
+  if (Lazy)
+    m_entries = NULL;
+  else
+    m_entries = alloc_entries (size);
+  m_size = size;
+  m_size_prime_index = size_prime_index;
+}
+
+template<typename Descriptor, bool Lazy,
+	 template<typename Type> class Allocator>
+hash_table<Descriptor, Lazy, Allocator>::hash_table (const hash_table &h,
+						     bool sanitize_eq_and_hash) :
+  m_n_elements (h.m_n_elements), m_n_deleted (h.m_n_deleted),
+  m_searches (0), m_collisions (0),
+  m_sanitize_eq_and_hash (sanitize_eq_and_hash)
+{
+  size_t size = h.m_size;
+
+  if (Lazy && h.m_entries == NULL)
+    m_entries = NULL;
+  else
+    {
+      value_type *nentries = alloc_entries (size);
+      for (size_t i = 0; i < size; ++i)
+	{
+	  value_type &entry = h.m_entries[i];
+	  if (is_deleted (entry))
+	    mark_deleted (nentries[i]);
+	  else if (!is_empty (entry))
+	    new ((void*) (nentries + i)) value_type (entry);
+	}
+      m_entries = nentries;
+    }
+  m_size = size;
+  m_size_prime_index = h.m_size_prime_index;
+}
+
+template<typename Descriptor, bool Lazy,
+	 template<typename Type> class Allocator>
+hash_table<Descriptor, Lazy, Allocator>::~hash_table ()
+{
+  if (!Lazy || m_entries)
+    {
+      for (size_t i = m_size - 1; i < m_size; i--)
+	if (!is_empty (m_entries[i]) && !is_deleted (m_entries[i]))
+	  Descriptor::remove (m_entries[i]);
+
+      Allocator <value_type> ::data_free (m_entries);
+    }
+}
+
+/* This function returns an array of empty hash table elements.  */
+
+template<typename Descriptor, bool Lazy,
+	 template<typename Type> class Allocator>
+inline typename hash_table<Descriptor, Lazy, Allocator>::value_type *
+hash_table<Descriptor, Lazy,
+	   Allocator>::alloc_entries (size_t n) const
+{
+  value_type *nentries;
+
+  nentries = Allocator <value_type> ::data_alloc (n);
+
+  gdb_assert (nentries != NULL);
+  for (size_t i = 0; i < n; i++)
+    mark_empty (nentries[i]);
+
+  return nentries;
+}
+
+/* Similar to find_slot, but without several unwanted side effects:
+    - Does not call equal when it finds an existing entry.
+    - Does not change the count of elements/searches/collisions in the
+      hash table.
+   This function also assumes there are no deleted entries in the table.
+   HASH is the hash value for the element to be inserted.  */
+
+template<typename Descriptor, bool Lazy,
+	 template<typename Type> class Allocator>
+typename hash_table<Descriptor, Lazy, Allocator>::value_type *
+hash_table<Descriptor, Lazy,
+	   Allocator>::find_empty_slot_for_expand (hashval_t hash)
+{
+  hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
+  size_t size = m_size;
+  value_type *slot = m_entries + index;
+  hashval_t hash2;
+
+  if (is_empty (*slot))
+    return slot;
+  gdb_assert (!is_deleted (*slot));
+
+  hash2 = hash_table_mod2 (hash, m_size_prime_index);
+  for (;;)
+    {
+      index += hash2;
+      if (index >= size)
+        index -= size;
+
+      slot = m_entries + index;
+      if (is_empty (*slot))
+        return slot;
+      gdb_assert (!is_deleted (*slot));
+    }
+}
+
+/* Return true if the current table is excessively big for ELTS elements.  */
+
+template<typename Descriptor, bool Lazy,
+	 template<typename Type> class Allocator>
+inline bool
+hash_table<Descriptor, Lazy, Allocator>::too_empty_p (unsigned int elts)
+{
+  return elts * 8 < m_size && m_size > 32;
+}
+
+/* The following function changes size of memory allocated for the
+   entries and repeatedly inserts the table elements.  The occupancy
+   of the table after the call will be about 50%.  Naturally the hash
+   table must already exist.  Remember also that the place of the
+   table entries is changed.  If memory allocation fails, this function
+   will abort.  */
+
+template<typename Descriptor, bool Lazy,
+	 template<typename Type> class Allocator>
+void
+hash_table<Descriptor, Lazy, Allocator>::expand ()
+{
+  value_type *oentries = m_entries;
+  unsigned int oindex = m_size_prime_index;
+  size_t osize = size ();
+  value_type *olimit = oentries + osize;
+  size_t elts = elements ();
+
+  /* Resize only when table after removal of unused elements is either
+     too full or too empty.  */
+  unsigned int nindex;
+  size_t nsize;
+  if (elts * 2 > osize || too_empty_p (elts))
+    {
+      nindex = hash_table_higher_prime_index (elts * 2);
+      nsize = prime_tab[nindex].prime;
+    }
+  else
+    {
+      nindex = oindex;
+      nsize = osize;
+    }
+
+  value_type *nentries = alloc_entries (nsize);
+
+  m_entries = nentries;
+  m_size = nsize;
+  m_size_prime_index = nindex;
+  m_n_elements -= m_n_deleted;
+  m_n_deleted = 0;
+
+  value_type *p = oentries;
+  do
+    {
+      value_type &x = *p;
+
+      if (!is_empty (x) && !is_deleted (x))
+        {
+          value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
+
+          *q = x;
+        }
+
+      p++;
+    }
+  while (p < olimit);
+
+  Allocator <value_type> ::data_free (oentries);
+}
+
+/* Implements empty() in cases where it isn't a no-op.  */
+
+template<typename Descriptor, bool Lazy,
+	 template<typename Type> class Allocator>
+void
+hash_table<Descriptor, Lazy, Allocator>::empty_slow ()
+{
+  size_t size = m_size;
+  size_t nsize = size;
+  value_type *entries = m_entries;
+  int i;
+
+  for (i = size - 1; i >= 0; i--)
+    if (!is_empty (entries[i]) && !is_deleted (entries[i]))
+      Descriptor::remove (entries[i]);
+
+  /* Instead of clearing megabyte, downsize the table.  */
+  if (size > 1024*1024 / sizeof (value_type))
+    nsize = 1024 / sizeof (value_type);
+  else if (too_empty_p (m_n_elements))
+    nsize = m_n_elements * 2;
+
+  if (nsize != size)
+    {
+      int nindex = hash_table_higher_prime_index (nsize);
+      int nsize2 = prime_tab[nindex].prime;
+
+      Allocator <value_type> ::data_free (m_entries);
+
+      m_entries = alloc_entries (nsize);
+      m_size = nsize2;
+      m_size_prime_index = nindex;
+    }
+  else
+    {
+#ifndef BROKEN_VALUE_INITIALIZATION
+      for ( ; size; ++entries, --size)
+	*entries = value_type ();
+#else
+      memset (entries, 0, size * sizeof (value_type));
+#endif
+    }
+  m_n_deleted = 0;
+  m_n_elements = 0;
+}
+
+/* This function clears a specified SLOT in a hash table.  It is
+   useful when you've already done the lookup and don't want to do it
+   again. */
+
+template<typename Descriptor, bool Lazy,
+	 template<typename Type> class Allocator>
+void
+hash_table<Descriptor, Lazy, Allocator>::clear_slot (value_type *slot)
+{
+  gdb_assert (!(slot < m_entries || slot >= m_entries + size ()
+		         || is_empty (*slot) || is_deleted (*slot)));
+
+  Descriptor::remove (*slot);
+
+  mark_deleted (*slot);
+  m_n_deleted++;
+}
+
+/* This function searches for a hash table entry equal to the given
+   COMPARABLE element starting with the given HASH value.  It cannot
+   be used to insert or delete an element. */
+
+template<typename Descriptor, bool Lazy,
+	 template<typename Type> class Allocator>
+typename hash_table<Descriptor, Lazy, Allocator>::value_type &
+hash_table<Descriptor, Lazy, Allocator>
+::find_with_hash (const compare_type &comparable, hashval_t hash)
+{
+  m_searches++;
+  size_t size = m_size;
+  hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
+
+  if (Lazy && m_entries == NULL)
+    m_entries = alloc_entries (size);
+  value_type *entry = &m_entries[index];
+  if (is_empty (*entry)
+      || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
+    return *entry;
+
+  hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
+  for (;;)
+    {
+      m_collisions++;
+      index += hash2;
+      if (index >= size)
+        index -= size;
+
+      entry = &m_entries[index];
+      if (is_empty (*entry)
+          || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
+	{
+#if CHECKING_P
+	  if (m_sanitize_eq_and_hash)
+	    verify (comparable, hash);
+#endif
+	  return *entry;
+	}
+    }
+}
+
+/* This function searches for a hash table slot containing an entry
+   equal to the given COMPARABLE element and starting with the given
+   HASH.  To delete an entry, call this with insert=NO_INSERT, then
+   call clear_slot on the slot returned (possibly after doing some
+   checks).  To insert an entry, call this with insert=INSERT, then
+   write the value you want into the returned slot.  When inserting an
+   entry, NULL may be returned if memory allocation fails. */
+
+template<typename Descriptor, bool Lazy,
+	 template<typename Type> class Allocator>
+typename hash_table<Descriptor, Lazy, Allocator>::value_type *
+hash_table<Descriptor, Lazy, Allocator>
+::find_slot_with_hash (const compare_type &comparable, hashval_t hash,
+		       enum insert_option insert)
+{
+  if (Lazy && m_entries == NULL)
+    {
+      if (insert == INSERT)
+	m_entries = alloc_entries (m_size);
+      else
+	return NULL;
+    }
+  if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
+    expand ();
+
+#if CHECKING_P
+  if (m_sanitize_eq_and_hash)
+    verify (comparable, hash);
+#endif
+
+  m_searches++;
+  value_type *first_deleted_slot = NULL;
+  hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
+  hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
+  value_type *entry = &m_entries[index];
+  size_t size = m_size;
+  if (is_empty (*entry))
+    goto empty_entry;
+  else if (is_deleted (*entry))
+    first_deleted_slot = &m_entries[index];
+  else if (Descriptor::equal (*entry, comparable))
+    return &m_entries[index];
+
+  for (;;)
+    {
+      m_collisions++;
+      index += hash2;
+      if (index >= size)
+	index -= size;
+
+      entry = &m_entries[index];
+      if (is_empty (*entry))
+	goto empty_entry;
+      else if (is_deleted (*entry))
+	{
+	  if (!first_deleted_slot)
+	    first_deleted_slot = &m_entries[index];
+	}
+      else if (Descriptor::equal (*entry, comparable))
+	return &m_entries[index];
+    }
+
+ empty_entry:
+  if (insert == NO_INSERT)
+    return NULL;
+
+  if (first_deleted_slot)
+    {
+      m_n_deleted--;
+      mark_empty (*first_deleted_slot);
+      return first_deleted_slot;
+    }
+
+  m_n_elements++;
+  return &m_entries[index];
+}
+
+/* Verify that all existing elements in the hash table which are
+   equal to COMPARABLE have an equal HASH value provided as argument.  */
+
+template<typename Descriptor, bool Lazy,
+	 template<typename Type> class Allocator>
+void
+hash_table<Descriptor, Lazy, Allocator>
+::verify (const compare_type &comparable, hashval_t hash)
+{
+  for (size_t i = 0; i < std::min<size_t> (hash_table_sanitize_eq_limit, m_size); i++)
+    {
+      value_type *entry = &m_entries[i];
+      if (!is_empty (*entry) && !is_deleted (*entry)
+	  && hash != Descriptor::hash (*entry)
+	  && Descriptor::equal (*entry, comparable))
+	hashtab_chk_error ();
+    }
+}
+
+/* This function deletes an element with the given COMPARABLE value
+   from hash table starting with the given HASH.  If there is no
+   matching element in the hash table, this function does nothing. */
+
+template<typename Descriptor, bool Lazy,
+	 template<typename Type> class Allocator>
+void
+hash_table<Descriptor, Lazy, Allocator>
+::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
+{
+  value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
+  if (slot == NULL)
+    return;
+
+  Descriptor::remove (*slot);
+
+  mark_deleted (*slot);
+  m_n_deleted++;
+}
+
+/* This function scans over the entire hash table calling CALLBACK for
+   each live entry.  If CALLBACK returns false, the iteration stops.
+   ARGUMENT is passed as CALLBACK's second argument. */
+
+template<typename Descriptor, bool Lazy,
+	  template<typename Type> class Allocator>
+template<typename Argument,
+	 int (*Callback)
+	 (typename hash_table<Descriptor, Lazy, Allocator>::value_type *slot,
+	 Argument argument)>
+void
+hash_table<Descriptor, Lazy, Allocator>::traverse_noresize (Argument argument)
+{
+  if (Lazy && m_entries == NULL)
+    return;
+
+  value_type *slot = m_entries;
+  value_type *limit = slot + size ();
+
+  do
+    {
+      value_type &x = *slot;
+
+      if (!is_empty (x) && !is_deleted (x))
+        if (! Callback (slot, argument))
+          break;
+    }
+  while (++slot < limit);
+}
+
+/* Like traverse_noresize, but does resize the table when it is too empty
+   to improve effectivity of subsequent calls.  */
+
+template <typename Descriptor, bool Lazy,
+	  template <typename Type> class Allocator>
+template <typename Argument,
+	  int (*Callback)
+	  (typename hash_table<Descriptor, Lazy, Allocator>::value_type *slot,
+	  Argument argument)>
+void
+hash_table<Descriptor, Lazy, Allocator>::traverse (Argument argument)
+{
+  if (too_empty_p (elements ()) && (!Lazy || m_entries))
+    expand ();
+
+  traverse_noresize <Argument, Callback> (argument);
+}
+
+/* Slide down the iterator slots until an active entry is found.  */
+
+template<typename Descriptor, bool Lazy,
+	 template<typename Type> class Allocator>
+void
+hash_table<Descriptor, Lazy, Allocator>::iterator::slide ()
+{
+  for ( ; m_slot < m_limit; ++m_slot )
+    {
+      value_type &x = *m_slot;
+      if (!is_empty (x) && !is_deleted (x))
+        return;
+    }
+  m_slot = NULL;
+  m_limit = NULL;
+}
+
+/* Bump the iterator.  */
+
+template<typename Descriptor, bool Lazy,
+	 template<typename Type> class Allocator>
+inline typename hash_table<Descriptor, Lazy, Allocator>::iterator &
+hash_table<Descriptor, Lazy, Allocator>::iterator::operator ++ ()
+{
+  ++m_slot;
+  slide ();
+  return *this;
+}
+
+
+/* Iterate through the elements of hash_table HTAB,
+   using hash_table <....>::iterator ITER,
+   storing each element in RESULT, which is of type TYPE.  */
+
+#define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
+  for ((ITER) = (HTAB).begin (); \
+       (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
+       ++(ITER))
+
+#endif /* TYPED_HASHTAB_H */
diff --git a/gdb/hash-traits.h b/gdb/hash-traits.h
new file mode 100644
index 00000000000..c31edc96039
--- /dev/null
+++ b/gdb/hash-traits.h
@@ -0,0 +1,322 @@
+/* Traits for hashable types.
+   Copyright (C) 2014-2019 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef hash_traits_h
+#define hash_traits_h
+
+/* Helpful type for removing with free.  */
+
+template <typename Type>
+struct typed_free_remove
+{
+  static inline void remove (Type *p);
+};
+
+
+/* Remove with free.  */
+
+template <typename Type>
+inline void
+typed_free_remove <Type>::remove (Type *p)
+{
+  free (p);
+}
+
+/* Helpful type for removing with delete.  */
+
+template <typename Type>
+struct typed_delete_remove
+{
+  static inline void remove (Type *p);
+};
+
+
+/* Remove with delete.  */
+
+template <typename Type>
+inline void
+typed_delete_remove <Type>::remove (Type *p)
+{
+  delete p;
+}
+
+/* Helpful type for a no-op remove.  */
+
+template <typename Type>
+struct typed_noop_remove
+{
+  static inline void remove (Type &);
+};
+
+
+/* Remove doing nothing.  */
+
+template <typename Type>
+inline void
+typed_noop_remove <Type>::remove (Type &)
+{
+}
+
+
+/* Hasher for integer type Type in which Empty is a spare value that can be
+   used to mark empty slots.  If Deleted != Empty then Deleted is another
+   spare value that can be used for deleted slots; if Deleted == Empty then
+   hash table entries cannot be deleted.  */
+
+template <typename Type, Type Empty, Type Deleted = Empty>
+struct int_hash : typed_noop_remove <Type>
+{
+  typedef Type value_type;
+  typedef Type compare_type;
+
+  static inline hashval_t hash (value_type);
+  static inline bool equal (value_type existing, value_type candidate);
+  static inline void mark_deleted (Type &);
+  static inline void mark_empty (Type &);
+  static inline bool is_deleted (Type);
+  static inline bool is_empty (Type);
+};
+
+template <typename Type, Type Empty, Type Deleted>
+inline hashval_t
+int_hash <Type, Empty, Deleted>::hash (value_type x)
+{
+  return x;
+}
+
+template <typename Type, Type Empty, Type Deleted>
+inline bool
+int_hash <Type, Empty, Deleted>::equal (value_type x, value_type y)
+{
+  return x == y;
+}
+
+template <typename Type, Type Empty, Type Deleted>
+inline void
+int_hash <Type, Empty, Deleted>::mark_deleted (Type &x)
+{
+  gdb_assert (Empty != Deleted);
+  x = Deleted;
+}
+
+template <typename Type, Type Empty, Type Deleted>
+inline void
+int_hash <Type, Empty, Deleted>::mark_empty (Type &x)
+{
+  x = Empty;
+}
+
+template <typename Type, Type Empty, Type Deleted>
+inline bool
+int_hash <Type, Empty, Deleted>::is_deleted (Type x)
+{
+  return Empty != Deleted && x == Deleted;
+}
+
+template <typename Type, Type Empty, Type Deleted>
+inline bool
+int_hash <Type, Empty, Deleted>::is_empty (Type x)
+{
+  return x == Empty;
+}
+
+/* Pointer hasher based on pointer equality.  Other types of pointer hash
+   can inherit this and override the hash and equal functions with some
+   other form of equality (such as string equality).  */
+
+template <typename Type>
+struct pointer_hash
+{
+  typedef Type *value_type;
+  typedef Type *compare_type;
+
+  static inline hashval_t hash (const value_type &);
+  static inline bool equal (const value_type &existing,
+			    const compare_type &candidate);
+  static inline void mark_deleted (Type *&);
+  static inline void mark_empty (Type *&);
+  static inline bool is_deleted (Type *);
+  static inline bool is_empty (Type *);
+};
+
+template <typename Type>
+inline hashval_t
+pointer_hash <Type>::hash (const value_type &candidate)
+{
+  /* This is a really poor hash function, but it is what the current code uses,
+     so I am reusing it to avoid an additional axis in testing.  */
+  return (hashval_t) ((intptr_t)candidate >> 3);
+}
+
+template <typename Type>
+inline bool
+pointer_hash <Type>::equal (const value_type &existing,
+			   const compare_type &candidate)
+{
+  return existing == candidate;
+}
+
+template <typename Type>
+inline void
+pointer_hash <Type>::mark_deleted (Type *&e)
+{
+  e = reinterpret_cast<Type *> (1);
+}
+
+template <typename Type>
+inline void
+pointer_hash <Type>::mark_empty (Type *&e)
+{
+  e = NULL;
+}
+
+template <typename Type>
+inline bool
+pointer_hash <Type>::is_deleted (Type *e)
+{
+  return e == reinterpret_cast<Type *> (1);
+}
+
+template <typename Type>
+inline bool
+pointer_hash <Type>::is_empty (Type *e)
+{
+  return e == NULL;
+}
+
+/* Hasher for "const char *" strings, using string rather than pointer
+   equality.  */
+
+struct string_hash : pointer_hash <const char>
+{
+  static inline hashval_t hash (const char *);
+  static inline bool equal (const char *, const char *);
+};
+
+inline hashval_t
+string_hash::hash (const char *id)
+{
+  return htab_hash_string (id);
+}
+
+inline bool
+string_hash::equal (const char *id1, const char *id2)
+{
+  return strcmp (id1, id2) == 0;
+}
+
+/* Traits for pointer elements that should not be freed when an element
+   is deleted.  */
+
+template <typename T>
+struct nofree_ptr_hash : pointer_hash <T>, typed_noop_remove <T *> {};
+
+/* Traits for pointer elements that should be freed via free() when an
+   element is deleted.  */
+
+template <typename T>
+struct free_ptr_hash : pointer_hash <T>, typed_free_remove <T> {};
+
+/* Traits for pointer elements that should be freed via delete operand when an
+   element is deleted.  */
+
+template <typename T>
+struct delete_ptr_hash : pointer_hash <T>, typed_delete_remove <T> {};
+
+/* Traits for string elements that should not be freed when an element
+   is deleted.  */
+
+struct nofree_string_hash : string_hash, typed_noop_remove <const char *> {};
+
+/* Traits for pairs of values, using the first to record empty and
+   deleted slots.  */
+
+template <typename T1, typename T2>
+struct pair_hash
+{
+  typedef std::pair <typename T1::value_type,
+		     typename T2::value_type> value_type;
+  typedef std::pair <typename T1::compare_type,
+		     typename T2::compare_type> compare_type;
+
+  static inline hashval_t hash (const value_type &);
+  static inline bool equal (const value_type &, const compare_type &);
+  static inline void remove (value_type &);
+  static inline void mark_deleted (value_type &);
+  static inline void mark_empty (value_type &);
+  static inline bool is_deleted (const value_type &);
+  static inline bool is_empty (const value_type &);
+};
+
+template <typename T1, typename T2>
+inline hashval_t
+pair_hash <T1, T2>::hash (const value_type &x)
+{
+  return iterative_hash_hashval_t (T1::hash (x.first), T2::hash (x.second));
+}
+
+template <typename T1, typename T2>
+inline bool
+pair_hash <T1, T2>::equal (const value_type &x, const compare_type &y)
+{
+  return T1::equal (x.first, y.first) && T2::equal (x.second, y.second);
+}
+
+template <typename T1, typename T2>
+inline void
+pair_hash <T1, T2>::remove (value_type &x)
+{
+  T1::remove (x.first);
+  T2::remove (x.second);
+}
+
+template <typename T1, typename T2>
+inline void
+pair_hash <T1, T2>::mark_deleted (value_type &x)
+{
+  T1::mark_deleted (x.first);
+}
+
+template <typename T1, typename T2>
+inline void
+pair_hash <T1, T2>::mark_empty (value_type &x)
+{
+  T1::mark_empty (x.first);
+}
+
+template <typename T1, typename T2>
+inline bool
+pair_hash <T1, T2>::is_deleted (const value_type &x)
+{
+  return T1::is_deleted (x.first);
+}
+
+template <typename T1, typename T2>
+inline bool
+pair_hash <T1, T2>::is_empty (const value_type &x)
+{
+  return T1::is_empty (x.first);
+}
+
+template <typename T> struct default_hash_traits : T {};
+
+template <typename T>
+struct default_hash_traits <T *> : pointer_hash <T> {};
+
+#endif