libstdc++
list_partition.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
4 //
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 3, or (at your option) any later
9 // version.
10 
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.
15 
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/>.
24 
25 /** @file parallel/list_partition.h
26  * @brief Functionality to split sequence referenced by only input
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.
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
46  * grown or not
47  */
48  template<typename InputIterator>
49  void
51  size_t& count_to_two, size_t& range_length,
52  const bool make_twice)
53  {
54  ++count_to_two;
55  if (not make_twice or count_to_two < 2)
56  shrink(os_starts, count_to_two, range_length);
57  else
58  {
59  os_starts.resize((os_starts.size() - 1) * 2 + 1);
60  count_to_two = 0;
61  }
62  }
63 
64  /** @brief Combines two ranges into one and thus halves the number of ranges.
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 InputIterator>
69  void
70  shrink(std::vector<InputIterator>& os_starts, size_t& count_to_two,
71  size_t& range_length)
72  {
73  for (typename std::vector<InputIterator>::size_type i = 0;
74  i <= (os_starts.size() / 2); ++i)
75  os_starts[i] = os_starts[i * 2];
76  range_length *= 2;
77  }
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.
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]
87  * contains the end iterator of the sequence.
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$.
96  * @return Length of the whole sequence.
97  */
98  template<typename InputIterator, typename FunctorType>
99  size_t
100  list_partition(const InputIterator begin, const InputIterator end,
101  InputIterator* starts, size_t* lengths, const int num_parts,
102  FunctorType& f, int oversampling = 0)
103  {
104  bool make_twice = false;
105 
106  // The resizing algorithm is chosen according to the oversampling factor.
107  if (oversampling == 0)
108  {
109  make_twice = true;
110  oversampling = 1;
111  }
112 
113  std::vector<InputIterator> os_starts(2 * oversampling * num_parts + 1);
114 
115  os_starts[0]= begin;
116  InputIterator 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)
122  {
123  cur = next;
124  for (; cur < os_starts.size() and it != end; ++cur)
125  {
126  for (dist_limit += range_length;
127  dist < dist_limit and it != end; ++dist)
128  {
129  f(it);
130  ++it;
131  }
132  os_starts[cur] = it;
133  }
134 
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)
138  break;
139 
140  shrink_and_double(os_starts, count_to_two, range_length, make_twice);
141  next = os_starts.size() / 2 + 1;
142  }
143 
144  // Calculation of the parts (one must be extracted from current
145  // because the partition beginning at end, consists only of
146  // itself).
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];
150 
151  size_t index = 0;
152 
153  // Smallest partitions.
154  for (int i = 1; i < (num_parts + 1 - size_greater); ++i)
155  {
156  lengths[i - 1] = size_part * range_length;
157  index += size_part;
158  starts[i] = os_starts[index];
159  }
160 
161  // Biggest partitions.
162  for (int i = num_parts + 1 - size_greater; i <= num_parts; ++i)
163  {
164  lengths[i - 1] = (size_part+1) * range_length;
165  index += (size_part+1);
166  starts[i] = os_starts[index];
167  }
168 
169  // Correction of the end size (the end iteration has not finished).
170  lengths[num_parts - 1] -= (dist_limit - dist);
171 
172  return dist;
173  }
174 }
175 
176 #endif /* _GLIBCXX_PARALLEL_LIST_PARTITION_H */