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