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/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_header
47#endif
48
49_LIBCPP_PUSH_MACROS
50#include <__undef_macros>
51
52_LIBCPP_BEGIN_NAMESPACE_STD
53
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 small
75// integral types such as unsigned char/short, `uint8_t`, and `uint16_t`. To prevent undefined behavior or
76// ambiguities due to integral promotions for the small integral types, all intermediate bitwise operations are
77// 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 remaining
80// 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 remaining
88// 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 of
96// 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 void
108__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 else
118 *__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 [[__nodiscard__]] _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 else
150 *__seg_ &= ~__mask_;
151 return *this;
152 }
153
154#if _LIBCPP_STD_VER >= 23
155 _LIBCPP_HIDE_FROM_ABI constexpr const __bit_reference& operator=(bool __x) const noexcept {
156 if (__x)
157 *__seg_ |= __mask_;
158 else
159 *__seg_ &= ~__mask_;
160 return *this;
161 }
162#endif
163
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_ABI
175 _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit __bit_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT
176 : __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 void
185swap(__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 void
193swap(__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) _NOEXCEPT
231 : __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_ABI
244 _LIBCPP_CONSTEXPR explicit __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT
245 : __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_BOOL
287 using reference = __conditional_t<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >;
288#else
289 using reference = __conditional_t<_IsConst, bool, __bit_reference<_Cp> >;
290#endif
291 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() _NOEXCEPT
305#if _LIBCPP_STD_VER >= 14
306 : __seg_(nullptr),
307 __ctz_(0)
308#endif
309 {
310 }
311
312#ifdef _LIBCPP_ABI_TRIVIALLY_COPYABLE_BIT_ITERATOR
313 template <bool _IsConstDep = _IsConst, __enable_if_t<_IsConstDep, int> = 0>
314 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT
315 : __seg_(__it.__seg_),
316 __ctz_(__it.__ctz_) {}
317
318 _LIBCPP_HIDE_FROM_ABI __bit_iterator(const __bit_iterator&) = default;
319 _LIBCPP_HIDE_FROM_ABI __bit_iterator& operator=(const __bit_iterator&) = default;
320#else
321 // When _IsConst=false, this is the copy constructor.
322 // It is non-trivial. Making it trivial would break ABI.
323 // When _IsConst=true, this is a converting constructor;
324 // the copy and move constructors are implicitly generated
325 // and trivial.
326 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT
327 : __seg_(__it.__seg_),
328 __ctz_(__it.__ctz_) {}
329
330 // When _IsConst=false, we have a user-provided copy constructor,
331 // so we must also provide a copy assignment operator because
332 // the implicit generation of a defaulted one is deprecated.
333 // When _IsConst=true, the assignment operators are
334 // implicitly generated and trivial.
335 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator&
336 operator=(const _If<_IsConst, struct __private_nat, __bit_iterator>& __it) {
337 __seg_ = __it.__seg_;
338 __ctz_ = __it.__ctz_;
339 return *this;
340 }
341#endif
342
343 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference operator*() const _NOEXCEPT {
344 _LIBCPP_ASSERT_INTERNAL(__ctz_ < __bits_per_word, "Dereferencing an invalid __bit_iterator.");
345 return __conditional_t<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >(
346 __seg_, __storage_type(1) << __ctz_);
347 }
348
349 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator++() {
350 if (__ctz_ != __bits_per_word - 1)
351 ++__ctz_;
352 else {
353 __ctz_ = 0;
354 ++__seg_;
355 }
356 return *this;
357 }
358
359 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator++(int) {
360 __bit_iterator __tmp = *this;
361 ++(*this);
362 return __tmp;
363 }
364
365 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator--() {
366 if (__ctz_ != 0)
367 --__ctz_;
368 else {
369 __ctz_ = __bits_per_word - 1;
370 --__seg_;
371 }
372 return *this;
373 }
374
375 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator--(int) {
376 __bit_iterator __tmp = *this;
377 --(*this);
378 return __tmp;
379 }
380
381 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator+=(difference_type __n) {
382 if (__n >= 0)
383 __seg_ += (__n + __ctz_) / __bits_per_word;
384 else
385 __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1) /
386 static_cast<difference_type>(__bits_per_word);
387 __n &= (__bits_per_word - 1);
388 __ctz_ = static_cast<unsigned>((__n + __ctz_) % __bits_per_word);
389 return *this;
390 }
391
392 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator-=(difference_type __n) {
393 return *this += -__n;
394 }
395
396 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator+(difference_type __n) const {
397 __bit_iterator __t(*this);
398 __t += __n;
399 return __t;
400 }
401
402 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator-(difference_type __n) const {
403 __bit_iterator __t(*this);
404 __t -= __n;
405 return __t;
406 }
407
408 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator
409 operator+(difference_type __n, const __bit_iterator& __it) {
410 return __it + __n;
411 }
412
413 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend difference_type
414 operator-(const __bit_iterator& __x, const __bit_iterator& __y) {
415 return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;
416 }
417
418 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference operator[](difference_type __n) const {
419 return *(*this + __n);
420 }
421
422 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
423 operator==(const __bit_iterator& __x, const __bit_iterator& __y) {
424 return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;
425 }
426
427#if _LIBCPP_STD_VER <= 17
428 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
429 operator!=(const __bit_iterator& __x, const __bit_iterator& __y) {
430 return !(__x == __y);
431 }
432
433 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
434 operator<(const __bit_iterator& __x, const __bit_iterator& __y) {
435 return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);
436 }
437
438 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
439 operator>(const __bit_iterator& __x, const __bit_iterator& __y) {
440 return __y < __x;
441 }
442
443 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
444 operator<=(const __bit_iterator& __x, const __bit_iterator& __y) {
445 return !(__y < __x);
446 }
447
448 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool
449 operator>=(const __bit_iterator& __x, const __bit_iterator& __y) {
450 return !(__x < __y);
451 }
452#else // _LIBCPP_STD_VER <= 17
453 _LIBCPP_HIDE_FROM_ABI constexpr friend strong_ordering
454 operator<=>(const __bit_iterator& __x, const __bit_iterator& __y) {
455 if (__x.__seg_ < __y.__seg_)
456 return strong_ordering::less;
457
458 if (__x.__seg_ == __y.__seg_)
459 return __x.__ctz_ <=> __y.__ctz_;
460
461 return strong_ordering::greater;
462 }
463#endif // _LIBCPP_STD_VER <= 17
464
465private:
466 _LIBCPP_HIDE_FROM_ABI
467 _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT
468 : __seg_(__s),
469 __ctz_(__ctz) {
470 _LIBCPP_ASSERT_INTERNAL(
471 __ctz_ < __bits_per_word, "__bit_iterator initialized with an invalid number of trailing zeros.");
472 }
473
474 friend typename _Cp::__self;
475
476 friend class __bit_reference<_Cp>;
477 friend class __bit_const_reference<_Cp>;
478 friend class __bit_iterator<_Cp, true>;
479 template <class _Dp>
480 friend struct __bit_array;
481
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 bool
504 __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 bool
507 __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 class _Proj1,
513 class _Proj2,
514 __enable_if_t<__is_identity<_Proj1>::value && __is_identity<_Proj2>::value &&
515 __desugars_to_v<__equal_tag, _BinaryPredicate, bool, bool>,
516 int> >
517 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool __equal_iter_impl(
518 __bit_iterator<_Dp, _IsConst1>,
519 __bit_iterator<_Dp, _IsConst1>,
520 __bit_iterator<_Dp, _IsConst2>,
521 _BinaryPredicate,
522 _Proj1&,
523 _Proj2&);
524 template <bool,
525 class _Dp,
526 bool _IsConst1,
527 bool _IsConst2,
528 class _Pred,
529 class _Proj1,
530 class _Proj2,
531 __enable_if_t<__desugars_to_v<__equal_tag, _Pred, bool, bool> && __is_identity<_Proj1>::value &&
532 __is_identity<_Proj2>::value,
533 int> >
534 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool __equal_impl(
535 __bit_iterator<_Dp, _IsConst1> __first1,
536 __bit_iterator<_Dp, _IsConst1> __last1,
537 __bit_iterator<_Dp, _IsConst2> __first2,
538 __bit_iterator<_Dp, _IsConst2>,
539 _Pred&,
540 _Proj1&,
541 _Proj2&);
542 template <bool _ToFind, class _Dp, bool _IC>
543 _LIBCPP_CONSTEXPR_SINCE_CXX20 friend __bit_iterator<_Dp, _IC>
544 __find_bool(__bit_iterator<_Dp, _IC>, typename __size_difference_type_traits<_Dp>::size_type);
545 template <bool _ToCount, class _Dp, bool _IC>
546 friend typename __bit_iterator<_Dp, _IC>::difference_type _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
547 __count_bool(__bit_iterator<_Dp, _IC>, typename __size_difference_type_traits<_Dp>::size_type);
548
549 template <class, class...>
550 friend struct __specialized_algorithm;
551};
552
553template <class _Cp>
554struct __specialized_algorithm<_Algorithm::__fill_n, __single_iterator<__bit_iterator<_Cp, false> > > {
555 static const bool __has_algorithm = true;
556
557 template <bool _FillVal>
558 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static void
559 __impl(__bit_iterator<_Cp, false> __first, typename __size_difference_type_traits<_Cp>::size_type __n) {
560 using _It = __bit_iterator<_Cp, false>;
561 using __storage_type = typename _It::__storage_type;
562
563 const int __bits_per_word = _It::__bits_per_word;
564 // do first partial word
565 if (__first.__ctz_ != 0) {
566 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
567 __storage_type __dn = std::min(__clz_f, __n);
568 std::__fill_masked_range(std::__to_address(__first.__seg_), __clz_f - __dn, __first.__ctz_, _FillVal);
569 __n -= __dn;
570 ++__first.__seg_;
571 }
572 // do middle whole words
573 __storage_type __nw = __n / __bits_per_word;
574 std::__fill_n(std::__to_address(__first.__seg_), __nw, _FillVal ? static_cast<__storage_type>(-1) : 0);
575 __n -= __nw * __bits_per_word;
576 // do last partial word
577 if (__n > 0) {
578 __first.__seg_ += __nw;
579 std::__fill_masked_range(std::__to_address(__first.__seg_), __bits_per_word - __n, 0u, _FillVal);
580 }
581 }
582
583 template <class _Size, class _Tp>
584 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static __bit_iterator<_Cp, false>
585 operator()(__bit_iterator<_Cp, false> __first, _Size __n, const _Tp& __value) {
586 if (__n > 0) {
587 if (__value)
588 __impl<true>(__first, __n);
589 else
590 __impl<false>(__first, __n);
591 }
592 return __first + __n;
593 }
594};
595
596template <class _Cp, bool _IsConst>
597struct __specialized_algorithm<_Algorithm::__copy,
598 __iterator_pair<__bit_iterator<_Cp, _IsConst>, __bit_iterator<_Cp, _IsConst> >,
599 __single_iterator<__bit_iterator<_Cp, false> > > {
600 static const bool __has_algorithm = true;
601
602 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static __bit_iterator<_Cp, false>
603 __aligned_impl(__bit_iterator<_Cp, _IsConst> __first,
604 __bit_iterator<_Cp, _IsConst> __last,
605 __bit_iterator<_Cp, false> __result) {
606 using _In = __bit_iterator<_Cp, _IsConst>;
607 using difference_type = typename _In::difference_type;
608 using __storage_type = typename _In::__storage_type;
609
610 const int __bits_per_word = _In::__bits_per_word;
611 difference_type __n = __last - __first;
612 if (__n > 0) {
613 // do first word
614 if (__first.__ctz_ != 0) {
615 unsigned __clz = __bits_per_word - __first.__ctz_;
616 difference_type __dn = std::min(static_cast<difference_type>(__clz), __n);
617 __n -= __dn;
618 __storage_type __m = std::__middle_mask<__storage_type>(__clz - __dn, __first.__ctz_);
619 __storage_type __b = *__first.__seg_ & __m;
620 *__result.__seg_ &= ~__m;
621 *__result.__seg_ |= __b;
622 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
623 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
624 ++__first.__seg_;
625 // __first.__ctz_ = 0;
626 }
627 // __first.__ctz_ == 0;
628 // do middle words
629 __storage_type __nw = __n / __bits_per_word;
630 std::copy(std::__to_address(__first.__seg_),
631 std::__to_address(__first.__seg_ + __nw),
632 std::__to_address(__result.__seg_));
633 __n -= __nw * __bits_per_word;
634 __result.__seg_ += __nw;
635 // do last word
636 if (__n > 0) {
637 __first.__seg_ += __nw;
638 __storage_type __m = std::__trailing_mask<__storage_type>(__bits_per_word - __n);
639 __storage_type __b = *__first.__seg_ & __m;
640 *__result.__seg_ &= ~__m;
641 *__result.__seg_ |= __b;
642 __result.__ctz_ = static_cast<unsigned>(__n);
643 }
644 }
645 return __result;
646 }
647
648 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static __bit_iterator<_Cp, false>
649 __unaligned_impl(__bit_iterator<_Cp, _IsConst> __first,
650 __bit_iterator<_Cp, _IsConst> __last,
651 __bit_iterator<_Cp, false> __result) {
652 using _In = __bit_iterator<_Cp, _IsConst>;
653 using difference_type = typename _In::difference_type;
654 using __storage_type = typename _In::__storage_type;
655
656 const int __bits_per_word = _In::__bits_per_word;
657 difference_type __n = __last - __first;
658 if (__n > 0) {
659 // do first word
660 if (__first.__ctz_ != 0) {
661 unsigned __clz_f = __bits_per_word - __first.__ctz_;
662 difference_type __dn = std::min(static_cast<difference_type>(__clz_f), __n);
663 __n -= __dn;
664 __storage_type __m = std::__middle_mask<__storage_type>(__clz_f - __dn, __first.__ctz_);
665 __storage_type __b = *__first.__seg_ & __m;
666 unsigned __clz_r = __bits_per_word - __result.__ctz_;
667 __storage_type __ddn = std::min<__storage_type>(__dn, __clz_r);
668 __m = std::__middle_mask<__storage_type>(__clz_r - __ddn, __result.__ctz_);
669 *__result.__seg_ &= ~__m;
670 if (__result.__ctz_ > __first.__ctz_)
671 *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_);
672 else
673 *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_);
674 __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;
675 __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word);
676 __dn -= __ddn;
677 if (__dn > 0) {
678 __m = std::__trailing_mask<__storage_type>(__bits_per_word - __dn);
679 *__result.__seg_ &= ~__m;
680 *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn);
681 __result.__ctz_ = static_cast<unsigned>(__dn);
682 }
683 ++__first.__seg_;
684 // __first.__ctz_ = 0;
685 }
686 // __first.__ctz_ == 0;
687 // do middle words
688 unsigned __clz_r = __bits_per_word - __result.__ctz_;
689 __storage_type __m = std::__leading_mask<__storage_type>(__result.__ctz_);
690 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) {
691 __storage_type __b = *__first.__seg_;
692 *__result.__seg_ &= ~__m;
693 *__result.__seg_ |= __b << __result.__ctz_;
694 ++__result.__seg_;
695 *__result.__seg_ &= __m;
696 *__result.__seg_ |= __b >> __clz_r;
697 }
698 // do last word
699 if (__n > 0) {
700 __m = std::__trailing_mask<__storage_type>(__bits_per_word - __n);
701 __storage_type __b = *__first.__seg_ & __m;
702 __storage_type __dn = std::min(__n, static_cast<difference_type>(__clz_r));
703 __m = std::__middle_mask<__storage_type>(__clz_r - __dn, __result.__ctz_);
704 *__result.__seg_ &= ~__m;
705 *__result.__seg_ |= __b << __result.__ctz_;
706 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
707 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
708 __n -= __dn;
709 if (__n > 0) {
710 __m = std::__trailing_mask<__storage_type>(__bits_per_word - __n);
711 *__result.__seg_ &= ~__m;
712 *__result.__seg_ |= __b >> __dn;
713 __result.__ctz_ = static_cast<unsigned>(__n);
714 }
715 }
716 }
717 return __result;
718 }
719
720 _LIBCPP_HIDE_FROM_ABI
721 _LIBCPP_CONSTEXPR_SINCE_CXX20 static pair<__bit_iterator<_Cp, _IsConst>, __bit_iterator<_Cp, false> >
722 operator()(__bit_iterator<_Cp, _IsConst> __first,
723 __bit_iterator<_Cp, _IsConst> __last,
724 __bit_iterator<_Cp, false> __result) {
725 if (__first.__ctz_ == __result.__ctz_)
726 return std::make_pair(__last, __aligned_impl(__first, __last, __result));
727 return std::make_pair(__last, __unaligned_impl(__first, __last, __result));
728 }
729};
730
731_LIBCPP_END_NAMESPACE_STD
732
733_LIBCPP_POP_MACROS
734
735#endif // _LIBCPP___BIT_REFERENCE