diff options
Diffstat (limited to 'libcxx/include/__pstl/internal/parallel_backend_utils.h')
| -rw-r--r-- | libcxx/include/__pstl/internal/parallel_backend_utils.h | 260 |
1 files changed, 260 insertions, 0 deletions
diff --git a/libcxx/include/__pstl/internal/parallel_backend_utils.h b/libcxx/include/__pstl/internal/parallel_backend_utils.h new file mode 100644 index 000000000000..8adcdb71f867 --- /dev/null +++ b/libcxx/include/__pstl/internal/parallel_backend_utils.h @@ -0,0 +1,260 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _PSTL_PARALLEL_BACKEND_UTILS_H +#define _PSTL_PARALLEL_BACKEND_UTILS_H + +#include <__assert> +#include <__config> +#include <__iterator/iterator_traits.h> +#include <__memory/addressof.h> + +#include "utils.h" + +namespace __pstl +{ + +namespace __utils +{ + +//! Destroy sequence [xs,xe) +struct __serial_destroy +{ + template <typename _RandomAccessIterator> + void + operator()(_RandomAccessIterator __zs, _RandomAccessIterator __ze) + { + typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _ValueType; + while (__zs != __ze) + { + --__ze; + (*__ze).~_ValueType(); + } + } +}; + +//! Merge sequences [__xs,__xe) and [__ys,__ye) to output sequence [__zs,(__xe-__xs)+(__ye-__ys)), using std::move +struct __serial_move_merge +{ + const std::size_t _M_nmerge; + + explicit __serial_move_merge(std::size_t __nmerge) : _M_nmerge(__nmerge) {} + template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _RandomAccessIterator3, class _Compare, + class _MoveValueX, class _MoveValueY, class _MoveSequenceX, class _MoveSequenceY> + void + operator()(_RandomAccessIterator1 __xs, _RandomAccessIterator1 __xe, _RandomAccessIterator2 __ys, + _RandomAccessIterator2 __ye, _RandomAccessIterator3 __zs, _Compare __comp, _MoveValueX __move_value_x, + _MoveValueY __move_value_y, _MoveSequenceX __move_sequence_x, _MoveSequenceY __move_sequence_y) + { + constexpr bool __same_move_val = std::is_same<_MoveValueX, _MoveValueY>::value; + constexpr bool __same_move_seq = std::is_same<_MoveSequenceX, _MoveSequenceY>::value; + + auto __n = _M_nmerge; + _LIBCPP_ASSERT_UNCATEGORIZED(__n > 0, ""); + + auto __nx = __xe - __xs; + //auto __ny = __ye - __ys; + _RandomAccessIterator3 __zs_beg = __zs; + + if (__xs != __xe) + { + if (__ys != __ye) + { + for (;;) + { + if (__comp(*__ys, *__xs)) + { + const auto __i = __zs - __zs_beg; + if (__i < __nx) + __move_value_x(__ys, __zs); + else + __move_value_y(__ys, __zs); + ++__zs, --__n; + if (++__ys == __ye) + { + break; + } + else if (__n == 0) + { + const auto __j = __zs - __zs_beg; + if (__same_move_seq || __j < __nx) + __zs = __move_sequence_x(__ys, __ye, __zs); + else + __zs = __move_sequence_y(__ys, __ye, __zs); + break; + } + } + else + { + const auto __i = __zs - __zs_beg; + if (__same_move_val || __i < __nx) + __move_value_x(__xs, __zs); + else + __move_value_y(__xs, __zs); + ++__zs, --__n; + if (++__xs == __xe) + { + const auto __j = __zs - __zs_beg; + if (__same_move_seq || __j < __nx) + __move_sequence_x(__ys, __ye, __zs); + else + __move_sequence_y(__ys, __ye, __zs); + return; + } + else if (__n == 0) + { + const auto __j = __zs - __zs_beg; + if (__same_move_seq || __j < __nx) + { + __zs = __move_sequence_x(__xs, __xe, __zs); + __move_sequence_x(__ys, __ye, __zs); + } + else + { + __zs = __move_sequence_y(__xs, __xe, __zs); + __move_sequence_y(__ys, __ye, __zs); + } + return; + } + } + } + } + __ys = __xs; + __ye = __xe; + } + const auto __i = __zs - __zs_beg; + if (__same_move_seq || __i < __nx) + __move_sequence_x(__ys, __ye, __zs); + else + __move_sequence_y(__ys, __ye, __zs); + } +}; + +template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare, + typename _CopyConstructRange> +_OutputIterator +__set_union_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, + _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp, + _CopyConstructRange __cc_range) +{ + using _Tp = typename std::iterator_traits<_OutputIterator>::value_type; + + for (; __first1 != __last1; ++__result) + { + if (__first2 == __last2) + return __cc_range(__first1, __last1, __result); + if (__comp(*__first2, *__first1)) + { + ::new (std::addressof(*__result)) _Tp(*__first2); + ++__first2; + } + else + { + ::new (std::addressof(*__result)) _Tp(*__first1); + if (!__comp(*__first1, *__first2)) + ++__first2; + ++__first1; + } + } + return __cc_range(__first2, __last2, __result); +} + +template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare> +_OutputIterator +__set_intersection_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, + _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp) +{ + using _Tp = typename std::iterator_traits<_OutputIterator>::value_type; + + for (; __first1 != __last1 && __first2 != __last2;) + { + if (__comp(*__first1, *__first2)) + ++__first1; + else + { + if (!__comp(*__first2, *__first1)) + { + ::new (std::addressof(*__result)) _Tp(*__first1); + ++__result; + ++__first1; + } + ++__first2; + } + } + return __result; +} + +template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare, + typename _CopyConstructRange> +_OutputIterator +__set_difference_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, + _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp, + _CopyConstructRange __cc_range) +{ + using _Tp = typename std::iterator_traits<_OutputIterator>::value_type; + + for (; __first1 != __last1;) + { + if (__first2 == __last2) + return __cc_range(__first1, __last1, __result); + + if (__comp(*__first1, *__first2)) + { + ::new (std::addressof(*__result)) _Tp(*__first1); + ++__result; + ++__first1; + } + else + { + if (!__comp(*__first2, *__first1)) + ++__first1; + ++__first2; + } + } + return __result; +} +template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare, + typename _CopyConstructRange> +_OutputIterator +__set_symmetric_difference_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, + _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp, + _CopyConstructRange __cc_range) +{ + using _Tp = typename std::iterator_traits<_OutputIterator>::value_type; + + for (; __first1 != __last1;) + { + if (__first2 == __last2) + return __cc_range(__first1, __last1, __result); + + if (__comp(*__first1, *__first2)) + { + ::new (std::addressof(*__result)) _Tp(*__first1); + ++__result; + ++__first1; + } + else + { + if (__comp(*__first2, *__first1)) + { + ::new (std::addressof(*__result)) _Tp(*__first2); + ++__result; + } + else + ++__first1; + ++__first2; + } + } + return __cc_range(__first2, __last2, __result); +} + +} // namespace __utils +} // namespace __pstl + +#endif /* _PSTL_PARALLEL_BACKEND_UTILS_H */ |