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