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