591 lines · plain
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___BIT_REFERENCE11#define _LIBCPP___BIT_REFERENCE12 13#include <__algorithm/comp.h>14#include <__algorithm/copy.h>15#include <__algorithm/copy_backward.h>16#include <__algorithm/copy_n.h>17#include <__algorithm/equal.h>18#include <__algorithm/fill_n.h>19#include <__algorithm/min.h>20#include <__algorithm/rotate.h>21#include <__algorithm/specialized_algorithms.h>22#include <__algorithm/swap_ranges.h>23#include <__assert>24#include <__bit/countr.h>25#include <__compare/ordering.h>26#include <__config>27#include <__cstddef/ptrdiff_t.h>28#include <__cstddef/size_t.h>29#include <__functional/identity.h>30#include <__fwd/bit_reference.h>31#include <__iterator/iterator_traits.h>32#include <__memory/construct_at.h>33#include <__memory/pointer_traits.h>34#include <__type_traits/conditional.h>35#include <__type_traits/desugars_to.h>36#include <__type_traits/enable_if.h>37#include <__type_traits/is_constant_evaluated.h>38#include <__type_traits/is_same.h>39#include <__type_traits/is_unsigned.h>40#include <__type_traits/void_t.h>41#include <__utility/pair.h>42#include <__utility/swap.h>43#include <climits>44 45#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)46# pragma GCC system_header47#endif48 49_LIBCPP_PUSH_MACROS50#include <__undef_macros>51 52_LIBCPP_BEGIN_NAMESPACE_STD53 54template <class _Cp>55class __bit_const_reference;56 57template <class _Tp>58struct __has_storage_type {59 static const bool value = false;60};61 62template <class, class>63struct __size_difference_type_traits {64 using difference_type = ptrdiff_t;65 using size_type = size_t;66};67 68template <class _Cp>69struct __size_difference_type_traits<_Cp, __void_t<typename _Cp::difference_type, typename _Cp::size_type> > {70 using difference_type = typename _Cp::difference_type;71 using size_type = typename _Cp::size_type;72};73 74// The `__x_mask` functions are designed to work exclusively with any unsigned `_StorageType`s, including small75// integral types such as unsigned char/short, `uint8_t`, and `uint16_t`. To prevent undefined behavior or76// ambiguities due to integral promotions for the small integral types, all intermediate bitwise operations are77// explicitly cast back to the unsigned `_StorageType`.78 79// Creates a mask of type `_StorageType` with a specified number of leading zeros (__clz) and sets all remaining80// bits to one.81template <class _StorageType>82_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _StorageType __trailing_mask(unsigned __clz) {83 static_assert(is_unsigned<_StorageType>::value, "__trailing_mask only works with unsigned types");84 return static_cast<_StorageType>(~static_cast<_StorageType>(0)) >> __clz;85}86 87// Creates a mask of type `_StorageType` with a specified number of trailing zeros (__ctz) and sets all remaining88// bits to one.89template <class _StorageType>90_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _StorageType __leading_mask(unsigned __ctz) {91 static_assert(is_unsigned<_StorageType>::value, "__leading_mask only works with unsigned types");92 return static_cast<_StorageType>(~static_cast<_StorageType>(0)) << __ctz;93}94 95// Creates a mask of type `_StorageType` with a specified number of leading zeros (__clz), a specified number of96// trailing zeros (__ctz), and sets all bits in between to one.97template <class _StorageType>98_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _StorageType __middle_mask(unsigned __clz, unsigned __ctz) {99 static_assert(is_unsigned<_StorageType>::value, "__middle_mask only works with unsigned types");100 return std::__leading_mask<_StorageType>(__ctz) & std::__trailing_mask<_StorageType>(__clz);101}102 103// This function is designed to operate correctly even for smaller integral types like `uint8_t`, `uint16_t`,104// or `unsigned short`.105// See https://github.com/llvm/llvm-project/pull/122410.106template <class _StoragePointer>107_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void108__fill_masked_range(_StoragePointer __word, unsigned __clz, unsigned __ctz, bool __fill_val) {109 static_assert(is_unsigned<typename pointer_traits<_StoragePointer>::element_type>::value,110 "__fill_masked_range must be called with unsigned type");111 using _StorageType = typename pointer_traits<_StoragePointer>::element_type;112 _LIBCPP_ASSERT_VALID_INPUT_RANGE(113 __ctz + __clz < sizeof(_StorageType) * CHAR_BIT, "__fill_masked_range called with invalid range");114 _StorageType __m = std::__middle_mask<_StorageType>(__clz, __ctz);115 if (__fill_val)116 *__word |= __m;117 else118 *__word &= ~__m;119}120 121template <class _Cp, bool = __has_storage_type<_Cp>::value>122class __bit_reference {123 using __storage_type _LIBCPP_NODEBUG = typename _Cp::__storage_type;124 using __storage_pointer _LIBCPP_NODEBUG = typename _Cp::__storage_pointer;125 126 __storage_pointer __seg_;127 __storage_type __mask_;128 129 friend typename _Cp::__self;130 131 friend class __bit_const_reference<_Cp>;132 friend class __bit_iterator<_Cp, false>;133 134public:135 using __container _LIBCPP_NODEBUG = typename _Cp::__self;136 137 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_reference(const __bit_reference&) = default;138 139 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 operator bool() const _NOEXCEPT {140 return static_cast<bool>(*__seg_ & __mask_);141 }142 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool operator~() const _NOEXCEPT {143 return !static_cast<bool>(*this);144 }145 146 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_reference& operator=(bool __x) _NOEXCEPT {147 if (__x)148 *__seg_ |= __mask_;149 else150 *__seg_ &= ~__mask_;151 return *this;152 }153 154#if _LIBCPP_STD_VER >= 23155 _LIBCPP_HIDE_FROM_ABI constexpr const __bit_reference& operator=(bool __x) const noexcept {156 if (__x)157 *__seg_ |= __mask_;158 else159 *__seg_ &= ~__mask_;160 return *this;161 }162#endif163 164 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_reference& operator=(const __bit_reference& __x) _NOEXCEPT {165 return operator=(static_cast<bool>(__x));166 }167 168 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void flip() _NOEXCEPT { *__seg_ ^= __mask_; }169 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, false> operator&() const _NOEXCEPT {170 return __bit_iterator<_Cp, false>(__seg_, static_cast<unsigned>(std::__countr_zero(__mask_)));171 }172 173private:174 _LIBCPP_HIDE_FROM_ABI175 _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit __bit_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT176 : __seg_(__s),177 __mask_(__m) {}178};179 180template <class _Cp>181class __bit_reference<_Cp, false> {};182 183template <class _Cp>184inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void185swap(__bit_reference<_Cp> __x, __bit_reference<_Cp> __y) _NOEXCEPT {186 bool __t = __x;187 __x = __y;188 __y = __t;189}190 191template <class _Cp, class _Dp>192inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void193swap(__bit_reference<_Cp> __x, __bit_reference<_Dp> __y) _NOEXCEPT {194 bool __t = __x;195 __x = __y;196 __y = __t;197}198 199template <class _Cp>200inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void swap(__bit_reference<_Cp> __x, bool& __y) _NOEXCEPT {201 bool __t = __x;202 __x = __y;203 __y = __t;204}205 206template <class _Cp>207inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void swap(bool& __x, __bit_reference<_Cp> __y) _NOEXCEPT {208 bool __t = __x;209 __x = __y;210 __y = __t;211}212 213template <class _Cp>214class __bit_const_reference {215 using __storage_type _LIBCPP_NODEBUG = typename _Cp::__storage_type;216 using __storage_pointer _LIBCPP_NODEBUG = typename _Cp::__const_storage_pointer;217 218 __storage_pointer __seg_;219 __storage_type __mask_;220 221 friend typename _Cp::__self;222 friend class __bit_iterator<_Cp, true>;223 224public:225 using __container _LIBCPP_NODEBUG = typename _Cp::__self;226 227 _LIBCPP_HIDE_FROM_ABI __bit_const_reference(const __bit_const_reference&) = default;228 __bit_const_reference& operator=(const __bit_const_reference&) = delete;229 230 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_const_reference(const __bit_reference<_Cp>& __x) _NOEXCEPT231 : __seg_(__x.__seg_),232 __mask_(__x.__mask_) {}233 234 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR operator bool() const _NOEXCEPT {235 return static_cast<bool>(*__seg_ & __mask_);236 }237 238 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, true> operator&() const _NOEXCEPT {239 return __bit_iterator<_Cp, true>(__seg_, static_cast<unsigned>(std::__countr_zero(__mask_)));240 }241 242private:243 _LIBCPP_HIDE_FROM_ABI244 _LIBCPP_CONSTEXPR explicit __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT245 : __seg_(__s),246 __mask_(__m) {}247};248 249template <class _Cp>250struct __bit_array {251 using difference_type _LIBCPP_NODEBUG = typename __size_difference_type_traits<_Cp>::difference_type;252 using __storage_type _LIBCPP_NODEBUG = typename _Cp::__storage_type;253 using __storage_pointer _LIBCPP_NODEBUG = typename _Cp::__storage_pointer;254 using iterator _LIBCPP_NODEBUG = typename _Cp::iterator;255 256 static const unsigned __bits_per_word = _Cp::__bits_per_word;257 static const unsigned _Np = 4;258 259 difference_type __size_;260 __storage_type __word_[_Np];261 262 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static difference_type capacity() {263 return static_cast<difference_type>(_Np * __bits_per_word);264 }265 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit __bit_array(difference_type __s) : __size_(__s) {266 if (__libcpp_is_constant_evaluated()) {267 for (size_t __i = 0; __i != __bit_array<_Cp>::_Np; ++__i)268 std::__construct_at(__word_ + __i, 0);269 }270 }271 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator begin() {272 return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]), 0);273 }274 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator end() {275 return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]) + __size_ / __bits_per_word,276 static_cast<unsigned>(__size_ % __bits_per_word));277 }278};279 280template <class _Cp, bool _IsConst, typename _Cp::__storage_type>281class __bit_iterator {282public:283 using difference_type = typename __size_difference_type_traits<_Cp>::difference_type;284 using value_type = bool;285 using pointer = __bit_iterator;286#ifndef _LIBCPP_ABI_BITSET_VECTOR_BOOL_CONST_SUBSCRIPT_RETURN_BOOL287 using reference = __conditional_t<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >;288#else289 using reference = __conditional_t<_IsConst, bool, __bit_reference<_Cp> >;290#endif291 using iterator_category = random_access_iterator_tag;292 293private:294 using __storage_type _LIBCPP_NODEBUG = typename _Cp::__storage_type;295 using __storage_pointer _LIBCPP_NODEBUG =296 __conditional_t<_IsConst, typename _Cp::__const_storage_pointer, typename _Cp::__storage_pointer>;297 298 static const unsigned __bits_per_word = _Cp::__bits_per_word;299 300 __storage_pointer __seg_;301 unsigned __ctz_;302 303public:304 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator() _NOEXCEPT305#if _LIBCPP_STD_VER >= 14306 : __seg_(nullptr),307 __ctz_(0)308#endif309 {310 }311 312 // When _IsConst=false, this is the copy constructor.313 // It is non-trivial. Making it trivial would break ABI.314 // When _IsConst=true, this is a converting constructor;315 // the copy and move constructors are implicitly generated316 // and trivial.317 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT318 : __seg_(__it.__seg_),319 __ctz_(__it.__ctz_) {}320 321 // When _IsConst=false, we have a user-provided copy constructor,322 // so we must also provide a copy assignment operator because323 // the implicit generation of a defaulted one is deprecated.324 // When _IsConst=true, the assignment operators are325 // implicitly generated and trivial.326 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator&327 operator=(const _If<_IsConst, struct __private_nat, __bit_iterator>& __it) {328 __seg_ = __it.__seg_;329 __ctz_ = __it.__ctz_;330 return *this;331 }332 333 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference operator*() const _NOEXCEPT {334 _LIBCPP_ASSERT_INTERNAL(__ctz_ < __bits_per_word, "Dereferencing an invalid __bit_iterator.");335 return __conditional_t<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >(336 __seg_, __storage_type(1) << __ctz_);337 }338 339 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator++() {340 if (__ctz_ != __bits_per_word - 1)341 ++__ctz_;342 else {343 __ctz_ = 0;344 ++__seg_;345 }346 return *this;347 }348 349 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator++(int) {350 __bit_iterator __tmp = *this;351 ++(*this);352 return __tmp;353 }354 355 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator--() {356 if (__ctz_ != 0)357 --__ctz_;358 else {359 __ctz_ = __bits_per_word - 1;360 --__seg_;361 }362 return *this;363 }364 365 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator--(int) {366 __bit_iterator __tmp = *this;367 --(*this);368 return __tmp;369 }370 371 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator+=(difference_type __n) {372 if (__n >= 0)373 __seg_ += (__n + __ctz_) / __bits_per_word;374 else375 __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1) /376 static_cast<difference_type>(__bits_per_word);377 __n &= (__bits_per_word - 1);378 __ctz_ = static_cast<unsigned>((__n + __ctz_) % __bits_per_word);379 return *this;380 }381 382 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator-=(difference_type __n) {383 return *this += -__n;384 }385 386 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator+(difference_type __n) const {387 __bit_iterator __t(*this);388 __t += __n;389 return __t;390 }391 392 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator-(difference_type __n) const {393 __bit_iterator __t(*this);394 __t -= __n;395 return __t;396 }397 398 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator399 operator+(difference_type __n, const __bit_iterator& __it) {400 return __it + __n;401 }402 403 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend difference_type404 operator-(const __bit_iterator& __x, const __bit_iterator& __y) {405 return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;406 }407 408 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference operator[](difference_type __n) const {409 return *(*this + __n);410 }411 412 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool413 operator==(const __bit_iterator& __x, const __bit_iterator& __y) {414 return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;415 }416 417#if _LIBCPP_STD_VER <= 17418 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool419 operator!=(const __bit_iterator& __x, const __bit_iterator& __y) {420 return !(__x == __y);421 }422 423 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool424 operator<(const __bit_iterator& __x, const __bit_iterator& __y) {425 return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);426 }427 428 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool429 operator>(const __bit_iterator& __x, const __bit_iterator& __y) {430 return __y < __x;431 }432 433 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool434 operator<=(const __bit_iterator& __x, const __bit_iterator& __y) {435 return !(__y < __x);436 }437 438 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool439 operator>=(const __bit_iterator& __x, const __bit_iterator& __y) {440 return !(__x < __y);441 }442#else // _LIBCPP_STD_VER <= 17443 _LIBCPP_HIDE_FROM_ABI constexpr friend strong_ordering444 operator<=>(const __bit_iterator& __x, const __bit_iterator& __y) {445 if (__x.__seg_ < __y.__seg_)446 return strong_ordering::less;447 448 if (__x.__seg_ == __y.__seg_)449 return __x.__ctz_ <=> __y.__ctz_;450 451 return strong_ordering::greater;452 }453#endif // _LIBCPP_STD_VER <= 17454 455private:456 _LIBCPP_HIDE_FROM_ABI457 _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT458 : __seg_(__s),459 __ctz_(__ctz) {460 _LIBCPP_ASSERT_INTERNAL(461 __ctz_ < __bits_per_word, "__bit_iterator initialized with an invalid number of trailing zeros.");462 }463 464 friend typename _Cp::__self;465 466 friend class __bit_reference<_Cp>;467 friend class __bit_const_reference<_Cp>;468 friend class __bit_iterator<_Cp, true>;469 template <class _Dp>470 friend struct __bit_array;471 472 template <class _Dp, bool _IC>473 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> __copy_aligned(474 __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result);475 template <class _Dp, bool _IC>476 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> __copy_unaligned(477 __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result);478 template <class _Dp, bool _IC>479 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend pair<__bit_iterator<_Dp, _IC>, __bit_iterator<_Dp, false> >480 __copy_impl::operator()(481 __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result) const;482 template <class _Dp, bool _IC>483 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> __copy_backward_aligned(484 __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result);485 template <class _Dp, bool _IC>486 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, false> __copy_backward_unaligned(487 __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result);488 template <class _AlgPolicy>489 friend struct __copy_backward_impl;490 template <class _Cl, class _Cr>491 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Cr, false>492 __swap_ranges_aligned(__bit_iterator<_Cl, false>, __bit_iterator<_Cl, false>, __bit_iterator<_Cr, false>);493 template <class _Cl, class _Cr>494 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Cr, false>495 __swap_ranges_unaligned(__bit_iterator<_Cl, false>, __bit_iterator<_Cl, false>, __bit_iterator<_Cr, false>);496 template <class, class _Cl, class _Cr>497 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend pair<__bit_iterator<_Cl, false>, __bit_iterator<_Cr, false> >498 __swap_ranges(__bit_iterator<_Cl, false>, __bit_iterator<_Cl, false>, __bit_iterator<_Cr, false>);499 template <class, class _Dp>500 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend pair<__bit_iterator<_Dp, false>, __bit_iterator<_Dp, false> >501 __rotate(__bit_iterator<_Dp, false>, __bit_iterator<_Dp, false>, __bit_iterator<_Dp, false>);502 template <class _Dp, bool _IsConst1, bool _IsConst2>503 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool504 __equal_aligned(__bit_iterator<_Dp, _IsConst1>, __bit_iterator<_Dp, _IsConst1>, __bit_iterator<_Dp, _IsConst2>);505 template <class _Dp, bool _IsConst1, bool _IsConst2>506 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool507 __equal_unaligned(__bit_iterator<_Dp, _IsConst1>, __bit_iterator<_Dp, _IsConst1>, __bit_iterator<_Dp, _IsConst2>);508 template <class _Dp,509 bool _IsConst1,510 bool _IsConst2,511 class _BinaryPredicate,512 __enable_if_t<__desugars_to_v<__equal_tag, _BinaryPredicate, bool, bool>, int> >513 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool __equal_iter_impl(514 __bit_iterator<_Dp, _IsConst1>, __bit_iterator<_Dp, _IsConst1>, __bit_iterator<_Dp, _IsConst2>, _BinaryPredicate);515 template <class _Dp,516 bool _IsConst1,517 bool _IsConst2,518 class _Pred,519 class _Proj1,520 class _Proj2,521 __enable_if_t<__desugars_to_v<__equal_tag, _Pred, bool, bool> && __is_identity<_Proj1>::value &&522 __is_identity<_Proj2>::value,523 int> >524 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool __equal_impl(525 __bit_iterator<_Dp, _IsConst1> __first1,526 __bit_iterator<_Dp, _IsConst1> __last1,527 __bit_iterator<_Dp, _IsConst2> __first2,528 __bit_iterator<_Dp, _IsConst2>,529 _Pred&,530 _Proj1&,531 _Proj2&);532 template <bool _ToFind, class _Dp, bool _IC>533 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, _IC>534 __find_bool(__bit_iterator<_Dp, _IC>, typename __size_difference_type_traits<_Dp>::size_type);535 template <bool _ToCount, class _Dp, bool _IC>536 friend typename __bit_iterator<_Dp, _IC>::difference_type _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20537 __count_bool(__bit_iterator<_Dp, _IC>, typename __size_difference_type_traits<_Dp>::size_type);538 539 template <class, class...>540 friend struct __specialized_algorithm;541};542 543template <class _Cp>544struct __specialized_algorithm<_Algorithm::__fill_n, __single_iterator<__bit_iterator<_Cp, false> > > {545 static const bool __has_algorithm = true;546 547 template <bool _FillVal>548 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static void549 __impl(__bit_iterator<_Cp, false> __first, typename __size_difference_type_traits<_Cp>::size_type __n) {550 using _It = __bit_iterator<_Cp, false>;551 using __storage_type = typename _It::__storage_type;552 553 const int __bits_per_word = _It::__bits_per_word;554 // do first partial word555 if (__first.__ctz_ != 0) {556 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);557 __storage_type __dn = std::min(__clz_f, __n);558 std::__fill_masked_range(std::__to_address(__first.__seg_), __clz_f - __dn, __first.__ctz_, _FillVal);559 __n -= __dn;560 ++__first.__seg_;561 }562 // do middle whole words563 __storage_type __nw = __n / __bits_per_word;564 std::__fill_n(std::__to_address(__first.__seg_), __nw, _FillVal ? static_cast<__storage_type>(-1) : 0);565 __n -= __nw * __bits_per_word;566 // do last partial word567 if (__n > 0) {568 __first.__seg_ += __nw;569 std::__fill_masked_range(std::__to_address(__first.__seg_), __bits_per_word - __n, 0u, _FillVal);570 }571 }572 573 template <class _Size, class _Tp>574 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static __bit_iterator<_Cp, false>575 operator()(__bit_iterator<_Cp, false> __first, _Size __n, const _Tp& __value) {576 if (__n > 0) {577 if (__value)578 __impl<true>(__first, __n);579 else580 __impl<false>(__first, __n);581 }582 return __first + __n;583 }584};585 586_LIBCPP_END_NAMESPACE_STD587 588_LIBCPP_POP_MACROS589 590#endif // _LIBCPP___BIT_REFERENCE591