This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[v3] Some minimal formatting fixes to the include/parallel headers (1)
- From: Paolo Carlini <pcarlini at suse dot de>
- To: Gcc Patch List <gcc-patches at gcc dot gnu dot org>
- Cc: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Wed, 09 Jan 2008 19:25:52 +0100
- Subject: [v3] Some minimal formatting fixes to the include/parallel headers (1)
Hi,
tested x86_64-linux, check-parallel, committed to mainline.
Paolo.
PS: noticed that a relatively urgent issue is moving out of line some
large member functions. Will do after this pass.
//////////////////
2008-01-09 Paolo Carlini <pcarlini@suse.de>
* include/parallel/iterator.h: Reformat to 80 columns; adjust some
inline specifiers.
* include/parallel/find_selectors.h: Likewise.
* include/parallel/losertree.h: Likewise.
* include/parallel/list_partition.h: Likewise.
* include/parallel/for_each.h: Likewise.
* include/parallel/multiseq_selection.h: Likewise.
* include/parallel/algorithmfwd.h: Likewise.
* include/parallel/for_each_selectors.h: Likewise.
* include/parallel/balanced_quicksort.h: Likewise.
* include/parallel/merge.h: Likewise.
* include/parallel/algobase.h: Likewise.
* include/parallel/find.h: Likewise.
* include/parallel/algo.h: Likewise.
* include/parallel/checkers.h: Likewise.
Index: include/parallel/iterator.h
===================================================================
--- include/parallel/iterator.h (revision 131429)
+++ include/parallel/iterator.h (working copy)
@@ -1,6 +1,6 @@
// -*- C++ -*-
-// Copyright (C) 2007 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
@@ -47,156 +47,158 @@
* applied to both child iterators.
*/
template<typename Iterator1, typename Iterator2, typename IteratorCategory>
- class iterator_pair : public std::pair<Iterator1, Iterator2>
- {
- private:
- typedef iterator_pair<Iterator1, Iterator2, IteratorCategory> type;
- typedef std::pair<Iterator1, Iterator2> base_type;
-
- public:
- typedef IteratorCategory iterator_category;
- typedef void value_type;
-
- typedef std::iterator_traits<Iterator1> traits_type;
- typedef typename traits_type::difference_type difference_type;
- typedef type* pointer;
- typedef type& reference;
-
- iterator_pair() { }
-
- iterator_pair(const Iterator1& first, const Iterator2& second)
- : base_type(first, second) { }
-
- // Pre-increment operator.
- type&
- operator++()
+ class iterator_pair : public std::pair<Iterator1, Iterator2>
{
- ++base_type::first;
- ++base_type::second;
- return *this;
- }
-
- // Post-increment operator.
- const type
- operator++(int)
- { return type(base_type::first++, base_type::second++); }
-
- // Pre-decrement operator.
- type&
- operator--()
- {
- --base_type::first;
- --base_type::second;
- return *this;
- }
-
- // Post-decrement operator.
- const type
- operator--(int)
- { return type(base_type::first--, base_type::second--); }
-
- // Type conversion.
- operator Iterator2() const
- { return base_type::second; }
-
- type&
- operator=(const type& other)
- {
- base_type::first = other.first;
- base_type::second = other.second;
- return *this;
- }
-
- type
- operator+(difference_type delta) const
- { return type(base_type::first + delta, base_type::second + delta); }
-
- difference_type
- operator-(const type& other) const
- { return base_type::first - other.first; }
+ private:
+ typedef iterator_pair<Iterator1, Iterator2, IteratorCategory> type;
+ typedef std::pair<Iterator1, Iterator2> base_type;
+
+ public:
+ typedef IteratorCategory iterator_category;
+ typedef void value_type;
+
+ typedef std::iterator_traits<Iterator1> traits_type;
+ typedef typename traits_type::difference_type difference_type;
+ typedef type* pointer;
+ typedef type& reference;
+
+ iterator_pair() { }
+
+ iterator_pair(const Iterator1& first, const Iterator2& second)
+ : base_type(first, second) { }
+
+ // Pre-increment operator.
+ type&
+ operator++()
+ {
+ ++base_type::first;
+ ++base_type::second;
+ return *this;
+ }
+
+ // Post-increment operator.
+ const type
+ operator++(int)
+ { return type(base_type::first++, base_type::second++); }
+
+ // Pre-decrement operator.
+ type&
+ operator--()
+ {
+ --base_type::first;
+ --base_type::second;
+ return *this;
+ }
+
+ // Post-decrement operator.
+ const type
+ operator--(int)
+ { return type(base_type::first--, base_type::second--); }
+
+ // Type conversion.
+ operator Iterator2() const
+ { return base_type::second; }
+
+ type&
+ operator=(const type& other)
+ {
+ base_type::first = other.first;
+ base_type::second = other.second;
+ return *this;
+ }
+
+ type
+ operator+(difference_type delta) const
+ { return type(base_type::first + delta, base_type::second + delta); }
+
+ difference_type
+ operator-(const type& other) const
+ { return base_type::first - other.first; }
};
/** @brief A triple of iterators. The usual iterator operations are
applied to all three child iterators.
*/
- template<typename Iterator1, typename Iterator2, typename Iterator3, typename IteratorCategory>
- class iterator_triple
- {
- private:
- typedef iterator_triple<Iterator1, Iterator2, Iterator3, IteratorCategory> type;
-
- public:
- typedef IteratorCategory iterator_category;
- typedef void value_type;
- typedef typename Iterator1::difference_type difference_type;
- typedef type* pointer;
- typedef type& reference;
-
- Iterator1 first;
- Iterator2 second;
- Iterator3 third;
-
- iterator_triple() { }
-
- iterator_triple(const Iterator1& _first, const Iterator2& _second,
- const Iterator3& _third)
- {
- first = _first;
- second = _second;
- third = _third;
- }
-
- // Pre-increment operator.
- type&
- operator++()
- {
- ++first;
- ++second;
- ++third;
- return *this;
- }
-
- // Post-increment operator.
- const type
- operator++(int)
- { return type(first++, second++, third++); }
-
- // Pre-decrement operator.
- type&
- operator--()
- {
- --first;
- --second;
- --third;
- return *this;
- }
-
- // Post-decrement operator.
- const type
- operator--(int)
- { return type(first--, second--, third--); }
-
- // Type conversion.
- operator Iterator3() const
- { return third; }
-
- type&
- operator=(const type& other)
- {
- first = other.first;
- second = other.second;
- third = other.third;
- return *this;
- }
-
- type
- operator+(difference_type delta) const
- { return type(first + delta, second + delta, third + delta); }
-
- difference_type
- operator-(const type& other) const
- { return first - other.first; }
+ template<typename Iterator1, typename Iterator2, typename Iterator3,
+ typename IteratorCategory>
+ class iterator_triple
+ {
+ private:
+ typedef iterator_triple<Iterator1, Iterator2, Iterator3,
+ IteratorCategory> type;
+
+ public:
+ typedef IteratorCategory iterator_category;
+ typedef void value_type;
+ typedef typename Iterator1::difference_type difference_type;
+ typedef type* pointer;
+ typedef type& reference;
+
+ Iterator1 first;
+ Iterator2 second;
+ Iterator3 third;
+
+ iterator_triple() { }
+
+ iterator_triple(const Iterator1& _first, const Iterator2& _second,
+ const Iterator3& _third)
+ {
+ first = _first;
+ second = _second;
+ third = _third;
+ }
+
+ // Pre-increment operator.
+ type&
+ operator++()
+ {
+ ++first;
+ ++second;
+ ++third;
+ return *this;
+ }
+
+ // Post-increment operator.
+ const type
+ operator++(int)
+ { return type(first++, second++, third++); }
+
+ // Pre-decrement operator.
+ type&
+ operator--()
+ {
+ --first;
+ --second;
+ --third;
+ return *this;
+ }
+
+ // Post-decrement operator.
+ const type
+ operator--(int)
+ { return type(first--, second--, third--); }
+
+ // Type conversion.
+ operator Iterator3() const
+ { return third; }
+
+ type&
+ operator=(const type& other)
+ {
+ first = other.first;
+ second = other.second;
+ third = other.third;
+ return *this;
+ }
+
+ type
+ operator+(difference_type delta) const
+ { return type(first + delta, second + delta, third + delta); }
+
+ difference_type
+ operator-(const type& other) const
+ { return first - other.first; }
};
}
Index: include/parallel/find_selectors.h
===================================================================
--- include/parallel/find_selectors.h (revision 131429)
+++ include/parallel/find_selectors.h (working copy)
@@ -1,6 +1,6 @@
// -*- C++ -*-
-// Copyright (C) 2007 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
@@ -60,10 +60,11 @@
* @param i2 Iterator on second sequence (unused).
* @param pred Find predicate.
*/
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
- inline bool
- operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
- { return pred(*i1); }
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
+ bool
+ operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
+ { return pred(*i1); }
/** @brief Corresponding sequential algorithm on a sequence.
* @param begin1 Begin iterator of first sequence.
@@ -71,12 +72,14 @@
* @param begin2 Begin iterator of second sequence.
* @param pred Find predicate.
*/
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
- inline std::pair<RandomAccessIterator1, RandomAccessIterator2>
- sequential_algorithm(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred)
- {
- return std::make_pair(find_if(begin1, end1, pred, sequential_tag()), begin2);
- }
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
+ std::pair<RandomAccessIterator1, RandomAccessIterator2>
+ sequential_algorithm(RandomAccessIterator1 begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator2 begin2, Pred pred)
+ { return std::make_pair(find_if(begin1, end1, pred,
+ sequential_tag()), begin2); }
};
/** @brief Test predicate on two adjacent elements. */
@@ -87,13 +90,14 @@
* @param i2 Iterator on second sequence (unused).
* @param pred Find predicate.
*/
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
- inline bool
- operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
- {
- // Passed end iterator is one short.
- return pred(*i1, *(i1 + 1));
- }
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
+ bool
+ operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
+ {
+ // Passed end iterator is one short.
+ return pred(*i1, *(i1 + 1));
+ }
/** @brief Corresponding sequential algorithm on a sequence.
* @param begin1 Begin iterator of first sequence.
@@ -101,16 +105,20 @@
* @param begin2 Begin iterator of second sequence.
* @param pred Find predicate.
*/
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
- inline std::pair<RandomAccessIterator1, RandomAccessIterator2>
- 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());
- if (spot == (end1 + 1))
- spot = end1;
- return std::make_pair(spot, begin2);
- }
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
+ std::pair<RandomAccessIterator1, RandomAccessIterator2>
+ 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());
+ if (spot == (end1 + 1))
+ spot = end1;
+ return std::make_pair(spot, begin2);
+ }
};
/** @brief Test inverted predicate on a single element. */
@@ -122,10 +130,11 @@
* @param i2 Iterator on second sequence (unused).
* @param pred Find predicate.
*/
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
- inline bool
- operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
- { return !pred(*i1, *i2); }
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
+ bool
+ operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
+ { return !pred(*i1, *i2); }
/**
* @brief Corresponding sequential algorithm on a sequence.
@@ -134,12 +143,13 @@
* @param begin2 Begin iterator of second sequence.
* @param pred Find predicate.
*/
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
- inline std::pair<RandomAccessIterator1, RandomAccessIterator2>
- sequential_algorithm(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred)
- {
- return mismatch(begin1, end1, begin2, pred, sequential_tag());
- }
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
+ std::pair<RandomAccessIterator1, RandomAccessIterator2>
+ sequential_algorithm(RandomAccessIterator1 begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator2 begin2, Pred pred)
+ { return mismatch(begin1, end1, begin2, pred, sequential_tag()); }
};
@@ -157,27 +167,31 @@
* @param i1 Iterator on first sequence.
* @param i2 Iterator on second sequence (unused).
* @param pred Find predicate. */
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
- inline bool
- operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
- {
- for (ForwardIterator pos_in_candidates = begin; pos_in_candidates != end; pos_in_candidates++)
- if (pred(*i1, *pos_in_candidates))
- return true;
- return false;
- }
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
+ 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;
+ return false;
+ }
/** @brief Corresponding sequential algorithm on a sequence.
* @param begin1 Begin iterator of first sequence.
* @param end1 End iterator of first sequence.
* @param begin2 Begin iterator of second sequence.
* @param pred Find predicate. */
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
- inline std::pair<RandomAccessIterator1, RandomAccessIterator2>
- 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);
- }
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
+ std::pair<RandomAccessIterator1, RandomAccessIterator2>
+ 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); }
};
}
Index: include/parallel/losertree.h
===================================================================
--- include/parallel/losertree.h (revision 131429)
+++ include/parallel/losertree.h (working copy)
@@ -76,9 +76,8 @@
Comparator comp;
public:
- inline
LoserTreeExplicit(unsigned int _size, Comparator _comp = std::less<T>())
- : comp(_comp)
+ : comp(_comp)
{
size = _size;
offset = size;
@@ -92,14 +91,14 @@
}
}
- inline ~LoserTreeExplicit()
+ ~LoserTreeExplicit()
{ delete[] losers; }
- inline int
+ int
get_min_source()
{ return losers[0].source; }
- inline void
+ void
insert_start(T key, int source, bool sup)
{
bool inf = false;
@@ -122,10 +121,10 @@
losers[0].source = source;
}
- inline void
+ void
init() { }
- inline void
+ void
delete_min_insert(T key, bool sup)
{
bool inf = false;
@@ -151,7 +150,7 @@
losers[0].source = source;
}
- inline void
+ void
insert_start_stable(T key, int source, bool sup)
{
bool inf = false;
@@ -176,10 +175,10 @@
losers[0].source = source;
}
- inline void
+ void
init_stable() { }
- inline void
+ void
delete_min_insert_stable(T key, bool sup)
{
bool inf = false;
@@ -233,7 +232,7 @@
bool first_insert;
public:
- inline LoserTree(unsigned int _k, Comparator _comp = std::less<T>())
+ LoserTree(unsigned int _k, Comparator _comp = std::less<T>())
: comp(_comp)
{
ik = _k;
@@ -249,14 +248,14 @@
first_insert = true;
}
- inline ~LoserTree()
+ ~LoserTree()
{ ::operator delete(losers); }
- inline int
+ int
get_min_source()
{ return losers[0].source; }
- inline void
+ void
insert_start(const T& key, int source, bool sup)
{
unsigned int pos = k + source;
@@ -303,12 +302,12 @@
}
}
- inline void
+ void
init()
{ losers[0] = losers[init_winner(1)]; }
// Do not pass const reference since key will be used as local variable.
- inline void
+ void
delete_min_insert(T key, bool sup)
{
int source = losers[0].source;
@@ -329,7 +328,7 @@
losers[0].key = key;
}
- inline void
+ void
insert_start_stable(const T& key, int source, bool sup)
{ return insert_start(key, source, sup); }
@@ -361,12 +360,12 @@
}
}
- inline void
+ void
init_stable()
{ losers[0] = losers[init_winner_stable(1)]; }
// Do not pass const reference since key will be used as local variable.
- inline void
+ void
delete_min_insert_stable(T key, bool sup)
{
int source = losers[0].source;
@@ -432,9 +431,8 @@
Comparator comp;
public:
- inline
LoserTreeReference(unsigned int _k, Comparator _comp = std::less<T>())
- : comp(_comp)
+ : comp(_comp)
{
ik = _k;
@@ -449,7 +447,7 @@
losers[i + k].sup = true;
}
- inline ~LoserTreeReference()
+ ~LoserTreeReference()
{
delete[] losers;
#ifndef COPY
@@ -457,11 +455,11 @@
#endif
}
- inline int
+ int
get_min_source()
{ return losers[0].source; }
- inline void
+ void
insert_start(T key, int source, bool sup)
{
unsigned int pos = k + source;
@@ -498,13 +496,13 @@
}
}
- inline void
+ void
init()
{
losers[0] = losers[init_winner(1)];
}
- inline void
+ void
delete_min_insert(T key, bool sup)
{
int source = losers[0].source;
@@ -529,7 +527,7 @@
#endif
}
- inline void
+ void
insert_start_stable(T key, int source, bool sup)
{ return insert_start(key, source, sup); }
@@ -560,11 +558,11 @@
}
}
- inline void
+ void
init_stable()
{ losers[0] = losers[init_winner_stable(1)]; }
- inline void
+ void
delete_min_insert_stable(T key, bool sup)
{
int source = losers[0].source;
@@ -622,7 +620,6 @@
Comparator comp;
public:
- inline
LoserTreePointer(unsigned int _k, Comparator _comp = std::less<T>())
: comp(_comp)
{
@@ -636,14 +633,14 @@
losers[i + k].sup = true;
}
- inline ~LoserTreePointer()
+ ~LoserTreePointer()
{ delete[] losers; }
- inline int
+ int
get_min_source()
{ return losers[0].source; }
- inline void
+ void
insert_start(const T& key, int source, bool sup)
{
unsigned int pos = k + source;
@@ -657,9 +654,7 @@
init_winner(unsigned int root)
{
if (root >= k)
- {
- return root;
- }
+ return root;
else
{
unsigned int left = init_winner (2 * root);
@@ -681,11 +676,11 @@
}
}
- inline void
+ void
init()
{ losers[0] = losers[init_winner(1)]; }
- inline void
+ void
delete_min_insert(const T& key, bool sup)
{
const T* keyp = &key;
@@ -707,7 +702,7 @@
losers[0].keyp = keyp;
}
- inline void
+ void
insert_start_stable(const T& key, int source, bool sup)
{ return insert_start(key, source, sup); }
@@ -739,11 +734,11 @@
}
}
- inline void
+ void
init_stable()
{ losers[0] = losers[init_winner_stable(1)]; }
- inline void
+ void
delete_min_insert_stable(const T& key, bool sup)
{
const T* keyp = &key;
@@ -810,9 +805,8 @@
}
public:
- inline
LoserTreeUnguarded(unsigned int _k, Comparator _comp = std::less<T>())
- : comp(_comp)
+ : comp(_comp)
{
ik = _k;
// Next greater or equal power of 2.
@@ -823,17 +817,17 @@
map(1, 0, ik);
}
- inline ~LoserTreeUnguarded()
+ ~LoserTreeUnguarded()
{
delete[] losers;
delete[] mapping;
}
- inline int
+ int
get_min_source()
{ return losers[0].source; }
- inline void
+ void
insert_start(const T& key, int source, bool)
{
unsigned int pos = mapping[source];
@@ -868,12 +862,12 @@
}
}
- inline void
+ void
init()
{ losers[0] = losers[init_winner(1, 0, ik)]; }
// Do not pass const reference since key will be used as local variable.
- inline void
+ void
delete_min_insert(const T& key, bool)
{
losers[0].key = key;
@@ -891,15 +885,15 @@
}
}
- inline void
+ void
insert_start_stable(const T& key, int source, bool)
{ return insert_start(key, source, false); }
- inline void
+ void
init_stable()
{ init(); }
- inline void
+ void
delete_min_insert_stable(const T& key, bool)
{
losers[0].key = key;
@@ -959,10 +953,9 @@
}
public:
- inline
LoserTreePointerUnguarded(unsigned int _k,
Comparator _comp = std::less<T>())
- : comp(_comp)
+ : comp(_comp)
{
ik = _k;
@@ -974,17 +967,17 @@
map(1, 0, ik);
}
- inline ~LoserTreePointerUnguarded()
+ ~LoserTreePointerUnguarded()
{
delete[] losers;
delete[] mapping;
}
- inline int
+ int
get_min_source()
{ return losers[0].source; }
- inline void
+ void
insert_start(const T& key, int source, bool)
{
unsigned int pos = mapping[source];
@@ -1019,13 +1012,11 @@
}
}
- inline void
+ void
init()
- {
- losers[0] = losers[init_winner(1, 0, ik)];
- }
+ { losers[0] = losers[init_winner(1, 0, ik)]; }
- inline void
+ void
delete_min_insert(const T& key, bool)
{
const T* keyp = &key;
@@ -1044,15 +1035,15 @@
losers[0].keyp = keyp;
}
- inline void
+ void
insert_start_stable(const T& key, int source, bool)
{ return insert_start(key, source, false); }
- inline void
+ void
init_stable()
{ init(); }
- inline void
+ void
delete_min_insert_stable(const T& key, bool)
{
int& source = losers[0].source;
Index: include/parallel/list_partition.h
===================================================================
--- include/parallel/list_partition.h (revision 131429)
+++ include/parallel/list_partition.h (working copy)
@@ -1,6 +1,6 @@
// -*- C++ -*-
-// Copyright (C) 2007 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
@@ -52,36 +52,35 @@
* grown or not
*/
template<typename InputIterator>
- void
- shrink_and_double(std::vector<InputIterator>& os_starts, size_t& count_to_two, size_t& range_length, const bool make_twice)
- {
- ++count_to_two;
- if (not make_twice or count_to_two < 2)
- {
+ void
+ shrink_and_double(std::vector<InputIterator>& os_starts,
+ size_t& count_to_two, size_t& range_length,
+ const bool make_twice)
+ {
+ ++count_to_two;
+ if (not make_twice or count_to_two < 2)
shrink(os_starts, count_to_two, range_length);
- }
- else
- {
- os_starts.resize((os_starts.size() - 1) * 2 + 1);
- count_to_two = 0;
- }
- }
+ else
+ {
+ os_starts.resize((os_starts.size() - 1) * 2 + 1);
+ count_to_two = 0;
+ }
+ }
/** @brief Combines two ranges into one and thus halves the number of ranges.
* @param os_starts Start positions worked on (oversampled).
* @param count_to_two Counts up to 2.
* @param range_length Current length of a chunk. */
template<typename InputIterator>
- void
- shrink(std::vector<InputIterator>& os_starts, size_t& count_to_two,
- size_t& range_length)
- {
- for (typename std::vector<InputIterator>::size_type i = 0; i <= (os_starts.size() / 2); ++i)
- {
+ void
+ shrink(std::vector<InputIterator>& os_starts, size_t& count_to_two,
+ size_t& range_length)
+ {
+ for (typename std::vector<InputIterator>::size_type i = 0;
+ i <= (os_starts.size() / 2); ++i)
os_starts[i] = os_starts[i * 2];
- }
- range_length *= 2;
- }
+ range_length *= 2;
+ }
/** @brief Splits a sequence given by input iterators into parts of
* almost equal size
@@ -103,79 +102,81 @@
* @return Length of the whole sequence.
*/
template<typename InputIterator, typename FunctorType>
- size_t
- list_partition(const InputIterator begin, const InputIterator end,
- InputIterator* starts, size_t* lengths, const int num_parts,
- FunctorType& f, int oversampling = 0)
- {
- bool make_twice = false;
-
- // According to the oversampling factor, the resizing algorithm is chosen.
- if (oversampling == 0)
- {
- make_twice = true;
- oversampling = 1;
- }
-
- std::vector<InputIterator> os_starts(2 * oversampling * num_parts + 1);
-
- os_starts[0]= begin;
- InputIterator prev = begin, it = begin;
- size_t dist_limit = 0, dist = 0;
- size_t cur = 1, next = 1;
- size_t range_length = 1;
- size_t count_to_two = 0;
- while (it != end){
- cur = next;
- for (; cur < os_starts.size() and it != end; ++cur)
+ size_t
+ list_partition(const InputIterator begin, const InputIterator end,
+ 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;
+ }
+
+ std::vector<InputIterator> os_starts(2 * oversampling * num_parts + 1);
+
+ os_starts[0]= begin;
+ InputIterator prev = begin, it = begin;
+ size_t dist_limit = 0, dist = 0;
+ size_t cur = 1, next = 1;
+ size_t range_length = 1;
+ size_t count_to_two = 0;
+ while (it != end)
{
- for (dist_limit += range_length; dist < dist_limit and it != end; ++dist)
+ cur = next;
+ for (; cur < os_starts.size() and it != end; ++cur)
{
- f(it);
- ++it;
+ for (dist_limit += range_length;
+ dist < dist_limit and it != end; ++dist)
+ {
+ f(it);
+ ++it;
+ }
+ os_starts[cur] = 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;
+
+ shrink_and_double(os_starts, count_to_two, range_length, make_twice);
+ next = os_starts.size() / 2 + 1;
}
- // Must compare for end and not cur < os_starts.size() , because
- // cur could be == os_starts.size() as well
- if (it == end)
- break;
+ // Calculation of the parts (one must be extracted from current
+ // because the partition beginning at end, consists only of
+ // itself).
+ size_t size_part = (cur - 1) / num_parts;
+ int size_greater = static_cast<int>((cur - 1) % num_parts);
+ starts[0] = os_starts[0];
- shrink_and_double(os_starts, count_to_two, range_length, make_twice);
- next = os_starts.size()/2 + 1;
- }
+ size_t index = 0;
- // Calculation of the parts (one must be extracted from current
- // because the partition beginning at end, consists only of
- // itself).
- size_t size_part = (cur - 1) / num_parts;
- int size_greater = static_cast<int>((cur - 1) % num_parts);
- starts[0] = os_starts[0];
-
- size_t index = 0;
-
- // 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];
- }
-
- // 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];
- }
+ // 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];
+ }
- // Correction of the end size (the end iteration has not finished).
- lengths[num_parts - 1] -= (dist_limit - dist);
+ // 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];
+ }
- return dist;
- }
+ // Correction of the end size (the end iteration has not finished).
+ lengths[num_parts - 1] -= (dist_limit - dist);
+
+ return dist;
+ }
}
#endif
Index: include/parallel/for_each.h
===================================================================
--- include/parallel/for_each.h (revision 131429)
+++ include/parallel/for_each.h (working copy)
@@ -1,6 +1,6 @@
// -*- C++ -*-
-// Copyright (C) 2007 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
@@ -61,22 +61,42 @@
* @param output Output iterator.
* @param bound Maximum number of elements processed.
* @param parallelism_tag Parallelization method */
- template<typename InputIterator, typename UserOp, typename Functionality, typename Red, typename Result>
- UserOp
- for_each_template_random_access(InputIterator begin, InputIterator end,
- UserOp user_op, Functionality& functionality,
- Red reduction, Result reduction_start,
- Result& output,
- typename std::iterator_traits<InputIterator>::difference_type bound, parallelism parallelism_tag)
- {
- if (parallelism_tag == parallel_unbalanced)
- 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);
- 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);
+ template<typename InputIterator, typename UserOp,
+ typename Functionality, typename Red, typename Result>
+ UserOp
+ for_each_template_random_access(InputIterator begin, InputIterator end,
+ UserOp user_op,
+ Functionality& functionality,
+ Red reduction, Result reduction_start,
+ Result& output, typename
+ std::iterator_traits<InputIterator>::
+ difference_type bound,
+ parallelism parallelism_tag)
+ {
+ if (parallelism_tag == parallel_unbalanced)
+ 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);
+ 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);
}
}
Index: include/parallel/multiseq_selection.h
===================================================================
--- include/parallel/multiseq_selection.h (revision 131429)
+++ include/parallel/multiseq_selection.h (working copy)
@@ -1,6 +1,6 @@
// -*- C++ -*-
-// Copyright (C) 2007 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
@@ -58,52 +58,55 @@
{
/** @brief Compare a pair of types lexicographically, ascending. */
template<typename T1, typename T2, typename Comparator>
- class lexicographic : public std::binary_function<std::pair<T1, T2>, std::pair<T1, T2>, bool>
- {
- private:
- Comparator& comp;
-
- public:
- lexicographic(Comparator& _comp) : comp(_comp) { }
-
- // XXX const
- inline bool
- operator()(const std::pair<T1, T2>& p1, const std::pair<T1, T2>& p2) const
+ class lexicographic
+ : public std::binary_function<std::pair<T1, T2>, std::pair<T1, T2>, bool>
{
- if (comp(p1.first, p2.first))
- return true;
+ private:
+ Comparator& comp;
- if (comp(p2.first, p1.first))
- return false;
+ public:
+ lexicographic(Comparator& _comp) : comp(_comp) { }
- // Firsts are equal.
- return p1.second < p2.second;
- }
- };
+ // XXX const
+ bool
+ operator()(const std::pair<T1, T2>& p1,
+ const std::pair<T1, T2>& p2) const
+ {
+ if (comp(p1.first, p2.first))
+ return true;
+
+ if (comp(p2.first, p1.first))
+ return false;
+
+ // Firsts are equal.
+ return p1.second < p2.second;
+ }
+ };
/** @brief Compare a pair of types lexicographically, descending. */
template<typename T1, typename T2, typename Comparator>
- class lexicographic_reverse : public std::binary_function<T1, T2, bool>
- {
- private:
- Comparator& comp;
+ class lexicographic_reverse : public std::binary_function<T1, T2, bool>
+ {
+ private:
+ Comparator& comp;
- public:
- lexicographic_reverse(Comparator& _comp) : comp(_comp) { }
+ public:
+ lexicographic_reverse(Comparator& _comp) : comp(_comp) { }
- inline bool
- operator()(const std::pair<T1, T2>& p1, const std::pair<T1, T2>& p2) const
- {
- if (comp(p2.first, p1.first))
- return true;
+ bool
+ operator()(const std::pair<T1, T2>& p1,
+ const std::pair<T1, T2>& p2) const
+ {
+ if (comp(p2.first, p1.first))
+ return true;
- if (comp(p1.first, p2.first))
- return false;
+ if (comp(p1.first, p2.first))
+ return false;
- // Firsts are equal.
- return p2.second < p1.second;
- }
- };
+ // Firsts are equal.
+ return p2.second < p1.second;
+ }
+ };
/**
* @brief Splits several sorted sequences at a certain global rank,
@@ -121,229 +124,243 @@
* the respective sequence.
* @param comp The ordering functor, defaults to std::less<T>.
*/
- template<typename RanSeqs, typename RankType, typename RankIterator, typename Comparator>
- void
- multiseq_partition(RanSeqs begin_seqs, RanSeqs end_seqs, RankType rank,
- RankIterator begin_offsets,
- Comparator comp = std::less<
- typename std::iterator_traits<typename std::iterator_traits<RanSeqs>::value_type::first_type>::value_type>()) // std::less<T>
- {
- _GLIBCXX_CALL(end_seqs - begin_seqs)
-
- typedef typename std::iterator_traits<RanSeqs>::value_type::first_type It;
- typedef typename std::iterator_traits<It>::difference_type difference_type;
- typedef typename std::iterator_traits<It>::value_type value_type;
-
- lexicographic<value_type, int, Comparator> lcomp(comp);
- lexicographic_reverse<value_type, int, Comparator> lrcomp(comp);
-
- // Number of sequences, number of elements in total (possibly
- // including padding).
- difference_type m = std::distance(begin_seqs, end_seqs), N = 0, nmax, n, r;
-
- for (int i = 0; i < m; i++)
- N += std::distance(begin_seqs[i].first, begin_seqs[i].second);
-
- if (rank == N)
- {
- 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);
-
- difference_type* ns = new difference_type[m];
- difference_type* a = new difference_type[m];
- difference_type* b = new difference_type[m];
- difference_type l;
-
- ns[0] = std::distance(begin_seqs[0].first, begin_seqs[0].second);
- 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]);
- }
-
- r = log2(nmax) + 1;
-
- // Pad all lists to this length, at least as long as any ns[i],
- // equality iff nmax = 2^k - 1.
- l = (1ULL << r) - 1;
+ template<typename RanSeqs, typename RankType, typename RankIterator,
+ typename Comparator>
+ void
+ multiseq_partition(RanSeqs begin_seqs, RanSeqs end_seqs,
+ RankType rank,
+ RankIterator begin_offsets,
+ Comparator comp = std::less<
+ typename std::iterator_traits<typename
+ std::iterator_traits<RanSeqs>::value_type::
+ first_type>::value_type>()) // std::less<T>
+ {
+ _GLIBCXX_CALL(end_seqs - begin_seqs)
- // From now on, including padding.
- N = l * m;
+ typedef typename std::iterator_traits<RanSeqs>::value_type::first_type
+ It;
+ typedef typename std::iterator_traits<It>::difference_type
+ difference_type;
+ typedef typename std::iterator_traits<It>::value_type value_type;
+
+ lexicographic<value_type, int, Comparator> lcomp(comp);
+ lexicographic_reverse<value_type, int, Comparator> lrcomp(comp);
+
+ // Number of sequences, number of elements in total (possibly
+ // including padding).
+ difference_type m = std::distance(begin_seqs, end_seqs), N = 0,
+ nmax, n, r;
+
+ for (int i = 0; i < m; i++)
+ N += std::distance(begin_seqs[i].first, begin_seqs[i].second);
+
+ if (rank == N)
+ {
+ 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);
+
+ difference_type* ns = new difference_type[m];
+ difference_type* a = new difference_type[m];
+ difference_type* b = new difference_type[m];
+ difference_type l;
+
+ ns[0] = std::distance(begin_seqs[0].first, begin_seqs[0].second);
+ 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]);
+ }
+
+ r = log2(nmax) + 1;
+
+ // Pad all lists to this length, at least as long as any ns[i],
+ // equality iff nmax = 2^k - 1.
+ l = (1ULL << r) - 1;
+
+ // From now on, including padding.
+ N = l * m;
+
+ for (int i = 0; i < m; i++)
+ {
+ a[i] = 0;
+ b[i] = l;
+ }
+ n = l / 2;
- for (int i = 0; i < m; i++)
- {
- a[i] = 0;
- b[i] = l;
- }
- n = l / 2;
-
- // Invariants:
- // 0 <= a[i] <= ns[i], 0 <= b[i] <= l
+ // Invariants:
+ // 0 <= a[i] <= ns[i], 0 <= b[i] <= l
#define S(i) (begin_seqs[i].first)
- // Initial partition.
- std::vector<std::pair<value_type, int> > sample;
-
- for (int i = 0; i < m; i++)
- if (n < ns[i]) //sequence long enough
- sample.push_back(std::make_pair(S(i)[n], i));
- __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));
-
- difference_type localrank = rank * m / N ;
-
- int j;
- for (j = 0; j < localrank && ((n + 1) <= ns[sample[j].second]); j++)
- a[sample[j].second] += n + 1;
- for (; j < m; j++)
- b[sample[j].second] -= n + 1;
-
- // Further refinement.
- while (n > 0)
- {
- 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 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 skew = static_cast<difference_type>(static_cast<uint64>(total) * rank / N - leftsize);
-
- if (skew > 0)
- {
- // Move to the left, find smallest.
- std::priority_queue<std::pair<value_type, int>, std::vector<std::pair<value_type, int> >, lexicographic_reverse<value_type, int, Comparator> > pq(lrcomp);
-
- for (int i = 0; i < m; i++)
- if (b[i] < ns[i])
- pq.push(std::make_pair(S(i)[b[i]], i));
-
- for (; 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;
-
- if (b[source] < ns[source])
- pq.push(std::make_pair(S(source)[b[source]], source));
- }
- }
- else if (skew < 0)
- {
- // Move to the right, find greatest.
- std::priority_queue<std::pair<value_type, int>, std::vector<std::pair<value_type, int> >, lexicographic<value_type, int, Comparator> > pq(lcomp);
+ // Initial partition.
+ std::vector<std::pair<value_type, int> > sample;
- for (int i = 0; i < m; i++)
+ for (int i = 0; i < m; 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));
+
+ difference_type localrank = rank * m / N ;
+
+ int j;
+ for (j = 0; j < localrank && ((n + 1) <= ns[sample[j].second]); j++)
+ a[sample[j].second] += n + 1;
+ for (; j < m; j++)
+ b[sample[j].second] -= n + 1;
+
+ // Further refinement.
+ while (n > 0)
+ {
+ 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)
- pq.push(std::make_pair(S(i)[a[i] - 1], i));
-
- for (; skew != 0; skew++)
- {
- int source = pq.top().second;
- pq.pop();
-
- a[source] -= n + 1;
- b[source] -= n + 1;
-
- if (a[source] > 0)
- pq.push(std::make_pair(S(source)[a[source] - 1], source));
- }
- }
- }
-
- // Postconditions:
- // a[i] == b[i] in most cases, except when a[i] has been clamped
- // because of having reached the boundary
-
- // Now return the result, calculate the offset.
-
- // Compare the keys on both edges of the border.
-
- // Maximum of left edge, minimum of right edge.
- value_type* maxleft = NULL;
- 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]]);
- }
- }
- }
-
- int seq = 0;
- for (int i = 0; i < m; i++)
- begin_offsets[i] = S(i) + a[i];
-
- delete[] ns;
- delete[] a;
- delete[] b;
- }
+ {
+ 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;
+ }
+
+ difference_type leftsize = 0, total = 0;
+ for (int i = 0; i < m; i++)
+ {
+ leftsize += a[i] / (n + 1);
+ total += l / (n + 1);
+ }
+
+ difference_type skew = static_cast<difference_type>
+ (static_cast<uint64>(total) * rank / N - leftsize);
+
+ if (skew > 0)
+ {
+ // Move to the left, find smallest.
+ std::priority_queue<std::pair<value_type, int>,
+ std::vector<std::pair<value_type, int> >,
+ lexicographic_reverse<value_type, int, Comparator> >
+ pq(lrcomp);
+
+ for (int i = 0; i < m; i++)
+ if (b[i] < ns[i])
+ pq.push(std::make_pair(S(i)[b[i]], i));
+
+ for (; 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;
+
+ if (b[source] < ns[source])
+ pq.push(std::make_pair(S(source)[b[source]], source));
+ }
+ }
+ else if (skew < 0)
+ {
+ // Move to the right, find greatest.
+ std::priority_queue<std::pair<value_type, int>,
+ std::vector<std::pair<value_type, int> >,
+ lexicographic<value_type, int, Comparator> > pq(lcomp);
+
+ for (int i = 0; i < m; i++)
+ if (a[i] > 0)
+ pq.push(std::make_pair(S(i)[a[i] - 1], i));
+
+ for (; skew != 0; skew++)
+ {
+ int source = pq.top().second;
+ pq.pop();
+
+ a[source] -= n + 1;
+ b[source] -= n + 1;
+
+ if (a[source] > 0)
+ pq.push(std::make_pair(S(source)[a[source] - 1], source));
+ }
+ }
+ }
+
+ // Postconditions:
+ // a[i] == b[i] in most cases, except when a[i] has been clamped
+ // because of having reached the boundary
+
+ // Now return the result, calculate the offset.
+
+ // Compare the keys on both edges of the border.
+
+ // Maximum of left edge, minimum of right edge.
+ value_type* maxleft = NULL;
+ 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]]);
+ }
+ }
+ }
+
+ int seq = 0;
+ for (int i = 0; i < m; i++)
+ begin_offsets[i] = S(i) + a[i];
+
+ delete[] ns;
+ delete[] a;
+ delete[] b;
+ }
/**
@@ -360,246 +377,254 @@
* selected element is unique, this number is 0.
* @param comp The ordering functor, defaults to std::less.
*/
- template<typename T, typename RanSeqs, typename RankType, typename Comparator>
- T
- multiseq_selection(RanSeqs begin_seqs, RanSeqs end_seqs, RankType rank,
- RankType& offset, Comparator comp = std::less<T>())
- {
- _GLIBCXX_CALL(end_seqs - begin_seqs)
-
- typedef typename std::iterator_traits<RanSeqs>::value_type::first_type It;
- typedef typename std::iterator_traits<It>::difference_type difference_type;
-
- lexicographic<T, int, Comparator> lcomp(comp);
- lexicographic_reverse<T, int, Comparator> lrcomp(comp);
-
- // Number of sequences, number of elements in total (possibly
- // including padding).
- difference_type m = std::distance(begin_seqs, end_seqs);
- difference_type N = 0;
- difference_type nmax, n, r;
-
- for (int i = 0; i < m; i++)
- N += std::distance(begin_seqs[i].first, begin_seqs[i].second);
-
- if (m == 0 || N == 0 || rank < 0 || rank >= N)
- {
- // Result undefined when there is no data or rank is outside bounds.
- throw std::exception();
- }
-
-
- difference_type* ns = new difference_type[m];
- difference_type* a = new difference_type[m];
- difference_type* b = new difference_type[m];
- difference_type l;
-
- ns[0] = std::distance(begin_seqs[0].first, begin_seqs[0].second);
- 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]);
- }
-
- r = log2(nmax) + 1;
-
- // Pad all lists to this length, at least as long as any ns[i],
- // equality iff nmax = 2^k - 1
- l = pow2(r) - 1;
-
- // From now on, including padding.
- N = l * m;
+ template<typename T, typename RanSeqs, typename RankType,
+ typename Comparator>
+ T
+ multiseq_selection(RanSeqs begin_seqs, RanSeqs end_seqs, RankType rank,
+ RankType& offset, Comparator comp = std::less<T>())
+ {
+ _GLIBCXX_CALL(end_seqs - begin_seqs)
- for (int i = 0; i < m; i++)
- {
- a[i] = 0;
- b[i] = l;
- }
- n = l / 2;
+ typedef typename std::iterator_traits<RanSeqs>::value_type::first_type
+ It;
+ typedef typename std::iterator_traits<It>::difference_type
+ difference_type;
+
+ lexicographic<T, int, Comparator> lcomp(comp);
+ lexicographic_reverse<T, int, Comparator> lrcomp(comp);
+
+ // Number of sequences, number of elements in total (possibly
+ // including padding).
+ difference_type m = std::distance(begin_seqs, end_seqs);
+ difference_type N = 0;
+ difference_type nmax, n, r;
+
+ for (int i = 0; i < m; i++)
+ N += std::distance(begin_seqs[i].first, begin_seqs[i].second);
+
+ if (m == 0 || N == 0 || rank < 0 || rank >= N)
+ {
+ // Result undefined when there is no data or rank is outside bounds.
+ throw std::exception();
+ }
+
+
+ difference_type* ns = new difference_type[m];
+ difference_type* a = new difference_type[m];
+ difference_type* b = new difference_type[m];
+ difference_type l;
+
+ ns[0] = std::distance(begin_seqs[0].first, begin_seqs[0].second);
+ 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]);
+ }
+
+ r = log2(nmax) + 1;
+
+ // Pad all lists to this length, at least as long as any ns[i],
+ // equality iff nmax = 2^k - 1
+ l = pow2(r) - 1;
+
+ // From now on, including padding.
+ N = l * m;
+
+ for (int i = 0; i < m; i++)
+ {
+ a[i] = 0;
+ b[i] = l;
+ }
+ n = l / 2;
- // Invariants:
- // 0 <= a[i] <= ns[i], 0 <= b[i] <= l
+ // Invariants:
+ // 0 <= a[i] <= ns[i], 0 <= b[i] <= l
#define S(i) (begin_seqs[i].first)
- // Initial partition.
- std::vector<std::pair<T, int> > sample;
-
- 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());
-
- // 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));
-
- difference_type localrank = rank * m / N ;
-
- int j;
- for (j = 0; j < localrank && ((n + 1) <= ns[sample[j].second]); j++)
- a[sample[j].second] += n + 1;
- for (; j < m; j++)
- b[sample[j].second] -= n + 1;
-
- // Further refinement.
- while (n > 0)
- {
- n /= 2;
+ // Initial partition.
+ std::vector<std::pair<T, int> > sample;
- 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;
- }
-
- 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;
-
- if (skew > 0)
- {
- // Move to the left, find smallest.
- std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int> >, lexicographic_reverse<T, int, Comparator> > pq(lrcomp);
-
- for (int i = 0; i < m; i++)
- if (b[i] < ns[i])
- pq.push(std::make_pair(S(i)[b[i]], i));
-
- for (; 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;
-
- if (b[source] < ns[source])
- pq.push(std::make_pair(S(source)[b[source]], source));
- }
- }
- else if (skew < 0)
- {
- // Move to the right, find greatest.
- std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int> >, lexicographic<T, int, Comparator> > pq(lcomp);
-
- for (int i = 0; i < m; i++)
+ 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());
+
+ // 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));
+
+ difference_type localrank = rank * m / N ;
+
+ int j;
+ for (j = 0; j < localrank && ((n + 1) <= ns[sample[j].second]); j++)
+ a[sample[j].second] += n + 1;
+ for (; j < m; j++)
+ b[sample[j].second] -= n + 1;
+
+ // Further refinement.
+ while (n > 0)
+ {
+ n /= 2;
+
+ const T* lmax = NULL;
+ 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();
-
- a[source] -= n + 1;
- b[source] -= n + 1;
-
- if (a[source] > 0)
- pq.push(std::make_pair(S(source)[a[source] - 1], source));
- }
- }
- }
-
- // Postconditions:
- // a[i] == b[i] in most cases, except when a[i] has been clamped
- // because of having reached the boundary
-
- // Now return the result, calculate the offset.
-
- // Compare the keys on both edges of the border.
-
- // Maximum of left edge, minimum of right edge.
- bool maxleftset = false, minrightset = false;
-
- // Impossible to avoid the warning?
- 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]))
+ {
+ 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;
+ }
+
+ 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);
+
+ if (skew > 0)
+ {
+ // Move to the left, find smallest.
+ std::priority_queue<std::pair<T, int>,
+ std::vector<std::pair<T, int> >,
+ lexicographic_reverse<T, int, Comparator> > pq(lrcomp);
+
+ for (int i = 0; i < m; i++)
+ if (b[i] < ns[i])
+ pq.push(std::make_pair(S(i)[b[i]], i));
+
+ for (; 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;
+
+ if (b[source] < ns[source])
+ pq.push(std::make_pair(S(source)[b[source]], source));
+ }
+ }
+ else if (skew < 0)
+ {
+ // Move to the right, find greatest.
+ std::priority_queue<std::pair<T, int>,
+ std::vector<std::pair<T, int> >,
+ lexicographic<T, int, Comparator> > pq(lcomp);
+
+ for (int i = 0; i < m; i++)
+ if (a[i] > 0)
+ pq.push(std::make_pair(S(i)[a[i] - 1], i));
+
+ for (; skew != 0; ++skew)
+ {
+ int source = pq.top().second;
+ pq.pop();
+
+ a[source] -= n + 1;
+ b[source] -= n + 1;
+
+ if (a[source] > 0)
+ pq.push(std::make_pair(S(source)[a[source] - 1], source));
+ }
+ }
+ }
+
+ // Postconditions:
+ // a[i] == b[i] in most cases, except when a[i] has been clamped
+ // because of having reached the boundary
+
+ // Now return the result, calculate the offset.
+
+ // Compare the keys on both edges of the border.
+
+ // Maximum of left edge, minimum of right edge.
+ bool maxleftset = false, minrightset = false;
+
+ // Impossible to avoid the warning?
+ T maxleft, minright;
+ for (int i = 0; i < m; i++)
+ {
+ if (a[i] > 0)
+ {
+ if (!maxleftset)
+ {
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))
+ 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;
+ }
+ else
+ {
+ // 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;
+ }
+ }
+
+ delete[] ns;
+ delete[] a;
+ delete[] b;
- // Minright is the splitter, in any case.
-
- if (!maxleftset || comp(minright, maxleft))
- {
- // Good luck, everything is split unambigiously.
- offset = 0;
- }
- else
- {
- // 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;
- }
- }
-
- delete[] ns;
- delete[] a;
- delete[] b;
-
- return minright;
- }
+ return minright;
+ }
}
#undef S
Index: include/parallel/algorithmfwd.h
===================================================================
--- include/parallel/algorithmfwd.h (revision 131429)
+++ include/parallel/algorithmfwd.h (working copy)
@@ -1,6 +1,6 @@
// <algorithm> parallel extensions -*- C++ -*-
-// Copyright (C) 2007 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
@@ -84,291 +84,324 @@
typename iterator_traits<_IIter>::difference_type
count(_IIter, _IIter, const _Tp&);
- template<typename _IIter, typename T>
+ template<typename _IIter, typename _Tp>
typename iterator_traits<_IIter>::difference_type
- count(_IIter, _IIter, const T&, __gnu_parallel::sequential_tag);
+ count(_IIter, _IIter, const _Tp&, __gnu_parallel::sequential_tag);
- template<typename _IIter, typename T>
+ template<typename _IIter, typename _Tp>
typename iterator_traits<_IIter>::difference_type
- count(_IIter, _IIter, const T&, __gnu_parallel::parallelism);
+ count(_IIter, _IIter, const _Tp&, __gnu_parallel::parallelism);
- template<typename _IIter, typename T, typename _IterTag>
+ template<typename _IIter, typename _Tp, typename _IterTag>
typename iterator_traits<_IIter>::difference_type
- count_switch(_IIter, _IIter, const T&, _IterTag);
+ count_switch(_IIter, _IIter, const _Tp&, _IterTag);
- template<typename _RAIter, typename T>
+ template<typename _RAIter, typename _Tp>
typename iterator_traits<_RAIter>::difference_type
- count_switch(_RAIter, _RAIter, const T&, random_access_iterator_tag,
+ count_switch(_RAIter, _RAIter, const _Tp&, random_access_iterator_tag,
__gnu_parallel::parallelism);
- template<typename _IIter, typename Predicate>
+ template<typename _IIter, typename _Predicate>
typename iterator_traits<_IIter>::difference_type
- count_if(_IIter, _IIter, Predicate);
+ count_if(_IIter, _IIter, _Predicate);
- template<typename _IIter, typename Predicate>
+ template<typename _IIter, typename _Predicate>
typename iterator_traits<_IIter>::difference_type
- count_if(_IIter, _IIter, Predicate, __gnu_parallel::sequential_tag);
+ count_if(_IIter, _IIter, _Predicate, __gnu_parallel::sequential_tag);
- template<typename _IIter, typename Predicate>
+ template<typename _IIter, typename _Predicate>
typename iterator_traits<_IIter>::difference_type
- count_if(_IIter, _IIter, Predicate, __gnu_parallel::parallelism);
+ count_if(_IIter, _IIter, _Predicate, __gnu_parallel::parallelism);
- template<typename _IIter, typename Predicate, typename _IterTag>
+ template<typename _IIter, typename _Predicate, typename _IterTag>
typename iterator_traits<_IIter>::difference_type
- count_if_switch(_IIter, _IIter, Predicate, _IterTag);
+ count_if_switch(_IIter, _IIter, _Predicate, _IterTag);
- template<typename _RAIter, typename Predicate>
+ template<typename _RAIter, typename _Predicate>
typename iterator_traits<_RAIter>::difference_type
- count_if_switch(_RAIter, _RAIter, Predicate, random_access_iterator_tag,
+ count_if_switch(_RAIter, _RAIter, _Predicate, random_access_iterator_tag,
__gnu_parallel::parallelism);
// algobase.h
template<typename _IIter1, typename _IIter2>
- bool
- equal(_IIter1, _IIter1, _IIter2, __gnu_parallel::sequential_tag);
+ bool
+ equal(_IIter1, _IIter1, _IIter2, __gnu_parallel::sequential_tag);
template<typename _IIter1, typename _IIter2, typename Predicate>
- bool
- equal(_IIter1, _IIter1, _IIter2, Predicate, __gnu_parallel::sequential_tag);
+ bool
+ equal(_IIter1, _IIter1, _IIter2, Predicate,
+ __gnu_parallel::sequential_tag);
template<typename _IIter1, typename _IIter2>
- bool
- equal(_IIter1, _IIter1, _IIter2);
+ bool
+ equal(_IIter1, _IIter1, _IIter2);
template<typename _IIter1, typename _IIter2, typename Predicate>
- bool
- equal(_IIter1, _IIter1, _IIter2, Predicate);
+ bool
+ equal(_IIter1, _IIter1, _IIter2, Predicate);
- template<typename _IIter, typename T>
- _IIter
- find(_IIter, _IIter, const T&, __gnu_parallel::sequential_tag);
-
- template<typename _IIter, typename T>
- _IIter
- find(_IIter, _IIter, const T& val);
-
- template<typename _IIter, typename T, typename _IterTag>
- _IIter
- find_switch(_IIter, _IIter, const T&, _IterTag);
-
- template<typename _RAIter, typename T>
- _RAIter
- find_switch(_RAIter, _RAIter, const T&, random_access_iterator_tag);
-
- template<typename _IIter, typename Predicate>
- _IIter
- find_if(_IIter, _IIter, Predicate, __gnu_parallel::sequential_tag);
-
- template<typename _IIter, typename Predicate>
- _IIter
- find_if(_IIter, _IIter, Predicate);
-
- template<typename _IIter, typename Predicate, typename _IterTag>
- _IIter
- find_if_switch(_IIter, _IIter, Predicate, _IterTag);
+ template<typename _IIter, typename _Tp>
+ _IIter
+ find(_IIter, _IIter, const _Tp&, __gnu_parallel::sequential_tag);
- template<typename _RAIter, typename Predicate>
- _RAIter
- find_if_switch(_RAIter, _RAIter, Predicate, random_access_iterator_tag);
+ template<typename _IIter, typename _Tp>
+ _IIter
+ find(_IIter, _IIter, const _Tp& val);
- template<typename _IIter, typename _FIter>
- _IIter
- find_first_of(_IIter, _IIter, _FIter, _FIter, __gnu_parallel::sequential_tag);
+ template<typename _IIter, typename _Tp, typename _IterTag>
+ _IIter
+ find_switch(_IIter, _IIter, const _Tp&, _IterTag);
- template<typename _IIter, typename _FIter, typename _BiPredicate>
- _IIter
- find_first_of(_IIter, _IIter, _FIter, _FIter, _BiPredicate, __gnu_parallel::sequential_tag);
+ template<typename _RAIter, typename _Tp>
+ _RAIter
+ find_switch(_RAIter, _RAIter, const _Tp&, random_access_iterator_tag);
- template<typename _IIter, typename _FIter, typename _BiPredicate>
- _IIter
- find_first_of(_IIter, _IIter, _FIter, _FIter, _BiPredicate);
+ template<typename _IIter, typename _Predicate>
+ _IIter
+ find_if(_IIter, _IIter, _Predicate, __gnu_parallel::sequential_tag);
- template<typename _IIter, typename _FIter>
- _IIter
- find_first_of(_IIter, _IIter, _FIter, _FIter);
+ template<typename _IIter, typename _Predicate>
+ _IIter
+ find_if(_IIter, _IIter, _Predicate);
- template<typename _IIter, typename _FIter, typename _IterTag1, typename _IterTag2>
- _IIter
- find_first_of_switch(_IIter, _IIter, _FIter, _FIter, _IterTag1, _IterTag2);
+ template<typename _IIter, typename _Predicate, typename _IterTag>
+ _IIter
+ find_if_switch(_IIter, _IIter, _Predicate, _IterTag);
- template<typename _RAIter, typename _FIter, typename _BiPredicate, typename _IterTag>
- _RAIter
- find_first_of_switch(_RAIter, _RAIter, _FIter, _FIter, _BiPredicate, random_access_iterator_tag, _IterTag);
+ template<typename _RAIter, typename _Predicate>
+ _RAIter
+ find_if_switch(_RAIter, _RAIter, _Predicate, random_access_iterator_tag);
- template<typename _IIter, typename _FIter, typename _BiPredicate, typename _IterTag1, typename _IterTag2>
- _IIter
- find_first_of_switch(_IIter, _IIter, _FIter, _FIter, _BiPredicate, _IterTag1, _IterTag2);
+ template<typename _IIter, typename _FIter>
+ _IIter
+ find_first_of(_IIter, _IIter, _FIter, _FIter,
+ __gnu_parallel::sequential_tag);
+ template<typename _IIter, typename _FIter, typename _BiPredicate>
+ _IIter
+ find_first_of(_IIter, _IIter, _FIter, _FIter, _BiPredicate,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter, typename Function>
- Function
- for_each(_IIter, _IIter, Function);
+ template<typename _IIter, typename _FIter, typename _BiPredicate>
+ _IIter
+ find_first_of(_IIter, _IIter, _FIter, _FIter, _BiPredicate);
- template<typename _IIter, typename Function>
- Function
- for_each(_IIter, _IIter, Function, __gnu_parallel::sequential_tag);
+ template<typename _IIter, typename _FIter>
+ _IIter
+ find_first_of(_IIter, _IIter, _FIter, _FIter);
- template<typename Iterator, typename Function>
- Function
- for_each(Iterator, Iterator, Function, __gnu_parallel::parallelism);
+ template<typename _IIter, typename _FIter,
+ typename _IterTag1, typename _IterTag2>
+ _IIter
+ find_first_of_switch(_IIter, _IIter, _FIter, _FIter, _IterTag1, _IterTag2);
- template<typename _IIter, typename Function, typename _IterTag>
- Function
- for_each_switch(_IIter, _IIter, Function, _IterTag);
+ template<typename _RAIter, typename _FIter, typename _BiPredicate,
+ typename _IterTag>
+ _RAIter
+ find_first_of_switch(_RAIter, _RAIter, _FIter, _FIter, _BiPredicate,
+ random_access_iterator_tag, _IterTag);
- template<typename _RAIter, typename Function>
- Function
- for_each_switch(_RAIter, _RAIter, Function, random_access_iterator_tag,
+ template<typename _IIter, typename _FIter, typename _BiPredicate,
+ typename _IterTag1, typename _IterTag2>
+ _IIter
+ find_first_of_switch(_IIter, _IIter, _FIter, _FIter, _BiPredicate,
+ _IterTag1, _IterTag2);
+
+
+ template<typename _IIter, typename _Function>
+ _Function
+ for_each(_IIter, _IIter, _Function);
+
+ template<typename _IIter, typename _Function>
+ _Function
+ for_each(_IIter, _IIter, _Function, __gnu_parallel::sequential_tag);
+
+ template<typename _Iterator, typename _Function>
+ _Function
+ for_each(_Iterator, _Iterator, _Function, __gnu_parallel::parallelism);
+
+ template<typename _IIter, typename _Function, typename _IterTag>
+ _Function
+ for_each_switch(_IIter, _IIter, _Function, _IterTag);
+
+ template<typename _RAIter, typename _Function>
+ _Function
+ for_each_switch(_RAIter, _RAIter, _Function, random_access_iterator_tag,
__gnu_parallel::parallelism);
- template<typename _FIter, typename Generator>
+ template<typename _FIter, typename _Generator>
void
- generate(_FIter, _FIter, Generator);
+ generate(_FIter, _FIter, _Generator);
- template<typename _FIter, typename Generator>
+ template<typename _FIter, typename _Generator>
void
- generate(_FIter, _FIter, Generator, __gnu_parallel::sequential_tag);
+ generate(_FIter, _FIter, _Generator, __gnu_parallel::sequential_tag);
- template<typename _FIter, typename Generator>
+ template<typename _FIter, typename _Generator>
void
- generate(_FIter, _FIter, Generator, __gnu_parallel::parallelism);
+ generate(_FIter, _FIter, _Generator, __gnu_parallel::parallelism);
- template<typename _FIter, typename Generator, typename _IterTag>
+ template<typename _FIter, typename _Generator, typename _IterTag>
void
- generate_switch(_FIter, _FIter, Generator, _IterTag);
+ generate_switch(_FIter, _FIter, _Generator, _IterTag);
- template<typename _RAIter, typename Generator>
+ template<typename _RAIter, typename _Generator>
void
- generate_switch(_RAIter, _RAIter, Generator, random_access_iterator_tag,
+ generate_switch(_RAIter, _RAIter, _Generator, random_access_iterator_tag,
__gnu_parallel::parallelism);
- template<typename _OIter, typename Size, typename Generator>
+ template<typename _OIter, typename _Size, typename _Generator>
_OIter
- generate_n(_OIter, Size, Generator);
+ generate_n(_OIter, _Size, _Generator);
- template<typename _OIter, typename Size, typename Generator>
+ template<typename _OIter, typename _Size, typename _Generator>
_OIter
- generate_n(_OIter, Size, Generator, __gnu_parallel::sequential_tag);
+ generate_n(_OIter, _Size, _Generator, __gnu_parallel::sequential_tag);
- template<typename _OIter, typename Size, typename Generator>
+ template<typename _OIter, typename _Size, typename _Generator>
_OIter
- generate_n(_OIter, Size, Generator, __gnu_parallel::parallelism);
+ generate_n(_OIter, _Size, _Generator, __gnu_parallel::parallelism);
- template<typename _OIter, typename Size, typename Generator, typename _IterTag>
+ template<typename _OIter, typename _Size, typename _Generator,
+ typename _IterTag>
_OIter
- generate_n_switch(_OIter, Size, Generator, _IterTag);
+ generate_n_switch(_OIter, _Size, _Generator, _IterTag);
- template<typename _RAIter, typename Size, typename Generator>
+ template<typename _RAIter, typename _Size, typename _Generator>
_RAIter
- generate_n_switch(_RAIter, Size, Generator, random_access_iterator_tag,
+ generate_n_switch(_RAIter, _Size, _Generator, random_access_iterator_tag,
__gnu_parallel::parallelism);
template<typename _IIter1, typename _IIter2>
- bool
- lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2, __gnu_parallel::sequential_tag);
-
- template<typename _IIter1, typename _IIter2, typename Predicate>
- bool
- lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2, Predicate, __gnu_parallel::sequential_tag);
+ bool
+ lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2,
+ __gnu_parallel::sequential_tag);
+
+ template<typename _IIter1, typename _IIter2, typename _Predicate>
+ bool
+ lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2, _Predicate,
+ __gnu_parallel::sequential_tag);
template<typename _IIter1, typename _IIter2>
- bool
- lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2);
+ bool
+ lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2);
- template<typename _IIter1, typename _IIter2, typename Predicate>
- bool
- lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2, Predicate);
-
- template<typename _IIter1, typename _IIter2, typename Predicate, typename _IterTag1, typename _IterTag2>
- bool
- lexicographical_compare_switch(_IIter1, _IIter1, _IIter2, _IIter2, Predicate, _IterTag1, _IterTag2);
-
- template<typename _RAIter1, typename _RAIter2, typename Predicate>
- bool
- lexicographical_compare_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, Predicate, random_access_iterator_tag, random_access_iterator_tag);
+ template<typename _IIter1, typename _IIter2, typename _Predicate>
+ bool
+ lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2, _Predicate);
+
+ template<typename _IIter1, typename _IIter2,
+ typename _Predicate, typename _IterTag1, typename _IterTag2>
+ bool
+ lexicographical_compare_switch(_IIter1, _IIter1, _IIter2, _IIter2,
+ _Predicate, _IterTag1, _IterTag2);
+
+ template<typename _RAIter1, typename _RAIter2, typename _Predicate>
+ bool
+ lexicographical_compare_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2,
+ _Predicate, random_access_iterator_tag,
+ random_access_iterator_tag);
// algo.h
template<typename _IIter1, typename _IIter2>
- pair<_IIter1, _IIter2>
- mismatch(_IIter1, _IIter1, _IIter2, __gnu_parallel::sequential_tag);
+ pair<_IIter1, _IIter2>
+ mismatch(_IIter1, _IIter1, _IIter2, __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename Predicate>
- pair<_IIter1, _IIter2>
- mismatch(_IIter1, _IIter1, _IIter2, Predicate, __gnu_parallel::sequential_tag);
+ template<typename _IIter1, typename _IIter2, typename _Predicate>
+ pair<_IIter1, _IIter2>
+ mismatch(_IIter1, _IIter1, _IIter2, _Predicate,
+ __gnu_parallel::sequential_tag);
template<typename _IIter1, typename _IIter2>
- pair<_IIter1, _IIter2>
- mismatch(_IIter1, _IIter1, _IIter2);
+ pair<_IIter1, _IIter2>
+ mismatch(_IIter1, _IIter1, _IIter2);
- template<typename _IIter1, typename _IIter2, typename Predicate>
- pair<_IIter1, _IIter2>
- mismatch(_IIter1, _IIter1, _IIter2, Predicate);
-
- template<typename _IIter1, typename _IIter2, typename Predicate, typename _IterTag1, typename _IterTag2>
- pair<_IIter1, _IIter2>
- mismatch_switch(_IIter1, _IIter1, _IIter2, Predicate, _IterTag1, _IterTag2);
-
- template<typename _RAIter1, typename _RAIter2, typename Predicate>
- pair<_RAIter1, _RAIter2>
- mismatch_switch(_RAIter1, _RAIter1, _RAIter2, Predicate, random_access_iterator_tag, random_access_iterator_tag);
+ template<typename _IIter1, typename _IIter2, typename _Predicate>
+ pair<_IIter1, _IIter2>
+ mismatch(_IIter1, _IIter1, _IIter2, _Predicate);
+
+ template<typename _IIter1, typename _IIter2, typename _Predicate,
+ typename _IterTag1, typename _IterTag2>
+ pair<_IIter1, _IIter2>
+ mismatch_switch(_IIter1, _IIter1, _IIter2, _Predicate,
+ _IterTag1, _IterTag2);
+
+ template<typename _RAIter1, typename _RAIter2, typename _Predicate>
+ pair<_RAIter1, _RAIter2>
+ mismatch_switch(_RAIter1, _RAIter1, _RAIter2, _Predicate,
+ random_access_iterator_tag, random_access_iterator_tag);
template<typename _FIter1, typename _FIter2>
- _FIter1
- search(_FIter1, _FIter1, _FIter2, _FIter2, __gnu_parallel::sequential_tag);
+ _FIter1
+ search(_FIter1, _FIter1, _FIter2, _FIter2, __gnu_parallel::sequential_tag);
template<typename _FIter1, typename _FIter2>
- _FIter1
- search(_FIter1, _FIter1, _FIter2, _FIter2);
+ _FIter1
+ search(_FIter1, _FIter1, _FIter2, _FIter2);
template<typename _FIter1, typename _FIter2, typename _BiPredicate>
- _FIter1
- search(_FIter1, _FIter1, _FIter2, _FIter2, _BiPredicate, __gnu_parallel::sequential_tag);
+ _FIter1
+ search(_FIter1, _FIter1, _FIter2, _FIter2, _BiPredicate,
+ __gnu_parallel::sequential_tag);
template<typename _FIter1, typename _FIter2, typename _BiPredicate>
- _FIter1
- search(_FIter1, _FIter1, _FIter2, _FIter2, _BiPredicate);
+ _FIter1
+ search(_FIter1, _FIter1, _FIter2, _FIter2, _BiPredicate);
template<typename _RAIter1, typename _RAIter2>
- _RAIter1
- search_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, random_access_iterator_tag, random_access_iterator_tag);
-
- template<typename _FIter1, typename _FIter2, typename _IterTag1, typename _IterTag2>
- _FIter1
- search_switch(_FIter1, _FIter1, _FIter2, _FIter2, _IterTag1, _IterTag2);
+ _RAIter1
+ search_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2,
+ random_access_iterator_tag, random_access_iterator_tag);
+
+ template<typename _FIter1, typename _FIter2, typename _IterTag1,
+ typename _IterTag2>
+ _FIter1
+ search_switch(_FIter1, _FIter1, _FIter2, _FIter2, _IterTag1, _IterTag2);
template<typename _RAIter1, typename _RAIter2, typename _BiPredicate>
- _RAIter1
- search_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, _BiPredicate , random_access_iterator_tag, random_access_iterator_tag);
+ _RAIter1
+ search_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, _BiPredicate,
+ random_access_iterator_tag, random_access_iterator_tag);
+
+ template<typename _FIter1, typename _FIter2, typename _BiPredicate,
+ typename _IterTag1, typename _IterTag2>
+ _FIter1
+ search_switch(_FIter1, _FIter1, _FIter2, _FIter2, _BiPredicate,
+ _IterTag1, _IterTag2);
+
+ template<typename _FIter, typename _Integer, typename _Tp>
+ _FIter
+ search_n(_FIter, _FIter, _Integer, const _Tp&,
+ __gnu_parallel::sequential_tag);
- template<typename _FIter1, typename _FIter2, typename _BiPredicate, typename _IterTag1, typename _IterTag2>
- _FIter1
- search_switch(_FIter1, _FIter1, _FIter2, _FIter2, _BiPredicate, _IterTag1, _IterTag2);
-
- template<typename _FIter, typename Integer, typename T>
- _FIter
- search_n(_FIter, _FIter, Integer, const T&, __gnu_parallel::sequential_tag);
-
- template<typename _FIter, typename Integer, typename T, typename _BiPredicate>
- _FIter
- search_n(_FIter, _FIter, Integer, const T&, _BiPredicate, __gnu_parallel::sequential_tag);
+ template<typename _FIter, typename _Integer, typename _Tp,
+ typename _BiPredicate>
+ _FIter
+ search_n(_FIter, _FIter, _Integer, const _Tp&, _BiPredicate,
+ __gnu_parallel::sequential_tag);
- template<typename _FIter, typename Integer, typename T>
- _FIter
- search_n(_FIter, _FIter, Integer, const T& val);
-
- template<typename _FIter, typename Integer, typename T, typename _BiPredicate>
- _FIter
- search_n(_FIter, _FIter, Integer, const T&, _BiPredicate);
-
- template<typename _RAIter, typename Integer, typename T, typename _BiPredicate>
- _RAIter
- search_n_switch(_RAIter, _RAIter, Integer, const T&, _BiPredicate, random_access_iterator_tag);
-
- template<typename _FIter, typename Integer, typename T, typename _BiPredicate, typename _IterTag>
- _FIter
- search_n_switch(_FIter, _FIter, Integer, const T&, _BiPredicate, _IterTag);
+ template<typename _FIter, typename _Integer, typename _Tp>
+ _FIter
+ search_n(_FIter, _FIter, _Integer, const _Tp&);
+
+ template<typename _FIter, typename _Integer, typename _Tp,
+ typename _BiPredicate>
+ _FIter
+ search_n(_FIter, _FIter, _Integer, const _Tp&, _BiPredicate);
+
+ template<typename _RAIter, typename _Integer, typename _Tp,
+ typename _BiPredicate>
+ _RAIter
+ search_n_switch(_RAIter, _RAIter, _Integer, const _Tp&,
+ _BiPredicate, random_access_iterator_tag);
+
+ template<typename _FIter, typename _Integer, typename _Tp,
+ typename _BiPredicate, typename _IterTag>
+ _FIter
+ search_n_switch(_FIter, _FIter, _Integer, const _Tp&,
+ _BiPredicate, _IterTag);
template<typename _IIter, typename _OIter, typename UnaryOperation>
@@ -385,7 +418,8 @@
transform(_IIter, _IIter, _OIter, UnaryOperation,
__gnu_parallel::parallelism);
- template<typename _IIter, typename _OIter, typename UnaryOperation, typename _IterTag1, typename _IterTag2>
+ template<typename _IIter, typename _OIter, typename UnaryOperation,
+ typename _IterTag1, typename _IterTag2>
_OIter
transform1_switch(_IIter, _IIter, _OIter, UnaryOperation,
_IterTag1, _IterTag2);
@@ -398,78 +432,87 @@
__gnu_parallel::parallelism);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _BiOperation>
+ template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _BiOperation>
_OIter
transform(_IIter1, _IIter1, _IIter2, _OIter, _BiOperation);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _BiOperation>
+ template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _BiOperation>
_OIter
transform(_IIter1, _IIter1, _IIter2, _OIter, _BiOperation,
__gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _BiOperation>
+ template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _BiOperation>
_OIter
transform(_IIter1, _IIter1, _IIter2, _OIter, _BiOperation,
__gnu_parallel::parallelism);
- template<typename _RAIter1, typename _RAIter2, typename _RAIter3, typename _BiOperation>
+ template<typename _RAIter1, typename _RAIter2, typename _RAIter3,
+ typename _BiOperation>
_RAIter3
transform2_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter3, _BiOperation,
random_access_iterator_tag, random_access_iterator_tag,
random_access_iterator_tag,
__gnu_parallel::parallelism parallelism_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _BiOperation, typename tag1, typename tag2, typename tag3>
+ template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _BiOperation, typename _Tag1,
+ typename _Tag2, typename _Tag3>
_OIter
transform2_switch(_IIter1, _IIter1, _IIter2, _OIter, _BiOperation,
- tag1, tag2, tag3);
+ _Tag1, _Tag2, _Tag3);
- template<typename _FIter, typename T>
+ template<typename _FIter, typename _Tp>
void
- replace(_FIter, _FIter, const T&, const T&);
+ replace(_FIter, _FIter, const _Tp&, const _Tp&);
- template<typename _FIter, typename T>
+ template<typename _FIter, typename _Tp>
void
- replace(_FIter, _FIter, const T&, const T&,
+ replace(_FIter, _FIter, const _Tp&, const _Tp&,
__gnu_parallel::sequential_tag);
- template<typename _FIter, typename T>
+ template<typename _FIter, typename _Tp>
void
- replace(_FIter, _FIter, const T&, const T&, __gnu_parallel::parallelism);
+ replace(_FIter, _FIter, const _Tp&, const _Tp&,
+ __gnu_parallel::parallelism);
- template<typename _FIter, typename T, typename _IterTag>
+ template<typename _FIter, typename _Tp, typename _IterTag>
void
- replace_switch(_FIter, _FIter, const T&, const T&, _IterTag);
+ replace_switch(_FIter, _FIter, const _Tp&, const _Tp&, _IterTag);
- template<typename _RAIter, typename T>
+ template<typename _RAIter, typename _Tp>
void
- replace_switch(_RAIter, _RAIter, const T&, const T&,
+ replace_switch(_RAIter, _RAIter, const _Tp&, const _Tp&,
random_access_iterator_tag, __gnu_parallel::parallelism);
- template<typename _FIter, typename Predicate, typename T>
+ template<typename _FIter, typename _Predicate, typename _Tp>
void
- replace_if(_FIter, _FIter, Predicate, const T&);
+ replace_if(_FIter, _FIter, _Predicate, const _Tp&);
- template<typename _FIter, typename Predicate, typename T>
+ template<typename _FIter, typename _Predicate, typename _Tp>
void
- replace_if(_FIter, _FIter, Predicate, const T&,
+ replace_if(_FIter, _FIter, _Predicate, const _Tp&,
__gnu_parallel::sequential_tag);
- template<typename _FIter, typename Predicate, typename T>
+ template<typename _FIter, typename _Predicate, typename _Tp>
void
- replace_if(_FIter, _FIter, Predicate, const T&,
+ replace_if(_FIter, _FIter, _Predicate, const _Tp&,
__gnu_parallel::parallelism);
- template<typename _FIter, typename Predicate, typename T, typename _IterTag>
+ template<typename _FIter, typename _Predicate, typename _Tp,
+ typename _IterTag>
void
- replace_if_switch(_FIter, _FIter, Predicate, const T&, _IterTag);
+ replace_if_switch(_FIter, _FIter, _Predicate, const _Tp&, _IterTag);
- template<typename _RAIter, typename Predicate, typename T>
+ template<typename _RAIter, typename _Predicate, typename _Tp>
void
- replace_if_switch(_RAIter, _RAIter, Predicate, const T&,
- random_access_iterator_tag, __gnu_parallel::parallelism);
+ replace_if_switch(_RAIter, _RAIter, _Predicate, const _Tp&,
+ random_access_iterator_tag,
+ __gnu_parallel::parallelism);
template<typename _FIter>
@@ -511,12 +554,14 @@
merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
__gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _Compare>
+ template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Compare>
_OIter
merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare,
__gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _Compare>
+ template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Compare>
_OIter
merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare);
@@ -524,12 +569,15 @@
_OIter
merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _Compare, typename _IterTag1, typename _IterTag2, typename _IterTag3>
+ template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Compare, typename _IterTag1, typename _IterTag2,
+ typename _IterTag3>
_OIter
merge_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare,
_IterTag1, _IterTag2, _IterTag3);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _Compare>
+ template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Compare>
_OIter
merge_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare,
random_access_iterator_tag, random_access_iterator_tag,
@@ -570,223 +618,277 @@
__gnu_parallel::parallelism);
template<typename _RAIter>
- void
- nth_element(_RAIter, _RAIter, _RAIter, __gnu_parallel::sequential_tag);
+ void
+ nth_element(_RAIter, _RAIter, _RAIter, __gnu_parallel::sequential_tag);
template<typename _RAIter, typename _Compare>
- void
- nth_element(_RAIter, _RAIter, _RAIter, _Compare, __gnu_parallel::sequential_tag);
+ void
+ nth_element(_RAIter, _RAIter, _RAIter, _Compare,
+ __gnu_parallel::sequential_tag);
template<typename _RAIter, typename _Compare>
- void
- nth_element(_RAIter, _RAIter, _RAIter, _Compare);
+ void
+ nth_element(_RAIter, _RAIter, _RAIter, _Compare);
template<typename _RAIter>
- void
- nth_element(_RAIter, _RAIter, _RAIter);
+ void
+ nth_element(_RAIter, _RAIter, _RAIter);
template<typename _RAIter, typename _Compare>
- void
- partial_sort(_RAIter, _RAIter, _RAIter, _Compare, __gnu_parallel::sequential_tag);
+ void
+ partial_sort(_RAIter, _RAIter, _RAIter, _Compare,
+ __gnu_parallel::sequential_tag);
template<typename _RAIter>
- void
- partial_sort(_RAIter, _RAIter, _RAIter, __gnu_parallel::sequential_tag);
+ void
+ partial_sort(_RAIter, _RAIter, _RAIter, __gnu_parallel::sequential_tag);
template<typename _RAIter, typename _Compare>
- void
- partial_sort(_RAIter, _RAIter, _RAIter, _Compare);
+ void
+ partial_sort(_RAIter, _RAIter, _RAIter, _Compare);
template<typename _RAIter>
- void
- partial_sort(_RAIter, _RAIter, _RAIter);
+ void
+ partial_sort(_RAIter, _RAIter, _RAIter);
template<typename _FIter, typename Predicate>
- _FIter
- partition(_FIter, _FIter, Predicate, __gnu_parallel::sequential_tag);
+ _FIter
+ partition(_FIter, _FIter, Predicate, __gnu_parallel::sequential_tag);
template<typename _FIter, typename Predicate>
- _FIter
- partition(_FIter, _FIter, Predicate);
+ _FIter
+ partition(_FIter, _FIter, Predicate);
template<typename _FIter, typename Predicate, typename _IterTag>
- _FIter
- partition_switch(_FIter, _FIter, Predicate, _IterTag);
+ _FIter
+ partition_switch(_FIter, _FIter, Predicate, _IterTag);
template<typename _RAIter, typename Predicate>
- _RAIter
- partition_switch(_RAIter, _RAIter, Predicate, random_access_iterator_tag);
+ _RAIter
+ partition_switch(_RAIter, _RAIter, Predicate, random_access_iterator_tag);
template<typename _RAIter>
- void
- random_shuffle(_RAIter, _RAIter, __gnu_parallel::sequential_tag);
+ void
+ random_shuffle(_RAIter, _RAIter, __gnu_parallel::sequential_tag);
- template<typename _RAIter, typename RandomNumberGenerator>
- void
- random_shuffle(_RAIter, _RAIter, RandomNumberGenerator& rand, __gnu_parallel::sequential_tag);
+ template<typename _RAIter, typename _RandomNumberGenerator>
+ void
+ random_shuffle(_RAIter, _RAIter, _RandomNumberGenerator&,
+ __gnu_parallel::sequential_tag);
template<typename _RAIter>
- void
- random_shuffle(_RAIter, _RAIter);
+ void
+ random_shuffle(_RAIter, _RAIter);
- template<typename _RAIter, typename RandomNumberGenerator>
- void
- random_shuffle(_RAIter, _RAIter, RandomNumberGenerator& rand);
+ template<typename _RAIter, typename _RandomNumberGenerator>
+ void
+ random_shuffle(_RAIter, _RAIter, _RandomNumberGenerator&);
template<typename _IIter1, typename _IIter2, typename _OIter>
- _OIter
- set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, __gnu_parallel::sequential_tag);
+ _OIter
+ set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
- _OIter
- set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, __gnu_parallel::sequential_tag);
+ template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename Predicate>
+ _OIter
+ set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate,
+ __gnu_parallel::sequential_tag);
template<typename _IIter1, typename _IIter2, typename _OIter>
- _OIter
- set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
+ _OIter
+ set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
- _OIter
- set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate);
-
- template<typename _IIter1, typename _IIter2, typename Predicate, typename _OIter, typename _IterTag1, typename _IterTag2, typename _IterTag3>
- _OIter
- set_union_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, _IterTag1, _IterTag2, _IterTag3);
-
- template<typename _RAIter1, typename _RAIter2, typename Output_RAIter, typename Predicate>
- Output_RAIter
- set_union_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, Output_RAIter, Predicate, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag);
+ template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Predicate>
+ _OIter
+ set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Predicate);
+
+ template<typename _IIter1, typename _IIter2, typename _Predicate,
+ typename _OIter, typename _IterTag1, typename _IterTag2,
+ typename _IterTag3>
+ _OIter
+ set_union_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ _Predicate, _IterTag1, _IterTag2, _IterTag3);
+
+ template<typename _RAIter1, typename _RAIter2, typename _Output_RAIter,
+ typename _Predicate>
+ _Output_RAIter
+ set_union_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, _Output_RAIter,
+ _Predicate, random_access_iterator_tag,
+ random_access_iterator_tag, random_access_iterator_tag);
template<typename _IIter1, typename _IIter2, typename _OIter>
- _OIter
- set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, __gnu_parallel::sequential_tag);
+ _OIter
+ set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
- _OIter
- set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, __gnu_parallel::sequential_tag);
+ template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Predicate>
+ _OIter
+ set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Predicate,
+ __gnu_parallel::sequential_tag);
template<typename _IIter1, typename _IIter2, typename _OIter>
- _OIter
- set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
+ _OIter
+ set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
- _OIter
- set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate);
-
- template<typename _IIter1, typename _IIter2, typename Predicate, typename _OIter, typename _IterTag1, typename _IterTag2, typename _IterTag3>
- _OIter
- set_intersection_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, _IterTag1, _IterTag2, _IterTag3);
-
- template<typename _RAIter1, typename _RAIter2, typename Output_RAIter, typename Predicate>
- Output_RAIter
- set_intersection_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, Output_RAIter, Predicate, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag);
+ template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Predicate>
+ _OIter
+ set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Predicate);
+
+ template<typename _IIter1, typename _IIter2, typename _Predicate,
+ typename _OIter, typename _IterTag1, typename _IterTag2,
+ typename _IterTag3>
+ _OIter
+ set_intersection_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ _Predicate, _IterTag1, _IterTag2, _IterTag3);
+
+ template<typename _RAIter1, typename _RAIter2, typename _Output_RAIter,
+ typename _Predicate>
+ _Output_RAIter
+ set_intersection_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2,
+ _Output_RAIter, _Predicate,
+ random_access_iterator_tag,
+ random_access_iterator_tag,
+ random_access_iterator_tag);
template<typename _IIter1, typename _IIter2, typename _OIter>
- _OIter
- set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, __gnu_parallel::sequential_tag);
+ _OIter
+ set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
- _OIter
- set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, __gnu_parallel::sequential_tag);
+ template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Predicate>
+ _OIter
+ set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ _Predicate, __gnu_parallel::sequential_tag);
template<typename _IIter1, typename _IIter2, typename _OIter>
- _OIter
- set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
+ _OIter
+ set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
- _OIter
- set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate);
-
- template<typename _IIter1, typename _IIter2, typename Predicate, typename _OIter, typename _IterTag1, typename _IterTag2, typename _IterTag3>
- _OIter
- set_symmetric_difference_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, _IterTag1, _IterTag2, _IterTag3);
-
- template<typename _RAIter1, typename _RAIter2, typename Output_RAIter, typename Predicate>
- Output_RAIter
- set_symmetric_difference_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, Output_RAIter, Predicate, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag);
+ template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Predicate>
+ _OIter
+ set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ _Predicate);
+
+ template<typename _IIter1, typename _IIter2, typename _Predicate,
+ typename _OIter, typename _IterTag1, typename _IterTag2,
+ typename _IterTag3>
+ _OIter
+ set_symmetric_difference_switch(_IIter1, _IIter1, _IIter2, _IIter2,
+ _OIter, _Predicate, _IterTag1, _IterTag2,
+ _IterTag3);
+
+ template<typename _RAIter1, typename _RAIter2, typename _Output_RAIter,
+ typename _Predicate>
+ _Output_RAIter
+ set_symmetric_difference_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2,
+ _Output_RAIter, _Predicate,
+ random_access_iterator_tag,
+ random_access_iterator_tag,
+ random_access_iterator_tag);
template<typename _IIter1, typename _IIter2, typename _OIter>
- _OIter
- set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, __gnu_parallel::sequential_tag);
+ _OIter
+ set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
- _OIter
- set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, __gnu_parallel::sequential_tag);
+ template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Predicate>
+ _OIter
+ set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Predicate,
+ __gnu_parallel::sequential_tag);
template<typename _IIter1, typename _IIter2, typename _OIter>
- _OIter
- set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
+ _OIter
+ set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
- _OIter
- set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate);
+ template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Predicate>
+ _OIter
+ set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Predicate);
- template<typename _IIter1, typename _IIter2, typename Predicate, typename _OIter, typename _IterTag1, typename _IterTag2, typename _IterTag3>
- _OIter
- set_difference_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, _IterTag1, _IterTag2, _IterTag3);
+ template<typename _IIter1, typename _IIter2, typename _Predicate,
+ typename _OIter, typename _IterTag1, typename _IterTag2,
+ typename _IterTag3>
+ _OIter
+ set_difference_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ _Predicate, _IterTag1, _IterTag2, _IterTag3);
- template<typename _RAIter1, typename _RAIter2, typename Output_RAIter, typename Predicate>
- Output_RAIter
- set_difference_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, Output_RAIter, Predicate, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag);
+ template<typename _RAIter1, typename _RAIter2, typename _Output_RAIter,
+ typename _Predicate>
+ _Output_RAIter
+ set_difference_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2,
+ _Output_RAIter, _Predicate,
+ random_access_iterator_tag,
+ random_access_iterator_tag,
+ random_access_iterator_tag);
template<typename _RAIter>
- void
- sort(_RAIter, _RAIter, __gnu_parallel::sequential_tag);
+ void
+ sort(_RAIter, _RAIter, __gnu_parallel::sequential_tag);
template<typename _RAIter, typename _Compare>
- void
- sort(_RAIter, _RAIter, _Compare, __gnu_parallel::sequential_tag);
+ void
+ sort(_RAIter, _RAIter, _Compare, __gnu_parallel::sequential_tag);
template<typename _RAIter>
- void
- sort(_RAIter, _RAIter);
+ void
+ sort(_RAIter, _RAIter);
template<typename _RAIter, typename _Compare>
- void
- sort(_RAIter, _RAIter, _Compare);
+ void
+ sort(_RAIter, _RAIter, _Compare);
template<typename _RAIter>
- void
- stable_sort(_RAIter, _RAIter, __gnu_parallel::sequential_tag);
+ void
+ stable_sort(_RAIter, _RAIter, __gnu_parallel::sequential_tag);
template<typename _RAIter, typename _Compare>
- void
- stable_sort(_RAIter, _RAIter, _Compare, __gnu_parallel::sequential_tag);
+ void
+ stable_sort(_RAIter, _RAIter, _Compare, __gnu_parallel::sequential_tag);
template<typename _RAIter>
- void
- stable_sort(_RAIter, _RAIter);
+ void
+ stable_sort(_RAIter, _RAIter);
template<typename _RAIter, typename _Compare>
- void
- stable_sort(_RAIter, _RAIter, _Compare);
+ void
+ stable_sort(_RAIter, _RAIter, _Compare);
template<typename _IIter, typename _OIter>
- _OIter
- unique_copy(_IIter, _IIter, _OIter, __gnu_parallel::sequential_tag);
+ _OIter
+ unique_copy(_IIter, _IIter, _OIter, __gnu_parallel::sequential_tag);
- template<typename _IIter, typename _OIter, typename Predicate>
- _OIter
- unique_copy(_IIter, _IIter, _OIter, Predicate, __gnu_parallel::sequential_tag);
+ template<typename _IIter, typename _OIter, typename _Predicate>
+ _OIter
+ unique_copy(_IIter, _IIter, _OIter, _Predicate,
+ __gnu_parallel::sequential_tag);
template<typename _IIter, typename _OIter>
- _OIter
- unique_copy(_IIter, _IIter, _OIter);
+ _OIter
+ unique_copy(_IIter, _IIter, _OIter);
- template<typename _IIter, typename _OIter, typename Predicate>
- _OIter
- unique_copy(_IIter, _IIter, _OIter, Predicate);
-
- template<typename _IIter, typename _OIter, typename Predicate, typename _IterTag1, typename _IterTag2>
- _OIter
- unique_copy_switch(_IIter, _IIter, _OIter, Predicate, _IterTag1, _IterTag2);
-
- template<typename _RAIter, typename RandomAccess_OIter, typename Predicate>
- RandomAccess_OIter
- unique_copy_switch(_RAIter, _RAIter, RandomAccess_OIter, Predicate,
- random_access_iterator_tag, random_access_iterator_tag);
+ template<typename _IIter, typename _OIter, typename _Predicate>
+ _OIter
+ unique_copy(_IIter, _IIter, _OIter, _Predicate);
+
+ template<typename _IIter, typename _OIter, typename _Predicate,
+ typename _IterTag1, typename _IterTag2>
+ _OIter
+ unique_copy_switch(_IIter, _IIter, _OIter, _Predicate,
+ _IterTag1, _IterTag2);
+
+ template<typename _RAIter, typename _RandomAccess_OIter, typename _Predicate>
+ _RandomAccess_OIter
+ unique_copy_switch(_RAIter, _RAIter, _RandomAccess_OIter, _Predicate,
+ random_access_iterator_tag, random_access_iterator_tag);
} // end namespace __parallel
} // end namespace std
Index: include/parallel/for_each_selectors.h
===================================================================
--- include/parallel/for_each_selectors.h (revision 131429)
+++ include/parallel/for_each_selectors.h (working copy)
@@ -1,6 +1,6 @@
// -*- C++ -*-
-// Copyright (C) 2007 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
@@ -63,11 +63,12 @@
* @param o Operator.
* @param i Iterator referencing object. */
template<typename Op>
- inline bool operator()(Op& o, It i)
- {
- o(*i);
- return true;
- }
+ bool
+ operator()(Op& o, It i)
+ {
+ o(*i);
+ return true;
+ }
};
/** @brief std::generate() selector. */
@@ -78,11 +79,12 @@
* @param o Operator.
* @param i Iterator referencing object. */
template<typename Op>
- inline bool operator()(Op& o, It i)
- {
- *i = o();
- return true;
- }
+ bool
+ operator()(Op& o, It i)
+ {
+ *i = o();
+ return true;
+ }
};
/** @brief std::fill() selector. */
@@ -93,11 +95,12 @@
* @param v Current value.
* @param i Iterator referencing object. */
template<typename Val>
- inline bool operator()(Val& v, It i)
- {
- *i = v;
- return true;
- }
+ bool
+ operator()(Val& v, It i)
+ {
+ *i = v;
+ return true;
+ }
};
/** @brief std::transform() selector, one input sequence variant. */
@@ -108,11 +111,12 @@
* @param o Operator.
* @param i Iterator referencing object. */
template<typename Op>
- inline bool operator()(Op& o, It i)
- {
- *i.second = o(*i.first);
- return true;
- }
+ bool
+ operator()(Op& o, It i)
+ {
+ *i.second = o(*i.first);
+ return true;
+ }
};
/** @brief std::transform() selector, two input sequences variant. */
@@ -123,11 +127,12 @@
* @param o Operator.
* @param i Iterator referencing object. */
template<typename Op>
- inline bool operator()(Op& o, It i)
- {
- *i.third = o(*i.first, *i.second);
- return true;
- }
+ bool
+ operator()(Op& o, It i)
+ {
+ *i.third = o(*i.first, *i.second);
+ return true;
+ }
};
/** @brief std::replace() selector. */
@@ -144,7 +149,8 @@
/** @brief Functor execution.
* @param v Current value.
* @param i Iterator referencing object. */
- inline bool operator()(T& v, It i)
+ bool
+ operator()(T& v, It i)
{
if (*i == v)
*i = new_val;
@@ -166,7 +172,8 @@
/** @brief Functor execution.
* @param o Operator.
* @param i Iterator referencing object. */
- inline bool operator()(Op& o, It i)
+ bool
+ operator()(Op& o, It i)
{
if (o(*i))
*i = new_val;
@@ -183,8 +190,9 @@
* @param i Iterator referencing object.
* @return 1 if count, 0 if does not count. */
template<typename Val>
- inline Diff operator()(Val& v, It i)
- { return (v == *i) ? 1 : 0; }
+ Diff
+ operator()(Val& v, It i)
+ { return (v == *i) ? 1 : 0; }
};
/** @brief std::count_if () selector. */
@@ -196,8 +204,9 @@
* @param i Iterator referencing object.
* @return 1 if count, 0 if does not count. */
template<typename Op>
- inline Diff operator()(Op& o, It i)
- { return (o(*i)) ? 1 : 0; }
+ Diff
+ operator()(Op& o, It i)
+ { return (o(*i)) ? 1 : 0; }
};
/** @brief std::accumulate() selector. */
@@ -209,8 +218,8 @@
* @param i Iterator referencing object.
* @return The current value. */
template<typename Op>
- inline typename std::iterator_traits<It>::value_type operator()(Op o, It i)
- { return *i; }
+ typename std::iterator_traits<It>::value_type operator()(Op o, It i)
+ { return *i; }
};
/** @brief std::inner_product() selector. */
@@ -226,18 +235,21 @@
/** @brief Constructor.
* @param b1 Begin iterator of first sequence.
* @param b2 Begin iterator of second sequence. */
- explicit inner_product_selector(It b1, It2 b2) : begin1_iterator(b1), begin2_iterator(b2) { }
+ explicit inner_product_selector(It b1, It2 b2)
+ : begin1_iterator(b1), begin2_iterator(b2) { }
/** @brief Functor execution.
* @param mult Multiplication functor.
* @param current Iterator referencing object.
* @return Inner product elemental result. */
template<typename Op>
- inline T operator()(Op mult, It current)
- {
- typename std::iterator_traits<It>::difference_type position = current - begin1_iterator;
- return mult(*current, *(begin2_iterator + position));
- }
+ T
+ operator()(Op mult, It current)
+ {
+ typename std::iterator_traits<It>::difference_type position
+ = current - begin1_iterator;
+ return mult(*current, *(begin2_iterator + position));
+ }
};
/** @brief Selector that just returns the passed iterator. */
@@ -249,8 +261,9 @@
* @param i Iterator referencing object.
* @return Passed iterator. */
template<typename Op>
- inline It operator()(Op o, It i)
- { return i; }
+ It
+ operator()(Op o, It i)
+ { return i; }
};
/** @brief Selector that returns the difference between two adjacent
@@ -260,13 +273,14 @@
struct adjacent_difference_selector : public generic_for_each_selector<It>
{
template<typename Op>
- inline bool operator()(Op& o, It i)
- {
- typename It::first_type go_back_one = i.first;
- --go_back_one;
- *i.second = o(*i.first, *go_back_one);
- return true;
- }
+ bool
+ operator()(Op& o, It i)
+ {
+ typename It::first_type go_back_one = i.first;
+ --go_back_one;
+ *i.second = o(*i.first, *go_back_one);
+ return true;
+ }
};
// XXX move into type_traits?
@@ -280,14 +294,15 @@
/** @brief Functor execution.
* @param i Iterator referencing object. */
template<typename It>
- inline void operator()(It i)
- { }
+ void
+ operator()(It i) { }
};
/** @brief Reduction function doing nothing. */
struct dummy_reduct
{
- inline bool operator()(bool /*x*/, bool /*y*/) const
+ bool
+ operator()(bool /*x*/, bool /*y*/) const
{ return true; }
};
@@ -300,7 +315,8 @@
explicit min_element_reduct(Comp &c) : comp(c)
{ }
- inline It operator()(It x, It y)
+ It
+ operator()(It x, It y)
{
if (comp(*x, *y))
return x;
@@ -318,7 +334,8 @@
explicit max_element_reduct(Comp& c) : comp(c)
{ }
- inline It operator()(It x, It y)
+ It
+ operator()(It x, It y)
{
if (comp(*x, *y))
return y;
@@ -336,7 +353,9 @@
explicit accumulate_binop_reduct(BinOp& b) : binop(b) {}
template<typename Result, typename Addend>
- Result operator()(const Result& x, const Addend& y) { return binop(x, y); }
+ Result
+ operator()(const Result& x, const Addend& y)
+ { return binop(x, y); }
};
}
Index: include/parallel/balanced_quicksort.h
===================================================================
--- include/parallel/balanced_quicksort.h (revision 131429)
+++ include/parallel/balanced_quicksort.h (working copy)
@@ -1,6 +1,6 @@
// -*- C++ -*-
-// Copyright (C) 2007 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
@@ -102,7 +102,7 @@
* this part.
* @pre @c (end-begin)>=1 */
template<typename RandomAccessIterator, typename Comparator>
- inline typename std::iterator_traits<RandomAccessIterator>::difference_type
+ typename std::iterator_traits<RandomAccessIterator>::difference_type
qsb_divide(RandomAccessIterator begin, RandomAccessIterator end,
Comparator comp, thread_index_t num_threads)
{
@@ -164,7 +164,7 @@
* @param num_threads
* Number of threads that are allowed to work on this part. */
template<typename RandomAccessIterator, typename Comparator>
- inline void
+ void
qsb_conquer(QSBThreadLocal<RandomAccessIterator>** tls,
RandomAccessIterator begin, RandomAccessIterator end,
Comparator comp,
@@ -240,7 +240,7 @@
* @param iam Number of the thread processing this function.
*/
template<typename RandomAccessIterator, typename Comparator>
- inline void
+ void
qsb_local_sort_with_helping(QSBThreadLocal<RandomAccessIterator>** tls,
Comparator& comp, int iam, bool wait)
{
@@ -418,7 +418,7 @@
* this part.
*/
template<typename RandomAccessIterator, typename Comparator>
- inline void
+ void
parallel_sort_qsb(RandomAccessIterator begin, RandomAccessIterator end,
Comparator comp,
typename std::iterator_traits<RandomAccessIterator>
Index: include/parallel/merge.h
===================================================================
--- include/parallel/merge.h (revision 131429)
+++ include/parallel/merge.h (working copy)
@@ -1,6 +1,6 @@
// -*- C++ -*-
-// Copyright (C) 2007 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
@@ -56,33 +56,39 @@
* @param max_length Maximum number of elements to merge.
* @param comp Comparator.
* @return Output end iterator. */
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename OutputIterator, typename _DifferenceTp, typename Comparator>
- OutputIterator
- 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--;
- }
-
- if (begin1 != end1)
- {
- target = std::copy(begin1, begin1 + max_length, target);
- begin1 += max_length;
- }
- else
- {
- target = std::copy(begin2, begin2 + max_length, target);
- begin2 += max_length;
- }
- return target;
- }
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename OutputIterator, typename _DifferenceTp,
+ typename Comparator>
+ OutputIterator
+ merge_advance_usual(RandomAccessIterator1& begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator2& begin2,
+ RandomAccessIterator2 end2, OutputIterator target,
+ _DifferenceTp max_length, Comparator comp)
+ {
+ 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--;
+ }
+
+ if (begin1 != end1)
+ {
+ target = std::copy(begin1, begin1 + max_length, target);
+ begin1 += max_length;
+ }
+ else
+ {
+ target = std::copy(begin2, begin2 + max_length, target);
+ begin2 += max_length;
+ }
+ return target;
+ }
/** @brief Merge routine being able to merge only the @c max_length
* smallest elements.
@@ -99,52 +105,59 @@
* @param max_length Maximum number of elements to merge.
* @param comp Comparator.
* @return Output end iterator. */
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename OutputIterator, typename _DifferenceTp, typename Comparator>
- OutputIterator
- merge_advance_movc(RandomAccessIterator1& begin1, RandomAccessIterator1 end1, RandomAccessIterator2& begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp)
- {
- typedef _DifferenceTp difference_type;
- typedef typename std::iterator_traits<RandomAccessIterator1>::value_type value_type1;
- typedef typename std::iterator_traits<RandomAccessIterator2>::value_type value_type2;
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename OutputIterator, typename _DifferenceTp,
+ typename Comparator>
+ OutputIterator
+ merge_advance_movc(RandomAccessIterator1& begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator2& begin2,
+ RandomAccessIterator2 end2,
+ OutputIterator target,
+ _DifferenceTp max_length, Comparator comp)
+ {
+ typedef _DifferenceTp difference_type;
+ typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
+ value_type1;
+ typedef typename std::iterator_traits<RandomAccessIterator2>::value_type
+ value_type2;
#if _GLIBCXX_ASSERTIONS
- _GLIBCXX_PARALLEL_ASSERT(max_length >= 0);
+ _GLIBCXX_PARALLEL_ASSERT(max_length >= 0);
#endif
- while (begin1 != end1 && begin2 != end2 && max_length > 0)
- {
- 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
- {
+ while (begin1 != end1 && begin2 != end2 && max_length > 0)
+ {
+ 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;
- }
- *target = element1;
+ *target = element1;
- target++;
- max_length--;
- }
- if (begin1 != end1)
- {
- target = std::copy(begin1, begin1 + max_length, target);
- begin1 += max_length;
- }
- else
- {
- target = std::copy(begin2, begin2 + max_length, target);
- begin2 += max_length;
- }
- return target;
- }
+ target++;
+ max_length--;
+ }
+ if (begin1 != end1)
+ {
+ target = std::copy(begin1, begin1 + max_length, target);
+ begin1 += max_length;
+ }
+ else
+ {
+ target = std::copy(begin2, begin2 + max_length, target);
+ begin2 += max_length;
+ }
+ return target;
+ }
/** @brief Merge routine being able to merge only the @c max_length
* smallest elements.
@@ -160,14 +173,20 @@
* @param max_length Maximum number of elements to merge.
* @param comp Comparator.
* @return Output end iterator. */
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename OutputIterator, typename _DifferenceTp, typename Comparator>
- inline OutputIterator
- 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);
- }
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename OutputIterator, typename _DifferenceTp,
+ typename Comparator>
+ inline OutputIterator
+ merge_advance(RandomAccessIterator1& begin1, RandomAccessIterator1 end1,
+ RandomAccessIterator2& begin2, RandomAccessIterator2 end2,
+ OutputIterator target, _DifferenceTp max_length,
+ Comparator comp)
+ {
+ _GLIBCXX_CALL(max_length)
+
+ return merge_advance_movc(begin1, end1, begin2, end2, target,
+ max_length, comp);
+ }
/** @brief Merge routine fallback to sequential in case the
iterators of the two input sequences are of different type.
@@ -179,15 +198,20 @@
* @param max_length Maximum number of elements to merge.
* @param comp Comparator.
* @return Output end iterator. */
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename RandomAccessIterator3, typename Comparator>
- inline RandomAccessIterator3
- parallel_merge_advance(RandomAccessIterator1& begin1, RandomAccessIterator1 end1,
- RandomAccessIterator2& begin2, RandomAccessIterator2 end2, //different iterators, parallel implementation not available
- RandomAccessIterator3 target,
- typename std::iterator_traits<RandomAccessIterator1>::difference_type max_length, Comparator comp)
- {
- return merge_advance(begin1, end1, begin2, end2, target, max_length, comp);
- }
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename RandomAccessIterator3, typename Comparator>
+ inline RandomAccessIterator3
+ parallel_merge_advance(RandomAccessIterator1& begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator2& begin2,
+ // different iterators, parallel implementation
+ // not available
+ RandomAccessIterator2 end2,
+ RandomAccessIterator3 target, typename
+ std::iterator_traits<RandomAccessIterator1>::
+ difference_type max_length, Comparator comp)
+ { return merge_advance(begin1, end1, begin2, end2, target,
+ max_length, comp); }
/** @brief Parallel merge routine being able to merge only the @c
* max_length smallest elements.
@@ -204,22 +228,33 @@
* @param comp Comparator.
* @return Output end iterator.
*/
- template<typename RandomAccessIterator1, typename RandomAccessIterator3, typename Comparator>
- inline RandomAccessIterator3
- parallel_merge_advance(RandomAccessIterator1& begin1, RandomAccessIterator1 end1, RandomAccessIterator1& begin2, RandomAccessIterator1 end2, RandomAccessIterator3 target, typename std::iterator_traits<RandomAccessIterator1>::difference_type max_length, Comparator comp)
- {
- typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
- value_type;
- typedef typename std::iterator_traits<RandomAccessIterator1>::difference_type
- difference_type1 /* == difference_type2 */;
- typedef typename std::iterator_traits<RandomAccessIterator3>::difference_type
- difference_type3;
-
- std::pair<RandomAccessIterator1, RandomAccessIterator1> seqs[2] = { std::make_pair(begin1, end1), std::make_pair(begin2, end2) };
- RandomAccessIterator3 target_end = parallel_multiway_merge(seqs, seqs + 2, target, comp, max_length, true, false);
+ template<typename RandomAccessIterator1, typename RandomAccessIterator3,
+ typename Comparator>
+ inline RandomAccessIterator3
+ parallel_merge_advance(RandomAccessIterator1& begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator1& begin2,
+ RandomAccessIterator1 end2,
+ RandomAccessIterator3 target, typename
+ std::iterator_traits<RandomAccessIterator1>::
+ difference_type max_length, Comparator comp)
+ {
+ typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
+ value_type;
+ typedef typename std::iterator_traits<RandomAccessIterator1>::
+ difference_type difference_type1 /* == difference_type2 */;
+ typedef typename std::iterator_traits<RandomAccessIterator3>::
+ difference_type difference_type3;
+
+ std::pair<RandomAccessIterator1, RandomAccessIterator1>
+ seqs[2] = { std::make_pair(begin1, end1),
+ std::make_pair(begin2, end2) };
+ RandomAccessIterator3
+ target_end = parallel_multiway_merge(seqs, seqs + 2, target,
+ comp, max_length, true, false);
- return target_end;
- }
+ return target_end;
+ }
} //namespace __gnu_parallel
#endif
Index: include/parallel/algobase.h
===================================================================
--- include/parallel/algobase.h (revision 131429)
+++ include/parallel/algobase.h (working copy)
@@ -1,6 +1,6 @@
// -*- C++ -*-
-// Copyright (C) 2007 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
@@ -57,215 +57,230 @@
// Sequential fallback
template<typename InputIterator1, typename InputIterator2>
- inline pair<InputIterator1, InputIterator2>
- mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2); }
+ inline pair<InputIterator1, InputIterator2>
+ mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2); }
// Sequential fallback
- template<typename InputIterator1, typename InputIterator2, typename Predicate>
- inline pair<InputIterator1, InputIterator2>
- mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- Predicate pred, __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); }
+ template<typename InputIterator1, typename InputIterator2,
+ typename Predicate>
+ inline pair<InputIterator1, InputIterator2>
+ mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
+ Predicate pred, __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); }
// Sequential fallback for input iterator case
- template<typename InputIterator1, typename InputIterator2, typename Predicate, typename IteratorTag1, typename IteratorTag2>
- inline pair<InputIterator1, InputIterator2>
- mismatch_switch(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, Predicate pred, IteratorTag1,
- IteratorTag2)
- { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); }
+ template<typename InputIterator1, typename InputIterator2,
+ typename Predicate, typename IteratorTag1, typename IteratorTag2>
+ inline pair<InputIterator1, InputIterator2>
+ mismatch_switch(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, Predicate pred, IteratorTag1,
+ IteratorTag2)
+ { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); }
// Parallel mismatch for random access iterators
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Predicate>
- pair<RandomAccessIterator1, RandomAccessIterator2>
- mismatch_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
- RandomAccessIterator2 begin2, Predicate pred,
- random_access_iterator_tag, random_access_iterator_tag)
- {
- 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));
- }
- else
- return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred);
- }
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Predicate>
+ pair<RandomAccessIterator1, RandomAccessIterator2>
+ mismatch_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
+ RandomAccessIterator2 begin2, Predicate pred,
+ random_access_iterator_tag, random_access_iterator_tag)
+ {
+ 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));
+ }
+ else
+ return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred);
+ }
// Public interface
template<typename InputIterator1, typename InputIterator2>
- inline pair<InputIterator1, InputIterator2>
- mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2)
- {
- typedef std::iterator_traits<InputIterator1> iterator1_traits;
- typedef std::iterator_traits<InputIterator2> iterator2_traits;
- typedef typename iterator1_traits::value_type value1_type;
- typedef typename iterator2_traits::value_type value2_type;
- typedef typename iterator1_traits::iterator_category iterator1_category;
- typedef typename iterator2_traits::iterator_category iterator2_category;
-
- typedef __gnu_parallel::equal_to<value1_type, value2_type> equal_to_type;
-
- return mismatch_switch(begin1, end1, begin2, equal_to_type(),
- iterator1_category(), iterator2_category());
- }
+ inline pair<InputIterator1, InputIterator2>
+ mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2)
+ {
+ typedef std::iterator_traits<InputIterator1> iterator1_traits;
+ typedef std::iterator_traits<InputIterator2> iterator2_traits;
+ typedef typename iterator1_traits::value_type value1_type;
+ typedef typename iterator2_traits::value_type value2_type;
+ typedef typename iterator1_traits::iterator_category iterator1_category;
+ typedef typename iterator2_traits::iterator_category iterator2_category;
+
+ typedef __gnu_parallel::equal_to<value1_type, value2_type> equal_to_type;
+
+ return mismatch_switch(begin1, end1, begin2, equal_to_type(),
+ iterator1_category(), iterator2_category());
+ }
// Public interface
- template<typename InputIterator1, typename InputIterator2, typename Predicate>
- inline pair<InputIterator1, InputIterator2>
- mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- Predicate pred)
- {
- typedef std::iterator_traits<InputIterator1> iterator1_traits;
- typedef std::iterator_traits<InputIterator2> iterator2_traits;
- typedef typename iterator1_traits::iterator_category iterator1_category;
- typedef typename iterator2_traits::iterator_category iterator2_category;
-
- return mismatch_switch(begin1, end1, begin2, pred, iterator1_category(),
- iterator2_category());
- }
+ template<typename InputIterator1, typename InputIterator2,
+ typename Predicate>
+ inline pair<InputIterator1, InputIterator2>
+ mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
+ Predicate pred)
+ {
+ typedef std::iterator_traits<InputIterator1> iterator1_traits;
+ typedef std::iterator_traits<InputIterator2> iterator2_traits;
+ typedef typename iterator1_traits::iterator_category iterator1_category;
+ typedef typename iterator2_traits::iterator_category iterator2_category;
+
+ return mismatch_switch(begin1, end1, begin2, pred, iterator1_category(),
+ iterator2_category());
+ }
// Sequential fallback
template<typename InputIterator1, typename InputIterator2>
- inline bool
- equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::equal(begin1, end1, begin2); }
+ inline bool
+ equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::equal(begin1, end1, begin2); }
// Sequential fallback
- template<typename InputIterator1, typename InputIterator2, typename Predicate>
- inline bool
- equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- Predicate pred, __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::equal(begin1, end1, begin2, pred); }
+ template<typename InputIterator1, typename InputIterator2,
+ typename Predicate>
+ inline bool
+ equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
+ Predicate pred, __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::equal(begin1, end1, begin2, pred); }
// Public interface
template<typename InputIterator1, typename InputIterator2>
- inline bool
- equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2)
- { return mismatch(begin1, end1, begin2).first == end1; }
+ inline bool
+ equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2)
+ { return mismatch(begin1, end1, begin2).first == end1; }
// Public interface
- template<typename InputIterator1, typename InputIterator2, typename Predicate>
- inline bool
- equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- Predicate pred)
- { return mismatch(begin1, end1, begin2, pred).first == end1; }
+ template<typename InputIterator1, typename InputIterator2,
+ typename Predicate>
+ inline bool
+ equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
+ Predicate pred)
+ { return mismatch(begin1, end1, begin2, pred).first == end1; }
// Sequential fallback
template<typename InputIterator1, typename InputIterator2>
- inline bool
- lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- __gnu_parallel::sequential_tag)
- {
- return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, begin2, end2);
- }
+ inline bool
+ lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
+ begin2, end2); }
// Sequential fallback
- template<typename InputIterator1, typename InputIterator2, typename Predicate>
- inline bool
- lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- Predicate pred, __gnu_parallel::sequential_tag)
- {
- return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
- begin2, end2, pred);
- }
+ template<typename InputIterator1, typename InputIterator2,
+ typename Predicate>
+ inline bool
+ lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ Predicate pred, __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
+ begin2, end2, pred); }
// Sequential fallback for input iterator case
- template<typename InputIterator1, typename InputIterator2, typename Predicate, typename IteratorTag1, typename IteratorTag2>
- inline bool
- lexicographical_compare_switch(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- Predicate pred, IteratorTag1, IteratorTag2)
- {
- return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
- begin2, end2, pred);
- }
+ template<typename InputIterator1, typename InputIterator2,
+ typename Predicate, typename IteratorTag1, typename IteratorTag2>
+ inline bool
+ lexicographical_compare_switch(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ Predicate pred, IteratorTag1, IteratorTag2)
+ { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
+ begin2, end2, pred); }
// Parallel lexicographical_compare for random access iterators
// Limitation: Both valuetypes must be the same
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Predicate>
- bool
- lexicographical_compare_switch(RandomAccessIterator1 begin1,
- RandomAccessIterator1 end1,
- RandomAccessIterator2 begin2,
- RandomAccessIterator2 end2, Predicate pred,
- random_access_iterator_tag,
- random_access_iterator_tag)
- {
- if (_GLIBCXX_PARALLEL_CONDITION(true))
- {
- typedef iterator_traits<RandomAccessIterator1> traits1_type;
- typedef typename traits1_type::value_type value1_type;
-
- typedef iterator_traits<RandomAccessIterator2> traits2_type;
- typedef typename traits2_type::value_type value2_type;
-
- typedef __gnu_parallel::equal_from_less<Predicate, value1_type, value2_type> equal_type;
-
- // Longer sequence in first place.
- if ((end1 - begin1) < (end2 - begin2))
- {
- typedef pair<RandomAccessIterator1, RandomAccessIterator2> pair_type;
- pair_type mm = mismatch_switch(begin1, end1, begin2,
- equal_type(pred),
- random_access_iterator_tag(),
- random_access_iterator_tag());
-
- return (mm.first == end1) || bool(pred(*mm.first, *mm.second));
- }
- else
- {
- typedef pair<RandomAccessIterator2, RandomAccessIterator1> pair_type;
- pair_type mm = mismatch_switch(begin2, end2, begin1,
- equal_type(pred),
- random_access_iterator_tag(),
- random_access_iterator_tag());
-
- return (mm.first != end2) && bool(pred(*mm.second, *mm.first));
- }
- }
- else
- return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, begin2, end2, pred);
- }
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Predicate>
+ bool
+ lexicographical_compare_switch(RandomAccessIterator1 begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator2 begin2,
+ RandomAccessIterator2 end2, Predicate pred,
+ random_access_iterator_tag,
+ random_access_iterator_tag)
+ {
+ if (_GLIBCXX_PARALLEL_CONDITION(true))
+ {
+ typedef iterator_traits<RandomAccessIterator1> traits1_type;
+ typedef typename traits1_type::value_type value1_type;
+
+ typedef iterator_traits<RandomAccessIterator2> traits2_type;
+ typedef typename traits2_type::value_type value2_type;
+
+ typedef __gnu_parallel::equal_from_less<Predicate, value1_type,
+ value2_type> equal_type;
+
+ // Longer sequence in first place.
+ if ((end1 - begin1) < (end2 - begin2))
+ {
+ typedef pair<RandomAccessIterator1, RandomAccessIterator2>
+ pair_type;
+ pair_type mm = mismatch_switch(begin1, end1, begin2,
+ equal_type(pred),
+ random_access_iterator_tag(),
+ random_access_iterator_tag());
+
+ return (mm.first == end1) || bool(pred(*mm.first, *mm.second));
+ }
+ else
+ {
+ typedef pair<RandomAccessIterator2, RandomAccessIterator1>
+ pair_type;
+ pair_type mm = mismatch_switch(begin2, end2, begin1,
+ equal_type(pred),
+ random_access_iterator_tag(),
+ random_access_iterator_tag());
+
+ return (mm.first != end2) && bool(pred(*mm.second, *mm.first));
+ }
+ }
+ else
+ return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
+ begin2, end2, pred);
+ }
// Public interface
template<typename InputIterator1, typename InputIterator2>
- inline bool
- lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2)
- {
- typedef iterator_traits<InputIterator1> traits1_type;
- typedef typename traits1_type::value_type value1_type;
- typedef typename traits1_type::iterator_category iterator1_category;
-
- typedef iterator_traits<InputIterator2> traits2_type;
- typedef typename traits2_type::value_type value2_type;
- typedef typename traits2_type::iterator_category iterator2_category;
- typedef __gnu_parallel::less<value1_type, value2_type> less_type;
-
- return lexicographical_compare_switch(begin1, end1, begin2, end2,
- less_type(), iterator1_category(),
- iterator2_category());
- }
+ inline bool
+ lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2)
+ {
+ typedef iterator_traits<InputIterator1> traits1_type;
+ typedef typename traits1_type::value_type value1_type;
+ typedef typename traits1_type::iterator_category iterator1_category;
+
+ typedef iterator_traits<InputIterator2> traits2_type;
+ typedef typename traits2_type::value_type value2_type;
+ typedef typename traits2_type::iterator_category iterator2_category;
+ typedef __gnu_parallel::less<value1_type, value2_type> less_type;
+
+ return lexicographical_compare_switch(begin1, end1, begin2, end2,
+ less_type(), iterator1_category(),
+ iterator2_category());
+ }
// Public interface
- template<typename InputIterator1, typename InputIterator2, typename Predicate>
- inline bool
- lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, Predicate pred)
- {
- typedef iterator_traits<InputIterator1> traits1_type;
- typedef typename traits1_type::iterator_category iterator1_category;
-
- typedef iterator_traits<InputIterator2> traits2_type;
- typedef typename traits2_type::iterator_category iterator2_category;
-
- return lexicographical_compare_switch(begin1, end1, begin2, end2, pred,
- iterator1_category(),
- iterator2_category());
- }
+ template<typename InputIterator1, typename InputIterator2,
+ typename Predicate>
+ inline bool
+ lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ Predicate pred)
+ {
+ typedef iterator_traits<InputIterator1> traits1_type;
+ typedef typename traits1_type::iterator_category iterator1_category;
+
+ typedef iterator_traits<InputIterator2> traits2_type;
+ typedef typename traits2_type::iterator_category iterator2_category;
+
+ return lexicographical_compare_switch(begin1, end1, begin2, end2, pred,
+ iterator1_category(),
+ iterator2_category());
+ }
} // end namespace
} // end namespace
Index: include/parallel/find.h
===================================================================
--- include/parallel/find.h (revision 131429)
+++ include/parallel/find.h (working copy)
@@ -1,6 +1,6 @@
// -*- C++ -*-
-// Copyright (C) 2007 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
@@ -58,11 +58,10 @@
* @param selector Functionality (e. g. std::find_if (), std::equal(),...)
* @return Place of finding in both sequences.
*/
-template<
- typename RandomAccessIterator1,
- typename RandomAccessIterator2,
- typename Pred,
- typename Selector>
+template<typename RandomAccessIterator1,
+ typename RandomAccessIterator2,
+ typename Pred,
+ typename Selector>
std::pair<RandomAccessIterator1, RandomAccessIterator2>
find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
RandomAccessIterator2 begin2, Pred pred, Selector selector)
@@ -96,11 +95,10 @@
* @param selector Functionality (e. g. std::find_if (), std::equal(),...)
* @return Place of finding in both sequences.
*/
-template<
- typename RandomAccessIterator1,
- typename RandomAccessIterator2,
- typename Pred,
- typename Selector>
+template<typename RandomAccessIterator1,
+ typename RandomAccessIterator2,
+ typename Pred,
+ typename Selector>
std::pair<RandomAccessIterator1, RandomAccessIterator2>
find_template(RandomAccessIterator1 begin1,
RandomAccessIterator1 end1,
@@ -190,11 +188,10 @@
* for CSB, the blocks are allocated in a predetermined manner,
* namely spacial round-robin.
*/
-template<
- typename RandomAccessIterator1,
- typename RandomAccessIterator2,
- typename Pred,
- typename Selector>
+template<typename RandomAccessIterator1,
+ typename RandomAccessIterator2,
+ typename Pred,
+ typename Selector>
std::pair<RandomAccessIterator1, RandomAccessIterator2>
find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
RandomAccessIterator2 begin2, Pred pred, Selector selector,
@@ -311,11 +308,10 @@
* blocks are allocated in a predetermined manner, namely spacial
* round-robin.
*/
-template<
- typename RandomAccessIterator1,
- typename RandomAccessIterator2,
- typename Pred,
- typename Selector>
+template<typename RandomAccessIterator1,
+ typename RandomAccessIterator2,
+ typename Pred,
+ typename Selector>
std::pair<RandomAccessIterator1, RandomAccessIterator2>
find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
RandomAccessIterator2 begin2, Pred pred, Selector selector,
Index: include/parallel/algo.h
===================================================================
--- include/parallel/algo.h (revision 131429)
+++ include/parallel/algo.h (working copy)
@@ -1,6 +1,6 @@
// -*- C++ -*-
-// Copyright (C) 2007 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
@@ -70,1600 +70,1908 @@
{
// Sequential fallback
template<typename InputIterator, typename Function>
- inline Function
- for_each(InputIterator begin, InputIterator end, Function f,
- __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::for_each(begin, end, f); }
+ inline Function
+ for_each(InputIterator begin, InputIterator end, Function f,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::for_each(begin, end, f); }
// Sequential fallback for input iterator case
template<typename InputIterator, typename Function, typename IteratorTag>
- Function
- for_each_switch(InputIterator begin, InputIterator end, Function f,
- IteratorTag)
- { return for_each(begin, end, f, __gnu_parallel::sequential_tag()); }
+ inline Function
+ for_each_switch(InputIterator begin, InputIterator end, Function f,
+ IteratorTag)
+ { return for_each(begin, end, f, __gnu_parallel::sequential_tag()); }
// Parallel algorithm for random access iterators
template<typename RandomAccessIterator, typename Function>
- Function
- for_each_switch(RandomAccessIterator begin, RandomAccessIterator end,
- 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)))
- {
- bool dummy;
- __gnu_parallel::for_each_selector<RandomAccessIterator> functionality;
- return __gnu_parallel::for_each_template_random_access(begin, end, f, functionality, __gnu_parallel::dummy_reduct(), true, dummy, -1, parallelism_tag);
- }
- else
- return for_each(begin, end, f, __gnu_parallel::sequential_tag());
- }
+ Function
+ for_each_switch(RandomAccessIterator begin, RandomAccessIterator end,
+ 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)))
+ {
+ bool dummy;
+ __gnu_parallel::for_each_selector<RandomAccessIterator>
+ functionality;
+
+ return __gnu_parallel::
+ for_each_template_random_access(begin, end, f, functionality,
+ __gnu_parallel::dummy_reduct(),
+ true, dummy, -1, parallelism_tag);
+ }
+ else
+ return for_each(begin, end, f, __gnu_parallel::sequential_tag());
+ }
// Public interface
template<typename Iterator, typename Function>
- inline Function
- for_each(Iterator begin, Iterator end, Function f,
- __gnu_parallel::parallelism parallelism_tag)
- {
- typedef std::iterator_traits<Iterator> iterator_traits;
- typedef typename iterator_traits::iterator_category iterator_category;
- return for_each_switch(begin, end, f, iterator_category(),
- parallelism_tag);
- }
+ inline Function
+ for_each(Iterator begin, Iterator end, Function f,
+ __gnu_parallel::parallelism parallelism_tag)
+ {
+ typedef std::iterator_traits<Iterator> iterator_traits;
+ typedef typename iterator_traits::iterator_category iterator_category;
+ return for_each_switch(begin, end, f, iterator_category(),
+ parallelism_tag);
+ }
template<typename Iterator, typename Function>
- inline Function
- for_each(Iterator begin, Iterator end, Function f)
- {
- typedef std::iterator_traits<Iterator> iterator_traits;
- typedef typename iterator_traits::iterator_category iterator_category;
- return for_each_switch(begin, end, f, iterator_category());
- }
+ inline Function
+ for_each(Iterator begin, Iterator end, Function f)
+ {
+ typedef std::iterator_traits<Iterator> iterator_traits;
+ typedef typename iterator_traits::iterator_category iterator_category;
+ return for_each_switch(begin, end, f, iterator_category());
+ }
// Sequential fallback
template<typename InputIterator, typename T>
- inline InputIterator
- find(InputIterator begin, InputIterator end, const T& val,
- __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::find(begin, end, val); }
+ inline InputIterator
+ find(InputIterator begin, InputIterator end, const T& val,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::find(begin, end, val); }
// Sequential fallback for input iterator case
template<typename InputIterator, typename T, typename IteratorTag>
- inline InputIterator
- find_switch(InputIterator begin, InputIterator end, const T& val, IteratorTag)
- { return _GLIBCXX_STD_P::find(begin, end, val); }
+ inline InputIterator
+ find_switch(InputIterator begin, InputIterator end, const T& val,
+ IteratorTag)
+ { return _GLIBCXX_STD_P::find(begin, end, val); }
// Parallel find for random access iterators
template<typename RandomAccessIterator, typename T>
- RandomAccessIterator
- find_switch(RandomAccessIterator begin, RandomAccessIterator end, const T& val, random_access_iterator_tag)
- {
- typedef iterator_traits<RandomAccessIterator> traits_type;
- typedef typename traits_type::value_type value_type;
-
- if (_GLIBCXX_PARALLEL_CONDITION(true))
- {
- binder2nd<__gnu_parallel::equal_to<value_type, T> > comp(__gnu_parallel::equal_to<value_type, T>(), val);
- return __gnu_parallel::find_template(begin, end, begin, comp, __gnu_parallel::find_if_selector()).first;
- }
- else
- return _GLIBCXX_STD_P::find(begin, end, val);
- }
+ RandomAccessIterator
+ find_switch(RandomAccessIterator begin, RandomAccessIterator end,
+ const T& val, random_access_iterator_tag)
+ {
+ typedef iterator_traits<RandomAccessIterator> traits_type;
+ typedef typename traits_type::value_type value_type;
+
+ if (_GLIBCXX_PARALLEL_CONDITION(true))
+ {
+ binder2nd<__gnu_parallel::equal_to<value_type, T> >
+ comp(__gnu_parallel::equal_to<value_type, T>(), val);
+ return __gnu_parallel::find_template(begin, end, begin, comp,
+ __gnu_parallel::
+ find_if_selector()).first;
+ }
+ else
+ return _GLIBCXX_STD_P::find(begin, end, val);
+ }
// Public interface
template<typename InputIterator, typename T>
- inline InputIterator
- find(InputIterator begin, InputIterator end, const T& val)
- {
- typedef std::iterator_traits<InputIterator> iterator_traits;
- typedef typename iterator_traits::iterator_category iterator_category;
- return find_switch(begin, end, val, iterator_category());
- }
+ inline InputIterator
+ find(InputIterator begin, InputIterator end, const T& val)
+ {
+ typedef std::iterator_traits<InputIterator> iterator_traits;
+ typedef typename iterator_traits::iterator_category iterator_category;
+ return find_switch(begin, end, val, iterator_category());
+ }
// Sequential fallback
template<typename InputIterator, typename Predicate>
- inline InputIterator
- find_if(InputIterator begin, InputIterator end, Predicate pred,
- __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::find_if(begin, end, pred); }
+ inline InputIterator
+ find_if(InputIterator begin, InputIterator end, Predicate pred,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::find_if(begin, end, pred); }
// Sequential fallback for input iterator case
template<typename InputIterator, typename Predicate, typename IteratorTag>
- inline InputIterator
- find_if_switch(InputIterator begin, InputIterator end, Predicate pred,
- IteratorTag)
- { return _GLIBCXX_STD_P::find_if(begin, end, pred); }
+ inline InputIterator
+ find_if_switch(InputIterator begin, InputIterator end, Predicate pred,
+ IteratorTag)
+ { return _GLIBCXX_STD_P::find_if(begin, end, pred); }
// Parallel find_if for random access iterators
template<typename RandomAccessIterator, typename Predicate>
- RandomAccessIterator
- find_if_switch(RandomAccessIterator begin, RandomAccessIterator end,
- Predicate pred, random_access_iterator_tag)
- {
- if (_GLIBCXX_PARALLEL_CONDITION(true))
- return __gnu_parallel::find_template(begin, end, begin, pred,
- __gnu_parallel::find_if_selector()).first;
- else
- return _GLIBCXX_STD_P::find_if(begin, end, pred);
- }
+ RandomAccessIterator
+ find_if_switch(RandomAccessIterator begin, RandomAccessIterator end,
+ 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;
+ else
+ return _GLIBCXX_STD_P::find_if(begin, end, pred);
+ }
// Public interface
template<typename InputIterator, typename Predicate>
- inline InputIterator
- find_if (InputIterator begin, InputIterator end, Predicate pred)
- {
- typedef std::iterator_traits<InputIterator> iterator_traits;
- typedef typename iterator_traits::iterator_category iterator_category;
- return find_if_switch(begin, end, pred, iterator_category());
- }
+ inline InputIterator
+ find_if(InputIterator begin, InputIterator end, Predicate pred)
+ {
+ typedef std::iterator_traits<InputIterator> iterator_traits;
+ typedef typename iterator_traits::iterator_category iterator_category;
+ return find_if_switch(begin, end, pred, iterator_category());
+ }
// Sequential fallback
template<typename InputIterator, typename ForwardIterator>
- inline InputIterator
- find_first_of(InputIterator begin1, InputIterator end1,
- ForwardIterator begin2, ForwardIterator end2,
- __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::find_first_of(begin1, end1, begin2, end2); }
+ inline InputIterator
+ find_first_of(InputIterator begin1, InputIterator end1,
+ ForwardIterator begin2, ForwardIterator end2,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::find_first_of(begin1, end1, begin2, end2); }
// Sequential fallback
template<typename InputIterator, typename ForwardIterator,
typename BinaryPredicate>
- inline InputIterator
- find_first_of(InputIterator begin1, InputIterator end1,
- ForwardIterator begin2, ForwardIterator end2,
- BinaryPredicate comp, __gnu_parallel::sequential_tag)
+ inline InputIterator
+ find_first_of(InputIterator begin1, InputIterator end1,
+ ForwardIterator begin2, ForwardIterator end2,
+ BinaryPredicate comp, __gnu_parallel::sequential_tag)
{ return _GLIBCXX_STD_P::find_first_of(begin1, end1, begin2, end2, comp); }
// Sequential fallback for input iterator type
- template<typename InputIterator, typename ForwardIterator, typename IteratorTag1, typename IteratorTag2>
- inline InputIterator
- find_first_of_switch(InputIterator begin1, InputIterator end1,
- ForwardIterator begin2, ForwardIterator end2,
- IteratorTag1, IteratorTag2)
- {
- return find_first_of(begin1, end1, begin2, end2,
- __gnu_parallel::sequential_tag());
- }
+ template<typename InputIterator, typename ForwardIterator,
+ typename IteratorTag1, typename IteratorTag2>
+ inline InputIterator
+ find_first_of_switch(InputIterator begin1, InputIterator end1,
+ ForwardIterator begin2, ForwardIterator end2,
+ IteratorTag1, IteratorTag2)
+ { return find_first_of(begin1, end1, begin2, end2,
+ __gnu_parallel::sequential_tag()); }
// Parallel algorithm for random access iterators
- template<typename RandomAccessIterator, typename ForwardIterator, typename BinaryPredicate, typename IteratorTag>
- inline RandomAccessIterator
- find_first_of_switch(RandomAccessIterator begin1, RandomAccessIterator end1,
- ForwardIterator begin2, ForwardIterator end2,
- BinaryPredicate comp, random_access_iterator_tag,
- IteratorTag)
- {
- return __gnu_parallel::find_template(begin1, end1, begin1, comp, __gnu_parallel::find_first_of_selector<ForwardIterator>(begin2, end2)).first;
- }
+ template<typename RandomAccessIterator, typename ForwardIterator,
+ typename BinaryPredicate, typename IteratorTag>
+ inline RandomAccessIterator
+ find_first_of_switch(RandomAccessIterator begin1,
+ RandomAccessIterator end1,
+ ForwardIterator begin2, ForwardIterator end2,
+ BinaryPredicate comp, random_access_iterator_tag,
+ IteratorTag)
+ {
+ return __gnu_parallel::
+ find_template(begin1, end1, begin1, comp,
+ __gnu_parallel::find_first_of_selector
+ <ForwardIterator>(begin2, end2)).first;
+ }
// Sequential fallback for input iterator type
- template<typename InputIterator, typename ForwardIterator, typename BinaryPredicate, typename IteratorTag1, typename IteratorTag2>
- inline
- InputIterator
- find_first_of_switch(InputIterator begin1, InputIterator end1,
- ForwardIterator begin2, ForwardIterator end2,
- BinaryPredicate comp, IteratorTag1, IteratorTag2)
- {
- return find_first_of(begin1, end1, begin2, end2, comp,
- __gnu_parallel::sequential_tag());
- }
+ template<typename InputIterator, typename ForwardIterator,
+ typename BinaryPredicate, typename IteratorTag1,
+ typename IteratorTag2>
+ inline InputIterator
+ find_first_of_switch(InputIterator begin1, InputIterator end1,
+ ForwardIterator begin2, ForwardIterator end2,
+ BinaryPredicate comp, IteratorTag1, IteratorTag2)
+ { return find_first_of(begin1, end1, begin2, end2, comp,
+ __gnu_parallel::sequential_tag()); }
// Public interface
- template<typename InputIterator, typename ForwardIterator, typename BinaryPredicate>
- inline InputIterator
- find_first_of(InputIterator begin1, InputIterator end1,
- ForwardIterator begin2, ForwardIterator end2,
- BinaryPredicate comp)
- {
- typedef std::iterator_traits<InputIterator> iteratori_traits;
- typedef std::iterator_traits<ForwardIterator> iteratorf_traits;
- typedef typename iteratori_traits::iterator_category iteratori_category;
- typedef typename iteratorf_traits::iterator_category iteratorf_category;
-
- return find_first_of_switch(begin1, end1, begin2, end2, comp,
- iteratori_category(), iteratorf_category());
- }
+ template<typename InputIterator, typename ForwardIterator,
+ typename BinaryPredicate>
+ inline InputIterator
+ find_first_of(InputIterator begin1, InputIterator end1,
+ ForwardIterator begin2, ForwardIterator end2,
+ BinaryPredicate comp)
+ {
+ typedef std::iterator_traits<InputIterator> iteratori_traits;
+ typedef std::iterator_traits<ForwardIterator> iteratorf_traits;
+ typedef typename iteratori_traits::iterator_category iteratori_category;
+ typedef typename iteratorf_traits::iterator_category iteratorf_category;
+
+ return find_first_of_switch(begin1, end1, begin2, end2, comp,
+ iteratori_category(), iteratorf_category());
+ }
// Public interface, insert default comparator
template<typename InputIterator, typename ForwardIterator>
- InputIterator
- find_first_of(InputIterator begin1, InputIterator end1,
- ForwardIterator begin2, ForwardIterator end2)
- {
- typedef std::iterator_traits<InputIterator> iteratori_traits;
- typedef std::iterator_traits<ForwardIterator> iteratorf_traits;
- typedef typename iteratori_traits::value_type valuei_type;
- typedef typename iteratorf_traits::value_type valuef_type;
-
- return find_first_of(begin1, end1, begin2, end2,
- __gnu_parallel::equal_to<valuei_type, valuef_type>());
- }
+ inline InputIterator
+ find_first_of(InputIterator begin1, InputIterator end1,
+ ForwardIterator begin2, ForwardIterator end2)
+ {
+ typedef std::iterator_traits<InputIterator> iteratori_traits;
+ typedef std::iterator_traits<ForwardIterator> iteratorf_traits;
+ typedef typename iteratori_traits::value_type valuei_type;
+ typedef typename iteratorf_traits::value_type valuef_type;
+
+ return find_first_of(begin1, end1, begin2, end2, __gnu_parallel::
+ equal_to<valuei_type, valuef_type>());
+ }
// Sequential fallback
template<typename InputIterator, typename OutputIterator>
- inline OutputIterator
- unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
- __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::unique_copy(begin1, end1, out); }
+ inline OutputIterator
+ unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::unique_copy(begin1, end1, out); }
// Sequential fallback
- template<typename InputIterator, typename OutputIterator, typename Predicate>
- inline OutputIterator
- unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
- Predicate pred, __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::unique_copy(begin1, end1, out, pred); }
+ template<typename InputIterator, typename OutputIterator,
+ typename Predicate>
+ inline OutputIterator
+ unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
+ Predicate pred, __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::unique_copy(begin1, end1, out, pred); }
// Sequential fallback for input iterator case
- template<typename InputIterator, typename OutputIterator, typename Predicate, typename IteratorTag1, typename IteratorTag2>
- inline OutputIterator
- unique_copy_switch(InputIterator begin, InputIterator last,
- OutputIterator out, Predicate pred,
- IteratorTag1, IteratorTag2)
- { return _GLIBCXX_STD_P::unique_copy(begin, last, out, pred); }
+ template<typename InputIterator, typename OutputIterator,
+ typename Predicate, typename IteratorTag1, typename IteratorTag2>
+ inline OutputIterator
+ unique_copy_switch(InputIterator begin, InputIterator last,
+ OutputIterator out, Predicate pred,
+ IteratorTag1, IteratorTag2)
+ { return _GLIBCXX_STD_P::unique_copy(begin, last, out, pred); }
// Parallel unique_copy for random access iterators
- template<typename RandomAccessIterator, typename RandomAccessOutputIterator, typename Predicate>
- RandomAccessOutputIterator
- unique_copy_switch(RandomAccessIterator begin, RandomAccessIterator last,
- RandomAccessOutputIterator out, Predicate pred,
- random_access_iterator_tag, random_access_iterator_tag)
- {
- 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);
- }
+ template<typename RandomAccessIterator, typename RandomAccessOutputIterator,
+ typename Predicate>
+ RandomAccessOutputIterator
+ unique_copy_switch(RandomAccessIterator begin, RandomAccessIterator last,
+ RandomAccessOutputIterator out, Predicate pred,
+ random_access_iterator_tag, random_access_iterator_tag)
+ {
+ if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::
+ sequence_index_t>(last - begin)
+ > __gnu_parallel::Settings::
+ unique_copy_minimal_n))
+ return __gnu_parallel::parallel_unique_copy(begin, last, out, pred);
+ else
+ return _GLIBCXX_STD_P::unique_copy(begin, last, out, pred);
+ }
// Public interface
template<typename InputIterator, typename OutputIterator>
- inline OutputIterator
- unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out)
- {
- typedef std::iterator_traits<InputIterator> iteratori_traits;
- typedef std::iterator_traits<OutputIterator> iteratoro_traits;
- typedef typename iteratori_traits::iterator_category iteratori_category;
- typedef typename iteratori_traits::value_type value_type;
- typedef typename iteratoro_traits::iterator_category iteratoro_category;
-
- return unique_copy_switch(begin1, end1, out, equal_to<value_type>(),
- iteratori_category(), iteratoro_category());
- }
+ inline OutputIterator
+ unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out)
+ {
+ typedef std::iterator_traits<InputIterator> iteratori_traits;
+ typedef std::iterator_traits<OutputIterator> iteratoro_traits;
+ typedef typename iteratori_traits::iterator_category iteratori_category;
+ typedef typename iteratori_traits::value_type value_type;
+ typedef typename iteratoro_traits::iterator_category iteratoro_category;
+
+ return unique_copy_switch(begin1, end1, out, equal_to<value_type>(),
+ iteratori_category(), iteratoro_category());
+ }
// Public interface
template<typename InputIterator, typename OutputIterator, typename Predicate>
- inline OutputIterator
- unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
- Predicate pred)
- {
- typedef std::iterator_traits<InputIterator> iteratori_traits;
- typedef std::iterator_traits<OutputIterator> iteratoro_traits;
- typedef typename iteratori_traits::iterator_category iteratori_category;
- typedef typename iteratoro_traits::iterator_category iteratoro_category;
-
- return unique_copy_switch(begin1, end1, out, pred, iteratori_category(),
- iteratoro_category());
- }
+ inline OutputIterator
+ unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
+ Predicate pred)
+ {
+ typedef std::iterator_traits<InputIterator> iteratori_traits;
+ typedef std::iterator_traits<OutputIterator> iteratoro_traits;
+ typedef typename iteratori_traits::iterator_category iteratori_category;
+ typedef typename iteratoro_traits::iterator_category iteratoro_category;
+
+ return unique_copy_switch(begin1, end1, out, pred, iteratori_category(),
+ iteratoro_category());
+ }
// Sequential fallback
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
- inline OutputIterator
- set_union(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator out, __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::set_union(begin1, end1, begin2, end2, out); }
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator>
+ inline OutputIterator
+ set_union(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator out, __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::set_union(begin1, end1, begin2, end2, out); }
// Sequential fallback
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Predicate>
- inline OutputIterator
- set_union(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator out, Predicate pred, __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::set_union(begin1, end1, begin2, end2, out, pred); }
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename Predicate>
+ inline OutputIterator
+ set_union(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator out, Predicate pred,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::set_union(begin1, end1,
+ begin2, end2, out, pred); }
// Sequential fallback for input iterator case
- template<typename InputIterator1, typename InputIterator2, typename Predicate,
- typename OutputIterator, typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
- inline OutputIterator
- set_union_switch(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator result, Predicate pred, IteratorTag1,
- IteratorTag2, IteratorTag3)
- {
- return _GLIBCXX_STD_P::set_union(begin1, end1, begin2, end2, result, pred);
- }
+ template<typename InputIterator1, typename InputIterator2,
+ typename Predicate, typename OutputIterator,
+ typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
+ inline OutputIterator
+ set_union_switch(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator result, Predicate pred, IteratorTag1,
+ IteratorTag2, IteratorTag3)
+ { return _GLIBCXX_STD_P::set_union(begin1, end1,
+ begin2, end2, result, pred); }
// Parallel set_union for random access iterators
template<typename RandomAccessIterator1, typename RandomAccessIterator2,
typename OutputRandomAccessIterator, typename Predicate>
- 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)
- {
- 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);
- }
+ 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)
+ {
+ 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);
+ }
// Public interface
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
- inline OutputIterator
- set_union(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- InputIterator2 end2, OutputIterator out)
- {
- typedef std::iterator_traits<InputIterator1> iteratori1_traits;
- typedef std::iterator_traits<InputIterator2> iteratori2_traits;
- typedef std::iterator_traits<OutputIterator> iteratoro_traits;
- typedef typename iteratori1_traits::iterator_category iteratori1_category;
- typedef typename iteratori2_traits::iterator_category iteratori2_category;
- typedef typename iteratoro_traits::iterator_category iteratoro_category;
- typedef typename iteratori1_traits::value_type value1_type;
- typedef typename iteratori2_traits::value_type value2_type;
-
- return set_union_switch(begin1, end1, begin2, end2, out,
- __gnu_parallel::less<value1_type, value2_type>(),
- iteratori1_category(), iteratori2_category(),
- iteratoro_category());
- }
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator>
+ inline OutputIterator
+ set_union(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2, OutputIterator out)
+ {
+ typedef std::iterator_traits<InputIterator1> iteratori1_traits;
+ typedef std::iterator_traits<InputIterator2> iteratori2_traits;
+ typedef std::iterator_traits<OutputIterator> iteratoro_traits;
+ typedef typename iteratori1_traits::iterator_category
+ iteratori1_category;
+ typedef typename iteratori2_traits::iterator_category
+ iteratori2_category;
+ typedef typename iteratoro_traits::iterator_category iteratoro_category;
+ typedef typename iteratori1_traits::value_type value1_type;
+ typedef typename iteratori2_traits::value_type value2_type;
+
+ return set_union_switch(begin1, end1, begin2, end2, out,
+ __gnu_parallel::less<value1_type, value2_type>(),
+ iteratori1_category(), iteratori2_category(),
+ iteratoro_category());
+ }
// Public interface
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Predicate>
- inline OutputIterator
- set_union(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- InputIterator2 end2, OutputIterator out, Predicate pred)
- {
- typedef std::iterator_traits<InputIterator1> iteratori1_traits;
- typedef std::iterator_traits<InputIterator2> iteratori2_traits;
- typedef std::iterator_traits<OutputIterator> iteratoro_traits;
- typedef typename iteratori1_traits::iterator_category iteratori1_category;
- typedef typename iteratori2_traits::iterator_category iteratori2_category;
- typedef typename iteratoro_traits::iterator_category iteratoro_category;
-
- return set_union_switch(begin1, end1, begin2, end2, out, pred,
- iteratori1_category(), iteratori2_category(),
- iteratoro_category());
- }
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename Predicate>
+ inline OutputIterator
+ set_union(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator out, Predicate pred)
+ {
+ typedef std::iterator_traits<InputIterator1> iteratori1_traits;
+ typedef std::iterator_traits<InputIterator2> iteratori2_traits;
+ typedef std::iterator_traits<OutputIterator> iteratoro_traits;
+ typedef typename iteratori1_traits::iterator_category
+ iteratori1_category;
+ typedef typename iteratori2_traits::iterator_category
+ iteratori2_category;
+ typedef typename iteratoro_traits::iterator_category iteratoro_category;
+
+ return set_union_switch(begin1, end1, begin2, end2, out, pred,
+ iteratori1_category(), iteratori2_category(),
+ iteratoro_category());
+ }
// Sequential fallback.
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
- inline OutputIterator
- set_intersection(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator out, __gnu_parallel::sequential_tag)
- {
- return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, end2, out);
- }
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator>
+ inline OutputIterator
+ set_intersection(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator out, __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::set_intersection(begin1, end1,
+ begin2, end2, out); }
// Sequential fallback.
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Predicate>
- inline OutputIterator
- set_intersection(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator out, Predicate pred,
- __gnu_parallel::sequential_tag)
- {
- return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, end2,
- out, pred);
- }
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename Predicate>
+ inline OutputIterator
+ set_intersection(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator out, Predicate pred,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, end2,
+ out, pred); }
// Sequential fallback for input iterator case
- template<typename InputIterator1, typename InputIterator2, typename Predicate,
- typename OutputIterator, typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
- inline OutputIterator
- set_intersection_switch(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator result, Predicate pred,
- IteratorTag1, IteratorTag2, IteratorTag3)
- {
- return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2,
- end2, result, pred);
- }
+ template<typename InputIterator1, typename InputIterator2,
+ typename Predicate, typename OutputIterator,
+ typename IteratorTag1, typename IteratorTag2,
+ typename IteratorTag3>
+ inline OutputIterator
+ set_intersection_switch(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator result, Predicate pred,
+ IteratorTag1, IteratorTag2, IteratorTag3)
+ { return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2,
+ end2, result, pred); }
// Parallel set_intersection for random access iterators
template<typename RandomAccessIterator1, typename RandomAccessIterator2,
typename OutputRandomAccessIterator, typename Predicate>
- OutputRandomAccessIterator
- set_intersection_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, RandomAccessIterator2 end2, OutputRandomAccessIterator result, Predicate pred, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag)
- {
- 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);
- else
- return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2,
- end2, result, pred);
- }
+ 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)
+ {
+ 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);
+ else
+ return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2,
+ end2, result, pred);
+ }
// Public interface
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
- inline OutputIterator
- set_intersection(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator out)
- {
- typedef std::iterator_traits<InputIterator1> iteratori1_traits;
- typedef std::iterator_traits<InputIterator2> iteratori2_traits;
- typedef std::iterator_traits<OutputIterator> iteratoro_traits;
- typedef typename iteratori1_traits::iterator_category iteratori1_category;
- typedef typename iteratori2_traits::iterator_category iteratori2_category;
- typedef typename iteratoro_traits::iterator_category iteratoro_category;
- typedef typename iteratori1_traits::value_type value1_type;
- typedef typename iteratori2_traits::value_type value2_type;
-
- return set_intersection_switch(begin1, end1, begin2, end2, out,
- __gnu_parallel::less<value1_type, value2_type>(),
- iteratori1_category(), iteratori2_category(),
- iteratoro_category());
- }
-
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Predicate>
- inline OutputIterator
- set_intersection(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- InputIterator2 end2, OutputIterator out, Predicate pred)
- {
- typedef std::iterator_traits<InputIterator1> iteratori1_traits;
- typedef std::iterator_traits<InputIterator2> iteratori2_traits;
- typedef std::iterator_traits<OutputIterator> iteratoro_traits;
- typedef typename iteratori1_traits::iterator_category iteratori1_category;
- typedef typename iteratori2_traits::iterator_category iteratori2_category;
- typedef typename iteratoro_traits::iterator_category iteratoro_category;
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator>
+ inline OutputIterator
+ set_intersection(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator out)
+ {
+ typedef std::iterator_traits<InputIterator1> iteratori1_traits;
+ typedef std::iterator_traits<InputIterator2> iteratori2_traits;
+ typedef std::iterator_traits<OutputIterator> iteratoro_traits;
+ typedef typename iteratori1_traits::iterator_category
+ iteratori1_category;
+ typedef typename iteratori2_traits::iterator_category
+ iteratori2_category;
+ typedef typename iteratoro_traits::iterator_category iteratoro_category;
+ typedef typename iteratori1_traits::value_type value1_type;
+ typedef typename iteratori2_traits::value_type value2_type;
+
+ return set_intersection_switch(begin1, end1, begin2, end2, out,
+ __gnu_parallel::
+ less<value1_type, value2_type>(),
+ iteratori1_category(),
+ iteratori2_category(),
+ iteratoro_category());
+ }
- return set_intersection_switch(begin1, end1, begin2, end2, out, pred,
- iteratori1_category(), iteratori2_category(),
- iteratoro_category());
- }
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename Predicate>
+ inline OutputIterator
+ set_intersection(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator out, Predicate pred)
+ {
+ typedef std::iterator_traits<InputIterator1> iteratori1_traits;
+ typedef std::iterator_traits<InputIterator2> iteratori2_traits;
+ typedef std::iterator_traits<OutputIterator> iteratoro_traits;
+ typedef typename iteratori1_traits::iterator_category
+ iteratori1_category;
+ typedef typename iteratori2_traits::iterator_category
+ iteratori2_category;
+ typedef typename iteratoro_traits::iterator_category iteratoro_category;
+
+ return set_intersection_switch(begin1, end1, begin2, end2, out, pred,
+ iteratori1_category(),
+ iteratori2_category(),
+ iteratoro_category());
+ }
// Sequential fallback
template<typename InputIterator1, typename InputIterator2,
typename OutputIterator>
- inline OutputIterator
- set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator out, __gnu_parallel::sequential_tag)
- {
- return _GLIBCXX_STD_P::set_symmetric_difference(begin1,end1, begin2,
- end2, out);
- }
+ inline OutputIterator
+ set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator out,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::set_symmetric_difference(begin1,end1,
+ begin2, end2, out); }
// Sequential fallback
template<typename InputIterator1, typename InputIterator2,
typename OutputIterator, typename Predicate>
- inline OutputIterator
- set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator out, Predicate pred, __gnu_parallel::sequential_tag)
- {
- return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1, begin2,
- end2, out, pred);
- }
+ inline OutputIterator
+ set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
+ 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); }
// Sequential fallback for input iterator case
- template<typename InputIterator1, typename InputIterator2, typename Predicate, typename OutputIterator, typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
- inline OutputIterator
- set_symmetric_difference_switch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator result, Predicate pred, IteratorTag1, IteratorTag2, IteratorTag3)
- {
- return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1, begin2, end2,
- result, pred);
- }
+ template<typename InputIterator1, typename InputIterator2,
+ typename Predicate, typename OutputIterator,
+ typename IteratorTag1, typename IteratorTag2,
+ typename IteratorTag3>
+ inline OutputIterator
+ set_symmetric_difference_switch(InputIterator1 begin1,
+ InputIterator1 end1,
+ InputIterator2 begin2,
+ InputIterator2 end2,
+ OutputIterator result, Predicate pred,
+ IteratorTag1, IteratorTag2, IteratorTag3)
+ { return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1,
+ begin2, end2,
+ result, pred); }
// Parallel set_symmetric_difference for random access iterators
template<typename RandomAccessIterator1, typename RandomAccessIterator2,
typename OutputRandomAccessIterator, typename Predicate>
- 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)
- {
- 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);
- }
+ 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)
+ {
+ 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);
+ }
// Public interface.
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
- inline OutputIterator
- set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator out)
- {
- typedef std::iterator_traits<InputIterator1> iteratori1_traits;
- typedef std::iterator_traits<InputIterator2> iteratori2_traits;
- typedef std::iterator_traits<OutputIterator> iteratoro_traits;
- typedef typename iteratori1_traits::iterator_category iteratori1_category;
- typedef typename iteratori2_traits::iterator_category iteratori2_category;
- typedef typename iteratoro_traits::iterator_category iteratoro_category;
- typedef typename iteratori1_traits::value_type value1_type;
- typedef typename iteratori2_traits::value_type value2_type;
-
- return set_symmetric_difference_switch(begin1, end1, begin2, end2, out,
- __gnu_parallel::less<value1_type, value2_type>(),
- iteratori1_category(), iteratori2_category(),
- iteratoro_category());
- }
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator>
+ inline OutputIterator
+ set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator out)
+ {
+ typedef std::iterator_traits<InputIterator1> iteratori1_traits;
+ typedef std::iterator_traits<InputIterator2> iteratori2_traits;
+ typedef std::iterator_traits<OutputIterator> iteratoro_traits;
+ typedef typename iteratori1_traits::iterator_category
+ iteratori1_category;
+ typedef typename iteratori2_traits::iterator_category
+ iteratori2_category;
+ typedef typename iteratoro_traits::iterator_category iteratoro_category;
+ typedef typename iteratori1_traits::value_type value1_type;
+ typedef typename iteratori2_traits::value_type value2_type;
+
+ return set_symmetric_difference_switch(begin1, end1, begin2, end2, out,
+ __gnu_parallel::
+ less<value1_type, value2_type>(),
+ iteratori1_category(),
+ iteratori2_category(),
+ iteratoro_category());
+ }
// Public interface.
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Predicate>
- inline OutputIterator
- set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator out, Predicate pred)
- {
- typedef std::iterator_traits<InputIterator1> iteratori1_traits;
- typedef std::iterator_traits<InputIterator2> iteratori2_traits;
- typedef std::iterator_traits<OutputIterator> iteratoro_traits;
- typedef typename iteratori1_traits::iterator_category iteratori1_category;
- 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());
- }
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename Predicate>
+ inline OutputIterator
+ set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator out, Predicate pred)
+ {
+ typedef std::iterator_traits<InputIterator1> iteratori1_traits;
+ typedef std::iterator_traits<InputIterator2> iteratori2_traits;
+ typedef std::iterator_traits<OutputIterator> iteratoro_traits;
+ typedef typename iteratori1_traits::iterator_category
+ iteratori1_category;
+ 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());
+ }
// Sequential fallback.
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
- inline OutputIterator
- set_difference(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator out, __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::set_difference(begin1,end1, begin2, end2, out); }
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator>
+ inline OutputIterator
+ set_difference(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator out, __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::set_difference(begin1,end1, begin2, end2, out); }
// Sequential fallback.
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Predicate>
- inline OutputIterator
- set_difference(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator out, Predicate pred,
- __gnu_parallel::sequential_tag)
- {
- return _GLIBCXX_STD_P::set_difference(begin1, end1, begin2, end2, out, pred);
- }
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename Predicate>
+ inline OutputIterator
+ set_difference(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator out, Predicate pred,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::set_difference(begin1, end1,
+ begin2, end2, out, pred); }
// Sequential fallback for input iterator case.
- template<typename InputIterator1, typename InputIterator2, typename Predicate,
- typename OutputIterator, typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
- inline OutputIterator
- set_difference_switch(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator result, Predicate pred,
- IteratorTag1, IteratorTag2, IteratorTag3)
- {
- return _GLIBCXX_STD_P::set_difference(begin1, end1, begin2, end2, result, pred);
- }
+ template<typename InputIterator1, typename InputIterator2,
+ typename Predicate, typename OutputIterator,
+ typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
+ inline OutputIterator
+ set_difference_switch(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator result, Predicate pred,
+ IteratorTag1, IteratorTag2, IteratorTag3)
+ { return _GLIBCXX_STD_P::set_difference(begin1, end1,
+ begin2, end2, result, pred); }
// Parallel set_difference for random access iterators
template<typename RandomAccessIterator1, typename RandomAccessIterator2,
typename OutputRandomAccessIterator, typename Predicate>
- 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)
- {
- 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);
- }
+ 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)
+ {
+ 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);
+ }
// Public interface
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
- inline OutputIterator
- set_difference(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator out)
- {
- typedef std::iterator_traits<InputIterator1> iteratori1_traits;
- typedef std::iterator_traits<InputIterator2> iteratori2_traits;
- typedef std::iterator_traits<OutputIterator> iteratoro_traits;
- typedef typename iteratori1_traits::iterator_category iteratori1_category;
- typedef typename iteratori2_traits::iterator_category iteratori2_category;
- typedef typename iteratoro_traits::iterator_category iteratoro_category;
- typedef typename iteratori1_traits::value_type value1_type;
- typedef typename iteratori2_traits::value_type value2_type;
-
- return set_difference_switch(begin1, end1, begin2, end2, out,
- __gnu_parallel::less<value1_type, value2_type>(),
- iteratori1_category(), iteratori2_category(),
- iteratoro_category());
- }
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator>
+ inline OutputIterator
+ set_difference(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator out)
+ {
+ typedef std::iterator_traits<InputIterator1> iteratori1_traits;
+ typedef std::iterator_traits<InputIterator2> iteratori2_traits;
+ typedef std::iterator_traits<OutputIterator> iteratoro_traits;
+ typedef typename iteratori1_traits::iterator_category
+ iteratori1_category;
+ typedef typename iteratori2_traits::iterator_category
+ iteratori2_category;
+ typedef typename iteratoro_traits::iterator_category iteratoro_category;
+ typedef typename iteratori1_traits::value_type value1_type;
+ typedef typename iteratori2_traits::value_type value2_type;
+
+ return set_difference_switch(begin1, end1, begin2, end2, out,
+ __gnu_parallel::
+ less<value1_type, value2_type>(),
+ iteratori1_category(),
+ iteratori2_category(),
+ iteratoro_category());
+ }
// Public interface
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Predicate>
- inline OutputIterator
- set_difference(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, InputIterator2 end2,
- OutputIterator out, Predicate pred)
- {
- typedef std::iterator_traits<InputIterator1> iteratori1_traits;
- typedef std::iterator_traits<InputIterator2> iteratori2_traits;
- typedef std::iterator_traits<OutputIterator> iteratoro_traits;
- typedef typename iteratori1_traits::iterator_category iteratori1_category;
- typedef typename iteratori2_traits::iterator_category iteratori2_category;
- typedef typename iteratoro_traits::iterator_category iteratoro_category;
-
- return set_difference_switch(begin1, end1, begin2, end2, out, pred,
- iteratori1_category(), iteratori2_category(),
- iteratoro_category());
- }
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename Predicate>
+ inline OutputIterator
+ set_difference(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator out, Predicate pred)
+ {
+ typedef std::iterator_traits<InputIterator1> iteratori1_traits;
+ typedef std::iterator_traits<InputIterator2> iteratori2_traits;
+ typedef std::iterator_traits<OutputIterator> iteratoro_traits;
+ typedef typename iteratori1_traits::iterator_category
+ iteratori1_category;
+ typedef typename iteratori2_traits::iterator_category
+ iteratori2_category;
+ typedef typename iteratoro_traits::iterator_category iteratoro_category;
+
+ return set_difference_switch(begin1, end1, begin2, end2, out, pred,
+ iteratori1_category(),
+ iteratori2_category(),
+ iteratoro_category());
+ }
// Sequential fallback
template<typename ForwardIterator>
- inline ForwardIterator
- adjacent_find(ForwardIterator begin, ForwardIterator end,
- __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::adjacent_find(begin, end); }
+ inline ForwardIterator
+ adjacent_find(ForwardIterator begin, ForwardIterator end,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::adjacent_find(begin, end); }
// Sequential fallback
template<typename ForwardIterator, typename BinaryPredicate>
- inline ForwardIterator
- adjacent_find(ForwardIterator begin, ForwardIterator end,
- BinaryPredicate binary_pred, __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::adjacent_find(begin, end, binary_pred); }
+ inline ForwardIterator
+ adjacent_find(ForwardIterator begin, ForwardIterator end,
+ BinaryPredicate binary_pred, __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::adjacent_find(begin, end, binary_pred); }
// Parallel algorithm for random access iterators
template<typename RandomAccessIterator>
- RandomAccessIterator
- adjacent_find_switch(RandomAccessIterator begin, RandomAccessIterator end,
- random_access_iterator_tag)
- {
- typedef iterator_traits<RandomAccessIterator> traits_type;
- typedef typename traits_type::value_type value_type;
-
- if (_GLIBCXX_PARALLEL_CONDITION(true))
- {
- RandomAccessIterator spot = __gnu_parallel::find_template(begin, end - 1, begin, equal_to<value_type>(), __gnu_parallel::adjacent_find_selector()).first;
- if (spot == (end - 1))
- return end;
- else
- return spot;
- }
- else
- return adjacent_find(begin, end, __gnu_parallel::sequential_tag());
- }
+ RandomAccessIterator
+ adjacent_find_switch(RandomAccessIterator begin, RandomAccessIterator end,
+ random_access_iterator_tag)
+ {
+ typedef iterator_traits<RandomAccessIterator> traits_type;
+ typedef typename traits_type::value_type value_type;
+
+ if (_GLIBCXX_PARALLEL_CONDITION(true))
+ {
+ RandomAccessIterator spot = __gnu_parallel::
+ find_template(begin, end - 1, begin, equal_to<value_type>(),
+ __gnu_parallel::adjacent_find_selector()).first;
+ if (spot == (end - 1))
+ return end;
+ else
+ return spot;
+ }
+ else
+ return adjacent_find(begin, end, __gnu_parallel::sequential_tag());
+ }
// Sequential fallback for input iterator case
template<typename ForwardIterator, typename IteratorTag>
- inline ForwardIterator
- adjacent_find_switch(ForwardIterator begin, ForwardIterator end, IteratorTag)
- { return adjacent_find(begin, end, __gnu_parallel::sequential_tag()); }
+ inline ForwardIterator
+ adjacent_find_switch(ForwardIterator begin, ForwardIterator end,
+ IteratorTag)
+ { return adjacent_find(begin, end, __gnu_parallel::sequential_tag()); }
// Public interface
template<typename ForwardIterator>
- inline ForwardIterator
- adjacent_find(ForwardIterator begin, ForwardIterator end)
- {
- typedef iterator_traits<ForwardIterator> traits_type;
- typedef typename traits_type::iterator_category iterator_category;
- return adjacent_find_switch(begin, end, iterator_category());
- }
+ inline ForwardIterator
+ adjacent_find(ForwardIterator begin, ForwardIterator end)
+ {
+ typedef iterator_traits<ForwardIterator> traits_type;
+ typedef typename traits_type::iterator_category iterator_category;
+ return adjacent_find_switch(begin, end, iterator_category());
+ }
// Sequential fallback for input iterator case
- template<typename ForwardIterator, typename BinaryPredicate, typename IteratorTag>
- inline ForwardIterator
- adjacent_find_switch(ForwardIterator begin, ForwardIterator end,
- BinaryPredicate pred, IteratorTag)
- { return adjacent_find(begin, end, pred, __gnu_parallel::sequential_tag()); }
+ template<typename ForwardIterator, typename BinaryPredicate,
+ typename IteratorTag>
+ inline ForwardIterator
+ adjacent_find_switch(ForwardIterator begin, ForwardIterator end,
+ BinaryPredicate pred, IteratorTag)
+ { return adjacent_find(begin, end, pred,
+ __gnu_parallel::sequential_tag()); }
// Parallel algorithm for random access iterators
template<typename RandomAccessIterator, typename BinaryPredicate>
- RandomAccessIterator
- adjacent_find_switch(RandomAccessIterator begin, RandomAccessIterator end,
- BinaryPredicate pred, random_access_iterator_tag)
- {
- if (_GLIBCXX_PARALLEL_CONDITION(true))
- return __gnu_parallel::find_template(begin, end, begin, pred,
- __gnu_parallel::adjacent_find_selector()).first;
- else
- return adjacent_find(begin, end, pred, __gnu_parallel::sequential_tag());
- }
+ RandomAccessIterator
+ adjacent_find_switch(RandomAccessIterator begin, RandomAccessIterator end,
+ 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;
+ else
+ return adjacent_find(begin, end, pred,
+ __gnu_parallel::sequential_tag());
+ }
// Public interface
template<typename ForwardIterator, typename BinaryPredicate>
- inline ForwardIterator
- adjacent_find(ForwardIterator begin, ForwardIterator end,
- BinaryPredicate pred)
- {
- typedef iterator_traits<ForwardIterator> traits_type;
- typedef typename traits_type::iterator_category iterator_category;
- return adjacent_find_switch(begin, end, pred, iterator_category());
- }
+ inline ForwardIterator
+ adjacent_find(ForwardIterator begin, ForwardIterator end,
+ BinaryPredicate pred)
+ {
+ typedef iterator_traits<ForwardIterator> traits_type;
+ typedef typename traits_type::iterator_category iterator_category;
+ return adjacent_find_switch(begin, end, pred, iterator_category());
+ }
// Sequential fallback
template<typename InputIterator, typename T>
- inline typename iterator_traits<InputIterator>::difference_type
- count(InputIterator begin, InputIterator end, const T& value,
- __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::count(begin, end, value); }
+ inline typename iterator_traits<InputIterator>::difference_type
+ count(InputIterator begin, InputIterator end, const T& value,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::count(begin, end, value); }
// Parallel code for random access iterators
template<typename RandomAccessIterator, typename T>
- typename iterator_traits<RandomAccessIterator>::difference_type
- count_switch(RandomAccessIterator begin, RandomAccessIterator end,
- const T& value, random_access_iterator_tag,
- __gnu_parallel::parallelism parallelism_tag
- = __gnu_parallel::parallel_unbalanced)
- {
- typedef iterator_traits<RandomAccessIterator> traits_type;
- typedef typename traits_type::value_type value_type;
- typedef typename traits_type::difference_type difference_type;
- typedef __gnu_parallel::sequence_index_t sequence_index_t;
-
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<sequence_index_t>(end - begin) >= __gnu_parallel::Settings::count_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
- {
- __gnu_parallel::count_selector<RandomAccessIterator, difference_type> functionality;
- difference_type res = 0;
- __gnu_parallel::for_each_template_random_access(begin, end, value, functionality, std::plus<sequence_index_t>(), res, res, -1, parallelism_tag);
- return res;
- }
- else
- return count(begin, end, value, __gnu_parallel::sequential_tag());
- }
+ typename iterator_traits<RandomAccessIterator>::difference_type
+ count_switch(RandomAccessIterator begin, RandomAccessIterator end,
+ const T& value, random_access_iterator_tag,
+ __gnu_parallel::parallelism parallelism_tag
+ = __gnu_parallel::parallel_unbalanced)
+ {
+ typedef iterator_traits<RandomAccessIterator> traits_type;
+ typedef typename traits_type::value_type value_type;
+ typedef typename traits_type::difference_type difference_type;
+ typedef __gnu_parallel::sequence_index_t sequence_index_t;
+
+ if (_GLIBCXX_PARALLEL_CONDITION(static_cast<sequence_index_t>
+ (end - begin)
+ >= __gnu_parallel::Settings::
+ count_minimal_n
+ && __gnu_parallel::
+ is_parallel(parallelism_tag)))
+ {
+ __gnu_parallel::count_selector<RandomAccessIterator, difference_type>
+ functionality;
+ difference_type res = 0;
+ __gnu_parallel::
+ for_each_template_random_access(begin, end, value,
+ functionality,
+ std::plus<sequence_index_t>(),
+ res, res, -1, parallelism_tag);
+ return res;
+ }
+ else
+ return count(begin, end, value, __gnu_parallel::sequential_tag());
+ }
// Sequential fallback for input iterator case.
template<typename InputIterator, typename T, typename IteratorTag>
- typename iterator_traits<InputIterator>::difference_type
- count_switch(InputIterator begin, InputIterator end, const T& value,
- IteratorTag)
- { return count(begin, end, value, __gnu_parallel::sequential_tag()); }
+ inline typename iterator_traits<InputIterator>::difference_type
+ count_switch(InputIterator begin, InputIterator end, const T& value,
+ IteratorTag)
+ { return count(begin, end, value, __gnu_parallel::sequential_tag()); }
// Public interface.
template<typename InputIterator, typename T>
- inline typename iterator_traits<InputIterator>::difference_type
- count(InputIterator begin, InputIterator end, const T& value,
- __gnu_parallel::parallelism parallelism_tag)
- {
- typedef iterator_traits<InputIterator> traits_type;
- typedef typename traits_type::iterator_category iterator_category;
- return count_switch(begin, end, value, iterator_category(),
- parallelism_tag);
- }
+ inline typename iterator_traits<InputIterator>::difference_type
+ count(InputIterator begin, InputIterator end, const T& value,
+ __gnu_parallel::parallelism parallelism_tag)
+ {
+ typedef iterator_traits<InputIterator> traits_type;
+ typedef typename traits_type::iterator_category iterator_category;
+ return count_switch(begin, end, value, iterator_category(),
+ parallelism_tag);
+ }
template<typename InputIterator, typename T>
- inline typename iterator_traits<InputIterator>::difference_type
- count(InputIterator begin, InputIterator end, const T& value)
- {
- typedef iterator_traits<InputIterator> traits_type;
- typedef typename traits_type::iterator_category iterator_category;
- return count_switch(begin, end, value, iterator_category());
- }
+ inline typename iterator_traits<InputIterator>::difference_type
+ count(InputIterator begin, InputIterator end, const T& value)
+ {
+ typedef iterator_traits<InputIterator> traits_type;
+ typedef typename traits_type::iterator_category iterator_category;
+ return count_switch(begin, end, value, iterator_category());
+ }
// Sequential fallback.
template<typename InputIterator, typename Predicate>
- inline typename iterator_traits<InputIterator>::difference_type
- count_if(InputIterator begin, InputIterator end, Predicate pred,
- __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::count_if(begin, end, pred); }
+ inline typename iterator_traits<InputIterator>::difference_type
+ count_if(InputIterator begin, InputIterator end, Predicate pred,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::count_if(begin, end, pred); }
// Parallel count_if for random access iterators
template<typename RandomAccessIterator, typename Predicate>
- typename iterator_traits<RandomAccessIterator>::difference_type
- count_if_switch(RandomAccessIterator begin, RandomAccessIterator end,
- Predicate pred, random_access_iterator_tag,
- __gnu_parallel::parallelism parallelism_tag
- = __gnu_parallel::parallel_unbalanced)
- {
- typedef iterator_traits<RandomAccessIterator> traits_type;
- typedef typename traits_type::value_type value_type;
- typedef typename traits_type::difference_type difference_type;
- typedef __gnu_parallel::sequence_index_t sequence_index_t;
-
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<sequence_index_t>(end - begin) >= __gnu_parallel::Settings::count_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
- {
- difference_type res = 0;
- __gnu_parallel::count_if_selector<RandomAccessIterator, difference_type> functionality;
- __gnu_parallel::for_each_template_random_access(begin, end, pred, functionality, std::plus<sequence_index_t>(), res, res, -1, parallelism_tag);
- return res;
- }
- else
- return count_if(begin, end, pred, __gnu_parallel::sequential_tag());
- }
+ typename iterator_traits<RandomAccessIterator>::difference_type
+ count_if_switch(RandomAccessIterator begin, RandomAccessIterator end,
+ Predicate pred, random_access_iterator_tag,
+ __gnu_parallel::parallelism parallelism_tag
+ = __gnu_parallel::parallel_unbalanced)
+ {
+ typedef iterator_traits<RandomAccessIterator> traits_type;
+ typedef typename traits_type::value_type value_type;
+ typedef typename traits_type::difference_type difference_type;
+ typedef __gnu_parallel::sequence_index_t sequence_index_t;
+
+ if (_GLIBCXX_PARALLEL_CONDITION(static_cast<sequence_index_t>
+ (end - begin)
+ >= __gnu_parallel::Settings::
+ count_minimal_n
+ && __gnu_parallel::
+ is_parallel(parallelism_tag)))
+ {
+ difference_type res = 0;
+ __gnu_parallel::
+ count_if_selector<RandomAccessIterator, difference_type>
+ functionality;
+ __gnu_parallel::
+ for_each_template_random_access(begin, end, pred,
+ functionality,
+ std::plus<sequence_index_t>(),
+ res, res, -1, parallelism_tag);
+ return res;
+ }
+ else
+ return count_if(begin, end, pred, __gnu_parallel::sequential_tag());
+ }
// Sequential fallback for input iterator case.
template<typename InputIterator, typename Predicate, typename IteratorTag>
- typename iterator_traits<InputIterator>::difference_type
- count_if_switch(InputIterator begin, InputIterator end, Predicate pred,
- IteratorTag)
- { return count_if(begin, end, pred, __gnu_parallel::sequential_tag()); }
+ inline typename iterator_traits<InputIterator>::difference_type
+ count_if_switch(InputIterator begin, InputIterator end, Predicate pred,
+ IteratorTag)
+ { return count_if(begin, end, pred, __gnu_parallel::sequential_tag()); }
// Public interface.
template<typename InputIterator, typename Predicate>
- inline typename iterator_traits<InputIterator>::difference_type
- count_if(InputIterator begin, InputIterator end, Predicate pred,
- __gnu_parallel::parallelism parallelism_tag)
- {
- typedef iterator_traits<InputIterator> traits_type;
- typedef typename traits_type::iterator_category iterator_category;
- return count_if_switch(begin, end, pred, iterator_category(),
- parallelism_tag);
- }
+ inline typename iterator_traits<InputIterator>::difference_type
+ count_if(InputIterator begin, InputIterator end, Predicate pred,
+ __gnu_parallel::parallelism parallelism_tag)
+ {
+ typedef iterator_traits<InputIterator> traits_type;
+ typedef typename traits_type::iterator_category iterator_category;
+ return count_if_switch(begin, end, pred, iterator_category(),
+ parallelism_tag);
+ }
template<typename InputIterator, typename Predicate>
- inline typename iterator_traits<InputIterator>::difference_type
- count_if(InputIterator begin, InputIterator end, Predicate pred)
- {
- typedef iterator_traits<InputIterator> traits_type;
- typedef typename traits_type::iterator_category iterator_category;
- return count_if_switch(begin, end, pred, iterator_category());
- }
+ inline typename iterator_traits<InputIterator>::difference_type
+ count_if(InputIterator begin, InputIterator end, Predicate pred)
+ {
+ typedef iterator_traits<InputIterator> traits_type;
+ typedef typename traits_type::iterator_category iterator_category;
+ return count_if_switch(begin, end, pred, iterator_category());
+ }
// Sequential fallback.
template<typename ForwardIterator1, typename ForwardIterator2>
- inline ForwardIterator1
- search(ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2, __gnu_parallel::sequential_tag)
- {
- return _GLIBCXX_STD_P::search(begin1, end1, begin2, end2);
- }
+ inline ForwardIterator1
+ search(ForwardIterator1 begin1, ForwardIterator1 end1,
+ ForwardIterator2 begin2, ForwardIterator2 end2,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::search(begin1, end1, begin2, end2); }
// Parallel algorithm for random access iterator
template<typename RandomAccessIterator1, typename RandomAccessIterator2>
- RandomAccessIterator1
- search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, RandomAccessIterator2 end2, random_access_iterator_tag, random_access_iterator_tag)
- {
- typedef std::iterator_traits<RandomAccessIterator1> iterator1_traits;
- typedef typename iterator1_traits::value_type value1_type;
- typedef std::iterator_traits<RandomAccessIterator2> iterator2_traits;
- typedef typename iterator2_traits::value_type value2_type;
-
- if (_GLIBCXX_PARALLEL_CONDITION(true))
- return __gnu_parallel::search_template(begin1, end1, begin2, end2, __gnu_parallel::equal_to<value1_type, value2_type>());
- else
- return search(begin1, end1, begin2, end2, __gnu_parallel::sequential_tag());
- }
+ RandomAccessIterator1
+ search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
+ RandomAccessIterator2 begin2, RandomAccessIterator2 end2,
+ random_access_iterator_tag, random_access_iterator_tag)
+ {
+ typedef std::iterator_traits<RandomAccessIterator1> iterator1_traits;
+ typedef typename iterator1_traits::value_type value1_type;
+ typedef std::iterator_traits<RandomAccessIterator2> iterator2_traits;
+ typedef typename iterator2_traits::value_type value2_type;
+
+ if (_GLIBCXX_PARALLEL_CONDITION(true))
+ return __gnu_parallel::
+ search_template(begin1, end1, begin2, end2, __gnu_parallel::
+ equal_to<value1_type, value2_type>());
+ else
+ return search(begin1, end1, begin2, end2,
+ __gnu_parallel::sequential_tag());
+ }
// Sequential fallback for input iterator case
- template<typename ForwardIterator1, typename ForwardIterator2, typename IteratorTag1, typename IteratorTag2>
- inline ForwardIterator1
- search_switch(ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2, IteratorTag1, IteratorTag2)
- {
- return search(begin1, end1, begin2, end2, __gnu_parallel::sequential_tag());
- }
+ template<typename ForwardIterator1, typename ForwardIterator2,
+ typename IteratorTag1, typename IteratorTag2>
+ inline ForwardIterator1
+ search_switch(ForwardIterator1 begin1, ForwardIterator1 end1,
+ ForwardIterator2 begin2, ForwardIterator2 end2,
+ IteratorTag1, IteratorTag2)
+ { return search(begin1, end1, begin2, end2,
+ __gnu_parallel::sequential_tag()); }
// Public interface.
template<typename ForwardIterator1, typename ForwardIterator2>
- inline ForwardIterator1
- search(ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2)
- {
- typedef std::iterator_traits<ForwardIterator1> iterator1_traits;
- typedef typename iterator1_traits::iterator_category iterator1_category;
- typedef std::iterator_traits<ForwardIterator2> iterator2_traits;
- typedef typename iterator2_traits::iterator_category iterator2_category;
-
- return search_switch(begin1, end1, begin2, end2, iterator1_category(), iterator2_category());
- }
+ inline ForwardIterator1
+ search(ForwardIterator1 begin1, ForwardIterator1 end1,
+ ForwardIterator2 begin2, ForwardIterator2 end2)
+ {
+ typedef std::iterator_traits<ForwardIterator1> iterator1_traits;
+ typedef typename iterator1_traits::iterator_category iterator1_category;
+ typedef std::iterator_traits<ForwardIterator2> iterator2_traits;
+ typedef typename iterator2_traits::iterator_category iterator2_category;
+
+ return search_switch(begin1, end1, begin2, end2,
+ iterator1_category(), iterator2_category());
+ }
// Public interface.
- template<typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
- inline ForwardIterator1
- search(ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2, BinaryPredicate pred, __gnu_parallel::sequential_tag)
- {
- return _GLIBCXX_STD_P::search(begin1, end1, begin2, end2, pred);
- }
+ template<typename ForwardIterator1, typename ForwardIterator2,
+ typename BinaryPredicate>
+ inline ForwardIterator1
+ search(ForwardIterator1 begin1, ForwardIterator1 end1,
+ ForwardIterator2 begin2, ForwardIterator2 end2,
+ BinaryPredicate pred, __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::search(begin1, end1, begin2, end2, pred); }
// Parallel algorithm for random access iterator.
template<typename RandomAccessIterator1, typename RandomAccessIterator2,
typename BinaryPredicate>
- RandomAccessIterator1
- search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
- 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);
- else
- return search(begin1, end1, begin2, end2, pred, __gnu_parallel::sequential_tag());
- }
+ RandomAccessIterator1
+ search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
+ 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);
+ else
+ return search(begin1, end1, begin2, end2, pred,
+ __gnu_parallel::sequential_tag());
+ }
// Sequential fallback for input iterator case
template<typename ForwardIterator1, typename ForwardIterator2,
- typename BinaryPredicate, typename IteratorTag1, typename IteratorTag2>
- inline ForwardIterator1
- search_switch(ForwardIterator1 begin1, ForwardIterator1 end1,
- ForwardIterator2 begin2, ForwardIterator2 end2, BinaryPredicate pred, IteratorTag1, IteratorTag2)
- {
- return search(begin1, end1, begin2, end2, pred, __gnu_parallel::sequential_tag());
- }
+ typename BinaryPredicate, typename IteratorTag1,
+ typename IteratorTag2>
+ inline ForwardIterator1
+ search_switch(ForwardIterator1 begin1, ForwardIterator1 end1,
+ ForwardIterator2 begin2, ForwardIterator2 end2,
+ BinaryPredicate pred, IteratorTag1, IteratorTag2)
+ { return search(begin1, end1, begin2, end2, pred,
+ __gnu_parallel::sequential_tag()); }
// Public interface
- template<typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
- inline ForwardIterator1
- search(ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2, BinaryPredicate pred)
- {
- typedef std::iterator_traits<ForwardIterator1> iterator1_traits;
- typedef typename iterator1_traits::iterator_category iterator1_category;
- typedef std::iterator_traits<ForwardIterator2> iterator2_traits;
- typedef typename iterator2_traits::iterator_category iterator2_category;
- return search_switch(begin1, end1, begin2, end2, pred, iterator1_category(), iterator2_category());
- }
+ template<typename ForwardIterator1, typename ForwardIterator2,
+ typename BinaryPredicate>
+ inline ForwardIterator1
+ search(ForwardIterator1 begin1, ForwardIterator1 end1,
+ ForwardIterator2 begin2, ForwardIterator2 end2,
+ BinaryPredicate pred)
+ {
+ typedef std::iterator_traits<ForwardIterator1> iterator1_traits;
+ typedef typename iterator1_traits::iterator_category iterator1_category;
+ typedef std::iterator_traits<ForwardIterator2> iterator2_traits;
+ typedef typename iterator2_traits::iterator_category iterator2_category;
+ return search_switch(begin1, end1, begin2, end2, pred,
+ iterator1_category(), iterator2_category());
+ }
// Sequential fallback
template<typename ForwardIterator, typename Integer, typename T>
- inline ForwardIterator
- search_n(ForwardIterator begin, ForwardIterator end, Integer count, const T& val, __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::search_n(begin, end, count, val); }
+ inline ForwardIterator
+ search_n(ForwardIterator begin, ForwardIterator end, Integer count,
+ const T& val, __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::search_n(begin, end, count, val); }
// Sequential fallback
- template<typename ForwardIterator, typename Integer, typename T, typename BinaryPredicate>
- inline ForwardIterator
- 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);
- }
+ template<typename ForwardIterator, typename Integer, typename T,
+ typename BinaryPredicate>
+ inline ForwardIterator
+ search_n(ForwardIterator begin, ForwardIterator end, Integer count,
+ const T& val, BinaryPredicate binary_pred,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::search_n(begin, end, count, val, binary_pred); }
// Public interface.
template<typename ForwardIterator, typename Integer, typename T>
- inline ForwardIterator
- search_n(ForwardIterator begin, ForwardIterator end, Integer count, const T& val)
- {
- typedef typename iterator_traits<ForwardIterator>::value_type value_type;
- return search_n(begin, end, count, val, __gnu_parallel::equal_to<value_type, T>());
- }
+ inline ForwardIterator
+ search_n(ForwardIterator begin, ForwardIterator end, Integer count,
+ const T& val)
+ {
+ typedef typename iterator_traits<ForwardIterator>::value_type value_type;
+ return search_n(begin, end, count, val,
+ __gnu_parallel::equal_to<value_type, T>());
+ }
// Parallel algorithm for random access iterators.
- template<typename RandomAccessIterator, typename Integer, typename T, typename BinaryPredicate>
- RandomAccessIterator
- search_n_switch(RandomAccessIterator begin, RandomAccessIterator end, Integer count, const T& val, BinaryPredicate binary_pred, random_access_iterator_tag)
- {
- if (_GLIBCXX_PARALLEL_CONDITION(true))
- {
- __gnu_parallel::pseudo_sequence<T, Integer> ps(val, count);
- return __gnu_parallel::search_template(begin, end, ps.begin(), ps.end(), binary_pred);
- }
- else
- return std::__search_n(begin, end, count, val, binary_pred, random_access_iterator_tag());
- }
+ template<typename RandomAccessIterator, typename Integer,
+ typename T, typename BinaryPredicate>
+ RandomAccessIterator
+ search_n_switch(RandomAccessIterator begin, RandomAccessIterator end,
+ Integer count, const T& val, BinaryPredicate binary_pred,
+ random_access_iterator_tag)
+ {
+ if (_GLIBCXX_PARALLEL_CONDITION(true))
+ {
+ __gnu_parallel::pseudo_sequence<T, Integer> ps(val, count);
+ return __gnu_parallel::search_template(begin, end, ps.begin(),
+ ps.end(), binary_pred);
+ }
+ else
+ return std::__search_n(begin, end, count, val,
+ binary_pred, random_access_iterator_tag());
+ }
// Sequential fallback for input iterator case.
- template<typename ForwardIterator, typename Integer, typename T, typename BinaryPredicate, typename IteratorTag>
- inline ForwardIterator
- 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());
- }
+ template<typename ForwardIterator, typename Integer, typename T,
+ typename BinaryPredicate, typename IteratorTag>
+ inline ForwardIterator
+ search_n_switch(ForwardIterator begin, ForwardIterator end, Integer count,
+ const T& val, BinaryPredicate binary_pred, IteratorTag)
+ { return __search_n(begin, end, count, val, binary_pred, IteratorTag()); }
// Public interface.
- template<typename ForwardIterator, typename Integer, typename T, typename BinaryPredicate>
- inline ForwardIterator
- search_n(ForwardIterator begin, ForwardIterator end, Integer count, const T& val, BinaryPredicate binary_pred)
- {
- return search_n_switch(begin, end, count, val, binary_pred, typename std::iterator_traits<ForwardIterator>::iterator_category());
- }
+ template<typename ForwardIterator, typename Integer, typename T,
+ typename BinaryPredicate>
+ inline ForwardIterator
+ search_n(ForwardIterator begin, ForwardIterator end, Integer count,
+ const T& val, BinaryPredicate binary_pred)
+ {
+ return search_n_switch(begin, end, count, val, binary_pred,
+ typename std::iterator_traits<ForwardIterator>::
+ iterator_category());
+ }
// Sequential fallback.
- template<typename InputIterator, typename OutputIterator, typename UnaryOperation>
- inline OutputIterator
- transform(InputIterator begin, InputIterator end, OutputIterator result,
- UnaryOperation unary_op, __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::transform(begin, end, result, unary_op); }
+ template<typename InputIterator, typename OutputIterator,
+ typename UnaryOperation>
+ inline OutputIterator
+ transform(InputIterator begin, InputIterator end, OutputIterator result,
+ UnaryOperation unary_op, __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::transform(begin, end, result, unary_op); }
// Parallel unary transform for random access iterators.
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename UnaryOperation>
- 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)
- {
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::transform_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
- {
- bool dummy = true;
- typedef __gnu_parallel::iterator_pair<RandomAccessIterator1, RandomAccessIterator2, random_access_iterator_tag> ip;
- ip begin_pair(begin, result), end_pair(end, result + (end - begin));
- __gnu_parallel::transform1_selector<ip> functionality;
- __gnu_parallel::for_each_template_random_access(begin_pair, end_pair, unary_op, functionality, __gnu_parallel::dummy_reduct(), dummy, dummy, -1, parallelism_tag);
- return functionality.finish_iterator;
- }
- else
- return transform(begin, end, result, unary_op,
- __gnu_parallel::sequential_tag());
- }
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename UnaryOperation>
+ RandomAccessIterator2
+ transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end,
+ RandomAccessIterator2 result, UnaryOperation unary_op,
+ random_access_iterator_tag, random_access_iterator_tag,
+ __gnu_parallel::parallelism parallelism_tag
+ = __gnu_parallel::parallel_balanced)
+ {
+ if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::
+ sequence_index_t>(end - begin)
+ >= __gnu_parallel::Settings::
+ transform_minimal_n
+ && __gnu_parallel::
+ is_parallel(parallelism_tag)))
+ {
+ bool dummy = true;
+ typedef __gnu_parallel::iterator_pair<RandomAccessIterator1,
+ RandomAccessIterator2, random_access_iterator_tag> ip;
+ ip begin_pair(begin, result), end_pair(end, result + (end - begin));
+ __gnu_parallel::transform1_selector<ip> functionality;
+ __gnu_parallel::
+ for_each_template_random_access(begin_pair, end_pair,
+ unary_op, functionality,
+ __gnu_parallel::dummy_reduct(),
+ dummy, dummy, -1, parallelism_tag);
+ return functionality.finish_iterator;
+ }
+ else
+ return transform(begin, end, result, unary_op,
+ __gnu_parallel::sequential_tag());
+ }
// Sequential fallback for input iterator case.
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename UnaryOperation, typename IteratorTag1, typename IteratorTag2>
- inline RandomAccessIterator2
- transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end, RandomAccessIterator2 result, UnaryOperation unary_op, IteratorTag1, IteratorTag2)
- {
- return transform(begin, end, result, unary_op,
- __gnu_parallel::sequential_tag());
- }
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename UnaryOperation, typename IteratorTag1,
+ typename IteratorTag2>
+ inline RandomAccessIterator2
+ transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end,
+ RandomAccessIterator2 result, UnaryOperation unary_op,
+ IteratorTag1, IteratorTag2)
+ { return transform(begin, end, result, unary_op,
+ __gnu_parallel::sequential_tag()); }
// Public interface.
- template<typename InputIterator, typename OutputIterator, typename UnaryOperation>
- inline OutputIterator
- transform(InputIterator begin, InputIterator end, OutputIterator result,
- UnaryOperation unary_op,
- __gnu_parallel::parallelism parallelism_tag)
- {
- typedef std::iterator_traits<InputIterator> iteratori_traits;
- typedef std::iterator_traits<OutputIterator> iteratoro_traits;
- typedef typename iteratori_traits::iterator_category iteratori_category;
- typedef typename iteratoro_traits::iterator_category iteratoro_category;
-
- return transform1_switch(begin, end, result, unary_op,
- iteratori_category(), iteratoro_category(),
- parallelism_tag);
- }
-
- template<typename InputIterator, typename OutputIterator, typename UnaryOperation>
- inline OutputIterator
- transform(InputIterator begin, InputIterator end, OutputIterator result,
- UnaryOperation unary_op)
- {
- typedef std::iterator_traits<InputIterator> iteratori_traits;
- typedef std::iterator_traits<OutputIterator> iteratoro_traits;
- typedef typename iteratori_traits::iterator_category iteratori_category;
- typedef typename iteratoro_traits::iterator_category iteratoro_category;
-
- return transform1_switch(begin, end, result, unary_op,
- iteratori_category(), iteratoro_category());
- }
+ template<typename InputIterator, typename OutputIterator,
+ typename UnaryOperation>
+ inline OutputIterator
+ transform(InputIterator begin, InputIterator end, OutputIterator result,
+ UnaryOperation unary_op,
+ __gnu_parallel::parallelism parallelism_tag)
+ {
+ typedef std::iterator_traits<InputIterator> iteratori_traits;
+ typedef std::iterator_traits<OutputIterator> iteratoro_traits;
+ typedef typename iteratori_traits::iterator_category iteratori_category;
+ typedef typename iteratoro_traits::iterator_category iteratoro_category;
+
+ return transform1_switch(begin, end, result, unary_op,
+ iteratori_category(), iteratoro_category(),
+ parallelism_tag);
+ }
+
+ template<typename InputIterator, typename OutputIterator,
+ typename UnaryOperation>
+ inline OutputIterator
+ transform(InputIterator begin, InputIterator end, OutputIterator result,
+ UnaryOperation unary_op)
+ {
+ typedef std::iterator_traits<InputIterator> iteratori_traits;
+ typedef std::iterator_traits<OutputIterator> iteratoro_traits;
+ typedef typename iteratori_traits::iterator_category iteratori_category;
+ typedef typename iteratoro_traits::iterator_category iteratoro_category;
+
+ return transform1_switch(begin, end, result, unary_op,
+ iteratori_category(), iteratoro_category());
+ }
// Sequential fallback
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryOperation>
- inline OutputIterator
- transform(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- OutputIterator result, BinaryOperation binary_op,
- __gnu_parallel::sequential_tag)
- {
- return _GLIBCXX_STD_P::transform(begin1, end1, begin2, result, binary_op);
- }
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename BinaryOperation>
+ inline OutputIterator
+ transform(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, OutputIterator result,
+ BinaryOperation binary_op, __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::transform(begin1, end1,
+ begin2, result, binary_op); }
// Parallel binary transform for random access iterators.
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename RandomAccessIterator3, typename BinaryOperation>
- 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)
- {
- if (_GLIBCXX_PARALLEL_CONDITION((end1 - begin1) >= __gnu_parallel::Settings::transform_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
- {
- bool dummy = true;
- typedef __gnu_parallel::iterator_triple<RandomAccessIterator1, RandomAccessIterator2, RandomAccessIterator3, random_access_iterator_tag> ip;
- ip begin_triple(begin1, begin2, result), end_triple(end1, begin2 + (end1 - begin1), result + (end1 - begin1));
- __gnu_parallel::transform2_selector<ip> functionality;
- __gnu_parallel::for_each_template_random_access(begin_triple, end_triple, binary_op, functionality, __gnu_parallel::dummy_reduct(), dummy, dummy, -1, parallelism_tag);
- return functionality.finish_iterator;
- }
- else
- return transform(begin1, end1, begin2, result, binary_op,
- __gnu_parallel::sequential_tag());
- }
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename RandomAccessIterator3, typename BinaryOperation>
+ RandomAccessIterator3
+ transform2_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
+ RandomAccessIterator2 begin2,
+ RandomAccessIterator3 result, BinaryOperation binary_op,
+ random_access_iterator_tag, random_access_iterator_tag,
+ random_access_iterator_tag,
+ __gnu_parallel::parallelism parallelism_tag
+ = __gnu_parallel::parallel_balanced)
+ {
+ if (_GLIBCXX_PARALLEL_CONDITION((end1 - begin1)
+ >= __gnu_parallel::Settings::
+ transform_minimal_n
+ && __gnu_parallel::
+ is_parallel(parallelism_tag)))
+ {
+ bool dummy = true;
+ typedef __gnu_parallel::iterator_triple<RandomAccessIterator1,
+ RandomAccessIterator2, RandomAccessIterator3,
+ random_access_iterator_tag> ip;
+ ip begin_triple(begin1, begin2, result),
+ end_triple(end1, begin2 + (end1 - begin1),
+ result + (end1 - begin1));
+ __gnu_parallel::transform2_selector<ip> functionality;
+ __gnu_parallel::
+ for_each_template_random_access(begin_triple, end_triple,
+ binary_op, functionality,
+ __gnu_parallel::dummy_reduct(),
+ dummy, dummy, -1,
+ parallelism_tag);
+ return functionality.finish_iterator;
+ }
+ else
+ return transform(begin1, end1, begin2, result, binary_op,
+ __gnu_parallel::sequential_tag());
+ }
// Sequential fallback for input iterator case.
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryOperation, typename tag1, typename tag2, typename tag3>
- inline OutputIterator
- transform2_switch(InputIterator1 begin1, InputIterator1 end1,
- InputIterator2 begin2, OutputIterator result,
- BinaryOperation binary_op, tag1, tag2, tag3)
- {
- return transform(begin1, end1, begin2, result, binary_op,
- __gnu_parallel::sequential_tag());
- }
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename BinaryOperation,
+ typename tag1, typename tag2, typename tag3>
+ inline OutputIterator
+ transform2_switch(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, OutputIterator result,
+ BinaryOperation binary_op, tag1, tag2, tag3)
+ { return transform(begin1, end1, begin2, result, binary_op,
+ __gnu_parallel::sequential_tag()); }
// Public interface.
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryOperation>
- inline OutputIterator
- transform(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- OutputIterator result, BinaryOperation binary_op,
- __gnu_parallel::parallelism parallelism_tag)
- {
- typedef std::iterator_traits<InputIterator1> iteratori1_traits;
- typedef typename iteratori1_traits::iterator_category iteratori1_category;
- typedef std::iterator_traits<InputIterator2> iteratori2_traits;
- typedef typename iteratori2_traits::iterator_category iteratori2_category;
- typedef std::iterator_traits<OutputIterator> iteratoro_traits;
- typedef typename iteratoro_traits::iterator_category iteratoro_category;
-
- return transform2_switch(begin1, end1, begin2, result, binary_op,
- iteratori1_category(), iteratori2_category(),
- iteratoro_category(), parallelism_tag);
- }
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename BinaryOperation>
+ inline OutputIterator
+ transform(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, OutputIterator result,
+ BinaryOperation binary_op,
+ __gnu_parallel::parallelism parallelism_tag)
+ {
+ typedef std::iterator_traits<InputIterator1> iteratori1_traits;
+ typedef typename iteratori1_traits::iterator_category
+ iteratori1_category;
+ typedef std::iterator_traits<InputIterator2> iteratori2_traits;
+ typedef typename iteratori2_traits::iterator_category
+ iteratori2_category;
+ typedef std::iterator_traits<OutputIterator> iteratoro_traits;
+ typedef typename iteratoro_traits::iterator_category iteratoro_category;
+
+ return transform2_switch(begin1, end1, begin2, result, binary_op,
+ iteratori1_category(), iteratori2_category(),
+ iteratoro_category(), parallelism_tag);
+ }
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryOperation>
- inline OutputIterator
- transform(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- OutputIterator result, BinaryOperation binary_op)
- {
- typedef std::iterator_traits<InputIterator1> iteratori1_traits;
- typedef typename iteratori1_traits::iterator_category iteratori1_category;
- typedef std::iterator_traits<InputIterator2> iteratori2_traits;
- typedef typename iteratori2_traits::iterator_category iteratori2_category;
- typedef std::iterator_traits<OutputIterator> iteratoro_traits;
- typedef typename iteratoro_traits::iterator_category iteratoro_category;
-
- return transform2_switch(begin1, end1, begin2, result, binary_op,
- iteratori1_category(), iteratori2_category(),
- iteratoro_category());
- }
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename BinaryOperation>
+ inline OutputIterator
+ transform(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, OutputIterator result,
+ BinaryOperation binary_op)
+ {
+ typedef std::iterator_traits<InputIterator1> iteratori1_traits;
+ typedef typename iteratori1_traits::iterator_category
+ iteratori1_category;
+ typedef std::iterator_traits<InputIterator2> iteratori2_traits;
+ typedef typename iteratori2_traits::iterator_category
+ iteratori2_category;
+ typedef std::iterator_traits<OutputIterator> iteratoro_traits;
+ typedef typename iteratoro_traits::iterator_category iteratoro_category;
+
+ return transform2_switch(begin1, end1, begin2, result, binary_op,
+ iteratori1_category(), iteratori2_category(),
+ iteratoro_category());
+ }
// Sequential fallback
template<typename ForwardIterator, typename T>
- inline void
- replace(ForwardIterator begin, ForwardIterator end, const T& old_value,
- const T& new_value, __gnu_parallel::sequential_tag)
- { _GLIBCXX_STD_P::replace(begin, end, old_value, new_value); }
+ inline void
+ replace(ForwardIterator begin, ForwardIterator end, const T& old_value,
+ const T& new_value, __gnu_parallel::sequential_tag)
+ { _GLIBCXX_STD_P::replace(begin, end, old_value, new_value); }
// Sequential fallback for input iterator case
template<typename ForwardIterator, typename T, typename IteratorTag>
- void
- replace_switch(ForwardIterator begin, ForwardIterator end,
- const T& old_value, const T& new_value, IteratorTag)
- {
- replace(begin, end, old_value, new_value,
- __gnu_parallel::sequential_tag());
- }
+ inline void
+ replace_switch(ForwardIterator begin, ForwardIterator end,
+ const T& old_value, const T& new_value, IteratorTag)
+ { replace(begin, end, old_value, new_value,
+ __gnu_parallel::sequential_tag()); }
// Parallel replace for random access iterators
template<typename RandomAccessIterator, typename T>
- void
- replace_switch(RandomAccessIterator begin, RandomAccessIterator end,
- const T& old_value, const T& new_value,
- random_access_iterator_tag,
- __gnu_parallel::parallelism parallelism_tag
- = __gnu_parallel::parallel_balanced)
- {
- // XXX parallel version is where?
- replace(begin, end, old_value, new_value,
- __gnu_parallel::sequential_tag());
- }
+ inline void
+ replace_switch(RandomAccessIterator begin, RandomAccessIterator end,
+ const T& old_value, const T& new_value,
+ random_access_iterator_tag,
+ __gnu_parallel::parallelism parallelism_tag
+ = __gnu_parallel::parallel_balanced)
+ {
+ // XXX parallel version is where?
+ replace(begin, end, old_value, new_value,
+ __gnu_parallel::sequential_tag());
+ }
// Public interface
template<typename ForwardIterator, typename T>
- inline void
- replace(ForwardIterator begin, ForwardIterator end, const T& old_value,
- const T& new_value, __gnu_parallel::parallelism parallelism_tag)
- {
- typedef iterator_traits<ForwardIterator> traits_type;
- typedef typename traits_type::iterator_category iterator_category;
- replace_switch(begin, end, old_value, new_value, iterator_category(),
- parallelism_tag);
- }
+ inline void
+ replace(ForwardIterator begin, ForwardIterator end, const T& old_value,
+ const T& new_value, __gnu_parallel::parallelism parallelism_tag)
+ {
+ typedef iterator_traits<ForwardIterator> traits_type;
+ typedef typename traits_type::iterator_category iterator_category;
+ replace_switch(begin, end, old_value, new_value, iterator_category(),
+ parallelism_tag);
+ }
template<typename ForwardIterator, typename T>
- inline void
- replace(ForwardIterator begin, ForwardIterator end, const T& old_value,
- const T& new_value)
- {
- typedef iterator_traits<ForwardIterator> traits_type;
- typedef typename traits_type::iterator_category iterator_category;
- replace_switch(begin, end, old_value, new_value, iterator_category());
- }
+ inline void
+ replace(ForwardIterator begin, ForwardIterator end, const T& old_value,
+ const T& new_value)
+ {
+ typedef iterator_traits<ForwardIterator> traits_type;
+ typedef typename traits_type::iterator_category iterator_category;
+ replace_switch(begin, end, old_value, new_value, iterator_category());
+ }
// Sequential fallback
template<typename ForwardIterator, typename Predicate, typename T>
- inline void
- replace_if(ForwardIterator begin, ForwardIterator end, Predicate pred,
- const T& new_value, __gnu_parallel::sequential_tag)
- { _GLIBCXX_STD_P::replace_if(begin, end, pred, new_value); }
+ inline void
+ replace_if(ForwardIterator begin, ForwardIterator end, Predicate pred,
+ const T& new_value, __gnu_parallel::sequential_tag)
+ { _GLIBCXX_STD_P::replace_if(begin, end, pred, new_value); }
// Sequential fallback for input iterator case
- template<typename ForwardIterator, typename Predicate, typename T, typename IteratorTag>
- 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()); }
+ template<typename ForwardIterator, typename Predicate, typename T,
+ typename IteratorTag>
+ inline 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()); }
// Parallel algorithm for random access iterators.
template<typename RandomAccessIterator, typename Predicate, typename T>
- void
- replace_if_switch(RandomAccessIterator begin, RandomAccessIterator end,
- Predicate pred, const T& new_value,
- random_access_iterator_tag,
- __gnu_parallel::parallelism parallelism_tag
- = __gnu_parallel::parallel_balanced)
- {
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::replace_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
- {
- bool dummy;
- __gnu_parallel::replace_if_selector<RandomAccessIterator, Predicate, T> functionality(new_value);
- __gnu_parallel::for_each_template_random_access(begin, end, pred, functionality, __gnu_parallel::dummy_reduct(), true, dummy, -1, parallelism_tag);
- }
- else
- replace_if(begin, end, pred, new_value,
- __gnu_parallel::sequential_tag());
- }
+ 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)
+ {
+ if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::
+ sequence_index_t>(end - begin)
+ >= __gnu_parallel::Settings::
+ replace_minimal_n
+ && __gnu_parallel::
+ is_parallel(parallelism_tag)))
+ {
+ bool dummy;
+ __gnu_parallel::
+ replace_if_selector<RandomAccessIterator, Predicate, T>
+ functionality(new_value);
+ __gnu_parallel::
+ for_each_template_random_access(begin, end, pred,
+ functionality,
+ __gnu_parallel::dummy_reduct(),
+ true, dummy, -1, parallelism_tag);
+ }
+ else
+ replace_if(begin, end, pred, new_value,
+ __gnu_parallel::sequential_tag());
+ }
// Public interface.
template<typename ForwardIterator, typename Predicate, typename T>
- inline void
- replace_if(ForwardIterator begin, ForwardIterator end,
- Predicate pred, const T& new_value,
- __gnu_parallel::parallelism parallelism_tag)
- {
- typedef std::iterator_traits<ForwardIterator> iterator_traits;
- typedef typename iterator_traits::iterator_category iterator_category;
- replace_if_switch(begin, end, pred, new_value, iterator_category(),
- parallelism_tag);
- }
+ inline void
+ replace_if(ForwardIterator begin, ForwardIterator end,
+ Predicate pred, const T& new_value,
+ __gnu_parallel::parallelism parallelism_tag)
+ {
+ typedef std::iterator_traits<ForwardIterator> iterator_traits;
+ typedef typename iterator_traits::iterator_category iterator_category;
+ replace_if_switch(begin, end, pred, new_value, iterator_category(),
+ parallelism_tag);
+ }
template<typename ForwardIterator, typename Predicate, typename T>
- inline void
- replace_if(ForwardIterator begin, ForwardIterator end,
- Predicate pred, const T& new_value)
- {
- typedef std::iterator_traits<ForwardIterator> iterator_traits;
- typedef typename iterator_traits::iterator_category iterator_category;
- replace_if_switch(begin, end, pred, new_value, iterator_category());
- }
+ inline void
+ replace_if(ForwardIterator begin, ForwardIterator end,
+ Predicate pred, const T& new_value)
+ {
+ typedef std::iterator_traits<ForwardIterator> iterator_traits;
+ typedef typename iterator_traits::iterator_category iterator_category;
+ replace_if_switch(begin, end, pred, new_value, iterator_category());
+ }
// Sequential fallback
template<typename ForwardIterator, typename Generator>
- inline void
- generate(ForwardIterator begin, ForwardIterator end, Generator gen,
- __gnu_parallel::sequential_tag)
- { _GLIBCXX_STD_P::generate(begin, end, gen); }
+ inline void
+ generate(ForwardIterator begin, ForwardIterator end, Generator gen,
+ __gnu_parallel::sequential_tag)
+ { _GLIBCXX_STD_P::generate(begin, end, gen); }
// Sequential fallback for input iterator case.
template<typename ForwardIterator, typename Generator, typename IteratorTag>
- void
- generate_switch(ForwardIterator begin, ForwardIterator end, Generator gen,
- IteratorTag)
- { generate(begin, end, gen, __gnu_parallel::sequential_tag()); }
+ inline void
+ generate_switch(ForwardIterator begin, ForwardIterator end, Generator gen,
+ IteratorTag)
+ { generate(begin, end, gen, __gnu_parallel::sequential_tag()); }
// Parallel algorithm for random access iterators.
template<typename RandomAccessIterator, typename Generator>
- void
- generate_switch(RandomAccessIterator begin, RandomAccessIterator end,
- Generator gen, random_access_iterator_tag,
- __gnu_parallel::parallelism parallelism_tag
- = __gnu_parallel::parallel_balanced)
- {
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::generate_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
- {
- bool dummy;
- __gnu_parallel::generate_selector<RandomAccessIterator> functionality;
- __gnu_parallel::for_each_template_random_access(begin, end, gen, functionality, __gnu_parallel::dummy_reduct(), true, dummy, -1, parallelism_tag);
- }
- else
- generate(begin, end, gen, __gnu_parallel::sequential_tag());
- }
+ void
+ generate_switch(RandomAccessIterator begin, RandomAccessIterator end,
+ 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)))
+ {
+ bool dummy;
+ __gnu_parallel::generate_selector<RandomAccessIterator>
+ functionality;
+ __gnu_parallel::
+ for_each_template_random_access(begin, end, gen, functionality,
+ __gnu_parallel::dummy_reduct(),
+ true, dummy, -1, parallelism_tag);
+ }
+ else
+ generate(begin, end, gen, __gnu_parallel::sequential_tag());
+ }
// Public interface.
template<typename ForwardIterator, typename Generator>
- inline void
- generate(ForwardIterator begin, ForwardIterator end,
- Generator gen, __gnu_parallel::parallelism parallelism_tag)
- {
- typedef std::iterator_traits<ForwardIterator> iterator_traits;
- typedef typename iterator_traits::iterator_category iterator_category;
- generate_switch(begin, end, gen, iterator_category(), parallelism_tag);
- }
+ inline void
+ generate(ForwardIterator begin, ForwardIterator end,
+ Generator gen, __gnu_parallel::parallelism parallelism_tag)
+ {
+ typedef std::iterator_traits<ForwardIterator> iterator_traits;
+ typedef typename iterator_traits::iterator_category iterator_category;
+ generate_switch(begin, end, gen, iterator_category(), parallelism_tag);
+ }
template<typename ForwardIterator, typename Generator>
- inline void
- generate(ForwardIterator begin, ForwardIterator end, Generator gen)
- {
- typedef std::iterator_traits<ForwardIterator> iterator_traits;
- typedef typename iterator_traits::iterator_category iterator_category;
- generate_switch(begin, end, gen, iterator_category());
- }
+ inline void
+ generate(ForwardIterator begin, ForwardIterator end, Generator gen)
+ {
+ typedef std::iterator_traits<ForwardIterator> iterator_traits;
+ typedef typename iterator_traits::iterator_category iterator_category;
+ generate_switch(begin, end, gen, iterator_category());
+ }
// Sequential fallback.
template<typename OutputIterator, typename Size, typename Generator>
- inline OutputIterator
- generate_n(OutputIterator begin, Size n, Generator gen,
- __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::generate_n(begin, n, gen); }
+ inline OutputIterator
+ generate_n(OutputIterator begin, Size n, Generator gen,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::generate_n(begin, n, gen); }
// Sequential fallback for input iterator case.
- template<typename OutputIterator, typename Size, typename Generator, typename IteratorTag>
- OutputIterator
- generate_n_switch(OutputIterator begin, Size n, Generator gen, IteratorTag)
- { return generate_n(begin, n, gen, __gnu_parallel::sequential_tag()); }
+ template<typename OutputIterator, typename Size, typename Generator,
+ typename IteratorTag>
+ inline OutputIterator
+ generate_n_switch(OutputIterator begin, Size n, Generator gen, IteratorTag)
+ { return generate_n(begin, n, gen, __gnu_parallel::sequential_tag()); }
// Parallel algorithm for random access iterators.
template<typename RandomAccessIterator, typename Size, typename Generator>
- RandomAccessIterator
- generate_n_switch(RandomAccessIterator begin, Size n, Generator gen,
- random_access_iterator_tag,
- __gnu_parallel::parallelism parallelism_tag
- = __gnu_parallel::parallel_balanced)
- {
- // XXX parallel version is where?
- return generate_n(begin, n, gen, __gnu_parallel::sequential_tag());
- }
+ RandomAccessIterator
+ generate_n_switch(RandomAccessIterator begin, Size n, Generator gen,
+ random_access_iterator_tag,
+ __gnu_parallel::parallelism parallelism_tag
+ = __gnu_parallel::parallel_balanced)
+ {
+ // XXX parallel version is where?
+ return generate_n(begin, n, gen, __gnu_parallel::sequential_tag());
+ }
// Public interface.
template<typename OutputIterator, typename Size, typename Generator>
- inline OutputIterator
- generate_n(OutputIterator begin, Size n, Generator gen,
- __gnu_parallel::parallelism parallelism_tag)
- {
- typedef std::iterator_traits<OutputIterator> iterator_traits;
- typedef typename iterator_traits::iterator_category iterator_category;
- return generate_n_switch(begin, n, gen, iterator_category(),
- parallelism_tag);
- }
+ inline OutputIterator
+ generate_n(OutputIterator begin, Size n, Generator gen,
+ __gnu_parallel::parallelism parallelism_tag)
+ {
+ typedef std::iterator_traits<OutputIterator> iterator_traits;
+ typedef typename iterator_traits::iterator_category iterator_category;
+ return generate_n_switch(begin, n, gen, iterator_category(),
+ parallelism_tag);
+ }
template<typename OutputIterator, typename Size, typename Generator>
- inline OutputIterator
- generate_n(OutputIterator begin, Size n, Generator gen)
- {
- typedef std::iterator_traits<OutputIterator> iterator_traits;
- typedef typename iterator_traits::iterator_category iterator_category;
- return generate_n_switch(begin, n, gen, iterator_category());
- }
+ inline OutputIterator
+ generate_n(OutputIterator begin, Size n, Generator gen)
+ {
+ typedef std::iterator_traits<OutputIterator> iterator_traits;
+ typedef typename iterator_traits::iterator_category iterator_category;
+ return generate_n_switch(begin, n, gen, iterator_category());
+ }
// Sequential fallback.
template<typename RandomAccessIterator>
- inline void
- random_shuffle(RandomAccessIterator begin, RandomAccessIterator end,
- __gnu_parallel::sequential_tag)
- { _GLIBCXX_STD_P::random_shuffle(begin, end); }
+ inline void
+ random_shuffle(RandomAccessIterator begin, RandomAccessIterator end,
+ __gnu_parallel::sequential_tag)
+ { _GLIBCXX_STD_P::random_shuffle(begin, end); }
// Sequential fallback.
template<typename RandomAccessIterator, typename RandomNumberGenerator>
- inline void
- random_shuffle(RandomAccessIterator begin, RandomAccessIterator end,
- RandomNumberGenerator& rand, __gnu_parallel::sequential_tag)
- { _GLIBCXX_STD_P::random_shuffle(begin, end, rand); }
+ inline void
+ random_shuffle(RandomAccessIterator begin, RandomAccessIterator end,
+ RandomNumberGenerator& rand, __gnu_parallel::sequential_tag)
+ { _GLIBCXX_STD_P::random_shuffle(begin, end, rand); }
/** @brief Functor wrapper for std::rand(). */
template<typename must_be_int = int>
- struct c_rand_number
- {
- inline int operator()(int limit)
- { return rand() % limit; }
- };
+ struct c_rand_number
+ {
+ int
+ operator()(int limit)
+ { return rand() % limit; }
+ };
// Fill in random number generator.
template<typename RandomAccessIterator>
- inline void
- random_shuffle(RandomAccessIterator begin, RandomAccessIterator end)
- {
- c_rand_number<> r;
- // Parallelization still possible.
- random_shuffle(begin, end, r);
- }
+ inline void
+ random_shuffle(RandomAccessIterator begin, RandomAccessIterator end)
+ {
+ c_rand_number<> r;
+ // Parallelization still possible.
+ random_shuffle(begin, end, r);
+ }
// Parallel algorithm for random access iterators.
template<typename RandomAccessIterator, typename RandomNumberGenerator>
- void
- random_shuffle(RandomAccessIterator begin, RandomAccessIterator end,
- 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))
- __gnu_parallel::parallel_random_shuffle(begin, end, rand);
- else
- __gnu_parallel::sequential_random_shuffle(begin, end, rand);
- }
+ void
+ random_shuffle(RandomAccessIterator begin, RandomAccessIterator end,
+ 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))
+ __gnu_parallel::parallel_random_shuffle(begin, end, rand);
+ else
+ __gnu_parallel::sequential_random_shuffle(begin, end, rand);
+ }
// Sequential fallback.
template<typename ForwardIterator, typename Predicate>
- inline ForwardIterator
- partition(ForwardIterator begin, ForwardIterator end, Predicate pred, __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::partition(begin, end, pred); }
+ inline ForwardIterator
+ partition(ForwardIterator begin, ForwardIterator end,
+ Predicate pred, __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::partition(begin, end, pred); }
// Sequential fallback for input iterator case.
template<typename ForwardIterator, typename Predicate, typename IteratorTag>
- inline ForwardIterator
- partition_switch(ForwardIterator begin, ForwardIterator end, Predicate pred, IteratorTag)
- { return partition(begin, end, pred, __gnu_parallel::sequential_tag()); }
+ inline ForwardIterator
+ partition_switch(ForwardIterator begin, ForwardIterator end,
+ Predicate pred, IteratorTag)
+ { return partition(begin, end, pred, __gnu_parallel::sequential_tag()); }
// Parallel algorithm for random access iterators.
template<typename RandomAccessIterator, typename Predicate>
- RandomAccessIterator
- 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))
- {
- typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_type;
- difference_type middle = __gnu_parallel::parallel_partition(begin, end, pred, __gnu_parallel::get_max_threads());
- return begin + middle;
- }
- else
- return partition(begin, end, pred, __gnu_parallel::sequential_tag());
- }
+ RandomAccessIterator
+ 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))
+ {
+ typedef typename std::iterator_traits<RandomAccessIterator>::
+ difference_type difference_type;
+ difference_type middle = __gnu_parallel::
+ parallel_partition(begin, end, pred,
+ __gnu_parallel::get_max_threads());
+ return begin + middle;
+ }
+ else
+ return partition(begin, end, pred, __gnu_parallel::sequential_tag());
+ }
// Public interface.
template<typename ForwardIterator, typename Predicate>
- inline ForwardIterator
- partition(ForwardIterator begin, ForwardIterator end, Predicate pred)
- {
- typedef iterator_traits<ForwardIterator> traits_type;
- typedef typename traits_type::iterator_category iterator_category;
- return partition_switch(begin, end, pred, iterator_category());
- }
+ inline ForwardIterator
+ partition(ForwardIterator begin, ForwardIterator end, Predicate pred)
+ {
+ typedef iterator_traits<ForwardIterator> traits_type;
+ typedef typename traits_type::iterator_category iterator_category;
+ return partition_switch(begin, end, pred, iterator_category());
+ }
// Sequential fallback
template<typename RandomAccessIterator>
- inline void
- sort(RandomAccessIterator begin, RandomAccessIterator end,
- __gnu_parallel::sequential_tag)
- { _GLIBCXX_STD_P::sort(begin, end); }
+ inline void
+ sort(RandomAccessIterator begin, RandomAccessIterator end,
+ __gnu_parallel::sequential_tag)
+ { _GLIBCXX_STD_P::sort(begin, end); }
// Sequential fallback
template<typename RandomAccessIterator, typename Comparator>
- inline void
- sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp,
- __gnu_parallel::sequential_tag)
- { _GLIBCXX_STD_P::sort<RandomAccessIterator, Comparator>(begin, end, comp); }
+ inline void
+ sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp,
+ __gnu_parallel::sequential_tag)
+ { _GLIBCXX_STD_P::sort<RandomAccessIterator, Comparator>(begin, end,
+ comp); }
// Public interface, insert default comparator
template<typename RandomAccessIterator>
- inline void
- sort(RandomAccessIterator begin, RandomAccessIterator end)
- {
- typedef iterator_traits<RandomAccessIterator> traits_type;
- typedef typename traits_type::value_type value_type;
- sort(begin, end, std::less<value_type>());
- }
+ inline void
+ sort(RandomAccessIterator begin, RandomAccessIterator end)
+ {
+ typedef iterator_traits<RandomAccessIterator> traits_type;
+ typedef typename traits_type::value_type value_type;
+ sort(begin, end, std::less<value_type>());
+ }
template<typename RandomAccessIterator, typename Comparator>
- void
- sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp)
- {
- typedef iterator_traits<RandomAccessIterator> traits_type;
- typedef typename traits_type::value_type value_type;
-
- 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());
- }
- }
+ void
+ sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp)
+ {
+ typedef iterator_traits<RandomAccessIterator> traits_type;
+ typedef typename traits_type::value_type value_type;
+
+ if (begin != end)
+ {
+ if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::
+ sequence_index_t>(end - begin)
+ >= __gnu_parallel::Settings::
+ sort_minimal_n))
+ __gnu_parallel::parallel_sort(begin, end, comp, false);
+ else
+ sort(begin, end, comp, __gnu_parallel::sequential_tag());
+ }
+ }
// Sequential fallback.
template<typename RandomAccessIterator>
- inline void
- stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
- __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::stable_sort(begin, end); }
+ inline void
+ stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::stable_sort(begin, end); }
// Sequential fallback.
template<typename RandomAccessIterator, typename Comparator>
- inline void
- stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
- Comparator comp, __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::stable_sort(begin, end, comp); }
+ inline void
+ stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
+ Comparator comp, __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::stable_sort(begin, end, comp); }
template<typename RandomAccessIterator>
- void
- stable_sort(RandomAccessIterator begin, RandomAccessIterator end)
- {
- typedef iterator_traits<RandomAccessIterator> traits_type;
- typedef typename traits_type::value_type value_type;
- stable_sort(begin, end, std::less<value_type>());
- }
+ inline void
+ stable_sort(RandomAccessIterator begin, RandomAccessIterator end)
+ {
+ typedef iterator_traits<RandomAccessIterator> traits_type;
+ typedef typename traits_type::value_type value_type;
+ stable_sort(begin, end, std::less<value_type>());
+ }
// Parallel algorithm for random access iterators
template<typename RandomAccessIterator, typename Comparator>
- void
- stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
- Comparator comp)
- {
- if (begin != end)
- {
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::sort_minimal_n))
- __gnu_parallel::parallel_sort(begin, end, comp, true);
- else
- stable_sort(begin, end, comp, __gnu_parallel::sequential_tag());
- }
- }
+ void
+ stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
+ Comparator comp)
+ {
+ 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());
+ }
+ }
// Sequential fallback
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
- inline OutputIterator
- merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- InputIterator2 end2, OutputIterator result,
- __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result); }
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator>
+ inline OutputIterator
+ merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
+ InputIterator2 end2, OutputIterator result,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result); }
// Sequential fallback
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Comparator>
- inline OutputIterator
- merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- InputIterator2 end2, OutputIterator result, Comparator comp,
- __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result, comp); }
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename Comparator>
+ inline OutputIterator
+ merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
+ InputIterator2 end2, OutputIterator result, Comparator comp,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result, comp); }
// Sequential fallback for input iterator case
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Comparator, typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
- inline OutputIterator
- 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); }
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename Comparator,
+ typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
+ inline OutputIterator
+ merge_switch(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator result, Comparator comp,
+ IteratorTag1, IteratorTag2, IteratorTag3)
+ { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2,
+ result, comp); }
// Parallel algorithm for random access iterators
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Comparator>
- 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)
- {
- 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);
- else
- return __gnu_parallel::merge_advance(begin1, end1, begin2, end2, result,
- (end1 - begin1) + (end2 - begin2),
- comp);
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename Comparator>
+ OutputIterator
+ merge_switch(InputIterator1 begin1, InputIterator1 end1,
+ InputIterator2 begin2, InputIterator2 end2,
+ OutputIterator result, Comparator comp,
+ random_access_iterator_tag, random_access_iterator_tag,
+ random_access_iterator_tag)
+ {
+ 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);
+ else
+ return __gnu_parallel::merge_advance(begin1, end1, begin2, end2,
+ result, (end1 - begin1)
+ + (end2 - begin2), comp);
}
// Public interface
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Comparator>
- inline OutputIterator
- merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- InputIterator2 end2, OutputIterator result, Comparator comp)
- {
- typedef typename iterator_traits<InputIterator1>::value_type value_type;
-
- typedef std::iterator_traits<InputIterator1> iteratori1_traits;
- typedef std::iterator_traits<InputIterator2> iteratori2_traits;
- typedef std::iterator_traits<OutputIterator> iteratoro_traits;
- typedef typename iteratori1_traits::iterator_category iteratori1_category;
- typedef typename iteratori2_traits::iterator_category iteratori2_category;
- typedef typename iteratoro_traits::iterator_category iteratoro_category;
-
- return merge_switch(begin1, end1, begin2, end2, result, comp,
- iteratori1_category(), iteratori2_category(),
- iteratoro_category());
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator, typename Comparator>
+ inline OutputIterator
+ merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
+ InputIterator2 end2, OutputIterator result, Comparator comp)
+ {
+ typedef typename iterator_traits<InputIterator1>::value_type value_type;
+
+ typedef std::iterator_traits<InputIterator1> iteratori1_traits;
+ typedef std::iterator_traits<InputIterator2> iteratori2_traits;
+ typedef std::iterator_traits<OutputIterator> iteratoro_traits;
+ typedef typename iteratori1_traits::iterator_category
+ iteratori1_category;
+ typedef typename iteratori2_traits::iterator_category
+ iteratori2_category;
+ typedef typename iteratoro_traits::iterator_category iteratoro_category;
+
+ return merge_switch(begin1, end1, begin2, end2, result, comp,
+ iteratori1_category(), iteratori2_category(),
+ iteratoro_category());
}
// Public interface, insert default comparator
- template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
- inline OutputIterator
- merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
- InputIterator2 end2, OutputIterator result)
- {
- typedef std::iterator_traits<InputIterator1> iterator1_traits;
- typedef std::iterator_traits<InputIterator2> iterator2_traits;
- typedef typename iterator1_traits::value_type value1_type;
- typedef typename iterator2_traits::value_type value2_type;
-
- return merge(begin1, end1, begin2, end2, result,
- __gnu_parallel::less<value1_type, value2_type>());
- }
+ template<typename InputIterator1, typename InputIterator2,
+ typename OutputIterator>
+ inline OutputIterator
+ merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
+ InputIterator2 end2, OutputIterator result)
+ {
+ typedef std::iterator_traits<InputIterator1> iterator1_traits;
+ typedef std::iterator_traits<InputIterator2> iterator2_traits;
+ typedef typename iterator1_traits::value_type value1_type;
+ typedef typename iterator2_traits::value_type value2_type;
+
+ return merge(begin1, end1, begin2, end2, result,
+ __gnu_parallel::less<value1_type, value2_type>());
+ }
// Sequential fallback
template<typename RandomAccessIterator>
- inline void
- nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
- RandomAccessIterator end, __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::nth_element(begin, nth, end); }
+ inline void
+ nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
+ RandomAccessIterator end, __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::nth_element(begin, nth, end); }
// Sequential fallback
template<typename RandomAccessIterator, typename Comparator>
- void
- nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
- RandomAccessIterator end, Comparator comp,
+ inline void
+ nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
+ RandomAccessIterator end, Comparator comp,
__gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::nth_element(begin, nth, end, comp); }
+ { return _GLIBCXX_STD_P::nth_element(begin, nth, end, comp); }
// Public interface
template<typename RandomAccessIterator, typename Comparator>
- inline void
- nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
- RandomAccessIterator end, Comparator comp)
- {
- 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());
- }
+ inline void
+ nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
+ RandomAccessIterator end, Comparator comp)
+ {
+ if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::
+ sequence_index_t>(end - begin)
+ >= __gnu_parallel::Settings::
+ nth_element_minimal_n))
+ __gnu_parallel::parallel_nth_element(begin, nth, end, comp);
+ else
+ nth_element(begin, nth, end, comp, __gnu_parallel::sequential_tag());
+ }
// Public interface, insert default comparator
template<typename RandomAccessIterator>
- void
- nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
- RandomAccessIterator end)
- {
- typedef iterator_traits<RandomAccessIterator> traits_type;
- typedef typename traits_type::value_type value_type;
- nth_element(begin, nth, end, std::less<value_type>());
- }
+ inline void
+ nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
+ RandomAccessIterator end)
+ {
+ typedef iterator_traits<RandomAccessIterator> traits_type;
+ typedef typename traits_type::value_type value_type;
+ nth_element(begin, nth, end, std::less<value_type>());
+ }
// Sequential fallback
template<typename RandomAccessIterator, typename _Compare>
- void
- partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
- RandomAccessIterator end, _Compare comp,
- __gnu_parallel::sequential_tag)
- { _GLIBCXX_STD_P::partial_sort(begin, middle, end, comp); }
+ inline void
+ partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
+ RandomAccessIterator end, _Compare comp,
+ __gnu_parallel::sequential_tag)
+ { _GLIBCXX_STD_P::partial_sort(begin, middle, end, comp); }
// Sequential fallback
template<typename RandomAccessIterator>
@@ -1674,186 +1982,215 @@
// Public interface, parallel algorithm for random access iterators
template<typename RandomAccessIterator, typename _Compare>
- void
- partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
- RandomAccessIterator end, _Compare comp)
- {
- 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());
- }
+ void
+ partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
+ RandomAccessIterator end, _Compare comp)
+ {
+ if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::
+ sequence_index_t>(end - begin)
+ >= __gnu_parallel::Settings::
+ partial_sort_minimal_n))
+ __gnu_parallel::parallel_partial_sort(begin, middle, end, comp);
+ else
+ partial_sort(begin, middle, end, comp,
+ __gnu_parallel::sequential_tag());
+ }
// Public interface, insert default comparator
template<typename RandomAccessIterator>
- void
- partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
- RandomAccessIterator end)
- {
- typedef iterator_traits<RandomAccessIterator> traits_type;
- typedef typename traits_type::value_type value_type;
- partial_sort(begin, middle, end, std::less<value_type>());
- }
+ inline void
+ partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
+ RandomAccessIterator end)
+ {
+ typedef iterator_traits<RandomAccessIterator> traits_type;
+ typedef typename traits_type::value_type value_type;
+ partial_sort(begin, middle, end, std::less<value_type>());
+ }
// Sequential fallback
template<typename ForwardIterator>
- inline ForwardIterator
- max_element(ForwardIterator begin, ForwardIterator end,
- __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::max_element(begin, end); }
+ inline ForwardIterator
+ max_element(ForwardIterator begin, ForwardIterator end,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::max_element(begin, end); }
// Sequential fallback
template<typename ForwardIterator, typename Comparator>
- inline ForwardIterator
- max_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
- __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::max_element(begin, end, comp); }
+ inline ForwardIterator
+ max_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::max_element(begin, end, comp); }
// Sequential fallback for input iterator case
template<typename ForwardIterator, typename Comparator, typename IteratorTag>
- ForwardIterator
- max_element_switch(ForwardIterator begin, ForwardIterator end,
- Comparator comp, IteratorTag)
- { return max_element(begin, end, comp, __gnu_parallel::sequential_tag()); }
+ inline ForwardIterator
+ max_element_switch(ForwardIterator begin, ForwardIterator end,
+ Comparator comp, IteratorTag)
+ { return max_element(begin, end, comp, __gnu_parallel::sequential_tag()); }
// Parallel algorithm for random access iterators
template<typename RandomAccessIterator, typename Comparator>
- RandomAccessIterator
- max_element_switch(RandomAccessIterator begin, RandomAccessIterator end,
- Comparator comp, random_access_iterator_tag,
- __gnu_parallel::parallelism parallelism_tag
- = __gnu_parallel::parallel_balanced)
- {
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::max_element_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
- {
- RandomAccessIterator res(begin);
- __gnu_parallel::identity_selector<RandomAccessIterator> functionality;
- __gnu_parallel::for_each_template_random_access(begin, end, __gnu_parallel::nothing(), functionality, __gnu_parallel::max_element_reduct<Comparator, RandomAccessIterator>(comp), res, res, -1, parallelism_tag);
- return res;
- }
- else
- return max_element(begin, end, comp, __gnu_parallel::sequential_tag());
- }
+ RandomAccessIterator
+ max_element_switch(RandomAccessIterator begin, RandomAccessIterator end,
+ 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)))
+ {
+ RandomAccessIterator res(begin);
+ __gnu_parallel::identity_selector<RandomAccessIterator>
+ functionality;
+ __gnu_parallel::
+ for_each_template_random_access(begin, end,
+ __gnu_parallel::nothing(),
+ functionality,
+ __gnu_parallel::
+ max_element_reduct<Comparator,
+ RandomAccessIterator>(comp),
+ res, res, -1, parallelism_tag);
+ return res;
+ }
+ else
+ return max_element(begin, end, comp, __gnu_parallel::sequential_tag());
+ }
// Public interface, insert default comparator
template<typename ForwardIterator>
- inline ForwardIterator
- max_element(ForwardIterator begin, ForwardIterator end,
- __gnu_parallel::parallelism parallelism_tag)
- {
- typedef typename iterator_traits<ForwardIterator>::value_type value_type;
- return max_element(begin, end, std::less<value_type>(), parallelism_tag);
- }
+ inline ForwardIterator
+ max_element(ForwardIterator begin, ForwardIterator end,
+ __gnu_parallel::parallelism parallelism_tag)
+ {
+ typedef typename iterator_traits<ForwardIterator>::value_type value_type;
+ return max_element(begin, end, std::less<value_type>(), parallelism_tag);
+ }
template<typename ForwardIterator>
- inline ForwardIterator
- max_element(ForwardIterator begin, ForwardIterator end)
- {
- typedef typename iterator_traits<ForwardIterator>::value_type value_type;
- return max_element(begin, end, std::less<value_type>());
- }
+ inline ForwardIterator
+ max_element(ForwardIterator begin, ForwardIterator end)
+ {
+ typedef typename iterator_traits<ForwardIterator>::value_type value_type;
+ return max_element(begin, end, std::less<value_type>());
+ }
// Public interface
template<typename ForwardIterator, typename Comparator>
- inline ForwardIterator
- max_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
- __gnu_parallel::parallelism parallelism_tag)
- {
- typedef iterator_traits<ForwardIterator> traits_type;
- typedef typename traits_type::iterator_category iterator_category;
- return max_element_switch(begin, end, comp, iterator_category(),
- parallelism_tag);
- }
+ inline ForwardIterator
+ max_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
+ __gnu_parallel::parallelism parallelism_tag)
+ {
+ typedef iterator_traits<ForwardIterator> traits_type;
+ typedef typename traits_type::iterator_category iterator_category;
+ return max_element_switch(begin, end, comp, iterator_category(),
+ parallelism_tag);
+ }
template<typename ForwardIterator, typename Comparator>
- inline ForwardIterator
- max_element(ForwardIterator begin, ForwardIterator end, Comparator comp)
- {
- typedef iterator_traits<ForwardIterator> traits_type;
- typedef typename traits_type::iterator_category iterator_category;
- return max_element_switch(begin, end, comp, iterator_category());
- }
+ inline ForwardIterator
+ max_element(ForwardIterator begin, ForwardIterator end, Comparator comp)
+ {
+ typedef iterator_traits<ForwardIterator> traits_type;
+ typedef typename traits_type::iterator_category iterator_category;
+ return max_element_switch(begin, end, comp, iterator_category());
+ }
// Sequential fallback
template<typename ForwardIterator>
- inline
- ForwardIterator
- min_element(ForwardIterator begin, ForwardIterator end,
- __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::min_element(begin, end); }
+ inline ForwardIterator
+ min_element(ForwardIterator begin, ForwardIterator end,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::min_element(begin, end); }
// Sequential fallback
template<typename ForwardIterator, typename Comparator>
- inline ForwardIterator
- min_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
- __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_P::min_element(begin, end, comp); }
+ inline ForwardIterator
+ min_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
+ __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_P::min_element(begin, end, comp); }
// Sequential fallback for input iterator case
template<typename ForwardIterator, typename Comparator, typename IteratorTag>
- ForwardIterator
- min_element_switch(ForwardIterator begin, ForwardIterator end,
- Comparator comp, IteratorTag)
- { return min_element(begin, end, comp, __gnu_parallel::sequential_tag()); }
+ inline ForwardIterator
+ min_element_switch(ForwardIterator begin, ForwardIterator end,
+ Comparator comp, IteratorTag)
+ { return min_element(begin, end, comp, __gnu_parallel::sequential_tag()); }
// Parallel algorithm for random access iterators
template<typename RandomAccessIterator, typename Comparator>
- RandomAccessIterator
- min_element_switch(RandomAccessIterator begin, RandomAccessIterator end,
- Comparator comp, random_access_iterator_tag,
- __gnu_parallel::parallelism parallelism_tag
- = __gnu_parallel::parallel_balanced)
- {
- if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::min_element_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
- {
- RandomAccessIterator res(begin);
- __gnu_parallel::identity_selector<RandomAccessIterator> functionality;
- __gnu_parallel::for_each_template_random_access(begin, end, __gnu_parallel::nothing(), functionality, __gnu_parallel::min_element_reduct<Comparator, RandomAccessIterator>(comp), res, res, -1, parallelism_tag);
- return res;
- }
- else
- return min_element(begin, end, comp, __gnu_parallel::sequential_tag());
- }
+ RandomAccessIterator
+ min_element_switch(RandomAccessIterator begin, RandomAccessIterator end,
+ 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)))
+ {
+ RandomAccessIterator res(begin);
+ __gnu_parallel::identity_selector<RandomAccessIterator>
+ functionality;
+ __gnu_parallel::
+ for_each_template_random_access(begin, end,
+ __gnu_parallel::nothing(),
+ functionality,
+ __gnu_parallel::
+ min_element_reduct<Comparator,
+ RandomAccessIterator>(comp),
+ res, res, -1, parallelism_tag);
+ return res;
+ }
+ else
+ return min_element(begin, end, comp, __gnu_parallel::sequential_tag());
+ }
// Public interface, insert default comparator
template<typename ForwardIterator>
- inline ForwardIterator
- min_element(ForwardIterator begin, ForwardIterator end,
- __gnu_parallel::parallelism parallelism_tag)
- {
- typedef typename iterator_traits<ForwardIterator>::value_type value_type;
- return min_element(begin, end, std::less<value_type>(), parallelism_tag);
- }
+ inline ForwardIterator
+ min_element(ForwardIterator begin, ForwardIterator end,
+ __gnu_parallel::parallelism parallelism_tag)
+ {
+ typedef typename iterator_traits<ForwardIterator>::value_type value_type;
+ return min_element(begin, end, std::less<value_type>(), parallelism_tag);
+ }
template<typename ForwardIterator>
- inline ForwardIterator
- min_element(ForwardIterator begin, ForwardIterator end)
- {
- typedef typename iterator_traits<ForwardIterator>::value_type value_type;
- return min_element(begin, end, std::less<value_type>());
- }
+ inline ForwardIterator
+ min_element(ForwardIterator begin, ForwardIterator end)
+ {
+ typedef typename iterator_traits<ForwardIterator>::value_type value_type;
+ return min_element(begin, end, std::less<value_type>());
+ }
// Public interface
template<typename ForwardIterator, typename Comparator>
- inline ForwardIterator
- min_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
- __gnu_parallel::parallelism parallelism_tag)
- {
- typedef iterator_traits<ForwardIterator> traits_type;
- typedef typename traits_type::iterator_category iterator_category;
- return min_element_switch(begin, end, comp, iterator_category(),
- parallelism_tag);
- }
+ inline ForwardIterator
+ min_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
+ __gnu_parallel::parallelism parallelism_tag)
+ {
+ typedef iterator_traits<ForwardIterator> traits_type;
+ typedef typename traits_type::iterator_category iterator_category;
+ return min_element_switch(begin, end, comp, iterator_category(),
+ parallelism_tag);
+ }
template<typename ForwardIterator, typename Comparator>
- inline ForwardIterator
- min_element(ForwardIterator begin, ForwardIterator end, Comparator comp)
- {
- typedef iterator_traits<ForwardIterator> traits_type;
- typedef typename traits_type::iterator_category iterator_category;
- return min_element_switch(begin, end, comp, iterator_category());
- }
+ inline ForwardIterator
+ min_element(ForwardIterator begin, ForwardIterator end, Comparator comp)
+ {
+ typedef iterator_traits<ForwardIterator> traits_type;
+ typedef typename traits_type::iterator_category iterator_category;
+ return min_element_switch(begin, end, comp, iterator_category());
+ }
} // end namespace
} // end namespace
Index: include/parallel/checkers.h
===================================================================
--- include/parallel/checkers.h (revision 131429)
+++ include/parallel/checkers.h (working copy)
@@ -1,6 +1,6 @@
// -*- C++ -*-
-// Copyright (C) 2007 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
@@ -53,28 +53,32 @@
*/
// XXX Comparator default template argument
template<typename InputIterator, typename Comparator>
- bool
- is_sorted(InputIterator begin, InputIterator end, Comparator comp = std::less<typename std::iterator_traits<InputIterator>::value_type>())
- {
- if (begin == end)
- return true;
-
- InputIterator current(begin), recent(begin);
-
- unsigned long long position = 1;
- for (current++; current != end; current++)
- {
- if (comp(*current, *recent))
- {
- printf("is_sorted: check failed before position %i.\n", position);
- return false;
- }
- recent = current;
- position++;
- }
+ bool
+ is_sorted(InputIterator begin, InputIterator end,
+ Comparator comp
+ = std::less<typename std::iterator_traits<InputIterator>::
+ value_type>())
+ {
+ if (begin == end)
+ return true;
+
+ InputIterator current(begin), recent(begin);
+
+ unsigned long long position = 1;
+ for (current++; current != end; current++)
+ {
+ if (comp(*current, *recent))
+ {
+ printf("is_sorted: check failed before position %i.\n",
+ position);
+ return false;
+ }
+ recent = current;
+ position++;
+ }
- return true;
- }
+ return true;
+ }
/**
* @brief Check whether @c [begin, @c end) is sorted according to @c comp.
@@ -87,30 +91,35 @@
*/
// XXX Comparator default template argument
template<typename InputIterator, typename Comparator>
- bool
- is_sorted_failure(InputIterator begin, InputIterator end, InputIterator& first_failure, Comparator comp = std::less<typename std::iterator_traits<InputIterator>::value_type>())
- {
- if (begin == end)
- return true;
-
- InputIterator current(begin), recent(begin);
+ bool
+ is_sorted_failure(InputIterator begin, InputIterator end,
+ InputIterator& first_failure,
+ Comparator comp
+ = std::less<typename std::iterator_traits<InputIterator>::
+ value_type>())
+ {
+ if (begin == end)
+ return true;
+
+ InputIterator current(begin), recent(begin);
+
+ unsigned long long position = 1;
+ 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++;
+ }
- unsigned long long position = 1;
- 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++;
- }
-
- first_failure = end;
- return true;
- }
+ first_failure = end;
+ return true;
+ }
/**
* @brief Check whether @c [begin, @c end) is sorted according to @c comp.
@@ -121,28 +130,31 @@
* @return @c true if sorted, @c false otherwise.
*/
template<typename InputIterator, typename Comparator>
- bool
- // XXX Comparator default template argument
- is_sorted_print_failures(InputIterator begin, InputIterator end, Comparator comp = std::less<typename std::iterator_traits<InputIterator>::value_type>())
- {
- if (begin == end)
- return true;
-
- InputIterator recent(begin);
- bool ok = true;
-
- 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;
- }
- return ok;
- }
+ bool
+ // XXX Comparator default template argument
+ is_sorted_print_failures(InputIterator begin, InputIterator end,
+ Comparator comp
+ = std::less<typename std::iterator_traits
+ <InputIterator>::value_type>())
+ {
+ if (begin == end)
+ return true;
+
+ InputIterator recent(begin);
+ bool ok = true;
+
+ 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;
+ }
+ return ok;
+ }
}
#endif