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