// -*- C++ -*-
-// Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008, 2009, 2010, 2011 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
#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 Current iterator __position. */
_RAIter _M_current;
/** @brief _Compare. */
- mutable _Compare& __comp;
+ _Compare& __comp;
public:
/** @brief Constructor. Sets iterator to beginning of sequence.
*
* This works well for merging up to 4 sequences.
*
- * Note that making the merging stable does <em>not</em> come at a
+ * 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
*
* This works well for merging up to 4 sequences.
*
- * Note that making the merging stable does <em>not</em> come at a
+ * 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
_LT __lt(__k, __comp);
// Default value for potentially non-default-constructible types.
- _ValueType* __arbitrary_element = NULL;
+ _ValueType* __arbitrary_element = 0;
for (_SeqNumber __t = 0; __t < __k; ++__t)
{
- if(__arbitrary_element == NULL
+ if(!__arbitrary_element
&& _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__t]) > 0)
__arbitrary_element = &(*__seqs_begin[__t].first);
}
/** @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);
}
_DifferenceType* __borders =
new _DifferenceType[__num_threads + 1];
- equally_split(__length, __num_threads, __borders);
+ __equally_split(__length, __num_threads, __borders);
for (_ThreadIndex __s = 0; __s < (__num_threads - 1); ++__s)
{
*
* 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
OSDN Git Service
