13e519524SHoward Hinnant// -*- C++ -*-
23e519524SHoward Hinnant//===----------------------------------------------------------------------===//
33e519524SHoward Hinnant//
45b08a8a4SHoward Hinnant//                     The LLVM Compiler Infrastructure
53e519524SHoward Hinnant//
6412dbebeSHoward Hinnant// This file is dual licensed under the MIT and the University of Illinois Open
7412dbebeSHoward Hinnant// Source Licenses. See LICENSE.TXT for details.
83e519524SHoward Hinnant//
93e519524SHoward Hinnant//===----------------------------------------------------------------------===//
103e519524SHoward Hinnant
113e519524SHoward Hinnant#ifndef _LIBCPP___BIT_REFERENCE
123e519524SHoward Hinnant#define _LIBCPP___BIT_REFERENCE
133e519524SHoward Hinnant
143e519524SHoward Hinnant#include <__config>
153e519524SHoward Hinnant#include <algorithm>
163e519524SHoward Hinnant
17073458b1SHoward Hinnant#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
183e519524SHoward Hinnant#pragma GCC system_header
19073458b1SHoward Hinnant#endif
203e519524SHoward Hinnant
21*a016efb1SEric Fiselier_LIBCPP_PUSH_MACROS
22*a016efb1SEric Fiselier#include <__undef_macros>
23*a016efb1SEric Fiselier
24*a016efb1SEric Fiselier
253e519524SHoward Hinnant_LIBCPP_BEGIN_NAMESPACE_STD
263e519524SHoward Hinnant
270ae9efebSHoward Hinnanttemplate <class _Cp, bool _IsConst, typename _Cp::__storage_type = 0> class __bit_iterator;
28c003db1fSHoward Hinnanttemplate <class _Cp> class __bit_const_reference;
293e519524SHoward Hinnant
30a7744562SHoward Hinnanttemplate <class _Tp>
31a7744562SHoward Hinnantstruct __has_storage_type
32a7744562SHoward Hinnant{
33a7744562SHoward Hinnant    static const bool value = false;
34a7744562SHoward Hinnant};
35a7744562SHoward Hinnant
36c003db1fSHoward Hinnanttemplate <class _Cp, bool = __has_storage_type<_Cp>::value>
373e519524SHoward Hinnantclass __bit_reference
383e519524SHoward Hinnant{
39c003db1fSHoward Hinnant    typedef typename _Cp::__storage_type    __storage_type;
40c003db1fSHoward Hinnant    typedef typename _Cp::__storage_pointer __storage_pointer;
413e519524SHoward Hinnant
423e519524SHoward Hinnant    __storage_pointer __seg_;
433e519524SHoward Hinnant    __storage_type    __mask_;
443e519524SHoward Hinnant
45c003db1fSHoward Hinnant    friend typename _Cp::__self;
46541f9e28SEric Fiselier
47c003db1fSHoward Hinnant    friend class __bit_const_reference<_Cp>;
48c003db1fSHoward Hinnant    friend class __bit_iterator<_Cp, false>;
493e519524SHoward Hinnantpublic:
50d368a84cSHoward Hinnant    _LIBCPP_INLINE_VISIBILITY operator bool() const _NOEXCEPT
51d368a84cSHoward Hinnant        {return static_cast<bool>(*__seg_ & __mask_);}
52d368a84cSHoward Hinnant    _LIBCPP_INLINE_VISIBILITY bool operator ~() const _NOEXCEPT
53d368a84cSHoward Hinnant        {return !static_cast<bool>(*this);}
543e519524SHoward Hinnant
553e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY
56d368a84cSHoward Hinnant    __bit_reference& operator=(bool __x) _NOEXCEPT
573e519524SHoward Hinnant    {
583e519524SHoward Hinnant        if (__x)
593e519524SHoward Hinnant            *__seg_ |= __mask_;
603e519524SHoward Hinnant        else
613e519524SHoward Hinnant            *__seg_ &= ~__mask_;
623e519524SHoward Hinnant        return *this;
633e519524SHoward Hinnant    }
643e519524SHoward Hinnant
653e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY
66d368a84cSHoward Hinnant    __bit_reference& operator=(const __bit_reference& __x) _NOEXCEPT
67d368a84cSHoward Hinnant        {return operator=(static_cast<bool>(__x));}
683e519524SHoward Hinnant
69d368a84cSHoward Hinnant    _LIBCPP_INLINE_VISIBILITY void flip() _NOEXCEPT {*__seg_ ^= __mask_;}
70c003db1fSHoward Hinnant    _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, false> operator&() const _NOEXCEPT
71c003db1fSHoward Hinnant        {return __bit_iterator<_Cp, false>(__seg_, static_cast<unsigned>(__ctz(__mask_)));}
723e519524SHoward Hinnantprivate:
733e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY
74d368a84cSHoward Hinnant    __bit_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT
75d368a84cSHoward Hinnant        : __seg_(__s), __mask_(__m) {}
763e519524SHoward Hinnant};
773e519524SHoward Hinnant
78c003db1fSHoward Hinnanttemplate <class _Cp>
79c003db1fSHoward Hinnantclass __bit_reference<_Cp, false>
80a7744562SHoward Hinnant{
81a7744562SHoward Hinnant};
82a7744562SHoward Hinnant
83d9db9f90SHoward Hinnanttemplate <class _Cp>
843af48ef7SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY
85d9db9f90SHoward Hinnantvoid
86d9db9f90SHoward Hinnantswap(__bit_reference<_Cp> __x, __bit_reference<_Cp> __y) _NOEXCEPT
87d9db9f90SHoward Hinnant{
88d9db9f90SHoward Hinnant    bool __t = __x;
89d9db9f90SHoward Hinnant    __x = __y;
90d9db9f90SHoward Hinnant    __y = __t;
91d9db9f90SHoward Hinnant}
92d9db9f90SHoward Hinnant
93c003db1fSHoward Hinnanttemplate <class _Cp, class _Dp>
943af48ef7SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY
953e519524SHoward Hinnantvoid
96c003db1fSHoward Hinnantswap(__bit_reference<_Cp> __x, __bit_reference<_Dp> __y) _NOEXCEPT
973e519524SHoward Hinnant{
983e519524SHoward Hinnant    bool __t = __x;
993e519524SHoward Hinnant    __x = __y;
1003e519524SHoward Hinnant    __y = __t;
1013e519524SHoward Hinnant}
1023e519524SHoward Hinnant
103c003db1fSHoward Hinnanttemplate <class _Cp>
1043af48ef7SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY
1053e519524SHoward Hinnantvoid
106c003db1fSHoward Hinnantswap(__bit_reference<_Cp> __x, bool& __y) _NOEXCEPT
1073e519524SHoward Hinnant{
1083e519524SHoward Hinnant    bool __t = __x;
1093e519524SHoward Hinnant    __x = __y;
1103e519524SHoward Hinnant    __y = __t;
1113e519524SHoward Hinnant}
1123e519524SHoward Hinnant
113c003db1fSHoward Hinnanttemplate <class _Cp>
1143af48ef7SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY
1153e519524SHoward Hinnantvoid
116c003db1fSHoward Hinnantswap(bool& __x, __bit_reference<_Cp> __y) _NOEXCEPT
1173e519524SHoward Hinnant{
1183e519524SHoward Hinnant    bool __t = __x;
1193e519524SHoward Hinnant    __x = __y;
1203e519524SHoward Hinnant    __y = __t;
1213e519524SHoward Hinnant}
1223e519524SHoward Hinnant
123c003db1fSHoward Hinnanttemplate <class _Cp>
1243e519524SHoward Hinnantclass __bit_const_reference
1253e519524SHoward Hinnant{
126c003db1fSHoward Hinnant    typedef typename _Cp::__storage_type          __storage_type;
127c003db1fSHoward Hinnant    typedef typename _Cp::__const_storage_pointer __storage_pointer;
1283e519524SHoward Hinnant
1293e519524SHoward Hinnant    __storage_pointer        __seg_;
1303e519524SHoward Hinnant    __storage_type __mask_;
1313e519524SHoward Hinnant
132c003db1fSHoward Hinnant    friend typename _Cp::__self;
133c003db1fSHoward Hinnant    friend class __bit_iterator<_Cp, true>;
1343e519524SHoward Hinnantpublic:
1353e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY
136c003db1fSHoward Hinnant    __bit_const_reference(const __bit_reference<_Cp>& __x) _NOEXCEPT
1373e519524SHoward Hinnant        : __seg_(__x.__seg_), __mask_(__x.__mask_) {}
1383e519524SHoward Hinnant
139eeac9fcfSHoward Hinnant    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR operator bool() const _NOEXCEPT
140d368a84cSHoward Hinnant        {return static_cast<bool>(*__seg_ & __mask_);}
1413e519524SHoward Hinnant
142c003db1fSHoward Hinnant    _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, true> operator&() const _NOEXCEPT
143c003db1fSHoward Hinnant        {return __bit_iterator<_Cp, true>(__seg_, static_cast<unsigned>(__ctz(__mask_)));}
1443e519524SHoward Hinnantprivate:
1453e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY
146eeac9fcfSHoward Hinnant    _LIBCPP_CONSTEXPR
147d368a84cSHoward Hinnant    __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT
148d368a84cSHoward Hinnant        : __seg_(__s), __mask_(__m) {}
1493e519524SHoward Hinnant
1503e519524SHoward Hinnant    __bit_const_reference& operator=(const __bit_const_reference& __x);
1513e519524SHoward Hinnant};
1523e519524SHoward Hinnant
1533e519524SHoward Hinnant// find
1543e519524SHoward Hinnant
155423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst>
156423a8d77SHoward Hinnant__bit_iterator<_Cp, _IsConst>
157423a8d77SHoward Hinnant__find_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
1583e519524SHoward Hinnant{
159423a8d77SHoward Hinnant    typedef __bit_iterator<_Cp, _IsConst> _It;
1603e519524SHoward Hinnant    typedef typename _It::__storage_type __storage_type;
161aec08784SEric Fiselier    static const int __bits_per_word = _It::__bits_per_word;
1623e519524SHoward Hinnant    // do first partial word
1633e519524SHoward Hinnant    if (__first.__ctz_ != 0)
1643e519524SHoward Hinnant    {
1653e519524SHoward Hinnant        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
166ce48a113SHoward Hinnant        __storage_type __dn = _VSTD::min(__clz_f, __n);
1673e519524SHoward Hinnant        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
1683e519524SHoward Hinnant        __storage_type __b = *__first.__seg_ & __m;
1693e519524SHoward Hinnant        if (__b)
170ce48a113SHoward Hinnant            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
171303e27d8SHoward Hinnant        if (__n == __dn)
1720fc6e981SMarshall Clow            return __first + __n;
1733e519524SHoward Hinnant        __n -= __dn;
1743e519524SHoward Hinnant        ++__first.__seg_;
1753e519524SHoward Hinnant    }
1763e519524SHoward Hinnant    // do middle whole words
1773e519524SHoward Hinnant    for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
1783e519524SHoward Hinnant        if (*__first.__seg_)
179ce48a113SHoward Hinnant            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(*__first.__seg_)));
1803e519524SHoward Hinnant    // do last partial word
1813e519524SHoward Hinnant    if (__n > 0)
1823e519524SHoward Hinnant    {
1833e519524SHoward Hinnant        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
1843e519524SHoward Hinnant        __storage_type __b = *__first.__seg_ & __m;
1853e519524SHoward Hinnant        if (__b)
186ce48a113SHoward Hinnant            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
1873e519524SHoward Hinnant    }
1883e519524SHoward Hinnant    return _It(__first.__seg_, static_cast<unsigned>(__n));
1893e519524SHoward Hinnant}
1903e519524SHoward Hinnant
191423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst>
192423a8d77SHoward Hinnant__bit_iterator<_Cp, _IsConst>
193423a8d77SHoward Hinnant__find_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
1943e519524SHoward Hinnant{
195423a8d77SHoward Hinnant    typedef __bit_iterator<_Cp, _IsConst> _It;
1963e519524SHoward Hinnant    typedef typename _It::__storage_type __storage_type;
197aec08784SEric Fiselier    const int __bits_per_word = _It::__bits_per_word;
1983e519524SHoward Hinnant    // do first partial word
1993e519524SHoward Hinnant    if (__first.__ctz_ != 0)
2003e519524SHoward Hinnant    {
2013e519524SHoward Hinnant        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
202ce48a113SHoward Hinnant        __storage_type __dn = _VSTD::min(__clz_f, __n);
2033e519524SHoward Hinnant        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
204423a8d77SHoward Hinnant        __storage_type __b = ~*__first.__seg_ & __m;
2053e519524SHoward Hinnant        if (__b)
206ce48a113SHoward Hinnant            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
207303e27d8SHoward Hinnant        if (__n == __dn)
2080fc6e981SMarshall Clow            return __first + __n;
2093e519524SHoward Hinnant        __n -= __dn;
2103e519524SHoward Hinnant        ++__first.__seg_;
2113e519524SHoward Hinnant    }
2123e519524SHoward Hinnant    // do middle whole words
2133e519524SHoward Hinnant    for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
2143e519524SHoward Hinnant    {
2153e519524SHoward Hinnant        __storage_type __b = ~*__first.__seg_;
2163e519524SHoward Hinnant        if (__b)
217ce48a113SHoward Hinnant            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
2183e519524SHoward Hinnant    }
2193e519524SHoward Hinnant    // do last partial word
2203e519524SHoward Hinnant    if (__n > 0)
2213e519524SHoward Hinnant    {
2223e519524SHoward Hinnant        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
223423a8d77SHoward Hinnant        __storage_type __b = ~*__first.__seg_ & __m;
2243e519524SHoward Hinnant        if (__b)
225ce48a113SHoward Hinnant            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
2263e519524SHoward Hinnant    }
2273e519524SHoward Hinnant    return _It(__first.__seg_, static_cast<unsigned>(__n));
2283e519524SHoward Hinnant}
2293e519524SHoward Hinnant
230423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst, class _Tp>
2313e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY
232423a8d77SHoward Hinnant__bit_iterator<_Cp, _IsConst>
233423a8d77SHoward Hinnantfind(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_)
2343e519524SHoward Hinnant{
235e4383379SHoward Hinnant    if (static_cast<bool>(__value_))
236c003db1fSHoward Hinnant        return __find_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first));
237c003db1fSHoward Hinnant    return __find_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first));
2383e519524SHoward Hinnant}
2393e519524SHoward Hinnant
2403e519524SHoward Hinnant// count
2413e519524SHoward Hinnant
242423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst>
243423a8d77SHoward Hinnanttypename __bit_iterator<_Cp, _IsConst>::difference_type
244423a8d77SHoward Hinnant__count_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
2453e519524SHoward Hinnant{
246423a8d77SHoward Hinnant    typedef __bit_iterator<_Cp, _IsConst> _It;
2473e519524SHoward Hinnant    typedef typename _It::__storage_type __storage_type;
2483e519524SHoward Hinnant    typedef typename _It::difference_type difference_type;
249aec08784SEric Fiselier    const int __bits_per_word = _It::__bits_per_word;
2503e519524SHoward Hinnant    difference_type __r = 0;
2513e519524SHoward Hinnant    // do first partial word
2523e519524SHoward Hinnant    if (__first.__ctz_ != 0)
2533e519524SHoward Hinnant    {
2543e519524SHoward Hinnant        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
255ce48a113SHoward Hinnant        __storage_type __dn = _VSTD::min(__clz_f, __n);
2563e519524SHoward Hinnant        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
257ce48a113SHoward Hinnant        __r = _VSTD::__pop_count(*__first.__seg_ & __m);
2583e519524SHoward Hinnant        __n -= __dn;
2593e519524SHoward Hinnant        ++__first.__seg_;
2603e519524SHoward Hinnant    }
2613e519524SHoward Hinnant    // do middle whole words
2623e519524SHoward Hinnant    for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
263ce48a113SHoward Hinnant        __r += _VSTD::__pop_count(*__first.__seg_);
2643e519524SHoward Hinnant    // do last partial word
2653e519524SHoward Hinnant    if (__n > 0)
2663e519524SHoward Hinnant    {
2673e519524SHoward Hinnant        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
268ce48a113SHoward Hinnant        __r += _VSTD::__pop_count(*__first.__seg_ & __m);
2693e519524SHoward Hinnant    }
2703e519524SHoward Hinnant    return __r;
2713e519524SHoward Hinnant}
2723e519524SHoward Hinnant
273423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst>
274423a8d77SHoward Hinnanttypename __bit_iterator<_Cp, _IsConst>::difference_type
275423a8d77SHoward Hinnant__count_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
2763e519524SHoward Hinnant{
277423a8d77SHoward Hinnant    typedef __bit_iterator<_Cp, _IsConst> _It;
2783e519524SHoward Hinnant    typedef typename _It::__storage_type __storage_type;
2793e519524SHoward Hinnant    typedef typename _It::difference_type difference_type;
280aec08784SEric Fiselier    const int __bits_per_word = _It::__bits_per_word;
2813e519524SHoward Hinnant    difference_type __r = 0;
2823e519524SHoward Hinnant    // do first partial word
2833e519524SHoward Hinnant    if (__first.__ctz_ != 0)
2843e519524SHoward Hinnant    {
2853e519524SHoward Hinnant        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
286ce48a113SHoward Hinnant        __storage_type __dn = _VSTD::min(__clz_f, __n);
2873e519524SHoward Hinnant        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
288423a8d77SHoward Hinnant        __r = _VSTD::__pop_count(~*__first.__seg_ & __m);
2893e519524SHoward Hinnant        __n -= __dn;
2903e519524SHoward Hinnant        ++__first.__seg_;
2913e519524SHoward Hinnant    }
2923e519524SHoward Hinnant    // do middle whole words
2933e519524SHoward Hinnant    for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
294ce48a113SHoward Hinnant        __r += _VSTD::__pop_count(~*__first.__seg_);
2953e519524SHoward Hinnant    // do last partial word
2963e519524SHoward Hinnant    if (__n > 0)
2973e519524SHoward Hinnant    {
2983e519524SHoward Hinnant        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
299423a8d77SHoward Hinnant        __r += _VSTD::__pop_count(~*__first.__seg_ & __m);
3003e519524SHoward Hinnant    }
3013e519524SHoward Hinnant    return __r;
3023e519524SHoward Hinnant}
3033e519524SHoward Hinnant
304423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst, class _Tp>
3053e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY
306423a8d77SHoward Hinnanttypename __bit_iterator<_Cp, _IsConst>::difference_type
307423a8d77SHoward Hinnantcount(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_)
3083e519524SHoward Hinnant{
309e4383379SHoward Hinnant    if (static_cast<bool>(__value_))
310c003db1fSHoward Hinnant        return __count_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first));
311c003db1fSHoward Hinnant    return __count_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first));
3123e519524SHoward Hinnant}
3133e519524SHoward Hinnant
3143e519524SHoward Hinnant// fill_n
3153e519524SHoward Hinnant
316c003db1fSHoward Hinnanttemplate <class _Cp>
3173e519524SHoward Hinnantvoid
318c003db1fSHoward Hinnant__fill_n_false(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n)
3193e519524SHoward Hinnant{
320c003db1fSHoward Hinnant    typedef __bit_iterator<_Cp, false> _It;
3213e519524SHoward Hinnant    typedef typename _It::__storage_type __storage_type;
322aec08784SEric Fiselier    const int __bits_per_word = _It::__bits_per_word;
3233e519524SHoward Hinnant    // do first partial word
3243e519524SHoward Hinnant    if (__first.__ctz_ != 0)
3253e519524SHoward Hinnant    {
3263e519524SHoward Hinnant        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
327ce48a113SHoward Hinnant        __storage_type __dn = _VSTD::min(__clz_f, __n);
3283e519524SHoward Hinnant        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
3293e519524SHoward Hinnant        *__first.__seg_ &= ~__m;
3303e519524SHoward Hinnant        __n -= __dn;
3313e519524SHoward Hinnant        ++__first.__seg_;
3323e519524SHoward Hinnant    }
3333e519524SHoward Hinnant    // do middle whole words
3343e519524SHoward Hinnant    __storage_type __nw = __n / __bits_per_word;
3353ec1f00bSHoward Hinnant    _VSTD::memset(_VSTD::__to_raw_pointer(__first.__seg_), 0, __nw * sizeof(__storage_type));
3363e519524SHoward Hinnant    __n -= __nw * __bits_per_word;
3373e519524SHoward Hinnant    // do last partial word
3383e519524SHoward Hinnant    if (__n > 0)
3393e519524SHoward Hinnant    {
3403e519524SHoward Hinnant        __first.__seg_ += __nw;
3413e519524SHoward Hinnant        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3423e519524SHoward Hinnant        *__first.__seg_ &= ~__m;
3433e519524SHoward Hinnant    }
3443e519524SHoward Hinnant}
3453e519524SHoward Hinnant
346c003db1fSHoward Hinnanttemplate <class _Cp>
3473e519524SHoward Hinnantvoid
348c003db1fSHoward Hinnant__fill_n_true(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n)
3493e519524SHoward Hinnant{
350c003db1fSHoward Hinnant    typedef __bit_iterator<_Cp, false> _It;
3513e519524SHoward Hinnant    typedef typename _It::__storage_type __storage_type;
352aec08784SEric Fiselier    const int __bits_per_word = _It::__bits_per_word;
3533e519524SHoward Hinnant    // do first partial word
3543e519524SHoward Hinnant    if (__first.__ctz_ != 0)
3553e519524SHoward Hinnant    {
3563e519524SHoward Hinnant        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
357ce48a113SHoward Hinnant        __storage_type __dn = _VSTD::min(__clz_f, __n);
3583e519524SHoward Hinnant        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
3593e519524SHoward Hinnant        *__first.__seg_ |= __m;
3603e519524SHoward Hinnant        __n -= __dn;
3613e519524SHoward Hinnant        ++__first.__seg_;
3623e519524SHoward Hinnant    }
3633e519524SHoward Hinnant    // do middle whole words
3643e519524SHoward Hinnant    __storage_type __nw = __n / __bits_per_word;
3653ec1f00bSHoward Hinnant    _VSTD::memset(_VSTD::__to_raw_pointer(__first.__seg_), -1, __nw * sizeof(__storage_type));
3663e519524SHoward Hinnant    __n -= __nw * __bits_per_word;
3673e519524SHoward Hinnant    // do last partial word
3683e519524SHoward Hinnant    if (__n > 0)
3693e519524SHoward Hinnant    {
3703e519524SHoward Hinnant        __first.__seg_ += __nw;
3713e519524SHoward Hinnant        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3723e519524SHoward Hinnant        *__first.__seg_ |= __m;
3733e519524SHoward Hinnant    }
3743e519524SHoward Hinnant}
3753e519524SHoward Hinnant
376c003db1fSHoward Hinnanttemplate <class _Cp>
3773af48ef7SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY
3783e519524SHoward Hinnantvoid
379c003db1fSHoward Hinnantfill_n(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n, bool __value_)
3803e519524SHoward Hinnant{
3813e519524SHoward Hinnant    if (__n > 0)
3823e519524SHoward Hinnant    {
383e4383379SHoward Hinnant        if (__value_)
3843e519524SHoward Hinnant            __fill_n_true(__first, __n);
3853e519524SHoward Hinnant        else
3863e519524SHoward Hinnant            __fill_n_false(__first, __n);
3873e519524SHoward Hinnant    }
3883e519524SHoward Hinnant}
3893e519524SHoward Hinnant
3903e519524SHoward Hinnant// fill
3913e519524SHoward Hinnant
392c003db1fSHoward Hinnanttemplate <class _Cp>
3933e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY
3943e519524SHoward Hinnantvoid
395c003db1fSHoward Hinnantfill(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __last, bool __value_)
3963e519524SHoward Hinnant{
397c003db1fSHoward Hinnant    _VSTD::fill_n(__first, static_cast<typename _Cp::size_type>(__last - __first), __value_);
3983e519524SHoward Hinnant}
3993e519524SHoward Hinnant
4003e519524SHoward Hinnant// copy
4013e519524SHoward Hinnant
402c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst>
403c003db1fSHoward Hinnant__bit_iterator<_Cp, false>
404c003db1fSHoward Hinnant__copy_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
405c003db1fSHoward Hinnant                                                     __bit_iterator<_Cp, false> __result)
4063e519524SHoward Hinnant{
407c003db1fSHoward Hinnant    typedef __bit_iterator<_Cp, _IsConst> _In;
4083e519524SHoward Hinnant    typedef  typename _In::difference_type difference_type;
4093e519524SHoward Hinnant    typedef typename _In::__storage_type __storage_type;
410aec08784SEric Fiselier    const int __bits_per_word = _In::__bits_per_word;
4113e519524SHoward Hinnant    difference_type __n = __last - __first;
4123e519524SHoward Hinnant    if (__n > 0)
4133e519524SHoward Hinnant    {
4143e519524SHoward Hinnant        // do first word
4153e519524SHoward Hinnant        if (__first.__ctz_ != 0)
4163e519524SHoward Hinnant        {
4173e519524SHoward Hinnant            unsigned __clz = __bits_per_word - __first.__ctz_;
418ce48a113SHoward Hinnant            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
4193e519524SHoward Hinnant            __n -= __dn;
4203e519524SHoward Hinnant            __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
4213e519524SHoward Hinnant            __storage_type __b = *__first.__seg_ & __m;
4223e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
4233e519524SHoward Hinnant            *__result.__seg_ |= __b;
4243e519524SHoward Hinnant            __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
4253e519524SHoward Hinnant            __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_)  % __bits_per_word);
4263e519524SHoward Hinnant            ++__first.__seg_;
4273e519524SHoward Hinnant            // __first.__ctz_ = 0;
4283e519524SHoward Hinnant        }
4293e519524SHoward Hinnant        // __first.__ctz_ == 0;
4303e519524SHoward Hinnant        // do middle words
4313e519524SHoward Hinnant        __storage_type __nw = __n / __bits_per_word;
4323ec1f00bSHoward Hinnant        _VSTD::memmove(_VSTD::__to_raw_pointer(__result.__seg_),
4333ec1f00bSHoward Hinnant                       _VSTD::__to_raw_pointer(__first.__seg_),
4343ec1f00bSHoward Hinnant                       __nw * sizeof(__storage_type));
4353e519524SHoward Hinnant        __n -= __nw * __bits_per_word;
4363e519524SHoward Hinnant        __result.__seg_ += __nw;
4373e519524SHoward Hinnant        // do last word
4383e519524SHoward Hinnant        if (__n > 0)
4393e519524SHoward Hinnant        {
4403e519524SHoward Hinnant            __first.__seg_ += __nw;
4413e519524SHoward Hinnant            __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
4423e519524SHoward Hinnant            __storage_type __b = *__first.__seg_ & __m;
4433e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
4443e519524SHoward Hinnant            *__result.__seg_ |= __b;
4453e519524SHoward Hinnant            __result.__ctz_ = static_cast<unsigned>(__n);
4463e519524SHoward Hinnant        }
4473e519524SHoward Hinnant    }
4483e519524SHoward Hinnant    return __result;
4493e519524SHoward Hinnant}
4503e519524SHoward Hinnant
451c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst>
452c003db1fSHoward Hinnant__bit_iterator<_Cp, false>
453c003db1fSHoward Hinnant__copy_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
454c003db1fSHoward Hinnant                                                       __bit_iterator<_Cp, false> __result)
4553e519524SHoward Hinnant{
456c003db1fSHoward Hinnant    typedef __bit_iterator<_Cp, _IsConst> _In;
4573e519524SHoward Hinnant    typedef  typename _In::difference_type difference_type;
4583e519524SHoward Hinnant    typedef typename _In::__storage_type __storage_type;
459aec08784SEric Fiselier    static const int __bits_per_word = _In::__bits_per_word;
4603e519524SHoward Hinnant    difference_type __n = __last - __first;
4613e519524SHoward Hinnant    if (__n > 0)
4623e519524SHoward Hinnant    {
4633e519524SHoward Hinnant        // do first word
4643e519524SHoward Hinnant        if (__first.__ctz_ != 0)
4653e519524SHoward Hinnant        {
4663e519524SHoward Hinnant            unsigned __clz_f = __bits_per_word - __first.__ctz_;
467ce48a113SHoward Hinnant            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
4683e519524SHoward Hinnant            __n -= __dn;
4693e519524SHoward Hinnant            __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
4703e519524SHoward Hinnant            __storage_type __b = *__first.__seg_ & __m;
4713e519524SHoward Hinnant            unsigned __clz_r = __bits_per_word - __result.__ctz_;
472ce48a113SHoward Hinnant            __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
4733e519524SHoward Hinnant            __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
4743e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
4753e519524SHoward Hinnant            if (__result.__ctz_ > __first.__ctz_)
4763e519524SHoward Hinnant                *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_);
4773e519524SHoward Hinnant            else
4783e519524SHoward Hinnant                *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_);
4793e519524SHoward Hinnant            __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;
4803e519524SHoward Hinnant            __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_)  % __bits_per_word);
4813e519524SHoward Hinnant            __dn -= __ddn;
4823e519524SHoward Hinnant            if (__dn > 0)
4833e519524SHoward Hinnant            {
4843e519524SHoward Hinnant                __m = ~__storage_type(0) >> (__bits_per_word - __dn);
4853e519524SHoward Hinnant                *__result.__seg_ &= ~__m;
4863e519524SHoward Hinnant                *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn);
4873e519524SHoward Hinnant                __result.__ctz_ = static_cast<unsigned>(__dn);
4883e519524SHoward Hinnant            }
4893e519524SHoward Hinnant            ++__first.__seg_;
4903e519524SHoward Hinnant            // __first.__ctz_ = 0;
4913e519524SHoward Hinnant        }
4923e519524SHoward Hinnant        // __first.__ctz_ == 0;
4933e519524SHoward Hinnant        // do middle words
4943e519524SHoward Hinnant        unsigned __clz_r = __bits_per_word - __result.__ctz_;
4953e519524SHoward Hinnant        __storage_type __m = ~__storage_type(0) << __result.__ctz_;
4963e519524SHoward Hinnant        for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_)
4973e519524SHoward Hinnant        {
4983e519524SHoward Hinnant            __storage_type __b = *__first.__seg_;
4993e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
5003e519524SHoward Hinnant            *__result.__seg_ |= __b << __result.__ctz_;
5013e519524SHoward Hinnant            ++__result.__seg_;
5023e519524SHoward Hinnant            *__result.__seg_ &= __m;
5033e519524SHoward Hinnant            *__result.__seg_ |= __b >> __clz_r;
5043e519524SHoward Hinnant        }
5053e519524SHoward Hinnant        // do last word
5063e519524SHoward Hinnant        if (__n > 0)
5073e519524SHoward Hinnant        {
5083e519524SHoward Hinnant            __m = ~__storage_type(0) >> (__bits_per_word - __n);
5093e519524SHoward Hinnant            __storage_type __b = *__first.__seg_ & __m;
510ce48a113SHoward Hinnant            __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r));
5113e519524SHoward Hinnant            __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
5123e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
5133e519524SHoward Hinnant            *__result.__seg_ |= __b << __result.__ctz_;
5143e519524SHoward Hinnant            __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
5153e519524SHoward Hinnant            __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_)  % __bits_per_word);
5163e519524SHoward Hinnant            __n -= __dn;
5173e519524SHoward Hinnant            if (__n > 0)
5183e519524SHoward Hinnant            {
5193e519524SHoward Hinnant                __m = ~__storage_type(0) >> (__bits_per_word - __n);
5203e519524SHoward Hinnant                *__result.__seg_ &= ~__m;
5213e519524SHoward Hinnant                *__result.__seg_ |= __b >> __dn;
5223e519524SHoward Hinnant                __result.__ctz_ = static_cast<unsigned>(__n);
5233e519524SHoward Hinnant            }
5243e519524SHoward Hinnant        }
5253e519524SHoward Hinnant    }
5263e519524SHoward Hinnant    return __result;
5273e519524SHoward Hinnant}
5283e519524SHoward Hinnant
529c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst>
5303e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY
531c003db1fSHoward Hinnant__bit_iterator<_Cp, false>
532c003db1fSHoward Hinnantcopy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
5333e519524SHoward Hinnant{
5343e519524SHoward Hinnant    if (__first.__ctz_ == __result.__ctz_)
5353e519524SHoward Hinnant        return __copy_aligned(__first, __last, __result);
5363e519524SHoward Hinnant    return __copy_unaligned(__first, __last, __result);
5373e519524SHoward Hinnant}
5383e519524SHoward Hinnant
5393e519524SHoward Hinnant// copy_backward
5403e519524SHoward Hinnant
541c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst>
542c003db1fSHoward Hinnant__bit_iterator<_Cp, false>
543c003db1fSHoward Hinnant__copy_backward_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
544c003db1fSHoward Hinnant                                                     __bit_iterator<_Cp, false> __result)
5453e519524SHoward Hinnant{
546c003db1fSHoward Hinnant    typedef __bit_iterator<_Cp, _IsConst> _In;
5473e519524SHoward Hinnant    typedef  typename _In::difference_type difference_type;
5483e519524SHoward Hinnant    typedef typename _In::__storage_type __storage_type;
549aec08784SEric Fiselier    const int __bits_per_word = _In::__bits_per_word;
5503e519524SHoward Hinnant    difference_type __n = __last - __first;
5513e519524SHoward Hinnant    if (__n > 0)
5523e519524SHoward Hinnant    {
5533e519524SHoward Hinnant        // do first word
5543e519524SHoward Hinnant        if (__last.__ctz_ != 0)
5553e519524SHoward Hinnant        {
556ce48a113SHoward Hinnant            difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n);
5573e519524SHoward Hinnant            __n -= __dn;
5583e519524SHoward Hinnant            unsigned __clz = __bits_per_word - __last.__ctz_;
5593e519524SHoward Hinnant            __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz);
5603e519524SHoward Hinnant            __storage_type __b = *__last.__seg_ & __m;
5613e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
5623e519524SHoward Hinnant            *__result.__seg_ |= __b;
5633e519524SHoward Hinnant            __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) +
5643e519524SHoward Hinnant                                                       __result.__ctz_)  % __bits_per_word);
5653e519524SHoward Hinnant            // __last.__ctz_ = 0
5663e519524SHoward Hinnant         }
5673e519524SHoward Hinnant        // __last.__ctz_ == 0 || __n == 0
5683e519524SHoward Hinnant        // __result.__ctz_ == 0 || __n == 0
5693e519524SHoward Hinnant        // do middle words
5703e519524SHoward Hinnant        __storage_type __nw = __n / __bits_per_word;
5713e519524SHoward Hinnant        __result.__seg_ -= __nw;
5723e519524SHoward Hinnant        __last.__seg_ -= __nw;
5733ec1f00bSHoward Hinnant        _VSTD::memmove(_VSTD::__to_raw_pointer(__result.__seg_),
5743ec1f00bSHoward Hinnant                       _VSTD::__to_raw_pointer(__last.__seg_),
5753ec1f00bSHoward Hinnant                       __nw * sizeof(__storage_type));
5763e519524SHoward Hinnant        __n -= __nw * __bits_per_word;
5773e519524SHoward Hinnant        // do last word
5783e519524SHoward Hinnant        if (__n > 0)
5793e519524SHoward Hinnant        {
5803e519524SHoward Hinnant            __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n);
5813e519524SHoward Hinnant            __storage_type __b = *--__last.__seg_ & __m;
5823e519524SHoward Hinnant            *--__result.__seg_ &= ~__m;
5833e519524SHoward Hinnant            *__result.__seg_ |= __b;
5843e519524SHoward Hinnant            __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));
5853e519524SHoward Hinnant        }
5863e519524SHoward Hinnant    }
5873e519524SHoward Hinnant    return __result;
5883e519524SHoward Hinnant}
5893e519524SHoward Hinnant
590c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst>
591c003db1fSHoward Hinnant__bit_iterator<_Cp, false>
592c003db1fSHoward Hinnant__copy_backward_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
593c003db1fSHoward Hinnant                                                       __bit_iterator<_Cp, false> __result)
5943e519524SHoward Hinnant{
595c003db1fSHoward Hinnant    typedef __bit_iterator<_Cp, _IsConst> _In;
5963e519524SHoward Hinnant    typedef  typename _In::difference_type difference_type;
5973e519524SHoward Hinnant    typedef typename _In::__storage_type __storage_type;
598aec08784SEric Fiselier    const int __bits_per_word = _In::__bits_per_word;
5993e519524SHoward Hinnant    difference_type __n = __last - __first;
6003e519524SHoward Hinnant    if (__n > 0)
6013e519524SHoward Hinnant    {
6023e519524SHoward Hinnant        // do first word
6033e519524SHoward Hinnant        if (__last.__ctz_ != 0)
6043e519524SHoward Hinnant        {
605ce48a113SHoward Hinnant            difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n);
6063e519524SHoward Hinnant            __n -= __dn;
6073e519524SHoward Hinnant            unsigned __clz_l = __bits_per_word - __last.__ctz_;
6083e519524SHoward Hinnant            __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l);
6093e519524SHoward Hinnant            __storage_type __b = *__last.__seg_ & __m;
6103e519524SHoward Hinnant            unsigned __clz_r = __bits_per_word - __result.__ctz_;
611ce48a113SHoward Hinnant            __storage_type __ddn = _VSTD::min(__dn, static_cast<difference_type>(__result.__ctz_));
6123e519524SHoward Hinnant            if (__ddn > 0)
6133e519524SHoward Hinnant            {
6143e519524SHoward Hinnant                __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r);
6153e519524SHoward Hinnant                *__result.__seg_ &= ~__m;
6163e519524SHoward Hinnant                if (__result.__ctz_ > __last.__ctz_)
6173e519524SHoward Hinnant                    *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);
6183e519524SHoward Hinnant                else
6193e519524SHoward Hinnant                    *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_);
6203e519524SHoward Hinnant                __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) +
6213e519524SHoward Hinnant                                                         __result.__ctz_)  % __bits_per_word);
6223e519524SHoward Hinnant                __dn -= __ddn;
6233e519524SHoward Hinnant            }
6243e519524SHoward Hinnant            if (__dn > 0)
6253e519524SHoward Hinnant            {
6263e519524SHoward Hinnant                // __result.__ctz_ == 0
6273e519524SHoward Hinnant                --__result.__seg_;
6283e519524SHoward Hinnant                __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1));
6293e519524SHoward Hinnant                __m = ~__storage_type(0) << __result.__ctz_;
6303e519524SHoward Hinnant                *__result.__seg_ &= ~__m;
6313e519524SHoward Hinnant                __last.__ctz_ -= __dn + __ddn;
6323e519524SHoward Hinnant                *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);
6333e519524SHoward Hinnant            }
6343e519524SHoward Hinnant            // __last.__ctz_ = 0
6353e519524SHoward Hinnant         }
6363e519524SHoward Hinnant        // __last.__ctz_ == 0 || __n == 0
6373e519524SHoward Hinnant        // __result.__ctz_ != 0 || __n == 0
6383e519524SHoward Hinnant        // do middle words
6393e519524SHoward Hinnant        unsigned __clz_r = __bits_per_word - __result.__ctz_;
6403e519524SHoward Hinnant        __storage_type __m = ~__storage_type(0) >> __clz_r;
6413e519524SHoward Hinnant        for (; __n >= __bits_per_word; __n -= __bits_per_word)
6423e519524SHoward Hinnant        {
6433e519524SHoward Hinnant            __storage_type __b = *--__last.__seg_;
6443e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
6453e519524SHoward Hinnant            *__result.__seg_ |= __b >> __clz_r;
6463e519524SHoward Hinnant            *--__result.__seg_ &= __m;
6473e519524SHoward Hinnant            *__result.__seg_ |= __b << __result.__ctz_;
6483e519524SHoward Hinnant        }
6493e519524SHoward Hinnant        // do last word
6503e519524SHoward Hinnant        if (__n > 0)
6513e519524SHoward Hinnant        {
6523e519524SHoward Hinnant            __m = ~__storage_type(0) << (__bits_per_word - __n);
6533e519524SHoward Hinnant            __storage_type __b = *--__last.__seg_ & __m;
654c206366fSHoward Hinnant            __clz_r = __bits_per_word - __result.__ctz_;
655ce48a113SHoward Hinnant            __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__result.__ctz_));
6563e519524SHoward Hinnant            __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r);
6573e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
6583e519524SHoward Hinnant            *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_);
6593e519524SHoward Hinnant            __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) +
6603e519524SHoward Hinnant                                                     __result.__ctz_)  % __bits_per_word);
6613e519524SHoward Hinnant            __n -= __dn;
6623e519524SHoward Hinnant            if (__n > 0)
6633e519524SHoward Hinnant            {
6643e519524SHoward Hinnant                // __result.__ctz_ == 0
6653e519524SHoward Hinnant                --__result.__seg_;
6663e519524SHoward Hinnant                __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));
6673e519524SHoward Hinnant                __m = ~__storage_type(0) << __result.__ctz_;
6683e519524SHoward Hinnant                *__result.__seg_ &= ~__m;
6693e519524SHoward Hinnant                *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn));
6703e519524SHoward Hinnant            }
6713e519524SHoward Hinnant        }
6723e519524SHoward Hinnant    }
6733e519524SHoward Hinnant    return __result;
6743e519524SHoward Hinnant}
6753e519524SHoward Hinnant
676c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst>
6773e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY
678c003db1fSHoward Hinnant__bit_iterator<_Cp, false>
679c003db1fSHoward Hinnantcopy_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
6803e519524SHoward Hinnant{
6813e519524SHoward Hinnant    if (__last.__ctz_ == __result.__ctz_)
6823e519524SHoward Hinnant        return __copy_backward_aligned(__first, __last, __result);
6833e519524SHoward Hinnant    return __copy_backward_unaligned(__first, __last, __result);
6843e519524SHoward Hinnant}
6853e519524SHoward Hinnant
6863e519524SHoward Hinnant// move
6873e519524SHoward Hinnant
688c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst>
6893e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY
690c003db1fSHoward Hinnant__bit_iterator<_Cp, false>
691c003db1fSHoward Hinnantmove(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
6923e519524SHoward Hinnant{
693ce48a113SHoward Hinnant    return _VSTD::copy(__first, __last, __result);
6943e519524SHoward Hinnant}
6953e519524SHoward Hinnant
6963e519524SHoward Hinnant// move_backward
6973e519524SHoward Hinnant
698c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst>
6993e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY
700c003db1fSHoward Hinnant__bit_iterator<_Cp, false>
701c003db1fSHoward Hinnantmove_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
7023e519524SHoward Hinnant{
70308de4b0dSMarshall Clow    return _VSTD::copy_backward(__first, __last, __result);
7043e519524SHoward Hinnant}
7053e519524SHoward Hinnant
7063e519524SHoward Hinnant// swap_ranges
7073e519524SHoward Hinnant
708dbe81119SHoward Hinnanttemplate <class __C1, class __C2>
709dbe81119SHoward Hinnant__bit_iterator<__C2, false>
710dbe81119SHoward Hinnant__swap_ranges_aligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last,
711dbe81119SHoward Hinnant                      __bit_iterator<__C2, false> __result)
7123e519524SHoward Hinnant{
713dbe81119SHoward Hinnant    typedef __bit_iterator<__C1, false> _I1;
7143e519524SHoward Hinnant    typedef  typename _I1::difference_type difference_type;
7153e519524SHoward Hinnant    typedef typename _I1::__storage_type __storage_type;
716aec08784SEric Fiselier    const int __bits_per_word = _I1::__bits_per_word;
7173e519524SHoward Hinnant    difference_type __n = __last - __first;
7183e519524SHoward Hinnant    if (__n > 0)
7193e519524SHoward Hinnant    {
7203e519524SHoward Hinnant        // do first word
7213e519524SHoward Hinnant        if (__first.__ctz_ != 0)
7223e519524SHoward Hinnant        {
7233e519524SHoward Hinnant            unsigned __clz = __bits_per_word - __first.__ctz_;
724ce48a113SHoward Hinnant            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
7253e519524SHoward Hinnant            __n -= __dn;
7263e519524SHoward Hinnant            __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
7273e519524SHoward Hinnant            __storage_type __b1 = *__first.__seg_ & __m;
7283e519524SHoward Hinnant            *__first.__seg_ &= ~__m;
7293e519524SHoward Hinnant            __storage_type __b2 = *__result.__seg_ & __m;
7303e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
7313e519524SHoward Hinnant            *__result.__seg_ |= __b1;
7323e519524SHoward Hinnant            *__first.__seg_  |= __b2;
7333e519524SHoward Hinnant            __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
7343e519524SHoward Hinnant            __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_)  % __bits_per_word);
7353e519524SHoward Hinnant            ++__first.__seg_;
7363e519524SHoward Hinnant            // __first.__ctz_ = 0;
7373e519524SHoward Hinnant        }
7383e519524SHoward Hinnant        // __first.__ctz_ == 0;
7393e519524SHoward Hinnant        // do middle words
7403e519524SHoward Hinnant        for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_)
7413e519524SHoward Hinnant            swap(*__first.__seg_, *__result.__seg_);
7423e519524SHoward Hinnant        // do last word
7433e519524SHoward Hinnant        if (__n > 0)
7443e519524SHoward Hinnant        {
7453e519524SHoward Hinnant            __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
7463e519524SHoward Hinnant            __storage_type __b1 = *__first.__seg_ & __m;
7473e519524SHoward Hinnant            *__first.__seg_ &= ~__m;
7483e519524SHoward Hinnant            __storage_type __b2 = *__result.__seg_ & __m;
7493e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
7503e519524SHoward Hinnant            *__result.__seg_ |= __b1;
7513e519524SHoward Hinnant            *__first.__seg_  |= __b2;
7523e519524SHoward Hinnant            __result.__ctz_ = static_cast<unsigned>(__n);
7533e519524SHoward Hinnant        }
7543e519524SHoward Hinnant    }
7553e519524SHoward Hinnant    return __result;
7563e519524SHoward Hinnant}
7573e519524SHoward Hinnant
758dbe81119SHoward Hinnanttemplate <class __C1, class __C2>
759dbe81119SHoward Hinnant__bit_iterator<__C2, false>
760dbe81119SHoward Hinnant__swap_ranges_unaligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last,
761dbe81119SHoward Hinnant                        __bit_iterator<__C2, false> __result)
7623e519524SHoward Hinnant{
763dbe81119SHoward Hinnant    typedef __bit_iterator<__C1, false> _I1;
7643e519524SHoward Hinnant    typedef  typename _I1::difference_type difference_type;
7653e519524SHoward Hinnant    typedef typename _I1::__storage_type __storage_type;
766aec08784SEric Fiselier    const int __bits_per_word = _I1::__bits_per_word;
7673e519524SHoward Hinnant    difference_type __n = __last - __first;
7683e519524SHoward Hinnant    if (__n > 0)
7693e519524SHoward Hinnant    {
7703e519524SHoward Hinnant        // do first word
7713e519524SHoward Hinnant        if (__first.__ctz_ != 0)
7723e519524SHoward Hinnant        {
7733e519524SHoward Hinnant            unsigned __clz_f = __bits_per_word - __first.__ctz_;
774ce48a113SHoward Hinnant            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
7753e519524SHoward Hinnant            __n -= __dn;
7763e519524SHoward Hinnant            __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
7773e519524SHoward Hinnant            __storage_type __b1 = *__first.__seg_ & __m;
7783e519524SHoward Hinnant            *__first.__seg_ &= ~__m;
7793e519524SHoward Hinnant            unsigned __clz_r = __bits_per_word - __result.__ctz_;
780ce48a113SHoward Hinnant            __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
7813e519524SHoward Hinnant            __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
7823e519524SHoward Hinnant            __storage_type __b2 = *__result.__seg_ & __m;
7833e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
7843e519524SHoward Hinnant            if (__result.__ctz_ > __first.__ctz_)
7853e519524SHoward Hinnant            {
7863e519524SHoward Hinnant                unsigned __s = __result.__ctz_ - __first.__ctz_;
7873e519524SHoward Hinnant                *__result.__seg_ |= __b1 << __s;
7883e519524SHoward Hinnant                *__first.__seg_  |= __b2 >> __s;
7893e519524SHoward Hinnant            }
7903e519524SHoward Hinnant            else
7913e519524SHoward Hinnant            {
7923e519524SHoward Hinnant                unsigned __s = __first.__ctz_ - __result.__ctz_;
7933e519524SHoward Hinnant                *__result.__seg_ |= __b1 >> __s;
7943e519524SHoward Hinnant                *__first.__seg_  |= __b2 << __s;
7953e519524SHoward Hinnant            }
7963e519524SHoward Hinnant            __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;
7973e519524SHoward Hinnant            __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_)  % __bits_per_word);
7983e519524SHoward Hinnant            __dn -= __ddn;
7993e519524SHoward Hinnant            if (__dn > 0)
8003e519524SHoward Hinnant            {
8013e519524SHoward Hinnant                __m = ~__storage_type(0) >> (__bits_per_word - __dn);
8023e519524SHoward Hinnant                __b2 = *__result.__seg_ & __m;
8033e519524SHoward Hinnant                *__result.__seg_ &= ~__m;
8043e519524SHoward Hinnant                unsigned __s = __first.__ctz_ + __ddn;
8053e519524SHoward Hinnant                *__result.__seg_ |= __b1 >> __s;
8063e519524SHoward Hinnant                *__first.__seg_  |= __b2 << __s;
8073e519524SHoward Hinnant                __result.__ctz_ = static_cast<unsigned>(__dn);
8083e519524SHoward Hinnant            }
8093e519524SHoward Hinnant            ++__first.__seg_;
8103e519524SHoward Hinnant            // __first.__ctz_ = 0;
8113e519524SHoward Hinnant        }
8123e519524SHoward Hinnant        // __first.__ctz_ == 0;
8133e519524SHoward Hinnant        // do middle words
8143e519524SHoward Hinnant        __storage_type __m = ~__storage_type(0) << __result.__ctz_;
8153e519524SHoward Hinnant        unsigned __clz_r = __bits_per_word - __result.__ctz_;
8163e519524SHoward Hinnant        for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_)
8173e519524SHoward Hinnant        {
8183e519524SHoward Hinnant            __storage_type __b1 = *__first.__seg_;
8193e519524SHoward Hinnant            __storage_type __b2 = *__result.__seg_ & __m;
8203e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
8213e519524SHoward Hinnant            *__result.__seg_ |= __b1 << __result.__ctz_;
8223e519524SHoward Hinnant            *__first.__seg_  = __b2 >> __result.__ctz_;
8233e519524SHoward Hinnant            ++__result.__seg_;
8243e519524SHoward Hinnant            __b2 = *__result.__seg_ & ~__m;
8253e519524SHoward Hinnant            *__result.__seg_ &= __m;
8263e519524SHoward Hinnant            *__result.__seg_ |= __b1 >> __clz_r;
8273e519524SHoward Hinnant            *__first.__seg_  |= __b2 << __clz_r;
8283e519524SHoward Hinnant        }
8293e519524SHoward Hinnant        // do last word
8303e519524SHoward Hinnant        if (__n > 0)
8313e519524SHoward Hinnant        {
8323e519524SHoward Hinnant            __m = ~__storage_type(0) >> (__bits_per_word - __n);
8333e519524SHoward Hinnant            __storage_type __b1 = *__first.__seg_ & __m;
8343e519524SHoward Hinnant            *__first.__seg_ &= ~__m;
835ce48a113SHoward Hinnant            __storage_type __dn = _VSTD::min<__storage_type>(__n, __clz_r);
8363e519524SHoward Hinnant            __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
8373e519524SHoward Hinnant            __storage_type __b2 = *__result.__seg_ & __m;
8383e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
8393e519524SHoward Hinnant            *__result.__seg_ |= __b1 << __result.__ctz_;
8403e519524SHoward Hinnant            *__first.__seg_  |= __b2 >> __result.__ctz_;
8413e519524SHoward Hinnant            __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
8423e519524SHoward Hinnant            __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_)  % __bits_per_word);
8433e519524SHoward Hinnant            __n -= __dn;
8443e519524SHoward Hinnant            if (__n > 0)
8453e519524SHoward Hinnant            {
8463e519524SHoward Hinnant                __m = ~__storage_type(0) >> (__bits_per_word - __n);
8473e519524SHoward Hinnant                __b2 = *__result.__seg_ & __m;
8483e519524SHoward Hinnant                *__result.__seg_ &= ~__m;
8493e519524SHoward Hinnant                *__result.__seg_ |= __b1 >> __dn;
8503e519524SHoward Hinnant                *__first.__seg_  |= __b2 << __dn;
8513e519524SHoward Hinnant                __result.__ctz_ = static_cast<unsigned>(__n);
8523e519524SHoward Hinnant            }
8533e519524SHoward Hinnant        }
8543e519524SHoward Hinnant    }
8553e519524SHoward Hinnant    return __result;
8563e519524SHoward Hinnant}
8573e519524SHoward Hinnant
858dbe81119SHoward Hinnanttemplate <class __C1, class __C2>
8593e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY
860dbe81119SHoward Hinnant__bit_iterator<__C2, false>
861dbe81119SHoward Hinnantswap_ranges(__bit_iterator<__C1, false> __first1, __bit_iterator<__C1, false> __last1,
862dbe81119SHoward Hinnant            __bit_iterator<__C2, false> __first2)
8633e519524SHoward Hinnant{
8643e519524SHoward Hinnant    if (__first1.__ctz_ == __first2.__ctz_)
8653e519524SHoward Hinnant        return __swap_ranges_aligned(__first1, __last1, __first2);
8663e519524SHoward Hinnant    return __swap_ranges_unaligned(__first1, __last1, __first2);
8673e519524SHoward Hinnant}
8683e519524SHoward Hinnant
8693e519524SHoward Hinnant// rotate
8703e519524SHoward Hinnant
871c003db1fSHoward Hinnanttemplate <class _Cp>
8723e519524SHoward Hinnantstruct __bit_array
8733e519524SHoward Hinnant{
874c003db1fSHoward Hinnant    typedef typename _Cp::difference_type difference_type;
875c003db1fSHoward Hinnant    typedef typename _Cp::__storage_type  __storage_type;
8763ec1f00bSHoward Hinnant    typedef typename _Cp::__storage_pointer __storage_pointer;
877c003db1fSHoward Hinnant    typedef typename _Cp::iterator        iterator;
878c003db1fSHoward Hinnant    static const unsigned __bits_per_word = _Cp::__bits_per_word;
879c003db1fSHoward Hinnant    static const unsigned _Np = 4;
8803e519524SHoward Hinnant
8813e519524SHoward Hinnant    difference_type __size_;
882c003db1fSHoward Hinnant    __storage_type __word_[_Np];
8833e519524SHoward Hinnant
8843e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY static difference_type capacity()
885c003db1fSHoward Hinnant        {return static_cast<difference_type>(_Np * __bits_per_word);}
8863e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY explicit __bit_array(difference_type __s) : __size_(__s) {}
8873ec1f00bSHoward Hinnant    _LIBCPP_INLINE_VISIBILITY iterator begin()
8883ec1f00bSHoward Hinnant    {
8893ec1f00bSHoward Hinnant        return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]), 0);
8903ec1f00bSHoward Hinnant    }
8913ec1f00bSHoward Hinnant    _LIBCPP_INLINE_VISIBILITY iterator end()
8923ec1f00bSHoward Hinnant    {
8933ec1f00bSHoward Hinnant        return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]) + __size_ / __bits_per_word,
8943ec1f00bSHoward Hinnant                                                  static_cast<unsigned>(__size_ % __bits_per_word));
8953ec1f00bSHoward Hinnant    }
8963e519524SHoward Hinnant};
8973e519524SHoward Hinnant
898c003db1fSHoward Hinnanttemplate <class _Cp>
899c003db1fSHoward Hinnant__bit_iterator<_Cp, false>
900c003db1fSHoward Hinnantrotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last)
9013e519524SHoward Hinnant{
902c003db1fSHoward Hinnant    typedef __bit_iterator<_Cp, false> _I1;
9033e519524SHoward Hinnant    typedef  typename _I1::difference_type difference_type;
9043e519524SHoward Hinnant    difference_type __d1 = __middle - __first;
9053e519524SHoward Hinnant    difference_type __d2 = __last - __middle;
9063e519524SHoward Hinnant    _I1 __r = __first + __d2;
9073e519524SHoward Hinnant    while (__d1 != 0 && __d2 != 0)
9083e519524SHoward Hinnant    {
9093e519524SHoward Hinnant        if (__d1 <= __d2)
9103e519524SHoward Hinnant        {
911c003db1fSHoward Hinnant            if (__d1 <= __bit_array<_Cp>::capacity())
9123e519524SHoward Hinnant            {
913c003db1fSHoward Hinnant                __bit_array<_Cp> __b(__d1);
914ce48a113SHoward Hinnant                _VSTD::copy(__first, __middle, __b.begin());
915ce48a113SHoward Hinnant                _VSTD::copy(__b.begin(), __b.end(), _VSTD::copy(__middle, __last, __first));
9163e519524SHoward Hinnant                break;
9173e519524SHoward Hinnant            }
9183e519524SHoward Hinnant            else
9193e519524SHoward Hinnant            {
920c003db1fSHoward Hinnant                __bit_iterator<_Cp, false> __mp = _VSTD::swap_ranges(__first, __middle, __middle);
9213e519524SHoward Hinnant                __first = __middle;
9223e519524SHoward Hinnant                __middle = __mp;
9233e519524SHoward Hinnant                __d2 -= __d1;
9243e519524SHoward Hinnant            }
9253e519524SHoward Hinnant        }
9263e519524SHoward Hinnant        else
9273e519524SHoward Hinnant        {
928c003db1fSHoward Hinnant            if (__d2 <= __bit_array<_Cp>::capacity())
9293e519524SHoward Hinnant            {
930c003db1fSHoward Hinnant                __bit_array<_Cp> __b(__d2);
931ce48a113SHoward Hinnant                _VSTD::copy(__middle, __last, __b.begin());
932ce48a113SHoward Hinnant                _VSTD::copy_backward(__b.begin(), __b.end(), _VSTD::copy_backward(__first, __middle, __last));
9333e519524SHoward Hinnant                break;
9343e519524SHoward Hinnant            }
9353e519524SHoward Hinnant            else
9363e519524SHoward Hinnant            {
937c003db1fSHoward Hinnant                __bit_iterator<_Cp, false> __mp = __first + __d2;
938ce48a113SHoward Hinnant                _VSTD::swap_ranges(__first, __mp, __middle);
9393e519524SHoward Hinnant                __first = __mp;
9403e519524SHoward Hinnant                __d1 -= __d2;
9413e519524SHoward Hinnant            }
9423e519524SHoward Hinnant        }
9433e519524SHoward Hinnant    }
9443e519524SHoward Hinnant    return __r;
9453e519524SHoward Hinnant}
9463e519524SHoward Hinnant
9473e519524SHoward Hinnant// equal
9483e519524SHoward Hinnant
9491237dccaSHoward Hinnanttemplate <class _Cp, bool _IC1, bool _IC2>
9503e519524SHoward Hinnantbool
9511237dccaSHoward Hinnant__equal_unaligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1,
9521237dccaSHoward Hinnant                  __bit_iterator<_Cp, _IC2> __first2)
9533e519524SHoward Hinnant{
9541237dccaSHoward Hinnant    typedef __bit_iterator<_Cp, _IC1> _It;
9553e519524SHoward Hinnant    typedef  typename _It::difference_type difference_type;
9563e519524SHoward Hinnant    typedef typename _It::__storage_type __storage_type;
957aec08784SEric Fiselier    static const int __bits_per_word = _It::__bits_per_word;
9583e519524SHoward Hinnant    difference_type __n = __last1 - __first1;
9593e519524SHoward Hinnant    if (__n > 0)
9603e519524SHoward Hinnant    {
9613e519524SHoward Hinnant        // do first word
9623e519524SHoward Hinnant        if (__first1.__ctz_ != 0)
9633e519524SHoward Hinnant        {
9643e519524SHoward Hinnant            unsigned __clz_f = __bits_per_word - __first1.__ctz_;
965ce48a113SHoward Hinnant            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
9663e519524SHoward Hinnant            __n -= __dn;
9673e519524SHoward Hinnant            __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
9683e519524SHoward Hinnant            __storage_type __b = *__first1.__seg_ & __m;
9693e519524SHoward Hinnant            unsigned __clz_r = __bits_per_word - __first2.__ctz_;
970ce48a113SHoward Hinnant            __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
9713e519524SHoward Hinnant            __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
9723e519524SHoward Hinnant            if (__first2.__ctz_ > __first1.__ctz_)
9734c0de496SHoward Hinnant            {
9743e519524SHoward Hinnant                if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_)))
9753e519524SHoward Hinnant                    return false;
9764c0de496SHoward Hinnant            }
9773e519524SHoward Hinnant            else
9784c0de496SHoward Hinnant            {
9793e519524SHoward Hinnant                if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_)))
9803e519524SHoward Hinnant                    return false;
9814c0de496SHoward Hinnant            }
9823e519524SHoward Hinnant            __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word;
9833e519524SHoward Hinnant            __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_)  % __bits_per_word);
9843e519524SHoward Hinnant            __dn -= __ddn;
9853e519524SHoward Hinnant            if (__dn > 0)
9863e519524SHoward Hinnant            {
9873e519524SHoward Hinnant                __m = ~__storage_type(0) >> (__bits_per_word - __dn);
9883e519524SHoward Hinnant                if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn)))
9893e519524SHoward Hinnant                    return false;
9903e519524SHoward Hinnant                __first2.__ctz_ = static_cast<unsigned>(__dn);
9913e519524SHoward Hinnant            }
9923e519524SHoward Hinnant            ++__first1.__seg_;
9933e519524SHoward Hinnant            // __first1.__ctz_ = 0;
9943e519524SHoward Hinnant        }
9953e519524SHoward Hinnant        // __first1.__ctz_ == 0;
9963e519524SHoward Hinnant        // do middle words
9973e519524SHoward Hinnant        unsigned __clz_r = __bits_per_word - __first2.__ctz_;
9983e519524SHoward Hinnant        __storage_type __m = ~__storage_type(0) << __first2.__ctz_;
9993e519524SHoward Hinnant        for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_)
10003e519524SHoward Hinnant        {
10013e519524SHoward Hinnant            __storage_type __b = *__first1.__seg_;
10023e519524SHoward Hinnant            if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_))
10033e519524SHoward Hinnant                return false;
10043e519524SHoward Hinnant            ++__first2.__seg_;
10053e519524SHoward Hinnant            if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r))
10063e519524SHoward Hinnant                return false;
10073e519524SHoward Hinnant        }
10083e519524SHoward Hinnant        // do last word
10093e519524SHoward Hinnant        if (__n > 0)
10103e519524SHoward Hinnant        {
10113e519524SHoward Hinnant            __m = ~__storage_type(0) >> (__bits_per_word - __n);
10123e519524SHoward Hinnant            __storage_type __b = *__first1.__seg_ & __m;
1013ce48a113SHoward Hinnant            __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r));
10143e519524SHoward Hinnant            __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
10153e519524SHoward Hinnant            if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_))
10163e519524SHoward Hinnant                return false;
10173e519524SHoward Hinnant            __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word;
10183e519524SHoward Hinnant            __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_)  % __bits_per_word);
10193e519524SHoward Hinnant            __n -= __dn;
10203e519524SHoward Hinnant            if (__n > 0)
10213e519524SHoward Hinnant            {
10223e519524SHoward Hinnant                __m = ~__storage_type(0) >> (__bits_per_word - __n);
10233e519524SHoward Hinnant                if ((*__first2.__seg_ & __m) != (__b >> __dn))
10243e519524SHoward Hinnant                    return false;
10253e519524SHoward Hinnant            }
10263e519524SHoward Hinnant        }
10273e519524SHoward Hinnant    }
10283e519524SHoward Hinnant    return true;
10293e519524SHoward Hinnant}
10303e519524SHoward Hinnant
10311237dccaSHoward Hinnanttemplate <class _Cp, bool _IC1, bool _IC2>
10323e519524SHoward Hinnantbool
10331237dccaSHoward Hinnant__equal_aligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1,
10341237dccaSHoward Hinnant                __bit_iterator<_Cp, _IC2> __first2)
10353e519524SHoward Hinnant{
10361237dccaSHoward Hinnant    typedef __bit_iterator<_Cp, _IC1> _It;
10373e519524SHoward Hinnant    typedef  typename _It::difference_type difference_type;
10383e519524SHoward Hinnant    typedef typename _It::__storage_type __storage_type;
1039aec08784SEric Fiselier    static const int __bits_per_word = _It::__bits_per_word;
10403e519524SHoward Hinnant    difference_type __n = __last1 - __first1;
10413e519524SHoward Hinnant    if (__n > 0)
10423e519524SHoward Hinnant    {
10433e519524SHoward Hinnant        // do first word
10443e519524SHoward Hinnant        if (__first1.__ctz_ != 0)
10453e519524SHoward Hinnant        {
10463e519524SHoward Hinnant            unsigned __clz = __bits_per_word - __first1.__ctz_;
1047ce48a113SHoward Hinnant            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
10483e519524SHoward Hinnant            __n -= __dn;
10493e519524SHoward Hinnant            __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
10503e519524SHoward Hinnant            if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))
10513e519524SHoward Hinnant                return false;
10523e519524SHoward Hinnant            ++__first2.__seg_;
10533e519524SHoward Hinnant            ++__first1.__seg_;
10543e519524SHoward Hinnant            // __first1.__ctz_ = 0;
10553e519524SHoward Hinnant            // __first2.__ctz_ = 0;
10563e519524SHoward Hinnant        }
10573e519524SHoward Hinnant        // __first1.__ctz_ == 0;
10583e519524SHoward Hinnant        // __first2.__ctz_ == 0;
10593e519524SHoward Hinnant        // do middle words
10603e519524SHoward Hinnant        for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_)
10613e519524SHoward Hinnant            if (*__first2.__seg_ != *__first1.__seg_)
10623e519524SHoward Hinnant                return false;
10633e519524SHoward Hinnant        // do last word
10643e519524SHoward Hinnant        if (__n > 0)
10653e519524SHoward Hinnant        {
10663e519524SHoward Hinnant            __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
10673e519524SHoward Hinnant            if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))
10683e519524SHoward Hinnant                return false;
10693e519524SHoward Hinnant        }
10703e519524SHoward Hinnant    }
10713e519524SHoward Hinnant    return true;
10723e519524SHoward Hinnant}
10733e519524SHoward Hinnant
1074c003db1fSHoward Hinnanttemplate <class _Cp, bool _IC1, bool _IC2>
107543d99238SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY
10763e519524SHoward Hinnantbool
1077c003db1fSHoward Hinnantequal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2)
10783e519524SHoward Hinnant{
10793e519524SHoward Hinnant    if (__first1.__ctz_ == __first2.__ctz_)
10803e519524SHoward Hinnant        return __equal_aligned(__first1, __last1, __first2);
10813e519524SHoward Hinnant    return __equal_unaligned(__first1, __last1, __first2);
10823e519524SHoward Hinnant}
10833e519524SHoward Hinnant
10840ae9efebSHoward Hinnanttemplate <class _Cp, bool _IsConst,
10850ae9efebSHoward Hinnant          typename _Cp::__storage_type>
10863e519524SHoward Hinnantclass __bit_iterator
10873e519524SHoward Hinnant{
10883e519524SHoward Hinnantpublic:
1089c003db1fSHoward Hinnant    typedef typename _Cp::difference_type                                                          difference_type;
10903e519524SHoward Hinnant    typedef bool                                                                                  value_type;
10913e519524SHoward Hinnant    typedef __bit_iterator                                                                        pointer;
1092c003db1fSHoward Hinnant    typedef typename conditional<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >::type reference;
10933e519524SHoward Hinnant    typedef random_access_iterator_tag                                                            iterator_category;
10943e519524SHoward Hinnant
10953e519524SHoward Hinnantprivate:
1096c003db1fSHoward Hinnant    typedef typename _Cp::__storage_type                                           __storage_type;
1097c003db1fSHoward Hinnant    typedef typename conditional<_IsConst, typename _Cp::__const_storage_pointer,
1098c003db1fSHoward Hinnant                                           typename _Cp::__storage_pointer>::type  __storage_pointer;
1099c003db1fSHoward Hinnant    static const unsigned __bits_per_word = _Cp::__bits_per_word;
11003e519524SHoward Hinnant
11013e519524SHoward Hinnant    __storage_pointer __seg_;
11023e519524SHoward Hinnant    unsigned          __ctz_;
11033e519524SHoward Hinnant
11043e519524SHoward Hinnantpublic:
110536b2a3b0SMarshall Clow    _LIBCPP_INLINE_VISIBILITY __bit_iterator() _NOEXCEPT
110636b2a3b0SMarshall Clow#if _LIBCPP_STD_VER > 11
110736b2a3b0SMarshall Clow    : __seg_(nullptr), __ctz_(0)
110836b2a3b0SMarshall Clow#endif
110936b2a3b0SMarshall Clow    {}
11103e519524SHoward Hinnant
1111d368a84cSHoward Hinnant    _LIBCPP_INLINE_VISIBILITY
1112c003db1fSHoward Hinnant    __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT
11133e519524SHoward Hinnant        : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {}
11143e519524SHoward Hinnant
1115d368a84cSHoward Hinnant    _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT
1116d368a84cSHoward Hinnant        {return reference(__seg_, __storage_type(1) << __ctz_);}
11173e519524SHoward Hinnant
11183e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator++()
11193e519524SHoward Hinnant    {
11203e519524SHoward Hinnant        if (__ctz_ != __bits_per_word-1)
11213e519524SHoward Hinnant            ++__ctz_;
11223e519524SHoward Hinnant        else
11233e519524SHoward Hinnant        {
11243e519524SHoward Hinnant            __ctz_ = 0;
11253e519524SHoward Hinnant            ++__seg_;
11263e519524SHoward Hinnant        }
11273e519524SHoward Hinnant        return *this;
11283e519524SHoward Hinnant    }
11293e519524SHoward Hinnant
11303e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY __bit_iterator operator++(int)
11313e519524SHoward Hinnant    {
11323e519524SHoward Hinnant        __bit_iterator __tmp = *this;
11333e519524SHoward Hinnant        ++(*this);
11343e519524SHoward Hinnant        return __tmp;
11353e519524SHoward Hinnant    }
11363e519524SHoward Hinnant
11373e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator--()
11383e519524SHoward Hinnant    {
11393e519524SHoward Hinnant        if (__ctz_ != 0)
11403e519524SHoward Hinnant            --__ctz_;
11413e519524SHoward Hinnant        else
11423e519524SHoward Hinnant        {
11433e519524SHoward Hinnant            __ctz_ = __bits_per_word - 1;
11443e519524SHoward Hinnant            --__seg_;
11453e519524SHoward Hinnant        }
11463e519524SHoward Hinnant        return *this;
11473e519524SHoward Hinnant    }
11483e519524SHoward Hinnant
11493e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY __bit_iterator operator--(int)
11503e519524SHoward Hinnant    {
11513e519524SHoward Hinnant        __bit_iterator __tmp = *this;
11523e519524SHoward Hinnant        --(*this);
11533e519524SHoward Hinnant        return __tmp;
11543e519524SHoward Hinnant    }
11553e519524SHoward Hinnant
11563e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator+=(difference_type __n)
11573e519524SHoward Hinnant    {
11583e519524SHoward Hinnant        if (__n >= 0)
11593e519524SHoward Hinnant            __seg_ += (__n + __ctz_) / __bits_per_word;
11603e519524SHoward Hinnant        else
11613e519524SHoward Hinnant            __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1)
11623e519524SHoward Hinnant                    / static_cast<difference_type>(__bits_per_word);
11633e519524SHoward Hinnant        __n &= (__bits_per_word - 1);
11643e519524SHoward Hinnant        __ctz_ = static_cast<unsigned>((__n + __ctz_)  % __bits_per_word);
11653e519524SHoward Hinnant        return *this;
11663e519524SHoward Hinnant    }
11673e519524SHoward Hinnant
11683e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator-=(difference_type __n)
11693e519524SHoward Hinnant    {
11703e519524SHoward Hinnant        return *this += -__n;
11713e519524SHoward Hinnant    }
11723e519524SHoward Hinnant
11733e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY __bit_iterator operator+(difference_type __n) const
11743e519524SHoward Hinnant    {
11753e519524SHoward Hinnant        __bit_iterator __t(*this);
11763e519524SHoward Hinnant        __t += __n;
11773e519524SHoward Hinnant        return __t;
11783e519524SHoward Hinnant    }
11793e519524SHoward Hinnant
11803e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY __bit_iterator operator-(difference_type __n) const
11813e519524SHoward Hinnant    {
11823e519524SHoward Hinnant        __bit_iterator __t(*this);
11833e519524SHoward Hinnant        __t -= __n;
11843e519524SHoward Hinnant        return __t;
11853e519524SHoward Hinnant    }
11863e519524SHoward Hinnant
11873e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY
11883e519524SHoward Hinnant    friend __bit_iterator operator+(difference_type __n, const __bit_iterator& __it) {return __it + __n;}
11893e519524SHoward Hinnant
11903e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY
11913e519524SHoward Hinnant    friend difference_type operator-(const __bit_iterator& __x, const __bit_iterator& __y)
11923e519524SHoward Hinnant        {return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;}
11933e519524SHoward Hinnant
11943e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const {return *(*this + __n);}
11953e519524SHoward Hinnant
11963e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY friend bool operator==(const __bit_iterator& __x, const __bit_iterator& __y)
11973e519524SHoward Hinnant        {return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;}
11983e519524SHoward Hinnant
11993e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY friend bool operator!=(const __bit_iterator& __x, const __bit_iterator& __y)
12003e519524SHoward Hinnant        {return !(__x == __y);}
12013e519524SHoward Hinnant
12023e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY friend bool operator<(const __bit_iterator& __x, const __bit_iterator& __y)
12033e519524SHoward Hinnant        {return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);}
12043e519524SHoward Hinnant
12053e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY friend bool operator>(const __bit_iterator& __x, const __bit_iterator& __y)
12063e519524SHoward Hinnant        {return __y < __x;}
12073e519524SHoward Hinnant
12083e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y)
12093e519524SHoward Hinnant        {return !(__y < __x);}
12103e519524SHoward Hinnant
12113e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y)
12123e519524SHoward Hinnant        {return !(__x < __y);}
12133e519524SHoward Hinnant
12143e519524SHoward Hinnantprivate:
12153e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY
1216d368a84cSHoward Hinnant    __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT
1217d368a84cSHoward Hinnant        : __seg_(__s), __ctz_(__ctz) {}
12183e519524SHoward Hinnant
1219c003db1fSHoward Hinnant    friend typename _Cp::__self;
1220541f9e28SEric Fiselier
1221c003db1fSHoward Hinnant    friend class __bit_reference<_Cp>;
1222c003db1fSHoward Hinnant    friend class __bit_const_reference<_Cp>;
1223c003db1fSHoward Hinnant    friend class __bit_iterator<_Cp, true>;
1224c003db1fSHoward Hinnant    template <class _Dp> friend struct __bit_array;
1225c003db1fSHoward Hinnant    template <class _Dp> friend void __fill_n_false(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n);
1226c003db1fSHoward Hinnant    template <class _Dp> friend void __fill_n_true(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n);
1227c003db1fSHoward Hinnant    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_aligned(__bit_iterator<_Dp, _IC> __first,
1228c003db1fSHoward Hinnant                                                                                  __bit_iterator<_Dp, _IC> __last,
1229c003db1fSHoward Hinnant                                                                                  __bit_iterator<_Dp, false> __result);
1230c003db1fSHoward Hinnant    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_unaligned(__bit_iterator<_Dp, _IC> __first,
1231c003db1fSHoward Hinnant                                                                                    __bit_iterator<_Dp, _IC> __last,
1232c003db1fSHoward Hinnant                                                                                    __bit_iterator<_Dp, false> __result);
1233c003db1fSHoward Hinnant    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy(__bit_iterator<_Dp, _IC> __first,
1234c003db1fSHoward Hinnant                                                                        __bit_iterator<_Dp, _IC> __last,
1235c003db1fSHoward Hinnant                                                                        __bit_iterator<_Dp, false> __result);
1236c003db1fSHoward Hinnant    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_aligned(__bit_iterator<_Dp, _IC> __first,
1237c003db1fSHoward Hinnant                                                                                           __bit_iterator<_Dp, _IC> __last,
1238c003db1fSHoward Hinnant                                                                                           __bit_iterator<_Dp, false> __result);
1239c003db1fSHoward Hinnant    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_unaligned(__bit_iterator<_Dp, _IC> __first,
1240c003db1fSHoward Hinnant                                                                                             __bit_iterator<_Dp, _IC> __last,
1241c003db1fSHoward Hinnant                                                                                             __bit_iterator<_Dp, false> __result);
1242c003db1fSHoward Hinnant    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy_backward(__bit_iterator<_Dp, _IC> __first,
1243c003db1fSHoward Hinnant                                                                                 __bit_iterator<_Dp, _IC> __last,
1244c003db1fSHoward Hinnant                                                                                 __bit_iterator<_Dp, false> __result);
1245dbe81119SHoward Hinnant    template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_aligned(__bit_iterator<__C1, false>,
1246dbe81119SHoward Hinnant                                                                                           __bit_iterator<__C1, false>,
1247dbe81119SHoward Hinnant                                                                                           __bit_iterator<__C2, false>);
1248dbe81119SHoward Hinnant    template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_unaligned(__bit_iterator<__C1, false>,
1249dbe81119SHoward Hinnant                                                                                             __bit_iterator<__C1, false>,
1250dbe81119SHoward Hinnant                                                                                             __bit_iterator<__C2, false>);
1251dbe81119SHoward Hinnant    template <class __C1, class __C2>friend __bit_iterator<__C2, false> swap_ranges(__bit_iterator<__C1, false>,
1252dbe81119SHoward Hinnant                                                                                 __bit_iterator<__C1, false>,
1253dbe81119SHoward Hinnant                                                                                 __bit_iterator<__C2, false>);
1254c003db1fSHoward Hinnant    template <class _Dp> friend __bit_iterator<_Dp, false> rotate(__bit_iterator<_Dp, false>,
1255c003db1fSHoward Hinnant                                                                __bit_iterator<_Dp, false>,
1256c003db1fSHoward Hinnant                                                                __bit_iterator<_Dp, false>);
12571237dccaSHoward Hinnant    template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_aligned(__bit_iterator<_Dp, _IC1>,
12581237dccaSHoward Hinnant                                                    __bit_iterator<_Dp, _IC1>,
12591237dccaSHoward Hinnant                                                    __bit_iterator<_Dp, _IC2>);
12601237dccaSHoward Hinnant    template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_unaligned(__bit_iterator<_Dp, _IC1>,
12611237dccaSHoward Hinnant                                                      __bit_iterator<_Dp, _IC1>,
12621237dccaSHoward Hinnant                                                      __bit_iterator<_Dp, _IC2>);
1263c003db1fSHoward Hinnant    template <class _Dp, bool _IC1, bool _IC2> friend bool equal(__bit_iterator<_Dp, _IC1>,
1264c003db1fSHoward Hinnant                                                                __bit_iterator<_Dp, _IC1>,
1265c003db1fSHoward Hinnant                                                                __bit_iterator<_Dp, _IC2>);
1266423a8d77SHoward Hinnant    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_true(__bit_iterator<_Dp, _IC>,
1267c003db1fSHoward Hinnant                                                                          typename _Dp::size_type);
1268423a8d77SHoward Hinnant    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_false(__bit_iterator<_Dp, _IC>,
1269c003db1fSHoward Hinnant                                                                           typename _Dp::size_type);
1270423a8d77SHoward Hinnant    template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type
1271423a8d77SHoward Hinnant                   __count_bool_true(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
1272423a8d77SHoward Hinnant    template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type
1273423a8d77SHoward Hinnant                   __count_bool_false(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
12743e519524SHoward Hinnant};
12753e519524SHoward Hinnant
12763e519524SHoward Hinnant_LIBCPP_END_NAMESPACE_STD
12773e519524SHoward Hinnant
1278*a016efb1SEric Fiselier_LIBCPP_POP_MACROS
1279*a016efb1SEric Fiselier
12803e519524SHoward Hinnant#endif  // _LIBCPP___BIT_REFERENCE
1281