aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorChristian Biesinger <cbiesinger@google.com>2019-09-21 18:00:23 +0900
committerChristian Biesinger <cbiesinger@google.com>2019-09-24 19:53:35 -0500
commit3286a5fda95c1f1988fdecf0f542a0e58d1f4e27 (patch)
tree68d094fa5239eb19102594f0faf42e7dab9d8449
parent3d4352200e3e98a6d8855e6f3a39b6d33d84e36b (diff)
downloadgdb-users/cbiesinger/hashtable.zip
gdb-users/cbiesinger/hashtable.tar.gz
gdb-users/cbiesinger/hashtable.tar.bz2
Fork GCC's hash-table.h for use in GDBusers/cbiesinger/hashtable
And use it at one callsite in dwarf2read.
-rw-r--r--gdb/Makefile.in1
-rw-r--r--gdb/dwarf2read.c23
-rw-r--r--gdb/hash-map-traits.h188
-rw-r--r--gdb/hash-map.h220
-rw-r--r--gdb/hash-table.c97
-rw-r--r--gdb/hash-table.h1038
-rw-r--r--gdb/hash-traits.h322
7 files changed, 1875 insertions, 14 deletions
diff --git a/gdb/Makefile.in b/gdb/Makefile.in
index 877a9cc..b702166 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 1052501..7175c80 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 0000000..af66018
--- /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 0000000..d479196
--- /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 0000000..56aeb14
--- /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 0000000..3427fc7
--- /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 0000000..c31edc96
--- /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