This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.
| Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
|---|---|---|
| Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
| Other format: | [Raw text] | |
This patch enables the compile-time choice of the parallelism variant, for sorting so far. This can reduce compilation time and object code size significantly. Also, the user can propose the number of threads to use for a specific call, without having to set it globally via omp_set_num_threads(). This is important for the upcoming OpenMP-in-pthread nesting. The algorithms still work correct even if not enough threads are alloted by the OpenMP runtime. The default behavior is unchanged, conforming to OpenMP conventions concerning the number of threads.
We want to extend this principle to other parallelized algorithms, e. g. for_each and similar.
* 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.Index: include/parallel/quicksort.h
===================================================================
--- include/parallel/quicksort.h (revision 134194)
+++ include/parallel/quicksort.h (working copy)
@@ -87,7 +87,8 @@
__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);
@@ -162,9 +163,8 @@
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 +172,11 @@
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);
Index: include/parallel/balanced_quicksort.h
===================================================================
--- include/parallel/balanced_quicksort.h (revision 134194)
+++ include/parallel/balanced_quicksort.h (working copy)
@@ -252,7 +252,8 @@
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;
@@ -423,8 +424,6 @@
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 +435,8 @@
typedef QSBThreadLocal<RandomAccessIterator> tls_type;
+ difference_type n = end - begin;
+
if (n <= 1)
return;
Index: include/parallel/tags.h
===================================================================
--- include/parallel/tags.h (revision 134194)
+++ include/parallel/tags.h (working copy)
@@ -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. */
@@ -48,8 +51,45 @@
struct exact_tag { };
/** @brief Recommends parallel execution at compile time. */
- struct parallel_tag { };
+ struct parallel_tag
+ {
+ private:
+ thread_index_t num_threads;
+ public:
+ parallel_tag()
+ {
+ this->num_threads = 0;
+ }
+
+ parallel_tag(thread_index_t num_threads)
+ {
+ this->num_threads = num_threads;
+ }
+
+ inline thread_index_t get_num_threads()
+ {
+ if(num_threads == 0)
+ return omp_get_max_threads();
+ else
+ return num_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. */
struct balanced_tag : public parallel_tag { };
@@ -67,8 +107,56 @@
struct omp_loop_static_tag : public parallel_tag { };
+ /** @brief Base class for for std::find() variants. */
struct find_tag { };
+
+ /** @brief Recommends parallel execution using OpenMP static
+ load-balancing 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 Recommends parallel execution using OpenMP static
+ load-balancing 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 Recommends parallel execution using OpenMP static
+ load-balancing 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 Recommends parallel execution using OpenMP static
+ load-balancing at compile time. */
+ struct quicksort_tag : public parallel_tag
+ {
+ quicksort_tag() { }
+ quicksort_tag(thread_index_t num_threads)
+ : parallel_tag(num_threads) { }
+ };
+
+ /** @brief Recommends parallel execution using OpenMP static
+ load-balancing 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 { };
Index: include/parallel/merge.h
===================================================================
--- include/parallel/merge.h (revision 134194)
+++ include/parallel/merge.h (working copy)
@@ -248,7 +248,7 @@
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
Index: include/parallel/algo.h
===================================================================
--- include/parallel/algo.h (revision 134194)
+++ include/parallel/algo.h (working copy)
@@ -72,51 +72,52 @@
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;
+ 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);
- }
+ 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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
// 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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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,21 +1713,44 @@
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>
inline void
@@ -1733,128 +1758,317 @@
{
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 @@
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 @@
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,
+