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> 16*bdd1243dSDimitry Andric#include <__bit/countr.h> 17*bdd1243dSDimitry Andric#include <__bit/popcount.h> 1804eeddc0SDimitry Andric#include <__config> 1981ad6265SDimitry Andric#include <__iterator/iterator_traits.h> 2061cfbce3SDimitry Andric#include <__memory/construct_at.h> 2181ad6265SDimitry Andric#include <__memory/pointer_traits.h> 2281ad6265SDimitry Andric#include <cstring> 2381ad6265SDimitry Andric#include <type_traits> 240b57cec5SDimitry Andric 250b57cec5SDimitry Andric#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 260b57cec5SDimitry Andric# pragma GCC system_header 270b57cec5SDimitry Andric#endif 280b57cec5SDimitry Andric 290b57cec5SDimitry Andric_LIBCPP_PUSH_MACROS 300b57cec5SDimitry Andric#include <__undef_macros> 310b57cec5SDimitry Andric 320b57cec5SDimitry Andric 330b57cec5SDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD 340b57cec5SDimitry Andric 350b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst, typename _Cp::__storage_type = 0> class __bit_iterator; 360b57cec5SDimitry Andrictemplate <class _Cp> class __bit_const_reference; 370b57cec5SDimitry Andric 380b57cec5SDimitry Andrictemplate <class _Tp> 390b57cec5SDimitry Andricstruct __has_storage_type 400b57cec5SDimitry Andric{ 410b57cec5SDimitry Andric static const bool value = false; 420b57cec5SDimitry Andric}; 430b57cec5SDimitry Andric 440b57cec5SDimitry Andrictemplate <class _Cp, bool = __has_storage_type<_Cp>::value> 450b57cec5SDimitry Andricclass __bit_reference 460b57cec5SDimitry Andric{ 470b57cec5SDimitry Andric typedef typename _Cp::__storage_type __storage_type; 480b57cec5SDimitry Andric typedef typename _Cp::__storage_pointer __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>; 570b57cec5SDimitry Andricpublic: 58*bdd1243dSDimitry Andric using __container = typename _Cp::__self; 59*bdd1243dSDimitry Andric 60*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 61480093f4SDimitry Andric __bit_reference(const __bit_reference&) = default; 62480093f4SDimitry Andric 63*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 operator bool() const _NOEXCEPT 640b57cec5SDimitry Andric {return static_cast<bool>(*__seg_ & __mask_);} 65*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 bool operator ~() const _NOEXCEPT 660b57cec5SDimitry Andric {return !static_cast<bool>(*this);} 670b57cec5SDimitry Andric 68*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 690b57cec5SDimitry Andric __bit_reference& operator=(bool __x) _NOEXCEPT 700b57cec5SDimitry Andric { 710b57cec5SDimitry Andric if (__x) 720b57cec5SDimitry Andric *__seg_ |= __mask_; 730b57cec5SDimitry Andric else 740b57cec5SDimitry Andric *__seg_ &= ~__mask_; 750b57cec5SDimitry Andric return *this; 760b57cec5SDimitry Andric } 770b57cec5SDimitry Andric 7881ad6265SDimitry Andric#if _LIBCPP_STD_VER > 20 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 88*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 890b57cec5SDimitry Andric __bit_reference& operator=(const __bit_reference& __x) _NOEXCEPT 900b57cec5SDimitry Andric {return operator=(static_cast<bool>(__x));} 910b57cec5SDimitry Andric 92*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 void flip() _NOEXCEPT {*__seg_ ^= __mask_;} 93*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, false> operator&() const _NOEXCEPT 94*bdd1243dSDimitry Andric {return __bit_iterator<_Cp, false>(__seg_, static_cast<unsigned>(std::__libcpp_ctz(__mask_)));} 950b57cec5SDimitry Andricprivate: 96*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 9781ad6265SDimitry Andric explicit __bit_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT 980b57cec5SDimitry Andric : __seg_(__s), __mask_(__m) {} 990b57cec5SDimitry Andric}; 1000b57cec5SDimitry Andric 1010b57cec5SDimitry Andrictemplate <class _Cp> 1020b57cec5SDimitry Andricclass __bit_reference<_Cp, false> 1030b57cec5SDimitry Andric{ 1040b57cec5SDimitry Andric}; 1050b57cec5SDimitry Andric 1060b57cec5SDimitry Andrictemplate <class _Cp> 107*bdd1243dSDimitry Andricinline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 1080b57cec5SDimitry Andricvoid 1090b57cec5SDimitry Andricswap(__bit_reference<_Cp> __x, __bit_reference<_Cp> __y) _NOEXCEPT 1100b57cec5SDimitry Andric{ 1110b57cec5SDimitry Andric bool __t = __x; 1120b57cec5SDimitry Andric __x = __y; 1130b57cec5SDimitry Andric __y = __t; 1140b57cec5SDimitry Andric} 1150b57cec5SDimitry Andric 1160b57cec5SDimitry Andrictemplate <class _Cp, class _Dp> 117*bdd1243dSDimitry Andricinline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 1180b57cec5SDimitry Andricvoid 1190b57cec5SDimitry Andricswap(__bit_reference<_Cp> __x, __bit_reference<_Dp> __y) _NOEXCEPT 1200b57cec5SDimitry Andric{ 1210b57cec5SDimitry Andric bool __t = __x; 1220b57cec5SDimitry Andric __x = __y; 1230b57cec5SDimitry Andric __y = __t; 1240b57cec5SDimitry Andric} 1250b57cec5SDimitry Andric 1260b57cec5SDimitry Andrictemplate <class _Cp> 127*bdd1243dSDimitry Andricinline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 1280b57cec5SDimitry Andricvoid 1290b57cec5SDimitry Andricswap(__bit_reference<_Cp> __x, bool& __y) _NOEXCEPT 1300b57cec5SDimitry Andric{ 1310b57cec5SDimitry Andric bool __t = __x; 1320b57cec5SDimitry Andric __x = __y; 1330b57cec5SDimitry Andric __y = __t; 1340b57cec5SDimitry Andric} 1350b57cec5SDimitry Andric 1360b57cec5SDimitry Andrictemplate <class _Cp> 137*bdd1243dSDimitry Andricinline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 1380b57cec5SDimitry Andricvoid 1390b57cec5SDimitry Andricswap(bool& __x, __bit_reference<_Cp> __y) _NOEXCEPT 1400b57cec5SDimitry Andric{ 1410b57cec5SDimitry Andric bool __t = __x; 1420b57cec5SDimitry Andric __x = __y; 1430b57cec5SDimitry Andric __y = __t; 1440b57cec5SDimitry Andric} 1450b57cec5SDimitry Andric 1460b57cec5SDimitry Andrictemplate <class _Cp> 1470b57cec5SDimitry Andricclass __bit_const_reference 1480b57cec5SDimitry Andric{ 1490b57cec5SDimitry Andric typedef typename _Cp::__storage_type __storage_type; 1500b57cec5SDimitry Andric typedef typename _Cp::__const_storage_pointer __storage_pointer; 1510b57cec5SDimitry Andric 1520b57cec5SDimitry Andric __storage_pointer __seg_; 1530b57cec5SDimitry Andric __storage_type __mask_; 1540b57cec5SDimitry Andric 1550b57cec5SDimitry Andric friend typename _Cp::__self; 1560b57cec5SDimitry Andric friend class __bit_iterator<_Cp, true>; 1570b57cec5SDimitry Andricpublic: 1580b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 159480093f4SDimitry Andric __bit_const_reference(const __bit_const_reference&) = default; 160480093f4SDimitry Andric 161*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 1620b57cec5SDimitry Andric __bit_const_reference(const __bit_reference<_Cp>& __x) _NOEXCEPT 1630b57cec5SDimitry Andric : __seg_(__x.__seg_), __mask_(__x.__mask_) {} 1640b57cec5SDimitry Andric 1650b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR operator bool() const _NOEXCEPT 1660b57cec5SDimitry Andric {return static_cast<bool>(*__seg_ & __mask_);} 1670b57cec5SDimitry Andric 168*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, true> operator&() const _NOEXCEPT 169*bdd1243dSDimitry Andric {return __bit_iterator<_Cp, true>(__seg_, static_cast<unsigned>(std::__libcpp_ctz(__mask_)));} 1700b57cec5SDimitry Andricprivate: 1710b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 1720b57cec5SDimitry Andric _LIBCPP_CONSTEXPR 17381ad6265SDimitry Andric explicit __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT 1740b57cec5SDimitry Andric : __seg_(__s), __mask_(__m) {} 1750b57cec5SDimitry Andric 176480093f4SDimitry Andric __bit_const_reference& operator=(const __bit_const_reference&) = delete; 1770b57cec5SDimitry Andric}; 1780b57cec5SDimitry Andric 1790b57cec5SDimitry Andric// find 1800b57cec5SDimitry Andric 1810b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 182*bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, _IsConst> 1830b57cec5SDimitry Andric__find_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 1840b57cec5SDimitry Andric{ 1850b57cec5SDimitry Andric typedef __bit_iterator<_Cp, _IsConst> _It; 1860b57cec5SDimitry Andric typedef typename _It::__storage_type __storage_type; 18761cfbce3SDimitry Andric const int __bits_per_word = _It::__bits_per_word; 1880b57cec5SDimitry Andric // do first partial word 1890b57cec5SDimitry Andric if (__first.__ctz_ != 0) 1900b57cec5SDimitry Andric { 1910b57cec5SDimitry Andric __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 1920b57cec5SDimitry Andric __storage_type __dn = _VSTD::min(__clz_f, __n); 1930b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 1940b57cec5SDimitry Andric __storage_type __b = *__first.__seg_ & __m; 1950b57cec5SDimitry Andric if (__b) 1960b57cec5SDimitry Andric return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b))); 1970b57cec5SDimitry Andric if (__n == __dn) 1980b57cec5SDimitry Andric return __first + __n; 1990b57cec5SDimitry Andric __n -= __dn; 2000b57cec5SDimitry Andric ++__first.__seg_; 2010b57cec5SDimitry Andric } 2020b57cec5SDimitry Andric // do middle whole words 2030b57cec5SDimitry Andric for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 2040b57cec5SDimitry Andric if (*__first.__seg_) 2050b57cec5SDimitry Andric return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(*__first.__seg_))); 2060b57cec5SDimitry Andric // do last partial word 2070b57cec5SDimitry Andric if (__n > 0) 2080b57cec5SDimitry Andric { 2090b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 2100b57cec5SDimitry Andric __storage_type __b = *__first.__seg_ & __m; 2110b57cec5SDimitry Andric if (__b) 2120b57cec5SDimitry Andric return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b))); 2130b57cec5SDimitry Andric } 2140b57cec5SDimitry Andric return _It(__first.__seg_, static_cast<unsigned>(__n)); 2150b57cec5SDimitry Andric} 2160b57cec5SDimitry Andric 2170b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 218*bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, _IsConst> 2190b57cec5SDimitry Andric__find_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 2200b57cec5SDimitry Andric{ 2210b57cec5SDimitry Andric typedef __bit_iterator<_Cp, _IsConst> _It; 2220b57cec5SDimitry Andric typedef typename _It::__storage_type __storage_type; 2230b57cec5SDimitry Andric const int __bits_per_word = _It::__bits_per_word; 2240b57cec5SDimitry Andric // do first partial word 2250b57cec5SDimitry Andric if (__first.__ctz_ != 0) 2260b57cec5SDimitry Andric { 2270b57cec5SDimitry Andric __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 2280b57cec5SDimitry Andric __storage_type __dn = _VSTD::min(__clz_f, __n); 2290b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 2300b57cec5SDimitry Andric __storage_type __b = ~*__first.__seg_ & __m; 2310b57cec5SDimitry Andric if (__b) 2320b57cec5SDimitry Andric return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b))); 2330b57cec5SDimitry Andric if (__n == __dn) 2340b57cec5SDimitry Andric return __first + __n; 2350b57cec5SDimitry Andric __n -= __dn; 2360b57cec5SDimitry Andric ++__first.__seg_; 2370b57cec5SDimitry Andric } 2380b57cec5SDimitry Andric // do middle whole words 2390b57cec5SDimitry Andric for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 2400b57cec5SDimitry Andric { 2410b57cec5SDimitry Andric __storage_type __b = ~*__first.__seg_; 2420b57cec5SDimitry Andric if (__b) 2430b57cec5SDimitry Andric return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b))); 2440b57cec5SDimitry Andric } 2450b57cec5SDimitry Andric // do last partial word 2460b57cec5SDimitry Andric if (__n > 0) 2470b57cec5SDimitry Andric { 2480b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 2490b57cec5SDimitry Andric __storage_type __b = ~*__first.__seg_ & __m; 2500b57cec5SDimitry Andric if (__b) 2510b57cec5SDimitry Andric return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b))); 2520b57cec5SDimitry Andric } 2530b57cec5SDimitry Andric return _It(__first.__seg_, static_cast<unsigned>(__n)); 2540b57cec5SDimitry Andric} 2550b57cec5SDimitry Andric 2560b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst, class _Tp> 257*bdd1243dSDimitry Andricinline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 2580b57cec5SDimitry Andric__bit_iterator<_Cp, _IsConst> 259753f127fSDimitry Andricfind(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value) 2600b57cec5SDimitry Andric{ 261753f127fSDimitry Andric if (static_cast<bool>(__value)) 262e8d8bef9SDimitry Andric return _VSTD::__find_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first)); 263e8d8bef9SDimitry Andric return _VSTD::__find_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first)); 2640b57cec5SDimitry Andric} 2650b57cec5SDimitry Andric 2660b57cec5SDimitry Andric// count 2670b57cec5SDimitry Andric 2680b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 269*bdd1243dSDimitry Andric_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 typename __bit_iterator<_Cp, _IsConst>::difference_type 2700b57cec5SDimitry Andric__count_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 2710b57cec5SDimitry Andric{ 2720b57cec5SDimitry Andric typedef __bit_iterator<_Cp, _IsConst> _It; 2730b57cec5SDimitry Andric typedef typename _It::__storage_type __storage_type; 2740b57cec5SDimitry Andric typedef typename _It::difference_type difference_type; 2750b57cec5SDimitry Andric const int __bits_per_word = _It::__bits_per_word; 2760b57cec5SDimitry Andric difference_type __r = 0; 2770b57cec5SDimitry Andric // do first partial word 2780b57cec5SDimitry Andric if (__first.__ctz_ != 0) 2790b57cec5SDimitry Andric { 2800b57cec5SDimitry Andric __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 2810b57cec5SDimitry Andric __storage_type __dn = _VSTD::min(__clz_f, __n); 2820b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 2830b57cec5SDimitry Andric __r = _VSTD::__libcpp_popcount(*__first.__seg_ & __m); 2840b57cec5SDimitry Andric __n -= __dn; 2850b57cec5SDimitry Andric ++__first.__seg_; 2860b57cec5SDimitry Andric } 2870b57cec5SDimitry Andric // do middle whole words 2880b57cec5SDimitry Andric for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 2890b57cec5SDimitry Andric __r += _VSTD::__libcpp_popcount(*__first.__seg_); 2900b57cec5SDimitry Andric // do last partial word 2910b57cec5SDimitry Andric if (__n > 0) 2920b57cec5SDimitry Andric { 2930b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 2940b57cec5SDimitry Andric __r += _VSTD::__libcpp_popcount(*__first.__seg_ & __m); 2950b57cec5SDimitry Andric } 2960b57cec5SDimitry Andric return __r; 2970b57cec5SDimitry Andric} 2980b57cec5SDimitry Andric 2990b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 300*bdd1243dSDimitry Andric_LIBCPP_HIDE_FROM_ABI typename __bit_iterator<_Cp, _IsConst>::difference_type 3010b57cec5SDimitry Andric__count_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 3020b57cec5SDimitry Andric{ 3030b57cec5SDimitry Andric typedef __bit_iterator<_Cp, _IsConst> _It; 3040b57cec5SDimitry Andric typedef typename _It::__storage_type __storage_type; 3050b57cec5SDimitry Andric typedef typename _It::difference_type difference_type; 3060b57cec5SDimitry Andric const int __bits_per_word = _It::__bits_per_word; 3070b57cec5SDimitry Andric difference_type __r = 0; 3080b57cec5SDimitry Andric // do first partial word 3090b57cec5SDimitry Andric if (__first.__ctz_ != 0) 3100b57cec5SDimitry Andric { 3110b57cec5SDimitry Andric __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 3120b57cec5SDimitry Andric __storage_type __dn = _VSTD::min(__clz_f, __n); 3130b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 3140b57cec5SDimitry Andric __r = _VSTD::__libcpp_popcount(~*__first.__seg_ & __m); 3150b57cec5SDimitry Andric __n -= __dn; 3160b57cec5SDimitry Andric ++__first.__seg_; 3170b57cec5SDimitry Andric } 3180b57cec5SDimitry Andric // do middle whole words 3190b57cec5SDimitry Andric for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 3200b57cec5SDimitry Andric __r += _VSTD::__libcpp_popcount(~*__first.__seg_); 3210b57cec5SDimitry Andric // do last partial word 3220b57cec5SDimitry Andric if (__n > 0) 3230b57cec5SDimitry Andric { 3240b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 3250b57cec5SDimitry Andric __r += _VSTD::__libcpp_popcount(~*__first.__seg_ & __m); 3260b57cec5SDimitry Andric } 3270b57cec5SDimitry Andric return __r; 3280b57cec5SDimitry Andric} 3290b57cec5SDimitry Andric 3300b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst, class _Tp> 3310b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 3320b57cec5SDimitry Andrictypename __bit_iterator<_Cp, _IsConst>::difference_type 333753f127fSDimitry Andriccount(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value) 3340b57cec5SDimitry Andric{ 335753f127fSDimitry Andric if (static_cast<bool>(__value)) 336e8d8bef9SDimitry Andric return _VSTD::__count_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first)); 337e8d8bef9SDimitry Andric return _VSTD::__count_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first)); 3380b57cec5SDimitry Andric} 3390b57cec5SDimitry Andric 3400b57cec5SDimitry Andric// fill_n 3410b57cec5SDimitry Andric 3420b57cec5SDimitry Andrictemplate <class _Cp> 343*bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void 3440b57cec5SDimitry Andric__fill_n_false(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) 3450b57cec5SDimitry Andric{ 3460b57cec5SDimitry Andric typedef __bit_iterator<_Cp, false> _It; 3470b57cec5SDimitry Andric typedef typename _It::__storage_type __storage_type; 3480b57cec5SDimitry Andric const int __bits_per_word = _It::__bits_per_word; 3490b57cec5SDimitry Andric // do first partial word 3500b57cec5SDimitry Andric if (__first.__ctz_ != 0) 3510b57cec5SDimitry Andric { 3520b57cec5SDimitry Andric __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 3530b57cec5SDimitry Andric __storage_type __dn = _VSTD::min(__clz_f, __n); 3540b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 3550b57cec5SDimitry Andric *__first.__seg_ &= ~__m; 3560b57cec5SDimitry Andric __n -= __dn; 3570b57cec5SDimitry Andric ++__first.__seg_; 3580b57cec5SDimitry Andric } 3590b57cec5SDimitry Andric // do middle whole words 3600b57cec5SDimitry Andric __storage_type __nw = __n / __bits_per_word; 36161cfbce3SDimitry Andric std::fill_n(std::__to_address(__first.__seg_), __nw, 0); 3620b57cec5SDimitry Andric __n -= __nw * __bits_per_word; 3630b57cec5SDimitry Andric // do last partial word 3640b57cec5SDimitry Andric if (__n > 0) 3650b57cec5SDimitry Andric { 3660b57cec5SDimitry Andric __first.__seg_ += __nw; 3670b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 3680b57cec5SDimitry Andric *__first.__seg_ &= ~__m; 3690b57cec5SDimitry Andric } 3700b57cec5SDimitry Andric} 3710b57cec5SDimitry Andric 3720b57cec5SDimitry Andrictemplate <class _Cp> 373*bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void 3740b57cec5SDimitry Andric__fill_n_true(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) 3750b57cec5SDimitry Andric{ 3760b57cec5SDimitry Andric typedef __bit_iterator<_Cp, false> _It; 3770b57cec5SDimitry Andric typedef typename _It::__storage_type __storage_type; 3780b57cec5SDimitry Andric const int __bits_per_word = _It::__bits_per_word; 3790b57cec5SDimitry Andric // do first partial word 3800b57cec5SDimitry Andric if (__first.__ctz_ != 0) 3810b57cec5SDimitry Andric { 3820b57cec5SDimitry Andric __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 3830b57cec5SDimitry Andric __storage_type __dn = _VSTD::min(__clz_f, __n); 3840b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 3850b57cec5SDimitry Andric *__first.__seg_ |= __m; 3860b57cec5SDimitry Andric __n -= __dn; 3870b57cec5SDimitry Andric ++__first.__seg_; 3880b57cec5SDimitry Andric } 3890b57cec5SDimitry Andric // do middle whole words 3900b57cec5SDimitry Andric __storage_type __nw = __n / __bits_per_word; 39161cfbce3SDimitry Andric // __storage_type is always an unsigned type, so -1 sets all bits 39261cfbce3SDimitry Andric std::fill_n(std::__to_address(__first.__seg_), __nw, static_cast<__storage_type>(-1)); 3930b57cec5SDimitry Andric __n -= __nw * __bits_per_word; 3940b57cec5SDimitry Andric // do last partial word 3950b57cec5SDimitry Andric if (__n > 0) 3960b57cec5SDimitry Andric { 3970b57cec5SDimitry Andric __first.__seg_ += __nw; 3980b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 3990b57cec5SDimitry Andric *__first.__seg_ |= __m; 4000b57cec5SDimitry Andric } 4010b57cec5SDimitry Andric} 4020b57cec5SDimitry Andric 4030b57cec5SDimitry Andrictemplate <class _Cp> 404*bdd1243dSDimitry Andricinline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 4050b57cec5SDimitry Andricvoid 406753f127fSDimitry Andricfill_n(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n, bool __value) 4070b57cec5SDimitry Andric{ 4080b57cec5SDimitry Andric if (__n > 0) 4090b57cec5SDimitry Andric { 410753f127fSDimitry Andric if (__value) 411e8d8bef9SDimitry Andric _VSTD::__fill_n_true(__first, __n); 4120b57cec5SDimitry Andric else 413e8d8bef9SDimitry Andric _VSTD::__fill_n_false(__first, __n); 4140b57cec5SDimitry Andric } 4150b57cec5SDimitry Andric} 4160b57cec5SDimitry Andric 4170b57cec5SDimitry Andric// fill 4180b57cec5SDimitry Andric 4190b57cec5SDimitry Andrictemplate <class _Cp> 420*bdd1243dSDimitry Andricinline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 4210b57cec5SDimitry Andricvoid 422753f127fSDimitry Andricfill(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __last, bool __value) 4230b57cec5SDimitry Andric{ 424753f127fSDimitry Andric _VSTD::fill_n(__first, static_cast<typename _Cp::size_type>(__last - __first), __value); 4250b57cec5SDimitry Andric} 4260b57cec5SDimitry Andric 4270b57cec5SDimitry Andric// copy 4280b57cec5SDimitry Andric 4290b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 430*bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> 4310b57cec5SDimitry Andric__copy_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 4320b57cec5SDimitry Andric __bit_iterator<_Cp, false> __result) 4330b57cec5SDimitry Andric{ 4340b57cec5SDimitry Andric typedef __bit_iterator<_Cp, _IsConst> _In; 4350b57cec5SDimitry Andric typedef typename _In::difference_type difference_type; 4360b57cec5SDimitry Andric typedef typename _In::__storage_type __storage_type; 4370b57cec5SDimitry Andric const int __bits_per_word = _In::__bits_per_word; 4380b57cec5SDimitry Andric difference_type __n = __last - __first; 4390b57cec5SDimitry Andric if (__n > 0) 4400b57cec5SDimitry Andric { 4410b57cec5SDimitry Andric // do first word 4420b57cec5SDimitry Andric if (__first.__ctz_ != 0) 4430b57cec5SDimitry Andric { 4440b57cec5SDimitry Andric unsigned __clz = __bits_per_word - __first.__ctz_; 4450b57cec5SDimitry Andric difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 4460b57cec5SDimitry Andric __n -= __dn; 4470b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 4480b57cec5SDimitry Andric __storage_type __b = *__first.__seg_ & __m; 4490b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 4500b57cec5SDimitry Andric *__result.__seg_ |= __b; 4510b57cec5SDimitry Andric __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 4520b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 4530b57cec5SDimitry Andric ++__first.__seg_; 4540b57cec5SDimitry Andric // __first.__ctz_ = 0; 4550b57cec5SDimitry Andric } 4560b57cec5SDimitry Andric // __first.__ctz_ == 0; 4570b57cec5SDimitry Andric // do middle words 4580b57cec5SDimitry Andric __storage_type __nw = __n / __bits_per_word; 45961cfbce3SDimitry Andric std::copy_n(std::__to_address(__first.__seg_), __nw, std::__to_address(__result.__seg_)); 4600b57cec5SDimitry Andric __n -= __nw * __bits_per_word; 4610b57cec5SDimitry Andric __result.__seg_ += __nw; 4620b57cec5SDimitry Andric // do last word 4630b57cec5SDimitry Andric if (__n > 0) 4640b57cec5SDimitry Andric { 4650b57cec5SDimitry Andric __first.__seg_ += __nw; 4660b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 4670b57cec5SDimitry Andric __storage_type __b = *__first.__seg_ & __m; 4680b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 4690b57cec5SDimitry Andric *__result.__seg_ |= __b; 4700b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(__n); 4710b57cec5SDimitry Andric } 4720b57cec5SDimitry Andric } 4730b57cec5SDimitry Andric return __result; 4740b57cec5SDimitry Andric} 4750b57cec5SDimitry Andric 4760b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 477*bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> 4780b57cec5SDimitry Andric__copy_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 4790b57cec5SDimitry Andric __bit_iterator<_Cp, false> __result) 4800b57cec5SDimitry Andric{ 4810b57cec5SDimitry Andric typedef __bit_iterator<_Cp, _IsConst> _In; 4820b57cec5SDimitry Andric typedef typename _In::difference_type difference_type; 4830b57cec5SDimitry Andric typedef typename _In::__storage_type __storage_type; 48461cfbce3SDimitry Andric const int __bits_per_word = _In::__bits_per_word; 4850b57cec5SDimitry Andric difference_type __n = __last - __first; 4860b57cec5SDimitry Andric if (__n > 0) 4870b57cec5SDimitry Andric { 4880b57cec5SDimitry Andric // do first word 4890b57cec5SDimitry Andric if (__first.__ctz_ != 0) 4900b57cec5SDimitry Andric { 4910b57cec5SDimitry Andric unsigned __clz_f = __bits_per_word - __first.__ctz_; 4920b57cec5SDimitry Andric difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 4930b57cec5SDimitry Andric __n -= __dn; 4940b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 4950b57cec5SDimitry Andric __storage_type __b = *__first.__seg_ & __m; 4960b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __result.__ctz_; 4970b57cec5SDimitry Andric __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 4980b57cec5SDimitry Andric __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 4990b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 5000b57cec5SDimitry Andric if (__result.__ctz_ > __first.__ctz_) 5010b57cec5SDimitry Andric *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_); 5020b57cec5SDimitry Andric else 5030b57cec5SDimitry Andric *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_); 5040b57cec5SDimitry Andric __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 5050b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 5060b57cec5SDimitry Andric __dn -= __ddn; 5070b57cec5SDimitry Andric if (__dn > 0) 5080b57cec5SDimitry Andric { 5090b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __dn); 5100b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 5110b57cec5SDimitry Andric *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn); 5120b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(__dn); 5130b57cec5SDimitry Andric } 5140b57cec5SDimitry Andric ++__first.__seg_; 5150b57cec5SDimitry Andric // __first.__ctz_ = 0; 5160b57cec5SDimitry Andric } 5170b57cec5SDimitry Andric // __first.__ctz_ == 0; 5180b57cec5SDimitry Andric // do middle words 5190b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __result.__ctz_; 5200b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) << __result.__ctz_; 5210b57cec5SDimitry Andric for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 5220b57cec5SDimitry Andric { 5230b57cec5SDimitry Andric __storage_type __b = *__first.__seg_; 5240b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 5250b57cec5SDimitry Andric *__result.__seg_ |= __b << __result.__ctz_; 5260b57cec5SDimitry Andric ++__result.__seg_; 5270b57cec5SDimitry Andric *__result.__seg_ &= __m; 5280b57cec5SDimitry Andric *__result.__seg_ |= __b >> __clz_r; 5290b57cec5SDimitry Andric } 5300b57cec5SDimitry Andric // do last word 5310b57cec5SDimitry Andric if (__n > 0) 5320b57cec5SDimitry Andric { 5330b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __n); 5340b57cec5SDimitry Andric __storage_type __b = *__first.__seg_ & __m; 5350b57cec5SDimitry Andric __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); 5360b57cec5SDimitry Andric __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 5370b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 5380b57cec5SDimitry Andric *__result.__seg_ |= __b << __result.__ctz_; 5390b57cec5SDimitry Andric __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 5400b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 5410b57cec5SDimitry Andric __n -= __dn; 5420b57cec5SDimitry Andric if (__n > 0) 5430b57cec5SDimitry Andric { 5440b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __n); 5450b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 5460b57cec5SDimitry Andric *__result.__seg_ |= __b >> __dn; 5470b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(__n); 5480b57cec5SDimitry Andric } 5490b57cec5SDimitry Andric } 5500b57cec5SDimitry Andric } 5510b57cec5SDimitry Andric return __result; 5520b57cec5SDimitry Andric} 5530b57cec5SDimitry Andric 5540b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 555*bdd1243dSDimitry Andricinline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 5560b57cec5SDimitry Andric__bit_iterator<_Cp, false> 5570b57cec5SDimitry Andriccopy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 5580b57cec5SDimitry Andric{ 5590b57cec5SDimitry Andric if (__first.__ctz_ == __result.__ctz_) 560e8d8bef9SDimitry Andric return _VSTD::__copy_aligned(__first, __last, __result); 561e8d8bef9SDimitry Andric return _VSTD::__copy_unaligned(__first, __last, __result); 5620b57cec5SDimitry Andric} 5630b57cec5SDimitry Andric 5640b57cec5SDimitry Andric// copy_backward 5650b57cec5SDimitry Andric 5660b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 567*bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> 5680b57cec5SDimitry Andric__copy_backward_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 5690b57cec5SDimitry Andric __bit_iterator<_Cp, false> __result) 5700b57cec5SDimitry Andric{ 5710b57cec5SDimitry Andric typedef __bit_iterator<_Cp, _IsConst> _In; 5720b57cec5SDimitry Andric typedef typename _In::difference_type difference_type; 5730b57cec5SDimitry Andric typedef typename _In::__storage_type __storage_type; 5740b57cec5SDimitry Andric const int __bits_per_word = _In::__bits_per_word; 5750b57cec5SDimitry Andric difference_type __n = __last - __first; 5760b57cec5SDimitry Andric if (__n > 0) 5770b57cec5SDimitry Andric { 5780b57cec5SDimitry Andric // do first word 5790b57cec5SDimitry Andric if (__last.__ctz_ != 0) 5800b57cec5SDimitry Andric { 5810b57cec5SDimitry Andric difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); 5820b57cec5SDimitry Andric __n -= __dn; 5830b57cec5SDimitry Andric unsigned __clz = __bits_per_word - __last.__ctz_; 5840b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz); 5850b57cec5SDimitry Andric __storage_type __b = *__last.__seg_ & __m; 5860b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 5870b57cec5SDimitry Andric *__result.__seg_ |= __b; 5880b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 5890b57cec5SDimitry Andric __result.__ctz_) % __bits_per_word); 5900b57cec5SDimitry Andric // __last.__ctz_ = 0 5910b57cec5SDimitry Andric } 5920b57cec5SDimitry Andric // __last.__ctz_ == 0 || __n == 0 5930b57cec5SDimitry Andric // __result.__ctz_ == 0 || __n == 0 5940b57cec5SDimitry Andric // do middle words 5950b57cec5SDimitry Andric __storage_type __nw = __n / __bits_per_word; 5960b57cec5SDimitry Andric __result.__seg_ -= __nw; 5970b57cec5SDimitry Andric __last.__seg_ -= __nw; 59861cfbce3SDimitry Andric std::copy_n(std::__to_address(__last.__seg_), __nw, std::__to_address(__result.__seg_)); 5990b57cec5SDimitry Andric __n -= __nw * __bits_per_word; 6000b57cec5SDimitry Andric // do last word 6010b57cec5SDimitry Andric if (__n > 0) 6020b57cec5SDimitry Andric { 6030b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n); 6040b57cec5SDimitry Andric __storage_type __b = *--__last.__seg_ & __m; 6050b57cec5SDimitry Andric *--__result.__seg_ &= ~__m; 6060b57cec5SDimitry Andric *__result.__seg_ |= __b; 6070b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 6080b57cec5SDimitry Andric } 6090b57cec5SDimitry Andric } 6100b57cec5SDimitry Andric return __result; 6110b57cec5SDimitry Andric} 6120b57cec5SDimitry Andric 6130b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 614*bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> 6150b57cec5SDimitry Andric__copy_backward_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 6160b57cec5SDimitry Andric __bit_iterator<_Cp, false> __result) 6170b57cec5SDimitry Andric{ 6180b57cec5SDimitry Andric typedef __bit_iterator<_Cp, _IsConst> _In; 6190b57cec5SDimitry Andric typedef typename _In::difference_type difference_type; 6200b57cec5SDimitry Andric typedef typename _In::__storage_type __storage_type; 6210b57cec5SDimitry Andric const int __bits_per_word = _In::__bits_per_word; 6220b57cec5SDimitry Andric difference_type __n = __last - __first; 6230b57cec5SDimitry Andric if (__n > 0) 6240b57cec5SDimitry Andric { 6250b57cec5SDimitry Andric // do first word 6260b57cec5SDimitry Andric if (__last.__ctz_ != 0) 6270b57cec5SDimitry Andric { 6280b57cec5SDimitry Andric difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); 6290b57cec5SDimitry Andric __n -= __dn; 6300b57cec5SDimitry Andric unsigned __clz_l = __bits_per_word - __last.__ctz_; 6310b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l); 6320b57cec5SDimitry Andric __storage_type __b = *__last.__seg_ & __m; 6330b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __result.__ctz_; 6340b57cec5SDimitry Andric __storage_type __ddn = _VSTD::min(__dn, static_cast<difference_type>(__result.__ctz_)); 6350b57cec5SDimitry Andric if (__ddn > 0) 6360b57cec5SDimitry Andric { 6370b57cec5SDimitry Andric __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r); 6380b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 6390b57cec5SDimitry Andric if (__result.__ctz_ > __last.__ctz_) 6400b57cec5SDimitry Andric *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 6410b57cec5SDimitry Andric else 6420b57cec5SDimitry Andric *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_); 6430b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) + 6440b57cec5SDimitry Andric __result.__ctz_) % __bits_per_word); 6450b57cec5SDimitry Andric __dn -= __ddn; 6460b57cec5SDimitry Andric } 6470b57cec5SDimitry Andric if (__dn > 0) 6480b57cec5SDimitry Andric { 6490b57cec5SDimitry Andric // __result.__ctz_ == 0 6500b57cec5SDimitry Andric --__result.__seg_; 6510b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1)); 6520b57cec5SDimitry Andric __m = ~__storage_type(0) << __result.__ctz_; 6530b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 6540b57cec5SDimitry Andric __last.__ctz_ -= __dn + __ddn; 6550b57cec5SDimitry Andric *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 6560b57cec5SDimitry Andric } 6570b57cec5SDimitry Andric // __last.__ctz_ = 0 6580b57cec5SDimitry Andric } 6590b57cec5SDimitry Andric // __last.__ctz_ == 0 || __n == 0 6600b57cec5SDimitry Andric // __result.__ctz_ != 0 || __n == 0 6610b57cec5SDimitry Andric // do middle words 6620b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __result.__ctz_; 6630b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> __clz_r; 6640b57cec5SDimitry Andric for (; __n >= __bits_per_word; __n -= __bits_per_word) 6650b57cec5SDimitry Andric { 6660b57cec5SDimitry Andric __storage_type __b = *--__last.__seg_; 6670b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 6680b57cec5SDimitry Andric *__result.__seg_ |= __b >> __clz_r; 6690b57cec5SDimitry Andric *--__result.__seg_ &= __m; 6700b57cec5SDimitry Andric *__result.__seg_ |= __b << __result.__ctz_; 6710b57cec5SDimitry Andric } 6720b57cec5SDimitry Andric // do last word 6730b57cec5SDimitry Andric if (__n > 0) 6740b57cec5SDimitry Andric { 6750b57cec5SDimitry Andric __m = ~__storage_type(0) << (__bits_per_word - __n); 6760b57cec5SDimitry Andric __storage_type __b = *--__last.__seg_ & __m; 6770b57cec5SDimitry Andric __clz_r = __bits_per_word - __result.__ctz_; 6780b57cec5SDimitry Andric __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__result.__ctz_)); 6790b57cec5SDimitry Andric __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r); 6800b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 6810b57cec5SDimitry Andric *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_); 6820b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 6830b57cec5SDimitry Andric __result.__ctz_) % __bits_per_word); 6840b57cec5SDimitry Andric __n -= __dn; 6850b57cec5SDimitry Andric if (__n > 0) 6860b57cec5SDimitry Andric { 6870b57cec5SDimitry Andric // __result.__ctz_ == 0 6880b57cec5SDimitry Andric --__result.__seg_; 6890b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 6900b57cec5SDimitry Andric __m = ~__storage_type(0) << __result.__ctz_; 6910b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 6920b57cec5SDimitry Andric *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn)); 6930b57cec5SDimitry Andric } 6940b57cec5SDimitry Andric } 6950b57cec5SDimitry Andric } 6960b57cec5SDimitry Andric return __result; 6970b57cec5SDimitry Andric} 6980b57cec5SDimitry Andric 6990b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 700*bdd1243dSDimitry Andricinline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 7010b57cec5SDimitry Andric__bit_iterator<_Cp, false> 7020b57cec5SDimitry Andriccopy_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 7030b57cec5SDimitry Andric{ 7040b57cec5SDimitry Andric if (__last.__ctz_ == __result.__ctz_) 705e8d8bef9SDimitry Andric return _VSTD::__copy_backward_aligned(__first, __last, __result); 706e8d8bef9SDimitry Andric return _VSTD::__copy_backward_unaligned(__first, __last, __result); 7070b57cec5SDimitry Andric} 7080b57cec5SDimitry Andric 7090b57cec5SDimitry Andric// move 7100b57cec5SDimitry Andric 7110b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 7120b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 7130b57cec5SDimitry Andric__bit_iterator<_Cp, false> 7140b57cec5SDimitry Andricmove(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 7150b57cec5SDimitry Andric{ 7160b57cec5SDimitry Andric return _VSTD::copy(__first, __last, __result); 7170b57cec5SDimitry Andric} 7180b57cec5SDimitry Andric 7190b57cec5SDimitry Andric// move_backward 7200b57cec5SDimitry Andric 7210b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 7220b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 7230b57cec5SDimitry Andric__bit_iterator<_Cp, false> 7240b57cec5SDimitry Andricmove_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 7250b57cec5SDimitry Andric{ 7260b57cec5SDimitry Andric return _VSTD::copy_backward(__first, __last, __result); 7270b57cec5SDimitry Andric} 7280b57cec5SDimitry Andric 7290b57cec5SDimitry Andric// swap_ranges 7300b57cec5SDimitry Andric 7310b57cec5SDimitry Andrictemplate <class __C1, class __C2> 732*bdd1243dSDimitry Andric_LIBCPP_HIDE_FROM_ABI __bit_iterator<__C2, false> 7330b57cec5SDimitry Andric__swap_ranges_aligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, 7340b57cec5SDimitry Andric __bit_iterator<__C2, false> __result) 7350b57cec5SDimitry Andric{ 7360b57cec5SDimitry Andric typedef __bit_iterator<__C1, false> _I1; 7370b57cec5SDimitry Andric typedef typename _I1::difference_type difference_type; 7380b57cec5SDimitry Andric typedef typename _I1::__storage_type __storage_type; 7390b57cec5SDimitry Andric const int __bits_per_word = _I1::__bits_per_word; 7400b57cec5SDimitry Andric difference_type __n = __last - __first; 7410b57cec5SDimitry Andric if (__n > 0) 7420b57cec5SDimitry Andric { 7430b57cec5SDimitry Andric // do first word 7440b57cec5SDimitry Andric if (__first.__ctz_ != 0) 7450b57cec5SDimitry Andric { 7460b57cec5SDimitry Andric unsigned __clz = __bits_per_word - __first.__ctz_; 7470b57cec5SDimitry Andric difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 7480b57cec5SDimitry Andric __n -= __dn; 7490b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 7500b57cec5SDimitry Andric __storage_type __b1 = *__first.__seg_ & __m; 7510b57cec5SDimitry Andric *__first.__seg_ &= ~__m; 7520b57cec5SDimitry Andric __storage_type __b2 = *__result.__seg_ & __m; 7530b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 7540b57cec5SDimitry Andric *__result.__seg_ |= __b1; 7550b57cec5SDimitry Andric *__first.__seg_ |= __b2; 7560b57cec5SDimitry Andric __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 7570b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 7580b57cec5SDimitry Andric ++__first.__seg_; 7590b57cec5SDimitry Andric // __first.__ctz_ = 0; 7600b57cec5SDimitry Andric } 7610b57cec5SDimitry Andric // __first.__ctz_ == 0; 7620b57cec5SDimitry Andric // do middle words 7630b57cec5SDimitry Andric for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_) 7640b57cec5SDimitry Andric swap(*__first.__seg_, *__result.__seg_); 7650b57cec5SDimitry Andric // do last word 7660b57cec5SDimitry Andric if (__n > 0) 7670b57cec5SDimitry Andric { 7680b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 7690b57cec5SDimitry Andric __storage_type __b1 = *__first.__seg_ & __m; 7700b57cec5SDimitry Andric *__first.__seg_ &= ~__m; 7710b57cec5SDimitry Andric __storage_type __b2 = *__result.__seg_ & __m; 7720b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 7730b57cec5SDimitry Andric *__result.__seg_ |= __b1; 7740b57cec5SDimitry Andric *__first.__seg_ |= __b2; 7750b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(__n); 7760b57cec5SDimitry Andric } 7770b57cec5SDimitry Andric } 7780b57cec5SDimitry Andric return __result; 7790b57cec5SDimitry Andric} 7800b57cec5SDimitry Andric 7810b57cec5SDimitry Andrictemplate <class __C1, class __C2> 782*bdd1243dSDimitry Andric_LIBCPP_HIDE_FROM_ABI __bit_iterator<__C2, false> 7830b57cec5SDimitry Andric__swap_ranges_unaligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, 7840b57cec5SDimitry Andric __bit_iterator<__C2, false> __result) 7850b57cec5SDimitry Andric{ 7860b57cec5SDimitry Andric typedef __bit_iterator<__C1, false> _I1; 7870b57cec5SDimitry Andric typedef typename _I1::difference_type difference_type; 7880b57cec5SDimitry Andric typedef typename _I1::__storage_type __storage_type; 7890b57cec5SDimitry Andric const int __bits_per_word = _I1::__bits_per_word; 7900b57cec5SDimitry Andric difference_type __n = __last - __first; 7910b57cec5SDimitry Andric if (__n > 0) 7920b57cec5SDimitry Andric { 7930b57cec5SDimitry Andric // do first word 7940b57cec5SDimitry Andric if (__first.__ctz_ != 0) 7950b57cec5SDimitry Andric { 7960b57cec5SDimitry Andric unsigned __clz_f = __bits_per_word - __first.__ctz_; 7970b57cec5SDimitry Andric difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 7980b57cec5SDimitry Andric __n -= __dn; 7990b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 8000b57cec5SDimitry Andric __storage_type __b1 = *__first.__seg_ & __m; 8010b57cec5SDimitry Andric *__first.__seg_ &= ~__m; 8020b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __result.__ctz_; 8030b57cec5SDimitry Andric __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 8040b57cec5SDimitry Andric __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 8050b57cec5SDimitry Andric __storage_type __b2 = *__result.__seg_ & __m; 8060b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 8070b57cec5SDimitry Andric if (__result.__ctz_ > __first.__ctz_) 8080b57cec5SDimitry Andric { 8090b57cec5SDimitry Andric unsigned __s = __result.__ctz_ - __first.__ctz_; 8100b57cec5SDimitry Andric *__result.__seg_ |= __b1 << __s; 8110b57cec5SDimitry Andric *__first.__seg_ |= __b2 >> __s; 8120b57cec5SDimitry Andric } 8130b57cec5SDimitry Andric else 8140b57cec5SDimitry Andric { 8150b57cec5SDimitry Andric unsigned __s = __first.__ctz_ - __result.__ctz_; 8160b57cec5SDimitry Andric *__result.__seg_ |= __b1 >> __s; 8170b57cec5SDimitry Andric *__first.__seg_ |= __b2 << __s; 8180b57cec5SDimitry Andric } 8190b57cec5SDimitry Andric __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 8200b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 8210b57cec5SDimitry Andric __dn -= __ddn; 8220b57cec5SDimitry Andric if (__dn > 0) 8230b57cec5SDimitry Andric { 8240b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __dn); 8250b57cec5SDimitry Andric __b2 = *__result.__seg_ & __m; 8260b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 8270b57cec5SDimitry Andric unsigned __s = __first.__ctz_ + __ddn; 8280b57cec5SDimitry Andric *__result.__seg_ |= __b1 >> __s; 8290b57cec5SDimitry Andric *__first.__seg_ |= __b2 << __s; 8300b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(__dn); 8310b57cec5SDimitry Andric } 8320b57cec5SDimitry Andric ++__first.__seg_; 8330b57cec5SDimitry Andric // __first.__ctz_ = 0; 8340b57cec5SDimitry Andric } 8350b57cec5SDimitry Andric // __first.__ctz_ == 0; 8360b57cec5SDimitry Andric // do middle words 8370b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) << __result.__ctz_; 8380b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __result.__ctz_; 8390b57cec5SDimitry Andric for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 8400b57cec5SDimitry Andric { 8410b57cec5SDimitry Andric __storage_type __b1 = *__first.__seg_; 8420b57cec5SDimitry Andric __storage_type __b2 = *__result.__seg_ & __m; 8430b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 8440b57cec5SDimitry Andric *__result.__seg_ |= __b1 << __result.__ctz_; 8450b57cec5SDimitry Andric *__first.__seg_ = __b2 >> __result.__ctz_; 8460b57cec5SDimitry Andric ++__result.__seg_; 8470b57cec5SDimitry Andric __b2 = *__result.__seg_ & ~__m; 8480b57cec5SDimitry Andric *__result.__seg_ &= __m; 8490b57cec5SDimitry Andric *__result.__seg_ |= __b1 >> __clz_r; 8500b57cec5SDimitry Andric *__first.__seg_ |= __b2 << __clz_r; 8510b57cec5SDimitry Andric } 8520b57cec5SDimitry Andric // do last word 8530b57cec5SDimitry Andric if (__n > 0) 8540b57cec5SDimitry Andric { 8550b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __n); 8560b57cec5SDimitry Andric __storage_type __b1 = *__first.__seg_ & __m; 8570b57cec5SDimitry Andric *__first.__seg_ &= ~__m; 8580b57cec5SDimitry Andric __storage_type __dn = _VSTD::min<__storage_type>(__n, __clz_r); 8590b57cec5SDimitry Andric __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 8600b57cec5SDimitry Andric __storage_type __b2 = *__result.__seg_ & __m; 8610b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 8620b57cec5SDimitry Andric *__result.__seg_ |= __b1 << __result.__ctz_; 8630b57cec5SDimitry Andric *__first.__seg_ |= __b2 >> __result.__ctz_; 8640b57cec5SDimitry Andric __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 8650b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 8660b57cec5SDimitry Andric __n -= __dn; 8670b57cec5SDimitry Andric if (__n > 0) 8680b57cec5SDimitry Andric { 8690b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __n); 8700b57cec5SDimitry Andric __b2 = *__result.__seg_ & __m; 8710b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 8720b57cec5SDimitry Andric *__result.__seg_ |= __b1 >> __dn; 8730b57cec5SDimitry Andric *__first.__seg_ |= __b2 << __dn; 8740b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(__n); 8750b57cec5SDimitry Andric } 8760b57cec5SDimitry Andric } 8770b57cec5SDimitry Andric } 8780b57cec5SDimitry Andric return __result; 8790b57cec5SDimitry Andric} 8800b57cec5SDimitry Andric 8810b57cec5SDimitry Andrictemplate <class __C1, class __C2> 8820b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 8830b57cec5SDimitry Andric__bit_iterator<__C2, false> 8840b57cec5SDimitry Andricswap_ranges(__bit_iterator<__C1, false> __first1, __bit_iterator<__C1, false> __last1, 8850b57cec5SDimitry Andric __bit_iterator<__C2, false> __first2) 8860b57cec5SDimitry Andric{ 8870b57cec5SDimitry Andric if (__first1.__ctz_ == __first2.__ctz_) 888e8d8bef9SDimitry Andric return _VSTD::__swap_ranges_aligned(__first1, __last1, __first2); 889e8d8bef9SDimitry Andric return _VSTD::__swap_ranges_unaligned(__first1, __last1, __first2); 8900b57cec5SDimitry Andric} 8910b57cec5SDimitry Andric 8920b57cec5SDimitry Andric// rotate 8930b57cec5SDimitry Andric 8940b57cec5SDimitry Andrictemplate <class _Cp> 8950b57cec5SDimitry Andricstruct __bit_array 8960b57cec5SDimitry Andric{ 8970b57cec5SDimitry Andric typedef typename _Cp::difference_type difference_type; 8980b57cec5SDimitry Andric typedef typename _Cp::__storage_type __storage_type; 8990b57cec5SDimitry Andric typedef typename _Cp::__storage_pointer __storage_pointer; 9000b57cec5SDimitry Andric typedef typename _Cp::iterator iterator; 9010b57cec5SDimitry Andric static const unsigned __bits_per_word = _Cp::__bits_per_word; 9020b57cec5SDimitry Andric static const unsigned _Np = 4; 9030b57cec5SDimitry Andric 9040b57cec5SDimitry Andric difference_type __size_; 9050b57cec5SDimitry Andric __storage_type __word_[_Np]; 9060b57cec5SDimitry Andric 907*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 static difference_type capacity() 9080b57cec5SDimitry Andric {return static_cast<difference_type>(_Np * __bits_per_word);} 909*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit __bit_array(difference_type __s) : __size_(__s) { 91061cfbce3SDimitry Andric if (__libcpp_is_constant_evaluated()) { 91161cfbce3SDimitry Andric for (size_t __i = 0; __i != __bit_array<_Cp>::_Np; ++__i) 91261cfbce3SDimitry Andric std::__construct_at(__word_ + __i, 0); 91361cfbce3SDimitry Andric } 91461cfbce3SDimitry Andric } 915*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator begin() 9160b57cec5SDimitry Andric { 9170b57cec5SDimitry Andric return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]), 0); 9180b57cec5SDimitry Andric } 919*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator end() 9200b57cec5SDimitry Andric { 9210b57cec5SDimitry Andric return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]) + __size_ / __bits_per_word, 9220b57cec5SDimitry Andric static_cast<unsigned>(__size_ % __bits_per_word)); 9230b57cec5SDimitry Andric } 9240b57cec5SDimitry Andric}; 9250b57cec5SDimitry Andric 9260b57cec5SDimitry Andrictemplate <class _Cp> 927*bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> 9280b57cec5SDimitry Andricrotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last) 9290b57cec5SDimitry Andric{ 9300b57cec5SDimitry Andric typedef __bit_iterator<_Cp, false> _I1; 9310b57cec5SDimitry Andric typedef typename _I1::difference_type difference_type; 9320b57cec5SDimitry Andric difference_type __d1 = __middle - __first; 9330b57cec5SDimitry Andric difference_type __d2 = __last - __middle; 9340b57cec5SDimitry Andric _I1 __r = __first + __d2; 9350b57cec5SDimitry Andric while (__d1 != 0 && __d2 != 0) 9360b57cec5SDimitry Andric { 9370b57cec5SDimitry Andric if (__d1 <= __d2) 9380b57cec5SDimitry Andric { 9390b57cec5SDimitry Andric if (__d1 <= __bit_array<_Cp>::capacity()) 9400b57cec5SDimitry Andric { 9410b57cec5SDimitry Andric __bit_array<_Cp> __b(__d1); 9420b57cec5SDimitry Andric _VSTD::copy(__first, __middle, __b.begin()); 9430b57cec5SDimitry Andric _VSTD::copy(__b.begin(), __b.end(), _VSTD::copy(__middle, __last, __first)); 9440b57cec5SDimitry Andric break; 9450b57cec5SDimitry Andric } 9460b57cec5SDimitry Andric else 9470b57cec5SDimitry Andric { 9480b57cec5SDimitry Andric __bit_iterator<_Cp, false> __mp = _VSTD::swap_ranges(__first, __middle, __middle); 9490b57cec5SDimitry Andric __first = __middle; 9500b57cec5SDimitry Andric __middle = __mp; 9510b57cec5SDimitry Andric __d2 -= __d1; 9520b57cec5SDimitry Andric } 9530b57cec5SDimitry Andric } 9540b57cec5SDimitry Andric else 9550b57cec5SDimitry Andric { 9560b57cec5SDimitry Andric if (__d2 <= __bit_array<_Cp>::capacity()) 9570b57cec5SDimitry Andric { 9580b57cec5SDimitry Andric __bit_array<_Cp> __b(__d2); 9590b57cec5SDimitry Andric _VSTD::copy(__middle, __last, __b.begin()); 9600b57cec5SDimitry Andric _VSTD::copy_backward(__b.begin(), __b.end(), _VSTD::copy_backward(__first, __middle, __last)); 9610b57cec5SDimitry Andric break; 9620b57cec5SDimitry Andric } 9630b57cec5SDimitry Andric else 9640b57cec5SDimitry Andric { 9650b57cec5SDimitry Andric __bit_iterator<_Cp, false> __mp = __first + __d2; 9660b57cec5SDimitry Andric _VSTD::swap_ranges(__first, __mp, __middle); 9670b57cec5SDimitry Andric __first = __mp; 9680b57cec5SDimitry Andric __d1 -= __d2; 9690b57cec5SDimitry Andric } 9700b57cec5SDimitry Andric } 9710b57cec5SDimitry Andric } 9720b57cec5SDimitry Andric return __r; 9730b57cec5SDimitry Andric} 9740b57cec5SDimitry Andric 9750b57cec5SDimitry Andric// equal 9760b57cec5SDimitry Andric 9770b57cec5SDimitry Andrictemplate <class _Cp, bool _IC1, bool _IC2> 978*bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool 9790b57cec5SDimitry Andric__equal_unaligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, 9800b57cec5SDimitry Andric __bit_iterator<_Cp, _IC2> __first2) 9810b57cec5SDimitry Andric{ 9820b57cec5SDimitry Andric typedef __bit_iterator<_Cp, _IC1> _It; 9830b57cec5SDimitry Andric typedef typename _It::difference_type difference_type; 9840b57cec5SDimitry Andric typedef typename _It::__storage_type __storage_type; 98561cfbce3SDimitry Andric const int __bits_per_word = _It::__bits_per_word; 9860b57cec5SDimitry Andric difference_type __n = __last1 - __first1; 9870b57cec5SDimitry Andric if (__n > 0) 9880b57cec5SDimitry Andric { 9890b57cec5SDimitry Andric // do first word 9900b57cec5SDimitry Andric if (__first1.__ctz_ != 0) 9910b57cec5SDimitry Andric { 9920b57cec5SDimitry Andric unsigned __clz_f = __bits_per_word - __first1.__ctz_; 9930b57cec5SDimitry Andric difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 9940b57cec5SDimitry Andric __n -= __dn; 9950b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 9960b57cec5SDimitry Andric __storage_type __b = *__first1.__seg_ & __m; 9970b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __first2.__ctz_; 9980b57cec5SDimitry Andric __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 9990b57cec5SDimitry Andric __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 10000b57cec5SDimitry Andric if (__first2.__ctz_ > __first1.__ctz_) 10010b57cec5SDimitry Andric { 10020b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_))) 10030b57cec5SDimitry Andric return false; 10040b57cec5SDimitry Andric } 10050b57cec5SDimitry Andric else 10060b57cec5SDimitry Andric { 10070b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_))) 10080b57cec5SDimitry Andric return false; 10090b57cec5SDimitry Andric } 10100b57cec5SDimitry Andric __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word; 10110b57cec5SDimitry Andric __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word); 10120b57cec5SDimitry Andric __dn -= __ddn; 10130b57cec5SDimitry Andric if (__dn > 0) 10140b57cec5SDimitry Andric { 10150b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __dn); 10160b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn))) 10170b57cec5SDimitry Andric return false; 10180b57cec5SDimitry Andric __first2.__ctz_ = static_cast<unsigned>(__dn); 10190b57cec5SDimitry Andric } 10200b57cec5SDimitry Andric ++__first1.__seg_; 10210b57cec5SDimitry Andric // __first1.__ctz_ = 0; 10220b57cec5SDimitry Andric } 10230b57cec5SDimitry Andric // __first1.__ctz_ == 0; 10240b57cec5SDimitry Andric // do middle words 10250b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __first2.__ctz_; 10260b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) << __first2.__ctz_; 10270b57cec5SDimitry Andric for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_) 10280b57cec5SDimitry Andric { 10290b57cec5SDimitry Andric __storage_type __b = *__first1.__seg_; 10300b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 10310b57cec5SDimitry Andric return false; 10320b57cec5SDimitry Andric ++__first2.__seg_; 10330b57cec5SDimitry Andric if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r)) 10340b57cec5SDimitry Andric return false; 10350b57cec5SDimitry Andric } 10360b57cec5SDimitry Andric // do last word 10370b57cec5SDimitry Andric if (__n > 0) 10380b57cec5SDimitry Andric { 10390b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __n); 10400b57cec5SDimitry Andric __storage_type __b = *__first1.__seg_ & __m; 10410b57cec5SDimitry Andric __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); 10420b57cec5SDimitry Andric __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 10430b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 10440b57cec5SDimitry Andric return false; 10450b57cec5SDimitry Andric __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word; 10460b57cec5SDimitry Andric __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word); 10470b57cec5SDimitry Andric __n -= __dn; 10480b57cec5SDimitry Andric if (__n > 0) 10490b57cec5SDimitry Andric { 10500b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __n); 10510b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (__b >> __dn)) 10520b57cec5SDimitry Andric return false; 10530b57cec5SDimitry Andric } 10540b57cec5SDimitry Andric } 10550b57cec5SDimitry Andric } 10560b57cec5SDimitry Andric return true; 10570b57cec5SDimitry Andric} 10580b57cec5SDimitry Andric 10590b57cec5SDimitry Andrictemplate <class _Cp, bool _IC1, bool _IC2> 1060*bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool 10610b57cec5SDimitry Andric__equal_aligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, 10620b57cec5SDimitry Andric __bit_iterator<_Cp, _IC2> __first2) 10630b57cec5SDimitry Andric{ 10640b57cec5SDimitry Andric typedef __bit_iterator<_Cp, _IC1> _It; 10650b57cec5SDimitry Andric typedef typename _It::difference_type difference_type; 10660b57cec5SDimitry Andric typedef typename _It::__storage_type __storage_type; 106761cfbce3SDimitry Andric const int __bits_per_word = _It::__bits_per_word; 10680b57cec5SDimitry Andric difference_type __n = __last1 - __first1; 10690b57cec5SDimitry Andric if (__n > 0) 10700b57cec5SDimitry Andric { 10710b57cec5SDimitry Andric // do first word 10720b57cec5SDimitry Andric if (__first1.__ctz_ != 0) 10730b57cec5SDimitry Andric { 10740b57cec5SDimitry Andric unsigned __clz = __bits_per_word - __first1.__ctz_; 10750b57cec5SDimitry Andric difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 10760b57cec5SDimitry Andric __n -= __dn; 10770b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 10780b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 10790b57cec5SDimitry Andric return false; 10800b57cec5SDimitry Andric ++__first2.__seg_; 10810b57cec5SDimitry Andric ++__first1.__seg_; 10820b57cec5SDimitry Andric // __first1.__ctz_ = 0; 10830b57cec5SDimitry Andric // __first2.__ctz_ = 0; 10840b57cec5SDimitry Andric } 10850b57cec5SDimitry Andric // __first1.__ctz_ == 0; 10860b57cec5SDimitry Andric // __first2.__ctz_ == 0; 10870b57cec5SDimitry Andric // do middle words 10880b57cec5SDimitry Andric for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_) 10890b57cec5SDimitry Andric if (*__first2.__seg_ != *__first1.__seg_) 10900b57cec5SDimitry Andric return false; 10910b57cec5SDimitry Andric // do last word 10920b57cec5SDimitry Andric if (__n > 0) 10930b57cec5SDimitry Andric { 10940b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 10950b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 10960b57cec5SDimitry Andric return false; 10970b57cec5SDimitry Andric } 10980b57cec5SDimitry Andric } 10990b57cec5SDimitry Andric return true; 11000b57cec5SDimitry Andric} 11010b57cec5SDimitry Andric 11020b57cec5SDimitry Andrictemplate <class _Cp, bool _IC1, bool _IC2> 1103*bdd1243dSDimitry Andricinline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 11040b57cec5SDimitry Andricbool 11050b57cec5SDimitry Andricequal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) 11060b57cec5SDimitry Andric{ 11070b57cec5SDimitry Andric if (__first1.__ctz_ == __first2.__ctz_) 1108e8d8bef9SDimitry Andric return _VSTD::__equal_aligned(__first1, __last1, __first2); 1109e8d8bef9SDimitry Andric return _VSTD::__equal_unaligned(__first1, __last1, __first2); 11100b57cec5SDimitry Andric} 11110b57cec5SDimitry Andric 11120b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst, 11130b57cec5SDimitry Andric typename _Cp::__storage_type> 11140b57cec5SDimitry Andricclass __bit_iterator 11150b57cec5SDimitry Andric{ 11160b57cec5SDimitry Andricpublic: 11170b57cec5SDimitry Andric typedef typename _Cp::difference_type difference_type; 11180b57cec5SDimitry Andric typedef bool value_type; 11190b57cec5SDimitry Andric typedef __bit_iterator pointer; 112081ad6265SDimitry Andric#ifndef _LIBCPP_ABI_BITSET_VECTOR_BOOL_CONST_SUBSCRIPT_RETURN_BOOL 1121*bdd1243dSDimitry Andric typedef __conditional_t<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> > reference; 112281ad6265SDimitry Andric#else 1123*bdd1243dSDimitry Andric using reference = __conditional_t<_IsConst, bool, __bit_reference<_Cp> >; 112481ad6265SDimitry Andric#endif 11250b57cec5SDimitry Andric typedef random_access_iterator_tag iterator_category; 11260b57cec5SDimitry Andric 11270b57cec5SDimitry Andricprivate: 11280b57cec5SDimitry Andric typedef typename _Cp::__storage_type __storage_type; 1129*bdd1243dSDimitry Andric typedef __conditional_t<_IsConst, typename _Cp::__const_storage_pointer, typename _Cp::__storage_pointer> 1130*bdd1243dSDimitry Andric __storage_pointer; 11310b57cec5SDimitry Andric static const unsigned __bits_per_word = _Cp::__bits_per_word; 11320b57cec5SDimitry Andric 11330b57cec5SDimitry Andric __storage_pointer __seg_; 11340b57cec5SDimitry Andric unsigned __ctz_; 11350b57cec5SDimitry Andric 11360b57cec5SDimitry Andricpublic: 1137*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator() _NOEXCEPT 11380b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 11390b57cec5SDimitry Andric : __seg_(nullptr), __ctz_(0) 11400b57cec5SDimitry Andric#endif 11410b57cec5SDimitry Andric {} 11420b57cec5SDimitry Andric 11434652422eSDimitry Andric // When _IsConst=false, this is the copy constructor. 11444652422eSDimitry Andric // It is non-trivial. Making it trivial would break ABI. 11454652422eSDimitry Andric // When _IsConst=true, this is a converting constructor; 11464652422eSDimitry Andric // the copy and move constructors are implicitly generated 11474652422eSDimitry Andric // and trivial. 1148*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 11494652422eSDimitry Andric __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT 11500b57cec5SDimitry Andric : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {} 11510b57cec5SDimitry Andric 11524652422eSDimitry Andric // When _IsConst=false, we have a user-provided copy constructor, 11534652422eSDimitry Andric // so we must also provide a copy assignment operator because 11544652422eSDimitry Andric // the implicit generation of a defaulted one is deprecated. 11554652422eSDimitry Andric // When _IsConst=true, the assignment operators are 11564652422eSDimitry Andric // implicitly generated and trivial. 1157*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 11584652422eSDimitry Andric __bit_iterator& operator=(const _If<_IsConst, struct __private_nat, __bit_iterator>& __it) { 11594652422eSDimitry Andric __seg_ = __it.__seg_; 11604652422eSDimitry Andric __ctz_ = __it.__ctz_; 11614652422eSDimitry Andric return *this; 11624652422eSDimitry Andric } 116347395794SDimitry Andric 1164*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 reference operator*() const _NOEXCEPT { 1165*bdd1243dSDimitry Andric return __conditional_t<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >( 1166*bdd1243dSDimitry Andric __seg_, __storage_type(1) << __ctz_); 116781ad6265SDimitry Andric } 11680b57cec5SDimitry Andric 1169*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator++() 11700b57cec5SDimitry Andric { 11710b57cec5SDimitry Andric if (__ctz_ != __bits_per_word-1) 11720b57cec5SDimitry Andric ++__ctz_; 11730b57cec5SDimitry Andric else 11740b57cec5SDimitry Andric { 11750b57cec5SDimitry Andric __ctz_ = 0; 11760b57cec5SDimitry Andric ++__seg_; 11770b57cec5SDimitry Andric } 11780b57cec5SDimitry Andric return *this; 11790b57cec5SDimitry Andric } 11800b57cec5SDimitry Andric 1181*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator++(int) 11820b57cec5SDimitry Andric { 11830b57cec5SDimitry Andric __bit_iterator __tmp = *this; 11840b57cec5SDimitry Andric ++(*this); 11850b57cec5SDimitry Andric return __tmp; 11860b57cec5SDimitry Andric } 11870b57cec5SDimitry Andric 1188*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator--() 11890b57cec5SDimitry Andric { 11900b57cec5SDimitry Andric if (__ctz_ != 0) 11910b57cec5SDimitry Andric --__ctz_; 11920b57cec5SDimitry Andric else 11930b57cec5SDimitry Andric { 11940b57cec5SDimitry Andric __ctz_ = __bits_per_word - 1; 11950b57cec5SDimitry Andric --__seg_; 11960b57cec5SDimitry Andric } 11970b57cec5SDimitry Andric return *this; 11980b57cec5SDimitry Andric } 11990b57cec5SDimitry Andric 1200*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator--(int) 12010b57cec5SDimitry Andric { 12020b57cec5SDimitry Andric __bit_iterator __tmp = *this; 12030b57cec5SDimitry Andric --(*this); 12040b57cec5SDimitry Andric return __tmp; 12050b57cec5SDimitry Andric } 12060b57cec5SDimitry Andric 1207*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator+=(difference_type __n) 12080b57cec5SDimitry Andric { 12090b57cec5SDimitry Andric if (__n >= 0) 12100b57cec5SDimitry Andric __seg_ += (__n + __ctz_) / __bits_per_word; 12110b57cec5SDimitry Andric else 12120b57cec5SDimitry Andric __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1) 12130b57cec5SDimitry Andric / static_cast<difference_type>(__bits_per_word); 12140b57cec5SDimitry Andric __n &= (__bits_per_word - 1); 12150b57cec5SDimitry Andric __ctz_ = static_cast<unsigned>((__n + __ctz_) % __bits_per_word); 12160b57cec5SDimitry Andric return *this; 12170b57cec5SDimitry Andric } 12180b57cec5SDimitry Andric 1219*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator-=(difference_type __n) 12200b57cec5SDimitry Andric { 12210b57cec5SDimitry Andric return *this += -__n; 12220b57cec5SDimitry Andric } 12230b57cec5SDimitry Andric 1224*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator+(difference_type __n) const 12250b57cec5SDimitry Andric { 12260b57cec5SDimitry Andric __bit_iterator __t(*this); 12270b57cec5SDimitry Andric __t += __n; 12280b57cec5SDimitry Andric return __t; 12290b57cec5SDimitry Andric } 12300b57cec5SDimitry Andric 1231*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator-(difference_type __n) const 12320b57cec5SDimitry Andric { 12330b57cec5SDimitry Andric __bit_iterator __t(*this); 12340b57cec5SDimitry Andric __t -= __n; 12350b57cec5SDimitry Andric return __t; 12360b57cec5SDimitry Andric } 12370b57cec5SDimitry Andric 1238*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 12390b57cec5SDimitry Andric friend __bit_iterator operator+(difference_type __n, const __bit_iterator& __it) {return __it + __n;} 12400b57cec5SDimitry Andric 1241*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 12420b57cec5SDimitry Andric friend difference_type operator-(const __bit_iterator& __x, const __bit_iterator& __y) 12430b57cec5SDimitry Andric {return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;} 12440b57cec5SDimitry Andric 1245*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 reference operator[](difference_type __n) const {return *(*this + __n);} 12460b57cec5SDimitry Andric 1247*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool operator==(const __bit_iterator& __x, const __bit_iterator& __y) 12480b57cec5SDimitry Andric {return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;} 12490b57cec5SDimitry Andric 1250*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool operator!=(const __bit_iterator& __x, const __bit_iterator& __y) 12510b57cec5SDimitry Andric {return !(__x == __y);} 12520b57cec5SDimitry Andric 1253*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool operator<(const __bit_iterator& __x, const __bit_iterator& __y) 12540b57cec5SDimitry Andric {return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);} 12550b57cec5SDimitry Andric 1256*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool operator>(const __bit_iterator& __x, const __bit_iterator& __y) 12570b57cec5SDimitry Andric {return __y < __x;} 12580b57cec5SDimitry Andric 1259*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y) 12600b57cec5SDimitry Andric {return !(__y < __x);} 12610b57cec5SDimitry Andric 1262*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y) 12630b57cec5SDimitry Andric {return !(__x < __y);} 12640b57cec5SDimitry Andric 12650b57cec5SDimitry Andricprivate: 1266*bdd1243dSDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 126781ad6265SDimitry Andric explicit __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT 12680b57cec5SDimitry Andric : __seg_(__s), __ctz_(__ctz) {} 12690b57cec5SDimitry Andric 12700b57cec5SDimitry Andric friend typename _Cp::__self; 12710b57cec5SDimitry Andric 12720b57cec5SDimitry Andric friend class __bit_reference<_Cp>; 12730b57cec5SDimitry Andric friend class __bit_const_reference<_Cp>; 12740b57cec5SDimitry Andric friend class __bit_iterator<_Cp, true>; 12750b57cec5SDimitry Andric template <class _Dp> friend struct __bit_array; 127661cfbce3SDimitry Andric template <class _Dp> 1277*bdd1243dSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 127861cfbce3SDimitry Andric friend void __fill_n_false(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); 127961cfbce3SDimitry Andric 128061cfbce3SDimitry Andric template <class _Dp> 1281*bdd1243dSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 128261cfbce3SDimitry Andric friend void __fill_n_true(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); 128361cfbce3SDimitry Andric 128461cfbce3SDimitry Andric template <class _Dp, bool _IC> 1285*bdd1243dSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 128661cfbce3SDimitry Andric friend __bit_iterator<_Dp, false> __copy_aligned(__bit_iterator<_Dp, _IC> __first, 12870b57cec5SDimitry Andric __bit_iterator<_Dp, _IC> __last, 12880b57cec5SDimitry Andric __bit_iterator<_Dp, false> __result); 128961cfbce3SDimitry Andric template <class _Dp, bool _IC> 1290*bdd1243dSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 129161cfbce3SDimitry Andric friend __bit_iterator<_Dp, false> __copy_unaligned(__bit_iterator<_Dp, _IC> __first, 12920b57cec5SDimitry Andric __bit_iterator<_Dp, _IC> __last, 12930b57cec5SDimitry Andric __bit_iterator<_Dp, false> __result); 129461cfbce3SDimitry Andric template <class _Dp, bool _IC> 1295*bdd1243dSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 129661cfbce3SDimitry Andric friend __bit_iterator<_Dp, false> copy(__bit_iterator<_Dp, _IC> __first, 12970b57cec5SDimitry Andric __bit_iterator<_Dp, _IC> __last, 12980b57cec5SDimitry Andric __bit_iterator<_Dp, false> __result); 129961cfbce3SDimitry Andric template <class _Dp, bool _IC> 1300*bdd1243dSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 130161cfbce3SDimitry Andric friend __bit_iterator<_Dp, false> __copy_backward_aligned(__bit_iterator<_Dp, _IC> __first, 13020b57cec5SDimitry Andric __bit_iterator<_Dp, _IC> __last, 13030b57cec5SDimitry Andric __bit_iterator<_Dp, false> __result); 130461cfbce3SDimitry Andric template <class _Dp, bool _IC> 1305*bdd1243dSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 130661cfbce3SDimitry Andric friend __bit_iterator<_Dp, false> __copy_backward_unaligned(__bit_iterator<_Dp, _IC> __first, 13070b57cec5SDimitry Andric __bit_iterator<_Dp, _IC> __last, 13080b57cec5SDimitry Andric __bit_iterator<_Dp, false> __result); 130961cfbce3SDimitry Andric template <class _Dp, bool _IC> 1310*bdd1243dSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 131161cfbce3SDimitry Andric friend __bit_iterator<_Dp, false> copy_backward(__bit_iterator<_Dp, _IC> __first, 13120b57cec5SDimitry Andric __bit_iterator<_Dp, _IC> __last, 13130b57cec5SDimitry Andric __bit_iterator<_Dp, false> __result); 13140b57cec5SDimitry Andric template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_aligned(__bit_iterator<__C1, false>, 13150b57cec5SDimitry Andric __bit_iterator<__C1, false>, 13160b57cec5SDimitry Andric __bit_iterator<__C2, false>); 13170b57cec5SDimitry Andric template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_unaligned(__bit_iterator<__C1, false>, 13180b57cec5SDimitry Andric __bit_iterator<__C1, false>, 13190b57cec5SDimitry Andric __bit_iterator<__C2, false>); 13200b57cec5SDimitry Andric template <class __C1, class __C2>friend __bit_iterator<__C2, false> swap_ranges(__bit_iterator<__C1, false>, 13210b57cec5SDimitry Andric __bit_iterator<__C1, false>, 13220b57cec5SDimitry Andric __bit_iterator<__C2, false>); 132361cfbce3SDimitry Andric template <class _Dp> 1324*bdd1243dSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 132561cfbce3SDimitry Andric friend __bit_iterator<_Dp, false> rotate(__bit_iterator<_Dp, false>, 13260b57cec5SDimitry Andric __bit_iterator<_Dp, false>, 13270b57cec5SDimitry Andric __bit_iterator<_Dp, false>); 132861cfbce3SDimitry Andric template <class _Dp, bool _IC1, bool _IC2> 1329*bdd1243dSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 133061cfbce3SDimitry Andric friend bool __equal_aligned(__bit_iterator<_Dp, _IC1>, 13310b57cec5SDimitry Andric __bit_iterator<_Dp, _IC1>, 13320b57cec5SDimitry Andric __bit_iterator<_Dp, _IC2>); 133361cfbce3SDimitry Andric template <class _Dp, bool _IC1, bool _IC2> 1334*bdd1243dSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 133561cfbce3SDimitry Andric friend bool __equal_unaligned(__bit_iterator<_Dp, _IC1>, 13360b57cec5SDimitry Andric __bit_iterator<_Dp, _IC1>, 13370b57cec5SDimitry Andric __bit_iterator<_Dp, _IC2>); 133861cfbce3SDimitry Andric template <class _Dp, bool _IC1, bool _IC2> 1339*bdd1243dSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 134061cfbce3SDimitry Andric friend bool equal(__bit_iterator<_Dp, _IC1>, 13410b57cec5SDimitry Andric __bit_iterator<_Dp, _IC1>, 13420b57cec5SDimitry Andric __bit_iterator<_Dp, _IC2>); 134361cfbce3SDimitry Andric template <class _Dp, bool _IC> 1344*bdd1243dSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 134561cfbce3SDimitry Andric friend __bit_iterator<_Dp, _IC> __find_bool_true(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 134661cfbce3SDimitry Andric template <class _Dp, bool _IC> 1347*bdd1243dSDimitry Andric _LIBCPP_CONSTEXPR_SINCE_CXX20 134861cfbce3SDimitry Andric friend __bit_iterator<_Dp, _IC> __find_bool_false(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 13490b57cec5SDimitry Andric template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type 1350*bdd1243dSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 13510b57cec5SDimitry Andric __count_bool_true(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 13520b57cec5SDimitry Andric template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type 13530b57cec5SDimitry Andric __count_bool_false(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 13540b57cec5SDimitry Andric}; 13550b57cec5SDimitry Andric 13560b57cec5SDimitry Andric_LIBCPP_END_NAMESPACE_STD 13570b57cec5SDimitry Andric 13580b57cec5SDimitry Andric_LIBCPP_POP_MACROS 13590b57cec5SDimitry Andric 13600b57cec5SDimitry Andric#endif // _LIBCPP___BIT_REFERENCE 1361