diff options
Diffstat (limited to 'gcc-4.4.3/libstdc++-v3/include/parallel/merge.h')
| -rw-r--r-- | gcc-4.4.3/libstdc++-v3/include/parallel/merge.h | 261 |
1 files changed, 261 insertions, 0 deletions
diff --git a/gcc-4.4.3/libstdc++-v3/include/parallel/merge.h b/gcc-4.4.3/libstdc++-v3/include/parallel/merge.h new file mode 100644 index 000000000..d947e258a --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/parallel/merge.h @@ -0,0 +1,261 @@ +// -*- 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/merge.h + * @brief Parallel implementation of std::merge(). + * This file is a GNU parallel extension to the Standard C++ Library. + */ + +// Written by Johannes Singler. + +#ifndef _GLIBCXX_PARALLEL_MERGE_H +#define _GLIBCXX_PARALLEL_MERGE_H 1 + +#include <parallel/basic_iterator.h> +#include <bits/stl_algo.h> + +namespace __gnu_parallel +{ + /** @brief Merge routine being able to merge only the @c max_length + * smallest elements. + * + * The @c begin iterators are advanced accordingly, they might not + * reach @c end, in contrast to the usual variant. + * @param begin1 Begin iterator of first sequence. + * @param end1 End iterator of first sequence. + * @param begin2 Begin iterator of second sequence. + * @param end2 End iterator of second sequence. + * @param target Target begin iterator. + * @param max_length Maximum number of elements to merge. + * @param comp Comparator. + * @return Output end iterator. */ + template<typename RandomAccessIterator1, typename RandomAccessIterator2, + typename OutputIterator, typename _DifferenceTp, + typename Comparator> + OutputIterator + merge_advance_usual(RandomAccessIterator1& begin1, + RandomAccessIterator1 end1, + RandomAccessIterator2& begin2, + RandomAccessIterator2 end2, OutputIterator target, + _DifferenceTp max_length, Comparator comp) + { + typedef _DifferenceTp difference_type; + while (begin1 != end1 && begin2 != end2 && max_length > 0) + { + // array1[i1] < array0[i0] + if (comp(*begin2, *begin1)) + *target++ = *begin2++; + else + *target++ = *begin1++; + --max_length; + } + + if (begin1 != end1) + { + target = std::copy(begin1, begin1 + max_length, target); + begin1 += max_length; + } + else + { + target = std::copy(begin2, begin2 + max_length, target); + begin2 += max_length; + } + return target; + } + + /** @brief Merge routine being able to merge only the @c max_length + * smallest elements. + * + * The @c begin iterators are advanced accordingly, they might not + * reach @c end, in contrast to the usual variant. + * Specially designed code should allow the compiler to generate + * conditional moves instead of branches. + * @param begin1 Begin iterator of first sequence. + * @param end1 End iterator of first sequence. + * @param begin2 Begin iterator of second sequence. + * @param end2 End iterator of second sequence. + * @param target Target begin iterator. + * @param max_length Maximum number of elements to merge. + * @param comp Comparator. + * @return Output end iterator. */ + template<typename RandomAccessIterator1, typename RandomAccessIterator2, + typename OutputIterator, typename _DifferenceTp, + typename Comparator> + OutputIterator + merge_advance_movc(RandomAccessIterator1& begin1, + RandomAccessIterator1 end1, + RandomAccessIterator2& begin2, + RandomAccessIterator2 end2, + OutputIterator target, + _DifferenceTp max_length, Comparator comp) + { + typedef _DifferenceTp difference_type; + typedef typename std::iterator_traits<RandomAccessIterator1>::value_type + value_type1; + typedef typename std::iterator_traits<RandomAccessIterator2>::value_type + value_type2; + +#if _GLIBCXX_ASSERTIONS + _GLIBCXX_PARALLEL_ASSERT(max_length >= 0); +#endif + + while (begin1 != end1 && begin2 != end2 && max_length > 0) + { + RandomAccessIterator1 next1 = begin1 + 1; + RandomAccessIterator2 next2 = begin2 + 1; + value_type1 element1 = *begin1; + value_type2 element2 = *begin2; + + if (comp(element2, element1)) + { + element1 = element2; + begin2 = next2; + } + else + begin1 = next1; + + *target = element1; + + ++target; + --max_length; + } + if (begin1 != end1) + { + target = std::copy(begin1, begin1 + max_length, target); + begin1 += max_length; + } + else + { + target = std::copy(begin2, begin2 + max_length, target); + begin2 += max_length; + } + return target; + } + + /** @brief Merge routine being able to merge only the @c max_length + * smallest elements. + * + * The @c begin iterators are advanced accordingly, they might not + * reach @c end, in contrast to the usual variant. + * Static switch on whether to use the conditional-move variant. + * @param begin1 Begin iterator of first sequence. + * @param end1 End iterator of first sequence. + * @param begin2 Begin iterator of second sequence. + * @param end2 End iterator of second sequence. + * @param target Target begin iterator. + * @param max_length Maximum number of elements to merge. + * @param comp Comparator. + * @return Output end iterator. */ + template<typename RandomAccessIterator1, typename RandomAccessIterator2, + typename OutputIterator, typename _DifferenceTp, + typename Comparator> + inline OutputIterator + merge_advance(RandomAccessIterator1& begin1, RandomAccessIterator1 end1, + RandomAccessIterator2& begin2, RandomAccessIterator2 end2, + OutputIterator target, _DifferenceTp max_length, + Comparator comp) + { + _GLIBCXX_CALL(max_length) + + return merge_advance_movc(begin1, end1, begin2, end2, target, + max_length, comp); + } + + /** @brief Merge routine fallback to sequential in case the + iterators of the two input sequences are of different type. + * @param begin1 Begin iterator of first sequence. + * @param end1 End iterator of first sequence. + * @param begin2 Begin iterator of second sequence. + * @param end2 End iterator of second sequence. + * @param target Target begin iterator. + * @param max_length Maximum number of elements to merge. + * @param comp Comparator. + * @return Output end iterator. */ + template<typename RandomAccessIterator1, typename RandomAccessIterator2, + typename RandomAccessIterator3, typename Comparator> + inline RandomAccessIterator3 + parallel_merge_advance(RandomAccessIterator1& begin1, + RandomAccessIterator1 end1, + RandomAccessIterator2& begin2, + // different iterators, parallel implementation + // not available + RandomAccessIterator2 end2, + RandomAccessIterator3 target, typename + std::iterator_traits<RandomAccessIterator1>:: + difference_type max_length, Comparator comp) + { return merge_advance(begin1, end1, begin2, end2, target, + max_length, comp); } + + /** @brief Parallel merge routine being able to merge only the @c + * max_length smallest elements. + * + * The @c begin iterators are advanced accordingly, they might not + * reach @c end, in contrast to the usual variant. + * The functionality is projected onto parallel_multiway_merge. + * @param begin1 Begin iterator of first sequence. + * @param end1 End iterator of first sequence. + * @param begin2 Begin iterator of second sequence. + * @param end2 End iterator of second sequence. + * @param target Target begin iterator. + * @param max_length Maximum number of elements to merge. + * @param comp Comparator. + * @return Output end iterator. + */ + template<typename RandomAccessIterator1, typename RandomAccessIterator3, + typename Comparator> + inline RandomAccessIterator3 + parallel_merge_advance(RandomAccessIterator1& begin1, + RandomAccessIterator1 end1, + RandomAccessIterator1& begin2, + RandomAccessIterator1 end2, + RandomAccessIterator3 target, typename + std::iterator_traits<RandomAccessIterator1>:: + difference_type max_length, Comparator comp) + { + typedef typename + std::iterator_traits<RandomAccessIterator1>::value_type value_type; + typedef typename std::iterator_traits<RandomAccessIterator1>:: + difference_type difference_type1 /* == difference_type2 */; + typedef typename std::iterator_traits<RandomAccessIterator3>:: + difference_type difference_type3; + typedef typename std::pair<RandomAccessIterator1, RandomAccessIterator1> + iterator_pair; + + iterator_pair + seqs[2] = { std::make_pair(begin1, end1), + std::make_pair(begin2, end2) }; + RandomAccessIterator3 + target_end = parallel_multiway_merge + < /* stable = */ true, /* sentinels = */ false>( + seqs, seqs + 2, target, + multiway_merge_exact_splitting + < /* stable = */ true, iterator_pair*, + Comparator, difference_type1>, + max_length, comp, omp_get_max_threads()); + + return target_end; + } +} //namespace __gnu_parallel + +#endif /* _GLIBCXX_PARALLEL_MERGE_H */ |