| // -*- C++ -*- |
| |
| // Copyright (C) 2007-2020 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/set_operations.h |
| * @brief Parallel implementations of set operations for random-access |
| * iterators. |
| * This file is a GNU parallel extension to the Standard C++ Library. |
| */ |
| |
| // Written by Marius Elvert and Felix Bondarenko. |
| |
| #ifndef _GLIBCXX_PARALLEL_SET_OPERATIONS_H |
| #define _GLIBCXX_PARALLEL_SET_OPERATIONS_H 1 |
| |
| #include <omp.h> |
| |
| #include <parallel/settings.h> |
| #include <parallel/multiseq_selection.h> |
| |
| namespace __gnu_parallel |
| { |
| template<typename _IIter, typename _OutputIterator> |
| _OutputIterator |
| __copy_tail(std::pair<_IIter, _IIter> __b, |
| std::pair<_IIter, _IIter> __e, _OutputIterator __r) |
| { |
| if (__b.first != __e.first) |
| { |
| do |
| { |
| *__r++ = *__b.first++; |
| } |
| while (__b.first != __e.first); |
| } |
| else |
| { |
| while (__b.second != __e.second) |
| *__r++ = *__b.second++; |
| } |
| return __r; |
| } |
| |
| template<typename _IIter, |
| typename _OutputIterator, |
| typename _Compare> |
| struct __symmetric_difference_func |
| { |
| typedef std::iterator_traits<_IIter> _TraitsType; |
| typedef typename _TraitsType::difference_type _DifferenceType; |
| typedef typename std::pair<_IIter, _IIter> _IteratorPair; |
| |
| __symmetric_difference_func(_Compare __comp) : _M_comp(__comp) {} |
| |
| _Compare _M_comp; |
| |
| _OutputIterator |
| _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d, |
| _OutputIterator __r) const |
| { |
| while (__a != __b && __c != __d) |
| { |
| if (_M_comp(*__a, *__c)) |
| { |
| *__r = *__a; |
| ++__a; |
| ++__r; |
| } |
| else if (_M_comp(*__c, *__a)) |
| { |
| *__r = *__c; |
| ++__c; |
| ++__r; |
| } |
| else |
| { |
| ++__a; |
| ++__c; |
| } |
| } |
| return std::copy(__c, __d, std::copy(__a, __b, __r)); |
| } |
| |
| _DifferenceType |
| __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const |
| { |
| _DifferenceType __counter = 0; |
| |
| while (__a != __b && __c != __d) |
| { |
| if (_M_comp(*__a, *__c)) |
| { |
| ++__a; |
| ++__counter; |
| } |
| else if (_M_comp(*__c, *__a)) |
| { |
| ++__c; |
| ++__counter; |
| } |
| else |
| { |
| ++__a; |
| ++__c; |
| } |
| } |
| |
| return __counter + (__b - __a) + (__d - __c); |
| } |
| |
| _OutputIterator |
| __first_empty(_IIter __c, _IIter __d, _OutputIterator __out) const |
| { return std::copy(__c, __d, __out); } |
| |
| _OutputIterator |
| __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const |
| { return std::copy(__a, __b, __out); } |
| }; |
| |
| |
| template<typename _IIter, |
| typename _OutputIterator, |
| typename _Compare> |
| struct __difference_func |
| { |
| typedef std::iterator_traits<_IIter> _TraitsType; |
| typedef typename _TraitsType::difference_type _DifferenceType; |
| typedef typename std::pair<_IIter, _IIter> _IteratorPair; |
| |
| __difference_func(_Compare __comp) : _M_comp(__comp) {} |
| |
| _Compare _M_comp; |
| |
| _OutputIterator |
| _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d, |
| _OutputIterator __r) const |
| { |
| while (__a != __b && __c != __d) |
| { |
| if (_M_comp(*__a, *__c)) |
| { |
| *__r = *__a; |
| ++__a; |
| ++__r; |
| } |
| else if (_M_comp(*__c, *__a)) |
| { ++__c; } |
| else |
| { |
| ++__a; |
| ++__c; |
| } |
| } |
| return std::copy(__a, __b, __r); |
| } |
| |
| _DifferenceType |
| __count(_IIter __a, _IIter __b, |
| _IIter __c, _IIter __d) const |
| { |
| _DifferenceType __counter = 0; |
| |
| while (__a != __b && __c != __d) |
| { |
| if (_M_comp(*__a, *__c)) |
| { |
| ++__a; |
| ++__counter; |
| } |
| else if (_M_comp(*__c, *__a)) |
| { ++__c; } |
| else |
| { ++__a; ++__c; } |
| } |
| |
| return __counter + (__b - __a); |
| } |
| |
| _OutputIterator |
| __first_empty(_IIter, _IIter, _OutputIterator __out) const |
| { return __out; } |
| |
| _OutputIterator |
| __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const |
| { return std::copy(__a, __b, __out); } |
| }; |
| |
| |
| template<typename _IIter, |
| typename _OutputIterator, |
| typename _Compare> |
| struct __intersection_func |
| { |
| typedef std::iterator_traits<_IIter> _TraitsType; |
| typedef typename _TraitsType::difference_type _DifferenceType; |
| typedef typename std::pair<_IIter, _IIter> _IteratorPair; |
| |
| __intersection_func(_Compare __comp) : _M_comp(__comp) {} |
| |
| _Compare _M_comp; |
| |
| _OutputIterator |
| _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d, |
| _OutputIterator __r) const |
| { |
| while (__a != __b && __c != __d) |
| { |
| if (_M_comp(*__a, *__c)) |
| { ++__a; } |
| else if (_M_comp(*__c, *__a)) |
| { ++__c; } |
| else |
| { |
| *__r = *__a; |
| ++__a; |
| ++__c; |
| ++__r; |
| } |
| } |
| |
| return __r; |
| } |
| |
| _DifferenceType |
| __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const |
| { |
| _DifferenceType __counter = 0; |
| |
| while (__a != __b && __c != __d) |
| { |
| if (_M_comp(*__a, *__c)) |
| { ++__a; } |
| else if (_M_comp(*__c, *__a)) |
| { ++__c; } |
| else |
| { |
| ++__a; |
| ++__c; |
| ++__counter; |
| } |
| } |
| |
| return __counter; |
| } |
| |
| _OutputIterator |
| __first_empty(_IIter, _IIter, _OutputIterator __out) const |
| { return __out; } |
| |
| _OutputIterator |
| __second_empty(_IIter, _IIter, _OutputIterator __out) const |
| { return __out; } |
| }; |
| |
| template<class _IIter, class _OutputIterator, class _Compare> |
| struct __union_func |
| { |
| typedef typename std::iterator_traits<_IIter>::difference_type |
| _DifferenceType; |
| |
| __union_func(_Compare __comp) : _M_comp(__comp) {} |
| |
| _Compare _M_comp; |
| |
| _OutputIterator |
| _M_invoke(_IIter __a, const _IIter __b, _IIter __c, |
| const _IIter __d, _OutputIterator __r) const |
| { |
| while (__a != __b && __c != __d) |
| { |
| if (_M_comp(*__a, *__c)) |
| { |
| *__r = *__a; |
| ++__a; |
| } |
| else if (_M_comp(*__c, *__a)) |
| { |
| *__r = *__c; |
| ++__c; |
| } |
| else |
| { |
| *__r = *__a; |
| ++__a; |
| ++__c; |
| } |
| ++__r; |
| } |
| return std::copy(__c, __d, std::copy(__a, __b, __r)); |
| } |
| |
| _DifferenceType |
| __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const |
| { |
| _DifferenceType __counter = 0; |
| |
| while (__a != __b && __c != __d) |
| { |
| if (_M_comp(*__a, *__c)) |
| { ++__a; } |
| else if (_M_comp(*__c, *__a)) |
| { ++__c; } |
| else |
| { |
| ++__a; |
| ++__c; |
| } |
| ++__counter; |
| } |
| |
| __counter += (__b - __a); |
| __counter += (__d - __c); |
| return __counter; |
| } |
| |
| _OutputIterator |
| __first_empty(_IIter __c, _IIter __d, _OutputIterator __out) const |
| { return std::copy(__c, __d, __out); } |
| |
| _OutputIterator |
| __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const |
| { return std::copy(__a, __b, __out); } |
| }; |
| |
| template<typename _IIter, |
| typename _OutputIterator, |
| typename _Operation> |
| _OutputIterator |
| __parallel_set_operation(_IIter __begin1, _IIter __end1, |
| _IIter __begin2, _IIter __end2, |
| _OutputIterator __result, _Operation __op) |
| { |
| _GLIBCXX_CALL((__end1 - __begin1) + (__end2 - __begin2)) |
| |
| typedef std::iterator_traits<_IIter> _TraitsType; |
| typedef typename _TraitsType::difference_type _DifferenceType; |
| typedef typename std::pair<_IIter, _IIter> _IteratorPair; |
| |
| if (__begin1 == __end1) |
| return __op.__first_empty(__begin2, __end2, __result); |
| |
| if (__begin2 == __end2) |
| return __op.__second_empty(__begin1, __end1, __result); |
| |
| const _DifferenceType __size = (__end1 - __begin1) + (__end2 - __begin2); |
| |
| const _IteratorPair __sequence[2] = { std::make_pair(__begin1, __end1), |
| std::make_pair(__begin2, __end2) }; |
| _OutputIterator __return_value = __result; |
| _DifferenceType *__borders; |
| _IteratorPair *__block_begins; |
| _DifferenceType* __lengths; |
| |
| _ThreadIndex __num_threads = |
| std::min<_DifferenceType>(__get_max_threads(), |
| std::min(__end1 - __begin1, __end2 - __begin2)); |
| |
| # 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); |
| __block_begins = new _IteratorPair[__num_threads + 1]; |
| // Very __start. |
| __block_begins[0] = std::make_pair(__begin1, __begin2); |
| __lengths = new _DifferenceType[__num_threads]; |
| } //single |
| |
| _ThreadIndex __iam = omp_get_thread_num(); |
| |
| // _Result from multiseq_partition. |
| _IIter __offset[2]; |
| const _DifferenceType __rank = __borders[__iam + 1]; |
| |
| multiseq_partition(__sequence, __sequence + 2, |
| __rank, __offset, __op._M_comp); |
| |
| // allowed to read? |
| // together |
| // *(__offset[ 0 ] - 1) == *__offset[ 1 ] |
| if (__offset[ 0 ] != __begin1 && __offset[1] != __end2 |
| && !__op._M_comp(*(__offset[0] - 1), *__offset[1]) |
| && !__op._M_comp(*__offset[1], *(__offset[0] - 1))) |
| { |
| // Avoid split between globally equal elements: move one to |
| // front in first sequence. |
| --__offset[0]; |
| } |
| |
| _IteratorPair __block_end = __block_begins[__iam + 1] = |
| _IteratorPair(__offset[0], __offset[1]); |
| |
| // Make sure all threads have their block_begin result written out. |
| # pragma omp barrier |
| |
| _IteratorPair __block_begin = __block_begins[__iam]; |
| |
| // Begin working for the first block, while the others except |
| // the last start to count. |
| if (__iam == 0) |
| { |
| // The first thread can copy already. |
| __lengths[ __iam ] = |
| __op._M_invoke(__block_begin.first, __block_end.first, |
| __block_begin.second, __block_end.second, |
| __result) - __result; |
| } |
| else |
| { |
| __lengths[ __iam ] = |
| __op.__count(__block_begin.first, __block_end.first, |
| __block_begin.second, __block_end.second); |
| } |
| |
| // Make sure everyone wrote their lengths. |
| # pragma omp barrier |
| |
| _OutputIterator __r = __result; |
| |
| if (__iam == 0) |
| { |
| // Do the last block. |
| for (_ThreadIndex __i = 0; __i < __num_threads; ++__i) |
| __r += __lengths[__i]; |
| |
| __block_begin = __block_begins[__num_threads]; |
| |
| // Return the result iterator of the last block. |
| __return_value = |
| __op._M_invoke(__block_begin.first, __end1, |
| __block_begin.second, __end2, __r); |
| |
| } |
| else |
| { |
| for (_ThreadIndex __i = 0; __i < __iam; ++__i) |
| __r += __lengths[ __i ]; |
| |
| // Reset begins for copy pass. |
| __op._M_invoke(__block_begin.first, __block_end.first, |
| __block_begin.second, __block_end.second, __r); |
| } |
| } |
| return __return_value; |
| } |
| |
| template<typename _IIter, |
| typename _OutputIterator, |
| typename _Compare> |
| inline _OutputIterator |
| __parallel_set_union(_IIter __begin1, _IIter __end1, |
| _IIter __begin2, _IIter __end2, |
| _OutputIterator __result, _Compare __comp) |
| { |
| return __parallel_set_operation(__begin1, __end1, __begin2, __end2, |
| __result, |
| __union_func< _IIter, _OutputIterator, |
| _Compare>(__comp)); |
| } |
| |
| template<typename _IIter, |
| typename _OutputIterator, |
| typename _Compare> |
| inline _OutputIterator |
| __parallel_set_intersection(_IIter __begin1, _IIter __end1, |
| _IIter __begin2, _IIter __end2, |
| _OutputIterator __result, _Compare __comp) |
| { |
| return __parallel_set_operation(__begin1, __end1, __begin2, __end2, |
| __result, |
| __intersection_func<_IIter, |
| _OutputIterator, _Compare>(__comp)); |
| } |
| |
| template<typename _IIter, |
| typename _OutputIterator, |
| typename _Compare> |
| inline _OutputIterator |
| __parallel_set_difference(_IIter __begin1, _IIter __end1, |
| _IIter __begin2, _IIter __end2, |
| _OutputIterator __result, _Compare __comp) |
| { |
| return __parallel_set_operation(__begin1, __end1, __begin2, __end2, |
| __result, |
| __difference_func<_IIter, |
| _OutputIterator, _Compare>(__comp)); |
| } |
| |
| template<typename _IIter, |
| typename _OutputIterator, |
| typename _Compare> |
| inline _OutputIterator |
| __parallel_set_symmetric_difference(_IIter __begin1, _IIter __end1, |
| _IIter __begin2, _IIter __end2, |
| _OutputIterator __result, |
| _Compare __comp) |
| { |
| return __parallel_set_operation(__begin1, __end1, __begin2, __end2, |
| __result, |
| __symmetric_difference_func<_IIter, |
| _OutputIterator, _Compare>(__comp)); |
| } |
| } |
| |
| #endif /* _GLIBCXX_PARALLEL_SET_OPERATIONS_H */ |
