From patchwork Fri Apr 7 15:25:33 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom Tromey X-Patchwork-Id: 67504 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 435073856956 for ; Fri, 7 Apr 2023 15:26:40 +0000 (GMT) X-Original-To: gdb-patches@sourceware.org Delivered-To: gdb-patches@sourceware.org Received: from alt-proxy28.mail.unifiedlayer.com (alt-proxy28.mail.unifiedlayer.com [74.220.216.123]) by sourceware.org (Postfix) with ESMTPS id 6D7203858D33 for ; Fri, 7 Apr 2023 15:25:41 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 6D7203858D33 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=tromey.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=tromey.com Received: from cmgw13.mail.unifiedlayer.com (unknown [10.0.90.128]) by progateway1.mail.pro1.eigbox.com (Postfix) with ESMTP id D609A10040601 for ; Fri, 7 Apr 2023 15:25:40 +0000 (UTC) Received: from box5379.bluehost.com ([162.241.216.53]) by cmsmtp with ESMTP id kny8pNc0fNX2akny8p1QNK; Fri, 07 Apr 2023 15:25:40 +0000 X-Authority-Reason: nr=8 X-Authority-Analysis: v=2.4 cv=NMAQR22g c=1 sm=1 tr=0 ts=643035f4 a=ApxJNpeYhEAb1aAlGBBbmA==:117 a=ApxJNpeYhEAb1aAlGBBbmA==:17 a=dLZJa+xiwSxG16/P+YVxDGlgEgI=:19 a=IkcTkHD0fZMA:10:nop_charset_1 a=dKHAf1wccvYA:10:nop_rcvd_month_year a=Qbun_eYptAEA:10:endurance_base64_authed_username_1 a=mDV3o1hIAAAA:8 a=D6NO0QO3AAAA:8 a=WCsLRPAStWySxu04ousA:9 a=QEXdDO2ut3YA:10:nop_charset_2 a=_FVE-zBwftR9WsbkzFJk:22 a=_qBf4pV_onaRna5B3ALl:22 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tromey.com; s=default; h=To:In-Reply-To:References:Message-Id:Content-Transfer-Encoding: Content-Type:MIME-Version:Subject:Date:From:Sender:Reply-To:Cc:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=MRiZffcvlua2rHO0KBKEvS5HFmAyp+Jk4XodaVf353M=; b=FUuAhBGvBWVVRcyiDdqEE5ZECs rIgQBoJJhMKa5GVqZ8r+klLj47DnnJ23VABS2+3WKygRP4hlEuXrV1tdMQpmb7HSK8W9cuiS5fKVQ Z1O0dGquF698iLbJIByvjaWzU; Received: from 75-166-159-36.hlrn.qwest.net ([75.166.159.36]:60392 helo=[192.168.0.21]) by box5379.bluehost.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1pkny8-001hDU-IF for gdb-patches@sourceware.org; Fri, 07 Apr 2023 09:25:40 -0600 From: Tom Tromey Date: Fri, 07 Apr 2023 09:25:33 -0600 Subject: [PATCH 01/19] Add a hash table to gdbsupport MIME-Version: 1.0 Message-Id: <20230407-t-robin-hood-hash-v1-1-900d93ef1510@tromey.com> References: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> In-Reply-To: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> To: gdb-patches@sourceware.org X-Mailer: b4 0.12.1 X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - box5379.bluehost.com X-AntiAbuse: Original Domain - sourceware.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - tromey.com X-BWhitelist: no X-Source-IP: 75.166.159.36 X-Source-L: No X-Exim-ID: 1pkny8-001hDU-IF X-Source: X-Source-Args: X-Source-Dir: X-Source-Sender: 75-166-159-36.hlrn.qwest.net ([192.168.0.21]) [75.166.159.36]:60392 X-Source-Auth: tom+tromey.com X-Email-Count: 2 X-Source-Cap: ZWx5bnJvYmk7ZWx5bnJvYmk7Ym94NTM3OS5ibHVlaG9zdC5jb20= X-Local-Domain: yes X-Spam-Status: No, score=-3026.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, JMQ_SPF_NEUTRAL, KAM_SHORT, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gdb-patches-bounces+patchwork=sourceware.org@sourceware.org Sender: "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 . */ + +#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 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 expected { 4, 10, 3 }; + std::vector 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 { 4, 10 }; + actual = std::vector (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 { 6, 7, 13 }; + actual = std::vector (table.begin (), table.end ()); + SELF_CHECK (expected == actual); + + table.erase (6); + expected = std::vector { 13, 7 }; + actual = std::vector (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 . */ + +#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 . */ + +#ifndef GDBSUPPORT_HASH_TABLE_H +#define GDBSUPPORT_HASH_TABLE_H + +#include +#include + +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 +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 + 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 &) = default; + iterator_templ (iterator_templ &&) = default; + iterator_templ &operator= (const iterator_templ &) = default; + iterator_templ &operator= (iterator_templ &&) = default; + + V &operator* () + { + /* const_cast is used here to make sharing the implementation + between const and non-const simpler. */ + return const_cast (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 (&m_data[m_i - 1]); + } + + iterator_templ &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 &other) const + { + return m_i == other.m_i && &m_data == &other.m_data; + } + + bool operator!= (const iterator_templ &other) const + { return !(*this == other); } + + private: + + /* Only allow private construction. */ + friend class traited_hash_table; + + /* 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 &data) + : m_i (ndx), + m_data (data) + { } + + /* Create a 'begin' iterator. */ + explicit iterator_templ (const std::vector &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 &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 + iterator_templ 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 (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 (0, m_data); + if (Traits::equals (m_data[ndx], val)) + return iterator_templ (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 &) = default; + explicit traited_hash_table (traited_hash_table &&) = default; + traited_hash_table &operator= (const traited_hash_table &) + = default; + traited_hash_table &operator= (traited_hash_table &&) + = default; + + /* Iterator types. */ + typedef iterator_templ iterator; + typedef iterator_templ 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 + 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 + 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 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 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 + iterator find (const T &val, size_t hash) + { return find_impl (val, hash); } + + template + iterator find (const T &val) + { return find_impl (val, Traits::hash (val)); } + + template + const_iterator find (const T &val, size_t hash) const + { return find_impl (val, hash); } + + template + const_iterator find (const T &val) const + { return find_impl (val, Traits::hash (val)); } + + /* Return true if the hash table contains VAL, or false if not. */ + template + 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 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 m_data; +}; + + +/* A typical traits implementation for a type. This uses the standard + hash function and the standard equality function. */ +template +struct typical_hash_traits +{ + using value_type = T; + + template + 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 () (val); } +}; + +/* A hash set that stores elements of a type T. */ +template +using hash_set = traited_hash_table>; + +/* 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 +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 +struct hash_map_traits +{ + /* A convenience typedef for the key type. */ + typedef typename Traits::value_type key_type; + + typedef std::pair 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. */ +template +class traited_hash_map + : public traited_hash_table> +{ + using trait_type = hash_map_traits; + using super_type = traited_hash_table; + 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 insert (const key_type &key, + const Value &value) + { return super_type::insert (std::pair (key, value)); } +}; + +/* An easy-to-instantiate hash map that uses the "typical" hash traits + for the key. */ +template +using hash_map = traited_hash_map, Value>; + +} /* namespace gdb */ + +#endif /* GDBSUPPORT_HASH_TABLE_H */ From patchwork Fri Apr 7 15:25:34 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom Tromey X-Patchwork-Id: 67499 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 6960A3858438 for ; Fri, 7 Apr 2023 15:26:03 +0000 (GMT) X-Original-To: gdb-patches@sourceware.org Delivered-To: gdb-patches@sourceware.org Received: from gproxy4-pub.mail.unifiedlayer.com (gproxy4-pub.mail.unifiedlayer.com [69.89.23.142]) by sourceware.org (Postfix) with ESMTPS id D65243858CDA for ; Fri, 7 Apr 2023 15:25:41 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org D65243858CDA Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=tromey.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=tromey.com Received: from cmgw15.mail.unifiedlayer.com (unknown [10.0.90.130]) by progateway6.mail.pro1.eigbox.com (Postfix) with ESMTP id 0071B1004954D for ; Fri, 7 Apr 2023 15:25:41 +0000 (UTC) Received: from box5379.bluehost.com ([162.241.216.53]) by cmsmtp with ESMTP id kny8pyJzQyk8zkny8pWLrN; Fri, 07 Apr 2023 15:25:40 +0000 X-Authority-Reason: nr=8 X-Authority-Analysis: v=2.4 cv=fuoZ2H0f c=1 sm=1 tr=0 ts=643035f4 a=ApxJNpeYhEAb1aAlGBBbmA==:117 a=ApxJNpeYhEAb1aAlGBBbmA==:17 a=dLZJa+xiwSxG16/P+YVxDGlgEgI=:19 a=IkcTkHD0fZMA:10:nop_charset_1 a=dKHAf1wccvYA:10:nop_rcvd_month_year a=Qbun_eYptAEA:10:endurance_base64_authed_username_1 a=g4z11tMtLadPjQWhkm0A:9 a=QEXdDO2ut3YA:10:nop_charset_2 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tromey.com; s=default; h=To:In-Reply-To:References:Message-Id:Content-Transfer-Encoding: Content-Type:MIME-Version:Subject:Date:From:Sender:Reply-To:Cc:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=DaVXKHBWo/6a0c3SfsgE+yxe02vb4hVFdVoUfxNrunE=; b=oxcRKv94muo8fKZGsOWoy0GZuI 0ohvPw2Zd8psWLy8MX5tAZ79+tqxY7H4HKRoWwHdfb+HONfY+zb60XZ9M4FK14CieimLt5T6ACHot Yf8CD1gZL/aw07jwgjrxt37S/; Received: from 75-166-159-36.hlrn.qwest.net ([75.166.159.36]:60392 helo=[192.168.0.21]) by box5379.bluehost.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1pkny8-001hDU-NV for gdb-patches@sourceware.org; Fri, 07 Apr 2023 09:25:40 -0600 From: Tom Tromey Date: Fri, 07 Apr 2023 09:25:34 -0600 Subject: [PATCH 02/19] Convert compile-c-symbols.c to new hash table MIME-Version: 1.0 Message-Id: <20230407-t-robin-hood-hash-v1-2-900d93ef1510@tromey.com> References: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> In-Reply-To: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> To: gdb-patches@sourceware.org X-Mailer: b4 0.12.1 X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - box5379.bluehost.com X-AntiAbuse: Original Domain - sourceware.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - tromey.com X-BWhitelist: no X-Source-IP: 75.166.159.36 X-Source-L: No X-Exim-ID: 1pkny8-001hDU-NV X-Source: X-Source-Args: X-Source-Dir: X-Source-Sender: 75-166-159-36.hlrn.qwest.net ([192.168.0.21]) [75.166.159.36]:60392 X-Source-Auth: tom+tromey.com X-Email-Count: 3 X-Source-Cap: ZWx5bnJvYmk7ZWx5bnJvYmk7Ym94NTM3OS5ibHVlaG9zdC5jb20= X-Local-Domain: yes X-Spam-Status: No, score=-3026.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, JMQ_SPF_NEUTRAL, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gdb-patches-bounces+patchwork=sourceware.org@sourceware.org Sender: "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" @@ -444,43 +445,27 @@ gcc_symbol_address (void *datum, struct gcc_c_context *gcc_context, -/* 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_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); } From patchwork Fri Apr 7 15:25:35 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom Tromey X-Patchwork-Id: 67516 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 90AE23857739 for ; Fri, 7 Apr 2023 15:28:02 +0000 (GMT) X-Original-To: gdb-patches@sourceware.org Delivered-To: gdb-patches@sourceware.org Received: from qproxy3-pub.mail.unifiedlayer.com (qproxy3-pub.mail.unifiedlayer.com [67.222.38.20]) by sourceware.org (Postfix) with ESMTPS id DFE8F38708A5 for ; Fri, 7 Apr 2023 15:27:11 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org DFE8F38708A5 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=tromey.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=tromey.com Received: from outbound-ss-761.bluehost.com (outbound-ss-761.bluehost.com [74.220.211.250]) by qproxy3.mail.unifiedlayer.com (Postfix) with ESMTP id 1A9EB802E747 for ; Fri, 7 Apr 2023 15:27:11 +0000 (UTC) Received: from cmgw10.mail.unifiedlayer.com (unknown [10.0.90.125]) by progateway8.mail.pro1.eigbox.com (Postfix) with ESMTP id 0CE2810050371 for ; Fri, 7 Apr 2023 15:25:41 +0000 (UTC) Received: from box5379.bluehost.com ([162.241.216.53]) by cmsmtp with ESMTP id kny8poKF7FhsVkny9pK5pa; Fri, 07 Apr 2023 15:25:41 +0000 X-Authority-Reason: nr=8 X-Authority-Analysis: v=2.4 cv=ELjDb3VC c=1 sm=1 tr=0 ts=643035f5 a=ApxJNpeYhEAb1aAlGBBbmA==:117 a=ApxJNpeYhEAb1aAlGBBbmA==:17 a=dLZJa+xiwSxG16/P+YVxDGlgEgI=:19 a=IkcTkHD0fZMA:10:nop_charset_1 a=dKHAf1wccvYA:10:nop_rcvd_month_year a=Qbun_eYptAEA:10:endurance_base64_authed_username_1 a=mDV3o1hIAAAA:8 a=8pvPtFq1LiyjqC6Q-G8A:9 a=QEXdDO2ut3YA:10:nop_charset_2 a=wf2hqGuFN4hjegy2J-mS:22 a=_FVE-zBwftR9WsbkzFJk:22 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tromey.com; s=default; h=To:In-Reply-To:References:Message-Id:Content-Transfer-Encoding: Content-Type:MIME-Version:Subject:Date:From:Sender:Reply-To:Cc:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=sn6/GYkisqu/5Nat8t1RVWAfVZwYpG8tu+iG0Hkm1zg=; b=TuKtl//rtrjzHhRDSpsGsR/gMy glw9DYW2c+hB/2kqxr1fSm3iEJ7JAFqsZITq/t5lBM25CvXKxROkB4QE+F+O3ocaxI6asvl3E511o 66iPhtHvtWZp9i5PokSzwhHwZ; Received: from 75-166-159-36.hlrn.qwest.net ([75.166.159.36]:60392 helo=[192.168.0.21]) by box5379.bluehost.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1pkny8-001hDU-Rx for gdb-patches@sourceware.org; Fri, 07 Apr 2023 09:25:40 -0600 From: Tom Tromey Date: Fri, 07 Apr 2023 09:25:35 -0600 Subject: [PATCH 03/19] Convert filename-seen-cache.h to new hash table MIME-Version: 1.0 Message-Id: <20230407-t-robin-hood-hash-v1-3-900d93ef1510@tromey.com> References: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> In-Reply-To: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> To: gdb-patches@sourceware.org X-Mailer: b4 0.12.1 X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - box5379.bluehost.com X-AntiAbuse: Original Domain - sourceware.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - tromey.com X-BWhitelist: no X-Source-IP: 75.166.159.36 X-Source-L: No X-Exim-ID: 1pkny8-001hDU-Rx X-Source: X-Source-Args: X-Source-Dir: X-Source-Sender: 75-166-159-36.hlrn.qwest.net ([192.168.0.21]) [75.166.159.36]:60392 X-Source-Auth: tom+tromey.com X-Email-Count: 4 X-Source-Cap: ZWx5bnJvYmk7ZWx5bnJvYmk7Ym94NTM3OS5ibHVlaG9zdC5jb20= X-Local-Domain: yes X-Spam-Status: No, score=-3026.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, JMQ_SPF_NEUTRAL, KAM_SHORT, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gdb-patches-bounces+patchwork=sourceware.org@sourceware.org Sender: "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 . */ - -#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 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; + /* Table of files seen so far. */ - htab_up m_tab; + gdb::traited_hash_table m_tab; }; #endif /* FILENAME_SEEN_CACHE_H */ From patchwork Fri Apr 7 15:25:36 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom Tromey X-Patchwork-Id: 67500 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 7CCCE3856948 for ; Fri, 7 Apr 2023 15:26:07 +0000 (GMT) X-Original-To: gdb-patches@sourceware.org Delivered-To: gdb-patches@sourceware.org Received: from gproxy4-pub.mail.unifiedlayer.com (gproxy4-pub.mail.unifiedlayer.com [69.89.23.142]) by sourceware.org (Postfix) with ESMTPS id D35EE3858D35 for ; Fri, 7 Apr 2023 15:25:41 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org D35EE3858D35 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=tromey.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=tromey.com Received: from cmgw14.mail.unifiedlayer.com (unknown [10.0.90.129]) by progateway6.mail.pro1.eigbox.com (Postfix) with ESMTP id 29F3B10049526 for ; Fri, 7 Apr 2023 15:25:41 +0000 (UTC) Received: from box5379.bluehost.com ([162.241.216.53]) by cmsmtp with ESMTP id kny9pbB6SzLqskny9ph3z8; Fri, 07 Apr 2023 15:25:41 +0000 X-Authority-Reason: nr=8 X-Authority-Analysis: v=2.4 cv=M+SIlw8s c=1 sm=1 tr=0 ts=643035f5 a=ApxJNpeYhEAb1aAlGBBbmA==:117 a=ApxJNpeYhEAb1aAlGBBbmA==:17 a=dLZJa+xiwSxG16/P+YVxDGlgEgI=:19 a=IkcTkHD0fZMA:10:nop_charset_1 a=dKHAf1wccvYA:10:nop_rcvd_month_year a=Qbun_eYptAEA:10:endurance_base64_authed_username_1 a=XLl_NUxlzQrDj_gAf_AA:9 a=QEXdDO2ut3YA:10:nop_charset_2 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tromey.com; s=default; h=To:In-Reply-To:References:Message-Id:Content-Transfer-Encoding: Content-Type:MIME-Version:Subject:Date:From:Sender:Reply-To:Cc:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=+kwhHgm/eidySNbqkPjL6R0Ou7p5yfui9TJCOqu+urQ=; b=n8O/p7b8TS2AqkeKCvLLYez8f3 35zOMka16pX0HdFGxD9LD0KnwVHCR0WgGlw9X59o5Ny/NoANinRdMOxymKe8sGWy5V0nFpVdVMZVb ypIIGSCf72ETgI0ps0p93aGJx; Received: from 75-166-159-36.hlrn.qwest.net ([75.166.159.36]:60392 helo=[192.168.0.21]) by box5379.bluehost.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1pkny8-001hDU-W8 for gdb-patches@sourceware.org; Fri, 07 Apr 2023 09:25:41 -0600 From: Tom Tromey Date: Fri, 07 Apr 2023 09:25:36 -0600 Subject: [PATCH 04/19] Convert linespec.c to new hash table MIME-Version: 1.0 Message-Id: <20230407-t-robin-hood-hash-v1-4-900d93ef1510@tromey.com> References: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> In-Reply-To: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> To: gdb-patches@sourceware.org X-Mailer: b4 0.12.1 X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - box5379.bluehost.com X-AntiAbuse: Original Domain - sourceware.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - tromey.com X-BWhitelist: no X-Source-IP: 75.166.159.36 X-Source-L: No X-Exim-ID: 1pkny8-001hDU-W8 X-Source: X-Source-Args: X-Source-Dir: X-Source-Sender: 75-166-159-36.hlrn.qwest.net ([192.168.0.21]) [75.166.159.36]:60392 X-Source-Auth: tom+tromey.com X-Email-Count: 5 X-Source-Cap: ZWx5bnJvYmk7ZWx5bnJvYmk7Ym94NTM3OS5ibHVlaG9zdC5jb20= X-Local-Domain: yes X-Spam-Status: No, score=-3026.3 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, JMQ_SPF_NEUTRAL, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gdb-patches-bounces+patchwork=sourceware.org@sourceware.org Sender: "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 #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 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 m_unique_syms; /* The result vector. */ std::vector 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 &&release_symtabs () @@ -3666,24 +3662,9 @@ class symtab_collector std::vector m_symtabs; /* This is used to ensure the symtabs are unique. */ - htab_up m_symtab_table; + gdb::hash_set 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 From patchwork Fri Apr 7 15:25:37 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom Tromey X-Patchwork-Id: 67502 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 965E23853830 for ; Fri, 7 Apr 2023 15:26:23 +0000 (GMT) X-Original-To: gdb-patches@sourceware.org Delivered-To: gdb-patches@sourceware.org Received: from outbound-ss-820.bluehost.com (outbound-ss-820.bluehost.com [69.89.24.241]) by sourceware.org (Postfix) with ESMTPS id 289E23858C74 for ; Fri, 7 Apr 2023 15:25:42 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 289E23858C74 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=tromey.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=tromey.com Received: from cmgw10.mail.unifiedlayer.com (unknown [10.0.90.125]) by progateway2.mail.pro1.eigbox.com (Postfix) with ESMTP id 744F810047F97 for ; Fri, 7 Apr 2023 15:25:41 +0000 (UTC) Received: from box5379.bluehost.com ([162.241.216.53]) by cmsmtp with ESMTP id kny9poKFKFhsVkny9pK5po; Fri, 07 Apr 2023 15:25:41 +0000 X-Authority-Reason: nr=8 X-Authority-Analysis: v=2.4 cv=ELjDb3VC c=1 sm=1 tr=0 ts=643035f5 a=ApxJNpeYhEAb1aAlGBBbmA==:117 a=ApxJNpeYhEAb1aAlGBBbmA==:17 a=dLZJa+xiwSxG16/P+YVxDGlgEgI=:19 a=IkcTkHD0fZMA:10:nop_charset_1 a=dKHAf1wccvYA:10:nop_rcvd_month_year a=Qbun_eYptAEA:10:endurance_base64_authed_username_1 a=9SNkT6929W1KL7AQTFIA:9 a=QEXdDO2ut3YA:10:nop_charset_2 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tromey.com; s=default; h=To:In-Reply-To:References:Message-Id:Content-Transfer-Encoding: Content-Type:MIME-Version:Subject:Date:From:Sender:Reply-To:Cc:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=FLcjinxEvo61Em1t/qxJxNpGFfiOkrkG6Vw/Q1vxXn4=; b=HxisVogOBRUAWeKf9qBtb3vdR5 vn0VCsFLnAuQ/OQJrSrdP8tuc8N2FdZXsH7XAIt4LGvzLqa/Z1csEBnh27iq41BbL7PAPU2AT1NTU 2Tu9V0oXzdp5eRrmodWqTJzlr; Received: from 75-166-159-36.hlrn.qwest.net ([75.166.159.36]:60392 helo=[192.168.0.21]) by box5379.bluehost.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1pkny9-001hDU-4m for gdb-patches@sourceware.org; Fri, 07 Apr 2023 09:25:41 -0600 From: Tom Tromey Date: Fri, 07 Apr 2023 09:25:37 -0600 Subject: [PATCH 05/19] Convert target-descriptions.c to new hash table MIME-Version: 1.0 Message-Id: <20230407-t-robin-hood-hash-v1-5-900d93ef1510@tromey.com> References: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> In-Reply-To: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> To: gdb-patches@sourceware.org X-Mailer: b4 0.12.1 X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - box5379.bluehost.com X-AntiAbuse: Original Domain - sourceware.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - tromey.com X-BWhitelist: no X-Source-IP: 75.166.159.36 X-Source-L: No X-Exim-ID: 1pkny9-001hDU-4m X-Source: X-Source-Args: X-Source-Dir: X-Source-Sender: 75-166-159-36.hlrn.qwest.net ([192.168.0.21]) [75.166.159.36]:60392 X-Source-Auth: tom+tromey.com X-Email-Count: 6 X-Source-Cap: ZWx5bnJvYmk7ZWx5bnJvYmk7Ym94NTM3OS5ibHVlaG9zdC5jb20= X-Local-Domain: yes X-Spam-Status: No, score=-3026.4 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, JMQ_SPF_NEUTRAL, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gdb-patches-bounces+patchwork=sourceware.org@sourceware.org Sender: "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 #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 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++; From patchwork Fri Apr 7 15:25:38 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom Tromey X-Patchwork-Id: 67498 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id C25483857C44 for ; Fri, 7 Apr 2023 15:25:56 +0000 (GMT) X-Original-To: gdb-patches@sourceware.org Delivered-To: gdb-patches@sourceware.org Received: from progateway7-pub.mail.pro1.eigbox.com (gproxy5-pub.mail.unifiedlayer.com [67.222.38.55]) by sourceware.org (Postfix) with ESMTPS id 156183858C83 for ; Fri, 7 Apr 2023 15:25:42 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 156183858C83 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=tromey.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=tromey.com Received: from cmgw10.mail.unifiedlayer.com (unknown [10.0.90.125]) by progateway7.mail.pro1.eigbox.com (Postfix) with ESMTP id 7452610047419 for ; Fri, 7 Apr 2023 15:25:41 +0000 (UTC) Received: from box5379.bluehost.com ([162.241.216.53]) by cmsmtp with ESMTP id kny9poKFOFhsVkny9pK5ps; Fri, 07 Apr 2023 15:25:41 +0000 X-Authority-Reason: nr=8 X-Authority-Analysis: v=2.4 cv=ELjDb3VC c=1 sm=1 tr=0 ts=643035f5 a=ApxJNpeYhEAb1aAlGBBbmA==:117 a=ApxJNpeYhEAb1aAlGBBbmA==:17 a=dLZJa+xiwSxG16/P+YVxDGlgEgI=:19 a=IkcTkHD0fZMA:10:nop_charset_1 a=dKHAf1wccvYA:10:nop_rcvd_month_year a=Qbun_eYptAEA:10:endurance_base64_authed_username_1 a=CCpqsmhAAAAA:8 a=XINXnd7XTCThitrW7pYA:9 a=QEXdDO2ut3YA:10:nop_charset_2 a=ul9cdbp4aOFLsgKbc677:22 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tromey.com; s=default; h=To:In-Reply-To:References:Message-Id:Content-Transfer-Encoding: Content-Type:MIME-Version:Subject:Date:From:Sender:Reply-To:Cc:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=CapfTj95Xc2HEy4ueCKkDUvS+phIfFO49A1AjvNyptE=; b=su586iJBCf8/z4/pthP0gCnK3F X6DDRHHvZVoWU45qfY5X+EDnuSM36ejCOFuKDqJHJ/Jei5NfiDuMCx+IuzFPEWGa/iCUjJ6+78TC4 mcpERQZh8PtG9CqN+K6af/jkl; Received: from 75-166-159-36.hlrn.qwest.net ([75.166.159.36]:60392 helo=[192.168.0.21]) by box5379.bluehost.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1pkny9-001hDU-8p for gdb-patches@sourceware.org; Fri, 07 Apr 2023 09:25:41 -0600 From: Tom Tromey Date: Fri, 07 Apr 2023 09:25:38 -0600 Subject: [PATCH 06/19] Convert dwarf2/macro.c to new hash table MIME-Version: 1.0 Message-Id: <20230407-t-robin-hood-hash-v1-6-900d93ef1510@tromey.com> References: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> In-Reply-To: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> To: gdb-patches@sourceware.org X-Mailer: b4 0.12.1 X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - box5379.bluehost.com X-AntiAbuse: Original Domain - sourceware.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - tromey.com X-BWhitelist: no X-Source-IP: 75.166.159.36 X-Source-L: No X-Exim-ID: 1pkny9-001hDU-8p X-Source: X-Source-Args: X-Source-Dir: X-Source-Sender: 75-166-159-36.hlrn.qwest.net ([192.168.0.21]) [75.166.159.36]:60392 X-Source-Auth: tom+tromey.com X-Email-Count: 7 X-Source-Cap: ZWx5bnJvYmk7ZWx5bnJvYmk7Ym94NTM3OS5ibHVlaG9zdC5jb20= X-Local-Domain: yes X-Spam-Status: No, score=-3026.3 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, JMQ_SPF_NEUTRAL, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gdb-patches-bounces+patchwork=sourceware.org@sourceware.org Sender: "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 str_offsets_base, - htab_t include_hash, struct dwarf2_cu *cu) + gdb::hash_set &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 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); } From patchwork Fri Apr 7 15:25:39 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom Tromey X-Patchwork-Id: 67501 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 7EC713853814 for ; Fri, 7 Apr 2023 15:26:20 +0000 (GMT) X-Original-To: gdb-patches@sourceware.org Delivered-To: gdb-patches@sourceware.org Received: from gproxy1-pub.mail.unifiedlayer.com (gproxy1-pub.mail.unifiedlayer.com [69.89.25.95]) by sourceware.org (Postfix) with ESMTPS id 502123858C1F for ; Fri, 7 Apr 2023 15:25:42 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 502123858C1F Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=tromey.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=tromey.com Received: from cmgw14.mail.unifiedlayer.com (unknown [10.0.90.129]) by progateway3.mail.pro1.eigbox.com (Postfix) with ESMTP id 8949210047D80 for ; Fri, 7 Apr 2023 15:25:41 +0000 (UTC) Received: from box5379.bluehost.com ([162.241.216.53]) by cmsmtp with ESMTP id kny9pbB6hzLqskny9ph3zM; Fri, 07 Apr 2023 15:25:41 +0000 X-Authority-Reason: nr=8 X-Authority-Analysis: v=2.4 cv=M+SIlw8s c=1 sm=1 tr=0 ts=643035f5 a=ApxJNpeYhEAb1aAlGBBbmA==:117 a=ApxJNpeYhEAb1aAlGBBbmA==:17 a=dLZJa+xiwSxG16/P+YVxDGlgEgI=:19 a=IkcTkHD0fZMA:10:nop_charset_1 a=dKHAf1wccvYA:10:nop_rcvd_month_year a=Qbun_eYptAEA:10:endurance_base64_authed_username_1 a=3lNPh8f3RqoXguu8mcoA:9 a=QEXdDO2ut3YA:10:nop_charset_2 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tromey.com; s=default; h=To:In-Reply-To:References:Message-Id:Content-Transfer-Encoding: Content-Type:MIME-Version:Subject:Date:From:Sender:Reply-To:Cc:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=tzPck+U+Zon8x4/5meb3BoRlSZWU7OcK5I/dWLpivi8=; b=nPkc/8GvLtdDbP8x0DTrm+bR1m v2RPsUuyd2Ndx/ydrmLe1GKaiWXVheO3qfU+WQbb440u1W9+/MMMnfe8ROB5jevhDgjZdZLB5l0sJ zQuPVh4X/xi4eH1tdvxmi+dWp; Received: from 75-166-159-36.hlrn.qwest.net ([75.166.159.36]:60392 helo=[192.168.0.21]) by box5379.bluehost.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1pkny9-001hDU-Cq for gdb-patches@sourceware.org; Fri, 07 Apr 2023 09:25:41 -0600 From: Tom Tromey Date: Fri, 07 Apr 2023 09:25:39 -0600 Subject: [PATCH 07/19] Convert breakpoint.c to new hash table MIME-Version: 1.0 Message-Id: <20230407-t-robin-hood-hash-v1-7-900d93ef1510@tromey.com> References: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> In-Reply-To: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> To: gdb-patches@sourceware.org X-Mailer: b4 0.12.1 X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - box5379.bluehost.com X-AntiAbuse: Original Domain - sourceware.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - tromey.com X-BWhitelist: no X-Source-IP: 75.166.159.36 X-Source-L: No X-Exim-ID: 1pkny9-001hDU-Cq X-Source: X-Source-Args: X-Source-Dir: X-Source-Sender: 75-166-159-36.hlrn.qwest.net ([192.168.0.21]) [75.166.159.36]:60392 X-Source-Auth: tom+tromey.com X-Email-Count: 8 X-Source-Cap: ZWx5bnJvYmk7ZWx5bnJvYmk7Ym94NTM3OS5ibHVlaG9zdC5jb20= X-Local-Domain: yes X-Spam-Status: No, score=-3026.4 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, JMQ_SPF_NEUTRAL, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gdb-patches-bounces+patchwork=sourceware.org@sourceware.org Sender: "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 -#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; + gdb::traited_hash_table 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; From patchwork Fri Apr 7 15:25:40 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom Tromey X-Patchwork-Id: 67511 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 6E012385356A for ; Fri, 7 Apr 2023 15:27:29 +0000 (GMT) X-Original-To: gdb-patches@sourceware.org Delivered-To: gdb-patches@sourceware.org Received: from gproxy3-pub.mail.unifiedlayer.com (gproxy3-pub.mail.unifiedlayer.com [69.89.30.42]) by sourceware.org (Postfix) with ESMTPS id 172E7385842A for ; Fri, 7 Apr 2023 15:25:44 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 172E7385842A Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=tromey.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=tromey.com Received: from cmgw14.mail.unifiedlayer.com (unknown [10.0.90.129]) by progateway5.mail.pro1.eigbox.com (Postfix) with ESMTP id AEDBA10048762 for ; Fri, 7 Apr 2023 15:25:41 +0000 (UTC) Received: from box5379.bluehost.com ([162.241.216.53]) by cmsmtp with ESMTP id kny9pbB6mzLqskny9ph3zR; Fri, 07 Apr 2023 15:25:41 +0000 X-Authority-Reason: nr=8 X-Authority-Analysis: v=2.4 cv=M+SIlw8s c=1 sm=1 tr=0 ts=643035f5 a=ApxJNpeYhEAb1aAlGBBbmA==:117 a=ApxJNpeYhEAb1aAlGBBbmA==:17 a=dLZJa+xiwSxG16/P+YVxDGlgEgI=:19 a=IkcTkHD0fZMA:10:nop_charset_1 a=dKHAf1wccvYA:10:nop_rcvd_month_year a=Qbun_eYptAEA:10:endurance_base64_authed_username_1 a=lD6fMf488kMWFAAwEFgA:9 a=QEXdDO2ut3YA:10:nop_charset_2 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tromey.com; s=default; h=To:In-Reply-To:References:Message-Id:Content-Transfer-Encoding: Content-Type:MIME-Version:Subject:Date:From:Sender:Reply-To:Cc:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=XGz2WfWtEZwu1+mLvv0VK8GfBhyA+5Alr4a+HCsgc2A=; b=EUh2q1y0G+D8HQuC50Z019VqmQ ruCfNipxStFlt6inaeD+avZHrV6BMRVp8MsRmFkhv1+EeYEuSyK6hgle1/7u5CZF6S5Agx9bq0IQC SU2Yiu3KzMENhbd8cROLWm+QQ; Received: from 75-166-159-36.hlrn.qwest.net ([75.166.159.36]:60392 helo=[192.168.0.21]) by box5379.bluehost.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1pkny9-001hDU-Hl for gdb-patches@sourceware.org; Fri, 07 Apr 2023 09:25:41 -0600 From: Tom Tromey Date: Fri, 07 Apr 2023 09:25:40 -0600 Subject: [PATCH 08/19] Convert py-framefilter.c to new hash table MIME-Version: 1.0 Message-Id: <20230407-t-robin-hood-hash-v1-8-900d93ef1510@tromey.com> References: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> In-Reply-To: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> To: gdb-patches@sourceware.org X-Mailer: b4 0.12.1 X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - box5379.bluehost.com X-AntiAbuse: Original Domain - sourceware.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - tromey.com X-BWhitelist: no X-Source-IP: 75.166.159.36 X-Source-L: No X-Exim-ID: 1pkny9-001hDU-Hl X-Source: X-Source-Args: X-Source-Dir: X-Source-Sender: 75-166-159-36.hlrn.qwest.net ([192.168.0.21]) [75.166.159.36]:60392 X-Source-Auth: tom+tromey.com X-Email-Count: 9 X-Source-Cap: ZWx5bnJvYmk7ZWx5bnJvYmk7Ym94NTM3OS5ibHVlaG9zdC5jb20= X-Local-Domain: yes X-Spam-Status: No, score=-3026.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, JMQ_SPF_NEUTRAL, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gdb-patches-bounces+patchwork=sourceware.org@sourceware.org Sender: "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 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) { From patchwork Fri Apr 7 15:25:41 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom Tromey X-Patchwork-Id: 67505 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 671473856DF6 for ; Fri, 7 Apr 2023 15:26:40 +0000 (GMT) X-Original-To: gdb-patches@sourceware.org Delivered-To: gdb-patches@sourceware.org Received: from outbound-ss-761.bluehost.com (outbound-ss-761.bluehost.com [74.220.211.250]) by sourceware.org (Postfix) with ESMTPS id 901CD3858C2B for ; Fri, 7 Apr 2023 15:25:42 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 901CD3858C2B Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=tromey.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=tromey.com Received: from cmgw14.mail.unifiedlayer.com (unknown [10.0.90.129]) by progateway8.mail.pro1.eigbox.com (Postfix) with ESMTP id C947A1003E981 for ; Fri, 7 Apr 2023 15:25:41 +0000 (UTC) Received: from box5379.bluehost.com ([162.241.216.53]) by cmsmtp with ESMTP id kny9pbB6rzLqskny9ph3zV; Fri, 07 Apr 2023 15:25:41 +0000 X-Authority-Reason: nr=8 X-Authority-Analysis: v=2.4 cv=M+SIlw8s c=1 sm=1 tr=0 ts=643035f5 a=ApxJNpeYhEAb1aAlGBBbmA==:117 a=ApxJNpeYhEAb1aAlGBBbmA==:17 a=dLZJa+xiwSxG16/P+YVxDGlgEgI=:19 a=IkcTkHD0fZMA:10:nop_charset_1 a=dKHAf1wccvYA:10:nop_rcvd_month_year a=Qbun_eYptAEA:10:endurance_base64_authed_username_1 a=tgYc36JjReZGD-yYzW8A:9 a=QEXdDO2ut3YA:10:nop_charset_2 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tromey.com; s=default; h=To:In-Reply-To:References:Message-Id:Content-Transfer-Encoding: Content-Type:MIME-Version:Subject:Date:From:Sender:Reply-To:Cc:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=A+frZ0GdvpI+KK/2YOFs+nOqr2f0Zx2DcGAwA2nsbv8=; b=LfjIzLKYOcXx26X7cQ5neAf5jW jQA2Hxe299lQ4WOyWXkWjtragXLPG8yvDWNqH9alNggc7wvvNsh3si8vloXowreOeXOoZ1/NWPBQV 8fTjN6T+dr2zarKrbj8WpYLer; Received: from 75-166-159-36.hlrn.qwest.net ([75.166.159.36]:60392 helo=[192.168.0.21]) by box5379.bluehost.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1pkny9-001hDU-Lb for gdb-patches@sourceware.org; Fri, 07 Apr 2023 09:25:41 -0600 From: Tom Tromey Date: Fri, 07 Apr 2023 09:25:41 -0600 Subject: [PATCH 09/19] Convert disasm.c to new hash table MIME-Version: 1.0 Message-Id: <20230407-t-robin-hood-hash-v1-9-900d93ef1510@tromey.com> References: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> In-Reply-To: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> To: gdb-patches@sourceware.org X-Mailer: b4 0.12.1 X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - box5379.bluehost.com X-AntiAbuse: Original Domain - sourceware.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - tromey.com X-BWhitelist: no X-Source-IP: 75.166.159.36 X-Source-L: No X-Exim-ID: 1pkny9-001hDU-Lb X-Source: X-Source-Args: X-Source-Dir: X-Source-Sender: 75-166-159-36.hlrn.qwest.net ([192.168.0.21]) [75.166.159.36]:60392 X-Source-Auth: tom+tromey.com X-Email-Count: 10 X-Source-Cap: ZWx5bnJvYmk7ZWx5bnJvYmk7Ym94NTM3OS5ibHVlaG9zdC5jb20= X-Local-Domain: yes X-Spam-Status: No, score=-3026.5 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, JMQ_SPF_NEUTRAL, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gdb-patches-bounces+patchwork=sourceware.org@sourceware.org Sender: "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 { - 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 () (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 &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 &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_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) From patchwork Fri Apr 7 15:25:42 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom Tromey X-Patchwork-Id: 67503 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 5359A3856DD5 for ; Fri, 7 Apr 2023 15:26:27 +0000 (GMT) X-Original-To: gdb-patches@sourceware.org Delivered-To: gdb-patches@sourceware.org Received: from progateway7-pub.mail.pro1.eigbox.com (gproxy5-pub.mail.unifiedlayer.com [67.222.38.55]) by sourceware.org (Postfix) with ESMTPS id 950E33858C30 for ; Fri, 7 Apr 2023 15:25:42 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 950E33858C30 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=tromey.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=tromey.com Received: from cmgw13.mail.unifiedlayer.com (unknown [10.0.90.128]) by progateway7.mail.pro1.eigbox.com (Postfix) with ESMTP id E6B3510047423 for ; Fri, 7 Apr 2023 15:25:41 +0000 (UTC) Received: from box5379.bluehost.com ([162.241.216.53]) by cmsmtp with ESMTP id kny9pNc1ONX2akny9p1QO4; Fri, 07 Apr 2023 15:25:41 +0000 X-Authority-Reason: nr=8 X-Authority-Analysis: v=2.4 cv=NMAQR22g c=1 sm=1 tr=0 ts=643035f5 a=ApxJNpeYhEAb1aAlGBBbmA==:117 a=ApxJNpeYhEAb1aAlGBBbmA==:17 a=dLZJa+xiwSxG16/P+YVxDGlgEgI=:19 a=IkcTkHD0fZMA:10:nop_charset_1 a=dKHAf1wccvYA:10:nop_rcvd_month_year a=Qbun_eYptAEA:10:endurance_base64_authed_username_1 a=rfOID86329tGnJx2QQwA:9 a=QEXdDO2ut3YA:10:nop_charset_2 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tromey.com; s=default; h=To:In-Reply-To:References:Message-Id:Content-Transfer-Encoding: Content-Type:MIME-Version:Subject:Date:From:Sender:Reply-To:Cc:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=obW5jNOxenhr+9VJ+2t1/xalr518fHLhC4LeDszS3tg=; b=GsmMv0yo+twc+P3hcfTbcetqfh XT9RQB0BNqI/JcfvsBLZQtjBRZABgO0LHMQV7N2jgmSPBvzUAIELC2/45EKcdQgqbL5Z5lAG30E6h C/Old4t04N8XNZ5PoSbVyt8Vv; Received: from 75-166-159-36.hlrn.qwest.net ([75.166.159.36]:60392 helo=[192.168.0.21]) by box5379.bluehost.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1pkny9-001hDU-Pb for gdb-patches@sourceware.org; Fri, 07 Apr 2023 09:25:41 -0600 From: Tom Tromey Date: Fri, 07 Apr 2023 09:25:42 -0600 Subject: [PATCH 10/19] Convert compile/compile.c to new hash table MIME-Version: 1.0 Message-Id: <20230407-t-robin-hood-hash-v1-10-900d93ef1510@tromey.com> References: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> In-Reply-To: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> To: gdb-patches@sourceware.org X-Mailer: b4 0.12.1 X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - box5379.bluehost.com X-AntiAbuse: Original Domain - sourceware.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - tromey.com X-BWhitelist: no X-Source-IP: 75.166.159.36 X-Source-L: No X-Exim-ID: 1pkny9-001hDU-Pb X-Source: X-Source-Args: X-Source-Dir: X-Source-Sender: 75-166-159-36.hlrn.qwest.net ([192.168.0.21]) [75.166.159.36]:60392 X-Source-Auth: tom+tromey.com X-Email-Count: 11 X-Source-Cap: ZWx5bnJvYmk7ZWx5bnJvYmk7Ym94NTM3OS5ibHVlaG9zdC5jb20= X-Local-Domain: yes X-Spam-Status: No, score=-3026.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, JMQ_SPF_NEUTRAL, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gdb-patches-bounces+patchwork=sourceware.org@sourceware.org Sender: "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 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 m_type_map; /* Map from gdb symbols to gcc error messages to emit. */ - htab_up m_symbol_err_map; + gdb::hash_map m_symbol_err_map; }; /* Public function that is called from compile_control case in the From patchwork Fri Apr 7 15:25:43 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom Tromey X-Patchwork-Id: 67508 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 7FDDA385382A for ; Fri, 7 Apr 2023 15:27:12 +0000 (GMT) X-Original-To: gdb-patches@sourceware.org Delivered-To: gdb-patches@sourceware.org Received: from alt-proxy28.mail.unifiedlayer.com (alt-proxy28.mail.unifiedlayer.com [74.220.216.123]) by sourceware.org (Postfix) with ESMTPS id C2B883858C31 for ; Fri, 7 Apr 2023 15:25:42 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org C2B883858C31 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=tromey.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=tromey.com Received: from cmgw10.mail.unifiedlayer.com (unknown [10.0.90.125]) by progateway1.mail.pro1.eigbox.com (Postfix) with ESMTP id 1371C1004061D for ; Fri, 7 Apr 2023 15:25:42 +0000 (UTC) Received: from box5379.bluehost.com ([162.241.216.53]) by cmsmtp with ESMTP id knyApoKFqFhsVknyApK5qJ; Fri, 07 Apr 2023 15:25:42 +0000 X-Authority-Reason: nr=8 X-Authority-Analysis: v=2.4 cv=ELjDb3VC c=1 sm=1 tr=0 ts=643035f6 a=ApxJNpeYhEAb1aAlGBBbmA==:117 a=ApxJNpeYhEAb1aAlGBBbmA==:17 a=dLZJa+xiwSxG16/P+YVxDGlgEgI=:19 a=IkcTkHD0fZMA:10:nop_charset_1 a=dKHAf1wccvYA:10:nop_rcvd_month_year a=Qbun_eYptAEA:10:endurance_base64_authed_username_1 a=eMNa1_i98CwEnHqiDYUA:9 a=QEXdDO2ut3YA:10:nop_charset_2 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tromey.com; s=default; h=To:In-Reply-To:References:Message-Id:Content-Transfer-Encoding: Content-Type:MIME-Version:Subject:Date:From:Sender:Reply-To:Cc:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=lOCaEHd0Hs6M6siP1aKZ1VVN4e6nIjrhCwW6jr8T08I=; b=AppCjAYcU3+/Oaswe1goOtwlmc p5GwmHA/+95oKnx/dMNTymdzJS4sTdL2sq5QDG7X311OhMCUGsJzd19LhoCsgteeEIwCb8Fu04pfq 31trQAYdJJAUxCVWaXfi2m2ub; Received: from 75-166-159-36.hlrn.qwest.net ([75.166.159.36]:60392 helo=[192.168.0.21]) by box5379.bluehost.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1pkny9-001hDU-TV for gdb-patches@sourceware.org; Fri, 07 Apr 2023 09:25:41 -0600 From: Tom Tromey Date: Fri, 07 Apr 2023 09:25:43 -0600 Subject: [PATCH 11/19] Convert type copying to new hash table MIME-Version: 1.0 Message-Id: <20230407-t-robin-hood-hash-v1-11-900d93ef1510@tromey.com> References: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> In-Reply-To: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> To: gdb-patches@sourceware.org X-Mailer: b4 0.12.1 X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - box5379.bluehost.com X-AntiAbuse: Original Domain - sourceware.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - tromey.com X-BWhitelist: no X-Source-IP: 75.166.159.36 X-Source-L: No X-Exim-ID: 1pkny9-001hDU-TV X-Source: X-Source-Args: X-Source-Dir: X-Source-Sender: 75-166-159-36.hlrn.qwest.net ([192.168.0.21]) [75.166.159.36]:60392 X-Source-Auth: tom+tromey.com X-Email-Count: 12 X-Source-Cap: ZWx5bnJvYmk7ZWx5bnJvYmk7Ym94NTM3OS5ibHVlaG9zdC5jb20= X-Local-Domain: yes X-Spam-Status: No, score=-3026.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, JMQ_SPF_NEUTRAL, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gdb-patches-bounces+patchwork=sourceware.org@sourceware.org Sender: "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); } -/* 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, - 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 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 &&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 From patchwork Fri Apr 7 15:25:44 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom Tromey X-Patchwork-Id: 67506 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 4A4893852774 for ; Fri, 7 Apr 2023 15:26:53 +0000 (GMT) X-Original-To: gdb-patches@sourceware.org Delivered-To: gdb-patches@sourceware.org Received: from gproxy2-pub.mail.unifiedlayer.com (gproxy2-pub.mail.unifiedlayer.com [69.89.18.3]) by sourceware.org (Postfix) with ESMTPS id 11FF13858C39 for ; Fri, 7 Apr 2023 15:25:43 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 11FF13858C39 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=tromey.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=tromey.com Received: from cmgw12.mail.unifiedlayer.com (unknown [10.0.90.127]) by progateway4.mail.pro1.eigbox.com (Postfix) with ESMTP id 5366A10047E07 for ; Fri, 7 Apr 2023 15:25:42 +0000 (UTC) Received: from box5379.bluehost.com ([162.241.216.53]) by cmsmtp with ESMTP id knyApLk5pChTwknyAplpWm; Fri, 07 Apr 2023 15:25:42 +0000 X-Authority-Reason: nr=8 X-Authority-Analysis: v=2.4 cv=BK12EHcG c=1 sm=1 tr=0 ts=643035f6 a=ApxJNpeYhEAb1aAlGBBbmA==:117 a=ApxJNpeYhEAb1aAlGBBbmA==:17 a=dLZJa+xiwSxG16/P+YVxDGlgEgI=:19 a=IkcTkHD0fZMA:10:nop_charset_1 a=dKHAf1wccvYA:10:nop_rcvd_month_year a=Qbun_eYptAEA:10:endurance_base64_authed_username_1 a=PJTVvGXVjnd0oxVvKrAA:9 a=QEXdDO2ut3YA:10:nop_charset_2 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tromey.com; s=default; h=To:In-Reply-To:References:Message-Id:Content-Transfer-Encoding: Content-Type:MIME-Version:Subject:Date:From:Sender:Reply-To:Cc:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=lZAGdiJv1mfzfjLecLKit/0OJxjIvuFu59MnMH90I9Q=; b=up1lP7qNZON/27pm5qVAw11NCs DajmgBmax8TvoKfTfDFgF61Ekrtcu6xmiDKMoPS5w8EK1wuXiG34v7D7AoRm5hUY4IMT/RgQmA+7E o6rpqMVIeTG1xPK3ssgR6MFGT; Received: from 75-166-159-36.hlrn.qwest.net ([75.166.159.36]:60392 helo=[192.168.0.21]) by box5379.bluehost.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1pknyA-001hDU-1I for gdb-patches@sourceware.org; Fri, 07 Apr 2023 09:25:42 -0600 From: Tom Tromey Date: Fri, 07 Apr 2023 09:25:44 -0600 Subject: [PATCH 12/19] Convert static links to new hash table MIME-Version: 1.0 Message-Id: <20230407-t-robin-hood-hash-v1-12-900d93ef1510@tromey.com> References: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> In-Reply-To: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> To: gdb-patches@sourceware.org X-Mailer: b4 0.12.1 X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - box5379.bluehost.com X-AntiAbuse: Original Domain - sourceware.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - tromey.com X-BWhitelist: no X-Source-IP: 75.166.159.36 X-Source-L: No X-Exim-ID: 1pknyA-001hDU-1I X-Source: X-Source-Args: X-Source-Dir: X-Source-Sender: 75-166-159-36.hlrn.qwest.net ([192.168.0.21]) [75.166.159.36]:60392 X-Source-Auth: tom+tromey.com X-Email-Count: 13 X-Source-Cap: ZWx5bnJvYmk7ZWx5bnJvYmk7Ym94NTM3OS5ibHVlaG9zdC5jb20= X-Local-Domain: yes X-Spam-Status: No, score=-3026.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, JMQ_SPF_NEUTRAL, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gdb-patches-bounces+patchwork=sourceware.org@sourceware.org Sender: "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; } 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 +#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 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 From patchwork Fri Apr 7 15:25:45 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom Tromey X-Patchwork-Id: 67507 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 06DEC385415F for ; Fri, 7 Apr 2023 15:27:01 +0000 (GMT) X-Original-To: gdb-patches@sourceware.org Delivered-To: gdb-patches@sourceware.org Received: from gproxy1-pub.mail.unifiedlayer.com (gproxy1-pub.mail.unifiedlayer.com [69.89.25.95]) by sourceware.org (Postfix) with ESMTPS id E972F3858C36 for ; Fri, 7 Apr 2023 15:25:42 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org E972F3858C36 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=tromey.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=tromey.com Received: from cmgw15.mail.unifiedlayer.com (unknown [10.0.90.130]) by progateway3.mail.pro1.eigbox.com (Postfix) with ESMTP id 4F60610047D92 for ; Fri, 7 Apr 2023 15:25:42 +0000 (UTC) Received: from box5379.bluehost.com ([162.241.216.53]) by cmsmtp with ESMTP id knyApyK0Lyk8zknyApWLsG; Fri, 07 Apr 2023 15:25:42 +0000 X-Authority-Reason: nr=8 X-Authority-Analysis: v=2.4 cv=fuoZ2H0f c=1 sm=1 tr=0 ts=643035f6 a=ApxJNpeYhEAb1aAlGBBbmA==:117 a=ApxJNpeYhEAb1aAlGBBbmA==:17 a=dLZJa+xiwSxG16/P+YVxDGlgEgI=:19 a=IkcTkHD0fZMA:10:nop_charset_1 a=dKHAf1wccvYA:10:nop_rcvd_month_year a=Qbun_eYptAEA:10:endurance_base64_authed_username_1 a=fcNt3aYxtXCb0dmhKWgA:9 a=QEXdDO2ut3YA:10:nop_charset_2 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tromey.com; s=default; h=To:In-Reply-To:References:Message-Id:Content-Transfer-Encoding: Content-Type:MIME-Version:Subject:Date:From:Sender:Reply-To:Cc:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=RviTTy+580l1X3O4ueK9gDciEA85imRHsvc+VWMBapg=; b=Gb7Dz2Lt1TTc0h1K7DKcndVTYN 9mUcPXMu3A09DsW/fJGogN/Scdhick2iWInbsCjVcs0O/5ElwCTTvEGSEYu7h9M957VTQ1Ey73NSi cosn5ZK//p3uP5piKDap1nFo7; Received: from 75-166-159-36.hlrn.qwest.net ([75.166.159.36]:60392 helo=[192.168.0.21]) by box5379.bluehost.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1pknyA-001hDU-4l for gdb-patches@sourceware.org; Fri, 07 Apr 2023 09:25:42 -0600 From: Tom Tromey Date: Fri, 07 Apr 2023 09:25:45 -0600 Subject: [PATCH 13/19] Convert gnu-v3-abi.c to new hash table MIME-Version: 1.0 Message-Id: <20230407-t-robin-hood-hash-v1-13-900d93ef1510@tromey.com> References: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> In-Reply-To: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> To: gdb-patches@sourceware.org X-Mailer: b4 0.12.1 X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - box5379.bluehost.com X-AntiAbuse: Original Domain - sourceware.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - tromey.com X-BWhitelist: no X-Source-IP: 75.166.159.36 X-Source-L: No X-Exim-ID: 1pknyA-001hDU-4l X-Source: X-Source-Args: X-Source-Dir: X-Source-Sender: 75-166-159-36.hlrn.qwest.net ([192.168.0.21]) [75.166.159.36]:60392 X-Source-Auth: tom+tromey.com X-Email-Count: 14 X-Source-Cap: ZWx5bnJvYmk7ZWx5bnJvYmk7Ym94NTM3OS5ibHVlaG9zdC5jb20= X-Local-Domain: yes X-Spam-Status: No, score=-3026.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, JMQ_SPF_NEUTRAL, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gdb-patches-bounces+patchwork=sourceware.org@sourceware.org Sender: "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 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 &va, + const std::pair &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 *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 result_vec; + vtable_hash_t offset_hash; + compute_vtable_size (offset_hash, value); - compute_vtable_size (offset_hash.get (), &result_vec, value); + std::vector> 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; } } From patchwork Fri Apr 7 15:25:46 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom Tromey X-Patchwork-Id: 67509 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 97D0E387090E for ; Fri, 7 Apr 2023 15:27:17 +0000 (GMT) X-Original-To: gdb-patches@sourceware.org Delivered-To: gdb-patches@sourceware.org Received: from alt-proxy28.mail.unifiedlayer.com (alt-proxy28.mail.unifiedlayer.com [74.220.216.123]) by sourceware.org (Postfix) with ESMTPS id 386AD3858404 for ; Fri, 7 Apr 2023 15:25:43 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 386AD3858404 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=tromey.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=tromey.com Received: from cmgw11.mail.unifiedlayer.com (unknown [10.0.90.126]) by progateway1.mail.pro1.eigbox.com (Postfix) with ESMTP id 9429010040637 for ; Fri, 7 Apr 2023 15:25:42 +0000 (UTC) Received: from box5379.bluehost.com ([162.241.216.53]) by cmsmtp with ESMTP id knyApJGGA2LM4knyApdkJl; Fri, 07 Apr 2023 15:25:42 +0000 X-Authority-Reason: nr=8 X-Authority-Analysis: v=2.4 cv=KbQXDSUD c=1 sm=1 tr=0 ts=643035f6 a=ApxJNpeYhEAb1aAlGBBbmA==:117 a=ApxJNpeYhEAb1aAlGBBbmA==:17 a=dLZJa+xiwSxG16/P+YVxDGlgEgI=:19 a=IkcTkHD0fZMA:10:nop_charset_1 a=dKHAf1wccvYA:10:nop_rcvd_month_year a=Qbun_eYptAEA:10:endurance_base64_authed_username_1 a=YsoOj7E6qrNLeVQtAV0A:9 a=QEXdDO2ut3YA:10:nop_charset_2 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tromey.com; s=default; h=To:In-Reply-To:References:Message-Id:Content-Transfer-Encoding: Content-Type:MIME-Version:Subject:Date:From:Sender:Reply-To:Cc:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=LnfcVHhaH0vPTPuh/R5R5zD3v2A7+xjwDNK+raQYe6M=; b=UtrtMGYv3TJSgPPevhlt8bKHr1 vqp3+5z47fJ8RzM08yErAVVrrj8PKzngJYzNjwrhNFn61k8CtgXOmYTSMP19C+zaFr8igFrY8eTOc I+tkOxKDYZGHtZpEQH5bkRvxp; Received: from 75-166-159-36.hlrn.qwest.net ([75.166.159.36]:60392 helo=[192.168.0.21]) by box5379.bluehost.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1pknyA-001hDU-90 for gdb-patches@sourceware.org; Fri, 07 Apr 2023 09:25:42 -0600 From: Tom Tromey Date: Fri, 07 Apr 2023 09:25:46 -0600 Subject: [PATCH 14/19] Convert abbrev cache to new hash table MIME-Version: 1.0 Message-Id: <20230407-t-robin-hood-hash-v1-14-900d93ef1510@tromey.com> References: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> In-Reply-To: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> To: gdb-patches@sourceware.org X-Mailer: b4 0.12.1 X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - box5379.bluehost.com X-AntiAbuse: Original Domain - sourceware.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - tromey.com X-BWhitelist: no X-Source-IP: 75.166.159.36 X-Source-L: No X-Exim-ID: 1pknyA-001hDU-90 X-Source: X-Source-Args: X-Source-Dir: X-Source-Sender: 75-166-159-36.hlrn.qwest.net ([192.168.0.21]) [75.166.159.36]:60392 X-Source-Auth: tom+tromey.com X-Email-Count: 15 X-Source-Cap: ZWx5bnJvYmk7ZWx5bnJvYmk7Ym94NTM3OS5ibHVlaG9zdC5jb20= X-Local-Domain: yes X-Spam-Status: No, score=-3026.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, JMQ_SPF_NEUTRAL, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gdb-patches-bounces+patchwork=sourceware.org@sourceware.org Sender: "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, - 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 m_tables; }; #endif /* GDB_DWARF2_ABBREV_CACHE_H */ From patchwork Fri Apr 7 15:25:47 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom Tromey X-Patchwork-Id: 67513 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 39D65385B526 for ; Fri, 7 Apr 2023 15:27:36 +0000 (GMT) X-Original-To: gdb-patches@sourceware.org Delivered-To: gdb-patches@sourceware.org Received: from outbound-ss-820.bluehost.com (outbound-ss-820.bluehost.com [69.89.24.241]) by sourceware.org (Postfix) with ESMTPS id 3B4FA385840C for ; Fri, 7 Apr 2023 15:25:43 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 3B4FA385840C Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=tromey.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=tromey.com Received: from cmgw10.mail.unifiedlayer.com (unknown [10.0.90.125]) by progateway2.mail.pro1.eigbox.com (Postfix) with ESMTP id 9085610047F94 for ; Fri, 7 Apr 2023 15:25:42 +0000 (UTC) Received: from box5379.bluehost.com ([162.241.216.53]) by cmsmtp with ESMTP id knyApoKGCFhsVknyApK5qe; Fri, 07 Apr 2023 15:25:42 +0000 X-Authority-Reason: nr=8 X-Authority-Analysis: v=2.4 cv=ELjDb3VC c=1 sm=1 tr=0 ts=643035f6 a=ApxJNpeYhEAb1aAlGBBbmA==:117 a=ApxJNpeYhEAb1aAlGBBbmA==:17 a=dLZJa+xiwSxG16/P+YVxDGlgEgI=:19 a=IkcTkHD0fZMA:10:nop_charset_1 a=dKHAf1wccvYA:10:nop_rcvd_month_year a=Qbun_eYptAEA:10:endurance_base64_authed_username_1 a=_dMr5OX9suqoNhTj5OMA:9 a=QEXdDO2ut3YA:10:nop_charset_2 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tromey.com; s=default; h=To:In-Reply-To:References:Message-Id:Content-Transfer-Encoding: Content-Type:MIME-Version:Subject:Date:From:Sender:Reply-To:Cc:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=VUsXwWMkTJEcc+QFXCKzKwocY9BVYrWPDEH3bwpdda4=; b=mbqTWOdBOAt2kalEHnUsBpt3Ak UlxvkDWdU245uuh3QqdU1WNDEZG5ufisXSwbn8Ueq9wE+by7Xc9l5kBNM2PAWB4mVZWI/ayZ65PQ2 8m07cXhYfGT3sPdaFenjCZvB+; Received: from 75-166-159-36.hlrn.qwest.net ([75.166.159.36]:60392 helo=[192.168.0.21]) by box5379.bluehost.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1pknyA-001hDU-DL for gdb-patches@sourceware.org; Fri, 07 Apr 2023 09:25:42 -0600 From: Tom Tromey Date: Fri, 07 Apr 2023 09:25:47 -0600 Subject: [PATCH 15/19] Convert abbrevs to new hash table MIME-Version: 1.0 Message-Id: <20230407-t-robin-hood-hash-v1-15-900d93ef1510@tromey.com> References: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> In-Reply-To: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> To: gdb-patches@sourceware.org X-Mailer: b4 0.12.1 X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - box5379.bluehost.com X-AntiAbuse: Original Domain - sourceware.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - tromey.com X-BWhitelist: no X-Source-IP: 75.166.159.36 X-Source-L: No X-Exim-ID: 1pknyA-001hDU-DL X-Source: X-Source-Args: X-Source-Dir: X-Source-Sender: 75-166-159-36.hlrn.qwest.net ([192.168.0.21]) [75.166.159.36]:60392 X-Source-Auth: tom+tromey.com X-Email-Count: 16 X-Source-Cap: ZWx5bnJvYmk7ZWx5bnJvYmk7Ym94NTM3OS5ibHVlaG9zdC5jb20= X-Local-Domain: yes X-Spam-Status: No, score=-3026.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, JMQ_SPF_NEUTRAL, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gdb-patches-bounces+patchwork=sourceware.org@sourceware.org Sender: "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 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 m_abbrevs; /* Storage for the abbrev table. */ auto_obstack m_abbrev_obstack; From patchwork Fri Apr 7 15:25:48 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom Tromey X-Patchwork-Id: 67510 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id E168D3856247 for ; Fri, 7 Apr 2023 15:27:25 +0000 (GMT) X-Original-To: gdb-patches@sourceware.org Delivered-To: gdb-patches@sourceware.org Received: from alt-proxy28.mail.unifiedlayer.com (alt-proxy28.mail.unifiedlayer.com [74.220.216.123]) by sourceware.org (Postfix) with ESMTPS id 57F97385840F for ; Fri, 7 Apr 2023 15:25:43 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 57F97385840F Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=tromey.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=tromey.com Received: from cmgw10.mail.unifiedlayer.com (unknown [10.0.90.125]) by progateway1.mail.pro1.eigbox.com (Postfix) with ESMTP id B97FA10040609 for ; Fri, 7 Apr 2023 15:25:42 +0000 (UTC) Received: from box5379.bluehost.com ([162.241.216.53]) by cmsmtp with ESMTP id knyApoKGGFhsVknyApK5qi; Fri, 07 Apr 2023 15:25:42 +0000 X-Authority-Reason: nr=8 X-Authority-Analysis: v=2.4 cv=ELjDb3VC c=1 sm=1 tr=0 ts=643035f6 a=ApxJNpeYhEAb1aAlGBBbmA==:117 a=ApxJNpeYhEAb1aAlGBBbmA==:17 a=dLZJa+xiwSxG16/P+YVxDGlgEgI=:19 a=IkcTkHD0fZMA:10:nop_charset_1 a=dKHAf1wccvYA:10:nop_rcvd_month_year a=Qbun_eYptAEA:10:endurance_base64_authed_username_1 a=5liizJNXi3Bc9PMnLVwA:9 a=QEXdDO2ut3YA:10:nop_charset_2 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tromey.com; s=default; h=To:In-Reply-To:References:Message-Id:Content-Transfer-Encoding: Content-Type:MIME-Version:Subject:Date:From:Sender:Reply-To:Cc:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=XXANQq1G9cogOfEmQyaNfDya5ShGebzeqeuWAdnMU5k=; b=kLyuGAedT2bUrkngUTnxGx5hxG rKtPr1xNjfjKw+AMVrHyvdYgHSOE/A13YL7OSyA9daSRJdb1Kpu636ikG998KiF1z633P5xf9rNt2 WanWgSV4N/yU+15BASjn5Szgb; Received: from 75-166-159-36.hlrn.qwest.net ([75.166.159.36]:60392 helo=[192.168.0.21]) by box5379.bluehost.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1pknyA-001hDU-HE for gdb-patches@sourceware.org; Fri, 07 Apr 2023 09:25:42 -0600 From: Tom Tromey Date: Fri, 07 Apr 2023 09:25:48 -0600 Subject: [PATCH 16/19] Convert typedef hash to new hash table MIME-Version: 1.0 Message-Id: <20230407-t-robin-hood-hash-v1-16-900d93ef1510@tromey.com> References: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> In-Reply-To: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> To: gdb-patches@sourceware.org X-Mailer: b4 0.12.1 X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - box5379.bluehost.com X-AntiAbuse: Original Domain - sourceware.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - tromey.com X-BWhitelist: no X-Source-IP: 75.166.159.36 X-Source-L: No X-Exim-ID: 1pknyA-001hDU-HE X-Source: X-Source-Args: X-Source-Dir: X-Source-Sender: 75-166-159-36.hlrn.qwest.net ([192.168.0.21]) [75.166.159.36]:60392 X-Source-Auth: tom+tromey.com X-Email-Count: 17 X-Source-Cap: ZWx5bnJvYmk7ZWx5bnJvYmk7Ym94NTM3OS5ibHVlaG9zdC5jb20= X-Local-Domain: yes X-Spam-Status: No, score=-3026.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, JMQ_SPF_NEUTRAL, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gdb-patches-bounces+patchwork=sourceware.org@sourceware.org Sender: "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, -/* 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 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 m_table; /* Storage for typedef_field objects that must be synthesized. */ auto_obstack m_storage; From patchwork Fri Apr 7 15:25:49 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom Tromey X-Patchwork-Id: 67515 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 5988C3882042 for ; Fri, 7 Apr 2023 15:27:52 +0000 (GMT) X-Original-To: gdb-patches@sourceware.org Delivered-To: gdb-patches@sourceware.org Received: from gproxy1-pub.mail.unifiedlayer.com (gproxy1-pub.mail.unifiedlayer.com [69.89.25.95]) by sourceware.org (Postfix) with ESMTPS id 7CEC63858412 for ; Fri, 7 Apr 2023 15:25:43 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 7CEC63858412 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=tromey.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=tromey.com Received: from cmgw12.mail.unifiedlayer.com (unknown [10.0.90.127]) by progateway3.mail.pro1.eigbox.com (Postfix) with ESMTP id D87E710047D9C for ; Fri, 7 Apr 2023 15:25:42 +0000 (UTC) Received: from box5379.bluehost.com ([162.241.216.53]) by cmsmtp with ESMTP id knyApLk6DChTwknyAplpX9; Fri, 07 Apr 2023 15:25:42 +0000 X-Authority-Reason: nr=8 X-Authority-Analysis: v=2.4 cv=BK12EHcG c=1 sm=1 tr=0 ts=643035f6 a=ApxJNpeYhEAb1aAlGBBbmA==:117 a=ApxJNpeYhEAb1aAlGBBbmA==:17 a=dLZJa+xiwSxG16/P+YVxDGlgEgI=:19 a=IkcTkHD0fZMA:10:nop_charset_1 a=dKHAf1wccvYA:10:nop_rcvd_month_year a=Qbun_eYptAEA:10:endurance_base64_authed_username_1 a=-Qg8vedUpOfewEj0WjoA:9 a=QEXdDO2ut3YA:10:nop_charset_2 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tromey.com; s=default; h=To:In-Reply-To:References:Message-Id:Content-Transfer-Encoding: Content-Type:MIME-Version:Subject:Date:From:Sender:Reply-To:Cc:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=3twPf7u5lY2DJgwsKXcbP1Kh/Qo5jStaLH1DGFzPaUg=; b=xfVpdvRhagpeWR7evqiIDsx3kW gGVCGbsUgzCMfWx3Ps4QxQlMX6Ho13naNmKtqQiGmnwgm19sgCCiZtqXhR9HmUg9gNyFWj4IdVzfd rx2EsXYcMVY6XJpgusPaIT0jw; Received: from 75-166-159-36.hlrn.qwest.net ([75.166.159.36]:60392 helo=[192.168.0.21]) by box5379.bluehost.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1pknyA-001hDU-ML for gdb-patches@sourceware.org; Fri, 07 Apr 2023 09:25:42 -0600 From: Tom Tromey Date: Fri, 07 Apr 2023 09:25:49 -0600 Subject: [PATCH 17/19] Convert all_bfds to new hash table MIME-Version: 1.0 Message-Id: <20230407-t-robin-hood-hash-v1-17-900d93ef1510@tromey.com> References: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> In-Reply-To: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> To: gdb-patches@sourceware.org X-Mailer: b4 0.12.1 X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - box5379.bluehost.com X-AntiAbuse: Original Domain - sourceware.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - tromey.com X-BWhitelist: no X-Source-IP: 75.166.159.36 X-Source-L: No X-Exim-ID: 1pknyA-001hDU-ML X-Source: X-Source-Args: X-Source-Dir: X-Source-Sender: 75-166-159-36.hlrn.qwest.net ([192.168.0.21]) [75.166.159.36]:60392 X-Source-Auth: tom+tromey.com X-Email-Count: 18 X-Source-Cap: ZWx5bnJvYmk7ZWx5bnJvYmk7Ym94NTM3OS5ibHVlaG9zdC5jb20= X-Local-Domain: yes X-Spam-Status: No, score=-3026.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, JMQ_SPF_NEUTRAL, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gdb-patches-bounces+patchwork=sourceware.org@sourceware.org Sender: "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 +#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 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 } From patchwork Fri Apr 7 15:25:50 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom Tromey X-Patchwork-Id: 67514 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 0B1C03882020 for ; Fri, 7 Apr 2023 15:27:47 +0000 (GMT) X-Original-To: gdb-patches@sourceware.org Delivered-To: gdb-patches@sourceware.org Received: from outbound-ss-761.bluehost.com (outbound-ss-761.bluehost.com [74.220.211.250]) by sourceware.org (Postfix) with ESMTPS id 9836D3858416 for ; Fri, 7 Apr 2023 15:25:43 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 9836D3858416 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=tromey.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=tromey.com Received: from cmgw12.mail.unifiedlayer.com (unknown [10.0.90.127]) by progateway8.mail.pro1.eigbox.com (Postfix) with ESMTP id 02C311003E989 for ; Fri, 7 Apr 2023 15:25:43 +0000 (UTC) Received: from box5379.bluehost.com ([162.241.216.53]) by cmsmtp with ESMTP id knyApLk6MChTwknyAplpXI; Fri, 07 Apr 2023 15:25:42 +0000 X-Authority-Reason: nr=8 X-Authority-Analysis: v=2.4 cv=BK12EHcG c=1 sm=1 tr=0 ts=643035f6 a=ApxJNpeYhEAb1aAlGBBbmA==:117 a=ApxJNpeYhEAb1aAlGBBbmA==:17 a=dLZJa+xiwSxG16/P+YVxDGlgEgI=:19 a=IkcTkHD0fZMA:10:nop_charset_1 a=dKHAf1wccvYA:10:nop_rcvd_month_year a=Qbun_eYptAEA:10:endurance_base64_authed_username_1 a=FQqm291_FjzXRzvnCggA:9 a=QEXdDO2ut3YA:10:nop_charset_2 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tromey.com; s=default; h=To:In-Reply-To:References:Message-Id:Content-Transfer-Encoding: Content-Type:MIME-Version:Subject:Date:From:Sender:Reply-To:Cc:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=XiNLLP12xFpgrqcMaBVgUzlyME/94edL2r50zEQ3meI=; b=qwwcyIt7auaXyPjAYjb9CfXx8g wSKjKC7qGJkJ4PMoljzprZCrH1BZAYvBJkG9ql6sDTAPb7TOyTVKpDOXa/aM1vL/x9EWjH13Weg5L Fb2ueFgBFQNzTDSeH6dqOk7fn; Received: from 75-166-159-36.hlrn.qwest.net ([75.166.159.36]:60392 helo=[192.168.0.21]) by box5379.bluehost.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1pknyA-001hDU-Qr for gdb-patches@sourceware.org; Fri, 07 Apr 2023 09:25:42 -0600 From: Tom Tromey Date: Fri, 07 Apr 2023 09:25:50 -0600 Subject: [PATCH 18/19] Convert more DWARF code to new hash table MIME-Version: 1.0 Message-Id: <20230407-t-robin-hood-hash-v1-18-900d93ef1510@tromey.com> References: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> In-Reply-To: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> To: gdb-patches@sourceware.org X-Mailer: b4 0.12.1 X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - box5379.bluehost.com X-AntiAbuse: Original Domain - sourceware.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - tromey.com X-BWhitelist: no X-Source-IP: 75.166.159.36 X-Source-L: No X-Exim-ID: 1pknyA-001hDU-Qr X-Source: X-Source-Args: X-Source-Dir: X-Source-Sender: 75-166-159-36.hlrn.qwest.net ([192.168.0.21]) [75.166.159.36]:60392 X-Source-Auth: tom+tromey.com X-Email-Count: 19 X-Source-Cap: ZWx5bnJvYmk7ZWx5bnJvYmk7Ym94NTM3OS5ibHVlaG9zdC5jb20= X-Local-Domain: yes X-Spam-Status: No, score=-3026.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, JMQ_SPF_NEUTRAL, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gdb-patches-bounces+patchwork=sourceware.org@sourceware.org Sender: "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 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 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 visited_found; + gdb::hash_set 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 *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 *result, + gdb::hash_set &all_children, + gdb::hash_set &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 *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 all_children; + gdb::hash_set 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); } From patchwork Fri Apr 7 15:25:51 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom Tromey X-Patchwork-Id: 67512 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 9BBB03852744 for ; Fri, 7 Apr 2023 15:27:35 +0000 (GMT) X-Original-To: gdb-patches@sourceware.org Delivered-To: gdb-patches@sourceware.org Received: from gproxy4-pub.mail.unifiedlayer.com (gproxy4-pub.mail.unifiedlayer.com [69.89.23.142]) by sourceware.org (Postfix) with ESMTPS id B3BC63858421 for ; Fri, 7 Apr 2023 15:25:43 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org B3BC63858421 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=tromey.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=tromey.com Received: from cmgw12.mail.unifiedlayer.com (unknown [10.0.90.127]) by progateway6.mail.pro1.eigbox.com (Postfix) with ESMTP id 1F6AA1004954F for ; Fri, 7 Apr 2023 15:25:43 +0000 (UTC) Received: from box5379.bluehost.com ([162.241.216.53]) by cmsmtp with ESMTP id knyBpLk6QChTwknyBplpXM; Fri, 07 Apr 2023 15:25:43 +0000 X-Authority-Reason: nr=8 X-Authority-Analysis: v=2.4 cv=BK12EHcG c=1 sm=1 tr=0 ts=643035f7 a=ApxJNpeYhEAb1aAlGBBbmA==:117 a=ApxJNpeYhEAb1aAlGBBbmA==:17 a=dLZJa+xiwSxG16/P+YVxDGlgEgI=:19 a=IkcTkHD0fZMA:10:nop_charset_1 a=dKHAf1wccvYA:10:nop_rcvd_month_year a=Qbun_eYptAEA:10:endurance_base64_authed_username_1 a=sbcTgWqzmVlm1C441K8A:9 a=QEXdDO2ut3YA:10:nop_charset_2 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tromey.com; s=default; h=To:In-Reply-To:References:Message-Id:Content-Transfer-Encoding: Content-Type:MIME-Version:Subject:Date:From:Sender:Reply-To:Cc:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=S3epSMILyZ4VzkJTifoSjbLMRjOyLC8Lv7KyOgIxNp8=; b=wzWiuazWVi+plkobD/t4Stufxx usuUHDsUUQj9Spca5Hz8aoZJ+cdmSXimiuQwxithTWJaEcu8MpmxtnyZYu59ps34huxDhOO54/2EV Qb8lQUGE9fk72/5EIJd8WbM32; Received: from 75-166-159-36.hlrn.qwest.net ([75.166.159.36]:60392 helo=[192.168.0.21]) by box5379.bluehost.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1pknyA-001hDU-VK for gdb-patches@sourceware.org; Fri, 07 Apr 2023 09:25:42 -0600 From: Tom Tromey Date: Fri, 07 Apr 2023 09:25:51 -0600 Subject: [PATCH 19/19] Convert gdb_bfd.c to new hash table MIME-Version: 1.0 Message-Id: <20230407-t-robin-hood-hash-v1-19-900d93ef1510@tromey.com> References: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> In-Reply-To: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> To: gdb-patches@sourceware.org X-Mailer: b4 0.12.1 X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - box5379.bluehost.com X-AntiAbuse: Original Domain - sourceware.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - tromey.com X-BWhitelist: no X-Source-IP: 75.166.159.36 X-Source-L: No X-Exim-ID: 1pknyA-001hDU-VK X-Source: X-Source-Args: X-Source-Dir: X-Source-Sender: 75-166-159-36.hlrn.qwest.net ([192.168.0.21]) [75.166.159.36]:60392 X-Source-Auth: tom+tromey.com X-Email-Count: 20 X-Source-Cap: ZWx5bnJvYmk7ZWx5bnJvYmk7Ym94NTM3OS5ibHVlaG9zdC5jb20= X-Local-Domain: yes X-Spam-Status: No, score=-3026.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, JMQ_SPF_NEUTRAL, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gdb-patches-bounces+patchwork=sourceware.org@sourceware.org Sender: "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::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; /* 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. */