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));
206 __num_threads_leftside = std::max<_ThreadIndex>
207 (1, std::min<_ThreadIndex>(__num_threads - 1, __split_pos
208 * __num_threads / __n));
214 # pragma omp parallel num_threads(2)
217 if(omp_get_num_threads() < 2)
220 __wait = __parent_wait;
222 # pragma omp sections
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)
343 (std::make_pair(__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;
470 __tls[__i]->_M_num_threads = __num_threads;
471 __tls[__i]->_M_global = std::make_pair(__begin, __end);
474 __tls[__i]->_M_initial = std::make_pair(__end, __end);
479 __num_threads,
true);
481 #if _GLIBCXX_PARALLEL_ASSERTIONS
485 _GLIBCXX_PARALLEL_ASSERT(
486 !__tls[__i]->_M_leftover_parts.pop_back(__dummy));