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>
61 class guarded_iterator;
65 template<
typename RandomAccessIterator,
typename Comparator>
67 operator<(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
68 guarded_iterator<RandomAccessIterator, Comparator>& bi2);
70 template<
typename RandomAccessIterator,
typename Comparator>
72 operator<=(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
73 guarded_iterator<RandomAccessIterator, Comparator>& bi2);
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()));