This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[PATCH][libstdc++-v3 parallel mode]
- From: Johannes Singler <singler at ira dot uka dot de>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>, gcc-patches at gcc dot gnu dot org
- Date: Thu, 29 Nov 2007 15:22:07 +0100
- Subject: [PATCH][libstdc++-v3 parallel mode]
I reformatted on a basic level the remaining files except the ones that
expect significant changes soon:
-Max line length
-Tabs to spaces
-Pragmas consistent
Tested x86_64-unknown-linux-gnu: No regressions
Please approve (necessary in this case?).
2007-11-29 Johannes Singler <singler@ira.uka.de>
* include/parallel/iterator.h: Reformatting.
* include/parallel/find_selectors.h: Reformatting.
* include/parallel/list_partition.h: Reformatting.
* include/parallel/for_each.h: Reformatting.
* include/parallel/multiseq_selection.h: Reformatting.
* include/parallel/algorithmfwd.h: Reformatting.
* include/parallel/for_each_selectors.h: Reformatting.
* include/parallel/balanced_quicksort.h: Reformatting.
* include/parallel/merge.h: Reformatting.
* include/parallel/unique_copy.h: Reformatting.
* include/parallel/settings.h: Reformatting.
* include/parallel/numericfwd.h: Reformatting.
* include/parallel/search.h: Reformatting.
* include/parallel/partition.h: Reformatting.
* include/parallel/algobase.h: Reformatting.
* include/parallel/algo.h: Reformatting.
* include/parallel/queue.h: Reformatting.
* include/parallel/checkers.h: Reformatting.
Johannes
Index: include/parallel/iterator.h
===================================================================
--- include/parallel/iterator.h (revision 130490)
+++ include/parallel/iterator.h (working copy)
@@ -43,10 +43,10 @@
namespace __gnu_parallel
{
- /** @brief A pair of iterators. The usual iterator operations are
- * applied to both child iterators.
- */
- template<typename Iterator1, typename Iterator2, typename IteratorCategory>
+/** @brief A pair of iterators. The usual iterator operations are
+ * applied to both child iterators.
+ */
+template<typename Iterator1, typename Iterator2, typename IteratorCategory>
class iterator_pair : public std::pair<Iterator1, Iterator2>
{
private:
@@ -117,14 +117,16 @@
};
- /** @brief A triple of iterators. The usual iterator operations are
- applied to all three child iterators.
- */
- template<typename Iterator1, typename Iterator2, typename Iterator3, typename IteratorCategory>
+/** @brief A triple of iterators. The usual iterator operations are
+ applied to all three child iterators.
+ */
+template<typename Iterator1, typename Iterator2, typename Iterator3,
+ typename IteratorCategory>
class iterator_triple
{
private:
- typedef iterator_triple<Iterator1, Iterator2, Iterator3, IteratorCategory> type;
+ typedef iterator_triple<Iterator1, Iterator2, Iterator3, IteratorCategory>
+ type;
public:
typedef IteratorCategory iterator_category;
Index: include/parallel/find_selectors.h
===================================================================
--- include/parallel/find_selectors.h (revision 130490)
+++ include/parallel/find_selectors.h (working copy)
@@ -60,7 +60,8 @@
* @param i2 Iterator on second sequence (unused).
* @param pred Find predicate.
*/
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
inline bool
operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
{ return pred(*i1); }
@@ -71,11 +72,15 @@
* @param begin2 Begin iterator of second sequence.
* @param pred Find predicate.
*/
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
inline std::pair<RandomAccessIterator1, RandomAccessIterator2>
- sequential_algorithm(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred)
+ sequential_algorithm(RandomAccessIterator1 begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator2 begin2, Pred pred)
{
- return std::make_pair(find_if(begin1, end1, pred, sequential_tag()), begin2);
+ return std::make_pair(find_if(begin1, end1, pred, sequential_tag()),
+ begin2);
}
};
@@ -87,7 +92,8 @@
* @param i2 Iterator on second sequence (unused).
* @param pred Find predicate.
*/
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
inline bool
operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
{
@@ -101,14 +107,18 @@
* @param begin2 Begin iterator of second sequence.
* @param pred Find predicate.
*/
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
inline std::pair<RandomAccessIterator1, RandomAccessIterator2>
- sequential_algorithm(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred)
+ sequential_algorithm(RandomAccessIterator1 begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator2 begin2, Pred pred)
{
// Passed end iterator is one short.
- RandomAccessIterator1 spot = adjacent_find(begin1, end1 + 1, pred, sequential_tag());
+ RandomAccessIterator1 spot = adjacent_find(begin1, end1 + 1, pred,
+ sequential_tag());
if (spot == (end1 + 1))
- spot = end1;
+ spot = end1;
return std::make_pair(spot, begin2);
}
};
@@ -122,7 +132,8 @@
* @param i2 Iterator on second sequence (unused).
* @param pred Find predicate.
*/
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
inline bool
operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
{ return !pred(*i1, *i2); }
@@ -134,9 +145,12 @@
* @param begin2 Begin iterator of second sequence.
* @param pred Find predicate.
*/
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
inline std::pair<RandomAccessIterator1, RandomAccessIterator2>
- sequential_algorithm(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred)
+ sequential_algorithm(RandomAccessIterator1 begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator2 begin2, Pred pred)
{
return mismatch(begin1, end1, begin2, pred, sequential_tag());
}
@@ -144,7 +158,7 @@
/** @brief Test predicate on several elements. */
- template<typename ForwardIterator>
+template<typename ForwardIterator>
struct find_first_of_selector : public generic_find_selector
{
ForwardIterator begin;
@@ -157,13 +171,16 @@
* @param i1 Iterator on first sequence.
* @param i2 Iterator on second sequence (unused).
* @param pred Find predicate. */
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
inline bool
operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
{
- for (ForwardIterator pos_in_candidates = begin; pos_in_candidates != end; pos_in_candidates++)
- if (pred(*i1, *pos_in_candidates))
- return true;
+ for (ForwardIterator pos_in_candidates = begin;
+ pos_in_candidates != end;
+ ++pos_in_candidates)
+ if (pred(*i1, *pos_in_candidates))
+ return true;
return false;
}
@@ -172,11 +189,16 @@
* @param end1 End iterator of first sequence.
* @param begin2 Begin iterator of second sequence.
* @param pred Find predicate. */
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
inline std::pair<RandomAccessIterator1, RandomAccessIterator2>
- sequential_algorithm(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred)
+ sequential_algorithm(RandomAccessIterator1 begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator2 begin2, Pred pred)
{
- return std::make_pair(find_first_of(begin1, end1, begin, end, pred, sequential_tag()), begin2);
+ return std::make_pair(find_first_of(begin1, end1, begin, end, pred,
+ sequential_tag()),
+ begin2);
}
};
}
Index: include/parallel/list_partition.h
===================================================================
--- include/parallel/list_partition.h (revision 130490)
+++ include/parallel/list_partition.h (working copy)
@@ -44,77 +44,79 @@
namespace __gnu_parallel
{
- /** @brief Shrinks and doubles the ranges.
- * @param os_starts Start positions worked on (oversampled).
- * @param count_to_two Counts up to 2.
- * @param range_length Current length of a chunk.
- * @param make_twice Whether the @c os_starts is allowed to be
- * grown or not
- */
- template<typename InputIterator>
+/** @brief Shrinks and doubles the ranges.
+ * @param os_starts Start positions worked on (oversampled).
+ * @param count_to_two Counts up to 2.
+ * @param range_length Current length of a chunk.
+ * @param make_twice Whether the @c os_starts is allowed to be
+ * grown or not
+ */
+template<typename InputIterator>
void
- shrink_and_double(std::vector<InputIterator>& os_starts, size_t& count_to_two, size_t& range_length, const bool make_twice)
+ shrink_and_double(std::vector<InputIterator>& os_starts,
+ size_t& count_to_two, size_t& range_length,
+ const bool make_twice)
{
++count_to_two;
if (not make_twice or count_to_two < 2)
- {
- shrink(os_starts, count_to_two, range_length);
- }
+ shrink(os_starts, count_to_two, range_length);
else
{
- os_starts.resize((os_starts.size() - 1) * 2 + 1);
- count_to_two = 0;
+ os_starts.resize((os_starts.size() - 1) * 2 + 1);
+ count_to_two = 0;
}
}
- /** @brief Combines two ranges into one and thus halves the number of ranges.
- * @param os_starts Start positions worked on (oversampled).
- * @param count_to_two Counts up to 2.
- * @param range_length Current length of a chunk. */
- template<typename InputIterator>
+/** @brief Combines two ranges into one and thus halves the number of ranges.
+ * @param os_starts Start positions worked on (oversampled).
+ * @param count_to_two Counts up to 2.
+ * @param range_length Current length of a chunk. */
+template<typename InputIterator>
void
shrink(std::vector<InputIterator>& os_starts, size_t& count_to_two,
- size_t& range_length)
+ size_t& range_length)
{
- for (typename std::vector<InputIterator>::size_type i = 0; i <= (os_starts.size() / 2); ++i)
+ for (typename std::vector<InputIterator>::size_type i = 0;
+ i <= (os_starts.size() / 2);
+ ++i)
{
- os_starts[i] = os_starts[i * 2];
+ os_starts[i] = os_starts[i * 2];
}
range_length *= 2;
}
- /** @brief Splits a sequence given by input iterators into parts of
- * almost equal size
- *
- * The function needs only one pass over the sequence.
- * @param begin Begin iterator of input sequence.
- * @param end End iterator of input sequence.
- * @param starts Start iterators for the resulting parts, dimension
- * @c num_parts+1. For convenience, @c starts @c [num_parts]
- * contains the end iterator of the sequence.
- * @param lengths Length of the resulting parts.
- * @param num_parts Number of parts to split the sequence into.
- * @param f Functor to be applied to each element by traversing it
- * @param oversampling Oversampling factor. If 0, then the
- * partitions will differ in at most @f$ \sqrt{\mathrm{end} -
- * \mathrm{begin}} @f$ elements. Otherwise, the ratio between the
- * longest and the shortest part is bounded by @f$
- * 1/(\mathrm{oversampling} \cdot \mathrm{num\_parts}) @f$.
- * @return Length of the whole sequence.
- */
- template<typename InputIterator, typename FunctorType>
+/** @brief Splits a sequence given by input iterators into parts of
+ * almost equal size
+ *
+ * The function needs only one pass over the sequence.
+ * @param begin Begin iterator of input sequence.
+ * @param end End iterator of input sequence.
+ * @param starts Start iterators for the resulting parts, dimension
+ * @c num_parts+1. For convenience, @c starts @c [num_parts]
+ * contains the end iterator of the sequence.
+ * @param lengths Length of the resulting parts.
+ * @param num_parts Number of parts to split the sequence into.
+ * @param f Functor to be applied to each element by traversing it
+ * @param oversampling Oversampling factor. If 0, then the
+ * partitions will differ in at most @f$ \sqrt{\mathrm{end} -
+ * \mathrm{begin}} @f$ elements. Otherwise, the ratio between the
+ * longest and the shortest part is bounded by @f$
+ * 1/(\mathrm{oversampling} \cdot \mathrm{num\_parts}) @f$.
+ * @return Length of the whole sequence.
+ */
+template<typename InputIterator, typename FunctorType>
size_t
list_partition(const InputIterator begin, const InputIterator end,
- InputIterator* starts, size_t* lengths, const int num_parts,
- FunctorType& f, int oversampling = 0)
+ InputIterator* starts, size_t* lengths, const int num_parts,
+ FunctorType& f, int oversampling = 0)
{
bool make_twice = false;
// According to the oversampling factor, the resizing algorithm is chosen.
if (oversampling == 0)
{
- make_twice = true;
- oversampling = 1;
+ make_twice = true;
+ oversampling = 1;
}
std::vector<InputIterator> os_starts(2 * oversampling * num_parts + 1);
@@ -128,19 +130,21 @@
while (it != end){
cur = next;
for (; cur < os_starts.size() and it != end; ++cur)
- {
- for (dist_limit += range_length; dist < dist_limit and it != end; ++dist)
- {
- f(it);
- ++it;
- }
- os_starts[cur] = it;
- }
+ {
+ for (dist_limit += range_length;
+ dist < dist_limit and it != end;
+ ++dist)
+ {
+ f(it);
+ ++it;
+ }
+ os_starts[cur] = it;
+ }
// Must compare for end and not cur < os_starts.size() , because
// cur could be == os_starts.size() as well
if (it == end)
- break;
+ break;
shrink_and_double(os_starts, count_to_two, range_length, make_twice);
next = os_starts.size()/2 + 1;
@@ -158,17 +162,17 @@
// Smallest partitions.
for (int i = 1; i < (num_parts + 1 - size_greater); ++i)
{
- lengths[i-1] = size_part * range_length;
- index += size_part;
- starts[i] = os_starts[index];
+ lengths[i-1] = size_part * range_length;
+ index += size_part;
+ starts[i] = os_starts[index];
}
// Biggest partitions.
for (int i = num_parts + 1 - size_greater; i <= num_parts; ++i)
{
- lengths[i-1] = (size_part+1) * range_length;
- index += (size_part+1);
- starts[i] = os_starts[index];
+ lengths[i-1] = (size_part+1) * range_length;
+ index += (size_part+1);
+ starts[i] = os_starts[index];
}
// Correction of the end size (the end iteration has not finished).
Index: include/parallel/for_each.h
===================================================================
--- include/parallel/for_each.h (revision 130490)
+++ include/parallel/for_each.h (working copy)
@@ -61,22 +61,31 @@
* @param output Output iterator.
* @param bound Maximum number of elements processed.
* @param parallelism_tag Parallelization method */
- template<typename InputIterator, typename UserOp, typename Functionality, typename Red, typename Result>
+
+template<typename InputIterator, typename UserOp, typename Functionality,
+ typename Red, typename Result>
UserOp
for_each_template_random_access(InputIterator begin, InputIterator end,
- UserOp user_op, Functionality& functionality,
- Red reduction, Result reduction_start,
- Result& output,
- typename std::iterator_traits<InputIterator>::difference_type bound, parallelism parallelism_tag)
+ UserOp user_op, Functionality& functionality,
+ Red reduction, Result reduction_start,
+ Result& output,
+ typename std::iterator_traits
+ <InputIterator>
+ ::difference_type bound,
+ parallelism parallelism_tag)
{
if (parallelism_tag == parallel_unbalanced)
- return for_each_template_random_access_ed(begin, end, user_op, functionality, reduction, reduction_start, output, bound);
+ return for_each_template_random_access_ed(begin, end, user_op,
+ functionality, reduction, reduction_start, output, bound);
else if (parallelism_tag == parallel_omp_loop)
- return for_each_template_random_access_omp_loop(begin, end, user_op, functionality, reduction, reduction_start, output, bound);
+ return for_each_template_random_access_omp_loop(begin, end, user_op,
+ functionality, reduction, reduction_start, output, bound);
else if (parallelism_tag == parallel_omp_loop_static)
- return for_each_template_random_access_omp_loop(begin, end, user_op, functionality, reduction, reduction_start, output, bound);
- else //e. g. parallel_balanced
- return for_each_template_random_access_workstealing(begin, end, user_op, functionality, reduction, reduction_start, output, bound);
+ return for_each_template_random_access_omp_loop(begin, end, user_op,
+ functionality, reduction, reduction_start, output, bound);
+ else //e. g. parallel_balanced
+ return for_each_template_random_access_workstealing(begin, end, user_op,
+ functionality, reduction, reduction_start, output, bound);
}
}
Index: include/parallel/multiseq_selection.h
===================================================================
--- include/parallel/multiseq_selection.h (revision 130490)
+++ include/parallel/multiseq_selection.h (working copy)
@@ -56,9 +56,10 @@
namespace __gnu_parallel
{
- /** @brief Compare a pair of types lexicographically, ascending. */
- template<typename T1, typename T2, typename Comparator>
- class lexicographic : public std::binary_function<std::pair<T1, T2>, std::pair<T1, T2>, bool>
+/** @brief Compare a pair of types lexicographically, ascending. */
+template<typename T1, typename T2, typename Comparator>
+ class lexicographic : public std::binary_function<std::pair<T1, T2>,
+ std::pair<T1, T2>, bool>
{
private:
Comparator& comp;
@@ -71,18 +72,18 @@
operator()(const std::pair<T1, T2>& p1, const std::pair<T1, T2>& p2) const
{
if (comp(p1.first, p2.first))
- return true;
+ return true;
if (comp(p2.first, p1.first))
- return false;
+ return false;
// Firsts are equal.
return p1.second < p2.second;
}
};
- /** @brief Compare a pair of types lexicographically, descending. */
- template<typename T1, typename T2, typename Comparator>
+/** @brief Compare a pair of types lexicographically, descending. */
+template<typename T1, typename T2, typename Comparator>
class lexicographic_reverse : public std::binary_function<T1, T2, bool>
{
private:
@@ -95,38 +96,41 @@
operator()(const std::pair<T1, T2>& p1, const std::pair<T1, T2>& p2) const
{
if (comp(p2.first, p1.first))
- return true;
+ return true;
if (comp(p1.first, p2.first))
- return false;
+ return false;
// Firsts are equal.
return p2.second < p1.second;
}
};
- /**
- * @brief Splits several sorted sequences at a certain global rank,
- * resulting in a splitting point for each sequence.
- * The sequences are passed via a sequence of random-access
- * iterator pairs, none of the sequences may be empty. If there
- * are several equal elements across the split, the ones on the
- * left side will be chosen from sequences with smaller number.
- * @param begin_seqs Begin of the sequence of iterator pairs.
- * @param end_seqs End of the sequence of iterator pairs.
- * @param rank The global rank to partition at.
- * @param begin_offsets A random-access sequence begin where the
- * result will be stored in. Each element of the sequence is an
- * iterator that points to the first element on the greater part of
- * the respective sequence.
- * @param comp The ordering functor, defaults to std::less<T>.
- */
- template<typename RanSeqs, typename RankType, typename RankIterator, typename Comparator>
+/**
+ * @brief Splits several sorted sequences at a certain global rank,
+ * resulting in a splitting point for each sequence.
+ * The sequences are passed via a sequence of random-access
+ * iterator pairs, none of the sequences may be empty. If there
+ * are several equal elements across the split, the ones on the
+ * left side will be chosen from sequences with smaller number.
+ * @param begin_seqs Begin of the sequence of iterator pairs.
+ * @param end_seqs End of the sequence of iterator pairs.
+ * @param rank The global rank to partition at.
+ * @param begin_offsets A random-access sequence begin where the
+ * result will be stored in. Each element of the sequence is an
+ * iterator that points to the first element on the greater part of
+ * the respective sequence.
+ * @param comp The ordering functor, defaults to std::less<T>.
+ */
+template<typename RanSeqs, typename RankType, typename RankIterator,
+ typename Comparator>
void
multiseq_partition(RanSeqs begin_seqs, RanSeqs end_seqs, RankType rank,
- RankIterator begin_offsets,
- Comparator comp = std::less<
- typename std::iterator_traits<typename std::iterator_traits<RanSeqs>::value_type::first_type>::value_type>()) // std::less<T>
+ RankIterator begin_offsets,
+ Comparator comp = std::less<
+ typename std::iterator_traits
+ <typename std::iterator_traits<RanSeqs>
+ ::value_type::first_type>::value_type>())
{
_GLIBCXX_CALL(end_seqs - begin_seqs)
@@ -146,9 +150,9 @@
if (rank == N)
{
- for (int i = 0; i < m; i++)
- begin_offsets[i] = begin_seqs[i].second; // Very end.
- // Return m - 1;
+ for (int i = 0; i < m; i++)
+ begin_offsets[i] = begin_seqs[i].second; // Very end.
+ // Return m - 1;
}
_GLIBCXX_PARALLEL_ASSERT(m != 0 && N != 0 && rank >= 0 && rank < N);
@@ -162,8 +166,8 @@
nmax = ns[0];
for (int i = 0; i < m; i++)
{
- ns[i] = std::distance(begin_seqs[i].first, begin_seqs[i].second);
- nmax = std::max(nmax, ns[i]);
+ ns[i] = std::distance(begin_seqs[i].first, begin_seqs[i].second);
+ nmax = std::max(nmax, ns[i]);
}
r = log2(nmax) + 1;
@@ -177,8 +181,8 @@
for (int i = 0; i < m; i++)
{
- a[i] = 0;
- b[i] = l;
+ a[i] = 0;
+ b[i] = l;
}
n = l / 2;
@@ -191,13 +195,13 @@
std::vector<std::pair<value_type, int> > sample;
for (int i = 0; i < m; i++)
- if (n < ns[i]) //sequence long enough
- sample.push_back(std::make_pair(S(i)[n], i));
+ if (n < ns[i]) //sequence long enough
+ sample.push_back(std::make_pair(S(i)[n], i));
__gnu_sequential::sort(sample.begin(), sample.end(), lcomp);
- for (int i = 0; i < m; i++) //conceptual infinity
- if (n >= ns[i]) //sequence too short, conceptual infinity
- sample.push_back(std::make_pair(S(i)[0] /*dummy element*/, i));
+ for (int i = 0; i < m; i++) //conceptual infinity
+ if (n >= ns[i]) //sequence too short, conceptual infinity
+ sample.push_back(std::make_pair(S(i)[0] /*dummy element*/, i));
difference_type localrank = rank * m / N ;
@@ -210,93 +214,103 @@
// Further refinement.
while (n > 0)
{
- n /= 2;
+ n /= 2;
- int lmax_seq = -1; // to avoid warning
- const value_type* lmax = NULL; // impossible to avoid the warning?
- for (int i = 0; i < m; i++)
- {
- if (a[i] > 0)
- {
- if (!lmax)
- {
- lmax = &(S(i)[a[i] - 1]);
- lmax_seq = i;
- }
- else
- {
- // Max, favor rear sequences.
- if (!comp(S(i)[a[i] - 1], *lmax))
- {
- lmax = &(S(i)[a[i] - 1]);
- lmax_seq = i;
- }
- }
- }
- }
+ int lmax_seq = -1; // to avoid warning
+ const value_type* lmax = NULL; // impossible to avoid the warning?
+ for (int i = 0; i < m; i++)
+ {
+ if (a[i] > 0)
+ {
+ if (!lmax)
+ {
+ lmax = &(S(i)[a[i] - 1]);
+ lmax_seq = i;
+ }
+ else
+ {
+ // Max, favor rear sequences.
+ if (!comp(S(i)[a[i] - 1], *lmax))
+ {
+ lmax = &(S(i)[a[i] - 1]);
+ lmax_seq = i;
+ }
+ }
+ }
+ }
- int i;
- for (i = 0; i < m; i++)
- {
- difference_type middle = (b[i] + a[i]) / 2;
- if (lmax && middle < ns[i] &&
- lcomp(std::make_pair(S(i)[middle], i), std::make_pair(*lmax, lmax_seq)))
- a[i] = std::min(a[i] + n + 1, ns[i]);
- else
- b[i] -= n + 1;
- }
+ int i;
+ for (i = 0; i < m; i++)
+ {
+ difference_type middle = (b[i] + a[i]) / 2;
+ if (lmax && middle < ns[i] &&
+ lcomp(std::make_pair(S(i)[middle], i),
+ std::make_pair(*lmax, lmax_seq)))
+ a[i] = std::min(a[i] + n + 1, ns[i]);
+ else
+ b[i] -= n + 1;
+ }
- difference_type leftsize = 0, total = 0;
- for (int i = 0; i < m; i++)
- {
- leftsize += a[i] / (n + 1);
- total += l / (n + 1);
- }
+ difference_type leftsize = 0, total = 0;
+ for (int i = 0; i < m; i++)
+ {
+ leftsize += a[i] / (n + 1);
+ total += l / (n + 1);
+ }
- difference_type skew = static_cast<difference_type>(static_cast<uint64>(total) * rank / N - leftsize);
+ difference_type skew = static_cast<difference_type>
+ (static_cast<uint64>(total) * rank / N - leftsize);
+ // Use integer of maximum size available.
- if (skew > 0)
- {
- // Move to the left, find smallest.
- std::priority_queue<std::pair<value_type, int>, std::vector<std::pair<value_type, int> >, lexicographic_reverse<value_type, int, Comparator> > pq(lrcomp);
+ if (skew > 0)
+ {
+ // Move to the left, find smallest.
+ std::priority_queue<
+ std::pair<value_type, int>,
+ std::vector<std::pair<value_type, int> >,
+ lexicographic_reverse<value_type, int, Comparator> >
+ pq(lrcomp);
- for (int i = 0; i < m; i++)
- if (b[i] < ns[i])
- pq.push(std::make_pair(S(i)[b[i]], i));
+ for (int i = 0; i < m; i++)
+ if (b[i] < ns[i])
+ pq.push(std::make_pair(S(i)[b[i]], i));
- for (; skew != 0 && !pq.empty(); skew--)
- {
- int source = pq.top().second;
- pq.pop();
+ for (; skew != 0 && !pq.empty(); skew--)
+ {
+ int source = pq.top().second;
+ pq.pop();
- a[source] = std::min(a[source] + n + 1, ns[source]);
- b[source] += n + 1;
+ a[source] = std::min(a[source] + n + 1, ns[source]);
+ b[source] += n + 1;
- if (b[source] < ns[source])
- pq.push(std::make_pair(S(source)[b[source]], source));
- }
- }
- else if (skew < 0)
- {
- // Move to the right, find greatest.
- std::priority_queue<std::pair<value_type, int>, std::vector<std::pair<value_type, int> >, lexicographic<value_type, int, Comparator> > pq(lcomp);
+ if (b[source] < ns[source])
+ pq.push(std::make_pair(S(source)[b[source]], source));
+ }
+ }
+ else if (skew < 0)
+ {
+ // Move to the right, find greatest.
+ std::priority_queue<
+ std::pair<value_type, int>,
+ std::vector<std::pair<value_type, int> >,
+ lexicographic<value_type, int, Comparator> > pq(lcomp);
- for (int i = 0; i < m; i++)
- if (a[i] > 0)
- pq.push(std::make_pair(S(i)[a[i] - 1], i));
+ for (int i = 0; i < m; i++)
+ if (a[i] > 0)
+ pq.push(std::make_pair(S(i)[a[i] - 1], i));
- for (; skew != 0; skew++)
- {
- int source = pq.top().second;
- pq.pop();
+ for (; skew != 0; skew++)
+ {
+ int source = pq.top().second;
+ pq.pop();
- a[source] -= n + 1;
- b[source] -= n + 1;
+ a[source] -= n + 1;
+ b[source] -= n + 1;
- if (a[source] > 0)
- pq.push(std::make_pair(S(source)[a[source] - 1], source));
- }
- }
+ if (a[source] > 0)
+ pq.push(std::make_pair(S(source)[a[source] - 1], source));
+ }
+ }
}
// Postconditions:
@@ -312,28 +326,28 @@
value_type* minright = NULL;
for (int i = 0; i < m; i++)
{
- if (a[i] > 0)
- {
- if (!maxleft)
- maxleft = &(S(i)[a[i] - 1]);
- else
- {
- // Max, favor rear sequences.
- if (!comp(S(i)[a[i] - 1], *maxleft))
- maxleft = &(S(i)[a[i] - 1]);
- }
- }
- if (b[i] < ns[i])
- {
- if (!minright)
- minright = &(S(i)[b[i]]);
- else
- {
- // Min, favor fore sequences.
- if (comp(S(i)[b[i]], *minright))
- minright = &(S(i)[b[i]]);
- }
- }
+ if (a[i] > 0)
+ {
+ if (!maxleft)
+ maxleft = &(S(i)[a[i] - 1]);
+ else
+ {
+ // Max, favor rear sequences.
+ if (!comp(S(i)[a[i] - 1], *maxleft))
+ maxleft = &(S(i)[a[i] - 1]);
+ }
+ }
+ if (b[i] < ns[i])
+ {
+ if (!minright)
+ minright = &(S(i)[b[i]]);
+ else
+ {
+ // Min, favor fore sequences.
+ if (comp(S(i)[b[i]], *minright))
+ minright = &(S(i)[b[i]]);
+ }
+ }
}
int seq = 0;
@@ -346,24 +360,25 @@
}
- /**
- * @brief Selects the element at a certain global rank from several
- * sorted sequences.
- *
- * The sequences are passed via a sequence of random-access
- * iterator pairs, none of the sequences may be empty.
- * @param begin_seqs Begin of the sequence of iterator pairs.
- * @param end_seqs End of the sequence of iterator pairs.
- * @param rank The global rank to partition at.
- * @param offset The rank of the selected element in the global
- * subsequence of elements equal to the selected element. If the
- * selected element is unique, this number is 0.
- * @param comp The ordering functor, defaults to std::less.
- */
- template<typename T, typename RanSeqs, typename RankType, typename Comparator>
+/**
+ * @brief Selects the element at a certain global rank from several
+ * sorted sequences.
+ *
+ * The sequences are passed via a sequence of random-access
+ * iterator pairs, none of the sequences may be empty.
+ * @param begin_seqs Begin of the sequence of iterator pairs.
+ * @param end_seqs End of the sequence of iterator pairs.
+ * @param rank The global rank to partition at.
+ * @param offset The rank of the selected element in the global
+ * subsequence of elements equal to the selected element. If the
+ * selected element is unique, this number is 0.
+ * @param comp The ordering functor, defaults to std::less.
+ */
+template<typename T, typename RanSeqs, typename RankType,
+ typename Comparator>
T
multiseq_selection(RanSeqs begin_seqs, RanSeqs end_seqs, RankType rank,
- RankType& offset, Comparator comp = std::less<T>())
+ RankType& offset, Comparator comp = std::less<T>())
{
_GLIBCXX_CALL(end_seqs - begin_seqs)
@@ -384,8 +399,8 @@
if (m == 0 || N == 0 || rank < 0 || rank >= N)
{
- // Result undefined when there is no data or rank is outside bounds.
- throw std::exception();
+ // Result undefined when there is no data or rank is outside bounds.
+ throw std::exception();
}
@@ -398,8 +413,8 @@
nmax = ns[0];
for (int i = 0; i < m; i++)
{
- ns[i] = std::distance(begin_seqs[i].first, begin_seqs[i].second);
- nmax = std::max(nmax, ns[i]);
+ ns[i] = std::distance(begin_seqs[i].first, begin_seqs[i].second);
+ nmax = std::max(nmax, ns[i]);
}
r = log2(nmax) + 1;
@@ -413,8 +428,8 @@
for (int i = 0; i < m; i++)
{
- a[i] = 0;
- b[i] = l;
+ a[i] = 0;
+ b[i] = l;
}
n = l / 2;
@@ -428,13 +443,14 @@
for (int i = 0; i < m; i++)
if (n < ns[i])
- sample.push_back(std::make_pair(S(i)[n], i));
- __gnu_sequential::sort(sample.begin(), sample.end(), lcomp, sequential_tag());
+ sample.push_back(std::make_pair(S(i)[n], i));
+ __gnu_sequential::sort(sample.begin(), sample.end(), lcomp,
+ sequential_tag());
// Conceptual infinity.
for (int i = 0; i < m; i++)
if (n >= ns[i])
- sample.push_back(std::make_pair(S(i)[0] /*dummy element*/, i));
+ sample.push_back(std::make_pair(S(i)[0] /*dummy element*/, i));
difference_type localrank = rank * m / N ;
@@ -447,86 +463,92 @@
// Further refinement.
while (n > 0)
{
- n /= 2;
+ n /= 2;
- const T* lmax = NULL;
- for (int i = 0; i < m; i++)
- {
- if (a[i] > 0)
- {
- if (!lmax)
- {
- lmax = &(S(i)[a[i] - 1]);
- }
- else
- {
- if (comp(*lmax, S(i)[a[i] - 1])) //max
- lmax = &(S(i)[a[i] - 1]);
- }
- }
- }
+ const T* lmax = NULL;
+ for (int i = 0; i < m; i++)
+ {
+ if (a[i] > 0)
+ {
+ if (!lmax)
+ {
+ lmax = &(S(i)[a[i] - 1]);
+ }
+ else
+ {
+ if (comp(*lmax, S(i)[a[i] - 1])) //max
+ lmax = &(S(i)[a[i] - 1]);
+ }
+ }
+ }
- int i;
- for (i = 0; i < m; i++)
- {
- difference_type middle = (b[i] + a[i]) / 2;
- if (lmax && middle < ns[i] && comp(S(i)[middle], *lmax))
- a[i] = std::min(a[i] + n + 1, ns[i]);
- else
- b[i] -= n + 1;
- }
+ int i;
+ for (i = 0; i < m; i++)
+ {
+ difference_type middle = (b[i] + a[i]) / 2;
+ if (lmax && middle < ns[i] && comp(S(i)[middle], *lmax))
+ a[i] = std::min(a[i] + n + 1, ns[i]);
+ else
+ b[i] -= n + 1;
+ }
- difference_type leftsize = 0, total = 0;
- for (int i = 0; i < m; i++)
- {
- leftsize += a[i] / (n + 1);
- total += l / (n + 1);
- }
+ difference_type leftsize = 0, total = 0;
+ for (int i = 0; i < m; i++)
+ {
+ leftsize += a[i] / (n + 1);
+ total += l / (n + 1);
+ }
- difference_type skew = (unsigned long long)total * rank / N - leftsize;
+ difference_type skew = (unsigned long long)total * rank / N - leftsize;
- if (skew > 0)
- {
- // Move to the left, find smallest.
- std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int> >, lexicographic_reverse<T, int, Comparator> > pq(lrcomp);
+ if (skew > 0)
+ {
+ // Move to the left, find smallest.
+ std::priority_queue<
+ std::pair<T, int>,
+ std::vector<std::pair<T, int> >,
+ lexicographic_reverse<T, int, Comparator> > pq(lrcomp);
- for (int i = 0; i < m; i++)
- if (b[i] < ns[i])
- pq.push(std::make_pair(S(i)[b[i]], i));
+ for (int i = 0; i < m; i++)
+ if (b[i] < ns[i])
+ pq.push(std::make_pair(S(i)[b[i]], i));
- for (; skew != 0 && !pq.empty(); skew--)
- {
- int source = pq.top().second;
- pq.pop();
+ for (; skew != 0 && !pq.empty(); skew--)
+ {
+ int source = pq.top().second;
+ pq.pop();
- a[source] = std::min(a[source] + n + 1, ns[source]);
- b[source] += n + 1;
+ a[source] = std::min(a[source] + n + 1, ns[source]);
+ b[source] += n + 1;
- if (b[source] < ns[source])
- pq.push(std::make_pair(S(source)[b[source]], source));
- }
- }
- else if (skew < 0)
- {
- // Move to the right, find greatest.
- std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int> >, lexicographic<T, int, Comparator> > pq(lcomp);
+ if (b[source] < ns[source])
+ pq.push(std::make_pair(S(source)[b[source]], source));
+ }
+ }
+ else if (skew < 0)
+ {
+ // Move to the right, find greatest.
+ std::priority_queue<
+ std::pair<T, int>,
+ std::vector<std::pair<T, int> >,
+ lexicographic<T, int, Comparator> > pq(lcomp);
- for (int i = 0; i < m; i++)
- if (a[i] > 0)
- pq.push(std::make_pair(S(i)[a[i] - 1], i));
+ for (int i = 0; i < m; i++)
+ if (a[i] > 0)
+ pq.push(std::make_pair(S(i)[a[i] - 1], i));
- for (; skew != 0; skew++)
- {
- int source = pq.top().second;
- pq.pop();
+ for (; skew != 0; skew++)
+ {
+ int source = pq.top().second;
+ pq.pop();
- a[source] -= n + 1;
- b[source] -= n + 1;
+ a[source] -= n + 1;
+ b[source] -= n + 1;
- if (a[source] > 0)
- pq.push(std::make_pair(S(source)[a[source] - 1], source));
- }
- }
+ if (a[source] > 0)
+ pq.push(std::make_pair(S(source)[a[source] - 1], source));
+ }
+ }
}
// Postconditions:
@@ -544,54 +566,54 @@
T maxleft, minright;
for (int i = 0; i < m; i++)
{
- if (a[i] > 0)
- {
- if (!maxleftset)
- {
- maxleft = S(i)[a[i] - 1];
- maxleftset = true;
- }
- else
- {
- // Max.
- if (comp(maxleft, S(i)[a[i] - 1]))
- maxleft = S(i)[a[i] - 1];
- }
- }
- if (b[i] < ns[i])
- {
- if (!minrightset)
- {
- minright = S(i)[b[i]];
- minrightset = true;
- }
- else
- {
- // Min.
- if (comp(S(i)[b[i]], minright))
- minright = S(i)[b[i]];
- }
- }
+ if (a[i] > 0)
+ {
+ if (!maxleftset)
+ {
+ maxleft = S(i)[a[i] - 1];
+ maxleftset = true;
+ }
+ else
+ {
+ // Max.
+ if (comp(maxleft, S(i)[a[i] - 1]))
+ maxleft = S(i)[a[i] - 1];
+ }
+ }
+ if (b[i] < ns[i])
+ {
+ if (!minrightset)
+ {
+ minright = S(i)[b[i]];
+ minrightset = true;
+ }
+ else
+ {
+ // Min.
+ if (comp(S(i)[b[i]], minright))
+ minright = S(i)[b[i]];
+ }
+ }
}
// Minright is the splitter, in any case.
if (!maxleftset || comp(minright, maxleft))
{
- // Good luck, everything is split unambigiously.
- offset = 0;
+ // Good luck, everything is split unambigiously.
+ offset = 0;
}
else
{
- // We have to calculate an offset.
- offset = 0;
+ // We have to calculate an offset.
+ offset = 0;
- for (int i = 0; i < m; i++)
- {
- difference_type lb = std::lower_bound(S(i), S(i) + ns[i], minright,
- comp) - S(i);
- offset += a[i] - lb;
- }
+ for (int i = 0; i < m; i++)
+ {
+ difference_type lb = std::lower_bound(S(i), S(i) + ns[i], minright,
+ comp) - S(i);
+ offset += a[i] - lb;
+ }
}
delete[] ns;
Index: include/parallel/algorithmfwd.h
===================================================================
--- include/parallel/algorithmfwd.h (revision 130490)
+++ include/parallel/algorithmfwd.h (working copy)
@@ -44,749 +44,837 @@
{
namespace __parallel
{
- template<typename _FIter>
+template<typename _FIter>
_FIter
adjacent_find(_FIter, _FIter);
- template<typename _FIter>
+template<typename _FIter>
_FIter
adjacent_find(_FIter, _FIter, __gnu_parallel::sequential_tag);
- template<typename _FIter, typename _IterTag>
+template<typename _FIter, typename _IterTag>
_FIter
adjacent_find_switch(_FIter, _FIter, _IterTag);
- template<typename _RAIter>
+template<typename _RAIter>
_RAIter
adjacent_find_switch(_RAIter, _RAIter, random_access_iterator_tag);
- template<typename _FIter, typename _BiPredicate>
+template<typename _FIter, typename _BiPredicate>
_FIter
adjacent_find(_FIter, _FIter, _BiPredicate);
- template<typename _FIter, typename _BiPredicate>
+template<typename _FIter, typename _BiPredicate>
_FIter
adjacent_find(_FIter, _FIter, _BiPredicate,
- __gnu_parallel::sequential_tag);
+ __gnu_parallel::sequential_tag);
- template<typename _FIter, typename _BiPredicate, typename _IterTag>
+template<typename _FIter, typename _BiPredicate, typename _IterTag>
_FIter
adjacent_find_switch(_FIter, _FIter, _BiPredicate, _IterTag);
- template<typename _RAIter, typename _BiPredicate>
+template<typename _RAIter, typename _BiPredicate>
_RAIter
adjacent_find_switch(_RAIter, _RAIter, _BiPredicate,
- random_access_iterator_tag);
+ random_access_iterator_tag);
- template<typename _IIter, typename _Tp>
+template<typename _IIter, typename _Tp>
typename iterator_traits<_IIter>::difference_type
count(_IIter, _IIter, const _Tp&);
- template<typename _IIter, typename T>
+template<typename _IIter, typename T>
typename iterator_traits<_IIter>::difference_type
count(_IIter, _IIter, const T&, __gnu_parallel::sequential_tag);
- template<typename _IIter, typename T>
+template<typename _IIter, typename T>
typename iterator_traits<_IIter>::difference_type
count(_IIter, _IIter, const T&, __gnu_parallel::parallelism);
- template<typename _IIter, typename T, typename _IterTag>
+template<typename _IIter, typename T, typename _IterTag>
typename iterator_traits<_IIter>::difference_type
count_switch(_IIter, _IIter, const T&, _IterTag);
- template<typename _RAIter, typename T>
+template<typename _RAIter, typename T>
typename iterator_traits<_RAIter>::difference_type
count_switch(_RAIter, _RAIter, const T&, random_access_iterator_tag,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
- template<typename _IIter, typename Predicate>
+template<typename _IIter, typename Predicate>
typename iterator_traits<_IIter>::difference_type
count_if(_IIter, _IIter, Predicate);
- template<typename _IIter, typename Predicate>
+template<typename _IIter, typename Predicate>
typename iterator_traits<_IIter>::difference_type
count_if(_IIter, _IIter, Predicate, __gnu_parallel::sequential_tag);
- template<typename _IIter, typename Predicate>
+template<typename _IIter, typename Predicate>
typename iterator_traits<_IIter>::difference_type
count_if(_IIter, _IIter, Predicate, __gnu_parallel::parallelism);
- template<typename _IIter, typename Predicate, typename _IterTag>
+template<typename _IIter, typename Predicate, typename _IterTag>
typename iterator_traits<_IIter>::difference_type
count_if_switch(_IIter, _IIter, Predicate, _IterTag);
- template<typename _RAIter, typename Predicate>
+template<typename _RAIter, typename Predicate>
typename iterator_traits<_RAIter>::difference_type
count_if_switch(_RAIter, _RAIter, Predicate, random_access_iterator_tag,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
// algobase.h
- template<typename _IIter1, typename _IIter2>
+template<typename _IIter1, typename _IIter2>
bool
equal(_IIter1, _IIter1, _IIter2, __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename Predicate>
bool
equal(_IIter1, _IIter1, _IIter2, Predicate, __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2>
+template<typename _IIter1, typename _IIter2>
bool
equal(_IIter1, _IIter1, _IIter2);
- template<typename _IIter1, typename _IIter2, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename Predicate>
bool
equal(_IIter1, _IIter1, _IIter2, Predicate);
- template<typename _IIter, typename T>
+template<typename _IIter, typename T>
_IIter
find(_IIter, _IIter, const T&, __gnu_parallel::sequential_tag);
- template<typename _IIter, typename T>
+template<typename _IIter, typename T>
_IIter
find(_IIter, _IIter, const T& val);
- template<typename _IIter, typename T, typename _IterTag>
+template<typename _IIter, typename T, typename _IterTag>
_IIter
find_switch(_IIter, _IIter, const T&, _IterTag);
- template<typename _RAIter, typename T>
+template<typename _RAIter, typename T>
_RAIter
find_switch(_RAIter, _RAIter, const T&, random_access_iterator_tag);
- template<typename _IIter, typename Predicate>
+template<typename _IIter, typename Predicate>
_IIter
find_if(_IIter, _IIter, Predicate, __gnu_parallel::sequential_tag);
- template<typename _IIter, typename Predicate>
+template<typename _IIter, typename Predicate>
_IIter
find_if(_IIter, _IIter, Predicate);
- template<typename _IIter, typename Predicate, typename _IterTag>
+template<typename _IIter, typename Predicate, typename _IterTag>
_IIter
find_if_switch(_IIter, _IIter, Predicate, _IterTag);
- template<typename _RAIter, typename Predicate>
+template<typename _RAIter, typename Predicate>
_RAIter
find_if_switch(_RAIter, _RAIter, Predicate, random_access_iterator_tag);
- template<typename _IIter, typename _FIter>
+template<typename _IIter, typename _FIter>
_IIter
- find_first_of(_IIter, _IIter, _FIter, _FIter, __gnu_parallel::sequential_tag);
+ find_first_of(_IIter, _IIter, _FIter, _FIter,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter, typename _FIter, typename _BiPredicate>
+template<typename _IIter, typename _FIter, typename _BiPredicate>
_IIter
- find_first_of(_IIter, _IIter, _FIter, _FIter, _BiPredicate, __gnu_parallel::sequential_tag);
+ find_first_of(_IIter, _IIter, _FIter, _FIter, _BiPredicate,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter, typename _FIter, typename _BiPredicate>
+template<typename _IIter, typename _FIter, typename _BiPredicate>
_IIter
find_first_of(_IIter, _IIter, _FIter, _FIter, _BiPredicate);
- template<typename _IIter, typename _FIter>
+template<typename _IIter, typename _FIter>
_IIter
find_first_of(_IIter, _IIter, _FIter, _FIter);
- template<typename _IIter, typename _FIter, typename _IterTag1, typename _IterTag2>
+template<typename _IIter, typename _FIter, typename _IterTag1,
+ typename _IterTag2>
_IIter
find_first_of_switch(_IIter, _IIter, _FIter, _FIter, _IterTag1, _IterTag2);
- template<typename _RAIter, typename _FIter, typename _BiPredicate, typename _IterTag>
+template<typename _RAIter, typename _FIter, typename _BiPredicate,
+ typename _IterTag>
_RAIter
- find_first_of_switch(_RAIter, _RAIter, _FIter, _FIter, _BiPredicate, random_access_iterator_tag, _IterTag);
+ find_first_of_switch(_RAIter, _RAIter, _FIter, _FIter, _BiPredicate,
+ random_access_iterator_tag, _IterTag);
- template<typename _IIter, typename _FIter, typename _BiPredicate, typename _IterTag1, typename _IterTag2>
+template<typename _IIter, typename _FIter, typename _BiPredicate,
+ typename _IterTag1, typename _IterTag2>
_IIter
- find_first_of_switch(_IIter, _IIter, _FIter, _FIter, _BiPredicate, _IterTag1, _IterTag2);
+ find_first_of_switch(_IIter, _IIter, _FIter, _FIter, _BiPredicate,
+ _IterTag1, _IterTag2);
- template<typename _IIter, typename Function>
+template<typename _IIter, typename Function>
Function
for_each(_IIter, _IIter, Function);
- template<typename _IIter, typename Function>
+template<typename _IIter, typename Function>
Function
for_each(_IIter, _IIter, Function, __gnu_parallel::sequential_tag);
- template<typename Iterator, typename Function>
+template<typename Iterator, typename Function>
Function
for_each(Iterator, Iterator, Function, __gnu_parallel::parallelism);
- template<typename _IIter, typename Function, typename _IterTag>
+template<typename _IIter, typename Function, typename _IterTag>
Function
for_each_switch(_IIter, _IIter, Function, _IterTag);
- template<typename _RAIter, typename Function>
+template<typename _RAIter, typename Function>
Function
for_each_switch(_RAIter, _RAIter, Function, random_access_iterator_tag,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
- template<typename _FIter, typename Generator>
+template<typename _FIter, typename Generator>
void
generate(_FIter, _FIter, Generator);
- template<typename _FIter, typename Generator>
+template<typename _FIter, typename Generator>
void
generate(_FIter, _FIter, Generator, __gnu_parallel::sequential_tag);
- template<typename _FIter, typename Generator>
+template<typename _FIter, typename Generator>
void
generate(_FIter, _FIter, Generator, __gnu_parallel::parallelism);
- template<typename _FIter, typename Generator, typename _IterTag>
+template<typename _FIter, typename Generator, typename _IterTag>
void
generate_switch(_FIter, _FIter, Generator, _IterTag);
- template<typename _RAIter, typename Generator>
+template<typename _RAIter, typename Generator>
void
generate_switch(_RAIter, _RAIter, Generator, random_access_iterator_tag,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
- template<typename _OIter, typename Size, typename Generator>
+template<typename _OIter, typename Size, typename Generator>
_OIter
generate_n(_OIter, Size, Generator);
- template<typename _OIter, typename Size, typename Generator>
+template<typename _OIter, typename Size, typename Generator>
_OIter
generate_n(_OIter, Size, Generator, __gnu_parallel::sequential_tag);
- template<typename _OIter, typename Size, typename Generator>
+template<typename _OIter, typename Size, typename Generator>
_OIter
generate_n(_OIter, Size, Generator, __gnu_parallel::parallelism);
- template<typename _OIter, typename Size, typename Generator, typename _IterTag>
+template<typename _OIter, typename Size, typename Generator, typename _IterTag>
_OIter
generate_n_switch(_OIter, Size, Generator, _IterTag);
- template<typename _RAIter, typename Size, typename Generator>
+template<typename _RAIter, typename Size, typename Generator>
_RAIter
generate_n_switch(_RAIter, Size, Generator, random_access_iterator_tag,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
- template<typename _IIter1, typename _IIter2>
+template<typename _IIter1, typename _IIter2>
bool
- lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2, __gnu_parallel::sequential_tag);
+ lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename Predicate>
bool
- lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2, Predicate, __gnu_parallel::sequential_tag);
+ lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2, Predicate,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2>
+template<typename _IIter1, typename _IIter2>
bool
lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2);
- template<typename _IIter1, typename _IIter2, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename Predicate>
bool
lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2, Predicate);
- template<typename _IIter1, typename _IIter2, typename Predicate, typename _IterTag1, typename _IterTag2>
+template<typename _IIter1, typename _IIter2, typename Predicate,
+ typename _IterTag1, typename _IterTag2>
bool
- lexicographical_compare_switch(_IIter1, _IIter1, _IIter2, _IIter2, Predicate, _IterTag1, _IterTag2);
+ lexicographical_compare_switch(_IIter1, _IIter1, _IIter2, _IIter2,
+ Predicate, _IterTag1, _IterTag2);
- template<typename _RAIter1, typename _RAIter2, typename Predicate>
+template<typename _RAIter1, typename _RAIter2, typename Predicate>
bool
- lexicographical_compare_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, Predicate, random_access_iterator_tag, random_access_iterator_tag);
+ lexicographical_compare_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2,
+ Predicate, random_access_iterator_tag,
+ random_access_iterator_tag);
// algo.h
- template<typename _IIter1, typename _IIter2>
+template<typename _IIter1, typename _IIter2>
pair<_IIter1, _IIter2>
mismatch(_IIter1, _IIter1, _IIter2, __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename Predicate>
pair<_IIter1, _IIter2>
- mismatch(_IIter1, _IIter1, _IIter2, Predicate, __gnu_parallel::sequential_tag);
+ mismatch(_IIter1, _IIter1, _IIter2, Predicate,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2>
+template<typename _IIter1, typename _IIter2>
pair<_IIter1, _IIter2>
mismatch(_IIter1, _IIter1, _IIter2);
- template<typename _IIter1, typename _IIter2, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename Predicate>
pair<_IIter1, _IIter2>
mismatch(_IIter1, _IIter1, _IIter2, Predicate);
- template<typename _IIter1, typename _IIter2, typename Predicate, typename _IterTag1, typename _IterTag2>
+template<typename _IIter1, typename _IIter2, typename Predicate,
+ typename _IterTag1, typename _IterTag2>
pair<_IIter1, _IIter2>
mismatch_switch(_IIter1, _IIter1, _IIter2, Predicate, _IterTag1, _IterTag2);
- template<typename _RAIter1, typename _RAIter2, typename Predicate>
+template<typename _RAIter1, typename _RAIter2, typename Predicate>
pair<_RAIter1, _RAIter2>
- mismatch_switch(_RAIter1, _RAIter1, _RAIter2, Predicate, random_access_iterator_tag, random_access_iterator_tag);
+ mismatch_switch(_RAIter1, _RAIter1, _RAIter2, Predicate,
+ random_access_iterator_tag, random_access_iterator_tag);
- template<typename _FIter1, typename _FIter2>
+template<typename _FIter1, typename _FIter2>
_FIter1
search(_FIter1, _FIter1, _FIter2, _FIter2, __gnu_parallel::sequential_tag);
- template<typename _FIter1, typename _FIter2>
+template<typename _FIter1, typename _FIter2>
_FIter1
search(_FIter1, _FIter1, _FIter2, _FIter2);
- template<typename _FIter1, typename _FIter2, typename _BiPredicate>
+template<typename _FIter1, typename _FIter2, typename _BiPredicate>
_FIter1
- search(_FIter1, _FIter1, _FIter2, _FIter2, _BiPredicate, __gnu_parallel::sequential_tag);
+ search(_FIter1, _FIter1, _FIter2, _FIter2, _BiPredicate,
+ __gnu_parallel::sequential_tag);
- template<typename _FIter1, typename _FIter2, typename _BiPredicate>
+template<typename _FIter1, typename _FIter2, typename _BiPredicate>
_FIter1
search(_FIter1, _FIter1, _FIter2, _FIter2, _BiPredicate);
- template<typename _RAIter1, typename _RAIter2>
+template<typename _RAIter1, typename _RAIter2>
_RAIter1
- search_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, random_access_iterator_tag, random_access_iterator_tag);
+ search_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2,
+ random_access_iterator_tag, random_access_iterator_tag);
- template<typename _FIter1, typename _FIter2, typename _IterTag1, typename _IterTag2>
+template<typename _FIter1, typename _FIter2, typename _IterTag1,
+ typename _IterTag2>
_FIter1
search_switch(_FIter1, _FIter1, _FIter2, _FIter2, _IterTag1, _IterTag2);
- template<typename _RAIter1, typename _RAIter2, typename _BiPredicate>
+template<typename _RAIter1, typename _RAIter2, typename _BiPredicate>
_RAIter1
- search_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, _BiPredicate , random_access_iterator_tag, random_access_iterator_tag);
+ search_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, _BiPredicate,
+ random_access_iterator_tag, random_access_iterator_tag);
- template<typename _FIter1, typename _FIter2, typename _BiPredicate, typename _IterTag1, typename _IterTag2>
+template<typename _FIter1, typename _FIter2, typename _BiPredicate,
+ typename _IterTag1, typename _IterTag2>
_FIter1
- search_switch(_FIter1, _FIter1, _FIter2, _FIter2, _BiPredicate, _IterTag1, _IterTag2);
+ search_switch(_FIter1, _FIter1, _FIter2, _FIter2, _BiPredicate,
+ _IterTag1, _IterTag2);
- template<typename _FIter, typename Integer, typename T>
+template<typename _FIter, typename Integer, typename T>
_FIter
search_n(_FIter, _FIter, Integer, const T&, __gnu_parallel::sequential_tag);
- template<typename _FIter, typename Integer, typename T, typename _BiPredicate>
+template<typename _FIter, typename Integer, typename T, typename _BiPredicate>
_FIter
- search_n(_FIter, _FIter, Integer, const T&, _BiPredicate, __gnu_parallel::sequential_tag);
-
- template<typename _FIter, typename Integer, typename T>
+ search_n(_FIter, _FIter, Integer, const T&, _BiPredicate,
+ __gnu_parallel::sequential_tag);
+
+template<typename _FIter, typename Integer, typename T>
_FIter
search_n(_FIter, _FIter, Integer, const T& val);
- template<typename _FIter, typename Integer, typename T, typename _BiPredicate>
+template<typename _FIter, typename Integer, typename T, typename _BiPredicate>
_FIter
search_n(_FIter, _FIter, Integer, const T&, _BiPredicate);
- template<typename _RAIter, typename Integer, typename T, typename _BiPredicate>
+template<typename _RAIter, typename Integer, typename T, typename _BiPredicate>
_RAIter
- search_n_switch(_RAIter, _RAIter, Integer, const T&, _BiPredicate, random_access_iterator_tag);
+ search_n_switch(_RAIter, _RAIter, Integer, const T&, _BiPredicate,
+ random_access_iterator_tag);
- template<typename _FIter, typename Integer, typename T, typename _BiPredicate, typename _IterTag>
+template<typename _FIter, typename Integer, typename T, typename _BiPredicate,
+ typename _IterTag>
_FIter
search_n_switch(_FIter, _FIter, Integer, const T&, _BiPredicate, _IterTag);
- template<typename _IIter, typename _OIter, typename UnaryOperation>
+template<typename _IIter, typename _OIter, typename UnaryOperation>
_OIter
transform(_IIter, _IIter, _OIter, UnaryOperation);
- template<typename _IIter, typename _OIter, typename UnaryOperation>
+template<typename _IIter, typename _OIter, typename UnaryOperation>
_OIter
transform(_IIter, _IIter, _OIter, UnaryOperation,
- __gnu_parallel::sequential_tag);
+ __gnu_parallel::sequential_tag);
- template<typename _IIter, typename _OIter, typename UnaryOperation>
+template<typename _IIter, typename _OIter, typename UnaryOperation>
_OIter
transform(_IIter, _IIter, _OIter, UnaryOperation,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
- template<typename _IIter, typename _OIter, typename UnaryOperation, typename _IterTag1, typename _IterTag2>
+template<typename _IIter, typename _OIter, typename UnaryOperation,
+ typename _IterTag1, typename _IterTag2>
_OIter
transform1_switch(_IIter, _IIter, _OIter, UnaryOperation,
- _IterTag1, _IterTag2);
+ _IterTag1, _IterTag2);
- template<typename _RAIIter, typename _RAOIter, typename UnaryOperation>
+template<typename _RAIIter, typename _RAOIter, typename UnaryOperation>
_RAOIter
transform1_switch(_RAIIter, _RAIIter, _RAOIter, UnaryOperation,
- random_access_iterator_tag, random_access_iterator_tag,
- __gnu_parallel::parallelism);
+ random_access_iterator_tag, random_access_iterator_tag,
+ __gnu_parallel::parallelism);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _BiOperation>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _BiOperation>
_OIter
transform(_IIter1, _IIter1, _IIter2, _OIter, _BiOperation);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _BiOperation>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _BiOperation>
_OIter
transform(_IIter1, _IIter1, _IIter2, _OIter, _BiOperation,
- __gnu_parallel::sequential_tag);
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _BiOperation>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _BiOperation>
_OIter
transform(_IIter1, _IIter1, _IIter2, _OIter, _BiOperation,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
- template<typename _RAIter1, typename _RAIter2, typename _RAIter3, typename _BiOperation>
+template<typename _RAIter1, typename _RAIter2, typename _RAIter3,
+ typename _BiOperation>
_RAIter3
transform2_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter3, _BiOperation,
- random_access_iterator_tag, random_access_iterator_tag,
- random_access_iterator_tag,
- __gnu_parallel::parallelism parallelism_tag);
+ random_access_iterator_tag, random_access_iterator_tag,
+ random_access_iterator_tag,
+ __gnu_parallel::parallelism parallelism_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _BiOperation, typename tag1, typename tag2, typename tag3>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _BiOperation, typename tag1, typename tag2, typename tag3>
_OIter
transform2_switch(_IIter1, _IIter1, _IIter2, _OIter, _BiOperation,
- tag1, tag2, tag3);
+ tag1, tag2, tag3);
- template<typename _FIter, typename T>
+template<typename _FIter, typename T>
void
replace(_FIter, _FIter, const T&, const T&);
- template<typename _FIter, typename T>
+template<typename _FIter, typename T>
void
replace(_FIter, _FIter, const T&, const T&,
- __gnu_parallel::sequential_tag);
+ __gnu_parallel::sequential_tag);
- template<typename _FIter, typename T>
+template<typename _FIter, typename T>
void
replace(_FIter, _FIter, const T&, const T&, __gnu_parallel::parallelism);
- template<typename _FIter, typename T, typename _IterTag>
+template<typename _FIter, typename T, typename _IterTag>
void
replace_switch(_FIter, _FIter, const T&, const T&, _IterTag);
- template<typename _RAIter, typename T>
+template<typename _RAIter, typename T>
void
replace_switch(_RAIter, _RAIter, const T&, const T&,
- random_access_iterator_tag, __gnu_parallel::parallelism);
+ random_access_iterator_tag, __gnu_parallel::parallelism);
- template<typename _FIter, typename Predicate, typename T>
+template<typename _FIter, typename Predicate, typename T>
void
replace_if(_FIter, _FIter, Predicate, const T&);
- template<typename _FIter, typename Predicate, typename T>
+template<typename _FIter, typename Predicate, typename T>
void
replace_if(_FIter, _FIter, Predicate, const T&,
- __gnu_parallel::sequential_tag);
+ __gnu_parallel::sequential_tag);
- template<typename _FIter, typename Predicate, typename T>
+template<typename _FIter, typename Predicate, typename T>
void
replace_if(_FIter, _FIter, Predicate, const T&,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
- template<typename _FIter, typename Predicate, typename T, typename _IterTag>
+template<typename _FIter, typename Predicate, typename T, typename _IterTag>
void
replace_if_switch(_FIter, _FIter, Predicate, const T&, _IterTag);
- template<typename _RAIter, typename Predicate, typename T>
+template<typename _RAIter, typename Predicate, typename T>
void
replace_if_switch(_RAIter, _RAIter, Predicate, const T&,
- random_access_iterator_tag, __gnu_parallel::parallelism);
+ random_access_iterator_tag, __gnu_parallel::parallelism);
- template<typename _FIter>
+template<typename _FIter>
_FIter
max_element(_FIter, _FIter);
- template<typename _FIter>
+template<typename _FIter>
_FIter
max_element(_FIter, _FIter, __gnu_parallel::sequential_tag);
- template<typename _FIter>
+template<typename _FIter>
_FIter
max_element(_FIter, _FIter, __gnu_parallel::parallelism parallelism_tag);
- template<typename _FIter, typename _Compare>
+template<typename _FIter, typename _Compare>
_FIter
max_element(_FIter, _FIter, _Compare);
- template<typename _FIter, typename _Compare>
+template<typename _FIter, typename _Compare>
_FIter
max_element(_FIter, _FIter, _Compare, __gnu_parallel::sequential_tag);
- template<typename _FIter, typename _Compare>
+template<typename _FIter, typename _Compare>
_FIter
max_element(_FIter, _FIter, _Compare, __gnu_parallel::parallelism);
- template<typename _FIter, typename _Compare, typename _IterTag>
+template<typename _FIter, typename _Compare, typename _IterTag>
_FIter
max_element_switch(_FIter, _FIter, _Compare, _IterTag);
- template<typename _RAIter, typename _Compare>
+template<typename _RAIter, typename _Compare>
_RAIter
max_element_switch(_RAIter, _RAIter, _Compare, random_access_iterator_tag,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
- template<typename _IIter1, typename _IIter2, typename _OIter>
+template<typename _IIter1, typename _IIter2, typename _OIter>
_OIter
merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
- __gnu_parallel::sequential_tag);
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _Compare>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Compare>
_OIter
merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare,
- __gnu_parallel::sequential_tag);
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _Compare>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Compare>
_OIter
merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare);
- template<typename _IIter1, typename _IIter2, typename _OIter>
+template<typename _IIter1, typename _IIter2, typename _OIter>
_OIter
merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _Compare, typename _IterTag1, typename _IterTag2, typename _IterTag3>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Compare,
+ typename _IterTag1, typename _IterTag2, typename _IterTag3>
_OIter
merge_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare,
- _IterTag1, _IterTag2, _IterTag3);
+ _IterTag1, _IterTag2, _IterTag3);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _Compare>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Compare>
_OIter
merge_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare,
- random_access_iterator_tag, random_access_iterator_tag,
- random_access_iterator_tag);
+ random_access_iterator_tag, random_access_iterator_tag,
+ random_access_iterator_tag);
- template<typename _FIter>
+template<typename _FIter>
_FIter
min_element(_FIter, _FIter);
- template<typename _FIter>
+template<typename _FIter>
_FIter
min_element(_FIter, _FIter, __gnu_parallel::sequential_tag);
- template<typename _FIter>
+template<typename _FIter>
_FIter
min_element(_FIter, _FIter, __gnu_parallel::parallelism parallelism_tag);
- template<typename _FIter, typename _Compare>
+template<typename _FIter, typename _Compare>
_FIter
min_element(_FIter, _FIter, _Compare);
- template<typename _FIter, typename _Compare>
+template<typename _FIter, typename _Compare>
_FIter
min_element(_FIter, _FIter, _Compare, __gnu_parallel::sequential_tag);
- template<typename _FIter, typename _Compare>
+template<typename _FIter, typename _Compare>
_FIter
min_element(_FIter, _FIter, _Compare, __gnu_parallel::parallelism);
- template<typename _FIter, typename _Compare, typename _IterTag>
+template<typename _FIter, typename _Compare, typename _IterTag>
_FIter
min_element_switch(_FIter, _FIter, _Compare, _IterTag);
- template<typename _RAIter, typename _Compare>
+template<typename _RAIter, typename _Compare>
_RAIter
min_element_switch(_RAIter, _RAIter, _Compare, random_access_iterator_tag,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
- template<typename _RAIter>
+template<typename _RAIter>
void
nth_element(_RAIter, _RAIter, _RAIter, __gnu_parallel::sequential_tag);
- template<typename _RAIter, typename _Compare>
+template<typename _RAIter, typename _Compare>
void
- nth_element(_RAIter, _RAIter, _RAIter, _Compare, __gnu_parallel::sequential_tag);
+ nth_element(_RAIter, _RAIter, _RAIter, _Compare,
+ __gnu_parallel::sequential_tag);
- template<typename _RAIter, typename _Compare>
+template<typename _RAIter, typename _Compare>
void
nth_element(_RAIter, _RAIter, _RAIter, _Compare);
- template<typename _RAIter>
+template<typename _RAIter>
void
nth_element(_RAIter, _RAIter, _RAIter);
- template<typename _RAIter, typename _Compare>
+template<typename _RAIter, typename _Compare>
void
- partial_sort(_RAIter, _RAIter, _RAIter, _Compare, __gnu_parallel::sequential_tag);
+ partial_sort(_RAIter, _RAIter, _RAIter, _Compare,
+ __gnu_parallel::sequential_tag);
- template<typename _RAIter>
+template<typename _RAIter>
void
partial_sort(_RAIter, _RAIter, _RAIter, __gnu_parallel::sequential_tag);
- template<typename _RAIter, typename _Compare>
+template<typename _RAIter, typename _Compare>
void
partial_sort(_RAIter, _RAIter, _RAIter, _Compare);
- template<typename _RAIter>
+template<typename _RAIter>
void
partial_sort(_RAIter, _RAIter, _RAIter);
- template<typename _FIter, typename Predicate>
+template<typename _FIter, typename Predicate>
_FIter
partition(_FIter, _FIter, Predicate, __gnu_parallel::sequential_tag);
- template<typename _FIter, typename Predicate>
+template<typename _FIter, typename Predicate>
_FIter
partition(_FIter, _FIter, Predicate);
- template<typename _FIter, typename Predicate, typename _IterTag>
+template<typename _FIter, typename Predicate, typename _IterTag>
_FIter
partition_switch(_FIter, _FIter, Predicate, _IterTag);
- template<typename _RAIter, typename Predicate>
+template<typename _RAIter, typename Predicate>
_RAIter
partition_switch(_RAIter, _RAIter, Predicate, random_access_iterator_tag);
- template<typename _RAIter>
+template<typename _RAIter>
void
random_shuffle(_RAIter, _RAIter, __gnu_parallel::sequential_tag);
- template<typename _RAIter, typename RandomNumberGenerator>
+template<typename _RAIter, typename RandomNumberGenerator>
void
- random_shuffle(_RAIter, _RAIter, RandomNumberGenerator& rand, __gnu_parallel::sequential_tag);
+ random_shuffle(_RAIter, _RAIter, RandomNumberGenerator& rand,
+ __gnu_parallel::sequential_tag);
- template<typename _RAIter>
+template<typename _RAIter>
void
random_shuffle(_RAIter, _RAIter);
- template<typename _RAIter, typename RandomNumberGenerator>
+template<typename _RAIter, typename RandomNumberGenerator>
void
random_shuffle(_RAIter, _RAIter, RandomNumberGenerator& rand);
- template<typename _IIter1, typename _IIter2, typename _OIter>
+template<typename _IIter1, typename _IIter2, typename _OIter>
_OIter
- set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, __gnu_parallel::sequential_tag);
+ set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename Predicate>
_OIter
- set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, __gnu_parallel::sequential_tag);
+ set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter>
+template<typename _IIter1, typename _IIter2, typename _OIter>
_OIter
set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename Predicate>
_OIter
set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate);
- template<typename _IIter1, typename _IIter2, typename Predicate, typename _OIter, typename _IterTag1, typename _IterTag2, typename _IterTag3>
+template<typename _IIter1, typename _IIter2, typename Predicate,
+ typename _OIter,
+ typename _IterTag1, typename _IterTag2, typename _IterTag3>
_OIter
- set_union_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, _IterTag1, _IterTag2, _IterTag3);
+ set_union_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate,
+ _IterTag1, _IterTag2, _IterTag3);
- template<typename _RAIter1, typename _RAIter2, typename Output_RAIter, typename Predicate>
+template<typename _RAIter1, typename _RAIter2, typename Output_RAIter,
+ typename Predicate>
Output_RAIter
- set_union_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, Output_RAIter, Predicate, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag);
+ set_union_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, Output_RAIter,
+ Predicate, random_access_iterator_tag,
+ random_access_iterator_tag, random_access_iterator_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter>
+template<typename _IIter1, typename _IIter2, typename _OIter>
_OIter
- set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, __gnu_parallel::sequential_tag);
+ set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename Predicate>
_OIter
- set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, __gnu_parallel::sequential_tag);
+ set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter>
+template<typename _IIter1, typename _IIter2, typename _OIter>
_OIter
set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename Predicate>
_OIter
set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate);
- template<typename _IIter1, typename _IIter2, typename Predicate, typename _OIter, typename _IterTag1, typename _IterTag2, typename _IterTag3>
+template<typename _IIter1, typename _IIter2, typename Predicate,
+ typename _OIter,
+ typename _IterTag1, typename _IterTag2, typename _IterTag3>
_OIter
- set_intersection_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, _IterTag1, _IterTag2, _IterTag3);
+ set_intersection_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ Predicate, _IterTag1, _IterTag2, _IterTag3);
- template<typename _RAIter1, typename _RAIter2, typename Output_RAIter, typename Predicate>
+template<typename _RAIter1, typename _RAIter2, typename Output_RAIter,
+ typename Predicate>
Output_RAIter
- set_intersection_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, Output_RAIter, Predicate, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag);
+ set_intersection_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2,
+ Output_RAIter, Predicate,
+ random_access_iterator_tag,
+ random_access_iterator_tag,
+ random_access_iterator_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter>
+template<typename _IIter1, typename _IIter2, typename _OIter>
_OIter
- set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, __gnu_parallel::sequential_tag);
+ set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename Predicate>
_OIter
- set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, __gnu_parallel::sequential_tag);
+ set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ Predicate, __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter>
+template<typename _IIter1, typename _IIter2, typename _OIter>
_OIter
set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename Predicate>
_OIter
- set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate);
+ set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ Predicate);
- template<typename _IIter1, typename _IIter2, typename Predicate, typename _OIter, typename _IterTag1, typename _IterTag2, typename _IterTag3>
+template<typename _IIter1, typename _IIter2, typename Predicate,
+ typename _OIter,
+ typename _IterTag1, typename _IterTag2, typename _IterTag3>
_OIter
- set_symmetric_difference_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, _IterTag1, _IterTag2, _IterTag3);
+ set_symmetric_difference_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ Predicate, _IterTag1, _IterTag2, _IterTag3);
- template<typename _RAIter1, typename _RAIter2, typename Output_RAIter, typename Predicate>
+template<typename _RAIter1, typename _RAIter2, typename Output_RAIter,
+ typename Predicate>
Output_RAIter
- set_symmetric_difference_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, Output_RAIter, Predicate, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag);
+ set_symmetric_difference_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2,
+ Output_RAIter, Predicate,
+ random_access_iterator_tag,
+ random_access_iterator_tag,
+ random_access_iterator_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter>
+template<typename _IIter1, typename _IIter2, typename _OIter>
_OIter
- set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, __gnu_parallel::sequential_tag);
+ set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename Predicate>
_OIter
- set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, __gnu_parallel::sequential_tag);
+ set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter>
+template<typename _IIter1, typename _IIter2, typename _OIter>
_OIter
set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename Predicate>
_OIter
set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate);
- template<typename _IIter1, typename _IIter2, typename Predicate, typename _OIter, typename _IterTag1, typename _IterTag2, typename _IterTag3>
+template<typename _IIter1, typename _IIter2, typename Predicate,
+ typename _OIter,
+ typename _IterTag1, typename _IterTag2, typename _IterTag3>
_OIter
- set_difference_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, _IterTag1, _IterTag2, _IterTag3);
+ set_difference_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate,
+ _IterTag1, _IterTag2, _IterTag3);
- template<typename _RAIter1, typename _RAIter2, typename Output_RAIter, typename Predicate>
+template<typename _RAIter1, typename _RAIter2, typename Output_RAIter,
+ typename Predicate>
Output_RAIter
- set_difference_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, Output_RAIter, Predicate, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag);
+ set_difference_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2,
+ Output_RAIter, Predicate,
+ random_access_iterator_tag,
+ random_access_iterator_tag,
+ random_access_iterator_tag);
- template<typename _RAIter>
+template<typename _RAIter>
void
sort(_RAIter, _RAIter, __gnu_parallel::sequential_tag);
- template<typename _RAIter, typename _Compare>
+template<typename _RAIter, typename _Compare>
void
sort(_RAIter, _RAIter, _Compare, __gnu_parallel::sequential_tag);
- template<typename _RAIter>
+template<typename _RAIter>
void
sort(_RAIter, _RAIter);
- template<typename _RAIter, typename _Compare>
+template<typename _RAIter, typename _Compare>
void
sort(_RAIter, _RAIter, _Compare);
- template<typename _RAIter>
+template<typename _RAIter>
void
stable_sort(_RAIter, _RAIter, __gnu_parallel::sequential_tag);
- template<typename _RAIter, typename _Compare>
+template<typename _RAIter, typename _Compare>
void
stable_sort(_RAIter, _RAIter, _Compare, __gnu_parallel::sequential_tag);
- template<typename _RAIter>
+template<typename _RAIter>
void
stable_sort(_RAIter, _RAIter);
- template<typename _RAIter, typename _Compare>
+template<typename _RAIter, typename _Compare>
void
stable_sort(_RAIter, _RAIter, _Compare);
- template<typename _IIter, typename _OIter>
+template<typename _IIter, typename _OIter>
_OIter
unique_copy(_IIter, _IIter, _OIter, __gnu_parallel::sequential_tag);
- template<typename _IIter, typename _OIter, typename Predicate>
+template<typename _IIter, typename _OIter, typename Predicate>
_OIter
- unique_copy(_IIter, _IIter, _OIter, Predicate, __gnu_parallel::sequential_tag);
+ unique_copy(_IIter, _IIter, _OIter, Predicate,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter, typename _OIter>
+template<typename _IIter, typename _OIter>
_OIter
unique_copy(_IIter, _IIter, _OIter);
- template<typename _IIter, typename _OIter, typename Predicate>
+template<typename _IIter, typename _OIter, typename Predicate>
_OIter
unique_copy(_IIter, _IIter, _OIter, Predicate);
- template<typename _IIter, typename _OIter, typename Predicate, typename _IterTag1, typename _IterTag2>
+template<typename _IIter, typename _OIter, typename Predicate,
+ typename _IterTag1, typename _IterTag2>
_OIter
unique_copy_switch(_IIter, _IIter, _OIter, Predicate, _IterTag1, _IterTag2);
- template<typename _RAIter, typename RandomAccess_OIter, typename Predicate>
+template<typename _RAIter, typename RandomAccess_OIter, typename Predicate>
RandomAccess_OIter
unique_copy_switch(_RAIter, _RAIter, RandomAccess_OIter, Predicate,
- random_access_iterator_tag, random_access_iterator_tag);
+ random_access_iterator_tag, random_access_iterator_tag);
} // end namespace __parallel
} // end namespace std
Index: include/parallel/for_each_selectors.h
===================================================================
--- include/parallel/for_each_selectors.h (revision 130490)
+++ include/parallel/for_each_selectors.h (working copy)
@@ -45,7 +45,7 @@
{
/** @brief Generic selector for embarrassingly parallel functions. */
- template<typename It>
+template<typename It>
struct generic_for_each_selector
{
/** @brief Iterator on last element processed; needed for some
@@ -56,13 +56,13 @@
/** @brief std::for_each() selector. */
- template<typename It>
+template<typename It>
struct for_each_selector : public generic_for_each_selector<It>
{
/** @brief Functor execution.
* @param o Operator.
* @param i Iterator referencing object. */
- template<typename Op>
+ template<typename Op>
inline bool operator()(Op& o, It i)
{
o(*i);
@@ -71,13 +71,13 @@
};
/** @brief std::generate() selector. */
- template<typename It>
+template<typename It>
struct generate_selector : public generic_for_each_selector<It>
{
/** @brief Functor execution.
* @param o Operator.
* @param i Iterator referencing object. */
- template<typename Op>
+ template<typename Op>
inline bool operator()(Op& o, It i)
{
*i = o();
@@ -86,13 +86,13 @@
};
/** @brief std::fill() selector. */
- template<typename It>
+template<typename It>
struct fill_selector : public generic_for_each_selector<It>
{
/** @brief Functor execution.
* @param v Current value.
* @param i Iterator referencing object. */
- template<typename Val>
+ template<typename Val>
inline bool operator()(Val& v, It i)
{
*i = v;
@@ -101,13 +101,13 @@
};
/** @brief std::transform() selector, one input sequence variant. */
- template<typename It>
+template<typename It>
struct transform1_selector : public generic_for_each_selector<It>
{
/** @brief Functor execution.
* @param o Operator.
* @param i Iterator referencing object. */
- template<typename Op>
+ template<typename Op>
inline bool operator()(Op& o, It i)
{
*i.second = o(*i.first);
@@ -116,13 +116,13 @@
};
/** @brief std::transform() selector, two input sequences variant. */
- template<typename It>
+template<typename It>
struct transform2_selector : public generic_for_each_selector<It>
{
/** @brief Functor execution.
* @param o Operator.
* @param i Iterator referencing object. */
- template<typename Op>
+ template<typename Op>
inline bool operator()(Op& o, It i)
{
*i.third = o(*i.first, *i.second);
@@ -131,7 +131,7 @@
};
/** @brief std::replace() selector. */
- template<typename It, typename T>
+template<typename It, typename T>
struct replace_selector : public generic_for_each_selector<It>
{
/** @brief Value to replace with. */
@@ -153,7 +153,7 @@
};
/** @brief std::replace() selector. */
- template<typename It, typename Op, typename T>
+template<typename It, typename Op, typename T>
struct replace_if_selector : public generic_for_each_selector<It>
{
/** @brief Value to replace with. */
@@ -175,46 +175,47 @@
};
/** @brief std::count() selector. */
- template<typename It, typename Diff>
+template<typename It, typename Diff>
struct count_selector : public generic_for_each_selector<It>
{
/** @brief Functor execution.
* @param v Current value.
* @param i Iterator referencing object.
* @return 1 if count, 0 if does not count. */
- template<typename Val>
+ template<typename Val>
inline Diff operator()(Val& v, It i)
{ return (v == *i) ? 1 : 0; }
};
/** @brief std::count_if () selector. */
- template<typename It, typename Diff>
+template<typename It, typename Diff>
struct count_if_selector : public generic_for_each_selector<It>
{
/** @brief Functor execution.
* @param o Operator.
* @param i Iterator referencing object.
* @return 1 if count, 0 if does not count. */
- template<typename Op>
+ template<typename Op>
inline Diff operator()(Op& o, It i)
{ return (o(*i)) ? 1 : 0; }
};
/** @brief std::accumulate() selector. */
- template<typename It>
+template<typename It>
struct accumulate_selector : public generic_for_each_selector<It>
{
/** @brief Functor execution.
* @param o Operator (unused).
* @param i Iterator referencing object.
* @return The current value. */
- template<typename Op>
- inline typename std::iterator_traits<It>::value_type operator()(Op o, It i)
+ template<typename Op>
+ inline typename std::iterator_traits<It>::value_type operator()
+ (Op o, It i)
{ return *i; }
};
/** @brief std::inner_product() selector. */
- template<typename It, typename It2, typename T>
+template<typename It, typename It2, typename T>
struct inner_product_selector : public generic_for_each_selector<It>
{
/** @brief Begin iterator of first sequence. */
@@ -226,29 +227,31 @@
/** @brief Constructor.
* @param b1 Begin iterator of first sequence.
* @param b2 Begin iterator of second sequence. */
- explicit inner_product_selector(It b1, It2 b2) : begin1_iterator(b1), begin2_iterator(b2) { }
+ explicit inner_product_selector(It b1, It2 b2) : begin1_iterator(b1),
+ begin2_iterator(b2) { }
/** @brief Functor execution.
* @param mult Multiplication functor.
* @param current Iterator referencing object.
* @return Inner product elemental result. */
- template<typename Op>
+ template<typename Op>
inline T operator()(Op mult, It current)
{
- typename std::iterator_traits<It>::difference_type position = current - begin1_iterator;
+ typename std::iterator_traits<It>::difference_type position
+ = current - begin1_iterator;
return mult(*current, *(begin2_iterator + position));
}
};
/** @brief Selector that just returns the passed iterator. */
- template<typename It>
+template<typename It>
struct identity_selector : public generic_for_each_selector<It>
{
/** @brief Functor execution.
* @param o Operator (unused).
* @param i Iterator referencing object.
* @return Passed iterator. */
- template<typename Op>
+ template<typename Op>
inline It operator()(Op o, It i)
{ return i; }
};
@@ -256,10 +259,10 @@
/** @brief Selector that returns the difference between two adjacent
* elements.
*/
- template<typename It>
+template<typename It>
struct adjacent_difference_selector : public generic_for_each_selector<It>
{
- template<typename Op>
+ template<typename Op>
inline bool operator()(Op& o, It i)
{
typename It::first_type go_back_one = i.first;
@@ -279,7 +282,7 @@
{
/** @brief Functor execution.
* @param i Iterator referencing object. */
- template<typename It>
+ template<typename It>
inline void operator()(It i)
{ }
};
@@ -292,7 +295,7 @@
};
/** @brief Reduction for finding the maximum element, using a comparator. */
- template<typename Comp, typename It>
+template<typename Comp, typename It>
struct min_element_reduct
{
Comp& comp;
@@ -310,7 +313,7 @@
};
/** @brief Reduction for finding the maximum element, using a comparator. */
- template<typename Comp, typename It>
+template<typename Comp, typename It>
struct max_element_reduct
{
Comp& comp;
@@ -328,14 +331,14 @@
};
/** @brief General reduction, using a binary operator. */
- template<typename BinOp>
+template<typename BinOp>
struct accumulate_binop_reduct
{
BinOp& binop;
explicit accumulate_binop_reduct(BinOp& b) : binop(b) {}
- template<typename Result, typename Addend>
+ template<typename Result, typename Addend>
Result operator()(const Result& x, const Addend& y) { return binop(x, y); }
};
}
Index: include/parallel/balanced_quicksort.h
===================================================================
--- include/parallel/balanced_quicksort.h (revision 130490)
+++ include/parallel/balanced_quicksort.h (working copy)
@@ -329,7 +329,8 @@
{
// Right side larger.
if ((split_pos2) != end)
- tl.leftover_parts.push_front(std::make_pair(split_pos2, end));
+ tl.leftover_parts.push_front
+ (std::make_pair(split_pos2, end));
//current.first = begin; //already set anyway
current.second = split_pos1;
Index: include/parallel/merge.h
===================================================================
--- include/parallel/merge.h (revision 130490)
+++ include/parallel/merge.h (working copy)
@@ -56,30 +56,37 @@
* @param max_length Maximum number of elements to merge.
* @param comp Comparator.
* @return Output end iterator. */
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename OutputIterator, typename _DifferenceTp, typename Comparator>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename OutputIterator, typename _DifferenceTp,
+ typename Comparator>
OutputIterator
- merge_advance_usual(RandomAccessIterator1& begin1, RandomAccessIterator1 end1, RandomAccessIterator2& begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp)
+ merge_advance_usual(RandomAccessIterator1& begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator2& begin2,
+ RandomAccessIterator2 end2,
+ OutputIterator target,
+ _DifferenceTp max_length, Comparator comp)
{
typedef _DifferenceTp difference_type;
while (begin1 != end1 && begin2 != end2 && max_length > 0)
{
- // array1[i1] < array0[i0]
- if (comp(*begin2, *begin1))
- *target++ = *begin2++;
- else
- *target++ = *begin1++;
- max_length--;
+ // array1[i1] < array0[i0]
+ if (comp(*begin2, *begin1))
+ *target++ = *begin2++;
+ else
+ *target++ = *begin1++;
+ max_length--;
}
if (begin1 != end1)
{
- target = std::copy(begin1, begin1 + max_length, target);
- begin1 += max_length;
+ target = std::copy(begin1, begin1 + max_length, target);
+ begin1 += max_length;
}
else
{
- target = std::copy(begin2, begin2 + max_length, target);
- begin2 += max_length;
+ target = std::copy(begin2, begin2 + max_length, target);
+ begin2 += max_length;
}
return target;
}
@@ -99,13 +106,20 @@
* @param max_length Maximum number of elements to merge.
* @param comp Comparator.
* @return Output end iterator. */
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename OutputIterator, typename _DifferenceTp, typename Comparator>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename OutputIterator, typename _DifferenceTp,
+ typename Comparator>
OutputIterator
- merge_advance_movc(RandomAccessIterator1& begin1, RandomAccessIterator1 end1, RandomAccessIterator2& begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp)
+ merge_advance_movc(RandomAccessIterator1& begin1, RandomAccessIterator1 end1,
+ RandomAccessIterator2& begin2, RandomAccessIterator2 end2,
+ OutputIterator target, _DifferenceTp max_length,
+ Comparator comp)
{
typedef _DifferenceTp difference_type;
- typedef typename std::iterator_traits<RandomAccessIterator1>::value_type value_type1;
- typedef typename std::iterator_traits<RandomAccessIterator2>::value_type value_type2;
+ typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
+ value_type1;
+ typedef typename std::iterator_traits<RandomAccessIterator2>::value_type
+ value_type2;
#if _GLIBCXX_ASSERTIONS
_GLIBCXX_PARALLEL_ASSERT(max_length >= 0);
@@ -113,35 +127,35 @@
while (begin1 != end1 && begin2 != end2 && max_length > 0)
{
- RandomAccessIterator1 next1 = begin1 + 1;
- RandomAccessIterator2 next2 = begin2 + 1;
- value_type1 element1 = *begin1;
- value_type2 element2 = *begin2;
+ RandomAccessIterator1 next1 = begin1 + 1;
+ RandomAccessIterator2 next2 = begin2 + 1;
+ value_type1 element1 = *begin1;
+ value_type2 element2 = *begin2;
- if (comp(element2, element1))
- {
- element1 = element2;
- begin2 = next2;
- }
- else
- {
- begin1 = next1;
- }
+ if (comp(element2, element1))
+ {
+ element1 = element2;
+ begin2 = next2;
+ }
+ else
+ {
+ begin1 = next1;
+ }
- *target = element1;
+ *target = element1;
- target++;
- max_length--;
+ target++;
+ max_length--;
}
if (begin1 != end1)
{
- target = std::copy(begin1, begin1 + max_length, target);
- begin1 += max_length;
+ target = std::copy(begin1, begin1 + max_length, target);
+ begin1 += max_length;
}
else
{
- target = std::copy(begin2, begin2 + max_length, target);
- begin2 += max_length;
+ target = std::copy(begin2, begin2 + max_length, target);
+ begin2 += max_length;
}
return target;
}
@@ -160,13 +174,19 @@
* @param max_length Maximum number of elements to merge.
* @param comp Comparator.
* @return Output end iterator. */
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename OutputIterator, typename _DifferenceTp, typename Comparator>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename OutputIterator, typename _DifferenceTp,
+ typename Comparator>
inline OutputIterator
- merge_advance(RandomAccessIterator1& begin1, RandomAccessIterator1 end1, RandomAccessIterator2& begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp)
+ merge_advance(RandomAccessIterator1& begin1, RandomAccessIterator1 end1,
+ RandomAccessIterator2& begin2, RandomAccessIterator2 end2,
+ OutputIterator target, _DifferenceTp max_length,
+ Comparator comp)
{
_GLIBCXX_CALL(max_length)
- return merge_advance_movc(begin1, end1, begin2, end2, target, max_length, comp);
+ return merge_advance_movc
+ (begin1, end1, begin2, end2, target, max_length, comp);
}
/** @brief Merge routine fallback to sequential in case the
@@ -179,12 +199,17 @@
* @param max_length Maximum number of elements to merge.
* @param comp Comparator.
* @return Output end iterator. */
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename RandomAccessIterator3, typename Comparator>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename RandomAccessIterator3, typename Comparator>
inline RandomAccessIterator3
- parallel_merge_advance(RandomAccessIterator1& begin1, RandomAccessIterator1 end1,
- RandomAccessIterator2& begin2, RandomAccessIterator2 end2, //different iterators, parallel implementation not available
- RandomAccessIterator3 target,
- typename std::iterator_traits<RandomAccessIterator1>::difference_type max_length, Comparator comp)
+ parallel_merge_advance(RandomAccessIterator1& begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator2& begin2,
+ //different iterators, parallelism not available
+ RandomAccessIterator2 end2,
+ RandomAccessIterator3 target,
+ typename std::iterator_traits<RandomAccessIterator1>
+ ::difference_type max_length, Comparator comp)
{
return merge_advance(begin1, end1, begin2, end2, target, max_length, comp);
}
@@ -204,22 +229,31 @@
* @param comp Comparator.
* @return Output end iterator.
*/
- template<typename RandomAccessIterator1, typename RandomAccessIterator3, typename Comparator>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator3,
+ typename Comparator>
inline RandomAccessIterator3
- parallel_merge_advance(RandomAccessIterator1& begin1, RandomAccessIterator1 end1, RandomAccessIterator1& begin2, RandomAccessIterator1 end2, RandomAccessIterator3 target, typename std::iterator_traits<RandomAccessIterator1>::difference_type max_length, Comparator comp)
+ parallel_merge_advance(RandomAccessIterator1& begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator1& begin2,
+ RandomAccessIterator1 end2,
+ RandomAccessIterator3 target,
+ typename std::iterator_traits<RandomAccessIterator1>
+ ::difference_type max_length, Comparator comp)
{
typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
value_type;
- typedef typename std::iterator_traits<RandomAccessIterator1>::difference_type
- difference_type1 /* == difference_type2 */;
- typedef typename std::iterator_traits<RandomAccessIterator3>::difference_type
- difference_type3;
+ typedef typename std::iterator_traits<RandomAccessIterator1>
+ ::difference_type difference_type1 /* == difference_type2 */;
+ typedef typename std::iterator_traits<RandomAccessIterator3>
+ ::difference_type difference_type3;
- std::pair<RandomAccessIterator1, RandomAccessIterator1> seqs[2] = { std::make_pair(begin1, end1), std::make_pair(begin2, end2) };
- RandomAccessIterator3 target_end = parallel_multiway_merge(seqs, seqs + 2, target, comp, max_length, true, false);
+ std::pair<RandomAccessIterator1, RandomAccessIterator1> seqs[2]
+ = { std::make_pair(begin1, end1), std::make_pair(begin2, end2) };
+ RandomAccessIterator3 target_end = parallel_multiway_merge
+ (seqs, seqs + 2, target, comp, max_length, true, false);
return target_end;
}
-} //namespace __gnu_parallel
+} //namespace __gnu_parallel
#endif
Index: include/parallel/unique_copy.h
===================================================================
--- include/parallel/unique_copy.h (revision 130490)
+++ include/parallel/unique_copy.h (working copy)
@@ -192,9 +192,11 @@
parallel_unique_copy(InputIterator first, InputIterator last,
OutputIterator result)
{
- typedef typename std::iterator_traits<InputIterator>::value_type value_type;
+ typedef typename std::iterator_traits<InputIterator>::value_type
+ value_type;
- return parallel_unique_copy(first, last, result, std::equal_to<value_type>());
+ return parallel_unique_copy(first, last, result,
+ std::equal_to<value_type>());
}
}//namespace __gnu_parallel
Index: include/parallel/settings.h
===================================================================
--- include/parallel/settings.h (revision 130490)
+++ include/parallel/settings.h (working copy)
@@ -33,7 +33,8 @@
* whether to use parallelized algorithms.
* This file is a GNU parallel extension to the Standard C++ Library.
*
- * @section parallelization_decision The decision whether to run an algorithm in parallel.
+ * @section parallelization_decision
+ * The decision whether to run an algorithm in parallel.
*
* There are several ways the user can switch on and off the
* parallel execution of an algorithm, both at compile- and
@@ -104,7 +105,10 @@
* __gnu_parallel::Settings::force_parallel, i. e. usually a decision based on
* the input size.
*/
-#define _GLIBCXX_PARALLEL_CONDITION(c) (!(__gnu_parallel::Settings::force_sequential) && ((__gnu_parallel::get_max_threads() > 1 && (c)) || __gnu_parallel::Settings::force_parallel))
+#define _GLIBCXX_PARALLEL_CONDITION(c) \
+ (!(__gnu_parallel::Settings::force_sequential) \
+ && ((__gnu_parallel::get_max_threads() > 1 && (c)) \
+ || __gnu_parallel::Settings::force_parallel))
namespace __gnu_parallel
{
@@ -131,7 +135,8 @@
/** @brief Different merging algorithms: bubblesort-alike,
loser-tree variants, enum sentinel */
enum MultiwayMergeAlgorithm
- { BUBBLE, LOSER_TREE_EXPLICIT, LOSER_TREE, LOSER_TREE_COMBINED, LOSER_TREE_SENTINEL, MWM_ALGORITHM_LAST };
+ { BUBBLE, LOSER_TREE_EXPLICIT, LOSER_TREE, LOSER_TREE_COMBINED,
+ LOSER_TREE_SENTINEL, MWM_ALGORITHM_LAST };
/** @brief Different splitting strategies for sorting/merging:
by sampling, exact */
@@ -340,7 +345,8 @@
volatile sequence_index_t Settings::partition_chunk_size = 1000;
volatile double Settings::partition_chunk_share = 0.0;
volatile unsigned int Settings::adjacent_difference_minimal_n = 1000;
- volatile Settings::PartialSumAlgorithm Settings::partial_sum_algorithm = Settings::LINEAR;
+ volatile Settings::PartialSumAlgorithm Settings::partial_sum_algorithm
+ = Settings::LINEAR;
volatile unsigned int Settings::partial_sum_minimal_n = 1000;
volatile float Settings::partial_sum_dilatation = 1.0f;
volatile unsigned int Settings::random_shuffle_minimal_n = 1000;
@@ -352,10 +358,13 @@
// unique copy
volatile sequence_index_t Settings::unique_copy_minimal_n = 10000;
- volatile Settings::MultiwayMergeAlgorithm Settings::multiway_merge_algorithm = Settings::LOSER_TREE;
- volatile Settings::Splitting Settings::multiway_merge_splitting = Settings::EXACT;
+ volatile Settings::MultiwayMergeAlgorithm Settings::multiway_merge_algorithm
+ = Settings::LOSER_TREE;
+ volatile Settings::Splitting Settings::multiway_merge_splitting
+ = Settings::EXACT;
volatile unsigned int Settings::multiway_merge_oversampling = 10;
- volatile Settings::FindDistribution Settings::find_distribution = Settings::CONSTANT_SIZE_BLOCKS;
+ volatile Settings::FindDistribution Settings::find_distribution
+ = Settings::CONSTANT_SIZE_BLOCKS;
volatile sequence_index_t Settings::find_sequential_search_size = 256;
volatile sequence_index_t Settings::find_initial_block_size = 256;
volatile sequence_index_t Settings::find_maximum_block_size = 8192;
@@ -375,7 +384,8 @@
volatile sequence_index_t Settings::set_union_minimal_n = 1000;
volatile sequence_index_t Settings::set_intersection_minimal_n = 1000;
volatile sequence_index_t Settings::set_difference_minimal_n = 1000;
- volatile sequence_index_t Settings::set_symmetric_difference_minimal_n = 1000;
+ volatile sequence_index_t Settings::set_symmetric_difference_minimal_n
+ = 1000;
volatile unsigned long long Settings::L1_cache_size = 16 << 10;
volatile unsigned long long Settings::L2_cache_size = 256 << 10;
volatile unsigned int Settings::TLB_size = 128;
Index: include/parallel/numericfwd.h
===================================================================
--- include/parallel/numericfwd.h (revision 130490)
+++ include/parallel/numericfwd.h (working copy)
@@ -44,146 +44,158 @@
{
namespace __parallel
{
- template<typename _IIter, typename T>
+template<typename _IIter, typename T>
inline T
accumulate(_IIter, _IIter, T);
- template<typename _IIter, typename T>
+template<typename _IIter, typename T>
inline T
accumulate(_IIter, _IIter, T, __gnu_parallel::sequential_tag);
- template<typename _IIter, typename T>
+template<typename _IIter, typename T>
inline T
accumulate(_IIter, _IIter, T, __gnu_parallel::parallelism parallelism_tag);
- template<typename _IIter, typename T, typename _Tag>
+template<typename _IIter, typename T, typename _Tag>
inline T
accumulate_switch(_IIter, _IIter, T, _Tag);
- template<typename _IIter, typename T, typename _BinaryOper>
+template<typename _IIter, typename T, typename _BinaryOper>
inline T
accumulate(_IIter, _IIter, T, _BinaryOper);
- template<typename _IIter, typename T, typename _BinaryOper>
+template<typename _IIter, typename T, typename _BinaryOper>
inline T
accumulate(_IIter, _IIter, T, _BinaryOper, __gnu_parallel::sequential_tag);
- template<typename _IIter, typename T, typename _BinaryOper>
+template<typename _IIter, typename T, typename _BinaryOper>
inline T
accumulate(_IIter, _IIter, T, _BinaryOper,
- __gnu_parallel::parallelism parallelism_tag);
+ __gnu_parallel::parallelism parallelism_tag);
- template<typename _IIter, typename T, typename _BinaryOper, typename _Tag>
+template<typename _IIter, typename T, typename _BinaryOper, typename _Tag>
T
accumulate_switch(_IIter, _IIter, T, _BinaryOper, _Tag);
- template<typename _RAIter, typename T, typename _BinaryOper>
+template<typename _RAIter, typename T, typename _BinaryOper>
T
accumulate_switch(_RAIter, _RAIter, T, _BinaryOper,
- random_access_iterator_tag, __gnu_parallel::parallelism);
+ random_access_iterator_tag, __gnu_parallel::parallelism);
template<typename _IIter, typename _OIter>
inline _OIter
adjacent_difference(_IIter, _IIter, _OIter);
- template<typename _IIter, typename _OIter, typename _BinaryOper>
+template<typename _IIter, typename _OIter, typename _BinaryOper>
inline _OIter
adjacent_difference(_IIter, _IIter, _OIter, _BinaryOper);
- template<typename _IIter, typename _OIter>
+template<typename _IIter, typename _OIter>
inline _OIter
adjacent_difference(_IIter, _IIter, _OIter, __gnu_parallel::sequential_tag);
- template<typename _IIter, typename _OIter, typename _BinaryOper>
+template<typename _IIter, typename _OIter, typename _BinaryOper>
inline _OIter
adjacent_difference(_IIter, _IIter, _OIter, _BinaryOper,
- __gnu_parallel::sequential_tag);
+ __gnu_parallel::sequential_tag);
- template<typename _IIter, typename _OIter>
+template<typename _IIter, typename _OIter>
inline _OIter
adjacent_difference(_IIter, _IIter, _OIter, __gnu_parallel::parallelism);
- template<typename _IIter, typename _OIter, typename _BinaryOper>
+template<typename _IIter, typename _OIter, typename _BinaryOper>
inline _OIter
adjacent_difference(_IIter, _IIter, _OIter, _BinaryOper,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
- template<typename _IIter, typename _OIter, typename _BinaryOper, typename _Tag1, typename _Tag2>
+template<typename _IIter, typename _OIter, typename _BinaryOper,
+ typename _Tag1, typename _Tag2>
inline _OIter
- adjacent_difference_switch(_IIter, _IIter, _OIter, _BinaryOper, _Tag1, _Tag2);
+ adjacent_difference_switch(_IIter, _IIter, _OIter, _BinaryOper,
+ _Tag1, _Tag2);
- template<typename _IIter, typename _OIter, typename _BinaryOper>
+template<typename _IIter, typename _OIter, typename _BinaryOper>
_OIter
adjacent_difference_switch(_IIter, _IIter, _OIter, _BinaryOper,
- random_access_iterator_tag,
- random_access_iterator_tag,
- __gnu_parallel::parallelism);
+ random_access_iterator_tag,
+ random_access_iterator_tag,
+ __gnu_parallel::parallelism);
- template<typename _IIter1, typename _IIter2, typename T>
+template<typename _IIter1, typename _IIter2, typename T>
inline T
inner_product(_IIter1, _IIter1, _IIter2, T);
- template<typename _IIter1, typename _IIter2, typename T>
+template<typename _IIter1, typename _IIter2, typename T>
inline T
inner_product(_IIter1, _IIter1, _IIter2, T, __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename T>
+template<typename _IIter1, typename _IIter2, typename T>
inline T
inner_product(_IIter1, _IIter1, _IIter2, T, __gnu_parallel::parallelism);
- template<typename _IIter1, typename _IIter2, typename T, typename BinaryFunction1, typename BinaryFunction2>
+template<typename _IIter1, typename _IIter2, typename T,
+ typename BinaryFunction1, typename BinaryFunction2>
inline T
- inner_product(_IIter1, _IIter1, _IIter2, T, BinaryFunction1, BinaryFunction2);
+ inner_product(_IIter1, _IIter1, _IIter2, T,
+ BinaryFunction1, BinaryFunction2);
- template<typename _IIter1, typename _IIter2, typename T, typename BinaryFunction1, typename BinaryFunction2>
+template<typename _IIter1, typename _IIter2, typename T,
+ typename BinaryFunction1, typename BinaryFunction2>
inline T
inner_product(_IIter1, _IIter1, _IIter2, T, BinaryFunction1, BinaryFunction2,
- __gnu_parallel::sequential_tag);
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename T, typename BinaryFunction1, typename BinaryFunction2>
+template<typename _IIter1, typename _IIter2, typename T,
+ typename BinaryFunction1, typename BinaryFunction2>
inline T
inner_product(_IIter1, _IIter1, _IIter2, T, BinaryFunction1, BinaryFunction2,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
- template<typename _RAIter1, typename _RAIter2, typename T, typename BinaryFunction1, typename BinaryFunction2>
+template<typename _RAIter1, typename _RAIter2, typename T,
+ typename BinaryFunction1, typename BinaryFunction2>
T
inner_product_switch(_RAIter1, _RAIter1, _RAIter2, T, BinaryFunction1,
- BinaryFunction2, random_access_iterator_tag,
- random_access_iterator_tag,
- __gnu_parallel::parallelism);
+ BinaryFunction2, random_access_iterator_tag,
+ random_access_iterator_tag,
+ __gnu_parallel::parallelism);
- template<typename _IIter1, typename _IIter2, typename T, typename BinaryFunction1, typename BinaryFunction2, typename _Tag1, typename _Tag2>
+template<typename _IIter1, typename _IIter2, typename T,
+ typename BinaryFunction1, typename BinaryFunction2,
+ typename _Tag1, typename _Tag2>
inline T
inner_product_switch(_IIter1, _IIter1, _IIter2, T, BinaryFunction1,
- BinaryFunction2, _Tag1, _Tag2);
+ BinaryFunction2, _Tag1, _Tag2);
- template<typename _IIter, typename _OIter>
+template<typename _IIter, typename _OIter>
inline _OIter
partial_sum(_IIter, _IIter, _OIter, __gnu_parallel::sequential_tag);
- template<typename _IIter, typename _OIter, typename _BinaryOper>
+template<typename _IIter, typename _OIter, typename _BinaryOper>
inline _OIter
- partial_sum(_IIter, _IIter, _OIter, _BinaryOper, __gnu_parallel::sequential_tag);
+ partial_sum(_IIter, _IIter, _OIter, _BinaryOper,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter, typename _OIter>
+template<typename _IIter, typename _OIter>
inline _OIter
partial_sum(_IIter, _IIter, _OIter result);
- template<typename _IIter, typename _OIter, typename _BinaryOper>
+template<typename _IIter, typename _OIter, typename _BinaryOper>
inline _OIter
partial_sum(_IIter, _IIter, _OIter, _BinaryOper);
- template<typename _IIter, typename _OIter, typename _BinaryOper, typename _Tag1, typename _Tag2>
+template<typename _IIter, typename _OIter, typename _BinaryOper,
+ typename _Tag1, typename _Tag2>
inline _OIter
partial_sum_switch(_IIter, _IIter, _OIter, _BinaryOper, _Tag1, _Tag2);
- template<typename _IIter, typename _OIter, typename _BinaryOper>
+template<typename _IIter, typename _OIter, typename _BinaryOper>
_OIter
- partial_sum_switch(_IIter, _IIter, _OIter, _BinaryOper, random_access_iterator_tag, random_access_iterator_tag);
+ partial_sum_switch(_IIter, _IIter, _OIter, _BinaryOper,
+ random_access_iterator_tag, random_access_iterator_tag);
} // end namespace
} // end namespace
Index: include/parallel/search.h
===================================================================
--- include/parallel/search.h (revision 130490)
+++ include/parallel/search.h (working copy)
@@ -152,9 +152,9 @@
if (pos_in_pattern == pattern_length)
{
// Found new candidate for result.
- omp_set_lock(&result_lock);
+ omp_set_lock(&result_lock);
result = std::min(result, start);
- omp_unset_lock(&result_lock);
+ omp_unset_lock(&result_lock);
found_pattern = true;
break;
Index: include/parallel/partition.h
===================================================================
--- include/parallel/partition.h (revision 130490)
+++ include/parallel/partition.h (working copy)
@@ -51,11 +51,11 @@
namespace __gnu_parallel
{
/** @brief Parallel implementation of std::partition.
- * @param begin Begin iterator of input sequence to split.
- * @param end End iterator of input sequence to split.
- * @param pred Partition predicate, possibly including some kind of pivot.
- * @param num_threads Maximum number of threads to use for this task.
- * @return Number of elements not fulfilling the predicate. */
+ * @param begin Begin iterator of input sequence to split.
+ * @param end End iterator of input sequence to split.
+ * @param pred Partition predicate, possibly including some kind of pivot.
+ * @param num_threads Maximum number of threads to use for this task.
+ * @return Number of elements not fulfilling the predicate. */
template<typename RandomAccessIterator, typename Predicate>
typename std::iterator_traits<RandomAccessIterator>::difference_type
parallel_partition(RandomAccessIterator begin, RandomAccessIterator end,
@@ -106,7 +106,7 @@
{
difference_type num_chunks = (right - left + 1) / chunk_size;
- for (int r = 0; r < num_threads; r++)
+ for (int r = 0; r < num_threads; ++r)
{
reserved_left[r] = false;
reserved_right[r] = false;
@@ -164,10 +164,10 @@
{
while (pred(begin[thread_left])
&& thread_left <= thread_left_border)
- thread_left++;
+ ++thread_left;
while (!pred(begin[thread_right])
&& thread_right >= thread_right_border)
- thread_right--;
+ --thread_right;
if (thread_left > thread_left_border
|| thread_right < thread_right_border)
@@ -175,18 +175,18 @@
break;
std::swap(begin[thread_left], begin[thread_right]);
- thread_left++;
- thread_right--;
+ ++thread_left;
+ --thread_right;
}
}
// Now swap the leftover chunks to the right places.
if (thread_left <= thread_left_border)
# pragma omp atomic
- leftover_left++;
+ ++leftover_left;
if (thread_right >= thread_right_border)
# pragma omp atomic
- leftover_right++;
+ ++leftover_right;
# pragma omp barrier
@@ -225,7 +225,7 @@
// Find spot and swap.
difference_type swapstart = -1;
omp_set_lock(&result_lock);
- for (int r = 0; r < leftover_left; r++)
+ for (int r = 0; r < leftover_left; ++r)
if (!reserved_left[r])
{
reserved_left[r] = true;
@@ -250,7 +250,7 @@
// Find spot and swap
difference_type swapstart = -1;
omp_set_lock(&result_lock);
- for (int r = 0; r < leftover_right; r++)
+ for (int r = 0; r < leftover_right; ++r)
if (!reserved_right[r])
{
reserved_right[r] = true;
@@ -272,9 +272,9 @@
# pragma omp single
{
- for (int r = 0; r < leftover_left; r++)
+ for (int r = 0; r < leftover_left; ++r)
_GLIBCXX_PARALLEL_ASSERT(reserved_left[r]);
- for (int r = 0; r < leftover_right; r++)
+ for (int r = 0; r < leftover_right; ++r)
_GLIBCXX_PARALLEL_ASSERT(reserved_right[r]);
}
@@ -295,17 +295,17 @@
{
// Go right until key is geq than pivot.
while (pred(begin[final_left]) && final_left < final_right)
- final_left++;
+ ++final_left;
// Go left until key is less than pivot.
while (!pred(begin[final_right]) && final_left < final_right)
- final_right--;
+ --final_right;
if (final_left == final_right)
break;
std::swap(begin[final_left], begin[final_right]);
- final_left++;
- final_right--;
+ ++final_left;
+ --final_right;
}
// All elements on the left side are < piv, all elements on the
@@ -325,12 +325,12 @@
}
/**
- * @brief Parallel implementation of std::nth_element().
- * @param begin Begin iterator of input sequence.
- * @param nth Iterator of element that must be in position afterwards.
- * @param end End iterator of input sequence.
- * @param comp Comparator.
- */
+ * @brief Parallel implementation of std::nth_element().
+ * @param begin Begin iterator of input sequence.
+ * @param nth Iterator of element that must be in position afterwards.
+ * @param end End iterator of input sequence.
+ * @param comp Comparator.
+ */
template<typename RandomAccessIterator, typename Comparator>
void
parallel_nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
@@ -345,7 +345,8 @@
RandomAccessIterator split;
random_number rng;
- difference_type minimum_length = std::max<difference_type>(2, Settings::partition_minimal_n);
+ difference_type minimum_length = std::max<difference_type>
+ (2, Settings::partition_minimal_n);
// Break if input range to small.
while (static_cast<sequence_index_t>(end - begin) >= minimum_length)
@@ -359,15 +360,19 @@
std::swap(*pivot_pos, *(end - 1));
pivot_pos = end - 1;
- // XXX Comparator must have first_value_type, second_value_type, result_type
- // Comparator == __gnu_parallel::lexicographic<S, int, __gnu_parallel::less<S, S> >
+ // XXX Comparator must have first_value_type, second_value_type,
+ // result_type
+ // Comparator ==
+ // __gnu_parallel::lexicographic<S, int, __gnu_parallel::less<S, S> >
// pivot_pos == std::pair<S, int>*
// XXX binder2nd only for RandomAccessIterators??
- __gnu_parallel::binder2nd<Comparator, value_type, value_type, bool> pred(comp, *pivot_pos);
+ __gnu_parallel::binder2nd<Comparator, value_type, value_type, bool>
+ pred(comp, *pivot_pos);
// Divide, leave pivot unchanged in last place.
RandomAccessIterator split_pos1, split_pos2;
- split_pos1 = begin + parallel_partition(begin, end - 1, pred, get_max_threads());
+ split_pos1 = begin + parallel_partition
+ (begin, end - 1, pred, get_max_threads());
// Left side: < pivot_pos; right side: >= pivot_pos
@@ -377,14 +382,21 @@
pivot_pos = split_pos1;
// In case all elements are equal, split_pos1 == 0
- if ((split_pos1 + 1 - begin) < (n >> 7) || (end - split_pos1) < (n >> 7))
+ if ((split_pos1 + 1 - begin) < (n >> 7)
+ || (end - split_pos1) < (n >> 7))
{
// Very unequal split, one part smaller than one 128th
// elements not stricly larger than the pivot.
- __gnu_parallel::unary_negate<__gnu_parallel::binder1st<Comparator, value_type, value_type, bool>, value_type> pred(__gnu_parallel::binder1st<Comparator, value_type, value_type, bool>(comp, *pivot_pos));
+ __gnu_parallel::unary_negate
+ <__gnu_parallel::binder1st
+ <Comparator, value_type, value_type, bool>, value_type>
+ pred(__gnu_parallel::binder1st
+ <Comparator, value_type, value_type, bool>(
+ comp, *pivot_pos));
// Find other end of pivot-equal range.
- split_pos2 = __gnu_sequential::partition(split_pos1 + 1, end, pred);
+ split_pos2 = __gnu_sequential::partition(split_pos1 + 1, end,
+ pred);
}
else
// Only skip the pivot.
@@ -404,13 +416,15 @@
}
/** @brief Parallel implementation of std::partial_sort().
-* @param begin Begin iterator of input sequence.
-* @param middle Sort until this position.
-* @param end End iterator of input sequence.
-* @param comp Comparator. */
+ * @param begin Begin iterator of input sequence.
+ * @param middle Sort until this position.
+ * @param end End iterator of input sequence.
+ * @param comp Comparator. */
template<typename RandomAccessIterator, typename Comparator>
void
- parallel_partial_sort(RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end, Comparator comp)
+ parallel_partial_sort(RandomAccessIterator begin,
+ RandomAccessIterator middle,
+ RandomAccessIterator end, Comparator comp)
{
parallel_nth_element(begin, middle, end, comp);
std::sort(begin, middle, comp);
Index: include/parallel/algobase.h
===================================================================
--- include/parallel/algobase.h (revision 130490)
+++ include/parallel/algobase.h (working copy)
@@ -56,45 +56,49 @@
// NB: equal and lexicographical_compare require mismatch.
// Sequential fallback
- template<typename InputIterator1, typename InputIterator2>
+template<typename InputIterator1, typename InputIterator2>
inline pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- __gnu_parallel::sequential_tag)
+ __gnu_parallel::sequential_tag)
{ return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2); }
// Sequential fallback
- template<typename InputIterator1, typename InputIterator2, typename Predicate>
+template<typename InputIterator1, typename InputIterator2, typename Predicate>
inline pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- Predicate pred, __gnu_parallel::sequential_tag)
+ Predicate pred, __gnu_parallel::sequential_tag)
{ return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); }
// Sequential fallback for input iterator case
- template<typename InputIterator1, typename InputIterator2, typename Predicate, typename IteratorTag1, typename IteratorTag2>
+template<typename InputIterator1, typename InputIterator2, typename Predicate,
+ typename IteratorTag1, typename IteratorTag2>
inline pair<InputIterator1, InputIterator2>
mismatch_switch(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, Predicate pred, IteratorTag1,
- IteratorTag2)
+ InputIterator2 begin2, Predicate pred, IteratorTag1,
+ IteratorTag2)
{ return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); }
// Parallel mismatch for random access iterators
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Predicate>
+template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Predicate>
pair<RandomAccessIterator1, RandomAccessIterator2>
mismatch_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
- RandomAccessIterator2 begin2, Predicate pred,
- random_access_iterator_tag, random_access_iterator_tag)
+ RandomAccessIterator2 begin2, Predicate pred,
+ random_access_iterator_tag, random_access_iterator_tag)
{
if (_GLIBCXX_PARALLEL_CONDITION(true))
{
- RandomAccessIterator1 res = __gnu_parallel::find_template(begin1, end1, begin2, pred, __gnu_parallel::mismatch_selector()).first;
- return make_pair(res , begin2 + (res - begin1));
+ RandomAccessIterator1 res = __gnu_parallel::find_template
+ (begin1, end1, begin2, pred,
+ __gnu_parallel::mismatch_selector()).first;
+ return make_pair(res , begin2 + (res - begin1));
}
else
return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred);
}
// Public interface
- template<typename InputIterator1, typename InputIterator2>
+template<typename InputIterator1, typename InputIterator2>
inline pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2)
{
@@ -108,14 +112,14 @@
typedef __gnu_parallel::equal_to<value1_type, value2_type> equal_to_type;
return mismatch_switch(begin1, end1, begin2, equal_to_type(),
- iterator1_category(), iterator2_category());
+ iterator1_category(), iterator2_category());
}
// Public interface
- template<typename InputIterator1, typename InputIterator2, typename Predicate>
+template<typename InputIterator1, typename InputIterator2, typename Predicate>
inline pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- Predicate pred)
+ Predicate pred)
{
typedef std::iterator_traits<InputIterator1> iterator1_traits;
typedef std::iterator_traits<InputIterator2> iterator2_traits;
@@ -123,131 +127,138 @@
typedef typename iterator2_traits::iterator_category iterator2_category;
return mismatch_switch(begin1, end1, begin2, pred, iterator1_category(),
- iterator2_category());
+ iterator2_category());
}
// Sequential fallback
- template<typename InputIterator1, typename InputIterator2>
+template<typename InputIterator1, typename InputIterator2>
inline bool
equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- __gnu_parallel::sequential_tag)
+ __gnu_parallel::sequential_tag)
{ return _GLIBCXX_STD_P::equal(begin1, end1, begin2); }
// Sequential fallback
- template<typename InputIterator1, typename InputIterator2, typename Predicate>
+template<typename InputIterator1, typename InputIterator2, typename Predicate>
inline bool
equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- Predicate pred, __gnu_parallel::sequential_tag)
+ Predicate pred, __gnu_parallel::sequential_tag)
{ return _GLIBCXX_STD_P::equal(begin1, end1, begin2, pred); }
// Public interface
- template<typename InputIterator1, typename InputIterator2>
+template<typename InputIterator1, typename InputIterator2>
inline bool
equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2)
{ return mismatch(begin1, end1, begin2).first == end1; }
// Public interface
- template<typename InputIterator1, typename InputIterator2, typename Predicate>
+template<typename InputIterator1, typename InputIterator2, typename Predicate>
inline bool
equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- Predicate pred)
+ Predicate pred)
{ return mismatch(begin1, end1, begin2, pred).first == end1; }
// Sequential fallback
- template<typename InputIterator1, typename InputIterator2>
+template<typename InputIterator1, typename InputIterator2>
inline bool
lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- __gnu_parallel::sequential_tag)
+ InputIterator2 begin2, InputIterator2 end2,
+ __gnu_parallel::sequential_tag)
{
return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, begin2, end2);
}
// Sequential fallback
- template<typename InputIterator1, typename InputIterator2, typename Predicate>
+template<typename InputIterator1, typename InputIterator2, typename Predicate>
inline bool
lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- Predicate pred, __gnu_parallel::sequential_tag)
+ InputIterator2 begin2, InputIterator2 end2,
+ Predicate pred, __gnu_parallel::sequential_tag)
{
return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
- begin2, end2, pred);
+ begin2, end2, pred);
}
// Sequential fallback for input iterator case
- template<typename InputIterator1, typename InputIterator2, typename Predicate, typename IteratorTag1, typename IteratorTag2>
+template<typename InputIterator1, typename InputIterator2, typename Predicate,
+ typename IteratorTag1, typename IteratorTag2>
inline bool
lexicographical_compare_switch(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- Predicate pred, IteratorTag1, IteratorTag2)
+ InputIterator2 begin2, InputIterator2 end2,
+ Predicate pred, IteratorTag1, IteratorTag2)
{
return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
- begin2, end2, pred);
+ begin2, end2, pred);
}
// Parallel lexicographical_compare for random access iterators
// Limitation: Both valuetypes must be the same
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Predicate>
+template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Predicate>
bool
lexicographical_compare_switch(RandomAccessIterator1 begin1,
- RandomAccessIterator1 end1,
- RandomAccessIterator2 begin2,
- RandomAccessIterator2 end2, Predicate pred,
- random_access_iterator_tag,
- random_access_iterator_tag)
+ RandomAccessIterator1 end1,
+ RandomAccessIterator2 begin2,
+ RandomAccessIterator2 end2, Predicate pred,
+ random_access_iterator_tag,
+ random_access_iterator_tag)
{
if (_GLIBCXX_PARALLEL_CONDITION(true))
{
- typedef iterator_traits<RandomAccessIterator1> traits1_type;
- typedef typename traits1_type::value_type value1_type;
+ typedef iterator_traits<RandomAccessIterator1> traits1_type;
+ typedef typename traits1_type::value_type value1_type;
- typedef iterator_traits<RandomAccessIterator2> traits2_type;
- typedef typename traits2_type::value_type value2_type;
-
- typedef __gnu_parallel::equal_from_less<Predicate, value1_type, value2_type> equal_type;
+ typedef iterator_traits<RandomAccessIterator2> traits2_type;
+ typedef typename traits2_type::value_type value2_type;
- // Longer sequence in first place.
- if ((end1 - begin1) < (end2 - begin2))
- {
- typedef pair<RandomAccessIterator1, RandomAccessIterator2> pair_type;
- pair_type mm = mismatch_switch(begin1, end1, begin2,
- equal_type(pred),
- random_access_iterator_tag(),
- random_access_iterator_tag());
+ typedef __gnu_parallel::equal_from_less
+ <Predicate, value1_type, value2_type> equal_type;
- // Less because shorter.
- const bool lbs = mm.first == end1;
+ // Longer sequence in first place.
+ if ((end1 - begin1) < (end2 - begin2))
+ {
+ typedef pair<RandomAccessIterator1, RandomAccessIterator2>
+ pair_type;
+ pair_type mm = mismatch_switch(begin1, end1, begin2,
+ equal_type(pred),
+ random_access_iterator_tag(),
+ random_access_iterator_tag());
- // Less because differing elements less.
- const bool lbdel = pred(*mm.first, *mm.second);
+ // Less because shorter.
+ const bool lbs = mm.first == end1;
- return lbs || lbdel;
- }
- else
- {
- typedef pair<RandomAccessIterator2, RandomAccessIterator1> pair_type;
- pair_type mm = mismatch_switch(begin2, end2, begin1,
- equal_type(pred),
- random_access_iterator_tag(),
- random_access_iterator_tag());
+ // Less because differing elements less.
+ const bool lbdel = pred(*mm.first, *mm.second);
- // Less because shorter.
- const bool lbs = mm.first != end2;
+ return lbs || lbdel;
+ }
+ else
+ {
+ typedef pair<RandomAccessIterator2, RandomAccessIterator1>
+ pair_type;
+ pair_type mm = mismatch_switch(begin2, end2, begin1,
+ equal_type(pred),
+ random_access_iterator_tag(),
+ random_access_iterator_tag());
- // Less because differing element less.
- const bool lbdel = pred(*mm.second, *mm.first);
+ // Less because shorter.
+ const bool lbs = mm.first != end2;
- return lbs && lbdel;
- }
+ // Less because differing element less.
+ const bool lbdel = pred(*mm.second, *mm.first);
+
+ return lbs && lbdel;
+ }
}
else
- return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, begin2, end2, pred);
+ return _GLIBCXX_STD_P::lexicographical_compare
+ (begin1, end1, begin2, end2, pred);
}
// Public interface
- template<typename InputIterator1, typename InputIterator2>
+template<typename InputIterator1, typename InputIterator2>
inline bool
- lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2)
+ lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2)
{
typedef iterator_traits<InputIterator1> traits1_type;
typedef typename traits1_type::value_type value1_type;
@@ -259,24 +270,26 @@
typedef __gnu_parallel::less<value1_type, value2_type> less_type;
return lexicographical_compare_switch(begin1, end1, begin2, end2,
- less_type(), iterator1_category(),
- iterator2_category());
+ less_type(), iterator1_category(),
+ iterator2_category());
}
// Public interface
- template<typename InputIterator1, typename InputIterator2, typename Predicate>
+template<typename InputIterator1, typename InputIterator2, typename Predicate>
inline bool
- lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, Predicate pred)
+ lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ Predicate pred)
{
typedef iterator_traits<InputIterator1> traits1_type;
typedef typename traits1_type::iterator_category iterator1_category;
-
+
typedef iterator_traits<InputIterator2> traits2_type;
typedef typename traits2_type::iterator_category iterator2_category;
return lexicographical_compare_switch(begin1, end1, begin2, end2, pred,
- iterator1_category(),
- iterator2_category());
+ iterator1_category(),
+ iterator2_category());
}
} // end namespace
} // end namespace
Index: include/parallel/algo.h
===================================================================
--- include/parallel/algo.h (revision 130490)
+++ include/parallel/algo.h (working copy)
@@ -29,7 +29,7 @@
// Public License.
/** @file parallel/algo.h
- * @brief Parallel STL function calls corresponding to the stl_algo.h header.
+ * @brief Parallel STL function calls corresponding to stl_algo.h.
*
* The functions defined here mainly do case switches and
* call the actual parallelized versions in other files.
@@ -68,51 +68,56 @@
{
namespace __parallel
{
- // Sequential fallback
- template<typename InputIterator, typename Function>
+// Sequential fallback
+template<typename InputIterator, typename Function>
inline Function
- for_each(InputIterator begin, InputIterator end, Function f,
- __gnu_parallel::sequential_tag)
+ for_each(InputIterator begin, InputIterator end, Function f,
+ __gnu_parallel::sequential_tag)
{ return _GLIBCXX_STD_P::for_each(begin, end, f); }
- // Sequential fallback for input iterator case
- template<typename InputIterator, typename Function, typename IteratorTag>
+// Sequential fallback for input iterator case
+template<typename InputIterator, typename Function, typename IteratorTag>
Function
- for_each_switch(InputIterator begin, InputIterator end, Function f,
- IteratorTag)
+ for_each_switch(InputIterator begin, InputIterator end, Function f,
+ IteratorTag)
{ return for_each(begin, end, f, __gnu_parallel::sequential_tag()); }
- // Parallel algorithm for random access iterators
- template<typename RandomAccessIterator, typename Function>
+// 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::for_each_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
+ if (_GLIBCXX_PARALLEL_CONDITION(
+ static_cast<__gnu_parallel::sequence_index_t>(end - begin)
+ >= __gnu_parallel::Settings::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);
+ bool dummy;
+ __gnu_parallel::for_each_selector<RandomAccessIterator> functionality;
+ return __gnu_parallel::for_each_template_random_access
+ (begin, end, f, functionality, __gnu_parallel::dummy_reduct(),
+ true, dummy, -1, parallelism_tag);
}
else
return for_each(begin, end, f, __gnu_parallel::sequential_tag());
}
- // Public interface
- template<typename Iterator, typename Function>
+// 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>
+template<typename Iterator, typename Function>
inline Function
for_each(Iterator begin, Iterator end, Function f)
{
@@ -122,38 +127,42 @@
}
- // Sequential fallback
- template<typename InputIterator, typename T>
+// Sequential fallback
+template<typename InputIterator, typename T>
inline InputIterator
find(InputIterator begin, InputIterator end, const T& val,
__gnu_parallel::sequential_tag)
{ return _GLIBCXX_STD_P::find(begin, end, val); }
- // Sequential fallback for input iterator case
- template<typename InputIterator, typename T, typename IteratorTag>
+// 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)
+ find_switch(InputIterator begin, InputIterator end, const T& val,
+ IteratorTag)
{ return _GLIBCXX_STD_P::find(begin, end, val); }
- // Parallel find for random access iterators
- template<typename RandomAccessIterator, typename T>
+// 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)
+ find_switch(RandomAccessIterator begin, RandomAccessIterator end,
+ const T& val, random_access_iterator_tag)
{
typedef iterator_traits<RandomAccessIterator> traits_type;
typedef typename traits_type::value_type value_type;
if (_GLIBCXX_PARALLEL_CONDITION(true))
{
- binder2nd<__gnu_parallel::equal_to<value_type, 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);
}
- // Public interface
- template<typename InputIterator, typename T>
+// Public interface
+template<typename InputIterator, typename T>
inline InputIterator
find(InputIterator begin, InputIterator end, const T& val)
{
@@ -162,35 +171,35 @@
return find_switch(begin, end, val, iterator_category());
}
- // Sequential fallback
- template<typename InputIterator, typename Predicate>
+// Sequential fallback
+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>
+// 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>
+// 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;
+ __gnu_parallel::find_if_selector()).first;
else
return _GLIBCXX_STD_P::find_if(begin, end, pred);
}
- // Public interface
- template<typename InputIterator, typename Predicate>
+// Public interface
+template<typename InputIterator, typename Predicate>
inline InputIterator
find_if (InputIterator begin, InputIterator end, Predicate pred)
{
@@ -199,63 +208,70 @@
return find_if_switch(begin, end, pred, iterator_category());
}
- // Sequential fallback
- template<typename InputIterator, typename ForwardIterator>
+// Sequential fallback
+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>
+// Sequential fallback
+template<typename InputIterator, typename ForwardIterator,
+ typename BinaryPredicate>
inline InputIterator
find_first_of(InputIterator begin1, InputIterator end1,
- ForwardIterator begin2, ForwardIterator end2,
- BinaryPredicate comp, __gnu_parallel::sequential_tag)
+ 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>
+// Sequential fallback for input iterator type
+template<typename InputIterator, typename ForwardIterator,
+ typename IteratorTag1, typename IteratorTag2>
inline InputIterator
find_first_of_switch(InputIterator begin1, InputIterator end1,
- ForwardIterator begin2, ForwardIterator end2,
- IteratorTag1, IteratorTag2)
+ 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>
+// Parallel algorithm for random access iterators
+template<typename RandomAccessIterator, typename ForwardIterator,
+ typename BinaryPredicate, typename IteratorTag>
inline RandomAccessIterator
find_first_of_switch(RandomAccessIterator begin1, RandomAccessIterator end1,
- ForwardIterator begin2, ForwardIterator end2,
- BinaryPredicate comp, random_access_iterator_tag,
- IteratorTag)
+ 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;
+ return __gnu_parallel::find_template(begin1, end1, begin1, comp,
+ __gnu_parallel::find_first_of_selector<ForwardIterator>(begin2, end2))
+ .first;
}
- // Sequential fallback for input iterator type
- template<typename InputIterator, typename ForwardIterator, typename BinaryPredicate, typename IteratorTag1, typename IteratorTag2>
+// Sequential fallback for input iterator type
+template<typename InputIterator, typename ForwardIterator,
+ typename BinaryPredicate,
+ typename IteratorTag1, typename IteratorTag2>
inline
InputIterator
find_first_of_switch(InputIterator begin1, InputIterator end1,
- ForwardIterator begin2, ForwardIterator end2,
- BinaryPredicate comp, IteratorTag1, IteratorTag2)
+ 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>
+// Public interface
+template<typename InputIterator, typename ForwardIterator,
+ 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;
@@ -263,14 +279,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>
+// Public interface, insert default comparator
+template<typename InputIterator, typename ForwardIterator>
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;
@@ -278,46 +294,50 @@
typedef typename iteratorf_traits::value_type valuef_type;
return find_first_of(begin1, end1, begin2, end2,
- __gnu_parallel::equal_to<valuei_type, valuef_type>());
+ __gnu_parallel::equal_to<valuei_type, valuef_type>());
}
- // Sequential fallback
- template<typename InputIterator, typename OutputIterator>
+// 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>
+// Sequential fallback
+template<typename InputIterator, typename OutputIterator, typename Predicate>
inline OutputIterator
unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
- Predicate pred, __gnu_parallel::sequential_tag)
+ 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>
+// Sequential fallback for input iterator case
+template<typename InputIterator, typename OutputIterator, typename Predicate,
+ typename IteratorTag1, typename IteratorTag2>
inline OutputIterator
unique_copy_switch(InputIterator begin, InputIterator last,
- OutputIterator out, Predicate pred,
- IteratorTag1, IteratorTag2)
+ 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>
+// Parallel unique_copy for random access iterators
+template<typename RandomAccessIterator, typename RandomAccessOutputIterator,
+ typename Predicate>
RandomAccessOutputIterator
unique_copy_switch(RandomAccessIterator begin, RandomAccessIterator last,
- RandomAccessOutputIterator out, Predicate pred,
- random_access_iterator_tag, random_access_iterator_tag)
+ 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::unique_copy_minimal_n))
+ if (_GLIBCXX_PARALLEL_CONDITION(
+ static_cast<__gnu_parallel::sequence_index_t>(last - begin)
+ > __gnu_parallel::Settings::unique_copy_minimal_n))
return __gnu_parallel::parallel_unique_copy(begin, last, out, pred);
else
return _GLIBCXX_STD_P::unique_copy(begin, last, out, pred);
}
- // Public interface
- template<typename InputIterator, typename OutputIterator>
+// Public interface
+template<typename InputIterator, typename OutputIterator>
inline OutputIterator
unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out)
{
@@ -328,14 +348,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>
+// 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;
@@ -343,58 +363,70 @@
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>
+// Sequential fallback
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator>
inline OutputIterator
set_union(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator out, __gnu_parallel::sequential_tag)
+ 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>
+// Sequential fallback
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename Predicate>
inline OutputIterator
set_union(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator out, Predicate pred, __gnu_parallel::sequential_tag)
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator out, Predicate pred,
+ __gnu_parallel::sequential_tag)
{ return _GLIBCXX_STD_P::set_union(begin1, end1, begin2, end2, out, pred); }
- // Sequential fallback for input iterator case
- template<typename InputIterator1, typename InputIterator2, typename Predicate,
- typename OutputIterator, typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
+// Sequential fallback for input iterator case
+template<typename InputIterator1, typename InputIterator2, typename Predicate,
+ typename OutputIterator,
+ typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
inline OutputIterator
set_union_switch(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator result, Predicate pred, IteratorTag1,
- IteratorTag2, IteratorTag3)
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator result, Predicate pred, IteratorTag1,
+ IteratorTag2, IteratorTag3)
{
- return _GLIBCXX_STD_P::set_union(begin1, end1, begin2, end2, result, pred);
+ return _GLIBCXX_STD_P::set_union(begin1, end1, begin2, end2,
+ result, pred);
}
- // Parallel set_union for random access iterators
- template<typename RandomAccessIterator1, typename RandomAccessIterator2,
- typename OutputRandomAccessIterator, typename Predicate>
+// Parallel set_union for random access iterators
+template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename OutputRandomAccessIterator, typename Predicate>
OutputRandomAccessIterator
set_union_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
- RandomAccessIterator2 begin2, RandomAccessIterator2 end2,
- OutputRandomAccessIterator result, Predicate pred,
- random_access_iterator_tag, random_access_iterator_tag,
- random_access_iterator_tag)
+ 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::set_union_minimal_n || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2) >= __gnu_parallel::Settings::set_union_minimal_n))
- return __gnu_parallel::parallel_set_union(begin1, end1, begin2, end2, result, pred);
+ if (_GLIBCXX_PARALLEL_CONDITION(
+ static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
+ >= __gnu_parallel::Settings::set_union_minimal_n
+ || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
+ >= __gnu_parallel::Settings::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>
+// Public interface
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator>
inline OutputIterator
set_union(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- InputIterator2 end2, OutputIterator out)
+ InputIterator2 end2, OutputIterator out)
{
typedef std::iterator_traits<InputIterator1> iteratori1_traits;
typedef std::iterator_traits<InputIterator2> iteratori2_traits;
@@ -406,16 +438,17 @@
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>
+// Public interface
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename Predicate>
inline OutputIterator
set_union(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- InputIterator2 end2, OutputIterator out, Predicate pred)
+ InputIterator2 end2, OutputIterator out, Predicate pred)
{
typedef std::iterator_traits<InputIterator1> iteratori1_traits;
typedef std::iterator_traits<InputIterator2> iteratori2_traits;
@@ -425,65 +458,81 @@
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>
+// Sequential fallback.
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator>
inline OutputIterator
set_intersection(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator out, __gnu_parallel::sequential_tag)
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator out, __gnu_parallel::sequential_tag)
{
return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, end2, out);
}
- // Sequential fallback.
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Predicate>
+// Sequential fallback.
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename Predicate>
inline OutputIterator
set_intersection(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator out, Predicate pred,
- __gnu_parallel::sequential_tag)
+ 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>
+// Sequential fallback for input iterator case
+template<typename InputIterator1, typename InputIterator2, typename Predicate,
+ typename OutputIterator,
+ typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
inline OutputIterator
set_intersection_switch(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator result, Predicate pred,
- IteratorTag1, IteratorTag2, IteratorTag3)
+ 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>
+// Parallel set_intersection for random access iterators
+template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename OutputRandomAccessIterator, typename Predicate>
OutputRandomAccessIterator
- set_intersection_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, RandomAccessIterator2 end2, OutputRandomAccessIterator result, Predicate pred, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag)
+ set_intersection_switch(RandomAccessIterator1 begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator2 begin2,
+ RandomAccessIterator2 end2,
+ OutputRandomAccessIterator result,
+ Predicate pred,
+ random_access_iterator_tag,
+ random_access_iterator_tag,
+ random_access_iterator_tag)
{
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1) >= __gnu_parallel::Settings::set_union_minimal_n || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2) >= __gnu_parallel::Settings::set_union_minimal_n))
+ if (_GLIBCXX_PARALLEL_CONDITION(
+ static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
+ >= __gnu_parallel::Settings::set_union_minimal_n
+ || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
+ >= __gnu_parallel::Settings::set_union_minimal_n))
return __gnu_parallel::parallel_set_intersection(begin1, end1, begin2,
- end2, result, pred);
+ end2, result, pred);
else
return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2,
- end2, result, pred);
+ end2, result, pred);
}
- // Public interface
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
+// Public interface
+template<typename InputIterator1, typename InputIterator2,
+ 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;
@@ -495,15 +544,17 @@
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>
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename Predicate>
inline OutputIterator
- set_intersection(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- InputIterator2 end2, OutputIterator out, Predicate pred)
+ set_intersection(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator out, Predicate pred)
{
typedef std::iterator_traits<InputIterator1> iteratori1_traits;
typedef std::iterator_traits<InputIterator2> iteratori2_traits;
@@ -513,59 +564,83 @@
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>
+// Sequential fallback
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator>
inline OutputIterator
set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator out, __gnu_parallel::sequential_tag)
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator out, __gnu_parallel::sequential_tag)
{
return _GLIBCXX_STD_P::set_symmetric_difference(begin1,end1, begin2,
- end2, out);
+ end2, out);
}
- // Sequential fallback
- template<typename InputIterator1, typename InputIterator2,
- typename OutputIterator, typename Predicate>
+// Sequential fallback
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename Predicate>
inline OutputIterator
set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator out, Predicate pred, __gnu_parallel::sequential_tag)
+ 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>
+// Sequential fallback for input iterator case
+template<typename InputIterator1, typename InputIterator2, typename Predicate,
+ typename OutputIterator,
+ typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
inline OutputIterator
- set_symmetric_difference_switch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator result, Predicate pred, IteratorTag1, IteratorTag2, IteratorTag3)
+ set_symmetric_difference_switch(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator result, Predicate pred,
+ IteratorTag1, IteratorTag2, IteratorTag3)
{
- return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1, begin2, end2,
- result, pred);
+ return _GLIBCXX_STD_P::set_symmetric_difference(
+ begin1, end1, begin2, end2, result, pred);
}
- // Parallel set_symmetric_difference for random access iterators
- template<typename RandomAccessIterator1, typename RandomAccessIterator2,
- typename OutputRandomAccessIterator, typename Predicate>
+// Parallel set_symmetric_difference for random access iterators
+template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename OutputRandomAccessIterator, typename Predicate>
OutputRandomAccessIterator
- set_symmetric_difference_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, RandomAccessIterator2 end2, OutputRandomAccessIterator result, Predicate pred, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag)
+ set_symmetric_difference_switch(RandomAccessIterator1 begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator2 begin2,
+ RandomAccessIterator2 end2,
+ OutputRandomAccessIterator result,
+ Predicate pred,
+ random_access_iterator_tag,
+ random_access_iterator_tag,
+ random_access_iterator_tag)
{
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1) >= __gnu_parallel::Settings::set_symmetric_difference_minimal_n || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2) >= __gnu_parallel::Settings::set_symmetric_difference_minimal_n))
- return __gnu_parallel::parallel_set_symmetric_difference(begin1, end1, begin2, end2, result, pred);
+ if (_GLIBCXX_PARALLEL_CONDITION(
+ static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
+ >= __gnu_parallel::Settings::set_symmetric_difference_minimal_n
+ || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
+ >= __gnu_parallel::Settings::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>
+// Public interface.
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator>
inline OutputIterator
- set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator out)
+ set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator out)
{
typedef std::iterator_traits<InputIterator1> iteratori1_traits;
typedef std::iterator_traits<InputIterator2> iteratori2_traits;
@@ -576,16 +651,20 @@
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());
+ return set_symmetric_difference_switch(
+ begin1, end1, begin2, end2, out,
+ __gnu_parallel::less<value1_type, value2_type>(),
+ iteratori1_category(), iteratori2_category(),
+ iteratoro_category());
}
- // Public interface.
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Predicate>
+// Public interface.
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename Predicate>
inline OutputIterator
- set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator out, Predicate pred)
+ set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator out, Predicate pred)
{
typedef std::iterator_traits<InputIterator1> iteratori1_traits;
typedef std::iterator_traits<InputIterator2> iteratori2_traits;
@@ -594,60 +673,80 @@
typedef typename iteratori2_traits::iterator_category iteratori2_category;
typedef typename iteratoro_traits::iterator_category iteratoro_category;
- return set_symmetric_difference_switch(begin1, end1, begin2, end2, out,
- pred, iteratori1_category(),
- iteratori2_category(), iteratoro_category());
+ return set_symmetric_difference_switch(
+ begin1, end1, begin2, end2, out, pred, iteratori1_category(),
+ iteratori2_category(), iteratoro_category());
}
- // Sequential fallback.
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
+// Sequential fallback.
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator>
inline OutputIterator
set_difference(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator out, __gnu_parallel::sequential_tag)
+ 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>
+// Sequential fallback.
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename Predicate>
inline OutputIterator
set_difference(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator out, Predicate pred,
- __gnu_parallel::sequential_tag)
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator out, Predicate pred,
+ __gnu_parallel::sequential_tag)
{
- return _GLIBCXX_STD_P::set_difference(begin1, end1, begin2, end2, out, pred);
+ return _GLIBCXX_STD_P::set_difference(
+ begin1, end1, begin2, end2, out, pred);
}
- // Sequential fallback for input iterator case.
- template<typename InputIterator1, typename InputIterator2, typename Predicate,
- typename OutputIterator, typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
+// Sequential fallback for input iterator case.
+template<typename InputIterator1, typename InputIterator2, typename Predicate,
+ typename OutputIterator, typename IteratorTag1,
+ typename IteratorTag2, typename IteratorTag3>
inline OutputIterator
set_difference_switch(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator result, Predicate pred,
- IteratorTag1, IteratorTag2, IteratorTag3)
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator result, Predicate pred,
+ IteratorTag1, IteratorTag2, IteratorTag3)
{
- return _GLIBCXX_STD_P::set_difference(begin1, end1, begin2, end2, result, pred);
+ return _GLIBCXX_STD_P::set_difference(
+ begin1, end1, begin2, end2, result, pred);
}
- // Parallel set_difference for random access iterators
- template<typename RandomAccessIterator1, typename RandomAccessIterator2,
- typename OutputRandomAccessIterator, typename Predicate>
+// Parallel set_difference for random access iterators
+template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename OutputRandomAccessIterator, typename Predicate>
OutputRandomAccessIterator
- set_difference_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, RandomAccessIterator2 end2, OutputRandomAccessIterator result, Predicate pred, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag)
+ set_difference_switch(RandomAccessIterator1 begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator2 begin2,
+ RandomAccessIterator2 end2,
+ OutputRandomAccessIterator result,
+ Predicate pred,
+ random_access_iterator_tag,
+ random_access_iterator_tag,
+ random_access_iterator_tag)
{
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1) >= __gnu_parallel::Settings::set_difference_minimal_n || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2) >= __gnu_parallel::Settings::set_difference_minimal_n))
- return __gnu_parallel::parallel_set_difference(begin1, end1, begin2, end2, result, pred);
+ if (_GLIBCXX_PARALLEL_CONDITION(
+ static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
+ >= __gnu_parallel::Settings::set_difference_minimal_n
+ || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
+ >= __gnu_parallel::Settings::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>
+// Public interface
+template<typename InputIterator1, typename InputIterator2,
+ 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;
@@ -659,17 +758,18 @@
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>
+// Public interface
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename Predicate>
inline OutputIterator
set_difference(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator out, Predicate pred)
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator out, Predicate pred)
{
typedef std::iterator_traits<InputIterator1> iteratori1_traits;
typedef std::iterator_traits<InputIterator2> iteratori2_traits;
@@ -679,53 +779,58 @@
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>
+// 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>
+// 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>
+// 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());
}
- // Sequential fallback for input iterator case
- template<typename ForwardIterator, typename IteratorTag>
+// Sequential fallback for input iterator case
+template<typename ForwardIterator, typename IteratorTag>
inline ForwardIterator
- adjacent_find_switch(ForwardIterator begin, ForwardIterator end, IteratorTag)
+ adjacent_find_switch(ForwardIterator begin, ForwardIterator end,
+ IteratorTag)
{ return adjacent_find(begin, end, __gnu_parallel::sequential_tag()); }
- // Public interface
- template<typename ForwardIterator>
+// Public interface
+template<typename ForwardIterator>
inline ForwardIterator
adjacent_find(ForwardIterator begin, ForwardIterator end)
{
@@ -734,88 +839,95 @@
return adjacent_find_switch(begin, end, iterator_category());
}
- // Sequential fallback for input iterator case
- template<typename ForwardIterator, typename BinaryPredicate, typename IteratorTag>
+// Sequential fallback for input iterator case
+template<typename ForwardIterator, typename BinaryPredicate,
+ typename IteratorTag>
inline ForwardIterator
adjacent_find_switch(ForwardIterator begin, ForwardIterator end,
- BinaryPredicate pred, IteratorTag)
+ BinaryPredicate pred, IteratorTag)
{ return adjacent_find(begin, end, pred, __gnu_parallel::sequential_tag()); }
- // Parallel algorithm for random access iterators
- template<typename RandomAccessIterator, typename BinaryPredicate>
+// 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;
+ __gnu_parallel::adjacent_find_selector()).first;
else
return adjacent_find(begin, end, pred, __gnu_parallel::sequential_tag());
}
- // Public interface
- template<typename ForwardIterator, typename BinaryPredicate>
+// 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;
return adjacent_find_switch(begin, end, pred, iterator_category());
}
- // Sequential fallback
- template<typename InputIterator, typename T>
+// Sequential fallback
+template<typename InputIterator, typename T>
inline typename iterator_traits<InputIterator>::difference_type
count(InputIterator begin, InputIterator end, const T& value,
- __gnu_parallel::sequential_tag)
+ __gnu_parallel::sequential_tag)
{ return _GLIBCXX_STD_P::count(begin, end, value); }
- // Parallel code for random access iterators
- template<typename RandomAccessIterator, typename T>
+// 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;
typedef typename traits_type::difference_type difference_type;
typedef __gnu_parallel::sequence_index_t sequence_index_t;
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<sequence_index_t>(end - begin) >= __gnu_parallel::Settings::count_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
+ if (_GLIBCXX_PARALLEL_CONDITION(
+ static_cast<sequence_index_t>(end - begin)
+ >= __gnu_parallel::Settings::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;
+ __gnu_parallel::count_selector<RandomAccessIterator, difference_type>
+ functionality;
+ difference_type res = 0;
+ __gnu_parallel::for_each_template_random_access(
+ begin, end, value, functionality,
+ std::plus<sequence_index_t>(), res, res, -1, parallelism_tag);
+ return res;
}
else
return count(begin, end, value, __gnu_parallel::sequential_tag());
}
- // Sequential fallback for input iterator case.
- template<typename InputIterator, typename T, typename IteratorTag>
+// Sequential fallback for input iterator case.
+template<typename InputIterator, typename T, typename IteratorTag>
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>
+// 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>
+template<typename InputIterator, typename T>
inline typename iterator_traits<InputIterator>::difference_type
count(InputIterator begin, InputIterator end, const T& value)
{
@@ -825,57 +937,63 @@
}
- // Sequential fallback.
- template<typename InputIterator, typename Predicate>
+// Sequential fallback.
+template<typename InputIterator, typename Predicate>
inline typename iterator_traits<InputIterator>::difference_type
count_if(InputIterator begin, InputIterator end, Predicate pred,
- __gnu_parallel::sequential_tag)
+ __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>
+// 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;
typedef typename traits_type::difference_type difference_type;
typedef __gnu_parallel::sequence_index_t sequence_index_t;
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<sequence_index_t>(end - begin) >= __gnu_parallel::Settings::count_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
+ if (_GLIBCXX_PARALLEL_CONDITION(
+ static_cast<sequence_index_t>(end - begin)
+ >= __gnu_parallel::Settings::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;
+ difference_type res = 0;
+ __gnu_parallel::count_if_selector<
+ RandomAccessIterator, difference_type> functionality;
+ __gnu_parallel::for_each_template_random_access(
+ begin, end, pred, functionality,
+ std::plus<sequence_index_t>(), res, res, -1, parallelism_tag);
+ return res;
}
else
return count_if(begin, end, pred, __gnu_parallel::sequential_tag());
}
- // Sequential fallback for input iterator case.
- template<typename InputIterator, typename Predicate, typename IteratorTag>
+// Sequential fallback for input iterator case.
+template<typename InputIterator, typename Predicate, typename IteratorTag>
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>
+// 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>
+template<typename InputIterator, typename Predicate>
inline typename iterator_traits<InputIterator>::difference_type
count_if(InputIterator begin, InputIterator end, Predicate pred)
{
@@ -885,18 +1003,22 @@
}
- // Sequential fallback.
- template<typename ForwardIterator1, typename ForwardIterator2>
+// Sequential fallback.
+template<typename ForwardIterator1, typename ForwardIterator2>
inline ForwardIterator1
- search(ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2, __gnu_parallel::sequential_tag)
+ search(ForwardIterator1 begin1, ForwardIterator1 end1,
+ ForwardIterator2 begin2, ForwardIterator2 end2,
+ __gnu_parallel::sequential_tag)
{
return _GLIBCXX_STD_P::search(begin1, end1, begin2, end2);
}
- // Parallel algorithm for random access iterator
- template<typename RandomAccessIterator1, typename RandomAccessIterator2>
+// 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)
+ search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
+ RandomAccessIterator2 begin2, RandomAccessIterator2 end2,
+ random_access_iterator_tag, random_access_iterator_tag)
{
typedef std::iterator_traits<RandomAccessIterator1> iterator1_traits;
typedef typename iterator1_traits::value_type value1_type;
@@ -904,170 +1026,230 @@
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>
+// Sequential fallback for input iterator case
+template<typename ForwardIterator1, typename ForwardIterator2,
+ typename IteratorTag1, typename IteratorTag2>
inline ForwardIterator1
- search_switch(ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2, IteratorTag1, IteratorTag2)
+ search_switch(ForwardIterator1 begin1, ForwardIterator1 end1,
+ ForwardIterator2 begin2, ForwardIterator2 end2,
+ IteratorTag1, IteratorTag2)
{
- return search(begin1, end1, begin2, end2, __gnu_parallel::sequential_tag());
+ return search(begin1, end1, begin2, end2,
+ __gnu_parallel::sequential_tag());
}
- // Public interface.
- template<typename ForwardIterator1, typename ForwardIterator2>
+// Public interface.
+template<typename ForwardIterator1, typename ForwardIterator2>
inline ForwardIterator1
- search(ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2)
+ search(ForwardIterator1 begin1, ForwardIterator1 end1,
+ ForwardIterator2 begin2, ForwardIterator2 end2)
{
typedef std::iterator_traits<ForwardIterator1> iterator1_traits;
typedef typename iterator1_traits::iterator_category iterator1_category;
typedef std::iterator_traits<ForwardIterator2> iterator2_traits;
typedef typename iterator2_traits::iterator_category iterator2_category;
- return search_switch(begin1, end1, begin2, end2, iterator1_category(), iterator2_category());
+ return search_switch(begin1, end1, begin2, end2,
+ iterator1_category(), iterator2_category());
}
- // Public interface.
- template<typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
+// Public interface.
+template<typename ForwardIterator1, typename ForwardIterator2,
+ typename BinaryPredicate>
inline ForwardIterator1
- search(ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2, BinaryPredicate pred, __gnu_parallel::sequential_tag)
+ search(ForwardIterator1 begin1, ForwardIterator1 end1,
+ ForwardIterator2 begin2, ForwardIterator2 end2,
+ BinaryPredicate pred, __gnu_parallel::sequential_tag)
{
return _GLIBCXX_STD_P::search(begin1, end1, begin2, end2, pred);
}
- // Parallel algorithm for random access iterator.
- template<typename RandomAccessIterator1, typename RandomAccessIterator2,
- typename BinaryPredicate>
+// Parallel algorithm for random access iterator.
+template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename BinaryPredicate>
RandomAccessIterator1
search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
- RandomAccessIterator2 begin2, RandomAccessIterator2 end2, BinaryPredicate pred, random_access_iterator_tag, random_access_iterator_tag)
+ 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>
+// Sequential fallback for input iterator case
+template<typename ForwardIterator1, typename ForwardIterator2,
+ typename BinaryPredicate,
+ typename IteratorTag1, typename IteratorTag2>
inline ForwardIterator1
search_switch(ForwardIterator1 begin1, ForwardIterator1 end1,
- ForwardIterator2 begin2, ForwardIterator2 end2, BinaryPredicate pred, IteratorTag1, IteratorTag2)
+ ForwardIterator2 begin2, ForwardIterator2 end2,
+ BinaryPredicate pred, IteratorTag1, IteratorTag2)
{
- return search(begin1, end1, begin2, end2, pred, __gnu_parallel::sequential_tag());
+ return search(begin1, end1, begin2, end2, pred,
+ __gnu_parallel::sequential_tag());
}
- // Public interface
- template<typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
+// Public interface
+template<typename ForwardIterator1, typename ForwardIterator2,
+ typename BinaryPredicate>
inline ForwardIterator1
- search(ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2, BinaryPredicate pred)
+ search(ForwardIterator1 begin1, ForwardIterator1 end1,
+ ForwardIterator2 begin2, ForwardIterator2 end2,
+ BinaryPredicate pred)
{
typedef std::iterator_traits<ForwardIterator1> iterator1_traits;
typedef typename iterator1_traits::iterator_category iterator1_category;
typedef std::iterator_traits<ForwardIterator2> iterator2_traits;
typedef typename iterator2_traits::iterator_category iterator2_category;
- return search_switch(begin1, end1, begin2, end2, pred, iterator1_category(), iterator2_category());
+ return search_switch(begin1, end1, begin2, end2, pred,
+ iterator1_category(), iterator2_category());
}
- // Sequential fallback
- template<typename ForwardIterator, typename Integer, typename T>
+// 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)
+ search_n(ForwardIterator begin, ForwardIterator end, Integer count,
+ const T& val, __gnu_parallel::sequential_tag)
{ return _GLIBCXX_STD_P::search_n(begin, end, count, val); }
- // Sequential fallback
- template<typename ForwardIterator, typename Integer, typename T, typename BinaryPredicate>
+// Sequential fallback
+template<typename ForwardIterator, typename Integer, typename T,
+ typename BinaryPredicate>
inline ForwardIterator
- search_n(ForwardIterator begin, ForwardIterator end, Integer count, const T& val, BinaryPredicate binary_pred, __gnu_parallel::sequential_tag)
+ search_n(ForwardIterator begin, ForwardIterator end, Integer count,
+ const T& val, BinaryPredicate binary_pred,
+ __gnu_parallel::sequential_tag)
{
return _GLIBCXX_STD_P::search_n(begin, end, count, val, binary_pred);
}
- // Public interface.
- template<typename ForwardIterator, typename Integer, typename T>
+// Public interface.
+template<typename ForwardIterator, typename Integer, typename T>
inline ForwardIterator
- search_n(ForwardIterator begin, ForwardIterator end, Integer count, const T& val)
+ search_n(ForwardIterator begin, ForwardIterator end,
+ Integer count, const T& val)
{
typedef typename iterator_traits<ForwardIterator>::value_type value_type;
- return search_n(begin, end, count, val, __gnu_parallel::equal_to<value_type, T>());
+ return search_n(begin, end, count, val,
+ __gnu_parallel::equal_to<value_type, T>());
}
- // Parallel algorithm for random access iterators.
- template<typename RandomAccessIterator, typename Integer, typename T, typename BinaryPredicate>
+// Parallel algorithm for random access iterators.
+template<typename RandomAccessIterator, typename Integer, typename T,
+ typename BinaryPredicate>
RandomAccessIterator
- search_n_switch(RandomAccessIterator begin, RandomAccessIterator end, Integer count, const T& val, BinaryPredicate binary_pred, random_access_iterator_tag)
+ search_n_switch(RandomAccessIterator begin, RandomAccessIterator end,
+ Integer count, const T& val, BinaryPredicate binary_pred,
+ random_access_iterator_tag)
{
if (_GLIBCXX_PARALLEL_CONDITION(true))
{
- __gnu_parallel::pseudo_sequence<T, Integer> ps(val, count);
- return __gnu_parallel::search_template(begin, end, ps.begin(), ps.end(), binary_pred);
+ __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>
+// Sequential fallback for input iterator case.
+template<typename ForwardIterator, typename Integer, typename T,
+ typename BinaryPredicate, typename IteratorTag>
inline ForwardIterator
- search_n_switch(ForwardIterator begin, ForwardIterator end, Integer count, const T& val, BinaryPredicate binary_pred, IteratorTag)
+ search_n_switch(ForwardIterator begin, ForwardIterator end, Integer count,
+ const T& val, BinaryPredicate binary_pred, IteratorTag)
{
return __search_n(begin, end, count, val, binary_pred, IteratorTag());
}
- // Public interface.
- template<typename ForwardIterator, typename Integer, typename T, typename BinaryPredicate>
+// Public interface.
+template<typename ForwardIterator, typename Integer, typename T,
+ typename BinaryPredicate>
inline ForwardIterator
- search_n(ForwardIterator begin, ForwardIterator end, Integer count, const T& val, BinaryPredicate binary_pred)
+ search_n(ForwardIterator begin, ForwardIterator end, Integer count,
+ const T& val, BinaryPredicate binary_pred)
{
- return search_n_switch(begin, end, count, val, binary_pred, typename std::iterator_traits<ForwardIterator>::iterator_category());
+ return search_n_switch(
+ begin, end, count, val, binary_pred,
+ typename std::iterator_traits<ForwardIterator>
+ ::iterator_category());
}
- // Sequential fallback.
- template<typename InputIterator, typename OutputIterator, typename UnaryOperation>
+// Sequential fallback.
+template<typename InputIterator, typename OutputIterator,
+ typename UnaryOperation>
inline OutputIterator
transform(InputIterator begin, InputIterator end, OutputIterator result,
- UnaryOperation unary_op, __gnu_parallel::sequential_tag)
+ 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>
+// Parallel unary transform for random access iterators.
+template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename UnaryOperation>
RandomAccessIterator2
- transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end, RandomAccessIterator2 result, UnaryOperation unary_op, random_access_iterator_tag, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
+ transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end,
+ RandomAccessIterator2 result, UnaryOperation unary_op,
+ random_access_iterator_tag,
+ random_access_iterator_tag,
+ __gnu_parallel::parallelism parallelism_tag
+ = __gnu_parallel::parallel_balanced)
{
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::transform_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
+ if (_GLIBCXX_PARALLEL_CONDITION(
+ static_cast<__gnu_parallel::sequence_index_t>(end - begin)
+ >= __gnu_parallel::Settings::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;
+ 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());
+ __gnu_parallel::sequential_tag());
}
- // Sequential fallback for input iterator case.
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename UnaryOperation, typename IteratorTag1, typename IteratorTag2>
+// Sequential fallback for input iterator case.
+template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename UnaryOperation,
+ typename IteratorTag1, typename IteratorTag2>
inline RandomAccessIterator2
- transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end, RandomAccessIterator2 result, UnaryOperation unary_op, IteratorTag1, IteratorTag2)
- {
+ transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end,
+ 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>
+// Public interface.
+template<typename InputIterator, typename OutputIterator,
+ typename UnaryOperation>
inline OutputIterator
transform(InputIterator begin, InputIterator end, OutputIterator result,
- UnaryOperation unary_op,
- __gnu_parallel::parallelism parallelism_tag)
+ UnaryOperation unary_op,
+ __gnu_parallel::parallelism parallelism_tag)
{
typedef std::iterator_traits<InputIterator> iteratori_traits;
typedef std::iterator_traits<OutputIterator> iteratoro_traits;
@@ -1075,14 +1257,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>
+template<typename InputIterator, typename OutputIterator,
+ 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;
@@ -1090,56 +1273,76 @@
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>
+// Sequential fallback
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename BinaryOperation>
inline OutputIterator
transform(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- OutputIterator result, BinaryOperation binary_op,
- __gnu_parallel::sequential_tag)
+ OutputIterator result, BinaryOperation binary_op,
+ __gnu_parallel::sequential_tag)
{
return _GLIBCXX_STD_P::transform(begin1, end1, begin2, result, binary_op);
}
- // Parallel binary transform for random access iterators.
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename RandomAccessIterator3, typename BinaryOperation>
+// Parallel binary transform for random access iterators.
+template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename RandomAccessIterator3, typename BinaryOperation>
RandomAccessIterator3
- transform2_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, RandomAccessIterator3 result, BinaryOperation binary_op, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
+ transform2_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
+ RandomAccessIterator2 begin2, RandomAccessIterator3 result,
+ BinaryOperation binary_op,
+ random_access_iterator_tag,
+ random_access_iterator_tag,
+ random_access_iterator_tag,
+ __gnu_parallel::parallelism parallelism_tag
+ = __gnu_parallel::parallel_balanced)
{
- if (_GLIBCXX_PARALLEL_CONDITION((end1 - begin1) >= __gnu_parallel::Settings::transform_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
+ if (_GLIBCXX_PARALLEL_CONDITION((end1 - begin1)
+ >= __gnu_parallel::Settings::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;
+ 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());
+ __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>
+// Sequential fallback for input iterator case.
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename BinaryOperation,
+ typename tag1, typename tag2, typename tag3>
inline OutputIterator
transform2_switch(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, OutputIterator result,
- BinaryOperation binary_op, tag1, tag2, tag3)
+ 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>
+// Public interface.
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename BinaryOperation>
inline OutputIterator
transform(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- OutputIterator result, BinaryOperation binary_op,
- __gnu_parallel::parallelism parallelism_tag)
+ 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;
@@ -1149,14 +1352,15 @@
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>
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename BinaryOperation>
inline OutputIterator
transform(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- OutputIterator result, BinaryOperation binary_op)
+ OutputIterator result, BinaryOperation binary_op)
{
typedef std::iterator_traits<InputIterator1> iteratori1_traits;
typedef typename iteratori1_traits::iterator_category iteratori1_category;
@@ -1166,57 +1370,57 @@
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>
+// 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>
+// Sequential fallback for input iterator case
+template<typename ForwardIterator, typename T, typename IteratorTag>
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>
+// Parallel replace for random access iterators
+template<typename RandomAccessIterator, typename T>
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?
+ // 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>
+// 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>
+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;
@@ -1224,107 +1428,124 @@
}
- // Sequential fallback
- template<typename ForwardIterator, typename Predicate, typename T>
+// Sequential fallback
+template<typename ForwardIterator, typename Predicate, typename T>
inline void
replace_if(ForwardIterator begin, ForwardIterator end, Predicate pred,
- const T& new_value, __gnu_parallel::sequential_tag)
+ 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>
+// Sequential fallback for input iterator case
+template<
+ typename ForwardIterator,
+ typename Predicate,
+ typename T,
+ typename IteratorTag>
void
replace_if_switch(ForwardIterator begin, ForwardIterator end, Predicate pred,
- const T& new_value, IteratorTag)
- { replace_if(begin, end, pred, new_value, __gnu_parallel::sequential_tag()); }
+ const T& new_value, IteratorTag)
+ {
+ replace_if(begin, end, pred, new_value, __gnu_parallel::sequential_tag());
+ }
- // Parallel algorithm for random access iterators.
- template<typename RandomAccessIterator, typename Predicate, typename T>
+// 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::replace_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
+ if (_GLIBCXX_PARALLEL_CONDITION(
+ static_cast<__gnu_parallel::sequence_index_t>(end - begin)
+ >= __gnu_parallel::Settings::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);
+ 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());
+ __gnu_parallel::sequential_tag());
}
- // Public interface.
- template<typename ForwardIterator, typename Predicate, typename T>
+// 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>
+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;
replace_if_switch(begin, end, pred, new_value, iterator_category());
}
- // Sequential fallback
- template<typename ForwardIterator, typename Generator>
+// Sequential fallback
+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>
+// Sequential fallback for input iterator case.
+template<typename ForwardIterator, typename Generator, typename IteratorTag>
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>
+// 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::generate_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
+ if (_GLIBCXX_PARALLEL_CONDITION(
+ static_cast<__gnu_parallel::sequence_index_t>(end - begin)
+ >= __gnu_parallel::Settings::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);
+ bool dummy;
+ __gnu_parallel::generate_selector<RandomAccessIterator> functionality;
+ __gnu_parallel::for_each_template_random_access
+ (begin, end, gen, functionality, __gnu_parallel::dummy_reduct(),
+ true, dummy, -1, parallelism_tag);
}
else
generate(begin, end, gen, __gnu_parallel::sequential_tag());
}
- // Public interface.
- template<typename ForwardIterator, typename Generator>
+// 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;
generate_switch(begin, end, gen, iterator_category(), parallelism_tag);
}
- template<typename ForwardIterator, typename Generator>
+template<typename ForwardIterator, typename Generator>
inline void
generate(ForwardIterator begin, ForwardIterator end, Generator gen)
{
@@ -1334,44 +1555,45 @@
}
- // Sequential fallback.
- template<typename OutputIterator, typename Size, typename Generator>
+// Sequential fallback.
+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>
+// Sequential fallback for input iterator case.
+template<typename OutputIterator, typename Size, typename Generator,
+ typename IteratorTag>
OutputIterator
generate_n_switch(OutputIterator begin, Size n, Generator gen, IteratorTag)
{ return generate_n(begin, n, gen, __gnu_parallel::sequential_tag()); }
- // Parallel algorithm for random access iterators.
- template<typename RandomAccessIterator, typename Size, typename Generator>
+// Parallel algorithm for random access iterators.
+template<typename RandomAccessIterator, typename Size, typename Generator>
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?
+ // XXX parallel version is where?
return generate_n(begin, n, gen, __gnu_parallel::sequential_tag());
}
- // Public interface.
- template<typename OutputIterator, typename Size, typename Generator>
+// Public interface.
+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>
+template<typename OutputIterator, typename Size, typename Generator>
inline OutputIterator
generate_n(OutputIterator begin, Size n, Generator gen)
{
@@ -1381,82 +1603,91 @@
}
- // Sequential fallback.
- template<typename RandomAccessIterator>
+// Sequential fallback.
+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>
+// 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); }
/** @brief Functor wrapper for std::rand(). */
- template<typename must_be_int = int>
+template<typename must_be_int = int>
struct c_rand_number
{
inline int operator()(int limit)
{ return rand() % limit; }
};
- // Fill in random number generator.
- template<typename RandomAccessIterator>
+// Fill in random number generator.
+template<typename RandomAccessIterator>
inline void
random_shuffle(RandomAccessIterator begin, RandomAccessIterator end)
{
c_rand_number<> r;
- // Parallelization still possible.
+ // Parallelization still possible.
random_shuffle(begin, end, r);
}
- // Parallel algorithm for random access iterators.
- template<typename RandomAccessIterator, typename RandomNumberGenerator>
+// Parallel algorithm for random access iterators.
+template<typename RandomAccessIterator, typename RandomNumberGenerator>
void
random_shuffle(RandomAccessIterator begin, RandomAccessIterator end,
- RandomNumberGenerator& rand)
+ RandomNumberGenerator& rand)
{
if (begin == end)
return;
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::random_shuffle_minimal_n))
+ if (_GLIBCXX_PARALLEL_CONDITION(
+ static_cast<__gnu_parallel::sequence_index_t>(end - begin)
+ >= __gnu_parallel::Settings::random_shuffle_minimal_n))
__gnu_parallel::parallel_random_shuffle(begin, end, rand);
else
__gnu_parallel::sequential_random_shuffle(begin, end, rand);
}
- // Sequential fallback.
- template<typename ForwardIterator, typename Predicate>
+// Sequential fallback.
+template<typename ForwardIterator, typename Predicate>
inline ForwardIterator
- partition(ForwardIterator begin, ForwardIterator end, Predicate pred, __gnu_parallel::sequential_tag)
+ partition(ForwardIterator begin, ForwardIterator end,
+ Predicate pred, __gnu_parallel::sequential_tag)
{ return _GLIBCXX_STD_P::partition(begin, end, pred); }
- // Sequential fallback for input iterator case.
- template<typename ForwardIterator, typename Predicate, typename IteratorTag>
+// Sequential fallback for input iterator case.
+template<typename ForwardIterator, typename Predicate, typename IteratorTag>
inline ForwardIterator
- partition_switch(ForwardIterator begin, ForwardIterator end, Predicate pred, IteratorTag)
+ partition_switch(ForwardIterator begin, ForwardIterator end,
+ Predicate pred, IteratorTag)
{ return partition(begin, end, pred, __gnu_parallel::sequential_tag()); }
- // Parallel algorithm for random access iterators.
- template<typename RandomAccessIterator, typename Predicate>
+// Parallel algorithm for random access iterators.
+template<typename RandomAccessIterator, typename Predicate>
RandomAccessIterator
- partition_switch(RandomAccessIterator begin, RandomAccessIterator end, Predicate pred, random_access_iterator_tag)
+ partition_switch(RandomAccessIterator begin, RandomAccessIterator end,
+ Predicate pred, random_access_iterator_tag)
{
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::partition_minimal_n))
+ if (_GLIBCXX_PARALLEL_CONDITION(
+ static_cast<__gnu_parallel::sequence_index_t>(end - begin)
+ >= __gnu_parallel::Settings::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;
+ typedef typename std::iterator_traits<RandomAccessIterator>
+ ::difference_type difference_type;
+ difference_type middle = __gnu_parallel::parallel_partition
+ (begin, end, pred, __gnu_parallel::get_max_threads());
+ return begin + middle;
}
else
return partition(begin, end, pred, __gnu_parallel::sequential_tag());
}
- // Public interface.
- template<typename ForwardIterator, typename Predicate>
+// Public interface.
+template<typename ForwardIterator, typename Predicate>
inline ForwardIterator
partition(ForwardIterator begin, ForwardIterator end, Predicate pred)
{
@@ -1465,22 +1696,22 @@
return partition_switch(begin, end, pred, iterator_category());
}
- // Sequential fallback
- template<typename RandomAccessIterator>
+// Sequential fallback
+template<typename RandomAccessIterator>
inline void
sort(RandomAccessIterator begin, RandomAccessIterator end,
__gnu_parallel::sequential_tag)
{ _GLIBCXX_STD_P::sort(begin, end); }
- // Sequential fallback
- template<typename RandomAccessIterator, typename Comparator>
+// Sequential fallback
+template<typename RandomAccessIterator, typename Comparator>
inline void
sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp,
__gnu_parallel::sequential_tag)
{ _GLIBCXX_STD_P::sort<RandomAccessIterator, Comparator>(begin, end, comp); }
- // Public interface, insert default comparator
- template<typename RandomAccessIterator>
+// Public interface, insert default comparator
+template<typename RandomAccessIterator>
inline void
sort(RandomAccessIterator begin, RandomAccessIterator end)
{
@@ -1489,7 +1720,7 @@
sort(begin, end, std::less<value_type>());
}
- template<typename RandomAccessIterator, typename Comparator>
+template<typename RandomAccessIterator, typename Comparator>
void
sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp)
{
@@ -1498,28 +1729,30 @@
if (begin != end)
{
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::sort_minimal_n))
- __gnu_parallel::parallel_sort(begin, end, comp, false);
- else
- sort(begin, end, comp, __gnu_parallel::sequential_tag());
+ if (_GLIBCXX_PARALLEL_CONDITION(
+ static_cast<__gnu_parallel::sequence_index_t>(end - begin)
+ >= __gnu_parallel::Settings::sort_minimal_n))
+ __gnu_parallel::parallel_sort(begin, end, comp, false);
+ else
+ sort(begin, end, comp, __gnu_parallel::sequential_tag());
}
}
- // Sequential fallback.
- template<typename RandomAccessIterator>
+// Sequential fallback.
+template<typename RandomAccessIterator>
inline void
stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
- __gnu_parallel::sequential_tag)
+ __gnu_parallel::sequential_tag)
{ return _GLIBCXX_STD_P::stable_sort(begin, end); }
- // Sequential fallback.
- template<typename RandomAccessIterator, typename Comparator>
+// Sequential fallback.
+template<typename RandomAccessIterator, typename Comparator>
inline void
stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
- Comparator comp, __gnu_parallel::sequential_tag)
+ Comparator comp, __gnu_parallel::sequential_tag)
{ return _GLIBCXX_STD_P::stable_sort(begin, end, comp); }
- template<typename RandomAccessIterator>
+template<typename RandomAccessIterator>
void
stable_sort(RandomAccessIterator begin, RandomAccessIterator end)
{
@@ -1528,66 +1761,81 @@
stable_sort(begin, end, std::less<value_type>());
}
- // Parallel algorithm for random access iterators
- template<typename RandomAccessIterator, typename Comparator>
+// Parallel algorithm for random access iterators
+template<typename RandomAccessIterator, typename Comparator>
void
stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
- Comparator comp)
+ Comparator comp)
{
if (begin != end)
{
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::sort_minimal_n))
- __gnu_parallel::parallel_sort(begin, end, comp, true);
- else
- stable_sort(begin, end, comp, __gnu_parallel::sequential_tag());
+ if (_GLIBCXX_PARALLEL_CONDITION(
+ static_cast<__gnu_parallel::sequence_index_t>(end - begin)
+ >= __gnu_parallel::Settings::sort_minimal_n))
+ __gnu_parallel::parallel_sort(begin, end, comp, true);
+ else
+ stable_sort(begin, end, comp, __gnu_parallel::sequential_tag());
}
}
- // Sequential fallback
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
+// Sequential fallback
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator>
inline OutputIterator
merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- InputIterator2 end2, OutputIterator result,
- __gnu_parallel::sequential_tag)
+ 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>
+// Sequential fallback
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename Comparator>
inline OutputIterator
merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- InputIterator2 end2, OutputIterator result, Comparator comp,
- __gnu_parallel::sequential_tag)
+ 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>
+// Sequential fallback for input iterator case
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename Comparator,
+ typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
inline OutputIterator
- merge_switch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator result, Comparator comp, IteratorTag1, IteratorTag2, IteratorTag3)
+ merge_switch(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator result, Comparator comp,
+ IteratorTag1, IteratorTag2, IteratorTag3)
{ return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result, comp); }
- // Parallel algorithm for random access iterators
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Comparator>
+// Parallel algorithm for random access iterators
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename Comparator>
OutputIterator
merge_switch(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator result, Comparator comp,
- random_access_iterator_tag, random_access_iterator_tag,
- random_access_iterator_tag)
+ 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::merge_minimal_n || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2) >= __gnu_parallel::Settings::merge_minimal_n)))
+ if (_GLIBCXX_PARALLEL_CONDITION((
+ static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
+ >= __gnu_parallel::Settings::merge_minimal_n
+ || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
+ >= __gnu_parallel::Settings::merge_minimal_n)))
return __gnu_parallel::parallel_merge_advance(begin1, end1, begin2, end2,
- result, (end1 - begin1) + (end2 - begin2), comp);
+ result, (end1 - begin1) + (end2 - begin2), comp);
else
return __gnu_parallel::merge_advance(begin1, end1, begin2, end2, result,
- (end1 - begin1) + (end2 - begin2),
- comp);
+ (end1 - begin1) + (end2 - begin2),
+ comp);
}
- // Public interface
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Comparator>
+// Public interface
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename Comparator>
inline OutputIterator
merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- InputIterator2 end2, OutputIterator result, Comparator comp)
+ InputIterator2 end2, OutputIterator result, Comparator comp)
{
typedef typename iterator_traits<InputIterator1>::value_type value_type;
@@ -1599,16 +1847,17 @@
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>
+// Public interface, insert default comparator
+template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator>
inline OutputIterator
merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- InputIterator2 end2, OutputIterator result)
+ InputIterator2 end2, OutputIterator result)
{
typedef std::iterator_traits<InputIterator1> iterator1_traits;
typedef std::iterator_traits<InputIterator2> iterator2_traits;
@@ -1616,136 +1865,147 @@
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>
+// 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>
+// Sequential fallback
+template<typename RandomAccessIterator, typename Comparator>
void
nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
- RandomAccessIterator end, Comparator comp,
- __gnu_parallel::sequential_tag)
+ RandomAccessIterator end, Comparator comp,
+ __gnu_parallel::sequential_tag)
{ return _GLIBCXX_STD_P::nth_element(begin, nth, end, comp); }
- // Public interface
- template<typename RandomAccessIterator, typename Comparator>
+// Public interface
+template<typename RandomAccessIterator, typename Comparator>
inline void
nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
- RandomAccessIterator end, Comparator comp)
+ RandomAccessIterator end, Comparator comp)
{
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::nth_element_minimal_n))
+ if (_GLIBCXX_PARALLEL_CONDITION(
+ static_cast<__gnu_parallel::sequence_index_t>(end - begin)
+ >= __gnu_parallel::Settings::nth_element_minimal_n))
__gnu_parallel::parallel_nth_element(begin, nth, end, comp);
else
nth_element(begin, nth, end, comp, __gnu_parallel::sequential_tag());
}
- // Public interface, insert default comparator
- template<typename RandomAccessIterator>
+// Public interface, insert default comparator
+template<typename RandomAccessIterator>
void
nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
- RandomAccessIterator end)
+ RandomAccessIterator end)
{
typedef iterator_traits<RandomAccessIterator> traits_type;
typedef typename traits_type::value_type value_type;
nth_element(begin, nth, end, std::less<value_type>());
}
- // Sequential fallback
- template<typename RandomAccessIterator, typename _Compare>
+// Sequential fallback
+template<typename RandomAccessIterator, typename _Compare>
void
partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
- RandomAccessIterator end, _Compare comp,
- __gnu_parallel::sequential_tag)
+ RandomAccessIterator end, _Compare comp,
+ __gnu_parallel::sequential_tag)
{ _GLIBCXX_STD_P::partial_sort(begin, middle, end, comp); }
- // Sequential fallback
- template<typename RandomAccessIterator>
+// Sequential fallback
+template<typename RandomAccessIterator>
void
partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
- RandomAccessIterator end, __gnu_parallel::sequential_tag)
+ RandomAccessIterator end, __gnu_parallel::sequential_tag)
{ _GLIBCXX_STD_P::partial_sort(begin, middle, end); }
- // Public interface, parallel algorithm for random access iterators
- template<typename RandomAccessIterator, typename _Compare>
+// Public interface, parallel algorithm for random access iterators
+template<typename RandomAccessIterator, typename _Compare>
void
partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
- RandomAccessIterator end, _Compare comp)
+ RandomAccessIterator end, _Compare comp)
{
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::partial_sort_minimal_n))
+ if (_GLIBCXX_PARALLEL_CONDITION(
+ static_cast<__gnu_parallel::sequence_index_t>(end - begin)
+ >= __gnu_parallel::Settings::partial_sort_minimal_n))
__gnu_parallel::parallel_partial_sort(begin, middle, end, comp);
else
partial_sort(begin, middle, end, comp, __gnu_parallel::sequential_tag());
}
- // Public interface, insert default comparator
- template<typename RandomAccessIterator>
+// Public interface, insert default comparator
+template<typename RandomAccessIterator>
void
partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
- RandomAccessIterator end)
+ RandomAccessIterator end)
{
typedef iterator_traits<RandomAccessIterator> traits_type;
typedef typename traits_type::value_type value_type;
partial_sort(begin, middle, end, std::less<value_type>());
}
- // Sequential fallback
- template<typename ForwardIterator>
+// Sequential fallback
+template<typename ForwardIterator>
inline ForwardIterator
max_element(ForwardIterator begin, ForwardIterator end,
- __gnu_parallel::sequential_tag)
+ __gnu_parallel::sequential_tag)
{ return _GLIBCXX_STD_P::max_element(begin, end); }
- // Sequential fallback
- template<typename ForwardIterator, typename Comparator>
+// Sequential fallback
+template<typename ForwardIterator, typename Comparator>
inline ForwardIterator
max_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
- __gnu_parallel::sequential_tag)
+ __gnu_parallel::sequential_tag)
{ return _GLIBCXX_STD_P::max_element(begin, end, comp); }
- // Sequential fallback for input iterator case
- template<typename ForwardIterator, typename Comparator, typename IteratorTag>
+// Sequential fallback for input iterator case
+template<typename ForwardIterator, typename Comparator, typename IteratorTag>
ForwardIterator
max_element_switch(ForwardIterator begin, ForwardIterator end,
- Comparator comp, IteratorTag)
+ Comparator comp, IteratorTag)
{ return max_element(begin, end, comp, __gnu_parallel::sequential_tag()); }
- // Parallel algorithm for random access iterators
- template<typename RandomAccessIterator, typename Comparator>
+// Parallel algorithm for random access iterators
+template<typename RandomAccessIterator, typename Comparator>
RandomAccessIterator
max_element_switch(RandomAccessIterator begin, RandomAccessIterator end,
- Comparator comp, random_access_iterator_tag,
- __gnu_parallel::parallelism parallelism_tag
- = __gnu_parallel::parallel_balanced)
+ Comparator comp, random_access_iterator_tag,
+ __gnu_parallel::parallelism parallelism_tag
+ = __gnu_parallel::parallel_balanced)
{
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::max_element_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
+ if (_GLIBCXX_PARALLEL_CONDITION(
+ static_cast<__gnu_parallel::sequence_index_t>(end - begin)
+ >= __gnu_parallel::Settings::max_element_minimal_n
+ && __gnu_parallel::is_parallel(parallelism_tag)))
{
- RandomAccessIterator res(begin);
- __gnu_parallel::identity_selector<RandomAccessIterator> functionality;
- __gnu_parallel::for_each_template_random_access(begin, end, __gnu_parallel::nothing(), functionality, __gnu_parallel::max_element_reduct<Comparator, RandomAccessIterator>(comp), res, res, -1, parallelism_tag);
- return res;
+ RandomAccessIterator res(begin);
+ __gnu_parallel::identity_selector<RandomAccessIterator> functionality;
+ __gnu_parallel::for_each_template_random_access
+ (begin, end, __gnu_parallel::nothing(), functionality,
+ __gnu_parallel::max_element_reduct
+ <Comparator, RandomAccessIterator>(comp),
+ res, res, -1, parallelism_tag);
+ return res;
}
else
return max_element(begin, end, comp, __gnu_parallel::sequential_tag());
}
- // Public interface, insert default comparator
- template<typename ForwardIterator>
+// Public interface, insert default comparator
+template<typename ForwardIterator>
inline ForwardIterator
max_element(ForwardIterator begin, ForwardIterator end,
- __gnu_parallel::parallelism parallelism_tag)
+ __gnu_parallel::parallelism parallelism_tag)
{
typedef typename iterator_traits<ForwardIterator>::value_type value_type;
return max_element(begin, end, std::less<value_type>(), parallelism_tag);
}
- template<typename ForwardIterator>
+template<typename ForwardIterator>
inline ForwardIterator
max_element(ForwardIterator begin, ForwardIterator end)
{
@@ -1753,19 +2013,19 @@
return max_element(begin, end, std::less<value_type>());
}
- // Public interface
- template<typename ForwardIterator, typename Comparator>
+// Public interface
+template<typename ForwardIterator, typename Comparator>
inline ForwardIterator
max_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
- __gnu_parallel::parallelism parallelism_tag)
+ __gnu_parallel::parallelism parallelism_tag)
{
typedef iterator_traits<ForwardIterator> traits_type;
typedef typename traits_type::iterator_category iterator_category;
return max_element_switch(begin, end, comp, iterator_category(),
- parallelism_tag);
+ parallelism_tag);
}
- template<typename ForwardIterator, typename Comparator>
+template<typename ForwardIterator, typename Comparator>
inline ForwardIterator
max_element(ForwardIterator begin, ForwardIterator end, Comparator comp)
{
@@ -1775,58 +2035,65 @@
}
- // Sequential fallback
- template<typename ForwardIterator>
+// Sequential fallback
+template<typename ForwardIterator>
inline
ForwardIterator
min_element(ForwardIterator begin, ForwardIterator end,
- __gnu_parallel::sequential_tag)
+ __gnu_parallel::sequential_tag)
{ return _GLIBCXX_STD_P::min_element(begin, end); }
- // Sequential fallback
- template<typename ForwardIterator, typename Comparator>
+// Sequential fallback
+template<typename ForwardIterator, typename Comparator>
inline ForwardIterator
min_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
- __gnu_parallel::sequential_tag)
+ __gnu_parallel::sequential_tag)
{ return _GLIBCXX_STD_P::min_element(begin, end, comp); }
- // Sequential fallback for input iterator case
- template<typename ForwardIterator, typename Comparator, typename IteratorTag>
+// Sequential fallback for input iterator case
+template<typename ForwardIterator, typename Comparator, typename IteratorTag>
ForwardIterator
min_element_switch(ForwardIterator begin, ForwardIterator end,
- Comparator comp, IteratorTag)
+ Comparator comp, IteratorTag)
{ return min_element(begin, end, comp, __gnu_parallel::sequential_tag()); }
- // Parallel algorithm for random access iterators
- template<typename RandomAccessIterator, typename Comparator>
+// Parallel algorithm for random access iterators
+template<typename RandomAccessIterator, typename Comparator>
RandomAccessIterator
min_element_switch(RandomAccessIterator begin, RandomAccessIterator end,
- Comparator comp, random_access_iterator_tag,
- __gnu_parallel::parallelism parallelism_tag
- = __gnu_parallel::parallel_balanced)
+ Comparator comp, random_access_iterator_tag,
+ __gnu_parallel::parallelism parallelism_tag
+ = __gnu_parallel::parallel_balanced)
{
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::min_element_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
+ if (_GLIBCXX_PARALLEL_CONDITION(
+ static_cast<__gnu_parallel::sequence_index_t>(end - begin)
+ >= __gnu_parallel::Settings::min_element_minimal_n
+ && __gnu_parallel::is_parallel(parallelism_tag)))
{
- RandomAccessIterator res(begin);
- __gnu_parallel::identity_selector<RandomAccessIterator> functionality;
- __gnu_parallel::for_each_template_random_access(begin, end, __gnu_parallel::nothing(), functionality, __gnu_parallel::min_element_reduct<Comparator, RandomAccessIterator>(comp), res, res, -1, parallelism_tag);
- return res;
+ RandomAccessIterator res(begin);
+ __gnu_parallel::identity_selector<RandomAccessIterator> functionality;
+ __gnu_parallel::for_each_template_random_access
+ (begin, end, __gnu_parallel::nothing(), functionality,
+ __gnu_parallel::min_element_reduct
+ <Comparator, RandomAccessIterator>(comp),
+ res, res, -1, parallelism_tag);
+ return res;
}
else
return min_element(begin, end, comp, __gnu_parallel::sequential_tag());
}
- // Public interface, insert default comparator
- template<typename ForwardIterator>
+// Public interface, insert default comparator
+template<typename ForwardIterator>
inline ForwardIterator
min_element(ForwardIterator begin, ForwardIterator end,
- __gnu_parallel::parallelism parallelism_tag)
+ __gnu_parallel::parallelism parallelism_tag)
{
typedef typename iterator_traits<ForwardIterator>::value_type value_type;
return min_element(begin, end, std::less<value_type>(), parallelism_tag);
}
- template<typename ForwardIterator>
+template<typename ForwardIterator>
inline ForwardIterator
min_element(ForwardIterator begin, ForwardIterator end)
{
@@ -1834,19 +2101,19 @@
return min_element(begin, end, std::less<value_type>());
}
- // Public interface
- template<typename ForwardIterator, typename Comparator>
+// Public interface
+template<typename ForwardIterator, typename Comparator>
inline ForwardIterator
min_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
- __gnu_parallel::parallelism parallelism_tag)
+ __gnu_parallel::parallelism parallelism_tag)
{
typedef iterator_traits<ForwardIterator> traits_type;
typedef typename traits_type::iterator_category iterator_category;
return min_element_switch(begin, end, comp, iterator_category(),
- parallelism_tag);
+ parallelism_tag);
}
- template<typename ForwardIterator, typename Comparator>
+template<typename ForwardIterator, typename Comparator>
inline ForwardIterator
min_element(ForwardIterator begin, ForwardIterator end, Comparator comp)
{
Index: include/parallel/queue.h
===================================================================
--- include/parallel/queue.h (revision 130490)
+++ include/parallel/queue.h (working copy)
@@ -42,19 +42,20 @@
#include <parallel/base.h>
#include <parallel/compatibility.h>
-/** @brief Decide whether to declare certain variable volatile in this file. */
+/** @brief Decide whether to declare certain variable volatile in this file.
+ */
#define _GLIBCXX_VOLATILE volatile
namespace __gnu_parallel
{
- /**@brief Double-ended queue of bounded size, allowing lock-free
- * atomic access. push_front() and pop_front() must not be called
- * concurrently to each other, while pop_back() can be called
- * concurrently at all times.
- * @c empty(), @c size(), and @c top() are intentionally not provided.
- * Calling them would not make sense in a concurrent setting.
- * @param T Contained element type. */
- template<typename T>
+/**@brief Double-ended queue of bounded size, allowing lock-free
+ * atomic access. push_front() and pop_front() must not be called
+ * concurrently to each other, while pop_back() can be called
+ * concurrently at all times.
+ * @c empty(), @c size(), and @c top() are intentionally not provided.
+ * Calling them would not make sense in a concurrent setting.
+ * @param T Contained element type. */
+template<typename T>
class RestrictedBoundedConcurrentQueue
{
private:
@@ -65,7 +66,7 @@
sequence_index_t max_size;
/** @brief Cyclic begin and end pointers contained in one
- atomically changeable value. */
+ atomically changeable value. */
_GLIBCXX_VOLATILE lcas_t borders;
public:
@@ -76,7 +77,7 @@
this->max_size = max_size;
base = new T[max_size];
borders = encode2(0, 0);
-#pragma omp flush
+# pragma omp flush
}
/** @brief Destructor. Not to be called concurrent, of course. */
@@ -105,48 +106,48 @@
bool pop_front(T& t)
{
int former_front, former_back;
-#pragma omp flush
+# pragma omp flush
decode2(borders, former_front, former_back);
while (former_front > former_back)
- {
- // Chance.
- lcas_t former_borders = encode2(former_front, former_back);
- lcas_t new_borders = encode2(former_front - 1, former_back);
- if (compare_and_swap(&borders, former_borders, new_borders))
- {
- t = *(base + (former_front - 1) % max_size);
- return true;
- }
-#pragma omp flush
- decode2(borders, former_front, former_back);
- }
+ {
+ // Chance.
+ lcas_t former_borders = encode2(former_front, former_back);
+ lcas_t new_borders = encode2(former_front - 1, former_back);
+ if (compare_and_swap(&borders, former_borders, new_borders))
+ {
+ t = *(base + (former_front - 1) % max_size);
+ return true;
+ }
+# pragma omp flush
+ decode2(borders, former_front, former_back);
+ }
return false;
}
/** @brief Pops one element from the queue at the front end.
* Must not be called concurrently with pop_front(). */
- bool pop_back(T& t) //queue behavior
+ bool pop_back(T& t) //queue behavior
{
int former_front, former_back;
-#pragma omp flush
+# pragma omp flush
decode2(borders, former_front, former_back);
while (former_front > former_back)
- {
- // Chance.
- lcas_t former_borders = encode2(former_front, former_back);
- lcas_t new_borders = encode2(former_front, former_back + 1);
- if (compare_and_swap(&borders, former_borders, new_borders))
- {
- t = *(base + former_back % max_size);
- return true;
- }
-#pragma omp flush
- decode2(borders, former_front, former_back);
- }
+ {
+ // Chance.
+ lcas_t former_borders = encode2(former_front, former_back);
+ lcas_t new_borders = encode2(former_front, former_back + 1);
+ if (compare_and_swap(&borders, former_borders, new_borders))
+ {
+ t = *(base + former_back % max_size);
+ return true;
+ }
+# pragma omp flush
+ decode2(borders, former_front, former_back);
+ }
return false;
}
};
-} //namespace __gnu_parallel
+} //namespace __gnu_parallel
#undef _GLIBCXX_VOLATILE
Index: include/parallel/checkers.h
===================================================================
--- include/parallel/checkers.h (revision 130490)
+++ include/parallel/checkers.h (working copy)
@@ -52,9 +52,10 @@
* @return @c true if sorted, @c false otherwise.
*/
// XXX Comparator default template argument
- template<typename InputIterator, typename Comparator>
+template<typename InputIterator, typename Comparator>
bool
- is_sorted(InputIterator begin, InputIterator end, Comparator comp = std::less<typename std::iterator_traits<InputIterator>::value_type>())
+ is_sorted(InputIterator begin, InputIterator end, Comparator comp
+ = std::less<typename std::iterator_traits<InputIterator>::value_type>())
{
if (begin == end)
return true;
@@ -62,15 +63,15 @@
InputIterator current(begin), recent(begin);
unsigned long long position = 1;
- for (current++; current != end; current++)
+ for (++current; current != end; ++current)
{
- if (comp(*current, *recent))
- {
- printf("is_sorted: check failed before position %i.\n", position);
- return false;
- }
- recent = current;
- position++;
+ if (comp(*current, *recent))
+ {
+ printf("is_sorted: check failed before position %i.\n", position);
+ return false;
+ }
+ recent = current;
+ ++position;
}
return true;
@@ -86,9 +87,12 @@
* @return @c true if sorted, @c false otherwise.
*/
// XXX Comparator default template argument
- template<typename InputIterator, typename Comparator>
+template<typename InputIterator, typename Comparator>
bool
- is_sorted_failure(InputIterator begin, InputIterator end, InputIterator& first_failure, Comparator comp = std::less<typename std::iterator_traits<InputIterator>::value_type>())
+ is_sorted_failure(InputIterator begin, InputIterator end,
+ InputIterator& first_failure, Comparator comp
+ = std::less<typename std::iterator_traits<InputIterator>
+ ::value_type>())
{
if (begin == end)
return true;
@@ -96,16 +100,17 @@
InputIterator current(begin), recent(begin);
unsigned long long position = 1;
- for (current++; current != end; current++)
+ for (++current; current != end; ++current)
{
- if (comp(*current, *recent))
- {
- first_failure = current;
- printf("is_sorted: check failed before position %lld.\n", position);
- return false;
- }
- recent = current;
- position++;
+ if (comp(*current, *recent))
+ {
+ first_failure = current;
+ printf("is_sorted: check failed before position %lld.\n",
+ position);
+ return false;
+ }
+ recent = current;
+ ++position;
}
first_failure = end;
@@ -120,10 +125,13 @@
* @param comp Comparator.
* @return @c true if sorted, @c false otherwise.
*/
- template<typename InputIterator, typename Comparator>
+template<typename InputIterator, typename Comparator>
bool
// XXX Comparator default template argument
- is_sorted_print_failures(InputIterator begin, InputIterator end, Comparator comp = std::less<typename std::iterator_traits<InputIterator>::value_type>())
+ is_sorted_print_failures(InputIterator begin, InputIterator end,
+ Comparator comp = std::less
+ <typename std::iterator_traits<InputIterator>
+ ::value_type>())
{
if (begin == end)
return true;
@@ -131,15 +139,15 @@
InputIterator recent(begin);
bool ok = true;
- for (InputIterator pos(begin + 1); pos != end; pos++)
+ for (InputIterator pos(begin + 1); pos != end; ++pos)
{
- if (comp(*pos, *recent))
- {
- printf("%ld: %d %d %d %d\n", pos - begin, *(pos - 2),
- *(pos- 1), *pos, *(pos + 1));
- ok = false;
- }
- recent = pos;
+ if (comp(*pos, *recent))
+ {
+ printf("%ld: %d %d %d %d\n", pos - begin, *(pos - 2),
+ *(pos- 1), *pos, *(pos + 1));
+ ok = false;
+ }
+ recent = pos;
}
return ok;
}