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