diff options
Diffstat (limited to 'gcc-4.4.3/libstdc++-v3/include/parallel/list_partition.h')
| -rw-r--r-- | gcc-4.4.3/libstdc++-v3/include/parallel/list_partition.h | 176 |
1 files changed, 0 insertions, 176 deletions
diff --git a/gcc-4.4.3/libstdc++-v3/include/parallel/list_partition.h b/gcc-4.4.3/libstdc++-v3/include/parallel/list_partition.h deleted file mode 100644 index a359a3f3a..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/parallel/list_partition.h +++ /dev/null @@ -1,176 +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/list_partition.h - * @brief Functionality to split sequence referenced by only input - * iterators. - * This file is a GNU parallel extension to the Standard C++ Library. - */ - -// Written by Leonor Frias Moya and Johannes Singler. - -#ifndef _GLIBCXX_PARALLEL_LIST_PARTITION_H -#define _GLIBCXX_PARALLEL_LIST_PARTITION_H 1 - -#include <parallel/parallel.h> -#include <vector> - -namespace __gnu_parallel -{ - /** @brief Shrinks and doubles the ranges. - * @param os_starts Start positions worked on (oversampled). - * @param count_to_two Counts up to 2. - * @param range_length Current length of a chunk. - * @param make_twice Whether the @c os_starts is allowed to be - * grown or not - */ - template<typename InputIterator> - void - shrink_and_double(std::vector<InputIterator>& os_starts, - size_t& count_to_two, size_t& range_length, - const bool make_twice) - { - ++count_to_two; - if (not make_twice or count_to_two < 2) - shrink(os_starts, count_to_two, range_length); - else - { - os_starts.resize((os_starts.size() - 1) * 2 + 1); - count_to_two = 0; - } - } - - /** @brief Combines two ranges into one and thus halves the number of ranges. - * @param os_starts Start positions worked on (oversampled). - * @param count_to_two Counts up to 2. - * @param range_length Current length of a chunk. */ - template<typename InputIterator> - void - shrink(std::vector<InputIterator>& os_starts, size_t& count_to_two, - size_t& range_length) - { - for (typename std::vector<InputIterator>::size_type i = 0; - i <= (os_starts.size() / 2); ++i) - os_starts[i] = os_starts[i * 2]; - range_length *= 2; - } - - /** @brief Splits a sequence given by input iterators into parts of - * almost equal size - * - * The function needs only one pass over the sequence. - * @param begin Begin iterator of input sequence. - * @param end End iterator of input sequence. - * @param starts Start iterators for the resulting parts, dimension - * @c num_parts+1. For convenience, @c starts @c [num_parts] - * contains the end iterator of the sequence. - * @param lengths Length of the resulting parts. - * @param num_parts Number of parts to split the sequence into. - * @param f Functor to be applied to each element by traversing it - * @param oversampling Oversampling factor. If 0, then the - * partitions will differ in at most @f$ \sqrt{\mathrm{end} - - * \mathrm{begin}} @f$ elements. Otherwise, the ratio between the - * longest and the shortest part is bounded by @f$ - * 1/(\mathrm{oversampling} \cdot \mathrm{num\_parts}) @f$. - * @return Length of the whole sequence. - */ - template<typename InputIterator, typename FunctorType> - size_t - list_partition(const InputIterator begin, const InputIterator end, - InputIterator* starts, size_t* lengths, const int num_parts, - FunctorType& f, int oversampling = 0) - { - bool make_twice = false; - - // The resizing algorithm is chosen according to the oversampling factor. - if (oversampling == 0) - { - make_twice = true; - oversampling = 1; - } - - std::vector<InputIterator> os_starts(2 * oversampling * num_parts + 1); - - os_starts[0]= begin; - InputIterator prev = begin, it = begin; - size_t dist_limit = 0, dist = 0; - size_t cur = 1, next = 1; - size_t range_length = 1; - size_t count_to_two = 0; - while (it != end) - { - cur = next; - for (; cur < os_starts.size() and it != end; ++cur) - { - for (dist_limit += range_length; - dist < dist_limit and it != end; ++dist) - { - f(it); - ++it; - } - os_starts[cur] = it; - } - - // Must compare for end and not cur < os_starts.size() , because - // cur could be == os_starts.size() as well - if (it == end) - break; - - shrink_and_double(os_starts, count_to_two, range_length, make_twice); - next = os_starts.size() / 2 + 1; - } - - // Calculation of the parts (one must be extracted from current - // because the partition beginning at end, consists only of - // itself). - size_t size_part = (cur - 1) / num_parts; - int size_greater = static_cast<int>((cur - 1) % num_parts); - starts[0] = os_starts[0]; - - size_t index = 0; - - // Smallest partitions. - for (int i = 1; i < (num_parts + 1 - size_greater); ++i) - { - lengths[i - 1] = size_part * range_length; - index += size_part; - starts[i] = os_starts[index]; - } - - // Biggest partitions. - for (int i = num_parts + 1 - size_greater; i <= num_parts; ++i) - { - lengths[i - 1] = (size_part+1) * range_length; - index += (size_part+1); - starts[i] = os_starts[index]; - } - - // Correction of the end size (the end iteration has not finished). - lengths[num_parts - 1] -= (dist_limit - dist); - - return dist; - } -} - -#endif /* _GLIBCXX_PARALLEL_LIST_PARTITION_H */ |