multiway_merge.h

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 2, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License
00017 // along with this library; see the file COPYING.  If not, write to
00018 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
00019 // MA 02111-1307, USA.
00020 
00021 // As a special exception, you may use this file as part of a free
00022 // software library without restriction.  Specifically, if other files
00023 // instantiate templates or use macros or inline functions from this
00024 // file, or you compile this file and link it with other files to
00025 // produce an executable, this file does not by itself cause the
00026 // resulting executable to be covered by the GNU General Public
00027 // License.  This exception does not however invalidate any other
00028 // reasons why the executable file might be covered by the GNU General
00029 // Public License.
00030 
00031 /** @file parallel/multiway_merge.h
00032 *  @brief Implementation of sequential and parallel multiway merge.
00033 *
00034 *  Explanations on the high-speed merging routines in the appendix of
00035 *
00036 *  P. Sanders.
00037 *  Fast priority queues for cached memory.
00038 *  ACM Journal of Experimental Algorithmics, 5, 2000.
00039 *
00040 *  This file is a GNU parallel extension to the Standard C++ Library.
00041 */
00042 
00043 // Written by Johannes Singler and Manuel Holtgrewe.
00044 
00045 #ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
00046 #define _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
00047 
00048 #include <vector>
00049 
00050 #include <bits/stl_algo.h>
00051 #include <parallel/features.h>
00052 #include <parallel/parallel.h>
00053 #include <parallel/losertree.h>
00054 #if _GLIBCXX_ASSERTIONS
00055 #include <parallel/checkers.h>
00056 #endif
00057 
00058 /** @brief Length of a sequence described by a pair of iterators. */
00059 #define _GLIBCXX_PARALLEL_LENGTH(s) ((s).second - (s).first)
00060 
00061 namespace __gnu_parallel
00062 {
00063 
00064 // Announce guarded and unguarded iterator.
00065 
00066 template<typename RandomAccessIterator, typename Comparator>
00067   class guarded_iterator;
00068 
00069 // Making the arguments const references seems to dangerous,
00070 // the user-defined comparator might not be const.
00071 template<typename RandomAccessIterator, typename Comparator>
00072   inline bool
00073   operator<(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
00074              guarded_iterator<RandomAccessIterator, Comparator>& bi2);
00075 
00076 template<typename RandomAccessIterator, typename Comparator>
00077   inline bool
00078   operator<=(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
00079               guarded_iterator<RandomAccessIterator, Comparator>& bi2);
00080 
00081 /** @brief Iterator wrapper supporting an implicit supremum at the end
00082  *         of the sequence, dominating all comparisons.
00083  *
00084  * The implicit supremum comes with a performance cost.
00085  *
00086  * Deriving from RandomAccessIterator is not possible since
00087  * RandomAccessIterator need not be a class.
00088  */
00089 template<typename RandomAccessIterator, typename Comparator>
00090   class guarded_iterator
00091   {
00092   private:
00093     /** @brief Current iterator position. */
00094     RandomAccessIterator current;
00095 
00096     /** @brief End iterator of the sequence. */
00097     RandomAccessIterator end;
00098 
00099     /** @brief Comparator. */
00100     Comparator& comp;
00101 
00102   public:
00103     /** @brief Constructor. Sets iterator to beginning of sequence.
00104     *  @param begin Begin iterator of sequence.
00105     *  @param end End iterator of sequence.
00106     *  @param comp Comparator provided for associated overloaded
00107     *  compare operators. */
00108     guarded_iterator(RandomAccessIterator begin,
00109                      RandomAccessIterator end, Comparator& comp)
00110     : current(begin), end(end), comp(comp)
00111     { }
00112 
00113     /** @brief Pre-increment operator.
00114     *  @return This. */
00115     guarded_iterator<RandomAccessIterator, Comparator>&
00116     operator++()
00117     {
00118       ++current;
00119       return *this;
00120     }
00121 
00122     /** @brief Dereference operator.
00123     *  @return Referenced element. */
00124     typename std::iterator_traits<RandomAccessIterator>::value_type&
00125     operator*()
00126     { return *current; }
00127 
00128     /** @brief Convert to wrapped iterator.
00129     *  @return Wrapped iterator. */
00130     operator RandomAccessIterator()
00131     { return current; }
00132 
00133     friend bool
00134     operator< <RandomAccessIterator, Comparator>(
00135       guarded_iterator<RandomAccessIterator, Comparator>& bi1,
00136       guarded_iterator<RandomAccessIterator, Comparator>& bi2);
00137 
00138     friend bool
00139     operator<= <RandomAccessIterator, Comparator>(
00140       guarded_iterator<RandomAccessIterator, Comparator>& bi1,
00141       guarded_iterator<RandomAccessIterator, Comparator>& bi2);
00142   };
00143 
00144 /** @brief Compare two elements referenced by guarded iterators.
00145  *  @param bi1 First iterator.
00146  *  @param bi2 Second iterator.
00147  *  @return @c True if less. */
00148 template<typename RandomAccessIterator, typename Comparator>
00149   inline bool
00150   operator<(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
00151             guarded_iterator<RandomAccessIterator, Comparator>& bi2)
00152   {
00153     if (bi1.current == bi1.end) //bi1 is sup
00154       return bi2.current == bi2.end;    //bi2 is not sup
00155     if (bi2.current == bi2.end) //bi2 is sup
00156       return true;
00157     return (bi1.comp)(*bi1, *bi2);  //normal compare
00158   }
00159 
00160 /** @brief Compare two elements referenced by guarded iterators.
00161  *  @param bi1 First iterator.
00162  *  @param bi2 Second iterator.
00163  *  @return @c True if less equal. */
00164 template<typename RandomAccessIterator, typename Comparator>
00165   inline bool
00166   operator<=(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
00167                guarded_iterator<RandomAccessIterator, Comparator>& bi2)
00168   {
00169     if (bi2.current == bi2.end) //bi1 is sup
00170       return bi1.current != bi1.end;    //bi2 is not sup
00171     if (bi1.current == bi1.end) //bi2 is sup
00172       return false;
00173     return !(bi1.comp)(*bi2, *bi1); //normal compare
00174   }
00175 
00176 template<typename RandomAccessIterator, typename Comparator>
00177   class unguarded_iterator;
00178 
00179 template<typename RandomAccessIterator, typename Comparator>
00180   inline bool
00181   operator<(unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
00182             unguarded_iterator<RandomAccessIterator, Comparator>& bi2);
00183 
00184 template<typename RandomAccessIterator, typename Comparator>
00185   inline bool
00186   operator<=(unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
00187              unguarded_iterator<RandomAccessIterator, Comparator>& bi2);
00188 
00189 template<typename RandomAccessIterator, typename Comparator>
00190   class unguarded_iterator
00191   {
00192   private:
00193     /** @brief Current iterator position. */
00194     RandomAccessIterator current;
00195     /** @brief Comparator. */
00196     mutable Comparator& comp;
00197 
00198   public:
00199     /** @brief Constructor. Sets iterator to beginning of sequence.
00200     *  @param begin Begin iterator of sequence.
00201     *  @param end Unused, only for compatibility.
00202     *  @param comp Unused, only for compatibility. */
00203     unguarded_iterator(RandomAccessIterator begin,
00204                        RandomAccessIterator end, Comparator& comp)
00205     : current(begin), comp(comp)
00206     { }
00207 
00208     /** @brief Pre-increment operator.
00209     *  @return This. */
00210     unguarded_iterator<RandomAccessIterator, Comparator>&
00211     operator++()
00212     {
00213       ++current;
00214       return *this;
00215     }
00216 
00217     /** @brief Dereference operator.
00218     *  @return Referenced element. */
00219     typename std::iterator_traits<RandomAccessIterator>::value_type&
00220     operator*()
00221     { return *current; }
00222 
00223     /** @brief Convert to wrapped iterator.
00224     *  @return Wrapped iterator. */
00225     operator RandomAccessIterator()
00226     { return current; }
00227 
00228     friend bool
00229     operator< <RandomAccessIterator, Comparator>(
00230       unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
00231       unguarded_iterator<RandomAccessIterator, Comparator>& bi2);
00232 
00233     friend bool
00234     operator<= <RandomAccessIterator, Comparator>(
00235       unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
00236       unguarded_iterator<RandomAccessIterator, Comparator>& bi2);
00237   };
00238 
00239 /** @brief Compare two elements referenced by unguarded iterators.
00240  *  @param bi1 First iterator.
00241  *  @param bi2 Second iterator.
00242  *  @return @c True if less. */
00243 template<typename RandomAccessIterator, typename Comparator>
00244   inline bool
00245   operator<(unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
00246             unguarded_iterator<RandomAccessIterator, Comparator>& bi2)
00247   {
00248     // Normal compare.
00249     return (bi1.comp)(*bi1, *bi2);
00250   }
00251 
00252 /** @brief Compare two elements referenced by unguarded iterators.
00253  *  @param bi1 First iterator.
00254  *  @param bi2 Second iterator.
00255  *  @return @c True if less equal. */
00256 template<typename RandomAccessIterator, typename Comparator>
00257   inline bool
00258   operator<=(unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
00259             unguarded_iterator<RandomAccessIterator, Comparator>& bi2)
00260   {
00261     // Normal compare.
00262     return !(bi1.comp)(*bi2, *bi1);
00263   }
00264 
00265 /** @brief Highly efficient 3-way merging procedure.
00266  *
00267  * Merging is done with the algorithm implementation described by Peter
00268  * Sanders.  Basically, the idea is to minimize the number of necessary
00269  * comparison after merging out an element.  The implementation trick
00270  * that makes this fast is that the order of the sequences is stored
00271  * in the instruction pointer (translated into labels in C++).
00272  *
00273  * This works well for merging up to 4 sequences.
00274  *
00275  * Note that making the merging stable does <em>not</em> come at a
00276  * performance hit.
00277  *
00278  * Whether the merging is done guarded or unguarded is selected by the
00279  * used iterator class.
00280  *
00281  * @param seqs_begin Begin iterator of iterator pair input sequence.
00282  * @param seqs_end End iterator of iterator pair input sequence.
00283  * @param target Begin iterator out output sequence.
00284  * @param comp Comparator.
00285  * @param length Maximum length to merge, less equal than the
00286  * total number of elements available.
00287  *
00288  * @return End iterator of output sequence.
00289  */
00290 template<template<typename RAI, typename C> class iterator,
00291      typename RandomAccessIteratorIterator,
00292      typename RandomAccessIterator3,
00293      typename _DifferenceTp,
00294      typename Comparator>
00295   RandomAccessIterator3
00296   multiway_merge_3_variant(
00297       RandomAccessIteratorIterator seqs_begin,
00298       RandomAccessIteratorIterator seqs_end,
00299       RandomAccessIterator3 target,
00300       Comparator comp, _DifferenceTp length)
00301   {
00302     _GLIBCXX_CALL(length);
00303 
00304     typedef _DifferenceTp difference_type;
00305 
00306     typedef typename std::iterator_traits<RandomAccessIteratorIterator>
00307       ::value_type::first_type
00308       RandomAccessIterator1;
00309     typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
00310       value_type;
00311 
00312     if (length == 0)
00313       return target;
00314 
00315 #if _GLIBCXX_ASSERTIONS
00316     _DifferenceTp orig_length = length;
00317 #endif
00318 
00319     iterator<RandomAccessIterator1, Comparator>
00320       seq0(seqs_begin[0].first, seqs_begin[0].second, comp),
00321       seq1(seqs_begin[1].first, seqs_begin[1].second, comp),
00322       seq2(seqs_begin[2].first, seqs_begin[2].second, comp);
00323 
00324     if (seq0 <= seq1)
00325       {
00326         if (seq1 <= seq2)
00327           goto s012;
00328         else
00329           if (seq2 <  seq0)
00330             goto s201;
00331           else
00332             goto s021;
00333       }
00334     else
00335       {
00336         if (seq1 <= seq2)
00337           {
00338             if (seq0 <= seq2)
00339               goto s102;
00340             else
00341               goto s120;
00342           }
00343         else
00344           goto s210;
00345       }
00346 #define _GLIBCXX_PARALLEL_MERGE_3_CASE(a,b,c,c0,c1)     \
00347     s ## a ## b ## c :                                  \
00348       *target = *seq ## a;                              \
00349       ++target;                                         \
00350       --length;                                         \
00351       ++seq ## a;                                       \
00352       if (length == 0) goto finish;                     \
00353       if (seq ## a c0 seq ## b) goto s ## a ## b ## c;  \
00354       if (seq ## a c1 seq ## c) goto s ## b ## a ## c;  \
00355       goto s ## b ## c ## a;
00356 
00357     _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 1, 2, <=, <=);
00358     _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 2, 0, <=, < );
00359     _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 0, 1, < , < );
00360     _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 0, 2, < , <=);
00361     _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 2, 1, <=, <=);
00362     _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 1, 0, < , < );
00363 
00364 #undef _GLIBCXX_PARALLEL_MERGE_3_CASE
00365 
00366   finish:
00367     ;
00368 
00369 #if _GLIBCXX_ASSERTIONS
00370   _GLIBCXX_PARALLEL_ASSERT(
00371       ((RandomAccessIterator1)seq0 - seqs_begin[0].first) +
00372       ((RandomAccessIterator1)seq1 - seqs_begin[1].first) +
00373       ((RandomAccessIterator1)seq2 - seqs_begin[2].first)
00374       == orig_length);
00375 #endif
00376 
00377     seqs_begin[0].first = seq0;
00378     seqs_begin[1].first = seq1;
00379     seqs_begin[2].first = seq2;
00380 
00381     return target;
00382   }
00383 
00384 /**
00385  * @brief Highly efficient 4-way merging procedure.
00386  *
00387  * Merging is done with the algorithm implementation described by Peter
00388  * Sanders. Basically, the idea is to minimize the number of necessary
00389  * comparison after merging out an element.  The implementation trick
00390  * that makes this fast is that the order of the sequences is stored
00391  * in the instruction pointer (translated into goto labels in C++).
00392  *
00393  * This works well for merging up to 4 sequences.
00394  *
00395  * Note that making the merging stable does <em>not</em> come at a
00396  * performance hit.
00397  *
00398  * Whether the merging is done guarded or unguarded is selected by the
00399  * used iterator class.
00400  *
00401  * @param seqs_begin Begin iterator of iterator pair input sequence.
00402  * @param seqs_end End iterator of iterator pair input sequence.
00403  * @param target Begin iterator out output sequence.
00404  * @param comp Comparator.
00405  * @param length Maximum length to merge, less equal than the
00406  * total number of elements available.
00407  *
00408  * @return End iterator of output sequence.
00409  */
00410 template<template<typename RAI, typename C> class iterator,
00411      typename RandomAccessIteratorIterator,
00412      typename RandomAccessIterator3,
00413      typename _DifferenceTp,
00414      typename Comparator>
00415   RandomAccessIterator3
00416   multiway_merge_4_variant(RandomAccessIteratorIterator seqs_begin,
00417                            RandomAccessIteratorIterator seqs_end,
00418                            RandomAccessIterator3 target,
00419                            Comparator comp, _DifferenceTp length)
00420   {
00421     _GLIBCXX_CALL(length);
00422     typedef _DifferenceTp difference_type;
00423 
00424     typedef typename std::iterator_traits<RandomAccessIteratorIterator>
00425       ::value_type::first_type
00426       RandomAccessIterator1;
00427     typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
00428       value_type;
00429 
00430     iterator<RandomAccessIterator1, Comparator>
00431       seq0(seqs_begin[0].first, seqs_begin[0].second, comp),
00432       seq1(seqs_begin[1].first, seqs_begin[1].second, comp),
00433       seq2(seqs_begin[2].first, seqs_begin[2].second, comp),
00434       seq3(seqs_begin[3].first, seqs_begin[3].second, comp);
00435 
00436 #define _GLIBCXX_PARALLEL_DECISION(a,b,c,d) {                   \
00437       if (seq ## d < seq ## a) goto s ## d ## a ## b ## c;  \
00438       if (seq ## d < seq ## b) goto s ## a ## d ## b ## c;  \
00439       if (seq ## d < seq ## c) goto s ## a ## b ## d ## c;  \
00440       goto s ## a ## b ## c ## d;  }
00441 
00442     if (seq0 <= seq1)
00443       {
00444         if (seq1 <= seq2)
00445           _GLIBCXX_PARALLEL_DECISION(0,1,2,3)
00446           else
00447             if (seq2 < seq0)
00448               _GLIBCXX_PARALLEL_DECISION(2,0,1,3)
00449               else
00450                 _GLIBCXX_PARALLEL_DECISION(0,2,1,3)
00451                   }
00452     else
00453       {
00454         if (seq1 <= seq2)
00455           {
00456             if (seq0 <= seq2)
00457               _GLIBCXX_PARALLEL_DECISION(1,0,2,3)
00458               else
00459                 _GLIBCXX_PARALLEL_DECISION(1,2,0,3)
00460                   }
00461         else
00462           _GLIBCXX_PARALLEL_DECISION(2,1,0,3)
00463             }
00464 
00465 #define _GLIBCXX_PARALLEL_MERGE_4_CASE(a,b,c,d,c0,c1,c2)        \
00466     s ## a ## b ## c ## d:                                      \
00467       if (length == 0) goto finish;                             \
00468     *target = *seq ## a;                                        \
00469     ++target;                                                   \
00470     --length;                                                   \
00471     ++seq ## a;                                                 \
00472     if (seq ## a c0 seq ## b) goto s ## a ## b ## c ## d;       \
00473     if (seq ## a c1 seq ## c) goto s ## b ## a ## c ## d;       \
00474     if (seq ## a c2 seq ## d) goto s ## b ## c ## a ## d;       \
00475     goto s ## b ## c ## d ## a;
00476 
00477     _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 2, 3, <=, <=, <=);
00478     _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 3, 2, <=, <=, <=);
00479     _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 1, 3, <=, <=, <=);
00480     _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 3, 1, <=, <=, <=);
00481     _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 1, 2, <=, <=, <=);
00482     _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 2, 1, <=, <=, <=);
00483     _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 2, 3, < , <=, <=);
00484     _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 3, 2, < , <=, <=);
00485     _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 0, 3, <=, < , <=);
00486     _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 3, 0, <=, <=, < );
00487     _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 0, 2, <=, < , <=);
00488     _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 2, 0, <=, <=, < );
00489     _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 1, 3, < , < , <=);
00490     _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 3, 1, < , <=, < );
00491     _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 0, 3, < , < , <=);
00492     _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 3, 0, < , <=, < );
00493     _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 0, 1, <=, < , < );
00494     _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 1, 0, <=, < , < );
00495     _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 1, 2, < , < , < );
00496     _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 2, 1, < , < , < );
00497     _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 0, 2, < , < , < );
00498     _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 2, 0, < , < , < );
00499     _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 0, 1, < , < , < );
00500     _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 1, 0, < , < , < );
00501 
00502 #undef _GLIBCXX_PARALLEL_MERGE_4_CASE
00503 #undef _GLIBCXX_PARALLEL_DECISION
00504 
00505   finish:
00506     ;
00507 
00508     seqs_begin[0].first = seq0;
00509     seqs_begin[1].first = seq1;
00510     seqs_begin[2].first = seq2;
00511     seqs_begin[3].first = seq3;
00512 
00513     return target;
00514   }
00515 
00516 /** @brief Multi-way merging procedure for a high branching factor,
00517  *         guarded case.
00518  *
00519  * This merging variant uses a LoserTree class as selected by <tt>LT</tt>.
00520  *
00521  * Stability is selected through the used LoserTree class <tt>LT</tt>.
00522  *
00523  * At least one non-empty sequence is required.
00524  *
00525  * @param seqs_begin Begin iterator of iterator pair input sequence.
00526  * @param seqs_end End iterator of iterator pair input sequence.
00527  * @param target Begin iterator out output sequence.
00528  * @param comp Comparator.
00529  * @param length Maximum length to merge, less equal than the
00530  * total number of elements available.
00531  *
00532  * @return End iterator of output sequence.
00533  */
00534 template<typename LT,
00535      typename RandomAccessIteratorIterator,
00536      typename RandomAccessIterator3,
00537      typename _DifferenceTp,
00538      typename Comparator>
00539   RandomAccessIterator3
00540   multiway_merge_loser_tree(RandomAccessIteratorIterator seqs_begin,
00541                             RandomAccessIteratorIterator seqs_end,
00542                             RandomAccessIterator3 target,
00543                             Comparator comp,
00544                             _DifferenceTp length)
00545   {
00546     _GLIBCXX_CALL(length)
00547 
00548     typedef _DifferenceTp difference_type;
00549     typedef typename std::iterator_traits<RandomAccessIteratorIterator>
00550       ::value_type::first_type
00551       RandomAccessIterator1;
00552     typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
00553       value_type;
00554 
00555     int k = static_cast<int>(seqs_end - seqs_begin);
00556 
00557     LT lt(k, comp);
00558 
00559     // Default value for potentially non-default-constructible types.
00560     value_type* arbitrary_element = NULL;
00561 
00562     for (int t = 0; t < k; ++t)
00563       {
00564         if(arbitrary_element == NULL
00565             && _GLIBCXX_PARALLEL_LENGTH(seqs_begin[t]) > 0)
00566           arbitrary_element = &(*seqs_begin[t].first);
00567       }
00568 
00569     for (int t = 0; t < k; ++t)
00570       {
00571         if (seqs_begin[t].first == seqs_begin[t].second)
00572           lt.insert_start(*arbitrary_element, t, true);
00573         else
00574           lt.insert_start(*seqs_begin[t].first, t, false);
00575       }
00576 
00577     lt.init();
00578 
00579     int source;
00580 
00581     for (difference_type i = 0; i < length; ++i)
00582       {
00583         //take out
00584         source = lt.get_min_source();
00585 
00586         *(target++) = *(seqs_begin[source].first++);
00587 
00588         // Feed.
00589         if (seqs_begin[source].first == seqs_begin[source].second)
00590           lt.delete_min_insert(*arbitrary_element, true);
00591         else
00592           // Replace from same source.
00593           lt.delete_min_insert(*seqs_begin[source].first, false);
00594       }
00595 
00596     return target;
00597   }
00598 
00599 /** @brief Multi-way merging procedure for a high branching factor,
00600  *         unguarded case.
00601  *
00602  * Merging is done using the LoserTree class <tt>LT</tt>.
00603  *
00604  * Stability is selected by the used LoserTrees.
00605  *
00606  * @pre No input will run out of elements during the merge.
00607  *
00608  * @param seqs_begin Begin iterator of iterator pair input sequence.
00609  * @param seqs_end End iterator of iterator pair input sequence.
00610  * @param target Begin iterator out output sequence.
00611  * @param comp Comparator.
00612  * @param length Maximum length to merge, less equal than the
00613  * total number of elements available.
00614  *
00615  * @return End iterator of output sequence.
00616  */
00617 template<typename LT,
00618     typename RandomAccessIteratorIterator,
00619     typename RandomAccessIterator3,
00620     typename _DifferenceTp, typename Comparator>
00621   RandomAccessIterator3
00622   multiway_merge_loser_tree_unguarded(
00623     RandomAccessIteratorIterator seqs_begin,
00624     RandomAccessIteratorIterator seqs_end,
00625     RandomAccessIterator3 target,
00626     const typename std::iterator_traits<typename std::iterator_traits<
00627       RandomAccessIteratorIterator>::value_type::first_type>::value_type&
00628         sentinel,
00629     Comparator comp,
00630     _DifferenceTp length)
00631   {
00632     _GLIBCXX_CALL(length)
00633     typedef _DifferenceTp difference_type;
00634 
00635     typedef typename std::iterator_traits<RandomAccessIteratorIterator>
00636       ::value_type::first_type
00637       RandomAccessIterator1;
00638     typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
00639       value_type;
00640 
00641     int k = seqs_end - seqs_begin;
00642 
00643     LT lt(k, sentinel, comp);
00644 
00645     for (int t = 0; t < k; ++t)
00646       {
00647 #if _GLIBCXX_ASSERTIONS
00648         _GLIBCXX_PARALLEL_ASSERT(seqs_begin[t].first != seqs_begin[t].second);
00649 #endif
00650         lt.insert_start(*seqs_begin[t].first, t, false);
00651       }
00652 
00653     lt.init();
00654 
00655     int source;
00656 
00657 #if _GLIBCXX_ASSERTIONS
00658     difference_type i = 0;
00659 #endif
00660 
00661     RandomAccessIterator3 target_end = target + length;
00662     while (target < target_end)
00663       {
00664         // Take out.
00665         source = lt.get_min_source();
00666 
00667 #if _GLIBCXX_ASSERTIONS
00668         _GLIBCXX_PARALLEL_ASSERT(0 <= source && source < k);
00669         _GLIBCXX_PARALLEL_ASSERT(i == 0
00670             || !comp(*(seqs_begin[source].first), *(target - 1)));
00671 #endif
00672 
00673         // Feed.
00674         *(target++) = *(seqs_begin[source].first++);
00675 
00676 #if _GLIBCXX_ASSERTIONS
00677         ++i;
00678 #endif
00679         // Replace from same source.
00680         lt.delete_min_insert(*seqs_begin[source].first, false);
00681       }
00682 
00683     return target;
00684   }
00685 
00686 
00687 /** @brief Multi-way merging procedure for a high branching factor,
00688  *         requiring sentinels to exist.
00689  *
00690  * @param stable The value must the same as for the used LoserTrees.
00691  * @param UnguardedLoserTree Loser Tree variant to use for the unguarded
00692  *   merging.
00693  * @param GuardedLoserTree Loser Tree variant to use for the guarded
00694  *   merging.
00695  *
00696  * @param seqs_begin Begin iterator of iterator pair input sequence.
00697  * @param seqs_end End iterator of iterator pair input sequence.
00698  * @param target Begin iterator out output sequence.
00699  * @param comp Comparator.
00700  * @param length Maximum length to merge, less equal than the
00701  * total number of elements available.
00702  *
00703  * @return End iterator of output sequence.
00704  */
00705 template<
00706     typename UnguardedLoserTree,
00707     typename RandomAccessIteratorIterator,
00708     typename RandomAccessIterator3,
00709     typename _DifferenceTp,
00710     typename Comparator>
00711   RandomAccessIterator3
00712   multiway_merge_loser_tree_sentinel(
00713     RandomAccessIteratorIterator seqs_begin,
00714     RandomAccessIteratorIterator seqs_end,
00715     RandomAccessIterator3 target,
00716     const typename std::iterator_traits<typename std::iterator_traits<
00717       RandomAccessIteratorIterator>::value_type::first_type>::value_type&
00718         sentinel,
00719     Comparator comp,
00720     _DifferenceTp length)
00721   {
00722     _GLIBCXX_CALL(length)
00723 
00724     typedef _DifferenceTp difference_type;
00725     typedef std::iterator_traits<RandomAccessIteratorIterator> traits_type;
00726     typedef typename std::iterator_traits<RandomAccessIteratorIterator>
00727       ::value_type::first_type
00728       RandomAccessIterator1;
00729     typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
00730       value_type;
00731 
00732     RandomAccessIterator3 target_end;
00733 
00734     for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s)
00735       // Move the sequends end behind the sentinel spots.  This has the
00736       // effect that the sentinel appears to be within the sequence. Then,
00737       // we can use the unguarded variant if we merge out as many
00738       // non-sentinel elements as we have.
00739       ++((*s).second);
00740 
00741     target_end = multiway_merge_loser_tree_unguarded
00742         <UnguardedLoserTree>
00743       (seqs_begin, seqs_end, target, sentinel, comp, length);
00744 
00745 #if _GLIBCXX_ASSERTIONS
00746     _GLIBCXX_PARALLEL_ASSERT(target_end == target + length);
00747     _GLIBCXX_PARALLEL_ASSERT(is_sorted(target, target_end, comp));
00748 #endif
00749 
00750     // Restore the sequence ends so the sentinels are not contained in the
00751     // sequence any more (see comment in loop above).
00752     for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s)
00753       --((*s).second);
00754 
00755     return target_end;
00756   }
00757 
00758 /**
00759  * @brief Traits for determining whether the loser tree should
00760  *   use pointers or copies.
00761  *
00762  * The field "use_pointer" is used to determine whether to use pointers in
00763  * the loser trees or whether to copy the values into the loser tree.
00764  *
00765  * The default behavior is to use pointers if the data type is 4 times as
00766  * big as the pointer to it.
00767  *
00768  * Specialize for your data type to customize the behavior.
00769  *
00770  * Example:
00771  *
00772  *   template<>
00773  *   struct loser_tree_traits<int>
00774  *   { static const bool use_pointer = false; };
00775  *
00776  *   template<>
00777  *   struct loser_tree_traits<heavyweight_type>
00778  *   { static const bool use_pointer = true; };
00779  *
00780  * @param T type to give the loser tree traits for.
00781  */
00782 template <typename T>
00783 struct loser_tree_traits
00784 {
00785   /**
00786    * @brief True iff to use pointers instead of values in loser trees.
00787    *
00788    * The default behavior is to use pointers if the data type is four
00789    * times as big as the pointer to it.
00790    */
00791   static const bool use_pointer = (sizeof(T) > 4 * sizeof(T*));
00792 };
00793 
00794 /**
00795  * @brief Switch for 3-way merging with sentinels turned off.
00796  *
00797  * Note that 3-way merging is always stable!
00798  */
00799 template<
00800   bool sentinels /*default == false*/,
00801   typename RandomAccessIteratorIterator,
00802   typename RandomAccessIterator3,
00803   typename _DifferenceTp,
00804   typename Comparator>
00805 struct multiway_merge_3_variant_sentinel_switch
00806 {
00807   RandomAccessIterator3 operator()(
00808       RandomAccessIteratorIterator seqs_begin,
00809       RandomAccessIteratorIterator seqs_end,
00810       RandomAccessIterator3 target,
00811       Comparator comp, _DifferenceTp length)
00812   {
00813     return multiway_merge_3_variant<guarded_iterator>(
00814         seqs_begin, seqs_end, target, comp, length);
00815   }
00816 };
00817 
00818 /**
00819  * @brief Switch for 3-way merging with sentinels turned on.
00820  *
00821  * Note that 3-way merging is always stable!
00822  */
00823 template<
00824   typename RandomAccessIteratorIterator,
00825   typename RandomAccessIterator3,
00826   typename _DifferenceTp,
00827   typename Comparator>
00828 struct multiway_merge_3_variant_sentinel_switch
00829     <true, RandomAccessIteratorIterator, RandomAccessIterator3,
00830      _DifferenceTp, Comparator>
00831 {
00832   RandomAccessIterator3 operator()(
00833       RandomAccessIteratorIterator seqs_begin,
00834       RandomAccessIteratorIterator seqs_end,
00835       RandomAccessIterator3 target,
00836       Comparator comp, _DifferenceTp length)
00837   {
00838     return multiway_merge_3_variant<unguarded_iterator>(
00839         seqs_begin, seqs_end, target, comp, length);
00840   }
00841 };
00842 
00843 /**
00844  * @brief Switch for 4-way merging with sentinels turned off.
00845  *
00846  * Note that 4-way merging is always stable!
00847  */
00848 template<
00849   bool sentinels /*default == false*/,
00850   typename RandomAccessIteratorIterator,
00851   typename RandomAccessIterator3,
00852   typename _DifferenceTp,
00853   typename Comparator>
00854 struct multiway_merge_4_variant_sentinel_switch
00855 {
00856   RandomAccessIterator3 operator()(
00857       RandomAccessIteratorIterator seqs_begin,
00858       RandomAccessIteratorIterator seqs_end,
00859       RandomAccessIterator3 target,
00860       Comparator comp, _DifferenceTp length)
00861   {
00862     return multiway_merge_4_variant<guarded_iterator>(
00863         seqs_begin, seqs_end, target, comp, length);
00864   }
00865 };
00866 
00867 /**
00868  * @brief Switch for 4-way merging with sentinels turned on.
00869  *
00870  * Note that 4-way merging is always stable!
00871  */
00872 template<
00873   typename RandomAccessIteratorIterator,
00874   typename RandomAccessIterator3,
00875   typename _DifferenceTp,
00876   typename Comparator>
00877 struct multiway_merge_4_variant_sentinel_switch
00878     <true, RandomAccessIteratorIterator, RandomAccessIterator3,
00879      _DifferenceTp, Comparator>
00880 {
00881   RandomAccessIterator3 operator()(
00882       RandomAccessIteratorIterator seqs_begin,
00883       RandomAccessIteratorIterator seqs_end,
00884       RandomAccessIterator3 target,
00885       Comparator comp, _DifferenceTp length)
00886   {
00887     return multiway_merge_4_variant<unguarded_iterator>(
00888         seqs_begin, seqs_end, target, comp, length);
00889   }
00890 };
00891 
00892 /**
00893  * @brief Switch for k-way merging with sentinels turned on.
00894  */
00895 template<
00896   bool sentinels,
00897   bool stable,
00898   typename RandomAccessIteratorIterator,
00899   typename RandomAccessIterator3,
00900   typename _DifferenceTp,
00901   typename Comparator>
00902 struct multiway_merge_k_variant_sentinel_switch
00903 {
00904   RandomAccessIterator3 operator()(
00905       RandomAccessIteratorIterator seqs_begin,
00906       RandomAccessIteratorIterator seqs_end,
00907       RandomAccessIterator3 target,
00908       const typename std::iterator_traits<typename std::iterator_traits<
00909         RandomAccessIteratorIterator>::value_type::first_type>::value_type&
00910           sentinel,
00911       Comparator comp, _DifferenceTp length)
00912   {
00913     typedef typename std::iterator_traits<RandomAccessIteratorIterator>
00914       ::value_type::first_type
00915       RandomAccessIterator1;
00916     typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
00917       value_type;
00918 
00919     return multiway_merge_loser_tree_sentinel<
00920         typename __gnu_cxx::__conditional_type<
00921             loser_tree_traits<value_type>::use_pointer
00922           , LoserTreePointerUnguarded<stable, value_type, Comparator>
00923           , LoserTreeUnguarded<stable, value_type, Comparator>
00924         >::__type>(seqs_begin, seqs_end, target, sentinel, comp, length);
00925   }
00926 };
00927 
00928 /**
00929  * @brief Switch for k-way merging with sentinels turned off.
00930  */
00931 template<
00932   bool stable,
00933   typename RandomAccessIteratorIterator,
00934   typename RandomAccessIterator3,
00935   typename _DifferenceTp,
00936   typename Comparator>
00937 struct multiway_merge_k_variant_sentinel_switch
00938     <false, stable, RandomAccessIteratorIterator, RandomAccessIterator3,
00939      _DifferenceTp, Comparator>
00940 {
00941   RandomAccessIterator3 operator()(
00942       RandomAccessIteratorIterator seqs_begin,
00943       RandomAccessIteratorIterator seqs_end,
00944       RandomAccessIterator3 target,
00945       const typename std::iterator_traits<typename std::iterator_traits<
00946         RandomAccessIteratorIterator>::value_type::first_type>::value_type&
00947           sentinel,
00948       Comparator comp, _DifferenceTp length)
00949   {
00950     typedef typename std::iterator_traits<RandomAccessIteratorIterator>
00951       ::value_type::first_type
00952       RandomAccessIterator1;
00953     typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
00954       value_type;
00955 
00956     return multiway_merge_loser_tree<
00957         typename __gnu_cxx::__conditional_type<
00958             loser_tree_traits<value_type>::use_pointer
00959           , LoserTreePointer<stable, value_type, Comparator>
00960           , LoserTree<stable, value_type, Comparator>
00961         >::__type >(seqs_begin, seqs_end, target, comp, length);
00962   }
00963 };
00964 
00965 /** @brief Sequential multi-way merging switch.
00966  *
00967  *  The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and
00968  *  runtime settings.
00969  *  @param seqs_begin Begin iterator of iterator pair input sequence.
00970  *  @param seqs_end End iterator of iterator pair input sequence.
00971  *  @param target Begin iterator out output sequence.
00972  *  @param comp Comparator.
00973  *  @param length Maximum length to merge, possibly larger than the
00974  *  number of elements available.
00975  *  @param stable Stable merging incurs a performance penalty.
00976  *  @param sentinel The sequences have a sentinel element.
00977  *  @return End iterator of output sequence. */
00978 template<
00979     bool stable,
00980     bool sentinels,
00981     typename RandomAccessIteratorIterator,
00982     typename RandomAccessIterator3,
00983     typename _DifferenceTp,
00984     typename Comparator>
00985   RandomAccessIterator3
00986   sequential_multiway_merge(
00987     RandomAccessIteratorIterator seqs_begin,
00988     RandomAccessIteratorIterator seqs_end,
00989     RandomAccessIterator3 target,
00990     const typename std::iterator_traits<typename std::iterator_traits<
00991       RandomAccessIteratorIterator>::value_type::first_type>::value_type&
00992         sentinel,
00993     Comparator comp, _DifferenceTp length)
00994   {
00995     _GLIBCXX_CALL(length)
00996 
00997     typedef _DifferenceTp difference_type;
00998     typedef typename std::iterator_traits<RandomAccessIteratorIterator>
00999       ::value_type::first_type
01000       RandomAccessIterator1;
01001     typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
01002       value_type;
01003 
01004 #if _GLIBCXX_ASSERTIONS
01005     for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s)
01006       {
01007         _GLIBCXX_PARALLEL_ASSERT(is_sorted((*s).first, (*s).second, comp));
01008       }
01009 #endif
01010 
01011     _DifferenceTp total_length = 0;
01012     for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s)
01013       total_length += _GLIBCXX_PARALLEL_LENGTH(*s);
01014 
01015     length = std::min<_DifferenceTp>(length, total_length);
01016 
01017     if(length == 0)
01018       return target;
01019 
01020     RandomAccessIterator3 return_target = target;
01021     int k = static_cast<int>(seqs_end - seqs_begin);
01022 
01023     switch (k)
01024       {
01025       case 0:
01026         break;
01027       case 1:
01028         return_target = std::copy(seqs_begin[0].first,
01029                                   seqs_begin[0].first + length,
01030                                   target);
01031         seqs_begin[0].first += length;
01032         break;
01033       case 2:
01034         return_target = merge_advance(seqs_begin[0].first,
01035                                       seqs_begin[0].second,
01036                                       seqs_begin[1].first,
01037                                       seqs_begin[1].second,
01038                                       target, length, comp);
01039         break;
01040       case 3:
01041         return_target = multiway_merge_3_variant_sentinel_switch<
01042             sentinels
01043           , RandomAccessIteratorIterator
01044           , RandomAccessIterator3
01045           , _DifferenceTp
01046           , Comparator>()(seqs_begin, seqs_end, target, comp, length);
01047         break;
01048       case 4:
01049         return_target = multiway_merge_4_variant_sentinel_switch<
01050             sentinels
01051           , RandomAccessIteratorIterator
01052           , RandomAccessIterator3
01053           , _DifferenceTp
01054           , Comparator>()(seqs_begin, seqs_end, target, comp, length);
01055         break;
01056       default:
01057           return_target = multiway_merge_k_variant_sentinel_switch<
01058               sentinels
01059             , stable
01060             , RandomAccessIteratorIterator
01061             , RandomAccessIterator3
01062             , _DifferenceTp
01063             , Comparator>()
01064                 (seqs_begin, seqs_end, target, sentinel, comp, length);
01065           break;
01066       }
01067 #if _GLIBCXX_ASSERTIONS
01068     _GLIBCXX_PARALLEL_ASSERT(is_sorted(target, target + length, comp));
01069 #endif
01070 
01071     return return_target;
01072   }
01073 
01074 /**
01075  * @brief Stable sorting functor.
01076  *
01077  * Used to reduce code instanciation in multiway_merge_sampling_splitting.
01078  */
01079 template<bool stable, class RandomAccessIterator, class StrictWeakOrdering>
01080 struct sampling_sorter
01081 {
01082   void operator()(RandomAccessIterator first, RandomAccessIterator last,
01083                   StrictWeakOrdering comp)
01084   { __gnu_sequential::stable_sort(first, last, comp); }
01085 };
01086 
01087 /**
01088  * @brief Non-stable sorting functor.
01089  *
01090  * Used to reduce code instantiation in multiway_merge_sampling_splitting.
01091  */
01092 template<class RandomAccessIterator, class StrictWeakOrdering>
01093 struct sampling_sorter<false, RandomAccessIterator, StrictWeakOrdering>
01094 {
01095   void operator()(RandomAccessIterator first, RandomAccessIterator last,
01096                   StrictWeakOrdering comp)
01097   { __gnu_sequential::sort(first, last, comp); }
01098 };
01099 
01100 /**
01101  * @brief Sampling based splitting for parallel multiway-merge routine.
01102  */
01103 template<
01104     bool stable
01105   , typename RandomAccessIteratorIterator
01106   , typename Comparator
01107   , typename difference_type>
01108 void multiway_merge_sampling_splitting(
01109     RandomAccessIteratorIterator seqs_begin,
01110     RandomAccessIteratorIterator seqs_end,
01111     Comparator comp, difference_type length,
01112     difference_type total_length,
01113     std::vector<std::pair<difference_type, difference_type> > *pieces)
01114 {
01115   typedef typename std::iterator_traits<RandomAccessIteratorIterator>
01116     ::value_type::first_type
01117     RandomAccessIterator1;
01118   typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
01119     value_type;
01120 
01121   // k sequences.
01122   int k = static_cast<int>(seqs_end - seqs_begin);
01123 
01124   int num_threads = omp_get_num_threads();
01125 
01126   difference_type num_samples =
01127       __gnu_parallel::_Settings::get().merge_oversampling * num_threads;
01128 
01129   value_type* samples = static_cast<value_type*>(
01130     ::operator new(sizeof(value_type) * k * num_samples));
01131   // Sample.
01132   for (int s = 0; s < k; ++s)
01133     for (difference_type i = 0; i < num_samples; ++i)
01134       {
01135         difference_type sample_index =
01136             static_cast<difference_type>(
01137                 _GLIBCXX_PARALLEL_LENGTH(seqs_begin[s])
01138                     * (double(i + 1) / (num_samples + 1))
01139                     * (double(length) / total_length));
01140         new(&(samples[s * num_samples + i]))
01141             value_type(seqs_begin[s].first[sample_index]);
01142       }
01143 
01144   // Sort stable or non-stable, depending on value of template parameter
01145   // "stable".
01146   sampling_sorter<stable, value_type*, Comparator>()(
01147       samples, samples + (num_samples * k), comp);
01148 
01149   for (int slab = 0; slab < num_threads; ++slab)
01150     // For each slab / processor.
01151     for (int seq = 0; seq < k; ++seq)
01152       {
01153         // For each sequence.
01154         if (slab > 0)
01155           pieces[slab][seq].first =
01156               std::upper_bound(
01157                 seqs_begin[seq].first,
01158                 seqs_begin[seq].second,
01159                 samples[num_samples * k * slab / num_threads],
01160                   comp)
01161               - seqs_begin[seq].first;
01162         else
01163           // Absolute beginning.
01164           pieces[slab][seq].first = 0;
01165         if ((slab + 1) < num_threads)
01166           pieces[slab][seq].second =
01167               std::upper_bound(
01168                   seqs_begin[seq].first,
01169                   seqs_begin[seq].second,
01170                   samples[num_samples * k * (slab + 1) /
01171                       num_threads], comp)
01172               - seqs_begin[seq].first;
01173         else
01174             // Absolute end.
01175           pieces[slab][seq].second = _GLIBCXX_PARALLEL_LENGTH(seqs_begin[seq]);
01176       }
01177     ::operator delete(samples);
01178 }
01179 
01180 /**
01181  * @brief Exact splitting for parallel multiway-merge routine.
01182  *
01183  * None of the passed sequences may be empty.
01184  */
01185 template<
01186     bool stable
01187   , typename RandomAccessIteratorIterator
01188   , typename Comparator
01189   , typename difference_type>
01190 void multiway_merge_exact_splitting(
01191     RandomAccessIteratorIterator seqs_begin,
01192     RandomAccessIteratorIterator seqs_end,
01193     Comparator comp,
01194     difference_type length,
01195     difference_type total_length,
01196     std::vector<std::pair<difference_type, difference_type> > *pieces)
01197 {
01198   typedef typename std::iterator_traits<RandomAccessIteratorIterator>
01199     ::value_type::first_type
01200     RandomAccessIterator1;
01201 
01202   const bool tight = (total_length == length);
01203 
01204   // k sequences.
01205   const int k = static_cast<int>(seqs_end - seqs_begin);
01206 
01207   const int num_threads = omp_get_num_threads();
01208 
01209   // (Settings::multiway_merge_splitting == __gnu_parallel::_Settings::EXACT).
01210   std::vector<RandomAccessIterator1>* offsets =
01211       new std::vector<RandomAccessIterator1>[num_threads];
01212   std::vector<
01213       std::pair<RandomAccessIterator1, RandomAccessIterator1>
01214       > se(k);
01215 
01216   copy(seqs_begin, seqs_end, se.begin());
01217 
01218   difference_type* borders =
01219       new difference_type[num_threads + 1];
01220   equally_split(length, num_threads, borders);
01221 
01222   for (int s = 0; s < (num_threads - 1); ++s)
01223     {
01224       offsets[s].resize(k);
01225       multiseq_partition(
01226           se.begin(), se.end(), borders[s + 1],
01227           offsets[s].begin(), comp);
01228 
01229       // Last one also needed and available.
01230       if (!tight)
01231         {
01232           offsets[num_threads - 1].resize(k);
01233           multiseq_partition(se.begin(), se.end(),
01234                 difference_type(length),
01235                 offsets[num_threads - 1].begin(),  comp);
01236         }
01237     }
01238 
01239 
01240   for (int slab = 0; slab < num_threads; ++slab)
01241     {
01242       // For each slab / processor.
01243       for (int seq = 0; seq < k; ++seq)
01244         {
01245           // For each sequence.
01246           if (slab == 0)
01247             {
01248               // Absolute beginning.
01249               pieces[slab][seq].first = 0;
01250             }
01251           else
01252             pieces[slab][seq].first =
01253                 pieces[slab - 1][seq].second;
01254           if (!tight || slab < (num_threads - 1))
01255             pieces[slab][seq].second =
01256                 offsets[slab][seq] - seqs_begin[seq].first;
01257           else
01258             {
01259               // slab == num_threads - 1
01260               pieces[slab][seq].second =
01261                   _GLIBCXX_PARALLEL_LENGTH(seqs_begin[seq]);
01262             }
01263         }
01264     }
01265   delete[] offsets;
01266 }
01267 
01268 /** @brief Parallel multi-way merge routine.
01269  *
01270  * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor
01271  * and runtime settings.
01272  *
01273  * Must not be called if the number of sequences is 1.
01274  *
01275  * @param Splitter functor to split input (either exact or sampling based)
01276  *
01277  * @param seqs_begin Begin iterator of iterator pair input sequence.
01278  * @param seqs_end End iterator of iterator pair input sequence.
01279  * @param target Begin iterator out output sequence.
01280  * @param comp Comparator.
01281  * @param length Maximum length to merge, possibly larger than the
01282  * number of elements available.
01283  * @param stable Stable merging incurs a performance penalty.
01284  * @param sentinel Ignored.
01285  * @return End iterator of output sequence.
01286  */
01287 template<
01288     bool stable,
01289     bool sentinels,
01290     typename RandomAccessIteratorIterator,
01291     typename RandomAccessIterator3,
01292     typename _DifferenceTp,
01293     typename Splitter,
01294     typename Comparator
01295     >
01296   RandomAccessIterator3
01297   parallel_multiway_merge(RandomAccessIteratorIterator seqs_begin,
01298                           RandomAccessIteratorIterator seqs_end,
01299                           RandomAccessIterator3 target,
01300                           Comparator comp,
01301                           Splitter splitter,
01302                           _DifferenceTp length)
01303     {
01304 #if _GLIBCXX_ASSERTIONS
01305       _GLIBCXX_PARALLEL_ASSERT(seqs_end - seqs_begin > 1);
01306 #endif
01307 
01308       _GLIBCXX_CALL(length)
01309 
01310       typedef _DifferenceTp difference_type;
01311       typedef typename std::iterator_traits<RandomAccessIteratorIterator>
01312         ::value_type::first_type
01313         RandomAccessIterator1;
01314       typedef typename
01315         std::iterator_traits<RandomAccessIterator1>::value_type value_type;
01316 
01317       // Leave only non-empty sequences.
01318       std::pair<RandomAccessIterator1, RandomAccessIterator1>* ne_seqs =
01319         static_cast<std::pair<RandomAccessIterator1, RandomAccessIterator1>*>(
01320         ::operator new(
01321             sizeof(std::pair<RandomAccessIterator1, RandomAccessIterator1>)
01322               * (seqs_end - seqs_begin)));
01323       int k = 0;
01324       difference_type total_length = 0;
01325       for (RandomAccessIteratorIterator raii = seqs_begin;
01326            raii != seqs_end; ++raii)
01327         {
01328           _DifferenceTp seq_length = _GLIBCXX_PARALLEL_LENGTH(*raii);
01329           if(seq_length > 0)
01330             {
01331               total_length += seq_length;
01332               //ne_seqs[k] = *raii;
01333               new(&(ne_seqs[k++]))
01334                 std::pair<RandomAccessIterator1, RandomAccessIterator1>(*raii);
01335             }
01336         }
01337 
01338       _GLIBCXX_CALL(total_length)
01339 
01340       length = std::min<_DifferenceTp>(length, total_length);
01341 
01342       if (total_length == 0 || k == 0)
01343       {
01344         ::operator delete(ne_seqs);
01345         return target;
01346       }
01347 
01348       std::vector<std::pair<difference_type, difference_type> >* pieces;
01349 
01350       thread_index_t num_threads = static_cast<thread_index_t>
01351         (std::min<difference_type>(get_max_threads(), total_length));
01352 
01353 #     pragma omp parallel num_threads (num_threads)
01354         {
01355 #         pragma omp single
01356             {
01357               num_threads = omp_get_num_threads();
01358               // Thread t will have to merge pieces[iam][0..k - 1]
01359               pieces = new std::vector<
01360                   std::pair<difference_type, difference_type> >[num_threads];
01361               for (int s = 0; s < num_threads; ++s)
01362                 pieces[s].resize(k);
01363 
01364               difference_type num_samples =
01365                   __gnu_parallel::_Settings::get().merge_oversampling *
01366                     num_threads;
01367 
01368               splitter(ne_seqs, ne_seqs + k, comp, length, total_length,
01369                        pieces);
01370             } //single
01371 
01372           thread_index_t iam = omp_get_thread_num();
01373 
01374           difference_type target_position = 0;
01375 
01376           for (int c = 0; c < k; ++c)
01377             target_position += pieces[iam][c].first;
01378 
01379           std::pair<RandomAccessIterator1, RandomAccessIterator1>* chunks
01380             = new std::pair<RandomAccessIterator1, RandomAccessIterator1>[k];
01381 
01382           for (int s = 0; s < k; ++s)
01383             {
01384               chunks[s] = std::make_pair(
01385                 ne_seqs[s].first + pieces[iam][s].first,
01386                 ne_seqs[s].first + pieces[iam][s].second);
01387             }
01388 
01389           if(length > target_position)
01390             sequential_multiway_merge<stable, sentinels>(
01391               chunks, chunks + k, target + target_position,
01392               *(seqs_begin->second), comp, length - target_position);
01393 
01394           delete[] chunks;
01395         } // parallel
01396 
01397 #if _GLIBCXX_ASSERTIONS
01398       _GLIBCXX_PARALLEL_ASSERT(is_sorted(target, target + length, comp));
01399 #endif
01400 
01401       k = 0;
01402       // Update ends of sequences.
01403       for (RandomAccessIteratorIterator raii = seqs_begin;
01404            raii != seqs_end; ++raii)
01405         {
01406           _DifferenceTp length = _GLIBCXX_PARALLEL_LENGTH(*raii);
01407           if(length > 0)
01408             (*raii).first += pieces[num_threads - 1][k++].second;
01409         }
01410 
01411       delete[] pieces;
01412 
01413       return target + length;
01414     }
01415 
01416 /**
01417  * @brief Multiway Merge Frontend.
01418  *
01419  * Merge the sequences specified by seqs_begin and seqs_end into
01420  * target.  seqs_begin and seqs_end must point to a sequence of
01421  * pairs.  These pairs must contain an iterator to the beginning
01422  * of a sequence in their first entry and an iterator the end of
01423  * the same sequence in their second entry.
01424  *
01425  * Ties are broken arbitrarily.  See stable_multiway_merge for a variant
01426  * that breaks ties by sequence number but is slower.
01427  *
01428  * The first entries of the pairs (i.e. the begin iterators) will be moved
01429  * forward.
01430  *
01431  * The output sequence has to provide enough space for all elements
01432  * that are written to it.
01433  *
01434  * This function will merge the input sequences:
01435  *
01436  * - not stable
01437  * - parallel, depending on the input size and Settings
01438  * - using sampling for splitting
01439  * - not using sentinels
01440  *
01441  * Example:
01442  *
01443  * <pre>
01444  *   int sequences[10][10];
01445  *   for (int i = 0; i < 10; ++i)
01446  *     for (int j = 0; i < 10; ++j)
01447  *       sequences[i][j] = j;
01448  *
01449  *   int out[33];
01450  *   std::vector<std::pair<int*> > seqs;
01451  *   for (int i = 0; i < 10; ++i)
01452  *     { seqs.push(std::make_pair<int*>(sequences[i], sequences[i] + 10)) }
01453  *
01454  *   multiway_merge(seqs.begin(), seqs.end(), target, std::less<int>(), 33);
01455  * </pre>
01456  *
01457  * @see stable_multiway_merge
01458  *
01459  * @pre All input sequences must be sorted.
01460  * @pre Target must provide enough space to merge out length elements or
01461  *    the number of elements in all sequences, whichever is smaller.
01462  *
01463  * @post [target, return value) contains merged elements from the
01464  *    input sequences.
01465  * @post return value - target = min(length, number of elements in all
01466  *    sequences).
01467  *
01468  * @param RandomAccessIteratorPairIterator iterator over sequence
01469  *    of pairs of iterators
01470  * @param RandomAccessIteratorOut iterator over target sequence
01471  * @param _DifferenceTp difference type for the sequence
01472  * @param Comparator strict weak ordering type to compare elements
01473  *    in sequences
01474  *
01475  * @param seqs_begin  begin of sequence sequence
01476  * @param seqs_end    end of sequence sequence
01477  * @param target      target sequence to merge to.
01478  * @param comp        strict weak ordering to use for element comparison.
01479  * @param length Maximum length to merge, possibly larger than the
01480  * number of elements available.
01481  *
01482  * @return end iterator of output sequence
01483  */
01484 // public interface
01485 template<
01486     typename RandomAccessIteratorPairIterator
01487   , typename RandomAccessIteratorOut
01488   , typename _DifferenceTp
01489   , typename Comparator>
01490 RandomAccessIteratorOut
01491 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01492     , RandomAccessIteratorPairIterator seqs_end
01493     , RandomAccessIteratorOut target
01494     , Comparator comp, _DifferenceTp length)
01495 {
01496   typedef _DifferenceTp difference_type;
01497   _GLIBCXX_CALL(seqs_end - seqs_begin)
01498 
01499   // catch special case: no sequences
01500   if (seqs_begin == seqs_end)
01501     return target;
01502 
01503   // Execute merge; maybe parallel, depending on the number of merged
01504   // elements and the number of sequences and global thresholds in
01505   // Settings.
01506   if ((seqs_end - seqs_begin > 1) &&
01507         _GLIBCXX_PARALLEL_CONDITION(
01508         ((seqs_end - seqs_begin) >=
01509         __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01510         && ((sequence_index_t)length >=
01511         __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01512     return parallel_multiway_merge
01513       </* stable = */ false, /* sentinels = */ false>
01514         (seqs_begin, seqs_end, target, comp,
01515         multiway_merge_sampling_splitting</* stable = */ false,
01516           typename std::iterator_traits<RandomAccessIteratorPairIterator>
01517             ::value_type*, Comparator, _DifferenceTp>,
01518         static_cast<difference_type>(length));
01519   else
01520     return sequential_multiway_merge
01521       </* stable = */false, /* sentinels = */ false>(
01522         seqs_begin, seqs_end,
01523         target, *(seqs_begin->second), comp, length);
01524 }
01525 
01526 // public interface
01527 template<
01528     typename RandomAccessIteratorPairIterator
01529   , typename RandomAccessIteratorOut
01530   , typename _DifferenceTp
01531   , typename Comparator>
01532 RandomAccessIteratorOut
01533 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01534     , RandomAccessIteratorPairIterator seqs_end
01535     , RandomAccessIteratorOut target
01536     , Comparator comp, _DifferenceTp length
01537     , __gnu_parallel::sequential_tag)
01538 {
01539   typedef _DifferenceTp difference_type;
01540   _GLIBCXX_CALL(seqs_end - seqs_begin)
01541 
01542   // catch special case: no sequences
01543   if (seqs_begin == seqs_end)
01544     return target;
01545 
01546   // Execute multiway merge *sequentially*.
01547   return sequential_multiway_merge
01548     </* stable = */ false, /* sentinels = */ false>
01549       (seqs_begin, seqs_end, target, *(seqs_begin->second), comp, length);
01550 }
01551 
01552 //public interface
01553 template<
01554     typename RandomAccessIteratorPairIterator
01555   , typename RandomAccessIteratorOut
01556   , typename _DifferenceTp
01557   , typename Comparator>
01558 RandomAccessIteratorOut
01559 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01560     , RandomAccessIteratorPairIterator seqs_end
01561     , RandomAccessIteratorOut target
01562     , Comparator comp, _DifferenceTp length
01563     , __gnu_parallel::exact_tag)
01564 {
01565     typedef _DifferenceTp difference_type;
01566     _GLIBCXX_CALL(seqs_end - seqs_begin)
01567 
01568     // catch special case: no sequences
01569     if (seqs_begin == seqs_end)
01570       return target;
01571 
01572     // Execute merge; maybe parallel, depending on the number of merged
01573     // elements and the number of sequences and global thresholds in
01574     // Settings.
01575     if ((seqs_end - seqs_begin > 1) &&
01576           _GLIBCXX_PARALLEL_CONDITION(
01577           ((seqs_end - seqs_begin) >=
01578              __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01579           && ((sequence_index_t)length >=
01580             __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01581       return parallel_multiway_merge
01582                     </* stable = */ false, /* sentinels = */ false>(
01583           seqs_begin, seqs_end,
01584           target, comp,
01585           multiway_merge_exact_splitting</* stable = */ false,
01586             typename std::iterator_traits<RandomAccessIteratorPairIterator>
01587               ::value_type*, Comparator, _DifferenceTp>,
01588           static_cast<difference_type>(length));
01589     else
01590       return sequential_multiway_merge
01591                       </* stable = */ false, /* sentinels = */ false>(
01592           seqs_begin, seqs_end,
01593           target, *(seqs_begin->second), comp, length);
01594 }
01595 
01596 // public interface
01597 template<
01598     typename RandomAccessIteratorPairIterator
01599   , typename RandomAccessIteratorOut
01600   , typename _DifferenceTp
01601   , typename Comparator>
01602 RandomAccessIteratorOut
01603 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01604     , RandomAccessIteratorPairIterator seqs_end
01605     , RandomAccessIteratorOut target
01606     , Comparator comp, _DifferenceTp length)
01607 {
01608     typedef _DifferenceTp difference_type;
01609     _GLIBCXX_CALL(seqs_end - seqs_begin)
01610 
01611     // catch special case: no sequences
01612     if (seqs_begin == seqs_end)
01613       return target;
01614 
01615     // Execute merge; maybe parallel, depending on the number of merged
01616     // elements and the number of sequences and global thresholds in
01617     // Settings.
01618     if ((seqs_end - seqs_begin > 1) &&
01619           _GLIBCXX_PARALLEL_CONDITION(
01620           ((seqs_end - seqs_begin) >=
01621             __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01622           && ((sequence_index_t)length >=
01623             __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01624       return parallel_multiway_merge
01625         </* stable = */ true, /* sentinels = */ false>(
01626           seqs_begin, seqs_end,
01627           target, comp,
01628           multiway_merge_sampling_splitting</* stable = */ true,
01629             typename std::iterator_traits<RandomAccessIteratorPairIterator>
01630               ::value_type*, Comparator, _DifferenceTp>,
01631           static_cast<difference_type>(length));
01632     else
01633       return sequential_multiway_merge
01634         </* stable = */ true, /* sentinels = */ false>(
01635           seqs_begin, seqs_end,
01636           target, *(seqs_begin->second), comp, length);
01637 }
01638 
01639 // public interface
01640 template<
01641     typename RandomAccessIteratorPairIterator
01642   , typename RandomAccessIteratorOut
01643   , typename _DifferenceTp
01644   , typename Comparator>
01645 RandomAccessIteratorOut
01646 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01647     , RandomAccessIteratorPairIterator seqs_end
01648     , RandomAccessIteratorOut target
01649     , Comparator comp, _DifferenceTp length
01650     , __gnu_parallel::sequential_tag)
01651 {
01652     typedef _DifferenceTp difference_type;
01653     _GLIBCXX_CALL(seqs_end - seqs_begin)
01654 
01655     // catch special case: no sequences
01656     if (seqs_begin == seqs_end)
01657       return target;
01658 
01659     // Execute multiway merge *sequentially*.
01660     return sequential_multiway_merge
01661       </* stable = */ true, /* sentinels = */ false>
01662         (seqs_begin, seqs_end, target, *(seqs_begin->second), comp, length);
01663 }
01664 
01665 // public interface
01666 template<
01667     typename RandomAccessIteratorPairIterator
01668   , typename RandomAccessIteratorOut
01669   , typename _DifferenceTp
01670   , typename Comparator>
01671 RandomAccessIteratorOut
01672 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01673     , RandomAccessIteratorPairIterator seqs_end
01674     , RandomAccessIteratorOut target
01675     , Comparator comp, _DifferenceTp length
01676     , __gnu_parallel::exact_tag)
01677 {
01678     typedef _DifferenceTp difference_type;
01679     _GLIBCXX_CALL(seqs_end - seqs_begin)
01680 
01681     // catch special case: no sequences
01682     if (seqs_begin == seqs_end)
01683       return target;
01684 
01685     // Execute merge; maybe parallel, depending on the number of merged
01686     // elements and the number of sequences and global thresholds in
01687     // Settings.
01688     if ((seqs_end - seqs_begin > 1) &&
01689           _GLIBCXX_PARALLEL_CONDITION(
01690           ((seqs_end - seqs_begin) >=
01691             __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01692           && ((sequence_index_t)length >=
01693             __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01694       return parallel_multiway_merge
01695         </* stable = */ true, /* sentinels = */ false>(
01696           seqs_begin, seqs_end,
01697           target, comp, 
01698           multiway_merge_exact_splitting
01699             </* stable = */ true,
01700               typename std::iterator_traits<RandomAccessIteratorPairIterator>
01701                 ::value_type*, Comparator, _DifferenceTp>,
01702           static_cast<difference_type>(length));
01703     else
01704       return sequential_multiway_merge</* stable = */ true,
01705         /* sentinels = */ false>(
01706           seqs_begin, seqs_end,
01707           target, *(seqs_begin->second), comp, length);
01708 }
01709 
01710 /**
01711  * @brief Multiway Merge Frontend.
01712  *
01713  * Merge the sequences specified by seqs_begin and seqs_end into
01714  * target.  seqs_begin and seqs_end must point to a sequence of
01715  * pairs.  These pairs must contain an iterator to the beginning
01716  * of a sequence in their first entry and an iterator the end of
01717  * the same sequence in their second entry.
01718  *
01719  * Ties are broken arbitrarily.  See stable_multiway_merge for a variant
01720  * that breaks ties by sequence number but is slower.
01721  *
01722  * The first entries of the pairs (i.e. the begin iterators) will be moved
01723  * forward accordingly.
01724  *
01725  * The output sequence has to provide enough space for all elements
01726  * that are written to it.
01727  *
01728  * This function will merge the input sequences:
01729  *
01730  * - not stable
01731  * - parallel, depending on the input size and Settings
01732  * - using sampling for splitting
01733  * - using sentinels
01734  *
01735  * You have to take care that the element the end iterator points to is
01736  * readable and contains a value that is greater than any other non-sentinel
01737  * value in all sequences.
01738  *
01739  * Example:
01740  *
01741  * <pre>
01742  *   int sequences[10][11];
01743  *   for (int i = 0; i < 10; ++i)
01744  *     for (int j = 0; i < 11; ++j)
01745  *       sequences[i][j] = j; // last one is sentinel!
01746  *
01747  *   int out[33];
01748  *   std::vector<std::pair<int*> > seqs;
01749  *   for (int i = 0; i < 10; ++i)
01750  *     { seqs.push(std::make_pair<int*>(sequences[i], sequences[i] + 10)) }
01751  *
01752  *   multiway_merge(seqs.begin(), seqs.end(), target, std::less<int>(), 33);
01753  * </pre>
01754  *
01755  * @pre All input sequences must be sorted.
01756  * @pre Target must provide enough space to merge out length elements or
01757  *    the number of elements in all sequences, whichever is smaller.
01758  * @pre For each @c i, @c seqs_begin[i].second must be the end
01759  *    marker of the sequence, but also reference the one more sentinel
01760  *    element.
01761  *
01762  * @post [target, return value) contains merged elements from the
01763  *    input sequences.
01764  * @post return value - target = min(length, number of elements in all
01765  *    sequences).
01766  *
01767  * @see stable_multiway_merge_sentinels
01768  *
01769  * @param RandomAccessIteratorPairIterator iterator over sequence
01770  *    of pairs of iterators
01771  * @param RandomAccessIteratorOut iterator over target sequence
01772  * @param _DifferenceTp difference type for the sequence
01773  * @param Comparator strict weak ordering type to compare elements
01774  *    in sequences
01775  *
01776  * @param seqs_begin  begin of sequence sequence
01777  * @param seqs_end    end of sequence sequence
01778  * @param target      target sequence to merge to.
01779  * @param comp        strict weak ordering to use for element comparison.
01780  * @param length Maximum length to merge, possibly larger than the
01781  * number of elements available.
01782  *
01783  * @return end iterator of output sequence
01784  */
01785 // public interface
01786 template<
01787     typename RandomAccessIteratorPairIterator
01788   , typename RandomAccessIteratorOut
01789   , typename _DifferenceTp
01790   , typename Comparator>
01791 RandomAccessIteratorOut
01792 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
01793     , RandomAccessIteratorPairIterator seqs_end
01794     , RandomAccessIteratorOut target
01795     , Comparator comp, _DifferenceTp length)
01796 {
01797     typedef _DifferenceTp difference_type;
01798     _GLIBCXX_CALL(seqs_end - seqs_begin)
01799 
01800     // catch special case: no sequences
01801     if (seqs_begin == seqs_end)
01802       return target;
01803 
01804     // Execute merge; maybe parallel, depending on the number of merged
01805     // elements and the number of sequences and global thresholds in
01806     // Settings.
01807     if ((seqs_end - seqs_begin > 1) &&
01808           _GLIBCXX_PARALLEL_CONDITION(
01809           ((seqs_end - seqs_begin) >=
01810             __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01811           && ((sequence_index_t)length >=
01812             __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01813       return parallel_multiway_merge
01814         </* stable = */ false, /* sentinels = */ true>
01815           (seqs_begin, seqs_end, target, comp,
01816           multiway_merge_sampling_splitting
01817             </* stable = */ false,
01818               typename std::iterator_traits<RandomAccessIteratorPairIterator>
01819                 ::value_type*, Comparator, _DifferenceTp>,
01820           static_cast<difference_type>(length));
01821     else
01822       return sequential_multiway_merge
01823         </* stable = */false, /* sentinels = */ true>(
01824           seqs_begin, seqs_end,
01825           target, *(seqs_begin->second), comp, length);
01826 }
01827 
01828 //public interface
01829 template<
01830     typename RandomAccessIteratorPairIterator
01831   , typename RandomAccessIteratorOut
01832   , typename _DifferenceTp
01833   , typename Comparator>
01834 RandomAccessIteratorOut
01835 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
01836     , RandomAccessIteratorPairIterator seqs_end
01837     , RandomAccessIteratorOut target
01838     , Comparator comp, _DifferenceTp length
01839     , __gnu_parallel::sequential_tag)
01840 {
01841     typedef _DifferenceTp difference_type;
01842     _GLIBCXX_CALL(seqs_end - seqs_begin)
01843 
01844     // catch special case: no sequences
01845     if (seqs_begin == seqs_end)
01846       return target;
01847 
01848     // Execute multiway merge *sequentially*.
01849     return sequential_multiway_merge
01850       </* stable = */ false, /* sentinels = */ true>
01851         (seqs_begin, seqs_end, target, *(seqs_begin->second), comp, length);
01852 }
01853 
01854 // public interface
01855 template<
01856     typename RandomAccessIteratorPairIterator
01857   , typename RandomAccessIteratorOut
01858   , typename _DifferenceTp
01859   , typename Comparator>
01860 RandomAccessIteratorOut
01861 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
01862     , RandomAccessIteratorPairIterator seqs_end
01863     , RandomAccessIteratorOut target
01864     , Comparator comp, _DifferenceTp length
01865     , __gnu_parallel::exact_tag)
01866 {
01867     typedef _DifferenceTp difference_type;
01868     _GLIBCXX_CALL(seqs_end - seqs_begin)
01869 
01870     // catch special case: no sequences
01871     if (seqs_begin == seqs_end)
01872       return target;
01873 
01874     // Execute merge; maybe parallel, depending on the number of merged
01875     // elements and the number of sequences and global thresholds in
01876     // Settings.
01877     if ((seqs_end - seqs_begin > 1) &&
01878           _GLIBCXX_PARALLEL_CONDITION(
01879           ((seqs_end - seqs_begin) >=
01880             __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01881           && ((sequence_index_t)length >=
01882             __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01883       return parallel_multiway_merge
01884         </* stable = */ false, /* sentinels = */ true>(
01885           seqs_begin, seqs_end,
01886           target, comp,
01887           multiway_merge_exact_splitting
01888             </* stable = */ false,
01889               typename std::iterator_traits<RandomAccessIteratorPairIterator>
01890                 ::value_type*, Comparator, _DifferenceTp>,
01891           static_cast<difference_type>(length));
01892     else
01893       return sequential_multiway_merge
01894         </* stable = */ false, /* sentinels = */ true>(
01895           seqs_begin, seqs_end,
01896           target, *(seqs_begin->second), comp, length);
01897 }
01898 
01899 // public interface
01900 template<
01901     typename RandomAccessIteratorPairIterator
01902   , typename RandomAccessIteratorOut
01903   , typename _DifferenceTp
01904   , typename Comparator>
01905 RandomAccessIteratorOut
01906 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
01907     , RandomAccessIteratorPairIterator seqs_end
01908     , RandomAccessIteratorOut target
01909     , Comparator comp, _DifferenceTp length)
01910 {
01911     typedef _DifferenceTp difference_type;
01912     _GLIBCXX_CALL(seqs_end - seqs_begin)
01913 
01914     // catch special case: no sequences
01915     if (seqs_begin == seqs_end)
01916       return target;
01917 
01918     // Execute merge; maybe parallel, depending on the number of merged
01919     // elements and the number of sequences and global thresholds in
01920     // Settings.
01921     if ((seqs_end - seqs_begin > 1) &&
01922           _GLIBCXX_PARALLEL_CONDITION(
01923           ((seqs_end - seqs_begin) >=
01924             __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01925           && ((sequence_index_t)length >=
01926             __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01927       return parallel_multiway_merge
01928         </* stable = */ true, /* sentinels = */ true>(
01929           seqs_begin, seqs_end,
01930           target, comp,
01931           multiway_merge_sampling_splitting
01932             </* stable = */ true,
01933               typename std::iterator_traits<RandomAccessIteratorPairIterator>
01934                 ::value_type*, Comparator, _DifferenceTp>,
01935           static_cast<difference_type>(length));
01936     else
01937       return sequential_multiway_merge
01938         </* stable = */ true, /* sentinels = */ true>(
01939           seqs_begin, seqs_end,
01940           target, *(seqs_begin->second), comp, length);
01941 }
01942 
01943 // public interface
01944 template<
01945     typename RandomAccessIteratorPairIterator
01946   , typename RandomAccessIteratorOut
01947   , typename _DifferenceTp
01948   , typename Comparator>
01949 RandomAccessIteratorOut
01950 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
01951     , RandomAccessIteratorPairIterator seqs_end
01952     , RandomAccessIteratorOut target
01953     , Comparator comp, _DifferenceTp length
01954     , __gnu_parallel::sequential_tag)
01955 {
01956     typedef _DifferenceTp difference_type;
01957     _GLIBCXX_CALL(seqs_end - seqs_begin)
01958 
01959     // catch special case: no sequences
01960     if (seqs_begin == seqs_end)
01961       return target;
01962 
01963     // Execute multiway merge *sequentially*.
01964     return sequential_multiway_merge
01965       </* stable = */ true, /* sentinels = */ true>
01966         (seqs_begin, seqs_end, target, *(seqs_begin->second), comp, length);
01967 }
01968 
01969 // public interface
01970 template<
01971     typename RandomAccessIteratorPairIterator
01972   , typename RandomAccessIteratorOut
01973   , typename _DifferenceTp
01974   , typename Comparator>
01975 RandomAccessIteratorOut
01976 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
01977     , RandomAccessIteratorPairIterator seqs_end
01978     , RandomAccessIteratorOut target
01979     , Comparator comp, _DifferenceTp length
01980     , __gnu_parallel::exact_tag)
01981 {
01982     typedef _DifferenceTp difference_type;
01983     _GLIBCXX_CALL(seqs_end - seqs_begin)
01984 
01985     // catch special case: no sequences
01986     if (seqs_begin == seqs_end)
01987       return target;
01988 
01989     // Execute merge; maybe parallel, depending on the number of merged
01990     // elements and the number of sequences and global thresholds in
01991     // Settings.
01992     if ((seqs_end - seqs_begin > 1) &&
01993           _GLIBCXX_PARALLEL_CONDITION(
01994           ((seqs_end - seqs_begin) >=
01995           __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01996           && ((sequence_index_t)length >=
01997           __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01998       return parallel_multiway_merge
01999         </* stable = */ true, /* sentinels = */ true>(
02000           seqs_begin, seqs_end,
02001           target, comp, 
02002           multiway_merge_exact_splitting
02003             </* stable = */ true,
02004               typename std::iterator_traits<RandomAccessIteratorPairIterator>
02005                 ::value_type*, Comparator, _DifferenceTp>,
02006           static_cast<difference_type>(length));
02007     else
02008       return sequential_multiway_merge
02009         </* stable = */ true, /* sentinels = */ true>(
02010           seqs_begin, seqs_end,
02011           target, *(seqs_begin->second), comp, length);
02012 }
02013 
02014 }; // namespace __gnu_parallel
02015 
02016 #endif

Generated on Sat Oct 25 05:09:05 2008 for libstdc++ by  doxygen 1.5.6