{"id":2226194,"url":"http://patchwork.ozlabs.org/api/patches/2226194/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhub8n5f78.gcc.gcc-TEST.redi.15.1.4@forge-stage.sourceware.org/","project":{"id":17,"url":"http://patchwork.ozlabs.org/api/projects/17/?format=json","name":"GNU Compiler Collection","link_name":"gcc","list_id":"gcc-patches.gcc.gnu.org","list_email":"gcc-patches@gcc.gnu.org","web_url":null,"scm_url":null,"webscm_url":null,"list_archive_url":"","list_archive_url_format":"","commit_url_format":""},"msgid":"","list_archive_url":null,"date":"2026-04-22T10:25:13","name":"[v1,04/12] libstdc++: Refactor Hashtable erasure","commit_ref":null,"pull_url":null,"state":"new","archived":false,"hash":"27d0e4c81421065988a847ea33f8d68299321696","submitter":{"id":93210,"url":"http://patchwork.ozlabs.org/api/people/93210/?format=json","name":"Jonathan Wakely via Sourceware Forge","email":"forge-bot+redi@forge-stage.sourceware.org"},"delegate":null,"mbox":"http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhub8n5f78.gcc.gcc-TEST.redi.15.1.4@forge-stage.sourceware.org/mbox/","series":[{"id":500966,"url":"http://patchwork.ozlabs.org/api/series/500966/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/list/?series=500966","date":"2026-04-22T10:25:11","name":"WIP: libstdc++: Refactor hash table code","version":1,"mbox":"http://patchwork.ozlabs.org/series/500966/mbox/"}],"comments":"http://patchwork.ozlabs.org/api/patches/2226194/comments/","check":"pending","checks":"http://patchwork.ozlabs.org/api/patches/2226194/checks/","tags":{},"related":[],"headers":{"Return-Path":"","X-Original-To":["incoming@patchwork.ozlabs.org","gcc-patches@gcc.gnu.org"],"Delivered-To":["patchwork-incoming@legolas.ozlabs.org","gcc-patches@gcc.gnu.org"],"Authentication-Results":["legolas.ozlabs.org;\n spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org\n (client-ip=2620:52:6:3111::32; helo=vm01.sourceware.org;\n envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org;\n receiver=patchwork.ozlabs.org)","sourceware.org; dmarc=none (p=none dis=none)\n header.from=forge-stage.sourceware.org","sourceware.org;\n spf=pass smtp.mailfrom=forge-stage.sourceware.org","server2.sourceware.org;\n arc=none smtp.remote-ip=38.145.34.39"],"Received":["from vm01.sourceware.org (vm01.sourceware.org\n [IPv6:2620:52:6:3111::32])\n\t(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)\n\t key-exchange x25519 server-signature ECDSA (secp384r1) server-digest SHA384)\n\t(No client certificate requested)\n\tby legolas.ozlabs.org (Postfix) with ESMTPS id 4g0wdh4bkQz1yD5\n\tfor ; Wed, 22 Apr 2026 20:37:12 +1000 (AEST)","from vm01.sourceware.org (localhost [127.0.0.1])\n\tby sourceware.org (Postfix) with ESMTP id 77C214315731\n\tfor ; Wed, 22 Apr 2026 10:37:03 +0000 (GMT)","from forge-stage.sourceware.org (vm08.sourceware.org [38.145.34.39])\n by sourceware.org (Postfix) with ESMTPS id 124BF4BBCD88\n for ; Wed, 22 Apr 2026 10:26:15 +0000 (GMT)","from forge-stage.sourceware.org (localhost [IPv6:::1])\n (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)\n key-exchange x25519 server-signature ECDSA (prime256v1) server-digest SHA256)\n (No client certificate requested)\n by forge-stage.sourceware.org (Postfix) with ESMTPS id E1D2E405A3\n for ; Wed, 22 Apr 2026 10:26:14 +0000 (UTC)"],"DKIM-Filter":["OpenDKIM Filter v2.11.0 sourceware.org 77C214315731","OpenDKIM Filter v2.11.0 sourceware.org 124BF4BBCD88"],"DMARC-Filter":"OpenDMARC Filter v1.4.2 sourceware.org 124BF4BBCD88","ARC-Filter":"OpenARC Filter v1.0.0 sourceware.org 124BF4BBCD88","ARC-Seal":"i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1776853575; cv=none;\n b=T2pf8PhfJ7N5b9sHtRsgfTxRC61Yb8lNoX/TLvrsaVPsA1iyzNhvRCWSPt/PfrdeS/vopSPQcWTnqui41ROk/Lld0yjB9m5GIv0NlQryfztipAGjPIsDNGCuJBvvpqWMjsFGzWQ7oxizomNJOIr56TrT682b0knFj2dPXtlIt2M=","ARC-Message-Signature":"i=1; a=rsa-sha256; d=sourceware.org; s=key;\n t=1776853575; c=relaxed/simple;\n bh=y32drPMTmyOsUOPwd+wWEMJbvs3yzXdUjeicOUZLC98=;\n h=From:Date:Subject:MIME-Version:To:Message-ID;\n b=KKP4oK9XlN3aqo1kgeVEEXaVwzesXUeGqWwqsipKrzKYgI6lqyxAkGRK2Nw6YrAnF0+oxJ3aawBnCFGmQS+vR19hy3RNxRtgaY69XouLebraXn4cAenvRvRicMj8DY7PktliTr5WwztQJEQrWtqmiCrS6eARU3lfPGvYZudO5H8=","ARC-Authentication-Results":"i=1; server2.sourceware.org","From":"Jonathan Wakely via Sourceware Forge\n ","Date":"Wed, 22 Apr 2026 10:25:13 +0000","Subject":"[PATCH v1 04/12] libstdc++: Refactor Hashtable erasure","MIME-Version":"1.0","Content-Type":"text/plain; charset=UTF-8","Content-Transfer-Encoding":"8bit","To":"gcc-patches mailing list ","Message-ID":"\n ","X-Mailer":"batrachomyomachia","X-Requested-Reviewer":"fdumont","X-Pull-Request-Organization":"gcc","X-Pull-Request-Repository":"gcc-TEST","X-Pull-Request":"https://forge.sourceware.org/gcc/gcc-TEST/pulls/15","References":"\n ","In-Reply-To":"\n ","X-Patch-URL":"\n https://forge.sourceware.org/redi/gcc/commit/d7a6ec5e20a4e17d87fa7e253787853fe8445ac2","X-BeenThere":"gcc-patches@gcc.gnu.org","X-Mailman-Version":"2.1.30","Precedence":"list","List-Id":"Gcc-patches mailing list ","List-Unsubscribe":",\n ","List-Archive":"","List-Post":"","List-Help":"","List-Subscribe":",\n ","Reply-To":"gcc-patches mailing list , redi@gcc.gnu.org","Errors-To":"gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org"},"content":"From: Jonathan Wakely \n\nThis reworks the internal member functions for erasure from\nunordered containers, similarly to the earlier commit doing it for\ninsertion.\n\nInstead of multiple overloads of _M_erase which are selected via tag\ndispatching, the erase(const key_type&) member can use 'if constexpr' to\nchoose an appropriate implementation (returning after erasing a single\nelement for unique keys, or continuing to erase all equivalent elements\nfor non-unique keys).\n\nlibstdc++-v3/ChangeLog:\n\n\t* include/bits/hashtable.h (_Hashtable::_M_erase): Remove\n\toverloads for erasing by key, moving logic to ...\n\t(_Hashtable::erase): ... here.\n\nReviewed-by: François Dumont \n---\n libstdc++-v3/include/bits/hashtable.h | 113 +++++++++-----------------\n 1 file changed, 39 insertions(+), 74 deletions(-)","diff":"diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h\nindex eeffa15e5259..23484f711cc5 100644\n--- a/libstdc++-v3/include/bits/hashtable.h\n+++ b/libstdc++-v3/include/bits/hashtable.h\n@@ -955,12 +955,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \titerator\n \t_M_emplace_multi(const_iterator, _Args&&... __args);\n \n- size_type\n- _M_erase(true_type __uks, const key_type&);\n-\n- size_type\n- _M_erase(false_type __uks, const key_type&);\n-\n iterator\n _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n);\n \n@@ -1002,8 +996,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n { return erase(const_iterator(__it)); }\n \n size_type\n- erase(const key_type& __k)\n- { return _M_erase(__unique_keys{}, __k); }\n+ erase(const key_type& __k);\n \n iterator\n erase(const_iterator, const_iterator);\n@@ -2372,6 +2365,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n return __result;\n }\n \n+#pragma GCC diagnostic push\n+#pragma GCC diagnostic ignored \"-Wc++17-extensions\" // if constexpr\n template::\n- _M_erase(true_type /* __uks */, const key_type& __k)\n+ erase(const key_type& __k)\n -> size_type\n {\n __node_base_ptr __prev_n;\n@@ -2409,77 +2404,47 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t __n = static_cast<__node_ptr>(__prev_n->_M_nxt);\n \t}\n \n- _M_erase(__bkt, __prev_n, __n);\n- return 1;\n- }\n-\n- template\n- auto\n- _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,\n-\t _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::\n- _M_erase(false_type /* __uks */, const key_type& __k)\n- -> size_type\n- {\n- std::size_t __bkt;\n- __node_base_ptr __prev_n;\n- __node_ptr __n;\n- if (size() <= __small_size_threshold())\n+ if constexpr (__unique_keys::value)\n \t{\n-\t __prev_n = _M_find_before_node(__k);\n-\t if (!__prev_n)\n-\t return 0;\n-\n-\t // We found a matching node, erase it.\n-\t __n = static_cast<__node_ptr>(__prev_n->_M_nxt);\n-\t __bkt = _M_bucket_index(*__n);\n+\t _M_erase(__bkt, __prev_n, __n);\n+\t return 1;\n \t}\n else\n \t{\n-\t __hash_code __code = this->_M_hash_code(__k);\n-\t __bkt = _M_bucket_index(__code);\n-\n-\t // Look for the node before the first matching node.\n-\t __prev_n = _M_find_before_node(__bkt, __k, __code);\n-\t if (!__prev_n)\n-\t return 0;\n-\n-\t __n = static_cast<__node_ptr>(__prev_n->_M_nxt);\n-\t}\n-\n- // _GLIBCXX_RESOLVE_LIB_DEFECTS\n- // 526. Is it undefined if a function in the standard changes\n- // in parameters?\n- // We use one loop to find all matching nodes and another to deallocate\n- // them so that the key stays valid during the first loop. It might be\n- // invalidated indirectly when destroying nodes.\n- __node_ptr __n_last = __n->_M_next();\n- while (__n_last && this->_M_node_equals(*__n, *__n_last))\n-\t__n_last = __n_last->_M_next();\n-\n- std::size_t __n_last_bkt = __n_last ? _M_bucket_index(*__n_last) : __bkt;\n-\n- // Deallocate nodes.\n- size_type __result = 0;\n- do\n-\t{\n-\t __node_ptr __p = __n->_M_next();\n-\t this->_M_deallocate_node(__n);\n-\t __n = __p;\n-\t ++__result;\n+\t // _GLIBCXX_RESOLVE_LIB_DEFECTS\n+\t // 526. Is it undefined if a function in the standard changes\n+\t // in parameters?\n+\t // We use one loop to find all matching nodes and another to\n+\t // deallocate them so that the key stays valid during the first loop.\n+\t // It might be invalidated indirectly when destroying nodes.\n+\t __node_ptr __n_last = __n->_M_next();\n+\t while (__n_last && this->_M_node_equals(*__n, *__n_last))\n+\t __n_last = __n_last->_M_next();\n+\n+\t std::size_t __n_last_bkt\n+\t = __n_last ? _M_bucket_index(*__n_last) : __bkt;\n+\n+\t // Deallocate nodes.\n+\t size_type __result = 0;\n+\t do\n+\t {\n+\t __node_ptr __p = __n->_M_next();\n+\t this->_M_deallocate_node(__n);\n+\t __n = __p;\n+\t ++__result;\n+\t }\n+\t while (__n != __n_last);\n+\n+\t _M_element_count -= __result;\n+\t if (__prev_n == _M_buckets[__bkt])\n+\t _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);\n+\t else if (__n_last_bkt != __bkt)\n+\t _M_buckets[__n_last_bkt] = __prev_n;\n+\t __prev_n->_M_nxt = __n_last;\n+\t return __result;\n \t}\n- while (__n != __n_last);\n-\n- _M_element_count -= __result;\n- if (__prev_n == _M_buckets[__bkt])\n-\t_M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);\n- else if (__n_last_bkt != __bkt)\n-\t_M_buckets[__n_last_bkt] = __prev_n;\n- __prev_n->_M_nxt = __n_last;\n- return __result;\n }\n+#pragma GCC diagnostic pop\n \n template