From patchwork Sun Nov 28 21:27:47 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Fran=C3=A7ois_Dumont?= X-Patchwork-Id: 48240 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 F39393858414 for ; Sun, 28 Nov 2021 21:28:21 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org F39393858414 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1638134902; bh=GX9HuxB0oznGqjEAgGTrYRmdLO3X/Eaw3eekd9HmnJI=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=n72YgQ34pxk2UqgNJsvFrHXMNQ6dYsv+M1V5bMvqpzXmKB6QoPl9tGWqvQL055Nn/ xwfYs5eUXms6T0eUamQr5TvBhxHI4sMFmCWWAJLhqE7EqjFI3dDK5gNjsDBwf6Gg5a fsxO3htM5kLbyfPq/+bBmGfiaQOMtF6FTfYA6QjU= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-wr1-x42c.google.com (mail-wr1-x42c.google.com [IPv6:2a00:1450:4864:20::42c]) by sourceware.org (Postfix) with ESMTPS id C51283858402; Sun, 28 Nov 2021 21:27:49 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org C51283858402 Received: by mail-wr1-x42c.google.com with SMTP id o13so32210976wrs.12; Sun, 28 Nov 2021 13:27:49 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:to:cc:from:subject:message-id:date:user-agent :mime-version:content-language; bh=GX9HuxB0oznGqjEAgGTrYRmdLO3X/Eaw3eekd9HmnJI=; b=NzTgaYmPVt3rijB+qWVsreonqW05MGMMlvTFJKSM8gGAd8p1jjZ/wZL3Uz/VL+HwM6 WxaCORAxgoFPzpNFGDcJGPbanfFvpUf/5S9dEz32qoB9oLlo9PYlL7D1zRrUnHxh4pSi /dh+4PaqnCrgqQXN6A0VoTOL+125BwvnaGjsQi91MtIzmRxgKsTaAqQDqwNohNvX9AP+ 1qQJGKPMA8E9DA84Y/5y+5vT3DcW4fSTh4cStwPg1iD/mhqoXkCD772TJWa/rNp9drxc qoHtAAwMeC3kMMVJeVTpUAC04lEMnXLFy+soee7MYmN7zpc2bUfw7VXwFIfkFiMLl4eD rBdw== X-Gm-Message-State: AOAM530vM+m0H8exc/uAGPznT6YpGbQjBFdatpko34zFocpLbSv7edoi dWedGTfO/FcTVrOh3l1J+ge9MRkfYjA= X-Google-Smtp-Source: ABdhPJzp+KYH7DDLM9mFtJZr7pJAy5eMIDPCAnfGflIn6tXFFhr6wSGIk3Tw5Lneq/9XuGv0p/dhiA== X-Received: by 2002:adf:f589:: with SMTP id f9mr28959238wro.505.1638134868592; Sun, 28 Nov 2021 13:27:48 -0800 (PST) Received: from ?IPv6:2a01:e0a:1dc:b1c0:a900:470a:93bf:9997? ([2a01:e0a:1dc:b1c0:a900:470a:93bf:9997]) by smtp.googlemail.com with ESMTPSA id t16sm4975910wrn.49.2021.11.28.13.27.47 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Sun, 28 Nov 2021 13:27:48 -0800 (PST) To: "libstdc++@gcc.gnu.org" Subject: [PATCH] Extend usage of user hint in _Hashtable Message-ID: <458f5d38-8b36-30f7-53b8-bd7a291f70a0@gmail.com> Date: Sun, 28 Nov 2021 22:27:47 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.14.0 MIME-Version: 1.0 Content-Language: fr X-Spam-Status: No, score=-9.9 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: =?utf-8?q?Fran=C3=A7ois_Dumont_via_Gcc-patches?= From: =?utf-8?q?Fran=C3=A7ois_Dumont?= Reply-To: =?utf-8?q?Fran=C3=A7ois_Dumont?= Cc: gcc-patches Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" libstdc++: In _Hashtable, use insertion hint as much as possible.     Make use in unordered containers of the user provided hint iterator as much as possible.     Hint is now used:     - As a hint for allocation, in order to limit memory fragmentation when     allocator is making use of it.     - For unordered_set/unordered_map we check if it does not match the key of the     element to insert, before computing the hash code.     - For unordered_multiset/unordered_multimap, if equals to the key of the element     to insert, the hash code is taken from the hint so that we can take advantage of     the potential hash code cache.     Moreover, in _M_count_tr and _M_equal_range_tr reuse the first matching node key     to check for other matching nodes to avoid any temporary instantiations.     libstdc++-v3/ChangeLog:             * include/bits/hashtable_policy.h (_NodeBuilder<>::_S_build): Add _NodePtr template             parameter.             (_ReuseOrAllocNode::operator()): Add __node_ptr parameter.             (_AllocNode::operator()): Likewise.             (_Insert_base::try_emplace): Adapt to use hint.             (_Hash_code_base<>::_M_hash_code(const _Hash_node_value<>&)): New.             (_Hashtable_base<>::_M_equals<>(const _Kt&, const _Hash_node_value<>&)): New.             (_Hashtable_base<>::_M_equals<>(const _Kt&, __hash_code, const _Hash_node_value<>&)):             Adapt, use latter.             (_Hashtable_base<>::_M_equals_tr<>(const _Kt&, const _Hash_node_value<>&)): New.             (_Hashtable_base<>::_M_equals_tr<>(const _Kt&, __hash_code, const _Hash_node_value<>&)):             Adapt, use latter. (_Hashtable_alloc<>::_M_allocate_node(__node_ptr, _Args&&...)): Add __node_ptr parameter.             * include/bits/hashtable.h (_Hashtable<>::_Scope_node<>(__hashtable_alloc*, __node_ptr, _Args&&...)):             Add __node_ptr parameter.             (_Hashtable<>::_M_get_node_hint(size_type, __node_ptr)): New.             (_Hashtable<>::_M_emplace_unique(const_iterator, _Args&&...)): New.             (_Hashtable<>::_M_emplace_multi(const_iterator, _Args&&...)): New.             (_Hashtable<>::_M_emplace()): Adapt to use latter.             (_Hashtable<>::_M_insert_unique(const_iterator, _Kt&&, _Arg&&, const _NodeGenerator&)):             (_Hashtable<>::_M_reinsert_node(const_iterator, node_type&&)): Add const_iterator.             Add const_iterator parameter.             * include/bits/unordered_map.h (unordered_map<>::insert(node_type&&)): Pass cend as             hint.             (unordered_map<>::insert(const_iterator, node_type&&)): Adapt to use hint.             * include/bits/unordered_set.h (unordered_set<>::insert(node_type&&)): Pass cend as             hint.             (unordered_set<>::insert(const_iterator, node_type&&)): Adapt to use hint. Tested under Linux x86_64. Ok to commit ? François diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 6e2d4c10cfe..5010cefcd77 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -301,9 +301,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Allocate a node and construct an element within it. template - _Scoped_node(__hashtable_alloc* __h, _Args&&... __args) + _Scoped_node(__hashtable_alloc* __h, + __node_ptr __hint, _Args&&... __args) : _M_h(__h), - _M_node(__h->_M_allocate_node(std::forward<_Args>(__args)...)) + _M_node(__h->_M_allocate_node(__hint, + std::forward<_Args>(__args)...)) { } // Destroy element and deallocate node. @@ -818,6 +820,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return nullptr; } + // Gets a hint after which a node should be allocated given a bucket. + __node_ptr + _M_get_node_hint(size_type __bkt, __node_ptr __hint = nullptr) const + { + __node_base_ptr __node; + if (__node = _M_buckets[__bkt]) + return __node != &_M_before_begin + ? static_cast<__node_ptr>(__node) : __hint; + + return __hint; + } + // Insert a node at the beginning of a bucket. void _M_insert_bucket_begin(size_type, __node_ptr); @@ -846,26 +860,40 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template std::pair - _M_emplace(true_type __uks, _Args&&... __args); + _M_emplace_unique(const_iterator, _Args&&... __args); template iterator - _M_emplace(false_type __uks, _Args&&... __args) - { return _M_emplace(cend(), __uks, std::forward<_Args>(__args)...); } + _M_emplace_multi(const_iterator, _Args&&... __args); + + template + std::pair + _M_emplace(true_type /*__uks*/, _Args&&... __args) + { return _M_emplace_unique(cend(), std::forward<_Args>(__args)...); } - // Emplace with hint, useless when keys are unique. template iterator - _M_emplace(const_iterator, true_type __uks, _Args&&... __args) - { return _M_emplace(__uks, std::forward<_Args>(__args)...).first; } + _M_emplace(false_type /*__uks*/, _Args&&... __args) + { return _M_emplace_multi(cend(), std::forward<_Args>(__args)...); } template iterator - _M_emplace(const_iterator, false_type __uks, _Args&&... __args); + _M_emplace(const_iterator __hint, true_type /*__uks*/, + _Args&&... __args) + { + return _M_emplace_unique(__hint, + std::forward<_Args>(__args)...).first; + } + + template + iterator + _M_emplace(const_iterator __hint, false_type /*__uks*/, + _Args&&... __args) + { return _M_emplace_multi(__hint, std::forward<_Args>(__args)...); } template std::pair - _M_insert_unique(_Kt&&, _Arg&&, const _NodeGenerator&); + _M_insert_unique(const_iterator, _Kt&&, _Arg&&, const _NodeGenerator&); template static __conditional_t< @@ -888,7 +916,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen, true_type /* __uks */) { - return _M_insert_unique( + return _M_insert_unique(cend(), _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))), std::forward<_Arg>(__arg), __node_gen); } @@ -902,14 +930,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __uks); } - // Insert with hint, not used when keys are unique. + // Insert with hint when keys are unique. template iterator - _M_insert(const_iterator, _Arg&& __arg, + _M_insert(const_iterator __hint, _Arg&& __arg, const _NodeGenerator& __node_gen, true_type __uks) { - return - _M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).first; + return _M_insert_unique(__hint, + _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))), + std::forward<_Arg>(__arg), __node_gen).first; } // Insert with hint when keys are not unique. @@ -973,7 +1002,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION #if __cplusplus > 201402L /// Re-insert an extracted node into a container with unique keys. insert_return_type - _M_reinsert_node(node_type&& __nh) + _M_reinsert_node(const_iterator __hint, node_type&& __nh) { insert_return_type __ret; if (__nh.empty()) @@ -983,6 +1012,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_assert(get_allocator() == __nh.get_allocator()); const key_type& __k = __nh._M_key(); + if (__hint._M_cur && this->_M_equals(__k, *__hint._M_cur)) + { + __ret.node = std::move(__nh); + __ret.position = iterator(__hint._M_cur); + __ret.inserted = false; + } + else + { __hash_code __code = this->_M_hash_code(__k); size_type __bkt = _M_bucket_index(__code); if (__node_ptr __n = _M_find_node(__bkt, __k, __code)) @@ -999,6 +1036,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __ret.inserted = true; } } + } return __ret; } @@ -1012,7 +1050,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_assert(get_allocator() == __nh.get_allocator()); const key_type& __k = __nh._M_key(); - auto __code = this->_M_hash_code(__k); + __hash_code __code; + if (__hint._M_cur && this->_M_equals(__k, *__hint._M_cur)) + __code = this->_M_hash_code(*__hint._M_cur); + else + __code = this->_M_hash_code(__k); auto __ret = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr); __nh._M_ptr = nullptr; @@ -1105,8 +1147,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;) { auto __pos = __i++; - __hash_code __code - = this->_M_hash_code(__src.hash_function(), *__pos._M_cur); + const key_type& __k = _ExtractKey{}(*__pos); + __hash_code __code; + if (__hint && this->_M_equals(__k, *__hint)) + __code = this->_M_hash_code(*__hint); + else + __code = this->_M_hash_code(__src.hash_function(), *__pos._M_cur); auto __nh = __src.extract(__pos); __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur; __nh._M_ptr = nullptr; @@ -1332,7 +1378,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // _M_before_begin. __node_ptr __ht_n = __ht._M_begin(); __node_ptr __this_n - = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v())); + = __node_gen(nullptr, __fwd_value_for<_Ht>(__ht_n->_M_v())); this->_M_copy_code(*__this_n, *__ht_n); _M_update_bbegin(__this_n); @@ -1340,7 +1386,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __node_ptr __prev_n = __this_n; for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next()) { - __this_n = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v())); + __this_n + = __node_gen(__prev_n, __fwd_value_for<_Ht>(__ht_n->_M_v())); __prev_n->_M_nxt = __this_n; this->_M_copy_code(*__this_n, *__ht_n); size_type __bkt = _M_bucket_index(*__this_n); @@ -1732,10 +1779,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // All equivalent values are next to each other, if we find a // non-equivalent value after an equivalent one it means that we won't // find any new equivalent value. + const key_type& __nk = _ExtractKey{}(__n->_M_v()); iterator __it(__n); size_type __result = 1; for (++__it; - __it._M_cur && this->_M_equals_tr(__k, __code, *__it._M_cur); + __it._M_cur && this->_M_equals(__nk, __code, *__it._M_cur); ++__it) ++__result; @@ -1819,8 +1867,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // All equivalent values are next to each other, if we find a // non-equivalent value after an equivalent one it means that we won't // find any new equivalent value. + const key_type& __nk = _ExtractKey{}(__n->_M_v()); auto __beg = __ite++; - while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur)) + while (__ite._M_cur && this->_M_equals(__nk, __code, *__ite._M_cur)) ++__ite; return { __beg, __ite }; @@ -1847,8 +1896,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // All equivalent values are next to each other, if we find a // non-equivalent value after an equivalent one it means that we won't // find any new equivalent value. + const key_type& __nk = _ExtractKey{}(__n->_M_v()); auto __beg = __ite++; - while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur)) + while (__ite._M_cur && this->_M_equals(__nk, __code, *__ite._M_cur)) ++__ite; return { __beg, __ite }; @@ -1997,17 +2047,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_emplace(true_type /* __uks */, _Args&&... __args) + _M_emplace_unique(const_iterator __hint, _Args&&... __args) -> pair { // First build the node to get access to the hash code - _Scoped_node __node { this, std::forward<_Args>(__args)... }; + _Scoped_node __node { this, __hint._M_cur, std::forward<_Args>(__args)... }; const key_type& __k = _ExtractKey{}(__node._M_node->_M_v()); + if (__hint._M_cur && this->_M_equals(__k, *__hint._M_cur)) + return { iterator(__hint._M_cur), false }; + __hash_code __code = this->_M_hash_code(__k); size_type __bkt = _M_bucket_index(__code); if (__node_ptr __p = _M_find_node(__bkt, __k, __code)) // There is already an equivalent node, no insertion - return std::make_pair(iterator(__p), false); + return { iterator(__p), false }; // Insert the node auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node); @@ -2023,15 +2076,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_emplace(const_iterator __hint, false_type /* __uks */, - _Args&&... __args) + _M_emplace_multi(const_iterator __hint, _Args&&... __args) -> iterator { // First build the node to get its hash code. - _Scoped_node __node { this, std::forward<_Args>(__args)... }; + _Scoped_node __node + { this, __hint._M_cur, std::forward<_Args>(__args)... }; + const key_type& __k = _ExtractKey{}(__node._M_node->_M_v()); + __hash_code __code; + if (__hint._M_cur && this->_M_equals(__k, *__hint._M_cur)) + __code = this->_M_hash_code(*__hint._M_cur); + else + __code = this->_M_hash_code(__k); - __hash_code __code = this->_M_hash_code(__k); auto __pos = _M_insert_multi_node(__hint._M_cur, __code, __node._M_node); __node._M_node = nullptr; @@ -2132,10 +2190,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_insert_unique(_Kt&& __k, _Arg&& __v, + _M_insert_unique(const_iterator __hint, + _Kt&& __k, _Arg&& __v, const _NodeGenerator& __node_gen) -> pair { + if (__hint._M_cur && this->_M_equals_tr(__k, *__hint._M_cur)) + return { iterator(__hint._M_cur), false }; + __hash_code __code = this->_M_hash_code_tr(__k); size_type __bkt = _M_bucket_index(__code); @@ -2143,11 +2205,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return { iterator(__node), false }; _Scoped_node __node { - __node_builder_t::_S_build(std::forward<_Kt>(__k), + __node_builder_t::_S_build(_M_get_node_hint(__bkt, __hint._M_cur), + std::forward<_Kt>(__k), std::forward<_Arg>(__v), __node_gen), this }; + auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node); __node._M_node = nullptr; @@ -2169,11 +2233,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION -> iterator { // First allocate new node so that we don't do anything if it throws. - _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this }; + _Scoped_node __node + { __node_gen(__hint._M_cur, std::forward<_Arg>(__v)), this }; // Second compute the hash code so that we don't rehash if it throws. - __hash_code __code - = this->_M_hash_code(_ExtractKey{}(__node._M_node->_M_v())); + const auto& __k = _ExtractKey{}(__node._M_node->_M_v()); + __hash_code __code; + if (__hint._M_cur && this->_M_equals(__k, *__hint._M_cur)) + __code = this->_M_hash_code(*__hint._M_cur); + else + __code = this->_M_hash_code(__k); auto __pos = _M_insert_multi_node(__hint._M_cur, __code, __node._M_node); diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 0b5443fc187..7b9e0476159 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -115,12 +115,14 @@ namespace __detail template<> struct _NodeBuilder<_Select1st> { - template - static auto - _S_build(_Kt&& __k, _Arg&& __arg, const _NodeGenerator& __node_gen) - -> typename _NodeGenerator::__node_type* - { - return __node_gen(std::forward<_Kt>(__k), + template + static _NodePtr + _S_build(_NodePtr __hint, + _Kt&& __k, _Arg&& __arg, const _NodeGenerator& __node_gen) + { + return __node_gen(__hint, + std::forward<_Kt>(__k), std::forward<_Arg>(__arg).second); } }; @@ -128,11 +130,12 @@ namespace __detail template<> struct _NodeBuilder<_Identity> { - template - static auto - _S_build(_Kt&& __k, _Arg&&, const _NodeGenerator& __node_gen) - -> typename _NodeGenerator::__node_type* - { return __node_gen(std::forward<_Kt>(__k)); } + template + static _NodePtr + _S_build(_NodePtr __hint, + _Kt&& __k, _Arg&&, const _NodeGenerator& __node_gen) + { return __node_gen(__hint, std::forward<_Kt>(__k)); } }; template @@ -150,22 +153,23 @@ namespace __detail typename __hashtable_alloc::__node_alloc_traits; public: - using __node_type = typename __hashtable_alloc::__node_type; + using __node_ptr = typename __hashtable_alloc::__node_ptr; - _ReuseOrAllocNode(__node_type* __nodes, __hashtable_alloc& __h) + _ReuseOrAllocNode(__node_ptr __nodes, __hashtable_alloc& __h) : _M_nodes(__nodes), _M_h(__h) { } + _ReuseOrAllocNode(const _ReuseOrAllocNode&) = delete; ~_ReuseOrAllocNode() { _M_h._M_deallocate_nodes(_M_nodes); } template - __node_type* - operator()(_Args&&... __args) const + __node_ptr + operator()(__node_ptr __hint, _Args&&... __args) const { if (_M_nodes) { - __node_type* __node = _M_nodes; + __node_ptr __node = _M_nodes; _M_nodes = _M_nodes->_M_next(); __node->_M_nxt = nullptr; auto& __a = _M_h._M_node_allocator(); @@ -180,13 +184,15 @@ namespace __detail _M_h._M_deallocate_node_ptr(__node); __throw_exception_again; } + return __node; } - return _M_h._M_allocate_node(std::forward<_Args>(__args)...); + + return _M_h._M_allocate_node(__hint, std::forward<_Args>(__args)...); } private: - mutable __node_type* _M_nodes; + mutable __node_ptr _M_nodes; __hashtable_alloc& _M_h; }; @@ -199,15 +205,15 @@ namespace __detail using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>; public: - using __node_type = typename __hashtable_alloc::__node_type; + using __node_ptr = typename __hashtable_alloc::__node_ptr; _AllocNode(__hashtable_alloc& __h) : _M_h(__h) { } template - __node_type* - operator()(_Args&&... __args) const - { return _M_h._M_allocate_node(std::forward<_Args>(__args)...); } + __node_ptr + operator()(__node_ptr __hint, _Args&&... __args) const + { return _M_h._M_allocate_node(__hint, std::forward<_Args>(__args)...); } private: __hashtable_alloc& _M_h; @@ -761,6 +767,7 @@ namespace __detail typename __hashtable::_Scoped_node __node { __h, + __h->_M_get_node_hint(__bkt), std::piecewise_construct, std::tuple(__k), std::tuple<>() @@ -788,6 +795,7 @@ namespace __detail typename __hashtable::_Scoped_node __node { __h, + __h->_M_get_node_hint(__bkt), std::piecewise_construct, std::forward_as_tuple(std::move(__k)), std::tuple<>() @@ -876,7 +884,7 @@ namespace __detail template std::pair - try_emplace(const_iterator, _KType&& __k, _Args&&... __args) + try_emplace(const_iterator __hint, _KType&& __k, _Args&&... __args) { __hashtable& __h = _M_conjure_hashtable(); auto __code = __h._M_hash_code(__k); @@ -885,7 +893,7 @@ namespace __detail return { iterator(__node), false }; typename __hashtable::_Scoped_node __node { - &__h, + &__h, __hint._M_cur, std::piecewise_construct, std::forward_as_tuple(std::forward<_KType>(__k)), std::forward_as_tuple(std::forward<_Args>(__args)...) @@ -1250,6 +1258,14 @@ namespace __detail return _M_hash()(__k); } + __hash_code + _M_hash_code(const _Hash_node_value<_Value, true>& __n) const + { return __n._M_hash_code; } + + __hash_code + _M_hash_code(const _Hash_node_value<_Value, false>& __n) const + { return _M_hash_code(_ExtractKey{}(__n._M_v())); } + __hash_code _M_hash_code(const _Hash&, const _Hash_node_value<_Value, true>& __n) const @@ -1641,18 +1657,23 @@ namespace __detail { } bool - _M_equals(const _Key& __k, __hash_code __c, + _M_equals(const _Key& __k, const _Hash_node_value<_Value, __hash_cached::value>& __n) const { static_assert(__is_invocable{}, "key equality predicate must be invocable with two arguments of " "key type"); - return _S_equals(__c, __n) && _M_eq()(__k, _ExtractKey{}(__n._M_v())); + return _M_eq()(__k, _ExtractKey{}(__n._M_v())); } + bool + _M_equals(const _Key& __k, __hash_code __c, + const _Hash_node_value<_Value, __hash_cached::value>& __n) const + { return _S_equals(__c, __n) && _M_equals(__k, __n); } + template bool - _M_equals_tr(const _Kt& __k, __hash_code __c, + _M_equals_tr(const _Kt& __k, const _Hash_node_value<_Value, __hash_cached::value>& __n) const { @@ -1660,9 +1681,16 @@ namespace __detail __is_invocable{}, "key equality predicate must be invocable with two arguments of " "key type"); - return _S_equals(__c, __n) && _M_eq()(__k, _ExtractKey{}(__n._M_v())); + return _M_eq()(__k, _ExtractKey{}(__n._M_v())); } + template + bool + _M_equals_tr(const _Kt& __k, __hash_code __c, + const _Hash_node_value<_Value, + __hash_cached::value>& __n) const + { return _S_equals(__c, __n) && _M_equals_tr(__k, __n); } + bool _M_node_equals( const _Hash_node_value<_Value, __hash_cached::value>& __lhn, @@ -1880,7 +1908,7 @@ namespace __detail // Allocate a node and construct an element within it. template __node_ptr - _M_allocate_node(_Args&&... __args); + _M_allocate_node(__node_ptr __hint, _Args&&... __args); // Destroy the element within a node and deallocate the node. void @@ -1907,22 +1935,32 @@ namespace __detail template template auto - _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(_Args&&... __args) + _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(__node_ptr __hint, + _Args&&... __args) -> __node_ptr { - auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1); + auto& __alloc = _M_node_allocator(); + typename __node_alloc_traits::pointer __nptr; + if (__hint) + { + typedef typename __node_alloc_traits::const_pointer _CPtr; + auto __hptr = std::pointer_traits<_CPtr>::pointer_to(*__hint); + __nptr = __node_alloc_traits::allocate(__alloc, 1, __hptr); + } + else + __nptr = __node_alloc_traits::allocate(__alloc, 1); + __node_ptr __n = std::__to_address(__nptr); __try { ::new ((void*)__n) __node_type; - __node_alloc_traits::construct(_M_node_allocator(), - __n->_M_valptr(), + __node_alloc_traits::construct(__alloc, __n->_M_valptr(), std::forward<_Args>(__args)...); return __n; } __catch(...) { - __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1); + __node_alloc_traits::deallocate(__alloc, __nptr, 1); __throw_exception_again; } } diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h index 2261e6685ea..9f621cdbaeb 100644 --- a/libstdc++-v3/include/bits/unordered_map.h +++ b/libstdc++-v3/include/bits/unordered_map.h @@ -436,12 +436,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER /// Re-insert an extracted node. insert_return_type insert(node_type&& __nh) - { return _M_h._M_reinsert_node(std::move(__nh)); } + { return _M_h._M_reinsert_node(cend(), std::move(__nh)); } /// Re-insert an extracted node. iterator - insert(const_iterator, node_type&& __nh) - { return _M_h._M_reinsert_node(std::move(__nh)).position; } + insert(const_iterator __hint, node_type&& __nh) + { return _M_h._M_reinsert_node(__hint, std::move(__nh)).position; } #define __cpp_lib_unordered_map_try_emplace 201411 /** diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h index ac4a890d25a..10d81905acb 100644 --- a/libstdc++-v3/include/bits/unordered_set.h +++ b/libstdc++-v3/include/bits/unordered_set.h @@ -497,12 +497,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER /// Re-insert an extracted node. insert_return_type insert(node_type&& __nh) - { return _M_h._M_reinsert_node(std::move(__nh)); } + { return _M_h._M_reinsert_node(cend(), std::move(__nh)); } /// Re-insert an extracted node. iterator - insert(const_iterator, node_type&& __nh) - { return _M_h._M_reinsert_node(std::move(__nh)).position; } + insert(const_iterator __hint, node_type&& __nh) + { return _M_h._M_reinsert_node(__hint, std::move(__nh)).position; } #endif // C++17 ///@{