xref: /freebsd/contrib/llvm-project/libcxx/include/__bit_reference (revision b64c5a0ace59af62eff52bfe110a521dc73c937b) 
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