1 // -*- C++ -*-
2
3 // Copyright (C) 2007-2019 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>
39 #include <parallel/basic_iterator.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 */
_GLIBCXX_VISIBILITY(default)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
__get_max_threads()85 __get_max_threads()
86 {
87 _ThreadIndex __i = omp_get_max_threads();
88 return __i > 1 ? __i : 1;
89 }
90
91
92 inline bool
__is_parallel(const _Parallelism __p)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
__rd_log2(_Size __n)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
__encode2(int __a,int __b)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
__decode2(_CASable __x,int & __a,int & __b)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&
min(const _Tp & __a,const _Tp & __b)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&
max(const _Tp & __a,const _Tp & __b)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:
_EqualFromLess(_Compare & __comp)163 _EqualFromLess(_Compare& __comp) : _M_comp(__comp) { }
164
operator()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>
173 class __unary_negate
174 : public std::unary_function<argument_type, bool>
175 {
176 protected:
177 _Predicate _M_pred;
178
179 public:
180 explicit
__unary_negate(const _Predicate & __x)181 __unary_negate(const _Predicate& __x) : _M_pred(__x) { }
182
183 bool
operator()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>
192 class __binder1st
193 : public std::unary_function<_SecondArgumentType, _ResultType>
194 {
195 protected:
196 _Operation _M_op;
197 _FirstArgumentType _M_value;
198
199 public:
__binder1st(const _Operation & __x,const _FirstArgumentType & __y)200 __binder1st(const _Operation& __x, const _FirstArgumentType& __y)
201 : _M_op(__x), _M_value(__y) { }
202
203 _ResultType
operator()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
operator()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>
220 class __binder2nd
221 : public std::unary_function<_FirstArgumentType, _ResultType>
222 {
223 protected:
224 _Operation _M_op;
225 _SecondArgumentType _M_value;
226
227 public:
__binder2nd(const _Operation & __x,const _SecondArgumentType & __y)228 __binder2nd(const _Operation& __x, const _SecondArgumentType& __y)
229 : _M_op(__x), _M_value(__y) { }
230
231 _ResultType
operator()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
operator()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 {
operator_EqualTo246 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
operator_Less255 operator()(const _T1& __t1, const _T2& __t2) const
256 { return __t1 < __t2; }
257
258 bool
operator_Less259 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>
306 class _PseudoSequenceIterator
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.
315 _PseudoSequenceIterator&
316 operator++()
317 {
318 ++_M_pos;
319 return *this;
320 }
321
322 // Post-increment operator.
323 _PseudoSequenceIterator
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>
359 class _PseudoSequence
360 {
361 public:
362 typedef _DifferenceTp _DifferenceType;
363
364 // Better cast down to uint64_t, than up to _DifferenceTp.
365 typedef _PseudoSequenceIterator<_Tp, uint64_t> iterator;
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 */
431