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