256 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___ALGORITHM_COPY_H10#define _LIBCPP___ALGORITHM_COPY_H11 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_header27#endif28 29_LIBCPP_PUSH_MACROS30#include <__undef_macros>31 32_LIBCPP_BEGIN_NAMESPACE_STD33 34template <class _InputIterator, class _OutputIterator>35inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator36copy(_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 word52 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 words67 __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 word74 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 word97 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 else110 *__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 words125 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 word136 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 void180 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_v<_InIter>, 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_v<_InIter> && __is_segmented_iterator_v<_OutIter>,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 =201 typename common_type<__iterator_difference_type<_InIter>, __iterator_difference_type<_OutIter> >::type;202 203 if (__first == __last)204 return std::make_pair(std::move(__first), std::move(__result));205 206 auto __local_first = _Traits::__local(__result);207 auto __segment_iterator = _Traits::__segment(__result);208 while (true) {209 auto __local_last = _Traits::__end(__segment_iterator);210 auto __size = std::min<_DiffT>(__local_last - __local_first, __last - __first);211 auto __iters = std::__copy(__first, __first + __size, __local_first);212 __first = std::move(__iters.first);213 214 if (__first == __last)215 return std::make_pair(std::move(__first), _Traits::__compose(__segment_iterator, std::move(__iters.second)));216 217 __local_first = _Traits::__begin(++__segment_iterator);218 }219 }220 221 template <class _Cp, bool _IsConst>222 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<__bit_iterator<_Cp, _IsConst>, __bit_iterator<_Cp, false> >223 operator()(__bit_iterator<_Cp, _IsConst> __first,224 __bit_iterator<_Cp, _IsConst> __last,225 __bit_iterator<_Cp, false> __result) const {226 if (__first.__ctz_ == __result.__ctz_)227 return std::make_pair(__last, std::__copy_aligned(__first, __last, __result));228 return std::make_pair(__last, std::__copy_unaligned(__first, __last, __result));229 }230 231 // At this point, the iterators have been unwrapped so any `contiguous_iterator` has been unwrapped to a pointer.232 template <class _In, class _Out, __enable_if_t<__can_lower_copy_assignment_to_memmove<_In, _Out>::value, int> = 0>233 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*>234 operator()(_In* __first, _In* __last, _Out* __result) const {235 return std::__copy_trivial_impl(__first, __last, __result);236 }237};238 239template <class _InIter, class _Sent, class _OutIter>240pair<_InIter, _OutIter> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14241__copy(_InIter __first, _Sent __last, _OutIter __result) {242 return std::__copy_move_unwrap_iters<__copy_impl>(std::move(__first), std::move(__last), std::move(__result));243}244 245template <class _InputIterator, class _OutputIterator>246_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator247copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {248 return std::__copy(__first, __last, __result).second;249}250 251_LIBCPP_END_NAMESPACE_STD252 253_LIBCPP_POP_MACROS254 255#endif // _LIBCPP___ALGORITHM_COPY_H256