1*38fd1498Szrj // -*- C++ -*- 2*38fd1498Szrj 3*38fd1498Szrj // Copyright (C) 2007-2018 Free Software Foundation, Inc. 4*38fd1498Szrj // 5*38fd1498Szrj // This file is part of the GNU ISO C++ Library. This library is free 6*38fd1498Szrj // software; you can redistribute it and/or modify it under the terms 7*38fd1498Szrj // of the GNU General Public License as published by the Free Software 8*38fd1498Szrj // Foundation; either version 3, or (at your option) any later 9*38fd1498Szrj // version. 10*38fd1498Szrj 11*38fd1498Szrj // This library is distributed in the hope that it will be useful, but 12*38fd1498Szrj // WITHOUT ANY WARRANTY; without even the implied warranty of 13*38fd1498Szrj // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14*38fd1498Szrj // General Public License for more details. 15*38fd1498Szrj 16*38fd1498Szrj // Under Section 7 of GPL version 3, you are granted additional 17*38fd1498Szrj // permissions described in the GCC Runtime Library Exception, version 18*38fd1498Szrj // 3.1, as published by the Free Software Foundation. 19*38fd1498Szrj 20*38fd1498Szrj // You should have received a copy of the GNU General Public License and 21*38fd1498Szrj // a copy of the GCC Runtime Library Exception along with this program; 22*38fd1498Szrj // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23*38fd1498Szrj // <http://www.gnu.org/licenses/>. 24*38fd1498Szrj 25*38fd1498Szrj /** @file parallel/multiway_merge.h 26*38fd1498Szrj * @brief Implementation of sequential and parallel multiway merge. 27*38fd1498Szrj * 28*38fd1498Szrj * Explanations on the high-speed merging routines in the appendix of 29*38fd1498Szrj * 30*38fd1498Szrj * P. Sanders. 31*38fd1498Szrj * Fast priority queues for cached memory. 32*38fd1498Szrj * ACM Journal of Experimental Algorithmics, 5, 2000. 33*38fd1498Szrj * 34*38fd1498Szrj * This file is a GNU parallel extension to the Standard C++ Library. 35*38fd1498Szrj */ 36*38fd1498Szrj 37*38fd1498Szrj // Written by Johannes Singler and Manuel Holtgrewe. 38*38fd1498Szrj 39*38fd1498Szrj #ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H 40*38fd1498Szrj #define _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H 41*38fd1498Szrj 42*38fd1498Szrj #include <vector> 43*38fd1498Szrj 44*38fd1498Szrj #include <bits/stl_algo.h> 45*38fd1498Szrj #include <parallel/features.h> 46*38fd1498Szrj #include <parallel/parallel.h> 47*38fd1498Szrj #include <parallel/losertree.h> 48*38fd1498Szrj #include <parallel/multiseq_selection.h> 49*38fd1498Szrj #if _GLIBCXX_PARALLEL_ASSERTIONS 50*38fd1498Szrj #include <parallel/checkers.h> 51*38fd1498Szrj #endif 52*38fd1498Szrj 53*38fd1498Szrj /** @brief Length of a sequence described by a pair of iterators. */ 54*38fd1498Szrj #define _GLIBCXX_PARALLEL_LENGTH(__s) ((__s).second - (__s).first) 55*38fd1498Szrj 56*38fd1498Szrj namespace __gnu_parallel 57*38fd1498Szrj { 58*38fd1498Szrj template<typename _RAIter1, typename _RAIter2, typename _OutputIterator, 59*38fd1498Szrj typename _DifferenceTp, typename _Compare> 60*38fd1498Szrj _OutputIterator 61*38fd1498Szrj __merge_advance(_RAIter1&, _RAIter1, _RAIter2&, _RAIter2, 62*38fd1498Szrj _OutputIterator, _DifferenceTp, _Compare); 63*38fd1498Szrj 64*38fd1498Szrj /** @brief _Iterator wrapper supporting an implicit supremum at the end 65*38fd1498Szrj * of the sequence, dominating all comparisons. 66*38fd1498Szrj * 67*38fd1498Szrj * The implicit supremum comes with a performance cost. 68*38fd1498Szrj * 69*38fd1498Szrj * Deriving from _RAIter is not possible since 70*38fd1498Szrj * _RAIter need not be a class. 71*38fd1498Szrj */ 72*38fd1498Szrj template<typename _RAIter, typename _Compare> 73*38fd1498Szrj class _GuardedIterator 74*38fd1498Szrj { 75*38fd1498Szrj private: 76*38fd1498Szrj /** @brief Current iterator __position. */ 77*38fd1498Szrj _RAIter _M_current; 78*38fd1498Szrj 79*38fd1498Szrj /** @brief End iterator of the sequence. */ 80*38fd1498Szrj _RAIter _M_end; 81*38fd1498Szrj 82*38fd1498Szrj /** @brief _Compare. */ 83*38fd1498Szrj _Compare& __comp; 84*38fd1498Szrj 85*38fd1498Szrj public: 86*38fd1498Szrj /** @brief Constructor. Sets iterator to beginning of sequence. 87*38fd1498Szrj * @param __begin Begin iterator of sequence. 88*38fd1498Szrj * @param __end End iterator of sequence. 89*38fd1498Szrj * @param __comp Comparator provided for associated overloaded 90*38fd1498Szrj * compare operators. */ _GuardedIterator(_RAIter __begin,_RAIter __end,_Compare & __comp)91*38fd1498Szrj _GuardedIterator(_RAIter __begin, _RAIter __end, _Compare& __comp) 92*38fd1498Szrj : _M_current(__begin), _M_end(__end), __comp(__comp) 93*38fd1498Szrj { } 94*38fd1498Szrj 95*38fd1498Szrj /** @brief Pre-increment operator. 96*38fd1498Szrj * @return This. */ 97*38fd1498Szrj _GuardedIterator<_RAIter, _Compare>& 98*38fd1498Szrj operator++() 99*38fd1498Szrj { 100*38fd1498Szrj ++_M_current; 101*38fd1498Szrj return *this; 102*38fd1498Szrj } 103*38fd1498Szrj 104*38fd1498Szrj /** @brief Dereference operator. 105*38fd1498Szrj * @return Referenced element. */ 106*38fd1498Szrj typename std::iterator_traits<_RAIter>::value_type& 107*38fd1498Szrj operator*() 108*38fd1498Szrj { return *_M_current; } 109*38fd1498Szrj 110*38fd1498Szrj /** @brief Convert to wrapped iterator. 111*38fd1498Szrj * @return Wrapped iterator. */ _RAIter()112*38fd1498Szrj operator _RAIter() 113*38fd1498Szrj { return _M_current; } 114*38fd1498Szrj 115*38fd1498Szrj /** @brief Compare two elements referenced by guarded iterators. 116*38fd1498Szrj * @param __bi1 First iterator. 117*38fd1498Szrj * @param __bi2 Second iterator. 118*38fd1498Szrj * @return @c true if less. */ 119*38fd1498Szrj friend bool 120*38fd1498Szrj operator<(_GuardedIterator<_RAIter, _Compare>& __bi1, 121*38fd1498Szrj _GuardedIterator<_RAIter, _Compare>& __bi2) 122*38fd1498Szrj { 123*38fd1498Szrj if (__bi1._M_current == __bi1._M_end) // __bi1 is sup 124*38fd1498Szrj return __bi2._M_current == __bi2._M_end; // __bi2 is not sup 125*38fd1498Szrj if (__bi2._M_current == __bi2._M_end) // __bi2 is sup 126*38fd1498Szrj return true; 127*38fd1498Szrj return (__bi1.__comp)(*__bi1, *__bi2); // normal compare 128*38fd1498Szrj } 129*38fd1498Szrj 130*38fd1498Szrj /** @brief Compare two elements referenced by guarded iterators. 131*38fd1498Szrj * @param __bi1 First iterator. 132*38fd1498Szrj * @param __bi2 Second iterator. 133*38fd1498Szrj * @return @c True if less equal. */ 134*38fd1498Szrj friend bool 135*38fd1498Szrj operator<=(_GuardedIterator<_RAIter, _Compare>& __bi1, 136*38fd1498Szrj _GuardedIterator<_RAIter, _Compare>& __bi2) 137*38fd1498Szrj { 138*38fd1498Szrj if (__bi2._M_current == __bi2._M_end) // __bi1 is sup 139*38fd1498Szrj return __bi1._M_current != __bi1._M_end; // __bi2 is not sup 140*38fd1498Szrj if (__bi1._M_current == __bi1._M_end) // __bi2 is sup 141*38fd1498Szrj return false; 142*38fd1498Szrj return !(__bi1.__comp)(*__bi2, *__bi1); // normal compare 143*38fd1498Szrj } 144*38fd1498Szrj }; 145*38fd1498Szrj 146*38fd1498Szrj template<typename _RAIter, typename _Compare> 147*38fd1498Szrj class _UnguardedIterator 148*38fd1498Szrj { 149*38fd1498Szrj private: 150*38fd1498Szrj /** @brief Current iterator __position. */ 151*38fd1498Szrj _RAIter _M_current; 152*38fd1498Szrj /** @brief _Compare. */ 153*38fd1498Szrj _Compare& __comp; 154*38fd1498Szrj 155*38fd1498Szrj public: 156*38fd1498Szrj /** @brief Constructor. Sets iterator to beginning of sequence. 157*38fd1498Szrj * @param __begin Begin iterator of sequence. 158*38fd1498Szrj * @param __end Unused, only for compatibility. 159*38fd1498Szrj * @param __comp Unused, only for compatibility. */ _UnguardedIterator(_RAIter __begin,_RAIter,_Compare & __comp)160*38fd1498Szrj _UnguardedIterator(_RAIter __begin, 161*38fd1498Szrj _RAIter /* __end */, _Compare& __comp) 162*38fd1498Szrj : _M_current(__begin), __comp(__comp) 163*38fd1498Szrj { } 164*38fd1498Szrj 165*38fd1498Szrj /** @brief Pre-increment operator. 166*38fd1498Szrj * @return This. */ 167*38fd1498Szrj _UnguardedIterator<_RAIter, _Compare>& 168*38fd1498Szrj operator++() 169*38fd1498Szrj { 170*38fd1498Szrj ++_M_current; 171*38fd1498Szrj return *this; 172*38fd1498Szrj } 173*38fd1498Szrj 174*38fd1498Szrj /** @brief Dereference operator. 175*38fd1498Szrj * @return Referenced element. */ 176*38fd1498Szrj typename std::iterator_traits<_RAIter>::value_type& 177*38fd1498Szrj operator*() 178*38fd1498Szrj { return *_M_current; } 179*38fd1498Szrj 180*38fd1498Szrj /** @brief Convert to wrapped iterator. 181*38fd1498Szrj * @return Wrapped iterator. */ _RAIter()182*38fd1498Szrj operator _RAIter() 183*38fd1498Szrj { return _M_current; } 184*38fd1498Szrj 185*38fd1498Szrj /** @brief Compare two elements referenced by unguarded iterators. 186*38fd1498Szrj * @param __bi1 First iterator. 187*38fd1498Szrj * @param __bi2 Second iterator. 188*38fd1498Szrj * @return @c true if less. */ 189*38fd1498Szrj friend bool 190*38fd1498Szrj operator<(_UnguardedIterator<_RAIter, _Compare>& __bi1, 191*38fd1498Szrj _UnguardedIterator<_RAIter, _Compare>& __bi2) 192*38fd1498Szrj { 193*38fd1498Szrj // Normal compare. 194*38fd1498Szrj return (__bi1.__comp)(*__bi1, *__bi2); 195*38fd1498Szrj } 196*38fd1498Szrj 197*38fd1498Szrj /** @brief Compare two elements referenced by unguarded iterators. 198*38fd1498Szrj * @param __bi1 First iterator. 199*38fd1498Szrj * @param __bi2 Second iterator. 200*38fd1498Szrj * @return @c True if less equal. */ 201*38fd1498Szrj friend bool 202*38fd1498Szrj operator<=(_UnguardedIterator<_RAIter, _Compare>& __bi1, 203*38fd1498Szrj _UnguardedIterator<_RAIter, _Compare>& __bi2) 204*38fd1498Szrj { 205*38fd1498Szrj // Normal compare. 206*38fd1498Szrj return !(__bi1.__comp)(*__bi2, *__bi1); 207*38fd1498Szrj } 208*38fd1498Szrj }; 209*38fd1498Szrj 210*38fd1498Szrj /** @brief Highly efficient 3-way merging procedure. 211*38fd1498Szrj * 212*38fd1498Szrj * Merging is done with the algorithm implementation described by Peter 213*38fd1498Szrj * Sanders. Basically, the idea is to minimize the number of necessary 214*38fd1498Szrj * comparison after merging an element. The implementation trick 215*38fd1498Szrj * that makes this fast is that the order of the sequences is stored 216*38fd1498Szrj * in the instruction pointer (translated into labels in C++). 217*38fd1498Szrj * 218*38fd1498Szrj * This works well for merging up to 4 sequences. 219*38fd1498Szrj * 220*38fd1498Szrj * Note that making the merging stable does @a not come at a 221*38fd1498Szrj * performance hit. 222*38fd1498Szrj * 223*38fd1498Szrj * Whether the merging is done guarded or unguarded is selected by the 224*38fd1498Szrj * used iterator class. 225*38fd1498Szrj * 226*38fd1498Szrj * @param __seqs_begin Begin iterator of iterator pair input sequence. 227*38fd1498Szrj * @param __seqs_end End iterator of iterator pair input sequence. 228*38fd1498Szrj * @param __target Begin iterator of output sequence. 229*38fd1498Szrj * @param __comp Comparator. 230*38fd1498Szrj * @param __length Maximum length to merge, less equal than the 231*38fd1498Szrj * total number of elements available. 232*38fd1498Szrj * 233*38fd1498Szrj * @return End iterator of output sequence. 234*38fd1498Szrj */ 235*38fd1498Szrj template<template<typename RAI, typename C> class iterator, 236*38fd1498Szrj typename _RAIterIterator, 237*38fd1498Szrj typename _RAIter3, 238*38fd1498Szrj typename _DifferenceTp, 239*38fd1498Szrj typename _Compare> 240*38fd1498Szrj _RAIter3 multiway_merge_3_variant(_RAIterIterator __seqs_begin,_RAIterIterator __seqs_end,_RAIter3 __target,_DifferenceTp __length,_Compare __comp)241*38fd1498Szrj multiway_merge_3_variant(_RAIterIterator __seqs_begin, 242*38fd1498Szrj _RAIterIterator __seqs_end, 243*38fd1498Szrj _RAIter3 __target, 244*38fd1498Szrj _DifferenceTp __length, _Compare __comp) 245*38fd1498Szrj { 246*38fd1498Szrj _GLIBCXX_CALL(__length); 247*38fd1498Szrj 248*38fd1498Szrj typedef _DifferenceTp _DifferenceType; 249*38fd1498Szrj 250*38fd1498Szrj typedef typename std::iterator_traits<_RAIterIterator> 251*38fd1498Szrj ::value_type::first_type 252*38fd1498Szrj _RAIter1; 253*38fd1498Szrj typedef typename std::iterator_traits<_RAIter1>::value_type 254*38fd1498Szrj _ValueType; 255*38fd1498Szrj 256*38fd1498Szrj if (__length == 0) 257*38fd1498Szrj return __target; 258*38fd1498Szrj 259*38fd1498Szrj #if _GLIBCXX_PARALLEL_ASSERTIONS 260*38fd1498Szrj _DifferenceTp __orig_length = __length; 261*38fd1498Szrj #endif 262*38fd1498Szrj 263*38fd1498Szrj iterator<_RAIter1, _Compare> 264*38fd1498Szrj __seq0(__seqs_begin[0].first, __seqs_begin[0].second, __comp), 265*38fd1498Szrj __seq1(__seqs_begin[1].first, __seqs_begin[1].second, __comp), 266*38fd1498Szrj __seq2(__seqs_begin[2].first, __seqs_begin[2].second, __comp); 267*38fd1498Szrj 268*38fd1498Szrj if (__seq0 <= __seq1) 269*38fd1498Szrj { 270*38fd1498Szrj if (__seq1 <= __seq2) 271*38fd1498Szrj goto __s012; 272*38fd1498Szrj else 273*38fd1498Szrj if (__seq2 < __seq0) 274*38fd1498Szrj goto __s201; 275*38fd1498Szrj else 276*38fd1498Szrj goto __s021; 277*38fd1498Szrj } 278*38fd1498Szrj else 279*38fd1498Szrj { 280*38fd1498Szrj if (__seq1 <= __seq2) 281*38fd1498Szrj { 282*38fd1498Szrj if (__seq0 <= __seq2) 283*38fd1498Szrj goto __s102; 284*38fd1498Szrj else 285*38fd1498Szrj goto __s120; 286*38fd1498Szrj } 287*38fd1498Szrj else 288*38fd1498Szrj goto __s210; 289*38fd1498Szrj } 290*38fd1498Szrj #define _GLIBCXX_PARALLEL_MERGE_3_CASE(__a, __b, __c, __c0, __c1) \ 291*38fd1498Szrj __s ## __a ## __b ## __c : \ 292*38fd1498Szrj *__target = *__seq ## __a; \ 293*38fd1498Szrj ++__target; \ 294*38fd1498Szrj --__length; \ 295*38fd1498Szrj ++__seq ## __a; \ 296*38fd1498Szrj if (__length == 0) goto __finish; \ 297*38fd1498Szrj if (__seq ## __a __c0 __seq ## __b) goto __s ## __a ## __b ## __c; \ 298*38fd1498Szrj if (__seq ## __a __c1 __seq ## __c) goto __s ## __b ## __a ## __c; \ 299*38fd1498Szrj goto __s ## __b ## __c ## __a; 300*38fd1498Szrj 301*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 1, 2, <=, <=); 302*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 2, 0, <=, < ); 303*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 0, 1, < , < ); 304*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 0, 2, < , <=); 305*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 2, 1, <=, <=); 306*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 1, 0, < , < ); 307*38fd1498Szrj 308*38fd1498Szrj #undef _GLIBCXX_PARALLEL_MERGE_3_CASE 309*38fd1498Szrj 310*38fd1498Szrj __finish: 311*38fd1498Szrj ; 312*38fd1498Szrj 313*38fd1498Szrj #if _GLIBCXX_PARALLEL_ASSERTIONS 314*38fd1498Szrj _GLIBCXX_PARALLEL_ASSERT( 315*38fd1498Szrj ((_RAIter1)__seq0 - __seqs_begin[0].first) + 316*38fd1498Szrj ((_RAIter1)__seq1 - __seqs_begin[1].first) + 317*38fd1498Szrj ((_RAIter1)__seq2 - __seqs_begin[2].first) 318*38fd1498Szrj == __orig_length); 319*38fd1498Szrj #endif 320*38fd1498Szrj 321*38fd1498Szrj __seqs_begin[0].first = __seq0; 322*38fd1498Szrj __seqs_begin[1].first = __seq1; 323*38fd1498Szrj __seqs_begin[2].first = __seq2; 324*38fd1498Szrj 325*38fd1498Szrj return __target; 326*38fd1498Szrj } 327*38fd1498Szrj 328*38fd1498Szrj /** 329*38fd1498Szrj * @brief Highly efficient 4-way merging procedure. 330*38fd1498Szrj * 331*38fd1498Szrj * Merging is done with the algorithm implementation described by Peter 332*38fd1498Szrj * Sanders. Basically, the idea is to minimize the number of necessary 333*38fd1498Szrj * comparison after merging an element. The implementation trick 334*38fd1498Szrj * that makes this fast is that the order of the sequences is stored 335*38fd1498Szrj * in the instruction pointer (translated into goto labels in C++). 336*38fd1498Szrj * 337*38fd1498Szrj * This works well for merging up to 4 sequences. 338*38fd1498Szrj * 339*38fd1498Szrj * Note that making the merging stable does @a not come at a 340*38fd1498Szrj * performance hit. 341*38fd1498Szrj * 342*38fd1498Szrj * Whether the merging is done guarded or unguarded is selected by the 343*38fd1498Szrj * used iterator class. 344*38fd1498Szrj * 345*38fd1498Szrj * @param __seqs_begin Begin iterator of iterator pair input sequence. 346*38fd1498Szrj * @param __seqs_end End iterator of iterator pair input sequence. 347*38fd1498Szrj * @param __target Begin iterator of output sequence. 348*38fd1498Szrj * @param __comp Comparator. 349*38fd1498Szrj * @param __length Maximum length to merge, less equal than the 350*38fd1498Szrj * total number of elements available. 351*38fd1498Szrj * 352*38fd1498Szrj * @return End iterator of output sequence. 353*38fd1498Szrj */ 354*38fd1498Szrj template<template<typename RAI, typename C> class iterator, 355*38fd1498Szrj typename _RAIterIterator, 356*38fd1498Szrj typename _RAIter3, 357*38fd1498Szrj typename _DifferenceTp, 358*38fd1498Szrj typename _Compare> 359*38fd1498Szrj _RAIter3 multiway_merge_4_variant(_RAIterIterator __seqs_begin,_RAIterIterator __seqs_end,_RAIter3 __target,_DifferenceTp __length,_Compare __comp)360*38fd1498Szrj multiway_merge_4_variant(_RAIterIterator __seqs_begin, 361*38fd1498Szrj _RAIterIterator __seqs_end, 362*38fd1498Szrj _RAIter3 __target, 363*38fd1498Szrj _DifferenceTp __length, _Compare __comp) 364*38fd1498Szrj { 365*38fd1498Szrj _GLIBCXX_CALL(__length); 366*38fd1498Szrj typedef _DifferenceTp _DifferenceType; 367*38fd1498Szrj 368*38fd1498Szrj typedef typename std::iterator_traits<_RAIterIterator> 369*38fd1498Szrj ::value_type::first_type 370*38fd1498Szrj _RAIter1; 371*38fd1498Szrj typedef typename std::iterator_traits<_RAIter1>::value_type 372*38fd1498Szrj _ValueType; 373*38fd1498Szrj 374*38fd1498Szrj iterator<_RAIter1, _Compare> 375*38fd1498Szrj __seq0(__seqs_begin[0].first, __seqs_begin[0].second, __comp), 376*38fd1498Szrj __seq1(__seqs_begin[1].first, __seqs_begin[1].second, __comp), 377*38fd1498Szrj __seq2(__seqs_begin[2].first, __seqs_begin[2].second, __comp), 378*38fd1498Szrj __seq3(__seqs_begin[3].first, __seqs_begin[3].second, __comp); 379*38fd1498Szrj 380*38fd1498Szrj #define _GLIBCXX_PARALLEL_DECISION(__a, __b, __c, __d) { \ 381*38fd1498Szrj if (__seq ## __d < __seq ## __a) \ 382*38fd1498Szrj goto __s ## __d ## __a ## __b ## __c; \ 383*38fd1498Szrj if (__seq ## __d < __seq ## __b) \ 384*38fd1498Szrj goto __s ## __a ## __d ## __b ## __c; \ 385*38fd1498Szrj if (__seq ## __d < __seq ## __c) \ 386*38fd1498Szrj goto __s ## __a ## __b ## __d ## __c; \ 387*38fd1498Szrj goto __s ## __a ## __b ## __c ## __d; } 388*38fd1498Szrj 389*38fd1498Szrj if (__seq0 <= __seq1) 390*38fd1498Szrj { 391*38fd1498Szrj if (__seq1 <= __seq2) 392*38fd1498Szrj _GLIBCXX_PARALLEL_DECISION(0,1,2,3) 393*38fd1498Szrj else 394*38fd1498Szrj if (__seq2 < __seq0) 395*38fd1498Szrj _GLIBCXX_PARALLEL_DECISION(2,0,1,3) 396*38fd1498Szrj else 397*38fd1498Szrj _GLIBCXX_PARALLEL_DECISION(0,2,1,3) 398*38fd1498Szrj } 399*38fd1498Szrj else 400*38fd1498Szrj { 401*38fd1498Szrj if (__seq1 <= __seq2) 402*38fd1498Szrj { 403*38fd1498Szrj if (__seq0 <= __seq2) 404*38fd1498Szrj _GLIBCXX_PARALLEL_DECISION(1,0,2,3) 405*38fd1498Szrj else 406*38fd1498Szrj _GLIBCXX_PARALLEL_DECISION(1,2,0,3) 407*38fd1498Szrj } 408*38fd1498Szrj else 409*38fd1498Szrj _GLIBCXX_PARALLEL_DECISION(2,1,0,3) 410*38fd1498Szrj } 411*38fd1498Szrj 412*38fd1498Szrj #define _GLIBCXX_PARALLEL_MERGE_4_CASE(__a, __b, __c, __d, \ 413*38fd1498Szrj __c0, __c1, __c2) \ 414*38fd1498Szrj __s ## __a ## __b ## __c ## __d: \ 415*38fd1498Szrj if (__length == 0) goto __finish; \ 416*38fd1498Szrj *__target = *__seq ## __a; \ 417*38fd1498Szrj ++__target; \ 418*38fd1498Szrj --__length; \ 419*38fd1498Szrj ++__seq ## __a; \ 420*38fd1498Szrj if (__seq ## __a __c0 __seq ## __b) \ 421*38fd1498Szrj goto __s ## __a ## __b ## __c ## __d; \ 422*38fd1498Szrj if (__seq ## __a __c1 __seq ## __c) \ 423*38fd1498Szrj goto __s ## __b ## __a ## __c ## __d; \ 424*38fd1498Szrj if (__seq ## __a __c2 __seq ## __d) \ 425*38fd1498Szrj goto __s ## __b ## __c ## __a ## __d; \ 426*38fd1498Szrj goto __s ## __b ## __c ## __d ## __a; 427*38fd1498Szrj 428*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 2, 3, <=, <=, <=); 429*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 3, 2, <=, <=, <=); 430*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 1, 3, <=, <=, <=); 431*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 3, 1, <=, <=, <=); 432*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 1, 2, <=, <=, <=); 433*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 2, 1, <=, <=, <=); 434*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 2, 3, < , <=, <=); 435*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 3, 2, < , <=, <=); 436*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 0, 3, <=, < , <=); 437*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 3, 0, <=, <=, < ); 438*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 0, 2, <=, < , <=); 439*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 2, 0, <=, <=, < ); 440*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 1, 3, < , < , <=); 441*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 3, 1, < , <=, < ); 442*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 0, 3, < , < , <=); 443*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 3, 0, < , <=, < ); 444*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 0, 1, <=, < , < ); 445*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 1, 0, <=, < , < ); 446*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 1, 2, < , < , < ); 447*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 2, 1, < , < , < ); 448*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 0, 2, < , < , < ); 449*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 2, 0, < , < , < ); 450*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 0, 1, < , < , < ); 451*38fd1498Szrj _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 1, 0, < , < , < ); 452*38fd1498Szrj 453*38fd1498Szrj #undef _GLIBCXX_PARALLEL_MERGE_4_CASE 454*38fd1498Szrj #undef _GLIBCXX_PARALLEL_DECISION 455*38fd1498Szrj 456*38fd1498Szrj __finish: 457*38fd1498Szrj ; 458*38fd1498Szrj 459*38fd1498Szrj __seqs_begin[0].first = __seq0; 460*38fd1498Szrj __seqs_begin[1].first = __seq1; 461*38fd1498Szrj __seqs_begin[2].first = __seq2; 462*38fd1498Szrj __seqs_begin[3].first = __seq3; 463*38fd1498Szrj 464*38fd1498Szrj return __target; 465*38fd1498Szrj } 466*38fd1498Szrj 467*38fd1498Szrj /** @brief Multi-way merging procedure for a high branching factor, 468*38fd1498Szrj * guarded case. 469*38fd1498Szrj * 470*38fd1498Szrj * This merging variant uses a LoserTree class as selected by <tt>_LT</tt>. 471*38fd1498Szrj * 472*38fd1498Szrj * Stability is selected through the used LoserTree class <tt>_LT</tt>. 473*38fd1498Szrj * 474*38fd1498Szrj * At least one non-empty sequence is required. 475*38fd1498Szrj * 476*38fd1498Szrj * @param __seqs_begin Begin iterator of iterator pair input sequence. 477*38fd1498Szrj * @param __seqs_end End iterator of iterator pair input sequence. 478*38fd1498Szrj * @param __target Begin iterator of output sequence. 479*38fd1498Szrj * @param __comp Comparator. 480*38fd1498Szrj * @param __length Maximum length to merge, less equal than the 481*38fd1498Szrj * total number of elements available. 482*38fd1498Szrj * 483*38fd1498Szrj * @return End iterator of output sequence. 484*38fd1498Szrj */ 485*38fd1498Szrj template<typename _LT, 486*38fd1498Szrj typename _RAIterIterator, 487*38fd1498Szrj typename _RAIter3, 488*38fd1498Szrj typename _DifferenceTp, 489*38fd1498Szrj typename _Compare> 490*38fd1498Szrj _RAIter3 multiway_merge_loser_tree(_RAIterIterator __seqs_begin,_RAIterIterator __seqs_end,_RAIter3 __target,_DifferenceTp __length,_Compare __comp)491*38fd1498Szrj multiway_merge_loser_tree(_RAIterIterator __seqs_begin, 492*38fd1498Szrj _RAIterIterator __seqs_end, 493*38fd1498Szrj _RAIter3 __target, 494*38fd1498Szrj _DifferenceTp __length, _Compare __comp) 495*38fd1498Szrj { 496*38fd1498Szrj _GLIBCXX_CALL(__length) 497*38fd1498Szrj 498*38fd1498Szrj typedef _DifferenceTp _DifferenceType; 499*38fd1498Szrj typedef typename std::iterator_traits<_RAIterIterator> 500*38fd1498Szrj ::difference_type _SeqNumber; 501*38fd1498Szrj typedef typename std::iterator_traits<_RAIterIterator> 502*38fd1498Szrj ::value_type::first_type 503*38fd1498Szrj _RAIter1; 504*38fd1498Szrj typedef typename std::iterator_traits<_RAIter1>::value_type 505*38fd1498Szrj _ValueType; 506*38fd1498Szrj 507*38fd1498Szrj _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin); 508*38fd1498Szrj 509*38fd1498Szrj _LT __lt(__k, __comp); 510*38fd1498Szrj 511*38fd1498Szrj // Default value for potentially non-default-constructible types. 512*38fd1498Szrj _ValueType* __arbitrary_element = 0; 513*38fd1498Szrj 514*38fd1498Szrj for (_SeqNumber __t = 0; __t < __k; ++__t) 515*38fd1498Szrj { 516*38fd1498Szrj if(!__arbitrary_element 517*38fd1498Szrj && _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__t]) > 0) 518*38fd1498Szrj __arbitrary_element = &(*__seqs_begin[__t].first); 519*38fd1498Szrj } 520*38fd1498Szrj 521*38fd1498Szrj for (_SeqNumber __t = 0; __t < __k; ++__t) 522*38fd1498Szrj { 523*38fd1498Szrj if (__seqs_begin[__t].first == __seqs_begin[__t].second) 524*38fd1498Szrj __lt.__insert_start(*__arbitrary_element, __t, true); 525*38fd1498Szrj else 526*38fd1498Szrj __lt.__insert_start(*__seqs_begin[__t].first, __t, false); 527*38fd1498Szrj } 528*38fd1498Szrj 529*38fd1498Szrj __lt.__init(); 530*38fd1498Szrj 531*38fd1498Szrj _SeqNumber __source; 532*38fd1498Szrj 533*38fd1498Szrj for (_DifferenceType __i = 0; __i < __length; ++__i) 534*38fd1498Szrj { 535*38fd1498Szrj //take out 536*38fd1498Szrj __source = __lt.__get_min_source(); 537*38fd1498Szrj 538*38fd1498Szrj *(__target++) = *(__seqs_begin[__source].first++); 539*38fd1498Szrj 540*38fd1498Szrj // Feed. 541*38fd1498Szrj if (__seqs_begin[__source].first == __seqs_begin[__source].second) 542*38fd1498Szrj __lt.__delete_min_insert(*__arbitrary_element, true); 543*38fd1498Szrj else 544*38fd1498Szrj // Replace from same __source. 545*38fd1498Szrj __lt.__delete_min_insert(*__seqs_begin[__source].first, false); 546*38fd1498Szrj } 547*38fd1498Szrj 548*38fd1498Szrj return __target; 549*38fd1498Szrj } 550*38fd1498Szrj 551*38fd1498Szrj /** @brief Multi-way merging procedure for a high branching factor, 552*38fd1498Szrj * unguarded case. 553*38fd1498Szrj * 554*38fd1498Szrj * Merging is done using the LoserTree class <tt>_LT</tt>. 555*38fd1498Szrj * 556*38fd1498Szrj * Stability is selected by the used LoserTrees. 557*38fd1498Szrj * 558*38fd1498Szrj * @pre No input will run out of elements during the merge. 559*38fd1498Szrj * 560*38fd1498Szrj * @param __seqs_begin Begin iterator of iterator pair input sequence. 561*38fd1498Szrj * @param __seqs_end End iterator of iterator pair input sequence. 562*38fd1498Szrj * @param __target Begin iterator of output sequence. 563*38fd1498Szrj * @param __comp Comparator. 564*38fd1498Szrj * @param __length Maximum length to merge, less equal than the 565*38fd1498Szrj * total number of elements available. 566*38fd1498Szrj * 567*38fd1498Szrj * @return End iterator of output sequence. 568*38fd1498Szrj */ 569*38fd1498Szrj template<typename _LT, 570*38fd1498Szrj typename _RAIterIterator, 571*38fd1498Szrj typename _RAIter3, 572*38fd1498Szrj typename _DifferenceTp, typename _Compare> 573*38fd1498Szrj _RAIter3 multiway_merge_loser_tree_unguarded(_RAIterIterator __seqs_begin,_RAIterIterator __seqs_end,_RAIter3 __target,const typename std::iterator_traits<typename std::iterator_traits<_RAIterIterator>::value_type::first_type>::value_type & __sentinel,_DifferenceTp __length,_Compare __comp)574*38fd1498Szrj multiway_merge_loser_tree_unguarded(_RAIterIterator __seqs_begin, 575*38fd1498Szrj _RAIterIterator __seqs_end, 576*38fd1498Szrj _RAIter3 __target, 577*38fd1498Szrj const typename std::iterator_traits<typename std::iterator_traits< 578*38fd1498Szrj _RAIterIterator>::value_type::first_type>::value_type& 579*38fd1498Szrj __sentinel, 580*38fd1498Szrj _DifferenceTp __length, 581*38fd1498Szrj _Compare __comp) 582*38fd1498Szrj { 583*38fd1498Szrj _GLIBCXX_CALL(__length) 584*38fd1498Szrj typedef _DifferenceTp _DifferenceType; 585*38fd1498Szrj 586*38fd1498Szrj typedef typename std::iterator_traits<_RAIterIterator> 587*38fd1498Szrj ::difference_type _SeqNumber; 588*38fd1498Szrj typedef typename std::iterator_traits<_RAIterIterator> 589*38fd1498Szrj ::value_type::first_type 590*38fd1498Szrj _RAIter1; 591*38fd1498Szrj typedef typename std::iterator_traits<_RAIter1>::value_type 592*38fd1498Szrj _ValueType; 593*38fd1498Szrj 594*38fd1498Szrj _SeqNumber __k = __seqs_end - __seqs_begin; 595*38fd1498Szrj 596*38fd1498Szrj _LT __lt(__k, __sentinel, __comp); 597*38fd1498Szrj 598*38fd1498Szrj for (_SeqNumber __t = 0; __t < __k; ++__t) 599*38fd1498Szrj { 600*38fd1498Szrj #if _GLIBCXX_PARALLEL_ASSERTIONS 601*38fd1498Szrj _GLIBCXX_PARALLEL_ASSERT(__seqs_begin[__t].first 602*38fd1498Szrj != __seqs_begin[__t].second); 603*38fd1498Szrj #endif 604*38fd1498Szrj __lt.__insert_start(*__seqs_begin[__t].first, __t, false); 605*38fd1498Szrj } 606*38fd1498Szrj 607*38fd1498Szrj __lt.__init(); 608*38fd1498Szrj 609*38fd1498Szrj _SeqNumber __source; 610*38fd1498Szrj 611*38fd1498Szrj #if _GLIBCXX_PARALLEL_ASSERTIONS 612*38fd1498Szrj _DifferenceType __i = 0; 613*38fd1498Szrj #endif 614*38fd1498Szrj 615*38fd1498Szrj _RAIter3 __target_end = __target + __length; 616*38fd1498Szrj while (__target < __target_end) 617*38fd1498Szrj { 618*38fd1498Szrj // Take out. 619*38fd1498Szrj __source = __lt.__get_min_source(); 620*38fd1498Szrj 621*38fd1498Szrj #if _GLIBCXX_PARALLEL_ASSERTIONS 622*38fd1498Szrj _GLIBCXX_PARALLEL_ASSERT(0 <= __source && __source < __k); 623*38fd1498Szrj _GLIBCXX_PARALLEL_ASSERT(__i == 0 624*38fd1498Szrj || !__comp(*(__seqs_begin[__source].first), *(__target - 1))); 625*38fd1498Szrj #endif 626*38fd1498Szrj 627*38fd1498Szrj // Feed. 628*38fd1498Szrj *(__target++) = *(__seqs_begin[__source].first++); 629*38fd1498Szrj 630*38fd1498Szrj #if _GLIBCXX_PARALLEL_ASSERTIONS 631*38fd1498Szrj ++__i; 632*38fd1498Szrj #endif 633*38fd1498Szrj // Replace from same __source. 634*38fd1498Szrj __lt.__delete_min_insert(*__seqs_begin[__source].first, false); 635*38fd1498Szrj } 636*38fd1498Szrj 637*38fd1498Szrj return __target; 638*38fd1498Szrj } 639*38fd1498Szrj 640*38fd1498Szrj 641*38fd1498Szrj /** @brief Multi-way merging procedure for a high branching factor, 642*38fd1498Szrj * requiring sentinels to exist. 643*38fd1498Szrj * 644*38fd1498Szrj * @tparam UnguardedLoserTree _Loser Tree variant to use for the unguarded 645*38fd1498Szrj * merging. 646*38fd1498Szrj * 647*38fd1498Szrj * @param __seqs_begin Begin iterator of iterator pair input sequence. 648*38fd1498Szrj * @param __seqs_end End iterator of iterator pair input sequence. 649*38fd1498Szrj * @param __target Begin iterator of output sequence. 650*38fd1498Szrj * @param __comp Comparator. 651*38fd1498Szrj * @param __length Maximum length to merge, less equal than the 652*38fd1498Szrj * total number of elements available. 653*38fd1498Szrj * 654*38fd1498Szrj * @return End iterator of output sequence. 655*38fd1498Szrj */ 656*38fd1498Szrj template<typename UnguardedLoserTree, 657*38fd1498Szrj typename _RAIterIterator, 658*38fd1498Szrj typename _RAIter3, 659*38fd1498Szrj typename _DifferenceTp, 660*38fd1498Szrj typename _Compare> 661*38fd1498Szrj _RAIter3 multiway_merge_loser_tree_sentinel(_RAIterIterator __seqs_begin,_RAIterIterator __seqs_end,_RAIter3 __target,const typename std::iterator_traits<typename std::iterator_traits<_RAIterIterator>::value_type::first_type>::value_type & __sentinel,_DifferenceTp __length,_Compare __comp)662*38fd1498Szrj multiway_merge_loser_tree_sentinel(_RAIterIterator __seqs_begin, 663*38fd1498Szrj _RAIterIterator __seqs_end, 664*38fd1498Szrj _RAIter3 __target, 665*38fd1498Szrj const typename std::iterator_traits<typename std::iterator_traits< 666*38fd1498Szrj _RAIterIterator>::value_type::first_type>::value_type& 667*38fd1498Szrj __sentinel, 668*38fd1498Szrj _DifferenceTp __length, 669*38fd1498Szrj _Compare __comp) 670*38fd1498Szrj { 671*38fd1498Szrj _GLIBCXX_CALL(__length) 672*38fd1498Szrj 673*38fd1498Szrj typedef _DifferenceTp _DifferenceType; 674*38fd1498Szrj typedef std::iterator_traits<_RAIterIterator> _TraitsType; 675*38fd1498Szrj typedef typename std::iterator_traits<_RAIterIterator> 676*38fd1498Szrj ::value_type::first_type 677*38fd1498Szrj _RAIter1; 678*38fd1498Szrj typedef typename std::iterator_traits<_RAIter1>::value_type 679*38fd1498Szrj _ValueType; 680*38fd1498Szrj 681*38fd1498Szrj _RAIter3 __target_end; 682*38fd1498Szrj 683*38fd1498Szrj for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s) 684*38fd1498Szrj // Move the sequence ends to the sentinel. This has the 685*38fd1498Szrj // effect that the sentinel appears to be within the sequence. Then, 686*38fd1498Szrj // we can use the unguarded variant if we merge out as many 687*38fd1498Szrj // non-sentinel elements as we have. 688*38fd1498Szrj ++((*__s).second); 689*38fd1498Szrj 690*38fd1498Szrj __target_end = multiway_merge_loser_tree_unguarded<UnguardedLoserTree> 691*38fd1498Szrj (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp); 692*38fd1498Szrj 693*38fd1498Szrj #if _GLIBCXX_PARALLEL_ASSERTIONS 694*38fd1498Szrj _GLIBCXX_PARALLEL_ASSERT(__target_end == __target + __length); 695*38fd1498Szrj _GLIBCXX_PARALLEL_ASSERT(__is_sorted(__target, __target_end, __comp)); 696*38fd1498Szrj #endif 697*38fd1498Szrj 698*38fd1498Szrj // Restore the sequence ends so the sentinels are not contained in the 699*38fd1498Szrj // sequence any more (see comment in loop above). 700*38fd1498Szrj for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s) 701*38fd1498Szrj --((*__s).second); 702*38fd1498Szrj 703*38fd1498Szrj return __target_end; 704*38fd1498Szrj } 705*38fd1498Szrj 706*38fd1498Szrj /** 707*38fd1498Szrj * @brief Traits for determining whether the loser tree should 708*38fd1498Szrj * use pointers or copies. 709*38fd1498Szrj * 710*38fd1498Szrj * The field "_M_use_pointer" is used to determine whether to use pointers 711*38fd1498Szrj * in he loser trees or whether to copy the values into the loser tree. 712*38fd1498Szrj * 713*38fd1498Szrj * The default behavior is to use pointers if the data type is 4 times as 714*38fd1498Szrj * big as the pointer to it. 715*38fd1498Szrj * 716*38fd1498Szrj * Specialize for your data type to customize the behavior. 717*38fd1498Szrj * 718*38fd1498Szrj * Example: 719*38fd1498Szrj * 720*38fd1498Szrj * template<> 721*38fd1498Szrj * struct _LoserTreeTraits<int> 722*38fd1498Szrj * { static const bool _M_use_pointer = false; }; 723*38fd1498Szrj * 724*38fd1498Szrj * template<> 725*38fd1498Szrj * struct _LoserTreeTraits<heavyweight_type> 726*38fd1498Szrj * { static const bool _M_use_pointer = true; }; 727*38fd1498Szrj * 728*38fd1498Szrj * @param _Tp type to give the loser tree traits for. 729*38fd1498Szrj */ 730*38fd1498Szrj template <typename _Tp> 731*38fd1498Szrj struct _LoserTreeTraits 732*38fd1498Szrj { 733*38fd1498Szrj /** 734*38fd1498Szrj * @brief True iff to use pointers instead of values in loser trees. 735*38fd1498Szrj * 736*38fd1498Szrj * The default behavior is to use pointers if the data type is four 737*38fd1498Szrj * times as big as the pointer to it. 738*38fd1498Szrj */ 739*38fd1498Szrj static const bool _M_use_pointer = (sizeof(_Tp) > 4 * sizeof(_Tp*)); 740*38fd1498Szrj }; 741*38fd1498Szrj 742*38fd1498Szrj /** 743*38fd1498Szrj * @brief Switch for 3-way merging with __sentinels turned off. 744*38fd1498Szrj * 745*38fd1498Szrj * Note that 3-way merging is always stable! 746*38fd1498Szrj */ 747*38fd1498Szrj template<bool __sentinels /*default == false*/, 748*38fd1498Szrj typename _RAIterIterator, 749*38fd1498Szrj typename _RAIter3, 750*38fd1498Szrj typename _DifferenceTp, 751*38fd1498Szrj typename _Compare> 752*38fd1498Szrj struct __multiway_merge_3_variant_sentinel_switch 753*38fd1498Szrj { 754*38fd1498Szrj _RAIter3 operator__multiway_merge_3_variant_sentinel_switch755*38fd1498Szrj operator()(_RAIterIterator __seqs_begin, 756*38fd1498Szrj _RAIterIterator __seqs_end, 757*38fd1498Szrj _RAIter3 __target, 758*38fd1498Szrj _DifferenceTp __length, _Compare __comp) 759*38fd1498Szrj { return multiway_merge_3_variant<_GuardedIterator> 760*38fd1498Szrj (__seqs_begin, __seqs_end, __target, __length, __comp); } 761*38fd1498Szrj }; 762*38fd1498Szrj 763*38fd1498Szrj /** 764*38fd1498Szrj * @brief Switch for 3-way merging with __sentinels turned on. 765*38fd1498Szrj * 766*38fd1498Szrj * Note that 3-way merging is always stable! 767*38fd1498Szrj */ 768*38fd1498Szrj template<typename _RAIterIterator, 769*38fd1498Szrj typename _RAIter3, 770*38fd1498Szrj typename _DifferenceTp, 771*38fd1498Szrj typename _Compare> 772*38fd1498Szrj struct __multiway_merge_3_variant_sentinel_switch<true, _RAIterIterator, 773*38fd1498Szrj _RAIter3, _DifferenceTp, 774*38fd1498Szrj _Compare> 775*38fd1498Szrj { 776*38fd1498Szrj _RAIter3 777*38fd1498Szrj operator()(_RAIterIterator __seqs_begin, 778*38fd1498Szrj _RAIterIterator __seqs_end, 779*38fd1498Szrj _RAIter3 __target, 780*38fd1498Szrj _DifferenceTp __length, _Compare __comp) 781*38fd1498Szrj { return multiway_merge_3_variant<_UnguardedIterator> 782*38fd1498Szrj (__seqs_begin, __seqs_end, __target, __length, __comp); } 783*38fd1498Szrj }; 784*38fd1498Szrj 785*38fd1498Szrj /** 786*38fd1498Szrj * @brief Switch for 4-way merging with __sentinels turned off. 787*38fd1498Szrj * 788*38fd1498Szrj * Note that 4-way merging is always stable! 789*38fd1498Szrj */ 790*38fd1498Szrj template<bool __sentinels /*default == false*/, 791*38fd1498Szrj typename _RAIterIterator, 792*38fd1498Szrj typename _RAIter3, 793*38fd1498Szrj typename _DifferenceTp, 794*38fd1498Szrj typename _Compare> 795*38fd1498Szrj struct __multiway_merge_4_variant_sentinel_switch 796*38fd1498Szrj { 797*38fd1498Szrj _RAIter3 798*38fd1498Szrj operator()(_RAIterIterator __seqs_begin, 799*38fd1498Szrj _RAIterIterator __seqs_end, 800*38fd1498Szrj _RAIter3 __target, 801*38fd1498Szrj _DifferenceTp __length, _Compare __comp) 802*38fd1498Szrj { return multiway_merge_4_variant<_GuardedIterator> 803*38fd1498Szrj (__seqs_begin, __seqs_end, __target, __length, __comp); } 804*38fd1498Szrj }; 805*38fd1498Szrj 806*38fd1498Szrj /** 807*38fd1498Szrj * @brief Switch for 4-way merging with __sentinels turned on. 808*38fd1498Szrj * 809*38fd1498Szrj * Note that 4-way merging is always stable! 810*38fd1498Szrj */ 811*38fd1498Szrj template<typename _RAIterIterator, 812*38fd1498Szrj typename _RAIter3, 813*38fd1498Szrj typename _DifferenceTp, 814*38fd1498Szrj typename _Compare> 815*38fd1498Szrj struct __multiway_merge_4_variant_sentinel_switch<true, _RAIterIterator, 816*38fd1498Szrj _RAIter3, _DifferenceTp, 817*38fd1498Szrj _Compare> 818*38fd1498Szrj { 819*38fd1498Szrj _RAIter3 820*38fd1498Szrj operator()(_RAIterIterator __seqs_begin, 821*38fd1498Szrj _RAIterIterator __seqs_end, 822*38fd1498Szrj _RAIter3 __target, 823*38fd1498Szrj _DifferenceTp __length, _Compare __comp) 824*38fd1498Szrj { return multiway_merge_4_variant<_UnguardedIterator> 825*38fd1498Szrj (__seqs_begin, __seqs_end, __target, __length, __comp); } 826*38fd1498Szrj }; 827*38fd1498Szrj 828*38fd1498Szrj /** 829*38fd1498Szrj * @brief Switch for k-way merging with __sentinels turned on. 830*38fd1498Szrj */ 831*38fd1498Szrj template<bool __sentinels, 832*38fd1498Szrj bool __stable, 833*38fd1498Szrj typename _RAIterIterator, 834*38fd1498Szrj typename _RAIter3, 835*38fd1498Szrj typename _DifferenceTp, 836*38fd1498Szrj typename _Compare> 837*38fd1498Szrj struct __multiway_merge_k_variant_sentinel_switch 838*38fd1498Szrj { 839*38fd1498Szrj _RAIter3 840*38fd1498Szrj operator()(_RAIterIterator __seqs_begin, 841*38fd1498Szrj _RAIterIterator __seqs_end, 842*38fd1498Szrj _RAIter3 __target, 843*38fd1498Szrj const typename std::iterator_traits<typename std::iterator_traits< 844*38fd1498Szrj _RAIterIterator>::value_type::first_type>::value_type& 845*38fd1498Szrj __sentinel, 846*38fd1498Szrj _DifferenceTp __length, _Compare __comp) 847*38fd1498Szrj { 848*38fd1498Szrj typedef typename std::iterator_traits<_RAIterIterator> 849*38fd1498Szrj ::value_type::first_type 850*38fd1498Szrj _RAIter1; 851*38fd1498Szrj typedef typename std::iterator_traits<_RAIter1>::value_type 852*38fd1498Szrj _ValueType; 853*38fd1498Szrj 854*38fd1498Szrj return multiway_merge_loser_tree_sentinel< 855*38fd1498Szrj typename __gnu_cxx::__conditional_type< 856*38fd1498Szrj _LoserTreeTraits<_ValueType>::_M_use_pointer, 857*38fd1498Szrj _LoserTreePointerUnguarded<__stable, _ValueType, _Compare>, 858*38fd1498Szrj _LoserTreeUnguarded<__stable, _ValueType, _Compare> 859*38fd1498Szrj >::__type> 860*38fd1498Szrj (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp); 861*38fd1498Szrj } 862*38fd1498Szrj }; 863*38fd1498Szrj 864*38fd1498Szrj /** 865*38fd1498Szrj * @brief Switch for k-way merging with __sentinels turned off. 866*38fd1498Szrj */ 867*38fd1498Szrj template<bool __stable, 868*38fd1498Szrj typename _RAIterIterator, 869*38fd1498Szrj typename _RAIter3, 870*38fd1498Szrj typename _DifferenceTp, 871*38fd1498Szrj typename _Compare> 872*38fd1498Szrj struct __multiway_merge_k_variant_sentinel_switch<false, __stable, 873*38fd1498Szrj _RAIterIterator, 874*38fd1498Szrj _RAIter3, _DifferenceTp, 875*38fd1498Szrj _Compare> 876*38fd1498Szrj { 877*38fd1498Szrj _RAIter3 878*38fd1498Szrj operator()(_RAIterIterator __seqs_begin, 879*38fd1498Szrj _RAIterIterator __seqs_end, 880*38fd1498Szrj _RAIter3 __target, 881*38fd1498Szrj const typename std::iterator_traits<typename std::iterator_traits< 882*38fd1498Szrj _RAIterIterator>::value_type::first_type>::value_type& 883*38fd1498Szrj __sentinel, 884*38fd1498Szrj _DifferenceTp __length, _Compare __comp) 885*38fd1498Szrj { 886*38fd1498Szrj typedef typename std::iterator_traits<_RAIterIterator> 887*38fd1498Szrj ::value_type::first_type 888*38fd1498Szrj _RAIter1; 889*38fd1498Szrj typedef typename std::iterator_traits<_RAIter1>::value_type 890*38fd1498Szrj _ValueType; 891*38fd1498Szrj 892*38fd1498Szrj return multiway_merge_loser_tree< 893*38fd1498Szrj typename __gnu_cxx::__conditional_type< 894*38fd1498Szrj _LoserTreeTraits<_ValueType>::_M_use_pointer, 895*38fd1498Szrj _LoserTreePointer<__stable, _ValueType, _Compare>, 896*38fd1498Szrj _LoserTree<__stable, _ValueType, _Compare> 897*38fd1498Szrj >::__type >(__seqs_begin, __seqs_end, __target, __length, __comp); 898*38fd1498Szrj } 899*38fd1498Szrj }; 900*38fd1498Szrj 901*38fd1498Szrj /** @brief Sequential multi-way merging switch. 902*38fd1498Szrj * 903*38fd1498Szrj * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and 904*38fd1498Szrj * runtime settings. 905*38fd1498Szrj * @param __seqs_begin Begin iterator of iterator pair input sequence. 906*38fd1498Szrj * @param __seqs_end End iterator of iterator pair input sequence. 907*38fd1498Szrj * @param __target Begin iterator of output sequence. 908*38fd1498Szrj * @param __comp Comparator. 909*38fd1498Szrj * @param __length Maximum length to merge, possibly larger than the 910*38fd1498Szrj * number of elements available. 911*38fd1498Szrj * @param __sentinel The sequences have __a __sentinel element. 912*38fd1498Szrj * @return End iterator of output sequence. */ 913*38fd1498Szrj template<bool __stable, 914*38fd1498Szrj bool __sentinels, 915*38fd1498Szrj typename _RAIterIterator, 916*38fd1498Szrj typename _RAIter3, 917*38fd1498Szrj typename _DifferenceTp, 918*38fd1498Szrj typename _Compare> 919*38fd1498Szrj _RAIter3 920*38fd1498Szrj __sequential_multiway_merge(_RAIterIterator __seqs_begin, 921*38fd1498Szrj _RAIterIterator __seqs_end, 922*38fd1498Szrj _RAIter3 __target, 923*38fd1498Szrj const typename std::iterator_traits<typename std::iterator_traits< 924*38fd1498Szrj _RAIterIterator>::value_type::first_type>::value_type& 925*38fd1498Szrj __sentinel, 926*38fd1498Szrj _DifferenceTp __length, _Compare __comp) 927*38fd1498Szrj { 928*38fd1498Szrj _GLIBCXX_CALL(__length) 929*38fd1498Szrj 930*38fd1498Szrj typedef _DifferenceTp _DifferenceType; 931*38fd1498Szrj typedef typename std::iterator_traits<_RAIterIterator> 932*38fd1498Szrj ::difference_type _SeqNumber; 933*38fd1498Szrj typedef typename std::iterator_traits<_RAIterIterator> 934*38fd1498Szrj ::value_type::first_type 935*38fd1498Szrj _RAIter1; 936*38fd1498Szrj typedef typename std::iterator_traits<_RAIter1>::value_type 937*38fd1498Szrj _ValueType; 938*38fd1498Szrj 939*38fd1498Szrj #if _GLIBCXX_PARALLEL_ASSERTIONS 940*38fd1498Szrj for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s) 941*38fd1498Szrj { 942*38fd1498Szrj _GLIBCXX_PARALLEL_ASSERT(__is_sorted((*__s).first, 943*38fd1498Szrj (*__s).second, __comp)); 944*38fd1498Szrj } 945*38fd1498Szrj #endif 946*38fd1498Szrj 947*38fd1498Szrj _DifferenceTp __total_length = 0; 948*38fd1498Szrj for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s) 949*38fd1498Szrj __total_length += _GLIBCXX_PARALLEL_LENGTH(*__s); 950*38fd1498Szrj 951*38fd1498Szrj __length = std::min<_DifferenceTp>(__length, __total_length); 952*38fd1498Szrj 953*38fd1498Szrj if(__length == 0) 954*38fd1498Szrj return __target; 955*38fd1498Szrj 956*38fd1498Szrj _RAIter3 __return_target = __target; 957*38fd1498Szrj _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin); 958*38fd1498Szrj 959*38fd1498Szrj switch (__k) 960*38fd1498Szrj { 961*38fd1498Szrj case 0: 962*38fd1498Szrj break; 963*38fd1498Szrj case 1: 964*38fd1498Szrj __return_target = std::copy(__seqs_begin[0].first, 965*38fd1498Szrj __seqs_begin[0].first + __length, 966*38fd1498Szrj __target); 967*38fd1498Szrj __seqs_begin[0].first += __length; 968*38fd1498Szrj break; 969*38fd1498Szrj case 2: 970*38fd1498Szrj __return_target = __merge_advance(__seqs_begin[0].first, 971*38fd1498Szrj __seqs_begin[0].second, 972*38fd1498Szrj __seqs_begin[1].first, 973*38fd1498Szrj __seqs_begin[1].second, 974*38fd1498Szrj __target, __length, __comp); 975*38fd1498Szrj break; 976*38fd1498Szrj case 3: 977*38fd1498Szrj __return_target = __multiway_merge_3_variant_sentinel_switch 978*38fd1498Szrj <__sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare>() 979*38fd1498Szrj (__seqs_begin, __seqs_end, __target, __length, __comp); 980*38fd1498Szrj break; 981*38fd1498Szrj case 4: 982*38fd1498Szrj __return_target = __multiway_merge_4_variant_sentinel_switch 983*38fd1498Szrj <__sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare>() 984*38fd1498Szrj (__seqs_begin, __seqs_end, __target, __length, __comp); 985*38fd1498Szrj break; 986*38fd1498Szrj default: 987*38fd1498Szrj __return_target = __multiway_merge_k_variant_sentinel_switch 988*38fd1498Szrj <__sentinels, __stable, _RAIterIterator, _RAIter3, _DifferenceTp, 989*38fd1498Szrj _Compare>() 990*38fd1498Szrj (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp); 991*38fd1498Szrj break; 992*38fd1498Szrj } 993*38fd1498Szrj #if _GLIBCXX_PARALLEL_ASSERTIONS 994*38fd1498Szrj _GLIBCXX_PARALLEL_ASSERT( 995*38fd1498Szrj __is_sorted(__target, __target + __length, __comp)); 996*38fd1498Szrj #endif 997*38fd1498Szrj 998*38fd1498Szrj return __return_target; 999*38fd1498Szrj } 1000*38fd1498Szrj 1001*38fd1498Szrj /** 1002*38fd1498Szrj * @brief Stable sorting functor. 1003*38fd1498Szrj * 1004*38fd1498Szrj * Used to reduce code instanciation in multiway_merge_sampling_splitting. 1005*38fd1498Szrj */ 1006*38fd1498Szrj template<bool __stable, class _RAIter, class _StrictWeakOrdering> 1007*38fd1498Szrj struct _SamplingSorter 1008*38fd1498Szrj { 1009*38fd1498Szrj void 1010*38fd1498Szrj operator()(_RAIter __first, _RAIter __last, _StrictWeakOrdering __comp) 1011*38fd1498Szrj { __gnu_sequential::stable_sort(__first, __last, __comp); } 1012*38fd1498Szrj }; 1013*38fd1498Szrj 1014*38fd1498Szrj /** 1015*38fd1498Szrj * @brief Non-__stable sorting functor. 1016*38fd1498Szrj * 1017*38fd1498Szrj * Used to reduce code instantiation in multiway_merge_sampling_splitting. 1018*38fd1498Szrj */ 1019*38fd1498Szrj template<class _RAIter, class _StrictWeakOrdering> 1020*38fd1498Szrj struct _SamplingSorter<false, _RAIter, _StrictWeakOrdering> 1021*38fd1498Szrj { 1022*38fd1498Szrj void 1023*38fd1498Szrj operator()(_RAIter __first, _RAIter __last, _StrictWeakOrdering __comp) 1024*38fd1498Szrj { __gnu_sequential::sort(__first, __last, __comp); } 1025*38fd1498Szrj }; 1026*38fd1498Szrj 1027*38fd1498Szrj /** 1028*38fd1498Szrj * @brief Sampling based splitting for parallel multiway-merge routine. 1029*38fd1498Szrj */ 1030*38fd1498Szrj template<bool __stable, 1031*38fd1498Szrj typename _RAIterIterator, 1032*38fd1498Szrj typename _Compare, 1033*38fd1498Szrj typename _DifferenceType> 1034*38fd1498Szrj void 1035*38fd1498Szrj multiway_merge_sampling_splitting(_RAIterIterator __seqs_begin, 1036*38fd1498Szrj _RAIterIterator __seqs_end, 1037*38fd1498Szrj _DifferenceType __length, 1038*38fd1498Szrj _DifferenceType __total_length, 1039*38fd1498Szrj _Compare __comp, 1040*38fd1498Szrj std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces) 1041*38fd1498Szrj { 1042*38fd1498Szrj typedef typename std::iterator_traits<_RAIterIterator> 1043*38fd1498Szrj ::difference_type _SeqNumber; 1044*38fd1498Szrj typedef typename std::iterator_traits<_RAIterIterator> 1045*38fd1498Szrj ::value_type::first_type 1046*38fd1498Szrj _RAIter1; 1047*38fd1498Szrj typedef typename std::iterator_traits<_RAIter1>::value_type 1048*38fd1498Szrj _ValueType; 1049*38fd1498Szrj 1050*38fd1498Szrj // __k sequences. 1051*38fd1498Szrj const _SeqNumber __k 1052*38fd1498Szrj = static_cast<_SeqNumber>(__seqs_end - __seqs_begin); 1053*38fd1498Szrj 1054*38fd1498Szrj const _ThreadIndex __num_threads = omp_get_num_threads(); 1055*38fd1498Szrj 1056*38fd1498Szrj const _DifferenceType __num_samples = 1057*38fd1498Szrj __gnu_parallel::_Settings::get().merge_oversampling * __num_threads; 1058*38fd1498Szrj 1059*38fd1498Szrj _ValueType* __samples = static_cast<_ValueType*> 1060*38fd1498Szrj (::operator new(sizeof(_ValueType) * __k * __num_samples)); 1061*38fd1498Szrj // Sample. 1062*38fd1498Szrj for (_SeqNumber __s = 0; __s < __k; ++__s) 1063*38fd1498Szrj for (_DifferenceType __i = 0; __i < __num_samples; ++__i) 1064*38fd1498Szrj { 1065*38fd1498Szrj _DifferenceType sample_index = static_cast<_DifferenceType> 1066*38fd1498Szrj (_GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__s]) 1067*38fd1498Szrj * (double(__i + 1) / (__num_samples + 1)) 1068*38fd1498Szrj * (double(__length) / __total_length)); 1069*38fd1498Szrj new(&(__samples[__s * __num_samples + __i])) 1070*38fd1498Szrj _ValueType(__seqs_begin[__s].first[sample_index]); 1071*38fd1498Szrj } 1072*38fd1498Szrj 1073*38fd1498Szrj // Sort stable or non-stable, depending on value of template parameter 1074*38fd1498Szrj // "__stable". 1075*38fd1498Szrj _SamplingSorter<__stable, _ValueType*, _Compare>() 1076*38fd1498Szrj (__samples, __samples + (__num_samples * __k), __comp); 1077*38fd1498Szrj 1078*38fd1498Szrj for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab) 1079*38fd1498Szrj // For each slab / processor. 1080*38fd1498Szrj for (_SeqNumber __seq = 0; __seq < __k; ++__seq) 1081*38fd1498Szrj { 1082*38fd1498Szrj // For each sequence. 1083*38fd1498Szrj if (__slab > 0) 1084*38fd1498Szrj __pieces[__slab][__seq].first = std::upper_bound 1085*38fd1498Szrj (__seqs_begin[__seq].first, __seqs_begin[__seq].second, 1086*38fd1498Szrj __samples[__num_samples * __k * __slab / __num_threads], 1087*38fd1498Szrj __comp) 1088*38fd1498Szrj - __seqs_begin[__seq].first; 1089*38fd1498Szrj else 1090*38fd1498Szrj // Absolute beginning. 1091*38fd1498Szrj __pieces[__slab][__seq].first = 0; 1092*38fd1498Szrj if ((__slab + 1) < __num_threads) 1093*38fd1498Szrj __pieces[__slab][__seq].second = std::upper_bound 1094*38fd1498Szrj (__seqs_begin[__seq].first, __seqs_begin[__seq].second, 1095*38fd1498Szrj __samples[__num_samples * __k * (__slab + 1) / __num_threads], 1096*38fd1498Szrj __comp) 1097*38fd1498Szrj - __seqs_begin[__seq].first; 1098*38fd1498Szrj else 1099*38fd1498Szrj // Absolute end. 1100*38fd1498Szrj __pieces[__slab][__seq].second = 1101*38fd1498Szrj _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]); 1102*38fd1498Szrj } 1103*38fd1498Szrj 1104*38fd1498Szrj for (_SeqNumber __s = 0; __s < __k; ++__s) 1105*38fd1498Szrj for (_DifferenceType __i = 0; __i < __num_samples; ++__i) 1106*38fd1498Szrj __samples[__s * __num_samples + __i].~_ValueType(); 1107*38fd1498Szrj ::operator delete(__samples); 1108*38fd1498Szrj } 1109*38fd1498Szrj 1110*38fd1498Szrj /** 1111*38fd1498Szrj * @brief Exact splitting for parallel multiway-merge routine. 1112*38fd1498Szrj * 1113*38fd1498Szrj * None of the passed sequences may be empty. 1114*38fd1498Szrj */ 1115*38fd1498Szrj template<bool __stable, 1116*38fd1498Szrj typename _RAIterIterator, 1117*38fd1498Szrj typename _Compare, 1118*38fd1498Szrj typename _DifferenceType> 1119*38fd1498Szrj void 1120*38fd1498Szrj multiway_merge_exact_splitting(_RAIterIterator __seqs_begin, 1121*38fd1498Szrj _RAIterIterator __seqs_end, 1122*38fd1498Szrj _DifferenceType __length, 1123*38fd1498Szrj _DifferenceType __total_length, 1124*38fd1498Szrj _Compare __comp, 1125*38fd1498Szrj std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces) 1126*38fd1498Szrj { 1127*38fd1498Szrj typedef typename std::iterator_traits<_RAIterIterator> 1128*38fd1498Szrj ::difference_type _SeqNumber; 1129*38fd1498Szrj typedef typename std::iterator_traits<_RAIterIterator> 1130*38fd1498Szrj ::value_type::first_type 1131*38fd1498Szrj _RAIter1; 1132*38fd1498Szrj 1133*38fd1498Szrj const bool __tight = (__total_length == __length); 1134*38fd1498Szrj 1135*38fd1498Szrj // __k sequences. 1136*38fd1498Szrj const _SeqNumber __k = __seqs_end - __seqs_begin; 1137*38fd1498Szrj 1138*38fd1498Szrj const _ThreadIndex __num_threads = omp_get_num_threads(); 1139*38fd1498Szrj 1140*38fd1498Szrj // (Settings::multiway_merge_splitting 1141*38fd1498Szrj // == __gnu_parallel::_Settings::EXACT). 1142*38fd1498Szrj std::vector<_RAIter1>* __offsets = 1143*38fd1498Szrj new std::vector<_RAIter1>[__num_threads]; 1144*38fd1498Szrj std::vector<std::pair<_RAIter1, _RAIter1> > __se(__k); 1145*38fd1498Szrj 1146*38fd1498Szrj copy(__seqs_begin, __seqs_end, __se.begin()); 1147*38fd1498Szrj 1148*38fd1498Szrj _DifferenceType* __borders = 1149*38fd1498Szrj new _DifferenceType[__num_threads + 1]; 1150*38fd1498Szrj __equally_split(__length, __num_threads, __borders); 1151*38fd1498Szrj 1152*38fd1498Szrj for (_ThreadIndex __s = 0; __s < (__num_threads - 1); ++__s) 1153*38fd1498Szrj { 1154*38fd1498Szrj __offsets[__s].resize(__k); 1155*38fd1498Szrj multiseq_partition(__se.begin(), __se.end(), __borders[__s + 1], 1156*38fd1498Szrj __offsets[__s].begin(), __comp); 1157*38fd1498Szrj 1158*38fd1498Szrj // Last one also needed and available. 1159*38fd1498Szrj if (!__tight) 1160*38fd1498Szrj { 1161*38fd1498Szrj __offsets[__num_threads - 1].resize(__k); 1162*38fd1498Szrj multiseq_partition(__se.begin(), __se.end(), 1163*38fd1498Szrj _DifferenceType(__length), 1164*38fd1498Szrj __offsets[__num_threads - 1].begin(), 1165*38fd1498Szrj __comp); 1166*38fd1498Szrj } 1167*38fd1498Szrj } 1168*38fd1498Szrj delete[] __borders; 1169*38fd1498Szrj 1170*38fd1498Szrj for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab) 1171*38fd1498Szrj { 1172*38fd1498Szrj // For each slab / processor. 1173*38fd1498Szrj for (_SeqNumber __seq = 0; __seq < __k; ++__seq) 1174*38fd1498Szrj { 1175*38fd1498Szrj // For each sequence. 1176*38fd1498Szrj if (__slab == 0) 1177*38fd1498Szrj { 1178*38fd1498Szrj // Absolute beginning. 1179*38fd1498Szrj __pieces[__slab][__seq].first = 0; 1180*38fd1498Szrj } 1181*38fd1498Szrj else 1182*38fd1498Szrj __pieces[__slab][__seq].first = 1183*38fd1498Szrj __pieces[__slab - 1][__seq].second; 1184*38fd1498Szrj if (!__tight || __slab < (__num_threads - 1)) 1185*38fd1498Szrj __pieces[__slab][__seq].second = 1186*38fd1498Szrj __offsets[__slab][__seq] - __seqs_begin[__seq].first; 1187*38fd1498Szrj else 1188*38fd1498Szrj { 1189*38fd1498Szrj // __slab == __num_threads - 1 1190*38fd1498Szrj __pieces[__slab][__seq].second = 1191*38fd1498Szrj _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]); 1192*38fd1498Szrj } 1193*38fd1498Szrj } 1194*38fd1498Szrj } 1195*38fd1498Szrj delete[] __offsets; 1196*38fd1498Szrj } 1197*38fd1498Szrj 1198*38fd1498Szrj /** @brief Parallel multi-way merge routine. 1199*38fd1498Szrj * 1200*38fd1498Szrj * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor 1201*38fd1498Szrj * and runtime settings. 1202*38fd1498Szrj * 1203*38fd1498Szrj * Must not be called if the number of sequences is 1. 1204*38fd1498Szrj * 1205*38fd1498Szrj * @tparam _Splitter functor to split input (either __exact or sampling based) 1206*38fd1498Szrj * @tparam __stable Stable merging incurs a performance penalty. 1207*38fd1498Szrj * @tparam __sentinel Ignored. 1208*38fd1498Szrj * 1209*38fd1498Szrj * @param __seqs_begin Begin iterator of iterator pair input sequence. 1210*38fd1498Szrj * @param __seqs_end End iterator of iterator pair input sequence. 1211*38fd1498Szrj * @param __target Begin iterator of output sequence. 1212*38fd1498Szrj * @param __comp Comparator. 1213*38fd1498Szrj * @param __length Maximum length to merge, possibly larger than the 1214*38fd1498Szrj * number of elements available. 1215*38fd1498Szrj * @return End iterator of output sequence. 1216*38fd1498Szrj */ 1217*38fd1498Szrj template<bool __stable, 1218*38fd1498Szrj bool __sentinels, 1219*38fd1498Szrj typename _RAIterIterator, 1220*38fd1498Szrj typename _RAIter3, 1221*38fd1498Szrj typename _DifferenceTp, 1222*38fd1498Szrj typename _Splitter, 1223*38fd1498Szrj typename _Compare> 1224*38fd1498Szrj _RAIter3 1225*38fd1498Szrj parallel_multiway_merge(_RAIterIterator __seqs_begin, 1226*38fd1498Szrj _RAIterIterator __seqs_end, 1227*38fd1498Szrj _RAIter3 __target, 1228*38fd1498Szrj _Splitter __splitter, 1229*38fd1498Szrj _DifferenceTp __length, 1230*38fd1498Szrj _Compare __comp, 1231*38fd1498Szrj _ThreadIndex __num_threads) 1232*38fd1498Szrj { 1233*38fd1498Szrj #if _GLIBCXX_PARALLEL_ASSERTIONS 1234*38fd1498Szrj _GLIBCXX_PARALLEL_ASSERT(__seqs_end - __seqs_begin > 1); 1235*38fd1498Szrj #endif 1236*38fd1498Szrj 1237*38fd1498Szrj _GLIBCXX_CALL(__length) 1238*38fd1498Szrj 1239*38fd1498Szrj typedef _DifferenceTp _DifferenceType; 1240*38fd1498Szrj typedef typename std::iterator_traits<_RAIterIterator> 1241*38fd1498Szrj ::difference_type _SeqNumber; 1242*38fd1498Szrj typedef typename std::iterator_traits<_RAIterIterator> 1243*38fd1498Szrj ::value_type::first_type 1244*38fd1498Szrj _RAIter1; 1245*38fd1498Szrj typedef typename 1246*38fd1498Szrj std::iterator_traits<_RAIter1>::value_type _ValueType; 1247*38fd1498Szrj 1248*38fd1498Szrj // Leave only non-empty sequences. 1249*38fd1498Szrj typedef std::pair<_RAIter1, _RAIter1> seq_type; 1250*38fd1498Szrj seq_type* __ne_seqs = new seq_type[__seqs_end - __seqs_begin]; 1251*38fd1498Szrj _SeqNumber __k = 0; 1252*38fd1498Szrj _DifferenceType __total_length = 0; 1253*38fd1498Szrj for (_RAIterIterator __raii = __seqs_begin; 1254*38fd1498Szrj __raii != __seqs_end; ++__raii) 1255*38fd1498Szrj { 1256*38fd1498Szrj _DifferenceTp __seq_length = _GLIBCXX_PARALLEL_LENGTH(*__raii); 1257*38fd1498Szrj if(__seq_length > 0) 1258*38fd1498Szrj { 1259*38fd1498Szrj __total_length += __seq_length; 1260*38fd1498Szrj __ne_seqs[__k++] = *__raii; 1261*38fd1498Szrj } 1262*38fd1498Szrj } 1263*38fd1498Szrj 1264*38fd1498Szrj _GLIBCXX_CALL(__total_length) 1265*38fd1498Szrj 1266*38fd1498Szrj __length = std::min<_DifferenceTp>(__length, __total_length); 1267*38fd1498Szrj 1268*38fd1498Szrj if (__total_length == 0 || __k == 0) 1269*38fd1498Szrj { 1270*38fd1498Szrj delete[] __ne_seqs; 1271*38fd1498Szrj return __target; 1272*38fd1498Szrj } 1273*38fd1498Szrj 1274*38fd1498Szrj std::vector<std::pair<_DifferenceType, _DifferenceType> >* __pieces; 1275*38fd1498Szrj 1276*38fd1498Szrj __num_threads = static_cast<_ThreadIndex> 1277*38fd1498Szrj (std::min<_DifferenceType>(__num_threads, __total_length)); 1278*38fd1498Szrj 1279*38fd1498Szrj # pragma omp parallel num_threads (__num_threads) 1280*38fd1498Szrj { 1281*38fd1498Szrj # pragma omp single 1282*38fd1498Szrj { 1283*38fd1498Szrj __num_threads = omp_get_num_threads(); 1284*38fd1498Szrj // Thread __t will have to merge pieces[__iam][0..__k - 1] 1285*38fd1498Szrj __pieces = new std::vector< 1286*38fd1498Szrj std::pair<_DifferenceType, _DifferenceType> >[__num_threads]; 1287*38fd1498Szrj for (_ThreadIndex __s = 0; __s < __num_threads; ++__s) 1288*38fd1498Szrj __pieces[__s].resize(__k); 1289*38fd1498Szrj 1290*38fd1498Szrj _DifferenceType __num_samples = 1291*38fd1498Szrj __gnu_parallel::_Settings::get().merge_oversampling 1292*38fd1498Szrj * __num_threads; 1293*38fd1498Szrj 1294*38fd1498Szrj __splitter(__ne_seqs, __ne_seqs + __k, __length, __total_length, 1295*38fd1498Szrj __comp, __pieces); 1296*38fd1498Szrj } //single 1297*38fd1498Szrj 1298*38fd1498Szrj _ThreadIndex __iam = omp_get_thread_num(); 1299*38fd1498Szrj 1300*38fd1498Szrj _DifferenceType __target_position = 0; 1301*38fd1498Szrj 1302*38fd1498Szrj for (_SeqNumber __c = 0; __c < __k; ++__c) 1303*38fd1498Szrj __target_position += __pieces[__iam][__c].first; 1304*38fd1498Szrj 1305*38fd1498Szrj seq_type* __chunks = new seq_type[__k]; 1306*38fd1498Szrj 1307*38fd1498Szrj for (_SeqNumber __s = 0; __s < __k; ++__s) 1308*38fd1498Szrj __chunks[__s] = std::make_pair(__ne_seqs[__s].first 1309*38fd1498Szrj + __pieces[__iam][__s].first, 1310*38fd1498Szrj __ne_seqs[__s].first 1311*38fd1498Szrj + __pieces[__iam][__s].second); 1312*38fd1498Szrj 1313*38fd1498Szrj if(__length > __target_position) 1314*38fd1498Szrj __sequential_multiway_merge<__stable, __sentinels> 1315*38fd1498Szrj (__chunks, __chunks + __k, __target + __target_position, 1316*38fd1498Szrj *(__seqs_begin->second), __length - __target_position, __comp); 1317*38fd1498Szrj 1318*38fd1498Szrj delete[] __chunks; 1319*38fd1498Szrj } // parallel 1320*38fd1498Szrj 1321*38fd1498Szrj #if _GLIBCXX_PARALLEL_ASSERTIONS 1322*38fd1498Szrj _GLIBCXX_PARALLEL_ASSERT( 1323*38fd1498Szrj __is_sorted(__target, __target + __length, __comp)); 1324*38fd1498Szrj #endif 1325*38fd1498Szrj 1326*38fd1498Szrj __k = 0; 1327*38fd1498Szrj // Update ends of sequences. 1328*38fd1498Szrj for (_RAIterIterator __raii = __seqs_begin; 1329*38fd1498Szrj __raii != __seqs_end; ++__raii) 1330*38fd1498Szrj { 1331*38fd1498Szrj _DifferenceTp __length = _GLIBCXX_PARALLEL_LENGTH(*__raii); 1332*38fd1498Szrj if(__length > 0) 1333*38fd1498Szrj (*__raii).first += __pieces[__num_threads - 1][__k++].second; 1334*38fd1498Szrj } 1335*38fd1498Szrj 1336*38fd1498Szrj delete[] __pieces; 1337*38fd1498Szrj delete[] __ne_seqs; 1338*38fd1498Szrj 1339*38fd1498Szrj return __target + __length; 1340*38fd1498Szrj } 1341*38fd1498Szrj 1342*38fd1498Szrj /** 1343*38fd1498Szrj * @brief Multiway Merge Frontend. 1344*38fd1498Szrj * 1345*38fd1498Szrj * Merge the sequences specified by seqs_begin and __seqs_end into 1346*38fd1498Szrj * __target. __seqs_begin and __seqs_end must point to a sequence of 1347*38fd1498Szrj * pairs. These pairs must contain an iterator to the beginning 1348*38fd1498Szrj * of a sequence in their first entry and an iterator the _M_end of 1349*38fd1498Szrj * the same sequence in their second entry. 1350*38fd1498Szrj * 1351*38fd1498Szrj * Ties are broken arbitrarily. See stable_multiway_merge for a variant 1352*38fd1498Szrj * that breaks ties by sequence number but is slower. 1353*38fd1498Szrj * 1354*38fd1498Szrj * The first entries of the pairs (i.e. the begin iterators) will be moved 1355*38fd1498Szrj * forward. 1356*38fd1498Szrj * 1357*38fd1498Szrj * The output sequence has to provide enough space for all elements 1358*38fd1498Szrj * that are written to it. 1359*38fd1498Szrj * 1360*38fd1498Szrj * This function will merge the input sequences: 1361*38fd1498Szrj * 1362*38fd1498Szrj * - not stable 1363*38fd1498Szrj * - parallel, depending on the input size and Settings 1364*38fd1498Szrj * - using sampling for splitting 1365*38fd1498Szrj * - not using sentinels 1366*38fd1498Szrj * 1367*38fd1498Szrj * Example: 1368*38fd1498Szrj * 1369*38fd1498Szrj * <pre> 1370*38fd1498Szrj * int sequences[10][10]; 1371*38fd1498Szrj * for (int __i = 0; __i < 10; ++__i) 1372*38fd1498Szrj * for (int __j = 0; __i < 10; ++__j) 1373*38fd1498Szrj * sequences[__i][__j] = __j; 1374*38fd1498Szrj * 1375*38fd1498Szrj * int __out[33]; 1376*38fd1498Szrj * std::vector<std::pair<int*> > seqs; 1377*38fd1498Szrj * for (int __i = 0; __i < 10; ++__i) 1378*38fd1498Szrj * { seqs.push(std::make_pair<int*>(sequences[__i], 1379*38fd1498Szrj * sequences[__i] + 10)) } 1380*38fd1498Szrj * 1381*38fd1498Szrj * multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33); 1382*38fd1498Szrj * </pre> 1383*38fd1498Szrj * 1384*38fd1498Szrj * @see stable_multiway_merge 1385*38fd1498Szrj * 1386*38fd1498Szrj * @pre All input sequences must be sorted. 1387*38fd1498Szrj * @pre Target must provide enough space to merge out length elements or 1388*38fd1498Szrj * the number of elements in all sequences, whichever is smaller. 1389*38fd1498Szrj * 1390*38fd1498Szrj * @post [__target, return __value) contains merged __elements from the 1391*38fd1498Szrj * input sequences. 1392*38fd1498Szrj * @post return __value - __target = min(__length, number of elements in all 1393*38fd1498Szrj * sequences). 1394*38fd1498Szrj * 1395*38fd1498Szrj * @tparam _RAIterPairIterator iterator over sequence 1396*38fd1498Szrj * of pairs of iterators 1397*38fd1498Szrj * @tparam _RAIterOut iterator over target sequence 1398*38fd1498Szrj * @tparam _DifferenceTp difference type for the sequence 1399*38fd1498Szrj * @tparam _Compare strict weak ordering type to compare elements 1400*38fd1498Szrj * in sequences 1401*38fd1498Szrj * 1402*38fd1498Szrj * @param __seqs_begin __begin of sequence __sequence 1403*38fd1498Szrj * @param __seqs_end _M_end of sequence __sequence 1404*38fd1498Szrj * @param __target target sequence to merge to. 1405*38fd1498Szrj * @param __comp strict weak ordering to use for element comparison. 1406*38fd1498Szrj * @param __length Maximum length to merge, possibly larger than the 1407*38fd1498Szrj * number of elements available. 1408*38fd1498Szrj * 1409*38fd1498Szrj * @return _M_end iterator of output sequence 1410*38fd1498Szrj */ 1411*38fd1498Szrj // multiway_merge 1412*38fd1498Szrj // public interface 1413*38fd1498Szrj template<typename _RAIterPairIterator, 1414*38fd1498Szrj typename _RAIterOut, 1415*38fd1498Szrj typename _DifferenceTp, 1416*38fd1498Szrj typename _Compare> 1417*38fd1498Szrj _RAIterOut 1418*38fd1498Szrj multiway_merge(_RAIterPairIterator __seqs_begin, 1419*38fd1498Szrj _RAIterPairIterator __seqs_end, 1420*38fd1498Szrj _RAIterOut __target, 1421*38fd1498Szrj _DifferenceTp __length, _Compare __comp, 1422*38fd1498Szrj __gnu_parallel::sequential_tag) 1423*38fd1498Szrj { 1424*38fd1498Szrj typedef _DifferenceTp _DifferenceType; 1425*38fd1498Szrj _GLIBCXX_CALL(__seqs_end - __seqs_begin) 1426*38fd1498Szrj 1427*38fd1498Szrj // catch special case: no sequences 1428*38fd1498Szrj if (__seqs_begin == __seqs_end) 1429*38fd1498Szrj return __target; 1430*38fd1498Szrj 1431*38fd1498Szrj // Execute multiway merge *sequentially*. 1432*38fd1498Szrj return __sequential_multiway_merge 1433*38fd1498Szrj </* __stable = */ false, /* __sentinels = */ false> 1434*38fd1498Szrj (__seqs_begin, __seqs_end, __target, 1435*38fd1498Szrj *(__seqs_begin->second), __length, __comp); 1436*38fd1498Szrj } 1437*38fd1498Szrj 1438*38fd1498Szrj // public interface 1439*38fd1498Szrj template<typename _RAIterPairIterator, 1440*38fd1498Szrj typename _RAIterOut, 1441*38fd1498Szrj typename _DifferenceTp, 1442*38fd1498Szrj typename _Compare> 1443*38fd1498Szrj _RAIterOut 1444*38fd1498Szrj multiway_merge(_RAIterPairIterator __seqs_begin, 1445*38fd1498Szrj _RAIterPairIterator __seqs_end, 1446*38fd1498Szrj _RAIterOut __target, 1447*38fd1498Szrj _DifferenceTp __length, _Compare __comp, 1448*38fd1498Szrj __gnu_parallel::exact_tag __tag) 1449*38fd1498Szrj { 1450*38fd1498Szrj typedef _DifferenceTp _DifferenceType; 1451*38fd1498Szrj _GLIBCXX_CALL(__seqs_end - __seqs_begin) 1452*38fd1498Szrj 1453*38fd1498Szrj // catch special case: no sequences 1454*38fd1498Szrj if (__seqs_begin == __seqs_end) 1455*38fd1498Szrj return __target; 1456*38fd1498Szrj 1457*38fd1498Szrj // Execute merge; maybe parallel, depending on the number of merged 1458*38fd1498Szrj // elements and the number of sequences and global thresholds in 1459*38fd1498Szrj // Settings. 1460*38fd1498Szrj if ((__seqs_end - __seqs_begin > 1) 1461*38fd1498Szrj && _GLIBCXX_PARALLEL_CONDITION( 1462*38fd1498Szrj ((__seqs_end - __seqs_begin) >= 1463*38fd1498Szrj __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 1464*38fd1498Szrj && ((_SequenceIndex)__length >= 1465*38fd1498Szrj __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 1466*38fd1498Szrj return parallel_multiway_merge 1467*38fd1498Szrj </* __stable = */ false, /* __sentinels = */ false> 1468*38fd1498Szrj (__seqs_begin, __seqs_end, __target, 1469*38fd1498Szrj multiway_merge_exact_splitting</* __stable = */ false, 1470*38fd1498Szrj typename std::iterator_traits<_RAIterPairIterator> 1471*38fd1498Szrj ::value_type*, _Compare, _DifferenceTp>, 1472*38fd1498Szrj static_cast<_DifferenceType>(__length), __comp, 1473*38fd1498Szrj __tag.__get_num_threads()); 1474*38fd1498Szrj else 1475*38fd1498Szrj return __sequential_multiway_merge 1476*38fd1498Szrj </* __stable = */ false, /* __sentinels = */ false> 1477*38fd1498Szrj (__seqs_begin, __seqs_end, __target, 1478*38fd1498Szrj *(__seqs_begin->second), __length, __comp); 1479*38fd1498Szrj } 1480*38fd1498Szrj 1481*38fd1498Szrj // public interface 1482*38fd1498Szrj template<typename _RAIterPairIterator, 1483*38fd1498Szrj typename _RAIterOut, 1484*38fd1498Szrj typename _DifferenceTp, 1485*38fd1498Szrj typename _Compare> 1486*38fd1498Szrj _RAIterOut 1487*38fd1498Szrj multiway_merge(_RAIterPairIterator __seqs_begin, 1488*38fd1498Szrj _RAIterPairIterator __seqs_end, 1489*38fd1498Szrj _RAIterOut __target, 1490*38fd1498Szrj _DifferenceTp __length, _Compare __comp, 1491*38fd1498Szrj __gnu_parallel::sampling_tag __tag) 1492*38fd1498Szrj { 1493*38fd1498Szrj typedef _DifferenceTp _DifferenceType; 1494*38fd1498Szrj _GLIBCXX_CALL(__seqs_end - __seqs_begin) 1495*38fd1498Szrj 1496*38fd1498Szrj // catch special case: no sequences 1497*38fd1498Szrj if (__seqs_begin == __seqs_end) 1498*38fd1498Szrj return __target; 1499*38fd1498Szrj 1500*38fd1498Szrj // Execute merge; maybe parallel, depending on the number of merged 1501*38fd1498Szrj // elements and the number of sequences and global thresholds in 1502*38fd1498Szrj // Settings. 1503*38fd1498Szrj if ((__seqs_end - __seqs_begin > 1) 1504*38fd1498Szrj && _GLIBCXX_PARALLEL_CONDITION( 1505*38fd1498Szrj ((__seqs_end - __seqs_begin) >= 1506*38fd1498Szrj __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 1507*38fd1498Szrj && ((_SequenceIndex)__length >= 1508*38fd1498Szrj __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 1509*38fd1498Szrj return parallel_multiway_merge 1510*38fd1498Szrj </* __stable = */ false, /* __sentinels = */ false> 1511*38fd1498Szrj (__seqs_begin, __seqs_end, __target, 1512*38fd1498Szrj multiway_merge_exact_splitting</* __stable = */ false, 1513*38fd1498Szrj typename std::iterator_traits<_RAIterPairIterator> 1514*38fd1498Szrj ::value_type*, _Compare, _DifferenceTp>, 1515*38fd1498Szrj static_cast<_DifferenceType>(__length), __comp, 1516*38fd1498Szrj __tag.__get_num_threads()); 1517*38fd1498Szrj else 1518*38fd1498Szrj return __sequential_multiway_merge 1519*38fd1498Szrj </* __stable = */ false, /* __sentinels = */ false> 1520*38fd1498Szrj (__seqs_begin, __seqs_end, __target, 1521*38fd1498Szrj *(__seqs_begin->second), __length, __comp); 1522*38fd1498Szrj } 1523*38fd1498Szrj 1524*38fd1498Szrj // public interface 1525*38fd1498Szrj template<typename _RAIterPairIterator, 1526*38fd1498Szrj typename _RAIterOut, 1527*38fd1498Szrj typename _DifferenceTp, 1528*38fd1498Szrj typename _Compare> 1529*38fd1498Szrj _RAIterOut 1530*38fd1498Szrj multiway_merge(_RAIterPairIterator __seqs_begin, 1531*38fd1498Szrj _RAIterPairIterator __seqs_end, 1532*38fd1498Szrj _RAIterOut __target, 1533*38fd1498Szrj _DifferenceTp __length, _Compare __comp, 1534*38fd1498Szrj parallel_tag __tag = parallel_tag(0)) 1535*38fd1498Szrj { return multiway_merge(__seqs_begin, __seqs_end, __target, __length, 1536*38fd1498Szrj __comp, exact_tag(__tag.__get_num_threads())); } 1537*38fd1498Szrj 1538*38fd1498Szrj // public interface 1539*38fd1498Szrj template<typename _RAIterPairIterator, 1540*38fd1498Szrj typename _RAIterOut, 1541*38fd1498Szrj typename _DifferenceTp, 1542*38fd1498Szrj typename _Compare> 1543*38fd1498Szrj _RAIterOut 1544*38fd1498Szrj multiway_merge(_RAIterPairIterator __seqs_begin, 1545*38fd1498Szrj _RAIterPairIterator __seqs_end, 1546*38fd1498Szrj _RAIterOut __target, 1547*38fd1498Szrj _DifferenceTp __length, _Compare __comp, 1548*38fd1498Szrj default_parallel_tag __tag) 1549*38fd1498Szrj { return multiway_merge(__seqs_begin, __seqs_end, __target, __length, 1550*38fd1498Szrj __comp, exact_tag(__tag.__get_num_threads())); } 1551*38fd1498Szrj 1552*38fd1498Szrj // stable_multiway_merge 1553*38fd1498Szrj // public interface 1554*38fd1498Szrj template<typename _RAIterPairIterator, 1555*38fd1498Szrj typename _RAIterOut, 1556*38fd1498Szrj typename _DifferenceTp, 1557*38fd1498Szrj typename _Compare> 1558*38fd1498Szrj _RAIterOut 1559*38fd1498Szrj stable_multiway_merge(_RAIterPairIterator __seqs_begin, 1560*38fd1498Szrj _RAIterPairIterator __seqs_end, 1561*38fd1498Szrj _RAIterOut __target, 1562*38fd1498Szrj _DifferenceTp __length, _Compare __comp, 1563*38fd1498Szrj __gnu_parallel::sequential_tag) 1564*38fd1498Szrj { 1565*38fd1498Szrj typedef _DifferenceTp _DifferenceType; 1566*38fd1498Szrj _GLIBCXX_CALL(__seqs_end - __seqs_begin) 1567*38fd1498Szrj 1568*38fd1498Szrj // catch special case: no sequences 1569*38fd1498Szrj if (__seqs_begin == __seqs_end) 1570*38fd1498Szrj return __target; 1571*38fd1498Szrj 1572*38fd1498Szrj // Execute multiway merge *sequentially*. 1573*38fd1498Szrj return __sequential_multiway_merge 1574*38fd1498Szrj </* __stable = */ true, /* __sentinels = */ false> 1575*38fd1498Szrj (__seqs_begin, __seqs_end, __target, 1576*38fd1498Szrj *(__seqs_begin->second), __length, __comp); 1577*38fd1498Szrj } 1578*38fd1498Szrj 1579*38fd1498Szrj // public interface 1580*38fd1498Szrj template<typename _RAIterPairIterator, 1581*38fd1498Szrj typename _RAIterOut, 1582*38fd1498Szrj typename _DifferenceTp, 1583*38fd1498Szrj typename _Compare> 1584*38fd1498Szrj _RAIterOut 1585*38fd1498Szrj stable_multiway_merge(_RAIterPairIterator __seqs_begin, 1586*38fd1498Szrj _RAIterPairIterator __seqs_end, 1587*38fd1498Szrj _RAIterOut __target, 1588*38fd1498Szrj _DifferenceTp __length, _Compare __comp, 1589*38fd1498Szrj __gnu_parallel::exact_tag __tag) 1590*38fd1498Szrj { 1591*38fd1498Szrj typedef _DifferenceTp _DifferenceType; 1592*38fd1498Szrj _GLIBCXX_CALL(__seqs_end - __seqs_begin) 1593*38fd1498Szrj 1594*38fd1498Szrj // catch special case: no sequences 1595*38fd1498Szrj if (__seqs_begin == __seqs_end) 1596*38fd1498Szrj return __target; 1597*38fd1498Szrj 1598*38fd1498Szrj // Execute merge; maybe parallel, depending on the number of merged 1599*38fd1498Szrj // elements and the number of sequences and global thresholds in 1600*38fd1498Szrj // Settings. 1601*38fd1498Szrj if ((__seqs_end - __seqs_begin > 1) 1602*38fd1498Szrj && _GLIBCXX_PARALLEL_CONDITION( 1603*38fd1498Szrj ((__seqs_end - __seqs_begin) >= 1604*38fd1498Szrj __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 1605*38fd1498Szrj && ((_SequenceIndex)__length >= 1606*38fd1498Szrj __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 1607*38fd1498Szrj return parallel_multiway_merge 1608*38fd1498Szrj </* __stable = */ true, /* __sentinels = */ false> 1609*38fd1498Szrj (__seqs_begin, __seqs_end, __target, 1610*38fd1498Szrj multiway_merge_exact_splitting</* __stable = */ true, 1611*38fd1498Szrj typename std::iterator_traits<_RAIterPairIterator> 1612*38fd1498Szrj ::value_type*, _Compare, _DifferenceTp>, 1613*38fd1498Szrj static_cast<_DifferenceType>(__length), __comp, 1614*38fd1498Szrj __tag.__get_num_threads()); 1615*38fd1498Szrj else 1616*38fd1498Szrj return __sequential_multiway_merge 1617*38fd1498Szrj </* __stable = */ true, /* __sentinels = */ false> 1618*38fd1498Szrj (__seqs_begin, __seqs_end, __target, 1619*38fd1498Szrj *(__seqs_begin->second), __length, __comp); 1620*38fd1498Szrj } 1621*38fd1498Szrj 1622*38fd1498Szrj // public interface 1623*38fd1498Szrj template<typename _RAIterPairIterator, 1624*38fd1498Szrj typename _RAIterOut, 1625*38fd1498Szrj typename _DifferenceTp, 1626*38fd1498Szrj typename _Compare> 1627*38fd1498Szrj _RAIterOut 1628*38fd1498Szrj stable_multiway_merge(_RAIterPairIterator __seqs_begin, 1629*38fd1498Szrj _RAIterPairIterator __seqs_end, 1630*38fd1498Szrj _RAIterOut __target, 1631*38fd1498Szrj _DifferenceTp __length, _Compare __comp, 1632*38fd1498Szrj sampling_tag __tag) 1633*38fd1498Szrj { 1634*38fd1498Szrj typedef _DifferenceTp _DifferenceType; 1635*38fd1498Szrj _GLIBCXX_CALL(__seqs_end - __seqs_begin) 1636*38fd1498Szrj 1637*38fd1498Szrj // catch special case: no sequences 1638*38fd1498Szrj if (__seqs_begin == __seqs_end) 1639*38fd1498Szrj return __target; 1640*38fd1498Szrj 1641*38fd1498Szrj // Execute merge; maybe parallel, depending on the number of merged 1642*38fd1498Szrj // elements and the number of sequences and global thresholds in 1643*38fd1498Szrj // Settings. 1644*38fd1498Szrj if ((__seqs_end - __seqs_begin > 1) 1645*38fd1498Szrj && _GLIBCXX_PARALLEL_CONDITION( 1646*38fd1498Szrj ((__seqs_end - __seqs_begin) >= 1647*38fd1498Szrj __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 1648*38fd1498Szrj && ((_SequenceIndex)__length >= 1649*38fd1498Szrj __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 1650*38fd1498Szrj return parallel_multiway_merge 1651*38fd1498Szrj </* __stable = */ true, /* __sentinels = */ false> 1652*38fd1498Szrj (__seqs_begin, __seqs_end, __target, 1653*38fd1498Szrj multiway_merge_sampling_splitting</* __stable = */ true, 1654*38fd1498Szrj typename std::iterator_traits<_RAIterPairIterator> 1655*38fd1498Szrj ::value_type*, _Compare, _DifferenceTp>, 1656*38fd1498Szrj static_cast<_DifferenceType>(__length), __comp, 1657*38fd1498Szrj __tag.__get_num_threads()); 1658*38fd1498Szrj else 1659*38fd1498Szrj return __sequential_multiway_merge 1660*38fd1498Szrj </* __stable = */ true, /* __sentinels = */ false> 1661*38fd1498Szrj (__seqs_begin, __seqs_end, __target, 1662*38fd1498Szrj *(__seqs_begin->second), __length, __comp); 1663*38fd1498Szrj } 1664*38fd1498Szrj 1665*38fd1498Szrj // public interface 1666*38fd1498Szrj template<typename _RAIterPairIterator, 1667*38fd1498Szrj typename _RAIterOut, 1668*38fd1498Szrj typename _DifferenceTp, 1669*38fd1498Szrj typename _Compare> 1670*38fd1498Szrj _RAIterOut 1671*38fd1498Szrj stable_multiway_merge(_RAIterPairIterator __seqs_begin, 1672*38fd1498Szrj _RAIterPairIterator __seqs_end, 1673*38fd1498Szrj _RAIterOut __target, 1674*38fd1498Szrj _DifferenceTp __length, _Compare __comp, 1675*38fd1498Szrj parallel_tag __tag = parallel_tag(0)) 1676*38fd1498Szrj { 1677*38fd1498Szrj return stable_multiway_merge 1678*38fd1498Szrj (__seqs_begin, __seqs_end, __target, __length, __comp, 1679*38fd1498Szrj exact_tag(__tag.__get_num_threads())); 1680*38fd1498Szrj } 1681*38fd1498Szrj 1682*38fd1498Szrj // public interface 1683*38fd1498Szrj template<typename _RAIterPairIterator, 1684*38fd1498Szrj typename _RAIterOut, 1685*38fd1498Szrj typename _DifferenceTp, 1686*38fd1498Szrj typename _Compare> 1687*38fd1498Szrj _RAIterOut 1688*38fd1498Szrj stable_multiway_merge(_RAIterPairIterator __seqs_begin, 1689*38fd1498Szrj _RAIterPairIterator __seqs_end, 1690*38fd1498Szrj _RAIterOut __target, 1691*38fd1498Szrj _DifferenceTp __length, _Compare __comp, 1692*38fd1498Szrj default_parallel_tag __tag) 1693*38fd1498Szrj { 1694*38fd1498Szrj return stable_multiway_merge 1695*38fd1498Szrj (__seqs_begin, __seqs_end, __target, __length, __comp, 1696*38fd1498Szrj exact_tag(__tag.__get_num_threads())); 1697*38fd1498Szrj } 1698*38fd1498Szrj 1699*38fd1498Szrj /** 1700*38fd1498Szrj * @brief Multiway Merge Frontend. 1701*38fd1498Szrj * 1702*38fd1498Szrj * Merge the sequences specified by seqs_begin and __seqs_end into 1703*38fd1498Szrj * __target. __seqs_begin and __seqs_end must point to a sequence of 1704*38fd1498Szrj * pairs. These pairs must contain an iterator to the beginning 1705*38fd1498Szrj * of a sequence in their first entry and an iterator the _M_end of 1706*38fd1498Szrj * the same sequence in their second entry. 1707*38fd1498Szrj * 1708*38fd1498Szrj * Ties are broken arbitrarily. See stable_multiway_merge for a variant 1709*38fd1498Szrj * that breaks ties by sequence number but is slower. 1710*38fd1498Szrj * 1711*38fd1498Szrj * The first entries of the pairs (i.e. the begin iterators) will be moved 1712*38fd1498Szrj * forward accordingly. 1713*38fd1498Szrj * 1714*38fd1498Szrj * The output sequence has to provide enough space for all elements 1715*38fd1498Szrj * that are written to it. 1716*38fd1498Szrj * 1717*38fd1498Szrj * This function will merge the input sequences: 1718*38fd1498Szrj * 1719*38fd1498Szrj * - not stable 1720*38fd1498Szrj * - parallel, depending on the input size and Settings 1721*38fd1498Szrj * - using sampling for splitting 1722*38fd1498Szrj * - using sentinels 1723*38fd1498Szrj * 1724*38fd1498Szrj * You have to take care that the element the _M_end iterator points to is 1725*38fd1498Szrj * readable and contains a value that is greater than any other non-sentinel 1726*38fd1498Szrj * value in all sequences. 1727*38fd1498Szrj * 1728*38fd1498Szrj * Example: 1729*38fd1498Szrj * 1730*38fd1498Szrj * <pre> 1731*38fd1498Szrj * int sequences[10][11]; 1732*38fd1498Szrj * for (int __i = 0; __i < 10; ++__i) 1733*38fd1498Szrj * for (int __j = 0; __i < 11; ++__j) 1734*38fd1498Szrj * sequences[__i][__j] = __j; // __last one is sentinel! 1735*38fd1498Szrj * 1736*38fd1498Szrj * int __out[33]; 1737*38fd1498Szrj * std::vector<std::pair<int*> > seqs; 1738*38fd1498Szrj * for (int __i = 0; __i < 10; ++__i) 1739*38fd1498Szrj * { seqs.push(std::make_pair<int*>(sequences[__i], 1740*38fd1498Szrj * sequences[__i] + 10)) } 1741*38fd1498Szrj * 1742*38fd1498Szrj * multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33); 1743*38fd1498Szrj * </pre> 1744*38fd1498Szrj * 1745*38fd1498Szrj * @pre All input sequences must be sorted. 1746*38fd1498Szrj * @pre Target must provide enough space to merge out length elements or 1747*38fd1498Szrj * the number of elements in all sequences, whichever is smaller. 1748*38fd1498Szrj * @pre For each @c __i, @c __seqs_begin[__i].second must be the end 1749*38fd1498Szrj * marker of the sequence, but also reference the one more __sentinel 1750*38fd1498Szrj * element. 1751*38fd1498Szrj * 1752*38fd1498Szrj * @post [__target, return __value) contains merged __elements from the 1753*38fd1498Szrj * input sequences. 1754*38fd1498Szrj * @post return __value - __target = min(__length, number of elements in all 1755*38fd1498Szrj * sequences). 1756*38fd1498Szrj * 1757*38fd1498Szrj * @see stable_multiway_merge_sentinels 1758*38fd1498Szrj * 1759*38fd1498Szrj * @tparam _RAIterPairIterator iterator over sequence 1760*38fd1498Szrj * of pairs of iterators 1761*38fd1498Szrj * @tparam _RAIterOut iterator over target sequence 1762*38fd1498Szrj * @tparam _DifferenceTp difference type for the sequence 1763*38fd1498Szrj * @tparam _Compare strict weak ordering type to compare elements 1764*38fd1498Szrj * in sequences 1765*38fd1498Szrj * 1766*38fd1498Szrj * @param __seqs_begin __begin of sequence __sequence 1767*38fd1498Szrj * @param __seqs_end _M_end of sequence __sequence 1768*38fd1498Szrj * @param __target target sequence to merge to. 1769*38fd1498Szrj * @param __comp strict weak ordering to use for element comparison. 1770*38fd1498Szrj * @param __length Maximum length to merge, possibly larger than the 1771*38fd1498Szrj * number of elements available. 1772*38fd1498Szrj * 1773*38fd1498Szrj * @return _M_end iterator of output sequence 1774*38fd1498Szrj */ 1775*38fd1498Szrj // multiway_merge_sentinels 1776*38fd1498Szrj // public interface 1777*38fd1498Szrj template<typename _RAIterPairIterator, 1778*38fd1498Szrj typename _RAIterOut, 1779*38fd1498Szrj typename _DifferenceTp, 1780*38fd1498Szrj typename _Compare> 1781*38fd1498Szrj _RAIterOut 1782*38fd1498Szrj multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 1783*38fd1498Szrj _RAIterPairIterator __seqs_end, 1784*38fd1498Szrj _RAIterOut __target, 1785*38fd1498Szrj _DifferenceTp __length, _Compare __comp, 1786*38fd1498Szrj __gnu_parallel::sequential_tag) 1787*38fd1498Szrj { 1788*38fd1498Szrj typedef _DifferenceTp _DifferenceType; 1789*38fd1498Szrj _GLIBCXX_CALL(__seqs_end - __seqs_begin) 1790*38fd1498Szrj 1791*38fd1498Szrj // catch special case: no sequences 1792*38fd1498Szrj if (__seqs_begin == __seqs_end) 1793*38fd1498Szrj return __target; 1794*38fd1498Szrj 1795*38fd1498Szrj // Execute multiway merge *sequentially*. 1796*38fd1498Szrj return __sequential_multiway_merge 1797*38fd1498Szrj </* __stable = */ false, /* __sentinels = */ true> 1798*38fd1498Szrj (__seqs_begin, __seqs_end, 1799*38fd1498Szrj __target, *(__seqs_begin->second), __length, __comp); 1800*38fd1498Szrj } 1801*38fd1498Szrj 1802*38fd1498Szrj // public interface 1803*38fd1498Szrj template<typename _RAIterPairIterator, 1804*38fd1498Szrj typename _RAIterOut, 1805*38fd1498Szrj typename _DifferenceTp, 1806*38fd1498Szrj typename _Compare> 1807*38fd1498Szrj _RAIterOut 1808*38fd1498Szrj multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 1809*38fd1498Szrj _RAIterPairIterator __seqs_end, 1810*38fd1498Szrj _RAIterOut __target, 1811*38fd1498Szrj _DifferenceTp __length, _Compare __comp, 1812*38fd1498Szrj __gnu_parallel::exact_tag __tag) 1813*38fd1498Szrj { 1814*38fd1498Szrj typedef _DifferenceTp _DifferenceType; 1815*38fd1498Szrj _GLIBCXX_CALL(__seqs_end - __seqs_begin) 1816*38fd1498Szrj 1817*38fd1498Szrj // catch special case: no sequences 1818*38fd1498Szrj if (__seqs_begin == __seqs_end) 1819*38fd1498Szrj return __target; 1820*38fd1498Szrj 1821*38fd1498Szrj // Execute merge; maybe parallel, depending on the number of merged 1822*38fd1498Szrj // elements and the number of sequences and global thresholds in 1823*38fd1498Szrj // Settings. 1824*38fd1498Szrj if ((__seqs_end - __seqs_begin > 1) 1825*38fd1498Szrj && _GLIBCXX_PARALLEL_CONDITION( 1826*38fd1498Szrj ((__seqs_end - __seqs_begin) >= 1827*38fd1498Szrj __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 1828*38fd1498Szrj && ((_SequenceIndex)__length >= 1829*38fd1498Szrj __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 1830*38fd1498Szrj return parallel_multiway_merge 1831*38fd1498Szrj </* __stable = */ false, /* __sentinels = */ true> 1832*38fd1498Szrj (__seqs_begin, __seqs_end, __target, 1833*38fd1498Szrj multiway_merge_exact_splitting</* __stable = */ false, 1834*38fd1498Szrj typename std::iterator_traits<_RAIterPairIterator> 1835*38fd1498Szrj ::value_type*, _Compare, _DifferenceTp>, 1836*38fd1498Szrj static_cast<_DifferenceType>(__length), __comp, 1837*38fd1498Szrj __tag.__get_num_threads()); 1838*38fd1498Szrj else 1839*38fd1498Szrj return __sequential_multiway_merge 1840*38fd1498Szrj </* __stable = */ false, /* __sentinels = */ true> 1841*38fd1498Szrj (__seqs_begin, __seqs_end, __target, 1842*38fd1498Szrj *(__seqs_begin->second), __length, __comp); 1843*38fd1498Szrj } 1844*38fd1498Szrj 1845*38fd1498Szrj // public interface 1846*38fd1498Szrj template<typename _RAIterPairIterator, 1847*38fd1498Szrj typename _RAIterOut, 1848*38fd1498Szrj typename _DifferenceTp, 1849*38fd1498Szrj typename _Compare> 1850*38fd1498Szrj _RAIterOut 1851*38fd1498Szrj multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 1852*38fd1498Szrj _RAIterPairIterator __seqs_end, 1853*38fd1498Szrj _RAIterOut __target, 1854*38fd1498Szrj _DifferenceTp __length, _Compare __comp, 1855*38fd1498Szrj sampling_tag __tag) 1856*38fd1498Szrj { 1857*38fd1498Szrj typedef _DifferenceTp _DifferenceType; 1858*38fd1498Szrj _GLIBCXX_CALL(__seqs_end - __seqs_begin) 1859*38fd1498Szrj 1860*38fd1498Szrj // catch special case: no sequences 1861*38fd1498Szrj if (__seqs_begin == __seqs_end) 1862*38fd1498Szrj return __target; 1863*38fd1498Szrj 1864*38fd1498Szrj // Execute merge; maybe parallel, depending on the number of merged 1865*38fd1498Szrj // elements and the number of sequences and global thresholds in 1866*38fd1498Szrj // Settings. 1867*38fd1498Szrj if ((__seqs_end - __seqs_begin > 1) 1868*38fd1498Szrj && _GLIBCXX_PARALLEL_CONDITION( 1869*38fd1498Szrj ((__seqs_end - __seqs_begin) >= 1870*38fd1498Szrj __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 1871*38fd1498Szrj && ((_SequenceIndex)__length >= 1872*38fd1498Szrj __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 1873*38fd1498Szrj return parallel_multiway_merge 1874*38fd1498Szrj </* __stable = */ false, /* __sentinels = */ true> 1875*38fd1498Szrj (__seqs_begin, __seqs_end, __target, 1876*38fd1498Szrj multiway_merge_sampling_splitting</* __stable = */ false, 1877*38fd1498Szrj typename std::iterator_traits<_RAIterPairIterator> 1878*38fd1498Szrj ::value_type*, _Compare, _DifferenceTp>, 1879*38fd1498Szrj static_cast<_DifferenceType>(__length), __comp, 1880*38fd1498Szrj __tag.__get_num_threads()); 1881*38fd1498Szrj else 1882*38fd1498Szrj return __sequential_multiway_merge 1883*38fd1498Szrj </* __stable = */false, /* __sentinels = */ true>( 1884*38fd1498Szrj __seqs_begin, __seqs_end, __target, 1885*38fd1498Szrj *(__seqs_begin->second), __length, __comp); 1886*38fd1498Szrj } 1887*38fd1498Szrj 1888*38fd1498Szrj // public interface 1889*38fd1498Szrj template<typename _RAIterPairIterator, 1890*38fd1498Szrj typename _RAIterOut, 1891*38fd1498Szrj typename _DifferenceTp, 1892*38fd1498Szrj typename _Compare> 1893*38fd1498Szrj _RAIterOut 1894*38fd1498Szrj multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 1895*38fd1498Szrj _RAIterPairIterator __seqs_end, 1896*38fd1498Szrj _RAIterOut __target, 1897*38fd1498Szrj _DifferenceTp __length, _Compare __comp, 1898*38fd1498Szrj parallel_tag __tag = parallel_tag(0)) 1899*38fd1498Szrj { 1900*38fd1498Szrj return multiway_merge_sentinels 1901*38fd1498Szrj (__seqs_begin, __seqs_end, __target, __length, __comp, 1902*38fd1498Szrj exact_tag(__tag.__get_num_threads())); 1903*38fd1498Szrj } 1904*38fd1498Szrj 1905*38fd1498Szrj // public interface 1906*38fd1498Szrj template<typename _RAIterPairIterator, 1907*38fd1498Szrj typename _RAIterOut, 1908*38fd1498Szrj typename _DifferenceTp, 1909*38fd1498Szrj typename _Compare> 1910*38fd1498Szrj _RAIterOut 1911*38fd1498Szrj multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 1912*38fd1498Szrj _RAIterPairIterator __seqs_end, 1913*38fd1498Szrj _RAIterOut __target, 1914*38fd1498Szrj _DifferenceTp __length, _Compare __comp, 1915*38fd1498Szrj default_parallel_tag __tag) 1916*38fd1498Szrj { 1917*38fd1498Szrj return multiway_merge_sentinels 1918*38fd1498Szrj (__seqs_begin, __seqs_end, __target, __length, __comp, 1919*38fd1498Szrj exact_tag(__tag.__get_num_threads())); 1920*38fd1498Szrj } 1921*38fd1498Szrj 1922*38fd1498Szrj // stable_multiway_merge_sentinels 1923*38fd1498Szrj // public interface 1924*38fd1498Szrj template<typename _RAIterPairIterator, 1925*38fd1498Szrj typename _RAIterOut, 1926*38fd1498Szrj typename _DifferenceTp, 1927*38fd1498Szrj typename _Compare> 1928*38fd1498Szrj _RAIterOut 1929*38fd1498Szrj stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 1930*38fd1498Szrj _RAIterPairIterator __seqs_end, 1931*38fd1498Szrj _RAIterOut __target, 1932*38fd1498Szrj _DifferenceTp __length, _Compare __comp, 1933*38fd1498Szrj __gnu_parallel::sequential_tag) 1934*38fd1498Szrj { 1935*38fd1498Szrj typedef _DifferenceTp _DifferenceType; 1936*38fd1498Szrj _GLIBCXX_CALL(__seqs_end - __seqs_begin) 1937*38fd1498Szrj 1938*38fd1498Szrj // catch special case: no sequences 1939*38fd1498Szrj if (__seqs_begin == __seqs_end) 1940*38fd1498Szrj return __target; 1941*38fd1498Szrj 1942*38fd1498Szrj // Execute multiway merge *sequentially*. 1943*38fd1498Szrj return __sequential_multiway_merge 1944*38fd1498Szrj </* __stable = */ true, /* __sentinels = */ true> 1945*38fd1498Szrj (__seqs_begin, __seqs_end, __target, 1946*38fd1498Szrj *(__seqs_begin->second), __length, __comp); 1947*38fd1498Szrj } 1948*38fd1498Szrj 1949*38fd1498Szrj // public interface 1950*38fd1498Szrj template<typename _RAIterPairIterator, 1951*38fd1498Szrj typename _RAIterOut, 1952*38fd1498Szrj typename _DifferenceTp, 1953*38fd1498Szrj typename _Compare> 1954*38fd1498Szrj _RAIterOut 1955*38fd1498Szrj stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 1956*38fd1498Szrj _RAIterPairIterator __seqs_end, 1957*38fd1498Szrj _RAIterOut __target, 1958*38fd1498Szrj _DifferenceTp __length, _Compare __comp, 1959*38fd1498Szrj __gnu_parallel::exact_tag __tag) 1960*38fd1498Szrj { 1961*38fd1498Szrj typedef _DifferenceTp _DifferenceType; 1962*38fd1498Szrj _GLIBCXX_CALL(__seqs_end - __seqs_begin) 1963*38fd1498Szrj 1964*38fd1498Szrj // catch special case: no sequences 1965*38fd1498Szrj if (__seqs_begin == __seqs_end) 1966*38fd1498Szrj return __target; 1967*38fd1498Szrj 1968*38fd1498Szrj // Execute merge; maybe parallel, depending on the number of merged 1969*38fd1498Szrj // elements and the number of sequences and global thresholds in 1970*38fd1498Szrj // Settings. 1971*38fd1498Szrj if ((__seqs_end - __seqs_begin > 1) 1972*38fd1498Szrj && _GLIBCXX_PARALLEL_CONDITION( 1973*38fd1498Szrj ((__seqs_end - __seqs_begin) >= 1974*38fd1498Szrj __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 1975*38fd1498Szrj && ((_SequenceIndex)__length >= 1976*38fd1498Szrj __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 1977*38fd1498Szrj return parallel_multiway_merge 1978*38fd1498Szrj </* __stable = */ true, /* __sentinels = */ true> 1979*38fd1498Szrj (__seqs_begin, __seqs_end, __target, 1980*38fd1498Szrj multiway_merge_exact_splitting</* __stable = */ true, 1981*38fd1498Szrj typename std::iterator_traits<_RAIterPairIterator> 1982*38fd1498Szrj ::value_type*, _Compare, _DifferenceTp>, 1983*38fd1498Szrj static_cast<_DifferenceType>(__length), __comp, 1984*38fd1498Szrj __tag.__get_num_threads()); 1985*38fd1498Szrj else 1986*38fd1498Szrj return __sequential_multiway_merge 1987*38fd1498Szrj </* __stable = */ true, /* __sentinels = */ true> 1988*38fd1498Szrj (__seqs_begin, __seqs_end, __target, 1989*38fd1498Szrj *(__seqs_begin->second), __length, __comp); 1990*38fd1498Szrj } 1991*38fd1498Szrj 1992*38fd1498Szrj // public interface 1993*38fd1498Szrj template<typename _RAIterPairIterator, 1994*38fd1498Szrj typename _RAIterOut, 1995*38fd1498Szrj typename _DifferenceTp, 1996*38fd1498Szrj typename _Compare> 1997*38fd1498Szrj _RAIterOut 1998*38fd1498Szrj stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 1999*38fd1498Szrj _RAIterPairIterator __seqs_end, 2000*38fd1498Szrj _RAIterOut __target, 2001*38fd1498Szrj _DifferenceTp __length, 2002*38fd1498Szrj _Compare __comp, 2003*38fd1498Szrj sampling_tag __tag) 2004*38fd1498Szrj { 2005*38fd1498Szrj typedef _DifferenceTp _DifferenceType; 2006*38fd1498Szrj _GLIBCXX_CALL(__seqs_end - __seqs_begin) 2007*38fd1498Szrj 2008*38fd1498Szrj // catch special case: no sequences 2009*38fd1498Szrj if (__seqs_begin == __seqs_end) 2010*38fd1498Szrj return __target; 2011*38fd1498Szrj 2012*38fd1498Szrj // Execute merge; maybe parallel, depending on the number of merged 2013*38fd1498Szrj // elements and the number of sequences and global thresholds in 2014*38fd1498Szrj // Settings. 2015*38fd1498Szrj if ((__seqs_end - __seqs_begin > 1) 2016*38fd1498Szrj && _GLIBCXX_PARALLEL_CONDITION( 2017*38fd1498Szrj ((__seqs_end - __seqs_begin) >= 2018*38fd1498Szrj __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 2019*38fd1498Szrj && ((_SequenceIndex)__length >= 2020*38fd1498Szrj __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 2021*38fd1498Szrj return parallel_multiway_merge 2022*38fd1498Szrj </* __stable = */ true, /* __sentinels = */ true> 2023*38fd1498Szrj (__seqs_begin, __seqs_end, __target, 2024*38fd1498Szrj multiway_merge_sampling_splitting</* __stable = */ true, 2025*38fd1498Szrj typename std::iterator_traits<_RAIterPairIterator> 2026*38fd1498Szrj ::value_type*, _Compare, _DifferenceTp>, 2027*38fd1498Szrj static_cast<_DifferenceType>(__length), __comp, 2028*38fd1498Szrj __tag.__get_num_threads()); 2029*38fd1498Szrj else 2030*38fd1498Szrj return __sequential_multiway_merge 2031*38fd1498Szrj </* __stable = */ true, /* __sentinels = */ true> 2032*38fd1498Szrj (__seqs_begin, __seqs_end, __target, 2033*38fd1498Szrj *(__seqs_begin->second), __length, __comp); 2034*38fd1498Szrj } 2035*38fd1498Szrj 2036*38fd1498Szrj // public interface 2037*38fd1498Szrj template<typename _RAIterPairIterator, 2038*38fd1498Szrj typename _RAIterOut, 2039*38fd1498Szrj typename _DifferenceTp, 2040*38fd1498Szrj typename _Compare> 2041*38fd1498Szrj _RAIterOut 2042*38fd1498Szrj stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 2043*38fd1498Szrj _RAIterPairIterator __seqs_end, 2044*38fd1498Szrj _RAIterOut __target, 2045*38fd1498Szrj _DifferenceTp __length, 2046*38fd1498Szrj _Compare __comp, 2047*38fd1498Szrj parallel_tag __tag = parallel_tag(0)) 2048*38fd1498Szrj { 2049*38fd1498Szrj return stable_multiway_merge_sentinels 2050*38fd1498Szrj (__seqs_begin, __seqs_end, __target, __length, __comp, 2051*38fd1498Szrj exact_tag(__tag.__get_num_threads())); 2052*38fd1498Szrj } 2053*38fd1498Szrj 2054*38fd1498Szrj // public interface 2055*38fd1498Szrj template<typename _RAIterPairIterator, 2056*38fd1498Szrj typename _RAIterOut, 2057*38fd1498Szrj typename _DifferenceTp, 2058*38fd1498Szrj typename _Compare> 2059*38fd1498Szrj _RAIterOut 2060*38fd1498Szrj stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 2061*38fd1498Szrj _RAIterPairIterator __seqs_end, 2062*38fd1498Szrj _RAIterOut __target, 2063*38fd1498Szrj _DifferenceTp __length, _Compare __comp, 2064*38fd1498Szrj default_parallel_tag __tag) 2065*38fd1498Szrj { 2066*38fd1498Szrj return stable_multiway_merge_sentinels 2067*38fd1498Szrj (__seqs_begin, __seqs_end, __target, __length, __comp, 2068*38fd1498Szrj exact_tag(__tag.__get_num_threads())); 2069*38fd1498Szrj } 2070*38fd1498Szrj }; // namespace __gnu_parallel 2071*38fd1498Szrj 2072*38fd1498Szrj #endif /* _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H */ 2073