1// -*- C++ -*-
2
3// Copyright (C) 2007, 2008, 2009, 2010 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 */
48namespace std
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::__norm;
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    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    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>
173    class __unary_negate
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>
192    class __binder1st
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>
220    class __binder2nd
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*>(NULL)
271			+ *static_cast<_Tp2*>(NULL))>
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*>(NULL)
287			* *static_cast<_Tp2*>(NULL))>
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 _DifferenceType 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 _DifferenceType 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 _M_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#define _GLIBCXX_PARALLEL_ASSERT(_Condition) __glibcxx_assert(_Condition)
423
424} //namespace __gnu_parallel
425
426#endif /* _GLIBCXX_PARALLEL_BASE_H */
427