225 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_SWAP_RANGES_H10#define _LIBCPP___ALGORITHM_SWAP_RANGES_H11 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_header22#endif23 24_LIBCPP_PUSH_MACROS25#include <__undef_macros>26 27_LIBCPP_BEGIN_NAMESPACE_STD28 29template <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 word40 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 words58 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_)59 swap(*__first.__seg_, *__result.__seg_);60 // do last word61 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 75template <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 word86 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 words124 __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 word139 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.166template <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.177template <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.189template <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.202template <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 214template <class _ForwardIterator1, class _ForwardIterator2>215inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator2216swap_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_STD221 222_LIBCPP_POP_MACROS223 224#endif // _LIBCPP___ALGORITHM_SWAP_RANGES_H225