base.h

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 2, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License
00017 // along with this library; see the file COPYING.  If not, write to
00018 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
00019 // MA 02111-1307, USA.
00020 
00021 // As a special exception, you may use this file as part of a free
00022 // software library without restriction.  Specifically, if other files
00023 // instantiate templates or use macros or inline functions from this
00024 // file, or you compile this file and link it with other files to
00025 // produce an executable, this file does not by itself cause the
00026 // resulting executable to be covered by the GNU General Public
00027 // License.  This exception does not however invalidate any other
00028 // reasons why the executable file might be covered by the GNU General
00029 // Public License.
00030 
00031 /** @file parallel/base.h
00032  *  @brief Sequential helper functions.
00033  *  This file is a GNU parallel extension to the Standard C++ Library.
00034  */
00035 
00036 // Written by Johannes Singler.
00037 
00038 #ifndef _GLIBCXX_PARALLEL_BASE_H
00039 #define _GLIBCXX_PARALLEL_BASE_H 1
00040 
00041 #include <cstdio>
00042 #include <functional>
00043 #include <omp.h>
00044 #include <parallel/features.h>
00045 #include <parallel/basic_iterator.h>
00046 #include <parallel/parallel.h>
00047 
00048 
00049 // Parallel mode namespaces.
00050 
00051 /**
00052  * @namespace std::__parallel
00053  * @brief GNU parallel code, replaces standard behavior with parallel behavior.
00054  */
00055 namespace std 
00056 { 
00057   namespace __parallel { } 
00058 }
00059 
00060 /**
00061  * @namespace __gnu_parallel
00062  * @brief GNU parallel code for public use.
00063  */
00064 namespace __gnu_parallel
00065 {
00066   // Import all the parallel versions of components in namespace std.
00067   using namespace std::__parallel;
00068 }
00069 
00070 /**
00071  * @namespace __gnu_sequential
00072  * @brief GNU sequential classes for public use.
00073  */
00074 namespace __gnu_sequential 
00075 { 
00076   // Import whatever is the serial version.
00077 #ifdef _GLIBCXX_PARALLEL
00078   using namespace std::__norm;
00079 #else
00080   using namespace std;
00081 #endif   
00082 }
00083 
00084 
00085 namespace __gnu_parallel
00086 {
00087   // NB: Including this file cannot produce (unresolved) symbols from
00088   // the OpenMP runtime unless the parallel mode is actually invoked
00089   // and active, which imples that the OpenMP runtime is actually
00090   // going to be linked in.
00091   inline int
00092   get_max_threads() 
00093   { 
00094     int __i = omp_get_max_threads();
00095     return __i > 1 ? __i : 1; 
00096   }
00097 
00098   
00099   inline bool 
00100   is_parallel(const _Parallelism __p) { return __p != sequential; }
00101 
00102 
00103   // XXX remove std::duplicates from here if possible,
00104   // XXX but keep minimal dependencies.
00105 
00106 /** @brief Calculates the rounded-down logarithm of @c n for base 2.
00107   *  @param n Argument.
00108   *  @return Returns 0 for argument 0.
00109   */
00110 template<typename Size>
00111   inline Size
00112   log2(Size n)
00113     {
00114       Size k;
00115       for (k = 0; n != 1; n >>= 1)
00116         ++k;
00117       return k;
00118     }
00119 
00120 /** @brief Encode two integers into one __gnu_parallel::lcas_t.
00121   *  @param a First integer, to be encoded in the most-significant @c
00122   *  lcas_t_bits/2 bits.
00123   *  @param b Second integer, to be encoded in the least-significant
00124   *  @c lcas_t_bits/2 bits.
00125   *  @return __gnu_parallel::lcas_t value encoding @c a and @c b.
00126   *  @see decode2
00127   */
00128 inline lcas_t
00129 encode2(int a, int b)   //must all be non-negative, actually
00130 {
00131   return (((lcas_t)a) << (lcas_t_bits / 2)) | (((lcas_t)b) << 0);
00132 }
00133 
00134 /** @brief Decode two integers from one __gnu_parallel::lcas_t.
00135   *  @param x __gnu_parallel::lcas_t to decode integers from.
00136   *  @param a First integer, to be decoded from the most-significant
00137   *  @c lcas_t_bits/2 bits of @c x.
00138   *  @param b Second integer, to be encoded in the least-significant
00139   *  @c lcas_t_bits/2 bits of @c x.
00140   *  @see encode2
00141   */
00142 inline void
00143 decode2(lcas_t x, int& a, int& b)
00144 {
00145   a = (int)((x >> (lcas_t_bits / 2)) & lcas_t_mask);
00146   b = (int)((x >>               0 ) & lcas_t_mask);
00147 }
00148 
00149 /** @brief Equivalent to std::min. */
00150 template<typename T>
00151   const T&
00152   min(const T& a, const T& b)
00153   { return (a < b) ? a : b; }
00154 
00155 /** @brief Equivalent to std::max. */
00156 template<typename T>
00157   const T&
00158   max(const T& a, const T& b)
00159   { return (a > b) ? a : b; }
00160 
00161 /** @brief Constructs predicate for equality from strict weak
00162   *  ordering predicate
00163   */
00164 // XXX comparator at the end, as per others
00165 template<typename Comparator, typename T1, typename T2>
00166   class equal_from_less : public std::binary_function<T1, T2, bool>
00167   {
00168   private:
00169     Comparator& comp;
00170 
00171   public:
00172     equal_from_less(Comparator& _comp) : comp(_comp) { }
00173 
00174     bool operator()(const T1& a, const T2& b)
00175     {
00176       return !comp(a, b) && !comp(b, a);
00177     }
00178   };
00179 
00180 
00181 /** @brief Similar to std::binder1st,
00182   *  but giving the argument types explicitly. */
00183 template<typename _Predicate, typename argument_type>
00184   class unary_negate
00185   : public std::unary_function<argument_type, bool>
00186   {
00187   protected:
00188     _Predicate _M_pred;
00189 
00190   public:
00191     explicit
00192     unary_negate(const _Predicate& __x) : _M_pred(__x) { }
00193 
00194     bool
00195     operator()(const argument_type& __x)
00196     { return !_M_pred(__x); }
00197   };
00198 
00199 /** @brief Similar to std::binder1st,
00200   *  but giving the argument types explicitly. */
00201 template<typename _Operation, typename first_argument_type,
00202      typename second_argument_type, typename result_type>
00203   class binder1st
00204   : public std::unary_function<second_argument_type, result_type>
00205   {
00206   protected:
00207     _Operation op;
00208     first_argument_type value;
00209 
00210   public:
00211     binder1st(const _Operation& __x,
00212               const first_argument_type& __y)
00213     : op(__x), value(__y) { }
00214 
00215     result_type
00216     operator()(const second_argument_type& __x)
00217     { return op(value, __x); }
00218 
00219     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00220     // 109.  Missing binders for non-const sequence elements
00221     result_type
00222     operator()(second_argument_type& __x) const
00223     { return op(value, __x); }
00224   };
00225 
00226 /**
00227   *  @brief Similar to std::binder2nd, but giving the argument types
00228   *  explicitly.
00229   */
00230 template<typename _Operation, typename first_argument_type,
00231      typename second_argument_type, typename result_type>
00232   class binder2nd
00233   : public std::unary_function<first_argument_type, result_type>
00234   {
00235   protected:
00236     _Operation op;
00237     second_argument_type value;
00238 
00239   public:
00240     binder2nd(const _Operation& __x,
00241               const second_argument_type& __y)
00242     : op(__x), value(__y) { }
00243 
00244     result_type
00245     operator()(const first_argument_type& __x) const
00246     { return op(__x, value); }
00247 
00248     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00249     // 109.  Missing binders for non-const sequence elements
00250     result_type
00251     operator()(first_argument_type& __x)
00252     { return op(__x, value); }
00253   };
00254 
00255 /** @brief Similar to std::equal_to, but allows two different types. */
00256 template<typename T1, typename T2>
00257   struct equal_to : std::binary_function<T1, T2, bool>
00258   {
00259     bool operator()(const T1& t1, const T2& t2) const
00260     { return t1 == t2; }
00261   };
00262 
00263 /** @brief Similar to std::less, but allows two different types. */
00264 template<typename T1, typename T2>
00265   struct less : std::binary_function<T1, T2, bool>
00266   {
00267     bool
00268     operator()(const T1& t1, const T2& t2) const
00269     { return t1 < t2; }
00270 
00271     bool
00272     operator()(const T2& t2, const T1& t1) const
00273     { return t2 < t1; }
00274   };
00275 
00276 // Partial specialization for one type. Same as std::less.
00277 template<typename _Tp>
00278 struct less<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, bool>
00279   {
00280     bool
00281     operator()(const _Tp& __x, const _Tp& __y) const
00282     { return __x < __y; }
00283   };
00284 
00285 
00286   /** @brief Similar to std::plus, but allows two different types. */
00287 template<typename _Tp1, typename _Tp2>
00288   struct plus : public std::binary_function<_Tp1, _Tp2, _Tp1>
00289   {
00290     typedef typeof(*static_cast<_Tp1*>(NULL)
00291                     + *static_cast<_Tp2*>(NULL)) result;
00292 
00293     result
00294     operator()(const _Tp1& __x, const _Tp2& __y) const
00295     { return __x + __y; }
00296   };
00297 
00298 // Partial specialization for one type. Same as std::plus.
00299 template<typename _Tp>
00300   struct plus<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp>
00301   {
00302     typedef typeof(*static_cast<_Tp*>(NULL)
00303                     + *static_cast<_Tp*>(NULL)) result;
00304 
00305     result
00306     operator()(const _Tp& __x, const _Tp& __y) const
00307     { return __x + __y; }
00308   };
00309 
00310 
00311 /** @brief Similar to std::multiplies, but allows two different types. */
00312 template<typename _Tp1, typename _Tp2>
00313   struct multiplies : public std::binary_function<_Tp1, _Tp2, _Tp1>
00314   {
00315     typedef typeof(*static_cast<_Tp1*>(NULL)
00316                     * *static_cast<_Tp2*>(NULL)) result;
00317 
00318     result
00319     operator()(const _Tp1& __x, const _Tp2& __y) const
00320     { return __x * __y; }
00321   };
00322 
00323 // Partial specialization for one type. Same as std::multiplies.
00324 template<typename _Tp>
00325   struct multiplies<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp>
00326   {
00327     typedef typeof(*static_cast<_Tp*>(NULL)
00328                     * *static_cast<_Tp*>(NULL)) result;
00329 
00330     result
00331     operator()(const _Tp& __x, const _Tp& __y) const
00332     { return __x * __y; }
00333   };
00334 
00335 
00336 template<typename T, typename _DifferenceTp>
00337   class pseudo_sequence;
00338 
00339 /** @brief Iterator associated with __gnu_parallel::pseudo_sequence.
00340   *  If features the usual random-access iterator functionality.
00341   *  @param T Sequence value type.
00342   *  @param difference_type Sequence difference type.
00343   */
00344 template<typename T, typename _DifferenceTp>
00345   class pseudo_sequence_iterator
00346   {
00347   public:
00348     typedef _DifferenceTp difference_type;
00349 
00350   private:
00351     typedef pseudo_sequence_iterator<T, _DifferenceTp> type;
00352 
00353     const T& val;
00354     difference_type pos;
00355 
00356   public:
00357     pseudo_sequence_iterator(const T& val, difference_type pos)
00358     : val(val), pos(pos) { }
00359 
00360     // Pre-increment operator.
00361     type&
00362     operator++()
00363     {
00364       ++pos;
00365       return *this;
00366     }
00367 
00368     // Post-increment operator.
00369     const type
00370     operator++(int)
00371     { return type(pos++); }
00372 
00373     const T&
00374     operator*() const
00375     { return val; }
00376 
00377     const T&
00378     operator[](difference_type) const
00379     { return val; }
00380 
00381     bool
00382     operator==(const type& i2)
00383     { return pos == i2.pos; }
00384 
00385     difference_type
00386     operator!=(const type& i2)
00387     { return pos != i2.pos; }
00388 
00389     difference_type
00390     operator-(const type& i2)
00391     { return pos - i2.pos; }
00392   };
00393 
00394 /** @brief Sequence that conceptually consists of multiple copies of
00395     the same element.
00396   *  The copies are not stored explicitly, of course.
00397   *  @param T Sequence value type.
00398   *  @param difference_type Sequence difference type.
00399   */
00400 template<typename T, typename _DifferenceTp>
00401   class pseudo_sequence
00402   {
00403     typedef pseudo_sequence<T, _DifferenceTp> type;
00404 
00405   public:
00406     typedef _DifferenceTp difference_type;
00407 
00408     // Better case down to uint64, than up to _DifferenceTp.
00409     typedef pseudo_sequence_iterator<T, uint64> iterator;
00410 
00411     /** @brief Constructor.
00412       *  @param val Element of the sequence.
00413       *  @param count Number of (virtual) copies.
00414       */
00415     pseudo_sequence(const T& val, difference_type count)
00416     : val(val), count(count)  { }
00417 
00418     /** @brief Begin iterator. */
00419     iterator
00420     begin() const
00421     { return iterator(val, 0); }
00422 
00423     /** @brief End iterator. */
00424     iterator
00425     end() const
00426     { return iterator(val, count); }
00427 
00428   private:
00429     const T& val;
00430     difference_type count;
00431   };
00432 
00433 /** @brief Functor that does nothing */
00434 template<typename _ValueTp>
00435   class void_functor
00436   {
00437     inline void
00438     operator()(const _ValueTp& v) const { }
00439   };
00440 
00441 /** @brief Compute the median of three referenced elements,
00442     according to @c comp.
00443   *  @param a First iterator.
00444   *  @param b Second iterator.
00445   *  @param c Third iterator.
00446   *  @param comp Comparator.
00447   */
00448 template<typename RandomAccessIterator, typename Comparator>
00449   RandomAccessIterator
00450   median_of_three_iterators(RandomAccessIterator a, RandomAccessIterator b,
00451                             RandomAccessIterator c, Comparator& comp)
00452   {
00453     if (comp(*a, *b))
00454       if (comp(*b, *c))
00455         return b;
00456       else
00457         if (comp(*a, *c))
00458           return c;
00459         else
00460           return a;
00461     else
00462       {
00463         // Just swap a and b.
00464         if (comp(*a, *c))
00465           return a;
00466         else
00467           if (comp(*b, *c))
00468             return c;
00469           else
00470             return b;
00471       }
00472   }
00473 
00474 // Avoid the use of assert, because we're trying to keep the <cassert>
00475 // include out of the mix. (Same as debug mode).
00476 inline void
00477 __replacement_assert(const char* __file, int __line,
00478                      const char* __function, const char* __condition)
00479 {
00480   std::printf("%s:%d: %s: Assertion '%s' failed.\n", __file, __line,
00481               __function, __condition);
00482   __builtin_abort();
00483 }
00484 
00485 #define _GLIBCXX_PARALLEL_ASSERT(_Condition)                            \
00486 do                                      \
00487   {                                 \
00488     if (!(_Condition))                          \
00489       __gnu_parallel::__replacement_assert(__FILE__, __LINE__,      \
00490                                   __PRETTY_FUNCTION__, #_Condition);    \
00491   } while (false)
00492 
00493 } //namespace __gnu_parallel
00494 
00495 #endif

Generated on Wed Mar 26 00:42:54 2008 for libstdc++ by  doxygen 1.5.1