From patchwork Wed Feb 22 06:06:23 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: 60348 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:5915:0:0:0:0:0 with SMTP id v21csp409281wrd; Tue, 21 Feb 2023 22:07:52 -0800 (PST) X-Google-Smtp-Source: AK7set/B7FNN6hl8IeOxQTW6mjaQXwMEQ+Kxn6RYdK/95N//iCwozslFy7FlVRePwykmDzwfuLuF X-Received: by 2002:adf:e58f:0:b0:2c5:a07e:4bb6 with SMTP id l15-20020adfe58f000000b002c5a07e4bb6mr5804841wrm.33.1677046072404; Tue, 21 Feb 2023 22:07:52 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1677046072; cv=none; d=google.com; s=arc-20160816; b=CCLJ/iJWcfHTRGCK9m1O2Kg2Rov0cy2ZEnK7C9kltNtDYbT33RkAygp3QxU/dX4QJY Nb+dIT4HZua5V+W1BUk0ExnPCLe4ySHlutirXjbAFvJLHN3e0tXSduoW/BVB5oR8777q x8EcIp4u9DWa8uzvF4ZJzBgP4DD5Wxev0n4rBXR80HaMJaUoPvFEnR4N1FTk6rURGtW9 l4s1nynqPmjDrgA5mIYY3tIzlx7pEkQwqK+mdkiC8caCBHCFwiHEhYRd6nJHsEBYapGT To6tjGs7fu4GvNUS5EM5gqfPGm71wS6tNWl+a2HG5qVKFguGqCT5tk+ljl1C37u0sVtT FLWg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence:in-reply-to :content-language:references:cc:to:subject:user-agent:mime-version :date:message-id:dmarc-filter:delivered-to:dkim-signature :dkim-filter; bh=fmGKT5SCFZK5kd+/vNkgH3lG/OOI7eK7qtvZ9/fwb9U=; b=PEDoYh+KwPPMf+7ABGrtHl5XwxBpFWxB2mWoKmzy/XnETPzTjmRy4rbNxQkyGtzxCG I5gUklFZpbv5gUPQUKfYgxD3n4mvVvoT1aNaVG0i3+T3S+DdQfgOAer7vBT93N2ZH+xc 1iBvTLvpFix3czY6S3oUXttG2W9PueQ+7X5YX+ZC3bhxsVq8h4GyKfkXdgWyIDS/jiqN pcneKW6taql/zL5XtyWG1QurMoyOcQC++tAjazEUaKvZDms+CmOSTfUFsQJoNQrrMKPn bAJBCa/LOf5YfjDdI+cLDvyDPeA5J9LuiC86rwF9otu1tfA4gRUPyzyZrQGgpescDwqP m0sw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=iR7pWUl6; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (server2.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id f1-20020a5d58e1000000b002c5505d1e75si731333wrd.288.2023.02.21.22.07.52 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 21 Feb 2023 22:07:52 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=iR7pWUl6; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 8F8203850409 for ; Wed, 22 Feb 2023 06:07:20 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 8F8203850409 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1677046040; bh=fmGKT5SCFZK5kd+/vNkgH3lG/OOI7eK7qtvZ9/fwb9U=; h=Date:Subject:To:Cc:References:In-Reply-To:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:List-Subscribe: From:Reply-To:From; b=iR7pWUl6RLtytgVn8RF0obeNcRmOcmFte3Gx2nZxtb6EY6pgXFRo2O/cetuLb349P Mvc6Ex2gt4+s7uJ/FHrCFqCDudEwNZ1SyCIfGWP3KTHhoejTRdYHnLxqOx6X0P9QZJ WY8KLXS8QeLQivLCUcoS+pKZUyNaMfZF45+pJIoU= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-ed1-x52c.google.com (mail-ed1-x52c.google.com [IPv6:2a00:1450:4864:20::52c]) by sourceware.org (Postfix) with ESMTPS id 009DA3858D3C; Wed, 22 Feb 2023 06:06:27 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 009DA3858D3C Received: by mail-ed1-x52c.google.com with SMTP id s26so26001665edw.11; Tue, 21 Feb 2023 22:06:27 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=in-reply-to:content-language:references: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=fmGKT5SCFZK5kd+/vNkgH3lG/OOI7eK7qtvZ9/fwb9U=; b=uc4C9RaB4SHwB5bEyN/KE06fXL/HgxEySwxsy6cbeCVpXUzZYhAsDGhfxGUFuRWG/x 8jcxc7/E6XpW12bO44iNhTWMMhNL9SzU9rmMbK9hsHFuQQIAq4PpWM4CJhXhIHvJDMep IUVQpr1m9RqbyKe3atqG5JTdFb9NNhW4RUnUADX309t75aAIWNy0wsUOq5pDwZXMSJI7 iJ2pAcLRsDL+E4gX4lPI7jv7ZyFCV6yVCDhbwzVEOadoxJ2AAMqczHXJd0gvUNJDu7SB gLEscmVMYqc6RfmeoYLQeXXRiXSxEIeRsj2afjhyx/2fqDWj0ToKxOUkGMe+K8AjwxlN ze/A== X-Gm-Message-State: AO0yUKUXW6eFrlVCYmUIUtYOWrDiRVF3bX79KOT3MObnp1Ua7k+BHtcm rHnyCXiE/3wlRwJxrpXeK3WRj2gQ1BY= X-Received: by 2002:a17:906:c309:b0:8aa:bea6:ce8b with SMTP id s9-20020a170906c30900b008aabea6ce8bmr12687174ejz.53.1677045985898; Tue, 21 Feb 2023 22:06:25 -0800 (PST) Received: from [10.22.3.31] ([109.190.253.11]) by smtp.googlemail.com with ESMTPSA id k7-20020a1709065fc700b008dceec0fd4csm2113915ejv.73.2023.02.21.22.06.24 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 21 Feb 2023 22:06:24 -0800 (PST) Message-ID: <7313d189-ae56-4582-6f23-9263dbf57dd3@gmail.com> Date: Wed, 22 Feb 2023 07:06:23 +0100 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.7.1 Subject: [PATCH] libstdc++: Limit allocations in _Rb_tree 1/2 To: "libstdc++@gcc.gnu.org" Cc: gcc-patches References: <43172ea5-6729-02c5-d374-9537fff7eb4c@gmail.com> Content-Language: fr In-Reply-To: <43172ea5-6729-02c5-d374-9537fff7eb4c@gmail.com> X-Spam-Status: No, score=-6.2 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, KAM_NUMSUBJECT, 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+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1758510262500277826?= X-GMAIL-MSGID: =?utf-8?q?1758510262500277826?= Here is eventually a working proposal. Compared to the unordered container approach we need to find out what type is going to be used to call the comparer. Otherwise we might reinstantiate a temporary each time we call the comparer. For example in case of const char* insertion with a less comparer we would create a string_view instance on each comparer call and so each time do a strlen. This code is tricky and do not cover all use cases. For those uncovered cases the default behavior is to create a key_type instance which will be moved to storage if needed. Is there any plan to create a builtin function to get help from the compiler to find out this type ? Something like std::invoke_result but giving also the actual argument types.     libstdc++: [_Rb_tree] Limit allocations on unique insertions [PR 96088]     Detect when invoking the comparer requires an allocation using the noexcept     qualification of the functor. In this case guess the type needed to invoke     the comparer and create a temporary instance used for all comparer invocations.     This temporary instance will be eventually moved to storage location if it is to     insert. Avoid to allocate a node and construct the stored value 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<>::__has_firstargument): Likewise.             (_Rb_tree<>::_S_get_key_type_aux): New helper method, use latter.             (_Rb_tree<>::_S_get_key_type): New helper method, use latter.             (_Rb_tree<>::__key_type_t): New.             (_Rb_tree<>::__is_comparable_lhs): New.             (_Rb_tree<>::__is_comparable_rhs): New.             (_Rb_tree<>::__is_comparable): New, use latters.             (_Rb_tree<>::__is_nothrow_comparable_lhs): New.             (_Rb_tree<>::__is_nothrow_comparable_rhs): New.             (_Rb_tree<>::__is_nothrow_comparable): New, use latters.             (_Rb_tree<>::_S_forward_key): New.             (_Rb_tree<>::_M_get_insert_unique_pos_tr): 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.             (_Rb_tree<>::_Auto_node::_S_build): New.             * 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. François diff --git a/libstdc++-v3/include/bits/stl_function.h b/libstdc++-v3/include/bits/stl_function.h index fa03f32b1b8..f8817e2f6ae 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. @@ -1183,15 +1192,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { return __x.first; } #if __cplusplus >= 201103L + private: template - typename _Pair2::first_type& - operator()(_Pair2& __x) const - { return __x.first; } + struct __1st_type + { using type = typename _Pair2::first_type; }; + + template + struct __1st_type> + { using type = _Tp; }; + template + struct __1st_type> + { using type = const _Tp; }; + + template + struct __1st_type<_Pair2&> + { using type = typename __1st_type<_Pair2>::type&; }; + + public: template - const typename _Pair2::first_type& - operator()(const _Pair2& __x) const - { return __x.first; } + typename __1st_type<_Pair2>::type&& + operator()(_Pair2&& __x) const noexcept + { return std::forward<_Pair2>(__x).first; } #endif }; diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index 3c331fbc952..5dae42a504c 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -534,6 +534,137 @@ _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; } + }; + + template> + struct __has_first_argument + { }; + + template + struct __has_first_argument<_Func, _Kt, + __void_t> + { using type = typename _Func::first_argument_type; }; + + template + using __has_first_argument_t + = typename __has_first_argument<_Func, _Kt>::type; + + template> + static typename _Func::first_argument_type + _S_get_key_type_aux(const _Func&, _Kt&& __kt); + + template + static _Key + _S_get_key_type_aux(...); + +#if __cplusplus >= 201402L + template> + static auto + _S_get_key_type(const _Func&, _Kt&& __kt) + -> decltype(std::forward<_Kt>(__kt)); +#endif + + template + static _Arg + _S_get_key_type(bool (*)(const _Arg&, const _Arg&), _Kt&&); + + template + static auto + _S_get_key_type(const _Func& __func, _Kt&& __kt) + -> decltype(_S_get_key_type_aux(__func, std::forward<_Kt>(__kt))); + + template + using __key_type_t = decltype(_S_get_key_type( + std::declval<_Compare>(), std::declval<_Kt>())); + + template + using __is_comparable_lhs = + __is_invocable<_Compare&, _Kt, const _Key&>; + + template + using __is_comparable_rhs = + __is_invocable<_Compare&, const _Key&, _Kt>; + + template + using __is_comparable = + __and_<__is_comparable_lhs<_Kt>, __is_comparable_rhs<_Kt>>; + + template + using __is_nothrow_comparable_lhs = + __is_nothrow_invocable<_Compare&, _Kt, const _Key&>; + + template + using __is_nothrow_comparable_rhs = + __is_nothrow_invocable<_Compare&, const _Key&, _Kt>; + + template + using __is_nothrow_comparable = + __and_<__is_nothrow_comparable_lhs<_Kt>, + __is_nothrow_comparable_rhs<_Kt>>; + + template + static __enable_if_t< + __and_<__not_, _Key>>, + __is_comparable<__key_type_t<_Kt>>>::value, + __conditional_t< + __and_<__is_nothrow_comparable_lhs, + __not_<__is_nothrow_comparable<__key_type_t<_Kt>>>>::value, + _Key, __key_type_t<_Kt>>> + _S_forward_key(_Kt&& __k) + { return std::forward<_Kt>(__k); } + + template + static __enable_if_t< + __or_, _Key>, + __not_<__is_comparable<__key_type_t<_Kt>>>>::value, + _Key> + _S_forward_key(_Kt&& __k) + { return { std::forward<_Kt>(__k) }; } + + static const _Key& + _S_forward_key(const _Key& __k) + { return __k; } + + static _Key&& + _S_forward_key(_Key&& __k) + { return std::move(__k); } +#endif // C++11 + public: typedef _Key key_type; typedef _Val value_type; @@ -833,6 +964,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION pair<_Base_ptr, _Base_ptr> _M_get_insert_equal_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_hint_unique_pos(const_iterator __pos, const key_type& __k); @@ -1075,6 +1212,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an); } + 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); @@ -1667,6 +1825,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return __it; } + template + static _Auto_node + _S_build(_Rb_tree& __t, + _Kt&& __k, _Arg&& __arg, std::_Select1st<_Value>) + { + return + { __t, std::forward<_Kt>(__k), std::forward<_Arg>(__arg).second }; + } + + template + static _Auto_node + _S_build(_Rb_tree& __t, _Kt&& __k, _Arg&&, std::_Identity<_Value>) + { return { __t, std::forward<_Kt>(__k) }; } + _Rb_tree& _M_t; _Link_type _M_node; }; @@ -2152,6 +2324,39 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return _Res(__x, __y); } +#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 #if __cplusplus >= 201103L @@ -2438,6 +2643,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return {iterator(__res.first), false}; } + template + 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 = _Auto_node::_S_build(*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..17c809240f4 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/map/96088.cc @@ -0,0 +1,325 @@ +// { 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 ); + + VERIFY( !m.emplace(*lst.begin()).second ); + VERIFY( m.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 4 ); +} + +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 ); + + VERIFY( !m.emplace(*lst.begin()).second ); + 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 == 3 ); +} + +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 ); +} + +struct less_string_view_noexcept_transparent_functor +{ + bool + operator()(const std::string_view& lhs, + const std::string_view& rhs) const noexcept + { return lhs < rhs; } + + typedef std::__is_transparent is_transparent; +}; + +void +test24() +{ + __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_transparent_functor +{ + bool + operator()(const std::string_view& lhs, + const std::string_view& rhs) const + { return lhs < rhs; } + + typedef std::__is_transparent is_transparent; +}; + +void +test25() +{ + __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 ); +} + +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(); + test23(); + test24(); + test25(); + 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..a6da8ecda27 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/set/96088.cc @@ -0,0 +1,325 @@ +// { 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 ); + + s.emplace(*lst.begin()); + VERIFY( s.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 4 ); +} + +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 ); + + s.emplace(*lst.begin()); + 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 == 3 ); +} + +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 == 3 ); +} + +struct less_string_view_noexcept_transparent_functor +{ + bool + operator()(const std::string_view& lhs, + const std::string_view& rhs) const noexcept + { return lhs < rhs; } + + typedef std::__is_transparent is_transparent; +}; + +void +test24() +{ + __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_transparent_functor +{ + bool + operator()(const std::string_view& lhs, + const std::string_view& rhs) const + { return lhs < rhs; } + + typedef std::__is_transparent is_transparent; +}; + +void +test25() +{ + __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(); + test24(); + test25(); + test03(); + return 0; +}