42#ifndef _GLIBCXX_PARALLEL_BALANCED_QUICKSORT_H
43#define _GLIBCXX_PARALLEL_BALANCED_QUICKSORT_H 1
54#if _GLIBCXX_PARALLEL_ASSERTIONS
56#ifdef _GLIBCXX_HAVE_UNISTD_H
64 template<
typename _RAIter>
68 typedef typename _TraitsType::difference_type _DifferenceType;
101 template<
typename _RAIter,
typename _Compare>
106 _GLIBCXX_PARALLEL_ASSERT(__num_threads > 0);
109 typedef typename _TraitsType::value_type _ValueType;
110 typedef typename _TraitsType::difference_type _DifferenceType;
112 _RAIter __pivot_pos =
116#if defined(_GLIBCXX_PARALLEL_ASSERTIONS)
118 _DifferenceType __n = __end - __begin;
120 _GLIBCXX_PARALLEL_ASSERT((!__comp(*__pivot_pos, *__begin)
121 && !__comp(*(__begin + __n / 2),
123 || (!__comp(*__pivot_pos, *__begin)
124 && !__comp(*(__end - 1), *__pivot_pos))
125 || (!__comp(*__pivot_pos, *(__begin + __n / 2))
126 && !__comp(*__begin, *__pivot_pos))
127 || (!__comp(*__pivot_pos, *(__begin + __n / 2))
128 && !__comp(*(__end - 1), *__pivot_pos))
129 || (!__comp(*__pivot_pos, *(__end - 1))
130 && !__comp(*__begin, *__pivot_pos))
131 || (!__comp(*__pivot_pos, *(__end - 1))
132 && !__comp(*(__begin + __n / 2),
137 if (__pivot_pos != (__end - 1))
138 std::iter_swap(__pivot_pos, __end - 1);
139 __pivot_pos = __end - 1;
142 __pred(__comp, *__pivot_pos);
150 std::iter_swap(__begin + __split_pos, __pivot_pos);
151 __pivot_pos = __begin + __split_pos;
153#if _GLIBCXX_PARALLEL_ASSERTIONS
155 for (__r = __begin; __r != __pivot_pos; ++__r)
156 _GLIBCXX_PARALLEL_ASSERT(__comp(*__r, *__pivot_pos));
157 for (; __r != __end; ++__r)
158 _GLIBCXX_PARALLEL_ASSERT(!__comp(*__r, *__pivot_pos));
172 template<
typename _RAIter,
typename _Compare>
175 _RAIter __begin, _RAIter __end,
181 typedef typename _TraitsType::value_type _ValueType;
182 typedef typename _TraitsType::difference_type _DifferenceType;
184 _DifferenceType __n = __end - __begin;
186 if (__num_threads <= 1 || __n <= 1)
197 _DifferenceType __split_pos =
200#if _GLIBCXX_PARALLEL_ASSERTIONS
201 _GLIBCXX_PARALLEL_ASSERT(0 <= __split_pos &&
202 __split_pos < (__end - __begin));
208 * __num_threads / __n));
214# pragma omp parallel num_threads(2)
217 if(omp_get_num_threads() < 2)
220 __wait = __parent_wait;
227 __iam, __num_threads_leftside, __wait);
228 __wait = __parent_wait;
233 __qsb_conquer(__tls, __begin + __split_pos + 1, __end, __comp,
234 __iam + __num_threads_leftside,
235 __num_threads - __num_threads_leftside, __wait);
236 __wait = __parent_wait;
248 template<
typename _RAIter,
typename _Compare>
255 typedef typename _TraitsType::value_type _ValueType;
256 typedef typename _TraitsType::difference_type _DifferenceType;
263 if (__base_case_n < 2)
272 _DifferenceType __elements_done = 0;
273#if _GLIBCXX_PARALLEL_ASSERTIONS
274 _DifferenceType __total_elements_done = 0;
280 _RAIter __begin = __current.first, __end = __current.second;
281 _DifferenceType __n = __end - __begin;
283 if (__n > __base_case_n)
286 _RAIter __pivot_pos = __begin + __rng(__n);
289 if (__pivot_pos != (__end - 1))
290 std::iter_swap(__pivot_pos, __end - 1);
291 __pivot_pos = __end - 1;
294 <_Compare, _ValueType, _ValueType,
bool>
295 __pred(__comp, *__pivot_pos);
298 _RAIter __split_pos1, __split_pos2;
299 __split_pos1 = __gnu_sequential::partition(__begin, __end - 1,
303#if _GLIBCXX_PARALLEL_ASSERTIONS
304 _GLIBCXX_PARALLEL_ASSERT(__begin <= __split_pos1
305 && __split_pos1 < __end);
308 if (__split_pos1 != __pivot_pos)
309 std::iter_swap(__split_pos1, __pivot_pos);
310 __pivot_pos = __split_pos1;
313 if ((__split_pos1 + 1 - __begin) < (__n >> 7)
314 || (__end - __split_pos1) < (__n >> 7))
319 <_Compare, _ValueType, _ValueType,
bool>, _ValueType>
321 <_Compare, _ValueType, _ValueType,
bool>
322 (__comp, *__pivot_pos));
325 __split_pos2 = __gnu_sequential::partition(__split_pos1 + 1,
330 __split_pos2 = __split_pos1 + 1;
333 __elements_done += (__split_pos2 - __split_pos1);
334#if _GLIBCXX_PARALLEL_ASSERTIONS
335 __total_elements_done += (__split_pos2 - __split_pos1);
338 if (((__split_pos1 + 1) - __begin) < (__end - (__split_pos2)))
341 if ((__split_pos2) != __end)
346 __current.second = __split_pos1;
352 if (__begin != __split_pos1)
354 (__begin, __split_pos1));
356 __current.first = __split_pos2;
363 __gnu_sequential::sort(__begin, __end, __comp);
364 __elements_done += __n;
365#if _GLIBCXX_PARALLEL_ASSERTIONS
366 __total_elements_done += __n;
378#if _GLIBCXX_PARALLEL_ASSERTIONS
379 double __search_start = omp_get_wtime();
383 bool __successfully_stolen =
false;
385 && !__successfully_stolen
388 && (omp_get_wtime() < (__search_start + 1.0))
393 __victim = __rng(__num_threads);
396 __successfully_stolen = (__victim != __iam)
397 && __tls[__victim]->_M_leftover_parts.pop_back(__current);
398 if (!__successfully_stolen)
400#if !defined(__ICC) && !defined(__ECC)
405#if _GLIBCXX_PARALLEL_ASSERTIONS
406 if (omp_get_wtime() >= (__search_start + 1.0))
409 _GLIBCXX_PARALLEL_ASSERT(omp_get_wtime()
410 < (__search_start + 1.0));
413 if (!__successfully_stolen)
415#if _GLIBCXX_PARALLEL_ASSERTIONS
431 template<
typename _RAIter,
typename _Compare>
439 typedef typename _TraitsType::value_type _ValueType;
440 typedef typename _TraitsType::difference_type _DifferenceType;
445 _DifferenceType __n = __end - __begin;
451 if (__num_threads > __n)
455 _TLSType** __tls =
new _TLSType*[__num_threads];
456 _DifferenceType __queue_size = (__num_threads
466 volatile _DifferenceType __elements_leftover = __n;
469 __tls[__i]->_M_elements_leftover = &__elements_leftover;
470 __tls[__i]->_M_num_threads = __num_threads;
479 __num_threads,
true);
481#if _GLIBCXX_PARALLEL_ASSERTIONS
485 _GLIBCXX_PARALLEL_ASSERT(
486 !__tls[__i]->_M_leftover_parts.pop_back(__dummy));
Lock-free double-ended queue. This file is a GNU parallel extension to the Standard C++ Library.
#define _GLIBCXX_PARALLEL_ASSERTIONS
Switch on many _GLIBCXX_PARALLEL_ASSERTions in parallel code. Should be switched on only locally.
#define _GLIBCXX_CALL(__n)
Macro to produce log message when entering a function.
Parallel implementation of std::partition(), std::nth_element(), and std::partial_sort()....
Routines for checking the correctness of algorithm results. This file is a GNU parallel extension to ...
Random number generator based on the Mersenne twister. This file is a GNU parallel extension to the S...
Includes the original header files concerned with iterators except for stream iterators....
Runtime settings and tuning parameters, heuristics to decide whether to use parallelized algorithms.
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
constexpr const _Tp & min(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_sort_qsb(_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)
Top-level quicksort routine.
_RAIter __median_of_three_iterators(_RAIter __a, _RAIter __b, _RAIter __c, _Compare __comp)
Compute the median of three referenced elements, according to __comp.
void __qsb_local_sort_with_helping(_QSBThreadLocal< _RAIter > **__tls, _Compare &__comp, _ThreadIndex __iam, bool __wait)
Quicksort step doing load-balanced local sort.
void __qsb_conquer(_QSBThreadLocal< _RAIter > **__tls, _RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __iam, _ThreadIndex __num_threads, bool __parent_wait)
Quicksort conquer step.
void __yield()
Yield control to another thread, without waiting for the end of the time slice.
std::iterator_traits< _RAIter >::difference_type __parallel_partition(_RAIter __begin, _RAIter __end, _Predicate __pred, _ThreadIndex __num_threads)
Parallel implementation of std::partition.
_Size __rd_log2(_Size __n)
Calculates the rounded-down logarithm of __n for base 2.
std::iterator_traits< _RAIter >::difference_type __qsb_divide(_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)
Balanced quicksort divide step.
Traits class for iterators.
Struct holding two objects of arbitrary type.
Information local to one thread in the parallel quicksort run.
_Piece _M_initial
Initial piece to work on.
volatile _DifferenceType * _M_elements_leftover
Pointer to a counter of elements left over to sort.
_ThreadIndex _M_num_threads
Number of threads involved in this algorithm.
std::pair< _RAIter, _RAIter > _Piece
Continuous part of the sequence, described by an iterator pair.
_QSBThreadLocal(int __queue_size)
Constructor.
_RestrictedBoundedConcurrentQueue< _Piece > _M_leftover_parts
Work-stealing queue.
_Piece _M_global
The complete sequence to sort.
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.
Double-ended queue of bounded size, allowing lock-free atomic access. push_front() and pop_front() mu...
Random number generator, based on the Mersenne twister.
_SequenceIndex sort_qsb_base_case_maximal_n
Maximal subsequence __length to switch to unbalanced __base case. Applies to std::sort with dynamical...
static const _Settings & get()
Get the global settings.