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
operator__serial_destroy27 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
__serial_move_merge__serial_move_merge46 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
operator__serial_move_merge52 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
__init_buf(_RandomAccessIterator1 __xs,_RandomAccessIterator1 __xe,_OutputIterator __zs,bool __bMove)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:
__stack(_DifferenceType __max_size)144 __stack(_DifferenceType __max_size) : _M_buf(__max_size), _M_maxsize(__max_size) { _M_ptr = _M_buf.get(); }
145
~__stack()146 ~__stack()
147 {
148 _PSTL_ASSERT(size() <= _M_maxsize);
149 while (!empty())
150 pop();
151 }
152
153 const _Buf&
buffer()154 buffer() const
155 {
156 return _M_buf;
157 }
158 size_t
size()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
empty()166 empty() const
167 {
168 _PSTL_ASSERT(_M_ptr >= _M_buf.get());
169 return _M_ptr == _M_buf.get();
170 }
171 void
push(const _ValueType & __v)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&
top()179 top() const
180 {
181 return *(_M_ptr - 1);
182 }
183 void
pop()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