33#ifndef _GLIBCXX_PARALLEL_PARTITION_H
34#define _GLIBCXX_PARALLEL_PARTITION_H 1
43#define _GLIBCXX_VOLATILE volatile
54 template<
typename _RAIter,
typename _Predicate>
60 typedef typename _TraitsType::value_type _ValueType;
61 typedef typename _TraitsType::difference_type _DifferenceType;
63 _DifferenceType __n = __end - __begin;
72 __leftover_left, __leftover_right,
73 __leftnew, __rightnew;
76 int* __reserved_left = 0, * __reserved_right = 0;
81 if (__dist >= 2 * __num_threads * __chunk_size)
82# pragma omp parallel num_threads(__num_threads)
86 __num_threads = omp_get_num_threads();
87 __reserved_left =
new int[__num_threads];
88 __reserved_right =
new int[__num_threads];
91 __chunk_size = std::max<_DifferenceType>
98 while (__dist >= 2 * __num_threads * __chunk_size)
102 _DifferenceType __num_chunks = __dist / __chunk_size;
106 __reserved_left [__r] = 0;
107 __reserved_right[__r] = 0;
110 __leftover_right = 0;
114 _DifferenceType __thread_left, __thread_left_border,
115 __thread_right, __thread_right_border;
117 __thread_left = __left + 1;
119 __thread_left_border = __thread_left - 1;
121 __thread_right = __n - 1;
123 __thread_right_border = __thread_right + 1;
125 bool __iam_finished =
false;
126 while (!__iam_finished)
128 if (__thread_left > __thread_left_border)
130 _DifferenceType __former_dist =
132 if (__former_dist < __chunk_size)
135 __iam_finished =
true;
142 __thread_left_border =
143 __thread_left + (__chunk_size - 1);
147 if (__thread_right < __thread_right_border)
149 _DifferenceType __former_dist =
151 if (__former_dist < __chunk_size)
154 __iam_finished =
true;
161 __thread_right_border =
162 __thread_right - (__chunk_size - 1);
167 while (__thread_left < __thread_right)
169 while (__pred(__begin[__thread_left])
170 && __thread_left <= __thread_left_border)
172 while (!__pred(__begin[__thread_right])
173 && __thread_right >= __thread_right_border)
176 if (__thread_left > __thread_left_border
177 || __thread_right < __thread_right_border)
181 std::iter_swap(__begin + __thread_left,
182 __begin + __thread_right);
189 if (__thread_left <= __thread_left_border)
192 if (__thread_right >= __thread_right_border)
200 __leftnew = __left - __leftover_left * __chunk_size,
201 __rightold = __right,
202 __rightnew = __right + __leftover_right * __chunk_size;
205 if (__thread_left <= __thread_left_border
206 && __thread_left_border >= __leftnew)
209 __reserved_left[(__left - (__thread_left_border + 1))
214 if (__thread_right >= __thread_right_border
215 && __thread_right_border <= __rightnew)
218 __reserved_right[((__thread_right_border - 1) - __right)
224 if (__thread_left <= __thread_left_border
225 && __thread_left_border < __leftnew)
228 _DifferenceType __swapstart = -1;
229 for (
int __r = 0; __r < __leftover_left; ++__r)
230 if (__reserved_left[__r] == 0
233 __swapstart = __leftold - (__r + 1) * __chunk_size;
237#if _GLIBCXX_PARALLEL_ASSERTIONS
238 _GLIBCXX_PARALLEL_ASSERT(__swapstart != -1);
241 std::swap_ranges(__begin + __thread_left_border
242 - (__chunk_size - 1),
243 __begin + __thread_left_border + 1,
244 __begin + __swapstart);
247 if (__thread_right >= __thread_right_border
248 && __thread_right_border > __rightnew)
251 _DifferenceType __swapstart = -1;
252 for (
int __r = 0; __r < __leftover_right; ++__r)
253 if (__reserved_right[__r] == 0
256 __swapstart = __rightold + __r * __chunk_size + 1;
260#if _GLIBCXX_PARALLEL_ASSERTIONS
261 _GLIBCXX_PARALLEL_ASSERT(__swapstart != -1);
264 std::swap_ranges(__begin + __thread_right_border,
265 __begin + __thread_right_border
266 + __chunk_size, __begin + __swapstart);
268#if _GLIBCXX_PARALLEL_ASSERTIONS
273 for (_DifferenceType __r = 0; __r < __leftover_left; ++__r)
274 _GLIBCXX_PARALLEL_ASSERT(__reserved_left[__r] == 1);
275 for (_DifferenceType __r = 0; __r < __leftover_right; ++__r)
276 _GLIBCXX_PARALLEL_ASSERT(__reserved_right[__r] == 1);
281 __right = __rightnew;
282 __dist = __right - __left + 1;
285# pragma omp flush(__left, __right)
288 _DifferenceType __final_left = __left, __final_right = __right;
290 while (__final_left < __final_right)
293 while (__pred(__begin[__final_left])
294 && __final_left < __final_right)
298 while (!__pred(__begin[__final_right])
299 && __final_left < __final_right)
302 if (__final_left == __final_right)
304 std::iter_swap(__begin + __final_left, __begin + __final_right);
311 delete[] __reserved_left;
312 delete[] __reserved_right;
316 if (__final_left < __n && !__pred(__begin[__final_left]))
320 return __final_left + 1;
330 template<
typename _RAIter,
typename _Compare>
333 _RAIter __end, _Compare __comp)
336 typedef typename _TraitsType::value_type _ValueType;
337 typedef typename _TraitsType::difference_type _DifferenceType;
345 _DifferenceType __minimum_length = std::max<_DifferenceType>(2,
349 while (
static_cast<_SequenceIndex>(__end - __begin) >= __minimum_length)
351 _DifferenceType __n = __end - __begin;
353 _RAIter __pivot_pos = __begin + __rng(__n);
356 if (__pivot_pos != (__end - 1))
357 std::iter_swap(__pivot_pos, __end - 1);
358 __pivot_pos = __end - 1;
367 __pred(__comp, *__pivot_pos);
370 _RAIter __split_pos1, __split_pos2;
373 __get_max_threads());
378 if (__split_pos1 != __pivot_pos)
379 std::iter_swap(__split_pos1, __pivot_pos);
380 __pivot_pos = __split_pos1;
383 if ((__split_pos1 + 1 - __begin) < (__n >> 7)
384 || (__end - __split_pos1) < (__n >> 7))
389 __binder1st<_Compare, _ValueType,
390 _ValueType,
bool>, _ValueType>
392 _ValueType,
bool>(__comp, *__pivot_pos));
395 __split_pos2 = __gnu_sequential::partition(__split_pos1 + 1,
400 __split_pos2 = __split_pos1 + 1;
403 if (__split_pos2 <= __nth)
404 __begin = __split_pos2;
405 else if (__nth < __split_pos1)
406 __end = __split_pos1;
412 __gnu_sequential::nth_element(__begin, __nth, __end, __comp);
420 template<
typename _RAIter,
typename _Compare>
424 _RAIter __end, _Compare __comp)
427 std::sort(__begin, __middle, __comp);
432#undef _GLIBCXX_VOLATILE
End-user include file. Provides advanced settings and tuning options. This file is a GNU parallel ext...
#define _GLIBCXX_CALL(__n)
Macro to produce log message when entering a function.
Parallel sorting algorithm switch. This file is a GNU parallel extension to the Standard C++ Library.
#define _GLIBCXX_VOLATILE
Decide whether to declare certain variables volatile.
Includes the original header files concerned with iterators except for stream iterators....
Random number generator based on the Mersenne twister. This file is a GNU parallel extension to the S...
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
GNU parallel code for public use.
uint16_t _ThreadIndex
Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit in...
void __parallel_nth_element(_RAIter __begin, _RAIter __nth, _RAIter __end, _Compare __comp)
Parallel implementation of std::nth_element().
uint64_t _SequenceIndex
Unsigned integer to index __elements. The total number of elements for each algorithm must fit into t...
_Tp __fetch_and_add(volatile _Tp *__ptr, _Tp __addend)
Add a value to a variable, atomically.
void __parallel_partial_sort(_RAIter __begin, _RAIter __middle, _RAIter __end, _Compare __comp)
Parallel implementation of std::partial_sort().
std::iterator_traits< _RAIter >::difference_type __parallel_partition(_RAIter __begin, _RAIter __end, _Predicate __pred, _ThreadIndex __num_threads)
Parallel implementation of std::partition.
bool __compare_and_swap(volatile _Tp *__ptr, _Tp __comparand, _Tp __replacement)
Compare-and-swap.
Traits class for iterators.
Similar to std::unary_negate, but giving the argument types explicitly.
Similar to std::binder1st, but giving the argument types explicitly.
Similar to std::binder2nd, but giving the argument types explicitly.
Random number generator, based on the Mersenne twister.
class _Settings Run-time settings for the parallel mode including all tunable parameters.
_SequenceIndex nth_element_minimal_n
Minimal input size for nth_element.
double partition_chunk_share
Chunk size for partition, relative to input size. If > 0.0, this value overrides partition_chunk_size...
_SequenceIndex partition_chunk_size
Chunk size for partition.
_SequenceIndex partition_minimal_n
Minimal input size for partition.
static const _Settings & get()
Get the global settings.