libstdc++: Rework std::copy/copy_backward/move/move_backward/fill/fill_n algos

Enhance those algos overloads to generalize existing optimization for
__gnu_debug::_Safe_iterator w/o _GLIBCXX_DEBUG mode and for std::deque
 iterators.

Also extend __copy_move_a2 ostreambuf_iterator overloads to std::vector and
std::deque iterators.

	* include/bits/stl_algobase.h
	(__copy_move_a1<>(_II, _II, _OI)): New.
	(__copy_move_a1<>(_Deque_iterator<>, _Deque_iterator<>, _OI)): New.
	(__copy_move_a1<>(_Deque_iterator<>, _Deque_iterator<>,
	_Deque_iterator<>)): New.
	(__copy_move_a1<>(_II, _II, _Deque_iterator<>)): New.
	(__copy_move_a<>(_II, _II, _OI)): Adapt, call __copy_move_a1<>.
	(__copy_move_a<>(const _Safe_iterator<>&, const _Safe_iterator<>&,
	_OI)): New.
	(__copy_move_a<>(const _Safe_iterator<>&, const _Safe_iterator<>&,
	 const _Safe_iterator<>&)): New.
	(__copy_move_a<>(_II, _II, const _Safe_iterator<>&)): New.
	(copy, move): Adapt, call __copy_move_a.
	(__copy_move_backward_a1<>(_II, _II, _OI)): New,
	call __copy_move_backward_a2.
	(__copy_move_backward_a1<>(_Deque_iterator<>, _Deque_iterator<>, _OI)): New.
	(__copy_move_backward_a1<>(_Deque_iterator<>, _Deque_iterator<>,
	_Deque_iterator<>)): New.
	(__copy_move_backward_a1<>(_II, _II, _Deque_iterator<>)): New.
	(__copy_move_backward_a<>(_II, _II, _OI)): Adapt, call
	__copy_move_backward_a1<>.
	(__copy_move_backward_a<>(const _Safe_iterator<>&, const _Safe_iterator<>&,
	_OI)): New.
	(__copy_move_backward_a<>(const _Safe_iterator<>&, const _Safe_iterator<>&,
	 const _Safe_iterator<>&)): New.
	(__copy_move_backward_a<>(_II, _II, const _Safe_iterator<>&)): New.
	(copy_backward, move_backward): Adapt, call __copy_move_backward_a<>.
	(__fill_a): Rename into...
	(__fill_a1): ... this.
	(__fill_a1(__normal_iterator<>, __normal_iterator<>, const _Tp&)): New.
	(__fill_a1(const _Deque_iterator<>&, const _Deque_iterator<>&, _VTp)):
	New.
	(__fill_a(_FIte, _FIte, const _Tp&)): New, call __fill_a1.
	(__fill_a(const _Safe_iterator<>&, const _Safe_iterator<>&,
	const _Tp&)): New.
	(fill): Adapt, remove __niter_base usage.
	(__fill_n_a): Rename into...
	(__fill_n_a1): ...this.
	(__fill_n_a(const _Safe_iterator<>&, _Size, const _Tp&,
	input_iterator_tag)): New.
	(__fill_n_a(_OI, _Size, const _Tp&, output_iterator_tag)): New, call
	__fill_n_a1.
	(__fill_n_a(_OI, _Size, const _Tp&, random_access_iterator_tag)): New,
	call __fill_a.
	(__equal_aux): Rename into...
	(__equal_aux1): ...this.
	(__equal_aux1(_Deque_iterator<>, _Deque_iterator<>, _OI)): New.
	(__equal_aux1(_Deque_iterator<>, _Deque_iterator<>,
	_Deque_iterator<>)): New.
	(__equal_aux1(_II, _II, _Deque_iterator<>)): New.
	(__equal_aux(_II1, _II1, _II2)): New, call __equal_aux1.
	(__equal_aux(const _Safe_iterator<>&, const _Safe_iterator<>&,
	_OI)): New.
	(__equal_aux(const _Safe_iterator<>&, const _Safe_iterator<>&,
	 const _Safe_iterator<>&)): New.
	(__equal_aux(_II, _II, const _Safe_iterator<>&)): New.
	(equal(_II1, _II1, _II2)): Adapt.
	* include/bits/stl_deque.h
	(fill, copy, copy_backward, move, move_backward): Remove.
	* include/bits/deque.tcc: Include <bits/stl_algobase.h>.
	(__fill_a1): New.
	(__copy_move_dit): New.
	(__copy_move_a1): New, use latter.
	(__copy_move_a1(_II, _II, _Deque_iterator<>)): New.
	(__copy_move_backward_dit): New.
	(__copy_move_backward_a1): New, use latter.
	(__copy_move_backward_a1(_II, _II, _Deque_iterator<>)): New.
	(__equal_dit): New.
	(__equal_aux1): New, use latter.
	(__equal_aux1(_II, _II, _Deque_iterator<>)): New.
	* include/std/numeric (__is_random_access_iter): Move...
	* include/bits/stl_iterator_base_types.h (__is_random_access_iter): ...
	here. Provide pre-C++11 definition.
	* include/debug/debug.h (_Safe_iterator<>): New declaration.
	* include/debug/safe_iterator.h (_Safe_iterator<>::_M_can_advance): Add
	__strict parameter.
	* include/debug/safe_iterator.tcc: Include <bits/stl_algobase.h>.
	(_Safe_iterator<>::_M_can_advance): Adapt.
	(std::__copy_move_a, std::__copy_move_backward_a, __fill_a): New.
	(__fill_n_a, __equal_aux): New.
	* include/debug/stl_iterator.h (__niter_base): Remove.
	* include/debug/vector (__niter_base): Remove.
	* testsuite/performance/25_algorithms/copy_backward_deque_iterators.cc:
	Include <vector> and <list>. Add benches.
	* testsuite/performance/25_algorithms/copy_deque_iterators.cc: Likewise.
	* testsuite/performance/25_algorithms/equal_deque_iterators.cc: Likewise.
	* testsuite/25_algorithms/copy/debug/1_neg.cc: New.
	* testsuite/25_algorithms/copy/deque_iterators/2.cc: New.
	* testsuite/25_algorithms/copy/deque_iterators/31.cc: New.
	* testsuite/25_algorithms/copy/deque_iterators/32.cc: New.
	* testsuite/25_algorithms/copy/deque_iterators/33.cc: New.
	* testsuite/25_algorithms/copy/deque_iterators/41.cc: New.
	* testsuite/25_algorithms/copy/deque_iterators/42.cc: New.
	* testsuite/25_algorithms/copy/deque_iterators/43.cc: New.
	* testsuite/25_algorithms/copy/streambuf_iterators/char/4.cc (test02):
	New.
	* testsuite/25_algorithms/copy_backward/deque_iterators/2.cc: New.
	* testsuite/25_algorithms/equal/deque_iterators/1.cc: New.
	* testsuite/25_algorithms/fill/deque_iterators/1.cc: New.
	* testsuite/25_algorithms/move/deque_iterators/2.cc: New.
	* testsuite/25_algorithms/move_backward/deque_iterators/2.cc: New.

From-SVN: r279201

5 files changed, 250 insertions, 28 deletions

diff --git a/libstdc++-v3/include/debug/debug.h b/libstdc++-v3/include/debug/debug.h
index d851b4ae6dd..8d3a8606ccd 100644
--- a/libstdc++-v3/include/debug/debug.h
+++ b/libstdc++-v3/include/debug/debug.h
@@ -56,6 +56,9 @@ namespace std
 namespace __gnu_debug
 {
   using namespace std::__debug;
+
+  template<typename _Ite, typename _Seq, typename _Cat>
+    struct _Safe_iterator;
 }
 
 #ifndef _GLIBCXX_DEBUG
diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h
index fa0d03f39dc..536690d6dcd 100644
--- a/libstdc++-v3/include/debug/safe_iterator.h
+++ b/libstdc++-v3/include/debug/safe_iterator.h
@@ -400,7 +400,7 @@ namespace __gnu_debug
 
       // Can we advance the iterator @p __n steps (@p __n may be negative)
       bool
-      _M_can_advance(difference_type __n) const;
+      _M_can_advance(difference_type __n, bool __strict = false) const;
 
       // Is the iterator range [*this, __rhs) valid?
       bool
diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc
index 1750bc473d2..1d98a882d56 100644
--- a/libstdc++-v3/include/debug/safe_iterator.tcc
+++ b/libstdc++-v3/include/debug/safe_iterator.tcc
@@ -29,6 +29,8 @@
 #ifndef _GLIBCXX_DEBUG_SAFE_ITERATOR_TCC
 #define _GLIBCXX_DEBUG_SAFE_ITERATOR_TCC 1
 
+#include <bits/stl_algobase.h>
+
 namespace __gnu_debug
 {
   template<typename _Iterator, typename _Sequence, typename _Category>
@@ -82,7 +84,7 @@ namespace __gnu_debug
   template<typename _Iterator, typename _Sequence, typename _Category>
     bool
     _Safe_iterator<_Iterator, _Sequence, _Category>::
-    _M_can_advance(difference_type __n) const
+    _M_can_advance(difference_type __n, bool __strict) const
     {
       if (this->_M_singular())
 	return false;
@@ -94,17 +96,17 @@ namespace __gnu_debug
 	{
 	  std::pair<difference_type, _Distance_precision> __dist =
 	    _M_get_distance_from_begin();
-	  bool __ok =  ((__dist.second == __dp_exact && __dist.first >= -__n)
-			|| (__dist.second != __dp_exact && __dist.first > 0));
-	  return __ok;
+	  return __dist.second == __dp_exact
+	    ? __dist.first >= -__n
+	    : !__strict && __dist.first > 0;
 	}
       else
 	{
 	  std::pair<difference_type, _Distance_precision> __dist =
 	    _M_get_distance_to_end();
-	  bool __ok = ((__dist.second == __dp_exact && __dist.first >= __n)
-		       || (__dist.second != __dp_exact && __dist.first > 0));
-	  return __ok;
+	  return __dist.second == __dp_exact
+	    ? __dist.first >= __n
+	    : !__strict && __dist.first > 0;
 	}
     }
 
@@ -228,4 +230,241 @@ namespace __gnu_debug
     }
 } // namespace __gnu_debug
 
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+  template<bool _IsMove,
+	   typename _Ite, typename _Seq, typename _Cat, typename _OI>
+    _OI
+    __copy_move_a(
+      const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
+      const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __last,
+      _OI __result)
+    {
+      typename ::__gnu_debug::_Distance_traits<_Ite>::__type __dist;
+      __glibcxx_check_valid_range2(__first, __last, __dist);
+      __glibcxx_check_can_increment(__result, __dist.first);
+
+      if (__dist.second > ::__gnu_debug::__dp_equality)
+	return std::__copy_move_a<_IsMove>(__first.base(), __last.base(),
+					   __result);
+
+      return std::__copy_move_a1<_IsMove>(__first, __last, __result);
+    }
+
+  template<bool _IsMove,
+	   typename _II, typename _Ite, typename _Seq, typename _Cat>
+    __gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
+    __copy_move_a(_II __first, _II __last,
+      const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __result)
+    {
+      typename ::__gnu_debug::_Distance_traits<_II>::__type __dist;
+      __glibcxx_check_valid_range2(__first, __last, __dist);
+      __glibcxx_check_can_increment(__result, __dist.first);
+
+      if (__dist.second > ::__gnu_debug::__dp_sign
+	  && __result._M_can_advance(__dist.first, true))
+	return ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>(
+		std::__copy_move_a<_IsMove>(__first, __last, __result.base()),
+		__result._M_sequence);
+
+      return std::__copy_move_a1<_IsMove>(__first, __last, __result);
+    }
+
+  template<bool _IsMove,
+	   typename _IIte, typename _ISeq, typename _ICat,
+	   typename _OIte, typename _OSeq, typename _OCat>
+    ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>
+    __copy_move_a(
+      const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>& __first,
+      const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>& __last,
+      const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>& __result)
+    {
+      typename ::__gnu_debug::_Distance_traits<_IIte>::__type __dist;
+      __glibcxx_check_valid_range2(__first, __last, __dist);
+      __glibcxx_check_can_increment(__result, __dist.first);
+
+      if (__dist.second > ::__gnu_debug::__dp_equality)
+	{
+	  if (__dist.second > ::__gnu_debug::__dp_sign
+	      && __result._M_can_advance(__dist.first, true))
+	    return ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>(
+	      std::__copy_move_a<_IsMove>(__first.base(), __last.base(),
+					  __result.base()),
+	      __result._M_sequence);
+
+	  return std::__copy_move_a<_IsMove>(__first.base(), __last.base(),
+					     __result);
+	}
+
+      return std::__copy_move_a1<_IsMove>(__first, __last, __result);
+    }
+
+  template<bool _IsMove,
+	   typename _Ite, typename _Seq, typename _Cat, typename _OI>
+    _OI
+    __copy_move_backward_a(
+		const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
+		const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __last,
+		_OI __result)
+    {
+      typename ::__gnu_debug::_Distance_traits<_Ite>::__type __dist;
+      __glibcxx_check_valid_range2(__first, __last, __dist);
+      __glibcxx_check_can_increment(__result, -__dist.first);
+
+      if (__dist.second > ::__gnu_debug::__dp_equality)
+	return std::__copy_move_backward_a<_IsMove>(
+		__first.base(), __last.base(), __result);
+
+      return std::__copy_move_backward_a1<_IsMove>(__first, __last, __result);
+    }
+
+  template<bool _IsMove,
+	   typename _II, typename _Ite, typename _Seq, typename _Cat>
+    __gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
+    __copy_move_backward_a(_II __first, _II __last,
+	const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __result)
+    {
+      typename ::__gnu_debug::_Distance_traits<_II>::__type __dist;
+      __glibcxx_check_valid_range2(__first, __last, __dist);
+      __glibcxx_check_can_increment(__result, -__dist.first);
+
+      if (__dist.second > ::__gnu_debug::__dp_sign
+	  && __result._M_can_advance(-__dist.first, true))
+	return ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>(
+		std::__copy_move_backward_a<_IsMove>(__first, __last,
+						     __result.base()),
+		__result._M_sequence);
+
+      return std::__copy_move_backward_a1<_IsMove>(__first, __last, __result);
+    }
+
+  template<bool _IsMove,
+	   typename _IIte, typename _ISeq, typename _ICat,
+	   typename _OIte, typename _OSeq, typename _OCat>
+    ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>
+    __copy_move_backward_a(
+	const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>& __first,
+	const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>& __last,
+	const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>& __result)
+    {
+      typename ::__gnu_debug::_Distance_traits<_IIte>::__type __dist;
+      __glibcxx_check_valid_range2(__first, __last, __dist);
+      __glibcxx_check_can_increment(__result, -__dist.first);
+
+      if (__dist.second > ::__gnu_debug::__dp_equality)
+	{
+	  if (__dist.second > ::__gnu_debug::__dp_sign
+	      && __result._M_can_advance(-__dist.first, true))
+	    return ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>(
+	      std::__copy_move_backward_a<_IsMove>(__first.base(), __last.base(),
+						   __result.base()),
+	      __result._M_sequence);
+
+	  return std::__copy_move_backward_a<_IsMove>(
+	    __first.base(), __last.base(), __result);
+	}
+
+      return std::__copy_move_backward_a1<_IsMove>(__first, __last, __result);
+    }
+
+  template<typename _Ite, typename _Seq, typename _Cat, typename _Tp>
+    void
+    __fill_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
+	     const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __last,
+	     const _Tp& __value)
+    {
+      typename ::__gnu_debug::_Distance_traits<_Ite>::__type __dist;
+      __glibcxx_check_valid_range2(__first, __last, __dist);
+
+      if (__dist.second > ::__gnu_debug::__dp_equality)
+	std::__fill_a(__first.base(), __last.base(), __value);
+
+      std::__fill_a1(__first, __last, __value);
+    }
+
+  template<typename _Ite, typename _Seq, typename _Cat, typename _Size,
+	   typename _Tp>
+    ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
+    __fill_n_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
+	       _Size __n, const _Tp& __value,
+	       std::input_iterator_tag)
+    {
+#if __cplusplus >= 201103L
+      static_assert(is_integral<_Size>{}, "fill_n must pass integral size");
+#endif
+
+      if (__n <= 0)
+	return __first;
+
+      __glibcxx_check_can_increment(__first, __n);
+      if (__first._M_can_advance(__n, true))
+	return ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>(
+		std::__fill_n_a(__first.base(), __n, __value, _Cat()),
+		__first._M_sequence);
+
+      return std::__fill_n_a1(__first, __n, __value);
+    }
+
+  template<typename _II1, typename _Seq1, typename _Cat1, typename _II2>
+    bool
+    __equal_aux(
+	const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>& __first1,
+	const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>& __last1,
+	_II2 __first2)
+    {
+      typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist;
+      __glibcxx_check_valid_range2(__first1, __last1, __dist);
+      __glibcxx_check_can_increment(__first2, __dist.first);
+
+      if (__dist.second > ::__gnu_debug::__dp_equality)
+	return std::__equal_aux(__first1.base(), __last1.base(), __first2);
+
+      return std::__equal_aux1(__first1, __last1, __first2);
+    }
+
+  template<typename _II1, typename _II2, typename _Seq2, typename _Cat2>
+    bool
+    __equal_aux(_II1 __first1, _II1 __last1,
+	const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>& __first2)
+    {
+      typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist;
+      __glibcxx_check_valid_range2(__first1, __last1, __dist);
+      __glibcxx_check_can_increment(__first2, __dist.first);
+
+      if (__dist.second > ::__gnu_debug::__dp_sign
+	  && __first2._M_can_advance(__dist.first, true))
+	return std::__equal_aux(__first1, __last1, __first2.base());
+
+      return std::__equal_aux1(__first1, __last1, __first2);
+    }
+
+  template<typename _II1, typename _Seq1, typename _Cat1,
+	   typename _II2, typename _Seq2, typename _Cat2>
+    bool
+    __equal_aux(
+	const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>& __first1,
+	const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>& __last1,
+	const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>& __first2)
+    {
+      typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist;
+      __glibcxx_check_valid_range2(__first1, __last1, __dist);
+      __glibcxx_check_can_increment(__first2, __dist.first);
+
+      if (__dist.second > ::__gnu_debug::__dp_equality)
+	{
+	  if (__dist.second > ::__gnu_debug::__dp_sign &&
+	      __first2._M_can_advance(__dist.first, true))
+	    return std::__equal_aux(__first1.base(), __last1.base(),
+				    __first2.base());
+	  return std::__equal_aux(__first1.base(), __last1.base(), __first2);
+	}
+
+      return __equal_aux1(__first1, __last1, __first2);
+    }
+
+_GLIBCXX_END_NAMESPACE_VERSION
+} // namespace std
+
 #endif
diff --git a/libstdc++-v3/include/debug/stl_iterator.h b/libstdc++-v3/include/debug/stl_iterator.h
index 3b9ee5d9beb..8a7c19428a6 100644
--- a/libstdc++-v3/include/debug/stl_iterator.h
+++ b/libstdc++-v3/include/debug/stl_iterator.h
@@ -115,17 +115,4 @@ namespace __gnu_debug
 #endif
 }
 
-namespace std
-{
-_GLIBCXX_BEGIN_NAMESPACE_VERSION
-
-  template<typename _Iterator, typename _Container, typename _Sequence>
-    _Iterator
-    __niter_base(const __gnu_debug::_Safe_iterator<
-		 __gnu_cxx::__normal_iterator<_Iterator, _Container>,
-		 _Sequence, std::random_access_iterator_tag>&);
-
-_GLIBCXX_END_NAMESPACE_VERSION
-}
-
 #endif
diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector
index 56b5e140fd3..8138600f143 100644
--- a/libstdc++-v3/include/debug/vector
+++ b/libstdc++-v3/include/debug/vector
@@ -794,13 +794,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     };
 #endif
 
- template<typename _Iterator, typename _Container, typename _Sequence>
-    _Iterator
-    __niter_base(const __gnu_debug::_Safe_iterator<
-		 __gnu_cxx::__normal_iterator<_Iterator, _Container>,
-		 _Sequence, std::random_access_iterator_tag>& __it)
-    { return std::__niter_base(__it.base()); }
-
 #if __cplusplus >= 201703L
   namespace __detail::__variant
   {