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_BACKWARD_H 10 #define _LIBCPP___ALGORITHM_COPY_BACKWARD_H 11 12 #include <__algorithm/copy_move_common.h> 13 #include <__algorithm/copy_n.h> 14 #include <__algorithm/iterator_operations.h> 15 #include <__algorithm/min.h> 16 #include <__config> 17 #include <__fwd/bit_reference.h> 18 #include <__iterator/iterator_traits.h> 19 #include <__iterator/segmented_iterator.h> 20 #include <__memory/pointer_traits.h> 21 #include <__type_traits/common_type.h> 22 #include <__type_traits/enable_if.h> 23 #include <__type_traits/is_constructible.h> 24 #include <__utility/move.h> 25 #include <__utility/pair.h> 26 27 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 28 # pragma GCC system_header 29 #endif 30 31 _LIBCPP_PUSH_MACROS 32 #include <__undef_macros> 33 34 _LIBCPP_BEGIN_NAMESPACE_STD 35 36 template <class _AlgPolicy, class _InIter, class _Sent, class _OutIter> 37 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_InIter, _OutIter> 38 __copy_backward(_InIter __first, _Sent __last, _OutIter __result); 39 40 template <class _Cp, bool _IsConst> 41 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_backward_aligned( 42 __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) { 43 using _In = __bit_iterator<_Cp, _IsConst>; 44 using difference_type = typename _In::difference_type; 45 using __storage_type = typename _In::__storage_type; 46 47 const int __bits_per_word = _In::__bits_per_word; 48 difference_type __n = __last - __first; 49 if (__n > 0) { 50 // do first word 51 if (__last.__ctz_ != 0) { 52 difference_type __dn = std::min(static_cast<difference_type>(__last.__ctz_), __n); 53 __n -= __dn; 54 unsigned __clz = __bits_per_word - __last.__ctz_; 55 __storage_type __m = std::__middle_mask<__storage_type>(__clz, __last.__ctz_ - __dn); 56 __storage_type __b = *__last.__seg_ & __m; 57 *__result.__seg_ &= ~__m; 58 *__result.__seg_ |= __b; 59 __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + __result.__ctz_) % __bits_per_word); 60 // __last.__ctz_ = 0 61 } 62 // __last.__ctz_ == 0 || __n == 0 63 // __result.__ctz_ == 0 || __n == 0 64 // do middle words 65 __storage_type __nw = __n / __bits_per_word; 66 __result.__seg_ -= __nw; 67 __last.__seg_ -= __nw; 68 std::copy_n(std::__to_address(__last.__seg_), __nw, std::__to_address(__result.__seg_)); 69 __n -= __nw * __bits_per_word; 70 // do last word 71 if (__n > 0) { 72 __storage_type __m = std::__leading_mask<__storage_type>(__bits_per_word - __n); 73 __storage_type __b = *--__last.__seg_ & __m; 74 *--__result.__seg_ &= ~__m; 75 *__result.__seg_ |= __b; 76 __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 77 } 78 } 79 return __result; 80 } 81 82 template <class _Cp, bool _IsConst> 83 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_backward_unaligned( 84 __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) { 85 using _In = __bit_iterator<_Cp, _IsConst>; 86 using difference_type = typename _In::difference_type; 87 using __storage_type = typename _In::__storage_type; 88 89 const int __bits_per_word = _In::__bits_per_word; 90 difference_type __n = __last - __first; 91 if (__n > 0) { 92 // do first word 93 if (__last.__ctz_ != 0) { 94 difference_type __dn = std::min(static_cast<difference_type>(__last.__ctz_), __n); 95 __n -= __dn; 96 unsigned __clz_l = __bits_per_word - __last.__ctz_; 97 __storage_type __m = std::__middle_mask<__storage_type>(__clz_l, __last.__ctz_ - __dn); 98 __storage_type __b = *__last.__seg_ & __m; 99 unsigned __clz_r = __bits_per_word - __result.__ctz_; 100 __storage_type __ddn = std::min(__dn, static_cast<difference_type>(__result.__ctz_)); 101 if (__ddn > 0) { 102 __m = std::__middle_mask<__storage_type>(__clz_r, __result.__ctz_ - __ddn); 103 *__result.__seg_ &= ~__m; 104 if (__result.__ctz_ > __last.__ctz_) 105 *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 106 else 107 *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_); 108 __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) + __result.__ctz_) % __bits_per_word); 109 __dn -= __ddn; 110 } 111 if (__dn > 0) { 112 // __result.__ctz_ == 0 113 --__result.__seg_; 114 __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1)); 115 __m = std::__leading_mask<__storage_type>(__result.__ctz_); 116 *__result.__seg_ &= ~__m; 117 __last.__ctz_ -= __dn + __ddn; 118 *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 119 } 120 // __last.__ctz_ = 0 121 } 122 // __last.__ctz_ == 0 || __n == 0 123 // __result.__ctz_ != 0 || __n == 0 124 // do middle words 125 unsigned __clz_r = __bits_per_word - __result.__ctz_; 126 __storage_type __m = std::__trailing_mask<__storage_type>(__clz_r); 127 for (; __n >= __bits_per_word; __n -= __bits_per_word) { 128 __storage_type __b = *--__last.__seg_; 129 *__result.__seg_ &= ~__m; 130 *__result.__seg_ |= __b >> __clz_r; 131 *--__result.__seg_ &= __m; 132 *__result.__seg_ |= __b << __result.__ctz_; 133 } 134 // do last word 135 if (__n > 0) { 136 __m = std::__leading_mask<__storage_type>(__bits_per_word - __n); 137 __storage_type __b = *--__last.__seg_ & __m; 138 __clz_r = __bits_per_word - __result.__ctz_; 139 __storage_type __dn = std::min(__n, static_cast<difference_type>(__result.__ctz_)); 140 __m = std::__middle_mask<__storage_type>(__clz_r, __result.__ctz_ - __dn); 141 *__result.__seg_ &= ~__m; 142 *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_); 143 __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + __result.__ctz_) % __bits_per_word); 144 __n -= __dn; 145 if (__n > 0) { 146 // __result.__ctz_ == 0 147 --__result.__seg_; 148 __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 149 __m = std::__leading_mask<__storage_type>(__result.__ctz_); 150 *__result.__seg_ &= ~__m; 151 *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn)); 152 } 153 } 154 } 155 return __result; 156 } 157 158 template <class _AlgPolicy> 159 struct __copy_backward_impl { 160 template <class _InIter, class _Sent, class _OutIter> 161 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter> 162 operator()(_InIter __first, _Sent __last, _OutIter __result) const { 163 auto __last_iter = _IterOps<_AlgPolicy>::next(__first, __last); 164 auto __original_last_iter = __last_iter; 165 166 while (__first != __last_iter) { 167 *--__result = *--__last_iter; 168 } 169 170 return std::make_pair(std::move(__original_last_iter), std::move(__result)); 171 } 172 173 template <class _InIter, class _OutIter, __enable_if_t<__is_segmented_iterator<_InIter>::value, int> = 0> 174 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter> 175 operator()(_InIter __first, _InIter __last, _OutIter __result) const { 176 using _Traits = __segmented_iterator_traits<_InIter>; 177 auto __sfirst = _Traits::__segment(__first); 178 auto __slast = _Traits::__segment(__last); 179 if (__sfirst == __slast) { 180 auto __iters = 181 std::__copy_backward<_AlgPolicy>(_Traits::__local(__first), _Traits::__local(__last), std::move(__result)); 182 return std::make_pair(__last, __iters.second); 183 } 184 185 __result = 186 std::__copy_backward<_AlgPolicy>(_Traits::__begin(__slast), _Traits::__local(__last), std::move(__result)) 187 .second; 188 --__slast; 189 while (__sfirst != __slast) { 190 __result = 191 std::__copy_backward<_AlgPolicy>(_Traits::__begin(__slast), _Traits::__end(__slast), std::move(__result)) 192 .second; 193 --__slast; 194 } 195 __result = std::__copy_backward<_AlgPolicy>(_Traits::__local(__first), _Traits::__end(__slast), std::move(__result)) 196 .second; 197 return std::make_pair(__last, std::move(__result)); 198 } 199 200 template <class _InIter, 201 class _OutIter, 202 __enable_if_t<__has_random_access_iterator_category<_InIter>::value && 203 !__is_segmented_iterator<_InIter>::value && __is_segmented_iterator<_OutIter>::value, 204 int> = 0> 205 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter> 206 operator()(_InIter __first, _InIter __last, _OutIter __result) const { 207 using _Traits = __segmented_iterator_traits<_OutIter>; 208 auto __orig_last = __last; 209 auto __segment_iterator = _Traits::__segment(__result); 210 211 // When the range contains no elements, __result might not be a valid iterator 212 if (__first == __last) 213 return std::make_pair(__first, __result); 214 215 auto __local_last = _Traits::__local(__result); 216 while (true) { 217 using _DiffT = typename common_type<__iter_diff_t<_InIter>, __iter_diff_t<_OutIter> >::type; 218 219 auto __local_first = _Traits::__begin(__segment_iterator); 220 auto __size = std::min<_DiffT>(__local_last - __local_first, __last - __first); 221 auto __iter = std::__copy_backward<_AlgPolicy>(__last - __size, __last, __local_last).second; 222 __last -= __size; 223 224 if (__first == __last) 225 return std::make_pair(std::move(__orig_last), _Traits::__compose(__segment_iterator, std::move(__iter))); 226 --__segment_iterator; 227 __local_last = _Traits::__end(__segment_iterator); 228 } 229 } 230 231 template <class _Cp, bool _IsConst> 232 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<__bit_iterator<_Cp, _IsConst>, __bit_iterator<_Cp, false> > 233 operator()(__bit_iterator<_Cp, _IsConst> __first, 234 __bit_iterator<_Cp, _IsConst> __last, 235 __bit_iterator<_Cp, false> __result) { 236 if (__last.__ctz_ == __result.__ctz_) 237 return std::make_pair(__last, std::__copy_backward_aligned(__first, __last, __result)); 238 return std::make_pair(__last, std::__copy_backward_unaligned(__first, __last, __result)); 239 } 240 241 // At this point, the iterators have been unwrapped so any `contiguous_iterator` has been unwrapped to a pointer. 242 template <class _In, class _Out, __enable_if_t<__can_lower_copy_assignment_to_memmove<_In, _Out>::value, int> = 0> 243 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*> 244 operator()(_In* __first, _In* __last, _Out* __result) const { 245 return std::__copy_backward_trivial_impl(__first, __last, __result); 246 } 247 }; 248 249 template <class _AlgPolicy, class _BidirectionalIterator1, class _Sentinel, class _BidirectionalIterator2> 250 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_BidirectionalIterator1, _BidirectionalIterator2> 251 __copy_backward(_BidirectionalIterator1 __first, _Sentinel __last, _BidirectionalIterator2 __result) { 252 return std::__copy_move_unwrap_iters<__copy_backward_impl<_AlgPolicy> >( 253 std::move(__first), std::move(__last), std::move(__result)); 254 } 255 256 template <class _BidirectionalIterator1, class _BidirectionalIterator2> 257 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _BidirectionalIterator2 258 copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, _BidirectionalIterator2 __result) { 259 static_assert(std::is_copy_constructible<_BidirectionalIterator1>::value && 260 std::is_copy_constructible<_BidirectionalIterator1>::value, 261 "Iterators must be copy constructible."); 262 263 return std::__copy_backward<_ClassicAlgPolicy>(std::move(__first), std::move(__last), std::move(__result)).second; 264 } 265 266 _LIBCPP_END_NAMESPACE_STD 267 268 _LIBCPP_POP_MACROS 269 270 #endif // _LIBCPP___ALGORITHM_COPY_BACKWARD_H 271