1 // -*- C++ -*- 2 3 // Copyright (C) 2007, 2008, 2009 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 <functional> 36 #include <omp.h> 37 #include <parallel/features.h> 38 #include <parallel/basic_iterator.h> 39 #include <parallel/parallel.h> 40 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 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::__norm; 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 int 85 get_max_threads() 86 { 87 int __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 // XXX remove std::duplicates from here if possible, 97 // XXX but keep minimal dependencies. 98 99 /** @brief Calculates the rounded-down logarithm of @c n for base 2. 100 * @param n Argument. 101 * @return Returns 0 for any argument <1. 102 */ 103 template<typename Size> 104 inline Size 105 __log2(Size n) 106 { 107 Size k; 108 for (k = 0; n > 1; n >>= 1) 109 ++k; 110 return k; 111 } 112 113 /** @brief Encode two integers into one __gnu_parallel::lcas_t. 114 * @param a First integer, to be encoded in the most-significant @c 115 * lcas_t_bits/2 bits. 116 * @param b Second integer, to be encoded in the least-significant 117 * @c lcas_t_bits/2 bits. 118 * @return __gnu_parallel::lcas_t value encoding @c a and @c b. 119 * @see decode2 120 */ 121 inline lcas_t 122 encode2(int a, int b) //must all be non-negative, actually 123 { 124 return (((lcas_t)a) << (lcas_t_bits / 2)) | (((lcas_t)b) << 0); 125 } 126 127 /** @brief Decode two integers from one __gnu_parallel::lcas_t. 128 * @param x __gnu_parallel::lcas_t to decode integers from. 129 * @param a First integer, to be decoded from the most-significant 130 * @c lcas_t_bits/2 bits of @c x. 131 * @param b Second integer, to be encoded in the least-significant 132 * @c lcas_t_bits/2 bits of @c x. 133 * @see encode2 134 */ 135 inline void 136 decode2(lcas_t x, int& a, int& b) 137 { 138 a = (int)((x >> (lcas_t_bits / 2)) & lcas_t_mask); 139 b = (int)((x >> 0 ) & lcas_t_mask); 140 } 141 142 /** @brief Equivalent to std::min. */ 143 template<typename T> 144 const T& 145 min(const T& a, const T& b) 146 { return (a < b) ? a : b; } 147 148 /** @brief Equivalent to std::max. */ 149 template<typename T> 150 const T& 151 max(const T& a, const T& b) 152 { return (a > b) ? a : b; } 153 154 /** @brief Constructs predicate for equality from strict weak 155 * ordering predicate 156 */ 157 // XXX comparator at the end, as per others 158 template<typename Comparator, typename T1, typename T2> 159 class equal_from_less : public std::binary_function<T1, T2, bool> 160 { 161 private: 162 Comparator& comp; 163 164 public: 165 equal_from_less(Comparator& _comp) : comp(_comp) { } 166 167 bool operator()(const T1& a, const T2& b) 168 { 169 return !comp(a, b) && !comp(b, a); 170 } 171 }; 172 173 174 /** @brief Similar to std::binder1st, 175 * but giving the argument types explicitly. */ 176 template<typename _Predicate, typename argument_type> 177 class unary_negate 178 : public std::unary_function<argument_type, bool> 179 { 180 protected: 181 _Predicate _M_pred; 182 183 public: 184 explicit 185 unary_negate(const _Predicate& __x) : _M_pred(__x) { } 186 187 bool 188 operator()(const argument_type& __x) 189 { return !_M_pred(__x); } 190 }; 191 192 /** @brief Similar to std::binder1st, 193 * but giving the argument types explicitly. */ 194 template<typename _Operation, typename first_argument_type, 195 typename second_argument_type, typename result_type> 196 class binder1st 197 : public std::unary_function<second_argument_type, result_type> 198 { 199 protected: 200 _Operation op; 201 first_argument_type value; 202 203 public: 204 binder1st(const _Operation& __x, 205 const first_argument_type& __y) 206 : op(__x), value(__y) { } 207 208 result_type 209 operator()(const second_argument_type& __x) 210 { return op(value, __x); } 211 212 // _GLIBCXX_RESOLVE_LIB_DEFECTS 213 // 109. Missing binders for non-const sequence elements 214 result_type 215 operator()(second_argument_type& __x) const 216 { return op(value, __x); } 217 }; 218 219 /** 220 * @brief Similar to std::binder2nd, but giving the argument types 221 * explicitly. 222 */ 223 template<typename _Operation, typename first_argument_type, 224 typename second_argument_type, typename result_type> 225 class binder2nd 226 : public std::unary_function<first_argument_type, result_type> 227 { 228 protected: 229 _Operation op; 230 second_argument_type value; 231 232 public: 233 binder2nd(const _Operation& __x, 234 const second_argument_type& __y) 235 : op(__x), value(__y) { } 236 237 result_type 238 operator()(const first_argument_type& __x) const 239 { return op(__x, value); } 240 241 // _GLIBCXX_RESOLVE_LIB_DEFECTS 242 // 109. Missing binders for non-const sequence elements 243 result_type 244 operator()(first_argument_type& __x) 245 { return op(__x, value); } 246 }; 247 248 /** @brief Similar to std::equal_to, but allows two different types. */ 249 template<typename T1, typename T2> 250 struct equal_to : std::binary_function<T1, T2, bool> 251 { 252 bool operator()(const T1& t1, const T2& t2) const 253 { return t1 == t2; } 254 }; 255 256 /** @brief Similar to std::less, but allows two different types. */ 257 template<typename T1, typename T2> 258 struct less : std::binary_function<T1, T2, bool> 259 { 260 bool 261 operator()(const T1& t1, const T2& t2) const 262 { return t1 < t2; } 263 264 bool 265 operator()(const T2& t2, const T1& t1) const 266 { return t2 < t1; } 267 }; 268 269 // Partial specialization for one type. Same as std::less. 270 template<typename _Tp> 271 struct less<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, bool> 272 { 273 bool 274 operator()(const _Tp& __x, const _Tp& __y) const 275 { return __x < __y; } 276 }; 277 278 279 /** @brief Similar to std::plus, but allows two different types. */ 280 template<typename _Tp1, typename _Tp2> 281 struct plus : public std::binary_function<_Tp1, _Tp2, _Tp1> 282 { 283 typedef __typeof__(*static_cast<_Tp1*>(NULL) 284 + *static_cast<_Tp2*>(NULL)) result; 285 286 result 287 operator()(const _Tp1& __x, const _Tp2& __y) const 288 { return __x + __y; } 289 }; 290 291 // Partial specialization for one type. Same as std::plus. 292 template<typename _Tp> 293 struct plus<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp> 294 { 295 typedef __typeof__(*static_cast<_Tp*>(NULL) 296 + *static_cast<_Tp*>(NULL)) result; 297 298 result 299 operator()(const _Tp& __x, const _Tp& __y) const 300 { return __x + __y; } 301 }; 302 303 304 /** @brief Similar to std::multiplies, but allows two different types. */ 305 template<typename _Tp1, typename _Tp2> 306 struct multiplies : public std::binary_function<_Tp1, _Tp2, _Tp1> 307 { 308 typedef __typeof__(*static_cast<_Tp1*>(NULL) 309 * *static_cast<_Tp2*>(NULL)) result; 310 311 result 312 operator()(const _Tp1& __x, const _Tp2& __y) const 313 { return __x * __y; } 314 }; 315 316 // Partial specialization for one type. Same as std::multiplies. 317 template<typename _Tp> 318 struct multiplies<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp> 319 { 320 typedef __typeof__(*static_cast<_Tp*>(NULL) 321 * *static_cast<_Tp*>(NULL)) result; 322 323 result 324 operator()(const _Tp& __x, const _Tp& __y) const 325 { return __x * __y; } 326 }; 327 328 329 template<typename T, typename _DifferenceTp> 330 class pseudo_sequence; 331 332 /** @brief Iterator associated with __gnu_parallel::pseudo_sequence. 333 * If features the usual random-access iterator functionality. 334 * @param T Sequence value type. 335 * @param difference_type Sequence difference type. 336 */ 337 template<typename T, typename _DifferenceTp> 338 class pseudo_sequence_iterator 339 { 340 public: 341 typedef _DifferenceTp difference_type; 342 343 private: 344 typedef pseudo_sequence_iterator<T, _DifferenceTp> type; 345 346 const T& val; 347 difference_type pos; 348 349 public: 350 pseudo_sequence_iterator(const T& val, difference_type pos) 351 : val(val), pos(pos) { } 352 353 // Pre-increment operator. 354 type& 355 operator++() 356 { 357 ++pos; 358 return *this; 359 } 360 361 // Post-increment operator. 362 const type 363 operator++(int) 364 { return type(pos++); } 365 366 const T& 367 operator*() const 368 { return val; } 369 370 const T& 371 operator[](difference_type) const 372 { return val; } 373 374 bool 375 operator==(const type& i2) 376 { return pos == i2.pos; } 377 378 difference_type 379 operator!=(const type& i2) 380 { return pos != i2.pos; } 381 382 difference_type 383 operator-(const type& i2) 384 { return pos - i2.pos; } 385 }; 386 387 /** @brief Sequence that conceptually consists of multiple copies of 388 the same element. 389 * The copies are not stored explicitly, of course. 390 * @param T Sequence value type. 391 * @param difference_type Sequence difference type. 392 */ 393 template<typename T, typename _DifferenceTp> 394 class pseudo_sequence 395 { 396 typedef pseudo_sequence<T, _DifferenceTp> type; 397 398 public: 399 typedef _DifferenceTp difference_type; 400 401 // Better case down to uint64, than up to _DifferenceTp. 402 typedef pseudo_sequence_iterator<T, uint64> iterator; 403 404 /** @brief Constructor. 405 * @param val Element of the sequence. 406 * @param count Number of (virtual) copies. 407 */ 408 pseudo_sequence(const T& val, difference_type count) 409 : val(val), count(count) { } 410 411 /** @brief Begin iterator. */ 412 iterator 413 begin() const 414 { return iterator(val, 0); } 415 416 /** @brief End iterator. */ 417 iterator 418 end() const 419 { return iterator(val, count); } 420 421 private: 422 const T& val; 423 difference_type count; 424 }; 425 426 /** @brief Functor that does nothing */ 427 template<typename _ValueTp> 428 class void_functor 429 { 430 inline void 431 operator()(const _ValueTp& v) const { } 432 }; 433 434 /** @brief Compute the median of three referenced elements, 435 according to @c comp. 436 * @param a First iterator. 437 * @param b Second iterator. 438 * @param c Third iterator. 439 * @param comp Comparator. 440 */ 441 template<typename RandomAccessIterator, typename Comparator> 442 RandomAccessIterator 443 median_of_three_iterators(RandomAccessIterator a, RandomAccessIterator b, 444 RandomAccessIterator c, Comparator& comp) 445 { 446 if (comp(*a, *b)) 447 if (comp(*b, *c)) 448 return b; 449 else 450 if (comp(*a, *c)) 451 return c; 452 else 453 return a; 454 else 455 { 456 // Just swap a and b. 457 if (comp(*a, *c)) 458 return a; 459 else 460 if (comp(*b, *c)) 461 return c; 462 else 463 return b; 464 } 465 } 466 467 #define _GLIBCXX_PARALLEL_ASSERT(_Condition) __glibcxx_assert(_Condition) 468 469 } //namespace __gnu_parallel 470 471 #endif /* _GLIBCXX_PARALLEL_BASE_H */ 472
