contrib/gcc-4.4/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 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
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       std::pair<RandomAccessIterator1, RandomAccessIterator1>* ne_seqs =
1309         static_cast<std::pair<RandomAccessIterator1, RandomAccessIterator1>*>(
1310         ::operator new(
1311             sizeof(std::pair<RandomAccessIterator1, RandomAccessIterator1>)
1312               * (seqs_end - seqs_begin)));
1313       int k = 0;
1314       difference_type total_length = 0;
1315       for (RandomAccessIteratorIterator raii = seqs_begin;
1316            raii != seqs_end; ++raii)
1317         {
1318           _DifferenceTp seq_length = _GLIBCXX_PARALLEL_LENGTH(*raii);
1319           if(seq_length > 0)
1320             {
1321               total_length += seq_length;
1322               //ne_seqs[k] = *raii;
1323               new(&(ne_seqs[k++]))
1324                 std::pair<RandomAccessIterator1, RandomAccessIterator1>(*raii);
1325             }
1326         }
1327
1328       _GLIBCXX_CALL(total_length)
1329
1330       length = std::min<_DifferenceTp>(length, total_length);
1331
1332       if (total_length == 0 || k == 0)
1333       {
1334         ::operator delete(ne_seqs);
1335         return target;
1336       }
1337
1338       std::vector<std::pair<difference_type, difference_type> >* pieces;
1339
1340       num_threads = static_cast<thread_index_t>
1341         (std::min<difference_type>(num_threads, total_length));
1342
1343 #     pragma omp parallel num_threads (num_threads)
1344         {
1345 #         pragma omp single
1346             {
1347               num_threads = omp_get_num_threads();
1348               // Thread t will have to merge pieces[iam][0..k - 1]
1349               pieces = new std::vector<
1350                   std::pair<difference_type, difference_type> >[num_threads];
1351               for (int s = 0; s < num_threads; ++s)
1352                 pieces[s].resize(k);
1353
1354               difference_type num_samples =
1355                   __gnu_parallel::_Settings::get().merge_oversampling *
1356                     num_threads;
1357
1358               splitter(ne_seqs, ne_seqs + k, length, total_length,
1359                        comp, pieces);
1360             } //single
1361
1362           thread_index_t iam = omp_get_thread_num();
1363
1364           difference_type target_position = 0;
1365
1366           for (int c = 0; c < k; ++c)
1367             target_position += pieces[iam][c].first;
1368
1369           std::pair<RandomAccessIterator1, RandomAccessIterator1>* chunks
1370             = new std::pair<RandomAccessIterator1, RandomAccessIterator1>[k];
1371
1372           for (int s = 0; s < k; ++s)
1373             {
1374               chunks[s] = std::make_pair(
1375                 ne_seqs[s].first + pieces[iam][s].first,
1376                 ne_seqs[s].first + pieces[iam][s].second);
1377             }
1378
1379           if(length > target_position)
1380             sequential_multiway_merge<stable, sentinels>(
1381               chunks, chunks + k, target + target_position,
1382                *(seqs_begin->second), length - target_position, comp);
1383
1384           delete[] chunks;
1385         } // parallel
1386
1387 #if _GLIBCXX_ASSERTIONS
1388       _GLIBCXX_PARALLEL_ASSERT(is_sorted(target, target + length, comp));
1389 #endif
1390
1391       k = 0;
1392       // Update ends of sequences.
1393       for (RandomAccessIteratorIterator raii = seqs_begin;
1394            raii != seqs_end; ++raii)
1395         {
1396           _DifferenceTp length = _GLIBCXX_PARALLEL_LENGTH(*raii);
1397           if(length > 0)
1398             (*raii).first += pieces[num_threads - 1][k++].second;
1399         }
1400
1401       delete[] pieces;
1402
1403       return target + length;
1404     }
1405
1406 /**
1407  * @brief Multiway Merge Frontend.
1408  *
1409  * Merge the sequences specified by seqs_begin and seqs_end into
1410  * target.  seqs_begin and seqs_end must point to a sequence of
1411  * pairs.  These pairs must contain an iterator to the beginning
1412  * of a sequence in their first entry and an iterator the end of
1413  * the same sequence in their second entry.
1414  *
1415  * Ties are broken arbitrarily.  See stable_multiway_merge for a variant
1416  * that breaks ties by sequence number but is slower.
1417  *
1418  * The first entries of the pairs (i.e. the begin iterators) will be moved
1419  * forward.
1420  *
1421  * The output sequence has to provide enough space for all elements
1422  * that are written to it.
1423  *
1424  * This function will merge the input sequences:
1425  *
1426  * - not stable
1427  * - parallel, depending on the input size and Settings
1428  * - using sampling for splitting
1429  * - not using sentinels
1430  *
1431  * Example:
1432  *
1433  * <pre>
1434  *   int sequences[10][10];
1435  *   for (int i = 0; i < 10; ++i)
1436  *     for (int j = 0; i < 10; ++j)
1437  *       sequences[i][j] = j;
1438  *
1439  *   int out[33];
1440  *   std::vector<std::pair<int*> > seqs;
1441  *   for (int i = 0; i < 10; ++i)
1442  *     { seqs.push(std::make_pair<int*>(sequences[i], sequences[i] + 10)) }
1443  *
1444  *   multiway_merge(seqs.begin(), seqs.end(), target, std::less<int>(), 33);
1445  * </pre>
1446  *
1447  * @see stable_multiway_merge
1448  *
1449  * @pre All input sequences must be sorted.
1450  * @pre Target must provide enough space to merge out length elements or
1451  *    the number of elements in all sequences, whichever is smaller.
1452  *
1453  * @post [target, return value) contains merged elements from the
1454  *    input sequences.
1455  * @post return value - target = min(length, number of elements in all
1456  *    sequences).
1457  *
1458  * @param RandomAccessIteratorPairIterator iterator over sequence
1459  *    of pairs of iterators
1460  * @param RandomAccessIteratorOut iterator over target sequence
1461  * @param _DifferenceTp difference type for the sequence
1462  * @param Comparator strict weak ordering type to compare elements
1463  *    in sequences
1464  *
1465  * @param seqs_begin  begin of sequence sequence
1466  * @param seqs_end    end of sequence sequence
1467  * @param target      target sequence to merge to.
1468  * @param comp        strict weak ordering to use for element comparison.
1469  * @param length Maximum length to merge, possibly larger than the
1470  * number of elements available.
1471  *
1472  * @return end iterator of output sequence
1473  */
1474 // multiway_merge
1475 // public interface
1476 template<
1477     typename RandomAccessIteratorPairIterator
1478   , typename RandomAccessIteratorOut
1479   , typename _DifferenceTp
1480   , typename Comparator>
1481 RandomAccessIteratorOut
1482 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1483     , RandomAccessIteratorPairIterator seqs_end
1484     , RandomAccessIteratorOut target
1485     , _DifferenceTp length, Comparator comp
1486     , __gnu_parallel::sequential_tag)
1487 {
1488   typedef _DifferenceTp difference_type;
1489   _GLIBCXX_CALL(seqs_end - seqs_begin)
1490
1491   // catch special case: no sequences
1492   if (seqs_begin == seqs_end)
1493     return target;
1494
1495   // Execute multiway merge *sequentially*.
1496   return sequential_multiway_merge
1497     </* stable = */ false, /* sentinels = */ false>
1498       (seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
1499 }
1500
1501 // public interface
1502 template<
1503     typename RandomAccessIteratorPairIterator
1504   , typename RandomAccessIteratorOut
1505   , typename _DifferenceTp
1506   , typename Comparator>
1507 RandomAccessIteratorOut
1508 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1509     , RandomAccessIteratorPairIterator seqs_end
1510     , RandomAccessIteratorOut target
1511     , _DifferenceTp length, Comparator comp
1512     , __gnu_parallel::exact_tag tag)
1513 {
1514     typedef _DifferenceTp difference_type;
1515     _GLIBCXX_CALL(seqs_end - seqs_begin)
1516
1517     // catch special case: no sequences
1518     if (seqs_begin == seqs_end)
1519       return target;
1520
1521     // Execute merge; maybe parallel, depending on the number of merged
1522     // elements and the number of sequences and global thresholds in
1523     // Settings.
1524     if ((seqs_end - seqs_begin > 1) &&
1525           _GLIBCXX_PARALLEL_CONDITION(
1526           ((seqs_end - seqs_begin) >=
1527              __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1528           && ((sequence_index_t)length >=
1529             __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1530       return parallel_multiway_merge
1531                     </* stable = */ false, /* sentinels = */ false>(
1532           seqs_begin, seqs_end, target,
1533           multiway_merge_exact_splitting</* stable = */ false,
1534             typename std::iterator_traits<RandomAccessIteratorPairIterator>
1535               ::value_type*, Comparator, _DifferenceTp>,
1536           static_cast<difference_type>(length), comp, tag.get_num_threads());
1537     else
1538       return sequential_multiway_merge
1539                       </* stable = */ false, /* sentinels = */ false>(
1540           seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
1541 }
1542
1543 // public interface
1544 template<
1545     typename RandomAccessIteratorPairIterator
1546   , typename RandomAccessIteratorOut
1547   , typename _DifferenceTp
1548   , typename Comparator>
1549 RandomAccessIteratorOut
1550 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1551     , RandomAccessIteratorPairIterator seqs_end
1552     , RandomAccessIteratorOut target
1553     , _DifferenceTp length, Comparator comp
1554     , __gnu_parallel::sampling_tag tag)
1555 {
1556     typedef _DifferenceTp difference_type;
1557     _GLIBCXX_CALL(seqs_end - seqs_begin)
1558
1559     // catch special case: no sequences
1560     if (seqs_begin == seqs_end)
1561       return target;
1562
1563     // Execute merge; maybe parallel, depending on the number of merged
1564     // elements and the number of sequences and global thresholds in
1565     // Settings.
1566     if ((seqs_end - seqs_begin > 1) &&
1567           _GLIBCXX_PARALLEL_CONDITION(
1568           ((seqs_end - seqs_begin) >=
1569              __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1570           && ((sequence_index_t)length >=
1571             __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1572       return parallel_multiway_merge
1573                     </* stable = */ false, /* sentinels = */ false>(
1574           seqs_begin, seqs_end,
1575           target,
1576           multiway_merge_exact_splitting</* stable = */ false,
1577             typename std::iterator_traits<RandomAccessIteratorPairIterator>
1578               ::value_type*, Comparator, _DifferenceTp>,
1579           static_cast<difference_type>(length), comp, tag.get_num_threads());
1580     else
1581       return sequential_multiway_merge
1582                       </* stable = */ false, /* sentinels = */ false>(
1583           seqs_begin, seqs_end,
1584           target, *(seqs_begin->second), length, comp);
1585 }
1586
1587 // public interface
1588 template<
1589     typename RandomAccessIteratorPairIterator
1590   , typename RandomAccessIteratorOut
1591   , typename _DifferenceTp
1592   , typename Comparator>
1593 RandomAccessIteratorOut
1594 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1595     , RandomAccessIteratorPairIterator seqs_end
1596     , RandomAccessIteratorOut target
1597     , _DifferenceTp length, Comparator comp
1598     , parallel_tag tag = parallel_tag(0))
1599 {
1600   return multiway_merge(seqs_begin, seqs_end, target, length, comp,
1601                          exact_tag(tag.get_num_threads()));
1602 }
1603
1604 // public interface
1605 template<
1606     typename RandomAccessIteratorPairIterator
1607   , typename RandomAccessIteratorOut
1608   , typename _DifferenceTp
1609   , typename Comparator>
1610 RandomAccessIteratorOut
1611 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1612     , RandomAccessIteratorPairIterator seqs_end
1613     , RandomAccessIteratorOut target
1614     , _DifferenceTp length, Comparator comp
1615     , default_parallel_tag tag)
1616 {
1617   return multiway_merge(seqs_begin, seqs_end, target, length, comp,
1618                          exact_tag(tag.get_num_threads()));
1619 }
1620
1621 // stable_multiway_merge
1622 // public interface
1623 template<
1624     typename RandomAccessIteratorPairIterator
1625   , typename RandomAccessIteratorOut
1626   , typename _DifferenceTp
1627   , typename Comparator>
1628 RandomAccessIteratorOut
1629 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1630     , RandomAccessIteratorPairIterator seqs_end
1631     , RandomAccessIteratorOut target
1632     , _DifferenceTp length, Comparator comp
1633     , __gnu_parallel::sequential_tag)
1634 {
1635     typedef _DifferenceTp difference_type;
1636     _GLIBCXX_CALL(seqs_end - seqs_begin)
1637
1638     // catch special case: no sequences
1639     if (seqs_begin == seqs_end)
1640       return target;
1641
1642     // Execute multiway merge *sequentially*.
1643     return sequential_multiway_merge
1644       </* stable = */ true, /* sentinels = */ false>
1645         (seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
1646 }
1647
1648 // public interface
1649 template<
1650     typename RandomAccessIteratorPairIterator
1651   , typename RandomAccessIteratorOut
1652   , typename _DifferenceTp
1653   , typename Comparator>
1654 RandomAccessIteratorOut
1655 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1656     , RandomAccessIteratorPairIterator seqs_end
1657     , RandomAccessIteratorOut target
1658     , _DifferenceTp length, Comparator comp
1659     , __gnu_parallel::exact_tag tag)
1660 {
1661     typedef _DifferenceTp difference_type;
1662     _GLIBCXX_CALL(seqs_end - seqs_begin)
1663
1664     // catch special case: no sequences
1665     if (seqs_begin == seqs_end)
1666       return target;
1667
1668     // Execute merge; maybe parallel, depending on the number of merged
1669     // elements and the number of sequences and global thresholds in
1670     // Settings.
1671     if ((seqs_end - seqs_begin > 1) &&
1672           _GLIBCXX_PARALLEL_CONDITION(
1673           ((seqs_end - seqs_begin) >=
1674             __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1675           && ((sequence_index_t)length >=
1676             __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1677       return parallel_multiway_merge
1678         </* stable = */ true, /* sentinels = */ false>(
1679           seqs_begin, seqs_end,
1680           target,
1681           multiway_merge_exact_splitting</* stable = */ true,
1682             typename std::iterator_traits<RandomAccessIteratorPairIterator>
1683               ::value_type*, Comparator, _DifferenceTp>,
1684           static_cast<difference_type>(length), comp, tag.get_num_threads());
1685     else
1686       return sequential_multiway_merge</* stable = */ true,
1687         /* sentinels = */ false>(
1688           seqs_begin, seqs_end,
1689           target, *(seqs_begin->second), length, comp);
1690 }
1691
1692 // public interface
1693 template<
1694     typename RandomAccessIteratorPairIterator
1695   , typename RandomAccessIteratorOut
1696   , typename _DifferenceTp
1697   , typename Comparator>
1698 RandomAccessIteratorOut
1699 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1700     , RandomAccessIteratorPairIterator seqs_end
1701     , RandomAccessIteratorOut target
1702     , _DifferenceTp length, Comparator comp
1703     , sampling_tag tag)
1704 {
1705     typedef _DifferenceTp difference_type;
1706     _GLIBCXX_CALL(seqs_end - seqs_begin)
1707
1708     // catch special case: no sequences
1709     if (seqs_begin == seqs_end)
1710       return target;
1711
1712     // Execute merge; maybe parallel, depending on the number of merged
1713     // elements and the number of sequences and global thresholds in
1714     // Settings.
1715     if ((seqs_end - seqs_begin > 1) &&
1716           _GLIBCXX_PARALLEL_CONDITION(
1717           ((seqs_end - seqs_begin) >=
1718             __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1719           && ((sequence_index_t)length >=
1720             __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1721       return parallel_multiway_merge
1722         </* stable = */ true, /* sentinels = */ false>(
1723           seqs_begin, seqs_end,
1724           target,
1725           multiway_merge_sampling_splitting</* stable = */ true,
1726             typename std::iterator_traits<RandomAccessIteratorPairIterator>
1727               ::value_type*, Comparator, _DifferenceTp>,
1728           static_cast<difference_type>(length), comp, tag.get_num_threads());
1729     else
1730       return sequential_multiway_merge
1731         </* stable = */ true, /* sentinels = */ false>(
1732           seqs_begin, seqs_end,
1733           target, *(seqs_begin->second), length, comp);
1734 }
1735
1736
1737 // public interface
1738 template<
1739     typename RandomAccessIteratorPairIterator
1740   , typename RandomAccessIteratorOut
1741   , typename _DifferenceTp
1742   , typename Comparator>
1743 RandomAccessIteratorOut
1744 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1745     , RandomAccessIteratorPairIterator seqs_end
1746     , RandomAccessIteratorOut target
1747     , _DifferenceTp length, Comparator comp
1748     , parallel_tag tag = parallel_tag(0))
1749 {
1750   return stable_multiway_merge(seqs_begin, seqs_end, target, length, comp,
1751                          exact_tag(tag.get_num_threads()));
1752 }
1753
1754 // public interface
1755 template<
1756     typename RandomAccessIteratorPairIterator
1757   , typename RandomAccessIteratorOut
1758   , typename _DifferenceTp
1759   , typename Comparator>
1760 RandomAccessIteratorOut
1761 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1762     , RandomAccessIteratorPairIterator seqs_end
1763     , RandomAccessIteratorOut target
1764     , _DifferenceTp length, Comparator comp
1765     , default_parallel_tag tag)
1766 {
1767   return stable_multiway_merge(seqs_begin, seqs_end, target, length, comp,
1768                          exact_tag(tag.get_num_threads()));
1769 }
1770
1771 /**
1772  * @brief Multiway Merge Frontend.
1773  *
1774  * Merge the sequences specified by seqs_begin and seqs_end into
1775  * target.  seqs_begin and seqs_end must point to a sequence of
1776  * pairs.  These pairs must contain an iterator to the beginning
1777  * of a sequence in their first entry and an iterator the end of
1778  * the same sequence in their second entry.
1779  *
1780  * Ties are broken arbitrarily.  See stable_multiway_merge for a variant
1781  * that breaks ties by sequence number but is slower.
1782  *
1783  * The first entries of the pairs (i.e. the begin iterators) will be moved
1784  * forward accordingly.
1785  *
1786  * The output sequence has to provide enough space for all elements
1787  * that are written to it.
1788  *
1789  * This function will merge the input sequences:
1790  *
1791  * - not stable
1792  * - parallel, depending on the input size and Settings
1793  * - using sampling for splitting
1794  * - using sentinels
1795  *
1796  * You have to take care that the element the end iterator points to is
1797  * readable and contains a value that is greater than any other non-sentinel
1798  * value in all sequences.
1799  *
1800  * Example:
1801  *
1802  * <pre>
1803  *   int sequences[10][11];
1804  *   for (int i = 0; i < 10; ++i)
1805  *     for (int j = 0; i < 11; ++j)
1806  *       sequences[i][j] = j; // last one is sentinel!
1807  *
1808  *   int out[33];
1809  *   std::vector<std::pair<int*> > seqs;
1810  *   for (int i = 0; i < 10; ++i)
1811  *     { seqs.push(std::make_pair<int*>(sequences[i], sequences[i] + 10)) }
1812  *
1813  *   multiway_merge(seqs.begin(), seqs.end(), target, std::less<int>(), 33);
1814  * </pre>
1815  *
1816  * @pre All input sequences must be sorted.
1817  * @pre Target must provide enough space to merge out length elements or
1818  *    the number of elements in all sequences, whichever is smaller.
1819  * @pre For each @c i, @c seqs_begin[i].second must be the end
1820  *    marker of the sequence, but also reference the one more sentinel
1821  *    element.
1822  *
1823  * @post [target, return value) contains merged elements from the
1824  *    input sequences.
1825  * @post return value - target = min(length, number of elements in all
1826  *    sequences).
1827  *
1828  * @see stable_multiway_merge_sentinels
1829  *
1830  * @param RandomAccessIteratorPairIterator iterator over sequence
1831  *    of pairs of iterators
1832  * @param RandomAccessIteratorOut iterator over target sequence
1833  * @param _DifferenceTp difference type for the sequence
1834  * @param Comparator strict weak ordering type to compare elements
1835  *    in sequences
1836  *
1837  * @param seqs_begin  begin of sequence sequence
1838  * @param seqs_end    end of sequence sequence
1839  * @param target      target sequence to merge to.
1840  * @param comp        strict weak ordering to use for element comparison.
1841  * @param length Maximum length to merge, possibly larger than the
1842  * number of elements available.
1843  *
1844  * @return end iterator of output sequence
1845  */
1846 // multiway_merge_sentinels
1847 // public interface
1848 template<
1849     typename RandomAccessIteratorPairIterator
1850   , typename RandomAccessIteratorOut
1851   , typename _DifferenceTp
1852   , typename Comparator>
1853 RandomAccessIteratorOut
1854 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1855     , RandomAccessIteratorPairIterator seqs_end
1856     , RandomAccessIteratorOut target
1857     , _DifferenceTp length, Comparator comp
1858     , __gnu_parallel::sequential_tag)
1859 {
1860     typedef _DifferenceTp difference_type;
1861     _GLIBCXX_CALL(seqs_end - seqs_begin)
1862
1863     // catch special case: no sequences
1864     if (seqs_begin == seqs_end)
1865       return target;
1866
1867     // Execute multiway merge *sequentially*.
1868     return sequential_multiway_merge
1869       </* stable = */ false, /* sentinels = */ true>
1870         (seqs_begin, seqs_end,
1871          target, *(seqs_begin->second), length, comp);
1872 }
1873
1874 // public interface
1875 template<
1876     typename RandomAccessIteratorPairIterator
1877   , typename RandomAccessIteratorOut
1878   , typename _DifferenceTp
1879   , typename Comparator>
1880 RandomAccessIteratorOut
1881 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1882     , RandomAccessIteratorPairIterator seqs_end
1883     , RandomAccessIteratorOut target
1884     , _DifferenceTp length, Comparator comp
1885     , __gnu_parallel::exact_tag tag)
1886 {
1887     typedef _DifferenceTp difference_type;
1888     _GLIBCXX_CALL(seqs_end - seqs_begin)
1889
1890     // catch special case: no sequences
1891     if (seqs_begin == seqs_end)
1892       return target;
1893
1894     // Execute merge; maybe parallel, depending on the number of merged
1895     // elements and the number of sequences and global thresholds in
1896     // Settings.
1897     if ((seqs_end - seqs_begin > 1) &&
1898           _GLIBCXX_PARALLEL_CONDITION(
1899           ((seqs_end - seqs_begin) >=
1900             __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1901           && ((sequence_index_t)length >=
1902             __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1903       return parallel_multiway_merge
1904         </* stable = */ false, /* sentinels = */ true>(
1905           seqs_begin, seqs_end,
1906           target,
1907           multiway_merge_exact_splitting</* stable = */ false,
1908             typename std::iterator_traits<RandomAccessIteratorPairIterator>
1909               ::value_type*, Comparator, _DifferenceTp>,
1910           static_cast<difference_type>(length), comp, tag.get_num_threads());
1911     else
1912       return sequential_multiway_merge
1913         </* stable = */ false, /* sentinels = */ true>(
1914           seqs_begin, seqs_end,
1915           target, *(seqs_begin->second), length, comp);
1916 }
1917
1918 // public interface
1919 template<
1920     typename RandomAccessIteratorPairIterator
1921   , typename RandomAccessIteratorOut
1922   , typename _DifferenceTp
1923   , typename Comparator>
1924 RandomAccessIteratorOut
1925 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1926     , RandomAccessIteratorPairIterator seqs_end
1927     , RandomAccessIteratorOut target
1928     , _DifferenceTp length, Comparator comp
1929     , sampling_tag tag)
1930 {
1931     typedef _DifferenceTp difference_type;
1932     _GLIBCXX_CALL(seqs_end - seqs_begin)
1933
1934     // catch special case: no sequences
1935     if (seqs_begin == seqs_end)
1936       return target;
1937
1938     // Execute merge; maybe parallel, depending on the number of merged
1939     // elements and the number of sequences and global thresholds in
1940     // Settings.
1941     if ((seqs_end - seqs_begin > 1) &&
1942           _GLIBCXX_PARALLEL_CONDITION(
1943           ((seqs_end - seqs_begin) >=
1944             __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1945           && ((sequence_index_t)length >=
1946             __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1947       return parallel_multiway_merge
1948         </* stable = */ false, /* sentinels = */ true>
1949           (seqs_begin, seqs_end, target,
1950           multiway_merge_sampling_splitting</* stable = */ false,
1951             typename std::iterator_traits<RandomAccessIteratorPairIterator>
1952               ::value_type*, Comparator, _DifferenceTp>,
1953           static_cast<difference_type>(length), comp, tag.get_num_threads());
1954     else
1955       return sequential_multiway_merge
1956         </* stable = */false, /* sentinels = */ true>(
1957           seqs_begin, seqs_end,
1958           target, *(seqs_begin->second), length, comp);
1959 }
1960
1961 // public interface
1962 template<
1963     typename RandomAccessIteratorPairIterator
1964   , typename RandomAccessIteratorOut
1965   , typename _DifferenceTp
1966   , typename Comparator>
1967 RandomAccessIteratorOut
1968 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1969     , RandomAccessIteratorPairIterator seqs_end
1970     , RandomAccessIteratorOut target
1971     , _DifferenceTp length, Comparator comp
1972     , parallel_tag tag = parallel_tag(0))
1973 {
1974   return multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp,
1975                          exact_tag(tag.get_num_threads()));
1976 }
1977
1978 // public interface
1979 template<
1980     typename RandomAccessIteratorPairIterator
1981   , typename RandomAccessIteratorOut
1982   , typename _DifferenceTp
1983   , typename Comparator>
1984 RandomAccessIteratorOut
1985 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1986     , RandomAccessIteratorPairIterator seqs_end
1987     , RandomAccessIteratorOut target
1988     , _DifferenceTp length, Comparator comp
1989     , default_parallel_tag tag)
1990 {
1991   return multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp,
1992                          exact_tag(tag.get_num_threads()));
1993 }
1994
1995 // stable_multiway_merge_sentinels
1996 // public interface
1997 template<
1998     typename RandomAccessIteratorPairIterator
1999   , typename RandomAccessIteratorOut
2000   , typename _DifferenceTp
2001   , typename Comparator>
2002 RandomAccessIteratorOut
2003 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
2004     , RandomAccessIteratorPairIterator seqs_end
2005     , RandomAccessIteratorOut target
2006     , _DifferenceTp length, Comparator comp
2007     , __gnu_parallel::sequential_tag)
2008 {
2009     typedef _DifferenceTp difference_type;
2010     _GLIBCXX_CALL(seqs_end - seqs_begin)
2011
2012     // catch special case: no sequences
2013     if (seqs_begin == seqs_end)
2014       return target;
2015
2016     // Execute multiway merge *sequentially*.
2017     return sequential_multiway_merge
2018       </* stable = */ true, /* sentinels = */ true>
2019         (seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
2020 }
2021
2022 // public interface
2023 template<
2024     typename RandomAccessIteratorPairIterator
2025   , typename RandomAccessIteratorOut
2026   , typename _DifferenceTp
2027   , typename Comparator>
2028 RandomAccessIteratorOut
2029 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
2030     , RandomAccessIteratorPairIterator seqs_end
2031     , RandomAccessIteratorOut target
2032     , _DifferenceTp length, Comparator comp
2033     , __gnu_parallel::exact_tag tag)
2034 {
2035     typedef _DifferenceTp difference_type;
2036     _GLIBCXX_CALL(seqs_end - seqs_begin)
2037
2038     // catch special case: no sequences
2039     if (seqs_begin == seqs_end)
2040       return target;
2041
2042     // Execute merge; maybe parallel, depending on the number of merged
2043     // elements and the number of sequences and global thresholds in
2044     // Settings.
2045     if ((seqs_end - seqs_begin > 1) &&
2046           _GLIBCXX_PARALLEL_CONDITION(
2047           ((seqs_end - seqs_begin) >=
2048           __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
2049           && ((sequence_index_t)length >=
2050           __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
2051       return parallel_multiway_merge
2052         </* stable = */ true, /* sentinels = */ true>(
2053           seqs_begin, seqs_end,
2054           target,
2055           multiway_merge_exact_splitting</* stable = */ true,
2056             typename std::iterator_traits<RandomAccessIteratorPairIterator>
2057               ::value_type*, Comparator, _DifferenceTp>,
2058           static_cast<difference_type>(length), comp, tag.get_num_threads());
2059     else
2060       return sequential_multiway_merge
2061         </* stable = */ true, /* sentinels = */ true>(
2062           seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
2063 }
2064
2065 // public interface
2066 template<
2067     typename RandomAccessIteratorPairIterator
2068   , typename RandomAccessIteratorOut
2069   , typename _DifferenceTp
2070   , typename Comparator>
2071 RandomAccessIteratorOut
2072 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
2073     , RandomAccessIteratorPairIterator seqs_end
2074     , RandomAccessIteratorOut target
2075     , _DifferenceTp length, Comparator comp
2076     , sampling_tag tag)
2077 {
2078     typedef _DifferenceTp difference_type;
2079     _GLIBCXX_CALL(seqs_end - seqs_begin)
2080
2081     // catch special case: no sequences
2082     if (seqs_begin == seqs_end)
2083       return target;
2084
2085     // Execute merge; maybe parallel, depending on the number of merged
2086     // elements and the number of sequences and global thresholds in
2087     // Settings.
2088     if ((seqs_end - seqs_begin > 1) &&
2089           _GLIBCXX_PARALLEL_CONDITION(
2090           ((seqs_end - seqs_begin) >=
2091             __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
2092           && ((sequence_index_t)length >=
2093             __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
2094       return parallel_multiway_merge
2095         </* stable = */ true, /* sentinels = */ true>(
2096           seqs_begin, seqs_end,
2097           target,
2098           multiway_merge_sampling_splitting</* stable = */ true,
2099             typename std::iterator_traits<RandomAccessIteratorPairIterator>
2100               ::value_type*, Comparator, _DifferenceTp>,
2101           static_cast<difference_type>(length), comp, tag.get_num_threads());
2102     else
2103       return sequential_multiway_merge
2104         </* stable = */ true, /* sentinels = */ true>(
2105           seqs_begin, seqs_end,
2106           target, *(seqs_begin->second), length, comp);
2107 }
2108
2109 // public interface
2110 template<
2111     typename RandomAccessIteratorPairIterator
2112   , typename RandomAccessIteratorOut
2113   , typename _DifferenceTp
2114   , typename Comparator>
2115 RandomAccessIteratorOut
2116 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
2117     , RandomAccessIteratorPairIterator seqs_end
2118     , RandomAccessIteratorOut target
2119     , _DifferenceTp length, Comparator comp
2120     , parallel_tag tag = parallel_tag(0))
2121 {
2122   return stable_multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp,
2123                          exact_tag(tag.get_num_threads()));
2124 }
2125
2126 // public interface
2127 template<
2128     typename RandomAccessIteratorPairIterator
2129   , typename RandomAccessIteratorOut
2130   , typename _DifferenceTp
2131   , typename Comparator>
2132 RandomAccessIteratorOut
2133 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
2134     , RandomAccessIteratorPairIterator seqs_end
2135     , RandomAccessIteratorOut target
2136     , _DifferenceTp length, Comparator comp
2137     , default_parallel_tag tag)
2138 {
2139   return stable_multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp,
2140                          exact_tag(tag.get_num_threads()));
2141 }
2142
2143 }; // namespace __gnu_parallel
2144
2145 #endif /* _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H */