3 // Copyright (C) 2007, 2008 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 2, or (at your option) any later
11 // This library is distributed in the hope that it will be useful, but
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.
16 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING. If not, write to
18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19 // MA 02111-1307, USA.
21 // As a special exception, you may use this file as part of a free
22 // software library without restriction. Specifically, if other files
23 // instantiate templates or use macros or inline functions from this
24 // file, or you compile this file and link it with other files to
25 // produce an executable, this file does not by itself cause the
26 // resulting executable to be covered by the GNU General Public
27 // License. This exception does not however invalidate any other
28 // reasons why the executable file might be covered by the GNU General
31 /** @file parallel/list_partition.h
32 * @brief Functionality to split sequence referenced by only input
34 * This file is a GNU parallel extension to the Standard C++ Library.
37 // Written by Leonor Frias Moya and Johannes Singler.
39 #ifndef _GLIBCXX_PARALLEL_LIST_PARTITION_H
40 #define _GLIBCXX_PARALLEL_LIST_PARTITION_H 1
42 #include <parallel/parallel.h>
45 namespace __gnu_parallel
47 /** @brief Shrinks and doubles the ranges.
48 * @param os_starts Start positions worked on (oversampled).
49 * @param count_to_two Counts up to 2.
50 * @param range_length Current length of a chunk.
51 * @param make_twice Whether the @c os_starts is allowed to be
54 template<typename InputIterator
>
56 shrink_and_double(std::vector
<InputIterator
>& os_starts
,
57 size_t& count_to_two
, size_t& range_length
,
58 const bool make_twice
)
61 if (not make_twice
or count_to_two
< 2)
62 shrink(os_starts
, count_to_two
, range_length
);
65 os_starts
.resize((os_starts
.size() - 1) * 2 + 1);
70 /** @brief Combines two ranges into one and thus halves the number of ranges.
71 * @param os_starts Start positions worked on (oversampled).
72 * @param count_to_two Counts up to 2.
73 * @param range_length Current length of a chunk. */
74 template<typename InputIterator
>
76 shrink(std::vector
<InputIterator
>& os_starts
, size_t& count_to_two
,
79 for (typename
std::vector
<InputIterator
>::size_type i
= 0;
80 i
<= (os_starts
.size() / 2); ++i
)
81 os_starts
[i
] = os_starts
[i
* 2];
85 /** @brief Splits a sequence given by input iterators into parts of
88 * The function needs only one pass over the sequence.
89 * @param begin Begin iterator of input sequence.
90 * @param end End iterator of input sequence.
91 * @param starts Start iterators for the resulting parts, dimension
92 * @c num_parts+1. For convenience, @c starts @c [num_parts]
93 * contains the end iterator of the sequence.
94 * @param lengths Length of the resulting parts.
95 * @param num_parts Number of parts to split the sequence into.
96 * @param f Functor to be applied to each element by traversing it
97 * @param oversampling Oversampling factor. If 0, then the
98 * partitions will differ in at most @f$ \sqrt{\mathrm{end} -
99 * \mathrm{begin}} @f$ elements. Otherwise, the ratio between the
100 * longest and the shortest part is bounded by @f$
101 * 1/(\mathrm{oversampling} \cdot \mathrm{num\_parts}) @f$.
102 * @return Length of the whole sequence.
104 template<typename InputIterator
, typename FunctorType
>
106 list_partition(const InputIterator begin
, const InputIterator end
,
107 InputIterator
* starts
, size_t* lengths
, const int num_parts
,
108 FunctorType
& f
, int oversampling
= 0)
110 bool make_twice
= false;
112 // The resizing algorithm is chosen according to the oversampling factor.
113 if (oversampling
== 0)
119 std::vector
<InputIterator
> os_starts(2 * oversampling
* num_parts
+ 1);
122 InputIterator prev
= begin
, it
= begin
;
123 size_t dist_limit
= 0, dist
= 0;
124 size_t cur
= 1, next
= 1;
125 size_t range_length
= 1;
126 size_t count_to_two
= 0;
130 for (; cur
< os_starts
.size() and it
!= end
; ++cur
)
132 for (dist_limit
+= range_length
;
133 dist
< dist_limit
and it
!= end
; ++dist
)
141 // Must compare for end and not cur < os_starts.size() , because
142 // cur could be == os_starts.size() as well
146 shrink_and_double(os_starts
, count_to_two
, range_length
, make_twice
);
147 next
= os_starts
.size() / 2 + 1;
150 // Calculation of the parts (one must be extracted from current
151 // because the partition beginning at end, consists only of
153 size_t size_part
= (cur
- 1) / num_parts
;
154 int size_greater
= static_cast<int>((cur
- 1) % num_parts
);
155 starts
[0] = os_starts
[0];
159 // Smallest partitions.
160 for (int i
= 1; i
< (num_parts
+ 1 - size_greater
); ++i
)
162 lengths
[i
- 1] = size_part
* range_length
;
164 starts
[i
] = os_starts
[index
];
167 // Biggest partitions.
168 for (int i
= num_parts
+ 1 - size_greater
; i
<= num_parts
; ++i
)
170 lengths
[i
- 1] = (size_part
+1) * range_length
;
171 index
+= (size_part
+1);
172 starts
[i
] = os_starts
[index
];
175 // Correction of the end size (the end iteration has not finished).
176 lengths
[num_parts
- 1] -= (dist_limit
- dist
);