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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007, 2008 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/base.h
  32  *  @brief Sequential helper functions.
  33  *  This file is a GNU parallel extension to the Standard C++ Library.
  34  */
  35
  36 // Written by Johannes Singler.
  37
  38 #ifndef _GLIBCXX_PARALLEL_BASE_H
  39 #define _GLIBCXX_PARALLEL_BASE_H 1
  40
  41 #include <cstdio>
  42 #include <functional>
  43 #include <omp.h>
  44 #include <parallel/features.h>
  45 #include <parallel/basic_iterator.h>
  46 #include <parallel/parallel.h>
  47
  48
  49 // Parallel mode namespaces.
  50
  51 /**
  52  * @namespace std::__parallel
  53  * @brief GNU parallel code, replaces standard behavior with parallel behavior.
  54  */
  55 namespace std
  56 {
  57   namespace __parallel { }
  58 }
  59
  60 /**
  61  * @namespace __gnu_parallel
  62  * @brief GNU parallel code for public use.
  63  */
  64 namespace __gnu_parallel
  65 {
  66   // Import all the parallel versions of components in namespace std.
  67   using namespace std::__parallel;
  68 }
  69
  70 /**
  71  * @namespace __gnu_sequential
  72  * @brief GNU sequential classes for public use.
  73  */
  74 namespace __gnu_sequential
  75 {
  76   // Import whatever is the serial version.
  77 #ifdef _GLIBCXX_PARALLEL
  78   using namespace std::__norm;
  79 #else
  80   using namespace std;
  81 #endif
  82 }
  83
  84
  85 namespace __gnu_parallel
  86 {
  87   // NB: Including this file cannot produce (unresolved) symbols from
  88   // the OpenMP runtime unless the parallel mode is actually invoked
  89   // and active, which imples that the OpenMP runtime is actually
  90   // going to be linked in.
  91   inline int
  92   get_max_threads()
  93   {
  94     int __i = omp_get_max_threads();
  95     return __i > 1 ? __i : 1;
  96   }
  97
  98
  99   inline bool
 100   is_parallel(const _Parallelism __p) { return __p != sequential; }
 101
 102
 103   // XXX remove std::duplicates from here if possible,
 104   // XXX but keep minimal dependencies.
 105
 106 /** @brief Calculates the rounded-down logarithm of @c n for base 2.
 107   *  @param n Argument.
 108   *  @return Returns 0 for argument 0.
 109   */
 110 template<typename Size>
 111   inline Size
 112   log2(Size n)
 113     {
 114       Size k;
 115       for (k = 0; n != 1; n >>= 1)
 116         ++k;
 117       return k;
 118     }
 119
 120 /** @brief Encode two integers into one __gnu_parallel::lcas_t.
 121   *  @param a First integer, to be encoded in the most-significant @c
 122   *  lcas_t_bits/2 bits.
 123   *  @param b Second integer, to be encoded in the least-significant
 124   *  @c lcas_t_bits/2 bits.
 125   *  @return __gnu_parallel::lcas_t value encoding @c a and @c b.
 126   *  @see decode2
 127   */
 128 inline lcas_t
 129 encode2(int a, int b)   //must all be non-negative, actually
 130 {
 131   return (((lcas_t)a) << (lcas_t_bits / 2)) | (((lcas_t)b) << 0);
 132 }
 133
 134 /** @brief Decode two integers from one __gnu_parallel::lcas_t.
 135   *  @param x __gnu_parallel::lcas_t to decode integers from.
 136   *  @param a First integer, to be decoded from the most-significant
 137   *  @c lcas_t_bits/2 bits of @c x.
 138   *  @param b Second integer, to be encoded in the least-significant
 139   *  @c lcas_t_bits/2 bits of @c x.
 140   *  @see encode2
 141   */
 142 inline void
 143 decode2(lcas_t x, int& a, int& b)
 144 {
 145   a = (int)((x >> (lcas_t_bits / 2)) & lcas_t_mask);
 146   b = (int)((x >>               0 ) & lcas_t_mask);
 147 }
 148
 149 /** @brief Equivalent to std::min. */
 150 template<typename T>
 151   const T&
 152   min(const T& a, const T& b)
 153   { return (a < b) ? a : b; }
 154
 155 /** @brief Equivalent to std::max. */
 156 template<typename T>
 157   const T&
 158   max(const T& a, const T& b)
 159   { return (a > b) ? a : b; }
 160
 161 /** @brief Constructs predicate for equality from strict weak
 162   *  ordering predicate
 163   */
 164 // XXX comparator at the end, as per others
 165 template<typename Comparator, typename T1, typename T2>
 166   class equal_from_less : public std::binary_function<T1, T2, bool>
 167   {
 168   private:
 169     Comparator& comp;
 170
 171   public:
 172     equal_from_less(Comparator& _comp) : comp(_comp) { }
 173
 174     bool operator()(const T1& a, const T2& b)
 175     {
 176       return !comp(a, b) && !comp(b, a);
 177     }
 178   };
 179
 180
 181 /** @brief Similar to std::binder1st,
 182   *  but giving the argument types explicitly. */
 183 template<typename _Predicate, typename argument_type>
 184   class unary_negate
 185   : public std::unary_function<argument_type, bool>
 186   {
 187   protected:
 188     _Predicate _M_pred;
 189
 190   public:
 191     explicit
 192     unary_negate(const _Predicate& __x) : _M_pred(__x) { }
 193
 194     bool
 195     operator()(const argument_type& __x)
 196     { return !_M_pred(__x); }
 197   };
 198
 199 /** @brief Similar to std::binder1st,
 200   *  but giving the argument types explicitly. */
 201 template<typename _Operation, typename first_argument_type,
 202          typename second_argument_type, typename result_type>
 203   class binder1st
 204   : public std::unary_function<second_argument_type, result_type>
 205   {
 206   protected:
 207     _Operation op;
 208     first_argument_type value;
 209
 210   public:
 211     binder1st(const _Operation& __x,
 212               const first_argument_type& __y)
 213     : op(__x), value(__y) { }
 214
 215     result_type
 216     operator()(const second_argument_type& __x)
 217     { return op(value, __x); }
 218
 219     // _GLIBCXX_RESOLVE_LIB_DEFECTS
 220     // 109.  Missing binders for non-const sequence elements
 221     result_type
 222     operator()(second_argument_type& __x) const
 223     { return op(value, __x); }
 224   };
 225
 226 /**
 227   *  @brief Similar to std::binder2nd, but giving the argument types
 228   *  explicitly.
 229   */
 230 template<typename _Operation, typename first_argument_type,
 231          typename second_argument_type, typename result_type>
 232   class binder2nd
 233   : public std::unary_function<first_argument_type, result_type>
 234   {
 235   protected:
 236     _Operation op;
 237     second_argument_type value;
 238
 239   public:
 240     binder2nd(const _Operation& __x,
 241               const second_argument_type& __y)
 242     : op(__x), value(__y) { }
 243
 244     result_type
 245     operator()(const first_argument_type& __x) const
 246     { return op(__x, value); }
 247
 248     // _GLIBCXX_RESOLVE_LIB_DEFECTS
 249     // 109.  Missing binders for non-const sequence elements
 250     result_type
 251     operator()(first_argument_type& __x)
 252     { return op(__x, value); }
 253   };
 254
 255 /** @brief Similar to std::equal_to, but allows two different types. */
 256 template<typename T1, typename T2>
 257   struct equal_to : std::binary_function<T1, T2, bool>
 258   {
 259     bool operator()(const T1& t1, const T2& t2) const
 260     { return t1 == t2; }
 261   };
 262
 263 /** @brief Similar to std::less, but allows two different types. */
 264 template<typename T1, typename T2>
 265   struct less : std::binary_function<T1, T2, bool>
 266   {
 267     bool
 268     operator()(const T1& t1, const T2& t2) const
 269     { return t1 < t2; }
 270
 271     bool
 272     operator()(const T2& t2, const T1& t1) const
 273     { return t2 < t1; }
 274   };
 275
 276 // Partial specialization for one type. Same as std::less.
 277 template<typename _Tp>
 278 struct less<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, bool>
 279   {
 280     bool
 281     operator()(const _Tp& __x, const _Tp& __y) const
 282     { return __x < __y; }
 283   };
 284
 285
 286   /** @brief Similar to std::plus, but allows two different types. */
 287 template<typename _Tp1, typename _Tp2>
 288   struct plus : public std::binary_function<_Tp1, _Tp2, _Tp1>
 289   {
 290     typedef typeof(*static_cast<_Tp1*>(NULL)
 291                     + *static_cast<_Tp2*>(NULL)) result;
 292
 293     result
 294     operator()(const _Tp1& __x, const _Tp2& __y) const
 295     { return __x + __y; }
 296   };
 297
 298 // Partial specialization for one type. Same as std::plus.
 299 template<typename _Tp>
 300   struct plus<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp>
 301   {
 302     typedef typeof(*static_cast<_Tp*>(NULL)
 303                     + *static_cast<_Tp*>(NULL)) result;
 304
 305     result
 306     operator()(const _Tp& __x, const _Tp& __y) const
 307     { return __x + __y; }
 308   };
 309
 310
 311 /** @brief Similar to std::multiplies, but allows two different types. */
 312 template<typename _Tp1, typename _Tp2>
 313   struct multiplies : public std::binary_function<_Tp1, _Tp2, _Tp1>
 314   {
 315     typedef typeof(*static_cast<_Tp1*>(NULL)
 316                     * *static_cast<_Tp2*>(NULL)) result;
 317
 318     result
 319     operator()(const _Tp1& __x, const _Tp2& __y) const
 320     { return __x * __y; }
 321   };
 322
 323 // Partial specialization for one type. Same as std::multiplies.
 324 template<typename _Tp>
 325   struct multiplies<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp>
 326   {
 327     typedef typeof(*static_cast<_Tp*>(NULL)
 328                     * *static_cast<_Tp*>(NULL)) result;
 329
 330     result
 331     operator()(const _Tp& __x, const _Tp& __y) const
 332     { return __x * __y; }
 333   };
 334
 335
 336 template<typename T, typename _DifferenceTp>
 337   class pseudo_sequence;
 338
 339 /** @brief Iterator associated with __gnu_parallel::pseudo_sequence.
 340   *  If features the usual random-access iterator functionality.
 341   *  @param T Sequence value type.
 342   *  @param difference_type Sequence difference type.
 343   */
 344 template<typename T, typename _DifferenceTp>
 345   class pseudo_sequence_iterator
 346   {
 347   public:
 348     typedef _DifferenceTp difference_type;
 349
 350   private:
 351     typedef pseudo_sequence_iterator<T, _DifferenceTp> type;
 352
 353     const T& val;
 354     difference_type pos;
 355
 356   public:
 357     pseudo_sequence_iterator(const T& val, difference_type pos)
 358     : val(val), pos(pos) { }
 359
 360     // Pre-increment operator.
 361     type&
 362     operator++()
 363     {
 364       ++pos;
 365       return *this;
 366     }
 367
 368     // Post-increment operator.
 369     const type
 370     operator++(int)
 371     { return type(pos++); }
 372
 373     const T&
 374     operator*() const
 375     { return val; }
 376
 377     const T&
 378     operator[](difference_type) const
 379     { return val; }
 380
 381     bool
 382     operator==(const type& i2)
 383     { return pos == i2.pos; }
 384
 385     difference_type
 386     operator!=(const type& i2)
 387     { return pos != i2.pos; }
 388
 389     difference_type
 390     operator-(const type& i2)
 391     { return pos - i2.pos; }
 392   };
 393
 394 /** @brief Sequence that conceptually consists of multiple copies of
 395     the same element.
 396   *  The copies are not stored explicitly, of course.
 397   *  @param T Sequence value type.
 398   *  @param difference_type Sequence difference type.
 399   */
 400 template<typename T, typename _DifferenceTp>
 401   class pseudo_sequence
 402   {
 403     typedef pseudo_sequence<T, _DifferenceTp> type;
 404
 405   public:
 406     typedef _DifferenceTp difference_type;
 407
 408     // Better case down to uint64, than up to _DifferenceTp.
 409     typedef pseudo_sequence_iterator<T, uint64> iterator;
 410
 411     /** @brief Constructor.
 412       *  @param val Element of the sequence.
 413       *  @param count Number of (virtual) copies.
 414       */
 415     pseudo_sequence(const T& val, difference_type count)
 416     : val(val), count(count)  { }
 417
 418     /** @brief Begin iterator. */
 419     iterator
 420     begin() const
 421     { return iterator(val, 0); }
 422
 423     /** @brief End iterator. */
 424     iterator
 425     end() const
 426     { return iterator(val, count); }
 427
 428   private:
 429     const T& val;
 430     difference_type count;
 431   };
 432
 433 /** @brief Functor that does nothing */
 434 template<typename _ValueTp>
 435   class void_functor
 436   {
 437     inline void
 438     operator()(const _ValueTp& v) const { }
 439   };
 440
 441 /** @brief Compute the median of three referenced elements,
 442     according to @c comp.
 443   *  @param a First iterator.
 444   *  @param b Second iterator.
 445   *  @param c Third iterator.
 446   *  @param comp Comparator.
 447   */
 448 template<typename RandomAccessIterator, typename Comparator>
 449   RandomAccessIterator
 450   median_of_three_iterators(RandomAccessIterator a, RandomAccessIterator b,
 451                             RandomAccessIterator c, Comparator& comp)
 452   {
 453     if (comp(*a, *b))
 454       if (comp(*b, *c))
 455         return b;
 456       else
 457         if (comp(*a, *c))
 458           return c;
 459         else
 460           return a;
 461     else
 462       {
 463         // Just swap a and b.
 464         if (comp(*a, *c))
 465           return a;
 466         else
 467           if (comp(*b, *c))
 468             return c;
 469           else
 470             return b;
 471       }
 472   }
 473
 474 // Avoid the use of assert, because we're trying to keep the <cassert>
 475 // include out of the mix. (Same as debug mode).
 476 inline void
 477 __replacement_assert(const char* __file, int __line,
 478                      const char* __function, const char* __condition)
 479 {
 480   std::printf("%s:%d: %s: Assertion '%s' failed.\n", __file, __line,
 481               __function, __condition);
 482   __builtin_abort();
 483 }
 484
 485 #define _GLIBCXX_PARALLEL_ASSERT(_Condition)                            \
 486 do                                                                      \
 487   {                                                                     \
 488     if (!(_Condition))                                                  \
 489       __gnu_parallel::__replacement_assert(__FILE__, __LINE__,          \
 490                                   __PRETTY_FUNCTION__, #_Condition);    \
 491   } while (false)
 492
 493 } //namespace __gnu_parallel
 494
 495 #endif