libstdc++
unique_copy.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007, 2008, 2009, 2010, 2011 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/unique_copy.h
26  * @brief Parallel implementations of std::unique_copy().
27  * This file is a GNU parallel extension to the Standard C++ Library.
28  */
29 
30 // Written by Robert Geisberger and Robin Dapp.
31 
32 #ifndef _GLIBCXX_PARALLEL_UNIQUE_COPY_H
33 #define _GLIBCXX_PARALLEL_UNIQUE_COPY_H 1
34 
35 #include <parallel/parallel.h>
37 
38 namespace __gnu_parallel
39 {
40  /** @brief Parallel std::unique_copy(), w/__o explicit equality predicate.
41  * @param __first Begin iterator of input sequence.
42  * @param __last End iterator of input sequence.
43  * @param __result Begin iterator of result __sequence.
44  * @param __binary_pred Equality predicate.
45  * @return End iterator of result __sequence. */
46  template<typename _IIter,
47  class _OutputIterator,
48  class _BinaryPredicate>
49  _OutputIterator
50  __parallel_unique_copy(_IIter __first, _IIter __last,
51  _OutputIterator __result,
52  _BinaryPredicate __binary_pred)
53  {
54  _GLIBCXX_CALL(__last - __first)
55 
56  typedef std::iterator_traits<_IIter> _TraitsType;
57  typedef typename _TraitsType::value_type _ValueType;
58  typedef typename _TraitsType::difference_type _DifferenceType;
59 
60  _DifferenceType __size = __last - __first;
61 
62  if (__size == 0)
63  return __result;
64 
65  // Let the first thread process two parts.
66  _DifferenceType *__counter;
67  _DifferenceType *__borders;
68 
69  _ThreadIndex __num_threads = __get_max_threads();
70  // First part contains at least one element.
71 # pragma omp parallel num_threads(__num_threads)
72  {
73 # pragma omp single
74  {
75  __num_threads = omp_get_num_threads();
76  __borders = new _DifferenceType[__num_threads + 2];
77  __equally_split(__size, __num_threads + 1, __borders);
78  __counter = new _DifferenceType[__num_threads + 1];
79  }
80 
81  _ThreadIndex __iam = omp_get_thread_num();
82 
83  _DifferenceType __begin, __end;
84 
85  // Check for length without duplicates
86  // Needed for position in output
87  _DifferenceType __i = 0;
88  _OutputIterator __out = __result;
89 
90  if (__iam == 0)
91  {
92  __begin = __borders[0] + 1; // == 1
93  __end = __borders[__iam + 1];
94 
95  ++__i;
96  *__out++ = *__first;
97 
98  for (_IIter __iter = __first + __begin; __iter < __first + __end;
99  ++__iter)
100  {
101  if (!__binary_pred(*__iter, *(__iter - 1)))
102  {
103  ++__i;
104  *__out++ = *__iter;
105  }
106  }
107  }
108  else
109  {
110  __begin = __borders[__iam]; //one part
111  __end = __borders[__iam + 1];
112 
113  for (_IIter __iter = __first + __begin; __iter < __first + __end;
114  ++__iter)
115  {
116  if (!__binary_pred(*__iter, *(__iter - 1)))
117  ++__i;
118  }
119  }
120  __counter[__iam] = __i;
121 
122  // Last part still untouched.
123  _DifferenceType __begin_output;
124 
125 # pragma omp barrier
126 
127  // Store result in output on calculated positions.
128  __begin_output = 0;
129 
130  if (__iam == 0)
131  {
132  for (_ThreadIndex __t = 0; __t < __num_threads; ++__t)
133  __begin_output += __counter[__t];
134 
135  __i = 0;
136 
137  _OutputIterator __iter_out = __result + __begin_output;
138 
139  __begin = __borders[__num_threads];
140  __end = __size;
141 
142  for (_IIter __iter = __first + __begin; __iter < __first + __end;
143  ++__iter)
144  {
145  if (__iter == __first
146  || !__binary_pred(*__iter, *(__iter - 1)))
147  {
148  ++__i;
149  *__iter_out++ = *__iter;
150  }
151  }
152 
153  __counter[__num_threads] = __i;
154  }
155  else
156  {
157  for (_ThreadIndex __t = 0; __t < __iam; __t++)
158  __begin_output += __counter[__t];
159 
160  _OutputIterator __iter_out = __result + __begin_output;
161  for (_IIter __iter = __first + __begin; __iter < __first + __end;
162  ++__iter)
163  {
164  if (!__binary_pred(*__iter, *(__iter - 1)))
165  *__iter_out++ = *__iter;
166  }
167  }
168  }
169 
170  _DifferenceType __end_output = 0;
171  for (_ThreadIndex __t = 0; __t < __num_threads + 1; __t++)
172  __end_output += __counter[__t];
173 
174  delete[] __borders;
175 
176  return __result + __end_output;
177  }
178 
179  /** @brief Parallel std::unique_copy(), without explicit equality predicate
180  * @param __first Begin iterator of input sequence.
181  * @param __last End iterator of input sequence.
182  * @param __result Begin iterator of result __sequence.
183  * @return End iterator of result __sequence. */
184  template<typename _IIter, class _OutputIterator>
185  inline _OutputIterator
186  __parallel_unique_copy(_IIter __first, _IIter __last,
187  _OutputIterator __result)
188  {
189  typedef typename std::iterator_traits<_IIter>::value_type
190  _ValueType;
191  return __parallel_unique_copy(__first, __last, __result,
193  }
194 
195 }//namespace __gnu_parallel
196 
197 #endif /* _GLIBCXX_PARALLEL_UNIQUE_COPY_H */