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