2011-03-09 Paolo Carlini <paolo.carlini@oracle.com>

	* testsuite/util/testsuite_rvalref.h: Minor tweaks.

2011-03-09  Jonathan Wakely  <redi@gcc.gnu.org>
	    Chris Jefferson  <chris@bubblescope.net>
	    Paolo Carlini  <paolo.carlini@oracle.com>

	* testsuite/util/testsuite_rvalref.h (rvalstruct_compare_by_value):
	New.
	* testsuite/25_algorithms/sort_heap/check_compare_by_value.cc:
	Likewise.
	* testsuite/25_algorithms/partial_sort/check_compare_by_value:
	Likewise.
	* testsuite/25_algorithms/stable_sort/check_compare_by_value.cc:
	Likewise.
	* testsuite/25_algorithms/sort/check_compare_by_value: Likewise.

2011-03-09  Chris Jefferson  <chris@bubblescope.net>

	PR libstdc++/48038
	* include/bits/stl_algo.h (__merge_backward): Rename to
	__move_merge_backward and change to always move rather than copy.
	(__move_merge): New function similar to std::merge except values
	are moved instead of copied.
	(__merge_adaptive, __merge_sort_loop): Change from using std::merge
	and __merge_backward to __move_merge and __move_merge_backward.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@170827 138bc75d-0d04-0410-961f-82ee72b054a4

7 files changed, 573 insertions, 92 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 44c87bece9f..6c3f1d34cda 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,10 +1,38 @@
+2011-03-09  Paolo Carlini  <paolo.carlini@oracle.com>
+
+	* testsuite/util/testsuite_rvalref.h: Minor tweaks.
+
+2011-03-09  Jonathan Wakely  <redi@gcc.gnu.org>
+	    Chris Jefferson  <chris@bubblescope.net>
+	    Paolo Carlini  <paolo.carlini@oracle.com>
+
+	* testsuite/util/testsuite_rvalref.h (rvalstruct_compare_by_value):
+	New.
+	* testsuite/25_algorithms/sort_heap/check_compare_by_value.cc:
+	Likewise.
+	* testsuite/25_algorithms/partial_sort/check_compare_by_value:
+	Likewise.
+	* testsuite/25_algorithms/stable_sort/check_compare_by_value.cc:
+	Likewise.
+	* testsuite/25_algorithms/sort/check_compare_by_value: Likewise.
+
+2011-03-09  Chris Jefferson  <chris@bubblescope.net>
+
+	PR libstdc++/48038
+	* include/bits/stl_algo.h (__merge_backward): Rename to
+	__move_merge_backward and change to always move rather than copy.
+	(__move_merge): New function similar to std::merge except values
+	are moved instead of copied.
+	(__merge_adaptive, __merge_sort_loop): Change from using std::merge
+	and __merge_backward to __move_merge and __move_merge_backward.
+
 2011-03-07  Jason Merrill  <jason@redhat.com>
 
 	* testsuite/20_util/ratio/cons/cons_overflow_neg.cc: Adjust
 	expected errors.
 
 2011-03-07  Benjamin Kosnik  <bkoz@redhat.com>
-            Matthias Klose  <doko@ubuntu.com>
+	    Matthias Klose  <doko@ubuntu.com>
 	    Jonathan Wakely  <redi@gcc.gnu.org>
 
 	PR libstdc++/47145
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 707021bdc8f..5fc561e25e9 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -2720,32 +2720,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
 	   typename _BidirectionalIterator3>
     _BidirectionalIterator3
-    __merge_backward(_BidirectionalIterator1 __first1,
-		     _BidirectionalIterator1 __last1,
-		     _BidirectionalIterator2 __first2,
-		     _BidirectionalIterator2 __last2,
-		     _BidirectionalIterator3 __result)
+    __move_merge_backward(_BidirectionalIterator1 __first1,
+			  _BidirectionalIterator1 __last1,
+			  _BidirectionalIterator2 __first2,
+			  _BidirectionalIterator2 __last2,
+			  _BidirectionalIterator3 __result)
     {
       if (__first1 == __last1)
-	return std::copy_backward(__first2, __last2, __result);
+	return _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
       if (__first2 == __last2)
-	return std::copy_backward(__first1, __last1, __result);
+	return _GLIBCXX_MOVE_BACKWARD3(__first1, __last1, __result);
       --__last1;
       --__last2;
       while (true)
 	{
 	  if (*__last2 < *__last1)
 	    {
-	      *--__result = *__last1;
+	      *--__result = _GLIBCXX_MOVE(*__last1);
 	      if (__first1 == __last1)
-		return std::copy_backward(__first2, ++__last2, __result);
+		return _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
 	      --__last1;
 	    }
 	  else
 	    {
-	      *--__result = *__last2;
+	      *--__result = _GLIBCXX_MOVE(*__last2);
 	      if (__first2 == __last2)
-		return std::copy_backward(__first1, ++__last1, __result);
+		return _GLIBCXX_MOVE_BACKWARD3(__first1, ++__last1, __result);
 	      --__last2;
 	    }
 	}
@@ -2755,39 +2755,94 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
 	   typename _BidirectionalIterator3, typename _Compare>
     _BidirectionalIterator3
-    __merge_backward(_BidirectionalIterator1 __first1,
-		     _BidirectionalIterator1 __last1,
-		     _BidirectionalIterator2 __first2,
-		     _BidirectionalIterator2 __last2,
-		     _BidirectionalIterator3 __result,
-		     _Compare __comp)
+    __move_merge_backward(_BidirectionalIterator1 __first1,
+			  _BidirectionalIterator1 __last1,
+			  _BidirectionalIterator2 __first2,
+			  _BidirectionalIterator2 __last2,
+			  _BidirectionalIterator3 __result,
+			  _Compare __comp)
     {
       if (__first1 == __last1)
-	return std::copy_backward(__first2, __last2, __result);
+	return _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
       if (__first2 == __last2)
-	return std::copy_backward(__first1, __last1, __result);
+	return _GLIBCXX_MOVE_BACKWARD3(__first1, __last1, __result);
       --__last1;
       --__last2;
       while (true)
 	{
 	  if (__comp(*__last2, *__last1))
 	    {
-	      *--__result = *__last1;
+	      *--__result = _GLIBCXX_MOVE(*__last1);
 	      if (__first1 == __last1)
-		return std::copy_backward(__first2, ++__last2, __result);
+		return _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
 	      --__last1;
 	    }
 	  else
 	    {
-	      *--__result = *__last2;
+	      *--__result = _GLIBCXX_MOVE(*__last2);
 	      if (__first2 == __last2)
-		return std::copy_backward(__first1, ++__last1, __result);
+		return _GLIBCXX_MOVE_BACKWARD3(__first1, ++__last1, __result);
 	      --__last2;
 	    }
 	}
     }
 
   /// This is a helper function for the merge routines.
+  template<typename _InputIterator1, typename _InputIterator2,
+	   typename _OutputIterator>
+    _OutputIterator
+    __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
+		 _InputIterator2 __first2, _InputIterator2 __last2,
+		 _OutputIterator __result)
+    {
+      while (__first1 != __last1 && __first2 != __last2)
+	{
+	  if (*__first2 < *__first1)
+	    {
+	      *__result = _GLIBCXX_MOVE(*__first2);
+	      ++__first2;
+	    }
+	  else
+	    {
+	      *__result = _GLIBCXX_MOVE(*__first1);
+	      ++__first1;
+	    }
+	  ++__result;
+	}
+      return _GLIBCXX_MOVE3(__first2, __last2,
+			    _GLIBCXX_MOVE3(__first1, __last1,
+					   __result));
+    }
+
+  /// This is a helper function for the merge routines.
+  template<typename _InputIterator1, typename _InputIterator2,
+	   typename _OutputIterator, typename _Compare>
+    _OutputIterator
+    __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
+		 _InputIterator2 __first2, _InputIterator2 __last2,
+		 _OutputIterator __result, _Compare __comp)
+    {
+      while (__first1 != __last1 && __first2 != __last2)
+	{
+	  if (__comp(*__first2, *__first1))
+	    {
+	      *__result = _GLIBCXX_MOVE(*__first2);
+	      ++__first2;
+	    }
+	  else
+	    {
+	      *__result = _GLIBCXX_MOVE(*__first1);
+	      ++__first1;
+	    }
+	  ++__result;
+	}
+      return _GLIBCXX_MOVE3(__first2, __last2,
+			    _GLIBCXX_MOVE3(__first1, __last1,
+					   __result));
+    }
+
+
+  /// This is a helper function for the merge routines.
   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
 	   typename _Distance>
     _BidirectionalIterator1
@@ -2832,20 +2887,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       if (__len1 <= __len2 && __len1 <= __buffer_size)
 	{
 	  _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
-	  _GLIBCXX_STD_A::merge(_GLIBCXX_MAKE_MOVE_ITERATOR(__buffer),
-				_GLIBCXX_MAKE_MOVE_ITERATOR(__buffer_end),
-				_GLIBCXX_MAKE_MOVE_ITERATOR(__middle),
-				_GLIBCXX_MAKE_MOVE_ITERATOR(__last),
-				__first);
+	  std::__move_merge(__buffer, __buffer_end, __middle, __last, __first);
 	}
       else if (__len2 <= __buffer_size)
 	{
 	  _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
-	  std::__merge_backward(_GLIBCXX_MAKE_MOVE_ITERATOR(__first),
-				_GLIBCXX_MAKE_MOVE_ITERATOR(__middle),
-				_GLIBCXX_MAKE_MOVE_ITERATOR(__buffer),
-				_GLIBCXX_MAKE_MOVE_ITERATOR(__buffer_end),
-				__last);
+	  std::__move_merge_backward(__first, __middle, __buffer,
+				    __buffer_end, __last);
 	}
       else
 	{
@@ -2895,20 +2943,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       if (__len1 <= __len2 && __len1 <= __buffer_size)
 	{
 	  _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
-	  _GLIBCXX_STD_A::merge(_GLIBCXX_MAKE_MOVE_ITERATOR(__buffer),
-				_GLIBCXX_MAKE_MOVE_ITERATOR(__buffer_end),
-				_GLIBCXX_MAKE_MOVE_ITERATOR(__middle),
-				_GLIBCXX_MAKE_MOVE_ITERATOR(__last),
-				__first, __comp);
+	  std::__move_merge(__buffer, __buffer_end, __middle, __last,
+			    __first, __comp);
 	}
       else if (__len2 <= __buffer_size)
 	{
 	  _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
-	  std::__merge_backward(_GLIBCXX_MAKE_MOVE_ITERATOR(__first),
-				_GLIBCXX_MAKE_MOVE_ITERATOR(__middle),
-				_GLIBCXX_MAKE_MOVE_ITERATOR(__buffer),
-				_GLIBCXX_MAKE_MOVE_ITERATOR(__buffer_end),
-				__last,__comp);
+	  std::__move_merge_backward(__first, __middle, __buffer, __buffer_end,
+				     __last, __comp);
 	}
       else
 	{
@@ -3157,23 +3199,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       while (__last - __first >= __two_step)
 	{
-	  __result = _GLIBCXX_STD_A::merge(
-			_GLIBCXX_MAKE_MOVE_ITERATOR(__first),
-			_GLIBCXX_MAKE_MOVE_ITERATOR(__first + __step_size),
-			_GLIBCXX_MAKE_MOVE_ITERATOR(__first + __step_size),
-			_GLIBCXX_MAKE_MOVE_ITERATOR(__first + __two_step),
-			__result);
+	  __result = std::__move_merge(__first, __first + __step_size,
+				       __first + __step_size,
+				       __first + __two_step, __result);
 	  __first += __two_step;
 	}
 
       __step_size = std::min(_Distance(__last - __first), __step_size);
-      _GLIBCXX_STD_A::merge(_GLIBCXX_MAKE_MOVE_ITERATOR(__first),
-			    _GLIBCXX_MAKE_MOVE_ITERATOR(__first +
-							__step_size),
-			    _GLIBCXX_MAKE_MOVE_ITERATOR(__first +
-							__step_size),
-			    _GLIBCXX_MAKE_MOVE_ITERATOR(__last),
-			    __result);
+      std::__move_merge(__first, __first + __step_size,
+			__first + __step_size, __last, __result);
     }
 
   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
@@ -3188,23 +3222,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       while (__last - __first >= __two_step)
 	{
-	  __result = _GLIBCXX_STD_A::merge(
-			_GLIBCXX_MAKE_MOVE_ITERATOR(__first),
-			_GLIBCXX_MAKE_MOVE_ITERATOR(__first + __step_size),
-			_GLIBCXX_MAKE_MOVE_ITERATOR(__first + __step_size),
-			_GLIBCXX_MAKE_MOVE_ITERATOR(__first + __two_step),
-			__result, __comp);
+	  __result = std::__move_merge(__first, __first + __step_size,
+				       __first + __step_size,
+				       __first + __two_step,
+				       __result, __comp);
 	  __first += __two_step;
 	}
       __step_size = std::min(_Distance(__last - __first), __step_size);
 
-      _GLIBCXX_STD_A::merge(_GLIBCXX_MAKE_MOVE_ITERATOR(__first),
-			    _GLIBCXX_MAKE_MOVE_ITERATOR(__first +
-							__step_size),
-			    _GLIBCXX_MAKE_MOVE_ITERATOR(__first +
-							__step_size),
-			    _GLIBCXX_MAKE_MOVE_ITERATOR(__last),
-			    __result, __comp);
+      std::__move_merge(__first,__first + __step_size,
+			__first + __step_size, __last, __result, __comp);
     }
 
   template<typename _RandomAccessIterator, typename _Distance>
diff --git a/libstdc++-v3/testsuite/25_algorithms/partial_sort/check_compare_by_value.cc b/libstdc++-v3/testsuite/25_algorithms/partial_sort/check_compare_by_value.cc
new file mode 100644
index 00000000000..e6bb20f6b25
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/partial_sort/check_compare_by_value.cc
@@ -0,0 +1,93 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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/>.
+
+// 25.3.1.3 [lib.partial.sort]
+
+#undef _GLIBCXX_CONCEPT_CHECKS
+
+// XXX FIXME:  parallel-mode should deal correctly with moveable-only types
+// per C++0x, at minimum smoothly fall back to serial.
+#undef _GLIBCXX_PARALLEL
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+#include <testsuite_rvalref.h>
+
+using __gnu_test::test_container;
+using __gnu_test::random_access_iterator_wrapper;
+
+typedef __gnu_test::rvalstruct_compare_by_value V;
+typedef test_container<V, random_access_iterator_wrapper> Container;
+
+void
+test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  V s1[] = { 10, 20, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 
+	     17, 8, 18, 9, 19 };
+  const int N = sizeof(s1) / sizeof(V);
+  Container con(s1, s1 + N);
+  std::partial_sort(con.begin(), con.begin() + 10, con.end());
+  VERIFY( s1[0].ok );
+  for(int i = 1; i < 10; ++i)
+    VERIFY( s1[i].val > s1[i - 1].val && s1[i].ok );
+  for(int i = 10; i < N; ++i)
+    VERIFY( s1[i].val > s1[9].val && s1[i].ok );
+
+}
+
+void
+test02()
+{
+  bool test __attribute__((unused)) = true;
+
+  V s1[] = { 10, 20, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 
+	     17, 8, 18, 9, 19 };
+  const int N = sizeof(s1) / sizeof(V);
+  Container con(s1, s1 + N);
+  std::partial_sort(con.begin(), con.begin() + 10, con.end(),
+		    __gnu_test::order);
+  VERIFY( s1[0].ok );
+  for(int i = 1; i < 10; ++i)
+    VERIFY( s1[i].val > s1[i - 1].val && s1[i].ok );
+  for(int i = 10; i < N; ++i)
+    VERIFY( s1[i].val > s1[9].val && s1[i].ok );
+}
+
+void
+test03()
+{
+  bool test __attribute__((unused)) = true;
+
+  V vvs[] = { 2, 0 };
+  std::partial_sort(vvs, vvs + 2, vvs + 2);
+  VERIFY( vvs[0].ok && vvs[0].val == 0 );
+  VERIFY( vvs[1].ok && vvs[1].val == 2 );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  test03();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/sort/check_compare_by_value.cc b/libstdc++-v3/testsuite/25_algorithms/sort/check_compare_by_value.cc
new file mode 100644
index 00000000000..ac3e2f7d4ef
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/sort/check_compare_by_value.cc
@@ -0,0 +1,86 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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/>.
+
+// 25.3.1 algorithms, sort
+
+#undef _GLIBCXX_CONCEPT_CHECKS
+
+// XXX FIXME:  parallel-mode should deal correctly with moveable-only types
+// per C++0x, at minimum smoothly fall back to serial.
+#undef _GLIBCXX_PARALLEL
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+#include <testsuite_rvalref.h>
+
+using __gnu_test::test_container;
+using __gnu_test::random_access_iterator_wrapper;
+
+typedef __gnu_test::rvalstruct_compare_by_value V;
+typedef test_container<V, random_access_iterator_wrapper> Container;
+
+void
+test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  V s1[] = { 10, 20, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 
+	     17, 8, 18, 9, 19 };
+  const int N = sizeof(s1) / sizeof(V);
+  Container con(s1, s1 + N);
+  std::sort(con.begin(), con.end());
+  VERIFY( s1[0].ok );
+  for(int i = 1; i < N; ++i)
+    VERIFY( s1[i].val > s1[i - 1].val && s1[i].ok );
+}
+
+void
+test02()
+{
+  bool test __attribute__((unused)) = true;
+
+  V s1[] = { 10, 20, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 
+	     17, 8, 18, 9, 19 };
+  const int N = sizeof(s1) / sizeof(V);
+  Container con(s1, s1 + N);
+  std::sort(con.begin(), con.end(), __gnu_test::order);
+  VERIFY( s1[0].ok );
+  for(int i = 1; i < N; ++i)
+    VERIFY( s1[i].val > s1[i - 1].val && s1[i].ok );
+}
+
+void test03()
+{
+  bool test __attribute__((unused)) = true;
+
+  V vvs[] = { 2, 0 };
+  std::sort(vvs, vvs + 2);
+  VERIFY( vvs[0].ok && vvs[0].val == 0 );
+  VERIFY( vvs[1].ok && vvs[1].val == 2 );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  test03();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/sort_heap/check_compare_by_value.cc b/libstdc++-v3/testsuite/25_algorithms/sort_heap/check_compare_by_value.cc
new file mode 100644
index 00000000000..32cff8fd854
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/sort_heap/check_compare_by_value.cc
@@ -0,0 +1,88 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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/>.
+
+#undef _GLIBCXX_CONCEPT_CHECKS
+
+// XXX FIXME:  parallel-mode should deal correctly with moveable-only types
+// per C++0x, at minimum smoothly fall back to serial.
+#undef _GLIBCXX_PARALLEL
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+#include <testsuite_rvalref.h>
+
+using __gnu_test::test_container;
+using __gnu_test::random_access_iterator_wrapper;
+
+typedef __gnu_test::rvalstruct_compare_by_value V;
+typedef test_container<V, random_access_iterator_wrapper> Container;
+
+void
+test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  V s1[] = { 10, 20, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 
+	     17, 8, 18, 9, 19 };
+  const int N = sizeof(s1) / sizeof(V);
+  Container con(s1, s1 + N);
+  std::make_heap(con.begin(), con.end());
+  std::sort_heap(con.begin(), con.end());
+  VERIFY( s1[0].ok );
+  for(int i = 1; i < N; ++i)
+    VERIFY( s1[i].val > s1[i - 1].val && s1[i].ok );
+}
+
+void
+test02()
+{
+  bool test __attribute__((unused)) = true;
+
+  V s1[] = { 10, 20, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 
+	     17, 8, 18, 9, 19 };
+  const int N = sizeof(s1) / sizeof(V);
+  Container con(s1, s1 + N);
+  std::make_heap(con.begin(), con.end(), __gnu_test::order);
+  std::sort_heap(con.begin(), con.end(), __gnu_test::order);
+  VERIFY( s1[0].ok );
+  for(int i = 1; i < N; ++i)
+    VERIFY( s1[i].val > s1[i - 1].val && s1[i].ok );
+}
+
+void
+test03()
+{
+  bool test __attribute__((unused)) = true;
+
+  V vvs[] = { 2, 0 };
+  std::make_heap(vvs, vvs + 2);
+  std::sort_heap(vvs, vvs + 2);
+  VERIFY( vvs[0].ok && vvs[0].val == 0 );
+  VERIFY( vvs[1].ok && vvs[1].val == 2 );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  test03();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/stable_sort/check_compare_by_value.cc b/libstdc++-v3/testsuite/25_algorithms/stable_sort/check_compare_by_value.cc
new file mode 100644
index 00000000000..817468c1685
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/stable_sort/check_compare_by_value.cc
@@ -0,0 +1,90 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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/>.
+
+// 25.3.1.2 [lib.stable.sort]
+
+#undef _GLIBCXX_CONCEPT_CHECKS
+
+// XXX FIXME:  parallel-mode should deal correctly with moveable-only types
+// per C++0x, at minimum smoothly fall back to serial.
+#undef _GLIBCXX_PARALLEL
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+#include <testsuite_rvalref.h>
+
+using __gnu_test::test_container;
+using __gnu_test::random_access_iterator_wrapper;
+
+typedef __gnu_test::rvalstruct_compare_by_value V;
+typedef test_container<V, random_access_iterator_wrapper> Container;
+
+void
+test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  V s1[] = { 10, 20, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 
+	     17, 8, 18, 9, 19 };
+  const int N = sizeof(s1) / sizeof(V);
+  Container con(s1, s1 + N);
+  std::stable_sort(con.begin(), con.end());
+  VERIFY( s1[0].ok );
+  for(int i = 1; i < N; ++i)
+  {
+    VERIFY( s1[i].val > s1[i - 1].val);
+    VERIFY( s1[i].ok );
+  }
+}
+
+void
+test02()
+{
+  bool test __attribute__((unused)) = true;
+
+  V s1[] = { 10, 20, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 
+	     17, 8, 18, 9, 19 };
+  const int N = sizeof(s1) / sizeof(V);
+  Container con(s1, s1 + N);
+  std::stable_sort(con.begin(), con.end(), __gnu_test::order);
+  VERIFY( s1[0].ok );
+  for(int i = 1; i < N; ++i)
+    VERIFY( s1[i].val > s1[i - 1].val && s1[i].ok );
+}
+
+void
+test03()
+{
+  bool test __attribute__((unused)) = true;
+
+  V vvs[] = { 2, 0 };
+  std::stable_sort(vvs, vvs + 2);
+  VERIFY( vvs[0].ok && vvs[0].val == 0 );
+  VERIFY( vvs[1].ok && vvs[1].val == 2 );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  test03();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/util/testsuite_rvalref.h b/libstdc++-v3/testsuite/util/testsuite_rvalref.h
index acf25da503a..8e37bbdb097 100644
--- a/libstdc++-v3/testsuite/util/testsuite_rvalref.h
+++ b/libstdc++-v3/testsuite/util/testsuite_rvalref.h
@@ -24,10 +24,10 @@
 #define _GLIBCXX_TESTSUITE_RVALREF_H 1
 
 #include <testsuite_hooks.h>
+#include <bits/functional_hash.h>
 
 namespace __gnu_test
 {
-
   // This class is designed to test libstdc++'s template-based rvalue
   // reference support. It should fail at compile-time if there is an
   // attempt to copy it.
@@ -53,8 +53,9 @@ namespace __gnu_test
     rvalstruct(const rvalstruct&) = delete;
 
     rvalstruct(rvalstruct&& in)
-    { 
-      VERIFY(in.valid == true);
+    {
+      bool test __attribute__((unused)) = true;
+      VERIFY( in.valid == true );
       val = in.val;
       in.valid = false;
       valid = true;
@@ -65,8 +66,9 @@ namespace __gnu_test
 
     rvalstruct&
     operator=(rvalstruct&& in)
-    { 
-      VERIFY(in.valid == true);
+    {
+      bool test __attribute__((unused)) = true;
+      VERIFY( in.valid == true );
       val = in.val;
       in.valid = false;
       valid = true;
@@ -84,8 +86,9 @@ namespace __gnu_test
 
   void
   swap(rvalstruct& lhs, rvalstruct& rhs)
-  {  
-    VERIFY(lhs.valid && rhs.valid);
+  {
+    bool test __attribute__((unused)) = true;
+    VERIFY( lhs.valid && rhs.valid );
     int temp = lhs.val;
     lhs.val = rhs.val;
     rhs.val = temp;
@@ -108,14 +111,16 @@ namespace __gnu_test
     { }
 
     copycounter(const copycounter& in) : val(in.val), valid(true)
-    { 
-      VERIFY(in.valid == true);
+    {
+      bool test __attribute__((unused)) = true;
+      VERIFY( in.valid == true );
       ++copycount;
     }
 
     copycounter(copycounter&& in)
-    { 
-      VERIFY(in.valid == true);
+    {
+      bool test __attribute__((unused)) = true;
+      VERIFY( in.valid == true );
       val = in.val;
       in.valid = false;
       valid = true;
@@ -131,8 +136,9 @@ namespace __gnu_test
 
     bool
     operator=(const copycounter& in) 
-    { 
-      VERIFY(in.valid == true);
+    {
+      bool test __attribute__((unused)) = true;
+      VERIFY( in.valid == true );
       ++copycount;
       val = in.val;
       valid = true;
@@ -141,7 +147,8 @@ namespace __gnu_test
 
     copycounter&
     operator=(copycounter&& in)
-    { 
+    {
+      bool test __attribute__((unused)) = true;
       VERIFY(in.valid == true);
       val = in.val;
       in.valid = false;
@@ -165,22 +172,85 @@ namespace __gnu_test
 
   inline void
   swap(copycounter& lhs, copycounter& rhs)
-  {  
-    VERIFY(lhs.valid && rhs.valid);
+  {
+    bool test __attribute__((unused)) = true;
+    VERIFY( lhs.valid && rhs.valid );
     int temp = lhs.val;
     lhs.val = rhs.val;
     rhs.val = temp;
   }
-  
-} // namespace __gnu_test
 
-#ifdef __GXX_EXPERIMENTAL_CXX0X__
+  // In the occasion of libstdc++/48038.
+  struct rvalstruct_compare_by_value
+  {
+    int val;
+    bool ok;
 
-#include <bits/functional_hash.h>
+    rvalstruct_compare_by_value(int v)
+    : val(v), ok(true) { }
+
+    rvalstruct_compare_by_value(const rvalstruct_compare_by_value& rh)
+    : val(rh.val), ok(rh.ok)
+    {
+      bool test __attribute__((unused)) = true;
+      VERIFY(rh.ok);
+    }
+
+    rvalstruct_compare_by_value&
+    operator=(const rvalstruct_compare_by_value& rh)
+    {
+      bool test __attribute__((unused)) = true;
+      VERIFY( rh.ok );
+      val = rh.val;
+      ok = rh.ok;
+      return *this;
+    }
+
+    rvalstruct_compare_by_value(rvalstruct_compare_by_value&& rh)
+    : val(rh.val), ok(rh.ok)
+    {
+      bool test __attribute__((unused)) = true;
+      VERIFY( rh.ok );
+      rh.ok = false;
+    }
+
+    rvalstruct_compare_by_value&
+    operator=(rvalstruct_compare_by_value&& rh)
+    {
+      bool test __attribute__((unused)) = true;
+      VERIFY( rh.ok );
+      val = rh.val;
+      ok = rh.ok;
+      rh.ok = false;
+      return *this;
+    }
+  };
+
+  inline bool
+  operator<(rvalstruct_compare_by_value lh,
+	    rvalstruct_compare_by_value rh)
+  {
+    bool test __attribute__((unused)) = true;
+    VERIFY( rh.ok );
+    VERIFY( lh.ok );
+    return lh.val < rh.val;
+  }
+
+  inline bool
+  order(rvalstruct_compare_by_value lh,
+	rvalstruct_compare_by_value rh)
+  {
+    bool test __attribute__((unused)) = true;
+    VERIFY( rh.ok );
+    VERIFY( lh.ok );
+    return lh.val < rh.val;
+  }
+
+} // namespace __gnu_test
 
 namespace std
 {
-  /// std::hash specialization for type_index.
+  /// std::hash specialization for __gnu_test::rvalstruct.
   template<>
     struct hash<__gnu_test::rvalstruct>
     {
@@ -192,6 +262,5 @@ namespace std
       { return __rvs.val; }
     };
 }
-#endif
 
 #endif // _GLIBCXX_TESTSUITE_TR1_H