33 #ifndef _GLIBCXX_PARALLEL_LIST_PARTITION_H
34 #define _GLIBCXX_PARALLEL_LIST_PARTITION_H 1
39 namespace __gnu_parallel
48 template<
typename InputIterator>
51 size_t& count_to_two,
size_t& range_length,
52 const bool make_twice)
55 if (not make_twice or count_to_two < 2)
56 shrink(os_starts, count_to_two, range_length);
59 os_starts.
resize((os_starts.
size() - 1) * 2 + 1);
68 template<
typename InputIterator>
73 for (
typename std::vector<InputIterator>::size_type i = 0;
74 i <= (os_starts.
size() / 2); ++i)
75 os_starts[i] = os_starts[i * 2];
98 template<
typename InputIterator,
typename FunctorType>
101 InputIterator* starts,
size_t* lengths,
const int num_parts,
102 FunctorType& f,
int oversampling = 0)
104 bool make_twice =
false;
107 if (oversampling == 0)
116 InputIterator prev = begin, it = begin;
117 size_t dist_limit = 0, dist = 0;
118 size_t cur = 1, next = 1;
119 size_t range_length = 1;
120 size_t count_to_two = 0;
124 for (; cur < os_starts.
size() and it != end; ++cur)
126 for (dist_limit += range_length;
127 dist < dist_limit and it != end; ++dist)
141 next = os_starts.
size() / 2 + 1;
147 size_t size_part = (cur - 1) / num_parts;
148 int size_greater =
static_cast<int>((cur - 1) % num_parts);
149 starts[0] = os_starts[0];
154 for (
int i = 1; i < (num_parts + 1 - size_greater); ++i)
156 lengths[i - 1] = size_part * range_length;
158 starts[i] = os_starts[index];
162 for (
int i = num_parts + 1 - size_greater; i <= num_parts; ++i)
164 lengths[i - 1] = (size_part+1) * range_length;
165 index += (size_part+1);
166 starts[i] = os_starts[index];
170 lengths[num_parts - 1] -= (dist_limit - dist);
void shrink_and_double(std::vector< InputIterator > &os_starts, size_t &count_to_two, size_t &range_length, const bool make_twice)
Shrinks and doubles the ranges.
void resize(size_type __new_size, value_type __x=value_type())
Resizes the vector to the specified number of elements.
A standard container which offers fixed time access to individual elements in any order...
void shrink(std::vector< InputIterator > &os_starts, size_t &count_to_two, size_t &range_length)
Combines two ranges into one and thus halves the number of ranges.
size_t list_partition(const InputIterator begin, const InputIterator end, InputIterator *starts, size_t *lengths, const int num_parts, FunctorType &f, int oversampling=0)
Splits a sequence given by input iterators into parts of almost equal size.
End-user include file. Provides advanced settings and tuning options. This file is a GNU parallel ext...