[PATCH] libstdc++: Limit allocations in _Rb_tree 2/2

["François Dumont" <frs.dumont@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 1312 bytes --]

This one is a refinement for multimap/multiset.

It allows to have share the same key if managed with ref counting like 
the cow string.

     libstdc++: [_Rb_tree] Limit allocations on equal insertions [PR 96088]

     When inserting the same key several times prefer to insert the new 
entry using the
     current stored key_type instance if this copy is noexcept. 
Otherwise create a new
     key instance from input argument.

     libstdc++-v3/ChangeLog:

             PR libstdc++/96088
             * include/bits/cow_string.h 
(basic_string<>::basic_string(const basic_string&)):
             Add noexcept qualification when allocator is always equal.
             * include/bits/stl_tree.h 
(_Rb_tree<>::_M_get_insert_equal_pos_tr): New.
             (_Rb_tree<>::_M_emplace_equal_tr): New, use latter.
             (_Rb_tree<>::_M_emplace_equal_aux): New, use latter.
(_Rb_tree<>::_M_emplace_equal<_Arg>(_Arg&&)): New, use latter.
             * testsuite/23_containers/multimap/96088.cc (test01): Add 
check on redundant
             insertion.
             (test02): Likewise.
             * testsuite/23_containers/multiset/96088.cc (test01, 
test02): Likewise.

François

[-- Attachment #2: pr96088_multimap.patch --]
[-- Type: text/x-patch, Size: 5413 bytes --]

diff --git a/libstdc++-v3/include/bits/cow_string.h b/libstdc++-v3/include/bits/cow_string.h
index ad9929c4ad3..cdfbe5e190b 100644
--- a/libstdc++-v3/include/bits/cow_string.h
+++ b/libstdc++-v3/include/bits/cow_string.h
@@ -541,6 +541,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
        *  @param  __str  Source string.
        */
       basic_string(const basic_string& __str)
+	_GLIBCXX_NOEXCEPT_IF(_CharT_alloc_traits::_S_always_equal())
       : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()),
 					    __str.get_allocator()),
 		    __str.get_allocator())
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index 21e9586b0a3..c3a4a97cfcf 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -968,6 +968,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       template<typename _Kt>
 	pair<_Base_ptr, _Base_ptr>
 	_M_get_insert_unique_pos_tr(const _Kt& __k);
+
+      template<typename _Kt>
+	pair<_Base_ptr, _Base_ptr>
+	_M_get_insert_equal_pos_tr(const _Kt& __k);
 #endif
 
       pair<_Base_ptr, _Base_ptr>
@@ -1225,6 +1229,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    std::forward<_Arg>(__arg));
 	}
 
+      template<typename _Kt, typename _Arg>
+	iterator
+	_M_emplace_equal_kv(_Kt&&, _Arg&&);
+
+      template<typename _Arg>
+	iterator
+	_M_emplace_equal_aux(_Arg&& __arg)
+	{
+	  return _M_emplace_equal_kv(
+	    _S_forward_key(_KeyOfValue{}(std::forward<_Arg>(__arg))),
+	    std::forward<_Arg>(__arg));
+	}
+
       template<typename _Arg>
 	pair<iterator, bool>
 	_M_emplace_unique(_Arg&& __arg)
@@ -1237,6 +1254,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	pair<iterator, bool>
 	_M_emplace_unique(_Args&&... __args);
 
+      template<typename _Arg>
+	iterator
+	_M_emplace_equal(_Arg&& __arg)
+	{
+	  using __to_value = _ConvertToValueType<_KeyOfValue, value_type>;
+	  return _M_emplace_equal_aux(__to_value{}(std::forward<_Arg>(__arg)));
+	}
+
       template<typename... _Args>
 	iterator
 	_M_emplace_equal(_Args&&... __args);
@@ -2355,6 +2380,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  return _Res(__x, __y);
 	return _Res(__j._M_node, 0);
       }
+
+  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_equal_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();
+	while (__x != 0)
+	  {
+	    __y = __x;
+	    __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
+	      _S_left(__x) : _S_right(__x);
+	  }
+	return _Res(__x, __y);
+      }
 #endif
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -2661,6 +2706,26 @@ _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_equal_kv(_Kt&& __k, _Arg&& __arg)
+      -> iterator
+      {
+	auto __res = _M_get_insert_equal_pos_tr(__k);
+	_Auto_node __z =
+	  (!is_nothrow_copy_constructible<key_type>::value
+	   || __res.second == _M_end()
+	   || _M_impl._M_key_compare(__k, _S_key(__res.second)))
+	  ? _S_build_node(*this, std::forward<_Kt>(__k),
+			  std::forward<_Arg>(__arg), _KeyOfValue{})
+	  : _S_build_node(*this, _S_key(__res.second),
+			  std::forward<_Arg>(__arg), _KeyOfValue{});
+	return __z._M_insert(__res);
+      }
+
   template<typename _Key, typename _Val, typename _KeyOfValue,
 	   typename _Compare, typename _Alloc>
     template<typename... _Args>
diff --git a/libstdc++-v3/testsuite/23_containers/multimap/96088.cc b/libstdc++-v3/testsuite/23_containers/multimap/96088.cc
index 919c5e59c71..1a778a0785d 100644
--- a/libstdc++-v3/testsuite/23_containers/multimap/96088.cc
+++ b/libstdc++-v3/testsuite/23_containers/multimap/96088.cc
@@ -1,4 +1,5 @@
 // { dg-do run { target c++17 } }
+// { dg-add-options no_pch }
 // { dg-require-effective-target std_allocator_new }
 
 // Copyright (C) 2023 Free Software Foundation, Inc.
@@ -20,6 +21,9 @@
 
 // libstdc++/96088
 
+#undef _GLIBCXX_USE_CXX11_ABI
+#define _GLIBCXX_USE_CXX11_ABI 0
+
 #include <string_view>
 #include <string>
 #include <map>
@@ -42,6 +46,15 @@ test01()
 
   VERIFY( __gnu_test::counter::count() == 2 );
   VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  // Allocate a node and the std::string (unless COW).
+  constexpr std::size_t increments = _GLIBCXX_USE_CXX11_ABI ? 2 : 1;
+
+  foo.insert(lst.begin(), lst.end());
+  VERIFY( foo.size() == 2 );
+
+  VERIFY( __gnu_test::counter::count() == 2 + increments );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 + increments );
 }
 
 void
@@ -54,6 +67,15 @@ test02()
 
   VERIFY( __gnu_test::counter::count() == 2 );
   VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  // Allocate a node and the std::string (unless COW).
+  constexpr std::size_t increments = _GLIBCXX_USE_CXX11_ABI ? 2 : 1;
+
+  foo.insert(lst.begin(), lst.end());
+  VERIFY( foo.size() == 2 );
+
+  VERIFY( __gnu_test::counter::count() == 2 + increments );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 + 2 );
 }
 
 int