// -*- 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 // . /** @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 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include namespace std { namespace __parallel { // Sequential fallback template 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 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 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 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 inline Function for_each(Iterator begin, Iterator end, Function f, __gnu_parallel::_Parallelism parallelism_tag) { typedef std::iterator_traits iterator_traits; typedef typename iterator_traits::iterator_category iterator_category; return for_each_switch(begin, end, f, iterator_category(), parallelism_tag); } template inline Function for_each(Iterator begin, Iterator end, Function f) { typedef std::iterator_traits iterator_traits; typedef typename iterator_traits::iterator_category iterator_category; return for_each_switch(begin, end, f, iterator_category()); } // Sequential fallback template 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 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 RandomAccessIterator find_switch(RandomAccessIterator begin, RandomAccessIterator end, const T& val, random_access_iterator_tag) { typedef iterator_traits traits_type; typedef typename traits_type::value_type value_type; if (_GLIBCXX_PARALLEL_CONDITION(true)) { binder2nd<__gnu_parallel::equal_to > comp(__gnu_parallel::equal_to(), 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 inline InputIterator find(InputIterator begin, InputIterator end, const T& val) { typedef std::iterator_traits iterator_traits; typedef typename iterator_traits::iterator_category iterator_category; return find_switch(begin, end, val, iterator_category()); } // Sequential fallback template 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 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 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 inline InputIterator find_if(InputIterator begin, InputIterator end, Predicate pred) { typedef std::iterator_traits iterator_traits; typedef typename iterator_traits::iterator_category iterator_category; return find_if_switch(begin, end, pred, iterator_category()); } // Sequential fallback template 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 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 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 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 (begin2, end2)).first; } // Sequential fallback for input iterator type template 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 inline InputIterator find_first_of(InputIterator begin1, InputIterator end1, ForwardIterator begin2, ForwardIterator end2, BinaryPredicate comp) { typedef std::iterator_traits iteratori_traits; typedef std::iterator_traits 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 inline InputIterator find_first_of(InputIterator begin1, InputIterator end1, ForwardIterator begin2, ForwardIterator end2) { typedef std::iterator_traits iteratori_traits; typedef std::iterator_traits 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()); } // Sequential fallback template 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 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 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 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 inline OutputIterator unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out) { typedef std::iterator_traits iteratori_traits; typedef std::iterator_traits 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(), iteratori_category(), iteratoro_category()); } // Public interface template inline OutputIterator unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out, Predicate pred) { typedef std::iterator_traits iteratori_traits; typedef std::iterator_traits 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 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 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 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 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 inline OutputIterator set_union(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator out) { typedef std::iterator_traits iteratori1_traits; typedef std::iterator_traits iteratori2_traits; typedef std::iterator_traits 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(), iteratori1_category(), iteratori2_category(), iteratoro_category()); } // Public interface template inline OutputIterator set_union(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator out, Predicate pred) { typedef std::iterator_traits iteratori1_traits; typedef std::iterator_traits iteratori2_traits; typedef std::iterator_traits 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 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 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 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 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 inline OutputIterator set_intersection(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator out) { typedef std::iterator_traits iteratori1_traits; typedef std::iterator_traits iteratori2_traits; typedef std::iterator_traits 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(), iteratori1_category(), iteratori2_category(), iteratoro_category()); } template inline OutputIterator set_intersection(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator out, Predicate pred) { typedef std::iterator_traits iteratori1_traits; typedef std::iterator_traits iteratori2_traits; typedef std::iterator_traits 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 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 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 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 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 inline OutputIterator set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator out) { typedef std::iterator_traits iteratori1_traits; typedef std::iterator_traits iteratori2_traits; typedef std::iterator_traits 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(), iteratori1_category(), iteratori2_category(), iteratoro_category()); } // Public interface. template inline OutputIterator set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator out, Predicate pred) { typedef std::iterator_traits iteratori1_traits; typedef std::iterator_traits iteratori2_traits; typedef std::iterator_traits 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 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 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 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 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 inline OutputIterator set_difference(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator out) { typedef std::iterator_traits iteratori1_traits; typedef std::iterator_traits iteratori2_traits; typedef std::iterator_traits 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(), iteratori1_category(), iteratori2_category(), iteratoro_category()); } // Public interface template inline OutputIterator set_difference(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator out, Predicate pred) { typedef std::iterator_traits iteratori1_traits; typedef std::iterator_traits iteratori2_traits; typedef std::iterator_traits 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 inline ForwardIterator adjacent_find(ForwardIterator begin, ForwardIterator end, __gnu_parallel::sequential_tag) { return _GLIBCXX_STD_P::adjacent_find(begin, end); } // Sequential fallback template 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 RandomAccessIterator adjacent_find_switch(RandomAccessIterator begin, RandomAccessIterator end, random_access_iterator_tag) { typedef iterator_traits 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(), __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 inline ForwardIterator adjacent_find_switch(ForwardIterator begin, ForwardIterator end, IteratorTag) { return adjacent_find(begin, end, __gnu_parallel::sequential_tag()); } // Public interface template inline ForwardIterator adjacent_find(ForwardIterator begin, ForwardIterator end) { typedef iterator_traits 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 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 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 inline ForwardIterator adjacent_find(ForwardIterator begin, ForwardIterator end, BinaryPredicate pred) { typedef iterator_traits traits_type; typedef typename traits_type::iterator_category iterator_category; return adjacent_find_switch(begin, end, pred, iterator_category()); } // Sequential fallback template inline typename iterator_traits::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 iterator_traits::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 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(end - begin) >= __gnu_parallel::_Settings::get().count_minimal_n && __gnu_parallel::is_parallel(parallelism_tag))) { __gnu_parallel::count_selector functionality; difference_type res = 0; __gnu_parallel:: for_each_template_random_access(begin, end, value, functionality, std::plus(), res, res, -1, parallelism_tag); return res; } else return count(begin, end, value, __gnu_parallel::sequential_tag()); } // Sequential fallback for input iterator case. template inline typename iterator_traits::difference_type count_switch(InputIterator begin, InputIterator end, const T& value, IteratorTag) { return count(begin, end, value, __gnu_parallel::sequential_tag()); } // Public interface. template inline typename iterator_traits::difference_type count(InputIterator begin, InputIterator end, const T& value, __gnu_parallel::_Parallelism parallelism_tag) { typedef iterator_traits traits_type; typedef typename traits_type::iterator_category iterator_category; return count_switch(begin, end, value, iterator_category(), parallelism_tag); } template inline typename iterator_traits::difference_type count(InputIterator begin, InputIterator end, const T& value) { typedef iterator_traits traits_type; typedef typename traits_type::iterator_category iterator_category; return count_switch(begin, end, value, iterator_category()); } // Sequential fallback. template inline typename iterator_traits::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 iterator_traits::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 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(end - begin) >= __gnu_parallel::_Settings::get().count_minimal_n && __gnu_parallel::is_parallel(parallelism_tag))) { difference_type res = 0; __gnu_parallel:: count_if_selector functionality; __gnu_parallel:: for_each_template_random_access(begin, end, pred, functionality, std::plus(), 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 inline typename iterator_traits::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 inline typename iterator_traits::difference_type count_if(InputIterator begin, InputIterator end, Predicate pred, __gnu_parallel::_Parallelism parallelism_tag) { typedef iterator_traits traits_type; typedef typename traits_type::iterator_category iterator_category; return count_if_switch(begin, end, pred, iterator_category(), parallelism_tag); } template inline typename iterator_traits::difference_type count_if(InputIterator begin, InputIterator end, Predicate pred) { typedef iterator_traits traits_type; typedef typename traits_type::iterator_category iterator_category; return count_if_switch(begin, end, pred, iterator_category()); } // Sequential fallback. template 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 RandomAccessIterator1 search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, RandomAccessIterator2 end2, random_access_iterator_tag, random_access_iterator_tag) { typedef std::iterator_traits iterator1_traits; typedef typename iterator1_traits::value_type value1_type; typedef std::iterator_traits 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()); else return search(begin1, end1, begin2, end2, __gnu_parallel::sequential_tag()); } // Sequential fallback for input iterator case template 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 inline ForwardIterator1 search(ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2) { typedef std::iterator_traits iterator1_traits; typedef typename iterator1_traits::iterator_category iterator1_category; typedef std::iterator_traits iterator2_traits; typedef typename iterator2_traits::iterator_category iterator2_category; return search_switch(begin1, end1, begin2, end2, iterator1_category(), iterator2_category()); } // Public interface. template 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 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 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 inline ForwardIterator1 search(ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2, BinaryPredicate pred) { typedef std::iterator_traits iterator1_traits; typedef typename iterator1_traits::iterator_category iterator1_category; typedef std::iterator_traits 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 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 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 inline ForwardIterator search_n(ForwardIterator begin, ForwardIterator end, Integer count, const T& val) { typedef typename iterator_traits::value_type value_type; return search_n(begin, end, count, val, __gnu_parallel::equal_to()); } // Parallel algorithm for random access iterators. template 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 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 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 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:: iterator_category()); } // Sequential fallback. template 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 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 ip; ip begin_pair(begin, result), end_pair(end, result + (end - begin)); __gnu_parallel::transform1_selector 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 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 inline OutputIterator transform(InputIterator begin, InputIterator end, OutputIterator result, UnaryOperation unary_op, __gnu_parallel::_Parallelism parallelism_tag) { typedef std::iterator_traits iteratori_traits; typedef std::iterator_traits 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 inline OutputIterator transform(InputIterator begin, InputIterator end, OutputIterator result, UnaryOperation unary_op) { typedef std::iterator_traits iteratori_traits; typedef std::iterator_traits 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 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 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 ip; ip begin_triple(begin1, begin2, result), end_triple(end1, begin2 + (end1 - begin1), result + (end1 - begin1)); __gnu_parallel::transform2_selector 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 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 inline OutputIterator transform(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, OutputIterator result, BinaryOperation binary_op, __gnu_parallel::_Parallelism parallelism_tag) { typedef std::iterator_traits iteratori1_traits; typedef typename iteratori1_traits::iterator_category iteratori1_category; typedef std::iterator_traits iteratori2_traits; typedef typename iteratori2_traits::iterator_category iteratori2_category; typedef std::iterator_traits 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 inline OutputIterator transform(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, OutputIterator result, BinaryOperation binary_op) { typedef std::iterator_traits iteratori1_traits; typedef typename iteratori1_traits::iterator_category iteratori1_category; typedef std::iterator_traits iteratori2_traits; typedef typename iteratori2_traits::iterator_category iteratori2_category; typedef std::iterator_traits 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 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 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 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 inline void replace(ForwardIterator begin, ForwardIterator end, const T& old_value, const T& new_value, __gnu_parallel::_Parallelism parallelism_tag) { typedef iterator_traits traits_type; typedef typename traits_type::iterator_category iterator_category; replace_switch(begin, end, old_value, new_value, iterator_category(), parallelism_tag); } template inline void replace(ForwardIterator begin, ForwardIterator end, const T& old_value, const T& new_value) { typedef iterator_traits traits_type; typedef typename traits_type::iterator_category iterator_category; replace_switch(begin, end, old_value, new_value, iterator_category()); } // Sequential fallback template 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 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 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 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 inline void replace_if(ForwardIterator begin, ForwardIterator end, Predicate pred, const T& new_value, __gnu_parallel::_Parallelism parallelism_tag) { typedef std::iterator_traits iterator_traits; typedef typename iterator_traits::iterator_category iterator_category; replace_if_switch(begin, end, pred, new_value, iterator_category(), parallelism_tag); } template inline void replace_if(ForwardIterator begin, ForwardIterator end, Predicate pred, const T& new_value) { typedef std::iterator_traits iterator_traits; typedef typename iterator_traits::iterator_category iterator_category; replace_if_switch(begin, end, pred, new_value, iterator_category()); } // Sequential fallback template 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 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 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 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 inline void generate(ForwardIterator begin, ForwardIterator end, Generator gen, __gnu_parallel::_Parallelism parallelism_tag) { typedef std::iterator_traits iterator_traits; typedef typename iterator_traits::iterator_category iterator_category; generate_switch(begin, end, gen, iterator_category(), parallelism_tag); } template inline void generate(ForwardIterator begin, ForwardIterator end, Generator gen) { typedef std::iterator_traits iterator_traits; typedef typename iterator_traits::iterator_category iterator_category; generate_switch(begin, end, gen, iterator_category()); } // Sequential fallback. template 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 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 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 inline OutputIterator generate_n(OutputIterator begin, Size n, Generator gen, __gnu_parallel::_Parallelism parallelism_tag) { typedef std::iterator_traits iterator_traits; typedef typename iterator_traits::iterator_category iterator_category; return generate_n_switch(begin, n, gen, iterator_category(), parallelism_tag); } template inline OutputIterator generate_n(OutputIterator begin, Size n, Generator gen) { typedef std::iterator_traits iterator_traits; typedef typename iterator_traits::iterator_category iterator_category; return generate_n_switch(begin, n, gen, iterator_category()); } // Sequential fallback. template inline void random_shuffle(RandomAccessIterator begin, RandomAccessIterator end, __gnu_parallel::sequential_tag) { _GLIBCXX_STD_P::random_shuffle(begin, end); } // Sequential fallback. template 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 struct c_rand_number { int operator()(int limit) { return rand() % limit; } }; // Fill in random number generator. template 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 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 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 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 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:: 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 inline ForwardIterator partition(ForwardIterator begin, ForwardIterator end, Predicate pred) { typedef iterator_traits traits_type; typedef typename traits_type::iterator_category iterator_category; return partition_switch(begin, end, pred, iterator_category()); } // sort interface // Sequential fallback template inline void sort(RandomAccessIterator begin, RandomAccessIterator end, __gnu_parallel::sequential_tag) { _GLIBCXX_STD_P::sort(begin, end); } // Sequential fallback template inline void sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, __gnu_parallel::sequential_tag) { _GLIBCXX_STD_P::sort(begin, end, comp); } // Public interface template void sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, Parallelism parallelism) { typedef iterator_traits 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(begin, end, comp, parallelism); else sort(begin, end, comp, __gnu_parallel::sequential_tag()); } } // Public interface, insert default comparator template inline void sort(RandomAccessIterator begin, RandomAccessIterator end) { typedef iterator_traits traits_type; typedef typename traits_type::value_type value_type; sort(begin, end, std::less(), __gnu_parallel::default_parallel_tag()); } // Public interface, insert default comparator template inline void sort(RandomAccessIterator begin, RandomAccessIterator end, __gnu_parallel::default_parallel_tag parallelism) { typedef iterator_traits traits_type; typedef typename traits_type::value_type value_type; sort(begin, end, std::less(), parallelism); } // Public interface, insert default comparator template inline void sort(RandomAccessIterator begin, RandomAccessIterator end, __gnu_parallel::parallel_tag parallelism) { typedef iterator_traits traits_type; typedef typename traits_type::value_type value_type; sort(begin, end, std::less(), parallelism); } // Public interface, insert default comparator template inline void sort(RandomAccessIterator begin, RandomAccessIterator end, __gnu_parallel::multiway_mergesort_tag parallelism) { typedef iterator_traits traits_type; typedef typename traits_type::value_type value_type; sort(begin, end, std::less(), parallelism); } // Public interface, insert default comparator template inline void sort(RandomAccessIterator begin, RandomAccessIterator end, __gnu_parallel::multiway_mergesort_sampling_tag parallelism) { typedef iterator_traits traits_type; typedef typename traits_type::value_type value_type; sort(begin, end, std::less(), parallelism); } // Public interface, insert default comparator template inline void sort(RandomAccessIterator begin, RandomAccessIterator end, __gnu_parallel::multiway_mergesort_exact_tag parallelism) { typedef iterator_traits traits_type; typedef typename traits_type::value_type value_type; sort(begin, end, std::less(), parallelism); } // Public interface, insert default comparator template inline void sort(RandomAccessIterator begin, RandomAccessIterator end, __gnu_parallel::quicksort_tag parallelism) { typedef iterator_traits traits_type; typedef typename traits_type::value_type value_type; sort(begin, end, std::less(), parallelism); } // Public interface, insert default comparator template inline void sort(RandomAccessIterator begin, RandomAccessIterator end, __gnu_parallel::balanced_quicksort_tag parallelism) { typedef iterator_traits traits_type; typedef typename traits_type::value_type value_type; sort(begin, end, std::less(), parallelism); } // Public interface template void sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp) { typedef iterator_traits 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 inline void stable_sort(RandomAccessIterator begin, RandomAccessIterator end, __gnu_parallel::sequential_tag) { _GLIBCXX_STD_P::stable_sort(begin, end); } // Sequential fallback template inline void stable_sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, __gnu_parallel::sequential_tag) { _GLIBCXX_STD_P::stable_sort( begin, end, comp); } // Public interface template void stable_sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, Parallelism parallelism) { typedef iterator_traits 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(begin, end, comp, parallelism); else stable_sort(begin, end, comp, __gnu_parallel::sequential_tag()); } } // Public interface, insert default comparator template inline void stable_sort(RandomAccessIterator begin, RandomAccessIterator end) { typedef iterator_traits traits_type; typedef typename traits_type::value_type value_type; stable_sort(begin, end, std::less(), __gnu_parallel::default_parallel_tag()); } // Public interface, insert default comparator template inline void stable_sort(RandomAccessIterator begin, RandomAccessIterator end, __gnu_parallel::default_parallel_tag parallelism) { typedef iterator_traits traits_type; typedef typename traits_type::value_type value_type; stable_sort(begin, end, std::less(), parallelism); } // Public interface, insert default comparator template inline void stable_sort(RandomAccessIterator begin, RandomAccessIterator end, __gnu_parallel::parallel_tag parallelism) { typedef iterator_traits traits_type; typedef typename traits_type::value_type value_type; stable_sort(begin, end, std::less(), parallelism); } // Public interface, insert default comparator template inline void stable_sort(RandomAccessIterator begin, RandomAccessIterator end, __gnu_parallel::multiway_mergesort_tag parallelism) { typedef iterator_traits traits_type; typedef typename traits_type::value_type value_type; stable_sort(begin, end, std::less(), parallelism); } // Public interface, insert default comparator template inline void stable_sort(RandomAccessIterator begin, RandomAccessIterator end, __gnu_parallel::quicksort_tag parallelism) { typedef iterator_traits traits_type; typedef typename traits_type::value_type value_type; stable_sort(begin, end, std::less(), parallelism); } // Public interface, insert default comparator template inline void stable_sort(RandomAccessIterator begin, RandomAccessIterator end, __gnu_parallel::balanced_quicksort_tag parallelism) { typedef iterator_traits traits_type; typedef typename traits_type::value_type value_type; stable_sort(begin, end, std::less(), parallelism); } // Public interface template void stable_sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp) { typedef iterator_traits traits_type; typedef typename traits_type::value_type value_type; stable_sort(begin, end, comp, __gnu_parallel::default_parallel_tag()); } // // Sequential fallback // template // inline void // stable_sort(RandomAccessIterator begin, RandomAccessIterator end, // __gnu_parallel::sequential_tag) // { return _GLIBCXX_STD_P::stable_sort(begin, end); } // // // Sequential fallback // template // inline void // stable_sort(RandomAccessIterator begin, RandomAccessIterator end, // Comparator comp, __gnu_parallel::sequential_tag) // { return _GLIBCXX_STD_P::stable_sort(begin, end, comp); } // // template // void // stable_sort(RandomAccessIterator begin, RandomAccessIterator end) // { // typedef iterator_traits traits_type; // typedef typename traits_type::value_type value_type; // stable_sort(begin, end, std::less()); // } // // // Parallel algorithm for random access iterators // template // 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 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 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 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 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 inline OutputIterator merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator result, Comparator comp) { typedef typename iterator_traits::value_type value_type; typedef std::iterator_traits iteratori1_traits; typedef std::iterator_traits iteratori2_traits; typedef std::iterator_traits 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 inline OutputIterator merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator result) { typedef std::iterator_traits iterator1_traits; typedef std::iterator_traits 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()); } // Sequential fallback template 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 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 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 inline void nth_element(RandomAccessIterator begin, RandomAccessIterator nth, RandomAccessIterator end) { typedef iterator_traits traits_type; typedef typename traits_type::value_type value_type; nth_element(begin, nth, end, std::less()); } // Sequential fallback template 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 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 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 inline void partial_sort(RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end) { typedef iterator_traits traits_type; typedef typename traits_type::value_type value_type; partial_sort(begin, middle, end, std::less()); } // Sequential fallback template inline ForwardIterator max_element(ForwardIterator begin, ForwardIterator end, __gnu_parallel::sequential_tag) { return _GLIBCXX_STD_P::max_element(begin, end); } // Sequential fallback template 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 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 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 functionality; __gnu_parallel:: for_each_template_random_access(begin, end, __gnu_parallel::nothing(), functionality, __gnu_parallel:: max_element_reduct(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 inline ForwardIterator max_element(ForwardIterator begin, ForwardIterator end, __gnu_parallel::_Parallelism parallelism_tag) { typedef typename iterator_traits::value_type value_type; return max_element(begin, end, std::less(), parallelism_tag); } template inline ForwardIterator max_element(ForwardIterator begin, ForwardIterator end) { typedef typename iterator_traits::value_type value_type; return max_element(begin, end, std::less()); } // Public interface template inline ForwardIterator max_element(ForwardIterator begin, ForwardIterator end, Comparator comp, __gnu_parallel::_Parallelism parallelism_tag) { typedef iterator_traits traits_type; typedef typename traits_type::iterator_category iterator_category; return max_element_switch(begin, end, comp, iterator_category(), parallelism_tag); } template inline ForwardIterator max_element(ForwardIterator begin, ForwardIterator end, Comparator comp) { typedef iterator_traits traits_type; typedef typename traits_type::iterator_category iterator_category; return max_element_switch(begin, end, comp, iterator_category()); } // Sequential fallback template inline ForwardIterator min_element(ForwardIterator begin, ForwardIterator end, __gnu_parallel::sequential_tag) { return _GLIBCXX_STD_P::min_element(begin, end); } // Sequential fallback template 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 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 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 functionality; __gnu_parallel:: for_each_template_random_access(begin, end, __gnu_parallel::nothing(), functionality, __gnu_parallel:: min_element_reduct(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 inline ForwardIterator min_element(ForwardIterator begin, ForwardIterator end, __gnu_parallel::_Parallelism parallelism_tag) { typedef typename iterator_traits::value_type value_type; return min_element(begin, end, std::less(), parallelism_tag); } template inline ForwardIterator min_element(ForwardIterator begin, ForwardIterator end) { typedef typename iterator_traits::value_type value_type; return min_element(begin, end, std::less()); } // Public interface template inline ForwardIterator min_element(ForwardIterator begin, ForwardIterator end, Comparator comp, __gnu_parallel::_Parallelism parallelism_tag) { typedef iterator_traits traits_type; typedef typename traits_type::iterator_category iterator_category; return min_element_switch(begin, end, comp, iterator_category(), parallelism_tag); } template inline ForwardIterator min_element(ForwardIterator begin, ForwardIterator end, Comparator comp) { typedef iterator_traits 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 */