libstdc++
list_partition.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007-2018 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 _IIter>
49  void
51  size_t& __count_to_two, size_t& __range_length,
52  const bool __make_twice)
53  {
54  ++__count_to_two;
55  if (!__make_twice || __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 _IIter>
69  void
70  __shrink(std::vector<_IIter>& __os_starts, size_t& __count_to_two,
71  size_t& __range_length)
72  {
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;
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
93  * \f$\sqrt{\mathrm{end} - \mathrm{begin}}\f$
94  * elements. Otherwise, the ratio between the
95  * longest and the shortest part is bounded by
96  * \f$1/(\mathrm{oversampling} \cdot \mathrm{num\_parts})\f$
97  * @return Length of the whole sequence.
98  */
99  template<typename _IIter, typename _FunctorType>
100  size_t
101  list_partition(const _IIter __begin, const _IIter __end,
102  _IIter* __starts, size_t* __lengths, const int __num_parts,
103  _FunctorType& __f, int __oversampling = 0)
104  {
105  bool __make_twice = false;
106 
107  // The resizing algorithm is chosen according to the oversampling factor.
108  if (__oversampling == 0)
109  {
110  __make_twice = true;
111  __oversampling = 1;
112  }
113 
114  std::vector<_IIter> __os_starts(2 * __oversampling * __num_parts + 1);
115 
116  __os_starts[0] = __begin;
117  _IIter __prev = __begin, __it = __begin;
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)
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  }
145 
146  // Calculation of the parts (one must be extracted from __current
147  // because the partition beginning at end, consists only of
148  // itself).
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];
152 
153  size_t __index = 0;
154 
155  // Smallest partitions.
156  for (int __i = 1; __i < (__num_parts + 1 - __size_greater); ++__i)
157  {
158  __lengths[__i - 1] = __size_part * __range_length;
159  __index += __size_part;
160  __starts[__i] = __os_starts[__index];
161  }
162 
163  // Biggest partitions.
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  }
171 
172  // Correction of the end size (the end iteration has not finished).
173  __lengths[__num_parts - 1] -= (__dist_limit - __dist);
174 
175  return __dist;
176  }
177 }
178 
179 #endif /* _GLIBCXX_PARALLEL_LIST_PARTITION_H */
A standard container which offers fixed time access to individual elements in any order.
Definition: stl_vector.h:339
End-user include file. Provides advanced settings and tuning options. This file is a GNU parallel ext...
size_t list_partition(const _IIter __begin, const _IIter __end, _IIter *__starts, size_t *__lengths, const int __num_parts, _FunctorType &__f, int __oversampling=0)
Splits a sequence given by input iterators into parts of almost equal size.
GNU parallel code for public use.
void __shrink(std::vector< _IIter > &__os_starts, size_t &__count_to_two, size_t &__range_length)
Combines two ranges into one and thus halves the number of ranges.
void resize(size_type __new_size)
Resizes the vector to the specified number of elements.
Definition: stl_vector.h:824
void __shrink_and_double(std::vector< _IIter > &__os_starts, size_t &__count_to_two, size_t &__range_length, const bool __make_twice)
Shrinks and doubles the ranges.
size_type size() const noexcept
Definition: stl_vector.h:805