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