diff mbox series

[committed,2/2] libstdc++: Fix conversions to key/value types for hash table insertion [PR115285]

Message ID 20241107220305.658696-2-jwakely@redhat.com
State New
Headers show
Series [committed,1/2] libstdc++: Define __is_pair variable template for C++11 | expand

Commit Message

Jonathan Wakely Nov. 7, 2024, 10 p.m. UTC 
The conversions to key_type and value_type that are performed when
inserting into _Hashtable need to be fixed to do any required
conversions explicitly. The current code assumes that conversions from
the parameter to the key_type or value_type can be done implicitly,
which isn't necessarily true.

Remove the _S_forward_key function which doesn't handle all cases and
either forward the parameter if it already has type cv key_type, or
explicitly construct a temporary of type key_type.

Similarly, the _ConvertToValueType specialization for maps doesn't
handle all cases either, for std::pair arguments only some value
categories are handled. Remove _ConvertToValueType and for the _M_insert
function for unique keys, either forward the argument unchanged or
explicitly construct a temporary of type value_type.

For the _M_insert overload for non-unique keys we don't need any
conversion at all, we can just forward the argument directly to where we
construct a node.

libstdc++-v3/ChangeLog:

	PR libstdc++/115285
	* include/bits/hashtable.h (_Hashtable::_S_forward_key): Remove.
	(_Hashtable::_M_insert_unique_aux): Replace _S_forward_key with
	a static_cast to a type defined using conditional_t.
	(_Hashtable::_M_insert): Replace _ConvertToValueType with a
	static_cast to a type defined using conditional_t.
	* include/bits/hashtable_policy.h (_ConvertToValueType): Remove.
	* testsuite/23_containers/unordered_map/insert/115285.cc: New test.
	* testsuite/23_containers/unordered_set/insert/115285.cc: New test.
	* testsuite/23_containers/unordered_set/96088.cc: Adjust
	expected number of allocations.
---
This is the start of several patch series refactoring the internals
for <unordered_map> and <unordered_set>.

This is a minimal fix suitable for backporting. More changes on trunk
are coming.

Tested powerpc64le-linux. Pushed to trunk.

 libstdc++-v3/include/bits/hashtable.h         | 33 +++++--------
 libstdc++-v3/include/bits/hashtable_policy.h  | 34 --------------
 .../unordered_map/insert/115285.cc            | 47 +++++++++++++++++++
 .../23_containers/unordered_set/96088.cc      |  2 +-
 .../unordered_set/insert/115285.cc            | 28 +++++++++++
 5 files changed, 88 insertions(+), 56 deletions(-)
 create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_map/insert/115285.cc
 create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_set/insert/115285.cc
diff mbox series

Patch

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 6c553fb4b08..bd514cab798 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -929,25 +929,16 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	std::pair<iterator, bool>
 	_M_insert_unique(_Kt&&, _Arg&&, _NodeGenerator&);
 
-      template<typename _Kt>
-	key_type
-	_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 _Arg, typename _NodeGenerator>
 	std::pair<iterator, bool>
 	_M_insert_unique_aux(_Arg&& __arg, _NodeGenerator& __node_gen)
 	{
+	  using _Kt = decltype(_ExtractKey{}(std::forward<_Arg>(__arg)));
+	  constexpr bool __is_key_type
+	    = is_same<__remove_cvref_t<_Kt>, key_type>::value;
+	  using _Fwd_key = __conditional_t<__is_key_type, _Kt&&, key_type>;
 	  return _M_insert_unique(
-	    _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
+	    static_cast<_Fwd_key>(_ExtractKey{}(std::forward<_Arg>(__arg))),
 	    std::forward<_Arg>(__arg), __node_gen);
 	}
 
@@ -956,10 +947,12 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_M_insert(_Arg&& __arg, _NodeGenerator& __node_gen,
 		  true_type /* __uks */)
 	{
-	  using __to_value
-	    = __detail::_ConvertToValueType<_ExtractKey, value_type>;
+	  using __detail::_Identity;
+	  using _Vt = __conditional_t<is_same<_ExtractKey, _Identity>::value
+					|| __is_pair<__remove_cvref_t<_Arg>>,
+				      _Arg&&, value_type>;
 	  return _M_insert_unique_aux(
-	    __to_value{}(std::forward<_Arg>(__arg)), __node_gen);
+		   static_cast<_Vt>(std::forward<_Arg>(__arg)), __node_gen);
 	}
 
       template<typename _Arg, typename _NodeGenerator>
@@ -967,10 +960,8 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_M_insert(_Arg&& __arg, _NodeGenerator& __node_gen,
 		  false_type __uks)
 	{
-	  using __to_value
-	    = __detail::_ConvertToValueType<_ExtractKey, value_type>;
-	  return _M_insert(cend(),
-	    __to_value{}(std::forward<_Arg>(__arg)), __node_gen, __uks);
+	  return _M_insert(cend(), std::forward<_Arg>(__arg),
+			   __node_gen, __uks);
 	}
 
       // Insert with hint, not used when keys are unique.
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index d8b201864c1..e5ad85ed9f1 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -113,40 +113,6 @@  namespace __detail
       { return std::forward<_Tp>(__x).first; }
   };
 
-  template<typename _ExKey, typename _Value>
-    struct _ConvertToValueType;
-
-  template<typename _Value>
-    struct _ConvertToValueType<_Identity, _Value>
-    {
-      template<typename _Kt>
-	constexpr _Kt&&
-	operator()(_Kt&& __k) const noexcept
-	{ return std::forward<_Kt>(__k); }
-    };
-
-  template<typename _Value>
-    struct _ConvertToValueType<_Select1st, _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 _Val>
-	constexpr std::pair<_Kt, _Val>&&
-	operator()(std::pair<_Kt, _Val>&& __x) const noexcept
-	{ return std::move(__x); }
-
-      template<typename _Kt, typename _Val>
-	constexpr const std::pair<_Kt, _Val>&
-	operator()(const std::pair<_Kt, _Val>& __x) const noexcept
-	{ return __x; }
-    };
-
   template<typename _ExKey>
     struct _NodeBuilder;
 
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/insert/115285.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/insert/115285.cc
new file mode 100644
index 00000000000..4ada6a6e588
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/insert/115285.cc
@@ -0,0 +1,47 @@ 
+// { dg-do run { target c++11 } }
+
+// PR libstdc++/115285
+
+#include <unordered_map>
+#include <iterator>
+#include <testsuite_hooks.h>
+
+struct Pair
+{
+  explicit operator std::pair<const int, int>() const&& { return {1, 2}; }
+};
+
+void
+test01()
+{
+  Pair p[2];
+  auto mi = std::make_move_iterator(p);
+  auto me = std::make_move_iterator(p+2);
+  std::unordered_map<int, int> m(mi, me);
+  VERIFY( m.size() == 1 );
+}
+
+struct K {
+  explicit K(int) noexcept { }
+  bool operator==(const K&) const { return true; }
+};
+
+template<> struct std::hash<K> {
+  std::size_t operator()(const K&) const { return 0ul; }
+};
+
+void
+test02()
+{
+  const std::pair<int, int> p[2]{{1,2}, {3,4}};
+  auto mi = std::make_move_iterator(p);
+  auto me = std::make_move_iterator(p+2);
+  std::unordered_map<K, int> m(mi, me);
+  VERIFY( m.size() == 1 );
+}
+
+int main()
+{
+  test01();
+  test02();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc
index bc2f093f47c..59e1ad12401 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc
@@ -244,7 +244,7 @@  test03()
     VERIFY( us.size() == 1 );
 
     VERIFY( __gnu_test::counter::count() == origin + increments );
-    VERIFY( __gnu_test::counter::get()._M_increments == increments + 1 );
+    VERIFY( __gnu_test::counter::get()._M_increments == increments );
   }
   VERIFY( __gnu_test::counter::count() == origin );
 
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/insert/115285.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/insert/115285.cc
new file mode 100644
index 00000000000..aead7b67469
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/insert/115285.cc
@@ -0,0 +1,28 @@ 
+// { dg-do run { target c++11 } }
+
+// PR libstdc++/115285
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+
+struct K {
+  explicit K(int) noexcept { }
+  bool operator==(const K&) const { return true; }
+};
+
+template<> struct std::hash<K> {
+  std::size_t operator()(const K&) const { return 0ul; }
+};
+
+void
+test01()
+{
+  int i[2]{1, 2};
+  std::unordered_set<K> s(i, i+2);
+  VERIFY( s.size() == 1 );
+}
+
+int main()
+{
+  test01();
+}