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