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