Home | History | Annotate | Download | only in parallel
      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