// -*- C++ -*- //===----------------------------------------------------------------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// #ifndef _LIBCPP___BIT_REFERENCE #define _LIBCPP___BIT_REFERENCE #include <__algorithm/copy_n.h> #include <__algorithm/fill_n.h> #include <__algorithm/min.h> #include <__bit/countr.h> #include <__bit/invert_if.h> #include <__bit/popcount.h> #include <__config> #include <__fwd/bit_reference.h> #include <__iterator/iterator_traits.h> #include <__memory/construct_at.h> #include <__memory/pointer_traits.h> #include <__type_traits/conditional.h> #include <__utility/swap.h> #include <cstring> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header #endif _LIBCPP_PUSH_MACROS #include <__undef_macros> _LIBCPP_BEGIN_NAMESPACE_STD template <class _Cp> class __bit_const_reference; template <class _Tp> struct __has_storage_type { static const bool value = false; }; template <class _Cp, bool = __has_storage_type<_Cp>::value> class __bit_reference { using __storage_type = typename _Cp::__storage_type; using __storage_pointer = typename _Cp::__storage_pointer; __storage_pointer __seg_; __storage_type __mask_; friend typename _Cp::__self; friend class __bit_const_reference<_Cp>; friend class __bit_iterator<_Cp, false>; public: using __container = typename _Cp::__self; _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_reference(const __bit_reference&) = default; _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 operator bool() const _NOEXCEPT { return static_cast<bool>(*__seg_ & __mask_); } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool operator~() const _NOEXCEPT { return !static_cast<bool>(*this); } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_reference& operator=(bool __x) _NOEXCEPT { if (__x) *__seg_ |= __mask_; else *__seg_ &= ~__mask_; return *this; } #if _LIBCPP_STD_VER >= 23 _LIBCPP_HIDE_FROM_ABI constexpr const __bit_reference& operator=(bool __x) const noexcept { if (__x) *__seg_ |= __mask_; else *__seg_ &= ~__mask_; return *this; } #endif _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_reference& operator=(const __bit_reference& __x) _NOEXCEPT { return operator=(static_cast<bool>(__x)); } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void flip() _NOEXCEPT { *__seg_ ^= __mask_; } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, false> operator&() const _NOEXCEPT { return __bit_iterator<_Cp, false>(__seg_, static_cast<unsigned>(std::__libcpp_ctz(__mask_))); } private: _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit __bit_reference( __storage_pointer __s, __storage_type __m) _NOEXCEPT : __seg_(__s), __mask_(__m) {} }; template <class _Cp> class __bit_reference<_Cp, false> {}; template <class _Cp> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void swap(__bit_reference<_Cp> __x, __bit_reference<_Cp> __y) _NOEXCEPT { bool __t = __x; __x = __y; __y = __t; } template <class _Cp, class _Dp> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void swap(__bit_reference<_Cp> __x, __bit_reference<_Dp> __y) _NOEXCEPT { bool __t = __x; __x = __y; __y = __t; } template <class _Cp> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void swap(__bit_reference<_Cp> __x, bool& __y) _NOEXCEPT { bool __t = __x; __x = __y; __y = __t; } template <class _Cp> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void swap(bool& __x, __bit_reference<_Cp> __y) _NOEXCEPT { bool __t = __x; __x = __y; __y = __t; } template <class _Cp> class __bit_const_reference { using __storage_type = typename _Cp::__storage_type; using __storage_pointer = typename _Cp::__const_storage_pointer; __storage_pointer __seg_; __storage_type __mask_; friend typename _Cp::__self; friend class __bit_iterator<_Cp, true>; public: using __container = typename _Cp::__self; _LIBCPP_HIDE_FROM_ABI __bit_const_reference(const __bit_const_reference&) = default; _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_const_reference(const __bit_reference<_Cp>& __x) _NOEXCEPT : __seg_(__x.__seg_), __mask_(__x.__mask_) {} _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR operator bool() const _NOEXCEPT { return static_cast<bool>(*__seg_ & __mask_); } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, true> operator&() const _NOEXCEPT { return __bit_iterator<_Cp, true>(__seg_, static_cast<unsigned>(std::__libcpp_ctz(__mask_))); } private: _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR explicit __bit_const_reference( __storage_pointer __s, __storage_type __m) _NOEXCEPT : __seg_(__s), __mask_(__m) {} __bit_const_reference& operator=(const __bit_const_reference&) = delete; }; // fill_n template <bool _FillVal, class _Cp> _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __fill_n(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) { using _It = __bit_iterator<_Cp, false>; using __storage_type = typename _It::__storage_type; const int __bits_per_word = _It::__bits_per_word; // do first partial word if (__first.__ctz_ != 0) { __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); __storage_type __dn = std::min(__clz_f, __n); __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); if (_FillVal) *__first.__seg_ |= __m; else *__first.__seg_ &= ~__m; __n -= __dn; ++__first.__seg_; } // do middle whole words __storage_type __nw = __n / __bits_per_word; std::fill_n(std::__to_address(__first.__seg_), __nw, _FillVal ? static_cast<__storage_type>(-1) : 0); __n -= __nw * __bits_per_word; // do last partial word if (__n > 0) { __first.__seg_ += __nw; __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); if (_FillVal) *__first.__seg_ |= __m; else *__first.__seg_ &= ~__m; } } template <class _Cp> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void fill_n(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n, bool __value) { if (__n > 0) { if (__value) std::__fill_n<true>(__first, __n); else std::__fill_n<false>(__first, __n); } } // fill template <class _Cp> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void fill(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __last, bool __value) { std::fill_n(__first, static_cast<typename _Cp::size_type>(__last - __first), __value); } // copy template <class _Cp, bool _IsConst> _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_aligned( __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) { using _In = __bit_iterator<_Cp, _IsConst>; using difference_type = typename _In::difference_type; using __storage_type = typename _In::__storage_type; const int __bits_per_word = _In::__bits_per_word; difference_type __n = __last - __first; if (__n > 0) { // do first word if (__first.__ctz_ != 0) { unsigned __clz = __bits_per_word - __first.__ctz_; difference_type __dn = std::min(static_cast<difference_type>(__clz), __n); __n -= __dn; __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); __storage_type __b = *__first.__seg_ & __m; *__result.__seg_ &= ~__m; *__result.__seg_ |= __b; __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); ++__first.__seg_; // __first.__ctz_ = 0; } // __first.__ctz_ == 0; // do middle words __storage_type __nw = __n / __bits_per_word; std::copy_n(std::__to_address(__first.__seg_), __nw, std::__to_address(__result.__seg_)); __n -= __nw * __bits_per_word; __result.__seg_ += __nw; // do last word if (__n > 0) { __first.__seg_ += __nw; __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); __storage_type __b = *__first.__seg_ & __m; *__result.__seg_ &= ~__m; *__result.__seg_ |= __b; __result.__ctz_ = static_cast<unsigned>(__n); } } return __result; } template <class _Cp, bool _IsConst> _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_unaligned( __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) { using _In = __bit_iterator<_Cp, _IsConst>; using difference_type = typename _In::difference_type; using __storage_type = typename _In::__storage_type; const int __bits_per_word = _In::__bits_per_word; difference_type __n = __last - __first; if (__n > 0) { // do first word if (__first.__ctz_ != 0) { unsigned __clz_f = __bits_per_word - __first.__ctz_; difference_type __dn = std::min(static_cast<difference_type>(__clz_f), __n); __n -= __dn; __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); __storage_type __b = *__first.__seg_ & __m; unsigned __clz_r = __bits_per_word - __result.__ctz_; __storage_type __ddn = std::min<__storage_type>(__dn, __clz_r); __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); *__result.__seg_ &= ~__m; if (__result.__ctz_ > __first.__ctz_) *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_); else *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_); __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); __dn -= __ddn; if (__dn > 0) { __m = ~__storage_type(0) >> (__bits_per_word - __dn); *__result.__seg_ &= ~__m; *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn); __result.__ctz_ = static_cast<unsigned>(__dn); } ++__first.__seg_; // __first.__ctz_ = 0; } // __first.__ctz_ == 0; // do middle words unsigned __clz_r = __bits_per_word - __result.__ctz_; __storage_type __m = ~__storage_type(0) << __result.__ctz_; for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) { __storage_type __b = *__first.__seg_; *__result.__seg_ &= ~__m; *__result.__seg_ |= __b << __result.__ctz_; ++__result.__seg_; *__result.__seg_ &= __m; *__result.__seg_ |= __b >> __clz_r; } // do last word if (__n > 0) { __m = ~__storage_type(0) >> (__bits_per_word - __n); __storage_type __b = *__first.__seg_ & __m; __storage_type __dn = std::min(__n, static_cast<difference_type>(__clz_r)); __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); *__result.__seg_ &= ~__m; *__result.__seg_ |= __b << __result.__ctz_; __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); __n -= __dn; if (__n > 0) { __m = ~__storage_type(0) >> (__bits_per_word - __n); *__result.__seg_ &= ~__m; *__result.__seg_ |= __b >> __dn; __result.__ctz_ = static_cast<unsigned>(__n); } } } return __result; } template <class _Cp, bool _IsConst> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, false> copy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) { if (__first.__ctz_ == __result.__ctz_) return std::__copy_aligned(__first, __last, __result); return std::__copy_unaligned(__first, __last, __result); } // copy_backward template <class _Cp, bool _IsConst> _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_backward_aligned( __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) { using _In = __bit_iterator<_Cp, _IsConst>; using difference_type = typename _In::difference_type; using __storage_type = typename _In::__storage_type; const int __bits_per_word = _In::__bits_per_word; difference_type __n = __last - __first; if (__n > 0) { // do first word if (__last.__ctz_ != 0) { difference_type __dn = std::min(static_cast<difference_type>(__last.__ctz_), __n); __n -= __dn; unsigned __clz = __bits_per_word - __last.__ctz_; __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz); __storage_type __b = *__last.__seg_ & __m; *__result.__seg_ &= ~__m; *__result.__seg_ |= __b; __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + __result.__ctz_) % __bits_per_word); // __last.__ctz_ = 0 } // __last.__ctz_ == 0 || __n == 0 // __result.__ctz_ == 0 || __n == 0 // do middle words __storage_type __nw = __n / __bits_per_word; __result.__seg_ -= __nw; __last.__seg_ -= __nw; std::copy_n(std::__to_address(__last.__seg_), __nw, std::__to_address(__result.__seg_)); __n -= __nw * __bits_per_word; // do last word if (__n > 0) { __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n); __storage_type __b = *--__last.__seg_ & __m; *--__result.__seg_ &= ~__m; *__result.__seg_ |= __b; __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); } } return __result; } template <class _Cp, bool _IsConst> _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_backward_unaligned( __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) { using _In = __bit_iterator<_Cp, _IsConst>; using difference_type = typename _In::difference_type; using __storage_type = typename _In::__storage_type; const int __bits_per_word = _In::__bits_per_word; difference_type __n = __last - __first; if (__n > 0) { // do first word if (__last.__ctz_ != 0) { difference_type __dn = std::min(static_cast<difference_type>(__last.__ctz_), __n); __n -= __dn; unsigned __clz_l = __bits_per_word - __last.__ctz_; __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l); __storage_type __b = *__last.__seg_ & __m; unsigned __clz_r = __bits_per_word - __result.__ctz_; __storage_type __ddn = std::min(__dn, static_cast<difference_type>(__result.__ctz_)); if (__ddn > 0) { __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r); *__result.__seg_ &= ~__m; if (__result.__ctz_ > __last.__ctz_) *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); else *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_); __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) + __result.__ctz_) % __bits_per_word); __dn -= __ddn; } if (__dn > 0) { // __result.__ctz_ == 0 --__result.__seg_; __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1)); __m = ~__storage_type(0) << __result.__ctz_; *__result.__seg_ &= ~__m; __last.__ctz_ -= __dn + __ddn; *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); } // __last.__ctz_ = 0 } // __last.__ctz_ == 0 || __n == 0 // __result.__ctz_ != 0 || __n == 0 // do middle words unsigned __clz_r = __bits_per_word - __result.__ctz_; __storage_type __m = ~__storage_type(0) >> __clz_r; for (; __n >= __bits_per_word; __n -= __bits_per_word) { __storage_type __b = *--__last.__seg_; *__result.__seg_ &= ~__m; *__result.__seg_ |= __b >> __clz_r; *--__result.__seg_ &= __m; *__result.__seg_ |= __b << __result.__ctz_; } // do last word if (__n > 0) { __m = ~__storage_type(0) << (__bits_per_word - __n); __storage_type __b = *--__last.__seg_ & __m; __clz_r = __bits_per_word - __result.__ctz_; __storage_type __dn = std::min(__n, static_cast<difference_type>(__result.__ctz_)); __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r); *__result.__seg_ &= ~__m; *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_); __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + __result.__ctz_) % __bits_per_word); __n -= __dn; if (__n > 0) { // __result.__ctz_ == 0 --__result.__seg_; __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); __m = ~__storage_type(0) << __result.__ctz_; *__result.__seg_ &= ~__m; *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn)); } } } return __result; } template <class _Cp, bool _IsConst> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, false> copy_backward( __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) { if (__last.__ctz_ == __result.__ctz_) return std::__copy_backward_aligned(__first, __last, __result); return std::__copy_backward_unaligned(__first, __last, __result); } // move template <class _Cp, bool _IsConst> inline _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> move(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) { return std::copy(__first, __last, __result); } // move_backward template <class _Cp, bool _IsConst> inline _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> move_backward( __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) { return std::copy_backward(__first, __last, __result); } // swap_ranges template <class _Cl, class _Cr> _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cr, false> __swap_ranges_aligned( __bit_iterator<_Cl, false> __first, __bit_iterator<_Cl, false> __last, __bit_iterator<_Cr, false> __result) { using _I1 = __bit_iterator<_Cl, false>; using difference_type = typename _I1::difference_type; using __storage_type = typename _I1::__storage_type; const int __bits_per_word = _I1::__bits_per_word; difference_type __n = __last - __first; if (__n > 0) { // do first word if (__first.__ctz_ != 0) { unsigned __clz = __bits_per_word - __first.__ctz_; difference_type __dn = std::min(static_cast<difference_type>(__clz), __n); __n -= __dn; __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); __storage_type __b1 = *__first.__seg_ & __m; *__first.__seg_ &= ~__m; __storage_type __b2 = *__result.__seg_ & __m; *__result.__seg_ &= ~__m; *__result.__seg_ |= __b1; *__first.__seg_ |= __b2; __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); ++__first.__seg_; // __first.__ctz_ = 0; } // __first.__ctz_ == 0; // do middle words for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_) swap(*__first.__seg_, *__result.__seg_); // do last word if (__n > 0) { __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); __storage_type __b1 = *__first.__seg_ & __m; *__first.__seg_ &= ~__m; __storage_type __b2 = *__result.__seg_ & __m; *__result.__seg_ &= ~__m; *__result.__seg_ |= __b1; *__first.__seg_ |= __b2; __result.__ctz_ = static_cast<unsigned>(__n); } } return __result; } template <class _Cl, class _Cr> _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cr, false> __swap_ranges_unaligned( __bit_iterator<_Cl, false> __first, __bit_iterator<_Cl, false> __last, __bit_iterator<_Cr, false> __result) { using _I1 = __bit_iterator<_Cl, false>; using difference_type = typename _I1::difference_type; using __storage_type = typename _I1::__storage_type; const int __bits_per_word = _I1::__bits_per_word; difference_type __n = __last - __first; if (__n > 0) { // do first word if (__first.__ctz_ != 0) { unsigned __clz_f = __bits_per_word - __first.__ctz_; difference_type __dn = std::min(static_cast<difference_type>(__clz_f), __n); __n -= __dn; __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); __storage_type __b1 = *__first.__seg_ & __m; *__first.__seg_ &= ~__m; unsigned __clz_r = __bits_per_word - __result.__ctz_; __storage_type __ddn = std::min<__storage_type>(__dn, __clz_r); __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); __storage_type __b2 = *__result.__seg_ & __m; *__result.__seg_ &= ~__m; if (__result.__ctz_ > __first.__ctz_) { unsigned __s = __result.__ctz_ - __first.__ctz_; *__result.__seg_ |= __b1 << __s; *__first.__seg_ |= __b2 >> __s; } else { unsigned __s = __first.__ctz_ - __result.__ctz_; *__result.__seg_ |= __b1 >> __s; *__first.__seg_ |= __b2 << __s; } __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); __dn -= __ddn; if (__dn > 0) { __m = ~__storage_type(0) >> (__bits_per_word - __dn); __b2 = *__result.__seg_ & __m; *__result.__seg_ &= ~__m; unsigned __s = __first.__ctz_ + __ddn; *__result.__seg_ |= __b1 >> __s; *__first.__seg_ |= __b2 << __s; __result.__ctz_ = static_cast<unsigned>(__dn); } ++__first.__seg_; // __first.__ctz_ = 0; } // __first.__ctz_ == 0; // do middle words __storage_type __m = ~__storage_type(0) << __result.__ctz_; unsigned __clz_r = __bits_per_word - __result.__ctz_; for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) { __storage_type __b1 = *__first.__seg_; __storage_type __b2 = *__result.__seg_ & __m; *__result.__seg_ &= ~__m; *__result.__seg_ |= __b1 << __result.__ctz_; *__first.__seg_ = __b2 >> __result.__ctz_; ++__result.__seg_; __b2 = *__result.__seg_ & ~__m; *__result.__seg_ &= __m; *__result.__seg_ |= __b1 >> __clz_r; *__first.__seg_ |= __b2 << __clz_r; } // do last word if (__n > 0) { __m = ~__storage_type(0) >> (__bits_per_word - __n); __storage_type __b1 = *__first.__seg_ & __m; *__first.__seg_ &= ~__m; __storage_type __dn = std::min<__storage_type>(__n, __clz_r); __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); __storage_type __b2 = *__result.__seg_ & __m; *__result.__seg_ &= ~__m; *__result.__seg_ |= __b1 << __result.__ctz_; *__first.__seg_ |= __b2 >> __result.__ctz_; __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); __n -= __dn; if (__n > 0) { __m = ~__storage_type(0) >> (__bits_per_word - __n); __b2 = *__result.__seg_ & __m; *__result.__seg_ &= ~__m; *__result.__seg_ |= __b1 >> __dn; *__first.__seg_ |= __b2 << __dn; __result.__ctz_ = static_cast<unsigned>(__n); } } } return __result; } template <class _Cl, class _Cr> inline _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cr, false> swap_ranges( __bit_iterator<_Cl, false> __first1, __bit_iterator<_Cl, false> __last1, __bit_iterator<_Cr, false> __first2) { if (__first1.__ctz_ == __first2.__ctz_) return std::__swap_ranges_aligned(__first1, __last1, __first2); return std::__swap_ranges_unaligned(__first1, __last1, __first2); } // rotate template <class _Cp> struct __bit_array { using difference_type = typename _Cp::difference_type; using __storage_type = typename _Cp::__storage_type; using __storage_pointer = typename _Cp::__storage_pointer; using iterator = typename _Cp::iterator; static const unsigned __bits_per_word = _Cp::__bits_per_word; static const unsigned _Np = 4; difference_type __size_; __storage_type __word_[_Np]; _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static difference_type capacity() { return static_cast<difference_type>(_Np * __bits_per_word); } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit __bit_array(difference_type __s) : __size_(__s) { if (__libcpp_is_constant_evaluated()) { for (size_t __i = 0; __i != __bit_array<_Cp>::_Np; ++__i) std::__construct_at(__word_ + __i, 0); } } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator begin() { return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]), 0); } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator end() { return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]) + __size_ / __bits_per_word, static_cast<unsigned>(__size_ % __bits_per_word)); } }; template <class _Cp> _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> rotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last) { using _I1 = __bit_iterator<_Cp, false>; using difference_type = typename _I1::difference_type; difference_type __d1 = __middle - __first; difference_type __d2 = __last - __middle; _I1 __r = __first + __d2; while (__d1 != 0 && __d2 != 0) { if (__d1 <= __d2) { if (__d1 <= __bit_array<_Cp>::capacity()) { __bit_array<_Cp> __b(__d1); std::copy(__first, __middle, __b.begin()); std::copy(__b.begin(), __b.end(), std::copy(__middle, __last, __first)); break; } else { __bit_iterator<_Cp, false> __mp = std::swap_ranges(__first, __middle, __middle); __first = __middle; __middle = __mp; __d2 -= __d1; } } else { if (__d2 <= __bit_array<_Cp>::capacity()) { __bit_array<_Cp> __b(__d2); std::copy(__middle, __last, __b.begin()); std::copy_backward(__b.begin(), __b.end(), std::copy_backward(__first, __middle, __last)); break; } else { __bit_iterator<_Cp, false> __mp = __first + __d2; std::swap_ranges(__first, __mp, __middle); __first = __mp; __d1 -= __d2; } } } return __r; } // equal template <class _Cp, bool _IC1, bool _IC2> _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool __equal_unaligned( __bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) { using _It = __bit_iterator<_Cp, _IC1>; using difference_type = typename _It::difference_type; using __storage_type = typename _It::__storage_type; const int __bits_per_word = _It::__bits_per_word; difference_type __n = __last1 - __first1; if (__n > 0) { // do first word if (__first1.__ctz_ != 0) { unsigned __clz_f = __bits_per_word - __first1.__ctz_; difference_type __dn = std::min(static_cast<difference_type>(__clz_f), __n); __n -= __dn; __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); __storage_type __b = *__first1.__seg_ & __m; unsigned __clz_r = __bits_per_word - __first2.__ctz_; __storage_type __ddn = std::min<__storage_type>(__dn, __clz_r); __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); if (__first2.__ctz_ > __first1.__ctz_) { if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_))) return false; } else { if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_))) return false; } __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word; __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word); __dn -= __ddn; if (__dn > 0) { __m = ~__storage_type(0) >> (__bits_per_word - __dn); if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn))) return false; __first2.__ctz_ = static_cast<unsigned>(__dn); } ++__first1.__seg_; // __first1.__ctz_ = 0; } // __first1.__ctz_ == 0; // do middle words unsigned __clz_r = __bits_per_word - __first2.__ctz_; __storage_type __m = ~__storage_type(0) << __first2.__ctz_; for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_) { __storage_type __b = *__first1.__seg_; if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) return false; ++__first2.__seg_; if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r)) return false; } // do last word if (__n > 0) { __m = ~__storage_type(0) >> (__bits_per_word - __n); __storage_type __b = *__first1.__seg_ & __m; __storage_type __dn = std::min(__n, static_cast<difference_type>(__clz_r)); __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) return false; __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word; __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word); __n -= __dn; if (__n > 0) { __m = ~__storage_type(0) >> (__bits_per_word - __n); if ((*__first2.__seg_ & __m) != (__b >> __dn)) return false; } } } return true; } template <class _Cp, bool _IC1, bool _IC2> _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool __equal_aligned( __bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) { using _It = __bit_iterator<_Cp, _IC1>; using difference_type = typename _It::difference_type; using __storage_type = typename _It::__storage_type; const int __bits_per_word = _It::__bits_per_word; difference_type __n = __last1 - __first1; if (__n > 0) { // do first word if (__first1.__ctz_ != 0) { unsigned __clz = __bits_per_word - __first1.__ctz_; difference_type __dn = std::min(static_cast<difference_type>(__clz), __n); __n -= __dn; __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) return false; ++__first2.__seg_; ++__first1.__seg_; // __first1.__ctz_ = 0; // __first2.__ctz_ = 0; } // __first1.__ctz_ == 0; // __first2.__ctz_ == 0; // do middle words for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_) if (*__first2.__seg_ != *__first1.__seg_) return false; // do last word if (__n > 0) { __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) return false; } } return true; } template <class _Cp, bool _IC1, bool _IC2> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool equal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) { if (__first1.__ctz_ == __first2.__ctz_) return std::__equal_aligned(__first1, __last1, __first2); return std::__equal_unaligned(__first1, __last1, __first2); } template <class _Cp, bool _IsConst, typename _Cp::__storage_type> class __bit_iterator { public: using difference_type = typename _Cp::difference_type; using value_type = bool; using pointer = __bit_iterator; #ifndef _LIBCPP_ABI_BITSET_VECTOR_BOOL_CONST_SUBSCRIPT_RETURN_BOOL using reference = __conditional_t<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >; #else using reference = __conditional_t<_IsConst, bool, __bit_reference<_Cp> >; #endif using iterator_category = random_access_iterator_tag; private: using __storage_type = typename _Cp::__storage_type; using __storage_pointer = __conditional_t<_IsConst, typename _Cp::__const_storage_pointer, typename _Cp::__storage_pointer>; static const unsigned __bits_per_word = _Cp::__bits_per_word; __storage_pointer __seg_; unsigned __ctz_; public: _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator() _NOEXCEPT #if _LIBCPP_STD_VER >= 14 : __seg_(nullptr), __ctz_(0) #endif { } // When _IsConst=false, this is the copy constructor. // It is non-trivial. Making it trivial would break ABI. // When _IsConst=true, this is a converting constructor; // the copy and move constructors are implicitly generated // and trivial. _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {} // When _IsConst=false, we have a user-provided copy constructor, // so we must also provide a copy assignment operator because // the implicit generation of a defaulted one is deprecated. // When _IsConst=true, the assignment operators are // implicitly generated and trivial. _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator=(const _If<_IsConst, struct __private_nat, __bit_iterator>& __it) { __seg_ = __it.__seg_; __ctz_ = __it.__ctz_; return *this; } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference operator*() const _NOEXCEPT { return __conditional_t<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >( __seg_, __storage_type(1) << __ctz_); } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator++() { if (__ctz_ != __bits_per_word - 1) ++__ctz_; else { __ctz_ = 0; ++__seg_; } return *this; } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator++(int) { __bit_iterator __tmp = *this; ++(*this); return __tmp; } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator--() { if (__ctz_ != 0) --__ctz_; else { __ctz_ = __bits_per_word - 1; --__seg_; } return *this; } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator--(int) { __bit_iterator __tmp = *this; --(*this); return __tmp; } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator+=(difference_type __n) { if (__n >= 0) __seg_ += (__n + __ctz_) / __bits_per_word; else __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1) / static_cast<difference_type>(__bits_per_word); __n &= (__bits_per_word - 1); __ctz_ = static_cast<unsigned>((__n + __ctz_) % __bits_per_word); return *this; } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator-=(difference_type __n) { return *this += -__n; } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator+(difference_type __n) const { __bit_iterator __t(*this); __t += __n; return __t; } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator-(difference_type __n) const { __bit_iterator __t(*this); __t -= __n; return __t; } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator operator+(difference_type __n, const __bit_iterator& __it) { return __it + __n; } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend difference_type operator-(const __bit_iterator& __x, const __bit_iterator& __y) { return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_; } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference operator[](difference_type __n) const { return *(*this + __n); } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool operator==(const __bit_iterator& __x, const __bit_iterator& __y) { return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_; } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool operator!=(const __bit_iterator& __x, const __bit_iterator& __y) { return !(__x == __y); } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool operator<(const __bit_iterator& __x, const __bit_iterator& __y) { return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_); } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool operator>(const __bit_iterator& __x, const __bit_iterator& __y) { return __y < __x; } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y) { return !(__y < __x); } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y) { return !(__x < __y); } private: _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit __bit_iterator( __storage_pointer __s, unsigned __ctz) _NOEXCEPT : __seg_(__s), __ctz_(__ctz) {} friend typename _Cp::__self; friend class __bit_reference<_Cp>; friend class __bit_const_reference<_Cp>; friend class __bit_iterator<_Cp, true>; template <class _Dp> friend struct __bit_array; template <bool _FillVal, class _Dp> _LIBCPP_CONSTEXPR_SINCE_CXX20 friend void __fill_n(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); template <class _Dp, bool _IC> _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> __copy_aligned( __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result); template <class _Dp, bool _IC> _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> __copy_unaligned( __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result); template <class _Dp, bool _IC> _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> copy(__bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result); template <class _Dp, bool _IC> _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> __copy_backward_aligned( __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result); template <class _Dp, bool _IC> _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> __copy_backward_unaligned( __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result); template <class _Dp, bool _IC> _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> copy_backward(__bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result); template <class _Cl, class _Cr> friend __bit_iterator<_Cr, false> __swap_ranges_aligned(__bit_iterator<_Cl, false>, __bit_iterator<_Cl, false>, __bit_iterator<_Cr, false>); template <class _Cl, class _Cr> friend __bit_iterator<_Cr, false> __swap_ranges_unaligned(__bit_iterator<_Cl, false>, __bit_iterator<_Cl, false>, __bit_iterator<_Cr, false>); template <class _Cl, class _Cr> friend __bit_iterator<_Cr, false> swap_ranges(__bit_iterator<_Cl, false>, __bit_iterator<_Cl, false>, __bit_iterator<_Cr, false>); template <class _Dp> _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> rotate(__bit_iterator<_Dp, false>, __bit_iterator<_Dp, false>, __bit_iterator<_Dp, false>); template <class _Dp, bool _IC1, bool _IC2> _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool __equal_aligned(__bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC2>); template <class _Dp, bool _IC1, bool _IC2> _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool __equal_unaligned(__bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC2>); template <class _Dp, bool _IC1, bool _IC2> _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool equal(__bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC2>); template <bool _ToFind, class _Dp, bool _IC> _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, _IC> __find_bool(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); template <bool _ToCount, class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __count_bool(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); }; _LIBCPP_END_NAMESPACE_STD _LIBCPP_POP_MACROS #endif // _LIBCPP___BIT_REFERENCE