libstdc++
base.h
Go to the documentation of this file.
1// -*- C++ -*-
2
3// Copyright (C) 2007-2024 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 */
48namespace std _GLIBCXX_VISIBILITY(default)
49{
50 namespace __parallel { }
51}
52
53/**
54 * @namespace __gnu_parallel
55 * @brief GNU parallel code for public use.
56 */
57namespace __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 */
67namespace __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
78namespace __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
348 operator-(const _PseudoSequenceIterator& __i2)
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. */
380 begin() const
381 { return iterator(_M_val, 0); }
382
383 /** @brief End 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 */
End-user include file. Provides advanced settings and tuning options. This file is a GNU parallel ext...
Includes the original header files concerned with iterators except for stream iterators....
Defines on whether to include algorithm variants.
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 & max(const _Tp &__a, const _Tp &__b)
Equivalent to std::max.
Definition base.h:150
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
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
One of the math functors.
One of the math functors.
One of the comparison functors.
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