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