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