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