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 */