← Back
Editing: set_operations.h
// -*- C++ -*- // Copyright (C) 2007-2018 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 */
Save File
Cancel