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