]>
Commit | Line | Data |
---|---|---|
c2ba9709 JS |
1 | // -*- C++ -*- |
2 | ||
748086b7 | 3 | // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. |
c2ba9709 JS |
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 | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
c2ba9709 JS |
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 | ||
748086b7 JJ |
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. | |
c2ba9709 | 19 | |
748086b7 JJ |
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/>. | |
c2ba9709 JS |
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 | ||
c2ba9709 | 35 | #include <functional> |
ee1b5fc5 BK |
36 | #include <omp.h> |
37 | #include <parallel/features.h> | |
c2ba9709 JS |
38 | #include <parallel/basic_iterator.h> |
39 | #include <parallel/parallel.h> | |
c2ba9709 | 40 | |
847eb551 BK |
41 | |
42 | // Parallel mode namespaces. | |
939759fc BK |
43 | |
44 | /** | |
45 | * @namespace std::__parallel | |
46 | * @brief GNU parallel code, replaces standard behavior with parallel behavior. | |
47 | */ | |
847eb551 BK |
48 | namespace std |
49 | { | |
50 | namespace __parallel { } | |
51 | } | |
52 | ||
53 | /** | |
54 | * @namespace __gnu_parallel | |
939759fc | 55 | * @brief GNU parallel code for public use. |
847eb551 BK |
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 | { | |
ee1b5fc5 | 69 | // Import whatever is the serial version. |
847eb551 BK |
70 | #ifdef _GLIBCXX_PARALLEL |
71 | using namespace std::__norm; | |
72 | #else | |
73 | using namespace std; | |
74 | #endif | |
75 | } | |
76 | ||
77 | ||
c2ba9709 JS |
78 | namespace __gnu_parallel |
79 | { | |
ee1b5fc5 BK |
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 | |
1acba85b | 85 | __get_max_threads() |
ee1b5fc5 BK |
86 | { |
87 | int __i = omp_get_max_threads(); | |
88 | return __i > 1 ? __i : 1; | |
89 | } | |
90 | ||
3b06118a | 91 | |
ee1b5fc5 | 92 | inline bool |
1acba85b | 93 | __is_parallel(const _Parallelism __p) { return __p != sequential; } |
ee1b5fc5 BK |
94 | |
95 | ||
1acba85b JS |
96 | /** @brief Calculates the rounded-down logarithm of @__c __n for base 2. |
97 | * @param __n Argument. | |
c38b84d8 | 98 | * @return Returns 0 for any argument <1. |
e683ee2a | 99 | */ |
1acba85b JS |
100 | template<typename _Size> |
101 | inline _Size | |
4459d22e | 102 | __rd_log2(_Size __n) |
c2ba9709 | 103 | { |
1acba85b JS |
104 | _Size __k; |
105 | for (__k = 0; __n > 1; __n >>= 1) | |
106 | ++__k; | |
107 | return __k; | |
c2ba9709 JS |
108 | } |
109 | ||
721641c4 | 110 | /** @brief Encode two integers into one gnu_parallel::_CASable. |
1acba85b JS |
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. | |
4459d22e | 115 | * @return value encoding @__c __a and @__c __b. |
e683ee2a JS |
116 | * @see decode2 |
117 | */ | |
1acba85b | 118 | inline _CASable |
15ac3c72 | 119 | __encode2(int __a, int __b) //must all be non-negative, actually |
e683ee2a | 120 | { |
1acba85b | 121 | return (((_CASable)__a) << (_CASable_bits / 2)) | (((_CASable)__b) << 0); |
e683ee2a JS |
122 | } |
123 | ||
721641c4 | 124 | /** @brief Decode two integers from one gnu_parallel::_CASable. |
1acba85b JS |
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 | |
e683ee2a JS |
131 | */ |
132 | inline void | |
1acba85b | 133 | decode2(_CASable __x, int& __a, int& __b) |
e683ee2a | 134 | { |
1acba85b JS |
135 | __a = (int)((__x >> (_CASable_bits / 2)) & _CASable_mask); |
136 | __b = (int)((__x >> 0 ) & _CASable_mask); | |
e683ee2a JS |
137 | } |
138 | ||
3b06118a JS |
139 | //needed for parallel "numeric", even if "algorithm" not included |
140 | ||
e683ee2a | 141 | /** @brief Equivalent to std::min. */ |
1acba85b JS |
142 | template<typename _Tp> |
143 | const _Tp& | |
144 | min(const _Tp& __a, const _Tp& __b) | |
145 | { return (__a < __b) ? __a : __b; } | |
c2ba9709 | 146 | |
e683ee2a | 147 | /** @brief Equivalent to std::max. */ |
1acba85b JS |
148 | template<typename _Tp> |
149 | const _Tp& | |
150 | max(const _Tp& __a, const _Tp& __b) | |
151 | { return (__a > __b) ? __a : __b; } | |
c2ba9709 | 152 | |
e683ee2a JS |
153 | /** @brief Constructs predicate for equality from strict weak |
154 | * ordering predicate | |
155 | */ | |
2a2e7f9d | 156 | template<typename _T1, typename _T2, typename _Compare> |
1acba85b | 157 | class _EqualFromLess : public std::binary_function<_T1, _T2, bool> |
c2ba9709 JS |
158 | { |
159 | private: | |
54384f7f | 160 | _Compare& _M_comp; |
c2ba9709 JS |
161 | |
162 | public: | |
54384f7f | 163 | _EqualFromLess(_Compare& __comp) : _M_comp(__comp) { } |
c2ba9709 | 164 | |
1acba85b | 165 | bool operator()(const _T1& __a, const _T2& __b) |
c2ba9709 | 166 | { |
54384f7f | 167 | return !_M_comp(__a, __b) && !_M_comp(__b, __a); |
c2ba9709 JS |
168 | } |
169 | }; | |
170 | ||
171 | ||
4459d22e | 172 | /** @brief Similar to std::binder1st, |
e683ee2a JS |
173 | * but giving the argument types explicitly. */ |
174 | template<typename _Predicate, typename argument_type> | |
1acba85b | 175 | class __unary_negate |
e683ee2a JS |
176 | : public std::unary_function<argument_type, bool> |
177 | { | |
178 | protected: | |
179 | _Predicate _M_pred; | |
180 | ||
181 | public: | |
182 | explicit | |
1acba85b | 183 | __unary_negate(const _Predicate& __x) : _M_pred(__x) { } |
e683ee2a JS |
184 | |
185 | bool | |
186 | operator()(const argument_type& __x) | |
187 | { return !_M_pred(__x); } | |
188 | }; | |
189 | ||
4459d22e | 190 | /** @brief Similar to std::binder1st, |
e683ee2a | 191 | * but giving the argument types explicitly. */ |
1acba85b | 192 | template<typename _Operation, typename _FirstArgumentType, |
15ac3c72 | 193 | typename _SecondArgumentType, typename _ResultType> |
1acba85b JS |
194 | class __binder1st |
195 | : public std::unary_function<_SecondArgumentType, _ResultType> | |
e683ee2a JS |
196 | { |
197 | protected: | |
1acba85b JS |
198 | _Operation _M_op; |
199 | _FirstArgumentType _M_value; | |
e683ee2a JS |
200 | |
201 | public: | |
1acba85b JS |
202 | __binder1st(const _Operation& __x, |
203 | const _FirstArgumentType& __y) | |
204 | : _M_op(__x), _M_value(__y) { } | |
e683ee2a | 205 | |
1acba85b JS |
206 | _ResultType |
207 | operator()(const _SecondArgumentType& __x) | |
208 | { return _M_op(_M_value, __x); } | |
e683ee2a JS |
209 | |
210 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
721641c4 | 211 | // 109. Missing binders for non-const sequence elements |
1acba85b JS |
212 | _ResultType |
213 | operator()(_SecondArgumentType& __x) const | |
214 | { return _M_op(_M_value, __x); } | |
e683ee2a JS |
215 | }; |
216 | ||
217 | /** | |
218 | * @brief Similar to std::binder2nd, but giving the argument types | |
219 | * explicitly. | |
220 | */ | |
1acba85b | 221 | template<typename _Operation, typename _FirstArgumentType, |
15ac3c72 | 222 | typename _SecondArgumentType, typename _ResultType> |
e683ee2a | 223 | class binder2nd |
1acba85b | 224 | : public std::unary_function<_FirstArgumentType, _ResultType> |
e683ee2a JS |
225 | { |
226 | protected: | |
1acba85b JS |
227 | _Operation _M_op; |
228 | _SecondArgumentType _M_value; | |
e683ee2a JS |
229 | |
230 | public: | |
231 | binder2nd(const _Operation& __x, | |
1acba85b JS |
232 | const _SecondArgumentType& __y) |
233 | : _M_op(__x), _M_value(__y) { } | |
e683ee2a | 234 | |
1acba85b JS |
235 | _ResultType |
236 | operator()(const _FirstArgumentType& __x) const | |
237 | { return _M_op(__x, _M_value); } | |
e683ee2a JS |
238 | |
239 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
721641c4 | 240 | // 109. Missing binders for non-const sequence elements |
1acba85b JS |
241 | _ResultType |
242 | operator()(_FirstArgumentType& __x) | |
243 | { return _M_op(__x, _M_value); } | |
e683ee2a JS |
244 | }; |
245 | ||
246 | /** @brief Similar to std::equal_to, but allows two different types. */ | |
1acba85b | 247 | template<typename _T1, typename _T2> |
4459d22e | 248 | struct _EqualTo : std::binary_function<_T1, _T2, bool> |
0e6c9eaa | 249 | { |
1acba85b JS |
250 | bool operator()(const _T1& __t1, const _T2& __t2) const |
251 | { return __t1 == __t2; } | |
0e6c9eaa JS |
252 | }; |
253 | ||
e683ee2a | 254 | /** @brief Similar to std::less, but allows two different types. */ |
1acba85b JS |
255 | template<typename _T1, typename _T2> |
256 | struct _Less : std::binary_function<_T1, _T2, bool> | |
c2ba9709 | 257 | { |
e683ee2a | 258 | bool |
1acba85b JS |
259 | operator()(const _T1& __t1, const _T2& __t2) const |
260 | { return __t1 < __t2; } | |
c5654e49 | 261 | |
e683ee2a | 262 | bool |
1acba85b JS |
263 | operator()(const _T2& __t2, const _T1& __t1) const |
264 | { return __t2 < __t1; } | |
c2ba9709 JS |
265 | }; |
266 | ||
e683ee2a JS |
267 | // Partial specialization for one type. Same as std::less. |
268 | template<typename _Tp> | |
1acba85b | 269 | struct _Less<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, bool> |
e683ee2a JS |
270 | { |
271 | bool | |
272 | operator()(const _Tp& __x, const _Tp& __y) const | |
273 | { return __x < __y; } | |
274 | }; | |
c2ba9709 | 275 | |
0e6c9eaa | 276 | |
e683ee2a JS |
277 | /** @brief Similar to std::plus, but allows two different types. */ |
278 | template<typename _Tp1, typename _Tp2> | |
1acba85b | 279 | struct _Plus : public std::binary_function<_Tp1, _Tp2, _Tp1> |
e683ee2a | 280 | { |
2dcc0099 | 281 | typedef __typeof__(*static_cast<_Tp1*>(NULL) |
15ac3c72 | 282 | + *static_cast<_Tp2*>(NULL)) __result; |
0e6c9eaa | 283 | |
1acba85b | 284 | __result |
e683ee2a JS |
285 | operator()(const _Tp1& __x, const _Tp2& __y) const |
286 | { return __x + __y; } | |
287 | }; | |
0e6c9eaa | 288 | |
e683ee2a JS |
289 | // Partial specialization for one type. Same as std::plus. |
290 | template<typename _Tp> | |
1acba85b | 291 | struct _Plus<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp> |
e683ee2a | 292 | { |
2dcc0099 | 293 | typedef __typeof__(*static_cast<_Tp*>(NULL) |
15ac3c72 | 294 | + *static_cast<_Tp*>(NULL)) __result; |
0e6c9eaa | 295 | |
1acba85b | 296 | __result |
e683ee2a JS |
297 | operator()(const _Tp& __x, const _Tp& __y) const |
298 | { return __x + __y; } | |
299 | }; | |
0e6c9eaa JS |
300 | |
301 | ||
e683ee2a JS |
302 | /** @brief Similar to std::multiplies, but allows two different types. */ |
303 | template<typename _Tp1, typename _Tp2> | |
1acba85b | 304 | struct _Multiplies : public std::binary_function<_Tp1, _Tp2, _Tp1> |
e683ee2a | 305 | { |
2dcc0099 | 306 | typedef __typeof__(*static_cast<_Tp1*>(NULL) |
15ac3c72 | 307 | * *static_cast<_Tp2*>(NULL)) __result; |
0e6c9eaa | 308 | |
1acba85b | 309 | __result |
e683ee2a JS |
310 | operator()(const _Tp1& __x, const _Tp2& __y) const |
311 | { return __x * __y; } | |
312 | }; | |
0e6c9eaa | 313 | |
e683ee2a JS |
314 | // Partial specialization for one type. Same as std::multiplies. |
315 | template<typename _Tp> | |
1acba85b | 316 | struct _Multiplies<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp> |
e683ee2a | 317 | { |
2dcc0099 | 318 | typedef __typeof__(*static_cast<_Tp*>(NULL) |
15ac3c72 | 319 | * *static_cast<_Tp*>(NULL)) __result; |
0e6c9eaa | 320 | |
1acba85b | 321 | __result |
e683ee2a JS |
322 | operator()(const _Tp& __x, const _Tp& __y) const |
323 | { return __x * __y; } | |
324 | }; | |
0e6c9eaa JS |
325 | |
326 | ||
1acba85b JS |
327 | template<typename _Tp, typename _DifferenceTp> |
328 | class _PseudoSequence; | |
c2ba9709 | 329 | |
1acba85b | 330 | /** @brief _Iterator associated with __gnu_parallel::_PseudoSequence. |
e683ee2a | 331 | * If features the usual random-access iterator functionality. |
1acba85b JS |
332 | * @param _Tp Sequence _M_value type. |
333 | * @param _DifferenceType Sequence difference type. | |
e683ee2a | 334 | */ |
1acba85b JS |
335 | template<typename _Tp, typename _DifferenceTp> |
336 | class _PseudoSequenceIterator | |
c2ba9709 JS |
337 | { |
338 | public: | |
1acba85b | 339 | typedef _DifferenceTp _DifferenceType; |
c2ba9709 JS |
340 | |
341 | private: | |
1acba85b JS |
342 | const _Tp& _M_val; |
343 | _DifferenceType _M_pos; | |
c2ba9709 JS |
344 | |
345 | public: | |
1acba85b JS |
346 | _PseudoSequenceIterator(const _Tp& _M_val, _DifferenceType _M_pos) |
347 | : _M_val(_M_val), _M_pos(_M_pos) { } | |
c2ba9709 JS |
348 | |
349 | // Pre-increment operator. | |
11b9c936 | 350 | _PseudoSequenceIterator& |
c2ba9709 JS |
351 | operator++() |
352 | { | |
1acba85b | 353 | ++_M_pos; |
c2ba9709 JS |
354 | return *this; |
355 | } | |
356 | ||
357 | // Post-increment operator. | |
11b9c936 | 358 | const _PseudoSequenceIterator |
c2ba9709 | 359 | operator++(int) |
11b9c936 | 360 | { return _PseudoSequenceIterator(_M_pos++); } |
c2ba9709 | 361 | |
1acba85b | 362 | const _Tp& |
c2ba9709 | 363 | operator*() const |
1acba85b | 364 | { return _M_val; } |
c2ba9709 | 365 | |
1acba85b JS |
366 | const _Tp& |
367 | operator[](_DifferenceType) const | |
368 | { return _M_val; } | |
c2ba9709 | 369 | |
e683ee2a | 370 | bool |
11b9c936 | 371 | operator==(const _PseudoSequenceIterator& __i2) |
1acba85b | 372 | { return _M_pos == __i2._M_pos; } |
c2ba9709 | 373 | |
1acba85b | 374 | _DifferenceType |
11b9c936 | 375 | operator!=(const _PseudoSequenceIterator& __i2) |
1acba85b | 376 | { return _M_pos != __i2._M_pos; } |
c2ba9709 | 377 | |
1acba85b | 378 | _DifferenceType |
11b9c936 | 379 | operator-(const _PseudoSequenceIterator& __i2) |
1acba85b | 380 | { return _M_pos - __i2._M_pos; } |
c2ba9709 JS |
381 | }; |
382 | ||
e683ee2a JS |
383 | /** @brief Sequence that conceptually consists of multiple copies of |
384 | the same element. | |
385 | * The copies are not stored explicitly, of course. | |
1acba85b JS |
386 | * @param _Tp Sequence _M_value type. |
387 | * @param _DifferenceType Sequence difference type. | |
e683ee2a | 388 | */ |
1acba85b JS |
389 | template<typename _Tp, typename _DifferenceTp> |
390 | class _PseudoSequence | |
c2ba9709 | 391 | { |
c2ba9709 | 392 | public: |
1acba85b | 393 | typedef _DifferenceTp _DifferenceType; |
c5654e49 | 394 | |
63ffc486 JS |
395 | // Better cast down to uint64_t, than up to _DifferenceTp. |
396 | typedef _PseudoSequenceIterator<_Tp, uint64_t> iterator; | |
c2ba9709 JS |
397 | |
398 | /** @brief Constructor. | |
1acba85b JS |
399 | * @param _M_val Element of the sequence. |
400 | * @param __count Number of (virtual) copies. | |
e683ee2a | 401 | */ |
1acba85b JS |
402 | _PseudoSequence(const _Tp& _M_val, _DifferenceType __count) |
403 | : _M_val(_M_val), __count(__count) { } | |
c2ba9709 JS |
404 | |
405 | /** @brief Begin iterator. */ | |
406 | iterator | |
407 | begin() const | |
1acba85b | 408 | { return iterator(_M_val, 0); } |
c2ba9709 JS |
409 | |
410 | /** @brief End iterator. */ | |
411 | iterator | |
412 | end() const | |
1acba85b | 413 | { return iterator(_M_val, __count); } |
c2ba9709 JS |
414 | |
415 | private: | |
1acba85b JS |
416 | const _Tp& _M_val; |
417 | _DifferenceType __count; | |
c2ba9709 JS |
418 | }; |
419 | ||
e683ee2a JS |
420 | /** @brief Functor that does nothing */ |
421 | template<typename _ValueTp> | |
1acba85b | 422 | class _VoidFunctor |
c2ba9709 | 423 | { |
e683ee2a | 424 | inline void |
1acba85b | 425 | operator()(const _ValueTp& __v) const { } |
c2ba9709 JS |
426 | }; |
427 | ||
e683ee2a | 428 | /** @brief Compute the median of three referenced elements, |
1acba85b JS |
429 | according to @__c __comp. |
430 | * @param __a First iterator. | |
431 | * @param __b Second iterator. | |
432 | * @param __c Third iterator. | |
433 | * @param __comp Comparator. | |
e683ee2a | 434 | */ |
1acba85b JS |
435 | template<typename _RAIter, typename _Compare> |
436 | _RAIter | |
437 | __median_of_three_iterators(_RAIter __a, _RAIter __b, | |
438 | _RAIter __c, _Compare& __comp) | |
c2ba9709 | 439 | { |
1acba85b JS |
440 | if (__comp(*__a, *__b)) |
441 | if (__comp(*__b, *__c)) | |
442 | return __b; | |
c2ba9709 | 443 | else |
1acba85b JS |
444 | if (__comp(*__a, *__c)) |
445 | return __c; | |
e683ee2a | 446 | else |
1acba85b | 447 | return __a; |
c2ba9709 JS |
448 | else |
449 | { | |
1acba85b JS |
450 | // Just swap __a and __b. |
451 | if (__comp(*__a, *__c)) | |
452 | return __a; | |
e683ee2a | 453 | else |
1acba85b JS |
454 | if (__comp(*__b, *__c)) |
455 | return __c; | |
e683ee2a | 456 | else |
1acba85b | 457 | return __b; |
c2ba9709 JS |
458 | } |
459 | } | |
460 | ||
d4e1b072 | 461 | #define _GLIBCXX_PARALLEL_ASSERT(_Condition) __glibcxx_assert(_Condition) |
e683ee2a | 462 | |
c2ba9709 JS |
463 | } //namespace __gnu_parallel |
464 | ||
cbcd1e45 | 465 | #endif /* _GLIBCXX_PARALLEL_BASE_H */ |