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