libstdc++
base.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007, 2008, 2009 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 <functional>
36 #include <omp.h>
37 #include <parallel/features.h>
39 #include <parallel/parallel.h>
40 
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
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::__norm;
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 int
85  get_max_threads()
86  {
87  int __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  // XXX remove std::duplicates from here if possible,
97  // XXX but keep minimal dependencies.
98 
99 /** @brief Calculates the rounded-down logarithm of @c n for base 2.
100  * @param n Argument.
101  * @return Returns 0 for any argument <1.
102  */
103 template<typename Size>
104  inline Size
105  __log2(Size n)
106  {
107  Size k;
108  for (k = 0; n > 1; n >>= 1)
109  ++k;
110  return k;
111  }
112 
113 /** @brief Encode two integers into one __gnu_parallel::lcas_t.
114  * @param a First integer, to be encoded in the most-significant @c
115  * lcas_t_bits/2 bits.
116  * @param b Second integer, to be encoded in the least-significant
117  * @c lcas_t_bits/2 bits.
118  * @return __gnu_parallel::lcas_t value encoding @c a and @c b.
119  * @see decode2
120  */
121 inline lcas_t
122 encode2(int a, int b) //must all be non-negative, actually
123 {
124  return (((lcas_t)a) << (lcas_t_bits / 2)) | (((lcas_t)b) << 0);
125 }
126 
127 /** @brief Decode two integers from one __gnu_parallel::lcas_t.
128  * @param x __gnu_parallel::lcas_t to decode integers from.
129  * @param a First integer, to be decoded from the most-significant
130  * @c lcas_t_bits/2 bits of @c x.
131  * @param b Second integer, to be encoded in the least-significant
132  * @c lcas_t_bits/2 bits of @c x.
133  * @see encode2
134  */
135 inline void
136 decode2(lcas_t x, int& a, int& b)
137 {
138  a = (int)((x >> (lcas_t_bits / 2)) & lcas_t_mask);
139  b = (int)((x >> 0 ) & lcas_t_mask);
140 }
141 
142 /** @brief Equivalent to std::min. */
143 template<typename T>
144  const T&
145  min(const T& a, const T& b)
146  { return (a < b) ? a : b; }
147 
148 /** @brief Equivalent to std::max. */
149 template<typename T>
150  const T&
151  max(const T& a, const T& b)
152  { return (a > b) ? a : b; }
153 
154 /** @brief Constructs predicate for equality from strict weak
155  * ordering predicate
156  */
157 // XXX comparator at the end, as per others
158 template<typename Comparator, typename T1, typename T2>
159  class equal_from_less : public std::binary_function<T1, T2, bool>
160  {
161  private:
162  Comparator& comp;
163 
164  public:
165  equal_from_less(Comparator& _comp) : comp(_comp) { }
166 
167  bool operator()(const T1& a, const T2& b)
168  {
169  return !comp(a, b) && !comp(b, a);
170  }
171  };
172 
173 
174 /** @brief Similar to std::binder1st,
175  * but giving the argument types explicitly. */
176 template<typename _Predicate, typename argument_type>
178  : public std::unary_function<argument_type, bool>
179  {
180  protected:
181  _Predicate _M_pred;
182 
183  public:
184  explicit
185  unary_negate(const _Predicate& __x) : _M_pred(__x) { }
186 
187  bool
188  operator()(const argument_type& __x)
189  { return !_M_pred(__x); }
190  };
191 
192 /** @brief Similar to std::binder1st,
193  * but giving the argument types explicitly. */
194 template<typename _Operation, typename first_argument_type,
195  typename second_argument_type, typename result_type>
196  class binder1st
197  : public std::unary_function<second_argument_type, result_type>
198  {
199  protected:
200  _Operation op;
201  first_argument_type value;
202 
203  public:
204  binder1st(const _Operation& __x,
205  const first_argument_type& __y)
206  : op(__x), value(__y) { }
207 
209  operator()(const second_argument_type& __x)
210  { return op(value, __x); }
211 
212  // _GLIBCXX_RESOLVE_LIB_DEFECTS
213  // 109. Missing binders for non-const sequence elements
215  operator()(second_argument_type& __x) const
216  { return op(value, __x); }
217  };
218 
219 /**
220  * @brief Similar to std::binder2nd, but giving the argument types
221  * explicitly.
222  */
223 template<typename _Operation, typename first_argument_type,
224  typename second_argument_type, typename result_type>
225  class binder2nd
226  : public std::unary_function<first_argument_type, result_type>
227  {
228  protected:
229  _Operation op;
230  second_argument_type value;
231 
232  public:
233  binder2nd(const _Operation& __x,
234  const second_argument_type& __y)
235  : op(__x), value(__y) { }
236 
238  operator()(const first_argument_type& __x) const
239  { return op(__x, value); }
240 
241  // _GLIBCXX_RESOLVE_LIB_DEFECTS
242  // 109. Missing binders for non-const sequence elements
244  operator()(first_argument_type& __x)
245  { return op(__x, value); }
246  };
247 
248 /** @brief Similar to std::equal_to, but allows two different types. */
249 template<typename T1, typename T2>
250  struct equal_to : std::binary_function<T1, T2, bool>
251  {
252  bool operator()(const T1& t1, const T2& t2) const
253  { return t1 == t2; }
254  };
255 
256 /** @brief Similar to std::less, but allows two different types. */
257 template<typename T1, typename T2>
258  struct less : std::binary_function<T1, T2, bool>
259  {
260  bool
261  operator()(const T1& t1, const T2& t2) const
262  { return t1 < t2; }
263 
264  bool
265  operator()(const T2& t2, const T1& t1) const
266  { return t2 < t1; }
267  };
268 
269 // Partial specialization for one type. Same as std::less.
270 template<typename _Tp>
271 struct less<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, bool>
272  {
273  bool
274  operator()(const _Tp& __x, const _Tp& __y) const
275  { return __x < __y; }
276  };
277 
278 
279  /** @brief Similar to std::plus, but allows two different types. */
280 template<typename _Tp1, typename _Tp2>
281  struct plus : public std::binary_function<_Tp1, _Tp2, _Tp1>
282  {
283  typedef __typeof__(*static_cast<_Tp1*>(NULL)
284  + *static_cast<_Tp2*>(NULL)) result;
285 
286  result
287  operator()(const _Tp1& __x, const _Tp2& __y) const
288  { return __x + __y; }
289  };
290 
291 // Partial specialization for one type. Same as std::plus.
292 template<typename _Tp>
293  struct plus<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp>
294  {
295  typedef __typeof__(*static_cast<_Tp*>(NULL)
296  + *static_cast<_Tp*>(NULL)) result;
297 
298  result
299  operator()(const _Tp& __x, const _Tp& __y) const
300  { return __x + __y; }
301  };
302 
303 
304 /** @brief Similar to std::multiplies, but allows two different types. */
305 template<typename _Tp1, typename _Tp2>
306  struct multiplies : public std::binary_function<_Tp1, _Tp2, _Tp1>
307  {
308  typedef __typeof__(*static_cast<_Tp1*>(NULL)
309  * *static_cast<_Tp2*>(NULL)) result;
310 
311  result
312  operator()(const _Tp1& __x, const _Tp2& __y) const
313  { return __x * __y; }
314  };
315 
316 // Partial specialization for one type. Same as std::multiplies.
317 template<typename _Tp>
318  struct multiplies<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp>
319  {
320  typedef __typeof__(*static_cast<_Tp*>(NULL)
321  * *static_cast<_Tp*>(NULL)) result;
322 
323  result
324  operator()(const _Tp& __x, const _Tp& __y) const
325  { return __x * __y; }
326  };
327 
328 
329 template<typename T, typename _DifferenceTp>
330  class pseudo_sequence;
331 
332 /** @brief Iterator associated with __gnu_parallel::pseudo_sequence.
333  * If features the usual random-access iterator functionality.
334  * @param T Sequence value type.
335  * @param difference_type Sequence difference type.
336  */
337 template<typename T, typename _DifferenceTp>
339  {
340  public:
341  typedef _DifferenceTp difference_type;
342 
343  private:
345 
346  const T& val;
347  difference_type pos;
348 
349  public:
350  pseudo_sequence_iterator(const T& val, difference_type pos)
351  : val(val), pos(pos) { }
352 
353  // Pre-increment operator.
354  type&
355  operator++()
356  {
357  ++pos;
358  return *this;
359  }
360 
361  // Post-increment operator.
362  const type
363  operator++(int)
364  { return type(pos++); }
365 
366  const T&
367  operator*() const
368  { return val; }
369 
370  const T&
371  operator[](difference_type) const
372  { return val; }
373 
374  bool
375  operator==(const type& i2)
376  { return pos == i2.pos; }
377 
378  difference_type
379  operator!=(const type& i2)
380  { return pos != i2.pos; }
381 
382  difference_type
383  operator-(const type& i2)
384  { return pos - i2.pos; }
385  };
386 
387 /** @brief Sequence that conceptually consists of multiple copies of
388  the same element.
389  * The copies are not stored explicitly, of course.
390  * @param T Sequence value type.
391  * @param difference_type Sequence difference type.
392  */
393 template<typename T, typename _DifferenceTp>
395  {
397 
398  public:
399  typedef _DifferenceTp difference_type;
400 
401  // Better case down to uint64, than up to _DifferenceTp.
403 
404  /** @brief Constructor.
405  * @param val Element of the sequence.
406  * @param count Number of (virtual) copies.
407  */
408  pseudo_sequence(const T& val, difference_type count)
409  : val(val), count(count) { }
410 
411  /** @brief Begin iterator. */
412  iterator
413  begin() const
414  { return iterator(val, 0); }
415 
416  /** @brief End iterator. */
417  iterator
418  end() const
419  { return iterator(val, count); }
420 
421  private:
422  const T& val;
423  difference_type count;
424  };
425 
426 /** @brief Functor that does nothing */
427 template<typename _ValueTp>
429  {
430  inline void
431  operator()(const _ValueTp& v) const { }
432  };
433 
434 /** @brief Compute the median of three referenced elements,
435  according to @c comp.
436  * @param a First iterator.
437  * @param b Second iterator.
438  * @param c Third iterator.
439  * @param comp Comparator.
440  */
441 template<typename RandomAccessIterator, typename Comparator>
442  RandomAccessIterator
443  median_of_three_iterators(RandomAccessIterator a, RandomAccessIterator b,
444  RandomAccessIterator c, Comparator& comp)
445  {
446  if (comp(*a, *b))
447  if (comp(*b, *c))
448  return b;
449  else
450  if (comp(*a, *c))
451  return c;
452  else
453  return a;
454  else
455  {
456  // Just swap a and b.
457  if (comp(*a, *c))
458  return a;
459  else
460  if (comp(*b, *c))
461  return c;
462  else
463  return b;
464  }
465  }
466 
467 #define _GLIBCXX_PARALLEL_ASSERT(_Condition) __glibcxx_assert(_Condition)
468 
469 } //namespace __gnu_parallel
470 
471 #endif /* _GLIBCXX_PARALLEL_BASE_H */