1// -*- C++ -*-
2
3// Copyright (C) 2007-2015 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
39namespace __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
50    __shrink_and_double(std::vector<_IIter>& __os_starts,
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 */
180