32 #ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGESORT_H
33 #define _GLIBCXX_PARALLEL_MULTIWAY_MERGESORT_H 1
42 namespace __gnu_parallel
46 template<
typename _DifferenceTp>
49 typedef _DifferenceTp difference_type;
61 template<
typename RandomAccessIterator>
65 typedef typename traits_type::value_type value_type;
66 typedef typename traits_type::difference_type difference_type;
96 template<
typename RandomAccessIterator,
typename _DifferenceTp>
99 _DifferenceTp num_samples)
102 typedef typename traits_type::value_type value_type;
103 typedef _DifferenceTp difference_type;
107 difference_type* es =
new difference_type[num_samples + 2];
110 num_samples + 1, es);
112 for (difference_type i = 0; i < num_samples; ++i)
113 ::
new(&(sd->
samples[iam * num_samples + i]))
120 template<
bool exact,
typename RandomAccessIterator,
121 typename Comparator,
typename SortingPlacesIterator>
127 template<
typename RandomAccessIterator,
typename Comparator,
128 typename SortingPlacesIterator>
130 <true, RandomAccessIterator, Comparator, SortingPlacesIterator>
137 std::iterator_traits<RandomAccessIterator>::difference_type
146 seqs[s] = std::make_pair(sd->
temporary[s],
153 if (iam < sd->num_threads - 1)
161 sd->
pieces[iam][seq].
end = offsets[seq] - seqs[seq].first;
183 template<
typename RandomAccessIterator,
typename Comparator,
184 typename SortingPlacesIterator>
186 SortingPlacesIterator>
193 std::iterator_traits<RandomAccessIterator>::difference_type
198 typedef typename traits_type::value_type value_type;
199 typedef typename traits_type::difference_type difference_type;
206 __gnu_sequential::sort(sd->
samples,
215 if (num_samples * iam > 0)
220 sd->
samples[num_samples * iam],
227 if ((num_samples * (iam + 1)) < (num_samples * sd->
num_threads))
232 sd->
samples[num_samples * (iam + 1)],
242 template<
bool stable,
typename RandomAccessIterator,
typename Comparator>
243 struct possibly_stable_sort
247 template<
typename RandomAccessIterator,
typename Comparator>
248 struct possibly_stable_sort<true, RandomAccessIterator, Comparator>
250 void operator()(
const RandomAccessIterator& begin,
251 const RandomAccessIterator& end, Comparator& comp)
const
253 __gnu_sequential::stable_sort(begin, end, comp);
257 template<
typename RandomAccessIterator,
typename Comparator>
258 struct possibly_stable_sort<false, RandomAccessIterator, Comparator>
260 void operator()(
const RandomAccessIterator begin,
261 const RandomAccessIterator end, Comparator& comp)
const
263 __gnu_sequential::sort(begin, end, comp);
267 template<
bool stable,
typename SeqRandomAccessIterator,
268 typename RandomAccessIterator,
typename Comparator,
270 struct possibly_stable_multiway_merge
274 template<
typename SeqRandomAccessIterator,
typename RandomAccessIterator,
275 typename Comparator,
typename DiffType>
276 struct possibly_stable_multiway_merge
277 <true, SeqRandomAccessIterator, RandomAccessIterator, Comparator,
280 void operator()(
const SeqRandomAccessIterator& seqs_begin,
281 const SeqRandomAccessIterator& seqs_end,
282 const RandomAccessIterator& target,
284 DiffType length_am)
const
286 stable_multiway_merge(seqs_begin, seqs_end, target, length_am, comp,
291 template<
typename SeqRandomAccessIterator,
typename RandomAccessIterator,
292 typename Comparator,
typename DiffType>
293 struct possibly_stable_multiway_merge
294 <false, SeqRandomAccessIterator, RandomAccessIterator, Comparator,
297 void operator()(
const SeqRandomAccessIterator& seqs_begin,
298 const SeqRandomAccessIterator& seqs_end,
299 const RandomAccessIterator& target,
301 DiffType length_am)
const
312 template<
bool stable,
bool exact,
typename RandomAccessIterator,
319 typedef typename traits_type::value_type value_type;
320 typedef typename traits_type::difference_type difference_type;
325 difference_type length_local = sd->
starts[iam + 1] - sd->
starts[iam];
329 typedef value_type* SortingPlacesIterator;
332 static_cast<value_type*
>(
333 ::operator
new(
sizeof(value_type) * (length_local + 1)));
340 possibly_stable_sort<stable, SortingPlacesIterator, Comparator>()
348 difference_type num_samples =
351 <exact, RandomAccessIterator, Comparator, SortingPlacesIterator>()
352 (iam, sd, comp, num_samples);
355 difference_type offset = 0, length_am = 0;
374 possibly_stable_multiway_merge<
376 typename seq_vector_type::iterator,
377 RandomAccessIterator,
378 Comparator, difference_type>()
379 (seqs.begin(), seqs.end(),
380 sd->
source + offset, comp,
395 template<
bool stable,
bool exact,
typename RandomAccessIterator,
405 typedef typename traits_type::value_type value_type;
406 typedef typename traits_type::difference_type difference_type;
408 difference_type n = end - begin;
419 difference_type* starts;
421 # pragma omp parallel num_threads(num_threads)
423 num_threads = omp_get_num_threads();
430 sd.
temporary =
new value_type*[num_threads];
434 difference_type size =
437 sd.
samples =
static_cast<value_type*
>(
438 ::operator
new(size *
sizeof(value_type)));
443 sd.
offsets =
new difference_type[num_threads - 1];
445 for (
int s = 0; s < num_threads; ++s)
447 starts = sd.
starts =
new difference_type[num_threads + 1];
449 difference_type chunk_length = n / num_threads;
450 difference_type split = n % num_threads;
451 difference_type pos = 0;
452 for (
int i = 0; i < num_threads; ++i)
455 pos += (i < split) ? (chunk_length + 1) : chunk_length;
457 starts[num_threads] = pos;
461 parallel_sort_mwms_pu<stable, exact>(&sd, comp);