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