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