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 17ab4f4382SHoward Hinnant#include <__undef_min_max> 18ab4f4382SHoward Hinnant 19073458b1SHoward Hinnant#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 203e519524SHoward Hinnant#pragma GCC system_header 21073458b1SHoward Hinnant#endif 223e519524SHoward Hinnant 233e519524SHoward Hinnant_LIBCPP_BEGIN_NAMESPACE_STD 243e519524SHoward Hinnant 250ae9efebSHoward Hinnanttemplate <class _Cp, bool _IsConst, typename _Cp::__storage_type = 0> class __bit_iterator; 26c003db1fSHoward Hinnanttemplate <class _Cp> class __bit_const_reference; 273e519524SHoward Hinnant 28a7744562SHoward Hinnanttemplate <class _Tp> 29a7744562SHoward Hinnantstruct __has_storage_type 30a7744562SHoward Hinnant{ 31a7744562SHoward Hinnant static const bool value = false; 32a7744562SHoward Hinnant}; 33a7744562SHoward Hinnant 34c003db1fSHoward Hinnanttemplate <class _Cp, bool = __has_storage_type<_Cp>::value> 353e519524SHoward Hinnantclass __bit_reference 363e519524SHoward Hinnant{ 37c003db1fSHoward Hinnant typedef typename _Cp::__storage_type __storage_type; 38c003db1fSHoward Hinnant typedef typename _Cp::__storage_pointer __storage_pointer; 393e519524SHoward Hinnant 403e519524SHoward Hinnant __storage_pointer __seg_; 413e519524SHoward Hinnant __storage_type __mask_; 423e519524SHoward Hinnant 433e519524SHoward Hinnant#if defined(__clang__) 44c003db1fSHoward Hinnant friend typename _Cp::__self; 453e519524SHoward Hinnant#else 46c003db1fSHoward Hinnant friend class _Cp::__self; 473e519524SHoward Hinnant#endif 48c003db1fSHoward Hinnant friend class __bit_const_reference<_Cp>; 49c003db1fSHoward Hinnant friend class __bit_iterator<_Cp, false>; 503e519524SHoward Hinnantpublic: 51d368a84cSHoward Hinnant _LIBCPP_INLINE_VISIBILITY operator bool() const _NOEXCEPT 52d368a84cSHoward Hinnant {return static_cast<bool>(*__seg_ & __mask_);} 53d368a84cSHoward Hinnant _LIBCPP_INLINE_VISIBILITY bool operator ~() const _NOEXCEPT 54d368a84cSHoward Hinnant {return !static_cast<bool>(*this);} 553e519524SHoward Hinnant 563e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 57d368a84cSHoward Hinnant __bit_reference& operator=(bool __x) _NOEXCEPT 583e519524SHoward Hinnant { 593e519524SHoward Hinnant if (__x) 603e519524SHoward Hinnant *__seg_ |= __mask_; 613e519524SHoward Hinnant else 623e519524SHoward Hinnant *__seg_ &= ~__mask_; 633e519524SHoward Hinnant return *this; 643e519524SHoward Hinnant } 653e519524SHoward Hinnant 663e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 67d368a84cSHoward Hinnant __bit_reference& operator=(const __bit_reference& __x) _NOEXCEPT 68d368a84cSHoward Hinnant {return operator=(static_cast<bool>(__x));} 693e519524SHoward Hinnant 70d368a84cSHoward Hinnant _LIBCPP_INLINE_VISIBILITY void flip() _NOEXCEPT {*__seg_ ^= __mask_;} 71c003db1fSHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, false> operator&() const _NOEXCEPT 72c003db1fSHoward Hinnant {return __bit_iterator<_Cp, false>(__seg_, static_cast<unsigned>(__ctz(__mask_)));} 733e519524SHoward Hinnantprivate: 743e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 75d368a84cSHoward Hinnant __bit_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT 76d368a84cSHoward Hinnant : __seg_(__s), __mask_(__m) {} 773e519524SHoward Hinnant}; 783e519524SHoward Hinnant 79c003db1fSHoward Hinnanttemplate <class _Cp> 80c003db1fSHoward Hinnantclass __bit_reference<_Cp, false> 81a7744562SHoward Hinnant{ 82a7744562SHoward Hinnant}; 83a7744562SHoward Hinnant 84*d9db9f90SHoward Hinnanttemplate <class _Cp> 85*d9db9f90SHoward Hinnant_LIBCPP_INLINE_VISIBILITY inline 86*d9db9f90SHoward Hinnantvoid 87*d9db9f90SHoward Hinnantswap(__bit_reference<_Cp> __x, __bit_reference<_Cp> __y) _NOEXCEPT 88*d9db9f90SHoward Hinnant{ 89*d9db9f90SHoward Hinnant bool __t = __x; 90*d9db9f90SHoward Hinnant __x = __y; 91*d9db9f90SHoward Hinnant __y = __t; 92*d9db9f90SHoward Hinnant} 93*d9db9f90SHoward Hinnant 94c003db1fSHoward Hinnanttemplate <class _Cp, class _Dp> 953e519524SHoward Hinnant_LIBCPP_INLINE_VISIBILITY inline 963e519524SHoward Hinnantvoid 97c003db1fSHoward Hinnantswap(__bit_reference<_Cp> __x, __bit_reference<_Dp> __y) _NOEXCEPT 983e519524SHoward Hinnant{ 993e519524SHoward Hinnant bool __t = __x; 1003e519524SHoward Hinnant __x = __y; 1013e519524SHoward Hinnant __y = __t; 1023e519524SHoward Hinnant} 1033e519524SHoward Hinnant 104c003db1fSHoward Hinnanttemplate <class _Cp> 1053e519524SHoward Hinnant_LIBCPP_INLINE_VISIBILITY inline 1063e519524SHoward Hinnantvoid 107c003db1fSHoward Hinnantswap(__bit_reference<_Cp> __x, bool& __y) _NOEXCEPT 1083e519524SHoward Hinnant{ 1093e519524SHoward Hinnant bool __t = __x; 1103e519524SHoward Hinnant __x = __y; 1113e519524SHoward Hinnant __y = __t; 1123e519524SHoward Hinnant} 1133e519524SHoward Hinnant 114c003db1fSHoward Hinnanttemplate <class _Cp> 1153e519524SHoward Hinnant_LIBCPP_INLINE_VISIBILITY inline 1163e519524SHoward Hinnantvoid 117c003db1fSHoward Hinnantswap(bool& __x, __bit_reference<_Cp> __y) _NOEXCEPT 1183e519524SHoward Hinnant{ 1193e519524SHoward Hinnant bool __t = __x; 1203e519524SHoward Hinnant __x = __y; 1213e519524SHoward Hinnant __y = __t; 1223e519524SHoward Hinnant} 1233e519524SHoward Hinnant 124c003db1fSHoward Hinnanttemplate <class _Cp> 1253e519524SHoward Hinnantclass __bit_const_reference 1263e519524SHoward Hinnant{ 127c003db1fSHoward Hinnant typedef typename _Cp::__storage_type __storage_type; 128c003db1fSHoward Hinnant typedef typename _Cp::__const_storage_pointer __storage_pointer; 1293e519524SHoward Hinnant 1303e519524SHoward Hinnant __storage_pointer __seg_; 1313e519524SHoward Hinnant __storage_type __mask_; 1323e519524SHoward Hinnant 1333e519524SHoward Hinnant#if defined(__clang__) 134c003db1fSHoward Hinnant friend typename _Cp::__self; 1353e519524SHoward Hinnant#else 136c003db1fSHoward Hinnant friend class _Cp::__self; 1373e519524SHoward Hinnant#endif 138c003db1fSHoward Hinnant friend class __bit_iterator<_Cp, true>; 1393e519524SHoward Hinnantpublic: 1403e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 141c003db1fSHoward Hinnant __bit_const_reference(const __bit_reference<_Cp>& __x) _NOEXCEPT 1423e519524SHoward Hinnant : __seg_(__x.__seg_), __mask_(__x.__mask_) {} 1433e519524SHoward Hinnant 144eeac9fcfSHoward Hinnant _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR operator bool() const _NOEXCEPT 145d368a84cSHoward Hinnant {return static_cast<bool>(*__seg_ & __mask_);} 1463e519524SHoward Hinnant 147c003db1fSHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, true> operator&() const _NOEXCEPT 148c003db1fSHoward Hinnant {return __bit_iterator<_Cp, true>(__seg_, static_cast<unsigned>(__ctz(__mask_)));} 1493e519524SHoward Hinnantprivate: 1503e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 151eeac9fcfSHoward Hinnant _LIBCPP_CONSTEXPR 152d368a84cSHoward Hinnant __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT 153d368a84cSHoward Hinnant : __seg_(__s), __mask_(__m) {} 1543e519524SHoward Hinnant 1553e519524SHoward Hinnant __bit_const_reference& operator=(const __bit_const_reference& __x); 1563e519524SHoward Hinnant}; 1573e519524SHoward Hinnant 1583e519524SHoward Hinnant// find 1593e519524SHoward Hinnant 160423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst> 161423a8d77SHoward Hinnant__bit_iterator<_Cp, _IsConst> 162423a8d77SHoward Hinnant__find_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 1633e519524SHoward Hinnant{ 164423a8d77SHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _It; 1653e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 1663e519524SHoward Hinnant static const unsigned __bits_per_word = _It::__bits_per_word; 1673e519524SHoward Hinnant // do first partial word 1683e519524SHoward Hinnant if (__first.__ctz_ != 0) 1693e519524SHoward Hinnant { 1703e519524SHoward Hinnant __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 171ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__clz_f, __n); 1723e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 1733e519524SHoward Hinnant __storage_type __b = *__first.__seg_ & __m; 1743e519524SHoward Hinnant if (__b) 175ce48a113SHoward Hinnant return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 1763e519524SHoward Hinnant __n -= __dn; 1773e519524SHoward Hinnant ++__first.__seg_; 1783e519524SHoward Hinnant } 1793e519524SHoward Hinnant // do middle whole words 1803e519524SHoward Hinnant for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 1813e519524SHoward Hinnant if (*__first.__seg_) 182ce48a113SHoward Hinnant return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(*__first.__seg_))); 1833e519524SHoward Hinnant // do last partial word 1843e519524SHoward Hinnant if (__n > 0) 1853e519524SHoward Hinnant { 1863e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 1873e519524SHoward Hinnant __storage_type __b = *__first.__seg_ & __m; 1883e519524SHoward Hinnant if (__b) 189ce48a113SHoward Hinnant return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 1903e519524SHoward Hinnant } 1913e519524SHoward Hinnant return _It(__first.__seg_, static_cast<unsigned>(__n)); 1923e519524SHoward Hinnant} 1933e519524SHoward Hinnant 194423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst> 195423a8d77SHoward Hinnant__bit_iterator<_Cp, _IsConst> 196423a8d77SHoward Hinnant__find_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 1973e519524SHoward Hinnant{ 198423a8d77SHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _It; 1993e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 2003e519524SHoward Hinnant static const unsigned __bits_per_word = _It::__bits_per_word; 2013e519524SHoward Hinnant // do first partial word 2023e519524SHoward Hinnant if (__first.__ctz_ != 0) 2033e519524SHoward Hinnant { 2043e519524SHoward Hinnant __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 205ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__clz_f, __n); 2063e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 207423a8d77SHoward Hinnant __storage_type __b = ~*__first.__seg_ & __m; 2083e519524SHoward Hinnant if (__b) 209ce48a113SHoward Hinnant return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 2103e519524SHoward Hinnant __n -= __dn; 2113e519524SHoward Hinnant ++__first.__seg_; 2123e519524SHoward Hinnant } 2133e519524SHoward Hinnant // do middle whole words 2143e519524SHoward Hinnant for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 2153e519524SHoward Hinnant { 2163e519524SHoward Hinnant __storage_type __b = ~*__first.__seg_; 2173e519524SHoward Hinnant if (__b) 218ce48a113SHoward Hinnant return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 2193e519524SHoward Hinnant } 2203e519524SHoward Hinnant // do last partial word 2213e519524SHoward Hinnant if (__n > 0) 2223e519524SHoward Hinnant { 2233e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 224423a8d77SHoward Hinnant __storage_type __b = ~*__first.__seg_ & __m; 2253e519524SHoward Hinnant if (__b) 226ce48a113SHoward Hinnant return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 2273e519524SHoward Hinnant } 2283e519524SHoward Hinnant return _It(__first.__seg_, static_cast<unsigned>(__n)); 2293e519524SHoward Hinnant} 2303e519524SHoward Hinnant 231423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst, class _Tp> 2323e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 233423a8d77SHoward Hinnant__bit_iterator<_Cp, _IsConst> 234423a8d77SHoward Hinnantfind(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_) 2353e519524SHoward Hinnant{ 236e4383379SHoward Hinnant if (static_cast<bool>(__value_)) 237c003db1fSHoward Hinnant return __find_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first)); 238c003db1fSHoward Hinnant return __find_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first)); 2393e519524SHoward Hinnant} 2403e519524SHoward Hinnant 2413e519524SHoward Hinnant// count 2423e519524SHoward Hinnant 243423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst> 244423a8d77SHoward Hinnanttypename __bit_iterator<_Cp, _IsConst>::difference_type 245423a8d77SHoward Hinnant__count_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 2463e519524SHoward Hinnant{ 247423a8d77SHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _It; 2483e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 2493e519524SHoward Hinnant typedef typename _It::difference_type difference_type; 2503e519524SHoward Hinnant static const unsigned __bits_per_word = _It::__bits_per_word; 2513e519524SHoward Hinnant difference_type __r = 0; 2523e519524SHoward Hinnant // do first partial word 2533e519524SHoward Hinnant if (__first.__ctz_ != 0) 2543e519524SHoward Hinnant { 2553e519524SHoward Hinnant __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 256ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__clz_f, __n); 2573e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 258ce48a113SHoward Hinnant __r = _VSTD::__pop_count(*__first.__seg_ & __m); 2593e519524SHoward Hinnant __n -= __dn; 2603e519524SHoward Hinnant ++__first.__seg_; 2613e519524SHoward Hinnant } 2623e519524SHoward Hinnant // do middle whole words 2633e519524SHoward Hinnant for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 264ce48a113SHoward Hinnant __r += _VSTD::__pop_count(*__first.__seg_); 2653e519524SHoward Hinnant // do last partial word 2663e519524SHoward Hinnant if (__n > 0) 2673e519524SHoward Hinnant { 2683e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 269ce48a113SHoward Hinnant __r += _VSTD::__pop_count(*__first.__seg_ & __m); 2703e519524SHoward Hinnant } 2713e519524SHoward Hinnant return __r; 2723e519524SHoward Hinnant} 2733e519524SHoward Hinnant 274423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst> 275423a8d77SHoward Hinnanttypename __bit_iterator<_Cp, _IsConst>::difference_type 276423a8d77SHoward Hinnant__count_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 2773e519524SHoward Hinnant{ 278423a8d77SHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _It; 2793e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 2803e519524SHoward Hinnant typedef typename _It::difference_type difference_type; 2813e519524SHoward Hinnant static const unsigned __bits_per_word = _It::__bits_per_word; 2823e519524SHoward Hinnant difference_type __r = 0; 2833e519524SHoward Hinnant // do first partial word 2843e519524SHoward Hinnant if (__first.__ctz_ != 0) 2853e519524SHoward Hinnant { 2863e519524SHoward Hinnant __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 287ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__clz_f, __n); 2883e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 289423a8d77SHoward Hinnant __r = _VSTD::__pop_count(~*__first.__seg_ & __m); 2903e519524SHoward Hinnant __n -= __dn; 2913e519524SHoward Hinnant ++__first.__seg_; 2923e519524SHoward Hinnant } 2933e519524SHoward Hinnant // do middle whole words 2943e519524SHoward Hinnant for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 295ce48a113SHoward Hinnant __r += _VSTD::__pop_count(~*__first.__seg_); 2963e519524SHoward Hinnant // do last partial word 2973e519524SHoward Hinnant if (__n > 0) 2983e519524SHoward Hinnant { 2993e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 300423a8d77SHoward Hinnant __r += _VSTD::__pop_count(~*__first.__seg_ & __m); 3013e519524SHoward Hinnant } 3023e519524SHoward Hinnant return __r; 3033e519524SHoward Hinnant} 3043e519524SHoward Hinnant 305423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst, class _Tp> 3063e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 307423a8d77SHoward Hinnanttypename __bit_iterator<_Cp, _IsConst>::difference_type 308423a8d77SHoward Hinnantcount(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_) 3093e519524SHoward Hinnant{ 310e4383379SHoward Hinnant if (static_cast<bool>(__value_)) 311c003db1fSHoward Hinnant return __count_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first)); 312c003db1fSHoward Hinnant return __count_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first)); 3133e519524SHoward Hinnant} 3143e519524SHoward Hinnant 3153e519524SHoward Hinnant// fill_n 3163e519524SHoward Hinnant 317c003db1fSHoward Hinnanttemplate <class _Cp> 3183e519524SHoward Hinnantvoid 319c003db1fSHoward Hinnant__fill_n_false(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) 3203e519524SHoward Hinnant{ 321c003db1fSHoward Hinnant typedef __bit_iterator<_Cp, false> _It; 3223e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 3233e519524SHoward Hinnant static const unsigned __bits_per_word = _It::__bits_per_word; 3243e519524SHoward Hinnant // do first partial word 3253e519524SHoward Hinnant if (__first.__ctz_ != 0) 3263e519524SHoward Hinnant { 3273e519524SHoward Hinnant __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 328ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__clz_f, __n); 3293e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 3303e519524SHoward Hinnant *__first.__seg_ &= ~__m; 3313e519524SHoward Hinnant __n -= __dn; 3323e519524SHoward Hinnant ++__first.__seg_; 3333e519524SHoward Hinnant } 3343e519524SHoward Hinnant // do middle whole words 3353e519524SHoward Hinnant __storage_type __nw = __n / __bits_per_word; 336ce48a113SHoward Hinnant _VSTD::memset(__first.__seg_, 0, __nw * sizeof(__storage_type)); 3373e519524SHoward Hinnant __n -= __nw * __bits_per_word; 3383e519524SHoward Hinnant // do last partial word 3393e519524SHoward Hinnant if (__n > 0) 3403e519524SHoward Hinnant { 3413e519524SHoward Hinnant __first.__seg_ += __nw; 3423e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 3433e519524SHoward Hinnant *__first.__seg_ &= ~__m; 3443e519524SHoward Hinnant } 3453e519524SHoward Hinnant} 3463e519524SHoward Hinnant 347c003db1fSHoward Hinnanttemplate <class _Cp> 3483e519524SHoward Hinnantvoid 349c003db1fSHoward Hinnant__fill_n_true(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) 3503e519524SHoward Hinnant{ 351c003db1fSHoward Hinnant typedef __bit_iterator<_Cp, false> _It; 3523e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 3533e519524SHoward Hinnant static const unsigned __bits_per_word = _It::__bits_per_word; 3543e519524SHoward Hinnant // do first partial word 3553e519524SHoward Hinnant if (__first.__ctz_ != 0) 3563e519524SHoward Hinnant { 3573e519524SHoward Hinnant __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 358ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__clz_f, __n); 3593e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 3603e519524SHoward Hinnant *__first.__seg_ |= __m; 3613e519524SHoward Hinnant __n -= __dn; 3623e519524SHoward Hinnant ++__first.__seg_; 3633e519524SHoward Hinnant } 3643e519524SHoward Hinnant // do middle whole words 3653e519524SHoward Hinnant __storage_type __nw = __n / __bits_per_word; 366ce48a113SHoward Hinnant _VSTD::memset(__first.__seg_, -1, __nw * sizeof(__storage_type)); 3673e519524SHoward Hinnant __n -= __nw * __bits_per_word; 3683e519524SHoward Hinnant // do last partial word 3693e519524SHoward Hinnant if (__n > 0) 3703e519524SHoward Hinnant { 3713e519524SHoward Hinnant __first.__seg_ += __nw; 3723e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 3733e519524SHoward Hinnant *__first.__seg_ |= __m; 3743e519524SHoward Hinnant } 3753e519524SHoward Hinnant} 3763e519524SHoward Hinnant 377c003db1fSHoward Hinnanttemplate <class _Cp> 3783e519524SHoward Hinnant_LIBCPP_INLINE_VISIBILITY inline 3793e519524SHoward Hinnantvoid 380c003db1fSHoward Hinnantfill_n(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n, bool __value_) 3813e519524SHoward Hinnant{ 3823e519524SHoward Hinnant if (__n > 0) 3833e519524SHoward Hinnant { 384e4383379SHoward Hinnant if (__value_) 3853e519524SHoward Hinnant __fill_n_true(__first, __n); 3863e519524SHoward Hinnant else 3873e519524SHoward Hinnant __fill_n_false(__first, __n); 3883e519524SHoward Hinnant } 3893e519524SHoward Hinnant} 3903e519524SHoward Hinnant 3913e519524SHoward Hinnant// fill 3923e519524SHoward Hinnant 393c003db1fSHoward Hinnanttemplate <class _Cp> 3943e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 3953e519524SHoward Hinnantvoid 396c003db1fSHoward Hinnantfill(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __last, bool __value_) 3973e519524SHoward Hinnant{ 398c003db1fSHoward Hinnant _VSTD::fill_n(__first, static_cast<typename _Cp::size_type>(__last - __first), __value_); 3993e519524SHoward Hinnant} 4003e519524SHoward Hinnant 4013e519524SHoward Hinnant// copy 4023e519524SHoward Hinnant 403c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 404c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 405c003db1fSHoward Hinnant__copy_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 406c003db1fSHoward Hinnant __bit_iterator<_Cp, false> __result) 4073e519524SHoward Hinnant{ 408c003db1fSHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _In; 4093e519524SHoward Hinnant typedef typename _In::difference_type difference_type; 4103e519524SHoward Hinnant typedef typename _In::__storage_type __storage_type; 4113e519524SHoward Hinnant static const unsigned __bits_per_word = _In::__bits_per_word; 4123e519524SHoward Hinnant difference_type __n = __last - __first; 4133e519524SHoward Hinnant if (__n > 0) 4143e519524SHoward Hinnant { 4153e519524SHoward Hinnant // do first word 4163e519524SHoward Hinnant if (__first.__ctz_ != 0) 4173e519524SHoward Hinnant { 4183e519524SHoward Hinnant unsigned __clz = __bits_per_word - __first.__ctz_; 419ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 4203e519524SHoward Hinnant __n -= __dn; 4213e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 4223e519524SHoward Hinnant __storage_type __b = *__first.__seg_ & __m; 4233e519524SHoward Hinnant *__result.__seg_ &= ~__m; 4243e519524SHoward Hinnant *__result.__seg_ |= __b; 4253e519524SHoward Hinnant __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 4263e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 4273e519524SHoward Hinnant ++__first.__seg_; 4283e519524SHoward Hinnant // __first.__ctz_ = 0; 4293e519524SHoward Hinnant } 4303e519524SHoward Hinnant // __first.__ctz_ == 0; 4313e519524SHoward Hinnant // do middle words 4323e519524SHoward Hinnant __storage_type __nw = __n / __bits_per_word; 433ce48a113SHoward Hinnant _VSTD::memmove(__result.__seg_, __first.__seg_, __nw * sizeof(__storage_type)); 4343e519524SHoward Hinnant __n -= __nw * __bits_per_word; 4353e519524SHoward Hinnant __result.__seg_ += __nw; 4363e519524SHoward Hinnant // do last word 4373e519524SHoward Hinnant if (__n > 0) 4383e519524SHoward Hinnant { 4393e519524SHoward Hinnant __first.__seg_ += __nw; 4403e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 4413e519524SHoward Hinnant __storage_type __b = *__first.__seg_ & __m; 4423e519524SHoward Hinnant *__result.__seg_ &= ~__m; 4433e519524SHoward Hinnant *__result.__seg_ |= __b; 4443e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(__n); 4453e519524SHoward Hinnant } 4463e519524SHoward Hinnant } 4473e519524SHoward Hinnant return __result; 4483e519524SHoward Hinnant} 4493e519524SHoward Hinnant 450c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 451c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 452c003db1fSHoward Hinnant__copy_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 453c003db1fSHoward Hinnant __bit_iterator<_Cp, false> __result) 4543e519524SHoward Hinnant{ 455c003db1fSHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _In; 4563e519524SHoward Hinnant typedef typename _In::difference_type difference_type; 4573e519524SHoward Hinnant typedef typename _In::__storage_type __storage_type; 4583e519524SHoward Hinnant static const unsigned __bits_per_word = _In::__bits_per_word; 4593e519524SHoward Hinnant difference_type __n = __last - __first; 4603e519524SHoward Hinnant if (__n > 0) 4613e519524SHoward Hinnant { 4623e519524SHoward Hinnant // do first word 4633e519524SHoward Hinnant if (__first.__ctz_ != 0) 4643e519524SHoward Hinnant { 4653e519524SHoward Hinnant unsigned __clz_f = __bits_per_word - __first.__ctz_; 466ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 4673e519524SHoward Hinnant __n -= __dn; 4683e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 4693e519524SHoward Hinnant __storage_type __b = *__first.__seg_ & __m; 4703e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __result.__ctz_; 471ce48a113SHoward Hinnant __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 4723e519524SHoward Hinnant __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 4733e519524SHoward Hinnant *__result.__seg_ &= ~__m; 4743e519524SHoward Hinnant if (__result.__ctz_ > __first.__ctz_) 4753e519524SHoward Hinnant *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_); 4763e519524SHoward Hinnant else 4773e519524SHoward Hinnant *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_); 4783e519524SHoward Hinnant __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 4793e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 4803e519524SHoward Hinnant __dn -= __ddn; 4813e519524SHoward Hinnant if (__dn > 0) 4823e519524SHoward Hinnant { 4833e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __dn); 4843e519524SHoward Hinnant *__result.__seg_ &= ~__m; 4853e519524SHoward Hinnant *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn); 4863e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(__dn); 4873e519524SHoward Hinnant } 4883e519524SHoward Hinnant ++__first.__seg_; 4893e519524SHoward Hinnant // __first.__ctz_ = 0; 4903e519524SHoward Hinnant } 4913e519524SHoward Hinnant // __first.__ctz_ == 0; 4923e519524SHoward Hinnant // do middle words 4933e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __result.__ctz_; 4943e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) << __result.__ctz_; 4953e519524SHoward Hinnant for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 4963e519524SHoward Hinnant { 4973e519524SHoward Hinnant __storage_type __b = *__first.__seg_; 4983e519524SHoward Hinnant *__result.__seg_ &= ~__m; 4993e519524SHoward Hinnant *__result.__seg_ |= __b << __result.__ctz_; 5003e519524SHoward Hinnant ++__result.__seg_; 5013e519524SHoward Hinnant *__result.__seg_ &= __m; 5023e519524SHoward Hinnant *__result.__seg_ |= __b >> __clz_r; 5033e519524SHoward Hinnant } 5043e519524SHoward Hinnant // do last word 5053e519524SHoward Hinnant if (__n > 0) 5063e519524SHoward Hinnant { 5073e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __n); 5083e519524SHoward Hinnant __storage_type __b = *__first.__seg_ & __m; 509ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); 5103e519524SHoward Hinnant __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 5113e519524SHoward Hinnant *__result.__seg_ &= ~__m; 5123e519524SHoward Hinnant *__result.__seg_ |= __b << __result.__ctz_; 5133e519524SHoward Hinnant __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 5143e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 5153e519524SHoward Hinnant __n -= __dn; 5163e519524SHoward Hinnant if (__n > 0) 5173e519524SHoward Hinnant { 5183e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __n); 5193e519524SHoward Hinnant *__result.__seg_ &= ~__m; 5203e519524SHoward Hinnant *__result.__seg_ |= __b >> __dn; 5213e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(__n); 5223e519524SHoward Hinnant } 5233e519524SHoward Hinnant } 5243e519524SHoward Hinnant } 5253e519524SHoward Hinnant return __result; 5263e519524SHoward Hinnant} 5273e519524SHoward Hinnant 528c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 5293e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 530c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 531c003db1fSHoward Hinnantcopy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 5323e519524SHoward Hinnant{ 5333e519524SHoward Hinnant if (__first.__ctz_ == __result.__ctz_) 5343e519524SHoward Hinnant return __copy_aligned(__first, __last, __result); 5353e519524SHoward Hinnant return __copy_unaligned(__first, __last, __result); 5363e519524SHoward Hinnant} 5373e519524SHoward Hinnant 5383e519524SHoward Hinnant// copy_backward 5393e519524SHoward Hinnant 540c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 541c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 542c003db1fSHoward Hinnant__copy_backward_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 543c003db1fSHoward Hinnant __bit_iterator<_Cp, false> __result) 5443e519524SHoward Hinnant{ 545c003db1fSHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _In; 5463e519524SHoward Hinnant typedef typename _In::difference_type difference_type; 5473e519524SHoward Hinnant typedef typename _In::__storage_type __storage_type; 5483e519524SHoward Hinnant static const unsigned __bits_per_word = _In::__bits_per_word; 5493e519524SHoward Hinnant difference_type __n = __last - __first; 5503e519524SHoward Hinnant if (__n > 0) 5513e519524SHoward Hinnant { 5523e519524SHoward Hinnant // do first word 5533e519524SHoward Hinnant if (__last.__ctz_ != 0) 5543e519524SHoward Hinnant { 555ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); 5563e519524SHoward Hinnant __n -= __dn; 5573e519524SHoward Hinnant unsigned __clz = __bits_per_word - __last.__ctz_; 5583e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz); 5593e519524SHoward Hinnant __storage_type __b = *__last.__seg_ & __m; 5603e519524SHoward Hinnant *__result.__seg_ &= ~__m; 5613e519524SHoward Hinnant *__result.__seg_ |= __b; 5623e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 5633e519524SHoward Hinnant __result.__ctz_) % __bits_per_word); 5643e519524SHoward Hinnant // __last.__ctz_ = 0 5653e519524SHoward Hinnant } 5663e519524SHoward Hinnant // __last.__ctz_ == 0 || __n == 0 5673e519524SHoward Hinnant // __result.__ctz_ == 0 || __n == 0 5683e519524SHoward Hinnant // do middle words 5693e519524SHoward Hinnant __storage_type __nw = __n / __bits_per_word; 5703e519524SHoward Hinnant __result.__seg_ -= __nw; 5713e519524SHoward Hinnant __last.__seg_ -= __nw; 572ce48a113SHoward Hinnant _VSTD::memmove(__result.__seg_, __last.__seg_, __nw * sizeof(__storage_type)); 5733e519524SHoward Hinnant __n -= __nw * __bits_per_word; 5743e519524SHoward Hinnant // do last word 5753e519524SHoward Hinnant if (__n > 0) 5763e519524SHoward Hinnant { 5773e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n); 5783e519524SHoward Hinnant __storage_type __b = *--__last.__seg_ & __m; 5793e519524SHoward Hinnant *--__result.__seg_ &= ~__m; 5803e519524SHoward Hinnant *__result.__seg_ |= __b; 5813e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 5823e519524SHoward Hinnant } 5833e519524SHoward Hinnant } 5843e519524SHoward Hinnant return __result; 5853e519524SHoward Hinnant} 5863e519524SHoward Hinnant 587c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 588c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 589c003db1fSHoward Hinnant__copy_backward_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 590c003db1fSHoward Hinnant __bit_iterator<_Cp, false> __result) 5913e519524SHoward Hinnant{ 592c003db1fSHoward Hinnant typedef __bit_iterator<_Cp, _IsConst> _In; 5933e519524SHoward Hinnant typedef typename _In::difference_type difference_type; 5943e519524SHoward Hinnant typedef typename _In::__storage_type __storage_type; 5953e519524SHoward Hinnant static const unsigned __bits_per_word = _In::__bits_per_word; 5963e519524SHoward Hinnant difference_type __n = __last - __first; 5973e519524SHoward Hinnant if (__n > 0) 5983e519524SHoward Hinnant { 5993e519524SHoward Hinnant // do first word 6003e519524SHoward Hinnant if (__last.__ctz_ != 0) 6013e519524SHoward Hinnant { 602ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); 6033e519524SHoward Hinnant __n -= __dn; 6043e519524SHoward Hinnant unsigned __clz_l = __bits_per_word - __last.__ctz_; 6053e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l); 6063e519524SHoward Hinnant __storage_type __b = *__last.__seg_ & __m; 6073e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __result.__ctz_; 608ce48a113SHoward Hinnant __storage_type __ddn = _VSTD::min(__dn, static_cast<difference_type>(__result.__ctz_)); 6093e519524SHoward Hinnant if (__ddn > 0) 6103e519524SHoward Hinnant { 6113e519524SHoward Hinnant __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r); 6123e519524SHoward Hinnant *__result.__seg_ &= ~__m; 6133e519524SHoward Hinnant if (__result.__ctz_ > __last.__ctz_) 6143e519524SHoward Hinnant *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 6153e519524SHoward Hinnant else 6163e519524SHoward Hinnant *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_); 6173e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) + 6183e519524SHoward Hinnant __result.__ctz_) % __bits_per_word); 6193e519524SHoward Hinnant __dn -= __ddn; 6203e519524SHoward Hinnant } 6213e519524SHoward Hinnant if (__dn > 0) 6223e519524SHoward Hinnant { 6233e519524SHoward Hinnant // __result.__ctz_ == 0 6243e519524SHoward Hinnant --__result.__seg_; 6253e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1)); 6263e519524SHoward Hinnant __m = ~__storage_type(0) << __result.__ctz_; 6273e519524SHoward Hinnant *__result.__seg_ &= ~__m; 6283e519524SHoward Hinnant __last.__ctz_ -= __dn + __ddn; 6293e519524SHoward Hinnant *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 6303e519524SHoward Hinnant } 6313e519524SHoward Hinnant // __last.__ctz_ = 0 6323e519524SHoward Hinnant } 6333e519524SHoward Hinnant // __last.__ctz_ == 0 || __n == 0 6343e519524SHoward Hinnant // __result.__ctz_ != 0 || __n == 0 6353e519524SHoward Hinnant // do middle words 6363e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __result.__ctz_; 6373e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> __clz_r; 6383e519524SHoward Hinnant for (; __n >= __bits_per_word; __n -= __bits_per_word) 6393e519524SHoward Hinnant { 6403e519524SHoward Hinnant __storage_type __b = *--__last.__seg_; 6413e519524SHoward Hinnant *__result.__seg_ &= ~__m; 6423e519524SHoward Hinnant *__result.__seg_ |= __b >> __clz_r; 6433e519524SHoward Hinnant *--__result.__seg_ &= __m; 6443e519524SHoward Hinnant *__result.__seg_ |= __b << __result.__ctz_; 6453e519524SHoward Hinnant } 6463e519524SHoward Hinnant // do last word 6473e519524SHoward Hinnant if (__n > 0) 6483e519524SHoward Hinnant { 6493e519524SHoward Hinnant __m = ~__storage_type(0) << (__bits_per_word - __n); 6503e519524SHoward Hinnant __storage_type __b = *--__last.__seg_ & __m; 651c206366fSHoward Hinnant __clz_r = __bits_per_word - __result.__ctz_; 652ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__result.__ctz_)); 6533e519524SHoward Hinnant __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r); 6543e519524SHoward Hinnant *__result.__seg_ &= ~__m; 6553e519524SHoward Hinnant *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_); 6563e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 6573e519524SHoward Hinnant __result.__ctz_) % __bits_per_word); 6583e519524SHoward Hinnant __n -= __dn; 6593e519524SHoward Hinnant if (__n > 0) 6603e519524SHoward Hinnant { 6613e519524SHoward Hinnant // __result.__ctz_ == 0 6623e519524SHoward Hinnant --__result.__seg_; 6633e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 6643e519524SHoward Hinnant __m = ~__storage_type(0) << __result.__ctz_; 6653e519524SHoward Hinnant *__result.__seg_ &= ~__m; 6663e519524SHoward Hinnant *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn)); 6673e519524SHoward Hinnant } 6683e519524SHoward Hinnant } 6693e519524SHoward Hinnant } 6703e519524SHoward Hinnant return __result; 6713e519524SHoward Hinnant} 6723e519524SHoward Hinnant 673c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 6743e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 675c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 676c003db1fSHoward Hinnantcopy_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 6773e519524SHoward Hinnant{ 6783e519524SHoward Hinnant if (__last.__ctz_ == __result.__ctz_) 6793e519524SHoward Hinnant return __copy_backward_aligned(__first, __last, __result); 6803e519524SHoward Hinnant return __copy_backward_unaligned(__first, __last, __result); 6813e519524SHoward Hinnant} 6823e519524SHoward Hinnant 6833e519524SHoward Hinnant// move 6843e519524SHoward Hinnant 685c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 6863e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 687c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 688c003db1fSHoward Hinnantmove(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 6893e519524SHoward Hinnant{ 690ce48a113SHoward Hinnant return _VSTD::copy(__first, __last, __result); 6913e519524SHoward Hinnant} 6923e519524SHoward Hinnant 6933e519524SHoward Hinnant// move_backward 6943e519524SHoward Hinnant 695c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst> 6963e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 697c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 698c003db1fSHoward Hinnantmove_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 6993e519524SHoward Hinnant{ 700ce48a113SHoward Hinnant return _VSTD::copy(__first, __last, __result); 7013e519524SHoward Hinnant} 7023e519524SHoward Hinnant 7033e519524SHoward Hinnant// swap_ranges 7043e519524SHoward Hinnant 705dbe81119SHoward Hinnanttemplate <class __C1, class __C2> 706dbe81119SHoward Hinnant__bit_iterator<__C2, false> 707dbe81119SHoward Hinnant__swap_ranges_aligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, 708dbe81119SHoward Hinnant __bit_iterator<__C2, false> __result) 7093e519524SHoward Hinnant{ 710dbe81119SHoward Hinnant typedef __bit_iterator<__C1, false> _I1; 7113e519524SHoward Hinnant typedef typename _I1::difference_type difference_type; 7123e519524SHoward Hinnant typedef typename _I1::__storage_type __storage_type; 7133e519524SHoward Hinnant static const unsigned __bits_per_word = _I1::__bits_per_word; 7143e519524SHoward Hinnant difference_type __n = __last - __first; 7153e519524SHoward Hinnant if (__n > 0) 7163e519524SHoward Hinnant { 7173e519524SHoward Hinnant // do first word 7183e519524SHoward Hinnant if (__first.__ctz_ != 0) 7193e519524SHoward Hinnant { 7203e519524SHoward Hinnant unsigned __clz = __bits_per_word - __first.__ctz_; 721ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 7223e519524SHoward Hinnant __n -= __dn; 7233e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 7243e519524SHoward Hinnant __storage_type __b1 = *__first.__seg_ & __m; 7253e519524SHoward Hinnant *__first.__seg_ &= ~__m; 7263e519524SHoward Hinnant __storage_type __b2 = *__result.__seg_ & __m; 7273e519524SHoward Hinnant *__result.__seg_ &= ~__m; 7283e519524SHoward Hinnant *__result.__seg_ |= __b1; 7293e519524SHoward Hinnant *__first.__seg_ |= __b2; 7303e519524SHoward Hinnant __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 7313e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 7323e519524SHoward Hinnant ++__first.__seg_; 7333e519524SHoward Hinnant // __first.__ctz_ = 0; 7343e519524SHoward Hinnant } 7353e519524SHoward Hinnant // __first.__ctz_ == 0; 7363e519524SHoward Hinnant // do middle words 7373e519524SHoward Hinnant for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_) 7383e519524SHoward Hinnant swap(*__first.__seg_, *__result.__seg_); 7393e519524SHoward Hinnant // do last word 7403e519524SHoward Hinnant if (__n > 0) 7413e519524SHoward Hinnant { 7423e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 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.__ctz_ = static_cast<unsigned>(__n); 7503e519524SHoward Hinnant } 7513e519524SHoward Hinnant } 7523e519524SHoward Hinnant return __result; 7533e519524SHoward Hinnant} 7543e519524SHoward Hinnant 755dbe81119SHoward Hinnanttemplate <class __C1, class __C2> 756dbe81119SHoward Hinnant__bit_iterator<__C2, false> 757dbe81119SHoward Hinnant__swap_ranges_unaligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, 758dbe81119SHoward Hinnant __bit_iterator<__C2, false> __result) 7593e519524SHoward Hinnant{ 760dbe81119SHoward Hinnant typedef __bit_iterator<__C1, false> _I1; 7613e519524SHoward Hinnant typedef typename _I1::difference_type difference_type; 7623e519524SHoward Hinnant typedef typename _I1::__storage_type __storage_type; 7633e519524SHoward Hinnant static const unsigned __bits_per_word = _I1::__bits_per_word; 7643e519524SHoward Hinnant difference_type __n = __last - __first; 7653e519524SHoward Hinnant if (__n > 0) 7663e519524SHoward Hinnant { 7673e519524SHoward Hinnant // do first word 7683e519524SHoward Hinnant if (__first.__ctz_ != 0) 7693e519524SHoward Hinnant { 7703e519524SHoward Hinnant unsigned __clz_f = __bits_per_word - __first.__ctz_; 771ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 7723e519524SHoward Hinnant __n -= __dn; 7733e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 7743e519524SHoward Hinnant __storage_type __b1 = *__first.__seg_ & __m; 7753e519524SHoward Hinnant *__first.__seg_ &= ~__m; 7763e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __result.__ctz_; 777ce48a113SHoward Hinnant __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 7783e519524SHoward Hinnant __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 7793e519524SHoward Hinnant __storage_type __b2 = *__result.__seg_ & __m; 7803e519524SHoward Hinnant *__result.__seg_ &= ~__m; 7813e519524SHoward Hinnant if (__result.__ctz_ > __first.__ctz_) 7823e519524SHoward Hinnant { 7833e519524SHoward Hinnant unsigned __s = __result.__ctz_ - __first.__ctz_; 7843e519524SHoward Hinnant *__result.__seg_ |= __b1 << __s; 7853e519524SHoward Hinnant *__first.__seg_ |= __b2 >> __s; 7863e519524SHoward Hinnant } 7873e519524SHoward Hinnant else 7883e519524SHoward Hinnant { 7893e519524SHoward Hinnant unsigned __s = __first.__ctz_ - __result.__ctz_; 7903e519524SHoward Hinnant *__result.__seg_ |= __b1 >> __s; 7913e519524SHoward Hinnant *__first.__seg_ |= __b2 << __s; 7923e519524SHoward Hinnant } 7933e519524SHoward Hinnant __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 7943e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 7953e519524SHoward Hinnant __dn -= __ddn; 7963e519524SHoward Hinnant if (__dn > 0) 7973e519524SHoward Hinnant { 7983e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __dn); 7993e519524SHoward Hinnant __b2 = *__result.__seg_ & __m; 8003e519524SHoward Hinnant *__result.__seg_ &= ~__m; 8013e519524SHoward Hinnant unsigned __s = __first.__ctz_ + __ddn; 8023e519524SHoward Hinnant *__result.__seg_ |= __b1 >> __s; 8033e519524SHoward Hinnant *__first.__seg_ |= __b2 << __s; 8043e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(__dn); 8053e519524SHoward Hinnant } 8063e519524SHoward Hinnant ++__first.__seg_; 8073e519524SHoward Hinnant // __first.__ctz_ = 0; 8083e519524SHoward Hinnant } 8093e519524SHoward Hinnant // __first.__ctz_ == 0; 8103e519524SHoward Hinnant // do middle words 8113e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) << __result.__ctz_; 8123e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __result.__ctz_; 8133e519524SHoward Hinnant for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 8143e519524SHoward Hinnant { 8153e519524SHoward Hinnant __storage_type __b1 = *__first.__seg_; 8163e519524SHoward Hinnant __storage_type __b2 = *__result.__seg_ & __m; 8173e519524SHoward Hinnant *__result.__seg_ &= ~__m; 8183e519524SHoward Hinnant *__result.__seg_ |= __b1 << __result.__ctz_; 8193e519524SHoward Hinnant *__first.__seg_ = __b2 >> __result.__ctz_; 8203e519524SHoward Hinnant ++__result.__seg_; 8213e519524SHoward Hinnant __b2 = *__result.__seg_ & ~__m; 8223e519524SHoward Hinnant *__result.__seg_ &= __m; 8233e519524SHoward Hinnant *__result.__seg_ |= __b1 >> __clz_r; 8243e519524SHoward Hinnant *__first.__seg_ |= __b2 << __clz_r; 8253e519524SHoward Hinnant } 8263e519524SHoward Hinnant // do last word 8273e519524SHoward Hinnant if (__n > 0) 8283e519524SHoward Hinnant { 8293e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __n); 8303e519524SHoward Hinnant __storage_type __b1 = *__first.__seg_ & __m; 8313e519524SHoward Hinnant *__first.__seg_ &= ~__m; 832ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min<__storage_type>(__n, __clz_r); 8333e519524SHoward Hinnant __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 8343e519524SHoward Hinnant __storage_type __b2 = *__result.__seg_ & __m; 8353e519524SHoward Hinnant *__result.__seg_ &= ~__m; 8363e519524SHoward Hinnant *__result.__seg_ |= __b1 << __result.__ctz_; 8373e519524SHoward Hinnant *__first.__seg_ |= __b2 >> __result.__ctz_; 8383e519524SHoward Hinnant __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 8393e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 8403e519524SHoward Hinnant __n -= __dn; 8413e519524SHoward Hinnant if (__n > 0) 8423e519524SHoward Hinnant { 8433e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __n); 8443e519524SHoward Hinnant __b2 = *__result.__seg_ & __m; 8453e519524SHoward Hinnant *__result.__seg_ &= ~__m; 8463e519524SHoward Hinnant *__result.__seg_ |= __b1 >> __dn; 8473e519524SHoward Hinnant *__first.__seg_ |= __b2 << __dn; 8483e519524SHoward Hinnant __result.__ctz_ = static_cast<unsigned>(__n); 8493e519524SHoward Hinnant } 8503e519524SHoward Hinnant } 8513e519524SHoward Hinnant } 8523e519524SHoward Hinnant return __result; 8533e519524SHoward Hinnant} 8543e519524SHoward Hinnant 855dbe81119SHoward Hinnanttemplate <class __C1, class __C2> 8563e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 857dbe81119SHoward Hinnant__bit_iterator<__C2, false> 858dbe81119SHoward Hinnantswap_ranges(__bit_iterator<__C1, false> __first1, __bit_iterator<__C1, false> __last1, 859dbe81119SHoward Hinnant __bit_iterator<__C2, false> __first2) 8603e519524SHoward Hinnant{ 8613e519524SHoward Hinnant if (__first1.__ctz_ == __first2.__ctz_) 8623e519524SHoward Hinnant return __swap_ranges_aligned(__first1, __last1, __first2); 8633e519524SHoward Hinnant return __swap_ranges_unaligned(__first1, __last1, __first2); 8643e519524SHoward Hinnant} 8653e519524SHoward Hinnant 8663e519524SHoward Hinnant// rotate 8673e519524SHoward Hinnant 868c003db1fSHoward Hinnanttemplate <class _Cp> 8693e519524SHoward Hinnantstruct __bit_array 8703e519524SHoward Hinnant{ 871c003db1fSHoward Hinnant typedef typename _Cp::difference_type difference_type; 872c003db1fSHoward Hinnant typedef typename _Cp::__storage_type __storage_type; 873c003db1fSHoward Hinnant typedef typename _Cp::iterator iterator; 874c003db1fSHoward Hinnant static const unsigned __bits_per_word = _Cp::__bits_per_word; 875c003db1fSHoward Hinnant static const unsigned _Np = 4; 8763e519524SHoward Hinnant 8773e519524SHoward Hinnant difference_type __size_; 878c003db1fSHoward Hinnant __storage_type __word_[_Np]; 8793e519524SHoward Hinnant 8803e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY static difference_type capacity() 881c003db1fSHoward Hinnant {return static_cast<difference_type>(_Np * __bits_per_word);} 8823e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY explicit __bit_array(difference_type __s) : __size_(__s) {} 8833e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY iterator begin() {return iterator(__word_, 0);} 8843e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY iterator end() {return iterator(__word_ + __size_ / __bits_per_word, 8853e519524SHoward Hinnant static_cast<unsigned>(__size_ % __bits_per_word));} 8863e519524SHoward Hinnant}; 8873e519524SHoward Hinnant 888c003db1fSHoward Hinnanttemplate <class _Cp> 889c003db1fSHoward Hinnant__bit_iterator<_Cp, false> 890c003db1fSHoward Hinnantrotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last) 8913e519524SHoward Hinnant{ 892c003db1fSHoward Hinnant typedef __bit_iterator<_Cp, false> _I1; 8933e519524SHoward Hinnant typedef typename _I1::difference_type difference_type; 8943e519524SHoward Hinnant typedef typename _I1::__storage_type __storage_type; 8953e519524SHoward Hinnant difference_type __d1 = __middle - __first; 8963e519524SHoward Hinnant difference_type __d2 = __last - __middle; 8973e519524SHoward Hinnant _I1 __r = __first + __d2; 8983e519524SHoward Hinnant while (__d1 != 0 && __d2 != 0) 8993e519524SHoward Hinnant { 9003e519524SHoward Hinnant if (__d1 <= __d2) 9013e519524SHoward Hinnant { 902c003db1fSHoward Hinnant if (__d1 <= __bit_array<_Cp>::capacity()) 9033e519524SHoward Hinnant { 904c003db1fSHoward Hinnant __bit_array<_Cp> __b(__d1); 905ce48a113SHoward Hinnant _VSTD::copy(__first, __middle, __b.begin()); 906ce48a113SHoward Hinnant _VSTD::copy(__b.begin(), __b.end(), _VSTD::copy(__middle, __last, __first)); 9073e519524SHoward Hinnant break; 9083e519524SHoward Hinnant } 9093e519524SHoward Hinnant else 9103e519524SHoward Hinnant { 911c003db1fSHoward Hinnant __bit_iterator<_Cp, false> __mp = _VSTD::swap_ranges(__first, __middle, __middle); 9123e519524SHoward Hinnant __first = __middle; 9133e519524SHoward Hinnant __middle = __mp; 9143e519524SHoward Hinnant __d2 -= __d1; 9153e519524SHoward Hinnant } 9163e519524SHoward Hinnant } 9173e519524SHoward Hinnant else 9183e519524SHoward Hinnant { 919c003db1fSHoward Hinnant if (__d2 <= __bit_array<_Cp>::capacity()) 9203e519524SHoward Hinnant { 921c003db1fSHoward Hinnant __bit_array<_Cp> __b(__d2); 922ce48a113SHoward Hinnant _VSTD::copy(__middle, __last, __b.begin()); 923ce48a113SHoward Hinnant _VSTD::copy_backward(__b.begin(), __b.end(), _VSTD::copy_backward(__first, __middle, __last)); 9243e519524SHoward Hinnant break; 9253e519524SHoward Hinnant } 9263e519524SHoward Hinnant else 9273e519524SHoward Hinnant { 928c003db1fSHoward Hinnant __bit_iterator<_Cp, false> __mp = __first + __d2; 929ce48a113SHoward Hinnant _VSTD::swap_ranges(__first, __mp, __middle); 9303e519524SHoward Hinnant __first = __mp; 9313e519524SHoward Hinnant __d1 -= __d2; 9323e519524SHoward Hinnant } 9333e519524SHoward Hinnant } 9343e519524SHoward Hinnant } 9353e519524SHoward Hinnant return __r; 9363e519524SHoward Hinnant} 9373e519524SHoward Hinnant 9383e519524SHoward Hinnant// equal 9393e519524SHoward Hinnant 9401237dccaSHoward Hinnanttemplate <class _Cp, bool _IC1, bool _IC2> 9413e519524SHoward Hinnantbool 9421237dccaSHoward Hinnant__equal_unaligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, 9431237dccaSHoward Hinnant __bit_iterator<_Cp, _IC2> __first2) 9443e519524SHoward Hinnant{ 9451237dccaSHoward Hinnant typedef __bit_iterator<_Cp, _IC1> _It; 9463e519524SHoward Hinnant typedef typename _It::difference_type difference_type; 9473e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 9483e519524SHoward Hinnant static const unsigned __bits_per_word = _It::__bits_per_word; 9493e519524SHoward Hinnant difference_type __n = __last1 - __first1; 9503e519524SHoward Hinnant if (__n > 0) 9513e519524SHoward Hinnant { 9523e519524SHoward Hinnant // do first word 9533e519524SHoward Hinnant if (__first1.__ctz_ != 0) 9543e519524SHoward Hinnant { 9553e519524SHoward Hinnant unsigned __clz_f = __bits_per_word - __first1.__ctz_; 956ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 9573e519524SHoward Hinnant __n -= __dn; 9583e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 9593e519524SHoward Hinnant __storage_type __b = *__first1.__seg_ & __m; 9603e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __first2.__ctz_; 961ce48a113SHoward Hinnant __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 9623e519524SHoward Hinnant __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 9633e519524SHoward Hinnant if (__first2.__ctz_ > __first1.__ctz_) 9644c0de496SHoward Hinnant { 9653e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_))) 9663e519524SHoward Hinnant return false; 9674c0de496SHoward Hinnant } 9683e519524SHoward Hinnant else 9694c0de496SHoward Hinnant { 9703e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_))) 9713e519524SHoward Hinnant return false; 9724c0de496SHoward Hinnant } 9733e519524SHoward Hinnant __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word; 9743e519524SHoward Hinnant __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word); 9753e519524SHoward Hinnant __dn -= __ddn; 9763e519524SHoward Hinnant if (__dn > 0) 9773e519524SHoward Hinnant { 9783e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __dn); 9793e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn))) 9803e519524SHoward Hinnant return false; 9813e519524SHoward Hinnant __first2.__ctz_ = static_cast<unsigned>(__dn); 9823e519524SHoward Hinnant } 9833e519524SHoward Hinnant ++__first1.__seg_; 9843e519524SHoward Hinnant // __first1.__ctz_ = 0; 9853e519524SHoward Hinnant } 9863e519524SHoward Hinnant // __first1.__ctz_ == 0; 9873e519524SHoward Hinnant // do middle words 9883e519524SHoward Hinnant unsigned __clz_r = __bits_per_word - __first2.__ctz_; 9893e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) << __first2.__ctz_; 9903e519524SHoward Hinnant for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_) 9913e519524SHoward Hinnant { 9923e519524SHoward Hinnant __storage_type __b = *__first1.__seg_; 9933e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 9943e519524SHoward Hinnant return false; 9953e519524SHoward Hinnant ++__first2.__seg_; 9963e519524SHoward Hinnant if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r)) 9973e519524SHoward Hinnant return false; 9983e519524SHoward Hinnant } 9993e519524SHoward Hinnant // do last word 10003e519524SHoward Hinnant if (__n > 0) 10013e519524SHoward Hinnant { 10023e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __n); 10033e519524SHoward Hinnant __storage_type __b = *__first1.__seg_ & __m; 1004ce48a113SHoward Hinnant __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); 10053e519524SHoward Hinnant __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 10063e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 10073e519524SHoward Hinnant return false; 10083e519524SHoward Hinnant __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word; 10093e519524SHoward Hinnant __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word); 10103e519524SHoward Hinnant __n -= __dn; 10113e519524SHoward Hinnant if (__n > 0) 10123e519524SHoward Hinnant { 10133e519524SHoward Hinnant __m = ~__storage_type(0) >> (__bits_per_word - __n); 10143e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (__b >> __dn)) 10153e519524SHoward Hinnant return false; 10163e519524SHoward Hinnant } 10173e519524SHoward Hinnant } 10183e519524SHoward Hinnant } 10193e519524SHoward Hinnant return true; 10203e519524SHoward Hinnant} 10213e519524SHoward Hinnant 10221237dccaSHoward Hinnanttemplate <class _Cp, bool _IC1, bool _IC2> 10233e519524SHoward Hinnantbool 10241237dccaSHoward Hinnant__equal_aligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, 10251237dccaSHoward Hinnant __bit_iterator<_Cp, _IC2> __first2) 10263e519524SHoward Hinnant{ 10271237dccaSHoward Hinnant typedef __bit_iterator<_Cp, _IC1> _It; 10283e519524SHoward Hinnant typedef typename _It::difference_type difference_type; 10293e519524SHoward Hinnant typedef typename _It::__storage_type __storage_type; 10303e519524SHoward Hinnant static const unsigned __bits_per_word = _It::__bits_per_word; 10313e519524SHoward Hinnant difference_type __n = __last1 - __first1; 10323e519524SHoward Hinnant if (__n > 0) 10333e519524SHoward Hinnant { 10343e519524SHoward Hinnant // do first word 10353e519524SHoward Hinnant if (__first1.__ctz_ != 0) 10363e519524SHoward Hinnant { 10373e519524SHoward Hinnant unsigned __clz = __bits_per_word - __first1.__ctz_; 1038ce48a113SHoward Hinnant difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 10393e519524SHoward Hinnant __n -= __dn; 10403e519524SHoward Hinnant __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 10413e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 10423e519524SHoward Hinnant return false; 10433e519524SHoward Hinnant ++__first2.__seg_; 10443e519524SHoward Hinnant ++__first1.__seg_; 10453e519524SHoward Hinnant // __first1.__ctz_ = 0; 10463e519524SHoward Hinnant // __first2.__ctz_ = 0; 10473e519524SHoward Hinnant } 10483e519524SHoward Hinnant // __first1.__ctz_ == 0; 10493e519524SHoward Hinnant // __first2.__ctz_ == 0; 10503e519524SHoward Hinnant // do middle words 10513e519524SHoward Hinnant for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_) 10523e519524SHoward Hinnant if (*__first2.__seg_ != *__first1.__seg_) 10533e519524SHoward Hinnant return false; 10543e519524SHoward Hinnant // do last word 10553e519524SHoward Hinnant if (__n > 0) 10563e519524SHoward Hinnant { 10573e519524SHoward Hinnant __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 10583e519524SHoward Hinnant if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 10593e519524SHoward Hinnant return false; 10603e519524SHoward Hinnant } 10613e519524SHoward Hinnant } 10623e519524SHoward Hinnant return true; 10633e519524SHoward Hinnant} 10643e519524SHoward Hinnant 1065c003db1fSHoward Hinnanttemplate <class _Cp, bool _IC1, bool _IC2> 106643d99238SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY 10673e519524SHoward Hinnantbool 1068c003db1fSHoward Hinnantequal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) 10693e519524SHoward Hinnant{ 10703e519524SHoward Hinnant if (__first1.__ctz_ == __first2.__ctz_) 10713e519524SHoward Hinnant return __equal_aligned(__first1, __last1, __first2); 10723e519524SHoward Hinnant return __equal_unaligned(__first1, __last1, __first2); 10733e519524SHoward Hinnant} 10743e519524SHoward Hinnant 10750ae9efebSHoward Hinnanttemplate <class _Cp, bool _IsConst, 10760ae9efebSHoward Hinnant typename _Cp::__storage_type> 10773e519524SHoward Hinnantclass __bit_iterator 10783e519524SHoward Hinnant{ 10793e519524SHoward Hinnantpublic: 1080c003db1fSHoward Hinnant typedef typename _Cp::difference_type difference_type; 10813e519524SHoward Hinnant typedef bool value_type; 10823e519524SHoward Hinnant typedef __bit_iterator pointer; 1083c003db1fSHoward Hinnant typedef typename conditional<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >::type reference; 10843e519524SHoward Hinnant typedef random_access_iterator_tag iterator_category; 10853e519524SHoward Hinnant 10863e519524SHoward Hinnantprivate: 1087c003db1fSHoward Hinnant typedef typename _Cp::__storage_type __storage_type; 1088c003db1fSHoward Hinnant typedef typename conditional<_IsConst, typename _Cp::__const_storage_pointer, 1089c003db1fSHoward Hinnant typename _Cp::__storage_pointer>::type __storage_pointer; 1090c003db1fSHoward Hinnant static const unsigned __bits_per_word = _Cp::__bits_per_word; 10913e519524SHoward Hinnant 10923e519524SHoward Hinnant __storage_pointer __seg_; 10933e519524SHoward Hinnant unsigned __ctz_; 10943e519524SHoward Hinnant 10953e519524SHoward Hinnantpublic: 1096d368a84cSHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator() _NOEXCEPT {} 10973e519524SHoward Hinnant 1098d368a84cSHoward Hinnant _LIBCPP_INLINE_VISIBILITY 1099c003db1fSHoward Hinnant __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT 11003e519524SHoward Hinnant : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {} 11013e519524SHoward Hinnant 1102d368a84cSHoward Hinnant _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT 1103d368a84cSHoward Hinnant {return reference(__seg_, __storage_type(1) << __ctz_);} 11043e519524SHoward Hinnant 11053e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator++() 11063e519524SHoward Hinnant { 11073e519524SHoward Hinnant if (__ctz_ != __bits_per_word-1) 11083e519524SHoward Hinnant ++__ctz_; 11093e519524SHoward Hinnant else 11103e519524SHoward Hinnant { 11113e519524SHoward Hinnant __ctz_ = 0; 11123e519524SHoward Hinnant ++__seg_; 11133e519524SHoward Hinnant } 11143e519524SHoward Hinnant return *this; 11153e519524SHoward Hinnant } 11163e519524SHoward Hinnant 11173e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator operator++(int) 11183e519524SHoward Hinnant { 11193e519524SHoward Hinnant __bit_iterator __tmp = *this; 11203e519524SHoward Hinnant ++(*this); 11213e519524SHoward Hinnant return __tmp; 11223e519524SHoward Hinnant } 11233e519524SHoward Hinnant 11243e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator--() 11253e519524SHoward Hinnant { 11263e519524SHoward Hinnant if (__ctz_ != 0) 11273e519524SHoward Hinnant --__ctz_; 11283e519524SHoward Hinnant else 11293e519524SHoward Hinnant { 11303e519524SHoward Hinnant __ctz_ = __bits_per_word - 1; 11313e519524SHoward Hinnant --__seg_; 11323e519524SHoward Hinnant } 11333e519524SHoward Hinnant return *this; 11343e519524SHoward Hinnant } 11353e519524SHoward Hinnant 11363e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator operator--(int) 11373e519524SHoward Hinnant { 11383e519524SHoward Hinnant __bit_iterator __tmp = *this; 11393e519524SHoward Hinnant --(*this); 11403e519524SHoward Hinnant return __tmp; 11413e519524SHoward Hinnant } 11423e519524SHoward Hinnant 11433e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator+=(difference_type __n) 11443e519524SHoward Hinnant { 11453e519524SHoward Hinnant if (__n >= 0) 11463e519524SHoward Hinnant __seg_ += (__n + __ctz_) / __bits_per_word; 11473e519524SHoward Hinnant else 11483e519524SHoward Hinnant __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1) 11493e519524SHoward Hinnant / static_cast<difference_type>(__bits_per_word); 11503e519524SHoward Hinnant __n &= (__bits_per_word - 1); 11513e519524SHoward Hinnant __ctz_ = static_cast<unsigned>((__n + __ctz_) % __bits_per_word); 11523e519524SHoward Hinnant return *this; 11533e519524SHoward Hinnant } 11543e519524SHoward Hinnant 11553e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator-=(difference_type __n) 11563e519524SHoward Hinnant { 11573e519524SHoward Hinnant return *this += -__n; 11583e519524SHoward Hinnant } 11593e519524SHoward Hinnant 11603e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator operator+(difference_type __n) const 11613e519524SHoward Hinnant { 11623e519524SHoward Hinnant __bit_iterator __t(*this); 11633e519524SHoward Hinnant __t += __n; 11643e519524SHoward Hinnant return __t; 11653e519524SHoward Hinnant } 11663e519524SHoward Hinnant 11673e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY __bit_iterator operator-(difference_type __n) const 11683e519524SHoward Hinnant { 11693e519524SHoward Hinnant __bit_iterator __t(*this); 11703e519524SHoward Hinnant __t -= __n; 11713e519524SHoward Hinnant return __t; 11723e519524SHoward Hinnant } 11733e519524SHoward Hinnant 11743e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 11753e519524SHoward Hinnant friend __bit_iterator operator+(difference_type __n, const __bit_iterator& __it) {return __it + __n;} 11763e519524SHoward Hinnant 11773e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 11783e519524SHoward Hinnant friend difference_type operator-(const __bit_iterator& __x, const __bit_iterator& __y) 11793e519524SHoward Hinnant {return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;} 11803e519524SHoward Hinnant 11813e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const {return *(*this + __n);} 11823e519524SHoward Hinnant 11833e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY friend bool operator==(const __bit_iterator& __x, const __bit_iterator& __y) 11843e519524SHoward Hinnant {return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;} 11853e519524SHoward Hinnant 11863e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY friend bool operator!=(const __bit_iterator& __x, const __bit_iterator& __y) 11873e519524SHoward Hinnant {return !(__x == __y);} 11883e519524SHoward Hinnant 11893e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY friend bool operator<(const __bit_iterator& __x, const __bit_iterator& __y) 11903e519524SHoward Hinnant {return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);} 11913e519524SHoward Hinnant 11923e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY friend bool operator>(const __bit_iterator& __x, const __bit_iterator& __y) 11933e519524SHoward Hinnant {return __y < __x;} 11943e519524SHoward Hinnant 11953e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y) 11963e519524SHoward Hinnant {return !(__y < __x);} 11973e519524SHoward Hinnant 11983e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y) 11993e519524SHoward Hinnant {return !(__x < __y);} 12003e519524SHoward Hinnant 12013e519524SHoward Hinnantprivate: 12023e519524SHoward Hinnant _LIBCPP_INLINE_VISIBILITY 1203d368a84cSHoward Hinnant __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT 1204d368a84cSHoward Hinnant : __seg_(__s), __ctz_(__ctz) {} 12053e519524SHoward Hinnant 12063e519524SHoward Hinnant#if defined(__clang__) 1207c003db1fSHoward Hinnant friend typename _Cp::__self; 12083e519524SHoward Hinnant#else 1209c003db1fSHoward Hinnant friend class _Cp::__self; 12103e519524SHoward Hinnant#endif 1211c003db1fSHoward Hinnant friend class __bit_reference<_Cp>; 1212c003db1fSHoward Hinnant friend class __bit_const_reference<_Cp>; 1213c003db1fSHoward Hinnant friend class __bit_iterator<_Cp, true>; 1214c003db1fSHoward Hinnant template <class _Dp> friend struct __bit_array; 1215c003db1fSHoward Hinnant template <class _Dp> friend void __fill_n_false(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); 1216c003db1fSHoward Hinnant template <class _Dp> friend void __fill_n_true(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); 1217c003db1fSHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_aligned(__bit_iterator<_Dp, _IC> __first, 1218c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC> __last, 1219c003db1fSHoward Hinnant __bit_iterator<_Dp, false> __result); 1220c003db1fSHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_unaligned(__bit_iterator<_Dp, _IC> __first, 1221c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC> __last, 1222c003db1fSHoward Hinnant __bit_iterator<_Dp, false> __result); 1223c003db1fSHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy(__bit_iterator<_Dp, _IC> __first, 1224c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC> __last, 1225c003db1fSHoward Hinnant __bit_iterator<_Dp, false> __result); 1226c003db1fSHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_aligned(__bit_iterator<_Dp, _IC> __first, 1227c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC> __last, 1228c003db1fSHoward Hinnant __bit_iterator<_Dp, false> __result); 1229c003db1fSHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_unaligned(__bit_iterator<_Dp, _IC> __first, 1230c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC> __last, 1231c003db1fSHoward Hinnant __bit_iterator<_Dp, false> __result); 1232c003db1fSHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy_backward(__bit_iterator<_Dp, _IC> __first, 1233c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC> __last, 1234c003db1fSHoward Hinnant __bit_iterator<_Dp, false> __result); 1235dbe81119SHoward Hinnant template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_aligned(__bit_iterator<__C1, false>, 1236dbe81119SHoward Hinnant __bit_iterator<__C1, false>, 1237dbe81119SHoward Hinnant __bit_iterator<__C2, false>); 1238dbe81119SHoward Hinnant template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_unaligned(__bit_iterator<__C1, false>, 1239dbe81119SHoward Hinnant __bit_iterator<__C1, false>, 1240dbe81119SHoward Hinnant __bit_iterator<__C2, false>); 1241dbe81119SHoward Hinnant template <class __C1, class __C2>friend __bit_iterator<__C2, false> swap_ranges(__bit_iterator<__C1, false>, 1242dbe81119SHoward Hinnant __bit_iterator<__C1, false>, 1243dbe81119SHoward Hinnant __bit_iterator<__C2, false>); 1244c003db1fSHoward Hinnant template <class _Dp> friend __bit_iterator<_Dp, false> rotate(__bit_iterator<_Dp, false>, 1245c003db1fSHoward Hinnant __bit_iterator<_Dp, false>, 1246c003db1fSHoward Hinnant __bit_iterator<_Dp, false>); 12471237dccaSHoward Hinnant template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_aligned(__bit_iterator<_Dp, _IC1>, 12481237dccaSHoward Hinnant __bit_iterator<_Dp, _IC1>, 12491237dccaSHoward Hinnant __bit_iterator<_Dp, _IC2>); 12501237dccaSHoward Hinnant template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_unaligned(__bit_iterator<_Dp, _IC1>, 12511237dccaSHoward Hinnant __bit_iterator<_Dp, _IC1>, 12521237dccaSHoward Hinnant __bit_iterator<_Dp, _IC2>); 1253c003db1fSHoward Hinnant template <class _Dp, bool _IC1, bool _IC2> friend bool equal(__bit_iterator<_Dp, _IC1>, 1254c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC1>, 1255c003db1fSHoward Hinnant __bit_iterator<_Dp, _IC2>); 1256423a8d77SHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_true(__bit_iterator<_Dp, _IC>, 1257c003db1fSHoward Hinnant typename _Dp::size_type); 1258423a8d77SHoward Hinnant template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_false(__bit_iterator<_Dp, _IC>, 1259c003db1fSHoward Hinnant typename _Dp::size_type); 1260423a8d77SHoward Hinnant template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type 1261423a8d77SHoward Hinnant __count_bool_true(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 1262423a8d77SHoward Hinnant template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type 1263423a8d77SHoward Hinnant __count_bool_false(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 12643e519524SHoward Hinnant}; 12653e519524SHoward Hinnant 12663e519524SHoward Hinnant_LIBCPP_END_NAMESPACE_STD 12673e519524SHoward Hinnant 12683e519524SHoward Hinnant#endif // _LIBCPP___BIT_REFERENCE 1269