libcxx/include/__algorithm/copy.h

   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
  34 template <class _InputIterator, class _OutputIterator>
  35 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator
  36 copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result);
  37
  38 template <class _InIter, class _Sent, class _OutIter>
  39 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter> __copy(_InIter, _Sent, _OutIter);
  40
  41 template <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 = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
  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 = ~__storage_type(0) >> (__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
  86 template <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   = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
 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                  = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
 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 = ~__storage_type(0) >> (__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 = ~__storage_type(0) << __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                 = ~__storage_type(0) >> (__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                 = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
 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 = ~__storage_type(0) >> (__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
 157 struct __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
 238 template <class _InIter, class _Sent, class _OutIter>
 239 pair<_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
 244 template <class _InputIterator, class _OutputIterator>
 245 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator
 246 copy(_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