algobase.h
Go to the documentation of this file.
// -*- C++ -*-
// Copyright (C) 2007-2018 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>
inline bool
equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
{
return __gnu_parallel::mismatch(__begin1, __end1, __begin2).first
== __end1;
}
// Public interface
template<typename _IIter1, typename _IIter2, typename _Predicate>
inline bool
equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
_Predicate __pred)
{
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>
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
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>
inline bool
lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
_IIter2 __begin2, _IIter2 __end2)
{
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>
inline bool
lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
_IIter2 __begin2, _IIter2 __end2,
_Predicate __pred)
{
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());
}
} // end namespace
} // end namespace
#endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */
algorithmfwd.h
stl_algobase.h
__gnu_parallel::_Less
Similar to std::less, but allows two different types.
Definition: parallel/base.h:252
base.h
Sequential helper functions. This file is a GNU parallel extension to the Standard C++ Library...
std::make_pair
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
Definition: stl_pair.h:519
find.h
Parallel implementation base for std::find(), std::equal() and related functions. This file is a GNU ...
find_selectors.h
_Function objects representing different tasks to be plugged into the parallel find algorithm...
std
ISO C++ entities toplevel namespace is std.
std::distance
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Definition: stl_iterator_base_funcs.h:138
_GLIBCXX_PARALLEL_CONDITION
#define _GLIBCXX_PARALLEL_CONDITION(__c)
Determine at compile(?)-time if the parallel variant of an algorithm should be called.
Definition: settings.h:95
__gnu_parallel::_EqualTo
Similar to std::equal_to, but allows two different types.
Definition: parallel/base.h:244
__gnu_parallel::sequential_tag
Forces sequential execution at compile time.
Definition: tags.h:42
__gnu_parallel::__find_template
std::pair< _RAIter1, _RAIter2 > __find_template(_RAIter1 __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred, _Selector __selector)
Parallel std::find, switch for different algorithms.
Definition: find.h:60
std::__iterator_category
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
Definition: stl_iterator_base_types.h:205
__gnu_parallel
GNU parallel code for public use.
Definition: balanced_quicksort.h:61