{"id":2226243,"url":"http://patchwork.ozlabs.org/api/1.1/patches/2226243/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhub8n5f78.gcc.gcc-TEST.redi.15.1.12@forge-stage.sourceware.org/","project":{"id":17,"url":"http://patchwork.ozlabs.org/api/1.1/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},"msgid":"","date":"2026-04-22T10:25:21","name":"[v1,12/12] libstdc++: Add _Hashtable::_M_locate(const key_type&)","commit_ref":null,"pull_url":null,"state":"new","archived":false,"hash":"a5a2ddc855b02f36147aa7012858daac473b158c","submitter":{"id":93210,"url":"http://patchwork.ozlabs.org/api/1.1/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.12@forge-stage.sourceware.org/mbox/","series":[{"id":500966,"url":"http://patchwork.ozlabs.org/api/1.1/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/2226243/comments/","check":"pending","checks":"http://patchwork.ozlabs.org/api/patches/2226243/checks/","tags":{},"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 4g0wqf6fYyz1yHB\n\tfor ; Wed, 22 Apr 2026 20:45:50 +1000 (AEST)","from vm01.sourceware.org (localhost [127.0.0.1])\n\tby sourceware.org (Postfix) with ESMTP id 6BB104015E88\n\tfor ; Wed, 22 Apr 2026 10:45:48 +0000 (GMT)","from forge-stage.sourceware.org (vm08.sourceware.org [38.145.34.39])\n by sourceware.org (Postfix) with ESMTPS id 1A2304BBCDDA\n for ; Wed, 22 Apr 2026 10:26:20 +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 5B13A405AB\n for ; Wed, 22 Apr 2026 10:26:15 +0000 (UTC)"],"DKIM-Filter":["OpenDKIM Filter v2.11.0 sourceware.org 6BB104015E88","OpenDKIM Filter v2.11.0 sourceware.org 1A2304BBCDDA"],"DMARC-Filter":"OpenDMARC Filter v1.4.2 sourceware.org 1A2304BBCDDA","ARC-Filter":"OpenARC Filter v1.0.0 sourceware.org 1A2304BBCDDA","ARC-Seal":"i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1776853580; cv=none;\n b=MGXWvuGgHGOOFX9VWnrVTfRsyolIJudhpkz3ZO5jwVdFcaB8J9SRx4v2XDX4NL34iNNPZqhrWq/9ziv5vKvb/SzzuUrnItY4L7XyHichZVHtvFHFCkfOYSvolTcR1WMFbDhjQ3cCiv9acqUpUFZqS2Hz34Rv2M5KCExya1G1tLs=","ARC-Message-Signature":"i=1; a=rsa-sha256; d=sourceware.org; s=key;\n t=1776853580; c=relaxed/simple;\n bh=2JsfkON01B7B22OQgIuGD84DYJ1Nb+a6kH+MmwJ5n7U=;\n h=From:Date:Subject:To:Message-ID;\n b=d7B3zj/+4hqIMurOxPnNSJZks7UwXGQYv87mAjPWUQU1daH/g85emA7Twab5n5UBnKHJZ0zztRrZoj/5eMNsYy9PS6YJPW/d26Afim3ACKaUjJQylQpL+6EZfJoVvKexzslneuTLR4agMphGQwL2pDwrbhrpJNEafIty7DATEsM=","ARC-Authentication-Results":"i=1; server2.sourceware.org","From":"Jonathan Wakely via Sourceware Forge\n ","Date":"Wed, 22 Apr 2026 10:25:21 +0000","Subject":"[PATCH v1 12/12] libstdc++: Add _Hashtable::_M_locate(const\n key_type&)","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/49b7f6d1492cc2aebc1454cbd5a2ff3f546d4cf4","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\nWe have two overloads of _M_find_before_node but they have quite\ndifferent performance characteristics, which isn't necessarily obvious.\n\nThe original version, _M_find_before_node(bucket, key, hash_code), looks\nonly in the specified bucket, doing a linear search within that bucket\nfor an element that compares equal to the key. This is the typical fast\nlookup for hash containers, assuming the load factor is low so that each\nbucket isn't too large.\n\nThe newer _M_find_before_node(key) was added in r12-6272-ge3ef832a9e8d6a\nand could be naively assumed to calculate the hash code and bucket for\nkey and then call the efficient _M_find_before_node(bkt, key, code)\nfunction. But in fact it does a linear search of the entire container.\nThis is potentially very slow and should only be used for a suitably\nsmall container, as determined by the __small_size_threshold() function.\nWe don't even have a comment pointing out this O(N) performance of the\nnewer overload.\n\nAdditionally, the newer overload is only ever used in exactly one place,\nwhich would suggest it could just be removed. However there are several\nplaces that do the linear search of the whole container with an explicit\nloop each time.\n\nThis adds a new member function, _M_locate, and uses it to replace most\nuses of _M_find_node and the loops doing linear searches. This new\nmember function does both forms of lookup, the linear search for small\nsizes and the _M_find_node(bkt, key, code) lookup within a single\nbucket. The new function returns a __location_type which is a struct\nthat contains a pointer to the first node matching the key (if such a\nnode is present), or the hash code and bucket index for the key. The\nhash code and bucket index allow the caller to know where a new node\nwith that key should be inserted, for the cases where the lookup didn't\nfind a matching node.\n\nThe result struct actually contains a pointer to the node *before* the\none that was located, as that is needed for it to be useful in erase and\nextract members. There is a member function that returns the found node,\ni.e. _M_before->_M_nxt downcast to __node_ptr, which should be used in\nmost cases.\n\nThis new function greatly simplifies the functions that currently have\nto do two kinds of lookup and explicitly check the current size against\nthe small size threshold.\n\nAdditionally, now that try_emplace is defined directly in _Hashtable\n(not in _Insert_base) we can use _M_locate in there too, to speed up\nsome try_emplace calls. Previously it did not do the small-size linear\nsearch.\n\nIt would be possible to add a function to get a __location_type from an\niterator, and then rewrite some functions like _M_erase and\n_M_extract_node to take a __location_type parameter. While that might be\nconceptually nice, it wouldn't really make the code any simpler or more\nreadable than it is now. That isn't done in this change.\n\nlibstdc++-v3/ChangeLog:\n\n\t* include/bits/hashtable.h (__location_type): New struct.\n\t(_M_locate): New member function.\n\t(_M_find_before_node(const key_type&)): Remove.\n\t(_M_find_node): Move variable initialization into condition.\n\t(_M_find_node_tr): Likewise.\n\t(operator=(initializer_list), try_emplace, _M_reinsert_node)\n\t(_M_merge_unique, find, erase(const key_type&)): Use _M_locate\n\tfor lookup.\n---\n libstdc++-v3/include/bits/hashtable.h | 333 +++++++++++---------------\n 1 file changed, 145 insertions(+), 188 deletions(-)","diff":"diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h\nindex aca431ae216f..6a2da121ab98 100644\n--- a/libstdc++-v3/include/bits/hashtable.h\n+++ b/libstdc++-v3/include/bits/hashtable.h\n@@ -596,28 +596,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \tif (_M_bucket_count < __l_bkt_count)\n \t rehash(__l_bkt_count);\n \n-\t_ExtractKey __ex;\n+\t__hash_code __code;\n+\tsize_type __bkt;\n \tfor (auto& __e : __l)\n \t {\n-\t const key_type& __k = __ex(__e);\n+\t const key_type& __k = _ExtractKey{}(__e);\n \n \t if constexpr (__unique_keys::value)\n-\t if (this->size() <= __small_size_threshold())\n-\t\t{\n-\t\t auto __it = _M_begin();\n-\t\t for (; __it; __it = __it->_M_next())\n-\t\t if (this->_M_key_equals(__k, *__it))\n-\t\t break;\n-\t\t if (__it)\n-\t\t continue; // Found existing element with equivalent key\n-\t\t}\n-\n-\t __hash_code __code = this->_M_hash_code(__k);\n-\t size_type __bkt = _M_bucket_index(__code);\n-\n-\t if constexpr (__unique_keys::value)\n-\t if (_M_find_node(__bkt, __k, __code))\n-\t\tcontinue; // Found existing element with equivalent key\n+\t {\n+\t\tif (auto __loc = _M_locate(__k))\n+\t\t continue; // Found existing element with equivalent key\n+\t\telse\n+\t\t {\n+\t\t __code = __loc._M_hash_code;\n+\t\t __bkt = __loc._M_bucket_index;\n+\t\t }\n+\t }\n+\t else\n+\t {\n+\t\t__code = this->_M_hash_code(__k);\n+\t\t__bkt = _M_bucket_index(__code);\n+\t }\n \n \t _M_insert_unique_node(__bkt, __code, __roan(__e));\n \t }\n@@ -809,10 +808,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n _M_bucket_index(__hash_code __c) const\n { return __hash_code_base::_M_bucket_index(__c, _M_bucket_count); }\n \n- __node_base_ptr\n- _M_find_before_node(const key_type&);\n-\n // Find and insert helper functions and types\n+\n // Find the node before the one matching the criteria.\n __node_base_ptr\n _M_find_before_node(size_type, const key_type&, __hash_code) const;\n@@ -821,12 +818,57 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t__node_base_ptr\n \t_M_find_before_node_tr(size_type, const _Kt&, __hash_code) const;\n \n+ // A pointer to a particular node and/or a hash code and bucket index\n+ // where such a node would be found in the container.\n+ struct __location_type\n+ {\n+\t// True if _M_node() is a valid node pointer.\n+\texplicit operator bool() const noexcept\n+\t{ return static_cast(_M_before); }\n+\n+\t// An iterator that refers to the node, or end().\n+\texplicit operator iterator() const noexcept\n+\t{ return iterator(_M_node()); }\n+\n+\t// A const_iterator that refers to the node, or cend().\n+\texplicit operator const_iterator() const noexcept\n+\t{ return const_iterator(_M_node()); }\n+\n+\t// A pointer to the node, or null.\n+\t__node_ptr _M_node() const\n+\t{\n+\t if (_M_before)\n+\t return static_cast<__node_ptr>(_M_before->_M_nxt);\n+\t return __node_ptr();\n+\t}\n+\n+\t__node_base_ptr _M_before{}; // Must only be used to get _M_nxt\n+\t__hash_code _M_hash_code{}; // Only valid if _M_bucket_index != -1\n+\tsize_type _M_bucket_index = size_type(-1);\n+ };\n+\n+ // Adaptive lookup to find key, or which bucket it would be in.\n+ // For a container smaller than the small size threshold use a linear\n+ // search through the whole container, just testing for equality.\n+ // Otherwise, calculate the hash code and bucket index for the key,\n+ // and search in that bucket.\n+ // The return value will have a pointer to the node _before_ the first\n+ // node matching the key, if any such node exists. Returning the node\n+ // before the desired one allows the result to be used for erasure.\n+ // If no matching element is present, the hash code and bucket for the\n+ // key will be set, allowing a new node to be inserted at that location.\n+ // (The hash code and bucket might also be set when a node is found.)\n+ // The _M_before pointer might point to _M_before_begin, so must not be\n+ // cast to __node_ptr, and it must not be used to modify *_M_before\n+ // except in non-const member functions, such as erase.\n+ __location_type\n+ _M_locate(const key_type& __k) const;\n+\n __node_ptr\n _M_find_node(size_type __bkt, const key_type& __key,\n \t\t __hash_code __c) const\n {\n-\t__node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c);\n-\tif (__before_n)\n+\tif (__node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c))\n \t return static_cast<__node_ptr>(__before_n->_M_nxt);\n \treturn nullptr;\n }\n@@ -836,8 +878,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t_M_find_node_tr(size_type __bkt, const _Kt& __key,\n \t\t\t__hash_code __c) const\n \t{\n-\t auto __before_n = _M_find_before_node_tr(__bkt, __key, __c);\n-\t if (__before_n)\n+\t if (auto __before_n = _M_find_before_node_tr(__bkt, __key, __c))\n \t return static_cast<__node_ptr>(__before_n->_M_nxt);\n \t return nullptr;\n \t}\n@@ -1004,10 +1045,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \tstd::pair\n \ttry_emplace(const_iterator, _KType&& __k, _Args&&... __args)\n \t{\n-\t auto __code = this->_M_hash_code(__k);\n-\t std::size_t __bkt = _M_bucket_index(__code);\n-\t if (auto __node = _M_find_node(__bkt, __k, __code))\n-\t return { iterator(__node), false };\n+\t __hash_code __code;\n+\t size_type __bkt;\n+\t if (auto __loc = _M_locate(__k))\n+\t return { iterator(__loc), false };\n+\t else\n+\t {\n+\t __code = __loc._M_hash_code;\n+\t __bkt = __loc._M_bucket_index;\n+\t }\n \n \t _Scoped_node __node {\n \t this,\n@@ -1101,38 +1147,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t {\n \t __glibcxx_assert(get_allocator() == __nh.get_allocator());\n \n-\t __node_ptr __n = nullptr;\n-\t const key_type& __k = __nh._M_key();\n-\t const size_type __size = size();\n-\t if (__size <= __small_size_threshold())\n-\t {\n-\t\tfor (__n = _M_begin(); __n; __n = __n->_M_next())\n-\t\t if (this->_M_key_equals(__k, *__n))\n-\t\t break;\n-\t }\n-\n-\t __hash_code __code;\n-\t size_type __bkt;\n-\t if (!__n)\n-\t {\n-\t\t__code = this->_M_hash_code(__k);\n-\t\t__bkt = _M_bucket_index(__code);\n-\t\tif (__size > __small_size_threshold())\n-\t\t __n = _M_find_node(__bkt, __k, __code);\n-\t }\n-\n-\t if (__n)\n+\t if (auto __loc = _M_locate(__nh._M_key()))\n \t {\n \t\t__ret.node = std::move(__nh);\n-\t\t__ret.position = iterator(__n);\n+\t\t__ret.position = iterator(__loc);\n \t\t__ret.inserted = false;\n \t }\n \t else\n \t {\n+\t\tauto __code = __loc._M_hash_code;\n+\t\tauto __bkt = __loc._M_bucket_index;\n \t\t__ret.position\n-\t\t = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);\n-\t\t__nh.release();\n+\t\t = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);\n \t\t__ret.inserted = true;\n+\t\t__nh.release();\n \t }\n \t }\n \treturn __ret;\n@@ -1218,7 +1246,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n {\n \t__glibcxx_assert(get_allocator() == __src.get_allocator());\n \n-\tauto __size = size();\n \tauto __n_elt = __src.size();\n \tsize_type __first = 1;\n \t// For a container of identical type we can use its private members.\n@@ -1229,31 +1256,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t __p = __p->_M_next();\n \t const auto& __node = *__p;\n \t const key_type& __k = _ExtractKey{}(__node._M_v());\n-\t if (__size <= __small_size_threshold())\n-\t {\n-\t\tauto __n = _M_begin();\n-\t\tfor (; __n; __n = __n->_M_next())\n-\t\t if (this->_M_key_equals(__k, *__n))\n-\t\t break;\n-\t\tif (__n)\n-\t\t continue;\n-\t }\n-\n-\t __hash_code __code\n-\t = _M_src_hash_code(__src.hash_function(), __k, __node);\n-\t size_type __bkt = _M_bucket_index(__code);\n-\t if (__size > __small_size_threshold())\n-\t if (_M_find_node(__bkt, __k, __code) != nullptr)\n-\t\tcontinue;\n+\t auto __loc = _M_locate(__k);\n+\t if (__loc)\n+\t continue;\n \n-\t __hash_code __src_code = __src.hash_function()(__k);\n-\t size_type __src_bkt = __src._M_bucket_index(__src_code);\n+\t size_type __src_bkt\n+\t = __src._M_bucket_index(__src.hash_function()(__k));\n \t auto __nh = __src._M_extract_node(__src_bkt, __prev);\n-\t _M_insert_unique_node(__bkt, __code, __nh._M_ptr,\n-\t\t\t\t __first * __n_elt + 1);\n+\t _M_insert_unique_node(__loc._M_bucket_index, __loc._M_hash_code,\n+\t\t\t\t __nh._M_ptr, __first * __n_elt + 1);\n \t __nh.release();\n \t __first = 0;\n-\t ++__size;\n \t __p = __prev;\n \t }\n }\n@@ -1267,7 +1280,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t node_type>, \"Node types are compatible\");\n \t __glibcxx_assert(get_allocator() == __src.get_allocator());\n \n-\t auto __size = size();\n \t auto __n_elt = __src.size();\n \t size_type __first = 1;\n \t // For a compatible container we can only use the public API,\n@@ -1277,29 +1289,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t --__n_elt;\n \t auto __pos = __i++;\n \t const key_type& __k = _ExtractKey{}(*__pos);\n-\t if (__size <= __small_size_threshold())\n-\t\t{\n-\t\t auto __n = _M_begin();\n-\t\t for (; __n; __n = __n->_M_next())\n-\t\t if (this->_M_key_equals(__k, *__n))\n-\t\t break;\n-\t\t if (__n)\n-\t\t continue;\n-\t\t}\n-\n-\t __hash_code __code\n-\t\t= _M_src_hash_code(__src.hash_function(), __k, *__pos._M_cur);\n-\t size_type __bkt = _M_bucket_index(__code);\n-\t if (__size > __small_size_threshold())\n-\t\tif (_M_find_node(__bkt, __k, __code) != nullptr)\n-\t\t continue;\n+\t const auto __loc = _M_locate(__k);\n+\t if (__loc)\n+\t\tcontinue;\n \n \t auto __nh = __src.extract(__pos);\n-\t _M_insert_unique_node(__bkt, __code, __nh._M_ptr,\n+\t _M_insert_unique_node(__loc._M_bucket_index,\n+\t\t\t\t __loc._M_hash_code, __nh._M_ptr,\n \t\t\t\t __first * __n_elt + 1);\n \t __nh.release();\n \t __first = 0;\n-\t ++__size;\n \t }\n \t}\n \n@@ -1864,19 +1863,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::\n find(const key_type& __k)\n -> iterator\n- {\n- if (size() <= __small_size_threshold())\n-\t{\n-\t for (auto __it = _M_begin(); __it; __it = __it->_M_next())\n-\t if (this->_M_key_equals(__k, *__it))\n-\t return iterator(__it);\n-\t return end();\n-\t}\n-\n- __hash_code __code = this->_M_hash_code(__k);\n- std::size_t __bkt = _M_bucket_index(__code);\n- return iterator(_M_find_node(__bkt, __k, __code));\n- }\n+ { return iterator(_M_locate(__k)); }\n \n template::\n find(const key_type& __k) const\n -> const_iterator\n- {\n- if (size() <= __small_size_threshold())\n-\t{\n-\t for (auto __it = _M_begin(); __it; __it = __it->_M_next())\n-\t if (this->_M_key_equals(__k, *__it))\n-\t return const_iterator(__it);\n-\t return end();\n-\t}\n-\n- __hash_code __code = this->_M_hash_code(__k);\n- std::size_t __bkt = _M_bucket_index(__code);\n- return const_iterator(_M_find_node(__bkt, __k, __code));\n- }\n+ { return const_iterator(_M_locate(__k)); }\n \n #if __cplusplus > 201703L\n template\n- auto\n- _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,\n-\t _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::\n- _M_find_before_node(const key_type& __k)\n- -> __node_base_ptr\n- {\n- __node_base_ptr __prev_p = &_M_before_begin;\n- if (!__prev_p->_M_nxt)\n-\treturn nullptr;\n-\n- for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);\n-\t __p != nullptr;\n-\t __p = __p->_M_next())\n-\t{\n-\t if (this->_M_key_equals(__k, *__p))\n-\t return __prev_p;\n-\n-\t __prev_p = __p;\n-\t}\n-\n- return nullptr;\n- }\n-\n // Find the node before the one whose key compares equal to k in the bucket\n // bkt. Return nullptr if no node is found.\n template\n+ auto\n+ _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,\n+\t _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::\n+ _M_locate(const key_type& __k) const\n+ -> __location_type\n+ {\n+ __location_type __loc;\n+ const auto __size = size();\n+\n+ if (__size <= __small_size_threshold())\n+\t{\n+\t __loc._M_before = pointer_traits<__node_base_ptr>::\n+\t pointer_to(const_cast<__node_base&>(_M_before_begin));\n+\t while (__loc._M_before->_M_nxt)\n+\t {\n+\t if (this->_M_key_equals(__k, *__loc._M_node()))\n+\t\treturn __loc;\n+\t __loc._M_before = __loc._M_before->_M_nxt;\n+\t }\n+\t __loc._M_before = nullptr; // Didn't find it.\n+\t}\n+\n+ __loc._M_hash_code = this->_M_hash_code(__k);\n+ __loc._M_bucket_index = _M_bucket_index(__loc._M_hash_code);\n+\n+ if (__size > __small_size_threshold())\n+\t__loc._M_before = _M_find_before_node(__loc._M_bucket_index, __k,\n+\t\t\t\t\t __loc._M_hash_code);\n+\n+ return __loc;\n+ }\n+\n template_M_next())\n-\t if (this->_M_key_equals(*__kp, *__it))\n-\t\t// There is already an equivalent node, no insertion.\n-\t\treturn { iterator(__it), false };\n+\t __code = __loc._M_hash_code;\n+\t __bkt = __loc._M_bucket_index;\n \t }\n \n-\t__code = this->_M_hash_code(*__kp);\n-\t__bkt = _M_bucket_index(__code);\n-\n-\tif (__size > __small_size_threshold())\n-\t if (__node_ptr __p = _M_find_node(__bkt, *__kp, __code))\n-\t // There is already an equivalent node, no insertion.\n-\t return { iterator(__p), false };\n-\n \tif (!__node._M_node)\n \t __node._M_node\n \t\t= this->_M_allocate_node(std::forward<_Args>(__args)...);\n@@ -2570,32 +2544,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n erase(const key_type& __k)\n -> size_type\n {\n- __node_base_ptr __prev_n;\n- __node_ptr __n;\n- std::size_t __bkt;\n- if (size() <= __small_size_threshold())\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}\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+ auto __loc = _M_locate(__k);\n+ if (!__loc)\n+\treturn 0;\n \n-\t // We found a matching node, erase it.\n-\t __n = static_cast<__node_ptr>(__prev_n->_M_nxt);\n-\t}\n+ __node_base_ptr __prev_n = __loc._M_before;\n+ __node_ptr __n = __loc._M_node();\n+ auto __bkt = __loc._M_bucket_index;\n+ if (__bkt == size_type(-1))\n+\t__bkt = _M_bucket_index(*__n);\n \n if constexpr (__unique_keys::value)\n \t{\n","prefixes":["v1","12/12"]}