Debian Codegraph @

libcxx/include/__cxx03/__bit_reference

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