123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197 |
- // -*- C++ -*-
- // Copyright (C) 2007-2022 Free Software Foundation, Inc.
- //
- // This file is part of the GNU ISO C++ Library. This library is free
- // software; you can redistribute it and/or modify it under the terms
- // of the GNU General Public License as published by the Free Software
- // Foundation; either version 3, or (at your option) any later
- // version.
- // This library is distributed in the hope that it will be useful, but
- // WITHOUT ANY WARRANTY; without even the implied warranty of
- // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- // General Public License for more details.
- // Under Section 7 of GPL version 3, you are granted additional
- // permissions described in the GCC Runtime Library Exception, version
- // 3.1, as published by the Free Software Foundation.
- // You should have received a copy of the GNU General Public License and
- // a copy of the GCC Runtime Library Exception along with this program;
- // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
- // <http://www.gnu.org/licenses/>.
- /** @file parallel/unique_copy.h
- * @brief Parallel implementations of std::unique_copy().
- * This file is a GNU parallel extension to the Standard C++ Library.
- */
- // Written by Robert Geisberger and Robin Dapp.
- #ifndef _GLIBCXX_PARALLEL_UNIQUE_COPY_H
- #define _GLIBCXX_PARALLEL_UNIQUE_COPY_H 1
- #include <parallel/parallel.h>
- #include <parallel/multiseq_selection.h>
- namespace __gnu_parallel
- {
- /** @brief Parallel std::unique_copy(), w/__o explicit equality predicate.
- * @param __first Begin iterator of input sequence.
- * @param __last End iterator of input sequence.
- * @param __result Begin iterator of result __sequence.
- * @param __binary_pred Equality predicate.
- * @return End iterator of result __sequence. */
- template<typename _IIter,
- class _OutputIterator,
- class _BinaryPredicate>
- _OutputIterator
- __parallel_unique_copy(_IIter __first, _IIter __last,
- _OutputIterator __result,
- _BinaryPredicate __binary_pred)
- {
- _GLIBCXX_CALL(__last - __first)
- typedef std::iterator_traits<_IIter> _TraitsType;
- typedef typename _TraitsType::value_type _ValueType;
- typedef typename _TraitsType::difference_type _DifferenceType;
- _DifferenceType __size = __last - __first;
- if (__size == 0)
- return __result;
- // Let the first thread process two parts.
- _DifferenceType *__counter;
- _DifferenceType *__borders;
- _ThreadIndex __num_threads = __get_max_threads();
- // First part contains at least one element.
- # pragma omp parallel num_threads(__num_threads)
- {
- # pragma omp single
- {
- __num_threads = omp_get_num_threads();
- __borders = new _DifferenceType[__num_threads + 2];
- __equally_split(__size, __num_threads + 1, __borders);
- __counter = new _DifferenceType[__num_threads + 1];
- }
- _ThreadIndex __iam = omp_get_thread_num();
- _DifferenceType __begin, __end;
- // Check for length without duplicates
- // Needed for position in output
- _DifferenceType __i = 0;
- _OutputIterator __out = __result;
- if (__iam == 0)
- {
- __begin = __borders[0] + 1; // == 1
- __end = __borders[__iam + 1];
- ++__i;
- *__out++ = *__first;
- for (_IIter __iter = __first + __begin; __iter < __first + __end;
- ++__iter)
- {
- if (!__binary_pred(*__iter, *(__iter - 1)))
- {
- ++__i;
- *__out++ = *__iter;
- }
- }
- }
- else
- {
- __begin = __borders[__iam]; //one part
- __end = __borders[__iam + 1];
- for (_IIter __iter = __first + __begin; __iter < __first + __end;
- ++__iter)
- {
- if (!__binary_pred(*__iter, *(__iter - 1)))
- ++__i;
- }
- }
- __counter[__iam] = __i;
- // Last part still untouched.
- _DifferenceType __begin_output;
- # pragma omp barrier
- // Store result in output on calculated positions.
- __begin_output = 0;
- if (__iam == 0)
- {
- for (_ThreadIndex __t = 0; __t < __num_threads; ++__t)
- __begin_output += __counter[__t];
- __i = 0;
- _OutputIterator __iter_out = __result + __begin_output;
- __begin = __borders[__num_threads];
- __end = __size;
- for (_IIter __iter = __first + __begin; __iter < __first + __end;
- ++__iter)
- {
- if (__iter == __first
- || !__binary_pred(*__iter, *(__iter - 1)))
- {
- ++__i;
- *__iter_out++ = *__iter;
- }
- }
- __counter[__num_threads] = __i;
- }
- else
- {
- for (_ThreadIndex __t = 0; __t < __iam; __t++)
- __begin_output += __counter[__t];
- _OutputIterator __iter_out = __result + __begin_output;
- for (_IIter __iter = __first + __begin; __iter < __first + __end;
- ++__iter)
- {
- if (!__binary_pred(*__iter, *(__iter - 1)))
- *__iter_out++ = *__iter;
- }
- }
- }
- _DifferenceType __end_output = 0;
- for (_ThreadIndex __t = 0; __t < __num_threads + 1; __t++)
- __end_output += __counter[__t];
- delete[] __borders;
- return __result + __end_output;
- }
- /** @brief Parallel std::unique_copy(), without explicit equality predicate
- * @param __first Begin iterator of input sequence.
- * @param __last End iterator of input sequence.
- * @param __result Begin iterator of result __sequence.
- * @return End iterator of result __sequence. */
- template<typename _IIter, class _OutputIterator>
- inline _OutputIterator
- __parallel_unique_copy(_IIter __first, _IIter __last,
- _OutputIterator __result)
- {
- typedef typename std::iterator_traits<_IIter>::value_type
- _ValueType;
- return __parallel_unique_copy(__first, __last, __result,
- std::equal_to<_ValueType>());
- }
- }//namespace __gnu_parallel
- #endif /* _GLIBCXX_PARALLEL_UNIQUE_COPY_H */
|