00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039 #ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
00040 #define _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
00041
00042 #include <vector>
00043
00044 #include <bits/stl_algo.h>
00045 #include <parallel/features.h>
00046 #include <parallel/parallel.h>
00047 #include <parallel/losertree.h>
00048 #if _GLIBCXX_ASSERTIONS
00049 #include <parallel/checkers.h>
00050 #endif
00051
00052
00053 #define _GLIBCXX_PARALLEL_LENGTH(s) ((s).second - (s).first)
00054
00055 namespace __gnu_parallel
00056 {
00057
00058
00059
00060 template<typename RandomAccessIterator, typename Comparator>
00061 class guarded_iterator;
00062
00063
00064
00065 template<typename RandomAccessIterator, typename Comparator>
00066 inline bool
00067 operator<(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
00068 guarded_iterator<RandomAccessIterator, Comparator>& bi2);
00069
00070 template<typename RandomAccessIterator, typename Comparator>
00071 inline bool
00072 operator<=(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
00073 guarded_iterator<RandomAccessIterator, Comparator>& bi2);
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083 template<typename RandomAccessIterator, typename Comparator>
00084 class guarded_iterator
00085 {
00086 private:
00087
00088 RandomAccessIterator current;
00089
00090
00091 RandomAccessIterator end;
00092
00093
00094 Comparator& comp;
00095
00096 public:
00097
00098
00099
00100
00101
00102 guarded_iterator(RandomAccessIterator begin,
00103 RandomAccessIterator end, Comparator& comp)
00104 : current(begin), end(end), comp(comp)
00105 { }
00106
00107
00108
00109 guarded_iterator<RandomAccessIterator, Comparator>&
00110 operator++()
00111 {
00112 ++current;
00113 return *this;
00114 }
00115
00116
00117
00118 typename std::iterator_traits<RandomAccessIterator>::value_type&
00119 operator*()
00120 { return *current; }
00121
00122
00123
00124 operator RandomAccessIterator()
00125 { return current; }
00126
00127 friend bool
00128 operator< <RandomAccessIterator, Comparator>(
00129 guarded_iterator<RandomAccessIterator, Comparator>& bi1,
00130 guarded_iterator<RandomAccessIterator, Comparator>& bi2);
00131
00132 friend bool
00133 operator<= <RandomAccessIterator, Comparator>(
00134 guarded_iterator<RandomAccessIterator, Comparator>& bi1,
00135 guarded_iterator<RandomAccessIterator, Comparator>& bi2);
00136 };
00137
00138
00139
00140
00141
00142 template<typename RandomAccessIterator, typename Comparator>
00143 inline bool
00144 operator<(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
00145 guarded_iterator<RandomAccessIterator, Comparator>& bi2)
00146 {
00147 if (bi1.current == bi1.end)
00148 return bi2.current == bi2.end;
00149 if (bi2.current == bi2.end)
00150 return true;
00151 return (bi1.comp)(*bi1, *bi2);
00152 }
00153
00154
00155
00156
00157
00158 template<typename RandomAccessIterator, typename Comparator>
00159 inline bool
00160 operator<=(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
00161 guarded_iterator<RandomAccessIterator, Comparator>& bi2)
00162 {
00163 if (bi2.current == bi2.end)
00164 return bi1.current != bi1.end;
00165 if (bi1.current == bi1.end)
00166 return false;
00167 return !(bi1.comp)(*bi2, *bi1);
00168 }
00169
00170 template<typename RandomAccessIterator, typename Comparator>
00171 class unguarded_iterator;
00172
00173 template<typename RandomAccessIterator, typename Comparator>
00174 inline bool
00175 operator<(unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
00176 unguarded_iterator<RandomAccessIterator, Comparator>& bi2);
00177
00178 template<typename RandomAccessIterator, typename Comparator>
00179 inline bool
00180 operator<=(unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
00181 unguarded_iterator<RandomAccessIterator, Comparator>& bi2);
00182
00183 template<typename RandomAccessIterator, typename Comparator>
00184 class unguarded_iterator
00185 {
00186 private:
00187
00188 RandomAccessIterator current;
00189
00190 mutable Comparator& comp;
00191
00192 public:
00193
00194
00195
00196
00197 unguarded_iterator(RandomAccessIterator begin,
00198 RandomAccessIterator end, Comparator& comp)
00199 : current(begin), comp(comp)
00200 { }
00201
00202
00203
00204 unguarded_iterator<RandomAccessIterator, Comparator>&
00205 operator++()
00206 {
00207 ++current;
00208 return *this;
00209 }
00210
00211
00212
00213 typename std::iterator_traits<RandomAccessIterator>::value_type&
00214 operator*()
00215 { return *current; }
00216
00217
00218
00219 operator RandomAccessIterator()
00220 { return current; }
00221
00222 friend bool
00223 operator< <RandomAccessIterator, Comparator>(
00224 unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
00225 unguarded_iterator<RandomAccessIterator, Comparator>& bi2);
00226
00227 friend bool
00228 operator<= <RandomAccessIterator, Comparator>(
00229 unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
00230 unguarded_iterator<RandomAccessIterator, Comparator>& bi2);
00231 };
00232
00233
00234
00235
00236
00237 template<typename RandomAccessIterator, typename Comparator>
00238 inline bool
00239 operator<(unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
00240 unguarded_iterator<RandomAccessIterator, Comparator>& bi2)
00241 {
00242
00243 return (bi1.comp)(*bi1, *bi2);
00244 }
00245
00246
00247
00248
00249
00250 template<typename RandomAccessIterator, typename Comparator>
00251 inline bool
00252 operator<=(unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
00253 unguarded_iterator<RandomAccessIterator, Comparator>& bi2)
00254 {
00255
00256 return !(bi1.comp)(*bi2, *bi1);
00257 }
00258
00259
00260
00261
00262
00263
00264
00265
00266
00267
00268
00269
00270
00271
00272
00273
00274
00275
00276
00277
00278
00279
00280
00281
00282
00283
00284 template<template<typename RAI, typename C> class iterator,
00285 typename RandomAccessIteratorIterator,
00286 typename RandomAccessIterator3,
00287 typename _DifferenceTp,
00288 typename Comparator>
00289 RandomAccessIterator3
00290 multiway_merge_3_variant(
00291 RandomAccessIteratorIterator seqs_begin,
00292 RandomAccessIteratorIterator seqs_end,
00293 RandomAccessIterator3 target,
00294 _DifferenceTp length, Comparator comp)
00295 {
00296 _GLIBCXX_CALL(length);
00297
00298 typedef _DifferenceTp difference_type;
00299
00300 typedef typename std::iterator_traits<RandomAccessIteratorIterator>
00301 ::value_type::first_type
00302 RandomAccessIterator1;
00303 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
00304 value_type;
00305
00306 if (length == 0)
00307 return target;
00308
00309 #if _GLIBCXX_ASSERTIONS
00310 _DifferenceTp orig_length = length;
00311 #endif
00312
00313 iterator<RandomAccessIterator1, Comparator>
00314 seq0(seqs_begin[0].first, seqs_begin[0].second, comp),
00315 seq1(seqs_begin[1].first, seqs_begin[1].second, comp),
00316 seq2(seqs_begin[2].first, seqs_begin[2].second, comp);
00317
00318 if (seq0 <= seq1)
00319 {
00320 if (seq1 <= seq2)
00321 goto s012;
00322 else
00323 if (seq2 < seq0)
00324 goto s201;
00325 else
00326 goto s021;
00327 }
00328 else
00329 {
00330 if (seq1 <= seq2)
00331 {
00332 if (seq0 <= seq2)
00333 goto s102;
00334 else
00335 goto s120;
00336 }
00337 else
00338 goto s210;
00339 }
00340 #define _GLIBCXX_PARALLEL_MERGE_3_CASE(a,b,c,c0,c1) \
00341 s ## a ## b ## c : \
00342 *target = *seq ## a; \
00343 ++target; \
00344 --length; \
00345 ++seq ## a; \
00346 if (length == 0) goto finish; \
00347 if (seq ## a c0 seq ## b) goto s ## a ## b ## c; \
00348 if (seq ## a c1 seq ## c) goto s ## b ## a ## c; \
00349 goto s ## b ## c ## a;
00350
00351 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 1, 2, <=, <=);
00352 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 2, 0, <=, < );
00353 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 0, 1, < , < );
00354 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 0, 2, < , <=);
00355 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 2, 1, <=, <=);
00356 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 1, 0, < , < );
00357
00358 #undef _GLIBCXX_PARALLEL_MERGE_3_CASE
00359
00360 finish:
00361 ;
00362
00363 #if _GLIBCXX_ASSERTIONS
00364 _GLIBCXX_PARALLEL_ASSERT(
00365 ((RandomAccessIterator1)seq0 - seqs_begin[0].first) +
00366 ((RandomAccessIterator1)seq1 - seqs_begin[1].first) +
00367 ((RandomAccessIterator1)seq2 - seqs_begin[2].first)
00368 == orig_length);
00369 #endif
00370
00371 seqs_begin[0].first = seq0;
00372 seqs_begin[1].first = seq1;
00373 seqs_begin[2].first = seq2;
00374
00375 return target;
00376 }
00377
00378
00379
00380
00381
00382
00383
00384
00385
00386
00387
00388
00389
00390
00391
00392
00393
00394
00395
00396
00397
00398
00399
00400
00401
00402
00403
00404 template<template<typename RAI, typename C> class iterator,
00405 typename RandomAccessIteratorIterator,
00406 typename RandomAccessIterator3,
00407 typename _DifferenceTp,
00408 typename Comparator>
00409 RandomAccessIterator3
00410 multiway_merge_4_variant(RandomAccessIteratorIterator seqs_begin,
00411 RandomAccessIteratorIterator seqs_end,
00412 RandomAccessIterator3 target,
00413 _DifferenceTp length, Comparator comp)
00414 {
00415 _GLIBCXX_CALL(length);
00416 typedef _DifferenceTp difference_type;
00417
00418 typedef typename std::iterator_traits<RandomAccessIteratorIterator>
00419 ::value_type::first_type
00420 RandomAccessIterator1;
00421 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
00422 value_type;
00423
00424 iterator<RandomAccessIterator1, Comparator>
00425 seq0(seqs_begin[0].first, seqs_begin[0].second, comp),
00426 seq1(seqs_begin[1].first, seqs_begin[1].second, comp),
00427 seq2(seqs_begin[2].first, seqs_begin[2].second, comp),
00428 seq3(seqs_begin[3].first, seqs_begin[3].second, comp);
00429
00430 #define _GLIBCXX_PARALLEL_DECISION(a,b,c,d) { \
00431 if (seq ## d < seq ## a) goto s ## d ## a ## b ## c; \
00432 if (seq ## d < seq ## b) goto s ## a ## d ## b ## c; \
00433 if (seq ## d < seq ## c) goto s ## a ## b ## d ## c; \
00434 goto s ## a ## b ## c ## d; }
00435
00436 if (seq0 <= seq1)
00437 {
00438 if (seq1 <= seq2)
00439 _GLIBCXX_PARALLEL_DECISION(0,1,2,3)
00440 else
00441 if (seq2 < seq0)
00442 _GLIBCXX_PARALLEL_DECISION(2,0,1,3)
00443 else
00444 _GLIBCXX_PARALLEL_DECISION(0,2,1,3)
00445 }
00446 else
00447 {
00448 if (seq1 <= seq2)
00449 {
00450 if (seq0 <= seq2)
00451 _GLIBCXX_PARALLEL_DECISION(1,0,2,3)
00452 else
00453 _GLIBCXX_PARALLEL_DECISION(1,2,0,3)
00454 }
00455 else
00456 _GLIBCXX_PARALLEL_DECISION(2,1,0,3)
00457 }
00458
00459 #define _GLIBCXX_PARALLEL_MERGE_4_CASE(a,b,c,d,c0,c1,c2) \
00460 s ## a ## b ## c ## d: \
00461 if (length == 0) goto finish; \
00462 *target = *seq ## a; \
00463 ++target; \
00464 --length; \
00465 ++seq ## a; \
00466 if (seq ## a c0 seq ## b) goto s ## a ## b ## c ## d; \
00467 if (seq ## a c1 seq ## c) goto s ## b ## a ## c ## d; \
00468 if (seq ## a c2 seq ## d) goto s ## b ## c ## a ## d; \
00469 goto s ## b ## c ## d ## a;
00470
00471 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 2, 3, <=, <=, <=);
00472 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 3, 2, <=, <=, <=);
00473 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 1, 3, <=, <=, <=);
00474 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 3, 1, <=, <=, <=);
00475 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 1, 2, <=, <=, <=);
00476 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 2, 1, <=, <=, <=);
00477 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 2, 3, < , <=, <=);
00478 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 3, 2, < , <=, <=);
00479 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 0, 3, <=, < , <=);
00480 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 3, 0, <=, <=, < );
00481 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 0, 2, <=, < , <=);
00482 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 2, 0, <=, <=, < );
00483 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 1, 3, < , < , <=);
00484 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 3, 1, < , <=, < );
00485 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 0, 3, < , < , <=);
00486 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 3, 0, < , <=, < );
00487 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 0, 1, <=, < , < );
00488 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 1, 0, <=, < , < );
00489 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 1, 2, < , < , < );
00490 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 2, 1, < , < , < );
00491 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 0, 2, < , < , < );
00492 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 2, 0, < , < , < );
00493 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 0, 1, < , < , < );
00494 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 1, 0, < , < , < );
00495
00496 #undef _GLIBCXX_PARALLEL_MERGE_4_CASE
00497 #undef _GLIBCXX_PARALLEL_DECISION
00498
00499 finish:
00500 ;
00501
00502 seqs_begin[0].first = seq0;
00503 seqs_begin[1].first = seq1;
00504 seqs_begin[2].first = seq2;
00505 seqs_begin[3].first = seq3;
00506
00507 return target;
00508 }
00509
00510
00511
00512
00513
00514
00515
00516
00517
00518
00519
00520
00521
00522
00523
00524
00525
00526
00527
00528 template<typename LT,
00529 typename RandomAccessIteratorIterator,
00530 typename RandomAccessIterator3,
00531 typename _DifferenceTp,
00532 typename Comparator>
00533 RandomAccessIterator3
00534 multiway_merge_loser_tree(RandomAccessIteratorIterator seqs_begin,
00535 RandomAccessIteratorIterator seqs_end,
00536 RandomAccessIterator3 target,
00537 _DifferenceTp length, Comparator comp)
00538 {
00539 _GLIBCXX_CALL(length)
00540
00541 typedef _DifferenceTp difference_type;
00542 typedef typename std::iterator_traits<RandomAccessIteratorIterator>
00543 ::value_type::first_type
00544 RandomAccessIterator1;
00545 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
00546 value_type;
00547
00548 int k = static_cast<int>(seqs_end - seqs_begin);
00549
00550 LT lt(k, comp);
00551
00552
00553 value_type* arbitrary_element = NULL;
00554
00555 for (int t = 0; t < k; ++t)
00556 {
00557 if(arbitrary_element == NULL
00558 && _GLIBCXX_PARALLEL_LENGTH(seqs_begin[t]) > 0)
00559 arbitrary_element = &(*seqs_begin[t].first);
00560 }
00561
00562 for (int t = 0; t < k; ++t)
00563 {
00564 if (seqs_begin[t].first == seqs_begin[t].second)
00565 lt.insert_start(*arbitrary_element, t, true);
00566 else
00567 lt.insert_start(*seqs_begin[t].first, t, false);
00568 }
00569
00570 lt.init();
00571
00572 int source;
00573
00574 for (difference_type i = 0; i < length; ++i)
00575 {
00576
00577 source = lt.get_min_source();
00578
00579 *(target++) = *(seqs_begin[source].first++);
00580
00581
00582 if (seqs_begin[source].first == seqs_begin[source].second)
00583 lt.delete_min_insert(*arbitrary_element, true);
00584 else
00585
00586 lt.delete_min_insert(*seqs_begin[source].first, false);
00587 }
00588
00589 return target;
00590 }
00591
00592
00593
00594
00595
00596
00597
00598
00599
00600
00601
00602
00603
00604
00605
00606
00607
00608
00609
00610 template<typename LT,
00611 typename RandomAccessIteratorIterator,
00612 typename RandomAccessIterator3,
00613 typename _DifferenceTp, typename Comparator>
00614 RandomAccessIterator3
00615 multiway_merge_loser_tree_unguarded(
00616 RandomAccessIteratorIterator seqs_begin,
00617 RandomAccessIteratorIterator seqs_end,
00618 RandomAccessIterator3 target,
00619 const typename std::iterator_traits<typename std::iterator_traits<
00620 RandomAccessIteratorIterator>::value_type::first_type>::value_type&
00621 sentinel,
00622 _DifferenceTp length,
00623 Comparator comp)
00624 {
00625 _GLIBCXX_CALL(length)
00626 typedef _DifferenceTp difference_type;
00627
00628 typedef typename std::iterator_traits<RandomAccessIteratorIterator>
00629 ::value_type::first_type
00630 RandomAccessIterator1;
00631 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
00632 value_type;
00633
00634 int k = seqs_end - seqs_begin;
00635
00636 LT lt(k, sentinel, comp);
00637
00638 for (int t = 0; t < k; ++t)
00639 {
00640 #if _GLIBCXX_ASSERTIONS
00641 _GLIBCXX_PARALLEL_ASSERT(seqs_begin[t].first != seqs_begin[t].second);
00642 #endif
00643 lt.insert_start(*seqs_begin[t].first, t, false);
00644 }
00645
00646 lt.init();
00647
00648 int source;
00649
00650 #if _GLIBCXX_ASSERTIONS
00651 difference_type i = 0;
00652 #endif
00653
00654 RandomAccessIterator3 target_end = target + length;
00655 while (target < target_end)
00656 {
00657
00658 source = lt.get_min_source();
00659
00660 #if _GLIBCXX_ASSERTIONS
00661 _GLIBCXX_PARALLEL_ASSERT(0 <= source && source < k);
00662 _GLIBCXX_PARALLEL_ASSERT(i == 0
00663 || !comp(*(seqs_begin[source].first), *(target - 1)));
00664 #endif
00665
00666
00667 *(target++) = *(seqs_begin[source].first++);
00668
00669 #if _GLIBCXX_ASSERTIONS
00670 ++i;
00671 #endif
00672
00673 lt.delete_min_insert(*seqs_begin[source].first, false);
00674 }
00675
00676 return target;
00677 }
00678
00679
00680
00681
00682
00683
00684
00685
00686
00687
00688
00689
00690
00691
00692
00693
00694
00695
00696
00697
00698 template<
00699 typename UnguardedLoserTree,
00700 typename RandomAccessIteratorIterator,
00701 typename RandomAccessIterator3,
00702 typename _DifferenceTp,
00703 typename Comparator>
00704 RandomAccessIterator3
00705 multiway_merge_loser_tree_sentinel(
00706 RandomAccessIteratorIterator seqs_begin,
00707 RandomAccessIteratorIterator seqs_end,
00708 RandomAccessIterator3 target,
00709 const typename std::iterator_traits<typename std::iterator_traits<
00710 RandomAccessIteratorIterator>::value_type::first_type>::value_type&
00711 sentinel,
00712 _DifferenceTp length,
00713 Comparator comp)
00714 {
00715 _GLIBCXX_CALL(length)
00716
00717 typedef _DifferenceTp difference_type;
00718 typedef std::iterator_traits<RandomAccessIteratorIterator> traits_type;
00719 typedef typename std::iterator_traits<RandomAccessIteratorIterator>
00720 ::value_type::first_type
00721 RandomAccessIterator1;
00722 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
00723 value_type;
00724
00725 RandomAccessIterator3 target_end;
00726
00727 for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s)
00728
00729
00730
00731
00732 ++((*s).second);
00733
00734 target_end = multiway_merge_loser_tree_unguarded
00735 <UnguardedLoserTree>
00736 (seqs_begin, seqs_end, target, sentinel, length, comp);
00737
00738 #if _GLIBCXX_ASSERTIONS
00739 _GLIBCXX_PARALLEL_ASSERT(target_end == target + length);
00740 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target, target_end, comp));
00741 #endif
00742
00743
00744
00745 for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s)
00746 --((*s).second);
00747
00748 return target_end;
00749 }
00750
00751
00752
00753
00754
00755
00756
00757
00758
00759
00760
00761
00762
00763
00764
00765
00766
00767
00768
00769
00770
00771
00772
00773
00774
00775 template <typename T>
00776 struct loser_tree_traits
00777 {
00778
00779
00780
00781
00782
00783
00784 static const bool use_pointer = (sizeof(T) > 4 * sizeof(T*));
00785 };
00786
00787
00788
00789
00790
00791
00792 template<
00793 bool sentinels ,
00794 typename RandomAccessIteratorIterator,
00795 typename RandomAccessIterator3,
00796 typename _DifferenceTp,
00797 typename Comparator>
00798 struct multiway_merge_3_variant_sentinel_switch
00799 {
00800 RandomAccessIterator3 operator()(
00801 RandomAccessIteratorIterator seqs_begin,
00802 RandomAccessIteratorIterator seqs_end,
00803 RandomAccessIterator3 target,
00804 _DifferenceTp length, Comparator comp)
00805 {
00806 return multiway_merge_3_variant<guarded_iterator>(
00807 seqs_begin, seqs_end, target, length, comp);
00808 }
00809 };
00810
00811
00812
00813
00814
00815
00816 template<
00817 typename RandomAccessIteratorIterator,
00818 typename RandomAccessIterator3,
00819 typename _DifferenceTp,
00820 typename Comparator>
00821 struct multiway_merge_3_variant_sentinel_switch
00822 <true, RandomAccessIteratorIterator, RandomAccessIterator3,
00823 _DifferenceTp, Comparator>
00824 {
00825 RandomAccessIterator3 operator()(
00826 RandomAccessIteratorIterator seqs_begin,
00827 RandomAccessIteratorIterator seqs_end,
00828 RandomAccessIterator3 target,
00829 _DifferenceTp length, Comparator comp)
00830 {
00831 return multiway_merge_3_variant<unguarded_iterator>(
00832 seqs_begin, seqs_end, target, length, comp);
00833 }
00834 };
00835
00836
00837
00838
00839
00840
00841 template<
00842 bool sentinels ,
00843 typename RandomAccessIteratorIterator,
00844 typename RandomAccessIterator3,
00845 typename _DifferenceTp,
00846 typename Comparator>
00847 struct multiway_merge_4_variant_sentinel_switch
00848 {
00849 RandomAccessIterator3 operator()(
00850 RandomAccessIteratorIterator seqs_begin,
00851 RandomAccessIteratorIterator seqs_end,
00852 RandomAccessIterator3 target,
00853 _DifferenceTp length, Comparator comp)
00854 {
00855 return multiway_merge_4_variant<guarded_iterator>(
00856 seqs_begin, seqs_end, target, length, comp);
00857 }
00858 };
00859
00860
00861
00862
00863
00864
00865 template<
00866 typename RandomAccessIteratorIterator,
00867 typename RandomAccessIterator3,
00868 typename _DifferenceTp,
00869 typename Comparator>
00870 struct multiway_merge_4_variant_sentinel_switch
00871 <true, RandomAccessIteratorIterator, RandomAccessIterator3,
00872 _DifferenceTp, Comparator>
00873 {
00874 RandomAccessIterator3 operator()(
00875 RandomAccessIteratorIterator seqs_begin,
00876 RandomAccessIteratorIterator seqs_end,
00877 RandomAccessIterator3 target,
00878 _DifferenceTp length, Comparator comp)
00879 {
00880 return multiway_merge_4_variant<unguarded_iterator>(
00881 seqs_begin, seqs_end, target, length, comp);
00882 }
00883 };
00884
00885
00886
00887
00888 template<
00889 bool sentinels,
00890 bool stable,
00891 typename RandomAccessIteratorIterator,
00892 typename RandomAccessIterator3,
00893 typename _DifferenceTp,
00894 typename Comparator>
00895 struct multiway_merge_k_variant_sentinel_switch
00896 {
00897 RandomAccessIterator3 operator()(
00898 RandomAccessIteratorIterator seqs_begin,
00899 RandomAccessIteratorIterator seqs_end,
00900 RandomAccessIterator3 target,
00901 const typename std::iterator_traits<typename std::iterator_traits<
00902 RandomAccessIteratorIterator>::value_type::first_type>::value_type&
00903 sentinel,
00904 _DifferenceTp length, Comparator comp)
00905 {
00906 typedef typename std::iterator_traits<RandomAccessIteratorIterator>
00907 ::value_type::first_type
00908 RandomAccessIterator1;
00909 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
00910 value_type;
00911
00912 return multiway_merge_loser_tree_sentinel<
00913 typename __gnu_cxx::__conditional_type<
00914 loser_tree_traits<value_type>::use_pointer
00915 , LoserTreePointerUnguarded<stable, value_type, Comparator>
00916 , LoserTreeUnguarded<stable, value_type, Comparator>
00917 >::__type>(seqs_begin, seqs_end, target, sentinel, length, comp);
00918 }
00919 };
00920
00921
00922
00923
00924 template<
00925 bool stable,
00926 typename RandomAccessIteratorIterator,
00927 typename RandomAccessIterator3,
00928 typename _DifferenceTp,
00929 typename Comparator>
00930 struct multiway_merge_k_variant_sentinel_switch
00931 <false, stable, RandomAccessIteratorIterator, RandomAccessIterator3,
00932 _DifferenceTp, Comparator>
00933 {
00934 RandomAccessIterator3 operator()(
00935 RandomAccessIteratorIterator seqs_begin,
00936 RandomAccessIteratorIterator seqs_end,
00937 RandomAccessIterator3 target,
00938 const typename std::iterator_traits<typename std::iterator_traits<
00939 RandomAccessIteratorIterator>::value_type::first_type>::value_type&
00940 sentinel,
00941 _DifferenceTp length, Comparator comp)
00942 {
00943 typedef typename std::iterator_traits<RandomAccessIteratorIterator>
00944 ::value_type::first_type
00945 RandomAccessIterator1;
00946 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
00947 value_type;
00948
00949 return multiway_merge_loser_tree<
00950 typename __gnu_cxx::__conditional_type<
00951 loser_tree_traits<value_type>::use_pointer
00952 , LoserTreePointer<stable, value_type, Comparator>
00953 , LoserTree<stable, value_type, Comparator>
00954 >::__type >(seqs_begin, seqs_end, target, length, comp);
00955 }
00956 };
00957
00958
00959
00960
00961
00962
00963
00964
00965
00966
00967
00968
00969
00970
00971 template<
00972 bool stable,
00973 bool sentinels,
00974 typename RandomAccessIteratorIterator,
00975 typename RandomAccessIterator3,
00976 typename _DifferenceTp,
00977 typename Comparator>
00978 RandomAccessIterator3
00979 sequential_multiway_merge(
00980 RandomAccessIteratorIterator seqs_begin,
00981 RandomAccessIteratorIterator seqs_end,
00982 RandomAccessIterator3 target,
00983 const typename std::iterator_traits<typename std::iterator_traits<
00984 RandomAccessIteratorIterator>::value_type::first_type>::value_type&
00985 sentinel,
00986 _DifferenceTp length, Comparator comp)
00987 {
00988 _GLIBCXX_CALL(length)
00989
00990 typedef _DifferenceTp difference_type;
00991 typedef typename std::iterator_traits<RandomAccessIteratorIterator>
00992 ::value_type::first_type
00993 RandomAccessIterator1;
00994 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
00995 value_type;
00996
00997 #if _GLIBCXX_ASSERTIONS
00998 for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s)
00999 {
01000 _GLIBCXX_PARALLEL_ASSERT(is_sorted((*s).first, (*s).second, comp));
01001 }
01002 #endif
01003
01004 _DifferenceTp total_length = 0;
01005 for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s)
01006 total_length += _GLIBCXX_PARALLEL_LENGTH(*s);
01007
01008 length = std::min<_DifferenceTp>(length, total_length);
01009
01010 if(length == 0)
01011 return target;
01012
01013 RandomAccessIterator3 return_target = target;
01014 int k = static_cast<int>(seqs_end - seqs_begin);
01015
01016 switch (k)
01017 {
01018 case 0:
01019 break;
01020 case 1:
01021 return_target = std::copy(seqs_begin[0].first,
01022 seqs_begin[0].first + length,
01023 target);
01024 seqs_begin[0].first += length;
01025 break;
01026 case 2:
01027 return_target = merge_advance(seqs_begin[0].first,
01028 seqs_begin[0].second,
01029 seqs_begin[1].first,
01030 seqs_begin[1].second,
01031 target, length, comp);
01032 break;
01033 case 3:
01034 return_target = multiway_merge_3_variant_sentinel_switch<
01035 sentinels
01036 , RandomAccessIteratorIterator
01037 , RandomAccessIterator3
01038 , _DifferenceTp
01039 , Comparator>()(seqs_begin, seqs_end, target, length, comp);
01040 break;
01041 case 4:
01042 return_target = multiway_merge_4_variant_sentinel_switch<
01043 sentinels
01044 , RandomAccessIteratorIterator
01045 , RandomAccessIterator3
01046 , _DifferenceTp
01047 , Comparator>()(seqs_begin, seqs_end, target, length, comp);
01048 break;
01049 default:
01050 return_target = multiway_merge_k_variant_sentinel_switch<
01051 sentinels
01052 , stable
01053 , RandomAccessIteratorIterator
01054 , RandomAccessIterator3
01055 , _DifferenceTp
01056 , Comparator>()(seqs_begin, seqs_end, target, sentinel, length, comp);
01057 break;
01058 }
01059 #if _GLIBCXX_ASSERTIONS
01060 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target, target + length, comp));
01061 #endif
01062
01063 return return_target;
01064 }
01065
01066
01067
01068
01069
01070
01071 template<bool stable, class RandomAccessIterator, class StrictWeakOrdering>
01072 struct sampling_sorter
01073 {
01074 void operator()(RandomAccessIterator first, RandomAccessIterator last,
01075 StrictWeakOrdering comp)
01076 { __gnu_sequential::stable_sort(first, last, comp); }
01077 };
01078
01079
01080
01081
01082
01083
01084 template<class RandomAccessIterator, class StrictWeakOrdering>
01085 struct sampling_sorter<false, RandomAccessIterator, StrictWeakOrdering>
01086 {
01087 void operator()(RandomAccessIterator first, RandomAccessIterator last,
01088 StrictWeakOrdering comp)
01089 { __gnu_sequential::sort(first, last, comp); }
01090 };
01091
01092
01093
01094
01095 template<
01096 bool stable
01097 , typename RandomAccessIteratorIterator
01098 , typename Comparator
01099 , typename difference_type>
01100 void multiway_merge_sampling_splitting(
01101 RandomAccessIteratorIterator seqs_begin,
01102 RandomAccessIteratorIterator seqs_end,
01103 difference_type length, difference_type total_length, Comparator comp,
01104 std::vector<std::pair<difference_type, difference_type> > *pieces)
01105 {
01106 typedef typename std::iterator_traits<RandomAccessIteratorIterator>
01107 ::value_type::first_type
01108 RandomAccessIterator1;
01109 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
01110 value_type;
01111
01112
01113 int k = static_cast<int>(seqs_end - seqs_begin);
01114
01115 int num_threads = omp_get_num_threads();
01116
01117 difference_type num_samples =
01118 __gnu_parallel::_Settings::get().merge_oversampling * num_threads;
01119
01120 value_type* samples = static_cast<value_type*>(
01121 ::operator new(sizeof(value_type) * k * num_samples));
01122
01123 for (int s = 0; s < k; ++s)
01124 for (difference_type i = 0; i < num_samples; ++i)
01125 {
01126 difference_type sample_index =
01127 static_cast<difference_type>(
01128 _GLIBCXX_PARALLEL_LENGTH(seqs_begin[s])
01129 * (double(i + 1) / (num_samples + 1))
01130 * (double(length) / total_length));
01131 new(&(samples[s * num_samples + i]))
01132 value_type(seqs_begin[s].first[sample_index]);
01133 }
01134
01135
01136
01137 sampling_sorter<stable, value_type*, Comparator>()(
01138 samples, samples + (num_samples * k), comp);
01139
01140 for (int slab = 0; slab < num_threads; ++slab)
01141
01142 for (int seq = 0; seq < k; ++seq)
01143 {
01144
01145 if (slab > 0)
01146 pieces[slab][seq].first =
01147 std::upper_bound(
01148 seqs_begin[seq].first,
01149 seqs_begin[seq].second,
01150 samples[num_samples * k * slab / num_threads],
01151 comp)
01152 - seqs_begin[seq].first;
01153 else
01154
01155 pieces[slab][seq].first = 0;
01156 if ((slab + 1) < num_threads)
01157 pieces[slab][seq].second =
01158 std::upper_bound(
01159 seqs_begin[seq].first,
01160 seqs_begin[seq].second,
01161 samples[num_samples * k * (slab + 1) /
01162 num_threads], comp)
01163 - seqs_begin[seq].first;
01164 else
01165
01166 pieces[slab][seq].second = _GLIBCXX_PARALLEL_LENGTH(seqs_begin[seq]);
01167 }
01168 ::operator delete(samples);
01169 }
01170
01171
01172
01173
01174
01175
01176 template<
01177 bool stable
01178 , typename RandomAccessIteratorIterator
01179 , typename Comparator
01180 , typename difference_type>
01181 void multiway_merge_exact_splitting(
01182 RandomAccessIteratorIterator seqs_begin,
01183 RandomAccessIteratorIterator seqs_end,
01184 difference_type length, difference_type total_length, Comparator comp,
01185 std::vector<std::pair<difference_type, difference_type> > *pieces)
01186 {
01187 typedef typename std::iterator_traits<RandomAccessIteratorIterator>
01188 ::value_type::first_type
01189 RandomAccessIterator1;
01190
01191 const bool tight = (total_length == length);
01192
01193
01194 const int k = static_cast<int>(seqs_end - seqs_begin);
01195
01196 const int num_threads = omp_get_num_threads();
01197
01198
01199 std::vector<RandomAccessIterator1>* offsets =
01200 new std::vector<RandomAccessIterator1>[num_threads];
01201 std::vector<
01202 std::pair<RandomAccessIterator1, RandomAccessIterator1>
01203 > se(k);
01204
01205 copy(seqs_begin, seqs_end, se.begin());
01206
01207 difference_type* borders =
01208 new difference_type[num_threads + 1];
01209 equally_split(length, num_threads, borders);
01210
01211 for (int s = 0; s < (num_threads - 1); ++s)
01212 {
01213 offsets[s].resize(k);
01214 multiseq_partition(
01215 se.begin(), se.end(), borders[s + 1],
01216 offsets[s].begin(), comp);
01217
01218
01219 if (!tight)
01220 {
01221 offsets[num_threads - 1].resize(k);
01222 multiseq_partition(se.begin(), se.end(),
01223 difference_type(length),
01224 offsets[num_threads - 1].begin(), comp);
01225 }
01226 }
01227 delete[] borders;
01228
01229 for (int slab = 0; slab < num_threads; ++slab)
01230 {
01231
01232 for (int seq = 0; seq < k; ++seq)
01233 {
01234
01235 if (slab == 0)
01236 {
01237
01238 pieces[slab][seq].first = 0;
01239 }
01240 else
01241 pieces[slab][seq].first =
01242 pieces[slab - 1][seq].second;
01243 if (!tight || slab < (num_threads - 1))
01244 pieces[slab][seq].second =
01245 offsets[slab][seq] - seqs_begin[seq].first;
01246 else
01247 {
01248
01249 pieces[slab][seq].second =
01250 _GLIBCXX_PARALLEL_LENGTH(seqs_begin[seq]);
01251 }
01252 }
01253 }
01254 delete[] offsets;
01255 }
01256
01257
01258
01259
01260
01261
01262
01263
01264
01265
01266
01267
01268
01269
01270
01271
01272
01273
01274
01275
01276 template<
01277 bool stable,
01278 bool sentinels,
01279 typename RandomAccessIteratorIterator,
01280 typename RandomAccessIterator3,
01281 typename _DifferenceTp,
01282 typename Splitter,
01283 typename Comparator
01284 >
01285 RandomAccessIterator3
01286 parallel_multiway_merge(RandomAccessIteratorIterator seqs_begin,
01287 RandomAccessIteratorIterator seqs_end,
01288 RandomAccessIterator3 target,
01289 Splitter splitter,
01290 _DifferenceTp length,
01291 Comparator comp,
01292 thread_index_t num_threads)
01293 {
01294 #if _GLIBCXX_ASSERTIONS
01295 _GLIBCXX_PARALLEL_ASSERT(seqs_end - seqs_begin > 1);
01296 #endif
01297
01298 _GLIBCXX_CALL(length)
01299
01300 typedef _DifferenceTp difference_type;
01301 typedef typename std::iterator_traits<RandomAccessIteratorIterator>
01302 ::value_type::first_type
01303 RandomAccessIterator1;
01304 typedef typename
01305 std::iterator_traits<RandomAccessIterator1>::value_type value_type;
01306
01307
01308 typedef std::pair<RandomAccessIterator1, RandomAccessIterator1> seq_type;
01309 seq_type* ne_seqs = new seq_type[seqs_end - seqs_begin];
01310 int k = 0;
01311 difference_type total_length = 0;
01312 for (RandomAccessIteratorIterator raii = seqs_begin;
01313 raii != seqs_end; ++raii)
01314 {
01315 _DifferenceTp seq_length = _GLIBCXX_PARALLEL_LENGTH(*raii);
01316 if(seq_length > 0)
01317 {
01318 total_length += seq_length;
01319 ne_seqs[k++] = *raii;
01320 }
01321 }
01322
01323 _GLIBCXX_CALL(total_length)
01324
01325 length = std::min<_DifferenceTp>(length, total_length);
01326
01327 if (total_length == 0 || k == 0)
01328 {
01329 delete[] ne_seqs;
01330 return target;
01331 }
01332
01333 std::vector<std::pair<difference_type, difference_type> >* pieces;
01334
01335 num_threads = static_cast<thread_index_t>
01336 (std::min<difference_type>(num_threads, total_length));
01337
01338 # pragma omp parallel num_threads (num_threads)
01339 {
01340 # pragma omp single
01341 {
01342 num_threads = omp_get_num_threads();
01343
01344 pieces = new std::vector<
01345 std::pair<difference_type, difference_type> >[num_threads];
01346 for (int s = 0; s < num_threads; ++s)
01347 pieces[s].resize(k);
01348
01349 difference_type num_samples =
01350 __gnu_parallel::_Settings::get().merge_oversampling *
01351 num_threads;
01352
01353 splitter(ne_seqs, ne_seqs + k, length, total_length,
01354 comp, pieces);
01355 }
01356
01357 thread_index_t iam = omp_get_thread_num();
01358
01359 difference_type target_position = 0;
01360
01361 for (int c = 0; c < k; ++c)
01362 target_position += pieces[iam][c].first;
01363
01364 seq_type* chunks = new seq_type[k];
01365
01366 for (int s = 0; s < k; ++s)
01367 {
01368 chunks[s] = std::make_pair(
01369 ne_seqs[s].first + pieces[iam][s].first,
01370 ne_seqs[s].first + pieces[iam][s].second);
01371 }
01372
01373 if(length > target_position)
01374 sequential_multiway_merge<stable, sentinels>(
01375 chunks, chunks + k, target + target_position,
01376 *(seqs_begin->second), length - target_position, comp);
01377
01378 delete[] chunks;
01379 }
01380
01381 #if _GLIBCXX_ASSERTIONS
01382 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target, target + length, comp));
01383 #endif
01384
01385 k = 0;
01386
01387 for (RandomAccessIteratorIterator raii = seqs_begin;
01388 raii != seqs_end; ++raii)
01389 {
01390 _DifferenceTp length = _GLIBCXX_PARALLEL_LENGTH(*raii);
01391 if(length > 0)
01392 (*raii).first += pieces[num_threads - 1][k++].second;
01393 }
01394
01395 delete[] pieces;
01396 delete[] ne_seqs;
01397
01398 return target + length;
01399 }
01400
01401
01402
01403
01404
01405
01406
01407
01408
01409
01410
01411
01412
01413
01414
01415
01416
01417
01418
01419
01420
01421
01422
01423
01424
01425
01426
01427
01428
01429
01430
01431
01432
01433
01434
01435
01436
01437
01438
01439
01440
01441
01442
01443
01444
01445
01446
01447
01448
01449
01450
01451
01452
01453
01454
01455
01456
01457
01458
01459
01460
01461
01462
01463
01464
01465
01466
01467
01468
01469
01470
01471 template<
01472 typename RandomAccessIteratorPairIterator
01473 , typename RandomAccessIteratorOut
01474 , typename _DifferenceTp
01475 , typename Comparator>
01476 RandomAccessIteratorOut
01477 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01478 , RandomAccessIteratorPairIterator seqs_end
01479 , RandomAccessIteratorOut target
01480 , _DifferenceTp length, Comparator comp
01481 , __gnu_parallel::sequential_tag)
01482 {
01483 typedef _DifferenceTp difference_type;
01484 _GLIBCXX_CALL(seqs_end - seqs_begin)
01485
01486
01487 if (seqs_begin == seqs_end)
01488 return target;
01489
01490
01491 return sequential_multiway_merge
01492 < false, false>
01493 (seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
01494 }
01495
01496
01497 template<
01498 typename RandomAccessIteratorPairIterator
01499 , typename RandomAccessIteratorOut
01500 , typename _DifferenceTp
01501 , typename Comparator>
01502 RandomAccessIteratorOut
01503 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01504 , RandomAccessIteratorPairIterator seqs_end
01505 , RandomAccessIteratorOut target
01506 , _DifferenceTp length, Comparator comp
01507 , __gnu_parallel::exact_tag tag)
01508 {
01509 typedef _DifferenceTp difference_type;
01510 _GLIBCXX_CALL(seqs_end - seqs_begin)
01511
01512
01513 if (seqs_begin == seqs_end)
01514 return target;
01515
01516
01517
01518
01519 if ((seqs_end - seqs_begin > 1) &&
01520 _GLIBCXX_PARALLEL_CONDITION(
01521 ((seqs_end - seqs_begin) >=
01522 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01523 && ((sequence_index_t)length >=
01524 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01525 return parallel_multiway_merge
01526 < false, false>(
01527 seqs_begin, seqs_end, target,
01528 multiway_merge_exact_splitting< false,
01529 typename std::iterator_traits<RandomAccessIteratorPairIterator>
01530 ::value_type*, Comparator, _DifferenceTp>,
01531 static_cast<difference_type>(length), comp, tag.get_num_threads());
01532 else
01533 return sequential_multiway_merge
01534 < false, false>(
01535 seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
01536 }
01537
01538
01539 template<
01540 typename RandomAccessIteratorPairIterator
01541 , typename RandomAccessIteratorOut
01542 , typename _DifferenceTp
01543 , typename Comparator>
01544 RandomAccessIteratorOut
01545 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01546 , RandomAccessIteratorPairIterator seqs_end
01547 , RandomAccessIteratorOut target
01548 , _DifferenceTp length, Comparator comp
01549 , __gnu_parallel::sampling_tag tag)
01550 {
01551 typedef _DifferenceTp difference_type;
01552 _GLIBCXX_CALL(seqs_end - seqs_begin)
01553
01554
01555 if (seqs_begin == seqs_end)
01556 return target;
01557
01558
01559
01560
01561 if ((seqs_end - seqs_begin > 1) &&
01562 _GLIBCXX_PARALLEL_CONDITION(
01563 ((seqs_end - seqs_begin) >=
01564 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01565 && ((sequence_index_t)length >=
01566 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01567 return parallel_multiway_merge
01568 < false, false>(
01569 seqs_begin, seqs_end,
01570 target,
01571 multiway_merge_exact_splitting< false,
01572 typename std::iterator_traits<RandomAccessIteratorPairIterator>
01573 ::value_type*, Comparator, _DifferenceTp>,
01574 static_cast<difference_type>(length), comp, tag.get_num_threads());
01575 else
01576 return sequential_multiway_merge
01577 < false, false>(
01578 seqs_begin, seqs_end,
01579 target, *(seqs_begin->second), length, comp);
01580 }
01581
01582
01583 template<
01584 typename RandomAccessIteratorPairIterator
01585 , typename RandomAccessIteratorOut
01586 , typename _DifferenceTp
01587 , typename Comparator>
01588 RandomAccessIteratorOut
01589 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01590 , RandomAccessIteratorPairIterator seqs_end
01591 , RandomAccessIteratorOut target
01592 , _DifferenceTp length, Comparator comp
01593 , parallel_tag tag = parallel_tag(0))
01594 {
01595 return multiway_merge(seqs_begin, seqs_end, target, length, comp,
01596 exact_tag(tag.get_num_threads()));
01597 }
01598
01599
01600 template<
01601 typename RandomAccessIteratorPairIterator
01602 , typename RandomAccessIteratorOut
01603 , typename _DifferenceTp
01604 , typename Comparator>
01605 RandomAccessIteratorOut
01606 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01607 , RandomAccessIteratorPairIterator seqs_end
01608 , RandomAccessIteratorOut target
01609 , _DifferenceTp length, Comparator comp
01610 , default_parallel_tag tag)
01611 {
01612 return multiway_merge(seqs_begin, seqs_end, target, length, comp,
01613 exact_tag(tag.get_num_threads()));
01614 }
01615
01616
01617
01618 template<
01619 typename RandomAccessIteratorPairIterator
01620 , typename RandomAccessIteratorOut
01621 , typename _DifferenceTp
01622 , typename Comparator>
01623 RandomAccessIteratorOut
01624 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01625 , RandomAccessIteratorPairIterator seqs_end
01626 , RandomAccessIteratorOut target
01627 , _DifferenceTp length, Comparator comp
01628 , __gnu_parallel::sequential_tag)
01629 {
01630 typedef _DifferenceTp difference_type;
01631 _GLIBCXX_CALL(seqs_end - seqs_begin)
01632
01633
01634 if (seqs_begin == seqs_end)
01635 return target;
01636
01637
01638 return sequential_multiway_merge
01639 < true, false>
01640 (seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
01641 }
01642
01643
01644 template<
01645 typename RandomAccessIteratorPairIterator
01646 , typename RandomAccessIteratorOut
01647 , typename _DifferenceTp
01648 , typename Comparator>
01649 RandomAccessIteratorOut
01650 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01651 , RandomAccessIteratorPairIterator seqs_end
01652 , RandomAccessIteratorOut target
01653 , _DifferenceTp length, Comparator comp
01654 , __gnu_parallel::exact_tag tag)
01655 {
01656 typedef _DifferenceTp difference_type;
01657 _GLIBCXX_CALL(seqs_end - seqs_begin)
01658
01659
01660 if (seqs_begin == seqs_end)
01661 return target;
01662
01663
01664
01665
01666 if ((seqs_end - seqs_begin > 1) &&
01667 _GLIBCXX_PARALLEL_CONDITION(
01668 ((seqs_end - seqs_begin) >=
01669 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01670 && ((sequence_index_t)length >=
01671 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01672 return parallel_multiway_merge
01673 < true, false>(
01674 seqs_begin, seqs_end,
01675 target,
01676 multiway_merge_exact_splitting< true,
01677 typename std::iterator_traits<RandomAccessIteratorPairIterator>
01678 ::value_type*, Comparator, _DifferenceTp>,
01679 static_cast<difference_type>(length), comp, tag.get_num_threads());
01680 else
01681 return sequential_multiway_merge< true,
01682 false>(
01683 seqs_begin, seqs_end,
01684 target, *(seqs_begin->second), length, comp);
01685 }
01686
01687
01688 template<
01689 typename RandomAccessIteratorPairIterator
01690 , typename RandomAccessIteratorOut
01691 , typename _DifferenceTp
01692 , typename Comparator>
01693 RandomAccessIteratorOut
01694 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01695 , RandomAccessIteratorPairIterator seqs_end
01696 , RandomAccessIteratorOut target
01697 , _DifferenceTp length, Comparator comp
01698 , sampling_tag tag)
01699 {
01700 typedef _DifferenceTp difference_type;
01701 _GLIBCXX_CALL(seqs_end - seqs_begin)
01702
01703
01704 if (seqs_begin == seqs_end)
01705 return target;
01706
01707
01708
01709
01710 if ((seqs_end - seqs_begin > 1) &&
01711 _GLIBCXX_PARALLEL_CONDITION(
01712 ((seqs_end - seqs_begin) >=
01713 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01714 && ((sequence_index_t)length >=
01715 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01716 return parallel_multiway_merge
01717 < true, false>(
01718 seqs_begin, seqs_end,
01719 target,
01720 multiway_merge_sampling_splitting< true,
01721 typename std::iterator_traits<RandomAccessIteratorPairIterator>
01722 ::value_type*, Comparator, _DifferenceTp>,
01723 static_cast<difference_type>(length), comp, tag.get_num_threads());
01724 else
01725 return sequential_multiway_merge
01726 < true, false>(
01727 seqs_begin, seqs_end,
01728 target, *(seqs_begin->second), length, comp);
01729 }
01730
01731
01732
01733 template<
01734 typename RandomAccessIteratorPairIterator
01735 , typename RandomAccessIteratorOut
01736 , typename _DifferenceTp
01737 , typename Comparator>
01738 RandomAccessIteratorOut
01739 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01740 , RandomAccessIteratorPairIterator seqs_end
01741 , RandomAccessIteratorOut target
01742 , _DifferenceTp length, Comparator comp
01743 , parallel_tag tag = parallel_tag(0))
01744 {
01745 return stable_multiway_merge(seqs_begin, seqs_end, target, length, comp,
01746 exact_tag(tag.get_num_threads()));
01747 }
01748
01749
01750 template<
01751 typename RandomAccessIteratorPairIterator
01752 , typename RandomAccessIteratorOut
01753 , typename _DifferenceTp
01754 , typename Comparator>
01755 RandomAccessIteratorOut
01756 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01757 , RandomAccessIteratorPairIterator seqs_end
01758 , RandomAccessIteratorOut target
01759 , _DifferenceTp length, Comparator comp
01760 , default_parallel_tag tag)
01761 {
01762 return stable_multiway_merge(seqs_begin, seqs_end, target, length, comp,
01763 exact_tag(tag.get_num_threads()));
01764 }
01765
01766
01767
01768
01769
01770
01771
01772
01773
01774
01775
01776
01777
01778
01779
01780
01781
01782
01783
01784
01785
01786
01787
01788
01789
01790
01791
01792
01793
01794
01795
01796
01797
01798
01799
01800
01801
01802
01803
01804
01805
01806
01807
01808
01809
01810
01811
01812
01813
01814
01815
01816
01817
01818
01819
01820
01821
01822
01823
01824
01825
01826
01827
01828
01829
01830
01831
01832
01833
01834
01835
01836
01837
01838
01839
01840
01841
01842
01843 template<
01844 typename RandomAccessIteratorPairIterator
01845 , typename RandomAccessIteratorOut
01846 , typename _DifferenceTp
01847 , typename Comparator>
01848 RandomAccessIteratorOut
01849 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
01850 , RandomAccessIteratorPairIterator seqs_end
01851 , RandomAccessIteratorOut target
01852 , _DifferenceTp length, Comparator comp
01853 , __gnu_parallel::sequential_tag)
01854 {
01855 typedef _DifferenceTp difference_type;
01856 _GLIBCXX_CALL(seqs_end - seqs_begin)
01857
01858
01859 if (seqs_begin == seqs_end)
01860 return target;
01861
01862
01863 return sequential_multiway_merge
01864 < false, true>
01865 (seqs_begin, seqs_end,
01866 target, *(seqs_begin->second), length, comp);
01867 }
01868
01869
01870 template<
01871 typename RandomAccessIteratorPairIterator
01872 , typename RandomAccessIteratorOut
01873 , typename _DifferenceTp
01874 , typename Comparator>
01875 RandomAccessIteratorOut
01876 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
01877 , RandomAccessIteratorPairIterator seqs_end
01878 , RandomAccessIteratorOut target
01879 , _DifferenceTp length, Comparator comp
01880 , __gnu_parallel::exact_tag tag)
01881 {
01882 typedef _DifferenceTp difference_type;
01883 _GLIBCXX_CALL(seqs_end - seqs_begin)
01884
01885
01886 if (seqs_begin == seqs_end)
01887 return target;
01888
01889
01890
01891
01892 if ((seqs_end - seqs_begin > 1) &&
01893 _GLIBCXX_PARALLEL_CONDITION(
01894 ((seqs_end - seqs_begin) >=
01895 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01896 && ((sequence_index_t)length >=
01897 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01898 return parallel_multiway_merge
01899 < false, true>(
01900 seqs_begin, seqs_end,
01901 target,
01902 multiway_merge_exact_splitting< false,
01903 typename std::iterator_traits<RandomAccessIteratorPairIterator>
01904 ::value_type*, Comparator, _DifferenceTp>,
01905 static_cast<difference_type>(length), comp, tag.get_num_threads());
01906 else
01907 return sequential_multiway_merge
01908 < false, true>(
01909 seqs_begin, seqs_end,
01910 target, *(seqs_begin->second), length, comp);
01911 }
01912
01913
01914 template<
01915 typename RandomAccessIteratorPairIterator
01916 , typename RandomAccessIteratorOut
01917 , typename _DifferenceTp
01918 , typename Comparator>
01919 RandomAccessIteratorOut
01920 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
01921 , RandomAccessIteratorPairIterator seqs_end
01922 , RandomAccessIteratorOut target
01923 , _DifferenceTp length, Comparator comp
01924 , sampling_tag tag)
01925 {
01926 typedef _DifferenceTp difference_type;
01927 _GLIBCXX_CALL(seqs_end - seqs_begin)
01928
01929
01930 if (seqs_begin == seqs_end)
01931 return target;
01932
01933
01934
01935
01936 if ((seqs_end - seqs_begin > 1) &&
01937 _GLIBCXX_PARALLEL_CONDITION(
01938 ((seqs_end - seqs_begin) >=
01939 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01940 && ((sequence_index_t)length >=
01941 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01942 return parallel_multiway_merge
01943 < false, true>
01944 (seqs_begin, seqs_end, target,
01945 multiway_merge_sampling_splitting< false,
01946 typename std::iterator_traits<RandomAccessIteratorPairIterator>
01947 ::value_type*, Comparator, _DifferenceTp>,
01948 static_cast<difference_type>(length), comp, tag.get_num_threads());
01949 else
01950 return sequential_multiway_merge
01951 <false, true>(
01952 seqs_begin, seqs_end,
01953 target, *(seqs_begin->second), length, comp);
01954 }
01955
01956
01957 template<
01958 typename RandomAccessIteratorPairIterator
01959 , typename RandomAccessIteratorOut
01960 , typename _DifferenceTp
01961 , typename Comparator>
01962 RandomAccessIteratorOut
01963 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
01964 , RandomAccessIteratorPairIterator seqs_end
01965 , RandomAccessIteratorOut target
01966 , _DifferenceTp length, Comparator comp
01967 , parallel_tag tag = parallel_tag(0))
01968 {
01969 return multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp,
01970 exact_tag(tag.get_num_threads()));
01971 }
01972
01973
01974 template<
01975 typename RandomAccessIteratorPairIterator
01976 , typename RandomAccessIteratorOut
01977 , typename _DifferenceTp
01978 , typename Comparator>
01979 RandomAccessIteratorOut
01980 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
01981 , RandomAccessIteratorPairIterator seqs_end
01982 , RandomAccessIteratorOut target
01983 , _DifferenceTp length, Comparator comp
01984 , default_parallel_tag tag)
01985 {
01986 return multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp,
01987 exact_tag(tag.get_num_threads()));
01988 }
01989
01990
01991
01992 template<
01993 typename RandomAccessIteratorPairIterator
01994 , typename RandomAccessIteratorOut
01995 , typename _DifferenceTp
01996 , typename Comparator>
01997 RandomAccessIteratorOut
01998 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
01999 , RandomAccessIteratorPairIterator seqs_end
02000 , RandomAccessIteratorOut target
02001 , _DifferenceTp length, Comparator comp
02002 , __gnu_parallel::sequential_tag)
02003 {
02004 typedef _DifferenceTp difference_type;
02005 _GLIBCXX_CALL(seqs_end - seqs_begin)
02006
02007
02008 if (seqs_begin == seqs_end)
02009 return target;
02010
02011
02012 return sequential_multiway_merge
02013 < true, true>
02014 (seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
02015 }
02016
02017
02018 template<
02019 typename RandomAccessIteratorPairIterator
02020 , typename RandomAccessIteratorOut
02021 , typename _DifferenceTp
02022 , typename Comparator>
02023 RandomAccessIteratorOut
02024 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
02025 , RandomAccessIteratorPairIterator seqs_end
02026 , RandomAccessIteratorOut target
02027 , _DifferenceTp length, Comparator comp
02028 , __gnu_parallel::exact_tag tag)
02029 {
02030 typedef _DifferenceTp difference_type;
02031 _GLIBCXX_CALL(seqs_end - seqs_begin)
02032
02033
02034 if (seqs_begin == seqs_end)
02035 return target;
02036
02037
02038
02039
02040 if ((seqs_end - seqs_begin > 1) &&
02041 _GLIBCXX_PARALLEL_CONDITION(
02042 ((seqs_end - seqs_begin) >=
02043 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
02044 && ((sequence_index_t)length >=
02045 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
02046 return parallel_multiway_merge
02047 < true, true>(
02048 seqs_begin, seqs_end,
02049 target,
02050 multiway_merge_exact_splitting< true,
02051 typename std::iterator_traits<RandomAccessIteratorPairIterator>
02052 ::value_type*, Comparator, _DifferenceTp>,
02053 static_cast<difference_type>(length), comp, tag.get_num_threads());
02054 else
02055 return sequential_multiway_merge
02056 < true, true>(
02057 seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
02058 }
02059
02060
02061 template<
02062 typename RandomAccessIteratorPairIterator
02063 , typename RandomAccessIteratorOut
02064 , typename _DifferenceTp
02065 , typename Comparator>
02066 RandomAccessIteratorOut
02067 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
02068 , RandomAccessIteratorPairIterator seqs_end
02069 , RandomAccessIteratorOut target
02070 , _DifferenceTp length, Comparator comp
02071 , sampling_tag tag)
02072 {
02073 typedef _DifferenceTp difference_type;
02074 _GLIBCXX_CALL(seqs_end - seqs_begin)
02075
02076
02077 if (seqs_begin == seqs_end)
02078 return target;
02079
02080
02081
02082
02083 if ((seqs_end - seqs_begin > 1) &&
02084 _GLIBCXX_PARALLEL_CONDITION(
02085 ((seqs_end - seqs_begin) >=
02086 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
02087 && ((sequence_index_t)length >=
02088 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
02089 return parallel_multiway_merge
02090 < true, true>(
02091 seqs_begin, seqs_end,
02092 target,
02093 multiway_merge_sampling_splitting< true,
02094 typename std::iterator_traits<RandomAccessIteratorPairIterator>
02095 ::value_type*, Comparator, _DifferenceTp>,
02096 static_cast<difference_type>(length), comp, tag.get_num_threads());
02097 else
02098 return sequential_multiway_merge
02099 < true, true>(
02100 seqs_begin, seqs_end,
02101 target, *(seqs_begin->second), length, comp);
02102 }
02103
02104
02105 template<
02106 typename RandomAccessIteratorPairIterator
02107 , typename RandomAccessIteratorOut
02108 , typename _DifferenceTp
02109 , typename Comparator>
02110 RandomAccessIteratorOut
02111 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
02112 , RandomAccessIteratorPairIterator seqs_end
02113 , RandomAccessIteratorOut target
02114 , _DifferenceTp length, Comparator comp
02115 , parallel_tag tag = parallel_tag(0))
02116 {
02117 return stable_multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp,
02118 exact_tag(tag.get_num_threads()));
02119 }
02120
02121
02122 template<
02123 typename RandomAccessIteratorPairIterator
02124 , typename RandomAccessIteratorOut
02125 , typename _DifferenceTp
02126 , typename Comparator>
02127 RandomAccessIteratorOut
02128 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
02129 , RandomAccessIteratorPairIterator seqs_end
02130 , RandomAccessIteratorOut target
02131 , _DifferenceTp length, Comparator comp
02132 , default_parallel_tag tag)
02133 {
02134 return stable_multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp,
02135 exact_tag(tag.get_num_threads()));
02136 }
02137
02138 };
02139
02140 #endif