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
17namespace __pstl
18{
19namespace __par_backend
20{
21
22//! Destroy sequence [xs,xe)
23struct __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
39template <class _MoveValues, class _MoveSequences>
40struct __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
108template <typename _RandomAccessIterator1, typename _OutputIterator>
109void
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?
129template <typename _Buf>
130class __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