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 _ThreadIndex
  85   __get_max_threads()
  86   {
  87     _ThreadIndex __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       { return !_M_comp(__a, __b) && !_M_comp(__b, __a); }
 167     };
 168
 169
 170   /** @brief Similar to std::binder1st,
 171    *  but giving the argument types explicitly. */
 172   template<typename _Predicate, typename argument_type>
 173     class __unary_negate
 174     : public std::unary_function<argument_type, bool>
 175     {
 176     protected:
 177       _Predicate _M_pred;
 178
 179     public:
 180       explicit
 181       __unary_negate(const _Predicate& __x) : _M_pred(__x) { }
 182
 183       bool
 184       operator()(const argument_type& __x)
 185       { return !_M_pred(__x); }
 186     };
 187
 188   /** @brief Similar to std::binder1st,
 189    *  but giving the argument types explicitly. */
 190   template<typename _Operation, typename _FirstArgumentType,
 191            typename _SecondArgumentType, typename _ResultType>
 192     class __binder1st
 193     : public std::unary_function<_SecondArgumentType, _ResultType>
 194     {
 195     protected:
 196       _Operation _M_op;
 197       _FirstArgumentType _M_value;
 198
 199     public:
 200       __binder1st(const _Operation& __x, const _FirstArgumentType& __y)
 201       : _M_op(__x), _M_value(__y) { }
 202
 203       _ResultType
 204       operator()(const _SecondArgumentType& __x)
 205       { return _M_op(_M_value, __x); }
 206
 207       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 208       // 109.  Missing binders for non-const sequence elements
 209       _ResultType
 210       operator()(_SecondArgumentType& __x) const
 211       { return _M_op(_M_value, __x); }
 212     };
 213
 214   /**
 215    *  @brief Similar to std::binder2nd, but giving the argument types
 216    *  explicitly.
 217    */
 218   template<typename _Operation, typename _FirstArgumentType,
 219            typename _SecondArgumentType, typename _ResultType>
 220     class binder2nd
 221     : public std::unary_function<_FirstArgumentType, _ResultType>
 222     {
 223     protected:
 224       _Operation _M_op;
 225       _SecondArgumentType _M_value;
 226
 227     public:
 228       binder2nd(const _Operation& __x, const _SecondArgumentType& __y)
 229       : _M_op(__x), _M_value(__y) { }
 230
 231       _ResultType
 232       operator()(const _FirstArgumentType& __x) const
 233       { return _M_op(__x, _M_value); }
 234
 235       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 236       // 109.  Missing binders for non-const sequence elements
 237       _ResultType
 238       operator()(_FirstArgumentType& __x)
 239       { return _M_op(__x, _M_value); }
 240     };
 241
 242   /** @brief Similar to std::equal_to, but allows two different types. */
 243   template<typename _T1, typename _T2>
 244     struct _EqualTo : std::binary_function<_T1, _T2, bool>
 245     {
 246       bool operator()(const _T1& __t1, const _T2& __t2) const
 247       { return __t1 == __t2; }
 248     };
 249
 250   /** @brief Similar to std::less, but allows two different types. */
 251   template<typename _T1, typename _T2>
 252     struct _Less : std::binary_function<_T1, _T2, bool>
 253     {
 254       bool
 255       operator()(const _T1& __t1, const _T2& __t2) const
 256       { return __t1 < __t2; }
 257
 258       bool
 259       operator()(const _T2& __t2, const _T1& __t1) const
 260       { return __t2 < __t1; }
 261     };
 262
 263   // Partial specialization for one type. Same as std::less.
 264   template<typename _Tp>
 265     struct _Less<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, bool>
 266     {
 267       bool
 268       operator()(const _Tp& __x, const _Tp& __y) const
 269       { return __x < __y; }
 270     };
 271
 272
 273   /** @brief Similar to std::plus, but allows two different types. */
 274   template<typename _Tp1, typename _Tp2>
 275     struct _Plus : public std::binary_function<_Tp1, _Tp2, _Tp1>
 276     {
 277       typedef __typeof__(*static_cast<_Tp1*>(NULL)
 278                          + *static_cast<_Tp2*>(NULL)) __result;
 279
 280       __result
 281       operator()(const _Tp1& __x, const _Tp2& __y) const
 282       { return __x + __y; }
 283     };
 284
 285   // Partial specialization for one type. Same as std::plus.
 286   template<typename _Tp>
 287     struct _Plus<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp>
 288     {
 289       typedef __typeof__(*static_cast<_Tp*>(NULL)
 290                          + *static_cast<_Tp*>(NULL)) __result;
 291
 292       __result
 293       operator()(const _Tp& __x, const _Tp& __y) const
 294       { return __x + __y; }
 295     };
 296
 297
 298   /** @brief Similar to std::multiplies, but allows two different types. */
 299   template<typename _Tp1, typename _Tp2>
 300     struct _Multiplies : public std::binary_function<_Tp1, _Tp2, _Tp1>
 301     {
 302       typedef __typeof__(*static_cast<_Tp1*>(NULL)
 303                          * *static_cast<_Tp2*>(NULL)) __result;
 304
 305       __result
 306       operator()(const _Tp1& __x, const _Tp2& __y) const
 307       { return __x * __y; }
 308     };
 309
 310   // Partial specialization for one type. Same as std::multiplies.
 311   template<typename _Tp>
 312     struct _Multiplies<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp>
 313     {
 314       typedef __typeof__(*static_cast<_Tp*>(NULL)
 315                          * *static_cast<_Tp*>(NULL)) __result;
 316
 317       __result
 318       operator()(const _Tp& __x, const _Tp& __y) const
 319       { return __x * __y; }
 320     };
 321
 322
 323   template<typename _Tp, typename _DifferenceTp>
 324     class _PseudoSequence;
 325
 326   /** @brief _Iterator associated with __gnu_parallel::_PseudoSequence.
 327    *  If features the usual random-access iterator functionality.
 328    *  @param _Tp Sequence _M_value type.
 329    *  @param _DifferenceType Sequence difference type.
 330    */
 331   template<typename _Tp, typename _DifferenceTp>
 332     class _PseudoSequenceIterator
 333     {
 334     public:
 335       typedef _DifferenceTp _DifferenceType;
 336
 337     private:
 338       const _Tp& _M_val;
 339       _DifferenceType _M_pos;
 340
 341     public:
 342       _PseudoSequenceIterator(const _Tp& __val, _DifferenceType __pos)
 343       : _M_val(__val), _M_pos(__pos) { }
 344
 345       // Pre-increment operator.
 346       _PseudoSequenceIterator&
 347       operator++()
 348       {
 349         ++_M_pos;
 350         return *this;
 351       }
 352
 353       // Post-increment operator.
 354       const _PseudoSequenceIterator
 355       operator++(int)
 356       { return _PseudoSequenceIterator(_M_pos++); }
 357
 358       const _Tp&
 359       operator*() const
 360       { return _M_val; }
 361
 362       const _Tp&
 363       operator[](_DifferenceType) const
 364       { return _M_val; }
 365
 366       bool
 367       operator==(const _PseudoSequenceIterator& __i2)
 368       { return _M_pos == __i2._M_pos; }
 369
 370       _DifferenceType
 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
 379   /** @brief Sequence that conceptually consists of multiple copies of
 380       the same element.
 381       *  The copies are not stored explicitly, of course.
 382       *  @param _Tp Sequence _M_value type.
 383       *  @param _DifferenceType Sequence difference type.
 384       */
 385   template<typename _Tp, typename _DifferenceTp>
 386     class _PseudoSequence
 387     {
 388     public:
 389       typedef _DifferenceTp _DifferenceType;
 390
 391       // Better cast down to uint64_t, than up to _DifferenceTp.
 392       typedef _PseudoSequenceIterator<_Tp, uint64_t> iterator;
 393
 394       /** @brief Constructor.
 395        *  @param _M_val Element of the sequence.
 396        *  @param __count Number of (virtual) copies.
 397        */
 398       _PseudoSequence(const _Tp& __val, _DifferenceType __count)
 399       : _M_val(__val), _M_count(__count)  { }
 400
 401       /** @brief Begin iterator. */
 402       iterator
 403       begin() const
 404       { return iterator(_M_val, 0); }
 405
 406       /** @brief End iterator. */
 407       iterator
 408       end() const
 409       { return iterator(_M_val, _M_count); }
 410
 411     private:
 412       const _Tp& _M_val;
 413       _DifferenceType _M_count;
 414     };
 415
 416   /** @brief Functor that does nothing */
 417   template<typename _ValueTp>
 418     class _VoidFunctor
 419     {
 420       inline void
 421       operator()(const _ValueTp& __v) const { }
 422     };
 423
 424   /** @brief Compute the median of three referenced elements,
 425       according to @c __comp.
 426       *  @param __a First iterator.
 427       *  @param __b Second iterator.
 428       *  @param __c Third iterator.
 429       *  @param __comp Comparator.
 430       */
 431   template<typename _RAIter, typename _Compare>
 432     _RAIter
 433     __median_of_three_iterators(_RAIter __a, _RAIter __b,
 434                                 _RAIter __c, _Compare& __comp)
 435     {
 436       if (__comp(*__a, *__b))
 437         if (__comp(*__b, *__c))
 438           return __b;
 439         else
 440           if (__comp(*__a, *__c))
 441             return __c;
 442           else
 443             return __a;
 444       else
 445         {
 446           // Just swap __a and __b.
 447           if (__comp(*__a, *__c))
 448             return __a;
 449           else
 450             if (__comp(*__b, *__c))
 451               return __c;
 452             else
 453               return __b;
 454         }
 455     }
 456
 457 #define _GLIBCXX_PARALLEL_ASSERT(_Condition) __glibcxx_assert(_Condition)
 458
 459 } //namespace __gnu_parallel
 460
 461 #endif /* _GLIBCXX_PARALLEL_BASE_H */