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 43262801Sdim#if defined(__clang__) || defined(__IBMCPP__) || defined(_LIBCPP_MSVC) 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> 85262801Sdiminline _LIBCPP_INLINE_VISIBILITY 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> 95262801Sdiminline _LIBCPP_INLINE_VISIBILITY 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> 105262801Sdiminline _LIBCPP_INLINE_VISIBILITY 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> 115262801Sdiminline _LIBCPP_INLINE_VISIBILITY 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 133262801Sdim#if defined(__clang__) || defined(__IBMCPP__) || defined(_LIBCPP_MSVC) 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))); 176262801Sdim if (__n == __dn) 177278724Sdim return __first + __n; 178227825Stheraven __n -= __dn; 179227825Stheraven ++__first.__seg_; 180227825Stheraven } 181227825Stheraven // do middle whole words 182227825Stheraven for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 183227825Stheraven if (*__first.__seg_) 184227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(*__first.__seg_))); 185227825Stheraven // do last partial word 186227825Stheraven if (__n > 0) 187227825Stheraven { 188227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 189227825Stheraven __storage_type __b = *__first.__seg_ & __m; 190227825Stheraven if (__b) 191227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 192227825Stheraven } 193227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(__n)); 194227825Stheraven} 195227825Stheraven 196241903Sdimtemplate <class _Cp, bool _IsConst> 197241903Sdim__bit_iterator<_Cp, _IsConst> 198241903Sdim__find_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 199227825Stheraven{ 200241903Sdim typedef __bit_iterator<_Cp, _IsConst> _It; 201227825Stheraven typedef typename _It::__storage_type __storage_type; 202227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 203227825Stheraven // do first partial word 204227825Stheraven if (__first.__ctz_ != 0) 205227825Stheraven { 206227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 207227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 208227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 209241903Sdim __storage_type __b = ~*__first.__seg_ & __m; 210227825Stheraven if (__b) 211227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 212262801Sdim if (__n == __dn) 213278724Sdim return __first + __n; 214227825Stheraven __n -= __dn; 215227825Stheraven ++__first.__seg_; 216227825Stheraven } 217227825Stheraven // do middle whole words 218227825Stheraven for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 219227825Stheraven { 220227825Stheraven __storage_type __b = ~*__first.__seg_; 221227825Stheraven if (__b) 222227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 223227825Stheraven } 224227825Stheraven // do last partial word 225227825Stheraven if (__n > 0) 226227825Stheraven { 227227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 228241903Sdim __storage_type __b = ~*__first.__seg_ & __m; 229227825Stheraven if (__b) 230227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); 231227825Stheraven } 232227825Stheraven return _It(__first.__seg_, static_cast<unsigned>(__n)); 233227825Stheraven} 234227825Stheraven 235241903Sdimtemplate <class _Cp, bool _IsConst, class _Tp> 236227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 237241903Sdim__bit_iterator<_Cp, _IsConst> 238241903Sdimfind(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_) 239227825Stheraven{ 240227825Stheraven if (static_cast<bool>(__value_)) 241232950Stheraven return __find_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first)); 242232950Stheraven return __find_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first)); 243227825Stheraven} 244227825Stheraven 245227825Stheraven// count 246227825Stheraven 247241903Sdimtemplate <class _Cp, bool _IsConst> 248241903Sdimtypename __bit_iterator<_Cp, _IsConst>::difference_type 249241903Sdim__count_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 250227825Stheraven{ 251241903Sdim typedef __bit_iterator<_Cp, _IsConst> _It; 252227825Stheraven typedef typename _It::__storage_type __storage_type; 253227825Stheraven typedef typename _It::difference_type difference_type; 254227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 255227825Stheraven difference_type __r = 0; 256227825Stheraven // do first partial word 257227825Stheraven if (__first.__ctz_ != 0) 258227825Stheraven { 259227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 260227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 261227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 262227825Stheraven __r = _VSTD::__pop_count(*__first.__seg_ & __m); 263227825Stheraven __n -= __dn; 264227825Stheraven ++__first.__seg_; 265227825Stheraven } 266227825Stheraven // do middle whole words 267227825Stheraven for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 268227825Stheraven __r += _VSTD::__pop_count(*__first.__seg_); 269227825Stheraven // do last partial word 270227825Stheraven if (__n > 0) 271227825Stheraven { 272227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 273227825Stheraven __r += _VSTD::__pop_count(*__first.__seg_ & __m); 274227825Stheraven } 275227825Stheraven return __r; 276227825Stheraven} 277227825Stheraven 278241903Sdimtemplate <class _Cp, bool _IsConst> 279241903Sdimtypename __bit_iterator<_Cp, _IsConst>::difference_type 280241903Sdim__count_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 281227825Stheraven{ 282241903Sdim typedef __bit_iterator<_Cp, _IsConst> _It; 283227825Stheraven typedef typename _It::__storage_type __storage_type; 284227825Stheraven typedef typename _It::difference_type difference_type; 285227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 286227825Stheraven difference_type __r = 0; 287227825Stheraven // do first partial word 288227825Stheraven if (__first.__ctz_ != 0) 289227825Stheraven { 290227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 291227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 292227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 293241903Sdim __r = _VSTD::__pop_count(~*__first.__seg_ & __m); 294227825Stheraven __n -= __dn; 295227825Stheraven ++__first.__seg_; 296227825Stheraven } 297227825Stheraven // do middle whole words 298227825Stheraven for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 299227825Stheraven __r += _VSTD::__pop_count(~*__first.__seg_); 300227825Stheraven // do last partial word 301227825Stheraven if (__n > 0) 302227825Stheraven { 303227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 304241903Sdim __r += _VSTD::__pop_count(~*__first.__seg_ & __m); 305227825Stheraven } 306227825Stheraven return __r; 307227825Stheraven} 308227825Stheraven 309241903Sdimtemplate <class _Cp, bool _IsConst, class _Tp> 310227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 311241903Sdimtypename __bit_iterator<_Cp, _IsConst>::difference_type 312241903Sdimcount(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_) 313227825Stheraven{ 314227825Stheraven if (static_cast<bool>(__value_)) 315232950Stheraven return __count_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first)); 316232950Stheraven return __count_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first)); 317227825Stheraven} 318227825Stheraven 319227825Stheraven// fill_n 320227825Stheraven 321232950Stheraventemplate <class _Cp> 322227825Stheravenvoid 323232950Stheraven__fill_n_false(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) 324227825Stheraven{ 325232950Stheraven typedef __bit_iterator<_Cp, false> _It; 326227825Stheraven typedef typename _It::__storage_type __storage_type; 327227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 328227825Stheraven // do first partial word 329227825Stheraven if (__first.__ctz_ != 0) 330227825Stheraven { 331227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 332227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 333227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 334227825Stheraven *__first.__seg_ &= ~__m; 335227825Stheraven __n -= __dn; 336227825Stheraven ++__first.__seg_; 337227825Stheraven } 338227825Stheraven // do middle whole words 339227825Stheraven __storage_type __nw = __n / __bits_per_word; 340253159Stheraven _VSTD::memset(_VSTD::__to_raw_pointer(__first.__seg_), 0, __nw * sizeof(__storage_type)); 341227825Stheraven __n -= __nw * __bits_per_word; 342227825Stheraven // do last partial word 343227825Stheraven if (__n > 0) 344227825Stheraven { 345227825Stheraven __first.__seg_ += __nw; 346227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 347227825Stheraven *__first.__seg_ &= ~__m; 348227825Stheraven } 349227825Stheraven} 350227825Stheraven 351232950Stheraventemplate <class _Cp> 352227825Stheravenvoid 353232950Stheraven__fill_n_true(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) 354227825Stheraven{ 355232950Stheraven typedef __bit_iterator<_Cp, false> _It; 356227825Stheraven typedef typename _It::__storage_type __storage_type; 357227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 358227825Stheraven // do first partial word 359227825Stheraven if (__first.__ctz_ != 0) 360227825Stheraven { 361227825Stheraven __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 362227825Stheraven __storage_type __dn = _VSTD::min(__clz_f, __n); 363227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 364227825Stheraven *__first.__seg_ |= __m; 365227825Stheraven __n -= __dn; 366227825Stheraven ++__first.__seg_; 367227825Stheraven } 368227825Stheraven // do middle whole words 369227825Stheraven __storage_type __nw = __n / __bits_per_word; 370253159Stheraven _VSTD::memset(_VSTD::__to_raw_pointer(__first.__seg_), -1, __nw * sizeof(__storage_type)); 371227825Stheraven __n -= __nw * __bits_per_word; 372227825Stheraven // do last partial word 373227825Stheraven if (__n > 0) 374227825Stheraven { 375227825Stheraven __first.__seg_ += __nw; 376227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 377227825Stheraven *__first.__seg_ |= __m; 378227825Stheraven } 379227825Stheraven} 380227825Stheraven 381232950Stheraventemplate <class _Cp> 382262801Sdiminline _LIBCPP_INLINE_VISIBILITY 383227825Stheravenvoid 384232950Stheravenfill_n(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n, bool __value_) 385227825Stheraven{ 386227825Stheraven if (__n > 0) 387227825Stheraven { 388227825Stheraven if (__value_) 389227825Stheraven __fill_n_true(__first, __n); 390227825Stheraven else 391227825Stheraven __fill_n_false(__first, __n); 392227825Stheraven } 393227825Stheraven} 394227825Stheraven 395227825Stheraven// fill 396227825Stheraven 397232950Stheraventemplate <class _Cp> 398227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 399227825Stheravenvoid 400232950Stheravenfill(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __last, bool __value_) 401227825Stheraven{ 402232950Stheraven _VSTD::fill_n(__first, static_cast<typename _Cp::size_type>(__last - __first), __value_); 403227825Stheraven} 404227825Stheraven 405227825Stheraven// copy 406227825Stheraven 407232950Stheraventemplate <class _Cp, bool _IsConst> 408232950Stheraven__bit_iterator<_Cp, false> 409232950Stheraven__copy_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 410232950Stheraven __bit_iterator<_Cp, false> __result) 411227825Stheraven{ 412232950Stheraven typedef __bit_iterator<_Cp, _IsConst> _In; 413227825Stheraven typedef typename _In::difference_type difference_type; 414227825Stheraven typedef typename _In::__storage_type __storage_type; 415227825Stheraven static const unsigned __bits_per_word = _In::__bits_per_word; 416227825Stheraven difference_type __n = __last - __first; 417227825Stheraven if (__n > 0) 418227825Stheraven { 419227825Stheraven // do first word 420227825Stheraven if (__first.__ctz_ != 0) 421227825Stheraven { 422227825Stheraven unsigned __clz = __bits_per_word - __first.__ctz_; 423227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 424227825Stheraven __n -= __dn; 425227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 426227825Stheraven __storage_type __b = *__first.__seg_ & __m; 427227825Stheraven *__result.__seg_ &= ~__m; 428227825Stheraven *__result.__seg_ |= __b; 429227825Stheraven __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 430227825Stheraven __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 431227825Stheraven ++__first.__seg_; 432227825Stheraven // __first.__ctz_ = 0; 433227825Stheraven } 434227825Stheraven // __first.__ctz_ == 0; 435227825Stheraven // do middle words 436227825Stheraven __storage_type __nw = __n / __bits_per_word; 437253159Stheraven _VSTD::memmove(_VSTD::__to_raw_pointer(__result.__seg_), 438253159Stheraven _VSTD::__to_raw_pointer(__first.__seg_), 439253159Stheraven __nw * sizeof(__storage_type)); 440227825Stheraven __n -= __nw * __bits_per_word; 441227825Stheraven __result.__seg_ += __nw; 442227825Stheraven // do last word 443227825Stheraven if (__n > 0) 444227825Stheraven { 445227825Stheraven __first.__seg_ += __nw; 446227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 447227825Stheraven __storage_type __b = *__first.__seg_ & __m; 448227825Stheraven *__result.__seg_ &= ~__m; 449227825Stheraven *__result.__seg_ |= __b; 450227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 451227825Stheraven } 452227825Stheraven } 453227825Stheraven return __result; 454227825Stheraven} 455227825Stheraven 456232950Stheraventemplate <class _Cp, bool _IsConst> 457232950Stheraven__bit_iterator<_Cp, false> 458232950Stheraven__copy_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 459232950Stheraven __bit_iterator<_Cp, false> __result) 460227825Stheraven{ 461232950Stheraven typedef __bit_iterator<_Cp, _IsConst> _In; 462227825Stheraven typedef typename _In::difference_type difference_type; 463227825Stheraven typedef typename _In::__storage_type __storage_type; 464227825Stheraven static const unsigned __bits_per_word = _In::__bits_per_word; 465227825Stheraven difference_type __n = __last - __first; 466227825Stheraven if (__n > 0) 467227825Stheraven { 468227825Stheraven // do first word 469227825Stheraven if (__first.__ctz_ != 0) 470227825Stheraven { 471227825Stheraven unsigned __clz_f = __bits_per_word - __first.__ctz_; 472227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 473227825Stheraven __n -= __dn; 474227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 475227825Stheraven __storage_type __b = *__first.__seg_ & __m; 476227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 477227825Stheraven __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 478227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 479227825Stheraven *__result.__seg_ &= ~__m; 480227825Stheraven if (__result.__ctz_ > __first.__ctz_) 481227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_); 482227825Stheraven else 483227825Stheraven *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_); 484227825Stheraven __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 485227825Stheraven __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 486227825Stheraven __dn -= __ddn; 487227825Stheraven if (__dn > 0) 488227825Stheraven { 489227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __dn); 490227825Stheraven *__result.__seg_ &= ~__m; 491227825Stheraven *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn); 492227825Stheraven __result.__ctz_ = static_cast<unsigned>(__dn); 493227825Stheraven } 494227825Stheraven ++__first.__seg_; 495227825Stheraven // __first.__ctz_ = 0; 496227825Stheraven } 497227825Stheraven // __first.__ctz_ == 0; 498227825Stheraven // do middle words 499227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 500227825Stheraven __storage_type __m = ~__storage_type(0) << __result.__ctz_; 501227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 502227825Stheraven { 503227825Stheraven __storage_type __b = *__first.__seg_; 504227825Stheraven *__result.__seg_ &= ~__m; 505227825Stheraven *__result.__seg_ |= __b << __result.__ctz_; 506227825Stheraven ++__result.__seg_; 507227825Stheraven *__result.__seg_ &= __m; 508227825Stheraven *__result.__seg_ |= __b >> __clz_r; 509227825Stheraven } 510227825Stheraven // do last word 511227825Stheraven if (__n > 0) 512227825Stheraven { 513227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 514227825Stheraven __storage_type __b = *__first.__seg_ & __m; 515227825Stheraven __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); 516227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 517227825Stheraven *__result.__seg_ &= ~__m; 518227825Stheraven *__result.__seg_ |= __b << __result.__ctz_; 519227825Stheraven __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 520227825Stheraven __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 521227825Stheraven __n -= __dn; 522227825Stheraven if (__n > 0) 523227825Stheraven { 524227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 525227825Stheraven *__result.__seg_ &= ~__m; 526227825Stheraven *__result.__seg_ |= __b >> __dn; 527227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 528227825Stheraven } 529227825Stheraven } 530227825Stheraven } 531227825Stheraven return __result; 532227825Stheraven} 533227825Stheraven 534232950Stheraventemplate <class _Cp, bool _IsConst> 535227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 536232950Stheraven__bit_iterator<_Cp, false> 537232950Stheravencopy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 538227825Stheraven{ 539227825Stheraven if (__first.__ctz_ == __result.__ctz_) 540227825Stheraven return __copy_aligned(__first, __last, __result); 541227825Stheraven return __copy_unaligned(__first, __last, __result); 542227825Stheraven} 543227825Stheraven 544227825Stheraven// copy_backward 545227825Stheraven 546232950Stheraventemplate <class _Cp, bool _IsConst> 547232950Stheraven__bit_iterator<_Cp, false> 548232950Stheraven__copy_backward_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 549232950Stheraven __bit_iterator<_Cp, false> __result) 550227825Stheraven{ 551232950Stheraven typedef __bit_iterator<_Cp, _IsConst> _In; 552227825Stheraven typedef typename _In::difference_type difference_type; 553227825Stheraven typedef typename _In::__storage_type __storage_type; 554227825Stheraven static const unsigned __bits_per_word = _In::__bits_per_word; 555227825Stheraven difference_type __n = __last - __first; 556227825Stheraven if (__n > 0) 557227825Stheraven { 558227825Stheraven // do first word 559227825Stheraven if (__last.__ctz_ != 0) 560227825Stheraven { 561227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); 562227825Stheraven __n -= __dn; 563227825Stheraven unsigned __clz = __bits_per_word - __last.__ctz_; 564227825Stheraven __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz); 565227825Stheraven __storage_type __b = *__last.__seg_ & __m; 566227825Stheraven *__result.__seg_ &= ~__m; 567227825Stheraven *__result.__seg_ |= __b; 568227825Stheraven __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 569227825Stheraven __result.__ctz_) % __bits_per_word); 570227825Stheraven // __last.__ctz_ = 0 571227825Stheraven } 572227825Stheraven // __last.__ctz_ == 0 || __n == 0 573227825Stheraven // __result.__ctz_ == 0 || __n == 0 574227825Stheraven // do middle words 575227825Stheraven __storage_type __nw = __n / __bits_per_word; 576227825Stheraven __result.__seg_ -= __nw; 577227825Stheraven __last.__seg_ -= __nw; 578253159Stheraven _VSTD::memmove(_VSTD::__to_raw_pointer(__result.__seg_), 579253159Stheraven _VSTD::__to_raw_pointer(__last.__seg_), 580253159Stheraven __nw * sizeof(__storage_type)); 581227825Stheraven __n -= __nw * __bits_per_word; 582227825Stheraven // do last word 583227825Stheraven if (__n > 0) 584227825Stheraven { 585227825Stheraven __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n); 586227825Stheraven __storage_type __b = *--__last.__seg_ & __m; 587227825Stheraven *--__result.__seg_ &= ~__m; 588227825Stheraven *__result.__seg_ |= __b; 589227825Stheraven __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 590227825Stheraven } 591227825Stheraven } 592227825Stheraven return __result; 593227825Stheraven} 594227825Stheraven 595232950Stheraventemplate <class _Cp, bool _IsConst> 596232950Stheraven__bit_iterator<_Cp, false> 597232950Stheraven__copy_backward_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 598232950Stheraven __bit_iterator<_Cp, false> __result) 599227825Stheraven{ 600232950Stheraven typedef __bit_iterator<_Cp, _IsConst> _In; 601227825Stheraven typedef typename _In::difference_type difference_type; 602227825Stheraven typedef typename _In::__storage_type __storage_type; 603227825Stheraven static const unsigned __bits_per_word = _In::__bits_per_word; 604227825Stheraven difference_type __n = __last - __first; 605227825Stheraven if (__n > 0) 606227825Stheraven { 607227825Stheraven // do first word 608227825Stheraven if (__last.__ctz_ != 0) 609227825Stheraven { 610227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); 611227825Stheraven __n -= __dn; 612227825Stheraven unsigned __clz_l = __bits_per_word - __last.__ctz_; 613227825Stheraven __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l); 614227825Stheraven __storage_type __b = *__last.__seg_ & __m; 615227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 616227825Stheraven __storage_type __ddn = _VSTD::min(__dn, static_cast<difference_type>(__result.__ctz_)); 617227825Stheraven if (__ddn > 0) 618227825Stheraven { 619227825Stheraven __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r); 620227825Stheraven *__result.__seg_ &= ~__m; 621227825Stheraven if (__result.__ctz_ > __last.__ctz_) 622227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 623227825Stheraven else 624227825Stheraven *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_); 625227825Stheraven __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) + 626227825Stheraven __result.__ctz_) % __bits_per_word); 627227825Stheraven __dn -= __ddn; 628227825Stheraven } 629227825Stheraven if (__dn > 0) 630227825Stheraven { 631227825Stheraven // __result.__ctz_ == 0 632227825Stheraven --__result.__seg_; 633227825Stheraven __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1)); 634227825Stheraven __m = ~__storage_type(0) << __result.__ctz_; 635227825Stheraven *__result.__seg_ &= ~__m; 636227825Stheraven __last.__ctz_ -= __dn + __ddn; 637227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 638227825Stheraven } 639227825Stheraven // __last.__ctz_ = 0 640227825Stheraven } 641227825Stheraven // __last.__ctz_ == 0 || __n == 0 642227825Stheraven // __result.__ctz_ != 0 || __n == 0 643227825Stheraven // do middle words 644227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 645227825Stheraven __storage_type __m = ~__storage_type(0) >> __clz_r; 646227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word) 647227825Stheraven { 648227825Stheraven __storage_type __b = *--__last.__seg_; 649227825Stheraven *__result.__seg_ &= ~__m; 650227825Stheraven *__result.__seg_ |= __b >> __clz_r; 651227825Stheraven *--__result.__seg_ &= __m; 652227825Stheraven *__result.__seg_ |= __b << __result.__ctz_; 653227825Stheraven } 654227825Stheraven // do last word 655227825Stheraven if (__n > 0) 656227825Stheraven { 657227825Stheraven __m = ~__storage_type(0) << (__bits_per_word - __n); 658227825Stheraven __storage_type __b = *--__last.__seg_ & __m; 659232950Stheraven __clz_r = __bits_per_word - __result.__ctz_; 660227825Stheraven __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__result.__ctz_)); 661227825Stheraven __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r); 662227825Stheraven *__result.__seg_ &= ~__m; 663227825Stheraven *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_); 664227825Stheraven __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 665227825Stheraven __result.__ctz_) % __bits_per_word); 666227825Stheraven __n -= __dn; 667227825Stheraven if (__n > 0) 668227825Stheraven { 669227825Stheraven // __result.__ctz_ == 0 670227825Stheraven --__result.__seg_; 671227825Stheraven __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 672227825Stheraven __m = ~__storage_type(0) << __result.__ctz_; 673227825Stheraven *__result.__seg_ &= ~__m; 674227825Stheraven *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn)); 675227825Stheraven } 676227825Stheraven } 677227825Stheraven } 678227825Stheraven return __result; 679227825Stheraven} 680227825Stheraven 681232950Stheraventemplate <class _Cp, bool _IsConst> 682227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 683232950Stheraven__bit_iterator<_Cp, false> 684232950Stheravencopy_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 685227825Stheraven{ 686227825Stheraven if (__last.__ctz_ == __result.__ctz_) 687227825Stheraven return __copy_backward_aligned(__first, __last, __result); 688227825Stheraven return __copy_backward_unaligned(__first, __last, __result); 689227825Stheraven} 690227825Stheraven 691227825Stheraven// move 692227825Stheraven 693232950Stheraventemplate <class _Cp, bool _IsConst> 694227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 695232950Stheraven__bit_iterator<_Cp, false> 696232950Stheravenmove(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 697227825Stheraven{ 698227825Stheraven return _VSTD::copy(__first, __last, __result); 699227825Stheraven} 700227825Stheraven 701227825Stheraven// move_backward 702227825Stheraven 703232950Stheraventemplate <class _Cp, bool _IsConst> 704227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 705232950Stheraven__bit_iterator<_Cp, false> 706232950Stheravenmove_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 707227825Stheraven{ 708278724Sdim return _VSTD::copy_backward(__first, __last, __result); 709227825Stheraven} 710227825Stheraven 711227825Stheraven// swap_ranges 712227825Stheraven 713227825Stheraventemplate <class __C1, class __C2> 714227825Stheraven__bit_iterator<__C2, false> 715227825Stheraven__swap_ranges_aligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, 716227825Stheraven __bit_iterator<__C2, false> __result) 717227825Stheraven{ 718227825Stheraven typedef __bit_iterator<__C1, false> _I1; 719227825Stheraven typedef typename _I1::difference_type difference_type; 720227825Stheraven typedef typename _I1::__storage_type __storage_type; 721227825Stheraven static const unsigned __bits_per_word = _I1::__bits_per_word; 722227825Stheraven difference_type __n = __last - __first; 723227825Stheraven if (__n > 0) 724227825Stheraven { 725227825Stheraven // do first word 726227825Stheraven if (__first.__ctz_ != 0) 727227825Stheraven { 728227825Stheraven unsigned __clz = __bits_per_word - __first.__ctz_; 729227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 730227825Stheraven __n -= __dn; 731227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 732227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 733227825Stheraven *__first.__seg_ &= ~__m; 734227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 735227825Stheraven *__result.__seg_ &= ~__m; 736227825Stheraven *__result.__seg_ |= __b1; 737227825Stheraven *__first.__seg_ |= __b2; 738227825Stheraven __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 739227825Stheraven __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 740227825Stheraven ++__first.__seg_; 741227825Stheraven // __first.__ctz_ = 0; 742227825Stheraven } 743227825Stheraven // __first.__ctz_ == 0; 744227825Stheraven // do middle words 745227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_) 746227825Stheraven swap(*__first.__seg_, *__result.__seg_); 747227825Stheraven // do last word 748227825Stheraven if (__n > 0) 749227825Stheraven { 750227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 751227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 752227825Stheraven *__first.__seg_ &= ~__m; 753227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 754227825Stheraven *__result.__seg_ &= ~__m; 755227825Stheraven *__result.__seg_ |= __b1; 756227825Stheraven *__first.__seg_ |= __b2; 757227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 758227825Stheraven } 759227825Stheraven } 760227825Stheraven return __result; 761227825Stheraven} 762227825Stheraven 763227825Stheraventemplate <class __C1, class __C2> 764227825Stheraven__bit_iterator<__C2, false> 765227825Stheraven__swap_ranges_unaligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, 766227825Stheraven __bit_iterator<__C2, false> __result) 767227825Stheraven{ 768227825Stheraven typedef __bit_iterator<__C1, false> _I1; 769227825Stheraven typedef typename _I1::difference_type difference_type; 770227825Stheraven typedef typename _I1::__storage_type __storage_type; 771227825Stheraven static const unsigned __bits_per_word = _I1::__bits_per_word; 772227825Stheraven difference_type __n = __last - __first; 773227825Stheraven if (__n > 0) 774227825Stheraven { 775227825Stheraven // do first word 776227825Stheraven if (__first.__ctz_ != 0) 777227825Stheraven { 778227825Stheraven unsigned __clz_f = __bits_per_word - __first.__ctz_; 779227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 780227825Stheraven __n -= __dn; 781227825Stheraven __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 782227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 783227825Stheraven *__first.__seg_ &= ~__m; 784227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 785227825Stheraven __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 786227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 787227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 788227825Stheraven *__result.__seg_ &= ~__m; 789227825Stheraven if (__result.__ctz_ > __first.__ctz_) 790227825Stheraven { 791227825Stheraven unsigned __s = __result.__ctz_ - __first.__ctz_; 792227825Stheraven *__result.__seg_ |= __b1 << __s; 793227825Stheraven *__first.__seg_ |= __b2 >> __s; 794227825Stheraven } 795227825Stheraven else 796227825Stheraven { 797227825Stheraven unsigned __s = __first.__ctz_ - __result.__ctz_; 798227825Stheraven *__result.__seg_ |= __b1 >> __s; 799227825Stheraven *__first.__seg_ |= __b2 << __s; 800227825Stheraven } 801227825Stheraven __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 802227825Stheraven __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 803227825Stheraven __dn -= __ddn; 804227825Stheraven if (__dn > 0) 805227825Stheraven { 806227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __dn); 807227825Stheraven __b2 = *__result.__seg_ & __m; 808227825Stheraven *__result.__seg_ &= ~__m; 809227825Stheraven unsigned __s = __first.__ctz_ + __ddn; 810227825Stheraven *__result.__seg_ |= __b1 >> __s; 811227825Stheraven *__first.__seg_ |= __b2 << __s; 812227825Stheraven __result.__ctz_ = static_cast<unsigned>(__dn); 813227825Stheraven } 814227825Stheraven ++__first.__seg_; 815227825Stheraven // __first.__ctz_ = 0; 816227825Stheraven } 817227825Stheraven // __first.__ctz_ == 0; 818227825Stheraven // do middle words 819227825Stheraven __storage_type __m = ~__storage_type(0) << __result.__ctz_; 820227825Stheraven unsigned __clz_r = __bits_per_word - __result.__ctz_; 821227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 822227825Stheraven { 823227825Stheraven __storage_type __b1 = *__first.__seg_; 824227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 825227825Stheraven *__result.__seg_ &= ~__m; 826227825Stheraven *__result.__seg_ |= __b1 << __result.__ctz_; 827227825Stheraven *__first.__seg_ = __b2 >> __result.__ctz_; 828227825Stheraven ++__result.__seg_; 829227825Stheraven __b2 = *__result.__seg_ & ~__m; 830227825Stheraven *__result.__seg_ &= __m; 831227825Stheraven *__result.__seg_ |= __b1 >> __clz_r; 832227825Stheraven *__first.__seg_ |= __b2 << __clz_r; 833227825Stheraven } 834227825Stheraven // do last word 835227825Stheraven if (__n > 0) 836227825Stheraven { 837227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 838227825Stheraven __storage_type __b1 = *__first.__seg_ & __m; 839227825Stheraven *__first.__seg_ &= ~__m; 840227825Stheraven __storage_type __dn = _VSTD::min<__storage_type>(__n, __clz_r); 841227825Stheraven __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 842227825Stheraven __storage_type __b2 = *__result.__seg_ & __m; 843227825Stheraven *__result.__seg_ &= ~__m; 844227825Stheraven *__result.__seg_ |= __b1 << __result.__ctz_; 845227825Stheraven *__first.__seg_ |= __b2 >> __result.__ctz_; 846227825Stheraven __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 847227825Stheraven __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 848227825Stheraven __n -= __dn; 849227825Stheraven if (__n > 0) 850227825Stheraven { 851227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 852227825Stheraven __b2 = *__result.__seg_ & __m; 853227825Stheraven *__result.__seg_ &= ~__m; 854227825Stheraven *__result.__seg_ |= __b1 >> __dn; 855227825Stheraven *__first.__seg_ |= __b2 << __dn; 856227825Stheraven __result.__ctz_ = static_cast<unsigned>(__n); 857227825Stheraven } 858227825Stheraven } 859227825Stheraven } 860227825Stheraven return __result; 861227825Stheraven} 862227825Stheraven 863227825Stheraventemplate <class __C1, class __C2> 864227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 865227825Stheraven__bit_iterator<__C2, false> 866227825Stheravenswap_ranges(__bit_iterator<__C1, false> __first1, __bit_iterator<__C1, false> __last1, 867227825Stheraven __bit_iterator<__C2, false> __first2) 868227825Stheraven{ 869227825Stheraven if (__first1.__ctz_ == __first2.__ctz_) 870227825Stheraven return __swap_ranges_aligned(__first1, __last1, __first2); 871227825Stheraven return __swap_ranges_unaligned(__first1, __last1, __first2); 872227825Stheraven} 873227825Stheraven 874227825Stheraven// rotate 875227825Stheraven 876232950Stheraventemplate <class _Cp> 877227825Stheravenstruct __bit_array 878227825Stheraven{ 879232950Stheraven typedef typename _Cp::difference_type difference_type; 880232950Stheraven typedef typename _Cp::__storage_type __storage_type; 881253159Stheraven typedef typename _Cp::__storage_pointer __storage_pointer; 882232950Stheraven typedef typename _Cp::iterator iterator; 883232950Stheraven static const unsigned __bits_per_word = _Cp::__bits_per_word; 884232950Stheraven static const unsigned _Np = 4; 885227825Stheraven 886227825Stheraven difference_type __size_; 887232950Stheraven __storage_type __word_[_Np]; 888227825Stheraven 889227825Stheraven _LIBCPP_INLINE_VISIBILITY static difference_type capacity() 890232950Stheraven {return static_cast<difference_type>(_Np * __bits_per_word);} 891227825Stheraven _LIBCPP_INLINE_VISIBILITY explicit __bit_array(difference_type __s) : __size_(__s) {} 892253159Stheraven _LIBCPP_INLINE_VISIBILITY iterator begin() 893253159Stheraven { 894253159Stheraven return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]), 0); 895253159Stheraven } 896253159Stheraven _LIBCPP_INLINE_VISIBILITY iterator end() 897253159Stheraven { 898253159Stheraven return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]) + __size_ / __bits_per_word, 899253159Stheraven static_cast<unsigned>(__size_ % __bits_per_word)); 900253159Stheraven } 901227825Stheraven}; 902227825Stheraven 903232950Stheraventemplate <class _Cp> 904232950Stheraven__bit_iterator<_Cp, false> 905232950Stheravenrotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last) 906227825Stheraven{ 907232950Stheraven typedef __bit_iterator<_Cp, false> _I1; 908227825Stheraven typedef typename _I1::difference_type difference_type; 909227825Stheraven difference_type __d1 = __middle - __first; 910227825Stheraven difference_type __d2 = __last - __middle; 911227825Stheraven _I1 __r = __first + __d2; 912227825Stheraven while (__d1 != 0 && __d2 != 0) 913227825Stheraven { 914227825Stheraven if (__d1 <= __d2) 915227825Stheraven { 916232950Stheraven if (__d1 <= __bit_array<_Cp>::capacity()) 917227825Stheraven { 918232950Stheraven __bit_array<_Cp> __b(__d1); 919227825Stheraven _VSTD::copy(__first, __middle, __b.begin()); 920227825Stheraven _VSTD::copy(__b.begin(), __b.end(), _VSTD::copy(__middle, __last, __first)); 921227825Stheraven break; 922227825Stheraven } 923227825Stheraven else 924227825Stheraven { 925232950Stheraven __bit_iterator<_Cp, false> __mp = _VSTD::swap_ranges(__first, __middle, __middle); 926227825Stheraven __first = __middle; 927227825Stheraven __middle = __mp; 928227825Stheraven __d2 -= __d1; 929227825Stheraven } 930227825Stheraven } 931227825Stheraven else 932227825Stheraven { 933232950Stheraven if (__d2 <= __bit_array<_Cp>::capacity()) 934227825Stheraven { 935232950Stheraven __bit_array<_Cp> __b(__d2); 936227825Stheraven _VSTD::copy(__middle, __last, __b.begin()); 937227825Stheraven _VSTD::copy_backward(__b.begin(), __b.end(), _VSTD::copy_backward(__first, __middle, __last)); 938227825Stheraven break; 939227825Stheraven } 940227825Stheraven else 941227825Stheraven { 942232950Stheraven __bit_iterator<_Cp, false> __mp = __first + __d2; 943227825Stheraven _VSTD::swap_ranges(__first, __mp, __middle); 944227825Stheraven __first = __mp; 945227825Stheraven __d1 -= __d2; 946227825Stheraven } 947227825Stheraven } 948227825Stheraven } 949227825Stheraven return __r; 950227825Stheraven} 951227825Stheraven 952227825Stheraven// equal 953227825Stheraven 954241903Sdimtemplate <class _Cp, bool _IC1, bool _IC2> 955227825Stheravenbool 956241903Sdim__equal_unaligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, 957241903Sdim __bit_iterator<_Cp, _IC2> __first2) 958227825Stheraven{ 959241903Sdim typedef __bit_iterator<_Cp, _IC1> _It; 960227825Stheraven typedef typename _It::difference_type difference_type; 961227825Stheraven typedef typename _It::__storage_type __storage_type; 962227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 963227825Stheraven difference_type __n = __last1 - __first1; 964227825Stheraven if (__n > 0) 965227825Stheraven { 966227825Stheraven // do first word 967227825Stheraven if (__first1.__ctz_ != 0) 968227825Stheraven { 969227825Stheraven unsigned __clz_f = __bits_per_word - __first1.__ctz_; 970227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 971227825Stheraven __n -= __dn; 972227825Stheraven __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 973227825Stheraven __storage_type __b = *__first1.__seg_ & __m; 974227825Stheraven unsigned __clz_r = __bits_per_word - __first2.__ctz_; 975227825Stheraven __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 976227825Stheraven __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 977227825Stheraven if (__first2.__ctz_ > __first1.__ctz_) 978236387Sdim { 979227825Stheraven if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_))) 980227825Stheraven return false; 981236387Sdim } 982227825Stheraven else 983236387Sdim { 984227825Stheraven if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_))) 985227825Stheraven return false; 986236387Sdim } 987227825Stheraven __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word; 988227825Stheraven __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word); 989227825Stheraven __dn -= __ddn; 990227825Stheraven if (__dn > 0) 991227825Stheraven { 992227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __dn); 993227825Stheraven if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn))) 994227825Stheraven return false; 995227825Stheraven __first2.__ctz_ = static_cast<unsigned>(__dn); 996227825Stheraven } 997227825Stheraven ++__first1.__seg_; 998227825Stheraven // __first1.__ctz_ = 0; 999227825Stheraven } 1000227825Stheraven // __first1.__ctz_ == 0; 1001227825Stheraven // do middle words 1002227825Stheraven unsigned __clz_r = __bits_per_word - __first2.__ctz_; 1003227825Stheraven __storage_type __m = ~__storage_type(0) << __first2.__ctz_; 1004227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_) 1005227825Stheraven { 1006227825Stheraven __storage_type __b = *__first1.__seg_; 1007227825Stheraven if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 1008227825Stheraven return false; 1009227825Stheraven ++__first2.__seg_; 1010227825Stheraven if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r)) 1011227825Stheraven return false; 1012227825Stheraven } 1013227825Stheraven // do last word 1014227825Stheraven if (__n > 0) 1015227825Stheraven { 1016227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 1017227825Stheraven __storage_type __b = *__first1.__seg_ & __m; 1018227825Stheraven __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); 1019227825Stheraven __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 1020227825Stheraven if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 1021227825Stheraven return false; 1022227825Stheraven __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word; 1023227825Stheraven __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word); 1024227825Stheraven __n -= __dn; 1025227825Stheraven if (__n > 0) 1026227825Stheraven { 1027227825Stheraven __m = ~__storage_type(0) >> (__bits_per_word - __n); 1028227825Stheraven if ((*__first2.__seg_ & __m) != (__b >> __dn)) 1029227825Stheraven return false; 1030227825Stheraven } 1031227825Stheraven } 1032227825Stheraven } 1033227825Stheraven return true; 1034227825Stheraven} 1035227825Stheraven 1036241903Sdimtemplate <class _Cp, bool _IC1, bool _IC2> 1037227825Stheravenbool 1038241903Sdim__equal_aligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, 1039241903Sdim __bit_iterator<_Cp, _IC2> __first2) 1040227825Stheraven{ 1041241903Sdim typedef __bit_iterator<_Cp, _IC1> _It; 1042227825Stheraven typedef typename _It::difference_type difference_type; 1043227825Stheraven typedef typename _It::__storage_type __storage_type; 1044227825Stheraven static const unsigned __bits_per_word = _It::__bits_per_word; 1045227825Stheraven difference_type __n = __last1 - __first1; 1046227825Stheraven if (__n > 0) 1047227825Stheraven { 1048227825Stheraven // do first word 1049227825Stheraven if (__first1.__ctz_ != 0) 1050227825Stheraven { 1051227825Stheraven unsigned __clz = __bits_per_word - __first1.__ctz_; 1052227825Stheraven difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 1053227825Stheraven __n -= __dn; 1054227825Stheraven __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 1055227825Stheraven if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 1056227825Stheraven return false; 1057227825Stheraven ++__first2.__seg_; 1058227825Stheraven ++__first1.__seg_; 1059227825Stheraven // __first1.__ctz_ = 0; 1060227825Stheraven // __first2.__ctz_ = 0; 1061227825Stheraven } 1062227825Stheraven // __first1.__ctz_ == 0; 1063227825Stheraven // __first2.__ctz_ == 0; 1064227825Stheraven // do middle words 1065227825Stheraven for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_) 1066227825Stheraven if (*__first2.__seg_ != *__first1.__seg_) 1067227825Stheraven return false; 1068227825Stheraven // do last word 1069227825Stheraven if (__n > 0) 1070227825Stheraven { 1071227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 1072227825Stheraven if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 1073227825Stheraven return false; 1074227825Stheraven } 1075227825Stheraven } 1076227825Stheraven return true; 1077227825Stheraven} 1078227825Stheraven 1079232950Stheraventemplate <class _Cp, bool _IC1, bool _IC2> 1080227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1081227825Stheravenbool 1082232950Stheravenequal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) 1083227825Stheraven{ 1084227825Stheraven if (__first1.__ctz_ == __first2.__ctz_) 1085227825Stheraven return __equal_aligned(__first1, __last1, __first2); 1086227825Stheraven return __equal_unaligned(__first1, __last1, __first2); 1087227825Stheraven} 1088227825Stheraven 1089241903Sdimtemplate <class _Cp, bool _IsConst, 1090241903Sdim typename _Cp::__storage_type> 1091227825Stheravenclass __bit_iterator 1092227825Stheraven{ 1093227825Stheravenpublic: 1094232950Stheraven typedef typename _Cp::difference_type difference_type; 1095227825Stheraven typedef bool value_type; 1096227825Stheraven typedef __bit_iterator pointer; 1097232950Stheraven typedef typename conditional<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >::type reference; 1098227825Stheraven typedef random_access_iterator_tag iterator_category; 1099227825Stheraven 1100227825Stheravenprivate: 1101232950Stheraven typedef typename _Cp::__storage_type __storage_type; 1102232950Stheraven typedef typename conditional<_IsConst, typename _Cp::__const_storage_pointer, 1103232950Stheraven typename _Cp::__storage_pointer>::type __storage_pointer; 1104232950Stheraven static const unsigned __bits_per_word = _Cp::__bits_per_word; 1105227825Stheraven 1106227825Stheraven __storage_pointer __seg_; 1107227825Stheraven unsigned __ctz_; 1108227825Stheraven 1109227825Stheravenpublic: 1110262801Sdim _LIBCPP_INLINE_VISIBILITY __bit_iterator() _NOEXCEPT 1111262801Sdim#if _LIBCPP_STD_VER > 11 1112262801Sdim : __seg_(nullptr), __ctz_(0) 1113262801Sdim#endif 1114262801Sdim {} 1115227825Stheraven 1116227825Stheraven _LIBCPP_INLINE_VISIBILITY 1117232950Stheraven __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT 1118227825Stheraven : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {} 1119227825Stheraven 1120227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT 1121227825Stheraven {return reference(__seg_, __storage_type(1) << __ctz_);} 1122227825Stheraven 1123227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator++() 1124227825Stheraven { 1125227825Stheraven if (__ctz_ != __bits_per_word-1) 1126227825Stheraven ++__ctz_; 1127227825Stheraven else 1128227825Stheraven { 1129227825Stheraven __ctz_ = 0; 1130227825Stheraven ++__seg_; 1131227825Stheraven } 1132227825Stheraven return *this; 1133227825Stheraven } 1134227825Stheraven 1135227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator operator++(int) 1136227825Stheraven { 1137227825Stheraven __bit_iterator __tmp = *this; 1138227825Stheraven ++(*this); 1139227825Stheraven return __tmp; 1140227825Stheraven } 1141227825Stheraven 1142227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator--() 1143227825Stheraven { 1144227825Stheraven if (__ctz_ != 0) 1145227825Stheraven --__ctz_; 1146227825Stheraven else 1147227825Stheraven { 1148227825Stheraven __ctz_ = __bits_per_word - 1; 1149227825Stheraven --__seg_; 1150227825Stheraven } 1151227825Stheraven return *this; 1152227825Stheraven } 1153227825Stheraven 1154227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator operator--(int) 1155227825Stheraven { 1156227825Stheraven __bit_iterator __tmp = *this; 1157227825Stheraven --(*this); 1158227825Stheraven return __tmp; 1159227825Stheraven } 1160227825Stheraven 1161227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator+=(difference_type __n) 1162227825Stheraven { 1163227825Stheraven if (__n >= 0) 1164227825Stheraven __seg_ += (__n + __ctz_) / __bits_per_word; 1165227825Stheraven else 1166227825Stheraven __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1) 1167227825Stheraven / static_cast<difference_type>(__bits_per_word); 1168227825Stheraven __n &= (__bits_per_word - 1); 1169227825Stheraven __ctz_ = static_cast<unsigned>((__n + __ctz_) % __bits_per_word); 1170227825Stheraven return *this; 1171227825Stheraven } 1172227825Stheraven 1173227825Stheraven _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator-=(difference_type __n) 1174227825Stheraven { 1175227825Stheraven return *this += -__n; 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 __bit_iterator operator-(difference_type __n) const 1186227825Stheraven { 1187227825Stheraven __bit_iterator __t(*this); 1188227825Stheraven __t -= __n; 1189227825Stheraven return __t; 1190227825Stheraven } 1191227825Stheraven 1192227825Stheraven _LIBCPP_INLINE_VISIBILITY 1193227825Stheraven friend __bit_iterator operator+(difference_type __n, const __bit_iterator& __it) {return __it + __n;} 1194227825Stheraven 1195227825Stheraven _LIBCPP_INLINE_VISIBILITY 1196227825Stheraven friend difference_type operator-(const __bit_iterator& __x, const __bit_iterator& __y) 1197227825Stheraven {return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;} 1198227825Stheraven 1199227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const {return *(*this + __n);} 1200227825Stheraven 1201227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator==(const __bit_iterator& __x, const __bit_iterator& __y) 1202227825Stheraven {return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;} 1203227825Stheraven 1204227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator!=(const __bit_iterator& __x, const __bit_iterator& __y) 1205227825Stheraven {return !(__x == __y);} 1206227825Stheraven 1207227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator<(const __bit_iterator& __x, const __bit_iterator& __y) 1208227825Stheraven {return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);} 1209227825Stheraven 1210227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator>(const __bit_iterator& __x, const __bit_iterator& __y) 1211227825Stheraven {return __y < __x;} 1212227825Stheraven 1213227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y) 1214227825Stheraven {return !(__y < __x);} 1215227825Stheraven 1216227825Stheraven _LIBCPP_INLINE_VISIBILITY friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y) 1217227825Stheraven {return !(__x < __y);} 1218227825Stheraven 1219227825Stheravenprivate: 1220227825Stheraven _LIBCPP_INLINE_VISIBILITY 1221227825Stheraven __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT 1222227825Stheraven : __seg_(__s), __ctz_(__ctz) {} 1223227825Stheraven 1224262801Sdim#if defined(__clang__) || defined(__IBMCPP__) || defined(_LIBCPP_MSVC) 1225232950Stheraven friend typename _Cp::__self; 1226227825Stheraven#else 1227232950Stheraven friend class _Cp::__self; 1228227825Stheraven#endif 1229232950Stheraven friend class __bit_reference<_Cp>; 1230232950Stheraven friend class __bit_const_reference<_Cp>; 1231232950Stheraven friend class __bit_iterator<_Cp, true>; 1232232950Stheraven template <class _Dp> friend struct __bit_array; 1233232950Stheraven template <class _Dp> friend void __fill_n_false(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); 1234232950Stheraven template <class _Dp> friend void __fill_n_true(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); 1235232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_aligned(__bit_iterator<_Dp, _IC> __first, 1236232950Stheraven __bit_iterator<_Dp, _IC> __last, 1237232950Stheraven __bit_iterator<_Dp, false> __result); 1238232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_unaligned(__bit_iterator<_Dp, _IC> __first, 1239232950Stheraven __bit_iterator<_Dp, _IC> __last, 1240232950Stheraven __bit_iterator<_Dp, false> __result); 1241232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy(__bit_iterator<_Dp, _IC> __first, 1242232950Stheraven __bit_iterator<_Dp, _IC> __last, 1243232950Stheraven __bit_iterator<_Dp, false> __result); 1244232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_aligned(__bit_iterator<_Dp, _IC> __first, 1245232950Stheraven __bit_iterator<_Dp, _IC> __last, 1246232950Stheraven __bit_iterator<_Dp, false> __result); 1247232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_unaligned(__bit_iterator<_Dp, _IC> __first, 1248232950Stheraven __bit_iterator<_Dp, _IC> __last, 1249232950Stheraven __bit_iterator<_Dp, false> __result); 1250232950Stheraven template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy_backward(__bit_iterator<_Dp, _IC> __first, 1251232950Stheraven __bit_iterator<_Dp, _IC> __last, 1252232950Stheraven __bit_iterator<_Dp, false> __result); 1253227825Stheraven template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_aligned(__bit_iterator<__C1, false>, 1254227825Stheraven __bit_iterator<__C1, false>, 1255227825Stheraven __bit_iterator<__C2, false>); 1256227825Stheraven template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_unaligned(__bit_iterator<__C1, false>, 1257227825Stheraven __bit_iterator<__C1, false>, 1258227825Stheraven __bit_iterator<__C2, false>); 1259227825Stheraven template <class __C1, class __C2>friend __bit_iterator<__C2, false> swap_ranges(__bit_iterator<__C1, false>, 1260227825Stheraven __bit_iterator<__C1, false>, 1261227825Stheraven __bit_iterator<__C2, false>); 1262232950Stheraven template <class _Dp> friend __bit_iterator<_Dp, false> rotate(__bit_iterator<_Dp, false>, 1263232950Stheraven __bit_iterator<_Dp, false>, 1264232950Stheraven __bit_iterator<_Dp, false>); 1265241903Sdim template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_aligned(__bit_iterator<_Dp, _IC1>, 1266241903Sdim __bit_iterator<_Dp, _IC1>, 1267241903Sdim __bit_iterator<_Dp, _IC2>); 1268241903Sdim template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_unaligned(__bit_iterator<_Dp, _IC1>, 1269241903Sdim __bit_iterator<_Dp, _IC1>, 1270241903Sdim __bit_iterator<_Dp, _IC2>); 1271232950Stheraven template <class _Dp, bool _IC1, bool _IC2> friend bool equal(__bit_iterator<_Dp, _IC1>, 1272232950Stheraven __bit_iterator<_Dp, _IC1>, 1273232950Stheraven __bit_iterator<_Dp, _IC2>); 1274241903Sdim template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_true(__bit_iterator<_Dp, _IC>, 1275232950Stheraven typename _Dp::size_type); 1276241903Sdim template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_false(__bit_iterator<_Dp, _IC>, 1277232950Stheraven typename _Dp::size_type); 1278241903Sdim template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type 1279241903Sdim __count_bool_true(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 1280241903Sdim template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type 1281241903Sdim __count_bool_false(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 1282227825Stheraven}; 1283227825Stheraven 1284227825Stheraven_LIBCPP_END_NAMESPACE_STD 1285227825Stheraven 1286227825Stheraven#endif // _LIBCPP___BIT_REFERENCE 1287