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/for_each_selectors.h 26 * @brief Functors representing different tasks to be plugged into the 27 * generic parallelization methods for embarrassingly parallel functions. 28 * This file is a GNU parallel extension to the Standard C++ Library. 29 */ 30 31 // Written by Felix Putze. 32 33 #ifndef _GLIBCXX_PARALLEL_FOR_EACH_SELECTORS_H 34 #define _GLIBCXX_PARALLEL_FOR_EACH_SELECTORS_H 1 35 36 #include <parallel/basic_iterator.h> 37 38 namespace __gnu_parallel 39 { 40 41 /** @brief Generic selector for embarrassingly parallel functions. */ 42 template<typename It> 43 struct generic_for_each_selector 44 { 45 /** @brief Iterator on last element processed; needed for some 46 * algorithms (e. g. std::transform()). 47 */ 48 It finish_iterator; 49 }; 50 51 52 /** @brief std::for_each() selector. */ 53 template<typename It> 54 struct for_each_selector : public generic_for_each_selector<It> 55 { 56 /** @brief Functor execution. 57 * @param o Operator. 58 * @param i Iterator referencing object. */ 59 template<typename Op> 60 bool 61 operator()(Op& o, It i) 62 { 63 o(*i); 64 return true; 65 } 66 }; 67 68 /** @brief std::generate() selector. */ 69 template<typename It> 70 struct generate_selector : public generic_for_each_selector<It> 71 { 72 /** @brief Functor execution. 73 * @param o Operator. 74 * @param i Iterator referencing object. */ 75 template<typename Op> 76 bool 77 operator()(Op& o, It i) 78 { 79 *i = o(); 80 return true; 81 } 82 }; 83 84 /** @brief std::fill() selector. */ 85 template<typename It> 86 struct fill_selector : public generic_for_each_selector<It> 87 { 88 /** @brief Functor execution. 89 * @param v Current value. 90 * @param i Iterator referencing object. */ 91 template<typename Val> 92 bool 93 operator()(Val& v, It i) 94 { 95 *i = v; 96 return true; 97 } 98 }; 99 100 /** @brief std::transform() selector, one input sequence variant. */ 101 template<typename It> 102 struct transform1_selector : public generic_for_each_selector<It> 103 { 104 /** @brief Functor execution. 105 * @param o Operator. 106 * @param i Iterator referencing object. */ 107 template<typename Op> 108 bool 109 operator()(Op& o, It i) 110 { 111 *i.second = o(*i.first); 112 return true; 113 } 114 }; 115 116 /** @brief std::transform() selector, two input sequences variant. */ 117 template<typename It> 118 struct transform2_selector : public generic_for_each_selector<It> 119 { 120 /** @brief Functor execution. 121 * @param o Operator. 122 * @param i Iterator referencing object. */ 123 template<typename Op> 124 bool 125 operator()(Op& o, It i) 126 { 127 *i.third = o(*i.first, *i.second); 128 return true; 129 } 130 }; 131 132 /** @brief std::replace() selector. */ 133 template<typename It, typename T> 134 struct replace_selector : public generic_for_each_selector<It> 135 { 136 /** @brief Value to replace with. */ 137 const T& new_val; 138 139 /** @brief Constructor 140 * @param new_val Value to replace with. */ 141 explicit 142 replace_selector(const T &new_val) : new_val(new_val) {} 143 144 /** @brief Functor execution. 145 * @param v Current value. 146 * @param i Iterator referencing object. */ 147 bool 148 operator()(T& v, It i) 149 { 150 if (*i == v) 151 *i = new_val; 152 return true; 153 } 154 }; 155 156 /** @brief std::replace() selector. */ 157 template<typename It, typename Op, typename T> 158 struct replace_if_selector : public generic_for_each_selector<It> 159 { 160 /** @brief Value to replace with. */ 161 const T& new_val; 162 163 /** @brief Constructor. 164 * @param new_val Value to replace with. */ 165 explicit 166 replace_if_selector(const T &new_val) : new_val(new_val) { } 167 168 /** @brief Functor execution. 169 * @param o Operator. 170 * @param i Iterator referencing object. */ 171 bool 172 operator()(Op& o, It i) 173 { 174 if (o(*i)) 175 *i = new_val; 176 return true; 177 } 178 }; 179 180 /** @brief std::count() selector. */ 181 template<typename It, typename Diff> 182 struct count_selector : public generic_for_each_selector<It> 183 { 184 /** @brief Functor execution. 185 * @param v Current value. 186 * @param i Iterator referencing object. 187 * @return 1 if count, 0 if does not count. */ 188 template<typename Val> 189 Diff 190 operator()(Val& v, It i) 191 { return (v == *i) ? 1 : 0; } 192 }; 193 194 /** @brief std::count_if () selector. */ 195 template<typename It, typename Diff> 196 struct count_if_selector : public generic_for_each_selector<It> 197 { 198 /** @brief Functor execution. 199 * @param o Operator. 200 * @param i Iterator referencing object. 201 * @return 1 if count, 0 if does not count. */ 202 template<typename Op> 203 Diff 204 operator()(Op& o, It i) 205 { return (o(*i)) ? 1 : 0; } 206 }; 207 208 /** @brief std::accumulate() selector. */ 209 template<typename It> 210 struct accumulate_selector : public generic_for_each_selector<It> 211 { 212 /** @brief Functor execution. 213 * @param o Operator (unused). 214 * @param i Iterator referencing object. 215 * @return The current value. */ 216 template<typename Op> 217 typename std::iterator_traits<It>::value_type operator()(Op o, It i) 218 { return *i; } 219 }; 220 221 /** @brief std::inner_product() selector. */ 222 template<typename It, typename It2, typename T> 223 struct inner_product_selector : public generic_for_each_selector<It> 224 { 225 /** @brief Begin iterator of first sequence. */ 226 It begin1_iterator; 227 228 /** @brief Begin iterator of second sequence. */ 229 It2 begin2_iterator; 230 231 /** @brief Constructor. 232 * @param b1 Begin iterator of first sequence. 233 * @param b2 Begin iterator of second sequence. */ 234 explicit 235 inner_product_selector(It b1, It2 b2) 236 : begin1_iterator(b1), begin2_iterator(b2) { } 237 238 /** @brief Functor execution. 239 * @param mult Multiplication functor. 240 * @param current Iterator referencing object. 241 * @return Inner product elemental result. */ 242 template<typename Op> 243 T 244 operator()(Op mult, It current) 245 { 246 typename std::iterator_traits<It>::difference_type position 247 = current - begin1_iterator; 248 return mult(*current, *(begin2_iterator + position)); 249 } 250 }; 251 252 /** @brief Selector that just returns the passed iterator. */ 253 template<typename It> 254 struct identity_selector : public generic_for_each_selector<It> 255 { 256 /** @brief Functor execution. 257 * @param o Operator (unused). 258 * @param i Iterator referencing object. 259 * @return Passed iterator. */ 260 template<typename Op> 261 It 262 operator()(Op o, It i) 263 { return i; } 264 }; 265 266 /** @brief Selector that returns the difference between two adjacent 267 * elements. 268 */ 269 template<typename It> 270 struct adjacent_difference_selector : public generic_for_each_selector<It> 271 { 272 template<typename Op> 273 bool 274 operator()(Op& o, It i) 275 { 276 typename It::first_type go_back_one = i.first; 277 --go_back_one; 278 *i.second = o(*i.first, *go_back_one); 279 return true; 280 } 281 }; 282 283 // XXX move into type_traits? 284 /** @brief Functor doing nothing 285 * 286 * For some reduction tasks (this is not a function object, but is 287 * passed as selector dummy parameter. 288 */ 289 struct nothing 290 { 291 /** @brief Functor execution. 292 * @param i Iterator referencing object. */ 293 template<typename It> 294 void 295 operator()(It i) { } 296 }; 297 298 /** @brief Reduction function doing nothing. */ 299 struct dummy_reduct 300 { 301 bool 302 operator()(bool /*x*/, bool /*y*/) const 303 { return true; } 304 }; 305 306 /** @brief Reduction for finding the maximum element, using a comparator. */ 307 template<typename Comp, typename It> 308 struct min_element_reduct 309 { 310 Comp& comp; 311 312 explicit 313 min_element_reduct(Comp &c) : comp(c) { } 314 315 It 316 operator()(It x, It y) 317 { 318 if (comp(*x, *y)) 319 return x; 320 else 321 return y; 322 } 323 }; 324 325 /** @brief Reduction for finding the maximum element, using a comparator. */ 326 template<typename Comp, typename It> 327 struct max_element_reduct 328 { 329 Comp& comp; 330 331 explicit 332 max_element_reduct(Comp& c) : comp(c) { } 333 334 It 335 operator()(It x, It y) 336 { 337 if (comp(*x, *y)) 338 return y; 339 else 340 return x; 341 } 342 }; 343 344 /** @brief General reduction, using a binary operator. */ 345 template<typename BinOp> 346 struct accumulate_binop_reduct 347 { 348 BinOp& binop; 349 350 explicit 351 accumulate_binop_reduct(BinOp& b) : binop(b) { } 352 353 template<typename Result, typename Addend> 354 Result 355 operator()(const Result& x, const Addend& y) 356 { return binop(x, y); } 357 }; 358 } 359 360 #endif /* _GLIBCXX_PARALLEL_FOR_EACH_SELECTORS_H */ 361
