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