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, 0 insertions, 2140 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 deleted file mode 100644 index fe32053d6..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/parallel/multiway_merge.h +++ /dev/null @@ -1,2140 +0,0 @@ -// -*- 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 */ |