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
38namespace __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 */
198