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