l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.6/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       _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 = 0;
 506
 507       for (_SeqNumber __t = 0; __t < __k; ++__t)
 508         {
 509           if(!__arbitrary_element
 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       const _SeqNumber __k
1049         = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
1050
1051       const _ThreadIndex __num_threads = omp_get_num_threads();
1052
1053       const _DifferenceType __num_samples =
1054         __gnu_parallel::_Settings::get().merge_oversampling * __num_threads;
1055
1056       _ValueType* __samples = static_cast<_ValueType*>
1057         (::operator new(sizeof(_ValueType) * __k * __num_samples));
1058       // Sample.
1059       for (_SeqNumber __s = 0; __s < __k; ++__s)
1060         for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
1061           {
1062             _DifferenceType sample_index = static_cast<_DifferenceType>
1063               (_GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__s])
1064                * (double(__i + 1) / (__num_samples + 1))
1065                * (double(__length) / __total_length));
1066             new(&(__samples[__s * __num_samples + __i]))
1067               _ValueType(__seqs_begin[__s].first[sample_index]);
1068           }
1069
1070       // Sort stable or non-stable, depending on value of template parameter
1071       // "__stable".
1072       _SamplingSorter<__stable, _ValueType*, _Compare>()
1073         (__samples, __samples + (__num_samples * __k), __comp);
1074
1075       for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab)
1076         // For each slab / processor.
1077         for (_SeqNumber __seq = 0; __seq < __k; ++__seq)
1078           {
1079             // For each sequence.
1080             if (__slab > 0)
1081               __pieces[__slab][__seq].first = std::upper_bound
1082                 (__seqs_begin[__seq].first, __seqs_begin[__seq].second,
1083                  __samples[__num_samples * __k * __slab / __num_threads],
1084                  __comp)
1085                 - __seqs_begin[__seq].first;
1086             else
1087               // Absolute beginning.
1088               __pieces[__slab][__seq].first = 0;
1089             if ((__slab + 1) < __num_threads)
1090               __pieces[__slab][__seq].second = std::upper_bound
1091                 (__seqs_begin[__seq].first, __seqs_begin[__seq].second,
1092                  __samples[__num_samples * __k * (__slab + 1) / __num_threads],
1093                  __comp)
1094                 - __seqs_begin[__seq].first;
1095             else
1096               // Absolute end.
1097               __pieces[__slab][__seq].second =
1098                 _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]);
1099           }
1100
1101       for (_SeqNumber __s = 0; __s < __k; ++__s)
1102         for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
1103           __samples[__s * __num_samples + __i].~_ValueType();
1104       ::operator delete(__samples);
1105     }
1106
1107   /**
1108    * @brief Exact splitting for parallel multiway-merge routine.
1109    *
1110    * None of the passed sequences may be empty.
1111    */
1112   template<bool __stable,
1113            typename _RAIterIterator,
1114            typename _Compare,
1115            typename _DifferenceType>
1116     void
1117     multiway_merge_exact_splitting(_RAIterIterator __seqs_begin,
1118                                    _RAIterIterator __seqs_end,
1119                                    _DifferenceType __length,
1120                                    _DifferenceType __total_length,
1121                                    _Compare __comp,
1122        std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces)
1123     {
1124       typedef typename std::iterator_traits<_RAIterIterator>
1125         ::difference_type _SeqNumber;
1126       typedef typename std::iterator_traits<_RAIterIterator>
1127         ::value_type::first_type
1128         _RAIter1;
1129
1130       const bool __tight = (__total_length == __length);
1131
1132       // __k sequences.
1133       const _SeqNumber __k = __seqs_end - __seqs_begin;
1134
1135       const _ThreadIndex __num_threads = omp_get_num_threads();
1136
1137       // (Settings::multiway_merge_splitting
1138       //  == __gnu_parallel::_Settings::EXACT).
1139       std::vector<_RAIter1>* __offsets =
1140         new std::vector<_RAIter1>[__num_threads];
1141       std::vector<std::pair<_RAIter1, _RAIter1> > __se(__k);
1142
1143       copy(__seqs_begin, __seqs_end, __se.begin());
1144
1145       _DifferenceType* __borders =
1146         new _DifferenceType[__num_threads + 1];
1147       equally_split(__length, __num_threads, __borders);
1148
1149       for (_ThreadIndex __s = 0; __s < (__num_threads - 1); ++__s)
1150         {
1151           __offsets[__s].resize(__k);
1152           multiseq_partition(__se.begin(), __se.end(), __borders[__s + 1],
1153                              __offsets[__s].begin(), __comp);
1154
1155           // Last one also needed and available.
1156           if (!__tight)
1157             {
1158               __offsets[__num_threads - 1].resize(__k);
1159               multiseq_partition(__se.begin(), __se.end(),
1160                                  _DifferenceType(__length),
1161                                  __offsets[__num_threads - 1].begin(),
1162                                  __comp);
1163             }
1164         }
1165       delete[] __borders;
1166
1167       for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab)
1168         {
1169           // For each slab / processor.
1170           for (_SeqNumber __seq = 0; __seq < __k; ++__seq)
1171             {
1172               // For each sequence.
1173               if (__slab == 0)
1174                 {
1175                   // Absolute beginning.
1176                   __pieces[__slab][__seq].first = 0;
1177                 }
1178               else
1179                 __pieces[__slab][__seq].first =
1180                   __pieces[__slab - 1][__seq].second;
1181               if (!__tight || __slab < (__num_threads - 1))
1182                 __pieces[__slab][__seq].second =
1183                   __offsets[__slab][__seq] - __seqs_begin[__seq].first;
1184               else
1185                 {
1186                   // __slab == __num_threads - 1
1187                   __pieces[__slab][__seq].second =
1188                     _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]);
1189                 }
1190             }
1191         }
1192       delete[] __offsets;
1193     }
1194
1195   /** @brief Parallel multi-way merge routine.
1196    *
1197    * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor
1198    * and runtime settings.
1199    *
1200    * Must not be called if the number of sequences is 1.
1201    *
1202    * @param _Splitter functor to split input (either __exact or sampling based)
1203    *
1204    * @param __seqs_begin Begin iterator of iterator pair input sequence.
1205    * @param __seqs_end End iterator of iterator pair input sequence.
1206    * @param __target Begin iterator of output sequence.
1207    * @param __comp Comparator.
1208    * @param __length Maximum length to merge, possibly larger than the
1209    * number of elements available.
1210    * @param __stable Stable merging incurs a performance penalty.
1211    * @param __sentinel Ignored.
1212    * @return End iterator of output sequence.
1213    */
1214   template<bool __stable,
1215            bool __sentinels,
1216            typename _RAIterIterator,
1217            typename _RAIter3,
1218            typename _DifferenceTp,
1219            typename _Splitter,
1220            typename _Compare>
1221     _RAIter3
1222     parallel_multiway_merge(_RAIterIterator __seqs_begin,
1223                             _RAIterIterator __seqs_end,
1224                             _RAIter3 __target,
1225                             _Splitter __splitter,
1226                             _DifferenceTp __length,
1227                             _Compare __comp,
1228                             _ThreadIndex __num_threads)
1229       {
1230 #if _GLIBCXX_ASSERTIONS
1231         _GLIBCXX_PARALLEL_ASSERT(__seqs_end - __seqs_begin > 1);
1232 #endif
1233
1234         _GLIBCXX_CALL(__length)
1235
1236         typedef _DifferenceTp _DifferenceType;
1237         typedef typename std::iterator_traits<_RAIterIterator>
1238           ::difference_type _SeqNumber;
1239         typedef typename std::iterator_traits<_RAIterIterator>
1240           ::value_type::first_type
1241           _RAIter1;
1242         typedef typename
1243           std::iterator_traits<_RAIter1>::value_type _ValueType;
1244
1245         // Leave only non-empty sequences.
1246         typedef std::pair<_RAIter1, _RAIter1> seq_type;
1247         seq_type* __ne_seqs = new seq_type[__seqs_end - __seqs_begin];
1248         _SeqNumber __k = 0;
1249         _DifferenceType __total_length = 0;
1250         for (_RAIterIterator __raii = __seqs_begin;
1251              __raii != __seqs_end; ++__raii)
1252           {
1253             _DifferenceTp __seq_length = _GLIBCXX_PARALLEL_LENGTH(*__raii);
1254             if(__seq_length > 0)
1255               {
1256                 __total_length += __seq_length;
1257                 __ne_seqs[__k++] = *__raii;
1258               }
1259           }
1260
1261         _GLIBCXX_CALL(__total_length)
1262
1263         __length = std::min<_DifferenceTp>(__length, __total_length);
1264
1265         if (__total_length == 0 || __k == 0)
1266           {
1267             delete[] __ne_seqs;
1268             return __target;
1269           }
1270
1271         std::vector<std::pair<_DifferenceType, _DifferenceType> >* __pieces;
1272
1273         __num_threads = static_cast<_ThreadIndex>
1274           (std::min<_DifferenceType>(__num_threads, __total_length));
1275
1276 #       pragma omp parallel num_threads (__num_threads)
1277         {
1278 #         pragma omp single
1279           {
1280             __num_threads = omp_get_num_threads();
1281             // Thread __t will have to merge pieces[__iam][0..__k - 1]
1282             __pieces = new std::vector<
1283             std::pair<_DifferenceType, _DifferenceType> >[__num_threads];
1284             for (_ThreadIndex __s = 0; __s < __num_threads; ++__s)
1285               __pieces[__s].resize(__k);
1286
1287             _DifferenceType __num_samples =
1288               __gnu_parallel::_Settings::get().merge_oversampling
1289               * __num_threads;
1290
1291             __splitter(__ne_seqs, __ne_seqs + __k, __length, __total_length,
1292                        __comp, __pieces);
1293           } //single
1294
1295           _ThreadIndex __iam = omp_get_thread_num();
1296
1297           _DifferenceType __target_position = 0;
1298
1299           for (_SeqNumber __c = 0; __c < __k; ++__c)
1300             __target_position += __pieces[__iam][__c].first;
1301
1302           seq_type* __chunks = new seq_type[__k];
1303
1304           for (_SeqNumber __s = 0; __s < __k; ++__s)
1305             __chunks[__s] = std::make_pair(__ne_seqs[__s].first
1306                                            + __pieces[__iam][__s].first,
1307                                            __ne_seqs[__s].first
1308                                            + __pieces[__iam][__s].second);
1309
1310           if(__length > __target_position)
1311             __sequential_multiway_merge<__stable, __sentinels>
1312               (__chunks, __chunks + __k, __target + __target_position,
1313                *(__seqs_begin->second), __length - __target_position, __comp);
1314
1315           delete[] __chunks;
1316         } // parallel
1317
1318 #if _GLIBCXX_ASSERTIONS
1319         _GLIBCXX_PARALLEL_ASSERT(
1320           __is_sorted(__target, __target + __length, __comp));
1321 #endif
1322
1323         __k = 0;
1324         // Update ends of sequences.
1325         for (_RAIterIterator __raii = __seqs_begin;
1326              __raii != __seqs_end; ++__raii)
1327           {
1328             _DifferenceTp __length = _GLIBCXX_PARALLEL_LENGTH(*__raii);
1329             if(__length > 0)
1330               (*__raii).first += __pieces[__num_threads - 1][__k++].second;
1331           }
1332
1333         delete[] __pieces;
1334         delete[] __ne_seqs;
1335
1336         return __target + __length;
1337       }
1338
1339   /**
1340    * @brief Multiway Merge Frontend.
1341    *
1342    * Merge the sequences specified by seqs_begin and __seqs_end into
1343    * __target.  __seqs_begin and __seqs_end must point to a sequence of
1344    * pairs.  These pairs must contain an iterator to the beginning
1345    * of a sequence in their first entry and an iterator the _M_end of
1346    * the same sequence in their second entry.
1347    *
1348    * Ties are broken arbitrarily.  See stable_multiway_merge for a variant
1349    * that breaks ties by sequence number but is slower.
1350    *
1351    * The first entries of the pairs (i.e. the begin iterators) will be moved
1352    * forward.
1353    *
1354    * The output sequence has to provide enough space for all elements
1355    * that are written to it.
1356    *
1357    * This function will merge the input sequences:
1358    *
1359    * - not stable
1360    * - parallel, depending on the input size and Settings
1361    * - using sampling for splitting
1362    * - not using sentinels
1363    *
1364    * Example:
1365    *
1366    * <pre>
1367    *   int sequences[10][10];
1368    *   for (int __i = 0; __i < 10; ++__i)
1369    *     for (int __j = 0; __i < 10; ++__j)
1370    *       sequences[__i][__j] = __j;
1371    *
1372    *   int __out[33];
1373    *   std::vector<std::pair<int*> > seqs;
1374    *   for (int __i = 0; __i < 10; ++__i)
1375    *     { seqs.push(std::make_pair<int*>(sequences[__i],
1376    *                                      sequences[__i] + 10)) }
1377    *
1378    *   multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33);
1379    * </pre>
1380    *
1381    * @see stable_multiway_merge
1382    *
1383    * @pre All input sequences must be sorted.
1384    * @pre Target must provide enough space to merge out length elements or
1385    *    the number of elements in all sequences, whichever is smaller.
1386    *
1387    * @post [__target, return __value) contains merged __elements from the
1388    *    input sequences.
1389    * @post return __value - __target = min(__length, number of elements in all
1390    *    sequences).
1391    *
1392    * @param _RAIterPairIterator iterator over sequence
1393    *    of pairs of iterators
1394    * @param _RAIterOut iterator over target sequence
1395    * @param _DifferenceTp difference type for the sequence
1396    * @param _Compare strict weak ordering type to compare elements
1397    *    in sequences
1398    *
1399    * @param __seqs_begin  __begin of sequence __sequence
1400    * @param __seqs_end    _M_end of sequence __sequence
1401    * @param __target      target sequence to merge to.
1402    * @param __comp        strict weak ordering to use for element comparison.
1403    * @param __length Maximum length to merge, possibly larger than the
1404    * number of elements available.
1405    *
1406    * @return _M_end iterator of output sequence
1407    */
1408   // multiway_merge
1409   // public interface
1410   template<typename _RAIterPairIterator,
1411            typename _RAIterOut,
1412            typename _DifferenceTp,
1413            typename _Compare>
1414     _RAIterOut
1415     multiway_merge(_RAIterPairIterator __seqs_begin,
1416                    _RAIterPairIterator __seqs_end,
1417                    _RAIterOut __target,
1418                    _DifferenceTp __length, _Compare __comp,
1419                    __gnu_parallel::sequential_tag)
1420     {
1421       typedef _DifferenceTp _DifferenceType;
1422       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1423
1424       // catch special case: no sequences
1425       if (__seqs_begin == __seqs_end)
1426         return __target;
1427
1428       // Execute multiway merge *sequentially*.
1429       return __sequential_multiway_merge
1430         </* __stable = */ false, /* __sentinels = */ false>
1431         (__seqs_begin, __seqs_end, __target,
1432          *(__seqs_begin->second), __length, __comp);
1433     }
1434
1435   // public interface
1436   template<typename _RAIterPairIterator,
1437            typename _RAIterOut,
1438            typename _DifferenceTp,
1439            typename _Compare>
1440     _RAIterOut
1441     multiway_merge(_RAIterPairIterator __seqs_begin,
1442                    _RAIterPairIterator __seqs_end,
1443                    _RAIterOut __target,
1444                    _DifferenceTp __length, _Compare __comp,
1445                    __gnu_parallel::exact_tag __tag)
1446     {
1447       typedef _DifferenceTp _DifferenceType;
1448       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1449
1450       // catch special case: no sequences
1451       if (__seqs_begin == __seqs_end)
1452         return __target;
1453
1454       // Execute merge; maybe parallel, depending on the number of merged
1455       // elements and the number of sequences and global thresholds in
1456       // Settings.
1457       if ((__seqs_end - __seqs_begin > 1)
1458           && _GLIBCXX_PARALLEL_CONDITION(
1459             ((__seqs_end - __seqs_begin) >=
1460                __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1461             && ((_SequenceIndex)__length >=
1462               __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1463         return parallel_multiway_merge
1464           </* __stable = */ false, /* __sentinels = */ false>
1465           (__seqs_begin, __seqs_end, __target,
1466            multiway_merge_exact_splitting</* __stable = */ false,
1467            typename std::iterator_traits<_RAIterPairIterator>
1468            ::value_type*, _Compare, _DifferenceTp>,
1469            static_cast<_DifferenceType>(__length), __comp,
1470            __tag.__get_num_threads());
1471       else
1472         return __sequential_multiway_merge
1473           </* __stable = */ false, /* __sentinels = */ false>
1474           (__seqs_begin, __seqs_end, __target,
1475            *(__seqs_begin->second), __length, __comp);
1476     }
1477
1478   // public interface
1479   template<typename _RAIterPairIterator,
1480            typename _RAIterOut,
1481            typename _DifferenceTp,
1482            typename _Compare>
1483     _RAIterOut
1484     multiway_merge(_RAIterPairIterator __seqs_begin,
1485                    _RAIterPairIterator __seqs_end,
1486                    _RAIterOut __target,
1487                    _DifferenceTp __length, _Compare __comp,
1488                    __gnu_parallel::sampling_tag __tag)
1489     {
1490       typedef _DifferenceTp _DifferenceType;
1491       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1492
1493       // catch special case: no sequences
1494       if (__seqs_begin == __seqs_end)
1495         return __target;
1496
1497       // Execute merge; maybe parallel, depending on the number of merged
1498       // elements and the number of sequences and global thresholds in
1499       // Settings.
1500       if ((__seqs_end - __seqs_begin > 1)
1501           && _GLIBCXX_PARALLEL_CONDITION(
1502             ((__seqs_end - __seqs_begin) >=
1503                __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1504             && ((_SequenceIndex)__length >=
1505               __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1506         return parallel_multiway_merge
1507           </* __stable = */ false, /* __sentinels = */ false>
1508           (__seqs_begin, __seqs_end, __target,
1509            multiway_merge_exact_splitting</* __stable = */ false,
1510            typename std::iterator_traits<_RAIterPairIterator>
1511            ::value_type*, _Compare, _DifferenceTp>,
1512            static_cast<_DifferenceType>(__length), __comp,
1513            __tag.__get_num_threads());
1514       else
1515         return __sequential_multiway_merge
1516           </* __stable = */ false, /* __sentinels = */ false>
1517           (__seqs_begin, __seqs_end, __target,
1518            *(__seqs_begin->second), __length, __comp);
1519     }
1520
1521   // public interface
1522   template<typename _RAIterPairIterator,
1523            typename _RAIterOut,
1524            typename _DifferenceTp,
1525            typename _Compare>
1526     _RAIterOut
1527     multiway_merge(_RAIterPairIterator __seqs_begin,
1528                    _RAIterPairIterator __seqs_end,
1529                    _RAIterOut __target,
1530                    _DifferenceTp __length, _Compare __comp,
1531                    parallel_tag __tag = parallel_tag(0))
1532     { return multiway_merge(__seqs_begin, __seqs_end, __target, __length,
1533                             __comp, exact_tag(__tag.__get_num_threads())); }
1534
1535   // public interface
1536   template<typename _RAIterPairIterator,
1537            typename _RAIterOut,
1538            typename _DifferenceTp,
1539            typename _Compare>
1540     _RAIterOut
1541     multiway_merge(_RAIterPairIterator __seqs_begin,
1542                    _RAIterPairIterator __seqs_end,
1543                    _RAIterOut __target,
1544                    _DifferenceTp __length, _Compare __comp,
1545                    default_parallel_tag __tag)
1546     { return multiway_merge(__seqs_begin, __seqs_end, __target, __length,
1547                             __comp, exact_tag(__tag.__get_num_threads())); }
1548
1549   // stable_multiway_merge
1550   // public interface
1551   template<typename _RAIterPairIterator,
1552            typename _RAIterOut,
1553            typename _DifferenceTp,
1554            typename _Compare>
1555     _RAIterOut
1556     stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1557                           _RAIterPairIterator __seqs_end,
1558                           _RAIterOut __target,
1559                           _DifferenceTp __length, _Compare __comp,
1560                           __gnu_parallel::sequential_tag)
1561     {
1562       typedef _DifferenceTp _DifferenceType;
1563       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1564
1565       // catch special case: no sequences
1566       if (__seqs_begin == __seqs_end)
1567         return __target;
1568
1569       // Execute multiway merge *sequentially*.
1570       return __sequential_multiway_merge
1571         </* __stable = */ true, /* __sentinels = */ false>
1572           (__seqs_begin, __seqs_end, __target,
1573            *(__seqs_begin->second), __length, __comp);
1574     }
1575
1576   // public interface
1577   template<typename _RAIterPairIterator,
1578            typename _RAIterOut,
1579            typename _DifferenceTp,
1580            typename _Compare>
1581     _RAIterOut
1582     stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1583                           _RAIterPairIterator __seqs_end,
1584                           _RAIterOut __target,
1585                           _DifferenceTp __length, _Compare __comp,
1586                           __gnu_parallel::exact_tag __tag)
1587     {
1588       typedef _DifferenceTp _DifferenceType;
1589       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1590
1591       // catch special case: no sequences
1592       if (__seqs_begin == __seqs_end)
1593         return __target;
1594
1595       // Execute merge; maybe parallel, depending on the number of merged
1596       // elements and the number of sequences and global thresholds in
1597       // Settings.
1598       if ((__seqs_end - __seqs_begin > 1)
1599           && _GLIBCXX_PARALLEL_CONDITION(
1600             ((__seqs_end - __seqs_begin) >=
1601               __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1602             && ((_SequenceIndex)__length >=
1603               __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1604         return parallel_multiway_merge
1605           </* __stable = */ true, /* __sentinels = */ false>
1606           (__seqs_begin, __seqs_end, __target,
1607            multiway_merge_exact_splitting</* __stable = */ true,
1608            typename std::iterator_traits<_RAIterPairIterator>
1609            ::value_type*, _Compare, _DifferenceTp>,
1610            static_cast<_DifferenceType>(__length), __comp,
1611            __tag.__get_num_threads());
1612       else
1613         return __sequential_multiway_merge
1614           </* __stable = */ true, /* __sentinels = */ false>
1615           (__seqs_begin, __seqs_end, __target,
1616            *(__seqs_begin->second), __length, __comp);
1617     }
1618
1619   // public interface
1620   template<typename _RAIterPairIterator,
1621            typename _RAIterOut,
1622            typename _DifferenceTp,
1623            typename _Compare>
1624     _RAIterOut
1625     stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1626                           _RAIterPairIterator __seqs_end,
1627                           _RAIterOut __target,
1628                           _DifferenceTp __length, _Compare __comp,
1629                           sampling_tag __tag)
1630     {
1631       typedef _DifferenceTp _DifferenceType;
1632       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1633
1634       // catch special case: no sequences
1635       if (__seqs_begin == __seqs_end)
1636         return __target;
1637
1638       // Execute merge; maybe parallel, depending on the number of merged
1639       // elements and the number of sequences and global thresholds in
1640       // Settings.
1641       if ((__seqs_end - __seqs_begin > 1)
1642           && _GLIBCXX_PARALLEL_CONDITION(
1643             ((__seqs_end - __seqs_begin) >=
1644               __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1645             && ((_SequenceIndex)__length >=
1646               __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1647         return parallel_multiway_merge
1648           </* __stable = */ true, /* __sentinels = */ false>
1649           (__seqs_begin, __seqs_end, __target,
1650            multiway_merge_sampling_splitting</* __stable = */ true,
1651            typename std::iterator_traits<_RAIterPairIterator>
1652            ::value_type*, _Compare, _DifferenceTp>,
1653            static_cast<_DifferenceType>(__length), __comp,
1654            __tag.__get_num_threads());
1655       else
1656         return __sequential_multiway_merge
1657           </* __stable = */ true, /* __sentinels = */ false>
1658           (__seqs_begin, __seqs_end, __target,
1659            *(__seqs_begin->second), __length, __comp);
1660     }
1661
1662   // public interface
1663   template<typename _RAIterPairIterator,
1664            typename _RAIterOut,
1665            typename _DifferenceTp,
1666            typename _Compare>
1667     _RAIterOut
1668     stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1669                           _RAIterPairIterator __seqs_end,
1670                           _RAIterOut __target,
1671                           _DifferenceTp __length, _Compare __comp,
1672                           parallel_tag __tag = parallel_tag(0))
1673     {
1674       return stable_multiway_merge
1675         (__seqs_begin, __seqs_end, __target, __length, __comp,
1676          exact_tag(__tag.__get_num_threads()));
1677     }
1678
1679   // public interface
1680   template<typename _RAIterPairIterator,
1681            typename _RAIterOut,
1682            typename _DifferenceTp,
1683            typename _Compare>
1684     _RAIterOut
1685     stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1686                           _RAIterPairIterator __seqs_end,
1687                           _RAIterOut __target,
1688                           _DifferenceTp __length, _Compare __comp,
1689                           default_parallel_tag __tag)
1690     {
1691       return stable_multiway_merge
1692         (__seqs_begin, __seqs_end, __target, __length, __comp,
1693          exact_tag(__tag.__get_num_threads()));
1694     }
1695
1696   /**
1697    * @brief Multiway Merge Frontend.
1698    *
1699    * Merge the sequences specified by seqs_begin and __seqs_end into
1700    * __target.  __seqs_begin and __seqs_end must point to a sequence of
1701    * pairs.  These pairs must contain an iterator to the beginning
1702    * of a sequence in their first entry and an iterator the _M_end of
1703    * the same sequence in their second entry.
1704    *
1705    * Ties are broken arbitrarily.  See stable_multiway_merge for a variant
1706    * that breaks ties by sequence number but is slower.
1707    *
1708    * The first entries of the pairs (i.e. the begin iterators) will be moved
1709    * forward accordingly.
1710    *
1711    * The output sequence has to provide enough space for all elements
1712    * that are written to it.
1713    *
1714    * This function will merge the input sequences:
1715    *
1716    * - not stable
1717    * - parallel, depending on the input size and Settings
1718    * - using sampling for splitting
1719    * - using sentinels
1720    *
1721    * You have to take care that the element the _M_end iterator points to is
1722    * readable and contains a value that is greater than any other non-sentinel
1723    * value in all sequences.
1724    *
1725    * Example:
1726    *
1727    * <pre>
1728    *   int sequences[10][11];
1729    *   for (int __i = 0; __i < 10; ++__i)
1730    *     for (int __j = 0; __i < 11; ++__j)
1731    *       sequences[__i][__j] = __j; // __last one is sentinel!
1732    *
1733    *   int __out[33];
1734    *   std::vector<std::pair<int*> > seqs;
1735    *   for (int __i = 0; __i < 10; ++__i)
1736    *     { seqs.push(std::make_pair<int*>(sequences[__i],
1737    *                                      sequences[__i] + 10)) }
1738    *
1739    *   multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33);
1740    * </pre>
1741    *
1742    * @pre All input sequences must be sorted.
1743    * @pre Target must provide enough space to merge out length elements or
1744    *    the number of elements in all sequences, whichever is smaller.
1745    * @pre For each @c __i, @c __seqs_begin[__i].second must be the end
1746    *    marker of the sequence, but also reference the one more __sentinel
1747    *    element.
1748    *
1749    * @post [__target, return __value) contains merged __elements from the
1750    *    input sequences.
1751    * @post return __value - __target = min(__length, number of elements in all
1752    *    sequences).
1753    *
1754    * @see stable_multiway_merge_sentinels
1755    *
1756    * @param _RAIterPairIterator iterator over sequence
1757    *    of pairs of iterators
1758    * @param _RAIterOut iterator over target sequence
1759    * @param _DifferenceTp difference type for the sequence
1760    * @param _Compare strict weak ordering type to compare elements
1761    *    in sequences
1762    *
1763    * @param __seqs_begin  __begin of sequence __sequence
1764    * @param __seqs_end    _M_end of sequence __sequence
1765    * @param __target      target sequence to merge to.
1766    * @param __comp        strict weak ordering to use for element comparison.
1767    * @param __length Maximum length to merge, possibly larger than the
1768    * number of elements available.
1769    *
1770    * @return _M_end iterator of output sequence
1771    */
1772   // multiway_merge_sentinels
1773   // public interface
1774   template<typename _RAIterPairIterator,
1775            typename _RAIterOut,
1776            typename _DifferenceTp,
1777            typename _Compare>
1778     _RAIterOut
1779     multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1780                              _RAIterPairIterator __seqs_end,
1781                              _RAIterOut __target,
1782                              _DifferenceTp __length, _Compare __comp,
1783                              __gnu_parallel::sequential_tag)
1784     {
1785       typedef _DifferenceTp _DifferenceType;
1786       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1787
1788       // catch special case: no sequences
1789       if (__seqs_begin == __seqs_end)
1790         return __target;
1791
1792       // Execute multiway merge *sequentially*.
1793       return __sequential_multiway_merge
1794         </* __stable = */ false, /* __sentinels = */ true>
1795           (__seqs_begin, __seqs_end,
1796            __target, *(__seqs_begin->second), __length, __comp);
1797     }
1798
1799   // public interface
1800   template<typename _RAIterPairIterator,
1801            typename _RAIterOut,
1802            typename _DifferenceTp,
1803            typename _Compare>
1804     _RAIterOut
1805     multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1806                              _RAIterPairIterator __seqs_end,
1807                              _RAIterOut __target,
1808                              _DifferenceTp __length, _Compare __comp,
1809                              __gnu_parallel::exact_tag __tag)
1810     {
1811       typedef _DifferenceTp _DifferenceType;
1812       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1813
1814       // catch special case: no sequences
1815       if (__seqs_begin == __seqs_end)
1816         return __target;
1817
1818       // Execute merge; maybe parallel, depending on the number of merged
1819       // elements and the number of sequences and global thresholds in
1820       // Settings.
1821       if ((__seqs_end - __seqs_begin > 1)
1822           && _GLIBCXX_PARALLEL_CONDITION(
1823             ((__seqs_end - __seqs_begin) >=
1824               __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1825             && ((_SequenceIndex)__length >=
1826               __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1827         return parallel_multiway_merge
1828           </* __stable = */ false, /* __sentinels = */ true>
1829           (__seqs_begin, __seqs_end, __target,
1830            multiway_merge_exact_splitting</* __stable = */ false,
1831            typename std::iterator_traits<_RAIterPairIterator>
1832            ::value_type*, _Compare, _DifferenceTp>,
1833            static_cast<_DifferenceType>(__length), __comp,
1834            __tag.__get_num_threads());
1835       else
1836         return __sequential_multiway_merge
1837           </* __stable = */ false, /* __sentinels = */ true>
1838           (__seqs_begin, __seqs_end, __target,
1839            *(__seqs_begin->second), __length, __comp);
1840     }
1841
1842   // public interface
1843   template<typename _RAIterPairIterator,
1844            typename _RAIterOut,
1845            typename _DifferenceTp,
1846            typename _Compare>
1847     _RAIterOut
1848     multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1849                              _RAIterPairIterator __seqs_end,
1850                              _RAIterOut __target,
1851                              _DifferenceTp __length, _Compare __comp,
1852                              sampling_tag __tag)
1853     {
1854       typedef _DifferenceTp _DifferenceType;
1855       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1856
1857       // catch special case: no sequences
1858       if (__seqs_begin == __seqs_end)
1859         return __target;
1860
1861       // Execute merge; maybe parallel, depending on the number of merged
1862       // elements and the number of sequences and global thresholds in
1863       // Settings.
1864       if ((__seqs_end - __seqs_begin > 1)
1865           && _GLIBCXX_PARALLEL_CONDITION(
1866             ((__seqs_end - __seqs_begin) >=
1867               __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1868             && ((_SequenceIndex)__length >=
1869               __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1870         return parallel_multiway_merge
1871           </* __stable = */ false, /* __sentinels = */ true>
1872           (__seqs_begin, __seqs_end, __target,
1873            multiway_merge_sampling_splitting</* __stable = */ false,
1874            typename std::iterator_traits<_RAIterPairIterator>
1875            ::value_type*, _Compare, _DifferenceTp>,
1876            static_cast<_DifferenceType>(__length), __comp,
1877            __tag.__get_num_threads());
1878       else
1879         return __sequential_multiway_merge
1880           </* __stable = */false, /* __sentinels = */ true>(
1881             __seqs_begin, __seqs_end, __target,
1882             *(__seqs_begin->second), __length, __comp);
1883     }
1884
1885   // public interface
1886   template<typename _RAIterPairIterator,
1887            typename _RAIterOut,
1888            typename _DifferenceTp,
1889            typename _Compare>
1890     _RAIterOut
1891     multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1892                              _RAIterPairIterator __seqs_end,
1893                              _RAIterOut __target,
1894                              _DifferenceTp __length, _Compare __comp,
1895                              parallel_tag __tag = parallel_tag(0))
1896     {
1897       return multiway_merge_sentinels
1898         (__seqs_begin, __seqs_end, __target, __length, __comp,
1899          exact_tag(__tag.__get_num_threads()));
1900     }
1901
1902   // public interface
1903   template<typename _RAIterPairIterator,
1904            typename _RAIterOut,
1905            typename _DifferenceTp,
1906            typename _Compare>
1907     _RAIterOut
1908     multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1909                              _RAIterPairIterator __seqs_end,
1910                              _RAIterOut __target,
1911                              _DifferenceTp __length, _Compare __comp,
1912                              default_parallel_tag __tag)
1913     {
1914       return multiway_merge_sentinels
1915         (__seqs_begin, __seqs_end, __target, __length, __comp,
1916          exact_tag(__tag.__get_num_threads()));
1917     }
1918
1919   // stable_multiway_merge_sentinels
1920   // public interface
1921   template<typename _RAIterPairIterator,
1922            typename _RAIterOut,
1923            typename _DifferenceTp,
1924            typename _Compare>
1925     _RAIterOut
1926     stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1927                                     _RAIterPairIterator __seqs_end,
1928                                     _RAIterOut __target,
1929                                     _DifferenceTp __length, _Compare __comp,
1930                                     __gnu_parallel::sequential_tag)
1931     {
1932       typedef _DifferenceTp _DifferenceType;
1933       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1934
1935       // catch special case: no sequences
1936       if (__seqs_begin == __seqs_end)
1937         return __target;
1938
1939       // Execute multiway merge *sequentially*.
1940       return __sequential_multiway_merge
1941         </* __stable = */ true, /* __sentinels = */ true>
1942         (__seqs_begin, __seqs_end, __target,
1943          *(__seqs_begin->second), __length, __comp);
1944     }
1945
1946   // public interface
1947   template<typename _RAIterPairIterator,
1948            typename _RAIterOut,
1949            typename _DifferenceTp,
1950            typename _Compare>
1951     _RAIterOut
1952     stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1953                                     _RAIterPairIterator __seqs_end,
1954                                     _RAIterOut __target,
1955                                     _DifferenceTp __length, _Compare __comp,
1956                                     __gnu_parallel::exact_tag __tag)
1957     {
1958       typedef _DifferenceTp _DifferenceType;
1959       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1960
1961       // catch special case: no sequences
1962       if (__seqs_begin == __seqs_end)
1963         return __target;
1964
1965       // Execute merge; maybe parallel, depending on the number of merged
1966       // elements and the number of sequences and global thresholds in
1967       // Settings.
1968       if ((__seqs_end - __seqs_begin > 1)
1969           && _GLIBCXX_PARALLEL_CONDITION(
1970             ((__seqs_end - __seqs_begin) >=
1971             __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1972             && ((_SequenceIndex)__length >=
1973             __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1974         return parallel_multiway_merge
1975           </* __stable = */ true, /* __sentinels = */ true>
1976           (__seqs_begin, __seqs_end, __target,
1977            multiway_merge_exact_splitting</* __stable = */ true,
1978            typename std::iterator_traits<_RAIterPairIterator>
1979            ::value_type*, _Compare, _DifferenceTp>,
1980            static_cast<_DifferenceType>(__length), __comp,
1981            __tag.__get_num_threads());
1982       else
1983         return __sequential_multiway_merge
1984           </* __stable = */ true, /* __sentinels = */ true>
1985           (__seqs_begin, __seqs_end, __target,
1986            *(__seqs_begin->second), __length, __comp);
1987     }
1988
1989   // public interface
1990   template<typename _RAIterPairIterator,
1991            typename _RAIterOut,
1992            typename _DifferenceTp,
1993            typename _Compare>
1994     _RAIterOut
1995     stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1996                                     _RAIterPairIterator __seqs_end,
1997                                     _RAIterOut __target,
1998                                     _DifferenceTp __length,
1999                                     _Compare __comp,
2000                                     sampling_tag __tag)
2001     {
2002       typedef _DifferenceTp _DifferenceType;
2003       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
2004
2005       // catch special case: no sequences
2006       if (__seqs_begin == __seqs_end)
2007         return __target;
2008
2009       // Execute merge; maybe parallel, depending on the number of merged
2010       // elements and the number of sequences and global thresholds in
2011       // Settings.
2012       if ((__seqs_end - __seqs_begin > 1)
2013           && _GLIBCXX_PARALLEL_CONDITION(
2014             ((__seqs_end - __seqs_begin) >=
2015               __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
2016             && ((_SequenceIndex)__length >=
2017               __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
2018         return parallel_multiway_merge
2019           </* __stable = */ true, /* __sentinels = */ true>
2020           (__seqs_begin, __seqs_end, __target,
2021            multiway_merge_sampling_splitting</* __stable = */ true,
2022            typename std::iterator_traits<_RAIterPairIterator>
2023            ::value_type*, _Compare, _DifferenceTp>,
2024            static_cast<_DifferenceType>(__length), __comp,
2025            __tag.__get_num_threads());
2026       else
2027         return __sequential_multiway_merge
2028           </* __stable = */ true, /* __sentinels = */ true>
2029           (__seqs_begin, __seqs_end, __target,
2030            *(__seqs_begin->second), __length, __comp);
2031     }
2032
2033   // public interface
2034   template<typename _RAIterPairIterator,
2035            typename _RAIterOut,
2036            typename _DifferenceTp,
2037            typename _Compare>
2038     _RAIterOut
2039     stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
2040                                     _RAIterPairIterator __seqs_end,
2041                                     _RAIterOut __target,
2042                                     _DifferenceTp __length,
2043                                     _Compare __comp,
2044                                     parallel_tag __tag = parallel_tag(0))
2045     {
2046       return stable_multiway_merge_sentinels
2047         (__seqs_begin, __seqs_end, __target, __length, __comp,
2048          exact_tag(__tag.__get_num_threads()));
2049     }
2050
2051   // public interface
2052   template<typename _RAIterPairIterator,
2053            typename _RAIterOut,
2054            typename _DifferenceTp,
2055            typename _Compare>
2056     _RAIterOut
2057     stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
2058                                     _RAIterPairIterator __seqs_end,
2059                                     _RAIterOut __target,
2060                                     _DifferenceTp __length, _Compare __comp,
2061                                     default_parallel_tag __tag)
2062     {
2063       return stable_multiway_merge_sentinels
2064         (__seqs_begin, __seqs_end, __target, __length, __comp,
2065          exact_tag(__tag.__get_num_threads()));
2066     }
2067 }; // namespace __gnu_parallel
2068
2069 #endif /* _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H */