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
17ab4f4382SHoward Hinnant#include <__undef_min_max>
18ab4f4382SHoward Hinnant
19073458b1SHoward Hinnant#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
203e519524SHoward Hinnant#pragma GCC system_header
21073458b1SHoward Hinnant#endif
223e519524SHoward Hinnant
233e519524SHoward Hinnant_LIBCPP_BEGIN_NAMESPACE_STD
243e519524SHoward Hinnant
250ae9efebSHoward Hinnanttemplate <class _Cp, bool _IsConst, typename _Cp::__storage_type = 0> class __bit_iterator;
26c003db1fSHoward Hinnanttemplate <class _Cp> class __bit_const_reference;
273e519524SHoward Hinnant
28a7744562SHoward Hinnanttemplate <class _Tp>
29a7744562SHoward Hinnantstruct __has_storage_type
30a7744562SHoward Hinnant{
31a7744562SHoward Hinnant    static const bool value = false;
32a7744562SHoward Hinnant};
33a7744562SHoward Hinnant
34c003db1fSHoward Hinnanttemplate <class _Cp, bool = __has_storage_type<_Cp>::value>
353e519524SHoward Hinnantclass __bit_reference
363e519524SHoward Hinnant{
37c003db1fSHoward Hinnant    typedef typename _Cp::__storage_type    __storage_type;
38c003db1fSHoward Hinnant    typedef typename _Cp::__storage_pointer __storage_pointer;
393e519524SHoward Hinnant
403e519524SHoward Hinnant    __storage_pointer __seg_;
413e519524SHoward Hinnant    __storage_type    __mask_;
423e519524SHoward Hinnant
433e519524SHoward Hinnant#if defined(__clang__)
44c003db1fSHoward Hinnant    friend typename _Cp::__self;
453e519524SHoward Hinnant#else
46c003db1fSHoward Hinnant    friend class _Cp::__self;
473e519524SHoward Hinnant#endif
48c003db1fSHoward Hinnant    friend class __bit_const_reference<_Cp>;
49c003db1fSHoward Hinnant    friend class __bit_iterator<_Cp, false>;
503e519524SHoward Hinnantpublic:
51d368a84cSHoward Hinnant    _LIBCPP_INLINE_VISIBILITY operator bool() const _NOEXCEPT
52d368a84cSHoward Hinnant        {return static_cast<bool>(*__seg_ & __mask_);}
53d368a84cSHoward Hinnant    _LIBCPP_INLINE_VISIBILITY bool operator ~() const _NOEXCEPT
54d368a84cSHoward Hinnant        {return !static_cast<bool>(*this);}
553e519524SHoward Hinnant
563e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY
57d368a84cSHoward Hinnant    __bit_reference& operator=(bool __x) _NOEXCEPT
583e519524SHoward Hinnant    {
593e519524SHoward Hinnant        if (__x)
603e519524SHoward Hinnant            *__seg_ |= __mask_;
613e519524SHoward Hinnant        else
623e519524SHoward Hinnant            *__seg_ &= ~__mask_;
633e519524SHoward Hinnant        return *this;
643e519524SHoward Hinnant    }
653e519524SHoward Hinnant
663e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY
67d368a84cSHoward Hinnant    __bit_reference& operator=(const __bit_reference& __x) _NOEXCEPT
68d368a84cSHoward Hinnant        {return operator=(static_cast<bool>(__x));}
693e519524SHoward Hinnant
70d368a84cSHoward Hinnant    _LIBCPP_INLINE_VISIBILITY void flip() _NOEXCEPT {*__seg_ ^= __mask_;}
71c003db1fSHoward Hinnant    _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, false> operator&() const _NOEXCEPT
72c003db1fSHoward Hinnant        {return __bit_iterator<_Cp, false>(__seg_, static_cast<unsigned>(__ctz(__mask_)));}
733e519524SHoward Hinnantprivate:
743e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY
75d368a84cSHoward Hinnant    __bit_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT
76d368a84cSHoward Hinnant        : __seg_(__s), __mask_(__m) {}
773e519524SHoward Hinnant};
783e519524SHoward Hinnant
79c003db1fSHoward Hinnanttemplate <class _Cp>
80c003db1fSHoward Hinnantclass __bit_reference<_Cp, false>
81a7744562SHoward Hinnant{
82a7744562SHoward Hinnant};
83a7744562SHoward Hinnant
84*d9db9f90SHoward Hinnanttemplate <class _Cp>
85*d9db9f90SHoward Hinnant_LIBCPP_INLINE_VISIBILITY inline
86*d9db9f90SHoward Hinnantvoid
87*d9db9f90SHoward Hinnantswap(__bit_reference<_Cp> __x, __bit_reference<_Cp> __y) _NOEXCEPT
88*d9db9f90SHoward Hinnant{
89*d9db9f90SHoward Hinnant    bool __t = __x;
90*d9db9f90SHoward Hinnant    __x = __y;
91*d9db9f90SHoward Hinnant    __y = __t;
92*d9db9f90SHoward Hinnant}
93*d9db9f90SHoward Hinnant
94c003db1fSHoward Hinnanttemplate <class _Cp, class _Dp>
953e519524SHoward Hinnant_LIBCPP_INLINE_VISIBILITY inline
963e519524SHoward Hinnantvoid
97c003db1fSHoward Hinnantswap(__bit_reference<_Cp> __x, __bit_reference<_Dp> __y) _NOEXCEPT
983e519524SHoward Hinnant{
993e519524SHoward Hinnant    bool __t = __x;
1003e519524SHoward Hinnant    __x = __y;
1013e519524SHoward Hinnant    __y = __t;
1023e519524SHoward Hinnant}
1033e519524SHoward Hinnant
104c003db1fSHoward Hinnanttemplate <class _Cp>
1053e519524SHoward Hinnant_LIBCPP_INLINE_VISIBILITY inline
1063e519524SHoward Hinnantvoid
107c003db1fSHoward Hinnantswap(__bit_reference<_Cp> __x, bool& __y) _NOEXCEPT
1083e519524SHoward Hinnant{
1093e519524SHoward Hinnant    bool __t = __x;
1103e519524SHoward Hinnant    __x = __y;
1113e519524SHoward Hinnant    __y = __t;
1123e519524SHoward Hinnant}
1133e519524SHoward Hinnant
114c003db1fSHoward Hinnanttemplate <class _Cp>
1153e519524SHoward Hinnant_LIBCPP_INLINE_VISIBILITY inline
1163e519524SHoward Hinnantvoid
117c003db1fSHoward Hinnantswap(bool& __x, __bit_reference<_Cp> __y) _NOEXCEPT
1183e519524SHoward Hinnant{
1193e519524SHoward Hinnant    bool __t = __x;
1203e519524SHoward Hinnant    __x = __y;
1213e519524SHoward Hinnant    __y = __t;
1223e519524SHoward Hinnant}
1233e519524SHoward Hinnant
124c003db1fSHoward Hinnanttemplate <class _Cp>
1253e519524SHoward Hinnantclass __bit_const_reference
1263e519524SHoward Hinnant{
127c003db1fSHoward Hinnant    typedef typename _Cp::__storage_type          __storage_type;
128c003db1fSHoward Hinnant    typedef typename _Cp::__const_storage_pointer __storage_pointer;
1293e519524SHoward Hinnant
1303e519524SHoward Hinnant    __storage_pointer        __seg_;
1313e519524SHoward Hinnant    __storage_type __mask_;
1323e519524SHoward Hinnant
1333e519524SHoward Hinnant#if defined(__clang__)
134c003db1fSHoward Hinnant    friend typename _Cp::__self;
1353e519524SHoward Hinnant#else
136c003db1fSHoward Hinnant    friend class _Cp::__self;
1373e519524SHoward Hinnant#endif
138c003db1fSHoward Hinnant    friend class __bit_iterator<_Cp, true>;
1393e519524SHoward Hinnantpublic:
1403e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY
141c003db1fSHoward Hinnant    __bit_const_reference(const __bit_reference<_Cp>& __x) _NOEXCEPT
1423e519524SHoward Hinnant        : __seg_(__x.__seg_), __mask_(__x.__mask_) {}
1433e519524SHoward Hinnant
144eeac9fcfSHoward Hinnant    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR operator bool() const _NOEXCEPT
145d368a84cSHoward Hinnant        {return static_cast<bool>(*__seg_ & __mask_);}
1463e519524SHoward Hinnant
147c003db1fSHoward Hinnant    _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, true> operator&() const _NOEXCEPT
148c003db1fSHoward Hinnant        {return __bit_iterator<_Cp, true>(__seg_, static_cast<unsigned>(__ctz(__mask_)));}
1493e519524SHoward Hinnantprivate:
1503e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY
151eeac9fcfSHoward Hinnant    _LIBCPP_CONSTEXPR
152d368a84cSHoward Hinnant    __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT
153d368a84cSHoward Hinnant        : __seg_(__s), __mask_(__m) {}
1543e519524SHoward Hinnant
1553e519524SHoward Hinnant    __bit_const_reference& operator=(const __bit_const_reference& __x);
1563e519524SHoward Hinnant};
1573e519524SHoward Hinnant
1583e519524SHoward Hinnant// find
1593e519524SHoward Hinnant
160423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst>
161423a8d77SHoward Hinnant__bit_iterator<_Cp, _IsConst>
162423a8d77SHoward Hinnant__find_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
1633e519524SHoward Hinnant{
164423a8d77SHoward Hinnant    typedef __bit_iterator<_Cp, _IsConst> _It;
1653e519524SHoward Hinnant    typedef typename _It::__storage_type __storage_type;
1663e519524SHoward Hinnant    static const unsigned __bits_per_word = _It::__bits_per_word;
1673e519524SHoward Hinnant    // do first partial word
1683e519524SHoward Hinnant    if (__first.__ctz_ != 0)
1693e519524SHoward Hinnant    {
1703e519524SHoward Hinnant        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
171ce48a113SHoward Hinnant        __storage_type __dn = _VSTD::min(__clz_f, __n);
1723e519524SHoward Hinnant        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
1733e519524SHoward Hinnant        __storage_type __b = *__first.__seg_ & __m;
1743e519524SHoward Hinnant        if (__b)
175ce48a113SHoward Hinnant            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
1763e519524SHoward Hinnant        __n -= __dn;
1773e519524SHoward Hinnant        ++__first.__seg_;
1783e519524SHoward Hinnant    }
1793e519524SHoward Hinnant    // do middle whole words
1803e519524SHoward Hinnant    for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
1813e519524SHoward Hinnant        if (*__first.__seg_)
182ce48a113SHoward Hinnant            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(*__first.__seg_)));
1833e519524SHoward Hinnant    // do last partial word
1843e519524SHoward Hinnant    if (__n > 0)
1853e519524SHoward Hinnant    {
1863e519524SHoward Hinnant        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
1873e519524SHoward Hinnant        __storage_type __b = *__first.__seg_ & __m;
1883e519524SHoward Hinnant        if (__b)
189ce48a113SHoward Hinnant            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
1903e519524SHoward Hinnant    }
1913e519524SHoward Hinnant    return _It(__first.__seg_, static_cast<unsigned>(__n));
1923e519524SHoward Hinnant}
1933e519524SHoward Hinnant
194423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst>
195423a8d77SHoward Hinnant__bit_iterator<_Cp, _IsConst>
196423a8d77SHoward Hinnant__find_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
1973e519524SHoward Hinnant{
198423a8d77SHoward Hinnant    typedef __bit_iterator<_Cp, _IsConst> _It;
1993e519524SHoward Hinnant    typedef typename _It::__storage_type __storage_type;
2003e519524SHoward Hinnant    static const unsigned __bits_per_word = _It::__bits_per_word;
2013e519524SHoward Hinnant    // do first partial word
2023e519524SHoward Hinnant    if (__first.__ctz_ != 0)
2033e519524SHoward Hinnant    {
2043e519524SHoward Hinnant        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
205ce48a113SHoward Hinnant        __storage_type __dn = _VSTD::min(__clz_f, __n);
2063e519524SHoward Hinnant        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
207423a8d77SHoward Hinnant        __storage_type __b = ~*__first.__seg_ & __m;
2083e519524SHoward Hinnant        if (__b)
209ce48a113SHoward Hinnant            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
2103e519524SHoward Hinnant        __n -= __dn;
2113e519524SHoward Hinnant        ++__first.__seg_;
2123e519524SHoward Hinnant    }
2133e519524SHoward Hinnant    // do middle whole words
2143e519524SHoward Hinnant    for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
2153e519524SHoward Hinnant    {
2163e519524SHoward Hinnant        __storage_type __b = ~*__first.__seg_;
2173e519524SHoward Hinnant        if (__b)
218ce48a113SHoward Hinnant            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
2193e519524SHoward Hinnant    }
2203e519524SHoward Hinnant    // do last partial word
2213e519524SHoward Hinnant    if (__n > 0)
2223e519524SHoward Hinnant    {
2233e519524SHoward Hinnant        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
224423a8d77SHoward Hinnant        __storage_type __b = ~*__first.__seg_ & __m;
2253e519524SHoward Hinnant        if (__b)
226ce48a113SHoward Hinnant            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
2273e519524SHoward Hinnant    }
2283e519524SHoward Hinnant    return _It(__first.__seg_, static_cast<unsigned>(__n));
2293e519524SHoward Hinnant}
2303e519524SHoward Hinnant
231423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst, class _Tp>
2323e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY
233423a8d77SHoward Hinnant__bit_iterator<_Cp, _IsConst>
234423a8d77SHoward Hinnantfind(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_)
2353e519524SHoward Hinnant{
236e4383379SHoward Hinnant    if (static_cast<bool>(__value_))
237c003db1fSHoward Hinnant        return __find_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first));
238c003db1fSHoward Hinnant    return __find_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first));
2393e519524SHoward Hinnant}
2403e519524SHoward Hinnant
2413e519524SHoward Hinnant// count
2423e519524SHoward Hinnant
243423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst>
244423a8d77SHoward Hinnanttypename __bit_iterator<_Cp, _IsConst>::difference_type
245423a8d77SHoward Hinnant__count_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
2463e519524SHoward Hinnant{
247423a8d77SHoward Hinnant    typedef __bit_iterator<_Cp, _IsConst> _It;
2483e519524SHoward Hinnant    typedef typename _It::__storage_type __storage_type;
2493e519524SHoward Hinnant    typedef typename _It::difference_type difference_type;
2503e519524SHoward Hinnant    static const unsigned __bits_per_word = _It::__bits_per_word;
2513e519524SHoward Hinnant    difference_type __r = 0;
2523e519524SHoward Hinnant    // do first partial word
2533e519524SHoward Hinnant    if (__first.__ctz_ != 0)
2543e519524SHoward Hinnant    {
2553e519524SHoward Hinnant        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
256ce48a113SHoward Hinnant        __storage_type __dn = _VSTD::min(__clz_f, __n);
2573e519524SHoward Hinnant        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
258ce48a113SHoward Hinnant        __r = _VSTD::__pop_count(*__first.__seg_ & __m);
2593e519524SHoward Hinnant        __n -= __dn;
2603e519524SHoward Hinnant        ++__first.__seg_;
2613e519524SHoward Hinnant    }
2623e519524SHoward Hinnant    // do middle whole words
2633e519524SHoward Hinnant    for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
264ce48a113SHoward Hinnant        __r += _VSTD::__pop_count(*__first.__seg_);
2653e519524SHoward Hinnant    // do last partial word
2663e519524SHoward Hinnant    if (__n > 0)
2673e519524SHoward Hinnant    {
2683e519524SHoward Hinnant        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
269ce48a113SHoward Hinnant        __r += _VSTD::__pop_count(*__first.__seg_ & __m);
2703e519524SHoward Hinnant    }
2713e519524SHoward Hinnant    return __r;
2723e519524SHoward Hinnant}
2733e519524SHoward Hinnant
274423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst>
275423a8d77SHoward Hinnanttypename __bit_iterator<_Cp, _IsConst>::difference_type
276423a8d77SHoward Hinnant__count_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
2773e519524SHoward Hinnant{
278423a8d77SHoward Hinnant    typedef __bit_iterator<_Cp, _IsConst> _It;
2793e519524SHoward Hinnant    typedef typename _It::__storage_type __storage_type;
2803e519524SHoward Hinnant    typedef typename _It::difference_type difference_type;
2813e519524SHoward Hinnant    static const unsigned __bits_per_word = _It::__bits_per_word;
2823e519524SHoward Hinnant    difference_type __r = 0;
2833e519524SHoward Hinnant    // do first partial word
2843e519524SHoward Hinnant    if (__first.__ctz_ != 0)
2853e519524SHoward Hinnant    {
2863e519524SHoward Hinnant        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
287ce48a113SHoward Hinnant        __storage_type __dn = _VSTD::min(__clz_f, __n);
2883e519524SHoward Hinnant        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
289423a8d77SHoward Hinnant        __r = _VSTD::__pop_count(~*__first.__seg_ & __m);
2903e519524SHoward Hinnant        __n -= __dn;
2913e519524SHoward Hinnant        ++__first.__seg_;
2923e519524SHoward Hinnant    }
2933e519524SHoward Hinnant    // do middle whole words
2943e519524SHoward Hinnant    for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
295ce48a113SHoward Hinnant        __r += _VSTD::__pop_count(~*__first.__seg_);
2963e519524SHoward Hinnant    // do last partial word
2973e519524SHoward Hinnant    if (__n > 0)
2983e519524SHoward Hinnant    {
2993e519524SHoward Hinnant        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
300423a8d77SHoward Hinnant        __r += _VSTD::__pop_count(~*__first.__seg_ & __m);
3013e519524SHoward Hinnant    }
3023e519524SHoward Hinnant    return __r;
3033e519524SHoward Hinnant}
3043e519524SHoward Hinnant
305423a8d77SHoward Hinnanttemplate <class _Cp, bool _IsConst, class _Tp>
3063e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY
307423a8d77SHoward Hinnanttypename __bit_iterator<_Cp, _IsConst>::difference_type
308423a8d77SHoward Hinnantcount(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_)
3093e519524SHoward Hinnant{
310e4383379SHoward Hinnant    if (static_cast<bool>(__value_))
311c003db1fSHoward Hinnant        return __count_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first));
312c003db1fSHoward Hinnant    return __count_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first));
3133e519524SHoward Hinnant}
3143e519524SHoward Hinnant
3153e519524SHoward Hinnant// fill_n
3163e519524SHoward Hinnant
317c003db1fSHoward Hinnanttemplate <class _Cp>
3183e519524SHoward Hinnantvoid
319c003db1fSHoward Hinnant__fill_n_false(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n)
3203e519524SHoward Hinnant{
321c003db1fSHoward Hinnant    typedef __bit_iterator<_Cp, false> _It;
3223e519524SHoward Hinnant    typedef typename _It::__storage_type __storage_type;
3233e519524SHoward Hinnant    static const unsigned __bits_per_word = _It::__bits_per_word;
3243e519524SHoward Hinnant    // do first partial word
3253e519524SHoward Hinnant    if (__first.__ctz_ != 0)
3263e519524SHoward Hinnant    {
3273e519524SHoward Hinnant        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
328ce48a113SHoward Hinnant        __storage_type __dn = _VSTD::min(__clz_f, __n);
3293e519524SHoward Hinnant        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
3303e519524SHoward Hinnant        *__first.__seg_ &= ~__m;
3313e519524SHoward Hinnant        __n -= __dn;
3323e519524SHoward Hinnant        ++__first.__seg_;
3333e519524SHoward Hinnant    }
3343e519524SHoward Hinnant    // do middle whole words
3353e519524SHoward Hinnant    __storage_type __nw = __n / __bits_per_word;
336ce48a113SHoward Hinnant    _VSTD::memset(__first.__seg_, 0, __nw * sizeof(__storage_type));
3373e519524SHoward Hinnant    __n -= __nw * __bits_per_word;
3383e519524SHoward Hinnant    // do last partial word
3393e519524SHoward Hinnant    if (__n > 0)
3403e519524SHoward Hinnant    {
3413e519524SHoward Hinnant        __first.__seg_ += __nw;
3423e519524SHoward Hinnant        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3433e519524SHoward Hinnant        *__first.__seg_ &= ~__m;
3443e519524SHoward Hinnant    }
3453e519524SHoward Hinnant}
3463e519524SHoward Hinnant
347c003db1fSHoward Hinnanttemplate <class _Cp>
3483e519524SHoward Hinnantvoid
349c003db1fSHoward Hinnant__fill_n_true(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n)
3503e519524SHoward Hinnant{
351c003db1fSHoward Hinnant    typedef __bit_iterator<_Cp, false> _It;
3523e519524SHoward Hinnant    typedef typename _It::__storage_type __storage_type;
3533e519524SHoward Hinnant    static const unsigned __bits_per_word = _It::__bits_per_word;
3543e519524SHoward Hinnant    // do first partial word
3553e519524SHoward Hinnant    if (__first.__ctz_ != 0)
3563e519524SHoward Hinnant    {
3573e519524SHoward Hinnant        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
358ce48a113SHoward Hinnant        __storage_type __dn = _VSTD::min(__clz_f, __n);
3593e519524SHoward Hinnant        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
3603e519524SHoward Hinnant        *__first.__seg_ |= __m;
3613e519524SHoward Hinnant        __n -= __dn;
3623e519524SHoward Hinnant        ++__first.__seg_;
3633e519524SHoward Hinnant    }
3643e519524SHoward Hinnant    // do middle whole words
3653e519524SHoward Hinnant    __storage_type __nw = __n / __bits_per_word;
366ce48a113SHoward Hinnant    _VSTD::memset(__first.__seg_, -1, __nw * sizeof(__storage_type));
3673e519524SHoward Hinnant    __n -= __nw * __bits_per_word;
3683e519524SHoward Hinnant    // do last partial word
3693e519524SHoward Hinnant    if (__n > 0)
3703e519524SHoward Hinnant    {
3713e519524SHoward Hinnant        __first.__seg_ += __nw;
3723e519524SHoward Hinnant        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3733e519524SHoward Hinnant        *__first.__seg_ |= __m;
3743e519524SHoward Hinnant    }
3753e519524SHoward Hinnant}
3763e519524SHoward Hinnant
377c003db1fSHoward Hinnanttemplate <class _Cp>
3783e519524SHoward Hinnant_LIBCPP_INLINE_VISIBILITY inline
3793e519524SHoward Hinnantvoid
380c003db1fSHoward Hinnantfill_n(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n, bool __value_)
3813e519524SHoward Hinnant{
3823e519524SHoward Hinnant    if (__n > 0)
3833e519524SHoward Hinnant    {
384e4383379SHoward Hinnant        if (__value_)
3853e519524SHoward Hinnant            __fill_n_true(__first, __n);
3863e519524SHoward Hinnant        else
3873e519524SHoward Hinnant            __fill_n_false(__first, __n);
3883e519524SHoward Hinnant    }
3893e519524SHoward Hinnant}
3903e519524SHoward Hinnant
3913e519524SHoward Hinnant// fill
3923e519524SHoward Hinnant
393c003db1fSHoward Hinnanttemplate <class _Cp>
3943e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY
3953e519524SHoward Hinnantvoid
396c003db1fSHoward Hinnantfill(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __last, bool __value_)
3973e519524SHoward Hinnant{
398c003db1fSHoward Hinnant    _VSTD::fill_n(__first, static_cast<typename _Cp::size_type>(__last - __first), __value_);
3993e519524SHoward Hinnant}
4003e519524SHoward Hinnant
4013e519524SHoward Hinnant// copy
4023e519524SHoward Hinnant
403c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst>
404c003db1fSHoward Hinnant__bit_iterator<_Cp, false>
405c003db1fSHoward Hinnant__copy_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
406c003db1fSHoward Hinnant                                                     __bit_iterator<_Cp, false> __result)
4073e519524SHoward Hinnant{
408c003db1fSHoward Hinnant    typedef __bit_iterator<_Cp, _IsConst> _In;
4093e519524SHoward Hinnant    typedef  typename _In::difference_type difference_type;
4103e519524SHoward Hinnant    typedef typename _In::__storage_type __storage_type;
4113e519524SHoward Hinnant    static const unsigned __bits_per_word = _In::__bits_per_word;
4123e519524SHoward Hinnant    difference_type __n = __last - __first;
4133e519524SHoward Hinnant    if (__n > 0)
4143e519524SHoward Hinnant    {
4153e519524SHoward Hinnant        // do first word
4163e519524SHoward Hinnant        if (__first.__ctz_ != 0)
4173e519524SHoward Hinnant        {
4183e519524SHoward Hinnant            unsigned __clz = __bits_per_word - __first.__ctz_;
419ce48a113SHoward Hinnant            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
4203e519524SHoward Hinnant            __n -= __dn;
4213e519524SHoward Hinnant            __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
4223e519524SHoward Hinnant            __storage_type __b = *__first.__seg_ & __m;
4233e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
4243e519524SHoward Hinnant            *__result.__seg_ |= __b;
4253e519524SHoward Hinnant            __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
4263e519524SHoward Hinnant            __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_)  % __bits_per_word);
4273e519524SHoward Hinnant            ++__first.__seg_;
4283e519524SHoward Hinnant            // __first.__ctz_ = 0;
4293e519524SHoward Hinnant        }
4303e519524SHoward Hinnant        // __first.__ctz_ == 0;
4313e519524SHoward Hinnant        // do middle words
4323e519524SHoward Hinnant        __storage_type __nw = __n / __bits_per_word;
433ce48a113SHoward Hinnant        _VSTD::memmove(__result.__seg_, __first.__seg_, __nw * sizeof(__storage_type));
4343e519524SHoward Hinnant        __n -= __nw * __bits_per_word;
4353e519524SHoward Hinnant        __result.__seg_ += __nw;
4363e519524SHoward Hinnant        // do last word
4373e519524SHoward Hinnant        if (__n > 0)
4383e519524SHoward Hinnant        {
4393e519524SHoward Hinnant            __first.__seg_ += __nw;
4403e519524SHoward Hinnant            __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
4413e519524SHoward Hinnant            __storage_type __b = *__first.__seg_ & __m;
4423e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
4433e519524SHoward Hinnant            *__result.__seg_ |= __b;
4443e519524SHoward Hinnant            __result.__ctz_ = static_cast<unsigned>(__n);
4453e519524SHoward Hinnant        }
4463e519524SHoward Hinnant    }
4473e519524SHoward Hinnant    return __result;
4483e519524SHoward Hinnant}
4493e519524SHoward Hinnant
450c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst>
451c003db1fSHoward Hinnant__bit_iterator<_Cp, false>
452c003db1fSHoward Hinnant__copy_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
453c003db1fSHoward Hinnant                                                       __bit_iterator<_Cp, false> __result)
4543e519524SHoward Hinnant{
455c003db1fSHoward Hinnant    typedef __bit_iterator<_Cp, _IsConst> _In;
4563e519524SHoward Hinnant    typedef  typename _In::difference_type difference_type;
4573e519524SHoward Hinnant    typedef typename _In::__storage_type __storage_type;
4583e519524SHoward Hinnant    static const unsigned __bits_per_word = _In::__bits_per_word;
4593e519524SHoward Hinnant    difference_type __n = __last - __first;
4603e519524SHoward Hinnant    if (__n > 0)
4613e519524SHoward Hinnant    {
4623e519524SHoward Hinnant        // do first word
4633e519524SHoward Hinnant        if (__first.__ctz_ != 0)
4643e519524SHoward Hinnant        {
4653e519524SHoward Hinnant            unsigned __clz_f = __bits_per_word - __first.__ctz_;
466ce48a113SHoward Hinnant            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
4673e519524SHoward Hinnant            __n -= __dn;
4683e519524SHoward Hinnant            __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
4693e519524SHoward Hinnant            __storage_type __b = *__first.__seg_ & __m;
4703e519524SHoward Hinnant            unsigned __clz_r = __bits_per_word - __result.__ctz_;
471ce48a113SHoward Hinnant            __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
4723e519524SHoward Hinnant            __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
4733e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
4743e519524SHoward Hinnant            if (__result.__ctz_ > __first.__ctz_)
4753e519524SHoward Hinnant                *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_);
4763e519524SHoward Hinnant            else
4773e519524SHoward Hinnant                *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_);
4783e519524SHoward Hinnant            __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;
4793e519524SHoward Hinnant            __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_)  % __bits_per_word);
4803e519524SHoward Hinnant            __dn -= __ddn;
4813e519524SHoward Hinnant            if (__dn > 0)
4823e519524SHoward Hinnant            {
4833e519524SHoward Hinnant                __m = ~__storage_type(0) >> (__bits_per_word - __dn);
4843e519524SHoward Hinnant                *__result.__seg_ &= ~__m;
4853e519524SHoward Hinnant                *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn);
4863e519524SHoward Hinnant                __result.__ctz_ = static_cast<unsigned>(__dn);
4873e519524SHoward Hinnant            }
4883e519524SHoward Hinnant            ++__first.__seg_;
4893e519524SHoward Hinnant            // __first.__ctz_ = 0;
4903e519524SHoward Hinnant        }
4913e519524SHoward Hinnant        // __first.__ctz_ == 0;
4923e519524SHoward Hinnant        // do middle words
4933e519524SHoward Hinnant        unsigned __clz_r = __bits_per_word - __result.__ctz_;
4943e519524SHoward Hinnant        __storage_type __m = ~__storage_type(0) << __result.__ctz_;
4953e519524SHoward Hinnant        for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_)
4963e519524SHoward Hinnant        {
4973e519524SHoward Hinnant            __storage_type __b = *__first.__seg_;
4983e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
4993e519524SHoward Hinnant            *__result.__seg_ |= __b << __result.__ctz_;
5003e519524SHoward Hinnant            ++__result.__seg_;
5013e519524SHoward Hinnant            *__result.__seg_ &= __m;
5023e519524SHoward Hinnant            *__result.__seg_ |= __b >> __clz_r;
5033e519524SHoward Hinnant        }
5043e519524SHoward Hinnant        // do last word
5053e519524SHoward Hinnant        if (__n > 0)
5063e519524SHoward Hinnant        {
5073e519524SHoward Hinnant            __m = ~__storage_type(0) >> (__bits_per_word - __n);
5083e519524SHoward Hinnant            __storage_type __b = *__first.__seg_ & __m;
509ce48a113SHoward Hinnant            __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r));
5103e519524SHoward Hinnant            __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
5113e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
5123e519524SHoward Hinnant            *__result.__seg_ |= __b << __result.__ctz_;
5133e519524SHoward Hinnant            __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
5143e519524SHoward Hinnant            __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_)  % __bits_per_word);
5153e519524SHoward Hinnant            __n -= __dn;
5163e519524SHoward Hinnant            if (__n > 0)
5173e519524SHoward Hinnant            {
5183e519524SHoward Hinnant                __m = ~__storage_type(0) >> (__bits_per_word - __n);
5193e519524SHoward Hinnant                *__result.__seg_ &= ~__m;
5203e519524SHoward Hinnant                *__result.__seg_ |= __b >> __dn;
5213e519524SHoward Hinnant                __result.__ctz_ = static_cast<unsigned>(__n);
5223e519524SHoward Hinnant            }
5233e519524SHoward Hinnant        }
5243e519524SHoward Hinnant    }
5253e519524SHoward Hinnant    return __result;
5263e519524SHoward Hinnant}
5273e519524SHoward Hinnant
528c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst>
5293e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY
530c003db1fSHoward Hinnant__bit_iterator<_Cp, false>
531c003db1fSHoward Hinnantcopy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
5323e519524SHoward Hinnant{
5333e519524SHoward Hinnant    if (__first.__ctz_ == __result.__ctz_)
5343e519524SHoward Hinnant        return __copy_aligned(__first, __last, __result);
5353e519524SHoward Hinnant    return __copy_unaligned(__first, __last, __result);
5363e519524SHoward Hinnant}
5373e519524SHoward Hinnant
5383e519524SHoward Hinnant// copy_backward
5393e519524SHoward Hinnant
540c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst>
541c003db1fSHoward Hinnant__bit_iterator<_Cp, false>
542c003db1fSHoward Hinnant__copy_backward_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
543c003db1fSHoward Hinnant                                                     __bit_iterator<_Cp, false> __result)
5443e519524SHoward Hinnant{
545c003db1fSHoward Hinnant    typedef __bit_iterator<_Cp, _IsConst> _In;
5463e519524SHoward Hinnant    typedef  typename _In::difference_type difference_type;
5473e519524SHoward Hinnant    typedef typename _In::__storage_type __storage_type;
5483e519524SHoward Hinnant    static const unsigned __bits_per_word = _In::__bits_per_word;
5493e519524SHoward Hinnant    difference_type __n = __last - __first;
5503e519524SHoward Hinnant    if (__n > 0)
5513e519524SHoward Hinnant    {
5523e519524SHoward Hinnant        // do first word
5533e519524SHoward Hinnant        if (__last.__ctz_ != 0)
5543e519524SHoward Hinnant        {
555ce48a113SHoward Hinnant            difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n);
5563e519524SHoward Hinnant            __n -= __dn;
5573e519524SHoward Hinnant            unsigned __clz = __bits_per_word - __last.__ctz_;
5583e519524SHoward Hinnant            __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz);
5593e519524SHoward Hinnant            __storage_type __b = *__last.__seg_ & __m;
5603e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
5613e519524SHoward Hinnant            *__result.__seg_ |= __b;
5623e519524SHoward Hinnant            __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) +
5633e519524SHoward Hinnant                                                       __result.__ctz_)  % __bits_per_word);
5643e519524SHoward Hinnant            // __last.__ctz_ = 0
5653e519524SHoward Hinnant         }
5663e519524SHoward Hinnant        // __last.__ctz_ == 0 || __n == 0
5673e519524SHoward Hinnant        // __result.__ctz_ == 0 || __n == 0
5683e519524SHoward Hinnant        // do middle words
5693e519524SHoward Hinnant        __storage_type __nw = __n / __bits_per_word;
5703e519524SHoward Hinnant        __result.__seg_ -= __nw;
5713e519524SHoward Hinnant        __last.__seg_ -= __nw;
572ce48a113SHoward Hinnant        _VSTD::memmove(__result.__seg_, __last.__seg_, __nw * sizeof(__storage_type));
5733e519524SHoward Hinnant        __n -= __nw * __bits_per_word;
5743e519524SHoward Hinnant        // do last word
5753e519524SHoward Hinnant        if (__n > 0)
5763e519524SHoward Hinnant        {
5773e519524SHoward Hinnant            __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n);
5783e519524SHoward Hinnant            __storage_type __b = *--__last.__seg_ & __m;
5793e519524SHoward Hinnant            *--__result.__seg_ &= ~__m;
5803e519524SHoward Hinnant            *__result.__seg_ |= __b;
5813e519524SHoward Hinnant            __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));
5823e519524SHoward Hinnant        }
5833e519524SHoward Hinnant    }
5843e519524SHoward Hinnant    return __result;
5853e519524SHoward Hinnant}
5863e519524SHoward Hinnant
587c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst>
588c003db1fSHoward Hinnant__bit_iterator<_Cp, false>
589c003db1fSHoward Hinnant__copy_backward_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
590c003db1fSHoward Hinnant                                                       __bit_iterator<_Cp, false> __result)
5913e519524SHoward Hinnant{
592c003db1fSHoward Hinnant    typedef __bit_iterator<_Cp, _IsConst> _In;
5933e519524SHoward Hinnant    typedef  typename _In::difference_type difference_type;
5943e519524SHoward Hinnant    typedef typename _In::__storage_type __storage_type;
5953e519524SHoward Hinnant    static const unsigned __bits_per_word = _In::__bits_per_word;
5963e519524SHoward Hinnant    difference_type __n = __last - __first;
5973e519524SHoward Hinnant    if (__n > 0)
5983e519524SHoward Hinnant    {
5993e519524SHoward Hinnant        // do first word
6003e519524SHoward Hinnant        if (__last.__ctz_ != 0)
6013e519524SHoward Hinnant        {
602ce48a113SHoward Hinnant            difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n);
6033e519524SHoward Hinnant            __n -= __dn;
6043e519524SHoward Hinnant            unsigned __clz_l = __bits_per_word - __last.__ctz_;
6053e519524SHoward Hinnant            __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l);
6063e519524SHoward Hinnant            __storage_type __b = *__last.__seg_ & __m;
6073e519524SHoward Hinnant            unsigned __clz_r = __bits_per_word - __result.__ctz_;
608ce48a113SHoward Hinnant            __storage_type __ddn = _VSTD::min(__dn, static_cast<difference_type>(__result.__ctz_));
6093e519524SHoward Hinnant            if (__ddn > 0)
6103e519524SHoward Hinnant            {
6113e519524SHoward Hinnant                __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r);
6123e519524SHoward Hinnant                *__result.__seg_ &= ~__m;
6133e519524SHoward Hinnant                if (__result.__ctz_ > __last.__ctz_)
6143e519524SHoward Hinnant                    *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);
6153e519524SHoward Hinnant                else
6163e519524SHoward Hinnant                    *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_);
6173e519524SHoward Hinnant                __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) +
6183e519524SHoward Hinnant                                                         __result.__ctz_)  % __bits_per_word);
6193e519524SHoward Hinnant                __dn -= __ddn;
6203e519524SHoward Hinnant            }
6213e519524SHoward Hinnant            if (__dn > 0)
6223e519524SHoward Hinnant            {
6233e519524SHoward Hinnant                // __result.__ctz_ == 0
6243e519524SHoward Hinnant                --__result.__seg_;
6253e519524SHoward Hinnant                __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1));
6263e519524SHoward Hinnant                __m = ~__storage_type(0) << __result.__ctz_;
6273e519524SHoward Hinnant                *__result.__seg_ &= ~__m;
6283e519524SHoward Hinnant                __last.__ctz_ -= __dn + __ddn;
6293e519524SHoward Hinnant                *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);
6303e519524SHoward Hinnant            }
6313e519524SHoward Hinnant            // __last.__ctz_ = 0
6323e519524SHoward Hinnant         }
6333e519524SHoward Hinnant        // __last.__ctz_ == 0 || __n == 0
6343e519524SHoward Hinnant        // __result.__ctz_ != 0 || __n == 0
6353e519524SHoward Hinnant        // do middle words
6363e519524SHoward Hinnant        unsigned __clz_r = __bits_per_word - __result.__ctz_;
6373e519524SHoward Hinnant        __storage_type __m = ~__storage_type(0) >> __clz_r;
6383e519524SHoward Hinnant        for (; __n >= __bits_per_word; __n -= __bits_per_word)
6393e519524SHoward Hinnant        {
6403e519524SHoward Hinnant            __storage_type __b = *--__last.__seg_;
6413e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
6423e519524SHoward Hinnant            *__result.__seg_ |= __b >> __clz_r;
6433e519524SHoward Hinnant            *--__result.__seg_ &= __m;
6443e519524SHoward Hinnant            *__result.__seg_ |= __b << __result.__ctz_;
6453e519524SHoward Hinnant        }
6463e519524SHoward Hinnant        // do last word
6473e519524SHoward Hinnant        if (__n > 0)
6483e519524SHoward Hinnant        {
6493e519524SHoward Hinnant            __m = ~__storage_type(0) << (__bits_per_word - __n);
6503e519524SHoward Hinnant            __storage_type __b = *--__last.__seg_ & __m;
651c206366fSHoward Hinnant            __clz_r = __bits_per_word - __result.__ctz_;
652ce48a113SHoward Hinnant            __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__result.__ctz_));
6533e519524SHoward Hinnant            __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r);
6543e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
6553e519524SHoward Hinnant            *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_);
6563e519524SHoward Hinnant            __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) +
6573e519524SHoward Hinnant                                                     __result.__ctz_)  % __bits_per_word);
6583e519524SHoward Hinnant            __n -= __dn;
6593e519524SHoward Hinnant            if (__n > 0)
6603e519524SHoward Hinnant            {
6613e519524SHoward Hinnant                // __result.__ctz_ == 0
6623e519524SHoward Hinnant                --__result.__seg_;
6633e519524SHoward Hinnant                __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));
6643e519524SHoward Hinnant                __m = ~__storage_type(0) << __result.__ctz_;
6653e519524SHoward Hinnant                *__result.__seg_ &= ~__m;
6663e519524SHoward Hinnant                *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn));
6673e519524SHoward Hinnant            }
6683e519524SHoward Hinnant        }
6693e519524SHoward Hinnant    }
6703e519524SHoward Hinnant    return __result;
6713e519524SHoward Hinnant}
6723e519524SHoward Hinnant
673c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst>
6743e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY
675c003db1fSHoward Hinnant__bit_iterator<_Cp, false>
676c003db1fSHoward Hinnantcopy_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
6773e519524SHoward Hinnant{
6783e519524SHoward Hinnant    if (__last.__ctz_ == __result.__ctz_)
6793e519524SHoward Hinnant        return __copy_backward_aligned(__first, __last, __result);
6803e519524SHoward Hinnant    return __copy_backward_unaligned(__first, __last, __result);
6813e519524SHoward Hinnant}
6823e519524SHoward Hinnant
6833e519524SHoward Hinnant// move
6843e519524SHoward Hinnant
685c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst>
6863e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY
687c003db1fSHoward Hinnant__bit_iterator<_Cp, false>
688c003db1fSHoward Hinnantmove(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
6893e519524SHoward Hinnant{
690ce48a113SHoward Hinnant    return _VSTD::copy(__first, __last, __result);
6913e519524SHoward Hinnant}
6923e519524SHoward Hinnant
6933e519524SHoward Hinnant// move_backward
6943e519524SHoward Hinnant
695c003db1fSHoward Hinnanttemplate <class _Cp, bool _IsConst>
6963e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY
697c003db1fSHoward Hinnant__bit_iterator<_Cp, false>
698c003db1fSHoward Hinnantmove_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
6993e519524SHoward Hinnant{
700ce48a113SHoward Hinnant    return _VSTD::copy(__first, __last, __result);
7013e519524SHoward Hinnant}
7023e519524SHoward Hinnant
7033e519524SHoward Hinnant// swap_ranges
7043e519524SHoward Hinnant
705dbe81119SHoward Hinnanttemplate <class __C1, class __C2>
706dbe81119SHoward Hinnant__bit_iterator<__C2, false>
707dbe81119SHoward Hinnant__swap_ranges_aligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last,
708dbe81119SHoward Hinnant                      __bit_iterator<__C2, false> __result)
7093e519524SHoward Hinnant{
710dbe81119SHoward Hinnant    typedef __bit_iterator<__C1, false> _I1;
7113e519524SHoward Hinnant    typedef  typename _I1::difference_type difference_type;
7123e519524SHoward Hinnant    typedef typename _I1::__storage_type __storage_type;
7133e519524SHoward Hinnant    static const unsigned __bits_per_word = _I1::__bits_per_word;
7143e519524SHoward Hinnant    difference_type __n = __last - __first;
7153e519524SHoward Hinnant    if (__n > 0)
7163e519524SHoward Hinnant    {
7173e519524SHoward Hinnant        // do first word
7183e519524SHoward Hinnant        if (__first.__ctz_ != 0)
7193e519524SHoward Hinnant        {
7203e519524SHoward Hinnant            unsigned __clz = __bits_per_word - __first.__ctz_;
721ce48a113SHoward Hinnant            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
7223e519524SHoward Hinnant            __n -= __dn;
7233e519524SHoward Hinnant            __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
7243e519524SHoward Hinnant            __storage_type __b1 = *__first.__seg_ & __m;
7253e519524SHoward Hinnant            *__first.__seg_ &= ~__m;
7263e519524SHoward Hinnant            __storage_type __b2 = *__result.__seg_ & __m;
7273e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
7283e519524SHoward Hinnant            *__result.__seg_ |= __b1;
7293e519524SHoward Hinnant            *__first.__seg_  |= __b2;
7303e519524SHoward Hinnant            __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
7313e519524SHoward Hinnant            __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_)  % __bits_per_word);
7323e519524SHoward Hinnant            ++__first.__seg_;
7333e519524SHoward Hinnant            // __first.__ctz_ = 0;
7343e519524SHoward Hinnant        }
7353e519524SHoward Hinnant        // __first.__ctz_ == 0;
7363e519524SHoward Hinnant        // do middle words
7373e519524SHoward Hinnant        for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_)
7383e519524SHoward Hinnant            swap(*__first.__seg_, *__result.__seg_);
7393e519524SHoward Hinnant        // do last word
7403e519524SHoward Hinnant        if (__n > 0)
7413e519524SHoward Hinnant        {
7423e519524SHoward Hinnant            __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
7433e519524SHoward Hinnant            __storage_type __b1 = *__first.__seg_ & __m;
7443e519524SHoward Hinnant            *__first.__seg_ &= ~__m;
7453e519524SHoward Hinnant            __storage_type __b2 = *__result.__seg_ & __m;
7463e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
7473e519524SHoward Hinnant            *__result.__seg_ |= __b1;
7483e519524SHoward Hinnant            *__first.__seg_  |= __b2;
7493e519524SHoward Hinnant            __result.__ctz_ = static_cast<unsigned>(__n);
7503e519524SHoward Hinnant        }
7513e519524SHoward Hinnant    }
7523e519524SHoward Hinnant    return __result;
7533e519524SHoward Hinnant}
7543e519524SHoward Hinnant
755dbe81119SHoward Hinnanttemplate <class __C1, class __C2>
756dbe81119SHoward Hinnant__bit_iterator<__C2, false>
757dbe81119SHoward Hinnant__swap_ranges_unaligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last,
758dbe81119SHoward Hinnant                        __bit_iterator<__C2, false> __result)
7593e519524SHoward Hinnant{
760dbe81119SHoward Hinnant    typedef __bit_iterator<__C1, false> _I1;
7613e519524SHoward Hinnant    typedef  typename _I1::difference_type difference_type;
7623e519524SHoward Hinnant    typedef typename _I1::__storage_type __storage_type;
7633e519524SHoward Hinnant    static const unsigned __bits_per_word = _I1::__bits_per_word;
7643e519524SHoward Hinnant    difference_type __n = __last - __first;
7653e519524SHoward Hinnant    if (__n > 0)
7663e519524SHoward Hinnant    {
7673e519524SHoward Hinnant        // do first word
7683e519524SHoward Hinnant        if (__first.__ctz_ != 0)
7693e519524SHoward Hinnant        {
7703e519524SHoward Hinnant            unsigned __clz_f = __bits_per_word - __first.__ctz_;
771ce48a113SHoward Hinnant            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
7723e519524SHoward Hinnant            __n -= __dn;
7733e519524SHoward Hinnant            __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
7743e519524SHoward Hinnant            __storage_type __b1 = *__first.__seg_ & __m;
7753e519524SHoward Hinnant            *__first.__seg_ &= ~__m;
7763e519524SHoward Hinnant            unsigned __clz_r = __bits_per_word - __result.__ctz_;
777ce48a113SHoward Hinnant            __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
7783e519524SHoward Hinnant            __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
7793e519524SHoward Hinnant            __storage_type __b2 = *__result.__seg_ & __m;
7803e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
7813e519524SHoward Hinnant            if (__result.__ctz_ > __first.__ctz_)
7823e519524SHoward Hinnant            {
7833e519524SHoward Hinnant                unsigned __s = __result.__ctz_ - __first.__ctz_;
7843e519524SHoward Hinnant                *__result.__seg_ |= __b1 << __s;
7853e519524SHoward Hinnant                *__first.__seg_  |= __b2 >> __s;
7863e519524SHoward Hinnant            }
7873e519524SHoward Hinnant            else
7883e519524SHoward Hinnant            {
7893e519524SHoward Hinnant                unsigned __s = __first.__ctz_ - __result.__ctz_;
7903e519524SHoward Hinnant                *__result.__seg_ |= __b1 >> __s;
7913e519524SHoward Hinnant                *__first.__seg_  |= __b2 << __s;
7923e519524SHoward Hinnant            }
7933e519524SHoward Hinnant            __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;
7943e519524SHoward Hinnant            __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_)  % __bits_per_word);
7953e519524SHoward Hinnant            __dn -= __ddn;
7963e519524SHoward Hinnant            if (__dn > 0)
7973e519524SHoward Hinnant            {
7983e519524SHoward Hinnant                __m = ~__storage_type(0) >> (__bits_per_word - __dn);
7993e519524SHoward Hinnant                __b2 = *__result.__seg_ & __m;
8003e519524SHoward Hinnant                *__result.__seg_ &= ~__m;
8013e519524SHoward Hinnant                unsigned __s = __first.__ctz_ + __ddn;
8023e519524SHoward Hinnant                *__result.__seg_ |= __b1 >> __s;
8033e519524SHoward Hinnant                *__first.__seg_  |= __b2 << __s;
8043e519524SHoward Hinnant                __result.__ctz_ = static_cast<unsigned>(__dn);
8053e519524SHoward Hinnant            }
8063e519524SHoward Hinnant            ++__first.__seg_;
8073e519524SHoward Hinnant            // __first.__ctz_ = 0;
8083e519524SHoward Hinnant        }
8093e519524SHoward Hinnant        // __first.__ctz_ == 0;
8103e519524SHoward Hinnant        // do middle words
8113e519524SHoward Hinnant        __storage_type __m = ~__storage_type(0) << __result.__ctz_;
8123e519524SHoward Hinnant        unsigned __clz_r = __bits_per_word - __result.__ctz_;
8133e519524SHoward Hinnant        for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_)
8143e519524SHoward Hinnant        {
8153e519524SHoward Hinnant            __storage_type __b1 = *__first.__seg_;
8163e519524SHoward Hinnant            __storage_type __b2 = *__result.__seg_ & __m;
8173e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
8183e519524SHoward Hinnant            *__result.__seg_ |= __b1 << __result.__ctz_;
8193e519524SHoward Hinnant            *__first.__seg_  = __b2 >> __result.__ctz_;
8203e519524SHoward Hinnant            ++__result.__seg_;
8213e519524SHoward Hinnant            __b2 = *__result.__seg_ & ~__m;
8223e519524SHoward Hinnant            *__result.__seg_ &= __m;
8233e519524SHoward Hinnant            *__result.__seg_ |= __b1 >> __clz_r;
8243e519524SHoward Hinnant            *__first.__seg_  |= __b2 << __clz_r;
8253e519524SHoward Hinnant        }
8263e519524SHoward Hinnant        // do last word
8273e519524SHoward Hinnant        if (__n > 0)
8283e519524SHoward Hinnant        {
8293e519524SHoward Hinnant            __m = ~__storage_type(0) >> (__bits_per_word - __n);
8303e519524SHoward Hinnant            __storage_type __b1 = *__first.__seg_ & __m;
8313e519524SHoward Hinnant            *__first.__seg_ &= ~__m;
832ce48a113SHoward Hinnant            __storage_type __dn = _VSTD::min<__storage_type>(__n, __clz_r);
8333e519524SHoward Hinnant            __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
8343e519524SHoward Hinnant            __storage_type __b2 = *__result.__seg_ & __m;
8353e519524SHoward Hinnant            *__result.__seg_ &= ~__m;
8363e519524SHoward Hinnant            *__result.__seg_ |= __b1 << __result.__ctz_;
8373e519524SHoward Hinnant            *__first.__seg_  |= __b2 >> __result.__ctz_;
8383e519524SHoward Hinnant            __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
8393e519524SHoward Hinnant            __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_)  % __bits_per_word);
8403e519524SHoward Hinnant            __n -= __dn;
8413e519524SHoward Hinnant            if (__n > 0)
8423e519524SHoward Hinnant            {
8433e519524SHoward Hinnant                __m = ~__storage_type(0) >> (__bits_per_word - __n);
8443e519524SHoward Hinnant                __b2 = *__result.__seg_ & __m;
8453e519524SHoward Hinnant                *__result.__seg_ &= ~__m;
8463e519524SHoward Hinnant                *__result.__seg_ |= __b1 >> __dn;
8473e519524SHoward Hinnant                *__first.__seg_  |= __b2 << __dn;
8483e519524SHoward Hinnant                __result.__ctz_ = static_cast<unsigned>(__n);
8493e519524SHoward Hinnant            }
8503e519524SHoward Hinnant        }
8513e519524SHoward Hinnant    }
8523e519524SHoward Hinnant    return __result;
8533e519524SHoward Hinnant}
8543e519524SHoward Hinnant
855dbe81119SHoward Hinnanttemplate <class __C1, class __C2>
8563e519524SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY
857dbe81119SHoward Hinnant__bit_iterator<__C2, false>
858dbe81119SHoward Hinnantswap_ranges(__bit_iterator<__C1, false> __first1, __bit_iterator<__C1, false> __last1,
859dbe81119SHoward Hinnant            __bit_iterator<__C2, false> __first2)
8603e519524SHoward Hinnant{
8613e519524SHoward Hinnant    if (__first1.__ctz_ == __first2.__ctz_)
8623e519524SHoward Hinnant        return __swap_ranges_aligned(__first1, __last1, __first2);
8633e519524SHoward Hinnant    return __swap_ranges_unaligned(__first1, __last1, __first2);
8643e519524SHoward Hinnant}
8653e519524SHoward Hinnant
8663e519524SHoward Hinnant// rotate
8673e519524SHoward Hinnant
868c003db1fSHoward Hinnanttemplate <class _Cp>
8693e519524SHoward Hinnantstruct __bit_array
8703e519524SHoward Hinnant{
871c003db1fSHoward Hinnant    typedef typename _Cp::difference_type difference_type;
872c003db1fSHoward Hinnant    typedef typename _Cp::__storage_type  __storage_type;
873c003db1fSHoward Hinnant    typedef typename _Cp::iterator        iterator;
874c003db1fSHoward Hinnant    static const unsigned __bits_per_word = _Cp::__bits_per_word;
875c003db1fSHoward Hinnant    static const unsigned _Np = 4;
8763e519524SHoward Hinnant
8773e519524SHoward Hinnant    difference_type __size_;
878c003db1fSHoward Hinnant    __storage_type __word_[_Np];
8793e519524SHoward Hinnant
8803e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY static difference_type capacity()
881c003db1fSHoward Hinnant        {return static_cast<difference_type>(_Np * __bits_per_word);}
8823e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY explicit __bit_array(difference_type __s) : __size_(__s) {}
8833e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY iterator begin() {return iterator(__word_, 0);}
8843e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY iterator end()   {return iterator(__word_ + __size_ / __bits_per_word,
8853e519524SHoward Hinnant                                                  static_cast<unsigned>(__size_ % __bits_per_word));}
8863e519524SHoward Hinnant};
8873e519524SHoward Hinnant
888c003db1fSHoward Hinnanttemplate <class _Cp>
889c003db1fSHoward Hinnant__bit_iterator<_Cp, false>
890c003db1fSHoward Hinnantrotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last)
8913e519524SHoward Hinnant{
892c003db1fSHoward Hinnant    typedef __bit_iterator<_Cp, false> _I1;
8933e519524SHoward Hinnant    typedef  typename _I1::difference_type difference_type;
8943e519524SHoward Hinnant    typedef typename _I1::__storage_type __storage_type;
8953e519524SHoward Hinnant    difference_type __d1 = __middle - __first;
8963e519524SHoward Hinnant    difference_type __d2 = __last - __middle;
8973e519524SHoward Hinnant    _I1 __r = __first + __d2;
8983e519524SHoward Hinnant    while (__d1 != 0 && __d2 != 0)
8993e519524SHoward Hinnant    {
9003e519524SHoward Hinnant        if (__d1 <= __d2)
9013e519524SHoward Hinnant        {
902c003db1fSHoward Hinnant            if (__d1 <= __bit_array<_Cp>::capacity())
9033e519524SHoward Hinnant            {
904c003db1fSHoward Hinnant                __bit_array<_Cp> __b(__d1);
905ce48a113SHoward Hinnant                _VSTD::copy(__first, __middle, __b.begin());
906ce48a113SHoward Hinnant                _VSTD::copy(__b.begin(), __b.end(), _VSTD::copy(__middle, __last, __first));
9073e519524SHoward Hinnant                break;
9083e519524SHoward Hinnant            }
9093e519524SHoward Hinnant            else
9103e519524SHoward Hinnant            {
911c003db1fSHoward Hinnant                __bit_iterator<_Cp, false> __mp = _VSTD::swap_ranges(__first, __middle, __middle);
9123e519524SHoward Hinnant                __first = __middle;
9133e519524SHoward Hinnant                __middle = __mp;
9143e519524SHoward Hinnant                __d2 -= __d1;
9153e519524SHoward Hinnant            }
9163e519524SHoward Hinnant        }
9173e519524SHoward Hinnant        else
9183e519524SHoward Hinnant        {
919c003db1fSHoward Hinnant            if (__d2 <= __bit_array<_Cp>::capacity())
9203e519524SHoward Hinnant            {
921c003db1fSHoward Hinnant                __bit_array<_Cp> __b(__d2);
922ce48a113SHoward Hinnant                _VSTD::copy(__middle, __last, __b.begin());
923ce48a113SHoward Hinnant                _VSTD::copy_backward(__b.begin(), __b.end(), _VSTD::copy_backward(__first, __middle, __last));
9243e519524SHoward Hinnant                break;
9253e519524SHoward Hinnant            }
9263e519524SHoward Hinnant            else
9273e519524SHoward Hinnant            {
928c003db1fSHoward Hinnant                __bit_iterator<_Cp, false> __mp = __first + __d2;
929ce48a113SHoward Hinnant                _VSTD::swap_ranges(__first, __mp, __middle);
9303e519524SHoward Hinnant                __first = __mp;
9313e519524SHoward Hinnant                __d1 -= __d2;
9323e519524SHoward Hinnant            }
9333e519524SHoward Hinnant        }
9343e519524SHoward Hinnant    }
9353e519524SHoward Hinnant    return __r;
9363e519524SHoward Hinnant}
9373e519524SHoward Hinnant
9383e519524SHoward Hinnant// equal
9393e519524SHoward Hinnant
9401237dccaSHoward Hinnanttemplate <class _Cp, bool _IC1, bool _IC2>
9413e519524SHoward Hinnantbool
9421237dccaSHoward Hinnant__equal_unaligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1,
9431237dccaSHoward Hinnant                  __bit_iterator<_Cp, _IC2> __first2)
9443e519524SHoward Hinnant{
9451237dccaSHoward Hinnant    typedef __bit_iterator<_Cp, _IC1> _It;
9463e519524SHoward Hinnant    typedef  typename _It::difference_type difference_type;
9473e519524SHoward Hinnant    typedef typename _It::__storage_type __storage_type;
9483e519524SHoward Hinnant    static const unsigned __bits_per_word = _It::__bits_per_word;
9493e519524SHoward Hinnant    difference_type __n = __last1 - __first1;
9503e519524SHoward Hinnant    if (__n > 0)
9513e519524SHoward Hinnant    {
9523e519524SHoward Hinnant        // do first word
9533e519524SHoward Hinnant        if (__first1.__ctz_ != 0)
9543e519524SHoward Hinnant        {
9553e519524SHoward Hinnant            unsigned __clz_f = __bits_per_word - __first1.__ctz_;
956ce48a113SHoward Hinnant            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
9573e519524SHoward Hinnant            __n -= __dn;
9583e519524SHoward Hinnant            __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
9593e519524SHoward Hinnant            __storage_type __b = *__first1.__seg_ & __m;
9603e519524SHoward Hinnant            unsigned __clz_r = __bits_per_word - __first2.__ctz_;
961ce48a113SHoward Hinnant            __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
9623e519524SHoward Hinnant            __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
9633e519524SHoward Hinnant            if (__first2.__ctz_ > __first1.__ctz_)
9644c0de496SHoward Hinnant            {
9653e519524SHoward Hinnant                if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_)))
9663e519524SHoward Hinnant                    return false;
9674c0de496SHoward Hinnant            }
9683e519524SHoward Hinnant            else
9694c0de496SHoward Hinnant            {
9703e519524SHoward Hinnant                if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_)))
9713e519524SHoward Hinnant                    return false;
9724c0de496SHoward Hinnant            }
9733e519524SHoward Hinnant            __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word;
9743e519524SHoward Hinnant            __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_)  % __bits_per_word);
9753e519524SHoward Hinnant            __dn -= __ddn;
9763e519524SHoward Hinnant            if (__dn > 0)
9773e519524SHoward Hinnant            {
9783e519524SHoward Hinnant                __m = ~__storage_type(0) >> (__bits_per_word - __dn);
9793e519524SHoward Hinnant                if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn)))
9803e519524SHoward Hinnant                    return false;
9813e519524SHoward Hinnant                __first2.__ctz_ = static_cast<unsigned>(__dn);
9823e519524SHoward Hinnant            }
9833e519524SHoward Hinnant            ++__first1.__seg_;
9843e519524SHoward Hinnant            // __first1.__ctz_ = 0;
9853e519524SHoward Hinnant        }
9863e519524SHoward Hinnant        // __first1.__ctz_ == 0;
9873e519524SHoward Hinnant        // do middle words
9883e519524SHoward Hinnant        unsigned __clz_r = __bits_per_word - __first2.__ctz_;
9893e519524SHoward Hinnant        __storage_type __m = ~__storage_type(0) << __first2.__ctz_;
9903e519524SHoward Hinnant        for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_)
9913e519524SHoward Hinnant        {
9923e519524SHoward Hinnant            __storage_type __b = *__first1.__seg_;
9933e519524SHoward Hinnant            if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_))
9943e519524SHoward Hinnant                return false;
9953e519524SHoward Hinnant            ++__first2.__seg_;
9963e519524SHoward Hinnant            if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r))
9973e519524SHoward Hinnant                return false;
9983e519524SHoward Hinnant        }
9993e519524SHoward Hinnant        // do last word
10003e519524SHoward Hinnant        if (__n > 0)
10013e519524SHoward Hinnant        {
10023e519524SHoward Hinnant            __m = ~__storage_type(0) >> (__bits_per_word - __n);
10033e519524SHoward Hinnant            __storage_type __b = *__first1.__seg_ & __m;
1004ce48a113SHoward Hinnant            __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r));
10053e519524SHoward Hinnant            __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
10063e519524SHoward Hinnant            if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_))
10073e519524SHoward Hinnant                return false;
10083e519524SHoward Hinnant            __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word;
10093e519524SHoward Hinnant            __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_)  % __bits_per_word);
10103e519524SHoward Hinnant            __n -= __dn;
10113e519524SHoward Hinnant            if (__n > 0)
10123e519524SHoward Hinnant            {
10133e519524SHoward Hinnant                __m = ~__storage_type(0) >> (__bits_per_word - __n);
10143e519524SHoward Hinnant                if ((*__first2.__seg_ & __m) != (__b >> __dn))
10153e519524SHoward Hinnant                    return false;
10163e519524SHoward Hinnant            }
10173e519524SHoward Hinnant        }
10183e519524SHoward Hinnant    }
10193e519524SHoward Hinnant    return true;
10203e519524SHoward Hinnant}
10213e519524SHoward Hinnant
10221237dccaSHoward Hinnanttemplate <class _Cp, bool _IC1, bool _IC2>
10233e519524SHoward Hinnantbool
10241237dccaSHoward Hinnant__equal_aligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1,
10251237dccaSHoward Hinnant                __bit_iterator<_Cp, _IC2> __first2)
10263e519524SHoward Hinnant{
10271237dccaSHoward Hinnant    typedef __bit_iterator<_Cp, _IC1> _It;
10283e519524SHoward Hinnant    typedef  typename _It::difference_type difference_type;
10293e519524SHoward Hinnant    typedef typename _It::__storage_type __storage_type;
10303e519524SHoward Hinnant    static const unsigned __bits_per_word = _It::__bits_per_word;
10313e519524SHoward Hinnant    difference_type __n = __last1 - __first1;
10323e519524SHoward Hinnant    if (__n > 0)
10333e519524SHoward Hinnant    {
10343e519524SHoward Hinnant        // do first word
10353e519524SHoward Hinnant        if (__first1.__ctz_ != 0)
10363e519524SHoward Hinnant        {
10373e519524SHoward Hinnant            unsigned __clz = __bits_per_word - __first1.__ctz_;
1038ce48a113SHoward Hinnant            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
10393e519524SHoward Hinnant            __n -= __dn;
10403e519524SHoward Hinnant            __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
10413e519524SHoward Hinnant            if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))
10423e519524SHoward Hinnant                return false;
10433e519524SHoward Hinnant            ++__first2.__seg_;
10443e519524SHoward Hinnant            ++__first1.__seg_;
10453e519524SHoward Hinnant            // __first1.__ctz_ = 0;
10463e519524SHoward Hinnant            // __first2.__ctz_ = 0;
10473e519524SHoward Hinnant        }
10483e519524SHoward Hinnant        // __first1.__ctz_ == 0;
10493e519524SHoward Hinnant        // __first2.__ctz_ == 0;
10503e519524SHoward Hinnant        // do middle words
10513e519524SHoward Hinnant        for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_)
10523e519524SHoward Hinnant            if (*__first2.__seg_ != *__first1.__seg_)
10533e519524SHoward Hinnant                return false;
10543e519524SHoward Hinnant        // do last word
10553e519524SHoward Hinnant        if (__n > 0)
10563e519524SHoward Hinnant        {
10573e519524SHoward Hinnant            __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
10583e519524SHoward Hinnant            if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))
10593e519524SHoward Hinnant                return false;
10603e519524SHoward Hinnant        }
10613e519524SHoward Hinnant    }
10623e519524SHoward Hinnant    return true;
10633e519524SHoward Hinnant}
10643e519524SHoward Hinnant
1065c003db1fSHoward Hinnanttemplate <class _Cp, bool _IC1, bool _IC2>
106643d99238SHoward Hinnantinline _LIBCPP_INLINE_VISIBILITY
10673e519524SHoward Hinnantbool
1068c003db1fSHoward Hinnantequal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2)
10693e519524SHoward Hinnant{
10703e519524SHoward Hinnant    if (__first1.__ctz_ == __first2.__ctz_)
10713e519524SHoward Hinnant        return __equal_aligned(__first1, __last1, __first2);
10723e519524SHoward Hinnant    return __equal_unaligned(__first1, __last1, __first2);
10733e519524SHoward Hinnant}
10743e519524SHoward Hinnant
10750ae9efebSHoward Hinnanttemplate <class _Cp, bool _IsConst,
10760ae9efebSHoward Hinnant          typename _Cp::__storage_type>
10773e519524SHoward Hinnantclass __bit_iterator
10783e519524SHoward Hinnant{
10793e519524SHoward Hinnantpublic:
1080c003db1fSHoward Hinnant    typedef typename _Cp::difference_type                                                          difference_type;
10813e519524SHoward Hinnant    typedef bool                                                                                  value_type;
10823e519524SHoward Hinnant    typedef __bit_iterator                                                                        pointer;
1083c003db1fSHoward Hinnant    typedef typename conditional<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >::type reference;
10843e519524SHoward Hinnant    typedef random_access_iterator_tag                                                            iterator_category;
10853e519524SHoward Hinnant
10863e519524SHoward Hinnantprivate:
1087c003db1fSHoward Hinnant    typedef typename _Cp::__storage_type                                           __storage_type;
1088c003db1fSHoward Hinnant    typedef typename conditional<_IsConst, typename _Cp::__const_storage_pointer,
1089c003db1fSHoward Hinnant                                           typename _Cp::__storage_pointer>::type  __storage_pointer;
1090c003db1fSHoward Hinnant    static const unsigned __bits_per_word = _Cp::__bits_per_word;
10913e519524SHoward Hinnant
10923e519524SHoward Hinnant    __storage_pointer __seg_;
10933e519524SHoward Hinnant    unsigned          __ctz_;
10943e519524SHoward Hinnant
10953e519524SHoward Hinnantpublic:
1096d368a84cSHoward Hinnant    _LIBCPP_INLINE_VISIBILITY __bit_iterator() _NOEXCEPT {}
10973e519524SHoward Hinnant
1098d368a84cSHoward Hinnant    _LIBCPP_INLINE_VISIBILITY
1099c003db1fSHoward Hinnant    __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT
11003e519524SHoward Hinnant        : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {}
11013e519524SHoward Hinnant
1102d368a84cSHoward Hinnant    _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT
1103d368a84cSHoward Hinnant        {return reference(__seg_, __storage_type(1) << __ctz_);}
11043e519524SHoward Hinnant
11053e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator++()
11063e519524SHoward Hinnant    {
11073e519524SHoward Hinnant        if (__ctz_ != __bits_per_word-1)
11083e519524SHoward Hinnant            ++__ctz_;
11093e519524SHoward Hinnant        else
11103e519524SHoward Hinnant        {
11113e519524SHoward Hinnant            __ctz_ = 0;
11123e519524SHoward Hinnant            ++__seg_;
11133e519524SHoward Hinnant        }
11143e519524SHoward Hinnant        return *this;
11153e519524SHoward Hinnant    }
11163e519524SHoward Hinnant
11173e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY __bit_iterator operator++(int)
11183e519524SHoward Hinnant    {
11193e519524SHoward Hinnant        __bit_iterator __tmp = *this;
11203e519524SHoward Hinnant        ++(*this);
11213e519524SHoward Hinnant        return __tmp;
11223e519524SHoward Hinnant    }
11233e519524SHoward Hinnant
11243e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator--()
11253e519524SHoward Hinnant    {
11263e519524SHoward Hinnant        if (__ctz_ != 0)
11273e519524SHoward Hinnant            --__ctz_;
11283e519524SHoward Hinnant        else
11293e519524SHoward Hinnant        {
11303e519524SHoward Hinnant            __ctz_ = __bits_per_word - 1;
11313e519524SHoward Hinnant            --__seg_;
11323e519524SHoward Hinnant        }
11333e519524SHoward Hinnant        return *this;
11343e519524SHoward Hinnant    }
11353e519524SHoward Hinnant
11363e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY __bit_iterator operator--(int)
11373e519524SHoward Hinnant    {
11383e519524SHoward Hinnant        __bit_iterator __tmp = *this;
11393e519524SHoward Hinnant        --(*this);
11403e519524SHoward Hinnant        return __tmp;
11413e519524SHoward Hinnant    }
11423e519524SHoward Hinnant
11433e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator+=(difference_type __n)
11443e519524SHoward Hinnant    {
11453e519524SHoward Hinnant        if (__n >= 0)
11463e519524SHoward Hinnant            __seg_ += (__n + __ctz_) / __bits_per_word;
11473e519524SHoward Hinnant        else
11483e519524SHoward Hinnant            __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1)
11493e519524SHoward Hinnant                    / static_cast<difference_type>(__bits_per_word);
11503e519524SHoward Hinnant        __n &= (__bits_per_word - 1);
11513e519524SHoward Hinnant        __ctz_ = static_cast<unsigned>((__n + __ctz_)  % __bits_per_word);
11523e519524SHoward Hinnant        return *this;
11533e519524SHoward Hinnant    }
11543e519524SHoward Hinnant
11553e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator-=(difference_type __n)
11563e519524SHoward Hinnant    {
11573e519524SHoward Hinnant        return *this += -__n;
11583e519524SHoward Hinnant    }
11593e519524SHoward Hinnant
11603e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY __bit_iterator operator+(difference_type __n) const
11613e519524SHoward Hinnant    {
11623e519524SHoward Hinnant        __bit_iterator __t(*this);
11633e519524SHoward Hinnant        __t += __n;
11643e519524SHoward Hinnant        return __t;
11653e519524SHoward Hinnant    }
11663e519524SHoward Hinnant
11673e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY __bit_iterator operator-(difference_type __n) const
11683e519524SHoward Hinnant    {
11693e519524SHoward Hinnant        __bit_iterator __t(*this);
11703e519524SHoward Hinnant        __t -= __n;
11713e519524SHoward Hinnant        return __t;
11723e519524SHoward Hinnant    }
11733e519524SHoward Hinnant
11743e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY
11753e519524SHoward Hinnant    friend __bit_iterator operator+(difference_type __n, const __bit_iterator& __it) {return __it + __n;}
11763e519524SHoward Hinnant
11773e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY
11783e519524SHoward Hinnant    friend difference_type operator-(const __bit_iterator& __x, const __bit_iterator& __y)
11793e519524SHoward Hinnant        {return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;}
11803e519524SHoward Hinnant
11813e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const {return *(*this + __n);}
11823e519524SHoward Hinnant
11833e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY friend bool operator==(const __bit_iterator& __x, const __bit_iterator& __y)
11843e519524SHoward Hinnant        {return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;}
11853e519524SHoward Hinnant
11863e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY friend bool operator!=(const __bit_iterator& __x, const __bit_iterator& __y)
11873e519524SHoward Hinnant        {return !(__x == __y);}
11883e519524SHoward Hinnant
11893e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY friend bool operator<(const __bit_iterator& __x, const __bit_iterator& __y)
11903e519524SHoward Hinnant        {return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);}
11913e519524SHoward Hinnant
11923e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY friend bool operator>(const __bit_iterator& __x, const __bit_iterator& __y)
11933e519524SHoward Hinnant        {return __y < __x;}
11943e519524SHoward Hinnant
11953e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y)
11963e519524SHoward Hinnant        {return !(__y < __x);}
11973e519524SHoward Hinnant
11983e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y)
11993e519524SHoward Hinnant        {return !(__x < __y);}
12003e519524SHoward Hinnant
12013e519524SHoward Hinnantprivate:
12023e519524SHoward Hinnant    _LIBCPP_INLINE_VISIBILITY
1203d368a84cSHoward Hinnant    __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT
1204d368a84cSHoward Hinnant        : __seg_(__s), __ctz_(__ctz) {}
12053e519524SHoward Hinnant
12063e519524SHoward Hinnant#if defined(__clang__)
1207c003db1fSHoward Hinnant    friend typename _Cp::__self;
12083e519524SHoward Hinnant#else
1209c003db1fSHoward Hinnant    friend class _Cp::__self;
12103e519524SHoward Hinnant#endif
1211c003db1fSHoward Hinnant    friend class __bit_reference<_Cp>;
1212c003db1fSHoward Hinnant    friend class __bit_const_reference<_Cp>;
1213c003db1fSHoward Hinnant    friend class __bit_iterator<_Cp, true>;
1214c003db1fSHoward Hinnant    template <class _Dp> friend struct __bit_array;
1215c003db1fSHoward Hinnant    template <class _Dp> friend void __fill_n_false(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n);
1216c003db1fSHoward Hinnant    template <class _Dp> friend void __fill_n_true(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n);
1217c003db1fSHoward Hinnant    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_aligned(__bit_iterator<_Dp, _IC> __first,
1218c003db1fSHoward Hinnant                                                                                  __bit_iterator<_Dp, _IC> __last,
1219c003db1fSHoward Hinnant                                                                                  __bit_iterator<_Dp, false> __result);
1220c003db1fSHoward Hinnant    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_unaligned(__bit_iterator<_Dp, _IC> __first,
1221c003db1fSHoward Hinnant                                                                                    __bit_iterator<_Dp, _IC> __last,
1222c003db1fSHoward Hinnant                                                                                    __bit_iterator<_Dp, false> __result);
1223c003db1fSHoward Hinnant    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy(__bit_iterator<_Dp, _IC> __first,
1224c003db1fSHoward Hinnant                                                                        __bit_iterator<_Dp, _IC> __last,
1225c003db1fSHoward Hinnant                                                                        __bit_iterator<_Dp, false> __result);
1226c003db1fSHoward Hinnant    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_aligned(__bit_iterator<_Dp, _IC> __first,
1227c003db1fSHoward Hinnant                                                                                           __bit_iterator<_Dp, _IC> __last,
1228c003db1fSHoward Hinnant                                                                                           __bit_iterator<_Dp, false> __result);
1229c003db1fSHoward Hinnant    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_unaligned(__bit_iterator<_Dp, _IC> __first,
1230c003db1fSHoward Hinnant                                                                                             __bit_iterator<_Dp, _IC> __last,
1231c003db1fSHoward Hinnant                                                                                             __bit_iterator<_Dp, false> __result);
1232c003db1fSHoward Hinnant    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy_backward(__bit_iterator<_Dp, _IC> __first,
1233c003db1fSHoward Hinnant                                                                                 __bit_iterator<_Dp, _IC> __last,
1234c003db1fSHoward Hinnant                                                                                 __bit_iterator<_Dp, false> __result);
1235dbe81119SHoward Hinnant    template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_aligned(__bit_iterator<__C1, false>,
1236dbe81119SHoward Hinnant                                                                                           __bit_iterator<__C1, false>,
1237dbe81119SHoward Hinnant                                                                                           __bit_iterator<__C2, false>);
1238dbe81119SHoward Hinnant    template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_unaligned(__bit_iterator<__C1, false>,
1239dbe81119SHoward Hinnant                                                                                             __bit_iterator<__C1, false>,
1240dbe81119SHoward Hinnant                                                                                             __bit_iterator<__C2, false>);
1241dbe81119SHoward Hinnant    template <class __C1, class __C2>friend __bit_iterator<__C2, false> swap_ranges(__bit_iterator<__C1, false>,
1242dbe81119SHoward Hinnant                                                                                 __bit_iterator<__C1, false>,
1243dbe81119SHoward Hinnant                                                                                 __bit_iterator<__C2, false>);
1244c003db1fSHoward Hinnant    template <class _Dp> friend __bit_iterator<_Dp, false> rotate(__bit_iterator<_Dp, false>,
1245c003db1fSHoward Hinnant                                                                __bit_iterator<_Dp, false>,
1246c003db1fSHoward Hinnant                                                                __bit_iterator<_Dp, false>);
12471237dccaSHoward Hinnant    template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_aligned(__bit_iterator<_Dp, _IC1>,
12481237dccaSHoward Hinnant                                                    __bit_iterator<_Dp, _IC1>,
12491237dccaSHoward Hinnant                                                    __bit_iterator<_Dp, _IC2>);
12501237dccaSHoward Hinnant    template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_unaligned(__bit_iterator<_Dp, _IC1>,
12511237dccaSHoward Hinnant                                                      __bit_iterator<_Dp, _IC1>,
12521237dccaSHoward Hinnant                                                      __bit_iterator<_Dp, _IC2>);
1253c003db1fSHoward Hinnant    template <class _Dp, bool _IC1, bool _IC2> friend bool equal(__bit_iterator<_Dp, _IC1>,
1254c003db1fSHoward Hinnant                                                                __bit_iterator<_Dp, _IC1>,
1255c003db1fSHoward Hinnant                                                                __bit_iterator<_Dp, _IC2>);
1256423a8d77SHoward Hinnant    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_true(__bit_iterator<_Dp, _IC>,
1257c003db1fSHoward Hinnant                                                                          typename _Dp::size_type);
1258423a8d77SHoward Hinnant    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_false(__bit_iterator<_Dp, _IC>,
1259c003db1fSHoward Hinnant                                                                           typename _Dp::size_type);
1260423a8d77SHoward Hinnant    template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type
1261423a8d77SHoward Hinnant                   __count_bool_true(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
1262423a8d77SHoward Hinnant    template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type
1263423a8d77SHoward Hinnant                   __count_bool_false(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
12643e519524SHoward Hinnant};
12653e519524SHoward Hinnant
12663e519524SHoward Hinnant_LIBCPP_END_NAMESPACE_STD
12673e519524SHoward Hinnant
12683e519524SHoward Hinnant#endif  // _LIBCPP___BIT_REFERENCE
1269