libstdc++-v3/include/parallel/for_each_selectors.h

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