__bit_reference revision 249998
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 84249998Sdimtemplate <class _Cp> 85249998Sdim_LIBCPP_INLINE_VISIBILITY inline 86249998Sdimvoid 87249998Sdimswap(__bit_reference<_Cp> __x, __bit_reference<_Cp> __y) _NOEXCEPT 88249998Sdim{ 89249998Sdim bool __t = __x; 90249998Sdim __x = __y; 91249998Sdim __y = __t; 92249998Sdim} 93249998Sdim 94232950Stheraventemplate <class _Cp, class _Dp> 95227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 96227825Stheravenvoid 97232950Stheravenswap(__bit_reference<_Cp> __x, __bit_reference<_Dp> __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(__bit_reference<_Cp> __x, bool& __y) _NOEXCEPT 108227825Stheraven{ 109227825Stheraven bool __t = __x; 110227825Stheraven __x = __y; 111227825Stheraven __y = __t; 112227825Stheraven} 113227825Stheraven 114232950Stheraventemplate <class _Cp> 115227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 116227825Stheravenvoid 117232950Stheravenswap(bool& __x, __bit_reference<_Cp> __y) _NOEXCEPT 118227825Stheraven{ 119227825Stheraven bool __t = __x; 120227825Stheraven __x = __y; 121227825Stheraven __y = __t; 122227825Stheraven} 123227825Stheraven 124232950Stheraventemplate <class _Cp> 125227825Stheravenclass __bit_const_reference 126227825Stheraven{ 127232950Stheraven typedef typename _Cp::__storage_type __storage_type; 128232950Stheraven typedef typename _Cp::__const_storage_pointer __storage_pointer; 129227825Stheraven 130227825Stheraven __storage_pointer __seg_; 131227825Stheraven __storage_type __mask_; 132227825Stheraven 133227825Stheraven#if defined(__clang__) 134232950Stheraven friend typename _Cp::__self; 135227825Stheraven#else 136232950Stheraven friend class _Cp::__self; 137227825Stheraven#endif 138232950Stheraven friend class __bit_iterator<_Cp, true>; 139227825Stheravenpublic: 140227825Stheraven _LIBCPP_INLINE_VISIBILITY 141232950Stheraven __bit_const_reference(const __bit_reference<_Cp>& __x) _NOEXCEPT 142227825Stheraven : __seg_(__x.__seg_), __mask_(__x.__mask_) {} 143227825Stheraven 144241903Sdim _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR operator bool() const _NOEXCEPT 145227825Stheraven {return static_cast<bool>(*__seg_ & __mask_);} 146227825Stheraven 147232950Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, true> operator&() const _NOEXCEPT 148232950Stheraven {return __bit_iterator<_Cp, true>(__seg_, static_cast<unsigned>(__ctz(__mask_)));} 149227825Stheravenprivate: 150227825Stheraven _LIBCPP_INLINE_VISIBILITY 151241903Sdim _LIBCPP_CONSTEXPR 152227825Stheraven __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT 153227825Stheraven : __seg_(__s), __mask_(__m) {} 154227825Stheraven 155227825Stheraven __bit_const_reference& operator=(const __bit_const_reference& __x); 156227825Stheraven}; 157227825Stheraven 158227825Stheraven// find 159227825Stheraven 160241903Sdimtemplate <class _Cp, bool _IsConst> 161241903Sdim__bit_iterator<_Cp, _IsConst> 162241903Sdim__find_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 163227825Stheraven{ 164241903Sdim typedef __bit_iterator<_Cp, _IsConst> _It; 165227825Stheraven typedef typename _It::__storage_type __storage_type; 166227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 167227825Stheraven // do first partial word 168227825Stheraven if (__first.__ctz_ != 0) 169227825Stheraven { 170227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 171227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 172227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 173227825Stheraven __storage_type __b = *__first.__seg_ & __m; 174227825Stheraven if (__b) 175227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 176227825Stheraven __n -= __dn; 177227825Stheraven ++__first.__seg_; 178227825Stheraven } 179227825Stheraven // do middle whole words 180227825Stheraven for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 181227825Stheraven if (*__first.__seg_) 182227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(*__first.__seg_))); 183227825Stheraven // do last partial word 184227825Stheraven if (__n > 0) 185227825Stheraven { 186227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 187227825Stheraven __storage_type __b = *__first.__seg_ & __m; 188227825Stheraven if (__b) 189227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 190227825Stheraven } 191227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(__n)); 192227825Stheraven} 193227825Stheraven 194241903Sdimtemplate <class _Cp, bool _IsConst> 195241903Sdim__bit_iterator<_Cp, _IsConst> 196241903Sdim__find_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 197227825Stheraven{ 198241903Sdim typedef __bit_iterator<_Cp, _IsConst> _It; 199227825Stheraven typedef typename _It::__storage_type __storage_type; 200227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 201227825Stheraven // do first partial word 202227825Stheraven if (__first.__ctz_ != 0) 203227825Stheraven { 204227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 205227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 206227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 207241903Sdim __storage_type __b = ~*__first.__seg_ & __m; 208227825Stheraven if (__b) 209227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 210227825Stheraven __n -= __dn; 211227825Stheraven ++__first.__seg_; 212227825Stheraven } 213227825Stheraven // do middle whole words 214227825Stheraven for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 215227825Stheraven { 216227825Stheraven __storage_type __b = ~*__first.__seg_; 217227825Stheraven if (__b) 218227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 219227825Stheraven } 220227825Stheraven // do last partial word 221227825Stheraven if (__n > 0) 222227825Stheraven { 223227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 224241903Sdim __storage_type __b = ~*__first.__seg_ & __m; 225227825Stheraven if (__b) 226227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 227227825Stheraven } 228227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(__n)); 229227825Stheraven} 230227825Stheraven 231241903Sdimtemplate <class _Cp, bool _IsConst, class _Tp> 232227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 233241903Sdim__bit_iterator<_Cp, _IsConst> 234241903Sdimfind(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_) 235227825Stheraven{ 236227825Stheraven if (static_cast<bool>(__value_)) 237232950Stheraven return __find_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first)); 238232950Stheraven return __find_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first)); 239227825Stheraven} 240227825Stheraven 241227825Stheraven// count 242227825Stheraven 243241903Sdimtemplate <class _Cp, bool _IsConst> 244241903Sdimtypename __bit_iterator<_Cp, _IsConst>::difference_type 245241903Sdim__count_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 246227825Stheraven{ 247241903Sdim typedef __bit_iterator<_Cp, _IsConst> _It; 248227825Stheraven typedef typename _It::__storage_type __storage_type; 249227825Stheraven typedef typename _It::difference_type difference_type; 250227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 251227825Stheraven difference_type __r = 0; 252227825Stheraven // do first partial word 253227825Stheraven if (__first.__ctz_ != 0) 254227825Stheraven { 255227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 256227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 257227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 258227825Stheraven __r = _VSTD::__pop_count(*__first.__seg_ & __m); 259227825Stheraven __n -= __dn; 260227825Stheraven ++__first.__seg_; 261227825Stheraven } 262227825Stheraven // do middle whole words 263227825Stheraven for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 264227825Stheraven __r += _VSTD::__pop_count(*__first.__seg_); 265227825Stheraven // do last partial word 266227825Stheraven if (__n > 0) 267227825Stheraven { 268227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 269227825Stheraven __r += _VSTD::__pop_count(*__first.__seg_ & __m); 270227825Stheraven } 271227825Stheraven return __r; 272227825Stheraven} 273227825Stheraven 274241903Sdimtemplate <class _Cp, bool _IsConst> 275241903Sdimtypename __bit_iterator<_Cp, _IsConst>::difference_type 276241903Sdim__count_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 277227825Stheraven{ 278241903Sdim typedef __bit_iterator<_Cp, _IsConst> _It; 279227825Stheraven typedef typename _It::__storage_type __storage_type; 280227825Stheraven typedef typename _It::difference_type difference_type; 281227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 282227825Stheraven difference_type __r = 0; 283227825Stheraven // do first partial word 284227825Stheraven if (__first.__ctz_ != 0) 285227825Stheraven { 286227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 287227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 288227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 289241903Sdim __r = _VSTD::__pop_count(~*__first.__seg_ & __m); 290227825Stheraven __n -= __dn; 291227825Stheraven ++__first.__seg_; 292227825Stheraven } 293227825Stheraven // do middle whole words 294227825Stheraven for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 295227825Stheraven __r += _VSTD::__pop_count(~*__first.__seg_); 296227825Stheraven // do last partial word 297227825Stheraven if (__n > 0) 298227825Stheraven { 299227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 300241903Sdim __r += _VSTD::__pop_count(~*__first.__seg_ & __m); 301227825Stheraven } 302227825Stheraven return __r; 303227825Stheraven} 304227825Stheraven 305241903Sdimtemplate <class _Cp, bool _IsConst, class _Tp> 306227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 307241903Sdimtypename __bit_iterator<_Cp, _IsConst>::difference_type 308241903Sdimcount(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_) 309227825Stheraven{ 310227825Stheraven if (static_cast<bool>(__value_)) 311232950Stheraven return __count_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first)); 312232950Stheraven return __count_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first)); 313227825Stheraven} 314227825Stheraven 315227825Stheraven// fill_n 316227825Stheraven 317232950Stheraventemplate <class _Cp> 318227825Stheravenvoid 319232950Stheraven__fill_n_false(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) 320227825Stheraven{ 321232950Stheraven typedef __bit_iterator<_Cp, false> _It; 322227825Stheraven typedef typename _It::__storage_type __storage_type; 323227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 324227825Stheraven // do first partial word 325227825Stheraven if (__first.__ctz_ != 0) 326227825Stheraven { 327227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 328227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 329227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 330227825Stheraven *__first.__seg_ &= ~__m; 331227825Stheraven __n -= __dn; 332227825Stheraven ++__first.__seg_; 333227825Stheraven } 334227825Stheraven // do middle whole words 335227825Stheraven __storage_type __nw = __n / __bits_per_word; 336227825Stheraven _VSTD::memset(__first.__seg_, 0, __nw * sizeof(__storage_type)); 337227825Stheraven __n -= __nw * __bits_per_word; 338227825Stheraven // do last partial word 339227825Stheraven if (__n > 0) 340227825Stheraven { 341227825Stheraven __first.__seg_ += __nw; 342227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 343227825Stheraven *__first.__seg_ &= ~__m; 344227825Stheraven } 345227825Stheraven} 346227825Stheraven 347232950Stheraventemplate <class _Cp> 348227825Stheravenvoid 349232950Stheraven__fill_n_true(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) 350227825Stheraven{ 351232950Stheraven typedef __bit_iterator<_Cp, false> _It; 352227825Stheraven typedef typename _It::__storage_type __storage_type; 353227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 354227825Stheraven // do first partial word 355227825Stheraven if (__first.__ctz_ != 0) 356227825Stheraven { 357227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 358227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 359227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 360227825Stheraven *__first.__seg_ |= __m; 361227825Stheraven __n -= __dn; 362227825Stheraven ++__first.__seg_; 363227825Stheraven } 364227825Stheraven // do middle whole words 365227825Stheraven __storage_type __nw = __n / __bits_per_word; 366227825Stheraven _VSTD::memset(__first.__seg_, -1, __nw * sizeof(__storage_type)); 367227825Stheraven __n -= __nw * __bits_per_word; 368227825Stheraven // do last partial word 369227825Stheraven if (__n > 0) 370227825Stheraven { 371227825Stheraven __first.__seg_ += __nw; 372227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 373227825Stheraven *__first.__seg_ |= __m; 374227825Stheraven } 375227825Stheraven} 376227825Stheraven 377232950Stheraventemplate <class _Cp> 378227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 379227825Stheravenvoid 380232950Stheravenfill_n(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n, bool __value_) 381227825Stheraven{ 382227825Stheraven if (__n > 0) 383227825Stheraven { 384227825Stheraven if (__value_) 385227825Stheraven __fill_n_true(__first, __n); 386227825Stheraven else 387227825Stheraven __fill_n_false(__first, __n); 388227825Stheraven } 389227825Stheraven} 390227825Stheraven 391227825Stheraven// fill 392227825Stheraven 393232950Stheraventemplate <class _Cp> 394227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 395227825Stheravenvoid 396232950Stheravenfill(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __last, bool __value_) 397227825Stheraven{ 398232950Stheraven _VSTD::fill_n(__first, static_cast<typename _Cp::size_type>(__last - __first), __value_); 399227825Stheraven} 400227825Stheraven 401227825Stheraven// copy 402227825Stheraven 403232950Stheraventemplate <class _Cp, bool _IsConst> 404232950Stheraven__bit_iterator<_Cp, false> 405232950Stheraven__copy_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 406232950Stheraven __bit_iterator<_Cp, false> __result) 407227825Stheraven{ 408232950Stheraven typedef __bit_iterator<_Cp, _IsConst> _In; 409227825Stheraven typedef typename _In::difference_type difference_type; 410227825Stheraven typedef typename _In::__storage_type __storage_type; 411227825Stheraven static const unsigned __bits_per_word = _In::__bits_per_word; 412227825Stheraven difference_type __n = __last - __first; 413227825Stheraven if (__n > 0) 414227825Stheraven { 415227825Stheraven // do first word 416227825Stheraven if (__first.__ctz_ != 0) 417227825Stheraven { 418227825Stheraven unsigned __clz = __bits_per_word - __first.__ctz_; 419227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 420227825Stheraven __n -= __dn; 421227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 422227825Stheraven __storage_type __b = *__first.__seg_ & __m; 423227825Stheraven *__result.__seg_ &= ~__m; 424227825Stheraven *__result.__seg_ |= __b; 425227825Stheraven __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 426227825Stheraven __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 427227825Stheraven ++__first.__seg_; 428227825Stheraven // __first.__ctz_ = 0; 429227825Stheraven } 430227825Stheraven // __first.__ctz_ == 0; 431227825Stheraven // do middle words 432227825Stheraven __storage_type __nw = __n / __bits_per_word; 433227825Stheraven _VSTD::memmove(__result.__seg_, __first.__seg_, __nw * sizeof(__storage_type)); 434227825Stheraven __n -= __nw * __bits_per_word; 435227825Stheraven __result.__seg_ += __nw; 436227825Stheraven // do last word 437227825Stheraven if (__n > 0) 438227825Stheraven { 439227825Stheraven __first.__seg_ += __nw; 440227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 441227825Stheraven __storage_type __b = *__first.__seg_ & __m; 442227825Stheraven *__result.__seg_ &= ~__m; 443227825Stheraven *__result.__seg_ |= __b; 444227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 445227825Stheraven } 446227825Stheraven } 447227825Stheraven return __result; 448227825Stheraven} 449227825Stheraven 450232950Stheraventemplate <class _Cp, bool _IsConst> 451232950Stheraven__bit_iterator<_Cp, false> 452232950Stheraven__copy_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 453232950Stheraven __bit_iterator<_Cp, false> __result) 454227825Stheraven{ 455232950Stheraven typedef __bit_iterator<_Cp, _IsConst> _In; 456227825Stheraven typedef typename _In::difference_type difference_type; 457227825Stheraven typedef typename _In::__storage_type __storage_type; 458227825Stheraven static const unsigned __bits_per_word = _In::__bits_per_word; 459227825Stheraven difference_type __n = __last - __first; 460227825Stheraven if (__n > 0) 461227825Stheraven { 462227825Stheraven // do first word 463227825Stheraven if (__first.__ctz_ != 0) 464227825Stheraven { 465227825Stheraven unsigned __clz_f = __bits_per_word - __first.__ctz_; 466227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 467227825Stheraven __n -= __dn; 468227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 469227825Stheraven __storage_type __b = *__first.__seg_ & __m; 470227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 471227825Stheraven __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 472227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 473227825Stheraven *__result.__seg_ &= ~__m; 474227825Stheraven if (__result.__ctz_ > __first.__ctz_) 475227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_); 476227825Stheraven else 477227825Stheraven *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_); 478227825Stheraven __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 479227825Stheraven __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 480227825Stheraven __dn -= __ddn; 481227825Stheraven if (__dn > 0) 482227825Stheraven { 483227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __dn); 484227825Stheraven *__result.__seg_ &= ~__m; 485227825Stheraven *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn); 486227825Stheraven __result.__ctz_ = static_cast<unsigned>(__dn); 487227825Stheraven } 488227825Stheraven ++__first.__seg_; 489227825Stheraven // __first.__ctz_ = 0; 490227825Stheraven } 491227825Stheraven // __first.__ctz_ == 0; 492227825Stheraven // do middle words 493227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 494227825Stheraven __storage_type __m = ~__storage_type(0) << __result.__ctz_; 495227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 496227825Stheraven { 497227825Stheraven __storage_type __b = *__first.__seg_; 498227825Stheraven *__result.__seg_ &= ~__m; 499227825Stheraven *__result.__seg_ |= __b << __result.__ctz_; 500227825Stheraven ++__result.__seg_; 501227825Stheraven *__result.__seg_ &= __m; 502227825Stheraven *__result.__seg_ |= __b >> __clz_r; 503227825Stheraven } 504227825Stheraven // do last word 505227825Stheraven if (__n > 0) 506227825Stheraven { 507227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 508227825Stheraven __storage_type __b = *__first.__seg_ & __m; 509227825Stheraven __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); 510227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 511227825Stheraven *__result.__seg_ &= ~__m; 512227825Stheraven *__result.__seg_ |= __b << __result.__ctz_; 513227825Stheraven __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 514227825Stheraven __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 515227825Stheraven __n -= __dn; 516227825Stheraven if (__n > 0) 517227825Stheraven { 518227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 519227825Stheraven *__result.__seg_ &= ~__m; 520227825Stheraven *__result.__seg_ |= __b >> __dn; 521227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 522227825Stheraven } 523227825Stheraven } 524227825Stheraven } 525227825Stheraven return __result; 526227825Stheraven} 527227825Stheraven 528232950Stheraventemplate <class _Cp, bool _IsConst> 529227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 530232950Stheraven__bit_iterator<_Cp, false> 531232950Stheravencopy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 532227825Stheraven{ 533227825Stheraven if (__first.__ctz_ == __result.__ctz_) 534227825Stheraven return __copy_aligned(__first, __last, __result); 535227825Stheraven return __copy_unaligned(__first, __last, __result); 536227825Stheraven} 537227825Stheraven 538227825Stheraven// copy_backward 539227825Stheraven 540232950Stheraventemplate <class _Cp, bool _IsConst> 541232950Stheraven__bit_iterator<_Cp, false> 542232950Stheraven__copy_backward_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 543232950Stheraven __bit_iterator<_Cp, false> __result) 544227825Stheraven{ 545232950Stheraven typedef __bit_iterator<_Cp, _IsConst> _In; 546227825Stheraven typedef typename _In::difference_type difference_type; 547227825Stheraven typedef typename _In::__storage_type __storage_type; 548227825Stheraven static const unsigned __bits_per_word = _In::__bits_per_word; 549227825Stheraven difference_type __n = __last - __first; 550227825Stheraven if (__n > 0) 551227825Stheraven { 552227825Stheraven // do first word 553227825Stheraven if (__last.__ctz_ != 0) 554227825Stheraven { 555227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); 556227825Stheraven __n -= __dn; 557227825Stheraven unsigned __clz = __bits_per_word - __last.__ctz_; 558227825Stheraven __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz); 559227825Stheraven __storage_type __b = *__last.__seg_ & __m; 560227825Stheraven *__result.__seg_ &= ~__m; 561227825Stheraven *__result.__seg_ |= __b; 562227825Stheraven __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 563227825Stheraven __result.__ctz_) % __bits_per_word); 564227825Stheraven // __last.__ctz_ = 0 565227825Stheraven } 566227825Stheraven // __last.__ctz_ == 0 || __n == 0 567227825Stheraven // __result.__ctz_ == 0 || __n == 0 568227825Stheraven // do middle words 569227825Stheraven __storage_type __nw = __n / __bits_per_word; 570227825Stheraven __result.__seg_ -= __nw; 571227825Stheraven __last.__seg_ -= __nw; 572227825Stheraven _VSTD::memmove(__result.__seg_, __last.__seg_, __nw * sizeof(__storage_type)); 573227825Stheraven __n -= __nw * __bits_per_word; 574227825Stheraven // do last word 575227825Stheraven if (__n > 0) 576227825Stheraven { 577227825Stheraven __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n); 578227825Stheraven __storage_type __b = *--__last.__seg_ & __m; 579227825Stheraven *--__result.__seg_ &= ~__m; 580227825Stheraven *__result.__seg_ |= __b; 581227825Stheraven __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 582227825Stheraven } 583227825Stheraven } 584227825Stheraven return __result; 585227825Stheraven} 586227825Stheraven 587232950Stheraventemplate <class _Cp, bool _IsConst> 588232950Stheraven__bit_iterator<_Cp, false> 589232950Stheraven__copy_backward_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 590232950Stheraven __bit_iterator<_Cp, false> __result) 591227825Stheraven{ 592232950Stheraven typedef __bit_iterator<_Cp, _IsConst> _In; 593227825Stheraven typedef typename _In::difference_type difference_type; 594227825Stheraven typedef typename _In::__storage_type __storage_type; 595227825Stheraven static const unsigned __bits_per_word = _In::__bits_per_word; 596227825Stheraven difference_type __n = __last - __first; 597227825Stheraven if (__n > 0) 598227825Stheraven { 599227825Stheraven // do first word 600227825Stheraven if (__last.__ctz_ != 0) 601227825Stheraven { 602227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); 603227825Stheraven __n -= __dn; 604227825Stheraven unsigned __clz_l = __bits_per_word - __last.__ctz_; 605227825Stheraven __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l); 606227825Stheraven __storage_type __b = *__last.__seg_ & __m; 607227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 608227825Stheraven __storage_type __ddn = _VSTD::min(__dn, static_cast<difference_type>(__result.__ctz_)); 609227825Stheraven if (__ddn > 0) 610227825Stheraven { 611227825Stheraven __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r); 612227825Stheraven *__result.__seg_ &= ~__m; 613227825Stheraven if (__result.__ctz_ > __last.__ctz_) 614227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 615227825Stheraven else 616227825Stheraven *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_); 617227825Stheraven __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) + 618227825Stheraven __result.__ctz_) % __bits_per_word); 619227825Stheraven __dn -= __ddn; 620227825Stheraven } 621227825Stheraven if (__dn > 0) 622227825Stheraven { 623227825Stheraven // __result.__ctz_ == 0 624227825Stheraven --__result.__seg_; 625227825Stheraven __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1)); 626227825Stheraven __m = ~__storage_type(0) << __result.__ctz_; 627227825Stheraven *__result.__seg_ &= ~__m; 628227825Stheraven __last.__ctz_ -= __dn + __ddn; 629227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 630227825Stheraven } 631227825Stheraven // __last.__ctz_ = 0 632227825Stheraven } 633227825Stheraven // __last.__ctz_ == 0 || __n == 0 634227825Stheraven // __result.__ctz_ != 0 || __n == 0 635227825Stheraven // do middle words 636227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 637227825Stheraven __storage_type __m = ~__storage_type(0) >> __clz_r; 638227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word) 639227825Stheraven { 640227825Stheraven __storage_type __b = *--__last.__seg_; 641227825Stheraven *__result.__seg_ &= ~__m; 642227825Stheraven *__result.__seg_ |= __b >> __clz_r; 643227825Stheraven *--__result.__seg_ &= __m; 644227825Stheraven *__result.__seg_ |= __b << __result.__ctz_; 645227825Stheraven } 646227825Stheraven // do last word 647227825Stheraven if (__n > 0) 648227825Stheraven { 649227825Stheraven __m = ~__storage_type(0) << (__bits_per_word - __n); 650227825Stheraven __storage_type __b = *--__last.__seg_ & __m; 651232950Stheraven __clz_r = __bits_per_word - __result.__ctz_; 652227825Stheraven __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__result.__ctz_)); 653227825Stheraven __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r); 654227825Stheraven *__result.__seg_ &= ~__m; 655227825Stheraven *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_); 656227825Stheraven __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 657227825Stheraven __result.__ctz_) % __bits_per_word); 658227825Stheraven __n -= __dn; 659227825Stheraven if (__n > 0) 660227825Stheraven { 661227825Stheraven // __result.__ctz_ == 0 662227825Stheraven --__result.__seg_; 663227825Stheraven __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 664227825Stheraven __m = ~__storage_type(0) << __result.__ctz_; 665227825Stheraven *__result.__seg_ &= ~__m; 666227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn)); 667227825Stheraven } 668227825Stheraven } 669227825Stheraven } 670227825Stheraven return __result; 671227825Stheraven} 672227825Stheraven 673232950Stheraventemplate <class _Cp, bool _IsConst> 674227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 675232950Stheraven__bit_iterator<_Cp, false> 676232950Stheravencopy_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 677227825Stheraven{ 678227825Stheraven if (__last.__ctz_ == __result.__ctz_) 679227825Stheraven return __copy_backward_aligned(__first, __last, __result); 680227825Stheraven return __copy_backward_unaligned(__first, __last, __result); 681227825Stheraven} 682227825Stheraven 683227825Stheraven// move 684227825Stheraven 685232950Stheraventemplate <class _Cp, bool _IsConst> 686227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 687232950Stheraven__bit_iterator<_Cp, false> 688232950Stheravenmove(__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// move_backward 694227825Stheraven 695232950Stheraventemplate <class _Cp, bool _IsConst> 696227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 697232950Stheraven__bit_iterator<_Cp, false> 698232950Stheravenmove_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 699227825Stheraven{ 700227825Stheraven return _VSTD::copy(__first, __last, __result); 701227825Stheraven} 702227825Stheraven 703227825Stheraven// swap_ranges 704227825Stheraven 705227825Stheraventemplate <class __C1, class __C2> 706227825Stheraven__bit_iterator<__C2, false> 707227825Stheraven__swap_ranges_aligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, 708227825Stheraven __bit_iterator<__C2, false> __result) 709227825Stheraven{ 710227825Stheraven typedef __bit_iterator<__C1, false> _I1; 711227825Stheraven typedef typename _I1::difference_type difference_type; 712227825Stheraven typedef typename _I1::__storage_type __storage_type; 713227825Stheraven static const unsigned __bits_per_word = _I1::__bits_per_word; 714227825Stheraven difference_type __n = __last - __first; 715227825Stheraven if (__n > 0) 716227825Stheraven { 717227825Stheraven // do first word 718227825Stheraven if (__first.__ctz_ != 0) 719227825Stheraven { 720227825Stheraven unsigned __clz = __bits_per_word - __first.__ctz_; 721227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 722227825Stheraven __n -= __dn; 723227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 724227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 725227825Stheraven *__first.__seg_ &= ~__m; 726227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 727227825Stheraven *__result.__seg_ &= ~__m; 728227825Stheraven *__result.__seg_ |= __b1; 729227825Stheraven *__first.__seg_ |= __b2; 730227825Stheraven __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 731227825Stheraven __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 732227825Stheraven ++__first.__seg_; 733227825Stheraven // __first.__ctz_ = 0; 734227825Stheraven } 735227825Stheraven // __first.__ctz_ == 0; 736227825Stheraven // do middle words 737227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_) 738227825Stheraven swap(*__first.__seg_, *__result.__seg_); 739227825Stheraven // do last word 740227825Stheraven if (__n > 0) 741227825Stheraven { 742227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 743227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 744227825Stheraven *__first.__seg_ &= ~__m; 745227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 746227825Stheraven *__result.__seg_ &= ~__m; 747227825Stheraven *__result.__seg_ |= __b1; 748227825Stheraven *__first.__seg_ |= __b2; 749227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 750227825Stheraven } 751227825Stheraven } 752227825Stheraven return __result; 753227825Stheraven} 754227825Stheraven 755227825Stheraventemplate <class __C1, class __C2> 756227825Stheraven__bit_iterator<__C2, false> 757227825Stheraven__swap_ranges_unaligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, 758227825Stheraven __bit_iterator<__C2, false> __result) 759227825Stheraven{ 760227825Stheraven typedef __bit_iterator<__C1, false> _I1; 761227825Stheraven typedef typename _I1::difference_type difference_type; 762227825Stheraven typedef typename _I1::__storage_type __storage_type; 763227825Stheraven static const unsigned __bits_per_word = _I1::__bits_per_word; 764227825Stheraven difference_type __n = __last - __first; 765227825Stheraven if (__n > 0) 766227825Stheraven { 767227825Stheraven // do first word 768227825Stheraven if (__first.__ctz_ != 0) 769227825Stheraven { 770227825Stheraven unsigned __clz_f = __bits_per_word - __first.__ctz_; 771227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 772227825Stheraven __n -= __dn; 773227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 774227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 775227825Stheraven *__first.__seg_ &= ~__m; 776227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 777227825Stheraven __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 778227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 779227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 780227825Stheraven *__result.__seg_ &= ~__m; 781227825Stheraven if (__result.__ctz_ > __first.__ctz_) 782227825Stheraven { 783227825Stheraven unsigned __s = __result.__ctz_ - __first.__ctz_; 784227825Stheraven *__result.__seg_ |= __b1 << __s; 785227825Stheraven *__first.__seg_ |= __b2 >> __s; 786227825Stheraven } 787227825Stheraven else 788227825Stheraven { 789227825Stheraven unsigned __s = __first.__ctz_ - __result.__ctz_; 790227825Stheraven *__result.__seg_ |= __b1 >> __s; 791227825Stheraven *__first.__seg_ |= __b2 << __s; 792227825Stheraven } 793227825Stheraven __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 794227825Stheraven __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 795227825Stheraven __dn -= __ddn; 796227825Stheraven if (__dn > 0) 797227825Stheraven { 798227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __dn); 799227825Stheraven __b2 = *__result.__seg_ & __m; 800227825Stheraven *__result.__seg_ &= ~__m; 801227825Stheraven unsigned __s = __first.__ctz_ + __ddn; 802227825Stheraven *__result.__seg_ |= __b1 >> __s; 803227825Stheraven *__first.__seg_ |= __b2 << __s; 804227825Stheraven __result.__ctz_ = static_cast<unsigned>(__dn); 805227825Stheraven } 806227825Stheraven ++__first.__seg_; 807227825Stheraven // __first.__ctz_ = 0; 808227825Stheraven } 809227825Stheraven // __first.__ctz_ == 0; 810227825Stheraven // do middle words 811227825Stheraven __storage_type __m = ~__storage_type(0) << __result.__ctz_; 812227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 813227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 814227825Stheraven { 815227825Stheraven __storage_type __b1 = *__first.__seg_; 816227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 817227825Stheraven *__result.__seg_ &= ~__m; 818227825Stheraven *__result.__seg_ |= __b1 << __result.__ctz_; 819227825Stheraven *__first.__seg_ = __b2 >> __result.__ctz_; 820227825Stheraven ++__result.__seg_; 821227825Stheraven __b2 = *__result.__seg_ & ~__m; 822227825Stheraven *__result.__seg_ &= __m; 823227825Stheraven *__result.__seg_ |= __b1 >> __clz_r; 824227825Stheraven *__first.__seg_ |= __b2 << __clz_r; 825227825Stheraven } 826227825Stheraven // do last word 827227825Stheraven if (__n > 0) 828227825Stheraven { 829227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 830227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 831227825Stheraven *__first.__seg_ &= ~__m; 832227825Stheraven __storage_type __dn = _VSTD::min<__storage_type>(__n, __clz_r); 833227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 834227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 835227825Stheraven *__result.__seg_ &= ~__m; 836227825Stheraven *__result.__seg_ |= __b1 << __result.__ctz_; 837227825Stheraven *__first.__seg_ |= __b2 >> __result.__ctz_; 838227825Stheraven __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 839227825Stheraven __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 840227825Stheraven __n -= __dn; 841227825Stheraven if (__n > 0) 842227825Stheraven { 843227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 844227825Stheraven __b2 = *__result.__seg_ & __m; 845227825Stheraven *__result.__seg_ &= ~__m; 846227825Stheraven *__result.__seg_ |= __b1 >> __dn; 847227825Stheraven *__first.__seg_ |= __b2 << __dn; 848227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 849227825Stheraven } 850227825Stheraven } 851227825Stheraven } 852227825Stheraven return __result; 853227825Stheraven} 854227825Stheraven 855227825Stheraventemplate <class __C1, class __C2> 856227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 857227825Stheraven__bit_iterator<__C2, false> 858227825Stheravenswap_ranges(__bit_iterator<__C1, false> __first1, __bit_iterator<__C1, false> __last1, 859227825Stheraven __bit_iterator<__C2, false> __first2) 860227825Stheraven{ 861227825Stheraven if (__first1.__ctz_ == __first2.__ctz_) 862227825Stheraven return __swap_ranges_aligned(__first1, __last1, __first2); 863227825Stheraven return __swap_ranges_unaligned(__first1, __last1, __first2); 864227825Stheraven} 865227825Stheraven 866227825Stheraven// rotate 867227825Stheraven 868232950Stheraventemplate <class _Cp> 869227825Stheravenstruct __bit_array 870227825Stheraven{ 871232950Stheraven typedef typename _Cp::difference_type difference_type; 872232950Stheraven typedef typename _Cp::__storage_type __storage_type; 873232950Stheraven typedef typename _Cp::iterator iterator; 874232950Stheraven static const unsigned __bits_per_word = _Cp::__bits_per_word; 875232950Stheraven static const unsigned _Np = 4; 876227825Stheraven 877227825Stheraven difference_type __size_; 878232950Stheraven __storage_type __word_[_Np]; 879227825Stheraven 880227825Stheraven _LIBCPP_INLINE_VISIBILITY static difference_type capacity() 881232950Stheraven {return static_cast<difference_type>(_Np * __bits_per_word);} 882227825Stheraven _LIBCPP_INLINE_VISIBILITY explicit __bit_array(difference_type __s) : __size_(__s) {} 883227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator begin() {return iterator(__word_, 0);} 884227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator end() {return iterator(__word_ + __size_ / __bits_per_word, 885227825Stheraven static_cast<unsigned>(__size_ % __bits_per_word));} 886227825Stheraven}; 887227825Stheraven 888232950Stheraventemplate <class _Cp> 889232950Stheraven__bit_iterator<_Cp, false> 890232950Stheravenrotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last) 891227825Stheraven{ 892232950Stheraven typedef __bit_iterator<_Cp, false> _I1; 893227825Stheraven typedef typename _I1::difference_type difference_type; 894227825Stheraven typedef typename _I1::__storage_type __storage_type; 895227825Stheraven difference_type __d1 = __middle - __first; 896227825Stheraven difference_type __d2 = __last - __middle; 897227825Stheraven _I1 __r = __first + __d2; 898227825Stheraven while (__d1 != 0 && __d2 != 0) 899227825Stheraven { 900227825Stheraven if (__d1 <= __d2) 901227825Stheraven { 902232950Stheraven if (__d1 <= __bit_array<_Cp>::capacity()) 903227825Stheraven { 904232950Stheraven __bit_array<_Cp> __b(__d1); 905227825Stheraven _VSTD::copy(__first, __middle, __b.begin()); 906227825Stheraven _VSTD::copy(__b.begin(), __b.end(), _VSTD::copy(__middle, __last, __first)); 907227825Stheraven break; 908227825Stheraven } 909227825Stheraven else 910227825Stheraven { 911232950Stheraven __bit_iterator<_Cp, false> __mp = _VSTD::swap_ranges(__first, __middle, __middle); 912227825Stheraven __first = __middle; 913227825Stheraven __middle = __mp; 914227825Stheraven __d2 -= __d1; 915227825Stheraven } 916227825Stheraven } 917227825Stheraven else 918227825Stheraven { 919232950Stheraven if (__d2 <= __bit_array<_Cp>::capacity()) 920227825Stheraven { 921232950Stheraven __bit_array<_Cp> __b(__d2); 922227825Stheraven _VSTD::copy(__middle, __last, __b.begin()); 923227825Stheraven _VSTD::copy_backward(__b.begin(), __b.end(), _VSTD::copy_backward(__first, __middle, __last)); 924227825Stheraven break; 925227825Stheraven } 926227825Stheraven else 927227825Stheraven { 928232950Stheraven __bit_iterator<_Cp, false> __mp = __first + __d2; 929227825Stheraven _VSTD::swap_ranges(__first, __mp, __middle); 930227825Stheraven __first = __mp; 931227825Stheraven __d1 -= __d2; 932227825Stheraven } 933227825Stheraven } 934227825Stheraven } 935227825Stheraven return __r; 936227825Stheraven} 937227825Stheraven 938227825Stheraven// equal 939227825Stheraven 940241903Sdimtemplate <class _Cp, bool _IC1, bool _IC2> 941227825Stheravenbool 942241903Sdim__equal_unaligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, 943241903Sdim __bit_iterator<_Cp, _IC2> __first2) 944227825Stheraven{ 945241903Sdim typedef __bit_iterator<_Cp, _IC1> _It; 946227825Stheraven typedef typename _It::difference_type difference_type; 947227825Stheraven typedef typename _It::__storage_type __storage_type; 948227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 949227825Stheraven difference_type __n = __last1 - __first1; 950227825Stheraven if (__n > 0) 951227825Stheraven { 952227825Stheraven // do first word 953227825Stheraven if (__first1.__ctz_ != 0) 954227825Stheraven { 955227825Stheraven unsigned __clz_f = __bits_per_word - __first1.__ctz_; 956227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 957227825Stheraven __n -= __dn; 958227825Stheraven __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 959227825Stheraven __storage_type __b = *__first1.__seg_ & __m; 960227825Stheraven unsigned __clz_r = __bits_per_word - __first2.__ctz_; 961227825Stheraven __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 962227825Stheraven __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 963227825Stheraven if (__first2.__ctz_ > __first1.__ctz_) 964236387Sdim { 965227825Stheraven if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_))) 966227825Stheraven return false; 967236387Sdim } 968227825Stheraven else 969236387Sdim { 970227825Stheraven if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_))) 971227825Stheraven return false; 972236387Sdim } 973227825Stheraven __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word; 974227825Stheraven __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word); 975227825Stheraven __dn -= __ddn; 976227825Stheraven if (__dn > 0) 977227825Stheraven { 978227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __dn); 979227825Stheraven if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn))) 980227825Stheraven return false; 981227825Stheraven __first2.__ctz_ = static_cast<unsigned>(__dn); 982227825Stheraven } 983227825Stheraven ++__first1.__seg_; 984227825Stheraven // __first1.__ctz_ = 0; 985227825Stheraven } 986227825Stheraven // __first1.__ctz_ == 0; 987227825Stheraven // do middle words 988227825Stheraven unsigned __clz_r = __bits_per_word - __first2.__ctz_; 989227825Stheraven __storage_type __m = ~__storage_type(0) << __first2.__ctz_; 990227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_) 991227825Stheraven { 992227825Stheraven __storage_type __b = *__first1.__seg_; 993227825Stheraven if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 994227825Stheraven return false; 995227825Stheraven ++__first2.__seg_; 996227825Stheraven if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r)) 997227825Stheraven return false; 998227825Stheraven } 999227825Stheraven // do last word 1000227825Stheraven if (__n > 0) 1001227825Stheraven { 1002227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 1003227825Stheraven __storage_type __b = *__first1.__seg_ & __m; 1004227825Stheraven __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); 1005227825Stheraven __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 1006227825Stheraven if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 1007227825Stheraven return false; 1008227825Stheraven __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word; 1009227825Stheraven __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word); 1010227825Stheraven __n -= __dn; 1011227825Stheraven if (__n > 0) 1012227825Stheraven { 1013227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 1014227825Stheraven if ((*__first2.__seg_ & __m) != (__b >> __dn)) 1015227825Stheraven return false; 1016227825Stheraven } 1017227825Stheraven } 1018227825Stheraven } 1019227825Stheraven return true; 1020227825Stheraven} 1021227825Stheraven 1022241903Sdimtemplate <class _Cp, bool _IC1, bool _IC2> 1023227825Stheravenbool 1024241903Sdim__equal_aligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, 1025241903Sdim __bit_iterator<_Cp, _IC2> __first2) 1026227825Stheraven{ 1027241903Sdim typedef __bit_iterator<_Cp, _IC1> _It; 1028227825Stheraven typedef typename _It::difference_type difference_type; 1029227825Stheraven typedef typename _It::__storage_type __storage_type; 1030227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 1031227825Stheraven difference_type __n = __last1 - __first1; 1032227825Stheraven if (__n > 0) 1033227825Stheraven { 1034227825Stheraven // do first word 1035227825Stheraven if (__first1.__ctz_ != 0) 1036227825Stheraven { 1037227825Stheraven unsigned __clz = __bits_per_word - __first1.__ctz_; 1038227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 1039227825Stheraven __n -= __dn; 1040227825Stheraven __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 1041227825Stheraven if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 1042227825Stheraven return false; 1043227825Stheraven ++__first2.__seg_; 1044227825Stheraven ++__first1.__seg_; 1045227825Stheraven // __first1.__ctz_ = 0; 1046227825Stheraven // __first2.__ctz_ = 0; 1047227825Stheraven } 1048227825Stheraven // __first1.__ctz_ == 0; 1049227825Stheraven // __first2.__ctz_ == 0; 1050227825Stheraven // do middle words 1051227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_) 1052227825Stheraven if (*__first2.__seg_ != *__first1.__seg_) 1053227825Stheraven return false; 1054227825Stheraven // do last word 1055227825Stheraven if (__n > 0) 1056227825Stheraven { 1057227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 1058227825Stheraven if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 1059227825Stheraven return false; 1060227825Stheraven } 1061227825Stheraven } 1062227825Stheraven return true; 1063227825Stheraven} 1064227825Stheraven 1065232950Stheraventemplate <class _Cp, bool _IC1, bool _IC2> 1066227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1067227825Stheravenbool 1068232950Stheravenequal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) 1069227825Stheraven{ 1070227825Stheraven if (__first1.__ctz_ == __first2.__ctz_) 1071227825Stheraven return __equal_aligned(__first1, __last1, __first2); 1072227825Stheraven return __equal_unaligned(__first1, __last1, __first2); 1073227825Stheraven} 1074227825Stheraven 1075241903Sdimtemplate <class _Cp, bool _IsConst, 1076241903Sdim typename _Cp::__storage_type> 1077227825Stheravenclass __bit_iterator 1078227825Stheraven{ 1079227825Stheravenpublic: 1080232950Stheraven typedef typename _Cp::difference_type difference_type; 1081227825Stheraven typedef bool value_type; 1082227825Stheraven typedef __bit_iterator pointer; 1083232950Stheraven typedef typename conditional<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >::type reference; 1084227825Stheraven typedef random_access_iterator_tag iterator_category; 1085227825Stheraven 1086227825Stheravenprivate: 1087232950Stheraven typedef typename _Cp::__storage_type __storage_type; 1088232950Stheraven typedef typename conditional<_IsConst, typename _Cp::__const_storage_pointer, 1089232950Stheraven typename _Cp::__storage_pointer>::type __storage_pointer; 1090232950Stheraven static const unsigned __bits_per_word = _Cp::__bits_per_word; 1091227825Stheraven 1092227825Stheraven __storage_pointer __seg_; 1093227825Stheraven unsigned __ctz_; 1094227825Stheraven 1095227825Stheravenpublic: 1096227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator() _NOEXCEPT {} 1097227825Stheraven 1098227825Stheraven _LIBCPP_INLINE_VISIBILITY 1099232950Stheraven __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT 1100227825Stheraven : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {} 1101227825Stheraven 1102227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT 1103227825Stheraven {return reference(__seg_, __storage_type(1) << __ctz_);} 1104227825Stheraven 1105227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator++() 1106227825Stheraven { 1107227825Stheraven if (__ctz_ != __bits_per_word-1) 1108227825Stheraven ++__ctz_; 1109227825Stheraven else 1110227825Stheraven { 1111227825Stheraven __ctz_ = 0; 1112227825Stheraven ++__seg_; 1113227825Stheraven } 1114227825Stheraven return *this; 1115227825Stheraven } 1116227825Stheraven 1117227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator operator++(int) 1118227825Stheraven { 1119227825Stheraven __bit_iterator __tmp = *this; 1120227825Stheraven ++(*this); 1121227825Stheraven return __tmp; 1122227825Stheraven } 1123227825Stheraven 1124227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator--() 1125227825Stheraven { 1126227825Stheraven if (__ctz_ != 0) 1127227825Stheraven --__ctz_; 1128227825Stheraven else 1129227825Stheraven { 1130227825Stheraven __ctz_ = __bits_per_word - 1; 1131227825Stheraven --__seg_; 1132227825Stheraven } 1133227825Stheraven return *this; 1134227825Stheraven } 1135227825Stheraven 1136227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator operator--(int) 1137227825Stheraven { 1138227825Stheraven __bit_iterator __tmp = *this; 1139227825Stheraven --(*this); 1140227825Stheraven return __tmp; 1141227825Stheraven } 1142227825Stheraven 1143227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator+=(difference_type __n) 1144227825Stheraven { 1145227825Stheraven if (__n >= 0) 1146227825Stheraven __seg_ += (__n + __ctz_) / __bits_per_word; 1147227825Stheraven else 1148227825Stheraven __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1) 1149227825Stheraven / static_cast<difference_type>(__bits_per_word); 1150227825Stheraven __n &= (__bits_per_word - 1); 1151227825Stheraven __ctz_ = static_cast<unsigned>((__n + __ctz_) % __bits_per_word); 1152227825Stheraven return *this; 1153227825Stheraven } 1154227825Stheraven 1155227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator-=(difference_type __n) 1156227825Stheraven { 1157227825Stheraven return *this += -__n; 1158227825Stheraven } 1159227825Stheraven 1160227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator operator+(difference_type __n) const 1161227825Stheraven { 1162227825Stheraven __bit_iterator __t(*this); 1163227825Stheraven __t += __n; 1164227825Stheraven return __t; 1165227825Stheraven } 1166227825Stheraven 1167227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator operator-(difference_type __n) const 1168227825Stheraven { 1169227825Stheraven __bit_iterator __t(*this); 1170227825Stheraven __t -= __n; 1171227825Stheraven return __t; 1172227825Stheraven } 1173227825Stheraven 1174227825Stheraven _LIBCPP_INLINE_VISIBILITY 1175227825Stheraven friend __bit_iterator operator+(difference_type __n, const __bit_iterator& __it) {return __it + __n;} 1176227825Stheraven 1177227825Stheraven _LIBCPP_INLINE_VISIBILITY 1178227825Stheraven friend difference_type operator-(const __bit_iterator& __x, const __bit_iterator& __y) 1179227825Stheraven {return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;} 1180227825Stheraven 1181227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const {return *(*this + __n);} 1182227825Stheraven 1183227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator==(const __bit_iterator& __x, const __bit_iterator& __y) 1184227825Stheraven {return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;} 1185227825Stheraven 1186227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator!=(const __bit_iterator& __x, const __bit_iterator& __y) 1187227825Stheraven {return !(__x == __y);} 1188227825Stheraven 1189227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator<(const __bit_iterator& __x, const __bit_iterator& __y) 1190227825Stheraven {return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);} 1191227825Stheraven 1192227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator>(const __bit_iterator& __x, const __bit_iterator& __y) 1193227825Stheraven {return __y < __x;} 1194227825Stheraven 1195227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y) 1196227825Stheraven {return !(__y < __x);} 1197227825Stheraven 1198227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y) 1199227825Stheraven {return !(__x < __y);} 1200227825Stheraven 1201227825Stheravenprivate: 1202227825Stheraven _LIBCPP_INLINE_VISIBILITY 1203227825Stheraven __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT 1204227825Stheraven : __seg_(__s), __ctz_(__ctz) {} 1205227825Stheraven 1206227825Stheraven#if defined(__clang__) 1207232950Stheraven friend typename _Cp::__self; 1208227825Stheraven#else 1209232950Stheraven friend class _Cp::__self; 1210227825Stheraven#endif 1211232950Stheraven friend class __bit_reference<_Cp>; 1212232950Stheraven friend class __bit_const_reference<_Cp>; 1213232950Stheraven friend class __bit_iterator<_Cp, true>; 1214232950Stheraven template <class _Dp> friend struct __bit_array; 1215232950Stheraven template <class _Dp> friend void __fill_n_false(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); 1216232950Stheraven template <class _Dp> friend void __fill_n_true(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); 1217232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_aligned(__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_unaligned(__bit_iterator<_Dp, _IC> __first, 1221232950Stheraven __bit_iterator<_Dp, _IC> __last, 1222232950Stheraven __bit_iterator<_Dp, false> __result); 1223232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy(__bit_iterator<_Dp, _IC> __first, 1224232950Stheraven __bit_iterator<_Dp, _IC> __last, 1225232950Stheraven __bit_iterator<_Dp, false> __result); 1226232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_aligned(__bit_iterator<_Dp, _IC> __first, 1227232950Stheraven __bit_iterator<_Dp, _IC> __last, 1228232950Stheraven __bit_iterator<_Dp, false> __result); 1229232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_unaligned(__bit_iterator<_Dp, _IC> __first, 1230232950Stheraven __bit_iterator<_Dp, _IC> __last, 1231232950Stheraven __bit_iterator<_Dp, false> __result); 1232232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy_backward(__bit_iterator<_Dp, _IC> __first, 1233232950Stheraven __bit_iterator<_Dp, _IC> __last, 1234232950Stheraven __bit_iterator<_Dp, false> __result); 1235227825Stheraven template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_aligned(__bit_iterator<__C1, false>, 1236227825Stheraven __bit_iterator<__C1, false>, 1237227825Stheraven __bit_iterator<__C2, false>); 1238227825Stheraven template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_unaligned(__bit_iterator<__C1, false>, 1239227825Stheraven __bit_iterator<__C1, false>, 1240227825Stheraven __bit_iterator<__C2, false>); 1241227825Stheraven template <class __C1, class __C2>friend __bit_iterator<__C2, false> swap_ranges(__bit_iterator<__C1, false>, 1242227825Stheraven __bit_iterator<__C1, false>, 1243227825Stheraven __bit_iterator<__C2, false>); 1244232950Stheraven template <class _Dp> friend __bit_iterator<_Dp, false> rotate(__bit_iterator<_Dp, false>, 1245232950Stheraven __bit_iterator<_Dp, false>, 1246232950Stheraven __bit_iterator<_Dp, false>); 1247241903Sdim template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_aligned(__bit_iterator<_Dp, _IC1>, 1248241903Sdim __bit_iterator<_Dp, _IC1>, 1249241903Sdim __bit_iterator<_Dp, _IC2>); 1250241903Sdim template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_unaligned(__bit_iterator<_Dp, _IC1>, 1251241903Sdim __bit_iterator<_Dp, _IC1>, 1252241903Sdim __bit_iterator<_Dp, _IC2>); 1253232950Stheraven template <class _Dp, bool _IC1, bool _IC2> friend bool equal(__bit_iterator<_Dp, _IC1>, 1254232950Stheraven __bit_iterator<_Dp, _IC1>, 1255232950Stheraven __bit_iterator<_Dp, _IC2>); 1256241903Sdim template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_true(__bit_iterator<_Dp, _IC>, 1257232950Stheraven typename _Dp::size_type); 1258241903Sdim template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_false(__bit_iterator<_Dp, _IC>, 1259232950Stheraven typename _Dp::size_type); 1260241903Sdim template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type 1261241903Sdim __count_bool_true(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 1262241903Sdim template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type 1263241903Sdim __count_bool_false(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 1264227825Stheraven}; 1265227825Stheraven 1266227825Stheraven_LIBCPP_END_NAMESPACE_STD 1267227825Stheraven 1268227825Stheraven#endif // _LIBCPP___BIT_REFERENCE 1269