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
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 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
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 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.
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 _ForwardIterator2
216swap_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