3 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
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
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.
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.
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/>.
25 /** @file parallel/base.h
26 * @brief Sequential helper functions.
27 * This file is a GNU parallel extension to the Standard C++ Library.
30 // Written by Johannes Singler.
32 #ifndef _GLIBCXX_PARALLEL_BASE_H
33 #define _GLIBCXX_PARALLEL_BASE_H 1
37 #include <parallel/features.h>
38 #include <parallel/basic_iterator.h>
39 #include <parallel/parallel.h>
42 // Parallel mode namespaces.
45 * @namespace std::__parallel
46 * @brief GNU parallel code, replaces standard behavior with parallel behavior.
50 namespace __parallel { }
54 * @namespace __gnu_parallel
55 * @brief GNU parallel code for public use.
57 namespace __gnu_parallel
59 // Import all the parallel versions of components in namespace std.
60 using namespace std::__parallel;
64 * @namespace __gnu_sequential
65 * @brief GNU sequential classes for public use.
67 namespace __gnu_sequential
69 // Import whatever is the serial version.
70 #ifdef _GLIBCXX_PARALLEL
71 using namespace std::__norm;
78 namespace __gnu_parallel
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.
87 int __i = omp_get_max_threads();
88 return __i > 1 ? __i : 1;
93 __is_parallel(const _Parallelism __p) { return __p != sequential; }
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.
100 template<typename _Size>
105 for (__k = 0; __n > 1; __n >>= 1)
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.
119 __encode2(int __a, int __b) //must all be non-negative, actually
121 return (((_CASable)__a) << (_CASable_bits / 2)) | (((_CASable)__b) << 0);
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.
133 decode2(_CASable __x, int& __a, int& __b)
135 __a = (int)((__x >> (_CASable_bits / 2)) & _CASable_mask);
136 __b = (int)((__x >> 0 ) & _CASable_mask);
139 //needed for parallel "numeric", even if "algorithm" not included
141 /** @brief Equivalent to std::min. */
142 template<typename _Tp>
144 min(const _Tp& __a, const _Tp& __b)
145 { return (__a < __b) ? __a : __b; }
147 /** @brief Equivalent to std::max. */
148 template<typename _Tp>
150 max(const _Tp& __a, const _Tp& __b)
151 { return (__a > __b) ? __a : __b; }
153 /** @brief Constructs predicate for equality from strict weak
156 template<typename _T1, typename _T2, typename _Compare>
157 class _EqualFromLess : public std::binary_function<_T1, _T2, bool>
163 _EqualFromLess(_Compare& __comp) : _M_comp(__comp) { }
165 bool operator()(const _T1& __a, const _T2& __b)
167 return !_M_comp(__a, __b) && !_M_comp(__b, __a);
172 /** @brief Similar to std::binder1st,
173 * but giving the argument types explicitly. */
174 template<typename _Predicate, typename argument_type>
176 : public std::unary_function<argument_type, bool>
183 __unary_negate(const _Predicate& __x) : _M_pred(__x) { }
186 operator()(const argument_type& __x)
187 { return !_M_pred(__x); }
190 /** @brief Similar to std::binder1st,
191 * but giving the argument types explicitly. */
192 template<typename _Operation, typename _FirstArgumentType,
193 typename _SecondArgumentType, typename _ResultType>
195 : public std::unary_function<_SecondArgumentType, _ResultType>
199 _FirstArgumentType _M_value;
202 __binder1st(const _Operation& __x,
203 const _FirstArgumentType& __y)
204 : _M_op(__x), _M_value(__y) { }
207 operator()(const _SecondArgumentType& __x)
208 { return _M_op(_M_value, __x); }
210 // _GLIBCXX_RESOLVE_LIB_DEFECTS
211 // 109. Missing binders for non-const sequence elements
213 operator()(_SecondArgumentType& __x) const
214 { return _M_op(_M_value, __x); }
218 * @brief Similar to std::binder2nd, but giving the argument types
221 template<typename _Operation, typename _FirstArgumentType,
222 typename _SecondArgumentType, typename _ResultType>
224 : public std::unary_function<_FirstArgumentType, _ResultType>
228 _SecondArgumentType _M_value;
231 binder2nd(const _Operation& __x,
232 const _SecondArgumentType& __y)
233 : _M_op(__x), _M_value(__y) { }
236 operator()(const _FirstArgumentType& __x) const
237 { return _M_op(__x, _M_value); }
239 // _GLIBCXX_RESOLVE_LIB_DEFECTS
240 // 109. Missing binders for non-const sequence elements
242 operator()(_FirstArgumentType& __x)
243 { return _M_op(__x, _M_value); }
246 /** @brief Similar to std::equal_to, but allows two different types. */
247 template<typename _T1, typename _T2>
248 struct _EqualTo : std::binary_function<_T1, _T2, bool>
250 bool operator()(const _T1& __t1, const _T2& __t2) const
251 { return __t1 == __t2; }
254 /** @brief Similar to std::less, but allows two different types. */
255 template<typename _T1, typename _T2>
256 struct _Less : std::binary_function<_T1, _T2, bool>
259 operator()(const _T1& __t1, const _T2& __t2) const
260 { return __t1 < __t2; }
263 operator()(const _T2& __t2, const _T1& __t1) const
264 { return __t2 < __t1; }
267 // Partial specialization for one type. Same as std::less.
268 template<typename _Tp>
269 struct _Less<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, bool>
272 operator()(const _Tp& __x, const _Tp& __y) const
273 { return __x < __y; }
277 /** @brief Similar to std::plus, but allows two different types. */
278 template<typename _Tp1, typename _Tp2>
279 struct _Plus : public std::binary_function<_Tp1, _Tp2, _Tp1>
281 typedef __typeof__(*static_cast<_Tp1*>(NULL)
282 + *static_cast<_Tp2*>(NULL)) __result;
285 operator()(const _Tp1& __x, const _Tp2& __y) const
286 { return __x + __y; }
289 // Partial specialization for one type. Same as std::plus.
290 template<typename _Tp>
291 struct _Plus<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp>
293 typedef __typeof__(*static_cast<_Tp*>(NULL)
294 + *static_cast<_Tp*>(NULL)) __result;
297 operator()(const _Tp& __x, const _Tp& __y) const
298 { return __x + __y; }
302 /** @brief Similar to std::multiplies, but allows two different types. */
303 template<typename _Tp1, typename _Tp2>
304 struct _Multiplies : public std::binary_function<_Tp1, _Tp2, _Tp1>
306 typedef __typeof__(*static_cast<_Tp1*>(NULL)
307 * *static_cast<_Tp2*>(NULL)) __result;
310 operator()(const _Tp1& __x, const _Tp2& __y) const
311 { return __x * __y; }
314 // Partial specialization for one type. Same as std::multiplies.
315 template<typename _Tp>
316 struct _Multiplies<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp>
318 typedef __typeof__(*static_cast<_Tp*>(NULL)
319 * *static_cast<_Tp*>(NULL)) __result;
322 operator()(const _Tp& __x, const _Tp& __y) const
323 { return __x * __y; }
327 template<typename _Tp, typename _DifferenceTp>
328 class _PseudoSequence;
330 /** @brief _Iterator associated with __gnu_parallel::_PseudoSequence.
331 * If features the usual random-access iterator functionality.
332 * @param _Tp Sequence _M_value type.
333 * @param _DifferenceType Sequence difference type.
335 template<typename _Tp, typename _DifferenceTp>
336 class _PseudoSequenceIterator
339 typedef _DifferenceTp _DifferenceType;
343 _DifferenceType _M_pos;
346 _PseudoSequenceIterator(const _Tp& _M_val, _DifferenceType _M_pos)
347 : _M_val(_M_val), _M_pos(_M_pos) { }
349 // Pre-increment operator.
350 _PseudoSequenceIterator&
357 // Post-increment operator.
358 const _PseudoSequenceIterator
360 { return _PseudoSequenceIterator(_M_pos++); }
367 operator[](_DifferenceType) const
371 operator==(const _PseudoSequenceIterator& __i2)
372 { return _M_pos == __i2._M_pos; }
375 operator!=(const _PseudoSequenceIterator& __i2)
376 { return _M_pos != __i2._M_pos; }
379 operator-(const _PseudoSequenceIterator& __i2)
380 { return _M_pos - __i2._M_pos; }
383 /** @brief Sequence that conceptually consists of multiple copies of
385 * The copies are not stored explicitly, of course.
386 * @param _Tp Sequence _M_value type.
387 * @param _DifferenceType Sequence difference type.
389 template<typename _Tp, typename _DifferenceTp>
390 class _PseudoSequence
393 typedef _DifferenceTp _DifferenceType;
395 // Better case down to uint64, than up to _DifferenceTp.
396 typedef _PseudoSequenceIterator<_Tp, uint64> iterator;
398 /** @brief Constructor.
399 * @param _M_val Element of the sequence.
400 * @param __count Number of (virtual) copies.
402 _PseudoSequence(const _Tp& _M_val, _DifferenceType __count)
403 : _M_val(_M_val), __count(__count) { }
405 /** @brief Begin iterator. */
408 { return iterator(_M_val, 0); }
410 /** @brief End iterator. */
413 { return iterator(_M_val, __count); }
417 _DifferenceType __count;
420 /** @brief Functor that does nothing */
421 template<typename _ValueTp>
425 operator()(const _ValueTp& __v) const { }
428 /** @brief Compute the median of three referenced elements,
429 according to @__c __comp.
430 * @param __a First iterator.
431 * @param __b Second iterator.
432 * @param __c Third iterator.
433 * @param __comp Comparator.
435 template<typename _RAIter, typename _Compare>
437 __median_of_three_iterators(_RAIter __a, _RAIter __b,
438 _RAIter __c, _Compare& __comp)
440 if (__comp(*__a, *__b))
441 if (__comp(*__b, *__c))
444 if (__comp(*__a, *__c))
450 // Just swap __a and __b.
451 if (__comp(*__a, *__c))
454 if (__comp(*__b, *__c))
461 #define _GLIBCXX_PARALLEL_ASSERT(_Condition) __glibcxx_assert(_Condition)
463 } //namespace __gnu_parallel
465 #endif /* _GLIBCXX_PARALLEL_BASE_H */