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