contrib/gcc-5.0/libstdc++-v3/include/parallel/multiway_merge.h

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