2009-08-24 Chris Jefferson <chris@bubblescope.net>

	* include/stl_algo.h (__unguarded_partition_pivot,
	__move_median_first): New.
	(__insertion_sort, __unguarded_insertion_sort): Adjust for move-only
	types.
	(__unguarded_linear_insert): Assume always inserting value at __last.
	(__unguarded_partition): Take pivot by reference.
	(__introsort_loop, __introselect) : Use __unguarded_partition_pivot.
	* testsuite/25_algorithms/nth_element/moveable.cc : Enable.

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

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 56bbffa..f60c2b4 100644 (file)
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,14 @@
+2009-08-24  Chris Jefferson  <chris@bubblescope.net>
+
+       * include/stl_algo.h (__unguarded_partition_pivot,
+       __move_median_first): New.
+       (__insertion_sort, __unguarded_insertion_sort): Adjust for move-only
+       types.
+       (__unguarded_linear_insert): Assume always inserting value at __last.
+       (__unguarded_partition): Take pivot by reference.
+       (__introsort_loop, __introselect) : Use __unguarded_partition_pivot.
+       * testsuite/25_algorithms/nth_element/moveable.cc : Enable.
+
 2009-08-23  Ralf Wildenhues  <Ralf.Wildenhues@gmx.de>
 
        * libsupc++/Makefile.am (LTCOMPILE): Expand $(LIBTOOLFLAGS)

diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 6418ebf..a745295 100644 (file)
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -136,6 +136,56 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
        return __b;
     }
 
+  /// Swaps the median value of *__a, *__b and *__c to *__a
+  template<typename _Iterator>
+    void
+    __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c)
+    {
+      // concept requirements
+      __glibcxx_function_requires(_LessThanComparableConcept<
+           typename iterator_traits<_Iterator>::value_type>)
+
+      if (*__a < *__b)
+       {
+         if (*__b < *__c)
+           std::iter_swap(__a, __b);
+         else if (*__a < *__c)
+           std::iter_swap(__a, __c);
+       }
+      else if (*__a < *__c)
+       return;
+      else if (*__b < *__c)
+       std::iter_swap(__a, __c);
+      else
+       std::iter_swap(__a, __b);
+    }
+
+  /// Swaps the median value of *__a, *__b and *__c under __comp to *__a
+  template<typename _Iterator, typename _Compare>
+    void
+    __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c,
+                       _Compare __comp)
+    {
+      // concept requirements
+      __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
+           typename iterator_traits<_Iterator>::value_type,
+           typename iterator_traits<_Iterator>::value_type>)
+
+      if (__comp(*__a, *__b))
+       {
+         if (__comp(*__b, *__c))
+           std::iter_swap(__a, __b);
+         else if (__comp(*__a, *__c))
+           std::iter_swap(__a, __c);
+       }
+      else if (__comp(*__a, *__c))
+       return;
+      else if (__comp(*__b, *__c))
+       std::iter_swap(__a, __c);
+      else
+       std::iter_swap(__a, __b);
+    }
+
   // for_each
 
   /// This is an overload used by find() for the Input Iterator case.
@@ -2058,36 +2108,40 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
     }
 
   /// This is a helper function for the sort routine.
-  template<typename _RandomAccessIterator, typename _Tp>
+  template<typename _RandomAccessIterator>
     void
-    __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val)
+    __unguarded_linear_insert(_RandomAccessIterator __last)
     {
+      typename iterator_traits<_RandomAccessIterator>::value_type
+       __val = _GLIBCXX_MOVE(*__last);
       _RandomAccessIterator __next = __last;
       --__next;
       while (__val < *__next)
        {
-         *__last = *__next;
+         *__last = _GLIBCXX_MOVE(*__next);
          __last = __next;
          --__next;
        }
-      *__last = __val;
+      *__last = _GLIBCXX_MOVE(__val);
     }
 
   /// This is a helper function for the sort routine.
-  template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
+  template<typename _RandomAccessIterator, typename _Compare>
     void
-    __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val,
+    __unguarded_linear_insert(_RandomAccessIterator __last,
                              _Compare __comp)
     {
+      typename iterator_traits<_RandomAccessIterator>::value_type
+       __val = _GLIBCXX_MOVE(*__last);
       _RandomAccessIterator __next = __last;
       --__next;
       while (__comp(__val, *__next))
        {
-         *__last = *__next;
+         *__last = _GLIBCXX_MOVE(*__next);
          __last = __next;
          --__next;
        }
-      *__last = __val;
+      *__last = _GLIBCXX_MOVE(__val);
     }
 
   /// This is a helper function for the sort routine.
@@ -2101,15 +2155,15 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 
       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
        {
-         typename iterator_traits<_RandomAccessIterator>::value_type
-           __val = *__i;
-         if (__val < *__first)
+         if (*__i < *__first)
            {
-             std::copy_backward(__first, __i, __i + 1);
-             *__first = __val;
+             typename iterator_traits<_RandomAccessIterator>::value_type
+               __val = _GLIBCXX_MOVE(*__i);
+             _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
+             *__first = _GLIBCXX_MOVE(__val);
            }
          else
-           std::__unguarded_linear_insert(__i, __val);
+           std::__unguarded_linear_insert(__i);
        }
     }
 
@@ -2123,15 +2177,15 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 
       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
        {
-         typename iterator_traits<_RandomAccessIterator>::value_type
-           __val = *__i;
-         if (__comp(__val, *__first))
+         if (__comp(*__i, *__first))
            {
-             std::copy_backward(__first, __i, __i + 1);
-             *__first = __val;
+             typename iterator_traits<_RandomAccessIterator>::value_type
+               __val = _GLIBCXX_MOVE(*__i);
+             _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
+             *__first = _GLIBCXX_MOVE(__val);
            }
          else
-           std::__unguarded_linear_insert(__i, __val, __comp);
+           std::__unguarded_linear_insert(__i, __comp);
        }
     }
 
@@ -2145,7 +2199,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
        _ValueType;
 
       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
-       std::__unguarded_linear_insert(__i, _ValueType(*__i));
+       std::__unguarded_linear_insert(__i);
     }
 
   /// This is a helper function for the sort routine.
@@ -2158,7 +2212,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
        _ValueType;
 
       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
-       std::__unguarded_linear_insert(__i, _ValueType(*__i), __comp);
+       std::__unguarded_linear_insert(__i, __comp);
     }
 
   /**
@@ -2202,7 +2256,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
   template<typename _RandomAccessIterator, typename _Tp>
     _RandomAccessIterator
     __unguarded_partition(_RandomAccessIterator __first,
-                         _RandomAccessIterator __last, _Tp __pivot)
+                         _RandomAccessIterator __last, const _Tp& __pivot)
     {
       while (true)
        {
@@ -2223,7 +2277,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
     _RandomAccessIterator
     __unguarded_partition(_RandomAccessIterator __first,
                          _RandomAccessIterator __last,
-                         _Tp __pivot, _Compare __comp)
+                         const _Tp& __pivot, _Compare __comp)
     {
       while (true)
        {
@@ -2239,6 +2293,29 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
        }
     }
 
+  /// This is a helper function...
+  template<typename _RandomAccessIterator>
+    inline _RandomAccessIterator
+    __unguarded_partition_pivot(_RandomAccessIterator __first,
+                               _RandomAccessIterator __last)
+    {
+      _RandomAccessIterator __mid = __first + (__last - __first) / 2;
+      std::__move_median_first(__first, __mid, (__last - 1));
+      return std::__unguarded_partition(__first + 1, __last, *__first);
+    }
+
+
+  /// This is a helper function...
+  template<typename _RandomAccessIterator, typename _Compare>
+    inline _RandomAccessIterator
+    __unguarded_partition_pivot(_RandomAccessIterator __first,
+                               _RandomAccessIterator __last, _Compare __comp)
+    {
+      _RandomAccessIterator __mid = __first + (__last - __first) / 2;
+      std::__move_median_first(__first, __mid, (__last - 1), __comp);
+      return std::__unguarded_partition(__first + 1, __last, *__first, __comp);
+    }
+
   /// This is a helper function for the sort routine.
   template<typename _RandomAccessIterator, typename _Size>
     void
@@ -2246,9 +2323,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
                     _RandomAccessIterator __last,
                     _Size __depth_limit)
     {
-      typedef typename iterator_traits<_RandomAccessIterator>::value_type
-       _ValueType;
-
       while (__last - __first > int(_S_threshold))
        {
          if (__depth_limit == 0)
@@ -2258,14 +2332,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
            }
          --__depth_limit;
          _RandomAccessIterator __cut =
-           std::__unguarded_partition(__first, __last,
-                                      _ValueType(std::__median(*__first,
-                                                               *(__first
-                                                                 + (__last
-                                                                    - __first)
-                                                                 / 2),
-                                                               *(__last
-                                                                 - 1))));
+           std::__unguarded_partition_pivot(__first, __last);
          std::__introsort_loop(__cut, __last, __depth_limit);
          __last = __cut;
        }
@@ -2278,9 +2345,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
                     _RandomAccessIterator __last,
                     _Size __depth_limit, _Compare __comp)
     {
-      typedef typename iterator_traits<_RandomAccessIterator>::value_type
-       _ValueType;
-
       while (__last - __first > int(_S_threshold))
        {
          if (__depth_limit == 0)
@@ -2290,15 +2354,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
            }
          --__depth_limit;
          _RandomAccessIterator __cut =
-           std::__unguarded_partition(__first, __last,
-                                      _ValueType(std::__median(*__first,
-                                                               *(__first
-                                                                 + (__last
-                                                                    - __first)
-                                                                 / 2),
-                                                               *(__last - 1),
-                                                               __comp)),
-                                      __comp);
+           std::__unguarded_partition_pivot(__first, __last, __comp);
          std::__introsort_loop(__cut, __last, __depth_limit, __comp);
          __last = __cut;
        }
@@ -2349,14 +2405,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
            }
          --__depth_limit;
          _RandomAccessIterator __cut =
-           std::__unguarded_partition(__first, __last,
-                                      _ValueType(std::__median(*__first,
-                                                               *(__first
-                                                                 + (__last
-                                                                    - __first)
-                                                                 / 2),
-                                                               *(__last
-                                                                 - 1))));
+           std::__unguarded_partition_pivot(__first, __last);
          if (__cut <= __nth)
            __first = __cut;
          else
@@ -2385,15 +2434,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
            }
          --__depth_limit;
          _RandomAccessIterator __cut =
-           std::__unguarded_partition(__first, __last,
-                                      _ValueType(std::__median(*__first,
-                                                               *(__first
-                                                                 + (__last
-                                                                    - __first)
-                                                                 / 2),
-                                                               *(__last - 1),
-                                                               __comp)),
-                                      __comp);
+           std::__unguarded_partition_pivot(__first, __last, __comp);
          if (__cut <= __nth)
            __first = __cut;
          else

diff --git a/libstdc++-v3/testsuite/25_algorithms/nth_element/moveable.cc b/libstdc++-v3/testsuite/25_algorithms/nth_element/moveable.cc
index cb72949..005f6ec 100644 (file)
--- a/libstdc++-v3/testsuite/25_algorithms/nth_element/moveable.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/nth_element/moveable.cc
@@ -1,4 +1,3 @@
-// { dg-require-rvalref "" }
 // { dg-options "-std=gnu++0x" }
 
 // Copyright (C) 2005, 2007, 2009 Free Software Foundation, Inc.