| // -*- 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 <iterator> |
| #include <utility> |
| #include <cassert> |
| #include "utils.h" |
| |
| #include "pstl_config.h" |
| |
| _PSTL_HIDE_FROM_ABI_PUSH |
| |
| 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; |
| assert(__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); |
| } |
| }; |
| |
| } // namespace __utils |
| } // namespace __pstl |
| |
| _PSTL_HIDE_FROM_ABI_POP |
| |
| #endif /* _PSTL_PARALLEL_BACKEND_UTILS_H */ |