11.2.0/pstl/parallel_backend_utils.h

// -*- C++ -*-
//===-- parallel_backend_utils.h ------------------------------------------===//
//
// 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 "utils.h"

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;
        _PSTL_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);
    }
};

template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare,
          typename _CopyConstructRange>
_OutputIterator
__set_union_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
                      _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp,
                      _CopyConstructRange __cc_range)
{
    using _Tp = typename std::iterator_traits<_OutputIterator>::value_type;

    for (; __first1 != __last1; ++__result)
    {
        if (__first2 == __last2)
            return __cc_range(__first1, __last1, __result);
        if (__comp(*__first2, *__first1))
        {
            ::new (std::addressof(*__result)) _Tp(*__first2);
            ++__first2;
        }
        else
        {
            ::new (std::addressof(*__result)) _Tp(*__first1);
            if (!__comp(*__first1, *__first2))
                ++__first2;
            ++__first1;
        }
    }
    return __cc_range(__first2, __last2, __result);
}

template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare>
_OutputIterator
__set_intersection_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
                             _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp)
{
    using _Tp = typename std::iterator_traits<_OutputIterator>::value_type;

    for (; __first1 != __last1 && __first2 != __last2;)
    {
        if (__comp(*__first1, *__first2))
            ++__first1;
        else
        {
            if (!__comp(*__first2, *__first1))
            {
                ::new (std::addressof(*__result)) _Tp(*__first1);
                ++__result;
                ++__first1;
            }
            ++__first2;
        }
    }
    return __result;
}

template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare,
          typename _CopyConstructRange>
_OutputIterator
__set_difference_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
                           _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp,
                           _CopyConstructRange __cc_range)
{
    using _Tp = typename std::iterator_traits<_OutputIterator>::value_type;

    for (; __first1 != __last1;)
    {
        if (__first2 == __last2)
            return __cc_range(__first1, __last1, __result);

        if (__comp(*__first1, *__first2))
        {
            ::new (std::addressof(*__result)) _Tp(*__first1);
            ++__result;
            ++__first1;
        }
        else
        {
            if (!__comp(*__first2, *__first1))
                ++__first1;
            ++__first2;
        }
    }
    return __result;
}
template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare,
          typename _CopyConstructRange>
_OutputIterator
__set_symmetric_difference_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
                                     _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp,
                                     _CopyConstructRange __cc_range)
{
    using _Tp = typename std::iterator_traits<_OutputIterator>::value_type;

    for (; __first1 != __last1;)
    {
        if (__first2 == __last2)
            return __cc_range(__first1, __last1, __result);

        if (__comp(*__first1, *__first2))
        {
            ::new (std::addressof(*__result)) _Tp(*__first1);
            ++__result;
            ++__first1;
        }
        else
        {
            if (__comp(*__first2, *__first1))
            {
                ::new (std::addressof(*__result)) _Tp(*__first2);
                ++__result;
            }
            else
                ++__first1;
            ++__first2;
        }
    }
    return __cc_range(__first2, __last2, __result);
}

} // namespace __utils
} // namespace __pstl

#endif /* _PSTL_PARALLEL_BACKEND_UTILS_H */
Revision:	1166
Committed:	Tue Oct 26 14:22:36 2021 UTC (4 years ago) by rossy
Content type:	text/x-chdr
File size:	9111 byte(s)
Log Message:	Daodan: Replace MinGW build env with an up-to-date MSYS2 env
#	Content
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
20	namespace __utils
21	{
22
23	//! Destroy sequence [xs,xe)
24	struct __serial_destroy
25	{
26	template <typename _RandomAccessIterator>
27	void
28	operator()(_RandomAccessIterator __zs, _RandomAccessIterator __ze)
29	{
30	typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _ValueType;
31	while (__zs != __ze)
32	{
33	--__ze;
34	(*__ze).~_ValueType();
35	}
36	}
37	};
38
39	//! Merge sequences [__xs,__xe) and [__ys,__ye) to output sequence [__zs,(__xe-__xs)+(__ye-__ys)), using std::move
40	struct __serial_move_merge
41	{
42	const std::size_t _M_nmerge;
43
44	explicit __serial_move_merge(std::size_t __nmerge) : _M_nmerge(__nmerge) {}
45	template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _RandomAccessIterator3, class _Compare,
46	class _MoveValueX, class _MoveValueY, class _MoveSequenceX, class _MoveSequenceY>
47	void
48	operator()(_RandomAccessIterator1 __xs, _RandomAccessIterator1 __xe, _RandomAccessIterator2 __ys,
49	_RandomAccessIterator2 __ye, _RandomAccessIterator3 __zs, _Compare __comp, _MoveValueX __move_value_x,
50	_MoveValueY __move_value_y, _MoveSequenceX __move_sequence_x, _MoveSequenceY __move_sequence_y)
51	{
52	constexpr bool __same_move_val = std::is_same<_MoveValueX, _MoveValueY>::value;
53	constexpr bool __same_move_seq = std::is_same<_MoveSequenceX, _MoveSequenceY>::value;
54
55	auto __n = _M_nmerge;
56	_PSTL_ASSERT(__n > 0);
57
58	auto __nx = __xe - __xs;
59	//auto __ny = __ye - __ys;
60	_RandomAccessIterator3 __zs_beg = __zs;
61
62	if (__xs != __xe)
63	{
64	if (__ys != __ye)
65	{
66	for (;;)
67	{
68	if (__comp(__ys, __xs))
69	{
70	const auto __i = __zs - __zs_beg;
71	if (__i < __nx)
72	__move_value_x(__ys, __zs);
73	else
74	__move_value_y(__ys, __zs);
75	++__zs, --__n;
76	if (++__ys == __ye)
77	{
78	break;
79	}
80	else if (__n == 0)
81	{
82	const auto __j = __zs - __zs_beg;
83	if (__same_move_seq \|\| __j < __nx)
84	__zs = __move_sequence_x(__ys, __ye, __zs);
85	else
86	__zs = __move_sequence_y(__ys, __ye, __zs);
87	break;
88	}
89	}
90	else
91	{
92	const auto __i = __zs - __zs_beg;
93	if (__same_move_val \|\| __i < __nx)
94	__move_value_x(__xs, __zs);
95	else
96	__move_value_y(__xs, __zs);
97	++__zs, --__n;
98	if (++__xs == __xe)
99	{
100	const auto __j = __zs - __zs_beg;
101	if (__same_move_seq \|\| __j < __nx)
102	__move_sequence_x(__ys, __ye, __zs);
103	else
104	__move_sequence_y(__ys, __ye, __zs);
105	return;
106	}
107	else if (__n == 0)
108	{
109	const auto __j = __zs - __zs_beg;
110	if (__same_move_seq \|\| __j < __nx)
111	{
112	__zs = __move_sequence_x(__xs, __xe, __zs);
113	__move_sequence_x(__ys, __ye, __zs);
114	}
115	else
116	{
117	__zs = __move_sequence_y(__xs, __xe, __zs);
118	__move_sequence_y(__ys, __ye, __zs);
119	}
120	return;
121	}
122	}
123	}
124	}
125	__ys = __xs;
126	__ye = __xe;
127	}
128	const auto __i = __zs - __zs_beg;
129	if (__same_move_seq \|\| __i < __nx)
130	__move_sequence_x(__ys, __ye, __zs);
131	else
132	__move_sequence_y(__ys, __ye, __zs);
133	}
134	};
135
136	template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare,
137	typename _CopyConstructRange>
138	_OutputIterator
139	__set_union_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
140	_ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp,
141	_CopyConstructRange __cc_range)
142	{
143	using _Tp = typename std::iterator_traits<_OutputIterator>::value_type;
144
145	for (; __first1 != __last1; ++__result)
146	{
147	if (__first2 == __last2)
148	return __cc_range(__first1, __last1, __result);
149	if (__comp(__first2, __first1))
150	{
151	::new (std::addressof(__result)) _Tp(__first2);
152	++__first2;
153	}
154	else
155	{
156	::new (std::addressof(__result)) _Tp(__first1);
157	if (!__comp(__first1, __first2))
158	++__first2;
159	++__first1;
160	}
161	}
162	return __cc_range(__first2, __last2, __result);
163	}
164
165	template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare>
166	_OutputIterator
167	__set_intersection_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
168	_ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp)
169	{
170	using _Tp = typename std::iterator_traits<_OutputIterator>::value_type;
171
172	for (; __first1 != __last1 && __first2 != __last2;)
173	{
174	if (__comp(__first1, __first2))
175	++__first1;
176	else
177	{
178	if (!__comp(__first2, __first1))
179	{
180	::new (std::addressof(__result)) _Tp(__first1);
181	++__result;
182	++__first1;
183	}
184	++__first2;
185	}
186	}
187	return __result;
188	}
189
190	template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare,
191	typename _CopyConstructRange>
192	_OutputIterator
193	__set_difference_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
194	_ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp,
195	_CopyConstructRange __cc_range)
196	{
197	using _Tp = typename std::iterator_traits<_OutputIterator>::value_type;
198
199	for (; __first1 != __last1;)
200	{
201	if (__first2 == __last2)
202	return __cc_range(__first1, __last1, __result);
203
204	if (__comp(__first1, __first2))
205	{
206	::new (std::addressof(__result)) _Tp(__first1);
207	++__result;
208	++__first1;
209	}
210	else
211	{
212	if (!__comp(__first2, __first1))
213	++__first1;
214	++__first2;
215	}
216	}
217	return __result;
218	}
219	template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare,
220	typename _CopyConstructRange>
221	_OutputIterator
222	__set_symmetric_difference_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
223	_ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp,
224	_CopyConstructRange __cc_range)
225	{
226	using _Tp = typename std::iterator_traits<_OutputIterator>::value_type;
227
228	for (; __first1 != __last1;)
229	{
230	if (__first2 == __last2)
231	return __cc_range(__first1, __last1, __result);
232
233	if (__comp(__first1, __first2))
234	{
235	::new (std::addressof(__result)) _Tp(__first1);
236	++__result;
237	++__first1;
238	}
239	else
240	{
241	if (__comp(__first2, __first1))
242	{
243	::new (std::addressof(__result)) _Tp(__first2);
244	++__result;
245	}
246	else
247	++__first1;
248	++__first2;
249	}
250	}
251	return __cc_range(__first2, __last2, __result);
252	}
253
254	} // namespace __utils
255	} // namespace __pstl
256
257	#endif /* _PSTL_PARALLEL_BACKEND_UTILS_H */