__bit_reference revision 241903
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 17232950Stheraven#include <__undef_min_max> 18232950Stheraven 19227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 20227825Stheraven#pragma GCC system_header 21227825Stheraven#endif 22227825Stheraven 23227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 24227825Stheraven 25241903Sdimtemplate <class _Cp, bool _IsConst, typename _Cp::__storage_type = 0> class __bit_iterator; 26232950Stheraventemplate <class _Cp> class __bit_const_reference; 27227825Stheraven 28227825Stheraventemplate <class _Tp> 29227825Stheravenstruct __has_storage_type 30227825Stheraven{ 31227825Stheraven static const bool value = false; 32227825Stheraven}; 33227825Stheraven 34232950Stheraventemplate <class _Cp, bool = __has_storage_type<_Cp>::value> 35227825Stheravenclass __bit_reference 36227825Stheraven{ 37232950Stheraven typedef typename _Cp::__storage_type __storage_type; 38232950Stheraven typedef typename _Cp::__storage_pointer __storage_pointer; 39227825Stheraven 40227825Stheraven __storage_pointer __seg_; 41227825Stheraven __storage_type __mask_; 42227825Stheraven 43227825Stheraven#if defined(__clang__) 44232950Stheraven friend typename _Cp::__self; 45227825Stheraven#else 46232950Stheraven friend class _Cp::__self; 47227825Stheraven#endif 48232950Stheraven friend class __bit_const_reference<_Cp>; 49232950Stheraven friend class __bit_iterator<_Cp, false>; 50227825Stheravenpublic: 51227825Stheraven _LIBCPP_INLINE_VISIBILITY operator bool() const _NOEXCEPT 52227825Stheraven {return static_cast<bool>(*__seg_ & __mask_);} 53227825Stheraven _LIBCPP_INLINE_VISIBILITY bool operator ~() const _NOEXCEPT 54227825Stheraven {return !static_cast<bool>(*this);} 55227825Stheraven 56227825Stheraven _LIBCPP_INLINE_VISIBILITY 57227825Stheraven __bit_reference& operator=(bool __x) _NOEXCEPT 58227825Stheraven { 59227825Stheraven if (__x) 60227825Stheraven *__seg_ |= __mask_; 61227825Stheraven else 62227825Stheraven *__seg_ &= ~__mask_; 63227825Stheraven return *this; 64227825Stheraven } 65227825Stheraven 66227825Stheraven _LIBCPP_INLINE_VISIBILITY 67227825Stheraven __bit_reference& operator=(const __bit_reference& __x) _NOEXCEPT 68227825Stheraven {return operator=(static_cast<bool>(__x));} 69227825Stheraven 70227825Stheraven _LIBCPP_INLINE_VISIBILITY void flip() _NOEXCEPT {*__seg_ ^= __mask_;} 71232950Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, false> operator&() const _NOEXCEPT 72232950Stheraven {return __bit_iterator<_Cp, false>(__seg_, static_cast<unsigned>(__ctz(__mask_)));} 73227825Stheravenprivate: 74227825Stheraven _LIBCPP_INLINE_VISIBILITY 75227825Stheraven __bit_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT 76227825Stheraven : __seg_(__s), __mask_(__m) {} 77227825Stheraven}; 78227825Stheraven 79232950Stheraventemplate <class _Cp> 80232950Stheravenclass __bit_reference<_Cp, false> 81227825Stheraven{ 82227825Stheraven}; 83227825Stheraven 84232950Stheraventemplate <class _Cp, class _Dp> 85227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 86227825Stheravenvoid 87232950Stheravenswap(__bit_reference<_Cp> __x, __bit_reference<_Dp> __y) _NOEXCEPT 88227825Stheraven{ 89227825Stheraven bool __t = __x; 90227825Stheraven __x = __y; 91227825Stheraven __y = __t; 92227825Stheraven} 93227825Stheraven 94232950Stheraventemplate <class _Cp> 95227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 96227825Stheravenvoid 97232950Stheravenswap(__bit_reference<_Cp> __x, bool& __y) _NOEXCEPT 98227825Stheraven{ 99227825Stheraven bool __t = __x; 100227825Stheraven __x = __y; 101227825Stheraven __y = __t; 102227825Stheraven} 103227825Stheraven 104232950Stheraventemplate <class _Cp> 105227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 106227825Stheravenvoid 107232950Stheravenswap(bool& __x, __bit_reference<_Cp> __y) _NOEXCEPT 108227825Stheraven{ 109227825Stheraven bool __t = __x; 110227825Stheraven __x = __y; 111227825Stheraven __y = __t; 112227825Stheraven} 113227825Stheraven 114232950Stheraventemplate <class _Cp> 115227825Stheravenclass __bit_const_reference 116227825Stheraven{ 117232950Stheraven typedef typename _Cp::__storage_type __storage_type; 118232950Stheraven typedef typename _Cp::__const_storage_pointer __storage_pointer; 119227825Stheraven 120227825Stheraven __storage_pointer __seg_; 121227825Stheraven __storage_type __mask_; 122227825Stheraven 123227825Stheraven#if defined(__clang__) 124232950Stheraven friend typename _Cp::__self; 125227825Stheraven#else 126232950Stheraven friend class _Cp::__self; 127227825Stheraven#endif 128232950Stheraven friend class __bit_iterator<_Cp, true>; 129227825Stheravenpublic: 130227825Stheraven _LIBCPP_INLINE_VISIBILITY 131232950Stheraven __bit_const_reference(const __bit_reference<_Cp>& __x) _NOEXCEPT 132227825Stheraven : __seg_(__x.__seg_), __mask_(__x.__mask_) {} 133227825Stheraven 134241903Sdim _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR operator bool() const _NOEXCEPT 135227825Stheraven {return static_cast<bool>(*__seg_ & __mask_);} 136227825Stheraven 137232950Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, true> operator&() const _NOEXCEPT 138232950Stheraven {return __bit_iterator<_Cp, true>(__seg_, static_cast<unsigned>(__ctz(__mask_)));} 139227825Stheravenprivate: 140227825Stheraven _LIBCPP_INLINE_VISIBILITY 141241903Sdim _LIBCPP_CONSTEXPR 142227825Stheraven __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT 143227825Stheraven : __seg_(__s), __mask_(__m) {} 144227825Stheraven 145227825Stheraven __bit_const_reference& operator=(const __bit_const_reference& __x); 146227825Stheraven}; 147227825Stheraven 148227825Stheraven// find 149227825Stheraven 150241903Sdimtemplate <class _Cp, bool _IsConst> 151241903Sdim__bit_iterator<_Cp, _IsConst> 152241903Sdim__find_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 153227825Stheraven{ 154241903Sdim typedef __bit_iterator<_Cp, _IsConst> _It; 155227825Stheraven typedef typename _It::__storage_type __storage_type; 156227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 157227825Stheraven // do first partial word 158227825Stheraven if (__first.__ctz_ != 0) 159227825Stheraven { 160227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 161227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 162227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 163227825Stheraven __storage_type __b = *__first.__seg_ & __m; 164227825Stheraven if (__b) 165227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 166227825Stheraven __n -= __dn; 167227825Stheraven ++__first.__seg_; 168227825Stheraven } 169227825Stheraven // do middle whole words 170227825Stheraven for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 171227825Stheraven if (*__first.__seg_) 172227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(*__first.__seg_))); 173227825Stheraven // do last partial word 174227825Stheraven if (__n > 0) 175227825Stheraven { 176227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 177227825Stheraven __storage_type __b = *__first.__seg_ & __m; 178227825Stheraven if (__b) 179227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 180227825Stheraven } 181227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(__n)); 182227825Stheraven} 183227825Stheraven 184241903Sdimtemplate <class _Cp, bool _IsConst> 185241903Sdim__bit_iterator<_Cp, _IsConst> 186241903Sdim__find_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 187227825Stheraven{ 188241903Sdim typedef __bit_iterator<_Cp, _IsConst> _It; 189227825Stheraven typedef typename _It::__storage_type __storage_type; 190227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 191227825Stheraven // do first partial word 192227825Stheraven if (__first.__ctz_ != 0) 193227825Stheraven { 194227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 195227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 196227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 197241903Sdim __storage_type __b = ~*__first.__seg_ & __m; 198227825Stheraven if (__b) 199227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 200227825Stheraven __n -= __dn; 201227825Stheraven ++__first.__seg_; 202227825Stheraven } 203227825Stheraven // do middle whole words 204227825Stheraven for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 205227825Stheraven { 206227825Stheraven __storage_type __b = ~*__first.__seg_; 207227825Stheraven if (__b) 208227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 209227825Stheraven } 210227825Stheraven // do last partial word 211227825Stheraven if (__n > 0) 212227825Stheraven { 213227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 214241903Sdim __storage_type __b = ~*__first.__seg_ & __m; 215227825Stheraven if (__b) 216227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 217227825Stheraven } 218227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(__n)); 219227825Stheraven} 220227825Stheraven 221241903Sdimtemplate <class _Cp, bool _IsConst, class _Tp> 222227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 223241903Sdim__bit_iterator<_Cp, _IsConst> 224241903Sdimfind(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_) 225227825Stheraven{ 226227825Stheraven if (static_cast<bool>(__value_)) 227232950Stheraven return __find_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first)); 228232950Stheraven return __find_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first)); 229227825Stheraven} 230227825Stheraven 231227825Stheraven// count 232227825Stheraven 233241903Sdimtemplate <class _Cp, bool _IsConst> 234241903Sdimtypename __bit_iterator<_Cp, _IsConst>::difference_type 235241903Sdim__count_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 236227825Stheraven{ 237241903Sdim typedef __bit_iterator<_Cp, _IsConst> _It; 238227825Stheraven typedef typename _It::__storage_type __storage_type; 239227825Stheraven typedef typename _It::difference_type difference_type; 240227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 241227825Stheraven difference_type __r = 0; 242227825Stheraven // do first partial word 243227825Stheraven if (__first.__ctz_ != 0) 244227825Stheraven { 245227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 246227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 247227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 248227825Stheraven __r = _VSTD::__pop_count(*__first.__seg_ & __m); 249227825Stheraven __n -= __dn; 250227825Stheraven ++__first.__seg_; 251227825Stheraven } 252227825Stheraven // do middle whole words 253227825Stheraven for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 254227825Stheraven __r += _VSTD::__pop_count(*__first.__seg_); 255227825Stheraven // do last partial word 256227825Stheraven if (__n > 0) 257227825Stheraven { 258227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 259227825Stheraven __r += _VSTD::__pop_count(*__first.__seg_ & __m); 260227825Stheraven } 261227825Stheraven return __r; 262227825Stheraven} 263227825Stheraven 264241903Sdimtemplate <class _Cp, bool _IsConst> 265241903Sdimtypename __bit_iterator<_Cp, _IsConst>::difference_type 266241903Sdim__count_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 267227825Stheraven{ 268241903Sdim typedef __bit_iterator<_Cp, _IsConst> _It; 269227825Stheraven typedef typename _It::__storage_type __storage_type; 270227825Stheraven typedef typename _It::difference_type difference_type; 271227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 272227825Stheraven difference_type __r = 0; 273227825Stheraven // do first partial word 274227825Stheraven if (__first.__ctz_ != 0) 275227825Stheraven { 276227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 277227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 278227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 279241903Sdim __r = _VSTD::__pop_count(~*__first.__seg_ & __m); 280227825Stheraven __n -= __dn; 281227825Stheraven ++__first.__seg_; 282227825Stheraven } 283227825Stheraven // do middle whole words 284227825Stheraven for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 285227825Stheraven __r += _VSTD::__pop_count(~*__first.__seg_); 286227825Stheraven // do last partial word 287227825Stheraven if (__n > 0) 288227825Stheraven { 289227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 290241903Sdim __r += _VSTD::__pop_count(~*__first.__seg_ & __m); 291227825Stheraven } 292227825Stheraven return __r; 293227825Stheraven} 294227825Stheraven 295241903Sdimtemplate <class _Cp, bool _IsConst, class _Tp> 296227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 297241903Sdimtypename __bit_iterator<_Cp, _IsConst>::difference_type 298241903Sdimcount(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_) 299227825Stheraven{ 300227825Stheraven if (static_cast<bool>(__value_)) 301232950Stheraven return __count_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first)); 302232950Stheraven return __count_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first)); 303227825Stheraven} 304227825Stheraven 305227825Stheraven// fill_n 306227825Stheraven 307232950Stheraventemplate <class _Cp> 308227825Stheravenvoid 309232950Stheraven__fill_n_false(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) 310227825Stheraven{ 311232950Stheraven typedef __bit_iterator<_Cp, false> _It; 312227825Stheraven typedef typename _It::__storage_type __storage_type; 313227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 314227825Stheraven // do first partial word 315227825Stheraven if (__first.__ctz_ != 0) 316227825Stheraven { 317227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 318227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 319227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 320227825Stheraven *__first.__seg_ &= ~__m; 321227825Stheraven __n -= __dn; 322227825Stheraven ++__first.__seg_; 323227825Stheraven } 324227825Stheraven // do middle whole words 325227825Stheraven __storage_type __nw = __n / __bits_per_word; 326227825Stheraven _VSTD::memset(__first.__seg_, 0, __nw * sizeof(__storage_type)); 327227825Stheraven __n -= __nw * __bits_per_word; 328227825Stheraven // do last partial word 329227825Stheraven if (__n > 0) 330227825Stheraven { 331227825Stheraven __first.__seg_ += __nw; 332227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 333227825Stheraven *__first.__seg_ &= ~__m; 334227825Stheraven } 335227825Stheraven} 336227825Stheraven 337232950Stheraventemplate <class _Cp> 338227825Stheravenvoid 339232950Stheraven__fill_n_true(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) 340227825Stheraven{ 341232950Stheraven typedef __bit_iterator<_Cp, false> _It; 342227825Stheraven typedef typename _It::__storage_type __storage_type; 343227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 344227825Stheraven // do first partial word 345227825Stheraven if (__first.__ctz_ != 0) 346227825Stheraven { 347227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 348227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 349227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 350227825Stheraven *__first.__seg_ |= __m; 351227825Stheraven __n -= __dn; 352227825Stheraven ++__first.__seg_; 353227825Stheraven } 354227825Stheraven // do middle whole words 355227825Stheraven __storage_type __nw = __n / __bits_per_word; 356227825Stheraven _VSTD::memset(__first.__seg_, -1, __nw * sizeof(__storage_type)); 357227825Stheraven __n -= __nw * __bits_per_word; 358227825Stheraven // do last partial word 359227825Stheraven if (__n > 0) 360227825Stheraven { 361227825Stheraven __first.__seg_ += __nw; 362227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 363227825Stheraven *__first.__seg_ |= __m; 364227825Stheraven } 365227825Stheraven} 366227825Stheraven 367232950Stheraventemplate <class _Cp> 368227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 369227825Stheravenvoid 370232950Stheravenfill_n(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n, bool __value_) 371227825Stheraven{ 372227825Stheraven if (__n > 0) 373227825Stheraven { 374227825Stheraven if (__value_) 375227825Stheraven __fill_n_true(__first, __n); 376227825Stheraven else 377227825Stheraven __fill_n_false(__first, __n); 378227825Stheraven } 379227825Stheraven} 380227825Stheraven 381227825Stheraven// fill 382227825Stheraven 383232950Stheraventemplate <class _Cp> 384227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 385227825Stheravenvoid 386232950Stheravenfill(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __last, bool __value_) 387227825Stheraven{ 388232950Stheraven _VSTD::fill_n(__first, static_cast<typename _Cp::size_type>(__last - __first), __value_); 389227825Stheraven} 390227825Stheraven 391227825Stheraven// copy 392227825Stheraven 393232950Stheraventemplate <class _Cp, bool _IsConst> 394232950Stheraven__bit_iterator<_Cp, false> 395232950Stheraven__copy_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 396232950Stheraven __bit_iterator<_Cp, false> __result) 397227825Stheraven{ 398232950Stheraven typedef __bit_iterator<_Cp, _IsConst> _In; 399227825Stheraven typedef typename _In::difference_type difference_type; 400227825Stheraven typedef typename _In::__storage_type __storage_type; 401227825Stheraven static const unsigned __bits_per_word = _In::__bits_per_word; 402227825Stheraven difference_type __n = __last - __first; 403227825Stheraven if (__n > 0) 404227825Stheraven { 405227825Stheraven // do first word 406227825Stheraven if (__first.__ctz_ != 0) 407227825Stheraven { 408227825Stheraven unsigned __clz = __bits_per_word - __first.__ctz_; 409227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 410227825Stheraven __n -= __dn; 411227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 412227825Stheraven __storage_type __b = *__first.__seg_ & __m; 413227825Stheraven *__result.__seg_ &= ~__m; 414227825Stheraven *__result.__seg_ |= __b; 415227825Stheraven __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 416227825Stheraven __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 417227825Stheraven ++__first.__seg_; 418227825Stheraven // __first.__ctz_ = 0; 419227825Stheraven } 420227825Stheraven // __first.__ctz_ == 0; 421227825Stheraven // do middle words 422227825Stheraven __storage_type __nw = __n / __bits_per_word; 423227825Stheraven _VSTD::memmove(__result.__seg_, __first.__seg_, __nw * sizeof(__storage_type)); 424227825Stheraven __n -= __nw * __bits_per_word; 425227825Stheraven __result.__seg_ += __nw; 426227825Stheraven // do last word 427227825Stheraven if (__n > 0) 428227825Stheraven { 429227825Stheraven __first.__seg_ += __nw; 430227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 431227825Stheraven __storage_type __b = *__first.__seg_ & __m; 432227825Stheraven *__result.__seg_ &= ~__m; 433227825Stheraven *__result.__seg_ |= __b; 434227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 435227825Stheraven } 436227825Stheraven } 437227825Stheraven return __result; 438227825Stheraven} 439227825Stheraven 440232950Stheraventemplate <class _Cp, bool _IsConst> 441232950Stheraven__bit_iterator<_Cp, false> 442232950Stheraven__copy_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 443232950Stheraven __bit_iterator<_Cp, false> __result) 444227825Stheraven{ 445232950Stheraven typedef __bit_iterator<_Cp, _IsConst> _In; 446227825Stheraven typedef typename _In::difference_type difference_type; 447227825Stheraven typedef typename _In::__storage_type __storage_type; 448227825Stheraven static const unsigned __bits_per_word = _In::__bits_per_word; 449227825Stheraven difference_type __n = __last - __first; 450227825Stheraven if (__n > 0) 451227825Stheraven { 452227825Stheraven // do first word 453227825Stheraven if (__first.__ctz_ != 0) 454227825Stheraven { 455227825Stheraven unsigned __clz_f = __bits_per_word - __first.__ctz_; 456227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 457227825Stheraven __n -= __dn; 458227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 459227825Stheraven __storage_type __b = *__first.__seg_ & __m; 460227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 461227825Stheraven __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 462227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 463227825Stheraven *__result.__seg_ &= ~__m; 464227825Stheraven if (__result.__ctz_ > __first.__ctz_) 465227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_); 466227825Stheraven else 467227825Stheraven *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_); 468227825Stheraven __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 469227825Stheraven __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 470227825Stheraven __dn -= __ddn; 471227825Stheraven if (__dn > 0) 472227825Stheraven { 473227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __dn); 474227825Stheraven *__result.__seg_ &= ~__m; 475227825Stheraven *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn); 476227825Stheraven __result.__ctz_ = static_cast<unsigned>(__dn); 477227825Stheraven } 478227825Stheraven ++__first.__seg_; 479227825Stheraven // __first.__ctz_ = 0; 480227825Stheraven } 481227825Stheraven // __first.__ctz_ == 0; 482227825Stheraven // do middle words 483227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 484227825Stheraven __storage_type __m = ~__storage_type(0) << __result.__ctz_; 485227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 486227825Stheraven { 487227825Stheraven __storage_type __b = *__first.__seg_; 488227825Stheraven *__result.__seg_ &= ~__m; 489227825Stheraven *__result.__seg_ |= __b << __result.__ctz_; 490227825Stheraven ++__result.__seg_; 491227825Stheraven *__result.__seg_ &= __m; 492227825Stheraven *__result.__seg_ |= __b >> __clz_r; 493227825Stheraven } 494227825Stheraven // do last word 495227825Stheraven if (__n > 0) 496227825Stheraven { 497227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 498227825Stheraven __storage_type __b = *__first.__seg_ & __m; 499227825Stheraven __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); 500227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 501227825Stheraven *__result.__seg_ &= ~__m; 502227825Stheraven *__result.__seg_ |= __b << __result.__ctz_; 503227825Stheraven __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 504227825Stheraven __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 505227825Stheraven __n -= __dn; 506227825Stheraven if (__n > 0) 507227825Stheraven { 508227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 509227825Stheraven *__result.__seg_ &= ~__m; 510227825Stheraven *__result.__seg_ |= __b >> __dn; 511227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 512227825Stheraven } 513227825Stheraven } 514227825Stheraven } 515227825Stheraven return __result; 516227825Stheraven} 517227825Stheraven 518232950Stheraventemplate <class _Cp, bool _IsConst> 519227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 520232950Stheraven__bit_iterator<_Cp, false> 521232950Stheravencopy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 522227825Stheraven{ 523227825Stheraven if (__first.__ctz_ == __result.__ctz_) 524227825Stheraven return __copy_aligned(__first, __last, __result); 525227825Stheraven return __copy_unaligned(__first, __last, __result); 526227825Stheraven} 527227825Stheraven 528227825Stheraven// copy_backward 529227825Stheraven 530232950Stheraventemplate <class _Cp, bool _IsConst> 531232950Stheraven__bit_iterator<_Cp, false> 532232950Stheraven__copy_backward_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 533232950Stheraven __bit_iterator<_Cp, false> __result) 534227825Stheraven{ 535232950Stheraven typedef __bit_iterator<_Cp, _IsConst> _In; 536227825Stheraven typedef typename _In::difference_type difference_type; 537227825Stheraven typedef typename _In::__storage_type __storage_type; 538227825Stheraven static const unsigned __bits_per_word = _In::__bits_per_word; 539227825Stheraven difference_type __n = __last - __first; 540227825Stheraven if (__n > 0) 541227825Stheraven { 542227825Stheraven // do first word 543227825Stheraven if (__last.__ctz_ != 0) 544227825Stheraven { 545227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); 546227825Stheraven __n -= __dn; 547227825Stheraven unsigned __clz = __bits_per_word - __last.__ctz_; 548227825Stheraven __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz); 549227825Stheraven __storage_type __b = *__last.__seg_ & __m; 550227825Stheraven *__result.__seg_ &= ~__m; 551227825Stheraven *__result.__seg_ |= __b; 552227825Stheraven __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 553227825Stheraven __result.__ctz_) % __bits_per_word); 554227825Stheraven // __last.__ctz_ = 0 555227825Stheraven } 556227825Stheraven // __last.__ctz_ == 0 || __n == 0 557227825Stheraven // __result.__ctz_ == 0 || __n == 0 558227825Stheraven // do middle words 559227825Stheraven __storage_type __nw = __n / __bits_per_word; 560227825Stheraven __result.__seg_ -= __nw; 561227825Stheraven __last.__seg_ -= __nw; 562227825Stheraven _VSTD::memmove(__result.__seg_, __last.__seg_, __nw * sizeof(__storage_type)); 563227825Stheraven __n -= __nw * __bits_per_word; 564227825Stheraven // do last word 565227825Stheraven if (__n > 0) 566227825Stheraven { 567227825Stheraven __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n); 568227825Stheraven __storage_type __b = *--__last.__seg_ & __m; 569227825Stheraven *--__result.__seg_ &= ~__m; 570227825Stheraven *__result.__seg_ |= __b; 571227825Stheraven __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 572227825Stheraven } 573227825Stheraven } 574227825Stheraven return __result; 575227825Stheraven} 576227825Stheraven 577232950Stheraventemplate <class _Cp, bool _IsConst> 578232950Stheraven__bit_iterator<_Cp, false> 579232950Stheraven__copy_backward_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 580232950Stheraven __bit_iterator<_Cp, false> __result) 581227825Stheraven{ 582232950Stheraven typedef __bit_iterator<_Cp, _IsConst> _In; 583227825Stheraven typedef typename _In::difference_type difference_type; 584227825Stheraven typedef typename _In::__storage_type __storage_type; 585227825Stheraven static const unsigned __bits_per_word = _In::__bits_per_word; 586227825Stheraven difference_type __n = __last - __first; 587227825Stheraven if (__n > 0) 588227825Stheraven { 589227825Stheraven // do first word 590227825Stheraven if (__last.__ctz_ != 0) 591227825Stheraven { 592227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); 593227825Stheraven __n -= __dn; 594227825Stheraven unsigned __clz_l = __bits_per_word - __last.__ctz_; 595227825Stheraven __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l); 596227825Stheraven __storage_type __b = *__last.__seg_ & __m; 597227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 598227825Stheraven __storage_type __ddn = _VSTD::min(__dn, static_cast<difference_type>(__result.__ctz_)); 599227825Stheraven if (__ddn > 0) 600227825Stheraven { 601227825Stheraven __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r); 602227825Stheraven *__result.__seg_ &= ~__m; 603227825Stheraven if (__result.__ctz_ > __last.__ctz_) 604227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 605227825Stheraven else 606227825Stheraven *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_); 607227825Stheraven __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) + 608227825Stheraven __result.__ctz_) % __bits_per_word); 609227825Stheraven __dn -= __ddn; 610227825Stheraven } 611227825Stheraven if (__dn > 0) 612227825Stheraven { 613227825Stheraven // __result.__ctz_ == 0 614227825Stheraven --__result.__seg_; 615227825Stheraven __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1)); 616227825Stheraven __m = ~__storage_type(0) << __result.__ctz_; 617227825Stheraven *__result.__seg_ &= ~__m; 618227825Stheraven __last.__ctz_ -= __dn + __ddn; 619227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 620227825Stheraven } 621227825Stheraven // __last.__ctz_ = 0 622227825Stheraven } 623227825Stheraven // __last.__ctz_ == 0 || __n == 0 624227825Stheraven // __result.__ctz_ != 0 || __n == 0 625227825Stheraven // do middle words 626227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 627227825Stheraven __storage_type __m = ~__storage_type(0) >> __clz_r; 628227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word) 629227825Stheraven { 630227825Stheraven __storage_type __b = *--__last.__seg_; 631227825Stheraven *__result.__seg_ &= ~__m; 632227825Stheraven *__result.__seg_ |= __b >> __clz_r; 633227825Stheraven *--__result.__seg_ &= __m; 634227825Stheraven *__result.__seg_ |= __b << __result.__ctz_; 635227825Stheraven } 636227825Stheraven // do last word 637227825Stheraven if (__n > 0) 638227825Stheraven { 639227825Stheraven __m = ~__storage_type(0) << (__bits_per_word - __n); 640227825Stheraven __storage_type __b = *--__last.__seg_ & __m; 641232950Stheraven __clz_r = __bits_per_word - __result.__ctz_; 642227825Stheraven __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__result.__ctz_)); 643227825Stheraven __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r); 644227825Stheraven *__result.__seg_ &= ~__m; 645227825Stheraven *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_); 646227825Stheraven __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 647227825Stheraven __result.__ctz_) % __bits_per_word); 648227825Stheraven __n -= __dn; 649227825Stheraven if (__n > 0) 650227825Stheraven { 651227825Stheraven // __result.__ctz_ == 0 652227825Stheraven --__result.__seg_; 653227825Stheraven __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 654227825Stheraven __m = ~__storage_type(0) << __result.__ctz_; 655227825Stheraven *__result.__seg_ &= ~__m; 656227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn)); 657227825Stheraven } 658227825Stheraven } 659227825Stheraven } 660227825Stheraven return __result; 661227825Stheraven} 662227825Stheraven 663232950Stheraventemplate <class _Cp, bool _IsConst> 664227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 665232950Stheraven__bit_iterator<_Cp, false> 666232950Stheravencopy_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 667227825Stheraven{ 668227825Stheraven if (__last.__ctz_ == __result.__ctz_) 669227825Stheraven return __copy_backward_aligned(__first, __last, __result); 670227825Stheraven return __copy_backward_unaligned(__first, __last, __result); 671227825Stheraven} 672227825Stheraven 673227825Stheraven// move 674227825Stheraven 675232950Stheraventemplate <class _Cp, bool _IsConst> 676227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 677232950Stheraven__bit_iterator<_Cp, false> 678232950Stheravenmove(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 679227825Stheraven{ 680227825Stheraven return _VSTD::copy(__first, __last, __result); 681227825Stheraven} 682227825Stheraven 683227825Stheraven// move_backward 684227825Stheraven 685232950Stheraventemplate <class _Cp, bool _IsConst> 686227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 687232950Stheraven__bit_iterator<_Cp, false> 688232950Stheravenmove_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 689227825Stheraven{ 690227825Stheraven return _VSTD::copy(__first, __last, __result); 691227825Stheraven} 692227825Stheraven 693227825Stheraven// swap_ranges 694227825Stheraven 695227825Stheraventemplate <class __C1, class __C2> 696227825Stheraven__bit_iterator<__C2, false> 697227825Stheraven__swap_ranges_aligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, 698227825Stheraven __bit_iterator<__C2, false> __result) 699227825Stheraven{ 700227825Stheraven typedef __bit_iterator<__C1, false> _I1; 701227825Stheraven typedef typename _I1::difference_type difference_type; 702227825Stheraven typedef typename _I1::__storage_type __storage_type; 703227825Stheraven static const unsigned __bits_per_word = _I1::__bits_per_word; 704227825Stheraven difference_type __n = __last - __first; 705227825Stheraven if (__n > 0) 706227825Stheraven { 707227825Stheraven // do first word 708227825Stheraven if (__first.__ctz_ != 0) 709227825Stheraven { 710227825Stheraven unsigned __clz = __bits_per_word - __first.__ctz_; 711227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 712227825Stheraven __n -= __dn; 713227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 714227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 715227825Stheraven *__first.__seg_ &= ~__m; 716227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 717227825Stheraven *__result.__seg_ &= ~__m; 718227825Stheraven *__result.__seg_ |= __b1; 719227825Stheraven *__first.__seg_ |= __b2; 720227825Stheraven __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 721227825Stheraven __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 722227825Stheraven ++__first.__seg_; 723227825Stheraven // __first.__ctz_ = 0; 724227825Stheraven } 725227825Stheraven // __first.__ctz_ == 0; 726227825Stheraven // do middle words 727227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_) 728227825Stheraven swap(*__first.__seg_, *__result.__seg_); 729227825Stheraven // do last word 730227825Stheraven if (__n > 0) 731227825Stheraven { 732227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 733227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 734227825Stheraven *__first.__seg_ &= ~__m; 735227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 736227825Stheraven *__result.__seg_ &= ~__m; 737227825Stheraven *__result.__seg_ |= __b1; 738227825Stheraven *__first.__seg_ |= __b2; 739227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 740227825Stheraven } 741227825Stheraven } 742227825Stheraven return __result; 743227825Stheraven} 744227825Stheraven 745227825Stheraventemplate <class __C1, class __C2> 746227825Stheraven__bit_iterator<__C2, false> 747227825Stheraven__swap_ranges_unaligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, 748227825Stheraven __bit_iterator<__C2, false> __result) 749227825Stheraven{ 750227825Stheraven typedef __bit_iterator<__C1, false> _I1; 751227825Stheraven typedef typename _I1::difference_type difference_type; 752227825Stheraven typedef typename _I1::__storage_type __storage_type; 753227825Stheraven static const unsigned __bits_per_word = _I1::__bits_per_word; 754227825Stheraven difference_type __n = __last - __first; 755227825Stheraven if (__n > 0) 756227825Stheraven { 757227825Stheraven // do first word 758227825Stheraven if (__first.__ctz_ != 0) 759227825Stheraven { 760227825Stheraven unsigned __clz_f = __bits_per_word - __first.__ctz_; 761227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 762227825Stheraven __n -= __dn; 763227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 764227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 765227825Stheraven *__first.__seg_ &= ~__m; 766227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 767227825Stheraven __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 768227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 769227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 770227825Stheraven *__result.__seg_ &= ~__m; 771227825Stheraven if (__result.__ctz_ > __first.__ctz_) 772227825Stheraven { 773227825Stheraven unsigned __s = __result.__ctz_ - __first.__ctz_; 774227825Stheraven *__result.__seg_ |= __b1 << __s; 775227825Stheraven *__first.__seg_ |= __b2 >> __s; 776227825Stheraven } 777227825Stheraven else 778227825Stheraven { 779227825Stheraven unsigned __s = __first.__ctz_ - __result.__ctz_; 780227825Stheraven *__result.__seg_ |= __b1 >> __s; 781227825Stheraven *__first.__seg_ |= __b2 << __s; 782227825Stheraven } 783227825Stheraven __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 784227825Stheraven __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 785227825Stheraven __dn -= __ddn; 786227825Stheraven if (__dn > 0) 787227825Stheraven { 788227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __dn); 789227825Stheraven __b2 = *__result.__seg_ & __m; 790227825Stheraven *__result.__seg_ &= ~__m; 791227825Stheraven unsigned __s = __first.__ctz_ + __ddn; 792227825Stheraven *__result.__seg_ |= __b1 >> __s; 793227825Stheraven *__first.__seg_ |= __b2 << __s; 794227825Stheraven __result.__ctz_ = static_cast<unsigned>(__dn); 795227825Stheraven } 796227825Stheraven ++__first.__seg_; 797227825Stheraven // __first.__ctz_ = 0; 798227825Stheraven } 799227825Stheraven // __first.__ctz_ == 0; 800227825Stheraven // do middle words 801227825Stheraven __storage_type __m = ~__storage_type(0) << __result.__ctz_; 802227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 803227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 804227825Stheraven { 805227825Stheraven __storage_type __b1 = *__first.__seg_; 806227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 807227825Stheraven *__result.__seg_ &= ~__m; 808227825Stheraven *__result.__seg_ |= __b1 << __result.__ctz_; 809227825Stheraven *__first.__seg_ = __b2 >> __result.__ctz_; 810227825Stheraven ++__result.__seg_; 811227825Stheraven __b2 = *__result.__seg_ & ~__m; 812227825Stheraven *__result.__seg_ &= __m; 813227825Stheraven *__result.__seg_ |= __b1 >> __clz_r; 814227825Stheraven *__first.__seg_ |= __b2 << __clz_r; 815227825Stheraven } 816227825Stheraven // do last word 817227825Stheraven if (__n > 0) 818227825Stheraven { 819227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 820227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 821227825Stheraven *__first.__seg_ &= ~__m; 822227825Stheraven __storage_type __dn = _VSTD::min<__storage_type>(__n, __clz_r); 823227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 824227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 825227825Stheraven *__result.__seg_ &= ~__m; 826227825Stheraven *__result.__seg_ |= __b1 << __result.__ctz_; 827227825Stheraven *__first.__seg_ |= __b2 >> __result.__ctz_; 828227825Stheraven __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 829227825Stheraven __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 830227825Stheraven __n -= __dn; 831227825Stheraven if (__n > 0) 832227825Stheraven { 833227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 834227825Stheraven __b2 = *__result.__seg_ & __m; 835227825Stheraven *__result.__seg_ &= ~__m; 836227825Stheraven *__result.__seg_ |= __b1 >> __dn; 837227825Stheraven *__first.__seg_ |= __b2 << __dn; 838227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 839227825Stheraven } 840227825Stheraven } 841227825Stheraven } 842227825Stheraven return __result; 843227825Stheraven} 844227825Stheraven 845227825Stheraventemplate <class __C1, class __C2> 846227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 847227825Stheraven__bit_iterator<__C2, false> 848227825Stheravenswap_ranges(__bit_iterator<__C1, false> __first1, __bit_iterator<__C1, false> __last1, 849227825Stheraven __bit_iterator<__C2, false> __first2) 850227825Stheraven{ 851227825Stheraven if (__first1.__ctz_ == __first2.__ctz_) 852227825Stheraven return __swap_ranges_aligned(__first1, __last1, __first2); 853227825Stheraven return __swap_ranges_unaligned(__first1, __last1, __first2); 854227825Stheraven} 855227825Stheraven 856227825Stheraven// rotate 857227825Stheraven 858232950Stheraventemplate <class _Cp> 859227825Stheravenstruct __bit_array 860227825Stheraven{ 861232950Stheraven typedef typename _Cp::difference_type difference_type; 862232950Stheraven typedef typename _Cp::__storage_type __storage_type; 863232950Stheraven typedef typename _Cp::iterator iterator; 864232950Stheraven static const unsigned __bits_per_word = _Cp::__bits_per_word; 865232950Stheraven static const unsigned _Np = 4; 866227825Stheraven 867227825Stheraven difference_type __size_; 868232950Stheraven __storage_type __word_[_Np]; 869227825Stheraven 870227825Stheraven _LIBCPP_INLINE_VISIBILITY static difference_type capacity() 871232950Stheraven {return static_cast<difference_type>(_Np * __bits_per_word);} 872227825Stheraven _LIBCPP_INLINE_VISIBILITY explicit __bit_array(difference_type __s) : __size_(__s) {} 873227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator begin() {return iterator(__word_, 0);} 874227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator end() {return iterator(__word_ + __size_ / __bits_per_word, 875227825Stheraven static_cast<unsigned>(__size_ % __bits_per_word));} 876227825Stheraven}; 877227825Stheraven 878232950Stheraventemplate <class _Cp> 879232950Stheraven__bit_iterator<_Cp, false> 880232950Stheravenrotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last) 881227825Stheraven{ 882232950Stheraven typedef __bit_iterator<_Cp, false> _I1; 883227825Stheraven typedef typename _I1::difference_type difference_type; 884227825Stheraven typedef typename _I1::__storage_type __storage_type; 885227825Stheraven difference_type __d1 = __middle - __first; 886227825Stheraven difference_type __d2 = __last - __middle; 887227825Stheraven _I1 __r = __first + __d2; 888227825Stheraven while (__d1 != 0 && __d2 != 0) 889227825Stheraven { 890227825Stheraven if (__d1 <= __d2) 891227825Stheraven { 892232950Stheraven if (__d1 <= __bit_array<_Cp>::capacity()) 893227825Stheraven { 894232950Stheraven __bit_array<_Cp> __b(__d1); 895227825Stheraven _VSTD::copy(__first, __middle, __b.begin()); 896227825Stheraven _VSTD::copy(__b.begin(), __b.end(), _VSTD::copy(__middle, __last, __first)); 897227825Stheraven break; 898227825Stheraven } 899227825Stheraven else 900227825Stheraven { 901232950Stheraven __bit_iterator<_Cp, false> __mp = _VSTD::swap_ranges(__first, __middle, __middle); 902227825Stheraven __first = __middle; 903227825Stheraven __middle = __mp; 904227825Stheraven __d2 -= __d1; 905227825Stheraven } 906227825Stheraven } 907227825Stheraven else 908227825Stheraven { 909232950Stheraven if (__d2 <= __bit_array<_Cp>::capacity()) 910227825Stheraven { 911232950Stheraven __bit_array<_Cp> __b(__d2); 912227825Stheraven _VSTD::copy(__middle, __last, __b.begin()); 913227825Stheraven _VSTD::copy_backward(__b.begin(), __b.end(), _VSTD::copy_backward(__first, __middle, __last)); 914227825Stheraven break; 915227825Stheraven } 916227825Stheraven else 917227825Stheraven { 918232950Stheraven __bit_iterator<_Cp, false> __mp = __first + __d2; 919227825Stheraven _VSTD::swap_ranges(__first, __mp, __middle); 920227825Stheraven __first = __mp; 921227825Stheraven __d1 -= __d2; 922227825Stheraven } 923227825Stheraven } 924227825Stheraven } 925227825Stheraven return __r; 926227825Stheraven} 927227825Stheraven 928227825Stheraven// equal 929227825Stheraven 930241903Sdimtemplate <class _Cp, bool _IC1, bool _IC2> 931227825Stheravenbool 932241903Sdim__equal_unaligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, 933241903Sdim __bit_iterator<_Cp, _IC2> __first2) 934227825Stheraven{ 935241903Sdim typedef __bit_iterator<_Cp, _IC1> _It; 936227825Stheraven typedef typename _It::difference_type difference_type; 937227825Stheraven typedef typename _It::__storage_type __storage_type; 938227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 939227825Stheraven difference_type __n = __last1 - __first1; 940227825Stheraven if (__n > 0) 941227825Stheraven { 942227825Stheraven // do first word 943227825Stheraven if (__first1.__ctz_ != 0) 944227825Stheraven { 945227825Stheraven unsigned __clz_f = __bits_per_word - __first1.__ctz_; 946227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 947227825Stheraven __n -= __dn; 948227825Stheraven __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 949227825Stheraven __storage_type __b = *__first1.__seg_ & __m; 950227825Stheraven unsigned __clz_r = __bits_per_word - __first2.__ctz_; 951227825Stheraven __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 952227825Stheraven __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 953227825Stheraven if (__first2.__ctz_ > __first1.__ctz_) 954236387Sdim { 955227825Stheraven if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_))) 956227825Stheraven return false; 957236387Sdim } 958227825Stheraven else 959236387Sdim { 960227825Stheraven if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_))) 961227825Stheraven return false; 962236387Sdim } 963227825Stheraven __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word; 964227825Stheraven __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word); 965227825Stheraven __dn -= __ddn; 966227825Stheraven if (__dn > 0) 967227825Stheraven { 968227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __dn); 969227825Stheraven if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn))) 970227825Stheraven return false; 971227825Stheraven __first2.__ctz_ = static_cast<unsigned>(__dn); 972227825Stheraven } 973227825Stheraven ++__first1.__seg_; 974227825Stheraven // __first1.__ctz_ = 0; 975227825Stheraven } 976227825Stheraven // __first1.__ctz_ == 0; 977227825Stheraven // do middle words 978227825Stheraven unsigned __clz_r = __bits_per_word - __first2.__ctz_; 979227825Stheraven __storage_type __m = ~__storage_type(0) << __first2.__ctz_; 980227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_) 981227825Stheraven { 982227825Stheraven __storage_type __b = *__first1.__seg_; 983227825Stheraven if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 984227825Stheraven return false; 985227825Stheraven ++__first2.__seg_; 986227825Stheraven if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r)) 987227825Stheraven return false; 988227825Stheraven } 989227825Stheraven // do last word 990227825Stheraven if (__n > 0) 991227825Stheraven { 992227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 993227825Stheraven __storage_type __b = *__first1.__seg_ & __m; 994227825Stheraven __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); 995227825Stheraven __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 996227825Stheraven if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 997227825Stheraven return false; 998227825Stheraven __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word; 999227825Stheraven __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word); 1000227825Stheraven __n -= __dn; 1001227825Stheraven if (__n > 0) 1002227825Stheraven { 1003227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 1004227825Stheraven if ((*__first2.__seg_ & __m) != (__b >> __dn)) 1005227825Stheraven return false; 1006227825Stheraven } 1007227825Stheraven } 1008227825Stheraven } 1009227825Stheraven return true; 1010227825Stheraven} 1011227825Stheraven 1012241903Sdimtemplate <class _Cp, bool _IC1, bool _IC2> 1013227825Stheravenbool 1014241903Sdim__equal_aligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, 1015241903Sdim __bit_iterator<_Cp, _IC2> __first2) 1016227825Stheraven{ 1017241903Sdim typedef __bit_iterator<_Cp, _IC1> _It; 1018227825Stheraven typedef typename _It::difference_type difference_type; 1019227825Stheraven typedef typename _It::__storage_type __storage_type; 1020227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 1021227825Stheraven difference_type __n = __last1 - __first1; 1022227825Stheraven if (__n > 0) 1023227825Stheraven { 1024227825Stheraven // do first word 1025227825Stheraven if (__first1.__ctz_ != 0) 1026227825Stheraven { 1027227825Stheraven unsigned __clz = __bits_per_word - __first1.__ctz_; 1028227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 1029227825Stheraven __n -= __dn; 1030227825Stheraven __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 1031227825Stheraven if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 1032227825Stheraven return false; 1033227825Stheraven ++__first2.__seg_; 1034227825Stheraven ++__first1.__seg_; 1035227825Stheraven // __first1.__ctz_ = 0; 1036227825Stheraven // __first2.__ctz_ = 0; 1037227825Stheraven } 1038227825Stheraven // __first1.__ctz_ == 0; 1039227825Stheraven // __first2.__ctz_ == 0; 1040227825Stheraven // do middle words 1041227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_) 1042227825Stheraven if (*__first2.__seg_ != *__first1.__seg_) 1043227825Stheraven return false; 1044227825Stheraven // do last word 1045227825Stheraven if (__n > 0) 1046227825Stheraven { 1047227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 1048227825Stheraven if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 1049227825Stheraven return false; 1050227825Stheraven } 1051227825Stheraven } 1052227825Stheraven return true; 1053227825Stheraven} 1054227825Stheraven 1055232950Stheraventemplate <class _Cp, bool _IC1, bool _IC2> 1056227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1057227825Stheravenbool 1058232950Stheravenequal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) 1059227825Stheraven{ 1060227825Stheraven if (__first1.__ctz_ == __first2.__ctz_) 1061227825Stheraven return __equal_aligned(__first1, __last1, __first2); 1062227825Stheraven return __equal_unaligned(__first1, __last1, __first2); 1063227825Stheraven} 1064227825Stheraven 1065241903Sdimtemplate <class _Cp, bool _IsConst, 1066241903Sdim typename _Cp::__storage_type> 1067227825Stheravenclass __bit_iterator 1068227825Stheraven{ 1069227825Stheravenpublic: 1070232950Stheraven typedef typename _Cp::difference_type difference_type; 1071227825Stheraven typedef bool value_type; 1072227825Stheraven typedef __bit_iterator pointer; 1073232950Stheraven typedef typename conditional<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >::type reference; 1074227825Stheraven typedef random_access_iterator_tag iterator_category; 1075227825Stheraven 1076227825Stheravenprivate: 1077232950Stheraven typedef typename _Cp::__storage_type __storage_type; 1078232950Stheraven typedef typename conditional<_IsConst, typename _Cp::__const_storage_pointer, 1079232950Stheraven typename _Cp::__storage_pointer>::type __storage_pointer; 1080232950Stheraven static const unsigned __bits_per_word = _Cp::__bits_per_word; 1081227825Stheraven 1082227825Stheraven __storage_pointer __seg_; 1083227825Stheraven unsigned __ctz_; 1084227825Stheraven 1085227825Stheravenpublic: 1086227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator() _NOEXCEPT {} 1087227825Stheraven 1088227825Stheraven _LIBCPP_INLINE_VISIBILITY 1089232950Stheraven __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT 1090227825Stheraven : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {} 1091227825Stheraven 1092227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT 1093227825Stheraven {return reference(__seg_, __storage_type(1) << __ctz_);} 1094227825Stheraven 1095227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator++() 1096227825Stheraven { 1097227825Stheraven if (__ctz_ != __bits_per_word-1) 1098227825Stheraven ++__ctz_; 1099227825Stheraven else 1100227825Stheraven { 1101227825Stheraven __ctz_ = 0; 1102227825Stheraven ++__seg_; 1103227825Stheraven } 1104227825Stheraven return *this; 1105227825Stheraven } 1106227825Stheraven 1107227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator operator++(int) 1108227825Stheraven { 1109227825Stheraven __bit_iterator __tmp = *this; 1110227825Stheraven ++(*this); 1111227825Stheraven return __tmp; 1112227825Stheraven } 1113227825Stheraven 1114227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator--() 1115227825Stheraven { 1116227825Stheraven if (__ctz_ != 0) 1117227825Stheraven --__ctz_; 1118227825Stheraven else 1119227825Stheraven { 1120227825Stheraven __ctz_ = __bits_per_word - 1; 1121227825Stheraven --__seg_; 1122227825Stheraven } 1123227825Stheraven return *this; 1124227825Stheraven } 1125227825Stheraven 1126227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator operator--(int) 1127227825Stheraven { 1128227825Stheraven __bit_iterator __tmp = *this; 1129227825Stheraven --(*this); 1130227825Stheraven return __tmp; 1131227825Stheraven } 1132227825Stheraven 1133227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator+=(difference_type __n) 1134227825Stheraven { 1135227825Stheraven if (__n >= 0) 1136227825Stheraven __seg_ += (__n + __ctz_) / __bits_per_word; 1137227825Stheraven else 1138227825Stheraven __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1) 1139227825Stheraven / static_cast<difference_type>(__bits_per_word); 1140227825Stheraven __n &= (__bits_per_word - 1); 1141227825Stheraven __ctz_ = static_cast<unsigned>((__n + __ctz_) % __bits_per_word); 1142227825Stheraven return *this; 1143227825Stheraven } 1144227825Stheraven 1145227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator-=(difference_type __n) 1146227825Stheraven { 1147227825Stheraven return *this += -__n; 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 __bit_iterator operator-(difference_type __n) const 1158227825Stheraven { 1159227825Stheraven __bit_iterator __t(*this); 1160227825Stheraven __t -= __n; 1161227825Stheraven return __t; 1162227825Stheraven } 1163227825Stheraven 1164227825Stheraven _LIBCPP_INLINE_VISIBILITY 1165227825Stheraven friend __bit_iterator operator+(difference_type __n, const __bit_iterator& __it) {return __it + __n;} 1166227825Stheraven 1167227825Stheraven _LIBCPP_INLINE_VISIBILITY 1168227825Stheraven friend difference_type operator-(const __bit_iterator& __x, const __bit_iterator& __y) 1169227825Stheraven {return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;} 1170227825Stheraven 1171227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const {return *(*this + __n);} 1172227825Stheraven 1173227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator==(const __bit_iterator& __x, const __bit_iterator& __y) 1174227825Stheraven {return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;} 1175227825Stheraven 1176227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator!=(const __bit_iterator& __x, const __bit_iterator& __y) 1177227825Stheraven {return !(__x == __y);} 1178227825Stheraven 1179227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator<(const __bit_iterator& __x, const __bit_iterator& __y) 1180227825Stheraven {return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);} 1181227825Stheraven 1182227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator>(const __bit_iterator& __x, const __bit_iterator& __y) 1183227825Stheraven {return __y < __x;} 1184227825Stheraven 1185227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y) 1186227825Stheraven {return !(__y < __x);} 1187227825Stheraven 1188227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y) 1189227825Stheraven {return !(__x < __y);} 1190227825Stheraven 1191227825Stheravenprivate: 1192227825Stheraven _LIBCPP_INLINE_VISIBILITY 1193227825Stheraven __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT 1194227825Stheraven : __seg_(__s), __ctz_(__ctz) {} 1195227825Stheraven 1196227825Stheraven#if defined(__clang__) 1197232950Stheraven friend typename _Cp::__self; 1198227825Stheraven#else 1199232950Stheraven friend class _Cp::__self; 1200227825Stheraven#endif 1201232950Stheraven friend class __bit_reference<_Cp>; 1202232950Stheraven friend class __bit_const_reference<_Cp>; 1203232950Stheraven friend class __bit_iterator<_Cp, true>; 1204232950Stheraven template <class _Dp> friend struct __bit_array; 1205232950Stheraven template <class _Dp> friend void __fill_n_false(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); 1206232950Stheraven template <class _Dp> friend void __fill_n_true(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); 1207232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_aligned(__bit_iterator<_Dp, _IC> __first, 1208232950Stheraven __bit_iterator<_Dp, _IC> __last, 1209232950Stheraven __bit_iterator<_Dp, false> __result); 1210232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_unaligned(__bit_iterator<_Dp, _IC> __first, 1211232950Stheraven __bit_iterator<_Dp, _IC> __last, 1212232950Stheraven __bit_iterator<_Dp, false> __result); 1213232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy(__bit_iterator<_Dp, _IC> __first, 1214232950Stheraven __bit_iterator<_Dp, _IC> __last, 1215232950Stheraven __bit_iterator<_Dp, false> __result); 1216232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_aligned(__bit_iterator<_Dp, _IC> __first, 1217232950Stheraven __bit_iterator<_Dp, _IC> __last, 1218232950Stheraven __bit_iterator<_Dp, false> __result); 1219232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_unaligned(__bit_iterator<_Dp, _IC> __first, 1220232950Stheraven __bit_iterator<_Dp, _IC> __last, 1221232950Stheraven __bit_iterator<_Dp, false> __result); 1222232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy_backward(__bit_iterator<_Dp, _IC> __first, 1223232950Stheraven __bit_iterator<_Dp, _IC> __last, 1224232950Stheraven __bit_iterator<_Dp, false> __result); 1225227825Stheraven template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_aligned(__bit_iterator<__C1, false>, 1226227825Stheraven __bit_iterator<__C1, false>, 1227227825Stheraven __bit_iterator<__C2, false>); 1228227825Stheraven template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_unaligned(__bit_iterator<__C1, false>, 1229227825Stheraven __bit_iterator<__C1, false>, 1230227825Stheraven __bit_iterator<__C2, false>); 1231227825Stheraven template <class __C1, class __C2>friend __bit_iterator<__C2, false> swap_ranges(__bit_iterator<__C1, false>, 1232227825Stheraven __bit_iterator<__C1, false>, 1233227825Stheraven __bit_iterator<__C2, false>); 1234232950Stheraven template <class _Dp> friend __bit_iterator<_Dp, false> rotate(__bit_iterator<_Dp, false>, 1235232950Stheraven __bit_iterator<_Dp, false>, 1236232950Stheraven __bit_iterator<_Dp, false>); 1237241903Sdim template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_aligned(__bit_iterator<_Dp, _IC1>, 1238241903Sdim __bit_iterator<_Dp, _IC1>, 1239241903Sdim __bit_iterator<_Dp, _IC2>); 1240241903Sdim template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_unaligned(__bit_iterator<_Dp, _IC1>, 1241241903Sdim __bit_iterator<_Dp, _IC1>, 1242241903Sdim __bit_iterator<_Dp, _IC2>); 1243232950Stheraven template <class _Dp, bool _IC1, bool _IC2> friend bool equal(__bit_iterator<_Dp, _IC1>, 1244232950Stheraven __bit_iterator<_Dp, _IC1>, 1245232950Stheraven __bit_iterator<_Dp, _IC2>); 1246241903Sdim template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_true(__bit_iterator<_Dp, _IC>, 1247232950Stheraven typename _Dp::size_type); 1248241903Sdim template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_false(__bit_iterator<_Dp, _IC>, 1249232950Stheraven typename _Dp::size_type); 1250241903Sdim template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type 1251241903Sdim __count_bool_true(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 1252241903Sdim template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type 1253241903Sdim __count_bool_false(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 1254227825Stheraven}; 1255227825Stheraven 1256227825Stheraven_LIBCPP_END_NAMESPACE_STD 1257227825Stheraven 1258227825Stheraven#endif // _LIBCPP___BIT_REFERENCE 1259