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_SWAP_RANGES_H 10 #define _LIBCPP___ALGORITHM_SWAP_RANGES_H 11 12 #include <__algorithm/iterator_operations.h> 13 #include <__algorithm/min.h> 14 #include <__config> 15 #include <__fwd/bit_reference.h> 16 #include <__utility/move.h> 17 #include <__utility/pair.h> 18 #include <__utility/swap.h> 19 20 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 21 # pragma GCC system_header 22 #endif 23 24 _LIBCPP_PUSH_MACROS 25 #include <__undef_macros> 26 27 _LIBCPP_BEGIN_NAMESPACE_STD 28 29 template <class _Cl, class _Cr> 30 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cr, false> __swap_ranges_aligned( 31 __bit_iterator<_Cl, false> __first, __bit_iterator<_Cl, false> __last, __bit_iterator<_Cr, false> __result) { 32 using _I1 = __bit_iterator<_Cl, false>; 33 using difference_type = typename _I1::difference_type; 34 using __storage_type = typename _I1::__storage_type; 35 36 const int __bits_per_word = _I1::__bits_per_word; 37 difference_type __n = __last - __first; 38 if (__n > 0) { 39 // do first word 40 if (__first.__ctz_ != 0) { 41 unsigned __clz = __bits_per_word - __first.__ctz_; 42 difference_type __dn = std::min(static_cast<difference_type>(__clz), __n); 43 __n -= __dn; 44 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 45 __storage_type __b1 = *__first.__seg_ & __m; 46 *__first.__seg_ &= ~__m; 47 __storage_type __b2 = *__result.__seg_ & __m; 48 *__result.__seg_ &= ~__m; 49 *__result.__seg_ |= __b1; 50 *__first.__seg_ |= __b2; 51 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 52 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 53 ++__first.__seg_; 54 // __first.__ctz_ = 0; 55 } 56 // __first.__ctz_ == 0; 57 // do middle words 58 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_) 59 swap(*__first.__seg_, *__result.__seg_); 60 // do last word 61 if (__n > 0) { 62 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 63 __storage_type __b1 = *__first.__seg_ & __m; 64 *__first.__seg_ &= ~__m; 65 __storage_type __b2 = *__result.__seg_ & __m; 66 *__result.__seg_ &= ~__m; 67 *__result.__seg_ |= __b1; 68 *__first.__seg_ |= __b2; 69 __result.__ctz_ = static_cast<unsigned>(__n); 70 } 71 } 72 return __result; 73 } 74 75 template <class _Cl, class _Cr> 76 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cr, false> __swap_ranges_unaligned( 77 __bit_iterator<_Cl, false> __first, __bit_iterator<_Cl, false> __last, __bit_iterator<_Cr, false> __result) { 78 using _I1 = __bit_iterator<_Cl, false>; 79 using difference_type = typename _I1::difference_type; 80 using __storage_type = typename _I1::__storage_type; 81 82 const int __bits_per_word = _I1::__bits_per_word; 83 difference_type __n = __last - __first; 84 if (__n > 0) { 85 // do first word 86 if (__first.__ctz_ != 0) { 87 unsigned __clz_f = __bits_per_word - __first.__ctz_; 88 difference_type __dn = std::min(static_cast<difference_type>(__clz_f), __n); 89 __n -= __dn; 90 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 91 __storage_type __b1 = *__first.__seg_ & __m; 92 *__first.__seg_ &= ~__m; 93 unsigned __clz_r = __bits_per_word - __result.__ctz_; 94 __storage_type __ddn = std::min<__storage_type>(__dn, __clz_r); 95 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 96 __storage_type __b2 = *__result.__seg_ & __m; 97 *__result.__seg_ &= ~__m; 98 if (__result.__ctz_ > __first.__ctz_) { 99 unsigned __s = __result.__ctz_ - __first.__ctz_; 100 *__result.__seg_ |= __b1 << __s; 101 *__first.__seg_ |= __b2 >> __s; 102 } else { 103 unsigned __s = __first.__ctz_ - __result.__ctz_; 104 *__result.__seg_ |= __b1 >> __s; 105 *__first.__seg_ |= __b2 << __s; 106 } 107 __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 108 __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 109 __dn -= __ddn; 110 if (__dn > 0) { 111 __m = ~__storage_type(0) >> (__bits_per_word - __dn); 112 __b2 = *__result.__seg_ & __m; 113 *__result.__seg_ &= ~__m; 114 unsigned __s = __first.__ctz_ + __ddn; 115 *__result.__seg_ |= __b1 >> __s; 116 *__first.__seg_ |= __b2 << __s; 117 __result.__ctz_ = static_cast<unsigned>(__dn); 118 } 119 ++__first.__seg_; 120 // __first.__ctz_ = 0; 121 } 122 // __first.__ctz_ == 0; 123 // do middle words 124 __storage_type __m = ~__storage_type(0) << __result.__ctz_; 125 unsigned __clz_r = __bits_per_word - __result.__ctz_; 126 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) { 127 __storage_type __b1 = *__first.__seg_; 128 __storage_type __b2 = *__result.__seg_ & __m; 129 *__result.__seg_ &= ~__m; 130 *__result.__seg_ |= __b1 << __result.__ctz_; 131 *__first.__seg_ = __b2 >> __result.__ctz_; 132 ++__result.__seg_; 133 __b2 = *__result.__seg_ & ~__m; 134 *__result.__seg_ &= __m; 135 *__result.__seg_ |= __b1 >> __clz_r; 136 *__first.__seg_ |= __b2 << __clz_r; 137 } 138 // do last word 139 if (__n > 0) { 140 __m = ~__storage_type(0) >> (__bits_per_word - __n); 141 __storage_type __b1 = *__first.__seg_ & __m; 142 *__first.__seg_ &= ~__m; 143 __storage_type __dn = std::min<__storage_type>(__n, __clz_r); 144 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 145 __storage_type __b2 = *__result.__seg_ & __m; 146 *__result.__seg_ &= ~__m; 147 *__result.__seg_ |= __b1 << __result.__ctz_; 148 *__first.__seg_ |= __b2 >> __result.__ctz_; 149 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 150 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 151 __n -= __dn; 152 if (__n > 0) { 153 __m = ~__storage_type(0) >> (__bits_per_word - __n); 154 __b2 = *__result.__seg_ & __m; 155 *__result.__seg_ &= ~__m; 156 *__result.__seg_ |= __b1 >> __dn; 157 *__first.__seg_ |= __b2 << __dn; 158 __result.__ctz_ = static_cast<unsigned>(__n); 159 } 160 } 161 } 162 return __result; 163 } 164 165 // 2+1 iterators: size2 >= size1; used by std::swap_ranges. 166 template <class, class _Cl, class _Cr> 167 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<__bit_iterator<_Cl, false>, __bit_iterator<_Cr, false> > 168 __swap_ranges(__bit_iterator<_Cl, false> __first1, 169 __bit_iterator<_Cl, false> __last1, 170 __bit_iterator<_Cr, false> __first2) { 171 if (__first1.__ctz_ == __first2.__ctz_) 172 return std::make_pair(__last1, std::__swap_ranges_aligned(__first1, __last1, __first2)); 173 return std::make_pair(__last1, std::__swap_ranges_unaligned(__first1, __last1, __first2)); 174 } 175 176 // 2+2 iterators: used by std::ranges::swap_ranges. 177 template <class _AlgPolicy, class _Cl, class _Cr> 178 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<__bit_iterator<_Cl, false>, __bit_iterator<_Cr, false> > 179 __swap_ranges(__bit_iterator<_Cl, false> __first1, 180 __bit_iterator<_Cl, false> __last1, 181 __bit_iterator<_Cr, false> __first2, 182 __bit_iterator<_Cr, false> __last2) { 183 if (__last1 - __first1 < __last2 - __first2) 184 return std::make_pair(__last1, std::__swap_ranges<_AlgPolicy>(__first1, __last1, __first2).second); 185 return std::make_pair(std::__swap_ranges<_AlgPolicy>(__first2, __last2, __first1).second, __last2); 186 } 187 188 // 2+2 iterators: the shorter size will be used. 189 template <class _AlgPolicy, class _ForwardIterator1, class _Sentinel1, class _ForwardIterator2, class _Sentinel2> 190 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_ForwardIterator1, _ForwardIterator2> 191 __swap_ranges(_ForwardIterator1 __first1, _Sentinel1 __last1, _ForwardIterator2 __first2, _Sentinel2 __last2) { 192 while (__first1 != __last1 && __first2 != __last2) { 193 _IterOps<_AlgPolicy>::iter_swap(__first1, __first2); 194 ++__first1; 195 ++__first2; 196 } 197 198 return pair<_ForwardIterator1, _ForwardIterator2>(std::move(__first1), std::move(__first2)); 199 } 200 201 // 2+1 iterators: size2 >= size1. 202 template <class _AlgPolicy, class _ForwardIterator1, class _Sentinel1, class _ForwardIterator2> 203 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_ForwardIterator1, _ForwardIterator2> 204 __swap_ranges(_ForwardIterator1 __first1, _Sentinel1 __last1, _ForwardIterator2 __first2) { 205 while (__first1 != __last1) { 206 _IterOps<_AlgPolicy>::iter_swap(__first1, __first2); 207 ++__first1; 208 ++__first2; 209 } 210 211 return pair<_ForwardIterator1, _ForwardIterator2>(std::move(__first1), std::move(__first2)); 212 } 213 214 template <class _ForwardIterator1, class _ForwardIterator2> 215 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator2 216 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2) { 217 return std::__swap_ranges<_ClassicAlgPolicy>(std::move(__first1), std::move(__last1), std::move(__first2)).second; 218 } 219 220 _LIBCPP_END_NAMESPACE_STD 221 222 _LIBCPP_POP_MACROS 223 224 #endif // _LIBCPP___ALGORITHM_SWAP_RANGES_H 225