diff options
Diffstat (limited to 'libstdc++-v3/include/parallel/set_operations.h')
| -rw-r--r-- | libstdc++-v3/include/parallel/set_operations.h | 529 |
1 files changed, 529 insertions, 0 deletions
diff --git a/libstdc++-v3/include/parallel/set_operations.h b/libstdc++-v3/include/parallel/set_operations.h new file mode 100644 index 000000000..f552c1dda --- /dev/null +++ b/libstdc++-v3/include/parallel/set_operations.h @@ -0,0 +1,529 @@ +// -*- C++ -*- + +// Copyright (C) 2007, 2008, 2009, 2010 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 */ |