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

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