diff options
Diffstat (limited to 'libstdc++-v3/include/parallel/unique_copy.h')
| -rw-r--r-- | libstdc++-v3/include/parallel/unique_copy.h | 279 |
1 files changed, 142 insertions, 137 deletions
diff --git a/libstdc++-v3/include/parallel/unique_copy.h b/libstdc++-v3/include/parallel/unique_copy.h index 327870e7d86..1ae5a12316d 100644 --- a/libstdc++-v3/include/parallel/unique_copy.h +++ b/libstdc++-v3/include/parallel/unique_copy.h @@ -37,155 +37,160 @@ 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) + /** @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) { - __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]; + __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]; - _ThreadIndex __iam = omp_get_thread_num(); + for (_IIter __iter = __first + __begin; __iter < __first + __end; + ++__iter) + { + if (!__binary_pred(*__iter, *(__iter - 1))) + ++__i; + } + } + __counter[__iam] = __i; - _DifferenceType __begin, __end; + // Last part still untouched. + _DifferenceType __begin_output; - // Check for length without duplicates - // Needed for position in output - _DifferenceType __i = 0; - _OutputIterator __out = __result; +# pragma omp barrier - if (__iam == 0) - { - __begin = __borders[0] + 1; // == 1 - __end = __borders[__iam + 1]; + // Store result in output on calculated positions. + __begin_output = 0; - ++__i; - *__out++ = *__first; + if (__iam == 0) + { + for (int __t = 0; __t < __num_threads; ++__t) + __begin_output += __counter[__t]; - 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 (int __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 (int __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; - } - } + __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 (int __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 (int __t = 0; __t < __num_threads + 1; __t++) + __end_output += __counter[__t]; + + delete[] __borders; + + return __result + __end_output; } - _DifferenceType __end_output = 0; - for (int __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>()); - } + /** @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 |