]>
Commit | Line | Data |
---|---|---|
c2ba9709 JS |
1 | // -*- C++ -*- |
2 | ||
748086b7 | 3 | // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. |
c2ba9709 JS |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
1acba85b | 6 | // software; you can redistribute __it and/or modify __it under the terms |
c2ba9709 | 7 | // of the GNU General Public License as published by the Free Software |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
c2ba9709 JS |
9 | // version. |
10 | ||
1acba85b | 11 | // This library is distributed in the hope that __it will be useful, but |
c2ba9709 JS |
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 | ||
748086b7 JJ |
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/>. | |
c2ba9709 JS |
24 | |
25 | /** @file parallel/list_partition.h | |
1acba85b | 26 | * @brief _Functionality to split __sequence referenced by only input |
c2ba9709 JS |
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. | |
1acba85b JS |
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. | |
45 | * @param __make_twice Whether the @__c __os_starts is allowed to be | |
c2ba9709 JS |
46 | * grown or not |
47 | */ | |
1acba85b | 48 | template<typename _IIter> |
531898c3 | 49 | void |
1acba85b JS |
50 | __shrink_and_double(std::vector<_IIter>& __os_starts, |
51 | size_t& __count_to_two, size_t& __range_length, | |
52 | const bool __make_twice) | |
531898c3 | 53 | { |
1acba85b JS |
54 | ++__count_to_two; |
55 | if (not __make_twice or __count_to_two < 2) | |
56 | __shrink(__os_starts, __count_to_two, __range_length); | |
531898c3 PC |
57 | else |
58 | { | |
1acba85b JS |
59 | __os_starts.resize((__os_starts.size() - 1) * 2 + 1); |
60 | __count_to_two = 0; | |
531898c3 PC |
61 | } |
62 | } | |
c2ba9709 JS |
63 | |
64 | /** @brief Combines two ranges into one and thus halves the number of ranges. | |
1acba85b JS |
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> | |
531898c3 | 69 | void |
1acba85b JS |
70 | __shrink(std::vector<_IIter>& __os_starts, size_t& __count_to_two, |
71 | size_t& __range_length) | |
531898c3 | 72 | { |
1acba85b JS |
73 | for (typename std::vector<_IIter>::size_type __i = 0; |
74 | __i <= (__os_starts.size() / 2); ++__i) | |
75 | __os_starts[__i] = __os_starts[__i * 2]; | |
76 | __range_length *= 2; | |
531898c3 | 77 | } |
c2ba9709 JS |
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. | |
1acba85b JS |
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 | |
86 | * @__c __num_parts+1. For convenience, @__c __starts @__c [__num_parts] | |
c2ba9709 | 87 | * contains the end iterator of the sequence. |
1acba85b JS |
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 | |
92 | * partitions will differ in at most @__f$ \sqrt{\mathrm{__end} - | |
93 | * \mathrm{__begin}} @__f$ __elements. Otherwise, the ratio between the | |
94 | * longest and the shortest part is bounded by @__f$ | |
95 | * 1/(\mathrm{__oversampling} \cdot \mathrm{num\_parts}) @__f$. | |
c2ba9709 JS |
96 | * @return Length of the whole sequence. |
97 | */ | |
1acba85b | 98 | template<typename _IIter, typename _FunctorType> |
531898c3 | 99 | size_t |
1acba85b JS |
100 | list_partition(const _IIter __begin, const _IIter __end, |
101 | _IIter* __starts, size_t* __lengths, const int __num_parts, | |
102 | _FunctorType& __f, int __oversampling = 0) | |
531898c3 | 103 | { |
1acba85b | 104 | bool __make_twice = false; |
531898c3 | 105 | |
a4797b34 | 106 | // The resizing algorithm is chosen according to the oversampling factor. |
1acba85b | 107 | if (__oversampling == 0) |
531898c3 | 108 | { |
1acba85b JS |
109 | __make_twice = true; |
110 | __oversampling = 1; | |
531898c3 PC |
111 | } |
112 | ||
1acba85b | 113 | std::vector<_IIter> __os_starts(2 * __oversampling * __num_parts + 1); |
531898c3 | 114 | |
1acba85b JS |
115 | __os_starts[0]= __begin; |
116 | _IIter __prev = __begin, __it = __begin; | |
117 | size_t __dist_limit = 0, __dist = 0; | |
118 | size_t __cur = 1, __next = 1; | |
119 | size_t __range_length = 1; | |
120 | size_t __count_to_two = 0; | |
121 | while (__it != __end) | |
c2ba9709 | 122 | { |
1acba85b JS |
123 | __cur = __next; |
124 | for (; __cur < __os_starts.size() and __it != __end; ++__cur) | |
c2ba9709 | 125 | { |
1acba85b JS |
126 | for (__dist_limit += __range_length; |
127 | __dist < __dist_limit and __it != __end; ++__dist) | |
531898c3 | 128 | { |
1acba85b JS |
129 | __f(__it); |
130 | ++__it; | |
531898c3 | 131 | } |
1acba85b | 132 | __os_starts[__cur] = __it; |
c2ba9709 | 133 | } |
531898c3 | 134 | |
1acba85b JS |
135 | // Must compare for end and not __cur < __os_starts.size() , because |
136 | // __cur could be == __os_starts.size() as well | |
137 | if (__it == __end) | |
531898c3 PC |
138 | break; |
139 | ||
1acba85b JS |
140 | __shrink_and_double(__os_starts, __count_to_two, __range_length, __make_twice); |
141 | __next = __os_starts.size() / 2 + 1; | |
c2ba9709 JS |
142 | } |
143 | ||
1acba85b JS |
144 | // Calculation of the parts (one must be extracted from __current |
145 | // because the partition beginning at __end, consists only of | |
531898c3 | 146 | // itself). |
1acba85b JS |
147 | size_t __size_part = (__cur - 1) / __num_parts; |
148 | int __size_greater = static_cast<int>((__cur - 1) % __num_parts); | |
149 | __starts[0] = __os_starts[0]; | |
c2ba9709 | 150 | |
1acba85b | 151 | size_t __index = 0; |
c2ba9709 | 152 | |
531898c3 | 153 | // Smallest partitions. |
1acba85b | 154 | for (int __i = 1; __i < (__num_parts + 1 - __size_greater); ++__i) |
531898c3 | 155 | { |
1acba85b JS |
156 | __lengths[__i - 1] = __size_part * __range_length; |
157 | __index += __size_part; | |
158 | __starts[__i] = __os_starts[__index]; | |
531898c3 PC |
159 | } |
160 | ||
161 | // Biggest partitions. | |
1acba85b | 162 | for (int __i = __num_parts + 1 - __size_greater; __i <= __num_parts; ++__i) |
531898c3 | 163 | { |
1acba85b JS |
164 | __lengths[__i - 1] = (__size_part+1) * __range_length; |
165 | __index += (__size_part+1); | |
166 | __starts[__i] = __os_starts[__index]; | |
531898c3 PC |
167 | } |
168 | ||
169 | // Correction of the end size (the end iteration has not finished). | |
1acba85b | 170 | __lengths[__num_parts - 1] -= (__dist_limit - __dist); |
531898c3 | 171 | |
1acba85b | 172 | return __dist; |
531898c3 | 173 | } |
c2ba9709 JS |
174 | } |
175 | ||
cbcd1e45 | 176 | #endif /* _GLIBCXX_PARALLEL_LIST_PARTITION_H */ |