39 #ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
40 #define _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
48 #if _GLIBCXX_ASSERTIONS
53 #define _GLIBCXX_PARALLEL_LENGTH(s) ((s).second - (s).first)
55 namespace __gnu_parallel
60 template<
typename RandomAccessIterator,
typename Comparator>
65 template<
typename RandomAccessIterator,
typename Comparator>
67 operator<(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
70 template<
typename RandomAccessIterator,
typename Comparator>
72 operator<=(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
83 template<
typename RandomAccessIterator,
typename Comparator>
88 RandomAccessIterator current;
91 RandomAccessIterator end;
103 RandomAccessIterator end, Comparator& comp)
104 : current(begin), end(end), comp(comp)
118 typename std::iterator_traits<RandomAccessIterator>::value_type&
124 operator RandomAccessIterator()
128 operator< <RandomAccessIterator, Comparator>(
133 operator<= <RandomAccessIterator, Comparator>(
142 template<
typename RandomAccessIterator,
typename Comparator>
144 operator<(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
147 if (bi1.current == bi1.end)
148 return bi2.current == bi2.end;
149 if (bi2.current == bi2.end)
151 return (bi1.comp)(*bi1, *bi2);
158 template<
typename RandomAccessIterator,
typename Comparator>
160 operator<=(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
163 if (bi2.current == bi2.end)
164 return bi1.current != bi1.end;
165 if (bi1.current == bi1.end)
167 return !(bi1.comp)(*bi2, *bi1);
170 template<
typename RandomAccessIterator,
typename Comparator>
171 class unguarded_iterator;
173 template<
typename RandomAccessIterator,
typename Comparator>
175 operator<(unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
176 unguarded_iterator<RandomAccessIterator, Comparator>& bi2);
178 template<
typename RandomAccessIterator,
typename Comparator>
180 operator<=(unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
181 unguarded_iterator<RandomAccessIterator, Comparator>& bi2);
183 template<
typename RandomAccessIterator,
typename Comparator>
184 class unguarded_iterator
188 RandomAccessIterator current;
190 mutable Comparator& comp;
197 unguarded_iterator(RandomAccessIterator begin,
198 RandomAccessIterator end, Comparator& comp)
199 : current(begin), comp(comp)
204 unguarded_iterator<RandomAccessIterator, Comparator>&
213 typename std::iterator_traits<RandomAccessIterator>::value_type&
219 operator RandomAccessIterator()
223 operator< <RandomAccessIterator, Comparator>(
224 unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
225 unguarded_iterator<RandomAccessIterator, Comparator>& bi2);
228 operator<= <RandomAccessIterator, Comparator>(
229 unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
230 unguarded_iterator<RandomAccessIterator, Comparator>& bi2);
237 template<
typename RandomAccessIterator,
typename Comparator>
239 operator<(unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
240 unguarded_iterator<RandomAccessIterator, Comparator>& bi2)
243 return (bi1.comp)(*bi1, *bi2);
250 template<
typename RandomAccessIterator,
typename Comparator>
252 operator<=(unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
253 unguarded_iterator<RandomAccessIterator, Comparator>& bi2)
256 return !(bi1.comp)(*bi2, *bi1);
284 template<
template<
typename RAI,
typename C>
class iterator,
285 typename RandomAccessIteratorIterator,
286 typename RandomAccessIterator3,
287 typename _DifferenceTp,
289 RandomAccessIterator3
291 RandomAccessIteratorIterator seqs_begin,
292 RandomAccessIteratorIterator seqs_end,
293 RandomAccessIterator3 target,
294 _DifferenceTp length, Comparator comp)
298 typedef _DifferenceTp difference_type;
301 ::value_type::first_type
302 RandomAccessIterator1;
303 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
309 #if _GLIBCXX_ASSERTIONS
310 _DifferenceTp orig_length = length;
313 iterator<RandomAccessIterator1, Comparator>
314 seq0(seqs_begin[0].first, seqs_begin[0].second, comp),
315 seq1(seqs_begin[1].first, seqs_begin[1].second, comp),
316 seq2(seqs_begin[2].first, seqs_begin[2].second, comp);
340 #define _GLIBCXX_PARALLEL_MERGE_3_CASE(a,b,c,c0,c1) \
342 *target = *seq ## a; \
346 if (length == 0) goto finish; \
347 if (seq ## a c0 seq ## b) goto s ## a ## b ## c; \
348 if (seq ## a c1 seq ## c) goto s ## b ## a ## c; \
349 goto s ## b ## c ## a;
351 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 1, 2, <=, <=);
352 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 2, 0, <=, < );
353 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 0, 1, < , < );
354 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 0, 2, < , <=);
355 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 2, 1, <=, <=);
356 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 1, 0, < , < );
358 #undef _GLIBCXX_PARALLEL_MERGE_3_CASE
363 #if _GLIBCXX_ASSERTIONS
364 _GLIBCXX_PARALLEL_ASSERT(
365 ((RandomAccessIterator1)seq0 - seqs_begin[0].first) +
366 ((RandomAccessIterator1)seq1 - seqs_begin[1].first) +
367 ((RandomAccessIterator1)seq2 - seqs_begin[2].first)
371 seqs_begin[0].first = seq0;
372 seqs_begin[1].first = seq1;
373 seqs_begin[2].first = seq2;
404 template<
template<
typename RAI,
typename C>
class iterator,
405 typename RandomAccessIteratorIterator,
406 typename RandomAccessIterator3,
407 typename _DifferenceTp,
409 RandomAccessIterator3
411 RandomAccessIteratorIterator seqs_end,
412 RandomAccessIterator3 target,
413 _DifferenceTp length, Comparator comp)
416 typedef _DifferenceTp difference_type;
419 ::value_type::first_type
420 RandomAccessIterator1;
421 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
424 iterator<RandomAccessIterator1, Comparator>
425 seq0(seqs_begin[0].first, seqs_begin[0].second, comp),
426 seq1(seqs_begin[1].first, seqs_begin[1].second, comp),
427 seq2(seqs_begin[2].first, seqs_begin[2].second, comp),
428 seq3(seqs_begin[3].first, seqs_begin[3].second, comp);
430 #define _GLIBCXX_PARALLEL_DECISION(a,b,c,d) { \
431 if (seq ## d < seq ## a) goto s ## d ## a ## b ## c; \
432 if (seq ## d < seq ## b) goto s ## a ## d ## b ## c; \
433 if (seq ## d < seq ## c) goto s ## a ## b ## d ## c; \
434 goto s ## a ## b ## c ## d; }
439 _GLIBCXX_PARALLEL_DECISION(0,1,2,3)
442 _GLIBCXX_PARALLEL_DECISION(2,0,1,3)
444 _GLIBCXX_PARALLEL_DECISION(0,2,1,3)
451 _GLIBCXX_PARALLEL_DECISION(1,0,2,3)
453 _GLIBCXX_PARALLEL_DECISION(1,2,0,3)
456 _GLIBCXX_PARALLEL_DECISION(2,1,0,3)
459 #define _GLIBCXX_PARALLEL_MERGE_4_CASE(a,b,c,d,c0,c1,c2) \
460 s ## a ## b ## c ## d: \
461 if (length == 0) goto finish; \
462 *target = *seq ## a; \
466 if (seq ## a c0 seq ## b) goto s ## a ## b ## c ## d; \
467 if (seq ## a c1 seq ## c) goto s ## b ## a ## c ## d; \
468 if (seq ## a c2 seq ## d) goto s ## b ## c ## a ## d; \
469 goto s ## b ## c ## d ## a;
471 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 2, 3, <=, <=, <=);
472 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 3, 2, <=, <=, <=);
473 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 1, 3, <=, <=, <=);
474 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 3, 1, <=, <=, <=);
475 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 1, 2, <=, <=, <=);
476 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 2, 1, <=, <=, <=);
477 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 2, 3, < , <=, <=);
478 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 3, 2, < , <=, <=);
479 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 0, 3, <=, < , <=);
480 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 3, 0, <=, <=, < );
481 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 0, 2, <=, < , <=);
482 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 2, 0, <=, <=, < );
483 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 1, 3, < , < , <=);
484 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 3, 1, < , <=, < );
485 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 0, 3, < , < , <=);
486 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 3, 0, < , <=, < );
487 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 0, 1, <=, < , < );
488 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 1, 0, <=, < , < );
489 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 1, 2, < , < , < );
490 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 2, 1, < , < , < );
491 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 0, 2, < , < , < );
492 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 2, 0, < , < , < );
493 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 0, 1, < , < , < );
494 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 1, 0, < , < , < );
496 #undef _GLIBCXX_PARALLEL_MERGE_4_CASE
497 #undef _GLIBCXX_PARALLEL_DECISION
502 seqs_begin[0].first = seq0;
503 seqs_begin[1].first = seq1;
504 seqs_begin[2].first = seq2;
505 seqs_begin[3].first = seq3;
528 template<
typename LT,
529 typename RandomAccessIteratorIterator,
530 typename RandomAccessIterator3,
531 typename _DifferenceTp,
533 RandomAccessIterator3
535 RandomAccessIteratorIterator seqs_end,
536 RandomAccessIterator3 target,
537 _DifferenceTp length, Comparator comp)
541 typedef _DifferenceTp difference_type;
543 ::value_type::first_type
544 RandomAccessIterator1;
545 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
548 int k =
static_cast<int>(seqs_end - seqs_begin);
553 value_type* arbitrary_element = NULL;
555 for (
int t = 0; t < k; ++t)
557 if(arbitrary_element == NULL
559 arbitrary_element = &(*seqs_begin[t].first);
562 for (
int t = 0; t < k; ++t)
564 if (seqs_begin[t].first == seqs_begin[t].second)
565 lt.insert_start(*arbitrary_element, t,
true);
567 lt.insert_start(*seqs_begin[t].first, t,
false);
574 for (difference_type i = 0; i < length; ++i)
577 source = lt.get_min_source();
579 *(target++) = *(seqs_begin[source].first++);
582 if (seqs_begin[source].first == seqs_begin[source].second)
583 lt.delete_min_insert(*arbitrary_element,
true);
586 lt.delete_min_insert(*seqs_begin[source].first,
false);
610 template<
typename LT,
611 typename RandomAccessIteratorIterator,
612 typename RandomAccessIterator3,
613 typename _DifferenceTp,
typename Comparator>
614 RandomAccessIterator3
616 RandomAccessIteratorIterator seqs_begin,
617 RandomAccessIteratorIterator seqs_end,
618 RandomAccessIterator3 target,
620 RandomAccessIteratorIterator>::value_type::first_type>::value_type&
622 _DifferenceTp length,
626 typedef _DifferenceTp difference_type;
629 ::value_type::first_type
630 RandomAccessIterator1;
631 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
634 int k = seqs_end - seqs_begin;
636 LT lt(k, sentinel, comp);
638 for (
int t = 0; t < k; ++t)
640 #if _GLIBCXX_ASSERTIONS
641 _GLIBCXX_PARALLEL_ASSERT(seqs_begin[t].first != seqs_begin[t].second);
643 lt.insert_start(*seqs_begin[t].first, t,
false);
650 #if _GLIBCXX_ASSERTIONS
651 difference_type i = 0;
654 RandomAccessIterator3 target_end = target + length;
655 while (target < target_end)
658 source = lt.get_min_source();
660 #if _GLIBCXX_ASSERTIONS
661 _GLIBCXX_PARALLEL_ASSERT(0 <= source && source < k);
662 _GLIBCXX_PARALLEL_ASSERT(i == 0
663 || !comp(*(seqs_begin[source].first), *(target - 1)));
667 *(target++) = *(seqs_begin[source].first++);
669 #if _GLIBCXX_ASSERTIONS
673 lt.delete_min_insert(*seqs_begin[source].first,
false);
699 typename UnguardedLoserTree,
700 typename RandomAccessIteratorIterator,
701 typename RandomAccessIterator3,
702 typename _DifferenceTp,
704 RandomAccessIterator3
706 RandomAccessIteratorIterator seqs_begin,
707 RandomAccessIteratorIterator seqs_end,
708 RandomAccessIterator3 target,
710 RandomAccessIteratorIterator>::value_type::first_type>::value_type&
712 _DifferenceTp length,
717 typedef _DifferenceTp difference_type;
720 ::value_type::first_type
721 RandomAccessIterator1;
722 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
725 RandomAccessIterator3 target_end;
727 for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s)
736 (seqs_begin, seqs_end, target, sentinel, length, comp);
738 #if _GLIBCXX_ASSERTIONS
739 _GLIBCXX_PARALLEL_ASSERT(target_end == target + length);
740 _GLIBCXX_PARALLEL_ASSERT(
is_sorted(target, target_end, comp));
745 for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s)
775 template <
typename T>
794 typename RandomAccessIteratorIterator,
795 typename RandomAccessIterator3,
796 typename _DifferenceTp,
800 RandomAccessIterator3 operator()(
801 RandomAccessIteratorIterator seqs_begin,
802 RandomAccessIteratorIterator seqs_end,
803 RandomAccessIterator3 target,
804 _DifferenceTp length, Comparator comp)
806 return multiway_merge_3_variant<guarded_iterator>(
807 seqs_begin, seqs_end, target, length, comp);
817 typename RandomAccessIteratorIterator,
818 typename RandomAccessIterator3,
819 typename _DifferenceTp,
822 <true, RandomAccessIteratorIterator, RandomAccessIterator3,
823 _DifferenceTp, Comparator>
825 RandomAccessIterator3 operator()(
826 RandomAccessIteratorIterator seqs_begin,
827 RandomAccessIteratorIterator seqs_end,
828 RandomAccessIterator3 target,
829 _DifferenceTp length, Comparator comp)
831 return multiway_merge_3_variant<unguarded_iterator>(
832 seqs_begin, seqs_end, target, length, comp);
843 typename RandomAccessIteratorIterator,
844 typename RandomAccessIterator3,
845 typename _DifferenceTp,
849 RandomAccessIterator3 operator()(
850 RandomAccessIteratorIterator seqs_begin,
851 RandomAccessIteratorIterator seqs_end,
852 RandomAccessIterator3 target,
853 _DifferenceTp length, Comparator comp)
855 return multiway_merge_4_variant<guarded_iterator>(
856 seqs_begin, seqs_end, target, length, comp);
866 typename RandomAccessIteratorIterator,
867 typename RandomAccessIterator3,
868 typename _DifferenceTp,
871 <true, RandomAccessIteratorIterator, RandomAccessIterator3,
872 _DifferenceTp, Comparator>
874 RandomAccessIterator3 operator()(
875 RandomAccessIteratorIterator seqs_begin,
876 RandomAccessIteratorIterator seqs_end,
877 RandomAccessIterator3 target,
878 _DifferenceTp length, Comparator comp)
880 return multiway_merge_4_variant<unguarded_iterator>(
881 seqs_begin, seqs_end, target, length, comp);
891 typename RandomAccessIteratorIterator,
892 typename RandomAccessIterator3,
893 typename _DifferenceTp,
897 RandomAccessIterator3 operator()(
898 RandomAccessIteratorIterator seqs_begin,
899 RandomAccessIteratorIterator seqs_end,
900 RandomAccessIterator3 target,
902 RandomAccessIteratorIterator>::value_type::first_type>::value_type&
904 _DifferenceTp length, Comparator comp)
907 ::value_type::first_type
908 RandomAccessIterator1;
909 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
913 typename __gnu_cxx::__conditional_type<
917 >::__type>(seqs_begin, seqs_end, target, sentinel, length, comp);
926 typename RandomAccessIteratorIterator,
927 typename RandomAccessIterator3,
928 typename _DifferenceTp,
931 <false, stable, RandomAccessIteratorIterator, RandomAccessIterator3,
932 _DifferenceTp, Comparator>
934 RandomAccessIterator3 operator()(
935 RandomAccessIteratorIterator seqs_begin,
936 RandomAccessIteratorIterator seqs_end,
937 RandomAccessIterator3 target,
939 RandomAccessIteratorIterator>::value_type::first_type>::value_type&
941 _DifferenceTp length, Comparator comp)
944 ::value_type::first_type
945 RandomAccessIterator1;
946 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
950 typename __gnu_cxx::__conditional_type<
954 >::__type >(seqs_begin, seqs_end, target, length, comp);
974 typename RandomAccessIteratorIterator,
975 typename RandomAccessIterator3,
976 typename _DifferenceTp,
978 RandomAccessIterator3
980 RandomAccessIteratorIterator seqs_begin,
981 RandomAccessIteratorIterator seqs_end,
982 RandomAccessIterator3 target,
984 RandomAccessIteratorIterator>::value_type::first_type>::value_type&
986 _DifferenceTp length, Comparator comp)
990 typedef _DifferenceTp difference_type;
992 ::value_type::first_type
993 RandomAccessIterator1;
994 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
997 #if _GLIBCXX_ASSERTIONS
998 for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s)
1000 _GLIBCXX_PARALLEL_ASSERT(
is_sorted((*s).first, (*s).second, comp));
1004 _DifferenceTp total_length = 0;
1005 for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s)
1008 length = std::min<_DifferenceTp>(length, total_length);
1013 RandomAccessIterator3 return_target = target;
1014 int k =
static_cast<int>(seqs_end - seqs_begin);
1021 return_target = std::copy(seqs_begin[0].first,
1022 seqs_begin[0].first + length,
1024 seqs_begin[0].first += length;
1028 seqs_begin[0].second,
1029 seqs_begin[1].first,
1030 seqs_begin[1].second,
1031 target, length, comp);
1036 , RandomAccessIteratorIterator
1037 , RandomAccessIterator3
1039 , Comparator>()(seqs_begin, seqs_end, target, length, comp);
1044 , RandomAccessIteratorIterator
1045 , RandomAccessIterator3
1047 , Comparator>()(seqs_begin, seqs_end, target, length, comp);
1053 , RandomAccessIteratorIterator
1054 , RandomAccessIterator3
1056 , Comparator>()(seqs_begin, seqs_end, target, sentinel, length, comp);
1059 #if _GLIBCXX_ASSERTIONS
1060 _GLIBCXX_PARALLEL_ASSERT(
is_sorted(target, target + length, comp));
1063 return return_target;
1071 template<
bool stable,
class RandomAccessIterator,
class StrictWeakOrdering>
1074 void operator()(RandomAccessIterator first, RandomAccessIterator last,
1075 StrictWeakOrdering comp)
1076 { __gnu_sequential::stable_sort(first, last, comp); }
1084 template<
class RandomAccessIterator,
class StrictWeakOrdering>
1087 void operator()(RandomAccessIterator first, RandomAccessIterator last,
1088 StrictWeakOrdering comp)
1089 { __gnu_sequential::sort(first, last, comp); }
1097 ,
typename RandomAccessIteratorIterator
1098 ,
typename Comparator
1099 ,
typename difference_type>
1101 RandomAccessIteratorIterator seqs_begin,
1102 RandomAccessIteratorIterator seqs_end,
1103 difference_type length, difference_type total_length, Comparator comp,
1107 ::value_type::first_type
1108 RandomAccessIterator1;
1109 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
1113 int k =
static_cast<int>(seqs_end - seqs_begin);
1115 int num_threads = omp_get_num_threads();
1117 difference_type num_samples =
1120 value_type* samples =
static_cast<value_type*
>(
1121 ::operator
new(
sizeof(value_type) * k * num_samples));
1123 for (
int s = 0; s < k; ++s)
1124 for (difference_type i = 0; i < num_samples; ++i)
1126 difference_type sample_index =
1127 static_cast<difference_type
>(
1129 * (double(i + 1) / (num_samples + 1))
1130 * (double(length) / total_length));
1131 new(&(samples[s * num_samples + i]))
1132 value_type(seqs_begin[s].first[sample_index]);
1138 samples, samples + (num_samples * k), comp);
1140 for (
int slab = 0; slab < num_threads; ++slab)
1142 for (
int seq = 0; seq < k; ++seq)
1146 pieces[slab][seq].first =
1148 seqs_begin[seq].first,
1149 seqs_begin[seq].second,
1150 samples[num_samples * k * slab / num_threads],
1152 - seqs_begin[seq].first;
1155 pieces[slab][seq].first = 0;
1156 if ((slab + 1) < num_threads)
1157 pieces[slab][seq].second =
1159 seqs_begin[seq].first,
1160 seqs_begin[seq].second,
1161 samples[num_samples * k * (slab + 1) /
1163 - seqs_begin[seq].first;
1168 ::operator
delete(samples);
1178 ,
typename RandomAccessIteratorIterator
1179 ,
typename Comparator
1180 ,
typename difference_type>
1182 RandomAccessIteratorIterator seqs_begin,
1183 RandomAccessIteratorIterator seqs_end,
1184 difference_type length, difference_type total_length, Comparator comp,
1188 ::value_type::first_type
1189 RandomAccessIterator1;
1191 const bool tight = (total_length == length);
1194 const int k =
static_cast<int>(seqs_end - seqs_begin);
1196 const int num_threads = omp_get_num_threads();
1205 copy(seqs_begin, seqs_end, se.begin());
1207 difference_type* borders =
1208 new difference_type[num_threads + 1];
1211 for (
int s = 0; s < (num_threads - 1); ++s)
1215 se.begin(), se.end(), borders[s + 1],
1216 offsets[s].
begin(), comp);
1221 offsets[num_threads - 1].
resize(k);
1223 difference_type(length),
1224 offsets[num_threads - 1].
begin(), comp);
1229 for (
int slab = 0; slab < num_threads; ++slab)
1232 for (
int seq = 0; seq < k; ++seq)
1238 pieces[slab][seq].first = 0;
1241 pieces[slab][seq].first =
1242 pieces[slab - 1][seq].second;
1243 if (!tight || slab < (num_threads - 1))
1244 pieces[slab][seq].second =
1245 offsets[slab][seq] - seqs_begin[seq].first;
1249 pieces[slab][seq].second =
1279 typename RandomAccessIteratorIterator,
1280 typename RandomAccessIterator3,
1281 typename _DifferenceTp,
1285 RandomAccessIterator3
1287 RandomAccessIteratorIterator seqs_end,
1288 RandomAccessIterator3 target,
1290 _DifferenceTp length,
1294 #if _GLIBCXX_ASSERTIONS
1295 _GLIBCXX_PARALLEL_ASSERT(seqs_end - seqs_begin > 1);
1300 typedef _DifferenceTp difference_type;
1302 ::value_type::first_type
1303 RandomAccessIterator1;
1305 std::iterator_traits<RandomAccessIterator1>::value_type value_type;
1309 seq_type* ne_seqs =
new seq_type[seqs_end - seqs_begin];
1311 difference_type total_length = 0;
1312 for (RandomAccessIteratorIterator raii = seqs_begin;
1313 raii != seqs_end; ++raii)
1318 total_length += seq_length;
1319 ne_seqs[k++] = *raii;
1325 length = std::min<_DifferenceTp>(length, total_length);
1327 if (total_length == 0 || k == 0)
1336 (std::min<difference_type>(num_threads, total_length));
1338 # pragma omp parallel num_threads (num_threads)
1342 num_threads = omp_get_num_threads();
1346 for (
int s = 0; s < num_threads; ++s)
1347 pieces[s].resize(k);
1349 difference_type num_samples =
1353 splitter(ne_seqs, ne_seqs + k, length, total_length,
1359 difference_type target_position = 0;
1361 for (
int c = 0; c < k; ++c)
1362 target_position += pieces[iam][c].first;
1364 seq_type* chunks =
new seq_type[k];
1366 for (
int s = 0; s < k; ++s)
1368 chunks[s] = std::make_pair(
1369 ne_seqs[s].first + pieces[iam][s].first,
1370 ne_seqs[s].first + pieces[iam][s].second);
1373 if(length > target_position)
1374 sequential_multiway_merge<stable, sentinels>(
1375 chunks, chunks + k, target + target_position,
1376 *(seqs_begin->second), length - target_position, comp);
1381 #if _GLIBCXX_ASSERTIONS
1382 _GLIBCXX_PARALLEL_ASSERT(
is_sorted(target, target + length, comp));
1387 for (RandomAccessIteratorIterator raii = seqs_begin;
1388 raii != seqs_end; ++raii)
1392 (*raii).first += pieces[num_threads - 1][k++].second;
1398 return target + length;
1472 typename RandomAccessIteratorPairIterator
1473 ,
typename RandomAccessIteratorOut
1474 ,
typename _DifferenceTp
1475 ,
typename Comparator>
1476 RandomAccessIteratorOut
1478 , RandomAccessIteratorPairIterator seqs_end
1479 , RandomAccessIteratorOut target
1480 , _DifferenceTp length, Comparator comp
1483 typedef _DifferenceTp difference_type;
1487 if (seqs_begin == seqs_end)
1493 (seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
1498 typename RandomAccessIteratorPairIterator
1499 ,
typename RandomAccessIteratorOut
1500 ,
typename _DifferenceTp
1501 ,
typename Comparator>
1502 RandomAccessIteratorOut
1504 , RandomAccessIteratorPairIterator seqs_end
1505 , RandomAccessIteratorOut target
1506 , _DifferenceTp length, Comparator comp
1509 typedef _DifferenceTp difference_type;
1513 if (seqs_begin == seqs_end)
1519 if ((seqs_end - seqs_begin > 1) &&
1521 ((seqs_end - seqs_begin) >=
1522 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1524 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1527 seqs_begin, seqs_end, target,
1529 typename std::iterator_traits<RandomAccessIteratorPairIterator>
1530 ::value_type*, Comparator, _DifferenceTp>,
1531 static_cast<difference_type>(length), comp, tag.get_num_threads());
1535 seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
1540 typename RandomAccessIteratorPairIterator
1541 , typename RandomAccessIteratorOut
1542 , typename _DifferenceTp
1543 , typename Comparator>
1544 RandomAccessIteratorOut
1546 , RandomAccessIteratorPairIterator seqs_end
1547 , RandomAccessIteratorOut target
1548 , _DifferenceTp length, Comparator comp
1549 , __gnu_parallel::sampling_tag tag)
1551 typedef _DifferenceTp difference_type;
1555 if (seqs_begin == seqs_end)
1561 if ((seqs_end - seqs_begin > 1) &&
1563 ((seqs_end - seqs_begin) >=
1564 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1566 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1569 seqs_begin, seqs_end,
1572 typename std::iterator_traits<RandomAccessIteratorPairIterator>
1573 ::value_type*, Comparator, _DifferenceTp>,
1574 static_cast<difference_type>(length), comp, tag.get_num_threads());
1578 seqs_begin, seqs_end,
1579 target, *(seqs_begin->second), length, comp);
1584 typename RandomAccessIteratorPairIterator
1585 , typename RandomAccessIteratorOut
1586 , typename _DifferenceTp
1587 , typename Comparator>
1588 RandomAccessIteratorOut
1590 , RandomAccessIteratorPairIterator seqs_end
1591 , RandomAccessIteratorOut target
1592 , _DifferenceTp length, Comparator comp
1593 , parallel_tag tag = parallel_tag(0))
1595 return multiway_merge(seqs_begin, seqs_end, target, length, comp,
1596 exact_tag(tag.get_num_threads()));
1601 typename RandomAccessIteratorPairIterator
1602 ,
typename RandomAccessIteratorOut
1603 ,
typename _DifferenceTp
1604 ,
typename Comparator>
1605 RandomAccessIteratorOut
1607 , RandomAccessIteratorPairIterator seqs_end
1608 , RandomAccessIteratorOut target
1609 , _DifferenceTp length, Comparator comp
1610 , default_parallel_tag tag)
1612 return multiway_merge(seqs_begin, seqs_end, target, length, comp,
1613 exact_tag(tag.get_num_threads()));
1619 typename RandomAccessIteratorPairIterator
1620 ,
typename RandomAccessIteratorOut
1621 ,
typename _DifferenceTp
1622 ,
typename Comparator>
1623 RandomAccessIteratorOut
1624 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1625 , RandomAccessIteratorPairIterator seqs_end
1626 , RandomAccessIteratorOut target
1627 , _DifferenceTp length, Comparator comp
1630 typedef _DifferenceTp difference_type;
1634 if (seqs_begin == seqs_end)
1640 (seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
1645 typename RandomAccessIteratorPairIterator
1646 , typename RandomAccessIteratorOut
1647 , typename _DifferenceTp
1648 , typename Comparator>
1649 RandomAccessIteratorOut
1650 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1651 , RandomAccessIteratorPairIterator seqs_end
1652 , RandomAccessIteratorOut target
1653 , _DifferenceTp length, Comparator comp
1654 , __gnu_parallel::exact_tag tag)
1656 typedef _DifferenceTp difference_type;
1660 if (seqs_begin == seqs_end)
1666 if ((seqs_end - seqs_begin > 1) &&
1668 ((seqs_end - seqs_begin) >=
1669 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1671 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1674 seqs_begin, seqs_end,
1677 typename std::iterator_traits<RandomAccessIteratorPairIterator>
1678 ::value_type*, Comparator, _DifferenceTp>,
1679 static_cast<difference_type>(length), comp, tag.get_num_threads());
1683 seqs_begin, seqs_end,
1684 target, *(seqs_begin->second), length, comp);
1689 typename RandomAccessIteratorPairIterator
1690 , typename RandomAccessIteratorOut
1691 , typename _DifferenceTp
1692 , typename Comparator>
1693 RandomAccessIteratorOut
1694 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1695 , RandomAccessIteratorPairIterator seqs_end
1696 , RandomAccessIteratorOut target
1697 , _DifferenceTp length, Comparator comp
1700 typedef _DifferenceTp difference_type;
1704 if (seqs_begin == seqs_end)
1710 if ((seqs_end - seqs_begin > 1) &&
1712 ((seqs_end - seqs_begin) >=
1713 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1715 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1718 seqs_begin, seqs_end,
1721 typename std::iterator_traits<RandomAccessIteratorPairIterator>
1722 ::value_type*, Comparator, _DifferenceTp>,
1723 static_cast<difference_type>(length), comp, tag.get_num_threads());
1727 seqs_begin, seqs_end,
1728 target, *(seqs_begin->second), length, comp);
1734 typename RandomAccessIteratorPairIterator
1735 , typename RandomAccessIteratorOut
1736 , typename _DifferenceTp
1737 , typename Comparator>
1738 RandomAccessIteratorOut
1739 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1740 , RandomAccessIteratorPairIterator seqs_end
1741 , RandomAccessIteratorOut target
1742 , _DifferenceTp length, Comparator comp
1743 , parallel_tag tag = parallel_tag(0))
1745 return stable_multiway_merge(seqs_begin, seqs_end, target, length, comp,
1746 exact_tag(tag.get_num_threads()));
1751 typename RandomAccessIteratorPairIterator
1752 ,
typename RandomAccessIteratorOut
1753 ,
typename _DifferenceTp
1754 ,
typename Comparator>
1755 RandomAccessIteratorOut
1756 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1757 , RandomAccessIteratorPairIterator seqs_end
1758 , RandomAccessIteratorOut target
1759 , _DifferenceTp length, Comparator comp
1760 , default_parallel_tag tag)
1762 return stable_multiway_merge(seqs_begin, seqs_end, target, length, comp,
1763 exact_tag(tag.get_num_threads()));
1844 typename RandomAccessIteratorPairIterator
1845 ,
typename RandomAccessIteratorOut
1846 ,
typename _DifferenceTp
1847 ,
typename Comparator>
1848 RandomAccessIteratorOut
1850 , RandomAccessIteratorPairIterator seqs_end
1851 , RandomAccessIteratorOut target
1852 , _DifferenceTp length, Comparator comp
1855 typedef _DifferenceTp difference_type;
1859 if (seqs_begin == seqs_end)
1865 (seqs_begin, seqs_end,
1866 target, *(seqs_begin->second), length, comp);
1871 typename RandomAccessIteratorPairIterator
1872 ,
typename RandomAccessIteratorOut
1873 ,
typename _DifferenceTp
1874 ,
typename Comparator>
1875 RandomAccessIteratorOut
1877 , RandomAccessIteratorPairIterator seqs_end
1878 , RandomAccessIteratorOut target
1879 , _DifferenceTp length, Comparator comp
1882 typedef _DifferenceTp difference_type;
1886 if (seqs_begin == seqs_end)
1892 if ((seqs_end - seqs_begin > 1) &&
1894 ((seqs_end - seqs_begin) >=
1895 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1897 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1900 seqs_begin, seqs_end,
1903 typename std::iterator_traits<RandomAccessIteratorPairIterator>
1904 ::value_type*, Comparator, _DifferenceTp>,
1905 static_cast<difference_type>(length), comp, tag.get_num_threads());
1909 seqs_begin, seqs_end,
1910 target, *(seqs_begin->second), length, comp);
1915 typename RandomAccessIteratorPairIterator
1916 , typename RandomAccessIteratorOut
1917 , typename _DifferenceTp
1918 , typename Comparator>
1919 RandomAccessIteratorOut
1921 , RandomAccessIteratorPairIterator seqs_end
1922 , RandomAccessIteratorOut target
1923 , _DifferenceTp length, Comparator comp
1926 typedef _DifferenceTp difference_type;
1930 if (seqs_begin == seqs_end)
1936 if ((seqs_end - seqs_begin > 1) &&
1938 ((seqs_end - seqs_begin) >=
1939 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1941 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1944 (seqs_begin, seqs_end, target,
1946 typename std::iterator_traits<RandomAccessIteratorPairIterator>
1947 ::value_type*, Comparator, _DifferenceTp>,
1948 static_cast<difference_type>(length), comp, tag.get_num_threads());
1952 seqs_begin, seqs_end,
1953 target, *(seqs_begin->second), length, comp);
1958 typename RandomAccessIteratorPairIterator
1959 , typename RandomAccessIteratorOut
1960 , typename _DifferenceTp
1961 , typename Comparator>
1962 RandomAccessIteratorOut
1964 , RandomAccessIteratorPairIterator seqs_end
1965 , RandomAccessIteratorOut target
1966 , _DifferenceTp length, Comparator comp
1967 , parallel_tag tag = parallel_tag(0))
1970 exact_tag(tag.get_num_threads()));
1975 typename RandomAccessIteratorPairIterator
1976 ,
typename RandomAccessIteratorOut
1977 ,
typename _DifferenceTp
1978 ,
typename Comparator>
1979 RandomAccessIteratorOut
1981 , RandomAccessIteratorPairIterator seqs_end
1982 , RandomAccessIteratorOut target
1983 , _DifferenceTp length, Comparator comp
1984 , default_parallel_tag tag)
1987 exact_tag(tag.get_num_threads()));
1993 typename RandomAccessIteratorPairIterator
1994 ,
typename RandomAccessIteratorOut
1995 ,
typename _DifferenceTp
1996 ,
typename Comparator>
1997 RandomAccessIteratorOut
1998 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1999 , RandomAccessIteratorPairIterator seqs_end
2000 , RandomAccessIteratorOut target
2001 , _DifferenceTp length, Comparator comp
2004 typedef _DifferenceTp difference_type;
2008 if (seqs_begin == seqs_end)
2014 (seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
2019 typename RandomAccessIteratorPairIterator
2020 , typename RandomAccessIteratorOut
2021 , typename _DifferenceTp
2022 , typename Comparator>
2023 RandomAccessIteratorOut
2024 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
2025 , RandomAccessIteratorPairIterator seqs_end
2026 , RandomAccessIteratorOut target
2027 , _DifferenceTp length, Comparator comp
2028 , __gnu_parallel::exact_tag tag)
2030 typedef _DifferenceTp difference_type;
2034 if (seqs_begin == seqs_end)
2040 if ((seqs_end - seqs_begin > 1) &&
2042 ((seqs_end - seqs_begin) >=
2043 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
2045 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
2048 seqs_begin, seqs_end,
2051 typename std::iterator_traits<RandomAccessIteratorPairIterator>
2052 ::value_type*, Comparator, _DifferenceTp>,
2053 static_cast<difference_type>(length), comp, tag.get_num_threads());
2057 seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
2062 typename RandomAccessIteratorPairIterator
2063 , typename RandomAccessIteratorOut
2064 , typename _DifferenceTp
2065 , typename Comparator>
2066 RandomAccessIteratorOut
2067 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
2068 , RandomAccessIteratorPairIterator seqs_end
2069 , RandomAccessIteratorOut target
2070 , _DifferenceTp length, Comparator comp
2073 typedef _DifferenceTp difference_type;
2077 if (seqs_begin == seqs_end)
2083 if ((seqs_end - seqs_begin > 1) &&
2085 ((seqs_end - seqs_begin) >=
2086 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
2088 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
2091 seqs_begin, seqs_end,
2094 typename std::iterator_traits<RandomAccessIteratorPairIterator>
2095 ::value_type*, Comparator, _DifferenceTp>,
2096 static_cast<difference_type>(length), comp, tag.get_num_threads());
2100 seqs_begin, seqs_end,
2101 target, *(seqs_begin->second), length, comp);
2106 typename RandomAccessIteratorPairIterator
2107 , typename RandomAccessIteratorOut
2108 , typename _DifferenceTp
2109 , typename Comparator>
2110 RandomAccessIteratorOut
2111 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
2112 , RandomAccessIteratorPairIterator seqs_end
2113 , RandomAccessIteratorOut target
2114 , _DifferenceTp length, Comparator comp
2115 , parallel_tag tag = parallel_tag(0))
2117 return stable_multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp,
2118 exact_tag(tag.get_num_threads()));
2123 typename RandomAccessIteratorPairIterator
2124 ,
typename RandomAccessIteratorOut
2125 ,
typename _DifferenceTp
2126 ,
typename Comparator>
2127 RandomAccessIteratorOut
2128 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
2129 , RandomAccessIteratorPairIterator seqs_end
2130 , RandomAccessIteratorOut target
2131 , _DifferenceTp length, Comparator comp
2132 , default_parallel_tag tag)
2134 return stable_multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp,
2135 exact_tag(tag.get_num_threads()));
RandomAccessIterator3 multiway_merge_loser_tree_sentinel(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::value_type &sentinel, _DifferenceTp length, Comparator comp)
Multi-way merging procedure for a high branching factor, requiring sentinels to exist.
void multiseq_partition(RanSeqs begin_seqs, RanSeqs end_seqs, RankType rank, RankIterator begin_offsets, Comparator 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 seq...
static const _Settings & get()
Get the global settings.
Stable unguarded LoserTree variant storing pointers.
void multiway_merge_sampling_splitting(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, difference_type length, difference_type total_length, Comparator comp, std::vector< std::pair< difference_type, difference_type > > *pieces)
Sampling based splitting for parallel multiway-merge routine.
guarded_iterator< RandomAccessIterator, Comparator > & operator++()
Pre-increment operator.
RandomAccessIteratorOut multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, __gnu_parallel::sequential_tag)
Multiway Merge Frontend.
static const bool use_pointer
True iff to use pointers instead of values in loser trees.
pair holds two objects of arbitrary type.
Stable implementation of unguarded LoserTree.
Traits for determining whether the loser tree should use pointers or copies.
#define _GLIBCXX_PARALLEL_CONDITION(c)
Determine at compile(?)-time if the parallel variant of an algorithm should be called.
RandomAccessIteratorOut multiway_merge(RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, __gnu_parallel::sequential_tag)
Multiway Merge Frontend.
OutputIterator merge_advance(RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp)
Merge routine being able to merge only the max_length smallest elements.
Defines on whether to include algorithm variants.
Many generic loser tree variants. This file is a GNU parallel extension to the Standard C++ Library...
unsigned int merge_oversampling
Oversampling factor for merge.
bool is_sorted(InputIterator begin, InputIterator end, Comparator comp=std::less< typename std::iterator_traits< InputIterator >::value_type >())
Check whether [begin, end) is sorted according to comp.
Forces parallel merging with exact splitting, at compile time.
void resize(size_type __new_size, value_type __x=value_type())
Resizes the vector to the specified number of elements.
Iterator wrapper supporting an implicit supremum at the end of the sequence, dominating all compariso...
uint16 thread_index_t
Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit in...
A standard container which offers fixed time access to individual elements in any order...
RandomAccessIterator3 multiway_merge_3_variant(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, _DifferenceTp length, Comparator comp)
Highly efficient 3-way merging procedure.
void multiway_merge_exact_splitting(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, difference_type length, difference_type total_length, Comparator comp, std::vector< std::pair< difference_type, difference_type > > *pieces)
Exact splitting for parallel multiway-merge routine.
RandomAccessIterator3 multiway_merge_loser_tree(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, _DifferenceTp length, Comparator comp)
Multi-way merging procedure for a high branching factor, guarded case.
std::iterator_traits< RandomAccessIterator >::value_type & operator*()
Dereference operator.
Switch for k-way merging with sentinels turned on.
RandomAccessIterator3 parallel_multiway_merge(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Splitter splitter, _DifferenceTp length, Comparator comp, thread_index_t num_threads)
Parallel multi-way merge routine.
Forces sequential execution at compile time.
#define _GLIBCXX_PARALLEL_LENGTH(s)
Length of a sequence described by a pair of iterators.
Switch for 3-way merging with sentinels turned off.
Stable LoserTree implementation.
uint64 sequence_index_t
Unsigned integer to index elements. The total number of elements for each algorithm must fit into thi...
End-user include file. Provides advanced settings and tuning options. This file is a GNU parallel ext...
RandomAccessIterator3 multiway_merge_4_variant(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, _DifferenceTp length, Comparator comp)
Highly efficient 4-way merging procedure.
RandomAccessIterator3 sequential_multiway_merge(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::value_type &sentinel, _DifferenceTp length, Comparator comp)
Sequential multi-way merging switch.
guarded_iterator(RandomAccessIterator begin, RandomAccessIterator end, Comparator &comp)
Constructor. Sets iterator to beginning of sequence.
OutputIterator equally_split(difference_type n, thread_index_t num_threads, OutputIterator s)
Function to split a sequence into parts of almost equal size.
Stable LoserTree variant.
#define _GLIBCXX_CALL(n)
Macro to produce log message when entering a function.
RandomAccessIterator3 multiway_merge_loser_tree_unguarded(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::value_type &sentinel, _DifferenceTp length, Comparator comp)
Multi-way merging procedure for a high branching factor, unguarded case.
Routines for checking the correctness of algorithm results. This file is a GNU parallel extension to ...
Switch for 4-way merging with sentinels turned off.