l4/pkg/l4re-core/libstdc++-v3/contrib/libstdc++-v3-4.4/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 RandomAccessIterator, typename Comparator>
  61   class guarded_iterator;
  62
  63 // Making the arguments const references seems to dangerous,
  64 // the user-defined comparator might not be const.
  65 template<typename RandomAccessIterator, typename Comparator>
  66   inline bool
  67   operator<(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
  68              guarded_iterator<RandomAccessIterator, Comparator>& bi2);
  69
  70 template<typename RandomAccessIterator, typename Comparator>
  71   inline bool
  72   operator<=(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
  73               guarded_iterator<RandomAccessIterator, Comparator>& 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 RandomAccessIterator is not possible since
  81  * RandomAccessIterator need not be a class.
  82  */
  83 template<typename RandomAccessIterator, typename Comparator>
  84   class guarded_iterator
  85   {
  86   private:
  87     /** @brief Current iterator position. */
  88     RandomAccessIterator current;
  89
  90     /** @brief End iterator of the sequence. */
  91     RandomAccessIterator end;
  92
  93     /** @brief Comparator. */
  94     Comparator& comp;
  95
  96   public:
  97     /** @brief Constructor. Sets iterator to beginning of sequence.
  98     *  @param begin Begin iterator of sequence.
  99     *  @param end End iterator of sequence.
 100     *  @param comp Comparator provided for associated overloaded
 101     *  compare operators. */
 102     guarded_iterator(RandomAccessIterator begin,
 103                      RandomAccessIterator end, Comparator& comp)
 104     : current(begin), end(end), comp(comp)
 105     { }
 106
 107     /** @brief Pre-increment operator.
 108     *  @return This. */
 109     guarded_iterator<RandomAccessIterator, Comparator>&
 110     operator++()
 111     {
 112       ++current;
 113       return *this;
 114     }
 115
 116     /** @brief Dereference operator.
 117     *  @return Referenced element. */
 118     typename std::iterator_traits<RandomAccessIterator>::value_type&
 119     operator*()
 120     { return *current; }
 121
 122     /** @brief Convert to wrapped iterator.
 123     *  @return Wrapped iterator. */
 124     operator RandomAccessIterator()
 125     { return current; }
 126
 127     friend bool
 128     operator< <RandomAccessIterator, Comparator>(
 129       guarded_iterator<RandomAccessIterator, Comparator>& bi1,
 130       guarded_iterator<RandomAccessIterator, Comparator>& bi2);
 131
 132     friend bool
 133     operator<= <RandomAccessIterator, Comparator>(
 134       guarded_iterator<RandomAccessIterator, Comparator>& bi1,
 135       guarded_iterator<RandomAccessIterator, Comparator>& 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 RandomAccessIterator, typename Comparator>
 143   inline bool
 144   operator<(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
 145             guarded_iterator<RandomAccessIterator, Comparator>& bi2)
 146   {
 147     if (bi1.current == bi1.end) //bi1 is sup
 148       return bi2.current == bi2.end;    //bi2 is not sup
 149     if (bi2.current == bi2.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 RandomAccessIterator, typename Comparator>
 159   inline bool
 160   operator<=(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
 161                guarded_iterator<RandomAccessIterator, Comparator>& bi2)
 162   {
 163     if (bi2.current == bi2.end) //bi1 is sup
 164       return bi1.current != bi1.end;    //bi2 is not sup
 165     if (bi1.current == bi1.end) //bi2 is sup
 166       return false;
 167     return !(bi1.comp)(*bi2, *bi1);     //normal compare
 168   }
 169
 170 template<typename RandomAccessIterator, typename Comparator>
 171   class unguarded_iterator;
 172
 173 template<typename RandomAccessIterator, typename Comparator>
 174   inline bool
 175   operator<(unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
 176             unguarded_iterator<RandomAccessIterator, Comparator>& bi2);
 177
 178 template<typename RandomAccessIterator, typename Comparator>
 179   inline bool
 180   operator<=(unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
 181              unguarded_iterator<RandomAccessIterator, Comparator>& bi2);
 182
 183 template<typename RandomAccessIterator, typename Comparator>
 184   class unguarded_iterator
 185   {
 186   private:
 187     /** @brief Current iterator position. */
 188     RandomAccessIterator current;
 189     /** @brief Comparator. */
 190     mutable Comparator& comp;
 191
 192   public:
 193     /** @brief Constructor. Sets iterator to beginning of sequence.
 194     *  @param begin Begin iterator of sequence.
 195     *  @param end Unused, only for compatibility.
 196     *  @param comp Unused, only for compatibility. */
 197     unguarded_iterator(RandomAccessIterator begin,
 198                        RandomAccessIterator end, Comparator& comp)
 199     : current(begin), comp(comp)
 200     { }
 201
 202     /** @brief Pre-increment operator.
 203     *  @return This. */
 204     unguarded_iterator<RandomAccessIterator, Comparator>&
 205     operator++()
 206     {
 207       ++current;
 208       return *this;
 209     }
 210
 211     /** @brief Dereference operator.
 212     *  @return Referenced element. */
 213     typename std::iterator_traits<RandomAccessIterator>::value_type&
 214     operator*()
 215     { return *current; }
 216
 217     /** @brief Convert to wrapped iterator.
 218     *  @return Wrapped iterator. */
 219     operator RandomAccessIterator()
 220     { return current; }
 221
 222     friend bool
 223     operator< <RandomAccessIterator, Comparator>(
 224       unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
 225       unguarded_iterator<RandomAccessIterator, Comparator>& bi2);
 226
 227     friend bool
 228     operator<= <RandomAccessIterator, Comparator>(
 229       unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
 230       unguarded_iterator<RandomAccessIterator, Comparator>& 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 RandomAccessIterator, typename Comparator>
 238   inline bool
 239   operator<(unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
 240             unguarded_iterator<RandomAccessIterator, Comparator>& 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 RandomAccessIterator, typename Comparator>
 251   inline bool
 252   operator<=(unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
 253             unguarded_iterator<RandomAccessIterator, Comparator>& 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 out 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 out 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 RandomAccessIteratorIterator,
 286          typename RandomAccessIterator3,
 287          typename _DifferenceTp,
 288          typename Comparator>
 289   RandomAccessIterator3
 290   multiway_merge_3_variant(
 291       RandomAccessIteratorIterator seqs_begin,
 292       RandomAccessIteratorIterator seqs_end,
 293       RandomAccessIterator3 target,
 294       _DifferenceTp length, Comparator comp)
 295   {
 296     _GLIBCXX_CALL(length);
 297
 298     typedef _DifferenceTp difference_type;
 299
 300     typedef typename std::iterator_traits<RandomAccessIteratorIterator>
 301       ::value_type::first_type
 302       RandomAccessIterator1;
 303     typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
 304       value_type;
 305
 306     if (length == 0)
 307       return target;
 308
 309 #if _GLIBCXX_ASSERTIONS
 310     _DifferenceTp orig_length = length;
 311 #endif
 312
 313     iterator<RandomAccessIterator1, Comparator>
 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       ((RandomAccessIterator1)seq0 - seqs_begin[0].first) +
 366       ((RandomAccessIterator1)seq1 - seqs_begin[1].first) +
 367       ((RandomAccessIterator1)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 out 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 out 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 RandomAccessIteratorIterator,
 406          typename RandomAccessIterator3,
 407          typename _DifferenceTp,
 408          typename Comparator>
 409   RandomAccessIterator3
 410   multiway_merge_4_variant(RandomAccessIteratorIterator seqs_begin,
 411                            RandomAccessIteratorIterator seqs_end,
 412                            RandomAccessIterator3 target,
 413                            _DifferenceTp length, Comparator comp)
 414   {
 415     _GLIBCXX_CALL(length);
 416     typedef _DifferenceTp difference_type;
 417
 418     typedef typename std::iterator_traits<RandomAccessIteratorIterator>
 419       ::value_type::first_type
 420       RandomAccessIterator1;
 421     typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
 422       value_type;
 423
 424     iterator<RandomAccessIterator1, Comparator>
 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 out 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 RandomAccessIteratorIterator,
 530          typename RandomAccessIterator3,
 531          typename _DifferenceTp,
 532          typename Comparator>
 533   RandomAccessIterator3
 534   multiway_merge_loser_tree(RandomAccessIteratorIterator seqs_begin,
 535                             RandomAccessIteratorIterator seqs_end,
 536                             RandomAccessIterator3 target,
 537                             _DifferenceTp length, Comparator comp)
 538   {
 539     _GLIBCXX_CALL(length)
 540
 541     typedef _DifferenceTp difference_type;
 542     typedef typename std::iterator_traits<RandomAccessIteratorIterator>
 543       ::value_type::first_type
 544       RandomAccessIterator1;
 545     typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
 546       value_type;
 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     value_type* 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 (difference_type 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 out 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 RandomAccessIteratorIterator,
 612     typename RandomAccessIterator3,
 613     typename _DifferenceTp, typename Comparator>
 614   RandomAccessIterator3
 615   multiway_merge_loser_tree_unguarded(
 616     RandomAccessIteratorIterator seqs_begin,
 617     RandomAccessIteratorIterator seqs_end,
 618     RandomAccessIterator3 target,
 619     const typename std::iterator_traits<typename std::iterator_traits<
 620       RandomAccessIteratorIterator>::value_type::first_type>::value_type&
 621         sentinel,
 622     _DifferenceTp length,
 623     Comparator comp)
 624   {
 625     _GLIBCXX_CALL(length)
 626     typedef _DifferenceTp difference_type;
 627
 628     typedef typename std::iterator_traits<RandomAccessIteratorIterator>
 629       ::value_type::first_type
 630       RandomAccessIterator1;
 631     typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
 632       value_type;
 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     difference_type i = 0;
 652 #endif
 653
 654     RandomAccessIterator3 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 out 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 RandomAccessIteratorIterator,
 701     typename RandomAccessIterator3,
 702     typename _DifferenceTp,
 703     typename Comparator>
 704   RandomAccessIterator3
 705   multiway_merge_loser_tree_sentinel(
 706     RandomAccessIteratorIterator seqs_begin,
 707     RandomAccessIteratorIterator seqs_end,
 708     RandomAccessIterator3 target,
 709     const typename std::iterator_traits<typename std::iterator_traits<
 710       RandomAccessIteratorIterator>::value_type::first_type>::value_type&
 711         sentinel,
 712     _DifferenceTp length,
 713     Comparator comp)
 714   {
 715     _GLIBCXX_CALL(length)
 716
 717     typedef _DifferenceTp difference_type;
 718     typedef std::iterator_traits<RandomAccessIteratorIterator> traits_type;
 719     typedef typename std::iterator_traits<RandomAccessIteratorIterator>
 720       ::value_type::first_type
 721       RandomAccessIterator1;
 722     typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
 723       value_type;
 724
 725     RandomAccessIterator3 target_end;
 726
 727     for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s)
 728       // Move the sequends 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 (RandomAccessIteratorIterator 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 "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 loser_tree_traits<int>
 767  *   { static const bool use_pointer = false; };
 768  *
 769  *   template<>
 770  *   struct loser_tree_traits<heavyweight_type>
 771  *   { static const bool use_pointer = true; };
 772  *
 773  * @param T type to give the loser tree traits for.
 774  */
 775 template <typename T>
 776 struct loser_tree_traits
 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 use_pointer = (sizeof(T) > 4 * sizeof(T*));
 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 RandomAccessIteratorIterator,
 795   typename RandomAccessIterator3,
 796   typename _DifferenceTp,
 797   typename Comparator>
 798 struct multiway_merge_3_variant_sentinel_switch
 799 {
 800   RandomAccessIterator3 operator()(
 801       RandomAccessIteratorIterator seqs_begin,
 802       RandomAccessIteratorIterator seqs_end,
 803       RandomAccessIterator3 target,
 804       _DifferenceTp length, Comparator comp)
 805   {
 806     return multiway_merge_3_variant<guarded_iterator>(
 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 RandomAccessIteratorIterator,
 818   typename RandomAccessIterator3,
 819   typename _DifferenceTp,
 820   typename Comparator>
 821 struct multiway_merge_3_variant_sentinel_switch
 822     <true, RandomAccessIteratorIterator, RandomAccessIterator3,
 823      _DifferenceTp, Comparator>
 824 {
 825   RandomAccessIterator3 operator()(
 826       RandomAccessIteratorIterator seqs_begin,
 827       RandomAccessIteratorIterator seqs_end,
 828       RandomAccessIterator3 target,
 829       _DifferenceTp length, Comparator 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 RandomAccessIteratorIterator,
 844   typename RandomAccessIterator3,
 845   typename _DifferenceTp,
 846   typename Comparator>
 847 struct multiway_merge_4_variant_sentinel_switch
 848 {
 849   RandomAccessIterator3 operator()(
 850       RandomAccessIteratorIterator seqs_begin,
 851       RandomAccessIteratorIterator seqs_end,
 852       RandomAccessIterator3 target,
 853       _DifferenceTp length, Comparator comp)
 854   {
 855     return multiway_merge_4_variant<guarded_iterator>(
 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 RandomAccessIteratorIterator,
 867   typename RandomAccessIterator3,
 868   typename _DifferenceTp,
 869   typename Comparator>
 870 struct multiway_merge_4_variant_sentinel_switch
 871     <true, RandomAccessIteratorIterator, RandomAccessIterator3,
 872      _DifferenceTp, Comparator>
 873 {
 874   RandomAccessIterator3 operator()(
 875       RandomAccessIteratorIterator seqs_begin,
 876       RandomAccessIteratorIterator seqs_end,
 877       RandomAccessIterator3 target,
 878       _DifferenceTp length, Comparator 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 RandomAccessIteratorIterator,
 892   typename RandomAccessIterator3,
 893   typename _DifferenceTp,
 894   typename Comparator>
 895 struct multiway_merge_k_variant_sentinel_switch
 896 {
 897   RandomAccessIterator3 operator()(
 898       RandomAccessIteratorIterator seqs_begin,
 899       RandomAccessIteratorIterator seqs_end,
 900       RandomAccessIterator3 target,
 901       const typename std::iterator_traits<typename std::iterator_traits<
 902         RandomAccessIteratorIterator>::value_type::first_type>::value_type&
 903           sentinel,
 904       _DifferenceTp length, Comparator comp)
 905   {
 906     typedef typename std::iterator_traits<RandomAccessIteratorIterator>
 907       ::value_type::first_type
 908       RandomAccessIterator1;
 909     typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
 910       value_type;
 911
 912     return multiway_merge_loser_tree_sentinel<
 913         typename __gnu_cxx::__conditional_type<
 914             loser_tree_traits<value_type>::use_pointer
 915           , LoserTreePointerUnguarded<stable, value_type, Comparator>
 916           , LoserTreeUnguarded<stable, value_type, Comparator>
 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 RandomAccessIteratorIterator,
 927   typename RandomAccessIterator3,
 928   typename _DifferenceTp,
 929   typename Comparator>
 930 struct multiway_merge_k_variant_sentinel_switch
 931     <false, stable, RandomAccessIteratorIterator, RandomAccessIterator3,
 932      _DifferenceTp, Comparator>
 933 {
 934   RandomAccessIterator3 operator()(
 935       RandomAccessIteratorIterator seqs_begin,
 936       RandomAccessIteratorIterator seqs_end,
 937       RandomAccessIterator3 target,
 938       const typename std::iterator_traits<typename std::iterator_traits<
 939         RandomAccessIteratorIterator>::value_type::first_type>::value_type&
 940           sentinel,
 941       _DifferenceTp length, Comparator comp)
 942   {
 943     typedef typename std::iterator_traits<RandomAccessIteratorIterator>
 944       ::value_type::first_type
 945       RandomAccessIterator1;
 946     typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
 947       value_type;
 948
 949     return multiway_merge_loser_tree<
 950         typename __gnu_cxx::__conditional_type<
 951             loser_tree_traits<value_type>::use_pointer
 952           , LoserTreePointer<stable, value_type, Comparator>
 953           , LoserTree<stable, value_type, Comparator>
 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 out 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 RandomAccessIteratorIterator,
 975     typename RandomAccessIterator3,
 976     typename _DifferenceTp,
 977     typename Comparator>
 978   RandomAccessIterator3
 979   sequential_multiway_merge(
 980     RandomAccessIteratorIterator seqs_begin,
 981     RandomAccessIteratorIterator seqs_end,
 982     RandomAccessIterator3 target,
 983     const typename std::iterator_traits<typename std::iterator_traits<
 984       RandomAccessIteratorIterator>::value_type::first_type>::value_type&
 985         sentinel,
 986     _DifferenceTp length, Comparator comp)
 987   {
 988     _GLIBCXX_CALL(length)
 989
 990     typedef _DifferenceTp difference_type;
 991     typedef typename std::iterator_traits<RandomAccessIteratorIterator>
 992       ::value_type::first_type
 993       RandomAccessIterator1;
 994     typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
 995       value_type;
 996
 997 #if _GLIBCXX_ASSERTIONS
 998     for (RandomAccessIteratorIterator 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 (RandomAccessIteratorIterator 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     RandomAccessIterator3 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           , RandomAccessIteratorIterator
1037           , RandomAccessIterator3
1038           , _DifferenceTp
1039           , Comparator>()(seqs_begin, seqs_end, target, length, comp);
1040         break;
1041       case 4:
1042         return_target = multiway_merge_4_variant_sentinel_switch<
1043             sentinels
1044           , RandomAccessIteratorIterator
1045           , RandomAccessIterator3
1046           , _DifferenceTp
1047           , Comparator>()(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             , RandomAccessIteratorIterator
1054             , RandomAccessIterator3
1055             , _DifferenceTp
1056             , Comparator>()(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 RandomAccessIterator, class StrictWeakOrdering>
1072 struct sampling_sorter
1073 {
1074   void operator()(RandomAccessIterator first, RandomAccessIterator 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 RandomAccessIterator, class StrictWeakOrdering>
1085 struct sampling_sorter<false, RandomAccessIterator, StrictWeakOrdering>
1086 {
1087   void operator()(RandomAccessIterator first, RandomAccessIterator 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 RandomAccessIteratorIterator
1098   , typename Comparator
1099   , typename difference_type>
1100 void multiway_merge_sampling_splitting(
1101     RandomAccessIteratorIterator seqs_begin,
1102     RandomAccessIteratorIterator seqs_end,
1103     difference_type length, difference_type total_length, Comparator comp,
1104     std::vector<std::pair<difference_type, difference_type> > *pieces)
1105 {
1106   typedef typename std::iterator_traits<RandomAccessIteratorIterator>
1107     ::value_type::first_type
1108     RandomAccessIterator1;
1109   typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
1110     value_type;
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   difference_type num_samples =
1118       __gnu_parallel::_Settings::get().merge_oversampling * num_threads;
1119
1120   value_type* samples = static_cast<value_type*>(
1121     ::operator new(sizeof(value_type) * k * num_samples));
1122   // Sample.
1123   for (int s = 0; s < k; ++s)
1124     for (difference_type i = 0; i < num_samples; ++i)
1125       {
1126         difference_type sample_index =
1127             static_cast<difference_type>(
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             value_type(seqs_begin[s].first[sample_index]);
1133       }
1134
1135   // Sort stable or non-stable, depending on value of template parameter
1136   // "stable".
1137   sampling_sorter<stable, value_type*, Comparator>()(
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 RandomAccessIteratorIterator
1179   , typename Comparator
1180   , typename difference_type>
1181 void multiway_merge_exact_splitting(
1182     RandomAccessIteratorIterator seqs_begin,
1183     RandomAccessIteratorIterator seqs_end,
1184     difference_type length, difference_type total_length, Comparator comp,
1185     std::vector<std::pair<difference_type, difference_type> > *pieces)
1186 {
1187   typedef typename std::iterator_traits<RandomAccessIteratorIterator>
1188     ::value_type::first_type
1189     RandomAccessIterator1;
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<RandomAccessIterator1>* offsets =
1200       new std::vector<RandomAccessIterator1>[num_threads];
1201   std::vector<
1202       std::pair<RandomAccessIterator1, RandomAccessIterator1>
1203       > se(k);
1204
1205   copy(seqs_begin, seqs_end, se.begin());
1206
1207   difference_type* borders =
1208       new difference_type[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                 difference_type(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 out 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 RandomAccessIteratorIterator,
1280     typename RandomAccessIterator3,
1281     typename _DifferenceTp,
1282     typename Splitter,
1283     typename Comparator
1284     >
1285   RandomAccessIterator3
1286   parallel_multiway_merge(RandomAccessIteratorIterator seqs_begin,
1287                           RandomAccessIteratorIterator seqs_end,
1288                           RandomAccessIterator3 target,
1289                           Splitter splitter,
1290                           _DifferenceTp length,
1291                           Comparator comp,
1292                           thread_index_t 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 difference_type;
1301       typedef typename std::iterator_traits<RandomAccessIteratorIterator>
1302         ::value_type::first_type
1303         RandomAccessIterator1;
1304       typedef typename
1305         std::iterator_traits<RandomAccessIterator1>::value_type value_type;
1306
1307       // Leave only non-empty sequences.
1308       typedef std::pair<RandomAccessIterator1, RandomAccessIterator1> seq_type;
1309       seq_type* ne_seqs = new seq_type[seqs_end - seqs_begin];
1310       int k = 0;
1311       difference_type total_length = 0;
1312       for (RandomAccessIteratorIterator 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<difference_type, difference_type> >* pieces;
1334
1335       num_threads = static_cast<thread_index_t>
1336         (std::min<difference_type>(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<difference_type, difference_type> >[num_threads];
1346               for (int s = 0; s < num_threads; ++s)
1347                 pieces[s].resize(k);
1348
1349               difference_type 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           thread_index_t iam = omp_get_thread_num();
1358
1359           difference_type 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 (RandomAccessIteratorIterator 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 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 RandomAccessIteratorPairIterator iterator over sequence
1454  *    of pairs of iterators
1455  * @param RandomAccessIteratorOut iterator over target sequence
1456  * @param _DifferenceTp difference type for the sequence
1457  * @param Comparator strict weak ordering type to compare elements
1458  *    in sequences
1459  *
1460  * @param seqs_begin  begin of sequence sequence
1461  * @param seqs_end    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 end iterator of output sequence
1468  */
1469 // multiway_merge
1470 // public interface
1471 template<
1472     typename RandomAccessIteratorPairIterator
1473   , typename RandomAccessIteratorOut
1474   , typename _DifferenceTp
1475   , typename Comparator>
1476 RandomAccessIteratorOut
1477 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1478     , RandomAccessIteratorPairIterator seqs_end
1479     , RandomAccessIteratorOut target
1480     , _DifferenceTp length, Comparator comp
1481     , __gnu_parallel::sequential_tag)
1482 {
1483   typedef _DifferenceTp difference_type;
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 RandomAccessIteratorPairIterator
1499   , typename RandomAccessIteratorOut
1500   , typename _DifferenceTp
1501   , typename Comparator>
1502 RandomAccessIteratorOut
1503 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1504     , RandomAccessIteratorPairIterator seqs_end
1505     , RandomAccessIteratorOut target
1506     , _DifferenceTp length, Comparator comp
1507     , __gnu_parallel::exact_tag tag)
1508 {
1509     typedef _DifferenceTp difference_type;
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           && ((sequence_index_t)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<RandomAccessIteratorPairIterator>
1530               ::value_type*, Comparator, _DifferenceTp>,
1531           static_cast<difference_type>(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 RandomAccessIteratorPairIterator
1541   , typename RandomAccessIteratorOut
1542   , typename _DifferenceTp
1543   , typename Comparator>
1544 RandomAccessIteratorOut
1545 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1546     , RandomAccessIteratorPairIterator seqs_end
1547     , RandomAccessIteratorOut target
1548     , _DifferenceTp length, Comparator comp
1549     , __gnu_parallel::sampling_tag tag)
1550 {
1551     typedef _DifferenceTp difference_type;
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           && ((sequence_index_t)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<RandomAccessIteratorPairIterator>
1573               ::value_type*, Comparator, _DifferenceTp>,
1574           static_cast<difference_type>(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 RandomAccessIteratorPairIterator
1585   , typename RandomAccessIteratorOut
1586   , typename _DifferenceTp
1587   , typename Comparator>
1588 RandomAccessIteratorOut
1589 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1590     , RandomAccessIteratorPairIterator seqs_end
1591     , RandomAccessIteratorOut target
1592     , _DifferenceTp length, Comparator 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 RandomAccessIteratorPairIterator
1602   , typename RandomAccessIteratorOut
1603   , typename _DifferenceTp
1604   , typename Comparator>
1605 RandomAccessIteratorOut
1606 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1607     , RandomAccessIteratorPairIterator seqs_end
1608     , RandomAccessIteratorOut target
1609     , _DifferenceTp length, Comparator 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 RandomAccessIteratorPairIterator
1620   , typename RandomAccessIteratorOut
1621   , typename _DifferenceTp
1622   , typename Comparator>
1623 RandomAccessIteratorOut
1624 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1625     , RandomAccessIteratorPairIterator seqs_end
1626     , RandomAccessIteratorOut target
1627     , _DifferenceTp length, Comparator comp
1628     , __gnu_parallel::sequential_tag)
1629 {
1630     typedef _DifferenceTp difference_type;
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 RandomAccessIteratorPairIterator
1646   , typename RandomAccessIteratorOut
1647   , typename _DifferenceTp
1648   , typename Comparator>
1649 RandomAccessIteratorOut
1650 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1651     , RandomAccessIteratorPairIterator seqs_end
1652     , RandomAccessIteratorOut target
1653     , _DifferenceTp length, Comparator comp
1654     , __gnu_parallel::exact_tag tag)
1655 {
1656     typedef _DifferenceTp difference_type;
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           && ((sequence_index_t)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<RandomAccessIteratorPairIterator>
1678               ::value_type*, Comparator, _DifferenceTp>,
1679           static_cast<difference_type>(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 RandomAccessIteratorPairIterator
1690   , typename RandomAccessIteratorOut
1691   , typename _DifferenceTp
1692   , typename Comparator>
1693 RandomAccessIteratorOut
1694 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1695     , RandomAccessIteratorPairIterator seqs_end
1696     , RandomAccessIteratorOut target
1697     , _DifferenceTp length, Comparator comp
1698     , sampling_tag tag)
1699 {
1700     typedef _DifferenceTp difference_type;
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           && ((sequence_index_t)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<RandomAccessIteratorPairIterator>
1722               ::value_type*, Comparator, _DifferenceTp>,
1723           static_cast<difference_type>(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 RandomAccessIteratorPairIterator
1735   , typename RandomAccessIteratorOut
1736   , typename _DifferenceTp
1737   , typename Comparator>
1738 RandomAccessIteratorOut
1739 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1740     , RandomAccessIteratorPairIterator seqs_end
1741     , RandomAccessIteratorOut target
1742     , _DifferenceTp length, Comparator 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 RandomAccessIteratorPairIterator
1752   , typename RandomAccessIteratorOut
1753   , typename _DifferenceTp
1754   , typename Comparator>
1755 RandomAccessIteratorOut
1756 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1757     , RandomAccessIteratorPairIterator seqs_end
1758     , RandomAccessIteratorOut target
1759     , _DifferenceTp length, Comparator 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 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 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 RandomAccessIteratorPairIterator iterator over sequence
1826  *    of pairs of iterators
1827  * @param RandomAccessIteratorOut iterator over target sequence
1828  * @param _DifferenceTp difference type for the sequence
1829  * @param Comparator strict weak ordering type to compare elements
1830  *    in sequences
1831  *
1832  * @param seqs_begin  begin of sequence sequence
1833  * @param seqs_end    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 end iterator of output sequence
1840  */
1841 // multiway_merge_sentinels
1842 // public interface
1843 template<
1844     typename RandomAccessIteratorPairIterator
1845   , typename RandomAccessIteratorOut
1846   , typename _DifferenceTp
1847   , typename Comparator>
1848 RandomAccessIteratorOut
1849 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1850     , RandomAccessIteratorPairIterator seqs_end
1851     , RandomAccessIteratorOut target
1852     , _DifferenceTp length, Comparator comp
1853     , __gnu_parallel::sequential_tag)
1854 {
1855     typedef _DifferenceTp difference_type;
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 RandomAccessIteratorPairIterator
1872   , typename RandomAccessIteratorOut
1873   , typename _DifferenceTp
1874   , typename Comparator>
1875 RandomAccessIteratorOut
1876 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1877     , RandomAccessIteratorPairIterator seqs_end
1878     , RandomAccessIteratorOut target
1879     , _DifferenceTp length, Comparator comp
1880     , __gnu_parallel::exact_tag tag)
1881 {
1882     typedef _DifferenceTp difference_type;
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           && ((sequence_index_t)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<RandomAccessIteratorPairIterator>
1904               ::value_type*, Comparator, _DifferenceTp>,
1905           static_cast<difference_type>(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 RandomAccessIteratorPairIterator
1916   , typename RandomAccessIteratorOut
1917   , typename _DifferenceTp
1918   , typename Comparator>
1919 RandomAccessIteratorOut
1920 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1921     , RandomAccessIteratorPairIterator seqs_end
1922     , RandomAccessIteratorOut target
1923     , _DifferenceTp length, Comparator comp
1924     , sampling_tag tag)
1925 {
1926     typedef _DifferenceTp difference_type;
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           && ((sequence_index_t)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<RandomAccessIteratorPairIterator>
1947               ::value_type*, Comparator, _DifferenceTp>,
1948           static_cast<difference_type>(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 RandomAccessIteratorPairIterator
1959   , typename RandomAccessIteratorOut
1960   , typename _DifferenceTp
1961   , typename Comparator>
1962 RandomAccessIteratorOut
1963 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1964     , RandomAccessIteratorPairIterator seqs_end
1965     , RandomAccessIteratorOut target
1966     , _DifferenceTp length, Comparator 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 RandomAccessIteratorPairIterator
1976   , typename RandomAccessIteratorOut
1977   , typename _DifferenceTp
1978   , typename Comparator>
1979 RandomAccessIteratorOut
1980 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1981     , RandomAccessIteratorPairIterator seqs_end
1982     , RandomAccessIteratorOut target
1983     , _DifferenceTp length, Comparator 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 RandomAccessIteratorPairIterator
1994   , typename RandomAccessIteratorOut
1995   , typename _DifferenceTp
1996   , typename Comparator>
1997 RandomAccessIteratorOut
1998 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1999     , RandomAccessIteratorPairIterator seqs_end
2000     , RandomAccessIteratorOut target
2001     , _DifferenceTp length, Comparator comp
2002     , __gnu_parallel::sequential_tag)
2003 {
2004     typedef _DifferenceTp difference_type;
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 RandomAccessIteratorPairIterator
2020   , typename RandomAccessIteratorOut
2021   , typename _DifferenceTp
2022   , typename Comparator>
2023 RandomAccessIteratorOut
2024 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
2025     , RandomAccessIteratorPairIterator seqs_end
2026     , RandomAccessIteratorOut target
2027     , _DifferenceTp length, Comparator comp
2028     , __gnu_parallel::exact_tag tag)
2029 {
2030     typedef _DifferenceTp difference_type;
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           && ((sequence_index_t)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<RandomAccessIteratorPairIterator>
2052               ::value_type*, Comparator, _DifferenceTp>,
2053           static_cast<difference_type>(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 RandomAccessIteratorPairIterator
2063   , typename RandomAccessIteratorOut
2064   , typename _DifferenceTp
2065   , typename Comparator>
2066 RandomAccessIteratorOut
2067 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
2068     , RandomAccessIteratorPairIterator seqs_end
2069     , RandomAccessIteratorOut target
2070     , _DifferenceTp length, Comparator comp
2071     , sampling_tag tag)
2072 {
2073     typedef _DifferenceTp difference_type;
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           && ((sequence_index_t)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<RandomAccessIteratorPairIterator>
2095               ::value_type*, Comparator, _DifferenceTp>,
2096           static_cast<difference_type>(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 RandomAccessIteratorPairIterator
2107   , typename RandomAccessIteratorOut
2108   , typename _DifferenceTp
2109   , typename Comparator>
2110 RandomAccessIteratorOut
2111 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
2112     , RandomAccessIteratorPairIterator seqs_end
2113     , RandomAccessIteratorOut target
2114     , _DifferenceTp length, Comparator 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 RandomAccessIteratorPairIterator
2124   , typename RandomAccessIteratorOut
2125   , typename _DifferenceTp
2126   , typename Comparator>
2127 RandomAccessIteratorOut
2128 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
2129     , RandomAccessIteratorPairIterator seqs_end
2130     , RandomAccessIteratorOut target
2131     , _DifferenceTp length, Comparator 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 */