l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.3.3/include/parallel/multiway_merge.h

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