// -*- 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
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;
+ }
-// Announce guarded and unguarded iterator.
-
-template<typename _RAIter, typename _Compare>
- class _GuardedIterator;
-
-// Making the arguments const references seems to dangerous,
-// the user-defined comparator might not be const.
-template<typename _RAIter, typename _Compare>
- inline bool
- operator<(_GuardedIterator<_RAIter, _Compare>& __bi1,
- _GuardedIterator<_RAIter, _Compare>& __bi2);
-
-template<typename _RAIter, typename _Compare>
- inline bool
- operator<=(_GuardedIterator<_RAIter, _Compare>& __bi1,
- _GuardedIterator<_RAIter, _Compare>& __bi2);
-
-/** @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 _M_end End iterator of sequence.
- * @param __comp Comparator provided for associated overloaded
- * compare operators. */
- _GuardedIterator(_RAIter __begin,
- _RAIter _M_end, _Compare& __comp)
- : _M_current(__begin), _M_end(_M_end), __comp(__comp)
- { }
-
- /** @brief Pre-increment operator.
- * @return This. */
- _GuardedIterator<_RAIter, _Compare>&
- operator++()
+ /** @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
{
- ++_M_current;
- return *this;
- }
+ 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; }
-
- friend bool
- operator< <_RAIter, _Compare>(
- _GuardedIterator<_RAIter, _Compare>& __bi1,
- _GuardedIterator<_RAIter, _Compare>& __bi2);
-
- friend bool
- operator<= <_RAIter, _Compare>(
- _GuardedIterator<_RAIter, _Compare>& __bi1,
- _GuardedIterator<_RAIter, _Compare>& __bi2);
- };
-
-/** @brief Compare two elements referenced by guarded iterators.
- * @param __bi1 First iterator.
- * @param __bi2 Second iterator.
- * @return @__c true if less. */
-template<typename _RAIter, typename _Compare>
- inline 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. */
-template<typename _RAIter, typename _Compare>
- inline 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 unguarded_iterator;
-
-template<typename _RAIter, typename _Compare>
- inline bool
- operator<(unguarded_iterator<_RAIter, _Compare>& __bi1,
- unguarded_iterator<_RAIter, _Compare>& __bi2);
-
-template<typename _RAIter, typename _Compare>
- inline bool
- operator<=(unguarded_iterator<_RAIter, _Compare>& __bi1,
- unguarded_iterator<_RAIter, _Compare>& __bi2);
-
-template<typename _RAIter, typename _Compare>
- class unguarded_iterator
- {
- private:
- /** @brief Current iterator __position. */
- _RAIter _M_current;
- /** @brief _Compare. */
- mutable _Compare& __comp;
-
- public:
- /** @brief Constructor. Sets iterator to beginning of sequence.
- * @param __begin Begin iterator of sequence.
- * @param _M_end Unused, only for compatibility.
- * @param __comp Unused, only for compatibility. */
- unguarded_iterator(_RAIter __begin,
- _RAIter _M_end, _Compare& __comp)
- : _M_current(__begin), __comp(__comp)
- { }
-
- /** @brief Pre-increment operator.
- * @return This. */
- unguarded_iterator<_RAIter, _Compare>&
- operator++()
+ /** @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)
{
- ++_M_current;
- return *this;
- }
+ _GLIBCXX_CALL(__length);
- /** @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; }
-
- friend bool
- operator< <_RAIter, _Compare>(
- unguarded_iterator<_RAIter, _Compare>& __bi1,
- unguarded_iterator<_RAIter, _Compare>& __bi2);
-
- friend bool
- operator<= <_RAIter, _Compare>(
- unguarded_iterator<_RAIter, _Compare>& __bi1,
- unguarded_iterator<_RAIter, _Compare>& __bi2);
- };
-
-/** @brief Compare two elements referenced by unguarded iterators.
- * @param __bi1 First iterator.
- * @param __bi2 Second iterator.
- * @return @__c true if less. */
-template<typename _RAIter, typename _Compare>
- inline bool
- operator<(unguarded_iterator<_RAIter, _Compare>& __bi1,
- unguarded_iterator<_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. */
-template<typename _RAIter, typename _Compare>
- inline bool
- operator<=(unguarded_iterator<_RAIter, _Compare>& __bi1,
- unguarded_iterator<_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 <em>not</em> 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;
+ 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;
+ _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);
+ 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;
+ if (__seq0 <= __seq1)
+ {
+ if (__seq1 <= __seq2)
+ goto __s012;
else
- goto __s021;
- }
- else
- {
- if (__seq1 <= __seq2)
- {
- if (__seq0 <= __seq2)
- goto __s102;
+ if (__seq2 < __seq0)
+ goto __s201;
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, < , < );
+ 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:
- ;
+ __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);
+ _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 <em>not</em> 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)
- }
+ __seqs_begin[0].first = __seq0;
+ __seqs_begin[1].first = __seq1;
+ __seqs_begin[2].first = __seq2;
-#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, < , < , < );
+ 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)
+ __finish:
+ ;
- typedef _DifferenceTp _DifferenceType;
- typedef typename std::iterator_traits<_RAIterIterator>
- ::value_type::first_type
- _RAIter1;
- typedef typename std::iterator_traits<_RAIter1>::value_type
- _ValueType;
+ __seqs_begin[0].first = __seq0;
+ __seqs_begin[1].first = __seq1;
+ __seqs_begin[2].first = __seq2;
+ __seqs_begin[3].first = __seq3;
- int __k = static_cast<int>(__seqs_end - __seqs_begin);
+ return __target;
+ }
- LT __lt(__k, __comp);
+ /** @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)
- // Default value for potentially non-default-constructible types.
- _ValueType* __arbitrary_element = NULL;
+ 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;
- for (int __t = 0; __t < __k; ++__t)
- {
- if(__arbitrary_element == NULL
- && _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__t]) > 0)
- __arbitrary_element = &(*__seqs_begin[__t].first);
- }
+ _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
- for (int __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 __lt(__k, __comp);
- __lt.__init();
+ // Default value for potentially non-default-constructible types.
+ _ValueType* __arbitrary_element = 0;
- int source;
+ for (_SeqNumber __t = 0; __t < __k; ++__t)
+ {
+ if(!__arbitrary_element
+ && _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__t]) > 0)
+ __arbitrary_element = &(*__seqs_begin[__t].first);
+ }
- for (_DifferenceType __i = 0; __i < __length; ++__i)
- {
- //take __out
- source = __lt.__get_min_source();
+ 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);
+ }
- *(__target++) = *(__seqs_begin[source].first++);
+ __lt.__init();
- // 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);
- }
+ _SeqNumber __source;
- 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;
+ for (_DifferenceType __i = 0; __i < __length; ++__i)
+ {
+ //take out
+ __source = __lt.__get_min_source();
- typedef typename std::iterator_traits<_RAIterIterator>
- ::value_type::first_type
- _RAIter1;
- typedef typename std::iterator_traits<_RAIter1>::value_type
- _ValueType;
+ *(__target++) = *(__seqs_begin[__source].first++);
- int __k = __seqs_end - __seqs_begin;
+ // 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);
+ }
- LT __lt(__k, __sentinel, __comp);
+ return __target;
+ }
- for (int __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);
- }
+ /** @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;
- __lt.__init();
+ _SeqNumber __k = __seqs_end - __seqs_begin;
- int source;
+ _LT __lt(__k, __sentinel, __comp);
+ for (_SeqNumber __t = 0; __t < __k; ++__t)
+ {
#if _GLIBCXX_ASSERTIONS
- _DifferenceType __i = 0;
+ _GLIBCXX_PARALLEL_ASSERT(__seqs_begin[__t].first
+ != __seqs_begin[__t].second);
#endif
+ __lt.__insert_start(*__seqs_begin[__t].first, __t, false);
+ }
- _RAIter3 __target_end = __target + __length;
- while (__target < __target_end)
- {
- // Take out.
- source = __lt.__get_min_source();
+ __lt.__init();
+
+ _SeqNumber __source;
#if _GLIBCXX_ASSERTIONS
- _GLIBCXX_PARALLEL_ASSERT(0 <= source && source < __k);
- _GLIBCXX_PARALLEL_ASSERT(__i == 0
- || !__comp(*(__seqs_begin[source].first), *(__target - 1)));
+ _DifferenceType __i = 0;
#endif
- // Feed.
- *(__target++) = *(__seqs_begin[source].first++);
+ _RAIter3 __target_end = __target + __length;
+ while (__target < __target_end)
+ {
+ // Take out.
+ __source = __lt.__get_min_source();
#if _GLIBCXX_ASSERTIONS
- ++__i;
+ _GLIBCXX_PARALLEL_ASSERT(0 <= __source && __source < __k);
+ _GLIBCXX_PARALLEL_ASSERT(__i == 0
+ || !__comp(*(__seqs_begin[__source].first), *(__target - 1)));
#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 sequends _M_end behind the sentinel spots. 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);
+ // Feed.
+ *(__target++) = *(__seqs_begin[__source].first++);
#if _GLIBCXX_ASSERTIONS
- _GLIBCXX_PARALLEL_ASSERT(__target_end == __target + __length);
- _GLIBCXX_PARALLEL_ASSERT(__is_sorted(__target, __target_end, __comp));
+ ++__i;
#endif
+ // Replace from same __source.
+ __lt.__delete_min_insert(*__seqs_begin[__source].first, false);
+ }
- // 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
- * the 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.
+ 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.
*
- * The default behavior is to use pointers if the data type is four
- * times as big as the pointer to it.
+ * @return End iterator of output sequence.
*/
- 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<unguarded_iterator>(
- __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<unguarded_iterator>(
- __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,
+ 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)
- {
- 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>
- ::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
+ _RAIterIterator>::value_type::first_type>::value_type&
+ __sentinel,
+ _DifferenceTp __length,
+ _Compare __comp)
+ {
+ _GLIBCXX_CALL(__length)
- _DifferenceTp __total_length = 0;
- for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
- __total_length += _GLIBCXX_PARALLEL_LENGTH(*__s);
+ 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;
- __length = std::min<_DifferenceTp>(__length, __total_length);
+ _RAIter3 __target_end;
- if(__length == 0)
- return __target;
+ 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);
- _RAIter3 __return_target = __target;
- int __k = static_cast<int>(__seqs_end - __seqs_begin);
+ __target_end = multiway_merge_loser_tree_unguarded<UnguardedLoserTree>
+ (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);
- 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));
+ _GLIBCXX_PARALLEL_ASSERT(__target_end == __target + __length);
+ _GLIBCXX_PARALLEL_ASSERT(__is_sorted(__target, __target_end, __comp));
#endif
- return __return_target;
- }
+ // 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);
-/**
- * @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>
- ::value_type::first_type
- _RAIter1;
- typedef typename std::iterator_traits<_RAIter1>::value_type
- _ValueType;
+ return __target_end;
+ }
- // __k sequences.
- int __k = static_cast<int>(__seqs_end - __seqs_begin);
+ /**
+ * @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*));
+ };
- int __num_threads = omp_get_num_threads();
+ /**
+ * @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); }
+ };
- _DifferenceType __num_samples =
- __gnu_parallel::_Settings::get().merge_oversampling * __num_threads;
+ /**
+ * @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); }
+ };
- _ValueType* __samples = static_cast<_ValueType*>(
- ::operator new(sizeof(_ValueType) * __k * __num_samples));
- // Sample.
- for (int __s = 0; __s < __k; ++__s)
- for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
+ /**
+ * @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)
{
- _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]);
+ 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);
}
+ };
- // Sort stable or non-stable, depending on value of template parameter
- // "__stable".
- _SamplingSorter<__stable, _ValueType*, _Compare>()(
- __samples, __samples + (__num_samples * __k), __comp);
-
- for (int __slab = 0; __slab < __num_threads; ++__slab)
- // For each slab / processor.
- for (int __seq = 0; __seq < __k; ++__seq)
+ /**
+ * @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)
{
- // 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]);
+ 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);
}
- ::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>
- ::value_type::first_type
- _RAIter1;
+ };
- const bool __tight = (__total_length == __length);
+ /** @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;
- // __k sequences.
- const int __k = static_cast<int>(__seqs_end - __seqs_begin);
+#if _GLIBCXX_ASSERTIONS
+ for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
+ {
+ _GLIBCXX_PARALLEL_ASSERT(__is_sorted((*__s).first,
+ (*__s).second, __comp));
+ }
+#endif
- const int __num_threads = omp_get_num_threads();
+ _DifferenceTp __total_length = 0;
+ for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
+ __total_length += _GLIBCXX_PARALLEL_LENGTH(*__s);
- // (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);
+ __length = std::min<_DifferenceTp>(__length, __total_length);
- copy(__seqs_begin, __seqs_end, __se.begin());
+ if(__length == 0)
+ return __target;
- _DifferenceType* __borders =
- new _DifferenceType[__num_threads + 1];
- equally_split(__length, __num_threads, __borders);
+ _RAIter3 __return_target = __target;
+ _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
- for (int __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);
- }
+ 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;
}
- delete[] __borders;
- for (int __slab = 0; __slab < __num_threads; ++__slab)
+ /**
+ * @brief Stable sorting functor.
+ *
+ * Used to reduce code instanciation in multiway_merge_sampling_splitting.
+ */
+ template<bool __stable, class _RAIter, class _StrictWeakOrdering>
+ struct _SamplingSorter
{
- // For each slab / processor.
- for (int __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]);
- }
- }
+ 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);
}
- 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)
+
+ /**
+ * @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);
+ _GLIBCXX_PARALLEL_ASSERT(__seqs_end - __seqs_begin > 1);
#endif
- _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;
-
- // Leave only non-empty sequences.
- typedef std::pair<_RAIter1, _RAIter1> seq_type;
- seq_type* __ne_seqs = new seq_type[__seqs_end - __seqs_begin];
- int __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(__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)
+ _GLIBCXX_CALL(__total_length)
- __length = std::min<_DifferenceTp>(__length, __total_length);
+ __length = std::min<_DifferenceTp>(__length, __total_length);
- if (__total_length == 0 || __k == 0)
- {
- delete[] __ne_seqs;
- return __target;
- }
+ if (__total_length == 0 || __k == 0)
+ {
+ delete[] __ne_seqs;
+ return __target;
+ }
- std::vector<std::pair<_DifferenceType, _DifferenceType> >* __pieces;
+ std::vector<std::pair<_DifferenceType, _DifferenceType> >* __pieces;
- __num_threads = static_cast<_ThreadIndex>
- (std::min<_DifferenceType>(__num_threads, __total_length));
+ __num_threads = static_cast<_ThreadIndex>
+ (std::min<_DifferenceType>(__num_threads, __total_length));
-# pragma omp parallel num_threads (__num_threads)
- {
+# 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 (int __s = 0; __s < __num_threads; ++__s)
- __pieces[__s].resize(__k);
+ {
+ __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;
+ _DifferenceType __num_samples =
+ __gnu_parallel::_Settings::get().merge_oversampling
+ * __num_threads;
- splitter(__ne_seqs, __ne_seqs + __k, __length, __total_length,
- __comp, __pieces);
- } //single
+ __splitter(__ne_seqs, __ne_seqs + __k, __length, __total_length,
+ __comp, __pieces);
+ } //single
- _ThreadIndex __iam = omp_get_thread_num();
+ _ThreadIndex __iam = omp_get_thread_num();
- _DifferenceType __target_position = 0;
+ _DifferenceType __target_position = 0;
- for (int __c = 0; __c < __k; ++__c)
- __target_position += __pieces[__iam][__c].first;
+ for (_SeqNumber __c = 0; __c < __k; ++__c)
+ __target_position += __pieces[__iam][__c].first;
- seq_type* __chunks = new seq_type[__k];
+ seq_type* __chunks = new seq_type[__k];
- for (int __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);
- }
+ 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);
+ 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
+ delete[] __chunks;
+ } // parallel
#if _GLIBCXX_ASSERTIONS
- _GLIBCXX_PARALLEL_ASSERT(__is_sorted(__target, __target + __length, __comp));
+ _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;
- }
+ __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;
+ delete[] __pieces;
+ delete[] __ne_seqs;
- return __target + __length;
- }
+ 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)
+ /**
+ * @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;
+ // 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
+ // 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::sampling_tag __tag)
-{
- typedef _DifferenceTp _DifferenceType;
- _GLIBCXX_CALL(__seqs_end - __seqs_begin)
+ </* __stable = */ false, /* __sentinels = */ false>
+ (__seqs_begin, __seqs_end, __target,
+ *(__seqs_begin->second), __length, __comp);
+ }
- // catch special case: no sequences
- if (__seqs_begin == __seqs_end)
- return __target;
+ // 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);
+ }
- // 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)
+ // 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);
+ }
- // catch special case: no sequences
- if (__seqs_begin == __seqs_end)
- return __target;
+ // 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)
- // 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;
- // 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);
+ }
- // 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)
+ // 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);
+ }
- // catch special case: no sequences
- if (__seqs_begin == __seqs_end)
- return __target;
+ // 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);
+ }
- // 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)
+ // 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()));
+ }
- // catch special case: no sequences
- if (__seqs_begin == __seqs_end)
- return __target;
+ // 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()));
+ }
- // 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)
+ /**
+ * @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;
+ // 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
+ // 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
- , sampling_tag __tag)
-{
- typedef _DifferenceTp _DifferenceType;
- _GLIBCXX_CALL(__seqs_end - __seqs_begin)
+ </* __stable = */ false, /* __sentinels = */ true>
+ (__seqs_begin, __seqs_end,
+ __target, *(__seqs_begin->second), __length, __comp);
+ }
- // catch special case: no sequences
- if (__seqs_begin == __seqs_end)
- return __target;
+ // 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);
+ }
- // 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)
+ // 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);
+ }
- // catch special case: no sequences
- if (__seqs_begin == __seqs_end)
- return __target;
+ // 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()));
+ }
- // 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)
+ // 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()));
+ }
- // catch special case: no sequences
- if (__seqs_begin == __seqs_end)
- return __target;
+ // 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)
- // 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;
- // 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);
+ }
- // 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) >=
+ // 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 >=
+ && ((_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()));
-}
+ 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 */