13e519524SHoward Hinnant// -*- C++ -*- 23e519524SHoward Hinnant//===----------------------------------------------------------------------===// 33e519524SHoward Hinnant// 45b08a8a4SHoward Hinnant// The LLVM Compiler Infrastructure 53e519524SHoward Hinnant// 6412dbebeSHoward Hinnant// This file is dual licensed under the MIT and the University of Illinois Open 7412dbebeSHoward Hinnant// Source Licenses. See LICENSE.TXT for details. 83e519524SHoward Hinnant// 93e519524SHoward Hinnant//===----------------------------------------------------------------------===// 103e519524SHoward Hinnant 113e519524SHoward Hinnant#ifndef _LIBCPP___BIT_REFERENCE 123e519524SHoward Hinnant#define _LIBCPP___BIT_REFERENCE 133e519524SHoward Hinnant 143e519524SHoward Hinnant#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 21*a016efb1SEric Fiselier_LIBCPP_PUSH_MACROS 22*a016efb1SEric Fiselier#include <__undef_macros> 23*a016efb1SEric Fiselier 24*a016efb1SEric 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: 50d368a84cSHoward Hinnant _LIBCPP_INLINE_VISIBILITY operator bool() const _NOEXCEPT 51d368a84cSHoward Hinnant {return static_cast<bool>(*__seg_ & __mask_);} 52d368a84cSHoward Hinnant _LIBCPP_INLINE_VISIBILITY bool operator ~() const _NOEXCEPT 53d368a84cSHoward Hinnant {return !static_cast<bool>(*this);} 543e519524SHoward Hinnant 553e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 56d368a84cSHoward Hinnant __bit_reference& operator=(bool __x) _NOEXCEPT 573e519524SHoward Hinnant { 583e519524SHoward Hinnant if (__x) 593e519524SHoward Hinnant *__seg_ |= __mask_; 603e519524SHoward Hinnant else 613e519524SHoward Hinnant *__seg_ &= ~__mask_; 623e519524SHoward Hinnant return *this; 633e519524SHoward Hinnant } 643e519524SHoward Hinnant 653e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 66d368a84cSHoward Hinnant __bit_reference& operator=(const __bit_reference& __x) _NOEXCEPT 67d368a84cSHoward Hinnant {return operator=(static_cast<bool>(__x));} 683e519524SHoward Hinnant 69d368a84cSHoward Hinnant _LIBCPP_INLINE_VISIBILITY void flip() _NOEXCEPT {*__seg_ ^= __mask_;} 70c003db1fSHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, false> operator&() const _NOEXCEPT 71c003db1fSHoward Hinnant {return __bit_iterator<_Cp, false>(__seg_, static_cast<unsigned>(__ctz(__mask_)));} 723e519524SHoward Hinnantprivate: 733e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 74d368a84cSHoward Hinnant __bit_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT 75d368a84cSHoward Hinnant : __seg_(__s), __mask_(__m) {} 763e519524SHoward Hinnant}; 773e519524SHoward Hinnant 78c003db1fSHoward Hinnanttemplate <class _Cp> 79c003db1fSHoward Hinnantclass __bit_reference<_Cp, false> 80a7744562SHoward Hinnant{ 81a7744562SHoward Hinnant}; 82a7744562SHoward Hinnant 83d9db9f90SHoward Hinnanttemplate <class _Cp> 843af48ef7SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 85d9db9f90SHoward Hinnantvoid 86d9db9f90SHoward Hinnantswap(__bit_reference<_Cp> __x, __bit_reference<_Cp> __y) _NOEXCEPT 87d9db9f90SHoward Hinnant{ 88d9db9f90SHoward Hinnant bool __t = __x; 89d9db9f90SHoward Hinnant __x = __y; 90d9db9f90SHoward Hinnant __y = __t; 91d9db9f90SHoward Hinnant} 92d9db9f90SHoward Hinnant 93c003db1fSHoward Hinnanttemplate <class _Cp, class _Dp> 943af48ef7SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 953e519524SHoward Hinnantvoid 96c003db1fSHoward Hinnantswap(__bit_reference<_Cp> __x, __bit_reference<_Dp> __y) _NOEXCEPT 973e519524SHoward Hinnant{ 983e519524SHoward Hinnant bool __t = __x; 993e519524SHoward Hinnant __x = __y; 1003e519524SHoward Hinnant __y = __t; 1013e519524SHoward Hinnant} 1023e519524SHoward Hinnant 103c003db1fSHoward Hinnanttemplate <class _Cp> 1043af48ef7SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 1053e519524SHoward Hinnantvoid 106c003db1fSHoward Hinnantswap(__bit_reference<_Cp> __x, bool& __y) _NOEXCEPT 1073e519524SHoward Hinnant{ 1083e519524SHoward Hinnant bool __t = __x; 1093e519524SHoward Hinnant __x = __y; 1103e519524SHoward Hinnant __y = __t; 1113e519524SHoward Hinnant} 1123e519524SHoward Hinnant 113c003db1fSHoward Hinnanttemplate <class _Cp> 1143af48ef7SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 1153e519524SHoward Hinnantvoid 116c003db1fSHoward Hinnantswap(bool& __x, __bit_reference<_Cp> __y) _NOEXCEPT 1173e519524SHoward Hinnant{ 1183e519524SHoward Hinnant bool __t = __x; 1193e519524SHoward Hinnant __x = __y; 1203e519524SHoward Hinnant __y = __t; 1213e519524SHoward Hinnant} 1223e519524SHoward Hinnant 123c003db1fSHoward Hinnanttemplate <class _Cp> 1243e519524SHoward Hinnantclass __bit_const_reference 1253e519524SHoward Hinnant{ 126c003db1fSHoward Hinnant typedef typename _Cp::__storage_type __storage_type; 127c003db1fSHoward Hinnant typedef typename _Cp::__const_storage_pointer __storage_pointer; 1283e519524SHoward Hinnant 1293e519524SHoward Hinnant __storage_pointer __seg_; 1303e519524SHoward Hinnant __storage_type __mask_; 1313e519524SHoward Hinnant 132c003db1fSHoward Hinnant friend typename _Cp::__self; 133c003db1fSHoward Hinnant friend class __bit_iterator<_Cp, true>; 1343e519524SHoward Hinnantpublic: 1353e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 136c003db1fSHoward Hinnant __bit_const_reference(const __bit_reference<_Cp>& __x) _NOEXCEPT 1373e519524SHoward Hinnant : __seg_(__x.__seg_), __mask_(__x.__mask_) {} 1383e519524SHoward Hinnant 139eeac9fcfSHoward Hinnant _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR operator bool() const _NOEXCEPT 140d368a84cSHoward Hinnant {return static_cast<bool>(*__seg_ & __mask_);} 1413e519524SHoward Hinnant 142c003db1fSHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, true> operator&() const _NOEXCEPT 143c003db1fSHoward Hinnant {return __bit_iterator<_Cp, true>(__seg_, static_cast<unsigned>(__ctz(__mask_)));} 1443e519524SHoward Hinnantprivate: 1453e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 146eeac9fcfSHoward Hinnant _LIBCPP_CONSTEXPR 147d368a84cSHoward Hinnant __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT 148d368a84cSHoward Hinnant : __seg_(__s), __mask_(__m) {} 1493e519524SHoward Hinnant 1503e519524SHoward Hinnant __bit_const_reference& operator=(const __bit_const_reference& __x); 1513e519524SHoward Hinnant}; 1523e519524SHoward Hinnant 1533e519524SHoward Hinnant// find 1543e519524SHoward Hinnant 155423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst> 156423a8d77SHoward Hinnant__bit_iterator<_Cp, _IsConst> 157423a8d77SHoward Hinnant__find_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 1583e519524SHoward Hinnant{ 159423a8d77SHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _It; 1603e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 161aec08784SEric Fiselier static const int __bits_per_word = _It::__bits_per_word; 1623e519524SHoward Hinnant // do first partial word 1633e519524SHoward Hinnant if (__first.__ctz_ != 0) 1643e519524SHoward Hinnant { 1653e519524SHoward Hinnant __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 166ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__clz_f, __n); 1673e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 1683e519524SHoward Hinnant __storage_type __b = *__first.__seg_ & __m; 1693e519524SHoward Hinnant if (__b) 170ce48a113SHoward Hinnant return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 171303e27d8SHoward Hinnant if (__n == __dn) 1720fc6e981SMarshall Clow return __first + __n; 1733e519524SHoward Hinnant __n -= __dn; 1743e519524SHoward Hinnant ++__first.__seg_; 1753e519524SHoward Hinnant } 1763e519524SHoward Hinnant // do middle whole words 1773e519524SHoward Hinnant for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 1783e519524SHoward Hinnant if (*__first.__seg_) 179ce48a113SHoward Hinnant return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(*__first.__seg_))); 1803e519524SHoward Hinnant // do last partial word 1813e519524SHoward Hinnant if (__n > 0) 1823e519524SHoward Hinnant { 1833e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 1843e519524SHoward Hinnant __storage_type __b = *__first.__seg_ & __m; 1853e519524SHoward Hinnant if (__b) 186ce48a113SHoward Hinnant return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 1873e519524SHoward Hinnant } 1883e519524SHoward Hinnant return _It(__first.__seg_, static_cast<unsigned>(__n)); 1893e519524SHoward Hinnant} 1903e519524SHoward Hinnant 191423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst> 192423a8d77SHoward Hinnant__bit_iterator<_Cp, _IsConst> 193423a8d77SHoward Hinnant__find_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 1943e519524SHoward Hinnant{ 195423a8d77SHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _It; 1963e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 197aec08784SEric Fiselier const int __bits_per_word = _It::__bits_per_word; 1983e519524SHoward Hinnant // do first partial word 1993e519524SHoward Hinnant if (__first.__ctz_ != 0) 2003e519524SHoward Hinnant { 2013e519524SHoward Hinnant __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 202ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__clz_f, __n); 2033e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 204423a8d77SHoward Hinnant __storage_type __b = ~*__first.__seg_ & __m; 2053e519524SHoward Hinnant if (__b) 206ce48a113SHoward Hinnant return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 207303e27d8SHoward Hinnant if (__n == __dn) 2080fc6e981SMarshall Clow return __first + __n; 2093e519524SHoward Hinnant __n -= __dn; 2103e519524SHoward Hinnant ++__first.__seg_; 2113e519524SHoward Hinnant } 2123e519524SHoward Hinnant // do middle whole words 2133e519524SHoward Hinnant for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 2143e519524SHoward Hinnant { 2153e519524SHoward Hinnant __storage_type __b = ~*__first.__seg_; 2163e519524SHoward Hinnant if (__b) 217ce48a113SHoward Hinnant return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 2183e519524SHoward Hinnant } 2193e519524SHoward Hinnant // do last partial word 2203e519524SHoward Hinnant if (__n > 0) 2213e519524SHoward Hinnant { 2223e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 223423a8d77SHoward Hinnant __storage_type __b = ~*__first.__seg_ & __m; 2243e519524SHoward Hinnant if (__b) 225ce48a113SHoward Hinnant return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 2263e519524SHoward Hinnant } 2273e519524SHoward Hinnant return _It(__first.__seg_, static_cast<unsigned>(__n)); 2283e519524SHoward Hinnant} 2293e519524SHoward Hinnant 230423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst, class _Tp> 2313e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 232423a8d77SHoward Hinnant__bit_iterator<_Cp, _IsConst> 233423a8d77SHoward Hinnantfind(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_) 2343e519524SHoward Hinnant{ 235e4383379SHoward Hinnant if (static_cast<bool>(__value_)) 236c003db1fSHoward Hinnant return __find_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first)); 237c003db1fSHoward Hinnant return __find_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first)); 2383e519524SHoward Hinnant} 2393e519524SHoward Hinnant 2403e519524SHoward Hinnant// count 2413e519524SHoward Hinnant 242423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst> 243423a8d77SHoward Hinnanttypename __bit_iterator<_Cp, _IsConst>::difference_type 244423a8d77SHoward Hinnant__count_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 2453e519524SHoward Hinnant{ 246423a8d77SHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _It; 2473e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 2483e519524SHoward Hinnant typedef typename _It::difference_type difference_type; 249aec08784SEric Fiselier const int __bits_per_word = _It::__bits_per_word; 2503e519524SHoward Hinnant difference_type __r = 0; 2513e519524SHoward Hinnant // do first partial word 2523e519524SHoward Hinnant if (__first.__ctz_ != 0) 2533e519524SHoward Hinnant { 2543e519524SHoward Hinnant __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 255ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__clz_f, __n); 2563e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 257ce48a113SHoward Hinnant __r = _VSTD::__pop_count(*__first.__seg_ & __m); 2583e519524SHoward Hinnant __n -= __dn; 2593e519524SHoward Hinnant ++__first.__seg_; 2603e519524SHoward Hinnant } 2613e519524SHoward Hinnant // do middle whole words 2623e519524SHoward Hinnant for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 263ce48a113SHoward Hinnant __r += _VSTD::__pop_count(*__first.__seg_); 2643e519524SHoward Hinnant // do last partial word 2653e519524SHoward Hinnant if (__n > 0) 2663e519524SHoward Hinnant { 2673e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 268ce48a113SHoward Hinnant __r += _VSTD::__pop_count(*__first.__seg_ & __m); 2693e519524SHoward Hinnant } 2703e519524SHoward Hinnant return __r; 2713e519524SHoward Hinnant} 2723e519524SHoward Hinnant 273423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst> 274423a8d77SHoward Hinnanttypename __bit_iterator<_Cp, _IsConst>::difference_type 275423a8d77SHoward Hinnant__count_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 2763e519524SHoward Hinnant{ 277423a8d77SHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _It; 2783e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 2793e519524SHoward Hinnant typedef typename _It::difference_type difference_type; 280aec08784SEric Fiselier const int __bits_per_word = _It::__bits_per_word; 2813e519524SHoward Hinnant difference_type __r = 0; 2823e519524SHoward Hinnant // do first partial word 2833e519524SHoward Hinnant if (__first.__ctz_ != 0) 2843e519524SHoward Hinnant { 2853e519524SHoward Hinnant __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 286ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__clz_f, __n); 2873e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 288423a8d77SHoward Hinnant __r = _VSTD::__pop_count(~*__first.__seg_ & __m); 2893e519524SHoward Hinnant __n -= __dn; 2903e519524SHoward Hinnant ++__first.__seg_; 2913e519524SHoward Hinnant } 2923e519524SHoward Hinnant // do middle whole words 2933e519524SHoward Hinnant for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 294ce48a113SHoward Hinnant __r += _VSTD::__pop_count(~*__first.__seg_); 2953e519524SHoward Hinnant // do last partial word 2963e519524SHoward Hinnant if (__n > 0) 2973e519524SHoward Hinnant { 2983e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 299423a8d77SHoward Hinnant __r += _VSTD::__pop_count(~*__first.__seg_ & __m); 3003e519524SHoward Hinnant } 3013e519524SHoward Hinnant return __r; 3023e519524SHoward Hinnant} 3033e519524SHoward Hinnant 304423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst, class _Tp> 3053e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 306423a8d77SHoward Hinnanttypename __bit_iterator<_Cp, _IsConst>::difference_type 307423a8d77SHoward Hinnantcount(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_) 3083e519524SHoward Hinnant{ 309e4383379SHoward Hinnant if (static_cast<bool>(__value_)) 310c003db1fSHoward Hinnant return __count_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first)); 311c003db1fSHoward Hinnant return __count_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first)); 3123e519524SHoward Hinnant} 3133e519524SHoward Hinnant 3143e519524SHoward Hinnant// fill_n 3153e519524SHoward Hinnant 316c003db1fSHoward Hinnanttemplate <class _Cp> 3173e519524SHoward Hinnantvoid 318c003db1fSHoward Hinnant__fill_n_false(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) 3193e519524SHoward Hinnant{ 320c003db1fSHoward Hinnant typedef __bit_iterator<_Cp, false> _It; 3213e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 322aec08784SEric Fiselier const int __bits_per_word = _It::__bits_per_word; 3233e519524SHoward Hinnant // do first partial word 3243e519524SHoward Hinnant if (__first.__ctz_ != 0) 3253e519524SHoward Hinnant { 3263e519524SHoward Hinnant __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 327ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__clz_f, __n); 3283e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 3293e519524SHoward Hinnant *__first.__seg_ &= ~__m; 3303e519524SHoward Hinnant __n -= __dn; 3313e519524SHoward Hinnant ++__first.__seg_; 3323e519524SHoward Hinnant } 3333e519524SHoward Hinnant // do middle whole words 3343e519524SHoward Hinnant __storage_type __nw = __n / __bits_per_word; 3353ec1f00bSHoward Hinnant _VSTD::memset(_VSTD::__to_raw_pointer(__first.__seg_), 0, __nw * sizeof(__storage_type)); 3363e519524SHoward Hinnant __n -= __nw * __bits_per_word; 3373e519524SHoward Hinnant // do last partial word 3383e519524SHoward Hinnant if (__n > 0) 3393e519524SHoward Hinnant { 3403e519524SHoward Hinnant __first.__seg_ += __nw; 3413e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 3423e519524SHoward Hinnant *__first.__seg_ &= ~__m; 3433e519524SHoward Hinnant } 3443e519524SHoward Hinnant} 3453e519524SHoward Hinnant 346c003db1fSHoward Hinnanttemplate <class _Cp> 3473e519524SHoward Hinnantvoid 348c003db1fSHoward Hinnant__fill_n_true(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) 3493e519524SHoward Hinnant{ 350c003db1fSHoward Hinnant typedef __bit_iterator<_Cp, false> _It; 3513e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 352aec08784SEric Fiselier const int __bits_per_word = _It::__bits_per_word; 3533e519524SHoward Hinnant // do first partial word 3543e519524SHoward Hinnant if (__first.__ctz_ != 0) 3553e519524SHoward Hinnant { 3563e519524SHoward Hinnant __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 357ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__clz_f, __n); 3583e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 3593e519524SHoward Hinnant *__first.__seg_ |= __m; 3603e519524SHoward Hinnant __n -= __dn; 3613e519524SHoward Hinnant ++__first.__seg_; 3623e519524SHoward Hinnant } 3633e519524SHoward Hinnant // do middle whole words 3643e519524SHoward Hinnant __storage_type __nw = __n / __bits_per_word; 3653ec1f00bSHoward Hinnant _VSTD::memset(_VSTD::__to_raw_pointer(__first.__seg_), -1, __nw * sizeof(__storage_type)); 3663e519524SHoward Hinnant __n -= __nw * __bits_per_word; 3673e519524SHoward Hinnant // do last partial word 3683e519524SHoward Hinnant if (__n > 0) 3693e519524SHoward Hinnant { 3703e519524SHoward Hinnant __first.__seg_ += __nw; 3713e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 3723e519524SHoward Hinnant *__first.__seg_ |= __m; 3733e519524SHoward Hinnant } 3743e519524SHoward Hinnant} 3753e519524SHoward Hinnant 376c003db1fSHoward Hinnanttemplate <class _Cp> 3773af48ef7SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 3783e519524SHoward Hinnantvoid 379c003db1fSHoward Hinnantfill_n(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n, bool __value_) 3803e519524SHoward Hinnant{ 3813e519524SHoward Hinnant if (__n > 0) 3823e519524SHoward Hinnant { 383e4383379SHoward Hinnant if (__value_) 3843e519524SHoward Hinnant __fill_n_true(__first, __n); 3853e519524SHoward Hinnant else 3863e519524SHoward Hinnant __fill_n_false(__first, __n); 3873e519524SHoward Hinnant } 3883e519524SHoward Hinnant} 3893e519524SHoward Hinnant 3903e519524SHoward Hinnant// fill 3913e519524SHoward Hinnant 392c003db1fSHoward Hinnanttemplate <class _Cp> 3933e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 3943e519524SHoward Hinnantvoid 395c003db1fSHoward Hinnantfill(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __last, bool __value_) 3963e519524SHoward Hinnant{ 397c003db1fSHoward Hinnant _VSTD::fill_n(__first, static_cast<typename _Cp::size_type>(__last - __first), __value_); 3983e519524SHoward Hinnant} 3993e519524SHoward Hinnant 4003e519524SHoward Hinnant// copy 4013e519524SHoward Hinnant 402c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 403c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 404c003db1fSHoward Hinnant__copy_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 405c003db1fSHoward Hinnant __bit_iterator<_Cp, false> __result) 4063e519524SHoward Hinnant{ 407c003db1fSHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _In; 4083e519524SHoward Hinnant typedef typename _In::difference_type difference_type; 4093e519524SHoward Hinnant typedef typename _In::__storage_type __storage_type; 410aec08784SEric Fiselier const int __bits_per_word = _In::__bits_per_word; 4113e519524SHoward Hinnant difference_type __n = __last - __first; 4123e519524SHoward Hinnant if (__n > 0) 4133e519524SHoward Hinnant { 4143e519524SHoward Hinnant // do first word 4153e519524SHoward Hinnant if (__first.__ctz_ != 0) 4163e519524SHoward Hinnant { 4173e519524SHoward Hinnant unsigned __clz = __bits_per_word - __first.__ctz_; 418ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 4193e519524SHoward Hinnant __n -= __dn; 4203e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 4213e519524SHoward Hinnant __storage_type __b = *__first.__seg_ & __m; 4223e519524SHoward Hinnant *__result.__seg_ &= ~__m; 4233e519524SHoward Hinnant *__result.__seg_ |= __b; 4243e519524SHoward Hinnant __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 4253e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 4263e519524SHoward Hinnant ++__first.__seg_; 4273e519524SHoward Hinnant // __first.__ctz_ = 0; 4283e519524SHoward Hinnant } 4293e519524SHoward Hinnant // __first.__ctz_ == 0; 4303e519524SHoward Hinnant // do middle words 4313e519524SHoward Hinnant __storage_type __nw = __n / __bits_per_word; 4323ec1f00bSHoward Hinnant _VSTD::memmove(_VSTD::__to_raw_pointer(__result.__seg_), 4333ec1f00bSHoward Hinnant _VSTD::__to_raw_pointer(__first.__seg_), 4343ec1f00bSHoward Hinnant __nw * sizeof(__storage_type)); 4353e519524SHoward Hinnant __n -= __nw * __bits_per_word; 4363e519524SHoward Hinnant __result.__seg_ += __nw; 4373e519524SHoward Hinnant // do last word 4383e519524SHoward Hinnant if (__n > 0) 4393e519524SHoward Hinnant { 4403e519524SHoward Hinnant __first.__seg_ += __nw; 4413e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 4423e519524SHoward Hinnant __storage_type __b = *__first.__seg_ & __m; 4433e519524SHoward Hinnant *__result.__seg_ &= ~__m; 4443e519524SHoward Hinnant *__result.__seg_ |= __b; 4453e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(__n); 4463e519524SHoward Hinnant } 4473e519524SHoward Hinnant } 4483e519524SHoward Hinnant return __result; 4493e519524SHoward Hinnant} 4503e519524SHoward Hinnant 451c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 452c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 453c003db1fSHoward Hinnant__copy_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 454c003db1fSHoward Hinnant __bit_iterator<_Cp, false> __result) 4553e519524SHoward Hinnant{ 456c003db1fSHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _In; 4573e519524SHoward Hinnant typedef typename _In::difference_type difference_type; 4583e519524SHoward Hinnant typedef typename _In::__storage_type __storage_type; 459aec08784SEric Fiselier static const int __bits_per_word = _In::__bits_per_word; 4603e519524SHoward Hinnant difference_type __n = __last - __first; 4613e519524SHoward Hinnant if (__n > 0) 4623e519524SHoward Hinnant { 4633e519524SHoward Hinnant // do first word 4643e519524SHoward Hinnant if (__first.__ctz_ != 0) 4653e519524SHoward Hinnant { 4663e519524SHoward Hinnant unsigned __clz_f = __bits_per_word - __first.__ctz_; 467ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 4683e519524SHoward Hinnant __n -= __dn; 4693e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 4703e519524SHoward Hinnant __storage_type __b = *__first.__seg_ & __m; 4713e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __result.__ctz_; 472ce48a113SHoward Hinnant __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 4733e519524SHoward Hinnant __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 4743e519524SHoward Hinnant *__result.__seg_ &= ~__m; 4753e519524SHoward Hinnant if (__result.__ctz_ > __first.__ctz_) 4763e519524SHoward Hinnant *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_); 4773e519524SHoward Hinnant else 4783e519524SHoward Hinnant *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_); 4793e519524SHoward Hinnant __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 4803e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 4813e519524SHoward Hinnant __dn -= __ddn; 4823e519524SHoward Hinnant if (__dn > 0) 4833e519524SHoward Hinnant { 4843e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __dn); 4853e519524SHoward Hinnant *__result.__seg_ &= ~__m; 4863e519524SHoward Hinnant *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn); 4873e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(__dn); 4883e519524SHoward Hinnant } 4893e519524SHoward Hinnant ++__first.__seg_; 4903e519524SHoward Hinnant // __first.__ctz_ = 0; 4913e519524SHoward Hinnant } 4923e519524SHoward Hinnant // __first.__ctz_ == 0; 4933e519524SHoward Hinnant // do middle words 4943e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __result.__ctz_; 4953e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) << __result.__ctz_; 4963e519524SHoward Hinnant for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 4973e519524SHoward Hinnant { 4983e519524SHoward Hinnant __storage_type __b = *__first.__seg_; 4993e519524SHoward Hinnant *__result.__seg_ &= ~__m; 5003e519524SHoward Hinnant *__result.__seg_ |= __b << __result.__ctz_; 5013e519524SHoward Hinnant ++__result.__seg_; 5023e519524SHoward Hinnant *__result.__seg_ &= __m; 5033e519524SHoward Hinnant *__result.__seg_ |= __b >> __clz_r; 5043e519524SHoward Hinnant } 5053e519524SHoward Hinnant // do last word 5063e519524SHoward Hinnant if (__n > 0) 5073e519524SHoward Hinnant { 5083e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __n); 5093e519524SHoward Hinnant __storage_type __b = *__first.__seg_ & __m; 510ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); 5113e519524SHoward Hinnant __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 5123e519524SHoward Hinnant *__result.__seg_ &= ~__m; 5133e519524SHoward Hinnant *__result.__seg_ |= __b << __result.__ctz_; 5143e519524SHoward Hinnant __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 5153e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 5163e519524SHoward Hinnant __n -= __dn; 5173e519524SHoward Hinnant if (__n > 0) 5183e519524SHoward Hinnant { 5193e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __n); 5203e519524SHoward Hinnant *__result.__seg_ &= ~__m; 5213e519524SHoward Hinnant *__result.__seg_ |= __b >> __dn; 5223e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(__n); 5233e519524SHoward Hinnant } 5243e519524SHoward Hinnant } 5253e519524SHoward Hinnant } 5263e519524SHoward Hinnant return __result; 5273e519524SHoward Hinnant} 5283e519524SHoward Hinnant 529c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 5303e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 531c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 532c003db1fSHoward Hinnantcopy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 5333e519524SHoward Hinnant{ 5343e519524SHoward Hinnant if (__first.__ctz_ == __result.__ctz_) 5353e519524SHoward Hinnant return __copy_aligned(__first, __last, __result); 5363e519524SHoward Hinnant return __copy_unaligned(__first, __last, __result); 5373e519524SHoward Hinnant} 5383e519524SHoward Hinnant 5393e519524SHoward Hinnant// copy_backward 5403e519524SHoward Hinnant 541c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 542c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 543c003db1fSHoward Hinnant__copy_backward_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 544c003db1fSHoward Hinnant __bit_iterator<_Cp, false> __result) 5453e519524SHoward Hinnant{ 546c003db1fSHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _In; 5473e519524SHoward Hinnant typedef typename _In::difference_type difference_type; 5483e519524SHoward Hinnant typedef typename _In::__storage_type __storage_type; 549aec08784SEric Fiselier const int __bits_per_word = _In::__bits_per_word; 5503e519524SHoward Hinnant difference_type __n = __last - __first; 5513e519524SHoward Hinnant if (__n > 0) 5523e519524SHoward Hinnant { 5533e519524SHoward Hinnant // do first word 5543e519524SHoward Hinnant if (__last.__ctz_ != 0) 5553e519524SHoward Hinnant { 556ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); 5573e519524SHoward Hinnant __n -= __dn; 5583e519524SHoward Hinnant unsigned __clz = __bits_per_word - __last.__ctz_; 5593e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz); 5603e519524SHoward Hinnant __storage_type __b = *__last.__seg_ & __m; 5613e519524SHoward Hinnant *__result.__seg_ &= ~__m; 5623e519524SHoward Hinnant *__result.__seg_ |= __b; 5633e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 5643e519524SHoward Hinnant __result.__ctz_) % __bits_per_word); 5653e519524SHoward Hinnant // __last.__ctz_ = 0 5663e519524SHoward Hinnant } 5673e519524SHoward Hinnant // __last.__ctz_ == 0 || __n == 0 5683e519524SHoward Hinnant // __result.__ctz_ == 0 || __n == 0 5693e519524SHoward Hinnant // do middle words 5703e519524SHoward Hinnant __storage_type __nw = __n / __bits_per_word; 5713e519524SHoward Hinnant __result.__seg_ -= __nw; 5723e519524SHoward Hinnant __last.__seg_ -= __nw; 5733ec1f00bSHoward Hinnant _VSTD::memmove(_VSTD::__to_raw_pointer(__result.__seg_), 5743ec1f00bSHoward Hinnant _VSTD::__to_raw_pointer(__last.__seg_), 5753ec1f00bSHoward Hinnant __nw * sizeof(__storage_type)); 5763e519524SHoward Hinnant __n -= __nw * __bits_per_word; 5773e519524SHoward Hinnant // do last word 5783e519524SHoward Hinnant if (__n > 0) 5793e519524SHoward Hinnant { 5803e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n); 5813e519524SHoward Hinnant __storage_type __b = *--__last.__seg_ & __m; 5823e519524SHoward Hinnant *--__result.__seg_ &= ~__m; 5833e519524SHoward Hinnant *__result.__seg_ |= __b; 5843e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 5853e519524SHoward Hinnant } 5863e519524SHoward Hinnant } 5873e519524SHoward Hinnant return __result; 5883e519524SHoward Hinnant} 5893e519524SHoward Hinnant 590c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 591c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 592c003db1fSHoward Hinnant__copy_backward_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 593c003db1fSHoward Hinnant __bit_iterator<_Cp, false> __result) 5943e519524SHoward Hinnant{ 595c003db1fSHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _In; 5963e519524SHoward Hinnant typedef typename _In::difference_type difference_type; 5973e519524SHoward Hinnant typedef typename _In::__storage_type __storage_type; 598aec08784SEric Fiselier const int __bits_per_word = _In::__bits_per_word; 5993e519524SHoward Hinnant difference_type __n = __last - __first; 6003e519524SHoward Hinnant if (__n > 0) 6013e519524SHoward Hinnant { 6023e519524SHoward Hinnant // do first word 6033e519524SHoward Hinnant if (__last.__ctz_ != 0) 6043e519524SHoward Hinnant { 605ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); 6063e519524SHoward Hinnant __n -= __dn; 6073e519524SHoward Hinnant unsigned __clz_l = __bits_per_word - __last.__ctz_; 6083e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l); 6093e519524SHoward Hinnant __storage_type __b = *__last.__seg_ & __m; 6103e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __result.__ctz_; 611ce48a113SHoward Hinnant __storage_type __ddn = _VSTD::min(__dn, static_cast<difference_type>(__result.__ctz_)); 6123e519524SHoward Hinnant if (__ddn > 0) 6133e519524SHoward Hinnant { 6143e519524SHoward Hinnant __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r); 6153e519524SHoward Hinnant *__result.__seg_ &= ~__m; 6163e519524SHoward Hinnant if (__result.__ctz_ > __last.__ctz_) 6173e519524SHoward Hinnant *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 6183e519524SHoward Hinnant else 6193e519524SHoward Hinnant *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_); 6203e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) + 6213e519524SHoward Hinnant __result.__ctz_) % __bits_per_word); 6223e519524SHoward Hinnant __dn -= __ddn; 6233e519524SHoward Hinnant } 6243e519524SHoward Hinnant if (__dn > 0) 6253e519524SHoward Hinnant { 6263e519524SHoward Hinnant // __result.__ctz_ == 0 6273e519524SHoward Hinnant --__result.__seg_; 6283e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1)); 6293e519524SHoward Hinnant __m = ~__storage_type(0) << __result.__ctz_; 6303e519524SHoward Hinnant *__result.__seg_ &= ~__m; 6313e519524SHoward Hinnant __last.__ctz_ -= __dn + __ddn; 6323e519524SHoward Hinnant *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 6333e519524SHoward Hinnant } 6343e519524SHoward Hinnant // __last.__ctz_ = 0 6353e519524SHoward Hinnant } 6363e519524SHoward Hinnant // __last.__ctz_ == 0 || __n == 0 6373e519524SHoward Hinnant // __result.__ctz_ != 0 || __n == 0 6383e519524SHoward Hinnant // do middle words 6393e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __result.__ctz_; 6403e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> __clz_r; 6413e519524SHoward Hinnant for (; __n >= __bits_per_word; __n -= __bits_per_word) 6423e519524SHoward Hinnant { 6433e519524SHoward Hinnant __storage_type __b = *--__last.__seg_; 6443e519524SHoward Hinnant *__result.__seg_ &= ~__m; 6453e519524SHoward Hinnant *__result.__seg_ |= __b >> __clz_r; 6463e519524SHoward Hinnant *--__result.__seg_ &= __m; 6473e519524SHoward Hinnant *__result.__seg_ |= __b << __result.__ctz_; 6483e519524SHoward Hinnant } 6493e519524SHoward Hinnant // do last word 6503e519524SHoward Hinnant if (__n > 0) 6513e519524SHoward Hinnant { 6523e519524SHoward Hinnant __m = ~__storage_type(0) << (__bits_per_word - __n); 6533e519524SHoward Hinnant __storage_type __b = *--__last.__seg_ & __m; 654c206366fSHoward Hinnant __clz_r = __bits_per_word - __result.__ctz_; 655ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__result.__ctz_)); 6563e519524SHoward Hinnant __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r); 6573e519524SHoward Hinnant *__result.__seg_ &= ~__m; 6583e519524SHoward Hinnant *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_); 6593e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 6603e519524SHoward Hinnant __result.__ctz_) % __bits_per_word); 6613e519524SHoward Hinnant __n -= __dn; 6623e519524SHoward Hinnant if (__n > 0) 6633e519524SHoward Hinnant { 6643e519524SHoward Hinnant // __result.__ctz_ == 0 6653e519524SHoward Hinnant --__result.__seg_; 6663e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 6673e519524SHoward Hinnant __m = ~__storage_type(0) << __result.__ctz_; 6683e519524SHoward Hinnant *__result.__seg_ &= ~__m; 6693e519524SHoward Hinnant *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn)); 6703e519524SHoward Hinnant } 6713e519524SHoward Hinnant } 6723e519524SHoward Hinnant } 6733e519524SHoward Hinnant return __result; 6743e519524SHoward Hinnant} 6753e519524SHoward Hinnant 676c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 6773e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 678c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 679c003db1fSHoward Hinnantcopy_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 6803e519524SHoward Hinnant{ 6813e519524SHoward Hinnant if (__last.__ctz_ == __result.__ctz_) 6823e519524SHoward Hinnant return __copy_backward_aligned(__first, __last, __result); 6833e519524SHoward Hinnant return __copy_backward_unaligned(__first, __last, __result); 6843e519524SHoward Hinnant} 6853e519524SHoward Hinnant 6863e519524SHoward Hinnant// move 6873e519524SHoward Hinnant 688c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 6893e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 690c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 691c003db1fSHoward Hinnantmove(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 6923e519524SHoward Hinnant{ 693ce48a113SHoward Hinnant return _VSTD::copy(__first, __last, __result); 6943e519524SHoward Hinnant} 6953e519524SHoward Hinnant 6963e519524SHoward Hinnant// move_backward 6973e519524SHoward Hinnant 698c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 6993e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 700c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 701c003db1fSHoward Hinnantmove_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 7023e519524SHoward Hinnant{ 70308de4b0dSMarshall Clow return _VSTD::copy_backward(__first, __last, __result); 7043e519524SHoward Hinnant} 7053e519524SHoward Hinnant 7063e519524SHoward Hinnant// swap_ranges 7073e519524SHoward Hinnant 708dbe81119SHoward Hinnanttemplate <class __C1, class __C2> 709dbe81119SHoward Hinnant__bit_iterator<__C2, false> 710dbe81119SHoward Hinnant__swap_ranges_aligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, 711dbe81119SHoward Hinnant __bit_iterator<__C2, false> __result) 7123e519524SHoward Hinnant{ 713dbe81119SHoward Hinnant typedef __bit_iterator<__C1, false> _I1; 7143e519524SHoward Hinnant typedef typename _I1::difference_type difference_type; 7153e519524SHoward Hinnant typedef typename _I1::__storage_type __storage_type; 716aec08784SEric Fiselier const int __bits_per_word = _I1::__bits_per_word; 7173e519524SHoward Hinnant difference_type __n = __last - __first; 7183e519524SHoward Hinnant if (__n > 0) 7193e519524SHoward Hinnant { 7203e519524SHoward Hinnant // do first word 7213e519524SHoward Hinnant if (__first.__ctz_ != 0) 7223e519524SHoward Hinnant { 7233e519524SHoward Hinnant unsigned __clz = __bits_per_word - __first.__ctz_; 724ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 7253e519524SHoward Hinnant __n -= __dn; 7263e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 7273e519524SHoward Hinnant __storage_type __b1 = *__first.__seg_ & __m; 7283e519524SHoward Hinnant *__first.__seg_ &= ~__m; 7293e519524SHoward Hinnant __storage_type __b2 = *__result.__seg_ & __m; 7303e519524SHoward Hinnant *__result.__seg_ &= ~__m; 7313e519524SHoward Hinnant *__result.__seg_ |= __b1; 7323e519524SHoward Hinnant *__first.__seg_ |= __b2; 7333e519524SHoward Hinnant __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 7343e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 7353e519524SHoward Hinnant ++__first.__seg_; 7363e519524SHoward Hinnant // __first.__ctz_ = 0; 7373e519524SHoward Hinnant } 7383e519524SHoward Hinnant // __first.__ctz_ == 0; 7393e519524SHoward Hinnant // do middle words 7403e519524SHoward Hinnant for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_) 7413e519524SHoward Hinnant swap(*__first.__seg_, *__result.__seg_); 7423e519524SHoward Hinnant // do last word 7433e519524SHoward Hinnant if (__n > 0) 7443e519524SHoward Hinnant { 7453e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 7463e519524SHoward Hinnant __storage_type __b1 = *__first.__seg_ & __m; 7473e519524SHoward Hinnant *__first.__seg_ &= ~__m; 7483e519524SHoward Hinnant __storage_type __b2 = *__result.__seg_ & __m; 7493e519524SHoward Hinnant *__result.__seg_ &= ~__m; 7503e519524SHoward Hinnant *__result.__seg_ |= __b1; 7513e519524SHoward Hinnant *__first.__seg_ |= __b2; 7523e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(__n); 7533e519524SHoward Hinnant } 7543e519524SHoward Hinnant } 7553e519524SHoward Hinnant return __result; 7563e519524SHoward Hinnant} 7573e519524SHoward Hinnant 758dbe81119SHoward Hinnanttemplate <class __C1, class __C2> 759dbe81119SHoward Hinnant__bit_iterator<__C2, false> 760dbe81119SHoward Hinnant__swap_ranges_unaligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, 761dbe81119SHoward Hinnant __bit_iterator<__C2, false> __result) 7623e519524SHoward Hinnant{ 763dbe81119SHoward Hinnant typedef __bit_iterator<__C1, false> _I1; 7643e519524SHoward Hinnant typedef typename _I1::difference_type difference_type; 7653e519524SHoward Hinnant typedef typename _I1::__storage_type __storage_type; 766aec08784SEric Fiselier const int __bits_per_word = _I1::__bits_per_word; 7673e519524SHoward Hinnant difference_type __n = __last - __first; 7683e519524SHoward Hinnant if (__n > 0) 7693e519524SHoward Hinnant { 7703e519524SHoward Hinnant // do first word 7713e519524SHoward Hinnant if (__first.__ctz_ != 0) 7723e519524SHoward Hinnant { 7733e519524SHoward Hinnant unsigned __clz_f = __bits_per_word - __first.__ctz_; 774ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 7753e519524SHoward Hinnant __n -= __dn; 7763e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 7773e519524SHoward Hinnant __storage_type __b1 = *__first.__seg_ & __m; 7783e519524SHoward Hinnant *__first.__seg_ &= ~__m; 7793e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __result.__ctz_; 780ce48a113SHoward Hinnant __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 7813e519524SHoward Hinnant __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 7823e519524SHoward Hinnant __storage_type __b2 = *__result.__seg_ & __m; 7833e519524SHoward Hinnant *__result.__seg_ &= ~__m; 7843e519524SHoward Hinnant if (__result.__ctz_ > __first.__ctz_) 7853e519524SHoward Hinnant { 7863e519524SHoward Hinnant unsigned __s = __result.__ctz_ - __first.__ctz_; 7873e519524SHoward Hinnant *__result.__seg_ |= __b1 << __s; 7883e519524SHoward Hinnant *__first.__seg_ |= __b2 >> __s; 7893e519524SHoward Hinnant } 7903e519524SHoward Hinnant else 7913e519524SHoward Hinnant { 7923e519524SHoward Hinnant unsigned __s = __first.__ctz_ - __result.__ctz_; 7933e519524SHoward Hinnant *__result.__seg_ |= __b1 >> __s; 7943e519524SHoward Hinnant *__first.__seg_ |= __b2 << __s; 7953e519524SHoward Hinnant } 7963e519524SHoward Hinnant __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 7973e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 7983e519524SHoward Hinnant __dn -= __ddn; 7993e519524SHoward Hinnant if (__dn > 0) 8003e519524SHoward Hinnant { 8013e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __dn); 8023e519524SHoward Hinnant __b2 = *__result.__seg_ & __m; 8033e519524SHoward Hinnant *__result.__seg_ &= ~__m; 8043e519524SHoward Hinnant unsigned __s = __first.__ctz_ + __ddn; 8053e519524SHoward Hinnant *__result.__seg_ |= __b1 >> __s; 8063e519524SHoward Hinnant *__first.__seg_ |= __b2 << __s; 8073e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(__dn); 8083e519524SHoward Hinnant } 8093e519524SHoward Hinnant ++__first.__seg_; 8103e519524SHoward Hinnant // __first.__ctz_ = 0; 8113e519524SHoward Hinnant } 8123e519524SHoward Hinnant // __first.__ctz_ == 0; 8133e519524SHoward Hinnant // do middle words 8143e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) << __result.__ctz_; 8153e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __result.__ctz_; 8163e519524SHoward Hinnant for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 8173e519524SHoward Hinnant { 8183e519524SHoward Hinnant __storage_type __b1 = *__first.__seg_; 8193e519524SHoward Hinnant __storage_type __b2 = *__result.__seg_ & __m; 8203e519524SHoward Hinnant *__result.__seg_ &= ~__m; 8213e519524SHoward Hinnant *__result.__seg_ |= __b1 << __result.__ctz_; 8223e519524SHoward Hinnant *__first.__seg_ = __b2 >> __result.__ctz_; 8233e519524SHoward Hinnant ++__result.__seg_; 8243e519524SHoward Hinnant __b2 = *__result.__seg_ & ~__m; 8253e519524SHoward Hinnant *__result.__seg_ &= __m; 8263e519524SHoward Hinnant *__result.__seg_ |= __b1 >> __clz_r; 8273e519524SHoward Hinnant *__first.__seg_ |= __b2 << __clz_r; 8283e519524SHoward Hinnant } 8293e519524SHoward Hinnant // do last word 8303e519524SHoward Hinnant if (__n > 0) 8313e519524SHoward Hinnant { 8323e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __n); 8333e519524SHoward Hinnant __storage_type __b1 = *__first.__seg_ & __m; 8343e519524SHoward Hinnant *__first.__seg_ &= ~__m; 835ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min<__storage_type>(__n, __clz_r); 8363e519524SHoward Hinnant __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 8373e519524SHoward Hinnant __storage_type __b2 = *__result.__seg_ & __m; 8383e519524SHoward Hinnant *__result.__seg_ &= ~__m; 8393e519524SHoward Hinnant *__result.__seg_ |= __b1 << __result.__ctz_; 8403e519524SHoward Hinnant *__first.__seg_ |= __b2 >> __result.__ctz_; 8413e519524SHoward Hinnant __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 8423e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 8433e519524SHoward Hinnant __n -= __dn; 8443e519524SHoward Hinnant if (__n > 0) 8453e519524SHoward Hinnant { 8463e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __n); 8473e519524SHoward Hinnant __b2 = *__result.__seg_ & __m; 8483e519524SHoward Hinnant *__result.__seg_ &= ~__m; 8493e519524SHoward Hinnant *__result.__seg_ |= __b1 >> __dn; 8503e519524SHoward Hinnant *__first.__seg_ |= __b2 << __dn; 8513e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(__n); 8523e519524SHoward Hinnant } 8533e519524SHoward Hinnant } 8543e519524SHoward Hinnant } 8553e519524SHoward Hinnant return __result; 8563e519524SHoward Hinnant} 8573e519524SHoward Hinnant 858dbe81119SHoward Hinnanttemplate <class __C1, class __C2> 8593e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 860dbe81119SHoward Hinnant__bit_iterator<__C2, false> 861dbe81119SHoward Hinnantswap_ranges(__bit_iterator<__C1, false> __first1, __bit_iterator<__C1, false> __last1, 862dbe81119SHoward Hinnant __bit_iterator<__C2, false> __first2) 8633e519524SHoward Hinnant{ 8643e519524SHoward Hinnant if (__first1.__ctz_ == __first2.__ctz_) 8653e519524SHoward Hinnant return __swap_ranges_aligned(__first1, __last1, __first2); 8663e519524SHoward Hinnant return __swap_ranges_unaligned(__first1, __last1, __first2); 8673e519524SHoward Hinnant} 8683e519524SHoward Hinnant 8693e519524SHoward Hinnant// rotate 8703e519524SHoward Hinnant 871c003db1fSHoward Hinnanttemplate <class _Cp> 8723e519524SHoward Hinnantstruct __bit_array 8733e519524SHoward Hinnant{ 874c003db1fSHoward Hinnant typedef typename _Cp::difference_type difference_type; 875c003db1fSHoward Hinnant typedef typename _Cp::__storage_type __storage_type; 8763ec1f00bSHoward Hinnant typedef typename _Cp::__storage_pointer __storage_pointer; 877c003db1fSHoward Hinnant typedef typename _Cp::iterator iterator; 878c003db1fSHoward Hinnant static const unsigned __bits_per_word = _Cp::__bits_per_word; 879c003db1fSHoward Hinnant static const unsigned _Np = 4; 8803e519524SHoward Hinnant 8813e519524SHoward Hinnant difference_type __size_; 882c003db1fSHoward Hinnant __storage_type __word_[_Np]; 8833e519524SHoward Hinnant 8843e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY static difference_type capacity() 885c003db1fSHoward Hinnant {return static_cast<difference_type>(_Np * __bits_per_word);} 8863e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY explicit __bit_array(difference_type __s) : __size_(__s) {} 8873ec1f00bSHoward Hinnant _LIBCPP_INLINE_VISIBILITY iterator begin() 8883ec1f00bSHoward Hinnant { 8893ec1f00bSHoward Hinnant return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]), 0); 8903ec1f00bSHoward Hinnant } 8913ec1f00bSHoward Hinnant _LIBCPP_INLINE_VISIBILITY iterator end() 8923ec1f00bSHoward Hinnant { 8933ec1f00bSHoward Hinnant return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]) + __size_ / __bits_per_word, 8943ec1f00bSHoward Hinnant static_cast<unsigned>(__size_ % __bits_per_word)); 8953ec1f00bSHoward Hinnant } 8963e519524SHoward Hinnant}; 8973e519524SHoward Hinnant 898c003db1fSHoward Hinnanttemplate <class _Cp> 899c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 900c003db1fSHoward Hinnantrotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last) 9013e519524SHoward Hinnant{ 902c003db1fSHoward Hinnant typedef __bit_iterator<_Cp, false> _I1; 9033e519524SHoward Hinnant typedef typename _I1::difference_type difference_type; 9043e519524SHoward Hinnant difference_type __d1 = __middle - __first; 9053e519524SHoward Hinnant difference_type __d2 = __last - __middle; 9063e519524SHoward Hinnant _I1 __r = __first + __d2; 9073e519524SHoward Hinnant while (__d1 != 0 && __d2 != 0) 9083e519524SHoward Hinnant { 9093e519524SHoward Hinnant if (__d1 <= __d2) 9103e519524SHoward Hinnant { 911c003db1fSHoward Hinnant if (__d1 <= __bit_array<_Cp>::capacity()) 9123e519524SHoward Hinnant { 913c003db1fSHoward Hinnant __bit_array<_Cp> __b(__d1); 914ce48a113SHoward Hinnant _VSTD::copy(__first, __middle, __b.begin()); 915ce48a113SHoward Hinnant _VSTD::copy(__b.begin(), __b.end(), _VSTD::copy(__middle, __last, __first)); 9163e519524SHoward Hinnant break; 9173e519524SHoward Hinnant } 9183e519524SHoward Hinnant else 9193e519524SHoward Hinnant { 920c003db1fSHoward Hinnant __bit_iterator<_Cp, false> __mp = _VSTD::swap_ranges(__first, __middle, __middle); 9213e519524SHoward Hinnant __first = __middle; 9223e519524SHoward Hinnant __middle = __mp; 9233e519524SHoward Hinnant __d2 -= __d1; 9243e519524SHoward Hinnant } 9253e519524SHoward Hinnant } 9263e519524SHoward Hinnant else 9273e519524SHoward Hinnant { 928c003db1fSHoward Hinnant if (__d2 <= __bit_array<_Cp>::capacity()) 9293e519524SHoward Hinnant { 930c003db1fSHoward Hinnant __bit_array<_Cp> __b(__d2); 931ce48a113SHoward Hinnant _VSTD::copy(__middle, __last, __b.begin()); 932ce48a113SHoward Hinnant _VSTD::copy_backward(__b.begin(), __b.end(), _VSTD::copy_backward(__first, __middle, __last)); 9333e519524SHoward Hinnant break; 9343e519524SHoward Hinnant } 9353e519524SHoward Hinnant else 9363e519524SHoward Hinnant { 937c003db1fSHoward Hinnant __bit_iterator<_Cp, false> __mp = __first + __d2; 938ce48a113SHoward Hinnant _VSTD::swap_ranges(__first, __mp, __middle); 9393e519524SHoward Hinnant __first = __mp; 9403e519524SHoward Hinnant __d1 -= __d2; 9413e519524SHoward Hinnant } 9423e519524SHoward Hinnant } 9433e519524SHoward Hinnant } 9443e519524SHoward Hinnant return __r; 9453e519524SHoward Hinnant} 9463e519524SHoward Hinnant 9473e519524SHoward Hinnant// equal 9483e519524SHoward Hinnant 9491237dccaSHoward Hinnanttemplate <class _Cp, bool _IC1, bool _IC2> 9503e519524SHoward Hinnantbool 9511237dccaSHoward Hinnant__equal_unaligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, 9521237dccaSHoward Hinnant __bit_iterator<_Cp, _IC2> __first2) 9533e519524SHoward Hinnant{ 9541237dccaSHoward Hinnant typedef __bit_iterator<_Cp, _IC1> _It; 9553e519524SHoward Hinnant typedef typename _It::difference_type difference_type; 9563e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 957aec08784SEric Fiselier static const int __bits_per_word = _It::__bits_per_word; 9583e519524SHoward Hinnant difference_type __n = __last1 - __first1; 9593e519524SHoward Hinnant if (__n > 0) 9603e519524SHoward Hinnant { 9613e519524SHoward Hinnant // do first word 9623e519524SHoward Hinnant if (__first1.__ctz_ != 0) 9633e519524SHoward Hinnant { 9643e519524SHoward Hinnant unsigned __clz_f = __bits_per_word - __first1.__ctz_; 965ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 9663e519524SHoward Hinnant __n -= __dn; 9673e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 9683e519524SHoward Hinnant __storage_type __b = *__first1.__seg_ & __m; 9693e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __first2.__ctz_; 970ce48a113SHoward Hinnant __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 9713e519524SHoward Hinnant __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 9723e519524SHoward Hinnant if (__first2.__ctz_ > __first1.__ctz_) 9734c0de496SHoward Hinnant { 9743e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_))) 9753e519524SHoward Hinnant return false; 9764c0de496SHoward Hinnant } 9773e519524SHoward Hinnant else 9784c0de496SHoward Hinnant { 9793e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_))) 9803e519524SHoward Hinnant return false; 9814c0de496SHoward Hinnant } 9823e519524SHoward Hinnant __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word; 9833e519524SHoward Hinnant __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word); 9843e519524SHoward Hinnant __dn -= __ddn; 9853e519524SHoward Hinnant if (__dn > 0) 9863e519524SHoward Hinnant { 9873e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __dn); 9883e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn))) 9893e519524SHoward Hinnant return false; 9903e519524SHoward Hinnant __first2.__ctz_ = static_cast<unsigned>(__dn); 9913e519524SHoward Hinnant } 9923e519524SHoward Hinnant ++__first1.__seg_; 9933e519524SHoward Hinnant // __first1.__ctz_ = 0; 9943e519524SHoward Hinnant } 9953e519524SHoward Hinnant // __first1.__ctz_ == 0; 9963e519524SHoward Hinnant // do middle words 9973e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __first2.__ctz_; 9983e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) << __first2.__ctz_; 9993e519524SHoward Hinnant for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_) 10003e519524SHoward Hinnant { 10013e519524SHoward Hinnant __storage_type __b = *__first1.__seg_; 10023e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 10033e519524SHoward Hinnant return false; 10043e519524SHoward Hinnant ++__first2.__seg_; 10053e519524SHoward Hinnant if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r)) 10063e519524SHoward Hinnant return false; 10073e519524SHoward Hinnant } 10083e519524SHoward Hinnant // do last word 10093e519524SHoward Hinnant if (__n > 0) 10103e519524SHoward Hinnant { 10113e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __n); 10123e519524SHoward Hinnant __storage_type __b = *__first1.__seg_ & __m; 1013ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); 10143e519524SHoward Hinnant __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 10153e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 10163e519524SHoward Hinnant return false; 10173e519524SHoward Hinnant __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word; 10183e519524SHoward Hinnant __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word); 10193e519524SHoward Hinnant __n -= __dn; 10203e519524SHoward Hinnant if (__n > 0) 10213e519524SHoward Hinnant { 10223e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __n); 10233e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (__b >> __dn)) 10243e519524SHoward Hinnant return false; 10253e519524SHoward Hinnant } 10263e519524SHoward Hinnant } 10273e519524SHoward Hinnant } 10283e519524SHoward Hinnant return true; 10293e519524SHoward Hinnant} 10303e519524SHoward Hinnant 10311237dccaSHoward Hinnanttemplate <class _Cp, bool _IC1, bool _IC2> 10323e519524SHoward Hinnantbool 10331237dccaSHoward Hinnant__equal_aligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, 10341237dccaSHoward Hinnant __bit_iterator<_Cp, _IC2> __first2) 10353e519524SHoward Hinnant{ 10361237dccaSHoward Hinnant typedef __bit_iterator<_Cp, _IC1> _It; 10373e519524SHoward Hinnant typedef typename _It::difference_type difference_type; 10383e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 1039aec08784SEric Fiselier static const int __bits_per_word = _It::__bits_per_word; 10403e519524SHoward Hinnant difference_type __n = __last1 - __first1; 10413e519524SHoward Hinnant if (__n > 0) 10423e519524SHoward Hinnant { 10433e519524SHoward Hinnant // do first word 10443e519524SHoward Hinnant if (__first1.__ctz_ != 0) 10453e519524SHoward Hinnant { 10463e519524SHoward Hinnant unsigned __clz = __bits_per_word - __first1.__ctz_; 1047ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 10483e519524SHoward Hinnant __n -= __dn; 10493e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 10503e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 10513e519524SHoward Hinnant return false; 10523e519524SHoward Hinnant ++__first2.__seg_; 10533e519524SHoward Hinnant ++__first1.__seg_; 10543e519524SHoward Hinnant // __first1.__ctz_ = 0; 10553e519524SHoward Hinnant // __first2.__ctz_ = 0; 10563e519524SHoward Hinnant } 10573e519524SHoward Hinnant // __first1.__ctz_ == 0; 10583e519524SHoward Hinnant // __first2.__ctz_ == 0; 10593e519524SHoward Hinnant // do middle words 10603e519524SHoward Hinnant for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_) 10613e519524SHoward Hinnant if (*__first2.__seg_ != *__first1.__seg_) 10623e519524SHoward Hinnant return false; 10633e519524SHoward Hinnant // do last word 10643e519524SHoward Hinnant if (__n > 0) 10653e519524SHoward Hinnant { 10663e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 10673e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 10683e519524SHoward Hinnant return false; 10693e519524SHoward Hinnant } 10703e519524SHoward Hinnant } 10713e519524SHoward Hinnant return true; 10723e519524SHoward Hinnant} 10733e519524SHoward Hinnant 1074c003db1fSHoward Hinnanttemplate <class _Cp, bool _IC1, bool _IC2> 107543d99238SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 10763e519524SHoward Hinnantbool 1077c003db1fSHoward Hinnantequal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) 10783e519524SHoward Hinnant{ 10793e519524SHoward Hinnant if (__first1.__ctz_ == __first2.__ctz_) 10803e519524SHoward Hinnant return __equal_aligned(__first1, __last1, __first2); 10813e519524SHoward Hinnant return __equal_unaligned(__first1, __last1, __first2); 10823e519524SHoward Hinnant} 10833e519524SHoward Hinnant 10840ae9efebSHoward Hinnanttemplate <class _Cp, bool _IsConst, 10850ae9efebSHoward Hinnant typename _Cp::__storage_type> 10863e519524SHoward Hinnantclass __bit_iterator 10873e519524SHoward Hinnant{ 10883e519524SHoward Hinnantpublic: 1089c003db1fSHoward Hinnant typedef typename _Cp::difference_type difference_type; 10903e519524SHoward Hinnant typedef bool value_type; 10913e519524SHoward Hinnant typedef __bit_iterator pointer; 1092c003db1fSHoward Hinnant typedef typename conditional<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >::type reference; 10933e519524SHoward Hinnant typedef random_access_iterator_tag iterator_category; 10943e519524SHoward Hinnant 10953e519524SHoward Hinnantprivate: 1096c003db1fSHoward Hinnant typedef typename _Cp::__storage_type __storage_type; 1097c003db1fSHoward Hinnant typedef typename conditional<_IsConst, typename _Cp::__const_storage_pointer, 1098c003db1fSHoward Hinnant typename _Cp::__storage_pointer>::type __storage_pointer; 1099c003db1fSHoward Hinnant static const unsigned __bits_per_word = _Cp::__bits_per_word; 11003e519524SHoward Hinnant 11013e519524SHoward Hinnant __storage_pointer __seg_; 11023e519524SHoward Hinnant unsigned __ctz_; 11033e519524SHoward Hinnant 11043e519524SHoward Hinnantpublic: 110536b2a3b0SMarshall Clow _LIBCPP_INLINE_VISIBILITY __bit_iterator() _NOEXCEPT 110636b2a3b0SMarshall Clow#if _LIBCPP_STD_VER > 11 110736b2a3b0SMarshall Clow : __seg_(nullptr), __ctz_(0) 110836b2a3b0SMarshall Clow#endif 110936b2a3b0SMarshall Clow {} 11103e519524SHoward Hinnant 1111d368a84cSHoward Hinnant _LIBCPP_INLINE_VISIBILITY 1112c003db1fSHoward Hinnant __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT 11133e519524SHoward Hinnant : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {} 11143e519524SHoward Hinnant 1115d368a84cSHoward Hinnant _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT 1116d368a84cSHoward Hinnant {return reference(__seg_, __storage_type(1) << __ctz_);} 11173e519524SHoward Hinnant 11183e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator++() 11193e519524SHoward Hinnant { 11203e519524SHoward Hinnant if (__ctz_ != __bits_per_word-1) 11213e519524SHoward Hinnant ++__ctz_; 11223e519524SHoward Hinnant else 11233e519524SHoward Hinnant { 11243e519524SHoward Hinnant __ctz_ = 0; 11253e519524SHoward Hinnant ++__seg_; 11263e519524SHoward Hinnant } 11273e519524SHoward Hinnant return *this; 11283e519524SHoward Hinnant } 11293e519524SHoward Hinnant 11303e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator operator++(int) 11313e519524SHoward Hinnant { 11323e519524SHoward Hinnant __bit_iterator __tmp = *this; 11333e519524SHoward Hinnant ++(*this); 11343e519524SHoward Hinnant return __tmp; 11353e519524SHoward Hinnant } 11363e519524SHoward Hinnant 11373e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator--() 11383e519524SHoward Hinnant { 11393e519524SHoward Hinnant if (__ctz_ != 0) 11403e519524SHoward Hinnant --__ctz_; 11413e519524SHoward Hinnant else 11423e519524SHoward Hinnant { 11433e519524SHoward Hinnant __ctz_ = __bits_per_word - 1; 11443e519524SHoward Hinnant --__seg_; 11453e519524SHoward Hinnant } 11463e519524SHoward Hinnant return *this; 11473e519524SHoward Hinnant } 11483e519524SHoward Hinnant 11493e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator operator--(int) 11503e519524SHoward Hinnant { 11513e519524SHoward Hinnant __bit_iterator __tmp = *this; 11523e519524SHoward Hinnant --(*this); 11533e519524SHoward Hinnant return __tmp; 11543e519524SHoward Hinnant } 11553e519524SHoward Hinnant 11563e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator+=(difference_type __n) 11573e519524SHoward Hinnant { 11583e519524SHoward Hinnant if (__n >= 0) 11593e519524SHoward Hinnant __seg_ += (__n + __ctz_) / __bits_per_word; 11603e519524SHoward Hinnant else 11613e519524SHoward Hinnant __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1) 11623e519524SHoward Hinnant / static_cast<difference_type>(__bits_per_word); 11633e519524SHoward Hinnant __n &= (__bits_per_word - 1); 11643e519524SHoward Hinnant __ctz_ = static_cast<unsigned>((__n + __ctz_) % __bits_per_word); 11653e519524SHoward Hinnant return *this; 11663e519524SHoward Hinnant } 11673e519524SHoward Hinnant 11683e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator-=(difference_type __n) 11693e519524SHoward Hinnant { 11703e519524SHoward Hinnant return *this += -__n; 11713e519524SHoward Hinnant } 11723e519524SHoward Hinnant 11733e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator operator+(difference_type __n) const 11743e519524SHoward Hinnant { 11753e519524SHoward Hinnant __bit_iterator __t(*this); 11763e519524SHoward Hinnant __t += __n; 11773e519524SHoward Hinnant return __t; 11783e519524SHoward Hinnant } 11793e519524SHoward Hinnant 11803e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator operator-(difference_type __n) const 11813e519524SHoward Hinnant { 11823e519524SHoward Hinnant __bit_iterator __t(*this); 11833e519524SHoward Hinnant __t -= __n; 11843e519524SHoward Hinnant return __t; 11853e519524SHoward Hinnant } 11863e519524SHoward Hinnant 11873e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 11883e519524SHoward Hinnant friend __bit_iterator operator+(difference_type __n, const __bit_iterator& __it) {return __it + __n;} 11893e519524SHoward Hinnant 11903e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 11913e519524SHoward Hinnant friend difference_type operator-(const __bit_iterator& __x, const __bit_iterator& __y) 11923e519524SHoward Hinnant {return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;} 11933e519524SHoward Hinnant 11943e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const {return *(*this + __n);} 11953e519524SHoward Hinnant 11963e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY friend bool operator==(const __bit_iterator& __x, const __bit_iterator& __y) 11973e519524SHoward Hinnant {return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;} 11983e519524SHoward Hinnant 11993e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY friend bool operator!=(const __bit_iterator& __x, const __bit_iterator& __y) 12003e519524SHoward Hinnant {return !(__x == __y);} 12013e519524SHoward Hinnant 12023e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY friend bool operator<(const __bit_iterator& __x, const __bit_iterator& __y) 12033e519524SHoward Hinnant {return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);} 12043e519524SHoward Hinnant 12053e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY friend bool operator>(const __bit_iterator& __x, const __bit_iterator& __y) 12063e519524SHoward Hinnant {return __y < __x;} 12073e519524SHoward Hinnant 12083e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y) 12093e519524SHoward Hinnant {return !(__y < __x);} 12103e519524SHoward Hinnant 12113e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y) 12123e519524SHoward Hinnant {return !(__x < __y);} 12133e519524SHoward Hinnant 12143e519524SHoward Hinnantprivate: 12153e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 1216d368a84cSHoward Hinnant __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT 1217d368a84cSHoward Hinnant : __seg_(__s), __ctz_(__ctz) {} 12183e519524SHoward Hinnant 1219c003db1fSHoward Hinnant friend typename _Cp::__self; 1220541f9e28SEric Fiselier 1221c003db1fSHoward Hinnant friend class __bit_reference<_Cp>; 1222c003db1fSHoward Hinnant friend class __bit_const_reference<_Cp>; 1223c003db1fSHoward Hinnant friend class __bit_iterator<_Cp, true>; 1224c003db1fSHoward Hinnant template <class _Dp> friend struct __bit_array; 1225c003db1fSHoward Hinnant template <class _Dp> friend void __fill_n_false(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); 1226c003db1fSHoward Hinnant template <class _Dp> friend void __fill_n_true(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); 1227c003db1fSHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_aligned(__bit_iterator<_Dp, _IC> __first, 1228c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC> __last, 1229c003db1fSHoward Hinnant __bit_iterator<_Dp, false> __result); 1230c003db1fSHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_unaligned(__bit_iterator<_Dp, _IC> __first, 1231c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC> __last, 1232c003db1fSHoward Hinnant __bit_iterator<_Dp, false> __result); 1233c003db1fSHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy(__bit_iterator<_Dp, _IC> __first, 1234c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC> __last, 1235c003db1fSHoward Hinnant __bit_iterator<_Dp, false> __result); 1236c003db1fSHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_aligned(__bit_iterator<_Dp, _IC> __first, 1237c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC> __last, 1238c003db1fSHoward Hinnant __bit_iterator<_Dp, false> __result); 1239c003db1fSHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_unaligned(__bit_iterator<_Dp, _IC> __first, 1240c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC> __last, 1241c003db1fSHoward Hinnant __bit_iterator<_Dp, false> __result); 1242c003db1fSHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy_backward(__bit_iterator<_Dp, _IC> __first, 1243c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC> __last, 1244c003db1fSHoward Hinnant __bit_iterator<_Dp, false> __result); 1245dbe81119SHoward Hinnant template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_aligned(__bit_iterator<__C1, false>, 1246dbe81119SHoward Hinnant __bit_iterator<__C1, false>, 1247dbe81119SHoward Hinnant __bit_iterator<__C2, false>); 1248dbe81119SHoward Hinnant template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_unaligned(__bit_iterator<__C1, false>, 1249dbe81119SHoward Hinnant __bit_iterator<__C1, false>, 1250dbe81119SHoward Hinnant __bit_iterator<__C2, false>); 1251dbe81119SHoward Hinnant template <class __C1, class __C2>friend __bit_iterator<__C2, false> swap_ranges(__bit_iterator<__C1, false>, 1252dbe81119SHoward Hinnant __bit_iterator<__C1, false>, 1253dbe81119SHoward Hinnant __bit_iterator<__C2, false>); 1254c003db1fSHoward Hinnant template <class _Dp> friend __bit_iterator<_Dp, false> rotate(__bit_iterator<_Dp, false>, 1255c003db1fSHoward Hinnant __bit_iterator<_Dp, false>, 1256c003db1fSHoward Hinnant __bit_iterator<_Dp, false>); 12571237dccaSHoward Hinnant template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_aligned(__bit_iterator<_Dp, _IC1>, 12581237dccaSHoward Hinnant __bit_iterator<_Dp, _IC1>, 12591237dccaSHoward Hinnant __bit_iterator<_Dp, _IC2>); 12601237dccaSHoward Hinnant template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_unaligned(__bit_iterator<_Dp, _IC1>, 12611237dccaSHoward Hinnant __bit_iterator<_Dp, _IC1>, 12621237dccaSHoward Hinnant __bit_iterator<_Dp, _IC2>); 1263c003db1fSHoward Hinnant template <class _Dp, bool _IC1, bool _IC2> friend bool equal(__bit_iterator<_Dp, _IC1>, 1264c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC1>, 1265c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC2>); 1266423a8d77SHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_true(__bit_iterator<_Dp, _IC>, 1267c003db1fSHoward Hinnant typename _Dp::size_type); 1268423a8d77SHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_false(__bit_iterator<_Dp, _IC>, 1269c003db1fSHoward Hinnant typename _Dp::size_type); 1270423a8d77SHoward Hinnant template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type 1271423a8d77SHoward Hinnant __count_bool_true(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 1272423a8d77SHoward Hinnant template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type 1273423a8d77SHoward Hinnant __count_bool_false(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 12743e519524SHoward Hinnant}; 12753e519524SHoward Hinnant 12763e519524SHoward Hinnant_LIBCPP_END_NAMESPACE_STD 12773e519524SHoward Hinnant 1278*a016efb1SEric Fiselier_LIBCPP_POP_MACROS 1279*a016efb1SEric Fiselier 12803e519524SHoward Hinnant#endif // _LIBCPP___BIT_REFERENCE 1281