diff options
| -rw-r--r-- | libstdc++-v3/ChangeLog | 16 | ||||
| -rw-r--r-- | libstdc++-v3/include/parallel/algo.h | 1692 | ||||
| -rw-r--r-- | libstdc++-v3/include/parallel/balanced_quicksort.h | 8 | ||||
| -rw-r--r-- | libstdc++-v3/include/parallel/merge.h | 2 | ||||
| -rw-r--r-- | libstdc++-v3/include/parallel/quicksort.h | 14 | ||||
| -rw-r--r-- | libstdc++-v3/include/parallel/sort.h | 181 | ||||
| -rw-r--r-- | libstdc++-v3/include/parallel/tags.h | 102 |
7 files changed, 1226 insertions, 789 deletions
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 8405db6..dfa4a47 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,5 +1,21 @@ 2008-04-23 Johannes Singler <singler@ira.uka.de> + * include/parallel/quicksort.h: Reformat, + (parallel_sort_qs): Do not pass number of elements. + * include/parallel/balanced_quicksort.h: Reformat, + (parallel_sort_qsb): Do not pass number of elements. + * include/parallel/tags.h: + Introduce new tags for compile-time choice. + * include/parallel/merge.h: + (parallel_merge_advance):Beautified. + * include/parallel/algo.h: Reformatting (spaces for tabs) + New sort and stable_sort variants, corresponding to the tags. + * include/parallel/sort.h: + New sort and stable_sort variants, corresponding to the tags. + Changed determining the desired number of threads. + +2008-04-23 Johannes Singler <singler@ira.uka.de> + * include/parallel/multiway_merge.h (multiway_merge_loser_tree): Leave checks to callers, add precondition instead. diff --git a/libstdc++-v3/include/parallel/algo.h b/libstdc++-v3/include/parallel/algo.h index e836b28..397d7cb 100644 --- a/libstdc++-v3/include/parallel/algo.h +++ b/libstdc++-v3/include/parallel/algo.h @@ -72,51 +72,52 @@ namespace __parallel template<typename InputIterator, typename Function> inline Function for_each(InputIterator begin, InputIterator end, Function f, - __gnu_parallel::sequential_tag) + __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) + 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) + 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); - } + 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()); + 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) + __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); + parallelism_tag); } template<typename Iterator, typename Function> @@ -133,35 +134,35 @@ namespace __parallel template<typename InputIterator, typename T> inline InputIterator find(InputIterator begin, InputIterator end, const T& val, - __gnu_parallel::sequential_tag) + __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) + 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) + 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, T> > - comp(__gnu_parallel::equal_to<value_type, T>(), val); - return __gnu_parallel::find_template(begin, end, begin, comp, - __gnu_parallel:: - find_if_selector()).first; - } + { + binder2nd<__gnu_parallel::equal_to<value_type, T> > + comp(__gnu_parallel::equal_to<value_type, 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); + return _GLIBCXX_STD_P::find(begin, end, val); } // Public interface @@ -178,28 +179,28 @@ namespace __parallel template<typename InputIterator, typename Predicate> inline InputIterator find_if(InputIterator begin, InputIterator end, Predicate pred, - __gnu_parallel::sequential_tag) + __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) + 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) + 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; + 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); + return _GLIBCXX_STD_P::find_if(begin, end, pred); } // Public interface @@ -216,63 +217,63 @@ namespace __parallel template<typename InputIterator, typename ForwardIterator> inline InputIterator find_first_of(InputIterator begin1, InputIterator end1, - ForwardIterator begin2, ForwardIterator end2, - __gnu_parallel::sequential_tag) + 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> + typename BinaryPredicate> inline InputIterator find_first_of(InputIterator begin1, InputIterator end1, - ForwardIterator begin2, ForwardIterator end2, - BinaryPredicate comp, __gnu_parallel::sequential_tag) + 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> + typename IteratorTag1, typename IteratorTag2> inline InputIterator find_first_of_switch(InputIterator begin1, InputIterator end1, - ForwardIterator begin2, ForwardIterator end2, - IteratorTag1, IteratorTag2) + ForwardIterator begin2, ForwardIterator end2, + IteratorTag1, IteratorTag2) { return find_first_of(begin1, end1, begin2, end2, - __gnu_parallel::sequential_tag()); } + __gnu_parallel::sequential_tag()); } // Parallel algorithm for random access iterators template<typename RandomAccessIterator, typename ForwardIterator, - typename BinaryPredicate, typename IteratorTag> + 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) + 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; + 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> + typename BinaryPredicate, typename IteratorTag1, + typename IteratorTag2> inline InputIterator find_first_of_switch(InputIterator begin1, InputIterator end1, - ForwardIterator begin2, ForwardIterator end2, - BinaryPredicate comp, IteratorTag1, IteratorTag2) + ForwardIterator begin2, ForwardIterator end2, + BinaryPredicate comp, IteratorTag1, IteratorTag2) { return find_first_of(begin1, end1, begin2, end2, comp, - __gnu_parallel::sequential_tag()); } + __gnu_parallel::sequential_tag()); } // Public interface template<typename InputIterator, typename ForwardIterator, - typename BinaryPredicate> + typename BinaryPredicate> inline InputIterator find_first_of(InputIterator begin1, InputIterator end1, - ForwardIterator begin2, ForwardIterator end2, - BinaryPredicate comp) + ForwardIterator begin2, ForwardIterator end2, + BinaryPredicate comp) { typedef std::iterator_traits<InputIterator> iteratori_traits; typedef std::iterator_traits<ForwardIterator> iteratorf_traits; @@ -280,14 +281,14 @@ namespace __parallel typedef typename iteratorf_traits::iterator_category iteratorf_category; return find_first_of_switch(begin1, end1, begin2, end2, comp, - iteratori_category(), iteratorf_category()); + 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) + ForwardIterator begin2, ForwardIterator end2) { typedef std::iterator_traits<InputIterator> iteratori_traits; typedef std::iterator_traits<ForwardIterator> iteratorf_traits; @@ -295,47 +296,47 @@ namespace __parallel typedef typename iteratorf_traits::value_type valuef_type; return find_first_of(begin1, end1, begin2, end2, __gnu_parallel:: - equal_to<valuei_type, valuef_type>()); + 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) + __gnu_parallel::sequential_tag) { return _GLIBCXX_STD_P::unique_copy(begin1, end1, out); } // Sequential fallback template<typename InputIterator, typename OutputIterator, - typename Predicate> + typename Predicate> inline OutputIterator unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out, - Predicate pred, __gnu_parallel::sequential_tag) + 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> + typename Predicate, typename IteratorTag1, typename IteratorTag2> inline OutputIterator unique_copy_switch(InputIterator begin, InputIterator last, - OutputIterator out, Predicate pred, - IteratorTag1, IteratorTag2) + 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> + typename Predicate> RandomAccessOutputIterator unique_copy_switch(RandomAccessIterator begin, RandomAccessIterator last, - RandomAccessOutputIterator out, Predicate pred, - random_access_iterator_tag, random_access_iterator_tag) + 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); + 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); + return _GLIBCXX_STD_P::unique_copy(begin, last, out, pred); } // Public interface @@ -350,14 +351,14 @@ namespace __parallel typedef typename iteratoro_traits::iterator_category iteratoro_category; return unique_copy_switch(begin1, end1, out, equal_to<value_type>(), - iteratori_category(), iteratoro_category()); + 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) + Predicate pred) { typedef std::iterator_traits<InputIterator> iteratori_traits; typedef std::iterator_traits<OutputIterator> iteratoro_traits; @@ -365,484 +366,484 @@ namespace __parallel typedef typename iteratoro_traits::iterator_category iteratoro_category; return unique_copy_switch(begin1, end1, out, pred, iteratori_category(), - iteratoro_category()); + iteratoro_category()); } // Sequential fallback template<typename InputIterator1, typename InputIterator2, - typename OutputIterator> + typename OutputIterator> inline OutputIterator set_union(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out, __gnu_parallel::sequential_tag) + 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> + typename OutputIterator, typename Predicate> inline OutputIterator set_union(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out, Predicate pred, - __gnu_parallel::sequential_tag) + InputIterator2 begin2, InputIterator2 end2, + OutputIterator out, Predicate pred, + __gnu_parallel::sequential_tag) { return _GLIBCXX_STD_P::set_union(begin1, end1, - begin2, end2, out, pred); } + 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> + 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) + InputIterator2 begin2, InputIterator2 end2, + OutputIterator result, Predicate pred, IteratorTag1, + IteratorTag2, IteratorTag3) { return _GLIBCXX_STD_P::set_union(begin1, end1, - begin2, end2, result, pred); } + begin2, end2, result, pred); } // Parallel set_union for random access iterators template<typename RandomAccessIterator1, typename RandomAccessIterator2, - typename OutputRandomAccessIterator, typename Predicate> + 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) + 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); + 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); + return _GLIBCXX_STD_P::set_union(begin1, end1, + begin2, end2, result, pred); } // Public interface template<typename InputIterator1, typename InputIterator2, - typename OutputIterator> + typename OutputIterator> inline OutputIterator set_union(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, OutputIterator out) + 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; + iteratori1_category; typedef typename iteratori2_traits::iterator_category - iteratori2_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()); + __gnu_parallel::less<value1_type, value2_type>(), + iteratori1_category(), iteratori2_category(), + iteratoro_category()); } // Public interface template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename Predicate> + typename OutputIterator, typename Predicate> inline OutputIterator set_union(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out, Predicate pred) + 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; + iteratori1_category; typedef typename iteratori2_traits::iterator_category - iteratori2_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()); + iteratori1_category(), iteratori2_category(), + iteratoro_category()); } // Sequential fallback. template<typename InputIterator1, typename InputIterator2, - typename OutputIterator> + typename OutputIterator> inline OutputIterator set_intersection(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out, __gnu_parallel::sequential_tag) + InputIterator2 begin2, InputIterator2 end2, + OutputIterator out, __gnu_parallel::sequential_tag) { return _GLIBCXX_STD_P::set_intersection(begin1, end1, - begin2, end2, out); } + begin2, end2, out); } // Sequential fallback. template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename Predicate> + typename OutputIterator, typename Predicate> inline OutputIterator set_intersection(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out, Predicate pred, - __gnu_parallel::sequential_tag) + InputIterator2 begin2, InputIterator2 end2, + OutputIterator out, Predicate pred, + __gnu_parallel::sequential_tag) { return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, end2, - out, pred); } + out, pred); } // Sequential fallback for input iterator case template<typename InputIterator1, typename InputIterator2, - typename Predicate, typename OutputIterator, - typename IteratorTag1, typename IteratorTag2, - typename IteratorTag3> + 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) + InputIterator2 begin2, InputIterator2 end2, + OutputIterator result, Predicate pred, + IteratorTag1, IteratorTag2, IteratorTag3) { return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, - end2, result, pred); } + end2, result, pred); } // Parallel set_intersection for random access iterators template<typename RandomAccessIterator1, typename RandomAccessIterator2, - typename OutputRandomAccessIterator, typename Predicate> + 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) + 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); + 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); + return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, + end2, result, pred); } // Public interface template<typename InputIterator1, typename InputIterator2, - typename OutputIterator> + typename OutputIterator> inline OutputIterator set_intersection(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out) + 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; + iteratori1_category; typedef typename iteratori2_traits::iterator_category - iteratori2_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()); + __gnu_parallel:: + less<value1_type, value2_type>(), + iteratori1_category(), + iteratori2_category(), + iteratoro_category()); } template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename Predicate> + typename OutputIterator, typename Predicate> inline OutputIterator set_intersection(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out, Predicate pred) + 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; + iteratori1_category; typedef typename iteratori2_traits::iterator_category - iteratori2_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()); + iteratori1_category(), + iteratori2_category(), + iteratoro_category()); } // Sequential fallback template<typename InputIterator1, typename InputIterator2, - typename OutputIterator> + typename OutputIterator> inline OutputIterator set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out, - __gnu_parallel::sequential_tag) + InputIterator2 begin2, InputIterator2 end2, + OutputIterator out, + __gnu_parallel::sequential_tag) { return _GLIBCXX_STD_P::set_symmetric_difference(begin1,end1, - begin2, end2, out); } + begin2, end2, out); } // Sequential fallback template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename Predicate> + 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) + 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); } + end2, out, pred); } // Sequential fallback for input iterator case template<typename InputIterator1, typename InputIterator2, - typename Predicate, typename OutputIterator, - typename IteratorTag1, typename IteratorTag2, - typename IteratorTag3> + 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) + 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); } + begin2, end2, + result, pred); } // Parallel set_symmetric_difference for random access iterators template<typename RandomAccessIterator1, typename RandomAccessIterator2, - typename OutputRandomAccessIterator, typename Predicate> + 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) + 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); + 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); + return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1, + begin2, end2, + result, pred); } // Public interface. template<typename InputIterator1, typename InputIterator2, - typename OutputIterator> + typename OutputIterator> inline OutputIterator set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out) + 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; + iteratori1_category; typedef typename iteratori2_traits::iterator_category - iteratori2_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()); + __gnu_parallel:: + less<value1_type, value2_type>(), + iteratori1_category(), + iteratori2_category(), + iteratoro_category()); } // Public interface. template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename Predicate> + typename OutputIterator, typename Predicate> inline OutputIterator set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out, Predicate pred) + 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; + iteratori1_category; typedef typename iteratori2_traits::iterator_category - iteratori2_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()); + pred, iteratori1_category(), + iteratori2_category(), + iteratoro_category()); } // Sequential fallback. template<typename InputIterator1, typename InputIterator2, - typename OutputIterator> + typename OutputIterator> inline OutputIterator set_difference(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out, __gnu_parallel::sequential_tag) + 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> + typename OutputIterator, typename Predicate> inline OutputIterator set_difference(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out, Predicate pred, - __gnu_parallel::sequential_tag) + InputIterator2 begin2, InputIterator2 end2, + OutputIterator out, Predicate pred, + __gnu_parallel::sequential_tag) { return _GLIBCXX_STD_P::set_difference(begin1, end1, - begin2, end2, out, pred); } + 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> + 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) + InputIterator2 begin2, InputIterator2 end2, + OutputIterator result, Predicate pred, + IteratorTag1, IteratorTag2, IteratorTag3) { return _GLIBCXX_STD_P::set_difference(begin1, end1, - begin2, end2, result, pred); } + begin2, end2, result, pred); } // Parallel set_difference for random access iterators template<typename RandomAccessIterator1, typename RandomAccessIterator2, - typename OutputRandomAccessIterator, typename Predicate> + 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) + 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); + 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); + return _GLIBCXX_STD_P::set_difference(begin1, end1, + begin2, end2, result, pred); } // Public interface template<typename InputIterator1, typename InputIterator2, - typename OutputIterator> + typename OutputIterator> inline OutputIterator set_difference(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out) + 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; + iteratori1_category; typedef typename iteratori2_traits::iterator_category - iteratori2_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()); + __gnu_parallel:: + less<value1_type, value2_type>(), + iteratori1_category(), + iteratori2_category(), + iteratoro_category()); } // Public interface template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename Predicate> + typename OutputIterator, typename Predicate> inline OutputIterator set_difference(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, InputIterator2 end2, - OutputIterator out, Predicate pred) + 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; + iteratori1_category; typedef typename iteratori2_traits::iterator_category - iteratori2_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()); + iteratori1_category(), + iteratori2_category(), + iteratoro_category()); } // Sequential fallback template<typename ForwardIterator> inline ForwardIterator adjacent_find(ForwardIterator begin, ForwardIterator end, - __gnu_parallel::sequential_tag) + __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) + 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) + 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; - } + { + 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()); + 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) + IteratorTag) { return adjacent_find(begin, end, __gnu_parallel::sequential_tag()); } // Public interface @@ -857,33 +858,33 @@ namespace __parallel // Sequential fallback for input iterator case template<typename ForwardIterator, typename BinaryPredicate, - typename IteratorTag> + typename IteratorTag> inline ForwardIterator adjacent_find_switch(ForwardIterator begin, ForwardIterator end, - BinaryPredicate pred, IteratorTag) + BinaryPredicate pred, IteratorTag) { return adjacent_find(begin, end, pred, - __gnu_parallel::sequential_tag()); } + __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) + 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; + 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()); + 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) + BinaryPredicate pred) { typedef iterator_traits<ForwardIterator> traits_type; typedef typename traits_type::iterator_category iterator_category; @@ -894,16 +895,16 @@ namespace __parallel template<typename InputIterator, typename T> inline typename iterator_traits<InputIterator>::difference_type count(InputIterator begin, InputIterator end, const T& value, - __gnu_parallel::sequential_tag) + __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) + 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; @@ -911,41 +912,41 @@ namespace __parallel 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; - } + 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()); + 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) + 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) + __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); + parallelism_tag); } template<typename InputIterator, typename T> @@ -962,16 +963,16 @@ namespace __parallel template<typename InputIterator, typename Predicate> inline typename iterator_traits<InputIterator>::difference_type count_if(InputIterator begin, InputIterator end, Predicate pred, - __gnu_parallel::sequential_tag) + __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) + 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; @@ -979,42 +980,42 @@ namespace __parallel 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; - } + 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()); + 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) + 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) + __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); + parallelism_tag); } template<typename InputIterator, typename Predicate> @@ -1031,16 +1032,16 @@ namespace __parallel template<typename ForwardIterator1, typename ForwardIterator2> inline ForwardIterator1 search(ForwardIterator1 begin1, ForwardIterator1 end1, - ForwardIterator2 begin2, ForwardIterator2 end2, - __gnu_parallel::sequential_tag) + 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) + 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; @@ -1048,29 +1049,29 @@ namespace __parallel 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>()); + 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()); + 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> + typename IteratorTag1, typename IteratorTag2> inline ForwardIterator1 search_switch(ForwardIterator1 begin1, ForwardIterator1 end1, - ForwardIterator2 begin2, ForwardIterator2 end2, - IteratorTag1, IteratorTag2) + ForwardIterator2 begin2, ForwardIterator2 end2, + IteratorTag1, IteratorTag2) { return search(begin1, end1, begin2, end2, - __gnu_parallel::sequential_tag()); } + __gnu_parallel::sequential_tag()); } // Public interface. template<typename ForwardIterator1, typename ForwardIterator2> inline ForwardIterator1 search(ForwardIterator1 begin1, ForwardIterator1 end1, - ForwardIterator2 begin2, ForwardIterator2 end2) + ForwardIterator2 begin2, ForwardIterator2 end2) { typedef std::iterator_traits<ForwardIterator1> iterator1_traits; typedef typename iterator1_traits::iterator_category iterator1_category; @@ -1078,187 +1079,187 @@ namespace __parallel typedef typename iterator2_traits::iterator_category iterator2_category; return search_switch(begin1, end1, begin2, end2, - iterator1_category(), iterator2_category()); + iterator1_category(), iterator2_category()); } // Public interface. template<typename ForwardIterator1, typename ForwardIterator2, - typename BinaryPredicate> + typename BinaryPredicate> inline ForwardIterator1 search(ForwardIterator1 begin1, ForwardIterator1 end1, - ForwardIterator2 begin2, ForwardIterator2 end2, - BinaryPredicate pred, __gnu_parallel::sequential_tag) + 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> + typename BinaryPredicate> RandomAccessIterator1 search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, - RandomAccessIterator2 begin2, RandomAccessIterator2 end2, - BinaryPredicate pred, - random_access_iterator_tag, random_access_iterator_tag) + 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); + return __gnu_parallel::search_template(begin1, end1, + begin2, end2, pred); else - return search(begin1, end1, begin2, end2, pred, - __gnu_parallel::sequential_tag()); + 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> + typename BinaryPredicate, typename IteratorTag1, + typename IteratorTag2> inline ForwardIterator1 search_switch(ForwardIterator1 begin1, ForwardIterator1 end1, - ForwardIterator2 begin2, ForwardIterator2 end2, - BinaryPredicate pred, IteratorTag1, IteratorTag2) + ForwardIterator2 begin2, ForwardIterator2 end2, + BinaryPredicate pred, IteratorTag1, IteratorTag2) { return search(begin1, end1, begin2, end2, pred, - __gnu_parallel::sequential_tag()); } + __gnu_parallel::sequential_tag()); } // Public interface template<typename ForwardIterator1, typename ForwardIterator2, - typename BinaryPredicate> + typename BinaryPredicate> inline ForwardIterator1 search(ForwardIterator1 begin1, ForwardIterator1 end1, - ForwardIterator2 begin2, ForwardIterator2 end2, - BinaryPredicate pred) + 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()); + 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) + 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> + typename BinaryPredicate> inline ForwardIterator search_n(ForwardIterator begin, ForwardIterator end, Integer count, - const T& val, BinaryPredicate binary_pred, - __gnu_parallel::sequential_tag) + 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) + 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>()); + __gnu_parallel::equal_to<value_type, T>()); } // Parallel algorithm for random access iterators. template<typename RandomAccessIterator, typename Integer, - typename T, typename BinaryPredicate> + typename T, typename BinaryPredicate> RandomAccessIterator search_n_switch(RandomAccessIterator begin, RandomAccessIterator end, - Integer count, const T& val, BinaryPredicate binary_pred, - random_access_iterator_tag) + 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); - } + { + __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()); + 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> + typename BinaryPredicate, typename IteratorTag> inline ForwardIterator search_n_switch(ForwardIterator begin, ForwardIterator end, Integer count, - const T& val, BinaryPredicate binary_pred, IteratorTag) + 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> + typename BinaryPredicate> inline ForwardIterator search_n(ForwardIterator begin, ForwardIterator end, Integer count, - const T& val, BinaryPredicate binary_pred) + const T& val, BinaryPredicate binary_pred) { return search_n_switch(begin, end, count, val, binary_pred, - typename std::iterator_traits<ForwardIterator>:: - iterator_category()); + typename std::iterator_traits<ForwardIterator>:: + iterator_category()); } // Sequential fallback. template<typename InputIterator, typename OutputIterator, - typename UnaryOperation> + typename UnaryOperation> inline OutputIterator transform(InputIterator begin, InputIterator end, OutputIterator result, - UnaryOperation unary_op, __gnu_parallel::sequential_tag) + 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> + 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) + 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; - } + 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()); + 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> + typename UnaryOperation, typename IteratorTag1, + typename IteratorTag2> inline RandomAccessIterator2 transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end, - RandomAccessIterator2 result, UnaryOperation unary_op, - IteratorTag1, IteratorTag2) + RandomAccessIterator2 result, UnaryOperation unary_op, + IteratorTag1, IteratorTag2) { return transform(begin, end, result, unary_op, - __gnu_parallel::sequential_tag()); } + __gnu_parallel::sequential_tag()); } // Public interface. template<typename InputIterator, typename OutputIterator, - typename UnaryOperation> + typename UnaryOperation> inline OutputIterator transform(InputIterator begin, InputIterator end, OutputIterator result, - UnaryOperation unary_op, - __gnu_parallel::_Parallelism parallelism_tag) + UnaryOperation unary_op, + __gnu_parallel::_Parallelism parallelism_tag) { typedef std::iterator_traits<InputIterator> iteratori_traits; typedef std::iterator_traits<OutputIterator> iteratoro_traits; @@ -1266,15 +1267,15 @@ namespace __parallel typedef typename iteratoro_traits::iterator_category iteratoro_category; return transform1_switch(begin, end, result, unary_op, - iteratori_category(), iteratoro_category(), - parallelism_tag); + iteratori_category(), iteratoro_category(), + parallelism_tag); } template<typename InputIterator, typename OutputIterator, - typename UnaryOperation> + typename UnaryOperation> inline OutputIterator transform(InputIterator begin, InputIterator end, OutputIterator result, - UnaryOperation unary_op) + UnaryOperation unary_op) { typedef std::iterator_traits<InputIterator> iteratori_traits; typedef std::iterator_traits<OutputIterator> iteratoro_traits; @@ -1282,157 +1283,158 @@ namespace __parallel typedef typename iteratoro_traits::iterator_category iteratoro_category; return transform1_switch(begin, end, result, unary_op, - iteratori_category(), iteratoro_category()); + iteratori_category(), iteratoro_category()); } // Sequential fallback template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename BinaryOperation> + typename OutputIterator, typename BinaryOperation> inline OutputIterator transform(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, OutputIterator result, - BinaryOperation binary_op, __gnu_parallel::sequential_tag) + InputIterator2 begin2, OutputIterator result, + BinaryOperation binary_op, __gnu_parallel::sequential_tag) { return _GLIBCXX_STD_P::transform(begin1, end1, - begin2, result, binary_op); } + begin2, result, binary_op); } // Parallel binary transform for random access iterators. template<typename RandomAccessIterator1, typename RandomAccessIterator2, - typename RandomAccessIterator3, typename BinaryOperation> + 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) + 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; - } + (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()); + 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> + 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) + InputIterator2 begin2, OutputIterator result, + BinaryOperation binary_op, tag1, tag2, tag3) { return transform(begin1, end1, begin2, result, binary_op, - __gnu_parallel::sequential_tag()); } + __gnu_parallel::sequential_tag()); } // Public interface. template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename BinaryOperation> + typename OutputIterator, typename BinaryOperation> inline OutputIterator transform(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, OutputIterator result, - BinaryOperation binary_op, - __gnu_parallel::_Parallelism parallelism_tag) + 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; + iteratori1_category; typedef std::iterator_traits<InputIterator2> iteratori2_traits; typedef typename iteratori2_traits::iterator_category - iteratori2_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); + iteratori1_category(), iteratori2_category(), + iteratoro_category(), parallelism_tag); } template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename BinaryOperation> + typename OutputIterator, typename BinaryOperation> inline OutputIterator transform(InputIterator1 begin1, InputIterator1 end1, - InputIterator2 begin2, OutputIterator result, - BinaryOperation binary_op) + InputIterator2 begin2, OutputIterator result, + BinaryOperation binary_op) { typedef std::iterator_traits<InputIterator1> iteratori1_traits; typedef typename iteratori1_traits::iterator_category - iteratori1_category; + iteratori1_category; typedef std::iterator_traits<InputIterator2> iteratori2_traits; typedef typename iteratori2_traits::iterator_category - iteratori2_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()); + 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) + 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) + const T& old_value, const T& new_value, IteratorTag) { replace(begin, end, old_value, new_value, - __gnu_parallel::sequential_tag()); } + __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) + 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()); + __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) + 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); + parallelism_tag); } template<typename ForwardIterator, typename T> inline void replace(ForwardIterator begin, ForwardIterator end, const T& old_value, - const T& new_value) + const T& new_value) { typedef iterator_traits<ForwardIterator> traits_type; typedef typename traits_type::iterator_category iterator_category; @@ -1444,64 +1446,64 @@ namespace __parallel 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) + 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> + typename IteratorTag> inline void replace_if_switch(ForwardIterator begin, ForwardIterator end, - Predicate pred, const T& new_value, IteratorTag) + Predicate pred, const T& new_value, IteratorTag) { replace_if(begin, end, pred, new_value, - __gnu_parallel::sequential_tag()); } + __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) + 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); - } + 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()); + 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) + 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); + parallelism_tag); } template<typename ForwardIterator, typename Predicate, typename T> inline void replace_if(ForwardIterator begin, ForwardIterator end, - Predicate pred, const T& new_value) + Predicate pred, const T& new_value) { typedef std::iterator_traits<ForwardIterator> iterator_traits; typedef typename iterator_traits::iterator_category iterator_category; @@ -1512,46 +1514,46 @@ namespace __parallel template<typename ForwardIterator, typename Generator> inline void generate(ForwardIterator begin, ForwardIterator end, Generator gen, - __gnu_parallel::sequential_tag) + __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) + 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) + 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); - } + 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()); + 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) + Generator gen, __gnu_parallel::_Parallelism parallelism_tag) { typedef std::iterator_traits<ForwardIterator> iterator_traits; typedef typename iterator_traits::iterator_category iterator_category; @@ -1572,12 +1574,12 @@ namespace __parallel template<typename OutputIterator, typename Size, typename Generator> inline OutputIterator generate_n(OutputIterator begin, Size n, Generator gen, - __gnu_parallel::sequential_tag) + __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> + typename IteratorTag> inline OutputIterator generate_n_switch(OutputIterator begin, Size n, Generator gen, IteratorTag) { return generate_n(begin, n, gen, __gnu_parallel::sequential_tag()); } @@ -1586,9 +1588,9 @@ namespace __parallel 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) + 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()); @@ -1598,12 +1600,12 @@ namespace __parallel template<typename OutputIterator, typename Size, typename Generator> inline OutputIterator generate_n(OutputIterator begin, Size n, Generator gen, - __gnu_parallel::_Parallelism parallelism_tag) + __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); + parallelism_tag); } template<typename OutputIterator, typename Size, typename Generator> @@ -1620,14 +1622,14 @@ namespace __parallel template<typename RandomAccessIterator> inline void random_shuffle(RandomAccessIterator begin, RandomAccessIterator end, - __gnu_parallel::sequential_tag) + __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) + RandomNumberGenerator& rand, __gnu_parallel::sequential_tag) { _GLIBCXX_STD_P::random_shuffle(begin, end, rand); } @@ -1654,51 +1656,51 @@ namespace __parallel template<typename RandomAccessIterator, typename RandomNumberGenerator> void random_shuffle(RandomAccessIterator begin, RandomAccessIterator end, - RandomNumberGenerator& rand) + RandomNumberGenerator& rand) { if (begin == end) - return; + 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); + 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); + __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) + 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) + 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) + 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; - } + 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()); + return partition(begin, end, pred, __gnu_parallel::sequential_tag()); } // Public interface. @@ -1711,20 +1713,43 @@ namespace __parallel 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) + __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) + __gnu_parallel::sequential_tag) { _GLIBCXX_STD_P::sort<RandomAccessIterator, Comparator>(begin, end, - comp); } + 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> @@ -1733,128 +1758,317 @@ namespace __parallel { typedef iterator_traits<RandomAccessIterator> traits_type; typedef typename traits_type::value_type value_type; - sort(begin, end, std::less<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()); + } - 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, false); - else - sort(begin, end, comp, __gnu_parallel::sequential_tag()); - } - } - // Sequential fallback. + // stable_sort interface + + + // 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); } + inline void + stable_sort(RandomAccessIterator begin, RandomAccessIterator end, + __gnu_parallel::sequential_tag) + { _GLIBCXX_STD_P::stable_sort(begin, end); } - // Sequential fallback. + // 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); } + 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>()); - } + 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()); + } - // Parallel algorithm for random access iterators + // 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) - { - 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, true); - else - stable_sort(begin, end, comp, __gnu_parallel::sequential_tag()); - } - } + 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> + typename OutputIterator> inline OutputIterator merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, - InputIterator2 end2, OutputIterator result, - __gnu_parallel::sequential_tag) + 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> + typename OutputIterator, typename Comparator> inline OutputIterator merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, - InputIterator2 end2, OutputIterator result, Comparator comp, - __gnu_parallel::sequential_tag) + 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> + 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) + InputIterator2 begin2, InputIterator2 end2, + OutputIterator result, Comparator comp, + IteratorTag1, IteratorTag2, IteratorTag3) { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, - result, comp); } + result, comp); } // Parallel algorithm for random access iterators template<typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename Comparator> + 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) + 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); + (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); + 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> + typename OutputIterator, typename Comparator> inline OutputIterator merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, - InputIterator2 end2, OutputIterator result, Comparator comp) + InputIterator2 end2, OutputIterator result, Comparator comp) { typedef typename iterator_traits<InputIterator1>::value_type value_type; @@ -1862,23 +2076,23 @@ namespace __parallel typedef std::iterator_traits<InputIterator2> iteratori2_traits; typedef std::iterator_traits<OutputIterator> iteratoro_traits; typedef typename iteratori1_traits::iterator_category - iteratori1_category; + iteratori1_category; typedef typename iteratori2_traits::iterator_category - iteratori2_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()); + iteratori1_category(), iteratori2_category(), + iteratoro_category()); } // Public interface, insert default comparator template<typename InputIterator1, typename InputIterator2, - typename OutputIterator> + typename OutputIterator> inline OutputIterator merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, - InputIterator2 end2, OutputIterator result) + InputIterator2 end2, OutputIterator result) { typedef std::iterator_traits<InputIterator1> iterator1_traits; typedef std::iterator_traits<InputIterator2> iterator2_traits; @@ -1886,43 +2100,43 @@ namespace __parallel typedef typename iterator2_traits::value_type value2_type; return merge(begin1, end1, begin2, end2, result, - __gnu_parallel::less<value1_type, value2_type>()); + __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) + 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) + 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) + 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); + 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()); + 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) + RandomAccessIterator end) { typedef iterator_traits<RandomAccessIterator> traits_type; typedef typename traits_type::value_type value_type; @@ -1933,37 +2147,37 @@ namespace __parallel template<typename RandomAccessIterator, typename _Compare> inline void partial_sort(RandomAccessIterator begin, RandomAccessIterator middle, - RandomAccessIterator end, _Compare comp, - __gnu_parallel::sequential_tag) + 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) + 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) + 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); + 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()); + 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) + RandomAccessIterator end) { typedef iterator_traits<RandomAccessIterator> traits_type; typedef typename traits_type::value_type value_type; @@ -1974,58 +2188,58 @@ namespace __parallel template<typename ForwardIterator> inline ForwardIterator max_element(ForwardIterator begin, ForwardIterator end, - __gnu_parallel::sequential_tag) + __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) + __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) + 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) + 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; - } + 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()); + 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) + __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); @@ -2043,12 +2257,12 @@ namespace __parallel template<typename ForwardIterator, typename Comparator> inline ForwardIterator max_element(ForwardIterator begin, ForwardIterator end, Comparator comp, - __gnu_parallel::_Parallelism parallelism_tag) + __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); + parallelism_tag); } template<typename ForwardIterator, typename Comparator> @@ -2065,58 +2279,58 @@ namespace __parallel template<typename ForwardIterator> inline ForwardIterator min_element(ForwardIterator begin, ForwardIterator end, - __gnu_parallel::sequential_tag) + __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) + __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) + 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) + 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; - } + 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()); + 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) + __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); @@ -2134,12 +2348,12 @@ namespace __parallel template<typename ForwardIterator, typename Comparator> inline ForwardIterator min_element(ForwardIterator begin, ForwardIterator end, Comparator comp, - __gnu_parallel::_Parallelism parallelism_tag) + __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); + parallelism_tag); } template<typename ForwardIterator, typename Comparator> diff --git a/libstdc++-v3/include/parallel/balanced_quicksort.h b/libstdc++-v3/include/parallel/balanced_quicksort.h index f6b3297..d94cf33 100644 --- a/libstdc++-v3/include/parallel/balanced_quicksort.h +++ b/libstdc++-v3/include/parallel/balanced_quicksort.h @@ -252,7 +252,8 @@ template<typename RandomAccessIterator, typename Comparator> QSBThreadLocal<RandomAccessIterator>& tl = *tls[iam]; - difference_type base_case_n = _Settings::get().sort_qsb_base_case_maximal_n; + difference_type base_case_n = + _Settings::get().sort_qsb_base_case_maximal_n; if (base_case_n < 2) base_case_n = 2; thread_index_t num_threads = tl.num_threads; @@ -415,7 +416,6 @@ template<typename RandomAccessIterator, typename Comparator> * @param begin Begin iterator of sequence. * @param end End iterator of sequence. * @param comp Comparator. - * @param n Length of the sequence to sort. * @param num_threads Number of threads that are allowed to work on * this part. */ @@ -423,8 +423,6 @@ template<typename RandomAccessIterator, typename Comparator> void parallel_sort_qsb(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, - typename std::iterator_traits<RandomAccessIterator> - ::difference_type n, thread_index_t num_threads) { _GLIBCXX_CALL(end - begin) @@ -436,6 +434,8 @@ template<typename RandomAccessIterator, typename Comparator> typedef QSBThreadLocal<RandomAccessIterator> tls_type; + difference_type n = end - begin; + if (n <= 1) return; diff --git a/libstdc++-v3/include/parallel/merge.h b/libstdc++-v3/include/parallel/merge.h index 6e0f2e3..cabd5bd 100644 --- a/libstdc++-v3/include/parallel/merge.h +++ b/libstdc++-v3/include/parallel/merge.h @@ -248,7 +248,7 @@ namespace __gnu_parallel typedef typename std::pair<RandomAccessIterator1, RandomAccessIterator1> iterator_pair; - std::pair<RandomAccessIterator1, RandomAccessIterator1> + iterator_pair seqs[2] = { std::make_pair(begin1, end1), std::make_pair(begin2, end2) }; RandomAccessIterator3 diff --git a/libstdc++-v3/include/parallel/quicksort.h b/libstdc++-v3/include/parallel/quicksort.h index de95549..8ef5b7c 100644 --- a/libstdc++-v3/include/parallel/quicksort.h +++ b/libstdc++-v3/include/parallel/quicksort.h @@ -87,7 +87,8 @@ namespace __gnu_parallel __gnu_parallel::binder2nd<Comparator, value_type, value_type, bool> pred(comp, pivot); - difference_type split = parallel_partition(begin, end, pred, num_threads); + difference_type split = + parallel_partition(begin, end, pred, num_threads); ::operator delete(samples); @@ -154,7 +155,6 @@ namespace __gnu_parallel * @param begin Begin iterator of input sequence. * @param end End iterator input sequence, ignored. * @param comp Comparator. - * @param n Length of input sequence. * @param num_threads Number of threads that are allowed to work on * this part. */ @@ -162,9 +162,8 @@ namespace __gnu_parallel void parallel_sort_qs(RandomAccessIterator begin, RandomAccessIterator end, - Comparator comp, typename std::iterator_traits - <RandomAccessIterator>::difference_type n, - int num_threads) + Comparator comp, + thread_index_t num_threads) { _GLIBCXX_CALL(n) @@ -172,12 +171,11 @@ namespace __gnu_parallel typedef typename traits_type::value_type value_type; typedef typename traits_type::difference_type difference_type; - if (n == 0) - return; + difference_type n = end - begin; // At least one element per processor. if (num_threads > n) - num_threads = static_cast<thread_index_t>(n); + num_threads = static_cast<thread_index_t>(n); // Hard to avoid. omp_set_num_threads(num_threads); diff --git a/libstdc++-v3/include/parallel/sort.h b/libstdc++-v3/include/parallel/sort.h index 83aa2df..559ed1c 100644 --- a/libstdc++-v3/include/parallel/sort.h +++ b/libstdc++-v3/include/parallel/sort.h @@ -60,7 +60,136 @@ namespace __gnu_parallel { + //prototype + template<bool stable, typename RandomAccessIterator, + typename Comparator, typename Parallelism> + void + parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, + Comparator comp, Parallelism parallelism); + /** + * @brief Choose multiway mergesort, splitting variant at run-time, + * for parallel sorting. + * @param begin Begin iterator of input sequence. + * @param end End iterator of input sequence. + * @param comp Comparator. + * @callgraph + */ + template<bool stable, typename RandomAccessIterator, typename Comparator> + inline void + parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, + Comparator comp, multiway_mergesort_tag parallelism) + { + _GLIBCXX_CALL(end - begin) + + if(_Settings::get().sort_splitting == EXACT) + parallel_sort_mwms<stable, true> + (begin, end, comp, parallelism.get_num_threads()); + else + parallel_sort_mwms<stable, false> + (begin, end, comp, parallelism.get_num_threads()); + } + + /** + * @brief Choose multiway mergesort with exact splitting, + * for parallel sorting. + * @param begin Begin iterator of input sequence. + * @param end End iterator of input sequence. + * @param comp Comparator. + * @callgraph + */ + template<bool stable, typename RandomAccessIterator, typename Comparator> + inline void + parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, + Comparator comp, multiway_mergesort_exact_tag parallelism) + { + _GLIBCXX_CALL(end - begin) + + parallel_sort_mwms<stable, true> + (begin, end, comp, parallelism.get_num_threads()); + } + + /** + * @brief Choose multiway mergesort with splitting by sampling, + * for parallel sorting. + * @param begin Begin iterator of input sequence. + * @param end End iterator of input sequence. + * @param comp Comparator. + * @callgraph + */ + template<bool stable, typename RandomAccessIterator, typename Comparator> + inline void + parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, + Comparator comp, multiway_mergesort_sampling_tag parallelism) + { + _GLIBCXX_CALL(end - begin) + + parallel_sort_mwms<stable, false> + (begin, end, comp, parallelism.get_num_threads()); + } + + /** + * @brief Choose quicksort for parallel sorting. + * @param begin Begin iterator of input sequence. + * @param end End iterator of input sequence. + * @param comp Comparator. + * @callgraph + */ + template<bool stable, typename RandomAccessIterator, typename Comparator> + inline void + parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, + Comparator comp, quicksort_tag parallelism) + { + _GLIBCXX_CALL(end - begin) + + _GLIBCXX_PARALLEL_ASSERT(stable == false); + + parallel_sort_qs(begin, end, comp, parallelism.get_num_threads()); + } + + /** + * @brief Choose balanced quicksort for parallel sorting. + * @param begin Begin iterator of input sequence. + * @param end End iterator of input sequence. + * @param comp Comparator. + * @param stable Sort stable. + * @callgraph + */ + template<bool stable, typename RandomAccessIterator, typename Comparator> + inline void + parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, + Comparator comp, balanced_quicksort_tag parallelism) + { + _GLIBCXX_CALL(end - begin) + + _GLIBCXX_PARALLEL_ASSERT(stable == false); + + parallel_sort_qsb(begin, end, comp, parallelism.get_num_threads()); + } + + + /** + * @brief Choose multiway mergesort with exact splitting, + * for parallel sorting. + * @param begin Begin iterator of input sequence. + * @param end End iterator of input sequence. + * @param comp Comparator. + * @callgraph + */ + template<bool stable, typename RandomAccessIterator, typename Comparator> + inline void + parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, + Comparator comp, default_parallel_tag parallelism) + { + _GLIBCXX_CALL(end - begin) + + parallel_sort<stable> + (begin, end, comp, + multiway_mergesort_exact_tag(parallelism.get_num_threads())); + } + + + /** * @brief Choose a parallel sorting algorithm. * @param begin Begin iterator of input sequence. * @param end End iterator of input sequence. @@ -68,54 +197,38 @@ namespace __gnu_parallel * @param stable Sort stable. * @callgraph */ - template<typename RandomAccessIterator, typename Comparator> + template<bool stable, typename RandomAccessIterator, typename Comparator> inline void parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, - Comparator comp, bool stable) + Comparator comp, parallel_tag parallelism) { _GLIBCXX_CALL(end - begin) typedef std::iterator_traits<RandomAccessIterator> traits_type; typedef typename traits_type::value_type value_type; typedef typename traits_type::difference_type difference_type; - if (begin != end) - { - difference_type n = end - begin; - - if (false) ; + if (false) ; #if _GLIBCXX_MERGESORT - else if (stable) - { - if(_Settings::get().sort_splitting == EXACT) - parallel_sort_mwms<true, true> - (begin, end, comp, get_max_threads()); - else - parallel_sort_mwms<true, false> - (begin, end, comp, get_max_threads()); - } - else if (_Settings::get().sort_algorithm == MWMS) - { - if(_Settings::get().sort_splitting == EXACT) - parallel_sort_mwms<false, true> - (begin, end, comp, get_max_threads()); - else - parallel_sort_mwms<false, false> - (begin, end, comp, get_max_threads()); - } + else if (stable || _Settings::get().sort_algorithm == MWMS) + { + if(_Settings::get().sort_splitting == EXACT) + parallel_sort_mwms<stable, true> + (begin, end, comp, parallelism.get_num_threads()); + else + parallel_sort_mwms<false, false> + (begin, end, comp, parallelism.get_num_threads()); + } #endif #if _GLIBCXX_QUICKSORT - else if (!stable && _Settings::get().sort_algorithm == QS) - parallel_sort_qs(begin, end, comp, n, get_max_threads()); + else if (_Settings::get().sort_algorithm == QS) + parallel_sort_qs(begin, end, comp, parallelism.get_num_threads()); #endif #if _GLIBCXX_BAL_QUICKSORT - else if (!stable && _Settings::get().sort_algorithm == QS_BALANCED) - parallel_sort_qsb(begin, end, comp, n, get_max_threads()); + else if (_Settings::get().sort_algorithm == QS_BALANCED) + parallel_sort_qsb(begin, end, comp, parallelism.get_num_threads()); #endif - else if(stable) - __gnu_sequential::stable_sort(begin, end, comp); - else - __gnu_sequential::sort(begin, end, comp); - } + else + __gnu_sequential::sort(begin, end, comp); } } // end namespace __gnu_parallel diff --git a/libstdc++-v3/include/parallel/tags.h b/libstdc++-v3/include/parallel/tags.h index f57add9..cf937af 100644 --- a/libstdc++-v3/include/parallel/tags.h +++ b/libstdc++-v3/include/parallel/tags.h @@ -1,6 +1,6 @@ // -*- C++ -*- -// Copyright (C) 2007 Free Software Foundation, Inc. +// Copyright (C) 2007, 2008 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 @@ -39,6 +39,9 @@ #ifndef _GLIBCXX_PARALLEL_TAGS_H #define _GLIBCXX_PARALLEL_TAGS_H 1 +#include <omp.h> +#include <parallel/types.h> + namespace __gnu_parallel { /** @brief Forces sequential execution at compile time. */ @@ -47,8 +50,53 @@ namespace __gnu_parallel /** @brief Forces exact splitting in multiway merge at compile time. */ struct exact_tag { }; - /** @brief Recommends parallel execution at compile time. */ - struct parallel_tag { }; + /** @brief Recommends parallel execution at compile time, + * optionally using a user-specified number of threads. */ + struct parallel_tag + { + private: + thread_index_t num_threads; + + public: + /** @brief Default constructor. Use default number of threads. */ + parallel_tag() + { + this->num_threads = 0; + } + + /** @brief Default constructor. Recommend number of threads to use. + * @param num_threads Desired number of threads. */ + parallel_tag(thread_index_t num_threads) + { + this->num_threads = num_threads; + } + + /** @brief Find out desired number of threads. + * @return Desired number of threads. */ + inline thread_index_t get_num_threads() + { + if(num_threads == 0) + return omp_get_max_threads(); + else + return num_threads; + } + + /** @brief Set the desired number of threads. + * @param num_threads Desired number of threads. */ + inline void set_num_threads(thread_index_t num_threads) + { + this->num_threads = num_threads; + } + }; + + /** @brief Recommends parallel execution using the + default parallel algorithm. */ + struct default_parallel_tag : public parallel_tag + { + default_parallel_tag() { } + default_parallel_tag(thread_index_t num_threads) + : parallel_tag(num_threads) { } + }; /** @brief Recommends parallel execution using dynamic load-balancing at compile time. */ @@ -67,8 +115,56 @@ namespace __gnu_parallel struct omp_loop_static_tag : public parallel_tag { }; + /** @brief Base class for for std::find() variants. */ struct find_tag { }; + + /** @brief Forces parallel sorting using multiway mergesort + * at compile time. */ + struct multiway_mergesort_tag : public parallel_tag + { + multiway_mergesort_tag() { } + multiway_mergesort_tag(thread_index_t num_threads) + : parallel_tag(num_threads) { } + }; + + /** @brief Forces parallel sorting using multiway mergesort + * with exact splitting at compile time. */ + struct multiway_mergesort_exact_tag : public parallel_tag + { + multiway_mergesort_exact_tag() { } + multiway_mergesort_exact_tag(thread_index_t num_threads) + : parallel_tag(num_threads) { } + }; + + /** @brief Forces parallel sorting using multiway mergesort + * with splitting by sampling at compile time. */ + struct multiway_mergesort_sampling_tag : public parallel_tag + { + multiway_mergesort_sampling_tag() { } + multiway_mergesort_sampling_tag(thread_index_t num_threads) + : parallel_tag(num_threads) { } + }; + + /** @brief Forces parallel sorting using unbalanced quicksort + * at compile time. */ + struct quicksort_tag : public parallel_tag + { + quicksort_tag() { } + quicksort_tag(thread_index_t num_threads) + : parallel_tag(num_threads) { } + }; + + /** @brief Forces parallel sorting using balanced quicksort + * at compile time. */ + struct balanced_quicksort_tag : public parallel_tag + { + balanced_quicksort_tag() { } + balanced_quicksort_tag(thread_index_t num_threads) + : parallel_tag(num_threads) { } + }; + + /** @brief Selects the growing block size variant for std::find(). @see _GLIBCXX_FIND_GROWING_BLOCKS */ struct growing_blocks_tag : public find_tag { }; |