1// -*- C++ -*- 2//===----------------------------------------------------------------------===// 3// 4// The LLVM Compiler Infrastructure 5// 6// This file is dual licensed under the MIT and the University of Illinois Open 7// Source Licenses. See LICENSE.TXT for details. 8// 9//===----------------------------------------------------------------------===// 10 11#ifndef _LIBCPP___BIT_REFERENCE 12#define _LIBCPP___BIT_REFERENCE 13 14#include <__config> 15#include <algorithm> 16 17#pragma GCC system_header 18 19_LIBCPP_BEGIN_NAMESPACE_STD 20 21template <class _C, bool _IsConst> class __bit_iterator; 22template <class _C> class __bit_const_reference; 23 24template <class _C> 25class __bit_reference 26{ 27 typedef typename _C::__storage_type __storage_type; 28 typedef typename _C::__storage_pointer __storage_pointer; 29 30 __storage_pointer __seg_; 31 __storage_type __mask_; 32 33#if defined(__clang__) 34 friend typename _C::__self; 35#else 36 friend class _C::__self; 37#endif 38 friend class __bit_const_reference<_C>; 39 friend class __bit_iterator<_C, false>; 40public: 41 _LIBCPP_INLINE_VISIBILITY operator bool() const _NOEXCEPT 42 {return static_cast<bool>(*__seg_ & __mask_);} 43 _LIBCPP_INLINE_VISIBILITY bool operator ~() const _NOEXCEPT 44 {return !static_cast<bool>(*this);} 45 46 _LIBCPP_INLINE_VISIBILITY 47 __bit_reference& operator=(bool __x) _NOEXCEPT 48 { 49 if (__x) 50 *__seg_ |= __mask_; 51 else 52 *__seg_ &= ~__mask_; 53 return *this; 54 } 55 56 _LIBCPP_INLINE_VISIBILITY 57 __bit_reference& operator=(const __bit_reference& __x) _NOEXCEPT 58 {return operator=(static_cast<bool>(__x));} 59 60 _LIBCPP_INLINE_VISIBILITY void flip() _NOEXCEPT {*__seg_ ^= __mask_;} 61 _LIBCPP_INLINE_VISIBILITY __bit_iterator<_C, false> operator&() const _NOEXCEPT 62 {return __bit_iterator<_C, false>(__seg_, static_cast<unsigned>(__ctz(__mask_)));} 63private: 64 _LIBCPP_INLINE_VISIBILITY 65 __bit_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT 66 : __seg_(__s), __mask_(__m) {} 67}; 68 69template <class _C, class _D> 70_LIBCPP_INLINE_VISIBILITY inline 71void 72swap(__bit_reference<_C> __x, __bit_reference<_D> __y) _NOEXCEPT 73{ 74 bool __t = __x; 75 __x = __y; 76 __y = __t; 77} 78 79template <class _C> 80_LIBCPP_INLINE_VISIBILITY inline 81void 82swap(__bit_reference<_C> __x, bool& __y) _NOEXCEPT 83{ 84 bool __t = __x; 85 __x = __y; 86 __y = __t; 87} 88 89template <class _C> 90_LIBCPP_INLINE_VISIBILITY inline 91void 92swap(bool& __x, __bit_reference<_C> __y) _NOEXCEPT 93{ 94 bool __t = __x; 95 __x = __y; 96 __y = __t; 97} 98 99template <class _C> 100class __bit_const_reference 101{ 102 typedef typename _C::__storage_type __storage_type; 103 typedef typename _C::__const_storage_pointer __storage_pointer; 104 105 __storage_pointer __seg_; 106 __storage_type __mask_; 107 108#if defined(__clang__) 109 friend typename _C::__self; 110#else 111 friend class _C::__self; 112#endif 113 friend class __bit_iterator<_C, true>; 114public: 115 _LIBCPP_INLINE_VISIBILITY 116 __bit_const_reference(const __bit_reference<_C>& __x) _NOEXCEPT 117 : __seg_(__x.__seg_), __mask_(__x.__mask_) {} 118 119 _LIBCPP_INLINE_VISIBILITY operator bool() const _NOEXCEPT 120 {return static_cast<bool>(*__seg_ & __mask_);} 121 122 _LIBCPP_INLINE_VISIBILITY __bit_iterator<_C, true> operator&() const _NOEXCEPT 123 {return __bit_iterator<_C, true>(__seg_, static_cast<unsigned>(__ctz(__mask_)));} 124private: 125 _LIBCPP_INLINE_VISIBILITY 126 __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT 127 : __seg_(__s), __mask_(__m) {} 128 129 __bit_const_reference& operator=(const __bit_const_reference& __x); 130}; 131 132// find 133 134template <class _C> 135__bit_iterator<_C, false> 136__find_bool_true(__bit_iterator<_C, false> __first, typename _C::size_type __n) 137{ 138 typedef __bit_iterator<_C, false> _It; 139 typedef typename _It::__storage_type __storage_type; 140 static const unsigned __bits_per_word = _It::__bits_per_word; 141 // do first partial word 142 if (__first.__ctz_ != 0) 143 { 144 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 145 __storage_type __dn = _STD::min(__clz_f, __n); 146 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 147 __storage_type __b = *__first.__seg_ & __m; 148 if (__b) 149 return _It(__first.__seg_, static_cast<unsigned>(_STD::__ctz(__b))); 150 __n -= __dn; 151 ++__first.__seg_; 152 } 153 // do middle whole words 154 for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 155 if (*__first.__seg_) 156 return _It(__first.__seg_, static_cast<unsigned>(_STD::__ctz(*__first.__seg_))); 157 // do last partial word 158 if (__n > 0) 159 { 160 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 161 __storage_type __b = *__first.__seg_ & __m; 162 if (__b) 163 return _It(__first.__seg_, static_cast<unsigned>(_STD::__ctz(__b))); 164 } 165 return _It(__first.__seg_, static_cast<unsigned>(__n)); 166} 167 168template <class _C> 169__bit_iterator<_C, false> 170__find_bool_false(__bit_iterator<_C, false> __first, typename _C::size_type __n) 171{ 172 typedef __bit_iterator<_C, false> _It; 173 typedef typename _It::__storage_type __storage_type; 174 static const unsigned __bits_per_word = _It::__bits_per_word; 175 // do first partial word 176 if (__first.__ctz_ != 0) 177 { 178 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 179 __storage_type __dn = _STD::min(__clz_f, __n); 180 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 181 __storage_type __b = ~(*__first.__seg_ & __m); 182 if (__b) 183 return _It(__first.__seg_, static_cast<unsigned>(_STD::__ctz(__b))); 184 __n -= __dn; 185 ++__first.__seg_; 186 } 187 // do middle whole words 188 for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 189 { 190 __storage_type __b = ~*__first.__seg_; 191 if (__b) 192 return _It(__first.__seg_, static_cast<unsigned>(_STD::__ctz(__b))); 193 } 194 // do last partial word 195 if (__n > 0) 196 { 197 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 198 __storage_type __b = ~(*__first.__seg_ & __m); 199 if (__b) 200 return _It(__first.__seg_, static_cast<unsigned>(_STD::__ctz(__b))); 201 } 202 return _It(__first.__seg_, static_cast<unsigned>(__n)); 203} 204 205template <class _C, class _Tp> 206inline _LIBCPP_INLINE_VISIBILITY 207__bit_iterator<_C, false> 208find(__bit_iterator<_C, false> __first, __bit_iterator<_C, false> __last, const _Tp& __value) 209{ 210 if (static_cast<bool>(__value)) 211 return __find_bool_true(__first, static_cast<typename _C::size_type>(__last - __first)); 212 return __find_bool_false(__first, static_cast<typename _C::size_type>(__last - __first)); 213} 214 215// count 216 217template <class _C> 218typename __bit_iterator<_C, false>::difference_type 219__count_bool_true(__bit_iterator<_C, false> __first, typename _C::size_type __n) 220{ 221 typedef __bit_iterator<_C, false> _It; 222 typedef typename _It::__storage_type __storage_type; 223 typedef typename _It::difference_type difference_type; 224 static const unsigned __bits_per_word = _It::__bits_per_word; 225 difference_type __r = 0; 226 // do first partial word 227 if (__first.__ctz_ != 0) 228 { 229 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 230 __storage_type __dn = _STD::min(__clz_f, __n); 231 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 232 __r = _STD::__pop_count(*__first.__seg_ & __m); 233 __n -= __dn; 234 ++__first.__seg_; 235 } 236 // do middle whole words 237 for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 238 __r += _STD::__pop_count(*__first.__seg_); 239 // do last partial word 240 if (__n > 0) 241 { 242 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 243 __r += _STD::__pop_count(*__first.__seg_ & __m); 244 } 245 return __r; 246} 247 248template <class _C> 249typename __bit_iterator<_C, false>::difference_type 250__count_bool_false(__bit_iterator<_C, false> __first, typename _C::size_type __n) 251{ 252 typedef __bit_iterator<_C, false> _It; 253 typedef typename _It::__storage_type __storage_type; 254 typedef typename _It::difference_type difference_type; 255 static const unsigned __bits_per_word = _It::__bits_per_word; 256 difference_type __r = 0; 257 // do first partial word 258 if (__first.__ctz_ != 0) 259 { 260 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 261 __storage_type __dn = _STD::min(__clz_f, __n); 262 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 263 __r = _STD::__pop_count(~(*__first.__seg_ & __m)); 264 __n -= __dn; 265 ++__first.__seg_; 266 } 267 // do middle whole words 268 for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 269 __r += _STD::__pop_count(~*__first.__seg_); 270 // do last partial word 271 if (__n > 0) 272 { 273 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 274 __r += _STD::__pop_count(~(*__first.__seg_ & __m)); 275 } 276 return __r; 277} 278 279template <class _C, class _Tp> 280inline _LIBCPP_INLINE_VISIBILITY 281typename __bit_iterator<_C, false>::difference_type 282count(__bit_iterator<_C, false> __first, __bit_iterator<_C, false> __last, const _Tp& __value) 283{ 284 if (static_cast<bool>(__value)) 285 return __count_bool_true(__first, static_cast<typename _C::size_type>(__last - __first)); 286 return __count_bool_false(__first, static_cast<typename _C::size_type>(__last - __first)); 287} 288 289// fill_n 290 291template <class _C> 292void 293__fill_n_false(__bit_iterator<_C, false> __first, typename _C::size_type __n) 294{ 295 typedef __bit_iterator<_C, false> _It; 296 typedef typename _It::__storage_type __storage_type; 297 static const unsigned __bits_per_word = _It::__bits_per_word; 298 // do first partial word 299 if (__first.__ctz_ != 0) 300 { 301 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 302 __storage_type __dn = _STD::min(__clz_f, __n); 303 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 304 *__first.__seg_ &= ~__m; 305 __n -= __dn; 306 ++__first.__seg_; 307 } 308 // do middle whole words 309 __storage_type __nw = __n / __bits_per_word; 310 _STD::memset(__first.__seg_, 0, __nw * sizeof(__storage_type)); 311 __n -= __nw * __bits_per_word; 312 // do last partial word 313 if (__n > 0) 314 { 315 __first.__seg_ += __nw; 316 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 317 *__first.__seg_ &= ~__m; 318 } 319} 320 321template <class _C> 322void 323__fill_n_true(__bit_iterator<_C, false> __first, typename _C::size_type __n) 324{ 325 typedef __bit_iterator<_C, false> _It; 326 typedef typename _It::__storage_type __storage_type; 327 static const unsigned __bits_per_word = _It::__bits_per_word; 328 // do first partial word 329 if (__first.__ctz_ != 0) 330 { 331 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 332 __storage_type __dn = _STD::min(__clz_f, __n); 333 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 334 *__first.__seg_ |= __m; 335 __n -= __dn; 336 ++__first.__seg_; 337 } 338 // do middle whole words 339 __storage_type __nw = __n / __bits_per_word; 340 _STD::memset(__first.__seg_, -1, __nw * sizeof(__storage_type)); 341 __n -= __nw * __bits_per_word; 342 // do last partial word 343 if (__n > 0) 344 { 345 __first.__seg_ += __nw; 346 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 347 *__first.__seg_ |= __m; 348 } 349} 350 351template <class _C> 352_LIBCPP_INLINE_VISIBILITY inline 353void 354fill_n(__bit_iterator<_C, false> __first, typename _C::size_type __n, bool __value) 355{ 356 if (__n > 0) 357 { 358 if (__value) 359 __fill_n_true(__first, __n); 360 else 361 __fill_n_false(__first, __n); 362 } 363} 364 365// fill 366 367template <class _C> 368inline _LIBCPP_INLINE_VISIBILITY 369void 370fill(__bit_iterator<_C, false> __first, __bit_iterator<_C, false> __last, bool __value) 371{ 372 _STD::fill_n(__first, static_cast<typename _C::size_type>(__last - __first), __value); 373} 374 375// copy 376 377template <class _C, bool _IsConst> 378__bit_iterator<_C, false> 379__copy_aligned(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, 380 __bit_iterator<_C, false> __result) 381{ 382 typedef __bit_iterator<_C, _IsConst> _In; 383 typedef typename _In::difference_type difference_type; 384 typedef typename _In::__storage_type __storage_type; 385 static const unsigned __bits_per_word = _In::__bits_per_word; 386 difference_type __n = __last - __first; 387 if (__n > 0) 388 { 389 // do first word 390 if (__first.__ctz_ != 0) 391 { 392 unsigned __clz = __bits_per_word - __first.__ctz_; 393 difference_type __dn = _STD::min(static_cast<difference_type>(__clz), __n); 394 __n -= __dn; 395 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 396 __storage_type __b = *__first.__seg_ & __m; 397 *__result.__seg_ &= ~__m; 398 *__result.__seg_ |= __b; 399 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 400 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 401 ++__first.__seg_; 402 // __first.__ctz_ = 0; 403 } 404 // __first.__ctz_ == 0; 405 // do middle words 406 __storage_type __nw = __n / __bits_per_word; 407 _STD::memmove(__result.__seg_, __first.__seg_, __nw * sizeof(__storage_type)); 408 __n -= __nw * __bits_per_word; 409 __result.__seg_ += __nw; 410 // do last word 411 if (__n > 0) 412 { 413 __first.__seg_ += __nw; 414 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 415 __storage_type __b = *__first.__seg_ & __m; 416 *__result.__seg_ &= ~__m; 417 *__result.__seg_ |= __b; 418 __result.__ctz_ = static_cast<unsigned>(__n); 419 } 420 } 421 return __result; 422} 423 424template <class _C, bool _IsConst> 425__bit_iterator<_C, false> 426__copy_unaligned(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, 427 __bit_iterator<_C, false> __result) 428{ 429 typedef __bit_iterator<_C, _IsConst> _In; 430 typedef typename _In::difference_type difference_type; 431 typedef typename _In::__storage_type __storage_type; 432 static const unsigned __bits_per_word = _In::__bits_per_word; 433 difference_type __n = __last - __first; 434 if (__n > 0) 435 { 436 // do first word 437 if (__first.__ctz_ != 0) 438 { 439 unsigned __clz_f = __bits_per_word - __first.__ctz_; 440 difference_type __dn = _STD::min(static_cast<difference_type>(__clz_f), __n); 441 __n -= __dn; 442 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 443 __storage_type __b = *__first.__seg_ & __m; 444 unsigned __clz_r = __bits_per_word - __result.__ctz_; 445 __storage_type __ddn = _STD::min<__storage_type>(__dn, __clz_r); 446 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 447 *__result.__seg_ &= ~__m; 448 if (__result.__ctz_ > __first.__ctz_) 449 *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_); 450 else 451 *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_); 452 __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 453 __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 454 __dn -= __ddn; 455 if (__dn > 0) 456 { 457 __m = ~__storage_type(0) >> (__bits_per_word - __dn); 458 *__result.__seg_ &= ~__m; 459 *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn); 460 __result.__ctz_ = static_cast<unsigned>(__dn); 461 } 462 ++__first.__seg_; 463 // __first.__ctz_ = 0; 464 } 465 // __first.__ctz_ == 0; 466 // do middle words 467 unsigned __clz_r = __bits_per_word - __result.__ctz_; 468 __storage_type __m = ~__storage_type(0) << __result.__ctz_; 469 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 470 { 471 __storage_type __b = *__first.__seg_; 472 *__result.__seg_ &= ~__m; 473 *__result.__seg_ |= __b << __result.__ctz_; 474 ++__result.__seg_; 475 *__result.__seg_ &= __m; 476 *__result.__seg_ |= __b >> __clz_r; 477 } 478 // do last word 479 if (__n > 0) 480 { 481 __m = ~__storage_type(0) >> (__bits_per_word - __n); 482 __storage_type __b = *__first.__seg_ & __m; 483 __storage_type __dn = _STD::min(__n, static_cast<difference_type>(__clz_r)); 484 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 485 *__result.__seg_ &= ~__m; 486 *__result.__seg_ |= __b << __result.__ctz_; 487 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 488 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 489 __n -= __dn; 490 if (__n > 0) 491 { 492 __m = ~__storage_type(0) >> (__bits_per_word - __n); 493 *__result.__seg_ &= ~__m; 494 *__result.__seg_ |= __b >> __dn; 495 __result.__ctz_ = static_cast<unsigned>(__n); 496 } 497 } 498 } 499 return __result; 500} 501 502template <class _C, bool _IsConst> 503inline _LIBCPP_INLINE_VISIBILITY 504__bit_iterator<_C, false> 505copy(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, __bit_iterator<_C, false> __result) 506{ 507 if (__first.__ctz_ == __result.__ctz_) 508 return __copy_aligned(__first, __last, __result); 509 return __copy_unaligned(__first, __last, __result); 510} 511 512// copy_backward 513 514template <class _C, bool _IsConst> 515__bit_iterator<_C, false> 516__copy_backward_aligned(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, 517 __bit_iterator<_C, false> __result) 518{ 519 typedef __bit_iterator<_C, _IsConst> _In; 520 typedef typename _In::difference_type difference_type; 521 typedef typename _In::__storage_type __storage_type; 522 static const unsigned __bits_per_word = _In::__bits_per_word; 523 difference_type __n = __last - __first; 524 if (__n > 0) 525 { 526 // do first word 527 if (__last.__ctz_ != 0) 528 { 529 difference_type __dn = _STD::min(static_cast<difference_type>(__last.__ctz_), __n); 530 __n -= __dn; 531 unsigned __clz = __bits_per_word - __last.__ctz_; 532 __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz); 533 __storage_type __b = *__last.__seg_ & __m; 534 *__result.__seg_ &= ~__m; 535 *__result.__seg_ |= __b; 536 __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 537 __result.__ctz_) % __bits_per_word); 538 // __last.__ctz_ = 0 539 } 540 // __last.__ctz_ == 0 || __n == 0 541 // __result.__ctz_ == 0 || __n == 0 542 // do middle words 543 __storage_type __nw = __n / __bits_per_word; 544 __result.__seg_ -= __nw; 545 __last.__seg_ -= __nw; 546 _STD::memmove(__result.__seg_, __last.__seg_, __nw * sizeof(__storage_type)); 547 __n -= __nw * __bits_per_word; 548 // do last word 549 if (__n > 0) 550 { 551 __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n); 552 __storage_type __b = *--__last.__seg_ & __m; 553 *--__result.__seg_ &= ~__m; 554 *__result.__seg_ |= __b; 555 __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 556 } 557 } 558 return __result; 559} 560 561template <class _C, bool _IsConst> 562__bit_iterator<_C, false> 563__copy_backward_unaligned(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, 564 __bit_iterator<_C, false> __result) 565{ 566 typedef __bit_iterator<_C, _IsConst> _In; 567 typedef typename _In::difference_type difference_type; 568 typedef typename _In::__storage_type __storage_type; 569 static const unsigned __bits_per_word = _In::__bits_per_word; 570 difference_type __n = __last - __first; 571 if (__n > 0) 572 { 573 // do first word 574 if (__last.__ctz_ != 0) 575 { 576 difference_type __dn = _STD::min(static_cast<difference_type>(__last.__ctz_), __n); 577 __n -= __dn; 578 unsigned __clz_l = __bits_per_word - __last.__ctz_; 579 __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l); 580 __storage_type __b = *__last.__seg_ & __m; 581 unsigned __clz_r = __bits_per_word - __result.__ctz_; 582 __storage_type __ddn = _STD::min(__dn, static_cast<difference_type>(__result.__ctz_)); 583 if (__ddn > 0) 584 { 585 __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r); 586 *__result.__seg_ &= ~__m; 587 if (__result.__ctz_ > __last.__ctz_) 588 *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 589 else 590 *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_); 591 __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) + 592 __result.__ctz_) % __bits_per_word); 593 __dn -= __ddn; 594 } 595 if (__dn > 0) 596 { 597 // __result.__ctz_ == 0 598 --__result.__seg_; 599 __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1)); 600 __m = ~__storage_type(0) << __result.__ctz_; 601 *__result.__seg_ &= ~__m; 602 __last.__ctz_ -= __dn + __ddn; 603 *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 604 } 605 // __last.__ctz_ = 0 606 } 607 // __last.__ctz_ == 0 || __n == 0 608 // __result.__ctz_ != 0 || __n == 0 609 // do middle words 610 unsigned __clz_r = __bits_per_word - __result.__ctz_; 611 __storage_type __m = ~__storage_type(0) >> __clz_r; 612 for (; __n >= __bits_per_word; __n -= __bits_per_word) 613 { 614 __storage_type __b = *--__last.__seg_; 615 *__result.__seg_ &= ~__m; 616 *__result.__seg_ |= __b >> __clz_r; 617 *--__result.__seg_ &= __m; 618 *__result.__seg_ |= __b << __result.__ctz_; 619 } 620 // do last word 621 if (__n > 0) 622 { 623 __m = ~__storage_type(0) << (__bits_per_word - __n); 624 __storage_type __b = *--__last.__seg_ & __m; 625 unsigned __clz_r = __bits_per_word - __result.__ctz_; 626 __storage_type __dn = _STD::min(__n, static_cast<difference_type>(__result.__ctz_)); 627 __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r); 628 *__result.__seg_ &= ~__m; 629 *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_); 630 __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 631 __result.__ctz_) % __bits_per_word); 632 __n -= __dn; 633 if (__n > 0) 634 { 635 // __result.__ctz_ == 0 636 --__result.__seg_; 637 __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 638 __m = ~__storage_type(0) << __result.__ctz_; 639 *__result.__seg_ &= ~__m; 640 *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn)); 641 } 642 } 643 } 644 return __result; 645} 646 647template <class _C, bool _IsConst> 648inline _LIBCPP_INLINE_VISIBILITY 649__bit_iterator<_C, false> 650copy_backward(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, __bit_iterator<_C, false> __result) 651{ 652 if (__last.__ctz_ == __result.__ctz_) 653 return __copy_backward_aligned(__first, __last, __result); 654 return __copy_backward_unaligned(__first, __last, __result); 655} 656 657// move 658 659template <class _C, bool _IsConst> 660inline _LIBCPP_INLINE_VISIBILITY 661__bit_iterator<_C, false> 662move(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, __bit_iterator<_C, false> __result) 663{ 664 return _STD::copy(__first, __last, __result); 665} 666 667// move_backward 668 669template <class _C, bool _IsConst> 670inline _LIBCPP_INLINE_VISIBILITY 671__bit_iterator<_C, false> 672move_backward(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, __bit_iterator<_C, false> __result) 673{ 674 return _STD::copy(__first, __last, __result); 675} 676 677// swap_ranges 678 679template <class _C1, class _C2> 680__bit_iterator<_C2, false> 681__swap_ranges_aligned(__bit_iterator<_C1, false> __first, __bit_iterator<_C1, false> __last, 682 __bit_iterator<_C2, false> __result) 683{ 684 typedef __bit_iterator<_C1, false> _I1; 685 typedef typename _I1::difference_type difference_type; 686 typedef typename _I1::__storage_type __storage_type; 687 static const unsigned __bits_per_word = _I1::__bits_per_word; 688 difference_type __n = __last - __first; 689 if (__n > 0) 690 { 691 // do first word 692 if (__first.__ctz_ != 0) 693 { 694 unsigned __clz = __bits_per_word - __first.__ctz_; 695 difference_type __dn = _STD::min(static_cast<difference_type>(__clz), __n); 696 __n -= __dn; 697 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 698 __storage_type __b1 = *__first.__seg_ & __m; 699 *__first.__seg_ &= ~__m; 700 __storage_type __b2 = *__result.__seg_ & __m; 701 *__result.__seg_ &= ~__m; 702 *__result.__seg_ |= __b1; 703 *__first.__seg_ |= __b2; 704 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 705 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 706 ++__first.__seg_; 707 // __first.__ctz_ = 0; 708 } 709 // __first.__ctz_ == 0; 710 // do middle words 711 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_) 712 swap(*__first.__seg_, *__result.__seg_); 713 // do last word 714 if (__n > 0) 715 { 716 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 717 __storage_type __b1 = *__first.__seg_ & __m; 718 *__first.__seg_ &= ~__m; 719 __storage_type __b2 = *__result.__seg_ & __m; 720 *__result.__seg_ &= ~__m; 721 *__result.__seg_ |= __b1; 722 *__first.__seg_ |= __b2; 723 __result.__ctz_ = static_cast<unsigned>(__n); 724 } 725 } 726 return __result; 727} 728 729template <class _C1, class _C2> 730__bit_iterator<_C2, false> 731__swap_ranges_unaligned(__bit_iterator<_C1, false> __first, __bit_iterator<_C1, false> __last, 732 __bit_iterator<_C2, false> __result) 733{ 734 typedef __bit_iterator<_C1, false> _I1; 735 typedef typename _I1::difference_type difference_type; 736 typedef typename _I1::__storage_type __storage_type; 737 static const unsigned __bits_per_word = _I1::__bits_per_word; 738 difference_type __n = __last - __first; 739 if (__n > 0) 740 { 741 // do first word 742 if (__first.__ctz_ != 0) 743 { 744 unsigned __clz_f = __bits_per_word - __first.__ctz_; 745 difference_type __dn = _STD::min(static_cast<difference_type>(__clz_f), __n); 746 __n -= __dn; 747 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 748 __storage_type __b1 = *__first.__seg_ & __m; 749 *__first.__seg_ &= ~__m; 750 unsigned __clz_r = __bits_per_word - __result.__ctz_; 751 __storage_type __ddn = _STD::min<__storage_type>(__dn, __clz_r); 752 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 753 __storage_type __b2 = *__result.__seg_ & __m; 754 *__result.__seg_ &= ~__m; 755 if (__result.__ctz_ > __first.__ctz_) 756 { 757 unsigned __s = __result.__ctz_ - __first.__ctz_; 758 *__result.__seg_ |= __b1 << __s; 759 *__first.__seg_ |= __b2 >> __s; 760 } 761 else 762 { 763 unsigned __s = __first.__ctz_ - __result.__ctz_; 764 *__result.__seg_ |= __b1 >> __s; 765 *__first.__seg_ |= __b2 << __s; 766 } 767 __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 768 __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 769 __dn -= __ddn; 770 if (__dn > 0) 771 { 772 __m = ~__storage_type(0) >> (__bits_per_word - __dn); 773 __b2 = *__result.__seg_ & __m; 774 *__result.__seg_ &= ~__m; 775 unsigned __s = __first.__ctz_ + __ddn; 776 *__result.__seg_ |= __b1 >> __s; 777 *__first.__seg_ |= __b2 << __s; 778 __result.__ctz_ = static_cast<unsigned>(__dn); 779 } 780 ++__first.__seg_; 781 // __first.__ctz_ = 0; 782 } 783 // __first.__ctz_ == 0; 784 // do middle words 785 __storage_type __m = ~__storage_type(0) << __result.__ctz_; 786 unsigned __clz_r = __bits_per_word - __result.__ctz_; 787 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 788 { 789 __storage_type __b1 = *__first.__seg_; 790 __storage_type __b2 = *__result.__seg_ & __m; 791 *__result.__seg_ &= ~__m; 792 *__result.__seg_ |= __b1 << __result.__ctz_; 793 *__first.__seg_ = __b2 >> __result.__ctz_; 794 ++__result.__seg_; 795 __b2 = *__result.__seg_ & ~__m; 796 *__result.__seg_ &= __m; 797 *__result.__seg_ |= __b1 >> __clz_r; 798 *__first.__seg_ |= __b2 << __clz_r; 799 } 800 // do last word 801 if (__n > 0) 802 { 803 __m = ~__storage_type(0) >> (__bits_per_word - __n); 804 __storage_type __b1 = *__first.__seg_ & __m; 805 *__first.__seg_ &= ~__m; 806 __storage_type __dn = _STD::min<__storage_type>(__n, __clz_r); 807 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 808 __storage_type __b2 = *__result.__seg_ & __m; 809 *__result.__seg_ &= ~__m; 810 *__result.__seg_ |= __b1 << __result.__ctz_; 811 *__first.__seg_ |= __b2 >> __result.__ctz_; 812 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 813 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 814 __n -= __dn; 815 if (__n > 0) 816 { 817 __m = ~__storage_type(0) >> (__bits_per_word - __n); 818 __b2 = *__result.__seg_ & __m; 819 *__result.__seg_ &= ~__m; 820 *__result.__seg_ |= __b1 >> __dn; 821 *__first.__seg_ |= __b2 << __dn; 822 __result.__ctz_ = static_cast<unsigned>(__n); 823 } 824 } 825 } 826 return __result; 827} 828 829template <class _C1, class _C2> 830inline _LIBCPP_INLINE_VISIBILITY 831__bit_iterator<_C2, false> 832swap_ranges(__bit_iterator<_C1, false> __first1, __bit_iterator<_C1, false> __last1, 833 __bit_iterator<_C2, false> __first2) 834{ 835 if (__first1.__ctz_ == __first2.__ctz_) 836 return __swap_ranges_aligned(__first1, __last1, __first2); 837 return __swap_ranges_unaligned(__first1, __last1, __first2); 838} 839 840// rotate 841 842template <class _C> 843struct __bit_array 844{ 845 typedef typename _C::difference_type difference_type; 846 typedef typename _C::__storage_type __storage_type; 847 typedef typename _C::iterator iterator; 848 static const unsigned __bits_per_word = _C::__bits_per_word; 849 static const unsigned _N = 4; 850 851 difference_type __size_; 852 __storage_type __word_[_N]; 853 854 _LIBCPP_INLINE_VISIBILITY static difference_type capacity() 855 {return static_cast<difference_type>(_N * __bits_per_word);} 856 _LIBCPP_INLINE_VISIBILITY explicit __bit_array(difference_type __s) : __size_(__s) {} 857 _LIBCPP_INLINE_VISIBILITY iterator begin() {return iterator(__word_, 0);} 858 _LIBCPP_INLINE_VISIBILITY iterator end() {return iterator(__word_ + __size_ / __bits_per_word, 859 static_cast<unsigned>(__size_ % __bits_per_word));} 860}; 861 862template <class _C> 863__bit_iterator<_C, false> 864rotate(__bit_iterator<_C, false> __first, __bit_iterator<_C, false> __middle, __bit_iterator<_C, false> __last) 865{ 866 typedef __bit_iterator<_C, false> _I1; 867 typedef typename _I1::difference_type difference_type; 868 typedef typename _I1::__storage_type __storage_type; 869 static const unsigned __bits_per_word = _I1::__bits_per_word; 870 difference_type __d1 = __middle - __first; 871 difference_type __d2 = __last - __middle; 872 _I1 __r = __first + __d2; 873 while (__d1 != 0 && __d2 != 0) 874 { 875 if (__d1 <= __d2) 876 { 877 if (__d1 <= __bit_array<_C>::capacity()) 878 { 879 __bit_array<_C> __b(__d1); 880 _STD::copy(__first, __middle, __b.begin()); 881 _STD::copy(__b.begin(), __b.end(), _STD::copy(__middle, __last, __first)); 882 break; 883 } 884 else 885 { 886 __bit_iterator<_C, false> __mp = _STD::swap_ranges(__first, __middle, __middle); 887 __first = __middle; 888 __middle = __mp; 889 __d2 -= __d1; 890 } 891 } 892 else 893 { 894 if (__d2 <= __bit_array<_C>::capacity()) 895 { 896 __bit_array<_C> __b(__d2); 897 _STD::copy(__middle, __last, __b.begin()); 898 _STD::copy_backward(__b.begin(), __b.end(), _STD::copy_backward(__first, __middle, __last)); 899 break; 900 } 901 else 902 { 903 __bit_iterator<_C, false> __mp = __first + __d2; 904 _STD::swap_ranges(__first, __mp, __middle); 905 __first = __mp; 906 __d1 -= __d2; 907 } 908 } 909 } 910 return __r; 911} 912 913// equal 914 915template <class _C> 916bool 917__equal_unaligned(__bit_iterator<_C, true> __first1, __bit_iterator<_C, true> __last1, 918 __bit_iterator<_C, true> __first2) 919{ 920 typedef __bit_iterator<_C, true> _It; 921 typedef typename _It::difference_type difference_type; 922 typedef typename _It::__storage_type __storage_type; 923 static const unsigned __bits_per_word = _It::__bits_per_word; 924 difference_type __n = __last1 - __first1; 925 if (__n > 0) 926 { 927 // do first word 928 if (__first1.__ctz_ != 0) 929 { 930 unsigned __clz_f = __bits_per_word - __first1.__ctz_; 931 difference_type __dn = _STD::min(static_cast<difference_type>(__clz_f), __n); 932 __n -= __dn; 933 __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 934 __storage_type __b = *__first1.__seg_ & __m; 935 unsigned __clz_r = __bits_per_word - __first2.__ctz_; 936 __storage_type __ddn = _STD::min<__storage_type>(__dn, __clz_r); 937 __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 938 if (__first2.__ctz_ > __first1.__ctz_) 939 if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_))) 940 return false; 941 else 942 if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_))) 943 return false; 944 __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word; 945 __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word); 946 __dn -= __ddn; 947 if (__dn > 0) 948 { 949 __m = ~__storage_type(0) >> (__bits_per_word - __dn); 950 if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn))) 951 return false; 952 __first2.__ctz_ = static_cast<unsigned>(__dn); 953 } 954 ++__first1.__seg_; 955 // __first1.__ctz_ = 0; 956 } 957 // __first1.__ctz_ == 0; 958 // do middle words 959 unsigned __clz_r = __bits_per_word - __first2.__ctz_; 960 __storage_type __m = ~__storage_type(0) << __first2.__ctz_; 961 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_) 962 { 963 __storage_type __b = *__first1.__seg_; 964 if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 965 return false; 966 ++__first2.__seg_; 967 if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r)) 968 return false; 969 } 970 // do last word 971 if (__n > 0) 972 { 973 __m = ~__storage_type(0) >> (__bits_per_word - __n); 974 __storage_type __b = *__first1.__seg_ & __m; 975 __storage_type __dn = _STD::min(__n, static_cast<difference_type>(__clz_r)); 976 __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 977 if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 978 return false; 979 __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word; 980 __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word); 981 __n -= __dn; 982 if (__n > 0) 983 { 984 __m = ~__storage_type(0) >> (__bits_per_word - __n); 985 if ((*__first2.__seg_ & __m) != (__b >> __dn)) 986 return false; 987 } 988 } 989 } 990 return true; 991} 992 993template <class _C> 994bool 995__equal_aligned(__bit_iterator<_C, true> __first1, __bit_iterator<_C, true> __last1, 996 __bit_iterator<_C, true> __first2) 997{ 998 typedef __bit_iterator<_C, true> _It; 999 typedef typename _It::difference_type difference_type; 1000 typedef typename _It::__storage_type __storage_type; 1001 static const unsigned __bits_per_word = _It::__bits_per_word; 1002 difference_type __n = __last1 - __first1; 1003 if (__n > 0) 1004 { 1005 // do first word 1006 if (__first1.__ctz_ != 0) 1007 { 1008 unsigned __clz = __bits_per_word - __first1.__ctz_; 1009 difference_type __dn = _STD::min(static_cast<difference_type>(__clz), __n); 1010 __n -= __dn; 1011 __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 1012 if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 1013 return false; 1014 ++__first2.__seg_; 1015 ++__first1.__seg_; 1016 // __first1.__ctz_ = 0; 1017 // __first2.__ctz_ = 0; 1018 } 1019 // __first1.__ctz_ == 0; 1020 // __first2.__ctz_ == 0; 1021 // do middle words 1022 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_) 1023 if (*__first2.__seg_ != *__first1.__seg_) 1024 return false; 1025 // do last word 1026 if (__n > 0) 1027 { 1028 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 1029 if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 1030 return false; 1031 } 1032 } 1033 return true; 1034} 1035 1036template <class _C, bool _IC1, bool _IC2> 1037inline _LIBCPP_INLINE_VISIBILITY 1038bool 1039equal(__bit_iterator<_C, _IC1> __first1, __bit_iterator<_C, _IC1> __last1, __bit_iterator<_C, _IC2> __first2) 1040{ 1041 if (__first1.__ctz_ == __first2.__ctz_) 1042 return __equal_aligned(__first1, __last1, __first2); 1043 return __equal_unaligned(__first1, __last1, __first2); 1044} 1045 1046template <class _C, bool _IsConst> 1047class __bit_iterator 1048{ 1049public: 1050 typedef typename _C::difference_type difference_type; 1051 typedef bool value_type; 1052 typedef __bit_iterator pointer; 1053 typedef typename conditional<_IsConst, __bit_const_reference<_C>, __bit_reference<_C> >::type reference; 1054 typedef random_access_iterator_tag iterator_category; 1055 1056private: 1057 typedef typename _C::__storage_type __storage_type; 1058 typedef typename conditional<_IsConst, typename _C::__const_storage_pointer, 1059 typename _C::__storage_pointer>::type __storage_pointer; 1060 static const unsigned __bits_per_word = _C::__bits_per_word; 1061 1062 __storage_pointer __seg_; 1063 unsigned __ctz_; 1064 1065public: 1066 _LIBCPP_INLINE_VISIBILITY __bit_iterator() _NOEXCEPT {} 1067 1068 _LIBCPP_INLINE_VISIBILITY 1069 __bit_iterator(const __bit_iterator<_C, false>& __it) _NOEXCEPT 1070 : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {} 1071 1072 _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT 1073 {return reference(__seg_, __storage_type(1) << __ctz_);} 1074 1075 _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator++() 1076 { 1077 if (__ctz_ != __bits_per_word-1) 1078 ++__ctz_; 1079 else 1080 { 1081 __ctz_ = 0; 1082 ++__seg_; 1083 } 1084 return *this; 1085 } 1086 1087 _LIBCPP_INLINE_VISIBILITY __bit_iterator operator++(int) 1088 { 1089 __bit_iterator __tmp = *this; 1090 ++(*this); 1091 return __tmp; 1092 } 1093 1094 _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator--() 1095 { 1096 if (__ctz_ != 0) 1097 --__ctz_; 1098 else 1099 { 1100 __ctz_ = __bits_per_word - 1; 1101 --__seg_; 1102 } 1103 return *this; 1104 } 1105 1106 _LIBCPP_INLINE_VISIBILITY __bit_iterator operator--(int) 1107 { 1108 __bit_iterator __tmp = *this; 1109 --(*this); 1110 return __tmp; 1111 } 1112 1113 _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator+=(difference_type __n) 1114 { 1115 if (__n >= 0) 1116 __seg_ += (__n + __ctz_) / __bits_per_word; 1117 else 1118 __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1) 1119 / static_cast<difference_type>(__bits_per_word); 1120 __n &= (__bits_per_word - 1); 1121 __ctz_ = static_cast<unsigned>((__n + __ctz_) % __bits_per_word); 1122 return *this; 1123 } 1124 1125 _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator-=(difference_type __n) 1126 { 1127 return *this += -__n; 1128 } 1129 1130 _LIBCPP_INLINE_VISIBILITY __bit_iterator operator+(difference_type __n) const 1131 { 1132 __bit_iterator __t(*this); 1133 __t += __n; 1134 return __t; 1135 } 1136 1137 _LIBCPP_INLINE_VISIBILITY __bit_iterator operator-(difference_type __n) const 1138 { 1139 __bit_iterator __t(*this); 1140 __t -= __n; 1141 return __t; 1142 } 1143 1144 _LIBCPP_INLINE_VISIBILITY 1145 friend __bit_iterator operator+(difference_type __n, const __bit_iterator& __it) {return __it + __n;} 1146 1147 _LIBCPP_INLINE_VISIBILITY 1148 friend difference_type operator-(const __bit_iterator& __x, const __bit_iterator& __y) 1149 {return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;} 1150 1151 _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const {return *(*this + __n);} 1152 1153 _LIBCPP_INLINE_VISIBILITY friend bool operator==(const __bit_iterator& __x, const __bit_iterator& __y) 1154 {return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;} 1155 1156 _LIBCPP_INLINE_VISIBILITY friend bool operator!=(const __bit_iterator& __x, const __bit_iterator& __y) 1157 {return !(__x == __y);} 1158 1159 _LIBCPP_INLINE_VISIBILITY friend bool operator<(const __bit_iterator& __x, const __bit_iterator& __y) 1160 {return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);} 1161 1162 _LIBCPP_INLINE_VISIBILITY friend bool operator>(const __bit_iterator& __x, const __bit_iterator& __y) 1163 {return __y < __x;} 1164 1165 _LIBCPP_INLINE_VISIBILITY friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y) 1166 {return !(__y < __x);} 1167 1168 _LIBCPP_INLINE_VISIBILITY friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y) 1169 {return !(__x < __y);} 1170 1171private: 1172 _LIBCPP_INLINE_VISIBILITY 1173 __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT 1174 : __seg_(__s), __ctz_(__ctz) {} 1175 1176#if defined(__clang__) 1177 friend typename _C::__self; 1178#else 1179 friend class _C::__self; 1180#endif 1181 friend class __bit_reference<_C>; 1182 friend class __bit_const_reference<_C>; 1183 friend class __bit_iterator<_C, true>; 1184 template <class _D> friend struct __bit_array; 1185 template <class _D> friend void __fill_n_false(__bit_iterator<_D, false> __first, typename _D::size_type __n); 1186 template <class _D> friend void __fill_n_true(__bit_iterator<_D, false> __first, typename _D::size_type __n); 1187 template <class _D, bool _IC> friend __bit_iterator<_D, false> __copy_aligned(__bit_iterator<_D, _IC> __first, 1188 __bit_iterator<_D, _IC> __last, 1189 __bit_iterator<_D, false> __result); 1190 template <class _D, bool _IC> friend __bit_iterator<_D, false> __copy_unaligned(__bit_iterator<_D, _IC> __first, 1191 __bit_iterator<_D, _IC> __last, 1192 __bit_iterator<_D, false> __result); 1193 template <class _D, bool _IC> friend __bit_iterator<_D, false> copy(__bit_iterator<_D, _IC> __first, 1194 __bit_iterator<_D, _IC> __last, 1195 __bit_iterator<_D, false> __result); 1196 template <class _D, bool _IC> friend __bit_iterator<_D, false> __copy_backward_aligned(__bit_iterator<_D, _IC> __first, 1197 __bit_iterator<_D, _IC> __last, 1198 __bit_iterator<_D, false> __result); 1199 template <class _D, bool _IC> friend __bit_iterator<_D, false> __copy_backward_unaligned(__bit_iterator<_D, _IC> __first, 1200 __bit_iterator<_D, _IC> __last, 1201 __bit_iterator<_D, false> __result); 1202 template <class _D, bool _IC> friend __bit_iterator<_D, false> copy_backward(__bit_iterator<_D, _IC> __first, 1203 __bit_iterator<_D, _IC> __last, 1204 __bit_iterator<_D, false> __result); 1205 template <class _C1, class _C2>friend __bit_iterator<_C2, false> __swap_ranges_aligned(__bit_iterator<_C1, false>, 1206 __bit_iterator<_C1, false>, 1207 __bit_iterator<_C2, false>); 1208 template <class _C1, class _C2>friend __bit_iterator<_C2, false> __swap_ranges_unaligned(__bit_iterator<_C1, false>, 1209 __bit_iterator<_C1, false>, 1210 __bit_iterator<_C2, false>); 1211 template <class _C1, class _C2>friend __bit_iterator<_C2, false> swap_ranges(__bit_iterator<_C1, false>, 1212 __bit_iterator<_C1, false>, 1213 __bit_iterator<_C2, false>); 1214 template <class _D> friend __bit_iterator<_D, false> rotate(__bit_iterator<_D, false>, 1215 __bit_iterator<_D, false>, 1216 __bit_iterator<_D, false>); 1217 template <class _D> friend bool __equal_aligned(__bit_iterator<_D, true>, 1218 __bit_iterator<_D, true>, 1219 __bit_iterator<_D, true>); 1220 template <class _D> friend bool __equal_unaligned(__bit_iterator<_D, true>, 1221 __bit_iterator<_D, true>, 1222 __bit_iterator<_D, true>); 1223 template <class _D, bool _IC1, bool _IC2> friend bool equal(__bit_iterator<_D, _IC1>, 1224 __bit_iterator<_D, _IC1>, 1225 __bit_iterator<_D, _IC2>); 1226 template <class _D> friend __bit_iterator<_D, false> __find_bool_true(__bit_iterator<_D, false>, 1227 typename _D::size_type); 1228 template <class _D> friend __bit_iterator<_D, false> __find_bool_false(__bit_iterator<_D, false>, 1229 typename _D::size_type); 1230}; 1231 1232_LIBCPP_END_NAMESPACE_STD 1233 1234#endif // _LIBCPP___BIT_REFERENCE 1235