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