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