]>
Commit | Line | Data |
---|---|---|
1 | // -*- C++ -*- | |
2 | ||
3 | // Copyright (C) 2007-2020 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 */ |