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/min.h>
14#include <__bits>
15#include <__config>
16#include <__iterator/iterator_traits.h>
17#include <__memory/pointer_traits.h>
18#include <cstring>
19#include <type_traits>
20
21#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
22# pragma GCC system_header
23#endif
24
25_LIBCPP_PUSH_MACROS
26#include <__undef_macros>
27
28
29_LIBCPP_BEGIN_NAMESPACE_STD
30
31template <class _Cp, bool _IsConst, typename _Cp::__storage_type = 0> class __bit_iterator;
32template <class _Cp> class __bit_const_reference;
33
34template <class _Tp>
35struct __has_storage_type
36{
37 static const bool value = false;
38};
39
40template <class _Cp, bool = __has_storage_type<_Cp>::value>
41class __bit_reference
42{
43 typedef typename _Cp::__storage_type __storage_type;
44 typedef typename _Cp::__storage_pointer __storage_pointer;
45
46 __storage_pointer __seg_;
47 __storage_type __mask_;
48
49 friend typename _Cp::__self;
50
51 friend class __bit_const_reference<_Cp>;
52 friend class __bit_iterator<_Cp, false>;
53public:
54 _LIBCPP_INLINE_VISIBILITY
55 __bit_reference(const __bit_reference&) = default;
56
57 _LIBCPP_INLINE_VISIBILITY operator bool() const _NOEXCEPT
58 {return static_cast<bool>(*__seg_ & __mask_);}
59 _LIBCPP_INLINE_VISIBILITY bool operator ~() const _NOEXCEPT
60 {return !static_cast<bool>(*this);}
61
62 _LIBCPP_INLINE_VISIBILITY
63 __bit_reference& operator=(bool __x) _NOEXCEPT
64 {
65 if (__x)
66 *__seg_ |= __mask_;
67 else
68 *__seg_ &= ~__mask_;
69 return *this;
70 }
71
72#if _LIBCPP_STD_VER > 20
73 _LIBCPP_HIDE_FROM_ABI const __bit_reference& operator=(bool __x) const noexcept {
74 if (__x)
75 *__seg_ |= __mask_;
76 else
77 *__seg_ &= ~__mask_;
78 return *this;
79 }
80#endif
81
82 _LIBCPP_INLINE_VISIBILITY
83 __bit_reference& operator=(const __bit_reference& __x) _NOEXCEPT
84 {return operator=(static_cast<bool>(__x));}
85
86 _LIBCPP_INLINE_VISIBILITY void flip() _NOEXCEPT {*__seg_ ^= __mask_;}
87 _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, false> operator&() const _NOEXCEPT
88 {return __bit_iterator<_Cp, false>(__seg_, static_cast<unsigned>(__libcpp_ctz(__mask_)));}
89private:
90 _LIBCPP_INLINE_VISIBILITY
91 explicit __bit_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT
92 : __seg_(__s), __mask_(__m) {}
93};
94
95template <class _Cp>
96class __bit_reference<_Cp, false>
97{
98};
99
100template <class _Cp>
101inline _LIBCPP_INLINE_VISIBILITY
102void
103swap(__bit_reference<_Cp> __x, __bit_reference<_Cp> __y) _NOEXCEPT
104{
105 bool __t = __x;
106 __x = __y;
107 __y = __t;
108}
109
110template <class _Cp, class _Dp>
111inline _LIBCPP_INLINE_VISIBILITY
112void
113swap(__bit_reference<_Cp> __x, __bit_reference<_Dp> __y) _NOEXCEPT
114{
115 bool __t = __x;
116 __x = __y;
117 __y = __t;
118}
119
120template <class _Cp>
121inline _LIBCPP_INLINE_VISIBILITY
122void
123swap(__bit_reference<_Cp> __x, bool& __y) _NOEXCEPT
124{
125 bool __t = __x;
126 __x = __y;
127 __y = __t;
128}
129
130template <class _Cp>
131inline _LIBCPP_INLINE_VISIBILITY
132void
133swap(bool& __x, __bit_reference<_Cp> __y) _NOEXCEPT
134{
135 bool __t = __x;
136 __x = __y;
137 __y = __t;
138}
139
140template <class _Cp>
141class __bit_const_reference
142{
143 typedef typename _Cp::__storage_type __storage_type;
144 typedef typename _Cp::__const_storage_pointer __storage_pointer;
145
146 __storage_pointer __seg_;
147 __storage_type __mask_;
148
149 friend typename _Cp::__self;
150 friend class __bit_iterator<_Cp, true>;
151public:
152 _LIBCPP_INLINE_VISIBILITY
153 __bit_const_reference(const __bit_const_reference&) = default;
154
155 _LIBCPP_INLINE_VISIBILITY
156 __bit_const_reference(const __bit_reference<_Cp>& __x) _NOEXCEPT
157 : __seg_(__x.__seg_), __mask_(__x.__mask_) {}
158
159 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR operator bool() const _NOEXCEPT
160 {return static_cast<bool>(*__seg_ & __mask_);}
161
162 _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, true> operator&() const _NOEXCEPT
163 {return __bit_iterator<_Cp, true>(__seg_, static_cast<unsigned>(__libcpp_ctz(__mask_)));}
164private:
165 _LIBCPP_INLINE_VISIBILITY
166 _LIBCPP_CONSTEXPR
167 explicit __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT
168 : __seg_(__s), __mask_(__m) {}
169
170 __bit_const_reference& operator=(const __bit_const_reference&) = delete;
171};
172
173// find
174
175template <class _Cp, bool _IsConst>
176__bit_iterator<_Cp, _IsConst>
177__find_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
178{
179 typedef __bit_iterator<_Cp, _IsConst> _It;
180 typedef typename _It::__storage_type __storage_type;
181 static const int __bits_per_word = _It::__bits_per_word;
182 // do first partial word
183 if (__first.__ctz_ != 0)
184 {
185 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
186 __storage_type __dn = _VSTD::min(__clz_f, __n);
187 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
188 __storage_type __b = *__first.__seg_ & __m;
189 if (__b)
190 return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b)));
191 if (__n == __dn)
192 return __first + __n;
193 __n -= __dn;
194 ++__first.__seg_;
195 }
196 // do middle whole words
197 for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
198 if (*__first.__seg_)
199 return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(*__first.__seg_)));
200 // do last partial word
201 if (__n > 0)
202 {
203 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
204 __storage_type __b = *__first.__seg_ & __m;
205 if (__b)
206 return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b)));
207 }
208 return _It(__first.__seg_, static_cast<unsigned>(__n));
209}
210
211template <class _Cp, bool _IsConst>
212__bit_iterator<_Cp, _IsConst>
213__find_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
214{
215 typedef __bit_iterator<_Cp, _IsConst> _It;
216 typedef typename _It::__storage_type __storage_type;
217 const int __bits_per_word = _It::__bits_per_word;
218 // do first partial word
219 if (__first.__ctz_ != 0)
220 {
221 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
222 __storage_type __dn = _VSTD::min(__clz_f, __n);
223 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
224 __storage_type __b = ~*__first.__seg_ & __m;
225 if (__b)
226 return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b)));
227 if (__n == __dn)
228 return __first + __n;
229 __n -= __dn;
230 ++__first.__seg_;
231 }
232 // do middle whole words
233 for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
234 {
235 __storage_type __b = ~*__first.__seg_;
236 if (__b)
237 return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b)));
238 }
239 // do last partial word
240 if (__n > 0)
241 {
242 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
243 __storage_type __b = ~*__first.__seg_ & __m;
244 if (__b)
245 return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b)));
246 }
247 return _It(__first.__seg_, static_cast<unsigned>(__n));
248}
249
250template <class _Cp, bool _IsConst, class _Tp>
251inline _LIBCPP_INLINE_VISIBILITY
252__bit_iterator<_Cp, _IsConst>
253find(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value)
254{
255 if (static_cast<bool>(__value))
256 return _VSTD::__find_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first));
257 return _VSTD::__find_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first));
258}
259
260// count
261
262template <class _Cp, bool _IsConst>
263typename __bit_iterator<_Cp, _IsConst>::difference_type
264__count_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
265{
266 typedef __bit_iterator<_Cp, _IsConst> _It;
267 typedef typename _It::__storage_type __storage_type;
268 typedef typename _It::difference_type difference_type;
269 const int __bits_per_word = _It::__bits_per_word;
270 difference_type __r = 0;
271 // do first partial word
272 if (__first.__ctz_ != 0)
273 {
274 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
275 __storage_type __dn = _VSTD::min(__clz_f, __n);
276 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
277 __r = _VSTD::__libcpp_popcount(*__first.__seg_ & __m);
278 __n -= __dn;
279 ++__first.__seg_;
280 }
281 // do middle whole words
282 for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
283 __r += _VSTD::__libcpp_popcount(*__first.__seg_);
284 // do last partial word
285 if (__n > 0)
286 {
287 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
288 __r += _VSTD::__libcpp_popcount(*__first.__seg_ & __m);
289 }
290 return __r;
291}
292
293template <class _Cp, bool _IsConst>
294typename __bit_iterator<_Cp, _IsConst>::difference_type
295__count_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
296{
297 typedef __bit_iterator<_Cp, _IsConst> _It;
298 typedef typename _It::__storage_type __storage_type;
299 typedef typename _It::difference_type difference_type;
300 const int __bits_per_word = _It::__bits_per_word;
301 difference_type __r = 0;
302 // do first partial word
303 if (__first.__ctz_ != 0)
304 {
305 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
306 __storage_type __dn = _VSTD::min(__clz_f, __n);
307 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
308 __r = _VSTD::__libcpp_popcount(~*__first.__seg_ & __m);
309 __n -= __dn;
310 ++__first.__seg_;
311 }
312 // do middle whole words
313 for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
314 __r += _VSTD::__libcpp_popcount(~*__first.__seg_);
315 // do last partial word
316 if (__n > 0)
317 {
318 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
319 __r += _VSTD::__libcpp_popcount(~*__first.__seg_ & __m);
320 }
321 return __r;
322}
323
324template <class _Cp, bool _IsConst, class _Tp>
325inline _LIBCPP_INLINE_VISIBILITY
326typename __bit_iterator<_Cp, _IsConst>::difference_type
327count(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value)
328{
329 if (static_cast<bool>(__value))
330 return _VSTD::__count_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first));
331 return _VSTD::__count_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first));
332}
333
334// fill_n
335
336template <class _Cp>
337void
338__fill_n_false(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n)
339{
340 typedef __bit_iterator<_Cp, false> _It;
341 typedef typename _It::__storage_type __storage_type;
342 const int __bits_per_word = _It::__bits_per_word;
343 // do first partial word
344 if (__first.__ctz_ != 0)
345 {
346 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
347 __storage_type __dn = _VSTD::min(__clz_f, __n);
348 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
349 *__first.__seg_ &= ~__m;
350 __n -= __dn;
351 ++__first.__seg_;
352 }
353 // do middle whole words
354 __storage_type __nw = __n / __bits_per_word;
355 _VSTD::memset(_VSTD::__to_address(__first.__seg_), c: 0, n: __nw * sizeof(__storage_type));
356 __n -= __nw * __bits_per_word;
357 // do last partial word
358 if (__n > 0)
359 {
360 __first.__seg_ += __nw;
361 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
362 *__first.__seg_ &= ~__m;
363 }
364}
365
366template <class _Cp>
367void
368__fill_n_true(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n)
369{
370 typedef __bit_iterator<_Cp, false> _It;
371 typedef typename _It::__storage_type __storage_type;
372 const int __bits_per_word = _It::__bits_per_word;
373 // do first partial word
374 if (__first.__ctz_ != 0)
375 {
376 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
377 __storage_type __dn = _VSTD::min(__clz_f, __n);
378 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
379 *__first.__seg_ |= __m;
380 __n -= __dn;
381 ++__first.__seg_;
382 }
383 // do middle whole words
384 __storage_type __nw = __n / __bits_per_word;
385 _VSTD::memset(_VSTD::__to_address(__first.__seg_), c: -1, n: __nw * sizeof(__storage_type));
386 __n -= __nw * __bits_per_word;
387 // do last partial word
388 if (__n > 0)
389 {
390 __first.__seg_ += __nw;
391 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
392 *__first.__seg_ |= __m;
393 }
394}
395
396template <class _Cp>
397inline _LIBCPP_INLINE_VISIBILITY
398void
399fill_n(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n, bool __value)
400{
401 if (__n > 0)
402 {
403 if (__value)
404 _VSTD::__fill_n_true(__first, __n);
405 else
406 _VSTD::__fill_n_false(__first, __n);
407 }
408}
409
410// fill
411
412template <class _Cp>
413inline _LIBCPP_INLINE_VISIBILITY
414void
415fill(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __last, bool __value)
416{
417 _VSTD::fill_n(__first, static_cast<typename _Cp::size_type>(__last - __first), __value);
418}
419
420// copy
421
422template <class _Cp, bool _IsConst>
423__bit_iterator<_Cp, false>
424__copy_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
425 __bit_iterator<_Cp, false> __result)
426{
427 typedef __bit_iterator<_Cp, _IsConst> _In;
428 typedef typename _In::difference_type difference_type;
429 typedef typename _In::__storage_type __storage_type;
430 const int __bits_per_word = _In::__bits_per_word;
431 difference_type __n = __last - __first;
432 if (__n > 0)
433 {
434 // do first word
435 if (__first.__ctz_ != 0)
436 {
437 unsigned __clz = __bits_per_word - __first.__ctz_;
438 difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
439 __n -= __dn;
440 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
441 __storage_type __b = *__first.__seg_ & __m;
442 *__result.__seg_ &= ~__m;
443 *__result.__seg_ |= __b;
444 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
445 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
446 ++__first.__seg_;
447 // __first.__ctz_ = 0;
448 }
449 // __first.__ctz_ == 0;
450 // do middle words
451 __storage_type __nw = __n / __bits_per_word;
452 _VSTD::memmove(_VSTD::__to_address(__result.__seg_),
453 _VSTD::__to_address(__first.__seg_),
454 n: __nw * sizeof(__storage_type));
455 __n -= __nw * __bits_per_word;
456 __result.__seg_ += __nw;
457 // do last word
458 if (__n > 0)
459 {
460 __first.__seg_ += __nw;
461 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
462 __storage_type __b = *__first.__seg_ & __m;
463 *__result.__seg_ &= ~__m;
464 *__result.__seg_ |= __b;
465 __result.__ctz_ = static_cast<unsigned>(__n);
466 }
467 }
468 return __result;
469}
470
471template <class _Cp, bool _IsConst>
472__bit_iterator<_Cp, false>
473__copy_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
474 __bit_iterator<_Cp, false> __result)
475{
476 typedef __bit_iterator<_Cp, _IsConst> _In;
477 typedef typename _In::difference_type difference_type;
478 typedef typename _In::__storage_type __storage_type;
479 static const int __bits_per_word = _In::__bits_per_word;
480 difference_type __n = __last - __first;
481 if (__n > 0)
482 {
483 // do first word
484 if (__first.__ctz_ != 0)
485 {
486 unsigned __clz_f = __bits_per_word - __first.__ctz_;
487 difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
488 __n -= __dn;
489 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
490 __storage_type __b = *__first.__seg_ & __m;
491 unsigned __clz_r = __bits_per_word - __result.__ctz_;
492 __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
493 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
494 *__result.__seg_ &= ~__m;
495 if (__result.__ctz_ > __first.__ctz_)
496 *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_);
497 else
498 *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_);
499 __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;
500 __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word);
501 __dn -= __ddn;
502 if (__dn > 0)
503 {
504 __m = ~__storage_type(0) >> (__bits_per_word - __dn);
505 *__result.__seg_ &= ~__m;
506 *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn);
507 __result.__ctz_ = static_cast<unsigned>(__dn);
508 }
509 ++__first.__seg_;
510 // __first.__ctz_ = 0;
511 }
512 // __first.__ctz_ == 0;
513 // do middle words
514 unsigned __clz_r = __bits_per_word - __result.__ctz_;
515 __storage_type __m = ~__storage_type(0) << __result.__ctz_;
516 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_)
517 {
518 __storage_type __b = *__first.__seg_;
519 *__result.__seg_ &= ~__m;
520 *__result.__seg_ |= __b << __result.__ctz_;
521 ++__result.__seg_;
522 *__result.__seg_ &= __m;
523 *__result.__seg_ |= __b >> __clz_r;
524 }
525 // do last word
526 if (__n > 0)
527 {
528 __m = ~__storage_type(0) >> (__bits_per_word - __n);
529 __storage_type __b = *__first.__seg_ & __m;
530 __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r));
531 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
532 *__result.__seg_ &= ~__m;
533 *__result.__seg_ |= __b << __result.__ctz_;
534 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
535 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
536 __n -= __dn;
537 if (__n > 0)
538 {
539 __m = ~__storage_type(0) >> (__bits_per_word - __n);
540 *__result.__seg_ &= ~__m;
541 *__result.__seg_ |= __b >> __dn;
542 __result.__ctz_ = static_cast<unsigned>(__n);
543 }
544 }
545 }
546 return __result;
547}
548
549template <class _Cp, bool _IsConst>
550inline _LIBCPP_INLINE_VISIBILITY
551__bit_iterator<_Cp, false>
552copy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
553{
554 if (__first.__ctz_ == __result.__ctz_)
555 return _VSTD::__copy_aligned(__first, __last, __result);
556 return _VSTD::__copy_unaligned(__first, __last, __result);
557}
558
559// copy_backward
560
561template <class _Cp, bool _IsConst>
562__bit_iterator<_Cp, false>
563__copy_backward_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
564 __bit_iterator<_Cp, false> __result)
565{
566 typedef __bit_iterator<_Cp, _IsConst> _In;
567 typedef typename _In::difference_type difference_type;
568 typedef typename _In::__storage_type __storage_type;
569 const int __bits_per_word = _In::__bits_per_word;
570 difference_type __n = __last - __first;
571 if (__n > 0)
572 {
573 // do first word
574 if (__last.__ctz_ != 0)
575 {
576 difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n);
577 __n -= __dn;
578 unsigned __clz = __bits_per_word - __last.__ctz_;
579 __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz);
580 __storage_type __b = *__last.__seg_ & __m;
581 *__result.__seg_ &= ~__m;
582 *__result.__seg_ |= __b;
583 __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) +
584 __result.__ctz_) % __bits_per_word);
585 // __last.__ctz_ = 0
586 }
587 // __last.__ctz_ == 0 || __n == 0
588 // __result.__ctz_ == 0 || __n == 0
589 // do middle words
590 __storage_type __nw = __n / __bits_per_word;
591 __result.__seg_ -= __nw;
592 __last.__seg_ -= __nw;
593 _VSTD::memmove(_VSTD::__to_address(__result.__seg_),
594 _VSTD::__to_address(__last.__seg_),
595 n: __nw * sizeof(__storage_type));
596 __n -= __nw * __bits_per_word;
597 // do last word
598 if (__n > 0)
599 {
600 __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n);
601 __storage_type __b = *--__last.__seg_ & __m;
602 *--__result.__seg_ &= ~__m;
603 *__result.__seg_ |= __b;
604 __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));
605 }
606 }
607 return __result;
608}
609
610template <class _Cp, bool _IsConst>
611__bit_iterator<_Cp, false>
612__copy_backward_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
613 __bit_iterator<_Cp, false> __result)
614{
615 typedef __bit_iterator<_Cp, _IsConst> _In;
616 typedef typename _In::difference_type difference_type;
617 typedef typename _In::__storage_type __storage_type;
618 const int __bits_per_word = _In::__bits_per_word;
619 difference_type __n = __last - __first;
620 if (__n > 0)
621 {
622 // do first word
623 if (__last.__ctz_ != 0)
624 {
625 difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n);
626 __n -= __dn;
627 unsigned __clz_l = __bits_per_word - __last.__ctz_;
628 __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l);
629 __storage_type __b = *__last.__seg_ & __m;
630 unsigned __clz_r = __bits_per_word - __result.__ctz_;
631 __storage_type __ddn = _VSTD::min(__dn, static_cast<difference_type>(__result.__ctz_));
632 if (__ddn > 0)
633 {
634 __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r);
635 *__result.__seg_ &= ~__m;
636 if (__result.__ctz_ > __last.__ctz_)
637 *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);
638 else
639 *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_);
640 __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) +
641 __result.__ctz_) % __bits_per_word);
642 __dn -= __ddn;
643 }
644 if (__dn > 0)
645 {
646 // __result.__ctz_ == 0
647 --__result.__seg_;
648 __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1));
649 __m = ~__storage_type(0) << __result.__ctz_;
650 *__result.__seg_ &= ~__m;
651 __last.__ctz_ -= __dn + __ddn;
652 *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);
653 }
654 // __last.__ctz_ = 0
655 }
656 // __last.__ctz_ == 0 || __n == 0
657 // __result.__ctz_ != 0 || __n == 0
658 // do middle words
659 unsigned __clz_r = __bits_per_word - __result.__ctz_;
660 __storage_type __m = ~__storage_type(0) >> __clz_r;
661 for (; __n >= __bits_per_word; __n -= __bits_per_word)
662 {
663 __storage_type __b = *--__last.__seg_;
664 *__result.__seg_ &= ~__m;
665 *__result.__seg_ |= __b >> __clz_r;
666 *--__result.__seg_ &= __m;
667 *__result.__seg_ |= __b << __result.__ctz_;
668 }
669 // do last word
670 if (__n > 0)
671 {
672 __m = ~__storage_type(0) << (__bits_per_word - __n);
673 __storage_type __b = *--__last.__seg_ & __m;
674 __clz_r = __bits_per_word - __result.__ctz_;
675 __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__result.__ctz_));
676 __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r);
677 *__result.__seg_ &= ~__m;
678 *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_);
679 __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) +
680 __result.__ctz_) % __bits_per_word);
681 __n -= __dn;
682 if (__n > 0)
683 {
684 // __result.__ctz_ == 0
685 --__result.__seg_;
686 __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));
687 __m = ~__storage_type(0) << __result.__ctz_;
688 *__result.__seg_ &= ~__m;
689 *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn));
690 }
691 }
692 }
693 return __result;
694}
695
696template <class _Cp, bool _IsConst>
697inline _LIBCPP_INLINE_VISIBILITY
698__bit_iterator<_Cp, false>
699copy_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
700{
701 if (__last.__ctz_ == __result.__ctz_)
702 return _VSTD::__copy_backward_aligned(__first, __last, __result);
703 return _VSTD::__copy_backward_unaligned(__first, __last, __result);
704}
705
706// move
707
708template <class _Cp, bool _IsConst>
709inline _LIBCPP_INLINE_VISIBILITY
710__bit_iterator<_Cp, false>
711move(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
712{
713 return _VSTD::copy(__first, __last, __result);
714}
715
716// move_backward
717
718template <class _Cp, bool _IsConst>
719inline _LIBCPP_INLINE_VISIBILITY
720__bit_iterator<_Cp, false>
721move_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
722{
723 return _VSTD::copy_backward(__first, __last, __result);
724}
725
726// swap_ranges
727
728template <class __C1, class __C2>
729__bit_iterator<__C2, false>
730__swap_ranges_aligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last,
731 __bit_iterator<__C2, false> __result)
732{
733 typedef __bit_iterator<__C1, false> _I1;
734 typedef typename _I1::difference_type difference_type;
735 typedef typename _I1::__storage_type __storage_type;
736 const int __bits_per_word = _I1::__bits_per_word;
737 difference_type __n = __last - __first;
738 if (__n > 0)
739 {
740 // do first word
741 if (__first.__ctz_ != 0)
742 {
743 unsigned __clz = __bits_per_word - __first.__ctz_;
744 difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
745 __n -= __dn;
746 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
747 __storage_type __b1 = *__first.__seg_ & __m;
748 *__first.__seg_ &= ~__m;
749 __storage_type __b2 = *__result.__seg_ & __m;
750 *__result.__seg_ &= ~__m;
751 *__result.__seg_ |= __b1;
752 *__first.__seg_ |= __b2;
753 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
754 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
755 ++__first.__seg_;
756 // __first.__ctz_ = 0;
757 }
758 // __first.__ctz_ == 0;
759 // do middle words
760 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_)
761 swap(*__first.__seg_, *__result.__seg_);
762 // do last word
763 if (__n > 0)
764 {
765 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
766 __storage_type __b1 = *__first.__seg_ & __m;
767 *__first.__seg_ &= ~__m;
768 __storage_type __b2 = *__result.__seg_ & __m;
769 *__result.__seg_ &= ~__m;
770 *__result.__seg_ |= __b1;
771 *__first.__seg_ |= __b2;
772 __result.__ctz_ = static_cast<unsigned>(__n);
773 }
774 }
775 return __result;
776}
777
778template <class __C1, class __C2>
779__bit_iterator<__C2, false>
780__swap_ranges_unaligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last,
781 __bit_iterator<__C2, false> __result)
782{
783 typedef __bit_iterator<__C1, false> _I1;
784 typedef typename _I1::difference_type difference_type;
785 typedef typename _I1::__storage_type __storage_type;
786 const int __bits_per_word = _I1::__bits_per_word;
787 difference_type __n = __last - __first;
788 if (__n > 0)
789 {
790 // do first word
791 if (__first.__ctz_ != 0)
792 {
793 unsigned __clz_f = __bits_per_word - __first.__ctz_;
794 difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
795 __n -= __dn;
796 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
797 __storage_type __b1 = *__first.__seg_ & __m;
798 *__first.__seg_ &= ~__m;
799 unsigned __clz_r = __bits_per_word - __result.__ctz_;
800 __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
801 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
802 __storage_type __b2 = *__result.__seg_ & __m;
803 *__result.__seg_ &= ~__m;
804 if (__result.__ctz_ > __first.__ctz_)
805 {
806 unsigned __s = __result.__ctz_ - __first.__ctz_;
807 *__result.__seg_ |= __b1 << __s;
808 *__first.__seg_ |= __b2 >> __s;
809 }
810 else
811 {
812 unsigned __s = __first.__ctz_ - __result.__ctz_;
813 *__result.__seg_ |= __b1 >> __s;
814 *__first.__seg_ |= __b2 << __s;
815 }
816 __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;
817 __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word);
818 __dn -= __ddn;
819 if (__dn > 0)
820 {
821 __m = ~__storage_type(0) >> (__bits_per_word - __dn);
822 __b2 = *__result.__seg_ & __m;
823 *__result.__seg_ &= ~__m;
824 unsigned __s = __first.__ctz_ + __ddn;
825 *__result.__seg_ |= __b1 >> __s;
826 *__first.__seg_ |= __b2 << __s;
827 __result.__ctz_ = static_cast<unsigned>(__dn);
828 }
829 ++__first.__seg_;
830 // __first.__ctz_ = 0;
831 }
832 // __first.__ctz_ == 0;
833 // do middle words
834 __storage_type __m = ~__storage_type(0) << __result.__ctz_;
835 unsigned __clz_r = __bits_per_word - __result.__ctz_;
836 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_)
837 {
838 __storage_type __b1 = *__first.__seg_;
839 __storage_type __b2 = *__result.__seg_ & __m;
840 *__result.__seg_ &= ~__m;
841 *__result.__seg_ |= __b1 << __result.__ctz_;
842 *__first.__seg_ = __b2 >> __result.__ctz_;
843 ++__result.__seg_;
844 __b2 = *__result.__seg_ & ~__m;
845 *__result.__seg_ &= __m;
846 *__result.__seg_ |= __b1 >> __clz_r;
847 *__first.__seg_ |= __b2 << __clz_r;
848 }
849 // do last word
850 if (__n > 0)
851 {
852 __m = ~__storage_type(0) >> (__bits_per_word - __n);
853 __storage_type __b1 = *__first.__seg_ & __m;
854 *__first.__seg_ &= ~__m;
855 __storage_type __dn = _VSTD::min<__storage_type>(__n, __clz_r);
856 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
857 __storage_type __b2 = *__result.__seg_ & __m;
858 *__result.__seg_ &= ~__m;
859 *__result.__seg_ |= __b1 << __result.__ctz_;
860 *__first.__seg_ |= __b2 >> __result.__ctz_;
861 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
862 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
863 __n -= __dn;
864 if (__n > 0)
865 {
866 __m = ~__storage_type(0) >> (__bits_per_word - __n);
867 __b2 = *__result.__seg_ & __m;
868 *__result.__seg_ &= ~__m;
869 *__result.__seg_ |= __b1 >> __dn;
870 *__first.__seg_ |= __b2 << __dn;
871 __result.__ctz_ = static_cast<unsigned>(__n);
872 }
873 }
874 }
875 return __result;
876}
877
878template <class __C1, class __C2>
879inline _LIBCPP_INLINE_VISIBILITY
880__bit_iterator<__C2, false>
881swap_ranges(__bit_iterator<__C1, false> __first1, __bit_iterator<__C1, false> __last1,
882 __bit_iterator<__C2, false> __first2)
883{
884 if (__first1.__ctz_ == __first2.__ctz_)
885 return _VSTD::__swap_ranges_aligned(__first1, __last1, __first2);
886 return _VSTD::__swap_ranges_unaligned(__first1, __last1, __first2);
887}
888
889// rotate
890
891template <class _Cp>
892struct __bit_array
893{
894 typedef typename _Cp::difference_type difference_type;
895 typedef typename _Cp::__storage_type __storage_type;
896 typedef typename _Cp::__storage_pointer __storage_pointer;
897 typedef typename _Cp::iterator iterator;
898 static const unsigned __bits_per_word = _Cp::__bits_per_word;
899 static const unsigned _Np = 4;
900
901 difference_type __size_;
902 __storage_type __word_[_Np];
903
904 _LIBCPP_INLINE_VISIBILITY static difference_type capacity()
905 {return static_cast<difference_type>(_Np * __bits_per_word);}
906 _LIBCPP_INLINE_VISIBILITY explicit __bit_array(difference_type __s) : __size_(__s) {}
907 _LIBCPP_INLINE_VISIBILITY iterator begin()
908 {
909 return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]), 0);
910 }
911 _LIBCPP_INLINE_VISIBILITY iterator end()
912 {
913 return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]) + __size_ / __bits_per_word,
914 static_cast<unsigned>(__size_ % __bits_per_word));
915 }
916};
917
918template <class _Cp>
919__bit_iterator<_Cp, false>
920rotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last)
921{
922 typedef __bit_iterator<_Cp, false> _I1;
923 typedef typename _I1::difference_type difference_type;
924 difference_type __d1 = __middle - __first;
925 difference_type __d2 = __last - __middle;
926 _I1 __r = __first + __d2;
927 while (__d1 != 0 && __d2 != 0)
928 {
929 if (__d1 <= __d2)
930 {
931 if (__d1 <= __bit_array<_Cp>::capacity())
932 {
933 __bit_array<_Cp> __b(__d1);
934 _VSTD::copy(__first, __middle, __b.begin());
935 _VSTD::copy(__b.begin(), __b.end(), _VSTD::copy(__middle, __last, __first));
936 break;
937 }
938 else
939 {
940 __bit_iterator<_Cp, false> __mp = _VSTD::swap_ranges(__first, __middle, __middle);
941 __first = __middle;
942 __middle = __mp;
943 __d2 -= __d1;
944 }
945 }
946 else
947 {
948 if (__d2 <= __bit_array<_Cp>::capacity())
949 {
950 __bit_array<_Cp> __b(__d2);
951 _VSTD::copy(__middle, __last, __b.begin());
952 _VSTD::copy_backward(__b.begin(), __b.end(), _VSTD::copy_backward(__first, __middle, __last));
953 break;
954 }
955 else
956 {
957 __bit_iterator<_Cp, false> __mp = __first + __d2;
958 _VSTD::swap_ranges(__first, __mp, __middle);
959 __first = __mp;
960 __d1 -= __d2;
961 }
962 }
963 }
964 return __r;
965}
966
967// equal
968
969template <class _Cp, bool _IC1, bool _IC2>
970bool
971__equal_unaligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1,
972 __bit_iterator<_Cp, _IC2> __first2)
973{
974 typedef __bit_iterator<_Cp, _IC1> _It;
975 typedef typename _It::difference_type difference_type;
976 typedef typename _It::__storage_type __storage_type;
977 static const int __bits_per_word = _It::__bits_per_word;
978 difference_type __n = __last1 - __first1;
979 if (__n > 0)
980 {
981 // do first word
982 if (__first1.__ctz_ != 0)
983 {
984 unsigned __clz_f = __bits_per_word - __first1.__ctz_;
985 difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
986 __n -= __dn;
987 __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
988 __storage_type __b = *__first1.__seg_ & __m;
989 unsigned __clz_r = __bits_per_word - __first2.__ctz_;
990 __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
991 __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
992 if (__first2.__ctz_ > __first1.__ctz_)
993 {
994 if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_)))
995 return false;
996 }
997 else
998 {
999 if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_)))
1000 return false;
1001 }
1002 __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word;
1003 __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word);
1004 __dn -= __ddn;
1005 if (__dn > 0)
1006 {
1007 __m = ~__storage_type(0) >> (__bits_per_word - __dn);
1008 if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn)))
1009 return false;
1010 __first2.__ctz_ = static_cast<unsigned>(__dn);
1011 }
1012 ++__first1.__seg_;
1013 // __first1.__ctz_ = 0;
1014 }
1015 // __first1.__ctz_ == 0;
1016 // do middle words
1017 unsigned __clz_r = __bits_per_word - __first2.__ctz_;
1018 __storage_type __m = ~__storage_type(0) << __first2.__ctz_;
1019 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_)
1020 {
1021 __storage_type __b = *__first1.__seg_;
1022 if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_))
1023 return false;
1024 ++__first2.__seg_;
1025 if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r))
1026 return false;
1027 }
1028 // do last word
1029 if (__n > 0)
1030 {
1031 __m = ~__storage_type(0) >> (__bits_per_word - __n);
1032 __storage_type __b = *__first1.__seg_ & __m;
1033 __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r));
1034 __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
1035 if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_))
1036 return false;
1037 __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word;
1038 __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word);
1039 __n -= __dn;
1040 if (__n > 0)
1041 {
1042 __m = ~__storage_type(0) >> (__bits_per_word - __n);
1043 if ((*__first2.__seg_ & __m) != (__b >> __dn))
1044 return false;
1045 }
1046 }
1047 }
1048 return true;
1049}
1050
1051template <class _Cp, bool _IC1, bool _IC2>
1052bool
1053__equal_aligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1,
1054 __bit_iterator<_Cp, _IC2> __first2)
1055{
1056 typedef __bit_iterator<_Cp, _IC1> _It;
1057 typedef typename _It::difference_type difference_type;
1058 typedef typename _It::__storage_type __storage_type;
1059 static const int __bits_per_word = _It::__bits_per_word;
1060 difference_type __n = __last1 - __first1;
1061 if (__n > 0)
1062 {
1063 // do first word
1064 if (__first1.__ctz_ != 0)
1065 {
1066 unsigned __clz = __bits_per_word - __first1.__ctz_;
1067 difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
1068 __n -= __dn;
1069 __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
1070 if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))
1071 return false;
1072 ++__first2.__seg_;
1073 ++__first1.__seg_;
1074 // __first1.__ctz_ = 0;
1075 // __first2.__ctz_ = 0;
1076 }
1077 // __first1.__ctz_ == 0;
1078 // __first2.__ctz_ == 0;
1079 // do middle words
1080 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_)
1081 if (*__first2.__seg_ != *__first1.__seg_)
1082 return false;
1083 // do last word
1084 if (__n > 0)
1085 {
1086 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
1087 if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))
1088 return false;
1089 }
1090 }
1091 return true;
1092}
1093
1094template <class _Cp, bool _IC1, bool _IC2>
1095inline _LIBCPP_INLINE_VISIBILITY
1096bool
1097equal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2)
1098{
1099 if (__first1.__ctz_ == __first2.__ctz_)
1100 return _VSTD::__equal_aligned(__first1, __last1, __first2);
1101 return _VSTD::__equal_unaligned(__first1, __last1, __first2);
1102}
1103
1104template <class _Cp, bool _IsConst,
1105 typename _Cp::__storage_type>
1106class __bit_iterator
1107{
1108public:
1109 typedef typename _Cp::difference_type difference_type;
1110 typedef bool value_type;
1111 typedef __bit_iterator pointer;
1112#ifndef _LIBCPP_ABI_BITSET_VECTOR_BOOL_CONST_SUBSCRIPT_RETURN_BOOL
1113 typedef typename conditional<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >::type reference;
1114#else
1115 using reference = typename conditional<_IsConst, bool, __bit_reference<_Cp> >::type;
1116#endif
1117 typedef random_access_iterator_tag iterator_category;
1118
1119private:
1120 typedef typename _Cp::__storage_type __storage_type;
1121 typedef typename conditional<_IsConst, typename _Cp::__const_storage_pointer,
1122 typename _Cp::__storage_pointer>::type __storage_pointer;
1123 static const unsigned __bits_per_word = _Cp::__bits_per_word;
1124
1125 __storage_pointer __seg_;
1126 unsigned __ctz_;
1127
1128public:
1129 _LIBCPP_INLINE_VISIBILITY __bit_iterator() _NOEXCEPT
1130#if _LIBCPP_STD_VER > 11
1131 : __seg_(nullptr), __ctz_(0)
1132#endif
1133 {}
1134
1135 // When _IsConst=false, this is the copy constructor.
1136 // It is non-trivial. Making it trivial would break ABI.
1137 // When _IsConst=true, this is a converting constructor;
1138 // the copy and move constructors are implicitly generated
1139 // and trivial.
1140 _LIBCPP_INLINE_VISIBILITY
1141 __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT
1142 : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {}
1143
1144 // When _IsConst=false, we have a user-provided copy constructor,
1145 // so we must also provide a copy assignment operator because
1146 // the implicit generation of a defaulted one is deprecated.
1147 // When _IsConst=true, the assignment operators are
1148 // implicitly generated and trivial.
1149 _LIBCPP_INLINE_VISIBILITY
1150 __bit_iterator& operator=(const _If<_IsConst, struct __private_nat, __bit_iterator>& __it) {
1151 __seg_ = __it.__seg_;
1152 __ctz_ = __it.__ctz_;
1153 return *this;
1154 }
1155
1156 _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT {
1157 return typename conditional<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >
1158 ::type(__seg_, __storage_type(1) << __ctz_);
1159 }
1160
1161 _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator++()
1162 {
1163 if (__ctz_ != __bits_per_word-1)
1164 ++__ctz_;
1165 else
1166 {
1167 __ctz_ = 0;
1168 ++__seg_;
1169 }
1170 return *this;
1171 }
1172
1173 _LIBCPP_INLINE_VISIBILITY __bit_iterator operator++(int)
1174 {
1175 __bit_iterator __tmp = *this;
1176 ++(*this);
1177 return __tmp;
1178 }
1179
1180 _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator--()
1181 {
1182 if (__ctz_ != 0)
1183 --__ctz_;
1184 else
1185 {
1186 __ctz_ = __bits_per_word - 1;
1187 --__seg_;
1188 }
1189 return *this;
1190 }
1191
1192 _LIBCPP_INLINE_VISIBILITY __bit_iterator operator--(int)
1193 {
1194 __bit_iterator __tmp = *this;
1195 --(*this);
1196 return __tmp;
1197 }
1198
1199 _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator+=(difference_type __n)
1200 {
1201 if (__n >= 0)
1202 __seg_ += (__n + __ctz_) / __bits_per_word;
1203 else
1204 __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1)
1205 / static_cast<difference_type>(__bits_per_word);
1206 __n &= (__bits_per_word - 1);
1207 __ctz_ = static_cast<unsigned>((__n + __ctz_) % __bits_per_word);
1208 return *this;
1209 }
1210
1211 _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator-=(difference_type __n)
1212 {
1213 return *this += -__n;
1214 }
1215
1216 _LIBCPP_INLINE_VISIBILITY __bit_iterator operator+(difference_type __n) const
1217 {
1218 __bit_iterator __t(*this);
1219 __t += __n;
1220 return __t;
1221 }
1222
1223 _LIBCPP_INLINE_VISIBILITY __bit_iterator operator-(difference_type __n) const
1224 {
1225 __bit_iterator __t(*this);
1226 __t -= __n;
1227 return __t;
1228 }
1229
1230 _LIBCPP_INLINE_VISIBILITY
1231 friend __bit_iterator operator+(difference_type __n, const __bit_iterator& __it) {return __it + __n;}
1232
1233 _LIBCPP_INLINE_VISIBILITY
1234 friend difference_type operator-(const __bit_iterator& __x, const __bit_iterator& __y)
1235 {return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;}
1236
1237 _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const {return *(*this + __n);}
1238
1239 _LIBCPP_INLINE_VISIBILITY friend bool operator==(const __bit_iterator& __x, const __bit_iterator& __y)
1240 {return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;}
1241
1242 _LIBCPP_INLINE_VISIBILITY friend bool operator!=(const __bit_iterator& __x, const __bit_iterator& __y)
1243 {return !(__x == __y);}
1244
1245 _LIBCPP_INLINE_VISIBILITY friend bool operator<(const __bit_iterator& __x, const __bit_iterator& __y)
1246 {return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);}
1247
1248 _LIBCPP_INLINE_VISIBILITY friend bool operator>(const __bit_iterator& __x, const __bit_iterator& __y)
1249 {return __y < __x;}
1250
1251 _LIBCPP_INLINE_VISIBILITY friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y)
1252 {return !(__y < __x);}
1253
1254 _LIBCPP_INLINE_VISIBILITY friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y)
1255 {return !(__x < __y);}
1256
1257private:
1258 _LIBCPP_INLINE_VISIBILITY
1259 explicit __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT
1260 : __seg_(__s), __ctz_(__ctz) {}
1261
1262 friend typename _Cp::__self;
1263
1264 friend class __bit_reference<_Cp>;
1265 friend class __bit_const_reference<_Cp>;
1266 friend class __bit_iterator<_Cp, true>;
1267 template <class _Dp> friend struct __bit_array;
1268 template <class _Dp> friend void __fill_n_false(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n);
1269 template <class _Dp> friend void __fill_n_true(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n);
1270 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_aligned(__bit_iterator<_Dp, _IC> __first,
1271 __bit_iterator<_Dp, _IC> __last,
1272 __bit_iterator<_Dp, false> __result);
1273 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_unaligned(__bit_iterator<_Dp, _IC> __first,
1274 __bit_iterator<_Dp, _IC> __last,
1275 __bit_iterator<_Dp, false> __result);
1276 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy(__bit_iterator<_Dp, _IC> __first,
1277 __bit_iterator<_Dp, _IC> __last,
1278 __bit_iterator<_Dp, false> __result);
1279 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_aligned(__bit_iterator<_Dp, _IC> __first,
1280 __bit_iterator<_Dp, _IC> __last,
1281 __bit_iterator<_Dp, false> __result);
1282 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_unaligned(__bit_iterator<_Dp, _IC> __first,
1283 __bit_iterator<_Dp, _IC> __last,
1284 __bit_iterator<_Dp, false> __result);
1285 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy_backward(__bit_iterator<_Dp, _IC> __first,
1286 __bit_iterator<_Dp, _IC> __last,
1287 __bit_iterator<_Dp, false> __result);
1288 template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_aligned(__bit_iterator<__C1, false>,
1289 __bit_iterator<__C1, false>,
1290 __bit_iterator<__C2, false>);
1291 template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_unaligned(__bit_iterator<__C1, false>,
1292 __bit_iterator<__C1, false>,
1293 __bit_iterator<__C2, false>);
1294 template <class __C1, class __C2>friend __bit_iterator<__C2, false> swap_ranges(__bit_iterator<__C1, false>,
1295 __bit_iterator<__C1, false>,
1296 __bit_iterator<__C2, false>);
1297 template <class _Dp> friend __bit_iterator<_Dp, false> rotate(__bit_iterator<_Dp, false>,
1298 __bit_iterator<_Dp, false>,
1299 __bit_iterator<_Dp, false>);
1300 template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_aligned(__bit_iterator<_Dp, _IC1>,
1301 __bit_iterator<_Dp, _IC1>,
1302 __bit_iterator<_Dp, _IC2>);
1303 template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_unaligned(__bit_iterator<_Dp, _IC1>,
1304 __bit_iterator<_Dp, _IC1>,
1305 __bit_iterator<_Dp, _IC2>);
1306 template <class _Dp, bool _IC1, bool _IC2> friend bool equal(__bit_iterator<_Dp, _IC1>,
1307 __bit_iterator<_Dp, _IC1>,
1308 __bit_iterator<_Dp, _IC2>);
1309 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_true(__bit_iterator<_Dp, _IC>,
1310 typename _Dp::size_type);
1311 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_false(__bit_iterator<_Dp, _IC>,
1312 typename _Dp::size_type);
1313 template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type
1314 __count_bool_true(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
1315 template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type
1316 __count_bool_false(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
1317};
1318
1319_LIBCPP_END_NAMESPACE_STD
1320
1321_LIBCPP_POP_MACROS
1322
1323#endif // _LIBCPP___BIT_REFERENCE
1324

source code of flutter_engine/third_party/libcxx/include/__bit_reference