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 25template <class _Cp, bool _IsConst, typename _Cp::__storage_type = 0> class __bit_iterator; 26template <class _Cp> class __bit_const_reference; 27 28template <class _Tp> 29struct __has_storage_type 30{ 31 static const bool value = false; 32}; 33 34template <class _Cp, bool = __has_storage_type<_Cp>::value> 35class __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>; 47public: 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_)));} 70private: 71 _LIBCPP_INLINE_VISIBILITY 72 __bit_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT 73 : __seg_(__s), __mask_(__m) {} 74}; 75 76template <class _Cp> 77class __bit_reference<_Cp, false> 78{ 79}; 80 81template <class _Cp> 82inline _LIBCPP_INLINE_VISIBILITY 83void 84swap(__bit_reference<_Cp> __x, __bit_reference<_Cp> __y) _NOEXCEPT 85{ 86 bool __t = __x; 87 __x = __y; 88 __y = __t; 89} 90 91template <class _Cp, class _Dp> 92inline _LIBCPP_INLINE_VISIBILITY 93void 94swap(__bit_reference<_Cp> __x, __bit_reference<_Dp> __y) _NOEXCEPT 95{ 96 bool __t = __x; 97 __x = __y; 98 __y = __t; 99} 100 101template <class _Cp> 102inline _LIBCPP_INLINE_VISIBILITY 103void 104swap(__bit_reference<_Cp> __x, bool& __y) _NOEXCEPT 105{ 106 bool __t = __x; 107 __x = __y; 108 __y = __t; 109} 110 111template <class _Cp> 112inline _LIBCPP_INLINE_VISIBILITY 113void 114swap(bool& __x, __bit_reference<_Cp> __y) _NOEXCEPT 115{ 116 bool __t = __x; 117 __x = __y; 118 __y = __t; 119} 120 121template <class _Cp> 122class __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>; 132public: 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_)));} 142private: 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 153template <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 189template <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 228template <class _Cp, bool _IsConst, class _Tp> 229inline _LIBCPP_INLINE_VISIBILITY 230__bit_iterator<_Cp, _IsConst> 231find(__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 240template <class _Cp, bool _IsConst> 241typename __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 271template <class _Cp, bool _IsConst> 272typename __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 302template <class _Cp, bool _IsConst, class _Tp> 303inline _LIBCPP_INLINE_VISIBILITY 304typename __bit_iterator<_Cp, _IsConst>::difference_type 305count(__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 314template <class _Cp> 315void 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 344template <class _Cp> 345void 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 374template <class _Cp> 375inline _LIBCPP_INLINE_VISIBILITY 376void 377fill_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 390template <class _Cp> 391inline _LIBCPP_INLINE_VISIBILITY 392void 393fill(__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 400template <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 449template <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 527template <class _Cp, bool _IsConst> 528inline _LIBCPP_INLINE_VISIBILITY 529__bit_iterator<_Cp, false> 530copy(__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 539template <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 588template <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 674template <class _Cp, bool _IsConst> 675inline _LIBCPP_INLINE_VISIBILITY 676__bit_iterator<_Cp, false> 677copy_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 686template <class _Cp, bool _IsConst> 687inline _LIBCPP_INLINE_VISIBILITY 688__bit_iterator<_Cp, false> 689move(__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 696template <class _Cp, bool _IsConst> 697inline _LIBCPP_INLINE_VISIBILITY 698__bit_iterator<_Cp, false> 699move_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 706template <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 756template <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 856template <class __C1, class __C2> 857inline _LIBCPP_INLINE_VISIBILITY 858__bit_iterator<__C2, false> 859swap_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 869template <class _Cp> 870struct __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 896template <class _Cp> 897__bit_iterator<_Cp, false> 898rotate(__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 947template <class _Cp, bool _IC1, bool _IC2> 948bool 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 1029template <class _Cp, bool _IC1, bool _IC2> 1030bool 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 1072template <class _Cp, bool _IC1, bool _IC2> 1073inline _LIBCPP_INLINE_VISIBILITY 1074bool 1075equal(__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 1082template <class _Cp, bool _IsConst, 1083 typename _Cp::__storage_type> 1084class __bit_iterator 1085{ 1086public: 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 1093private: 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 1102public: 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 1212private: 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