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