libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2007, 2008, 2009 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file parallel/list_partition.h 00026 * @brief _Functionality to split __sequence referenced by only input 00027 * iterators. 00028 * This file is a GNU parallel extension to the Standard C++ Library. 00029 */ 00030 00031 // Written by Leonor Frias Moya and Johannes Singler. 00032 00033 #ifndef _GLIBCXX_PARALLEL_LIST_PARTITION_H 00034 #define _GLIBCXX_PARALLEL_LIST_PARTITION_H 1 00035 00036 #include <parallel/parallel.h> 00037 #include <vector> 00038 00039 namespace __gnu_parallel 00040 { 00041 /** @brief Shrinks and doubles the ranges. 00042 * @param __os_starts Start positions worked on (oversampled). 00043 * @param __count_to_two Counts up to 2. 00044 * @param __range_length Current length of a chunk. 00045 * @param __make_twice Whether the @c __os_starts is allowed to be 00046 * grown or not 00047 */ 00048 template<typename _IIter> 00049 void 00050 __shrink_and_double(std::vector<_IIter>& __os_starts, 00051 size_t& __count_to_two, size_t& __range_length, 00052 const bool __make_twice) 00053 { 00054 ++__count_to_two; 00055 if (!__make_twice || __count_to_two < 2) 00056 __shrink(__os_starts, __count_to_two, __range_length); 00057 else 00058 { 00059 __os_starts.resize((__os_starts.size() - 1) * 2 + 1); 00060 __count_to_two = 0; 00061 } 00062 } 00063 00064 /** @brief Combines two ranges into one and thus halves the number of ranges. 00065 * @param __os_starts Start positions worked on (oversampled). 00066 * @param __count_to_two Counts up to 2. 00067 * @param __range_length Current length of a chunk. */ 00068 template<typename _IIter> 00069 void 00070 __shrink(std::vector<_IIter>& __os_starts, size_t& __count_to_two, 00071 size_t& __range_length) 00072 { 00073 for (typename std::vector<_IIter>::size_type __i = 0; 00074 __i <= (__os_starts.size() / 2); ++__i) 00075 __os_starts[__i] = __os_starts[__i * 2]; 00076 __range_length *= 2; 00077 } 00078 00079 /** @brief Splits a sequence given by input iterators into parts of 00080 * almost equal size 00081 * 00082 * The function needs only one pass over the sequence. 00083 * @param __begin Begin iterator of input sequence. 00084 * @param __end End iterator of input sequence. 00085 * @param __starts Start iterators for the resulting parts, dimension 00086 * @c __num_parts+1. For convenience, @c __starts @c [__num_parts] 00087 * contains the end iterator of the sequence. 00088 * @param __lengths Length of the resulting parts. 00089 * @param __num_parts Number of parts to split the sequence into. 00090 * @param __f Functor to be applied to each element by traversing __it 00091 * @param __oversampling Oversampling factor. If 0, then the 00092 * partitions will differ in at most 00093 * \sqrt{\mathrm{__end} - \mathrm{__begin}} 00094 * __elements. Otherwise, the ratio between the 00095 * longest and the shortest part is bounded by 00096 * 1/(\mathrm{__oversampling} \cdot \mathrm{num\_parts}) 00097 * @return Length of the whole sequence. 00098 */ 00099 template<typename _IIter, typename _FunctorType> 00100 size_t 00101 list_partition(const _IIter __begin, const _IIter __end, 00102 _IIter* __starts, size_t* __lengths, const int __num_parts, 00103 _FunctorType& __f, int __oversampling = 0) 00104 { 00105 bool __make_twice = false; 00106 00107 // The resizing algorithm is chosen according to the oversampling factor. 00108 if (__oversampling == 0) 00109 { 00110 __make_twice = true; 00111 __oversampling = 1; 00112 } 00113 00114 std::vector<_IIter> __os_starts(2 * __oversampling * __num_parts + 1); 00115 00116 __os_starts[0] = __begin; 00117 _IIter __prev = __begin, __it = __begin; 00118 size_t __dist_limit = 0, __dist = 0; 00119 size_t __cur = 1, __next = 1; 00120 size_t __range_length = 1; 00121 size_t __count_to_two = 0; 00122 while (__it != __end) 00123 { 00124 __cur = __next; 00125 for (; __cur < __os_starts.size() and __it != __end; ++__cur) 00126 { 00127 for (__dist_limit += __range_length; 00128 __dist < __dist_limit and __it != __end; ++__dist) 00129 { 00130 __f(__it); 00131 ++__it; 00132 } 00133 __os_starts[__cur] = __it; 00134 } 00135 00136 // Must compare for end and not __cur < __os_starts.size() , because 00137 // __cur could be == __os_starts.size() as well 00138 if (__it == __end) 00139 break; 00140 00141 __shrink_and_double(__os_starts, __count_to_two, __range_length, 00142 __make_twice); 00143 __next = __os_starts.size() / 2 + 1; 00144 } 00145 00146 // Calculation of the parts (one must be extracted from __current 00147 // because the partition beginning at end, consists only of 00148 // itself). 00149 size_t __size_part = (__cur - 1) / __num_parts; 00150 int __size_greater = static_cast<int>((__cur - 1) % __num_parts); 00151 __starts[0] = __os_starts[0]; 00152 00153 size_t __index = 0; 00154 00155 // Smallest partitions. 00156 for (int __i = 1; __i < (__num_parts + 1 - __size_greater); ++__i) 00157 { 00158 __lengths[__i - 1] = __size_part * __range_length; 00159 __index += __size_part; 00160 __starts[__i] = __os_starts[__index]; 00161 } 00162 00163 // Biggest partitions. 00164 for (int __i = __num_parts + 1 - __size_greater; __i <= __num_parts; 00165 ++__i) 00166 { 00167 __lengths[__i - 1] = (__size_part+1) * __range_length; 00168 __index += (__size_part+1); 00169 __starts[__i] = __os_starts[__index]; 00170 } 00171 00172 // Correction of the end size (the end iteration has not finished). 00173 __lengths[__num_parts - 1] -= (__dist_limit - __dist); 00174 00175 return __dist; 00176 } 00177 } 00178 00179 #endif /* _GLIBCXX_PARALLEL_LIST_PARTITION_H */