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: 98*0fca6ea1SDimitry Andric _LIBCPP_HIDE_FROM_ABI 99*0fca6ea1SDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit __bit_reference(__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; 152*0fca6ea1SDimitry Andric __bit_const_reference& operator=(const __bit_const_reference&) = delete; 153480093f4SDimitry Andric 1545f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_const_reference(const __bit_reference<_Cp>& __x) _NOEXCEPT 1555f757f3fSDimitry Andric : __seg_(__x.__seg_), 1565f757f3fSDimitry Andric __mask_(__x.__mask_) {} 1570b57cec5SDimitry Andric 1585f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR operator bool() const _NOEXCEPT { 1595f757f3fSDimitry Andric return static_cast<bool>(*__seg_ & __mask_); 1605f757f3fSDimitry Andric } 1610b57cec5SDimitry Andric 1625f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, true> operator&() const _NOEXCEPT { 1635f757f3fSDimitry Andric return __bit_iterator<_Cp, true>(__seg_, static_cast<unsigned>(std::__libcpp_ctz(__mask_))); 1645f757f3fSDimitry Andric } 1655f757f3fSDimitry Andric 1660b57cec5SDimitry Andricprivate: 167*0fca6ea1SDimitry Andric _LIBCPP_HIDE_FROM_ABI 168*0fca6ea1SDimitry Andric _LIBCPP_CONSTEXPR explicit __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT 1695f757f3fSDimitry Andric : __seg_(__s), 1705f757f3fSDimitry Andric __mask_(__m) {} 1710b57cec5SDimitry Andric}; 1720b57cec5SDimitry Andric 1730b57cec5SDimitry Andric// copy 1740b57cec5SDimitry Andric 1750b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 1765f757f3fSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_aligned( 1775f757f3fSDimitry Andric __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) { 1785f757f3fSDimitry Andric using _In = __bit_iterator<_Cp, _IsConst>; 1795f757f3fSDimitry Andric using difference_type = typename _In::difference_type; 1805f757f3fSDimitry Andric using __storage_type = typename _In::__storage_type; 1815f757f3fSDimitry Andric 1820b57cec5SDimitry Andric const int __bits_per_word = _In::__bits_per_word; 1830b57cec5SDimitry Andric difference_type __n = __last - __first; 1845f757f3fSDimitry Andric if (__n > 0) { 1850b57cec5SDimitry Andric // do first word 1865f757f3fSDimitry Andric if (__first.__ctz_ != 0) { 1870b57cec5SDimitry Andric unsigned __clz = __bits_per_word - __first.__ctz_; 1885f757f3fSDimitry Andric difference_type __dn = std::min(static_cast<difference_type>(__clz), __n); 1890b57cec5SDimitry Andric __n -= __dn; 1900b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 1910b57cec5SDimitry Andric __storage_type __b = *__first.__seg_ & __m; 1920b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 1930b57cec5SDimitry Andric *__result.__seg_ |= __b; 1940b57cec5SDimitry Andric __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 1950b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 1960b57cec5SDimitry Andric ++__first.__seg_; 1970b57cec5SDimitry Andric // __first.__ctz_ = 0; 1980b57cec5SDimitry Andric } 1990b57cec5SDimitry Andric // __first.__ctz_ == 0; 2000b57cec5SDimitry Andric // do middle words 2010b57cec5SDimitry Andric __storage_type __nw = __n / __bits_per_word; 20261cfbce3SDimitry Andric std::copy_n(std::__to_address(__first.__seg_), __nw, std::__to_address(__result.__seg_)); 2030b57cec5SDimitry Andric __n -= __nw * __bits_per_word; 2040b57cec5SDimitry Andric __result.__seg_ += __nw; 2050b57cec5SDimitry Andric // do last word 2065f757f3fSDimitry Andric if (__n > 0) { 2070b57cec5SDimitry Andric __first.__seg_ += __nw; 2080b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 2090b57cec5SDimitry Andric __storage_type __b = *__first.__seg_ & __m; 2100b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 2110b57cec5SDimitry Andric *__result.__seg_ |= __b; 2120b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(__n); 2130b57cec5SDimitry Andric } 2140b57cec5SDimitry Andric } 2150b57cec5SDimitry Andric return __result; 2160b57cec5SDimitry Andric} 2170b57cec5SDimitry Andric 2180b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 2195f757f3fSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_unaligned( 2205f757f3fSDimitry Andric __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) { 2215f757f3fSDimitry Andric using _In = __bit_iterator<_Cp, _IsConst>; 2225f757f3fSDimitry Andric using difference_type = typename _In::difference_type; 2235f757f3fSDimitry Andric using __storage_type = typename _In::__storage_type; 2245f757f3fSDimitry Andric 22561cfbce3SDimitry Andric const int __bits_per_word = _In::__bits_per_word; 2260b57cec5SDimitry Andric difference_type __n = __last - __first; 2275f757f3fSDimitry Andric if (__n > 0) { 2280b57cec5SDimitry Andric // do first word 2295f757f3fSDimitry Andric if (__first.__ctz_ != 0) { 2300b57cec5SDimitry Andric unsigned __clz_f = __bits_per_word - __first.__ctz_; 2315f757f3fSDimitry Andric difference_type __dn = std::min(static_cast<difference_type>(__clz_f), __n); 2320b57cec5SDimitry Andric __n -= __dn; 2330b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 2340b57cec5SDimitry Andric __storage_type __b = *__first.__seg_ & __m; 2350b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __result.__ctz_; 2365f757f3fSDimitry Andric __storage_type __ddn = std::min<__storage_type>(__dn, __clz_r); 2370b57cec5SDimitry Andric __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 2380b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 2390b57cec5SDimitry Andric if (__result.__ctz_ > __first.__ctz_) 2400b57cec5SDimitry Andric *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_); 2410b57cec5SDimitry Andric else 2420b57cec5SDimitry Andric *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_); 2430b57cec5SDimitry Andric __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 2440b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 2450b57cec5SDimitry Andric __dn -= __ddn; 2465f757f3fSDimitry Andric if (__dn > 0) { 2470b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __dn); 2480b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 2490b57cec5SDimitry Andric *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn); 2500b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(__dn); 2510b57cec5SDimitry Andric } 2520b57cec5SDimitry Andric ++__first.__seg_; 2530b57cec5SDimitry Andric // __first.__ctz_ = 0; 2540b57cec5SDimitry Andric } 2550b57cec5SDimitry Andric // __first.__ctz_ == 0; 2560b57cec5SDimitry Andric // do middle words 2570b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __result.__ctz_; 2580b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) << __result.__ctz_; 2595f757f3fSDimitry Andric for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) { 2600b57cec5SDimitry Andric __storage_type __b = *__first.__seg_; 2610b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 2620b57cec5SDimitry Andric *__result.__seg_ |= __b << __result.__ctz_; 2630b57cec5SDimitry Andric ++__result.__seg_; 2640b57cec5SDimitry Andric *__result.__seg_ &= __m; 2650b57cec5SDimitry Andric *__result.__seg_ |= __b >> __clz_r; 2660b57cec5SDimitry Andric } 2670b57cec5SDimitry Andric // do last word 2685f757f3fSDimitry Andric if (__n > 0) { 2690b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __n); 2700b57cec5SDimitry Andric __storage_type __b = *__first.__seg_ & __m; 2715f757f3fSDimitry Andric __storage_type __dn = std::min(__n, static_cast<difference_type>(__clz_r)); 2720b57cec5SDimitry Andric __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 2730b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 2740b57cec5SDimitry Andric *__result.__seg_ |= __b << __result.__ctz_; 2750b57cec5SDimitry Andric __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 2760b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 2770b57cec5SDimitry Andric __n -= __dn; 2785f757f3fSDimitry Andric if (__n > 0) { 2790b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __n); 2800b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 2810b57cec5SDimitry Andric *__result.__seg_ |= __b >> __dn; 2820b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(__n); 2830b57cec5SDimitry Andric } 2840b57cec5SDimitry Andric } 2850b57cec5SDimitry Andric } 2860b57cec5SDimitry Andric return __result; 2870b57cec5SDimitry Andric} 2880b57cec5SDimitry Andric 2890b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 2905f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, false> 2915f757f3fSDimitry Andriccopy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) { 2920b57cec5SDimitry Andric if (__first.__ctz_ == __result.__ctz_) 2935f757f3fSDimitry Andric return std::__copy_aligned(__first, __last, __result); 2945f757f3fSDimitry Andric return std::__copy_unaligned(__first, __last, __result); 2950b57cec5SDimitry Andric} 2960b57cec5SDimitry Andric 2970b57cec5SDimitry Andric// copy_backward 2980b57cec5SDimitry Andric 2990b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 3005f757f3fSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_backward_aligned( 3015f757f3fSDimitry Andric __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) { 3025f757f3fSDimitry Andric using _In = __bit_iterator<_Cp, _IsConst>; 3035f757f3fSDimitry Andric using difference_type = typename _In::difference_type; 3045f757f3fSDimitry Andric using __storage_type = typename _In::__storage_type; 3055f757f3fSDimitry Andric 3060b57cec5SDimitry Andric const int __bits_per_word = _In::__bits_per_word; 3070b57cec5SDimitry Andric difference_type __n = __last - __first; 3085f757f3fSDimitry Andric if (__n > 0) { 3090b57cec5SDimitry Andric // do first word 3105f757f3fSDimitry Andric if (__last.__ctz_ != 0) { 3115f757f3fSDimitry Andric difference_type __dn = std::min(static_cast<difference_type>(__last.__ctz_), __n); 3120b57cec5SDimitry Andric __n -= __dn; 3130b57cec5SDimitry Andric unsigned __clz = __bits_per_word - __last.__ctz_; 3140b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz); 3150b57cec5SDimitry Andric __storage_type __b = *__last.__seg_ & __m; 3160b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 3170b57cec5SDimitry Andric *__result.__seg_ |= __b; 3185f757f3fSDimitry Andric __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + __result.__ctz_) % __bits_per_word); 3190b57cec5SDimitry Andric // __last.__ctz_ = 0 3200b57cec5SDimitry Andric } 3210b57cec5SDimitry Andric // __last.__ctz_ == 0 || __n == 0 3220b57cec5SDimitry Andric // __result.__ctz_ == 0 || __n == 0 3230b57cec5SDimitry Andric // do middle words 3240b57cec5SDimitry Andric __storage_type __nw = __n / __bits_per_word; 3250b57cec5SDimitry Andric __result.__seg_ -= __nw; 3260b57cec5SDimitry Andric __last.__seg_ -= __nw; 32761cfbce3SDimitry Andric std::copy_n(std::__to_address(__last.__seg_), __nw, std::__to_address(__result.__seg_)); 3280b57cec5SDimitry Andric __n -= __nw * __bits_per_word; 3290b57cec5SDimitry Andric // do last word 3305f757f3fSDimitry Andric if (__n > 0) { 3310b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n); 3320b57cec5SDimitry Andric __storage_type __b = *--__last.__seg_ & __m; 3330b57cec5SDimitry Andric *--__result.__seg_ &= ~__m; 3340b57cec5SDimitry Andric *__result.__seg_ |= __b; 3350b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 3360b57cec5SDimitry Andric } 3370b57cec5SDimitry Andric } 3380b57cec5SDimitry Andric return __result; 3390b57cec5SDimitry Andric} 3400b57cec5SDimitry Andric 3410b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 3425f757f3fSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_backward_unaligned( 3435f757f3fSDimitry Andric __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) { 3445f757f3fSDimitry Andric using _In = __bit_iterator<_Cp, _IsConst>; 3455f757f3fSDimitry Andric using difference_type = typename _In::difference_type; 3465f757f3fSDimitry Andric using __storage_type = typename _In::__storage_type; 3475f757f3fSDimitry Andric 3480b57cec5SDimitry Andric const int __bits_per_word = _In::__bits_per_word; 3490b57cec5SDimitry Andric difference_type __n = __last - __first; 3505f757f3fSDimitry Andric if (__n > 0) { 3510b57cec5SDimitry Andric // do first word 3525f757f3fSDimitry Andric if (__last.__ctz_ != 0) { 3535f757f3fSDimitry Andric difference_type __dn = std::min(static_cast<difference_type>(__last.__ctz_), __n); 3540b57cec5SDimitry Andric __n -= __dn; 3550b57cec5SDimitry Andric unsigned __clz_l = __bits_per_word - __last.__ctz_; 3560b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l); 3570b57cec5SDimitry Andric __storage_type __b = *__last.__seg_ & __m; 3580b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __result.__ctz_; 3595f757f3fSDimitry Andric __storage_type __ddn = std::min(__dn, static_cast<difference_type>(__result.__ctz_)); 3605f757f3fSDimitry Andric if (__ddn > 0) { 3610b57cec5SDimitry Andric __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r); 3620b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 3630b57cec5SDimitry Andric if (__result.__ctz_ > __last.__ctz_) 3640b57cec5SDimitry Andric *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 3650b57cec5SDimitry Andric else 3660b57cec5SDimitry Andric *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_); 3675f757f3fSDimitry Andric __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) + __result.__ctz_) % __bits_per_word); 3680b57cec5SDimitry Andric __dn -= __ddn; 3690b57cec5SDimitry Andric } 3705f757f3fSDimitry Andric if (__dn > 0) { 3710b57cec5SDimitry Andric // __result.__ctz_ == 0 3720b57cec5SDimitry Andric --__result.__seg_; 3730b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1)); 3740b57cec5SDimitry Andric __m = ~__storage_type(0) << __result.__ctz_; 3750b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 3760b57cec5SDimitry Andric __last.__ctz_ -= __dn + __ddn; 3770b57cec5SDimitry Andric *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 3780b57cec5SDimitry Andric } 3790b57cec5SDimitry Andric // __last.__ctz_ = 0 3800b57cec5SDimitry Andric } 3810b57cec5SDimitry Andric // __last.__ctz_ == 0 || __n == 0 3820b57cec5SDimitry Andric // __result.__ctz_ != 0 || __n == 0 3830b57cec5SDimitry Andric // do middle words 3840b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __result.__ctz_; 3850b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> __clz_r; 3865f757f3fSDimitry Andric for (; __n >= __bits_per_word; __n -= __bits_per_word) { 3870b57cec5SDimitry Andric __storage_type __b = *--__last.__seg_; 3880b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 3890b57cec5SDimitry Andric *__result.__seg_ |= __b >> __clz_r; 3900b57cec5SDimitry Andric *--__result.__seg_ &= __m; 3910b57cec5SDimitry Andric *__result.__seg_ |= __b << __result.__ctz_; 3920b57cec5SDimitry Andric } 3930b57cec5SDimitry Andric // do last word 3945f757f3fSDimitry Andric if (__n > 0) { 3950b57cec5SDimitry Andric __m = ~__storage_type(0) << (__bits_per_word - __n); 3960b57cec5SDimitry Andric __storage_type __b = *--__last.__seg_ & __m; 3970b57cec5SDimitry Andric __clz_r = __bits_per_word - __result.__ctz_; 3985f757f3fSDimitry Andric __storage_type __dn = std::min(__n, static_cast<difference_type>(__result.__ctz_)); 3990b57cec5SDimitry Andric __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r); 4000b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 4010b57cec5SDimitry Andric *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_); 4025f757f3fSDimitry Andric __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + __result.__ctz_) % __bits_per_word); 4030b57cec5SDimitry Andric __n -= __dn; 4045f757f3fSDimitry Andric if (__n > 0) { 4050b57cec5SDimitry Andric // __result.__ctz_ == 0 4060b57cec5SDimitry Andric --__result.__seg_; 4070b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 4080b57cec5SDimitry Andric __m = ~__storage_type(0) << __result.__ctz_; 4090b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 4100b57cec5SDimitry Andric *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn)); 4110b57cec5SDimitry Andric } 4120b57cec5SDimitry Andric } 4130b57cec5SDimitry Andric } 4140b57cec5SDimitry Andric return __result; 4150b57cec5SDimitry Andric} 4160b57cec5SDimitry Andric 4170b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 4185f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, false> copy_backward( 4195f757f3fSDimitry Andric __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) { 4200b57cec5SDimitry Andric if (__last.__ctz_ == __result.__ctz_) 4215f757f3fSDimitry Andric return std::__copy_backward_aligned(__first, __last, __result); 4225f757f3fSDimitry Andric return std::__copy_backward_unaligned(__first, __last, __result); 4230b57cec5SDimitry Andric} 4240b57cec5SDimitry Andric 4250b57cec5SDimitry Andric// move 4260b57cec5SDimitry Andric 4270b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 4285f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> 4295f757f3fSDimitry Andricmove(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) { 4305f757f3fSDimitry Andric return std::copy(__first, __last, __result); 4310b57cec5SDimitry Andric} 4320b57cec5SDimitry Andric 4330b57cec5SDimitry Andric// move_backward 4340b57cec5SDimitry Andric 4350b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 4365f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> move_backward( 4375f757f3fSDimitry Andric __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) { 4385f757f3fSDimitry Andric return std::copy_backward(__first, __last, __result); 4390b57cec5SDimitry Andric} 4400b57cec5SDimitry Andric 4410b57cec5SDimitry Andric// swap_ranges 4420b57cec5SDimitry Andric 44306c3fb27SDimitry Andrictemplate <class _Cl, class _Cr> 4445f757f3fSDimitry Andric_LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cr, false> __swap_ranges_aligned( 4455f757f3fSDimitry Andric __bit_iterator<_Cl, false> __first, __bit_iterator<_Cl, false> __last, __bit_iterator<_Cr, false> __result) { 4465f757f3fSDimitry Andric using _I1 = __bit_iterator<_Cl, false>; 4475f757f3fSDimitry Andric using difference_type = typename _I1::difference_type; 4485f757f3fSDimitry Andric using __storage_type = typename _I1::__storage_type; 4495f757f3fSDimitry Andric 4500b57cec5SDimitry Andric const int __bits_per_word = _I1::__bits_per_word; 4510b57cec5SDimitry Andric difference_type __n = __last - __first; 4525f757f3fSDimitry Andric if (__n > 0) { 4530b57cec5SDimitry Andric // do first word 4545f757f3fSDimitry Andric if (__first.__ctz_ != 0) { 4550b57cec5SDimitry Andric unsigned __clz = __bits_per_word - __first.__ctz_; 4565f757f3fSDimitry Andric difference_type __dn = std::min(static_cast<difference_type>(__clz), __n); 4570b57cec5SDimitry Andric __n -= __dn; 4580b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 4590b57cec5SDimitry Andric __storage_type __b1 = *__first.__seg_ & __m; 4600b57cec5SDimitry Andric *__first.__seg_ &= ~__m; 4610b57cec5SDimitry Andric __storage_type __b2 = *__result.__seg_ & __m; 4620b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 4630b57cec5SDimitry Andric *__result.__seg_ |= __b1; 4640b57cec5SDimitry Andric *__first.__seg_ |= __b2; 4650b57cec5SDimitry Andric __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 4660b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 4670b57cec5SDimitry Andric ++__first.__seg_; 4680b57cec5SDimitry Andric // __first.__ctz_ = 0; 4690b57cec5SDimitry Andric } 4700b57cec5SDimitry Andric // __first.__ctz_ == 0; 4710b57cec5SDimitry Andric // do middle words 4720b57cec5SDimitry Andric for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_) 4730b57cec5SDimitry Andric swap(*__first.__seg_, *__result.__seg_); 4740b57cec5SDimitry Andric // do last word 4755f757f3fSDimitry Andric if (__n > 0) { 4760b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 4770b57cec5SDimitry Andric __storage_type __b1 = *__first.__seg_ & __m; 4780b57cec5SDimitry Andric *__first.__seg_ &= ~__m; 4790b57cec5SDimitry Andric __storage_type __b2 = *__result.__seg_ & __m; 4800b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 4810b57cec5SDimitry Andric *__result.__seg_ |= __b1; 4820b57cec5SDimitry Andric *__first.__seg_ |= __b2; 4830b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(__n); 4840b57cec5SDimitry Andric } 4850b57cec5SDimitry Andric } 4860b57cec5SDimitry Andric return __result; 4870b57cec5SDimitry Andric} 4880b57cec5SDimitry Andric 48906c3fb27SDimitry Andrictemplate <class _Cl, class _Cr> 4905f757f3fSDimitry Andric_LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cr, false> __swap_ranges_unaligned( 4915f757f3fSDimitry Andric __bit_iterator<_Cl, false> __first, __bit_iterator<_Cl, false> __last, __bit_iterator<_Cr, false> __result) { 4925f757f3fSDimitry Andric using _I1 = __bit_iterator<_Cl, false>; 4935f757f3fSDimitry Andric using difference_type = typename _I1::difference_type; 4945f757f3fSDimitry Andric using __storage_type = typename _I1::__storage_type; 4955f757f3fSDimitry Andric 4960b57cec5SDimitry Andric const int __bits_per_word = _I1::__bits_per_word; 4970b57cec5SDimitry Andric difference_type __n = __last - __first; 4985f757f3fSDimitry Andric if (__n > 0) { 4990b57cec5SDimitry Andric // do first word 5005f757f3fSDimitry Andric if (__first.__ctz_ != 0) { 5010b57cec5SDimitry Andric unsigned __clz_f = __bits_per_word - __first.__ctz_; 5025f757f3fSDimitry Andric difference_type __dn = std::min(static_cast<difference_type>(__clz_f), __n); 5030b57cec5SDimitry Andric __n -= __dn; 5040b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 5050b57cec5SDimitry Andric __storage_type __b1 = *__first.__seg_ & __m; 5060b57cec5SDimitry Andric *__first.__seg_ &= ~__m; 5070b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __result.__ctz_; 5085f757f3fSDimitry Andric __storage_type __ddn = std::min<__storage_type>(__dn, __clz_r); 5090b57cec5SDimitry Andric __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 5100b57cec5SDimitry Andric __storage_type __b2 = *__result.__seg_ & __m; 5110b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 5125f757f3fSDimitry Andric if (__result.__ctz_ > __first.__ctz_) { 5130b57cec5SDimitry Andric unsigned __s = __result.__ctz_ - __first.__ctz_; 5140b57cec5SDimitry Andric *__result.__seg_ |= __b1 << __s; 5150b57cec5SDimitry Andric *__first.__seg_ |= __b2 >> __s; 5165f757f3fSDimitry Andric } else { 5170b57cec5SDimitry Andric unsigned __s = __first.__ctz_ - __result.__ctz_; 5180b57cec5SDimitry Andric *__result.__seg_ |= __b1 >> __s; 5190b57cec5SDimitry Andric *__first.__seg_ |= __b2 << __s; 5200b57cec5SDimitry Andric } 5210b57cec5SDimitry Andric __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 5220b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 5230b57cec5SDimitry Andric __dn -= __ddn; 5245f757f3fSDimitry Andric if (__dn > 0) { 5250b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __dn); 5260b57cec5SDimitry Andric __b2 = *__result.__seg_ & __m; 5270b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 5280b57cec5SDimitry Andric unsigned __s = __first.__ctz_ + __ddn; 5290b57cec5SDimitry Andric *__result.__seg_ |= __b1 >> __s; 5300b57cec5SDimitry Andric *__first.__seg_ |= __b2 << __s; 5310b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(__dn); 5320b57cec5SDimitry Andric } 5330b57cec5SDimitry Andric ++__first.__seg_; 5340b57cec5SDimitry Andric // __first.__ctz_ = 0; 5350b57cec5SDimitry Andric } 5360b57cec5SDimitry Andric // __first.__ctz_ == 0; 5370b57cec5SDimitry Andric // do middle words 5380b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) << __result.__ctz_; 5390b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __result.__ctz_; 5405f757f3fSDimitry Andric for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) { 5410b57cec5SDimitry Andric __storage_type __b1 = *__first.__seg_; 5420b57cec5SDimitry Andric __storage_type __b2 = *__result.__seg_ & __m; 5430b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 5440b57cec5SDimitry Andric *__result.__seg_ |= __b1 << __result.__ctz_; 5450b57cec5SDimitry Andric *__first.__seg_ = __b2 >> __result.__ctz_; 5460b57cec5SDimitry Andric ++__result.__seg_; 5470b57cec5SDimitry Andric __b2 = *__result.__seg_ & ~__m; 5480b57cec5SDimitry Andric *__result.__seg_ &= __m; 5490b57cec5SDimitry Andric *__result.__seg_ |= __b1 >> __clz_r; 5500b57cec5SDimitry Andric *__first.__seg_ |= __b2 << __clz_r; 5510b57cec5SDimitry Andric } 5520b57cec5SDimitry Andric // do last word 5535f757f3fSDimitry Andric if (__n > 0) { 5540b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __n); 5550b57cec5SDimitry Andric __storage_type __b1 = *__first.__seg_ & __m; 5560b57cec5SDimitry Andric *__first.__seg_ &= ~__m; 5575f757f3fSDimitry Andric __storage_type __dn = std::min<__storage_type>(__n, __clz_r); 5580b57cec5SDimitry Andric __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 5590b57cec5SDimitry Andric __storage_type __b2 = *__result.__seg_ & __m; 5600b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 5610b57cec5SDimitry Andric *__result.__seg_ |= __b1 << __result.__ctz_; 5620b57cec5SDimitry Andric *__first.__seg_ |= __b2 >> __result.__ctz_; 5630b57cec5SDimitry Andric __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 5640b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 5650b57cec5SDimitry Andric __n -= __dn; 5665f757f3fSDimitry Andric if (__n > 0) { 5670b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __n); 5680b57cec5SDimitry Andric __b2 = *__result.__seg_ & __m; 5690b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 5700b57cec5SDimitry Andric *__result.__seg_ |= __b1 >> __dn; 5710b57cec5SDimitry Andric *__first.__seg_ |= __b2 << __dn; 5720b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(__n); 5730b57cec5SDimitry Andric } 5740b57cec5SDimitry Andric } 5750b57cec5SDimitry Andric } 5760b57cec5SDimitry Andric return __result; 5770b57cec5SDimitry Andric} 5780b57cec5SDimitry Andric 57906c3fb27SDimitry Andrictemplate <class _Cl, class _Cr> 5805f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cr, false> swap_ranges( 5815f757f3fSDimitry Andric __bit_iterator<_Cl, false> __first1, __bit_iterator<_Cl, false> __last1, __bit_iterator<_Cr, false> __first2) { 5820b57cec5SDimitry Andric if (__first1.__ctz_ == __first2.__ctz_) 5835f757f3fSDimitry Andric return std::__swap_ranges_aligned(__first1, __last1, __first2); 5845f757f3fSDimitry Andric return std::__swap_ranges_unaligned(__first1, __last1, __first2); 5850b57cec5SDimitry Andric} 5860b57cec5SDimitry Andric 5870b57cec5SDimitry Andric// rotate 5880b57cec5SDimitry Andric 5890b57cec5SDimitry Andrictemplate <class _Cp> 5905f757f3fSDimitry Andricstruct __bit_array { 5915f757f3fSDimitry Andric using difference_type = typename _Cp::difference_type; 5925f757f3fSDimitry Andric using __storage_type = typename _Cp::__storage_type; 5935f757f3fSDimitry Andric using __storage_pointer = typename _Cp::__storage_pointer; 5945f757f3fSDimitry Andric using iterator = typename _Cp::iterator; 5955f757f3fSDimitry Andric 5960b57cec5SDimitry Andric static const unsigned __bits_per_word = _Cp::__bits_per_word; 5970b57cec5SDimitry Andric static const unsigned _Np = 4; 5980b57cec5SDimitry Andric 5990b57cec5SDimitry Andric difference_type __size_; 6000b57cec5SDimitry Andric __storage_type __word_[_Np]; 6010b57cec5SDimitry Andric 6025f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static difference_type capacity() { 6035f757f3fSDimitry Andric return static_cast<difference_type>(_Np * __bits_per_word); 6045f757f3fSDimitry Andric } 6055f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit __bit_array(difference_type __s) : __size_(__s) { 60661cfbce3SDimitry Andric if (__libcpp_is_constant_evaluated()) { 60761cfbce3SDimitry Andric for (size_t __i = 0; __i != __bit_array<_Cp>::_Np; ++__i) 60861cfbce3SDimitry Andric std::__construct_at(__word_ + __i, 0); 60961cfbce3SDimitry Andric } 61061cfbce3SDimitry Andric } 6115f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator begin() { 6120b57cec5SDimitry Andric return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]), 0); 6130b57cec5SDimitry Andric } 6145f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator end() { 6150b57cec5SDimitry Andric return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]) + __size_ / __bits_per_word, 6160b57cec5SDimitry Andric static_cast<unsigned>(__size_ % __bits_per_word)); 6170b57cec5SDimitry Andric } 6180b57cec5SDimitry Andric}; 6190b57cec5SDimitry Andric 6200b57cec5SDimitry Andrictemplate <class _Cp> 621bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> 6225f757f3fSDimitry Andricrotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last) { 6235f757f3fSDimitry Andric using _I1 = __bit_iterator<_Cp, false>; 6245f757f3fSDimitry Andric using difference_type = typename _I1::difference_type; 6255f757f3fSDimitry Andric 6260b57cec5SDimitry Andric difference_type __d1 = __middle - __first; 6270b57cec5SDimitry Andric difference_type __d2 = __last - __middle; 6280b57cec5SDimitry Andric _I1 __r = __first + __d2; 6295f757f3fSDimitry Andric while (__d1 != 0 && __d2 != 0) { 6305f757f3fSDimitry Andric if (__d1 <= __d2) { 6315f757f3fSDimitry Andric if (__d1 <= __bit_array<_Cp>::capacity()) { 6320b57cec5SDimitry Andric __bit_array<_Cp> __b(__d1); 6335f757f3fSDimitry Andric std::copy(__first, __middle, __b.begin()); 6345f757f3fSDimitry Andric std::copy(__b.begin(), __b.end(), std::copy(__middle, __last, __first)); 6350b57cec5SDimitry Andric break; 6365f757f3fSDimitry Andric } else { 6375f757f3fSDimitry Andric __bit_iterator<_Cp, false> __mp = std::swap_ranges(__first, __middle, __middle); 6380b57cec5SDimitry Andric __first = __middle; 6390b57cec5SDimitry Andric __middle = __mp; 6400b57cec5SDimitry Andric __d2 -= __d1; 6410b57cec5SDimitry Andric } 6425f757f3fSDimitry Andric } else { 6435f757f3fSDimitry Andric if (__d2 <= __bit_array<_Cp>::capacity()) { 6440b57cec5SDimitry Andric __bit_array<_Cp> __b(__d2); 6455f757f3fSDimitry Andric std::copy(__middle, __last, __b.begin()); 6465f757f3fSDimitry Andric std::copy_backward(__b.begin(), __b.end(), std::copy_backward(__first, __middle, __last)); 6470b57cec5SDimitry Andric break; 6485f757f3fSDimitry Andric } else { 6490b57cec5SDimitry Andric __bit_iterator<_Cp, false> __mp = __first + __d2; 6505f757f3fSDimitry Andric std::swap_ranges(__first, __mp, __middle); 6510b57cec5SDimitry Andric __first = __mp; 6520b57cec5SDimitry Andric __d1 -= __d2; 6530b57cec5SDimitry Andric } 6540b57cec5SDimitry Andric } 6550b57cec5SDimitry Andric } 6560b57cec5SDimitry Andric return __r; 6570b57cec5SDimitry Andric} 6580b57cec5SDimitry Andric 6590b57cec5SDimitry Andric// equal 6600b57cec5SDimitry Andric 6610b57cec5SDimitry Andrictemplate <class _Cp, bool _IC1, bool _IC2> 6625f757f3fSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool __equal_unaligned( 6635f757f3fSDimitry Andric __bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) { 6645f757f3fSDimitry Andric using _It = __bit_iterator<_Cp, _IC1>; 6655f757f3fSDimitry Andric using difference_type = typename _It::difference_type; 6665f757f3fSDimitry Andric using __storage_type = typename _It::__storage_type; 6675f757f3fSDimitry Andric 66861cfbce3SDimitry Andric const int __bits_per_word = _It::__bits_per_word; 6690b57cec5SDimitry Andric difference_type __n = __last1 - __first1; 6705f757f3fSDimitry Andric if (__n > 0) { 6710b57cec5SDimitry Andric // do first word 6725f757f3fSDimitry Andric if (__first1.__ctz_ != 0) { 6730b57cec5SDimitry Andric unsigned __clz_f = __bits_per_word - __first1.__ctz_; 6745f757f3fSDimitry Andric difference_type __dn = std::min(static_cast<difference_type>(__clz_f), __n); 6750b57cec5SDimitry Andric __n -= __dn; 6760b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 6770b57cec5SDimitry Andric __storage_type __b = *__first1.__seg_ & __m; 6780b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __first2.__ctz_; 6795f757f3fSDimitry Andric __storage_type __ddn = std::min<__storage_type>(__dn, __clz_r); 6800b57cec5SDimitry Andric __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 6815f757f3fSDimitry Andric if (__first2.__ctz_ > __first1.__ctz_) { 6820b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_))) 6830b57cec5SDimitry Andric return false; 6845f757f3fSDimitry Andric } else { 6850b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_))) 6860b57cec5SDimitry Andric return false; 6870b57cec5SDimitry Andric } 6880b57cec5SDimitry Andric __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word; 6890b57cec5SDimitry Andric __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word); 6900b57cec5SDimitry Andric __dn -= __ddn; 6915f757f3fSDimitry Andric if (__dn > 0) { 6920b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __dn); 6930b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn))) 6940b57cec5SDimitry Andric return false; 6950b57cec5SDimitry Andric __first2.__ctz_ = static_cast<unsigned>(__dn); 6960b57cec5SDimitry Andric } 6970b57cec5SDimitry Andric ++__first1.__seg_; 6980b57cec5SDimitry Andric // __first1.__ctz_ = 0; 6990b57cec5SDimitry Andric } 7000b57cec5SDimitry Andric // __first1.__ctz_ == 0; 7010b57cec5SDimitry Andric // do middle words 7020b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __first2.__ctz_; 7030b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) << __first2.__ctz_; 7045f757f3fSDimitry Andric for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_) { 7050b57cec5SDimitry Andric __storage_type __b = *__first1.__seg_; 7060b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 7070b57cec5SDimitry Andric return false; 7080b57cec5SDimitry Andric ++__first2.__seg_; 7090b57cec5SDimitry Andric if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r)) 7100b57cec5SDimitry Andric return false; 7110b57cec5SDimitry Andric } 7120b57cec5SDimitry Andric // do last word 7135f757f3fSDimitry Andric if (__n > 0) { 7140b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __n); 7150b57cec5SDimitry Andric __storage_type __b = *__first1.__seg_ & __m; 7165f757f3fSDimitry Andric __storage_type __dn = std::min(__n, static_cast<difference_type>(__clz_r)); 7170b57cec5SDimitry Andric __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 7180b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 7190b57cec5SDimitry Andric return false; 7200b57cec5SDimitry Andric __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word; 7210b57cec5SDimitry Andric __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word); 7220b57cec5SDimitry Andric __n -= __dn; 7235f757f3fSDimitry Andric if (__n > 0) { 7240b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __n); 7250b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (__b >> __dn)) 7260b57cec5SDimitry Andric return false; 7270b57cec5SDimitry Andric } 7280b57cec5SDimitry Andric } 7290b57cec5SDimitry Andric } 7300b57cec5SDimitry Andric return true; 7310b57cec5SDimitry Andric} 7320b57cec5SDimitry Andric 7330b57cec5SDimitry Andrictemplate <class _Cp, bool _IC1, bool _IC2> 7345f757f3fSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool __equal_aligned( 7355f757f3fSDimitry Andric __bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) { 7365f757f3fSDimitry Andric using _It = __bit_iterator<_Cp, _IC1>; 7375f757f3fSDimitry Andric using difference_type = typename _It::difference_type; 7385f757f3fSDimitry Andric using __storage_type = typename _It::__storage_type; 7395f757f3fSDimitry Andric 74061cfbce3SDimitry Andric const int __bits_per_word = _It::__bits_per_word; 7410b57cec5SDimitry Andric difference_type __n = __last1 - __first1; 7425f757f3fSDimitry Andric if (__n > 0) { 7430b57cec5SDimitry Andric // do first word 7445f757f3fSDimitry Andric if (__first1.__ctz_ != 0) { 7450b57cec5SDimitry Andric unsigned __clz = __bits_per_word - __first1.__ctz_; 7465f757f3fSDimitry Andric difference_type __dn = std::min(static_cast<difference_type>(__clz), __n); 7470b57cec5SDimitry Andric __n -= __dn; 7480b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 7490b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 7500b57cec5SDimitry Andric return false; 7510b57cec5SDimitry Andric ++__first2.__seg_; 7520b57cec5SDimitry Andric ++__first1.__seg_; 7530b57cec5SDimitry Andric // __first1.__ctz_ = 0; 7540b57cec5SDimitry Andric // __first2.__ctz_ = 0; 7550b57cec5SDimitry Andric } 7560b57cec5SDimitry Andric // __first1.__ctz_ == 0; 7570b57cec5SDimitry Andric // __first2.__ctz_ == 0; 7580b57cec5SDimitry Andric // do middle words 7590b57cec5SDimitry Andric for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_) 7600b57cec5SDimitry Andric if (*__first2.__seg_ != *__first1.__seg_) 7610b57cec5SDimitry Andric return false; 7620b57cec5SDimitry Andric // do last word 7635f757f3fSDimitry Andric if (__n > 0) { 7640b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 7650b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 7660b57cec5SDimitry Andric return false; 7670b57cec5SDimitry Andric } 7680b57cec5SDimitry Andric } 7690b57cec5SDimitry Andric return true; 7700b57cec5SDimitry Andric} 7710b57cec5SDimitry Andric 7720b57cec5SDimitry Andrictemplate <class _Cp, bool _IC1, bool _IC2> 7735f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool 7745f757f3fSDimitry Andricequal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) { 7750b57cec5SDimitry Andric if (__first1.__ctz_ == __first2.__ctz_) 7765f757f3fSDimitry Andric return std::__equal_aligned(__first1, __last1, __first2); 7775f757f3fSDimitry Andric return std::__equal_unaligned(__first1, __last1, __first2); 7780b57cec5SDimitry Andric} 7790b57cec5SDimitry Andric 7805f757f3fSDimitry Andrictemplate <class _Cp, bool _IsConst, typename _Cp::__storage_type> 7815f757f3fSDimitry Andricclass __bit_iterator { 7820b57cec5SDimitry Andricpublic: 7835f757f3fSDimitry Andric using difference_type = typename _Cp::difference_type; 7845f757f3fSDimitry Andric using value_type = bool; 7855f757f3fSDimitry Andric using pointer = __bit_iterator; 78681ad6265SDimitry Andric#ifndef _LIBCPP_ABI_BITSET_VECTOR_BOOL_CONST_SUBSCRIPT_RETURN_BOOL 7875f757f3fSDimitry Andric using reference = __conditional_t<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >; 78881ad6265SDimitry Andric#else 789bdd1243dSDimitry Andric using reference = __conditional_t<_IsConst, bool, __bit_reference<_Cp> >; 79081ad6265SDimitry Andric#endif 7915f757f3fSDimitry Andric using iterator_category = random_access_iterator_tag; 7920b57cec5SDimitry Andric 7930b57cec5SDimitry Andricprivate: 7945f757f3fSDimitry Andric using __storage_type = typename _Cp::__storage_type; 7955f757f3fSDimitry Andric using __storage_pointer = 7965f757f3fSDimitry Andric __conditional_t<_IsConst, typename _Cp::__const_storage_pointer, typename _Cp::__storage_pointer>; 7975f757f3fSDimitry Andric 7980b57cec5SDimitry Andric static const unsigned __bits_per_word = _Cp::__bits_per_word; 7990b57cec5SDimitry Andric 8000b57cec5SDimitry Andric __storage_pointer __seg_; 8010b57cec5SDimitry Andric unsigned __ctz_; 8020b57cec5SDimitry Andric 8030b57cec5SDimitry Andricpublic: 8045f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator() _NOEXCEPT 80506c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 8065f757f3fSDimitry Andric : __seg_(nullptr), 8075f757f3fSDimitry Andric __ctz_(0) 8080b57cec5SDimitry Andric#endif 8095f757f3fSDimitry Andric { 8105f757f3fSDimitry Andric } 8110b57cec5SDimitry Andric 8124652422eSDimitry Andric // When _IsConst=false, this is the copy constructor. 8134652422eSDimitry Andric // It is non-trivial. Making it trivial would break ABI. 8144652422eSDimitry Andric // When _IsConst=true, this is a converting constructor; 8154652422eSDimitry Andric // the copy and move constructors are implicitly generated 8164652422eSDimitry Andric // and trivial. 8175f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT 8185f757f3fSDimitry Andric : __seg_(__it.__seg_), 8195f757f3fSDimitry Andric __ctz_(__it.__ctz_) {} 8200b57cec5SDimitry Andric 8214652422eSDimitry Andric // When _IsConst=false, we have a user-provided copy constructor, 8224652422eSDimitry Andric // so we must also provide a copy assignment operator because 8234652422eSDimitry Andric // the implicit generation of a defaulted one is deprecated. 8244652422eSDimitry Andric // When _IsConst=true, the assignment operators are 8254652422eSDimitry Andric // implicitly generated and trivial. 8265f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& 8275f757f3fSDimitry Andric operator=(const _If<_IsConst, struct __private_nat, __bit_iterator>& __it) { 8284652422eSDimitry Andric __seg_ = __it.__seg_; 8294652422eSDimitry Andric __ctz_ = __it.__ctz_; 8304652422eSDimitry Andric return *this; 8314652422eSDimitry Andric } 83247395794SDimitry Andric 8335f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference operator*() const _NOEXCEPT { 834bdd1243dSDimitry Andric return __conditional_t<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >( 835bdd1243dSDimitry Andric __seg_, __storage_type(1) << __ctz_); 83681ad6265SDimitry Andric } 8370b57cec5SDimitry Andric 8385f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator++() { 8390b57cec5SDimitry Andric if (__ctz_ != __bits_per_word - 1) 8400b57cec5SDimitry Andric ++__ctz_; 8415f757f3fSDimitry Andric else { 8420b57cec5SDimitry Andric __ctz_ = 0; 8430b57cec5SDimitry Andric ++__seg_; 8440b57cec5SDimitry Andric } 8450b57cec5SDimitry Andric return *this; 8460b57cec5SDimitry Andric } 8470b57cec5SDimitry Andric 8485f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator++(int) { 8490b57cec5SDimitry Andric __bit_iterator __tmp = *this; 8500b57cec5SDimitry Andric ++(*this); 8510b57cec5SDimitry Andric return __tmp; 8520b57cec5SDimitry Andric } 8530b57cec5SDimitry Andric 8545f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator--() { 8550b57cec5SDimitry Andric if (__ctz_ != 0) 8560b57cec5SDimitry Andric --__ctz_; 8575f757f3fSDimitry Andric else { 8580b57cec5SDimitry Andric __ctz_ = __bits_per_word - 1; 8590b57cec5SDimitry Andric --__seg_; 8600b57cec5SDimitry Andric } 8610b57cec5SDimitry Andric return *this; 8620b57cec5SDimitry Andric } 8630b57cec5SDimitry Andric 8645f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator--(int) { 8650b57cec5SDimitry Andric __bit_iterator __tmp = *this; 8660b57cec5SDimitry Andric --(*this); 8670b57cec5SDimitry Andric return __tmp; 8680b57cec5SDimitry Andric } 8690b57cec5SDimitry Andric 8705f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator+=(difference_type __n) { 8710b57cec5SDimitry Andric if (__n >= 0) 8720b57cec5SDimitry Andric __seg_ += (__n + __ctz_) / __bits_per_word; 8730b57cec5SDimitry Andric else 8745f757f3fSDimitry Andric __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1) / 8755f757f3fSDimitry Andric static_cast<difference_type>(__bits_per_word); 8760b57cec5SDimitry Andric __n &= (__bits_per_word - 1); 8770b57cec5SDimitry Andric __ctz_ = static_cast<unsigned>((__n + __ctz_) % __bits_per_word); 8780b57cec5SDimitry Andric return *this; 8790b57cec5SDimitry Andric } 8800b57cec5SDimitry Andric 8815f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator-=(difference_type __n) { 8820b57cec5SDimitry Andric return *this += -__n; 8830b57cec5SDimitry Andric } 8840b57cec5SDimitry Andric 8855f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator+(difference_type __n) const { 8860b57cec5SDimitry Andric __bit_iterator __t(*this); 8870b57cec5SDimitry Andric __t += __n; 8880b57cec5SDimitry Andric return __t; 8890b57cec5SDimitry Andric } 8900b57cec5SDimitry Andric 8915f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator-(difference_type __n) const { 8920b57cec5SDimitry Andric __bit_iterator __t(*this); 8930b57cec5SDimitry Andric __t -= __n; 8940b57cec5SDimitry Andric return __t; 8950b57cec5SDimitry Andric } 8960b57cec5SDimitry Andric 8975f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator 8985f757f3fSDimitry Andric operator+(difference_type __n, const __bit_iterator& __it) { 8995f757f3fSDimitry Andric return __it + __n; 9005f757f3fSDimitry Andric } 9010b57cec5SDimitry Andric 9025f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend difference_type 9035f757f3fSDimitry Andric operator-(const __bit_iterator& __x, const __bit_iterator& __y) { 9045f757f3fSDimitry Andric return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_; 9055f757f3fSDimitry Andric } 9060b57cec5SDimitry Andric 9075f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference operator[](difference_type __n) const { 9085f757f3fSDimitry Andric return *(*this + __n); 9095f757f3fSDimitry Andric } 9100b57cec5SDimitry Andric 9115f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool 9125f757f3fSDimitry Andric operator==(const __bit_iterator& __x, const __bit_iterator& __y) { 9135f757f3fSDimitry Andric return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_; 9145f757f3fSDimitry Andric } 9150b57cec5SDimitry Andric 9165f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool 9175f757f3fSDimitry Andric operator!=(const __bit_iterator& __x, const __bit_iterator& __y) { 9185f757f3fSDimitry Andric return !(__x == __y); 9195f757f3fSDimitry Andric } 9200b57cec5SDimitry Andric 9215f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool 9225f757f3fSDimitry Andric operator<(const __bit_iterator& __x, const __bit_iterator& __y) { 9235f757f3fSDimitry Andric return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_); 9245f757f3fSDimitry Andric } 9250b57cec5SDimitry Andric 9265f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool 9275f757f3fSDimitry Andric operator>(const __bit_iterator& __x, const __bit_iterator& __y) { 9285f757f3fSDimitry Andric return __y < __x; 9295f757f3fSDimitry Andric } 9300b57cec5SDimitry Andric 9315f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool 9325f757f3fSDimitry Andric operator<=(const __bit_iterator& __x, const __bit_iterator& __y) { 9335f757f3fSDimitry Andric return !(__y < __x); 9345f757f3fSDimitry Andric } 9350b57cec5SDimitry Andric 9365f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool 9375f757f3fSDimitry Andric operator>=(const __bit_iterator& __x, const __bit_iterator& __y) { 9385f757f3fSDimitry Andric return !(__x < __y); 9395f757f3fSDimitry Andric } 9400b57cec5SDimitry Andric 9410b57cec5SDimitry Andricprivate: 942*0fca6ea1SDimitry Andric _LIBCPP_HIDE_FROM_ABI 943*0fca6ea1SDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT 9445f757f3fSDimitry Andric : __seg_(__s), 9455f757f3fSDimitry Andric __ctz_(__ctz) {} 9460b57cec5SDimitry Andric 9470b57cec5SDimitry Andric friend typename _Cp::__self; 9480b57cec5SDimitry Andric 9490b57cec5SDimitry Andric friend class __bit_reference<_Cp>; 9500b57cec5SDimitry Andric friend class __bit_const_reference<_Cp>; 9510b57cec5SDimitry Andric friend class __bit_iterator<_Cp, true>; 95261cfbce3SDimitry Andric template <class _Dp> 9535f757f3fSDimitry Andric friend struct __bit_array; 954*0fca6ea1SDimitry Andric 955868ee3f2SDimitry Andric template <bool _FillVal, class _Dp> 956*0fca6ea1SDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 friend void 957*0fca6ea1SDimitry Andric __fill_n_bool(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); 95861cfbce3SDimitry Andric 95961cfbce3SDimitry Andric template <class _Dp, bool _IC> 9605f757f3fSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> __copy_aligned( 9615f757f3fSDimitry Andric __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result); 96261cfbce3SDimitry Andric template <class _Dp, bool _IC> 9635f757f3fSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> __copy_unaligned( 9645f757f3fSDimitry Andric __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result); 96561cfbce3SDimitry Andric template <class _Dp, bool _IC> 9665f757f3fSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> 9675f757f3fSDimitry Andric copy(__bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result); 96861cfbce3SDimitry Andric template <class _Dp, bool _IC> 9695f757f3fSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> __copy_backward_aligned( 9705f757f3fSDimitry Andric __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result); 97161cfbce3SDimitry Andric template <class _Dp, bool _IC> 9725f757f3fSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> __copy_backward_unaligned( 9735f757f3fSDimitry Andric __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result); 97461cfbce3SDimitry Andric template <class _Dp, bool _IC> 9755f757f3fSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> 9765f757f3fSDimitry Andric copy_backward(__bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result); 9775f757f3fSDimitry Andric template <class _Cl, class _Cr> 9785f757f3fSDimitry Andric friend __bit_iterator<_Cr, false> 9795f757f3fSDimitry Andric __swap_ranges_aligned(__bit_iterator<_Cl, false>, __bit_iterator<_Cl, false>, __bit_iterator<_Cr, false>); 9805f757f3fSDimitry Andric template <class _Cl, class _Cr> 9815f757f3fSDimitry Andric friend __bit_iterator<_Cr, false> 9825f757f3fSDimitry Andric __swap_ranges_unaligned(__bit_iterator<_Cl, false>, __bit_iterator<_Cl, false>, __bit_iterator<_Cr, false>); 9835f757f3fSDimitry Andric template <class _Cl, class _Cr> 9845f757f3fSDimitry Andric friend __bit_iterator<_Cr, false> 9855f757f3fSDimitry Andric swap_ranges(__bit_iterator<_Cl, false>, __bit_iterator<_Cl, false>, __bit_iterator<_Cr, false>); 98661cfbce3SDimitry Andric template <class _Dp> 9875f757f3fSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> 9885f757f3fSDimitry Andric rotate(__bit_iterator<_Dp, false>, __bit_iterator<_Dp, false>, __bit_iterator<_Dp, false>); 98961cfbce3SDimitry Andric template <class _Dp, bool _IC1, bool _IC2> 9905f757f3fSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool 9915f757f3fSDimitry Andric __equal_aligned(__bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC2>); 99261cfbce3SDimitry Andric template <class _Dp, bool _IC1, bool _IC2> 9935f757f3fSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool 9945f757f3fSDimitry Andric __equal_unaligned(__bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC2>); 99561cfbce3SDimitry Andric template <class _Dp, bool _IC1, bool _IC2> 9965f757f3fSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool 9975f757f3fSDimitry Andric equal(__bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC2>); 9985f757f3fSDimitry Andric template <bool _ToFind, class _Dp, bool _IC> 9995f757f3fSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, _IC> 10005f757f3fSDimitry Andric __find_bool(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 10015f757f3fSDimitry Andric template <bool _ToCount, class _Dp, bool _IC> 1002*0fca6ea1SDimitry Andric friend typename __bit_iterator<_Dp, _IC>::difference_type _LIBCPP_HIDE_FROM_ABI 1003*0fca6ea1SDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 __count_bool(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 10040b57cec5SDimitry Andric}; 10050b57cec5SDimitry Andric 10060b57cec5SDimitry Andric_LIBCPP_END_NAMESPACE_STD 10070b57cec5SDimitry Andric 10080b57cec5SDimitry Andric_LIBCPP_POP_MACROS 10090b57cec5SDimitry Andric 10100b57cec5SDimitry Andric#endif // _LIBCPP___BIT_REFERENCE 1011