1 // -*- C++ -*-
2
3 // Copyright (C) 2007-2023 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>
36 #include <parallel/multiseq_selection.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,
192 std::equal_to<_ValueType>());
193 }
194
195 }//namespace __gnu_parallel
196
197 #endif /* _GLIBCXX_PARALLEL_UNIQUE_COPY_H */