| // -*- C++ -*- |
| |
| // Copyright (C) 2007, 2008, 2009 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/tags.h> |
| #include <parallel/settings.h> |
| #include <parallel/find.h> |
| #include <parallel/find_selectors.h> |
| |
| namespace std |
| { |
| 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_P::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_P::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_P::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_P::mismatch(__begin1, __end1, __begin2, __pred); |
| } |
| |
| // Public interface |
| template<typename _IIter1, typename _IIter2> |
| 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; |
| |
| return __mismatch_switch(__begin1, __end1, __begin2, _EqualTo(), |
| _IteratorCategory1(), _IteratorCategory2()); |
| } |
| |
| // Public interface |
| template<typename _IIter1, typename _IIter2, typename _Predicate> |
| inline pair<_IIter1, _IIter2> |
| 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()); |
| } |
| |
| // Sequential fallback |
| template<typename _IIter1, typename _IIter2> |
| inline bool |
| equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::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_P::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; |
| } |
| |
| // 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_P::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_P::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_P::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_P::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 */ |
