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   // XXX remove std::duplicates from here if possible,
  97   // XXX but keep minimal dependencies.
  98
  99 /** @brief Calculates the rounded-down logarithm of @__c __n for base 2.
 100   *  @param __n Argument.
 101   *  @return Returns 0 for any argument <1.
 102   */
 103 template<typename _Size>
 104   inline _Size
 105   __log2(_Size __n)
 106     {
 107       _Size __k;
 108       for (__k = 0; __n > 1; __n >>= 1)
 109         ++__k;
 110       return __k;
 111     }
 112
 113 /** @brief Encode two integers into one gnu_parallel::_CASable.
 114   *  @param __a First integer, to be encoded in the most-significant @__c
 115   *  _CASable_bits/2 bits.
 116   *  @param __b Second integer, to be encoded in the least-significant
 117   *  @__c _CASable_bits/2 bits.
 118   *  @return __gnu_parallel::_CASable _M_value encoding @__c __a and @__c __b.
 119   *  @see decode2
 120   */
 121 inline _CASable
 122 __encode2(int __a, int __b)     //must all be non-negative, actually
 123 {
 124   return (((_CASable)__a) << (_CASable_bits / 2)) | (((_CASable)__b) << 0);
 125 }
 126
 127 /** @brief Decode two integers from one gnu_parallel::_CASable.
 128   *  @param __x __gnu_parallel::_CASable to decode integers from.
 129   *  @param __a First integer, to be decoded from the most-significant
 130   *  @__c _CASable_bits/2 bits of @__c __x.
 131   *  @param __b Second integer, to be encoded in the least-significant
 132   *  @__c _CASable_bits/2 bits of @__c __x.
 133   *  @see __encode2
 134   */
 135 inline void
 136 decode2(_CASable __x, int& __a, int& __b)
 137 {
 138   __a = (int)((__x >> (_CASable_bits / 2)) & _CASable_mask);
 139   __b = (int)((__x >>               0 ) & _CASable_mask);
 140 }
 141
 142 /** @brief Equivalent to std::min. */
 143 template<typename _Tp>
 144   const _Tp&
 145   min(const _Tp& __a, const _Tp& __b)
 146   { return (__a < __b) ? __a : __b; }
 147
 148 /** @brief Equivalent to std::max. */
 149 template<typename _Tp>
 150   const _Tp&
 151   max(const _Tp& __a, const _Tp& __b)
 152   { return (__a > __b) ? __a : __b; }
 153
 154 /** @brief Constructs predicate for equality from strict weak
 155   *  ordering predicate
 156   */
 157 // XXX comparator at the end, as per others
 158 template<typename _Compare, typename _T1, typename _T2>
 159   class _EqualFromLess : public std::binary_function<_T1, _T2, bool>
 160   {
 161   private:
 162     _Compare& _M_comp;
 163
 164   public:
 165     _EqualFromLess(_Compare& __comp) : _M_comp(__comp) { }
 166
 167     bool operator()(const _T1& __a, const _T2& __b)
 168     {
 169       return !_M_comp(__a, __b) && !_M_comp(__b, __a);
 170     }
 171   };
 172
 173
 174 /** @brief Similar to std::__binder1st,
 175   *  but giving the argument types explicitly. */
 176 template<typename _Predicate, typename argument_type>
 177   class __unary_negate
 178   : public std::unary_function<argument_type, bool>
 179   {
 180   protected:
 181     _Predicate _M_pred;
 182
 183   public:
 184     explicit
 185     __unary_negate(const _Predicate& __x) : _M_pred(__x) { }
 186
 187     bool
 188     operator()(const argument_type& __x)
 189     { return !_M_pred(__x); }
 190   };
 191
 192 /** @brief Similar to std::__binder1st,
 193   *  but giving the argument types explicitly. */
 194 template<typename _Operation, typename _FirstArgumentType,
 195          typename _SecondArgumentType, typename _ResultType>
 196   class __binder1st
 197   : public std::unary_function<_SecondArgumentType, _ResultType>
 198   {
 199   protected:
 200     _Operation _M_op;
 201     _FirstArgumentType _M_value;
 202
 203   public:
 204     __binder1st(const _Operation& __x,
 205               const _FirstArgumentType& __y)
 206     : _M_op(__x), _M_value(__y) { }
 207
 208     _ResultType
 209     operator()(const _SecondArgumentType& __x)
 210     { return _M_op(_M_value, __x); }
 211
 212     // _GLIBCXX_RESOLVE_LIB_DEFECTS
 213     // 109.  Missing binders for non-const sequence elements
 214     _ResultType
 215     operator()(_SecondArgumentType& __x) const
 216     { return _M_op(_M_value, __x); }
 217   };
 218
 219 /**
 220   *  @brief Similar to std::binder2nd, but giving the argument types
 221   *  explicitly.
 222   */
 223 template<typename _Operation, typename _FirstArgumentType,
 224          typename _SecondArgumentType, typename _ResultType>
 225   class binder2nd
 226   : public std::unary_function<_FirstArgumentType, _ResultType>
 227   {
 228   protected:
 229     _Operation _M_op;
 230     _SecondArgumentType _M_value;
 231
 232   public:
 233     binder2nd(const _Operation& __x,
 234               const _SecondArgumentType& __y)
 235     : _M_op(__x), _M_value(__y) { }
 236
 237     _ResultType
 238     operator()(const _FirstArgumentType& __x) const
 239     { return _M_op(__x, _M_value); }
 240
 241     // _GLIBCXX_RESOLVE_LIB_DEFECTS
 242     // 109.  Missing binders for non-const sequence elements
 243     _ResultType
 244     operator()(_FirstArgumentType& __x)
 245     { return _M_op(__x, _M_value); }
 246   };
 247
 248 /** @brief Similar to std::equal_to, but allows two different types. */
 249 template<typename _T1, typename _T2>
 250   struct equal_to : std::binary_function<_T1, _T2, bool>
 251   {
 252     bool operator()(const _T1& __t1, const _T2& __t2) const
 253     { return __t1 == __t2; }
 254   };
 255
 256 /** @brief Similar to std::less, but allows two different types. */
 257 template<typename _T1, typename _T2>
 258   struct _Less : std::binary_function<_T1, _T2, bool>
 259   {
 260     bool
 261     operator()(const _T1& __t1, const _T2& __t2) const
 262     { return __t1 < __t2; }
 263
 264     bool
 265     operator()(const _T2& __t2, const _T1& __t1) const
 266     { return __t2 < __t1; }
 267   };
 268
 269 // Partial specialization for one type. Same as std::less.
 270 template<typename _Tp>
 271 struct _Less<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, bool>
 272   {
 273     bool
 274     operator()(const _Tp& __x, const _Tp& __y) const
 275     { return __x < __y; }
 276   };
 277
 278
 279   /** @brief Similar to std::plus, but allows two different types. */
 280 template<typename _Tp1, typename _Tp2>
 281   struct _Plus : public std::binary_function<_Tp1, _Tp2, _Tp1>
 282   {
 283     typedef __typeof__(*static_cast<_Tp1*>(NULL)
 284                        + *static_cast<_Tp2*>(NULL)) __result;
 285
 286     __result
 287     operator()(const _Tp1& __x, const _Tp2& __y) const
 288     { return __x + __y; }
 289   };
 290
 291 // Partial specialization for one type. Same as std::plus.
 292 template<typename _Tp>
 293   struct _Plus<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp>
 294   {
 295     typedef __typeof__(*static_cast<_Tp*>(NULL)
 296                        + *static_cast<_Tp*>(NULL)) __result;
 297
 298     __result
 299     operator()(const _Tp& __x, const _Tp& __y) const
 300     { return __x + __y; }
 301   };
 302
 303
 304 /** @brief Similar to std::multiplies, but allows two different types. */
 305 template<typename _Tp1, typename _Tp2>
 306   struct _Multiplies : public std::binary_function<_Tp1, _Tp2, _Tp1>
 307   {
 308     typedef __typeof__(*static_cast<_Tp1*>(NULL)
 309                        * *static_cast<_Tp2*>(NULL)) __result;
 310
 311     __result
 312     operator()(const _Tp1& __x, const _Tp2& __y) const
 313     { return __x * __y; }
 314   };
 315
 316 // Partial specialization for one type. Same as std::multiplies.
 317 template<typename _Tp>
 318   struct _Multiplies<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp>
 319   {
 320     typedef __typeof__(*static_cast<_Tp*>(NULL)
 321                        * *static_cast<_Tp*>(NULL)) __result;
 322
 323     __result
 324     operator()(const _Tp& __x, const _Tp& __y) const
 325     { return __x * __y; }
 326   };
 327
 328
 329 template<typename _Tp, typename _DifferenceTp>
 330   class _PseudoSequence;
 331
 332 /** @brief _Iterator associated with __gnu_parallel::_PseudoSequence.
 333   *  If features the usual random-access iterator functionality.
 334   *  @param _Tp Sequence _M_value type.
 335   *  @param _DifferenceType Sequence difference type.
 336   */
 337 template<typename _Tp, typename _DifferenceTp>
 338   class _PseudoSequenceIterator
 339   {
 340   public:
 341     typedef _DifferenceTp _DifferenceType;
 342
 343   private:
 344     const _Tp& _M_val;
 345     _DifferenceType _M_pos;
 346
 347   public:
 348     _PseudoSequenceIterator(const _Tp& _M_val, _DifferenceType _M_pos)
 349     : _M_val(_M_val), _M_pos(_M_pos) { }
 350
 351     // Pre-increment operator.
 352     _PseudoSequenceIterator&
 353     operator++()
 354     {
 355       ++_M_pos;
 356       return *this;
 357     }
 358
 359     // Post-increment operator.
 360     const _PseudoSequenceIterator
 361     operator++(int)
 362     { return _PseudoSequenceIterator(_M_pos++); }
 363
 364     const _Tp&
 365     operator*() const
 366     { return _M_val; }
 367
 368     const _Tp&
 369     operator[](_DifferenceType) const
 370     { return _M_val; }
 371
 372     bool
 373     operator==(const _PseudoSequenceIterator& __i2)
 374     { return _M_pos == __i2._M_pos; }
 375
 376     _DifferenceType
 377     operator!=(const _PseudoSequenceIterator& __i2)
 378     { return _M_pos != __i2._M_pos; }
 379
 380     _DifferenceType
 381     operator-(const _PseudoSequenceIterator& __i2)
 382     { return _M_pos - __i2._M_pos; }
 383   };
 384
 385 /** @brief Sequence that conceptually consists of multiple copies of
 386     the same element.
 387   *  The copies are not stored explicitly, of course.
 388   *  @param _Tp Sequence _M_value type.
 389   *  @param _DifferenceType Sequence difference type.
 390   */
 391 template<typename _Tp, typename _DifferenceTp>
 392   class _PseudoSequence
 393   {
 394   public:
 395     typedef _DifferenceTp _DifferenceType;
 396
 397     // Better case down to uint64, than up to _DifferenceTp.
 398     typedef _PseudoSequenceIterator<_Tp, uint64> iterator;
 399
 400     /** @brief Constructor.
 401       *  @param _M_val Element of the sequence.
 402       *  @param __count Number of (virtual) copies.
 403       */
 404     _PseudoSequence(const _Tp& _M_val, _DifferenceType __count)
 405     : _M_val(_M_val), __count(__count)  { }
 406
 407     /** @brief Begin iterator. */
 408     iterator
 409     begin() const
 410     { return iterator(_M_val, 0); }
 411
 412     /** @brief End iterator. */
 413     iterator
 414     end() const
 415     { return iterator(_M_val, __count); }
 416
 417   private:
 418     const _Tp& _M_val;
 419     _DifferenceType __count;
 420   };
 421
 422 /** @brief Functor that does nothing */
 423 template<typename _ValueTp>
 424   class _VoidFunctor
 425   {
 426     inline void
 427     operator()(const _ValueTp& __v) const { }
 428   };
 429
 430 /** @brief Compute the median of three referenced elements,
 431     according to @__c __comp.
 432   *  @param __a First iterator.
 433   *  @param __b Second iterator.
 434   *  @param __c Third iterator.
 435   *  @param __comp Comparator.
 436   */
 437 template<typename _RAIter, typename _Compare>
 438   _RAIter
 439   __median_of_three_iterators(_RAIter __a, _RAIter __b,
 440                             _RAIter __c, _Compare& __comp)
 441   {
 442     if (__comp(*__a, *__b))
 443       if (__comp(*__b, *__c))
 444         return __b;
 445       else
 446         if (__comp(*__a, *__c))
 447           return __c;
 448         else
 449           return __a;
 450     else
 451       {
 452         // Just swap __a and __b.
 453         if (__comp(*__a, *__c))
 454           return __a;
 455         else
 456           if (__comp(*__b, *__c))
 457             return __c;
 458           else
 459             return __b;
 460       }
 461   }
 462
 463 #define _GLIBCXX_PARALLEL_ASSERT(_Condition) __glibcxx_assert(_Condition)
 464
 465 } //namespace __gnu_parallel
 466
 467 #endif /* _GLIBCXX_PARALLEL_BASE_H */