diff options
Diffstat (limited to 'libstdc++-v3/include/parallel/list_partition.h')
| -rw-r--r-- | libstdc++-v3/include/parallel/list_partition.h | 179 |
1 files changed, 179 insertions, 0 deletions
diff --git a/libstdc++-v3/include/parallel/list_partition.h b/libstdc++-v3/include/parallel/list_partition.h new file mode 100644 index 000000000..1f1bfa22e --- /dev/null +++ b/libstdc++-v3/include/parallel/list_partition.h @@ -0,0 +1,179 @@ +// -*- 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 _IIter> + void + __shrink_and_double(std::vector<_IIter>& __os_starts, + size_t& __count_to_two, size_t& __range_length, + const bool __make_twice) + { + ++__count_to_two; + if (!__make_twice || __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 _IIter> + void + __shrink(std::vector<_IIter>& __os_starts, size_t& __count_to_two, + size_t& __range_length) + { + for (typename std::vector<_IIter>::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 + * \sqrt{\mathrm{__end} - \mathrm{__begin}} + * __elements. Otherwise, the ratio between the + * longest and the shortest part is bounded by + * 1/(\mathrm{__oversampling} \cdot \mathrm{num\_parts}) + * @return Length of the whole sequence. + */ + template<typename _IIter, typename _FunctorType> + size_t + list_partition(const _IIter __begin, const _IIter __end, + _IIter* __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<_IIter> __os_starts(2 * __oversampling * __num_parts + 1); + + __os_starts[0] = __begin; + _IIter __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 */ |