32 #ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGESORT_H 33 #define _GLIBCXX_PARALLEL_MULTIWAY_MERGESORT_H 1 45 template<
typename _DifferenceTp>
48 typedef _DifferenceTp _DifferenceType;
60 template<
typename _RAIter>
63 typedef std::iterator_traits<_RAIter> _TraitsType;
64 typedef typename _TraitsType::value_type _ValueType;
65 typedef typename _TraitsType::difference_type _DifferenceType;
95 template<
typename _RAIter,
typename _DifferenceTp>
98 _DifferenceTp __num_samples)
100 typedef std::iterator_traits<_RAIter> _TraitsType;
101 typedef typename _TraitsType::value_type _ValueType;
102 typedef _DifferenceTp _DifferenceType;
106 _DifferenceType* __es =
new _DifferenceType[__num_samples + 2];
109 __num_samples + 1, __es);
111 for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
112 ::
new(&(__sd->
_M_samples[__iam * __num_samples + __i]))
120 template<
bool __exact,
typename _RAIter,
121 typename _Compare,
typename _SortingPlacesIterator>
126 template<
typename _RAIter,
typename _Compare,
127 typename _SortingPlacesIterator>
135 std::iterator_traits<_RAIter>::difference_type
141 _SortingPlacesIterator> >
152 if (__iam < __sd->_M_num_threads - 1)
162 = __offsets[__seq] - __seqs[__seq].first;
176 __sd->
_M_pieces[__iam - 1][__seq]._M_end;
179 __sd->
_M_pieces[__iam][__seq]._M_begin = 0;
185 template<
typename _RAIter,
typename _Compare,
186 typename _SortingPlacesIterator>
194 std::iterator_traits<_RAIter>::difference_type
197 typedef std::iterator_traits<_RAIter> _TraitsType;
198 typedef typename _TraitsType::value_type _ValueType;
199 typedef typename _TraitsType::difference_type _DifferenceType;
216 if (__num_samples * __iam > 0)
227 __sd->
_M_pieces[__iam][__s]._M_begin = 0;
229 if ((__num_samples * (__iam + 1)) <
236 __sd->
_M_samples[__num_samples * (__iam + 1)],
247 template<
bool __stable,
typename _RAIter,
typename _Compare>
248 struct __possibly_stable_sort
251 template<
typename _RAIter,
typename _Compare>
252 struct __possibly_stable_sort<true, _RAIter, _Compare>
254 void operator()(
const _RAIter& __begin,
255 const _RAIter& __end, _Compare& __comp)
const 256 { __gnu_sequential::stable_sort(__begin, __end, __comp); }
259 template<
typename _RAIter,
typename _Compare>
260 struct __possibly_stable_sort<false, _RAIter, _Compare>
262 void operator()(
const _RAIter __begin,
263 const _RAIter __end, _Compare& __comp)
const 264 { __gnu_sequential::sort(__begin, __end, __comp); }
267 template<
bool __stable,
typename Seq_RAIter,
268 typename _RAIter,
typename _Compare,
270 struct __possibly_stable_multiway_merge
273 template<
typename Seq_RAIter,
typename _RAIter,
274 typename _Compare,
typename _DiffType>
275 struct __possibly_stable_multiway_merge<true, Seq_RAIter,
276 _RAIter, _Compare, _DiffType>
278 void operator()(
const Seq_RAIter& __seqs_begin,
279 const Seq_RAIter& __seqs_end,
280 const _RAIter& __target,
282 _DiffType __length_am)
const 283 { stable_multiway_merge(__seqs_begin, __seqs_end, __target,
287 template<
typename Seq_RAIter,
typename _RAIter,
288 typename _Compare,
typename _DiffType>
289 struct __possibly_stable_multiway_merge<false, Seq_RAIter,
290 _RAIter, _Compare, _DiffType>
292 void operator()(
const Seq_RAIter& __seqs_begin,
293 const Seq_RAIter& __seqs_end,
294 const _RAIter& __target,
296 _DiffType __length_am)
const 305 template<
bool __stable,
bool __exact,
typename _RAIter,
311 typedef std::iterator_traits<_RAIter> _TraitsType;
312 typedef typename _TraitsType::value_type _ValueType;
313 typedef typename _TraitsType::difference_type _DifferenceType;
318 _DifferenceType __length_local =
323 typedef _ValueType* _SortingPlacesIterator;
326 static_cast<_ValueType*
>(::operator
new(
sizeof(_ValueType)
327 * (__length_local + 1)));
335 __possibly_stable_sort<__stable, _SortingPlacesIterator, _Compare>()
345 _DifferenceType __num_samples =
348 (__iam, __sd, __comp, __num_samples);
351 _DifferenceType __offset = 0, __length_am = 0;
354 __length_am += (__sd->
_M_pieces[__iam][__s]._M_end
356 __offset += __sd->
_M_pieces[__iam][__s]._M_begin;
373 __possibly_stable_multiway_merge<
374 __stable,
typename _SeqVector::iterator,
375 _RAIter, _Compare, _DifferenceType>()(__seqs.begin(), __seqs.end(),
381 for (_DifferenceType __i = 0; __i < __length_local; ++__i)
392 template<
bool __stable,
bool __exact,
typename _RAIter,
401 typedef std::iterator_traits<_RAIter> _TraitsType;
402 typedef typename _TraitsType::value_type _ValueType;
403 typedef typename _TraitsType::difference_type _DifferenceType;
405 _DifferenceType __n = __end - __begin;
411 if (__num_threads > __n)
416 _DifferenceType* __starts;
417 _DifferenceType __size;
419 # pragma omp parallel num_threads(__num_threads) 421 __num_threads = omp_get_num_threads();
436 (::operator
new(__size *
sizeof(_ValueType)));
441 __sd.
_M_offsets =
new _DifferenceType[__num_threads - 1];
445 __sd.
_M_pieces[__s].resize(__num_threads);
446 __starts = __sd.
_M_starts =
new _DifferenceType[__num_threads + 1];
448 _DifferenceType __chunk_length = __n / __num_threads;
449 _DifferenceType __split = __n % __num_threads;
450 _DifferenceType __pos = 0;
453 __starts[__i] = __pos;
454 __pos += ((__i < __split)
455 ? (__chunk_length + 1) : __chunk_length);
457 __starts[__num_threads] = __pos;
461 parallel_sort_mwms_pu<__stable, __exact>(&__sd, __comp);
469 for (_DifferenceType __i = 0; __i < __size; ++__i)
A standard container which offers fixed time access to individual elements in any order...
Data accessed by all threads.
Includes the original header files concerned with iterators except for stream iterators. This file is a GNU parallel extension to the Standard C++ Library.
iterator begin() noexcept
uint16_t _ThreadIndex
Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit in...
_ValueType * _M_samples
Samples.
void parallel_sort_mwms(_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)
PMWMS main call.
_RAIterOut multiway_merge(_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag)
Multiway Merge Frontend.
End-user include file. Provides advanced settings and tuning options. This file is a GNU parallel ext...
static const _Settings & get()
Get the global settings.
_ForwardIterator uninitialized_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result)
Copies the range [first,last) into result.
_DifferenceType _M_end
End of subsequence.
_OutputIterator __equally_split(_DifferenceType __n, _ThreadIndex __num_threads, _OutputIterator __s)
function to split a sequence into parts of almost equal size.
_DifferenceType _M_begin
Begin of subsequence.
void parallel_sort_mwms_pu(_PMWMSSortingData< _RAIter > *__sd, _Compare &__comp)
PMWMS code executed by each thread.
Implementation of sequential and parallel multiway merge.
_ThreadIndex _M_num_threads
Number of threads involved.
Struct holding two objects of arbitrary type.
void multiseq_partition(_RanSeqs __begin_seqs, _RanSeqs __end_seqs, _RankType __rank, _RankIterator __begin_offsets, _Compare __comp=std::less< typename std::iterator_traits< typename std::iterator_traits< _RanSeqs >::value_type::first_type >::value_type >())
Splits several sorted sequences at a certain global __rank, resulting in a splitting point for each s...
Forces sequential execution at compile time.
_RAIter _M_source
Input __begin.
unsigned int sort_mwms_oversampling
Oversampling factor for parallel std::sort (MWMS).
std::vector< _Piece< _DifferenceType > > * _M_pieces
Pieces of data to merge [thread][__sequence].
_DifferenceType * _M_offsets
Offsets to add to the found positions.
GNU parallel code for public use.
_ValueType ** _M_temporary
Storage in which to sort.
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.
void __determine_samples(_PMWMSSortingData< _RAIter > *__sd, _DifferenceTp __num_samples)
Select _M_samples from a sequence.
_DifferenceType * _M_starts
Start indices, per thread.
#define _GLIBCXX_CALL(__n)
Macro to produce log message when entering a function.