--- /dev/null
+// -*- C++ -*-
+
+// Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
+// <http://www.gnu.org/licenses/>.
+
+/** @file parallel/multiway_merge.h
+* @brief Implementation of sequential and parallel multiway merge.
+*
+* Explanations on the high-speed merging routines in the appendix of
+*
+* P. Sanders.
+* Fast priority queues for cached memory.
+* ACM Journal of Experimental Algorithmics, 5, 2000.
+*
+* This file is a GNU parallel extension to the Standard C++ Library.
+*/
+
+// Written by Johannes Singler and Manuel Holtgrewe.
+
+#ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
+#define _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
+
+#include <vector>
+
+#include <bits/stl_algo.h>
+#include <parallel/features.h>
+#include <parallel/parallel.h>
+#include <parallel/losertree.h>
+#if _GLIBCXX_ASSERTIONS
+#include <parallel/checkers.h>
+#endif
+
+/** @brief Length of a sequence described by a pair of iterators. */
+#define _GLIBCXX_PARALLEL_LENGTH(s) ((s).second - (s).first)
+
+namespace __gnu_parallel
+{
+
+// Announce guarded and unguarded iterator.
+
+template<typename RandomAccessIterator, typename Comparator>
+ class guarded_iterator;
+
+// Making the arguments const references seems to dangerous,
+// the user-defined comparator might not be const.
+template<typename RandomAccessIterator, typename Comparator>
+ inline bool
+ operator<(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
+ guarded_iterator<RandomAccessIterator, Comparator>& bi2);
+
+template<typename RandomAccessIterator, typename Comparator>
+ inline bool
+ operator<=(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
+ guarded_iterator<RandomAccessIterator, Comparator>& 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 RandomAccessIterator is not possible since
+ * RandomAccessIterator need not be a class.
+ */
+template<typename RandomAccessIterator, typename Comparator>
+ class guarded_iterator
+ {
+ private:
+ /** @brief Current iterator position. */
+ RandomAccessIterator current;
+
+ /** @brief End iterator of the sequence. */
+ RandomAccessIterator end;
+
+ /** @brief Comparator. */
+ Comparator& 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. */
+ guarded_iterator(RandomAccessIterator begin,
+ RandomAccessIterator end, Comparator& comp)
+ : current(begin), end(end), comp(comp)
+ { }
+
+ /** @brief Pre-increment operator.
+ * @return This. */
+ guarded_iterator<RandomAccessIterator, Comparator>&
+ operator++()
+ {
+ ++current;
+ return *this;
+ }
+
+ /** @brief Dereference operator.
+ * @return Referenced element. */
+ typename std::iterator_traits<RandomAccessIterator>::value_type&
+ operator*()
+ { return *current; }
+
+ /** @brief Convert to wrapped iterator.
+ * @return Wrapped iterator. */
+ operator RandomAccessIterator()
+ { return current; }
+
+ friend bool
+ operator< <RandomAccessIterator, Comparator>(
+ guarded_iterator<RandomAccessIterator, Comparator>& bi1,
+ guarded_iterator<RandomAccessIterator, Comparator>& bi2);
+
+ friend bool
+ operator<= <RandomAccessIterator, Comparator>(
+ guarded_iterator<RandomAccessIterator, Comparator>& bi1,
+ guarded_iterator<RandomAccessIterator, Comparator>& bi2);
+ };
+
+/** @brief Compare two elements referenced by guarded iterators.
+ * @param bi1 First iterator.
+ * @param bi2 Second iterator.
+ * @return @c True if less. */
+template<typename RandomAccessIterator, typename Comparator>
+ inline bool
+ operator<(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
+ guarded_iterator<RandomAccessIterator, Comparator>& bi2)
+ {
+ if (bi1.current == bi1.end) //bi1 is sup
+ return bi2.current == bi2.end; //bi2 is not sup
+ if (bi2.current == bi2.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 RandomAccessIterator, typename Comparator>
+ inline bool
+ operator<=(guarded_iterator<RandomAccessIterator, Comparator>& bi1,
+ guarded_iterator<RandomAccessIterator, Comparator>& bi2)
+ {
+ if (bi2.current == bi2.end) //bi1 is sup
+ return bi1.current != bi1.end; //bi2 is not sup
+ if (bi1.current == bi1.end) //bi2 is sup
+ return false;
+ return !(bi1.comp)(*bi2, *bi1); //normal compare
+ }
+
+template<typename RandomAccessIterator, typename Comparator>
+ class unguarded_iterator;
+
+template<typename RandomAccessIterator, typename Comparator>
+ inline bool
+ operator<(unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
+ unguarded_iterator<RandomAccessIterator, Comparator>& bi2);
+
+template<typename RandomAccessIterator, typename Comparator>
+ inline bool
+ operator<=(unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
+ unguarded_iterator<RandomAccessIterator, Comparator>& bi2);
+
+template<typename RandomAccessIterator, typename Comparator>
+ class unguarded_iterator
+ {
+ private:
+ /** @brief Current iterator position. */
+ RandomAccessIterator current;
+ /** @brief Comparator. */
+ mutable Comparator& 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. */
+ unguarded_iterator(RandomAccessIterator begin,
+ RandomAccessIterator end, Comparator& comp)
+ : current(begin), comp(comp)
+ { }
+
+ /** @brief Pre-increment operator.
+ * @return This. */
+ unguarded_iterator<RandomAccessIterator, Comparator>&
+ operator++()
+ {
+ ++current;
+ return *this;
+ }
+
+ /** @brief Dereference operator.
+ * @return Referenced element. */
+ typename std::iterator_traits<RandomAccessIterator>::value_type&
+ operator*()
+ { return *current; }
+
+ /** @brief Convert to wrapped iterator.
+ * @return Wrapped iterator. */
+ operator RandomAccessIterator()
+ { return current; }
+
+ friend bool
+ operator< <RandomAccessIterator, Comparator>(
+ unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
+ unguarded_iterator<RandomAccessIterator, Comparator>& bi2);
+
+ friend bool
+ operator<= <RandomAccessIterator, Comparator>(
+ unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
+ unguarded_iterator<RandomAccessIterator, Comparator>& bi2);
+ };
+
+/** @brief Compare two elements referenced by unguarded iterators.
+ * @param bi1 First iterator.
+ * @param bi2 Second iterator.
+ * @return @c True if less. */
+template<typename RandomAccessIterator, typename Comparator>
+ inline bool
+ operator<(unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
+ unguarded_iterator<RandomAccessIterator, Comparator>& 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 RandomAccessIterator, typename Comparator>
+ inline bool
+ operator<=(unguarded_iterator<RandomAccessIterator, Comparator>& bi1,
+ unguarded_iterator<RandomAccessIterator, Comparator>& 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 out 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 out 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 RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Comparator>
+ RandomAccessIterator3
+ multiway_merge_3_variant(
+ RandomAccessIteratorIterator seqs_begin,
+ RandomAccessIteratorIterator seqs_end,
+ RandomAccessIterator3 target,
+ _DifferenceTp length, Comparator comp)
+ {
+ _GLIBCXX_CALL(length);
+
+ typedef _DifferenceTp difference_type;
+
+ typedef typename std::iterator_traits<RandomAccessIteratorIterator>
+ ::value_type::first_type
+ RandomAccessIterator1;
+ typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
+ value_type;
+
+ if (length == 0)
+ return target;
+
+#if _GLIBCXX_ASSERTIONS
+ _DifferenceTp orig_length = length;
+#endif
+
+ iterator<RandomAccessIterator1, Comparator>
+ seq0(seqs_begin[0].first, seqs_begin[0].second, comp),
+ seq1(seqs_begin[1].first, seqs_begin[1].second, comp),
+ seq2(seqs_begin[2].first, seqs_begin[2].second, comp);
+
+ if (seq0 <= seq1)
+ {
+ if (seq1 <= seq2)
+ goto s012;
+ else
+ if (seq2 < seq0)
+ goto s201;
+ else
+ goto s021;
+ }
+ else
+ {
+ if (seq1 <= seq2)
+ {
+ if (seq0 <= seq2)
+ goto s102;
+ else
+ goto s120;
+ }
+ else
+ goto s210;
+ }
+#define _GLIBCXX_PARALLEL_MERGE_3_CASE(a,b,c,c0,c1) \
+ s ## a ## b ## c : \
+ *target = *seq ## a; \
+ ++target; \
+ --length; \
+ ++seq ## a; \
+ if (length == 0) goto finish; \
+ if (seq ## a c0 seq ## b) goto s ## a ## b ## c; \
+ if (seq ## a c1 seq ## c) goto s ## b ## a ## c; \
+ goto s ## b ## c ## a;
+
+ _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 1, 2, <=, <=);
+ _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 2, 0, <=, < );
+ _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 0, 1, < , < );
+ _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 0, 2, < , <=);
+ _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 2, 1, <=, <=);
+ _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 1, 0, < , < );
+
+#undef _GLIBCXX_PARALLEL_MERGE_3_CASE
+
+ finish:
+ ;
+
+#if _GLIBCXX_ASSERTIONS
+ _GLIBCXX_PARALLEL_ASSERT(
+ ((RandomAccessIterator1)seq0 - seqs_begin[0].first) +
+ ((RandomAccessIterator1)seq1 - seqs_begin[1].first) +
+ ((RandomAccessIterator1)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 out 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 out 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 RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Comparator>
+ RandomAccessIterator3
+ multiway_merge_4_variant(RandomAccessIteratorIterator seqs_begin,
+ RandomAccessIteratorIterator seqs_end,
+ RandomAccessIterator3 target,
+ _DifferenceTp length, Comparator comp)
+ {
+ _GLIBCXX_CALL(length);
+ typedef _DifferenceTp difference_type;
+
+ typedef typename std::iterator_traits<RandomAccessIteratorIterator>
+ ::value_type::first_type
+ RandomAccessIterator1;
+ typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
+ value_type;
+
+ iterator<RandomAccessIterator1, Comparator>
+ 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 out 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 RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Comparator>
+ RandomAccessIterator3
+ multiway_merge_loser_tree(RandomAccessIteratorIterator seqs_begin,
+ RandomAccessIteratorIterator seqs_end,
+ RandomAccessIterator3 target,
+ _DifferenceTp length, Comparator comp)
+ {
+ _GLIBCXX_CALL(length)
+
+ typedef _DifferenceTp difference_type;
+ typedef typename std::iterator_traits<RandomAccessIteratorIterator>
+ ::value_type::first_type
+ RandomAccessIterator1;
+ typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
+ value_type;
+
+ int k = static_cast<int>(seqs_end - seqs_begin);
+
+ LT lt(k, comp);
+
+ // Default value for potentially non-default-constructible types.
+ value_type* arbitrary_element = NULL;
+
+ for (int t = 0; t < k; ++t)
+ {
+ if(arbitrary_element == NULL
+ && _GLIBCXX_PARALLEL_LENGTH(seqs_begin[t]) > 0)
+ arbitrary_element = &(*seqs_begin[t].first);
+ }
+
+ 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.init();
+
+ int source;
+
+ for (difference_type i = 0; i < length; ++i)
+ {
+ //take out
+ source = lt.get_min_source();
+
+ *(target++) = *(seqs_begin[source].first++);
+
+ // Feed.
+ if (seqs_begin[source].first == seqs_begin[source].second)
+ lt.delete_min_insert(*arbitrary_element, true);
+ else
+ // Replace from same source.
+ lt.delete_min_insert(*seqs_begin[source].first, false);
+ }
+
+ return target;
+ }
+
+/** @brief Multi-way merging procedure for a high branching factor,
+ * unguarded case.
+ *
+ * Merging is done using the LoserTree class <tt>LT</tt>.
+ *
+ * Stability is selected by the used LoserTrees.
+ *
+ * @pre No input will run out of elements during the merge.
+ *
+ * @param seqs_begin Begin iterator of iterator pair input sequence.
+ * @param seqs_end End iterator of iterator pair input sequence.
+ * @param target Begin iterator out 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 RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp, typename Comparator>
+ RandomAccessIterator3
+ multiway_merge_loser_tree_unguarded(
+ RandomAccessIteratorIterator seqs_begin,
+ RandomAccessIteratorIterator seqs_end,
+ RandomAccessIterator3 target,
+ const typename std::iterator_traits<typename std::iterator_traits<
+ RandomAccessIteratorIterator>::value_type::first_type>::value_type&
+ sentinel,
+ _DifferenceTp length,
+ Comparator comp)
+ {
+ _GLIBCXX_CALL(length)
+ typedef _DifferenceTp difference_type;
+
+ typedef typename std::iterator_traits<RandomAccessIteratorIterator>
+ ::value_type::first_type
+ RandomAccessIterator1;
+ typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
+ value_type;
+
+ int k = seqs_end - seqs_begin;
+
+ LT lt(k, sentinel, comp);
+
+ 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);
+ }
+
+ lt.init();
+
+ int source;
+
+#if _GLIBCXX_ASSERTIONS
+ difference_type i = 0;
+#endif
+
+ RandomAccessIterator3 target_end = target + length;
+ while (target < target_end)
+ {
+ // Take out.
+ source = lt.get_min_source();
+
+#if _GLIBCXX_ASSERTIONS
+ _GLIBCXX_PARALLEL_ASSERT(0 <= source && source < k);
+ _GLIBCXX_PARALLEL_ASSERT(i == 0
+ || !comp(*(seqs_begin[source].first), *(target - 1)));
+#endif
+
+ // Feed.
+ *(target++) = *(seqs_begin[source].first++);
+
+#if _GLIBCXX_ASSERTIONS
+ ++i;
+#endif
+ // Replace from same source.
+ lt.delete_min_insert(*seqs_begin[source].first, false);
+ }
+
+ return target;
+ }
+
+
+/** @brief Multi-way merging procedure for a high branching factor,
+ * requiring sentinels to exist.
+ *
+ * @param stable The value must the same as for the used LoserTrees.
+ * @param UnguardedLoserTree Loser Tree variant to use for the unguarded
+ * merging.
+ * @param GuardedLoserTree Loser Tree variant to use for the guarded
+ * merging.
+ *
+ * @param seqs_begin Begin iterator of iterator pair input sequence.
+ * @param seqs_end End iterator of iterator pair input sequence.
+ * @param target Begin iterator out 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 RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Comparator>
+ RandomAccessIterator3
+ multiway_merge_loser_tree_sentinel(
+ RandomAccessIteratorIterator seqs_begin,
+ RandomAccessIteratorIterator seqs_end,
+ RandomAccessIterator3 target,
+ const typename std::iterator_traits<typename std::iterator_traits<
+ RandomAccessIteratorIterator>::value_type::first_type>::value_type&
+ sentinel,
+ _DifferenceTp length,
+ Comparator comp)
+ {
+ _GLIBCXX_CALL(length)
+
+ typedef _DifferenceTp difference_type;
+ typedef std::iterator_traits<RandomAccessIteratorIterator> traits_type;
+ typedef typename std::iterator_traits<RandomAccessIteratorIterator>
+ ::value_type::first_type
+ RandomAccessIterator1;
+ typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
+ value_type;
+
+ RandomAccessIterator3 target_end;
+
+ for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s)
+ // Move the sequends 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);
+
+#if _GLIBCXX_ASSERTIONS
+ _GLIBCXX_PARALLEL_ASSERT(target_end == target + length);
+ _GLIBCXX_PARALLEL_ASSERT(is_sorted(target, target_end, comp));
+#endif
+
+ // Restore the sequence ends so the sentinels are not contained in the
+ // sequence any more (see comment in loop above).
+ for (RandomAccessIteratorIterator 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 "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 loser_tree_traits<int>
+ * { static const bool use_pointer = false; };
+ *
+ * template<>
+ * struct loser_tree_traits<heavyweight_type>
+ * { static const bool use_pointer = true; };
+ *
+ * @param T type to give the loser tree traits for.
+ */
+template <typename T>
+struct loser_tree_traits
+{
+ /**
+ * @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 use_pointer = (sizeof(T) > 4 * sizeof(T*));
+};
+
+/**
+ * @brief Switch for 3-way merging with sentinels turned off.
+ *
+ * Note that 3-way merging is always stable!
+ */
+template<
+ bool sentinels /*default == false*/,
+ typename RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Comparator>
+struct multiway_merge_3_variant_sentinel_switch
+{
+ RandomAccessIterator3 operator()(
+ RandomAccessIteratorIterator seqs_begin,
+ RandomAccessIteratorIterator seqs_end,
+ RandomAccessIterator3 target,
+ _DifferenceTp length, Comparator comp)
+ {
+ return multiway_merge_3_variant<guarded_iterator>(
+ 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 RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Comparator>
+struct multiway_merge_3_variant_sentinel_switch
+ <true, RandomAccessIteratorIterator, RandomAccessIterator3,
+ _DifferenceTp, Comparator>
+{
+ RandomAccessIterator3 operator()(
+ RandomAccessIteratorIterator seqs_begin,
+ RandomAccessIteratorIterator seqs_end,
+ RandomAccessIterator3 target,
+ _DifferenceTp length, Comparator 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 RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Comparator>
+struct multiway_merge_4_variant_sentinel_switch
+{
+ RandomAccessIterator3 operator()(
+ RandomAccessIteratorIterator seqs_begin,
+ RandomAccessIteratorIterator seqs_end,
+ RandomAccessIterator3 target,
+ _DifferenceTp length, Comparator comp)
+ {
+ return multiway_merge_4_variant<guarded_iterator>(
+ 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 RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Comparator>
+struct multiway_merge_4_variant_sentinel_switch
+ <true, RandomAccessIteratorIterator, RandomAccessIterator3,
+ _DifferenceTp, Comparator>
+{
+ RandomAccessIterator3 operator()(
+ RandomAccessIteratorIterator seqs_begin,
+ RandomAccessIteratorIterator seqs_end,
+ RandomAccessIterator3 target,
+ _DifferenceTp length, Comparator 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 RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Comparator>
+struct multiway_merge_k_variant_sentinel_switch
+{
+ RandomAccessIterator3 operator()(
+ RandomAccessIteratorIterator seqs_begin,
+ RandomAccessIteratorIterator seqs_end,
+ RandomAccessIterator3 target,
+ const typename std::iterator_traits<typename std::iterator_traits<
+ RandomAccessIteratorIterator>::value_type::first_type>::value_type&
+ sentinel,
+ _DifferenceTp length, Comparator comp)
+ {
+ typedef typename std::iterator_traits<RandomAccessIteratorIterator>
+ ::value_type::first_type
+ RandomAccessIterator1;
+ typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
+ value_type;
+
+ return multiway_merge_loser_tree_sentinel<
+ typename __gnu_cxx::__conditional_type<
+ loser_tree_traits<value_type>::use_pointer
+ , LoserTreePointerUnguarded<stable, value_type, Comparator>
+ , LoserTreeUnguarded<stable, value_type, Comparator>
+ >::__type>(seqs_begin, seqs_end, target, sentinel, length, comp);
+ }
+};
+
+/**
+ * @brief Switch for k-way merging with sentinels turned off.
+ */
+template<
+ bool stable,
+ typename RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Comparator>
+struct multiway_merge_k_variant_sentinel_switch
+ <false, stable, RandomAccessIteratorIterator, RandomAccessIterator3,
+ _DifferenceTp, Comparator>
+{
+ RandomAccessIterator3 operator()(
+ RandomAccessIteratorIterator seqs_begin,
+ RandomAccessIteratorIterator seqs_end,
+ RandomAccessIterator3 target,
+ const typename std::iterator_traits<typename std::iterator_traits<
+ RandomAccessIteratorIterator>::value_type::first_type>::value_type&
+ sentinel,
+ _DifferenceTp length, Comparator comp)
+ {
+ typedef typename std::iterator_traits<RandomAccessIteratorIterator>
+ ::value_type::first_type
+ RandomAccessIterator1;
+ typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
+ value_type;
+
+ return multiway_merge_loser_tree<
+ typename __gnu_cxx::__conditional_type<
+ loser_tree_traits<value_type>::use_pointer
+ , LoserTreePointer<stable, value_type, Comparator>
+ , LoserTree<stable, value_type, Comparator>
+ >::__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 out 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 RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Comparator>
+ RandomAccessIterator3
+ sequential_multiway_merge(
+ RandomAccessIteratorIterator seqs_begin,
+ RandomAccessIteratorIterator seqs_end,
+ RandomAccessIterator3 target,
+ const typename std::iterator_traits<typename std::iterator_traits<
+ RandomAccessIteratorIterator>::value_type::first_type>::value_type&
+ sentinel,
+ _DifferenceTp length, Comparator comp)
+ {
+ _GLIBCXX_CALL(length)
+
+ typedef _DifferenceTp difference_type;
+ typedef typename std::iterator_traits<RandomAccessIteratorIterator>
+ ::value_type::first_type
+ RandomAccessIterator1;
+ typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
+ value_type;
+
+#if _GLIBCXX_ASSERTIONS
+ for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s)
+ {
+ _GLIBCXX_PARALLEL_ASSERT(is_sorted((*s).first, (*s).second, comp));
+ }
+#endif
+
+ _DifferenceTp total_length = 0;
+ for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s)
+ total_length += _GLIBCXX_PARALLEL_LENGTH(*s);
+
+ length = std::min<_DifferenceTp>(length, total_length);
+
+ if(length == 0)
+ return target;
+
+ RandomAccessIterator3 return_target = target;
+ int k = static_cast<int>(seqs_end - seqs_begin);
+
+ switch (k)
+ {
+ case 0:
+ break;
+ case 1:
+ return_target = std::copy(seqs_begin[0].first,
+ seqs_begin[0].first + length,
+ target);
+ seqs_begin[0].first += length;
+ break;
+ case 2:
+ return_target = merge_advance(seqs_begin[0].first,
+ seqs_begin[0].second,
+ seqs_begin[1].first,
+ seqs_begin[1].second,
+ target, length, comp);
+ break;
+ case 3:
+ return_target = multiway_merge_3_variant_sentinel_switch<
+ sentinels
+ , RandomAccessIteratorIterator
+ , RandomAccessIterator3
+ , _DifferenceTp
+ , Comparator>()(seqs_begin, seqs_end, target, length, comp);
+ break;
+ case 4:
+ return_target = multiway_merge_4_variant_sentinel_switch<
+ sentinels
+ , RandomAccessIteratorIterator
+ , RandomAccessIterator3
+ , _DifferenceTp
+ , Comparator>()(seqs_begin, seqs_end, target, length, comp);
+ break;
+ default:
+ return_target = multiway_merge_k_variant_sentinel_switch<
+ sentinels
+ , stable
+ , RandomAccessIteratorIterator
+ , RandomAccessIterator3
+ , _DifferenceTp
+ , Comparator>()(seqs_begin, seqs_end, target, sentinel, length, comp);
+ break;
+ }
+#if _GLIBCXX_ASSERTIONS
+ _GLIBCXX_PARALLEL_ASSERT(is_sorted(target, target + length, comp));
+#endif
+
+ return return_target;
+ }
+
+/**
+ * @brief Stable sorting functor.
+ *
+ * Used to reduce code instanciation in multiway_merge_sampling_splitting.
+ */
+template<bool stable, class RandomAccessIterator, class StrictWeakOrdering>
+struct sampling_sorter
+{
+ void operator()(RandomAccessIterator first, RandomAccessIterator 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 RandomAccessIterator, class StrictWeakOrdering>
+struct sampling_sorter<false, RandomAccessIterator, StrictWeakOrdering>
+{
+ void operator()(RandomAccessIterator first, RandomAccessIterator last,
+ StrictWeakOrdering comp)
+ { __gnu_sequential::sort(first, last, comp); }
+};
+
+/**
+ * @brief Sampling based splitting for parallel multiway-merge routine.
+ */
+template<
+ bool stable
+ , typename RandomAccessIteratorIterator
+ , typename Comparator
+ , typename difference_type>
+void multiway_merge_sampling_splitting(
+ RandomAccessIteratorIterator seqs_begin,
+ RandomAccessIteratorIterator seqs_end,
+ difference_type length, difference_type total_length, Comparator comp,
+ std::vector<std::pair<difference_type, difference_type> > *pieces)
+{
+ typedef typename std::iterator_traits<RandomAccessIteratorIterator>
+ ::value_type::first_type
+ RandomAccessIterator1;
+ typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
+ value_type;
+
+ // k sequences.
+ int k = static_cast<int>(seqs_end - seqs_begin);
+
+ int num_threads = omp_get_num_threads();
+
+ difference_type num_samples =
+ __gnu_parallel::_Settings::get().merge_oversampling * num_threads;
+
+ value_type* samples = static_cast<value_type*>(
+ ::operator new(sizeof(value_type) * k * num_samples));
+ // Sample.
+ for (int s = 0; s < k; ++s)
+ for (difference_type i = 0; i < num_samples; ++i)
+ {
+ difference_type sample_index =
+ static_cast<difference_type>(
+ _GLIBCXX_PARALLEL_LENGTH(seqs_begin[s])
+ * (double(i + 1) / (num_samples + 1))
+ * (double(length) / total_length));
+ new(&(samples[s * num_samples + i]))
+ value_type(seqs_begin[s].first[sample_index]);
+ }
+
+ // Sort stable or non-stable, depending on value of template parameter
+ // "stable".
+ sampling_sorter<stable, value_type*, Comparator>()(
+ 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)
+ {
+ // 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]);
+ }
+ ::operator delete(samples);
+}
+
+/**
+ * @brief Exact splitting for parallel multiway-merge routine.
+ *
+ * None of the passed sequences may be empty.
+ */
+template<
+ bool stable
+ , typename RandomAccessIteratorIterator
+ , typename Comparator
+ , typename difference_type>
+void multiway_merge_exact_splitting(
+ RandomAccessIteratorIterator seqs_begin,
+ RandomAccessIteratorIterator seqs_end,
+ difference_type length, difference_type total_length, Comparator comp,
+ std::vector<std::pair<difference_type, difference_type> > *pieces)
+{
+ typedef typename std::iterator_traits<RandomAccessIteratorIterator>
+ ::value_type::first_type
+ RandomAccessIterator1;
+
+ const bool tight = (total_length == length);
+
+ // k sequences.
+ const int k = static_cast<int>(seqs_end - seqs_begin);
+
+ const int num_threads = omp_get_num_threads();
+
+ // (Settings::multiway_merge_splitting == __gnu_parallel::_Settings::EXACT).
+ std::vector<RandomAccessIterator1>* offsets =
+ new std::vector<RandomAccessIterator1>[num_threads];
+ std::vector<
+ std::pair<RandomAccessIterator1, RandomAccessIterator1>
+ > se(k);
+
+ copy(seqs_begin, seqs_end, se.begin());
+
+ difference_type* borders =
+ new difference_type[num_threads + 1];
+ equally_split(length, num_threads, borders);
+
+ 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(),
+ difference_type(length),
+ offsets[num_threads - 1].begin(), comp);
+ }
+ }
+ delete[] borders;
+
+ for (int slab = 0; slab < num_threads; ++slab)
+ {
+ // 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]);
+ }
+ }
+ }
+ 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 out 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 RandomAccessIteratorIterator,
+ typename RandomAccessIterator3,
+ typename _DifferenceTp,
+ typename Splitter,
+ typename Comparator
+ >
+ RandomAccessIterator3
+ parallel_multiway_merge(RandomAccessIteratorIterator seqs_begin,
+ RandomAccessIteratorIterator seqs_end,
+ RandomAccessIterator3 target,
+ Splitter splitter,
+ _DifferenceTp length,
+ Comparator comp,
+ thread_index_t num_threads)
+ {
+#if _GLIBCXX_ASSERTIONS
+ _GLIBCXX_PARALLEL_ASSERT(seqs_end - seqs_begin > 1);
+#endif
+
+ _GLIBCXX_CALL(length)
+
+ typedef _DifferenceTp difference_type;
+ typedef typename std::iterator_traits<RandomAccessIteratorIterator>
+ ::value_type::first_type
+ RandomAccessIterator1;
+ typedef typename
+ std::iterator_traits<RandomAccessIterator1>::value_type value_type;
+
+ // Leave only non-empty sequences.
+ typedef std::pair<RandomAccessIterator1, RandomAccessIterator1> seq_type;
+ seq_type* ne_seqs = new seq_type[seqs_end - seqs_begin];
+ int k = 0;
+ difference_type total_length = 0;
+ for (RandomAccessIteratorIterator raii = seqs_begin;
+ raii != seqs_end; ++raii)
+ {
+ _DifferenceTp seq_length = _GLIBCXX_PARALLEL_LENGTH(*raii);
+ if(seq_length > 0)
+ {
+ total_length += seq_length;
+ ne_seqs[k++] = *raii;
+ }
+ }
+
+ _GLIBCXX_CALL(total_length)
+
+ length = std::min<_DifferenceTp>(length, total_length);
+
+ if (total_length == 0 || k == 0)
+ {
+ delete[] ne_seqs;
+ return target;
+ }
+
+ std::vector<std::pair<difference_type, difference_type> >* pieces;
+
+ num_threads = static_cast<thread_index_t>
+ (std::min<difference_type>(num_threads, total_length));
+
+# pragma omp parallel num_threads (num_threads)
+ {
+# pragma omp single
+ {
+ num_threads = omp_get_num_threads();
+ // Thread t will have to merge pieces[iam][0..k - 1]
+ pieces = new std::vector<
+ std::pair<difference_type, difference_type> >[num_threads];
+ for (int s = 0; s < num_threads; ++s)
+ pieces[s].resize(k);
+
+ difference_type num_samples =
+ __gnu_parallel::_Settings::get().merge_oversampling *
+ num_threads;
+
+ splitter(ne_seqs, ne_seqs + k, length, total_length,
+ comp, pieces);
+ } //single
+
+ thread_index_t iam = omp_get_thread_num();
+
+ difference_type target_position = 0;
+
+ for (int c = 0; c < k; ++c)
+ target_position += pieces[iam][c].first;
+
+ 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);
+ }
+
+ if(length > target_position)
+ sequential_multiway_merge<stable, sentinels>(
+ chunks, chunks + k, target + target_position,
+ *(seqs_begin->second), length - target_position, comp);
+
+ delete[] chunks;
+ } // parallel
+
+#if _GLIBCXX_ASSERTIONS
+ _GLIBCXX_PARALLEL_ASSERT(is_sorted(target, target + length, comp));
+#endif
+
+ k = 0;
+ // Update ends of sequences.
+ for (RandomAccessIteratorIterator raii = seqs_begin;
+ raii != seqs_end; ++raii)
+ {
+ _DifferenceTp length = _GLIBCXX_PARALLEL_LENGTH(*raii);
+ if(length > 0)
+ (*raii).first += pieces[num_threads - 1][k++].second;
+ }
+
+ delete[] pieces;
+ delete[] ne_seqs;
+
+ return target + length;
+ }
+
+/**
+ * @brief Multiway Merge Frontend.
+ *
+ * Merge the sequences specified by seqs_begin and seqs_end into
+ * target. seqs_begin and seqs_end must point to a sequence of
+ * pairs. These pairs must contain an iterator to the beginning
+ * of a sequence in their first entry and an iterator the 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 RandomAccessIteratorPairIterator iterator over sequence
+ * of pairs of iterators
+ * @param RandomAccessIteratorOut iterator over target sequence
+ * @param _DifferenceTp difference type for the sequence
+ * @param Comparator strict weak ordering type to compare elements
+ * in sequences
+ *
+ * @param seqs_begin begin of sequence sequence
+ * @param seqs_end 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 end iterator of output sequence
+ */
+// multiway_merge
+// public interface
+template<
+ typename RandomAccessIteratorPairIterator
+ , typename RandomAccessIteratorOut
+ , typename _DifferenceTp
+ , typename Comparator>
+RandomAccessIteratorOut
+multiway_merge(RandomAccessIteratorPairIterator seqs_begin
+ , RandomAccessIteratorPairIterator seqs_end
+ , RandomAccessIteratorOut target
+ , _DifferenceTp length, Comparator comp
+ , __gnu_parallel::sequential_tag)
+{
+ typedef _DifferenceTp difference_type;
+ _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 RandomAccessIteratorPairIterator
+ , typename RandomAccessIteratorOut
+ , typename _DifferenceTp
+ , typename Comparator>
+RandomAccessIteratorOut
+multiway_merge(RandomAccessIteratorPairIterator seqs_begin
+ , RandomAccessIteratorPairIterator seqs_end
+ , RandomAccessIteratorOut target
+ , _DifferenceTp length, Comparator comp
+ , __gnu_parallel::exact_tag tag)
+{
+ typedef _DifferenceTp difference_type;
+ _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)
+ && ((sequence_index_t)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<RandomAccessIteratorPairIterator>
+ ::value_type*, Comparator, _DifferenceTp>,
+ static_cast<difference_type>(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 RandomAccessIteratorPairIterator
+ , typename RandomAccessIteratorOut
+ , typename _DifferenceTp
+ , typename Comparator>
+RandomAccessIteratorOut
+multiway_merge(RandomAccessIteratorPairIterator seqs_begin
+ , RandomAccessIteratorPairIterator seqs_end
+ , RandomAccessIteratorOut target
+ , _DifferenceTp length, Comparator comp
+ , __gnu_parallel::sampling_tag tag)
+{
+ typedef _DifferenceTp difference_type;
+ _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)
+ && ((sequence_index_t)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<RandomAccessIteratorPairIterator>
+ ::value_type*, Comparator, _DifferenceTp>,
+ static_cast<difference_type>(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 RandomAccessIteratorPairIterator
+ , typename RandomAccessIteratorOut
+ , typename _DifferenceTp
+ , typename Comparator>
+RandomAccessIteratorOut
+multiway_merge(RandomAccessIteratorPairIterator seqs_begin
+ , RandomAccessIteratorPairIterator seqs_end
+ , RandomAccessIteratorOut target
+ , _DifferenceTp length, Comparator 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 RandomAccessIteratorPairIterator
+ , typename RandomAccessIteratorOut
+ , typename _DifferenceTp
+ , typename Comparator>
+RandomAccessIteratorOut
+multiway_merge(RandomAccessIteratorPairIterator seqs_begin
+ , RandomAccessIteratorPairIterator seqs_end
+ , RandomAccessIteratorOut target
+ , _DifferenceTp length, Comparator 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 RandomAccessIteratorPairIterator
+ , typename RandomAccessIteratorOut
+ , typename _DifferenceTp
+ , typename Comparator>
+RandomAccessIteratorOut
+stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
+ , RandomAccessIteratorPairIterator seqs_end
+ , RandomAccessIteratorOut target
+ , _DifferenceTp length, Comparator comp
+ , __gnu_parallel::sequential_tag)
+{
+ typedef _DifferenceTp difference_type;
+ _GLIBCXX_CALL(seqs_end - seqs_begin)
+
+ // catch special case: no sequences
+ if (seqs_begin == seqs_end)
+ return target;
+
+ // Execute multiway merge *sequentially*.
+ return sequential_multiway_merge
+ </* stable = */ true, /* sentinels = */ false>
+ (seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
+}
+
+// public interface
+template<
+ typename RandomAccessIteratorPairIterator
+ , typename RandomAccessIteratorOut
+ , typename _DifferenceTp
+ , typename Comparator>
+RandomAccessIteratorOut
+stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
+ , RandomAccessIteratorPairIterator seqs_end
+ , RandomAccessIteratorOut target
+ , _DifferenceTp length, Comparator comp
+ , __gnu_parallel::exact_tag tag)
+{
+ typedef _DifferenceTp difference_type;
+ _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)
+ && ((sequence_index_t)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<RandomAccessIteratorPairIterator>
+ ::value_type*, Comparator, _DifferenceTp>,
+ static_cast<difference_type>(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 RandomAccessIteratorPairIterator
+ , typename RandomAccessIteratorOut
+ , typename _DifferenceTp
+ , typename Comparator>
+RandomAccessIteratorOut
+stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
+ , RandomAccessIteratorPairIterator seqs_end
+ , RandomAccessIteratorOut target
+ , _DifferenceTp length, Comparator comp
+ , sampling_tag tag)
+{
+ typedef _DifferenceTp difference_type;
+ _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)
+ && ((sequence_index_t)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<RandomAccessIteratorPairIterator>
+ ::value_type*, Comparator, _DifferenceTp>,
+ static_cast<difference_type>(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 RandomAccessIteratorPairIterator
+ , typename RandomAccessIteratorOut
+ , typename _DifferenceTp
+ , typename Comparator>
+RandomAccessIteratorOut
+stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
+ , RandomAccessIteratorPairIterator seqs_end
+ , RandomAccessIteratorOut target
+ , _DifferenceTp length, Comparator 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 RandomAccessIteratorPairIterator
+ , typename RandomAccessIteratorOut
+ , typename _DifferenceTp
+ , typename Comparator>
+RandomAccessIteratorOut
+stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
+ , RandomAccessIteratorPairIterator seqs_end
+ , RandomAccessIteratorOut target
+ , _DifferenceTp length, Comparator 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 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 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 RandomAccessIteratorPairIterator iterator over sequence
+ * of pairs of iterators
+ * @param RandomAccessIteratorOut iterator over target sequence
+ * @param _DifferenceTp difference type for the sequence
+ * @param Comparator strict weak ordering type to compare elements
+ * in sequences
+ *
+ * @param seqs_begin begin of sequence sequence
+ * @param seqs_end 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 end iterator of output sequence
+ */
+// multiway_merge_sentinels
+// public interface
+template<
+ typename RandomAccessIteratorPairIterator
+ , typename RandomAccessIteratorOut
+ , typename _DifferenceTp
+ , typename Comparator>
+RandomAccessIteratorOut
+multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
+ , RandomAccessIteratorPairIterator seqs_end
+ , RandomAccessIteratorOut target
+ , _DifferenceTp length, Comparator comp
+ , __gnu_parallel::sequential_tag)
+{
+ typedef _DifferenceTp difference_type;
+ _GLIBCXX_CALL(seqs_end - seqs_begin)
+
+ // catch special case: no sequences
+ if (seqs_begin == seqs_end)
+ return target;
+
+ // Execute multiway merge *sequentially*.
+ return sequential_multiway_merge
+ </* stable = */ false, /* sentinels = */ true>
+ (seqs_begin, seqs_end,
+ target, *(seqs_begin->second), length, comp);
+}
+
+// public interface
+template<
+ typename RandomAccessIteratorPairIterator
+ , typename RandomAccessIteratorOut
+ , typename _DifferenceTp
+ , typename Comparator>
+RandomAccessIteratorOut
+multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
+ , RandomAccessIteratorPairIterator seqs_end
+ , RandomAccessIteratorOut target
+ , _DifferenceTp length, Comparator comp
+ , __gnu_parallel::exact_tag tag)
+{
+ typedef _DifferenceTp difference_type;
+ _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)
+ && ((sequence_index_t)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<RandomAccessIteratorPairIterator>
+ ::value_type*, Comparator, _DifferenceTp>,
+ static_cast<difference_type>(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 RandomAccessIteratorPairIterator
+ , typename RandomAccessIteratorOut
+ , typename _DifferenceTp
+ , typename Comparator>
+RandomAccessIteratorOut
+multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
+ , RandomAccessIteratorPairIterator seqs_end
+ , RandomAccessIteratorOut target
+ , _DifferenceTp length, Comparator comp
+ , sampling_tag tag)
+{
+ typedef _DifferenceTp difference_type;
+ _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)
+ && ((sequence_index_t)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<RandomAccessIteratorPairIterator>
+ ::value_type*, Comparator, _DifferenceTp>,
+ static_cast<difference_type>(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 RandomAccessIteratorPairIterator
+ , typename RandomAccessIteratorOut
+ , typename _DifferenceTp
+ , typename Comparator>
+RandomAccessIteratorOut
+multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
+ , RandomAccessIteratorPairIterator seqs_end
+ , RandomAccessIteratorOut target
+ , _DifferenceTp length, Comparator 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 RandomAccessIteratorPairIterator
+ , typename RandomAccessIteratorOut
+ , typename _DifferenceTp
+ , typename Comparator>
+RandomAccessIteratorOut
+multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
+ , RandomAccessIteratorPairIterator seqs_end
+ , RandomAccessIteratorOut target
+ , _DifferenceTp length, Comparator 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 RandomAccessIteratorPairIterator
+ , typename RandomAccessIteratorOut
+ , typename _DifferenceTp
+ , typename Comparator>
+RandomAccessIteratorOut
+stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
+ , RandomAccessIteratorPairIterator seqs_end
+ , RandomAccessIteratorOut target
+ , _DifferenceTp length, Comparator comp
+ , __gnu_parallel::sequential_tag)
+{
+ typedef _DifferenceTp difference_type;
+ _GLIBCXX_CALL(seqs_end - seqs_begin)
+
+ // catch special case: no sequences
+ if (seqs_begin == seqs_end)
+ return target;
+
+ // Execute multiway merge *sequentially*.
+ return sequential_multiway_merge
+ </* stable = */ true, /* sentinels = */ true>
+ (seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
+}
+
+// public interface
+template<
+ typename RandomAccessIteratorPairIterator
+ , typename RandomAccessIteratorOut
+ , typename _DifferenceTp
+ , typename Comparator>
+RandomAccessIteratorOut
+stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
+ , RandomAccessIteratorPairIterator seqs_end
+ , RandomAccessIteratorOut target
+ , _DifferenceTp length, Comparator comp
+ , __gnu_parallel::exact_tag tag)
+{
+ typedef _DifferenceTp difference_type;
+ _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)
+ && ((sequence_index_t)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<RandomAccessIteratorPairIterator>
+ ::value_type*, Comparator, _DifferenceTp>,
+ static_cast<difference_type>(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 RandomAccessIteratorPairIterator
+ , typename RandomAccessIteratorOut
+ , typename _DifferenceTp
+ , typename Comparator>
+RandomAccessIteratorOut
+stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
+ , RandomAccessIteratorPairIterator seqs_end
+ , RandomAccessIteratorOut target
+ , _DifferenceTp length, Comparator comp
+ , sampling_tag tag)
+{
+ typedef _DifferenceTp difference_type;
+ _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)
+ && ((sequence_index_t)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<RandomAccessIteratorPairIterator>
+ ::value_type*, Comparator, _DifferenceTp>,
+ static_cast<difference_type>(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 RandomAccessIteratorPairIterator
+ , typename RandomAccessIteratorOut
+ , typename _DifferenceTp
+ , typename Comparator>
+RandomAccessIteratorOut
+stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
+ , RandomAccessIteratorPairIterator seqs_end
+ , RandomAccessIteratorOut target
+ , _DifferenceTp length, Comparator 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 RandomAccessIteratorPairIterator
+ , typename RandomAccessIteratorOut
+ , typename _DifferenceTp
+ , typename Comparator>
+RandomAccessIteratorOut
+stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
+ , RandomAccessIteratorPairIterator seqs_end
+ , RandomAccessIteratorOut target
+ , _DifferenceTp length, Comparator 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 */
projects / msp430-gcc.git / blobdiff