xref: /freebsd/contrib/llvm-project/libcxx/include/__bit_reference (revision 81ad626541db97eb356e2c1d4a20eb2a26a766ab)
10b57cec5SDimitry Andric// -*- C++ -*-
20b57cec5SDimitry Andric//===----------------------------------------------------------------------===//
30b57cec5SDimitry Andric//
40b57cec5SDimitry Andric// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
50b57cec5SDimitry Andric// See https://llvm.org/LICENSE.txt for license information.
60b57cec5SDimitry Andric// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
70b57cec5SDimitry Andric//
80b57cec5SDimitry Andric//===----------------------------------------------------------------------===//
90b57cec5SDimitry Andric
100b57cec5SDimitry Andric#ifndef _LIBCPP___BIT_REFERENCE
110b57cec5SDimitry Andric#define _LIBCPP___BIT_REFERENCE
120b57cec5SDimitry Andric
13*81ad6265SDimitry Andric#include <__algorithm/min.h>
14e8d8bef9SDimitry Andric#include <__bits>
1504eeddc0SDimitry Andric#include <__config>
16*81ad6265SDimitry Andric#include <__iterator/iterator_traits.h>
17*81ad6265SDimitry Andric#include <__memory/pointer_traits.h>
18*81ad6265SDimitry Andric#include <cstring>
19*81ad6265SDimitry Andric#include <type_traits>
200b57cec5SDimitry Andric
210b57cec5SDimitry Andric#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
220b57cec5SDimitry Andric#  pragma GCC system_header
230b57cec5SDimitry Andric#endif
240b57cec5SDimitry Andric
250b57cec5SDimitry Andric_LIBCPP_PUSH_MACROS
260b57cec5SDimitry Andric#include <__undef_macros>
270b57cec5SDimitry Andric
280b57cec5SDimitry Andric
290b57cec5SDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD
300b57cec5SDimitry Andric
310b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst, typename _Cp::__storage_type = 0> class __bit_iterator;
320b57cec5SDimitry Andrictemplate <class _Cp> class __bit_const_reference;
330b57cec5SDimitry Andric
340b57cec5SDimitry Andrictemplate <class _Tp>
350b57cec5SDimitry Andricstruct __has_storage_type
360b57cec5SDimitry Andric{
370b57cec5SDimitry Andric    static const bool value = false;
380b57cec5SDimitry Andric};
390b57cec5SDimitry Andric
400b57cec5SDimitry Andrictemplate <class _Cp, bool = __has_storage_type<_Cp>::value>
410b57cec5SDimitry Andricclass __bit_reference
420b57cec5SDimitry Andric{
430b57cec5SDimitry Andric    typedef typename _Cp::__storage_type    __storage_type;
440b57cec5SDimitry Andric    typedef typename _Cp::__storage_pointer __storage_pointer;
450b57cec5SDimitry Andric
460b57cec5SDimitry Andric    __storage_pointer __seg_;
470b57cec5SDimitry Andric    __storage_type    __mask_;
480b57cec5SDimitry Andric
490b57cec5SDimitry Andric    friend typename _Cp::__self;
500b57cec5SDimitry Andric
510b57cec5SDimitry Andric    friend class __bit_const_reference<_Cp>;
520b57cec5SDimitry Andric    friend class __bit_iterator<_Cp, false>;
530b57cec5SDimitry Andricpublic:
54480093f4SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
55480093f4SDimitry Andric    __bit_reference(const __bit_reference&) = default;
56480093f4SDimitry Andric
570b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY operator bool() const _NOEXCEPT
580b57cec5SDimitry Andric        {return static_cast<bool>(*__seg_ & __mask_);}
590b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY bool operator ~() const _NOEXCEPT
600b57cec5SDimitry Andric        {return !static_cast<bool>(*this);}
610b57cec5SDimitry Andric
620b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
630b57cec5SDimitry Andric    __bit_reference& operator=(bool __x) _NOEXCEPT
640b57cec5SDimitry Andric    {
650b57cec5SDimitry Andric        if (__x)
660b57cec5SDimitry Andric            *__seg_ |= __mask_;
670b57cec5SDimitry Andric        else
680b57cec5SDimitry Andric            *__seg_ &= ~__mask_;
690b57cec5SDimitry Andric        return *this;
700b57cec5SDimitry Andric    }
710b57cec5SDimitry Andric
72*81ad6265SDimitry Andric#if _LIBCPP_STD_VER > 20
73*81ad6265SDimitry Andric    _LIBCPP_HIDE_FROM_ABI const __bit_reference& operator=(bool __x) const noexcept {
74*81ad6265SDimitry Andric        if (__x)
75*81ad6265SDimitry Andric            *__seg_ |= __mask_;
76*81ad6265SDimitry Andric        else
77*81ad6265SDimitry Andric            *__seg_ &= ~__mask_;
78*81ad6265SDimitry Andric        return *this;
79*81ad6265SDimitry Andric    }
80*81ad6265SDimitry Andric#endif
81*81ad6265SDimitry Andric
820b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
830b57cec5SDimitry Andric    __bit_reference& operator=(const __bit_reference& __x) _NOEXCEPT
840b57cec5SDimitry Andric        {return operator=(static_cast<bool>(__x));}
850b57cec5SDimitry Andric
860b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY void flip() _NOEXCEPT {*__seg_ ^= __mask_;}
870b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, false> operator&() const _NOEXCEPT
880b57cec5SDimitry Andric        {return __bit_iterator<_Cp, false>(__seg_, static_cast<unsigned>(__libcpp_ctz(__mask_)));}
890b57cec5SDimitry Andricprivate:
900b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
91*81ad6265SDimitry Andric    explicit __bit_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT
920b57cec5SDimitry Andric        : __seg_(__s), __mask_(__m) {}
930b57cec5SDimitry Andric};
940b57cec5SDimitry Andric
950b57cec5SDimitry Andrictemplate <class _Cp>
960b57cec5SDimitry Andricclass __bit_reference<_Cp, false>
970b57cec5SDimitry Andric{
980b57cec5SDimitry Andric};
990b57cec5SDimitry Andric
1000b57cec5SDimitry Andrictemplate <class _Cp>
1010b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY
1020b57cec5SDimitry Andricvoid
1030b57cec5SDimitry Andricswap(__bit_reference<_Cp> __x, __bit_reference<_Cp> __y) _NOEXCEPT
1040b57cec5SDimitry Andric{
1050b57cec5SDimitry Andric    bool __t = __x;
1060b57cec5SDimitry Andric    __x = __y;
1070b57cec5SDimitry Andric    __y = __t;
1080b57cec5SDimitry Andric}
1090b57cec5SDimitry Andric
1100b57cec5SDimitry Andrictemplate <class _Cp, class _Dp>
1110b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY
1120b57cec5SDimitry Andricvoid
1130b57cec5SDimitry Andricswap(__bit_reference<_Cp> __x, __bit_reference<_Dp> __y) _NOEXCEPT
1140b57cec5SDimitry Andric{
1150b57cec5SDimitry Andric    bool __t = __x;
1160b57cec5SDimitry Andric    __x = __y;
1170b57cec5SDimitry Andric    __y = __t;
1180b57cec5SDimitry Andric}
1190b57cec5SDimitry Andric
1200b57cec5SDimitry Andrictemplate <class _Cp>
1210b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY
1220b57cec5SDimitry Andricvoid
1230b57cec5SDimitry Andricswap(__bit_reference<_Cp> __x, bool& __y) _NOEXCEPT
1240b57cec5SDimitry Andric{
1250b57cec5SDimitry Andric    bool __t = __x;
1260b57cec5SDimitry Andric    __x = __y;
1270b57cec5SDimitry Andric    __y = __t;
1280b57cec5SDimitry Andric}
1290b57cec5SDimitry Andric
1300b57cec5SDimitry Andrictemplate <class _Cp>
1310b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY
1320b57cec5SDimitry Andricvoid
1330b57cec5SDimitry Andricswap(bool& __x, __bit_reference<_Cp> __y) _NOEXCEPT
1340b57cec5SDimitry Andric{
1350b57cec5SDimitry Andric    bool __t = __x;
1360b57cec5SDimitry Andric    __x = __y;
1370b57cec5SDimitry Andric    __y = __t;
1380b57cec5SDimitry Andric}
1390b57cec5SDimitry Andric
1400b57cec5SDimitry Andrictemplate <class _Cp>
1410b57cec5SDimitry Andricclass __bit_const_reference
1420b57cec5SDimitry Andric{
1430b57cec5SDimitry Andric    typedef typename _Cp::__storage_type          __storage_type;
1440b57cec5SDimitry Andric    typedef typename _Cp::__const_storage_pointer __storage_pointer;
1450b57cec5SDimitry Andric
1460b57cec5SDimitry Andric    __storage_pointer        __seg_;
1470b57cec5SDimitry Andric    __storage_type __mask_;
1480b57cec5SDimitry Andric
1490b57cec5SDimitry Andric    friend typename _Cp::__self;
1500b57cec5SDimitry Andric    friend class __bit_iterator<_Cp, true>;
1510b57cec5SDimitry Andricpublic:
1520b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
153480093f4SDimitry Andric    __bit_const_reference(const __bit_const_reference&) = default;
154480093f4SDimitry Andric
155480093f4SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
1560b57cec5SDimitry Andric    __bit_const_reference(const __bit_reference<_Cp>& __x) _NOEXCEPT
1570b57cec5SDimitry Andric        : __seg_(__x.__seg_), __mask_(__x.__mask_) {}
1580b57cec5SDimitry Andric
1590b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR operator bool() const _NOEXCEPT
1600b57cec5SDimitry Andric        {return static_cast<bool>(*__seg_ & __mask_);}
1610b57cec5SDimitry Andric
1620b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, true> operator&() const _NOEXCEPT
1630b57cec5SDimitry Andric        {return __bit_iterator<_Cp, true>(__seg_, static_cast<unsigned>(__libcpp_ctz(__mask_)));}
1640b57cec5SDimitry Andricprivate:
1650b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
1660b57cec5SDimitry Andric    _LIBCPP_CONSTEXPR
167*81ad6265SDimitry Andric    explicit __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT
1680b57cec5SDimitry Andric        : __seg_(__s), __mask_(__m) {}
1690b57cec5SDimitry Andric
170480093f4SDimitry Andric    __bit_const_reference& operator=(const __bit_const_reference&) = delete;
1710b57cec5SDimitry Andric};
1720b57cec5SDimitry Andric
1730b57cec5SDimitry Andric// find
1740b57cec5SDimitry Andric
1750b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
1760b57cec5SDimitry Andric__bit_iterator<_Cp, _IsConst>
1770b57cec5SDimitry Andric__find_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
1780b57cec5SDimitry Andric{
1790b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, _IsConst> _It;
1800b57cec5SDimitry Andric    typedef typename _It::__storage_type __storage_type;
1810b57cec5SDimitry Andric    static const int __bits_per_word = _It::__bits_per_word;
1820b57cec5SDimitry Andric    // do first partial word
1830b57cec5SDimitry Andric    if (__first.__ctz_ != 0)
1840b57cec5SDimitry Andric    {
1850b57cec5SDimitry Andric        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
1860b57cec5SDimitry Andric        __storage_type __dn = _VSTD::min(__clz_f, __n);
1870b57cec5SDimitry Andric        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
1880b57cec5SDimitry Andric        __storage_type __b = *__first.__seg_ & __m;
1890b57cec5SDimitry Andric        if (__b)
1900b57cec5SDimitry Andric            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b)));
1910b57cec5SDimitry Andric        if (__n == __dn)
1920b57cec5SDimitry Andric            return __first + __n;
1930b57cec5SDimitry Andric        __n -= __dn;
1940b57cec5SDimitry Andric        ++__first.__seg_;
1950b57cec5SDimitry Andric    }
1960b57cec5SDimitry Andric    // do middle whole words
1970b57cec5SDimitry Andric    for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
1980b57cec5SDimitry Andric        if (*__first.__seg_)
1990b57cec5SDimitry Andric            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(*__first.__seg_)));
2000b57cec5SDimitry Andric    // do last partial word
2010b57cec5SDimitry Andric    if (__n > 0)
2020b57cec5SDimitry Andric    {
2030b57cec5SDimitry Andric        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
2040b57cec5SDimitry Andric        __storage_type __b = *__first.__seg_ & __m;
2050b57cec5SDimitry Andric        if (__b)
2060b57cec5SDimitry Andric            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b)));
2070b57cec5SDimitry Andric    }
2080b57cec5SDimitry Andric    return _It(__first.__seg_, static_cast<unsigned>(__n));
2090b57cec5SDimitry Andric}
2100b57cec5SDimitry Andric
2110b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
2120b57cec5SDimitry Andric__bit_iterator<_Cp, _IsConst>
2130b57cec5SDimitry Andric__find_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
2140b57cec5SDimitry Andric{
2150b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, _IsConst> _It;
2160b57cec5SDimitry Andric    typedef typename _It::__storage_type __storage_type;
2170b57cec5SDimitry Andric    const int __bits_per_word = _It::__bits_per_word;
2180b57cec5SDimitry Andric    // do first partial word
2190b57cec5SDimitry Andric    if (__first.__ctz_ != 0)
2200b57cec5SDimitry Andric    {
2210b57cec5SDimitry Andric        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
2220b57cec5SDimitry Andric        __storage_type __dn = _VSTD::min(__clz_f, __n);
2230b57cec5SDimitry Andric        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
2240b57cec5SDimitry Andric        __storage_type __b = ~*__first.__seg_ & __m;
2250b57cec5SDimitry Andric        if (__b)
2260b57cec5SDimitry Andric            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b)));
2270b57cec5SDimitry Andric        if (__n == __dn)
2280b57cec5SDimitry Andric            return __first + __n;
2290b57cec5SDimitry Andric        __n -= __dn;
2300b57cec5SDimitry Andric        ++__first.__seg_;
2310b57cec5SDimitry Andric    }
2320b57cec5SDimitry Andric    // do middle whole words
2330b57cec5SDimitry Andric    for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
2340b57cec5SDimitry Andric    {
2350b57cec5SDimitry Andric        __storage_type __b = ~*__first.__seg_;
2360b57cec5SDimitry Andric        if (__b)
2370b57cec5SDimitry Andric            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b)));
2380b57cec5SDimitry Andric    }
2390b57cec5SDimitry Andric    // do last partial word
2400b57cec5SDimitry Andric    if (__n > 0)
2410b57cec5SDimitry Andric    {
2420b57cec5SDimitry Andric        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
2430b57cec5SDimitry Andric        __storage_type __b = ~*__first.__seg_ & __m;
2440b57cec5SDimitry Andric        if (__b)
2450b57cec5SDimitry Andric            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b)));
2460b57cec5SDimitry Andric    }
2470b57cec5SDimitry Andric    return _It(__first.__seg_, static_cast<unsigned>(__n));
2480b57cec5SDimitry Andric}
2490b57cec5SDimitry Andric
2500b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst, class _Tp>
2510b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY
2520b57cec5SDimitry Andric__bit_iterator<_Cp, _IsConst>
2530b57cec5SDimitry Andricfind(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_)
2540b57cec5SDimitry Andric{
2550b57cec5SDimitry Andric    if (static_cast<bool>(__value_))
256e8d8bef9SDimitry Andric        return _VSTD::__find_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first));
257e8d8bef9SDimitry Andric    return _VSTD::__find_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first));
2580b57cec5SDimitry Andric}
2590b57cec5SDimitry Andric
2600b57cec5SDimitry Andric// count
2610b57cec5SDimitry Andric
2620b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
2630b57cec5SDimitry Andrictypename __bit_iterator<_Cp, _IsConst>::difference_type
2640b57cec5SDimitry Andric__count_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
2650b57cec5SDimitry Andric{
2660b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, _IsConst> _It;
2670b57cec5SDimitry Andric    typedef typename _It::__storage_type __storage_type;
2680b57cec5SDimitry Andric    typedef typename _It::difference_type difference_type;
2690b57cec5SDimitry Andric    const int __bits_per_word = _It::__bits_per_word;
2700b57cec5SDimitry Andric    difference_type __r = 0;
2710b57cec5SDimitry Andric    // do first partial word
2720b57cec5SDimitry Andric    if (__first.__ctz_ != 0)
2730b57cec5SDimitry Andric    {
2740b57cec5SDimitry Andric        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
2750b57cec5SDimitry Andric        __storage_type __dn = _VSTD::min(__clz_f, __n);
2760b57cec5SDimitry Andric        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
2770b57cec5SDimitry Andric        __r = _VSTD::__libcpp_popcount(*__first.__seg_ & __m);
2780b57cec5SDimitry Andric        __n -= __dn;
2790b57cec5SDimitry Andric        ++__first.__seg_;
2800b57cec5SDimitry Andric    }
2810b57cec5SDimitry Andric    // do middle whole words
2820b57cec5SDimitry Andric    for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
2830b57cec5SDimitry Andric        __r += _VSTD::__libcpp_popcount(*__first.__seg_);
2840b57cec5SDimitry Andric    // do last partial word
2850b57cec5SDimitry Andric    if (__n > 0)
2860b57cec5SDimitry Andric    {
2870b57cec5SDimitry Andric        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
2880b57cec5SDimitry Andric        __r += _VSTD::__libcpp_popcount(*__first.__seg_ & __m);
2890b57cec5SDimitry Andric    }
2900b57cec5SDimitry Andric    return __r;
2910b57cec5SDimitry Andric}
2920b57cec5SDimitry Andric
2930b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
2940b57cec5SDimitry Andrictypename __bit_iterator<_Cp, _IsConst>::difference_type
2950b57cec5SDimitry Andric__count_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
2960b57cec5SDimitry Andric{
2970b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, _IsConst> _It;
2980b57cec5SDimitry Andric    typedef typename _It::__storage_type __storage_type;
2990b57cec5SDimitry Andric    typedef typename _It::difference_type difference_type;
3000b57cec5SDimitry Andric    const int __bits_per_word = _It::__bits_per_word;
3010b57cec5SDimitry Andric    difference_type __r = 0;
3020b57cec5SDimitry Andric    // do first partial word
3030b57cec5SDimitry Andric    if (__first.__ctz_ != 0)
3040b57cec5SDimitry Andric    {
3050b57cec5SDimitry Andric        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
3060b57cec5SDimitry Andric        __storage_type __dn = _VSTD::min(__clz_f, __n);
3070b57cec5SDimitry Andric        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
3080b57cec5SDimitry Andric        __r = _VSTD::__libcpp_popcount(~*__first.__seg_ & __m);
3090b57cec5SDimitry Andric        __n -= __dn;
3100b57cec5SDimitry Andric        ++__first.__seg_;
3110b57cec5SDimitry Andric    }
3120b57cec5SDimitry Andric    // do middle whole words
3130b57cec5SDimitry Andric    for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
3140b57cec5SDimitry Andric        __r += _VSTD::__libcpp_popcount(~*__first.__seg_);
3150b57cec5SDimitry Andric    // do last partial word
3160b57cec5SDimitry Andric    if (__n > 0)
3170b57cec5SDimitry Andric    {
3180b57cec5SDimitry Andric        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3190b57cec5SDimitry Andric        __r += _VSTD::__libcpp_popcount(~*__first.__seg_ & __m);
3200b57cec5SDimitry Andric    }
3210b57cec5SDimitry Andric    return __r;
3220b57cec5SDimitry Andric}
3230b57cec5SDimitry Andric
3240b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst, class _Tp>
3250b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY
3260b57cec5SDimitry Andrictypename __bit_iterator<_Cp, _IsConst>::difference_type
3270b57cec5SDimitry Andriccount(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_)
3280b57cec5SDimitry Andric{
3290b57cec5SDimitry Andric    if (static_cast<bool>(__value_))
330e8d8bef9SDimitry Andric        return _VSTD::__count_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first));
331e8d8bef9SDimitry Andric    return _VSTD::__count_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first));
3320b57cec5SDimitry Andric}
3330b57cec5SDimitry Andric
3340b57cec5SDimitry Andric// fill_n
3350b57cec5SDimitry Andric
3360b57cec5SDimitry Andrictemplate <class _Cp>
3370b57cec5SDimitry Andricvoid
3380b57cec5SDimitry Andric__fill_n_false(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n)
3390b57cec5SDimitry Andric{
3400b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, false> _It;
3410b57cec5SDimitry Andric    typedef typename _It::__storage_type __storage_type;
3420b57cec5SDimitry Andric    const int __bits_per_word = _It::__bits_per_word;
3430b57cec5SDimitry Andric    // do first partial word
3440b57cec5SDimitry Andric    if (__first.__ctz_ != 0)
3450b57cec5SDimitry Andric    {
3460b57cec5SDimitry Andric        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
3470b57cec5SDimitry Andric        __storage_type __dn = _VSTD::min(__clz_f, __n);
3480b57cec5SDimitry Andric        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
3490b57cec5SDimitry Andric        *__first.__seg_ &= ~__m;
3500b57cec5SDimitry Andric        __n -= __dn;
3510b57cec5SDimitry Andric        ++__first.__seg_;
3520b57cec5SDimitry Andric    }
3530b57cec5SDimitry Andric    // do middle whole words
3540b57cec5SDimitry Andric    __storage_type __nw = __n / __bits_per_word;
355480093f4SDimitry Andric    _VSTD::memset(_VSTD::__to_address(__first.__seg_), 0, __nw * sizeof(__storage_type));
3560b57cec5SDimitry Andric    __n -= __nw * __bits_per_word;
3570b57cec5SDimitry Andric    // do last partial word
3580b57cec5SDimitry Andric    if (__n > 0)
3590b57cec5SDimitry Andric    {
3600b57cec5SDimitry Andric        __first.__seg_ += __nw;
3610b57cec5SDimitry Andric        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3620b57cec5SDimitry Andric        *__first.__seg_ &= ~__m;
3630b57cec5SDimitry Andric    }
3640b57cec5SDimitry Andric}
3650b57cec5SDimitry Andric
3660b57cec5SDimitry Andrictemplate <class _Cp>
3670b57cec5SDimitry Andricvoid
3680b57cec5SDimitry Andric__fill_n_true(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n)
3690b57cec5SDimitry Andric{
3700b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, false> _It;
3710b57cec5SDimitry Andric    typedef typename _It::__storage_type __storage_type;
3720b57cec5SDimitry Andric    const int __bits_per_word = _It::__bits_per_word;
3730b57cec5SDimitry Andric    // do first partial word
3740b57cec5SDimitry Andric    if (__first.__ctz_ != 0)
3750b57cec5SDimitry Andric    {
3760b57cec5SDimitry Andric        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
3770b57cec5SDimitry Andric        __storage_type __dn = _VSTD::min(__clz_f, __n);
3780b57cec5SDimitry Andric        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
3790b57cec5SDimitry Andric        *__first.__seg_ |= __m;
3800b57cec5SDimitry Andric        __n -= __dn;
3810b57cec5SDimitry Andric        ++__first.__seg_;
3820b57cec5SDimitry Andric    }
3830b57cec5SDimitry Andric    // do middle whole words
3840b57cec5SDimitry Andric    __storage_type __nw = __n / __bits_per_word;
385480093f4SDimitry Andric    _VSTD::memset(_VSTD::__to_address(__first.__seg_), -1, __nw * sizeof(__storage_type));
3860b57cec5SDimitry Andric    __n -= __nw * __bits_per_word;
3870b57cec5SDimitry Andric    // do last partial word
3880b57cec5SDimitry Andric    if (__n > 0)
3890b57cec5SDimitry Andric    {
3900b57cec5SDimitry Andric        __first.__seg_ += __nw;
3910b57cec5SDimitry Andric        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3920b57cec5SDimitry Andric        *__first.__seg_ |= __m;
3930b57cec5SDimitry Andric    }
3940b57cec5SDimitry Andric}
3950b57cec5SDimitry Andric
3960b57cec5SDimitry Andrictemplate <class _Cp>
3970b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY
3980b57cec5SDimitry Andricvoid
3990b57cec5SDimitry Andricfill_n(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n, bool __value_)
4000b57cec5SDimitry Andric{
4010b57cec5SDimitry Andric    if (__n > 0)
4020b57cec5SDimitry Andric    {
4030b57cec5SDimitry Andric        if (__value_)
404e8d8bef9SDimitry Andric            _VSTD::__fill_n_true(__first, __n);
4050b57cec5SDimitry Andric        else
406e8d8bef9SDimitry Andric            _VSTD::__fill_n_false(__first, __n);
4070b57cec5SDimitry Andric    }
4080b57cec5SDimitry Andric}
4090b57cec5SDimitry Andric
4100b57cec5SDimitry Andric// fill
4110b57cec5SDimitry Andric
4120b57cec5SDimitry Andrictemplate <class _Cp>
4130b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY
4140b57cec5SDimitry Andricvoid
4150b57cec5SDimitry Andricfill(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __last, bool __value_)
4160b57cec5SDimitry Andric{
4170b57cec5SDimitry Andric    _VSTD::fill_n(__first, static_cast<typename _Cp::size_type>(__last - __first), __value_);
4180b57cec5SDimitry Andric}
4190b57cec5SDimitry Andric
4200b57cec5SDimitry Andric// copy
4210b57cec5SDimitry Andric
4220b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
4230b57cec5SDimitry Andric__bit_iterator<_Cp, false>
4240b57cec5SDimitry Andric__copy_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
4250b57cec5SDimitry Andric                                                     __bit_iterator<_Cp, false> __result)
4260b57cec5SDimitry Andric{
4270b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, _IsConst> _In;
4280b57cec5SDimitry Andric    typedef  typename _In::difference_type difference_type;
4290b57cec5SDimitry Andric    typedef typename _In::__storage_type __storage_type;
4300b57cec5SDimitry Andric    const int __bits_per_word = _In::__bits_per_word;
4310b57cec5SDimitry Andric    difference_type __n = __last - __first;
4320b57cec5SDimitry Andric    if (__n > 0)
4330b57cec5SDimitry Andric    {
4340b57cec5SDimitry Andric        // do first word
4350b57cec5SDimitry Andric        if (__first.__ctz_ != 0)
4360b57cec5SDimitry Andric        {
4370b57cec5SDimitry Andric            unsigned __clz = __bits_per_word - __first.__ctz_;
4380b57cec5SDimitry Andric            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
4390b57cec5SDimitry Andric            __n -= __dn;
4400b57cec5SDimitry Andric            __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
4410b57cec5SDimitry Andric            __storage_type __b = *__first.__seg_ & __m;
4420b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
4430b57cec5SDimitry Andric            *__result.__seg_ |= __b;
4440b57cec5SDimitry Andric            __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
4450b57cec5SDimitry Andric            __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_)  % __bits_per_word);
4460b57cec5SDimitry Andric            ++__first.__seg_;
4470b57cec5SDimitry Andric            // __first.__ctz_ = 0;
4480b57cec5SDimitry Andric        }
4490b57cec5SDimitry Andric        // __first.__ctz_ == 0;
4500b57cec5SDimitry Andric        // do middle words
4510b57cec5SDimitry Andric        __storage_type __nw = __n / __bits_per_word;
452480093f4SDimitry Andric        _VSTD::memmove(_VSTD::__to_address(__result.__seg_),
453480093f4SDimitry Andric                       _VSTD::__to_address(__first.__seg_),
4540b57cec5SDimitry Andric                       __nw * sizeof(__storage_type));
4550b57cec5SDimitry Andric        __n -= __nw * __bits_per_word;
4560b57cec5SDimitry Andric        __result.__seg_ += __nw;
4570b57cec5SDimitry Andric        // do last word
4580b57cec5SDimitry Andric        if (__n > 0)
4590b57cec5SDimitry Andric        {
4600b57cec5SDimitry Andric            __first.__seg_ += __nw;
4610b57cec5SDimitry Andric            __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
4620b57cec5SDimitry Andric            __storage_type __b = *__first.__seg_ & __m;
4630b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
4640b57cec5SDimitry Andric            *__result.__seg_ |= __b;
4650b57cec5SDimitry Andric            __result.__ctz_ = static_cast<unsigned>(__n);
4660b57cec5SDimitry Andric        }
4670b57cec5SDimitry Andric    }
4680b57cec5SDimitry Andric    return __result;
4690b57cec5SDimitry Andric}
4700b57cec5SDimitry Andric
4710b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
4720b57cec5SDimitry Andric__bit_iterator<_Cp, false>
4730b57cec5SDimitry Andric__copy_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
4740b57cec5SDimitry Andric                                                       __bit_iterator<_Cp, false> __result)
4750b57cec5SDimitry Andric{
4760b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, _IsConst> _In;
4770b57cec5SDimitry Andric    typedef  typename _In::difference_type difference_type;
4780b57cec5SDimitry Andric    typedef typename _In::__storage_type __storage_type;
4790b57cec5SDimitry Andric    static const int __bits_per_word = _In::__bits_per_word;
4800b57cec5SDimitry Andric    difference_type __n = __last - __first;
4810b57cec5SDimitry Andric    if (__n > 0)
4820b57cec5SDimitry Andric    {
4830b57cec5SDimitry Andric        // do first word
4840b57cec5SDimitry Andric        if (__first.__ctz_ != 0)
4850b57cec5SDimitry Andric        {
4860b57cec5SDimitry Andric            unsigned __clz_f = __bits_per_word - __first.__ctz_;
4870b57cec5SDimitry Andric            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
4880b57cec5SDimitry Andric            __n -= __dn;
4890b57cec5SDimitry Andric            __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
4900b57cec5SDimitry Andric            __storage_type __b = *__first.__seg_ & __m;
4910b57cec5SDimitry Andric            unsigned __clz_r = __bits_per_word - __result.__ctz_;
4920b57cec5SDimitry Andric            __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
4930b57cec5SDimitry Andric            __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
4940b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
4950b57cec5SDimitry Andric            if (__result.__ctz_ > __first.__ctz_)
4960b57cec5SDimitry Andric                *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_);
4970b57cec5SDimitry Andric            else
4980b57cec5SDimitry Andric                *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_);
4990b57cec5SDimitry Andric            __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;
5000b57cec5SDimitry Andric            __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_)  % __bits_per_word);
5010b57cec5SDimitry Andric            __dn -= __ddn;
5020b57cec5SDimitry Andric            if (__dn > 0)
5030b57cec5SDimitry Andric            {
5040b57cec5SDimitry Andric                __m = ~__storage_type(0) >> (__bits_per_word - __dn);
5050b57cec5SDimitry Andric                *__result.__seg_ &= ~__m;
5060b57cec5SDimitry Andric                *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn);
5070b57cec5SDimitry Andric                __result.__ctz_ = static_cast<unsigned>(__dn);
5080b57cec5SDimitry Andric            }
5090b57cec5SDimitry Andric            ++__first.__seg_;
5100b57cec5SDimitry Andric            // __first.__ctz_ = 0;
5110b57cec5SDimitry Andric        }
5120b57cec5SDimitry Andric        // __first.__ctz_ == 0;
5130b57cec5SDimitry Andric        // do middle words
5140b57cec5SDimitry Andric        unsigned __clz_r = __bits_per_word - __result.__ctz_;
5150b57cec5SDimitry Andric        __storage_type __m = ~__storage_type(0) << __result.__ctz_;
5160b57cec5SDimitry Andric        for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_)
5170b57cec5SDimitry Andric        {
5180b57cec5SDimitry Andric            __storage_type __b = *__first.__seg_;
5190b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
5200b57cec5SDimitry Andric            *__result.__seg_ |= __b << __result.__ctz_;
5210b57cec5SDimitry Andric            ++__result.__seg_;
5220b57cec5SDimitry Andric            *__result.__seg_ &= __m;
5230b57cec5SDimitry Andric            *__result.__seg_ |= __b >> __clz_r;
5240b57cec5SDimitry Andric        }
5250b57cec5SDimitry Andric        // do last word
5260b57cec5SDimitry Andric        if (__n > 0)
5270b57cec5SDimitry Andric        {
5280b57cec5SDimitry Andric            __m = ~__storage_type(0) >> (__bits_per_word - __n);
5290b57cec5SDimitry Andric            __storage_type __b = *__first.__seg_ & __m;
5300b57cec5SDimitry Andric            __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r));
5310b57cec5SDimitry Andric            __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
5320b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
5330b57cec5SDimitry Andric            *__result.__seg_ |= __b << __result.__ctz_;
5340b57cec5SDimitry Andric            __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
5350b57cec5SDimitry Andric            __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_)  % __bits_per_word);
5360b57cec5SDimitry Andric            __n -= __dn;
5370b57cec5SDimitry Andric            if (__n > 0)
5380b57cec5SDimitry Andric            {
5390b57cec5SDimitry Andric                __m = ~__storage_type(0) >> (__bits_per_word - __n);
5400b57cec5SDimitry Andric                *__result.__seg_ &= ~__m;
5410b57cec5SDimitry Andric                *__result.__seg_ |= __b >> __dn;
5420b57cec5SDimitry Andric                __result.__ctz_ = static_cast<unsigned>(__n);
5430b57cec5SDimitry Andric            }
5440b57cec5SDimitry Andric        }
5450b57cec5SDimitry Andric    }
5460b57cec5SDimitry Andric    return __result;
5470b57cec5SDimitry Andric}
5480b57cec5SDimitry Andric
5490b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
5500b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY
5510b57cec5SDimitry Andric__bit_iterator<_Cp, false>
5520b57cec5SDimitry Andriccopy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
5530b57cec5SDimitry Andric{
5540b57cec5SDimitry Andric    if (__first.__ctz_ == __result.__ctz_)
555e8d8bef9SDimitry Andric        return _VSTD::__copy_aligned(__first, __last, __result);
556e8d8bef9SDimitry Andric    return _VSTD::__copy_unaligned(__first, __last, __result);
5570b57cec5SDimitry Andric}
5580b57cec5SDimitry Andric
5590b57cec5SDimitry Andric// copy_backward
5600b57cec5SDimitry Andric
5610b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
5620b57cec5SDimitry Andric__bit_iterator<_Cp, false>
5630b57cec5SDimitry Andric__copy_backward_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
5640b57cec5SDimitry Andric                                                     __bit_iterator<_Cp, false> __result)
5650b57cec5SDimitry Andric{
5660b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, _IsConst> _In;
5670b57cec5SDimitry Andric    typedef  typename _In::difference_type difference_type;
5680b57cec5SDimitry Andric    typedef typename _In::__storage_type __storage_type;
5690b57cec5SDimitry Andric    const int __bits_per_word = _In::__bits_per_word;
5700b57cec5SDimitry Andric    difference_type __n = __last - __first;
5710b57cec5SDimitry Andric    if (__n > 0)
5720b57cec5SDimitry Andric    {
5730b57cec5SDimitry Andric        // do first word
5740b57cec5SDimitry Andric        if (__last.__ctz_ != 0)
5750b57cec5SDimitry Andric        {
5760b57cec5SDimitry Andric            difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n);
5770b57cec5SDimitry Andric            __n -= __dn;
5780b57cec5SDimitry Andric            unsigned __clz = __bits_per_word - __last.__ctz_;
5790b57cec5SDimitry Andric            __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz);
5800b57cec5SDimitry Andric            __storage_type __b = *__last.__seg_ & __m;
5810b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
5820b57cec5SDimitry Andric            *__result.__seg_ |= __b;
5830b57cec5SDimitry Andric            __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) +
5840b57cec5SDimitry Andric                                                       __result.__ctz_)  % __bits_per_word);
5850b57cec5SDimitry Andric            // __last.__ctz_ = 0
5860b57cec5SDimitry Andric         }
5870b57cec5SDimitry Andric        // __last.__ctz_ == 0 || __n == 0
5880b57cec5SDimitry Andric        // __result.__ctz_ == 0 || __n == 0
5890b57cec5SDimitry Andric        // do middle words
5900b57cec5SDimitry Andric        __storage_type __nw = __n / __bits_per_word;
5910b57cec5SDimitry Andric        __result.__seg_ -= __nw;
5920b57cec5SDimitry Andric        __last.__seg_ -= __nw;
593480093f4SDimitry Andric        _VSTD::memmove(_VSTD::__to_address(__result.__seg_),
594480093f4SDimitry Andric                       _VSTD::__to_address(__last.__seg_),
5950b57cec5SDimitry Andric                       __nw * sizeof(__storage_type));
5960b57cec5SDimitry Andric        __n -= __nw * __bits_per_word;
5970b57cec5SDimitry Andric        // do last word
5980b57cec5SDimitry Andric        if (__n > 0)
5990b57cec5SDimitry Andric        {
6000b57cec5SDimitry Andric            __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n);
6010b57cec5SDimitry Andric            __storage_type __b = *--__last.__seg_ & __m;
6020b57cec5SDimitry Andric            *--__result.__seg_ &= ~__m;
6030b57cec5SDimitry Andric            *__result.__seg_ |= __b;
6040b57cec5SDimitry Andric            __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));
6050b57cec5SDimitry Andric        }
6060b57cec5SDimitry Andric    }
6070b57cec5SDimitry Andric    return __result;
6080b57cec5SDimitry Andric}
6090b57cec5SDimitry Andric
6100b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
6110b57cec5SDimitry Andric__bit_iterator<_Cp, false>
6120b57cec5SDimitry Andric__copy_backward_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
6130b57cec5SDimitry Andric                                                       __bit_iterator<_Cp, false> __result)
6140b57cec5SDimitry Andric{
6150b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, _IsConst> _In;
6160b57cec5SDimitry Andric    typedef  typename _In::difference_type difference_type;
6170b57cec5SDimitry Andric    typedef typename _In::__storage_type __storage_type;
6180b57cec5SDimitry Andric    const int __bits_per_word = _In::__bits_per_word;
6190b57cec5SDimitry Andric    difference_type __n = __last - __first;
6200b57cec5SDimitry Andric    if (__n > 0)
6210b57cec5SDimitry Andric    {
6220b57cec5SDimitry Andric        // do first word
6230b57cec5SDimitry Andric        if (__last.__ctz_ != 0)
6240b57cec5SDimitry Andric        {
6250b57cec5SDimitry Andric            difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n);
6260b57cec5SDimitry Andric            __n -= __dn;
6270b57cec5SDimitry Andric            unsigned __clz_l = __bits_per_word - __last.__ctz_;
6280b57cec5SDimitry Andric            __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l);
6290b57cec5SDimitry Andric            __storage_type __b = *__last.__seg_ & __m;
6300b57cec5SDimitry Andric            unsigned __clz_r = __bits_per_word - __result.__ctz_;
6310b57cec5SDimitry Andric            __storage_type __ddn = _VSTD::min(__dn, static_cast<difference_type>(__result.__ctz_));
6320b57cec5SDimitry Andric            if (__ddn > 0)
6330b57cec5SDimitry Andric            {
6340b57cec5SDimitry Andric                __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r);
6350b57cec5SDimitry Andric                *__result.__seg_ &= ~__m;
6360b57cec5SDimitry Andric                if (__result.__ctz_ > __last.__ctz_)
6370b57cec5SDimitry Andric                    *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);
6380b57cec5SDimitry Andric                else
6390b57cec5SDimitry Andric                    *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_);
6400b57cec5SDimitry Andric                __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) +
6410b57cec5SDimitry Andric                                                         __result.__ctz_)  % __bits_per_word);
6420b57cec5SDimitry Andric                __dn -= __ddn;
6430b57cec5SDimitry Andric            }
6440b57cec5SDimitry Andric            if (__dn > 0)
6450b57cec5SDimitry Andric            {
6460b57cec5SDimitry Andric                // __result.__ctz_ == 0
6470b57cec5SDimitry Andric                --__result.__seg_;
6480b57cec5SDimitry Andric                __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1));
6490b57cec5SDimitry Andric                __m = ~__storage_type(0) << __result.__ctz_;
6500b57cec5SDimitry Andric                *__result.__seg_ &= ~__m;
6510b57cec5SDimitry Andric                __last.__ctz_ -= __dn + __ddn;
6520b57cec5SDimitry Andric                *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);
6530b57cec5SDimitry Andric            }
6540b57cec5SDimitry Andric            // __last.__ctz_ = 0
6550b57cec5SDimitry Andric         }
6560b57cec5SDimitry Andric        // __last.__ctz_ == 0 || __n == 0
6570b57cec5SDimitry Andric        // __result.__ctz_ != 0 || __n == 0
6580b57cec5SDimitry Andric        // do middle words
6590b57cec5SDimitry Andric        unsigned __clz_r = __bits_per_word - __result.__ctz_;
6600b57cec5SDimitry Andric        __storage_type __m = ~__storage_type(0) >> __clz_r;
6610b57cec5SDimitry Andric        for (; __n >= __bits_per_word; __n -= __bits_per_word)
6620b57cec5SDimitry Andric        {
6630b57cec5SDimitry Andric            __storage_type __b = *--__last.__seg_;
6640b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
6650b57cec5SDimitry Andric            *__result.__seg_ |= __b >> __clz_r;
6660b57cec5SDimitry Andric            *--__result.__seg_ &= __m;
6670b57cec5SDimitry Andric            *__result.__seg_ |= __b << __result.__ctz_;
6680b57cec5SDimitry Andric        }
6690b57cec5SDimitry Andric        // do last word
6700b57cec5SDimitry Andric        if (__n > 0)
6710b57cec5SDimitry Andric        {
6720b57cec5SDimitry Andric            __m = ~__storage_type(0) << (__bits_per_word - __n);
6730b57cec5SDimitry Andric            __storage_type __b = *--__last.__seg_ & __m;
6740b57cec5SDimitry Andric            __clz_r = __bits_per_word - __result.__ctz_;
6750b57cec5SDimitry Andric            __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__result.__ctz_));
6760b57cec5SDimitry Andric            __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r);
6770b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
6780b57cec5SDimitry Andric            *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_);
6790b57cec5SDimitry Andric            __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) +
6800b57cec5SDimitry Andric                                                     __result.__ctz_)  % __bits_per_word);
6810b57cec5SDimitry Andric            __n -= __dn;
6820b57cec5SDimitry Andric            if (__n > 0)
6830b57cec5SDimitry Andric            {
6840b57cec5SDimitry Andric                // __result.__ctz_ == 0
6850b57cec5SDimitry Andric                --__result.__seg_;
6860b57cec5SDimitry Andric                __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));
6870b57cec5SDimitry Andric                __m = ~__storage_type(0) << __result.__ctz_;
6880b57cec5SDimitry Andric                *__result.__seg_ &= ~__m;
6890b57cec5SDimitry Andric                *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn));
6900b57cec5SDimitry Andric            }
6910b57cec5SDimitry Andric        }
6920b57cec5SDimitry Andric    }
6930b57cec5SDimitry Andric    return __result;
6940b57cec5SDimitry Andric}
6950b57cec5SDimitry Andric
6960b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
6970b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY
6980b57cec5SDimitry Andric__bit_iterator<_Cp, false>
6990b57cec5SDimitry Andriccopy_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
7000b57cec5SDimitry Andric{
7010b57cec5SDimitry Andric    if (__last.__ctz_ == __result.__ctz_)
702e8d8bef9SDimitry Andric        return _VSTD::__copy_backward_aligned(__first, __last, __result);
703e8d8bef9SDimitry Andric    return _VSTD::__copy_backward_unaligned(__first, __last, __result);
7040b57cec5SDimitry Andric}
7050b57cec5SDimitry Andric
7060b57cec5SDimitry Andric// move
7070b57cec5SDimitry Andric
7080b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
7090b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY
7100b57cec5SDimitry Andric__bit_iterator<_Cp, false>
7110b57cec5SDimitry Andricmove(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
7120b57cec5SDimitry Andric{
7130b57cec5SDimitry Andric    return _VSTD::copy(__first, __last, __result);
7140b57cec5SDimitry Andric}
7150b57cec5SDimitry Andric
7160b57cec5SDimitry Andric// move_backward
7170b57cec5SDimitry Andric
7180b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
7190b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY
7200b57cec5SDimitry Andric__bit_iterator<_Cp, false>
7210b57cec5SDimitry Andricmove_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
7220b57cec5SDimitry Andric{
7230b57cec5SDimitry Andric    return _VSTD::copy_backward(__first, __last, __result);
7240b57cec5SDimitry Andric}
7250b57cec5SDimitry Andric
7260b57cec5SDimitry Andric// swap_ranges
7270b57cec5SDimitry Andric
7280b57cec5SDimitry Andrictemplate <class __C1, class __C2>
7290b57cec5SDimitry Andric__bit_iterator<__C2, false>
7300b57cec5SDimitry Andric__swap_ranges_aligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last,
7310b57cec5SDimitry Andric                      __bit_iterator<__C2, false> __result)
7320b57cec5SDimitry Andric{
7330b57cec5SDimitry Andric    typedef __bit_iterator<__C1, false> _I1;
7340b57cec5SDimitry Andric    typedef  typename _I1::difference_type difference_type;
7350b57cec5SDimitry Andric    typedef typename _I1::__storage_type __storage_type;
7360b57cec5SDimitry Andric    const int __bits_per_word = _I1::__bits_per_word;
7370b57cec5SDimitry Andric    difference_type __n = __last - __first;
7380b57cec5SDimitry Andric    if (__n > 0)
7390b57cec5SDimitry Andric    {
7400b57cec5SDimitry Andric        // do first word
7410b57cec5SDimitry Andric        if (__first.__ctz_ != 0)
7420b57cec5SDimitry Andric        {
7430b57cec5SDimitry Andric            unsigned __clz = __bits_per_word - __first.__ctz_;
7440b57cec5SDimitry Andric            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
7450b57cec5SDimitry Andric            __n -= __dn;
7460b57cec5SDimitry Andric            __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
7470b57cec5SDimitry Andric            __storage_type __b1 = *__first.__seg_ & __m;
7480b57cec5SDimitry Andric            *__first.__seg_ &= ~__m;
7490b57cec5SDimitry Andric            __storage_type __b2 = *__result.__seg_ & __m;
7500b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
7510b57cec5SDimitry Andric            *__result.__seg_ |= __b1;
7520b57cec5SDimitry Andric            *__first.__seg_  |= __b2;
7530b57cec5SDimitry Andric            __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
7540b57cec5SDimitry Andric            __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_)  % __bits_per_word);
7550b57cec5SDimitry Andric            ++__first.__seg_;
7560b57cec5SDimitry Andric            // __first.__ctz_ = 0;
7570b57cec5SDimitry Andric        }
7580b57cec5SDimitry Andric        // __first.__ctz_ == 0;
7590b57cec5SDimitry Andric        // do middle words
7600b57cec5SDimitry Andric        for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_)
7610b57cec5SDimitry Andric            swap(*__first.__seg_, *__result.__seg_);
7620b57cec5SDimitry Andric        // do last word
7630b57cec5SDimitry Andric        if (__n > 0)
7640b57cec5SDimitry Andric        {
7650b57cec5SDimitry Andric            __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
7660b57cec5SDimitry Andric            __storage_type __b1 = *__first.__seg_ & __m;
7670b57cec5SDimitry Andric            *__first.__seg_ &= ~__m;
7680b57cec5SDimitry Andric            __storage_type __b2 = *__result.__seg_ & __m;
7690b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
7700b57cec5SDimitry Andric            *__result.__seg_ |= __b1;
7710b57cec5SDimitry Andric            *__first.__seg_  |= __b2;
7720b57cec5SDimitry Andric            __result.__ctz_ = static_cast<unsigned>(__n);
7730b57cec5SDimitry Andric        }
7740b57cec5SDimitry Andric    }
7750b57cec5SDimitry Andric    return __result;
7760b57cec5SDimitry Andric}
7770b57cec5SDimitry Andric
7780b57cec5SDimitry Andrictemplate <class __C1, class __C2>
7790b57cec5SDimitry Andric__bit_iterator<__C2, false>
7800b57cec5SDimitry Andric__swap_ranges_unaligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last,
7810b57cec5SDimitry Andric                        __bit_iterator<__C2, false> __result)
7820b57cec5SDimitry Andric{
7830b57cec5SDimitry Andric    typedef __bit_iterator<__C1, false> _I1;
7840b57cec5SDimitry Andric    typedef  typename _I1::difference_type difference_type;
7850b57cec5SDimitry Andric    typedef typename _I1::__storage_type __storage_type;
7860b57cec5SDimitry Andric    const int __bits_per_word = _I1::__bits_per_word;
7870b57cec5SDimitry Andric    difference_type __n = __last - __first;
7880b57cec5SDimitry Andric    if (__n > 0)
7890b57cec5SDimitry Andric    {
7900b57cec5SDimitry Andric        // do first word
7910b57cec5SDimitry Andric        if (__first.__ctz_ != 0)
7920b57cec5SDimitry Andric        {
7930b57cec5SDimitry Andric            unsigned __clz_f = __bits_per_word - __first.__ctz_;
7940b57cec5SDimitry Andric            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
7950b57cec5SDimitry Andric            __n -= __dn;
7960b57cec5SDimitry Andric            __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
7970b57cec5SDimitry Andric            __storage_type __b1 = *__first.__seg_ & __m;
7980b57cec5SDimitry Andric            *__first.__seg_ &= ~__m;
7990b57cec5SDimitry Andric            unsigned __clz_r = __bits_per_word - __result.__ctz_;
8000b57cec5SDimitry Andric            __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
8010b57cec5SDimitry Andric            __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
8020b57cec5SDimitry Andric            __storage_type __b2 = *__result.__seg_ & __m;
8030b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
8040b57cec5SDimitry Andric            if (__result.__ctz_ > __first.__ctz_)
8050b57cec5SDimitry Andric            {
8060b57cec5SDimitry Andric                unsigned __s = __result.__ctz_ - __first.__ctz_;
8070b57cec5SDimitry Andric                *__result.__seg_ |= __b1 << __s;
8080b57cec5SDimitry Andric                *__first.__seg_  |= __b2 >> __s;
8090b57cec5SDimitry Andric            }
8100b57cec5SDimitry Andric            else
8110b57cec5SDimitry Andric            {
8120b57cec5SDimitry Andric                unsigned __s = __first.__ctz_ - __result.__ctz_;
8130b57cec5SDimitry Andric                *__result.__seg_ |= __b1 >> __s;
8140b57cec5SDimitry Andric                *__first.__seg_  |= __b2 << __s;
8150b57cec5SDimitry Andric            }
8160b57cec5SDimitry Andric            __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;
8170b57cec5SDimitry Andric            __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_)  % __bits_per_word);
8180b57cec5SDimitry Andric            __dn -= __ddn;
8190b57cec5SDimitry Andric            if (__dn > 0)
8200b57cec5SDimitry Andric            {
8210b57cec5SDimitry Andric                __m = ~__storage_type(0) >> (__bits_per_word - __dn);
8220b57cec5SDimitry Andric                __b2 = *__result.__seg_ & __m;
8230b57cec5SDimitry Andric                *__result.__seg_ &= ~__m;
8240b57cec5SDimitry Andric                unsigned __s = __first.__ctz_ + __ddn;
8250b57cec5SDimitry Andric                *__result.__seg_ |= __b1 >> __s;
8260b57cec5SDimitry Andric                *__first.__seg_  |= __b2 << __s;
8270b57cec5SDimitry Andric                __result.__ctz_ = static_cast<unsigned>(__dn);
8280b57cec5SDimitry Andric            }
8290b57cec5SDimitry Andric            ++__first.__seg_;
8300b57cec5SDimitry Andric            // __first.__ctz_ = 0;
8310b57cec5SDimitry Andric        }
8320b57cec5SDimitry Andric        // __first.__ctz_ == 0;
8330b57cec5SDimitry Andric        // do middle words
8340b57cec5SDimitry Andric        __storage_type __m = ~__storage_type(0) << __result.__ctz_;
8350b57cec5SDimitry Andric        unsigned __clz_r = __bits_per_word - __result.__ctz_;
8360b57cec5SDimitry Andric        for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_)
8370b57cec5SDimitry Andric        {
8380b57cec5SDimitry Andric            __storage_type __b1 = *__first.__seg_;
8390b57cec5SDimitry Andric            __storage_type __b2 = *__result.__seg_ & __m;
8400b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
8410b57cec5SDimitry Andric            *__result.__seg_ |= __b1 << __result.__ctz_;
8420b57cec5SDimitry Andric            *__first.__seg_  = __b2 >> __result.__ctz_;
8430b57cec5SDimitry Andric            ++__result.__seg_;
8440b57cec5SDimitry Andric            __b2 = *__result.__seg_ & ~__m;
8450b57cec5SDimitry Andric            *__result.__seg_ &= __m;
8460b57cec5SDimitry Andric            *__result.__seg_ |= __b1 >> __clz_r;
8470b57cec5SDimitry Andric            *__first.__seg_  |= __b2 << __clz_r;
8480b57cec5SDimitry Andric        }
8490b57cec5SDimitry Andric        // do last word
8500b57cec5SDimitry Andric        if (__n > 0)
8510b57cec5SDimitry Andric        {
8520b57cec5SDimitry Andric            __m = ~__storage_type(0) >> (__bits_per_word - __n);
8530b57cec5SDimitry Andric            __storage_type __b1 = *__first.__seg_ & __m;
8540b57cec5SDimitry Andric            *__first.__seg_ &= ~__m;
8550b57cec5SDimitry Andric            __storage_type __dn = _VSTD::min<__storage_type>(__n, __clz_r);
8560b57cec5SDimitry Andric            __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
8570b57cec5SDimitry Andric            __storage_type __b2 = *__result.__seg_ & __m;
8580b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
8590b57cec5SDimitry Andric            *__result.__seg_ |= __b1 << __result.__ctz_;
8600b57cec5SDimitry Andric            *__first.__seg_  |= __b2 >> __result.__ctz_;
8610b57cec5SDimitry Andric            __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
8620b57cec5SDimitry Andric            __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_)  % __bits_per_word);
8630b57cec5SDimitry Andric            __n -= __dn;
8640b57cec5SDimitry Andric            if (__n > 0)
8650b57cec5SDimitry Andric            {
8660b57cec5SDimitry Andric                __m = ~__storage_type(0) >> (__bits_per_word - __n);
8670b57cec5SDimitry Andric                __b2 = *__result.__seg_ & __m;
8680b57cec5SDimitry Andric                *__result.__seg_ &= ~__m;
8690b57cec5SDimitry Andric                *__result.__seg_ |= __b1 >> __dn;
8700b57cec5SDimitry Andric                *__first.__seg_  |= __b2 << __dn;
8710b57cec5SDimitry Andric                __result.__ctz_ = static_cast<unsigned>(__n);
8720b57cec5SDimitry Andric            }
8730b57cec5SDimitry Andric        }
8740b57cec5SDimitry Andric    }
8750b57cec5SDimitry Andric    return __result;
8760b57cec5SDimitry Andric}
8770b57cec5SDimitry Andric
8780b57cec5SDimitry Andrictemplate <class __C1, class __C2>
8790b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY
8800b57cec5SDimitry Andric__bit_iterator<__C2, false>
8810b57cec5SDimitry Andricswap_ranges(__bit_iterator<__C1, false> __first1, __bit_iterator<__C1, false> __last1,
8820b57cec5SDimitry Andric            __bit_iterator<__C2, false> __first2)
8830b57cec5SDimitry Andric{
8840b57cec5SDimitry Andric    if (__first1.__ctz_ == __first2.__ctz_)
885e8d8bef9SDimitry Andric        return _VSTD::__swap_ranges_aligned(__first1, __last1, __first2);
886e8d8bef9SDimitry Andric    return _VSTD::__swap_ranges_unaligned(__first1, __last1, __first2);
8870b57cec5SDimitry Andric}
8880b57cec5SDimitry Andric
8890b57cec5SDimitry Andric// rotate
8900b57cec5SDimitry Andric
8910b57cec5SDimitry Andrictemplate <class _Cp>
8920b57cec5SDimitry Andricstruct __bit_array
8930b57cec5SDimitry Andric{
8940b57cec5SDimitry Andric    typedef typename _Cp::difference_type difference_type;
8950b57cec5SDimitry Andric    typedef typename _Cp::__storage_type  __storage_type;
8960b57cec5SDimitry Andric    typedef typename _Cp::__storage_pointer __storage_pointer;
8970b57cec5SDimitry Andric    typedef typename _Cp::iterator        iterator;
8980b57cec5SDimitry Andric    static const unsigned __bits_per_word = _Cp::__bits_per_word;
8990b57cec5SDimitry Andric    static const unsigned _Np = 4;
9000b57cec5SDimitry Andric
9010b57cec5SDimitry Andric    difference_type __size_;
9020b57cec5SDimitry Andric    __storage_type __word_[_Np];
9030b57cec5SDimitry Andric
9040b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY static difference_type capacity()
9050b57cec5SDimitry Andric        {return static_cast<difference_type>(_Np * __bits_per_word);}
9060b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY explicit __bit_array(difference_type __s) : __size_(__s) {}
9070b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY iterator begin()
9080b57cec5SDimitry Andric    {
9090b57cec5SDimitry Andric        return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]), 0);
9100b57cec5SDimitry Andric    }
9110b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY iterator end()
9120b57cec5SDimitry Andric    {
9130b57cec5SDimitry Andric        return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]) + __size_ / __bits_per_word,
9140b57cec5SDimitry Andric                                                  static_cast<unsigned>(__size_ % __bits_per_word));
9150b57cec5SDimitry Andric    }
9160b57cec5SDimitry Andric};
9170b57cec5SDimitry Andric
9180b57cec5SDimitry Andrictemplate <class _Cp>
9190b57cec5SDimitry Andric__bit_iterator<_Cp, false>
9200b57cec5SDimitry Andricrotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last)
9210b57cec5SDimitry Andric{
9220b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, false> _I1;
9230b57cec5SDimitry Andric    typedef  typename _I1::difference_type difference_type;
9240b57cec5SDimitry Andric    difference_type __d1 = __middle - __first;
9250b57cec5SDimitry Andric    difference_type __d2 = __last - __middle;
9260b57cec5SDimitry Andric    _I1 __r = __first + __d2;
9270b57cec5SDimitry Andric    while (__d1 != 0 && __d2 != 0)
9280b57cec5SDimitry Andric    {
9290b57cec5SDimitry Andric        if (__d1 <= __d2)
9300b57cec5SDimitry Andric        {
9310b57cec5SDimitry Andric            if (__d1 <= __bit_array<_Cp>::capacity())
9320b57cec5SDimitry Andric            {
9330b57cec5SDimitry Andric                __bit_array<_Cp> __b(__d1);
9340b57cec5SDimitry Andric                _VSTD::copy(__first, __middle, __b.begin());
9350b57cec5SDimitry Andric                _VSTD::copy(__b.begin(), __b.end(), _VSTD::copy(__middle, __last, __first));
9360b57cec5SDimitry Andric                break;
9370b57cec5SDimitry Andric            }
9380b57cec5SDimitry Andric            else
9390b57cec5SDimitry Andric            {
9400b57cec5SDimitry Andric                __bit_iterator<_Cp, false> __mp = _VSTD::swap_ranges(__first, __middle, __middle);
9410b57cec5SDimitry Andric                __first = __middle;
9420b57cec5SDimitry Andric                __middle = __mp;
9430b57cec5SDimitry Andric                __d2 -= __d1;
9440b57cec5SDimitry Andric            }
9450b57cec5SDimitry Andric        }
9460b57cec5SDimitry Andric        else
9470b57cec5SDimitry Andric        {
9480b57cec5SDimitry Andric            if (__d2 <= __bit_array<_Cp>::capacity())
9490b57cec5SDimitry Andric            {
9500b57cec5SDimitry Andric                __bit_array<_Cp> __b(__d2);
9510b57cec5SDimitry Andric                _VSTD::copy(__middle, __last, __b.begin());
9520b57cec5SDimitry Andric                _VSTD::copy_backward(__b.begin(), __b.end(), _VSTD::copy_backward(__first, __middle, __last));
9530b57cec5SDimitry Andric                break;
9540b57cec5SDimitry Andric            }
9550b57cec5SDimitry Andric            else
9560b57cec5SDimitry Andric            {
9570b57cec5SDimitry Andric                __bit_iterator<_Cp, false> __mp = __first + __d2;
9580b57cec5SDimitry Andric                _VSTD::swap_ranges(__first, __mp, __middle);
9590b57cec5SDimitry Andric                __first = __mp;
9600b57cec5SDimitry Andric                __d1 -= __d2;
9610b57cec5SDimitry Andric            }
9620b57cec5SDimitry Andric        }
9630b57cec5SDimitry Andric    }
9640b57cec5SDimitry Andric    return __r;
9650b57cec5SDimitry Andric}
9660b57cec5SDimitry Andric
9670b57cec5SDimitry Andric// equal
9680b57cec5SDimitry Andric
9690b57cec5SDimitry Andrictemplate <class _Cp, bool _IC1, bool _IC2>
9700b57cec5SDimitry Andricbool
9710b57cec5SDimitry Andric__equal_unaligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1,
9720b57cec5SDimitry Andric                  __bit_iterator<_Cp, _IC2> __first2)
9730b57cec5SDimitry Andric{
9740b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, _IC1> _It;
9750b57cec5SDimitry Andric    typedef  typename _It::difference_type difference_type;
9760b57cec5SDimitry Andric    typedef typename _It::__storage_type __storage_type;
9770b57cec5SDimitry Andric    static const int __bits_per_word = _It::__bits_per_word;
9780b57cec5SDimitry Andric    difference_type __n = __last1 - __first1;
9790b57cec5SDimitry Andric    if (__n > 0)
9800b57cec5SDimitry Andric    {
9810b57cec5SDimitry Andric        // do first word
9820b57cec5SDimitry Andric        if (__first1.__ctz_ != 0)
9830b57cec5SDimitry Andric        {
9840b57cec5SDimitry Andric            unsigned __clz_f = __bits_per_word - __first1.__ctz_;
9850b57cec5SDimitry Andric            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
9860b57cec5SDimitry Andric            __n -= __dn;
9870b57cec5SDimitry Andric            __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
9880b57cec5SDimitry Andric            __storage_type __b = *__first1.__seg_ & __m;
9890b57cec5SDimitry Andric            unsigned __clz_r = __bits_per_word - __first2.__ctz_;
9900b57cec5SDimitry Andric            __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
9910b57cec5SDimitry Andric            __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
9920b57cec5SDimitry Andric            if (__first2.__ctz_ > __first1.__ctz_)
9930b57cec5SDimitry Andric            {
9940b57cec5SDimitry Andric                if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_)))
9950b57cec5SDimitry Andric                    return false;
9960b57cec5SDimitry Andric            }
9970b57cec5SDimitry Andric            else
9980b57cec5SDimitry Andric            {
9990b57cec5SDimitry Andric                if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_)))
10000b57cec5SDimitry Andric                    return false;
10010b57cec5SDimitry Andric            }
10020b57cec5SDimitry Andric            __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word;
10030b57cec5SDimitry Andric            __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_)  % __bits_per_word);
10040b57cec5SDimitry Andric            __dn -= __ddn;
10050b57cec5SDimitry Andric            if (__dn > 0)
10060b57cec5SDimitry Andric            {
10070b57cec5SDimitry Andric                __m = ~__storage_type(0) >> (__bits_per_word - __dn);
10080b57cec5SDimitry Andric                if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn)))
10090b57cec5SDimitry Andric                    return false;
10100b57cec5SDimitry Andric                __first2.__ctz_ = static_cast<unsigned>(__dn);
10110b57cec5SDimitry Andric            }
10120b57cec5SDimitry Andric            ++__first1.__seg_;
10130b57cec5SDimitry Andric            // __first1.__ctz_ = 0;
10140b57cec5SDimitry Andric        }
10150b57cec5SDimitry Andric        // __first1.__ctz_ == 0;
10160b57cec5SDimitry Andric        // do middle words
10170b57cec5SDimitry Andric        unsigned __clz_r = __bits_per_word - __first2.__ctz_;
10180b57cec5SDimitry Andric        __storage_type __m = ~__storage_type(0) << __first2.__ctz_;
10190b57cec5SDimitry Andric        for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_)
10200b57cec5SDimitry Andric        {
10210b57cec5SDimitry Andric            __storage_type __b = *__first1.__seg_;
10220b57cec5SDimitry Andric            if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_))
10230b57cec5SDimitry Andric                return false;
10240b57cec5SDimitry Andric            ++__first2.__seg_;
10250b57cec5SDimitry Andric            if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r))
10260b57cec5SDimitry Andric                return false;
10270b57cec5SDimitry Andric        }
10280b57cec5SDimitry Andric        // do last word
10290b57cec5SDimitry Andric        if (__n > 0)
10300b57cec5SDimitry Andric        {
10310b57cec5SDimitry Andric            __m = ~__storage_type(0) >> (__bits_per_word - __n);
10320b57cec5SDimitry Andric            __storage_type __b = *__first1.__seg_ & __m;
10330b57cec5SDimitry Andric            __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r));
10340b57cec5SDimitry Andric            __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
10350b57cec5SDimitry Andric            if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_))
10360b57cec5SDimitry Andric                return false;
10370b57cec5SDimitry Andric            __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word;
10380b57cec5SDimitry Andric            __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_)  % __bits_per_word);
10390b57cec5SDimitry Andric            __n -= __dn;
10400b57cec5SDimitry Andric            if (__n > 0)
10410b57cec5SDimitry Andric            {
10420b57cec5SDimitry Andric                __m = ~__storage_type(0) >> (__bits_per_word - __n);
10430b57cec5SDimitry Andric                if ((*__first2.__seg_ & __m) != (__b >> __dn))
10440b57cec5SDimitry Andric                    return false;
10450b57cec5SDimitry Andric            }
10460b57cec5SDimitry Andric        }
10470b57cec5SDimitry Andric    }
10480b57cec5SDimitry Andric    return true;
10490b57cec5SDimitry Andric}
10500b57cec5SDimitry Andric
10510b57cec5SDimitry Andrictemplate <class _Cp, bool _IC1, bool _IC2>
10520b57cec5SDimitry Andricbool
10530b57cec5SDimitry Andric__equal_aligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1,
10540b57cec5SDimitry Andric                __bit_iterator<_Cp, _IC2> __first2)
10550b57cec5SDimitry Andric{
10560b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, _IC1> _It;
10570b57cec5SDimitry Andric    typedef  typename _It::difference_type difference_type;
10580b57cec5SDimitry Andric    typedef typename _It::__storage_type __storage_type;
10590b57cec5SDimitry Andric    static const int __bits_per_word = _It::__bits_per_word;
10600b57cec5SDimitry Andric    difference_type __n = __last1 - __first1;
10610b57cec5SDimitry Andric    if (__n > 0)
10620b57cec5SDimitry Andric    {
10630b57cec5SDimitry Andric        // do first word
10640b57cec5SDimitry Andric        if (__first1.__ctz_ != 0)
10650b57cec5SDimitry Andric        {
10660b57cec5SDimitry Andric            unsigned __clz = __bits_per_word - __first1.__ctz_;
10670b57cec5SDimitry Andric            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
10680b57cec5SDimitry Andric            __n -= __dn;
10690b57cec5SDimitry Andric            __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
10700b57cec5SDimitry Andric            if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))
10710b57cec5SDimitry Andric                return false;
10720b57cec5SDimitry Andric            ++__first2.__seg_;
10730b57cec5SDimitry Andric            ++__first1.__seg_;
10740b57cec5SDimitry Andric            // __first1.__ctz_ = 0;
10750b57cec5SDimitry Andric            // __first2.__ctz_ = 0;
10760b57cec5SDimitry Andric        }
10770b57cec5SDimitry Andric        // __first1.__ctz_ == 0;
10780b57cec5SDimitry Andric        // __first2.__ctz_ == 0;
10790b57cec5SDimitry Andric        // do middle words
10800b57cec5SDimitry Andric        for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_)
10810b57cec5SDimitry Andric            if (*__first2.__seg_ != *__first1.__seg_)
10820b57cec5SDimitry Andric                return false;
10830b57cec5SDimitry Andric        // do last word
10840b57cec5SDimitry Andric        if (__n > 0)
10850b57cec5SDimitry Andric        {
10860b57cec5SDimitry Andric            __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
10870b57cec5SDimitry Andric            if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))
10880b57cec5SDimitry Andric                return false;
10890b57cec5SDimitry Andric        }
10900b57cec5SDimitry Andric    }
10910b57cec5SDimitry Andric    return true;
10920b57cec5SDimitry Andric}
10930b57cec5SDimitry Andric
10940b57cec5SDimitry Andrictemplate <class _Cp, bool _IC1, bool _IC2>
10950b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY
10960b57cec5SDimitry Andricbool
10970b57cec5SDimitry Andricequal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2)
10980b57cec5SDimitry Andric{
10990b57cec5SDimitry Andric    if (__first1.__ctz_ == __first2.__ctz_)
1100e8d8bef9SDimitry Andric        return _VSTD::__equal_aligned(__first1, __last1, __first2);
1101e8d8bef9SDimitry Andric    return _VSTD::__equal_unaligned(__first1, __last1, __first2);
11020b57cec5SDimitry Andric}
11030b57cec5SDimitry Andric
11040b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst,
11050b57cec5SDimitry Andric          typename _Cp::__storage_type>
11060b57cec5SDimitry Andricclass __bit_iterator
11070b57cec5SDimitry Andric{
11080b57cec5SDimitry Andricpublic:
11090b57cec5SDimitry Andric    typedef typename _Cp::difference_type                                                          difference_type;
11100b57cec5SDimitry Andric    typedef bool                                                                                  value_type;
11110b57cec5SDimitry Andric    typedef __bit_iterator                                                                        pointer;
1112*81ad6265SDimitry Andric#ifndef _LIBCPP_ABI_BITSET_VECTOR_BOOL_CONST_SUBSCRIPT_RETURN_BOOL
11130b57cec5SDimitry Andric    typedef typename conditional<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >::type reference;
1114*81ad6265SDimitry Andric#else
1115*81ad6265SDimitry Andric    using reference = typename conditional<_IsConst, bool, __bit_reference<_Cp> >::type;
1116*81ad6265SDimitry Andric#endif
11170b57cec5SDimitry Andric    typedef random_access_iterator_tag                                                            iterator_category;
11180b57cec5SDimitry Andric
11190b57cec5SDimitry Andricprivate:
11200b57cec5SDimitry Andric    typedef typename _Cp::__storage_type                                           __storage_type;
11210b57cec5SDimitry Andric    typedef typename conditional<_IsConst, typename _Cp::__const_storage_pointer,
11220b57cec5SDimitry Andric                                           typename _Cp::__storage_pointer>::type  __storage_pointer;
11230b57cec5SDimitry Andric    static const unsigned __bits_per_word = _Cp::__bits_per_word;
11240b57cec5SDimitry Andric
11250b57cec5SDimitry Andric    __storage_pointer __seg_;
11260b57cec5SDimitry Andric    unsigned          __ctz_;
11270b57cec5SDimitry Andric
11280b57cec5SDimitry Andricpublic:
11290b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY __bit_iterator() _NOEXCEPT
11300b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11
11310b57cec5SDimitry Andric    : __seg_(nullptr), __ctz_(0)
11320b57cec5SDimitry Andric#endif
11330b57cec5SDimitry Andric    {}
11340b57cec5SDimitry Andric
11354652422eSDimitry Andric    // When _IsConst=false, this is the copy constructor.
11364652422eSDimitry Andric    // It is non-trivial. Making it trivial would break ABI.
11374652422eSDimitry Andric    // When _IsConst=true, this is a converting constructor;
11384652422eSDimitry Andric    // the copy and move constructors are implicitly generated
11394652422eSDimitry Andric    // and trivial.
11400b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
11414652422eSDimitry Andric    __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT
11420b57cec5SDimitry Andric        : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {}
11430b57cec5SDimitry Andric
11444652422eSDimitry Andric    // When _IsConst=false, we have a user-provided copy constructor,
11454652422eSDimitry Andric    // so we must also provide a copy assignment operator because
11464652422eSDimitry Andric    // the implicit generation of a defaulted one is deprecated.
11474652422eSDimitry Andric    // When _IsConst=true, the assignment operators are
11484652422eSDimitry Andric    // implicitly generated and trivial.
114947395794SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
11504652422eSDimitry Andric    __bit_iterator& operator=(const _If<_IsConst, struct __private_nat, __bit_iterator>& __it) {
11514652422eSDimitry Andric        __seg_ = __it.__seg_;
11524652422eSDimitry Andric        __ctz_ = __it.__ctz_;
11534652422eSDimitry Andric        return *this;
11544652422eSDimitry Andric    }
115547395794SDimitry Andric
1156*81ad6265SDimitry Andric    _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT {
1157*81ad6265SDimitry Andric        return typename conditional<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >
1158*81ad6265SDimitry Andric                ::type(__seg_, __storage_type(1) << __ctz_);
1159*81ad6265SDimitry Andric    }
11600b57cec5SDimitry Andric
11610b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator++()
11620b57cec5SDimitry Andric    {
11630b57cec5SDimitry Andric        if (__ctz_ != __bits_per_word-1)
11640b57cec5SDimitry Andric            ++__ctz_;
11650b57cec5SDimitry Andric        else
11660b57cec5SDimitry Andric        {
11670b57cec5SDimitry Andric            __ctz_ = 0;
11680b57cec5SDimitry Andric            ++__seg_;
11690b57cec5SDimitry Andric        }
11700b57cec5SDimitry Andric        return *this;
11710b57cec5SDimitry Andric    }
11720b57cec5SDimitry Andric
11730b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY __bit_iterator operator++(int)
11740b57cec5SDimitry Andric    {
11750b57cec5SDimitry Andric        __bit_iterator __tmp = *this;
11760b57cec5SDimitry Andric        ++(*this);
11770b57cec5SDimitry Andric        return __tmp;
11780b57cec5SDimitry Andric    }
11790b57cec5SDimitry Andric
11800b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator--()
11810b57cec5SDimitry Andric    {
11820b57cec5SDimitry Andric        if (__ctz_ != 0)
11830b57cec5SDimitry Andric            --__ctz_;
11840b57cec5SDimitry Andric        else
11850b57cec5SDimitry Andric        {
11860b57cec5SDimitry Andric            __ctz_ = __bits_per_word - 1;
11870b57cec5SDimitry Andric            --__seg_;
11880b57cec5SDimitry Andric        }
11890b57cec5SDimitry Andric        return *this;
11900b57cec5SDimitry Andric    }
11910b57cec5SDimitry Andric
11920b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY __bit_iterator operator--(int)
11930b57cec5SDimitry Andric    {
11940b57cec5SDimitry Andric        __bit_iterator __tmp = *this;
11950b57cec5SDimitry Andric        --(*this);
11960b57cec5SDimitry Andric        return __tmp;
11970b57cec5SDimitry Andric    }
11980b57cec5SDimitry Andric
11990b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator+=(difference_type __n)
12000b57cec5SDimitry Andric    {
12010b57cec5SDimitry Andric        if (__n >= 0)
12020b57cec5SDimitry Andric            __seg_ += (__n + __ctz_) / __bits_per_word;
12030b57cec5SDimitry Andric        else
12040b57cec5SDimitry Andric            __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1)
12050b57cec5SDimitry Andric                    / static_cast<difference_type>(__bits_per_word);
12060b57cec5SDimitry Andric        __n &= (__bits_per_word - 1);
12070b57cec5SDimitry Andric        __ctz_ = static_cast<unsigned>((__n + __ctz_)  % __bits_per_word);
12080b57cec5SDimitry Andric        return *this;
12090b57cec5SDimitry Andric    }
12100b57cec5SDimitry Andric
12110b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator-=(difference_type __n)
12120b57cec5SDimitry Andric    {
12130b57cec5SDimitry Andric        return *this += -__n;
12140b57cec5SDimitry Andric    }
12150b57cec5SDimitry Andric
12160b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY __bit_iterator operator+(difference_type __n) const
12170b57cec5SDimitry Andric    {
12180b57cec5SDimitry Andric        __bit_iterator __t(*this);
12190b57cec5SDimitry Andric        __t += __n;
12200b57cec5SDimitry Andric        return __t;
12210b57cec5SDimitry Andric    }
12220b57cec5SDimitry Andric
12230b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY __bit_iterator operator-(difference_type __n) const
12240b57cec5SDimitry Andric    {
12250b57cec5SDimitry Andric        __bit_iterator __t(*this);
12260b57cec5SDimitry Andric        __t -= __n;
12270b57cec5SDimitry Andric        return __t;
12280b57cec5SDimitry Andric    }
12290b57cec5SDimitry Andric
12300b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
12310b57cec5SDimitry Andric    friend __bit_iterator operator+(difference_type __n, const __bit_iterator& __it) {return __it + __n;}
12320b57cec5SDimitry Andric
12330b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
12340b57cec5SDimitry Andric    friend difference_type operator-(const __bit_iterator& __x, const __bit_iterator& __y)
12350b57cec5SDimitry Andric        {return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;}
12360b57cec5SDimitry Andric
12370b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const {return *(*this + __n);}
12380b57cec5SDimitry Andric
12390b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY friend bool operator==(const __bit_iterator& __x, const __bit_iterator& __y)
12400b57cec5SDimitry Andric        {return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;}
12410b57cec5SDimitry Andric
12420b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY friend bool operator!=(const __bit_iterator& __x, const __bit_iterator& __y)
12430b57cec5SDimitry Andric        {return !(__x == __y);}
12440b57cec5SDimitry Andric
12450b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY friend bool operator<(const __bit_iterator& __x, const __bit_iterator& __y)
12460b57cec5SDimitry Andric        {return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);}
12470b57cec5SDimitry Andric
12480b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY friend bool operator>(const __bit_iterator& __x, const __bit_iterator& __y)
12490b57cec5SDimitry Andric        {return __y < __x;}
12500b57cec5SDimitry Andric
12510b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y)
12520b57cec5SDimitry Andric        {return !(__y < __x);}
12530b57cec5SDimitry Andric
12540b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y)
12550b57cec5SDimitry Andric        {return !(__x < __y);}
12560b57cec5SDimitry Andric
12570b57cec5SDimitry Andricprivate:
12580b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
1259*81ad6265SDimitry Andric    explicit __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT
12600b57cec5SDimitry Andric        : __seg_(__s), __ctz_(__ctz) {}
12610b57cec5SDimitry Andric
12620b57cec5SDimitry Andric    friend typename _Cp::__self;
12630b57cec5SDimitry Andric
12640b57cec5SDimitry Andric    friend class __bit_reference<_Cp>;
12650b57cec5SDimitry Andric    friend class __bit_const_reference<_Cp>;
12660b57cec5SDimitry Andric    friend class __bit_iterator<_Cp, true>;
12670b57cec5SDimitry Andric    template <class _Dp> friend struct __bit_array;
12680b57cec5SDimitry Andric    template <class _Dp> friend void __fill_n_false(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n);
12690b57cec5SDimitry Andric    template <class _Dp> friend void __fill_n_true(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n);
12700b57cec5SDimitry Andric    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_aligned(__bit_iterator<_Dp, _IC> __first,
12710b57cec5SDimitry Andric                                                                                  __bit_iterator<_Dp, _IC> __last,
12720b57cec5SDimitry Andric                                                                                  __bit_iterator<_Dp, false> __result);
12730b57cec5SDimitry Andric    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_unaligned(__bit_iterator<_Dp, _IC> __first,
12740b57cec5SDimitry Andric                                                                                    __bit_iterator<_Dp, _IC> __last,
12750b57cec5SDimitry Andric                                                                                    __bit_iterator<_Dp, false> __result);
12760b57cec5SDimitry Andric    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy(__bit_iterator<_Dp, _IC> __first,
12770b57cec5SDimitry Andric                                                                        __bit_iterator<_Dp, _IC> __last,
12780b57cec5SDimitry Andric                                                                        __bit_iterator<_Dp, false> __result);
12790b57cec5SDimitry Andric    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_aligned(__bit_iterator<_Dp, _IC> __first,
12800b57cec5SDimitry Andric                                                                                           __bit_iterator<_Dp, _IC> __last,
12810b57cec5SDimitry Andric                                                                                           __bit_iterator<_Dp, false> __result);
12820b57cec5SDimitry Andric    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_unaligned(__bit_iterator<_Dp, _IC> __first,
12830b57cec5SDimitry Andric                                                                                             __bit_iterator<_Dp, _IC> __last,
12840b57cec5SDimitry Andric                                                                                             __bit_iterator<_Dp, false> __result);
12850b57cec5SDimitry Andric    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy_backward(__bit_iterator<_Dp, _IC> __first,
12860b57cec5SDimitry Andric                                                                                 __bit_iterator<_Dp, _IC> __last,
12870b57cec5SDimitry Andric                                                                                 __bit_iterator<_Dp, false> __result);
12880b57cec5SDimitry Andric    template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_aligned(__bit_iterator<__C1, false>,
12890b57cec5SDimitry Andric                                                                                           __bit_iterator<__C1, false>,
12900b57cec5SDimitry Andric                                                                                           __bit_iterator<__C2, false>);
12910b57cec5SDimitry Andric    template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_unaligned(__bit_iterator<__C1, false>,
12920b57cec5SDimitry Andric                                                                                             __bit_iterator<__C1, false>,
12930b57cec5SDimitry Andric                                                                                             __bit_iterator<__C2, false>);
12940b57cec5SDimitry Andric    template <class __C1, class __C2>friend __bit_iterator<__C2, false> swap_ranges(__bit_iterator<__C1, false>,
12950b57cec5SDimitry Andric                                                                                 __bit_iterator<__C1, false>,
12960b57cec5SDimitry Andric                                                                                 __bit_iterator<__C2, false>);
12970b57cec5SDimitry Andric    template <class _Dp> friend __bit_iterator<_Dp, false> rotate(__bit_iterator<_Dp, false>,
12980b57cec5SDimitry Andric                                                                __bit_iterator<_Dp, false>,
12990b57cec5SDimitry Andric                                                                __bit_iterator<_Dp, false>);
13000b57cec5SDimitry Andric    template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_aligned(__bit_iterator<_Dp, _IC1>,
13010b57cec5SDimitry Andric                                                    __bit_iterator<_Dp, _IC1>,
13020b57cec5SDimitry Andric                                                    __bit_iterator<_Dp, _IC2>);
13030b57cec5SDimitry Andric    template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_unaligned(__bit_iterator<_Dp, _IC1>,
13040b57cec5SDimitry Andric                                                      __bit_iterator<_Dp, _IC1>,
13050b57cec5SDimitry Andric                                                      __bit_iterator<_Dp, _IC2>);
13060b57cec5SDimitry Andric    template <class _Dp, bool _IC1, bool _IC2> friend bool equal(__bit_iterator<_Dp, _IC1>,
13070b57cec5SDimitry Andric                                                                __bit_iterator<_Dp, _IC1>,
13080b57cec5SDimitry Andric                                                                __bit_iterator<_Dp, _IC2>);
13090b57cec5SDimitry Andric    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_true(__bit_iterator<_Dp, _IC>,
13100b57cec5SDimitry Andric                                                                          typename _Dp::size_type);
13110b57cec5SDimitry Andric    template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_false(__bit_iterator<_Dp, _IC>,
13120b57cec5SDimitry Andric                                                                           typename _Dp::size_type);
13130b57cec5SDimitry Andric    template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type
13140b57cec5SDimitry Andric                   __count_bool_true(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
13150b57cec5SDimitry Andric    template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type
13160b57cec5SDimitry Andric                   __count_bool_false(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
13170b57cec5SDimitry Andric};
13180b57cec5SDimitry Andric
13190b57cec5SDimitry Andric_LIBCPP_END_NAMESPACE_STD
13200b57cec5SDimitry Andric
13210b57cec5SDimitry Andric_LIBCPP_POP_MACROS
13220b57cec5SDimitry Andric
13230b57cec5SDimitry Andric#endif // _LIBCPP___BIT_REFERENCE
1324