algobase.h (mismatch, equal): Provide parallel version for N3671 overloads.

2013-10-01  François Dumont  <fdumont@gcc.gnu.org>

	* include/parallel/algobase.h (mismatch, equal): Provide parallel
	version for N3671 overloads.

From-SVN: r203082

1 files changed, 142 insertions, 23 deletions

diff --git a/libstdc++-v3/include/parallel/algobase.h b/libstdc++-v3/include/parallel/algobase.h
index d615065a555..1acb63e921b 100644
--- a/libstdc++-v3/include/parallel/algobase.h
+++ b/libstdc++-v3/include/parallel/algobase.h
@@ -94,17 +94,13 @@ namespace __parallel
     inline pair<_IIter1, _IIter2>
     mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
     {
-      typedef std::iterator_traits<_IIter1> _Iterator1Traits;
-      typedef std::iterator_traits<_IIter2> _Iterator2Traits;
-      typedef typename _Iterator1Traits::value_type _ValueType1;
-      typedef typename _Iterator2Traits::value_type _ValueType2;
-      typedef typename _Iterator1Traits::iterator_category _IteratorCategory1;
-      typedef typename _Iterator2Traits::iterator_category _IteratorCategory2;
-
-      typedef __gnu_parallel::_EqualTo<_ValueType1, _ValueType2> _EqualTo;
+      typedef __gnu_parallel::_EqualTo<
+	typename std::iterator_traits<_IIter1>::value_type,
+	typename std::iterator_traits<_IIter2>::value_type> _EqualTo;
 
       return __mismatch_switch(__begin1, __end1, __begin2, _EqualTo(),
-                               _IteratorCategory1(), _IteratorCategory2());
+                               std::__iterator_category(__begin1),
+			       std::__iterator_category(__begin2));
     }
 
   // Public interface
@@ -113,32 +109,93 @@ namespace __parallel
     mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
              _Predicate __pred)
     {
-      typedef std::iterator_traits<_IIter1> _Iterator1Traits;
-      typedef std::iterator_traits<_IIter2> _Iterator2Traits;
-      typedef typename _Iterator1Traits::iterator_category _IteratorCategory1;
-      typedef typename _Iterator2Traits::iterator_category _IteratorCategory2;
-
       return __mismatch_switch(__begin1, __end1, __begin2, __pred,
-                               _IteratorCategory1(), _IteratorCategory2());
+                               std::__iterator_category(__begin1),
+			       std::__iterator_category(__begin2));
     }
 
 #if __cplusplus > 201103L
+  // Sequential fallback.
   template<typename _InputIterator1, typename _InputIterator2>
     inline pair<_InputIterator1, _InputIterator2>
     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
-	     _InputIterator2 __first2, _InputIterator2 __last2)
+	     _InputIterator2 __first2, _InputIterator2 __last2,
+	     __gnu_parallel::sequential_tag)
     { return _GLIBCXX_STD_A::mismatch(__first1, __last1, __first2, __last2); }
 
+  // Sequential fallback.
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _BinaryPredicate>
     inline pair<_InputIterator1, _InputIterator2>
     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
 	     _InputIterator2 __first2, _InputIterator2 __last2,
-	     _BinaryPredicate __binary_pred)
+	     _BinaryPredicate __binary_pred,
+	     __gnu_parallel::sequential_tag)
     {
       return _GLIBCXX_STD_A::mismatch(__first1, __last1, __first2, __last2,
 				      __binary_pred);
     }
+
+  // Sequential fallback for input iterator case
+  template<typename _IIter1, typename _IIter2,
+           typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
+    inline pair<_IIter1, _IIter2>
+    __mismatch_switch(_IIter1 __begin1, _IIter1 __end1,
+		      _IIter2 __begin2, _IIter2 __end2, _Predicate __pred,
+		      _IteratorTag1, _IteratorTag2)
+    {
+      return _GLIBCXX_STD_A::mismatch(__begin1, __end1,
+				      __begin2, __end2, __pred);
+    }
+
+  // Parallel mismatch for random access iterators
+  template<typename _RAIter1, typename _RAIter2, typename _Predicate>
+    pair<_RAIter1, _RAIter2>
+    __mismatch_switch(_RAIter1 __begin1, _RAIter1 __end1,
+                      _RAIter2 __begin2, _RAIter2 __end2, _Predicate __pred, 
+                      random_access_iterator_tag, random_access_iterator_tag)
+    {
+      if (_GLIBCXX_PARALLEL_CONDITION(true))
+        {
+	  if ((__end2 - __begin2) < (__end1 - __begin1))
+	    __end1 = __begin1 + (__end2 - __begin2);
+
+          _RAIter1 __res =
+            __gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred,
+                                            __gnu_parallel::
+                                            __mismatch_selector()).first;
+          return make_pair(__res , __begin2 + (__res - __begin1));
+        }
+      else
+        return _GLIBCXX_STD_A::mismatch(__begin1, __end1,
+					__begin2, __end2, __pred);
+    }
+
+  template<typename _IIter1, typename _IIter2>
+    inline pair<_IIter1, _IIter2>
+    mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2)
+    {
+      typedef __gnu_parallel::_EqualTo<
+	typename std::iterator_traits<_IIter1>::value_type,
+	typename std::iterator_traits<_IIter2>::value_type> _EqualTo;
+
+      return __mismatch_switch(__begin1, __end1, __begin2, __end2, _EqualTo(),
+			       std::__iterator_category(__begin1),
+			       std::__iterator_category(__begin2));
+    }
+
+  template<typename _InputIterator1, typename _InputIterator2,
+	   typename _BinaryPredicate>
+    inline pair<_InputIterator1, _InputIterator2>
+    mismatch(_InputIterator1 __begin1, _InputIterator1 __end1,
+	     _InputIterator2 __begin2, _InputIterator2 __end2,
+	     _BinaryPredicate __binary_pred)
+    {
+      return __mismatch_switch(__begin1, __end1, __begin2, __end2,
+			       __binary_pred,
+			       std::__iterator_category(__begin1),
+			       std::__iterator_category(__begin2));
+    }
 #endif
 
   // Sequential fallback
@@ -175,19 +232,81 @@ namespace __parallel
     }
 
 #if __cplusplus > 201103L
-  template<typename _II1, typename _II2>
+  // Sequential fallback
+  template<typename _IIter1, typename _IIter2>
     inline bool
-    equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
-    { return _GLIBCXX_STD_A::equal(__first1, __last1, __first2, __last2); }
+    equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2,
+	  __gnu_parallel::sequential_tag)
+    {
+      return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2);
+    }
 
+  // Sequential fallback
   template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
     inline bool
-    equal(_IIter1 __first1, _IIter1 __last1,
-	  _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred)
+    equal(_IIter1 __begin1, _IIter1 __end1,
+	  _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred,
+	  __gnu_parallel::sequential_tag)
     {
-      return _GLIBCXX_STD_A::equal(__first1, __last1, __first2, __last2,
+      return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2,
 				   __binary_pred);
     }
+
+  // Sequential fallback for input iterator case
+  template<typename _IIter1, typename _IIter2,
+           typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
+    inline bool
+    __equal_switch(_IIter1 __begin1, _IIter1 __end1,
+		   _IIter2 __begin2, _IIter2 __end2, _Predicate __pred,
+		   _IteratorTag1, _IteratorTag2)
+    {
+      return _GLIBCXX_STD_A::equal(__begin1, __end1,
+				   __begin2, __end2, __pred);
+    }
+
+  // Parallel equal for random access iterators
+  template<typename _RAIter1, typename _RAIter2, typename _Predicate>
+    inline bool
+    __equal_switch(_RAIter1 __begin1, _RAIter1 __end1,
+		   _RAIter2 __begin2, _RAIter2 __end2, _Predicate __pred, 
+		   random_access_iterator_tag, random_access_iterator_tag)
+    {
+      if (_GLIBCXX_PARALLEL_CONDITION(true))
+        {
+	  if (std::distance(__begin1, __end1)
+	      != std::distance(__begin2, __end2))
+	    return false;
+
+	  return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __end2,
+					  __pred).first == __end1;
+        }
+      else
+        return _GLIBCXX_STD_A::equal(__begin1, __end1,
+				     __begin2, __end2, __pred);
+    }
+
+  template<typename _IIter1, typename _IIter2>
+    inline bool
+    equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2)
+    {
+      typedef __gnu_parallel::_EqualTo<
+	typename std::iterator_traits<_IIter1>::value_type,
+	typename std::iterator_traits<_IIter2>::value_type> _EqualTo;
+
+      return __equal_switch(__begin1, __end1, __begin2, __end2, _EqualTo(),
+			    std::__iterator_category(__begin1),
+			    std::__iterator_category(__begin2));
+    }
+
+  template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
+    inline bool
+    equal(_IIter1 __begin1, _IIter1 __end1,
+	  _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred)
+    {
+      return __equal_switch(__begin1, __end1, __begin2, __end2, __binary_pred,
+			    std::__iterator_category(__begin1),
+			    std::__iterator_category(__begin2));
+    }
 #endif
 
   // Sequential fallback