This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[patch] : finish adding move symantics to <algorithm>


This patch finishes adding move symantics to <algorithm>, in particular to the sort functions and inplace_merge, as they all use each other and the same internal functions.

This one is slightly more intrusive than the others, and in particular introduces different algorithms for sorting moveable and non-moveable types.

Bootstrapped on powerpc-apple-darwin8.1.0

Chris
2005-05-30  Chris Jefferson  <chris@bubblescope.net>

	* include/bits/stl_algo.h (__stable_partition_adaptive, 
	__merge_sort_loop, __merge_backward, __rotate_adaptive, 
	__merge_adaptive) : Make rvalref aware.
	(__unguarded_linear_insert) : Remove unnecessary parameter, make 
	rvalref aware.
	(__unguarded_nocopy_partition, __unguarded_mid_partition,
	__introsort_partition, __move_merge) : New helper functions.
	(__insertion_sort) : Make rvalref aware, adapt to new
	__unguarded_linear_insert.
	(__unguarded_insertion_sort) : Adapt to new __unguarded_linear_insert.
	(__introsort_loop, nth_element) : Use __introsort_partition.
	* include/bits/stl_algobase.h (__move, __move_backward) : New.
	* include/bits/stl_tempbuf.h (_M_initalize_buffer) : Removed from
	_Temporary_buffer into own class, make rvalref aware.
	(_Temporary_buffer::_Temporary_buffer) : Use new _M_initalize_buffer, 
	remove old workaround.
	* include/bits/stl_uninitalized.h (__uninitalized_fill_n) : New.
	* testsuite/25_algorithms/inplace_merge/moveable.cc : New.
	* testsuite/25_algorithms/nth_element/moveable.cc : New.
	* testsuite/25_algorithms/partial_sort/moveable.cc : New.
	* testsuite/25_algorithms/partition/moveable.cc : Add stable_partition
	test.
	* testsuite/25_algorithms/sort/moveable.cc : New.
	* testsuite/25_algorithms/sort.cc : Move to...
	* testsuite/25_algorithms/sort/sort.cc : ...here.
	* testsuite/25_algorithms/stable_sort/moveable.cc : New.
	* testsuite/performance/25_algorithms/sort.cc : New.
	
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/include/bits/stl_algo.h libstdc++-v3/include/bits/stl_algo.h
--- libstdc++-v3.so_7.clean/include/bits/stl_algo.h	2005-05-25 13:38:47.000000000 +0100
+++ libstdc++-v3/include/bits/stl_algo.h	2005-05-28 12:18:24.000000000 +0100
@@ -1811,15 +1811,15 @@
 	  for ( ; __first != __last ; ++__first)
 	    if (__pred(*__first))
 	      {
-		*__result1 = *__first;
+		*__result1 = __gnu_cxx::__move(*__first);
 		++__result1;
 	      }
 	    else
 	      {
-		*__result2 = *__first;
+		*__result2 = __gnu_cxx::__move(*__first);
 		++__result2;
 	      }
-	  std::copy(__buffer, __result2, __result1);
+	  std::__move(__buffer, __result2, __result1);
 	  return __result1;
 	}
       else
@@ -1929,20 +1929,109 @@
    *  This is a helper function for the sort routine.
    *  @endif
   */
-  template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
-    void
-    __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val,
-			      _Compare __comp)
+  template<typename _RandomAccessIterator, typename _Compare>
+    inline void
+    __unguarded_linear_insert(_RandomAccessIterator __last, _Compare __comp)
     {
+      typename iterator_traits<_RandomAccessIterator>::value_type
+        __val(__gnu_cxx::__move(*__last));
       _RandomAccessIterator __next = __last;
       --__next;
       while (__comp(__val, *__next))
 	{
-	  *__last = *__next;
+	  *__last = __gnu_cxx::__move(*__next);
 	  __last = __next;
 	  --__next;
 	}
-      *__last = __val;
+      *__last = __gnu_cxx::__move(__val);
+    }
+
+  /**
+   *  @if maint
+   *  This is a helper function. It assumes __pivot is not in the range
+   *  [__first, __last).
+   *  @endif
+  */
+  template<typename _RandomAccessIterator, typename _Compare>
+    inline _RandomAccessIterator
+    __unguarded_nocopy_partition(_RandomAccessIterator __first,
+			  	 _RandomAccessIterator __last,
+			  	 _RandomAccessIterator __pivot, _Compare __comp)
+    {
+      while (true)
+	{
+	  while (__comp(*__first, *__pivot))
+	    ++__first;
+	  --__last;
+	  while (__comp(*__pivot, *__last))
+	    --__last;
+	  if (!(__first < __last))
+	    return __first;
+	  std::iter_swap(__first, __last);
+	  ++__first;
+	}
+    }
+    
+   /**
+    *  @if maint
+    *  This is a helper function for the sort routine
+    *  @endif
+    */
+  template<typename _RandomAccessIterator, typename _Compare>
+    _RandomAccessIterator 
+    __unguarded_mid_partition(_RandomAccessIterator __first,
+			      _RandomAccessIterator __last,
+			      _RandomAccessIterator __pivot, _Compare __comp)
+    {
+      while (true)
+        {
+          while (__comp(*__first, *__pivot))
+            ++__first;
+          --__last;
+          while (__comp(*__pivot, *__last))
+            --__last;
+          if (__first == __pivot)
+            {
+              if(__last == __pivot)
+                return __first;
+              ++__first;
+              while(__comp(*__first, *__pivot))
+                ++__first;
+              if(!(__first < __last))
+                return __first;
+              std::iter_swap(__first, __last);
+              ++__first;
+              break;
+            }
+            
+          if (__last == __pivot)
+            {
+              --__last;
+              while(__comp(*__pivot, *__last))
+                --__last;
+              if(!(__first < __last))
+                return __first;
+              std::iter_swap(__first, __last);
+              ++__first;
+              break;
+            }
+          std::iter_swap(__first, __last);
+          ++__first;
+        }
+
+        while (true)
+        {
+          while (__comp(*__first, *__pivot))
+            ++__first;
+          --__last;
+          while (__comp(*__pivot, *__last))
+            --__last;
+          
+          if (!(__first < __last))
+            return __first;
+          std::iter_swap(__first, __last);
+          ++__first;
+        }
     }
 
   /**
@@ -1959,15 +2048,15 @@
 
       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(__gnu_cxx::__move(*__i));
+	      std::__move_backward(__first, __i, __i + 1);
+	      *__first = __gnu_cxx::__move(__val);
 	    }
 	  else
-	    std::__unguarded_linear_insert(__i, __val, __comp);
+	    std::__unguarded_linear_insert(__i, __comp);
 	}
     }
 
@@ -1985,7 +2074,7 @@
 	_ValueType;
 
       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
-	std::__unguarded_linear_insert(__i, _ValueType(*__i), __comp);
+	std::__unguarded_linear_insert(__i, __comp);
     }
 
   /**
@@ -2200,6 +2289,65 @@
 			     __gnu_cxx::__ops::less());
     }
 
+
+
+  template<typename _RandomAccessIterator, typename _Compare>
+    inline typename __enable_if<_RandomAccessIterator, 
+      !(__gnu_cxx::__is_moveable<typename iterator_traits<_RandomAccessIterator>
+    				            ::value_type>::value)>::__type
+    __introsort_partition(_RandomAccessIterator __first,
+		          _RandomAccessIterator __last, _Compare __comp)
+    {
+    typedef typename iterator_traits<_RandomAccessIterator>::value_type
+	_ValueType;
+	
+	  return
+	    std::__unguarded_partition(__first, __last,
+				       _ValueType(std::__median(*__first,
+								*(__first
+								  + (__last
+								     - __first)
+								  / 2),
+								*(__last - 1),
+								__comp)),
+				       __comp);
+    }
+
+template<typename _RandomAccessIterator, typename _Compare>
+    inline typename __enable_if<_RandomAccessIterator,
+      __gnu_cxx::__is_moveable<typename iterator_traits<_RandomAccessIterator>
+    			         ::value_type>::value>::__type
+    __introsort_partition(_RandomAccessIterator __first,
+                          _RandomAccessIterator __last, _Compare __comp)
+    {
+      typedef typename iterator_traits<_RandomAccessIterator>::value_type
+	_ValueType;
+          _RandomAccessIterator __cut, __pivot(__first + (__last - __first)/2);
+          const _ValueType &__a = *__first;
+          const _ValueType &__b = *__pivot;
+          const _ValueType &__c = *(__last - 1);
+        
+	  if (__comp(__a, __b))
+	    if (__comp(__b, __c))
+	      __cut = __unguarded_mid_partition(__first, __last, __pivot,
+	      					__comp);
+	    else if (__comp(__a, __c))
+	      __cut = __unguarded_nocopy_partition(__first, __last - 1,
+	      					   __last - 1, __comp);
+	    else
+	      __cut = __unguarded_nocopy_partition(__first + 1, __last,
+	      					   __first, __comp);
+          else if (__comp(__a, __c))
+	    __cut = __unguarded_nocopy_partition(__first + 1, __last, __first,
+						 __comp);
+          else if (__comp(__b, __c))
+	    __cut = __unguarded_nocopy_partition(__first, __last - 1,
+						 __last - 1, __comp);
+          else
+    	    __cut = __unguarded_mid_partition(__first, __last, __pivot, __comp);
+         return __cut;
+    }
+
   /**
    *  @if maint
    *  This is a helper function for the sort routine.
@@ -2223,20 +2371,12 @@
 	    }
 	  --__depth_limit;
 	  _RandomAccessIterator __cut =
-	    std::__unguarded_partition(__first, __last,
-				       _ValueType(std::__median(*__first,
-								*(__first
-								  + (__last
-								     - __first)
-								  / 2),
-								*(__last - 1),
-								__comp)),
-				       __comp);
+	    std::__introsort_partition(__first, __last, __comp);
 	  std::__introsort_loop(__cut, __last, __depth_limit, __comp);
 	  __last = __cut;
 	}
     }
-
+   
   /**
    *  @brief Sort the elements of a sequence using a predicate for comparison.
    *  @param  first   An iterator.
@@ -2589,6 +2729,46 @@
 						    __result));
     }
 
+  // Varient of std::merge which moves rather than copies input
+  template<typename _InputIterator1, typename _InputIterator2,
+	   typename _OutputIterator, typename _Compare>
+    _OutputIterator
+    __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
+	  	 _InputIterator2 __first2, _InputIterator2 __last2,
+	  	 _OutputIterator __result, _Compare __comp)
+    {
+      // concept requirements
+      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
+      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
+      __glibcxx_function_requires(_SameTypeConcept<
+	    typename iterator_traits<_InputIterator1>::value_type,
+	    typename iterator_traits<_InputIterator2>::value_type>)
+      __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
+	    typename iterator_traits<_InputIterator1>::value_type>)
+      __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
+	    typename iterator_traits<_InputIterator1>::value_type,
+	    typename iterator_traits<_InputIterator2>::value_type>)
+      __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
+      __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
+
+      while (__first1 != __last1 && __first2 != __last2)
+	{
+	  if (__comp(*__first2, *__first1))
+	    {
+	      *__result = __gnu_cxx::__move(*__first2);
+	      ++__first2;
+	    }
+	  else
+	    {
+	      *__result = __gnu_cxx::__move(*__first1);
+	      ++__first1;
+	    }
+	  ++__result;
+	}
+      return std::__move(__first2, __last2, std::__move(__first1, __last1,
+				 			__result));
+    }
+
   /**
    *  @brief Merges two sorted ranges.
    *  @param  first1  An iterator.
@@ -2631,18 +2811,16 @@
 
       while (__last - __first >= __two_step)
 	{
-	  __result = std::merge(__first, __first + __step_size,
-				__first + __step_size, __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);
 
-      std::merge(__first, __first + __step_size,
-		 __first + __step_size, __last,
-		 __result,
-		 __comp);
+      std::__move_merge(__first, __first + __step_size,
+			__first + __step_size, __last, __result, __comp);
     }
 
   enum { _S_chunk_size = 7 };
@@ -2703,25 +2881,25 @@
 		     _Compare __comp)
     {
       if (__first1 == __last1)
-	return std::copy_backward(__first2, __last2, __result);
+	return std::__move_backward(__first2, __last2, __result);
       if (__first2 == __last2)
-	return std::copy_backward(__first1, __last1, __result);
+	return std::__move_backward(__first1, __last1, __result);
       --__last1;
       --__last2;
       while (true)
 	{
 	  if (__comp(*__last2, *__last1))
 	    {
-	      *--__result = *__last1;
+	      *--__result = __gnu_cxx::__move(*__last1);
 	      if (__first1 == __last1)
-		return std::copy_backward(__first2, ++__last2, __result);
+		return std::__move_backward(__first2, ++__last2, __result);
 	      --__last1;
 	    }
 	  else
 	    {
-	      *--__result = *__last2;
+	      *--__result = __gnu_cxx::__move(*__last2);
 	      if (__first2 == __last2)
-		return std::copy_backward(__first1, ++__last1, __result);
+		return std::__move_backward(__first1, ++__last1, __result);
 	      --__last2;
 	    }
 	}
@@ -2745,15 +2923,15 @@
       _BidirectionalIterator2 __buffer_end;
       if (__len1 > __len2 && __len2 <= __buffer_size)
 	{
-	  __buffer_end = std::copy(__middle, __last, __buffer);
-	  std::copy_backward(__first, __middle, __last);
-	  return std::copy(__buffer, __buffer_end, __first);
+	  __buffer_end = std::__move(__middle, __last, __buffer);
+	  std::__move_backward(__first, __middle, __last);
+	  return std::__move(__buffer, __buffer_end, __first);
 	}
       else if (__len1 <= __buffer_size)
 	{
-	  __buffer_end = std::copy(__first, __middle, __buffer);
-	  std::copy(__middle, __last, __first);
-	  return std::copy_backward(__buffer, __buffer_end, __last);
+	  __buffer_end = std::__move(__first, __middle, __buffer);
+	  std::__move(__middle, __last, __first);
+	  return std::__move_backward(__buffer, __buffer_end, __last);
 	}
       else
 	{
@@ -2780,12 +2958,13 @@
     {
       if (__len1 <= __len2 && __len1 <= __buffer_size)
 	{
-	  _Pointer __buffer_end = std::copy(__first, __middle, __buffer);
-	  std::merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
+	  _Pointer __buffer_end = std::__move(__first, __middle, __buffer);
+	  std::__move_merge(__buffer, __buffer_end, __middle, __last,
+	  		    __first, __comp);
 	}
       else if (__len2 <= __buffer_size)
 	{
-	  _Pointer __buffer_end = std::copy(__middle, __last, __buffer);
+	  _Pointer __buffer_end = std::__move(__middle, __last, __buffer);
 	  std::__merge_backward(__first, __middle, __buffer, __buffer_end,
 				__last, __comp);
 	}
@@ -3051,14 +3230,7 @@
       while (__last - __first > 3)
 	{
 	  _RandomAccessIterator __cut =
-	    std::__unguarded_partition(__first, __last,
-				       _ValueType(std::__median(*__first,
-								*(__first
-								  + (__last
-								     - __first)
-								  / 2),
-								*(__last - 1),
-							      __comp)), __comp);
+	   __introsort_partition(__first, __last, __comp);
 	  if (__cut <= __nth)
 	    __first = __cut;
 	  else
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/include/bits/stl_algobase.h libstdc++-v3/include/bits/stl_algobase.h
--- libstdc++-v3.so_7.clean/include/bits/stl_algobase.h	2005-05-25 13:38:47.000000000 +0100
+++ libstdc++-v3/include/bits/stl_algobase.h	2005-05-25 17:09:55.000000000 +0100
@@ -381,6 +381,33 @@
        return std::__copy_normal<__in, __out>::copy_n(__first, __last,
 						      __result);
     }
+    
+  template<typename _InputIterator, typename _OutputIterator>
+    inline typename __enable_if<_OutputIterator,
+      __gnu_cxx::__is_moveable<
+        typename iterator_traits<_OutputIterator>::value_type>::value &&
+        __are_same<typename iterator_traits<_InputIterator>::value_type,
+		   typename iterator_traits<_OutputIterator>::value_type>
+	  ::__value>::__type
+    __move(_InputIterator __first, _InputIterator __last,
+           _OutputIterator __result)
+    {
+      for(; __first != __last; ++__result, ++__first)
+        *__result = __gnu_cxx::__move(*__first);
+      return __result;
+    }
+        
+  template<typename _InputIterator, typename _OutputIterator>
+    inline typename __enable_if<_OutputIterator,
+      !(__gnu_cxx::__is_moveable<
+          typename iterator_traits<_OutputIterator>::value_type>::value &&
+          __are_same<typename iterator_traits<_InputIterator>::value_type,
+	  	     typename iterator_traits<_OutputIterator>::value_type>
+	  ::__value)>::__type
+    __move(_InputIterator __first, _InputIterator __last,
+           _OutputIterator __result)
+    { return std::copy(__first, __last, __result); }    
+  
   
   template<bool, typename>
     struct __copy_backward
@@ -512,6 +539,34 @@
 								 __result);
     }
 
+  template<typename _InputIterator, typename _OutputIterator>
+    inline 
+    typename __enable_if<_OutputIterator,
+      __gnu_cxx::__is_moveable<
+        typename iterator_traits<_OutputIterator>::value_type>::value &&
+        __are_same<typename iterator_traits<_InputIterator>::value_type,
+		   typename iterator_traits<_OutputIterator>::value_type>
+	  ::__value>::__type
+    __move_backward(_InputIterator __first, _InputIterator __last,
+		    _OutputIterator __result)
+    {
+      while (__first != __last)
+	*--__result = __gnu_cxx::__move(*--__last);
+      return __result;
+    }
+        
+  template<typename _InputIterator, typename _OutputIterator>
+    inline 
+    typename __enable_if<_OutputIterator,
+      !(__gnu_cxx::__is_moveable<
+          typename iterator_traits<_OutputIterator>::value_type>::value &&
+          __are_same<typename iterator_traits<_InputIterator>::value_type,
+	  	     typename iterator_traits<_OutputIterator>::value_type>
+	  ::__value)>::__type
+    __move_backward(_InputIterator __first, _InputIterator __last,
+		    _OutputIterator __result)
+    { return std::copy_backward(__first, __last, __result); }    
+    
   template<bool>
     struct __fill
     {
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/include/bits/stl_tempbuf.h libstdc++-v3/include/bits/stl_tempbuf.h
--- libstdc++-v3.so_7.clean/include/bits/stl_tempbuf.h	2005-02-01 16:07:12.000000000 +0000
+++ libstdc++-v3/include/bits/stl_tempbuf.h	2005-05-27 17:43:59.000000000 +0100
@@ -65,6 +65,36 @@
 
 namespace std
 {
+
+    template<bool __moveable, bool __trivial>
+      struct __initialize_temporary_buffer
+      {
+        template<typename _Tp>
+          static void
+          __fun(const _Tp& val, _Tp* _M_buffer, ptrdiff_t _M_len)
+          { std::uninitialized_fill_n(_M_buffer, _M_len, val); }
+      };
+      
+    // We can't normally assume the existance of a default constructor, but 
+    // all the moveable types have one.
+    template<>
+      struct __initialize_temporary_buffer<true, false>
+      {
+        template<typename _Tp>
+          static void
+          __fun(const _Tp& val, _Tp* _M_buffer, ptrdiff_t _M_len)
+          { std::__uninitialized_fill_n(_M_buffer, _M_len); }
+      };
+        
+    template<bool __moveable>
+      struct __initialize_temporary_buffer<__moveable, true>
+      {
+        template<typename _Tp>
+          static void
+          __fun(const _Tp& val, _Tp* _M_buffer, ptrdiff_t _M_len)
+          { }
+      };
+        
   /**
    *  @if maint
    *  This class is used in two places: stl_algo.h and ext/memory,
@@ -89,13 +119,6 @@
       size_type  _M_len;
       pointer    _M_buffer;
 
-      void
-      _M_initialize_buffer(const _Tp&, __true_type) { }
-
-      void
-      _M_initialize_buffer(const _Tp& val, __false_type)
-      { std::uninitialized_fill_n(_M_buffer, _M_len, val); }
-
     public:
       /// As per Table mumble.
       size_type
@@ -144,9 +167,6 @@
     : _M_original_len(std::distance(__first, __last)),
       _M_len(0), _M_buffer(0)
     {
-      // Workaround for a __type_traits bug in the pre-7.3 compiler.
-      typedef typename std::__is_scalar<_Tp>::__type _Trivial;
-
       try
 	{
 	  pair<pointer, size_type> __p(get_temporary_buffer<
@@ -154,7 +174,9 @@
 	  _M_buffer = __p.first;
 	  _M_len = __p.second;
 	  if (_M_len > 0)
-	    _M_initialize_buffer(*__first, _Trivial());
+	    __initialize_temporary_buffer<__gnu_cxx::__is_moveable<_Tp>::value,
+	      				  std::__is_scalar<_Tp>::__value>::
+					    __fun(*__first,_M_buffer, _M_len);
 	}
       catch(...)
 	{
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/include/bits/stl_uninitialized.h libstdc++-v3/include/bits/stl_uninitialized.h
--- libstdc++-v3.so_7.clean/include/bits/stl_uninitialized.h	2005-02-01 16:07:14.000000000 +0000
+++ libstdc++-v3/include/bits/stl_uninitialized.h	2005-05-25 00:25:20.000000000 +0100
@@ -218,6 +218,25 @@
       std::__uninitialized_fill_n_aux(__first, __n, __x, _Is_POD());
     }
 
+  // Specialised version of uninitialized_fill_n for default construction.
+  template<typename _ForwardIterator, typename _Size>
+    inline void
+    __uninitialized_fill_n(_ForwardIterator __first, _Size __n)
+    {
+      typedef typename iterator_traits<_ForwardIterator>::value_type _Tp;
+      _ForwardIterator __cur = __first;
+      try
+	{
+	  for (; __n > 0; --__n, ++__cur)
+	    std::_Construct(&*__cur);
+	}
+      catch(...)
+	{
+	  std::_Destroy(__first, __cur);
+	    __throw_exception_again;
+	}
+    }
+   
   // Extensions: versions of uninitialized_copy, uninitialized_fill,
   //  and uninitialized_fill_n that take an allocator parameter.
   //  We dispatch back to the standard versions when we're given the
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/25_algorithms/inplace_merge/moveable.cc libstdc++-v3/testsuite/25_algorithms/inplace_merge/moveable.cc
--- libstdc++-v3.so_7.clean/testsuite/25_algorithms/inplace_merge/moveable.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/inplace_merge/moveable.cc	2005-05-24 22:32:52.000000000 +0100
@@ -0,0 +1,52 @@
+// Copyright (C) 2005 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 2, 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 COPYING.  If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.4 [lib.alg.merge]
+
+#undef _GLIBCXX_CONCEPT_CHECKS
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+#include <testsuite_rvalref.h>
+
+using __gnu_test::test_container;
+using __gnu_test::bidirectional_iterator_wrapper;
+using std::inplace_merge;
+using __gnu_test::rvalstruct;
+
+typedef test_container<rvalstruct, bidirectional_iterator_wrapper> container;
+
+void 
+test1()
+{
+  int intarray[]={0,2,4,1,3,5};
+  rvalstruct array[6];
+  std::copy(intarray, intarray + 6, array);
+  container con(array, array + 6);
+  inplace_merge(con.begin(), con.it(3), con.end());
+  for(int i = 0; i < 6; ++i)
+    VERIFY(array[i].val == i && array[i].valid);
+}
+
+int 
+main()
+{
+  test1();
+  return 0;
+}
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/25_algorithms/nth_element/moveable.cc libstdc++-v3/testsuite/25_algorithms/nth_element/moveable.cc
--- libstdc++-v3.so_7.clean/testsuite/25_algorithms/nth_element/moveable.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/nth_element/moveable.cc	2005-05-24 22:51:23.000000000 +0100
@@ -0,0 +1,73 @@
+// Copyright (C) 2005 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 2, 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 COPYING.  If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.2 [lib.alg.nth.element]
+
+#undef _GLIBCXX_CONCEPT_CHECKS
+
+#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;
+using std::nth_element;
+using __gnu_test::rvalstruct;
+
+typedef test_container<rvalstruct, random_access_iterator_wrapper> Container;
+
+void 
+test1()
+{
+  int intarray[] = {6, 5, 4, 3, 2, 1, 0};
+  rvalstruct array[7];
+  std::copy(intarray, intarray + 7, array);
+  Container con(array, array + 7);
+  nth_element(con.begin(), con.it(3), con.end());
+  for(int i = 0; i < 3; ++i)
+    VERIFY(array[i].val < 3);
+  for(int i = 4; i < 7; ++i)
+    VERIFY(array[i].val > 3);
+  for(int i = 0; i < 7; ++i)
+    VERIFY(array[i].valid);
+}
+
+void 
+test2()
+{
+  int intarray[] = {0, 6, 1, 5, 2, 4, 3};
+  rvalstruct array[7];
+  std::copy(intarray, intarray + 7, array);
+  Container con(array,array + 7);
+  nth_element(con.begin(), con.it(3), con.end());
+  for(int i = 0; i < 3; ++i)
+    VERIFY(array[i].val < 3);
+  for(int i = 4; i < 7; ++i)
+    VERIFY(array[i].val > 3);
+  for(int i = 0; i < 7; ++i)
+    VERIFY(array[i].valid);  
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+  return 0;
+}
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/25_algorithms/partial_sort/moveable.cc libstdc++-v3/testsuite/25_algorithms/partial_sort/moveable.cc
--- libstdc++-v3.so_7.clean/testsuite/25_algorithms/partial_sort/moveable.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/partial_sort/moveable.cc	2005-05-22 12:00:46.000000000 +0100
@@ -0,0 +1,67 @@
+// Copyright (C) 2005 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 2, 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 COPYING.  If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.1.3 [lib.partial.sort]
+
+#undef _GLIBCXX_CONCEPT_CHECKS
+#define _GLIBCXX_TESTSUITE_ALLOW_RVALREF_ALIASING
+
+#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;
+using __gnu_test::rvalstruct;
+using std::partial_sort;
+
+typedef test_container<rvalstruct, random_access_iterator_wrapper> Container;
+
+void 
+test1()
+{
+  int intarray[] = {6, 5, 4, 3, 2, 1, 0};
+  rvalstruct array[7];
+  std::copy(intarray, intarray + 7, array);
+  Container con(array, array + 7);
+  partial_sort(con.begin(), con.it(3), con.end());
+  VERIFY(array[0].val == 0 && array[1].val == 1 && array[2].val == 2);
+  for(int i = 0; i < 7; ++i)
+    VERIFY(array[i].valid);
+}
+
+void 
+test2()
+{
+  int intarray[] = {0, 6, 1, 5, 2, 4, 3};
+  rvalstruct array[7];
+  std::copy(intarray, intarray + 7, array);
+  Container con(array,array + 7);
+  partial_sort(con.begin(), con.it(3), con.end());
+  VERIFY(array[0].val == 0 && array[1].val == 1 && array[2].val == 2);
+  for(int i = 0; i < 7; ++i)
+    VERIFY(array[i].valid);
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+}
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/25_algorithms/partition/moveable.cc libstdc++-v3/testsuite/25_algorithms/partition/moveable.cc
--- libstdc++-v3.so_7.clean/testsuite/25_algorithms/partition/moveable.cc	2005-05-20 16:08:39.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/partition/moveable.cc	2005-05-22 19:45:01.000000000 +0100
@@ -73,9 +73,24 @@
   for (const rvalstruct* i = barray+N/2; i < barray + N; ++i) VERIFY(!pred(*i));
 }
 
+// 25.2.12 stable_partition()
+void
+test02()
+{
+    using std::stable_partition;
+
+    rvalstruct s1[N];
+    std::copy(A, A + N, s1);
+    Fcontainer fcon(s1, s1 + N);
+    stable_partition(fcon.begin(), fcon.end(), Pred());
+    for(int i = 0; i < N; ++i)
+      VERIFY(s1[i].valid && s1[i].val == B[i]);
+}
+
 int
 main()
 {
   test01();
+  test02();
   return 0;
 }
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/25_algorithms/sort/moveable.cc libstdc++-v3/testsuite/25_algorithms/sort/moveable.cc
--- libstdc++-v3.so_7.clean/testsuite/25_algorithms/sort/moveable.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/sort/moveable.cc	2005-05-22 12:41:24.000000000 +0100
@@ -0,0 +1,61 @@
+// Copyright (C) 2001 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 2, 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 COPYING.  If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.1 algorithms, sort()
+
+#undef _GLIBCXX_CONCEPT_CHECKS
+#define _GLIBCXX_TESTSUITE_ALLOW_RVALREF_ALIASING
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+#include <testsuite_rvalref.h>
+
+bool test __attribute__((unused)) = true;
+
+using __gnu_test::test_container;
+using __gnu_test::random_access_iterator_wrapper;
+using __gnu_test::rvalstruct;
+using std::partial_sort;
+
+typedef test_container<rvalstruct, random_access_iterator_wrapper> Container;
+
+
+const int A[] = {10, 20, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 
+			17, 8, 18, 9, 19};
+const int N = sizeof(A) / sizeof(int);
+
+// 25.3.1.1 sort()
+void
+test01()
+{
+    rvalstruct s1[N];
+    std::copy(A, A + N, s1);
+    Container con(s1, s1 + N);
+    std::sort(con.begin(), con.end());
+    VERIFY(s1[0].valid);
+    for(int i = 1; i < N; ++i)
+      VERIFY(s1[i].val>s1[i-1].val && s1[i].valid);
+}
+
+int
+main()
+{
+  test01();
+  return 0;
+}
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/25_algorithms/sort/sort.cc libstdc++-v3/testsuite/25_algorithms/sort/sort.cc
--- libstdc++-v3.so_7.clean/testsuite/25_algorithms/sort/sort.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/sort/sort.cc	2005-05-23 15:16:24.000000000 +0100
@@ -0,0 +1,171 @@
+// Copyright (C) 2001 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 2, 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 COPYING.  If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.1 algorithms, sort()
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+bool test __attribute__((unused)) = true;
+
+const int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
+const int B[] = {10, 20, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 17, 8, 18, 9, 19};
+const int C[] = {20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
+const int N = sizeof(A) / sizeof(int);
+const int logN = 3; // ln(N) rounded up
+const int P = 7;
+
+// comparison predicate for stable_sort: order by rightmost digit
+struct CompLast
+{
+    bool
+    operator()(const int x, const int y)
+    { return x % 10 < y % 10; }
+};
+
+// This functor has the equivalent functionality of std::geater<>,
+// but there is no dependency on <functional> and it also tracks the
+// number of invocations since creation.
+class Gt
+{
+public:
+    static int count() { return itsCount; }
+    static void reset() { itsCount = 0; }
+
+    bool
+    operator()(const int& x, const int& y)
+    {
+        ++itsCount;
+        return x > y; 
+    }
+
+private:
+    static int itsCount;
+};
+
+int Gt::itsCount = 0;
+
+
+// 25.3.1.1 sort()
+void
+test01()
+{
+    int s1[N];
+    std::copy(B, B + N, s1);
+    VERIFY(std::equal(s1, s1 + N, B));
+
+    std::sort(s1, s1 + N);
+    VERIFY(std::equal(s1, s1 + N, A));
+
+    Gt gt;
+    gt.reset();
+    std::sort(s1, s1 + N, gt);
+    VERIFY(std::equal(s1, s1 + N, C));
+}
+
+// 25.3.1.2 stable_sort()
+void
+test02()
+{
+    int s1[N];
+    std::copy(A, A + N, s1);
+    VERIFY(std::equal(s1, s1 + N, A));
+
+    std::stable_sort(s1, s1 + N, CompLast());
+    VERIFY(std::equal(s1, s1 + N, B));
+
+    std::stable_sort(s1, s1 + N);
+    VERIFY(std::equal(s1, s1 + N, A));
+
+    Gt gt;
+    gt.reset();
+    std::stable_sort(s1, s1 + N, gt);
+    VERIFY(std::equal(s1, s1 + N, C));
+    VERIFY(gt.count() <= N * logN * logN);
+}
+
+// 25.3.1.3 partial_sort()
+void
+test03()
+{
+    int s1[N];
+    std::copy(B, B + N, s1);
+    VERIFY(std::equal(s1, s1 + N, B));
+
+    std::partial_sort(s1, s1 + P, s1 + N);
+    VERIFY(std::equal(s1, s1 + P, A));
+
+    Gt gt;
+    gt.reset();
+    std::partial_sort(s1, s1 + P, s1 + N, gt);
+    VERIFY(std::equal(s1, s1 + P, C));
+}
+
+// 25.3.1.4 partial_sort_copy()
+void
+test04()
+{
+    using std::partial_sort_copy;
+
+    int s1[N];
+    std::copy(B, B + N, s1);
+    VERIFY(std::equal(s1, s1 + N, B));
+
+    int s2[2*N];
+
+    partial_sort_copy(s1, s1 + N, s2, s2 + P);
+    VERIFY(std::equal(s2, s2 + P, A));
+
+    Gt gt;
+    gt.reset();
+    partial_sort_copy(s1, s1 + N, s2, s2 + P, gt);
+    VERIFY(std::equal(s2, s2 + P, C));
+
+    VERIFY(std::equal(s2, partial_sort_copy(s1, s1 + N, s2, s2 + 2*N), A));
+}
+
+// 25.3.2 nth_element()
+void
+test05()
+{
+    using std::nth_element;
+
+    int s1[N];
+    std::copy(B, B + N, s1);
+    VERIFY(std::equal(s1, s1 + N, B));
+
+    int* pn = s1 + (N / 2) - 1;
+    nth_element(s1, pn, s1 + N);
+    for (const int* i = pn; i < s1 + N; ++i) VERIFY(!(*i < *pn));
+
+    CompLast pred;
+    nth_element(s1, pn, s1 + N, pred);
+    for (const int* i = pn; i < s1 + N; ++i) VERIFY(!pred(*i, *pn));
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  test03();
+  test04();
+  test05();
+  
+  return 0;
+}
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/25_algorithms/sort.cc libstdc++-v3/testsuite/25_algorithms/sort.cc
--- libstdc++-v3.so_7.clean/testsuite/25_algorithms/sort.cc	2003-09-23 21:02:52.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/sort.cc	1970-01-01 01:00:00.000000000 +0100
@@ -1,171 +0,0 @@
-// Copyright (C) 2001 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 2, 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 COPYING.  If not, write to the Free
-// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
-// USA.
-
-// 25.3.1 algorithms, sort()
-
-#include <algorithm>
-#include <testsuite_hooks.h>
-
-bool test __attribute__((unused)) = true;
-
-const int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
-const int B[] = {10, 20, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 17, 8, 18, 9, 19};
-const int C[] = {20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
-const int N = sizeof(A) / sizeof(int);
-const int logN = 3; // ln(N) rounded up
-const int P = 7;
-
-// comparison predicate for stable_sort: order by rightmost digit
-struct CompLast
-{
-    bool
-    operator()(const int x, const int y)
-    { return x % 10 < y % 10; }
-};
-
-// This functor has the equivalent functionality of std::geater<>,
-// but there is no dependency on <functional> and it also tracks the
-// number of invocations since creation.
-class Gt
-{
-public:
-    static int count() { return itsCount; }
-    static void reset() { itsCount = 0; }
-
-    bool
-    operator()(const int& x, const int& y)
-    {
-        ++itsCount;
-        return x > y; 
-    }
-
-private:
-    static int itsCount;
-};
-
-int Gt::itsCount = 0;
-
-
-// 25.3.1.1 sort()
-void
-test01()
-{
-    int s1[N];
-    std::copy(B, B + N, s1);
-    VERIFY(std::equal(s1, s1 + N, B));
-
-    std::sort(s1, s1 + N);
-    VERIFY(std::equal(s1, s1 + N, A));
-
-    Gt gt;
-    gt.reset();
-    std::sort(s1, s1 + N, gt);
-    VERIFY(std::equal(s1, s1 + N, C));
-}
-
-// 25.3.1.2 stable_sort()
-void
-test02()
-{
-    int s1[N];
-    std::copy(A, A + N, s1);
-    VERIFY(std::equal(s1, s1 + N, A));
-
-    std::stable_sort(s1, s1 + N, CompLast());
-    VERIFY(std::equal(s1, s1 + N, B));
-
-    std::stable_sort(s1, s1 + N);
-    VERIFY(std::equal(s1, s1 + N, A));
-
-    Gt gt;
-    gt.reset();
-    std::stable_sort(s1, s1 + N, gt);
-    VERIFY(std::equal(s1, s1 + N, C));
-    VERIFY(gt.count() <= N * logN * logN);
-}
-
-// 25.3.1.3 partial_sort()
-void
-test03()
-{
-    int s1[N];
-    std::copy(B, B + N, s1);
-    VERIFY(std::equal(s1, s1 + N, B));
-
-    std::partial_sort(s1, s1 + P, s1 + N);
-    VERIFY(std::equal(s1, s1 + P, A));
-
-    Gt gt;
-    gt.reset();
-    std::partial_sort(s1, s1 + P, s1 + N, gt);
-    VERIFY(std::equal(s1, s1 + P, C));
-}
-
-// 25.3.1.4 partial_sort_copy()
-void
-test04()
-{
-    using std::partial_sort_copy;
-
-    int s1[N];
-    std::copy(B, B + N, s1);
-    VERIFY(std::equal(s1, s1 + N, B));
-
-    int s2[2*N];
-
-    partial_sort_copy(s1, s1 + N, s2, s2 + P);
-    VERIFY(std::equal(s2, s2 + P, A));
-
-    Gt gt;
-    gt.reset();
-    partial_sort_copy(s1, s1 + N, s2, s2 + P, gt);
-    VERIFY(std::equal(s2, s2 + P, C));
-
-    VERIFY(std::equal(s2, partial_sort_copy(s1, s1 + N, s2, s2 + 2*N), A));
-}
-
-// 25.3.2 nth_element()
-void
-test05()
-{
-    using std::nth_element;
-
-    int s1[N];
-    std::copy(B, B + N, s1);
-    VERIFY(std::equal(s1, s1 + N, B));
-
-    int* pn = s1 + (N / 2) - 1;
-    nth_element(s1, pn, s1 + N);
-    for (const int* i = pn; i < s1 + N; ++i) VERIFY(!(*i < *pn));
-
-    CompLast pred;
-    nth_element(s1, pn, s1 + N, pred);
-    for (const int* i = pn; i < s1 + N; ++i) VERIFY(!pred(*i, *pn));
-}
-
-int
-main()
-{
-  test01();
-  test02();
-  test03();
-  test04();
-  test05();
-  
-  return 0;
-}
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/25_algorithms/stable_sort/moveable.cc libstdc++-v3/testsuite/25_algorithms/stable_sort/moveable.cc
--- libstdc++-v3.so_7.clean/testsuite/25_algorithms/stable_sort/moveable.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/stable_sort/moveable.cc	2005-05-24 09:51:16.000000000 +0100
@@ -0,0 +1,54 @@
+// Copyright (C) 2005 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 2, 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 COPYING.  If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.1.2 [lib.stable.sort]
+
+#undef _GLIBCXX_CONCEPT_CHECKS
+
+#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;
+using __gnu_test::rvalstruct;
+using std::stable_sort;
+
+typedef test_container<rvalstruct, random_access_iterator_wrapper> Container;
+
+
+
+void 
+test1()
+{
+  int intarray[] = {6, 5, 4, 3, 2, 1, 0};
+  rvalstruct array[7];
+  std::copy(intarray, intarray + 7, array);
+  Container con(array, array + 7);
+  stable_sort(con.begin(), con.end());
+  for(int i = 0; i < 7; ++i)
+    VERIFY(array[i].val == i && array[i].valid);
+}
+
+
+int 
+main()
+{
+  test1();
+}
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/performance/25_algorithms/sort.cc libstdc++-v3/testsuite/performance/25_algorithms/sort.cc
--- libstdc++-v3.so_7.clean/testsuite/performance/25_algorithms/sort.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/performance/25_algorithms/sort.cc	2005-05-28 11:28:50.000000000 +0100
@@ -0,0 +1,227 @@
+// Copyright (C) 2005 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 2, 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 COPYING.  If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// As a special exception, you may use this file as part of a free software
+// library without restriction.  Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License.  This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+
+#define DISABLE_ITERATOR_DEBUG
+
+#include<vector>
+#include<algorithm>
+#include<stdio.h>
+#include<string>
+#include<sstream>
+
+#include<testsuite_performance.h>
+#include<testsuite_iterators.h>
+
+using namespace std;
+using namespace __gnu_test;
+
+// Used to stop move symantics
+struct vec_wrap
+{
+  vector<int> v; 
+  
+  explicit vec_wrap(vector<int> in_vec) : v(in_vec)
+  { }
+  
+  vec_wrap()
+  { }
+};
+
+bool inline
+operator<(const vec_wrap& lhs, const vec_wrap& rhs)
+{ return lhs.v == rhs.v; }
+
+
+// Used to perform the move symantics algorithm on an int
+struct int_wrap
+{
+  int i;
+  
+  explicit int_wrap(int in_val) : i(in_val)
+  {  }
+  
+  int_wrap(__gnu_cxx::__rvalref<int_wrap> in) : i(in.__ref.i)
+  { }
+  
+  void
+  operator=(int in)
+  { i = in; }
+  
+  void
+  operator=(__gnu_cxx::__rvalref<int_wrap> in)
+  { i = in.__ref.i; }
+  
+  int_wrap()
+  { }
+};
+
+struct ptr_wrap
+{
+  vector<int>* ptr;
+  ptr_wrap(vector<int>* in_ptr) : ptr(in_ptr)
+  { }
+};
+
+bool inline
+operator<(ptr_wrap lhs, ptr_wrap rhs)
+{ return *(lhs.ptr) < *(rhs.ptr); }
+
+bool inline
+operator<(const int_wrap& lhs, const int_wrap& rhs)
+{ return lhs.i < rhs.i; }
+
+namespace __gnu_cxx
+{
+  template<>
+    struct __is_moveable<int_wrap>
+    { static const bool value = true; };
+}
+
+struct
+dereference_compare
+{
+  template<typename T>
+    bool operator()(T lhs, T rhs)
+    { return *lhs < *rhs; }
+};
+
+template<typename T>
+void sort_and_output(T& vec, std::string description)
+{
+  time_counter time;
+  resource_counter resource;
+  start_counters(time, resource);
+  std::sort(vec.begin(), vec.end());
+  stop_counters(time, resource);
+  report_performance(__FILE__, description.c_str(), time, resource);
+  clear_counters(time, resource);
+  
+}
+
+void
+test1(int vec_length, vector<int> sort_vec, string vec_description)
+{
+  vector<vector<int> > moveable_vecs;
+  for(int i = 0; i < sort_vec.size(); i++)
+  {
+    vector<int> vec(vec_length, sort_vec[i]);
+    moveable_vecs.push_back(vec);
+  } 
+  ostringstream outputline;
+  outputline << "moveable vector - length " << sort_vec.size() << ":" <<
+    vec_description;
+  sort_and_output(moveable_vecs, outputline.str());  
+}
+
+
+void
+test2(int vec_length, vector<int> sort_vec, string vec_description )
+{
+  vector<vec_wrap> unmoveable_vecs;
+  for(int i = 0; i < sort_vec.size(); i++)
+  {
+    vector<int> vec(vec_length, sort_vec[i]);
+    vec_wrap wrap(vec);
+    unmoveable_vecs.push_back(wrap);
+  }  
+  ostringstream outputline;
+  outputline << "unmoveable vector - length " << sort_vec.size() << ":" <<
+    vec_description;
+  sort_and_output(unmoveable_vecs, outputline.str());
+}
+
+  
+void
+test3(int vec_length, vector<int> sort_vec, string vec_description)
+{
+  vector<vector<int> > primary_vec;
+  vector<ptr_wrap> ptr_vec;
+  for(int i = 0; i < sort_vec.size(); i++)
+  {
+    vector<int> vec(vec_length, sort_vec[i]);
+    primary_vec.push_back(vec);
+  }
+  for(int i = 0; i < sort_vec.size(); i++)
+    ptr_vec.push_back(&primary_vec[i]);
+  ostringstream outputline;
+  outputline << "pointers to vector - length " << sort_vec.size() << ":" <<
+    vec_description;
+  sort_and_output(ptr_vec, outputline.str());
+}
+ 
+ 
+void
+test4(vector<int> sort_vec, string vec_description)
+{
+  ostringstream outputline;
+  outputline << "ints - length " << sort_vec.size() << ":" << vec_description;
+  sort_and_output(sort_vec, outputline.str());
+}
+
+void
+test5(vector<int> sort_vec, string vec_description)
+{
+  vector<int_wrap> moveable_int_vec(sort_vec.size());
+  copy(sort_vec.begin(), sort_vec.end(), moveable_int_vec.begin());
+  ostringstream outputline;
+  outputline << "moveable ints - length " << sort_vec.size() << ":" <<
+    vec_description;
+  sort_and_output(moveable_int_vec, outputline.str());
+}
+  
+int
+main(void)
+{
+  for(int length = 100000; length < 1000001; length*=10)
+  {
+    vector<int> sort_vec;
+    int val = 1000;
+    for(int i = 0; i < length; ++i)
+    {
+      val = (val * 88888) % 1000003;
+      sort_vec.push_back(val);
+    }
+    test1(1000000/length, sort_vec, "random vector");
+    test2(1000000/length, sort_vec, "random vector");
+    test3(1000000/length, sort_vec, "random vector");
+    
+  }
+  
+  for(int length = 1000000; length < 10000001; length*=10)
+  {
+    vector<int> sort_vec;
+    int val = 1000;
+    for(int i = 0; i < length; ++i)
+    {
+      val = (val * 88888) % 1000003;
+      sort_vec.push_back(val);
+    }
+    test4(sort_vec, "random vector");
+    test5(sort_vec, "random vector");
+  }
+}

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]