diff options
Diffstat (limited to 'libstdc++-v3/include/parallel/multiway_merge.h')
| -rw-r--r-- | libstdc++-v3/include/parallel/multiway_merge.h | 2069 |
1 files changed, 2069 insertions, 0 deletions
diff --git a/libstdc++-v3/include/parallel/multiway_merge.h b/libstdc++-v3/include/parallel/multiway_merge.h new file mode 100644 index 000000000..00df31c13 --- /dev/null +++ b/libstdc++-v3/include/parallel/multiway_merge.h @@ -0,0 +1,2069 @@ +// -*- C++ -*- + +// Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License as published by the Free Software +// Foundation; either version 3, or (at your option) any later +// version. + +// This library is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +/** @file parallel/multiway_merge.h +* @brief Implementation of sequential and parallel multiway merge. +* +* Explanations on the high-speed merging routines in the appendix of +* +* P. Sanders. +* Fast priority queues for cached memory. +* ACM Journal of Experimental Algorithmics, 5, 2000. +* +* This file is a GNU parallel extension to the Standard C++ Library. +*/ + +// Written by Johannes Singler and Manuel Holtgrewe. + +#ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H +#define _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H + +#include <vector> + +#include <bits/stl_algo.h> +#include <parallel/features.h> +#include <parallel/parallel.h> +#include <parallel/losertree.h> +#if _GLIBCXX_ASSERTIONS +#include <parallel/checkers.h> +#endif + +/** @brief Length of a sequence described by a pair of iterators. */ +#define _GLIBCXX_PARALLEL_LENGTH(__s) ((__s).second - (__s).first) + +namespace __gnu_parallel +{ + /** @brief _Iterator wrapper supporting an implicit supremum at the end + * of the sequence, dominating all comparisons. + * + * The implicit supremum comes with a performance cost. + * + * Deriving from _RAIter is not possible since + * _RAIter need not be a class. + */ + template<typename _RAIter, typename _Compare> + class _GuardedIterator + { + private: + /** @brief Current iterator __position. */ + _RAIter _M_current; + + /** @brief End iterator of the sequence. */ + _RAIter _M_end; + + /** @brief _Compare. */ + _Compare& __comp; + + public: + /** @brief Constructor. Sets iterator to beginning of sequence. + * @param __begin Begin iterator of sequence. + * @param __end End iterator of sequence. + * @param __comp Comparator provided for associated overloaded + * compare operators. */ + _GuardedIterator(_RAIter __begin, _RAIter __end, _Compare& __comp) + : _M_current(__begin), _M_end(__end), __comp(__comp) + { } + + /** @brief Pre-increment operator. + * @return This. */ + _GuardedIterator<_RAIter, _Compare>& + operator++() + { + ++_M_current; + return *this; + } + + /** @brief Dereference operator. + * @return Referenced element. */ + typename std::iterator_traits<_RAIter>::value_type& + operator*() + { return *_M_current; } + + /** @brief Convert to wrapped iterator. + * @return Wrapped iterator. */ + operator _RAIter() + { return _M_current; } + + /** @brief Compare two elements referenced by guarded iterators. + * @param __bi1 First iterator. + * @param __bi2 Second iterator. + * @return @c true if less. */ + friend bool + operator<(_GuardedIterator<_RAIter, _Compare>& __bi1, + _GuardedIterator<_RAIter, _Compare>& __bi2) + { + if (__bi1._M_current == __bi1._M_end) // __bi1 is sup + return __bi2._M_current == __bi2._M_end; // __bi2 is not sup + if (__bi2._M_current == __bi2._M_end) // __bi2 is sup + return true; + return (__bi1.__comp)(*__bi1, *__bi2); // normal compare + } + + /** @brief Compare two elements referenced by guarded iterators. + * @param __bi1 First iterator. + * @param __bi2 Second iterator. + * @return @c True if less equal. */ + friend bool + operator<=(_GuardedIterator<_RAIter, _Compare>& __bi1, + _GuardedIterator<_RAIter, _Compare>& __bi2) + { + if (__bi2._M_current == __bi2._M_end) // __bi1 is sup + return __bi1._M_current != __bi1._M_end; // __bi2 is not sup + if (__bi1._M_current == __bi1._M_end) // __bi2 is sup + return false; + return !(__bi1.__comp)(*__bi2, *__bi1); // normal compare + } + }; + + template<typename _RAIter, typename _Compare> + class _UnguardedIterator + { + private: + /** @brief Current iterator __position. */ + _RAIter _M_current; + /** @brief _Compare. */ + _Compare& __comp; + + public: + /** @brief Constructor. Sets iterator to beginning of sequence. + * @param __begin Begin iterator of sequence. + * @param __end Unused, only for compatibility. + * @param __comp Unused, only for compatibility. */ + _UnguardedIterator(_RAIter __begin, + _RAIter /* __end */, _Compare& __comp) + : _M_current(__begin), __comp(__comp) + { } + + /** @brief Pre-increment operator. + * @return This. */ + _UnguardedIterator<_RAIter, _Compare>& + operator++() + { + ++_M_current; + return *this; + } + + /** @brief Dereference operator. + * @return Referenced element. */ + typename std::iterator_traits<_RAIter>::value_type& + operator*() + { return *_M_current; } + + /** @brief Convert to wrapped iterator. + * @return Wrapped iterator. */ + operator _RAIter() + { return _M_current; } + + /** @brief Compare two elements referenced by unguarded iterators. + * @param __bi1 First iterator. + * @param __bi2 Second iterator. + * @return @c true if less. */ + friend bool + operator<(_UnguardedIterator<_RAIter, _Compare>& __bi1, + _UnguardedIterator<_RAIter, _Compare>& __bi2) + { + // Normal compare. + return (__bi1.__comp)(*__bi1, *__bi2); + } + + /** @brief Compare two elements referenced by unguarded iterators. + * @param __bi1 First iterator. + * @param __bi2 Second iterator. + * @return @c True if less equal. */ + friend bool + operator<=(_UnguardedIterator<_RAIter, _Compare>& __bi1, + _UnguardedIterator<_RAIter, _Compare>& __bi2) + { + // Normal compare. + return !(__bi1.__comp)(*__bi2, *__bi1); + } + }; + + /** @brief Highly efficient 3-way merging procedure. + * + * Merging is done with the algorithm implementation described by Peter + * Sanders. Basically, the idea is to minimize the number of necessary + * comparison after merging an element. The implementation trick + * that makes this fast is that the order of the sequences is stored + * in the instruction pointer (translated into labels in C++). + * + * This works well for merging up to 4 sequences. + * + * Note that making the merging stable does @a not come at a + * performance hit. + * + * Whether the merging is done guarded or unguarded is selected by the + * used iterator class. + * + * @param __seqs_begin Begin iterator of iterator pair input sequence. + * @param __seqs_end End iterator of iterator pair input sequence. + * @param __target Begin iterator of output sequence. + * @param __comp Comparator. + * @param __length Maximum length to merge, less equal than the + * total number of elements available. + * + * @return End iterator of output sequence. + */ + template<template<typename RAI, typename C> class iterator, + typename _RAIterIterator, + typename _RAIter3, + typename _DifferenceTp, + typename _Compare> + _RAIter3 + multiway_merge_3_variant(_RAIterIterator __seqs_begin, + _RAIterIterator __seqs_end, + _RAIter3 __target, + _DifferenceTp __length, _Compare __comp) + { + _GLIBCXX_CALL(__length); + + typedef _DifferenceTp _DifferenceType; + + typedef typename std::iterator_traits<_RAIterIterator> + ::value_type::first_type + _RAIter1; + typedef typename std::iterator_traits<_RAIter1>::value_type + _ValueType; + + if (__length == 0) + return __target; + +#if _GLIBCXX_ASSERTIONS + _DifferenceTp __orig_length = __length; +#endif + + iterator<_RAIter1, _Compare> + __seq0(__seqs_begin[0].first, __seqs_begin[0].second, __comp), + __seq1(__seqs_begin[1].first, __seqs_begin[1].second, __comp), + __seq2(__seqs_begin[2].first, __seqs_begin[2].second, __comp); + + if (__seq0 <= __seq1) + { + if (__seq1 <= __seq2) + goto __s012; + else + if (__seq2 < __seq0) + goto __s201; + else + goto __s021; + } + else + { + if (__seq1 <= __seq2) + { + if (__seq0 <= __seq2) + goto __s102; + else + goto __s120; + } + else + goto __s210; + } +#define _GLIBCXX_PARALLEL_MERGE_3_CASE(__a, __b, __c, __c0, __c1) \ + __s ## __a ## __b ## __c : \ + *__target = *__seq ## __a; \ + ++__target; \ + --__length; \ + ++__seq ## __a; \ + if (__length == 0) goto __finish; \ + if (__seq ## __a __c0 __seq ## __b) goto __s ## __a ## __b ## __c; \ + if (__seq ## __a __c1 __seq ## __c) goto __s ## __b ## __a ## __c; \ + goto __s ## __b ## __c ## __a; + + _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 1, 2, <=, <=); + _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 2, 0, <=, < ); + _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 0, 1, < , < ); + _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 0, 2, < , <=); + _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 2, 1, <=, <=); + _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 1, 0, < , < ); + +#undef _GLIBCXX_PARALLEL_MERGE_3_CASE + + __finish: + ; + +#if _GLIBCXX_ASSERTIONS + _GLIBCXX_PARALLEL_ASSERT( + ((_RAIter1)__seq0 - __seqs_begin[0].first) + + ((_RAIter1)__seq1 - __seqs_begin[1].first) + + ((_RAIter1)__seq2 - __seqs_begin[2].first) + == __orig_length); +#endif + + __seqs_begin[0].first = __seq0; + __seqs_begin[1].first = __seq1; + __seqs_begin[2].first = __seq2; + + return __target; + } + + /** + * @brief Highly efficient 4-way merging procedure. + * + * Merging is done with the algorithm implementation described by Peter + * Sanders. Basically, the idea is to minimize the number of necessary + * comparison after merging an element. The implementation trick + * that makes this fast is that the order of the sequences is stored + * in the instruction pointer (translated into goto labels in C++). + * + * This works well for merging up to 4 sequences. + * + * Note that making the merging stable does @a not come at a + * performance hit. + * + * Whether the merging is done guarded or unguarded is selected by the + * used iterator class. + * + * @param __seqs_begin Begin iterator of iterator pair input sequence. + * @param __seqs_end End iterator of iterator pair input sequence. + * @param __target Begin iterator of output sequence. + * @param __comp Comparator. + * @param __length Maximum length to merge, less equal than the + * total number of elements available. + * + * @return End iterator of output sequence. + */ + template<template<typename RAI, typename C> class iterator, + typename _RAIterIterator, + typename _RAIter3, + typename _DifferenceTp, + typename _Compare> + _RAIter3 + multiway_merge_4_variant(_RAIterIterator __seqs_begin, + _RAIterIterator __seqs_end, + _RAIter3 __target, + _DifferenceTp __length, _Compare __comp) + { + _GLIBCXX_CALL(__length); + typedef _DifferenceTp _DifferenceType; + + typedef typename std::iterator_traits<_RAIterIterator> + ::value_type::first_type + _RAIter1; + typedef typename std::iterator_traits<_RAIter1>::value_type + _ValueType; + + iterator<_RAIter1, _Compare> + __seq0(__seqs_begin[0].first, __seqs_begin[0].second, __comp), + __seq1(__seqs_begin[1].first, __seqs_begin[1].second, __comp), + __seq2(__seqs_begin[2].first, __seqs_begin[2].second, __comp), + __seq3(__seqs_begin[3].first, __seqs_begin[3].second, __comp); + +#define _GLIBCXX_PARALLEL_DECISION(__a, __b, __c, __d) { \ + if (__seq ## __d < __seq ## __a) \ + goto __s ## __d ## __a ## __b ## __c; \ + if (__seq ## __d < __seq ## __b) \ + goto __s ## __a ## __d ## __b ## __c; \ + if (__seq ## __d < __seq ## __c) \ + goto __s ## __a ## __b ## __d ## __c; \ + goto __s ## __a ## __b ## __c ## __d; } + + if (__seq0 <= __seq1) + { + if (__seq1 <= __seq2) + _GLIBCXX_PARALLEL_DECISION(0,1,2,3) + else + if (__seq2 < __seq0) + _GLIBCXX_PARALLEL_DECISION(2,0,1,3) + else + _GLIBCXX_PARALLEL_DECISION(0,2,1,3) + } + else + { + if (__seq1 <= __seq2) + { + if (__seq0 <= __seq2) + _GLIBCXX_PARALLEL_DECISION(1,0,2,3) + else + _GLIBCXX_PARALLEL_DECISION(1,2,0,3) + } + else + _GLIBCXX_PARALLEL_DECISION(2,1,0,3) + } + +#define _GLIBCXX_PARALLEL_MERGE_4_CASE(__a, __b, __c, __d, \ + __c0, __c1, __c2) \ + __s ## __a ## __b ## __c ## __d: \ + if (__length == 0) goto __finish; \ + *__target = *__seq ## __a; \ + ++__target; \ + --__length; \ + ++__seq ## __a; \ + if (__seq ## __a __c0 __seq ## __b) \ + goto __s ## __a ## __b ## __c ## __d; \ + if (__seq ## __a __c1 __seq ## __c) \ + goto __s ## __b ## __a ## __c ## __d; \ + if (__seq ## __a __c2 __seq ## __d) \ + goto __s ## __b ## __c ## __a ## __d; \ + goto __s ## __b ## __c ## __d ## __a; + + _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 2, 3, <=, <=, <=); + _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 3, 2, <=, <=, <=); + _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 1, 3, <=, <=, <=); + _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 3, 1, <=, <=, <=); + _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 1, 2, <=, <=, <=); + _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 2, 1, <=, <=, <=); + _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 2, 3, < , <=, <=); + _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 3, 2, < , <=, <=); + _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 0, 3, <=, < , <=); + _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 3, 0, <=, <=, < ); + _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 0, 2, <=, < , <=); + _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 2, 0, <=, <=, < ); + _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 1, 3, < , < , <=); + _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 3, 1, < , <=, < ); + _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 0, 3, < , < , <=); + _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 3, 0, < , <=, < ); + _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 0, 1, <=, < , < ); + _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 1, 0, <=, < , < ); + _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 1, 2, < , < , < ); + _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 2, 1, < , < , < ); + _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 0, 2, < , < , < ); + _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 2, 0, < , < , < ); + _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 0, 1, < , < , < ); + _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 1, 0, < , < , < ); + +#undef _GLIBCXX_PARALLEL_MERGE_4_CASE +#undef _GLIBCXX_PARALLEL_DECISION + + __finish: + ; + + __seqs_begin[0].first = __seq0; + __seqs_begin[1].first = __seq1; + __seqs_begin[2].first = __seq2; + __seqs_begin[3].first = __seq3; + + return __target; + } + + /** @brief Multi-way merging procedure for a high branching factor, + * guarded case. + * + * This merging variant uses a LoserTree class as selected by <tt>_LT</tt>. + * + * Stability is selected through the used LoserTree class <tt>_LT</tt>. + * + * At least one non-empty sequence is required. + * + * @param __seqs_begin Begin iterator of iterator pair input sequence. + * @param __seqs_end End iterator of iterator pair input sequence. + * @param __target Begin iterator of output sequence. + * @param __comp Comparator. + * @param __length Maximum length to merge, less equal than the + * total number of elements available. + * + * @return End iterator of output sequence. + */ + template<typename _LT, + typename _RAIterIterator, + typename _RAIter3, + typename _DifferenceTp, + typename _Compare> + _RAIter3 + multiway_merge_loser_tree(_RAIterIterator __seqs_begin, + _RAIterIterator __seqs_end, + _RAIter3 __target, + _DifferenceTp __length, _Compare __comp) + { + _GLIBCXX_CALL(__length) + + typedef _DifferenceTp _DifferenceType; + typedef typename std::iterator_traits<_RAIterIterator> + ::difference_type _SeqNumber; + typedef typename std::iterator_traits<_RAIterIterator> + ::value_type::first_type + _RAIter1; + typedef typename std::iterator_traits<_RAIter1>::value_type + _ValueType; + + _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin); + + _LT __lt(__k, __comp); + + // Default value for potentially non-default-constructible types. + _ValueType* __arbitrary_element = 0; + + for (_SeqNumber __t = 0; __t < __k; ++__t) + { + if(!__arbitrary_element + && _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__t]) > 0) + __arbitrary_element = &(*__seqs_begin[__t].first); + } + + for (_SeqNumber __t = 0; __t < __k; ++__t) + { + if (__seqs_begin[__t].first == __seqs_begin[__t].second) + __lt.__insert_start(*__arbitrary_element, __t, true); + else + __lt.__insert_start(*__seqs_begin[__t].first, __t, false); + } + + __lt.__init(); + + _SeqNumber __source; + + for (_DifferenceType __i = 0; __i < __length; ++__i) + { + //take out + __source = __lt.__get_min_source(); + + *(__target++) = *(__seqs_begin[__source].first++); + + // Feed. + if (__seqs_begin[__source].first == __seqs_begin[__source].second) + __lt.__delete_min_insert(*__arbitrary_element, true); + else + // Replace from same __source. + __lt.__delete_min_insert(*__seqs_begin[__source].first, false); + } + + return __target; + } + + /** @brief Multi-way merging procedure for a high branching factor, + * unguarded case. + * + * Merging is done using the LoserTree class <tt>_LT</tt>. + * + * Stability is selected by the used LoserTrees. + * + * @pre No input will run out of elements during the merge. + * + * @param __seqs_begin Begin iterator of iterator pair input sequence. + * @param __seqs_end End iterator of iterator pair input sequence. + * @param __target Begin iterator of output sequence. + * @param __comp Comparator. + * @param __length Maximum length to merge, less equal than the + * total number of elements available. + * + * @return End iterator of output sequence. + */ + template<typename _LT, + typename _RAIterIterator, + typename _RAIter3, + typename _DifferenceTp, typename _Compare> + _RAIter3 + multiway_merge_loser_tree_unguarded(_RAIterIterator __seqs_begin, + _RAIterIterator __seqs_end, + _RAIter3 __target, + const typename std::iterator_traits<typename std::iterator_traits< + _RAIterIterator>::value_type::first_type>::value_type& + __sentinel, + _DifferenceTp __length, + _Compare __comp) + { + _GLIBCXX_CALL(__length) + typedef _DifferenceTp _DifferenceType; + + typedef typename std::iterator_traits<_RAIterIterator> + ::difference_type _SeqNumber; + typedef typename std::iterator_traits<_RAIterIterator> + ::value_type::first_type + _RAIter1; + typedef typename std::iterator_traits<_RAIter1>::value_type + _ValueType; + + _SeqNumber __k = __seqs_end - __seqs_begin; + + _LT __lt(__k, __sentinel, __comp); + + for (_SeqNumber __t = 0; __t < __k; ++__t) + { +#if _GLIBCXX_ASSERTIONS + _GLIBCXX_PARALLEL_ASSERT(__seqs_begin[__t].first + != __seqs_begin[__t].second); +#endif + __lt.__insert_start(*__seqs_begin[__t].first, __t, false); + } + + __lt.__init(); + + _SeqNumber __source; + +#if _GLIBCXX_ASSERTIONS + _DifferenceType __i = 0; +#endif + + _RAIter3 __target_end = __target + __length; + while (__target < __target_end) + { + // Take out. + __source = __lt.__get_min_source(); + +#if _GLIBCXX_ASSERTIONS + _GLIBCXX_PARALLEL_ASSERT(0 <= __source && __source < __k); + _GLIBCXX_PARALLEL_ASSERT(__i == 0 + || !__comp(*(__seqs_begin[__source].first), *(__target - 1))); +#endif + + // Feed. + *(__target++) = *(__seqs_begin[__source].first++); + +#if _GLIBCXX_ASSERTIONS + ++__i; +#endif + // Replace from same __source. + __lt.__delete_min_insert(*__seqs_begin[__source].first, false); + } + + return __target; + } + + + /** @brief Multi-way merging procedure for a high branching factor, + * requiring sentinels to exist. + * + * @param __stable The value must the same as for the used LoserTrees. + * @param UnguardedLoserTree _Loser Tree variant to use for the unguarded + * merging. + * @param GuardedLoserTree _Loser Tree variant to use for the guarded + * merging. + * + * @param __seqs_begin Begin iterator of iterator pair input sequence. + * @param __seqs_end End iterator of iterator pair input sequence. + * @param __target Begin iterator of output sequence. + * @param __comp Comparator. + * @param __length Maximum length to merge, less equal than the + * total number of elements available. + * + * @return End iterator of output sequence. + */ + template<typename UnguardedLoserTree, + typename _RAIterIterator, + typename _RAIter3, + typename _DifferenceTp, + typename _Compare> + _RAIter3 + multiway_merge_loser_tree_sentinel(_RAIterIterator __seqs_begin, + _RAIterIterator __seqs_end, + _RAIter3 __target, + const typename std::iterator_traits<typename std::iterator_traits< + _RAIterIterator>::value_type::first_type>::value_type& + __sentinel, + _DifferenceTp __length, + _Compare __comp) + { + _GLIBCXX_CALL(__length) + + typedef _DifferenceTp _DifferenceType; + typedef std::iterator_traits<_RAIterIterator> _TraitsType; + typedef typename std::iterator_traits<_RAIterIterator> + ::value_type::first_type + _RAIter1; + typedef typename std::iterator_traits<_RAIter1>::value_type + _ValueType; + + _RAIter3 __target_end; + + for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s) + // Move the sequence ends to the sentinel. This has the + // effect that the sentinel appears to be within the sequence. Then, + // we can use the unguarded variant if we merge out as many + // non-sentinel elements as we have. + ++((*__s).second); + + __target_end = multiway_merge_loser_tree_unguarded<UnguardedLoserTree> + (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp); + +#if _GLIBCXX_ASSERTIONS + _GLIBCXX_PARALLEL_ASSERT(__target_end == __target + __length); + _GLIBCXX_PARALLEL_ASSERT(__is_sorted(__target, __target_end, __comp)); +#endif + + // Restore the sequence ends so the sentinels are not contained in the + // sequence any more (see comment in loop above). + for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s) + --((*__s).second); + + return __target_end; + } + + /** + * @brief Traits for determining whether the loser tree should + * use pointers or copies. + * + * The field "_M_use_pointer" is used to determine whether to use pointers + * in he loser trees or whether to copy the values into the loser tree. + * + * The default behavior is to use pointers if the data type is 4 times as + * big as the pointer to it. + * + * Specialize for your data type to customize the behavior. + * + * Example: + * + * template<> + * struct _LoserTreeTraits<int> + * { static const bool _M_use_pointer = false; }; + * + * template<> + * struct _LoserTreeTraits<heavyweight_type> + * { static const bool _M_use_pointer = true; }; + * + * @param _Tp type to give the loser tree traits for. + */ + template <typename _Tp> + struct _LoserTreeTraits + { + /** + * @brief True iff to use pointers instead of values in loser trees. + * + * The default behavior is to use pointers if the data type is four + * times as big as the pointer to it. + */ + static const bool _M_use_pointer = (sizeof(_Tp) > 4 * sizeof(_Tp*)); + }; + + /** + * @brief Switch for 3-way merging with __sentinels turned off. + * + * Note that 3-way merging is always stable! + */ + template<bool __sentinels /*default == false*/, + typename _RAIterIterator, + typename _RAIter3, + typename _DifferenceTp, + typename _Compare> + struct __multiway_merge_3_variant_sentinel_switch + { + _RAIter3 + operator()(_RAIterIterator __seqs_begin, + _RAIterIterator __seqs_end, + _RAIter3 __target, + _DifferenceTp __length, _Compare __comp) + { return multiway_merge_3_variant<_GuardedIterator> + (__seqs_begin, __seqs_end, __target, __length, __comp); } + }; + + /** + * @brief Switch for 3-way merging with __sentinels turned on. + * + * Note that 3-way merging is always stable! + */ + template<typename _RAIterIterator, + typename _RAIter3, + typename _DifferenceTp, + typename _Compare> + struct __multiway_merge_3_variant_sentinel_switch<true, _RAIterIterator, + _RAIter3, _DifferenceTp, + _Compare> + { + _RAIter3 + operator()(_RAIterIterator __seqs_begin, + _RAIterIterator __seqs_end, + _RAIter3 __target, + _DifferenceTp __length, _Compare __comp) + { return multiway_merge_3_variant<_UnguardedIterator> + (__seqs_begin, __seqs_end, __target, __length, __comp); } + }; + + /** + * @brief Switch for 4-way merging with __sentinels turned off. + * + * Note that 4-way merging is always stable! + */ + template<bool __sentinels /*default == false*/, + typename _RAIterIterator, + typename _RAIter3, + typename _DifferenceTp, + typename _Compare> + struct __multiway_merge_4_variant_sentinel_switch + { + _RAIter3 + operator()(_RAIterIterator __seqs_begin, + _RAIterIterator __seqs_end, + _RAIter3 __target, + _DifferenceTp __length, _Compare __comp) + { return multiway_merge_4_variant<_GuardedIterator> + (__seqs_begin, __seqs_end, __target, __length, __comp); } + }; + + /** + * @brief Switch for 4-way merging with __sentinels turned on. + * + * Note that 4-way merging is always stable! + */ + template<typename _RAIterIterator, + typename _RAIter3, + typename _DifferenceTp, + typename _Compare> + struct __multiway_merge_4_variant_sentinel_switch<true, _RAIterIterator, + _RAIter3, _DifferenceTp, + _Compare> + { + _RAIter3 + operator()(_RAIterIterator __seqs_begin, + _RAIterIterator __seqs_end, + _RAIter3 __target, + _DifferenceTp __length, _Compare __comp) + { return multiway_merge_4_variant<_UnguardedIterator> + (__seqs_begin, __seqs_end, __target, __length, __comp); } + }; + + /** + * @brief Switch for k-way merging with __sentinels turned on. + */ + template<bool __sentinels, + bool __stable, + typename _RAIterIterator, + typename _RAIter3, + typename _DifferenceTp, + typename _Compare> + struct __multiway_merge_k_variant_sentinel_switch + { + _RAIter3 + operator()(_RAIterIterator __seqs_begin, + _RAIterIterator __seqs_end, + _RAIter3 __target, + const typename std::iterator_traits<typename std::iterator_traits< + _RAIterIterator>::value_type::first_type>::value_type& + __sentinel, + _DifferenceTp __length, _Compare __comp) + { + typedef typename std::iterator_traits<_RAIterIterator> + ::value_type::first_type + _RAIter1; + typedef typename std::iterator_traits<_RAIter1>::value_type + _ValueType; + + return multiway_merge_loser_tree_sentinel< + typename __gnu_cxx::__conditional_type< + _LoserTreeTraits<_ValueType>::_M_use_pointer, + _LoserTreePointerUnguarded<__stable, _ValueType, _Compare>, + _LoserTreeUnguarded<__stable, _ValueType, _Compare> + >::__type> + (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp); + } + }; + + /** + * @brief Switch for k-way merging with __sentinels turned off. + */ + template<bool __stable, + typename _RAIterIterator, + typename _RAIter3, + typename _DifferenceTp, + typename _Compare> + struct __multiway_merge_k_variant_sentinel_switch<false, __stable, + _RAIterIterator, + _RAIter3, _DifferenceTp, + _Compare> + { + _RAIter3 + operator()(_RAIterIterator __seqs_begin, + _RAIterIterator __seqs_end, + _RAIter3 __target, + const typename std::iterator_traits<typename std::iterator_traits< + _RAIterIterator>::value_type::first_type>::value_type& + __sentinel, + _DifferenceTp __length, _Compare __comp) + { + typedef typename std::iterator_traits<_RAIterIterator> + ::value_type::first_type + _RAIter1; + typedef typename std::iterator_traits<_RAIter1>::value_type + _ValueType; + + return multiway_merge_loser_tree< + typename __gnu_cxx::__conditional_type< + _LoserTreeTraits<_ValueType>::_M_use_pointer, + _LoserTreePointer<__stable, _ValueType, _Compare>, + _LoserTree<__stable, _ValueType, _Compare> + >::__type >(__seqs_begin, __seqs_end, __target, __length, __comp); + } + }; + + /** @brief Sequential multi-way merging switch. + * + * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and + * runtime settings. + * @param __seqs_begin Begin iterator of iterator pair input sequence. + * @param __seqs_end End iterator of iterator pair input sequence. + * @param __target Begin iterator of output sequence. + * @param __comp Comparator. + * @param __length Maximum length to merge, possibly larger than the + * number of elements available. + * @param __stable Stable merging incurs a performance penalty. + * @param __sentinel The sequences have __a __sentinel element. + * @return End iterator of output sequence. */ + template<bool __stable, + bool __sentinels, + typename _RAIterIterator, + typename _RAIter3, + typename _DifferenceTp, + typename _Compare> + _RAIter3 + __sequential_multiway_merge(_RAIterIterator __seqs_begin, + _RAIterIterator __seqs_end, + _RAIter3 __target, + const typename std::iterator_traits<typename std::iterator_traits< + _RAIterIterator>::value_type::first_type>::value_type& + __sentinel, + _DifferenceTp __length, _Compare __comp) + { + _GLIBCXX_CALL(__length) + + typedef _DifferenceTp _DifferenceType; + typedef typename std::iterator_traits<_RAIterIterator> + ::difference_type _SeqNumber; + typedef typename std::iterator_traits<_RAIterIterator> + ::value_type::first_type + _RAIter1; + typedef typename std::iterator_traits<_RAIter1>::value_type + _ValueType; + +#if _GLIBCXX_ASSERTIONS + for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s) + { + _GLIBCXX_PARALLEL_ASSERT(__is_sorted((*__s).first, + (*__s).second, __comp)); + } +#endif + + _DifferenceTp __total_length = 0; + for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s) + __total_length += _GLIBCXX_PARALLEL_LENGTH(*__s); + + __length = std::min<_DifferenceTp>(__length, __total_length); + + if(__length == 0) + return __target; + + _RAIter3 __return_target = __target; + _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin); + + switch (__k) + { + case 0: + break; + case 1: + __return_target = std::copy(__seqs_begin[0].first, + __seqs_begin[0].first + __length, + __target); + __seqs_begin[0].first += __length; + break; + case 2: + __return_target = __merge_advance(__seqs_begin[0].first, + __seqs_begin[0].second, + __seqs_begin[1].first, + __seqs_begin[1].second, + __target, __length, __comp); + break; + case 3: + __return_target = __multiway_merge_3_variant_sentinel_switch + <__sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare>() + (__seqs_begin, __seqs_end, __target, __length, __comp); + break; + case 4: + __return_target = __multiway_merge_4_variant_sentinel_switch + <__sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare>() + (__seqs_begin, __seqs_end, __target, __length, __comp); + break; + default: + __return_target = __multiway_merge_k_variant_sentinel_switch + <__sentinels, __stable, _RAIterIterator, _RAIter3, _DifferenceTp, + _Compare>() + (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp); + break; + } +#if _GLIBCXX_ASSERTIONS + _GLIBCXX_PARALLEL_ASSERT( + __is_sorted(__target, __target + __length, __comp)); +#endif + + return __return_target; + } + + /** + * @brief Stable sorting functor. + * + * Used to reduce code instanciation in multiway_merge_sampling_splitting. + */ + template<bool __stable, class _RAIter, class _StrictWeakOrdering> + struct _SamplingSorter + { + void + operator()(_RAIter __first, _RAIter __last, _StrictWeakOrdering __comp) + { __gnu_sequential::stable_sort(__first, __last, __comp); } + }; + + /** + * @brief Non-__stable sorting functor. + * + * Used to reduce code instantiation in multiway_merge_sampling_splitting. + */ + template<class _RAIter, class _StrictWeakOrdering> + struct _SamplingSorter<false, _RAIter, _StrictWeakOrdering> + { + void + operator()(_RAIter __first, _RAIter __last, _StrictWeakOrdering __comp) + { __gnu_sequential::sort(__first, __last, __comp); } + }; + + /** + * @brief Sampling based splitting for parallel multiway-merge routine. + */ + template<bool __stable, + typename _RAIterIterator, + typename _Compare, + typename _DifferenceType> + void + multiway_merge_sampling_splitting(_RAIterIterator __seqs_begin, + _RAIterIterator __seqs_end, + _DifferenceType __length, + _DifferenceType __total_length, + _Compare __comp, + std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces) + { + typedef typename std::iterator_traits<_RAIterIterator> + ::difference_type _SeqNumber; + typedef typename std::iterator_traits<_RAIterIterator> + ::value_type::first_type + _RAIter1; + typedef typename std::iterator_traits<_RAIter1>::value_type + _ValueType; + + // __k sequences. + const _SeqNumber __k + = static_cast<_SeqNumber>(__seqs_end - __seqs_begin); + + const _ThreadIndex __num_threads = omp_get_num_threads(); + + const _DifferenceType __num_samples = + __gnu_parallel::_Settings::get().merge_oversampling * __num_threads; + + _ValueType* __samples = static_cast<_ValueType*> + (::operator new(sizeof(_ValueType) * __k * __num_samples)); + // Sample. + for (_SeqNumber __s = 0; __s < __k; ++__s) + for (_DifferenceType __i = 0; __i < __num_samples; ++__i) + { + _DifferenceType sample_index = static_cast<_DifferenceType> + (_GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__s]) + * (double(__i + 1) / (__num_samples + 1)) + * (double(__length) / __total_length)); + new(&(__samples[__s * __num_samples + __i])) + _ValueType(__seqs_begin[__s].first[sample_index]); + } + + // Sort stable or non-stable, depending on value of template parameter + // "__stable". + _SamplingSorter<__stable, _ValueType*, _Compare>() + (__samples, __samples + (__num_samples * __k), __comp); + + for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab) + // For each slab / processor. + for (_SeqNumber __seq = 0; __seq < __k; ++__seq) + { + // For each sequence. + if (__slab > 0) + __pieces[__slab][__seq].first = std::upper_bound + (__seqs_begin[__seq].first, __seqs_begin[__seq].second, + __samples[__num_samples * __k * __slab / __num_threads], + __comp) + - __seqs_begin[__seq].first; + else + // Absolute beginning. + __pieces[__slab][__seq].first = 0; + if ((__slab + 1) < __num_threads) + __pieces[__slab][__seq].second = std::upper_bound + (__seqs_begin[__seq].first, __seqs_begin[__seq].second, + __samples[__num_samples * __k * (__slab + 1) / __num_threads], + __comp) + - __seqs_begin[__seq].first; + else + // Absolute end. + __pieces[__slab][__seq].second = + _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]); + } + + for (_SeqNumber __s = 0; __s < __k; ++__s) + for (_DifferenceType __i = 0; __i < __num_samples; ++__i) + __samples[__s * __num_samples + __i].~_ValueType(); + ::operator delete(__samples); + } + + /** + * @brief Exact splitting for parallel multiway-merge routine. + * + * None of the passed sequences may be empty. + */ + template<bool __stable, + typename _RAIterIterator, + typename _Compare, + typename _DifferenceType> + void + multiway_merge_exact_splitting(_RAIterIterator __seqs_begin, + _RAIterIterator __seqs_end, + _DifferenceType __length, + _DifferenceType __total_length, + _Compare __comp, + std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces) + { + typedef typename std::iterator_traits<_RAIterIterator> + ::difference_type _SeqNumber; + typedef typename std::iterator_traits<_RAIterIterator> + ::value_type::first_type + _RAIter1; + + const bool __tight = (__total_length == __length); + + // __k sequences. + const _SeqNumber __k = __seqs_end - __seqs_begin; + + const _ThreadIndex __num_threads = omp_get_num_threads(); + + // (Settings::multiway_merge_splitting + // == __gnu_parallel::_Settings::EXACT). + std::vector<_RAIter1>* __offsets = + new std::vector<_RAIter1>[__num_threads]; + std::vector<std::pair<_RAIter1, _RAIter1> > __se(__k); + + copy(__seqs_begin, __seqs_end, __se.begin()); + + _DifferenceType* __borders = + new _DifferenceType[__num_threads + 1]; + equally_split(__length, __num_threads, __borders); + + for (_ThreadIndex __s = 0; __s < (__num_threads - 1); ++__s) + { + __offsets[__s].resize(__k); + multiseq_partition(__se.begin(), __se.end(), __borders[__s + 1], + __offsets[__s].begin(), __comp); + + // Last one also needed and available. + if (!__tight) + { + __offsets[__num_threads - 1].resize(__k); + multiseq_partition(__se.begin(), __se.end(), + _DifferenceType(__length), + __offsets[__num_threads - 1].begin(), + __comp); + } + } + delete[] __borders; + + for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab) + { + // For each slab / processor. + for (_SeqNumber __seq = 0; __seq < __k; ++__seq) + { + // For each sequence. + if (__slab == 0) + { + // Absolute beginning. + __pieces[__slab][__seq].first = 0; + } + else + __pieces[__slab][__seq].first = + __pieces[__slab - 1][__seq].second; + if (!__tight || __slab < (__num_threads - 1)) + __pieces[__slab][__seq].second = + __offsets[__slab][__seq] - __seqs_begin[__seq].first; + else + { + // __slab == __num_threads - 1 + __pieces[__slab][__seq].second = + _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]); + } + } + } + delete[] __offsets; + } + + /** @brief Parallel multi-way merge routine. + * + * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor + * and runtime settings. + * + * Must not be called if the number of sequences is 1. + * + * @param _Splitter functor to split input (either __exact or sampling based) + * + * @param __seqs_begin Begin iterator of iterator pair input sequence. + * @param __seqs_end End iterator of iterator pair input sequence. + * @param __target Begin iterator of output sequence. + * @param __comp Comparator. + * @param __length Maximum length to merge, possibly larger than the + * number of elements available. + * @param __stable Stable merging incurs a performance penalty. + * @param __sentinel Ignored. + * @return End iterator of output sequence. + */ + template<bool __stable, + bool __sentinels, + typename _RAIterIterator, + typename _RAIter3, + typename _DifferenceTp, + typename _Splitter, + typename _Compare> + _RAIter3 + parallel_multiway_merge(_RAIterIterator __seqs_begin, + _RAIterIterator __seqs_end, + _RAIter3 __target, + _Splitter __splitter, + _DifferenceTp __length, + _Compare __comp, + _ThreadIndex __num_threads) + { +#if _GLIBCXX_ASSERTIONS + _GLIBCXX_PARALLEL_ASSERT(__seqs_end - __seqs_begin > 1); +#endif + + _GLIBCXX_CALL(__length) + + typedef _DifferenceTp _DifferenceType; + typedef typename std::iterator_traits<_RAIterIterator> + ::difference_type _SeqNumber; + typedef typename std::iterator_traits<_RAIterIterator> + ::value_type::first_type + _RAIter1; + typedef typename + std::iterator_traits<_RAIter1>::value_type _ValueType; + + // Leave only non-empty sequences. + typedef std::pair<_RAIter1, _RAIter1> seq_type; + seq_type* __ne_seqs = new seq_type[__seqs_end - __seqs_begin]; + _SeqNumber __k = 0; + _DifferenceType __total_length = 0; + for (_RAIterIterator __raii = __seqs_begin; + __raii != __seqs_end; ++__raii) + { + _DifferenceTp __seq_length = _GLIBCXX_PARALLEL_LENGTH(*__raii); + if(__seq_length > 0) + { + __total_length += __seq_length; + __ne_seqs[__k++] = *__raii; + } + } + + _GLIBCXX_CALL(__total_length) + + __length = std::min<_DifferenceTp>(__length, __total_length); + + if (__total_length == 0 || __k == 0) + { + delete[] __ne_seqs; + return __target; + } + + std::vector<std::pair<_DifferenceType, _DifferenceType> >* __pieces; + + __num_threads = static_cast<_ThreadIndex> + (std::min<_DifferenceType>(__num_threads, __total_length)); + +# pragma omp parallel num_threads (__num_threads) + { +# pragma omp single + { + __num_threads = omp_get_num_threads(); + // Thread __t will have to merge pieces[__iam][0..__k - 1] + __pieces = new std::vector< + std::pair<_DifferenceType, _DifferenceType> >[__num_threads]; + for (_ThreadIndex __s = 0; __s < __num_threads; ++__s) + __pieces[__s].resize(__k); + + _DifferenceType __num_samples = + __gnu_parallel::_Settings::get().merge_oversampling + * __num_threads; + + __splitter(__ne_seqs, __ne_seqs + __k, __length, __total_length, + __comp, __pieces); + } //single + + _ThreadIndex __iam = omp_get_thread_num(); + + _DifferenceType __target_position = 0; + + for (_SeqNumber __c = 0; __c < __k; ++__c) + __target_position += __pieces[__iam][__c].first; + + seq_type* __chunks = new seq_type[__k]; + + for (_SeqNumber __s = 0; __s < __k; ++__s) + __chunks[__s] = std::make_pair(__ne_seqs[__s].first + + __pieces[__iam][__s].first, + __ne_seqs[__s].first + + __pieces[__iam][__s].second); + + if(__length > __target_position) + __sequential_multiway_merge<__stable, __sentinels> + (__chunks, __chunks + __k, __target + __target_position, + *(__seqs_begin->second), __length - __target_position, __comp); + + delete[] __chunks; + } // parallel + +#if _GLIBCXX_ASSERTIONS + _GLIBCXX_PARALLEL_ASSERT( + __is_sorted(__target, __target + __length, __comp)); +#endif + + __k = 0; + // Update ends of sequences. + for (_RAIterIterator __raii = __seqs_begin; + __raii != __seqs_end; ++__raii) + { + _DifferenceTp __length = _GLIBCXX_PARALLEL_LENGTH(*__raii); + if(__length > 0) + (*__raii).first += __pieces[__num_threads - 1][__k++].second; + } + + delete[] __pieces; + delete[] __ne_seqs; + + return __target + __length; + } + + /** + * @brief Multiway Merge Frontend. + * + * Merge the sequences specified by seqs_begin and __seqs_end into + * __target. __seqs_begin and __seqs_end must point to a sequence of + * pairs. These pairs must contain an iterator to the beginning + * of a sequence in their first entry and an iterator the _M_end of + * the same sequence in their second entry. + * + * Ties are broken arbitrarily. See stable_multiway_merge for a variant + * that breaks ties by sequence number but is slower. + * + * The first entries of the pairs (i.e. the begin iterators) will be moved + * forward. + * + * The output sequence has to provide enough space for all elements + * that are written to it. + * + * This function will merge the input sequences: + * + * - not stable + * - parallel, depending on the input size and Settings + * - using sampling for splitting + * - not using sentinels + * + * Example: + * + * <pre> + * int sequences[10][10]; + * for (int __i = 0; __i < 10; ++__i) + * for (int __j = 0; __i < 10; ++__j) + * sequences[__i][__j] = __j; + * + * int __out[33]; + * std::vector<std::pair<int*> > seqs; + * for (int __i = 0; __i < 10; ++__i) + * { seqs.push(std::make_pair<int*>(sequences[__i], + * sequences[__i] + 10)) } + * + * multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33); + * </pre> + * + * @see stable_multiway_merge + * + * @pre All input sequences must be sorted. + * @pre Target must provide enough space to merge out length elements or + * the number of elements in all sequences, whichever is smaller. + * + * @post [__target, return __value) contains merged __elements from the + * input sequences. + * @post return __value - __target = min(__length, number of elements in all + * sequences). + * + * @param _RAIterPairIterator iterator over sequence + * of pairs of iterators + * @param _RAIterOut iterator over target sequence + * @param _DifferenceTp difference type for the sequence + * @param _Compare strict weak ordering type to compare elements + * in sequences + * + * @param __seqs_begin __begin of sequence __sequence + * @param __seqs_end _M_end of sequence __sequence + * @param __target target sequence to merge to. + * @param __comp strict weak ordering to use for element comparison. + * @param __length Maximum length to merge, possibly larger than the + * number of elements available. + * + * @return _M_end iterator of output sequence + */ + // multiway_merge + // public interface + template<typename _RAIterPairIterator, + typename _RAIterOut, + typename _DifferenceTp, + typename _Compare> + _RAIterOut + multiway_merge(_RAIterPairIterator __seqs_begin, + _RAIterPairIterator __seqs_end, + _RAIterOut __target, + _DifferenceTp __length, _Compare __comp, + __gnu_parallel::sequential_tag) + { + typedef _DifferenceTp _DifferenceType; + _GLIBCXX_CALL(__seqs_end - __seqs_begin) + + // catch special case: no sequences + if (__seqs_begin == __seqs_end) + return __target; + + // Execute multiway merge *sequentially*. + return __sequential_multiway_merge + </* __stable = */ false, /* __sentinels = */ false> + (__seqs_begin, __seqs_end, __target, + *(__seqs_begin->second), __length, __comp); + } + + // public interface + template<typename _RAIterPairIterator, + typename _RAIterOut, + typename _DifferenceTp, + typename _Compare> + _RAIterOut + multiway_merge(_RAIterPairIterator __seqs_begin, + _RAIterPairIterator __seqs_end, + _RAIterOut __target, + _DifferenceTp __length, _Compare __comp, + __gnu_parallel::exact_tag __tag) + { + typedef _DifferenceTp _DifferenceType; + _GLIBCXX_CALL(__seqs_end - __seqs_begin) + + // catch special case: no sequences + if (__seqs_begin == __seqs_end) + return __target; + + // Execute merge; maybe parallel, depending on the number of merged + // elements and the number of sequences and global thresholds in + // Settings. + if ((__seqs_end - __seqs_begin > 1) + && _GLIBCXX_PARALLEL_CONDITION( + ((__seqs_end - __seqs_begin) >= + __gnu_parallel::_Settings::get().multiway_merge_minimal_k) + && ((_SequenceIndex)__length >= + __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) + return parallel_multiway_merge + </* __stable = */ false, /* __sentinels = */ false> + (__seqs_begin, __seqs_end, __target, + multiway_merge_exact_splitting</* __stable = */ false, + typename std::iterator_traits<_RAIterPairIterator> + ::value_type*, _Compare, _DifferenceTp>, + static_cast<_DifferenceType>(__length), __comp, + __tag.__get_num_threads()); + else + return __sequential_multiway_merge + </* __stable = */ false, /* __sentinels = */ false> + (__seqs_begin, __seqs_end, __target, + *(__seqs_begin->second), __length, __comp); + } + + // public interface + template<typename _RAIterPairIterator, + typename _RAIterOut, + typename _DifferenceTp, + typename _Compare> + _RAIterOut + multiway_merge(_RAIterPairIterator __seqs_begin, + _RAIterPairIterator __seqs_end, + _RAIterOut __target, + _DifferenceTp __length, _Compare __comp, + __gnu_parallel::sampling_tag __tag) + { + typedef _DifferenceTp _DifferenceType; + _GLIBCXX_CALL(__seqs_end - __seqs_begin) + + // catch special case: no sequences + if (__seqs_begin == __seqs_end) + return __target; + + // Execute merge; maybe parallel, depending on the number of merged + // elements and the number of sequences and global thresholds in + // Settings. + if ((__seqs_end - __seqs_begin > 1) + && _GLIBCXX_PARALLEL_CONDITION( + ((__seqs_end - __seqs_begin) >= + __gnu_parallel::_Settings::get().multiway_merge_minimal_k) + && ((_SequenceIndex)__length >= + __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) + return parallel_multiway_merge + </* __stable = */ false, /* __sentinels = */ false> + (__seqs_begin, __seqs_end, __target, + multiway_merge_exact_splitting</* __stable = */ false, + typename std::iterator_traits<_RAIterPairIterator> + ::value_type*, _Compare, _DifferenceTp>, + static_cast<_DifferenceType>(__length), __comp, + __tag.__get_num_threads()); + else + return __sequential_multiway_merge + </* __stable = */ false, /* __sentinels = */ false> + (__seqs_begin, __seqs_end, __target, + *(__seqs_begin->second), __length, __comp); + } + + // public interface + template<typename _RAIterPairIterator, + typename _RAIterOut, + typename _DifferenceTp, + typename _Compare> + _RAIterOut + multiway_merge(_RAIterPairIterator __seqs_begin, + _RAIterPairIterator __seqs_end, + _RAIterOut __target, + _DifferenceTp __length, _Compare __comp, + parallel_tag __tag = parallel_tag(0)) + { return multiway_merge(__seqs_begin, __seqs_end, __target, __length, + __comp, exact_tag(__tag.__get_num_threads())); } + + // public interface + template<typename _RAIterPairIterator, + typename _RAIterOut, + typename _DifferenceTp, + typename _Compare> + _RAIterOut + multiway_merge(_RAIterPairIterator __seqs_begin, + _RAIterPairIterator __seqs_end, + _RAIterOut __target, + _DifferenceTp __length, _Compare __comp, + default_parallel_tag __tag) + { return multiway_merge(__seqs_begin, __seqs_end, __target, __length, + __comp, exact_tag(__tag.__get_num_threads())); } + + // stable_multiway_merge + // public interface + template<typename _RAIterPairIterator, + typename _RAIterOut, + typename _DifferenceTp, + typename _Compare> + _RAIterOut + stable_multiway_merge(_RAIterPairIterator __seqs_begin, + _RAIterPairIterator __seqs_end, + _RAIterOut __target, + _DifferenceTp __length, _Compare __comp, + __gnu_parallel::sequential_tag) + { + typedef _DifferenceTp _DifferenceType; + _GLIBCXX_CALL(__seqs_end - __seqs_begin) + + // catch special case: no sequences + if (__seqs_begin == __seqs_end) + return __target; + + // Execute multiway merge *sequentially*. + return __sequential_multiway_merge + </* __stable = */ true, /* __sentinels = */ false> + (__seqs_begin, __seqs_end, __target, + *(__seqs_begin->second), __length, __comp); + } + + // public interface + template<typename _RAIterPairIterator, + typename _RAIterOut, + typename _DifferenceTp, + typename _Compare> + _RAIterOut + stable_multiway_merge(_RAIterPairIterator __seqs_begin, + _RAIterPairIterator __seqs_end, + _RAIterOut __target, + _DifferenceTp __length, _Compare __comp, + __gnu_parallel::exact_tag __tag) + { + typedef _DifferenceTp _DifferenceType; + _GLIBCXX_CALL(__seqs_end - __seqs_begin) + + // catch special case: no sequences + if (__seqs_begin == __seqs_end) + return __target; + + // Execute merge; maybe parallel, depending on the number of merged + // elements and the number of sequences and global thresholds in + // Settings. + if ((__seqs_end - __seqs_begin > 1) + && _GLIBCXX_PARALLEL_CONDITION( + ((__seqs_end - __seqs_begin) >= + __gnu_parallel::_Settings::get().multiway_merge_minimal_k) + && ((_SequenceIndex)__length >= + __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) + return parallel_multiway_merge + </* __stable = */ true, /* __sentinels = */ false> + (__seqs_begin, __seqs_end, __target, + multiway_merge_exact_splitting</* __stable = */ true, + typename std::iterator_traits<_RAIterPairIterator> + ::value_type*, _Compare, _DifferenceTp>, + static_cast<_DifferenceType>(__length), __comp, + __tag.__get_num_threads()); + else + return __sequential_multiway_merge + </* __stable = */ true, /* __sentinels = */ false> + (__seqs_begin, __seqs_end, __target, + *(__seqs_begin->second), __length, __comp); + } + + // public interface + template<typename _RAIterPairIterator, + typename _RAIterOut, + typename _DifferenceTp, + typename _Compare> + _RAIterOut + stable_multiway_merge(_RAIterPairIterator __seqs_begin, + _RAIterPairIterator __seqs_end, + _RAIterOut __target, + _DifferenceTp __length, _Compare __comp, + sampling_tag __tag) + { + typedef _DifferenceTp _DifferenceType; + _GLIBCXX_CALL(__seqs_end - __seqs_begin) + + // catch special case: no sequences + if (__seqs_begin == __seqs_end) + return __target; + + // Execute merge; maybe parallel, depending on the number of merged + // elements and the number of sequences and global thresholds in + // Settings. + if ((__seqs_end - __seqs_begin > 1) + && _GLIBCXX_PARALLEL_CONDITION( + ((__seqs_end - __seqs_begin) >= + __gnu_parallel::_Settings::get().multiway_merge_minimal_k) + && ((_SequenceIndex)__length >= + __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) + return parallel_multiway_merge + </* __stable = */ true, /* __sentinels = */ false> + (__seqs_begin, __seqs_end, __target, + multiway_merge_sampling_splitting</* __stable = */ true, + typename std::iterator_traits<_RAIterPairIterator> + ::value_type*, _Compare, _DifferenceTp>, + static_cast<_DifferenceType>(__length), __comp, + __tag.__get_num_threads()); + else + return __sequential_multiway_merge + </* __stable = */ true, /* __sentinels = */ false> + (__seqs_begin, __seqs_end, __target, + *(__seqs_begin->second), __length, __comp); + } + + // public interface + template<typename _RAIterPairIterator, + typename _RAIterOut, + typename _DifferenceTp, + typename _Compare> + _RAIterOut + stable_multiway_merge(_RAIterPairIterator __seqs_begin, + _RAIterPairIterator __seqs_end, + _RAIterOut __target, + _DifferenceTp __length, _Compare __comp, + parallel_tag __tag = parallel_tag(0)) + { + return stable_multiway_merge + (__seqs_begin, __seqs_end, __target, __length, __comp, + exact_tag(__tag.__get_num_threads())); + } + + // public interface + template<typename _RAIterPairIterator, + typename _RAIterOut, + typename _DifferenceTp, + typename _Compare> + _RAIterOut + stable_multiway_merge(_RAIterPairIterator __seqs_begin, + _RAIterPairIterator __seqs_end, + _RAIterOut __target, + _DifferenceTp __length, _Compare __comp, + default_parallel_tag __tag) + { + return stable_multiway_merge + (__seqs_begin, __seqs_end, __target, __length, __comp, + exact_tag(__tag.__get_num_threads())); + } + + /** + * @brief Multiway Merge Frontend. + * + * Merge the sequences specified by seqs_begin and __seqs_end into + * __target. __seqs_begin and __seqs_end must point to a sequence of + * pairs. These pairs must contain an iterator to the beginning + * of a sequence in their first entry and an iterator the _M_end of + * the same sequence in their second entry. + * + * Ties are broken arbitrarily. See stable_multiway_merge for a variant + * that breaks ties by sequence number but is slower. + * + * The first entries of the pairs (i.e. the begin iterators) will be moved + * forward accordingly. + * + * The output sequence has to provide enough space for all elements + * that are written to it. + * + * This function will merge the input sequences: + * + * - not stable + * - parallel, depending on the input size and Settings + * - using sampling for splitting + * - using sentinels + * + * You have to take care that the element the _M_end iterator points to is + * readable and contains a value that is greater than any other non-sentinel + * value in all sequences. + * + * Example: + * + * <pre> + * int sequences[10][11]; + * for (int __i = 0; __i < 10; ++__i) + * for (int __j = 0; __i < 11; ++__j) + * sequences[__i][__j] = __j; // __last one is sentinel! + * + * int __out[33]; + * std::vector<std::pair<int*> > seqs; + * for (int __i = 0; __i < 10; ++__i) + * { seqs.push(std::make_pair<int*>(sequences[__i], + * sequences[__i] + 10)) } + * + * multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33); + * </pre> + * + * @pre All input sequences must be sorted. + * @pre Target must provide enough space to merge out length elements or + * the number of elements in all sequences, whichever is smaller. + * @pre For each @c __i, @c __seqs_begin[__i].second must be the end + * marker of the sequence, but also reference the one more __sentinel + * element. + * + * @post [__target, return __value) contains merged __elements from the + * input sequences. + * @post return __value - __target = min(__length, number of elements in all + * sequences). + * + * @see stable_multiway_merge_sentinels + * + * @param _RAIterPairIterator iterator over sequence + * of pairs of iterators + * @param _RAIterOut iterator over target sequence + * @param _DifferenceTp difference type for the sequence + * @param _Compare strict weak ordering type to compare elements + * in sequences + * + * @param __seqs_begin __begin of sequence __sequence + * @param __seqs_end _M_end of sequence __sequence + * @param __target target sequence to merge to. + * @param __comp strict weak ordering to use for element comparison. + * @param __length Maximum length to merge, possibly larger than the + * number of elements available. + * + * @return _M_end iterator of output sequence + */ + // multiway_merge_sentinels + // public interface + template<typename _RAIterPairIterator, + typename _RAIterOut, + typename _DifferenceTp, + typename _Compare> + _RAIterOut + multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, + _RAIterPairIterator __seqs_end, + _RAIterOut __target, + _DifferenceTp __length, _Compare __comp, + __gnu_parallel::sequential_tag) + { + typedef _DifferenceTp _DifferenceType; + _GLIBCXX_CALL(__seqs_end - __seqs_begin) + + // catch special case: no sequences + if (__seqs_begin == __seqs_end) + return __target; + + // Execute multiway merge *sequentially*. + return __sequential_multiway_merge + </* __stable = */ false, /* __sentinels = */ true> + (__seqs_begin, __seqs_end, + __target, *(__seqs_begin->second), __length, __comp); + } + + // public interface + template<typename _RAIterPairIterator, + typename _RAIterOut, + typename _DifferenceTp, + typename _Compare> + _RAIterOut + multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, + _RAIterPairIterator __seqs_end, + _RAIterOut __target, + _DifferenceTp __length, _Compare __comp, + __gnu_parallel::exact_tag __tag) + { + typedef _DifferenceTp _DifferenceType; + _GLIBCXX_CALL(__seqs_end - __seqs_begin) + + // catch special case: no sequences + if (__seqs_begin == __seqs_end) + return __target; + + // Execute merge; maybe parallel, depending on the number of merged + // elements and the number of sequences and global thresholds in + // Settings. + if ((__seqs_end - __seqs_begin > 1) + && _GLIBCXX_PARALLEL_CONDITION( + ((__seqs_end - __seqs_begin) >= + __gnu_parallel::_Settings::get().multiway_merge_minimal_k) + && ((_SequenceIndex)__length >= + __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) + return parallel_multiway_merge + </* __stable = */ false, /* __sentinels = */ true> + (__seqs_begin, __seqs_end, __target, + multiway_merge_exact_splitting</* __stable = */ false, + typename std::iterator_traits<_RAIterPairIterator> + ::value_type*, _Compare, _DifferenceTp>, + static_cast<_DifferenceType>(__length), __comp, + __tag.__get_num_threads()); + else + return __sequential_multiway_merge + </* __stable = */ false, /* __sentinels = */ true> + (__seqs_begin, __seqs_end, __target, + *(__seqs_begin->second), __length, __comp); + } + + // public interface + template<typename _RAIterPairIterator, + typename _RAIterOut, + typename _DifferenceTp, + typename _Compare> + _RAIterOut + multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, + _RAIterPairIterator __seqs_end, + _RAIterOut __target, + _DifferenceTp __length, _Compare __comp, + sampling_tag __tag) + { + typedef _DifferenceTp _DifferenceType; + _GLIBCXX_CALL(__seqs_end - __seqs_begin) + + // catch special case: no sequences + if (__seqs_begin == __seqs_end) + return __target; + + // Execute merge; maybe parallel, depending on the number of merged + // elements and the number of sequences and global thresholds in + // Settings. + if ((__seqs_end - __seqs_begin > 1) + && _GLIBCXX_PARALLEL_CONDITION( + ((__seqs_end - __seqs_begin) >= + __gnu_parallel::_Settings::get().multiway_merge_minimal_k) + && ((_SequenceIndex)__length >= + __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) + return parallel_multiway_merge + </* __stable = */ false, /* __sentinels = */ true> + (__seqs_begin, __seqs_end, __target, + multiway_merge_sampling_splitting</* __stable = */ false, + typename std::iterator_traits<_RAIterPairIterator> + ::value_type*, _Compare, _DifferenceTp>, + static_cast<_DifferenceType>(__length), __comp, + __tag.__get_num_threads()); + else + return __sequential_multiway_merge + </* __stable = */false, /* __sentinels = */ true>( + __seqs_begin, __seqs_end, __target, + *(__seqs_begin->second), __length, __comp); + } + + // public interface + template<typename _RAIterPairIterator, + typename _RAIterOut, + typename _DifferenceTp, + typename _Compare> + _RAIterOut + multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, + _RAIterPairIterator __seqs_end, + _RAIterOut __target, + _DifferenceTp __length, _Compare __comp, + parallel_tag __tag = parallel_tag(0)) + { + return multiway_merge_sentinels + (__seqs_begin, __seqs_end, __target, __length, __comp, + exact_tag(__tag.__get_num_threads())); + } + + // public interface + template<typename _RAIterPairIterator, + typename _RAIterOut, + typename _DifferenceTp, + typename _Compare> + _RAIterOut + multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, + _RAIterPairIterator __seqs_end, + _RAIterOut __target, + _DifferenceTp __length, _Compare __comp, + default_parallel_tag __tag) + { + return multiway_merge_sentinels + (__seqs_begin, __seqs_end, __target, __length, __comp, + exact_tag(__tag.__get_num_threads())); + } + + // stable_multiway_merge_sentinels + // public interface + template<typename _RAIterPairIterator, + typename _RAIterOut, + typename _DifferenceTp, + typename _Compare> + _RAIterOut + stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, + _RAIterPairIterator __seqs_end, + _RAIterOut __target, + _DifferenceTp __length, _Compare __comp, + __gnu_parallel::sequential_tag) + { + typedef _DifferenceTp _DifferenceType; + _GLIBCXX_CALL(__seqs_end - __seqs_begin) + + // catch special case: no sequences + if (__seqs_begin == __seqs_end) + return __target; + + // Execute multiway merge *sequentially*. + return __sequential_multiway_merge + </* __stable = */ true, /* __sentinels = */ true> + (__seqs_begin, __seqs_end, __target, + *(__seqs_begin->second), __length, __comp); + } + + // public interface + template<typename _RAIterPairIterator, + typename _RAIterOut, + typename _DifferenceTp, + typename _Compare> + _RAIterOut + stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, + _RAIterPairIterator __seqs_end, + _RAIterOut __target, + _DifferenceTp __length, _Compare __comp, + __gnu_parallel::exact_tag __tag) + { + typedef _DifferenceTp _DifferenceType; + _GLIBCXX_CALL(__seqs_end - __seqs_begin) + + // catch special case: no sequences + if (__seqs_begin == __seqs_end) + return __target; + + // Execute merge; maybe parallel, depending on the number of merged + // elements and the number of sequences and global thresholds in + // Settings. + if ((__seqs_end - __seqs_begin > 1) + && _GLIBCXX_PARALLEL_CONDITION( + ((__seqs_end - __seqs_begin) >= + __gnu_parallel::_Settings::get().multiway_merge_minimal_k) + && ((_SequenceIndex)__length >= + __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) + return parallel_multiway_merge + </* __stable = */ true, /* __sentinels = */ true> + (__seqs_begin, __seqs_end, __target, + multiway_merge_exact_splitting</* __stable = */ true, + typename std::iterator_traits<_RAIterPairIterator> + ::value_type*, _Compare, _DifferenceTp>, + static_cast<_DifferenceType>(__length), __comp, + __tag.__get_num_threads()); + else + return __sequential_multiway_merge + </* __stable = */ true, /* __sentinels = */ true> + (__seqs_begin, __seqs_end, __target, + *(__seqs_begin->second), __length, __comp); + } + + // public interface + template<typename _RAIterPairIterator, + typename _RAIterOut, + typename _DifferenceTp, + typename _Compare> + _RAIterOut + stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, + _RAIterPairIterator __seqs_end, + _RAIterOut __target, + _DifferenceTp __length, + _Compare __comp, + sampling_tag __tag) + { + typedef _DifferenceTp _DifferenceType; + _GLIBCXX_CALL(__seqs_end - __seqs_begin) + + // catch special case: no sequences + if (__seqs_begin == __seqs_end) + return __target; + + // Execute merge; maybe parallel, depending on the number of merged + // elements and the number of sequences and global thresholds in + // Settings. + if ((__seqs_end - __seqs_begin > 1) + && _GLIBCXX_PARALLEL_CONDITION( + ((__seqs_end - __seqs_begin) >= + __gnu_parallel::_Settings::get().multiway_merge_minimal_k) + && ((_SequenceIndex)__length >= + __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) + return parallel_multiway_merge + </* __stable = */ true, /* __sentinels = */ true> + (__seqs_begin, __seqs_end, __target, + multiway_merge_sampling_splitting</* __stable = */ true, + typename std::iterator_traits<_RAIterPairIterator> + ::value_type*, _Compare, _DifferenceTp>, + static_cast<_DifferenceType>(__length), __comp, + __tag.__get_num_threads()); + else + return __sequential_multiway_merge + </* __stable = */ true, /* __sentinels = */ true> + (__seqs_begin, __seqs_end, __target, + *(__seqs_begin->second), __length, __comp); + } + + // public interface + template<typename _RAIterPairIterator, + typename _RAIterOut, + typename _DifferenceTp, + typename _Compare> + _RAIterOut + stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, + _RAIterPairIterator __seqs_end, + _RAIterOut __target, + _DifferenceTp __length, + _Compare __comp, + parallel_tag __tag = parallel_tag(0)) + { + return stable_multiway_merge_sentinels + (__seqs_begin, __seqs_end, __target, __length, __comp, + exact_tag(__tag.__get_num_threads())); + } + + // public interface + template<typename _RAIterPairIterator, + typename _RAIterOut, + typename _DifferenceTp, + typename _Compare> + _RAIterOut + stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, + _RAIterPairIterator __seqs_end, + _RAIterOut __target, + _DifferenceTp __length, _Compare __comp, + default_parallel_tag __tag) + { + return stable_multiway_merge_sentinels + (__seqs_begin, __seqs_end, __target, __length, __comp, + exact_tag(__tag.__get_num_threads())); + } +}; // namespace __gnu_parallel + +#endif /* _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H */ |