1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP___BIT_REFERENCE
11#define _LIBCPP___BIT_REFERENCE
12
13#include <__algorithm/copy_n.h>
14#include <__algorithm/fill_n.h>
15#include <__algorithm/min.h>
16#include <__bit/countr.h>
17#include <__bit/invert_if.h>
18#include <__bit/popcount.h>
19#include <__compare/ordering.h>
20#include <__config>
21#include <__fwd/bit_reference.h>
22#include <__iterator/iterator_traits.h>
23#include <__memory/construct_at.h>
24#include <__memory/pointer_traits.h>
25#include <__type_traits/conditional.h>
26#include <__utility/swap.h>
27#include <cstring>
28
29#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
30# pragma GCC system_header
31#endif
32
33_LIBCPP_PUSH_MACROS
34#include <__undef_macros>
35
36_LIBCPP_BEGIN_NAMESPACE_STD
37
38template <class _Cp>
39class __bit_const_reference;
40
41template <class _Tp>
42struct __has_storage_type {
43 static const bool value = false;
44};
45
46template <class _Cp, bool = __has_storage_type<_Cp>::value>
47class __bit_reference {
48 using __storage_type = typename _Cp::__storage_type;
49 using __storage_pointer = typename _Cp::__storage_pointer;
50
51 __storage_pointer __seg_;
52 __storage_type __mask_;
53
54 friend typename _Cp::__self;
55
56 friend class __bit_const_reference<_Cp>;
57 friend class __bit_iterator<_Cp, false>;
58
59public:
60 using __container = typename _Cp::__self;
61
62 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_reference(const __bit_reference&) = default;
63
64 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 operator bool() const _NOEXCEPT {
65 return static_cast<bool>(*__seg_ & __mask_);
66 }
67 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool operator~() const _NOEXCEPT {
68 return !static_cast<bool>(*this);
69 }
70
71 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_reference& operator=(bool __x) _NOEXCEPT {
72 if (__x)
73 *__seg_ |= __mask_;
74 else
75 *__seg_ &= ~__mask_;
76 return *this;
77 }
78
79#if _LIBCPP_STD_VER >= 23
80 _LIBCPP_HIDE_FROM_ABI constexpr const __bit_reference& operator=(bool __x) const noexcept {
81 if (__x)
82 *__seg_ |= __mask_;
83 else
84 *__seg_ &= ~__mask_;
85 return *this;
86 }
87#endif
88
89 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_reference& operator=(const __bit_reference& __x) _NOEXCEPT {
90 return operator=(static_cast<bool>(__x));
91 }
92
93 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void flip() _NOEXCEPT { *__seg_ ^= __mask_; }
94 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, false> operator&() const _NOEXCEPT {
95 return __bit_iterator<_Cp, false>(__seg_, static_cast<unsigned>(std::__libcpp_ctz(__mask_)));
96 }
97
98private:
99 _LIBCPP_HIDE_FROM_ABI
100 _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit __bit_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT
101 : __seg_(__s),
102 __mask_(__m) {}
103};
104
105template <class _Cp>
106class __bit_reference<_Cp, false> {};
107
108template <class _Cp>
109inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
110swap(__bit_reference<_Cp> __x, __bit_reference<_Cp> __y) _NOEXCEPT {
111 bool __t = __x;
112 __x = __y;
113 __y = __t;
114}
115
116template <class _Cp, class _Dp>
117inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
118swap(__bit_reference<_Cp> __x, __bit_reference<_Dp> __y) _NOEXCEPT {
119 bool __t = __x;
120 __x = __y;
121 __y = __t;
122}
123
124template <class _Cp>
125inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void swap(__bit_reference<_Cp> __x, bool& __y) _NOEXCEPT {
126 bool __t = __x;
127 __x = __y;
128 __y = __t;
129}
130
131template <class _Cp>
132inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void swap(bool& __x, __bit_reference<_Cp> __y) _NOEXCEPT {
133 bool __t = __x;
134 __x = __y;
135 __y = __t;
136}
137
138template <class _Cp>
139class __bit_const_reference {
140 using __storage_type = typename _Cp::__storage_type;
141 using __storage_pointer = typename _Cp::__const_storage_pointer;
142
143 __storage_pointer __seg_;
144 __storage_type __mask_;
145
146 friend typename _Cp::__self;
147 friend class __bit_iterator<_Cp, true>;
148
149public:
150 using __container = typename _Cp::__self;
151
152 _LIBCPP_HIDE_FROM_ABI __bit_const_reference(const __bit_const_reference&) = default;
153 __bit_const_reference& operator=(const __bit_const_reference&) = delete;
154
155 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_const_reference(const __bit_reference<_Cp>& __x) _NOEXCEPT
156 : __seg_(__x.__seg_),
157 __mask_(__x.__mask_) {}
158
159 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR operator bool() const _NOEXCEPT {
160 return static_cast<bool>(*__seg_ & __mask_);
161 }
162
163 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, true> operator&() const _NOEXCEPT {
164 return __bit_iterator<_Cp, true>(__seg_, static_cast<unsigned>(std::__libcpp_ctz(__mask_)));
165 }
166
167private:
168 _LIBCPP_HIDE_FROM_ABI
169 _LIBCPP_CONSTEXPR explicit __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT
170 : __seg_(__s),
171 __mask_(__m) {}
172};
173
174// copy
175
176template <class _Cp, bool _IsConst>
177_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_aligned(
178 __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {
179 using _In = __bit_iterator<_Cp, _IsConst>;
180 using difference_type = typename _In::difference_type;
181 using __storage_type = typename _In::__storage_type;
182
183 const int __bits_per_word = _In::__bits_per_word;
184 difference_type __n = __last - __first;
185 if (__n > 0) {
186 // do first word
187 if (__first.__ctz_ != 0) {
188 unsigned __clz = __bits_per_word - __first.__ctz_;
189 difference_type __dn = std::min(static_cast<difference_type>(__clz), __n);
190 __n -= __dn;
191 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
192 __storage_type __b = *__first.__seg_ & __m;
193 *__result.__seg_ &= ~__m;
194 *__result.__seg_ |= __b;
195 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
196 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
197 ++__first.__seg_;
198 // __first.__ctz_ = 0;
199 }
200 // __first.__ctz_ == 0;
201 // do middle words
202 __storage_type __nw = __n / __bits_per_word;
203 std::copy_n(std::__to_address(__first.__seg_), __nw, std::__to_address(__result.__seg_));
204 __n -= __nw * __bits_per_word;
205 __result.__seg_ += __nw;
206 // do last word
207 if (__n > 0) {
208 __first.__seg_ += __nw;
209 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
210 __storage_type __b = *__first.__seg_ & __m;
211 *__result.__seg_ &= ~__m;
212 *__result.__seg_ |= __b;
213 __result.__ctz_ = static_cast<unsigned>(__n);
214 }
215 }
216 return __result;
217}
218
219template <class _Cp, bool _IsConst>
220_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_unaligned(
221 __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {
222 using _In = __bit_iterator<_Cp, _IsConst>;
223 using difference_type = typename _In::difference_type;
224 using __storage_type = typename _In::__storage_type;
225
226 const int __bits_per_word = _In::__bits_per_word;
227 difference_type __n = __last - __first;
228 if (__n > 0) {
229 // do first word
230 if (__first.__ctz_ != 0) {
231 unsigned __clz_f = __bits_per_word - __first.__ctz_;
232 difference_type __dn = std::min(static_cast<difference_type>(__clz_f), __n);
233 __n -= __dn;
234 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
235 __storage_type __b = *__first.__seg_ & __m;
236 unsigned __clz_r = __bits_per_word - __result.__ctz_;
237 __storage_type __ddn = std::min<__storage_type>(__dn, __clz_r);
238 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
239 *__result.__seg_ &= ~__m;
240 if (__result.__ctz_ > __first.__ctz_)
241 *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_);
242 else
243 *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_);
244 __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;
245 __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word);
246 __dn -= __ddn;
247 if (__dn > 0) {
248 __m = ~__storage_type(0) >> (__bits_per_word - __dn);
249 *__result.__seg_ &= ~__m;
250 *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn);
251 __result.__ctz_ = static_cast<unsigned>(__dn);
252 }
253 ++__first.__seg_;
254 // __first.__ctz_ = 0;
255 }
256 // __first.__ctz_ == 0;
257 // do middle words
258 unsigned __clz_r = __bits_per_word - __result.__ctz_;
259 __storage_type __m = ~__storage_type(0) << __result.__ctz_;
260 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) {
261 __storage_type __b = *__first.__seg_;
262 *__result.__seg_ &= ~__m;
263 *__result.__seg_ |= __b << __result.__ctz_;
264 ++__result.__seg_;
265 *__result.__seg_ &= __m;
266 *__result.__seg_ |= __b >> __clz_r;
267 }
268 // do last word
269 if (__n > 0) {
270 __m = ~__storage_type(0) >> (__bits_per_word - __n);
271 __storage_type __b = *__first.__seg_ & __m;
272 __storage_type __dn = std::min(__n, static_cast<difference_type>(__clz_r));
273 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
274 *__result.__seg_ &= ~__m;
275 *__result.__seg_ |= __b << __result.__ctz_;
276 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
277 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
278 __n -= __dn;
279 if (__n > 0) {
280 __m = ~__storage_type(0) >> (__bits_per_word - __n);
281 *__result.__seg_ &= ~__m;
282 *__result.__seg_ |= __b >> __dn;
283 __result.__ctz_ = static_cast<unsigned>(__n);
284 }
285 }
286 }
287 return __result;
288}
289
290template <class _Cp, bool _IsConst>
291inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, false>
292copy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {
293 if (__first.__ctz_ == __result.__ctz_)
294 return std::__copy_aligned(__first, __last, __result);
295 return std::__copy_unaligned(__first, __last, __result);
296}
297
298// copy_backward
299
300template <class _Cp, bool _IsConst>
301_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_backward_aligned(
302 __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {
303 using _In = __bit_iterator<_Cp, _IsConst>;
304 using difference_type = typename _In::difference_type;
305 using __storage_type = typename _In::__storage_type;
306
307 const int __bits_per_word = _In::__bits_per_word;
308 difference_type __n = __last - __first;
309 if (__n > 0) {
310 // do first word
311 if (__last.__ctz_ != 0) {
312 difference_type __dn = std::min(static_cast<difference_type>(__last.__ctz_), __n);
313 __n -= __dn;
314 unsigned __clz = __bits_per_word - __last.__ctz_;
315 __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz);
316 __storage_type __b = *__last.__seg_ & __m;
317 *__result.__seg_ &= ~__m;
318 *__result.__seg_ |= __b;
319 __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + __result.__ctz_) % __bits_per_word);
320 // __last.__ctz_ = 0
321 }
322 // __last.__ctz_ == 0 || __n == 0
323 // __result.__ctz_ == 0 || __n == 0
324 // do middle words
325 __storage_type __nw = __n / __bits_per_word;
326 __result.__seg_ -= __nw;
327 __last.__seg_ -= __nw;
328 std::copy_n(std::__to_address(__last.__seg_), __nw, std::__to_address(__result.__seg_));
329 __n -= __nw * __bits_per_word;
330 // do last word
331 if (__n > 0) {
332 __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n);
333 __storage_type __b = *--__last.__seg_ & __m;
334 *--__result.__seg_ &= ~__m;
335 *__result.__seg_ |= __b;
336 __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));
337 }
338 }
339 return __result;
340}
341
342template <class _Cp, bool _IsConst>
343_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_backward_unaligned(
344 __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {
345 using _In = __bit_iterator<_Cp, _IsConst>;
346 using difference_type = typename _In::difference_type;
347 using __storage_type = typename _In::__storage_type;
348
349 const int __bits_per_word = _In::__bits_per_word;
350 difference_type __n = __last - __first;
351 if (__n > 0) {
352 // do first word
353 if (__last.__ctz_ != 0) {
354 difference_type __dn = std::min(static_cast<difference_type>(__last.__ctz_), __n);
355 __n -= __dn;
356 unsigned __clz_l = __bits_per_word - __last.__ctz_;
357 __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l);
358 __storage_type __b = *__last.__seg_ & __m;
359 unsigned __clz_r = __bits_per_word - __result.__ctz_;
360 __storage_type __ddn = std::min(__dn, static_cast<difference_type>(__result.__ctz_));
361 if (__ddn > 0) {
362 __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r);
363 *__result.__seg_ &= ~__m;
364 if (__result.__ctz_ > __last.__ctz_)
365 *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);
366 else
367 *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_);
368 __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) + __result.__ctz_) % __bits_per_word);
369 __dn -= __ddn;
370 }
371 if (__dn > 0) {
372 // __result.__ctz_ == 0
373 --__result.__seg_;
374 __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1));
375 __m = ~__storage_type(0) << __result.__ctz_;
376 *__result.__seg_ &= ~__m;
377 __last.__ctz_ -= __dn + __ddn;
378 *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);
379 }
380 // __last.__ctz_ = 0
381 }
382 // __last.__ctz_ == 0 || __n == 0
383 // __result.__ctz_ != 0 || __n == 0
384 // do middle words
385 unsigned __clz_r = __bits_per_word - __result.__ctz_;
386 __storage_type __m = ~__storage_type(0) >> __clz_r;
387 for (; __n >= __bits_per_word; __n -= __bits_per_word) {
388 __storage_type __b = *--__last.__seg_;
389 *__result.__seg_ &= ~__m;
390 *__result.__seg_ |= __b >> __clz_r;
391 *--__result.__seg_ &= __m;
392 *__result.__seg_ |= __b << __result.__ctz_;
393 }
394 // do last word
395 if (__n > 0) {
396 __m = ~__storage_type(0) << (__bits_per_word - __n);
397 __storage_type __b = *--__last.__seg_ & __m;
398 __clz_r = __bits_per_word - __result.__ctz_;
399 __storage_type __dn = std::min(__n, static_cast<difference_type>(__result.__ctz_));
400 __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r);
401 *__result.__seg_ &= ~__m;
402 *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_);
403 __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + __result.__ctz_) % __bits_per_word);
404 __n -= __dn;
405 if (__n > 0) {
406 // __result.__ctz_ == 0
407 --__result.__seg_;
408 __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));
409 __m = ~__storage_type(0) << __result.__ctz_;
410 *__result.__seg_ &= ~__m;
411 *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn));
412 }
413 }
414 }
415 return __result;
416}
417
418template <class _Cp, bool _IsConst>
419inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, false> copy_backward(
420 __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {
421 if (__last.__ctz_ == __result.__ctz_)
422 return std::__copy_backward_aligned(__first, __last, __result);
423 return std::__copy_backward_unaligned(__first, __last, __result);
424}
425
426// move
427
428template <class _Cp, bool _IsConst>
429inline _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false>
430move(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {
431 return std::copy(__first, __last, __result);
432}
433
434// move_backward
435
436template <class _Cp, bool _IsConst>
437inline _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> move_backward(
438 __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {
439 return std::copy_backward(__first, __last, __result);
440}
441
442// swap_ranges
443
444template <class _Cl, class _Cr>
445_LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cr, false> __swap_ranges_aligned(
446 __bit_iterator<_Cl, false> __first, __bit_iterator<_Cl, false> __last, __bit_iterator<_Cr, false> __result) {
447 using _I1 = __bit_iterator<_Cl, false>;
448 using difference_type = typename _I1::difference_type;
449 using __storage_type = typename _I1::__storage_type;
450
451 const int __bits_per_word = _I1::__bits_per_word;
452 difference_type __n = __last - __first;
453 if (__n > 0) {
454 // do first word
455 if (__first.__ctz_ != 0) {
456 unsigned __clz = __bits_per_word - __first.__ctz_;
457 difference_type __dn = std::min(static_cast<difference_type>(__clz), __n);
458 __n -= __dn;
459 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
460 __storage_type __b1 = *__first.__seg_ & __m;
461 *__first.__seg_ &= ~__m;
462 __storage_type __b2 = *__result.__seg_ & __m;
463 *__result.__seg_ &= ~__m;
464 *__result.__seg_ |= __b1;
465 *__first.__seg_ |= __b2;
466 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
467 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
468 ++__first.__seg_;
469 // __first.__ctz_ = 0;
470 }
471 // __first.__ctz_ == 0;
472 // do middle words
473 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_)
474 swap(*__first.__seg_, *__result.__seg_);
475 // do last word
476 if (__n > 0) {
477 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
478 __storage_type __b1 = *__first.__seg_ & __m;
479 *__first.__seg_ &= ~__m;
480 __storage_type __b2 = *__result.__seg_ & __m;
481 *__result.__seg_ &= ~__m;
482 *__result.__seg_ |= __b1;
483 *__first.__seg_ |= __b2;
484 __result.__ctz_ = static_cast<unsigned>(__n);
485 }
486 }
487 return __result;
488}
489
490template <class _Cl, class _Cr>
491_LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cr, false> __swap_ranges_unaligned(
492 __bit_iterator<_Cl, false> __first, __bit_iterator<_Cl, false> __last, __bit_iterator<_Cr, false> __result) {
493 using _I1 = __bit_iterator<_Cl, false>;
494 using difference_type = typename _I1::difference_type;
495 using __storage_type = typename _I1::__storage_type;
496
497 const int __bits_per_word = _I1::__bits_per_word;
498 difference_type __n = __last - __first;
499 if (__n > 0) {
500 // do first word
501 if (__first.__ctz_ != 0) {
502 unsigned __clz_f = __bits_per_word - __first.__ctz_;
503 difference_type __dn = std::min(static_cast<difference_type>(__clz_f), __n);
504 __n -= __dn;
505 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
506 __storage_type __b1 = *__first.__seg_ & __m;
507 *__first.__seg_ &= ~__m;
508 unsigned __clz_r = __bits_per_word - __result.__ctz_;
509 __storage_type __ddn = std::min<__storage_type>(__dn, __clz_r);
510 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
511 __storage_type __b2 = *__result.__seg_ & __m;
512 *__result.__seg_ &= ~__m;
513 if (__result.__ctz_ > __first.__ctz_) {
514 unsigned __s = __result.__ctz_ - __first.__ctz_;
515 *__result.__seg_ |= __b1 << __s;
516 *__first.__seg_ |= __b2 >> __s;
517 } else {
518 unsigned __s = __first.__ctz_ - __result.__ctz_;
519 *__result.__seg_ |= __b1 >> __s;
520 *__first.__seg_ |= __b2 << __s;
521 }
522 __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;
523 __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word);
524 __dn -= __ddn;
525 if (__dn > 0) {
526 __m = ~__storage_type(0) >> (__bits_per_word - __dn);
527 __b2 = *__result.__seg_ & __m;
528 *__result.__seg_ &= ~__m;
529 unsigned __s = __first.__ctz_ + __ddn;
530 *__result.__seg_ |= __b1 >> __s;
531 *__first.__seg_ |= __b2 << __s;
532 __result.__ctz_ = static_cast<unsigned>(__dn);
533 }
534 ++__first.__seg_;
535 // __first.__ctz_ = 0;
536 }
537 // __first.__ctz_ == 0;
538 // do middle words
539 __storage_type __m = ~__storage_type(0) << __result.__ctz_;
540 unsigned __clz_r = __bits_per_word - __result.__ctz_;
541 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) {
542 __storage_type __b1 = *__first.__seg_;
543 __storage_type __b2 = *__result.__seg_ & __m;
544 *__result.__seg_ &= ~__m;
545 *__result.__seg_ |= __b1 << __result.__ctz_;
546 *__first.__seg_ = __b2 >> __result.__ctz_;
547 ++__result.__seg_;
548 __b2 = *__result.__seg_ & ~__m;
549 *__result.__seg_ &= __m;
550 *__result.__seg_ |= __b1 >> __clz_r;
551 *__first.__seg_ |= __b2 << __clz_r;
552 }
553 // do last word
554 if (__n > 0) {
555 __m = ~__storage_type(0) >> (__bits_per_word - __n);
556 __storage_type __b1 = *__first.__seg_ & __m;
557 *__first.__seg_ &= ~__m;
558 __storage_type __dn = std::min<__storage_type>(__n, __clz_r);
559 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
560 __storage_type __b2 = *__result.__seg_ & __m;
561 *__result.__seg_ &= ~__m;
562 *__result.__seg_ |= __b1 << __result.__ctz_;
563 *__first.__seg_ |= __b2 >> __result.__ctz_;
564 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
565 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
566 __n -= __dn;
567 if (__n > 0) {
568 __m = ~__storage_type(0) >> (__bits_per_word - __n);
569 __b2 = *__result.__seg_ & __m;
570 *__result.__seg_ &= ~__m;
571 *__result.__seg_ |= __b1 >> __dn;
572 *__first.__seg_ |= __b2 << __dn;
573 __result.__ctz_ = static_cast<unsigned>(__n);
574 }
575 }
576 }
577 return __result;
578}
579
580template <class _Cl, class _Cr>
581inline _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cr, false> swap_ranges(
582 __bit_iterator<_Cl, false> __first1, __bit_iterator<_Cl, false> __last1, __bit_iterator<_Cr, false> __first2) {
583 if (__first1.__ctz_ == __first2.__ctz_)
584 return std::__swap_ranges_aligned(__first1, __last1, __first2);
585 return std::__swap_ranges_unaligned(__first1, __last1, __first2);
586}
587
588// rotate
589
590template <class _Cp>
591struct __bit_array {
592 using difference_type = typename _Cp::difference_type;
593 using __storage_type = typename _Cp::__storage_type;
594 using __storage_pointer = typename _Cp::__storage_pointer;
595 using iterator = typename _Cp::iterator;
596
597 static const unsigned __bits_per_word = _Cp::__bits_per_word;
598 static const unsigned _Np = 4;
599
600 difference_type __size_;
601 __storage_type __word_[_Np];
602
603 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static difference_type capacity() {
604 return static_cast<difference_type>(_Np * __bits_per_word);
605 }
606 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit __bit_array(difference_type __s) : __size_(__s) {
607 if (__libcpp_is_constant_evaluated()) {
608 for (size_t __i = 0; __i != __bit_array<_Cp>::_Np; ++__i)
609 std::__construct_at(__word_ + __i, 0);
610 }
611 }
612 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator begin() {
613 return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]), 0);
614 }
615 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator end() {
616 return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]) + __size_ / __bits_per_word,
617 static_cast<unsigned>(__size_ % __bits_per_word));
618 }
619};
620
621template <class _Cp>
622_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false>
623rotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last) {
624 using _I1 = __bit_iterator<_Cp, false>;
625 using difference_type = typename _I1::difference_type;
626
627 difference_type __d1 = __middle - __first;
628 difference_type __d2 = __last - __middle;
629 _I1 __r = __first + __d2;
630 while (__d1 != 0 && __d2 != 0) {
631 if (__d1 <= __d2) {
632 if (__d1 <= __bit_array<_Cp>::capacity()) {
633 __bit_array<_Cp> __b(__d1);
634 std::copy(__first, __middle, __b.begin());
635 std::copy(__b.begin(), __b.end(), std::copy(__middle, __last, __first));
636 break;
637 } else {
638 __bit_iterator<_Cp, false> __mp = std::swap_ranges(__first, __middle, __middle);
639 __first = __middle;
640 __middle = __mp;
641 __d2 -= __d1;
642 }
643 } else {
644 if (__d2 <= __bit_array<_Cp>::capacity()) {
645 __bit_array<_Cp> __b(__d2);
646 std::copy(__middle, __last, __b.begin());
647 std::copy_backward(__b.begin(), __b.end(), std::copy_backward(__first, __middle, __last));
648 break;
649 } else {
650 __bit_iterator<_Cp, false> __mp = __first + __d2;
651 std::swap_ranges(__first, __mp, __middle);
652 __first = __mp;
653 __d1 -= __d2;
654 }
655 }
656 }
657 return __r;
658}
659
660// equal
661
662template <class _Cp, bool _IC1, bool _IC2>
663_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool __equal_unaligned(
664 __bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) {
665 using _It = __bit_iterator<_Cp, _IC1>;
666 using difference_type = typename _It::difference_type;
667 using __storage_type = typename _It::__storage_type;
668
669 const int __bits_per_word = _It::__bits_per_word;
670 difference_type __n = __last1 - __first1;
671 if (__n > 0) {
672 // do first word
673 if (__first1.__ctz_ != 0) {
674 unsigned __clz_f = __bits_per_word - __first1.__ctz_;
675 difference_type __dn = std::min(static_cast<difference_type>(__clz_f), __n);
676 __n -= __dn;
677 __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
678 __storage_type __b = *__first1.__seg_ & __m;
679 unsigned __clz_r = __bits_per_word - __first2.__ctz_;
680 __storage_type __ddn = std::min<__storage_type>(__dn, __clz_r);
681 __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
682 if (__first2.__ctz_ > __first1.__ctz_) {
683 if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_)))
684 return false;
685 } else {
686 if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_)))
687 return false;
688 }
689 __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word;
690 __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word);
691 __dn -= __ddn;
692 if (__dn > 0) {
693 __m = ~__storage_type(0) >> (__bits_per_word - __dn);
694 if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn)))
695 return false;
696 __first2.__ctz_ = static_cast<unsigned>(__dn);
697 }
698 ++__first1.__seg_;
699 // __first1.__ctz_ = 0;
700 }
701 // __first1.__ctz_ == 0;
702 // do middle words
703 unsigned __clz_r = __bits_per_word - __first2.__ctz_;
704 __storage_type __m = ~__storage_type(0) << __first2.__ctz_;
705 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_) {
706 __storage_type __b = *__first1.__seg_;
707 if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_))
708 return false;
709 ++__first2.__seg_;
710 if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r))
711 return false;
712 }
713 // do last word
714 if (__n > 0) {
715 __m = ~__storage_type(0) >> (__bits_per_word - __n);
716 __storage_type __b = *__first1.__seg_ & __m;
717 __storage_type __dn = std::min(__n, static_cast<difference_type>(__clz_r));
718 __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
719 if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_))
720 return false;
721 __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word;
722 __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word);
723 __n -= __dn;
724 if (__n > 0) {
725 __m = ~__storage_type(0) >> (__bits_per_word - __n);
726 if ((*__first2.__seg_ & __m) != (__b >> __dn))
727 return false;
728 }
729 }
730 }
731 return true;
732}
733
734template <class _Cp, bool _IC1, bool _IC2>
735_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool __equal_aligned(
736 __bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) {
737 using _It = __bit_iterator<_Cp, _IC1>;
738 using difference_type = typename _It::difference_type;
739 using __storage_type = typename _It::__storage_type;
740
741 const int __bits_per_word = _It::__bits_per_word;
742 difference_type __n = __last1 - __first1;
743 if (__n > 0) {
744 // do first word
745 if (__first1.__ctz_ != 0) {
746 unsigned __clz = __bits_per_word - __first1.__ctz_;
747 difference_type __dn = std::min(static_cast<difference_type>(__clz), __n);
748 __n -= __dn;
749 __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
750 if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))
751 return false;
752 ++__first2.__seg_;
753 ++__first1.__seg_;
754 // __first1.__ctz_ = 0;
755 // __first2.__ctz_ = 0;
756 }
757 // __first1.__ctz_ == 0;
758 // __first2.__ctz_ == 0;
759 // do middle words
760 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_)
761 if (*__first2.__seg_ != *__first1.__seg_)
762 return false;
763 // do last word
764 if (__n > 0) {
765 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
766 if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))
767 return false;
768 }
769 }
770 return true;
771}
772
773template <class _Cp, bool _IC1, bool _IC2>
774inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool
775equal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) {
776 if (__first1.__ctz_ == __first2.__ctz_)
777 return std::__equal_aligned(__first1, __last1, __first2);
778 return std::__equal_unaligned(__first1, __last1, __first2);
779}
780
781template <class _Cp, bool _IsConst, typename _Cp::__storage_type>
782class __bit_iterator {
783public:
784 using difference_type = typename _Cp::difference_type;
785 using value_type = bool;
786 using pointer = __bit_iterator;
787#ifndef _LIBCPP_ABI_BITSET_VECTOR_BOOL_CONST_SUBSCRIPT_RETURN_BOOL
788 using reference = __conditional_t<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >;
789#else
790 using reference = __conditional_t<_IsConst, bool, __bit_reference<_Cp> >;
791#endif
792 using iterator_category = random_access_iterator_tag;
793
794private:
795 using __storage_type = typename _Cp::__storage_type;
796 using __storage_pointer =
797 __conditional_t<_IsConst, typename _Cp::__const_storage_pointer, typename _Cp::__storage_pointer>;
798
799 static const unsigned __bits_per_word = _Cp::__bits_per_word;
800
801 __storage_pointer __seg_;
802 unsigned __ctz_;
803
804public:
805 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator() _NOEXCEPT
806#if _LIBCPP_STD_VER >= 14
807 : __seg_(nullptr),
808 __ctz_(0)
809#endif
810 {
811 }
812
813 // When _IsConst=false, this is the copy constructor.
814 // It is non-trivial. Making it trivial would break ABI.
815 // When _IsConst=true, this is a converting constructor;
816 // the copy and move constructors are implicitly generated
817 // and trivial.
818 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT
819 : __seg_(__it.__seg_),
820 __ctz_(__it.__ctz_) {}
821
822 // When _IsConst=false, we have a user-provided copy constructor,
823 // so we must also provide a copy assignment operator because
824 // the implicit generation of a defaulted one is deprecated.
825 // When _IsConst=true, the assignment operators are
826 // implicitly generated and trivial.
827 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator&
828 operator=(const _If<_IsConst, struct __private_nat, __bit_iterator>& __it) {
829 __seg_ = __it.__seg_;
830 __ctz_ = __it.__ctz_;
831 return *this;
832 }
833
834 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference operator*() const _NOEXCEPT {
835 return __conditional_t<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >(
836 __seg_, __storage_type(1) << __ctz_);
837 }
838
839 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator++() {
840 if (__ctz_ != __bits_per_word - 1)
841 ++__ctz_;
842 else {
843 __ctz_ = 0;
844 ++__seg_;
845 }
846 return *this;
847 }
848
849 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator++(int) {
850 __bit_iterator __tmp = *this;
851 ++(*this);
852 return __tmp;
853 }
854
855 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator--() {
856 if (__ctz_ != 0)
857 --__ctz_;
858 else {
859 __ctz_ = __bits_per_word - 1;
860 --__seg_;
861 }
862 return *this;
863 }
864
865 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator--(int) {
866 __bit_iterator __tmp = *this;
867 --(*this);
868 return __tmp;
869 }
870
871 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator+=(difference_type __n) {
872 if (__n >= 0)
873 __seg_ += (__n + __ctz_) / __bits_per_word;
874 else
875 __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1) /
876 static_cast<difference_type>(__bits_per_word);
877 __n &= (__bits_per_word - 1);
878 __ctz_ = static_cast<unsigned>((__n + __ctz_) % __bits_per_word);
879 return *this;
880 }
881
882 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator-=(difference_type __n) {
883 return *this += -__n;
884 }
885
886 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator+(difference_type __n) const {
887 __bit_iterator __t(*this);
888 __t += __n;
889 return __t;
890 }
891
892 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator-(difference_type __n) const {
893 __bit_iterator __t(*this);
894 __t -= __n;
895 return __t;
896 }
897
898 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator
899 operator+(difference_type __n, const __bit_iterator& __it) {
900 return __it + __n;
901 }
902
903 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend difference_type
904 operator-(const __bit_iterator& __x, const __bit_iterator& __y) {
905 return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;
906 }
907
908 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference operator[](difference_type __n) const {
909 return *(*this + __n);
910 }
911
912 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
913 operator==(const __bit_iterator& __x, const __bit_iterator& __y) {
914 return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;
915 }
916
917#if _LIBCPP_STD_VER <= 17
918 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
919 operator!=(const __bit_iterator& __x, const __bit_iterator& __y) {
920 return !(__x == __y);
921 }
922
923 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
924 operator<(const __bit_iterator& __x, const __bit_iterator& __y) {
925 return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);
926 }
927
928 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
929 operator>(const __bit_iterator& __x, const __bit_iterator& __y) {
930 return __y < __x;
931 }
932
933 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
934 operator<=(const __bit_iterator& __x, const __bit_iterator& __y) {
935 return !(__y < __x);
936 }
937
938 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
939 operator>=(const __bit_iterator& __x, const __bit_iterator& __y) {
940 return !(__x < __y);
941 }
942#else // _LIBCPP_STD_VER <= 17
943 _LIBCPP_HIDE_FROM_ABI constexpr friend strong_ordering
944 operator<=>(const __bit_iterator& __x, const __bit_iterator& __y) {
945 if (__x.__seg_ < __y.__seg_)
946 return strong_ordering::less;
947
948 if (__x.__seg_ == __y.__seg_)
949 return __x.__ctz_ <=> __y.__ctz_;
950
951 return strong_ordering::greater;
952 }
953#endif // _LIBCPP_STD_VER <= 17
954
955private:
956 _LIBCPP_HIDE_FROM_ABI
957 _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT
958 : __seg_(__s),
959 __ctz_(__ctz) {}
960
961 friend typename _Cp::__self;
962
963 friend class __bit_reference<_Cp>;
964 friend class __bit_const_reference<_Cp>;
965 friend class __bit_iterator<_Cp, true>;
966 template <class _Dp>
967 friend struct __bit_array;
968
969 template <bool _FillVal, class _Dp>
970 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend void
971 __fill_n_bool(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n);
972
973 template <class _Dp, bool _IC>
974 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> __copy_aligned(
975 __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result);
976 template <class _Dp, bool _IC>
977 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> __copy_unaligned(
978 __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result);
979 template <class _Dp, bool _IC>
980 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false>
981 copy(__bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result);
982 template <class _Dp, bool _IC>
983 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> __copy_backward_aligned(
984 __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result);
985 template <class _Dp, bool _IC>
986 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> __copy_backward_unaligned(
987 __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result);
988 template <class _Dp, bool _IC>
989 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false>
990 copy_backward(__bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result);
991 template <class _Cl, class _Cr>
992 friend __bit_iterator<_Cr, false>
993 __swap_ranges_aligned(__bit_iterator<_Cl, false>, __bit_iterator<_Cl, false>, __bit_iterator<_Cr, false>);
994 template <class _Cl, class _Cr>
995 friend __bit_iterator<_Cr, false>
996 __swap_ranges_unaligned(__bit_iterator<_Cl, false>, __bit_iterator<_Cl, false>, __bit_iterator<_Cr, false>);
997 template <class _Cl, class _Cr>
998 friend __bit_iterator<_Cr, false>
999 swap_ranges(__bit_iterator<_Cl, false>, __bit_iterator<_Cl, false>, __bit_iterator<_Cr, false>);
1000 template <class _Dp>
1001 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false>
1002 rotate(__bit_iterator<_Dp, false>, __bit_iterator<_Dp, false>, __bit_iterator<_Dp, false>);
1003 template <class _Dp, bool _IC1, bool _IC2>
1004 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
1005 __equal_aligned(__bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC2>);
1006 template <class _Dp, bool _IC1, bool _IC2>
1007 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
1008 __equal_unaligned(__bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC2>);
1009 template <class _Dp, bool _IC1, bool _IC2>
1010 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
1011 equal(__bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC2>);
1012 template <bool _ToFind, class _Dp, bool _IC>
1013 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, _IC>
1014 __find_bool(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
1015 template <bool _ToCount, class _Dp, bool _IC>
1016 friend typename __bit_iterator<_Dp, _IC>::difference_type _LIBCPP_HIDE_FROM_ABI
1017 _LIBCPP_CONSTEXPR_SINCE_CXX20 __count_bool(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
1018};
1019
1020_LIBCPP_END_NAMESPACE_STD
1021
1022_LIBCPP_POP_MACROS
1023
1024#endif // _LIBCPP___BIT_REFERENCE
1025