libcxx/include/__cxx03/__bit_reference

   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___CXX03___BIT_REFERENCE
  11 #define _LIBCPP___CXX03___BIT_REFERENCE
  12
  13 #include <__cxx03/__algorithm/copy_n.h>
  14 #include <__cxx03/__algorithm/fill_n.h>
  15 #include <__cxx03/__algorithm/min.h>
  16 #include <__cxx03/__bit/countr.h>
  17 #include <__cxx03/__bit/invert_if.h>
  18 #include <__cxx03/__bit/popcount.h>
  19 #include <__cxx03/__compare/ordering.h>
  20 #include <__cxx03/__config>
  21 #include <__cxx03/__fwd/bit_reference.h>
  22 #include <__cxx03/__iterator/iterator_traits.h>
  23 #include <__cxx03/__memory/construct_at.h>
  24 #include <__cxx03/__memory/pointer_traits.h>
  25 #include <__cxx03/__type_traits/conditional.h>
  26 #include <__cxx03/__utility/swap.h>
  27 #include <__cxx03/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 <__cxx03/__undef_macros>
  35
  36 _LIBCPP_BEGIN_NAMESPACE_STD
  37
  38 template <class _Cp>
  39 class __bit_const_reference;
  40
  41 template <class _Tp>
  42 struct __has_storage_type {
  43   static const bool value = false;
  44 };
  45
  46 template <class _Cp, bool = __has_storage_type<_Cp>::value>
  47 class __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
  59 public:
  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
  98 private:
  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
 105 template <class _Cp>
 106 class __bit_reference<_Cp, false> {};
 107
 108 template <class _Cp>
 109 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
 110 swap(__bit_reference<_Cp> __x, __bit_reference<_Cp> __y) _NOEXCEPT {
 111   bool __t = __x;
 112   __x      = __y;
 113   __y      = __t;
 114 }
 115
 116 template <class _Cp, class _Dp>
 117 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
 118 swap(__bit_reference<_Cp> __x, __bit_reference<_Dp> __y) _NOEXCEPT {
 119   bool __t = __x;
 120   __x      = __y;
 121   __y      = __t;
 122 }
 123
 124 template <class _Cp>
 125 inline _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
 131 template <class _Cp>
 132 inline _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
 138 template <class _Cp>
 139 class __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
 149 public:
 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
 167 private:
 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
 176 template <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
 219 template <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
 290 template <class _Cp, bool _IsConst>
 291 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, false>
 292 copy(__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
 300 template <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
 342 template <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
 418 template <class _Cp, bool _IsConst>
 419 inline _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
 428 template <class _Cp, bool _IsConst>
 429 inline _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false>
 430 move(__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
 436 template <class _Cp, bool _IsConst>
 437 inline _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
 444 template <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
 490 template <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
 580 template <class _Cl, class _Cr>
 581 inline _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
 590 template <class _Cp>
 591 struct __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
 621 template <class _Cp>
 622 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false>
 623 rotate(__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
 662 template <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
 734 template <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
 773 template <class _Cp, bool _IC1, bool _IC2>
 774 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool
 775 equal(__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
 781 template <class _Cp, bool _IsConst, typename _Cp::__storage_type>
 782 class __bit_iterator {
 783 public:
 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
 794 private:
 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
 804 public:
 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
 955 private:
 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___CXX03___BIT_REFERENCE