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/for_each_selectors.h 00026 * @brief Functors representing different tasks to be plugged into the 00027 * generic parallelization methods for embarrassingly parallel functions. 00028 * This file is a GNU parallel extension to the Standard C++ Library. 00029 */ 00030 00031 // Written by Felix Putze. 00032 00033 #ifndef _GLIBCXX_PARALLEL_FOR_EACH_SELECTORS_H 00034 #define _GLIBCXX_PARALLEL_FOR_EACH_SELECTORS_H 1 00035 00036 #include <parallel/basic_iterator.h> 00037 00038 namespace __gnu_parallel 00039 { 00040 00041 /** @brief Generic selector for embarrassingly parallel functions. */ 00042 template<typename It> 00043 struct generic_for_each_selector 00044 { 00045 /** @brief Iterator on last element processed; needed for some 00046 * algorithms (e. g. std::transform()). 00047 */ 00048 It finish_iterator; 00049 }; 00050 00051 00052 /** @brief std::for_each() selector. */ 00053 template<typename It> 00054 struct for_each_selector : public generic_for_each_selector<It> 00055 { 00056 /** @brief Functor execution. 00057 * @param o Operator. 00058 * @param i Iterator referencing object. */ 00059 template<typename Op> 00060 bool 00061 operator()(Op& o, It i) 00062 { 00063 o(*i); 00064 return true; 00065 } 00066 }; 00067 00068 /** @brief std::generate() selector. */ 00069 template<typename It> 00070 struct generate_selector : public generic_for_each_selector<It> 00071 { 00072 /** @brief Functor execution. 00073 * @param o Operator. 00074 * @param i Iterator referencing object. */ 00075 template<typename Op> 00076 bool 00077 operator()(Op& o, It i) 00078 { 00079 *i = o(); 00080 return true; 00081 } 00082 }; 00083 00084 /** @brief std::fill() selector. */ 00085 template<typename It> 00086 struct fill_selector : public generic_for_each_selector<It> 00087 { 00088 /** @brief Functor execution. 00089 * @param v Current value. 00090 * @param i Iterator referencing object. */ 00091 template<typename Val> 00092 bool 00093 operator()(Val& v, It i) 00094 { 00095 *i = v; 00096 return true; 00097 } 00098 }; 00099 00100 /** @brief std::transform() selector, one input sequence variant. */ 00101 template<typename It> 00102 struct transform1_selector : public generic_for_each_selector<It> 00103 { 00104 /** @brief Functor execution. 00105 * @param o Operator. 00106 * @param i Iterator referencing object. */ 00107 template<typename Op> 00108 bool 00109 operator()(Op& o, It i) 00110 { 00111 *i.second = o(*i.first); 00112 return true; 00113 } 00114 }; 00115 00116 /** @brief std::transform() selector, two input sequences variant. */ 00117 template<typename It> 00118 struct transform2_selector : public generic_for_each_selector<It> 00119 { 00120 /** @brief Functor execution. 00121 * @param o Operator. 00122 * @param i Iterator referencing object. */ 00123 template<typename Op> 00124 bool 00125 operator()(Op& o, It i) 00126 { 00127 *i.third = o(*i.first, *i.second); 00128 return true; 00129 } 00130 }; 00131 00132 /** @brief std::replace() selector. */ 00133 template<typename It, typename T> 00134 struct replace_selector : public generic_for_each_selector<It> 00135 { 00136 /** @brief Value to replace with. */ 00137 const T& new_val; 00138 00139 /** @brief Constructor 00140 * @param new_val Value to replace with. */ 00141 explicit 00142 replace_selector(const T &new_val) : new_val(new_val) {} 00143 00144 /** @brief Functor execution. 00145 * @param v Current value. 00146 * @param i Iterator referencing object. */ 00147 bool 00148 operator()(T& v, It i) 00149 { 00150 if (*i == v) 00151 *i = new_val; 00152 return true; 00153 } 00154 }; 00155 00156 /** @brief std::replace() selector. */ 00157 template<typename It, typename Op, typename T> 00158 struct replace_if_selector : public generic_for_each_selector<It> 00159 { 00160 /** @brief Value to replace with. */ 00161 const T& new_val; 00162 00163 /** @brief Constructor. 00164 * @param new_val Value to replace with. */ 00165 explicit 00166 replace_if_selector(const T &new_val) : new_val(new_val) { } 00167 00168 /** @brief Functor execution. 00169 * @param o Operator. 00170 * @param i Iterator referencing object. */ 00171 bool 00172 operator()(Op& o, It i) 00173 { 00174 if (o(*i)) 00175 *i = new_val; 00176 return true; 00177 } 00178 }; 00179 00180 /** @brief std::count() selector. */ 00181 template<typename It, typename Diff> 00182 struct count_selector : public generic_for_each_selector<It> 00183 { 00184 /** @brief Functor execution. 00185 * @param v Current value. 00186 * @param i Iterator referencing object. 00187 * @return 1 if count, 0 if does not count. */ 00188 template<typename Val> 00189 Diff 00190 operator()(Val& v, It i) 00191 { return (v == *i) ? 1 : 0; } 00192 }; 00193 00194 /** @brief std::count_if () selector. */ 00195 template<typename It, typename Diff> 00196 struct count_if_selector : public generic_for_each_selector<It> 00197 { 00198 /** @brief Functor execution. 00199 * @param o Operator. 00200 * @param i Iterator referencing object. 00201 * @return 1 if count, 0 if does not count. */ 00202 template<typename Op> 00203 Diff 00204 operator()(Op& o, It i) 00205 { return (o(*i)) ? 1 : 0; } 00206 }; 00207 00208 /** @brief std::accumulate() selector. */ 00209 template<typename It> 00210 struct accumulate_selector : public generic_for_each_selector<It> 00211 { 00212 /** @brief Functor execution. 00213 * @param o Operator (unused). 00214 * @param i Iterator referencing object. 00215 * @return The current value. */ 00216 template<typename Op> 00217 typename std::iterator_traits<It>::value_type operator()(Op o, It i) 00218 { return *i; } 00219 }; 00220 00221 /** @brief std::inner_product() selector. */ 00222 template<typename It, typename It2, typename T> 00223 struct inner_product_selector : public generic_for_each_selector<It> 00224 { 00225 /** @brief Begin iterator of first sequence. */ 00226 It begin1_iterator; 00227 00228 /** @brief Begin iterator of second sequence. */ 00229 It2 begin2_iterator; 00230 00231 /** @brief Constructor. 00232 * @param b1 Begin iterator of first sequence. 00233 * @param b2 Begin iterator of second sequence. */ 00234 explicit 00235 inner_product_selector(It b1, It2 b2) 00236 : begin1_iterator(b1), begin2_iterator(b2) { } 00237 00238 /** @brief Functor execution. 00239 * @param mult Multiplication functor. 00240 * @param current Iterator referencing object. 00241 * @return Inner product elemental result. */ 00242 template<typename Op> 00243 T 00244 operator()(Op mult, It current) 00245 { 00246 typename std::iterator_traits<It>::difference_type position 00247 = current - begin1_iterator; 00248 return mult(*current, *(begin2_iterator + position)); 00249 } 00250 }; 00251 00252 /** @brief Selector that just returns the passed iterator. */ 00253 template<typename It> 00254 struct identity_selector : public generic_for_each_selector<It> 00255 { 00256 /** @brief Functor execution. 00257 * @param o Operator (unused). 00258 * @param i Iterator referencing object. 00259 * @return Passed iterator. */ 00260 template<typename Op> 00261 It 00262 operator()(Op o, It i) 00263 { return i; } 00264 }; 00265 00266 /** @brief Selector that returns the difference between two adjacent 00267 * elements. 00268 */ 00269 template<typename It> 00270 struct adjacent_difference_selector : public generic_for_each_selector<It> 00271 { 00272 template<typename Op> 00273 bool 00274 operator()(Op& o, It i) 00275 { 00276 typename It::first_type go_back_one = i.first; 00277 --go_back_one; 00278 *i.second = o(*i.first, *go_back_one); 00279 return true; 00280 } 00281 }; 00282 00283 // XXX move into type_traits? 00284 /** @brief Functor doing nothing 00285 * 00286 * For some reduction tasks (this is not a function object, but is 00287 * passed as selector dummy parameter. 00288 */ 00289 struct nothing 00290 { 00291 /** @brief Functor execution. 00292 * @param i Iterator referencing object. */ 00293 template<typename It> 00294 void 00295 operator()(It i) { } 00296 }; 00297 00298 /** @brief Reduction function doing nothing. */ 00299 struct dummy_reduct 00300 { 00301 bool 00302 operator()(bool /*x*/, bool /*y*/) const 00303 { return true; } 00304 }; 00305 00306 /** @brief Reduction for finding the maximum element, using a comparator. */ 00307 template<typename Comp, typename It> 00308 struct min_element_reduct 00309 { 00310 Comp& comp; 00311 00312 explicit 00313 min_element_reduct(Comp &c) : comp(c) { } 00314 00315 It 00316 operator()(It x, It y) 00317 { 00318 if (comp(*x, *y)) 00319 return x; 00320 else 00321 return y; 00322 } 00323 }; 00324 00325 /** @brief Reduction for finding the maximum element, using a comparator. */ 00326 template<typename Comp, typename It> 00327 struct max_element_reduct 00328 { 00329 Comp& comp; 00330 00331 explicit 00332 max_element_reduct(Comp& c) : comp(c) { } 00333 00334 It 00335 operator()(It x, It y) 00336 { 00337 if (comp(*x, *y)) 00338 return y; 00339 else 00340 return x; 00341 } 00342 }; 00343 00344 /** @brief General reduction, using a binary operator. */ 00345 template<typename BinOp> 00346 struct accumulate_binop_reduct 00347 { 00348 BinOp& binop; 00349 00350 explicit 00351 accumulate_binop_reduct(BinOp& b) : binop(b) { } 00352 00353 template<typename Result, typename Addend> 00354 Result 00355 operator()(const Result& x, const Addend& y) 00356 { return binop(x, y); } 00357 }; 00358 } 00359 00360 #endif /* _GLIBCXX_PARALLEL_FOR_EACH_SELECTORS_H */