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