00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2007, 2008 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 2, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // You should have received a copy of the GNU General Public License 00017 // along with this library; see the file COPYING. If not, write to 00018 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 00019 // MA 02111-1307, USA. 00020 00021 // As a special exception, you may use this file as part of a free 00022 // software library without restriction. Specifically, if other files 00023 // instantiate templates or use macros or inline functions from this 00024 // file, or you compile this file and link it with other files to 00025 // produce an executable, this file does not by itself cause the 00026 // resulting executable to be covered by the GNU General Public 00027 // License. This exception does not however invalidate any other 00028 // reasons why the executable file might be covered by the GNU General 00029 // Public License. 00030 00031 /** @file parallel/list_partition.h 00032 * @brief Functionality to split sequence referenced by only input 00033 * iterators. 00034 * This file is a GNU parallel extension to the Standard C++ Library. 00035 */ 00036 00037 // Written by Leonor Frias Moya and Johannes Singler. 00038 00039 #ifndef _GLIBCXX_PARALLEL_LIST_PARTITION_H 00040 #define _GLIBCXX_PARALLEL_LIST_PARTITION_H 1 00041 00042 #include <parallel/parallel.h> 00043 #include <vector> 00044 00045 namespace __gnu_parallel 00046 { 00047 /** @brief Shrinks and doubles the ranges. 00048 * @param os_starts Start positions worked on (oversampled). 00049 * @param count_to_two Counts up to 2. 00050 * @param range_length Current length of a chunk. 00051 * @param make_twice Whether the @c os_starts is allowed to be 00052 * grown or not 00053 */ 00054 template<typename InputIterator> 00055 void 00056 shrink_and_double(std::vector<InputIterator>& os_starts, 00057 size_t& count_to_two, size_t& range_length, 00058 const bool make_twice) 00059 { 00060 ++count_to_two; 00061 if (not make_twice or count_to_two < 2) 00062 shrink(os_starts, count_to_two, range_length); 00063 else 00064 { 00065 os_starts.resize((os_starts.size() - 1) * 2 + 1); 00066 count_to_two = 0; 00067 } 00068 } 00069 00070 /** @brief Combines two ranges into one and thus halves the number of ranges. 00071 * @param os_starts Start positions worked on (oversampled). 00072 * @param count_to_two Counts up to 2. 00073 * @param range_length Current length of a chunk. */ 00074 template<typename InputIterator> 00075 void 00076 shrink(std::vector<InputIterator>& os_starts, size_t& count_to_two, 00077 size_t& range_length) 00078 { 00079 for (typename std::vector<InputIterator>::size_type i = 0; 00080 i <= (os_starts.size() / 2); ++i) 00081 os_starts[i] = os_starts[i * 2]; 00082 range_length *= 2; 00083 } 00084 00085 /** @brief Splits a sequence given by input iterators into parts of 00086 * almost equal size 00087 * 00088 * The function needs only one pass over the sequence. 00089 * @param begin Begin iterator of input sequence. 00090 * @param end End iterator of input sequence. 00091 * @param starts Start iterators for the resulting parts, dimension 00092 * @c num_parts+1. For convenience, @c starts @c [num_parts] 00093 * contains the end iterator of the sequence. 00094 * @param lengths Length of the resulting parts. 00095 * @param num_parts Number of parts to split the sequence into. 00096 * @param f Functor to be applied to each element by traversing it 00097 * @param oversampling Oversampling factor. If 0, then the 00098 * partitions will differ in at most @f$ \sqrt{\mathrm{end} - 00099 * \mathrm{begin}} @f$ elements. Otherwise, the ratio between the 00100 * longest and the shortest part is bounded by @f$ 00101 * 1/(\mathrm{oversampling} \cdot \mathrm{num\_parts}) @f$. 00102 * @return Length of the whole sequence. 00103 */ 00104 template<typename InputIterator, typename FunctorType> 00105 size_t 00106 list_partition(const InputIterator begin, const InputIterator end, 00107 InputIterator* starts, size_t* lengths, const int num_parts, 00108 FunctorType& f, int oversampling = 0) 00109 { 00110 bool make_twice = false; 00111 00112 // The resizing algorithm is chosen according to the oversampling factor. 00113 if (oversampling == 0) 00114 { 00115 make_twice = true; 00116 oversampling = 1; 00117 } 00118 00119 std::vector<InputIterator> os_starts(2 * oversampling * num_parts + 1); 00120 00121 os_starts[0]= begin; 00122 InputIterator prev = begin, it = begin; 00123 size_t dist_limit = 0, dist = 0; 00124 size_t cur = 1, next = 1; 00125 size_t range_length = 1; 00126 size_t count_to_two = 0; 00127 while (it != end) 00128 { 00129 cur = next; 00130 for (; cur < os_starts.size() and it != end; ++cur) 00131 { 00132 for (dist_limit += range_length; 00133 dist < dist_limit and it != end; ++dist) 00134 { 00135 f(it); 00136 ++it; 00137 } 00138 os_starts[cur] = it; 00139 } 00140 00141 // Must compare for end and not cur < os_starts.size() , because 00142 // cur could be == os_starts.size() as well 00143 if (it == end) 00144 break; 00145 00146 shrink_and_double(os_starts, count_to_two, range_length, make_twice); 00147 next = os_starts.size() / 2 + 1; 00148 } 00149 00150 // Calculation of the parts (one must be extracted from current 00151 // because the partition beginning at end, consists only of 00152 // itself). 00153 size_t size_part = (cur - 1) / num_parts; 00154 int size_greater = static_cast<int>((cur - 1) % num_parts); 00155 starts[0] = os_starts[0]; 00156 00157 size_t index = 0; 00158 00159 // Smallest partitions. 00160 for (int i = 1; i < (num_parts + 1 - size_greater); ++i) 00161 { 00162 lengths[i - 1] = size_part * range_length; 00163 index += size_part; 00164 starts[i] = os_starts[index]; 00165 } 00166 00167 // Biggest partitions. 00168 for (int i = num_parts + 1 - size_greater; i <= num_parts; ++i) 00169 { 00170 lengths[i - 1] = (size_part+1) * range_length; 00171 index += (size_part+1); 00172 starts[i] = os_starts[index]; 00173 } 00174 00175 // Correction of the end size (the end iteration has not finished). 00176 lengths[num_parts - 1] -= (dist_limit - dist); 00177 00178 return dist; 00179 } 00180 } 00181 00182 #endif