1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
|
// -*- C++ -*-
//===----------------------------------------------------------------------===//
//
// 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 <cassert>
#include "utils.h"
#include "pstl_config.h"
_PSTL_HIDE_FROM_ABI_PUSH
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;
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);
}
};
} // namespace __utils
} // namespace __pstl
_PSTL_HIDE_FROM_ABI_POP
#endif /* _PSTL_PARALLEL_BACKEND_UTILS_H */
|
