libstdc++
base.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007-2025 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 #pragma GCC diagnostic push
154 #pragma GCC diagnostic ignored "-Wdeprecated-declarations" // *nary_function
155 
156  /** @brief Constructs predicate for equality from strict weak
157  * ordering predicate
158  */
159  template<typename _T1, typename _T2, typename _Compare>
160  class _EqualFromLess : public std::binary_function<_T1, _T2, bool>
161  {
162  private:
163  _Compare& _M_comp;
164 
165  public:
166  _EqualFromLess(_Compare& __comp) : _M_comp(__comp) { }
167 
168  bool operator()(const _T1& __a, const _T2& __b)
169  { return !_M_comp(__a, __b) && !_M_comp(__b, __a); }
170  };
171 
172  /** @brief Similar to std::unary_negate,
173  * but giving the argument types explicitly. */
174  template<typename _Predicate, typename argument_type>
176  : public std::unary_function<argument_type, bool>
177  {
178  protected:
179  _Predicate _M_pred;
180 
181  public:
182  explicit
183  __unary_negate(const _Predicate& __x) : _M_pred(__x) { }
184 
185  bool
186  operator()(const argument_type& __x)
187  { return !_M_pred(__x); }
188  };
189 
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>
196  {
197  protected:
198  _Operation _M_op;
199  _FirstArgumentType _M_value;
200 
201  public:
202  __binder1st(const _Operation& __x, const _FirstArgumentType& __y)
203  : _M_op(__x), _M_value(__y) { }
204 
205  _ResultType
206  operator()(const _SecondArgumentType& __x)
207  { return _M_op(_M_value, __x); }
208 
209  // _GLIBCXX_RESOLVE_LIB_DEFECTS
210  // 109. Missing binders for non-const sequence elements
211  _ResultType
212  operator()(_SecondArgumentType& __x) const
213  { return _M_op(_M_value, __x); }
214  };
215 
216  /**
217  * @brief Similar to std::binder2nd, but giving the argument types
218  * explicitly.
219  */
220  template<typename _Operation, typename _FirstArgumentType,
221  typename _SecondArgumentType, typename _ResultType>
223  : public std::unary_function<_FirstArgumentType, _ResultType>
224  {
225  protected:
226  _Operation _M_op;
227  _SecondArgumentType _M_value;
228 
229  public:
230  __binder2nd(const _Operation& __x, const _SecondArgumentType& __y)
231  : _M_op(__x), _M_value(__y) { }
232 
233  _ResultType
234  operator()(const _FirstArgumentType& __x) const
235  { return _M_op(__x, _M_value); }
236 
237  // _GLIBCXX_RESOLVE_LIB_DEFECTS
238  // 109. Missing binders for non-const sequence elements
239  _ResultType
240  operator()(_FirstArgumentType& __x)
241  { return _M_op(__x, _M_value); }
242  };
243 
244  /** @brief Similar to std::equal_to, but allows two different types. */
245  template<typename _T1, typename _T2>
246  struct _EqualTo : std::binary_function<_T1, _T2, bool>
247  {
248  bool operator()(const _T1& __t1, const _T2& __t2) const
249  { return __t1 == __t2; }
250  };
251 
252  /** @brief Similar to std::less, but allows two different types. */
253  template<typename _T1, typename _T2>
254  struct _Less : std::binary_function<_T1, _T2, bool>
255  {
256  bool
257  operator()(const _T1& __t1, const _T2& __t2) const
258  { return __t1 < __t2; }
259 
260  bool
261  operator()(const _T2& __t2, const _T1& __t1) const
262  { return __t2 < __t1; }
263  };
264 
265  // Partial specialization for one type. Same as std::less.
266  template<typename _Tp>
267  struct _Less<_Tp, _Tp>
268  : public std::less<_Tp> { };
269 
270  /** @brief Similar to std::plus, but allows two different types. */
271  template<typename _Tp1, typename _Tp2, typename _Result
272  = __typeof__(*static_cast<_Tp1*>(0)
273  + *static_cast<_Tp2*>(0))>
274  struct _Plus : public std::binary_function<_Tp1, _Tp2, _Result>
275  {
276  _Result
277  operator()(const _Tp1& __x, const _Tp2& __y) const
278  { return __x + __y; }
279  };
280 
281  // Partial specialization for one type. Same as std::plus.
282  template<typename _Tp>
283  struct _Plus<_Tp, _Tp, _Tp>
284  : public std::plus<_Tp> { };
285 
286  /** @brief Similar to std::multiplies, but allows two different types. */
287  template<typename _Tp1, typename _Tp2, typename _Result
288  = __typeof__(*static_cast<_Tp1*>(0)
289  * *static_cast<_Tp2*>(0))>
290  struct _Multiplies : public std::binary_function<_Tp1, _Tp2, _Result>
291  {
292  _Result
293  operator()(const _Tp1& __x, const _Tp2& __y) const
294  { return __x * __y; }
295  };
296 
297  // Partial specialization for one type. Same as std::multiplies.
298  template<typename _Tp>
299  struct _Multiplies<_Tp, _Tp, _Tp>
300  : public std::multiplies<_Tp> { };
301 
302 #pragma GCC diagnostic pop // -Wdeprecated-declarations
303 
304  /** @brief _Iterator associated with __gnu_parallel::_PseudoSequence.
305  * If features the usual random-access iterator functionality.
306  * @param _Tp Sequence _M_value type.
307  * @param _DifferenceTp Sequence difference type.
308  */
309  template<typename _Tp, typename _DifferenceTp>
311  {
312  public:
313  typedef _DifferenceTp _DifferenceType;
314 
315  _PseudoSequenceIterator(const _Tp& __val, _DifferenceType __pos)
316  : _M_val(__val), _M_pos(__pos) { }
317 
318  // Pre-increment operator.
320  operator++()
321  {
322  ++_M_pos;
323  return *this;
324  }
325 
326  // Post-increment operator.
328  operator++(int)
329  { return _PseudoSequenceIterator(_M_pos++); }
330 
331  const _Tp&
332  operator*() const
333  { return _M_val; }
334 
335  const _Tp&
336  operator[](_DifferenceType) const
337  { return _M_val; }
338 
339  bool
340  operator==(const _PseudoSequenceIterator& __i2)
341  { return _M_pos == __i2._M_pos; }
342 
343  bool
344  operator!=(const _PseudoSequenceIterator& __i2)
345  { return _M_pos != __i2._M_pos; }
346 
347  _DifferenceType
349  { return _M_pos - __i2._M_pos; }
350 
351  private:
352  const _Tp& _M_val;
353  _DifferenceType _M_pos;
354  };
355 
356  /** @brief Sequence that conceptually consists of multiple copies of
357  the same element.
358  * The copies are not stored explicitly, of course.
359  * @param _Tp Sequence _M_value type.
360  * @param _DifferenceTp Sequence difference type.
361  */
362  template<typename _Tp, typename _DifferenceTp>
364  {
365  public:
366  typedef _DifferenceTp _DifferenceType;
367 
368  // Better cast down to uint64_t, than up to _DifferenceTp.
370 
371  /** @brief Constructor.
372  * @param __val Element of the sequence.
373  * @param __count Number of (virtual) copies.
374  */
375  _PseudoSequence(const _Tp& __val, _DifferenceType __count)
376  : _M_val(__val), _M_count(__count) { }
377 
378  /** @brief Begin iterator. */
379  iterator
380  begin() const
381  { return iterator(_M_val, 0); }
382 
383  /** @brief End iterator. */
384  iterator
385  end() const
386  { return iterator(_M_val, _M_count); }
387 
388  private:
389  const _Tp& _M_val;
390  _DifferenceType _M_count;
391  };
392 
393  /** @brief Compute the median of three referenced elements,
394  according to @c __comp.
395  * @param __a First iterator.
396  * @param __b Second iterator.
397  * @param __c Third iterator.
398  * @param __comp Comparator.
399  */
400  template<typename _RAIter, typename _Compare>
401  _RAIter
402  __median_of_three_iterators(_RAIter __a, _RAIter __b,
403  _RAIter __c, _Compare __comp)
404  {
405  if (__comp(*__a, *__b))
406  if (__comp(*__b, *__c))
407  return __b;
408  else
409  if (__comp(*__a, *__c))
410  return __c;
411  else
412  return __a;
413  else
414  {
415  // Just swap __a and __b.
416  if (__comp(*__a, *__c))
417  return __a;
418  else
419  if (__comp(*__b, *__c))
420  return __c;
421  else
422  return __b;
423  }
424  }
425 
426 #if _GLIBCXX_PARALLEL_ASSERTIONS && defined(__glibcxx_assert_impl)
427 # define _GLIBCXX_PARALLEL_ASSERT(_Condition) \
428  do { __glibcxx_assert_impl(_Condition); } while (false)
429 #else
430 # define _GLIBCXX_PARALLEL_ASSERT(_Condition) do { } while (false)
431 #endif
432 
433 } //namespace __gnu_parallel
434 
435 #endif /* _GLIBCXX_PARALLEL_BASE_H */
Includes the original header files concerned with iterators except for stream iterators....
Defines on whether to include algorithm variants.
End-user include file. Provides advanced settings and tuning options. This file is a GNU parallel ext...
constexpr complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
Definition: complex:434
constexpr complex< _Tp > operator-(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x minus y.
Definition: complex:404
ISO C++ entities toplevel namespace is std.
GNU parallel code, replaces standard behavior with parallel behavior.
Definition: algo.h:64
GNU parallel code for public use.
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.
Definition: base.h:144
_RAIter __median_of_three_iterators(_RAIter __a, _RAIter __b, _RAIter __c, _Compare __comp)
Compute the median of three referenced elements, according to __comp.
Definition: base.h:402
_Parallelism
Run-time equivalents for the compile-time tags.
Definition: types.h:45
@ sequential
Not parallel.
Definition: types.h:47
_CASable __encode2(int __a, int __b)
Encode two integers into one gnu_parallel::_CASable.
Definition: base.h:119
const _Tp & max(const _Tp &__a, const _Tp &__b)
Equivalent to std::max.
Definition: base.h:150
int64_t _CASable
Longest compare-and-swappable integer type on this platform.
Definition: types.h:127
static const _CASable _CASable_mask
_CASable with the right half of bits set to 1.
Definition: types.h:133
static const int _CASable_bits
Number of bits of _CASable.
Definition: types.h:130
_Size __rd_log2(_Size __n)
Calculates the rounded-down logarithm of __n for base 2.
Definition: base.h:102
void __decode2(_CASable __x, int &__a, int &__b)
Decode two integers from one gnu_parallel::_CASable.
Definition: base.h:133
GNU sequential classes for public use.
argument_type argument_type
argument_type is the type of the argument
Definition: stl_function.h:120
One of the math functors.
Definition: stl_function.h:185
One of the math functors.
Definition: stl_function.h:206
One of the comparison functors.
Definition: stl_function.h:401
Common iterator class.
Constructs predicate for equality from strict weak ordering predicate.
Definition: base.h:161
Similar to std::unary_negate, but giving the argument types explicitly.
Definition: base.h:177
Similar to std::binder1st, but giving the argument types explicitly.
Definition: base.h:196
Similar to std::binder2nd, but giving the argument types explicitly.
Definition: base.h:224
Similar to std::equal_to, but allows two different types.
Definition: base.h:247
Similar to std::less, but allows two different types.
Definition: base.h:255
Similar to std::plus, but allows two different types.
Definition: base.h:275
Similar to std::multiplies, but allows two different types.
Definition: base.h:291
_Iterator associated with __gnu_parallel::_PseudoSequence. If features the usual random-access iterat...
Definition: base.h:311
Sequence that conceptually consists of multiple copies of the same element. The copies are not stored...
Definition: base.h:364
iterator begin() const
Begin iterator.
Definition: base.h:380
iterator end() const
End iterator.
Definition: base.h:385
_PseudoSequence(const _Tp &__val, _DifferenceType __count)
Constructor.
Definition: base.h:375