| // -*- C++ -*- |
| //===-- parallel_backend_utils.h ------------------------------------------===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file is dual licensed under the MIT and the University of Illinois Open |
| // Source Licenses. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef __PSTL_parallel_backend_utils_H |
| #define __PSTL_parallel_backend_utils_H |
| |
| #include <iterator> |
| #include <utility> |
| #include "utils.h" |
| |
| namespace __pstl |
| { |
| namespace par_backend |
| { |
| |
| //! 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 |
| template <class _MoveValues, class _MoveSequences> |
| struct serial_move_merge |
| { |
| const std::size_t _M_nmerge; |
| _MoveValues _M_move_values; |
| _MoveSequences _M_move_sequences; |
| |
| explicit serial_move_merge(std::size_t __nmerge, _MoveValues __move_values, _MoveSequences __move_sequences) |
| : _M_nmerge(__nmerge), _M_move_values(__move_values), _M_move_sequences(__move_sequences) |
| { |
| } |
| template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _RandomAccessIterator3, class _Compare> |
| void |
| operator()(_RandomAccessIterator1 __xs, _RandomAccessIterator1 __xe, _RandomAccessIterator2 __ys, |
| _RandomAccessIterator2 __ye, _RandomAccessIterator3 __zs, _Compare __comp) |
| { |
| auto __n = _M_nmerge; |
| assert(__n > 0); |
| if (__xs != __xe) |
| { |
| if (__ys != __ye) |
| { |
| for (;;) |
| { |
| if (__comp(*__ys, *__xs)) |
| { |
| _M_move_values(__ys, __zs); |
| ++__zs, --__n; |
| if (++__ys == __ye) |
| { |
| break; |
| } |
| else if (__n == 0) |
| { |
| __zs = _M_move_sequences(__ys, __ye, __zs); |
| break; |
| } |
| else |
| { |
| } |
| } |
| else |
| { |
| _M_move_values(__xs, __zs); |
| ++__zs, --__n; |
| if (++__xs == __xe) |
| { |
| _M_move_sequences(__ys, __ye, __zs); |
| return; |
| } |
| else if (__n == 0) |
| { |
| __zs = _M_move_sequences(__xs, __xe, __zs); |
| _M_move_sequences(__ys, __ye, __zs); |
| return; |
| } |
| else |
| { |
| } |
| } |
| } |
| } |
| __ys = __xs; |
| __ye = __xe; |
| } |
| _M_move_sequences(__ys, __ye, __zs); |
| } |
| }; |
| |
| template <typename _RandomAccessIterator1, typename _OutputIterator> |
| void |
| init_buf(_RandomAccessIterator1 __xs, _RandomAccessIterator1 __xe, _OutputIterator __zs, bool __bMove) |
| { |
| const _OutputIterator __ze = __zs + (__xe - __xs); |
| typedef typename std::iterator_traits<_OutputIterator>::value_type _ValueType; |
| if (__bMove) |
| { |
| // Initialize the temporary buffer and move keys to it. |
| for (; __zs != __ze; ++__xs, ++__zs) |
| new (&*__zs) _ValueType(std::move(*__xs)); |
| } |
| else |
| { |
| // Initialize the temporary buffer |
| for (; __zs != __ze; ++__zs) |
| new (&*__zs) _ValueType; |
| } |
| } |
| |
| template <typename _Buf> |
| class stack |
| { |
| typedef typename std::iterator_traits<decltype(_Buf(0).get())>::value_type _ValueType; |
| typedef typename std::iterator_traits<_ValueType*>::difference_type _DifferenceType; |
| |
| _Buf _M_buf; |
| _ValueType* _M_ptr; |
| _DifferenceType _M_maxsize; |
| |
| stack(const stack&) = delete; |
| void |
| operator=(const stack&) = delete; |
| |
| public: |
| stack(_DifferenceType __max_size) : _M_buf(__max_size), _M_maxsize(__max_size) { _M_ptr = _M_buf.get(); } |
| |
| ~stack() |
| { |
| assert(size() <= _M_maxsize); |
| while (!empty()) |
| pop(); |
| } |
| |
| const _Buf& |
| buffer() const |
| { |
| return _M_buf; |
| } |
| size_t |
| size() const |
| { |
| assert(_M_ptr - _M_buf.get() <= _M_maxsize); |
| assert(_M_ptr - _M_buf.get() >= 0); |
| return _M_ptr - _M_buf.get(); |
| } |
| bool |
| empty() const |
| { |
| assert(_M_ptr >= _M_buf.get()); |
| return _M_ptr == _M_buf.get(); |
| } |
| void |
| push(const _ValueType& __v) |
| { |
| assert(size() < _M_maxsize); |
| new (_M_ptr) _ValueType(__v); |
| ++_M_ptr; |
| } |
| const _ValueType& |
| top() const |
| { |
| return *(_M_ptr - 1); |
| } |
| void |
| pop() |
| { |
| assert(_M_ptr > _M_buf.get()); |
| --_M_ptr; |
| (*_M_ptr).~_ValueType(); |
| } |
| }; |
| |
| } // namespace par_backend |
| } // namespace __pstl |
| |
| #endif /* __PSTL_parallel_backend_utils_H */ |