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