| // -*- 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 InputIterator1, typename InputIterator2> |
| inline pair<InputIterator1, InputIterator2> |
| mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2); } |
| |
| // Sequential fallback |
| template<typename InputIterator1, typename InputIterator2, |
| typename Predicate> |
| inline pair<InputIterator1, InputIterator2> |
| mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, |
| Predicate pred, __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); } |
| |
| // Sequential fallback for input iterator case |
| template<typename InputIterator1, typename InputIterator2, |
| typename Predicate, typename IteratorTag1, typename IteratorTag2> |
| inline pair<InputIterator1, InputIterator2> |
| mismatch_switch(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, Predicate pred, IteratorTag1, |
| IteratorTag2) |
| { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); } |
| |
| // Parallel mismatch for random access iterators |
| template<typename RandomAccessIterator1, typename RandomAccessIterator2, |
| typename Predicate> |
| pair<RandomAccessIterator1, RandomAccessIterator2> |
| mismatch_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, |
| RandomAccessIterator2 begin2, Predicate pred, |
| random_access_iterator_tag, random_access_iterator_tag) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION(true)) |
| { |
| RandomAccessIterator1 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 InputIterator1, typename InputIterator2> |
| inline pair<InputIterator1, InputIterator2> |
| mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2) |
| { |
| typedef std::iterator_traits<InputIterator1> iterator1_traits; |
| typedef std::iterator_traits<InputIterator2> iterator2_traits; |
| typedef typename iterator1_traits::value_type value1_type; |
| typedef typename iterator2_traits::value_type value2_type; |
| typedef typename iterator1_traits::iterator_category iterator1_category; |
| typedef typename iterator2_traits::iterator_category iterator2_category; |
| |
| typedef __gnu_parallel::equal_to<value1_type, value2_type> equal_to_type; |
| |
| return mismatch_switch(begin1, end1, begin2, equal_to_type(), |
| iterator1_category(), iterator2_category()); |
| } |
| |
| // Public interface |
| template<typename InputIterator1, typename InputIterator2, |
| typename Predicate> |
| inline pair<InputIterator1, InputIterator2> |
| mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, |
| Predicate pred) |
| { |
| typedef std::iterator_traits<InputIterator1> iterator1_traits; |
| typedef std::iterator_traits<InputIterator2> iterator2_traits; |
| typedef typename iterator1_traits::iterator_category iterator1_category; |
| typedef typename iterator2_traits::iterator_category iterator2_category; |
| |
| return mismatch_switch(begin1, end1, begin2, pred, iterator1_category(), |
| iterator2_category()); |
| } |
| |
| // Sequential fallback |
| template<typename InputIterator1, typename InputIterator2> |
| inline bool |
| equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::equal(begin1, end1, begin2); } |
| |
| // Sequential fallback |
| template<typename InputIterator1, typename InputIterator2, |
| typename Predicate> |
| inline bool |
| equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, |
| Predicate pred, __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::equal(begin1, end1, begin2, pred); } |
| |
| // Public interface |
| template<typename InputIterator1, typename InputIterator2> |
| inline bool |
| equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2) |
| { return mismatch(begin1, end1, begin2).first == end1; } |
| |
| // Public interface |
| template<typename InputIterator1, typename InputIterator2, |
| typename Predicate> |
| inline bool |
| equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, |
| Predicate pred) |
| { return mismatch(begin1, end1, begin2, pred).first == end1; } |
| |
| // Sequential fallback |
| template<typename InputIterator1, typename InputIterator2> |
| inline bool |
| lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 end2, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, |
| begin2, end2); } |
| |
| // Sequential fallback |
| template<typename InputIterator1, typename InputIterator2, |
| typename Predicate> |
| inline bool |
| lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 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 InputIterator1, typename InputIterator2, |
| typename Predicate, typename IteratorTag1, typename IteratorTag2> |
| inline bool |
| lexicographical_compare_switch(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 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 RandomAccessIterator1, typename RandomAccessIterator2, |
| typename Predicate> |
| bool |
| lexicographical_compare_switch(RandomAccessIterator1 begin1, |
| RandomAccessIterator1 end1, |
| RandomAccessIterator2 begin2, |
| RandomAccessIterator2 end2, Predicate pred, |
| random_access_iterator_tag, |
| random_access_iterator_tag) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION(true)) |
| { |
| typedef iterator_traits<RandomAccessIterator1> traits1_type; |
| typedef typename traits1_type::value_type value1_type; |
| |
| typedef iterator_traits<RandomAccessIterator2> traits2_type; |
| typedef typename traits2_type::value_type value2_type; |
| |
| typedef __gnu_parallel::equal_from_less<Predicate, value1_type, |
| value2_type> equal_type; |
| |
| // Longer sequence in first place. |
| if ((end1 - begin1) < (end2 - begin2)) |
| { |
| typedef pair<RandomAccessIterator1, RandomAccessIterator2> |
| pair_type; |
| pair_type mm = mismatch_switch(begin1, end1, begin2, |
| equal_type(pred), |
| random_access_iterator_tag(), |
| random_access_iterator_tag()); |
| |
| return (mm.first == end1) || bool(pred(*mm.first, *mm.second)); |
| } |
| else |
| { |
| typedef pair<RandomAccessIterator2, RandomAccessIterator1> |
| pair_type; |
| pair_type mm = mismatch_switch(begin2, end2, begin1, |
| equal_type(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 InputIterator1, typename InputIterator2> |
| inline bool |
| lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 end2) |
| { |
| typedef iterator_traits<InputIterator1> traits1_type; |
| typedef typename traits1_type::value_type value1_type; |
| typedef typename traits1_type::iterator_category iterator1_category; |
| |
| typedef iterator_traits<InputIterator2> traits2_type; |
| typedef typename traits2_type::value_type value2_type; |
| typedef typename traits2_type::iterator_category iterator2_category; |
| typedef __gnu_parallel::less<value1_type, value2_type> less_type; |
| |
| return lexicographical_compare_switch(begin1, end1, begin2, end2, |
| less_type(), iterator1_category(), |
| iterator2_category()); |
| } |
| |
| // Public interface |
| template<typename InputIterator1, typename InputIterator2, |
| typename Predicate> |
| inline bool |
| lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 end2, |
| Predicate pred) |
| { |
| typedef iterator_traits<InputIterator1> traits1_type; |
| typedef typename traits1_type::iterator_category iterator1_category; |
| |
| typedef iterator_traits<InputIterator2> traits2_type; |
| typedef typename traits2_type::iterator_category iterator2_category; |
| |
| return lexicographical_compare_switch(begin1, end1, begin2, end2, pred, |
| iterator1_category(), |
| iterator2_category()); |
| } |
| } // end namespace |
| } // end namespace |
| |
| #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */ |
