libstdc++-v3/include/parallel/base.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/base.h
  26  *  @brief Sequential helper functions.
  27  *  This file is a GNU parallel extension to the Standard C++ Library.
  28  */
  29
  30 // Written by Johannes Singler.
  31
  32 #ifndef _GLIBCXX_PARALLEL_BASE_H
  33 #define _GLIBCXX_PARALLEL_BASE_H 1
  34
  35 #include <functional>
  36 #include <omp.h>
  37 #include <parallel/features.h>
  38 #include <parallel/basic_iterator.h>
  39 #include <parallel/parallel.h>
  40
  41
  42 // Parallel mode namespaces.
  43
  44 /**
  45  * @namespace std::__parallel
  46  * @brief GNU parallel code, replaces standard behavior with parallel behavior.
  47  */
  48 namespace std
  49 {
  50   namespace __parallel { }
  51 }
  52
  53 /**
  54  * @namespace __gnu_parallel
  55  * @brief GNU parallel code for public use.
  56  */
  57 namespace __gnu_parallel
  58 {
  59   // Import all the parallel versions of components in namespace std.
  60   using namespace std::__parallel;
  61 }
  62
  63 /**
  64  * @namespace __gnu_sequential
  65  * @brief GNU sequential classes for public use.
  66  */
  67 namespace __gnu_sequential
  68 {
  69   // Import whatever is the serial version.
  70 #ifdef _GLIBCXX_PARALLEL
  71   using namespace std::__norm;
  72 #else
  73   using namespace std;
  74 #endif
  75 }
  76
  77
  78 namespace __gnu_parallel
  79 {
  80   // NB: Including this file cannot produce (unresolved) symbols from
  81   // the OpenMP runtime unless the parallel mode is actually invoked
  82   // and active, which imples that the OpenMP runtime is actually
  83   // going to be linked in.
  84   inline int
  85   __get_max_threads()
  86   {
  87     int __i = omp_get_max_threads();
  88     return __i > 1 ? __i : 1;
  89   }
  90
  91
  92   inline bool
  93   __is_parallel(const _Parallelism __p) { return __p != sequential; }
  94
  95
  96 /** @brief Calculates the rounded-down logarithm of @__c __n for base 2.
  97   *  @param __n Argument.
  98   *  @return Returns 0 for any argument <1.
  99   */
 100 template<typename _Size>
 101   inline _Size
 102   __rd_log2(_Size __n)
 103     {
 104       _Size __k;
 105       for (__k = 0; __n > 1; __n >>= 1)
 106         ++__k;
 107       return __k;
 108     }
 109
 110 /** @brief Encode two integers into one gnu_parallel::_CASable.
 111   *  @param __a First integer, to be encoded in the most-significant @__c
 112   *  _CASable_bits/2 bits.
 113   *  @param __b Second integer, to be encoded in the least-significant
 114   *  @__c _CASable_bits/2 bits.
 115   *  @return value encoding @__c __a and @__c __b.
 116   *  @see decode2
 117   */
 118 inline _CASable
 119 __encode2(int __a, int __b)     //must all be non-negative, actually
 120 {
 121   return (((_CASable)__a) << (_CASable_bits / 2)) | (((_CASable)__b) << 0);
 122 }
 123
 124 /** @brief Decode two integers from one gnu_parallel::_CASable.
 125   *  @param __x __gnu_parallel::_CASable to decode integers from.
 126   *  @param __a First integer, to be decoded from the most-significant
 127   *  @__c _CASable_bits/2 bits of @__c __x.
 128   *  @param __b Second integer, to be encoded in the least-significant
 129   *  @__c _CASable_bits/2 bits of @__c __x.
 130   *  @see __encode2
 131   */
 132 inline void
 133 decode2(_CASable __x, int& __a, int& __b)
 134 {
 135   __a = (int)((__x >> (_CASable_bits / 2)) & _CASable_mask);
 136   __b = (int)((__x >>               0 ) & _CASable_mask);
 137 }
 138
 139 //needed for parallel "numeric", even if "algorithm" not included
 140
 141 /** @brief Equivalent to std::min. */
 142 template<typename _Tp>
 143   const _Tp&
 144   min(const _Tp& __a, const _Tp& __b)
 145   { return (__a < __b) ? __a : __b; }
 146
 147 /** @brief Equivalent to std::max. */
 148 template<typename _Tp>
 149   const _Tp&
 150   max(const _Tp& __a, const _Tp& __b)
 151   { return (__a > __b) ? __a : __b; }
 152
 153 /** @brief Constructs predicate for equality from strict weak
 154   *  ordering predicate
 155   */
 156 template<typename _T1, typename _T2, typename _Compare>
 157   class _EqualFromLess : public std::binary_function<_T1, _T2, bool>
 158   {
 159   private:
 160     _Compare& _M_comp;
 161
 162   public:
 163     _EqualFromLess(_Compare& __comp) : _M_comp(__comp) { }
 164
 165     bool operator()(const _T1& __a, const _T2& __b)
 166     {
 167       return !_M_comp(__a, __b) && !_M_comp(__b, __a);
 168     }
 169   };
 170
 171
 172 /** @brief Similar to std::binder1st,
 173   *  but giving the argument types explicitly. */
 174 template<typename _Predicate, typename argument_type>
 175   class __unary_negate
 176   : public std::unary_function<argument_type, bool>
 177   {
 178   protected:
 179     _Predicate _M_pred;
 180
 181   public:
 182     explicit
 183     __unary_negate(const _Predicate& __x) : _M_pred(__x) { }
 184
 185     bool
 186     operator()(const argument_type& __x)
 187     { return !_M_pred(__x); }
 188   };
 189
 190 /** @brief Similar to std::binder1st,
 191   *  but giving the argument types explicitly. */
 192 template<typename _Operation, typename _FirstArgumentType,
 193          typename _SecondArgumentType, typename _ResultType>
 194   class __binder1st
 195   : public std::unary_function<_SecondArgumentType, _ResultType>
 196   {
 197   protected:
 198     _Operation _M_op;
 199     _FirstArgumentType _M_value;
 200
 201   public:
 202     __binder1st(const _Operation& __x,
 203               const _FirstArgumentType& __y)
 204     : _M_op(__x), _M_value(__y) { }
 205
 206     _ResultType
 207     operator()(const _SecondArgumentType& __x)
 208     { return _M_op(_M_value, __x); }
 209
 210     // _GLIBCXX_RESOLVE_LIB_DEFECTS
 211     // 109.  Missing binders for non-const sequence elements
 212     _ResultType
 213     operator()(_SecondArgumentType& __x) const
 214     { return _M_op(_M_value, __x); }
 215   };
 216
 217 /**
 218   *  @brief Similar to std::binder2nd, but giving the argument types
 219   *  explicitly.
 220   */
 221 template<typename _Operation, typename _FirstArgumentType,
 222          typename _SecondArgumentType, typename _ResultType>
 223   class binder2nd
 224   : public std::unary_function<_FirstArgumentType, _ResultType>
 225   {
 226   protected:
 227     _Operation _M_op;
 228     _SecondArgumentType _M_value;
 229
 230   public:
 231     binder2nd(const _Operation& __x,
 232               const _SecondArgumentType& __y)
 233     : _M_op(__x), _M_value(__y) { }
 234
 235     _ResultType
 236     operator()(const _FirstArgumentType& __x) const
 237     { return _M_op(__x, _M_value); }
 238
 239     // _GLIBCXX_RESOLVE_LIB_DEFECTS
 240     // 109.  Missing binders for non-const sequence elements
 241     _ResultType
 242     operator()(_FirstArgumentType& __x)
 243     { return _M_op(__x, _M_value); }
 244   };
 245
 246 /** @brief Similar to std::equal_to, but allows two different types. */
 247 template<typename _T1, typename _T2>
 248   struct _EqualTo : std::binary_function<_T1, _T2, bool>
 249   {
 250     bool operator()(const _T1& __t1, const _T2& __t2) const
 251     { return __t1 == __t2; }
 252   };
 253
 254 /** @brief Similar to std::less, but allows two different types. */
 255 template<typename _T1, typename _T2>
 256   struct _Less : std::binary_function<_T1, _T2, bool>
 257   {
 258     bool
 259     operator()(const _T1& __t1, const _T2& __t2) const
 260     { return __t1 < __t2; }
 261
 262     bool
 263     operator()(const _T2& __t2, const _T1& __t1) const
 264     { return __t2 < __t1; }
 265   };
 266
 267 // Partial specialization for one type. Same as std::less.
 268 template<typename _Tp>
 269 struct _Less<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, bool>
 270   {
 271     bool
 272     operator()(const _Tp& __x, const _Tp& __y) const
 273     { return __x < __y; }
 274   };
 275
 276
 277   /** @brief Similar to std::plus, but allows two different types. */
 278 template<typename _Tp1, typename _Tp2>
 279   struct _Plus : public std::binary_function<_Tp1, _Tp2, _Tp1>
 280   {
 281     typedef __typeof__(*static_cast<_Tp1*>(NULL)
 282                        + *static_cast<_Tp2*>(NULL)) __result;
 283
 284     __result
 285     operator()(const _Tp1& __x, const _Tp2& __y) const
 286     { return __x + __y; }
 287   };
 288
 289 // Partial specialization for one type. Same as std::plus.
 290 template<typename _Tp>
 291   struct _Plus<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp>
 292   {
 293     typedef __typeof__(*static_cast<_Tp*>(NULL)
 294                        + *static_cast<_Tp*>(NULL)) __result;
 295
 296     __result
 297     operator()(const _Tp& __x, const _Tp& __y) const
 298     { return __x + __y; }
 299   };
 300
 301
 302 /** @brief Similar to std::multiplies, but allows two different types. */
 303 template<typename _Tp1, typename _Tp2>
 304   struct _Multiplies : public std::binary_function<_Tp1, _Tp2, _Tp1>
 305   {
 306     typedef __typeof__(*static_cast<_Tp1*>(NULL)
 307                        * *static_cast<_Tp2*>(NULL)) __result;
 308
 309     __result
 310     operator()(const _Tp1& __x, const _Tp2& __y) const
 311     { return __x * __y; }
 312   };
 313
 314 // Partial specialization for one type. Same as std::multiplies.
 315 template<typename _Tp>
 316   struct _Multiplies<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp>
 317   {
 318     typedef __typeof__(*static_cast<_Tp*>(NULL)
 319                        * *static_cast<_Tp*>(NULL)) __result;
 320
 321     __result
 322     operator()(const _Tp& __x, const _Tp& __y) const
 323     { return __x * __y; }
 324   };
 325
 326
 327 template<typename _Tp, typename _DifferenceTp>
 328   class _PseudoSequence;
 329
 330 /** @brief _Iterator associated with __gnu_parallel::_PseudoSequence.
 331   *  If features the usual random-access iterator functionality.
 332   *  @param _Tp Sequence _M_value type.
 333   *  @param _DifferenceType Sequence difference type.
 334   */
 335 template<typename _Tp, typename _DifferenceTp>
 336   class _PseudoSequenceIterator
 337   {
 338   public:
 339     typedef _DifferenceTp _DifferenceType;
 340
 341   private:
 342     const _Tp& _M_val;
 343     _DifferenceType _M_pos;
 344
 345   public:
 346     _PseudoSequenceIterator(const _Tp& _M_val, _DifferenceType _M_pos)
 347     : _M_val(_M_val), _M_pos(_M_pos) { }
 348
 349     // Pre-increment operator.
 350     _PseudoSequenceIterator&
 351     operator++()
 352     {
 353       ++_M_pos;
 354       return *this;
 355     }
 356
 357     // Post-increment operator.
 358     const _PseudoSequenceIterator
 359     operator++(int)
 360     { return _PseudoSequenceIterator(_M_pos++); }
 361
 362     const _Tp&
 363     operator*() const
 364     { return _M_val; }
 365
 366     const _Tp&
 367     operator[](_DifferenceType) const
 368     { return _M_val; }
 369
 370     bool
 371     operator==(const _PseudoSequenceIterator& __i2)
 372     { return _M_pos == __i2._M_pos; }
 373
 374     _DifferenceType
 375     operator!=(const _PseudoSequenceIterator& __i2)
 376     { return _M_pos != __i2._M_pos; }
 377
 378     _DifferenceType
 379     operator-(const _PseudoSequenceIterator& __i2)
 380     { return _M_pos - __i2._M_pos; }
 381   };
 382
 383 /** @brief Sequence that conceptually consists of multiple copies of
 384     the same element.
 385   *  The copies are not stored explicitly, of course.
 386   *  @param _Tp Sequence _M_value type.
 387   *  @param _DifferenceType Sequence difference type.
 388   */
 389 template<typename _Tp, typename _DifferenceTp>
 390   class _PseudoSequence
 391   {
 392   public:
 393     typedef _DifferenceTp _DifferenceType;
 394
 395     // Better cast down to uint64_t, than up to _DifferenceTp.
 396     typedef _PseudoSequenceIterator<_Tp, uint64_t> iterator;
 397
 398     /** @brief Constructor.
 399       *  @param _M_val Element of the sequence.
 400       *  @param __count Number of (virtual) copies.
 401       */
 402     _PseudoSequence(const _Tp& _M_val, _DifferenceType __count)
 403     : _M_val(_M_val), __count(__count)  { }
 404
 405     /** @brief Begin iterator. */
 406     iterator
 407     begin() const
 408     { return iterator(_M_val, 0); }
 409
 410     /** @brief End iterator. */
 411     iterator
 412     end() const
 413     { return iterator(_M_val, __count); }
 414
 415   private:
 416     const _Tp& _M_val;
 417     _DifferenceType __count;
 418   };
 419
 420 /** @brief Functor that does nothing */
 421 template<typename _ValueTp>
 422   class _VoidFunctor
 423   {
 424     inline void
 425     operator()(const _ValueTp& __v) const { }
 426   };
 427
 428 /** @brief Compute the median of three referenced elements,
 429     according to @__c __comp.
 430   *  @param __a First iterator.
 431   *  @param __b Second iterator.
 432   *  @param __c Third iterator.
 433   *  @param __comp Comparator.
 434   */
 435 template<typename _RAIter, typename _Compare>
 436   _RAIter
 437   __median_of_three_iterators(_RAIter __a, _RAIter __b,
 438                             _RAIter __c, _Compare& __comp)
 439   {
 440     if (__comp(*__a, *__b))
 441       if (__comp(*__b, *__c))
 442         return __b;
 443       else
 444         if (__comp(*__a, *__c))
 445           return __c;
 446         else
 447           return __a;
 448     else
 449       {
 450         // Just swap __a and __b.
 451         if (__comp(*__a, *__c))
 452           return __a;
 453         else
 454           if (__comp(*__b, *__c))
 455             return __c;
 456           else
 457             return __b;
 458       }
 459   }
 460
 461 #define _GLIBCXX_PARALLEL_ASSERT(_Condition) __glibcxx_assert(_Condition)
 462
 463 } //namespace __gnu_parallel
 464
 465 #endif /* _GLIBCXX_PARALLEL_BASE_H */