* [PATCH 01/19] Add a hash table to gdbsupport
2023-04-07 15:25 [PATCH 00/19] Add hash table to gdbsupport Tom Tromey
@ 2023-04-07 15:25 ` Tom Tromey
2023-04-07 15:41 ` Tom Tromey
2023-04-07 15:25 ` [PATCH 02/19] Convert compile-c-symbols.c to new hash table Tom Tromey
` (19 subsequent siblings)
20 siblings, 1 reply; 29+ messages in thread
From: Tom Tromey @ 2023-04-07 15:25 UTC (permalink / raw)
To: gdb-patches
This patch adds a new hash table to gdbsupport. This hash table is
template based and type-safe. It is a new implementation; I
considered either writing a type-safe wrapper for the libiberty hash
table, or importing GCC's C++ hash table, but I think this one has
some advantages over both of these.
In comparison to libiberty:
* Type-safe.
* Can hold any type of object.
* Does not need a separate allocation for the table itself.
* Iterators rather than callbacks.
* Due to existing helper trait classes, often easier to instantiate.
The remaining patches in this series all reduce the number of lines
of code. E.g., a trait using std::hash and operator== is built in
and can be used with sets and maps without any more work than
"gdb::hash_set<...>".
* No possibility to introduce the classic bug of calling
htab_find_slot with INSERT and then forgetting to set the element.
In comparison to GCC:
* No tombstones are needed, simplifying trait implementation.
* Probably has better average chain length due to Robin Hood probing.
(I didn't test this.)
* No need to remove all the "ggc" stuff.
* GCC inherits some of the drawbacks of the libiberty approach, for
example the "insert" approach.
I've tried to make the interface relatively complete. A hash map and
a compatibility trait for libiberty-style hashing are both included.
There are maybe some things missing that could still be added:
* operator[] for hash maps. I *think* this could maybe be done, but
it seems a bit tricky.
* erase doesn't accept an iterator argument (easy, I just didn't need
it).
* Checking that the trait hash and equality functions agree. This
could be added but I was worried about the performance impact.
Perhaps if we had a debug assert. (This would have caught a latent
bug that was found by this series -- see the typedef patch.)
* More trait types.
---
gdb/Makefile.in | 1 +
gdb/unittests/hash-table-selftests.c | 128 ++++++++
gdbsupport/Makefile.am | 1 +
gdbsupport/Makefile.in | 19 +-
gdbsupport/hash-table.cc | 75 +++++
gdbsupport/hash-table.h | 551 +++++++++++++++++++++++++++++++++++
6 files changed, 767 insertions(+), 8 deletions(-)
diff --git a/gdb/Makefile.in b/gdb/Makefile.in
index 40497541880..08c809310ff 100644
--- a/gdb/Makefile.in
+++ b/gdb/Makefile.in
@@ -462,6 +462,7 @@ SELFTESTS_SRCS = \
unittests/function-view-selftests.c \
unittests/gdb_tilde_expand-selftests.c \
unittests/gmp-utils-selftests.c \
+ unittests/hash-table-selftests.c \
unittests/intrusive_list-selftests.c \
unittests/lookup_name_info-selftests.c \
unittests/memory-map-selftests.c \
diff --git a/gdb/unittests/hash-table-selftests.c b/gdb/unittests/hash-table-selftests.c
new file mode 100644
index 00000000000..e11515b7cd9
--- /dev/null
+++ b/gdb/unittests/hash-table-selftests.c
@@ -0,0 +1,128 @@
+/* Self tests for the hash table.
+
+ Copyright (C) 2023 Free Software Foundation, Inc.
+
+ This file is part of GDB.
+
+ This program 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 of the License, or
+ (at your option) any later version.
+
+ This program 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 this program. If not, see <http://www.gnu.org/licenses/>. */
+
+#include "gdbsupport/common-defs.h"
+#include "gdbsupport/selftest.h"
+#include "gdbsupport/hash-table.h"
+
+namespace selftests {
+
+/* Traits for unsigned integers. Note that the precise details here
+ are relied upon, because some of the tests are carefully crafted to
+ test details of the implementation. */
+struct unsigned_traits
+{
+ typedef unsigned value_type;
+
+ /* You can't insert 0 into this hash table. */
+ static bool is_empty (const unsigned &val)
+ { return val == 0; }
+
+ static bool equals (const unsigned &v1, const unsigned &v2)
+ { return v1 == v2; }
+
+ static size_t hash (const unsigned &val)
+ { return val; }
+};
+
+static void
+test_hash_table ()
+{
+ gdb::traited_hash_table<unsigned_traits> table;
+
+ SELF_CHECK (table.empty ());
+ SELF_CHECK (table.size () == 0);
+
+ table.insert (3);
+ SELF_CHECK (!table.empty ());
+ SELF_CHECK (table.size () == 1);
+ SELF_CHECK (table.contains (3));
+ auto iter = table.find (3);
+ SELF_CHECK (iter != table.end ());
+ SELF_CHECK (*iter == 3);
+ SELF_CHECK (++iter == table.end ());
+
+ /* Some of the following tests depend on this. */
+ SELF_CHECK (table.capacity () == 7);
+
+ table.insert (4);
+ /* This insertion has a hash collision with 3 and displaces the
+ 4. */
+ table.insert (7 + 3);
+ SELF_CHECK (table.size () == 3);
+
+ /* This test relies on Robin Hood probing and the "reverse"
+ iteration to compute the expected elements. */
+ std::vector<unsigned> expected { 4, 10, 3 };
+ std::vector<unsigned> actual (table.begin (), table.end ());
+ SELF_CHECK (expected == actual);
+
+ /* Deleting the 3 should move the 10, though we can't really test
+ for that. */
+ table.erase (3);
+ SELF_CHECK (table.size () == 2);
+ expected = std::vector<unsigned> { 4, 10 };
+ actual = std::vector<unsigned> (table.begin (), table.end ());
+ SELF_CHECK (expected == actual);
+
+ /* Deleting the 10 should stop iteration before moving the 4. We
+ can't test for that directly but we can make sure the 4 is still
+ found -- if it moved, it can't be found. */
+ table.erase (10);
+ SELF_CHECK (table.size () == 1);
+ SELF_CHECK (table.contains (4));
+ /* Nothing should have changed the size. */
+ SELF_CHECK (table.capacity () == 7);
+
+ table.erase (4);
+ SELF_CHECK (table.empty ());
+
+ /* Test that wrap-around works properly. */
+ table.insert (6);
+ table.insert (7);
+ table.insert (13);
+ expected = std::vector<unsigned> { 6, 7, 13 };
+ actual = std::vector<unsigned> (table.begin (), table.end ());
+ SELF_CHECK (expected == actual);
+
+ table.erase (6);
+ expected = std::vector<unsigned> { 13, 7 };
+ actual = std::vector<unsigned> (table.begin (), table.end ());
+ SELF_CHECK (expected == actual);
+
+ auto insert_pair = table.insert (7);
+ SELF_CHECK (*insert_pair.first == 7);
+ SELF_CHECK (!insert_pair.second);
+
+ auto insert_2 = table.insert (8);
+ SELF_CHECK (*insert_2.first == 8);
+ SELF_CHECK (insert_2.second);
+
+ table.clear ();
+ SELF_CHECK (table.empty ());
+}
+
+} /* namespace selftests */
+
+void _initialize_hash_table_selftests ();
+void
+_initialize_hash_table_selftests ()
+{
+ selftests::register_test ("hash-table", selftests::test_hash_table);
+}
diff --git a/gdbsupport/Makefile.am b/gdbsupport/Makefile.am
index 00524e9a566..8b701bf090d 100644
--- a/gdbsupport/Makefile.am
+++ b/gdbsupport/Makefile.am
@@ -61,6 +61,7 @@ libgdbsupport_a_SOURCES = \
gdb_tilde_expand.cc \
gdb_wait.cc \
gdb_vecs.cc \
+ hash-table.cc \
job-control.cc \
netstuff.cc \
new-op.cc \
diff --git a/gdbsupport/Makefile.in b/gdbsupport/Makefile.in
index 89ed11062d5..4594e8aff92 100644
--- a/gdbsupport/Makefile.in
+++ b/gdbsupport/Makefile.in
@@ -15,7 +15,7 @@
@SET_MAKE@
#
-# Copyright (C) 2020-2022 Free Software Foundation, Inc.
+# Copyright (C) 2020-2023 Free Software Foundation, Inc.
#
# This file is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
@@ -155,13 +155,14 @@ am_libgdbsupport_a_OBJECTS = agent.$(OBJEXT) btrace-common.$(OBJEXT) \
gdb-dlfcn.$(OBJEXT) gdb-hashtab.$(OBJEXT) \
gdb_obstack.$(OBJEXT) gdb_regex.$(OBJEXT) \
gdb_tilde_expand.$(OBJEXT) gdb_wait.$(OBJEXT) \
- gdb_vecs.$(OBJEXT) job-control.$(OBJEXT) netstuff.$(OBJEXT) \
- new-op.$(OBJEXT) pathstuff.$(OBJEXT) print-utils.$(OBJEXT) \
- ptid.$(OBJEXT) rsp-low.$(OBJEXT) run-time-clock.$(OBJEXT) \
- safe-strerror.$(OBJEXT) scoped_mmap.$(OBJEXT) search.$(OBJEXT) \
- signals.$(OBJEXT) signals-state-save-restore.$(OBJEXT) \
- tdesc.$(OBJEXT) thread-pool.$(OBJEXT) xml-utils.$(OBJEXT) \
- $(am__objects_1) $(am__objects_2)
+ gdb_vecs.$(OBJEXT) hash-table.$(OBJEXT) job-control.$(OBJEXT) \
+ netstuff.$(OBJEXT) new-op.$(OBJEXT) pathstuff.$(OBJEXT) \
+ print-utils.$(OBJEXT) ptid.$(OBJEXT) rsp-low.$(OBJEXT) \
+ run-time-clock.$(OBJEXT) safe-strerror.$(OBJEXT) \
+ scoped_mmap.$(OBJEXT) search.$(OBJEXT) signals.$(OBJEXT) \
+ signals-state-save-restore.$(OBJEXT) tdesc.$(OBJEXT) \
+ thread-pool.$(OBJEXT) xml-utils.$(OBJEXT) $(am__objects_1) \
+ $(am__objects_2)
libgdbsupport_a_OBJECTS = $(am_libgdbsupport_a_OBJECTS)
AM_V_P = $(am__v_P_@AM_V@)
am__v_P_ = $(am__v_P_@AM_DEFAULT_V@)
@@ -388,6 +389,7 @@ libgdbsupport_a_SOURCES = \
gdb_tilde_expand.cc \
gdb_wait.cc \
gdb_vecs.cc \
+ hash-table.cc \
job-control.cc \
netstuff.cc \
new-op.cc \
@@ -497,6 +499,7 @@ distclean-compile:
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/gdb_tilde_expand.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/gdb_vecs.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/gdb_wait.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/hash-table.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/job-control.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/netstuff.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/new-op.Po@am__quote@
diff --git a/gdbsupport/hash-table.cc b/gdbsupport/hash-table.cc
new file mode 100644
index 00000000000..d5ba29eda6b
--- /dev/null
+++ b/gdbsupport/hash-table.cc
@@ -0,0 +1,75 @@
+/* A hash table.
+
+ Copyright (C) 2023 Free Software Foundation, Inc.
+
+ This file is part of GDB.
+
+ This program 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 of the License, or
+ (at your option) any later version.
+
+ This program 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 this program. If not, see <http://www.gnu.org/licenses/>. */
+
+#include "common-defs.h"
+#include "hash-table.h"
+
+/* Table of primes, derived from libiberty. */
+
+static const size_t primes[] =
+{
+ 7,
+ 13,
+ 31,
+ 61,
+ 127,
+ 251,
+ 509,
+ 1021,
+ 2039,
+ 4093,
+ 191,
+ 6381,
+ 2749,
+ 65521,
+ 131071,
+ 262139,
+ 524287,
+ 1048573,
+ 2097143,
+ 4194301,
+ 8388593,
+ 16777213,
+ 33554393,
+ 67108859,
+ 134217689,
+ 268435399,
+ 536870909,
+ 1073741789,
+ 2147483647,
+ /* Avoid "decimal constant so large it is unsigned" for 4294967291. */
+ 0xfffffffb,
+};
+
+namespace gdb {
+namespace detail {
+
+/* The following function returns an index into the above table of the
+ nearest prime number which is at least N, and near a power of two. */
+
+size_t
+higher_prime (size_t n)
+{
+ return *std::upper_bound (std::begin (primes),
+ std::end (primes),
+ n);
+}
+
+} /* namespace detail */
+} /* namespace gdb */
diff --git a/gdbsupport/hash-table.h b/gdbsupport/hash-table.h
new file mode 100644
index 00000000000..7d3daef366f
--- /dev/null
+++ b/gdbsupport/hash-table.h
@@ -0,0 +1,551 @@
+/* A hash table.
+
+ Copyright (C) 2023 Free Software Foundation, Inc.
+
+ This file is part of GDB.
+
+ This program 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 of the License, or
+ (at your option) any later version.
+
+ This program 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 this program. If not, see <http://www.gnu.org/licenses/>. */
+
+#ifndef GDBSUPPORT_HASH_TABLE_H
+#define GDBSUPPORT_HASH_TABLE_H
+
+#include <iterator>
+#include <utility>
+
+namespace gdb {
+
+namespace detail {
+/* A helper function that finds the lowest prime greater than N. */
+extern size_t higher_prime (size_t n);
+}
+
+/* A hash table.
+
+ Currently this is an open-addressed hash table, using Robin Hood
+ probing and backward-shift deletion. These choices are described
+ in https://thenumb.at/Hashtables/
+
+ This hash table is also slightly based on libiberty's. In
+ particular the prime sizes are taken from there.
+
+ A hash table is parameterized by a Traits type. This type
+ must supply some static methods and types:
+
+ . Traits::value_type
+ The values stored in the hash table. The default constructor for a
+ value_type must construct an empty value. Objects of value_type
+ must be movable.
+
+ . Traits::is_empty (const value_type &) -> bool
+ Return true if the argument is empty.
+
+ . Traits::equals (const value_type &, const T &) -> bool
+ Return true if the two values are equal. Note that the hash table
+ will accept any type for some lookups and will attempt to pass this
+ to Traits::equals; this can have overloads or be a template if you
+ need to separate the value type from the lookup type.
+
+ . Traits::hash (const T &) -> size_t
+ Compute the hash value of the argument.
+
+ Both 'equals' and 'hash' must accept a value_type for T. If both
+ are overloaded for other types, then operations like 'find' and
+ 'erase' will work with those types as well. This enables lookups
+ using just a key type and not a full object.
+
+ Some typical implementations are provided; see the hash_table<>
+ template below.
+
+ The usual iterators are provided. Iterators should be considered
+ invalid whenever the hash table is modified.
+
+ Unlike the libiberty hash table, no controls are provided for the
+ allocation of the underlying vector or of entries. However, it's
+ perfectly ok to store unique_ptr or other smart pointers in this
+ hash table, so entries can be self-managing.
+
+ Currently this hash table is fixed at a 0.5 load factor. This
+ roughly corresponds to what libiberty does as well, though
+ libiberty will also rehash when shrinking, which this table does
+ not do.
+*/
+template<typename Traits>
+class traited_hash_table
+{
+public:
+
+ /* The type that is contained in this hash table. */
+ typedef typename Traits::value_type value_type;
+
+private:
+
+ /* The implementation of iterator types for this hash table. This
+ is a template that is instantiated for both const and non-const
+ types. */
+ template<typename V>
+ class iterator_templ
+ {
+ public:
+
+ /* Some types required for iterators. */
+ typedef V value_type;
+ typedef V *pointer;
+ typedef V &reference;
+ typedef std::ptrdiff_t difference_type;
+ typedef std::forward_iterator_tag iterator_category;
+
+ iterator_templ (const iterator_templ<V> &) = default;
+ iterator_templ (iterator_templ<V> &&) = default;
+ iterator_templ<V> &operator= (const iterator_templ<V> &) = default;
+ iterator_templ<V> &operator= (iterator_templ<V> &&) = default;
+
+ V &operator* ()
+ {
+ /* const_cast is used here to make sharing the implementation
+ between const and non-const simpler. */
+ return const_cast<V &> (m_data[m_i - 1]);
+ }
+
+ V *operator-> ()
+ {
+ /* const_cast is used here to make sharing the implementation
+ between const and non-const simpler. */
+ return const_cast<V *> (&m_data[m_i - 1]);
+ }
+
+ iterator_templ<V> &operator++ ()
+ {
+ /* Iteration is done in "reverse" order, to make it a little
+ simpler -- no checks of the underlying vector size are
+ needed, only comparisons against 0. */
+ --m_i;
+ skip_empty ();
+ return *this;
+ }
+
+ bool operator== (const iterator_templ<V> &other) const
+ {
+ return m_i == other.m_i && &m_data == &other.m_data;
+ }
+
+ bool operator!= (const iterator_templ<V> &other) const
+ { return !(*this == other); }
+
+ private:
+
+ /* Only allow private construction. */
+ friend class traited_hash_table<Traits>;
+
+ /* Create an iterator pointing at a particular slot. The caller
+ must assure that the slot is not empty; it is also ok to pass 0
+ as the index. In the non-zero case, NDX must be one plus the
+ desired index. */
+ iterator_templ (size_t ndx,
+ const std::vector<typename Traits::value_type> &data)
+ : m_i (ndx),
+ m_data (data)
+ { }
+
+ /* Create a 'begin' iterator. */
+ explicit iterator_templ (const std::vector<typename Traits::value_type> &data)
+ : m_i (data.size ()),
+ m_data (data)
+ {
+ skip_empty ();
+ }
+
+ /* Helper method to ensure that the iterator is not pointing at an
+ empty slot. */
+ void skip_empty ()
+ {
+ while (m_i > 0 && Traits::is_empty (m_data[m_i - 1]))
+ --m_i;
+ }
+
+ /* The index into the hash table, plus one. This is done so that
+ 0 can be the "end" sentinel. */
+ size_t m_i;
+ /* The container data. */
+ const std::vector<typename Traits::value_type> &m_data;
+ };
+
+ /* Implementation of find. This is written as a template so that
+ any type that is supported by the traits can be used to look up
+ an entry, and also to support both const and non-const
+ lookups. */
+ template<typename T, typename V>
+ iterator_templ<V> find_impl (const T &val, size_t hash) const
+ {
+ /* Maybe there are no entries. Note that this also avoids mod by
+ zero when DSIZE==0. */
+ if (m_entries == 0)
+ return iterator_templ<V> (0, m_data);
+
+ size_t dsize = m_data.size ();
+ size_t ndx = hash % dsize;
+
+ while (true)
+ {
+ if (Traits::is_empty (m_data[ndx]))
+ return iterator_templ<V> (0, m_data);
+ if (Traits::equals (m_data[ndx], val))
+ return iterator_templ<V> (ndx + 1, m_data);
+ ++ndx;
+ if (ndx == dsize)
+ ndx = 0;
+ }
+ }
+
+public:
+
+ traited_hash_table () = default;
+
+ /* Create a new hash table that will allow for SIZE elements to be
+ inserted without resizing. */
+ explicit traited_hash_table (size_t size)
+ : m_data (detail::higher_prime (2 * size + 1))
+ { }
+
+ /* Copying and moving. */
+ explicit traited_hash_table (const traited_hash_table<Traits> &) = default;
+ explicit traited_hash_table (traited_hash_table<Traits> &&) = default;
+ traited_hash_table<Traits> &operator= (const traited_hash_table<Traits> &)
+ = default;
+ traited_hash_table<Traits> &operator= (traited_hash_table<Traits> &&)
+ = default;
+
+ /* Iterator types. */
+ typedef iterator_templ<value_type> iterator;
+ typedef iterator_templ<const value_type> const_iterator;
+
+ /* Return a starting iterator. */
+ iterator begin ()
+ { return iterator (m_data); }
+ const_iterator begin () const
+ { return const_iterator (m_data); }
+ const_iterator cbegin () const
+ { return const_iterator (m_data); }
+
+ /* Return an end iterator. */
+ iterator end ()
+ { return iterator (0, m_data); }
+ const_iterator end () const
+ { return const_iterator (0, m_data); }
+ const_iterator cend () const
+ { return const_iterator (0, m_data); }
+
+ /* Erase an element given a lookup key and a hash. This is a
+ template so that any type supported by the traits can be
+ used. */
+ template<typename T>
+ void erase (const T &val, size_t hash)
+ {
+ /* Maybe there are no entries. Note that this also avoids mod by
+ zero when DSIZE==0. */
+ if (m_entries == 0)
+ return;
+
+ size_t dsize = m_data.size ();
+ size_t ndx = hash % dsize;
+ /* This assumes there's at least one empty element in the
+ table. */
+ while (true)
+ {
+ if (Traits::is_empty (m_data[ndx]))
+ {
+ /* Not found. */
+ break;
+ }
+ if (Traits::equals (m_data[ndx], val))
+ {
+ /* Backward-shift deletion. The idea here is that, due to
+ Robin Hood probing, we do not need tombstones but
+ instead can simply shift entries down -- if we find an
+ element that is already at its desired location,
+ iteration stops. */
+ --m_entries;
+ while (true)
+ {
+ size_t prev_ndx = ndx++;
+ if (ndx == dsize)
+ ndx = 0;
+ if (Traits::is_empty (m_data[ndx]))
+ {
+ /* Nothing to move. */
+ m_data[prev_ndx] = {};
+ return;
+ }
+ size_t nhash = Traits::hash (m_data[ndx]);
+ if (nhash % dsize == ndx)
+ {
+ /* This element is at its best spot, so no need to
+ keep moving. */
+ m_data[prev_ndx] = {};
+ return;
+ }
+ m_data[prev_ndx] = std::move (m_data[ndx]);
+ }
+ }
+ ++ndx;
+ if (ndx == dsize)
+ ndx = 0;
+ }
+ }
+
+ /* Erase an entry. Any type supported by the trait is accepted
+ here. */
+ template<typename T>
+ void erase (const T &val)
+ {
+ erase (val, Traits::hash (val));
+ }
+
+ /* Insert an element into the hash table. VAL is the new element;
+ it is copied. Returns a pair whose second element is a boolean.
+ This boolean is true if a new element was inserted, and false
+ otherwise. The first element of the pair is an iterator to
+ either the new element, or the existing element that prevented
+ insertion. */
+ std::pair<iterator, bool> insert (const value_type &val)
+ {
+ value_type copy = val;
+ return insert (std::move (copy));
+ }
+
+ /* Insert an element into the hash table. VAL is the new element;
+ it is moved. Returns a pair whose second element is a boolean.
+ This boolean is true if a new element was inserted, and false
+ otherwise. The first element of the pair is an iterator to
+ either the new element, or the existing element that prevented
+ insertion. */
+ std::pair<iterator, bool> insert (value_type &&val)
+ {
+ /* Load factor 0.5. The +1 here is to handle the case where the
+ vector has size 0. */
+ if (m_entries * 2 + 1 > m_data.size ())
+ resize ();
+
+ size_t hash = Traits::hash (val);
+ size_t dsize = m_data.size ();
+ size_t cost = 0;
+ size_t ndx = hash % dsize;
+
+ ++m_entries;
+ while (true)
+ {
+ if (Traits::is_empty (m_data[ndx]))
+ {
+ m_data[ndx] = std::move (val);
+ return { iterator (ndx + 1, m_data), true };
+ }
+ if (Traits::equals (m_data[ndx], val))
+ return { iterator (ndx + 1, m_data), false };
+
+ size_t nhash = Traits::hash (m_data[ndx]);
+ size_t nndx = nhash % dsize;
+
+ /* The cost is how far the entry is from its desired spot.
+ However, there is wraparound to deal with. */
+ size_t ncost;
+ if (ndx >= nndx)
+ {
+ /* --- 0 ... NDX ... NNDX ... END --- */
+ ncost = ndx - nndx;
+ }
+ else
+ {
+ /* --- 0 ... NNDX ... NDX ... END --- */
+ ncost = nndx + dsize - ndx;
+ }
+
+ /* Steal from the rich. */
+ if (cost > ncost)
+ {
+ std::swap (val, m_data[ndx]);
+ cost = ncost;
+ }
+
+ ++ndx;
+ if (ndx == dsize)
+ ndx = 0;
+ ++cost;
+ }
+ }
+
+ /* Find an element. Returns an iterator to the element, or an 'end'
+ iterator if the element is not found. */
+ template<typename T>
+ iterator find (const T &val, size_t hash)
+ { return find_impl<T, value_type> (val, hash); }
+
+ template<typename T>
+ iterator find (const T &val)
+ { return find_impl<T, value_type> (val, Traits::hash (val)); }
+
+ template<typename T>
+ const_iterator find (const T &val, size_t hash) const
+ { return find_impl<T, const value_type> (val, hash); }
+
+ template<typename T>
+ const_iterator find (const T &val) const
+ { return find_impl<T, const value_type> (val, Traits::hash (val)); }
+
+ /* Return true if the hash table contains VAL, or false if not. */
+ template<typename T>
+ bool contains (const T &val) const
+ { return find (val) != end (); }
+
+ /* Empty the hash table. */
+ void clear ()
+ {
+ m_entries = 0;
+ m_data.clear ();
+ }
+
+ /* Return true if the hash table is empty, false if it has any
+ entries. */
+ bool empty () const
+ { return m_entries == 0; }
+
+ /* Return the number of entries currently stored in this hash
+ table. */
+ size_t size () const
+ { return m_entries; }
+
+ /* The size of the vector that underlies this hash table. This is
+ not generally useful, but is used by the self tests. Note that
+ this is not the same as the number of elements that can be
+ inserted without resizing. */
+ size_t capacity () const
+ { return m_data.size (); }
+
+private:
+
+ /* Helper method to resize the hash table. */
+ void resize ()
+ {
+ std::vector<value_type> saved
+ (detail::higher_prime (m_data.size ()));
+ std::swap (saved, m_data);
+ m_entries = 0;
+
+ for (value_type &elt : saved)
+ {
+ if (!Traits::is_empty (elt))
+ insert (std::move (elt));
+ }
+ }
+
+ /* Number of non-empty entries in the table. */
+ size_t m_entries = 0;
+ /* The underlying data. */
+ std::vector<value_type> m_data;
+};
+
+
+/* A typical traits implementation for a type. This uses the standard
+ hash function and the standard equality function. */
+template<typename T>
+struct typical_hash_traits
+{
+ using value_type = T;
+
+ template<typename U>
+ static bool equals (const value_type &lhs, const U &rhs)
+ { return lhs == rhs; }
+
+ static bool is_empty (const value_type &val)
+ { return ! bool (val); }
+
+ static size_t hash (const value_type &val)
+ { return std::hash<value_type> () (val); }
+};
+
+/* A hash set that stores elements of a type T. */
+template<typename T>
+using hash_set = traited_hash_table<typical_hash_traits<T>>;
+
+/* A trait to use for compatibility with the libiberty hash table. It
+ is parameterized by the hash and equality functions. This can only
+ be used for pointer types. */
+template<htab_hash Hash, htab_eq Equal, typename T>
+struct libiberty_traits
+{
+ typedef T value_type;
+
+ static bool equals (const value_type &lhs, const value_type &rhs)
+ { return Equal (lhs, rhs); }
+
+ static bool is_empty (const value_type &val)
+ { return val == nullptr; }
+
+ static size_t hash (const value_type &val)
+ { return Hash (val); }
+};
+
+/* Traits for use in a hash map. These use ordinary hash table traits
+ for the key; the key type is taken from the traits. The table
+ itself stores key-value pairs. */
+template<typename Traits, typename Value>
+struct hash_map_traits
+{
+ /* A convenience typedef for the key type. */
+ typedef typename Traits::value_type key_type;
+
+ typedef std::pair<key_type, Value> value_type;
+
+ static bool equals (const value_type &lhs, const value_type &rhs)
+ { return Traits::equals (lhs.first, rhs.first); }
+
+ static bool equals (const value_type &lhs, const key_type &rhs)
+ { return Traits::equals (lhs.first, rhs); }
+
+ static bool is_empty (const value_type &val)
+ { return Traits::is_empty (val.first); }
+
+ static size_t hash (const key_type &key)
+ { return Traits::hash (key); }
+
+ static size_t hash (const value_type &val)
+ { return Traits::hash (val.first); }
+};
+
+/* A hash map. This is parameterized by a trait type that describes
+ the keys, and a value type. The map itself is just a hash table
+ whose entries are std::pair<key, value>. */
+template<typename Traits, typename Value>
+class traited_hash_map
+ : public traited_hash_table<hash_map_traits<Traits, Value>>
+{
+ using trait_type = hash_map_traits<Traits, Value>;
+ using super_type = traited_hash_table<trait_type>;
+ typedef typename trait_type::key_type key_type;
+
+public:
+
+ /* Like traited_hash_table::insert, but allows the key and value to
+ be passed as-is. */
+ std::pair<typename super_type::iterator, bool> insert (const key_type &key,
+ const Value &value)
+ { return super_type::insert (std::pair<key_type, Value> (key, value)); }
+};
+
+/* An easy-to-instantiate hash map that uses the "typical" hash traits
+ for the key. */
+template<typename Key, typename Value>
+using hash_map = traited_hash_map<typical_hash_traits<Key>, Value>;
+
+} /* namespace gdb */
+
+#endif /* GDBSUPPORT_HASH_TABLE_H */
--
2.39.2
^ permalink raw reply [flat|nested] 29+ messages in thread* Re: [PATCH 01/19] Add a hash table to gdbsupport
2023-04-07 15:25 ` [PATCH 01/19] Add a " Tom Tromey
@ 2023-04-07 15:41 ` Tom Tromey
0 siblings, 0 replies; 29+ messages in thread
From: Tom Tromey @ 2023-04-07 15:41 UTC (permalink / raw)
To: Tom Tromey; +Cc: gdb-patches
>>>>> "Tom" == Tom Tromey <tom@tromey.com> writes:
Just after I sent this I noticed...
Tom> + /* Erase an element given a lookup key and a hash. This is a
Tom> + template so that any type supported by the traits can be
Tom> + used. */
Tom> + template<typename T>
Tom> + void erase (const T &val, size_t hash)
Tom> + {
[...]
Tom> + if (Traits::equals (m_data[ndx], val))
Tom> + {
Tom> + /* Backward-shift deletion. The idea here is that, due to
[...]
Tom> + }
This block should have a 'break' at the end. This doesn't affect
correctness, but it's more efficient and also less confusing to exit the
loop after deleting an element.
I'm going to add this locally.
Tom
^ permalink raw reply [flat|nested] 29+ messages in thread
* [PATCH 02/19] Convert compile-c-symbols.c to new hash table
2023-04-07 15:25 [PATCH 00/19] Add hash table to gdbsupport Tom Tromey
2023-04-07 15:25 ` [PATCH 01/19] Add a " Tom Tromey
@ 2023-04-07 15:25 ` Tom Tromey
2023-04-07 15:25 ` [PATCH 03/19] Convert filename-seen-cache.h " Tom Tromey
` (18 subsequent siblings)
20 siblings, 0 replies; 29+ messages in thread
From: Tom Tromey @ 2023-04-07 15:25 UTC (permalink / raw)
To: gdb-patches
This converts compile-c-symbols.c to use the new hash table.
---
gdb/compile/compile-c-symbols.c | 54 +++++++++++++++--------------------------
1 file changed, 19 insertions(+), 35 deletions(-)
diff --git a/gdb/compile/compile-c-symbols.c b/gdb/compile/compile-c-symbols.c
index e21689dc25b..e76726e058c 100644
--- a/gdb/compile/compile-c-symbols.c
+++ b/gdb/compile/compile-c-symbols.c
@@ -30,6 +30,7 @@
#include "exceptions.h"
#include "gdbtypes.h"
#include "dwarf2/loc.h"
+#include "gdbsupport/hash-table.h"
\f
@@ -444,43 +445,27 @@ gcc_symbol_address (void *datum, struct gcc_c_context *gcc_context,
\f
-/* A hash function for symbol names. */
-
-static hashval_t
-hash_symname (const void *a)
-{
- const struct symbol *sym = (const struct symbol *) a;
-
- return htab_hash_string (sym->natural_name ());
-}
-
-/* A comparison function for hash tables that just looks at symbol
- names. */
-
-static int
-eq_symname (const void *a, const void *b)
+/* Traits for hashing symbols. */
+struct symbol_traits
{
- const struct symbol *syma = (const struct symbol *) a;
- const struct symbol *symb = (const struct symbol *) b;
+ typedef const struct symbol *value_type;
- return strcmp (syma->natural_name (), symb->natural_name ()) == 0;
-}
+ static bool is_empty (const struct symbol *sym)
+ { return sym == nullptr; }
-/* If a symbol with the same name as SYM is already in HASHTAB, return
- 1. Otherwise, add SYM to HASHTAB and return 0. */
+ static bool equals (const struct symbol *syma, const struct symbol *symb)
+ {
+ return strcmp (syma->natural_name (), symb->natural_name ()) == 0;
+ }
-static int
-symbol_seen (htab_t hashtab, struct symbol *sym)
-{
- void **slot;
+ static hashval_t hash (const struct symbol *sym)
+ {
+ return htab_hash_string (sym->natural_name ());
+ }
+};
- slot = htab_find_slot (hashtab, sym, INSERT);
- if (*slot != NULL)
- return 1;
-
- *slot = sym;
- return 0;
-}
+/* Type of a set that holds symbols. */
+typedef gdb::traited_hash_table<symbol_traits> symbol_set;
/* Generate C code to compute the length of a VLA. */
@@ -628,8 +613,7 @@ generate_c_for_variable_locations (compile_instance *compiler,
/* Ensure that a given name is only entered once. This reflects the
reality of shadowing. */
- htab_up symhash (htab_create_alloc (1, hash_symname, eq_symname, NULL,
- xcalloc, xfree));
+ symbol_set symset;
while (1)
{
@@ -637,7 +621,7 @@ generate_c_for_variable_locations (compile_instance *compiler,
compute the location of each local variable. */
for (struct symbol *sym : block_iterator_range (block))
{
- if (!symbol_seen (symhash.get (), sym))
+ if (symset.insert (sym).second)
generate_c_for_for_one_variable (compiler, stream, gdbarch,
registers_used, pc, sym);
}
--
2.39.2
^ permalink raw reply [flat|nested] 29+ messages in thread* [PATCH 03/19] Convert filename-seen-cache.h to new hash table
2023-04-07 15:25 [PATCH 00/19] Add hash table to gdbsupport Tom Tromey
2023-04-07 15:25 ` [PATCH 01/19] Add a " Tom Tromey
2023-04-07 15:25 ` [PATCH 02/19] Convert compile-c-symbols.c to new hash table Tom Tromey
@ 2023-04-07 15:25 ` Tom Tromey
2023-04-07 15:25 ` [PATCH 04/19] Convert linespec.c " Tom Tromey
` (17 subsequent siblings)
20 siblings, 0 replies; 29+ messages in thread
From: Tom Tromey @ 2023-04-07 15:25 UTC (permalink / raw)
To: gdb-patches
This converts filename-seen-cache.h to use the new hash table.
filename-seen-cache.c is removed. This patch is an example of using
the libiberty shim trait.
---
gdb/Makefile.in | 1 -
gdb/filename-seen-cache.c | 59 -----------------------------------------------
gdb/filename-seen-cache.h | 35 ++++++++++------------------
3 files changed, 12 insertions(+), 83 deletions(-)
diff --git a/gdb/Makefile.in b/gdb/Makefile.in
index 08c809310ff..bcab4cc29de 100644
--- a/gdb/Makefile.in
+++ b/gdb/Makefile.in
@@ -1093,7 +1093,6 @@ COMMON_SFILES = \
f-lang.c \
f-typeprint.c \
f-valprint.c \
- filename-seen-cache.c \
filesystem.c \
findcmd.c \
findvar.c \
diff --git a/gdb/filename-seen-cache.c b/gdb/filename-seen-cache.c
deleted file mode 100644
index be8fe1c18a0..00000000000
--- a/gdb/filename-seen-cache.c
+++ /dev/null
@@ -1,59 +0,0 @@
-/* Filename-seen cache for the GNU debugger, GDB.
-
- Copyright (C) 1986-2023 Free Software Foundation, Inc.
-
- This file is part of GDB.
-
- This program 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 of the License, or
- (at your option) any later version.
-
- This program 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 this program. If not, see <http://www.gnu.org/licenses/>. */
-
-#include "defs.h"
-#include "filename-seen-cache.h"
-#include "filenames.h"
-
- /* Initial size of the table. It automagically grows from here. */
-#define INITIAL_FILENAME_SEEN_CACHE_SIZE 100
-
-/* filename_seen_cache constructor. */
-
-filename_seen_cache::filename_seen_cache ()
- : m_tab (htab_create_alloc (INITIAL_FILENAME_SEEN_CACHE_SIZE,
- filename_hash, filename_eq,
- NULL, xcalloc, xfree))
-{
-}
-
-/* See filename-seen-cache.h. */
-
-void
-filename_seen_cache::clear ()
-{
- htab_empty (m_tab.get ());
-}
-
-/* See filename-seen-cache.h. */
-
-bool
-filename_seen_cache::seen (const char *file)
-{
- void **slot;
-
- /* Is FILE in tab? */
- slot = htab_find_slot (m_tab.get (), file, INSERT);
- if (*slot != NULL)
- return true;
-
- /* No; add it to tab. */
- *slot = (char *) file;
- return false;
-}
diff --git a/gdb/filename-seen-cache.h b/gdb/filename-seen-cache.h
index 7ae878a5616..322cea8f80d 100644
--- a/gdb/filename-seen-cache.h
+++ b/gdb/filename-seen-cache.h
@@ -20,47 +20,36 @@
#ifndef FILENAME_SEEN_CACHE_H
#define FILENAME_SEEN_CACHE_H
-#include "defs.h"
-#include "gdbsupport/function-view.h"
-#include "gdbsupport/gdb-hashtab.h"
+#include "gdbsupport/hash-table.h"
+#include "filenames.h"
/* Cache to watch for file names already seen. */
class filename_seen_cache
{
public:
- filename_seen_cache ();
+ filename_seen_cache () = default;
DISABLE_COPY_AND_ASSIGN (filename_seen_cache);
- /* Empty the cache, but do not delete it. */
- void clear ();
+ /* Empty the cache. */
+ void clear ()
+ { m_tab.clear (); }
/* If FILE is not already in the table of files in CACHE, add it and
return false; otherwise return true.
NOTE: We don't manage space for FILE, we assume FILE lives as
long as the caller needs. */
- bool seen (const char *file);
-
- /* Traverse all cache entries, calling CALLBACK on each. The
- filename is passed as argument to CALLBACK. */
- void traverse (gdb::function_view<void (const char *filename)> callback)
- {
- auto erased_cb = [] (void **slot, void *info) -> int
- {
- auto filename = (const char *) *slot;
- auto restored_cb = (decltype (callback) *) info;
- (*restored_cb) (filename);
- return 1;
- };
-
- htab_traverse_noresize (m_tab.get (), erased_cb, &callback);
- }
+ bool seen (const char *file)
+ { return !m_tab.insert (file).second; }
private:
+ using traits = gdb::libiberty_traits<filename_hash, filename_eq,
+ const char *>;
+
/* Table of files seen so far. */
- htab_up m_tab;
+ gdb::traited_hash_table<traits> m_tab;
};
#endif /* FILENAME_SEEN_CACHE_H */
--
2.39.2
^ permalink raw reply [flat|nested] 29+ messages in thread* [PATCH 04/19] Convert linespec.c to new hash table
2023-04-07 15:25 [PATCH 00/19] Add hash table to gdbsupport Tom Tromey
` (2 preceding siblings ...)
2023-04-07 15:25 ` [PATCH 03/19] Convert filename-seen-cache.h " Tom Tromey
@ 2023-04-07 15:25 ` Tom Tromey
2023-04-07 15:25 ` [PATCH 05/19] Convert target-descriptions.c " Tom Tromey
` (16 subsequent siblings)
20 siblings, 0 replies; 29+ messages in thread
From: Tom Tromey @ 2023-04-07 15:25 UTC (permalink / raw)
To: gdb-patches
This converts linespec.c to use the new hash table.
Note that more simplification could perhaps be done. Currently, the
collectors in this code insert an element into a set and then, if the
element has not been seen before, append it to a vector. If we know
the order does not matter, or if the results can be sorted later, we
could dispense with the vector. This would simplify the code some
more. (This technique is used in the vtable patch, later in this
series.)
---
gdb/linespec.c | 53 +++++++++++++++++------------------------------------
1 file changed, 17 insertions(+), 36 deletions(-)
diff --git a/gdb/linespec.c b/gdb/linespec.c
index 7d969f37fbf..5eb8552d37a 100644
--- a/gdb/linespec.c
+++ b/gdb/linespec.c
@@ -46,6 +46,7 @@
#include "location.h"
#include "gdbsupport/function-view.h"
#include "gdbsupport/def-vector.h"
+#include "gdbsupport/hash-table.h"
#include <algorithm>
#include "inferior.h"
@@ -3371,12 +3372,9 @@ namespace {
class decode_compound_collector
{
public:
- decode_compound_collector ()
- : m_unique_syms (htab_create_alloc (1, htab_hash_pointer,
- htab_eq_pointer, NULL,
- xcalloc, xfree))
- {
- }
+ decode_compound_collector () = default;
+
+ DISABLE_COPY_AND_ASSIGN (decode_compound_collector);
/* Return all symbols collected. */
std::vector<block_symbol> release_symbols ()
@@ -3390,7 +3388,7 @@ class decode_compound_collector
private:
/* A hash table of all symbols we found. We use this to avoid
adding any symbol more than once. */
- htab_up m_unique_syms;
+ gdb::hash_set<const struct symbol *> m_unique_syms;
/* The result vector. */
std::vector<block_symbol> m_symbols;
@@ -3399,7 +3397,6 @@ class decode_compound_collector
bool
decode_compound_collector::operator () (block_symbol *bsym)
{
- void **slot;
struct type *t;
struct symbol *sym = bsym->symbol;
@@ -3413,12 +3410,8 @@ decode_compound_collector::operator () (block_symbol *bsym)
&& t->code () != TYPE_CODE_NAMESPACE)
return true; /* Continue iterating. */
- slot = htab_find_slot (m_unique_syms.get (), sym, INSERT);
- if (!*slot)
- {
- *slot = sym;
- m_symbols.push_back (*bsym);
- }
+ if (m_unique_syms.insert (sym).second)
+ m_symbols.push_back (*bsym);
return true; /* Continue iterating. */
}
@@ -3646,14 +3639,17 @@ namespace {
class symtab_collector
{
public:
- symtab_collector ()
- : m_symtab_table (htab_create (1, htab_hash_pointer, htab_eq_pointer,
- NULL))
- {
- }
+ symtab_collector () = default;
+
+ DISABLE_COPY_AND_ASSIGN (symtab_collector);
/* Callable as a symbol_found_callback_ftype callback. */
- bool operator () (symtab *sym);
+ bool operator () (struct symtab *symtab)
+ {
+ if (m_symtab_table.insert (symtab).second)
+ m_symtabs.push_back (symtab);
+ return false;
+ }
/* Return an rvalue reference to the collected symtabs. */
std::vector<symtab *> &&release_symtabs ()
@@ -3666,24 +3662,9 @@ class symtab_collector
std::vector<symtab *> m_symtabs;
/* This is used to ensure the symtabs are unique. */
- htab_up m_symtab_table;
+ gdb::hash_set<const struct symtab *> m_symtab_table;
};
-bool
-symtab_collector::operator () (struct symtab *symtab)
-{
- void **slot;
-
- slot = htab_find_slot (m_symtab_table.get (), symtab, INSERT);
- if (!*slot)
- {
- *slot = symtab;
- m_symtabs.push_back (symtab);
- }
-
- return false;
-}
-
} // namespace
/* Given a file name, return a list of all matching symtabs. If
--
2.39.2
^ permalink raw reply [flat|nested] 29+ messages in thread* [PATCH 05/19] Convert target-descriptions.c to new hash table
2023-04-07 15:25 [PATCH 00/19] Add hash table to gdbsupport Tom Tromey
` (3 preceding siblings ...)
2023-04-07 15:25 ` [PATCH 04/19] Convert linespec.c " Tom Tromey
@ 2023-04-07 15:25 ` Tom Tromey
2023-04-07 15:25 ` [PATCH 06/19] Convert dwarf2/macro.c " Tom Tromey
` (15 subsequent siblings)
20 siblings, 0 replies; 29+ messages in thread
From: Tom Tromey @ 2023-04-07 15:25 UTC (permalink / raw)
To: gdb-patches
This converts target-descriptions.c to use the new hash table. This
is an example of using the standard traits -- i.e., std::hash and
operator==.
---
gdb/target-descriptions.c | 17 +++++++----------
1 file changed, 7 insertions(+), 10 deletions(-)
diff --git a/gdb/target-descriptions.c b/gdb/target-descriptions.c
index 7ae9058b2f2..a06c7d885e2 100644
--- a/gdb/target-descriptions.c
+++ b/gdb/target-descriptions.c
@@ -31,7 +31,7 @@
#include "osabi.h"
#include "gdbsupport/gdb_obstack.h"
-#include "hashtab.h"
+#include "gdbsupport/hash-table.h"
#include "inferior.h"
#include <algorithm>
#include "completer.h"
@@ -1047,14 +1047,11 @@ tdesc_use_registers (struct gdbarch *gdbarch,
/* Build up a set of all registers, so that we can assign register
numbers where needed. The hash table expands as necessary, so
the initial size is arbitrary. */
- htab_up reg_hash (htab_create (37, htab_hash_pointer, htab_eq_pointer,
- NULL));
+ gdb::hash_set<tdesc_reg *> reg_hash;
for (const tdesc_feature_up &feature : target_desc->features)
for (const tdesc_reg_up ® : feature->registers)
{
- void **slot = htab_find_slot (reg_hash.get (), reg.get (), INSERT);
-
- *slot = reg.get ();
+ reg_hash.insert (reg.get ());
/* Add reggroup if its new. */
if (!reg->group.empty ())
if (reggroup_find (gdbarch, reg->group.c_str ()) == NULL)
@@ -1067,7 +1064,7 @@ tdesc_use_registers (struct gdbarch *gdbarch,
architecture. */
for (const tdesc_arch_reg &arch_reg : data->arch_regs)
if (arch_reg.reg != NULL)
- htab_remove_elt (reg_hash.get (), arch_reg.reg);
+ reg_hash.erase (arch_reg.reg);
/* Assign numbers to the remaining registers and add them to the
list of registers. The new numbers are always above gdbarch_num_regs.
@@ -1085,7 +1082,7 @@ tdesc_use_registers (struct gdbarch *gdbarch,
{
for (const tdesc_feature_up &feature : target_desc->features)
for (const tdesc_reg_up ® : feature->registers)
- if (htab_find (reg_hash.get (), reg.get ()) != NULL)
+ if (reg_hash.contains (reg.get ()))
{
int regno = unk_reg_cb (gdbarch, feature.get (),
reg->name.c_str (), num_regs);
@@ -1096,7 +1093,7 @@ tdesc_use_registers (struct gdbarch *gdbarch,
data->arch_regs.emplace_back (nullptr, nullptr);
data->arch_regs[regno] = tdesc_arch_reg (reg.get (), NULL);
num_regs = regno + 1;
- htab_remove_elt (reg_hash.get (), reg.get ());
+ reg_hash.erase (reg.get ());
}
}
}
@@ -1108,7 +1105,7 @@ tdesc_use_registers (struct gdbarch *gdbarch,
unnumbered registers. */
for (const tdesc_feature_up &feature : target_desc->features)
for (const tdesc_reg_up ® : feature->registers)
- if (htab_find (reg_hash.get (), reg.get ()) != NULL)
+ if (reg_hash.contains (reg.get ()))
{
data->arch_regs.emplace_back (reg.get (), nullptr);
num_regs++;
--
2.39.2
^ permalink raw reply [flat|nested] 29+ messages in thread* [PATCH 06/19] Convert dwarf2/macro.c to new hash table
2023-04-07 15:25 [PATCH 00/19] Add hash table to gdbsupport Tom Tromey
` (4 preceding siblings ...)
2023-04-07 15:25 ` [PATCH 05/19] Convert target-descriptions.c " Tom Tromey
@ 2023-04-07 15:25 ` Tom Tromey
2023-04-07 15:25 ` [PATCH 07/19] Convert breakpoint.c " Tom Tromey
` (14 subsequent siblings)
20 siblings, 0 replies; 29+ messages in thread
From: Tom Tromey @ 2023-04-07 15:25 UTC (permalink / raw)
To: gdb-patches
This converts dwarf2/macro.c to use the new hash table.
---
gdb/dwarf2/macro.c | 21 +++++++--------------
1 file changed, 7 insertions(+), 14 deletions(-)
diff --git a/gdb/dwarf2/macro.c b/gdb/dwarf2/macro.c
index 78cce2d69eb..7a3aa5ffee3 100644
--- a/gdb/dwarf2/macro.c
+++ b/gdb/dwarf2/macro.c
@@ -445,7 +445,8 @@ dwarf_decode_macro_bytes (dwarf2_per_objfile *per_objfile,
struct dwarf2_section_info *str_section,
struct dwarf2_section_info *str_offsets_section,
gdb::optional<ULONGEST> str_offsets_base,
- htab_t include_hash, struct dwarf2_cu *cu)
+ gdb::hash_set<const gdb_byte *> &include_hash,
+ struct dwarf2_cu *cu)
{
struct objfile *objfile = per_objfile->objfile;
enum dwarf_macro_record_type macinfo_type;
@@ -720,7 +721,6 @@ dwarf_decode_macro_bytes (dwarf2_per_objfile *per_objfile,
case DW_MACRO_import_sup:
{
LONGEST offset;
- void **slot;
bfd *include_bfd = abfd;
const struct dwarf2_section_info *include_section = section;
const gdb_byte *include_mac_end = mac_end;
@@ -744,9 +744,8 @@ dwarf_decode_macro_bytes (dwarf2_per_objfile *per_objfile,
}
new_mac_ptr = include_section->buffer + offset;
- slot = htab_find_slot (include_hash, new_mac_ptr, INSERT);
- if (*slot != NULL)
+ if (!include_hash.insert (new_mac_ptr).second)
{
/* This has actually happened; see
http://sourceware.org/bugzilla/show_bug.cgi?id=13568. */
@@ -755,8 +754,6 @@ dwarf_decode_macro_bytes (dwarf2_per_objfile *per_objfile,
}
else
{
- *slot = (void *) new_mac_ptr;
-
dwarf_decode_macro_bytes (per_objfile, builder, include_bfd,
new_mac_ptr, include_mac_end,
current_file, lh, section,
@@ -764,7 +761,7 @@ dwarf_decode_macro_bytes (dwarf2_per_objfile *per_objfile,
str_section, str_offsets_section,
str_offsets_base, include_hash, cu);
- htab_remove_elt (include_hash, (void *) new_mac_ptr);
+ include_hash.erase (new_mac_ptr);
}
}
break;
@@ -813,7 +810,6 @@ dwarf_decode_macros (dwarf2_per_objfile *per_objfile,
struct macro_source_file *current_file = 0;
enum dwarf_macro_record_type macinfo_type;
const gdb_byte *opcode_definitions[256];
- void **slot;
abfd = section->get_bfd_owner ();
@@ -958,14 +954,11 @@ dwarf_decode_macros (dwarf2_per_objfile *per_objfile,
command-line macro definitions/undefinitions. This flag is unset when we
reach the first DW_MACINFO_start_file entry. */
- htab_up include_hash (htab_create_alloc (1, htab_hash_pointer,
- htab_eq_pointer,
- NULL, xcalloc, xfree));
+ gdb::hash_set<const gdb_byte *> include_hash;
mac_ptr = section->buffer + offset;
- slot = htab_find_slot (include_hash.get (), mac_ptr, INSERT);
- *slot = (void *) mac_ptr;
+ include_hash.insert (mac_ptr);
dwarf_decode_macro_bytes (per_objfile, builder, abfd, mac_ptr, mac_end,
current_file, lh, section, section_is_gnu, 0,
offset_size, str_section, str_offsets_section,
- str_offsets_base, include_hash.get (), cu);
+ str_offsets_base, include_hash, cu);
}
--
2.39.2
^ permalink raw reply [flat|nested] 29+ messages in thread* [PATCH 07/19] Convert breakpoint.c to new hash table
2023-04-07 15:25 [PATCH 00/19] Add hash table to gdbsupport Tom Tromey
` (5 preceding siblings ...)
2023-04-07 15:25 ` [PATCH 06/19] Convert dwarf2/macro.c " Tom Tromey
@ 2023-04-07 15:25 ` Tom Tromey
2023-04-07 15:25 ` [PATCH 08/19] Convert py-framefilter.c " Tom Tromey
` (13 subsequent siblings)
20 siblings, 0 replies; 29+ messages in thread
From: Tom Tromey @ 2023-04-07 15:25 UTC (permalink / raw)
To: gdb-patches
This converts breakpoint.c to use the new hash table.
---
gdb/breakpoint.c | 16 ++++++----------
1 file changed, 6 insertions(+), 10 deletions(-)
diff --git a/gdb/breakpoint.c b/gdb/breakpoint.c
index ebe97940f54..3e380a1fd0b 100644
--- a/gdb/breakpoint.c
+++ b/gdb/breakpoint.c
@@ -20,7 +20,6 @@
#include "defs.h"
#include "arch-utils.h"
#include <ctype.h>
-#include "hashtab.h"
#include "symtab.h"
#include "frame.h"
#include "breakpoint.h"
@@ -81,6 +80,7 @@
#include "progspace-and-thread.h"
#include "gdbsupport/array-view.h"
#include "gdbsupport/gdb_optional.h"
+#include "gdbsupport/hash-table.h"
/* Prototypes for local functions. */
@@ -12489,25 +12489,21 @@ static bool
ambiguous_names_p (struct bp_location *loc)
{
struct bp_location *l;
- htab_up htab (htab_create_alloc (13, htab_hash_string, htab_eq_string, NULL,
- xcalloc, xfree));
+
+ using traits = gdb::libiberty_traits<htab_hash_string, htab_eq_string,
+ const char *>;
+ gdb::traited_hash_table<traits> htab;
for (l = loc; l != NULL; l = l->next)
{
- const char **slot;
const char *name = l->function_name.get ();
/* Allow for some names to be NULL, ignore them. */
if (name == NULL)
continue;
- slot = (const char **) htab_find_slot (htab.get (), (const void *) name,
- INSERT);
- /* NOTE: We can assume slot != NULL here because xcalloc never
- returns NULL. */
- if (*slot != NULL)
+ if (!htab.insert (name).second)
return true;
- *slot = name;
}
return false;
--
2.39.2
^ permalink raw reply [flat|nested] 29+ messages in thread* [PATCH 08/19] Convert py-framefilter.c to new hash table
2023-04-07 15:25 [PATCH 00/19] Add hash table to gdbsupport Tom Tromey
` (6 preceding siblings ...)
2023-04-07 15:25 ` [PATCH 07/19] Convert breakpoint.c " Tom Tromey
@ 2023-04-07 15:25 ` Tom Tromey
2023-04-07 15:25 ` [PATCH 09/19] Convert disasm.c " Tom Tromey
` (12 subsequent siblings)
20 siblings, 0 replies; 29+ messages in thread
From: Tom Tromey @ 2023-04-07 15:25 UTC (permalink / raw)
To: gdb-patches
This converts py-framefilter.c to use the new hash table.
---
gdb/python/py-framefilter.c | 25 +++++++++----------------
1 file changed, 9 insertions(+), 16 deletions(-)
diff --git a/gdb/python/py-framefilter.c b/gdb/python/py-framefilter.c
index 0e8b2409636..987920c5a60 100644
--- a/gdb/python/py-framefilter.c
+++ b/gdb/python/py-framefilter.c
@@ -28,11 +28,11 @@
#include "stack.h"
#include "source.h"
#include "annotate.h"
-#include "hashtab.h"
#include "demangle.h"
#include "mi/mi-cmds.h"
#include "python-internal.h"
#include "gdbsupport/gdb_optional.h"
+#include "gdbsupport/hash-table.h"
#include "cli/cli-style.h"
enum mi_print_types
@@ -731,6 +731,8 @@ py_print_args (PyObject *filter,
return EXT_LANG_BT_OK;
}
+typedef gdb::hash_set<frame_info *> levels_printed_hash;
+
/* Print a single frame to the designated output stream, detecting
whether the output is MI or console, and formatting the output
according to the conventions of that protocol. FILTER is the
@@ -749,7 +751,8 @@ py_print_args (PyObject *filter,
static enum ext_lang_bt_status
py_print_frame (PyObject *filter, frame_filter_flags flags,
enum ext_lang_frame_args args_type,
- struct ui_out *out, int indent, htab_t levels_printed)
+ struct ui_out *out, int indent,
+ levels_printed_hash &levels_printed)
{
int has_addr = 0;
CORE_ADDR address = 0;
@@ -859,23 +862,16 @@ py_print_frame (PyObject *filter, frame_filter_flags flags,
&& (location_print
|| (out->is_mi_like_p () && (print_frame_info || print_args))))
{
- struct frame_info **slot;
- int level;
-
- slot = (frame_info **) htab_find_slot (levels_printed,
- frame.get(), INSERT);
-
- level = frame_relative_level (frame);
+ int level = frame_relative_level (frame);
/* Check if this frame has already been printed (there are cases
where elided synthetic dummy-frames have to 'borrow' the frame
architecture from the eliding frame. If that is the case, do
not print 'level', but print spaces. */
- if (*slot == frame)
+ if (!levels_printed.insert (frame.get ()).second)
out->field_skip ("level");
else
{
- *slot = frame.get ();
annotate_frame_begin (print_level ? level : 0,
gdbarch, address);
out->text ("#");
@@ -1195,10 +1191,7 @@ gdbpy_apply_frame_filter (const struct extension_language_defn *extlang,
if (iterable == Py_None)
return EXT_LANG_BT_NO_FILTERS;
- htab_up levels_printed (htab_create (20,
- htab_hash_pointer,
- htab_eq_pointer,
- NULL));
+ levels_printed_hash levels_printed;
while (true)
{
@@ -1230,7 +1223,7 @@ gdbpy_apply_frame_filter (const struct extension_language_defn *extlang,
try
{
success = py_print_frame (item.get (), flags, args_type, out, 0,
- levels_printed.get ());
+ levels_printed);
}
catch (const gdb_exception_error &except)
{
--
2.39.2
^ permalink raw reply [flat|nested] 29+ messages in thread* [PATCH 09/19] Convert disasm.c to new hash table
2023-04-07 15:25 [PATCH 00/19] Add hash table to gdbsupport Tom Tromey
` (7 preceding siblings ...)
2023-04-07 15:25 ` [PATCH 08/19] Convert py-framefilter.c " Tom Tromey
@ 2023-04-07 15:25 ` Tom Tromey
2023-04-07 15:25 ` [PATCH 10/19] Convert compile/compile.c " Tom Tromey
` (11 subsequent siblings)
20 siblings, 0 replies; 29+ messages in thread
From: Tom Tromey @ 2023-04-07 15:25 UTC (permalink / raw)
To: gdb-patches
This converts disasm.c to use the new hash table.
---
gdb/disasm.c | 72 +++++++++++++++++++++++-------------------------------------
1 file changed, 27 insertions(+), 45 deletions(-)
diff --git a/gdb/disasm.c b/gdb/disasm.c
index 03cd4b7ee02..ef9481e9958 100644
--- a/gdb/disasm.c
+++ b/gdb/disasm.c
@@ -33,6 +33,7 @@
#include "valprint.h"
#include "cli/cli-style.h"
#include "objfiles.h"
+#include "gdbsupport/hash-table.h"
/* Disassemble functions.
FIXME: We should get rid of all the duplicate code in gdb that does
@@ -119,72 +120,54 @@ struct deprecated_dis_line_entry
struct dis_line_entry
{
- struct symtab *symtab;
- int line;
-};
-
-/* Hash function for dis_line_entry. */
-
-static hashval_t
-hash_dis_line_entry (const void *item)
-{
- const struct dis_line_entry *dle = (const struct dis_line_entry *) item;
+ struct symtab *symtab = nullptr;
+ int line = -1;
- return htab_hash_pointer (dle->symtab) + dle->line;
-}
+ operator bool () const
+ { return symtab != nullptr; }
-/* Equal function for dis_line_entry. */
+ bool operator== (const dis_line_entry &other) const
+ { return symtab == other.symtab && line == other.line; }
+};
-static int
-eq_dis_line_entry (const void *item_lhs, const void *item_rhs)
+namespace std
{
- const struct dis_line_entry *lhs = (const struct dis_line_entry *) item_lhs;
- const struct dis_line_entry *rhs = (const struct dis_line_entry *) item_rhs;
- return (lhs->symtab == rhs->symtab
- && lhs->line == rhs->line);
-}
-
-/* Create the table to manage lines for mixed source/disassembly. */
-
-static htab_t
-allocate_dis_line_table (void)
+template<>
+struct hash<dis_line_entry>
{
- return htab_create_alloc (41,
- hash_dis_line_entry, eq_dis_line_entry,
- xfree, xcalloc, xfree);
+ size_t operator() (const dis_line_entry &entry) const
+ {
+ return std::hash<symtab *> () (entry.symtab) + entry.line;
+ }
+};
+
}
/* Add a new dis_line_entry containing SYMTAB and LINE to TABLE. */
static void
-add_dis_line_entry (htab_t table, struct symtab *symtab, int line)
+add_dis_line_entry (gdb::hash_set<dis_line_entry> &table,
+ struct symtab *symtab, int line)
{
- void **slot;
- struct dis_line_entry dle, *dlep;
+ struct dis_line_entry dle;
dle.symtab = symtab;
dle.line = line;
- slot = htab_find_slot (table, &dle, INSERT);
- if (*slot == NULL)
- {
- dlep = XNEW (struct dis_line_entry);
- dlep->symtab = symtab;
- dlep->line = line;
- *slot = dlep;
- }
+ table.insert (dle);
}
/* Return non-zero if SYMTAB, LINE are in TABLE. */
static int
-line_has_code_p (htab_t table, struct symtab *symtab, int line)
+line_has_code_p (const gdb::hash_set<dis_line_entry> &table,
+ struct symtab *symtab, int line)
{
struct dis_line_entry dle;
dle.symtab = symtab;
dle.line = line;
- return htab_find (table, &dle) != NULL;
+ return table.contains (dle);
}
/* Wrapper of target_read_code. */
@@ -739,7 +722,7 @@ do_mixed_source_and_assembly (struct gdbarch *gdbarch,
but if that text is for code that will be disassembled later, then
we'll want to defer printing it until later with its associated code. */
- htab_up dis_line_table (allocate_dis_line_table ());
+ gdb::hash_set<dis_line_entry> dis_line_table;
struct objfile *objfile = main_symtab->compunit ()->objfile ();
@@ -778,7 +761,7 @@ do_mixed_source_and_assembly (struct gdbarch *gdbarch,
pc += length;
if (sal.symtab != NULL)
- add_dis_line_entry (dis_line_table.get (), sal.symtab, sal.line);
+ add_dis_line_entry (dis_line_table, sal.symtab, sal.line);
}
/* Second pass: print the disassembly.
@@ -852,8 +835,7 @@ do_mixed_source_and_assembly (struct gdbarch *gdbarch,
not associated with code that we'll print later. */
for (l = sal.line - 1; l > last_line; --l)
{
- if (line_has_code_p (dis_line_table.get (),
- sal.symtab, l))
+ if (line_has_code_p (dis_line_table, sal.symtab, l))
break;
}
if (l < sal.line - 1)
--
2.39.2
^ permalink raw reply [flat|nested] 29+ messages in thread* [PATCH 10/19] Convert compile/compile.c to new hash table
2023-04-07 15:25 [PATCH 00/19] Add hash table to gdbsupport Tom Tromey
` (8 preceding siblings ...)
2023-04-07 15:25 ` [PATCH 09/19] Convert disasm.c " Tom Tromey
@ 2023-04-07 15:25 ` Tom Tromey
2023-04-07 15:25 ` [PATCH 11/19] Convert type copying " Tom Tromey
` (10 subsequent siblings)
20 siblings, 0 replies; 29+ messages in thread
From: Tom Tromey @ 2023-04-07 15:25 UTC (permalink / raw)
To: gdb-patches
This converts compile/compile.c to use the new hash table. This
change is also an example of the new hash_map template.
---
gdb/compile/compile.c | 151 ++++----------------------------------------------
gdb/compile/compile.h | 10 +++-
2 files changed, 18 insertions(+), 143 deletions(-)
diff --git a/gdb/compile/compile.c b/gdb/compile/compile.c
index c07686c32e0..d3c2554a90e 100644
--- a/gdb/compile/compile.c
+++ b/gdb/compile/compile.c
@@ -60,112 +60,15 @@ static struct cmd_list_element *compile_command_list;
bool compile_debug;
-/* Object of this type are stored in the compiler's symbol_err_map. */
-
-struct symbol_error
-{
- /* The symbol. */
-
- const struct symbol *sym;
-
- /* The error message to emit. This is malloc'd and owned by the
- hash table. */
-
- char *message;
-};
-
-/* An object that maps a gdb type to a gcc type. */
-
-struct type_map_instance
-{
- /* The gdb type. */
-
- struct type *type;
-
- /* The corresponding gcc type handle. */
-
- gcc_type gcc_type_handle;
-};
-
-/* Hash a type_map_instance. */
-
-static hashval_t
-hash_type_map_instance (const void *p)
-{
- const struct type_map_instance *inst = (const struct type_map_instance *) p;
-
- return htab_hash_pointer (inst->type);
-}
-
-/* Check two type_map_instance objects for equality. */
-
-static int
-eq_type_map_instance (const void *a, const void *b)
-{
- const struct type_map_instance *insta = (const struct type_map_instance *) a;
- const struct type_map_instance *instb = (const struct type_map_instance *) b;
-
- return insta->type == instb->type;
-}
-
-/* Hash function for struct symbol_error. */
-
-static hashval_t
-hash_symbol_error (const void *a)
-{
- const struct symbol_error *se = (const struct symbol_error *) a;
-
- return htab_hash_pointer (se->sym);
-}
-
-/* Equality function for struct symbol_error. */
-
-static int
-eq_symbol_error (const void *a, const void *b)
-{
- const struct symbol_error *sea = (const struct symbol_error *) a;
- const struct symbol_error *seb = (const struct symbol_error *) b;
-
- return sea->sym == seb->sym;
-}
-
-/* Deletion function for struct symbol_error. */
-
-static void
-del_symbol_error (void *a)
-{
- struct symbol_error *se = (struct symbol_error *) a;
-
- xfree (se->message);
- xfree (se);
-}
-
-/* Constructor for compile_instance. */
-
-compile_instance::compile_instance (struct gcc_base_context *gcc_fe,
- const char *options)
- : m_gcc_fe (gcc_fe), m_gcc_target_options (options),
- m_type_map (htab_create_alloc (10, hash_type_map_instance,
- eq_type_map_instance,
- xfree, xcalloc, xfree)),
- m_symbol_err_map (htab_create_alloc (10, hash_symbol_error,
- eq_symbol_error, del_symbol_error,
- xcalloc, xfree))
-{
-}
-
/* See compile-internal.h. */
bool
compile_instance::get_cached_type (struct type *type, gcc_type *ret) const
{
- struct type_map_instance inst, *found;
-
- inst.type = type;
- found = (struct type_map_instance *) htab_find (m_type_map.get (), &inst);
- if (found != NULL)
+ auto iter = m_type_map.find (type);
+ if (iter != m_type_map.end ())
{
- *ret = found->gcc_type_handle;
+ *ret = iter->second;
return true;
}
@@ -177,25 +80,13 @@ compile_instance::get_cached_type (struct type *type, gcc_type *ret) const
void
compile_instance::insert_type (struct type *type, gcc_type gcc_type)
{
- struct type_map_instance inst, *add;
- void **slot;
-
- inst.type = type;
- inst.gcc_type_handle = gcc_type;
- slot = htab_find_slot (m_type_map.get (), &inst, INSERT);
-
- add = (struct type_map_instance *) *slot;
/* The type might have already been inserted in order to handle
recursive types. */
- if (add != NULL && add->gcc_type_handle != gcc_type)
+ auto iter = m_type_map.find (type);
+ if (iter != m_type_map.end () && (*iter).second != gcc_type)
error (_("Unexpected type id from GCC, check you use recent enough GCC."));
- if (add == NULL)
- {
- add = XNEW (struct type_map_instance);
- *add = inst;
- *slot = add;
- }
+ m_type_map.insert (type, gcc_type);
}
/* See compile-internal.h. */
@@ -204,19 +95,7 @@ void
compile_instance::insert_symbol_error (const struct symbol *sym,
const char *text)
{
- struct symbol_error e;
- void **slot;
-
- e.sym = sym;
- slot = htab_find_slot (m_symbol_err_map.get (), &e, INSERT);
- if (*slot == NULL)
- {
- struct symbol_error *ep = XNEW (struct symbol_error);
-
- ep->sym = sym;
- ep->message = xstrdup (text);
- *slot = ep;
- }
+ m_symbol_err_map.insert (sym, text);
}
/* See compile-internal.h. */
@@ -224,20 +103,12 @@ compile_instance::insert_symbol_error (const struct symbol *sym,
void
compile_instance::error_symbol_once (const struct symbol *sym)
{
- struct symbol_error search;
- struct symbol_error *err;
-
- if (m_symbol_err_map == NULL)
- return;
-
- search.sym = sym;
- err = (struct symbol_error *) htab_find (m_symbol_err_map.get (), &search);
- if (err == NULL || err->message == NULL)
+ auto iter = m_symbol_err_map.find (sym);
+ if (iter == m_symbol_err_map.end () || (*iter).second.empty ())
return;
- gdb::unique_xmalloc_ptr<char> message (err->message);
- err->message = NULL;
- error (_("%s"), message.get ());
+ std::string message = std::move ((*iter).second);
+ error (_("%s"), message.c_str ());
}
/* Implement "show debug compile". */
diff --git a/gdb/compile/compile.h b/gdb/compile/compile.h
index a3b6a18fe20..d8703326d68 100644
--- a/gdb/compile/compile.h
+++ b/gdb/compile/compile.h
@@ -19,6 +19,7 @@
#define COMPILE_COMPILE_H
#include "gcc-c-interface.h"
+#include "gdbsupport/hash-table.h"
struct ui_file;
struct gdbarch;
@@ -33,7 +34,10 @@ struct dynamic_prop;
class compile_instance
{
public:
- compile_instance (struct gcc_base_context *gcc_fe, const char *options);
+ compile_instance (struct gcc_base_context *gcc_fe, const char *options)
+ : m_gcc_fe (gcc_fe),
+ m_gcc_target_options (options)
+ { }
virtual ~compile_instance ()
{
@@ -135,10 +139,10 @@ class compile_instance
std::string m_gcc_target_options;
/* Map from gdb types to gcc types. */
- htab_up m_type_map;
+ gdb::hash_map<struct type *, gcc_type> m_type_map;
/* Map from gdb symbols to gcc error messages to emit. */
- htab_up m_symbol_err_map;
+ gdb::hash_map<const struct symbol *, std::string> m_symbol_err_map;
};
/* Public function that is called from compile_control case in the
--
2.39.2
^ permalink raw reply [flat|nested] 29+ messages in thread* [PATCH 11/19] Convert type copying to new hash table
2023-04-07 15:25 [PATCH 00/19] Add hash table to gdbsupport Tom Tromey
` (9 preceding siblings ...)
2023-04-07 15:25 ` [PATCH 10/19] Convert compile/compile.c " Tom Tromey
@ 2023-04-07 15:25 ` Tom Tromey
2023-04-07 15:25 ` [PATCH 12/19] Convert static links " Tom Tromey
` (9 subsequent siblings)
20 siblings, 0 replies; 29+ messages in thread
From: Tom Tromey @ 2023-04-07 15:25 UTC (permalink / raw)
To: gdb-patches
This converts the type copying code to use the new hash map.
---
gdb/compile/compile-object-run.c | 4 +--
gdb/extension-priv.h | 3 +-
gdb/extension.c | 3 +-
gdb/extension.h | 4 ++-
gdb/gdbtypes.c | 59 ++++------------------------------------
gdb/gdbtypes.h | 7 ++---
gdb/guile/guile-internal.h | 2 +-
gdb/guile/scm-type.c | 9 +++---
gdb/guile/scm-value.c | 3 +-
gdb/python/py-type.c | 6 ++--
gdb/python/py-value.c | 3 +-
gdb/python/python-internal.h | 2 +-
gdb/value.c | 17 ++++++------
gdb/value.h | 4 +--
14 files changed, 40 insertions(+), 86 deletions(-)
diff --git a/gdb/compile/compile-object-run.c b/gdb/compile/compile-object-run.c
index abdea4d371f..f18fa32d802 100644
--- a/gdb/compile/compile-object-run.c
+++ b/gdb/compile/compile-object-run.c
@@ -106,8 +106,8 @@ do_module_cleanup (void *arg, int registers_valid)
static type *
create_copied_type_recursive (objfile *objfile, type *func_type)
{
- htab_up copied_types = create_copied_types_hash ();
- func_type = copy_type_recursive (func_type, copied_types.get ());
+ copied_types_hash_t copied_types;
+ func_type = copy_type_recursive (func_type, copied_types);
return func_type;
}
diff --git a/gdb/extension-priv.h b/gdb/extension-priv.h
index 3442302a0be..df19fefd14c 100644
--- a/gdb/extension-priv.h
+++ b/gdb/extension-priv.h
@@ -192,7 +192,8 @@ struct extension_language_ops
COPIED_TYPES is used to prevent cycles / duplicates and is passed to
preserve_one_value. */
void (*preserve_values) (const struct extension_language_defn *,
- struct objfile *objfile, htab_t copied_types);
+ struct objfile *objfile,
+ copied_types_hash_t &copied_types);
/* Return non-zero if there is a stop condition for the breakpoint.
This is used to implement the restriction that a breakpoint may have
diff --git a/gdb/extension.c b/gdb/extension.c
index 65f3bab32a7..779910ba8d8 100644
--- a/gdb/extension.c
+++ b/gdb/extension.c
@@ -560,7 +560,8 @@ apply_ext_lang_frame_filter (frame_info_ptr frame,
preserve_one_value. */
void
-preserve_ext_lang_values (struct objfile *objfile, htab_t copied_types)
+preserve_ext_lang_values (struct objfile *objfile,
+ copied_types_hash_t &copied_types)
{
for (const struct extension_language_defn *extlang : extension_languages)
{
diff --git a/gdb/extension.h b/gdb/extension.h
index 2b0445133d3..3b9b504f2ef 100644
--- a/gdb/extension.h
+++ b/gdb/extension.h
@@ -23,6 +23,7 @@
#include "mi/mi-cmds.h" /* For PRINT_NO_VALUES, etc. */
#include "gdbsupport/array-view.h"
#include "gdbsupport/gdb_optional.h"
+#include "gdbtypes.h"
struct breakpoint;
struct command_line;
@@ -295,7 +296,8 @@ extern enum ext_lang_bt_status apply_ext_lang_frame_filter
enum ext_lang_frame_args args_type,
struct ui_out *out, int frame_low, int frame_high);
-extern void preserve_ext_lang_values (struct objfile *, htab_t copied_types);
+extern void preserve_ext_lang_values (struct objfile *,
+ copied_types_hash_t &copied_types);
extern const struct extension_language_defn *get_breakpoint_cond_ext_lang
(struct breakpoint *b, enum extension_language skip_lang);
diff --git a/gdb/gdbtypes.c b/gdb/gdbtypes.c
index 6af59351b76..9f3b3cbd256 100644
--- a/gdb/gdbtypes.c
+++ b/gdb/gdbtypes.c
@@ -5461,46 +5461,6 @@ recursive_dump_type (struct type *type, int spaces)
obstack_free (&dont_print_type_obstack, NULL);
}
\f
-/* Trivial helpers for the libiberty hash table, for mapping one
- type to another. */
-
-struct type_pair
-{
- type_pair (struct type *old_, struct type *newobj_)
- : old (old_), newobj (newobj_)
- {}
-
- struct type * const old, * const newobj;
-};
-
-static hashval_t
-type_pair_hash (const void *item)
-{
- const struct type_pair *pair = (const struct type_pair *) item;
-
- return htab_hash_pointer (pair->old);
-}
-
-static int
-type_pair_eq (const void *item_lhs, const void *item_rhs)
-{
- const struct type_pair *lhs = (const struct type_pair *) item_lhs;
- const struct type_pair *rhs = (const struct type_pair *) item_rhs;
-
- return lhs->old == rhs->old;
-}
-
-/* Allocate the hash table used by copy_type_recursive to walk
- types without duplicates. */
-
-htab_up
-create_copied_types_hash ()
-{
- return htab_up (htab_create_alloc (1, type_pair_hash, type_pair_eq,
- htab_delete_entry<type_pair>,
- xcalloc, xfree));
-}
-
/* Recursively copy (deep copy) a dynamic attribute list of a type. */
static struct dynamic_prop_list *
@@ -5532,27 +5492,20 @@ copy_dynamic_prop_list (struct obstack *storage,
it is not associated with OBJFILE. */
struct type *
-copy_type_recursive (struct type *type, htab_t copied_types)
+copy_type_recursive (struct type *type, copied_types_hash_t &copied_types)
{
- void **slot;
- struct type *new_type;
-
if (!type->is_objfile_owned ())
return type;
- struct type_pair pair (type, nullptr);
+ auto iter = copied_types.find (type);
+ if (iter != copied_types.end ())
+ return iter->second;
- slot = htab_find_slot (copied_types, &pair, INSERT);
- if (*slot != NULL)
- return ((struct type_pair *) *slot)->newobj;
-
- new_type = type_allocator (type->arch ()).new_type ();
+ struct type *new_type = type_allocator (type->arch ()).new_type ();
/* We must add the new type to the hash table immediately, in case
we encounter this type again during a recursive call below. */
- struct type_pair *stored = new type_pair (type, new_type);
-
- *slot = stored;
+ copied_types.insert (type, new_type);
/* Copy the common fields of types. For the main type, we simply
copy the entire thing and then update specific fields as needed. */
diff --git a/gdb/gdbtypes.h b/gdb/gdbtypes.h
index b5cccb784b2..0c53c9d7203 100644
--- a/gdb/gdbtypes.h
+++ b/gdb/gdbtypes.h
@@ -44,10 +44,9 @@
written such that they can be used as both rvalues and lvalues.
*/
-#include "hashtab.h"
#include "gdbsupport/array-view.h"
-#include "gdbsupport/gdb-hashtab.h"
#include "gdbsupport/gdb_optional.h"
+#include "gdbsupport/hash-table.h"
#include "gdbsupport/offset-type.h"
#include "gdbsupport/enum-flags.h"
#include "gdbsupport/underlying.h"
@@ -2708,10 +2707,10 @@ extern int class_or_union_p (const struct type *);
extern void maintenance_print_type (const char *, int);
-extern htab_up create_copied_types_hash ();
+typedef gdb::hash_map<type *, type *> copied_types_hash_t;
extern struct type *copy_type_recursive (struct type *type,
- htab_t copied_types);
+ copied_types_hash_t &copied_types);
extern struct type *copy_type (const struct type *type);
diff --git a/gdb/guile/guile-internal.h b/gdb/guile/guile-internal.h
index b04ef17a5ad..e29e654de29 100644
--- a/gdb/guile/guile-internal.h
+++ b/gdb/guile/guile-internal.h
@@ -596,7 +596,7 @@ extern bool gdbscm_auto_load_enabled (const struct extension_language_defn *);
extern void gdbscm_preserve_values
(const struct extension_language_defn *,
- struct objfile *, htab_t copied_types);
+ struct objfile *, copied_types_hash_t &copied_types);
extern enum ext_lang_rc gdbscm_apply_val_pretty_printer
(const struct extension_language_defn *,
diff --git a/gdb/guile/scm-type.c b/gdb/guile/scm-type.c
index 008e792cc34..a880a478ba7 100644
--- a/gdb/guile/scm-type.c
+++ b/gdb/guile/scm-type.c
@@ -95,8 +95,8 @@ struct tyscm_deleter
return;
gdb_assert (htab != nullptr);
- htab_up copied_types = create_copied_types_hash ();
- htab_traverse_noresize (htab, tyscm_copy_type_recursive, copied_types.get ());
+ copied_types_hash_t copied_types;
+ htab_traverse_noresize (htab, tyscm_copy_type_recursive, &copied_types);
htab_delete (htab);
}
};
@@ -376,13 +376,12 @@ static int
tyscm_copy_type_recursive (void **slot, void *info)
{
type_smob *t_smob = (type_smob *) *slot;
- htab_t copied_types = (htab_t) info;
+ copied_types_hash_t *copied_types = (copied_types_hash_t *) info;
htab_t htab;
eqable_gdb_smob **new_slot;
type_smob t_smob_for_lookup;
- htab_empty (copied_types);
- t_smob->type = copy_type_recursive (t_smob->type, copied_types);
+ t_smob->type = copy_type_recursive (t_smob->type, *copied_types);
/* The eq?-hashtab that the type lived in is going away.
Add the type to its new eq?-hashtab: Otherwise if/when the type is later
diff --git a/gdb/guile/scm-value.c b/gdb/guile/scm-value.c
index 32a9539b3e2..29f51aaf852 100644
--- a/gdb/guile/scm-value.c
+++ b/gdb/guile/scm-value.c
@@ -87,7 +87,8 @@ static SCM substitute_symbol;
void
gdbscm_preserve_values (const struct extension_language_defn *extlang,
- struct objfile *objfile, htab_t copied_types)
+ struct objfile *objfile,
+ copied_types_hash_t &copied_types)
{
value_smob *iter;
diff --git a/gdb/python/py-type.c b/gdb/python/py-type.c
index b68ec8d2c92..a0efec61e17 100644
--- a/gdb/python/py-type.c
+++ b/gdb/python/py-type.c
@@ -1100,15 +1100,13 @@ struct typy_deleter
operating on. */
gdbpy_enter enter_py;
- htab_up copied_types = create_copied_types_hash ();
+ copied_types_hash_t copied_types;
while (obj)
{
type_object *next = obj->next;
- htab_empty (copied_types.get ());
-
- obj->type = copy_type_recursive (obj->type, copied_types.get ());
+ obj->type = copy_type_recursive (obj->type, copied_types);
obj->next = NULL;
obj->prev = NULL;
diff --git a/gdb/python/py-value.c b/gdb/python/py-value.c
index 65384c781bc..1857649eb3c 100644
--- a/gdb/python/py-value.c
+++ b/gdb/python/py-value.c
@@ -224,7 +224,8 @@ valpy_init (PyObject *self, PyObject *args, PyObject *kwds)
each. */
void
gdbpy_preserve_values (const struct extension_language_defn *extlang,
- struct objfile *objfile, htab_t copied_types)
+ struct objfile *objfile,
+ copied_types_hash_t &copied_types)
{
value_object *iter;
diff --git a/gdb/python/python-internal.h b/gdb/python/python-internal.h
index 258f5c42537..508dd2ef550 100644
--- a/gdb/python/python-internal.h
+++ b/gdb/python/python-internal.h
@@ -383,7 +383,7 @@ extern enum ext_lang_bt_status gdbpy_apply_frame_filter
struct ui_out *out, int frame_low, int frame_high);
extern void gdbpy_preserve_values (const struct extension_language_defn *,
struct objfile *objfile,
- htab_t copied_types);
+ copied_types_hash_t &copied_types);
extern enum ext_lang_bp_stop gdbpy_breakpoint_cond_says_stop
(const struct extension_language_defn *, struct breakpoint *);
extern int gdbpy_breakpoint_has_cond (const struct extension_language_defn *,
diff --git a/gdb/value.c b/gdb/value.c
index eab1933b256..1243e4f5eea 100644
--- a/gdb/value.c
+++ b/gdb/value.c
@@ -2373,7 +2373,7 @@ add_internal_function (gdb::unique_xmalloc_ptr<char> &&name,
}
void
-value::preserve (struct objfile *objfile, htab_t copied_types)
+value::preserve (struct objfile *objfile, copied_types_hash_t &copied_types)
{
if (m_type->objfile_owner () == objfile)
m_type = copy_type_recursive (m_type, copied_types);
@@ -2386,7 +2386,7 @@ value::preserve (struct objfile *objfile, htab_t copied_types)
static void
preserve_one_internalvar (struct internalvar *var, struct objfile *objfile,
- htab_t copied_types)
+ copied_types_hash_t &copied_types)
{
switch (var->kind)
{
@@ -2409,7 +2409,7 @@ preserve_one_internalvar (struct internalvar *var, struct objfile *objfile,
static void
preserve_one_varobj (struct varobj *varobj, struct objfile *objfile,
- htab_t copied_types)
+ copied_types_hash_t &copied_types)
{
if (varobj->type->is_objfile_owned ()
&& varobj->type->objfile_owner () == objfile)
@@ -2433,22 +2433,21 @@ preserve_values (struct objfile *objfile)
{
/* Create the hash table. We allocate on the objfile's obstack, since
it is soon to be deleted. */
- htab_up copied_types = create_copied_types_hash ();
+ copied_types_hash_t copied_types;
for (const value_ref_ptr &item : value_history)
- item->preserve (objfile, copied_types.get ());
+ item->preserve (objfile, copied_types);
for (auto &pair : internalvars)
- preserve_one_internalvar (&pair.second, objfile, copied_types.get ());
+ preserve_one_internalvar (&pair.second, objfile, copied_types);
/* For the remaining varobj, check that none has type owned by OBJFILE. */
all_root_varobjs ([&copied_types, objfile] (struct varobj *varobj)
{
- preserve_one_varobj (varobj, objfile,
- copied_types.get ());
+ preserve_one_varobj (varobj, objfile, copied_types);
});
- preserve_ext_lang_values (objfile, copied_types.get ());
+ preserve_ext_lang_values (objfile, copied_types);
}
static void
diff --git a/gdb/value.h b/gdb/value.h
index e13f92c397b..49c160b8532 100644
--- a/gdb/value.h
+++ b/gdb/value.h
@@ -24,12 +24,12 @@
#include "extension.h"
#include "gdbsupport/gdb_ref_ptr.h"
#include "gmp-utils.h"
+#include "gdbtypes.h"
struct block;
struct expression;
struct regcache;
struct symbol;
-struct type;
struct ui_file;
struct language_defn;
struct value_print_options;
@@ -563,7 +563,7 @@ struct value
/* Update this value before discarding OBJFILE. COPIED_TYPES is
used to prevent cycles / duplicates. */
- void preserve (struct objfile *objfile, htab_t copied_types);
+ void preserve (struct objfile *objfile, copied_types_hash_t &copied_types);
/* Unpack a bitfield of BITSIZE bits found at BITPOS in the object
at VALADDR + EMBEDDEDOFFSET that has the type of DEST_VAL and
--
2.39.2
^ permalink raw reply [flat|nested] 29+ messages in thread* [PATCH 12/19] Convert static links to new hash table
2023-04-07 15:25 [PATCH 00/19] Add hash table to gdbsupport Tom Tromey
` (10 preceding siblings ...)
2023-04-07 15:25 ` [PATCH 11/19] Convert type copying " Tom Tromey
@ 2023-04-07 15:25 ` Tom Tromey
2023-04-07 15:25 ` [PATCH 13/19] Convert gnu-v3-abi.c " Tom Tromey
` (8 subsequent siblings)
20 siblings, 0 replies; 29+ messages in thread
From: Tom Tromey @ 2023-04-07 15:25 UTC (permalink / raw)
To: gdb-patches
This converts the objfile static link table to the new hash map.
---
gdb/objfiles.c | 74 +++++++---------------------------------------------------
gdb/objfiles.h | 4 +++-
gdb/symfile.c | 2 +-
3 files changed, 13 insertions(+), 67 deletions(-)
diff --git a/gdb/objfiles.c b/gdb/objfiles.c
index 9caebfefd59..7de90f26c33 100644
--- a/gdb/objfiles.c
+++ b/gdb/objfiles.c
@@ -158,39 +158,6 @@ set_objfile_main_name (struct objfile *objfile,
objfile->per_bfd->language_of_main = lang;
}
-/* Helper structure to map blocks to static link properties in hash tables. */
-
-struct static_link_htab_entry
-{
- const struct block *block;
- const struct dynamic_prop *static_link;
-};
-
-/* Return a hash code for struct static_link_htab_entry *P. */
-
-static hashval_t
-static_link_htab_entry_hash (const void *p)
-{
- const struct static_link_htab_entry *e
- = (const struct static_link_htab_entry *) p;
-
- return htab_hash_pointer (e->block);
-}
-
-/* Return whether P1 an P2 (pointers to struct static_link_htab_entry) are
- mappings for the same block. */
-
-static int
-static_link_htab_entry_eq (const void *p1, const void *p2)
-{
- const struct static_link_htab_entry *e1
- = (const struct static_link_htab_entry *) p1;
- const struct static_link_htab_entry *e2
- = (const struct static_link_htab_entry *) p2;
-
- return e1->block == e2->block;
-}
-
/* Register STATIC_LINK as the static link for BLOCK, which is part of OBJFILE.
Must not be called more than once for each BLOCK. */
@@ -199,25 +166,10 @@ objfile_register_static_link (struct objfile *objfile,
const struct block *block,
const struct dynamic_prop *static_link)
{
- void **slot;
- struct static_link_htab_entry lookup_entry;
- struct static_link_htab_entry *entry;
-
- if (objfile->static_links == NULL)
- objfile->static_links.reset (htab_create_alloc
- (1, &static_link_htab_entry_hash, static_link_htab_entry_eq, NULL,
- xcalloc, xfree));
-
- /* Create a slot for the mapping, make sure it's the first mapping for this
- block and then create the mapping itself. */
- lookup_entry.block = block;
- slot = htab_find_slot (objfile->static_links.get (), &lookup_entry, INSERT);
- gdb_assert (*slot == NULL);
-
- entry = XOBNEW (&objfile->objfile_obstack, static_link_htab_entry);
- entry->block = block;
- entry->static_link = static_link;
- *slot = (void *) entry;
+ /* Enter the mapping and make sure it's the first mapping for this
+ block. */
+ auto insert_pair = objfile->static_links.insert (block, static_link);
+ gdb_assert (insert_pair.second);
}
/* Look for a static link for BLOCK, which is part of OBJFILE. Return NULL if
@@ -227,19 +179,11 @@ const struct dynamic_prop *
objfile_lookup_static_link (struct objfile *objfile,
const struct block *block)
{
- struct static_link_htab_entry *entry;
- struct static_link_htab_entry lookup_entry;
-
- if (objfile->static_links == NULL)
- return NULL;
- lookup_entry.block = block;
- entry = ((struct static_link_htab_entry *)
- htab_find (objfile->static_links.get (), &lookup_entry));
- if (entry == NULL)
- return NULL;
-
- gdb_assert (entry->block == block);
- return entry->static_link;
+ auto iter = objfile->static_links.find (block);
+ if (iter == objfile->static_links.end ())
+ return nullptr;
+ gdb_assert (iter->first == block);
+ return iter->second;
}
\f
diff --git a/gdb/objfiles.h b/gdb/objfiles.h
index 342aa09ac6a..79c701905fe 100644
--- a/gdb/objfiles.h
+++ b/gdb/objfiles.h
@@ -39,6 +39,7 @@
#include "jit.h"
#include "quick-symbol.h"
#include <forward_list>
+#include "gdbsupport/hash-table.h"
struct htab;
struct objfile_data;
@@ -769,7 +770,8 @@ struct objfile
Very few blocks have a static link, so it's more memory efficient to
store these here rather than in struct block. Static links must be
allocated on the objfile's obstack. */
- htab_up static_links;
+ gdb::hash_map<const struct block *,
+ const struct dynamic_prop *> static_links;
/* JIT-related data for this objfile, if the objfile is a JITer;
that is, it produces JITed objfiles. */
diff --git a/gdb/symfile.c b/gdb/symfile.c
index bb9981a4634..b2fc917d5ed 100644
--- a/gdb/symfile.c
+++ b/gdb/symfile.c
@@ -2562,7 +2562,7 @@ reread_symbols (int from_tty)
objfile->sect_index_text = -1;
objfile->compunit_symtabs = NULL;
objfile->template_symbols = NULL;
- objfile->static_links.reset (nullptr);
+ objfile->static_links.clear ();
/* obstack_init also initializes the obstack so it is
empty. We could use obstack_specify_allocation but
--
2.39.2
^ permalink raw reply [flat|nested] 29+ messages in thread* [PATCH 13/19] Convert gnu-v3-abi.c to new hash table
2023-04-07 15:25 [PATCH 00/19] Add hash table to gdbsupport Tom Tromey
` (11 preceding siblings ...)
2023-04-07 15:25 ` [PATCH 12/19] Convert static links " Tom Tromey
@ 2023-04-07 15:25 ` Tom Tromey
2023-04-07 15:25 ` [PATCH 14/19] Convert abbrev cache " Tom Tromey
` (7 subsequent siblings)
20 siblings, 0 replies; 29+ messages in thread
From: Tom Tromey @ 2023-04-07 15:25 UTC (permalink / raw)
To: gdb-patches
This converts gnu-v3-abi.c to use the new hash table.
This change shows how a std::vector can easily be made directly from
the hash table, simplifying the earlier approach of constructing a
vector and a hash table at the same time.
---
gdb/gnu-v3-abi.c | 101 ++++++++++++++++++++-----------------------------------
1 file changed, 36 insertions(+), 65 deletions(-)
diff --git a/gdb/gnu-v3-abi.c b/gdb/gnu-v3-abi.c
index 12bc5b09a93..ebd9097b28d 100644
--- a/gdb/gnu-v3-abi.c
+++ b/gdb/gnu-v3-abi.c
@@ -33,6 +33,7 @@
#include "cli/cli-style.h"
#include "dwarf2/loc.h"
#include "inferior.h"
+#include "gdbsupport/hash-table.h"
static struct cp_abi_ops gnu_v3_abi_ops;
@@ -786,51 +787,36 @@ gnuv3_method_ptr_to_value (struct value **this_p, struct value *method_ptr)
return value_from_pointer (lookup_pointer_type (method_type), ptr_value);
}
-/* Objects of this type are stored in a hash table and a vector when
- printing the vtables for a class. */
+/* Trait type used for the keys of the hash map used when printing
+ vtables for a class. */
-struct value_and_voffset
+struct value_traits
{
- /* The value representing the object. */
- struct value *value;
+ typedef value *value_type;
- /* The maximum vtable offset we've found for any object at this
- offset in the outermost object. */
- int max_voffset;
-};
-
-/* Hash function for value_and_voffset. */
+ static bool is_empty (const value_type &val)
+ { return val == nullptr; }
-static hashval_t
-hash_value_and_voffset (const void *p)
-{
- const struct value_and_voffset *o = (const struct value_and_voffset *) p;
+ static bool equals (const value_type &lhs, const value_type &rhs)
+ {
+ return (lhs->address () + lhs->embedded_offset ()
+ == rhs->address () + rhs->embedded_offset ());
+ }
- return o->value->address () + o->value->embedded_offset ();
-}
-
-/* Equality function for value_and_voffset. */
-
-static int
-eq_value_and_voffset (const void *a, const void *b)
-{
- const struct value_and_voffset *ova = (const struct value_and_voffset *) a;
- const struct value_and_voffset *ovb = (const struct value_and_voffset *) b;
+ static size_t hash (const value_type &val)
+ { return val->address () + val->embedded_offset (); }
+};
- return (ova->value->address () + ova->value->embedded_offset ()
- == ovb->value->address () + ovb->value->embedded_offset ());
-}
+typedef gdb::traited_hash_map<value_traits, int> vtable_hash_t;
-/* Comparison function for value_and_voffset. */
+/* Comparison function used for sorting the vtable entries. */
static bool
-compare_value_and_voffset (const struct value_and_voffset *va,
- const struct value_and_voffset *vb)
+compare_value_and_voffset (const std::pair<value *, int> &va,
+ const std::pair<value *, int> &vb)
{
- CORE_ADDR addra = (va->value->address ()
- + va->value->embedded_offset ());
- CORE_ADDR addrb = (vb->value->address ()
- + vb->value->embedded_offset ());
+ CORE_ADDR addra = va.first->address () + va.first->embedded_offset ();
+ CORE_ADDR addrb = vb.first->address () + vb.first->embedded_offset ();
return addra < addrb;
}
@@ -838,18 +824,14 @@ compare_value_and_voffset (const struct value_and_voffset *va,
/* A helper function used when printing vtables. This determines the
key (most derived) sub-object at each address and also computes the
maximum vtable offset seen for the corresponding vtable. Updates
- OFFSET_HASH and OFFSET_VEC with a new value_and_voffset object, if
- needed. VALUE is the object to examine. */
+ OFFSET_HASH with a new value_and_voffset object, if needed. VALUE
+ is the object to examine. */
static void
-compute_vtable_size (htab_t offset_hash,
- std::vector<value_and_voffset *> *offset_vec,
- struct value *value)
+compute_vtable_size (vtable_hash_t &offset_hash, struct value *value)
{
int i;
struct type *type = check_typedef (value->type ());
- void **slot;
- struct value_and_voffset search_vo, *current_vo;
gdb_assert (type->code () == TYPE_CODE_STRUCT);
@@ -859,18 +841,8 @@ compute_vtable_size (htab_t offset_hash,
return;
/* Update the hash and the vec, if needed. */
- search_vo.value = value;
- slot = htab_find_slot (offset_hash, &search_vo, INSERT);
- if (*slot)
- current_vo = (struct value_and_voffset *) *slot;
- else
- {
- current_vo = XNEW (struct value_and_voffset);
- current_vo->value = value;
- current_vo->max_voffset = -1;
- *slot = current_vo;
- offset_vec->push_back (current_vo);
- }
+ auto insert_pair = offset_hash.insert (value, -1);
+ int ¤t_max_voffset = insert_pair.first->second;
/* Update the value_and_voffset object with the highest vtable
offset from this class. */
@@ -885,15 +857,15 @@ compute_vtable_size (htab_t offset_hash,
{
int voffset = TYPE_FN_FIELD_VOFFSET (fn, j);
- if (voffset > current_vo->max_voffset)
- current_vo->max_voffset = voffset;
+ if (voffset > current_max_voffset)
+ current_max_voffset = voffset;
}
}
}
/* Recurse into base classes. */
for (i = 0; i < TYPE_N_BASECLASSES (type); ++i)
- compute_vtable_size (offset_hash, offset_vec, value_field (value, i));
+ compute_vtable_size (offset_hash, value_field (value, i));
}
/* Helper for gnuv3_print_vtable that prints a single vtable. */
@@ -994,23 +966,22 @@ gnuv3_print_vtable (struct value *value)
return;
}
- htab_up offset_hash (htab_create_alloc (1, hash_value_and_voffset,
- eq_value_and_voffset,
- xfree, xcalloc, xfree));
- std::vector<value_and_voffset *> result_vec;
+ vtable_hash_t offset_hash;
+ compute_vtable_size (offset_hash, value);
- compute_vtable_size (offset_hash.get (), &result_vec, value);
+ std::vector<std::pair<struct value *, int>> result_vec (offset_hash.begin (),
+ offset_hash.end ());
std::sort (result_vec.begin (), result_vec.end (),
compare_value_and_voffset);
count = 0;
- for (value_and_voffset *iter : result_vec)
+ for (auto &item : result_vec)
{
- if (iter->max_voffset >= 0)
+ if (item.second >= 0)
{
if (count > 0)
gdb_printf ("\n");
- print_one_vtable (gdbarch, iter->value, iter->max_voffset, &opts);
+ print_one_vtable (gdbarch, item.first, item.second, &opts);
++count;
}
}
--
2.39.2
^ permalink raw reply [flat|nested] 29+ messages in thread* [PATCH 14/19] Convert abbrev cache to new hash table
2023-04-07 15:25 [PATCH 00/19] Add hash table to gdbsupport Tom Tromey
` (12 preceding siblings ...)
2023-04-07 15:25 ` [PATCH 13/19] Convert gnu-v3-abi.c " Tom Tromey
@ 2023-04-07 15:25 ` Tom Tromey
2023-04-07 15:25 ` [PATCH 15/19] Convert abbrevs " Tom Tromey
` (6 subsequent siblings)
20 siblings, 0 replies; 29+ messages in thread
From: Tom Tromey @ 2023-04-07 15:25 UTC (permalink / raw)
To: gdb-patches
This converts the DWARF abbrev cache to use the new hash table.
---
gdb/dwarf2/abbrev-cache.c | 35 ++---------------------------------
gdb/dwarf2/abbrev-cache.h | 37 ++++++++++++++++++++++++++++++-------
2 files changed, 32 insertions(+), 40 deletions(-)
diff --git a/gdb/dwarf2/abbrev-cache.c b/gdb/dwarf2/abbrev-cache.c
index 6de81cd8075..6ee2660e2f3 100644
--- a/gdb/dwarf2/abbrev-cache.c
+++ b/gdb/dwarf2/abbrev-cache.c
@@ -21,33 +21,6 @@
#include "dwarf2/read.h"
#include "dwarf2/abbrev-cache.h"
-/* Hash function for an abbrev table. */
-
-hashval_t
-abbrev_cache::hash_table (const void *item)
-{
- const struct abbrev_table *table = (const struct abbrev_table *) item;
- return to_underlying (table->sect_off);
-}
-
-/* Comparison function for abbrev table. */
-
-int
-abbrev_cache::eq_table (const void *lhs, const void *rhs)
-{
- const struct abbrev_table *l_table = (const struct abbrev_table *) lhs;
- const search_key *key = (const search_key *) rhs;
- return (l_table->section == key->section
- && l_table->sect_off == key->offset);
-}
-
-abbrev_cache::abbrev_cache ()
- : m_tables (htab_create_alloc (20, hash_table, eq_table,
- htab_delete_entry<abbrev_table>,
- xcalloc, xfree))
-{
-}
-
void
abbrev_cache::add (abbrev_table_up table)
{
@@ -55,11 +28,7 @@ abbrev_cache::add (abbrev_table_up table)
if (table == nullptr)
return;
- search_key key = { table->section, table->sect_off };
- void **slot = htab_find_slot_with_hash (m_tables.get (), &key,
- to_underlying (table->sect_off),
- INSERT);
+ auto insert_pair = m_tables.insert (std::move (table));
/* If this one already existed, then it should have been reused. */
- gdb_assert (*slot == nullptr);
- *slot = (void *) table.release ();
+ gdb_assert (insert_pair.second);
}
diff --git a/gdb/dwarf2/abbrev-cache.h b/gdb/dwarf2/abbrev-cache.h
index d9406534c5d..bfd48d796c4 100644
--- a/gdb/dwarf2/abbrev-cache.h
+++ b/gdb/dwarf2/abbrev-cache.h
@@ -21,12 +21,13 @@
#define GDB_DWARF2_ABBREV_CACHE_H
#include "dwarf2/abbrev.h"
+#include "gdbsupport/hash-table.h"
/* An abbrev cache holds abbrev tables for easier reuse. */
class abbrev_cache
{
public:
- abbrev_cache ();
+ abbrev_cache () = default;
DISABLE_COPY_AND_ASSIGN (abbrev_cache);
/* Find an abbrev table coming from the abbrev section SECTION at
@@ -36,8 +37,10 @@ class abbrev_cache
{
search_key key = { section, offset };
- return (abbrev_table *) htab_find_with_hash (m_tables.get (), &key,
- to_underlying (offset));
+ auto iter = m_tables.find (key, to_underlying (offset));
+ if (iter == m_tables.end ())
+ return nullptr;
+ return iter->get ();
}
/* Add TABLE to this cache. Ownership of TABLE is transferred to
@@ -49,17 +52,37 @@ class abbrev_cache
private:
- static hashval_t hash_table (const void *item);
- static int eq_table (const void *lhs, const void *rhs);
-
struct search_key
{
struct dwarf2_section_info *section;
sect_offset offset;
};
+ struct abbrev_traits
+ {
+ typedef abbrev_table_up value_type;
+
+ static bool is_empty (const value_type &val)
+ { return val == nullptr; }
+
+ static bool equals (const value_type &lhs, const value_type &rhs)
+ {
+ return lhs->section == rhs->section && lhs->sect_off == rhs->sect_off;
+ }
+
+ static bool equals (const value_type &lhs, const search_key &rhs)
+ {
+ return lhs->section == rhs.section && lhs->sect_off == rhs.offset;
+ }
+
+ static size_t hash (const value_type &val)
+ {
+ return to_underlying (val->sect_off);
+ }
+ };
+
/* Hash table of abbrev tables. */
- htab_up m_tables;
+ gdb::traited_hash_table<abbrev_traits> m_tables;
};
#endif /* GDB_DWARF2_ABBREV_CACHE_H */
--
2.39.2
^ permalink raw reply [flat|nested] 29+ messages in thread* [PATCH 15/19] Convert abbrevs to new hash table
2023-04-07 15:25 [PATCH 00/19] Add hash table to gdbsupport Tom Tromey
` (13 preceding siblings ...)
2023-04-07 15:25 ` [PATCH 14/19] Convert abbrev cache " Tom Tromey
@ 2023-04-07 15:25 ` Tom Tromey
2023-04-07 15:25 ` [PATCH 16/19] Convert typedef hash " Tom Tromey
` (5 subsequent siblings)
20 siblings, 0 replies; 29+ messages in thread
From: Tom Tromey @ 2023-04-07 15:25 UTC (permalink / raw)
To: gdb-patches
This converts the DWARF abbrevs themselves to use the new hash table.
---
gdb/dwarf2/abbrev.c | 46 ---------------------------------------------
gdb/dwarf2/abbrev.h | 54 +++++++++++++++++++++++++++++++++++++++++++----------
2 files changed, 44 insertions(+), 56 deletions(-)
diff --git a/gdb/dwarf2/abbrev.c b/gdb/dwarf2/abbrev.c
index 1ebf8f6eed5..e82824033d4 100644
--- a/gdb/dwarf2/abbrev.c
+++ b/gdb/dwarf2/abbrev.c
@@ -30,52 +30,6 @@
#include "dwarf2/leb.h"
#include "bfd.h"
-/* Hash function for an abbrev. */
-
-static hashval_t
-hash_abbrev (const void *item)
-{
- const struct abbrev_info *info = (const struct abbrev_info *) item;
- /* Warning: if you change this next line, you must also update the
- other code in this class using the _with_hash functions. */
- return info->number;
-}
-
-/* Comparison function for abbrevs. */
-
-static int
-eq_abbrev (const void *lhs, const void *rhs)
-{
- const struct abbrev_info *l_info = (const struct abbrev_info *) lhs;
- const struct abbrev_info *r_info = (const struct abbrev_info *) rhs;
- return l_info->number == r_info->number;
-}
-
-/* Abbreviation tables.
-
- In DWARF version 2, the description of the debugging information is
- stored in a separate .debug_abbrev section. Before we read any
- dies from a section we read in all abbreviations and install them
- in a hash table. */
-
-abbrev_table::abbrev_table (sect_offset off, struct dwarf2_section_info *sect)
- : sect_off (off),
- section (sect),
- m_abbrevs (htab_create_alloc (20, hash_abbrev, eq_abbrev,
- nullptr, xcalloc, xfree))
-{
-}
-
-/* Add an abbreviation to the table. */
-
-void
-abbrev_table::add_abbrev (struct abbrev_info *abbrev)
-{
- void **slot = htab_find_slot_with_hash (m_abbrevs.get (), abbrev,
- abbrev->number, INSERT);
- *slot = abbrev;
-}
-
/* Helper function that returns true if a DIE with the given tag might
plausibly be indexed. */
diff --git a/gdb/dwarf2/abbrev.h b/gdb/dwarf2/abbrev.h
index 00cfbacf2d0..44750d7eb87 100644
--- a/gdb/dwarf2/abbrev.h
+++ b/gdb/dwarf2/abbrev.h
@@ -60,7 +60,12 @@ struct abbrev_info
struct abbrev_table;
typedef std::unique_ptr<struct abbrev_table> abbrev_table_up;
-/* Top level data structure to contain an abbreviation table. */
+/* Top level data structure to contain an abbreviation table.
+
+ In DWARF version 2, the description of the debugging information is
+ stored in a separate .debug_abbrev section. Before we read any
+ dies from a section we read in all abbreviations and install them
+ in a hash table. */
struct abbrev_table
{
@@ -76,12 +81,10 @@ struct abbrev_table
const struct abbrev_info *lookup_abbrev (unsigned int abbrev_number) const
{
- struct abbrev_info search;
- search.number = abbrev_number;
-
- return (struct abbrev_info *) htab_find_with_hash (m_abbrevs.get (),
- &search,
- abbrev_number);
+ auto iter = m_abbrevs.find (abbrev_number, abbrev_number);
+ if (iter == m_abbrevs.end ())
+ return nullptr;
+ return *iter;
}
/* Where the abbrev table came from.
@@ -92,15 +95,46 @@ struct abbrev_table
private:
- abbrev_table (sect_offset off, struct dwarf2_section_info *sect);
+ abbrev_table (sect_offset off, struct dwarf2_section_info *sect)
+ : sect_off (off),
+ section (sect)
+ {
+ }
DISABLE_COPY_AND_ASSIGN (abbrev_table);
/* Add an abbreviation to the table. */
- void add_abbrev (struct abbrev_info *abbrev);
+ void add_abbrev (struct abbrev_info *abbrev)
+ { m_abbrevs.insert (abbrev); }
+
+ struct abbrev_traits
+ {
+ typedef abbrev_info *value_type;
+
+ static bool is_empty (const value_type &val)
+ { return val == nullptr; }
+
+ static bool equals (const value_type &lhs, const value_type &rhs)
+ {
+ return lhs->number == rhs->number;
+ }
+
+ static bool equals (const value_type &lhs, unsigned int rhs)
+ {
+ return lhs->number == rhs;
+ }
+
+ static size_t hash (const value_type &val)
+ {
+ /* Warning: if you change this next line, you must also update
+ the other code in this class that computes the hash by
+ hand.. */
+ return val->number;
+ }
+ };
/* Hash table of abbrevs. */
- htab_up m_abbrevs;
+ gdb::traited_hash_table<abbrev_traits> m_abbrevs;
/* Storage for the abbrev table. */
auto_obstack m_abbrev_obstack;
--
2.39.2
^ permalink raw reply [flat|nested] 29+ messages in thread* [PATCH 16/19] Convert typedef hash to new hash table
2023-04-07 15:25 [PATCH 00/19] Add hash table to gdbsupport Tom Tromey
` (14 preceding siblings ...)
2023-04-07 15:25 ` [PATCH 15/19] Convert abbrevs " Tom Tromey
@ 2023-04-07 15:25 ` Tom Tromey
2023-04-07 15:25 ` [PATCH 17/19] Convert all_bfds " Tom Tromey
` (4 subsequent siblings)
20 siblings, 0 replies; 29+ messages in thread
From: Tom Tromey @ 2023-04-07 15:25 UTC (permalink / raw)
To: gdb-patches
This converts the typedef hash to use the new hash table.
This patch found a latent bug in the typedef code. Previously, the
hash function looked at the type name, but the hash equality function
used types_equal -- but that strips typedefs, meaning that equality of
types did not imply equality of hashes. This patch fixes the problem
and updates the relevant test.
---
gdb/testsuite/gdb.cp/ptype-flags.exp | 25 +++++++---
gdb/typeprint.c | 89 ++++--------------------------------
gdb/typeprint.h | 29 ++++++++++--
3 files changed, 55 insertions(+), 88 deletions(-)
diff --git a/gdb/testsuite/gdb.cp/ptype-flags.exp b/gdb/testsuite/gdb.cp/ptype-flags.exp
index 71018556840..7d9b2d54ac6 100644
--- a/gdb/testsuite/gdb.cp/ptype-flags.exp
+++ b/gdb/testsuite/gdb.cp/ptype-flags.exp
@@ -78,10 +78,18 @@ proc do_check_holder {name {flags ""} {show_typedefs 1} {show_methods 1}
proc do_check_typedef_holder {name {flags ""} {show_typedefs 1} {show_methods 1}
{raw 0}} {
- set contents {
- { field public "double a;" }
- { field public "ns::scoped_double b;" }
- { field public "global_double c;" }
+ if {$raw} {
+ set contents {
+ { field public "double a;" }
+ { field public "ns::scoped_double b;" }
+ { field public "global_double c;" }
+ }
+ } else {
+ set contents {
+ { field public "class_double a;" }
+ { field public "class_double b;" }
+ { field public "class_double c;" }
+ }
}
if {$show_typedefs} {
@@ -89,8 +97,13 @@ proc do_check_typedef_holder {name {flags ""} {show_typedefs 1} {show_methods 1}
}
if {$show_methods} {
- lappend contents { method private "double method1(ns::scoped_double);" }
- lappend contents { method private "double method2(global_double);" }
+ if {$raw} {
+ lappend contents { method private "double method1(ns::scoped_double);" }
+ lappend contents { method private "double method2(global_double);" }
+ } else {
+ lappend contents { method private "class_double method1(class_double);" }
+ lappend contents { method private "class_double method2(class_double);" }
+ }
}
if {$raw} {
diff --git a/gdb/typeprint.c b/gdb/typeprint.c
index 06ecd2c4776..b4712460c19 100644
--- a/gdb/typeprint.c
+++ b/gdb/typeprint.c
@@ -195,27 +195,6 @@ print_offset_data::finish (struct type *type, int level,
\f
-/* A hash function for a typedef_field. */
-
-static hashval_t
-hash_typedef_field (const void *p)
-{
- const struct decl_field *tf = (const struct decl_field *) p;
-
- return htab_hash_string (TYPE_SAFE_NAME (tf->type));
-}
-
-/* An equality function for a typedef field. */
-
-static int
-eq_typedef_field (const void *a, const void *b)
-{
- const struct decl_field *tfa = (const struct decl_field *) a;
- const struct decl_field *tfb = (const struct decl_field *) b;
-
- return types_equal (tfa->type, tfb->type);
-}
-
/* See typeprint.h. */
void
@@ -226,14 +205,7 @@ typedef_hash_table::recursively_update (struct type *t)
for (i = 0; i < TYPE_TYPEDEF_FIELD_COUNT (t); ++i)
{
struct decl_field *tdef = &TYPE_TYPEDEF_FIELD (t, i);
- void **slot;
-
- slot = htab_find_slot (m_table.get (), tdef, INSERT);
- /* Only add a given typedef name once. Really this shouldn't
- happen; but it is safe enough to do the updates breadth-first
- and thus use the most specific typedef. */
- if (*slot == NULL)
- *slot = tdef;
+ m_table.insert (tdef);
}
/* Recurse into superclasses. */
@@ -251,7 +223,6 @@ typedef_hash_table::add_template_parameters (struct type *t)
for (i = 0; i < TYPE_N_TEMPLATE_ARGUMENTS (t); ++i)
{
struct decl_field *tf;
- void **slot;
/* We only want type-valued template parameters in the hash. */
if (TYPE_TEMPLATE_ARGUMENT (t, i)->aclass () != LOC_TYPEDEF)
@@ -261,45 +232,10 @@ typedef_hash_table::add_template_parameters (struct type *t)
tf->name = TYPE_TEMPLATE_ARGUMENT (t, i)->linkage_name ();
tf->type = TYPE_TEMPLATE_ARGUMENT (t, i)->type ();
- slot = htab_find_slot (m_table.get (), tf, INSERT);
- if (*slot == NULL)
- *slot = tf;
+ m_table.insert (tf);
}
}
-/* See typeprint.h. */
-
-typedef_hash_table::typedef_hash_table ()
- : m_table (htab_create_alloc (10, hash_typedef_field, eq_typedef_field,
- NULL, xcalloc, xfree))
-{
-}
-
-/* Helper function for typedef_hash_table::copy. */
-
-static int
-copy_typedef_hash_element (void **slot, void *nt)
-{
- htab_t new_table = (htab_t) nt;
- void **new_slot;
-
- new_slot = htab_find_slot (new_table, *slot, INSERT);
- if (*new_slot == NULL)
- *new_slot = *slot;
-
- return 1;
-}
-
-/* See typeprint.h. */
-
-typedef_hash_table::typedef_hash_table (const typedef_hash_table &table)
-{
- m_table.reset (htab_create_alloc (10, hash_typedef_field, eq_typedef_field,
- NULL, xcalloc, xfree));
- htab_traverse_noresize (table.m_table.get (), copy_typedef_hash_element,
- m_table.get ());
-}
-
/* Look up the type T in the global typedef hash. If it is found,
return the typedef name. If it is not found, apply the
type-printers, if any, given by start_script_type_printers and return the
@@ -309,7 +245,6 @@ const char *
typedef_hash_table::find_global_typedef (const struct type_print_options *flags,
struct type *t)
{
- void **slot;
struct decl_field tf, *new_tf;
if (flags->global_typedefs == NULL)
@@ -318,12 +253,9 @@ typedef_hash_table::find_global_typedef (const struct type_print_options *flags,
tf.name = NULL;
tf.type = t;
- slot = htab_find_slot (flags->global_typedefs->m_table.get (), &tf, INSERT);
- if (*slot != NULL)
- {
- new_tf = (struct decl_field *) *slot;
- return new_tf->name;
- }
+ auto insert_pair = flags->global_typedefs->m_table.insert (&tf);
+ if (!insert_pair.second)
+ return (*insert_pair.first)->name;
/* Put an entry into the hash table now, in case
apply_ext_lang_type_printers recurses. */
@@ -331,7 +263,7 @@ typedef_hash_table::find_global_typedef (const struct type_print_options *flags,
new_tf->name = NULL;
new_tf->type = t;
- *slot = new_tf;
+ *insert_pair.first = new_tf;
gdb::unique_xmalloc_ptr<char> applied
= apply_ext_lang_type_printers (flags->global_printers, t);
@@ -351,15 +283,14 @@ typedef_hash_table::find_typedef (const struct type_print_options *flags,
{
if (flags->local_typedefs != NULL)
{
- struct decl_field tf, *found;
+ struct decl_field tf;
tf.name = NULL;
tf.type = t;
- htab_t table = flags->local_typedefs->m_table.get ();
- found = (struct decl_field *) htab_find (table, &tf);
+ auto iter = flags->local_typedefs->m_table.find (&tf);
- if (found != NULL)
- return found->name;
+ if (iter != flags->local_typedefs->m_table.end ())
+ return (*iter)->name;
}
return find_global_typedef (flags, t);
diff --git a/gdb/typeprint.h b/gdb/typeprint.h
index aa1a5872ca3..9a664c4b281 100644
--- a/gdb/typeprint.h
+++ b/gdb/typeprint.h
@@ -20,6 +20,7 @@
#define TYPEPRINT_H
#include "gdbsupport/gdb_obstack.h"
+#include "gdbsupport/hash-table.h"
enum language;
struct ui_file;
@@ -123,10 +124,12 @@ class typedef_hash_table
public:
/* Create a new typedef-lookup hash table. */
- typedef_hash_table ();
+ typedef_hash_table () = default;
/* Copy a typedef hash. */
- typedef_hash_table (const typedef_hash_table &);
+ typedef_hash_table (const typedef_hash_table &other)
+ : m_table (other.m_table)
+ { }
typedef_hash_table &operator= (const typedef_hash_table &) = delete;
@@ -150,8 +153,28 @@ class typedef_hash_table
struct type *t);
+ /* Traits used for the hash table. */
+ struct decl_field_traits
+ {
+ typedef decl_field *value_type;
+
+ static bool is_empty (const value_type &val)
+ { return val == nullptr; }
+
+ static bool equals (const value_type &lhs, const value_type &rhs)
+ { return types_equal (lhs->type, rhs->type); }
+
+ static size_t hash (const value_type &val)
+ {
+ /* The hash must agree with equals, and types_equal strips
+ typedefs. */
+ struct type *type = check_typedef (val->type);
+ return htab_hash_string (TYPE_SAFE_NAME (type));
+ }
+ };
+
/* The actual hash table. */
- htab_up m_table;
+ gdb::traited_hash_table<decl_field_traits> m_table;
/* Storage for typedef_field objects that must be synthesized. */
auto_obstack m_storage;
--
2.39.2
^ permalink raw reply [flat|nested] 29+ messages in thread* [PATCH 17/19] Convert all_bfds to new hash table
2023-04-07 15:25 [PATCH 00/19] Add hash table to gdbsupport Tom Tromey
` (15 preceding siblings ...)
2023-04-07 15:25 ` [PATCH 16/19] Convert typedef hash " Tom Tromey
@ 2023-04-07 15:25 ` Tom Tromey
2023-04-07 15:25 ` [PATCH 18/19] Convert more DWARF code " Tom Tromey
` (3 subsequent siblings)
20 siblings, 0 replies; 29+ messages in thread
From: Tom Tromey @ 2023-04-07 15:25 UTC (permalink / raw)
To: gdb-patches
This converts gdb_bfd.c to use the new hash table for all_bfds.
This patch slightly changes the htab_t pretty-printer test, which was
relying on all_bfds. Note that with the new hash table, gdb-specific
printers aren't needed; the libstdc++ printers suffice -- in fact,
they are better, because the true types of the contents are available.
---
gdb/gdb_bfd.c | 45 ++++++++++++---------------------
gdb/testsuite/gdb.gdb/python-helper.exp | 3 ++-
2 files changed, 18 insertions(+), 30 deletions(-)
diff --git a/gdb/gdb_bfd.c b/gdb/gdb_bfd.c
index b05c78218ed..1c8c59cdb6e 100644
--- a/gdb/gdb_bfd.c
+++ b/gdb/gdb_bfd.c
@@ -34,6 +34,7 @@
#include "inferior.h"
#include "cli/cli-style.h"
#include <unordered_map>
+#include "gdbsupport/hash-table.h"
/* An object of this type is stored in the section's user data when
mapping a section. */
@@ -55,7 +56,7 @@ struct gdb_bfd_section_data
BFDs; in contrast, this hash is used just to implement
"maint info bfd". */
-static htab_t all_bfds;
+static gdb::hash_set<bfd *> all_bfds;
/* An object of this type is stored in each BFD's user data. */
@@ -469,7 +470,6 @@ static void
gdb_bfd_init_data (struct bfd *abfd, struct stat *st)
{
struct gdb_bfd_data *gdata;
- void **slot;
gdb_assert (bfd_usrdata (abfd) == nullptr);
@@ -480,9 +480,8 @@ gdb_bfd_init_data (struct bfd *abfd, struct stat *st)
bfd_set_usrdata (abfd, gdata);
/* This is the first we've seen it, so add it to the hash table. */
- slot = htab_find_slot (all_bfds, abfd, INSERT);
- gdb_assert (slot && !*slot);
- *slot = abfd;
+ auto insert_pair = all_bfds.insert (abfd);
+ gdb_assert (insert_pair.second);
}
/* See gdb_bfd.h. */
@@ -707,7 +706,7 @@ gdb_bfd_unref (struct bfd *abfd)
delete gdata;
bfd_set_usrdata (abfd, NULL); /* Paranoia. */
- htab_remove_elt (all_bfds, abfd);
+ all_bfds.erase (abfd);
gdb_bfd_close_or_warn (abfd);
@@ -1068,25 +1067,6 @@ gdb_bfd_errmsg (bfd_error_type error_tag, char **matching)
return ret;
}
-/* A callback for htab_traverse that prints a single BFD. */
-
-static int
-print_one_bfd (void **slot, void *data)
-{
- bfd *abfd = (struct bfd *) *slot;
- struct gdb_bfd_data *gdata = (struct gdb_bfd_data *) bfd_usrdata (abfd);
- struct ui_out *uiout = (struct ui_out *) data;
-
- ui_out_emit_tuple tuple_emitter (uiout, NULL);
- uiout->field_signed ("refcount", gdata->refc);
- uiout->field_string ("addr", host_address_to_string (abfd));
- uiout->field_string ("filename", bfd_get_filename (abfd),
- file_name_style.style ());
- uiout->text ("\n");
-
- return 1;
-}
-
/* Implement the 'maint info bfd' command. */
static void
@@ -1100,7 +1080,17 @@ maintenance_info_bfds (const char *arg, int from_tty)
uiout->table_header (40, ui_left, "filename", "Filename");
uiout->table_body ();
- htab_traverse (all_bfds, print_one_bfd, uiout);
+ for (bfd *abfd : all_bfds)
+ {
+ struct gdb_bfd_data *gdata = (struct gdb_bfd_data *) bfd_usrdata (abfd);
+
+ ui_out_emit_tuple tuple_emitter (uiout, nullptr);
+ uiout->field_signed ("refcount", gdata->refc);
+ uiout->field_string ("addr", host_address_to_string (abfd));
+ uiout->field_string ("filename", bfd_get_filename (abfd),
+ file_name_style.style ());
+ uiout->text ("\n");
+ }
}
/* BFD related per-inferior data. */
@@ -1170,9 +1160,6 @@ void _initialize_gdb_bfd ();
void
_initialize_gdb_bfd ()
{
- all_bfds = htab_create_alloc (10, htab_hash_pointer, htab_eq_pointer,
- NULL, xcalloc, xfree);
-
add_cmd ("bfds", class_maintenance, maintenance_info_bfds, _("\
List the BFDs that are currently open."),
&maintenanceinfolist);
diff --git a/gdb/testsuite/gdb.gdb/python-helper.exp b/gdb/testsuite/gdb.gdb/python-helper.exp
index a58e3b601df..9838e128b17 100644
--- a/gdb/testsuite/gdb.gdb/python-helper.exp
+++ b/gdb/testsuite/gdb.gdb/python-helper.exp
@@ -206,7 +206,8 @@ proc test_python_helper {} {
gdb_test -prompt $outer_prompt_re "print *type->main_type" $answer
# Test the htab_t pretty-printer.
- gdb_test -prompt $outer_prompt_re "print all_bfds" "htab_t with ${::decimal} elements = \\{${::hex}.*\\}"
+ gdb_test -prompt $outer_prompt_re "print varobj_table" \
+ "htab_t with ${::decimal} elements"
return 0
}
--
2.39.2
^ permalink raw reply [flat|nested] 29+ messages in thread* [PATCH 18/19] Convert more DWARF code to new hash table
2023-04-07 15:25 [PATCH 00/19] Add hash table to gdbsupport Tom Tromey
` (16 preceding siblings ...)
2023-04-07 15:25 ` [PATCH 17/19] Convert all_bfds " Tom Tromey
@ 2023-04-07 15:25 ` Tom Tromey
2023-04-07 15:25 ` [PATCH 19/19] Convert gdb_bfd.c " Tom Tromey
` (2 subsequent siblings)
20 siblings, 0 replies; 29+ messages in thread
From: Tom Tromey @ 2023-04-07 15:25 UTC (permalink / raw)
To: gdb-patches
This converts more code in the DWARF reader to use the new hash table.
---
gdb/dwarf2/cu.c | 50 +++++++++++---------------------------------------
gdb/dwarf2/cu.h | 10 ++++++----
gdb/dwarf2/read.c | 55 ++++++++++++++++++++++---------------------------------
3 files changed, 39 insertions(+), 76 deletions(-)
diff --git a/gdb/dwarf2/cu.c b/gdb/dwarf2/cu.c
index 89de40daab0..ef958d44d55 100644
--- a/gdb/dwarf2/cu.c
+++ b/gdb/dwarf2/cu.c
@@ -118,24 +118,6 @@ dwarf2_cu::addr_type () const
return addr_type;
}
-/* A hashtab traversal function that marks the dependent CUs. */
-
-static int
-dwarf2_mark_helper (void **slot, void *data)
-{
- dwarf2_per_cu_data *per_cu = (dwarf2_per_cu_data *) *slot;
- dwarf2_per_objfile *per_objfile = (dwarf2_per_objfile *) data;
- dwarf2_cu *cu = per_objfile->get_cu (per_cu);
-
- /* cu->m_dependencies references may not yet have been ever read if
- QUIT aborts reading of the chain. As such dependencies remain
- valid it is not much useful to track and undo them during QUIT
- cleanups. */
- if (cu != nullptr)
- cu->mark ();
- return 1;
-}
-
/* See dwarf2/cu.h. */
void
@@ -144,32 +126,22 @@ dwarf2_cu::mark ()
if (!m_mark)
{
m_mark = true;
- if (m_dependencies != nullptr)
- htab_traverse (m_dependencies, dwarf2_mark_helper, per_objfile);
+ for (dwarf2_per_cu_data *per_cu : m_dependencies)
+ {
+ dwarf2_cu *cu = per_objfile->get_cu (per_cu);
+
+ /* cu->m_dependencies references may not yet have been ever
+ read if QUIT aborts reading of the chain. As such
+ dependencies remain valid it is not much useful to track
+ and undo them during QUIT cleanups. */
+ if (cu != nullptr)
+ cu->mark ();
+ }
}
}
/* See dwarf2/cu.h. */
-void
-dwarf2_cu::add_dependence (struct dwarf2_per_cu_data *ref_per_cu)
-{
- void **slot;
-
- if (m_dependencies == nullptr)
- m_dependencies
- = htab_create_alloc_ex (5, htab_hash_pointer, htab_eq_pointer,
- NULL, &comp_unit_obstack,
- hashtab_obstack_allocate,
- dummy_obstack_deallocate);
-
- slot = htab_find_slot (m_dependencies, ref_per_cu, INSERT);
- if (*slot == nullptr)
- *slot = ref_per_cu;
-}
-
-/* See dwarf2/cu.h. */
-
buildsym_compunit *
dwarf2_cu::get_builder ()
{
diff --git a/gdb/dwarf2/cu.h b/gdb/dwarf2/cu.h
index 8059b70f721..b321365149c 100644
--- a/gdb/dwarf2/cu.h
+++ b/gdb/dwarf2/cu.h
@@ -24,6 +24,7 @@
#include "dwarf2/comp-unit-head.h"
#include "gdbsupport/gdb_optional.h"
#include "language.h"
+#include "gdbsupport/hash-table.h"
/* Type used for delaying computation of method physnames.
See comments for compute_delayed_physnames. */
@@ -95,7 +96,8 @@ struct dwarf2_cu
}
/* Add a dependence relationship from this cu to REF_PER_CU. */
- void add_dependence (struct dwarf2_per_cu_data *ref_per_cu);
+ void add_dependence (struct dwarf2_per_cu_data *ref_per_cu)
+ { m_dependencies.insert (ref_per_cu); }
/* The header of the compilation unit. */
struct comp_unit_head header;
@@ -120,9 +122,9 @@ struct dwarf2_cu
std::unique_ptr<buildsym_compunit> m_builder;
/* A set of pointers to dwarf2_per_cu_data objects for compilation
- units referenced by this one. Only set during full symbol processing;
- partial symbol tables do not have dependencies. */
- htab_t m_dependencies = nullptr;
+ units referenced by this one. Only used during full symbol
+ processing; partial symbol tables do not have dependencies. */
+ gdb::hash_set<dwarf2_per_cu_data *> m_dependencies;
public:
/* The generic symbol table building routines have separate lists for
diff --git a/gdb/dwarf2/read.c b/gdb/dwarf2/read.c
index 8f35b973f3e..e3b6a86a811 100644
--- a/gdb/dwarf2/read.c
+++ b/gdb/dwarf2/read.c
@@ -95,6 +95,7 @@
#include "split-name.h"
#include "gdbsupport/parallel-for.h"
#include "gdbsupport/thread-pool.h"
+#include "gdbsupport/hash-table.h"
/* When == 1, print basic high level tracing messages.
When > 1, be more verbose.
@@ -3033,12 +3034,8 @@ dw_expand_symtabs_matching_file_matcher
if (file_matcher == NULL)
return;
- 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));
+ gdb::hash_set<quick_file_names *> visited_found;
+ gdb::hash_set<quick_file_names *> visited_not_found;
/* The rule is CUs specify all the files, including those used by
any TU, so there's no need to scan TUs here. */
@@ -3081,9 +3078,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.contains (file_data))
continue;
- else if (htab_find (visited_found.get (), file_data) != NULL)
+ else if (visited_found.contains (file_data))
{
per_cu->mark = 1;
continue;
@@ -3114,11 +3111,10 @@ dw_expand_symtabs_matching_file_matcher
}
}
- void **slot = htab_find_slot (per_cu->mark
- ? visited_found.get ()
- : visited_not_found.get (),
- file_data, INSERT);
- *slot = file_data;
+ if (per_cu->mark)
+ visited_found.insert (file_data);
+ else
+ visited_not_found.insert (file_data);
}
}
@@ -6249,21 +6245,20 @@ void dwarf2_per_objfile::set_type_for_signatured_type
included by PER_CU. */
static void
-recursively_compute_inclusions (std::vector<compunit_symtab *> *result,
- htab_t all_children, htab_t all_type_symtabs,
- dwarf2_per_cu_data *per_cu,
- dwarf2_per_objfile *per_objfile,
- struct compunit_symtab *immediate_parent)
+recursively_compute_inclusions
+ (std::vector<compunit_symtab *> *result,
+ gdb::hash_set<dwarf2_per_cu_data *> &all_children,
+ gdb::hash_set<compunit_symtab *> &all_type_symtabs,
+ dwarf2_per_cu_data *per_cu,
+ dwarf2_per_objfile *per_objfile,
+ struct compunit_symtab *immediate_parent)
{
- void **slot = htab_find_slot (all_children, per_cu, INSERT);
- if (*slot != NULL)
+ if (!all_children.insert (per_cu).second)
{
/* This inclusion and its children have been processed. */
return;
}
- *slot = per_cu;
-
/* Only add a CU if it has a symbol table. */
compunit_symtab *cust = per_objfile->get_symtab (per_cu);
if (cust != NULL)
@@ -6272,10 +6267,8 @@ recursively_compute_inclusions (std::vector<compunit_symtab *> *result,
seen it yet (type unit per_cu's can share symtabs). */
if (per_cu->is_debug_types)
{
- slot = htab_find_slot (all_type_symtabs, cust, INSERT);
- if (*slot == NULL)
+ if (all_type_symtabs.insert (cust).second)
{
- *slot = cust;
result->push_back (cust);
if (cust->user == NULL)
cust->user = immediate_parent;
@@ -6317,17 +6310,13 @@ compute_compunit_symtab_includes (dwarf2_per_cu_data *per_cu,
if (cust == NULL)
return;
- htab_up all_children (htab_create_alloc (1, htab_hash_pointer,
- htab_eq_pointer,
- NULL, xcalloc, xfree));
- htab_up all_type_symtabs (htab_create_alloc (1, htab_hash_pointer,
- htab_eq_pointer,
- NULL, xcalloc, xfree));
+ gdb::hash_set<dwarf2_per_cu_data *> all_children;
+ gdb::hash_set<compunit_symtab *> all_type_symtabs;
for (dwarf2_per_cu_data *ptr : *per_cu->imported_symtabs)
{
- recursively_compute_inclusions (&result_symtabs, all_children.get (),
- all_type_symtabs.get (), ptr,
+ recursively_compute_inclusions (&result_symtabs, all_children,
+ all_type_symtabs, ptr,
per_objfile, cust);
}
--
2.39.2
^ permalink raw reply [flat|nested] 29+ messages in thread* [PATCH 19/19] Convert gdb_bfd.c to new hash table
2023-04-07 15:25 [PATCH 00/19] Add hash table to gdbsupport Tom Tromey
` (17 preceding siblings ...)
2023-04-07 15:25 ` [PATCH 18/19] Convert more DWARF code " Tom Tromey
@ 2023-04-07 15:25 ` Tom Tromey
2023-04-10 19:45 ` [PATCH 00/19] Add hash table to gdbsupport John Baldwin
2023-12-08 18:28 ` Tom Tromey
20 siblings, 0 replies; 29+ messages in thread
From: Tom Tromey @ 2023-04-07 15:25 UTC (permalink / raw)
To: gdb-patches
This converts the BFD cache in gdb_bfd.c to use the new hash table.
---
gdb/gdb_bfd.c | 92 +++++++++++++++++++++--------------------------------------
1 file changed, 33 insertions(+), 59 deletions(-)
diff --git a/gdb/gdb_bfd.c b/gdb/gdb_bfd.c
index 1c8c59cdb6e..8c93e7cd8f1 100644
--- a/gdb/gdb_bfd.c
+++ b/gdb/gdb_bfd.c
@@ -124,10 +124,6 @@ registry_accessor<bfd>::get (bfd *abfd)
return &gdata->registry_fields;
}
-/* A hash table storing all the BFDs maintained in the cache. */
-
-static htab_t gdb_bfd_cache;
-
/* When true gdb will reuse an existing bfd object if the filename,
modification time, and file size all match. */
@@ -173,34 +169,38 @@ struct gdb_bfd_cache_search
dev_t device_id;
};
-/* A hash function for BFDs. */
+/* Traits for the BFD cache hash table. */
-static hashval_t
-hash_bfd (const void *b)
+struct gdb_bfd_cache_traits
{
- const bfd *abfd = (const struct bfd *) b;
+ typedef bfd *value_type;
- /* It is simplest to just hash the filename. */
- return htab_hash_string (bfd_get_filename (abfd));
-}
+ static bool is_empty (const bfd *val)
+ { return val == nullptr; }
-/* An equality function for BFDs. Note that this expects the caller
- to search using struct gdb_bfd_cache_search only, not BFDs. */
+ static size_t hash (const bfd *abfd)
+ { return htab_hash_string (bfd_get_filename (abfd)); }
-static int
-eq_bfd (const void *a, const void *b)
-{
- const bfd *abfd = (const struct bfd *) a;
- const struct gdb_bfd_cache_search *s
- = (const struct gdb_bfd_cache_search *) b;
- struct gdb_bfd_data *gdata = (struct gdb_bfd_data *) bfd_usrdata (abfd);
+ static size_t hash (const gdb_bfd_cache_search &val)
+ { return htab_hash_string (val.filename); }
- return (gdata->mtime == s->mtime
- && gdata->size == s->size
- && gdata->inode == s->inode
- && gdata->device_id == s->device_id
- && strcmp (bfd_get_filename (abfd), s->filename) == 0);
-}
+ static bool equals (const bfd *a, const bfd *b)
+ { return a == b; }
+
+ static bool equals (const bfd *abfd, const gdb_bfd_cache_search &s)
+ {
+ struct gdb_bfd_data *gdata = (struct gdb_bfd_data *) bfd_usrdata (abfd);
+ return (gdata->mtime == s.mtime
+ && gdata->size == s.size
+ && gdata->inode == s.inode
+ && gdata->device_id == s.device_id
+ && strcmp (bfd_get_filename (abfd), s.filename) == 0);
+ }
+};
+
+/* A hash table storing all the BFDs maintained in the cache. */
+
+static gdb::traited_hash_table<gdb_bfd_cache_traits> gdb_bfd_cache;
/* See gdb_bfd.h. */
@@ -490,8 +490,6 @@ gdb_bfd_ref_ptr
gdb_bfd_open (const char *name, const char *target, int fd,
bool warn_if_slow)
{
- hashval_t hash;
- void **slot;
bfd *abfd;
struct gdb_bfd_cache_search search;
struct stat st;
@@ -514,10 +512,6 @@ gdb_bfd_open (const char *name, const char *target, int fd,
name += strlen (TARGET_SYSROOT_PREFIX);
}
- if (gdb_bfd_cache == NULL)
- gdb_bfd_cache = htab_create_alloc (1, hash_bfd, eq_bfd, NULL,
- xcalloc, xfree);
-
if (fd == -1)
{
fd = gdb_open_cloexec (name, O_RDONLY | O_BINARY, 0).release ();
@@ -544,14 +538,10 @@ gdb_bfd_open (const char *name, const char *target, int fd,
search.inode = st.st_ino;
search.device_id = st.st_dev;
- /* Note that this must compute the same result as hash_bfd. */
- hash = htab_hash_string (name);
- /* Note that we cannot use htab_find_slot_with_hash here, because
- opening the BFD may fail; and this would violate hashtab
- invariants. */
- abfd = (struct bfd *) htab_find_with_hash (gdb_bfd_cache, &search, hash);
- if (bfd_sharing && abfd != NULL)
+ auto iter = gdb_bfd_cache.find (search);
+ if (bfd_sharing && iter != gdb_bfd_cache.end ())
{
+ abfd = *iter;
bfd_cache_debug_printf ("Reusing cached bfd %s for %s",
host_address_to_string (abfd),
bfd_get_filename (abfd));
@@ -569,9 +559,8 @@ gdb_bfd_open (const char *name, const char *target, int fd,
if (bfd_sharing)
{
- slot = htab_find_slot_with_hash (gdb_bfd_cache, &search, hash, INSERT);
- gdb_assert (!*slot);
- *slot = abfd;
+ auto insert_pair = gdb_bfd_cache.insert (abfd);
+ gdb_assert (insert_pair.second);
}
/* It's important to pass the already-computed stat info here,
@@ -662,7 +651,6 @@ void
gdb_bfd_unref (struct bfd *abfd)
{
struct gdb_bfd_data *gdata;
- struct gdb_bfd_cache_search search;
bfd *archive_bfd;
if (abfd == NULL)
@@ -685,23 +673,9 @@ gdb_bfd_unref (struct bfd *abfd)
bfd_get_filename (abfd));
archive_bfd = gdata->archive_bfd;
- search.filename = bfd_get_filename (abfd);
- if (gdb_bfd_cache && search.filename)
- {
- hashval_t hash = htab_hash_string (search.filename);
- void **slot;
-
- search.mtime = gdata->mtime;
- search.size = gdata->size;
- search.inode = gdata->inode;
- search.device_id = gdata->device_id;
- slot = htab_find_slot_with_hash (gdb_bfd_cache, &search, hash,
- NO_INSERT);
-
- if (slot && *slot)
- htab_clear_slot (gdb_bfd_cache, slot);
- }
+ if (bfd_get_filename (abfd) != nullptr)
+ gdb_bfd_cache.erase (abfd);
delete gdata;
bfd_set_usrdata (abfd, NULL); /* Paranoia. */
--
2.39.2
^ permalink raw reply [flat|nested] 29+ messages in thread* Re: [PATCH 00/19] Add hash table to gdbsupport
2023-04-07 15:25 [PATCH 00/19] Add hash table to gdbsupport Tom Tromey
` (18 preceding siblings ...)
2023-04-07 15:25 ` [PATCH 19/19] Convert gdb_bfd.c " Tom Tromey
@ 2023-04-10 19:45 ` John Baldwin
2023-11-03 18:54 ` Tom Tromey
2023-12-08 18:28 ` Tom Tromey
20 siblings, 1 reply; 29+ messages in thread
From: John Baldwin @ 2023-04-10 19:45 UTC (permalink / raw)
To: Tom Tromey, gdb-patches
On 4/7/23 8:25 AM, Tom Tromey wrote:
> I recently read an article about hash tables and was inspired to write
> a new one for gdb. I haven't converted all the libiberty htab uses in
> gdb, but this series does change enough of them to, I think, show that
> the new implementation is workable.
>
> The benefits of this approach are explained in the first patch.
>
> Regression tested on x86-64 Fedora 36. This found a latent bug in one
> use of htab_t, see the typedefs patch.
>
> Let me know what you think.
I just have one possibly naive question which is why not use
std::unordered_map<> directly in the various callers? At least, I think
it might be useful to explain why GDB includes a bespoke hash table now
that we require C++11, it was more obvious I think when GDB was still
written in C.
--
John Baldwin
^ permalink raw reply [flat|nested] 29+ messages in thread* Re: [PATCH 00/19] Add hash table to gdbsupport
2023-04-10 19:45 ` [PATCH 00/19] Add hash table to gdbsupport John Baldwin
@ 2023-11-03 18:54 ` Tom Tromey
0 siblings, 0 replies; 29+ messages in thread
From: Tom Tromey @ 2023-11-03 18:54 UTC (permalink / raw)
To: John Baldwin; +Cc: Tom Tromey, gdb-patches
>>>>> "John" == John Baldwin <jhb@FreeBSD.org> writes:
John> On 4/7/23 8:25 AM, Tom Tromey wrote:
>> I recently read an article about hash tables and was inspired to write
>> a new one for gdb. I haven't converted all the libiberty htab uses in
>> gdb, but this series does change enough of them to, I think, show that
>> the new implementation is workable.
>> The benefits of this approach are explained in the first patch.
>> Regression tested on x86-64 Fedora 36. This found a latent bug in
>> one
>> use of htab_t, see the typedefs patch.
>> Let me know what you think.
John> I just have one possibly naive question which is why not use
John> std::unordered_map<> directly in the various callers? At least, I think
John> it might be useful to explain why GDB includes a bespoke hash table now
John> that we require C++11, it was more obvious I think when GDB was still
John> written in C.
std::unordered_map has some issues. They may not affect every spot
using hash tables in gdb, but they probably affect some of them.
unordered_map is necessarily a chained hash table, not an open addressed
hash table. And, it has to allocate nodes for entries, because it
promises pointer stability. So, it has higher overhead than the hash
table in this series.
Also, I don't think there's a way to use one type as the key in
unordered_map but do lookups using a different type. gdb uses this in
some places.
I'll add some text to this effect to patch #1.
Tom
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [PATCH 00/19] Add hash table to gdbsupport
2023-04-07 15:25 [PATCH 00/19] Add hash table to gdbsupport Tom Tromey
` (19 preceding siblings ...)
2023-04-10 19:45 ` [PATCH 00/19] Add hash table to gdbsupport John Baldwin
@ 2023-12-08 18:28 ` Tom Tromey
2024-01-11 18:07 ` Tom Tromey
20 siblings, 1 reply; 29+ messages in thread
From: Tom Tromey @ 2023-12-08 18:28 UTC (permalink / raw)
To: Tom Tromey; +Cc: gdb-patches
>>>>> "Tom" == Tom Tromey <tom@tromey.com> writes:
Tom> I recently read an article about hash tables and was inspired to write
Tom> a new one for gdb. I haven't converted all the libiberty htab uses in
Tom> gdb, but this series does change enough of them to, I think, show that
Tom> the new implementation is workable.
Tom> The benefits of this approach are explained in the first patch.
Tom> Regression tested on x86-64 Fedora 36. This found a latent bug in one
Tom> use of htab_t, see the typedefs patch.
Tom> Let me know what you think.
I'd like to move forward with this.
I think most of the patches here are straightforward. The real question
is whether we want it. I've laid out my rationale in patch #1, with
some additions (explaining why this is better than unordered_map /
unordered_set) in a follow-up email.
Tom
^ permalink raw reply [flat|nested] 29+ messages in thread* Re: [PATCH 00/19] Add hash table to gdbsupport
2023-12-08 18:28 ` Tom Tromey
@ 2024-01-11 18:07 ` Tom Tromey
2024-01-11 19:35 ` John Baldwin
2024-01-12 2:57 ` Simon Marchi
0 siblings, 2 replies; 29+ messages in thread
From: Tom Tromey @ 2024-01-11 18:07 UTC (permalink / raw)
To: Tom Tromey; +Cc: gdb-patches
>>>>> "Tom" == Tom Tromey <tom@tromey.com> writes:
[ new hash table ]
Tom> I'd like to move forward with this.
Tom> I think most of the patches here are straightforward. The real question
Tom> is whether we want it. I've laid out my rationale in patch #1, with
Tom> some additions (explaining why this is better than unordered_map /
Tom> unordered_set) in a follow-up email.
I tried converting a few more libiberty hash tables to this one.
For a lot of things this is fine, big improvement, etc.
However, this hash table doesn't really admit the possibility that an
element might not have a natural sentinel value. This particularly
comes up with hash maps, where if you want a std::string->whatever map,
you have to introduce some kind of explicit sentinel (in my case I chose
empty string) and also then have to write a trait class.
So, this is one area where unordered_map has the advantage. Now, it
would be possible to handle this in some way. The hash table could
store a sentinel flag, for instance. Or, we could just accept this
drawback and use unordered_map when convenience is important.
Anyway, I tend to think it's not an enormous issue, but I figured I'd
point it out.
Tom
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [PATCH 00/19] Add hash table to gdbsupport
2024-01-11 18:07 ` Tom Tromey
@ 2024-01-11 19:35 ` John Baldwin
2024-01-12 2:57 ` Simon Marchi
1 sibling, 0 replies; 29+ messages in thread
From: John Baldwin @ 2024-01-11 19:35 UTC (permalink / raw)
To: Tom Tromey; +Cc: gdb-patches
On 1/11/24 10:07 AM, Tom Tromey wrote:
>>>>>> "Tom" == Tom Tromey <tom@tromey.com> writes:
>
> [ new hash table ]
>
> Tom> I'd like to move forward with this.
>
> Tom> I think most of the patches here are straightforward. The real question
> Tom> is whether we want it. I've laid out my rationale in patch #1, with
> Tom> some additions (explaining why this is better than unordered_map /
> Tom> unordered_set) in a follow-up email.
>
> I tried converting a few more libiberty hash tables to this one.
>
> For a lot of things this is fine, big improvement, etc.
>
> However, this hash table doesn't really admit the possibility that an
> element might not have a natural sentinel value. This particularly
> comes up with hash maps, where if you want a std::string->whatever map,
> you have to introduce some kind of explicit sentinel (in my case I chose
> empty string) and also then have to write a trait class.
>
> So, this is one area where unordered_map has the advantage. Now, it
> would be possible to handle this in some way. The hash table could
> store a sentinel flag, for instance. Or, we could just accept this
> drawback and use unordered_map when convenience is important.>
> Anyway, I tend to think it's not an enormous issue, but I figured I'd
> point it out.
This seems fine to me.
--
John Baldwin
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [PATCH 00/19] Add hash table to gdbsupport
2024-01-11 18:07 ` Tom Tromey
2024-01-11 19:35 ` John Baldwin
@ 2024-01-12 2:57 ` Simon Marchi
2024-01-12 18:22 ` Tom Tromey
1 sibling, 1 reply; 29+ messages in thread
From: Simon Marchi @ 2024-01-12 2:57 UTC (permalink / raw)
To: Tom Tromey; +Cc: gdb-patches
On 2024-01-11 13:07, Tom Tromey wrote:
>>>>>> "Tom" == Tom Tromey <tom@tromey.com> writes:
>
> [ new hash table ]
>
> Tom> I'd like to move forward with this.
>
> Tom> I think most of the patches here are straightforward. The real question
> Tom> is whether we want it. I've laid out my rationale in patch #1, with
> Tom> some additions (explaining why this is better than unordered_map /
> Tom> unordered_set) in a follow-up email.
>
> I tried converting a few more libiberty hash tables to this one.
>
> For a lot of things this is fine, big improvement, etc.
>
> However, this hash table doesn't really admit the possibility that an
> element might not have a natural sentinel value. This particularly
> comes up with hash maps, where if you want a std::string->whatever map,
> you have to introduce some kind of explicit sentinel (in my case I chose
> empty string) and also then have to write a trait class.
>
> So, this is one area where unordered_map has the advantage. Now, it
> would be possible to handle this in some way. The hash table could
> store a sentinel flag, for instance. Or, we could just accept this
> drawback and use unordered_map when convenience is important.
>
> Anyway, I tend to think it's not an enormous issue, but I figured I'd
> point it out.
>
> Tom
I spent a bit of time reading the interface of your hash table, and that
was a point I found unfortunate. The type V must have a default
constructor and an "empty" state (I guess that's what you mean by
sentinel), even if it doesn't make sense for the rest of the program.
How do other implementations (of open addessing hash tables) typically
deal with this? From what I recally, other implementations I have used
in the past didn't have this requirement.
And that makes me think that a question I did not see answered is: I
don't want to undermine your work, but what is the rationale for
implementing it ourselves? Efficient C++ hash maps is a topic that
comes up all the time on various programming news sites (I found this
recent blog post after a quick google search [1]), surely that's a
solved problem. Is there not a popular hash map library we can use
as-is?
Simon
[1] https://martin.ankerl.com/2022/08/27/hashmap-bench-01/
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [PATCH 00/19] Add hash table to gdbsupport
2024-01-12 2:57 ` Simon Marchi
@ 2024-01-12 18:22 ` Tom Tromey
2024-01-12 19:12 ` Simon Marchi
0 siblings, 1 reply; 29+ messages in thread
From: Tom Tromey @ 2024-01-12 18:22 UTC (permalink / raw)
To: Simon Marchi; +Cc: Tom Tromey, gdb-patches
Simon> I spent a bit of time reading the interface of your hash table, and that
Simon> was a point I found unfortunate. The type V must have a default
Simon> constructor and an "empty" state (I guess that's what you mean by
Simon> sentinel), even if it doesn't make sense for the rest of the program.
It's maybe worth noting that this is not a step backward from htab_t,
which only stores pointers.
Simon> How do other implementations (of open addessing hash tables) typically
Simon> deal with this? From what I recally, other implementations I have used
Simon> in the past didn't have this requirement.
I don't know in general. I looked at one and it uses a separate vector
of flag bytes to indicate which values are valid.
Simon> And that makes me think that a question I did not see answered is: I
Simon> don't want to undermine your work, but what is the rationale for
Simon> implementing it ourselves?
In my view, integrating an external C++ package like this is pain both
legally (at least, you have to find one with the appropriate license)
and technically. Even just trying to integrate the GCC hash table was a
pain. The typical problem, IMO, is that it's unusual to write a
standalone class like this, instead one introduces dependencies on a
variety of other things.
Tom
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [PATCH 00/19] Add hash table to gdbsupport
2024-01-12 18:22 ` Tom Tromey
@ 2024-01-12 19:12 ` Simon Marchi
0 siblings, 0 replies; 29+ messages in thread
From: Simon Marchi @ 2024-01-12 19:12 UTC (permalink / raw)
To: Tom Tromey; +Cc: gdb-patches
On 1/12/24 13:22, Tom Tromey wrote:
> Simon> I spent a bit of time reading the interface of your hash table, and that
> Simon> was a point I found unfortunate. The type V must have a default
> Simon> constructor and an "empty" state (I guess that's what you mean by
> Simon> sentinel), even if it doesn't make sense for the rest of the program.
>
> It's maybe worth noting that this is not a step backward from htab_t,
> which only stores pointers.
That's true, in the sense that you can still decide to store pointers in
the gdb::traited_hash_table. But if you want to change it so that it
stores objects directly (which I guess is an advantage because it's one
less indirection), then you have to introduce this new "invalid" or
"empty" state for objects for that class. It therefore removes the
guarantee you previously had for objects of that class to always be
valid, and it becomes possible for objects used elsewhere to be (by
mistake or not) in that new "empty" state. It's one more thing to
reason about, and some more potential pitfalls.
> Simon> How do other implementations (of open addessing hash tables) typically
> Simon> deal with this? From what I recally, other implementations I have used
> Simon> in the past didn't have this requirement.
>
> I don't know in general. I looked at one and it uses a separate vector
> of flag bytes to indicate which values are valid.
I looked at this one:
https://github.com/martinus/unordered_dense/tree/main
From what I understand, the underlying storage is a vector, and they
somehow make it so all vector elements are always occupied, there are
no empty slots.
> Simon> And that makes me think that a question I did not see answered is: I
> Simon> don't want to undermine your work, but what is the rationale for
> Simon> implementing it ourselves?
>
> In my view, integrating an external C++ package like this is pain both
> legally (at least, you have to find one with the appropriate license)
> and technically. Even just trying to integrate the GCC hash table was a
> pain. The typical problem, IMO, is that it's unusual to write a
> standalone class like this, instead one introduces dependencies on a
> variety of other things.
I did have some experiences (with folly notably) where trying to use one
data structure pulled in a bunch of files and it quickly became
unmanageable, but that was not the norm. But in my experience, most of
the time it's just one header file to copy over, with no dependency.
The one I linked above seems to be just that (I gave it a quick try in
GDB).
And the license being MIT, I don't think that's a problem. My
understanding is that it's permitted in this direction, and we use other
MIT-licensed stuff.
Simon
^ permalink raw reply [flat|nested] 29+ messages in thread