]>
Commit | Line | Data |
---|---|---|
6482a45c | 1 | // -*- C++ -*- |
2 | ||
fbd26352 | 3 | // Copyright (C) 2007-2019 Free Software Foundation, Inc. |
6482a45c | 4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
34475802 | 6 | // software; you can redistribute __it and/or modify __it under the terms |
6482a45c | 7 | // of the GNU General Public License as published by the Free Software |
6bc9506f | 8 | // Foundation; either version 3, or (at your option) any later |
6482a45c | 9 | // version. |
10 | ||
34475802 | 11 | // This library is distributed in the hope that __it will be useful, but |
6482a45c | 12 | // WITHOUT ANY WARRANTY; without even the implied warranty of |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | // General Public License for more details. | |
15 | ||
6bc9506f | 16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
19 | ||
20 | // You should have received a copy of the GNU General Public License and | |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
6482a45c | 24 | |
25 | /** @file parallel/list_partition.h | |
34475802 | 26 | * @brief _Functionality to split __sequence referenced by only input |
6482a45c | 27 | * iterators. |
28 | * This file is a GNU parallel extension to the Standard C++ Library. | |
29 | */ | |
30 | ||
31 | // Written by Leonor Frias Moya and Johannes Singler. | |
32 | ||
33 | #ifndef _GLIBCXX_PARALLEL_LIST_PARTITION_H | |
34 | #define _GLIBCXX_PARALLEL_LIST_PARTITION_H 1 | |
35 | ||
36 | #include <parallel/parallel.h> | |
37 | #include <vector> | |
38 | ||
39 | namespace __gnu_parallel | |
40 | { | |
41 | /** @brief Shrinks and doubles the ranges. | |
34475802 | 42 | * @param __os_starts Start positions worked on (oversampled). |
43 | * @param __count_to_two Counts up to 2. | |
44 | * @param __range_length Current length of a chunk. | |
73337dee | 45 | * @param __make_twice Whether the @c __os_starts is allowed to be |
6482a45c | 46 | * grown or not |
47 | */ | |
34475802 | 48 | template<typename _IIter> |
0be20f8a | 49 | void |
34475802 | 50 | __shrink_and_double(std::vector<_IIter>& __os_starts, |
757532bc | 51 | size_t& __count_to_two, size_t& __range_length, |
52 | const bool __make_twice) | |
0be20f8a | 53 | { |
34475802 | 54 | ++__count_to_two; |
757532bc | 55 | if (!__make_twice || __count_to_two < 2) |
84ec5566 | 56 | __shrink(__os_starts, __count_to_two, __range_length); |
0be20f8a | 57 | else |
84ec5566 | 58 | { |
59 | __os_starts.resize((__os_starts.size() - 1) * 2 + 1); | |
60 | __count_to_two = 0; | |
61 | } | |
0be20f8a | 62 | } |
6482a45c | 63 | |
64 | /** @brief Combines two ranges into one and thus halves the number of ranges. | |
34475802 | 65 | * @param __os_starts Start positions worked on (oversampled). |
66 | * @param __count_to_two Counts up to 2. | |
67 | * @param __range_length Current length of a chunk. */ | |
68 | template<typename _IIter> | |
0be20f8a | 69 | void |
34475802 | 70 | __shrink(std::vector<_IIter>& __os_starts, size_t& __count_to_two, |
757532bc | 71 | size_t& __range_length) |
0be20f8a | 72 | { |
34475802 | 73 | for (typename std::vector<_IIter>::size_type __i = 0; |
84ec5566 | 74 | __i <= (__os_starts.size() / 2); ++__i) |
75 | __os_starts[__i] = __os_starts[__i * 2]; | |
34475802 | 76 | __range_length *= 2; |
0be20f8a | 77 | } |
6482a45c | 78 | |
79 | /** @brief Splits a sequence given by input iterators into parts of | |
80 | * almost equal size | |
81 | * | |
82 | * The function needs only one pass over the sequence. | |
34475802 | 83 | * @param __begin Begin iterator of input sequence. |
84 | * @param __end End iterator of input sequence. | |
85 | * @param __starts Start iterators for the resulting parts, dimension | |
73337dee | 86 | * @c __num_parts+1. For convenience, @c __starts @c [__num_parts] |
6482a45c | 87 | * contains the end iterator of the sequence. |
34475802 | 88 | * @param __lengths Length of the resulting parts. |
89 | * @param __num_parts Number of parts to split the sequence into. | |
90 | * @param __f Functor to be applied to each element by traversing __it | |
91 | * @param __oversampling Oversampling factor. If 0, then the | |
73337dee | 92 | * partitions will differ in at most |
2d45356e | 93 | * \f$\sqrt{\mathrm{end} - \mathrm{begin}}\f$ |
94 | * elements. Otherwise, the ratio between the | |
73337dee | 95 | * longest and the shortest part is bounded by |
2d45356e | 96 | * \f$1/(\mathrm{oversampling} \cdot \mathrm{num\_parts})\f$ |
6482a45c | 97 | * @return Length of the whole sequence. |
98 | */ | |
34475802 | 99 | template<typename _IIter, typename _FunctorType> |
0be20f8a | 100 | size_t |
34475802 | 101 | list_partition(const _IIter __begin, const _IIter __end, |
84ec5566 | 102 | _IIter* __starts, size_t* __lengths, const int __num_parts, |
103 | _FunctorType& __f, int __oversampling = 0) | |
0be20f8a | 104 | { |
34475802 | 105 | bool __make_twice = false; |
0be20f8a | 106 | |
b2386313 | 107 | // The resizing algorithm is chosen according to the oversampling factor. |
34475802 | 108 | if (__oversampling == 0) |
84ec5566 | 109 | { |
110 | __make_twice = true; | |
111 | __oversampling = 1; | |
112 | } | |
0be20f8a | 113 | |
34475802 | 114 | std::vector<_IIter> __os_starts(2 * __oversampling * __num_parts + 1); |
0be20f8a | 115 | |
757532bc | 116 | __os_starts[0] = __begin; |
117 | _IIter __prev = __begin, __it = __begin; | |
34475802 | 118 | size_t __dist_limit = 0, __dist = 0; |
119 | size_t __cur = 1, __next = 1; | |
120 | size_t __range_length = 1; | |
121 | size_t __count_to_two = 0; | |
122 | while (__it != __end) | |
84ec5566 | 123 | { |
124 | __cur = __next; | |
125 | for (; __cur < __os_starts.size() and __it != __end; ++__cur) | |
126 | { | |
127 | for (__dist_limit += __range_length; | |
128 | __dist < __dist_limit and __it != __end; ++__dist) | |
129 | { | |
130 | __f(__it); | |
131 | ++__it; | |
132 | } | |
133 | __os_starts[__cur] = __it; | |
134 | } | |
135 | ||
136 | // Must compare for end and not __cur < __os_starts.size() , because | |
137 | // __cur could be == __os_starts.size() as well | |
138 | if (__it == __end) | |
139 | break; | |
140 | ||
141 | __shrink_and_double(__os_starts, __count_to_two, __range_length, | |
142 | __make_twice); | |
143 | __next = __os_starts.size() / 2 + 1; | |
144 | } | |
6482a45c | 145 | |
34475802 | 146 | // Calculation of the parts (one must be extracted from __current |
30238171 | 147 | // because the partition beginning at end, consists only of |
0be20f8a | 148 | // itself). |
34475802 | 149 | size_t __size_part = (__cur - 1) / __num_parts; |
150 | int __size_greater = static_cast<int>((__cur - 1) % __num_parts); | |
151 | __starts[0] = __os_starts[0]; | |
6482a45c | 152 | |
34475802 | 153 | size_t __index = 0; |
6482a45c | 154 | |
0be20f8a | 155 | // Smallest partitions. |
34475802 | 156 | for (int __i = 1; __i < (__num_parts + 1 - __size_greater); ++__i) |
84ec5566 | 157 | { |
158 | __lengths[__i - 1] = __size_part * __range_length; | |
159 | __index += __size_part; | |
160 | __starts[__i] = __os_starts[__index]; | |
161 | } | |
0be20f8a | 162 | |
163 | // Biggest partitions. | |
84ec5566 | 164 | for (int __i = __num_parts + 1 - __size_greater; __i <= __num_parts; |
165 | ++__i) | |
166 | { | |
167 | __lengths[__i - 1] = (__size_part+1) * __range_length; | |
168 | __index += (__size_part+1); | |
169 | __starts[__i] = __os_starts[__index]; | |
170 | } | |
0be20f8a | 171 | |
172 | // Correction of the end size (the end iteration has not finished). | |
34475802 | 173 | __lengths[__num_parts - 1] -= (__dist_limit - __dist); |
0be20f8a | 174 | |
34475802 | 175 | return __dist; |
0be20f8a | 176 | } |
6482a45c | 177 | } |
178 | ||
a8aa9db5 | 179 | #endif /* _GLIBCXX_PARALLEL_LIST_PARTITION_H */ |