33 #ifndef _GLIBCXX_PARALLEL_PARTITION_H
34 #define _GLIBCXX_PARALLEL_PARTITION_H 1
43 #define _GLIBCXX_VOLATILE volatile
45 namespace __gnu_parallel
53 template<
typename RandomAccessIterator,
typename Predicate>
54 typename std::iterator_traits<RandomAccessIterator>::difference_type
59 typedef typename traits_type::value_type value_type;
60 typedef typename traits_type::difference_type difference_type;
62 difference_type n = end - begin;
73 bool* reserved_left = NULL, * reserved_right = NULL;
77 omp_lock_t result_lock;
78 omp_init_lock(&result_lock);
81 if(
right - left + 1 >= 2 * num_threads * chunk_size)
82 # pragma omp parallel num_threads(num_threads)
86 num_threads = omp_get_num_threads();
87 reserved_left =
new bool[num_threads];
88 reserved_right =
new bool[num_threads];
93 / (
double)num_threads);
98 while (
right - left + 1 >= 2 * num_threads * chunk_size)
102 difference_type num_chunks = (
right - left + 1) / chunk_size;
104 for (
int r = 0; r < num_threads; ++r)
106 reserved_left[r] =
false;
107 reserved_right[r] =
false;
114 difference_type thread_left, thread_left_border,
115 thread_right, thread_right_border;
116 thread_left = left + 1;
119 thread_left_border = thread_left - 1;
120 thread_right = n - 1;
121 thread_right_border = thread_right + 1;
123 bool iam_finished =
false;
124 while (!iam_finished)
126 if (thread_left > thread_left_border)
128 omp_set_lock(&result_lock);
129 if (left + (chunk_size - 1) >
right)
134 thread_left_border = left + (chunk_size - 1);
137 omp_unset_lock(&result_lock);
140 if (thread_right < thread_right_border)
142 omp_set_lock(&result_lock);
143 if (left >
right - (chunk_size - 1))
147 thread_right =
right;
148 thread_right_border =
right - (chunk_size - 1);
151 omp_unset_lock(&result_lock);
158 while (thread_left < thread_right)
160 while (pred(begin[thread_left])
161 && thread_left <= thread_left_border)
163 while (!pred(begin[thread_right])
164 && thread_right >= thread_right_border)
167 if (thread_left > thread_left_border
168 || thread_right < thread_right_border)
172 std::swap(begin[thread_left], begin[thread_right]);
179 if (thread_left <= thread_left_border)
182 if (thread_right >= thread_right_border)
190 leftnew = left - leftover_left * chunk_size;
191 rightnew =
right + leftover_right * chunk_size;
197 if (thread_left <= thread_left_border
198 && thread_left_border >= leftnew)
201 reserved_left[(left - (thread_left_border + 1)) / chunk_size]
206 if (thread_right >= thread_right_border
207 && thread_right_border <= rightnew)
210 reserved_right[((thread_right_border - 1) -
right)
211 / chunk_size] =
true;
216 if (thread_left <= thread_left_border
217 && thread_left_border < leftnew)
220 difference_type swapstart = -1;
221 omp_set_lock(&result_lock);
222 for (
int r = 0; r < leftover_left; ++r)
223 if (!reserved_left[r])
225 reserved_left[r] =
true;
226 swapstart = left - (r + 1) * chunk_size;
229 omp_unset_lock(&result_lock);
231 #if _GLIBCXX_ASSERTIONS
232 _GLIBCXX_PARALLEL_ASSERT(swapstart != -1);
235 std::swap_ranges(begin + thread_left_border
237 begin + thread_left_border + 1,
241 if (thread_right >= thread_right_border
242 && thread_right_border > rightnew)
245 difference_type swapstart = -1;
246 omp_set_lock(&result_lock);
247 for (
int r = 0; r < leftover_right; ++r)
248 if (!reserved_right[r])
250 reserved_right[r] =
true;
251 swapstart =
right + r * chunk_size + 1;
254 omp_unset_lock(&result_lock);
256 #if _GLIBCXX_ASSERTIONS
257 _GLIBCXX_PARALLEL_ASSERT(swapstart != -1);
260 std::swap_ranges(begin + thread_right_border,
261 begin + thread_right_border + chunk_size,
264 #if _GLIBCXX_ASSERTIONS
269 for (
int r = 0; r < leftover_left; ++r)
270 _GLIBCXX_PARALLEL_ASSERT(reserved_left[r]);
271 for (
int r = 0; r < leftover_right; ++r)
272 _GLIBCXX_PARALLEL_ASSERT(reserved_right[r]);
283 # pragma omp flush(left, right)
286 difference_type final_left =
left, final_right =
right;
288 while (final_left < final_right)
291 while (pred(begin[final_left]) && final_left < final_right)
295 while (!pred(begin[final_right]) && final_left < final_right)
298 if (final_left == final_right)
300 std::swap(begin[final_left], begin[final_right]);
307 delete[] reserved_left;
308 delete[] reserved_right;
310 omp_destroy_lock(&result_lock);
314 if (final_left < n && !pred(begin[final_left]))
318 return final_left + 1;
328 template<
typename RandomAccessIterator,
typename Comparator>
331 RandomAccessIterator end, Comparator comp)
334 typedef typename traits_type::value_type value_type;
335 typedef typename traits_type::difference_type difference_type;
339 RandomAccessIterator split;
343 difference_type minimum_length = std::max<difference_type>(2,
347 while (static_cast<sequence_index_t>(end - begin) >= minimum_length)
349 difference_type n = end - begin;
351 RandomAccessIterator pivot_pos = begin + rng(n);
354 if (pivot_pos != (end - 1))
355 std::swap(*pivot_pos, *(end - 1));
365 pred(comp, *pivot_pos);
368 RandomAccessIterator split_pos1, split_pos2;
375 if (split_pos1 != pivot_pos)
376 std::swap(*split_pos1, *pivot_pos);
377 pivot_pos = split_pos1;
380 if ((split_pos1 + 1 - begin) < (n >> 7)
381 || (end - split_pos1) < (n >> 7))
388 value_type,
bool>(comp, *pivot_pos));
391 split_pos2 = __gnu_sequential::partition(split_pos1 + 1,
396 split_pos2 = split_pos1 + 1;
399 if (split_pos2 <= nth)
401 else if (nth < split_pos1)
408 __gnu_sequential::nth_element(begin, nth, end, comp);
416 template<
typename RandomAccessIterator,
typename Comparator>
419 RandomAccessIterator middle,
420 RandomAccessIterator end, Comparator comp)
423 std::sort(begin, middle, comp);
428 #undef _GLIBCXX_VOLATILE
static const _Settings & get()
Get the global settings.
sequence_index_t partition_chunk_size
Chunk size for partition.
std::iterator_traits< RandomAccessIterator >::difference_type parallel_partition(RandomAccessIterator begin, RandomAccessIterator end, Predicate pred, thread_index_t num_threads)
Parallel implementation of std::partition.
double partition_chunk_share
Chunk size for partition, relative to input size. If > 0.0, this value overrides partition_chunk_size...
Similar to std::binder1st, but giving the argument types explicitly.
Similar to std::binder1st, but giving the argument types explicitly.
Random number generator based on the Mersenne twister. This file is a GNU parallel extension to the S...
ios_base & right(ios_base &__base)
Calls base.setf(ios_base::right, ios_base::adjustfield).
const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
uint16 thread_index_t
Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit in...
ios_base & left(ios_base &__base)
Calls base.setf(ios_base::left, ios_base::adjustfield).
End-user include file. Provides advanced settings and tuning options. This file is a GNU parallel ext...
Random number generator, based on the Mersenne twister.
sequence_index_t nth_element_minimal_n
Minimal input size for nth_element.
void parallel_partial_sort(RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end, Comparator comp)
Parallel implementation of std::partial_sort().
sequence_index_t partition_minimal_n
Minimal input size for partition.
class _Settings Run-time settings for the parallel mode, including all tunable parameters.
#define _GLIBCXX_VOLATILE
Decide whether to declare certain variables volatile.
Parallel sorting algorithm switch. This file is a GNU parallel extension to the Standard C++ Library...
Includes the original header files concerned with iterators except for stream iterators. This file is a GNU parallel extension to the Standard C++ Library.
#define _GLIBCXX_CALL(n)
Macro to produce log message when entering a function.
Similar to std::binder2nd, but giving the argument types explicitly.
void parallel_nth_element(RandomAccessIterator begin, RandomAccessIterator nth, RandomAccessIterator end, Comparator comp)
Parallel implementation of std::nth_element().