__bit_reference revision 227825
1227825Stheraven// -*- C++ -*- 2227825Stheraven//===----------------------------------------------------------------------===// 3227825Stheraven// 4227825Stheraven// The LLVM Compiler Infrastructure 5227825Stheraven// 6227825Stheraven// This file is dual licensed under the MIT and the University of Illinois Open 7227825Stheraven// Source Licenses. See LICENSE.TXT for details. 8227825Stheraven// 9227825Stheraven//===----------------------------------------------------------------------===// 10227825Stheraven 11227825Stheraven#ifndef _LIBCPP___BIT_REFERENCE 12227825Stheraven#define _LIBCPP___BIT_REFERENCE 13227825Stheraven 14227825Stheraven#include <__config> 15227825Stheraven#include <algorithm> 16227825Stheraven 17227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 18227825Stheraven#pragma GCC system_header 19227825Stheraven#endif 20227825Stheraven 21227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 22227825Stheraven 23227825Stheraventemplate <class _C, bool _IsConst> class __bit_iterator; 24227825Stheraventemplate <class _C> class __bit_const_reference; 25227825Stheraven 26227825Stheraventemplate <class _Tp> 27227825Stheravenstruct __has_storage_type 28227825Stheraven{ 29227825Stheraven static const bool value = false; 30227825Stheraven}; 31227825Stheraven 32227825Stheraventemplate <class _C, bool = __has_storage_type<_C>::value> 33227825Stheravenclass __bit_reference 34227825Stheraven{ 35227825Stheraven typedef typename _C::__storage_type __storage_type; 36227825Stheraven typedef typename _C::__storage_pointer __storage_pointer; 37227825Stheraven 38227825Stheraven __storage_pointer __seg_; 39227825Stheraven __storage_type __mask_; 40227825Stheraven 41227825Stheraven#if defined(__clang__) 42227825Stheraven friend typename _C::__self; 43227825Stheraven#else 44227825Stheraven friend class _C::__self; 45227825Stheraven#endif 46227825Stheraven friend class __bit_const_reference<_C>; 47227825Stheraven friend class __bit_iterator<_C, false>; 48227825Stheravenpublic: 49227825Stheraven _LIBCPP_INLINE_VISIBILITY operator bool() const _NOEXCEPT 50227825Stheraven {return static_cast<bool>(*__seg_ & __mask_);} 51227825Stheraven _LIBCPP_INLINE_VISIBILITY bool operator ~() const _NOEXCEPT 52227825Stheraven {return !static_cast<bool>(*this);} 53227825Stheraven 54227825Stheraven _LIBCPP_INLINE_VISIBILITY 55227825Stheraven __bit_reference& operator=(bool __x) _NOEXCEPT 56227825Stheraven { 57227825Stheraven if (__x) 58227825Stheraven *__seg_ |= __mask_; 59227825Stheraven else 60227825Stheraven *__seg_ &= ~__mask_; 61227825Stheraven return *this; 62227825Stheraven } 63227825Stheraven 64227825Stheraven _LIBCPP_INLINE_VISIBILITY 65227825Stheraven __bit_reference& operator=(const __bit_reference& __x) _NOEXCEPT 66227825Stheraven {return operator=(static_cast<bool>(__x));} 67227825Stheraven 68227825Stheraven _LIBCPP_INLINE_VISIBILITY void flip() _NOEXCEPT {*__seg_ ^= __mask_;} 69227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator<_C, false> operator&() const _NOEXCEPT 70227825Stheraven {return __bit_iterator<_C, false>(__seg_, static_cast<unsigned>(__ctz(__mask_)));} 71227825Stheravenprivate: 72227825Stheraven _LIBCPP_INLINE_VISIBILITY 73227825Stheraven __bit_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT 74227825Stheraven : __seg_(__s), __mask_(__m) {} 75227825Stheraven}; 76227825Stheraven 77227825Stheraventemplate <class _C> 78227825Stheravenclass __bit_reference<_C, false> 79227825Stheraven{ 80227825Stheraven}; 81227825Stheraven 82227825Stheraventemplate <class _C, class _D> 83227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 84227825Stheravenvoid 85227825Stheravenswap(__bit_reference<_C> __x, __bit_reference<_D> __y) _NOEXCEPT 86227825Stheraven{ 87227825Stheraven bool __t = __x; 88227825Stheraven __x = __y; 89227825Stheraven __y = __t; 90227825Stheraven} 91227825Stheraven 92227825Stheraventemplate <class _C> 93227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 94227825Stheravenvoid 95227825Stheravenswap(__bit_reference<_C> __x, bool& __y) _NOEXCEPT 96227825Stheraven{ 97227825Stheraven bool __t = __x; 98227825Stheraven __x = __y; 99227825Stheraven __y = __t; 100227825Stheraven} 101227825Stheraven 102227825Stheraventemplate <class _C> 103227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 104227825Stheravenvoid 105227825Stheravenswap(bool& __x, __bit_reference<_C> __y) _NOEXCEPT 106227825Stheraven{ 107227825Stheraven bool __t = __x; 108227825Stheraven __x = __y; 109227825Stheraven __y = __t; 110227825Stheraven} 111227825Stheraven 112227825Stheraventemplate <class _C> 113227825Stheravenclass __bit_const_reference 114227825Stheraven{ 115227825Stheraven typedef typename _C::__storage_type __storage_type; 116227825Stheraven typedef typename _C::__const_storage_pointer __storage_pointer; 117227825Stheraven 118227825Stheraven __storage_pointer __seg_; 119227825Stheraven __storage_type __mask_; 120227825Stheraven 121227825Stheraven#if defined(__clang__) 122227825Stheraven friend typename _C::__self; 123227825Stheraven#else 124227825Stheraven friend class _C::__self; 125227825Stheraven#endif 126227825Stheraven friend class __bit_iterator<_C, true>; 127227825Stheravenpublic: 128227825Stheraven _LIBCPP_INLINE_VISIBILITY 129227825Stheraven __bit_const_reference(const __bit_reference<_C>& __x) _NOEXCEPT 130227825Stheraven : __seg_(__x.__seg_), __mask_(__x.__mask_) {} 131227825Stheraven 132227825Stheraven _LIBCPP_INLINE_VISIBILITY operator bool() const _NOEXCEPT 133227825Stheraven {return static_cast<bool>(*__seg_ & __mask_);} 134227825Stheraven 135227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator<_C, true> operator&() const _NOEXCEPT 136227825Stheraven {return __bit_iterator<_C, true>(__seg_, static_cast<unsigned>(__ctz(__mask_)));} 137227825Stheravenprivate: 138227825Stheraven _LIBCPP_INLINE_VISIBILITY 139227825Stheraven __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT 140227825Stheraven : __seg_(__s), __mask_(__m) {} 141227825Stheraven 142227825Stheraven __bit_const_reference& operator=(const __bit_const_reference& __x); 143227825Stheraven}; 144227825Stheraven 145227825Stheraven// find 146227825Stheraven 147227825Stheraventemplate <class _C> 148227825Stheraven__bit_iterator<_C, false> 149227825Stheraven__find_bool_true(__bit_iterator<_C, false> __first, typename _C::size_type __n) 150227825Stheraven{ 151227825Stheraven typedef __bit_iterator<_C, false> _It; 152227825Stheraven typedef typename _It::__storage_type __storage_type; 153227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 154227825Stheraven // do first partial word 155227825Stheraven if (__first.__ctz_ != 0) 156227825Stheraven { 157227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 158227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 159227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 160227825Stheraven __storage_type __b = *__first.__seg_ & __m; 161227825Stheraven if (__b) 162227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 163227825Stheraven __n -= __dn; 164227825Stheraven ++__first.__seg_; 165227825Stheraven } 166227825Stheraven // do middle whole words 167227825Stheraven for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 168227825Stheraven if (*__first.__seg_) 169227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(*__first.__seg_))); 170227825Stheraven // do last partial word 171227825Stheraven if (__n > 0) 172227825Stheraven { 173227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 174227825Stheraven __storage_type __b = *__first.__seg_ & __m; 175227825Stheraven if (__b) 176227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 177227825Stheraven } 178227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(__n)); 179227825Stheraven} 180227825Stheraven 181227825Stheraventemplate <class _C> 182227825Stheraven__bit_iterator<_C, false> 183227825Stheraven__find_bool_false(__bit_iterator<_C, false> __first, typename _C::size_type __n) 184227825Stheraven{ 185227825Stheraven typedef __bit_iterator<_C, false> _It; 186227825Stheraven typedef typename _It::__storage_type __storage_type; 187227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 188227825Stheraven // do first partial word 189227825Stheraven if (__first.__ctz_ != 0) 190227825Stheraven { 191227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 192227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 193227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 194227825Stheraven __storage_type __b = ~(*__first.__seg_ & __m); 195227825Stheraven if (__b) 196227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 197227825Stheraven __n -= __dn; 198227825Stheraven ++__first.__seg_; 199227825Stheraven } 200227825Stheraven // do middle whole words 201227825Stheraven for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 202227825Stheraven { 203227825Stheraven __storage_type __b = ~*__first.__seg_; 204227825Stheraven if (__b) 205227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 206227825Stheraven } 207227825Stheraven // do last partial word 208227825Stheraven if (__n > 0) 209227825Stheraven { 210227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 211227825Stheraven __storage_type __b = ~(*__first.__seg_ & __m); 212227825Stheraven if (__b) 213227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 214227825Stheraven } 215227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(__n)); 216227825Stheraven} 217227825Stheraven 218227825Stheraventemplate <class _C, class _Tp> 219227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 220227825Stheraven__bit_iterator<_C, false> 221227825Stheravenfind(__bit_iterator<_C, false> __first, __bit_iterator<_C, false> __last, const _Tp& __value_) 222227825Stheraven{ 223227825Stheraven if (static_cast<bool>(__value_)) 224227825Stheraven return __find_bool_true(__first, static_cast<typename _C::size_type>(__last - __first)); 225227825Stheraven return __find_bool_false(__first, static_cast<typename _C::size_type>(__last - __first)); 226227825Stheraven} 227227825Stheraven 228227825Stheraven// count 229227825Stheraven 230227825Stheraventemplate <class _C> 231227825Stheraventypename __bit_iterator<_C, false>::difference_type 232227825Stheraven__count_bool_true(__bit_iterator<_C, false> __first, typename _C::size_type __n) 233227825Stheraven{ 234227825Stheraven typedef __bit_iterator<_C, false> _It; 235227825Stheraven typedef typename _It::__storage_type __storage_type; 236227825Stheraven typedef typename _It::difference_type difference_type; 237227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 238227825Stheraven difference_type __r = 0; 239227825Stheraven // do first partial word 240227825Stheraven if (__first.__ctz_ != 0) 241227825Stheraven { 242227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 243227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 244227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 245227825Stheraven __r = _VSTD::__pop_count(*__first.__seg_ & __m); 246227825Stheraven __n -= __dn; 247227825Stheraven ++__first.__seg_; 248227825Stheraven } 249227825Stheraven // do middle whole words 250227825Stheraven for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 251227825Stheraven __r += _VSTD::__pop_count(*__first.__seg_); 252227825Stheraven // do last partial word 253227825Stheraven if (__n > 0) 254227825Stheraven { 255227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 256227825Stheraven __r += _VSTD::__pop_count(*__first.__seg_ & __m); 257227825Stheraven } 258227825Stheraven return __r; 259227825Stheraven} 260227825Stheraven 261227825Stheraventemplate <class _C> 262227825Stheraventypename __bit_iterator<_C, false>::difference_type 263227825Stheraven__count_bool_false(__bit_iterator<_C, false> __first, typename _C::size_type __n) 264227825Stheraven{ 265227825Stheraven typedef __bit_iterator<_C, false> _It; 266227825Stheraven typedef typename _It::__storage_type __storage_type; 267227825Stheraven typedef typename _It::difference_type difference_type; 268227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 269227825Stheraven difference_type __r = 0; 270227825Stheraven // do first partial word 271227825Stheraven if (__first.__ctz_ != 0) 272227825Stheraven { 273227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 274227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 275227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 276227825Stheraven __r = _VSTD::__pop_count(~(*__first.__seg_ & __m)); 277227825Stheraven __n -= __dn; 278227825Stheraven ++__first.__seg_; 279227825Stheraven } 280227825Stheraven // do middle whole words 281227825Stheraven for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 282227825Stheraven __r += _VSTD::__pop_count(~*__first.__seg_); 283227825Stheraven // do last partial word 284227825Stheraven if (__n > 0) 285227825Stheraven { 286227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 287227825Stheraven __r += _VSTD::__pop_count(~(*__first.__seg_ & __m)); 288227825Stheraven } 289227825Stheraven return __r; 290227825Stheraven} 291227825Stheraven 292227825Stheraventemplate <class _C, class _Tp> 293227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 294227825Stheraventypename __bit_iterator<_C, false>::difference_type 295227825Stheravencount(__bit_iterator<_C, false> __first, __bit_iterator<_C, false> __last, const _Tp& __value_) 296227825Stheraven{ 297227825Stheraven if (static_cast<bool>(__value_)) 298227825Stheraven return __count_bool_true(__first, static_cast<typename _C::size_type>(__last - __first)); 299227825Stheraven return __count_bool_false(__first, static_cast<typename _C::size_type>(__last - __first)); 300227825Stheraven} 301227825Stheraven 302227825Stheraven// fill_n 303227825Stheraven 304227825Stheraventemplate <class _C> 305227825Stheravenvoid 306227825Stheraven__fill_n_false(__bit_iterator<_C, false> __first, typename _C::size_type __n) 307227825Stheraven{ 308227825Stheraven typedef __bit_iterator<_C, false> _It; 309227825Stheraven typedef typename _It::__storage_type __storage_type; 310227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 311227825Stheraven // do first partial word 312227825Stheraven if (__first.__ctz_ != 0) 313227825Stheraven { 314227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 315227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 316227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 317227825Stheraven *__first.__seg_ &= ~__m; 318227825Stheraven __n -= __dn; 319227825Stheraven ++__first.__seg_; 320227825Stheraven } 321227825Stheraven // do middle whole words 322227825Stheraven __storage_type __nw = __n / __bits_per_word; 323227825Stheraven _VSTD::memset(__first.__seg_, 0, __nw * sizeof(__storage_type)); 324227825Stheraven __n -= __nw * __bits_per_word; 325227825Stheraven // do last partial word 326227825Stheraven if (__n > 0) 327227825Stheraven { 328227825Stheraven __first.__seg_ += __nw; 329227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 330227825Stheraven *__first.__seg_ &= ~__m; 331227825Stheraven } 332227825Stheraven} 333227825Stheraven 334227825Stheraventemplate <class _C> 335227825Stheravenvoid 336227825Stheraven__fill_n_true(__bit_iterator<_C, false> __first, typename _C::size_type __n) 337227825Stheraven{ 338227825Stheraven typedef __bit_iterator<_C, false> _It; 339227825Stheraven typedef typename _It::__storage_type __storage_type; 340227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 341227825Stheraven // do first partial word 342227825Stheraven if (__first.__ctz_ != 0) 343227825Stheraven { 344227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 345227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 346227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 347227825Stheraven *__first.__seg_ |= __m; 348227825Stheraven __n -= __dn; 349227825Stheraven ++__first.__seg_; 350227825Stheraven } 351227825Stheraven // do middle whole words 352227825Stheraven __storage_type __nw = __n / __bits_per_word; 353227825Stheraven _VSTD::memset(__first.__seg_, -1, __nw * sizeof(__storage_type)); 354227825Stheraven __n -= __nw * __bits_per_word; 355227825Stheraven // do last partial word 356227825Stheraven if (__n > 0) 357227825Stheraven { 358227825Stheraven __first.__seg_ += __nw; 359227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 360227825Stheraven *__first.__seg_ |= __m; 361227825Stheraven } 362227825Stheraven} 363227825Stheraven 364227825Stheraventemplate <class _C> 365227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 366227825Stheravenvoid 367227825Stheravenfill_n(__bit_iterator<_C, false> __first, typename _C::size_type __n, bool __value_) 368227825Stheraven{ 369227825Stheraven if (__n > 0) 370227825Stheraven { 371227825Stheraven if (__value_) 372227825Stheraven __fill_n_true(__first, __n); 373227825Stheraven else 374227825Stheraven __fill_n_false(__first, __n); 375227825Stheraven } 376227825Stheraven} 377227825Stheraven 378227825Stheraven// fill 379227825Stheraven 380227825Stheraventemplate <class _C> 381227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 382227825Stheravenvoid 383227825Stheravenfill(__bit_iterator<_C, false> __first, __bit_iterator<_C, false> __last, bool __value_) 384227825Stheraven{ 385227825Stheraven _VSTD::fill_n(__first, static_cast<typename _C::size_type>(__last - __first), __value_); 386227825Stheraven} 387227825Stheraven 388227825Stheraven// copy 389227825Stheraven 390227825Stheraventemplate <class _C, bool _IsConst> 391227825Stheraven__bit_iterator<_C, false> 392227825Stheraven__copy_aligned(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, 393227825Stheraven __bit_iterator<_C, false> __result) 394227825Stheraven{ 395227825Stheraven typedef __bit_iterator<_C, _IsConst> _In; 396227825Stheraven typedef typename _In::difference_type difference_type; 397227825Stheraven typedef typename _In::__storage_type __storage_type; 398227825Stheraven static const unsigned __bits_per_word = _In::__bits_per_word; 399227825Stheraven difference_type __n = __last - __first; 400227825Stheraven if (__n > 0) 401227825Stheraven { 402227825Stheraven // do first word 403227825Stheraven if (__first.__ctz_ != 0) 404227825Stheraven { 405227825Stheraven unsigned __clz = __bits_per_word - __first.__ctz_; 406227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 407227825Stheraven __n -= __dn; 408227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 409227825Stheraven __storage_type __b = *__first.__seg_ & __m; 410227825Stheraven *__result.__seg_ &= ~__m; 411227825Stheraven *__result.__seg_ |= __b; 412227825Stheraven __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 413227825Stheraven __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 414227825Stheraven ++__first.__seg_; 415227825Stheraven // __first.__ctz_ = 0; 416227825Stheraven } 417227825Stheraven // __first.__ctz_ == 0; 418227825Stheraven // do middle words 419227825Stheraven __storage_type __nw = __n / __bits_per_word; 420227825Stheraven _VSTD::memmove(__result.__seg_, __first.__seg_, __nw * sizeof(__storage_type)); 421227825Stheraven __n -= __nw * __bits_per_word; 422227825Stheraven __result.__seg_ += __nw; 423227825Stheraven // do last word 424227825Stheraven if (__n > 0) 425227825Stheraven { 426227825Stheraven __first.__seg_ += __nw; 427227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 428227825Stheraven __storage_type __b = *__first.__seg_ & __m; 429227825Stheraven *__result.__seg_ &= ~__m; 430227825Stheraven *__result.__seg_ |= __b; 431227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 432227825Stheraven } 433227825Stheraven } 434227825Stheraven return __result; 435227825Stheraven} 436227825Stheraven 437227825Stheraventemplate <class _C, bool _IsConst> 438227825Stheraven__bit_iterator<_C, false> 439227825Stheraven__copy_unaligned(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, 440227825Stheraven __bit_iterator<_C, false> __result) 441227825Stheraven{ 442227825Stheraven typedef __bit_iterator<_C, _IsConst> _In; 443227825Stheraven typedef typename _In::difference_type difference_type; 444227825Stheraven typedef typename _In::__storage_type __storage_type; 445227825Stheraven static const unsigned __bits_per_word = _In::__bits_per_word; 446227825Stheraven difference_type __n = __last - __first; 447227825Stheraven if (__n > 0) 448227825Stheraven { 449227825Stheraven // do first word 450227825Stheraven if (__first.__ctz_ != 0) 451227825Stheraven { 452227825Stheraven unsigned __clz_f = __bits_per_word - __first.__ctz_; 453227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 454227825Stheraven __n -= __dn; 455227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 456227825Stheraven __storage_type __b = *__first.__seg_ & __m; 457227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 458227825Stheraven __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 459227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 460227825Stheraven *__result.__seg_ &= ~__m; 461227825Stheraven if (__result.__ctz_ > __first.__ctz_) 462227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_); 463227825Stheraven else 464227825Stheraven *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_); 465227825Stheraven __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 466227825Stheraven __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 467227825Stheraven __dn -= __ddn; 468227825Stheraven if (__dn > 0) 469227825Stheraven { 470227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __dn); 471227825Stheraven *__result.__seg_ &= ~__m; 472227825Stheraven *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn); 473227825Stheraven __result.__ctz_ = static_cast<unsigned>(__dn); 474227825Stheraven } 475227825Stheraven ++__first.__seg_; 476227825Stheraven // __first.__ctz_ = 0; 477227825Stheraven } 478227825Stheraven // __first.__ctz_ == 0; 479227825Stheraven // do middle words 480227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 481227825Stheraven __storage_type __m = ~__storage_type(0) << __result.__ctz_; 482227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 483227825Stheraven { 484227825Stheraven __storage_type __b = *__first.__seg_; 485227825Stheraven *__result.__seg_ &= ~__m; 486227825Stheraven *__result.__seg_ |= __b << __result.__ctz_; 487227825Stheraven ++__result.__seg_; 488227825Stheraven *__result.__seg_ &= __m; 489227825Stheraven *__result.__seg_ |= __b >> __clz_r; 490227825Stheraven } 491227825Stheraven // do last word 492227825Stheraven if (__n > 0) 493227825Stheraven { 494227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 495227825Stheraven __storage_type __b = *__first.__seg_ & __m; 496227825Stheraven __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); 497227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 498227825Stheraven *__result.__seg_ &= ~__m; 499227825Stheraven *__result.__seg_ |= __b << __result.__ctz_; 500227825Stheraven __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 501227825Stheraven __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 502227825Stheraven __n -= __dn; 503227825Stheraven if (__n > 0) 504227825Stheraven { 505227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 506227825Stheraven *__result.__seg_ &= ~__m; 507227825Stheraven *__result.__seg_ |= __b >> __dn; 508227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 509227825Stheraven } 510227825Stheraven } 511227825Stheraven } 512227825Stheraven return __result; 513227825Stheraven} 514227825Stheraven 515227825Stheraventemplate <class _C, bool _IsConst> 516227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 517227825Stheraven__bit_iterator<_C, false> 518227825Stheravencopy(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, __bit_iterator<_C, false> __result) 519227825Stheraven{ 520227825Stheraven if (__first.__ctz_ == __result.__ctz_) 521227825Stheraven return __copy_aligned(__first, __last, __result); 522227825Stheraven return __copy_unaligned(__first, __last, __result); 523227825Stheraven} 524227825Stheraven 525227825Stheraven// copy_backward 526227825Stheraven 527227825Stheraventemplate <class _C, bool _IsConst> 528227825Stheraven__bit_iterator<_C, false> 529227825Stheraven__copy_backward_aligned(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, 530227825Stheraven __bit_iterator<_C, false> __result) 531227825Stheraven{ 532227825Stheraven typedef __bit_iterator<_C, _IsConst> _In; 533227825Stheraven typedef typename _In::difference_type difference_type; 534227825Stheraven typedef typename _In::__storage_type __storage_type; 535227825Stheraven static const unsigned __bits_per_word = _In::__bits_per_word; 536227825Stheraven difference_type __n = __last - __first; 537227825Stheraven if (__n > 0) 538227825Stheraven { 539227825Stheraven // do first word 540227825Stheraven if (__last.__ctz_ != 0) 541227825Stheraven { 542227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); 543227825Stheraven __n -= __dn; 544227825Stheraven unsigned __clz = __bits_per_word - __last.__ctz_; 545227825Stheraven __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz); 546227825Stheraven __storage_type __b = *__last.__seg_ & __m; 547227825Stheraven *__result.__seg_ &= ~__m; 548227825Stheraven *__result.__seg_ |= __b; 549227825Stheraven __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 550227825Stheraven __result.__ctz_) % __bits_per_word); 551227825Stheraven // __last.__ctz_ = 0 552227825Stheraven } 553227825Stheraven // __last.__ctz_ == 0 || __n == 0 554227825Stheraven // __result.__ctz_ == 0 || __n == 0 555227825Stheraven // do middle words 556227825Stheraven __storage_type __nw = __n / __bits_per_word; 557227825Stheraven __result.__seg_ -= __nw; 558227825Stheraven __last.__seg_ -= __nw; 559227825Stheraven _VSTD::memmove(__result.__seg_, __last.__seg_, __nw * sizeof(__storage_type)); 560227825Stheraven __n -= __nw * __bits_per_word; 561227825Stheraven // do last word 562227825Stheraven if (__n > 0) 563227825Stheraven { 564227825Stheraven __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n); 565227825Stheraven __storage_type __b = *--__last.__seg_ & __m; 566227825Stheraven *--__result.__seg_ &= ~__m; 567227825Stheraven *__result.__seg_ |= __b; 568227825Stheraven __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 569227825Stheraven } 570227825Stheraven } 571227825Stheraven return __result; 572227825Stheraven} 573227825Stheraven 574227825Stheraventemplate <class _C, bool _IsConst> 575227825Stheraven__bit_iterator<_C, false> 576227825Stheraven__copy_backward_unaligned(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, 577227825Stheraven __bit_iterator<_C, false> __result) 578227825Stheraven{ 579227825Stheraven typedef __bit_iterator<_C, _IsConst> _In; 580227825Stheraven typedef typename _In::difference_type difference_type; 581227825Stheraven typedef typename _In::__storage_type __storage_type; 582227825Stheraven static const unsigned __bits_per_word = _In::__bits_per_word; 583227825Stheraven difference_type __n = __last - __first; 584227825Stheraven if (__n > 0) 585227825Stheraven { 586227825Stheraven // do first word 587227825Stheraven if (__last.__ctz_ != 0) 588227825Stheraven { 589227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); 590227825Stheraven __n -= __dn; 591227825Stheraven unsigned __clz_l = __bits_per_word - __last.__ctz_; 592227825Stheraven __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l); 593227825Stheraven __storage_type __b = *__last.__seg_ & __m; 594227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 595227825Stheraven __storage_type __ddn = _VSTD::min(__dn, static_cast<difference_type>(__result.__ctz_)); 596227825Stheraven if (__ddn > 0) 597227825Stheraven { 598227825Stheraven __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r); 599227825Stheraven *__result.__seg_ &= ~__m; 600227825Stheraven if (__result.__ctz_ > __last.__ctz_) 601227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 602227825Stheraven else 603227825Stheraven *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_); 604227825Stheraven __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) + 605227825Stheraven __result.__ctz_) % __bits_per_word); 606227825Stheraven __dn -= __ddn; 607227825Stheraven } 608227825Stheraven if (__dn > 0) 609227825Stheraven { 610227825Stheraven // __result.__ctz_ == 0 611227825Stheraven --__result.__seg_; 612227825Stheraven __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1)); 613227825Stheraven __m = ~__storage_type(0) << __result.__ctz_; 614227825Stheraven *__result.__seg_ &= ~__m; 615227825Stheraven __last.__ctz_ -= __dn + __ddn; 616227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 617227825Stheraven } 618227825Stheraven // __last.__ctz_ = 0 619227825Stheraven } 620227825Stheraven // __last.__ctz_ == 0 || __n == 0 621227825Stheraven // __result.__ctz_ != 0 || __n == 0 622227825Stheraven // do middle words 623227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 624227825Stheraven __storage_type __m = ~__storage_type(0) >> __clz_r; 625227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word) 626227825Stheraven { 627227825Stheraven __storage_type __b = *--__last.__seg_; 628227825Stheraven *__result.__seg_ &= ~__m; 629227825Stheraven *__result.__seg_ |= __b >> __clz_r; 630227825Stheraven *--__result.__seg_ &= __m; 631227825Stheraven *__result.__seg_ |= __b << __result.__ctz_; 632227825Stheraven } 633227825Stheraven // do last word 634227825Stheraven if (__n > 0) 635227825Stheraven { 636227825Stheraven __m = ~__storage_type(0) << (__bits_per_word - __n); 637227825Stheraven __storage_type __b = *--__last.__seg_ & __m; 638227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 639227825Stheraven __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__result.__ctz_)); 640227825Stheraven __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r); 641227825Stheraven *__result.__seg_ &= ~__m; 642227825Stheraven *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_); 643227825Stheraven __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 644227825Stheraven __result.__ctz_) % __bits_per_word); 645227825Stheraven __n -= __dn; 646227825Stheraven if (__n > 0) 647227825Stheraven { 648227825Stheraven // __result.__ctz_ == 0 649227825Stheraven --__result.__seg_; 650227825Stheraven __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 651227825Stheraven __m = ~__storage_type(0) << __result.__ctz_; 652227825Stheraven *__result.__seg_ &= ~__m; 653227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn)); 654227825Stheraven } 655227825Stheraven } 656227825Stheraven } 657227825Stheraven return __result; 658227825Stheraven} 659227825Stheraven 660227825Stheraventemplate <class _C, bool _IsConst> 661227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 662227825Stheraven__bit_iterator<_C, false> 663227825Stheravencopy_backward(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, __bit_iterator<_C, false> __result) 664227825Stheraven{ 665227825Stheraven if (__last.__ctz_ == __result.__ctz_) 666227825Stheraven return __copy_backward_aligned(__first, __last, __result); 667227825Stheraven return __copy_backward_unaligned(__first, __last, __result); 668227825Stheraven} 669227825Stheraven 670227825Stheraven// move 671227825Stheraven 672227825Stheraventemplate <class _C, bool _IsConst> 673227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 674227825Stheraven__bit_iterator<_C, false> 675227825Stheravenmove(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, __bit_iterator<_C, false> __result) 676227825Stheraven{ 677227825Stheraven return _VSTD::copy(__first, __last, __result); 678227825Stheraven} 679227825Stheraven 680227825Stheraven// move_backward 681227825Stheraven 682227825Stheraventemplate <class _C, bool _IsConst> 683227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 684227825Stheraven__bit_iterator<_C, false> 685227825Stheravenmove_backward(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, __bit_iterator<_C, false> __result) 686227825Stheraven{ 687227825Stheraven return _VSTD::copy(__first, __last, __result); 688227825Stheraven} 689227825Stheraven 690227825Stheraven// swap_ranges 691227825Stheraven 692227825Stheraventemplate <class __C1, class __C2> 693227825Stheraven__bit_iterator<__C2, false> 694227825Stheraven__swap_ranges_aligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, 695227825Stheraven __bit_iterator<__C2, false> __result) 696227825Stheraven{ 697227825Stheraven typedef __bit_iterator<__C1, false> _I1; 698227825Stheraven typedef typename _I1::difference_type difference_type; 699227825Stheraven typedef typename _I1::__storage_type __storage_type; 700227825Stheraven static const unsigned __bits_per_word = _I1::__bits_per_word; 701227825Stheraven difference_type __n = __last - __first; 702227825Stheraven if (__n > 0) 703227825Stheraven { 704227825Stheraven // do first word 705227825Stheraven if (__first.__ctz_ != 0) 706227825Stheraven { 707227825Stheraven unsigned __clz = __bits_per_word - __first.__ctz_; 708227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 709227825Stheraven __n -= __dn; 710227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 711227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 712227825Stheraven *__first.__seg_ &= ~__m; 713227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 714227825Stheraven *__result.__seg_ &= ~__m; 715227825Stheraven *__result.__seg_ |= __b1; 716227825Stheraven *__first.__seg_ |= __b2; 717227825Stheraven __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 718227825Stheraven __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 719227825Stheraven ++__first.__seg_; 720227825Stheraven // __first.__ctz_ = 0; 721227825Stheraven } 722227825Stheraven // __first.__ctz_ == 0; 723227825Stheraven // do middle words 724227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_) 725227825Stheraven swap(*__first.__seg_, *__result.__seg_); 726227825Stheraven // do last word 727227825Stheraven if (__n > 0) 728227825Stheraven { 729227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 730227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 731227825Stheraven *__first.__seg_ &= ~__m; 732227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 733227825Stheraven *__result.__seg_ &= ~__m; 734227825Stheraven *__result.__seg_ |= __b1; 735227825Stheraven *__first.__seg_ |= __b2; 736227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 737227825Stheraven } 738227825Stheraven } 739227825Stheraven return __result; 740227825Stheraven} 741227825Stheraven 742227825Stheraventemplate <class __C1, class __C2> 743227825Stheraven__bit_iterator<__C2, false> 744227825Stheraven__swap_ranges_unaligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, 745227825Stheraven __bit_iterator<__C2, false> __result) 746227825Stheraven{ 747227825Stheraven typedef __bit_iterator<__C1, false> _I1; 748227825Stheraven typedef typename _I1::difference_type difference_type; 749227825Stheraven typedef typename _I1::__storage_type __storage_type; 750227825Stheraven static const unsigned __bits_per_word = _I1::__bits_per_word; 751227825Stheraven difference_type __n = __last - __first; 752227825Stheraven if (__n > 0) 753227825Stheraven { 754227825Stheraven // do first word 755227825Stheraven if (__first.__ctz_ != 0) 756227825Stheraven { 757227825Stheraven unsigned __clz_f = __bits_per_word - __first.__ctz_; 758227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 759227825Stheraven __n -= __dn; 760227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 761227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 762227825Stheraven *__first.__seg_ &= ~__m; 763227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 764227825Stheraven __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 765227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 766227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 767227825Stheraven *__result.__seg_ &= ~__m; 768227825Stheraven if (__result.__ctz_ > __first.__ctz_) 769227825Stheraven { 770227825Stheraven unsigned __s = __result.__ctz_ - __first.__ctz_; 771227825Stheraven *__result.__seg_ |= __b1 << __s; 772227825Stheraven *__first.__seg_ |= __b2 >> __s; 773227825Stheraven } 774227825Stheraven else 775227825Stheraven { 776227825Stheraven unsigned __s = __first.__ctz_ - __result.__ctz_; 777227825Stheraven *__result.__seg_ |= __b1 >> __s; 778227825Stheraven *__first.__seg_ |= __b2 << __s; 779227825Stheraven } 780227825Stheraven __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 781227825Stheraven __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 782227825Stheraven __dn -= __ddn; 783227825Stheraven if (__dn > 0) 784227825Stheraven { 785227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __dn); 786227825Stheraven __b2 = *__result.__seg_ & __m; 787227825Stheraven *__result.__seg_ &= ~__m; 788227825Stheraven unsigned __s = __first.__ctz_ + __ddn; 789227825Stheraven *__result.__seg_ |= __b1 >> __s; 790227825Stheraven *__first.__seg_ |= __b2 << __s; 791227825Stheraven __result.__ctz_ = static_cast<unsigned>(__dn); 792227825Stheraven } 793227825Stheraven ++__first.__seg_; 794227825Stheraven // __first.__ctz_ = 0; 795227825Stheraven } 796227825Stheraven // __first.__ctz_ == 0; 797227825Stheraven // do middle words 798227825Stheraven __storage_type __m = ~__storage_type(0) << __result.__ctz_; 799227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 800227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 801227825Stheraven { 802227825Stheraven __storage_type __b1 = *__first.__seg_; 803227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 804227825Stheraven *__result.__seg_ &= ~__m; 805227825Stheraven *__result.__seg_ |= __b1 << __result.__ctz_; 806227825Stheraven *__first.__seg_ = __b2 >> __result.__ctz_; 807227825Stheraven ++__result.__seg_; 808227825Stheraven __b2 = *__result.__seg_ & ~__m; 809227825Stheraven *__result.__seg_ &= __m; 810227825Stheraven *__result.__seg_ |= __b1 >> __clz_r; 811227825Stheraven *__first.__seg_ |= __b2 << __clz_r; 812227825Stheraven } 813227825Stheraven // do last word 814227825Stheraven if (__n > 0) 815227825Stheraven { 816227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 817227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 818227825Stheraven *__first.__seg_ &= ~__m; 819227825Stheraven __storage_type __dn = _VSTD::min<__storage_type>(__n, __clz_r); 820227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 821227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 822227825Stheraven *__result.__seg_ &= ~__m; 823227825Stheraven *__result.__seg_ |= __b1 << __result.__ctz_; 824227825Stheraven *__first.__seg_ |= __b2 >> __result.__ctz_; 825227825Stheraven __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 826227825Stheraven __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 827227825Stheraven __n -= __dn; 828227825Stheraven if (__n > 0) 829227825Stheraven { 830227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 831227825Stheraven __b2 = *__result.__seg_ & __m; 832227825Stheraven *__result.__seg_ &= ~__m; 833227825Stheraven *__result.__seg_ |= __b1 >> __dn; 834227825Stheraven *__first.__seg_ |= __b2 << __dn; 835227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 836227825Stheraven } 837227825Stheraven } 838227825Stheraven } 839227825Stheraven return __result; 840227825Stheraven} 841227825Stheraven 842227825Stheraventemplate <class __C1, class __C2> 843227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 844227825Stheraven__bit_iterator<__C2, false> 845227825Stheravenswap_ranges(__bit_iterator<__C1, false> __first1, __bit_iterator<__C1, false> __last1, 846227825Stheraven __bit_iterator<__C2, false> __first2) 847227825Stheraven{ 848227825Stheraven if (__first1.__ctz_ == __first2.__ctz_) 849227825Stheraven return __swap_ranges_aligned(__first1, __last1, __first2); 850227825Stheraven return __swap_ranges_unaligned(__first1, __last1, __first2); 851227825Stheraven} 852227825Stheraven 853227825Stheraven// rotate 854227825Stheraven 855227825Stheraventemplate <class _C> 856227825Stheravenstruct __bit_array 857227825Stheraven{ 858227825Stheraven typedef typename _C::difference_type difference_type; 859227825Stheraven typedef typename _C::__storage_type __storage_type; 860227825Stheraven typedef typename _C::iterator iterator; 861227825Stheraven static const unsigned __bits_per_word = _C::__bits_per_word; 862227825Stheraven static const unsigned _N = 4; 863227825Stheraven 864227825Stheraven difference_type __size_; 865227825Stheraven __storage_type __word_[_N]; 866227825Stheraven 867227825Stheraven _LIBCPP_INLINE_VISIBILITY static difference_type capacity() 868227825Stheraven {return static_cast<difference_type>(_N * __bits_per_word);} 869227825Stheraven _LIBCPP_INLINE_VISIBILITY explicit __bit_array(difference_type __s) : __size_(__s) {} 870227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator begin() {return iterator(__word_, 0);} 871227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator end() {return iterator(__word_ + __size_ / __bits_per_word, 872227825Stheraven static_cast<unsigned>(__size_ % __bits_per_word));} 873227825Stheraven}; 874227825Stheraven 875227825Stheraventemplate <class _C> 876227825Stheraven__bit_iterator<_C, false> 877227825Stheravenrotate(__bit_iterator<_C, false> __first, __bit_iterator<_C, false> __middle, __bit_iterator<_C, false> __last) 878227825Stheraven{ 879227825Stheraven typedef __bit_iterator<_C, false> _I1; 880227825Stheraven typedef typename _I1::difference_type difference_type; 881227825Stheraven typedef typename _I1::__storage_type __storage_type; 882227825Stheraven static const unsigned __bits_per_word = _I1::__bits_per_word; 883227825Stheraven difference_type __d1 = __middle - __first; 884227825Stheraven difference_type __d2 = __last - __middle; 885227825Stheraven _I1 __r = __first + __d2; 886227825Stheraven while (__d1 != 0 && __d2 != 0) 887227825Stheraven { 888227825Stheraven if (__d1 <= __d2) 889227825Stheraven { 890227825Stheraven if (__d1 <= __bit_array<_C>::capacity()) 891227825Stheraven { 892227825Stheraven __bit_array<_C> __b(__d1); 893227825Stheraven _VSTD::copy(__first, __middle, __b.begin()); 894227825Stheraven _VSTD::copy(__b.begin(), __b.end(), _VSTD::copy(__middle, __last, __first)); 895227825Stheraven break; 896227825Stheraven } 897227825Stheraven else 898227825Stheraven { 899227825Stheraven __bit_iterator<_C, false> __mp = _VSTD::swap_ranges(__first, __middle, __middle); 900227825Stheraven __first = __middle; 901227825Stheraven __middle = __mp; 902227825Stheraven __d2 -= __d1; 903227825Stheraven } 904227825Stheraven } 905227825Stheraven else 906227825Stheraven { 907227825Stheraven if (__d2 <= __bit_array<_C>::capacity()) 908227825Stheraven { 909227825Stheraven __bit_array<_C> __b(__d2); 910227825Stheraven _VSTD::copy(__middle, __last, __b.begin()); 911227825Stheraven _VSTD::copy_backward(__b.begin(), __b.end(), _VSTD::copy_backward(__first, __middle, __last)); 912227825Stheraven break; 913227825Stheraven } 914227825Stheraven else 915227825Stheraven { 916227825Stheraven __bit_iterator<_C, false> __mp = __first + __d2; 917227825Stheraven _VSTD::swap_ranges(__first, __mp, __middle); 918227825Stheraven __first = __mp; 919227825Stheraven __d1 -= __d2; 920227825Stheraven } 921227825Stheraven } 922227825Stheraven } 923227825Stheraven return __r; 924227825Stheraven} 925227825Stheraven 926227825Stheraven// equal 927227825Stheraven 928227825Stheraventemplate <class _C> 929227825Stheravenbool 930227825Stheraven__equal_unaligned(__bit_iterator<_C, true> __first1, __bit_iterator<_C, true> __last1, 931227825Stheraven __bit_iterator<_C, true> __first2) 932227825Stheraven{ 933227825Stheraven typedef __bit_iterator<_C, true> _It; 934227825Stheraven typedef typename _It::difference_type difference_type; 935227825Stheraven typedef typename _It::__storage_type __storage_type; 936227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 937227825Stheraven difference_type __n = __last1 - __first1; 938227825Stheraven if (__n > 0) 939227825Stheraven { 940227825Stheraven // do first word 941227825Stheraven if (__first1.__ctz_ != 0) 942227825Stheraven { 943227825Stheraven unsigned __clz_f = __bits_per_word - __first1.__ctz_; 944227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 945227825Stheraven __n -= __dn; 946227825Stheraven __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 947227825Stheraven __storage_type __b = *__first1.__seg_ & __m; 948227825Stheraven unsigned __clz_r = __bits_per_word - __first2.__ctz_; 949227825Stheraven __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 950227825Stheraven __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 951227825Stheraven if (__first2.__ctz_ > __first1.__ctz_) 952227825Stheraven if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_))) 953227825Stheraven return false; 954227825Stheraven else 955227825Stheraven if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_))) 956227825Stheraven return false; 957227825Stheraven __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word; 958227825Stheraven __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word); 959227825Stheraven __dn -= __ddn; 960227825Stheraven if (__dn > 0) 961227825Stheraven { 962227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __dn); 963227825Stheraven if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn))) 964227825Stheraven return false; 965227825Stheraven __first2.__ctz_ = static_cast<unsigned>(__dn); 966227825Stheraven } 967227825Stheraven ++__first1.__seg_; 968227825Stheraven // __first1.__ctz_ = 0; 969227825Stheraven } 970227825Stheraven // __first1.__ctz_ == 0; 971227825Stheraven // do middle words 972227825Stheraven unsigned __clz_r = __bits_per_word - __first2.__ctz_; 973227825Stheraven __storage_type __m = ~__storage_type(0) << __first2.__ctz_; 974227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_) 975227825Stheraven { 976227825Stheraven __storage_type __b = *__first1.__seg_; 977227825Stheraven if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 978227825Stheraven return false; 979227825Stheraven ++__first2.__seg_; 980227825Stheraven if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r)) 981227825Stheraven return false; 982227825Stheraven } 983227825Stheraven // do last word 984227825Stheraven if (__n > 0) 985227825Stheraven { 986227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 987227825Stheraven __storage_type __b = *__first1.__seg_ & __m; 988227825Stheraven __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); 989227825Stheraven __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 990227825Stheraven if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 991227825Stheraven return false; 992227825Stheraven __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word; 993227825Stheraven __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word); 994227825Stheraven __n -= __dn; 995227825Stheraven if (__n > 0) 996227825Stheraven { 997227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 998227825Stheraven if ((*__first2.__seg_ & __m) != (__b >> __dn)) 999227825Stheraven return false; 1000227825Stheraven } 1001227825Stheraven } 1002227825Stheraven } 1003227825Stheraven return true; 1004227825Stheraven} 1005227825Stheraven 1006227825Stheraventemplate <class _C> 1007227825Stheravenbool 1008227825Stheraven__equal_aligned(__bit_iterator<_C, true> __first1, __bit_iterator<_C, true> __last1, 1009227825Stheraven __bit_iterator<_C, true> __first2) 1010227825Stheraven{ 1011227825Stheraven typedef __bit_iterator<_C, true> _It; 1012227825Stheraven typedef typename _It::difference_type difference_type; 1013227825Stheraven typedef typename _It::__storage_type __storage_type; 1014227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 1015227825Stheraven difference_type __n = __last1 - __first1; 1016227825Stheraven if (__n > 0) 1017227825Stheraven { 1018227825Stheraven // do first word 1019227825Stheraven if (__first1.__ctz_ != 0) 1020227825Stheraven { 1021227825Stheraven unsigned __clz = __bits_per_word - __first1.__ctz_; 1022227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 1023227825Stheraven __n -= __dn; 1024227825Stheraven __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 1025227825Stheraven if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 1026227825Stheraven return false; 1027227825Stheraven ++__first2.__seg_; 1028227825Stheraven ++__first1.__seg_; 1029227825Stheraven // __first1.__ctz_ = 0; 1030227825Stheraven // __first2.__ctz_ = 0; 1031227825Stheraven } 1032227825Stheraven // __first1.__ctz_ == 0; 1033227825Stheraven // __first2.__ctz_ == 0; 1034227825Stheraven // do middle words 1035227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_) 1036227825Stheraven if (*__first2.__seg_ != *__first1.__seg_) 1037227825Stheraven return false; 1038227825Stheraven // do last word 1039227825Stheraven if (__n > 0) 1040227825Stheraven { 1041227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 1042227825Stheraven if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 1043227825Stheraven return false; 1044227825Stheraven } 1045227825Stheraven } 1046227825Stheraven return true; 1047227825Stheraven} 1048227825Stheraven 1049227825Stheraventemplate <class _C, bool _IC1, bool _IC2> 1050227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1051227825Stheravenbool 1052227825Stheravenequal(__bit_iterator<_C, _IC1> __first1, __bit_iterator<_C, _IC1> __last1, __bit_iterator<_C, _IC2> __first2) 1053227825Stheraven{ 1054227825Stheraven if (__first1.__ctz_ == __first2.__ctz_) 1055227825Stheraven return __equal_aligned(__first1, __last1, __first2); 1056227825Stheraven return __equal_unaligned(__first1, __last1, __first2); 1057227825Stheraven} 1058227825Stheraven 1059227825Stheraventemplate <class _C, bool _IsConst> 1060227825Stheravenclass __bit_iterator 1061227825Stheraven{ 1062227825Stheravenpublic: 1063227825Stheraven typedef typename _C::difference_type difference_type; 1064227825Stheraven typedef bool value_type; 1065227825Stheraven typedef __bit_iterator pointer; 1066227825Stheraven typedef typename conditional<_IsConst, __bit_const_reference<_C>, __bit_reference<_C> >::type reference; 1067227825Stheraven typedef random_access_iterator_tag iterator_category; 1068227825Stheraven 1069227825Stheravenprivate: 1070227825Stheraven typedef typename _C::__storage_type __storage_type; 1071227825Stheraven typedef typename conditional<_IsConst, typename _C::__const_storage_pointer, 1072227825Stheraven typename _C::__storage_pointer>::type __storage_pointer; 1073227825Stheraven static const unsigned __bits_per_word = _C::__bits_per_word; 1074227825Stheraven 1075227825Stheraven __storage_pointer __seg_; 1076227825Stheraven unsigned __ctz_; 1077227825Stheraven 1078227825Stheravenpublic: 1079227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator() _NOEXCEPT {} 1080227825Stheraven 1081227825Stheraven _LIBCPP_INLINE_VISIBILITY 1082227825Stheraven __bit_iterator(const __bit_iterator<_C, false>& __it) _NOEXCEPT 1083227825Stheraven : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {} 1084227825Stheraven 1085227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT 1086227825Stheraven {return reference(__seg_, __storage_type(1) << __ctz_);} 1087227825Stheraven 1088227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator++() 1089227825Stheraven { 1090227825Stheraven if (__ctz_ != __bits_per_word-1) 1091227825Stheraven ++__ctz_; 1092227825Stheraven else 1093227825Stheraven { 1094227825Stheraven __ctz_ = 0; 1095227825Stheraven ++__seg_; 1096227825Stheraven } 1097227825Stheraven return *this; 1098227825Stheraven } 1099227825Stheraven 1100227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator operator++(int) 1101227825Stheraven { 1102227825Stheraven __bit_iterator __tmp = *this; 1103227825Stheraven ++(*this); 1104227825Stheraven return __tmp; 1105227825Stheraven } 1106227825Stheraven 1107227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator--() 1108227825Stheraven { 1109227825Stheraven if (__ctz_ != 0) 1110227825Stheraven --__ctz_; 1111227825Stheraven else 1112227825Stheraven { 1113227825Stheraven __ctz_ = __bits_per_word - 1; 1114227825Stheraven --__seg_; 1115227825Stheraven } 1116227825Stheraven return *this; 1117227825Stheraven } 1118227825Stheraven 1119227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator operator--(int) 1120227825Stheraven { 1121227825Stheraven __bit_iterator __tmp = *this; 1122227825Stheraven --(*this); 1123227825Stheraven return __tmp; 1124227825Stheraven } 1125227825Stheraven 1126227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator+=(difference_type __n) 1127227825Stheraven { 1128227825Stheraven if (__n >= 0) 1129227825Stheraven __seg_ += (__n + __ctz_) / __bits_per_word; 1130227825Stheraven else 1131227825Stheraven __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1) 1132227825Stheraven / static_cast<difference_type>(__bits_per_word); 1133227825Stheraven __n &= (__bits_per_word - 1); 1134227825Stheraven __ctz_ = static_cast<unsigned>((__n + __ctz_) % __bits_per_word); 1135227825Stheraven return *this; 1136227825Stheraven } 1137227825Stheraven 1138227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator-=(difference_type __n) 1139227825Stheraven { 1140227825Stheraven return *this += -__n; 1141227825Stheraven } 1142227825Stheraven 1143227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator operator+(difference_type __n) const 1144227825Stheraven { 1145227825Stheraven __bit_iterator __t(*this); 1146227825Stheraven __t += __n; 1147227825Stheraven return __t; 1148227825Stheraven } 1149227825Stheraven 1150227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator operator-(difference_type __n) const 1151227825Stheraven { 1152227825Stheraven __bit_iterator __t(*this); 1153227825Stheraven __t -= __n; 1154227825Stheraven return __t; 1155227825Stheraven } 1156227825Stheraven 1157227825Stheraven _LIBCPP_INLINE_VISIBILITY 1158227825Stheraven friend __bit_iterator operator+(difference_type __n, const __bit_iterator& __it) {return __it + __n;} 1159227825Stheraven 1160227825Stheraven _LIBCPP_INLINE_VISIBILITY 1161227825Stheraven friend difference_type operator-(const __bit_iterator& __x, const __bit_iterator& __y) 1162227825Stheraven {return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;} 1163227825Stheraven 1164227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const {return *(*this + __n);} 1165227825Stheraven 1166227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator==(const __bit_iterator& __x, const __bit_iterator& __y) 1167227825Stheraven {return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;} 1168227825Stheraven 1169227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator!=(const __bit_iterator& __x, const __bit_iterator& __y) 1170227825Stheraven {return !(__x == __y);} 1171227825Stheraven 1172227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator<(const __bit_iterator& __x, const __bit_iterator& __y) 1173227825Stheraven {return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);} 1174227825Stheraven 1175227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator>(const __bit_iterator& __x, const __bit_iterator& __y) 1176227825Stheraven {return __y < __x;} 1177227825Stheraven 1178227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y) 1179227825Stheraven {return !(__y < __x);} 1180227825Stheraven 1181227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y) 1182227825Stheraven {return !(__x < __y);} 1183227825Stheraven 1184227825Stheravenprivate: 1185227825Stheraven _LIBCPP_INLINE_VISIBILITY 1186227825Stheraven __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT 1187227825Stheraven : __seg_(__s), __ctz_(__ctz) {} 1188227825Stheraven 1189227825Stheraven#if defined(__clang__) 1190227825Stheraven friend typename _C::__self; 1191227825Stheraven#else 1192227825Stheraven friend class _C::__self; 1193227825Stheraven#endif 1194227825Stheraven friend class __bit_reference<_C>; 1195227825Stheraven friend class __bit_const_reference<_C>; 1196227825Stheraven friend class __bit_iterator<_C, true>; 1197227825Stheraven template <class _D> friend struct __bit_array; 1198227825Stheraven template <class _D> friend void __fill_n_false(__bit_iterator<_D, false> __first, typename _D::size_type __n); 1199227825Stheraven template <class _D> friend void __fill_n_true(__bit_iterator<_D, false> __first, typename _D::size_type __n); 1200227825Stheraven template <class _D, bool _IC> friend __bit_iterator<_D, false> __copy_aligned(__bit_iterator<_D, _IC> __first, 1201227825Stheraven __bit_iterator<_D, _IC> __last, 1202227825Stheraven __bit_iterator<_D, false> __result); 1203227825Stheraven template <class _D, bool _IC> friend __bit_iterator<_D, false> __copy_unaligned(__bit_iterator<_D, _IC> __first, 1204227825Stheraven __bit_iterator<_D, _IC> __last, 1205227825Stheraven __bit_iterator<_D, false> __result); 1206227825Stheraven template <class _D, bool _IC> friend __bit_iterator<_D, false> copy(__bit_iterator<_D, _IC> __first, 1207227825Stheraven __bit_iterator<_D, _IC> __last, 1208227825Stheraven __bit_iterator<_D, false> __result); 1209227825Stheraven template <class _D, bool _IC> friend __bit_iterator<_D, false> __copy_backward_aligned(__bit_iterator<_D, _IC> __first, 1210227825Stheraven __bit_iterator<_D, _IC> __last, 1211227825Stheraven __bit_iterator<_D, false> __result); 1212227825Stheraven template <class _D, bool _IC> friend __bit_iterator<_D, false> __copy_backward_unaligned(__bit_iterator<_D, _IC> __first, 1213227825Stheraven __bit_iterator<_D, _IC> __last, 1214227825Stheraven __bit_iterator<_D, false> __result); 1215227825Stheraven template <class _D, bool _IC> friend __bit_iterator<_D, false> copy_backward(__bit_iterator<_D, _IC> __first, 1216227825Stheraven __bit_iterator<_D, _IC> __last, 1217227825Stheraven __bit_iterator<_D, false> __result); 1218227825Stheraven template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_aligned(__bit_iterator<__C1, false>, 1219227825Stheraven __bit_iterator<__C1, false>, 1220227825Stheraven __bit_iterator<__C2, false>); 1221227825Stheraven template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_unaligned(__bit_iterator<__C1, false>, 1222227825Stheraven __bit_iterator<__C1, false>, 1223227825Stheraven __bit_iterator<__C2, false>); 1224227825Stheraven template <class __C1, class __C2>friend __bit_iterator<__C2, false> swap_ranges(__bit_iterator<__C1, false>, 1225227825Stheraven __bit_iterator<__C1, false>, 1226227825Stheraven __bit_iterator<__C2, false>); 1227227825Stheraven template <class _D> friend __bit_iterator<_D, false> rotate(__bit_iterator<_D, false>, 1228227825Stheraven __bit_iterator<_D, false>, 1229227825Stheraven __bit_iterator<_D, false>); 1230227825Stheraven template <class _D> friend bool __equal_aligned(__bit_iterator<_D, true>, 1231227825Stheraven __bit_iterator<_D, true>, 1232227825Stheraven __bit_iterator<_D, true>); 1233227825Stheraven template <class _D> friend bool __equal_unaligned(__bit_iterator<_D, true>, 1234227825Stheraven __bit_iterator<_D, true>, 1235227825Stheraven __bit_iterator<_D, true>); 1236227825Stheraven template <class _D, bool _IC1, bool _IC2> friend bool equal(__bit_iterator<_D, _IC1>, 1237227825Stheraven __bit_iterator<_D, _IC1>, 1238227825Stheraven __bit_iterator<_D, _IC2>); 1239227825Stheraven template <class _D> friend __bit_iterator<_D, false> __find_bool_true(__bit_iterator<_D, false>, 1240227825Stheraven typename _D::size_type); 1241227825Stheraven template <class _D> friend __bit_iterator<_D, false> __find_bool_false(__bit_iterator<_D, false>, 1242227825Stheraven typename _D::size_type); 1243227825Stheraven}; 1244227825Stheraven 1245227825Stheraven_LIBCPP_END_NAMESPACE_STD 1246227825Stheraven 1247227825Stheraven#endif // _LIBCPP___BIT_REFERENCE 1248