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