diff options
Diffstat (limited to 'gcc-4.4.3/libstdc++-v3/include/parallel/multiway_merge.h')
| -rw-r--r-- | gcc-4.4.3/libstdc++-v3/include/parallel/multiway_merge.h | 2140 |
1 files changed, 2140 insertions, 0 deletions
diff --git a/gcc-4.4.3/libstdc++-v3/include/parallel/multiway_merge.h b/gcc-4.4.3/libstdc++-v3/include/parallel/multiway_merge.h new file mode 100644 index 000000000..fe32053d6 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/parallel/multiway_merge.h @@ -0,0 +1,2140 @@ +// -*- 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 */ |