This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.
| Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
|---|---|---|
| Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
| Other format: | [Raw text] | |
Hi, more fixes, should be most of it, for now. Tested x86_64-linux, make check-parallel. Paolo. ///////////////
2008-01-09 Paolo Carlini <pcarlini@suse.de> * include/parallel/multiway_merge.h: Reformat to 80 columns; adjust some inline specifiers; other minor style fixes. * include/parallel/losertree.h: Likewise. * include/parallel/list_partition.h: Likewise. * include/parallel/multiseq_selection.h: Likewise. * include/parallel/workstealing.h: Likewise. * include/parallel/base.h: Likewise. * include/parallel/par_loop.h: Likewise. * include/parallel/numeric: Likewise. * include/parallel/quicksort.h: Likewise. * include/parallel/algorithmfwd.h: Likewise. * include/parallel/for_each_selectors.h: Likewise. * include/parallel/omp_loop_static.h: Likewise. * include/parallel/random_shuffle.h: Likewise. * include/parallel/balanced_quicksort.h: Likewise. * include/parallel/set_operations.h: Likewise. * include/parallel/tree.h: Likewise. * include/parallel/merge.h: Likewise. * include/parallel/unique_copy.h: Likewise. * include/parallel/settings.h: Likewise. * include/parallel/multiway_mergesort.h: Likewise. * include/parallel/numericfwd.h: Likewise. * include/parallel/search.h: Likewise. * include/parallel/partition.h: Likewise. * include/parallel/compatibility.h: Likewise. * include/parallel/partial_sum.h: Likewise. * include/parallel/find.h: Likewise. * include/parallel/algo.h: Likewise. * include/parallel/queue.h: Likewise. * include/parallel/omp_loop.h: Likewise. * include/parallel/sort.h: Likewise. * include/parallel/random_number.h: Likewise.
Index: include/parallel/multiway_merge.h
===================================================================
--- include/parallel/multiway_merge.h (revision 131429)
+++ include/parallel/multiway_merge.h (working copy)
@@ -73,7 +73,7 @@
template<typename RandomAccessIterator, typename Comparator>
inline bool
operator<=(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
- guarded_iterator<RandomAccessIterator, Comparator>& bi2);
+ guarded_iterator<RandomAccessIterator, Comparator>& bi2);
/** @brief Iterator wrapper supporting an implicit supremum at the end
of the sequence, dominating all comparisons.
@@ -99,14 +99,14 @@
* @param end End iterator of sequence.
* @param comp Comparator provided for associated overloaded
* compare operators. */
- inline guarded_iterator(RandomAccessIterator begin,
- RandomAccessIterator end, Comparator& comp)
+ guarded_iterator(RandomAccessIterator begin,
+ RandomAccessIterator end, Comparator& comp)
: current(begin), end(end), comp(comp)
{ }
/** @brief Pre-increment operator.
* @return This. */
- inline guarded_iterator<RandomAccessIterator, Comparator>&
+ guarded_iterator<RandomAccessIterator, Comparator>&
operator++()
{
++current;
@@ -115,24 +115,24 @@
/** @brief Dereference operator.
* @return Referenced element. */
- inline typename std::iterator_traits<RandomAccessIterator>::value_type
+ typename std::iterator_traits<RandomAccessIterator>::value_type
operator*()
{ return *current; }
/** @brief Convert to wrapped iterator.
* @return Wrapped iterator. */
- inline operator RandomAccessIterator()
+ operator RandomAccessIterator()
{ return current; }
friend bool
operator< <RandomAccessIterator, Comparator>(
- guarded_iterator<RandomAccessIterator, Comparator>& bi1,
- guarded_iterator<RandomAccessIterator, Comparator>& bi2);
+ guarded_iterator<RandomAccessIterator, Comparator>& bi1,
+ guarded_iterator<RandomAccessIterator, Comparator>& bi2);
friend bool
operator<= <RandomAccessIterator, Comparator>(
- guarded_iterator<RandomAccessIterator, Comparator>& bi1,
- guarded_iterator<RandomAccessIterator, Comparator>& bi2);
+ guarded_iterator<RandomAccessIterator, Comparator>& bi1,
+ guarded_iterator<RandomAccessIterator, Comparator>& bi2);
};
/** @brief Compare two elements referenced by guarded iterators.
@@ -158,7 +158,7 @@
template<typename RandomAccessIterator, typename Comparator>
inline bool
operator<=(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
- guarded_iterator<RandomAccessIterator, Comparator>& bi2)
+ guarded_iterator<RandomAccessIterator, Comparator>& bi2)
{
if (bi2.current == bi2.end) //bi1 is sup
return bi1.current != bi1.end; //bi2 is not sup
@@ -194,14 +194,14 @@
* @param begin Begin iterator of sequence.
* @param end Unused, only for compatibility.
* @param comp Unused, only for compatibility. */
- inline unguarded_iterator(RandomAccessIterator begin,
- RandomAccessIterator end, Comparator& comp)
+ unguarded_iterator(RandomAccessIterator begin,
+ RandomAccessIterator end, Comparator& comp)
: current(begin), comp(comp)
{ }
/** @brief Pre-increment operator.
* @return This. */
- inline unguarded_iterator<RandomAccessIterator, Comparator>&
+ unguarded_iterator<RandomAccessIterator, Comparator>&
operator++()
{
++current;
@@ -210,25 +210,24 @@
/** @brief Dereference operator.
* @return Referenced element. */
- inline typename std::iterator_traits<RandomAccessIterator>::value_type
+ typename std::iterator_traits<RandomAccessIterator>::value_type
operator*()
{ return *current; }
/** @brief Convert to wrapped iterator.
* @return Wrapped iterator. */
- inline
operator RandomAccessIterator()
{ return current; }
friend bool
operator< <RandomAccessIterator, Comparator>(
- unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
- unguarded_iterator<RandomAccessIterator, Comparator>& bi2);
+ unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
+ unguarded_iterator<RandomAccessIterator, Comparator>& bi2);
friend bool
operator<= <RandomAccessIterator, Comparator>(
- unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
- unguarded_iterator<RandomAccessIterator, Comparator>& bi2);
+ unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
+ unguarded_iterator<RandomAccessIterator, Comparator>& bi2);
};
/** @brief Compare two elements referenced by unguarded iterators.
@@ -399,18 +398,17 @@
* @param length Maximum length to merge.
* @param stable Unused, stable anyway.
* @return End iterator of output sequence. */
-template<
- template<typename RAI, typename C> class iterator,
- typename RandomAccessIteratorIterator,
- typename RandomAccessIterator3,
- typename _DifferenceTp,
- typename Comparator>
+template<template<typename RAI, typename C> class iterator,
+ typename RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Comparator>
RandomAccessIterator3
- multiway_merge_3_variant(
- RandomAccessIteratorIterator seqs_begin,
- RandomAccessIteratorIterator seqs_end,
- RandomAccessIterator3 target,
- Comparator comp, _DifferenceTp length, bool stable)
+ multiway_merge_3_variant(RandomAccessIteratorIterator seqs_begin,
+ RandomAccessIteratorIterator seqs_end,
+ RandomAccessIterator3 target,
+ Comparator comp, _DifferenceTp length,
+ bool stable)
{
_GLIBCXX_CALL(length);
@@ -483,11 +481,10 @@
return target;
}
-template<
- typename RandomAccessIteratorIterator,
- typename RandomAccessIterator3,
- typename _DifferenceTp,
- typename Comparator>
+template<typename RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Comparator>
RandomAccessIterator3
multiway_merge_3_combined(RandomAccessIteratorIterator seqs_begin,
RandomAccessIteratorIterator seqs_end,
@@ -573,12 +570,11 @@
* @param length Maximum length to merge.
* @param stable Unused, stable anyway.
* @return End iterator of output sequence. */
-template<
- template<typename RAI, typename C> class iterator,
- typename RandomAccessIteratorIterator,
- typename RandomAccessIterator3,
- typename _DifferenceTp,
- typename Comparator>
+template<template<typename RAI, typename C> class iterator,
+ typename RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Comparator>
RandomAccessIterator3
multiway_merge_4_variant(RandomAccessIteratorIterator seqs_begin,
RandomAccessIteratorIterator seqs_end,
@@ -680,11 +676,10 @@
return target;
}
-template<
- typename RandomAccessIteratorIterator,
- typename RandomAccessIterator3,
- typename _DifferenceTp,
- typename Comparator>
+template<typename RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Comparator>
RandomAccessIterator3
multiway_merge_4_combined(RandomAccessIteratorIterator seqs_begin,
RandomAccessIteratorIterator seqs_end,
@@ -765,11 +760,10 @@
* @param stable Stable merging incurs a performance penalty.
* @return End iterator of output sequence.
*/
-template<
- typename RandomAccessIteratorIterator,
- typename RandomAccessIterator3,
- typename _DifferenceTp,
- typename Comparator>
+template<typename RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Comparator>
RandomAccessIterator3
multiway_merge_bubble(RandomAccessIteratorIterator seqs_begin,
RandomAccessIteratorIterator seqs_end,
@@ -845,7 +839,8 @@
++target;
++(seqs_begin[source[0]].first);
--length;
- if (seqs_begin[source[0]].first == seqs_begin[source[0]].second)
+ if (seqs_begin[source[0]].first
+ == seqs_begin[source[0]].second)
{
// Move everything to the left.
for (int s = 0; s < nrs - 1; ++s)
@@ -870,7 +865,8 @@
++target;
++(seqs_begin[source[0]].first);
--length;
- if (seqs_begin[source[0]].first == seqs_begin[source[0]].second)
+ if (seqs_begin[source[0]].first
+ == seqs_begin[source[0]].second)
{
for (int s = 0; s < nrs - 1; ++s)
{
@@ -888,9 +884,9 @@
// Sink down.
j = 1;
- while ((j < nrs) && (comp(fe[j], fe[j - 1]) ||
- (!comp(fe[j - 1], fe[j])
- && (source[j] < source[j - 1]))))
+ while ((j < nrs) && (comp(fe[j], fe[j - 1])
+ || (!comp(fe[j - 1], fe[j])
+ && (source[j] < source[j - 1]))))
{
std::swap(fe[j - 1], fe[j]);
std::swap(source[j - 1], source[j]);
@@ -910,7 +906,8 @@
++target;
++seqs_begin[source[0]].first;
--length;
- if (seqs_begin[source[0]].first == seqs_begin[source[0]].second)
+ if (seqs_begin[source[0]].first
+ == seqs_begin[source[0]].second)
{
for (int s = 0; s < (nrs - 1); ++s)
{
@@ -954,12 +951,11 @@
* @param stable Stable merging incurs a performance penalty.
* @return End iterator of output sequence.
*/
-template<
- typename LT,
- typename RandomAccessIteratorIterator,
- typename RandomAccessIterator3,
- typename _DifferenceTp,
- typename Comparator>
+template<typename LT,
+ typename RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Comparator>
RandomAccessIterator3
multiway_merge_loser_tree(RandomAccessIteratorIterator seqs_begin,
RandomAccessIteratorIterator seqs_end,
@@ -987,7 +983,8 @@
for (int t = 0; t < k; ++t)
{
- if(arbitrary_element == NULL && _GLIBCXX_PARALLEL_LENGTH(seqs_begin[t]) > 0)
+ if(arbitrary_element == NULL
+ && _GLIBCXX_PARALLEL_LENGTH(seqs_begin[t]) > 0)
arbitrary_element = &(*seqs_begin[t].first);
total_length += _GLIBCXX_PARALLEL_LENGTH(seqs_begin[t]);
}
@@ -1074,11 +1071,10 @@
* @return End iterator of output sequence.
* @pre No input will run out of elements during the merge.
*/
-template<
- typename LT,
- typename RandomAccessIteratorIterator,
- typename RandomAccessIterator3,
- typename _DifferenceTp, typename Comparator>
+template<typename LT,
+ typename RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp, typename Comparator>
RandomAccessIterator3
multiway_merge_loser_tree_unguarded(RandomAccessIteratorIterator seqs_begin,
RandomAccessIteratorIterator seqs_end,
@@ -1190,11 +1186,10 @@
return target;
}
-template<
- typename RandomAccessIteratorIterator,
- typename RandomAccessIterator3,
- typename _DifferenceTp,
- typename Comparator>
+template<typename RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Comparator>
RandomAccessIterator3
multiway_merge_loser_tree_combined(RandomAccessIteratorIterator seqs_begin,
RandomAccessIteratorIterator seqs_end,
@@ -1254,17 +1249,16 @@
return target_end;
}
-template<
- typename RandomAccessIteratorIterator,
- typename RandomAccessIterator3,
- typename _DifferenceTp,
- typename Comparator>
+template<typename RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Comparator>
RandomAccessIterator3
multiway_merge_loser_tree_sentinel(RandomAccessIteratorIterator seqs_begin,
RandomAccessIteratorIterator seqs_end,
- RandomAccessIterator3 target,
- Comparator comp,
- _DifferenceTp length, bool stable)
+ RandomAccessIterator3 target,
+ Comparator comp,
+ _DifferenceTp length, bool stable)
{
_GLIBCXX_CALL(length)
@@ -1326,7 +1320,8 @@
/** @brief Sequential multi-way merging switch.
*
- * The _GLIBCXX_PARALLEL_DECISION if based on the branching factor and runtime settings.
+ * The _GLIBCXX_PARALLEL_DECISION if based on the branching factor and
+ * runtime settings.
* @param seqs_begin Begin iterator of iterator pair input sequence.
* @param seqs_end End iterator of iterator pair input sequence.
* @param target Begin iterator out output sequence.
@@ -1335,11 +1330,10 @@
* @param stable Stable merging incurs a performance penalty.
* @param sentinel The sequences have a sentinel element.
* @return End iterator of output sequence. */
-template<
- typename RandomAccessIteratorIterator,
- typename RandomAccessIterator3,
- typename _DifferenceTp,
- typename Comparator>
+template<typename RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Comparator>
RandomAccessIterator3
multiway_merge(RandomAccessIteratorIterator seqs_begin,
RandomAccessIteratorIterator seqs_end,
@@ -1393,23 +1387,26 @@
{
case Settings::LOSER_TREE_COMBINED:
return_target = multiway_merge_3_combined(seqs_begin,
- seqs_end,
- target,
- comp, length, stable);
+ seqs_end,
+ target,
+ comp, length,
+ stable);
break;
case Settings::LOSER_TREE_SENTINEL:
- return_target = multiway_merge_3_variant<unguarded_iterator>(
- seqs_begin,
- seqs_end,
- target,
- comp, length, stable);
+ return_target =
+ multiway_merge_3_variant<unguarded_iterator>(seqs_begin,
+ seqs_end,
+ target,
+ comp, length,
+ stable);
break;
default:
- return_target = multiway_merge_3_variant<guarded_iterator>(
- seqs_begin,
- seqs_end,
- target,
- comp, length, stable);
+ return_target =
+ multiway_merge_3_variant<guarded_iterator>(seqs_begin,
+ seqs_end,
+ target,
+ comp, length,
+ stable);
break;
}
break;
@@ -1417,25 +1414,25 @@
switch (mwma)
{
case Settings::LOSER_TREE_COMBINED:
- return_target = multiway_merge_4_combined(
- seqs_begin,
- seqs_end,
- target,
- comp, length, stable);
+ return_target = multiway_merge_4_combined(seqs_begin,
+ seqs_end,
+ target,
+ comp, length, stable);
break;
case Settings::LOSER_TREE_SENTINEL:
- return_target = multiway_merge_4_variant<unguarded_iterator>(
- seqs_begin,
- seqs_end,
- target,
- comp, length, stable);
+ return_target =
+ multiway_merge_4_variant<unguarded_iterator>(seqs_begin,
+ seqs_end,
+ target,
+ comp, length,
+ stable);
break;
default:
return_target = multiway_merge_4_variant<guarded_iterator>(
- seqs_begin,
- seqs_end,
- target,
- comp, length, stable);
+ seqs_begin,
+ seqs_end,
+ target,
+ comp, length, stable);
break;
}
break;
@@ -1444,48 +1441,47 @@
switch (mwma)
{
case Settings::BUBBLE:
- return_target = multiway_merge_bubble(
- seqs_begin,
- seqs_end,
- target,
- comp, length, stable);
+ return_target = multiway_merge_bubble(seqs_begin,
+ seqs_end,
+ target,
+ comp, length, stable);
break;
#if _GLIBCXX_LOSER_TREE_EXPLICIT
case Settings::LOSER_TREE_EXPLICIT:
return_target = multiway_merge_loser_tree<
- LoserTreeExplicit<value_type, Comparator> >(
- seqs_begin,
- seqs_end,
- target,
- comp, length, stable);
+ LoserTreeExplicit<value_type, Comparator> >(seqs_begin,
+ seqs_end,
+ target,
+ comp, length,
+ stable);
break;
#endif
#if _GLIBCXX_LOSER_TREE
case Settings::LOSER_TREE:
return_target = multiway_merge_loser_tree<
- LoserTree<value_type, Comparator> >(
- seqs_begin,
- seqs_end,
- target,
- comp, length, stable);
+ LoserTree<value_type, Comparator> >(seqs_begin,
+ seqs_end,
+ target,
+ comp, length,
+ stable);
break;
#endif
#if _GLIBCXX_LOSER_TREE_COMBINED
case Settings::LOSER_TREE_COMBINED:
- return_target = multiway_merge_loser_tree_combined(
- seqs_begin,
- seqs_end,
- target,
- comp, length, stable);
+ return_target = multiway_merge_loser_tree_combined(seqs_begin,
+ seqs_end,
+ target,
+ comp, length,
+ stable);
break;
#endif
#if _GLIBCXX_LOSER_TREE_SENTINEL
case Settings::LOSER_TREE_SENTINEL:
- return_target = multiway_merge_loser_tree_sentinel(
- seqs_begin,
- seqs_end,
- target,
- comp, length, stable);
+ return_target = multiway_merge_loser_tree_sentinel(seqs_begin,
+ seqs_end,
+ target,
+ comp, length,
+ stable);
break;
#endif
default:
@@ -1504,7 +1500,8 @@
/** @brief Parallel multi-way merge routine.
*
- * The _GLIBCXX_PARALLEL_DECISION if based on the branching factor and runtime settings.
+ * The _GLIBCXX_PARALLEL_DECISION if based on the branching factor
+ * and runtime settings.
* @param seqs_begin Begin iterator of iterator pair input sequence.
* @param seqs_end End iterator of iterator pair input sequence.
* @param target Begin iterator out output sequence.
@@ -1514,11 +1511,10 @@
* @param sentinel Ignored.
* @return End iterator of output sequence.
*/
-template<
- typename RandomAccessIteratorIterator,
- typename RandomAccessIterator3,
- typename _DifferenceTp,
- typename Comparator>
+template<typename RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Comparator>
RandomAccessIterator3
parallel_multiway_merge(RandomAccessIteratorIterator seqs_begin,
RandomAccessIteratorIterator seqs_end,
@@ -1553,7 +1549,7 @@
std::vector<std::pair<difference_type, difference_type> >* pieces;
thread_index_t num_threads = static_cast<thread_index_t>(
- std::min<difference_type>(get_max_threads(), total_length));
+ std::min<difference_type>(get_max_threads(), total_length));
# pragma omp parallel num_threads (num_threads)
{
@@ -1578,20 +1574,20 @@
for (difference_type i = 0; i < num_samples; ++i)
{
difference_type sample_index =
- static_cast<difference_type>(
- _GLIBCXX_PARALLEL_LENGTH(seqs_begin[s]) * (double(i + 1) /
- (num_samples + 1)) * (double(length)
- / total_length));
- ::new(&(samples[s * num_samples + i])) value_type(
- seqs_begin[s].first[sample_index]);
+ static_cast<difference_type>(
+ _GLIBCXX_PARALLEL_LENGTH(seqs_begin[s])
+ * (double(i + 1) / (num_samples + 1))
+ * (double(length) / total_length));
+ ::new(&(samples[s * num_samples + i]))
+ value_type(seqs_begin[s].first[sample_index]);
}
if (stable)
- __gnu_sequential::stable_sort(
- samples, samples + (num_samples * k), comp);
+ __gnu_sequential::stable_sort(samples, samples
+ + (num_samples * k), comp);
else
- __gnu_sequential::sort(
- samples, samples + (num_samples * k), comp);
+ __gnu_sequential::sort(samples, samples
+ + (num_samples * k), comp);
for (int slab = 0; slab < num_threads; ++slab)
// For each slab / processor.
@@ -1600,12 +1596,12 @@
// For each sequence.
if (slab > 0)
pieces[slab][seq].first =
- std::upper_bound(
- seqs_begin[seq].first,
- seqs_begin[seq].second,
- samples[num_samples * k * slab / num_threads],
- comp)
- - seqs_begin[seq].first;
+ std::upper_bound(seqs_begin[seq].first,
+ seqs_begin[seq].second,
+ samples[num_samples * k
+ * slab / num_threads],
+ comp)
+ - seqs_begin[seq].first;
else
{
// Absolute beginning.
@@ -1613,14 +1609,15 @@
}
if ((slab + 1) < num_threads)
pieces[slab][seq].second =
- std::upper_bound(
- seqs_begin[seq].first,
- seqs_begin[seq].second,
- samples[num_samples * k * (slab + 1) /
- num_threads], comp)
- - seqs_begin[seq].first;
+ std::upper_bound(seqs_begin[seq].first,
+ seqs_begin[seq].second,
+ samples[num_samples * k
+ * (slab + 1)
+ / num_threads], comp)
+ - seqs_begin[seq].first;
else
- pieces[slab][seq].second = _GLIBCXX_PARALLEL_LENGTH(seqs_begin[seq]);
+ pieces[slab][seq].second
+ = _GLIBCXX_PARALLEL_LENGTH(seqs_begin[seq]);
}
::operator delete(samples);
}
@@ -1651,8 +1648,9 @@
{
offsets[num_threads - 1].resize(k);
multiseq_partition(se.begin(), se.end(),
- difference_type(length),
- offsets[num_threads - 1].begin(), comp);
+ difference_type(length),
+ offsets[num_threads - 1].begin(),
+ comp);
}
}
@@ -1673,12 +1671,12 @@
pieces[slab - 1][seq].second;
if (!tight || slab < (num_threads - 1))
pieces[slab][seq].second =
- offsets[slab][seq] - seqs_begin[seq].first;
+ offsets[slab][seq] - seqs_begin[seq].first;
else
{
// slab == num_threads - 1
pieces[slab][seq].second =
- _GLIBCXX_PARALLEL_LENGTH(seqs_begin[seq]);
+ _GLIBCXX_PARALLEL_LENGTH(seqs_begin[seq]);
}
}
}
@@ -1703,8 +1701,8 @@
for (int s = 0; s < k; ++s)
{
chunks[s] = std::make_pair(
- seqs_begin[s].first + pieces[iam][s].first,
- seqs_begin[s].first + pieces[iam][s].second);
+ seqs_begin[s].first + pieces[iam][s].first,
+ seqs_begin[s].first + pieces[iam][s].second);
local_length += _GLIBCXX_PARALLEL_LENGTH(chunks[s]);
}
@@ -1721,13 +1719,13 @@
begin0 = seqs_begin[0].first + pieces[iam][0].first,
begin1 = seqs_begin[1].first + pieces[iam][1].first;
merge_advance(begin0,
- seqs_begin[0].first + pieces[iam][0].second,
- begin1,
- seqs_begin[1].first + pieces[iam][1].second,
- target + target_position,
- (pieces[iam][0].second - pieces[iam][0].first) +
- (pieces[iam][1].second - pieces[iam][1].first),
- comp);
+ seqs_begin[0].first + pieces[iam][0].second,
+ begin1,
+ seqs_begin[1].first + pieces[iam][1].second,
+ target + target_position,
+ (pieces[iam][0].second - pieces[iam][0].first) +
+ (pieces[iam][1].second - pieces[iam][1].first),
+ comp);
}
} //parallel
@@ -1754,11 +1752,10 @@
* @param stable Stable merging incurs a performance penalty.
* @return End iterator of output sequence.
*/
-template<
- typename RandomAccessIteratorPairIterator,
- typename RandomAccessIterator3,
- typename _DifferenceTp,
- typename Comparator>
+template<typename RandomAccessIteratorPairIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Comparator>
RandomAccessIterator3
multiway_merge(RandomAccessIteratorPairIterator seqs_begin,
RandomAccessIteratorPairIterator seqs_end,
@@ -1775,13 +1772,13 @@
if (_GLIBCXX_PARALLEL_CONDITION(
((seqs_end - seqs_begin) >= Settings::multiway_merge_minimal_k)
&& ((sequence_index_t)length >= Settings::multiway_merge_minimal_n)))
- target_end = parallel_multiway_merge(
- seqs_begin, seqs_end,
- target, comp, static_cast<difference_type>(length), stable, false);
+ target_end = parallel_multiway_merge(seqs_begin, seqs_end,
+ target, comp,
+ static_cast<difference_type>(length),
+ stable, false);
else
- target_end = multiway_merge(
- seqs_begin, seqs_end,
- target, comp, length, stable, false, sequential_tag());
+ target_end = multiway_merge(seqs_begin, seqs_end, target, comp, length,
+ stable, false, sequential_tag());
return target_end;
}
@@ -1797,11 +1794,10 @@
* @pre For each @c i, @c seqs_begin[i].second must be the end
* marker of the sequence, but also reference the one more sentinel
* element. */
-template<
- typename RandomAccessIteratorPairIterator,
- typename RandomAccessIterator3,
- typename _DifferenceTp,
- typename Comparator>
+template<typename RandomAccessIteratorPairIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Comparator>
RandomAccessIterator3
multiway_merge_sentinel(RandomAccessIteratorPairIterator seqs_begin,
RandomAccessIteratorPairIterator seqs_end,
@@ -1824,9 +1820,9 @@
seqs_begin, seqs_end,
target, comp, static_cast<difference_type>(length), stable, true);
else
- return multiway_merge(
- seqs_begin, seqs_end,
- target, comp, length, stable, true, sequential_tag());
+ return multiway_merge(seqs_begin, seqs_end,
+ target, comp, length, stable,
+ true, sequential_tag());
}
}
Index: include/parallel/losertree.h
===================================================================
--- include/parallel/losertree.h (revision 131431)
+++ include/parallel/losertree.h (working copy)
@@ -82,7 +82,7 @@
size = _size;
offset = size;
losers = new Loser[size];
- for (unsigned int l = 0; l < size; l++)
+ for (unsigned int l = 0; l < size; ++l)
{
//losers[l].key = ... stays unset
losers[l].inf = true;
@@ -156,9 +156,10 @@
bool inf = false;
for (unsigned int pos = (offset + source) / 2; pos > 0; pos /= 2)
{
- if ((!inf && !losers[pos].inf && !sup && !losers[pos].sup &&
- ((comp(losers[pos].key, key)) ||
- (!comp(key, losers[pos].key) && losers[pos].source < source)))
+ if ((!inf && !losers[pos].inf && !sup && !losers[pos].sup
+ && ((comp(losers[pos].key, key))
+ || (!comp(key, losers[pos].key)
+ && losers[pos].source < source)))
|| losers[pos].inf || sup)
{
// Take next key.
@@ -186,8 +187,9 @@
for (unsigned int pos = (offset + source) / 2; pos > 0; pos /= 2)
{
if ((!inf && !losers[pos].inf && !sup && !losers[pos].sup
- && ((comp(losers[pos].key, key)) ||
- (!comp(key, losers[pos].key) && losers[pos].source < source)))
+ && ((comp(losers[pos].key, key))
+ || (!comp(key, losers[pos].key)
+ && losers[pos].source < source)))
|| losers[pos].inf || sup)
{
std::swap(losers[pos].key, key);
@@ -285,9 +287,9 @@
{
unsigned int left = init_winner (2 * root);
unsigned int right = init_winner (2 * root + 1);
- if (losers[right].sup ||
- (!losers[left].sup
- && !comp(losers[right].key, losers[left].key)))
+ if (losers[right].sup
+ || (!losers[left].sup
+ && !comp(losers[right].key, losers[left].key)))
{
// Left one is less or equal.
losers[root] = losers[right];
@@ -345,7 +347,7 @@
unsigned int right = init_winner (2 * root + 1);
if (losers[right].sup
|| (!losers[left].sup
- && !comp(losers[right].key, losers[left].key)))
+ && !comp(losers[right].key, losers[left].key)))
{
// Left one is less or equal.
losers[root] = losers[right];
@@ -443,7 +445,7 @@
#ifndef COPY
keys = new T[ik];
#endif
- for (unsigned int i = ik - 1; i < k; i++)
+ for (unsigned int i = ik - 1; i < k; ++i)
losers[i + k].sup = true;
}
@@ -569,11 +571,11 @@
for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
{
// The smaller one gets promoted, ties are broken by source.
- if ( (sup && (!losers[pos].sup || losers[pos].source < source)) ||
- (!sup && !losers[pos].sup &&
- ((comp(KEY(pos), KEY_SOURCE(source))) ||
- (!comp(KEY_SOURCE(source), KEY(pos))
- && losers[pos].source < source))))
+ if ((sup && (!losers[pos].sup || losers[pos].source < source))
+ || (!sup && !losers[pos].sup
+ && ((comp(KEY(pos), KEY_SOURCE(source)))
+ || (!comp(KEY_SOURCE(source), KEY(pos))
+ && losers[pos].source < source))))
{
// The other one is smaller.
std::swap(losers[pos].sup, sup);
@@ -629,7 +631,7 @@
k = 1 << (log2(ik - 1) + 1);
offset = k;
losers = new Loser[k * 2];
- for (unsigned int i = ik - 1; i < k; i++)
+ for (unsigned int i = ik - 1; i < k; ++i)
losers[i + k].sup = true;
}
@@ -746,11 +748,11 @@
for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
{
// The smaller one gets promoted, ties are broken by source.
- if ( (sup && (!losers[pos].sup || losers[pos].source < source)) ||
- (!sup && !losers[pos].sup &&
- ((comp(*losers[pos].keyp, *keyp)) ||
- (!comp(*keyp, *losers[pos].keyp)
- && losers[pos].source < source))))
+ if ( (sup && (!losers[pos].sup || losers[pos].source < source))
+ || (!sup && !losers[pos].sup &&
+ ((comp(*losers[pos].keyp, *keyp))
+ || (!comp(*keyp, *losers[pos].keyp)
+ && losers[pos].source < source))))
{
// The other one is smaller.
std::swap(losers[pos].sup, sup);
@@ -995,8 +997,8 @@
// Next greater or equal power of 2.
unsigned int division = 1 << (log2(end - begin - 1));
unsigned int left = init_winner(2 * root, begin, begin + division);
- unsigned int right
- = init_winner(2 * root + 1, begin + division, end);
+ unsigned int right = init_winner(2 * root + 1,
+ begin + division, end);
if (!comp(*losers[right].keyp, *losers[left].keyp))
{
// Left one is less or equal.
Index: include/parallel/list_partition.h
===================================================================
--- include/parallel/list_partition.h (revision 131431)
+++ include/parallel/list_partition.h (working copy)
@@ -159,7 +159,7 @@
// Smallest partitions.
for (int i = 1; i < (num_parts + 1 - size_greater); ++i)
{
- lengths[i-1] = size_part * range_length;
+ lengths[i - 1] = size_part * range_length;
index += size_part;
starts[i] = os_starts[index];
}
@@ -167,7 +167,7 @@
// Biggest partitions.
for (int i = num_parts + 1 - size_greater; i <= num_parts; ++i)
{
- lengths[i-1] = (size_part+1) * range_length;
+ lengths[i - 1] = (size_part+1) * range_length;
index += (size_part+1);
starts[i] = os_starts[index];
}
Index: include/parallel/multiseq_selection.h
===================================================================
--- include/parallel/multiseq_selection.h (revision 131431)
+++ include/parallel/multiseq_selection.h (working copy)
@@ -212,7 +212,7 @@
difference_type localrank = rank * m / N ;
int j;
- for (j = 0; j < localrank && ((n + 1) <= ns[sample[j].second]); j++)
+ for (j = 0; j < localrank && ((n + 1) <= ns[sample[j].second]); ++j)
a[sample[j].second] += n + 1;
for (; j < m; j++)
b[sample[j].second] -= n + 1;
@@ -279,7 +279,7 @@
if (b[i] < ns[i])
pq.push(std::make_pair(S(i)[b[i]], i));
- for (; skew != 0 && !pq.empty(); skew--)
+ for (; skew != 0 && !pq.empty(); --skew)
{
int source = pq.top().second;
pq.pop();
@@ -302,7 +302,7 @@
if (a[i] > 0)
pq.push(std::make_pair(S(i)[a[i] - 1], i));
- for (; skew != 0; skew++)
+ for (; skew != 0; ++skew)
{
int source = pq.top().second;
pq.pop();
@@ -416,7 +416,7 @@
ns[0] = std::distance(begin_seqs[0].first, begin_seqs[0].second);
nmax = ns[0];
- for (int i = 0; i < m; i++)
+ 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]);
@@ -431,7 +431,7 @@
// From now on, including padding.
N = l * m;
- for (int i = 0; i < m; i++)
+ for (int i = 0; i < m; ++i)
{
a[i] = 0;
b[i] = l;
@@ -460,9 +460,9 @@
difference_type localrank = rank * m / N ;
int j;
- for (j = 0; j < localrank && ((n + 1) <= ns[sample[j].second]); j++)
+ for (j = 0; j < localrank && ((n + 1) <= ns[sample[j].second]); ++j)
a[sample[j].second] += n + 1;
- for (; j < m; j++)
+ for (; j < m; ++j)
b[sample[j].second] -= n + 1;
// Further refinement.
@@ -471,7 +471,7 @@
n /= 2;
const T* lmax = NULL;
- for (int i = 0; i < m; i++)
+ for (int i = 0; i < m; ++i)
{
if (a[i] > 0)
{
@@ -496,7 +496,7 @@
}
difference_type leftsize = 0, total = 0;
- for (int i = 0; i < m; i++)
+ for (int i = 0; i < m; ++i)
{
leftsize += a[i] / (n + 1);
total += l / (n + 1);
@@ -512,7 +512,7 @@
std::vector<std::pair<T, int> >,
lexicographic_reverse<T, int, Comparator> > pq(lrcomp);
- for (int i = 0; i < m; i++)
+ for (int i = 0; i < m; ++i)
if (b[i] < ns[i])
pq.push(std::make_pair(S(i)[b[i]], i));
@@ -535,7 +535,7 @@
std::vector<std::pair<T, int> >,
lexicographic<T, int, Comparator> > pq(lcomp);
- for (int i = 0; i < m; i++)
+ for (int i = 0; i < m; ++i)
if (a[i] > 0)
pq.push(std::make_pair(S(i)[a[i] - 1], i));
@@ -566,7 +566,7 @@
// Impossible to avoid the warning?
T maxleft, minright;
- for (int i = 0; i < m; i++)
+ for (int i = 0; i < m; ++i)
{
if (a[i] > 0)
{
@@ -610,7 +610,7 @@
// We have to calculate an offset.
offset = 0;
- for (int i = 0; i < m; i++)
+ for (int i = 0; i < m; ++i)
{
difference_type lb = std::lower_bound(S(i), S(i) + ns[i],
minright,
Index: include/parallel/workstealing.h
===================================================================
--- include/parallel/workstealing.h (revision 131429)
+++ include/parallel/workstealing.h (working copy)
@@ -1,6 +1,6 @@
// -*- C++ -*-
-// Copyright (C) 2007 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
@@ -96,20 +96,19 @@
* std::count_n()).
* @return User-supplied functor (that may contain a part of the result).
*/
-template<
- typename RandomAccessIterator,
- typename Op,
- typename Fu,
- typename Red,
- typename Result>
+template<typename RandomAccessIterator,
+ typename Op,
+ typename Fu,
+ typename Red,
+ typename Result>
Op
- for_each_template_random_access_workstealing(
- RandomAccessIterator begin,
- RandomAccessIterator end,
- Op op, Fu& f, Red r,
- Result base, Result& output,
- typename std::iterator_traits<RandomAccessIterator>::difference_type
- bound)
+ for_each_template_random_access_workstealing(RandomAccessIterator begin,
+ RandomAccessIterator end,
+ Op op, Fu& f, Red r,
+ Result base, Result& output,
+ typename std::iterator_traits
+ <RandomAccessIterator>::
+ difference_type bound)
{
_GLIBCXX_CALL(end - begin)
@@ -180,7 +179,7 @@
// This thread is currently working.
# pragma omp atomic
- busy++;
+ ++busy;
iam_working = true;
@@ -198,8 +197,8 @@
// Cannot use volatile variable directly.
difference_type my_first = my_job.first;
result = f(op, begin + my_first);
- my_job.first++;
- my_job.load--;
+ ++my_job.first;
+ --my_job.load;
}
RandomAccessIterator current;
@@ -226,11 +225,11 @@
my_job.load = my_job.last - my_job.first + 1;
for (difference_type job_counter = 0;
job_counter < chunk_size && current_job <= my_job.last;
- job_counter++)
+ ++job_counter)
{
// Yes: process it!
current = begin + current_job;
- current_job++;
+ ++current_job;
// Do actual work.
result = r(result, f(op, current));
@@ -244,7 +243,7 @@
{
// This thread no longer has work.
# pragma omp atomic
- busy--;
+ --busy;
iam_working = false;
}
@@ -286,7 +285,7 @@
// Has potential work again.
# pragma omp atomic
- busy++;
+ ++busy;
iam_working = true;
# pragma omp flush(busy)
Index: include/parallel/base.h
===================================================================
--- include/parallel/base.h (revision 131430)
+++ include/parallel/base.h (working copy)
@@ -1,6 +1,6 @@
// -*- C++ -*-
-// Copyright (C) 2007 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
@@ -96,17 +96,13 @@
template<typename T>
const T&
min(const T& a, const T& b)
- {
- return (a < b) ? a : b;
- };
+ { return (a < b) ? a : b; }
/** @brief Equivalent to std::max. */
template<typename T>
const T&
max(const T& a, const T& b)
- {
- return (a > b) ? a : b;
- };
+ { return (a > b) ? a : b; }
/** @brief Constructs predicate for equality from strict weak
* ordering predicate
@@ -402,7 +398,7 @@
* @param comp Comparator.
*/
template<typename RandomAccessIterator, typename Comparator>
-RandomAccessIterator
+ RandomAccessIterator
median_of_three_iterators(RandomAccessIterator a, RandomAccessIterator b,
RandomAccessIterator c, Comparator& comp)
{
Index: include/parallel/par_loop.h
===================================================================
--- include/parallel/par_loop.h (revision 131429)
+++ include/parallel/par_loop.h (working copy)
@@ -1,6 +1,6 @@
// -*- C++ -*-
-// Copyright (C) 2007 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
@@ -64,19 +64,19 @@
* std::count_n()).
* @return User-supplied functor (that may contain a part of the result).
*/
-template<
- typename RandomAccessIterator,
- typename Op,
- typename Fu,
- typename Red,
- typename Result>
+template<typename RandomAccessIterator,
+ typename Op,
+ typename Fu,
+ typename Red,
+ typename Result>
Op
- for_each_template_random_access_ed(
- RandomAccessIterator begin,
- RandomAccessIterator end,
- Op o, Fu& f, Red r, Result base, Result& output,
- typename std::iterator_traits<RandomAccessIterator>::
- difference_type bound)
+ for_each_template_random_access_ed(RandomAccessIterator begin,
+ RandomAccessIterator end,
+ Op o, Fu& f, Red r, Result base,
+ Result& output,
+ typename std::iterator_traits
+ <RandomAccessIterator>::
+ difference_type bound)
{
typedef std::iterator_traits<RandomAccessIterator> traits_type;
typedef typename traits_type::difference_type difference_type;
@@ -85,7 +85,7 @@
Result *thread_results;
thread_index_t num_threads =
- __gnu_parallel::min<difference_type>(get_max_threads(), length);
+ __gnu_parallel::min<difference_type>(get_max_threads(), length);
# pragma omp parallel num_threads(num_threads)
{
@@ -116,7 +116,7 @@
thread_results[iam] = reduct;
} //parallel
- for (thread_index_t i = 0; i < num_threads; i++)
+ for (thread_index_t i = 0; i < num_threads; ++i)
output = r(output, thread_results[i]);
// Points to last element processed (needed as return value for
Index: include/parallel/numeric
===================================================================
--- include/parallel/numeric (revision 131429)
+++ include/parallel/numeric (working copy)
@@ -1,6 +1,6 @@
// -*- C++ -*-
-// Copyright (C) 2007 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
@@ -58,387 +58,449 @@
{
// Sequential fallback.
template<typename InputIterator, typename T>
- inline T
- accumulate(InputIterator begin, InputIterator end, T init,
- __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::accumulate(begin, end, init); }
+ inline T
+ accumulate(InputIterator begin, InputIterator end, T init,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::accumulate(begin, end, init); }
template<typename InputIterator, typename T, typename BinaryOperation>
- inline T
- accumulate(InputIterator begin, InputIterator end, T init,
- BinaryOperation binary_op, __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::accumulate(begin, end, init, binary_op); }
+ inline T
+ accumulate(InputIterator begin, InputIterator end, T init,
+ BinaryOperation binary_op, __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::accumulate(begin, end, init, binary_op); }
// Sequential fallback for input iterator case.
template<typename InputIterator, typename T, typename IteratorTag>
- inline T
- accumulate_switch(InputIterator begin, InputIterator end, T init, IteratorTag) { return accumulate(begin, end, init, __gnu_parallel::sequential_tag()); }
-
- template<typename InputIterator, typename T, typename BinaryOperation, typename IteratorTag>
- T
- accumulate_switch(InputIterator begin, InputIterator end, T init,
- BinaryOperation binary_op, IteratorTag)
- {
- return accumulate(begin, end, init, binary_op,
- __gnu_parallel::sequential_tag());
- }
+ inline T
+ accumulate_switch(InputIterator begin, InputIterator end,
+ T init, IteratorTag)
+ { return accumulate(begin, end, init, __gnu_parallel::sequential_tag()); }
+
+ template<typename InputIterator, typename T, typename BinaryOperation,
+ typename IteratorTag>
+ T
+ accumulate_switch(InputIterator begin, InputIterator end, T init,
+ BinaryOperation binary_op, IteratorTag)
+ { return accumulate(begin, end, init, binary_op,
+ __gnu_parallel::sequential_tag()); }
// Parallel algorithm for random access iterators.
- template<typename _RandomAccessIterator, typename T, typename BinaryOperation>
- T
- accumulate_switch(_RandomAccessIterator begin, _RandomAccessIterator end,
- T init, BinaryOperation binary_op,
- random_access_iterator_tag,
- __gnu_parallel::parallelism parallelism_tag
- = __gnu_parallel::parallel_unbalanced)
- {
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::accumulate_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
- {
- T res = init;
- __gnu_parallel::accumulate_selector<_RandomAccessIterator> my_selector;
- __gnu_parallel::for_each_template_random_access(begin, end, __gnu_parallel::nothing(), my_selector, __gnu_parallel::accumulate_binop_reduct<BinaryOperation>(binary_op), res, res, -1, parallelism_tag);
- return res;
- }
- else
- return accumulate(begin, end, init, binary_op,
- __gnu_parallel::sequential_tag());
- }
+ template<typename _RandomAccessIterator, typename T,
+ typename BinaryOperation>
+ T
+ accumulate_switch(_RandomAccessIterator begin, _RandomAccessIterator end,
+ T init, BinaryOperation binary_op,
+ random_access_iterator_tag,
+ __gnu_parallel::parallelism parallelism_tag
+ = __gnu_parallel::parallel_unbalanced)
+ {
+ if (_GLIBCXX_PARALLEL_CONDITION(
+ static_cast<__gnu_parallel::sequence_index_t>(end - begin)
+ >= __gnu_parallel::Settings::accumulate_minimal_n
+ && __gnu_parallel::is_parallel(parallelism_tag)))
+ {
+ T res = init;
+ __gnu_parallel::accumulate_selector<_RandomAccessIterator>
+ my_selector;
+ __gnu_parallel::
+ for_each_template_random_access(begin, end,
+ __gnu_parallel::nothing(),
+ my_selector,
+ __gnu_parallel::
+ accumulate_binop_reduct
+ <BinaryOperation>(binary_op),
+ res, res, -1, parallelism_tag);
+ return res;
+ }
+ else
+ return accumulate(begin, end, init, binary_op,
+ __gnu_parallel::sequential_tag());
+ }
// Public interface.
template<typename InputIterator, typename T>
- inline T
- accumulate(InputIterator begin, InputIterator end, T init,
- __gnu_parallel::parallelism parallelism_tag)
- {
- typedef std::iterator_traits<InputIterator> iterator_traits;
- typedef typename iterator_traits::value_type value_type;
- typedef typename iterator_traits::iterator_category iterator_category;
-
- return accumulate_switch(begin, end, init, __gnu_parallel::plus<T, value_type>(),
- iterator_category(), parallelism_tag);
- }
+ inline T
+ accumulate(InputIterator begin, InputIterator end, T init,
+ __gnu_parallel::parallelism parallelism_tag)
+ {
+ typedef std::iterator_traits<InputIterator> iterator_traits;
+ typedef typename iterator_traits::value_type value_type;
+ typedef typename iterator_traits::iterator_category iterator_category;
+
+ return accumulate_switch(begin, end, init,
+ __gnu_parallel::plus<T, value_type>(),
+ iterator_category(), parallelism_tag);
+ }
template<typename InputIterator, typename T>
- inline T
- accumulate(InputIterator begin, InputIterator end, T init)
- {
- typedef std::iterator_traits<InputIterator> iterator_traits;
- typedef typename iterator_traits::value_type value_type;
- typedef typename iterator_traits::iterator_category iterator_category;
-
- return accumulate_switch(begin, end, init, __gnu_parallel::plus<T, value_type>(),
- iterator_category());
- }
+ inline T
+ accumulate(InputIterator begin, InputIterator end, T init)
+ {
+ typedef std::iterator_traits<InputIterator> iterator_traits;
+ typedef typename iterator_traits::value_type value_type;
+ typedef typename iterator_traits::iterator_category iterator_category;
+
+ return accumulate_switch(begin, end, init,
+ __gnu_parallel::plus<T, value_type>(),
+ iterator_category());
+ }
template<typename InputIterator, typename T, typename BinaryOperation>
- inline T
- accumulate(InputIterator begin, InputIterator end, T init,
- BinaryOperation binary_op,
- __gnu_parallel::parallelism parallelism_tag)
- {
- typedef iterator_traits<InputIterator> iterator_traits;
- typedef typename iterator_traits::iterator_category iterator_category;
- return accumulate_switch(begin, end, init, binary_op,
- iterator_category(), parallelism_tag);
- }
+ inline T
+ accumulate(InputIterator begin, InputIterator end, T init,
+ BinaryOperation binary_op,
+ __gnu_parallel::parallelism parallelism_tag)
+ {
+ typedef iterator_traits<InputIterator> iterator_traits;
+ typedef typename iterator_traits::iterator_category iterator_category;
+ return accumulate_switch(begin, end, init, binary_op,
+ iterator_category(), parallelism_tag);
+ }
template<typename InputIterator, typename T, typename BinaryOperation>
- inline T
- accumulate(InputIterator begin, InputIterator end, T init,
- BinaryOperation binary_op)
- {
- typedef iterator_traits<InputIterator> iterator_traits;
- typedef typename iterator_traits::iterator_category iterator_category;
- return accumulate_switch(begin, end, init, binary_op,
- iterator_category());
- }
+ inline T
+ accumulate(InputIterator begin, InputIterator end, T init,
+ BinaryOperation binary_op)
+ {
+ typedef iterator_traits<InputIterator> iterator_traits;
+ typedef typename iterator_traits::iterator_category iterator_category;
+ return accumulate_switch(begin, end, init, binary_op,
+ iterator_category());
+ }
// Sequential fallback.
template<typename InputIterator1, typename InputIterator2, typename T>
- inline T
- inner_product(InputIterator1 first1, InputIterator1 last1,
- InputIterator2 first2, T init, __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init); }
-
- template<typename InputIterator1, typename InputIterator2, typename T, typename BinaryFunction1, typename BinaryFunction2>
- inline T
- inner_product(InputIterator1 first1, InputIterator1 last1,
- InputIterator2 first2, T init, BinaryFunction1 binary_op1,
- BinaryFunction2 binary_op2, __gnu_parallel::sequential_tag)
- {
- return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init,
- binary_op1, binary_op2);
- }
+ inline T
+ inner_product(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, T init,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init); }
+
+ template<typename InputIterator1, typename InputIterator2, typename T,
+ typename BinaryFunction1, typename BinaryFunction2>
+ inline T
+ inner_product(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, T init, BinaryFunction1 binary_op1,
+ BinaryFunction2 binary_op2, __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init,
+ binary_op1, binary_op2); }
// Parallel algorithm for random access iterators.
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename T, typename BinaryFunction1, typename BinaryFunction2>
- T
- inner_product_switch(RandomAccessIterator1 first1, RandomAccessIterator1 last1, RandomAccessIterator2 first2, T init, BinaryFunction1 binary_op1, BinaryFunction2 binary_op2, random_access_iterator_tag, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_unbalanced)
- {
- if (_GLIBCXX_PARALLEL_CONDITION((last1 - first1) >= __gnu_parallel::Settings::accumulate_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
- {
- T res = init;
- __gnu_parallel::inner_product_selector<RandomAccessIterator1, RandomAccessIterator2, T> my_selector(first1, first2);
- __gnu_parallel::for_each_template_random_access(first1, last1, binary_op2, my_selector, binary_op1, res, res, -1, parallelism_tag);
- return res;
- }
- else
- return inner_product(first1, last1, first2, init,
- __gnu_parallel::sequential_tag());
- }
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename T, typename BinaryFunction1, typename BinaryFunction2>
+ T
+ inner_product_switch(RandomAccessIterator1 first1,
+ RandomAccessIterator1 last1,
+ RandomAccessIterator2 first2, T init,
+ BinaryFunction1 binary_op1,
+ BinaryFunction2 binary_op2,
+ random_access_iterator_tag,
+ random_access_iterator_tag,
+ __gnu_parallel::parallelism parallelism_tag
+ = __gnu_parallel::parallel_unbalanced)
+ {
+ if (_GLIBCXX_PARALLEL_CONDITION((last1 - first1)
+ >= __gnu_parallel::Settings::
+ accumulate_minimal_n
+ && __gnu_parallel::
+ is_parallel(parallelism_tag)))
+ {
+ T res = init;
+ __gnu_parallel::
+ inner_product_selector<RandomAccessIterator1,
+ RandomAccessIterator2, T> my_selector(first1, first2);
+ __gnu_parallel::
+ for_each_template_random_access(first1, last1, binary_op2,
+ my_selector, binary_op1,
+ res, res, -1, parallelism_tag);
+ return res;
+ }
+ else
+ return inner_product(first1, last1, first2, init,
+ __gnu_parallel::sequential_tag());
+ }
// No parallelism for input iterators.
- template<typename InputIterator1, typename InputIterator2, typename T, typename BinaryFunction1, typename BinaryFunction2, typename IteratorTag1, typename IteratorTag2>
- inline T
- inner_product_switch(InputIterator1 first1, InputIterator1 last1,
- InputIterator2 first2, T init,
- BinaryFunction1 binary_op1, BinaryFunction2 binary_op2,
- IteratorTag1, IteratorTag2)
- {
- return inner_product(first1, last1, first2, init, binary_op1, binary_op2,
- __gnu_parallel::sequential_tag());
- }
-
- template<typename InputIterator1, typename InputIterator2, typename T, typename BinaryFunction1, typename BinaryFunction2>
- inline T
- inner_product(InputIterator1 first1, InputIterator1 last1,
- InputIterator2 first2, T init, BinaryFunction1 binary_op1,
- BinaryFunction2 binary_op2,
- __gnu_parallel::parallelism parallelism_tag)
- {
- 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 inner_product_switch(first1, last1, first2, init, binary_op1,
- binary_op2, iterator1_category(),
- iterator2_category(), parallelism_tag);
- }
-
- template<typename InputIterator1, typename InputIterator2, typename T, typename BinaryFunction1, typename BinaryFunction2>
- inline T
- inner_product(InputIterator1 first1, InputIterator1 last1,
- InputIterator2 first2, T init, BinaryFunction1 binary_op1,
- BinaryFunction2 binary_op2)
- {
- 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 inner_product_switch(first1, last1, first2, init, binary_op1,
- binary_op2, iterator1_category(),
- iterator2_category());
- }
+ template<typename InputIterator1, typename InputIterator2, typename T,
+ typename BinaryFunction1, typename BinaryFunction2,
+ typename IteratorTag1, typename IteratorTag2>
+ inline T
+ inner_product_switch(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, T init,
+ BinaryFunction1 binary_op1,
+ BinaryFunction2 binary_op2,
+ IteratorTag1, IteratorTag2)
+ { return inner_product(first1, last1, first2, init,
+ binary_op1, binary_op2,
+ __gnu_parallel::sequential_tag()); }
+
+ template<typename InputIterator1, typename InputIterator2, typename T,
+ typename BinaryFunction1, typename BinaryFunction2>
+ inline T
+ inner_product(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, T init, BinaryFunction1 binary_op1,
+ BinaryFunction2 binary_op2,
+ __gnu_parallel::parallelism parallelism_tag)
+ {
+ 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 inner_product_switch(first1, last1, first2, init, binary_op1,
+ binary_op2, iterator1_category(),
+ iterator2_category(), parallelism_tag);
+ }
+
+ template<typename InputIterator1, typename InputIterator2, typename T,
+ typename BinaryFunction1, typename BinaryFunction2>
+ inline T
+ inner_product(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, T init, BinaryFunction1 binary_op1,
+ BinaryFunction2 binary_op2)
+ {
+ 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 inner_product_switch(first1, last1, first2, init, binary_op1,
+ binary_op2, iterator1_category(),
+ iterator2_category());
+ }
template<typename InputIterator1, typename InputIterator2, typename T>
- inline T
- inner_product(InputIterator1 first1, InputIterator1 last1,
- InputIterator2 first2, T init,
- __gnu_parallel::parallelism parallelism_tag)
- {
- typedef iterator_traits<InputIterator1> traits_type1;
- typedef typename traits_type1::value_type value_type1;
- typedef iterator_traits<InputIterator2> traits_type2;
- typedef typename traits_type2::value_type value_type2;
+ inline T
+ inner_product(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, T init,
+ __gnu_parallel::parallelism parallelism_tag)
+ {
+ typedef iterator_traits<InputIterator1> traits_type1;
+ typedef typename traits_type1::value_type value_type1;
+ typedef iterator_traits<InputIterator2> traits_type2;
+ typedef typename traits_type2::value_type value_type2;
- typedef typename __gnu_parallel::multiplies<value_type1, value_type2>::result
+ typedef typename
+ __gnu_parallel::multiplies<value_type1, value_type2>::result
multiplies_result_type;
- return inner_product(first1, last1, first2, init,
+ return inner_product(first1, last1, first2, init,
__gnu_parallel::plus<T, multiplies_result_type>(),
- __gnu_parallel::multiplies<value_type1, value_type2>(),
+ __gnu_parallel::
+ multiplies<value_type1, value_type2>(),
parallelism_tag);
- }
+ }
template<typename InputIterator1, typename InputIterator2, typename T>
- inline T
- inner_product(InputIterator1 first1, InputIterator1 last1,
- InputIterator2 first2, T init)
- {
- typedef iterator_traits<InputIterator1> traits_type1;
- typedef typename traits_type1::value_type value_type1;
- typedef iterator_traits<InputIterator2> traits_type2;
- typedef typename traits_type2::value_type value_type2;
+ inline T
+ inner_product(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, T init)
+ {
+ typedef iterator_traits<InputIterator1> traits_type1;
+ typedef typename traits_type1::value_type value_type1;
+ typedef iterator_traits<InputIterator2> traits_type2;
+ typedef typename traits_type2::value_type value_type2;
- typedef typename __gnu_parallel::multiplies<value_type1, value_type2>::result
+ typedef typename
+ __gnu_parallel::multiplies<value_type1, value_type2>::result
multiplies_result_type;
- return inner_product(first1, last1, first2, init,
+ return inner_product(first1, last1, first2, init,
__gnu_parallel::plus<T, multiplies_result_type>(),
- __gnu_parallel::multiplies<value_type1, value_type2>());
- }
+ __gnu_parallel::
+ multiplies<value_type1, value_type2>());
+ }
// Sequential fallback.
template<typename InputIterator, typename OutputIterator>
- inline OutputIterator
- partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
- __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::partial_sum(begin, end, result); }
+ inline OutputIterator
+ partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::partial_sum(begin, end, result); }
// Sequential fallback.
- template<typename InputIterator, typename OutputIterator, typename BinaryOperation>
- inline OutputIterator
- partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
- BinaryOperation bin_op, __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::partial_sum(begin, end, result, bin_op); }
+ template<typename InputIterator, typename OutputIterator,
+ typename BinaryOperation>
+ inline OutputIterator
+ partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
+ BinaryOperation bin_op, __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::partial_sum(begin, end, result, bin_op); }
// Sequential fallback for input iterator case.
- template<typename InputIterator, typename OutputIterator, typename BinaryOperation, typename IteratorTag1, typename IteratorTag2>
- inline OutputIterator
- partial_sum_switch(InputIterator begin, InputIterator end, OutputIterator result, BinaryOperation bin_op, IteratorTag1, IteratorTag2)
- {
- return _GLIBCXX_STD_P::partial_sum(begin, end, result, bin_op);
- }
+ template<typename InputIterator, typename OutputIterator,
+ typename BinaryOperation, typename IteratorTag1,
+ typename IteratorTag2>
+ inline OutputIterator
+ partial_sum_switch(InputIterator begin, InputIterator end,
+ OutputIterator result, BinaryOperation bin_op,
+ IteratorTag1, IteratorTag2)
+ { return _GLIBCXX_STD_P::partial_sum(begin, end, result, bin_op); }
// Parallel algorithm for random access iterators.
- template<typename InputIterator, typename OutputIterator, typename BinaryOperation>
- OutputIterator
- partial_sum_switch(InputIterator begin, InputIterator end,
- OutputIterator result, BinaryOperation bin_op,
- random_access_iterator_tag, random_access_iterator_tag)
- {
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::partial_sum_minimal_n))
- return __gnu_parallel::parallel_partial_sum(begin, end, result, bin_op);
- else
- return partial_sum(begin, end, result, bin_op, __gnu_parallel::sequential_tag());
- }
+ template<typename InputIterator, typename OutputIterator,
+ typename BinaryOperation>
+ OutputIterator
+ partial_sum_switch(InputIterator begin, InputIterator end,
+ OutputIterator result, BinaryOperation bin_op,
+ random_access_iterator_tag, random_access_iterator_tag)
+ {
+ if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::
+ sequence_index_t>(end - begin)
+ >= __gnu_parallel::Settings::
+ partial_sum_minimal_n))
+ return __gnu_parallel::parallel_partial_sum(begin, end,
+ result, bin_op);
+ else
+ return partial_sum(begin, end, result, bin_op,
+ __gnu_parallel::sequential_tag());
+ }
// Public interface.
template<typename InputIterator, typename OutputIterator>
- inline OutputIterator
- partial_sum(InputIterator begin, InputIterator end, OutputIterator result)
- {
- typedef typename iterator_traits<InputIterator>::value_type value_type;
- return partial_sum(begin, end, result, std::plus<value_type>());
- }
+ inline OutputIterator
+ partial_sum(InputIterator begin, InputIterator end, OutputIterator result)
+ {
+ typedef typename iterator_traits<InputIterator>::value_type value_type;
+ return partial_sum(begin, end, result, std::plus<value_type>());
+ }
// Public interface
- template<typename InputIterator, typename OutputIterator, typename BinaryOperation>
- inline OutputIterator
- partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
- BinaryOperation binary_op)
- {
- typedef iterator_traits<InputIterator> traitsi_type;
- typedef typename traitsi_type::iterator_category iteratori_category;
-
- typedef iterator_traits<OutputIterator> traitso_type;
- typedef typename traitso_type::iterator_category iteratoro_category;
-
- return partial_sum_switch(begin, end, result, binary_op,
- iteratori_category(), iteratoro_category());
- }
+ template<typename InputIterator, typename OutputIterator,
+ typename BinaryOperation>
+ inline OutputIterator
+ partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
+ BinaryOperation binary_op)
+ {
+ typedef iterator_traits<InputIterator> traitsi_type;
+ typedef typename traitsi_type::iterator_category iteratori_category;
+
+ typedef iterator_traits<OutputIterator> traitso_type;
+ typedef typename traitso_type::iterator_category iteratoro_category;
+
+ return partial_sum_switch(begin, end, result, binary_op,
+ iteratori_category(), iteratoro_category());
+ }
// Sequential fallback.
template<typename InputIterator, typename OutputIterator>
- inline OutputIterator
- adjacent_difference(InputIterator begin, InputIterator end,
- OutputIterator result, __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::adjacent_difference(begin, end, result); }
+ inline OutputIterator
+ adjacent_difference(InputIterator begin, InputIterator end,
+ OutputIterator result, __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::adjacent_difference(begin, end, result); }
// Sequential fallback.
- template<typename InputIterator, typename OutputIterator, typename BinaryOperation>
- inline OutputIterator
- adjacent_difference(InputIterator begin, InputIterator end,
- OutputIterator result, BinaryOperation bin_op,
- __gnu_parallel::sequential_tag)
- {
- return _GLIBCXX_STD_P::adjacent_difference(begin, end, result, bin_op);
- }
+ template<typename InputIterator, typename OutputIterator,
+ typename BinaryOperation>
+ inline OutputIterator
+ adjacent_difference(InputIterator begin, InputIterator end,
+ OutputIterator result, BinaryOperation bin_op,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::adjacent_difference(begin, end, result, bin_op); }
// Sequential fallback for input iterator case.
- template<typename InputIterator, typename OutputIterator, typename BinaryOperation, typename IteratorTag1, typename IteratorTag2>
- inline OutputIterator
- adjacent_difference_switch(InputIterator begin, InputIterator end,
- OutputIterator result, BinaryOperation bin_op,
+ template<typename InputIterator, typename OutputIterator,
+ typename BinaryOperation, typename IteratorTag1,
+ typename IteratorTag2>
+ inline OutputIterator
+ adjacent_difference_switch(InputIterator begin, InputIterator end,
+ OutputIterator result, BinaryOperation bin_op,
IteratorTag1, IteratorTag2)
- {
- return adjacent_difference(begin, end, result, bin_op,
- __gnu_parallel::sequential_tag());
- }
+ { return adjacent_difference(begin, end, result, bin_op,
+ __gnu_parallel::sequential_tag()); }
// Parallel algorithm for random access iterators.
- template<typename InputIterator, typename OutputIterator, typename BinaryOperation>
- OutputIterator
- adjacent_difference_switch(InputIterator begin, InputIterator end,
- OutputIterator result, BinaryOperation bin_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::adjacent_difference_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
- {
- bool dummy = true;
- typedef __gnu_parallel::iterator_pair<InputIterator, OutputIterator, random_access_iterator_tag> ip;
- *result = *begin;
- ip begin_pair(begin + 1, result + 1), end_pair(end, result + (end - begin));
- __gnu_parallel::adjacent_difference_selector<ip> functionality;
- __gnu_parallel::for_each_template_random_access(begin_pair, end_pair, bin_op, functionality, __gnu_parallel::dummy_reduct(), dummy, dummy, -1, parallelism_tag);
- return functionality.finish_iterator;
- }
- else
- return adjacent_difference(begin, end, result, bin_op,
- __gnu_parallel::sequential_tag());
- }
+ template<typename InputIterator, typename OutputIterator,
+ typename BinaryOperation>
+ OutputIterator
+ adjacent_difference_switch(InputIterator begin, InputIterator end,
+ OutputIterator result, BinaryOperation bin_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::adjacent_difference_minimal_n
+ && __gnu_parallel::is_parallel(parallelism_tag)))
+ {
+ bool dummy = true;
+ typedef __gnu_parallel::iterator_pair<InputIterator, OutputIterator,
+ random_access_iterator_tag> ip;
+ *result = *begin;
+ ip begin_pair(begin + 1, result + 1),
+ end_pair(end, result + (end - begin));
+ __gnu_parallel::adjacent_difference_selector<ip> functionality;
+ __gnu_parallel::
+ for_each_template_random_access(begin_pair, end_pair, bin_op,
+ functionality,
+ __gnu_parallel::dummy_reduct(),
+ dummy, dummy, -1, parallelism_tag);
+ return functionality.finish_iterator;
+ }
+ else
+ return adjacent_difference(begin, end, result, bin_op,
+ __gnu_parallel::sequential_tag());
+ }
// Public interface.
template<typename InputIterator, typename OutputIterator>
- inline OutputIterator
- adjacent_difference(InputIterator begin, InputIterator end,
- OutputIterator result,
- __gnu_parallel::parallelism parallelism_tag)
- {
- typedef iterator_traits<InputIterator> traits_type;
- typedef typename traits_type::value_type value_type;
- return adjacent_difference(begin, end, result, std::minus<value_type>(),
- parallelism_tag);
- }
+ inline OutputIterator
+ adjacent_difference(InputIterator begin, InputIterator end,
+ OutputIterator result,
+ __gnu_parallel::parallelism parallelism_tag)
+ {
+ typedef iterator_traits<InputIterator> traits_type;
+ typedef typename traits_type::value_type value_type;
+ return adjacent_difference(begin, end, result, std::minus<value_type>(),
+ parallelism_tag);
+ }
template<typename InputIterator, typename OutputIterator>
- inline OutputIterator
- adjacent_difference(InputIterator begin, InputIterator end,
- OutputIterator result)
- {
- typedef iterator_traits<InputIterator> traits_type;
- typedef typename traits_type::value_type value_type;
- return adjacent_difference(begin, end, result, std::minus<value_type>());
- }
-
- template<typename InputIterator, typename OutputIterator, typename BinaryOperation>
- inline OutputIterator
- adjacent_difference(InputIterator begin, InputIterator end,
- OutputIterator result, BinaryOperation binary_op,
- __gnu_parallel::parallelism parallelism_tag)
- {
- typedef iterator_traits<InputIterator> traitsi_type;
- typedef typename traitsi_type::iterator_category iteratori_category;
-
- typedef iterator_traits<OutputIterator> traitso_type;
- typedef typename traitso_type::iterator_category iteratoro_category;
-
- return adjacent_difference_switch(begin, end, result, binary_op,
- iteratori_category(),
- iteratoro_category(), parallelism_tag);
- }
-
- template<typename InputIterator, typename OutputIterator, typename BinaryOperation>
- inline OutputIterator
- adjacent_difference(InputIterator begin, InputIterator end,
- OutputIterator result, BinaryOperation binary_op)
- {
- typedef iterator_traits<InputIterator> traitsi_type;
- typedef typename traitsi_type::iterator_category iteratori_category;
-
- typedef iterator_traits<OutputIterator> traitso_type;
- typedef typename traitso_type::iterator_category iteratoro_category;
-
- return adjacent_difference_switch(begin, end, result, binary_op,
- iteratori_category(),
- iteratoro_category());
- }
+ inline OutputIterator
+ adjacent_difference(InputIterator begin, InputIterator end,
+ OutputIterator result)
+ {
+ typedef iterator_traits<InputIterator> traits_type;
+ typedef typename traits_type::value_type value_type;
+ return adjacent_difference(begin, end, result, std::minus<value_type>());
+ }
+
+ template<typename InputIterator, typename OutputIterator,
+ typename BinaryOperation>
+ inline OutputIterator
+ adjacent_difference(InputIterator begin, InputIterator end,
+ OutputIterator result, BinaryOperation binary_op,
+ __gnu_parallel::parallelism parallelism_tag)
+ {
+ typedef iterator_traits<InputIterator> traitsi_type;
+ typedef typename traitsi_type::iterator_category iteratori_category;
+
+ typedef iterator_traits<OutputIterator> traitso_type;
+ typedef typename traitso_type::iterator_category iteratoro_category;
+
+ return adjacent_difference_switch(begin, end, result, binary_op,
+ iteratori_category(),
+ iteratoro_category(), parallelism_tag);
+ }
+
+ template<typename InputIterator, typename OutputIterator,
+ typename BinaryOperation>
+ inline OutputIterator
+ adjacent_difference(InputIterator begin, InputIterator end,
+ OutputIterator result, BinaryOperation binary_op)
+ {
+ typedef iterator_traits<InputIterator> traitsi_type;
+ typedef typename traitsi_type::iterator_category iteratori_category;
+
+ typedef iterator_traits<OutputIterator> traitso_type;
+ typedef typename traitso_type::iterator_category iteratoro_category;
+
+ return adjacent_difference_switch(begin, end, result, binary_op,
+ iteratori_category(),
+ iteratoro_category());
+ }
} // end namespace
} // end namespace
Index: include/parallel/quicksort.h
===================================================================
--- include/parallel/quicksort.h (revision 131429)
+++ include/parallel/quicksort.h (working copy)
@@ -53,48 +53,46 @@
* this part.
*/
template<typename RandomAccessIterator, typename Comparator>
- inline
- typename std::iterator_traits<RandomAccessIterator>::difference_type
- parallel_sort_qs_divide(
- RandomAccessIterator begin,
- RandomAccessIterator end,
- Comparator comp,
- typename std::iterator_traits<RandomAccessIterator>::difference_type
- pivot_rank,
- typename std::iterator_traits<RandomAccessIterator>::difference_type
- num_samples,
- thread_index_t num_threads)
- {
- typedef std::iterator_traits<RandomAccessIterator> traits_type;
- typedef typename traits_type::value_type value_type;
- typedef typename traits_type::difference_type difference_type;
-
- difference_type n = end - begin;
- num_samples = std::min(num_samples, n);
-
- // Allocate uninitialized, to avoid default constructor.
- value_type* samples = static_cast<value_type*>(
- ::operator new(num_samples * sizeof(value_type)));
-
- for (difference_type s = 0; s < num_samples; ++s)
- {
- const unsigned long long index = static_cast<unsigned long long>(s)
- * n / num_samples;
- ::new(&(samples[s])) value_type(begin[index]);
- }
+ typename std::iterator_traits<RandomAccessIterator>::difference_type
+ parallel_sort_qs_divide(RandomAccessIterator begin,
+ RandomAccessIterator end,
+ Comparator comp, typename std::iterator_traits
+ <RandomAccessIterator>::difference_type pivot_rank,
+ typename std::iterator_traits
+ <RandomAccessIterator>::difference_type
+ num_samples, thread_index_t num_threads)
+ {
+ typedef std::iterator_traits<RandomAccessIterator> traits_type;
+ typedef typename traits_type::value_type value_type;
+ typedef typename traits_type::difference_type difference_type;
+
+ difference_type n = end - begin;
+ num_samples = std::min(num_samples, n);
+
+ // Allocate uninitialized, to avoid default constructor.
+ value_type* samples =
+ static_cast<value_type*>(::operator new(num_samples
+ * sizeof(value_type)));
+
+ for (difference_type s = 0; s < num_samples; ++s)
+ {
+ const unsigned long long index = static_cast<unsigned long long>(s)
+ * n / num_samples;
+ ::new(&(samples[s])) value_type(begin[index]);
+ }
- __gnu_sequential::sort(samples, samples + num_samples, comp);
+ __gnu_sequential::sort(samples, samples + num_samples, comp);
- value_type& pivot = samples[pivot_rank * num_samples / n];
+ value_type& pivot = samples[pivot_rank * num_samples / n];
- __gnu_parallel::binder2nd<Comparator, value_type, value_type, bool>
+ __gnu_parallel::binder2nd<Comparator, value_type, value_type, bool>
pred(comp, pivot);
- difference_type split = parallel_partition(begin, end, pred, num_threads);
+ difference_type split = parallel_partition(begin, end, pred, num_threads);
- ::operator delete(samples);
+ ::operator delete(samples);
- return split;
- }
+ return split;
+ }
/** @brief Unbalanced quicksort conquer step.
* @param begin Begin iterator of subsequence.
@@ -104,50 +102,51 @@
* this part.
*/
template<typename RandomAccessIterator, typename Comparator>
- inline void
- parallel_sort_qs_conquer(RandomAccessIterator begin,
- RandomAccessIterator end,
- Comparator comp,
- thread_index_t num_threads)
- {
- typedef std::iterator_traits<RandomAccessIterator> traits_type;
- typedef typename traits_type::value_type value_type;
- typedef typename traits_type::difference_type difference_type;
-
- if (num_threads <= 1)
- {
- __gnu_sequential::sort(begin, end, comp);
- return;
- }
-
- difference_type n = end - begin, pivot_rank;
-
- if (n <= 1)
- return;
-
- thread_index_t num_threads_left;
-
- if ((num_threads % 2) == 1)
- num_threads_left = num_threads / 2 + 1;
- else
- num_threads_left = num_threads / 2;
-
- pivot_rank = n * num_threads_left / num_threads;
-
- difference_type split = parallel_sort_qs_divide(
- begin, end, comp, pivot_rank,
- Settings::sort_qs_num_samples_preset, num_threads);
+ void
+ parallel_sort_qs_conquer(RandomAccessIterator begin,
+ RandomAccessIterator end,
+ Comparator comp,
+ thread_index_t num_threads)
+ {
+ typedef std::iterator_traits<RandomAccessIterator> traits_type;
+ typedef typename traits_type::value_type value_type;
+ typedef typename traits_type::difference_type difference_type;
+
+ if (num_threads <= 1)
+ {
+ __gnu_sequential::sort(begin, end, comp);
+ return;
+ }
+
+ difference_type n = end - begin, pivot_rank;
+
+ if (n <= 1)
+ return;
+
+ thread_index_t num_threads_left;
+
+ if ((num_threads % 2) == 1)
+ num_threads_left = num_threads / 2 + 1;
+ else
+ num_threads_left = num_threads / 2;
+
+ pivot_rank = n * num_threads_left / num_threads;
+
+ difference_type split =
+ parallel_sort_qs_divide(begin, end, comp, pivot_rank,
+ Settings::sort_qs_num_samples_preset,
+ num_threads);
#pragma omp parallel sections
- {
+ {
#pragma omp section
- parallel_sort_qs_conquer(begin, begin + split,
- comp, num_threads_left);
+ parallel_sort_qs_conquer(begin, begin + split,
+ comp, num_threads_left);
#pragma omp section
- parallel_sort_qs_conquer(begin + split, end,
- comp, num_threads - num_threads_left);
+ parallel_sort_qs_conquer(begin + split, end,
+ comp, num_threads - num_threads_left);
+ }
}
- }
@@ -160,34 +159,33 @@
* this part.
*/
template<typename RandomAccessIterator, typename Comparator>
- inline void
- parallel_sort_qs(
- RandomAccessIterator begin,
- RandomAccessIterator end,
- Comparator comp,
- typename std::iterator_traits<RandomAccessIterator>::difference_type n,
- int num_threads)
- {
- _GLIBCXX_CALL(n)
-
- typedef std::iterator_traits<RandomAccessIterator> traits_type;
- typedef typename traits_type::value_type value_type;
- typedef typename traits_type::difference_type difference_type;
-
- if (n == 0)
- return;
-
- // At least one element per processor.
- if (num_threads > n)
- num_threads = static_cast<thread_index_t>(n);
+ void
+ parallel_sort_qs(RandomAccessIterator begin,
+ RandomAccessIterator end,
+ Comparator comp, typename std::iterator_traits
+ <RandomAccessIterator>::difference_type n,
+ int num_threads)
+ {
+ _GLIBCXX_CALL(n)
+
+ typedef std::iterator_traits<RandomAccessIterator> traits_type;
+ typedef typename traits_type::value_type value_type;
+ typedef typename traits_type::difference_type difference_type;
+
+ if (n == 0)
+ return;
- Settings::sort_qs_num_samples_preset = 100;
+ // At least one element per processor.
+ if (num_threads > n)
+ num_threads = static_cast<thread_index_t>(n);
- // Hard to avoid.
- omp_set_num_threads(num_threads);
+ Settings::sort_qs_num_samples_preset = 100;
- parallel_sort_qs_conquer(begin, begin + n, comp, num_threads);
- }
+ // Hard to avoid.
+ omp_set_num_threads(num_threads);
+
+ parallel_sort_qs_conquer(begin, begin + n, comp, num_threads);
+ }
} //namespace __gnu_parallel
Index: include/parallel/algorithmfwd.h
===================================================================
--- include/parallel/algorithmfwd.h (revision 131431)
+++ include/parallel/algorithmfwd.h (working copy)
@@ -454,8 +454,8 @@
_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,
+ __gnu_parallel::parallelism);
template<typename _IIter1, typename _IIter2, typename _OIter,
typename _BiOperation, typename _Tag1,
@@ -525,7 +525,7 @@
template<typename _FIter>
_FIter
- max_element(_FIter, _FIter, __gnu_parallel::parallelism parallelism_tag);
+ max_element(_FIter, _FIter, __gnu_parallel::parallelism);
template<typename _FIter, typename _Compare>
_FIter
Index: include/parallel/for_each_selectors.h
===================================================================
--- include/parallel/for_each_selectors.h (revision 131431)
+++ include/parallel/for_each_selectors.h (working copy)
@@ -57,231 +57,234 @@
/** @brief std::for_each() selector. */
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>
- bool
- operator()(Op& o, It i)
- {
- o(*i);
- return true;
- }
- };
+ struct for_each_selector : public generic_for_each_selector<It>
+ {
+ /** @brief Functor execution.
+ * @param o Operator.
+ * @param i Iterator referencing object. */
+ template<typename Op>
+ bool
+ operator()(Op& o, It i)
+ {
+ o(*i);
+ return true;
+ }
+ };
/** @brief std::generate() selector. */
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>
- bool
- operator()(Op& o, It i)
- {
- *i = o();
- return true;
- }
- };
+ struct generate_selector : public generic_for_each_selector<It>
+ {
+ /** @brief Functor execution.
+ * @param o Operator.
+ * @param i Iterator referencing object. */
+ template<typename Op>
+ bool
+ operator()(Op& o, It i)
+ {
+ *i = o();
+ return true;
+ }
+ };
/** @brief std::fill() selector. */
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>
- bool
- operator()(Val& v, It i)
- {
- *i = v;
- return true;
- }
- };
+ struct fill_selector : public generic_for_each_selector<It>
+ {
+ /** @brief Functor execution.
+ * @param v Current value.
+ * @param i Iterator referencing object. */
+ template<typename Val>
+ bool
+ operator()(Val& v, It i)
+ {
+ *i = v;
+ return true;
+ }
+ };
/** @brief std::transform() selector, one input sequence variant. */
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>
- bool
- operator()(Op& o, It i)
- {
- *i.second = o(*i.first);
- return true;
- }
- };
+ struct transform1_selector : public generic_for_each_selector<It>
+ {
+ /** @brief Functor execution.
+ * @param o Operator.
+ * @param i Iterator referencing object. */
+ template<typename Op>
+ bool
+ operator()(Op& o, It i)
+ {
+ *i.second = o(*i.first);
+ return true;
+ }
+ };
/** @brief std::transform() selector, two input sequences variant. */
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>
- bool
- operator()(Op& o, It i)
- {
- *i.third = o(*i.first, *i.second);
- return true;
- }
- };
+ struct transform2_selector : public generic_for_each_selector<It>
+ {
+ /** @brief Functor execution.
+ * @param o Operator.
+ * @param i Iterator referencing object. */
+ template<typename Op>
+ bool
+ operator()(Op& o, It i)
+ {
+ *i.third = o(*i.first, *i.second);
+ return true;
+ }
+ };
/** @brief std::replace() selector. */
template<typename It, typename T>
- struct replace_selector : public generic_for_each_selector<It>
- {
- /** @brief Value to replace with. */
- const T& new_val;
-
- /** @brief Constructor
- * @param new_val Value to replace with. */
- explicit replace_selector(const T &new_val) : new_val(new_val) {}
-
- /** @brief Functor execution.
- * @param v Current value.
- * @param i Iterator referencing object. */
- bool
- operator()(T& v, It i)
+ struct replace_selector : public generic_for_each_selector<It>
{
- if (*i == v)
- *i = new_val;
- return true;
- }
- };
+ /** @brief Value to replace with. */
+ const T& new_val;
+
+ /** @brief Constructor
+ * @param new_val Value to replace with. */
+ explicit
+ replace_selector(const T &new_val) : new_val(new_val) {}
+
+ /** @brief Functor execution.
+ * @param v Current value.
+ * @param i Iterator referencing object. */
+ bool
+ operator()(T& v, It i)
+ {
+ if (*i == v)
+ *i = new_val;
+ return true;
+ }
+ };
/** @brief std::replace() selector. */
template<typename It, typename Op, typename T>
- struct replace_if_selector : public generic_for_each_selector<It>
- {
- /** @brief Value to replace with. */
- const T& new_val;
-
- /** @brief Constructor.
- * @param new_val Value to replace with. */
- explicit replace_if_selector(const T &new_val) : new_val(new_val) { }
-
- /** @brief Functor execution.
- * @param o Operator.
- * @param i Iterator referencing object. */
- bool
- operator()(Op& o, It i)
+ struct replace_if_selector : public generic_for_each_selector<It>
{
- if (o(*i))
- *i = new_val;
- return true;
- }
- };
+ /** @brief Value to replace with. */
+ const T& new_val;
+
+ /** @brief Constructor.
+ * @param new_val Value to replace with. */
+ explicit
+ replace_if_selector(const T &new_val) : new_val(new_val) { }
+
+ /** @brief Functor execution.
+ * @param o Operator.
+ * @param i Iterator referencing object. */
+ bool
+ operator()(Op& o, It i)
+ {
+ if (o(*i))
+ *i = new_val;
+ return true;
+ }
+ };
/** @brief std::count() selector. */
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>
- Diff
- operator()(Val& v, It i)
- { return (v == *i) ? 1 : 0; }
- };
+ 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>
+ Diff
+ operator()(Val& v, It i)
+ { return (v == *i) ? 1 : 0; }
+ };
/** @brief std::count_if () selector. */
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>
- Diff
- operator()(Op& o, It i)
- { return (o(*i)) ? 1 : 0; }
- };
+ 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>
+ Diff
+ operator()(Op& o, It i)
+ { return (o(*i)) ? 1 : 0; }
+ };
/** @brief std::accumulate() selector. */
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>
- typename std::iterator_traits<It>::value_type operator()(Op o, It i)
- { return *i; }
- };
+ 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>
+ 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>
- struct inner_product_selector : public generic_for_each_selector<It>
- {
- /** @brief Begin iterator of first sequence. */
- It begin1_iterator;
-
- /** @brief Begin iterator of second sequence. */
- It2 begin2_iterator;
+ struct inner_product_selector : public generic_for_each_selector<It>
+ {
+ /** @brief Begin iterator of first sequence. */
+ It begin1_iterator;
- /** @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) { }
+ /** @brief Begin iterator of second sequence. */
+ It2 begin2_iterator;
- /** @brief Functor execution.
- * @param mult Multiplication functor.
- * @param current Iterator referencing object.
- * @return Inner product elemental result. */
- template<typename Op>
- T
- operator()(Op mult, It current)
- {
- typename std::iterator_traits<It>::difference_type position
- = current - begin1_iterator;
- return mult(*current, *(begin2_iterator + position));
- }
- };
+ /** @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) { }
+
+ /** @brief Functor execution.
+ * @param mult Multiplication functor.
+ * @param current Iterator referencing object.
+ * @return Inner product elemental result. */
+ template<typename Op>
+ T
+ operator()(Op mult, It current)
+ {
+ 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>
- 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>
- It
- operator()(Op o, It i)
- { return i; }
- };
+ 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>
+ It
+ operator()(Op o, It i)
+ { return i; }
+ };
/** @brief Selector that returns the difference between two adjacent
* elements.
*/
template<typename It>
- struct adjacent_difference_selector : public generic_for_each_selector<It>
- {
- template<typename Op>
- bool
- operator()(Op& o, It i)
- {
- typename It::first_type go_back_one = i.first;
- --go_back_one;
- *i.second = o(*i.first, *go_back_one);
- return true;
- }
- };
+ struct adjacent_difference_selector : public generic_for_each_selector<It>
+ {
+ template<typename Op>
+ bool
+ operator()(Op& o, It i)
+ {
+ typename It::first_type go_back_one = i.first;
+ --go_back_one;
+ *i.second = o(*i.first, *go_back_one);
+ return true;
+ }
+ };
// XXX move into type_traits?
/** @brief Functor doing nothing
@@ -308,55 +311,56 @@
/** @brief Reduction for finding the maximum element, using a comparator. */
template<typename Comp, typename It>
- struct min_element_reduct
- {
- Comp& comp;
+ struct min_element_reduct
+ {
+ Comp& comp;
- explicit min_element_reduct(Comp &c) : comp(c)
- { }
+ explicit
+ min_element_reduct(Comp &c) : comp(c) { }
- It
- operator()(It x, It y)
- {
- if (comp(*x, *y))
- return x;
- else
- return y;
- }
- };
+ It
+ operator()(It x, It y)
+ {
+ if (comp(*x, *y))
+ return x;
+ else
+ return y;
+ }
+ };
/** @brief Reduction for finding the maximum element, using a comparator. */
template<typename Comp, typename It>
- struct max_element_reduct
- {
- Comp& comp;
+ struct max_element_reduct
+ {
+ Comp& comp;
- explicit max_element_reduct(Comp& c) : comp(c)
- { }
+ explicit
+ max_element_reduct(Comp& c) : comp(c) { }
- It
- operator()(It x, It y)
- {
- if (comp(*x, *y))
- return y;
- else
- return x;
- }
- };
+ It
+ operator()(It x, It y)
+ {
+ if (comp(*x, *y))
+ return y;
+ else
+ return x;
+ }
+ };
/** @brief General reduction, using a binary operator. */
template<typename BinOp>
- struct accumulate_binop_reduct
- {
- BinOp& binop;
+ struct accumulate_binop_reduct
+ {
+ BinOp& binop;
- explicit accumulate_binop_reduct(BinOp& b) : binop(b) {}
+ explicit
+ accumulate_binop_reduct(BinOp& b) : binop(b) { }
- template<typename Result, typename Addend>
- Result
- operator()(const Result& x, const Addend& y)
- { return binop(x, y); }
- };
+ template<typename Result, typename Addend>
+ Result
+ operator()(const Result& x, const Addend& y)
+ { return binop(x, y); }
+ };
}
#endif
Index: include/parallel/omp_loop_static.h
===================================================================
--- include/parallel/omp_loop_static.h (revision 131429)
+++ include/parallel/omp_loop_static.h (working copy)
@@ -1,6 +1,6 @@
// -*- C++ -*-
-// Copyright (C) 2007 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
@@ -65,25 +65,26 @@
* @return User-supplied functor (that may contain a part of the result).
*/
template<typename RandomAccessIterator,
- typename Op,
- typename Fu,
- typename Red,
- typename Result>
+ typename Op,
+ typename Fu,
+ typename Red,
+ typename Result>
Op
- for_each_template_random_access_omp_loop_static(
- RandomAccessIterator begin,
- RandomAccessIterator end,
- Op o, Fu& f, Red r, Result base, Result& output,
- typename std::iterator_traits<RandomAccessIterator>::
- difference_type bound)
+ for_each_template_random_access_omp_loop_static(RandomAccessIterator begin,
+ RandomAccessIterator end,
+ Op o, Fu& f, Red r,
+ Result base, Result& output,
+ typename std::iterator_traits
+ <RandomAccessIterator>::
+ difference_type bound)
{
typedef typename
- std::iterator_traits<RandomAccessIterator>::difference_type
- difference_type;
+ std::iterator_traits<RandomAccessIterator>::difference_type
+ difference_type;
difference_type length = end - begin;
thread_index_t num_threads =
- std::min<difference_type>(get_max_threads(), length);
+ std::min<difference_type>(get_max_threads(), length);
Result *thread_results;
@@ -94,20 +95,19 @@
num_threads = omp_get_num_threads();
thread_results = new Result[num_threads];
- for (thread_index_t i = 0; i < num_threads; i++)
+ for (thread_index_t i = 0; i < num_threads; ++i)
thread_results[i] = Result();
}
thread_index_t iam = omp_get_thread_num();
# pragma omp for schedule(static, Settings::workstealing_chunk_size)
- for (difference_type pos = 0; pos < length; pos++)
- thread_results[iam] =
- r(thread_results[iam], f(o, begin+pos));
+ for (difference_type pos = 0; pos < length; ++pos)
+ thread_results[iam] = r(thread_results[iam], f(o, begin+pos));
} //parallel
- for (thread_index_t i = 0; i < num_threads; i++)
- output = r(output, thread_results[i]);
+ for (thread_index_t i = 0; i < num_threads; ++i)
+ output = r(output, thread_results[i]);
delete [] thread_results;
Index: include/parallel/random_shuffle.h
===================================================================
--- include/parallel/random_shuffle.h (revision 131429)
+++ include/parallel/random_shuffle.h (working copy)
@@ -124,7 +124,7 @@
/** @brief Random shuffle code executed by each thread.
* @param pus Array of thread-local data records. */
template<typename RandomAccessIterator, typename RandomNumberGenerator>
- inline void
+ void
parallel_random_shuffle_drs_pu(DRSSorterPU<RandomAccessIterator,
RandomNumberGenerator>* pus)
{
@@ -213,8 +213,8 @@
thread_index_t target_p = bin_proc[target_bin];
// Last column [d->num_threads] stays unchanged.
- ::new(&(temporaries[target_p][dist[target_bin + 1]++])) value_type(
- *(source + i + start));
+ ::new(&(temporaries[target_p][dist[target_bin + 1]++]))
+ value_type(*(source + i + start));
}
delete[] oracles;
@@ -260,13 +260,13 @@
* @param rng Random number generator to use.
*/
template<typename RandomAccessIterator, typename RandomNumberGenerator>
- inline void
- parallel_random_shuffle_drs(
- RandomAccessIterator begin,
- RandomAccessIterator end,
- typename std::iterator_traits<RandomAccessIterator>::difference_type n,
- thread_index_t num_threads,
- RandomNumberGenerator& rng)
+ void
+ parallel_random_shuffle_drs(RandomAccessIterator begin,
+ RandomAccessIterator end,
+ typename std::iterator_traits
+ <RandomAccessIterator>::difference_type n,
+ thread_index_t num_threads,
+ RandomNumberGenerator& rng)
{
typedef std::iterator_traits<RandomAccessIterator> traits_type;
typedef typename traits_type::value_type value_type;
@@ -393,7 +393,7 @@
* @param rng Random number generator to use.
*/
template<typename RandomAccessIterator, typename RandomNumberGenerator>
- inline void
+ void
sequential_random_shuffle(RandomAccessIterator begin,
RandomAccessIterator end,
RandomNumberGenerator& rng)
Index: include/parallel/balanced_quicksort.h
===================================================================
--- include/parallel/balanced_quicksort.h (revision 131431)
+++ include/parallel/balanced_quicksort.h (working copy)
@@ -112,8 +112,9 @@
typedef typename traits_type::value_type value_type;
typedef typename traits_type::difference_type difference_type;
- RandomAccessIterator pivot_pos = median_of_three_iterators(
- begin, begin + (end - begin) / 2, end - 1, comp);
+ RandomAccessIterator pivot_pos =
+ median_of_three_iterators(begin, begin + (end - begin) / 2,
+ end - 1, comp);
#if defined(_GLIBCXX_ASSERTIONS)
// Must be in between somewhere.
@@ -146,9 +147,9 @@
#if _GLIBCXX_ASSERTIONS
RandomAccessIterator r;
- for (r = begin; r != pivot_pos; r++)
+ for (r = begin; r != pivot_pos; ++r)
_GLIBCXX_PARALLEL_ASSERT(comp(*r, *pivot_pos));
- for (; r != end; r++)
+ for (; r != end; ++r)
_GLIBCXX_PARALLEL_ASSERT(!comp(*r, *pivot_pos));
#endif
@@ -308,12 +309,12 @@
__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));
+ <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.
@@ -339,8 +340,8 @@
{
// Left side larger.
if (begin != split_pos1)
- tl.leftover_parts.push_front(
- std::make_pair(begin, split_pos1));
+ tl.leftover_parts.push_front(std::make_pair(begin,
+ split_pos1));
current.first = split_pos2;
//current.second = end; //already set anyway
@@ -394,8 +395,8 @@
if (omp_get_wtime() >= (search_start + 1.0))
{
sleep(1);
- _GLIBCXX_PARALLEL_ASSERT(
- omp_get_wtime() < (search_start + 1.0));
+ _GLIBCXX_PARALLEL_ASSERT(omp_get_wtime()
+ < (search_start + 1.0));
}
#endif
if (!successfully_stolen)
@@ -452,7 +453,7 @@
// 2. The largest range has at most length n
// 3. Each range is larger than half of the range remaining
volatile difference_type elements_leftover = n;
- for (int i = 0; i < num_threads; i++)
+ for (int i = 0; i < num_threads; ++i)
{
tls[i]->elements_leftover = &elements_leftover;
tls[i]->num_threads = num_threads;
@@ -468,11 +469,11 @@
#if _GLIBCXX_ASSERTIONS
// All stack must be empty.
Piece dummy;
- for (int i = 1; i < num_threads; i++)
+ for (int i = 1; i < num_threads; ++i)
_GLIBCXX_PARALLEL_ASSERT(!tls[i]->leftover_parts.pop_back(dummy));
#endif
- for (int i = 0; i < num_threads; i++)
+ for (int i = 0; i < num_threads; ++i)
delete tls[i];
delete[] tls;
}
Index: include/parallel/set_operations.h
===================================================================
--- include/parallel/set_operations.h (revision 131429)
+++ include/parallel/set_operations.h (working copy)
@@ -1,6 +1,6 @@
// -*- C++ -*-
-// Copyright (C) 2007 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
@@ -48,7 +48,7 @@
namespace __gnu_parallel
{
template<typename InputIterator, typename OutputIterator>
- inline OutputIterator
+ OutputIterator
copy_tail(std::pair<InputIterator, InputIterator> b,
std::pair<InputIterator, InputIterator> e, OutputIterator r)
{
@@ -68,10 +68,9 @@
return r;
}
-template<
- typename InputIterator,
- typename OutputIterator,
- typename Comparator>
+template<typename InputIterator,
+ typename OutputIterator,
+ typename Comparator>
struct symmetric_difference_func
{
typedef std::iterator_traits<InputIterator> traits_type;
@@ -82,9 +81,10 @@
Comparator comp;
- inline OutputIterator invoke(InputIterator a, InputIterator b,
- InputIterator c, InputIterator d,
- OutputIterator r) const
+ OutputIterator
+ invoke(InputIterator a, InputIterator b,
+ InputIterator c, InputIterator d,
+ OutputIterator r) const
{
while (a != b && c != d)
{
@@ -109,9 +109,9 @@
return std::copy(c, d, std::copy(a, b, r));
}
- inline difference_type
- count(InputIterator a, InputIterator b, InputIterator c, InputIterator d)
- const
+ difference_type
+ count(InputIterator a, InputIterator b,
+ InputIterator c, InputIterator d) const
{
difference_type counter = 0;
@@ -137,21 +137,19 @@
return counter + (b - a) + (d - c);
}
- inline OutputIterator
+ OutputIterator
first_empty(InputIterator c, InputIterator d, OutputIterator out) const
{ return std::copy(c, d, out); }
- inline OutputIterator
+ OutputIterator
second_empty(InputIterator a, InputIterator b, OutputIterator out) const
{ return std::copy(a, b, out); }
-
};
-template<
- typename InputIterator,
- typename OutputIterator,
- typename Comparator>
+template<typename InputIterator,
+ typename OutputIterator,
+ typename Comparator>
struct difference_func
{
typedef std::iterator_traits<InputIterator> traits_type;
@@ -162,7 +160,7 @@
Comparator comp;
- inline OutputIterator
+ OutputIterator
invoke(InputIterator a, InputIterator b, InputIterator c, InputIterator d,
OutputIterator r) const
{
@@ -185,9 +183,9 @@
return std::copy(a, b, r);
}
- inline difference_type
- count(InputIterator a, InputIterator b, InputIterator c, InputIterator d)
- const
+ difference_type
+ count(InputIterator a, InputIterator b,
+ InputIterator c, InputIterator d) const
{
difference_type counter = 0;
@@ -217,10 +215,9 @@
};
-template<
- typename InputIterator,
- typename OutputIterator,
- typename Comparator>
+template<typename InputIterator,
+ typename OutputIterator,
+ typename Comparator>
struct intersection_func
{
typedef std::iterator_traits<InputIterator> traits_type;
@@ -231,7 +228,7 @@
Comparator comp;
- inline OutputIterator
+ OutputIterator
invoke(InputIterator a, InputIterator b, InputIterator c, InputIterator d,
OutputIterator r) const
{
@@ -253,9 +250,9 @@
return r;
}
- inline difference_type
- count(InputIterator a, InputIterator b, InputIterator c, InputIterator d)
- const
+ difference_type
+ count(InputIterator a, InputIterator b,
+ InputIterator c, InputIterator d) const
{
difference_type counter = 0;
@@ -289,13 +286,13 @@
struct union_func
{
typedef typename std::iterator_traits<InputIterator>::difference_type
- difference_type;
+ difference_type;
union_func(Comparator c) : comp(c) {}
Comparator comp;
- inline OutputIterator
+ OutputIterator
invoke(InputIterator a, const InputIterator b, InputIterator c,
const InputIterator d, OutputIterator r) const
{
@@ -322,9 +319,9 @@
return std::copy(c, d, std::copy(a, b, r));
}
- inline difference_type
- count(InputIterator a, InputIterator b, InputIterator c, InputIterator d)
- const
+ difference_type
+ count(InputIterator a, InputIterator b,
+ InputIterator c, InputIterator d) const
{
difference_type counter = 0;
@@ -356,10 +353,9 @@
{ return std::copy(a, b, out); }
};
-template<
- typename InputIterator,
- typename OutputIterator,
- typename Operation>
+template<typename InputIterator,
+ typename OutputIterator,
+ typename Operation>
OutputIterator
parallel_set_operation(InputIterator begin1, InputIterator end1,
InputIterator begin2, InputIterator end2,
@@ -480,11 +476,10 @@
}
-template<
- typename InputIterator,
- typename OutputIterator,
- typename Comparator>
- OutputIterator
+template<typename InputIterator,
+ typename OutputIterator,
+ typename Comparator>
+ inline OutputIterator
parallel_set_union(InputIterator begin1, InputIterator end1,
InputIterator begin2, InputIterator end2,
OutputIterator result, Comparator comp)
@@ -493,11 +488,10 @@
union_func< InputIterator, OutputIterator, Comparator>(comp));
}
-template<
- typename InputIterator,
- typename OutputIterator,
- typename Comparator>
- OutputIterator
+template<typename InputIterator,
+ typename OutputIterator,
+ typename Comparator>
+ inline OutputIterator
parallel_set_intersection(InputIterator begin1, InputIterator end1,
InputIterator begin2, InputIterator end2,
OutputIterator result, Comparator comp)
@@ -508,7 +502,7 @@
template<typename InputIterator, typename OutputIterator>
- OutputIterator
+ inline OutputIterator
set_intersection(InputIterator begin1, InputIterator end1,
InputIterator begin2, InputIterator end2,
OutputIterator result)
@@ -517,14 +511,13 @@
typedef typename traits_type::value_type value_type;
return set_intersection(begin1, end1, begin2, end2, result,
- std::less<value_type>());
+ std::less<value_type>());
}
-template<
- typename InputIterator,
- typename OutputIterator,
- typename Comparator>
- OutputIterator
+template<typename InputIterator,
+ typename OutputIterator,
+ typename Comparator>
+ inline OutputIterator
parallel_set_difference(InputIterator begin1, InputIterator end1,
InputIterator begin2, InputIterator end2,
OutputIterator result, Comparator comp)
@@ -533,11 +526,10 @@
difference_func<InputIterator, OutputIterator, Comparator>(comp));
}
-template<
- typename InputIterator,
- typename OutputIterator,
- typename Comparator>
- OutputIterator
+template<typename InputIterator,
+ typename OutputIterator,
+ typename Comparator>
+ inline OutputIterator
parallel_set_symmetric_difference(InputIterator begin1, InputIterator end1,
InputIterator begin2, InputIterator end2,
OutputIterator result, Comparator comp)
Index: include/parallel/tree.h
===================================================================
--- include/parallel/tree.h (revision 131429)
+++ include/parallel/tree.h (working copy)
@@ -77,11 +77,11 @@
component, if present. Set kind component.
* @param T Simple type, nothing to unconst */
template<typename T>
- struct unconst_first_component
- {
- /** @brief New type after removing the const */
- typedef T type;
- };
+ struct unconst_first_component
+ {
+ /** @brief New type after removing the const */
+ typedef T type;
+ };
/** @brief Helper class: remove the const modifier from the first
component, if present. Map kind component
@@ -89,11 +89,11 @@
* @param Load Second component
* @sa unconst_first_component */
template<typename Key, typename Load>
- struct unconst_first_component<std::pair<const Key, Load> >
- {
- /** @brief New type after removing the const */
- typedef std::pair<Key, Load> type;
- };
+ struct unconst_first_component<std::pair<const Key, Load> >
+ {
+ /** @brief New type after removing the const */
+ typedef std::pair<Key, Load> type;
+ };
/** @brief Helper class: set the appropriate comparator to deal with
* repetitions. Comparator for unique dictionaries.
@@ -103,24 +103,23 @@
* @param _Key Keys to compare
* @param _Compare Comparator equal to conceptual < */
template<typename _Key, typename _Compare>
- struct StrictlyLess : public std::binary_function<_Key, _Key, bool>
- {
- /** @brief Comparator equal to conceptual < */
- _Compare c;
+ struct StrictlyLess : public std::binary_function<_Key, _Key, bool>
+ {
+ /** @brief Comparator equal to conceptual < */
+ _Compare c;
- /** @brief Constructor given a Comparator */
- StrictlyLess(const _Compare& _c) : c(_c) { }
+ /** @brief Constructor given a Comparator */
+ StrictlyLess(const _Compare& _c) : c(_c) { }
- /** @brief Copy constructor */
- StrictlyLess(const StrictlyLess<_Key, _Compare>& strictly_less)
- : c(strictly_less.c) { }
+ /** @brief Copy constructor */
+ StrictlyLess(const StrictlyLess<_Key, _Compare>& strictly_less)
+ : c(strictly_less.c) { }
- /** @brief Operator() */
- bool operator()(const _Key& k1, const _Key& k2) const
- {
- return c(k1, k2);
- }
- };
+ /** @brief Operator() */
+ bool
+ operator()(const _Key& k1, const _Key& k2) const
+ { return c(k1, k2); }
+ };
/** @brief Helper class: set the appropriate comparator to deal with
* repetitions. Comparator for non-unique dictionaries.
@@ -130,22 +129,23 @@
* @param _Key Keys to compare
* @param _Compare Comparator equal to conceptual <= */
template<typename _Key, typename _Compare>
- struct LessEqual : public std::binary_function<_Key, _Key, bool>
- {
- /** @brief Comparator equal to conceptual < */
- _Compare c;
+ struct LessEqual : public std::binary_function<_Key, _Key, bool>
+ {
+ /** @brief Comparator equal to conceptual < */
+ _Compare c;
- /** @brief Constructor given a Comparator */
- LessEqual(const _Compare& _c) : c(_c) { }
+ /** @brief Constructor given a Comparator */
+ LessEqual(const _Compare& _c) : c(_c) { }
- /** @brief Copy constructor */
- LessEqual(const LessEqual<_Key, _Compare>& less_equal)
- : c(less_equal.c) { }
-
- /** @brief Operator() */
- bool operator()(const _Key& k1, const _Key& k2) const
- { return !c(k2, k1); }
- };
+ /** @brief Copy constructor */
+ LessEqual(const LessEqual<_Key, _Compare>& less_equal)
+ : c(less_equal.c) { }
+
+ /** @brief Operator() */
+ bool
+ operator()(const _Key& k1, const _Key& k2) const
+ { return !c(k2, k1); }
+ };
/** @brief Parallel red-black tree.
@@ -240,28 +240,28 @@
* @param __last Last element of the input
*/
template<typename _InputIterator>
- void
- _M_insert_unique(_InputIterator __first, _InputIterator __last)
- {
- if (__first==__last) return;
- if (_GLIBCXX_PARALLEL_CONDITION(true))
- if (base_type::_M_impl._M_node_count == 0)
- {
- _M_bulk_insertion_construction(__first, __last, true,
- strictly_less);
- _GLIBCXX_PARALLEL_ASSERT(rb_verify());
- }
+ void
+ _M_insert_unique(_InputIterator __first, _InputIterator __last)
+ {
+ if (__first == __last)
+ return;
+
+ if (_GLIBCXX_PARALLEL_CONDITION(true))
+ if (base_type::_M_impl._M_node_count == 0)
+ {
+ _M_bulk_insertion_construction(__first, __last, true,
+ strictly_less);
+ _GLIBCXX_PARALLEL_ASSERT(rb_verify());
+ }
+ else
+ {
+ _M_bulk_insertion_construction(__first, __last, false,
+ strictly_less);
+ _GLIBCXX_PARALLEL_ASSERT(rb_verify());
+ }
else
- {
- _M_bulk_insertion_construction(__first, __last, false,
- strictly_less);
- _GLIBCXX_PARALLEL_ASSERT(rb_verify());
- }
- else
- {
base_type::_M_insert_unique(__first, __last);
- }
- }
+ }
/** @brief Parallel replacement of the sequential
* std::_Rb_tree::_M_insert_equal()
@@ -272,19 +272,21 @@
* @param __first First element of the input
* @param __last Last element of the input */
template<typename _InputIterator>
- void
- _M_insert_equal(_InputIterator __first, _InputIterator __last)
- {
- if (__first==__last) return;
- if (_GLIBCXX_PARALLEL_CONDITION(true))
- if (base_type::_M_impl._M_node_count == 0)
- _M_bulk_insertion_construction(__first, __last, true, less_equal);
+ void
+ _M_insert_equal(_InputIterator __first, _InputIterator __last)
+ {
+ if (__first == __last)
+ return;
+
+ if (_GLIBCXX_PARALLEL_CONDITION(true))
+ if (base_type::_M_impl._M_node_count == 0)
+ _M_bulk_insertion_construction(__first, __last, true, less_equal);
+ else
+ _M_bulk_insertion_construction(__first, __last, false, less_equal);
else
- _M_bulk_insertion_construction(__first, __last, false, less_equal);
- else
- base_type::_M_insert_equal(__first, __last);
- _GLIBCXX_PARALLEL_ASSERT(rb_verify());
- }
+ base_type::_M_insert_equal(__first, __last);
+ _GLIBCXX_PARALLEL_ASSERT(rb_verify());
+ }
private:
@@ -295,274 +297,273 @@
* @param ranker Calculates the position of a node in an array of nodes
*/
template<typename ranker>
- class nodes_initializer
- {
- /** @brief Renaming of tree size_type */
+ class nodes_initializer
+ {
+ /** @brief Renaming of tree size_type */
- typedef _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc> tree_type;
- typedef typename tree_type::size_type size_typ