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 50 shrink_and_double(std::vector<InputIterator>& os_starts, 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 */ 177
