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 // XXX remove std::duplicates from here if possible,
97 // XXX but keep minimal dependencies.
99 /** @brief Calculates the rounded-down logarithm of @c n for base 2.
101 * @return Returns 0 for any argument <1.
103 template<typename Size>
108 for (k = 0; n > 1; n >>= 1)
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.
122 encode2(int a, int b) //must all be non-negative, actually
124 return (((lcas_t)a) << (lcas_t_bits / 2)) | (((lcas_t)b) << 0);
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.
136 decode2(lcas_t x, int& a, int& b)
138 a = (int)((x >> (lcas_t_bits / 2)) & lcas_t_mask);
139 b = (int)((x >> 0 ) & lcas_t_mask);
142 /** @brief Equivalent to std::min. */
145 min(const T& a, const T& b)
146 { return (a < b) ? a : b; }
148 /** @brief Equivalent to std::max. */
151 max(const T& a, const T& b)
152 { return (a > b) ? a : b; }
154 /** @brief Constructs predicate for equality from strict weak
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>
165 equal_from_less(Comparator& _comp) : comp(_comp) { }
167 bool operator()(const T1& a, const T2& b)
169 return !comp(a, b) && !comp(b, a);
174 /** @brief Similar to std::binder1st,
175 * but giving the argument types explicitly. */
176 template<typename _Predicate, typename argument_type>
178 : public std::unary_function<argument_type, bool>
185 unary_negate(const _Predicate& __x) : _M_pred(__x) { }
188 operator()(const argument_type& __x)
189 { return !_M_pred(__x); }
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>
197 : public std::unary_function<second_argument_type, result_type>
201 first_argument_type value;
204 binder1st(const _Operation& __x,
205 const first_argument_type& __y)
206 : op(__x), value(__y) { }
209 operator()(const second_argument_type& __x)
210 { return op(value, __x); }
212 // _GLIBCXX_RESOLVE_LIB_DEFECTS
213 // 109. Missing binders for non-const sequence elements
215 operator()(second_argument_type& __x) const
216 { return op(value, __x); }
220 * @brief Similar to std::binder2nd, but giving the argument types
223 template<typename _Operation, typename first_argument_type,
224 typename second_argument_type, typename result_type>
226 : public std::unary_function<first_argument_type, result_type>
230 second_argument_type value;
233 binder2nd(const _Operation& __x,
234 const second_argument_type& __y)
235 : op(__x), value(__y) { }
238 operator()(const first_argument_type& __x) const
239 { return op(__x, value); }
241 // _GLIBCXX_RESOLVE_LIB_DEFECTS
242 // 109. Missing binders for non-const sequence elements
244 operator()(first_argument_type& __x)
245 { return op(__x, value); }
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>
252 bool operator()(const T1& t1, const T2& t2) const
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>
261 operator()(const T1& t1, const T2& t2) const
265 operator()(const T2& t2, const T1& t1) const
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>
274 operator()(const _Tp& __x, const _Tp& __y) const
275 { return __x < __y; }
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>
283 typedef __typeof__(*static_cast<_Tp1*>(NULL)
284 + *static_cast<_Tp2*>(NULL)) result;
287 operator()(const _Tp1& __x, const _Tp2& __y) const
288 { return __x + __y; }
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>
295 typedef __typeof__(*static_cast<_Tp*>(NULL)
296 + *static_cast<_Tp*>(NULL)) result;
299 operator()(const _Tp& __x, const _Tp& __y) const
300 { return __x + __y; }
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>
308 typedef __typeof__(*static_cast<_Tp1*>(NULL)
309 * *static_cast<_Tp2*>(NULL)) result;
312 operator()(const _Tp1& __x, const _Tp2& __y) const
313 { return __x * __y; }
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>
320 typedef __typeof__(*static_cast<_Tp*>(NULL)
321 * *static_cast<_Tp*>(NULL)) result;
324 operator()(const _Tp& __x, const _Tp& __y) const
325 { return __x * __y; }
329 template<typename T, typename _DifferenceTp>
330 class pseudo_sequence;
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.
337 template<typename T, typename _DifferenceTp>
338 class pseudo_sequence_iterator
341 typedef _DifferenceTp difference_type;
344 typedef pseudo_sequence_iterator<T, _DifferenceTp> type;
350 pseudo_sequence_iterator(const T& val, difference_type pos)
351 : val(val), pos(pos) { }
353 // Pre-increment operator.
361 // Post-increment operator.
364 { return type(pos++); }
371 operator[](difference_type) const
375 operator==(const type& i2)
376 { return pos == i2.pos; }
379 operator!=(const type& i2)
380 { return pos != i2.pos; }
383 operator-(const type& i2)
384 { return pos - i2.pos; }
387 /** @brief Sequence that conceptually consists of multiple copies of
389 * The copies are not stored explicitly, of course.
390 * @param T Sequence value type.
391 * @param difference_type Sequence difference type.
393 template<typename T, typename _DifferenceTp>
394 class pseudo_sequence
396 typedef pseudo_sequence<T, _DifferenceTp> type;
399 typedef _DifferenceTp difference_type;
401 // Better case down to uint64, than up to _DifferenceTp.
402 typedef pseudo_sequence_iterator<T, uint64> iterator;
404 /** @brief Constructor.
405 * @param val Element of the sequence.
406 * @param count Number of (virtual) copies.
408 pseudo_sequence(const T& val, difference_type count)
409 : val(val), count(count) { }
411 /** @brief Begin iterator. */
414 { return iterator(val, 0); }
416 /** @brief End iterator. */
419 { return iterator(val, count); }
423 difference_type count;
426 /** @brief Functor that does nothing */
427 template<typename _ValueTp>
431 operator()(const _ValueTp& v) const { }
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.
441 template<typename RandomAccessIterator, typename Comparator>
443 median_of_three_iterators(RandomAccessIterator a, RandomAccessIterator b,
444 RandomAccessIterator c, Comparator& comp)
456 // Just swap a and b.
467 #define _GLIBCXX_PARALLEL_ASSERT(_Condition) __glibcxx_assert(_Condition)
469 } //namespace __gnu_parallel
471 #endif /* _GLIBCXX_PARALLEL_BASE_H */