__bit_reference revision 253159
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; 336253159Stheraven _VSTD::memset(_VSTD::__to_raw_pointer(__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; 366253159Stheraven _VSTD::memset(_VSTD::__to_raw_pointer(__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; 433253159Stheraven _VSTD::memmove(_VSTD::__to_raw_pointer(__result.__seg_), 434253159Stheraven _VSTD::__to_raw_pointer(__first.__seg_), 435253159Stheraven __nw * sizeof(__storage_type)); 436227825Stheraven __n -= __nw * __bits_per_word; 437227825Stheraven __result.__seg_ += __nw; 438227825Stheraven // do last word 439227825Stheraven if (__n > 0) 440227825Stheraven { 441227825Stheraven __first.__seg_ += __nw; 442227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 443227825Stheraven __storage_type __b = *__first.__seg_ & __m; 444227825Stheraven *__result.__seg_ &= ~__m; 445227825Stheraven *__result.__seg_ |= __b; 446227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 447227825Stheraven } 448227825Stheraven } 449227825Stheraven return __result; 450227825Stheraven} 451227825Stheraven 452232950Stheraventemplate <class _Cp, bool _IsConst> 453232950Stheraven__bit_iterator<_Cp, false> 454232950Stheraven__copy_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 455232950Stheraven __bit_iterator<_Cp, false> __result) 456227825Stheraven{ 457232950Stheraven typedef __bit_iterator<_Cp, _IsConst> _In; 458227825Stheraven typedef typename _In::difference_type difference_type; 459227825Stheraven typedef typename _In::__storage_type __storage_type; 460227825Stheraven static const unsigned __bits_per_word = _In::__bits_per_word; 461227825Stheraven difference_type __n = __last - __first; 462227825Stheraven if (__n > 0) 463227825Stheraven { 464227825Stheraven // do first word 465227825Stheraven if (__first.__ctz_ != 0) 466227825Stheraven { 467227825Stheraven unsigned __clz_f = __bits_per_word - __first.__ctz_; 468227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 469227825Stheraven __n -= __dn; 470227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 471227825Stheraven __storage_type __b = *__first.__seg_ & __m; 472227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 473227825Stheraven __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 474227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 475227825Stheraven *__result.__seg_ &= ~__m; 476227825Stheraven if (__result.__ctz_ > __first.__ctz_) 477227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_); 478227825Stheraven else 479227825Stheraven *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_); 480227825Stheraven __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 481227825Stheraven __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 482227825Stheraven __dn -= __ddn; 483227825Stheraven if (__dn > 0) 484227825Stheraven { 485227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __dn); 486227825Stheraven *__result.__seg_ &= ~__m; 487227825Stheraven *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn); 488227825Stheraven __result.__ctz_ = static_cast<unsigned>(__dn); 489227825Stheraven } 490227825Stheraven ++__first.__seg_; 491227825Stheraven // __first.__ctz_ = 0; 492227825Stheraven } 493227825Stheraven // __first.__ctz_ == 0; 494227825Stheraven // do middle words 495227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 496227825Stheraven __storage_type __m = ~__storage_type(0) << __result.__ctz_; 497227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 498227825Stheraven { 499227825Stheraven __storage_type __b = *__first.__seg_; 500227825Stheraven *__result.__seg_ &= ~__m; 501227825Stheraven *__result.__seg_ |= __b << __result.__ctz_; 502227825Stheraven ++__result.__seg_; 503227825Stheraven *__result.__seg_ &= __m; 504227825Stheraven *__result.__seg_ |= __b >> __clz_r; 505227825Stheraven } 506227825Stheraven // do last word 507227825Stheraven if (__n > 0) 508227825Stheraven { 509227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 510227825Stheraven __storage_type __b = *__first.__seg_ & __m; 511227825Stheraven __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); 512227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 513227825Stheraven *__result.__seg_ &= ~__m; 514227825Stheraven *__result.__seg_ |= __b << __result.__ctz_; 515227825Stheraven __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 516227825Stheraven __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 517227825Stheraven __n -= __dn; 518227825Stheraven if (__n > 0) 519227825Stheraven { 520227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 521227825Stheraven *__result.__seg_ &= ~__m; 522227825Stheraven *__result.__seg_ |= __b >> __dn; 523227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 524227825Stheraven } 525227825Stheraven } 526227825Stheraven } 527227825Stheraven return __result; 528227825Stheraven} 529227825Stheraven 530232950Stheraventemplate <class _Cp, bool _IsConst> 531227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 532232950Stheraven__bit_iterator<_Cp, false> 533232950Stheravencopy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 534227825Stheraven{ 535227825Stheraven if (__first.__ctz_ == __result.__ctz_) 536227825Stheraven return __copy_aligned(__first, __last, __result); 537227825Stheraven return __copy_unaligned(__first, __last, __result); 538227825Stheraven} 539227825Stheraven 540227825Stheraven// copy_backward 541227825Stheraven 542232950Stheraventemplate <class _Cp, bool _IsConst> 543232950Stheraven__bit_iterator<_Cp, false> 544232950Stheraven__copy_backward_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 545232950Stheraven __bit_iterator<_Cp, false> __result) 546227825Stheraven{ 547232950Stheraven typedef __bit_iterator<_Cp, _IsConst> _In; 548227825Stheraven typedef typename _In::difference_type difference_type; 549227825Stheraven typedef typename _In::__storage_type __storage_type; 550227825Stheraven static const unsigned __bits_per_word = _In::__bits_per_word; 551227825Stheraven difference_type __n = __last - __first; 552227825Stheraven if (__n > 0) 553227825Stheraven { 554227825Stheraven // do first word 555227825Stheraven if (__last.__ctz_ != 0) 556227825Stheraven { 557227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); 558227825Stheraven __n -= __dn; 559227825Stheraven unsigned __clz = __bits_per_word - __last.__ctz_; 560227825Stheraven __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz); 561227825Stheraven __storage_type __b = *__last.__seg_ & __m; 562227825Stheraven *__result.__seg_ &= ~__m; 563227825Stheraven *__result.__seg_ |= __b; 564227825Stheraven __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 565227825Stheraven __result.__ctz_) % __bits_per_word); 566227825Stheraven // __last.__ctz_ = 0 567227825Stheraven } 568227825Stheraven // __last.__ctz_ == 0 || __n == 0 569227825Stheraven // __result.__ctz_ == 0 || __n == 0 570227825Stheraven // do middle words 571227825Stheraven __storage_type __nw = __n / __bits_per_word; 572227825Stheraven __result.__seg_ -= __nw; 573227825Stheraven __last.__seg_ -= __nw; 574253159Stheraven _VSTD::memmove(_VSTD::__to_raw_pointer(__result.__seg_), 575253159Stheraven _VSTD::__to_raw_pointer(__last.__seg_), 576253159Stheraven __nw * sizeof(__storage_type)); 577227825Stheraven __n -= __nw * __bits_per_word; 578227825Stheraven // do last word 579227825Stheraven if (__n > 0) 580227825Stheraven { 581227825Stheraven __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n); 582227825Stheraven __storage_type __b = *--__last.__seg_ & __m; 583227825Stheraven *--__result.__seg_ &= ~__m; 584227825Stheraven *__result.__seg_ |= __b; 585227825Stheraven __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 586227825Stheraven } 587227825Stheraven } 588227825Stheraven return __result; 589227825Stheraven} 590227825Stheraven 591232950Stheraventemplate <class _Cp, bool _IsConst> 592232950Stheraven__bit_iterator<_Cp, false> 593232950Stheraven__copy_backward_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 594232950Stheraven __bit_iterator<_Cp, false> __result) 595227825Stheraven{ 596232950Stheraven typedef __bit_iterator<_Cp, _IsConst> _In; 597227825Stheraven typedef typename _In::difference_type difference_type; 598227825Stheraven typedef typename _In::__storage_type __storage_type; 599227825Stheraven static const unsigned __bits_per_word = _In::__bits_per_word; 600227825Stheraven difference_type __n = __last - __first; 601227825Stheraven if (__n > 0) 602227825Stheraven { 603227825Stheraven // do first word 604227825Stheraven if (__last.__ctz_ != 0) 605227825Stheraven { 606227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); 607227825Stheraven __n -= __dn; 608227825Stheraven unsigned __clz_l = __bits_per_word - __last.__ctz_; 609227825Stheraven __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l); 610227825Stheraven __storage_type __b = *__last.__seg_ & __m; 611227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 612227825Stheraven __storage_type __ddn = _VSTD::min(__dn, static_cast<difference_type>(__result.__ctz_)); 613227825Stheraven if (__ddn > 0) 614227825Stheraven { 615227825Stheraven __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r); 616227825Stheraven *__result.__seg_ &= ~__m; 617227825Stheraven if (__result.__ctz_ > __last.__ctz_) 618227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 619227825Stheraven else 620227825Stheraven *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_); 621227825Stheraven __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) + 622227825Stheraven __result.__ctz_) % __bits_per_word); 623227825Stheraven __dn -= __ddn; 624227825Stheraven } 625227825Stheraven if (__dn > 0) 626227825Stheraven { 627227825Stheraven // __result.__ctz_ == 0 628227825Stheraven --__result.__seg_; 629227825Stheraven __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1)); 630227825Stheraven __m = ~__storage_type(0) << __result.__ctz_; 631227825Stheraven *__result.__seg_ &= ~__m; 632227825Stheraven __last.__ctz_ -= __dn + __ddn; 633227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 634227825Stheraven } 635227825Stheraven // __last.__ctz_ = 0 636227825Stheraven } 637227825Stheraven // __last.__ctz_ == 0 || __n == 0 638227825Stheraven // __result.__ctz_ != 0 || __n == 0 639227825Stheraven // do middle words 640227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 641227825Stheraven __storage_type __m = ~__storage_type(0) >> __clz_r; 642227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word) 643227825Stheraven { 644227825Stheraven __storage_type __b = *--__last.__seg_; 645227825Stheraven *__result.__seg_ &= ~__m; 646227825Stheraven *__result.__seg_ |= __b >> __clz_r; 647227825Stheraven *--__result.__seg_ &= __m; 648227825Stheraven *__result.__seg_ |= __b << __result.__ctz_; 649227825Stheraven } 650227825Stheraven // do last word 651227825Stheraven if (__n > 0) 652227825Stheraven { 653227825Stheraven __m = ~__storage_type(0) << (__bits_per_word - __n); 654227825Stheraven __storage_type __b = *--__last.__seg_ & __m; 655232950Stheraven __clz_r = __bits_per_word - __result.__ctz_; 656227825Stheraven __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__result.__ctz_)); 657227825Stheraven __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r); 658227825Stheraven *__result.__seg_ &= ~__m; 659227825Stheraven *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_); 660227825Stheraven __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 661227825Stheraven __result.__ctz_) % __bits_per_word); 662227825Stheraven __n -= __dn; 663227825Stheraven if (__n > 0) 664227825Stheraven { 665227825Stheraven // __result.__ctz_ == 0 666227825Stheraven --__result.__seg_; 667227825Stheraven __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 668227825Stheraven __m = ~__storage_type(0) << __result.__ctz_; 669227825Stheraven *__result.__seg_ &= ~__m; 670227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn)); 671227825Stheraven } 672227825Stheraven } 673227825Stheraven } 674227825Stheraven return __result; 675227825Stheraven} 676227825Stheraven 677232950Stheraventemplate <class _Cp, bool _IsConst> 678227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 679232950Stheraven__bit_iterator<_Cp, false> 680232950Stheravencopy_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 681227825Stheraven{ 682227825Stheraven if (__last.__ctz_ == __result.__ctz_) 683227825Stheraven return __copy_backward_aligned(__first, __last, __result); 684227825Stheraven return __copy_backward_unaligned(__first, __last, __result); 685227825Stheraven} 686227825Stheraven 687227825Stheraven// move 688227825Stheraven 689232950Stheraventemplate <class _Cp, bool _IsConst> 690227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 691232950Stheraven__bit_iterator<_Cp, false> 692232950Stheravenmove(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 693227825Stheraven{ 694227825Stheraven return _VSTD::copy(__first, __last, __result); 695227825Stheraven} 696227825Stheraven 697227825Stheraven// move_backward 698227825Stheraven 699232950Stheraventemplate <class _Cp, bool _IsConst> 700227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 701232950Stheraven__bit_iterator<_Cp, false> 702232950Stheravenmove_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 703227825Stheraven{ 704227825Stheraven return _VSTD::copy(__first, __last, __result); 705227825Stheraven} 706227825Stheraven 707227825Stheraven// swap_ranges 708227825Stheraven 709227825Stheraventemplate <class __C1, class __C2> 710227825Stheraven__bit_iterator<__C2, false> 711227825Stheraven__swap_ranges_aligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, 712227825Stheraven __bit_iterator<__C2, false> __result) 713227825Stheraven{ 714227825Stheraven typedef __bit_iterator<__C1, false> _I1; 715227825Stheraven typedef typename _I1::difference_type difference_type; 716227825Stheraven typedef typename _I1::__storage_type __storage_type; 717227825Stheraven static const unsigned __bits_per_word = _I1::__bits_per_word; 718227825Stheraven difference_type __n = __last - __first; 719227825Stheraven if (__n > 0) 720227825Stheraven { 721227825Stheraven // do first word 722227825Stheraven if (__first.__ctz_ != 0) 723227825Stheraven { 724227825Stheraven unsigned __clz = __bits_per_word - __first.__ctz_; 725227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 726227825Stheraven __n -= __dn; 727227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 728227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 729227825Stheraven *__first.__seg_ &= ~__m; 730227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 731227825Stheraven *__result.__seg_ &= ~__m; 732227825Stheraven *__result.__seg_ |= __b1; 733227825Stheraven *__first.__seg_ |= __b2; 734227825Stheraven __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 735227825Stheraven __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 736227825Stheraven ++__first.__seg_; 737227825Stheraven // __first.__ctz_ = 0; 738227825Stheraven } 739227825Stheraven // __first.__ctz_ == 0; 740227825Stheraven // do middle words 741227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_) 742227825Stheraven swap(*__first.__seg_, *__result.__seg_); 743227825Stheraven // do last word 744227825Stheraven if (__n > 0) 745227825Stheraven { 746227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 747227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 748227825Stheraven *__first.__seg_ &= ~__m; 749227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 750227825Stheraven *__result.__seg_ &= ~__m; 751227825Stheraven *__result.__seg_ |= __b1; 752227825Stheraven *__first.__seg_ |= __b2; 753227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 754227825Stheraven } 755227825Stheraven } 756227825Stheraven return __result; 757227825Stheraven} 758227825Stheraven 759227825Stheraventemplate <class __C1, class __C2> 760227825Stheraven__bit_iterator<__C2, false> 761227825Stheraven__swap_ranges_unaligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, 762227825Stheraven __bit_iterator<__C2, false> __result) 763227825Stheraven{ 764227825Stheraven typedef __bit_iterator<__C1, false> _I1; 765227825Stheraven typedef typename _I1::difference_type difference_type; 766227825Stheraven typedef typename _I1::__storage_type __storage_type; 767227825Stheraven static const unsigned __bits_per_word = _I1::__bits_per_word; 768227825Stheraven difference_type __n = __last - __first; 769227825Stheraven if (__n > 0) 770227825Stheraven { 771227825Stheraven // do first word 772227825Stheraven if (__first.__ctz_ != 0) 773227825Stheraven { 774227825Stheraven unsigned __clz_f = __bits_per_word - __first.__ctz_; 775227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 776227825Stheraven __n -= __dn; 777227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 778227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 779227825Stheraven *__first.__seg_ &= ~__m; 780227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 781227825Stheraven __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 782227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 783227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 784227825Stheraven *__result.__seg_ &= ~__m; 785227825Stheraven if (__result.__ctz_ > __first.__ctz_) 786227825Stheraven { 787227825Stheraven unsigned __s = __result.__ctz_ - __first.__ctz_; 788227825Stheraven *__result.__seg_ |= __b1 << __s; 789227825Stheraven *__first.__seg_ |= __b2 >> __s; 790227825Stheraven } 791227825Stheraven else 792227825Stheraven { 793227825Stheraven unsigned __s = __first.__ctz_ - __result.__ctz_; 794227825Stheraven *__result.__seg_ |= __b1 >> __s; 795227825Stheraven *__first.__seg_ |= __b2 << __s; 796227825Stheraven } 797227825Stheraven __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 798227825Stheraven __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 799227825Stheraven __dn -= __ddn; 800227825Stheraven if (__dn > 0) 801227825Stheraven { 802227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __dn); 803227825Stheraven __b2 = *__result.__seg_ & __m; 804227825Stheraven *__result.__seg_ &= ~__m; 805227825Stheraven unsigned __s = __first.__ctz_ + __ddn; 806227825Stheraven *__result.__seg_ |= __b1 >> __s; 807227825Stheraven *__first.__seg_ |= __b2 << __s; 808227825Stheraven __result.__ctz_ = static_cast<unsigned>(__dn); 809227825Stheraven } 810227825Stheraven ++__first.__seg_; 811227825Stheraven // __first.__ctz_ = 0; 812227825Stheraven } 813227825Stheraven // __first.__ctz_ == 0; 814227825Stheraven // do middle words 815227825Stheraven __storage_type __m = ~__storage_type(0) << __result.__ctz_; 816227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 817227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 818227825Stheraven { 819227825Stheraven __storage_type __b1 = *__first.__seg_; 820227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 821227825Stheraven *__result.__seg_ &= ~__m; 822227825Stheraven *__result.__seg_ |= __b1 << __result.__ctz_; 823227825Stheraven *__first.__seg_ = __b2 >> __result.__ctz_; 824227825Stheraven ++__result.__seg_; 825227825Stheraven __b2 = *__result.__seg_ & ~__m; 826227825Stheraven *__result.__seg_ &= __m; 827227825Stheraven *__result.__seg_ |= __b1 >> __clz_r; 828227825Stheraven *__first.__seg_ |= __b2 << __clz_r; 829227825Stheraven } 830227825Stheraven // do last word 831227825Stheraven if (__n > 0) 832227825Stheraven { 833227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 834227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 835227825Stheraven *__first.__seg_ &= ~__m; 836227825Stheraven __storage_type __dn = _VSTD::min<__storage_type>(__n, __clz_r); 837227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 838227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 839227825Stheraven *__result.__seg_ &= ~__m; 840227825Stheraven *__result.__seg_ |= __b1 << __result.__ctz_; 841227825Stheraven *__first.__seg_ |= __b2 >> __result.__ctz_; 842227825Stheraven __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 843227825Stheraven __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 844227825Stheraven __n -= __dn; 845227825Stheraven if (__n > 0) 846227825Stheraven { 847227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 848227825Stheraven __b2 = *__result.__seg_ & __m; 849227825Stheraven *__result.__seg_ &= ~__m; 850227825Stheraven *__result.__seg_ |= __b1 >> __dn; 851227825Stheraven *__first.__seg_ |= __b2 << __dn; 852227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 853227825Stheraven } 854227825Stheraven } 855227825Stheraven } 856227825Stheraven return __result; 857227825Stheraven} 858227825Stheraven 859227825Stheraventemplate <class __C1, class __C2> 860227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 861227825Stheraven__bit_iterator<__C2, false> 862227825Stheravenswap_ranges(__bit_iterator<__C1, false> __first1, __bit_iterator<__C1, false> __last1, 863227825Stheraven __bit_iterator<__C2, false> __first2) 864227825Stheraven{ 865227825Stheraven if (__first1.__ctz_ == __first2.__ctz_) 866227825Stheraven return __swap_ranges_aligned(__first1, __last1, __first2); 867227825Stheraven return __swap_ranges_unaligned(__first1, __last1, __first2); 868227825Stheraven} 869227825Stheraven 870227825Stheraven// rotate 871227825Stheraven 872232950Stheraventemplate <class _Cp> 873227825Stheravenstruct __bit_array 874227825Stheraven{ 875232950Stheraven typedef typename _Cp::difference_type difference_type; 876232950Stheraven typedef typename _Cp::__storage_type __storage_type; 877253159Stheraven typedef typename _Cp::__storage_pointer __storage_pointer; 878232950Stheraven typedef typename _Cp::iterator iterator; 879232950Stheraven static const unsigned __bits_per_word = _Cp::__bits_per_word; 880232950Stheraven static const unsigned _Np = 4; 881227825Stheraven 882227825Stheraven difference_type __size_; 883232950Stheraven __storage_type __word_[_Np]; 884227825Stheraven 885227825Stheraven _LIBCPP_INLINE_VISIBILITY static difference_type capacity() 886232950Stheraven {return static_cast<difference_type>(_Np * __bits_per_word);} 887227825Stheraven _LIBCPP_INLINE_VISIBILITY explicit __bit_array(difference_type __s) : __size_(__s) {} 888253159Stheraven _LIBCPP_INLINE_VISIBILITY iterator begin() 889253159Stheraven { 890253159Stheraven return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]), 0); 891253159Stheraven } 892253159Stheraven _LIBCPP_INLINE_VISIBILITY iterator end() 893253159Stheraven { 894253159Stheraven return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]) + __size_ / __bits_per_word, 895253159Stheraven static_cast<unsigned>(__size_ % __bits_per_word)); 896253159Stheraven } 897227825Stheraven}; 898227825Stheraven 899232950Stheraventemplate <class _Cp> 900232950Stheraven__bit_iterator<_Cp, false> 901232950Stheravenrotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last) 902227825Stheraven{ 903232950Stheraven typedef __bit_iterator<_Cp, false> _I1; 904227825Stheraven typedef typename _I1::difference_type difference_type; 905227825Stheraven typedef typename _I1::__storage_type __storage_type; 906227825Stheraven difference_type __d1 = __middle - __first; 907227825Stheraven difference_type __d2 = __last - __middle; 908227825Stheraven _I1 __r = __first + __d2; 909227825Stheraven while (__d1 != 0 && __d2 != 0) 910227825Stheraven { 911227825Stheraven if (__d1 <= __d2) 912227825Stheraven { 913232950Stheraven if (__d1 <= __bit_array<_Cp>::capacity()) 914227825Stheraven { 915232950Stheraven __bit_array<_Cp> __b(__d1); 916227825Stheraven _VSTD::copy(__first, __middle, __b.begin()); 917227825Stheraven _VSTD::copy(__b.begin(), __b.end(), _VSTD::copy(__middle, __last, __first)); 918227825Stheraven break; 919227825Stheraven } 920227825Stheraven else 921227825Stheraven { 922232950Stheraven __bit_iterator<_Cp, false> __mp = _VSTD::swap_ranges(__first, __middle, __middle); 923227825Stheraven __first = __middle; 924227825Stheraven __middle = __mp; 925227825Stheraven __d2 -= __d1; 926227825Stheraven } 927227825Stheraven } 928227825Stheraven else 929227825Stheraven { 930232950Stheraven if (__d2 <= __bit_array<_Cp>::capacity()) 931227825Stheraven { 932232950Stheraven __bit_array<_Cp> __b(__d2); 933227825Stheraven _VSTD::copy(__middle, __last, __b.begin()); 934227825Stheraven _VSTD::copy_backward(__b.begin(), __b.end(), _VSTD::copy_backward(__first, __middle, __last)); 935227825Stheraven break; 936227825Stheraven } 937227825Stheraven else 938227825Stheraven { 939232950Stheraven __bit_iterator<_Cp, false> __mp = __first + __d2; 940227825Stheraven _VSTD::swap_ranges(__first, __mp, __middle); 941227825Stheraven __first = __mp; 942227825Stheraven __d1 -= __d2; 943227825Stheraven } 944227825Stheraven } 945227825Stheraven } 946227825Stheraven return __r; 947227825Stheraven} 948227825Stheraven 949227825Stheraven// equal 950227825Stheraven 951241903Sdimtemplate <class _Cp, bool _IC1, bool _IC2> 952227825Stheravenbool 953241903Sdim__equal_unaligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, 954241903Sdim __bit_iterator<_Cp, _IC2> __first2) 955227825Stheraven{ 956241903Sdim typedef __bit_iterator<_Cp, _IC1> _It; 957227825Stheraven typedef typename _It::difference_type difference_type; 958227825Stheraven typedef typename _It::__storage_type __storage_type; 959227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 960227825Stheraven difference_type __n = __last1 - __first1; 961227825Stheraven if (__n > 0) 962227825Stheraven { 963227825Stheraven // do first word 964227825Stheraven if (__first1.__ctz_ != 0) 965227825Stheraven { 966227825Stheraven unsigned __clz_f = __bits_per_word - __first1.__ctz_; 967227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 968227825Stheraven __n -= __dn; 969227825Stheraven __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 970227825Stheraven __storage_type __b = *__first1.__seg_ & __m; 971227825Stheraven unsigned __clz_r = __bits_per_word - __first2.__ctz_; 972227825Stheraven __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 973227825Stheraven __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 974227825Stheraven if (__first2.__ctz_ > __first1.__ctz_) 975236387Sdim { 976227825Stheraven if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_))) 977227825Stheraven return false; 978236387Sdim } 979227825Stheraven else 980236387Sdim { 981227825Stheraven if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_))) 982227825Stheraven return false; 983236387Sdim } 984227825Stheraven __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word; 985227825Stheraven __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word); 986227825Stheraven __dn -= __ddn; 987227825Stheraven if (__dn > 0) 988227825Stheraven { 989227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __dn); 990227825Stheraven if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn))) 991227825Stheraven return false; 992227825Stheraven __first2.__ctz_ = static_cast<unsigned>(__dn); 993227825Stheraven } 994227825Stheraven ++__first1.__seg_; 995227825Stheraven // __first1.__ctz_ = 0; 996227825Stheraven } 997227825Stheraven // __first1.__ctz_ == 0; 998227825Stheraven // do middle words 999227825Stheraven unsigned __clz_r = __bits_per_word - __first2.__ctz_; 1000227825Stheraven __storage_type __m = ~__storage_type(0) << __first2.__ctz_; 1001227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_) 1002227825Stheraven { 1003227825Stheraven __storage_type __b = *__first1.__seg_; 1004227825Stheraven if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 1005227825Stheraven return false; 1006227825Stheraven ++__first2.__seg_; 1007227825Stheraven if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r)) 1008227825Stheraven return false; 1009227825Stheraven } 1010227825Stheraven // do last word 1011227825Stheraven if (__n > 0) 1012227825Stheraven { 1013227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 1014227825Stheraven __storage_type __b = *__first1.__seg_ & __m; 1015227825Stheraven __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); 1016227825Stheraven __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 1017227825Stheraven if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 1018227825Stheraven return false; 1019227825Stheraven __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word; 1020227825Stheraven __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word); 1021227825Stheraven __n -= __dn; 1022227825Stheraven if (__n > 0) 1023227825Stheraven { 1024227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 1025227825Stheraven if ((*__first2.__seg_ & __m) != (__b >> __dn)) 1026227825Stheraven return false; 1027227825Stheraven } 1028227825Stheraven } 1029227825Stheraven } 1030227825Stheraven return true; 1031227825Stheraven} 1032227825Stheraven 1033241903Sdimtemplate <class _Cp, bool _IC1, bool _IC2> 1034227825Stheravenbool 1035241903Sdim__equal_aligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, 1036241903Sdim __bit_iterator<_Cp, _IC2> __first2) 1037227825Stheraven{ 1038241903Sdim typedef __bit_iterator<_Cp, _IC1> _It; 1039227825Stheraven typedef typename _It::difference_type difference_type; 1040227825Stheraven typedef typename _It::__storage_type __storage_type; 1041227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 1042227825Stheraven difference_type __n = __last1 - __first1; 1043227825Stheraven if (__n > 0) 1044227825Stheraven { 1045227825Stheraven // do first word 1046227825Stheraven if (__first1.__ctz_ != 0) 1047227825Stheraven { 1048227825Stheraven unsigned __clz = __bits_per_word - __first1.__ctz_; 1049227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 1050227825Stheraven __n -= __dn; 1051227825Stheraven __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 1052227825Stheraven if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 1053227825Stheraven return false; 1054227825Stheraven ++__first2.__seg_; 1055227825Stheraven ++__first1.__seg_; 1056227825Stheraven // __first1.__ctz_ = 0; 1057227825Stheraven // __first2.__ctz_ = 0; 1058227825Stheraven } 1059227825Stheraven // __first1.__ctz_ == 0; 1060227825Stheraven // __first2.__ctz_ == 0; 1061227825Stheraven // do middle words 1062227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_) 1063227825Stheraven if (*__first2.__seg_ != *__first1.__seg_) 1064227825Stheraven return false; 1065227825Stheraven // do last word 1066227825Stheraven if (__n > 0) 1067227825Stheraven { 1068227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 1069227825Stheraven if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 1070227825Stheraven return false; 1071227825Stheraven } 1072227825Stheraven } 1073227825Stheraven return true; 1074227825Stheraven} 1075227825Stheraven 1076232950Stheraventemplate <class _Cp, bool _IC1, bool _IC2> 1077227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1078227825Stheravenbool 1079232950Stheravenequal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) 1080227825Stheraven{ 1081227825Stheraven if (__first1.__ctz_ == __first2.__ctz_) 1082227825Stheraven return __equal_aligned(__first1, __last1, __first2); 1083227825Stheraven return __equal_unaligned(__first1, __last1, __first2); 1084227825Stheraven} 1085227825Stheraven 1086241903Sdimtemplate <class _Cp, bool _IsConst, 1087241903Sdim typename _Cp::__storage_type> 1088227825Stheravenclass __bit_iterator 1089227825Stheraven{ 1090227825Stheravenpublic: 1091232950Stheraven typedef typename _Cp::difference_type difference_type; 1092227825Stheraven typedef bool value_type; 1093227825Stheraven typedef __bit_iterator pointer; 1094232950Stheraven typedef typename conditional<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >::type reference; 1095227825Stheraven typedef random_access_iterator_tag iterator_category; 1096227825Stheraven 1097227825Stheravenprivate: 1098232950Stheraven typedef typename _Cp::__storage_type __storage_type; 1099232950Stheraven typedef typename conditional<_IsConst, typename _Cp::__const_storage_pointer, 1100232950Stheraven typename _Cp::__storage_pointer>::type __storage_pointer; 1101232950Stheraven static const unsigned __bits_per_word = _Cp::__bits_per_word; 1102227825Stheraven 1103227825Stheraven __storage_pointer __seg_; 1104227825Stheraven unsigned __ctz_; 1105227825Stheraven 1106227825Stheravenpublic: 1107227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator() _NOEXCEPT {} 1108227825Stheraven 1109227825Stheraven _LIBCPP_INLINE_VISIBILITY 1110232950Stheraven __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT 1111227825Stheraven : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {} 1112227825Stheraven 1113227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT 1114227825Stheraven {return reference(__seg_, __storage_type(1) << __ctz_);} 1115227825Stheraven 1116227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator++() 1117227825Stheraven { 1118227825Stheraven if (__ctz_ != __bits_per_word-1) 1119227825Stheraven ++__ctz_; 1120227825Stheraven else 1121227825Stheraven { 1122227825Stheraven __ctz_ = 0; 1123227825Stheraven ++__seg_; 1124227825Stheraven } 1125227825Stheraven return *this; 1126227825Stheraven } 1127227825Stheraven 1128227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator operator++(int) 1129227825Stheraven { 1130227825Stheraven __bit_iterator __tmp = *this; 1131227825Stheraven ++(*this); 1132227825Stheraven return __tmp; 1133227825Stheraven } 1134227825Stheraven 1135227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator--() 1136227825Stheraven { 1137227825Stheraven if (__ctz_ != 0) 1138227825Stheraven --__ctz_; 1139227825Stheraven else 1140227825Stheraven { 1141227825Stheraven __ctz_ = __bits_per_word - 1; 1142227825Stheraven --__seg_; 1143227825Stheraven } 1144227825Stheraven return *this; 1145227825Stheraven } 1146227825Stheraven 1147227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator operator--(int) 1148227825Stheraven { 1149227825Stheraven __bit_iterator __tmp = *this; 1150227825Stheraven --(*this); 1151227825Stheraven return __tmp; 1152227825Stheraven } 1153227825Stheraven 1154227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator+=(difference_type __n) 1155227825Stheraven { 1156227825Stheraven if (__n >= 0) 1157227825Stheraven __seg_ += (__n + __ctz_) / __bits_per_word; 1158227825Stheraven else 1159227825Stheraven __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1) 1160227825Stheraven / static_cast<difference_type>(__bits_per_word); 1161227825Stheraven __n &= (__bits_per_word - 1); 1162227825Stheraven __ctz_ = static_cast<unsigned>((__n + __ctz_) % __bits_per_word); 1163227825Stheraven return *this; 1164227825Stheraven } 1165227825Stheraven 1166227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator-=(difference_type __n) 1167227825Stheraven { 1168227825Stheraven return *this += -__n; 1169227825Stheraven } 1170227825Stheraven 1171227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator operator+(difference_type __n) const 1172227825Stheraven { 1173227825Stheraven __bit_iterator __t(*this); 1174227825Stheraven __t += __n; 1175227825Stheraven return __t; 1176227825Stheraven } 1177227825Stheraven 1178227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator operator-(difference_type __n) const 1179227825Stheraven { 1180227825Stheraven __bit_iterator __t(*this); 1181227825Stheraven __t -= __n; 1182227825Stheraven return __t; 1183227825Stheraven } 1184227825Stheraven 1185227825Stheraven _LIBCPP_INLINE_VISIBILITY 1186227825Stheraven friend __bit_iterator operator+(difference_type __n, const __bit_iterator& __it) {return __it + __n;} 1187227825Stheraven 1188227825Stheraven _LIBCPP_INLINE_VISIBILITY 1189227825Stheraven friend difference_type operator-(const __bit_iterator& __x, const __bit_iterator& __y) 1190227825Stheraven {return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;} 1191227825Stheraven 1192227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const {return *(*this + __n);} 1193227825Stheraven 1194227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator==(const __bit_iterator& __x, const __bit_iterator& __y) 1195227825Stheraven {return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;} 1196227825Stheraven 1197227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator!=(const __bit_iterator& __x, const __bit_iterator& __y) 1198227825Stheraven {return !(__x == __y);} 1199227825Stheraven 1200227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator<(const __bit_iterator& __x, const __bit_iterator& __y) 1201227825Stheraven {return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);} 1202227825Stheraven 1203227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator>(const __bit_iterator& __x, const __bit_iterator& __y) 1204227825Stheraven {return __y < __x;} 1205227825Stheraven 1206227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y) 1207227825Stheraven {return !(__y < __x);} 1208227825Stheraven 1209227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y) 1210227825Stheraven {return !(__x < __y);} 1211227825Stheraven 1212227825Stheravenprivate: 1213227825Stheraven _LIBCPP_INLINE_VISIBILITY 1214227825Stheraven __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT 1215227825Stheraven : __seg_(__s), __ctz_(__ctz) {} 1216227825Stheraven 1217227825Stheraven#if defined(__clang__) 1218232950Stheraven friend typename _Cp::__self; 1219227825Stheraven#else 1220232950Stheraven friend class _Cp::__self; 1221227825Stheraven#endif 1222232950Stheraven friend class __bit_reference<_Cp>; 1223232950Stheraven friend class __bit_const_reference<_Cp>; 1224232950Stheraven friend class __bit_iterator<_Cp, true>; 1225232950Stheraven template <class _Dp> friend struct __bit_array; 1226232950Stheraven template <class _Dp> friend void __fill_n_false(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); 1227232950Stheraven template <class _Dp> friend void __fill_n_true(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); 1228232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_aligned(__bit_iterator<_Dp, _IC> __first, 1229232950Stheraven __bit_iterator<_Dp, _IC> __last, 1230232950Stheraven __bit_iterator<_Dp, false> __result); 1231232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_unaligned(__bit_iterator<_Dp, _IC> __first, 1232232950Stheraven __bit_iterator<_Dp, _IC> __last, 1233232950Stheraven __bit_iterator<_Dp, false> __result); 1234232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy(__bit_iterator<_Dp, _IC> __first, 1235232950Stheraven __bit_iterator<_Dp, _IC> __last, 1236232950Stheraven __bit_iterator<_Dp, false> __result); 1237232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_aligned(__bit_iterator<_Dp, _IC> __first, 1238232950Stheraven __bit_iterator<_Dp, _IC> __last, 1239232950Stheraven __bit_iterator<_Dp, false> __result); 1240232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_unaligned(__bit_iterator<_Dp, _IC> __first, 1241232950Stheraven __bit_iterator<_Dp, _IC> __last, 1242232950Stheraven __bit_iterator<_Dp, false> __result); 1243232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy_backward(__bit_iterator<_Dp, _IC> __first, 1244232950Stheraven __bit_iterator<_Dp, _IC> __last, 1245232950Stheraven __bit_iterator<_Dp, false> __result); 1246227825Stheraven template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_aligned(__bit_iterator<__C1, false>, 1247227825Stheraven __bit_iterator<__C1, false>, 1248227825Stheraven __bit_iterator<__C2, false>); 1249227825Stheraven template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_unaligned(__bit_iterator<__C1, false>, 1250227825Stheraven __bit_iterator<__C1, false>, 1251227825Stheraven __bit_iterator<__C2, false>); 1252227825Stheraven template <class __C1, class __C2>friend __bit_iterator<__C2, false> swap_ranges(__bit_iterator<__C1, false>, 1253227825Stheraven __bit_iterator<__C1, false>, 1254227825Stheraven __bit_iterator<__C2, false>); 1255232950Stheraven template <class _Dp> friend __bit_iterator<_Dp, false> rotate(__bit_iterator<_Dp, false>, 1256232950Stheraven __bit_iterator<_Dp, false>, 1257232950Stheraven __bit_iterator<_Dp, false>); 1258241903Sdim template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_aligned(__bit_iterator<_Dp, _IC1>, 1259241903Sdim __bit_iterator<_Dp, _IC1>, 1260241903Sdim __bit_iterator<_Dp, _IC2>); 1261241903Sdim template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_unaligned(__bit_iterator<_Dp, _IC1>, 1262241903Sdim __bit_iterator<_Dp, _IC1>, 1263241903Sdim __bit_iterator<_Dp, _IC2>); 1264232950Stheraven template <class _Dp, bool _IC1, bool _IC2> friend bool equal(__bit_iterator<_Dp, _IC1>, 1265232950Stheraven __bit_iterator<_Dp, _IC1>, 1266232950Stheraven __bit_iterator<_Dp, _IC2>); 1267241903Sdim template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_true(__bit_iterator<_Dp, _IC>, 1268232950Stheraven typename _Dp::size_type); 1269241903Sdim template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_false(__bit_iterator<_Dp, _IC>, 1270232950Stheraven typename _Dp::size_type); 1271241903Sdim template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type 1272241903Sdim __count_bool_true(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 1273241903Sdim template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type 1274241903Sdim __count_bool_false(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 1275227825Stheraven}; 1276227825Stheraven 1277227825Stheraven_LIBCPP_END_NAMESPACE_STD 1278227825Stheraven 1279227825Stheraven#endif // _LIBCPP___BIT_REFERENCE 1280