3 // Copyright (C) 2007, 2008 Free Software Foundation, Inc.
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
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
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 <parallel/features.h>
43 #include <parallel/basic_iterator.h>
44 #include <parallel/parallel.h>
47 namespace __gnu_parallel
49 // XXX remove std::duplicates from here if possible,
50 // XXX but keep minimal dependencies.
52 /** @brief Calculates the rounded-down logarithm of @c n for base 2.
54 * @return Returns 0 for argument 0.
56 template<typename Size
>
61 for (k
= 0; n
!= 1; n
>>= 1)
66 /** @brief Encode two integers into one __gnu_parallel::lcas_t.
67 * @param a First integer, to be encoded in the most-significant @c
69 * @param b Second integer, to be encoded in the least-significant
70 * @c lcas_t_bits/2 bits.
71 * @return __gnu_parallel::lcas_t value encoding @c a and @c b.
75 encode2(int a
, int b
) //must all be non-negative, actually
77 return (((lcas_t
)a
) << (lcas_t_bits
/ 2)) | (((lcas_t
)b
) << 0);
80 /** @brief Decode two integers from one __gnu_parallel::lcas_t.
81 * @param x __gnu_parallel::lcas_t to decode integers from.
82 * @param a First integer, to be decoded from the most-significant
83 * @c lcas_t_bits/2 bits of @c x.
84 * @param b Second integer, to be encoded in the least-significant
85 * @c lcas_t_bits/2 bits of @c x.
89 decode2(lcas_t x
, int& a
, int& b
)
91 a
= (int)((x
>> (lcas_t_bits
/ 2)) & lcas_t_mask
);
92 b
= (int)((x
>> 0 ) & lcas_t_mask
);
95 /** @brief Equivalent to std::min. */
98 min(const T
& a
, const T
& b
)
99 { return (a
< b
) ? a
: b
; }
101 /** @brief Equivalent to std::max. */
104 max(const T
& a
, const T
& b
)
105 { return (a
> b
) ? a
: b
; }
107 /** @brief Constructs predicate for equality from strict weak
110 // XXX comparator at the end, as per others
111 template<typename Comparator
, typename T1
, typename T2
>
112 class equal_from_less
: public std::binary_function
<T1
, T2
, bool>
118 equal_from_less(Comparator
& _comp
) : comp(_comp
) { }
120 bool operator()(const T1
& a
, const T2
& b
)
122 return !comp(a
, b
) && !comp(b
, a
);
127 /** @brief Similar to std::binder1st,
128 * but giving the argument types explicitly. */
129 template<typename _Predicate
, typename argument_type
>
131 : public std::unary_function
<argument_type
, bool>
138 unary_negate(const _Predicate
& __x
) : _M_pred(__x
) { }
141 operator()(const argument_type
& __x
)
142 { return !_M_pred(__x
); }
145 /** @brief Similar to std::binder1st,
146 * but giving the argument types explicitly. */
149 typename first_argument_type
,
150 typename second_argument_type
,
151 typename result_type
>
153 : public std::unary_function
<second_argument_type
, result_type
>
157 first_argument_type value
;
160 binder1st(const _Operation
& __x
,
161 const first_argument_type
& __y
)
162 : op(__x
), value(__y
) { }
165 operator()(const second_argument_type
& __x
)
166 { return op(value
, __x
); }
168 // _GLIBCXX_RESOLVE_LIB_DEFECTS
169 // 109. Missing binders for non-const sequence elements
171 operator()(second_argument_type
& __x
) const
172 { return op(value
, __x
); }
176 * @brief Similar to std::binder2nd, but giving the argument types
181 typename first_argument_type
,
182 typename second_argument_type
,
183 typename result_type
>
185 : public std::unary_function
<first_argument_type
, result_type
>
189 second_argument_type value
;
192 binder2nd(const _Operation
& __x
,
193 const second_argument_type
& __y
)
194 : op(__x
), value(__y
) { }
197 operator()(const first_argument_type
& __x
) const
198 { return op(__x
, value
); }
200 // _GLIBCXX_RESOLVE_LIB_DEFECTS
201 // 109. Missing binders for non-const sequence elements
203 operator()(first_argument_type
& __x
)
204 { return op(__x
, value
); }
207 /** @brief Similar to std::equal_to, but allows two different types. */
208 template<typename T1
, typename T2
>
209 struct equal_to
: std::binary_function
<T1
, T2
, bool>
211 bool operator()(const T1
& t1
, const T2
& t2
) const
215 /** @brief Similar to std::less, but allows two different types. */
216 template<typename T1
, typename T2
>
217 struct less
: std::binary_function
<T1
, T2
, bool>
220 operator()(const T1
& t1
, const T2
& t2
) const
224 operator()(const T2
& t2
, const T1
& t1
) const
228 // Partial specialization for one type. Same as std::less.
229 template<typename _Tp
>
230 struct less
<_Tp
, _Tp
> : public std::binary_function
<_Tp
, _Tp
, bool>
233 operator()(const _Tp
& __x
, const _Tp
& __y
) const
234 { return __x
< __y
; }
238 /** @brief Similar to std::plus, but allows two different types. */
239 template<typename _Tp1
, typename _Tp2
>
240 struct plus
: public std::binary_function
<_Tp1
, _Tp2
, _Tp1
>
242 typedef typeof(*static_cast<_Tp1
*>(NULL
)
243 + *static_cast<_Tp2
*>(NULL
)) result
;
246 operator()(const _Tp1
& __x
, const _Tp2
& __y
) const
247 { return __x
+ __y
; }
250 // Partial specialization for one type. Same as std::plus.
251 template<typename _Tp
>
252 struct plus
<_Tp
, _Tp
> : public std::binary_function
<_Tp
, _Tp
, _Tp
>
254 typedef typeof(*static_cast<_Tp
*>(NULL
)
255 + *static_cast<_Tp
*>(NULL
)) result
;
258 operator()(const _Tp
& __x
, const _Tp
& __y
) const
259 { return __x
+ __y
; }
263 /** @brief Similar to std::multiplies, but allows two different types. */
264 template<typename _Tp1
, typename _Tp2
>
265 struct multiplies
: public std::binary_function
<_Tp1
, _Tp2
, _Tp1
>
267 typedef typeof(*static_cast<_Tp1
*>(NULL
)
268 * *static_cast<_Tp2
*>(NULL
)) result
;
271 operator()(const _Tp1
& __x
, const _Tp2
& __y
) const
272 { return __x
* __y
; }
275 // Partial specialization for one type. Same as std::multiplies.
276 template<typename _Tp
>
277 struct multiplies
<_Tp
, _Tp
> : public std::binary_function
<_Tp
, _Tp
, _Tp
>
279 typedef typeof(*static_cast<_Tp
*>(NULL
)
280 * *static_cast<_Tp
*>(NULL
)) result
;
283 operator()(const _Tp
& __x
, const _Tp
& __y
) const
284 { return __x
* __y
; }
288 template<typename T
, typename _DifferenceTp
>
289 class pseudo_sequence
;
291 /** @brief Iterator associated with __gnu_parallel::pseudo_sequence.
292 * If features the usual random-access iterator functionality.
293 * @param T Sequence value type.
294 * @param difference_type Sequence difference type.
296 template<typename T
, typename _DifferenceTp
>
297 class pseudo_sequence_iterator
300 typedef _DifferenceTp difference_type
;
303 typedef pseudo_sequence_iterator
<T
, _DifferenceTp
> type
;
309 pseudo_sequence_iterator(const T
& val
, difference_type pos
)
310 : val(val
), pos(pos
) { }
312 // Pre-increment operator.
320 // Post-increment operator.
323 { return type(pos
++); }
330 operator[](difference_type
) const
334 operator==(const type
& i2
)
335 { return pos
== i2
.pos
; }
338 operator!=(const type
& i2
)
339 { return pos
!= i2
.pos
; }
342 operator-(const type
& i2
)
343 { return pos
- i2
.pos
; }
346 /** @brief Sequence that conceptually consists of multiple copies of
348 * The copies are not stored explicitly, of course.
349 * @param T Sequence value type.
350 * @param difference_type Sequence difference type.
352 template<typename T
, typename _DifferenceTp
>
353 class pseudo_sequence
355 typedef pseudo_sequence
<T
, _DifferenceTp
> type
;
358 typedef _DifferenceTp difference_type
;
360 // Better case down to uint64, than up to _DifferenceTp.
361 typedef pseudo_sequence_iterator
<T
, uint64
> iterator
;
363 /** @brief Constructor.
364 * @param val Element of the sequence.
365 * @param count Number of (virtual) copies.
367 pseudo_sequence(const T
& val
, difference_type count
)
368 : val(val
), count(count
) { }
370 /** @brief Begin iterator. */
373 { return iterator(val
, 0); }
375 /** @brief End iterator. */
378 { return iterator(val
, count
); }
382 difference_type count
;
385 /** @brief Functor that does nothing */
386 template<typename _ValueTp
>
390 operator()(const _ValueTp
& v
) const { }
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.
400 template<typename RandomAccessIterator
, typename Comparator
>
402 median_of_three_iterators(RandomAccessIterator a
, RandomAccessIterator b
,
403 RandomAccessIterator c
, Comparator
& comp
)
415 // Just swap a and b.
426 // Avoid the use of assert, because we're trying to keep the <cassert>
427 // include out of the mix. (Same as debug mode).
429 __replacement_assert(const char* __file
, int __line
,
430 const char* __function
, const char* __condition
)
432 std::printf("%s:%d: %s: Assertion '%s' failed.\n", __file
, __line
,
433 __function
, __condition
);
437 #define _GLIBCXX_PARALLEL_ASSERT(_Condition) \
441 __gnu_parallel::__replacement_assert(__FILE__, __LINE__, \
442 __PRETTY_FUNCTION__, #_Condition); \
445 } //namespace __gnu_parallel