contrib/gcc-4.4/libstdc++-v3/include/parallel/for_each_selectors.h

   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 */