xref: /freebsd/contrib/llvm-project/libcxx/include/__bit_reference (revision 868ee3f2855615016ba87c14b9444c18a2e1ba30)
10b57cec5SDimitry Andric// -*- C++ -*-
20b57cec5SDimitry Andric//===----------------------------------------------------------------------===//
30b57cec5SDimitry Andric//
40b57cec5SDimitry Andric// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
50b57cec5SDimitry Andric// See https://llvm.org/LICENSE.txt for license information.
60b57cec5SDimitry Andric// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
70b57cec5SDimitry Andric//
80b57cec5SDimitry Andric//===----------------------------------------------------------------------===//
90b57cec5SDimitry Andric
100b57cec5SDimitry Andric#ifndef _LIBCPP___BIT_REFERENCE
110b57cec5SDimitry Andric#define _LIBCPP___BIT_REFERENCE
120b57cec5SDimitry Andric
1361cfbce3SDimitry Andric#include <__algorithm/copy_n.h>
1461cfbce3SDimitry Andric#include <__algorithm/fill_n.h>
1581ad6265SDimitry Andric#include <__algorithm/min.h>
16bdd1243dSDimitry Andric#include <__bit/countr.h>
175f757f3fSDimitry Andric#include <__bit/invert_if.h>
18bdd1243dSDimitry Andric#include <__bit/popcount.h>
1904eeddc0SDimitry Andric#include <__config>
205f757f3fSDimitry Andric#include <__fwd/bit_reference.h>
2181ad6265SDimitry Andric#include <__iterator/iterator_traits.h>
2261cfbce3SDimitry Andric#include <__memory/construct_at.h>
2381ad6265SDimitry Andric#include <__memory/pointer_traits.h>
2406c3fb27SDimitry Andric#include <__type_traits/conditional.h>
2506c3fb27SDimitry Andric#include <__utility/swap.h>
2681ad6265SDimitry Andric#include <cstring>
270b57cec5SDimitry Andric
280b57cec5SDimitry Andric#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
290b57cec5SDimitry Andric#  pragma GCC system_header
300b57cec5SDimitry Andric#endif
310b57cec5SDimitry Andric
320b57cec5SDimitry Andric_LIBCPP_PUSH_MACROS
330b57cec5SDimitry Andric#include <__undef_macros>
340b57cec5SDimitry Andric
350b57cec5SDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD
360b57cec5SDimitry Andric
375f757f3fSDimitry Andrictemplate <class _Cp>
385f757f3fSDimitry Andricclass __bit_const_reference;
390b57cec5SDimitry Andric
400b57cec5SDimitry Andrictemplate <class _Tp>
415f757f3fSDimitry Andricstruct __has_storage_type {
420b57cec5SDimitry Andric  static const bool value = false;
430b57cec5SDimitry Andric};
440b57cec5SDimitry Andric
450b57cec5SDimitry Andrictemplate <class _Cp, bool = __has_storage_type<_Cp>::value>
465f757f3fSDimitry Andricclass __bit_reference {
475f757f3fSDimitry Andric  using __storage_type    = typename _Cp::__storage_type;
485f757f3fSDimitry Andric  using __storage_pointer = typename _Cp::__storage_pointer;
490b57cec5SDimitry Andric
500b57cec5SDimitry Andric  __storage_pointer __seg_;
510b57cec5SDimitry Andric  __storage_type __mask_;
520b57cec5SDimitry Andric
530b57cec5SDimitry Andric  friend typename _Cp::__self;
540b57cec5SDimitry Andric
550b57cec5SDimitry Andric  friend class __bit_const_reference<_Cp>;
560b57cec5SDimitry Andric  friend class __bit_iterator<_Cp, false>;
575f757f3fSDimitry Andric
580b57cec5SDimitry Andricpublic:
59bdd1243dSDimitry Andric  using __container = typename _Cp::__self;
60bdd1243dSDimitry Andric
615f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_reference(const __bit_reference&) = default;
62480093f4SDimitry Andric
635f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 operator bool() const _NOEXCEPT {
645f757f3fSDimitry Andric    return static_cast<bool>(*__seg_ & __mask_);
655f757f3fSDimitry Andric  }
665f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool operator~() const _NOEXCEPT {
675f757f3fSDimitry Andric    return !static_cast<bool>(*this);
685f757f3fSDimitry Andric  }
690b57cec5SDimitry Andric
705f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_reference& operator=(bool __x) _NOEXCEPT {
710b57cec5SDimitry Andric    if (__x)
720b57cec5SDimitry Andric      *__seg_ |= __mask_;
730b57cec5SDimitry Andric    else
740b57cec5SDimitry Andric      *__seg_ &= ~__mask_;
750b57cec5SDimitry Andric    return *this;
760b57cec5SDimitry Andric  }
770b57cec5SDimitry Andric
7806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23
7961cfbce3SDimitry Andric  _LIBCPP_HIDE_FROM_ABI constexpr const __bit_reference& operator=(bool __x) const noexcept {
8081ad6265SDimitry Andric    if (__x)
8181ad6265SDimitry Andric      *__seg_ |= __mask_;
8281ad6265SDimitry Andric    else
8381ad6265SDimitry Andric      *__seg_ &= ~__mask_;
8481ad6265SDimitry Andric    return *this;
8581ad6265SDimitry Andric  }
8681ad6265SDimitry Andric#endif
8781ad6265SDimitry Andric
885f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_reference& operator=(const __bit_reference& __x) _NOEXCEPT {
895f757f3fSDimitry Andric    return operator=(static_cast<bool>(__x));
905f757f3fSDimitry Andric  }
910b57cec5SDimitry Andric
925f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void flip() _NOEXCEPT { *__seg_ ^= __mask_; }
935f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, false> operator&() const _NOEXCEPT {
945f757f3fSDimitry Andric    return __bit_iterator<_Cp, false>(__seg_, static_cast<unsigned>(std::__libcpp_ctz(__mask_)));
955f757f3fSDimitry Andric  }
965f757f3fSDimitry Andric
970b57cec5SDimitry Andricprivate:
985f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit __bit_reference(
995f757f3fSDimitry Andric      __storage_pointer __s, __storage_type __m) _NOEXCEPT
1005f757f3fSDimitry Andric      : __seg_(__s),
1015f757f3fSDimitry Andric        __mask_(__m) {}
1020b57cec5SDimitry Andric};
1030b57cec5SDimitry Andric
1040b57cec5SDimitry Andrictemplate <class _Cp>
1055f757f3fSDimitry Andricclass __bit_reference<_Cp, false> {};
1060b57cec5SDimitry Andric
1070b57cec5SDimitry Andrictemplate <class _Cp>
1085f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
1095f757f3fSDimitry Andricswap(__bit_reference<_Cp> __x, __bit_reference<_Cp> __y) _NOEXCEPT {
1100b57cec5SDimitry Andric  bool __t = __x;
1110b57cec5SDimitry Andric  __x      = __y;
1120b57cec5SDimitry Andric  __y      = __t;
1130b57cec5SDimitry Andric}
1140b57cec5SDimitry Andric
1150b57cec5SDimitry Andrictemplate <class _Cp, class _Dp>
1165f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
1175f757f3fSDimitry Andricswap(__bit_reference<_Cp> __x, __bit_reference<_Dp> __y) _NOEXCEPT {
1180b57cec5SDimitry Andric  bool __t = __x;
1190b57cec5SDimitry Andric  __x      = __y;
1200b57cec5SDimitry Andric  __y      = __t;
1210b57cec5SDimitry Andric}
1220b57cec5SDimitry Andric
1230b57cec5SDimitry Andrictemplate <class _Cp>
1245f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void swap(__bit_reference<_Cp> __x, bool& __y) _NOEXCEPT {
1250b57cec5SDimitry Andric  bool __t = __x;
1260b57cec5SDimitry Andric  __x      = __y;
1270b57cec5SDimitry Andric  __y      = __t;
1280b57cec5SDimitry Andric}
1290b57cec5SDimitry Andric
1300b57cec5SDimitry Andrictemplate <class _Cp>
1315f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void swap(bool& __x, __bit_reference<_Cp> __y) _NOEXCEPT {
1320b57cec5SDimitry Andric  bool __t = __x;
1330b57cec5SDimitry Andric  __x      = __y;
1340b57cec5SDimitry Andric  __y      = __t;
1350b57cec5SDimitry Andric}
1360b57cec5SDimitry Andric
1370b57cec5SDimitry Andrictemplate <class _Cp>
1385f757f3fSDimitry Andricclass __bit_const_reference {
1395f757f3fSDimitry Andric  using __storage_type    = typename _Cp::__storage_type;
1405f757f3fSDimitry Andric  using __storage_pointer = typename _Cp::__const_storage_pointer;
1410b57cec5SDimitry Andric
1420b57cec5SDimitry Andric  __storage_pointer __seg_;
1430b57cec5SDimitry Andric  __storage_type __mask_;
1440b57cec5SDimitry Andric
1450b57cec5SDimitry Andric  friend typename _Cp::__self;
1460b57cec5SDimitry Andric  friend class __bit_iterator<_Cp, true>;
1475f757f3fSDimitry Andric
1480b57cec5SDimitry Andricpublic:
14906c3fb27SDimitry Andric  using __container = typename _Cp::__self;
15006c3fb27SDimitry Andric
1515f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __bit_const_reference(const __bit_const_reference&) = default;
152480093f4SDimitry Andric
1535f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_const_reference(const __bit_reference<_Cp>& __x) _NOEXCEPT
1545f757f3fSDimitry Andric      : __seg_(__x.__seg_),
1555f757f3fSDimitry Andric        __mask_(__x.__mask_) {}
1560b57cec5SDimitry Andric
1575f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR operator bool() const _NOEXCEPT {
1585f757f3fSDimitry Andric    return static_cast<bool>(*__seg_ & __mask_);
1595f757f3fSDimitry Andric  }
1600b57cec5SDimitry Andric
1615f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, true> operator&() const _NOEXCEPT {
1625f757f3fSDimitry Andric    return __bit_iterator<_Cp, true>(__seg_, static_cast<unsigned>(std::__libcpp_ctz(__mask_)));
1635f757f3fSDimitry Andric  }
1645f757f3fSDimitry Andric
1650b57cec5SDimitry Andricprivate:
1665f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR explicit __bit_const_reference(
1675f757f3fSDimitry Andric      __storage_pointer __s, __storage_type __m) _NOEXCEPT
1685f757f3fSDimitry Andric      : __seg_(__s),
1695f757f3fSDimitry Andric        __mask_(__m) {}
1700b57cec5SDimitry Andric
171480093f4SDimitry Andric  __bit_const_reference& operator=(const __bit_const_reference&) = delete;
1720b57cec5SDimitry Andric};
1730b57cec5SDimitry Andric
1740b57cec5SDimitry Andric// fill_n
1750b57cec5SDimitry Andric
176*868ee3f2SDimitry Andrictemplate <bool _FillVal, class _Cp>
177bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
1785f757f3fSDimitry Andric__fill_n(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) {
1795f757f3fSDimitry Andric  using _It            = __bit_iterator<_Cp, false>;
1805f757f3fSDimitry Andric  using __storage_type = typename _It::__storage_type;
1815f757f3fSDimitry Andric
1820b57cec5SDimitry Andric  const int __bits_per_word = _It::__bits_per_word;
1830b57cec5SDimitry Andric  // do first partial word
1845f757f3fSDimitry Andric  if (__first.__ctz_ != 0) {
1850b57cec5SDimitry Andric    __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
1865f757f3fSDimitry Andric    __storage_type __dn    = std::min(__clz_f, __n);
1870b57cec5SDimitry Andric    __storage_type __m     = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
188*868ee3f2SDimitry Andric    if (_FillVal)
1890b57cec5SDimitry Andric      *__first.__seg_ |= __m;
1900b57cec5SDimitry Andric    else
1915f757f3fSDimitry Andric      *__first.__seg_ &= ~__m;
1925f757f3fSDimitry Andric    __n -= __dn;
1935f757f3fSDimitry Andric    ++__first.__seg_;
1945f757f3fSDimitry Andric  }
1955f757f3fSDimitry Andric  // do middle whole words
1965f757f3fSDimitry Andric  __storage_type __nw = __n / __bits_per_word;
197*868ee3f2SDimitry Andric  std::fill_n(std::__to_address(__first.__seg_), __nw, _FillVal ? static_cast<__storage_type>(-1) : 0);
1985f757f3fSDimitry Andric  __n -= __nw * __bits_per_word;
1995f757f3fSDimitry Andric  // do last partial word
2005f757f3fSDimitry Andric  if (__n > 0) {
2015f757f3fSDimitry Andric    __first.__seg_ += __nw;
2025f757f3fSDimitry Andric    __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
203*868ee3f2SDimitry Andric    if (_FillVal)
2045f757f3fSDimitry Andric      *__first.__seg_ |= __m;
2055f757f3fSDimitry Andric    else
2065f757f3fSDimitry Andric      *__first.__seg_ &= ~__m;
2075f757f3fSDimitry Andric  }
2085f757f3fSDimitry Andric}
2095f757f3fSDimitry Andric
2105f757f3fSDimitry Andrictemplate <class _Cp>
2115f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
2125f757f3fSDimitry Andricfill_n(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n, bool __value) {
2135f757f3fSDimitry Andric  if (__n > 0) {
2145f757f3fSDimitry Andric    if (__value)
2155f757f3fSDimitry Andric      std::__fill_n<true>(__first, __n);
2165f757f3fSDimitry Andric    else
2175f757f3fSDimitry Andric      std::__fill_n<false>(__first, __n);
2180b57cec5SDimitry Andric  }
2190b57cec5SDimitry Andric}
2200b57cec5SDimitry Andric
2210b57cec5SDimitry Andric// fill
2220b57cec5SDimitry Andric
2230b57cec5SDimitry Andrictemplate <class _Cp>
2245f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
2255f757f3fSDimitry Andricfill(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __last, bool __value) {
2265f757f3fSDimitry Andric  std::fill_n(__first, static_cast<typename _Cp::size_type>(__last - __first), __value);
2270b57cec5SDimitry Andric}
2280b57cec5SDimitry Andric
2290b57cec5SDimitry Andric// copy
2300b57cec5SDimitry Andric
2310b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
2325f757f3fSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_aligned(
2335f757f3fSDimitry Andric    __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {
2345f757f3fSDimitry Andric  using _In             = __bit_iterator<_Cp, _IsConst>;
2355f757f3fSDimitry Andric  using difference_type = typename _In::difference_type;
2365f757f3fSDimitry Andric  using __storage_type  = typename _In::__storage_type;
2375f757f3fSDimitry Andric
2380b57cec5SDimitry Andric  const int __bits_per_word = _In::__bits_per_word;
2390b57cec5SDimitry Andric  difference_type __n       = __last - __first;
2405f757f3fSDimitry Andric  if (__n > 0) {
2410b57cec5SDimitry Andric    // do first word
2425f757f3fSDimitry Andric    if (__first.__ctz_ != 0) {
2430b57cec5SDimitry Andric      unsigned __clz       = __bits_per_word - __first.__ctz_;
2445f757f3fSDimitry Andric      difference_type __dn = std::min(static_cast<difference_type>(__clz), __n);
2450b57cec5SDimitry Andric      __n -= __dn;
2460b57cec5SDimitry Andric      __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
2470b57cec5SDimitry Andric      __storage_type __b = *__first.__seg_ & __m;
2480b57cec5SDimitry Andric      *__result.__seg_ &= ~__m;
2490b57cec5SDimitry Andric      *__result.__seg_ |= __b;
2500b57cec5SDimitry Andric      __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
2510b57cec5SDimitry Andric      __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
2520b57cec5SDimitry Andric      ++__first.__seg_;
2530b57cec5SDimitry Andric      // __first.__ctz_ = 0;
2540b57cec5SDimitry Andric    }
2550b57cec5SDimitry Andric    // __first.__ctz_ == 0;
2560b57cec5SDimitry Andric    // do middle words
2570b57cec5SDimitry Andric    __storage_type __nw = __n / __bits_per_word;
25861cfbce3SDimitry Andric    std::copy_n(std::__to_address(__first.__seg_), __nw, std::__to_address(__result.__seg_));
2590b57cec5SDimitry Andric    __n -= __nw * __bits_per_word;
2600b57cec5SDimitry Andric    __result.__seg_ += __nw;
2610b57cec5SDimitry Andric    // do last word
2625f757f3fSDimitry Andric    if (__n > 0) {
2630b57cec5SDimitry Andric      __first.__seg_ += __nw;
2640b57cec5SDimitry Andric      __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
2650b57cec5SDimitry Andric      __storage_type __b = *__first.__seg_ & __m;
2660b57cec5SDimitry Andric      *__result.__seg_ &= ~__m;
2670b57cec5SDimitry Andric      *__result.__seg_ |= __b;
2680b57cec5SDimitry Andric      __result.__ctz_ = static_cast<unsigned>(__n);
2690b57cec5SDimitry Andric    }
2700b57cec5SDimitry Andric  }
2710b57cec5SDimitry Andric  return __result;
2720b57cec5SDimitry Andric}
2730b57cec5SDimitry Andric
2740b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
2755f757f3fSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_unaligned(
2765f757f3fSDimitry Andric    __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {
2775f757f3fSDimitry Andric  using _In             = __bit_iterator<_Cp, _IsConst>;
2785f757f3fSDimitry Andric  using difference_type = typename _In::difference_type;
2795f757f3fSDimitry Andric  using __storage_type  = typename _In::__storage_type;
2805f757f3fSDimitry Andric
28161cfbce3SDimitry Andric  const int __bits_per_word = _In::__bits_per_word;
2820b57cec5SDimitry Andric  difference_type __n       = __last - __first;
2835f757f3fSDimitry Andric  if (__n > 0) {
2840b57cec5SDimitry Andric    // do first word
2855f757f3fSDimitry Andric    if (__first.__ctz_ != 0) {
2860b57cec5SDimitry Andric      unsigned __clz_f     = __bits_per_word - __first.__ctz_;
2875f757f3fSDimitry Andric      difference_type __dn = std::min(static_cast<difference_type>(__clz_f), __n);
2880b57cec5SDimitry Andric      __n -= __dn;
2890b57cec5SDimitry Andric      __storage_type __m   = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
2900b57cec5SDimitry Andric      __storage_type __b   = *__first.__seg_ & __m;
2910b57cec5SDimitry Andric      unsigned __clz_r     = __bits_per_word - __result.__ctz_;
2925f757f3fSDimitry Andric      __storage_type __ddn = std::min<__storage_type>(__dn, __clz_r);
2930b57cec5SDimitry Andric      __m                  = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
2940b57cec5SDimitry Andric      *__result.__seg_ &= ~__m;
2950b57cec5SDimitry Andric      if (__result.__ctz_ > __first.__ctz_)
2960b57cec5SDimitry Andric        *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_);
2970b57cec5SDimitry Andric      else
2980b57cec5SDimitry Andric        *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_);
2990b57cec5SDimitry Andric      __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;
3000b57cec5SDimitry Andric      __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word);
3010b57cec5SDimitry Andric      __dn -= __ddn;
3025f757f3fSDimitry Andric      if (__dn > 0) {
3030b57cec5SDimitry Andric        __m = ~__storage_type(0) >> (__bits_per_word - __dn);
3040b57cec5SDimitry Andric        *__result.__seg_ &= ~__m;
3050b57cec5SDimitry Andric        *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn);
3060b57cec5SDimitry Andric        __result.__ctz_ = static_cast<unsigned>(__dn);
3070b57cec5SDimitry Andric      }
3080b57cec5SDimitry Andric      ++__first.__seg_;
3090b57cec5SDimitry Andric      // __first.__ctz_ = 0;
3100b57cec5SDimitry Andric    }
3110b57cec5SDimitry Andric    // __first.__ctz_ == 0;
3120b57cec5SDimitry Andric    // do middle words
3130b57cec5SDimitry Andric    unsigned __clz_r   = __bits_per_word - __result.__ctz_;
3140b57cec5SDimitry Andric    __storage_type __m = ~__storage_type(0) << __result.__ctz_;
3155f757f3fSDimitry Andric    for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) {
3160b57cec5SDimitry Andric      __storage_type __b = *__first.__seg_;
3170b57cec5SDimitry Andric      *__result.__seg_ &= ~__m;
3180b57cec5SDimitry Andric      *__result.__seg_ |= __b << __result.__ctz_;
3190b57cec5SDimitry Andric      ++__result.__seg_;
3200b57cec5SDimitry Andric      *__result.__seg_ &= __m;
3210b57cec5SDimitry Andric      *__result.__seg_ |= __b >> __clz_r;
3220b57cec5SDimitry Andric    }
3230b57cec5SDimitry Andric    // do last word
3245f757f3fSDimitry Andric    if (__n > 0) {
3250b57cec5SDimitry Andric      __m                 = ~__storage_type(0) >> (__bits_per_word - __n);
3260b57cec5SDimitry Andric      __storage_type __b  = *__first.__seg_ & __m;
3275f757f3fSDimitry Andric      __storage_type __dn = std::min(__n, static_cast<difference_type>(__clz_r));
3280b57cec5SDimitry Andric      __m                 = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
3290b57cec5SDimitry Andric      *__result.__seg_ &= ~__m;
3300b57cec5SDimitry Andric      *__result.__seg_ |= __b << __result.__ctz_;
3310b57cec5SDimitry Andric      __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
3320b57cec5SDimitry Andric      __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
3330b57cec5SDimitry Andric      __n -= __dn;
3345f757f3fSDimitry Andric      if (__n > 0) {
3350b57cec5SDimitry Andric        __m = ~__storage_type(0) >> (__bits_per_word - __n);
3360b57cec5SDimitry Andric        *__result.__seg_ &= ~__m;
3370b57cec5SDimitry Andric        *__result.__seg_ |= __b >> __dn;
3380b57cec5SDimitry Andric        __result.__ctz_ = static_cast<unsigned>(__n);
3390b57cec5SDimitry Andric      }
3400b57cec5SDimitry Andric    }
3410b57cec5SDimitry Andric  }
3420b57cec5SDimitry Andric  return __result;
3430b57cec5SDimitry Andric}
3440b57cec5SDimitry Andric
3450b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
3465f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, false>
3475f757f3fSDimitry Andriccopy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {
3480b57cec5SDimitry Andric  if (__first.__ctz_ == __result.__ctz_)
3495f757f3fSDimitry Andric    return std::__copy_aligned(__first, __last, __result);
3505f757f3fSDimitry Andric  return std::__copy_unaligned(__first, __last, __result);
3510b57cec5SDimitry Andric}
3520b57cec5SDimitry Andric
3530b57cec5SDimitry Andric// copy_backward
3540b57cec5SDimitry Andric
3550b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
3565f757f3fSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_backward_aligned(
3575f757f3fSDimitry Andric    __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {
3585f757f3fSDimitry Andric  using _In             = __bit_iterator<_Cp, _IsConst>;
3595f757f3fSDimitry Andric  using difference_type = typename _In::difference_type;
3605f757f3fSDimitry Andric  using __storage_type  = typename _In::__storage_type;
3615f757f3fSDimitry Andric
3620b57cec5SDimitry Andric  const int __bits_per_word = _In::__bits_per_word;
3630b57cec5SDimitry Andric  difference_type __n       = __last - __first;
3645f757f3fSDimitry Andric  if (__n > 0) {
3650b57cec5SDimitry Andric    // do first word
3665f757f3fSDimitry Andric    if (__last.__ctz_ != 0) {
3675f757f3fSDimitry Andric      difference_type __dn = std::min(static_cast<difference_type>(__last.__ctz_), __n);
3680b57cec5SDimitry Andric      __n -= __dn;
3690b57cec5SDimitry Andric      unsigned __clz     = __bits_per_word - __last.__ctz_;
3700b57cec5SDimitry Andric      __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz);
3710b57cec5SDimitry Andric      __storage_type __b = *__last.__seg_ & __m;
3720b57cec5SDimitry Andric      *__result.__seg_ &= ~__m;
3730b57cec5SDimitry Andric      *__result.__seg_ |= __b;
3745f757f3fSDimitry Andric      __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + __result.__ctz_) % __bits_per_word);
3750b57cec5SDimitry Andric      // __last.__ctz_ = 0
3760b57cec5SDimitry Andric    }
3770b57cec5SDimitry Andric    // __last.__ctz_ == 0 || __n == 0
3780b57cec5SDimitry Andric    // __result.__ctz_ == 0 || __n == 0
3790b57cec5SDimitry Andric    // do middle words
3800b57cec5SDimitry Andric    __storage_type __nw = __n / __bits_per_word;
3810b57cec5SDimitry Andric    __result.__seg_ -= __nw;
3820b57cec5SDimitry Andric    __last.__seg_ -= __nw;
38361cfbce3SDimitry Andric    std::copy_n(std::__to_address(__last.__seg_), __nw, std::__to_address(__result.__seg_));
3840b57cec5SDimitry Andric    __n -= __nw * __bits_per_word;
3850b57cec5SDimitry Andric    // do last word
3865f757f3fSDimitry Andric    if (__n > 0) {
3870b57cec5SDimitry Andric      __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n);
3880b57cec5SDimitry Andric      __storage_type __b = *--__last.__seg_ & __m;
3890b57cec5SDimitry Andric      *--__result.__seg_ &= ~__m;
3900b57cec5SDimitry Andric      *__result.__seg_ |= __b;
3910b57cec5SDimitry Andric      __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));
3920b57cec5SDimitry Andric    }
3930b57cec5SDimitry Andric  }
3940b57cec5SDimitry Andric  return __result;
3950b57cec5SDimitry Andric}
3960b57cec5SDimitry Andric
3970b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
3985f757f3fSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_backward_unaligned(
3995f757f3fSDimitry Andric    __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {
4005f757f3fSDimitry Andric  using _In             = __bit_iterator<_Cp, _IsConst>;
4015f757f3fSDimitry Andric  using difference_type = typename _In::difference_type;
4025f757f3fSDimitry Andric  using __storage_type  = typename _In::__storage_type;
4035f757f3fSDimitry Andric
4040b57cec5SDimitry Andric  const int __bits_per_word = _In::__bits_per_word;
4050b57cec5SDimitry Andric  difference_type __n       = __last - __first;
4065f757f3fSDimitry Andric  if (__n > 0) {
4070b57cec5SDimitry Andric    // do first word
4085f757f3fSDimitry Andric    if (__last.__ctz_ != 0) {
4095f757f3fSDimitry Andric      difference_type __dn = std::min(static_cast<difference_type>(__last.__ctz_), __n);
4100b57cec5SDimitry Andric      __n -= __dn;
4110b57cec5SDimitry Andric      unsigned __clz_l     = __bits_per_word - __last.__ctz_;
4120b57cec5SDimitry Andric      __storage_type __m   = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l);
4130b57cec5SDimitry Andric      __storage_type __b   = *__last.__seg_ & __m;
4140b57cec5SDimitry Andric      unsigned __clz_r     = __bits_per_word - __result.__ctz_;
4155f757f3fSDimitry Andric      __storage_type __ddn = std::min(__dn, static_cast<difference_type>(__result.__ctz_));
4165f757f3fSDimitry Andric      if (__ddn > 0) {
4170b57cec5SDimitry Andric        __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r);
4180b57cec5SDimitry Andric        *__result.__seg_ &= ~__m;
4190b57cec5SDimitry Andric        if (__result.__ctz_ > __last.__ctz_)
4200b57cec5SDimitry Andric          *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);
4210b57cec5SDimitry Andric        else
4220b57cec5SDimitry Andric          *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_);
4235f757f3fSDimitry Andric        __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) + __result.__ctz_) % __bits_per_word);
4240b57cec5SDimitry Andric        __dn -= __ddn;
4250b57cec5SDimitry Andric      }
4265f757f3fSDimitry Andric      if (__dn > 0) {
4270b57cec5SDimitry Andric        // __result.__ctz_ == 0
4280b57cec5SDimitry Andric        --__result.__seg_;
4290b57cec5SDimitry Andric        __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1));
4300b57cec5SDimitry Andric        __m             = ~__storage_type(0) << __result.__ctz_;
4310b57cec5SDimitry Andric        *__result.__seg_ &= ~__m;
4320b57cec5SDimitry Andric        __last.__ctz_ -= __dn + __ddn;
4330b57cec5SDimitry Andric        *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);
4340b57cec5SDimitry Andric      }
4350b57cec5SDimitry Andric      // __last.__ctz_ = 0
4360b57cec5SDimitry Andric    }
4370b57cec5SDimitry Andric    // __last.__ctz_ == 0 || __n == 0
4380b57cec5SDimitry Andric    // __result.__ctz_ != 0 || __n == 0
4390b57cec5SDimitry Andric    // do middle words
4400b57cec5SDimitry Andric    unsigned __clz_r   = __bits_per_word - __result.__ctz_;
4410b57cec5SDimitry Andric    __storage_type __m = ~__storage_type(0) >> __clz_r;
4425f757f3fSDimitry Andric    for (; __n >= __bits_per_word; __n -= __bits_per_word) {
4430b57cec5SDimitry Andric      __storage_type __b = *--__last.__seg_;
4440b57cec5SDimitry Andric      *__result.__seg_ &= ~__m;
4450b57cec5SDimitry Andric      *__result.__seg_ |= __b >> __clz_r;
4460b57cec5SDimitry Andric      *--__result.__seg_ &= __m;
4470b57cec5SDimitry Andric      *__result.__seg_ |= __b << __result.__ctz_;
4480b57cec5SDimitry Andric    }
4490b57cec5SDimitry Andric    // do last word
4505f757f3fSDimitry Andric    if (__n > 0) {
4510b57cec5SDimitry Andric      __m                 = ~__storage_type(0) << (__bits_per_word - __n);
4520b57cec5SDimitry Andric      __storage_type __b  = *--__last.__seg_ & __m;
4530b57cec5SDimitry Andric      __clz_r             = __bits_per_word - __result.__ctz_;
4545f757f3fSDimitry Andric      __storage_type __dn = std::min(__n, static_cast<difference_type>(__result.__ctz_));
4550b57cec5SDimitry Andric      __m                 = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r);
4560b57cec5SDimitry Andric      *__result.__seg_ &= ~__m;
4570b57cec5SDimitry Andric      *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_);
4585f757f3fSDimitry Andric      __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + __result.__ctz_) % __bits_per_word);
4590b57cec5SDimitry Andric      __n -= __dn;
4605f757f3fSDimitry Andric      if (__n > 0) {
4610b57cec5SDimitry Andric        // __result.__ctz_ == 0
4620b57cec5SDimitry Andric        --__result.__seg_;
4630b57cec5SDimitry Andric        __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));
4640b57cec5SDimitry Andric        __m             = ~__storage_type(0) << __result.__ctz_;
4650b57cec5SDimitry Andric        *__result.__seg_ &= ~__m;
4660b57cec5SDimitry Andric        *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn));
4670b57cec5SDimitry Andric      }
4680b57cec5SDimitry Andric    }
4690b57cec5SDimitry Andric  }
4700b57cec5SDimitry Andric  return __result;
4710b57cec5SDimitry Andric}
4720b57cec5SDimitry Andric
4730b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
4745f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, false> copy_backward(
4755f757f3fSDimitry Andric    __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {
4760b57cec5SDimitry Andric  if (__last.__ctz_ == __result.__ctz_)
4775f757f3fSDimitry Andric    return std::__copy_backward_aligned(__first, __last, __result);
4785f757f3fSDimitry Andric  return std::__copy_backward_unaligned(__first, __last, __result);
4790b57cec5SDimitry Andric}
4800b57cec5SDimitry Andric
4810b57cec5SDimitry Andric// move
4820b57cec5SDimitry Andric
4830b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
4845f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false>
4855f757f3fSDimitry Andricmove(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {
4865f757f3fSDimitry Andric  return std::copy(__first, __last, __result);
4870b57cec5SDimitry Andric}
4880b57cec5SDimitry Andric
4890b57cec5SDimitry Andric// move_backward
4900b57cec5SDimitry Andric
4910b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
4925f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> move_backward(
4935f757f3fSDimitry Andric    __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {
4945f757f3fSDimitry Andric  return std::copy_backward(__first, __last, __result);
4950b57cec5SDimitry Andric}
4960b57cec5SDimitry Andric
4970b57cec5SDimitry Andric// swap_ranges
4980b57cec5SDimitry Andric
49906c3fb27SDimitry Andrictemplate <class _Cl, class _Cr>
5005f757f3fSDimitry Andric_LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cr, false> __swap_ranges_aligned(
5015f757f3fSDimitry Andric    __bit_iterator<_Cl, false> __first, __bit_iterator<_Cl, false> __last, __bit_iterator<_Cr, false> __result) {
5025f757f3fSDimitry Andric  using _I1             = __bit_iterator<_Cl, false>;
5035f757f3fSDimitry Andric  using difference_type = typename _I1::difference_type;
5045f757f3fSDimitry Andric  using __storage_type  = typename _I1::__storage_type;
5055f757f3fSDimitry Andric
5060b57cec5SDimitry Andric  const int __bits_per_word = _I1::__bits_per_word;
5070b57cec5SDimitry Andric  difference_type __n       = __last - __first;
5085f757f3fSDimitry Andric  if (__n > 0) {
5090b57cec5SDimitry Andric    // do first word
5105f757f3fSDimitry Andric    if (__first.__ctz_ != 0) {
5110b57cec5SDimitry Andric      unsigned __clz       = __bits_per_word - __first.__ctz_;
5125f757f3fSDimitry Andric      difference_type __dn = std::min(static_cast<difference_type>(__clz), __n);
5130b57cec5SDimitry Andric      __n -= __dn;
5140b57cec5SDimitry Andric      __storage_type __m  = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
5150b57cec5SDimitry Andric      __storage_type __b1 = *__first.__seg_ & __m;
5160b57cec5SDimitry Andric      *__first.__seg_ &= ~__m;
5170b57cec5SDimitry Andric      __storage_type __b2 = *__result.__seg_ & __m;
5180b57cec5SDimitry Andric      *__result.__seg_ &= ~__m;
5190b57cec5SDimitry Andric      *__result.__seg_ |= __b1;
5200b57cec5SDimitry Andric      *__first.__seg_ |= __b2;
5210b57cec5SDimitry Andric      __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
5220b57cec5SDimitry Andric      __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
5230b57cec5SDimitry Andric      ++__first.__seg_;
5240b57cec5SDimitry Andric      // __first.__ctz_ = 0;
5250b57cec5SDimitry Andric    }
5260b57cec5SDimitry Andric    // __first.__ctz_ == 0;
5270b57cec5SDimitry Andric    // do middle words
5280b57cec5SDimitry Andric    for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_)
5290b57cec5SDimitry Andric      swap(*__first.__seg_, *__result.__seg_);
5300b57cec5SDimitry Andric    // do last word
5315f757f3fSDimitry Andric    if (__n > 0) {
5320b57cec5SDimitry Andric      __storage_type __m  = ~__storage_type(0) >> (__bits_per_word - __n);
5330b57cec5SDimitry Andric      __storage_type __b1 = *__first.__seg_ & __m;
5340b57cec5SDimitry Andric      *__first.__seg_ &= ~__m;
5350b57cec5SDimitry Andric      __storage_type __b2 = *__result.__seg_ & __m;
5360b57cec5SDimitry Andric      *__result.__seg_ &= ~__m;
5370b57cec5SDimitry Andric      *__result.__seg_ |= __b1;
5380b57cec5SDimitry Andric      *__first.__seg_ |= __b2;
5390b57cec5SDimitry Andric      __result.__ctz_ = static_cast<unsigned>(__n);
5400b57cec5SDimitry Andric    }
5410b57cec5SDimitry Andric  }
5420b57cec5SDimitry Andric  return __result;
5430b57cec5SDimitry Andric}
5440b57cec5SDimitry Andric
54506c3fb27SDimitry Andrictemplate <class _Cl, class _Cr>
5465f757f3fSDimitry Andric_LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cr, false> __swap_ranges_unaligned(
5475f757f3fSDimitry Andric    __bit_iterator<_Cl, false> __first, __bit_iterator<_Cl, false> __last, __bit_iterator<_Cr, false> __result) {
5485f757f3fSDimitry Andric  using _I1             = __bit_iterator<_Cl, false>;
5495f757f3fSDimitry Andric  using difference_type = typename _I1::difference_type;
5505f757f3fSDimitry Andric  using __storage_type  = typename _I1::__storage_type;
5515f757f3fSDimitry Andric
5520b57cec5SDimitry Andric  const int __bits_per_word = _I1::__bits_per_word;
5530b57cec5SDimitry Andric  difference_type __n       = __last - __first;
5545f757f3fSDimitry Andric  if (__n > 0) {
5550b57cec5SDimitry Andric    // do first word
5565f757f3fSDimitry Andric    if (__first.__ctz_ != 0) {
5570b57cec5SDimitry Andric      unsigned __clz_f     = __bits_per_word - __first.__ctz_;
5585f757f3fSDimitry Andric      difference_type __dn = std::min(static_cast<difference_type>(__clz_f), __n);
5590b57cec5SDimitry Andric      __n -= __dn;
5600b57cec5SDimitry Andric      __storage_type __m  = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
5610b57cec5SDimitry Andric      __storage_type __b1 = *__first.__seg_ & __m;
5620b57cec5SDimitry Andric      *__first.__seg_ &= ~__m;
5630b57cec5SDimitry Andric      unsigned __clz_r     = __bits_per_word - __result.__ctz_;
5645f757f3fSDimitry Andric      __storage_type __ddn = std::min<__storage_type>(__dn, __clz_r);
5650b57cec5SDimitry Andric      __m                  = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
5660b57cec5SDimitry Andric      __storage_type __b2  = *__result.__seg_ & __m;
5670b57cec5SDimitry Andric      *__result.__seg_ &= ~__m;
5685f757f3fSDimitry Andric      if (__result.__ctz_ > __first.__ctz_) {
5690b57cec5SDimitry Andric        unsigned __s = __result.__ctz_ - __first.__ctz_;
5700b57cec5SDimitry Andric        *__result.__seg_ |= __b1 << __s;
5710b57cec5SDimitry Andric        *__first.__seg_ |= __b2 >> __s;
5725f757f3fSDimitry Andric      } else {
5730b57cec5SDimitry Andric        unsigned __s = __first.__ctz_ - __result.__ctz_;
5740b57cec5SDimitry Andric        *__result.__seg_ |= __b1 >> __s;
5750b57cec5SDimitry Andric        *__first.__seg_ |= __b2 << __s;
5760b57cec5SDimitry Andric      }
5770b57cec5SDimitry Andric      __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;
5780b57cec5SDimitry Andric      __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word);
5790b57cec5SDimitry Andric      __dn -= __ddn;
5805f757f3fSDimitry Andric      if (__dn > 0) {
5810b57cec5SDimitry Andric        __m  = ~__storage_type(0) >> (__bits_per_word - __dn);
5820b57cec5SDimitry Andric        __b2 = *__result.__seg_ & __m;
5830b57cec5SDimitry Andric        *__result.__seg_ &= ~__m;
5840b57cec5SDimitry Andric        unsigned __s = __first.__ctz_ + __ddn;
5850b57cec5SDimitry Andric        *__result.__seg_ |= __b1 >> __s;
5860b57cec5SDimitry Andric        *__first.__seg_ |= __b2 << __s;
5870b57cec5SDimitry Andric        __result.__ctz_ = static_cast<unsigned>(__dn);
5880b57cec5SDimitry Andric      }
5890b57cec5SDimitry Andric      ++__first.__seg_;
5900b57cec5SDimitry Andric      // __first.__ctz_ = 0;
5910b57cec5SDimitry Andric    }
5920b57cec5SDimitry Andric    // __first.__ctz_ == 0;
5930b57cec5SDimitry Andric    // do middle words
5940b57cec5SDimitry Andric    __storage_type __m = ~__storage_type(0) << __result.__ctz_;
5950b57cec5SDimitry Andric    unsigned __clz_r   = __bits_per_word - __result.__ctz_;
5965f757f3fSDimitry Andric    for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) {
5970b57cec5SDimitry Andric      __storage_type __b1 = *__first.__seg_;
5980b57cec5SDimitry Andric      __storage_type __b2 = *__result.__seg_ & __m;
5990b57cec5SDimitry Andric      *__result.__seg_ &= ~__m;
6000b57cec5SDimitry Andric      *__result.__seg_ |= __b1 << __result.__ctz_;
6010b57cec5SDimitry Andric      *__first.__seg_ = __b2 >> __result.__ctz_;
6020b57cec5SDimitry Andric      ++__result.__seg_;
6030b57cec5SDimitry Andric      __b2 = *__result.__seg_ & ~__m;
6040b57cec5SDimitry Andric      *__result.__seg_ &= __m;
6050b57cec5SDimitry Andric      *__result.__seg_ |= __b1 >> __clz_r;
6060b57cec5SDimitry Andric      *__first.__seg_ |= __b2 << __clz_r;
6070b57cec5SDimitry Andric    }
6080b57cec5SDimitry Andric    // do last word
6095f757f3fSDimitry Andric    if (__n > 0) {
6100b57cec5SDimitry Andric      __m                 = ~__storage_type(0) >> (__bits_per_word - __n);
6110b57cec5SDimitry Andric      __storage_type __b1 = *__first.__seg_ & __m;
6120b57cec5SDimitry Andric      *__first.__seg_ &= ~__m;
6135f757f3fSDimitry Andric      __storage_type __dn = std::min<__storage_type>(__n, __clz_r);
6140b57cec5SDimitry Andric      __m                 = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
6150b57cec5SDimitry Andric      __storage_type __b2 = *__result.__seg_ & __m;
6160b57cec5SDimitry Andric      *__result.__seg_ &= ~__m;
6170b57cec5SDimitry Andric      *__result.__seg_ |= __b1 << __result.__ctz_;
6180b57cec5SDimitry Andric      *__first.__seg_ |= __b2 >> __result.__ctz_;
6190b57cec5SDimitry Andric      __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
6200b57cec5SDimitry Andric      __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
6210b57cec5SDimitry Andric      __n -= __dn;
6225f757f3fSDimitry Andric      if (__n > 0) {
6230b57cec5SDimitry Andric        __m  = ~__storage_type(0) >> (__bits_per_word - __n);
6240b57cec5SDimitry Andric        __b2 = *__result.__seg_ & __m;
6250b57cec5SDimitry Andric        *__result.__seg_ &= ~__m;
6260b57cec5SDimitry Andric        *__result.__seg_ |= __b1 >> __dn;
6270b57cec5SDimitry Andric        *__first.__seg_ |= __b2 << __dn;
6280b57cec5SDimitry Andric        __result.__ctz_ = static_cast<unsigned>(__n);
6290b57cec5SDimitry Andric      }
6300b57cec5SDimitry Andric    }
6310b57cec5SDimitry Andric  }
6320b57cec5SDimitry Andric  return __result;
6330b57cec5SDimitry Andric}
6340b57cec5SDimitry Andric
63506c3fb27SDimitry Andrictemplate <class _Cl, class _Cr>
6365f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cr, false> swap_ranges(
6375f757f3fSDimitry Andric    __bit_iterator<_Cl, false> __first1, __bit_iterator<_Cl, false> __last1, __bit_iterator<_Cr, false> __first2) {
6380b57cec5SDimitry Andric  if (__first1.__ctz_ == __first2.__ctz_)
6395f757f3fSDimitry Andric    return std::__swap_ranges_aligned(__first1, __last1, __first2);
6405f757f3fSDimitry Andric  return std::__swap_ranges_unaligned(__first1, __last1, __first2);
6410b57cec5SDimitry Andric}
6420b57cec5SDimitry Andric
6430b57cec5SDimitry Andric// rotate
6440b57cec5SDimitry Andric
6450b57cec5SDimitry Andrictemplate <class _Cp>
6465f757f3fSDimitry Andricstruct __bit_array {
6475f757f3fSDimitry Andric  using difference_type   = typename _Cp::difference_type;
6485f757f3fSDimitry Andric  using __storage_type    = typename _Cp::__storage_type;
6495f757f3fSDimitry Andric  using __storage_pointer = typename _Cp::__storage_pointer;
6505f757f3fSDimitry Andric  using iterator          = typename _Cp::iterator;
6515f757f3fSDimitry Andric
6520b57cec5SDimitry Andric  static const unsigned __bits_per_word = _Cp::__bits_per_word;
6530b57cec5SDimitry Andric  static const unsigned _Np             = 4;
6540b57cec5SDimitry Andric
6550b57cec5SDimitry Andric  difference_type __size_;
6560b57cec5SDimitry Andric  __storage_type __word_[_Np];
6570b57cec5SDimitry Andric
6585f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static difference_type capacity() {
6595f757f3fSDimitry Andric    return static_cast<difference_type>(_Np * __bits_per_word);
6605f757f3fSDimitry Andric  }
6615f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit __bit_array(difference_type __s) : __size_(__s) {
66261cfbce3SDimitry Andric    if (__libcpp_is_constant_evaluated()) {
66361cfbce3SDimitry Andric      for (size_t __i = 0; __i != __bit_array<_Cp>::_Np; ++__i)
66461cfbce3SDimitry Andric        std::__construct_at(__word_ + __i, 0);
66561cfbce3SDimitry Andric    }
66661cfbce3SDimitry Andric  }
6675f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator begin() {
6680b57cec5SDimitry Andric    return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]), 0);
6690b57cec5SDimitry Andric  }
6705f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator end() {
6710b57cec5SDimitry Andric    return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]) + __size_ / __bits_per_word,
6720b57cec5SDimitry Andric                    static_cast<unsigned>(__size_ % __bits_per_word));
6730b57cec5SDimitry Andric  }
6740b57cec5SDimitry Andric};
6750b57cec5SDimitry Andric
6760b57cec5SDimitry Andrictemplate <class _Cp>
677bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false>
6785f757f3fSDimitry Andricrotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last) {
6795f757f3fSDimitry Andric  using _I1             = __bit_iterator<_Cp, false>;
6805f757f3fSDimitry Andric  using difference_type = typename _I1::difference_type;
6815f757f3fSDimitry Andric
6820b57cec5SDimitry Andric  difference_type __d1 = __middle - __first;
6830b57cec5SDimitry Andric  difference_type __d2 = __last - __middle;
6840b57cec5SDimitry Andric  _I1 __r              = __first + __d2;
6855f757f3fSDimitry Andric  while (__d1 != 0 && __d2 != 0) {
6865f757f3fSDimitry Andric    if (__d1 <= __d2) {
6875f757f3fSDimitry Andric      if (__d1 <= __bit_array<_Cp>::capacity()) {
6880b57cec5SDimitry Andric        __bit_array<_Cp> __b(__d1);
6895f757f3fSDimitry Andric        std::copy(__first, __middle, __b.begin());
6905f757f3fSDimitry Andric        std::copy(__b.begin(), __b.end(), std::copy(__middle, __last, __first));
6910b57cec5SDimitry Andric        break;
6925f757f3fSDimitry Andric      } else {
6935f757f3fSDimitry Andric        __bit_iterator<_Cp, false> __mp = std::swap_ranges(__first, __middle, __middle);
6940b57cec5SDimitry Andric        __first                         = __middle;
6950b57cec5SDimitry Andric        __middle                        = __mp;
6960b57cec5SDimitry Andric        __d2 -= __d1;
6970b57cec5SDimitry Andric      }
6985f757f3fSDimitry Andric    } else {
6995f757f3fSDimitry Andric      if (__d2 <= __bit_array<_Cp>::capacity()) {
7000b57cec5SDimitry Andric        __bit_array<_Cp> __b(__d2);
7015f757f3fSDimitry Andric        std::copy(__middle, __last, __b.begin());
7025f757f3fSDimitry Andric        std::copy_backward(__b.begin(), __b.end(), std::copy_backward(__first, __middle, __last));
7030b57cec5SDimitry Andric        break;
7045f757f3fSDimitry Andric      } else {
7050b57cec5SDimitry Andric        __bit_iterator<_Cp, false> __mp = __first + __d2;
7065f757f3fSDimitry Andric        std::swap_ranges(__first, __mp, __middle);
7070b57cec5SDimitry Andric        __first = __mp;
7080b57cec5SDimitry Andric        __d1 -= __d2;
7090b57cec5SDimitry Andric      }
7100b57cec5SDimitry Andric    }
7110b57cec5SDimitry Andric  }
7120b57cec5SDimitry Andric  return __r;
7130b57cec5SDimitry Andric}
7140b57cec5SDimitry Andric
7150b57cec5SDimitry Andric// equal
7160b57cec5SDimitry Andric
7170b57cec5SDimitry Andrictemplate <class _Cp, bool _IC1, bool _IC2>
7185f757f3fSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool __equal_unaligned(
7195f757f3fSDimitry Andric    __bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) {
7205f757f3fSDimitry Andric  using _It             = __bit_iterator<_Cp, _IC1>;
7215f757f3fSDimitry Andric  using difference_type = typename _It::difference_type;
7225f757f3fSDimitry Andric  using __storage_type  = typename _It::__storage_type;
7235f757f3fSDimitry Andric
72461cfbce3SDimitry Andric  const int __bits_per_word = _It::__bits_per_word;
7250b57cec5SDimitry Andric  difference_type __n       = __last1 - __first1;
7265f757f3fSDimitry Andric  if (__n > 0) {
7270b57cec5SDimitry Andric    // do first word
7285f757f3fSDimitry Andric    if (__first1.__ctz_ != 0) {
7290b57cec5SDimitry Andric      unsigned __clz_f     = __bits_per_word - __first1.__ctz_;
7305f757f3fSDimitry Andric      difference_type __dn = std::min(static_cast<difference_type>(__clz_f), __n);
7310b57cec5SDimitry Andric      __n -= __dn;
7320b57cec5SDimitry Andric      __storage_type __m   = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
7330b57cec5SDimitry Andric      __storage_type __b   = *__first1.__seg_ & __m;
7340b57cec5SDimitry Andric      unsigned __clz_r     = __bits_per_word - __first2.__ctz_;
7355f757f3fSDimitry Andric      __storage_type __ddn = std::min<__storage_type>(__dn, __clz_r);
7360b57cec5SDimitry Andric      __m                  = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
7375f757f3fSDimitry Andric      if (__first2.__ctz_ > __first1.__ctz_) {
7380b57cec5SDimitry Andric        if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_)))
7390b57cec5SDimitry Andric          return false;
7405f757f3fSDimitry Andric      } else {
7410b57cec5SDimitry Andric        if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_)))
7420b57cec5SDimitry Andric          return false;
7430b57cec5SDimitry Andric      }
7440b57cec5SDimitry Andric      __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word;
7450b57cec5SDimitry Andric      __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word);
7460b57cec5SDimitry Andric      __dn -= __ddn;
7475f757f3fSDimitry Andric      if (__dn > 0) {
7480b57cec5SDimitry Andric        __m = ~__storage_type(0) >> (__bits_per_word - __dn);
7490b57cec5SDimitry Andric        if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn)))
7500b57cec5SDimitry Andric          return false;
7510b57cec5SDimitry Andric        __first2.__ctz_ = static_cast<unsigned>(__dn);
7520b57cec5SDimitry Andric      }
7530b57cec5SDimitry Andric      ++__first1.__seg_;
7540b57cec5SDimitry Andric      // __first1.__ctz_ = 0;
7550b57cec5SDimitry Andric    }
7560b57cec5SDimitry Andric    // __first1.__ctz_ == 0;
7570b57cec5SDimitry Andric    // do middle words
7580b57cec5SDimitry Andric    unsigned __clz_r   = __bits_per_word - __first2.__ctz_;
7590b57cec5SDimitry Andric    __storage_type __m = ~__storage_type(0) << __first2.__ctz_;
7605f757f3fSDimitry Andric    for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_) {
7610b57cec5SDimitry Andric      __storage_type __b = *__first1.__seg_;
7620b57cec5SDimitry Andric      if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_))
7630b57cec5SDimitry Andric        return false;
7640b57cec5SDimitry Andric      ++__first2.__seg_;
7650b57cec5SDimitry Andric      if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r))
7660b57cec5SDimitry Andric        return false;
7670b57cec5SDimitry Andric    }
7680b57cec5SDimitry Andric    // do last word
7695f757f3fSDimitry Andric    if (__n > 0) {
7700b57cec5SDimitry Andric      __m                 = ~__storage_type(0) >> (__bits_per_word - __n);
7710b57cec5SDimitry Andric      __storage_type __b  = *__first1.__seg_ & __m;
7725f757f3fSDimitry Andric      __storage_type __dn = std::min(__n, static_cast<difference_type>(__clz_r));
7730b57cec5SDimitry Andric      __m                 = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
7740b57cec5SDimitry Andric      if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_))
7750b57cec5SDimitry Andric        return false;
7760b57cec5SDimitry Andric      __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word;
7770b57cec5SDimitry Andric      __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word);
7780b57cec5SDimitry Andric      __n -= __dn;
7795f757f3fSDimitry Andric      if (__n > 0) {
7800b57cec5SDimitry Andric        __m = ~__storage_type(0) >> (__bits_per_word - __n);
7810b57cec5SDimitry Andric        if ((*__first2.__seg_ & __m) != (__b >> __dn))
7820b57cec5SDimitry Andric          return false;
7830b57cec5SDimitry Andric      }
7840b57cec5SDimitry Andric    }
7850b57cec5SDimitry Andric  }
7860b57cec5SDimitry Andric  return true;
7870b57cec5SDimitry Andric}
7880b57cec5SDimitry Andric
7890b57cec5SDimitry Andrictemplate <class _Cp, bool _IC1, bool _IC2>
7905f757f3fSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool __equal_aligned(
7915f757f3fSDimitry Andric    __bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) {
7925f757f3fSDimitry Andric  using _It             = __bit_iterator<_Cp, _IC1>;
7935f757f3fSDimitry Andric  using difference_type = typename _It::difference_type;
7945f757f3fSDimitry Andric  using __storage_type  = typename _It::__storage_type;
7955f757f3fSDimitry Andric
79661cfbce3SDimitry Andric  const int __bits_per_word = _It::__bits_per_word;
7970b57cec5SDimitry Andric  difference_type __n       = __last1 - __first1;
7985f757f3fSDimitry Andric  if (__n > 0) {
7990b57cec5SDimitry Andric    // do first word
8005f757f3fSDimitry Andric    if (__first1.__ctz_ != 0) {
8010b57cec5SDimitry Andric      unsigned __clz       = __bits_per_word - __first1.__ctz_;
8025f757f3fSDimitry Andric      difference_type __dn = std::min(static_cast<difference_type>(__clz), __n);
8030b57cec5SDimitry Andric      __n -= __dn;
8040b57cec5SDimitry Andric      __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
8050b57cec5SDimitry Andric      if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))
8060b57cec5SDimitry Andric        return false;
8070b57cec5SDimitry Andric      ++__first2.__seg_;
8080b57cec5SDimitry Andric      ++__first1.__seg_;
8090b57cec5SDimitry Andric      // __first1.__ctz_ = 0;
8100b57cec5SDimitry Andric      // __first2.__ctz_ = 0;
8110b57cec5SDimitry Andric    }
8120b57cec5SDimitry Andric    // __first1.__ctz_ == 0;
8130b57cec5SDimitry Andric    // __first2.__ctz_ == 0;
8140b57cec5SDimitry Andric    // do middle words
8150b57cec5SDimitry Andric    for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_)
8160b57cec5SDimitry Andric      if (*__first2.__seg_ != *__first1.__seg_)
8170b57cec5SDimitry Andric        return false;
8180b57cec5SDimitry Andric    // do last word
8195f757f3fSDimitry Andric    if (__n > 0) {
8200b57cec5SDimitry Andric      __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
8210b57cec5SDimitry Andric      if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))
8220b57cec5SDimitry Andric        return false;
8230b57cec5SDimitry Andric    }
8240b57cec5SDimitry Andric  }
8250b57cec5SDimitry Andric  return true;
8260b57cec5SDimitry Andric}
8270b57cec5SDimitry Andric
8280b57cec5SDimitry Andrictemplate <class _Cp, bool _IC1, bool _IC2>
8295f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool
8305f757f3fSDimitry Andricequal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) {
8310b57cec5SDimitry Andric  if (__first1.__ctz_ == __first2.__ctz_)
8325f757f3fSDimitry Andric    return std::__equal_aligned(__first1, __last1, __first2);
8335f757f3fSDimitry Andric  return std::__equal_unaligned(__first1, __last1, __first2);
8340b57cec5SDimitry Andric}
8350b57cec5SDimitry Andric
8365f757f3fSDimitry Andrictemplate <class _Cp, bool _IsConst, typename _Cp::__storage_type>
8375f757f3fSDimitry Andricclass __bit_iterator {
8380b57cec5SDimitry Andricpublic:
8395f757f3fSDimitry Andric  using difference_type = typename _Cp::difference_type;
8405f757f3fSDimitry Andric  using value_type      = bool;
8415f757f3fSDimitry Andric  using pointer         = __bit_iterator;
84281ad6265SDimitry Andric#ifndef _LIBCPP_ABI_BITSET_VECTOR_BOOL_CONST_SUBSCRIPT_RETURN_BOOL
8435f757f3fSDimitry Andric  using reference = __conditional_t<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >;
84481ad6265SDimitry Andric#else
845bdd1243dSDimitry Andric  using reference = __conditional_t<_IsConst, bool, __bit_reference<_Cp> >;
84681ad6265SDimitry Andric#endif
8475f757f3fSDimitry Andric  using iterator_category = random_access_iterator_tag;
8480b57cec5SDimitry Andric
8490b57cec5SDimitry Andricprivate:
8505f757f3fSDimitry Andric  using __storage_type = typename _Cp::__storage_type;
8515f757f3fSDimitry Andric  using __storage_pointer =
8525f757f3fSDimitry Andric      __conditional_t<_IsConst, typename _Cp::__const_storage_pointer, typename _Cp::__storage_pointer>;
8535f757f3fSDimitry Andric
8540b57cec5SDimitry Andric  static const unsigned __bits_per_word = _Cp::__bits_per_word;
8550b57cec5SDimitry Andric
8560b57cec5SDimitry Andric  __storage_pointer __seg_;
8570b57cec5SDimitry Andric  unsigned __ctz_;
8580b57cec5SDimitry Andric
8590b57cec5SDimitry Andricpublic:
8605f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator() _NOEXCEPT
86106c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14
8625f757f3fSDimitry Andric      : __seg_(nullptr),
8635f757f3fSDimitry Andric        __ctz_(0)
8640b57cec5SDimitry Andric#endif
8655f757f3fSDimitry Andric  {
8665f757f3fSDimitry Andric  }
8670b57cec5SDimitry Andric
8684652422eSDimitry Andric  // When _IsConst=false, this is the copy constructor.
8694652422eSDimitry Andric  // It is non-trivial. Making it trivial would break ABI.
8704652422eSDimitry Andric  // When _IsConst=true, this is a converting constructor;
8714652422eSDimitry Andric  // the copy and move constructors are implicitly generated
8724652422eSDimitry Andric  // and trivial.
8735f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT
8745f757f3fSDimitry Andric      : __seg_(__it.__seg_),
8755f757f3fSDimitry Andric        __ctz_(__it.__ctz_) {}
8760b57cec5SDimitry Andric
8774652422eSDimitry Andric  // When _IsConst=false, we have a user-provided copy constructor,
8784652422eSDimitry Andric  // so we must also provide a copy assignment operator because
8794652422eSDimitry Andric  // the implicit generation of a defaulted one is deprecated.
8804652422eSDimitry Andric  // When _IsConst=true, the assignment operators are
8814652422eSDimitry Andric  // implicitly generated and trivial.
8825f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator&
8835f757f3fSDimitry Andric  operator=(const _If<_IsConst, struct __private_nat, __bit_iterator>& __it) {
8844652422eSDimitry Andric    __seg_ = __it.__seg_;
8854652422eSDimitry Andric    __ctz_ = __it.__ctz_;
8864652422eSDimitry Andric    return *this;
8874652422eSDimitry Andric  }
88847395794SDimitry Andric
8895f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference operator*() const _NOEXCEPT {
890bdd1243dSDimitry Andric    return __conditional_t<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >(
891bdd1243dSDimitry Andric        __seg_, __storage_type(1) << __ctz_);
89281ad6265SDimitry Andric  }
8930b57cec5SDimitry Andric
8945f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator++() {
8950b57cec5SDimitry Andric    if (__ctz_ != __bits_per_word - 1)
8960b57cec5SDimitry Andric      ++__ctz_;
8975f757f3fSDimitry Andric    else {
8980b57cec5SDimitry Andric      __ctz_ = 0;
8990b57cec5SDimitry Andric      ++__seg_;
9000b57cec5SDimitry Andric    }
9010b57cec5SDimitry Andric    return *this;
9020b57cec5SDimitry Andric  }
9030b57cec5SDimitry Andric
9045f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator++(int) {
9050b57cec5SDimitry Andric    __bit_iterator __tmp = *this;
9060b57cec5SDimitry Andric    ++(*this);
9070b57cec5SDimitry Andric    return __tmp;
9080b57cec5SDimitry Andric  }
9090b57cec5SDimitry Andric
9105f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator--() {
9110b57cec5SDimitry Andric    if (__ctz_ != 0)
9120b57cec5SDimitry Andric      --__ctz_;
9135f757f3fSDimitry Andric    else {
9140b57cec5SDimitry Andric      __ctz_ = __bits_per_word - 1;
9150b57cec5SDimitry Andric      --__seg_;
9160b57cec5SDimitry Andric    }
9170b57cec5SDimitry Andric    return *this;
9180b57cec5SDimitry Andric  }
9190b57cec5SDimitry Andric
9205f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator--(int) {
9210b57cec5SDimitry Andric    __bit_iterator __tmp = *this;
9220b57cec5SDimitry Andric    --(*this);
9230b57cec5SDimitry Andric    return __tmp;
9240b57cec5SDimitry Andric  }
9250b57cec5SDimitry Andric
9265f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator+=(difference_type __n) {
9270b57cec5SDimitry Andric    if (__n >= 0)
9280b57cec5SDimitry Andric      __seg_ += (__n + __ctz_) / __bits_per_word;
9290b57cec5SDimitry Andric    else
9305f757f3fSDimitry Andric      __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1) /
9315f757f3fSDimitry Andric                static_cast<difference_type>(__bits_per_word);
9320b57cec5SDimitry Andric    __n &= (__bits_per_word - 1);
9330b57cec5SDimitry Andric    __ctz_ = static_cast<unsigned>((__n + __ctz_) % __bits_per_word);
9340b57cec5SDimitry Andric    return *this;
9350b57cec5SDimitry Andric  }
9360b57cec5SDimitry Andric
9375f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator-=(difference_type __n) {
9380b57cec5SDimitry Andric    return *this += -__n;
9390b57cec5SDimitry Andric  }
9400b57cec5SDimitry Andric
9415f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator+(difference_type __n) const {
9420b57cec5SDimitry Andric    __bit_iterator __t(*this);
9430b57cec5SDimitry Andric    __t += __n;
9440b57cec5SDimitry Andric    return __t;
9450b57cec5SDimitry Andric  }
9460b57cec5SDimitry Andric
9475f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator-(difference_type __n) const {
9480b57cec5SDimitry Andric    __bit_iterator __t(*this);
9490b57cec5SDimitry Andric    __t -= __n;
9500b57cec5SDimitry Andric    return __t;
9510b57cec5SDimitry Andric  }
9520b57cec5SDimitry Andric
9535f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator
9545f757f3fSDimitry Andric  operator+(difference_type __n, const __bit_iterator& __it) {
9555f757f3fSDimitry Andric    return __it + __n;
9565f757f3fSDimitry Andric  }
9570b57cec5SDimitry Andric
9585f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend difference_type
9595f757f3fSDimitry Andric  operator-(const __bit_iterator& __x, const __bit_iterator& __y) {
9605f757f3fSDimitry Andric    return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;
9615f757f3fSDimitry Andric  }
9620b57cec5SDimitry Andric
9635f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference operator[](difference_type __n) const {
9645f757f3fSDimitry Andric    return *(*this + __n);
9655f757f3fSDimitry Andric  }
9660b57cec5SDimitry Andric
9675f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
9685f757f3fSDimitry Andric  operator==(const __bit_iterator& __x, const __bit_iterator& __y) {
9695f757f3fSDimitry Andric    return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;
9705f757f3fSDimitry Andric  }
9710b57cec5SDimitry Andric
9725f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
9735f757f3fSDimitry Andric  operator!=(const __bit_iterator& __x, const __bit_iterator& __y) {
9745f757f3fSDimitry Andric    return !(__x == __y);
9755f757f3fSDimitry Andric  }
9760b57cec5SDimitry Andric
9775f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
9785f757f3fSDimitry Andric  operator<(const __bit_iterator& __x, const __bit_iterator& __y) {
9795f757f3fSDimitry Andric    return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);
9805f757f3fSDimitry Andric  }
9810b57cec5SDimitry Andric
9825f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
9835f757f3fSDimitry Andric  operator>(const __bit_iterator& __x, const __bit_iterator& __y) {
9845f757f3fSDimitry Andric    return __y < __x;
9855f757f3fSDimitry Andric  }
9860b57cec5SDimitry Andric
9875f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
9885f757f3fSDimitry Andric  operator<=(const __bit_iterator& __x, const __bit_iterator& __y) {
9895f757f3fSDimitry Andric    return !(__y < __x);
9905f757f3fSDimitry Andric  }
9910b57cec5SDimitry Andric
9925f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
9935f757f3fSDimitry Andric  operator>=(const __bit_iterator& __x, const __bit_iterator& __y) {
9945f757f3fSDimitry Andric    return !(__x < __y);
9955f757f3fSDimitry Andric  }
9960b57cec5SDimitry Andric
9970b57cec5SDimitry Andricprivate:
9985f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit __bit_iterator(
9995f757f3fSDimitry Andric      __storage_pointer __s, unsigned __ctz) _NOEXCEPT
10005f757f3fSDimitry Andric      : __seg_(__s),
10015f757f3fSDimitry Andric        __ctz_(__ctz) {}
10020b57cec5SDimitry Andric
10030b57cec5SDimitry Andric  friend typename _Cp::__self;
10040b57cec5SDimitry Andric
10050b57cec5SDimitry Andric  friend class __bit_reference<_Cp>;
10060b57cec5SDimitry Andric  friend class __bit_const_reference<_Cp>;
10070b57cec5SDimitry Andric  friend class __bit_iterator<_Cp, true>;
100861cfbce3SDimitry Andric  template <class _Dp>
10095f757f3fSDimitry Andric  friend struct __bit_array;
1010*868ee3f2SDimitry Andric  template <bool _FillVal, class _Dp>
10115f757f3fSDimitry Andric  _LIBCPP_CONSTEXPR_SINCE_CXX20 friend void __fill_n(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n);
101261cfbce3SDimitry Andric
101361cfbce3SDimitry Andric  template <class _Dp, bool _IC>
10145f757f3fSDimitry Andric  _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> __copy_aligned(
10155f757f3fSDimitry Andric      __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result);
101661cfbce3SDimitry Andric  template <class _Dp, bool _IC>
10175f757f3fSDimitry Andric  _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> __copy_unaligned(
10185f757f3fSDimitry Andric      __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result);
101961cfbce3SDimitry Andric  template <class _Dp, bool _IC>
10205f757f3fSDimitry Andric  _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false>
10215f757f3fSDimitry Andric  copy(__bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result);
102261cfbce3SDimitry Andric  template <class _Dp, bool _IC>
10235f757f3fSDimitry Andric  _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> __copy_backward_aligned(
10245f757f3fSDimitry Andric      __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result);
102561cfbce3SDimitry Andric  template <class _Dp, bool _IC>
10265f757f3fSDimitry Andric  _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> __copy_backward_unaligned(
10275f757f3fSDimitry Andric      __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result);
102861cfbce3SDimitry Andric  template <class _Dp, bool _IC>
10295f757f3fSDimitry Andric  _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false>
10305f757f3fSDimitry Andric  copy_backward(__bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result);
10315f757f3fSDimitry Andric  template <class _Cl, class _Cr>
10325f757f3fSDimitry Andric  friend __bit_iterator<_Cr, false>
10335f757f3fSDimitry Andric      __swap_ranges_aligned(__bit_iterator<_Cl, false>, __bit_iterator<_Cl, false>, __bit_iterator<_Cr, false>);
10345f757f3fSDimitry Andric  template <class _Cl, class _Cr>
10355f757f3fSDimitry Andric  friend __bit_iterator<_Cr, false>
10365f757f3fSDimitry Andric      __swap_ranges_unaligned(__bit_iterator<_Cl, false>, __bit_iterator<_Cl, false>, __bit_iterator<_Cr, false>);
10375f757f3fSDimitry Andric  template <class _Cl, class _Cr>
10385f757f3fSDimitry Andric  friend __bit_iterator<_Cr, false>
10395f757f3fSDimitry Andric      swap_ranges(__bit_iterator<_Cl, false>, __bit_iterator<_Cl, false>, __bit_iterator<_Cr, false>);
104061cfbce3SDimitry Andric  template <class _Dp>
10415f757f3fSDimitry Andric  _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false>
10425f757f3fSDimitry Andric      rotate(__bit_iterator<_Dp, false>, __bit_iterator<_Dp, false>, __bit_iterator<_Dp, false>);
104361cfbce3SDimitry Andric  template <class _Dp, bool _IC1, bool _IC2>
10445f757f3fSDimitry Andric  _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
10455f757f3fSDimitry Andric      __equal_aligned(__bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC2>);
104661cfbce3SDimitry Andric  template <class _Dp, bool _IC1, bool _IC2>
10475f757f3fSDimitry Andric  _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
10485f757f3fSDimitry Andric      __equal_unaligned(__bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC2>);
104961cfbce3SDimitry Andric  template <class _Dp, bool _IC1, bool _IC2>
10505f757f3fSDimitry Andric  _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
10515f757f3fSDimitry Andric      equal(__bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC2>);
10525f757f3fSDimitry Andric  template <bool _ToFind, class _Dp, bool _IC>
10535f757f3fSDimitry Andric  _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, _IC>
10545f757f3fSDimitry Andric      __find_bool(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
10555f757f3fSDimitry Andric  template <bool _ToCount, class _Dp, bool _IC>
10565f757f3fSDimitry Andric  friend typename __bit_iterator<_Dp, _IC>::difference_type _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
10575f757f3fSDimitry Andric      __count_bool(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
10580b57cec5SDimitry Andric};
10590b57cec5SDimitry Andric
10600b57cec5SDimitry Andric_LIBCPP_END_NAMESPACE_STD
10610b57cec5SDimitry Andric
10620b57cec5SDimitry Andric_LIBCPP_POP_MACROS
10630b57cec5SDimitry Andric
10640b57cec5SDimitry Andric#endif // _LIBCPP___BIT_REFERENCE
1065