libstdc++-v3/include/parallel/multiway_merge.h

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