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_backward(__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 difference_type __d1 = __middle - __first; 910 difference_type __d2 = __last - __middle; 911 _I1 __r = __first + __d2; 912 while (__d1 != 0 && __d2 != 0) 913 { 914 if (__d1 <= __d2) 915 { 916 if (__d1 <= __bit_array<_Cp>::capacity()) 917 { 918 __bit_array<_Cp> __b(__d1); 919 _VSTD::copy(__first, __middle, __b.begin()); 920 _VSTD::copy(__b.begin(), __b.end(), _VSTD::copy(__middle, __last, __first)); 921 break; 922 } 923 else 924 { 925 __bit_iterator<_Cp, false> __mp = _VSTD::swap_ranges(__first, __middle, __middle); 926 __first = __middle; 927 __middle = __mp; 928 __d2 -= __d1; 929 } 930 } 931 else 932 { 933 if (__d2 <= __bit_array<_Cp>::capacity()) 934 { 935 __bit_array<_Cp> __b(__d2); 936 _VSTD::copy(__middle, __last, __b.begin()); 937 _VSTD::copy_backward(__b.begin(), __b.end(), _VSTD::copy_backward(__first, __middle, __last)); 938 break; 939 } 940 else 941 { 942 __bit_iterator<_Cp, false> __mp = __first + __d2; 943 _VSTD::swap_ranges(__first, __mp, __middle); 944 __first = __mp; 945 __d1 -= __d2; 946 } 947 } 948 } 949 return __r; 950 } 951 952 // equal 953 954 template <class _Cp, bool _IC1, bool _IC2> 955 bool 956 __equal_unaligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, 957 __bit_iterator<_Cp, _IC2> __first2) 958 { 959 typedef __bit_iterator<_Cp, _IC1> _It; 960 typedef typename _It::difference_type difference_type; 961 typedef typename _It::__storage_type __storage_type; 962 static const unsigned __bits_per_word = _It::__bits_per_word; 963 difference_type __n = __last1 - __first1; 964 if (__n > 0) 965 { 966 // do first word 967 if (__first1.__ctz_ != 0) 968 { 969 unsigned __clz_f = __bits_per_word - __first1.__ctz_; 970 difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 971 __n -= __dn; 972 __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 973 __storage_type __b = *__first1.__seg_ & __m; 974 unsigned __clz_r = __bits_per_word - __first2.__ctz_; 975 __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 976 __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 977 if (__first2.__ctz_ > __first1.__ctz_) 978 { 979 if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_))) 980 return false; 981 } 982 else 983 { 984 if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_))) 985 return false; 986 } 987 __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word; 988 __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word); 989 __dn -= __ddn; 990 if (__dn > 0) 991 { 992 __m = ~__storage_type(0) >> (__bits_per_word - __dn); 993 if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn))) 994 return false; 995 __first2.__ctz_ = static_cast<unsigned>(__dn); 996 } 997 ++__first1.__seg_; 998 // __first1.__ctz_ = 0; 999 } 1000 // __first1.__ctz_ == 0; 1001 // do middle words 1002 unsigned __clz_r = __bits_per_word - __first2.__ctz_; 1003 __storage_type __m = ~__storage_type(0) << __first2.__ctz_; 1004 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_) 1005 { 1006 __storage_type __b = *__first1.__seg_; 1007 if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 1008 return false; 1009 ++__first2.__seg_; 1010 if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r)) 1011 return false; 1012 } 1013 // do last word 1014 if (__n > 0) 1015 { 1016 __m = ~__storage_type(0) >> (__bits_per_word - __n); 1017 __storage_type __b = *__first1.__seg_ & __m; 1018 __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); 1019 __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 1020 if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 1021 return false; 1022 __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word; 1023 __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word); 1024 __n -= __dn; 1025 if (__n > 0) 1026 { 1027 __m = ~__storage_type(0) >> (__bits_per_word - __n); 1028 if ((*__first2.__seg_ & __m) != (__b >> __dn)) 1029 return false; 1030 } 1031 } 1032 } 1033 return true; 1034 } 1035 1036 template <class _Cp, bool _IC1, bool _IC2> 1037 bool 1038 __equal_aligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, 1039 __bit_iterator<_Cp, _IC2> __first2) 1040 { 1041 typedef __bit_iterator<_Cp, _IC1> _It; 1042 typedef typename _It::difference_type difference_type; 1043 typedef typename _It::__storage_type __storage_type; 1044 static const unsigned __bits_per_word = _It::__bits_per_word; 1045 difference_type __n = __last1 - __first1; 1046 if (__n > 0) 1047 { 1048 // do first word 1049 if (__first1.__ctz_ != 0) 1050 { 1051 unsigned __clz = __bits_per_word - __first1.__ctz_; 1052 difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 1053 __n -= __dn; 1054 __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 1055 if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 1056 return false; 1057 ++__first2.__seg_; 1058 ++__first1.__seg_; 1059 // __first1.__ctz_ = 0; 1060 // __first2.__ctz_ = 0; 1061 } 1062 // __first1.__ctz_ == 0; 1063 // __first2.__ctz_ == 0; 1064 // do middle words 1065 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_) 1066 if (*__first2.__seg_ != *__first1.__seg_) 1067 return false; 1068 // do last word 1069 if (__n > 0) 1070 { 1071 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 1072 if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 1073 return false; 1074 } 1075 } 1076 return true; 1077 } 1078 1079 template <class _Cp, bool _IC1, bool _IC2> 1080 inline _LIBCPP_INLINE_VISIBILITY 1081 bool 1082 equal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) 1083 { 1084 if (__first1.__ctz_ == __first2.__ctz_) 1085 return __equal_aligned(__first1, __last1, __first2); 1086 return __equal_unaligned(__first1, __last1, __first2); 1087 } 1088 1089 template <class _Cp, bool _IsConst, 1090 typename _Cp::__storage_type> 1091 class __bit_iterator 1092 { 1093 public: 1094 typedef typename _Cp::difference_type difference_type; 1095 typedef bool value_type; 1096 typedef __bit_iterator pointer; 1097 typedef typename conditional<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >::type reference; 1098 typedef random_access_iterator_tag iterator_category; 1099 1100 private: 1101 typedef typename _Cp::__storage_type __storage_type; 1102 typedef typename conditional<_IsConst, typename _Cp::__const_storage_pointer, 1103 typename _Cp::__storage_pointer>::type __storage_pointer; 1104 static const unsigned __bits_per_word = _Cp::__bits_per_word; 1105 1106 __storage_pointer __seg_; 1107 unsigned __ctz_; 1108 1109 public: 1110 _LIBCPP_INLINE_VISIBILITY __bit_iterator() _NOEXCEPT 1111 #if _LIBCPP_STD_VER > 11 1112 : __seg_(nullptr), __ctz_(0) 1113 #endif 1114 {} 1115 1116 _LIBCPP_INLINE_VISIBILITY 1117 __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT 1118 : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {} 1119 1120 _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT 1121 {return reference(__seg_, __storage_type(1) << __ctz_);} 1122 1123 _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator++() 1124 { 1125 if (__ctz_ != __bits_per_word-1) 1126 ++__ctz_; 1127 else 1128 { 1129 __ctz_ = 0; 1130 ++__seg_; 1131 } 1132 return *this; 1133 } 1134 1135 _LIBCPP_INLINE_VISIBILITY __bit_iterator operator++(int) 1136 { 1137 __bit_iterator __tmp = *this; 1138 ++(*this); 1139 return __tmp; 1140 } 1141 1142 _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator--() 1143 { 1144 if (__ctz_ != 0) 1145 --__ctz_; 1146 else 1147 { 1148 __ctz_ = __bits_per_word - 1; 1149 --__seg_; 1150 } 1151 return *this; 1152 } 1153 1154 _LIBCPP_INLINE_VISIBILITY __bit_iterator operator--(int) 1155 { 1156 __bit_iterator __tmp = *this; 1157 --(*this); 1158 return __tmp; 1159 } 1160 1161 _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator+=(difference_type __n) 1162 { 1163 if (__n >= 0) 1164 __seg_ += (__n + __ctz_) / __bits_per_word; 1165 else 1166 __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1) 1167 / static_cast<difference_type>(__bits_per_word); 1168 __n &= (__bits_per_word - 1); 1169 __ctz_ = static_cast<unsigned>((__n + __ctz_) % __bits_per_word); 1170 return *this; 1171 } 1172 1173 _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator-=(difference_type __n) 1174 { 1175 return *this += -__n; 1176 } 1177 1178 _LIBCPP_INLINE_VISIBILITY __bit_iterator operator+(difference_type __n) const 1179 { 1180 __bit_iterator __t(*this); 1181 __t += __n; 1182 return __t; 1183 } 1184 1185 _LIBCPP_INLINE_VISIBILITY __bit_iterator operator-(difference_type __n) const 1186 { 1187 __bit_iterator __t(*this); 1188 __t -= __n; 1189 return __t; 1190 } 1191 1192 _LIBCPP_INLINE_VISIBILITY 1193 friend __bit_iterator operator+(difference_type __n, const __bit_iterator& __it) {return __it + __n;} 1194 1195 _LIBCPP_INLINE_VISIBILITY 1196 friend difference_type operator-(const __bit_iterator& __x, const __bit_iterator& __y) 1197 {return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;} 1198 1199 _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const {return *(*this + __n);} 1200 1201 _LIBCPP_INLINE_VISIBILITY friend bool operator==(const __bit_iterator& __x, const __bit_iterator& __y) 1202 {return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;} 1203 1204 _LIBCPP_INLINE_VISIBILITY friend bool operator!=(const __bit_iterator& __x, const __bit_iterator& __y) 1205 {return !(__x == __y);} 1206 1207 _LIBCPP_INLINE_VISIBILITY friend bool operator<(const __bit_iterator& __x, const __bit_iterator& __y) 1208 {return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);} 1209 1210 _LIBCPP_INLINE_VISIBILITY friend bool operator>(const __bit_iterator& __x, const __bit_iterator& __y) 1211 {return __y < __x;} 1212 1213 _LIBCPP_INLINE_VISIBILITY friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y) 1214 {return !(__y < __x);} 1215 1216 _LIBCPP_INLINE_VISIBILITY friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y) 1217 {return !(__x < __y);} 1218 1219 private: 1220 _LIBCPP_INLINE_VISIBILITY 1221 __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT 1222 : __seg_(__s), __ctz_(__ctz) {} 1223 1224 #if defined(__clang__) || defined(__IBMCPP__) || defined(_LIBCPP_MSVC) 1225 friend typename _Cp::__self; 1226 #else 1227 friend class _Cp::__self; 1228 #endif 1229 friend class __bit_reference<_Cp>; 1230 friend class __bit_const_reference<_Cp>; 1231 friend class __bit_iterator<_Cp, true>; 1232 template <class _Dp> friend struct __bit_array; 1233 template <class _Dp> friend void __fill_n_false(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); 1234 template <class _Dp> friend void __fill_n_true(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); 1235 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_aligned(__bit_iterator<_Dp, _IC> __first, 1236 __bit_iterator<_Dp, _IC> __last, 1237 __bit_iterator<_Dp, false> __result); 1238 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_unaligned(__bit_iterator<_Dp, _IC> __first, 1239 __bit_iterator<_Dp, _IC> __last, 1240 __bit_iterator<_Dp, false> __result); 1241 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy(__bit_iterator<_Dp, _IC> __first, 1242 __bit_iterator<_Dp, _IC> __last, 1243 __bit_iterator<_Dp, false> __result); 1244 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_aligned(__bit_iterator<_Dp, _IC> __first, 1245 __bit_iterator<_Dp, _IC> __last, 1246 __bit_iterator<_Dp, false> __result); 1247 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_unaligned(__bit_iterator<_Dp, _IC> __first, 1248 __bit_iterator<_Dp, _IC> __last, 1249 __bit_iterator<_Dp, false> __result); 1250 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy_backward(__bit_iterator<_Dp, _IC> __first, 1251 __bit_iterator<_Dp, _IC> __last, 1252 __bit_iterator<_Dp, false> __result); 1253 template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_aligned(__bit_iterator<__C1, false>, 1254 __bit_iterator<__C1, false>, 1255 __bit_iterator<__C2, false>); 1256 template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_unaligned(__bit_iterator<__C1, false>, 1257 __bit_iterator<__C1, false>, 1258 __bit_iterator<__C2, false>); 1259 template <class __C1, class __C2>friend __bit_iterator<__C2, false> swap_ranges(__bit_iterator<__C1, false>, 1260 __bit_iterator<__C1, false>, 1261 __bit_iterator<__C2, false>); 1262 template <class _Dp> friend __bit_iterator<_Dp, false> rotate(__bit_iterator<_Dp, false>, 1263 __bit_iterator<_Dp, false>, 1264 __bit_iterator<_Dp, false>); 1265 template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_aligned(__bit_iterator<_Dp, _IC1>, 1266 __bit_iterator<_Dp, _IC1>, 1267 __bit_iterator<_Dp, _IC2>); 1268 template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_unaligned(__bit_iterator<_Dp, _IC1>, 1269 __bit_iterator<_Dp, _IC1>, 1270 __bit_iterator<_Dp, _IC2>); 1271 template <class _Dp, bool _IC1, bool _IC2> friend bool equal(__bit_iterator<_Dp, _IC1>, 1272 __bit_iterator<_Dp, _IC1>, 1273 __bit_iterator<_Dp, _IC2>); 1274 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_true(__bit_iterator<_Dp, _IC>, 1275 typename _Dp::size_type); 1276 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_false(__bit_iterator<_Dp, _IC>, 1277 typename _Dp::size_type); 1278 template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type 1279 __count_bool_true(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 1280 template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type 1281 __count_bool_false(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 1282 }; 1283 1284 _LIBCPP_END_NAMESPACE_STD 1285 1286 #endif // _LIBCPP___BIT_REFERENCE 1287
