]>
Commit | Line | Data |
---|---|---|
c2ba9709 JS |
1 | // -*- C++ -*- |
2 | ||
7adcbafe | 3 | // Copyright (C) 2007-2022 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 | ||
53567bbd PC |
35 | #include <bits/c++config.h> |
36 | #include <bits/stl_function.h> | |
ee1b5fc5 BK |
37 | #include <omp.h> |
38 | #include <parallel/features.h> | |
c2ba9709 JS |
39 | #include <parallel/basic_iterator.h> |
40 | #include <parallel/parallel.h> | |
c2ba9709 | 41 | |
847eb551 | 42 | // Parallel mode namespaces. |
939759fc BK |
43 | |
44 | /** | |
45 | * @namespace std::__parallel | |
46 | * @brief GNU parallel code, replaces standard behavior with parallel behavior. | |
47 | */ | |
12ffa228 | 48 | namespace std _GLIBCXX_VISIBILITY(default) |
847eb551 BK |
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 | 70 | #ifdef _GLIBCXX_PARALLEL |
12ffa228 | 71 | using namespace std::_GLIBCXX_STD_A; |
847eb551 BK |
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. | |
8b0c13a8 | 84 | inline _ThreadIndex |
1acba85b | 85 | __get_max_threads() |
ee1b5fc5 | 86 | { |
8b0c13a8 | 87 | _ThreadIndex __i = omp_get_max_threads(); |
ee1b5fc5 BK |
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 | ||
8e32aa11 | 96 | /** @brief Calculates the rounded-down logarithm of @c __n for base 2. |
338311e5 PC |
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) | |
c2ba9709 | 103 | { |
1acba85b JS |
104 | _Size __k; |
105 | for (__k = 0; __n > 1; __n >>= 1) | |
106 | ++__k; | |
107 | return __k; | |
c2ba9709 JS |
108 | } |
109 | ||
338311e5 | 110 | /** @brief Encode two integers into one gnu_parallel::_CASable. |
8e32aa11 | 111 | * @param __a First integer, to be encoded in the most-significant @c |
338311e5 PC |
112 | * _CASable_bits/2 bits. |
113 | * @param __b Second integer, to be encoded in the least-significant | |
8e32aa11 BK |
114 | * @c _CASable_bits/2 bits. |
115 | * @return value encoding @c __a and @c __b. | |
31380bc4 | 116 | * @see __decode2 |
338311e5 PC |
117 | */ |
118 | inline _CASable | |
119 | __encode2(int __a, int __b) //must all be non-negative, actually | |
c2ba9709 | 120 | { |
338311e5 PC |
121 | return (((_CASable)__a) << (_CASable_bits / 2)) | (((_CASable)__b) << 0); |
122 | } | |
c2ba9709 | 123 | |
338311e5 PC |
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 | |
8e32aa11 | 127 | * @c _CASable_bits/2 bits of @c __x. |
338311e5 | 128 | * @param __b Second integer, to be encoded in the least-significant |
8e32aa11 | 129 | * @c _CASable_bits/2 bits of @c __x. |
338311e5 PC |
130 | * @see __encode2 |
131 | */ | |
132 | inline void | |
31380bc4 | 133 | __decode2(_CASable __x, int& __a, int& __b) |
338311e5 PC |
134 | { |
135 | __a = (int)((__x >> (_CASable_bits / 2)) & _CASable_mask); | |
136 | __b = (int)((__x >> 0 ) & _CASable_mask); | |
137 | } | |
c2ba9709 | 138 | |
338311e5 | 139 | //needed for parallel "numeric", even if "algorithm" not included |
c2ba9709 | 140 | |
338311e5 PC |
141 | /** @brief Equivalent to std::min. */ |
142 | template<typename _Tp> | |
2d9ca17b | 143 | inline const _Tp& |
338311e5 PC |
144 | min(const _Tp& __a, const _Tp& __b) |
145 | { return (__a < __b) ? __a : __b; } | |
c2ba9709 | 146 | |
338311e5 PC |
147 | /** @brief Equivalent to std::max. */ |
148 | template<typename _Tp> | |
2d9ca17b | 149 | inline const _Tp& |
338311e5 PC |
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; | |
e683ee2a | 161 | |
338311e5 PC |
162 | public: |
163 | _EqualFromLess(_Compare& __comp) : _M_comp(__comp) { } | |
0e6c9eaa | 164 | |
338311e5 PC |
165 | bool operator()(const _T1& __a, const _T2& __b) |
166 | { return !_M_comp(__a, __b) && !_M_comp(__b, __a); } | |
167 | }; | |
c2ba9709 | 168 | |
0e6c9eaa | 169 | |
4d62f1d0 | 170 | /** @brief Similar to std::unary_negate, |
338311e5 PC |
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> | |
31380bc4 | 220 | class __binder2nd |
338311e5 PC |
221 | : public std::unary_function<_FirstArgumentType, _ResultType> |
222 | { | |
223 | protected: | |
224 | _Operation _M_op; | |
225 | _SecondArgumentType _M_value; | |
226 | ||
227 | public: | |
31380bc4 | 228 | __binder2nd(const _Operation& __x, const _SecondArgumentType& __y) |
338311e5 PC |
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 | }; | |
0e6c9eaa | 249 | |
338311e5 PC |
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> | |
2305a1e8 PC |
265 | struct _Less<_Tp, _Tp> |
266 | : public std::less<_Tp> { }; | |
0e6c9eaa | 267 | |
338311e5 | 268 | /** @brief Similar to std::plus, but allows two different types. */ |
2305a1e8 | 269 | template<typename _Tp1, typename _Tp2, typename _Result |
8fc81078 PC |
270 | = __typeof__(*static_cast<_Tp1*>(0) |
271 | + *static_cast<_Tp2*>(0))> | |
2305a1e8 | 272 | struct _Plus : public std::binary_function<_Tp1, _Tp2, _Result> |
338311e5 | 273 | { |
2305a1e8 | 274 | _Result |
338311e5 PC |
275 | operator()(const _Tp1& __x, const _Tp2& __y) const |
276 | { return __x + __y; } | |
277 | }; | |
0e6c9eaa | 278 | |
338311e5 PC |
279 | // Partial specialization for one type. Same as std::plus. |
280 | template<typename _Tp> | |
2305a1e8 PC |
281 | struct _Plus<_Tp, _Tp, _Tp> |
282 | : public std::plus<_Tp> { }; | |
0e6c9eaa | 283 | |
338311e5 | 284 | /** @brief Similar to std::multiplies, but allows two different types. */ |
2305a1e8 | 285 | template<typename _Tp1, typename _Tp2, typename _Result |
8fc81078 PC |
286 | = __typeof__(*static_cast<_Tp1*>(0) |
287 | * *static_cast<_Tp2*>(0))> | |
2305a1e8 | 288 | struct _Multiplies : public std::binary_function<_Tp1, _Tp2, _Result> |
338311e5 | 289 | { |
2305a1e8 | 290 | _Result |
338311e5 PC |
291 | operator()(const _Tp1& __x, const _Tp2& __y) const |
292 | { return __x * __y; } | |
293 | }; | |
0e6c9eaa | 294 | |
338311e5 PC |
295 | // Partial specialization for one type. Same as std::multiplies. |
296 | template<typename _Tp> | |
2305a1e8 PC |
297 | struct _Multiplies<_Tp, _Tp, _Tp> |
298 | : public std::multiplies<_Tp> { }; | |
c2ba9709 | 299 | |
338311e5 PC |
300 | /** @brief _Iterator associated with __gnu_parallel::_PseudoSequence. |
301 | * If features the usual random-access iterator functionality. | |
302 | * @param _Tp Sequence _M_value type. | |
2d9ca17b | 303 | * @param _DifferenceTp Sequence difference type. |
338311e5 PC |
304 | */ |
305 | template<typename _Tp, typename _DifferenceTp> | |
306 | class _PseudoSequenceIterator | |
c2ba9709 | 307 | { |
338311e5 PC |
308 | public: |
309 | typedef _DifferenceTp _DifferenceType; | |
c2ba9709 | 310 | |
338311e5 PC |
311 | _PseudoSequenceIterator(const _Tp& __val, _DifferenceType __pos) |
312 | : _M_val(__val), _M_pos(__pos) { } | |
c2ba9709 | 313 | |
338311e5 PC |
314 | // Pre-increment operator. |
315 | _PseudoSequenceIterator& | |
316 | operator++() | |
317 | { | |
318 | ++_M_pos; | |
319 | return *this; | |
320 | } | |
c2ba9709 | 321 | |
338311e5 | 322 | // Post-increment operator. |
57fd5f95 | 323 | _PseudoSequenceIterator |
338311e5 PC |
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 | ||
57fd5f95 | 339 | bool |
338311e5 PC |
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; } | |
57fd5f95 PC |
346 | |
347 | private: | |
348 | const _Tp& _M_val; | |
349 | _DifferenceType _M_pos; | |
338311e5 PC |
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. | |
2d9ca17b | 356 | * @param _DifferenceTp Sequence difference type. |
e683ee2a | 357 | */ |
338311e5 PC |
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. | |
93c66bc6 | 368 | * @param __val Element of the sequence. |
338311e5 PC |
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 | ||
338311e5 | 389 | /** @brief Compute the median of three referenced elements, |
8e32aa11 | 390 | according to @c __comp. |
338311e5 PC |
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, | |
57fd5f95 | 399 | _RAIter __c, _Compare __comp) |
338311e5 PC |
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; | |
c2ba9709 | 409 | else |
338311e5 PC |
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 | } | |
c2ba9709 | 421 | |
eae0b895 | 422 | #if _GLIBCXX_PARALLEL_ASSERTIONS && defined(__glibcxx_assert_impl) |
10f51543 JW |
423 | # define _GLIBCXX_PARALLEL_ASSERT(_Condition) \ |
424 | do { __glibcxx_assert_impl(_Condition); } while (false) | |
eae0b895 | 425 | #else |
10f51543 | 426 | # define _GLIBCXX_PARALLEL_ASSERT(_Condition) do { } while (false) |
eae0b895 | 427 | #endif |
e683ee2a | 428 | |
c2ba9709 JS |
429 | } //namespace __gnu_parallel |
430 | ||
cbcd1e45 | 431 | #endif /* _GLIBCXX_PARALLEL_BASE_H */ |