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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007, 2008, 2009, 2010, 2011 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    * @param __stable The value must the same as for the used LoserTrees.
 645    * @param UnguardedLoserTree _Loser Tree variant to use for the unguarded
 646    *   merging.
 647    * @param GuardedLoserTree _Loser Tree variant to use for the guarded
 648    *   merging.
 649    *
 650    * @param __seqs_begin Begin iterator of iterator pair input sequence.
 651    * @param __seqs_end End iterator of iterator pair input sequence.
 652    * @param __target Begin iterator of output sequence.
 653    * @param __comp Comparator.
 654    * @param __length Maximum length to merge, less equal than the
 655    * total number of elements available.
 656    *
 657    * @return End iterator of output sequence.
 658    */
 659   template<typename UnguardedLoserTree,
 660            typename _RAIterIterator,
 661            typename _RAIter3,
 662            typename _DifferenceTp,
 663            typename _Compare>
 664     _RAIter3
 665     multiway_merge_loser_tree_sentinel(_RAIterIterator __seqs_begin,
 666                                        _RAIterIterator __seqs_end,
 667                                        _RAIter3 __target,
 668       const typename std::iterator_traits<typename std::iterator_traits<
 669         _RAIterIterator>::value_type::first_type>::value_type&
 670                                        __sentinel,
 671                                        _DifferenceTp __length,
 672                                        _Compare __comp)
 673     {
 674       _GLIBCXX_CALL(__length)
 675
 676       typedef _DifferenceTp _DifferenceType;
 677       typedef std::iterator_traits<_RAIterIterator> _TraitsType;
 678       typedef typename std::iterator_traits<_RAIterIterator>
 679         ::value_type::first_type
 680         _RAIter1;
 681       typedef typename std::iterator_traits<_RAIter1>::value_type
 682         _ValueType;
 683
 684       _RAIter3 __target_end;
 685
 686       for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
 687         // Move the sequence ends to the sentinel.  This has the
 688         // effect that the sentinel appears to be within the sequence. Then,
 689         // we can use the unguarded variant if we merge out as many
 690         // non-sentinel elements as we have.
 691         ++((*__s).second);
 692
 693       __target_end = multiway_merge_loser_tree_unguarded<UnguardedLoserTree>
 694         (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);
 695
 696 #if _GLIBCXX_ASSERTIONS
 697       _GLIBCXX_PARALLEL_ASSERT(__target_end == __target + __length);
 698       _GLIBCXX_PARALLEL_ASSERT(__is_sorted(__target, __target_end, __comp));
 699 #endif
 700
 701       // Restore the sequence ends so the sentinels are not contained in the
 702       // sequence any more (see comment in loop above).
 703       for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
 704         --((*__s).second);
 705
 706       return __target_end;
 707     }
 708
 709   /**
 710    * @brief Traits for determining whether the loser tree should
 711    *   use pointers or copies.
 712    *
 713    * The field "_M_use_pointer" is used to determine whether to use pointers
 714    * in he loser trees or whether to copy the values into the loser tree.
 715    *
 716    * The default behavior is to use pointers if the data type is 4 times as
 717    * big as the pointer to it.
 718    *
 719    * Specialize for your data type to customize the behavior.
 720    *
 721    * Example:
 722    *
 723    *   template<>
 724    *   struct _LoserTreeTraits<int>
 725    *   { static const bool _M_use_pointer = false; };
 726    *
 727    *   template<>
 728    *   struct _LoserTreeTraits<heavyweight_type>
 729    *   { static const bool _M_use_pointer = true; };
 730    *
 731    * @param _Tp type to give the loser tree traits for.
 732    */
 733   template <typename _Tp>
 734     struct _LoserTreeTraits
 735     {
 736       /**
 737        * @brief True iff to use pointers instead of values in loser trees.
 738        *
 739        * The default behavior is to use pointers if the data type is four
 740        * times as big as the pointer to it.
 741        */
 742       static const bool _M_use_pointer = (sizeof(_Tp) > 4 * sizeof(_Tp*));
 743     };
 744
 745   /**
 746    * @brief Switch for 3-way merging with __sentinels turned off.
 747    *
 748    * Note that 3-way merging is always stable!
 749    */
 750   template<bool __sentinels /*default == false*/,
 751            typename _RAIterIterator,
 752            typename _RAIter3,
 753            typename _DifferenceTp,
 754            typename _Compare>
 755     struct __multiway_merge_3_variant_sentinel_switch
 756     {
 757       _RAIter3
 758       operator()(_RAIterIterator __seqs_begin,
 759                  _RAIterIterator __seqs_end,
 760                  _RAIter3 __target,
 761                  _DifferenceTp __length, _Compare __comp)
 762       { return multiway_merge_3_variant<_GuardedIterator>
 763           (__seqs_begin, __seqs_end, __target, __length, __comp); }
 764     };
 765
 766   /**
 767    * @brief Switch for 3-way merging with __sentinels turned on.
 768    *
 769    * Note that 3-way merging is always stable!
 770    */
 771   template<typename _RAIterIterator,
 772            typename _RAIter3,
 773            typename _DifferenceTp,
 774            typename _Compare>
 775     struct __multiway_merge_3_variant_sentinel_switch<true, _RAIterIterator,
 776                                                       _RAIter3, _DifferenceTp,
 777                                                       _Compare>
 778     {
 779       _RAIter3
 780       operator()(_RAIterIterator __seqs_begin,
 781                  _RAIterIterator __seqs_end,
 782                  _RAIter3 __target,
 783                  _DifferenceTp __length, _Compare __comp)
 784       { return multiway_merge_3_variant<_UnguardedIterator>
 785           (__seqs_begin, __seqs_end, __target, __length, __comp); }
 786     };
 787
 788   /**
 789    * @brief Switch for 4-way merging with __sentinels turned off.
 790    *
 791    * Note that 4-way merging is always stable!
 792    */
 793   template<bool __sentinels /*default == false*/,
 794            typename _RAIterIterator,
 795            typename _RAIter3,
 796            typename _DifferenceTp,
 797            typename _Compare>
 798     struct __multiway_merge_4_variant_sentinel_switch
 799     {
 800       _RAIter3
 801       operator()(_RAIterIterator __seqs_begin,
 802                  _RAIterIterator __seqs_end,
 803                  _RAIter3 __target,
 804                  _DifferenceTp __length, _Compare __comp)
 805       { return multiway_merge_4_variant<_GuardedIterator>
 806           (__seqs_begin, __seqs_end, __target, __length, __comp); }
 807     };
 808
 809   /**
 810    * @brief Switch for 4-way merging with __sentinels turned on.
 811    *
 812    * Note that 4-way merging is always stable!
 813    */
 814   template<typename _RAIterIterator,
 815            typename _RAIter3,
 816            typename _DifferenceTp,
 817            typename _Compare>
 818     struct __multiway_merge_4_variant_sentinel_switch<true, _RAIterIterator,
 819                                                       _RAIter3, _DifferenceTp,
 820                                                       _Compare>
 821     {
 822       _RAIter3
 823       operator()(_RAIterIterator __seqs_begin,
 824                  _RAIterIterator __seqs_end,
 825                  _RAIter3 __target,
 826                  _DifferenceTp __length, _Compare __comp)
 827       { return multiway_merge_4_variant<_UnguardedIterator>
 828           (__seqs_begin, __seqs_end, __target, __length, __comp); }
 829     };
 830
 831   /**
 832    * @brief Switch for k-way merging with __sentinels turned on.
 833    */
 834   template<bool __sentinels,
 835            bool __stable,
 836            typename _RAIterIterator,
 837            typename _RAIter3,
 838            typename _DifferenceTp,
 839            typename _Compare>
 840     struct __multiway_merge_k_variant_sentinel_switch
 841     {
 842       _RAIter3
 843       operator()(_RAIterIterator __seqs_begin,
 844                  _RAIterIterator __seqs_end,
 845                  _RAIter3 __target,
 846       const typename std::iterator_traits<typename std::iterator_traits<
 847       _RAIterIterator>::value_type::first_type>::value_type&
 848                  __sentinel,
 849                  _DifferenceTp __length, _Compare __comp)
 850       {
 851         typedef typename std::iterator_traits<_RAIterIterator>
 852           ::value_type::first_type
 853           _RAIter1;
 854         typedef typename std::iterator_traits<_RAIter1>::value_type
 855           _ValueType;
 856
 857         return multiway_merge_loser_tree_sentinel<
 858         typename __gnu_cxx::__conditional_type<
 859         _LoserTreeTraits<_ValueType>::_M_use_pointer,
 860           _LoserTreePointerUnguarded<__stable, _ValueType, _Compare>,
 861           _LoserTreeUnguarded<__stable, _ValueType, _Compare>
 862           >::__type>
 863           (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);
 864       }
 865     };
 866
 867   /**
 868    * @brief Switch for k-way merging with __sentinels turned off.
 869    */
 870   template<bool __stable,
 871            typename _RAIterIterator,
 872            typename _RAIter3,
 873            typename _DifferenceTp,
 874            typename _Compare>
 875     struct __multiway_merge_k_variant_sentinel_switch<false, __stable,
 876                                                       _RAIterIterator,
 877                                                       _RAIter3, _DifferenceTp,
 878                                                       _Compare>
 879     {
 880       _RAIter3
 881       operator()(_RAIterIterator __seqs_begin,
 882                  _RAIterIterator __seqs_end,
 883                  _RAIter3 __target,
 884        const typename std::iterator_traits<typename std::iterator_traits<
 885        _RAIterIterator>::value_type::first_type>::value_type&
 886                  __sentinel,
 887                  _DifferenceTp __length, _Compare __comp)
 888       {
 889         typedef typename std::iterator_traits<_RAIterIterator>
 890           ::value_type::first_type
 891           _RAIter1;
 892         typedef typename std::iterator_traits<_RAIter1>::value_type
 893           _ValueType;
 894
 895         return multiway_merge_loser_tree<
 896         typename __gnu_cxx::__conditional_type<
 897         _LoserTreeTraits<_ValueType>::_M_use_pointer,
 898           _LoserTreePointer<__stable, _ValueType, _Compare>,
 899           _LoserTree<__stable, _ValueType, _Compare>
 900           >::__type >(__seqs_begin, __seqs_end, __target, __length, __comp);
 901       }
 902     };
 903
 904   /** @brief Sequential multi-way merging switch.
 905    *
 906    *  The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and
 907    *  runtime settings.
 908    *  @param __seqs_begin Begin iterator of iterator pair input sequence.
 909    *  @param __seqs_end End iterator of iterator pair input sequence.
 910    *  @param __target Begin iterator of output sequence.
 911    *  @param __comp Comparator.
 912    *  @param __length Maximum length to merge, possibly larger than the
 913    *  number of elements available.
 914    *  @param __stable Stable merging incurs a performance penalty.
 915    *  @param __sentinel The sequences have __a __sentinel element.
 916    *  @return End iterator of output sequence. */
 917   template<bool __stable,
 918            bool __sentinels,
 919            typename _RAIterIterator,
 920            typename _RAIter3,
 921            typename _DifferenceTp,
 922            typename _Compare>
 923     _RAIter3
 924     __sequential_multiway_merge(_RAIterIterator __seqs_begin,
 925                                 _RAIterIterator __seqs_end,
 926                                 _RAIter3 __target,
 927       const typename std::iterator_traits<typename std::iterator_traits<
 928         _RAIterIterator>::value_type::first_type>::value_type&
 929                                 __sentinel,
 930                                 _DifferenceTp __length, _Compare __comp)
 931     {
 932       _GLIBCXX_CALL(__length)
 933
 934       typedef _DifferenceTp _DifferenceType;
 935       typedef typename std::iterator_traits<_RAIterIterator>
 936         ::difference_type _SeqNumber;
 937       typedef typename std::iterator_traits<_RAIterIterator>
 938         ::value_type::first_type
 939         _RAIter1;
 940       typedef typename std::iterator_traits<_RAIter1>::value_type
 941         _ValueType;
 942
 943 #if _GLIBCXX_ASSERTIONS
 944       for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
 945         {
 946           _GLIBCXX_PARALLEL_ASSERT(__is_sorted((*__s).first,
 947                                                (*__s).second, __comp));
 948         }
 949 #endif
 950
 951       _DifferenceTp __total_length = 0;
 952       for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
 953         __total_length += _GLIBCXX_PARALLEL_LENGTH(*__s);
 954
 955       __length = std::min<_DifferenceTp>(__length, __total_length);
 956
 957       if(__length == 0)
 958         return __target;
 959
 960       _RAIter3 __return_target = __target;
 961       _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
 962
 963       switch (__k)
 964         {
 965         case 0:
 966           break;
 967         case 1:
 968           __return_target = std::copy(__seqs_begin[0].first,
 969                                       __seqs_begin[0].first + __length,
 970                                       __target);
 971           __seqs_begin[0].first += __length;
 972           break;
 973         case 2:
 974           __return_target = __merge_advance(__seqs_begin[0].first,
 975                                             __seqs_begin[0].second,
 976                                             __seqs_begin[1].first,
 977                                             __seqs_begin[1].second,
 978                                             __target, __length, __comp);
 979           break;
 980         case 3:
 981           __return_target = __multiway_merge_3_variant_sentinel_switch
 982             <__sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare>()
 983             (__seqs_begin, __seqs_end, __target, __length, __comp);
 984           break;
 985         case 4:
 986           __return_target = __multiway_merge_4_variant_sentinel_switch
 987             <__sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare>()
 988             (__seqs_begin, __seqs_end, __target, __length, __comp);
 989           break;
 990         default:
 991           __return_target = __multiway_merge_k_variant_sentinel_switch
 992             <__sentinels, __stable, _RAIterIterator, _RAIter3, _DifferenceTp,
 993              _Compare>()
 994             (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);
 995           break;
 996         }
 997 #if _GLIBCXX_ASSERTIONS
 998       _GLIBCXX_PARALLEL_ASSERT(
 999         __is_sorted(__target, __target + __length, __comp));
1000 #endif
1001
1002       return __return_target;
1003     }
1004
1005   /**
1006    * @brief Stable sorting functor.
1007    *
1008    * Used to reduce code instanciation in multiway_merge_sampling_splitting.
1009    */
1010   template<bool __stable, class _RAIter, class _StrictWeakOrdering>
1011     struct _SamplingSorter
1012     {
1013       void
1014       operator()(_RAIter __first, _RAIter __last, _StrictWeakOrdering __comp)
1015       { __gnu_sequential::stable_sort(__first, __last, __comp); }
1016     };
1017
1018   /**
1019    * @brief Non-__stable sorting functor.
1020    *
1021    * Used to reduce code instantiation in multiway_merge_sampling_splitting.
1022    */
1023   template<class _RAIter, class _StrictWeakOrdering>
1024     struct _SamplingSorter<false, _RAIter, _StrictWeakOrdering>
1025     {
1026       void
1027       operator()(_RAIter __first, _RAIter __last, _StrictWeakOrdering __comp)
1028       { __gnu_sequential::sort(__first, __last, __comp); }
1029     };
1030
1031   /**
1032    * @brief Sampling based splitting for parallel multiway-merge routine.
1033    */
1034   template<bool __stable,
1035            typename _RAIterIterator,
1036            typename _Compare,
1037            typename _DifferenceType>
1038     void
1039     multiway_merge_sampling_splitting(_RAIterIterator __seqs_begin,
1040                                       _RAIterIterator __seqs_end,
1041                                       _DifferenceType __length,
1042                                       _DifferenceType __total_length,
1043                                       _Compare __comp,
1044      std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces)
1045     {
1046       typedef typename std::iterator_traits<_RAIterIterator>
1047         ::difference_type _SeqNumber;
1048       typedef typename std::iterator_traits<_RAIterIterator>
1049         ::value_type::first_type
1050         _RAIter1;
1051       typedef typename std::iterator_traits<_RAIter1>::value_type
1052         _ValueType;
1053
1054       // __k sequences.
1055       const _SeqNumber __k
1056         = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
1057
1058       const _ThreadIndex __num_threads = omp_get_num_threads();
1059
1060       const _DifferenceType __num_samples =
1061         __gnu_parallel::_Settings::get().merge_oversampling * __num_threads;
1062
1063       _ValueType* __samples = static_cast<_ValueType*>
1064         (::operator new(sizeof(_ValueType) * __k * __num_samples));
1065       // Sample.
1066       for (_SeqNumber __s = 0; __s < __k; ++__s)
1067         for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
1068           {
1069             _DifferenceType sample_index = static_cast<_DifferenceType>
1070               (_GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__s])
1071                * (double(__i + 1) / (__num_samples + 1))
1072                * (double(__length) / __total_length));
1073             new(&(__samples[__s * __num_samples + __i]))
1074               _ValueType(__seqs_begin[__s].first[sample_index]);
1075           }
1076
1077       // Sort stable or non-stable, depending on value of template parameter
1078       // "__stable".
1079       _SamplingSorter<__stable, _ValueType*, _Compare>()
1080         (__samples, __samples + (__num_samples * __k), __comp);
1081
1082       for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab)
1083         // For each slab / processor.
1084         for (_SeqNumber __seq = 0; __seq < __k; ++__seq)
1085           {
1086             // For each sequence.
1087             if (__slab > 0)
1088               __pieces[__slab][__seq].first = std::upper_bound
1089                 (__seqs_begin[__seq].first, __seqs_begin[__seq].second,
1090                  __samples[__num_samples * __k * __slab / __num_threads],
1091                  __comp)
1092                 - __seqs_begin[__seq].first;
1093             else
1094               // Absolute beginning.
1095               __pieces[__slab][__seq].first = 0;
1096             if ((__slab + 1) < __num_threads)
1097               __pieces[__slab][__seq].second = std::upper_bound
1098                 (__seqs_begin[__seq].first, __seqs_begin[__seq].second,
1099                  __samples[__num_samples * __k * (__slab + 1) / __num_threads],
1100                  __comp)
1101                 - __seqs_begin[__seq].first;
1102             else
1103               // Absolute end.
1104               __pieces[__slab][__seq].second =
1105                 _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]);
1106           }
1107
1108       for (_SeqNumber __s = 0; __s < __k; ++__s)
1109         for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
1110           __samples[__s * __num_samples + __i].~_ValueType();
1111       ::operator delete(__samples);
1112     }
1113
1114   /**
1115    * @brief Exact splitting for parallel multiway-merge routine.
1116    *
1117    * None of the passed sequences may be empty.
1118    */
1119   template<bool __stable,
1120            typename _RAIterIterator,
1121            typename _Compare,
1122            typename _DifferenceType>
1123     void
1124     multiway_merge_exact_splitting(_RAIterIterator __seqs_begin,
1125                                    _RAIterIterator __seqs_end,
1126                                    _DifferenceType __length,
1127                                    _DifferenceType __total_length,
1128                                    _Compare __comp,
1129        std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces)
1130     {
1131       typedef typename std::iterator_traits<_RAIterIterator>
1132         ::difference_type _SeqNumber;
1133       typedef typename std::iterator_traits<_RAIterIterator>
1134         ::value_type::first_type
1135         _RAIter1;
1136
1137       const bool __tight = (__total_length == __length);
1138
1139       // __k sequences.
1140       const _SeqNumber __k = __seqs_end - __seqs_begin;
1141
1142       const _ThreadIndex __num_threads = omp_get_num_threads();
1143
1144       // (Settings::multiway_merge_splitting
1145       //  == __gnu_parallel::_Settings::EXACT).
1146       std::vector<_RAIter1>* __offsets =
1147         new std::vector<_RAIter1>[__num_threads];
1148       std::vector<std::pair<_RAIter1, _RAIter1> > __se(__k);
1149
1150       copy(__seqs_begin, __seqs_end, __se.begin());
1151
1152       _DifferenceType* __borders =
1153         new _DifferenceType[__num_threads + 1];
1154       __equally_split(__length, __num_threads, __borders);
1155
1156       for (_ThreadIndex __s = 0; __s < (__num_threads - 1); ++__s)
1157         {
1158           __offsets[__s].resize(__k);
1159           multiseq_partition(__se.begin(), __se.end(), __borders[__s + 1],
1160                              __offsets[__s].begin(), __comp);
1161
1162           // Last one also needed and available.
1163           if (!__tight)
1164             {
1165               __offsets[__num_threads - 1].resize(__k);
1166               multiseq_partition(__se.begin(), __se.end(),
1167                                  _DifferenceType(__length),
1168                                  __offsets[__num_threads - 1].begin(),
1169                                  __comp);
1170             }
1171         }
1172       delete[] __borders;
1173
1174       for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab)
1175         {
1176           // For each slab / processor.
1177           for (_SeqNumber __seq = 0; __seq < __k; ++__seq)
1178             {
1179               // For each sequence.
1180               if (__slab == 0)
1181                 {
1182                   // Absolute beginning.
1183                   __pieces[__slab][__seq].first = 0;
1184                 }
1185               else
1186                 __pieces[__slab][__seq].first =
1187                   __pieces[__slab - 1][__seq].second;
1188               if (!__tight || __slab < (__num_threads - 1))
1189                 __pieces[__slab][__seq].second =
1190                   __offsets[__slab][__seq] - __seqs_begin[__seq].first;
1191               else
1192                 {
1193                   // __slab == __num_threads - 1
1194                   __pieces[__slab][__seq].second =
1195                     _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]);
1196                 }
1197             }
1198         }
1199       delete[] __offsets;
1200     }
1201
1202   /** @brief Parallel multi-way merge routine.
1203    *
1204    * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor
1205    * and runtime settings.
1206    *
1207    * Must not be called if the number of sequences is 1.
1208    *
1209    * @param _Splitter functor to split input (either __exact or sampling based)
1210    *
1211    * @param __seqs_begin Begin iterator of iterator pair input sequence.
1212    * @param __seqs_end End iterator of iterator pair input sequence.
1213    * @param __target Begin iterator of output sequence.
1214    * @param __comp Comparator.
1215    * @param __length Maximum length to merge, possibly larger than the
1216    * number of elements available.
1217    * @param __stable Stable merging incurs a performance penalty.
1218    * @param __sentinel Ignored.
1219    * @return End iterator of output sequence.
1220    */
1221   template<bool __stable,
1222            bool __sentinels,
1223            typename _RAIterIterator,
1224            typename _RAIter3,
1225            typename _DifferenceTp,
1226            typename _Splitter,
1227            typename _Compare>
1228     _RAIter3
1229     parallel_multiway_merge(_RAIterIterator __seqs_begin,
1230                             _RAIterIterator __seqs_end,
1231                             _RAIter3 __target,
1232                             _Splitter __splitter,
1233                             _DifferenceTp __length,
1234                             _Compare __comp,
1235                             _ThreadIndex __num_threads)
1236       {
1237 #if _GLIBCXX_ASSERTIONS
1238         _GLIBCXX_PARALLEL_ASSERT(__seqs_end - __seqs_begin > 1);
1239 #endif
1240
1241         _GLIBCXX_CALL(__length)
1242
1243         typedef _DifferenceTp _DifferenceType;
1244         typedef typename std::iterator_traits<_RAIterIterator>
1245           ::difference_type _SeqNumber;
1246         typedef typename std::iterator_traits<_RAIterIterator>
1247           ::value_type::first_type
1248           _RAIter1;
1249         typedef typename
1250           std::iterator_traits<_RAIter1>::value_type _ValueType;
1251
1252         // Leave only non-empty sequences.
1253         typedef std::pair<_RAIter1, _RAIter1> seq_type;
1254         seq_type* __ne_seqs = new seq_type[__seqs_end - __seqs_begin];
1255         _SeqNumber __k = 0;
1256         _DifferenceType __total_length = 0;
1257         for (_RAIterIterator __raii = __seqs_begin;
1258              __raii != __seqs_end; ++__raii)
1259           {
1260             _DifferenceTp __seq_length = _GLIBCXX_PARALLEL_LENGTH(*__raii);
1261             if(__seq_length > 0)
1262               {
1263                 __total_length += __seq_length;
1264                 __ne_seqs[__k++] = *__raii;
1265               }
1266           }
1267
1268         _GLIBCXX_CALL(__total_length)
1269
1270         __length = std::min<_DifferenceTp>(__length, __total_length);
1271
1272         if (__total_length == 0 || __k == 0)
1273           {
1274             delete[] __ne_seqs;
1275             return __target;
1276           }
1277
1278         std::vector<std::pair<_DifferenceType, _DifferenceType> >* __pieces;
1279
1280         __num_threads = static_cast<_ThreadIndex>
1281           (std::min<_DifferenceType>(__num_threads, __total_length));
1282
1283 #       pragma omp parallel num_threads (__num_threads)
1284         {
1285 #         pragma omp single
1286           {
1287             __num_threads = omp_get_num_threads();
1288             // Thread __t will have to merge pieces[__iam][0..__k - 1]
1289             __pieces = new std::vector<
1290             std::pair<_DifferenceType, _DifferenceType> >[__num_threads];
1291             for (_ThreadIndex __s = 0; __s < __num_threads; ++__s)
1292               __pieces[__s].resize(__k);
1293
1294             _DifferenceType __num_samples =
1295               __gnu_parallel::_Settings::get().merge_oversampling
1296               * __num_threads;
1297
1298             __splitter(__ne_seqs, __ne_seqs + __k, __length, __total_length,
1299                        __comp, __pieces);
1300           } //single
1301
1302           _ThreadIndex __iam = omp_get_thread_num();
1303
1304           _DifferenceType __target_position = 0;
1305
1306           for (_SeqNumber __c = 0; __c < __k; ++__c)
1307             __target_position += __pieces[__iam][__c].first;
1308
1309           seq_type* __chunks = new seq_type[__k];
1310
1311           for (_SeqNumber __s = 0; __s < __k; ++__s)
1312             __chunks[__s] = std::make_pair(__ne_seqs[__s].first
1313                                            + __pieces[__iam][__s].first,
1314                                            __ne_seqs[__s].first
1315                                            + __pieces[__iam][__s].second);
1316
1317           if(__length > __target_position)
1318             __sequential_multiway_merge<__stable, __sentinels>
1319               (__chunks, __chunks + __k, __target + __target_position,
1320                *(__seqs_begin->second), __length - __target_position, __comp);
1321
1322           delete[] __chunks;
1323         } // parallel
1324
1325 #if _GLIBCXX_ASSERTIONS
1326         _GLIBCXX_PARALLEL_ASSERT(
1327           __is_sorted(__target, __target + __length, __comp));
1328 #endif
1329
1330         __k = 0;
1331         // Update ends of sequences.
1332         for (_RAIterIterator __raii = __seqs_begin;
1333              __raii != __seqs_end; ++__raii)
1334           {
1335             _DifferenceTp __length = _GLIBCXX_PARALLEL_LENGTH(*__raii);
1336             if(__length > 0)
1337               (*__raii).first += __pieces[__num_threads - 1][__k++].second;
1338           }
1339
1340         delete[] __pieces;
1341         delete[] __ne_seqs;
1342
1343         return __target + __length;
1344       }
1345
1346   /**
1347    * @brief Multiway Merge Frontend.
1348    *
1349    * Merge the sequences specified by seqs_begin and __seqs_end into
1350    * __target.  __seqs_begin and __seqs_end must point to a sequence of
1351    * pairs.  These pairs must contain an iterator to the beginning
1352    * of a sequence in their first entry and an iterator the _M_end of
1353    * the same sequence in their second entry.
1354    *
1355    * Ties are broken arbitrarily.  See stable_multiway_merge for a variant
1356    * that breaks ties by sequence number but is slower.
1357    *
1358    * The first entries of the pairs (i.e. the begin iterators) will be moved
1359    * forward.
1360    *
1361    * The output sequence has to provide enough space for all elements
1362    * that are written to it.
1363    *
1364    * This function will merge the input sequences:
1365    *
1366    * - not stable
1367    * - parallel, depending on the input size and Settings
1368    * - using sampling for splitting
1369    * - not using sentinels
1370    *
1371    * Example:
1372    *
1373    * <pre>
1374    *   int sequences[10][10];
1375    *   for (int __i = 0; __i < 10; ++__i)
1376    *     for (int __j = 0; __i < 10; ++__j)
1377    *       sequences[__i][__j] = __j;
1378    *
1379    *   int __out[33];
1380    *   std::vector<std::pair<int*> > seqs;
1381    *   for (int __i = 0; __i < 10; ++__i)
1382    *     { seqs.push(std::make_pair<int*>(sequences[__i],
1383    *                                      sequences[__i] + 10)) }
1384    *
1385    *   multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33);
1386    * </pre>
1387    *
1388    * @see stable_multiway_merge
1389    *
1390    * @pre All input sequences must be sorted.
1391    * @pre Target must provide enough space to merge out length elements or
1392    *    the number of elements in all sequences, whichever is smaller.
1393    *
1394    * @post [__target, return __value) contains merged __elements from the
1395    *    input sequences.
1396    * @post return __value - __target = min(__length, number of elements in all
1397    *    sequences).
1398    *
1399    * @param _RAIterPairIterator iterator over sequence
1400    *    of pairs of iterators
1401    * @param _RAIterOut iterator over target sequence
1402    * @param _DifferenceTp difference type for the sequence
1403    * @param _Compare strict weak ordering type to compare elements
1404    *    in sequences
1405    *
1406    * @param __seqs_begin  __begin of sequence __sequence
1407    * @param __seqs_end    _M_end of sequence __sequence
1408    * @param __target      target sequence to merge to.
1409    * @param __comp        strict weak ordering to use for element comparison.
1410    * @param __length Maximum length to merge, possibly larger than the
1411    * number of elements available.
1412    *
1413    * @return _M_end iterator of output sequence
1414    */
1415   // multiway_merge
1416   // public interface
1417   template<typename _RAIterPairIterator,
1418            typename _RAIterOut,
1419            typename _DifferenceTp,
1420            typename _Compare>
1421     _RAIterOut
1422     multiway_merge(_RAIterPairIterator __seqs_begin,
1423                    _RAIterPairIterator __seqs_end,
1424                    _RAIterOut __target,
1425                    _DifferenceTp __length, _Compare __comp,
1426                    __gnu_parallel::sequential_tag)
1427     {
1428       typedef _DifferenceTp _DifferenceType;
1429       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1430
1431       // catch special case: no sequences
1432       if (__seqs_begin == __seqs_end)
1433         return __target;
1434
1435       // Execute multiway merge *sequentially*.
1436       return __sequential_multiway_merge
1437         </* __stable = */ false, /* __sentinels = */ false>
1438         (__seqs_begin, __seqs_end, __target,
1439          *(__seqs_begin->second), __length, __comp);
1440     }
1441
1442   // public interface
1443   template<typename _RAIterPairIterator,
1444            typename _RAIterOut,
1445            typename _DifferenceTp,
1446            typename _Compare>
1447     _RAIterOut
1448     multiway_merge(_RAIterPairIterator __seqs_begin,
1449                    _RAIterPairIterator __seqs_end,
1450                    _RAIterOut __target,
1451                    _DifferenceTp __length, _Compare __comp,
1452                    __gnu_parallel::exact_tag __tag)
1453     {
1454       typedef _DifferenceTp _DifferenceType;
1455       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1456
1457       // catch special case: no sequences
1458       if (__seqs_begin == __seqs_end)
1459         return __target;
1460
1461       // Execute merge; maybe parallel, depending on the number of merged
1462       // elements and the number of sequences and global thresholds in
1463       // Settings.
1464       if ((__seqs_end - __seqs_begin > 1)
1465           && _GLIBCXX_PARALLEL_CONDITION(
1466             ((__seqs_end - __seqs_begin) >=
1467                __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1468             && ((_SequenceIndex)__length >=
1469               __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1470         return parallel_multiway_merge
1471           </* __stable = */ false, /* __sentinels = */ false>
1472           (__seqs_begin, __seqs_end, __target,
1473            multiway_merge_exact_splitting</* __stable = */ false,
1474            typename std::iterator_traits<_RAIterPairIterator>
1475            ::value_type*, _Compare, _DifferenceTp>,
1476            static_cast<_DifferenceType>(__length), __comp,
1477            __tag.__get_num_threads());
1478       else
1479         return __sequential_multiway_merge
1480           </* __stable = */ false, /* __sentinels = */ false>
1481           (__seqs_begin, __seqs_end, __target,
1482            *(__seqs_begin->second), __length, __comp);
1483     }
1484
1485   // public interface
1486   template<typename _RAIterPairIterator,
1487            typename _RAIterOut,
1488            typename _DifferenceTp,
1489            typename _Compare>
1490     _RAIterOut
1491     multiway_merge(_RAIterPairIterator __seqs_begin,
1492                    _RAIterPairIterator __seqs_end,
1493                    _RAIterOut __target,
1494                    _DifferenceTp __length, _Compare __comp,
1495                    __gnu_parallel::sampling_tag __tag)
1496     {
1497       typedef _DifferenceTp _DifferenceType;
1498       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1499
1500       // catch special case: no sequences
1501       if (__seqs_begin == __seqs_end)
1502         return __target;
1503
1504       // Execute merge; maybe parallel, depending on the number of merged
1505       // elements and the number of sequences and global thresholds in
1506       // Settings.
1507       if ((__seqs_end - __seqs_begin > 1)
1508           && _GLIBCXX_PARALLEL_CONDITION(
1509             ((__seqs_end - __seqs_begin) >=
1510                __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1511             && ((_SequenceIndex)__length >=
1512               __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1513         return parallel_multiway_merge
1514           </* __stable = */ false, /* __sentinels = */ false>
1515           (__seqs_begin, __seqs_end, __target,
1516            multiway_merge_exact_splitting</* __stable = */ false,
1517            typename std::iterator_traits<_RAIterPairIterator>
1518            ::value_type*, _Compare, _DifferenceTp>,
1519            static_cast<_DifferenceType>(__length), __comp,
1520            __tag.__get_num_threads());
1521       else
1522         return __sequential_multiway_merge
1523           </* __stable = */ false, /* __sentinels = */ false>
1524           (__seqs_begin, __seqs_end, __target,
1525            *(__seqs_begin->second), __length, __comp);
1526     }
1527
1528   // public interface
1529   template<typename _RAIterPairIterator,
1530            typename _RAIterOut,
1531            typename _DifferenceTp,
1532            typename _Compare>
1533     _RAIterOut
1534     multiway_merge(_RAIterPairIterator __seqs_begin,
1535                    _RAIterPairIterator __seqs_end,
1536                    _RAIterOut __target,
1537                    _DifferenceTp __length, _Compare __comp,
1538                    parallel_tag __tag = parallel_tag(0))
1539     { return multiway_merge(__seqs_begin, __seqs_end, __target, __length,
1540                             __comp, exact_tag(__tag.__get_num_threads())); }
1541
1542   // public interface
1543   template<typename _RAIterPairIterator,
1544            typename _RAIterOut,
1545            typename _DifferenceTp,
1546            typename _Compare>
1547     _RAIterOut
1548     multiway_merge(_RAIterPairIterator __seqs_begin,
1549                    _RAIterPairIterator __seqs_end,
1550                    _RAIterOut __target,
1551                    _DifferenceTp __length, _Compare __comp,
1552                    default_parallel_tag __tag)
1553     { return multiway_merge(__seqs_begin, __seqs_end, __target, __length,
1554                             __comp, exact_tag(__tag.__get_num_threads())); }
1555
1556   // stable_multiway_merge
1557   // public interface
1558   template<typename _RAIterPairIterator,
1559            typename _RAIterOut,
1560            typename _DifferenceTp,
1561            typename _Compare>
1562     _RAIterOut
1563     stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1564                           _RAIterPairIterator __seqs_end,
1565                           _RAIterOut __target,
1566                           _DifferenceTp __length, _Compare __comp,
1567                           __gnu_parallel::sequential_tag)
1568     {
1569       typedef _DifferenceTp _DifferenceType;
1570       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1571
1572       // catch special case: no sequences
1573       if (__seqs_begin == __seqs_end)
1574         return __target;
1575
1576       // Execute multiway merge *sequentially*.
1577       return __sequential_multiway_merge
1578         </* __stable = */ true, /* __sentinels = */ false>
1579           (__seqs_begin, __seqs_end, __target,
1580            *(__seqs_begin->second), __length, __comp);
1581     }
1582
1583   // public interface
1584   template<typename _RAIterPairIterator,
1585            typename _RAIterOut,
1586            typename _DifferenceTp,
1587            typename _Compare>
1588     _RAIterOut
1589     stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1590                           _RAIterPairIterator __seqs_end,
1591                           _RAIterOut __target,
1592                           _DifferenceTp __length, _Compare __comp,
1593                           __gnu_parallel::exact_tag __tag)
1594     {
1595       typedef _DifferenceTp _DifferenceType;
1596       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1597
1598       // catch special case: no sequences
1599       if (__seqs_begin == __seqs_end)
1600         return __target;
1601
1602       // Execute merge; maybe parallel, depending on the number of merged
1603       // elements and the number of sequences and global thresholds in
1604       // Settings.
1605       if ((__seqs_end - __seqs_begin > 1)
1606           && _GLIBCXX_PARALLEL_CONDITION(
1607             ((__seqs_end - __seqs_begin) >=
1608               __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1609             && ((_SequenceIndex)__length >=
1610               __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1611         return parallel_multiway_merge
1612           </* __stable = */ true, /* __sentinels = */ false>
1613           (__seqs_begin, __seqs_end, __target,
1614            multiway_merge_exact_splitting</* __stable = */ true,
1615            typename std::iterator_traits<_RAIterPairIterator>
1616            ::value_type*, _Compare, _DifferenceTp>,
1617            static_cast<_DifferenceType>(__length), __comp,
1618            __tag.__get_num_threads());
1619       else
1620         return __sequential_multiway_merge
1621           </* __stable = */ true, /* __sentinels = */ false>
1622           (__seqs_begin, __seqs_end, __target,
1623            *(__seqs_begin->second), __length, __comp);
1624     }
1625
1626   // public interface
1627   template<typename _RAIterPairIterator,
1628            typename _RAIterOut,
1629            typename _DifferenceTp,
1630            typename _Compare>
1631     _RAIterOut
1632     stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1633                           _RAIterPairIterator __seqs_end,
1634                           _RAIterOut __target,
1635                           _DifferenceTp __length, _Compare __comp,
1636                           sampling_tag __tag)
1637     {
1638       typedef _DifferenceTp _DifferenceType;
1639       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1640
1641       // catch special case: no sequences
1642       if (__seqs_begin == __seqs_end)
1643         return __target;
1644
1645       // Execute merge; maybe parallel, depending on the number of merged
1646       // elements and the number of sequences and global thresholds in
1647       // Settings.
1648       if ((__seqs_end - __seqs_begin > 1)
1649           && _GLIBCXX_PARALLEL_CONDITION(
1650             ((__seqs_end - __seqs_begin) >=
1651               __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1652             && ((_SequenceIndex)__length >=
1653               __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1654         return parallel_multiway_merge
1655           </* __stable = */ true, /* __sentinels = */ false>
1656           (__seqs_begin, __seqs_end, __target,
1657            multiway_merge_sampling_splitting</* __stable = */ true,
1658            typename std::iterator_traits<_RAIterPairIterator>
1659            ::value_type*, _Compare, _DifferenceTp>,
1660            static_cast<_DifferenceType>(__length), __comp,
1661            __tag.__get_num_threads());
1662       else
1663         return __sequential_multiway_merge
1664           </* __stable = */ true, /* __sentinels = */ false>
1665           (__seqs_begin, __seqs_end, __target,
1666            *(__seqs_begin->second), __length, __comp);
1667     }
1668
1669   // public interface
1670   template<typename _RAIterPairIterator,
1671            typename _RAIterOut,
1672            typename _DifferenceTp,
1673            typename _Compare>
1674     _RAIterOut
1675     stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1676                           _RAIterPairIterator __seqs_end,
1677                           _RAIterOut __target,
1678                           _DifferenceTp __length, _Compare __comp,
1679                           parallel_tag __tag = parallel_tag(0))
1680     {
1681       return stable_multiway_merge
1682         (__seqs_begin, __seqs_end, __target, __length, __comp,
1683          exact_tag(__tag.__get_num_threads()));
1684     }
1685
1686   // public interface
1687   template<typename _RAIterPairIterator,
1688            typename _RAIterOut,
1689            typename _DifferenceTp,
1690            typename _Compare>
1691     _RAIterOut
1692     stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1693                           _RAIterPairIterator __seqs_end,
1694                           _RAIterOut __target,
1695                           _DifferenceTp __length, _Compare __comp,
1696                           default_parallel_tag __tag)
1697     {
1698       return stable_multiway_merge
1699         (__seqs_begin, __seqs_end, __target, __length, __comp,
1700          exact_tag(__tag.__get_num_threads()));
1701     }
1702
1703   /**
1704    * @brief Multiway Merge Frontend.
1705    *
1706    * Merge the sequences specified by seqs_begin and __seqs_end into
1707    * __target.  __seqs_begin and __seqs_end must point to a sequence of
1708    * pairs.  These pairs must contain an iterator to the beginning
1709    * of a sequence in their first entry and an iterator the _M_end of
1710    * the same sequence in their second entry.
1711    *
1712    * Ties are broken arbitrarily.  See stable_multiway_merge for a variant
1713    * that breaks ties by sequence number but is slower.
1714    *
1715    * The first entries of the pairs (i.e. the begin iterators) will be moved
1716    * forward accordingly.
1717    *
1718    * The output sequence has to provide enough space for all elements
1719    * that are written to it.
1720    *
1721    * This function will merge the input sequences:
1722    *
1723    * - not stable
1724    * - parallel, depending on the input size and Settings
1725    * - using sampling for splitting
1726    * - using sentinels
1727    *
1728    * You have to take care that the element the _M_end iterator points to is
1729    * readable and contains a value that is greater than any other non-sentinel
1730    * value in all sequences.
1731    *
1732    * Example:
1733    *
1734    * <pre>
1735    *   int sequences[10][11];
1736    *   for (int __i = 0; __i < 10; ++__i)
1737    *     for (int __j = 0; __i < 11; ++__j)
1738    *       sequences[__i][__j] = __j; // __last one is sentinel!
1739    *
1740    *   int __out[33];
1741    *   std::vector<std::pair<int*> > seqs;
1742    *   for (int __i = 0; __i < 10; ++__i)
1743    *     { seqs.push(std::make_pair<int*>(sequences[__i],
1744    *                                      sequences[__i] + 10)) }
1745    *
1746    *   multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33);
1747    * </pre>
1748    *
1749    * @pre All input sequences must be sorted.
1750    * @pre Target must provide enough space to merge out length elements or
1751    *    the number of elements in all sequences, whichever is smaller.
1752    * @pre For each @c __i, @c __seqs_begin[__i].second must be the end
1753    *    marker of the sequence, but also reference the one more __sentinel
1754    *    element.
1755    *
1756    * @post [__target, return __value) contains merged __elements from the
1757    *    input sequences.
1758    * @post return __value - __target = min(__length, number of elements in all
1759    *    sequences).
1760    *
1761    * @see stable_multiway_merge_sentinels
1762    *
1763    * @param _RAIterPairIterator iterator over sequence
1764    *    of pairs of iterators
1765    * @param _RAIterOut iterator over target sequence
1766    * @param _DifferenceTp difference type for the sequence
1767    * @param _Compare strict weak ordering type to compare elements
1768    *    in sequences
1769    *
1770    * @param __seqs_begin  __begin of sequence __sequence
1771    * @param __seqs_end    _M_end of sequence __sequence
1772    * @param __target      target sequence to merge to.
1773    * @param __comp        strict weak ordering to use for element comparison.
1774    * @param __length Maximum length to merge, possibly larger than the
1775    * number of elements available.
1776    *
1777    * @return _M_end iterator of output sequence
1778    */
1779   // multiway_merge_sentinels
1780   // public interface
1781   template<typename _RAIterPairIterator,
1782            typename _RAIterOut,
1783            typename _DifferenceTp,
1784            typename _Compare>
1785     _RAIterOut
1786     multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1787                              _RAIterPairIterator __seqs_end,
1788                              _RAIterOut __target,
1789                              _DifferenceTp __length, _Compare __comp,
1790                              __gnu_parallel::sequential_tag)
1791     {
1792       typedef _DifferenceTp _DifferenceType;
1793       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1794
1795       // catch special case: no sequences
1796       if (__seqs_begin == __seqs_end)
1797         return __target;
1798
1799       // Execute multiway merge *sequentially*.
1800       return __sequential_multiway_merge
1801         </* __stable = */ false, /* __sentinels = */ true>
1802           (__seqs_begin, __seqs_end,
1803            __target, *(__seqs_begin->second), __length, __comp);
1804     }
1805
1806   // public interface
1807   template<typename _RAIterPairIterator,
1808            typename _RAIterOut,
1809            typename _DifferenceTp,
1810            typename _Compare>
1811     _RAIterOut
1812     multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1813                              _RAIterPairIterator __seqs_end,
1814                              _RAIterOut __target,
1815                              _DifferenceTp __length, _Compare __comp,
1816                              __gnu_parallel::exact_tag __tag)
1817     {
1818       typedef _DifferenceTp _DifferenceType;
1819       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1820
1821       // catch special case: no sequences
1822       if (__seqs_begin == __seqs_end)
1823         return __target;
1824
1825       // Execute merge; maybe parallel, depending on the number of merged
1826       // elements and the number of sequences and global thresholds in
1827       // Settings.
1828       if ((__seqs_end - __seqs_begin > 1)
1829           && _GLIBCXX_PARALLEL_CONDITION(
1830             ((__seqs_end - __seqs_begin) >=
1831               __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1832             && ((_SequenceIndex)__length >=
1833               __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1834         return parallel_multiway_merge
1835           </* __stable = */ false, /* __sentinels = */ true>
1836           (__seqs_begin, __seqs_end, __target,
1837            multiway_merge_exact_splitting</* __stable = */ false,
1838            typename std::iterator_traits<_RAIterPairIterator>
1839            ::value_type*, _Compare, _DifferenceTp>,
1840            static_cast<_DifferenceType>(__length), __comp,
1841            __tag.__get_num_threads());
1842       else
1843         return __sequential_multiway_merge
1844           </* __stable = */ false, /* __sentinels = */ true>
1845           (__seqs_begin, __seqs_end, __target,
1846            *(__seqs_begin->second), __length, __comp);
1847     }
1848
1849   // public interface
1850   template<typename _RAIterPairIterator,
1851            typename _RAIterOut,
1852            typename _DifferenceTp,
1853            typename _Compare>
1854     _RAIterOut
1855     multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1856                              _RAIterPairIterator __seqs_end,
1857                              _RAIterOut __target,
1858                              _DifferenceTp __length, _Compare __comp,
1859                              sampling_tag __tag)
1860     {
1861       typedef _DifferenceTp _DifferenceType;
1862       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1863
1864       // catch special case: no sequences
1865       if (__seqs_begin == __seqs_end)
1866         return __target;
1867
1868       // Execute merge; maybe parallel, depending on the number of merged
1869       // elements and the number of sequences and global thresholds in
1870       // Settings.
1871       if ((__seqs_end - __seqs_begin > 1)
1872           && _GLIBCXX_PARALLEL_CONDITION(
1873             ((__seqs_end - __seqs_begin) >=
1874               __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1875             && ((_SequenceIndex)__length >=
1876               __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1877         return parallel_multiway_merge
1878           </* __stable = */ false, /* __sentinels = */ true>
1879           (__seqs_begin, __seqs_end, __target,
1880            multiway_merge_sampling_splitting</* __stable = */ false,
1881            typename std::iterator_traits<_RAIterPairIterator>
1882            ::value_type*, _Compare, _DifferenceTp>,
1883            static_cast<_DifferenceType>(__length), __comp,
1884            __tag.__get_num_threads());
1885       else
1886         return __sequential_multiway_merge
1887           </* __stable = */false, /* __sentinels = */ true>(
1888             __seqs_begin, __seqs_end, __target,
1889             *(__seqs_begin->second), __length, __comp);
1890     }
1891
1892   // public interface
1893   template<typename _RAIterPairIterator,
1894            typename _RAIterOut,
1895            typename _DifferenceTp,
1896            typename _Compare>
1897     _RAIterOut
1898     multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1899                              _RAIterPairIterator __seqs_end,
1900                              _RAIterOut __target,
1901                              _DifferenceTp __length, _Compare __comp,
1902                              parallel_tag __tag = parallel_tag(0))
1903     {
1904       return multiway_merge_sentinels
1905         (__seqs_begin, __seqs_end, __target, __length, __comp,
1906          exact_tag(__tag.__get_num_threads()));
1907     }
1908
1909   // public interface
1910   template<typename _RAIterPairIterator,
1911            typename _RAIterOut,
1912            typename _DifferenceTp,
1913            typename _Compare>
1914     _RAIterOut
1915     multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1916                              _RAIterPairIterator __seqs_end,
1917                              _RAIterOut __target,
1918                              _DifferenceTp __length, _Compare __comp,
1919                              default_parallel_tag __tag)
1920     {
1921       return multiway_merge_sentinels
1922         (__seqs_begin, __seqs_end, __target, __length, __comp,
1923          exact_tag(__tag.__get_num_threads()));
1924     }
1925
1926   // stable_multiway_merge_sentinels
1927   // public interface
1928   template<typename _RAIterPairIterator,
1929            typename _RAIterOut,
1930            typename _DifferenceTp,
1931            typename _Compare>
1932     _RAIterOut
1933     stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1934                                     _RAIterPairIterator __seqs_end,
1935                                     _RAIterOut __target,
1936                                     _DifferenceTp __length, _Compare __comp,
1937                                     __gnu_parallel::sequential_tag)
1938     {
1939       typedef _DifferenceTp _DifferenceType;
1940       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1941
1942       // catch special case: no sequences
1943       if (__seqs_begin == __seqs_end)
1944         return __target;
1945
1946       // Execute multiway merge *sequentially*.
1947       return __sequential_multiway_merge
1948         </* __stable = */ true, /* __sentinels = */ true>
1949         (__seqs_begin, __seqs_end, __target,
1950          *(__seqs_begin->second), __length, __comp);
1951     }
1952
1953   // public interface
1954   template<typename _RAIterPairIterator,
1955            typename _RAIterOut,
1956            typename _DifferenceTp,
1957            typename _Compare>
1958     _RAIterOut
1959     stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1960                                     _RAIterPairIterator __seqs_end,
1961                                     _RAIterOut __target,
1962                                     _DifferenceTp __length, _Compare __comp,
1963                                     __gnu_parallel::exact_tag __tag)
1964     {
1965       typedef _DifferenceTp _DifferenceType;
1966       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1967
1968       // catch special case: no sequences
1969       if (__seqs_begin == __seqs_end)
1970         return __target;
1971
1972       // Execute merge; maybe parallel, depending on the number of merged
1973       // elements and the number of sequences and global thresholds in
1974       // Settings.
1975       if ((__seqs_end - __seqs_begin > 1)
1976           && _GLIBCXX_PARALLEL_CONDITION(
1977             ((__seqs_end - __seqs_begin) >=
1978             __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1979             && ((_SequenceIndex)__length >=
1980             __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1981         return parallel_multiway_merge
1982           </* __stable = */ true, /* __sentinels = */ true>
1983           (__seqs_begin, __seqs_end, __target,
1984            multiway_merge_exact_splitting</* __stable = */ true,
1985            typename std::iterator_traits<_RAIterPairIterator>
1986            ::value_type*, _Compare, _DifferenceTp>,
1987            static_cast<_DifferenceType>(__length), __comp,
1988            __tag.__get_num_threads());
1989       else
1990         return __sequential_multiway_merge
1991           </* __stable = */ true, /* __sentinels = */ true>
1992           (__seqs_begin, __seqs_end, __target,
1993            *(__seqs_begin->second), __length, __comp);
1994     }
1995
1996   // public interface
1997   template<typename _RAIterPairIterator,
1998            typename _RAIterOut,
1999            typename _DifferenceTp,
2000            typename _Compare>
2001     _RAIterOut
2002     stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
2003                                     _RAIterPairIterator __seqs_end,
2004                                     _RAIterOut __target,
2005                                     _DifferenceTp __length,
2006                                     _Compare __comp,
2007                                     sampling_tag __tag)
2008     {
2009       typedef _DifferenceTp _DifferenceType;
2010       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
2011
2012       // catch special case: no sequences
2013       if (__seqs_begin == __seqs_end)
2014         return __target;
2015
2016       // Execute merge; maybe parallel, depending on the number of merged
2017       // elements and the number of sequences and global thresholds in
2018       // Settings.
2019       if ((__seqs_end - __seqs_begin > 1)
2020           && _GLIBCXX_PARALLEL_CONDITION(
2021             ((__seqs_end - __seqs_begin) >=
2022               __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
2023             && ((_SequenceIndex)__length >=
2024               __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
2025         return parallel_multiway_merge
2026           </* __stable = */ true, /* __sentinels = */ true>
2027           (__seqs_begin, __seqs_end, __target,
2028            multiway_merge_sampling_splitting</* __stable = */ true,
2029            typename std::iterator_traits<_RAIterPairIterator>
2030            ::value_type*, _Compare, _DifferenceTp>,
2031            static_cast<_DifferenceType>(__length), __comp,
2032            __tag.__get_num_threads());
2033       else
2034         return __sequential_multiway_merge
2035           </* __stable = */ true, /* __sentinels = */ true>
2036           (__seqs_begin, __seqs_end, __target,
2037            *(__seqs_begin->second), __length, __comp);
2038     }
2039
2040   // public interface
2041   template<typename _RAIterPairIterator,
2042            typename _RAIterOut,
2043            typename _DifferenceTp,
2044            typename _Compare>
2045     _RAIterOut
2046     stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
2047                                     _RAIterPairIterator __seqs_end,
2048                                     _RAIterOut __target,
2049                                     _DifferenceTp __length,
2050                                     _Compare __comp,
2051                                     parallel_tag __tag = parallel_tag(0))
2052     {
2053       return stable_multiway_merge_sentinels
2054         (__seqs_begin, __seqs_end, __target, __length, __comp,
2055          exact_tag(__tag.__get_num_threads()));
2056     }
2057
2058   // public interface
2059   template<typename _RAIterPairIterator,
2060            typename _RAIterOut,
2061            typename _DifferenceTp,
2062            typename _Compare>
2063     _RAIterOut
2064     stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
2065                                     _RAIterPairIterator __seqs_end,
2066                                     _RAIterOut __target,
2067                                     _DifferenceTp __length, _Compare __comp,
2068                                     default_parallel_tag __tag)
2069     {
2070       return stable_multiway_merge_sentinels
2071         (__seqs_begin, __seqs_end, __target, __length, __comp,
2072          exact_tag(__tag.__get_num_threads()));
2073     }
2074 }; // namespace __gnu_parallel
2075
2076 #endif /* _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H */