From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wr1-x42f.google.com (mail-wr1-x42f.google.com [IPv6:2a00:1450:4864:20::42f]) by sourceware.org (Postfix) with ESMTPS id 180C23858421; Mon, 25 Oct 2021 18:08:58 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 180C23858421 Received: by mail-wr1-x42f.google.com with SMTP id s19so14271573wra.2; Mon, 25 Oct 2021 11:08:58 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language; bh=LHHpJJccaB2RwS5eMkLWizSEsYvepkE99mABTEYQdUU=; b=NDroRUpEFeaSvHzofXAYdkTIU2r63kNphvsYf0GQG/qIm3DmN5hQJqDyf9ZNG7qEJh 52Hnf4b6qqywmqDmCDQ1OuxlNgUTX04zkl3AwkSrMctmL1Ank75rjqnKPavHAKNZ7Dd3 u4/EBMouIPEyXrqrCMReZ69t2iKipl/WZVg0bQIz1FWbCCknmIqxSxFnvB+xg97YcuFl 7gp6QD1wez18w0NKH8/5smH3Vv9HMfgYjSVRKynEwCa7iO1UQbwyjxXZKmZuYk0qn/mK euVzpwwv6J3H1aGggqag5P1LJOmSUWsBvLEgNdkLway8OgWAuZk4ZB/9jHPuLKd3Gjej lfnw== X-Gm-Message-State: AOAM533JCv9q9oVX8guNf1a8JTrwzH/J8Ecu9lLWC8CkhKyZCqZgxhX9 2SRP7qPwpyPUUJ5m0iUbjNLG+FBrTEdRf8xh X-Google-Smtp-Source: ABdhPJwAQrvrde/7VlSK0nKqHg0csZaNt95RFxRBeYNzQTwy4X8qMkLKk1Rp+wBFuC7d2FUhCvOETg== X-Received: by 2002:a5d:47a7:: with SMTP id 7mr24988439wrb.75.1635185336934; Mon, 25 Oct 2021 11:08:56 -0700 (PDT) Received: from ?IPv6:2a01:cb22:899:ea00:c1ac:388:3df1:e319? ([2a01:cb22:899:ea00:c1ac:388:3df1:e319]) by smtp.googlemail.com with ESMTPSA id o11sm24445519wry.0.2021.10.25.11.08.50 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 25 Oct 2021 11:08:56 -0700 (PDT) Subject: Re: [PATH][_GLIBCXX_DEBUG] Fix unordered container merge To: Jonathan Wakely Cc: Jonathan Wakely , libstdc++ , gcc-patches References: <4eec3fb9-851e-3e4e-f9f4-1110db3af747@gmail.com> <6c349652-8b6f-2027-08c3-6ce58a765aeb@gmail.com> From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= Message-ID: <22bf1b42-8cf4-7a6e-d5dc-c322ccbb2b46@gmail.com> Date: Mon, 25 Oct 2021 20:08:47 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.13.0 MIME-Version: 1.0 In-Reply-To: Content-Type: multipart/mixed; boundary="------------D07B317F03D3724DFE79F89D" Content-Language: fr X-Spam-Status: No, score=-11.7 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, HTML_MESSAGE, NICE_REPLY_A, 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-Content-Filtered-By: Mailman/MimeDel 2.1.29 X-BeenThere: libstdc++@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++ mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 25 Oct 2021 18:09:03 -0000 This is a multi-part message in MIME format. --------------D07B317F03D3724DFE79F89D Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit New patch with the proposed workaround below. I also slightly change the _M_merge_multi implementation so that if the new hash code computation raise an exception the node is simply not extracted rather than extracted and then released. This way, if it takes place on the 1st moved node the _GLIBCXX_DEBUG mode won't try to invalidate anything because the source size won't have changed. Ok to commit ? François On 16/10/21 4:52 pm, Jonathan Wakely wrote: > > > On Sat, 16 Oct 2021, 14:49 François Dumont via Libstdc++, > > wrote: > > Hi > >      Here is the new proposal. My only concern is that we are also > using > hash or equal_to functors in the guard destructor. > > > > Can we catch any exception there, invalidate all iterators, and not > rethrow the exception? > > >      I am going to enhance merge normal implementation to make use of > the cached hash code when hash functors are the same between the > source > and destination of nodes. Maybe I'll be able to make use of it in > Debug > implementation too. > > François > > > On 14/10/21 10:23 am, Jonathan Wakely wrote: > > On Wed, 13 Oct 2021 at 18:10, François Dumont via Libstdc++ > > > wrote: > >> Hi > >> > >>       libstdc++: [_GLIBCXX_DEBUG] Implement unordered container > merge > >> > >>       The _GLIBCXX_DEBUG unordered containers need a dedicated > merge > >> implementation > >>       so that any existing iterator on the transfered nodes is > properly > >> invalidated. > >> > >>       Add typedef/using declaration for everything used as-is > from normal > >> implementation. > >> > >>       libstdc++-v3/ChangeLog: > >> > >>               * include/debug/safe_container.h > (_Safe_container<>): Make > >> all methods > >>               protected. > >>               * include/debug/safe_unordered_container.h > >>  (_Safe_unordered_container<>::_M_invalide_all): Make public. > >>  (_Safe_unordered_container<>::_M_invalide_if): Likewise. > >> (_Safe_unordered_container<>::_M_invalide_local_if): Likewise. > >>               * include/debug/unordered_map > >>  (unordered_map<>::mapped_type, pointer, const_pointer): New > >> typedef. > >>               (unordered_map<>::reference, const_reference, > >> difference_type): New typedef. > >>  (unordered_map<>::get_allocator, empty, size, max_size): > >> Add usings. > >>  (unordered_map<>::bucket_count, max_bucket_count, bucket): > >> Add usings. > >>  (unordered_map<>::hash_function, key_equal, count, > >> contains): Add usings. > >>               (unordered_map<>::operator[], at, rehash, > reserve): Add usings. > >>               (unordered_map<>::merge): New. > >>  (unordered_multimap<>::mapped_type, pointer, > >> const_pointer): New typedef. > >>  (unordered_multimap<>::reference, const_reference, > >> difference_type): New typedef. > >>  (unordered_multimap<>::get_allocator, empty, size, > >> max_size): Add usings. > >>  (unordered_multimap<>::bucket_count, max_bucket_count, > >> bucket): Add usings. > >>  (unordered_multimap<>::hash_function, key_equal, count, > >> contains): Add usings. > >>  (unordered_multimap<>::rehash, reserve): Add usings. > >>  (unordered_multimap<>::merge): New. > >>               * include/debug/unordered_set > >>  (unordered_set<>::mapped_type, pointer, const_pointer): New > >> typedef. > >>               (unordered_set<>::reference, const_reference, > >> difference_type): New typedef. > >>  (unordered_set<>::get_allocator, empty, size, max_size): > >> Add usings. > >>  (unordered_set<>::bucket_count, max_bucket_count, bucket): > >> Add usings. > >>  (unordered_set<>::hash_function, key_equal, count, > >> contains): Add usings. > >>               (unordered_set<>::rehash, reserve): Add usings. > >>               (unordered_set<>::merge): New. > >>  (unordered_multiset<>::mapped_type, pointer, > >> const_pointer): New typedef. > >>  (unordered_multiset<>::reference, const_reference, > >> difference_type): New typedef. > >>  (unordered_multiset<>::get_allocator, empty, size, > >> max_size): Add usings. > >>  (unordered_multiset<>::bucket_count, max_bucket_count, > >> bucket): Add usings. > >>  (unordered_multiset<>::hash_function, key_equal, count, > >> contains): Add usings. > >>  (unordered_multiset<>::rehash, reserve): Add usings. > >>  (unordered_multiset<>::merge): New. > >>               * > >> testsuite/23_containers/unordered_map/debug/merge1_neg.cc: New > test. > >>               * > >> testsuite/23_containers/unordered_map/debug/merge2_neg.cc: New > test. > >>               * > >> testsuite/23_containers/unordered_map/debug/merge3_neg.cc: New > test. > >>               * > >> testsuite/23_containers/unordered_map/debug/merge4_neg.cc: New > test. > >>               * > >> testsuite/23_containers/unordered_multimap/debug/merge1_neg.cc: > New test. > >>               * > >> testsuite/23_containers/unordered_multimap/debug/merge2_neg.cc: > New test. > >>               * > >> testsuite/23_containers/unordered_multimap/debug/merge3_neg.cc: > New test. > >>               * > >> testsuite/23_containers/unordered_multimap/debug/merge4_neg.cc: > New test. > >>               * > >> testsuite/23_containers/unordered_multiset/debug/merge1_neg.cc: > New test. > >>               * > >> testsuite/23_containers/unordered_multiset/debug/merge2_neg.cc: > New test. > >>               * > >> testsuite/23_containers/unordered_multiset/debug/merge3_neg.cc: > New test. > >>               * > >> testsuite/23_containers/unordered_multiset/debug/merge4_neg.cc: > New test. > >>               * > >> testsuite/23_containers/unordered_set/debug/merge1_neg.cc: New > test. > >>               * > >> testsuite/23_containers/unordered_set/debug/merge2_neg.cc: New > test. > >>               * > >> testsuite/23_containers/unordered_set/debug/merge3_neg.cc: New > test. > >>               * > >> testsuite/23_containers/unordered_set/debug/merge4_neg.cc: New > test. > >>               * testsuite/util/testsuite_abi.h: > [_GLIBCXX_DEBUG] Use > >> normal unordered container implementation. > >> > >> Tested under Linux x86_64. > >> > >> Ok to commit ? > > Yes, thanks. But ... > > > > This looks like an improvement over what we have now, but not 100% > > correct. The merge functions can exit via exception (if any hash > > function or equality predicate throws), and if that happens the safe > > iterators will not get invalidated. I think we need to call > > _Base::merge in a try-block, and do the iterator invalidation > whether > > we return normally or via an exception. > > > > Something like: > > > >    template > >      void > >      merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source) > >      { > >        struct _Guard > >        { > >          _Guard(unordered_set& __source) noexcept > >          : _M_source(__source), _M_size(__source.size()) > >          { } > > > >          ~_Guard() > >          { > >            const size_type __size = _M_source.size(); > >            if (__size != _M_size) > >              { > >                if (__size == 0) > >                  _M_source._M_invalidate_all(); > >                else > >                  { > >                    auto __pred = [&__source](auto __it) > >                                  { return __source.count(*__it) > == 0; }; > >                    __source._M_invalidate_if(__pred); > > __source._M_invalidate_local_if(__pred); > >                  } > >              } > >          } > > > >          _Guard(const _Guard&) = delete; > > > >          unordered_set& _M_source; > >          const size_type _M_size; > >        }; > >        _Guard __guard(__source); > >        _Base::merge(__source._M_base()); > >      } > > > --------------D07B317F03D3724DFE79F89D Content-Type: text/x-patch; charset=UTF-8; name="merge.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="merge.patch" diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index ff8af2201cd..dc011013d95 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -1064,14 +1064,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION /// Merge from a compatible container into one with unique keys. template void - _M_merge_unique(_Compatible_Hashtable& __src) noexcept + _M_merge_unique(_Compatible_Hashtable& __src) { static_assert(is_same_v, "Node types are compatible"); __glibcxx_assert(get_allocator() == __src.get_allocator()); auto __n_elt = __src.size(); - for (auto __i = __src.begin(), __end = __src.end(); __i != __end;) + for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;) { auto __pos = __i++; const key_type& __k = _ExtractKey{}(*__pos); @@ -1092,15 +1092,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION /// Merge from a compatible container into one with equivalent keys. template void - _M_merge_multi(_Compatible_Hashtable& __src) noexcept + _M_merge_multi(_Compatible_Hashtable& __src) { static_assert(is_same_v, "Node types are compatible"); __glibcxx_assert(get_allocator() == __src.get_allocator()); this->reserve(size() + __src.size()); - for (auto __i = __src.begin(), __end = __src.end(); __i != __end;) - _M_reinsert_node_multi(cend(), __src.extract(__i++)); + for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;) + { + auto __pos = __i++; + const key_type& __k = _ExtractKey{}(*__pos); + __hash_code __code = this->_M_hash_code(__k); + auto __nh = __src.extract(__pos); + _M_insert_multi_node(nullptr, __code, __nh._M_ptr); + __nh._M_ptr = nullptr; + } } #endif // C++17 diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 994c7b61046..23ebd137467 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -59,19 +59,19 @@ namespace __detail // Helper function: return distance(first, last) for forward // iterators, or 0/1 for input iterators. - template + template inline typename std::iterator_traits<_Iterator>::difference_type __distance_fw(_Iterator __first, _Iterator __last, std::input_iterator_tag) { return __first != __last ? 1 : 0; } - template + template inline typename std::iterator_traits<_Iterator>::difference_type __distance_fw(_Iterator __first, _Iterator __last, std::forward_iterator_tag) { return std::distance(__first, __last); } - template + template inline typename std::iterator_traits<_Iterator>::difference_type __distance_fw(_Iterator __first, _Iterator __last) { return __distance_fw(__first, __last, diff --git a/libstdc++-v3/include/debug/safe_container.h b/libstdc++-v3/include/debug/safe_container.h index 97c47167fe8..5de55d69f34 100644 --- a/libstdc++-v3/include/debug/safe_container.h +++ b/libstdc++-v3/include/debug/safe_container.h @@ -78,7 +78,6 @@ namespace __gnu_debug { } #endif - public: // Copy assignment invalidate all iterators. _Safe_container& operator=(const _Safe_container&) _GLIBCXX_NOEXCEPT diff --git a/libstdc++-v3/include/debug/safe_unordered_container.h b/libstdc++-v3/include/debug/safe_unordered_container.h index aae1e2dab60..06d0e91282c 100644 --- a/libstdc++-v3/include/debug/safe_unordered_container.h +++ b/libstdc++-v3/include/debug/safe_unordered_container.h @@ -72,6 +72,7 @@ namespace __gnu_debug { return __it != __local_end; }); } + public: void _M_invalidate_all() { diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map index bb697d364ea..927361cbc48 100644 --- a/libstdc++-v3/include/debug/unordered_map +++ b/libstdc++-v3/include/debug/unordered_map @@ -97,7 +97,12 @@ namespace __debug typedef typename _Base::key_type key_type; typedef typename _Base::value_type value_type; + typedef typename _Base::mapped_type mapped_type; + typedef typename _Base::pointer pointer; + typedef typename _Base::const_pointer const_pointer; + typedef typename _Base::reference reference; + typedef typename _Base::const_reference const_reference; typedef __gnu_debug::_Safe_iterator< _Base_iterator, unordered_map> iterator; typedef __gnu_debug::_Safe_iterator< @@ -106,6 +111,7 @@ namespace __debug _Base_local_iterator, unordered_map> local_iterator; typedef __gnu_debug::_Safe_local_iterator< _Base_const_local_iterator, unordered_map> const_local_iterator; + typedef typename _Base::difference_type difference_type; unordered_map() = default; @@ -209,6 +215,11 @@ namespace __debug return *this; } + using _Base::get_allocator; + using _Base::empty; + using _Base::size; + using _Base::max_size; + void swap(unordered_map& __x) noexcept( noexcept(declval<_Base&>().swap(__x)) ) @@ -291,6 +302,10 @@ namespace __debug return { _Base::cend(__b), this }; } + using _Base::bucket_count; + using _Base::max_bucket_count; + using _Base::bucket; + size_type bucket_size(size_type __b) const { @@ -298,6 +313,8 @@ namespace __debug return _Base::bucket_size(__b); } + using _Base::load_factor; + float max_load_factor() const noexcept { return _Base::max_load_factor(); } @@ -538,9 +555,127 @@ namespace __debug return { _Base::insert(__hint.base(), std::move(__nh)), this }; } - using _Base::merge; + private: + template + struct _UMapGuard + { + _UMapGuard(_Source& __source) noexcept + : _M_source(__source), _M_size(__source.size()) + { } + + _UMapGuard(const _UMapGuard&) = delete; + + ~_UMapGuard() + { + const size_type __size = _M_source.size(); + if (__size == _M_size) + return; + + __try + { + if (__size == 0) + _M_source._M_invalidate_all(); + else + { + auto __pred = + [this](auto __it) + { return _M_source.count(__it->second) == 0; }; + _M_source._M_invalidate_if(__pred); + _M_source._M_invalidate_local_if(__pred); + } + } + __catch(...) + { + _M_source._M_invalidate_all(); + } + } + + _Source& _M_source; + const size_type _M_size; + }; + + public: + template + void + merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source) + { + _UMapGuard __guard(__source); + _Base::merge(__source._M_base()); + } + + template + void + merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source) + { merge(__source); } + + private: + template + struct _UMMapGuard + { + _UMMapGuard(_Source& __source) noexcept + : _M_source(__source), _M_size(__source.size()) + { } + + _UMMapGuard(const _UMMapGuard&) = delete; + + ~_UMMapGuard() + { + const size_type __size = _M_source.size(); + if (__size == _M_size) + return; + + __try + { + if (__size == 0) + _M_source._M_invalidate_all(); + else + { + auto __pred = + [this](auto __it) + { + auto __rng = + _M_source._M_base().equal_range(__it->first); + for (auto __rit = __rng.first; + __rit != __rng.second; ++__rit) + { + if (__it == __rit) + return false; + } + + return true; + }; + _M_source._M_invalidate_if(__pred); + _M_source._M_invalidate_local_if(__pred); + } + } + __catch(...) + { + _M_source._M_invalidate_all(); + } + } + + _Source& _M_source; + const size_type _M_size; + }; + + public: + template + void + merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source) + { + _UMMapGuard __guard(__source); + _Base::merge(__source._M_base()); + } + + template + void + merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source) + { merge(__source); } #endif // C++17 + using _Base::hash_function; + using _Base::key_eq; + iterator find(const key_type& __key) { return { _Base::find(__key), this }; } @@ -567,6 +702,11 @@ namespace __debug { return { _Base::find(__k), this }; } #endif + using _Base::count; +#if __cplusplus > 201703L + using _Base::contains; +#endif + std::pair equal_range(const key_type& __key) { @@ -605,6 +745,9 @@ namespace __debug } #endif + using _Base::operator[]; + using _Base::at; + size_type erase(const key_type& __key) { @@ -651,6 +794,9 @@ namespace __debug return { __next, this }; } + using _Base::rehash; + using _Base::reserve; + _Base& _M_base() noexcept { return *this; } @@ -843,7 +989,12 @@ namespace __debug typedef typename _Base::key_type key_type; typedef typename _Base::value_type value_type; + typedef typename _Base::mapped_type mapped_type; + typedef typename _Base::pointer pointer; + typedef typename _Base::const_pointer const_pointer; + typedef typename _Base::reference reference; + typedef typename _Base::const_reference const_reference; typedef __gnu_debug::_Safe_iterator< _Base_iterator, unordered_multimap> iterator; typedef __gnu_debug::_Safe_iterator< @@ -852,6 +1003,7 @@ namespace __debug _Base_local_iterator, unordered_multimap> local_iterator; typedef __gnu_debug::_Safe_local_iterator< _Base_const_local_iterator, unordered_multimap> const_local_iterator; + typedef typename _Base::difference_type difference_type; unordered_multimap() = default; @@ -952,6 +1104,11 @@ namespace __debug return *this; } + using _Base::get_allocator; + using _Base::empty; + using _Base::size; + using _Base::max_size; + void swap(unordered_multimap& __x) noexcept( noexcept(declval<_Base&>().swap(__x)) ) @@ -1034,6 +1191,10 @@ namespace __debug return { _Base::cend(__b), this }; } + using _Base::bucket_count; + using _Base::max_bucket_count; + using _Base::bucket; + size_type bucket_size(size_type __b) const { @@ -1192,9 +1353,130 @@ namespace __debug return { _Base::insert(__hint.base(), std::move(__nh)), this }; } - using _Base::merge; + private: + template + struct _UMMapGuard + { + _UMMapGuard(_Source& __source) noexcept + : _M_source(__source), _M_size(__source.size()) + { } + + _UMMapGuard(const _UMMapGuard&) = delete; + + ~_UMMapGuard() + { + const size_type __size = _M_source.size(); + if (__size == _M_size) + return; + + __try + { + if (__size == 0) + _M_source._M_invalidate_all(); + else + { + // An exception was raised, find out which iterator to + // invalidate. + auto __pred = + [this](auto __it) + { + auto __rng = + _M_source._M_base().equal_range(__it->first); + for (auto __rit = __rng.first; + __rit != __rng.second; ++__rit) + { + if (__it == __rit) + return false; + } + + return true; + }; + + _M_source._M_invalidate_if(__pred); + _M_source._M_invalidate_local_if(__pred); + } + } + __catch(...) + { + _M_source._M_invalidate_all(); + } + } + + _Source& _M_source; + const size_type _M_size; + }; + + public: + template + void + merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source) + { + _UMMapGuard __guard(__source); + _Base::merge(__source._M_base()); + } + + template + void + merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source) + { merge(__source); } + + private: + template + struct _UMapGuard + { + _UMapGuard(_Source& __source) noexcept + : _M_source(__source), _M_size(__source.size()) + { } + + _UMapGuard(const _UMapGuard&) = delete; + + ~_UMapGuard() + { + const size_type __size = _M_source.size(); + if (__size == _M_size) + return; + + __try + { + if (__size == 0) + _M_source._M_invalidate_all(); + else + { + auto __pred = + [this](auto __it) + { return _M_source.count(__it->second) == 0; }; + _M_source._M_invalidate_if(__pred); + _M_source._M_invalidate_local_if(__pred); + } + } + __catch(...) + { + _M_source._M_invalidate_all(); + } + } + + _Source& _M_source; + const size_type _M_size; + }; + + public: + template + void + merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source) + { + _UMapGuard __guard(__source); + _Base::merge(__source._M_base()); + } + + template + void + merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source) + { merge(__source); } #endif // C++17 + using _Base::hash_function; + using _Base::key_eq; + iterator find(const key_type& __key) { return { _Base::find(__key), this }; } @@ -1221,6 +1503,11 @@ namespace __debug { return { _Base::find(__k), this }; } #endif + using _Base::count; +#if __cplusplus > 201703L + using _Base::contains; +#endif + std::pair equal_range(const key_type& __key) { @@ -1309,6 +1596,9 @@ namespace __debug return { __next, this }; } + using _Base::rehash; + using _Base::reserve; + _Base& _M_base() noexcept { return *this; } diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set index c25910946b7..6bc4b050439 100644 --- a/libstdc++-v3/include/debug/unordered_set +++ b/libstdc++-v3/include/debug/unordered_set @@ -88,6 +88,7 @@ namespace __debug public: typedef typename _Base::size_type size_type; + typedef typename _Base::difference_type difference_type; typedef typename _Base::hasher hasher; typedef typename _Base::key_equal key_equal; typedef typename _Base::allocator_type allocator_type; @@ -95,6 +96,10 @@ namespace __debug typedef typename _Base::key_type key_type; typedef typename _Base::value_type value_type; + typedef typename _Base::pointer pointer; + typedef typename _Base::const_pointer const_pointer; + typedef typename _Base::reference reference; + typedef typename _Base::const_reference const_reference; typedef __gnu_debug::_Safe_iterator< _Base_iterator, unordered_set> iterator; typedef __gnu_debug::_Safe_iterator< @@ -203,6 +208,11 @@ namespace __debug return *this; } + using _Base::get_allocator; + using _Base::empty; + using _Base::size; + using _Base::max_size; + void swap(unordered_set& __x) noexcept( noexcept(declval<_Base&>().swap(__x)) ) @@ -285,6 +295,9 @@ namespace __debug return { _Base::cend(__b), this }; } + using _Base::bucket_count; + using _Base::max_bucket_count; + size_type bucket_size(size_type __b) const { @@ -292,6 +305,9 @@ namespace __debug return _Base::bucket_size(__b); } + using _Base::bucket; + using _Base::load_factor; + float max_load_factor() const noexcept { return _Base::max_load_factor(); } @@ -303,6 +319,9 @@ namespace __debug _Base::max_load_factor(__f); } + using _Base::rehash; + using _Base::reserve; + template std::pair emplace(_Args&&... __args) @@ -423,9 +442,125 @@ namespace __debug return { _Base::insert(__hint.base(), std::move(__nh)), this }; } - using _Base::merge; + private: + template + struct _USetGuard + { + _USetGuard(_Source& __source) noexcept + : _M_source(__source), _M_size(__source.size()) + { } + + _USetGuard(const _USetGuard&) = delete; + + ~_USetGuard() + { + const size_type __size = _M_source.size(); + if (__size == _M_size) + return; + + __try + { + if (__size == 0) + _M_source._M_invalidate_all(); + else + { + auto __pred = [this](auto __it) + { return _M_source.count(*__it) == 0; }; + _M_source._M_invalidate_if(__pred); + _M_source._M_invalidate_local_if(__pred); + } + } + __catch(...) + { + _M_source._M_invalidate_all(); + } + } + + _Source& _M_source; + const size_type _M_size; + }; + + public: + template + void + merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source) + { + _USetGuard __guard(__source); + _Base::merge(__source._M_base()); + } + + template + void + merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source) + { merge(__source); } + + private: + template + struct _UMSetGuard + { + _UMSetGuard(_Source& __source) noexcept + : _M_source(__source), _M_size(__source.size()) + { } + + _UMSetGuard(const _UMSetGuard&) = delete; + + ~_UMSetGuard() + { + const size_type __size = _M_source.size(); + if (__size == _M_size) + return; + + __try + { + if (__size == 0) + _M_source._M_invalidate_all(); + else + { + auto __pred = + [this](auto __it) + { + auto __rng = _M_source._M_base().equal_range(*__it); + for (auto __rit = __rng.first; + __rit != __rng.second; ++__rit) + { + if (__it == __rit) + return false; + } + + return true; + }; + _M_source._M_invalidate_if(__pred); + _M_source._M_invalidate_local_if(__pred); + } + } + __catch(...) + { + _M_source._M_invalidate_all(); + } + } + + _Source& _M_source; + const size_type _M_size; + }; + + public: + template + void + merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source) + { + _UMSetGuard __guard(__source); + _Base::merge(__source._M_base()); + } + + template + void + merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source) + { merge(__source); } #endif // C++17 + using _Base::hash_function; + using _Base::key_eq; + iterator find(const key_type& __key) { return { _Base::find(__key), this }; } @@ -452,6 +587,12 @@ namespace __debug { return { _Base::find(__k), this }; } #endif + using _Base::count; + +#if __cplusplus > 201703L + using _Base::contains; +#endif + std::pair equal_range(const key_type& __key) { @@ -707,6 +848,7 @@ namespace __debug public: typedef typename _Base::size_type size_type; + typedef typename _Base::difference_type difference_type; typedef typename _Base::hasher hasher; typedef typename _Base::key_equal key_equal; typedef typename _Base::allocator_type allocator_type; @@ -714,6 +856,10 @@ namespace __debug typedef typename _Base::key_type key_type; typedef typename _Base::value_type value_type; + typedef typename _Base::pointer pointer; + typedef typename _Base::const_pointer const_pointer; + typedef typename _Base::reference reference; + typedef typename _Base::const_reference const_reference; typedef __gnu_debug::_Safe_iterator< _Base_iterator, unordered_multiset> iterator; typedef __gnu_debug::_Safe_iterator< @@ -822,6 +968,11 @@ namespace __debug return *this; } + using _Base::get_allocator; + using _Base::empty; + using _Base::size; + using _Base::max_size; + void swap(unordered_multiset& __x) noexcept( noexcept(declval<_Base&>().swap(__x)) ) @@ -904,6 +1055,9 @@ namespace __debug return { _Base::cend(__b), this }; } + using _Base::bucket_count; + using _Base::max_bucket_count; + size_type bucket_size(size_type __b) const { @@ -911,6 +1065,9 @@ namespace __debug return _Base::bucket_size(__b); } + using _Base::bucket; + using _Base::load_factor; + float max_load_factor() const noexcept { return _Base::max_load_factor(); } @@ -922,6 +1079,9 @@ namespace __debug _Base::max_load_factor(__f); } + using _Base::rehash; + using _Base::reserve; + template iterator emplace(_Args&&... __args) @@ -1037,9 +1197,125 @@ namespace __debug return { _Base::insert(__hint.base(), std::move(__nh)), this }; } - using _Base::merge; + private: + template + struct _UMSetGuard + { + _UMSetGuard(_Source& __source) noexcept + : _M_source(__source), _M_size(__source.size()) + { } + + _UMSetGuard(const _UMSetGuard&) = delete; + + ~_UMSetGuard() + { + const size_type __size = _M_source.size(); + if (__size == _M_size) + return; + + __try + { + if (__size == 0) + _M_source._M_invalidate_all(); + else + { + auto __pred = + [this](auto __it) + { + auto __rng = _M_source._M_base().equal_range(*__it); + for (auto __rit = __rng.first; + __rit != __rng.second; ++__rit) + { + if (__it == __rit) + return false; + } + + return true; + }; + _M_source._M_invalidate_if(__pred); + _M_source._M_invalidate_local_if(__pred); + } + } + __catch(...) + { + _M_source._M_invalidate_all(); + } + } + + _Source& _M_source; + const size_type _M_size; + }; + + public: + template + void + merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source) + { + _UMSetGuard __guard(__source); + _Base::merge(__source._M_base()); + } + + template + void + merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source) + { merge(__source); } + + private: + template + struct _USetGuard + { + _USetGuard(_Source& __source) noexcept + : _M_source(__source), _M_size(__source.size()) + { } + + _USetGuard(const _USetGuard&) = delete; + + ~_USetGuard() + { + const size_type __size = _M_source.size(); + if (__size == _M_size) + return; + + __try + { + if (__size == 0) + _M_source._M_invalidate_all(); + else + { + auto __pred = [this](auto __it) + { return _M_source.count(*__it) == 0; }; + _M_source._M_invalidate_if(__pred); + _M_source._M_invalidate_local_if(__pred); + } + } + __catch(...) + { + _M_source._M_invalidate_all(); + } + } + + _Source& _M_source; + const size_type _M_size; + }; + + public: + template + void + merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source) + { + _USetGuard __guard(__source); + _Base::merge(__source._M_base()); + } + + template + void + merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source) + { merge(__source); } #endif // C++17 + using _Base::hash_function; + using _Base::key_eq; + iterator find(const key_type& __key) { return { _Base::find(__key), this }; } @@ -1066,6 +1342,12 @@ namespace __debug { return { _Base::find(__k), this }; } #endif + using _Base::count; + +#if __cplusplus > 201703L + using _Base::contains; +#endif + std::pair equal_range(const key_type& __key) { diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge1_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge1_neg.cc new file mode 100644 index 00000000000..69e8a6741a8 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge1_neg.cc @@ -0,0 +1,31 @@ +// { dg-do run { target c++17 xfail *-*-* } } +// { dg-require-debug-mode "" } + +#include +#include +#include + +using test_type = std::unordered_map; + +void +test01() +{ + test_type c0{ { 1, 1 }, { 2, 2 }, { 3, 3 }, { 5, 5 }, { 6, 6 } }; + test_type c1{ { 1, 1 }, { 2, 2 }, { 3, 3 }, { 4, 4 } }; + + auto it2 = c1.find(2); + auto it4 = c1.find(4); + VERIFY( it2->second == 2 ); + VERIFY( it4->second == 4 ); + + c0.merge(c1); + + VERIFY( it2->second == 2 ); + VERIFY( it4 != it2 ); // Invalid iterator. +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge2_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge2_neg.cc new file mode 100644 index 00000000000..543cd960a5e --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge2_neg.cc @@ -0,0 +1,32 @@ +// { dg-do run { target c++17 xfail *-*-* } } +// { dg-require-debug-mode "" } + +#include +#include +#include + +using test_type = std::unordered_map; + +void +test01() +{ + test_type c0{ { 1, 1 }, { 2, 2 }, { 3, 3 }, { 5, 5 }, { 6, 6 } }; + test_type c1{ { 1, 1 }, { 2, 2 }, { 3, 3 }, { 4, 4 } }; + + auto it2 = c1.find(2); + auto it4 = c1.find(4); + VERIFY( it2->second == 2 ); + VERIFY( it4->second == 4 ); + + c0.merge(std::move(c1)); + + VERIFY( it2->second == 2 ); + VERIFY( it2 != it4 ); // Invalid iterator. +} + + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge3_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge3_neg.cc new file mode 100644 index 00000000000..8e234799cbf --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge3_neg.cc @@ -0,0 +1,42 @@ +// { dg-do run { target c++17 xfail *-*-* } } +// { dg-require-debug-mode "" } + +#include +#include +#include + +using test_type = std::unordered_map; + +void +test01() +{ + test_type c0 + { + { 1, 1 }, { 2, 2 }, { 3, 3 }, + { 5, 5 }, { 6, 6 }, { 7, 7 } + }; + std::unordered_multimap c1 + { + { 1, 1 }, { 1, 1 }, { 2, 2 }, { 2, 2 }, + { 3, 3 }, { 3, 3 }, { 4, 4 }, { 4, 4 }, + { 5, 5 } + }; + + auto it1 = c1.find(1); + auto it41 = c1.find(4); + auto it42 = it41; + ++it42; + VERIFY( it42->second == 4 ); + + c0.merge(c1); + + VERIFY( it1->second == 1 ); + VERIFY( c1.count(4) == 1 ); + VERIFY( it41 != it42 ); // Invalid iterator. +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge4_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge4_neg.cc new file mode 100644 index 00000000000..3c9c8268f8c --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge4_neg.cc @@ -0,0 +1,42 @@ +// { dg-do run { target c++17 xfail *-*-* } } +// { dg-require-debug-mode "" } + +#include +#include +#include + +using test_type = std::unordered_map; + +void +test01() +{ + test_type c0 + { + { 1, 1 }, { 2, 2 }, { 3, 3 }, + { 5, 5 }, { 6, 6 }, { 7, 7 } + }; + std::unordered_multimap c1 + { + { 1, 1 }, { 1, 1 }, { 2, 2 }, { 2, 2 }, + { 3, 3 }, { 3, 3 }, { 4, 4 }, { 4, 4 }, + { 5, 5 } + }; + + auto it1 = c1.find(1); + auto it41 = c1.find(4); + auto it42 = it41; + ++it42; + VERIFY( it42->second == 4 ); + + c0.merge(std::move(c1)); + + VERIFY( it1->second == 1 ); + VERIFY( c1.count(4) == 1 ); + VERIFY( it41 != it42 ); // Invalid iterator. +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge1_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge1_neg.cc new file mode 100644 index 00000000000..25b3b9e0c75 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge1_neg.cc @@ -0,0 +1,32 @@ +// { dg-do run { target c++17 xfail *-*-* } } +// { dg-require-debug-mode "" } + +#include +#include +#include + +using test_type = std::unordered_multimap; + +void +test01() +{ + test_type c0 + { + { 1, 1 }, { 1, 1 }, { 2, 2 }, + { 2, 2 }, { 3, 3 }, { 3, 3 } + }; + test_type c1 = c0; + + auto it = c1.find(2); + VERIFY( it->second == 2 ); + + c0.merge(c1); + + VERIFY( it != c1.end() ); // Invalid iterator. +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge2_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge2_neg.cc new file mode 100644 index 00000000000..8d28d83b972 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge2_neg.cc @@ -0,0 +1,32 @@ +// { dg-do run { target c++17 xfail *-*-* } } +// { dg-require-debug-mode "" } + +#include +#include +#include + +using test_type = std::unordered_multimap; + +void +test01() +{ + test_type c0 + { + { 1, 1 }, { 1, 1 }, { 2, 2 }, + { 2, 2 }, { 3, 3 }, { 3, 3 } + }; + test_type c1 = c0; + + auto it = c1.find(2); + VERIFY( it->second == 2 ); + + c0.merge(std::move(c1)); + + VERIFY( it != c1.end() ); // Invalid iterator. +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge3_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge3_neg.cc new file mode 100644 index 00000000000..5db91a27ca0 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge3_neg.cc @@ -0,0 +1,32 @@ +// { dg-do run { target c++17 xfail *-*-* } } +// { dg-require-debug-mode "" } + +#include +#include +#include + +using test_type = std::unordered_multimap; + +void +test01() +{ + test_type c0 + { + { 1, 1 }, { 1, 1 }, { 2, 2 }, + { 2, 2 }, { 3, 3 }, { 3, 3 } + }; + std::unordered_map c1{ { 1, 1 }, { 2, 2 }, { 3, 3 } }; + + auto it = c1.find(2); + VERIFY( it->second == 2 ); + + c0.merge(c1); + + VERIFY( it != c1.end() ); // Invalid iterator. +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge4_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge4_neg.cc new file mode 100644 index 00000000000..a1636703569 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge4_neg.cc @@ -0,0 +1,32 @@ +// { dg-do run { target c++17 xfail *-*-* } } +// { dg-require-debug-mode "" } + +#include +#include +#include + +using test_type = std::unordered_multimap; + +void +test01() +{ + test_type c0 + { + { 1, 1 }, { 1, 1 }, { 2, 2 }, + { 2, 2 }, { 3, 3 }, { 3, 3 } + }; + std::unordered_map c1{ { 1, 1 }, { 2, 2 }, { 3, 3 } }; + + auto it = c1.find(2); + VERIFY( it->second == 2 ); + + c0.merge(std::move(c1)); + + VERIFY( it != c1.end() ); // Invalid iterator. +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge1_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge1_neg.cc new file mode 100644 index 00000000000..bce8da7f6cf --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge1_neg.cc @@ -0,0 +1,28 @@ +// { dg-do run { target c++17 xfail *-*-* } } +// { dg-require-debug-mode "" } + +#include +#include +#include + +using test_type = std::unordered_multiset; + +void +test01() +{ + test_type c0{ 1, 1, 2, 2, 3, 3 }; + test_type c1 = c0; + + auto it = c1.find(2); + VERIFY( *it == 2 ); + + c0.merge(c1); + + VERIFY( it != c1.end() ); // Invalid iterator. +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge2_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge2_neg.cc new file mode 100644 index 00000000000..72317a32e89 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge2_neg.cc @@ -0,0 +1,28 @@ +// { dg-do run { target c++17 xfail *-*-* } } +// { dg-require-debug-mode "" } + +#include +#include +#include + +using test_type = std::unordered_multiset; + +void +test01() +{ + test_type c0{ 1, 1, 2, 2, 3, 3 }; + test_type c1 = c0; + + auto it = c1.find(2); + VERIFY( *it == 2 ); + + c0.merge(std::move(c1)); + + VERIFY( it != c1.end() ); // Invalid iterator. +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge3_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge3_neg.cc new file mode 100644 index 00000000000..1b1f4870dd1 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge3_neg.cc @@ -0,0 +1,28 @@ +// { dg-do run { target c++17 xfail *-*-* } } +// { dg-require-debug-mode "" } + +#include +#include +#include + +using test_type = std::unordered_multiset; + +void +test01() +{ + test_type c0{ 1, 1, 2, 2, 3, 3 }; + std::unordered_set c1{ 1, 2, 3 }; + + auto it = c1.find(2); + VERIFY( *it == 2 ); + + c0.merge(c1); + + VERIFY( it != c1.end() ); // Invalid iterator. +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge4_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge4_neg.cc new file mode 100644 index 00000000000..5005cf8468a --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge4_neg.cc @@ -0,0 +1,28 @@ +// { dg-do run { target c++17 xfail *-*-* } } +// { dg-require-debug-mode "" } + +#include +#include +#include + +using test_type = std::unordered_multiset; + +void +test01() +{ + test_type c0{ 1, 1, 2, 2, 3, 3 }; + std::unordered_set c1{ 1, 2, 3 }; + + auto it = c1.find(2); + VERIFY( *it == 2 ); + + c0.merge(std::move(c1)); + + VERIFY( it != c1.end() ); // Invalid iterator. +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge1_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge1_neg.cc new file mode 100644 index 00000000000..8a2bc6e468f --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge1_neg.cc @@ -0,0 +1,31 @@ +// { dg-do run { target c++17 xfail *-*-* } } +// { dg-require-debug-mode "" } + +#include +#include +#include + +using test_type = std::unordered_set; + +void +test01() +{ + test_type c0{ 1, 2, 3, 5, 6 }; + test_type c1{ 1, 2, 3, 4 }; + + auto it2 = c1.find(2); + auto it4 = c1.find(4); + VERIFY( *it2 == 2 ); + VERIFY( *it4 == 4 ); + + c0.merge(c1); + + VERIFY( *it2 == 2 ); + VERIFY( it2 != it4 ); // Invalid iterator. +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge2_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge2_neg.cc new file mode 100644 index 00000000000..3ac96540770 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge2_neg.cc @@ -0,0 +1,31 @@ +// { dg-do run { target c++17 xfail *-*-* } } +// { dg-require-debug-mode "" } + +#include +#include +#include + +using test_type = std::unordered_set; + +void +test01() +{ + test_type c0{ 1, 2, 3, 5, 6 }; + test_type c1{ 1, 2, 3, 4 }; + + auto it2 = c1.find(2); + auto it4 = c1.find(4); + VERIFY( *it2 == 2 ); + VERIFY( *it4 == 4 ); + + c0.merge(std::move(c1)); + + VERIFY( *it2 == 2 ); + VERIFY( it2 != it4 ); // Invalid iterator. +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge3_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge3_neg.cc new file mode 100644 index 00000000000..7e93b55d507 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge3_neg.cc @@ -0,0 +1,33 @@ +// { dg-do run { target c++17 xfail *-*-* } } +// { dg-require-debug-mode "" } + +#include +#include +#include + +using test_type = std::unordered_set; + +void +test01() +{ + test_type c0{ 1, 2, 3, 5, 6, 7 }; + std::unordered_multiset c1{ 1, 1, 2, 2, 3, 3, 4, 4, 5 }; + + auto it1 = c1.find(1); + auto it41 = c1.find(4); + auto it42 = it41; + ++it42; + VERIFY( *it42 == 4 ); + + c0.merge(c1); + + VERIFY( *it1 == 1 ); + VERIFY( c1.count(4) == 1 ); + VERIFY( it41 != it42 ); // Invalid iterator. +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge4_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge4_neg.cc new file mode 100644 index 00000000000..14c8ff63b05 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge4_neg.cc @@ -0,0 +1,33 @@ +// { dg-do run { target c++17 xfail *-*-* } } +// { dg-require-debug-mode "" } + +#include +#include +#include + +using test_type = std::unordered_set; + +void +test01() +{ + test_type c0{ 1, 2, 3, 5, 6, 7 }; + std::unordered_multiset c1{ 1, 1, 2, 2, 3, 3, 4, 4, 5 }; + + auto it1 = c1.find(1); + auto it41 = c1.find(4); + auto it42 = it41; + ++it42; + VERIFY( *it42 == 4 ); + + c0.merge(std::move(c1)); + + VERIFY( *it1 == 1 ); + VERIFY( c1.count(4) == 1 ); + VERIFY( it41 != it42 ); // Invalid iterator. +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/util/testsuite_abi.h b/libstdc++-v3/testsuite/util/testsuite_abi.h index 667c46c33d3..4a0cf64f6fb 100644 --- a/libstdc++-v3/testsuite/util/testsuite_abi.h +++ b/libstdc++-v3/testsuite/util/testsuite_abi.h @@ -24,7 +24,11 @@ #include #if __cplusplus >= 201103L # include +# ifdef _GLIBCXX_DEBUG +namespace unord = std::_GLIBCXX_STD_C; +# else namespace unord = std; +# endif #else # include namespace unord = std::tr1; --------------D07B317F03D3724DFE79F89D--