libstdc++
parallel/base.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007-2018 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 3, or (at your option) any later
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 
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.
19 
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/>.
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 
35 #include <bits/c++config.h>
36 #include <bits/stl_function.h>
37 #include <omp.h>
38 #include <parallel/features.h>
40 #include <parallel/parallel.h>
41 
42 // Parallel mode namespaces.
43 
44 /**
45  * @namespace std::__parallel
46  * @brief GNU parallel code, replaces standard behavior with parallel behavior.
47  */
48 namespace std _GLIBCXX_VISIBILITY(default)
49 {
50  namespace __parallel { }
51 }
52 
53 /**
54  * @namespace __gnu_parallel
55  * @brief GNU parallel code for public use.
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 {
69  // Import whatever is the serial version.
70 #ifdef _GLIBCXX_PARALLEL
71  using namespace std::_GLIBCXX_STD_A;
72 #else
73  using namespace std;
74 #endif
75 }
76 
77 
78 namespace __gnu_parallel
79 {
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 _ThreadIndex
85  __get_max_threads()
86  {
87  _ThreadIndex __i = omp_get_max_threads();
88  return __i > 1 ? __i : 1;
89  }
90 
91 
92  inline bool
93  __is_parallel(const _Parallelism __p) { return __p != sequential; }
94 
95 
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.
99  */
100  template<typename _Size>
101  inline _Size
102  __rd_log2(_Size __n)
103  {
104  _Size __k;
105  for (__k = 0; __n > 1; __n >>= 1)
106  ++__k;
107  return __k;
108  }
109 
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.
116  * @see __decode2
117  */
118  inline _CASable
119  __encode2(int __a, int __b) //must all be non-negative, actually
120  {
121  return (((_CASable)__a) << (_CASable_bits / 2)) | (((_CASable)__b) << 0);
122  }
123 
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.
130  * @see __encode2
131  */
132  inline void
133  __decode2(_CASable __x, int& __a, int& __b)
134  {
135  __a = (int)((__x >> (_CASable_bits / 2)) & _CASable_mask);
136  __b = (int)((__x >> 0 ) & _CASable_mask);
137  }
138 
139  //needed for parallel "numeric", even if "algorithm" not included
140 
141  /** @brief Equivalent to std::min. */
142  template<typename _Tp>
143  inline const _Tp&
144  min(const _Tp& __a, const _Tp& __b)
145  { return (__a < __b) ? __a : __b; }
146 
147  /** @brief Equivalent to std::max. */
148  template<typename _Tp>
149  inline const _Tp&
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;
161 
162  public:
163  _EqualFromLess(_Compare& __comp) : _M_comp(__comp) { }
164 
165  bool operator()(const _T1& __a, const _T2& __b)
166  { return !_M_comp(__a, __b) && !_M_comp(__b, __a); }
167  };
168 
169 
170  /** @brief Similar to std::unary_negate,
171  * but giving the argument types explicitly. */
172  template<typename _Predicate, typename argument_type>
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>
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>
221  : public std::unary_function<_FirstArgumentType, _ResultType>
222  {
223  protected:
224  _Operation _M_op;
225  _SecondArgumentType _M_value;
226 
227  public:
228  __binder2nd(const _Operation& __x, const _SecondArgumentType& __y)
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  };
249 
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>
265  struct _Less<_Tp, _Tp>
266  : public std::less<_Tp> { };
267 
268  /** @brief Similar to std::plus, but allows two different types. */
269  template<typename _Tp1, typename _Tp2, typename _Result
270  = __typeof__(*static_cast<_Tp1*>(0)
271  + *static_cast<_Tp2*>(0))>
272  struct _Plus : public std::binary_function<_Tp1, _Tp2, _Result>
273  {
274  _Result
275  operator()(const _Tp1& __x, const _Tp2& __y) const
276  { return __x + __y; }
277  };
278 
279  // Partial specialization for one type. Same as std::plus.
280  template<typename _Tp>
281  struct _Plus<_Tp, _Tp, _Tp>
282  : public std::plus<_Tp> { };
283 
284  /** @brief Similar to std::multiplies, but allows two different types. */
285  template<typename _Tp1, typename _Tp2, typename _Result
286  = __typeof__(*static_cast<_Tp1*>(0)
287  * *static_cast<_Tp2*>(0))>
288  struct _Multiplies : public std::binary_function<_Tp1, _Tp2, _Result>
289  {
290  _Result
291  operator()(const _Tp1& __x, const _Tp2& __y) const
292  { return __x * __y; }
293  };
294 
295  // Partial specialization for one type. Same as std::multiplies.
296  template<typename _Tp>
297  struct _Multiplies<_Tp, _Tp, _Tp>
298  : public std::multiplies<_Tp> { };
299 
300  /** @brief _Iterator associated with __gnu_parallel::_PseudoSequence.
301  * If features the usual random-access iterator functionality.
302  * @param _Tp Sequence _M_value type.
303  * @param _DifferenceTp Sequence difference type.
304  */
305  template<typename _Tp, typename _DifferenceTp>
307  {
308  public:
309  typedef _DifferenceTp _DifferenceType;
310 
311  _PseudoSequenceIterator(const _Tp& __val, _DifferenceType __pos)
312  : _M_val(__val), _M_pos(__pos) { }
313 
314  // Pre-increment operator.
316  operator++()
317  {
318  ++_M_pos;
319  return *this;
320  }
321 
322  // Post-increment operator.
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 
339  bool
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; }
346 
347  private:
348  const _Tp& _M_val;
349  _DifferenceType _M_pos;
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.
356  * @param _DifferenceTp Sequence difference type.
357  */
358  template<typename _Tp, typename _DifferenceTp>
360  {
361  public:
362  typedef _DifferenceTp _DifferenceType;
363 
364  // Better cast down to uint64_t, than up to _DifferenceTp.
366 
367  /** @brief Constructor.
368  * @param __val Element of the sequence.
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 
389  /** @brief Compute the median of three referenced elements,
390  according to @c __comp.
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,
399  _RAIter __c, _Compare __comp)
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;
409  else
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  }
421 
422 #if _GLIBCXX_PARALLEL_ASSERTIONS && defined(__glibcxx_assert_impl)
423 #define _GLIBCXX_PARALLEL_ASSERT(_Condition) __glibcxx_assert_impl(_Condition)
424 #else
425 #define _GLIBCXX_PARALLEL_ASSERT(_Condition)
426 #endif
427 
428 } //namespace __gnu_parallel
429 
430 #endif /* _GLIBCXX_PARALLEL_BASE_H */
Similar to std::unary_negate, but giving the argument types explicitly.
iterator begin() const
Begin iterator.
One of the comparison functors.
Definition: stl_function.h:340
Similar to std::plus, but allows two different types.
Similar to std::equal_to, but allows two different types.
Sequence that conceptually consists of multiple copies of the same element. The copies are not stored...
Similar to std::multiplies, but allows two different types.
Common iterator class.
End-user include file. Provides advanced settings and tuning options. This file is a GNU parallel ext...
_CASable __encode2(int __a, int __b)
Encode two integers into one gnu_parallel::_CASable.
int64_t _CASable
Longest compare-and-swappable integer type on this platform.
Definition: types.h:127
Similar to std::binder2nd, but giving the argument types explicitly.
argument_type argument_type
argument_type is the type of the argument
Definition: stl_function.h:108
Constructs predicate for equality from strict weak ordering predicate.
GNU sequential classes for public use.
iterator end() const
End iterator.
Defines on whether to include algorithm variants.
Includes the original header files concerned with iterators except for stream iterators....
Similar to std::binder1st, but giving the argument types explicitly.
Not parallel.
Definition: types.h:47
_RAIter __median_of_three_iterators(_RAIter __a, _RAIter __b, _RAIter __c, _Compare __comp)
Compute the median of three referenced elements, according to __comp.
static const _CASable _CASable_mask
_CASable with the right half of bits set to 1.
Definition: types.h:133
ISO C++ entities toplevel namespace is std.
GNU parallel code for public use.
static const int _CASable_bits
Number of bits of _CASable.
Definition: types.h:130
_Iterator associated with __gnu_parallel::_PseudoSequence. If features the usual random-access iterat...
One of the math functors.
Definition: stl_function.h:147
void __decode2(_CASable __x, int &__a, int &__b)
Decode two integers from one gnu_parallel::_CASable.
_Parallelism
Run-time equivalents for the compile-time tags.
Definition: types.h:44
_PseudoSequence(const _Tp &__val, _DifferenceType __count)
Constructor.
One of the math functors.
Definition: stl_function.h:153
GNU parallel code, replaces standard behavior with parallel behavior.
Definition: algo.h:63
const _Tp & max(const _Tp &__a, const _Tp &__b)
Equivalent to std::max.
Similar to std::less, but allows two different types.
uint16_t _ThreadIndex
Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit in...
Definition: types.h:123
const _Tp & min(const _Tp &__a, const _Tp &__b)
Equivalent to std::min.
_Size __rd_log2(_Size __n)
Calculates the rounded-down logarithm of __n for base 2.