From patchwork Thu Nov 23 21:59:03 2023 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: 1867986 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20230601 header.b=OtaUoYUN; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4SbsV03FCWz1yS0 for ; Fri, 24 Nov 2023 08:59:52 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 618DB3838F29 for ; Thu, 23 Nov 2023 21:59:49 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-wm1-x32e.google.com (mail-wm1-x32e.google.com [IPv6:2a00:1450:4864:20::32e]) by sourceware.org (Postfix) with ESMTPS id 415C9385E449; Thu, 23 Nov 2023 21:59:07 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 415C9385E449 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 415C9385E449 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::32e ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700776752; cv=none; b=gx2N2WdL+Oh6fxVKW+hRWOQl3ml3nEoW/gicr5ZVbziatCu2CLOK1MiGutvhe2KHeKB1mnVS8Ek4LBoYAbwXbyF7QnuWILFfvN+p7VJHnaSSbMNp7QvFZQyY8dbmkdwJjjAf8+xMmKATlE2IQ4EXKqD7ALqVtMfaTs+QrkpN+7s= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700776752; c=relaxed/simple; bh=3kIgpqVCpddrjE/C2Fi1wlxHvco1EB/m/hv7X7n3R5E=; h=DKIM-Signature:Message-ID:Date:MIME-Version:From:Subject:To; b=sSlWlLWOjuWKIvruO2nWC7vMKAa64P4XJQyPhM1J1F7+NziA2eKSuff5W9fFoF6NJ6xUtwVn7MevTUaysKrSe8c5O8adKFj0q8YKhqm9rPlb8ArAl8RlJmUOXWgI9MuBXzhX35+17GWfupMyaQtniSTlEkEtr7VgTwNjYchKM6Q= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-wm1-x32e.google.com with SMTP id 5b1f17b1804b1-40b30308c67so8846675e9.0; Thu, 23 Nov 2023 13:59:07 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1700776745; x=1701381545; darn=gcc.gnu.org; h=content-language:cc:to:subject:from:user-agent:mime-version:date :message-id:from:to:cc:subject:date:message-id:reply-to; bh=++R3xHiXiZVILwc0f1OXVd7xn/bHtLNzEmZWFUbiS8w=; b=OtaUoYUNVwEaNImDRQyZy6g65ETjoABLdmxi0b8SsWK1/szh2oM9TXtLlKXkXUGfXl jRP6kns3TePCRXLMxI0B1tjyOWdViEzfTc6CwNEuUJMPz7neMEJEMTXzj77IpAkzrVyP XFhDmgk+UXpjf41ZukrMZe87APaFDyVhgoJBCDuO1nHYBRrjiZ4FhlxTUZDK45ZL4xs+ aj8EtyR7AZWtl4pzdCgsdAtVfxBzO4slJKy9iWceMey8rBt9vg+Uv6kK5od85cniMDAK aQmTupgfT13a0s2VfxbkT9bb7V1d0amrwLjKJ/kWFTihheTM1Lu8wZwqllXJz9ivwdQJ iZoQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1700776745; x=1701381545; h=content-language:cc:to:subject:from:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=++R3xHiXiZVILwc0f1OXVd7xn/bHtLNzEmZWFUbiS8w=; b=dLa2ci+UEdzvGk387zfQ90HSLV+YnyFBEv2NPK+ezEIOrSMQ4aBqx1s2ttfxv2GTFP EpV/osa3+QHKhq/gttWBdzNjFOpONzD/sl0BTqJNk9TseVr8GFMhAZ+xYDBXIQfSsp/3 +N8Gfw7PTH8EeVbyDi1fb/2qOurXesmkUg8Xr6XT8YkrBPZlwwnzSEdZ+lA+L0HqJrOB 3Fxp9heNnkNjqeCafZGYrLjKe7om+OjYdy1CVTWV3N+TYp0urk/e91dlLHhw2s78uHWt RsTTgOBQFtm36U9SKxvpNluXyjFdGwtv99nadTG5WMrtqvKq4/u2R8Nu1G2Y4l1/d2uQ +eXg== X-Gm-Message-State: AOJu0YxFtgWxJwOdxvG2SMOTFZw1CHCu8OHJZE/QGYrd2i+i/XgtXdzq dr9l4Qp1veIxGsLXOveGnTaTXnyV6Ek= X-Google-Smtp-Source: AGHT+IHw3RXzxrHumO0PLCij09Fx4mBvbjVE0KusBHHue8zL8GHu36J5whrPoL84poRm2Peb0CjQoQ== X-Received: by 2002:a05:600c:458d:b0:405:4776:735a with SMTP id r13-20020a05600c458d00b004054776735amr649859wmo.2.1700776744986; Thu, 23 Nov 2023 13:59:04 -0800 (PST) Received: from ?IPV6:2a01:e0a:1dc:b1c0:fc8d:30b8:64d5:2ae8? ([2a01:e0a:1dc:b1c0:fc8d:30b8:64d5:2ae8]) by smtp.gmail.com with ESMTPSA id o7-20020a05600c510700b0040b36ad5413sm2995518wms.46.2023.11.23.13.59.03 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 23 Nov 2023 13:59:04 -0800 (PST) Message-ID: Date: Thu, 23 Nov 2023 22:59:03 +0100 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird From: =?utf-8?q?Fran=C3=A7ois_Dumont?= Subject: [PATCH 5/5][_Hashtable] Prefer to insert after last node To: libstdc++ Cc: gcc-patches Content-Language: en-US X-Spam-Status: No, score=-9.4 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, T_SCC_BODY_TEXT_LINE 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: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org libstdc++: [_Hashtable] Prefer to insert after last node     When inserting an element into an empty bucket we currently insert the new node     after the before-begin node so in first position. The drawback of doing this is     that we are forced to update the bucket that was containing this before-begin     node to point to the newly inserted node. To do so we need at best to do a modulo     to find this bucket and at worst, when hash code is not cached, also compute it.     To avoid this side effect it is better to insert after the last node. To do so     we are introducing a helper type _HintPolicy that have 3 resposibilities.     1. When the gnu versioned namespace is used we add a _M_last member to _Hashtable,     _HintPolicy is then in charge of maintaining it. For this purpose _HintPolicy is     using the RAII pattern, it resets the _M_last at destruction level. It also maintain     its own _M_last, all mutable operations are updating it when needed.     2. When the gnu versioned namespace is not used _HintPolicy will still maintain its     _M_last member using initially the user provided hint if any and if it is actually     the container last node that is to say a dereferenceable node with its next node being     null. All mutable operations can also update the contextual _HintPolicy instance     whenever they detect the last node during their process.     3. As long as we haven't been able to detect the container last node _HintPolicy     is used to keep a cache of the before-begin bucket index so that we do not need to     compute it afterward for example in the context of range insertion.     libstdc++-v3/ChangeLog:             * include/bits/hashtable.h [_GLIBCXX_INLINE_VERSION](_Hashtable<>::_M_last): New, the container last node.             (_Hashtable<>::_HintPolicy): New.             (_Hashtable<>::_M_get_hint(__node_ptr)): New.             (_Hashtable<>::_M_get_hint_policy(__node_ptr)): New. (_Hashtable<>::_M_check_for_last(__node_base_ptr)): New.             (_Hashtable<>::_M_set_last(__node_ptr)): New.             (_Hashtable<>::_M_get_last()): New.             (_Hashtable<>::_M_compute_hash_code(__node_ptr, const key_type&)): Remove.             (_Hashtable<>::_InsertInfo): New struct.             (_Hashtable<>::_M_get_insert_info): New, return latter. (_Hashtable<>::operator=(initializer_list<>)): Adapt to instantiate a _HintPolicy.             (_Hashtable<>::_M_insert_bucket_begin): Add _HintPolicy& parameter and use it             to optimize insertion in an empty bucket.             (_Hashtable<>::_M_insert_unique_node): Add _HintPolicy& parameter.             (_Hashtable<>::_M_insert_multi_node): Likewise and add _InsertInfo parameter. (_Hashtable<>::_M_emplace_unique(_HintPolicy&, _Args&&...)): New. (_Hashtable<>::_M_emplace_multi(_HintPolicy&, _Args&&...)): New.             (_Hashtable<>::_M_emplace): Adapt to use latters.             (_Hashtable<>::_M_insert_unique): Add _HintPolicy& parameter.             (_Hashtable<>::_M_insert_unique_aux): Add _HintPolicy& parameter.             (_Hashtable<>::_M_insert): Adapt to use latter.             (_Hashtable<>::emplace_hint(const_iterator, _Args&&...)): Adapt.             (_hashtable<>::rehash(size_type)): Adapt.             (_Hashtable<>::_M_reinsert_node(const_iterator, node_type&&)):             Add hint parameter, adapt to use it for _HintPolicy instantiation.             (_Hashtable<>::_M_reinsert_node_multi): Likewise.             (_Hashtable<>::_M_merge_unique): Adapt.             (_Hashtable<>::_M_rehash): Add _HintPolicy& parameter.             (_Hashtable<>::_Hashtable<_InputIte>()): Adapt.             (_Hashtable<>::_M_assign): Call _M_set_last.             (_Hashtable<>::_M_reset()): Reset _M_last. (_Hashtable<>::_M_move_assign(_Hashtable&&, true_type)): Move _M_last.             (_Hashtable<>(_Hashtable&&, __node_alloc_type&&, true_type)): Copy _M_last.             (_Hashtable<>(_Hashtable&&, __node_alloc_type&&, false_type)): Copy _M_last.             (_Hashtable<>::_M_insert_range): Adapt.             (_Hashtable<>::_M_erase): Call _M_check_for_last.             (_Hashtable<>::erase): Likewise.             * include/bits/hashtable_policy.h:             (_Map_base<>::operator[](const key_type&)): Use hint policy.             (_Map_base<>::operator[](key_type&&)): Likewise.             (_Insert_base<>::insert(const_iterator, const value_type&)): Likewise using hint.             (_Insert_base<>::try_emplace): Likewise. (_Insert_base<>::_M_insert_range<>(_InputIte, _InputIte, true_type)): Use hint policy. (_Insert_base<>::_M_insert_range<>(_InputIte, _InputIte, false_type)): Use hint policy.             (_Insert<>::insert(const_iterator, value_type&&)): Likewise.             * 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.             * testsuite/23_containers/unordered_multimap/insert/hint.cc: Adapt implementation             specific tests. Tested under Linux x64 Ok to commit ? François diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index aec77c34a58..d758b054b00 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -403,6 +403,59 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // numerous checks in the code to avoid 0 modulus. __node_base_ptr _M_single_bucket = nullptr; +#if _GLIBCXX_INLINE_VERSION + // The last container node to optimize insertion in empty buckets. + __node_ptr _M_last = nullptr; +#endif + + class _HintPolicy + { + _Hashtable& _M_htb; + __node_ptr _M_last; + std::size_t _M_bbegin_index; + bool _M_initialized = false; + + public: + _HintPolicy(_Hashtable& __htbl, __node_ptr __last) + : _M_htb(__htbl), _M_last(__last) + { } + +#if _GLIBCXX_INLINE_VERSION + ~_HintPolicy() + { _M_htb._M_last = _M_last; } +#endif + + std::size_t + _M_get_bbegin_bkt(__node_ptr __n) const + { + if (!_M_initialized) + return _M_htb._M_bucket_index(*__n); + return _M_bbegin_index; + } + + void + _M_store_bbegin_bkt(std::size_t __bkt) + { + _M_bbegin_index = __bkt; + _M_initialized = true; + } + + constexpr __node_ptr + _M_get_hint() + { return _M_last; } + + void + _M_set_last(__node_ptr __n) + { _M_last = __n; } + + void + _M_checked_set(__node_ptr __n) + { + if (!__n || !__n->_M_nxt) + _M_last = __n; + } + }; + void _M_update_bbegin() { @@ -425,6 +478,51 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_uses_single_bucket() const { return _M_uses_single_bucket(_M_buckets); } + __node_ptr + _M_get_hint([[maybe_unused]] __node_ptr __usr_hint = nullptr) const + { +#if _GLIBCXX_INLINE_VERSION + return _M_last; +#else + return __usr_hint && !__usr_hint->_M_nxt ? __usr_hint : nullptr; +#endif + } + + _HintPolicy + _M_get_hint_policy(__node_ptr __usr_hint = nullptr) + { return _HintPolicy(*this, _M_get_hint(__usr_hint)); } + + void + _M_check_for_last([[maybe_unused]] __node_base_ptr __prev_n) + { +#if _GLIBCXX_INLINE_VERSION + if (!__prev_n->_M_nxt) + { + _M_last = __prev_n == &_M_before_begin + ? nullptr + : static_cast<__node_ptr>(__prev_n); + } +#endif + } + + void + _M_set_last([[maybe_unused]] __node_ptr __n) + { +#if _GLIBCXX_INLINE_VERSION + _M_last = __n; +#endif + } + + constexpr __node_ptr + _M_get_last() + { +#if _GLIBCXX_INLINE_VERSION + return _M_last; +#else + return nullptr; +#endif + } + static constexpr size_t __small_size_threshold() noexcept { @@ -612,11 +710,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // We consider that all elements of __l are going to be inserted. auto __l_bkt_count = _M_rehash_policy._M_bkt_for_elements(__l.size()); + auto __hint_policy = _M_get_hint_policy(); + // Do not shrink to keep potential user reservation. if (_M_bucket_count < __l_bkt_count) - rehash(__l_bkt_count); + _M_rehash(__hint_policy, __l_bkt_count); - _M_insert_range(__l.begin(), __l.end(), __roan); + _M_insert_range(__l.begin(), __l.end(), __hint_policy, __roan); return *this; } @@ -838,30 +938,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Insert a node at the beginning of a bucket. void - _M_insert_bucket_begin(size_type __bkt, __node_ptr __node) + _M_insert_bucket_begin(_HintPolicy& __hint_policy, + size_type __bkt, __node_ptr __node) { + __node_base_ptr __prev; if (_M_buckets[__bkt]) { // Bucket is not empty, we just need to insert the new node // after the bucket before begin. - __node->_M_nxt = _M_buckets[__bkt]->_M_nxt; - _M_buckets[__bkt]->_M_nxt = __node; + __prev = _M_buckets[__bkt]; + if (!__prev->_M_nxt) + __hint_policy._M_set_last(__node); } else { - // The bucket is empty, the new node is inserted at the - // beginning of the singly-linked list and the bucket will - // contain _M_before_begin pointer. - __node->_M_nxt = _M_before_begin._M_nxt; - _M_before_begin._M_nxt = __node; - - if (__node->_M_nxt) - // We must update former begin bucket that is pointing to - // _M_before_begin. - _M_buckets[_M_bucket_index(*__node->_M_next())] = __node; - - _M_buckets[__bkt] = &_M_before_begin; + // If we have a hint, the last container node, insert after. + __node_ptr __hint = __hint_policy._M_get_hint(); + if (__hint) + { + __prev = __hint; + __hint_policy._M_set_last(__node); + } + else + { + // The bucket is empty, the new node is inserted at the + // beginning of the singly-linked list and the bucket will + // contain _M_before_begin pointer. + __prev = &_M_before_begin; + + if (__prev->_M_nxt) + { + // We must update former begin bucket that is pointing to + // _M_before_begin. + size_type __bb_bkt = __hint_policy._M_get_bbegin_bkt( + static_cast<__node_ptr>(__prev->_M_nxt)); + _M_buckets[__bb_bkt] = __node; + } + else + __hint_policy._M_set_last(__node); + + __hint_policy._M_store_bbegin_bkt(__bkt); + } + + _M_buckets[__bkt] = __prev; } + + __node->_M_nxt = __prev->_M_nxt; + __prev->_M_nxt = __node; } // Remove the bucket first node @@ -887,44 +1010,76 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __node_base_ptr _M_get_previous_node(size_type __bkt, __node_ptr __n); - pair<__node_ptr, __hash_code> - _M_compute_hash_code(__node_ptr __hint, const key_type& __k) const; + struct _InsertInfo + { + __node_base_ptr _M_prev; + __node_ptr _M_equi_n; + __hash_code _M_code; + }; + + _InsertInfo + _M_get_insert_info(_HintPolicy& __hint_policy, const key_type& __k, + __node_ptr __n = nullptr) const; // Insert node __n with hash code __code, in bucket __bkt if no // rehash (assumes no element with same key already present). // Takes ownership of __n if insertion succeeds, throws otherwise. iterator - _M_insert_unique_node(size_type __bkt, __hash_code, + _M_insert_unique_node(_HintPolicy& __hint_policy, + size_type __bkt, __hash_code, __node_ptr __n, size_type __n_elt = 1); - // Insert node __n with key __k and hash code __code. + // Insert node __n after __prev if any. // Takes ownership of __n if insertion succeeds, throws otherwise. iterator - _M_insert_multi_node(__node_ptr __hint, - __hash_code __code, __node_ptr __n); + _M_insert_multi_node(_HintPolicy& __hint_policy, + const _InsertInfo& __info, __node_ptr __n); + + template + std::pair + _M_emplace_unique(_HintPolicy&, _Args&&... __args); + + template + iterator + _M_emplace_multi(_HintPolicy&, _Args&&... __args); template std::pair - _M_emplace(true_type __uks, _Args&&... __args); + _M_emplace(true_type /*__uks*/, _Args&&... __args) + { + auto __hint_policy = _M_get_hint_policy(); + return _M_emplace_unique(__hint_policy, + std::forward<_Args>(__args)...); + } template iterator - _M_emplace(false_type __uks, _Args&&... __args) - { return _M_emplace(cend(), __uks, std::forward<_Args>(__args)...); } + _M_emplace(false_type /*__uks*/, _Args&&... __args) + { + auto __hint_policy = _M_get_hint_policy(); + return _M_emplace_multi(__hint_policy, + 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(_HintPolicy& __hint_policy, + true_type /*__uks*/, _Args&&... __args) + { + return _M_emplace_unique(__hint_policy, + std::forward<_Args>(__args)...).first; + } template iterator - _M_emplace(const_iterator, false_type __uks, _Args&&... __args); + _M_emplace(_HintPolicy& __hint_policy, + false_type /*__uks*/, _Args&&... __args) + { return _M_emplace_multi(__hint_policy, std::forward<_Args>(__args)...); } template std::pair - _M_insert_unique(_Kt&&, _Arg&&, _NodeGenerator&); + _M_insert_unique(_HintPolicy& __hint_policy, + _Kt&&, _Arg&&, _NodeGenerator&); template static __conditional_t< @@ -944,9 +1099,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template std::pair - _M_insert_unique_aux(_Arg&& __arg, _NodeGenerator& __node_gen) + _M_insert_unique_aux(_HintPolicy& __hint_policy, + _Arg&& __arg, _NodeGenerator& __node_gen) { - return _M_insert_unique( + return _M_insert_unique(__hint_policy, _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))), std::forward<_Arg>(__arg), __node_gen); } @@ -956,9 +1112,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_insert(_Arg&& __arg, _NodeGenerator& __node_gen, true_type /* __uks */) { + auto __hint_policy = _M_get_hint_policy(); using __to_value = __detail::_ConvertToValueType<_ExtractKey, value_type>; - return _M_insert_unique_aux( + return _M_insert_unique_aux(__hint_policy, __to_value{}(std::forward<_Arg>(__arg)), __node_gen); } @@ -967,32 +1124,35 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_insert(_Arg&& __arg, _NodeGenerator& __node_gen, false_type __uks) { + auto __hint_policy = _M_get_hint_policy(); using __to_value = __detail::_ConvertToValueType<_ExtractKey, value_type>; - return _M_insert(cend(), + return _M_insert(__hint_policy, __to_value{}(std::forward<_Arg>(__arg)), __node_gen, __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, - _NodeGenerator& __node_gen, true_type __uks) + _M_insert(_HintPolicy& __hint_policy, _Arg&& __arg, + _NodeGenerator& __node_gen, true_type /* __uks */) { - return - _M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).first; + using __to_value + = __detail::_ConvertToValueType<_ExtractKey, value_type>; + return _M_insert_unique_aux(__hint_policy, + __to_value{}(std::forward<_Arg>(__arg)), __node_gen).first; } // Insert with hint when keys are not unique. template iterator - _M_insert(const_iterator, _Arg&&, + _M_insert(_HintPolicy& __hint_policy, _Arg&& __arg, _NodeGenerator&, false_type __uks); template void _M_insert_range(_InputIterator __first, _InputIterator __last, - _NodeGenerator&); + _HintPolicy&, _NodeGenerator&); size_type _M_erase(true_type __uks, const key_type&); @@ -1014,7 +1174,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION iterator emplace_hint(const_iterator __hint, _Args&&... __args) { - return _M_emplace(__hint, __unique_keys{}, + auto __hint_policy = _M_get_hint_policy(__hint._M_cur); + return _M_emplace(__hint_policy, __unique_keys{}, std::forward<_Args>(__args)...); } @@ -1041,7 +1202,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Set number of buckets keeping it appropriate for container's number // of elements. - void rehash(size_type __bkt_count); + void rehash(size_type __bkt_count) + { + auto __hint_policy = _M_get_hint_policy(); + _M_rehash(__hint_policy, __bkt_count); + } // DR 1189. // reserve, if present, comes from _Rehash_base. @@ -1049,7 +1214,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()) @@ -1058,14 +1223,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { __glibcxx_assert(get_allocator() == __nh.get_allocator()); + auto __hint_policy = _M_get_hint_policy(__hint._M_cur); __node_ptr __n = nullptr; const key_type& __k = __nh._M_key(); const size_type __size = size(); if (__size <= __small_size_threshold()) { - for (__n = _M_begin(); __n; __n = __n->_M_next()) - if (this->_M_key_equals(__k, *__n)) - break; + __node_ptr __last_n = nullptr; + for (__n = _M_begin(); __n; + __last_n = __n, __n = __n->_M_next()) + { + if (this->_M_key_equals(__k, *__n)) + break; + } + + if (!__n) + __hint_policy._M_set_last(__last_n); } __hash_code __code; @@ -1086,8 +1259,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } else { - __ret.position - = _M_insert_unique_node(__bkt, __code, __nh._M_ptr); + __ret.position = _M_insert_unique_node( + __hint_policy, __bkt, __code, __nh._M_ptr); __nh._M_ptr = nullptr; __ret.inserted = true; } @@ -1104,10 +1277,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_assert(get_allocator() == __nh.get_allocator()); + auto __hint_policy = _M_get_hint_policy(__hint._M_cur); const key_type& __k = __nh._M_key(); - auto __code = this->_M_hash_code(__k); - auto __ret - = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr); + auto __info = _M_get_insert_info(__hint_policy, __k); + auto __ret = _M_insert_multi_node(__hint_policy, __info, __nh._M_ptr); __nh._M_ptr = nullptr; return __ret; } @@ -1147,6 +1320,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return this->_M_hash_code(__k); } + template + _InsertInfo + _M_get_insert_info(const _H2&, _HintPolicy& __hint_policy, + __node_ptr __n, const key_type& __k) + { + if constexpr (std::is_same_v<_H2, _Hash>) + if constexpr (std::is_empty_v<_Hash>) + return _M_get_insert_info(__hint_policy, __k, __n); + + return _M_get_insert_info(__hint_policy, __k); + } + public: // Extract a node. node_type @@ -1178,6 +1363,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION node_type>, "Node types are compatible"); __glibcxx_assert(get_allocator() == __src.get_allocator()); + auto __hint_policy = _M_get_hint_policy(); auto __n_elt = __src.size(); for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;) { @@ -1186,8 +1372,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION const key_type& __k = _ExtractKey{}(*__pos); if (__size <= __small_size_threshold()) { + __node_ptr __last_n = nullptr; bool __found = false; - for (auto __n = _M_begin(); __n; __n = __n->_M_next()) + for (auto __n = _M_begin(); __n; + __last_n = __n, __n = __n->_M_next()) if (this->_M_key_equals(__k, *__n)) { __found = true; @@ -1200,6 +1388,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION --__n_elt; continue; } + else + __hint_policy._M_set_last(__last_n); } __hash_code __code @@ -1209,7 +1399,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION || _M_find_node(__bkt, __k, __code) == nullptr) { auto __nh = __src.extract(__pos); - _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt); + _M_insert_unique_node( + __hint_policy, __bkt, __code, __nh._M_ptr, __n_elt); __nh._M_ptr = nullptr; __n_elt = 1; } @@ -1227,27 +1418,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION node_type>, "Node types are compatible"); __glibcxx_assert(get_allocator() == __src.get_allocator()); - __node_ptr __hint = nullptr; + auto __hint_policy = _M_get_hint_policy(); this->reserve(size() + __src.size()); for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;) { auto __pos = __i++; const key_type& __k = _ExtractKey{}(*__pos); - __hash_code __code - = _M_src_hash_code(__src.hash_function(), __k, *__pos._M_cur); + auto __info = _M_get_insert_info(__src.hash_function(), + __hint_policy, __pos._M_cur, __k); auto __nh = __src.extract(__pos); - __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur; + _M_insert_multi_node(__hint_policy, __info, __nh._M_ptr); __nh._M_ptr = nullptr; } } #endif // C++17 private: + void _M_rehash(_HintPolicy&, size_type __bkt_count); + // Helper rehash method used when keys are unique. - void _M_rehash(size_type __bkt_count, true_type __uks); + void _M_rehash(_HintPolicy&, size_type __bkt_count, true_type __uks); // Helper rehash method used when keys can be non-unique. - void _M_rehash(size_type __bkt_count, false_type __uks); + void _M_rehash(_HintPolicy&, size_type __bkt_count, false_type __uks); }; // Definitions of class template _Hashtable's out-of-line member functions. @@ -1308,8 +1501,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_bucket_count = __bkt_count; } + auto __hint_policy = _M_get_hint_policy(); __alloc_node_gen_t __node_gen(*this); - _M_insert_range(__f, __l, __node_gen); + _M_insert_range(__f, __l, __hint_policy, __node_gen); } template_M_node_allocator(), __ht._M_node_allocator()); + _M_set_last(__ht._M_get_last()); // Fix bucket containing the _M_before_begin pointer that can't be moved. _M_update_bbegin(); + __ht._M_reset(); } @@ -1575,6 +1774,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_before_begin(__ht._M_before_begin._M_nxt), _M_element_count(__ht._M_element_count), _M_rehash_policy(__ht._M_rehash_policy) +#if _GLIBCXX_INLINE_VERSION + , _M_last(__ht._M_last) +#endif { // Update buckets if __ht is using its single bucket. if (__ht._M_uses_single_bucket()) @@ -1638,6 +1840,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION else _M_buckets = __ht._M_buckets; + _M_set_last(__ht._M_get_last()); + // Fix bucket containing the _M_before_begin pointer that can't be // moved. _M_update_bbegin(__ht._M_begin()); @@ -2147,7 +2351,7 @@ _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(_HintPolicy& __hint_policy, _Args&&... __args) -> pair { // First build the node to get access to the hash code @@ -2156,10 +2360,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION const size_type __size = size(); if (__size <= __small_size_threshold()) { - for (auto __it = _M_begin(); __it; __it = __it->_M_next()) - if (this->_M_key_equals(__k, *__it)) + __node_ptr __last_n = nullptr; + for (auto __n = _M_begin(); __n; + __last_n = __n, __n = __n->_M_next()) + if (this->_M_key_equals(__k, *__n)) // There is already an equivalent node, no insertion - return { iterator(__it), false }; + return { iterator(__n), false }; + + __hint_policy._M_set_last(__last_n); } __hash_code __code = this->_M_hash_code(__k); @@ -2170,7 +2378,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return { iterator(__p), false }; // Insert the node - auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node); + auto __pos = _M_insert_unique_node(__hint_policy, __bkt, __code, + __node._M_node); __node._M_node = nullptr; return { __pos, true }; } @@ -2183,17 +2392,15 @@ _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(_HintPolicy& __hint_policy, _Args&&... __args) -> iterator { // First build the node to get its hash code. _Scoped_node __node { this, std::forward<_Args>(__args)... }; const key_type& __k = _ExtractKey{}(__node._M_node->_M_v()); - auto __res = this->_M_compute_hash_code(__hint._M_cur, __k); - auto __pos - = _M_insert_multi_node(__res.first, __res.second, __node._M_node); + auto __info = _M_get_insert_info(__hint_policy, __k); + auto __pos = _M_insert_multi_node(__hint_policy, __info, __node._M_node); __node._M_node = nullptr; return __pos; } @@ -2205,26 +2412,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_compute_hash_code(__node_ptr __hint, const key_type& __k) const - -> pair<__node_ptr, __hash_code> + _M_get_insert_info(_HintPolicy& __hint_policy, const key_type& __k, + __node_ptr __equi_n) const + -> _InsertInfo { if (size() <= __small_size_threshold()) { - if (__hint) - { - for (auto __it = __hint; __it; __it = __it->_M_next()) - if (this->_M_key_equals(__k, *__it)) - return { __it, this->_M_hash_code(*__it) }; - } - - for (auto __it = _M_begin(); __it != __hint; __it = __it->_M_next()) - if (this->_M_key_equals(__k, *__it)) - return { __it, this->_M_hash_code(*__it) }; + __node_ptr __last_n = nullptr; + __node_base_ptr __prev + = const_cast<__node_base_ptr>(&_M_before_begin); + for (auto __n = static_cast<__node_ptr>(__prev->_M_nxt); __n; + __prev = __last_n = __n, __n = __n->_M_next()) + if (this->_M_key_equals(__k, *__n)) + return + { + __prev, __n, + __hash_cached::value ? this->_M_hash_code(*__n) : 0 + }; - __hint = nullptr; + __hint_policy._M_set_last(__last_n); } - return { __hint, this->_M_hash_code(__k) }; + return + { + nullptr, nullptr, + __equi_n ? this->_M_hash_code(*__equi_n) : this->_M_hash_code(__k) + }; } template:: - _M_insert_unique_node(size_type __bkt, __hash_code __code, + _M_insert_unique_node(_HintPolicy& __hint_policy, + size_type __bkt, __hash_code __code, __node_ptr __node, size_type __n_elt) -> iterator { @@ -2245,7 +2459,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__do_rehash.first) { - _M_rehash(__do_rehash.second, true_type{}); + _M_rehash(__hint_policy, __do_rehash.second, true_type{}); __bkt = _M_bucket_index(__code); } @@ -2253,7 +2467,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION this->_M_store_code(*__node, __code); // Always insert at the beginning of the bucket. - _M_insert_bucket_begin(__bkt, __node); + _M_insert_bucket_begin(__hint_policy, __bkt, __node); ++_M_element_count; return iterator(__node); } @@ -2265,8 +2479,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_insert_multi_node(__node_ptr __hint, - __hash_code __code, __node_ptr __node) + _M_insert_multi_node(_HintPolicy& __hint_policy, + const _InsertInfo& __info, __node_ptr __node) -> iterator { __rehash_guard_t __rehash_guard(_M_rehash_policy); @@ -2274,42 +2488,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1); if (__do_rehash.first) - _M_rehash(__do_rehash.second, false_type{}); + _M_rehash(__hint_policy, __do_rehash.second, false_type{}); __rehash_guard._M_guarded_obj = nullptr; + auto __code = __info._M_code; this->_M_store_code(*__node, __code); const key_type& __k = _ExtractKey{}(__node->_M_v()); - size_type __bkt = _M_bucket_index(__code); + auto __prev = __info._M_prev; + const bool __has_prev = __prev != nullptr; + size_type __bkt; // Find the node before an equivalent one or use hint if it exists and // if it is equivalent. - __node_base_ptr __prev - = __builtin_expect(__hint != nullptr, false) - && this->_M_equals(__k, __code, *__hint) - ? __hint - : _M_find_before_node(__bkt, __k, __code); + if (!__has_prev) + { + __bkt = _M_bucket_index(__code); + __prev = _M_find_before_node(__bkt, __k, __code); + } if (__prev) { // Insert after the node before the equivalent one. __node->_M_nxt = __prev->_M_nxt; __prev->_M_nxt = __node; - if (__builtin_expect(__prev == __hint, false)) - // hint might be the last bucket node, in this case we need to - // update next bucket. - if (__node->_M_nxt - && !this->_M_equals(__k, __code, *__node->_M_next())) - { - size_type __next_bkt = _M_bucket_index(*__node->_M_next()); - if (__next_bkt != __bkt) - _M_buckets[__next_bkt] = __node; - } + + // __hint might be the last bucket node, in this case we need to + // update next bucket. + if (__has_prev && __node->_M_nxt != __info._M_equi_n) + { + const auto __nxt = __node->_M_next(); + if (!this->_M_equals(__k, __code, *__nxt)) + { + size_type __next_bkt = _M_bucket_index(*__nxt); + if (__next_bkt != _M_bucket_index(__code)) + _M_buckets[__next_bkt] = __node; + } + } + + __hint_policy._M_checked_set(__node); } else - // The inserted node has no equivalent in the hashtable. We must - // insert the new node at the beginning of the bucket to preserve - // equivalent elements' relative positions. - _M_insert_bucket_begin(__bkt, __node); + { + // The inserted node has no equivalent in the hashtable. We must + // insert the new node at the beginning of the bucket to preserve + // equivalent elements' relative positions. + _M_insert_bucket_begin(__hint_policy, __bkt, __node); + } + ++_M_element_count; return iterator(__node); } @@ -2323,15 +2548,21 @@ _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(_HintPolicy& __hint_policy, _Kt&& __k, _Arg&& __v, _NodeGenerator& __node_gen) -> pair { const size_type __size = size(); if (__size <= __small_size_threshold()) - for (auto __it = _M_begin(); __it; __it = __it->_M_next()) - if (this->_M_key_equals_tr(__k, *__it)) - return { iterator(__it), false }; + { + __node_ptr __last_n = nullptr; + for (auto __n = _M_begin(); __n; + __last_n = __n, __n = __n->_M_next()) + if (this->_M_key_equals_tr(__k, *__n)) + return { iterator(__n), false }; + + __hint_policy._M_set_last(__last_n); + } __hash_code __code = this->_M_hash_code_tr(__k); size_type __bkt = _M_bucket_index(__code); @@ -2346,8 +2577,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __node_gen), this }; + auto __pos - = _M_insert_unique_node(__bkt, __code, __node._M_node); + = _M_insert_unique_node(__hint_policy, __bkt, __code, __node._M_node); __node._M_node = nullptr; return { __pos, true }; } @@ -2361,20 +2593,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_insert(const_iterator __hint, _Arg&& __v, - _NodeGenerator& __node_gen, - false_type /* __uks */) + _M_insert(_HintPolicy& __hint_policy, _Arg&& __v, + _NodeGenerator& __node_gen, false_type /* __uks */) -> 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(std::forward<_Arg>(__v)), this }; // Second compute the hash code so that we don't rehash if it throws. - auto __res = this->_M_compute_hash_code( - __hint._M_cur, _ExtractKey{}(__node._M_node->_M_v())); - - auto __pos - = _M_insert_multi_node(__res.first, __res.second, __node._M_node); + auto __info = + _M_get_insert_info(__hint_policy, + _ExtractKey{}(__node._M_node->_M_v())); + auto __pos = _M_insert_multi_node(__hint_policy, + __info, __node._M_node); __node._M_node = nullptr; return __pos; } @@ -2388,10 +2619,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_insert_range(_InputIterator __first, _InputIterator __last, - _NodeGenerator& __node_gen) + _HintPolicy& __hint_policy, _NodeGenerator& __node_gen) { for (; __first != __last; ++__first) - _M_insert(*__first, __node_gen, __unique_keys{}); + _M_insert(__hint_policy, *__first, __node_gen, __unique_keys{}); } template_M_next()); this->_M_deallocate_node(__n); --_M_element_count; - + _M_check_for_last(__prev_n); return __result; } @@ -2547,7 +2778,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt); else if (__n_last_bkt != __bkt) _M_buckets[__n_last_bkt] = __prev_n; + __prev_n->_M_nxt = __n_last; + _M_check_for_last(__prev_n); return __result; } @@ -2595,6 +2828,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__n && (__n_bkt != __bkt || __is_bucket_begin)) _M_buckets[__n_bkt] = __prev_n; __prev_n->_M_nxt = __n; + _M_check_for_last(__prev_n); return iterator(__n); } @@ -2612,6 +2846,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_bucket_count * sizeof(__node_base_ptr)); _M_element_count = 0; _M_before_begin._M_nxt = nullptr; + _M_set_last(nullptr); } template:: - rehash(size_type __bkt_count) + _M_rehash(_HintPolicy& __hint_policy, size_type __bkt_count) { __rehash_guard_t __rehash_guard(_M_rehash_policy); __bkt_count @@ -2631,7 +2866,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__bkt_count != _M_bucket_count) { - _M_rehash(__bkt_count, __unique_keys{}); + _M_rehash(__hint_policy, __bkt_count, __unique_keys{}); __rehash_guard._M_guarded_obj = nullptr; } } @@ -2644,9 +2879,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_rehash(size_type __bkt_count, true_type /* __uks */) + _M_rehash(_HintPolicy& __hint_policy, + size_type __bkt_count, true_type /* __uks */) { __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count); + __node_ptr __prev_p = nullptr; __node_ptr __p = _M_begin(); _M_before_begin._M_nxt = nullptr; std::size_t __bbegin_bkt = 0; @@ -2670,12 +2907,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __new_buckets[__bkt]->_M_nxt = __p; } + __prev_p = __p; __p = __next; } _M_deallocate_buckets(); _M_bucket_count = __bkt_count; _M_buckets = __new_buckets; + __hint_policy._M_set_last(__prev_p); } // Rehash when there can be equivalent elements, preserve their relative @@ -2687,7 +2926,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_rehash(size_type __bkt_count, false_type /* __uks */) + _M_rehash(_HintPolicy& __hint_policy, + size_type __bkt_count, false_type /* __uks */) { __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count); __node_ptr __p = _M_begin(); @@ -2750,6 +2990,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __new_buckets[__bkt]->_M_nxt = __p; } } + __prev_p = __p; __prev_bkt = __bkt; __p = __next; @@ -2767,6 +3008,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_deallocate_buckets(); _M_bucket_count = __bkt_count; _M_buckets = __new_buckets; + __hint_policy._M_set_last(__prev_p); } #if __cplusplus > 201402L diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 9f775522cff..c8905f59289 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -848,8 +848,9 @@ namespace __detail std::tuple(__k), std::tuple<>() }; - auto __pos - = __h->_M_insert_unique_node(__bkt, __code, __node._M_node); + auto __hint_policy = __h->_M_get_hint_policy(); + auto __pos = __h->_M_insert_unique_node(__hint_policy, __bkt, __code, + __node._M_node); __node._M_node = nullptr; return __pos->second; } @@ -875,8 +876,9 @@ namespace __detail std::forward_as_tuple(std::move(__k)), std::tuple<>() }; - auto __pos - = __h->_M_insert_unique_node(__bkt, __code, __node._M_node); + auto __hint_policy = __h->_M_get_hint_policy(); + auto __pos = __h->_M_insert_unique_node(__hint_policy, __bkt, __code, + __node._M_node); __node._M_node = nullptr; return __pos->second; } @@ -964,13 +966,14 @@ namespace __detail insert(const_iterator __hint, const value_type& __v) { __hashtable& __h = _M_conjure_hashtable(); - __node_gen_type __node_gen(__h); - return __h._M_insert(__hint, __v, __node_gen, __unique_keys{}); + auto __hint_policy = __h._M_get_hint_policy(__hint._M_cur); + __node_gen_type __node_gen(__h); + return __h._M_insert(__hint_policy, __v, __node_gen, __unique_keys{}); } 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); @@ -984,8 +987,9 @@ namespace __detail std::forward_as_tuple(std::forward<_KType>(__k)), std::forward_as_tuple(std::forward<_Args>(__args)...) }; - auto __it - = __h._M_insert_unique_node(__bkt, __code, __node._M_node); + auto __hint_policy = __h._M_get_hint_policy(__hint._M_cur); + auto __it = __h._M_insert_unique_node(__hint_policy, __bkt, __code, + __node._M_node); __node._M_node = nullptr; return { __it, true }; } @@ -1013,8 +1017,9 @@ namespace __detail true_type /* __uks */) { __hashtable& __h = _M_conjure_hashtable(); + auto __hint_policy = __h._M_get_hint_policy(); __node_gen_type __node_gen(__h); - __h._M_insert_range(__first, __last, __node_gen); + __h._M_insert_range(__first, __last, __hint_policy, __node_gen); } template_M_conjure_hashtable(); + auto __hint_policy = __h._M_get_hint_policy(__hint._M_cur); __node_gen_type __node_gen(__h); - return __h._M_insert(__hint, std::move(__v), __node_gen, + return __h._M_insert(__hint_policy, std::move(__v), __node_gen, __unique_keys{}); } }; @@ -1153,7 +1160,8 @@ namespace __detail insert(const_iterator __hint, _Pair&& __v) { __hashtable& __h = this->_M_conjure_hashtable(); - return __h._M_emplace(__hint, __unique_keys{}, + auto __hint_policy = __h._M_get_hint_policy(__hint._M_cur); + return __h._M_emplace(__hint_policy, __unique_keys{}, std::forward<_Pair>(__v)); } }; diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h index 1c99a83bc1e..e5df97c9229 100644 --- a/libstdc++-v3/include/bits/unordered_map.h +++ b/libstdc++-v3/include/bits/unordered_map.h @@ -443,12 +443,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 #ifdef __glibcxx_unordered_map_try_emplace // C++ >= 17 && HOSTED diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h index f3b0c078baa..915cd4fb700 100644 --- a/libstdc++-v3/include/bits/unordered_set.h +++ b/libstdc++-v3/include/bits/unordered_set.h @@ -504,12 +504,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 ///@{ diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc index d0ed60c6799..1db71b8f30b 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc @@ -40,11 +40,12 @@ void test01() VERIFY( it2 != m.end() ); VERIFY( it2 != it1 ); VERIFY( it2->second == 2 ); - VERIFY( it2 == std::next(it1) ); + VERIFY( std::next(it2) == it1 ); + it1 = it2; Pair p(0, 1); it2 = m.insert(it1, p); - VERIFY( it2 == std::next(it1) ); + VERIFY( std::next(it2) == it1 ); } struct hasher @@ -71,13 +72,13 @@ void test02() VERIFY( m.bucket_size(m.bucket(it3->first)) == 1 ); auto it4 = m.insert(it1, Pair(0, 1)); - VERIFY( it4 == std::next(it1) ); + VERIFY( std::next(it4) == it1 ); VERIFY( m.bucket_size(m.bucket(it1->first)) == 3 ); VERIFY( m.bucket_size(m.bucket(it3->first)) == 1 ); Pair p(1, 1); it4 = m.insert(it2, p); - VERIFY( it4 == std::next(it2) ); + VERIFY( std::next(it4) == it2 ); VERIFY( m.bucket_size(m.bucket(it1->first)) == 4 ); auto range = m.equal_range(0); VERIFY( std::distance(range.first, range.second) == 2 ); @@ -104,11 +105,12 @@ void test03() VERIFY( it2 != m.end() ); VERIFY( it2 != it1 ); VERIFY( it2->second == 2 ); - VERIFY( it2 == std::next(it1) ); + VERIFY( std::next(it2) == it1 ); + it1 = it2; Pair p(0, 1); it2 = m.emplace_hint(it1, p); - VERIFY( it2 == std::next(it1) ); + VERIFY( std::next(it2) == it1 ); } int main()