libstdc++
unique_copy.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/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 
41 /** @brief Parallel std::unique_copy(), w/o explicit equality predicate.
42  * @param first Begin iterator of input sequence.
43  * @param last End iterator of input sequence.
44  * @param result Begin iterator of result sequence.
45  * @param binary_pred Equality predicate.
46  * @return End iterator of result sequence. */
47 template<typename InputIterator,
48  class OutputIterator,
49  class BinaryPredicate>
50  OutputIterator
51  parallel_unique_copy(InputIterator first, InputIterator last,
52  OutputIterator result, BinaryPredicate binary_pred)
53  {
54  _GLIBCXX_CALL(last - first)
55 
56  typedef std::iterator_traits<InputIterator> traits_type;
57  typedef typename traits_type::value_type value_type;
58  typedef typename traits_type::difference_type difference_type;
59 
60  difference_type size = last - first;
61 
62  if (size == 0)
63  return result;
64 
65  // Let the first thread process two parts.
66  difference_type *counter;
67  difference_type *borders;
68 
69  thread_index_t 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 difference_type[num_threads + 2];
77  equally_split(size, num_threads + 1, borders);
78  counter = new difference_type[num_threads + 1];
79  }
80 
81  thread_index_t iam = omp_get_thread_num();
82 
83  difference_type begin, end;
84 
85  // Check for length without duplicates
86  // Needed for position in output
87  difference_type 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 (InputIterator iter = first + begin; iter < first + end; ++iter)
99  {
100  if (!binary_pred(*iter, *(iter-1)))
101  {
102  ++i;
103  *out++ = *iter;
104  }
105  }
106  }
107  else
108  {
109  begin = borders[iam]; //one part
110  end = borders[iam + 1];
111 
112  for (InputIterator iter = first + begin; iter < first + end; ++iter)
113  {
114  if (!binary_pred(*iter, *(iter - 1)))
115  ++i;
116  }
117  }
118  counter[iam] = i;
119 
120  // Last part still untouched.
121  difference_type begin_output;
122 
123 # pragma omp barrier
124 
125  // Store result in output on calculated positions.
126  begin_output = 0;
127 
128  if (iam == 0)
129  {
130  for (int t = 0; t < num_threads; ++t)
131  begin_output += counter[t];
132 
133  i = 0;
134 
135  OutputIterator iter_out = result + begin_output;
136 
137  begin = borders[num_threads];
138  end = size;
139 
140  for (InputIterator iter = first + begin; iter < first + end; ++iter)
141  {
142  if (iter == first || !binary_pred(*iter, *(iter - 1)))
143  {
144  ++i;
145  *iter_out++ = *iter;
146  }
147  }
148 
149  counter[num_threads] = i;
150  }
151  else
152  {
153  for (int t = 0; t < iam; t++)
154  begin_output += counter[t];
155 
156  OutputIterator iter_out = result + begin_output;
157  for (InputIterator iter = first + begin; iter < first + end; ++iter)
158  {
159  if (!binary_pred(*iter, *(iter-1)))
160  *iter_out++ = *iter;
161  }
162  }
163  }
164 
165  difference_type end_output = 0;
166  for (int t = 0; t < num_threads + 1; t++)
167  end_output += counter[t];
168 
169  delete[] borders;
170 
171  return result + end_output;
172  }
173 
174 /** @brief Parallel std::unique_copy(), without explicit equality predicate
175  * @param first Begin iterator of input sequence.
176  * @param last End iterator of input sequence.
177  * @param result Begin iterator of result sequence.
178  * @return End iterator of result sequence. */
179 template<typename InputIterator, class OutputIterator>
180  inline OutputIterator
181  parallel_unique_copy(InputIterator first, InputIterator last,
182  OutputIterator result)
183  {
184  typedef typename std::iterator_traits<InputIterator>::value_type
185  value_type;
186  return parallel_unique_copy(first, last, result,
188  }
189 
190 }//namespace __gnu_parallel
191 
192 #endif /* _GLIBCXX_PARALLEL_UNIQUE_COPY_H */
#define _GLIBCXX_CALL(n)
Macro to produce log message when entering a function.
OutputIterator parallel_unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate binary_pred)
Parallel std::unique_copy(), w/o explicit equality predicate.
Definition: unique_copy.h:51
GNU parallel code for public use.
Functions to find elements of a certain global rank in multiple sorted sequences. Also serves for spl...
One of the comparison functors.
Definition: stl_function.h:199
uint16 thread_index_t
Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit in...
Definition: types.h:141
End-user include file. Provides advanced settings and tuning options. This file is a GNU parallel ext...
OutputIterator equally_split(difference_type n, thread_index_t num_threads, OutputIterator s)
Function to split a sequence into parts of almost equal size.
Definition: equally_split.h:48