1 // -*- C++ -*- 2 3 // Copyright (C) 2007-2013 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file parallel/base.h 26 * @brief Sequential helper functions. 27 * This file is a GNU parallel extension to the Standard C++ Library. 28 */ 29 30 // Written by Johannes Singler. 31 32 #ifndef _GLIBCXX_PARALLEL_BASE_H 33 #define _GLIBCXX_PARALLEL_BASE_H 1 34 35 #include <bits/c++config.h> 36 #include <bits/stl_function.h> 37 #include <omp.h> 38 #include <parallel/features.h> 39 #include <parallel/basic_iterator.h> 40 #include <parallel/parallel.h> 41 42 // Parallel mode namespaces. 43 44 /** 45 * @namespace std::__parallel 46 * @brief GNU parallel code, replaces standard behavior with parallel behavior. 47 */ 48 namespace std _GLIBCXX_VISIBILITY(default) 49 { 50 namespace __parallel { } 51 } 52 53 /** 54 * @namespace __gnu_parallel 55 * @brief GNU parallel code for public use. 56 */ 57 namespace __gnu_parallel 58 { 59 // Import all the parallel versions of components in namespace std. 60 using namespace std::__parallel; 61 } 62 63 /** 64 * @namespace __gnu_sequential 65 * @brief GNU sequential classes for public use. 66 */ 67 namespace __gnu_sequential 68 { 69 // Import whatever is the serial version. 70 #ifdef _GLIBCXX_PARALLEL 71 using namespace std::_GLIBCXX_STD_A; 72 #else 73 using namespace std; 74 #endif 75 } 76 77 78 namespace __gnu_parallel 79 { 80 // NB: Including this file cannot produce (unresolved) symbols from 81 // the OpenMP runtime unless the parallel mode is actually invoked 82 // and active, which imples that the OpenMP runtime is actually 83 // going to be linked in. 84 inline _ThreadIndex 85 __get_max_threads() 86 { 87 _ThreadIndex __i = omp_get_max_threads(); 88 return __i > 1 ? __i : 1; 89 } 90 91 92 inline bool 93 __is_parallel(const _Parallelism __p) { return __p != sequential; } 94 95 96 /** @brief Calculates the rounded-down logarithm of @c __n for base 2. 97 * @param __n Argument. 98 * @return Returns 0 for any argument <1. 99 */ 100 template<typename _Size> 101 inline _Size 102 __rd_log2(_Size __n) 103 { 104 _Size __k; 105 for (__k = 0; __n > 1; __n >>= 1) 106 ++__k; 107 return __k; 108 } 109 110 /** @brief Encode two integers into one gnu_parallel::_CASable. 111 * @param __a First integer, to be encoded in the most-significant @c 112 * _CASable_bits/2 bits. 113 * @param __b Second integer, to be encoded in the least-significant 114 * @c _CASable_bits/2 bits. 115 * @return value encoding @c __a and @c __b. 116 * @see __decode2 117 */ 118 inline _CASable 119 __encode2(int __a, int __b) //must all be non-negative, actually 120 { 121 return (((_CASable)__a) << (_CASable_bits / 2)) | (((_CASable)__b) << 0); 122 } 123 124 /** @brief Decode two integers from one gnu_parallel::_CASable. 125 * @param __x __gnu_parallel::_CASable to decode integers from. 126 * @param __a First integer, to be decoded from the most-significant 127 * @c _CASable_bits/2 bits of @c __x. 128 * @param __b Second integer, to be encoded in the least-significant 129 * @c _CASable_bits/2 bits of @c __x. 130 * @see __encode2 131 */ 132 inline void 133 __decode2(_CASable __x, int& __a, int& __b) 134 { 135 __a = (int)((__x >> (_CASable_bits / 2)) & _CASable_mask); 136 __b = (int)((__x >> 0 ) & _CASable_mask); 137 } 138 139 //needed for parallel "numeric", even if "algorithm" not included 140 141 /** @brief Equivalent to std::min. */ 142 template<typename _Tp> 143 inline const _Tp& 144 min(const _Tp& __a, const _Tp& __b) 145 { return (__a < __b) ? __a : __b; } 146 147 /** @brief Equivalent to std::max. */ 148 template<typename _Tp> 149 inline const _Tp& 150 max(const _Tp& __a, const _Tp& __b) 151 { return (__a > __b) ? __a : __b; } 152 153 /** @brief Constructs predicate for equality from strict weak 154 * ordering predicate 155 */ 156 template<typename _T1, typename _T2, typename _Compare> 157 class _EqualFromLess : public std::binary_function<_T1, _T2, bool> 158 { 159 private: 160 _Compare& _M_comp; 161 162 public: 163 _EqualFromLess(_Compare& __comp) : _M_comp(__comp) { } 164 165 bool operator()(const _T1& __a, const _T2& __b) 166 { return !_M_comp(__a, __b) && !_M_comp(__b, __a); } 167 }; 168 169 170 /** @brief Similar to std::unary_negate, 171 * but giving the argument types explicitly. */ 172 template<typename _Predicate, typename argument_type> 173 class __unary_negate 174 : public std::unary_function<argument_type, bool> 175 { 176 protected: 177 _Predicate _M_pred; 178 179 public: 180 explicit 181 __unary_negate(const _Predicate& __x) : _M_pred(__x) { } 182 183 bool 184 operator()(const argument_type& __x) 185 { return !_M_pred(__x); } 186 }; 187 188 /** @brief Similar to std::binder1st, 189 * but giving the argument types explicitly. */ 190 template<typename _Operation, typename _FirstArgumentType, 191 typename _SecondArgumentType, typename _ResultType> 192 class __binder1st 193 : public std::unary_function<_SecondArgumentType, _ResultType> 194 { 195 protected: 196 _Operation _M_op; 197 _FirstArgumentType _M_value; 198 199 public: 200 __binder1st(const _Operation& __x, const _FirstArgumentType& __y) 201 : _M_op(__x), _M_value(__y) { } 202 203 _ResultType 204 operator()(const _SecondArgumentType& __x) 205 { return _M_op(_M_value, __x); } 206 207 // _GLIBCXX_RESOLVE_LIB_DEFECTS 208 // 109. Missing binders for non-const sequence elements 209 _ResultType 210 operator()(_SecondArgumentType& __x) const 211 { return _M_op(_M_value, __x); } 212 }; 213 214 /** 215 * @brief Similar to std::binder2nd, but giving the argument types 216 * explicitly. 217 */ 218 template<typename _Operation, typename _FirstArgumentType, 219 typename _SecondArgumentType, typename _ResultType> 220 class __binder2nd 221 : public std::unary_function<_FirstArgumentType, _ResultType> 222 { 223 protected: 224 _Operation _M_op; 225 _SecondArgumentType _M_value; 226 227 public: 228 __binder2nd(const _Operation& __x, const _SecondArgumentType& __y) 229 : _M_op(__x), _M_value(__y) { } 230 231 _ResultType 232 operator()(const _FirstArgumentType& __x) const 233 { return _M_op(__x, _M_value); } 234 235 // _GLIBCXX_RESOLVE_LIB_DEFECTS 236 // 109. Missing binders for non-const sequence elements 237 _ResultType 238 operator()(_FirstArgumentType& __x) 239 { return _M_op(__x, _M_value); } 240 }; 241 242 /** @brief Similar to std::equal_to, but allows two different types. */ 243 template<typename _T1, typename _T2> 244 struct _EqualTo : std::binary_function<_T1, _T2, bool> 245 { 246 bool operator()(const _T1& __t1, const _T2& __t2) const 247 { return __t1 == __t2; } 248 }; 249 250 /** @brief Similar to std::less, but allows two different types. */ 251 template<typename _T1, typename _T2> 252 struct _Less : std::binary_function<_T1, _T2, bool> 253 { 254 bool 255 operator()(const _T1& __t1, const _T2& __t2) const 256 { return __t1 < __t2; } 257 258 bool 259 operator()(const _T2& __t2, const _T1& __t1) const 260 { return __t2 < __t1; } 261 }; 262 263 // Partial specialization for one type. Same as std::less. 264 template<typename _Tp> 265 struct _Less<_Tp, _Tp> 266 : public std::less<_Tp> { }; 267 268 /** @brief Similar to std::plus, but allows two different types. */ 269 template<typename _Tp1, typename _Tp2, typename _Result 270 = __typeof__(*static_cast<_Tp1*>(0) 271 + *static_cast<_Tp2*>(0))> 272 struct _Plus : public std::binary_function<_Tp1, _Tp2, _Result> 273 { 274 _Result 275 operator()(const _Tp1& __x, const _Tp2& __y) const 276 { return __x + __y; } 277 }; 278 279 // Partial specialization for one type. Same as std::plus. 280 template<typename _Tp> 281 struct _Plus<_Tp, _Tp, _Tp> 282 : public std::plus<_Tp> { }; 283 284 /** @brief Similar to std::multiplies, but allows two different types. */ 285 template<typename _Tp1, typename _Tp2, typename _Result 286 = __typeof__(*static_cast<_Tp1*>(0) 287 * *static_cast<_Tp2*>(0))> 288 struct _Multiplies : public std::binary_function<_Tp1, _Tp2, _Result> 289 { 290 _Result 291 operator()(const _Tp1& __x, const _Tp2& __y) const 292 { return __x * __y; } 293 }; 294 295 // Partial specialization for one type. Same as std::multiplies. 296 template<typename _Tp> 297 struct _Multiplies<_Tp, _Tp, _Tp> 298 : public std::multiplies<_Tp> { }; 299 300 /** @brief _Iterator associated with __gnu_parallel::_PseudoSequence. 301 * If features the usual random-access iterator functionality. 302 * @param _Tp Sequence _M_value type. 303 * @param _DifferenceTp Sequence difference type. 304 */ 305 template<typename _Tp, typename _DifferenceTp> 306 class _PseudoSequenceIterator 307 { 308 public: 309 typedef _DifferenceTp _DifferenceType; 310 311 _PseudoSequenceIterator(const _Tp& __val, _DifferenceType __pos) 312 : _M_val(__val), _M_pos(__pos) { } 313 314 // Pre-increment operator. 315 _PseudoSequenceIterator& 316 operator++() 317 { 318 ++_M_pos; 319 return *this; 320 } 321 322 // Post-increment operator. 323 _PseudoSequenceIterator 324 operator++(int) 325 { return _PseudoSequenceIterator(_M_pos++); } 326 327 const _Tp& 328 operator*() const 329 { return _M_val; } 330 331 const _Tp& 332 operator[](_DifferenceType) const 333 { return _M_val; } 334 335 bool 336 operator==(const _PseudoSequenceIterator& __i2) 337 { return _M_pos == __i2._M_pos; } 338 339 bool 340 operator!=(const _PseudoSequenceIterator& __i2) 341 { return _M_pos != __i2._M_pos; } 342 343 _DifferenceType 344 operator-(const _PseudoSequenceIterator& __i2) 345 { return _M_pos - __i2._M_pos; } 346 347 private: 348 const _Tp& _M_val; 349 _DifferenceType _M_pos; 350 }; 351 352 /** @brief Sequence that conceptually consists of multiple copies of 353 the same element. 354 * The copies are not stored explicitly, of course. 355 * @param _Tp Sequence _M_value type. 356 * @param _DifferenceTp Sequence difference type. 357 */ 358 template<typename _Tp, typename _DifferenceTp> 359 class _PseudoSequence 360 { 361 public: 362 typedef _DifferenceTp _DifferenceType; 363 364 // Better cast down to uint64_t, than up to _DifferenceTp. 365 typedef _PseudoSequenceIterator<_Tp, uint64_t> iterator; 366 367 /** @brief Constructor. 368 * @param __val Element of the sequence. 369 * @param __count Number of (virtual) copies. 370 */ 371 _PseudoSequence(const _Tp& __val, _DifferenceType __count) 372 : _M_val(__val), _M_count(__count) { } 373 374 /** @brief Begin iterator. */ 375 iterator 376 begin() const 377 { return iterator(_M_val, 0); } 378 379 /** @brief End iterator. */ 380 iterator 381 end() const 382 { return iterator(_M_val, _M_count); } 383 384 private: 385 const _Tp& _M_val; 386 _DifferenceType _M_count; 387 }; 388 389 /** @brief Compute the median of three referenced elements, 390 according to @c __comp. 391 * @param __a First iterator. 392 * @param __b Second iterator. 393 * @param __c Third iterator. 394 * @param __comp Comparator. 395 */ 396 template<typename _RAIter, typename _Compare> 397 _RAIter 398 __median_of_three_iterators(_RAIter __a, _RAIter __b, 399 _RAIter __c, _Compare __comp) 400 { 401 if (__comp(*__a, *__b)) 402 if (__comp(*__b, *__c)) 403 return __b; 404 else 405 if (__comp(*__a, *__c)) 406 return __c; 407 else 408 return __a; 409 else 410 { 411 // Just swap __a and __b. 412 if (__comp(*__a, *__c)) 413 return __a; 414 else 415 if (__comp(*__b, *__c)) 416 return __c; 417 else 418 return __b; 419 } 420 } 421 422 #define _GLIBCXX_PARALLEL_ASSERT(_Condition) __glibcxx_assert(_Condition) 423 424 } //namespace __gnu_parallel 425 426 #endif /* _GLIBCXX_PARALLEL_BASE_H */ 427
