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