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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007 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 Constructs predicate for equality from strict weak
  96    *  ordering predicate
  97    */
  98   // XXX comparator at the end, as per others
  99   template<typename Comparator, typename T1, typename T2>
 100   class equal_from_less : public std::binary_function<T1, T2, bool>
 101   {
 102   private:
 103     Comparator& comp;
 104
 105   public:
 106     equal_from_less(Comparator& _comp) : comp(_comp) { }
 107
 108     bool operator()(const T1& a, const T2& b)
 109     {
 110       return !comp(a, b) && !comp(b, a);
 111     }
 112   };
 113
 114
 115   /** @brief Similar to std::binder1st, but giving the argument types explicitly. */
 116   template<typename _Predicate, typename argument_type>
 117     class unary_negate
 118     : public std::unary_function<argument_type, bool>
 119     {
 120     protected:
 121       _Predicate _M_pred;
 122
 123     public:
 124       explicit
 125       unary_negate(const _Predicate& __x) : _M_pred(__x) { }
 126
 127       bool
 128       operator()(const argument_type& __x)
 129       { return !_M_pred(__x); }
 130     };
 131
 132   /** @brief Similar to std::binder1st, but giving the argument types explicitly. */
 133   template<typename _Operation, typename first_argument_type, typename second_argument_type, typename result_type>
 134     class binder1st
 135     : public std::unary_function<second_argument_type, result_type>
 136     {
 137     protected:
 138       _Operation op;
 139       first_argument_type value;
 140
 141     public:
 142       binder1st(const _Operation& __x,
 143                 const first_argument_type& __y)
 144       : op(__x), value(__y) { }
 145
 146       result_type
 147       operator()(const second_argument_type& __x)
 148       { return op(value, __x); }
 149
 150       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 151       // 109.  Missing binders for non-const sequence elements
 152       result_type
 153       operator()(second_argument_type& __x) const
 154       { return op(value, __x); }
 155     };
 156
 157   /**
 158    *  @brief Similar to std::binder2nd, but giving the argument types
 159    *  explicitly.
 160    */
 161   template<typename _Operation, typename first_argument_type, typename second_argument_type, typename result_type>
 162     class binder2nd
 163     : public std::unary_function<first_argument_type, result_type>
 164     {
 165     protected:
 166       _Operation op;
 167       second_argument_type value;
 168
 169     public:
 170       binder2nd(const _Operation& __x,
 171                 const second_argument_type& __y)
 172       : op(__x), value(__y) { }
 173
 174       result_type
 175       operator()(const first_argument_type& __x) const
 176       { return op(__x, value); }
 177
 178       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 179       // 109.  Missing binders for non-const sequence elements
 180       result_type
 181       operator()(first_argument_type& __x)
 182       { return op(__x, value); }
 183     };
 184
 185   /** @brief Similar to std::equal_to, but allows two different types. */
 186   template<typename T1, typename T2>
 187   struct equal_to : std::binary_function<T1, T2, bool>
 188   {
 189     bool operator()(const T1& t1, const T2& t2) const
 190     { return t1 == t2; }
 191   };
 192
 193   /** @brief Similar to std::less, but allows two different types. */
 194   template<typename T1, typename T2>
 195   struct less : std::binary_function<T1, T2, bool>
 196   {
 197     bool
 198     operator()(const T1& t1, const T2& t2) const
 199     { return t1 < t2; }
 200
 201     bool
 202     operator()(const T2& t2, const T1& t1) const
 203     { return t2 < t1; }
 204   };
 205
 206   // Partial specialization for one type. Same as std::less.
 207   template<typename _Tp>
 208   struct less<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, bool>
 209     {
 210       bool
 211       operator()(const _Tp& __x, const _Tp& __y) const
 212       { return __x < __y; }
 213     };
 214
 215
 216     /** @brief Similar to std::plus, but allows two different types. */
 217   template<typename _Tp1, typename _Tp2>
 218     struct plus : public std::binary_function<_Tp1, _Tp2, _Tp1>
 219     {
 220       typedef typeof(*static_cast<_Tp1*>(NULL) + *static_cast<_Tp2*>(NULL)) result;
 221
 222       result
 223       operator()(const _Tp1& __x, const _Tp2& __y) const
 224       { return __x + __y; }
 225     };
 226
 227   // Partial specialization for one type. Same as std::plus.
 228   template<typename _Tp>
 229     struct plus<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp>
 230     {
 231       typedef typeof(*static_cast<_Tp*>(NULL) + *static_cast<_Tp*>(NULL)) result;
 232
 233       result
 234       operator()(const _Tp& __x, const _Tp& __y) const
 235       { return __x + __y; }
 236     };
 237
 238
 239   /** @brief Similar to std::multiplies, but allows two different types. */
 240   template<typename _Tp1, typename _Tp2>
 241     struct multiplies : public std::binary_function<_Tp1, _Tp2, _Tp1>
 242     {
 243       typedef typeof(*static_cast<_Tp1*>(NULL) * *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::multiplies.
 251   template<typename _Tp>
 252     struct multiplies<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp>
 253     {
 254       typedef typeof(*static_cast<_Tp*>(NULL) * *static_cast<_Tp*>(NULL)) result;
 255
 256       result
 257       operator()(const _Tp& __x, const _Tp& __y) const
 258       { return __x * __y; }
 259     };
 260
 261
 262   template<typename T, typename _DifferenceTp>
 263   class pseudo_sequence;
 264
 265   /** @brief Iterator associated with __gnu_parallel::pseudo_sequence.
 266    *  If features the usual random-access iterator functionality.
 267    *  @param T Sequence value type.
 268    *  @param difference_type Sequence difference type.
 269    */
 270   template<typename T, typename _DifferenceTp>
 271   class pseudo_sequence_iterator
 272   {
 273   public:
 274     typedef _DifferenceTp difference_type;
 275
 276   private:
 277     typedef pseudo_sequence_iterator<T, _DifferenceTp> type;
 278
 279     const T& val;
 280     difference_type pos;
 281
 282   public:
 283     pseudo_sequence_iterator(const T& val, difference_type pos)
 284     : val(val), pos(pos) { }
 285
 286     // Pre-increment operator.
 287     type&
 288     operator++()
 289     {
 290       ++pos;
 291       return *this;
 292     }
 293
 294     // Post-increment operator.
 295     const type
 296     operator++(int)
 297     { return type(pos++); }
 298
 299     const T&
 300     operator*() const
 301     { return val; }
 302
 303     const T&
 304     operator[](difference_type) const
 305     { return val; }
 306
 307     bool
 308     operator==(const type& i2)
 309     { return pos == i2.pos; }
 310
 311     difference_type
 312     operator!=(const type& i2)
 313     { return pos != i2.pos; }
 314
 315     difference_type
 316     operator-(const type& i2)
 317     { return pos - i2.pos; }
 318   };
 319
 320   /** @brief Sequence that conceptually consists of multiple copies of
 321       the same element.
 322    *  The copies are not stored explicitly, of course.
 323    *  @param T Sequence value type.
 324    *  @param difference_type Sequence difference type.
 325    */
 326   template<typename T, typename _DifferenceTp>
 327   class pseudo_sequence
 328   {
 329     typedef pseudo_sequence<T, _DifferenceTp> type;
 330
 331   public:
 332     typedef _DifferenceTp difference_type;
 333
 334     // Better case down to uint64, than up to _DifferenceTp.
 335     typedef pseudo_sequence_iterator<T, uint64> iterator;
 336
 337     /** @brief Constructor.
 338      *  @param val Element of the sequence.
 339      *  @param count Number of (virtual) copies.
 340      */
 341     pseudo_sequence(const T& val, difference_type count)
 342     : val(val), count(count)  { }
 343
 344     /** @brief Begin iterator. */
 345     iterator
 346     begin() const
 347     { return iterator(val, 0); }
 348
 349     /** @brief End iterator. */
 350     iterator
 351     end() const
 352     { return iterator(val, count); }
 353
 354   private:
 355     const T& val;
 356     difference_type count;
 357   };
 358
 359   /** @brief Functor that does nothing */
 360   template<typename _ValueTp>
 361   class void_functor
 362   {
 363     inline void
 364     operator()(const _ValueTp& v) const { }
 365   };
 366
 367   /** @brief Compute the median of three referenced elements,
 368       according to @c comp.
 369    *  @param a First iterator.
 370    *  @param b Second iterator.
 371    *  @param c Third iterator.
 372    *  @param comp Comparator.
 373    */
 374   template<typename RandomAccessIterator, typename Comparator>
 375   RandomAccessIterator
 376   median_of_three_iterators(RandomAccessIterator a, RandomAccessIterator b,
 377                             RandomAccessIterator c, Comparator& comp)
 378   {
 379     if (comp(*a, *b))
 380       if (comp(*b, *c))
 381         return b;
 382       else
 383         if (comp(*a, *c))
 384           return c;
 385         else
 386           return a;
 387     else
 388       {
 389         // Just swap a and b.
 390         if (comp(*a, *c))
 391           return a;
 392         else
 393           if (comp(*b, *c))
 394             return c;
 395           else
 396             return b;
 397       }
 398   }
 399
 400   // Avoid the use of assert, because we're trying to keep the <cassert>
 401   // include out of the mix. (Same as debug mode).
 402   inline void
 403   __replacement_assert(const char* __file, int __line,
 404                        const char* __function, const char* __condition)
 405   {
 406     std::printf("%s:%d: %s: Assertion '%s' failed.\n", __file, __line,
 407                 __function, __condition);
 408     __builtin_abort();
 409   }
 410
 411 #define _GLIBCXX_PARALLEL_ASSERT(_Condition)                            \
 412   do                                                                    \
 413     {                                                                   \
 414       if (!(_Condition))                                                \
 415         __gnu_parallel::__replacement_assert(__FILE__, __LINE__,        \
 416                                     __PRETTY_FUNCTION__, #_Condition);  \
 417     } while (false)
 418
 419 } //namespace __gnu_parallel
 420
 421 #endif
 422