libstdc++: _Rb_tree code cleanup, remove lambdas

Use new template parameters to replace usage of lambdas to move or not
tree values on copy.

libstdc++-v3/ChangeLog:

	* include/bits/move.h (_GLIBCXX_FWDREF): New.
	* include/bits/stl_tree.h: Adapt to use latter.
	(_Rb_tree<>::_M_clone_node): Add _MoveValue template parameter.
	(_Rb_tree<>::_M_mbegin): New.
	(_Rb_tree<>::_M_begin): Use latter.
	(_Rb_tree<>::_M_copy): Add _MoveValues template parameter.
	* testsuite/23_containers/map/allocator/move_cons.cc: New test.
	* testsuite/23_containers/multimap/allocator/move_cons.cc: New test.
	* testsuite/23_containers/multiset/allocator/move_cons.cc: New test.
	* testsuite/23_containers/set/allocator/move_cons.cc: New test.

6 files changed, 250 insertions, 40 deletions

diff --git a/libstdc++-v3/include/bits/move.h b/libstdc++-v3/include/bits/move.h
index 5a4dbdc..b33c22a 100644
--- a/libstdc++-v3/include/bits/move.h
+++ b/libstdc++-v3/include/bits/move.h
@@ -158,9 +158,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   /// @} group utilities
 
+#define _GLIBCXX_FWDREF(_Tp) _Tp&&
 #define _GLIBCXX_MOVE(__val) std::move(__val)
 #define _GLIBCXX_FORWARD(_Tp, __val) std::forward<_Tp>(__val)
 #else
+#define _GLIBCXX_FWDREF(_Tp) const _Tp&
 #define _GLIBCXX_MOVE(__val) (__val)
 #define _GLIBCXX_FORWARD(_Tp, __val) (__val)
 #endif
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index ec141ea..a51d6da 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -478,11 +478,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 	template<typename _Arg>
 	  _Link_type
-#if __cplusplus < 201103L
-	  operator()(const _Arg& __arg)
-#else
-	  operator()(_Arg&& __arg)
-#endif
+	  operator()(_GLIBCXX_FWDREF(_Arg) __arg)
 	  {
 	    _Link_type __node = static_cast<_Link_type>(_M_extract());
 	    if (__node)
@@ -544,11 +540,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 	template<typename _Arg>
 	  _Link_type
-#if __cplusplus < 201103L
-	  operator()(const _Arg& __arg) const
-#else
-	  operator()(_Arg&& __arg) const
-#endif
+	  operator()(_GLIBCXX_FWDREF(_Arg) __arg) const
 	  { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
 
       private:
@@ -655,11 +647,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_M_put_node(__p);
       }
 
-      template<typename _NodeGen>
+      template<bool _MoveValue, typename _NodeGen>
 	_Link_type
-	_M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen)
+	_M_clone_node(_Link_type __x, _NodeGen& __node_gen)
 	{
-	  _Link_type __tmp = __node_gen(*__x->_M_valptr());
+#if __cplusplus >= 201103L
+	  using _Vp = typename conditional<_MoveValue,
+					   value_type&&,
+					   const value_type&>::type;
+#endif
+	  _Link_type __tmp
+	    = __node_gen(_GLIBCXX_FORWARD(_Vp, *__x->_M_valptr()));
 	  __tmp->_M_color = __x->_M_color;
 	  __tmp->_M_left = 0;
 	  __tmp->_M_right = 0;
@@ -748,9 +746,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       { return this->_M_impl._M_header._M_right; }
 
       _Link_type
-      _M_begin() _GLIBCXX_NOEXCEPT
+      _M_mbegin() const _GLIBCXX_NOEXCEPT
       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
 
+      _Link_type
+      _M_begin() _GLIBCXX_NOEXCEPT
+      { return _M_mbegin(); }
+
       _Const_Link_type
       _M_begin() const _GLIBCXX_NOEXCEPT
       {
@@ -889,15 +891,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _M_insert_equal_lower(const value_type& __x);
 #endif
 
-      template<typename _NodeGen>
+      enum { __as_lvalue, __as_rvalue };
+
+      template<bool _MoveValues, typename _NodeGen>
 	_Link_type
-	_M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&);
+	_M_copy(_Link_type, _Base_ptr, _NodeGen&);
 
-      template<typename _NodeGen>
+      template<bool _MoveValues, typename _NodeGen>
 	_Link_type
 	_M_copy(const _Rb_tree& __x, _NodeGen& __gen)
 	{
-	  _Link_type __root = _M_copy(__x._M_begin(), _M_end(), __gen);
+	  _Link_type __root =
+	    _M_copy<_MoveValues>(__x._M_mbegin(), _M_end(), __gen);
 	  _M_leftmost() = _S_minimum(__root);
 	  _M_rightmost() = _S_maximum(__root);
 	  _M_impl._M_node_count = __x._M_impl._M_node_count;
@@ -908,7 +913,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _M_copy(const _Rb_tree& __x)
       {
 	_Alloc_node __an(*this);
-	return _M_copy(__x, __an);
+	return _M_copy<__as_lvalue>(__x, __an);
       }
 
       void
@@ -1655,13 +1660,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       else
 	{
 	  _Alloc_node __an(*this);
-	  auto __lbd =
-	    [&__an](const value_type& __cval)
-	    {
-	      auto& __val = const_cast<value_type&>(__cval);
-	      return __an(std::move_if_noexcept(__val));
-	    };
-	  _M_root() = _M_copy(__x, __lbd);
+	  _M_root() =
+	    _M_copy<!__move_if_noexcept_cond<value_type>::value>(__x, __an);
 	}
     }
 
@@ -1693,13 +1693,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _M_impl._M_reset();
       if (__x._M_root() != nullptr)
 	{
-	  auto __lbd =
-	    [&__roan](const value_type& __cval)
-	    {
-	      auto& __val = const_cast<value_type&>(__cval);
-	      return __roan(std::move(__val));
-	    };
-	  _M_root() = _M_copy(__x, __lbd);
+	  _M_root() = _M_copy<__as_rvalue>(__x, __roan);
 	  __x.clear();
 	}
     }
@@ -1773,7 +1767,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  _M_impl._M_reset();
 	  _M_impl._M_key_compare = __x._M_impl._M_key_compare;
 	  if (__x._M_root() != 0)
-	    _M_root() = _M_copy(__x, __roan);
+	    _M_root() = _M_copy<__as_lvalue>(__x, __roan);
 	}
 
       return *this;
@@ -1859,29 +1853,31 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   template<typename _Key, typename _Val, typename _KoV,
 	   typename _Compare, typename _Alloc>
-    template<typename _NodeGen>
+    template<bool _MoveValues, typename _NodeGen>
       typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
       _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
-      _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen)
+      _M_copy(_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen)
       {
 	// Structural copy. __x and __p must be non-null.
-	_Link_type __top = _M_clone_node(__x, __node_gen);
+	_Link_type __top = _M_clone_node<_MoveValues>(__x, __node_gen);
 	__top->_M_parent = __p;
 
 	__try
 	  {
 	    if (__x->_M_right)
-	      __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen);
+	      __top->_M_right =
+		_M_copy<_MoveValues>(_S_right(__x), __top, __node_gen);
 	    __p = __top;
 	    __x = _S_left(__x);
 
 	    while (__x != 0)
 	      {
-		_Link_type __y = _M_clone_node(__x, __node_gen);
+		_Link_type __y = _M_clone_node<_MoveValues>(__x, __node_gen);
 		__p->_M_left = __y;
 		__y->_M_parent = __p;
 		if (__x->_M_right)
-		  __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen);
+		  __y->_M_right = _M_copy<_MoveValues>(_S_right(__x),
+						       __y, __node_gen);
 		__p = __y;
 		__x = _S_left(__x);
 	      }
diff --git a/libstdc++-v3/testsuite/23_containers/map/allocator/move_cons.cc b/libstdc++-v3/testsuite/23_containers/map/allocator/move_cons.cc
new file mode 100644
index 0000000..08a14a4
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/map/allocator/move_cons.cc
@@ -0,0 +1,53 @@
+// Copyright (C) 2020 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/>.
+
+// { dg-do run { target c++11 } }
+
+#include <map>
+#include <string>
+
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+using Cmp = std::less<int>;
+
+using __gnu_test::uneq_allocator;
+
+void test01()
+{
+  typedef uneq_allocator<std::pair<const int, std::string>> alloc_type;
+  typedef std::map<int, std::string, Cmp, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  const char* str = "A long enough string to require dynamic allocation";
+  v1 = { { 1, str } };
+
+  alloc_type a2(2);
+  test_type v2(std::move(v1), a2);
+
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(2 == v2.get_allocator().get_personality());
+
+  VERIFY( v1[1].empty() );
+  VERIFY( v2[1] == str );
+}
+
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/multimap/allocator/move_cons.cc b/libstdc++-v3/testsuite/23_containers/multimap/allocator/move_cons.cc
new file mode 100644
index 0000000..4fbd85d
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multimap/allocator/move_cons.cc
@@ -0,0 +1,53 @@
+// Copyright (C) 2020 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/>.
+
+// { dg-do run { target c++11 } }
+
+#include <map>
+#include <string>
+
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+using Cmp = std::less<int>;
+
+using __gnu_test::uneq_allocator;
+
+void test01()
+{
+  typedef uneq_allocator<std::pair<const int, std::string>> alloc_type;
+  typedef std::multimap<int, std::string, Cmp, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  const char* str = "A long enough string to require dynamic allocation";
+  v1 = { { 1, str } };
+
+  alloc_type a2(2);
+  test_type v2(std::move(v1), a2);
+
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(2 == v2.get_allocator().get_personality());
+
+  VERIFY( v1.begin()->second.empty() );
+  VERIFY( v2.begin()->second == str );
+}
+
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/multiset/allocator/move_cons.cc b/libstdc++-v3/testsuite/23_containers/multiset/allocator/move_cons.cc
new file mode 100644
index 0000000..bc7356b
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multiset/allocator/move_cons.cc
@@ -0,0 +1,53 @@
+// Copyright (C) 2020 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/>.
+
+// { dg-do run { target c++11 } }
+
+#include <set>
+#include <string>
+
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+using Cmp = std::less<std::string>;
+
+using __gnu_test::uneq_allocator;
+
+void test01()
+{
+  typedef uneq_allocator<std::string> alloc_type;
+  typedef std::multiset<std::string, Cmp, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  const char* str = "A long enough string to require dynamic allocation";
+  v1 = { str };
+
+  alloc_type a2(2);
+  test_type v2(std::move(v1), a2);
+
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(2 == v2.get_allocator().get_personality());
+
+  VERIFY( v1.count(str) == 0 );
+  VERIFY( v2.count(str) == 1 );
+}
+
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/set/allocator/move_cons.cc b/libstdc++-v3/testsuite/23_containers/set/allocator/move_cons.cc
new file mode 100644
index 0000000..137d50d
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/set/allocator/move_cons.cc
@@ -0,0 +1,53 @@
+// Copyright (C) 2020 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/>.
+
+// { dg-do run { target c++11 } }
+
+#include <set>
+#include <string>
+
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+using Cmp = std::less<std::string>;
+
+using __gnu_test::uneq_allocator;
+
+void test01()
+{
+  typedef uneq_allocator<std::string> alloc_type;
+  typedef std::set<std::string, Cmp, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  const char* str = "A long enough string to require dynamic allocation";
+  v1 = { str };
+
+  alloc_type a2(2);
+  test_type v2(std::move(v1), a2);
+
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(2 == v2.get_allocator().get_personality());
+
+  VERIFY( v1.count(str) == 0 );
+  VERIFY( v2.count(str) == 1 );
+}
+
+
+int main()
+{
+  test01();
+  return 0;
+}