[thirdparty/gcc.git] / libstdc++-v3 / include / parallel / algobase.h

// -*- C++ -*-

// Copyright (C) 2007-2023 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 3, 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.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file parallel/algobase.h
 *  @brief Parallel STL function calls corresponding to the
 *  stl_algobase.h header.  The functions defined here mainly do case
 *  switches and call the actual parallelized versions in other files.
 *  Inlining policy: Functions that basically only contain one
 *  function call, are declared inline.
 *  This file is a GNU parallel extension to the Standard C++ Library.
 */

// Written by Johannes Singler and Felix Putze.

#ifndef _GLIBCXX_PARALLEL_ALGOBASE_H
#define _GLIBCXX_PARALLEL_ALGOBASE_H 1

#include <bits/stl_algobase.h>
#include <parallel/base.h>
#include <parallel/algorithmfwd.h>
#include <parallel/find.h>
#include <parallel/find_selectors.h>

namespace std _GLIBCXX_VISIBILITY(default)
{
namespace __parallel
{
  // NB: equal and lexicographical_compare require mismatch.

  // Sequential fallback
  template<typename _IIter1, typename _IIter2>
    inline pair<_IIter1, _IIter2>
    mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
             __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2); }

  // Sequential fallback
  template<typename _IIter1, typename _IIter2, typename _Predicate>
    inline pair<_IIter1, _IIter2>
    mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
             _Predicate __pred, __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __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,
                      _Predicate __pred, _IteratorTag1, _IteratorTag2)
    { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __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, _Predicate __pred, 
                      random_access_iterator_tag, random_access_iterator_tag)
    {
      if (_GLIBCXX_PARALLEL_CONDITION(true))
        {
          _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, __pred);
    }

  // Public interface
  template<typename _IIter1, typename _IIter2>
    inline pair<_IIter1, _IIter2>
    mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
    {
      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(),
                               std::__iterator_category(__begin1),
			       std::__iterator_category(__begin2));
    }

  // Public interface
  template<typename _IIter1, typename _IIter2, typename _Predicate>
    inline pair<_IIter1, _IIter2>
    mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
             _Predicate __pred)
    {
      return __mismatch_switch(__begin1, __end1, __begin2, __pred,
                               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,
	     __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,
	     __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
  template<typename _IIter1, typename _IIter2>
    inline bool
    equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 
          __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2); }

  // Sequential fallback
  template<typename _IIter1, typename _IIter2, typename _Predicate>
    inline bool
    equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 
          _Predicate __pred, __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __pred); }

  // Public interface
  template<typename _IIter1, typename _IIter2>
    _GLIBCXX20_CONSTEXPR
    inline bool
    equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
    {
#if __cplusplus > 201703L
      if (std::is_constant_evaluated())
	return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2);
#endif

      return __gnu_parallel::mismatch(__begin1, __end1, __begin2).first
              == __end1;
    }

  // Public interface
  template<typename _IIter1, typename _IIter2, typename _Predicate>
    _GLIBCXX20_CONSTEXPR
    inline bool
    equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 
          _Predicate __pred)
    {
#if __cplusplus > 201703L
      if (std::is_constant_evaluated())
	return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __pred);
#endif

      return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __pred).first
              == __end1;
    }

#if __cplusplus > 201103L
  // Sequential fallback
  template<typename _IIter1, typename _IIter2>
    inline bool
    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 __begin1, _IIter1 __end1,
	  _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred,
	  __gnu_parallel::sequential_tag)
    {
      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>
    _GLIBCXX20_CONSTEXPR
    inline bool
    equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2)
    {
#if __cplusplus > 201703L
      if (std::is_constant_evaluated())
	return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2);
#endif

      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>
    _GLIBCXX20_CONSTEXPR
    inline bool
    equal(_IIter1 __begin1, _IIter1 __end1,
	  _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred)
    {
#if __cplusplus > 201703L
      if (std::is_constant_evaluated())
	return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2,
				     __binary_pred);
#endif

      return __equal_switch(__begin1, __end1, __begin2, __end2, __binary_pred,
			    std::__iterator_category(__begin1),
			    std::__iterator_category(__begin2));
    }
#endif // C++14

  // Sequential fallback
  template<typename _IIter1, typename _IIter2>
    inline bool
    lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 
                            _IIter2 __begin2, _IIter2 __end2, 
                            __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
                                                     __begin2, __end2); }

  // Sequential fallback
  template<typename _IIter1, typename _IIter2, typename _Predicate>
    inline bool
    lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 
                            _IIter2 __begin2, _IIter2 __end2, 
                            _Predicate __pred, __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_A::lexicographical_compare(
               __begin1, __end1, __begin2, __end2, __pred); }

  // Sequential fallback for input iterator case
  template<typename _IIter1, typename _IIter2,
           typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
    inline bool
    __lexicographical_compare_switch(_IIter1 __begin1, _IIter1 __end1,
                                     _IIter2 __begin2, _IIter2 __end2, 
                                     _Predicate __pred,
                                     _IteratorTag1, _IteratorTag2)
    { return _GLIBCXX_STD_A::lexicographical_compare(
               __begin1, __end1, __begin2, __end2, __pred); }

  // Parallel lexicographical_compare for random access iterators
  // Limitation: Both valuetypes must be the same
  template<typename _RAIter1, typename _RAIter2, typename _Predicate>
    bool
    __lexicographical_compare_switch(_RAIter1 __begin1, _RAIter1 __end1,
                                     _RAIter2 __begin2, _RAIter2 __end2,
                                     _Predicate __pred,
                                     random_access_iterator_tag, 
                                     random_access_iterator_tag)
    {
      if (_GLIBCXX_PARALLEL_CONDITION(true))
        {
          typedef iterator_traits<_RAIter1> _TraitsType1;
          typedef typename _TraitsType1::value_type _ValueType1;

          typedef iterator_traits<_RAIter2> _TraitsType2;
          typedef typename _TraitsType2::value_type _ValueType2;

          typedef __gnu_parallel::
                  _EqualFromLess<_ValueType1, _ValueType2, _Predicate>
                  _EqualFromLessCompare;

          // Longer sequence in first place.
          if ((__end1 - __begin1) < (__end2 - __begin2))
            {
              typedef pair<_RAIter1, _RAIter2> _SpotType;
              _SpotType __mm = __mismatch_switch(__begin1, __end1, __begin2, 
                                             _EqualFromLessCompare(__pred), 
                                             random_access_iterator_tag(), 
                                             random_access_iterator_tag());

              return (__mm.first == __end1)
                        || bool(__pred(*__mm.first, *__mm.second));
            }
          else
            {
              typedef pair<_RAIter2, _RAIter1> _SpotType;
              _SpotType __mm = __mismatch_switch(__begin2, __end2, __begin1, 
                                             _EqualFromLessCompare(__pred), 
                                             random_access_iterator_tag(), 
                                             random_access_iterator_tag());

              return (__mm.first != __end2)
                        && bool(__pred(*__mm.second, *__mm.first));
            }
        }
      else
        return _GLIBCXX_STD_A::lexicographical_compare(
                 __begin1, __end1, __begin2, __end2, __pred);
    }

  // Public interface
  template<typename _IIter1, typename _IIter2>
    _GLIBCXX20_CONSTEXPR
    inline bool
    lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
                            _IIter2 __begin2, _IIter2 __end2)
    {
#if __cplusplus > 201703L
      if (std::is_constant_evaluated())
	return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
						       __begin2, __end2);
#endif

      typedef iterator_traits<_IIter1> _TraitsType1;
      typedef typename _TraitsType1::value_type _ValueType1;
      typedef typename _TraitsType1::iterator_category _IteratorCategory1;

      typedef iterator_traits<_IIter2> _TraitsType2;
      typedef typename _TraitsType2::value_type _ValueType2;
      typedef typename _TraitsType2::iterator_category _IteratorCategory2;
      typedef __gnu_parallel::_Less<_ValueType1, _ValueType2> _LessType;

      return __lexicographical_compare_switch(
               __begin1, __end1, __begin2, __end2, _LessType(),
               _IteratorCategory1(), _IteratorCategory2());
    }

  // Public interface
  template<typename _IIter1, typename _IIter2, typename _Predicate>
    _GLIBCXX20_CONSTEXPR
    inline bool
    lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
                            _IIter2 __begin2, _IIter2 __end2,
                            _Predicate __pred)
    {
#if __cplusplus > 201703L
      if (std::is_constant_evaluated())
	return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
						       __begin2, __end2,
						       __pred);
#endif

      typedef iterator_traits<_IIter1> _TraitsType1;
      typedef typename _TraitsType1::iterator_category _IteratorCategory1;

      typedef iterator_traits<_IIter2> _TraitsType2;
      typedef typename _TraitsType2::iterator_category _IteratorCategory2;

      return __lexicographical_compare_switch(
               __begin1, __end1, __begin2, __end2, __pred,
               _IteratorCategory1(), _IteratorCategory2());
    }

#if __cpp_lib_three_way_comparison
  using _GLIBCXX_STD_A::lexicographical_compare_three_way;
#endif
} // end namespace
} // end namespace

#endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */
Commit	Line	Data
c2ba9709 JS	1	// -- C++ --
c2ba9709 JS	2
83ffe9cd	3	// Copyright (C) 2007-2023 Free Software Foundation, Inc.
c2ba9709 JS	4	//
	5	// This file is part of the GNU ISO C++ Library. This library is free
	6	// software; you can redistribute it and/or modify it under the terms
	7	// of the GNU General Public License as published by the Free Software
748086b7	8	// Foundation; either version 3, or (at your option) any later
c2ba9709 JS	9	// version.
	10
	11	// This library is distributed in the hope that it will be useful, but
	12	// WITHOUT ANY WARRANTY; without even the implied warranty of
	13	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	14	// General Public License for more details.
	15
748086b7 JJ	16	// Under Section 7 of GPL version 3, you are granted additional
	17	// permissions described in the GCC Runtime Library Exception, version
	18	// 3.1, as published by the Free Software Foundation.
	19
	20	// You should have received a copy of the GNU General Public License and
	21	// a copy of the GCC Runtime Library Exception along with this program;
	22	// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
	23	// <http://www.gnu.org/licenses/>.
c2ba9709 JS	24
	25	/** @file parallel/algobase.h
	26	* @brief Parallel STL function calls corresponding to the
	27	* stl_algobase.h header. The functions defined here mainly do case
	28	* switches and call the actual parallelized versions in other files.
	29	* Inlining policy: Functions that basically only contain one
	30	* function call, are declared inline.
	31	* This file is a GNU parallel extension to the Standard C++ Library.
	32	*/
	33
	34	// Written by Johannes Singler and Felix Putze.
	35
	36	#ifndef _GLIBCXX_PARALLEL_ALGOBASE_H
	37	#define _GLIBCXX_PARALLEL_ALGOBASE_H 1
	38
c2ba9709 JS	39	#include <bits/stl_algobase.h>
c2ba9709 JS	40	#include <parallel/base.h>
e330aa5b	41	#include <parallel/algorithmfwd.h>
c2ba9709 JS	42	#include <parallel/find.h>
c2ba9709 JS	43	#include <parallel/find_selectors.h>
c2ba9709	44
12ffa228	45	namespace std _GLIBCXX_VISIBILITY(default)
c2ba9709 JS	46	{
	47	namespace __parallel
	48	{
4f39bf5c	49	// NB: equal and lexicographical_compare require mismatch.
c2ba9709 JS	50
c2ba9709 JS	51	// Sequential fallback
1acba85b JS	52	template<typename _IIter1, typename _IIter2>
	53	inline pair<_IIter1, _IIter2>
	54	mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
15ac3c72	55	__gnu_parallel::sequential_tag)
12ffa228	56	{ return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2); }
c2ba9709 JS	57
c2ba9709 JS	58	// Sequential fallback
15ac3c72	59	template<typename _IIter1, typename _IIter2, typename _Predicate>
1acba85b JS	60	inline pair<_IIter1, _IIter2>
1acba85b JS	61	mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
15ac3c72	62	_Predicate __pred, __gnu_parallel::sequential_tag)
12ffa228	63	{ return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); }
c2ba9709 JS	64
c2ba9709 JS	65	// Sequential fallback for input iterator case
1acba85b	66	template<typename _IIter1, typename _IIter2,
15ac3c72	67	typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
1acba85b	68	inline pair<_IIter1, _IIter2>
15ac3c72 JS	69	__mismatch_switch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
15ac3c72 JS	70	_Predicate __pred, _IteratorTag1, _IteratorTag2)
12ffa228	71	{ return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); }
c2ba9709 JS	72
c2ba9709 JS	73	// Parallel mismatch for random access iterators
15ac3c72	74	template<typename _RAIter1, typename _RAIter2, typename _Predicate>
1acba85b JS	75	pair<_RAIter1, _RAIter2>
1acba85b JS	76	__mismatch_switch(_RAIter1 __begin1, _RAIter1 __end1,
15ac3c72 JS	77	_RAIter2 __begin2, _Predicate __pred,
15ac3c72 JS	78	random_access_iterator_tag, random_access_iterator_tag)
531898c3 PC	79	{
531898c3 PC	80	if (_GLIBCXX_PARALLEL_CONDITION(true))
15ac3c72 JS	81	{
	82	_RAIter1 __res =
	83	__gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred,
	84	__gnu_parallel::
	85	__mismatch_selector()).first;
	86	return make_pair(__res , __begin2 + (__res - __begin1));
	87	}
531898c3	88	else
12ffa228	89	return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred);
531898c3	90	}
c2ba9709 JS	91
c2ba9709 JS	92	// Public interface
1acba85b JS	93	template<typename _IIter1, typename _IIter2>
	94	inline pair<_IIter1, _IIter2>
	95	mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
531898c3	96	{
089ccc04 FD	97	typedef __gnu_parallel::_EqualTo<
	98	typename std::iterator_traits<_IIter1>::value_type,
	99	typename std::iterator_traits<_IIter2>::value_type> _EqualTo;
531898c3	100
4459d22e	101	return __mismatch_switch(__begin1, __end1, __begin2, _EqualTo(),
089ccc04 FD	102	std::__iterator_category(__begin1),
089ccc04 FD	103	std::__iterator_category(__begin2));
531898c3	104	}
c2ba9709 JS	105
c2ba9709 JS	106	// Public interface
15ac3c72	107	template<typename _IIter1, typename _IIter2, typename _Predicate>
1acba85b JS	108	inline pair<_IIter1, _IIter2>
1acba85b JS	109	mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
15ac3c72	110	_Predicate __pred)
531898c3	111	{
15ac3c72	112	return __mismatch_switch(__begin1, __end1, __begin2, __pred,
089ccc04 FD	113	std::__iterator_category(__begin1),
089ccc04 FD	114	std::__iterator_category(__begin2));
531898c3	115	}
c2ba9709	116
ea89b248	117	#if __cplusplus > 201103L
089ccc04	118	// Sequential fallback.
ea89b248 FD	119	template<typename _InputIterator1, typename _InputIterator2>
	120	inline pair<_InputIterator1, _InputIterator2>
	121	mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
089ccc04 FD	122	_InputIterator2 __first2, _InputIterator2 __last2,
089ccc04 FD	123	__gnu_parallel::sequential_tag)
ea89b248 FD	124	{ return _GLIBCXX_STD_A::mismatch(__first1, __last1, __first2, __last2); }
ea89b248 FD	125
089ccc04	126	// Sequential fallback.
ea89b248 FD	127	template<typename _InputIterator1, typename _InputIterator2,
	128	typename _BinaryPredicate>
	129	inline pair<_InputIterator1, _InputIterator2>
	130	mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
	131	_InputIterator2 __first2, _InputIterator2 __last2,
089ccc04 FD	132	_BinaryPredicate __binary_pred,
089ccc04 FD	133	__gnu_parallel::sequential_tag)
ea89b248 FD	134	{
	135	return _GLIBCXX_STD_A::mismatch(__first1, __last1, __first2, __last2,
	136	__binary_pred);
	137	}
089ccc04 FD	138
	139	// Sequential fallback for input iterator case
	140	template<typename _IIter1, typename _IIter2,
	141	typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
	142	inline pair<_IIter1, _IIter2>
	143	__mismatch_switch(_IIter1 __begin1, _IIter1 __end1,
	144	_IIter2 __begin2, _IIter2 __end2, _Predicate __pred,
	145	_IteratorTag1, _IteratorTag2)
	146	{
	147	return _GLIBCXX_STD_A::mismatch(__begin1, __end1,
	148	__begin2, __end2, __pred);
	149	}
	150
	151	// Parallel mismatch for random access iterators
	152	template<typename _RAIter1, typename _RAIter2, typename _Predicate>
	153	pair<_RAIter1, _RAIter2>
	154	__mismatch_switch(_RAIter1 __begin1, _RAIter1 __end1,
	155	_RAIter2 __begin2, _RAIter2 __end2, _Predicate __pred,
	156	random_access_iterator_tag, random_access_iterator_tag)
	157	{
	158	if (_GLIBCXX_PARALLEL_CONDITION(true))
	159	{
	160	if ((__end2 - __begin2) < (__end1 - __begin1))
	161	__end1 = __begin1 + (__end2 - __begin2);
	162
	163	_RAIter1 __res =
	164	__gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred,
	165	__gnu_parallel::
	166	__mismatch_selector()).first;
	167	return make_pair(__res , __begin2 + (__res - __begin1));
	168	}
	169	else
	170	return _GLIBCXX_STD_A::mismatch(__begin1, __end1,
	171	__begin2, __end2, __pred);
	172	}
	173
	174	template<typename _IIter1, typename _IIter2>
	175	inline pair<_IIter1, _IIter2>
	176	mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2)
	177	{
	178	typedef __gnu_parallel::_EqualTo<
	179	typename std::iterator_traits<_IIter1>::value_type,
	180	typename std::iterator_traits<_IIter2>::value_type> _EqualTo;
	181
	182	return __mismatch_switch(__begin1, __end1, __begin2, __end2, _EqualTo(),
	183	std::__iterator_category(__begin1),
	184	std::__iterator_category(__begin2));
	185	}
	186
	187	template<typename _InputIterator1, typename _InputIterator2,
	188	typename _BinaryPredicate>
	189	inline pair<_InputIterator1, _InputIterator2>
	190	mismatch(_InputIterator1 __begin1, _InputIterator1 __end1,
	191	_InputIterator2 __begin2, _InputIterator2 __end2,
	192	_BinaryPredicate __binary_pred)
	193	{
	194	return __mismatch_switch(__begin1, __end1, __begin2, __end2,
	195	__binary_pred,
	196	std::__iterator_category(__begin1),
	197	std::__iterator_category(__begin2));
	198	}
ea89b248 FD	199	#endif
ea89b248 FD	200
4f39bf5c	201	// Sequential fallback
1acba85b	202	template<typename _IIter1, typename _IIter2>
531898c3	203	inline bool
1acba85b	204	equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
15ac3c72	205	__gnu_parallel::sequential_tag)
12ffa228	206	{ return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2); }
4f39bf5c PC	207
4f39bf5c PC	208	// Sequential fallback
15ac3c72	209	template<typename _IIter1, typename _IIter2, typename _Predicate>
531898c3	210	inline bool
1acba85b	211	equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
15ac3c72	212	_Predicate __pred, __gnu_parallel::sequential_tag)
12ffa228	213	{ return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __pred); }
4f39bf5c PC	214
4f39bf5c PC	215	// Public interface
1acba85b	216	template<typename _IIter1, typename _IIter2>
e12097ed	217	_GLIBCXX20_CONSTEXPR
531898c3	218	inline bool
1acba85b	219	equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
0e50f335	220	{
e12097ed JW	221	#if __cplusplus > 201703L
	222	if (std::is_constant_evaluated())
	223	return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2);
	224	#endif
	225
52fe3d5b JS	226	return __gnu_parallel::mismatch(__begin1, __end1, __begin2).first
52fe3d5b JS	227	== __end1;
0e50f335	228	}
4f39bf5c PC	229
4f39bf5c PC	230	// Public interface
15ac3c72	231	template<typename _IIter1, typename _IIter2, typename _Predicate>
e12097ed	232	_GLIBCXX20_CONSTEXPR
531898c3	233	inline bool
1acba85b	234	equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
15ac3c72	235	_Predicate __pred)
0e50f335	236	{
e12097ed JW	237	#if __cplusplus > 201703L
	238	if (std::is_constant_evaluated())
	239	return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __pred);
	240	#endif
	241
52fe3d5b JS	242	return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __pred).first
52fe3d5b JS	243	== __end1;
0e50f335	244	}
4f39bf5c	245
ea89b248	246	#if __cplusplus > 201103L
089ccc04 FD	247	// Sequential fallback
089ccc04 FD	248	template<typename _IIter1, typename _IIter2>
ea89b248	249	inline bool
089ccc04 FD	250	equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2,
	251	__gnu_parallel::sequential_tag)
	252	{
	253	return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2);
	254	}
ea89b248	255
089ccc04	256	// Sequential fallback
ea89b248 FD	257	template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
ea89b248 FD	258	inline bool
089ccc04 FD	259	equal(_IIter1 __begin1, _IIter1 __end1,
	260	_IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred,
	261	__gnu_parallel::sequential_tag)
ea89b248	262	{
089ccc04	263	return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2,
ea89b248 FD	264	__binary_pred);
ea89b248 FD	265	}
089ccc04 FD	266
	267	// Sequential fallback for input iterator case
	268	template<typename _IIter1, typename _IIter2,
	269	typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
	270	inline bool
	271	__equal_switch(_IIter1 __begin1, _IIter1 __end1,
	272	_IIter2 __begin2, _IIter2 __end2, _Predicate __pred,
	273	_IteratorTag1, _IteratorTag2)
	274	{
	275	return _GLIBCXX_STD_A::equal(__begin1, __end1,
	276	__begin2, __end2, __pred);
	277	}
	278
	279	// Parallel equal for random access iterators
	280	template<typename _RAIter1, typename _RAIter2, typename _Predicate>
	281	inline bool
	282	__equal_switch(_RAIter1 __begin1, _RAIter1 __end1,
	283	_RAIter2 __begin2, _RAIter2 __end2, _Predicate __pred,
	284	random_access_iterator_tag, random_access_iterator_tag)
	285	{
	286	if (_GLIBCXX_PARALLEL_CONDITION(true))
	287	{
	288	if (std::distance(__begin1, __end1)
	289	!= std::distance(__begin2, __end2))
	290	return false;
	291
	292	return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __end2,
	293	__pred).first == __end1;
	294	}
	295	else
	296	return _GLIBCXX_STD_A::equal(__begin1, __end1,
	297	__begin2, __end2, __pred);
	298	}
	299
	300	template<typename _IIter1, typename _IIter2>
e12097ed	301	_GLIBCXX20_CONSTEXPR
089ccc04 FD	302	inline bool
	303	equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2)
	304	{
e12097ed JW	305	#if __cplusplus > 201703L
	306	if (std::is_constant_evaluated())
	307	return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2);
	308	#endif
	309
089ccc04 FD	310	typedef __gnu_parallel::_EqualTo<
	311	typename std::iterator_traits<_IIter1>::value_type,
	312	typename std::iterator_traits<_IIter2>::value_type> _EqualTo;
	313
	314	return __equal_switch(__begin1, __end1, __begin2, __end2, _EqualTo(),
	315	std::__iterator_category(__begin1),
	316	std::__iterator_category(__begin2));
	317	}
	318
	319	template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
e12097ed	320	_GLIBCXX20_CONSTEXPR
089ccc04 FD	321	inline bool
	322	equal(_IIter1 __begin1, _IIter1 __end1,
	323	_IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred)
	324	{
e12097ed JW	325	#if __cplusplus > 201703L
	326	if (std::is_constant_evaluated())
	327	return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2,
	328	__binary_pred);
	329	#endif
	330
089ccc04 FD	331	return __equal_switch(__begin1, __end1, __begin2, __end2, __binary_pred,
	332	std::__iterator_category(__begin1),
	333	std::__iterator_category(__begin2));
	334	}
e12097ed	335	#endif // C++14
ea89b248	336
c2ba9709	337	// Sequential fallback
1acba85b	338	template<typename _IIter1, typename _IIter2>
531898c3	339	inline bool
1acba85b	340	lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
15ac3c72 JS	341	_IIter2 __begin2, _IIter2 __end2,
15ac3c72 JS	342	__gnu_parallel::sequential_tag)
12ffa228	343	{ return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
15ac3c72	344	__begin2, __end2); }
c2ba9709 JS	345
c2ba9709 JS	346	// Sequential fallback
15ac3c72	347	template<typename _IIter1, typename _IIter2, typename _Predicate>
531898c3	348	inline bool
1acba85b	349	lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
15ac3c72 JS	350	_IIter2 __begin2, _IIter2 __end2,
15ac3c72 JS	351	_Predicate __pred, __gnu_parallel::sequential_tag)
12ffa228	352	{ return _GLIBCXX_STD_A::lexicographical_compare(
15ac3c72	353	__begin1, __end1, __begin2, __end2, __pred); }
c2ba9709 JS	354
c2ba9709 JS	355	// Sequential fallback for input iterator case
1acba85b	356	template<typename _IIter1, typename _IIter2,
15ac3c72	357	typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
531898c3	358	inline bool
15ac3c72 JS	359	__lexicographical_compare_switch(_IIter1 __begin1, _IIter1 __end1,
	360	_IIter2 __begin2, _IIter2 __end2,
	361	_Predicate __pred,
	362	_IteratorTag1, _IteratorTag2)
12ffa228	363	{ return _GLIBCXX_STD_A::lexicographical_compare(
15ac3c72	364	__begin1, __end1, __begin2, __end2, __pred); }
c2ba9709 JS	365
	366	// Parallel lexicographical_compare for random access iterators
	367	// Limitation: Both valuetypes must be the same
15ac3c72	368	template<typename _RAIter1, typename _RAIter2, typename _Predicate>
531898c3	369	bool
15ac3c72 JS	370	__lexicographical_compare_switch(_RAIter1 __begin1, _RAIter1 __end1,
	371	_RAIter2 __begin2, _RAIter2 __end2,
	372	_Predicate __pred,
	373	random_access_iterator_tag,
	374	random_access_iterator_tag)
531898c3 PC	375	{
531898c3 PC	376	if (_GLIBCXX_PARALLEL_CONDITION(true))
15ac3c72 JS	377	{
	378	typedef iterator_traits<_RAIter1> _TraitsType1;
	379	typedef typename _TraitsType1::value_type _ValueType1;
	380
	381	typedef iterator_traits<_RAIter2> _TraitsType2;
	382	typedef typename _TraitsType2::value_type _ValueType2;
	383
	384	typedef __gnu_parallel::
2a2e7f9d	385	_EqualFromLess<_ValueType1, _ValueType2, _Predicate>
15ac3c72 JS	386	_EqualFromLessCompare;
	387
	388	// Longer sequence in first place.
	389	if ((__end1 - __begin1) < (__end2 - __begin2))
	390	{
	391	typedef pair<_RAIter1, _RAIter2> _SpotType;
	392	_SpotType __mm = __mismatch_switch(__begin1, __end1, __begin2,
	393	_EqualFromLessCompare(__pred),
	394	random_access_iterator_tag(),
	395	random_access_iterator_tag());
	396
	397	return (__mm.first == __end1)
	398	\|\| bool(__pred(__mm.first, __mm.second));
	399	}
	400	else
	401	{
	402	typedef pair<_RAIter2, _RAIter1> _SpotType;
	403	_SpotType __mm = __mismatch_switch(__begin2, __end2, __begin1,
	404	_EqualFromLessCompare(__pred),
	405	random_access_iterator_tag(),
	406	random_access_iterator_tag());
	407
	408	return (__mm.first != __end2)
	409	&& bool(__pred(__mm.second, __mm.first));
	410	}
	411	}
531898c3	412	else
12ffa228	413	return _GLIBCXX_STD_A::lexicographical_compare(
15ac3c72	414	__begin1, __end1, __begin2, __end2, __pred);
531898c3	415	}
c2ba9709 JS	416
c2ba9709 JS	417	// Public interface
1acba85b	418	template<typename _IIter1, typename _IIter2>
e12097ed	419	_GLIBCXX20_CONSTEXPR
531898c3	420	inline bool
1acba85b	421	lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
15ac3c72	422	_IIter2 __begin2, _IIter2 __end2)
531898c3	423	{
e12097ed JW	424	#if __cplusplus > 201703L
	425	if (std::is_constant_evaluated())
	426	return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
	427	__begin2, __end2);
	428	#endif
	429
1acba85b JS	430	typedef iterator_traits<_IIter1> _TraitsType1;
	431	typedef typename _TraitsType1::value_type _ValueType1;
	432	typedef typename _TraitsType1::iterator_category _IteratorCategory1;
	433
	434	typedef iterator_traits<_IIter2> _TraitsType2;
	435	typedef typename _TraitsType2::value_type _ValueType2;
	436	typedef typename _TraitsType2::iterator_category _IteratorCategory2;
	437	typedef __gnu_parallel::_Less<_ValueType1, _ValueType2> _LessType;
	438
15ac3c72 JS	439	return __lexicographical_compare_switch(
	440	__begin1, __end1, __begin2, __end2, _LessType(),
	441	_IteratorCategory1(), _IteratorCategory2());
531898c3	442	}
c2ba9709 JS	443
c2ba9709 JS	444	// Public interface
15ac3c72	445	template<typename _IIter1, typename _IIter2, typename _Predicate>
e12097ed	446	_GLIBCXX20_CONSTEXPR
531898c3	447	inline bool
1acba85b	448	lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
15ac3c72 JS	449	_IIter2 __begin2, _IIter2 __end2,
15ac3c72 JS	450	_Predicate __pred)
531898c3	451	{
e12097ed JW	452	#if __cplusplus > 201703L
	453	if (std::is_constant_evaluated())
	454	return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
	455	__begin2, __end2,
	456	__pred);
	457	#endif
	458
1acba85b JS	459	typedef iterator_traits<_IIter1> _TraitsType1;
1acba85b JS	460	typedef typename _TraitsType1::iterator_category _IteratorCategory1;
531898c3	461
1acba85b JS	462	typedef iterator_traits<_IIter2> _TraitsType2;
1acba85b JS	463	typedef typename _TraitsType2::iterator_category _IteratorCategory2;
531898c3	464
15ac3c72 JS	465	return __lexicographical_compare_switch(
	466	__begin1, __end1, __begin2, __end2, __pred,
	467	_IteratorCategory1(), _IteratorCategory2());
531898c3	468	}
9c24e97a JW	469
	470	#if __cpp_lib_three_way_comparison
	471	using _GLIBCXX_STD_A::lexicographical_compare_three_way;
	472	#endif
c2ba9709 JS	473	} // end namespace
	474	} // end namespace
	475
cbcd1e45	476	#endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */