Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  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 */
  2073.