diff options
Diffstat (limited to 'libstdc++-v3/include/parallel/set_operations.h')
| -rw-r--r-- | libstdc++-v3/include/parallel/set_operations.h | 841 |
1 files changed, 420 insertions, 421 deletions
diff --git a/libstdc++-v3/include/parallel/set_operations.h b/libstdc++-v3/include/parallel/set_operations.h index ac669c55d5d..6dd63c9b128 100644 --- a/libstdc++-v3/include/parallel/set_operations.h +++ b/libstdc++-v3/include/parallel/set_operations.h @@ -41,490 +41,489 @@ 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) + 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 { - do + while (__a != __b && __c != __d) { - *__r++ = *__b.first++; + if (_M_comp(*__a, *__c)) + { + *__r = *__a; + ++__a; + ++__r; + } + else if (_M_comp(*__c, *__a)) + { + *__r = *__c; + ++__c; + ++__r; + } + else + { + ++__a; + ++__c; + } } - while (__b.first != __e.first); + return std::copy(__c, __d, std::copy(__a, __b, __r)); } - else + + _DifferenceType + __count(_IIter __a, _IIter __b, _IIter __c, _IIter d) const { - while (__b.second != __e.second) - *__r++ = *__b.second++; + _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); } - 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; + _OutputIterator + __first_empty(_IIter __c, _IIter d, _OutputIterator __out) const + { return std::copy(__c, d, __out); } - symmetric_difference_func(_Compare __comp) : _M_comp(__comp) {} + _OutputIterator + __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const + { return std::copy(__a, __b, __out); } + }; - _Compare _M_comp; - _OutputIterator - _M_invoke(_IIter __a, _IIter __b, - _IIter __c, _IIter d, - _OutputIterator __r) const + template<typename _IIter, + typename _OutputIterator, + typename _Compare> + struct __difference_func { - 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)); - } + typedef std::iterator_traits<_IIter> _TraitsType; + typedef typename _TraitsType::difference_type _DifferenceType; + typedef typename std::pair<_IIter, _IIter> _IteratorPair; - _DifferenceType - __count(_IIter __a, _IIter __b, - _IIter __c, _IIter d) const - { - _DifferenceType __counter = 0; + __difference_func(_Compare __comp) : _M_comp(__comp) {} - while (__a != __b && __c != d) - { - if (_M_comp(*__a, *__c)) - { - ++__a; - ++__counter; - } - else if (_M_comp(*__c, *__a)) - { - ++__c; - ++__counter; - } - else - { - ++__a; - ++__c; - } - } + _Compare _M_comp; - return __counter + (__b - __a) + (d - __c); - } + _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); + } - _OutputIterator - __first_empty(_IIter __c, _IIter d, _OutputIterator __out) const - { return std::copy(__c, d, __out); } + _DifferenceType + __count(_IIter __a, _IIter __b, + _IIter __c, _IIter d) const + { + _DifferenceType __counter = 0; - _OutputIterator - __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const - { return std::copy(__a, __b, __out); } - }; + 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); + } -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; + _OutputIterator + __first_empty(_IIter, _IIter, _OutputIterator __out) const + { return __out; } - __difference_func(_Compare __comp) : _M_comp(__comp) {} + _OutputIterator + __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const + { return std::copy(__a, __b, __out); } + }; - _Compare _M_comp; - _OutputIterator - _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter d, - _OutputIterator __r) const + template<typename _IIter, + typename _OutputIterator, + typename _Compare> + struct __intersection_func { - 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); - } + typedef std::iterator_traits<_IIter> _TraitsType; + typedef typename _TraitsType::difference_type _DifferenceType; + typedef typename std::pair<_IIter, _IIter> _IteratorPair; - _DifferenceType - __count(_IIter __a, _IIter __b, - _IIter __c, _IIter d) const - { - _DifferenceType __counter = 0; + __intersection_func(_Compare __comp) : _M_comp(__comp) {} - while (__a != __b && __c != d) - { - if (_M_comp(*__a, *__c)) - { - ++__a; - ++__counter; - } - else if (_M_comp(*__c, *__a)) - { ++__c; } - else - { ++__a; ++__c; } - } + _Compare _M_comp; - return __counter + (__b - __a); - } + _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; + } + } - inline _OutputIterator - __first_empty(_IIter __c, _IIter d, _OutputIterator __out) const - { return __out; } + return __r; + } - inline _OutputIterator - __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const - { return std::copy(__a, __b, __out); } - }; + _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; + } + } -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; + return __counter; + } - __intersection_func(_Compare __comp) : _M_comp(__comp) {} + _OutputIterator + __first_empty(_IIter, _IIter, _OutputIterator __out) const + { return __out; } - _Compare _M_comp; + _OutputIterator + __second_empty(_IIter, _IIter, _OutputIterator __out) const + { return __out; } + }; - _OutputIterator - _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter d, - _OutputIterator __r) const + template<class _IIter, class _OutputIterator, class _Compare> + struct __union_func { - while (__a != __b && __c != d) - { - if (_M_comp(*__a, *__c)) - { ++__a; } - else if (_M_comp(*__c, *__a)) - { ++__c; } - else - { - *__r = *__a; - ++__a; - ++__c; - ++__r; - } - } + typedef typename std::iterator_traits<_IIter>::difference_type + _DifferenceType; - return __r; - } + __union_func(_Compare __comp) : _M_comp(__comp) {} - _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; - } - } + _Compare _M_comp; - return __counter; - } + _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)); + } - inline _OutputIterator - __first_empty(_IIter __c, _IIter d, _OutputIterator __out) const - { return __out; } + _DifferenceType + __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const + { + _DifferenceType __counter = 0; - inline _OutputIterator - __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const - { return __out; } - }; + while (__a != __b && __c != __d) + { + if (_M_comp(*__a, *__c)) + { ++__a; } + else if (_M_comp(*__c, *__a)) + { ++__c; } + else + { + ++__a; + ++__c; + } + ++__counter; + } -template<class _IIter, class _OutputIterator, class _Compare> - struct __union_func - { - typedef typename std::iterator_traits<_IIter>::difference_type - _DifferenceType; + __counter += (__b - __a); + __counter += (__d - __c); + return __counter; + } - __union_func(_Compare __comp) : _M_comp(__comp) {} + _OutputIterator + __first_empty(_IIter __c, _IIter __d, _OutputIterator __out) const + { return std::copy(__c, __d, __out); } - _Compare _M_comp; + _OutputIterator + __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const + { return std::copy(__a, __b, __out); } + }; + template<typename _IIter, + typename _OutputIterator, + typename Operation> _OutputIterator - _M_invoke(_IIter __a, const _IIter __b, _IIter __c, - const _IIter d, _OutputIterator __r) const + __parallel_set_operation(_IIter __begin1, _IIter __end1, + _IIter __begin2, _IIter __end2, + _OutputIterator __result, Operation __op) { - 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)); - } + _GLIBCXX_CALL((__end1 - __begin1) + (__end2 - __begin2)) - _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; - } + typedef std::iterator_traits<_IIter> _TraitsType; + typedef typename _TraitsType::difference_type _DifferenceType; + typedef typename std::pair<_IIter, _IIter> _IteratorPair; - __counter += (__b - __a); - __counter += (d - __c); - return __counter; - } + if (__begin1 == __end1) + return __op.__first_empty(__begin2, __end2, __result); - inline _OutputIterator - __first_empty(_IIter __c, _IIter d, _OutputIterator __out) const - { return std::copy(__c, d, __out); } + if (__begin2 == __end2) + return __op.__second_empty(__begin1, __end1, __result); - inline _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) + 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 ]); + { + __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 - // Make sure all threads have their block_begin result written out. + _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 - _IteratorPair __block_begin = __block_begins[ __iam ]; + _OutputIterator __r = __result; - // 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); - } + if (__iam == 0) + { + // Do the last block. + for (int __i = 0; __i < __num_threads; ++__i) + __r += __lengths[__i]; - // Make sure everyone wrote their lengths. -# pragma omp barrier + __block_begin = __block_begins[__num_threads]; - _OutputIterator __r = __result; + // Return the result iterator of the last block. + __return_value = + __op._M_invoke(__block_begin.first, __end1, + __block_begin.second, __end2, __r); - if (__iam == 0) - { - // Do the last block. - for (int __i = 0; __i < __num_threads; ++__i) - __r += __lengths[__i]; + } + else + { + for (int __i = 0; __i < __iam; ++__i) + __r += __lengths[ __i ]; - __block_begin = __block_begins[__num_threads]; + // Reset begins for copy pass. + __op._M_invoke(__block_begin.first, __block_end.first, + __block_begin.second, __block_end.second, __r); + } + } + return __return_value; + } - // Return the result iterator of the last block. - return_value = __op._M_invoke( - __block_begin.first, __end1, __block_begin.second, __end2, __r); + 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)); + } - } - else - { - for (int __i = 0; __i < __iam; ++__i) - __r += __lengths[ __i ]; + 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)); + } - // 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 _M_comp) - { - return __parallel_set_operation(__begin1, __end1, __begin2, __end2, - __result, __union_func< _IIter, _OutputIterator, _Compare>(_M_comp)); - } - -template<typename _IIter, - typename _OutputIterator, - typename _Compare> - inline _OutputIterator - __parallel_set_intersection(_IIter __begin1, _IIter __end1, + template<typename _IIter, + typename _OutputIterator, + typename _Compare> + inline _OutputIterator + __parallel_set_difference(_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, - _OutputIterator __result, _Compare _M_comp) - { - return __parallel_set_operation( - __begin1, __end1, __begin2, __end2, __result, - __intersection_func<_IIter, _OutputIterator, _Compare>(_M_comp)); - } - -template<typename _IIter, - typename _OutputIterator, - typename _Compare> - inline _OutputIterator - __parallel_set_difference(_IIter __begin1, _IIter __end1, - _IIter __begin2, _IIter __end2, - _OutputIterator __result, _Compare _M_comp) - { - return __parallel_set_operation( - __begin1, __end1, __begin2, __end2, __result, - __difference_func<_IIter, _OutputIterator, _Compare>(_M_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 _M_comp) - { - return __parallel_set_operation( - __begin1, __end1, __begin2, __end2, __result, - symmetric_difference_func<_IIter, _OutputIterator, _Compare> - (_M_comp)); - } + _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 */ |