diff mbox series

libstdc++: Limit allocations in _Rb_tree

Message ID df42fe65-4c8a-8448-6463-17e498e0a6cd@gmail.com
State Superseded
Headers
Series libstdc++: Limit allocations in _Rb_tree |

Commit Message

François Dumont Feb. 2, 2023, 6:20 p.m. UTC 
  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 mbox series

Patch

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<typename _Tp2>
+      _Tp2&&
+      operator()(_Tp2&& __x) const noexcept
+      { return std::forward<_Tp2>(__x); }
+#endif
     };
 
   // Partial specialization, avoids confusing errors in e.g. std::set<const T>.
@@ -1192,6 +1201,11 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	const typename _Pair2::first_type&
 	operator()(const _Pair2& __x) const
 	{ return __x.first; }
+
+      template<typename _Pair2>
+	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<typename _ExKey, typename _Value>
+	struct _ConvertToValueType;
+
+      template<typename _Value>
+	struct _ConvertToValueType<std::_Identity<_Value>, _Value>
+	{
+	  template<typename _Kt>
+	    constexpr _Kt&&
+	    operator()(_Kt&& __k) const noexcept
+	    { return std::forward<_Kt>(__k); }
+	};
+
+      template<typename _Value>
+	struct _ConvertToValueType<std::_Select1st<_Value>, _Value>
+	{
+	  constexpr _Value&&
+	  operator()(_Value&& __x) const noexcept
+	  { return std::move(__x); }
+
+	  constexpr const _Value&
+	  operator()(const _Value& __x) const noexcept
+	  { return __x; }
+
+	  template<typename _Kt, typename _Vt>
+	    constexpr std::pair<_Kt, _Vt>&&
+	    operator()(std::pair<_Kt, _Vt>&& __x) const noexcept
+	    { return std::move(__x); }
+
+	  template<typename _Kt, typename _Vt>
+	    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<typename _Kt>
+	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<typename _Kt>
+	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<typename _Kt, typename _Arg>
+	std::pair<iterator, bool>
+	_M_emplace_unique_kv(_Kt&&, _Arg&&);
+
+      template<typename _Arg>
+	pair<iterator, bool>
+	_M_emplace_unique_aux(_Arg&& __arg)
+	{
+	  return _M_emplace_unique_kv(
+	    _S_forward_key(_KeyOfValue{}(std::forward<_Arg>(__arg))),
+	    std::forward<_Arg>(__arg));
+	}
+
+      template<typename _Arg>
+	pair<iterator, bool>
+	_M_emplace_unique(_Arg&& __arg)
+	{
+	  using __to_value = _ConvertToValueType<_KeyOfValue, value_type>;
+	  return _M_emplace_unique_aux(__to_value{}(std::forward<_Arg>(__arg)));
+	}
+
       template<typename... _Args>
 	pair<iterator, bool>
 	_M_emplace_unique(_Args&&... __args);
@@ -1670,6 +1751,19 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_Rb_tree& _M_t;
 	_Link_type _M_node;
       };
+
+      template<typename _Kt, typename _Arg, typename _SelectFst>
+	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<typename _Kt, typename _Arg>
+	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<typename _Key, typename _Val, typename _KeyOfValue,
+	   typename _Compare, typename _Alloc>
+    template<typename _Kt>
+      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<typename _Key, typename _Val, typename _KeyOfValue,
 	   typename _Compare, typename _Alloc>
     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
@@ -2438,6 +2565,24 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	return {iterator(__res.first), false};
       }
 
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+	   typename _Compare, typename _Alloc>
+    template<typename _Kt, typename _Arg>
+      auto
+      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      _M_emplace_unique_kv(_Kt&& __k, _Arg&& __arg)
+      -> pair<iterator, bool>
+      {
+	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<typename _Key, typename _Val, typename _KeyOfValue,
 	   typename _Compare, typename _Alloc>
     template<typename... _Args>
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
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/96088
+
+#include <string_view>
+#include <string>
+#include <map>
+#include <vector>
+
+#include <testsuite_hooks.h>
+#include <replacement_memory_operators.h>
+
+static constexpr std::initializer_list<std::pair<const char*, int>> lst =
+  { {"long_str_for_dynamic_allocating", 1} };
+
+void
+test01()
+{
+  __gnu_test::counter::reset();
+  std::map<std::string, int> 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<std::string, int, std::less<std::string_view>> 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<std::string, int, less_string_t> 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<std::string, int, less_stringview_t> 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<std::string, int, less_string_functor> 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<std::string, int, less_string_view_noexcept_functor> 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<std::string, int, less_string_view_functor> 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<std::pair<std::string, int>> v;
+  v.insert(v.end(), lst.begin(), lst.end());
+
+  const auto origin = __gnu_test::counter::count();
+
+  {
+    __gnu_test::counter::reset();
+    std::map<std::string, int, std::less<std::string_view>> 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<std::string, int, std::less<std::string_view>> 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
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/96088
+
+#include <string_view>
+#include <string>
+#include <map>
+
+#include <testsuite_hooks.h>
+#include <replacement_memory_operators.h>
+
+static constexpr std::initializer_list<std::pair<const char*, int>> lst = {
+    {"long_str_for_dynamic_allocating", 1}
+};
+
+void
+test01()
+{
+  __gnu_test::counter::reset();
+  std::multimap<std::string, int,
+		std::less<std::string_view>> 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<std::string, int> 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
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/96088
+
+#include <string_view>
+#include <string>
+#include <set>
+
+#include <testsuite_hooks.h>
+#include <replacement_memory_operators.h>
+
+static constexpr std::initializer_list<const char*> lst = {
+  "long_str_for_dynamic_allocating"
+};
+
+void
+test01()
+{
+  __gnu_test::counter::reset();
+  std::multiset<std::string, std::less<std::string_view>> 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<std::string> 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
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/96088
+
+#include <string_view>
+#include <string>
+#include <set>
+#include <vector>
+
+#include <testsuite_hooks.h>
+#include <replacement_memory_operators.h>
+
+static constexpr std::initializer_list<const char*> lst = {
+  "long_str_for_dynamic_allocating"
+};
+
+void
+test01()
+{
+  __gnu_test::counter::reset();
+  std::set<std::string, std::greater<std::string>> 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<std::string, std::greater<std::string_view>> 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<std::string, less_string_t> 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<std::string, less_stringview_t> 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<std::string, less_string_functor> 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<std::string, less_string_view_noexcept_functor> 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<std::string, less_string_view_functor> 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<std::string> v;
+  v.insert(v.end(), lst.begin(), lst.end());
+
+  const auto origin = __gnu_test::counter::count();
+
+  {
+    __gnu_test::counter::reset();
+    std::set<std::string, std::less<std::string_view>> 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<std::string, std::less<std::string_view>> 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;
+}