13e519524SHoward Hinnant// -*- C++ -*- 23e519524SHoward Hinnant//===----------------------------------------------------------------------===// 33e519524SHoward Hinnant// 457b08b09SChandler Carruth// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 557b08b09SChandler Carruth// See https://llvm.org/LICENSE.txt for license information. 657b08b09SChandler Carruth// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 73e519524SHoward Hinnant// 83e519524SHoward Hinnant//===----------------------------------------------------------------------===// 93e519524SHoward Hinnant 103e519524SHoward Hinnant#ifndef _LIBCPP___BIT_REFERENCE 113e519524SHoward Hinnant#define _LIBCPP___BIT_REFERENCE 123e519524SHoward Hinnant 13b973e2e2SThorsten Schütt#include <__bits> 144d81a46fSArthur O'Dwyer#include <__config> 153e519524SHoward Hinnant#include <algorithm> 163e519524SHoward Hinnant 17073458b1SHoward Hinnant#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 183e519524SHoward Hinnant# pragma GCC system_header 19073458b1SHoward Hinnant#endif 203e519524SHoward Hinnant 21a016efb1SEric Fiselier_LIBCPP_PUSH_MACROS 22a016efb1SEric Fiselier#include <__undef_macros> 23a016efb1SEric Fiselier 24a016efb1SEric Fiselier 253e519524SHoward Hinnant_LIBCPP_BEGIN_NAMESPACE_STD 263e519524SHoward Hinnant 270ae9efebSHoward Hinnanttemplate <class _Cp, bool _IsConst, typename _Cp::__storage_type = 0> class __bit_iterator; 28c003db1fSHoward Hinnanttemplate <class _Cp> class __bit_const_reference; 293e519524SHoward Hinnant 30a7744562SHoward Hinnanttemplate <class _Tp> 31a7744562SHoward Hinnantstruct __has_storage_type 32a7744562SHoward Hinnant{ 33a7744562SHoward Hinnant static const bool value = false; 34a7744562SHoward Hinnant}; 35a7744562SHoward Hinnant 36c003db1fSHoward Hinnanttemplate <class _Cp, bool = __has_storage_type<_Cp>::value> 373e519524SHoward Hinnantclass __bit_reference 383e519524SHoward Hinnant{ 39c003db1fSHoward Hinnant typedef typename _Cp::__storage_type __storage_type; 40c003db1fSHoward Hinnant typedef typename _Cp::__storage_pointer __storage_pointer; 413e519524SHoward Hinnant 423e519524SHoward Hinnant __storage_pointer __seg_; 433e519524SHoward Hinnant __storage_type __mask_; 443e519524SHoward Hinnant 45c003db1fSHoward Hinnant friend typename _Cp::__self; 46541f9e28SEric Fiselier 47c003db1fSHoward Hinnant friend class __bit_const_reference<_Cp>; 48c003db1fSHoward Hinnant friend class __bit_iterator<_Cp, false>; 493e519524SHoward Hinnantpublic: 50b7eb30d4SFangrui Song _LIBCPP_INLINE_VISIBILITY 51b7eb30d4SFangrui Song __bit_reference(const __bit_reference&) = default; 52b7eb30d4SFangrui Song 53d368a84cSHoward Hinnant _LIBCPP_INLINE_VISIBILITY operator bool() const _NOEXCEPT 54d368a84cSHoward Hinnant {return static_cast<bool>(*__seg_ & __mask_);} 55d368a84cSHoward Hinnant _LIBCPP_INLINE_VISIBILITY bool operator ~() const _NOEXCEPT 56d368a84cSHoward Hinnant {return !static_cast<bool>(*this);} 573e519524SHoward Hinnant 583e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 59d368a84cSHoward Hinnant __bit_reference& operator=(bool __x) _NOEXCEPT 603e519524SHoward Hinnant { 613e519524SHoward Hinnant if (__x) 623e519524SHoward Hinnant *__seg_ |= __mask_; 633e519524SHoward Hinnant else 643e519524SHoward Hinnant *__seg_ &= ~__mask_; 653e519524SHoward Hinnant return *this; 663e519524SHoward Hinnant } 673e519524SHoward Hinnant 68*fb9646edSNikolas Klauser#if _LIBCPP_STD_VER > 20 69*fb9646edSNikolas Klauser _LIBCPP_HIDE_FROM_ABI const __bit_reference& operator=(bool __x) const noexcept { 70*fb9646edSNikolas Klauser if (__x) 71*fb9646edSNikolas Klauser *__seg_ |= __mask_; 72*fb9646edSNikolas Klauser else 73*fb9646edSNikolas Klauser *__seg_ &= ~__mask_; 74*fb9646edSNikolas Klauser return *this; 75*fb9646edSNikolas Klauser } 76*fb9646edSNikolas Klauser#endif 77*fb9646edSNikolas Klauser 783e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 79d368a84cSHoward Hinnant __bit_reference& operator=(const __bit_reference& __x) _NOEXCEPT 80d368a84cSHoward Hinnant {return operator=(static_cast<bool>(__x));} 813e519524SHoward Hinnant 82d368a84cSHoward Hinnant _LIBCPP_INLINE_VISIBILITY void flip() _NOEXCEPT {*__seg_ ^= __mask_;} 83c003db1fSHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, false> operator&() const _NOEXCEPT 84f3b851f0SMarshall Clow {return __bit_iterator<_Cp, false>(__seg_, static_cast<unsigned>(__libcpp_ctz(__mask_)));} 853e519524SHoward Hinnantprivate: 863e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 87d368a84cSHoward Hinnant __bit_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT 88d368a84cSHoward Hinnant : __seg_(__s), __mask_(__m) {} 893e519524SHoward Hinnant}; 903e519524SHoward Hinnant 91c003db1fSHoward Hinnanttemplate <class _Cp> 92c003db1fSHoward Hinnantclass __bit_reference<_Cp, false> 93a7744562SHoward Hinnant{ 94a7744562SHoward Hinnant}; 95a7744562SHoward Hinnant 96d9db9f90SHoward Hinnanttemplate <class _Cp> 973af48ef7SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 98d9db9f90SHoward Hinnantvoid 99d9db9f90SHoward Hinnantswap(__bit_reference<_Cp> __x, __bit_reference<_Cp> __y) _NOEXCEPT 100d9db9f90SHoward Hinnant{ 101d9db9f90SHoward Hinnant bool __t = __x; 102d9db9f90SHoward Hinnant __x = __y; 103d9db9f90SHoward Hinnant __y = __t; 104d9db9f90SHoward Hinnant} 105d9db9f90SHoward Hinnant 106c003db1fSHoward Hinnanttemplate <class _Cp, class _Dp> 1073af48ef7SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 1083e519524SHoward Hinnantvoid 109c003db1fSHoward Hinnantswap(__bit_reference<_Cp> __x, __bit_reference<_Dp> __y) _NOEXCEPT 1103e519524SHoward Hinnant{ 1113e519524SHoward Hinnant bool __t = __x; 1123e519524SHoward Hinnant __x = __y; 1133e519524SHoward Hinnant __y = __t; 1143e519524SHoward Hinnant} 1153e519524SHoward Hinnant 116c003db1fSHoward Hinnanttemplate <class _Cp> 1173af48ef7SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 1183e519524SHoward Hinnantvoid 119c003db1fSHoward Hinnantswap(__bit_reference<_Cp> __x, bool& __y) _NOEXCEPT 1203e519524SHoward Hinnant{ 1213e519524SHoward Hinnant bool __t = __x; 1223e519524SHoward Hinnant __x = __y; 1233e519524SHoward Hinnant __y = __t; 1243e519524SHoward Hinnant} 1253e519524SHoward Hinnant 126c003db1fSHoward Hinnanttemplate <class _Cp> 1273af48ef7SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 1283e519524SHoward Hinnantvoid 129c003db1fSHoward Hinnantswap(bool& __x, __bit_reference<_Cp> __y) _NOEXCEPT 1303e519524SHoward Hinnant{ 1313e519524SHoward Hinnant bool __t = __x; 1323e519524SHoward Hinnant __x = __y; 1333e519524SHoward Hinnant __y = __t; 1343e519524SHoward Hinnant} 1353e519524SHoward Hinnant 136c003db1fSHoward Hinnanttemplate <class _Cp> 1373e519524SHoward Hinnantclass __bit_const_reference 1383e519524SHoward Hinnant{ 139c003db1fSHoward Hinnant typedef typename _Cp::__storage_type __storage_type; 140c003db1fSHoward Hinnant typedef typename _Cp::__const_storage_pointer __storage_pointer; 1413e519524SHoward Hinnant 1423e519524SHoward Hinnant __storage_pointer __seg_; 1433e519524SHoward Hinnant __storage_type __mask_; 1443e519524SHoward Hinnant 145c003db1fSHoward Hinnant friend typename _Cp::__self; 146c003db1fSHoward Hinnant friend class __bit_iterator<_Cp, true>; 1473e519524SHoward Hinnantpublic: 1483e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 149b7eb30d4SFangrui Song __bit_const_reference(const __bit_const_reference&) = default; 150b7eb30d4SFangrui Song 151b7eb30d4SFangrui Song _LIBCPP_INLINE_VISIBILITY 152c003db1fSHoward Hinnant __bit_const_reference(const __bit_reference<_Cp>& __x) _NOEXCEPT 1533e519524SHoward Hinnant : __seg_(__x.__seg_), __mask_(__x.__mask_) {} 1543e519524SHoward Hinnant 155eeac9fcfSHoward Hinnant _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR operator bool() const _NOEXCEPT 156d368a84cSHoward Hinnant {return static_cast<bool>(*__seg_ & __mask_);} 1573e519524SHoward Hinnant 158c003db1fSHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, true> operator&() const _NOEXCEPT 159f3b851f0SMarshall Clow {return __bit_iterator<_Cp, true>(__seg_, static_cast<unsigned>(__libcpp_ctz(__mask_)));} 1603e519524SHoward Hinnantprivate: 1613e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 162eeac9fcfSHoward Hinnant _LIBCPP_CONSTEXPR 163d368a84cSHoward Hinnant __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT 164d368a84cSHoward Hinnant : __seg_(__s), __mask_(__m) {} 1653e519524SHoward Hinnant 166b7eb30d4SFangrui Song __bit_const_reference& operator=(const __bit_const_reference&) = delete; 1673e519524SHoward Hinnant}; 1683e519524SHoward Hinnant 1693e519524SHoward Hinnant// find 1703e519524SHoward Hinnant 171423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst> 172423a8d77SHoward Hinnant__bit_iterator<_Cp, _IsConst> 173423a8d77SHoward Hinnant__find_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 1743e519524SHoward Hinnant{ 175423a8d77SHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _It; 1763e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 177aec08784SEric Fiselier static const int __bits_per_word = _It::__bits_per_word; 1783e519524SHoward Hinnant // do first partial word 1793e519524SHoward Hinnant if (__first.__ctz_ != 0) 1803e519524SHoward Hinnant { 1813e519524SHoward Hinnant __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 182ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__clz_f, __n); 1833e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 1843e519524SHoward Hinnant __storage_type __b = *__first.__seg_ & __m; 1853e519524SHoward Hinnant if (__b) 186f3b851f0SMarshall Clow return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b))); 187303e27d8SHoward Hinnant if (__n == __dn) 1880fc6e981SMarshall Clow return __first + __n; 1893e519524SHoward Hinnant __n -= __dn; 1903e519524SHoward Hinnant ++__first.__seg_; 1913e519524SHoward Hinnant } 1923e519524SHoward Hinnant // do middle whole words 1933e519524SHoward Hinnant for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 1943e519524SHoward Hinnant if (*__first.__seg_) 195f3b851f0SMarshall Clow return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(*__first.__seg_))); 1963e519524SHoward Hinnant // do last partial word 1973e519524SHoward Hinnant if (__n > 0) 1983e519524SHoward Hinnant { 1993e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 2003e519524SHoward Hinnant __storage_type __b = *__first.__seg_ & __m; 2013e519524SHoward Hinnant if (__b) 202f3b851f0SMarshall Clow return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b))); 2033e519524SHoward Hinnant } 2043e519524SHoward Hinnant return _It(__first.__seg_, static_cast<unsigned>(__n)); 2053e519524SHoward Hinnant} 2063e519524SHoward Hinnant 207423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst> 208423a8d77SHoward Hinnant__bit_iterator<_Cp, _IsConst> 209423a8d77SHoward Hinnant__find_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 2103e519524SHoward Hinnant{ 211423a8d77SHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _It; 2123e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 213aec08784SEric Fiselier const int __bits_per_word = _It::__bits_per_word; 2143e519524SHoward Hinnant // do first partial word 2153e519524SHoward Hinnant if (__first.__ctz_ != 0) 2163e519524SHoward Hinnant { 2173e519524SHoward Hinnant __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 218ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__clz_f, __n); 2193e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 220423a8d77SHoward Hinnant __storage_type __b = ~*__first.__seg_ & __m; 2213e519524SHoward Hinnant if (__b) 222f3b851f0SMarshall Clow return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b))); 223303e27d8SHoward Hinnant if (__n == __dn) 2240fc6e981SMarshall Clow return __first + __n; 2253e519524SHoward Hinnant __n -= __dn; 2263e519524SHoward Hinnant ++__first.__seg_; 2273e519524SHoward Hinnant } 2283e519524SHoward Hinnant // do middle whole words 2293e519524SHoward Hinnant for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 2303e519524SHoward Hinnant { 2313e519524SHoward Hinnant __storage_type __b = ~*__first.__seg_; 2323e519524SHoward Hinnant if (__b) 233f3b851f0SMarshall Clow return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b))); 2343e519524SHoward Hinnant } 2353e519524SHoward Hinnant // do last partial word 2363e519524SHoward Hinnant if (__n > 0) 2373e519524SHoward Hinnant { 2383e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 239423a8d77SHoward Hinnant __storage_type __b = ~*__first.__seg_ & __m; 2403e519524SHoward Hinnant if (__b) 241f3b851f0SMarshall Clow return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b))); 2423e519524SHoward Hinnant } 2433e519524SHoward Hinnant return _It(__first.__seg_, static_cast<unsigned>(__n)); 2443e519524SHoward Hinnant} 2453e519524SHoward Hinnant 246423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst, class _Tp> 2473e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 248423a8d77SHoward Hinnant__bit_iterator<_Cp, _IsConst> 249423a8d77SHoward Hinnantfind(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_) 2503e519524SHoward Hinnant{ 251e4383379SHoward Hinnant if (static_cast<bool>(__value_)) 252781c476cSArthur O'Dwyer return _VSTD::__find_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first)); 253781c476cSArthur O'Dwyer return _VSTD::__find_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first)); 2543e519524SHoward Hinnant} 2553e519524SHoward Hinnant 2563e519524SHoward Hinnant// count 2573e519524SHoward Hinnant 258423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst> 259423a8d77SHoward Hinnanttypename __bit_iterator<_Cp, _IsConst>::difference_type 260423a8d77SHoward Hinnant__count_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 2613e519524SHoward Hinnant{ 262423a8d77SHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _It; 2633e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 2643e519524SHoward Hinnant typedef typename _It::difference_type difference_type; 265aec08784SEric Fiselier const int __bits_per_word = _It::__bits_per_word; 2663e519524SHoward Hinnant difference_type __r = 0; 2673e519524SHoward Hinnant // do first partial word 2683e519524SHoward Hinnant if (__first.__ctz_ != 0) 2693e519524SHoward Hinnant { 2703e519524SHoward Hinnant __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 271ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__clz_f, __n); 2723e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 273f3b851f0SMarshall Clow __r = _VSTD::__libcpp_popcount(*__first.__seg_ & __m); 2743e519524SHoward Hinnant __n -= __dn; 2753e519524SHoward Hinnant ++__first.__seg_; 2763e519524SHoward Hinnant } 2773e519524SHoward Hinnant // do middle whole words 2783e519524SHoward Hinnant for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 279f3b851f0SMarshall Clow __r += _VSTD::__libcpp_popcount(*__first.__seg_); 2803e519524SHoward Hinnant // do last partial word 2813e519524SHoward Hinnant if (__n > 0) 2823e519524SHoward Hinnant { 2833e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 284f3b851f0SMarshall Clow __r += _VSTD::__libcpp_popcount(*__first.__seg_ & __m); 2853e519524SHoward Hinnant } 2863e519524SHoward Hinnant return __r; 2873e519524SHoward Hinnant} 2883e519524SHoward Hinnant 289423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst> 290423a8d77SHoward Hinnanttypename __bit_iterator<_Cp, _IsConst>::difference_type 291423a8d77SHoward Hinnant__count_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 2923e519524SHoward Hinnant{ 293423a8d77SHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _It; 2943e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 2953e519524SHoward Hinnant typedef typename _It::difference_type difference_type; 296aec08784SEric Fiselier const int __bits_per_word = _It::__bits_per_word; 2973e519524SHoward Hinnant difference_type __r = 0; 2983e519524SHoward Hinnant // do first partial word 2993e519524SHoward Hinnant if (__first.__ctz_ != 0) 3003e519524SHoward Hinnant { 3013e519524SHoward Hinnant __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 302ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__clz_f, __n); 3033e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 304f3b851f0SMarshall Clow __r = _VSTD::__libcpp_popcount(~*__first.__seg_ & __m); 3053e519524SHoward Hinnant __n -= __dn; 3063e519524SHoward Hinnant ++__first.__seg_; 3073e519524SHoward Hinnant } 3083e519524SHoward Hinnant // do middle whole words 3093e519524SHoward Hinnant for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 310f3b851f0SMarshall Clow __r += _VSTD::__libcpp_popcount(~*__first.__seg_); 3113e519524SHoward Hinnant // do last partial word 3123e519524SHoward Hinnant if (__n > 0) 3133e519524SHoward Hinnant { 3143e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 315f3b851f0SMarshall Clow __r += _VSTD::__libcpp_popcount(~*__first.__seg_ & __m); 3163e519524SHoward Hinnant } 3173e519524SHoward Hinnant return __r; 3183e519524SHoward Hinnant} 3193e519524SHoward Hinnant 320423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst, class _Tp> 3213e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 322423a8d77SHoward Hinnanttypename __bit_iterator<_Cp, _IsConst>::difference_type 323423a8d77SHoward Hinnantcount(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_) 3243e519524SHoward Hinnant{ 325e4383379SHoward Hinnant if (static_cast<bool>(__value_)) 326781c476cSArthur O'Dwyer return _VSTD::__count_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first)); 327781c476cSArthur O'Dwyer return _VSTD::__count_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first)); 3283e519524SHoward Hinnant} 3293e519524SHoward Hinnant 3303e519524SHoward Hinnant// fill_n 3313e519524SHoward Hinnant 332c003db1fSHoward Hinnanttemplate <class _Cp> 3333e519524SHoward Hinnantvoid 334c003db1fSHoward Hinnant__fill_n_false(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) 3353e519524SHoward Hinnant{ 336c003db1fSHoward Hinnant typedef __bit_iterator<_Cp, false> _It; 3373e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 338aec08784SEric Fiselier const int __bits_per_word = _It::__bits_per_word; 3393e519524SHoward Hinnant // do first partial word 3403e519524SHoward Hinnant if (__first.__ctz_ != 0) 3413e519524SHoward Hinnant { 3423e519524SHoward Hinnant __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 343ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__clz_f, __n); 3443e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 3453e519524SHoward Hinnant *__first.__seg_ &= ~__m; 3463e519524SHoward Hinnant __n -= __dn; 3473e519524SHoward Hinnant ++__first.__seg_; 3483e519524SHoward Hinnant } 3493e519524SHoward Hinnant // do middle whole words 3503e519524SHoward Hinnant __storage_type __nw = __n / __bits_per_word; 3510068c591SEric Fiselier _VSTD::memset(_VSTD::__to_address(__first.__seg_), 0, __nw * sizeof(__storage_type)); 3523e519524SHoward Hinnant __n -= __nw * __bits_per_word; 3533e519524SHoward Hinnant // do last partial word 3543e519524SHoward Hinnant if (__n > 0) 3553e519524SHoward Hinnant { 3563e519524SHoward Hinnant __first.__seg_ += __nw; 3573e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 3583e519524SHoward Hinnant *__first.__seg_ &= ~__m; 3593e519524SHoward Hinnant } 3603e519524SHoward Hinnant} 3613e519524SHoward Hinnant 362c003db1fSHoward Hinnanttemplate <class _Cp> 3633e519524SHoward Hinnantvoid 364c003db1fSHoward Hinnant__fill_n_true(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) 3653e519524SHoward Hinnant{ 366c003db1fSHoward Hinnant typedef __bit_iterator<_Cp, false> _It; 3673e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 368aec08784SEric Fiselier const int __bits_per_word = _It::__bits_per_word; 3693e519524SHoward Hinnant // do first partial word 3703e519524SHoward Hinnant if (__first.__ctz_ != 0) 3713e519524SHoward Hinnant { 3723e519524SHoward Hinnant __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 373ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__clz_f, __n); 3743e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 3753e519524SHoward Hinnant *__first.__seg_ |= __m; 3763e519524SHoward Hinnant __n -= __dn; 3773e519524SHoward Hinnant ++__first.__seg_; 3783e519524SHoward Hinnant } 3793e519524SHoward Hinnant // do middle whole words 3803e519524SHoward Hinnant __storage_type __nw = __n / __bits_per_word; 3810068c591SEric Fiselier _VSTD::memset(_VSTD::__to_address(__first.__seg_), -1, __nw * sizeof(__storage_type)); 3823e519524SHoward Hinnant __n -= __nw * __bits_per_word; 3833e519524SHoward Hinnant // do last partial word 3843e519524SHoward Hinnant if (__n > 0) 3853e519524SHoward Hinnant { 3863e519524SHoward Hinnant __first.__seg_ += __nw; 3873e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 3883e519524SHoward Hinnant *__first.__seg_ |= __m; 3893e519524SHoward Hinnant } 3903e519524SHoward Hinnant} 3913e519524SHoward Hinnant 392c003db1fSHoward Hinnanttemplate <class _Cp> 3933af48ef7SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 3943e519524SHoward Hinnantvoid 395c003db1fSHoward Hinnantfill_n(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n, bool __value_) 3963e519524SHoward Hinnant{ 3973e519524SHoward Hinnant if (__n > 0) 3983e519524SHoward Hinnant { 399e4383379SHoward Hinnant if (__value_) 400781c476cSArthur O'Dwyer _VSTD::__fill_n_true(__first, __n); 4013e519524SHoward Hinnant else 402781c476cSArthur O'Dwyer _VSTD::__fill_n_false(__first, __n); 4033e519524SHoward Hinnant } 4043e519524SHoward Hinnant} 4053e519524SHoward Hinnant 4063e519524SHoward Hinnant// fill 4073e519524SHoward Hinnant 408c003db1fSHoward Hinnanttemplate <class _Cp> 4093e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 4103e519524SHoward Hinnantvoid 411c003db1fSHoward Hinnantfill(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __last, bool __value_) 4123e519524SHoward Hinnant{ 413c003db1fSHoward Hinnant _VSTD::fill_n(__first, static_cast<typename _Cp::size_type>(__last - __first), __value_); 4143e519524SHoward Hinnant} 4153e519524SHoward Hinnant 4163e519524SHoward Hinnant// copy 4173e519524SHoward Hinnant 418c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 419c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 420c003db1fSHoward Hinnant__copy_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 421c003db1fSHoward Hinnant __bit_iterator<_Cp, false> __result) 4223e519524SHoward Hinnant{ 423c003db1fSHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _In; 4243e519524SHoward Hinnant typedef typename _In::difference_type difference_type; 4253e519524SHoward Hinnant typedef typename _In::__storage_type __storage_type; 426aec08784SEric Fiselier const int __bits_per_word = _In::__bits_per_word; 4273e519524SHoward Hinnant difference_type __n = __last - __first; 4283e519524SHoward Hinnant if (__n > 0) 4293e519524SHoward Hinnant { 4303e519524SHoward Hinnant // do first word 4313e519524SHoward Hinnant if (__first.__ctz_ != 0) 4323e519524SHoward Hinnant { 4333e519524SHoward Hinnant unsigned __clz = __bits_per_word - __first.__ctz_; 434ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 4353e519524SHoward Hinnant __n -= __dn; 4363e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 4373e519524SHoward Hinnant __storage_type __b = *__first.__seg_ & __m; 4383e519524SHoward Hinnant *__result.__seg_ &= ~__m; 4393e519524SHoward Hinnant *__result.__seg_ |= __b; 4403e519524SHoward Hinnant __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 4413e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 4423e519524SHoward Hinnant ++__first.__seg_; 4433e519524SHoward Hinnant // __first.__ctz_ = 0; 4443e519524SHoward Hinnant } 4453e519524SHoward Hinnant // __first.__ctz_ == 0; 4463e519524SHoward Hinnant // do middle words 4473e519524SHoward Hinnant __storage_type __nw = __n / __bits_per_word; 4480068c591SEric Fiselier _VSTD::memmove(_VSTD::__to_address(__result.__seg_), 4490068c591SEric Fiselier _VSTD::__to_address(__first.__seg_), 4503ec1f00bSHoward Hinnant __nw * sizeof(__storage_type)); 4513e519524SHoward Hinnant __n -= __nw * __bits_per_word; 4523e519524SHoward Hinnant __result.__seg_ += __nw; 4533e519524SHoward Hinnant // do last word 4543e519524SHoward Hinnant if (__n > 0) 4553e519524SHoward Hinnant { 4563e519524SHoward Hinnant __first.__seg_ += __nw; 4573e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 4583e519524SHoward Hinnant __storage_type __b = *__first.__seg_ & __m; 4593e519524SHoward Hinnant *__result.__seg_ &= ~__m; 4603e519524SHoward Hinnant *__result.__seg_ |= __b; 4613e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(__n); 4623e519524SHoward Hinnant } 4633e519524SHoward Hinnant } 4643e519524SHoward Hinnant return __result; 4653e519524SHoward Hinnant} 4663e519524SHoward Hinnant 467c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 468c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 469c003db1fSHoward Hinnant__copy_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 470c003db1fSHoward Hinnant __bit_iterator<_Cp, false> __result) 4713e519524SHoward Hinnant{ 472c003db1fSHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _In; 4733e519524SHoward Hinnant typedef typename _In::difference_type difference_type; 4743e519524SHoward Hinnant typedef typename _In::__storage_type __storage_type; 475aec08784SEric Fiselier static const int __bits_per_word = _In::__bits_per_word; 4763e519524SHoward Hinnant difference_type __n = __last - __first; 4773e519524SHoward Hinnant if (__n > 0) 4783e519524SHoward Hinnant { 4793e519524SHoward Hinnant // do first word 4803e519524SHoward Hinnant if (__first.__ctz_ != 0) 4813e519524SHoward Hinnant { 4823e519524SHoward Hinnant unsigned __clz_f = __bits_per_word - __first.__ctz_; 483ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 4843e519524SHoward Hinnant __n -= __dn; 4853e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 4863e519524SHoward Hinnant __storage_type __b = *__first.__seg_ & __m; 4873e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __result.__ctz_; 488ce48a113SHoward Hinnant __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 4893e519524SHoward Hinnant __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 4903e519524SHoward Hinnant *__result.__seg_ &= ~__m; 4913e519524SHoward Hinnant if (__result.__ctz_ > __first.__ctz_) 4923e519524SHoward Hinnant *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_); 4933e519524SHoward Hinnant else 4943e519524SHoward Hinnant *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_); 4953e519524SHoward Hinnant __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 4963e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 4973e519524SHoward Hinnant __dn -= __ddn; 4983e519524SHoward Hinnant if (__dn > 0) 4993e519524SHoward Hinnant { 5003e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __dn); 5013e519524SHoward Hinnant *__result.__seg_ &= ~__m; 5023e519524SHoward Hinnant *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn); 5033e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(__dn); 5043e519524SHoward Hinnant } 5053e519524SHoward Hinnant ++__first.__seg_; 5063e519524SHoward Hinnant // __first.__ctz_ = 0; 5073e519524SHoward Hinnant } 5083e519524SHoward Hinnant // __first.__ctz_ == 0; 5093e519524SHoward Hinnant // do middle words 5103e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __result.__ctz_; 5113e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) << __result.__ctz_; 5123e519524SHoward Hinnant for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 5133e519524SHoward Hinnant { 5143e519524SHoward Hinnant __storage_type __b = *__first.__seg_; 5153e519524SHoward Hinnant *__result.__seg_ &= ~__m; 5163e519524SHoward Hinnant *__result.__seg_ |= __b << __result.__ctz_; 5173e519524SHoward Hinnant ++__result.__seg_; 5183e519524SHoward Hinnant *__result.__seg_ &= __m; 5193e519524SHoward Hinnant *__result.__seg_ |= __b >> __clz_r; 5203e519524SHoward Hinnant } 5213e519524SHoward Hinnant // do last word 5223e519524SHoward Hinnant if (__n > 0) 5233e519524SHoward Hinnant { 5243e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __n); 5253e519524SHoward Hinnant __storage_type __b = *__first.__seg_ & __m; 526ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); 5273e519524SHoward Hinnant __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 5283e519524SHoward Hinnant *__result.__seg_ &= ~__m; 5293e519524SHoward Hinnant *__result.__seg_ |= __b << __result.__ctz_; 5303e519524SHoward Hinnant __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 5313e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 5323e519524SHoward Hinnant __n -= __dn; 5333e519524SHoward Hinnant if (__n > 0) 5343e519524SHoward Hinnant { 5353e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __n); 5363e519524SHoward Hinnant *__result.__seg_ &= ~__m; 5373e519524SHoward Hinnant *__result.__seg_ |= __b >> __dn; 5383e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(__n); 5393e519524SHoward Hinnant } 5403e519524SHoward Hinnant } 5413e519524SHoward Hinnant } 5423e519524SHoward Hinnant return __result; 5433e519524SHoward Hinnant} 5443e519524SHoward Hinnant 545c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 5463e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 547c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 548c003db1fSHoward Hinnantcopy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 5493e519524SHoward Hinnant{ 5503e519524SHoward Hinnant if (__first.__ctz_ == __result.__ctz_) 551781c476cSArthur O'Dwyer return _VSTD::__copy_aligned(__first, __last, __result); 552781c476cSArthur O'Dwyer return _VSTD::__copy_unaligned(__first, __last, __result); 5533e519524SHoward Hinnant} 5543e519524SHoward Hinnant 5553e519524SHoward Hinnant// copy_backward 5563e519524SHoward Hinnant 557c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 558c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 559c003db1fSHoward Hinnant__copy_backward_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 560c003db1fSHoward Hinnant __bit_iterator<_Cp, false> __result) 5613e519524SHoward Hinnant{ 562c003db1fSHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _In; 5633e519524SHoward Hinnant typedef typename _In::difference_type difference_type; 5643e519524SHoward Hinnant typedef typename _In::__storage_type __storage_type; 565aec08784SEric Fiselier const int __bits_per_word = _In::__bits_per_word; 5663e519524SHoward Hinnant difference_type __n = __last - __first; 5673e519524SHoward Hinnant if (__n > 0) 5683e519524SHoward Hinnant { 5693e519524SHoward Hinnant // do first word 5703e519524SHoward Hinnant if (__last.__ctz_ != 0) 5713e519524SHoward Hinnant { 572ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); 5733e519524SHoward Hinnant __n -= __dn; 5743e519524SHoward Hinnant unsigned __clz = __bits_per_word - __last.__ctz_; 5753e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz); 5763e519524SHoward Hinnant __storage_type __b = *__last.__seg_ & __m; 5773e519524SHoward Hinnant *__result.__seg_ &= ~__m; 5783e519524SHoward Hinnant *__result.__seg_ |= __b; 5793e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 5803e519524SHoward Hinnant __result.__ctz_) % __bits_per_word); 5813e519524SHoward Hinnant // __last.__ctz_ = 0 5823e519524SHoward Hinnant } 5833e519524SHoward Hinnant // __last.__ctz_ == 0 || __n == 0 5843e519524SHoward Hinnant // __result.__ctz_ == 0 || __n == 0 5853e519524SHoward Hinnant // do middle words 5863e519524SHoward Hinnant __storage_type __nw = __n / __bits_per_word; 5873e519524SHoward Hinnant __result.__seg_ -= __nw; 5883e519524SHoward Hinnant __last.__seg_ -= __nw; 5890068c591SEric Fiselier _VSTD::memmove(_VSTD::__to_address(__result.__seg_), 5900068c591SEric Fiselier _VSTD::__to_address(__last.__seg_), 5913ec1f00bSHoward Hinnant __nw * sizeof(__storage_type)); 5923e519524SHoward Hinnant __n -= __nw * __bits_per_word; 5933e519524SHoward Hinnant // do last word 5943e519524SHoward Hinnant if (__n > 0) 5953e519524SHoward Hinnant { 5963e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n); 5973e519524SHoward Hinnant __storage_type __b = *--__last.__seg_ & __m; 5983e519524SHoward Hinnant *--__result.__seg_ &= ~__m; 5993e519524SHoward Hinnant *__result.__seg_ |= __b; 6003e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 6013e519524SHoward Hinnant } 6023e519524SHoward Hinnant } 6033e519524SHoward Hinnant return __result; 6043e519524SHoward Hinnant} 6053e519524SHoward Hinnant 606c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 607c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 608c003db1fSHoward Hinnant__copy_backward_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 609c003db1fSHoward Hinnant __bit_iterator<_Cp, false> __result) 6103e519524SHoward Hinnant{ 611c003db1fSHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _In; 6123e519524SHoward Hinnant typedef typename _In::difference_type difference_type; 6133e519524SHoward Hinnant typedef typename _In::__storage_type __storage_type; 614aec08784SEric Fiselier const int __bits_per_word = _In::__bits_per_word; 6153e519524SHoward Hinnant difference_type __n = __last - __first; 6163e519524SHoward Hinnant if (__n > 0) 6173e519524SHoward Hinnant { 6183e519524SHoward Hinnant // do first word 6193e519524SHoward Hinnant if (__last.__ctz_ != 0) 6203e519524SHoward Hinnant { 621ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); 6223e519524SHoward Hinnant __n -= __dn; 6233e519524SHoward Hinnant unsigned __clz_l = __bits_per_word - __last.__ctz_; 6243e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l); 6253e519524SHoward Hinnant __storage_type __b = *__last.__seg_ & __m; 6263e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __result.__ctz_; 627ce48a113SHoward Hinnant __storage_type __ddn = _VSTD::min(__dn, static_cast<difference_type>(__result.__ctz_)); 6283e519524SHoward Hinnant if (__ddn > 0) 6293e519524SHoward Hinnant { 6303e519524SHoward Hinnant __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r); 6313e519524SHoward Hinnant *__result.__seg_ &= ~__m; 6323e519524SHoward Hinnant if (__result.__ctz_ > __last.__ctz_) 6333e519524SHoward Hinnant *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 6343e519524SHoward Hinnant else 6353e519524SHoward Hinnant *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_); 6363e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) + 6373e519524SHoward Hinnant __result.__ctz_) % __bits_per_word); 6383e519524SHoward Hinnant __dn -= __ddn; 6393e519524SHoward Hinnant } 6403e519524SHoward Hinnant if (__dn > 0) 6413e519524SHoward Hinnant { 6423e519524SHoward Hinnant // __result.__ctz_ == 0 6433e519524SHoward Hinnant --__result.__seg_; 6443e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1)); 6453e519524SHoward Hinnant __m = ~__storage_type(0) << __result.__ctz_; 6463e519524SHoward Hinnant *__result.__seg_ &= ~__m; 6473e519524SHoward Hinnant __last.__ctz_ -= __dn + __ddn; 6483e519524SHoward Hinnant *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 6493e519524SHoward Hinnant } 6503e519524SHoward Hinnant // __last.__ctz_ = 0 6513e519524SHoward Hinnant } 6523e519524SHoward Hinnant // __last.__ctz_ == 0 || __n == 0 6533e519524SHoward Hinnant // __result.__ctz_ != 0 || __n == 0 6543e519524SHoward Hinnant // do middle words 6553e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __result.__ctz_; 6563e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> __clz_r; 6573e519524SHoward Hinnant for (; __n >= __bits_per_word; __n -= __bits_per_word) 6583e519524SHoward Hinnant { 6593e519524SHoward Hinnant __storage_type __b = *--__last.__seg_; 6603e519524SHoward Hinnant *__result.__seg_ &= ~__m; 6613e519524SHoward Hinnant *__result.__seg_ |= __b >> __clz_r; 6623e519524SHoward Hinnant *--__result.__seg_ &= __m; 6633e519524SHoward Hinnant *__result.__seg_ |= __b << __result.__ctz_; 6643e519524SHoward Hinnant } 6653e519524SHoward Hinnant // do last word 6663e519524SHoward Hinnant if (__n > 0) 6673e519524SHoward Hinnant { 6683e519524SHoward Hinnant __m = ~__storage_type(0) << (__bits_per_word - __n); 6693e519524SHoward Hinnant __storage_type __b = *--__last.__seg_ & __m; 670c206366fSHoward Hinnant __clz_r = __bits_per_word - __result.__ctz_; 671ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__result.__ctz_)); 6723e519524SHoward Hinnant __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r); 6733e519524SHoward Hinnant *__result.__seg_ &= ~__m; 6743e519524SHoward Hinnant *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_); 6753e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 6763e519524SHoward Hinnant __result.__ctz_) % __bits_per_word); 6773e519524SHoward Hinnant __n -= __dn; 6783e519524SHoward Hinnant if (__n > 0) 6793e519524SHoward Hinnant { 6803e519524SHoward Hinnant // __result.__ctz_ == 0 6813e519524SHoward Hinnant --__result.__seg_; 6823e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 6833e519524SHoward Hinnant __m = ~__storage_type(0) << __result.__ctz_; 6843e519524SHoward Hinnant *__result.__seg_ &= ~__m; 6853e519524SHoward Hinnant *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn)); 6863e519524SHoward Hinnant } 6873e519524SHoward Hinnant } 6883e519524SHoward Hinnant } 6893e519524SHoward Hinnant return __result; 6903e519524SHoward Hinnant} 6913e519524SHoward Hinnant 692c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 6933e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 694c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 695c003db1fSHoward Hinnantcopy_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 6963e519524SHoward Hinnant{ 6973e519524SHoward Hinnant if (__last.__ctz_ == __result.__ctz_) 698781c476cSArthur O'Dwyer return _VSTD::__copy_backward_aligned(__first, __last, __result); 699781c476cSArthur O'Dwyer return _VSTD::__copy_backward_unaligned(__first, __last, __result); 7003e519524SHoward Hinnant} 7013e519524SHoward Hinnant 7023e519524SHoward Hinnant// move 7033e519524SHoward Hinnant 704c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 7053e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 706c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 707c003db1fSHoward Hinnantmove(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 7083e519524SHoward Hinnant{ 709ce48a113SHoward Hinnant return _VSTD::copy(__first, __last, __result); 7103e519524SHoward Hinnant} 7113e519524SHoward Hinnant 7123e519524SHoward Hinnant// move_backward 7133e519524SHoward Hinnant 714c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 7153e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 716c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 717c003db1fSHoward Hinnantmove_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 7183e519524SHoward Hinnant{ 71908de4b0dSMarshall Clow return _VSTD::copy_backward(__first, __last, __result); 7203e519524SHoward Hinnant} 7213e519524SHoward Hinnant 7223e519524SHoward Hinnant// swap_ranges 7233e519524SHoward Hinnant 724dbe81119SHoward Hinnanttemplate <class __C1, class __C2> 725dbe81119SHoward Hinnant__bit_iterator<__C2, false> 726dbe81119SHoward Hinnant__swap_ranges_aligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, 727dbe81119SHoward Hinnant __bit_iterator<__C2, false> __result) 7283e519524SHoward Hinnant{ 729dbe81119SHoward Hinnant typedef __bit_iterator<__C1, false> _I1; 7303e519524SHoward Hinnant typedef typename _I1::difference_type difference_type; 7313e519524SHoward Hinnant typedef typename _I1::__storage_type __storage_type; 732aec08784SEric Fiselier const int __bits_per_word = _I1::__bits_per_word; 7333e519524SHoward Hinnant difference_type __n = __last - __first; 7343e519524SHoward Hinnant if (__n > 0) 7353e519524SHoward Hinnant { 7363e519524SHoward Hinnant // do first word 7373e519524SHoward Hinnant if (__first.__ctz_ != 0) 7383e519524SHoward Hinnant { 7393e519524SHoward Hinnant unsigned __clz = __bits_per_word - __first.__ctz_; 740ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 7413e519524SHoward Hinnant __n -= __dn; 7423e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 7433e519524SHoward Hinnant __storage_type __b1 = *__first.__seg_ & __m; 7443e519524SHoward Hinnant *__first.__seg_ &= ~__m; 7453e519524SHoward Hinnant __storage_type __b2 = *__result.__seg_ & __m; 7463e519524SHoward Hinnant *__result.__seg_ &= ~__m; 7473e519524SHoward Hinnant *__result.__seg_ |= __b1; 7483e519524SHoward Hinnant *__first.__seg_ |= __b2; 7493e519524SHoward Hinnant __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 7503e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 7513e519524SHoward Hinnant ++__first.__seg_; 7523e519524SHoward Hinnant // __first.__ctz_ = 0; 7533e519524SHoward Hinnant } 7543e519524SHoward Hinnant // __first.__ctz_ == 0; 7553e519524SHoward Hinnant // do middle words 7563e519524SHoward Hinnant for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_) 7573e519524SHoward Hinnant swap(*__first.__seg_, *__result.__seg_); 7583e519524SHoward Hinnant // do last word 7593e519524SHoward Hinnant if (__n > 0) 7603e519524SHoward Hinnant { 7613e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 7623e519524SHoward Hinnant __storage_type __b1 = *__first.__seg_ & __m; 7633e519524SHoward Hinnant *__first.__seg_ &= ~__m; 7643e519524SHoward Hinnant __storage_type __b2 = *__result.__seg_ & __m; 7653e519524SHoward Hinnant *__result.__seg_ &= ~__m; 7663e519524SHoward Hinnant *__result.__seg_ |= __b1; 7673e519524SHoward Hinnant *__first.__seg_ |= __b2; 7683e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(__n); 7693e519524SHoward Hinnant } 7703e519524SHoward Hinnant } 7713e519524SHoward Hinnant return __result; 7723e519524SHoward Hinnant} 7733e519524SHoward Hinnant 774dbe81119SHoward Hinnanttemplate <class __C1, class __C2> 775dbe81119SHoward Hinnant__bit_iterator<__C2, false> 776dbe81119SHoward Hinnant__swap_ranges_unaligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, 777dbe81119SHoward Hinnant __bit_iterator<__C2, false> __result) 7783e519524SHoward Hinnant{ 779dbe81119SHoward Hinnant typedef __bit_iterator<__C1, false> _I1; 7803e519524SHoward Hinnant typedef typename _I1::difference_type difference_type; 7813e519524SHoward Hinnant typedef typename _I1::__storage_type __storage_type; 782aec08784SEric Fiselier const int __bits_per_word = _I1::__bits_per_word; 7833e519524SHoward Hinnant difference_type __n = __last - __first; 7843e519524SHoward Hinnant if (__n > 0) 7853e519524SHoward Hinnant { 7863e519524SHoward Hinnant // do first word 7873e519524SHoward Hinnant if (__first.__ctz_ != 0) 7883e519524SHoward Hinnant { 7893e519524SHoward Hinnant unsigned __clz_f = __bits_per_word - __first.__ctz_; 790ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 7913e519524SHoward Hinnant __n -= __dn; 7923e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 7933e519524SHoward Hinnant __storage_type __b1 = *__first.__seg_ & __m; 7943e519524SHoward Hinnant *__first.__seg_ &= ~__m; 7953e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __result.__ctz_; 796ce48a113SHoward Hinnant __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 7973e519524SHoward Hinnant __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 7983e519524SHoward Hinnant __storage_type __b2 = *__result.__seg_ & __m; 7993e519524SHoward Hinnant *__result.__seg_ &= ~__m; 8003e519524SHoward Hinnant if (__result.__ctz_ > __first.__ctz_) 8013e519524SHoward Hinnant { 8023e519524SHoward Hinnant unsigned __s = __result.__ctz_ - __first.__ctz_; 8033e519524SHoward Hinnant *__result.__seg_ |= __b1 << __s; 8043e519524SHoward Hinnant *__first.__seg_ |= __b2 >> __s; 8053e519524SHoward Hinnant } 8063e519524SHoward Hinnant else 8073e519524SHoward Hinnant { 8083e519524SHoward Hinnant unsigned __s = __first.__ctz_ - __result.__ctz_; 8093e519524SHoward Hinnant *__result.__seg_ |= __b1 >> __s; 8103e519524SHoward Hinnant *__first.__seg_ |= __b2 << __s; 8113e519524SHoward Hinnant } 8123e519524SHoward Hinnant __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 8133e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 8143e519524SHoward Hinnant __dn -= __ddn; 8153e519524SHoward Hinnant if (__dn > 0) 8163e519524SHoward Hinnant { 8173e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __dn); 8183e519524SHoward Hinnant __b2 = *__result.__seg_ & __m; 8193e519524SHoward Hinnant *__result.__seg_ &= ~__m; 8203e519524SHoward Hinnant unsigned __s = __first.__ctz_ + __ddn; 8213e519524SHoward Hinnant *__result.__seg_ |= __b1 >> __s; 8223e519524SHoward Hinnant *__first.__seg_ |= __b2 << __s; 8233e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(__dn); 8243e519524SHoward Hinnant } 8253e519524SHoward Hinnant ++__first.__seg_; 8263e519524SHoward Hinnant // __first.__ctz_ = 0; 8273e519524SHoward Hinnant } 8283e519524SHoward Hinnant // __first.__ctz_ == 0; 8293e519524SHoward Hinnant // do middle words 8303e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) << __result.__ctz_; 8313e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __result.__ctz_; 8323e519524SHoward Hinnant for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 8333e519524SHoward Hinnant { 8343e519524SHoward Hinnant __storage_type __b1 = *__first.__seg_; 8353e519524SHoward Hinnant __storage_type __b2 = *__result.__seg_ & __m; 8363e519524SHoward Hinnant *__result.__seg_ &= ~__m; 8373e519524SHoward Hinnant *__result.__seg_ |= __b1 << __result.__ctz_; 8383e519524SHoward Hinnant *__first.__seg_ = __b2 >> __result.__ctz_; 8393e519524SHoward Hinnant ++__result.__seg_; 8403e519524SHoward Hinnant __b2 = *__result.__seg_ & ~__m; 8413e519524SHoward Hinnant *__result.__seg_ &= __m; 8423e519524SHoward Hinnant *__result.__seg_ |= __b1 >> __clz_r; 8433e519524SHoward Hinnant *__first.__seg_ |= __b2 << __clz_r; 8443e519524SHoward Hinnant } 8453e519524SHoward Hinnant // do last word 8463e519524SHoward Hinnant if (__n > 0) 8473e519524SHoward Hinnant { 8483e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __n); 8493e519524SHoward Hinnant __storage_type __b1 = *__first.__seg_ & __m; 8503e519524SHoward Hinnant *__first.__seg_ &= ~__m; 851ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min<__storage_type>(__n, __clz_r); 8523e519524SHoward Hinnant __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 8533e519524SHoward Hinnant __storage_type __b2 = *__result.__seg_ & __m; 8543e519524SHoward Hinnant *__result.__seg_ &= ~__m; 8553e519524SHoward Hinnant *__result.__seg_ |= __b1 << __result.__ctz_; 8563e519524SHoward Hinnant *__first.__seg_ |= __b2 >> __result.__ctz_; 8573e519524SHoward Hinnant __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 8583e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 8593e519524SHoward Hinnant __n -= __dn; 8603e519524SHoward Hinnant if (__n > 0) 8613e519524SHoward Hinnant { 8623e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __n); 8633e519524SHoward Hinnant __b2 = *__result.__seg_ & __m; 8643e519524SHoward Hinnant *__result.__seg_ &= ~__m; 8653e519524SHoward Hinnant *__result.__seg_ |= __b1 >> __dn; 8663e519524SHoward Hinnant *__first.__seg_ |= __b2 << __dn; 8673e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(__n); 8683e519524SHoward Hinnant } 8693e519524SHoward Hinnant } 8703e519524SHoward Hinnant } 8713e519524SHoward Hinnant return __result; 8723e519524SHoward Hinnant} 8733e519524SHoward Hinnant 874dbe81119SHoward Hinnanttemplate <class __C1, class __C2> 8753e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 876dbe81119SHoward Hinnant__bit_iterator<__C2, false> 877dbe81119SHoward Hinnantswap_ranges(__bit_iterator<__C1, false> __first1, __bit_iterator<__C1, false> __last1, 878dbe81119SHoward Hinnant __bit_iterator<__C2, false> __first2) 8793e519524SHoward Hinnant{ 8803e519524SHoward Hinnant if (__first1.__ctz_ == __first2.__ctz_) 881781c476cSArthur O'Dwyer return _VSTD::__swap_ranges_aligned(__first1, __last1, __first2); 882781c476cSArthur O'Dwyer return _VSTD::__swap_ranges_unaligned(__first1, __last1, __first2); 8833e519524SHoward Hinnant} 8843e519524SHoward Hinnant 8853e519524SHoward Hinnant// rotate 8863e519524SHoward Hinnant 887c003db1fSHoward Hinnanttemplate <class _Cp> 8883e519524SHoward Hinnantstruct __bit_array 8893e519524SHoward Hinnant{ 890c003db1fSHoward Hinnant typedef typename _Cp::difference_type difference_type; 891c003db1fSHoward Hinnant typedef typename _Cp::__storage_type __storage_type; 8923ec1f00bSHoward Hinnant typedef typename _Cp::__storage_pointer __storage_pointer; 893c003db1fSHoward Hinnant typedef typename _Cp::iterator iterator; 894c003db1fSHoward Hinnant static const unsigned __bits_per_word = _Cp::__bits_per_word; 895c003db1fSHoward Hinnant static const unsigned _Np = 4; 8963e519524SHoward Hinnant 8973e519524SHoward Hinnant difference_type __size_; 898c003db1fSHoward Hinnant __storage_type __word_[_Np]; 8993e519524SHoward Hinnant 9003e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY static difference_type capacity() 901c003db1fSHoward Hinnant {return static_cast<difference_type>(_Np * __bits_per_word);} 9023e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY explicit __bit_array(difference_type __s) : __size_(__s) {} 9033ec1f00bSHoward Hinnant _LIBCPP_INLINE_VISIBILITY iterator begin() 9043ec1f00bSHoward Hinnant { 9053ec1f00bSHoward Hinnant return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]), 0); 9063ec1f00bSHoward Hinnant } 9073ec1f00bSHoward Hinnant _LIBCPP_INLINE_VISIBILITY iterator end() 9083ec1f00bSHoward Hinnant { 9093ec1f00bSHoward Hinnant return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]) + __size_ / __bits_per_word, 9103ec1f00bSHoward Hinnant static_cast<unsigned>(__size_ % __bits_per_word)); 9113ec1f00bSHoward Hinnant } 9123e519524SHoward Hinnant}; 9133e519524SHoward Hinnant 914c003db1fSHoward Hinnanttemplate <class _Cp> 915c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 916c003db1fSHoward Hinnantrotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last) 9173e519524SHoward Hinnant{ 918c003db1fSHoward Hinnant typedef __bit_iterator<_Cp, false> _I1; 9193e519524SHoward Hinnant typedef typename _I1::difference_type difference_type; 9203e519524SHoward Hinnant difference_type __d1 = __middle - __first; 9213e519524SHoward Hinnant difference_type __d2 = __last - __middle; 9223e519524SHoward Hinnant _I1 __r = __first + __d2; 9233e519524SHoward Hinnant while (__d1 != 0 && __d2 != 0) 9243e519524SHoward Hinnant { 9253e519524SHoward Hinnant if (__d1 <= __d2) 9263e519524SHoward Hinnant { 927c003db1fSHoward Hinnant if (__d1 <= __bit_array<_Cp>::capacity()) 9283e519524SHoward Hinnant { 929c003db1fSHoward Hinnant __bit_array<_Cp> __b(__d1); 930ce48a113SHoward Hinnant _VSTD::copy(__first, __middle, __b.begin()); 931ce48a113SHoward Hinnant _VSTD::copy(__b.begin(), __b.end(), _VSTD::copy(__middle, __last, __first)); 9323e519524SHoward Hinnant break; 9333e519524SHoward Hinnant } 9343e519524SHoward Hinnant else 9353e519524SHoward Hinnant { 936c003db1fSHoward Hinnant __bit_iterator<_Cp, false> __mp = _VSTD::swap_ranges(__first, __middle, __middle); 9373e519524SHoward Hinnant __first = __middle; 9383e519524SHoward Hinnant __middle = __mp; 9393e519524SHoward Hinnant __d2 -= __d1; 9403e519524SHoward Hinnant } 9413e519524SHoward Hinnant } 9423e519524SHoward Hinnant else 9433e519524SHoward Hinnant { 944c003db1fSHoward Hinnant if (__d2 <= __bit_array<_Cp>::capacity()) 9453e519524SHoward Hinnant { 946c003db1fSHoward Hinnant __bit_array<_Cp> __b(__d2); 947ce48a113SHoward Hinnant _VSTD::copy(__middle, __last, __b.begin()); 948ce48a113SHoward Hinnant _VSTD::copy_backward(__b.begin(), __b.end(), _VSTD::copy_backward(__first, __middle, __last)); 9493e519524SHoward Hinnant break; 9503e519524SHoward Hinnant } 9513e519524SHoward Hinnant else 9523e519524SHoward Hinnant { 953c003db1fSHoward Hinnant __bit_iterator<_Cp, false> __mp = __first + __d2; 954ce48a113SHoward Hinnant _VSTD::swap_ranges(__first, __mp, __middle); 9553e519524SHoward Hinnant __first = __mp; 9563e519524SHoward Hinnant __d1 -= __d2; 9573e519524SHoward Hinnant } 9583e519524SHoward Hinnant } 9593e519524SHoward Hinnant } 9603e519524SHoward Hinnant return __r; 9613e519524SHoward Hinnant} 9623e519524SHoward Hinnant 9633e519524SHoward Hinnant// equal 9643e519524SHoward Hinnant 9651237dccaSHoward Hinnanttemplate <class _Cp, bool _IC1, bool _IC2> 9663e519524SHoward Hinnantbool 9671237dccaSHoward Hinnant__equal_unaligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, 9681237dccaSHoward Hinnant __bit_iterator<_Cp, _IC2> __first2) 9693e519524SHoward Hinnant{ 9701237dccaSHoward Hinnant typedef __bit_iterator<_Cp, _IC1> _It; 9713e519524SHoward Hinnant typedef typename _It::difference_type difference_type; 9723e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 973aec08784SEric Fiselier static const int __bits_per_word = _It::__bits_per_word; 9743e519524SHoward Hinnant difference_type __n = __last1 - __first1; 9753e519524SHoward Hinnant if (__n > 0) 9763e519524SHoward Hinnant { 9773e519524SHoward Hinnant // do first word 9783e519524SHoward Hinnant if (__first1.__ctz_ != 0) 9793e519524SHoward Hinnant { 9803e519524SHoward Hinnant unsigned __clz_f = __bits_per_word - __first1.__ctz_; 981ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 9823e519524SHoward Hinnant __n -= __dn; 9833e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 9843e519524SHoward Hinnant __storage_type __b = *__first1.__seg_ & __m; 9853e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __first2.__ctz_; 986ce48a113SHoward Hinnant __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 9873e519524SHoward Hinnant __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 9883e519524SHoward Hinnant if (__first2.__ctz_ > __first1.__ctz_) 9894c0de496SHoward Hinnant { 9903e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_))) 9913e519524SHoward Hinnant return false; 9924c0de496SHoward Hinnant } 9933e519524SHoward Hinnant else 9944c0de496SHoward Hinnant { 9953e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_))) 9963e519524SHoward Hinnant return false; 9974c0de496SHoward Hinnant } 9983e519524SHoward Hinnant __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word; 9993e519524SHoward Hinnant __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word); 10003e519524SHoward Hinnant __dn -= __ddn; 10013e519524SHoward Hinnant if (__dn > 0) 10023e519524SHoward Hinnant { 10033e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __dn); 10043e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn))) 10053e519524SHoward Hinnant return false; 10063e519524SHoward Hinnant __first2.__ctz_ = static_cast<unsigned>(__dn); 10073e519524SHoward Hinnant } 10083e519524SHoward Hinnant ++__first1.__seg_; 10093e519524SHoward Hinnant // __first1.__ctz_ = 0; 10103e519524SHoward Hinnant } 10113e519524SHoward Hinnant // __first1.__ctz_ == 0; 10123e519524SHoward Hinnant // do middle words 10133e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __first2.__ctz_; 10143e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) << __first2.__ctz_; 10153e519524SHoward Hinnant for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_) 10163e519524SHoward Hinnant { 10173e519524SHoward Hinnant __storage_type __b = *__first1.__seg_; 10183e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 10193e519524SHoward Hinnant return false; 10203e519524SHoward Hinnant ++__first2.__seg_; 10213e519524SHoward Hinnant if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r)) 10223e519524SHoward Hinnant return false; 10233e519524SHoward Hinnant } 10243e519524SHoward Hinnant // do last word 10253e519524SHoward Hinnant if (__n > 0) 10263e519524SHoward Hinnant { 10273e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __n); 10283e519524SHoward Hinnant __storage_type __b = *__first1.__seg_ & __m; 1029ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); 10303e519524SHoward Hinnant __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 10313e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 10323e519524SHoward Hinnant return false; 10333e519524SHoward Hinnant __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word; 10343e519524SHoward Hinnant __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word); 10353e519524SHoward Hinnant __n -= __dn; 10363e519524SHoward Hinnant if (__n > 0) 10373e519524SHoward Hinnant { 10383e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __n); 10393e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (__b >> __dn)) 10403e519524SHoward Hinnant return false; 10413e519524SHoward Hinnant } 10423e519524SHoward Hinnant } 10433e519524SHoward Hinnant } 10443e519524SHoward Hinnant return true; 10453e519524SHoward Hinnant} 10463e519524SHoward Hinnant 10471237dccaSHoward Hinnanttemplate <class _Cp, bool _IC1, bool _IC2> 10483e519524SHoward Hinnantbool 10491237dccaSHoward Hinnant__equal_aligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, 10501237dccaSHoward Hinnant __bit_iterator<_Cp, _IC2> __first2) 10513e519524SHoward Hinnant{ 10521237dccaSHoward Hinnant typedef __bit_iterator<_Cp, _IC1> _It; 10533e519524SHoward Hinnant typedef typename _It::difference_type difference_type; 10543e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 1055aec08784SEric Fiselier static const int __bits_per_word = _It::__bits_per_word; 10563e519524SHoward Hinnant difference_type __n = __last1 - __first1; 10573e519524SHoward Hinnant if (__n > 0) 10583e519524SHoward Hinnant { 10593e519524SHoward Hinnant // do first word 10603e519524SHoward Hinnant if (__first1.__ctz_ != 0) 10613e519524SHoward Hinnant { 10623e519524SHoward Hinnant unsigned __clz = __bits_per_word - __first1.__ctz_; 1063ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 10643e519524SHoward Hinnant __n -= __dn; 10653e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 10663e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 10673e519524SHoward Hinnant return false; 10683e519524SHoward Hinnant ++__first2.__seg_; 10693e519524SHoward Hinnant ++__first1.__seg_; 10703e519524SHoward Hinnant // __first1.__ctz_ = 0; 10713e519524SHoward Hinnant // __first2.__ctz_ = 0; 10723e519524SHoward Hinnant } 10733e519524SHoward Hinnant // __first1.__ctz_ == 0; 10743e519524SHoward Hinnant // __first2.__ctz_ == 0; 10753e519524SHoward Hinnant // do middle words 10763e519524SHoward Hinnant for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_) 10773e519524SHoward Hinnant if (*__first2.__seg_ != *__first1.__seg_) 10783e519524SHoward Hinnant return false; 10793e519524SHoward Hinnant // do last word 10803e519524SHoward Hinnant if (__n > 0) 10813e519524SHoward Hinnant { 10823e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 10833e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 10843e519524SHoward Hinnant return false; 10853e519524SHoward Hinnant } 10863e519524SHoward Hinnant } 10873e519524SHoward Hinnant return true; 10883e519524SHoward Hinnant} 10893e519524SHoward Hinnant 1090c003db1fSHoward Hinnanttemplate <class _Cp, bool _IC1, bool _IC2> 109143d99238SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 10923e519524SHoward Hinnantbool 1093c003db1fSHoward Hinnantequal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) 10943e519524SHoward Hinnant{ 10953e519524SHoward Hinnant if (__first1.__ctz_ == __first2.__ctz_) 1096781c476cSArthur O'Dwyer return _VSTD::__equal_aligned(__first1, __last1, __first2); 1097781c476cSArthur O'Dwyer return _VSTD::__equal_unaligned(__first1, __last1, __first2); 10983e519524SHoward Hinnant} 10993e519524SHoward Hinnant 11000ae9efebSHoward Hinnanttemplate <class _Cp, bool _IsConst, 11010ae9efebSHoward Hinnant typename _Cp::__storage_type> 11023e519524SHoward Hinnantclass __bit_iterator 11033e519524SHoward Hinnant{ 11043e519524SHoward Hinnantpublic: 1105c003db1fSHoward Hinnant typedef typename _Cp::difference_type difference_type; 11063e519524SHoward Hinnant typedef bool value_type; 11073e519524SHoward Hinnant typedef __bit_iterator pointer; 1108c003db1fSHoward Hinnant typedef typename conditional<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >::type reference; 11093e519524SHoward Hinnant typedef random_access_iterator_tag iterator_category; 11103e519524SHoward Hinnant 11113e519524SHoward Hinnantprivate: 1112c003db1fSHoward Hinnant typedef typename _Cp::__storage_type __storage_type; 1113c003db1fSHoward Hinnant typedef typename conditional<_IsConst, typename _Cp::__const_storage_pointer, 1114c003db1fSHoward Hinnant typename _Cp::__storage_pointer>::type __storage_pointer; 1115c003db1fSHoward Hinnant static const unsigned __bits_per_word = _Cp::__bits_per_word; 11163e519524SHoward Hinnant 11173e519524SHoward Hinnant __storage_pointer __seg_; 11183e519524SHoward Hinnant unsigned __ctz_; 11193e519524SHoward Hinnant 11203e519524SHoward Hinnantpublic: 112136b2a3b0SMarshall Clow _LIBCPP_INLINE_VISIBILITY __bit_iterator() _NOEXCEPT 112236b2a3b0SMarshall Clow#if _LIBCPP_STD_VER > 11 112336b2a3b0SMarshall Clow : __seg_(nullptr), __ctz_(0) 112436b2a3b0SMarshall Clow#endif 112536b2a3b0SMarshall Clow {} 11263e519524SHoward Hinnant 112770d94c3fSArthur O'Dwyer // When _IsConst=false, this is the copy constructor. 112870d94c3fSArthur O'Dwyer // It is non-trivial. Making it trivial would break ABI. 112970d94c3fSArthur O'Dwyer // When _IsConst=true, this is a converting constructor; 113070d94c3fSArthur O'Dwyer // the copy and move constructors are implicitly generated 113170d94c3fSArthur O'Dwyer // and trivial. 1132d368a84cSHoward Hinnant _LIBCPP_INLINE_VISIBILITY 113370d94c3fSArthur O'Dwyer __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT 11343e519524SHoward Hinnant : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {} 11353e519524SHoward Hinnant 113670d94c3fSArthur O'Dwyer // When _IsConst=false, we have a user-provided copy constructor, 113770d94c3fSArthur O'Dwyer // so we must also provide a copy assignment operator because 113870d94c3fSArthur O'Dwyer // the implicit generation of a defaulted one is deprecated. 113970d94c3fSArthur O'Dwyer // When _IsConst=true, the assignment operators are 114070d94c3fSArthur O'Dwyer // implicitly generated and trivial. 1141a829443cSEric Fiselier _LIBCPP_INLINE_VISIBILITY 114270d94c3fSArthur O'Dwyer __bit_iterator& operator=(const _If<_IsConst, struct __private_nat, __bit_iterator>& __it) { 114370d94c3fSArthur O'Dwyer __seg_ = __it.__seg_; 114470d94c3fSArthur O'Dwyer __ctz_ = __it.__ctz_; 114570d94c3fSArthur O'Dwyer return *this; 114670d94c3fSArthur O'Dwyer } 1147a829443cSEric Fiselier 1148d368a84cSHoward Hinnant _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT 1149d368a84cSHoward Hinnant {return reference(__seg_, __storage_type(1) << __ctz_);} 11503e519524SHoward Hinnant 11513e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator++() 11523e519524SHoward Hinnant { 11533e519524SHoward Hinnant if (__ctz_ != __bits_per_word-1) 11543e519524SHoward Hinnant ++__ctz_; 11553e519524SHoward Hinnant else 11563e519524SHoward Hinnant { 11573e519524SHoward Hinnant __ctz_ = 0; 11583e519524SHoward Hinnant ++__seg_; 11593e519524SHoward Hinnant } 11603e519524SHoward Hinnant return *this; 11613e519524SHoward Hinnant } 11623e519524SHoward Hinnant 11633e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator operator++(int) 11643e519524SHoward Hinnant { 11653e519524SHoward Hinnant __bit_iterator __tmp = *this; 11663e519524SHoward Hinnant ++(*this); 11673e519524SHoward Hinnant return __tmp; 11683e519524SHoward Hinnant } 11693e519524SHoward Hinnant 11703e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator--() 11713e519524SHoward Hinnant { 11723e519524SHoward Hinnant if (__ctz_ != 0) 11733e519524SHoward Hinnant --__ctz_; 11743e519524SHoward Hinnant else 11753e519524SHoward Hinnant { 11763e519524SHoward Hinnant __ctz_ = __bits_per_word - 1; 11773e519524SHoward Hinnant --__seg_; 11783e519524SHoward Hinnant } 11793e519524SHoward Hinnant return *this; 11803e519524SHoward Hinnant } 11813e519524SHoward Hinnant 11823e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator operator--(int) 11833e519524SHoward Hinnant { 11843e519524SHoward Hinnant __bit_iterator __tmp = *this; 11853e519524SHoward Hinnant --(*this); 11863e519524SHoward Hinnant return __tmp; 11873e519524SHoward Hinnant } 11883e519524SHoward Hinnant 11893e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator+=(difference_type __n) 11903e519524SHoward Hinnant { 11913e519524SHoward Hinnant if (__n >= 0) 11923e519524SHoward Hinnant __seg_ += (__n + __ctz_) / __bits_per_word; 11933e519524SHoward Hinnant else 11943e519524SHoward Hinnant __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1) 11953e519524SHoward Hinnant / static_cast<difference_type>(__bits_per_word); 11963e519524SHoward Hinnant __n &= (__bits_per_word - 1); 11973e519524SHoward Hinnant __ctz_ = static_cast<unsigned>((__n + __ctz_) % __bits_per_word); 11983e519524SHoward Hinnant return *this; 11993e519524SHoward Hinnant } 12003e519524SHoward Hinnant 12013e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator-=(difference_type __n) 12023e519524SHoward Hinnant { 12033e519524SHoward Hinnant return *this += -__n; 12043e519524SHoward Hinnant } 12053e519524SHoward Hinnant 12063e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator operator+(difference_type __n) const 12073e519524SHoward Hinnant { 12083e519524SHoward Hinnant __bit_iterator __t(*this); 12093e519524SHoward Hinnant __t += __n; 12103e519524SHoward Hinnant return __t; 12113e519524SHoward Hinnant } 12123e519524SHoward Hinnant 12133e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator operator-(difference_type __n) const 12143e519524SHoward Hinnant { 12153e519524SHoward Hinnant __bit_iterator __t(*this); 12163e519524SHoward Hinnant __t -= __n; 12173e519524SHoward Hinnant return __t; 12183e519524SHoward Hinnant } 12193e519524SHoward Hinnant 12203e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 12213e519524SHoward Hinnant friend __bit_iterator operator+(difference_type __n, const __bit_iterator& __it) {return __it + __n;} 12223e519524SHoward Hinnant 12233e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 12243e519524SHoward Hinnant friend difference_type operator-(const __bit_iterator& __x, const __bit_iterator& __y) 12253e519524SHoward Hinnant {return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;} 12263e519524SHoward Hinnant 12273e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const {return *(*this + __n);} 12283e519524SHoward Hinnant 12293e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY friend bool operator==(const __bit_iterator& __x, const __bit_iterator& __y) 12303e519524SHoward Hinnant {return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;} 12313e519524SHoward Hinnant 12323e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY friend bool operator!=(const __bit_iterator& __x, const __bit_iterator& __y) 12333e519524SHoward Hinnant {return !(__x == __y);} 12343e519524SHoward Hinnant 12353e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY friend bool operator<(const __bit_iterator& __x, const __bit_iterator& __y) 12363e519524SHoward Hinnant {return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);} 12373e519524SHoward Hinnant 12383e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY friend bool operator>(const __bit_iterator& __x, const __bit_iterator& __y) 12393e519524SHoward Hinnant {return __y < __x;} 12403e519524SHoward Hinnant 12413e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y) 12423e519524SHoward Hinnant {return !(__y < __x);} 12433e519524SHoward Hinnant 12443e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y) 12453e519524SHoward Hinnant {return !(__x < __y);} 12463e519524SHoward Hinnant 12473e519524SHoward Hinnantprivate: 12483e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 1249d368a84cSHoward Hinnant __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT 1250d368a84cSHoward Hinnant : __seg_(__s), __ctz_(__ctz) {} 12513e519524SHoward Hinnant 1252c003db1fSHoward Hinnant friend typename _Cp::__self; 1253541f9e28SEric Fiselier 1254c003db1fSHoward Hinnant friend class __bit_reference<_Cp>; 1255c003db1fSHoward Hinnant friend class __bit_const_reference<_Cp>; 1256c003db1fSHoward Hinnant friend class __bit_iterator<_Cp, true>; 1257c003db1fSHoward Hinnant template <class _Dp> friend struct __bit_array; 1258c003db1fSHoward Hinnant template <class _Dp> friend void __fill_n_false(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); 1259c003db1fSHoward Hinnant template <class _Dp> friend void __fill_n_true(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); 1260c003db1fSHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_aligned(__bit_iterator<_Dp, _IC> __first, 1261c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC> __last, 1262c003db1fSHoward Hinnant __bit_iterator<_Dp, false> __result); 1263c003db1fSHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_unaligned(__bit_iterator<_Dp, _IC> __first, 1264c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC> __last, 1265c003db1fSHoward Hinnant __bit_iterator<_Dp, false> __result); 1266c003db1fSHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy(__bit_iterator<_Dp, _IC> __first, 1267c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC> __last, 1268c003db1fSHoward Hinnant __bit_iterator<_Dp, false> __result); 1269c003db1fSHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_aligned(__bit_iterator<_Dp, _IC> __first, 1270c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC> __last, 1271c003db1fSHoward Hinnant __bit_iterator<_Dp, false> __result); 1272c003db1fSHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_unaligned(__bit_iterator<_Dp, _IC> __first, 1273c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC> __last, 1274c003db1fSHoward Hinnant __bit_iterator<_Dp, false> __result); 1275c003db1fSHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy_backward(__bit_iterator<_Dp, _IC> __first, 1276c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC> __last, 1277c003db1fSHoward Hinnant __bit_iterator<_Dp, false> __result); 1278dbe81119SHoward Hinnant template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_aligned(__bit_iterator<__C1, false>, 1279dbe81119SHoward Hinnant __bit_iterator<__C1, false>, 1280dbe81119SHoward Hinnant __bit_iterator<__C2, false>); 1281dbe81119SHoward Hinnant template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_unaligned(__bit_iterator<__C1, false>, 1282dbe81119SHoward Hinnant __bit_iterator<__C1, false>, 1283dbe81119SHoward Hinnant __bit_iterator<__C2, false>); 1284dbe81119SHoward Hinnant template <class __C1, class __C2>friend __bit_iterator<__C2, false> swap_ranges(__bit_iterator<__C1, false>, 1285dbe81119SHoward Hinnant __bit_iterator<__C1, false>, 1286dbe81119SHoward Hinnant __bit_iterator<__C2, false>); 1287c003db1fSHoward Hinnant template <class _Dp> friend __bit_iterator<_Dp, false> rotate(__bit_iterator<_Dp, false>, 1288c003db1fSHoward Hinnant __bit_iterator<_Dp, false>, 1289c003db1fSHoward Hinnant __bit_iterator<_Dp, false>); 12901237dccaSHoward Hinnant template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_aligned(__bit_iterator<_Dp, _IC1>, 12911237dccaSHoward Hinnant __bit_iterator<_Dp, _IC1>, 12921237dccaSHoward Hinnant __bit_iterator<_Dp, _IC2>); 12931237dccaSHoward Hinnant template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_unaligned(__bit_iterator<_Dp, _IC1>, 12941237dccaSHoward Hinnant __bit_iterator<_Dp, _IC1>, 12951237dccaSHoward Hinnant __bit_iterator<_Dp, _IC2>); 1296c003db1fSHoward Hinnant template <class _Dp, bool _IC1, bool _IC2> friend bool equal(__bit_iterator<_Dp, _IC1>, 1297c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC1>, 1298c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC2>); 1299423a8d77SHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_true(__bit_iterator<_Dp, _IC>, 1300c003db1fSHoward Hinnant typename _Dp::size_type); 1301423a8d77SHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_false(__bit_iterator<_Dp, _IC>, 1302c003db1fSHoward Hinnant typename _Dp::size_type); 1303423a8d77SHoward Hinnant template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type 1304423a8d77SHoward Hinnant __count_bool_true(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 1305423a8d77SHoward Hinnant template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type 1306423a8d77SHoward Hinnant __count_bool_false(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 13073e519524SHoward Hinnant}; 13083e519524SHoward Hinnant 13093e519524SHoward Hinnant_LIBCPP_END_NAMESPACE_STD 13103e519524SHoward Hinnant 1311a016efb1SEric Fiselier_LIBCPP_POP_MACROS 1312a016efb1SEric Fiselier 13133e519524SHoward Hinnant#endif // _LIBCPP___BIT_REFERENCE 1314