#include <parallel/features.h>
#include <parallel/parallel.h>
#include <parallel/losertree.h>
+#include <parallel/multiseq_selection.h>
#if _GLIBCXX_ASSERTIONS
#include <parallel/checkers.h>
#endif
namespace __gnu_parallel
{
+ template<typename _RAIter1, typename _RAIter2, typename _OutputIterator,
+ typename _DifferenceTp, typename _Compare>
+ _OutputIterator
+ __merge_advance(_RAIter1&, _RAIter1, _RAIter2&, _RAIter2,
+ _OutputIterator, _DifferenceTp, _Compare);
+
/** @brief _Iterator wrapper supporting an implicit supremum at the end
* of the sequence, dominating all comparisons.
*
/** @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
+ * @tparam UnguardedLoserTree _Loser Tree variant to use for the unguarded
* merging.
*
* @param __seqs_begin Begin iterator of iterator pair input 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,
_ValueType;
// __k sequences.
- _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
+ const _SeqNumber __k
+ = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
- _ThreadIndex __num_threads = omp_get_num_threads();
+ const _ThreadIndex __num_threads = omp_get_num_threads();
- _DifferenceType __num_samples =
+ const _DifferenceType __num_samples =
__gnu_parallel::_Settings::get().merge_oversampling * __num_threads;
_ValueType* __samples = static_cast<_ValueType*>
__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);
}
*
* Must not be called if the number of sequences is 1.
*
- * @param _Splitter functor to split input (either __exact or sampling based)
+ * @tparam _Splitter functor to split input (either __exact or sampling based)
+ * @tparam __stable Stable merging incurs a performance penalty.
+ * @tparam __sentinel Ignored.
*
* @param __seqs_begin Begin iterator of iterator pair input sequence.
* @param __seqs_end End iterator of iterator pair input 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,
__length = std::min<_DifferenceTp>(__length, __total_length);
if (__total_length == 0 || __k == 0)
- {
- delete[] __ne_seqs;
- return __target;
- }
+ {
+ delete[] __ne_seqs;
+ return __target;
+ }
std::vector<std::pair<_DifferenceType, _DifferenceType> >* __pieces;
* @post return __value - __target = min(__length, number of elements in all
* sequences).
*
- * @param _RAIterPairIterator iterator over sequence
+ * @tparam _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
+ * @tparam _RAIterOut iterator over target sequence
+ * @tparam _DifferenceTp difference type for the sequence
+ * @tparam _Compare strict weak ordering type to compare elements
* in sequences
*
* @param __seqs_begin __begin of sequence __sequence
*
* @see stable_multiway_merge_sentinels
*
- * @param _RAIterPairIterator iterator over sequence
+ * @tparam _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
+ * @tparam _RAIterOut iterator over target sequence
+ * @tparam _DifferenceTp difference type for the sequence
+ * @tparam _Compare strict weak ordering type to compare elements
* in sequences
*
* @param __seqs_begin __begin of sequence __sequence