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
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 std::pair<RandomAccessIterator1, RandomAccessIterator1>* ne_seqs =
01309 static_cast<std::pair<RandomAccessIterator1, RandomAccessIterator1>*>(
01310 ::operator new(
01311 sizeof(std::pair<RandomAccessIterator1, RandomAccessIterator1>)
01312 * (seqs_end - seqs_begin)));
01313 int k = 0;
01314 difference_type total_length = 0;
01315 for (RandomAccessIteratorIterator raii = seqs_begin;
01316 raii != seqs_end; ++raii)
01317 {
01318 _DifferenceTp seq_length = _GLIBCXX_PARALLEL_LENGTH(*raii);
01319 if(seq_length > 0)
01320 {
01321 total_length += seq_length;
01322
01323 new(&(ne_seqs[k++]))
01324 std::pair<RandomAccessIterator1, RandomAccessIterator1>(*raii);
01325 }
01326 }
01327
01328 _GLIBCXX_CALL(total_length)
01329
01330 length = std::min<_DifferenceTp>(length, total_length);
01331
01332 if (total_length == 0 || k == 0)
01333 {
01334 ::operator delete(ne_seqs);
01335 return target;
01336 }
01337
01338 std::vector<std::pair<difference_type, difference_type> >* pieces;
01339
01340 num_threads = static_cast<thread_index_t>
01341 (std::min<difference_type>(num_threads, total_length));
01342
01343 # pragma omp parallel num_threads (num_threads)
01344 {
01345 # pragma omp single
01346 {
01347 num_threads = omp_get_num_threads();
01348
01349 pieces = new std::vector<
01350 std::pair<difference_type, difference_type> >[num_threads];
01351 for (int s = 0; s < num_threads; ++s)
01352 pieces[s].resize(k);
01353
01354 difference_type num_samples =
01355 __gnu_parallel::_Settings::get().merge_oversampling *
01356 num_threads;
01357
01358 splitter(ne_seqs, ne_seqs + k, length, total_length,
01359 comp, pieces);
01360 }
01361
01362 thread_index_t iam = omp_get_thread_num();
01363
01364 difference_type target_position = 0;
01365
01366 for (int c = 0; c < k; ++c)
01367 target_position += pieces[iam][c].first;
01368
01369 std::pair<RandomAccessIterator1, RandomAccessIterator1>* chunks
01370 = new std::pair<RandomAccessIterator1, RandomAccessIterator1>[k];
01371
01372 for (int s = 0; s < k; ++s)
01373 {
01374 chunks[s] = std::make_pair(
01375 ne_seqs[s].first + pieces[iam][s].first,
01376 ne_seqs[s].first + pieces[iam][s].second);
01377 }
01378
01379 if(length > target_position)
01380 sequential_multiway_merge<stable, sentinels>(
01381 chunks, chunks + k, target + target_position,
01382 *(seqs_begin->second), length - target_position, comp);
01383
01384 delete[] chunks;
01385 }
01386
01387 #if _GLIBCXX_ASSERTIONS
01388 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target, target + length, comp));
01389 #endif
01390
01391 k = 0;
01392
01393 for (RandomAccessIteratorIterator raii = seqs_begin;
01394 raii != seqs_end; ++raii)
01395 {
01396 _DifferenceTp length = _GLIBCXX_PARALLEL_LENGTH(*raii);
01397 if(length > 0)
01398 (*raii).first += pieces[num_threads - 1][k++].second;
01399 }
01400
01401 delete[] pieces;
01402
01403 return target + length;
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
01472
01473
01474
01475
01476 template<
01477 typename RandomAccessIteratorPairIterator
01478 , typename RandomAccessIteratorOut
01479 , typename _DifferenceTp
01480 , typename Comparator>
01481 RandomAccessIteratorOut
01482 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01483 , RandomAccessIteratorPairIterator seqs_end
01484 , RandomAccessIteratorOut target
01485 , _DifferenceTp length, Comparator comp
01486 , __gnu_parallel::sequential_tag)
01487 {
01488 typedef _DifferenceTp difference_type;
01489 _GLIBCXX_CALL(seqs_end - seqs_begin)
01490
01491
01492 if (seqs_begin == seqs_end)
01493 return target;
01494
01495
01496 return sequential_multiway_merge
01497 < false, false>
01498 (seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
01499 }
01500
01501
01502 template<
01503 typename RandomAccessIteratorPairIterator
01504 , typename RandomAccessIteratorOut
01505 , typename _DifferenceTp
01506 , typename Comparator>
01507 RandomAccessIteratorOut
01508 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01509 , RandomAccessIteratorPairIterator seqs_end
01510 , RandomAccessIteratorOut target
01511 , _DifferenceTp length, Comparator comp
01512 , __gnu_parallel::exact_tag tag)
01513 {
01514 typedef _DifferenceTp difference_type;
01515 _GLIBCXX_CALL(seqs_end - seqs_begin)
01516
01517
01518 if (seqs_begin == seqs_end)
01519 return target;
01520
01521
01522
01523
01524 if ((seqs_end - seqs_begin > 1) &&
01525 _GLIBCXX_PARALLEL_CONDITION(
01526 ((seqs_end - seqs_begin) >=
01527 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01528 && ((sequence_index_t)length >=
01529 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01530 return parallel_multiway_merge
01531 < false, false>(
01532 seqs_begin, seqs_end, target,
01533 multiway_merge_exact_splitting< false,
01534 typename std::iterator_traits<RandomAccessIteratorPairIterator>
01535 ::value_type*, Comparator, _DifferenceTp>,
01536 static_cast<difference_type>(length), comp, tag.get_num_threads());
01537 else
01538 return sequential_multiway_merge
01539 < false, false>(
01540 seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
01541 }
01542
01543
01544 template<
01545 typename RandomAccessIteratorPairIterator
01546 , typename RandomAccessIteratorOut
01547 , typename _DifferenceTp
01548 , typename Comparator>
01549 RandomAccessIteratorOut
01550 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01551 , RandomAccessIteratorPairIterator seqs_end
01552 , RandomAccessIteratorOut target
01553 , _DifferenceTp length, Comparator comp
01554 , __gnu_parallel::sampling_tag tag)
01555 {
01556 typedef _DifferenceTp difference_type;
01557 _GLIBCXX_CALL(seqs_end - seqs_begin)
01558
01559
01560 if (seqs_begin == seqs_end)
01561 return target;
01562
01563
01564
01565
01566 if ((seqs_end - seqs_begin > 1) &&
01567 _GLIBCXX_PARALLEL_CONDITION(
01568 ((seqs_end - seqs_begin) >=
01569 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01570 && ((sequence_index_t)length >=
01571 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01572 return parallel_multiway_merge
01573 < false, false>(
01574 seqs_begin, seqs_end,
01575 target,
01576 multiway_merge_exact_splitting< false,
01577 typename std::iterator_traits<RandomAccessIteratorPairIterator>
01578 ::value_type*, Comparator, _DifferenceTp>,
01579 static_cast<difference_type>(length), comp, tag.get_num_threads());
01580 else
01581 return sequential_multiway_merge
01582 < false, false>(
01583 seqs_begin, seqs_end,
01584 target, *(seqs_begin->second), length, comp);
01585 }
01586
01587
01588 template<
01589 typename RandomAccessIteratorPairIterator
01590 , typename RandomAccessIteratorOut
01591 , typename _DifferenceTp
01592 , typename Comparator>
01593 RandomAccessIteratorOut
01594 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01595 , RandomAccessIteratorPairIterator seqs_end
01596 , RandomAccessIteratorOut target
01597 , _DifferenceTp length, Comparator comp
01598 , parallel_tag tag = parallel_tag(0))
01599 {
01600 return multiway_merge(seqs_begin, seqs_end, target, length, comp,
01601 exact_tag(tag.get_num_threads()));
01602 }
01603
01604
01605 template<
01606 typename RandomAccessIteratorPairIterator
01607 , typename RandomAccessIteratorOut
01608 , typename _DifferenceTp
01609 , typename Comparator>
01610 RandomAccessIteratorOut
01611 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01612 , RandomAccessIteratorPairIterator seqs_end
01613 , RandomAccessIteratorOut target
01614 , _DifferenceTp length, Comparator comp
01615 , default_parallel_tag tag)
01616 {
01617 return multiway_merge(seqs_begin, seqs_end, target, length, comp,
01618 exact_tag(tag.get_num_threads()));
01619 }
01620
01621
01622
01623 template<
01624 typename RandomAccessIteratorPairIterator
01625 , typename RandomAccessIteratorOut
01626 , typename _DifferenceTp
01627 , typename Comparator>
01628 RandomAccessIteratorOut
01629 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01630 , RandomAccessIteratorPairIterator seqs_end
01631 , RandomAccessIteratorOut target
01632 , _DifferenceTp length, Comparator comp
01633 , __gnu_parallel::sequential_tag)
01634 {
01635 typedef _DifferenceTp difference_type;
01636 _GLIBCXX_CALL(seqs_end - seqs_begin)
01637
01638
01639 if (seqs_begin == seqs_end)
01640 return target;
01641
01642
01643 return sequential_multiway_merge
01644 < true, false>
01645 (seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
01646 }
01647
01648
01649 template<
01650 typename RandomAccessIteratorPairIterator
01651 , typename RandomAccessIteratorOut
01652 , typename _DifferenceTp
01653 , typename Comparator>
01654 RandomAccessIteratorOut
01655 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01656 , RandomAccessIteratorPairIterator seqs_end
01657 , RandomAccessIteratorOut target
01658 , _DifferenceTp length, Comparator comp
01659 , __gnu_parallel::exact_tag tag)
01660 {
01661 typedef _DifferenceTp difference_type;
01662 _GLIBCXX_CALL(seqs_end - seqs_begin)
01663
01664
01665 if (seqs_begin == seqs_end)
01666 return target;
01667
01668
01669
01670
01671 if ((seqs_end - seqs_begin > 1) &&
01672 _GLIBCXX_PARALLEL_CONDITION(
01673 ((seqs_end - seqs_begin) >=
01674 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01675 && ((sequence_index_t)length >=
01676 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01677 return parallel_multiway_merge
01678 < true, false>(
01679 seqs_begin, seqs_end,
01680 target,
01681 multiway_merge_exact_splitting< true,
01682 typename std::iterator_traits<RandomAccessIteratorPairIterator>
01683 ::value_type*, Comparator, _DifferenceTp>,
01684 static_cast<difference_type>(length), comp, tag.get_num_threads());
01685 else
01686 return sequential_multiway_merge< true,
01687 false>(
01688 seqs_begin, seqs_end,
01689 target, *(seqs_begin->second), length, comp);
01690 }
01691
01692
01693 template<
01694 typename RandomAccessIteratorPairIterator
01695 , typename RandomAccessIteratorOut
01696 , typename _DifferenceTp
01697 , typename Comparator>
01698 RandomAccessIteratorOut
01699 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01700 , RandomAccessIteratorPairIterator seqs_end
01701 , RandomAccessIteratorOut target
01702 , _DifferenceTp length, Comparator comp
01703 , sampling_tag tag)
01704 {
01705 typedef _DifferenceTp difference_type;
01706 _GLIBCXX_CALL(seqs_end - seqs_begin)
01707
01708
01709 if (seqs_begin == seqs_end)
01710 return target;
01711
01712
01713
01714
01715 if ((seqs_end - seqs_begin > 1) &&
01716 _GLIBCXX_PARALLEL_CONDITION(
01717 ((seqs_end - seqs_begin) >=
01718 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01719 && ((sequence_index_t)length >=
01720 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01721 return parallel_multiway_merge
01722 < true, false>(
01723 seqs_begin, seqs_end,
01724 target,
01725 multiway_merge_sampling_splitting< true,
01726 typename std::iterator_traits<RandomAccessIteratorPairIterator>
01727 ::value_type*, Comparator, _DifferenceTp>,
01728 static_cast<difference_type>(length), comp, tag.get_num_threads());
01729 else
01730 return sequential_multiway_merge
01731 < true, false>(
01732 seqs_begin, seqs_end,
01733 target, *(seqs_begin->second), length, comp);
01734 }
01735
01736
01737
01738 template<
01739 typename RandomAccessIteratorPairIterator
01740 , typename RandomAccessIteratorOut
01741 , typename _DifferenceTp
01742 , typename Comparator>
01743 RandomAccessIteratorOut
01744 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01745 , RandomAccessIteratorPairIterator seqs_end
01746 , RandomAccessIteratorOut target
01747 , _DifferenceTp length, Comparator comp
01748 , parallel_tag tag = parallel_tag(0))
01749 {
01750 return stable_multiway_merge(seqs_begin, seqs_end, target, length, comp,
01751 exact_tag(tag.get_num_threads()));
01752 }
01753
01754
01755 template<
01756 typename RandomAccessIteratorPairIterator
01757 , typename RandomAccessIteratorOut
01758 , typename _DifferenceTp
01759 , typename Comparator>
01760 RandomAccessIteratorOut
01761 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01762 , RandomAccessIteratorPairIterator seqs_end
01763 , RandomAccessIteratorOut target
01764 , _DifferenceTp length, Comparator comp
01765 , default_parallel_tag tag)
01766 {
01767 return stable_multiway_merge(seqs_begin, seqs_end, target, length, comp,
01768 exact_tag(tag.get_num_threads()));
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
01844
01845
01846
01847
01848 template<
01849 typename RandomAccessIteratorPairIterator
01850 , typename RandomAccessIteratorOut
01851 , typename _DifferenceTp
01852 , typename Comparator>
01853 RandomAccessIteratorOut
01854 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
01855 , RandomAccessIteratorPairIterator seqs_end
01856 , RandomAccessIteratorOut target
01857 , _DifferenceTp length, Comparator comp
01858 , __gnu_parallel::sequential_tag)
01859 {
01860 typedef _DifferenceTp difference_type;
01861 _GLIBCXX_CALL(seqs_end - seqs_begin)
01862
01863
01864 if (seqs_begin == seqs_end)
01865 return target;
01866
01867
01868 return sequential_multiway_merge
01869 < false, true>
01870 (seqs_begin, seqs_end,
01871 target, *(seqs_begin->second), length, comp);
01872 }
01873
01874
01875 template<
01876 typename RandomAccessIteratorPairIterator
01877 , typename RandomAccessIteratorOut
01878 , typename _DifferenceTp
01879 , typename Comparator>
01880 RandomAccessIteratorOut
01881 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
01882 , RandomAccessIteratorPairIterator seqs_end
01883 , RandomAccessIteratorOut target
01884 , _DifferenceTp length, Comparator comp
01885 , __gnu_parallel::exact_tag tag)
01886 {
01887 typedef _DifferenceTp difference_type;
01888 _GLIBCXX_CALL(seqs_end - seqs_begin)
01889
01890
01891 if (seqs_begin == seqs_end)
01892 return target;
01893
01894
01895
01896
01897 if ((seqs_end - seqs_begin > 1) &&
01898 _GLIBCXX_PARALLEL_CONDITION(
01899 ((seqs_end - seqs_begin) >=
01900 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01901 && ((sequence_index_t)length >=
01902 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01903 return parallel_multiway_merge
01904 < false, true>(
01905 seqs_begin, seqs_end,
01906 target,
01907 multiway_merge_exact_splitting< false,
01908 typename std::iterator_traits<RandomAccessIteratorPairIterator>
01909 ::value_type*, Comparator, _DifferenceTp>,
01910 static_cast<difference_type>(length), comp, tag.get_num_threads());
01911 else
01912 return sequential_multiway_merge
01913 < false, true>(
01914 seqs_begin, seqs_end,
01915 target, *(seqs_begin->second), length, comp);
01916 }
01917
01918
01919 template<
01920 typename RandomAccessIteratorPairIterator
01921 , typename RandomAccessIteratorOut
01922 , typename _DifferenceTp
01923 , typename Comparator>
01924 RandomAccessIteratorOut
01925 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
01926 , RandomAccessIteratorPairIterator seqs_end
01927 , RandomAccessIteratorOut target
01928 , _DifferenceTp length, Comparator comp
01929 , sampling_tag tag)
01930 {
01931 typedef _DifferenceTp difference_type;
01932 _GLIBCXX_CALL(seqs_end - seqs_begin)
01933
01934
01935 if (seqs_begin == seqs_end)
01936 return target;
01937
01938
01939
01940
01941 if ((seqs_end - seqs_begin > 1) &&
01942 _GLIBCXX_PARALLEL_CONDITION(
01943 ((seqs_end - seqs_begin) >=
01944 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01945 && ((sequence_index_t)length >=
01946 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01947 return parallel_multiway_merge
01948 < false, true>
01949 (seqs_begin, seqs_end, target,
01950 multiway_merge_sampling_splitting< false,
01951 typename std::iterator_traits<RandomAccessIteratorPairIterator>
01952 ::value_type*, Comparator, _DifferenceTp>,
01953 static_cast<difference_type>(length), comp, tag.get_num_threads());
01954 else
01955 return sequential_multiway_merge
01956 <false, true>(
01957 seqs_begin, seqs_end,
01958 target, *(seqs_begin->second), length, comp);
01959 }
01960
01961
01962 template<
01963 typename RandomAccessIteratorPairIterator
01964 , typename RandomAccessIteratorOut
01965 , typename _DifferenceTp
01966 , typename Comparator>
01967 RandomAccessIteratorOut
01968 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
01969 , RandomAccessIteratorPairIterator seqs_end
01970 , RandomAccessIteratorOut target
01971 , _DifferenceTp length, Comparator comp
01972 , parallel_tag tag = parallel_tag(0))
01973 {
01974 return multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp,
01975 exact_tag(tag.get_num_threads()));
01976 }
01977
01978
01979 template<
01980 typename RandomAccessIteratorPairIterator
01981 , typename RandomAccessIteratorOut
01982 , typename _DifferenceTp
01983 , typename Comparator>
01984 RandomAccessIteratorOut
01985 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
01986 , RandomAccessIteratorPairIterator seqs_end
01987 , RandomAccessIteratorOut target
01988 , _DifferenceTp length, Comparator comp
01989 , default_parallel_tag tag)
01990 {
01991 return multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp,
01992 exact_tag(tag.get_num_threads()));
01993 }
01994
01995
01996
01997 template<
01998 typename RandomAccessIteratorPairIterator
01999 , typename RandomAccessIteratorOut
02000 , typename _DifferenceTp
02001 , typename Comparator>
02002 RandomAccessIteratorOut
02003 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
02004 , RandomAccessIteratorPairIterator seqs_end
02005 , RandomAccessIteratorOut target
02006 , _DifferenceTp length, Comparator comp
02007 , __gnu_parallel::sequential_tag)
02008 {
02009 typedef _DifferenceTp difference_type;
02010 _GLIBCXX_CALL(seqs_end - seqs_begin)
02011
02012
02013 if (seqs_begin == seqs_end)
02014 return target;
02015
02016
02017 return sequential_multiway_merge
02018 < true, true>
02019 (seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
02020 }
02021
02022
02023 template<
02024 typename RandomAccessIteratorPairIterator
02025 , typename RandomAccessIteratorOut
02026 , typename _DifferenceTp
02027 , typename Comparator>
02028 RandomAccessIteratorOut
02029 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
02030 , RandomAccessIteratorPairIterator seqs_end
02031 , RandomAccessIteratorOut target
02032 , _DifferenceTp length, Comparator comp
02033 , __gnu_parallel::exact_tag tag)
02034 {
02035 typedef _DifferenceTp difference_type;
02036 _GLIBCXX_CALL(seqs_end - seqs_begin)
02037
02038
02039 if (seqs_begin == seqs_end)
02040 return target;
02041
02042
02043
02044
02045 if ((seqs_end - seqs_begin > 1) &&
02046 _GLIBCXX_PARALLEL_CONDITION(
02047 ((seqs_end - seqs_begin) >=
02048 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
02049 && ((sequence_index_t)length >=
02050 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
02051 return parallel_multiway_merge
02052 < true, true>(
02053 seqs_begin, seqs_end,
02054 target,
02055 multiway_merge_exact_splitting< true,
02056 typename std::iterator_traits<RandomAccessIteratorPairIterator>
02057 ::value_type*, Comparator, _DifferenceTp>,
02058 static_cast<difference_type>(length), comp, tag.get_num_threads());
02059 else
02060 return sequential_multiway_merge
02061 < true, true>(
02062 seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
02063 }
02064
02065
02066 template<
02067 typename RandomAccessIteratorPairIterator
02068 , typename RandomAccessIteratorOut
02069 , typename _DifferenceTp
02070 , typename Comparator>
02071 RandomAccessIteratorOut
02072 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
02073 , RandomAccessIteratorPairIterator seqs_end
02074 , RandomAccessIteratorOut target
02075 , _DifferenceTp length, Comparator comp
02076 , sampling_tag tag)
02077 {
02078 typedef _DifferenceTp difference_type;
02079 _GLIBCXX_CALL(seqs_end - seqs_begin)
02080
02081
02082 if (seqs_begin == seqs_end)
02083 return target;
02084
02085
02086
02087
02088 if ((seqs_end - seqs_begin > 1) &&
02089 _GLIBCXX_PARALLEL_CONDITION(
02090 ((seqs_end - seqs_begin) >=
02091 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
02092 && ((sequence_index_t)length >=
02093 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
02094 return parallel_multiway_merge
02095 < true, true>(
02096 seqs_begin, seqs_end,
02097 target,
02098 multiway_merge_sampling_splitting< true,
02099 typename std::iterator_traits<RandomAccessIteratorPairIterator>
02100 ::value_type*, Comparator, _DifferenceTp>,
02101 static_cast<difference_type>(length), comp, tag.get_num_threads());
02102 else
02103 return sequential_multiway_merge
02104 < true, true>(
02105 seqs_begin, seqs_end,
02106 target, *(seqs_begin->second), length, comp);
02107 }
02108
02109
02110 template<
02111 typename RandomAccessIteratorPairIterator
02112 , typename RandomAccessIteratorOut
02113 , typename _DifferenceTp
02114 , typename Comparator>
02115 RandomAccessIteratorOut
02116 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
02117 , RandomAccessIteratorPairIterator seqs_end
02118 , RandomAccessIteratorOut target
02119 , _DifferenceTp length, Comparator comp
02120 , parallel_tag tag = parallel_tag(0))
02121 {
02122 return stable_multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp,
02123 exact_tag(tag.get_num_threads()));
02124 }
02125
02126
02127 template<
02128 typename RandomAccessIteratorPairIterator
02129 , typename RandomAccessIteratorOut
02130 , typename _DifferenceTp
02131 , typename Comparator>
02132 RandomAccessIteratorOut
02133 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
02134 , RandomAccessIteratorPairIterator seqs_end
02135 , RandomAccessIteratorOut target
02136 , _DifferenceTp length, Comparator comp
02137 , default_parallel_tag tag)
02138 {
02139 return stable_multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp,
02140 exact_tag(tag.get_num_threads()));
02141 }
02142
02143 };
02144
02145 #endif