1 // -*- C++ -*- 2 //===-- parallel_backend_utils.h ------------------------------------------===// 3 // 4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5 // See https://llvm.org/LICENSE.txt for license information. 6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef __PSTL_parallel_backend_utils_H 11 #define __PSTL_parallel_backend_utils_H 12 13 #include <iterator> 14 #include <utility> 15 #include "utils.h" 16 17 namespace __pstl 18 { 19 namespace __par_backend 20 { 21 22 //! Destroy sequence [xs,xe) 23 struct __serial_destroy 24 { 25 template <typename _RandomAccessIterator> 26 void 27 operator()(_RandomAccessIterator __zs, _RandomAccessIterator __ze) 28 { 29 typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _ValueType; 30 while (__zs != __ze) 31 { 32 --__ze; 33 (*__ze).~_ValueType(); 34 } 35 } 36 }; 37 38 //! Merge sequences [__xs,__xe) and [__ys,__ye) to output sequence [__zs,(__xe-__xs)+(__ye-__ys)), using std::move 39 template <class _MoveValues, class _MoveSequences> 40 struct __serial_move_merge 41 { 42 const std::size_t _M_nmerge; 43 _MoveValues _M_move_values; 44 _MoveSequences _M_move_sequences; 45 46 explicit __serial_move_merge(std::size_t __nmerge, _MoveValues __move_values, _MoveSequences __move_sequences) 47 : _M_nmerge(__nmerge), _M_move_values(__move_values), _M_move_sequences(__move_sequences) 48 { 49 } 50 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _RandomAccessIterator3, class _Compare> 51 void 52 operator()(_RandomAccessIterator1 __xs, _RandomAccessIterator1 __xe, _RandomAccessIterator2 __ys, 53 _RandomAccessIterator2 __ye, _RandomAccessIterator3 __zs, _Compare __comp) 54 { 55 auto __n = _M_nmerge; 56 __PSTL_ASSERT(__n > 0); 57 if (__xs != __xe) 58 { 59 if (__ys != __ye) 60 { 61 for (;;) 62 { 63 if (__comp(*__ys, *__xs)) 64 { 65 _M_move_values(__ys, __zs); 66 ++__zs, --__n; 67 if (++__ys == __ye) 68 { 69 break; 70 } 71 else if (__n == 0) 72 { 73 __zs = _M_move_sequences(__ys, __ye, __zs); 74 break; 75 } 76 else 77 { 78 } 79 } 80 else 81 { 82 _M_move_values(__xs, __zs); 83 ++__zs, --__n; 84 if (++__xs == __xe) 85 { 86 _M_move_sequences(__ys, __ye, __zs); 87 return; 88 } 89 else if (__n == 0) 90 { 91 __zs = _M_move_sequences(__xs, __xe, __zs); 92 _M_move_sequences(__ys, __ye, __zs); 93 return; 94 } 95 else 96 { 97 } 98 } 99 } 100 } 101 __ys = __xs; 102 __ye = __xe; 103 } 104 _M_move_sequences(__ys, __ye, __zs); 105 } 106 }; 107 108 template <typename _RandomAccessIterator1, typename _OutputIterator> 109 void 110 __init_buf(_RandomAccessIterator1 __xs, _RandomAccessIterator1 __xe, _OutputIterator __zs, bool __bMove) 111 { 112 const _OutputIterator __ze = __zs + (__xe - __xs); 113 typedef typename std::iterator_traits<_OutputIterator>::value_type _ValueType; 114 if (__bMove) 115 { 116 // Initialize the temporary buffer and move keys to it. 117 for (; __zs != __ze; ++__xs, ++__zs) 118 new (&*__zs) _ValueType(std::move(*__xs)); 119 } 120 else 121 { 122 // Initialize the temporary buffer 123 for (; __zs != __ze; ++__zs) 124 new (&*__zs) _ValueType; 125 } 126 } 127 128 // TODO is this actually used anywhere? 129 template <typename _Buf> 130 class __stack 131 { 132 typedef typename std::iterator_traits<decltype(_Buf(0).get())>::value_type _ValueType; 133 typedef typename std::iterator_traits<_ValueType*>::difference_type _DifferenceType; 134 135 _Buf _M_buf; 136 _ValueType* _M_ptr; 137 _DifferenceType _M_maxsize; 138 139 __stack(const __stack&) = delete; 140 void 141 operator=(const __stack&) = delete; 142 143 public: 144 __stack(_DifferenceType __max_size) : _M_buf(__max_size), _M_maxsize(__max_size) { _M_ptr = _M_buf.get(); } 145 146 ~__stack() 147 { 148 __PSTL_ASSERT(size() <= _M_maxsize); 149 while (!empty()) 150 pop(); 151 } 152 153 const _Buf& 154 buffer() const 155 { 156 return _M_buf; 157 } 158 size_t 159 size() const 160 { 161 __PSTL_ASSERT(_M_ptr - _M_buf.get() <= _M_maxsize); 162 __PSTL_ASSERT(_M_ptr - _M_buf.get() >= 0); 163 return _M_ptr - _M_buf.get(); 164 } 165 bool 166 empty() const 167 { 168 __PSTL_ASSERT(_M_ptr >= _M_buf.get()); 169 return _M_ptr == _M_buf.get(); 170 } 171 void 172 push(const _ValueType& __v) 173 { 174 __PSTL_ASSERT(size() < _M_maxsize); 175 new (_M_ptr) _ValueType(__v); 176 ++_M_ptr; 177 } 178 const _ValueType& 179 top() const 180 { 181 return *(_M_ptr - 1); 182 } 183 void 184 pop() 185 { 186 __PSTL_ASSERT(_M_ptr > _M_buf.get()); 187 --_M_ptr; 188 (*_M_ptr).~_ValueType(); 189 } 190 }; 191 192 } // namespace __par_backend 193 } // namespace __pstl 194 195 #endif /* __PSTL_parallel_backend_utils_H */ 196