This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC 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]

[v3] Optimize copy / copy_backward for move_iterators


Hi,

tested x86_64-linux, committed to mainline.

Paolo.

/////////////////////
2007-10-27  Paolo Carlini  <pcarlini@suse.de>

	* include/bits/stl_algobase.h (struct __miter_base): Add.
	(__copy_move_a2, __copy_move_backward_a2): Add.
	(copy, copy_backward, move, move_backward): Adjust, call *a2 helpers.
	* include/bits/cpp_type_traits.h (struct __is_move_iterator): Add.
	* include/bits/streambuf_iterator.h (__copy_move_a<>): Rename
	to __copy_move_a2.
	* include/std/streambuf (friend __copy_move_a<>): Likewise.
	* testsuite/25_algorithms/copy/move_iterators/1.cc: New.
	* testsuite/25_algorithms/copy_backward/move_iterators/1.cc: Likewise.

	* include/bits/stl_iterator.h (__normal_iterator<>::_Iterator_type):
	Rename to iterator_type.
Index: include/std/streambuf
===================================================================
--- include/std/streambuf	(revision 129671)
+++ include/std/streambuf	(working copy)
@@ -155,11 +155,11 @@
       friend streamsize
       __copy_streambufs_eof<>(__streambuf_type*, __streambuf_type*, bool&);
 
-      template<bool _IsCopy, typename _CharT2>
+      template<bool _IsMove, typename _CharT2>
         friend typename __gnu_cxx::__enable_if<__is_char<_CharT2>::__value, 
 					       _CharT2*>::__type
-        __copy_move_a(istreambuf_iterator<_CharT2>,
-		      istreambuf_iterator<_CharT2>, _CharT2*);
+        __copy_move_a2(istreambuf_iterator<_CharT2>,
+		       istreambuf_iterator<_CharT2>, _CharT2*);
 
       template<typename _CharT2>
         friend typename __gnu_cxx::__enable_if<__is_char<_CharT2>::__value,
Index: include/bits/stl_algobase.h
===================================================================
--- include/bits/stl_algobase.h	(revision 129671)
+++ include/bits/stl_algobase.h	(working copy)
@@ -266,7 +266,7 @@
   // If _Iterator is a __normal_iterator return its base (a plain pointer,
   // normally) otherwise return it untouched.  See copy, fill, ... 
   template<typename _Iterator,
-	   bool _BoolType = __is_normal_iterator<_Iterator>::__value>
+	   bool _IsNormal = __is_normal_iterator<_Iterator>::__value>
     struct __niter_base
     {
       static _Iterator
@@ -277,13 +277,31 @@
   template<typename _Iterator>
     struct __niter_base<_Iterator, true>
     {
-      static typename _Iterator::_Iterator_type
+      static typename _Iterator::iterator_type
+      __b(_Iterator __it)
+      { return __it.base(); }
+    };
+
+  // Likewise, for move_iterator.
+  template<typename _Iterator,
+	   bool _IsMove = __is_move_iterator<_Iterator>::__value>
+    struct __miter_base
+    {
+      static _Iterator
+      __b(_Iterator __it)
+      { return __it; }
+    };
+
+  template<typename _Iterator>
+    struct __miter_base<_Iterator, true>
+    {
+      static typename _Iterator::iterator_type
       __b(_Iterator __it)
       { return __it.base(); }
     };
 
   // Used in __copy_move and __copy_move_backward below.
-  template<bool _IsCopy>
+  template<bool _IsMove>
     struct __cm_assign
     {
       template<typename _IteratorL, typename _IteratorR>
@@ -294,7 +312,7 @@
 
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
   template<>
-    struct __cm_assign<false>
+    struct __cm_assign<true>
     {
       template<typename _IteratorL, typename _IteratorR>
         static void
@@ -309,7 +327,7 @@
   // (2) If we're using random access iterators, then write the loop as
   // a for loop with an explicit count.
 
-  template<bool _IsCopy, bool, typename>
+  template<bool _IsMove, bool, typename>
     struct __copy_move
     {
       template<typename _II, typename _OI>
@@ -317,13 +335,13 @@
         __copy_m(_II __first, _II __last, _OI __result)
         {
 	  for (; __first != __last; ++__result, ++__first)
-	    std::__cm_assign<_IsCopy>::__a(__result, __first);
+	    std::__cm_assign<_IsMove>::__a(__result, __first);
 	  return __result;
 	}
     };
 
-  template<bool _IsCopy, bool _IsSimple>
-    struct __copy_move<_IsCopy, _IsSimple, random_access_iterator_tag>
+  template<bool _IsMove, bool _IsSimple>
+    struct __copy_move<_IsMove, _IsSimple, random_access_iterator_tag>
     {
       template<typename _II, typename _OI>
         static _OI
@@ -332,7 +350,7 @@
 	  typedef typename iterator_traits<_II>::difference_type _Distance;
 	  for(_Distance __n = __last - __first; __n > 0; --__n)
 	    {
-	      std::__cm_assign<_IsCopy>::__a(__result, __first);
+	      std::__cm_assign<_IsMove>::__a(__result, __first);
 	      ++__first;
 	      ++__result;
 	    }
@@ -340,8 +358,8 @@
 	}
     };
 
-  template<bool _IsCopy>
-    struct __copy_move<_IsCopy, true, random_access_iterator_tag>
+  template<bool _IsMove>
+    struct __copy_move<_IsMove, true, random_access_iterator_tag>
     {
       template<typename _Tp>
         static _Tp*
@@ -353,7 +371,7 @@
 	}
     };
 
-  template<bool _IsCopy, typename _II, typename _OI>
+  template<bool _IsMove, typename _II, typename _OI>
     inline _OI
     __copy_move_a(_II __first, _II __last, _OI __result)
     {
@@ -365,7 +383,7 @@
 	                     && __is_pointer<_OI>::__value
 			     && __are_same<_ValueTypeI, _ValueTypeO>::__value);
 
-      return std::__copy_move<_IsCopy, __simple,
+      return std::__copy_move<_IsMove, __simple,
 	                      _Category>::__copy_m(__first, __last, __result);
     }
 
@@ -380,23 +398,33 @@
   template<typename _CharT, typename _Traits>
     class ostreambuf_iterator;
 
-  template<bool _IsCopy, typename _CharT>
+  template<bool _IsMove, typename _CharT>
     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 
 	     ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
-    __copy_move_a(_CharT*, _CharT*,
-		  ostreambuf_iterator<_CharT, char_traits<_CharT> >);
+    __copy_move_a2(_CharT*, _CharT*,
+		   ostreambuf_iterator<_CharT, char_traits<_CharT> >);
 
-  template<bool _IsCopy, typename _CharT>
+  template<bool _IsMove, typename _CharT>
     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 
 	     ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
-    __copy_move_a(const _CharT*, const _CharT*,
-		  ostreambuf_iterator<_CharT, char_traits<_CharT> >);
+    __copy_move_a2(const _CharT*, const _CharT*,
+		   ostreambuf_iterator<_CharT, char_traits<_CharT> >);
 
-  template<bool _IsCopy, typename _CharT>
+  template<bool _IsMove, typename _CharT>
     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
 				    _CharT*>::__type
-    __copy_move_a(istreambuf_iterator<_CharT, char_traits<_CharT> >,
-		  istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);
+    __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >,
+		   istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);
+
+  template<bool _IsMove, typename _II, typename _OI>
+    inline _OI
+    __copy_move_a2(_II __first, _II __last, _OI __result)
+    {
+      return _OI(std::__copy_move_a<_IsMove>
+		 (std::__niter_base<_II>::__b(__first),
+		  std::__niter_base<_II>::__b(__last),
+		  std::__niter_base<_OI>::__b(__result)));
+    }
 
   /**
    *  @brief Copies the range [first,last) into result.
@@ -424,10 +452,9 @@
 	    typename iterator_traits<_II>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      return _OI(std::__copy_move_a<true>
-		 (std::__niter_base<_II>::__b(__first),
-		  std::__niter_base<_II>::__b(__last),
-		  std::__niter_base<_OI>::__b(__result)));
+      return (std::__copy_move_a2<__is_move_iterator<_II>::__value>
+	      (std::__miter_base<_II>::__b(__first),
+	       std::__miter_base<_II>::__b(__last), __result));
     }
 
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
@@ -457,14 +484,13 @@
 	    typename iterator_traits<_II>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      return _OI(std::__copy_move_a<false>
-		 (std::__niter_base<_II>::__b(__first),
-		  std::__niter_base<_II>::__b(__last),
-		  std::__niter_base<_OI>::__b(__result)));
+      return (std::__copy_move_a2<true>
+	      (std::__miter_base<_II>::__b(__first),
+	       std::__miter_base<_II>::__b(__last), __result));
     }
 #endif
 
-  template<bool _IsCopy, bool, typename>
+  template<bool _IsMove, bool, typename>
     struct __copy_move_backward
     {
       template<typename _BI1, typename _BI2>
@@ -472,13 +498,13 @@
         __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
         {
 	  while (__first != __last)
-	    std::__cm_assign<_IsCopy>::__a(--__result, --__last);
+	    std::__cm_assign<_IsMove>::__a(--__result, --__last);
 	  return __result;
 	}
     };
 
-  template<bool _IsCopy, bool _IsSimple>
-    struct __copy_move_backward<_IsCopy, _IsSimple, random_access_iterator_tag>
+  template<bool _IsMove, bool _IsSimple>
+    struct __copy_move_backward<_IsMove, _IsSimple, random_access_iterator_tag>
     {
       template<typename _BI1, typename _BI2>
         static _BI2
@@ -486,13 +512,13 @@
         {
 	  typename iterator_traits<_BI1>::difference_type __n;
 	  for (__n = __last - __first; __n > 0; --__n)
-	    std::__cm_assign<_IsCopy>::__a(--__result, --__last);
+	    std::__cm_assign<_IsMove>::__a(--__result, --__last);
 	  return __result;
 	}
     };
 
-  template<bool _IsCopy>
-    struct __copy_move_backward<_IsCopy, true, random_access_iterator_tag>
+  template<bool _IsMove>
+    struct __copy_move_backward<_IsMove, true, random_access_iterator_tag>
     {
       template<typename _Tp>
         static _Tp*
@@ -504,7 +530,7 @@
 	}
     };
 
-  template<bool _IsCopy, typename _BI1, typename _BI2>
+  template<bool _IsMove, typename _BI1, typename _BI2>
     inline _BI2
     __copy_move_backward_a(_BI1 __first, _BI1 __last, _BI2 __result)
     {
@@ -516,12 +542,22 @@
 	                     && __is_pointer<_BI2>::__value
 			     && __are_same<_ValueType1, _ValueType2>::__value);
 
-      return std::__copy_move_backward<_IsCopy, __simple,
+      return std::__copy_move_backward<_IsMove, __simple,
 	                               _Category>::__copy_move_b(__first,
 								 __last,
 								 __result);
     }
 
+  template<bool _IsMove, typename _BI1, typename _BI2>
+    inline _BI2
+    __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
+    {
+      return _BI2(std::__copy_move_backward_a<_IsMove>
+		  (std::__niter_base<_BI1>::__b(__first),
+		   std::__niter_base<_BI1>::__b(__last),
+		   std::__niter_base<_BI2>::__b(__result)));
+    }
+
   /**
    *  @brief Copies the range [first,last) into result.
    *  @param  first  A bidirectional iterator.
@@ -539,7 +575,7 @@
    *  Result may not be in the range [first,last).  Use copy instead.  Note
    *  that the start of the output range may overlap [first,last).
   */
-  template <typename _BI1, typename _BI2>
+  template<typename _BI1, typename _BI2>
     inline _BI2
     copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
     {
@@ -551,10 +587,9 @@
 	    typename iterator_traits<_BI2>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      return _BI2(std::__copy_move_backward_a<true>
-		  (std::__niter_base<_BI1>::__b(__first),
-		   std::__niter_base<_BI1>::__b(__last),
-		   std::__niter_base<_BI2>::__b(__result)));
+      return (std::__copy_move_backward_a2<__is_move_iterator<_BI1>::__value>
+	      (std::__miter_base<_BI1>::__b(__first),
+	       std::__miter_base<_BI1>::__b(__last), __result));
     }
 
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
@@ -587,10 +622,9 @@
 	    typename iterator_traits<_BI2>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      return _BI2(std::__copy_move_backward_a<false>
-		  (std::__niter_base<_BI1>::__b(__first),
-		   std::__niter_base<_BI1>::__b(__last),
-		   std::__niter_base<_BI2>::__b(__result)));
+      return (std::__copy_move_backward_a2<true>
+	      (std::__miter_base<_BI1>::__b(__first),
+	       std::__miter_base<_BI1>::__b(__last), __result));
     }
 #endif
 
Index: include/bits/stl_iterator.h
===================================================================
--- include/bits/stl_iterator.h	(revision 129671)
+++ include/bits/stl_iterator.h	(working copy)
@@ -668,6 +668,7 @@
       _Iterator _M_current;
 
     public:
+      typedef _Iterator					     iterator_type;
       typedef typename iterator_traits<_Iterator>::iterator_category
                                                              iterator_category;
       typedef typename iterator_traits<_Iterator>::value_type  value_type;
@@ -676,8 +677,6 @@
       typedef typename iterator_traits<_Iterator>::reference reference;
       typedef typename iterator_traits<_Iterator>::pointer   pointer;
 
-      typedef _Iterator _Iterator_type;
-
       __normal_iterator() : _M_current(_Iterator()) { }
 
       explicit
Index: include/bits/streambuf_iterator.h
===================================================================
--- include/bits/streambuf_iterator.h	(revision 129671)
+++ include/bits/streambuf_iterator.h	(working copy)
@@ -68,11 +68,11 @@
 	copy(istreambuf_iterator<_CharT2>, istreambuf_iterator<_CharT2>,
 	     ostreambuf_iterator<_CharT2>);
 
-      template<bool _IsCopy, typename _CharT2>
+      template<bool _IsMove, typename _CharT2>
 	friend typename __gnu_cxx::__enable_if<__is_char<_CharT2>::__value, 
 					       _CharT2*>::__type
-	__copy_move_a(istreambuf_iterator<_CharT2>,
-		      istreambuf_iterator<_CharT2>, _CharT2*);
+	__copy_move_a2(istreambuf_iterator<_CharT2>,
+		       istreambuf_iterator<_CharT2>, _CharT2*);
 
       template<typename _CharT2>
 	friend typename __gnu_cxx::__enable_if<__is_char<_CharT2>::__value,
@@ -292,11 +292,11 @@
       return __result;
     }
 
-  template<bool _IsCopy, typename _CharT>
+  template<bool _IsMove, typename _CharT>
     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 
     				    ostreambuf_iterator<_CharT> >::__type
-    __copy_move_a(_CharT* __first, _CharT* __last,
-		  ostreambuf_iterator<_CharT> __result)
+    __copy_move_a2(_CharT* __first, _CharT* __last,
+		   ostreambuf_iterator<_CharT> __result)
     {
       const streamsize __num = __last - __first;
       if (__num > 0)
@@ -304,11 +304,11 @@
       return __result;
     }
 
-  template<bool _IsCopy, typename _CharT>
+  template<bool _IsMove, typename _CharT>
     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
 				    ostreambuf_iterator<_CharT> >::__type
-    __copy_move_a(const _CharT* __first, const _CharT* __last,
-		  ostreambuf_iterator<_CharT> __result)
+    __copy_move_a2(const _CharT* __first, const _CharT* __last,
+		   ostreambuf_iterator<_CharT> __result)
     {
       const streamsize __num = __last - __first;
       if (__num > 0)
@@ -316,11 +316,11 @@
       return __result;
     }
 
-  template<bool _IsCopy, typename _CharT>
+  template<bool _IsMove, typename _CharT>
     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 
     				    _CharT*>::__type
-    __copy_move_a(istreambuf_iterator<_CharT> __first,
-		  istreambuf_iterator<_CharT> __last, _CharT* __result)
+    __copy_move_a2(istreambuf_iterator<_CharT> __first,
+		   istreambuf_iterator<_CharT> __last, _CharT* __result)
     {
       typedef istreambuf_iterator<_CharT>                  __is_iterator_type;
       typedef typename __is_iterator_type::traits_type     traits_type;
Index: include/bits/cpp_type_traits.h
===================================================================
--- include/bits/cpp_type_traits.h	(revision 129671)
+++ include/bits/cpp_type_traits.h	(working copy)
@@ -381,6 +381,28 @@
       typedef __true_type __type;
     };
 
+  //
+  // Move iterator type
+  //
+  template<typename _Tp>
+    struct __is_move_iterator
+    {
+      enum { __value = 0 };
+      typedef __false_type __type;
+    };
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+  template<typename _Iterator>
+    class move_iterator;
+
+  template<typename _Iterator>
+    struct __is_move_iterator< move_iterator<_Iterator> >
+    {
+      enum { __value = 1 };
+      typedef __true_type __type;
+    };
+#endif
+
 _GLIBCXX_END_NAMESPACE
 
 #endif //_CPP_TYPE_TRAITS_H
Index: testsuite/25_algorithms/copy_backward/move_iterators/1.cc
===================================================================
--- testsuite/25_algorithms/copy_backward/move_iterators/1.cc	(revision 0)
+++ testsuite/25_algorithms/copy_backward/move_iterators/1.cc	(revision 0)
@@ -0,0 +1,68 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2007 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 Pred 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.
+
+#undef _GLIBCXX_CONCEPT_CHECKS
+#define  _GLIBCXX_TESTSUITE_ALLOW_RVALREF_ALIASING
+
+#include <algorithm>
+#include <iterator>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+#include <testsuite_rvalref.h>
+
+using __gnu_test::test_container;
+using __gnu_test::bidirectional_iterator_wrapper;
+using __gnu_test::rvalstruct;
+using std::copy_backward;
+
+typedef test_container<rvalstruct,
+		       bidirectional_iterator_wrapper> container_in;
+typedef test_container<rvalstruct,
+		       bidirectional_iterator_wrapper> container_out;
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  int inarray[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
+  const int size = sizeof(inarray) / sizeof(int);
+
+  rvalstruct in[size], out[size];
+  std::copy(inarray, inarray + size, in);
+  std::fill(out, out + size, 0);
+
+  container_in incon(in, in + size);
+  container_out outcon(out, out + size);
+
+  copy_backward(std::move_iterator<bidirectional_iterator_wrapper<rvalstruct> >(incon.begin()),
+		std::move_iterator<bidirectional_iterator_wrapper<rvalstruct> >(incon.end()),
+		outcon.end());
+  VERIFY( std::equal(out, out + size, inarray) );
+  for (int z = 0; z < size; ++z)
+    VERIFY( out[z].valid );
+  for (int z = 0; z < size; ++z)
+    VERIFY( !in[z].valid );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
Index: testsuite/25_algorithms/copy/move_iterators/1.cc
===================================================================
--- testsuite/25_algorithms/copy/move_iterators/1.cc	(revision 0)
+++ testsuite/25_algorithms/copy/move_iterators/1.cc	(revision 0)
@@ -0,0 +1,66 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2007 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 Pred 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.
+
+#undef _GLIBCXX_CONCEPT_CHECKS
+#define  _GLIBCXX_TESTSUITE_ALLOW_RVALREF_ALIASING
+
+#include <algorithm>
+#include <iterator>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+#include <testsuite_rvalref.h>
+
+using __gnu_test::test_container;
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::output_iterator_wrapper;
+using __gnu_test::rvalstruct;
+using std::copy;
+
+typedef test_container<rvalstruct, input_iterator_wrapper> container_in;
+typedef test_container<rvalstruct, output_iterator_wrapper> container_out;
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  int inarray[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
+  const int size = sizeof(inarray) / sizeof(int);
+
+  rvalstruct in[size], out[size];
+  std::copy(inarray, inarray + size, in);
+
+  container_in incon(in, in + size);
+  container_out outcon(out, out + size);
+
+  copy(std::move_iterator<input_iterator_wrapper<rvalstruct> >(incon.begin()),
+       std::move_iterator<input_iterator_wrapper<rvalstruct> >(incon.end()),
+       outcon.begin());
+  VERIFY( std::equal(out, out + size, inarray) );
+  for (int z = 0; z < size; ++z)
+    VERIFY( out[z].valid );
+  for (int z = 0; z < size; ++z)
+    VERIFY( !in[z].valid );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}

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