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