Install gcc-4.3.3-tdm-1-g++.tar.gz
[msysgit.git] / mingw / lib / gcc / mingw32 / 4.3.3 / include / c++ / parallel / base.h
blob54c26d8ca6d58d2bf1c66545d9d27555abd0f754
1 // -*- C++ -*-
3 // Copyright (C) 2007, 2008 Free Software Foundation, Inc.
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
8 // Foundation; either version 2, or (at your option) any later
9 // version.
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 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING. If not, write to
18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19 // MA 02111-1307, USA.
21 // As a special exception, you may use this file as part of a free
22 // software library without restriction. Specifically, if other files
23 // instantiate templates or use macros or inline functions from this
24 // file, or you compile this file and link it with other files to
25 // produce an executable, this file does not by itself cause the
26 // resulting executable to be covered by the GNU General Public
27 // License. This exception does not however invalidate any other
28 // reasons why the executable file might be covered by the GNU General
29 // Public License.
31 /** @file parallel/base.h
32 * @brief Sequential helper functions.
33 * This file is a GNU parallel extension to the Standard C++ Library.
36 // Written by Johannes Singler.
38 #ifndef _GLIBCXX_PARALLEL_BASE_H
39 #define _GLIBCXX_PARALLEL_BASE_H 1
41 #include <cstdio>
42 #include <functional>
43 #include <omp.h>
44 #include <parallel/features.h>
45 #include <parallel/basic_iterator.h>
46 #include <parallel/parallel.h>
49 // Parallel mode namespaces.
51 /**
52 * @namespace std::__parallel
53 * @brief GNU parallel code, replaces standard behavior with parallel behavior.
55 namespace std
57 namespace __parallel { }
60 /**
61 * @namespace __gnu_parallel
62 * @brief GNU parallel code for public use.
64 namespace __gnu_parallel
66 // Import all the parallel versions of components in namespace std.
67 using namespace std::__parallel;
70 /**
71 * @namespace __gnu_sequential
72 * @brief GNU sequential classes for public use.
74 namespace __gnu_sequential
76 // Import whatever is the serial version.
77 #ifdef _GLIBCXX_PARALLEL
78 using namespace std::__norm;
79 #else
80 using namespace std;
81 #endif
85 namespace __gnu_parallel
87 // NB: Including this file cannot produce (unresolved) symbols from
88 // the OpenMP runtime unless the parallel mode is actually invoked
89 // and active, which imples that the OpenMP runtime is actually
90 // going to be linked in.
91 inline int
92 get_max_threads()
94 int __i = omp_get_max_threads();
95 return __i > 1 ? __i : 1;
99 inline bool
100 is_parallel(const _Parallelism __p) { return __p != sequential; }
103 // XXX remove std::duplicates from here if possible,
104 // XXX but keep minimal dependencies.
106 /** @brief Calculates the rounded-down logarithm of @c n for base 2.
107 * @param n Argument.
108 * @return Returns 0 for argument 0.
110 template<typename Size>
111 inline Size
112 log2(Size n)
114 Size k;
115 for (k = 0; n != 1; n >>= 1)
116 ++k;
117 return k;
120 /** @brief Encode two integers into one __gnu_parallel::lcas_t.
121 * @param a First integer, to be encoded in the most-significant @c
122 * lcas_t_bits/2 bits.
123 * @param b Second integer, to be encoded in the least-significant
124 * @c lcas_t_bits/2 bits.
125 * @return __gnu_parallel::lcas_t value encoding @c a and @c b.
126 * @see decode2
128 inline lcas_t
129 encode2(int a, int b) //must all be non-negative, actually
131 return (((lcas_t)a) << (lcas_t_bits / 2)) | (((lcas_t)b) << 0);
134 /** @brief Decode two integers from one __gnu_parallel::lcas_t.
135 * @param x __gnu_parallel::lcas_t to decode integers from.
136 * @param a First integer, to be decoded from the most-significant
137 * @c lcas_t_bits/2 bits of @c x.
138 * @param b Second integer, to be encoded in the least-significant
139 * @c lcas_t_bits/2 bits of @c x.
140 * @see encode2
142 inline void
143 decode2(lcas_t x, int& a, int& b)
145 a = (int)((x >> (lcas_t_bits / 2)) & lcas_t_mask);
146 b = (int)((x >> 0 ) & lcas_t_mask);
149 /** @brief Equivalent to std::min. */
150 template<typename T>
151 const T&
152 min(const T& a, const T& b)
153 { return (a < b) ? a : b; }
155 /** @brief Equivalent to std::max. */
156 template<typename T>
157 const T&
158 max(const T& a, const T& b)
159 { return (a > b) ? a : b; }
161 /** @brief Constructs predicate for equality from strict weak
162 * ordering predicate
164 // XXX comparator at the end, as per others
165 template<typename Comparator, typename T1, typename T2>
166 class equal_from_less : public std::binary_function<T1, T2, bool>
168 private:
169 Comparator& comp;
171 public:
172 equal_from_less(Comparator& _comp) : comp(_comp) { }
174 bool operator()(const T1& a, const T2& b)
176 return !comp(a, b) && !comp(b, a);
181 /** @brief Similar to std::binder1st,
182 * but giving the argument types explicitly. */
183 template<typename _Predicate, typename argument_type>
184 class unary_negate
185 : public std::unary_function<argument_type, bool>
187 protected:
188 _Predicate _M_pred;
190 public:
191 explicit
192 unary_negate(const _Predicate& __x) : _M_pred(__x) { }
194 bool
195 operator()(const argument_type& __x)
196 { return !_M_pred(__x); }
199 /** @brief Similar to std::binder1st,
200 * but giving the argument types explicitly. */
201 template<typename _Operation, typename first_argument_type,
202 typename second_argument_type, typename result_type>
203 class binder1st
204 : public std::unary_function<second_argument_type, result_type>
206 protected:
207 _Operation op;
208 first_argument_type value;
210 public:
211 binder1st(const _Operation& __x,
212 const first_argument_type& __y)
213 : op(__x), value(__y) { }
215 result_type
216 operator()(const second_argument_type& __x)
217 { return op(value, __x); }
219 // _GLIBCXX_RESOLVE_LIB_DEFECTS
220 // 109. Missing binders for non-const sequence elements
221 result_type
222 operator()(second_argument_type& __x) const
223 { return op(value, __x); }
227 * @brief Similar to std::binder2nd, but giving the argument types
228 * explicitly.
230 template<typename _Operation, typename first_argument_type,
231 typename second_argument_type, typename result_type>
232 class binder2nd
233 : public std::unary_function<first_argument_type, result_type>
235 protected:
236 _Operation op;
237 second_argument_type value;
239 public:
240 binder2nd(const _Operation& __x,
241 const second_argument_type& __y)
242 : op(__x), value(__y) { }
244 result_type
245 operator()(const first_argument_type& __x) const
246 { return op(__x, value); }
248 // _GLIBCXX_RESOLVE_LIB_DEFECTS
249 // 109. Missing binders for non-const sequence elements
250 result_type
251 operator()(first_argument_type& __x)
252 { return op(__x, value); }
255 /** @brief Similar to std::equal_to, but allows two different types. */
256 template<typename T1, typename T2>
257 struct equal_to : std::binary_function<T1, T2, bool>
259 bool operator()(const T1& t1, const T2& t2) const
260 { return t1 == t2; }
263 /** @brief Similar to std::less, but allows two different types. */
264 template<typename T1, typename T2>
265 struct less : std::binary_function<T1, T2, bool>
267 bool
268 operator()(const T1& t1, const T2& t2) const
269 { return t1 < t2; }
271 bool
272 operator()(const T2& t2, const T1& t1) const
273 { return t2 < t1; }
276 // Partial specialization for one type. Same as std::less.
277 template<typename _Tp>
278 struct less<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, bool>
280 bool
281 operator()(const _Tp& __x, const _Tp& __y) const
282 { return __x < __y; }
286 /** @brief Similar to std::plus, but allows two different types. */
287 template<typename _Tp1, typename _Tp2>
288 struct plus : public std::binary_function<_Tp1, _Tp2, _Tp1>
290 typedef __typeof__(*static_cast<_Tp1*>(NULL)
291 + *static_cast<_Tp2*>(NULL)) result;
293 result
294 operator()(const _Tp1& __x, const _Tp2& __y) const
295 { return __x + __y; }
298 // Partial specialization for one type. Same as std::plus.
299 template<typename _Tp>
300 struct plus<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp>
302 typedef __typeof__(*static_cast<_Tp*>(NULL)
303 + *static_cast<_Tp*>(NULL)) result;
305 result
306 operator()(const _Tp& __x, const _Tp& __y) const
307 { return __x + __y; }
311 /** @brief Similar to std::multiplies, but allows two different types. */
312 template<typename _Tp1, typename _Tp2>
313 struct multiplies : public std::binary_function<_Tp1, _Tp2, _Tp1>
315 typedef __typeof__(*static_cast<_Tp1*>(NULL)
316 * *static_cast<_Tp2*>(NULL)) result;
318 result
319 operator()(const _Tp1& __x, const _Tp2& __y) const
320 { return __x * __y; }
323 // Partial specialization for one type. Same as std::multiplies.
324 template<typename _Tp>
325 struct multiplies<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp>
327 typedef __typeof__(*static_cast<_Tp*>(NULL)
328 * *static_cast<_Tp*>(NULL)) result;
330 result
331 operator()(const _Tp& __x, const _Tp& __y) const
332 { return __x * __y; }
336 template<typename T, typename _DifferenceTp>
337 class pseudo_sequence;
339 /** @brief Iterator associated with __gnu_parallel::pseudo_sequence.
340 * If features the usual random-access iterator functionality.
341 * @param T Sequence value type.
342 * @param difference_type Sequence difference type.
344 template<typename T, typename _DifferenceTp>
345 class pseudo_sequence_iterator
347 public:
348 typedef _DifferenceTp difference_type;
350 private:
351 typedef pseudo_sequence_iterator<T, _DifferenceTp> type;
353 const T& val;
354 difference_type pos;
356 public:
357 pseudo_sequence_iterator(const T& val, difference_type pos)
358 : val(val), pos(pos) { }
360 // Pre-increment operator.
361 type&
362 operator++()
364 ++pos;
365 return *this;
368 // Post-increment operator.
369 const type
370 operator++(int)
371 { return type(pos++); }
373 const T&
374 operator*() const
375 { return val; }
377 const T&
378 operator[](difference_type) const
379 { return val; }
381 bool
382 operator==(const type& i2)
383 { return pos == i2.pos; }
385 difference_type
386 operator!=(const type& i2)
387 { return pos != i2.pos; }
389 difference_type
390 operator-(const type& i2)
391 { return pos - i2.pos; }
394 /** @brief Sequence that conceptually consists of multiple copies of
395 the same element.
396 * The copies are not stored explicitly, of course.
397 * @param T Sequence value type.
398 * @param difference_type Sequence difference type.
400 template<typename T, typename _DifferenceTp>
401 class pseudo_sequence
403 typedef pseudo_sequence<T, _DifferenceTp> type;
405 public:
406 typedef _DifferenceTp difference_type;
408 // Better case down to uint64, than up to _DifferenceTp.
409 typedef pseudo_sequence_iterator<T, uint64> iterator;
411 /** @brief Constructor.
412 * @param val Element of the sequence.
413 * @param count Number of (virtual) copies.
415 pseudo_sequence(const T& val, difference_type count)
416 : val(val), count(count) { }
418 /** @brief Begin iterator. */
419 iterator
420 begin() const
421 { return iterator(val, 0); }
423 /** @brief End iterator. */
424 iterator
425 end() const
426 { return iterator(val, count); }
428 private:
429 const T& val;
430 difference_type count;
433 /** @brief Functor that does nothing */
434 template<typename _ValueTp>
435 class void_functor
437 inline void
438 operator()(const _ValueTp& v) const { }
441 /** @brief Compute the median of three referenced elements,
442 according to @c comp.
443 * @param a First iterator.
444 * @param b Second iterator.
445 * @param c Third iterator.
446 * @param comp Comparator.
448 template<typename RandomAccessIterator, typename Comparator>
449 RandomAccessIterator
450 median_of_three_iterators(RandomAccessIterator a, RandomAccessIterator b,
451 RandomAccessIterator c, Comparator& comp)
453 if (comp(*a, *b))
454 if (comp(*b, *c))
455 return b;
456 else
457 if (comp(*a, *c))
458 return c;
459 else
460 return a;
461 else
463 // Just swap a and b.
464 if (comp(*a, *c))
465 return a;
466 else
467 if (comp(*b, *c))
468 return c;
469 else
470 return b;
474 // Avoid the use of assert, because we're trying to keep the <cassert>
475 // include out of the mix. (Same as debug mode).
476 inline void
477 __replacement_assert(const char* __file, int __line,
478 const char* __function, const char* __condition)
480 std::printf("%s:%d: %s: Assertion '%s' failed.\n", __file, __line,
481 __function, __condition);
482 __builtin_abort();
485 #define _GLIBCXX_PARALLEL_ASSERT(_Condition) \
486 do \
488 if (!(_Condition)) \
489 __gnu_parallel::__replacement_assert(__FILE__, __LINE__, \
490 __PRETTY_FUNCTION__, #_Condition); \
491 } while (false)
493 } //namespace __gnu_parallel
495 #endif