diff options
Diffstat (limited to 'gcc-4.4.3/libstdc++-v3/include/parallel/algo.h')
| -rw-r--r-- | gcc-4.4.3/libstdc++-v3/include/parallel/algo.h | 2364 |
1 files changed, 0 insertions, 2364 deletions
diff --git a/gcc-4.4.3/libstdc++-v3/include/parallel/algo.h b/gcc-4.4.3/libstdc++-v3/include/parallel/algo.h deleted file mode 100644 index a0fbd8d91..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/parallel/algo.h +++ /dev/null @@ -1,2364 +0,0 @@ -// -*- 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/algo.h - * @brief Parallel STL function calls corresponding to the stl_algo.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_ALGO_H -#define _GLIBCXX_PARALLEL_ALGO_H 1 - -#include <parallel/algorithmfwd.h> -#include <bits/stl_algobase.h> -#include <bits/stl_algo.h> -#include <parallel/iterator.h> -#include <parallel/base.h> -#include <parallel/sort.h> -#include <parallel/workstealing.h> -#include <parallel/par_loop.h> -#include <parallel/omp_loop.h> -#include <parallel/omp_loop_static.h> -#include <parallel/for_each_selectors.h> -#include <parallel/for_each.h> -#include <parallel/find.h> -#include <parallel/find_selectors.h> -#include <parallel/search.h> -#include <parallel/random_shuffle.h> -#include <parallel/partition.h> -#include <parallel/merge.h> -#include <parallel/unique_copy.h> -#include <parallel/set_operations.h> - -namespace std -{ -namespace __parallel -{ - // Sequential fallback - template<typename InputIterator, typename Function> - inline Function - for_each(InputIterator begin, InputIterator end, Function f, - __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::for_each(begin, end, f); } - - - // Sequential fallback for input iterator case - template<typename InputIterator, typename Function, typename IteratorTag> - inline Function - for_each_switch(InputIterator begin, InputIterator end, Function f, - IteratorTag) - { return for_each(begin, end, f, __gnu_parallel::sequential_tag()); } - - // Parallel algorithm for random access iterators - template<typename RandomAccessIterator, typename Function> - Function - for_each_switch(RandomAccessIterator begin, RandomAccessIterator end, - Function f, random_access_iterator_tag, - __gnu_parallel::_Parallelism parallelism_tag - = __gnu_parallel::parallel_balanced) - { - if (_GLIBCXX_PARALLEL_CONDITION( - static_cast<__gnu_parallel::sequence_index_t>(end - begin) - >= __gnu_parallel::_Settings::get().for_each_minimal_n - && __gnu_parallel::is_parallel(parallelism_tag))) - { - bool dummy; - __gnu_parallel::for_each_selector<RandomAccessIterator> functionality; - - return __gnu_parallel:: - for_each_template_random_access(begin, end, f, functionality, - __gnu_parallel::dummy_reduct(), - true, dummy, -1, parallelism_tag); - } - else - return for_each(begin, end, f, __gnu_parallel::sequential_tag()); - } - - // Public interface - template<typename Iterator, typename Function> - inline Function - for_each(Iterator begin, Iterator end, Function f, - __gnu_parallel::_Parallelism parallelism_tag) - { - typedef std::iterator_traits<Iterator> iterator_traits; - typedef typename iterator_traits::iterator_category iterator_category; - return for_each_switch(begin, end, f, iterator_category(), - parallelism_tag); - } - - template<typename Iterator, typename Function> - inline Function - for_each(Iterator begin, Iterator end, Function f) - { - typedef std::iterator_traits<Iterator> iterator_traits; - typedef typename iterator_traits::iterator_category iterator_category; - return for_each_switch(begin, end, f, iterator_category()); - } - - - // Sequential fallback - template<typename InputIterator, typename T> - inline InputIterator - find(InputIterator begin, InputIterator end, const T& val, - __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::find(begin, end, val); } - - // Sequential fallback for input iterator case - template<typename InputIterator, typename T, typename IteratorTag> - inline InputIterator - find_switch(InputIterator begin, InputIterator end, const T& val, - IteratorTag) - { return _GLIBCXX_STD_P::find(begin, end, val); } - - // Parallel find for random access iterators - template<typename RandomAccessIterator, typename T> - RandomAccessIterator - find_switch(RandomAccessIterator begin, RandomAccessIterator end, - const T& val, random_access_iterator_tag) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - - if (_GLIBCXX_PARALLEL_CONDITION(true)) - { - binder2nd<__gnu_parallel::equal_to<value_type, const T&> > - comp(__gnu_parallel::equal_to<value_type, const T&>(), val); - return __gnu_parallel::find_template(begin, end, begin, comp, - __gnu_parallel:: - find_if_selector()).first; - } - else - return _GLIBCXX_STD_P::find(begin, end, val); - } - - // Public interface - template<typename InputIterator, typename T> - inline InputIterator - find(InputIterator begin, InputIterator end, const T& val) - { - typedef std::iterator_traits<InputIterator> iterator_traits; - typedef typename iterator_traits::iterator_category iterator_category; - return find_switch(begin, end, val, iterator_category()); - } - - // Sequential fallback - template<typename InputIterator, typename Predicate> - inline InputIterator - find_if(InputIterator begin, InputIterator end, Predicate pred, - __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::find_if(begin, end, pred); } - - // Sequential fallback for input iterator case - template<typename InputIterator, typename Predicate, typename IteratorTag> - inline InputIterator - find_if_switch(InputIterator begin, InputIterator end, Predicate pred, - IteratorTag) - { return _GLIBCXX_STD_P::find_if(begin, end, pred); } - - // Parallel find_if for random access iterators - template<typename RandomAccessIterator, typename Predicate> - RandomAccessIterator - find_if_switch(RandomAccessIterator begin, RandomAccessIterator end, - Predicate pred, random_access_iterator_tag) - { - if (_GLIBCXX_PARALLEL_CONDITION(true)) - return __gnu_parallel::find_template(begin, end, begin, pred, - __gnu_parallel:: - find_if_selector()).first; - else - return _GLIBCXX_STD_P::find_if(begin, end, pred); - } - - // Public interface - template<typename InputIterator, typename Predicate> - inline InputIterator - find_if(InputIterator begin, InputIterator end, Predicate pred) - { - typedef std::iterator_traits<InputIterator> iterator_traits; - typedef typename iterator_traits::iterator_category iterator_category; - return find_if_switch(begin, end, pred, iterator_category()); - } - - // Sequential fallback - template<typename InputIterator, typename ForwardIterator> - inline InputIterator - find_first_of(InputIterator begin1, InputIterator end1, - ForwardIterator begin2, ForwardIterator end2, - __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::find_first_of(begin1, end1, begin2, end2); } - - // Sequential fallback - template<typename InputIterator, typename ForwardIterator, - typename BinaryPredicate> - inline InputIterator - find_first_of(InputIterator begin1, InputIterator end1, - ForwardIterator begin2, ForwardIterator end2, - BinaryPredicate comp, __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::find_first_of(begin1, end1, begin2, end2, comp); } - - // Sequential fallback for input iterator type - template<typename InputIterator, typename ForwardIterator, - typename IteratorTag1, typename IteratorTag2> - inline InputIterator - find_first_of_switch(InputIterator begin1, InputIterator end1, - ForwardIterator begin2, ForwardIterator end2, - IteratorTag1, IteratorTag2) - { return find_first_of(begin1, end1, begin2, end2, - __gnu_parallel::sequential_tag()); } - - // Parallel algorithm for random access iterators - template<typename RandomAccessIterator, typename ForwardIterator, - typename BinaryPredicate, typename IteratorTag> - inline RandomAccessIterator - find_first_of_switch(RandomAccessIterator begin1, - RandomAccessIterator end1, - ForwardIterator begin2, ForwardIterator end2, - BinaryPredicate comp, random_access_iterator_tag, - IteratorTag) - { - return __gnu_parallel:: - find_template(begin1, end1, begin1, comp, - __gnu_parallel::find_first_of_selector - <ForwardIterator>(begin2, end2)).first; - } - - // Sequential fallback for input iterator type - template<typename InputIterator, typename ForwardIterator, - typename BinaryPredicate, typename IteratorTag1, - typename IteratorTag2> - inline InputIterator - find_first_of_switch(InputIterator begin1, InputIterator end1, - ForwardIterator begin2, ForwardIterator end2, - BinaryPredicate comp, IteratorTag1, IteratorTag2) - { return find_first_of(begin1, end1, begin2, end2, comp, - __gnu_parallel::sequential_tag()); } - - // Public interface - template<typename InputIterator, typename ForwardIterator, - typename BinaryPredicate> - inline InputIterator - find_first_of(InputIterator begin1, InputIterator end1, - ForwardIterator begin2, ForwardIterator end2, - BinaryPredicate comp) - { - typedef std::iterator_traits<InputIterator> iteratori_traits; - typedef std::iterator_traits<ForwardIterator> iteratorf_traits; - typedef typename iteratori_traits::iterator_category iteratori_category; - typedef typename iteratorf_traits::iterator_category iteratorf_category; - - return find_first_of_switch(begin1, end1, begin2, end2, comp, - iteratori_category(), iteratorf_category()); - } - - // Public interface, insert default comparator - template<typename InputIterator, typename ForwardIterator> - inline InputIterator - find_first_of(InputIterator begin1, InputIterator end1, - ForwardIterator begin2, ForwardIterator end2) - { - typedef std::iterator_traits<InputIterator> iteratori_traits; - typedef std::iterator_traits<ForwardIterator> iteratorf_traits; - typedef typename iteratori_traits::value_type valuei_type; - typedef typename iteratorf_traits::value_type valuef_type; - - return find_first_of(begin1, end1, begin2, end2, __gnu_parallel:: - equal_to<valuei_type, valuef_type>()); - } - - // Sequential fallback - template<typename InputIterator, typename OutputIterator> - inline OutputIterator - unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out, - __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::unique_copy(begin1, end1, out); } - - // Sequential fallback - template<typename InputIterator, typename OutputIterator, - typename Predicate> - inline OutputIterator - unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out, - Predicate pred, __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::unique_copy(begin1, end1, out, pred); } - - // Sequential fallback for input iterator case - template<typename InputIterator, typename OutputIterator, - typename Predicate, typename IteratorTag1, typename IteratorTag2> - inline OutputIterator - unique_copy_switch(InputIterator begin, InputIterator last, - OutputIterator out, Predicate pred, - IteratorTag1, IteratorTag2) - { return _GLIBCXX_STD_P::unique_copy(begin, last, out, pred); } - - // Parallel unique_copy for random access iterators - template<typename RandomAccessIterator, typename RandomAccessOutputIterator, - typename Predicate> - RandomAccessOutputIterator - unique_copy_switch(RandomAccessIterator begin, RandomAccessIterator last, - RandomAccessOutputIterator out, Predicate pred, - random_access_iterator_tag, random_access_iterator_tag) - { - if (_GLIBCXX_PARALLEL_CONDITION( - static_cast<__gnu_parallel::sequence_index_t>(last - begin) - > __gnu_parallel::_Settings::get().unique_copy_minimal_n)) - return __gnu_parallel::parallel_unique_copy(begin, last, out, pred); - else - return _GLIBCXX_STD_P::unique_copy(begin, last, out, pred); - } - - // Public interface - template<typename InputIterator, typename OutputIterator> - inline OutputIterator - unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out) - { - typedef std::iterator_traits<InputIterator> iteratori_traits; - typedef std::iterator_traits<OutputIterator> iteratoro_traits; - typedef typename iteratori_traits::iterator_category iteratori_category; - typedef typename iteratori_traits::value_type value_type; - typedef typename iteratoro_traits::iterator_category iteratoro_category; - - return unique_copy_switch(begin1, end1, out, equal_to<value_type>(), - iteratori_category(), iteratoro_category()); - } - - // Public interface - template<typename InputIterator, typename OutputIterator, typename Predicate> - inline OutputIterator - unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out, - Predicate pred) - { - typedef std::iterator_traits<InputIterator> iteratori_traits; - typedef std::iterator_traits<OutputIterator> iteratoro_traits; - typedef typename iteratori_traits::iterator_category iteratori_category; - typedef typename iteratoro_traits::iterator_category iteratoro_category; - - return unique_copy_switch(begin1, end1, out, pred, iteratori_category(), - iteratoro_category()); - } - - // Sequential fallback - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator> - inline OutputIterator - set_union(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out, __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::set_union(begin1, end1, begin2, end2, out); } - - // Sequential fallback - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename Predicate> - inline OutputIterator - set_union(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out, Predicate pred, - __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::set_union(begin1, end1, - begin2, end2, out, pred); } - - // Sequential fallback for input iterator case - template<typename InputIterator1, typename InputIterator2, - typename Predicate, typename OutputIterator, - typename IteratorTag1, typename IteratorTag2, typename IteratorTag3> - inline OutputIterator - set_union_switch(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator result, Predicate pred, IteratorTag1, - IteratorTag2, IteratorTag3) - { return _GLIBCXX_STD_P::set_union(begin1, end1, - begin2, end2, result, pred); } - - // Parallel set_union for random access iterators - template<typename RandomAccessIterator1, typename RandomAccessIterator2, - typename OutputRandomAccessIterator, typename Predicate> - OutputRandomAccessIterator - set_union_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, - RandomAccessIterator2 begin2, RandomAccessIterator2 end2, - OutputRandomAccessIterator result, Predicate pred, - random_access_iterator_tag, random_access_iterator_tag, - random_access_iterator_tag) - { - if (_GLIBCXX_PARALLEL_CONDITION( - static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1) - >= __gnu_parallel::_Settings::get().set_union_minimal_n - || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2) - >= __gnu_parallel::_Settings::get().set_union_minimal_n)) - return __gnu_parallel::parallel_set_union(begin1, end1, - begin2, end2, result, pred); - else - return _GLIBCXX_STD_P::set_union(begin1, end1, - begin2, end2, result, pred); - } - - // Public interface - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator> - inline OutputIterator - set_union(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, OutputIterator out) - { - typedef std::iterator_traits<InputIterator1> iteratori1_traits; - typedef std::iterator_traits<InputIterator2> iteratori2_traits; - typedef std::iterator_traits<OutputIterator> iteratoro_traits; - typedef typename iteratori1_traits::iterator_category - iteratori1_category; - typedef typename iteratori2_traits::iterator_category - iteratori2_category; - typedef typename iteratoro_traits::iterator_category iteratoro_category; - typedef typename iteratori1_traits::value_type value1_type; - typedef typename iteratori2_traits::value_type value2_type; - - return set_union_switch(begin1, end1, begin2, end2, out, - __gnu_parallel::less<value1_type, value2_type>(), - iteratori1_category(), iteratori2_category(), - iteratoro_category()); - } - - // Public interface - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename Predicate> - inline OutputIterator - set_union(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out, Predicate pred) - { - typedef std::iterator_traits<InputIterator1> iteratori1_traits; - typedef std::iterator_traits<InputIterator2> iteratori2_traits; - typedef std::iterator_traits<OutputIterator> iteratoro_traits; - typedef typename iteratori1_traits::iterator_category - iteratori1_category; - typedef typename iteratori2_traits::iterator_category - iteratori2_category; - typedef typename iteratoro_traits::iterator_category iteratoro_category; - - return set_union_switch(begin1, end1, begin2, end2, out, pred, - iteratori1_category(), iteratori2_category(), - iteratoro_category()); - } - - // Sequential fallback. - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator> - inline OutputIterator - set_intersection(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out, __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::set_intersection(begin1, end1, - begin2, end2, out); } - - // Sequential fallback. - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename Predicate> - inline OutputIterator - set_intersection(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out, Predicate pred, - __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, end2, - out, pred); } - - // Sequential fallback for input iterator case - template<typename InputIterator1, typename InputIterator2, - typename Predicate, typename OutputIterator, - typename IteratorTag1, typename IteratorTag2, - typename IteratorTag3> - inline OutputIterator - set_intersection_switch(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator result, Predicate pred, - IteratorTag1, IteratorTag2, IteratorTag3) - { return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, - end2, result, pred); } - - // Parallel set_intersection for random access iterators - template<typename RandomAccessIterator1, typename RandomAccessIterator2, - typename OutputRandomAccessIterator, typename Predicate> - OutputRandomAccessIterator - set_intersection_switch(RandomAccessIterator1 begin1, - RandomAccessIterator1 end1, - RandomAccessIterator2 begin2, - RandomAccessIterator2 end2, - OutputRandomAccessIterator result, - Predicate pred, - random_access_iterator_tag, - random_access_iterator_tag, - random_access_iterator_tag) - { - if (_GLIBCXX_PARALLEL_CONDITION( - static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1) - >= __gnu_parallel::_Settings::get().set_union_minimal_n - || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2) - >= __gnu_parallel::_Settings::get().set_union_minimal_n)) - return __gnu_parallel::parallel_set_intersection(begin1, end1, begin2, - end2, result, pred); - else - return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, - end2, result, pred); - } - - // Public interface - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator> - inline OutputIterator - set_intersection(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out) - { - typedef std::iterator_traits<InputIterator1> iteratori1_traits; - typedef std::iterator_traits<InputIterator2> iteratori2_traits; - typedef std::iterator_traits<OutputIterator> iteratoro_traits; - typedef typename iteratori1_traits::iterator_category - iteratori1_category; - typedef typename iteratori2_traits::iterator_category - iteratori2_category; - typedef typename iteratoro_traits::iterator_category iteratoro_category; - typedef typename iteratori1_traits::value_type value1_type; - typedef typename iteratori2_traits::value_type value2_type; - - return set_intersection_switch(begin1, end1, begin2, end2, out, - __gnu_parallel:: - less<value1_type, value2_type>(), - iteratori1_category(), - iteratori2_category(), - iteratoro_category()); - } - - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename Predicate> - inline OutputIterator - set_intersection(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out, Predicate pred) - { - typedef std::iterator_traits<InputIterator1> iteratori1_traits; - typedef std::iterator_traits<InputIterator2> iteratori2_traits; - typedef std::iterator_traits<OutputIterator> iteratoro_traits; - typedef typename iteratori1_traits::iterator_category - iteratori1_category; - typedef typename iteratori2_traits::iterator_category - iteratori2_category; - typedef typename iteratoro_traits::iterator_category iteratoro_category; - - return set_intersection_switch(begin1, end1, begin2, end2, out, pred, - iteratori1_category(), - iteratori2_category(), - iteratoro_category()); - } - - // Sequential fallback - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator> - inline OutputIterator - set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out, - __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::set_symmetric_difference(begin1,end1, - begin2, end2, out); } - - // Sequential fallback - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename Predicate> - inline OutputIterator - set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out, Predicate pred, - __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1, begin2, - end2, out, pred); } - - // Sequential fallback for input iterator case - template<typename InputIterator1, typename InputIterator2, - typename Predicate, typename OutputIterator, - typename IteratorTag1, typename IteratorTag2, - typename IteratorTag3> - inline OutputIterator - set_symmetric_difference_switch(InputIterator1 begin1, - InputIterator1 end1, - InputIterator2 begin2, - InputIterator2 end2, - OutputIterator result, Predicate pred, - IteratorTag1, IteratorTag2, IteratorTag3) - { return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1, - begin2, end2, - result, pred); } - - // Parallel set_symmetric_difference for random access iterators - template<typename RandomAccessIterator1, typename RandomAccessIterator2, - typename OutputRandomAccessIterator, typename Predicate> - OutputRandomAccessIterator - set_symmetric_difference_switch(RandomAccessIterator1 begin1, - RandomAccessIterator1 end1, - RandomAccessIterator2 begin2, - RandomAccessIterator2 end2, - OutputRandomAccessIterator result, - Predicate pred, - random_access_iterator_tag, - random_access_iterator_tag, - random_access_iterator_tag) - { - if (_GLIBCXX_PARALLEL_CONDITION( - static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1) - >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n - || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2) - >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n)) - return __gnu_parallel::parallel_set_symmetric_difference(begin1, end1, - begin2, end2, - result, pred); - else - return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1, - begin2, end2, - result, pred); - } - - // Public interface. - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator> - inline OutputIterator - set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out) - { - typedef std::iterator_traits<InputIterator1> iteratori1_traits; - typedef std::iterator_traits<InputIterator2> iteratori2_traits; - typedef std::iterator_traits<OutputIterator> iteratoro_traits; - typedef typename iteratori1_traits::iterator_category - iteratori1_category; - typedef typename iteratori2_traits::iterator_category - iteratori2_category; - typedef typename iteratoro_traits::iterator_category iteratoro_category; - typedef typename iteratori1_traits::value_type value1_type; - typedef typename iteratori2_traits::value_type value2_type; - - return set_symmetric_difference_switch(begin1, end1, begin2, end2, out, - __gnu_parallel:: - less<value1_type, value2_type>(), - iteratori1_category(), - iteratori2_category(), - iteratoro_category()); - } - - // Public interface. - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename Predicate> - inline OutputIterator - set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out, Predicate pred) - { - typedef std::iterator_traits<InputIterator1> iteratori1_traits; - typedef std::iterator_traits<InputIterator2> iteratori2_traits; - typedef std::iterator_traits<OutputIterator> iteratoro_traits; - typedef typename iteratori1_traits::iterator_category - iteratori1_category; - typedef typename iteratori2_traits::iterator_category - iteratori2_category; - typedef typename iteratoro_traits::iterator_category iteratoro_category; - - return set_symmetric_difference_switch(begin1, end1, begin2, end2, out, - pred, iteratori1_category(), - iteratori2_category(), - iteratoro_category()); - } - - // Sequential fallback. - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator> - inline OutputIterator - set_difference(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out, __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::set_difference(begin1,end1, begin2, end2, out); } - - // Sequential fallback. - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename Predicate> - inline OutputIterator - set_difference(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out, Predicate pred, - __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::set_difference(begin1, end1, - begin2, end2, out, pred); } - - // Sequential fallback for input iterator case. - template<typename InputIterator1, typename InputIterator2, - typename Predicate, typename OutputIterator, - typename IteratorTag1, typename IteratorTag2, typename IteratorTag3> - inline OutputIterator - set_difference_switch(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator result, Predicate pred, - IteratorTag1, IteratorTag2, IteratorTag3) - { return _GLIBCXX_STD_P::set_difference(begin1, end1, - begin2, end2, result, pred); } - - // Parallel set_difference for random access iterators - template<typename RandomAccessIterator1, typename RandomAccessIterator2, - typename OutputRandomAccessIterator, typename Predicate> - OutputRandomAccessIterator - set_difference_switch(RandomAccessIterator1 begin1, - RandomAccessIterator1 end1, - RandomAccessIterator2 begin2, - RandomAccessIterator2 end2, - OutputRandomAccessIterator result, Predicate pred, - random_access_iterator_tag, - random_access_iterator_tag, - random_access_iterator_tag) - { - if (_GLIBCXX_PARALLEL_CONDITION( - static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1) - >= __gnu_parallel::_Settings::get().set_difference_minimal_n - || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2) - >= __gnu_parallel::_Settings::get().set_difference_minimal_n)) - return __gnu_parallel::parallel_set_difference(begin1, end1, - begin2, end2, - result, pred); - else - return _GLIBCXX_STD_P::set_difference(begin1, end1, - begin2, end2, result, pred); - } - - // Public interface - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator> - inline OutputIterator - set_difference(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out) - { - typedef std::iterator_traits<InputIterator1> iteratori1_traits; - typedef std::iterator_traits<InputIterator2> iteratori2_traits; - typedef std::iterator_traits<OutputIterator> iteratoro_traits; - typedef typename iteratori1_traits::iterator_category - iteratori1_category; - typedef typename iteratori2_traits::iterator_category - iteratori2_category; - typedef typename iteratoro_traits::iterator_category iteratoro_category; - typedef typename iteratori1_traits::value_type value1_type; - typedef typename iteratori2_traits::value_type value2_type; - - return set_difference_switch(begin1, end1, begin2, end2, out, - __gnu_parallel:: - less<value1_type, value2_type>(), - iteratori1_category(), - iteratori2_category(), - iteratoro_category()); - } - - // Public interface - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename Predicate> - inline OutputIterator - set_difference(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out, Predicate pred) - { - typedef std::iterator_traits<InputIterator1> iteratori1_traits; - typedef std::iterator_traits<InputIterator2> iteratori2_traits; - typedef std::iterator_traits<OutputIterator> iteratoro_traits; - typedef typename iteratori1_traits::iterator_category - iteratori1_category; - typedef typename iteratori2_traits::iterator_category - iteratori2_category; - typedef typename iteratoro_traits::iterator_category iteratoro_category; - - return set_difference_switch(begin1, end1, begin2, end2, out, pred, - iteratori1_category(), - iteratori2_category(), - iteratoro_category()); - } - - // Sequential fallback - template<typename ForwardIterator> - inline ForwardIterator - adjacent_find(ForwardIterator begin, ForwardIterator end, - __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::adjacent_find(begin, end); } - - // Sequential fallback - template<typename ForwardIterator, typename BinaryPredicate> - inline ForwardIterator - adjacent_find(ForwardIterator begin, ForwardIterator end, - BinaryPredicate binary_pred, __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::adjacent_find(begin, end, binary_pred); } - - // Parallel algorithm for random access iterators - template<typename RandomAccessIterator> - RandomAccessIterator - adjacent_find_switch(RandomAccessIterator begin, RandomAccessIterator end, - random_access_iterator_tag) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - - if (_GLIBCXX_PARALLEL_CONDITION(true)) - { - RandomAccessIterator spot = __gnu_parallel:: - find_template(begin, end - 1, begin, equal_to<value_type>(), - __gnu_parallel::adjacent_find_selector()).first; - if (spot == (end - 1)) - return end; - else - return spot; - } - else - return adjacent_find(begin, end, __gnu_parallel::sequential_tag()); - } - - // Sequential fallback for input iterator case - template<typename ForwardIterator, typename IteratorTag> - inline ForwardIterator - adjacent_find_switch(ForwardIterator begin, ForwardIterator end, - IteratorTag) - { return adjacent_find(begin, end, __gnu_parallel::sequential_tag()); } - - // Public interface - template<typename ForwardIterator> - inline ForwardIterator - adjacent_find(ForwardIterator begin, ForwardIterator end) - { - typedef iterator_traits<ForwardIterator> traits_type; - typedef typename traits_type::iterator_category iterator_category; - return adjacent_find_switch(begin, end, iterator_category()); - } - - // Sequential fallback for input iterator case - template<typename ForwardIterator, typename BinaryPredicate, - typename IteratorTag> - inline ForwardIterator - adjacent_find_switch(ForwardIterator begin, ForwardIterator end, - BinaryPredicate pred, IteratorTag) - { return adjacent_find(begin, end, pred, - __gnu_parallel::sequential_tag()); } - - // Parallel algorithm for random access iterators - template<typename RandomAccessIterator, typename BinaryPredicate> - RandomAccessIterator - adjacent_find_switch(RandomAccessIterator begin, RandomAccessIterator end, - BinaryPredicate pred, random_access_iterator_tag) - { - if (_GLIBCXX_PARALLEL_CONDITION(true)) - return __gnu_parallel::find_template(begin, end, begin, pred, - __gnu_parallel:: - adjacent_find_selector()).first; - else - return adjacent_find(begin, end, pred, - __gnu_parallel::sequential_tag()); - } - - // Public interface - template<typename ForwardIterator, typename BinaryPredicate> - inline ForwardIterator - adjacent_find(ForwardIterator begin, ForwardIterator end, - BinaryPredicate pred) - { - typedef iterator_traits<ForwardIterator> traits_type; - typedef typename traits_type::iterator_category iterator_category; - return adjacent_find_switch(begin, end, pred, iterator_category()); - } - - // Sequential fallback - template<typename InputIterator, typename T> - inline typename iterator_traits<InputIterator>::difference_type - count(InputIterator begin, InputIterator end, const T& value, - __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::count(begin, end, value); } - - // Parallel code for random access iterators - template<typename RandomAccessIterator, typename T> - typename iterator_traits<RandomAccessIterator>::difference_type - count_switch(RandomAccessIterator begin, RandomAccessIterator end, - const T& value, random_access_iterator_tag, - __gnu_parallel::_Parallelism parallelism_tag - = __gnu_parallel::parallel_unbalanced) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - typedef typename traits_type::difference_type difference_type; - typedef __gnu_parallel::sequence_index_t sequence_index_t; - - if (_GLIBCXX_PARALLEL_CONDITION( - static_cast<sequence_index_t>(end - begin) - >= __gnu_parallel::_Settings::get().count_minimal_n - && __gnu_parallel::is_parallel(parallelism_tag))) - { - __gnu_parallel::count_selector<RandomAccessIterator, difference_type> - functionality; - difference_type res = 0; - __gnu_parallel:: - for_each_template_random_access(begin, end, value, - functionality, - std::plus<sequence_index_t>(), - res, res, -1, parallelism_tag); - return res; - } - else - return count(begin, end, value, __gnu_parallel::sequential_tag()); - } - - // Sequential fallback for input iterator case. - template<typename InputIterator, typename T, typename IteratorTag> - inline typename iterator_traits<InputIterator>::difference_type - count_switch(InputIterator begin, InputIterator end, const T& value, - IteratorTag) - { return count(begin, end, value, __gnu_parallel::sequential_tag()); } - - // Public interface. - template<typename InputIterator, typename T> - inline typename iterator_traits<InputIterator>::difference_type - count(InputIterator begin, InputIterator end, const T& value, - __gnu_parallel::_Parallelism parallelism_tag) - { - typedef iterator_traits<InputIterator> traits_type; - typedef typename traits_type::iterator_category iterator_category; - return count_switch(begin, end, value, iterator_category(), - parallelism_tag); - } - - template<typename InputIterator, typename T> - inline typename iterator_traits<InputIterator>::difference_type - count(InputIterator begin, InputIterator end, const T& value) - { - typedef iterator_traits<InputIterator> traits_type; - typedef typename traits_type::iterator_category iterator_category; - return count_switch(begin, end, value, iterator_category()); - } - - - // Sequential fallback. - template<typename InputIterator, typename Predicate> - inline typename iterator_traits<InputIterator>::difference_type - count_if(InputIterator begin, InputIterator end, Predicate pred, - __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::count_if(begin, end, pred); } - - // Parallel count_if for random access iterators - template<typename RandomAccessIterator, typename Predicate> - typename iterator_traits<RandomAccessIterator>::difference_type - count_if_switch(RandomAccessIterator begin, RandomAccessIterator end, - Predicate pred, random_access_iterator_tag, - __gnu_parallel::_Parallelism parallelism_tag - = __gnu_parallel::parallel_unbalanced) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - typedef typename traits_type::difference_type difference_type; - typedef __gnu_parallel::sequence_index_t sequence_index_t; - - if (_GLIBCXX_PARALLEL_CONDITION( - static_cast<sequence_index_t>(end - begin) - >= __gnu_parallel::_Settings::get().count_minimal_n - && __gnu_parallel::is_parallel(parallelism_tag))) - { - difference_type res = 0; - __gnu_parallel:: - count_if_selector<RandomAccessIterator, difference_type> - functionality; - __gnu_parallel:: - for_each_template_random_access(begin, end, pred, - functionality, - std::plus<sequence_index_t>(), - res, res, -1, parallelism_tag); - return res; - } - else - return count_if(begin, end, pred, __gnu_parallel::sequential_tag()); - } - - // Sequential fallback for input iterator case. - template<typename InputIterator, typename Predicate, typename IteratorTag> - inline typename iterator_traits<InputIterator>::difference_type - count_if_switch(InputIterator begin, InputIterator end, Predicate pred, - IteratorTag) - { return count_if(begin, end, pred, __gnu_parallel::sequential_tag()); } - - // Public interface. - template<typename InputIterator, typename Predicate> - inline typename iterator_traits<InputIterator>::difference_type - count_if(InputIterator begin, InputIterator end, Predicate pred, - __gnu_parallel::_Parallelism parallelism_tag) - { - typedef iterator_traits<InputIterator> traits_type; - typedef typename traits_type::iterator_category iterator_category; - return count_if_switch(begin, end, pred, iterator_category(), - parallelism_tag); - } - - template<typename InputIterator, typename Predicate> - inline typename iterator_traits<InputIterator>::difference_type - count_if(InputIterator begin, InputIterator end, Predicate pred) - { - typedef iterator_traits<InputIterator> traits_type; - typedef typename traits_type::iterator_category iterator_category; - return count_if_switch(begin, end, pred, iterator_category()); - } - - - // Sequential fallback. - template<typename ForwardIterator1, typename ForwardIterator2> - inline ForwardIterator1 - search(ForwardIterator1 begin1, ForwardIterator1 end1, - ForwardIterator2 begin2, ForwardIterator2 end2, - __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::search(begin1, end1, begin2, end2); } - - // Parallel algorithm for random access iterator - template<typename RandomAccessIterator1, typename RandomAccessIterator2> - RandomAccessIterator1 - search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, - RandomAccessIterator2 begin2, RandomAccessIterator2 end2, - random_access_iterator_tag, random_access_iterator_tag) - { - typedef std::iterator_traits<RandomAccessIterator1> iterator1_traits; - typedef typename iterator1_traits::value_type value1_type; - typedef std::iterator_traits<RandomAccessIterator2> iterator2_traits; - typedef typename iterator2_traits::value_type value2_type; - - if (_GLIBCXX_PARALLEL_CONDITION(true)) - return __gnu_parallel:: - search_template(begin1, end1, begin2, end2, __gnu_parallel:: - equal_to<value1_type, value2_type>()); - else - return search(begin1, end1, begin2, end2, - __gnu_parallel::sequential_tag()); - } - - // Sequential fallback for input iterator case - template<typename ForwardIterator1, typename ForwardIterator2, - typename IteratorTag1, typename IteratorTag2> - inline ForwardIterator1 - search_switch(ForwardIterator1 begin1, ForwardIterator1 end1, - ForwardIterator2 begin2, ForwardIterator2 end2, - IteratorTag1, IteratorTag2) - { return search(begin1, end1, begin2, end2, - __gnu_parallel::sequential_tag()); } - - // Public interface. - template<typename ForwardIterator1, typename ForwardIterator2> - inline ForwardIterator1 - search(ForwardIterator1 begin1, ForwardIterator1 end1, - ForwardIterator2 begin2, ForwardIterator2 end2) - { - typedef std::iterator_traits<ForwardIterator1> iterator1_traits; - typedef typename iterator1_traits::iterator_category iterator1_category; - typedef std::iterator_traits<ForwardIterator2> iterator2_traits; - typedef typename iterator2_traits::iterator_category iterator2_category; - - return search_switch(begin1, end1, begin2, end2, - iterator1_category(), iterator2_category()); - } - - // Public interface. - template<typename ForwardIterator1, typename ForwardIterator2, - typename BinaryPredicate> - inline ForwardIterator1 - search(ForwardIterator1 begin1, ForwardIterator1 end1, - ForwardIterator2 begin2, ForwardIterator2 end2, - BinaryPredicate pred, __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::search(begin1, end1, begin2, end2, pred); } - - // Parallel algorithm for random access iterator. - template<typename RandomAccessIterator1, typename RandomAccessIterator2, - typename BinaryPredicate> - RandomAccessIterator1 - search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, - RandomAccessIterator2 begin2, RandomAccessIterator2 end2, - BinaryPredicate pred, - random_access_iterator_tag, random_access_iterator_tag) - { - if (_GLIBCXX_PARALLEL_CONDITION(true)) - return __gnu_parallel::search_template(begin1, end1, - begin2, end2, pred); - else - return search(begin1, end1, begin2, end2, pred, - __gnu_parallel::sequential_tag()); - } - - // Sequential fallback for input iterator case - template<typename ForwardIterator1, typename ForwardIterator2, - typename BinaryPredicate, typename IteratorTag1, - typename IteratorTag2> - inline ForwardIterator1 - search_switch(ForwardIterator1 begin1, ForwardIterator1 end1, - ForwardIterator2 begin2, ForwardIterator2 end2, - BinaryPredicate pred, IteratorTag1, IteratorTag2) - { return search(begin1, end1, begin2, end2, pred, - __gnu_parallel::sequential_tag()); } - - // Public interface - template<typename ForwardIterator1, typename ForwardIterator2, - typename BinaryPredicate> - inline ForwardIterator1 - search(ForwardIterator1 begin1, ForwardIterator1 end1, - ForwardIterator2 begin2, ForwardIterator2 end2, - BinaryPredicate pred) - { - typedef std::iterator_traits<ForwardIterator1> iterator1_traits; - typedef typename iterator1_traits::iterator_category iterator1_category; - typedef std::iterator_traits<ForwardIterator2> iterator2_traits; - typedef typename iterator2_traits::iterator_category iterator2_category; - return search_switch(begin1, end1, begin2, end2, pred, - iterator1_category(), iterator2_category()); - } - - // Sequential fallback - template<typename ForwardIterator, typename Integer, typename T> - inline ForwardIterator - search_n(ForwardIterator begin, ForwardIterator end, Integer count, - const T& val, __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::search_n(begin, end, count, val); } - - // Sequential fallback - template<typename ForwardIterator, typename Integer, typename T, - typename BinaryPredicate> - inline ForwardIterator - search_n(ForwardIterator begin, ForwardIterator end, Integer count, - const T& val, BinaryPredicate binary_pred, - __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::search_n(begin, end, count, val, binary_pred); } - - // Public interface. - template<typename ForwardIterator, typename Integer, typename T> - inline ForwardIterator - search_n(ForwardIterator begin, ForwardIterator end, Integer count, - const T& val) - { - typedef typename iterator_traits<ForwardIterator>::value_type value_type; - return search_n(begin, end, count, val, - __gnu_parallel::equal_to<value_type, T>()); - } - - // Parallel algorithm for random access iterators. - template<typename RandomAccessIterator, typename Integer, - typename T, typename BinaryPredicate> - RandomAccessIterator - search_n_switch(RandomAccessIterator begin, RandomAccessIterator end, - Integer count, const T& val, BinaryPredicate binary_pred, - random_access_iterator_tag) - { - if (_GLIBCXX_PARALLEL_CONDITION(true)) - { - __gnu_parallel::pseudo_sequence<T, Integer> ps(val, count); - return __gnu_parallel::search_template(begin, end, ps.begin(), - ps.end(), binary_pred); - } - else - return std::__search_n(begin, end, count, val, - binary_pred, random_access_iterator_tag()); - } - - // Sequential fallback for input iterator case. - template<typename ForwardIterator, typename Integer, typename T, - typename BinaryPredicate, typename IteratorTag> - inline ForwardIterator - search_n_switch(ForwardIterator begin, ForwardIterator end, Integer count, - const T& val, BinaryPredicate binary_pred, IteratorTag) - { return __search_n(begin, end, count, val, binary_pred, IteratorTag()); } - - // Public interface. - template<typename ForwardIterator, typename Integer, typename T, - typename BinaryPredicate> - inline ForwardIterator - search_n(ForwardIterator begin, ForwardIterator end, Integer count, - const T& val, BinaryPredicate binary_pred) - { - return search_n_switch(begin, end, count, val, binary_pred, - typename std::iterator_traits<ForwardIterator>:: - iterator_category()); - } - - - // Sequential fallback. - template<typename InputIterator, typename OutputIterator, - typename UnaryOperation> - inline OutputIterator - transform(InputIterator begin, InputIterator end, OutputIterator result, - UnaryOperation unary_op, __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::transform(begin, end, result, unary_op); } - - // Parallel unary transform for random access iterators. - template<typename RandomAccessIterator1, typename RandomAccessIterator2, - typename UnaryOperation> - RandomAccessIterator2 - transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end, - RandomAccessIterator2 result, UnaryOperation unary_op, - random_access_iterator_tag, random_access_iterator_tag, - __gnu_parallel::_Parallelism parallelism_tag - = __gnu_parallel::parallel_balanced) - { - if (_GLIBCXX_PARALLEL_CONDITION( - static_cast<__gnu_parallel::sequence_index_t>(end - begin) - >= __gnu_parallel::_Settings::get().transform_minimal_n - && __gnu_parallel::is_parallel(parallelism_tag))) - { - bool dummy = true; - typedef __gnu_parallel::iterator_pair<RandomAccessIterator1, - RandomAccessIterator2, random_access_iterator_tag> ip; - ip begin_pair(begin, result), end_pair(end, result + (end - begin)); - __gnu_parallel::transform1_selector<ip> functionality; - __gnu_parallel:: - for_each_template_random_access(begin_pair, end_pair, - unary_op, functionality, - __gnu_parallel::dummy_reduct(), - dummy, dummy, -1, parallelism_tag); - return functionality.finish_iterator; - } - else - return transform(begin, end, result, unary_op, - __gnu_parallel::sequential_tag()); - } - - // Sequential fallback for input iterator case. - template<typename RandomAccessIterator1, typename RandomAccessIterator2, - typename UnaryOperation, typename IteratorTag1, - typename IteratorTag2> - inline RandomAccessIterator2 - transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end, - RandomAccessIterator2 result, UnaryOperation unary_op, - IteratorTag1, IteratorTag2) - { return transform(begin, end, result, unary_op, - __gnu_parallel::sequential_tag()); } - - // Public interface. - template<typename InputIterator, typename OutputIterator, - typename UnaryOperation> - inline OutputIterator - transform(InputIterator begin, InputIterator end, OutputIterator result, - UnaryOperation unary_op, - __gnu_parallel::_Parallelism parallelism_tag) - { - typedef std::iterator_traits<InputIterator> iteratori_traits; - typedef std::iterator_traits<OutputIterator> iteratoro_traits; - typedef typename iteratori_traits::iterator_category iteratori_category; - typedef typename iteratoro_traits::iterator_category iteratoro_category; - - return transform1_switch(begin, end, result, unary_op, - iteratori_category(), iteratoro_category(), - parallelism_tag); - } - - template<typename InputIterator, typename OutputIterator, - typename UnaryOperation> - inline OutputIterator - transform(InputIterator begin, InputIterator end, OutputIterator result, - UnaryOperation unary_op) - { - typedef std::iterator_traits<InputIterator> iteratori_traits; - typedef std::iterator_traits<OutputIterator> iteratoro_traits; - typedef typename iteratori_traits::iterator_category iteratori_category; - typedef typename iteratoro_traits::iterator_category iteratoro_category; - - return transform1_switch(begin, end, result, unary_op, - iteratori_category(), iteratoro_category()); - } - - - // Sequential fallback - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename BinaryOperation> - inline OutputIterator - transform(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, OutputIterator result, - BinaryOperation binary_op, __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::transform(begin1, end1, - begin2, result, binary_op); } - - // Parallel binary transform for random access iterators. - template<typename RandomAccessIterator1, typename RandomAccessIterator2, - typename RandomAccessIterator3, typename BinaryOperation> - RandomAccessIterator3 - transform2_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, - RandomAccessIterator2 begin2, - RandomAccessIterator3 result, BinaryOperation binary_op, - random_access_iterator_tag, random_access_iterator_tag, - random_access_iterator_tag, - __gnu_parallel::_Parallelism parallelism_tag - = __gnu_parallel::parallel_balanced) - { - if (_GLIBCXX_PARALLEL_CONDITION( - (end1 - begin1) >= - __gnu_parallel::_Settings::get().transform_minimal_n - && __gnu_parallel::is_parallel(parallelism_tag))) - { - bool dummy = true; - typedef __gnu_parallel::iterator_triple<RandomAccessIterator1, - RandomAccessIterator2, RandomAccessIterator3, - random_access_iterator_tag> ip; - ip begin_triple(begin1, begin2, result), - end_triple(end1, begin2 + (end1 - begin1), - result + (end1 - begin1)); - __gnu_parallel::transform2_selector<ip> functionality; - __gnu_parallel:: - for_each_template_random_access(begin_triple, end_triple, - binary_op, functionality, - __gnu_parallel::dummy_reduct(), - dummy, dummy, -1, - parallelism_tag); - return functionality.finish_iterator; - } - else - return transform(begin1, end1, begin2, result, binary_op, - __gnu_parallel::sequential_tag()); - } - - // Sequential fallback for input iterator case. - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename BinaryOperation, - typename tag1, typename tag2, typename tag3> - inline OutputIterator - transform2_switch(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, OutputIterator result, - BinaryOperation binary_op, tag1, tag2, tag3) - { return transform(begin1, end1, begin2, result, binary_op, - __gnu_parallel::sequential_tag()); } - - // Public interface. - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename BinaryOperation> - inline OutputIterator - transform(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, OutputIterator result, - BinaryOperation binary_op, - __gnu_parallel::_Parallelism parallelism_tag) - { - typedef std::iterator_traits<InputIterator1> iteratori1_traits; - typedef typename iteratori1_traits::iterator_category - iteratori1_category; - typedef std::iterator_traits<InputIterator2> iteratori2_traits; - typedef typename iteratori2_traits::iterator_category - iteratori2_category; - typedef std::iterator_traits<OutputIterator> iteratoro_traits; - typedef typename iteratoro_traits::iterator_category iteratoro_category; - - return transform2_switch(begin1, end1, begin2, result, binary_op, - iteratori1_category(), iteratori2_category(), - iteratoro_category(), parallelism_tag); - } - - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename BinaryOperation> - inline OutputIterator - transform(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, OutputIterator result, - BinaryOperation binary_op) - { - typedef std::iterator_traits<InputIterator1> iteratori1_traits; - typedef typename iteratori1_traits::iterator_category - iteratori1_category; - typedef std::iterator_traits<InputIterator2> iteratori2_traits; - typedef typename iteratori2_traits::iterator_category - iteratori2_category; - typedef std::iterator_traits<OutputIterator> iteratoro_traits; - typedef typename iteratoro_traits::iterator_category iteratoro_category; - - return transform2_switch(begin1, end1, begin2, result, binary_op, - iteratori1_category(), iteratori2_category(), - iteratoro_category()); - } - - // Sequential fallback - template<typename ForwardIterator, typename T> - inline void - replace(ForwardIterator begin, ForwardIterator end, const T& old_value, - const T& new_value, __gnu_parallel::sequential_tag) - { _GLIBCXX_STD_P::replace(begin, end, old_value, new_value); } - - // Sequential fallback for input iterator case - template<typename ForwardIterator, typename T, typename IteratorTag> - inline void - replace_switch(ForwardIterator begin, ForwardIterator end, - const T& old_value, const T& new_value, IteratorTag) - { replace(begin, end, old_value, new_value, - __gnu_parallel::sequential_tag()); } - - // Parallel replace for random access iterators - template<typename RandomAccessIterator, typename T> - inline void - replace_switch(RandomAccessIterator begin, RandomAccessIterator end, - const T& old_value, const T& new_value, - random_access_iterator_tag, - __gnu_parallel::_Parallelism parallelism_tag - = __gnu_parallel::parallel_balanced) - { - // XXX parallel version is where? - replace(begin, end, old_value, new_value, - __gnu_parallel::sequential_tag()); - } - - // Public interface - template<typename ForwardIterator, typename T> - inline void - replace(ForwardIterator begin, ForwardIterator end, const T& old_value, - const T& new_value, __gnu_parallel::_Parallelism parallelism_tag) - { - typedef iterator_traits<ForwardIterator> traits_type; - typedef typename traits_type::iterator_category iterator_category; - replace_switch(begin, end, old_value, new_value, iterator_category(), - parallelism_tag); - } - - template<typename ForwardIterator, typename T> - inline void - replace(ForwardIterator begin, ForwardIterator end, const T& old_value, - const T& new_value) - { - typedef iterator_traits<ForwardIterator> traits_type; - typedef typename traits_type::iterator_category iterator_category; - replace_switch(begin, end, old_value, new_value, iterator_category()); - } - - - // Sequential fallback - template<typename ForwardIterator, typename Predicate, typename T> - inline void - replace_if(ForwardIterator begin, ForwardIterator end, Predicate pred, - const T& new_value, __gnu_parallel::sequential_tag) - { _GLIBCXX_STD_P::replace_if(begin, end, pred, new_value); } - - // Sequential fallback for input iterator case - template<typename ForwardIterator, typename Predicate, typename T, - typename IteratorTag> - inline void - replace_if_switch(ForwardIterator begin, ForwardIterator end, - Predicate pred, const T& new_value, IteratorTag) - { replace_if(begin, end, pred, new_value, - __gnu_parallel::sequential_tag()); } - - // Parallel algorithm for random access iterators. - template<typename RandomAccessIterator, typename Predicate, typename T> - void - replace_if_switch(RandomAccessIterator begin, RandomAccessIterator end, - Predicate pred, const T& new_value, - random_access_iterator_tag, - __gnu_parallel::_Parallelism parallelism_tag - = __gnu_parallel::parallel_balanced) - { - if (_GLIBCXX_PARALLEL_CONDITION( - static_cast<__gnu_parallel::sequence_index_t>(end - begin) - >= __gnu_parallel::_Settings::get().replace_minimal_n - && __gnu_parallel::is_parallel(parallelism_tag))) - { - bool dummy; - __gnu_parallel:: - replace_if_selector<RandomAccessIterator, Predicate, T> - functionality(new_value); - __gnu_parallel:: - for_each_template_random_access(begin, end, pred, - functionality, - __gnu_parallel::dummy_reduct(), - true, dummy, -1, parallelism_tag); - } - else - replace_if(begin, end, pred, new_value, - __gnu_parallel::sequential_tag()); - } - - // Public interface. - template<typename ForwardIterator, typename Predicate, typename T> - inline void - replace_if(ForwardIterator begin, ForwardIterator end, - Predicate pred, const T& new_value, - __gnu_parallel::_Parallelism parallelism_tag) - { - typedef std::iterator_traits<ForwardIterator> iterator_traits; - typedef typename iterator_traits::iterator_category iterator_category; - replace_if_switch(begin, end, pred, new_value, iterator_category(), - parallelism_tag); - } - - template<typename ForwardIterator, typename Predicate, typename T> - inline void - replace_if(ForwardIterator begin, ForwardIterator end, - Predicate pred, const T& new_value) - { - typedef std::iterator_traits<ForwardIterator> iterator_traits; - typedef typename iterator_traits::iterator_category iterator_category; - replace_if_switch(begin, end, pred, new_value, iterator_category()); - } - - // Sequential fallback - template<typename ForwardIterator, typename Generator> - inline void - generate(ForwardIterator begin, ForwardIterator end, Generator gen, - __gnu_parallel::sequential_tag) - { _GLIBCXX_STD_P::generate(begin, end, gen); } - - // Sequential fallback for input iterator case. - template<typename ForwardIterator, typename Generator, typename IteratorTag> - inline void - generate_switch(ForwardIterator begin, ForwardIterator end, Generator gen, - IteratorTag) - { generate(begin, end, gen, __gnu_parallel::sequential_tag()); } - - // Parallel algorithm for random access iterators. - template<typename RandomAccessIterator, typename Generator> - void - generate_switch(RandomAccessIterator begin, RandomAccessIterator end, - Generator gen, random_access_iterator_tag, - __gnu_parallel::_Parallelism parallelism_tag - = __gnu_parallel::parallel_balanced) - { - if (_GLIBCXX_PARALLEL_CONDITION( - static_cast<__gnu_parallel::sequence_index_t>(end - begin) - >= __gnu_parallel::_Settings::get().generate_minimal_n - && __gnu_parallel::is_parallel(parallelism_tag))) - { - bool dummy; - __gnu_parallel::generate_selector<RandomAccessIterator> - functionality; - __gnu_parallel:: - for_each_template_random_access(begin, end, gen, functionality, - __gnu_parallel::dummy_reduct(), - true, dummy, -1, parallelism_tag); - } - else - generate(begin, end, gen, __gnu_parallel::sequential_tag()); - } - - // Public interface. - template<typename ForwardIterator, typename Generator> - inline void - generate(ForwardIterator begin, ForwardIterator end, - Generator gen, __gnu_parallel::_Parallelism parallelism_tag) - { - typedef std::iterator_traits<ForwardIterator> iterator_traits; - typedef typename iterator_traits::iterator_category iterator_category; - generate_switch(begin, end, gen, iterator_category(), parallelism_tag); - } - - template<typename ForwardIterator, typename Generator> - inline void - generate(ForwardIterator begin, ForwardIterator end, Generator gen) - { - typedef std::iterator_traits<ForwardIterator> iterator_traits; - typedef typename iterator_traits::iterator_category iterator_category; - generate_switch(begin, end, gen, iterator_category()); - } - - - // Sequential fallback. - template<typename OutputIterator, typename Size, typename Generator> - inline OutputIterator - generate_n(OutputIterator begin, Size n, Generator gen, - __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::generate_n(begin, n, gen); } - - // Sequential fallback for input iterator case. - template<typename OutputIterator, typename Size, typename Generator, - typename IteratorTag> - inline OutputIterator - generate_n_switch(OutputIterator begin, Size n, Generator gen, IteratorTag) - { return generate_n(begin, n, gen, __gnu_parallel::sequential_tag()); } - - // Parallel algorithm for random access iterators. - template<typename RandomAccessIterator, typename Size, typename Generator> - inline RandomAccessIterator - generate_n_switch(RandomAccessIterator begin, Size n, Generator gen, - random_access_iterator_tag, - __gnu_parallel::_Parallelism parallelism_tag - = __gnu_parallel::parallel_balanced) - { - // XXX parallel version is where? - return generate_n(begin, n, gen, __gnu_parallel::sequential_tag()); - } - - // Public interface. - template<typename OutputIterator, typename Size, typename Generator> - inline OutputIterator - generate_n(OutputIterator begin, Size n, Generator gen, - __gnu_parallel::_Parallelism parallelism_tag) - { - typedef std::iterator_traits<OutputIterator> iterator_traits; - typedef typename iterator_traits::iterator_category iterator_category; - return generate_n_switch(begin, n, gen, iterator_category(), - parallelism_tag); - } - - template<typename OutputIterator, typename Size, typename Generator> - inline OutputIterator - generate_n(OutputIterator begin, Size n, Generator gen) - { - typedef std::iterator_traits<OutputIterator> iterator_traits; - typedef typename iterator_traits::iterator_category iterator_category; - return generate_n_switch(begin, n, gen, iterator_category()); - } - - - // Sequential fallback. - template<typename RandomAccessIterator> - inline void - random_shuffle(RandomAccessIterator begin, RandomAccessIterator end, - __gnu_parallel::sequential_tag) - { _GLIBCXX_STD_P::random_shuffle(begin, end); } - - // Sequential fallback. - template<typename RandomAccessIterator, typename RandomNumberGenerator> - inline void - random_shuffle(RandomAccessIterator begin, RandomAccessIterator end, - RandomNumberGenerator& rand, __gnu_parallel::sequential_tag) - { _GLIBCXX_STD_P::random_shuffle(begin, end, rand); } - - - /** @brief Functor wrapper for std::rand(). */ - template<typename must_be_int = int> - struct c_rand_number - { - int - operator()(int limit) - { return rand() % limit; } - }; - - // Fill in random number generator. - template<typename RandomAccessIterator> - inline void - random_shuffle(RandomAccessIterator begin, RandomAccessIterator end) - { - c_rand_number<> r; - // Parallelization still possible. - __gnu_parallel::random_shuffle(begin, end, r); - } - - // Parallel algorithm for random access iterators. - template<typename RandomAccessIterator, typename RandomNumberGenerator> - void - random_shuffle(RandomAccessIterator begin, RandomAccessIterator end, - RandomNumberGenerator& rand) - { - if (begin == end) - return; - if (_GLIBCXX_PARALLEL_CONDITION( - static_cast<__gnu_parallel::sequence_index_t>(end - begin) - >= __gnu_parallel::_Settings::get().random_shuffle_minimal_n)) - __gnu_parallel::parallel_random_shuffle(begin, end, rand); - else - __gnu_parallel::sequential_random_shuffle(begin, end, rand); - } - - // Sequential fallback. - template<typename ForwardIterator, typename Predicate> - inline ForwardIterator - partition(ForwardIterator begin, ForwardIterator end, - Predicate pred, __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::partition(begin, end, pred); } - - // Sequential fallback for input iterator case. - template<typename ForwardIterator, typename Predicate, typename IteratorTag> - inline ForwardIterator - partition_switch(ForwardIterator begin, ForwardIterator end, - Predicate pred, IteratorTag) - { return partition(begin, end, pred, __gnu_parallel::sequential_tag()); } - - // Parallel algorithm for random access iterators. - template<typename RandomAccessIterator, typename Predicate> - RandomAccessIterator - partition_switch(RandomAccessIterator begin, RandomAccessIterator end, - Predicate pred, random_access_iterator_tag) - { - if (_GLIBCXX_PARALLEL_CONDITION( - static_cast<__gnu_parallel::sequence_index_t>(end - begin) - >= __gnu_parallel::_Settings::get().partition_minimal_n)) - { - typedef typename std::iterator_traits<RandomAccessIterator>:: - difference_type difference_type; - difference_type middle = __gnu_parallel:: - parallel_partition(begin, end, pred, - __gnu_parallel::get_max_threads()); - return begin + middle; - } - else - return partition(begin, end, pred, __gnu_parallel::sequential_tag()); - } - - // Public interface. - template<typename ForwardIterator, typename Predicate> - inline ForwardIterator - partition(ForwardIterator begin, ForwardIterator end, Predicate pred) - { - typedef iterator_traits<ForwardIterator> traits_type; - typedef typename traits_type::iterator_category iterator_category; - return partition_switch(begin, end, pred, iterator_category()); - } - - // sort interface - - // Sequential fallback - template<typename RandomAccessIterator> - inline void - sort(RandomAccessIterator begin, RandomAccessIterator end, - __gnu_parallel::sequential_tag) - { _GLIBCXX_STD_P::sort(begin, end); } - - // Sequential fallback - template<typename RandomAccessIterator, typename Comparator> - inline void - sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, - __gnu_parallel::sequential_tag) - { _GLIBCXX_STD_P::sort<RandomAccessIterator, Comparator>(begin, end, - comp); } - - // Public interface - template<typename RandomAccessIterator, typename Comparator, - typename Parallelism> - void - sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, - Parallelism parallelism) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - - if (begin != end) - { - if (_GLIBCXX_PARALLEL_CONDITION( - static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= - __gnu_parallel::_Settings::get().sort_minimal_n)) - __gnu_parallel::parallel_sort<false>(begin, end, comp, parallelism); - else - sort(begin, end, comp, __gnu_parallel::sequential_tag()); - } - } - - // Public interface, insert default comparator - template<typename RandomAccessIterator> - inline void - sort(RandomAccessIterator begin, RandomAccessIterator end) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - sort(begin, end, std::less<value_type>(), - __gnu_parallel::default_parallel_tag()); - } - - // Public interface, insert default comparator - template<typename RandomAccessIterator> - inline void - sort(RandomAccessIterator begin, RandomAccessIterator end, - __gnu_parallel::default_parallel_tag parallelism) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - sort(begin, end, std::less<value_type>(), parallelism); - } - - // Public interface, insert default comparator - template<typename RandomAccessIterator> - inline void - sort(RandomAccessIterator begin, RandomAccessIterator end, - __gnu_parallel::parallel_tag parallelism) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - sort(begin, end, std::less<value_type>(), parallelism); - } - - // Public interface, insert default comparator - template<typename RandomAccessIterator> - inline void - sort(RandomAccessIterator begin, RandomAccessIterator end, - __gnu_parallel::multiway_mergesort_tag parallelism) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - sort(begin, end, std::less<value_type>(), parallelism); - } - - // Public interface, insert default comparator - template<typename RandomAccessIterator> - inline void - sort(RandomAccessIterator begin, RandomAccessIterator end, - __gnu_parallel::multiway_mergesort_sampling_tag parallelism) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - sort(begin, end, std::less<value_type>(), parallelism); - } - - // Public interface, insert default comparator - template<typename RandomAccessIterator> - inline void - sort(RandomAccessIterator begin, RandomAccessIterator end, - __gnu_parallel::multiway_mergesort_exact_tag parallelism) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - sort(begin, end, std::less<value_type>(), parallelism); - } - - // Public interface, insert default comparator - template<typename RandomAccessIterator> - inline void - sort(RandomAccessIterator begin, RandomAccessIterator end, - __gnu_parallel::quicksort_tag parallelism) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - sort(begin, end, std::less<value_type>(), parallelism); - } - - // Public interface, insert default comparator - template<typename RandomAccessIterator> - inline void - sort(RandomAccessIterator begin, RandomAccessIterator end, - __gnu_parallel::balanced_quicksort_tag parallelism) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - sort(begin, end, std::less<value_type>(), parallelism); - } - - // Public interface - template<typename RandomAccessIterator, typename Comparator> - void - sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - sort(begin, end, comp, __gnu_parallel::default_parallel_tag()); - } - - - // stable_sort interface - - - // Sequential fallback - template<typename RandomAccessIterator> - inline void - stable_sort(RandomAccessIterator begin, RandomAccessIterator end, - __gnu_parallel::sequential_tag) - { _GLIBCXX_STD_P::stable_sort(begin, end); } - - // Sequential fallback - template<typename RandomAccessIterator, typename Comparator> - inline void - stable_sort(RandomAccessIterator begin, RandomAccessIterator end, - Comparator comp, __gnu_parallel::sequential_tag) - { _GLIBCXX_STD_P::stable_sort<RandomAccessIterator, Comparator>( - begin, end, comp); } - - // Public interface - template<typename RandomAccessIterator, typename Comparator, - typename Parallelism> - void - stable_sort(RandomAccessIterator begin, RandomAccessIterator end, - Comparator comp, Parallelism parallelism) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - - if (begin != end) - { - if (_GLIBCXX_PARALLEL_CONDITION( - static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= - __gnu_parallel::_Settings::get().sort_minimal_n)) - __gnu_parallel::parallel_sort<true>(begin, end, comp, parallelism); - else - stable_sort(begin, end, comp, __gnu_parallel::sequential_tag()); - } - } - - // Public interface, insert default comparator - template<typename RandomAccessIterator> - inline void - stable_sort(RandomAccessIterator begin, RandomAccessIterator end) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - stable_sort(begin, end, std::less<value_type>(), - __gnu_parallel::default_parallel_tag()); - } - - // Public interface, insert default comparator - template<typename RandomAccessIterator> - inline void - stable_sort(RandomAccessIterator begin, RandomAccessIterator end, - __gnu_parallel::default_parallel_tag parallelism) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - stable_sort(begin, end, std::less<value_type>(), parallelism); - } - - // Public interface, insert default comparator - template<typename RandomAccessIterator> - inline void - stable_sort(RandomAccessIterator begin, RandomAccessIterator end, - __gnu_parallel::parallel_tag parallelism) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - stable_sort(begin, end, std::less<value_type>(), parallelism); - } - - // Public interface, insert default comparator - template<typename RandomAccessIterator> - inline void - stable_sort(RandomAccessIterator begin, RandomAccessIterator end, - __gnu_parallel::multiway_mergesort_tag parallelism) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - stable_sort(begin, end, std::less<value_type>(), parallelism); - } - - // Public interface, insert default comparator - template<typename RandomAccessIterator> - inline void - stable_sort(RandomAccessIterator begin, RandomAccessIterator end, - __gnu_parallel::quicksort_tag parallelism) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - stable_sort(begin, end, std::less<value_type>(), parallelism); - } - - // Public interface, insert default comparator - template<typename RandomAccessIterator> - inline void - stable_sort(RandomAccessIterator begin, RandomAccessIterator end, - __gnu_parallel::balanced_quicksort_tag parallelism) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - stable_sort(begin, end, std::less<value_type>(), parallelism); - } - - // Public interface - template<typename RandomAccessIterator, typename Comparator> - void - stable_sort(RandomAccessIterator begin, RandomAccessIterator end, - Comparator comp) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - stable_sort(begin, end, comp, __gnu_parallel::default_parallel_tag()); - } - - -// // Sequential fallback -// template<typename RandomAccessIterator> -// inline void -// stable_sort(RandomAccessIterator begin, RandomAccessIterator end, -// __gnu_parallel::sequential_tag) -// { return _GLIBCXX_STD_P::stable_sort(begin, end); } -// -// // Sequential fallback -// template<typename RandomAccessIterator, typename Comparator> -// inline void -// stable_sort(RandomAccessIterator begin, RandomAccessIterator end, -// Comparator comp, __gnu_parallel::sequential_tag) -// { return _GLIBCXX_STD_P::stable_sort(begin, end, comp); } -// -// template<typename RandomAccessIterator> -// void -// stable_sort(RandomAccessIterator begin, RandomAccessIterator end) -// { -// typedef iterator_traits<RandomAccessIterator> traits_type; -// typedef typename traits_type::value_type value_type; -// stable_sort(begin, end, std::less<value_type>()); -// } -// -// // Parallel algorithm for random access iterators -// template<typename RandomAccessIterator, typename Comparator> -// void -// stable_sort(RandomAccessIterator begin, RandomAccessIterator end, -// Comparator comp) -// { -// if (begin != end) -// { -// if (_GLIBCXX_PARALLEL_CONDITION( -// static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= -// __gnu_parallel::_Settings::get().sort_minimal_n)) -// __gnu_parallel::parallel_sort(begin, end, comp, -// __gnu_parallel::parallel_tag()); -// else -// stable_sort(begin, end, comp, __gnu_parallel::sequential_tag()); -// } -// } - - // Sequential fallback - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator> - inline OutputIterator - merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, - InputIterator2 end2, OutputIterator result, - __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result); } - - // Sequential fallback - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename Comparator> - inline OutputIterator - merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, - InputIterator2 end2, OutputIterator result, Comparator comp, - __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result, comp); } - - // Sequential fallback for input iterator case - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename Comparator, - typename IteratorTag1, typename IteratorTag2, typename IteratorTag3> - inline OutputIterator - merge_switch(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator result, Comparator comp, - IteratorTag1, IteratorTag2, IteratorTag3) - { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, - result, comp); } - - // Parallel algorithm for random access iterators - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename Comparator> - OutputIterator - merge_switch(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator result, Comparator comp, - random_access_iterator_tag, random_access_iterator_tag, - random_access_iterator_tag) - { - if (_GLIBCXX_PARALLEL_CONDITION( - (static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1) - >= __gnu_parallel::_Settings::get().merge_minimal_n - || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2) - >= __gnu_parallel::_Settings::get().merge_minimal_n))) - return __gnu_parallel::parallel_merge_advance(begin1, end1, - begin2, end2, - result, (end1 - begin1) - + (end2 - begin2), comp); - else - return __gnu_parallel::merge_advance(begin1, end1, begin2, end2, - result, (end1 - begin1) - + (end2 - begin2), comp); - } - - // Public interface - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename Comparator> - inline OutputIterator - merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, - InputIterator2 end2, OutputIterator result, Comparator comp) - { - typedef typename iterator_traits<InputIterator1>::value_type value_type; - - typedef std::iterator_traits<InputIterator1> iteratori1_traits; - typedef std::iterator_traits<InputIterator2> iteratori2_traits; - typedef std::iterator_traits<OutputIterator> iteratoro_traits; - typedef typename iteratori1_traits::iterator_category - iteratori1_category; - typedef typename iteratori2_traits::iterator_category - iteratori2_category; - typedef typename iteratoro_traits::iterator_category iteratoro_category; - - return merge_switch(begin1, end1, begin2, end2, result, comp, - iteratori1_category(), iteratori2_category(), - iteratoro_category()); - } - - - // Public interface, insert default comparator - template<typename InputIterator1, typename InputIterator2, - typename OutputIterator> - inline OutputIterator - merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, - InputIterator2 end2, OutputIterator result) - { - 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; - - return merge(begin1, end1, begin2, end2, result, - __gnu_parallel::less<value1_type, value2_type>()); - } - - // Sequential fallback - template<typename RandomAccessIterator> - inline void - nth_element(RandomAccessIterator begin, RandomAccessIterator nth, - RandomAccessIterator end, __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::nth_element(begin, nth, end); } - - // Sequential fallback - template<typename RandomAccessIterator, typename Comparator> - inline void - nth_element(RandomAccessIterator begin, RandomAccessIterator nth, - RandomAccessIterator end, Comparator comp, - __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::nth_element(begin, nth, end, comp); } - - // Public interface - template<typename RandomAccessIterator, typename Comparator> - inline void - nth_element(RandomAccessIterator begin, RandomAccessIterator nth, - RandomAccessIterator end, Comparator comp) - { - if (_GLIBCXX_PARALLEL_CONDITION( - static_cast<__gnu_parallel::sequence_index_t>(end - begin) - >= __gnu_parallel::_Settings::get().nth_element_minimal_n)) - __gnu_parallel::parallel_nth_element(begin, nth, end, comp); - else - nth_element(begin, nth, end, comp, __gnu_parallel::sequential_tag()); - } - - // Public interface, insert default comparator - template<typename RandomAccessIterator> - inline void - nth_element(RandomAccessIterator begin, RandomAccessIterator nth, - RandomAccessIterator end) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - nth_element(begin, nth, end, std::less<value_type>()); - } - - // Sequential fallback - template<typename RandomAccessIterator, typename _Compare> - inline void - partial_sort(RandomAccessIterator begin, RandomAccessIterator middle, - RandomAccessIterator end, _Compare comp, - __gnu_parallel::sequential_tag) - { _GLIBCXX_STD_P::partial_sort(begin, middle, end, comp); } - - // Sequential fallback - template<typename RandomAccessIterator> - inline void - partial_sort(RandomAccessIterator begin, RandomAccessIterator middle, - RandomAccessIterator end, __gnu_parallel::sequential_tag) - { _GLIBCXX_STD_P::partial_sort(begin, middle, end); } - - // Public interface, parallel algorithm for random access iterators - template<typename RandomAccessIterator, typename _Compare> - void - partial_sort(RandomAccessIterator begin, RandomAccessIterator middle, - RandomAccessIterator end, _Compare comp) - { - if (_GLIBCXX_PARALLEL_CONDITION( - static_cast<__gnu_parallel::sequence_index_t>(end - begin) - >= __gnu_parallel::_Settings::get().partial_sort_minimal_n)) - __gnu_parallel::parallel_partial_sort(begin, middle, end, comp); - else - partial_sort(begin, middle, end, comp, - __gnu_parallel::sequential_tag()); - } - - // Public interface, insert default comparator - template<typename RandomAccessIterator> - inline void - partial_sort(RandomAccessIterator begin, RandomAccessIterator middle, - RandomAccessIterator end) - { - typedef iterator_traits<RandomAccessIterator> traits_type; - typedef typename traits_type::value_type value_type; - partial_sort(begin, middle, end, std::less<value_type>()); - } - - // Sequential fallback - template<typename ForwardIterator> - inline ForwardIterator - max_element(ForwardIterator begin, ForwardIterator end, - __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::max_element(begin, end); } - - // Sequential fallback - template<typename ForwardIterator, typename Comparator> - inline ForwardIterator - max_element(ForwardIterator begin, ForwardIterator end, Comparator comp, - __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::max_element(begin, end, comp); } - - // Sequential fallback for input iterator case - template<typename ForwardIterator, typename Comparator, typename IteratorTag> - inline ForwardIterator - max_element_switch(ForwardIterator begin, ForwardIterator end, - Comparator comp, IteratorTag) - { return max_element(begin, end, comp, __gnu_parallel::sequential_tag()); } - - // Parallel algorithm for random access iterators - template<typename RandomAccessIterator, typename Comparator> - RandomAccessIterator - max_element_switch(RandomAccessIterator begin, RandomAccessIterator end, - Comparator comp, random_access_iterator_tag, - __gnu_parallel::_Parallelism parallelism_tag - = __gnu_parallel::parallel_balanced) - { - if (_GLIBCXX_PARALLEL_CONDITION( - static_cast<__gnu_parallel::sequence_index_t>(end - begin) - >= __gnu_parallel::_Settings::get().max_element_minimal_n - && __gnu_parallel::is_parallel(parallelism_tag))) - { - RandomAccessIterator res(begin); - __gnu_parallel::identity_selector<RandomAccessIterator> - functionality; - __gnu_parallel:: - for_each_template_random_access(begin, end, - __gnu_parallel::nothing(), - functionality, - __gnu_parallel:: - max_element_reduct<Comparator, - RandomAccessIterator>(comp), - res, res, -1, parallelism_tag); - return res; - } - else - return max_element(begin, end, comp, __gnu_parallel::sequential_tag()); - } - - // Public interface, insert default comparator - template<typename ForwardIterator> - inline ForwardIterator - max_element(ForwardIterator begin, ForwardIterator end, - __gnu_parallel::_Parallelism parallelism_tag) - { - typedef typename iterator_traits<ForwardIterator>::value_type value_type; - return max_element(begin, end, std::less<value_type>(), parallelism_tag); - } - - template<typename ForwardIterator> - inline ForwardIterator - max_element(ForwardIterator begin, ForwardIterator end) - { - typedef typename iterator_traits<ForwardIterator>::value_type value_type; - return max_element(begin, end, std::less<value_type>()); - } - - // Public interface - template<typename ForwardIterator, typename Comparator> - inline ForwardIterator - max_element(ForwardIterator begin, ForwardIterator end, Comparator comp, - __gnu_parallel::_Parallelism parallelism_tag) - { - typedef iterator_traits<ForwardIterator> traits_type; - typedef typename traits_type::iterator_category iterator_category; - return max_element_switch(begin, end, comp, iterator_category(), - parallelism_tag); - } - - template<typename ForwardIterator, typename Comparator> - inline ForwardIterator - max_element(ForwardIterator begin, ForwardIterator end, Comparator comp) - { - typedef iterator_traits<ForwardIterator> traits_type; - typedef typename traits_type::iterator_category iterator_category; - return max_element_switch(begin, end, comp, iterator_category()); - } - - - // Sequential fallback - template<typename ForwardIterator> - inline ForwardIterator - min_element(ForwardIterator begin, ForwardIterator end, - __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::min_element(begin, end); } - - // Sequential fallback - template<typename ForwardIterator, typename Comparator> - inline ForwardIterator - min_element(ForwardIterator begin, ForwardIterator end, Comparator comp, - __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_P::min_element(begin, end, comp); } - - // Sequential fallback for input iterator case - template<typename ForwardIterator, typename Comparator, typename IteratorTag> - inline ForwardIterator - min_element_switch(ForwardIterator begin, ForwardIterator end, - Comparator comp, IteratorTag) - { return min_element(begin, end, comp, __gnu_parallel::sequential_tag()); } - - // Parallel algorithm for random access iterators - template<typename RandomAccessIterator, typename Comparator> - RandomAccessIterator - min_element_switch(RandomAccessIterator begin, RandomAccessIterator end, - Comparator comp, random_access_iterator_tag, - __gnu_parallel::_Parallelism parallelism_tag - = __gnu_parallel::parallel_balanced) - { - if (_GLIBCXX_PARALLEL_CONDITION( - static_cast<__gnu_parallel::sequence_index_t>(end - begin) - >= __gnu_parallel::_Settings::get().min_element_minimal_n - && __gnu_parallel::is_parallel(parallelism_tag))) - { - RandomAccessIterator res(begin); - __gnu_parallel::identity_selector<RandomAccessIterator> - functionality; - __gnu_parallel:: - for_each_template_random_access(begin, end, - __gnu_parallel::nothing(), - functionality, - __gnu_parallel:: - min_element_reduct<Comparator, - RandomAccessIterator>(comp), - res, res, -1, parallelism_tag); - return res; - } - else - return min_element(begin, end, comp, __gnu_parallel::sequential_tag()); - } - - // Public interface, insert default comparator - template<typename ForwardIterator> - inline ForwardIterator - min_element(ForwardIterator begin, ForwardIterator end, - __gnu_parallel::_Parallelism parallelism_tag) - { - typedef typename iterator_traits<ForwardIterator>::value_type value_type; - return min_element(begin, end, std::less<value_type>(), parallelism_tag); - } - - template<typename ForwardIterator> - inline ForwardIterator - min_element(ForwardIterator begin, ForwardIterator end) - { - typedef typename iterator_traits<ForwardIterator>::value_type value_type; - return min_element(begin, end, std::less<value_type>()); - } - - // Public interface - template<typename ForwardIterator, typename Comparator> - inline ForwardIterator - min_element(ForwardIterator begin, ForwardIterator end, Comparator comp, - __gnu_parallel::_Parallelism parallelism_tag) - { - typedef iterator_traits<ForwardIterator> traits_type; - typedef typename traits_type::iterator_category iterator_category; - return min_element_switch(begin, end, comp, iterator_category(), - parallelism_tag); - } - - template<typename ForwardIterator, typename Comparator> - inline ForwardIterator - min_element(ForwardIterator begin, ForwardIterator end, Comparator comp) - { - typedef iterator_traits<ForwardIterator> traits_type; - typedef typename traits_type::iterator_category iterator_category; - return min_element_switch(begin, end, comp, iterator_category()); - } -} // end namespace -} // end namespace - -#endif /* _GLIBCXX_PARALLEL_ALGO_H */ |