[PATCH][_Hashtable] Fix insertion of range of type convertible to value_type PR 56112

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

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

Hi

Renewing my patch to fix PR 56112 but for the insert methods, I totally 
change it, now works also with move-only key types.

I let you Jonathan find a better name than _ValueTypeEnforcer as usual :-)

libstdc++: [_Hashtable] Insert range of types convertible to value_type 
PR 56112

Fix insertion of range of types convertible to value_type. Fix also when 
this value_type
has a move-only key_type which also allow converted values to be moved.

libstdc++-v3/ChangeLog:

         PR libstdc++/56112
         * include/bits/hashtable_policy.h (_ValueTypeEnforcer): New.
         * include/bits/hashtable.h 
(_Hashtable<>::_M_insert_unique_aux): New.
         (_Hashtable<>::_M_insert(_Arg&&, const _NodeGenerator&, 
true_type)): Use latters.
         (_Hashtable<>::_M_insert(_Arg&&, const _NodeGenerator&, 
false_type)): Likewise.
         (_Hashtable(_InputIterator, _InputIterator, size_type, const 
_Hash&, const _Equal&,
         const allocator_type&, true_type)): Use this.insert range.
         (_Hashtable(_InputIterator, _InputIterator, size_type, const 
_Hash&, const _Equal&,
         const allocator_type&, false_type)): Use _M_insert.
         * testsuite/23_containers/unordered_map/cons/56112.cc: Check 
how many times conversion
         is done.
         (test02): New test case.
         * testsuite/23_containers/unordered_set/cons/56112.cc: New test.

Tested under Linux x86_64.

Ok to commit ?

François


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

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 5e1a417f7cd..cd42d3c9ba0 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -898,21 +898,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       template<typename _Arg, typename _NodeGenerator>
 	std::pair<iterator, bool>
-	_M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
-		  true_type /* __uks */)
+	_M_insert_unique_aux(_Arg&& __arg, const _NodeGenerator& __node_gen)
 	{
 	  return _M_insert_unique(
 	    _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
 	    std::forward<_Arg>(__arg), __node_gen);
 	}
 
+      template<typename _Arg, typename _NodeGenerator>
+	std::pair<iterator, bool>
+	_M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
+		  true_type /* __uks */)
+	{
+	  using __to_value
+	    = __detail::_ValueTypeEnforcer<_ExtractKey, value_type>;
+	  return _M_insert_unique_aux(
+	    __to_value{}(std::forward<_Arg>(__arg)), __node_gen);
+	}
+
       template<typename _Arg, typename _NodeGenerator>
 	iterator
 	_M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
 		  false_type __uks)
 	{
-	  return _M_insert(cend(), std::forward<_Arg>(__arg), __node_gen,
-			   __uks);
+	  using __to_value
+	    = __detail::_ValueTypeEnforcer<_ExtractKey, value_type>;
+	  return _M_insert(cend(),
+	    __to_value{}(std::forward<_Arg>(__arg)), __node_gen, __uks);
 	}
 
       // Insert with hint, not used when keys are unique.
@@ -1184,10 +1196,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		 const _Hash& __h, const _Equal& __eq,
 		 const allocator_type& __a, true_type /* __uks */)
       : _Hashtable(__bkt_count_hint, __h, __eq, __a)
-      {
-	for (; __f != __l; ++__f)
-	  this->insert(*__f);
-      }
+      { this->insert(__f, __l); }
 
   template<typename _Key, typename _Value, typename _Alloc,
 	   typename _ExtractKey, typename _Equal,
@@ -1199,7 +1208,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _Hashtable(_InputIterator __f, _InputIterator __l,
 		 size_type __bkt_count_hint,
 		 const _Hash& __h, const _Equal& __eq,
-		 const allocator_type& __a, false_type /* __uks */)
+		 const allocator_type& __a, false_type __uks)
       : _Hashtable(__h, __eq, __a)
       {
 	auto __nb_elems = __detail::__distance_fw(__f, __l);
@@ -1214,8 +1223,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    _M_bucket_count = __bkt_count;
 	  }
 
+	__alloc_node_gen_t __node_gen(*this);
 	for (; __f != __l; ++__f)
-	  this->insert(*__f);
+	  _M_insert(*__f, __node_gen, __uks);
       }
 
   template<typename _Key, typename _Value, typename _Alloc,
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 0f0b0f9ea51..51518316cb8 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -109,6 +109,58 @@ namespace __detail
       { return std::forward<_Tp>(__x).first; }
   };
 
+  template<typename _ExKey, typename _Value>
+    struct _ValueTypeEnforcer;
+
+  template<typename _Value>
+    struct _ValueTypeEnforcer<_Identity, _Value>
+    {
+      template<typename _Kt>
+	constexpr _Kt&&
+	operator()(_Kt&& __k) noexcept
+	{ return std::forward<_Kt>(__k); }
+    };
+
+  template<typename _Value>
+    struct _ValueTypeEnforcer<_Select1st, _Value>
+    {
+      constexpr _Value&&
+      operator()(_Value&& __x) noexcept
+      { return std::move(__x); }
+
+      constexpr const _Value&
+      operator()(const _Value& __x) noexcept
+      { return __x; }
+
+      using __fst_type = typename _Value::first_type;
+
+      template<typename _Pair>
+	using __mutable_value_t =
+	  std::pair<
+	    typename std::remove_const<typename _Pair::first_type>::type,
+	    typename _Pair::second_type>;
+
+      constexpr __enable_if_t<std::is_const<__fst_type>::value,
+			      __mutable_value_t<_Value>&&>
+      operator()(__mutable_value_t<_Value>&& __x) noexcept
+      { return std::move(__x); }
+
+      constexpr __enable_if_t<std::is_const<__fst_type>::value,
+			      const __mutable_value_t<_Value>&>
+      operator()(const __mutable_value_t<_Value>& __x) noexcept
+      { return __x; }
+
+      template<typename _Kt, typename _Val>
+	constexpr std::pair<_Kt, _Val>&&
+	operator()(std::pair<_Kt, _Val>&& __x) noexcept
+	{ return std::move(__x); }
+
+      template<typename _Kt, typename _Val>
+	constexpr const std::pair<_Kt, _Val>&
+	operator()(const std::pair<_Kt, _Val>& __x) noexcept
+	{ return __x; }
+    };
+
   template<typename _ExKey>
     struct _NodeBuilder;
 
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/cons/56112.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/cons/56112.cc
index c4cdeee234c..4476103c986 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_map/cons/56112.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/cons/56112.cc
@@ -20,30 +20,108 @@
 #include <unordered_map>
 #include <utility>
 
+#include <testsuite_hooks.h>
+
 struct Key
 {
   explicit Key(const int* p) : value(p) { }
   ~Key() { value = nullptr; }
 
-  bool operator==(const Key& k) const { return *value == *k.value; }
+  bool operator==(const Key& k) const
+  { return *value == *k.value; }
 
   const int* value;
 };
 
 struct hash
 {
-  std::size_t operator()(const Key& k) const noexcept { return *k.value; }
+  std::size_t operator()(const Key& k) const noexcept
+  { return *k.value; }
 };
 
 struct S
 {
+  static int _count;
+
   int value;
-  operator std::pair<const Key, int>() const { return {Key(&value), value}; }
+  operator std::pair<const Key, int>() const
+  {
+    ++_count;
+    return { Key(&value), value };
+  }
 };
 
-int main()
+int S::_count = 0;
+
+void test01()
 {
     S s[1] = { {2} };
-    std::unordered_map<Key, int, hash> m(s, s+1);
-    std::unordered_multimap<Key, int, hash> mm(s, s+1);
+    std::unordered_map<Key, int, hash> m(s, s + 1);
+    VERIFY( S::_count == 1 );
+
+    std::unordered_multimap<Key, int, hash> mm(s, s + 1);
+    VERIFY( S::_count == 2 );
+
+    m.insert(s, s + 1);
+    VERIFY( S::_count == 3 );
+
+    mm.insert(s, s + 1);
+    VERIFY( S::_count == 4 );
+}
+
+struct MoveOnlyKey
+{
+  explicit MoveOnlyKey(const int* p) : value(p) { }
+  MoveOnlyKey(const MoveOnlyKey&) = delete;
+  MoveOnlyKey(MoveOnlyKey&& k) : value(k.value)
+  { k.value = nullptr;  }
+  ~MoveOnlyKey() { value = nullptr; }
+
+  bool operator==(const MoveOnlyKey& k) const
+  { return *value == *k.value; }
+
+  const int* value;
+};
+
+struct MoveOnlyKeyHash
+{
+  std::size_t operator()(const MoveOnlyKey& k) const noexcept
+  { return *k.value; }
+};
+
+struct S2
+{
+  static int _count;
+
+  int value;
+  operator std::pair<MoveOnlyKey, int>() const
+  {
+    ++_count;
+    return { MoveOnlyKey(&value), value };
+  }
+};
+
+int S2::_count = 0;
+
+void test02()
+{
+    S2 s[1] = { {2} };
+    std::unordered_map<MoveOnlyKey, int, MoveOnlyKeyHash> m(s, s + 1);
+    VERIFY( S2::_count == 1 );
+
+    std::unordered_multimap<MoveOnlyKey, int, MoveOnlyKeyHash> mm(s, s + 1);
+    VERIFY( S2::_count == 2 );
+
+    m.insert(s, s + 1);
+    VERIFY( S2::_count == 3 );
+
+    mm.insert(s, s + 1);
+    VERIFY( S2::_count == 4 );
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
 }
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/cons/56112.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/cons/56112.cc
new file mode 100644
index 00000000000..c55965a2caa
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/cons/56112.cc
@@ -0,0 +1,70 @@
+// { dg-do run { target c++11 } }
+
+// Copyright (C) 2022 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/>.
+
+#include <unordered_set>
+#include <utility>
+
+#include <testsuite_hooks.h>
+
+struct Key
+{
+  explicit Key(const int* p) : value(p) { }
+  ~Key() { value = nullptr; }
+
+  bool operator==(const Key& k) const
+  { return *value == *k.value; }
+
+  const int* value;
+};
+
+struct hash
+{
+  std::size_t operator()(const Key& k) const noexcept
+  { return *k.value; }
+};
+
+struct S
+{
+  static int _count;
+
+  int value;
+  operator Key() const
+  {
+    ++_count;
+    return Key(&value);
+  }
+};
+
+int S::_count = 0;
+
+int main()
+{
+    S s[1] = { {2} };
+    std::unordered_set<Key, hash> m(s, s + 1);
+    VERIFY( S::_count == 1 );
+
+    std::unordered_multiset<Key, hash> mm(s, s + 1);
+    VERIFY( S::_count == 2 );
+
+    m.insert(s, s + 1);
+    VERIFY( S::_count == 3 );
+
+    mm.insert(s, s + 1);
+    VERIFY( S::_count == 4 );
+}