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