__bit_reference revision 236387
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 25232950Stheraventemplate <class _Cp, bool _IsConst> 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 134227825Stheraven _LIBCPP_INLINE_VISIBILITY 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 141227825Stheraven __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT 142227825Stheraven : __seg_(__s), __mask_(__m) {} 143227825Stheraven 144227825Stheraven __bit_const_reference& operator=(const __bit_const_reference& __x); 145227825Stheraven}; 146227825Stheraven 147227825Stheraven// find 148227825Stheraven 149232950Stheraventemplate <class _Cp> 150232950Stheraven__bit_iterator<_Cp, false> 151232950Stheraven__find_bool_true(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) 152227825Stheraven{ 153232950Stheraven typedef __bit_iterator<_Cp, false> _It; 154227825Stheraven typedef typename _It::__storage_type __storage_type; 155227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 156227825Stheraven // do first partial word 157227825Stheraven if (__first.__ctz_ != 0) 158227825Stheraven { 159227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 160227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 161227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 162227825Stheraven __storage_type __b = *__first.__seg_ & __m; 163227825Stheraven if (__b) 164227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 165227825Stheraven __n -= __dn; 166227825Stheraven ++__first.__seg_; 167227825Stheraven } 168227825Stheraven // do middle whole words 169227825Stheraven for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 170227825Stheraven if (*__first.__seg_) 171227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(*__first.__seg_))); 172227825Stheraven // do last partial word 173227825Stheraven if (__n > 0) 174227825Stheraven { 175227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 176227825Stheraven __storage_type __b = *__first.__seg_ & __m; 177227825Stheraven if (__b) 178227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 179227825Stheraven } 180227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(__n)); 181227825Stheraven} 182227825Stheraven 183232950Stheraventemplate <class _Cp> 184232950Stheraven__bit_iterator<_Cp, false> 185232950Stheraven__find_bool_false(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) 186227825Stheraven{ 187232950Stheraven typedef __bit_iterator<_Cp, false> _It; 188227825Stheraven typedef typename _It::__storage_type __storage_type; 189227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 190227825Stheraven // do first partial word 191227825Stheraven if (__first.__ctz_ != 0) 192227825Stheraven { 193227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 194227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 195227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 196227825Stheraven __storage_type __b = ~(*__first.__seg_ & __m); 197227825Stheraven if (__b) 198227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 199227825Stheraven __n -= __dn; 200227825Stheraven ++__first.__seg_; 201227825Stheraven } 202227825Stheraven // do middle whole words 203227825Stheraven for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 204227825Stheraven { 205227825Stheraven __storage_type __b = ~*__first.__seg_; 206227825Stheraven if (__b) 207227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 208227825Stheraven } 209227825Stheraven // do last partial word 210227825Stheraven if (__n > 0) 211227825Stheraven { 212227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 213227825Stheraven __storage_type __b = ~(*__first.__seg_ & __m); 214227825Stheraven if (__b) 215227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 216227825Stheraven } 217227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(__n)); 218227825Stheraven} 219227825Stheraven 220232950Stheraventemplate <class _Cp, class _Tp> 221227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 222232950Stheraven__bit_iterator<_Cp, false> 223232950Stheravenfind(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __last, const _Tp& __value_) 224227825Stheraven{ 225227825Stheraven if (static_cast<bool>(__value_)) 226232950Stheraven return __find_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first)); 227232950Stheraven return __find_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first)); 228227825Stheraven} 229227825Stheraven 230227825Stheraven// count 231227825Stheraven 232232950Stheraventemplate <class _Cp> 233232950Stheraventypename __bit_iterator<_Cp, false>::difference_type 234232950Stheraven__count_bool_true(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) 235227825Stheraven{ 236232950Stheraven typedef __bit_iterator<_Cp, false> _It; 237227825Stheraven typedef typename _It::__storage_type __storage_type; 238227825Stheraven typedef typename _It::difference_type difference_type; 239227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 240227825Stheraven difference_type __r = 0; 241227825Stheraven // do first partial word 242227825Stheraven if (__first.__ctz_ != 0) 243227825Stheraven { 244227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 245227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 246227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 247227825Stheraven __r = _VSTD::__pop_count(*__first.__seg_ & __m); 248227825Stheraven __n -= __dn; 249227825Stheraven ++__first.__seg_; 250227825Stheraven } 251227825Stheraven // do middle whole words 252227825Stheraven for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 253227825Stheraven __r += _VSTD::__pop_count(*__first.__seg_); 254227825Stheraven // do last partial word 255227825Stheraven if (__n > 0) 256227825Stheraven { 257227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 258227825Stheraven __r += _VSTD::__pop_count(*__first.__seg_ & __m); 259227825Stheraven } 260227825Stheraven return __r; 261227825Stheraven} 262227825Stheraven 263232950Stheraventemplate <class _Cp> 264232950Stheraventypename __bit_iterator<_Cp, false>::difference_type 265232950Stheraven__count_bool_false(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) 266227825Stheraven{ 267232950Stheraven typedef __bit_iterator<_Cp, false> _It; 268227825Stheraven typedef typename _It::__storage_type __storage_type; 269227825Stheraven typedef typename _It::difference_type difference_type; 270227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 271227825Stheraven difference_type __r = 0; 272227825Stheraven // do first partial word 273227825Stheraven if (__first.__ctz_ != 0) 274227825Stheraven { 275227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 276227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 277227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 278227825Stheraven __r = _VSTD::__pop_count(~(*__first.__seg_ & __m)); 279227825Stheraven __n -= __dn; 280227825Stheraven ++__first.__seg_; 281227825Stheraven } 282227825Stheraven // do middle whole words 283227825Stheraven for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 284227825Stheraven __r += _VSTD::__pop_count(~*__first.__seg_); 285227825Stheraven // do last partial word 286227825Stheraven if (__n > 0) 287227825Stheraven { 288227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 289227825Stheraven __r += _VSTD::__pop_count(~(*__first.__seg_ & __m)); 290227825Stheraven } 291227825Stheraven return __r; 292227825Stheraven} 293227825Stheraven 294232950Stheraventemplate <class _Cp, class _Tp> 295227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 296232950Stheraventypename __bit_iterator<_Cp, false>::difference_type 297232950Stheravencount(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __last, const _Tp& __value_) 298227825Stheraven{ 299227825Stheraven if (static_cast<bool>(__value_)) 300232950Stheraven return __count_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first)); 301232950Stheraven return __count_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first)); 302227825Stheraven} 303227825Stheraven 304227825Stheraven// fill_n 305227825Stheraven 306232950Stheraventemplate <class _Cp> 307227825Stheravenvoid 308232950Stheraven__fill_n_false(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) 309227825Stheraven{ 310232950Stheraven typedef __bit_iterator<_Cp, false> _It; 311227825Stheraven typedef typename _It::__storage_type __storage_type; 312227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 313227825Stheraven // do first partial word 314227825Stheraven if (__first.__ctz_ != 0) 315227825Stheraven { 316227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 317227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 318227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 319227825Stheraven *__first.__seg_ &= ~__m; 320227825Stheraven __n -= __dn; 321227825Stheraven ++__first.__seg_; 322227825Stheraven } 323227825Stheraven // do middle whole words 324227825Stheraven __storage_type __nw = __n / __bits_per_word; 325227825Stheraven _VSTD::memset(__first.__seg_, 0, __nw * sizeof(__storage_type)); 326227825Stheraven __n -= __nw * __bits_per_word; 327227825Stheraven // do last partial word 328227825Stheraven if (__n > 0) 329227825Stheraven { 330227825Stheraven __first.__seg_ += __nw; 331227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 332227825Stheraven *__first.__seg_ &= ~__m; 333227825Stheraven } 334227825Stheraven} 335227825Stheraven 336232950Stheraventemplate <class _Cp> 337227825Stheravenvoid 338232950Stheraven__fill_n_true(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) 339227825Stheraven{ 340232950Stheraven typedef __bit_iterator<_Cp, false> _It; 341227825Stheraven typedef typename _It::__storage_type __storage_type; 342227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 343227825Stheraven // do first partial word 344227825Stheraven if (__first.__ctz_ != 0) 345227825Stheraven { 346227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 347227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 348227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 349227825Stheraven *__first.__seg_ |= __m; 350227825Stheraven __n -= __dn; 351227825Stheraven ++__first.__seg_; 352227825Stheraven } 353227825Stheraven // do middle whole words 354227825Stheraven __storage_type __nw = __n / __bits_per_word; 355227825Stheraven _VSTD::memset(__first.__seg_, -1, __nw * sizeof(__storage_type)); 356227825Stheraven __n -= __nw * __bits_per_word; 357227825Stheraven // do last partial word 358227825Stheraven if (__n > 0) 359227825Stheraven { 360227825Stheraven __first.__seg_ += __nw; 361227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 362227825Stheraven *__first.__seg_ |= __m; 363227825Stheraven } 364227825Stheraven} 365227825Stheraven 366232950Stheraventemplate <class _Cp> 367227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 368227825Stheravenvoid 369232950Stheravenfill_n(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n, bool __value_) 370227825Stheraven{ 371227825Stheraven if (__n > 0) 372227825Stheraven { 373227825Stheraven if (__value_) 374227825Stheraven __fill_n_true(__first, __n); 375227825Stheraven else 376227825Stheraven __fill_n_false(__first, __n); 377227825Stheraven } 378227825Stheraven} 379227825Stheraven 380227825Stheraven// fill 381227825Stheraven 382232950Stheraventemplate <class _Cp> 383227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 384227825Stheravenvoid 385232950Stheravenfill(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __last, bool __value_) 386227825Stheraven{ 387232950Stheraven _VSTD::fill_n(__first, static_cast<typename _Cp::size_type>(__last - __first), __value_); 388227825Stheraven} 389227825Stheraven 390227825Stheraven// copy 391227825Stheraven 392232950Stheraventemplate <class _Cp, bool _IsConst> 393232950Stheraven__bit_iterator<_Cp, false> 394232950Stheraven__copy_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 395232950Stheraven __bit_iterator<_Cp, false> __result) 396227825Stheraven{ 397232950Stheraven typedef __bit_iterator<_Cp, _IsConst> _In; 398227825Stheraven typedef typename _In::difference_type difference_type; 399227825Stheraven typedef typename _In::__storage_type __storage_type; 400227825Stheraven static const unsigned __bits_per_word = _In::__bits_per_word; 401227825Stheraven difference_type __n = __last - __first; 402227825Stheraven if (__n > 0) 403227825Stheraven { 404227825Stheraven // do first word 405227825Stheraven if (__first.__ctz_ != 0) 406227825Stheraven { 407227825Stheraven unsigned __clz = __bits_per_word - __first.__ctz_; 408227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 409227825Stheraven __n -= __dn; 410227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 411227825Stheraven __storage_type __b = *__first.__seg_ & __m; 412227825Stheraven *__result.__seg_ &= ~__m; 413227825Stheraven *__result.__seg_ |= __b; 414227825Stheraven __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 415227825Stheraven __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 416227825Stheraven ++__first.__seg_; 417227825Stheraven // __first.__ctz_ = 0; 418227825Stheraven } 419227825Stheraven // __first.__ctz_ == 0; 420227825Stheraven // do middle words 421227825Stheraven __storage_type __nw = __n / __bits_per_word; 422227825Stheraven _VSTD::memmove(__result.__seg_, __first.__seg_, __nw * sizeof(__storage_type)); 423227825Stheraven __n -= __nw * __bits_per_word; 424227825Stheraven __result.__seg_ += __nw; 425227825Stheraven // do last word 426227825Stheraven if (__n > 0) 427227825Stheraven { 428227825Stheraven __first.__seg_ += __nw; 429227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 430227825Stheraven __storage_type __b = *__first.__seg_ & __m; 431227825Stheraven *__result.__seg_ &= ~__m; 432227825Stheraven *__result.__seg_ |= __b; 433227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 434227825Stheraven } 435227825Stheraven } 436227825Stheraven return __result; 437227825Stheraven} 438227825Stheraven 439232950Stheraventemplate <class _Cp, bool _IsConst> 440232950Stheraven__bit_iterator<_Cp, false> 441232950Stheraven__copy_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 442232950Stheraven __bit_iterator<_Cp, false> __result) 443227825Stheraven{ 444232950Stheraven typedef __bit_iterator<_Cp, _IsConst> _In; 445227825Stheraven typedef typename _In::difference_type difference_type; 446227825Stheraven typedef typename _In::__storage_type __storage_type; 447227825Stheraven static const unsigned __bits_per_word = _In::__bits_per_word; 448227825Stheraven difference_type __n = __last - __first; 449227825Stheraven if (__n > 0) 450227825Stheraven { 451227825Stheraven // do first word 452227825Stheraven if (__first.__ctz_ != 0) 453227825Stheraven { 454227825Stheraven unsigned __clz_f = __bits_per_word - __first.__ctz_; 455227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 456227825Stheraven __n -= __dn; 457227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 458227825Stheraven __storage_type __b = *__first.__seg_ & __m; 459227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 460227825Stheraven __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 461227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 462227825Stheraven *__result.__seg_ &= ~__m; 463227825Stheraven if (__result.__ctz_ > __first.__ctz_) 464227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_); 465227825Stheraven else 466227825Stheraven *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_); 467227825Stheraven __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 468227825Stheraven __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 469227825Stheraven __dn -= __ddn; 470227825Stheraven if (__dn > 0) 471227825Stheraven { 472227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __dn); 473227825Stheraven *__result.__seg_ &= ~__m; 474227825Stheraven *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn); 475227825Stheraven __result.__ctz_ = static_cast<unsigned>(__dn); 476227825Stheraven } 477227825Stheraven ++__first.__seg_; 478227825Stheraven // __first.__ctz_ = 0; 479227825Stheraven } 480227825Stheraven // __first.__ctz_ == 0; 481227825Stheraven // do middle words 482227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 483227825Stheraven __storage_type __m = ~__storage_type(0) << __result.__ctz_; 484227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 485227825Stheraven { 486227825Stheraven __storage_type __b = *__first.__seg_; 487227825Stheraven *__result.__seg_ &= ~__m; 488227825Stheraven *__result.__seg_ |= __b << __result.__ctz_; 489227825Stheraven ++__result.__seg_; 490227825Stheraven *__result.__seg_ &= __m; 491227825Stheraven *__result.__seg_ |= __b >> __clz_r; 492227825Stheraven } 493227825Stheraven // do last word 494227825Stheraven if (__n > 0) 495227825Stheraven { 496227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 497227825Stheraven __storage_type __b = *__first.__seg_ & __m; 498227825Stheraven __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); 499227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 500227825Stheraven *__result.__seg_ &= ~__m; 501227825Stheraven *__result.__seg_ |= __b << __result.__ctz_; 502227825Stheraven __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 503227825Stheraven __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 504227825Stheraven __n -= __dn; 505227825Stheraven if (__n > 0) 506227825Stheraven { 507227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 508227825Stheraven *__result.__seg_ &= ~__m; 509227825Stheraven *__result.__seg_ |= __b >> __dn; 510227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 511227825Stheraven } 512227825Stheraven } 513227825Stheraven } 514227825Stheraven return __result; 515227825Stheraven} 516227825Stheraven 517232950Stheraventemplate <class _Cp, bool _IsConst> 518227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 519232950Stheraven__bit_iterator<_Cp, false> 520232950Stheravencopy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 521227825Stheraven{ 522227825Stheraven if (__first.__ctz_ == __result.__ctz_) 523227825Stheraven return __copy_aligned(__first, __last, __result); 524227825Stheraven return __copy_unaligned(__first, __last, __result); 525227825Stheraven} 526227825Stheraven 527227825Stheraven// copy_backward 528227825Stheraven 529232950Stheraventemplate <class _Cp, bool _IsConst> 530232950Stheraven__bit_iterator<_Cp, false> 531232950Stheraven__copy_backward_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 532232950Stheraven __bit_iterator<_Cp, false> __result) 533227825Stheraven{ 534232950Stheraven typedef __bit_iterator<_Cp, _IsConst> _In; 535227825Stheraven typedef typename _In::difference_type difference_type; 536227825Stheraven typedef typename _In::__storage_type __storage_type; 537227825Stheraven static const unsigned __bits_per_word = _In::__bits_per_word; 538227825Stheraven difference_type __n = __last - __first; 539227825Stheraven if (__n > 0) 540227825Stheraven { 541227825Stheraven // do first word 542227825Stheraven if (__last.__ctz_ != 0) 543227825Stheraven { 544227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); 545227825Stheraven __n -= __dn; 546227825Stheraven unsigned __clz = __bits_per_word - __last.__ctz_; 547227825Stheraven __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz); 548227825Stheraven __storage_type __b = *__last.__seg_ & __m; 549227825Stheraven *__result.__seg_ &= ~__m; 550227825Stheraven *__result.__seg_ |= __b; 551227825Stheraven __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 552227825Stheraven __result.__ctz_) % __bits_per_word); 553227825Stheraven // __last.__ctz_ = 0 554227825Stheraven } 555227825Stheraven // __last.__ctz_ == 0 || __n == 0 556227825Stheraven // __result.__ctz_ == 0 || __n == 0 557227825Stheraven // do middle words 558227825Stheraven __storage_type __nw = __n / __bits_per_word; 559227825Stheraven __result.__seg_ -= __nw; 560227825Stheraven __last.__seg_ -= __nw; 561227825Stheraven _VSTD::memmove(__result.__seg_, __last.__seg_, __nw * sizeof(__storage_type)); 562227825Stheraven __n -= __nw * __bits_per_word; 563227825Stheraven // do last word 564227825Stheraven if (__n > 0) 565227825Stheraven { 566227825Stheraven __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n); 567227825Stheraven __storage_type __b = *--__last.__seg_ & __m; 568227825Stheraven *--__result.__seg_ &= ~__m; 569227825Stheraven *__result.__seg_ |= __b; 570227825Stheraven __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 571227825Stheraven } 572227825Stheraven } 573227825Stheraven return __result; 574227825Stheraven} 575227825Stheraven 576232950Stheraventemplate <class _Cp, bool _IsConst> 577232950Stheraven__bit_iterator<_Cp, false> 578232950Stheraven__copy_backward_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 579232950Stheraven __bit_iterator<_Cp, false> __result) 580227825Stheraven{ 581232950Stheraven typedef __bit_iterator<_Cp, _IsConst> _In; 582227825Stheraven typedef typename _In::difference_type difference_type; 583227825Stheraven typedef typename _In::__storage_type __storage_type; 584227825Stheraven static const unsigned __bits_per_word = _In::__bits_per_word; 585227825Stheraven difference_type __n = __last - __first; 586227825Stheraven if (__n > 0) 587227825Stheraven { 588227825Stheraven // do first word 589227825Stheraven if (__last.__ctz_ != 0) 590227825Stheraven { 591227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); 592227825Stheraven __n -= __dn; 593227825Stheraven unsigned __clz_l = __bits_per_word - __last.__ctz_; 594227825Stheraven __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l); 595227825Stheraven __storage_type __b = *__last.__seg_ & __m; 596227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 597227825Stheraven __storage_type __ddn = _VSTD::min(__dn, static_cast<difference_type>(__result.__ctz_)); 598227825Stheraven if (__ddn > 0) 599227825Stheraven { 600227825Stheraven __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r); 601227825Stheraven *__result.__seg_ &= ~__m; 602227825Stheraven if (__result.__ctz_ > __last.__ctz_) 603227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 604227825Stheraven else 605227825Stheraven *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_); 606227825Stheraven __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) + 607227825Stheraven __result.__ctz_) % __bits_per_word); 608227825Stheraven __dn -= __ddn; 609227825Stheraven } 610227825Stheraven if (__dn > 0) 611227825Stheraven { 612227825Stheraven // __result.__ctz_ == 0 613227825Stheraven --__result.__seg_; 614227825Stheraven __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1)); 615227825Stheraven __m = ~__storage_type(0) << __result.__ctz_; 616227825Stheraven *__result.__seg_ &= ~__m; 617227825Stheraven __last.__ctz_ -= __dn + __ddn; 618227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 619227825Stheraven } 620227825Stheraven // __last.__ctz_ = 0 621227825Stheraven } 622227825Stheraven // __last.__ctz_ == 0 || __n == 0 623227825Stheraven // __result.__ctz_ != 0 || __n == 0 624227825Stheraven // do middle words 625227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 626227825Stheraven __storage_type __m = ~__storage_type(0) >> __clz_r; 627227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word) 628227825Stheraven { 629227825Stheraven __storage_type __b = *--__last.__seg_; 630227825Stheraven *__result.__seg_ &= ~__m; 631227825Stheraven *__result.__seg_ |= __b >> __clz_r; 632227825Stheraven *--__result.__seg_ &= __m; 633227825Stheraven *__result.__seg_ |= __b << __result.__ctz_; 634227825Stheraven } 635227825Stheraven // do last word 636227825Stheraven if (__n > 0) 637227825Stheraven { 638227825Stheraven __m = ~__storage_type(0) << (__bits_per_word - __n); 639227825Stheraven __storage_type __b = *--__last.__seg_ & __m; 640232950Stheraven __clz_r = __bits_per_word - __result.__ctz_; 641227825Stheraven __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__result.__ctz_)); 642227825Stheraven __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r); 643227825Stheraven *__result.__seg_ &= ~__m; 644227825Stheraven *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_); 645227825Stheraven __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 646227825Stheraven __result.__ctz_) % __bits_per_word); 647227825Stheraven __n -= __dn; 648227825Stheraven if (__n > 0) 649227825Stheraven { 650227825Stheraven // __result.__ctz_ == 0 651227825Stheraven --__result.__seg_; 652227825Stheraven __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 653227825Stheraven __m = ~__storage_type(0) << __result.__ctz_; 654227825Stheraven *__result.__seg_ &= ~__m; 655227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn)); 656227825Stheraven } 657227825Stheraven } 658227825Stheraven } 659227825Stheraven return __result; 660227825Stheraven} 661227825Stheraven 662232950Stheraventemplate <class _Cp, bool _IsConst> 663227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 664232950Stheraven__bit_iterator<_Cp, false> 665232950Stheravencopy_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 666227825Stheraven{ 667227825Stheraven if (__last.__ctz_ == __result.__ctz_) 668227825Stheraven return __copy_backward_aligned(__first, __last, __result); 669227825Stheraven return __copy_backward_unaligned(__first, __last, __result); 670227825Stheraven} 671227825Stheraven 672227825Stheraven// move 673227825Stheraven 674232950Stheraventemplate <class _Cp, bool _IsConst> 675227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 676232950Stheraven__bit_iterator<_Cp, false> 677232950Stheravenmove(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 678227825Stheraven{ 679227825Stheraven return _VSTD::copy(__first, __last, __result); 680227825Stheraven} 681227825Stheraven 682227825Stheraven// move_backward 683227825Stheraven 684232950Stheraventemplate <class _Cp, bool _IsConst> 685227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 686232950Stheraven__bit_iterator<_Cp, false> 687232950Stheravenmove_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 688227825Stheraven{ 689227825Stheraven return _VSTD::copy(__first, __last, __result); 690227825Stheraven} 691227825Stheraven 692227825Stheraven// swap_ranges 693227825Stheraven 694227825Stheraventemplate <class __C1, class __C2> 695227825Stheraven__bit_iterator<__C2, false> 696227825Stheraven__swap_ranges_aligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, 697227825Stheraven __bit_iterator<__C2, false> __result) 698227825Stheraven{ 699227825Stheraven typedef __bit_iterator<__C1, false> _I1; 700227825Stheraven typedef typename _I1::difference_type difference_type; 701227825Stheraven typedef typename _I1::__storage_type __storage_type; 702227825Stheraven static const unsigned __bits_per_word = _I1::__bits_per_word; 703227825Stheraven difference_type __n = __last - __first; 704227825Stheraven if (__n > 0) 705227825Stheraven { 706227825Stheraven // do first word 707227825Stheraven if (__first.__ctz_ != 0) 708227825Stheraven { 709227825Stheraven unsigned __clz = __bits_per_word - __first.__ctz_; 710227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 711227825Stheraven __n -= __dn; 712227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 713227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 714227825Stheraven *__first.__seg_ &= ~__m; 715227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 716227825Stheraven *__result.__seg_ &= ~__m; 717227825Stheraven *__result.__seg_ |= __b1; 718227825Stheraven *__first.__seg_ |= __b2; 719227825Stheraven __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 720227825Stheraven __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 721227825Stheraven ++__first.__seg_; 722227825Stheraven // __first.__ctz_ = 0; 723227825Stheraven } 724227825Stheraven // __first.__ctz_ == 0; 725227825Stheraven // do middle words 726227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_) 727227825Stheraven swap(*__first.__seg_, *__result.__seg_); 728227825Stheraven // do last word 729227825Stheraven if (__n > 0) 730227825Stheraven { 731227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 732227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 733227825Stheraven *__first.__seg_ &= ~__m; 734227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 735227825Stheraven *__result.__seg_ &= ~__m; 736227825Stheraven *__result.__seg_ |= __b1; 737227825Stheraven *__first.__seg_ |= __b2; 738227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 739227825Stheraven } 740227825Stheraven } 741227825Stheraven return __result; 742227825Stheraven} 743227825Stheraven 744227825Stheraventemplate <class __C1, class __C2> 745227825Stheraven__bit_iterator<__C2, false> 746227825Stheraven__swap_ranges_unaligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, 747227825Stheraven __bit_iterator<__C2, false> __result) 748227825Stheraven{ 749227825Stheraven typedef __bit_iterator<__C1, false> _I1; 750227825Stheraven typedef typename _I1::difference_type difference_type; 751227825Stheraven typedef typename _I1::__storage_type __storage_type; 752227825Stheraven static const unsigned __bits_per_word = _I1::__bits_per_word; 753227825Stheraven difference_type __n = __last - __first; 754227825Stheraven if (__n > 0) 755227825Stheraven { 756227825Stheraven // do first word 757227825Stheraven if (__first.__ctz_ != 0) 758227825Stheraven { 759227825Stheraven unsigned __clz_f = __bits_per_word - __first.__ctz_; 760227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 761227825Stheraven __n -= __dn; 762227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 763227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 764227825Stheraven *__first.__seg_ &= ~__m; 765227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 766227825Stheraven __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 767227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 768227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 769227825Stheraven *__result.__seg_ &= ~__m; 770227825Stheraven if (__result.__ctz_ > __first.__ctz_) 771227825Stheraven { 772227825Stheraven unsigned __s = __result.__ctz_ - __first.__ctz_; 773227825Stheraven *__result.__seg_ |= __b1 << __s; 774227825Stheraven *__first.__seg_ |= __b2 >> __s; 775227825Stheraven } 776227825Stheraven else 777227825Stheraven { 778227825Stheraven unsigned __s = __first.__ctz_ - __result.__ctz_; 779227825Stheraven *__result.__seg_ |= __b1 >> __s; 780227825Stheraven *__first.__seg_ |= __b2 << __s; 781227825Stheraven } 782227825Stheraven __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 783227825Stheraven __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 784227825Stheraven __dn -= __ddn; 785227825Stheraven if (__dn > 0) 786227825Stheraven { 787227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __dn); 788227825Stheraven __b2 = *__result.__seg_ & __m; 789227825Stheraven *__result.__seg_ &= ~__m; 790227825Stheraven unsigned __s = __first.__ctz_ + __ddn; 791227825Stheraven *__result.__seg_ |= __b1 >> __s; 792227825Stheraven *__first.__seg_ |= __b2 << __s; 793227825Stheraven __result.__ctz_ = static_cast<unsigned>(__dn); 794227825Stheraven } 795227825Stheraven ++__first.__seg_; 796227825Stheraven // __first.__ctz_ = 0; 797227825Stheraven } 798227825Stheraven // __first.__ctz_ == 0; 799227825Stheraven // do middle words 800227825Stheraven __storage_type __m = ~__storage_type(0) << __result.__ctz_; 801227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 802227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 803227825Stheraven { 804227825Stheraven __storage_type __b1 = *__first.__seg_; 805227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 806227825Stheraven *__result.__seg_ &= ~__m; 807227825Stheraven *__result.__seg_ |= __b1 << __result.__ctz_; 808227825Stheraven *__first.__seg_ = __b2 >> __result.__ctz_; 809227825Stheraven ++__result.__seg_; 810227825Stheraven __b2 = *__result.__seg_ & ~__m; 811227825Stheraven *__result.__seg_ &= __m; 812227825Stheraven *__result.__seg_ |= __b1 >> __clz_r; 813227825Stheraven *__first.__seg_ |= __b2 << __clz_r; 814227825Stheraven } 815227825Stheraven // do last word 816227825Stheraven if (__n > 0) 817227825Stheraven { 818227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 819227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 820227825Stheraven *__first.__seg_ &= ~__m; 821227825Stheraven __storage_type __dn = _VSTD::min<__storage_type>(__n, __clz_r); 822227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 823227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 824227825Stheraven *__result.__seg_ &= ~__m; 825227825Stheraven *__result.__seg_ |= __b1 << __result.__ctz_; 826227825Stheraven *__first.__seg_ |= __b2 >> __result.__ctz_; 827227825Stheraven __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 828227825Stheraven __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 829227825Stheraven __n -= __dn; 830227825Stheraven if (__n > 0) 831227825Stheraven { 832227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 833227825Stheraven __b2 = *__result.__seg_ & __m; 834227825Stheraven *__result.__seg_ &= ~__m; 835227825Stheraven *__result.__seg_ |= __b1 >> __dn; 836227825Stheraven *__first.__seg_ |= __b2 << __dn; 837227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 838227825Stheraven } 839227825Stheraven } 840227825Stheraven } 841227825Stheraven return __result; 842227825Stheraven} 843227825Stheraven 844227825Stheraventemplate <class __C1, class __C2> 845227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 846227825Stheraven__bit_iterator<__C2, false> 847227825Stheravenswap_ranges(__bit_iterator<__C1, false> __first1, __bit_iterator<__C1, false> __last1, 848227825Stheraven __bit_iterator<__C2, false> __first2) 849227825Stheraven{ 850227825Stheraven if (__first1.__ctz_ == __first2.__ctz_) 851227825Stheraven return __swap_ranges_aligned(__first1, __last1, __first2); 852227825Stheraven return __swap_ranges_unaligned(__first1, __last1, __first2); 853227825Stheraven} 854227825Stheraven 855227825Stheraven// rotate 856227825Stheraven 857232950Stheraventemplate <class _Cp> 858227825Stheravenstruct __bit_array 859227825Stheraven{ 860232950Stheraven typedef typename _Cp::difference_type difference_type; 861232950Stheraven typedef typename _Cp::__storage_type __storage_type; 862232950Stheraven typedef typename _Cp::iterator iterator; 863232950Stheraven static const unsigned __bits_per_word = _Cp::__bits_per_word; 864232950Stheraven static const unsigned _Np = 4; 865227825Stheraven 866227825Stheraven difference_type __size_; 867232950Stheraven __storage_type __word_[_Np]; 868227825Stheraven 869227825Stheraven _LIBCPP_INLINE_VISIBILITY static difference_type capacity() 870232950Stheraven {return static_cast<difference_type>(_Np * __bits_per_word);} 871227825Stheraven _LIBCPP_INLINE_VISIBILITY explicit __bit_array(difference_type __s) : __size_(__s) {} 872227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator begin() {return iterator(__word_, 0);} 873227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator end() {return iterator(__word_ + __size_ / __bits_per_word, 874227825Stheraven static_cast<unsigned>(__size_ % __bits_per_word));} 875227825Stheraven}; 876227825Stheraven 877232950Stheraventemplate <class _Cp> 878232950Stheraven__bit_iterator<_Cp, false> 879232950Stheravenrotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last) 880227825Stheraven{ 881232950Stheraven typedef __bit_iterator<_Cp, false> _I1; 882227825Stheraven typedef typename _I1::difference_type difference_type; 883227825Stheraven typedef typename _I1::__storage_type __storage_type; 884227825Stheraven difference_type __d1 = __middle - __first; 885227825Stheraven difference_type __d2 = __last - __middle; 886227825Stheraven _I1 __r = __first + __d2; 887227825Stheraven while (__d1 != 0 && __d2 != 0) 888227825Stheraven { 889227825Stheraven if (__d1 <= __d2) 890227825Stheraven { 891232950Stheraven if (__d1 <= __bit_array<_Cp>::capacity()) 892227825Stheraven { 893232950Stheraven __bit_array<_Cp> __b(__d1); 894227825Stheraven _VSTD::copy(__first, __middle, __b.begin()); 895227825Stheraven _VSTD::copy(__b.begin(), __b.end(), _VSTD::copy(__middle, __last, __first)); 896227825Stheraven break; 897227825Stheraven } 898227825Stheraven else 899227825Stheraven { 900232950Stheraven __bit_iterator<_Cp, false> __mp = _VSTD::swap_ranges(__first, __middle, __middle); 901227825Stheraven __first = __middle; 902227825Stheraven __middle = __mp; 903227825Stheraven __d2 -= __d1; 904227825Stheraven } 905227825Stheraven } 906227825Stheraven else 907227825Stheraven { 908232950Stheraven if (__d2 <= __bit_array<_Cp>::capacity()) 909227825Stheraven { 910232950Stheraven __bit_array<_Cp> __b(__d2); 911227825Stheraven _VSTD::copy(__middle, __last, __b.begin()); 912227825Stheraven _VSTD::copy_backward(__b.begin(), __b.end(), _VSTD::copy_backward(__first, __middle, __last)); 913227825Stheraven break; 914227825Stheraven } 915227825Stheraven else 916227825Stheraven { 917232950Stheraven __bit_iterator<_Cp, false> __mp = __first + __d2; 918227825Stheraven _VSTD::swap_ranges(__first, __mp, __middle); 919227825Stheraven __first = __mp; 920227825Stheraven __d1 -= __d2; 921227825Stheraven } 922227825Stheraven } 923227825Stheraven } 924227825Stheraven return __r; 925227825Stheraven} 926227825Stheraven 927227825Stheraven// equal 928227825Stheraven 929232950Stheraventemplate <class _Cp> 930227825Stheravenbool 931232950Stheraven__equal_unaligned(__bit_iterator<_Cp, true> __first1, __bit_iterator<_Cp, true> __last1, 932232950Stheraven __bit_iterator<_Cp, true> __first2) 933227825Stheraven{ 934232950Stheraven typedef __bit_iterator<_Cp, true> _It; 935227825Stheraven typedef typename _It::difference_type difference_type; 936227825Stheraven typedef typename _It::__storage_type __storage_type; 937227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 938227825Stheraven difference_type __n = __last1 - __first1; 939227825Stheraven if (__n > 0) 940227825Stheraven { 941227825Stheraven // do first word 942227825Stheraven if (__first1.__ctz_ != 0) 943227825Stheraven { 944227825Stheraven unsigned __clz_f = __bits_per_word - __first1.__ctz_; 945227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 946227825Stheraven __n -= __dn; 947227825Stheraven __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 948227825Stheraven __storage_type __b = *__first1.__seg_ & __m; 949227825Stheraven unsigned __clz_r = __bits_per_word - __first2.__ctz_; 950227825Stheraven __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 951227825Stheraven __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 952227825Stheraven if (__first2.__ctz_ > __first1.__ctz_) 953236387Sdim { 954227825Stheraven if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_))) 955227825Stheraven return false; 956236387Sdim } 957227825Stheraven else 958236387Sdim { 959227825Stheraven if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_))) 960227825Stheraven return false; 961236387Sdim } 962227825Stheraven __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word; 963227825Stheraven __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word); 964227825Stheraven __dn -= __ddn; 965227825Stheraven if (__dn > 0) 966227825Stheraven { 967227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __dn); 968227825Stheraven if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn))) 969227825Stheraven return false; 970227825Stheraven __first2.__ctz_ = static_cast<unsigned>(__dn); 971227825Stheraven } 972227825Stheraven ++__first1.__seg_; 973227825Stheraven // __first1.__ctz_ = 0; 974227825Stheraven } 975227825Stheraven // __first1.__ctz_ == 0; 976227825Stheraven // do middle words 977227825Stheraven unsigned __clz_r = __bits_per_word - __first2.__ctz_; 978227825Stheraven __storage_type __m = ~__storage_type(0) << __first2.__ctz_; 979227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_) 980227825Stheraven { 981227825Stheraven __storage_type __b = *__first1.__seg_; 982227825Stheraven if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 983227825Stheraven return false; 984227825Stheraven ++__first2.__seg_; 985227825Stheraven if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r)) 986227825Stheraven return false; 987227825Stheraven } 988227825Stheraven // do last word 989227825Stheraven if (__n > 0) 990227825Stheraven { 991227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 992227825Stheraven __storage_type __b = *__first1.__seg_ & __m; 993227825Stheraven __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); 994227825Stheraven __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 995227825Stheraven if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 996227825Stheraven return false; 997227825Stheraven __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word; 998227825Stheraven __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word); 999227825Stheraven __n -= __dn; 1000227825Stheraven if (__n > 0) 1001227825Stheraven { 1002227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 1003227825Stheraven if ((*__first2.__seg_ & __m) != (__b >> __dn)) 1004227825Stheraven return false; 1005227825Stheraven } 1006227825Stheraven } 1007227825Stheraven } 1008227825Stheraven return true; 1009227825Stheraven} 1010227825Stheraven 1011232950Stheraventemplate <class _Cp> 1012227825Stheravenbool 1013232950Stheraven__equal_aligned(__bit_iterator<_Cp, true> __first1, __bit_iterator<_Cp, true> __last1, 1014232950Stheraven __bit_iterator<_Cp, true> __first2) 1015227825Stheraven{ 1016232950Stheraven typedef __bit_iterator<_Cp, true> _It; 1017227825Stheraven typedef typename _It::difference_type difference_type; 1018227825Stheraven typedef typename _It::__storage_type __storage_type; 1019227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 1020227825Stheraven difference_type __n = __last1 - __first1; 1021227825Stheraven if (__n > 0) 1022227825Stheraven { 1023227825Stheraven // do first word 1024227825Stheraven if (__first1.__ctz_ != 0) 1025227825Stheraven { 1026227825Stheraven unsigned __clz = __bits_per_word - __first1.__ctz_; 1027227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 1028227825Stheraven __n -= __dn; 1029227825Stheraven __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 1030227825Stheraven if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 1031227825Stheraven return false; 1032227825Stheraven ++__first2.__seg_; 1033227825Stheraven ++__first1.__seg_; 1034227825Stheraven // __first1.__ctz_ = 0; 1035227825Stheraven // __first2.__ctz_ = 0; 1036227825Stheraven } 1037227825Stheraven // __first1.__ctz_ == 0; 1038227825Stheraven // __first2.__ctz_ == 0; 1039227825Stheraven // do middle words 1040227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_) 1041227825Stheraven if (*__first2.__seg_ != *__first1.__seg_) 1042227825Stheraven return false; 1043227825Stheraven // do last word 1044227825Stheraven if (__n > 0) 1045227825Stheraven { 1046227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 1047227825Stheraven if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 1048227825Stheraven return false; 1049227825Stheraven } 1050227825Stheraven } 1051227825Stheraven return true; 1052227825Stheraven} 1053227825Stheraven 1054232950Stheraventemplate <class _Cp, bool _IC1, bool _IC2> 1055227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1056227825Stheravenbool 1057232950Stheravenequal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) 1058227825Stheraven{ 1059227825Stheraven if (__first1.__ctz_ == __first2.__ctz_) 1060227825Stheraven return __equal_aligned(__first1, __last1, __first2); 1061227825Stheraven return __equal_unaligned(__first1, __last1, __first2); 1062227825Stheraven} 1063227825Stheraven 1064232950Stheraventemplate <class _Cp, bool _IsConst> 1065227825Stheravenclass __bit_iterator 1066227825Stheraven{ 1067227825Stheravenpublic: 1068232950Stheraven typedef typename _Cp::difference_type difference_type; 1069227825Stheraven typedef bool value_type; 1070227825Stheraven typedef __bit_iterator pointer; 1071232950Stheraven typedef typename conditional<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >::type reference; 1072227825Stheraven typedef random_access_iterator_tag iterator_category; 1073227825Stheraven 1074227825Stheravenprivate: 1075232950Stheraven typedef typename _Cp::__storage_type __storage_type; 1076232950Stheraven typedef typename conditional<_IsConst, typename _Cp::__const_storage_pointer, 1077232950Stheraven typename _Cp::__storage_pointer>::type __storage_pointer; 1078232950Stheraven static const unsigned __bits_per_word = _Cp::__bits_per_word; 1079227825Stheraven 1080227825Stheraven __storage_pointer __seg_; 1081227825Stheraven unsigned __ctz_; 1082227825Stheraven 1083227825Stheravenpublic: 1084227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator() _NOEXCEPT {} 1085227825Stheraven 1086227825Stheraven _LIBCPP_INLINE_VISIBILITY 1087232950Stheraven __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT 1088227825Stheraven : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {} 1089227825Stheraven 1090227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT 1091227825Stheraven {return reference(__seg_, __storage_type(1) << __ctz_);} 1092227825Stheraven 1093227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator++() 1094227825Stheraven { 1095227825Stheraven if (__ctz_ != __bits_per_word-1) 1096227825Stheraven ++__ctz_; 1097227825Stheraven else 1098227825Stheraven { 1099227825Stheraven __ctz_ = 0; 1100227825Stheraven ++__seg_; 1101227825Stheraven } 1102227825Stheraven return *this; 1103227825Stheraven } 1104227825Stheraven 1105227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator operator++(int) 1106227825Stheraven { 1107227825Stheraven __bit_iterator __tmp = *this; 1108227825Stheraven ++(*this); 1109227825Stheraven return __tmp; 1110227825Stheraven } 1111227825Stheraven 1112227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator--() 1113227825Stheraven { 1114227825Stheraven if (__ctz_ != 0) 1115227825Stheraven --__ctz_; 1116227825Stheraven else 1117227825Stheraven { 1118227825Stheraven __ctz_ = __bits_per_word - 1; 1119227825Stheraven --__seg_; 1120227825Stheraven } 1121227825Stheraven return *this; 1122227825Stheraven } 1123227825Stheraven 1124227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator operator--(int) 1125227825Stheraven { 1126227825Stheraven __bit_iterator __tmp = *this; 1127227825Stheraven --(*this); 1128227825Stheraven return __tmp; 1129227825Stheraven } 1130227825Stheraven 1131227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator+=(difference_type __n) 1132227825Stheraven { 1133227825Stheraven if (__n >= 0) 1134227825Stheraven __seg_ += (__n + __ctz_) / __bits_per_word; 1135227825Stheraven else 1136227825Stheraven __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1) 1137227825Stheraven / static_cast<difference_type>(__bits_per_word); 1138227825Stheraven __n &= (__bits_per_word - 1); 1139227825Stheraven __ctz_ = static_cast<unsigned>((__n + __ctz_) % __bits_per_word); 1140227825Stheraven return *this; 1141227825Stheraven } 1142227825Stheraven 1143227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator-=(difference_type __n) 1144227825Stheraven { 1145227825Stheraven return *this += -__n; 1146227825Stheraven } 1147227825Stheraven 1148227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator operator+(difference_type __n) const 1149227825Stheraven { 1150227825Stheraven __bit_iterator __t(*this); 1151227825Stheraven __t += __n; 1152227825Stheraven return __t; 1153227825Stheraven } 1154227825Stheraven 1155227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator operator-(difference_type __n) const 1156227825Stheraven { 1157227825Stheraven __bit_iterator __t(*this); 1158227825Stheraven __t -= __n; 1159227825Stheraven return __t; 1160227825Stheraven } 1161227825Stheraven 1162227825Stheraven _LIBCPP_INLINE_VISIBILITY 1163227825Stheraven friend __bit_iterator operator+(difference_type __n, const __bit_iterator& __it) {return __it + __n;} 1164227825Stheraven 1165227825Stheraven _LIBCPP_INLINE_VISIBILITY 1166227825Stheraven friend difference_type operator-(const __bit_iterator& __x, const __bit_iterator& __y) 1167227825Stheraven {return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;} 1168227825Stheraven 1169227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const {return *(*this + __n);} 1170227825Stheraven 1171227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator==(const __bit_iterator& __x, const __bit_iterator& __y) 1172227825Stheraven {return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;} 1173227825Stheraven 1174227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator!=(const __bit_iterator& __x, const __bit_iterator& __y) 1175227825Stheraven {return !(__x == __y);} 1176227825Stheraven 1177227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator<(const __bit_iterator& __x, const __bit_iterator& __y) 1178227825Stheraven {return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);} 1179227825Stheraven 1180227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator>(const __bit_iterator& __x, const __bit_iterator& __y) 1181227825Stheraven {return __y < __x;} 1182227825Stheraven 1183227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y) 1184227825Stheraven {return !(__y < __x);} 1185227825Stheraven 1186227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y) 1187227825Stheraven {return !(__x < __y);} 1188227825Stheraven 1189227825Stheravenprivate: 1190227825Stheraven _LIBCPP_INLINE_VISIBILITY 1191227825Stheraven __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT 1192227825Stheraven : __seg_(__s), __ctz_(__ctz) {} 1193227825Stheraven 1194227825Stheraven#if defined(__clang__) 1195232950Stheraven friend typename _Cp::__self; 1196227825Stheraven#else 1197232950Stheraven friend class _Cp::__self; 1198227825Stheraven#endif 1199232950Stheraven friend class __bit_reference<_Cp>; 1200232950Stheraven friend class __bit_const_reference<_Cp>; 1201232950Stheraven friend class __bit_iterator<_Cp, true>; 1202232950Stheraven template <class _Dp> friend struct __bit_array; 1203232950Stheraven template <class _Dp> friend void __fill_n_false(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); 1204232950Stheraven template <class _Dp> friend void __fill_n_true(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); 1205232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_aligned(__bit_iterator<_Dp, _IC> __first, 1206232950Stheraven __bit_iterator<_Dp, _IC> __last, 1207232950Stheraven __bit_iterator<_Dp, false> __result); 1208232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_unaligned(__bit_iterator<_Dp, _IC> __first, 1209232950Stheraven __bit_iterator<_Dp, _IC> __last, 1210232950Stheraven __bit_iterator<_Dp, false> __result); 1211232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy(__bit_iterator<_Dp, _IC> __first, 1212232950Stheraven __bit_iterator<_Dp, _IC> __last, 1213232950Stheraven __bit_iterator<_Dp, false> __result); 1214232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_aligned(__bit_iterator<_Dp, _IC> __first, 1215232950Stheraven __bit_iterator<_Dp, _IC> __last, 1216232950Stheraven __bit_iterator<_Dp, false> __result); 1217232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_unaligned(__bit_iterator<_Dp, _IC> __first, 1218232950Stheraven __bit_iterator<_Dp, _IC> __last, 1219232950Stheraven __bit_iterator<_Dp, false> __result); 1220232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy_backward(__bit_iterator<_Dp, _IC> __first, 1221232950Stheraven __bit_iterator<_Dp, _IC> __last, 1222232950Stheraven __bit_iterator<_Dp, false> __result); 1223227825Stheraven template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_aligned(__bit_iterator<__C1, false>, 1224227825Stheraven __bit_iterator<__C1, false>, 1225227825Stheraven __bit_iterator<__C2, false>); 1226227825Stheraven template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_unaligned(__bit_iterator<__C1, false>, 1227227825Stheraven __bit_iterator<__C1, false>, 1228227825Stheraven __bit_iterator<__C2, false>); 1229227825Stheraven template <class __C1, class __C2>friend __bit_iterator<__C2, false> swap_ranges(__bit_iterator<__C1, false>, 1230227825Stheraven __bit_iterator<__C1, false>, 1231227825Stheraven __bit_iterator<__C2, false>); 1232232950Stheraven template <class _Dp> friend __bit_iterator<_Dp, false> rotate(__bit_iterator<_Dp, false>, 1233232950Stheraven __bit_iterator<_Dp, false>, 1234232950Stheraven __bit_iterator<_Dp, false>); 1235232950Stheraven template <class _Dp> friend bool __equal_aligned(__bit_iterator<_Dp, true>, 1236232950Stheraven __bit_iterator<_Dp, true>, 1237232950Stheraven __bit_iterator<_Dp, true>); 1238232950Stheraven template <class _Dp> friend bool __equal_unaligned(__bit_iterator<_Dp, true>, 1239232950Stheraven __bit_iterator<_Dp, true>, 1240232950Stheraven __bit_iterator<_Dp, true>); 1241232950Stheraven template <class _Dp, bool _IC1, bool _IC2> friend bool equal(__bit_iterator<_Dp, _IC1>, 1242232950Stheraven __bit_iterator<_Dp, _IC1>, 1243232950Stheraven __bit_iterator<_Dp, _IC2>); 1244232950Stheraven template <class _Dp> friend __bit_iterator<_Dp, false> __find_bool_true(__bit_iterator<_Dp, false>, 1245232950Stheraven typename _Dp::size_type); 1246232950Stheraven template <class _Dp> friend __bit_iterator<_Dp, false> __find_bool_false(__bit_iterator<_Dp, false>, 1247232950Stheraven typename _Dp::size_type); 1248227825Stheraven}; 1249227825Stheraven 1250227825Stheraven_LIBCPP_END_NAMESPACE_STD 1251227825Stheraven 1252227825Stheraven#endif // _LIBCPP___BIT_REFERENCE 1253