From patchwork Thu Feb 2 18:20:26 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: 64188 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 7C6FD3896C3A for ; Thu, 2 Feb 2023 18:21:21 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 7C6FD3896C3A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1675362081; bh=UkJCWmz27y1O2R27kbj7bIdUlDi/fi81IbcKojKL5hA=; h=Date:To:Cc:Subject:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=owlIC2+39I9pwBCDX6u5nsmRrlmDAIVU//6j9BcGQDWEY0RIkNB2ZXhYQ+QVPfgPq D7dzAeriZn29bRG151nKmIjUQ1OjErRA4WYQwzB7huRjLOGpLhDNa0amg6DlOxQR2K VCXosS647PFDXgn3d98eYRytTUH5aYzirQ82KVzQ= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-ed1-x52d.google.com (mail-ed1-x52d.google.com [IPv6:2a00:1450:4864:20::52d]) by sourceware.org (Postfix) with ESMTPS id 2A89F3884526; Thu, 2 Feb 2023 18:20:47 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 2A89F3884526 Received: by mail-ed1-x52d.google.com with SMTP id u21so2942839edv.3; Thu, 02 Feb 2023 10:20:47 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=subject:from:cc:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=UkJCWmz27y1O2R27kbj7bIdUlDi/fi81IbcKojKL5hA=; b=leKdDxMZ43da8xZpDle/N8pkRPPuyeGq0kZ7XulLNW5i282rBOJsy67e6K+fj1TEng 8bMtP8+qe+ctr4ckY6aEEVTiKvsBd0TwMh5pt7S6MKkjT2D8p1QsUr37n44ungDufR22 MA6DfTX2+0Z0BueGs8bRRtTtsgsKdQij+LK7CrS3I687vbeAW2W5IJXJNNpi1LWYJlIG LhWCqcxZZnzMgf90VEOpbHQyMvWxNn0v712g7EbtPEvcxdqMC0MLht7m2jo65Sa5POyn 3t2jxKt0SsJbQtoUCFm80LvzcVLxlvWx25Bxb15DwiLE3a66t/WrS++AxYx4eAPcImfS ADXw== X-Gm-Message-State: AO0yUKUEovO3cwoIiNlV4N05As3Up8SL5CeTfmty/MN2M0ysCgiESP/+ XBYVMVNoR8UOauIRub6P49pT2ZFLXV4= X-Google-Smtp-Source: AK7set+u03D9bwnPqngJ9Gg96UerH0bPgYMqjGxkh3Obc79XwhIZbpBzKr/Y96BeZQj+K+FQ2X9l+Q== X-Received: by 2002:a50:950d:0:b0:47e:eaae:9a5b with SMTP id u13-20020a50950d000000b0047eeaae9a5bmr7662331eda.42.1675362045273; Thu, 02 Feb 2023 10:20:45 -0800 (PST) Received: from [10.11.1.53] ([109.190.253.11]) by smtp.googlemail.com with ESMTPSA id f21-20020a056402195500b0049be07c9ff5sm56273edz.4.2023.02.02.10.20.43 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 02 Feb 2023 10:20:44 -0800 (PST) Message-ID: Date: Thu, 2 Feb 2023 19:20:26 +0100 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.4.2 Content-Language: fr To: "libstdc++@gcc.gnu.org" Cc: gcc-patches Subject: [PATCH] libstdc++: Limit allocations in _Rb_tree X-Spam-Status: No, score=-6.4 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, KAM_SHORT, RCVD_IN_ABUSEAT, RCVD_IN_BARRACUDACENTRAL, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP 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.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?= Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" This is PR 96088 but this time for _Rb_tree based containers. I guess it won't go in for the moment but I wanted to submit it already because of the changes I had to do in stl_functions.h. It sounds like missing parts for C++11 move-semantic. I still need to run all tests to see if they can have side effects.      libstdc++: [_Rb_tree] Limit allocation on iterator insertion [PR 96088]     Detect when invoking the comparer require an allocation and in this case     create a temporary instance that will be moved to storage location if the     insertion eventually takes place. Avoid to allocate a node otherwise.     libstdc++-v3/ChangeLog:             PR libstdc++/96088             * include/bits/stl_function.h             (std::less<>::operator()): Add noexcept qualification.             (std::greater::operator()): Likewise. (std::_Identity<>::operator<_Tp2>(_Tp2&&)): New perfect forwarding operator. (std::_Select1st<>::operator<_Pair2>(_Pair2&&)): New move operator.             * include/bits/stl_tree.h (_Rb_tree<>::_ConvertToValueType<>): New helper type.             (_Rb_tree<>::_M_get_insert_unique_pos_tr): New.             (_Rb_tree<>::_S_forward_key): New.             (_Rb_tree<>::_M_emplace_unique_kv): New.             (_Rb_tree<>::_M_emplace_unique_aux): New, use latter.             (_Rb_tree<>::_M_emplace_unique): New, use latter.             * testsuite/23_containers/map/96088.cc: New test case.             * testsuite/23_containers/multimap/96088.cc: New test case.             * testsuite/23_containers/multiset/96088.cc: New test case.             * testsuite/23_containers/set/96088.cc: New test case. Ok to commit ? François diff --git a/libstdc++-v3/include/bits/stl_function.h b/libstdc++-v3/include/bits/stl_function.h index fa03f32b1b8..5e04c82629b 100644 --- a/libstdc++-v3/include/bits/stl_function.h +++ b/libstdc++-v3/include/bits/stl_function.h @@ -395,6 +395,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _GLIBCXX14_CONSTEXPR bool operator()(const _Tp& __x, const _Tp& __y) const + _GLIBCXX_NOEXCEPT_IF( noexcept(__x > __y) ) { return __x > __y; } }; @@ -405,6 +406,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _GLIBCXX14_CONSTEXPR bool operator()(const _Tp& __x, const _Tp& __y) const + _GLIBCXX_NOEXCEPT_IF( noexcept(__x < __y) ) { return __x < __y; } }; @@ -1165,6 +1167,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION const _Tp& operator()(const _Tp& __x) const { return __x; } + +#if __cplusplus >= 201103L + template + _Tp2&& + operator()(_Tp2&& __x) const noexcept + { return std::forward<_Tp2>(__x); } +#endif }; // Partial specialization, avoids confusing errors in e.g. std::set. @@ -1192,6 +1201,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION const typename _Pair2::first_type& operator()(const _Pair2& __x) const { return __x.first; } + + template + typename _Pair2::first_type&& + operator()(_Pair2&& __x) const + { return std::move(__x.first); } #endif }; diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index 3c331fbc952..8096ba97f18 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -534,6 +534,42 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Rb_tree& _M_t; }; +#if __cplusplus >= 201103L + template + struct _ConvertToValueType; + + template + struct _ConvertToValueType, _Value> + { + template + constexpr _Kt&& + operator()(_Kt&& __k) const noexcept + { return std::forward<_Kt>(__k); } + }; + + template + struct _ConvertToValueType, _Value> + { + constexpr _Value&& + operator()(_Value&& __x) const noexcept + { return std::move(__x); } + + constexpr const _Value& + operator()(const _Value& __x) const noexcept + { return __x; } + + template + constexpr std::pair<_Kt, _Vt>&& + operator()(std::pair<_Kt, _Vt>&& __x) const noexcept + { return std::move(__x); } + + template + constexpr const std::pair<_Kt, _Vt>& + operator()(const std::pair<_Kt, _Vt>& __x) const noexcept + { return __x; } + }; +#endif // C++11 + public: typedef _Key key_type; typedef _Val value_type; @@ -830,6 +866,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION pair<_Base_ptr, _Base_ptr> _M_get_insert_unique_pos(const key_type& __k); +#if __cplusplus >= 201103L + template + pair<_Base_ptr, _Base_ptr> + _M_get_insert_unique_pos_tr(const _Kt& __k); +#endif + pair<_Base_ptr, _Base_ptr> _M_get_insert_equal_pos(const key_type& __k); @@ -1075,6 +1117,45 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an); } + template + static __conditional_t< + __and_<__is_nothrow_invocable<_Compare&, + const key_type&, const key_type&>, + __not_<__is_nothrow_invocable<_Compare&, + _Kt, const key_type&>>>::value, + key_type, _Kt&&> + _S_forward_key(_Kt&& __k) + { return std::forward<_Kt>(__k); } + + static const key_type& + _S_forward_key(const key_type& __k) + { return __k; } + + static key_type&& + _S_forward_key(key_type&& __k) + { return std::move(__k); } + + template + std::pair + _M_emplace_unique_kv(_Kt&&, _Arg&&); + + template + pair + _M_emplace_unique_aux(_Arg&& __arg) + { + return _M_emplace_unique_kv( + _S_forward_key(_KeyOfValue{}(std::forward<_Arg>(__arg))), + std::forward<_Arg>(__arg)); + } + + template + pair + _M_emplace_unique(_Arg&& __arg) + { + using __to_value = _ConvertToValueType<_KeyOfValue, value_type>; + return _M_emplace_unique_aux(__to_value{}(std::forward<_Arg>(__arg))); + } + template pair _M_emplace_unique(_Args&&... __args); @@ -1670,6 +1751,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Rb_tree& _M_t; _Link_type _M_node; }; + + template + static _Auto_node + _S_build_node(_Rb_tree& __t, _Kt&& __k, _Arg&& __arg, _SelectFst) + { + return + { __t, std::forward<_Kt>(__k), std::forward<_Arg>(__arg).second }; + } + + template + static _Auto_node + _S_build_node(_Rb_tree& __t, _Kt&& __k, _Arg&&, std::_Identity<_Val>) + { return { __t, std::forward<_Kt>(__k) }; } #endif // C++11 }; @@ -2131,6 +2225,39 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return _Res(__j._M_node, 0); } +#if __cplusplus >= 201103L + template + template + auto + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_get_insert_unique_pos_tr(const _Kt& __k) + -> pair<_Base_ptr, _Base_ptr> + { + typedef pair<_Base_ptr, _Base_ptr> _Res; + _Link_type __x = _M_begin(); + _Base_ptr __y = _M_end(); + bool __comp = true; + while (__x != 0) + { + __y = __x; + __comp = _M_impl._M_key_compare(__k, _S_key(__x)); + __x = __comp ? _S_left(__x) : _S_right(__x); + } + iterator __j = iterator(__y); + if (__comp) + { + if (__j == begin()) + return _Res(__x, __y); + else + --__j; + } + if (_M_impl._M_key_compare(_S_key(__j._M_node), __k)) + return _Res(__x, __y); + return _Res(__j._M_node, 0); + } +#endif + template pair + template + auto + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_emplace_unique_kv(_Kt&& __k, _Arg&& __arg) + -> pair + { + auto __res = _M_get_insert_unique_pos_tr(__k); + if (__res.second) + { + _Auto_node __z = _S_build_node(*this, + std::forward<_Kt>(__k), std::forward<_Arg>(__arg), _KeyOfValue{}); + return { __z._M_insert(__res), true }; + } + return { iterator(__res.first), false }; + } + template template diff --git a/libstdc++-v3/testsuite/23_containers/map/96088.cc b/libstdc++-v3/testsuite/23_containers/map/96088.cc new file mode 100644 index 00000000000..7dd62129c23 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/map/96088.cc @@ -0,0 +1,252 @@ +// { dg-do run { target c++17 } } +// { dg-require-effective-target std_allocator_new } + +// Copyright (C) 2023 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// libstdc++/96088 + +#include +#include +#include +#include + +#include +#include + +static constexpr std::initializer_list> lst = + { {"long_str_for_dynamic_allocating", 1} }; + +void +test01() +{ + __gnu_test::counter::reset(); + std::map m; + m.insert(lst.begin(), lst.end()); + VERIFY( m.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); + + m.insert(lst.begin(), lst.end()); + VERIFY( m.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); +} + +void +test02() +{ + __gnu_test::counter::reset(); + std::map> m; + m.insert(lst.begin(), lst.end()); + VERIFY( m.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); + + m.insert(lst.begin(), lst.end()); + VERIFY( m.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); +} + +bool +less_string_f(const std::string& lhs, const std::string& rhs) noexcept +{ return lhs < rhs; } + +void +test11() +{ + typedef bool (*less_string_t)(const std::string&, + const std::string&) noexcept; + __gnu_test::counter::reset(); + less_string_t comparer = &less_string_f; + std::map m(comparer); + m.insert(lst.begin(), lst.end()); + VERIFY( m.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); + + m.insert(lst.begin(), lst.end()); + VERIFY( m.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); +} + +bool +less_string_view_f(const std::string_view& lhs, + const std::string_view& rhs) noexcept +{ return lhs < rhs; } + +void +test12() +{ + typedef bool (*less_stringview_t) (const std::string_view&, + const std::string_view&) noexcept; + __gnu_test::counter::reset(); + less_stringview_t comparer = &less_string_view_f; + std::map m(comparer); + m.insert(lst.begin(), lst.end()); + VERIFY( m.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); + + m.insert(lst.begin(), lst.end()); + VERIFY( m.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); +} + +struct less_string_functor +{ + bool + operator()(const std::string& lhs, const std::string& rhs) const noexcept + { return lhs < rhs; } +}; + +void +test21() +{ + __gnu_test::counter::reset(); + std::map m; + m.insert(lst.begin(), lst.end()); + VERIFY( m.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); + + m.insert(lst.begin(), lst.end()); + VERIFY( m.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); +} + +struct less_string_view_noexcept_functor +{ + bool + operator()(const std::string_view& lhs, + const std::string_view& rhs) const noexcept + { return lhs < rhs; } +}; + +void +test22() +{ + __gnu_test::counter::reset(); + std::map m; + m.insert(lst.begin(), lst.end()); + VERIFY( m.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); + + m.insert(lst.begin(), lst.end()); + VERIFY( m.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); +} + +struct less_string_view_functor +{ + bool + operator()(const std::string_view& lhs, + const std::string_view& rhs) const + { return lhs < rhs; } +}; + +void +test23() +{ + __gnu_test::counter::reset(); + std::map m; + m.insert(lst.begin(), lst.end()); + VERIFY( m.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); + + m.insert(lst.begin(), lst.end()); + VERIFY( m.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); +} + +void +test03() +{ + std::vector> v; + v.insert(v.end(), lst.begin(), lst.end()); + + const auto origin = __gnu_test::counter::count(); + + { + __gnu_test::counter::reset(); + std::map> m; + m.insert(v.begin(), v.end()); + VERIFY( m.size() == 1 ); + + // Allocate a node and the std::string (unless COW). + constexpr std::size_t increments = _GLIBCXX_USE_CXX11_ABI ? 2 : 1; + + VERIFY( __gnu_test::counter::count() == origin + increments ); + VERIFY( __gnu_test::counter::get()._M_increments == increments ); + + m.insert(v.begin(), v.end()); + VERIFY( m.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == origin + increments ); + VERIFY( __gnu_test::counter::get()._M_increments == increments ); + } + VERIFY( __gnu_test::counter::count() == origin ); + + { + __gnu_test::counter::reset(); + std::map> m; + m.insert(std::make_move_iterator(v.begin()), + std::make_move_iterator(v.end())); + VERIFY( m.size() == 1 ); + + // Allocate a node. String is moved. + constexpr std::size_t increments = 1; + + VERIFY( __gnu_test::counter::count() == origin + increments ); + VERIFY( __gnu_test::counter::get()._M_increments == increments ); + } +} + +int +main() +{ + test01(); + test02(); + test11(); + test12(); + test21(); + test22(); + test03(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/multimap/96088.cc b/libstdc++-v3/testsuite/23_containers/multimap/96088.cc new file mode 100644 index 00000000000..919c5e59c71 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/multimap/96088.cc @@ -0,0 +1,65 @@ +// { dg-do run { target c++17 } } +// { dg-require-effective-target std_allocator_new } + +// Copyright (C) 2023 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// libstdc++/96088 + +#include +#include +#include + +#include +#include + +static constexpr std::initializer_list> lst = { + {"long_str_for_dynamic_allocating", 1} +}; + +void +test01() +{ + __gnu_test::counter::reset(); + std::multimap> foo; + foo.insert(lst.begin(), lst.end()); + VERIFY( foo.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); +} + +void +test02() +{ + __gnu_test::counter::reset(); + std::multimap foo; + foo.insert(lst.begin(), lst.end()); + VERIFY( foo.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); +} + +int +main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/multiset/96088.cc b/libstdc++-v3/testsuite/23_containers/multiset/96088.cc new file mode 100644 index 00000000000..2cdc08aba51 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/multiset/96088.cc @@ -0,0 +1,64 @@ +// { dg-do run { target c++17 } } +// { dg-require-effective-target std_allocator_new } + +// Copyright (C) 2023 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// libstdc++/96088 + +#include +#include +#include + +#include +#include + +static constexpr std::initializer_list lst = { + "long_str_for_dynamic_allocating" +}; + +void +test01() +{ + __gnu_test::counter::reset(); + std::multiset> foo; + foo.insert(lst.begin(), lst.end()); + VERIFY( foo.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); +} + +void +test02() +{ + __gnu_test::counter::reset(); + std::multiset foo; + foo.insert(lst.begin(), lst.end()); + VERIFY( foo.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); +} + +int +main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/set/96088.cc b/libstdc++-v3/testsuite/23_containers/set/96088.cc new file mode 100644 index 00000000000..3ecb7f81ecc --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/set/96088.cc @@ -0,0 +1,254 @@ +// { dg-do run { target c++17 } } +// { dg-require-effective-target std_allocator_new } + +// Copyright (C) 2023 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// libstdc++/96088 + +#include +#include +#include +#include + +#include +#include + +static constexpr std::initializer_list lst = { + "long_str_for_dynamic_allocating" +}; + +void +test01() +{ + __gnu_test::counter::reset(); + std::set> s; + s.insert(lst.begin(), lst.end()); + VERIFY( s.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); + + s.insert(lst.begin(), lst.end()); + VERIFY( s.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); +} + +void +test02() +{ + __gnu_test::counter::reset(); + std::set> s; + s.insert(lst.begin(), lst.end()); + VERIFY( s.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); + + s.insert(lst.begin(), lst.end()); + VERIFY( s.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); +} + +bool +less_string_f(const std::string& lhs, const std::string& rhs) noexcept +{ return lhs < rhs; } + +void +test11() +{ + typedef bool (*less_string_t)(const std::string&, + const std::string&) noexcept; + __gnu_test::counter::reset(); + less_string_t less = &less_string_f; + std::set s(less); + s.insert(lst.begin(), lst.end()); + VERIFY( s.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); + + s.insert(lst.begin(), lst.end()); + VERIFY( s.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); +} + +bool +less_string_view_f(const std::string_view& lhs, + const std::string_view& rhs) noexcept +{ return lhs < rhs; } + +void +test12() +{ + typedef bool (*less_stringview_t)(const std::string_view&, + const std::string_view&) noexcept; + __gnu_test::counter::reset(); + less_stringview_t less = &less_string_view_f; + std::set s(less); + s.insert(lst.begin(), lst.end()); + VERIFY( s.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); + + s.insert(lst.begin(), lst.end()); + VERIFY( s.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); +} + +struct less_string_functor +{ + bool + operator()(const std::string& lhs, const std::string& rhs) const noexcept + { return lhs < rhs; } +}; + +void +test21() +{ + __gnu_test::counter::reset(); + std::set s; + s.insert(lst.begin(), lst.end()); + VERIFY( s.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); + + s.insert(lst.begin(), lst.end()); + VERIFY( s.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); +} + +struct less_string_view_noexcept_functor +{ + bool + operator()(const std::string_view& lhs, + const std::string_view& rhs) const noexcept + { return lhs < rhs; } +}; + +void +test22() +{ + __gnu_test::counter::reset(); + std::set s; + s.insert(lst.begin(), lst.end()); + VERIFY( s.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); + + s.insert(lst.begin(), lst.end()); + VERIFY( s.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); +} + +struct less_string_view_functor +{ + bool + operator()(const std::string_view& lhs, + const std::string_view& rhs) const + { return lhs < rhs; } +}; + +void +test23() +{ + __gnu_test::counter::reset(); + std::set s; + s.insert(lst.begin(), lst.end()); + VERIFY( s.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); + + s.insert(lst.begin(), lst.end()); + VERIFY( s.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); +} + +void +test03() +{ + std::vector v; + v.insert(v.end(), lst.begin(), lst.end()); + + const auto origin = __gnu_test::counter::count(); + + { + __gnu_test::counter::reset(); + std::set> s; + s.insert(v.begin(), v.end()); + VERIFY( s.size() == 1 ); + + // Allocate a node and the std::string (unless COW). + constexpr std::size_t increments = _GLIBCXX_USE_CXX11_ABI ? 2 : 1; + + VERIFY( __gnu_test::counter::count() == origin + increments ); + VERIFY( __gnu_test::counter::get()._M_increments == increments ); + + s.insert(v.begin(), v.end()); + VERIFY( s.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == origin + increments ); + VERIFY( __gnu_test::counter::get()._M_increments == increments ); + } + VERIFY( __gnu_test::counter::count() == origin ); + + { + __gnu_test::counter::reset(); + std::set> s; + s.insert(std::make_move_iterator(v.begin()), + std::make_move_iterator(v.end())); + VERIFY( s.size() == 1 ); + + // Allocate a node, string is moved. + constexpr std::size_t increments = 1; + + VERIFY( __gnu_test::counter::count() == origin + increments ); + VERIFY( __gnu_test::counter::get()._M_increments == increments ); + } +} + +int +main() +{ + test01(); + test02(); + test11(); + test12(); + test21(); + test22(); + test23(); + test03(); + return 0; +}