1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef _LIBCPP___ALGORITHM_COPY_H
10#define _LIBCPP___ALGORITHM_COPY_H
11
12#include <__algorithm/copy_move_common.h>
13#include <__algorithm/for_each_segment.h>
14#include <__algorithm/min.h>
15#include <__config>
16#include <__fwd/bit_reference.h>
17#include <__iterator/iterator_traits.h>
18#include <__iterator/segmented_iterator.h>
19#include <__memory/pointer_traits.h>
20#include <__type_traits/common_type.h>
21#include <__type_traits/enable_if.h>
22#include <__utility/move.h>
23#include <__utility/pair.h>
24
25#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
26# pragma GCC system_header
27#endif
28
29_LIBCPP_PUSH_MACROS
30#include <__undef_macros>
31
32_LIBCPP_BEGIN_NAMESPACE_STD
33
34template <class _InputIterator, class _OutputIterator>
35inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator
36copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result);
37
38template <class _InIter, class _Sent, class _OutIter>
39inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter> __copy(_InIter, _Sent, _OutIter);
40
41template <class _Cp, bool _IsConst>
42_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_aligned(
43 __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {
44 using _In = __bit_iterator<_Cp, _IsConst>;
45 using difference_type = typename _In::difference_type;
46 using __storage_type = typename _In::__storage_type;
47
48 const int __bits_per_word = _In::__bits_per_word;
49 difference_type __n = __last - __first;
50 if (__n > 0) {
51 // do first word
52 if (__first.__ctz_ != 0) {
53 unsigned __clz = __bits_per_word - __first.__ctz_;
54 difference_type __dn = std::min(static_cast<difference_type>(__clz), __n);
55 __n -= __dn;
56 __storage_type __m = std::__middle_mask<__storage_type>(__clz - __dn, __first.__ctz_);
57 __storage_type __b = *__first.__seg_ & __m;
58 *__result.__seg_ &= ~__m;
59 *__result.__seg_ |= __b;
60 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
61 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
62 ++__first.__seg_;
63 // __first.__ctz_ = 0;
64 }
65 // __first.__ctz_ == 0;
66 // do middle words
67 __storage_type __nw = __n / __bits_per_word;
68 std::copy(std::__to_address(__first.__seg_),
69 std::__to_address(__first.__seg_ + __nw),
70 std::__to_address(__result.__seg_));
71 __n -= __nw * __bits_per_word;
72 __result.__seg_ += __nw;
73 // do last word
74 if (__n > 0) {
75 __first.__seg_ += __nw;
76 __storage_type __m = std::__trailing_mask<__storage_type>(__bits_per_word - __n);
77 __storage_type __b = *__first.__seg_ & __m;
78 *__result.__seg_ &= ~__m;
79 *__result.__seg_ |= __b;
80 __result.__ctz_ = static_cast<unsigned>(__n);
81 }
82 }
83 return __result;
84}
85
86template <class _Cp, bool _IsConst>
87_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_unaligned(
88 __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {
89 using _In = __bit_iterator<_Cp, _IsConst>;
90 using difference_type = typename _In::difference_type;
91 using __storage_type = typename _In::__storage_type;
92
93 const int __bits_per_word = _In::__bits_per_word;
94 difference_type __n = __last - __first;
95 if (__n > 0) {
96 // do first word
97 if (__first.__ctz_ != 0) {
98 unsigned __clz_f = __bits_per_word - __first.__ctz_;
99 difference_type __dn = std::min(static_cast<difference_type>(__clz_f), __n);
100 __n -= __dn;
101 __storage_type __m = std::__middle_mask<__storage_type>(__clz_f - __dn, __first.__ctz_);
102 __storage_type __b = *__first.__seg_ & __m;
103 unsigned __clz_r = __bits_per_word - __result.__ctz_;
104 __storage_type __ddn = std::min<__storage_type>(__dn, __clz_r);
105 __m = std::__middle_mask<__storage_type>(__clz_r - __ddn, __result.__ctz_);
106 *__result.__seg_ &= ~__m;
107 if (__result.__ctz_ > __first.__ctz_)
108 *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_);
109 else
110 *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_);
111 __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;
112 __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word);
113 __dn -= __ddn;
114 if (__dn > 0) {
115 __m = std::__trailing_mask<__storage_type>(__bits_per_word - __dn);
116 *__result.__seg_ &= ~__m;
117 *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn);
118 __result.__ctz_ = static_cast<unsigned>(__dn);
119 }
120 ++__first.__seg_;
121 // __first.__ctz_ = 0;
122 }
123 // __first.__ctz_ == 0;
124 // do middle words
125 unsigned __clz_r = __bits_per_word - __result.__ctz_;
126 __storage_type __m = std::__leading_mask<__storage_type>(__result.__ctz_);
127 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) {
128 __storage_type __b = *__first.__seg_;
129 *__result.__seg_ &= ~__m;
130 *__result.__seg_ |= __b << __result.__ctz_;
131 ++__result.__seg_;
132 *__result.__seg_ &= __m;
133 *__result.__seg_ |= __b >> __clz_r;
134 }
135 // do last word
136 if (__n > 0) {
137 __m = std::__trailing_mask<__storage_type>(__bits_per_word - __n);
138 __storage_type __b = *__first.__seg_ & __m;
139 __storage_type __dn = std::min(__n, static_cast<difference_type>(__clz_r));
140 __m = std::__middle_mask<__storage_type>(__clz_r - __dn, __result.__ctz_);
141 *__result.__seg_ &= ~__m;
142 *__result.__seg_ |= __b << __result.__ctz_;
143 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
144 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
145 __n -= __dn;
146 if (__n > 0) {
147 __m = std::__trailing_mask<__storage_type>(__bits_per_word - __n);
148 *__result.__seg_ &= ~__m;
149 *__result.__seg_ |= __b >> __dn;
150 __result.__ctz_ = static_cast<unsigned>(__n);
151 }
152 }
153 }
154 return __result;
155}
156
157struct __copy_impl {
158 template <class _InIter, class _Sent, class _OutIter>
159 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
160 operator()(_InIter __first, _Sent __last, _OutIter __result) const {
161 while (__first != __last) {
162 *__result = *__first;
163 ++__first;
164 ++__result;
165 }
166
167 return std::make_pair(std::move(__first), std::move(__result));
168 }
169
170 template <class _InIter, class _OutIter>
171 struct _CopySegment {
172 using _Traits _LIBCPP_NODEBUG = __segmented_iterator_traits<_InIter>;
173
174 _OutIter& __result_;
175
176 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 explicit _CopySegment(_OutIter& __result)
177 : __result_(__result) {}
178
179 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void
180 operator()(typename _Traits::__local_iterator __lfirst, typename _Traits::__local_iterator __llast) {
181 __result_ = std::__copy(__lfirst, __llast, std::move(__result_)).second;
182 }
183 };
184
185 template <class _InIter, class _OutIter, __enable_if_t<__is_segmented_iterator<_InIter>::value, int> = 0>
186 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
187 operator()(_InIter __first, _InIter __last, _OutIter __result) const {
188 std::__for_each_segment(__first, __last, _CopySegment<_InIter, _OutIter>(__result));
189 return std::make_pair(__last, std::move(__result));
190 }
191
192 template <class _InIter,
193 class _OutIter,
194 __enable_if_t<__has_random_access_iterator_category<_InIter>::value &&
195 !__is_segmented_iterator<_InIter>::value && __is_segmented_iterator<_OutIter>::value,
196 int> = 0>
197 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
198 operator()(_InIter __first, _InIter __last, _OutIter __result) const {
199 using _Traits = __segmented_iterator_traits<_OutIter>;
200 using _DiffT = typename common_type<__iter_diff_t<_InIter>, __iter_diff_t<_OutIter> >::type;
201
202 if (__first == __last)
203 return std::make_pair(std::move(__first), std::move(__result));
204
205 auto __local_first = _Traits::__local(__result);
206 auto __segment_iterator = _Traits::__segment(__result);
207 while (true) {
208 auto __local_last = _Traits::__end(__segment_iterator);
209 auto __size = std::min<_DiffT>(__local_last - __local_first, __last - __first);
210 auto __iters = std::__copy(__first, __first + __size, __local_first);
211 __first = std::move(__iters.first);
212
213 if (__first == __last)
214 return std::make_pair(std::move(__first), _Traits::__compose(__segment_iterator, std::move(__iters.second)));
215
216 __local_first = _Traits::__begin(++__segment_iterator);
217 }
218 }
219
220 template <class _Cp, bool _IsConst>
221 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<__bit_iterator<_Cp, _IsConst>, __bit_iterator<_Cp, false> >
222 operator()(__bit_iterator<_Cp, _IsConst> __first,
223 __bit_iterator<_Cp, _IsConst> __last,
224 __bit_iterator<_Cp, false> __result) const {
225 if (__first.__ctz_ == __result.__ctz_)
226 return std::make_pair(__last, std::__copy_aligned(__first, __last, __result));
227 return std::make_pair(__last, std::__copy_unaligned(__first, __last, __result));
228 }
229
230 // At this point, the iterators have been unwrapped so any `contiguous_iterator` has been unwrapped to a pointer.
231 template <class _In, class _Out, __enable_if_t<__can_lower_copy_assignment_to_memmove<_In, _Out>::value, int> = 0>
232 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*>
233 operator()(_In* __first, _In* __last, _Out* __result) const {
234 return std::__copy_trivial_impl(__first, __last, __result);
235 }
236};
237
238template <class _InIter, class _Sent, class _OutIter>
239pair<_InIter, _OutIter> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
240__copy(_InIter __first, _Sent __last, _OutIter __result) {
241 return std::__copy_move_unwrap_iters<__copy_impl>(std::move(__first), std::move(__last), std::move(__result));
242}
243
244template <class _InputIterator, class _OutputIterator>
245_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator
246copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {
247 return std::__copy(__first, __last, __result).second;
248}
249
250_LIBCPP_END_NAMESPACE_STD
251
252_LIBCPP_POP_MACROS
253
254#endif // _LIBCPP___ALGORITHM_COPY_H
255