xref: /freebsd/contrib/llvm-project/libcxx/include/__bit_reference (revision 06c3fb2749bda94cb5201f81ffdb8fa6c3161b2e)
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
1361cfbce3SDimitry Andric#include <__algorithm/copy_n.h>
1461cfbce3SDimitry Andric#include <__algorithm/fill_n.h>
1581ad6265SDimitry Andric#include <__algorithm/min.h>
16bdd1243dSDimitry Andric#include <__bit/countr.h>
17bdd1243dSDimitry Andric#include <__bit/popcount.h>
1804eeddc0SDimitry Andric#include <__config>
1981ad6265SDimitry Andric#include <__iterator/iterator_traits.h>
2061cfbce3SDimitry Andric#include <__memory/construct_at.h>
2181ad6265SDimitry Andric#include <__memory/pointer_traits.h>
22*06c3fb27SDimitry Andric#include <__type_traits/conditional.h>
23*06c3fb27SDimitry Andric#include <__utility/swap.h>
2481ad6265SDimitry Andric#include <cstring>
250b57cec5SDimitry Andric
260b57cec5SDimitry Andric#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
270b57cec5SDimitry Andric#  pragma GCC system_header
280b57cec5SDimitry Andric#endif
290b57cec5SDimitry Andric
300b57cec5SDimitry Andric_LIBCPP_PUSH_MACROS
310b57cec5SDimitry Andric#include <__undef_macros>
320b57cec5SDimitry Andric
330b57cec5SDimitry Andric
340b57cec5SDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD
350b57cec5SDimitry Andric
360b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst, typename _Cp::__storage_type = 0> class __bit_iterator;
370b57cec5SDimitry Andrictemplate <class _Cp> class __bit_const_reference;
380b57cec5SDimitry Andric
390b57cec5SDimitry Andrictemplate <class _Tp>
400b57cec5SDimitry Andricstruct __has_storage_type
410b57cec5SDimitry Andric{
420b57cec5SDimitry Andric    static const bool value = false;
430b57cec5SDimitry Andric};
440b57cec5SDimitry Andric
450b57cec5SDimitry Andrictemplate <class _Cp, bool = __has_storage_type<_Cp>::value>
460b57cec5SDimitry Andricclass __bit_reference
470b57cec5SDimitry Andric{
480b57cec5SDimitry Andric    typedef typename _Cp::__storage_type    __storage_type;
490b57cec5SDimitry Andric    typedef typename _Cp::__storage_pointer __storage_pointer;
500b57cec5SDimitry Andric
510b57cec5SDimitry Andric    __storage_pointer __seg_;
520b57cec5SDimitry Andric    __storage_type    __mask_;
530b57cec5SDimitry Andric
540b57cec5SDimitry Andric    friend typename _Cp::__self;
550b57cec5SDimitry Andric
560b57cec5SDimitry Andric    friend class __bit_const_reference<_Cp>;
570b57cec5SDimitry Andric    friend class __bit_iterator<_Cp, false>;
580b57cec5SDimitry Andricpublic:
59bdd1243dSDimitry Andric    using __container = typename _Cp::__self;
60bdd1243dSDimitry Andric
61bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
62480093f4SDimitry Andric    __bit_reference(const __bit_reference&) = default;
63480093f4SDimitry Andric
64bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 operator bool() const _NOEXCEPT
650b57cec5SDimitry Andric        {return static_cast<bool>(*__seg_ & __mask_);}
66bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 bool operator ~() const _NOEXCEPT
670b57cec5SDimitry Andric        {return !static_cast<bool>(*this);}
680b57cec5SDimitry Andric
69bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
700b57cec5SDimitry Andric    __bit_reference& operator=(bool __x) _NOEXCEPT
710b57cec5SDimitry Andric    {
720b57cec5SDimitry Andric        if (__x)
730b57cec5SDimitry Andric            *__seg_ |= __mask_;
740b57cec5SDimitry Andric        else
750b57cec5SDimitry Andric            *__seg_ &= ~__mask_;
760b57cec5SDimitry Andric        return *this;
770b57cec5SDimitry Andric    }
780b57cec5SDimitry Andric
79*06c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23
8061cfbce3SDimitry Andric    _LIBCPP_HIDE_FROM_ABI constexpr const __bit_reference& operator=(bool __x) const noexcept {
8181ad6265SDimitry Andric        if (__x)
8281ad6265SDimitry Andric            *__seg_ |= __mask_;
8381ad6265SDimitry Andric        else
8481ad6265SDimitry Andric            *__seg_ &= ~__mask_;
8581ad6265SDimitry Andric        return *this;
8681ad6265SDimitry Andric    }
8781ad6265SDimitry Andric#endif
8881ad6265SDimitry Andric
89bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
900b57cec5SDimitry Andric    __bit_reference& operator=(const __bit_reference& __x) _NOEXCEPT
910b57cec5SDimitry Andric        {return operator=(static_cast<bool>(__x));}
920b57cec5SDimitry Andric
93bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 void flip() _NOEXCEPT {*__seg_ ^= __mask_;}
94bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, false> operator&() const _NOEXCEPT
95bdd1243dSDimitry Andric        {return __bit_iterator<_Cp, false>(__seg_, static_cast<unsigned>(std::__libcpp_ctz(__mask_)));}
960b57cec5SDimitry Andricprivate:
97bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
9881ad6265SDimitry Andric    explicit __bit_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT
990b57cec5SDimitry Andric        : __seg_(__s), __mask_(__m) {}
1000b57cec5SDimitry Andric};
1010b57cec5SDimitry Andric
1020b57cec5SDimitry Andrictemplate <class _Cp>
1030b57cec5SDimitry Andricclass __bit_reference<_Cp, false>
1040b57cec5SDimitry Andric{
1050b57cec5SDimitry Andric};
1060b57cec5SDimitry Andric
1070b57cec5SDimitry Andrictemplate <class _Cp>
108bdd1243dSDimitry Andricinline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
1090b57cec5SDimitry Andricvoid
1100b57cec5SDimitry Andricswap(__bit_reference<_Cp> __x, __bit_reference<_Cp> __y) _NOEXCEPT
1110b57cec5SDimitry Andric{
1120b57cec5SDimitry Andric    bool __t = __x;
1130b57cec5SDimitry Andric    __x = __y;
1140b57cec5SDimitry Andric    __y = __t;
1150b57cec5SDimitry Andric}
1160b57cec5SDimitry Andric
1170b57cec5SDimitry Andrictemplate <class _Cp, class _Dp>
118bdd1243dSDimitry Andricinline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
1190b57cec5SDimitry Andricvoid
1200b57cec5SDimitry Andricswap(__bit_reference<_Cp> __x, __bit_reference<_Dp> __y) _NOEXCEPT
1210b57cec5SDimitry Andric{
1220b57cec5SDimitry Andric    bool __t = __x;
1230b57cec5SDimitry Andric    __x = __y;
1240b57cec5SDimitry Andric    __y = __t;
1250b57cec5SDimitry Andric}
1260b57cec5SDimitry Andric
1270b57cec5SDimitry Andrictemplate <class _Cp>
128bdd1243dSDimitry Andricinline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
1290b57cec5SDimitry Andricvoid
1300b57cec5SDimitry Andricswap(__bit_reference<_Cp> __x, bool& __y) _NOEXCEPT
1310b57cec5SDimitry Andric{
1320b57cec5SDimitry Andric    bool __t = __x;
1330b57cec5SDimitry Andric    __x = __y;
1340b57cec5SDimitry Andric    __y = __t;
1350b57cec5SDimitry Andric}
1360b57cec5SDimitry Andric
1370b57cec5SDimitry Andrictemplate <class _Cp>
138bdd1243dSDimitry Andricinline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
1390b57cec5SDimitry Andricvoid
1400b57cec5SDimitry Andricswap(bool& __x, __bit_reference<_Cp> __y) _NOEXCEPT
1410b57cec5SDimitry Andric{
1420b57cec5SDimitry Andric    bool __t = __x;
1430b57cec5SDimitry Andric    __x = __y;
1440b57cec5SDimitry Andric    __y = __t;
1450b57cec5SDimitry Andric}
1460b57cec5SDimitry Andric
1470b57cec5SDimitry Andrictemplate <class _Cp>
1480b57cec5SDimitry Andricclass __bit_const_reference
1490b57cec5SDimitry Andric{
1500b57cec5SDimitry Andric    typedef typename _Cp::__storage_type          __storage_type;
1510b57cec5SDimitry Andric    typedef typename _Cp::__const_storage_pointer __storage_pointer;
1520b57cec5SDimitry Andric
1530b57cec5SDimitry Andric    __storage_pointer        __seg_;
1540b57cec5SDimitry Andric    __storage_type __mask_;
1550b57cec5SDimitry Andric
1560b57cec5SDimitry Andric    friend typename _Cp::__self;
1570b57cec5SDimitry Andric    friend class __bit_iterator<_Cp, true>;
1580b57cec5SDimitry Andricpublic:
159*06c3fb27SDimitry Andric    using __container = typename _Cp::__self;
160*06c3fb27SDimitry Andric
1610b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
162480093f4SDimitry Andric    __bit_const_reference(const __bit_const_reference&) = default;
163480093f4SDimitry Andric
164bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
1650b57cec5SDimitry Andric    __bit_const_reference(const __bit_reference<_Cp>& __x) _NOEXCEPT
1660b57cec5SDimitry Andric        : __seg_(__x.__seg_), __mask_(__x.__mask_) {}
1670b57cec5SDimitry Andric
1680b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR operator bool() const _NOEXCEPT
1690b57cec5SDimitry Andric        {return static_cast<bool>(*__seg_ & __mask_);}
1700b57cec5SDimitry Andric
171bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, true> operator&() const _NOEXCEPT
172bdd1243dSDimitry Andric        {return __bit_iterator<_Cp, true>(__seg_, static_cast<unsigned>(std::__libcpp_ctz(__mask_)));}
1730b57cec5SDimitry Andricprivate:
1740b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
1750b57cec5SDimitry Andric    _LIBCPP_CONSTEXPR
17681ad6265SDimitry Andric    explicit __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT
1770b57cec5SDimitry Andric        : __seg_(__s), __mask_(__m) {}
1780b57cec5SDimitry Andric
179480093f4SDimitry Andric    __bit_const_reference& operator=(const __bit_const_reference&) = delete;
1800b57cec5SDimitry Andric};
1810b57cec5SDimitry Andric
1820b57cec5SDimitry Andric// find
1830b57cec5SDimitry Andric
1840b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
185bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, _IsConst>
1860b57cec5SDimitry Andric__find_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
1870b57cec5SDimitry Andric{
1880b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, _IsConst> _It;
1890b57cec5SDimitry Andric    typedef typename _It::__storage_type __storage_type;
19061cfbce3SDimitry Andric    const int __bits_per_word = _It::__bits_per_word;
1910b57cec5SDimitry Andric    // do first partial word
1920b57cec5SDimitry Andric    if (__first.__ctz_ != 0)
1930b57cec5SDimitry Andric    {
1940b57cec5SDimitry Andric        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
1950b57cec5SDimitry Andric        __storage_type __dn = _VSTD::min(__clz_f, __n);
1960b57cec5SDimitry Andric        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
1970b57cec5SDimitry Andric        __storage_type __b = *__first.__seg_ & __m;
1980b57cec5SDimitry Andric        if (__b)
1990b57cec5SDimitry Andric            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b)));
2000b57cec5SDimitry Andric        if (__n == __dn)
2010b57cec5SDimitry Andric            return __first + __n;
2020b57cec5SDimitry Andric        __n -= __dn;
2030b57cec5SDimitry Andric        ++__first.__seg_;
2040b57cec5SDimitry Andric    }
2050b57cec5SDimitry Andric    // do middle whole words
2060b57cec5SDimitry Andric    for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
2070b57cec5SDimitry Andric        if (*__first.__seg_)
2080b57cec5SDimitry Andric            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(*__first.__seg_)));
2090b57cec5SDimitry Andric    // do last partial word
2100b57cec5SDimitry Andric    if (__n > 0)
2110b57cec5SDimitry Andric    {
2120b57cec5SDimitry Andric        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
2130b57cec5SDimitry Andric        __storage_type __b = *__first.__seg_ & __m;
2140b57cec5SDimitry Andric        if (__b)
2150b57cec5SDimitry Andric            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b)));
2160b57cec5SDimitry Andric    }
2170b57cec5SDimitry Andric    return _It(__first.__seg_, static_cast<unsigned>(__n));
2180b57cec5SDimitry Andric}
2190b57cec5SDimitry Andric
2200b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
221bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, _IsConst>
2220b57cec5SDimitry Andric__find_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
2230b57cec5SDimitry Andric{
2240b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, _IsConst> _It;
2250b57cec5SDimitry Andric    typedef typename _It::__storage_type __storage_type;
2260b57cec5SDimitry Andric    const int __bits_per_word = _It::__bits_per_word;
2270b57cec5SDimitry Andric    // do first partial word
2280b57cec5SDimitry Andric    if (__first.__ctz_ != 0)
2290b57cec5SDimitry Andric    {
2300b57cec5SDimitry Andric        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
2310b57cec5SDimitry Andric        __storage_type __dn = _VSTD::min(__clz_f, __n);
2320b57cec5SDimitry Andric        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
2330b57cec5SDimitry Andric        __storage_type __b = ~*__first.__seg_ & __m;
2340b57cec5SDimitry Andric        if (__b)
2350b57cec5SDimitry Andric            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b)));
2360b57cec5SDimitry Andric        if (__n == __dn)
2370b57cec5SDimitry Andric            return __first + __n;
2380b57cec5SDimitry Andric        __n -= __dn;
2390b57cec5SDimitry Andric        ++__first.__seg_;
2400b57cec5SDimitry Andric    }
2410b57cec5SDimitry Andric    // do middle whole words
2420b57cec5SDimitry Andric    for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
2430b57cec5SDimitry Andric    {
2440b57cec5SDimitry Andric        __storage_type __b = ~*__first.__seg_;
2450b57cec5SDimitry Andric        if (__b)
2460b57cec5SDimitry Andric            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b)));
2470b57cec5SDimitry Andric    }
2480b57cec5SDimitry Andric    // do last partial word
2490b57cec5SDimitry Andric    if (__n > 0)
2500b57cec5SDimitry Andric    {
2510b57cec5SDimitry Andric        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
2520b57cec5SDimitry Andric        __storage_type __b = ~*__first.__seg_ & __m;
2530b57cec5SDimitry Andric        if (__b)
2540b57cec5SDimitry Andric            return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b)));
2550b57cec5SDimitry Andric    }
2560b57cec5SDimitry Andric    return _It(__first.__seg_, static_cast<unsigned>(__n));
2570b57cec5SDimitry Andric}
2580b57cec5SDimitry Andric
2590b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst, class _Tp>
260bdd1243dSDimitry Andricinline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
2610b57cec5SDimitry Andric__bit_iterator<_Cp, _IsConst>
262753f127fSDimitry Andricfind(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value)
2630b57cec5SDimitry Andric{
264753f127fSDimitry Andric    if (static_cast<bool>(__value))
265e8d8bef9SDimitry Andric        return _VSTD::__find_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first));
266e8d8bef9SDimitry Andric    return _VSTD::__find_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first));
2670b57cec5SDimitry Andric}
2680b57cec5SDimitry Andric
2690b57cec5SDimitry Andric// count
2700b57cec5SDimitry Andric
2710b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
272bdd1243dSDimitry Andric_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 typename __bit_iterator<_Cp, _IsConst>::difference_type
2730b57cec5SDimitry Andric__count_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
2740b57cec5SDimitry Andric{
2750b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, _IsConst> _It;
2760b57cec5SDimitry Andric    typedef typename _It::__storage_type __storage_type;
2770b57cec5SDimitry Andric    typedef typename _It::difference_type difference_type;
2780b57cec5SDimitry Andric    const int __bits_per_word = _It::__bits_per_word;
2790b57cec5SDimitry Andric    difference_type __r = 0;
2800b57cec5SDimitry Andric    // do first partial word
2810b57cec5SDimitry Andric    if (__first.__ctz_ != 0)
2820b57cec5SDimitry Andric    {
2830b57cec5SDimitry Andric        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
2840b57cec5SDimitry Andric        __storage_type __dn = _VSTD::min(__clz_f, __n);
2850b57cec5SDimitry Andric        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
2860b57cec5SDimitry Andric        __r = _VSTD::__libcpp_popcount(*__first.__seg_ & __m);
2870b57cec5SDimitry Andric        __n -= __dn;
2880b57cec5SDimitry Andric        ++__first.__seg_;
2890b57cec5SDimitry Andric    }
2900b57cec5SDimitry Andric    // do middle whole words
2910b57cec5SDimitry Andric    for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
2920b57cec5SDimitry Andric        __r += _VSTD::__libcpp_popcount(*__first.__seg_);
2930b57cec5SDimitry Andric    // do last partial word
2940b57cec5SDimitry Andric    if (__n > 0)
2950b57cec5SDimitry Andric    {
2960b57cec5SDimitry Andric        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
2970b57cec5SDimitry Andric        __r += _VSTD::__libcpp_popcount(*__first.__seg_ & __m);
2980b57cec5SDimitry Andric    }
2990b57cec5SDimitry Andric    return __r;
3000b57cec5SDimitry Andric}
3010b57cec5SDimitry Andric
3020b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
303bdd1243dSDimitry Andric_LIBCPP_HIDE_FROM_ABI typename __bit_iterator<_Cp, _IsConst>::difference_type
3040b57cec5SDimitry Andric__count_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
3050b57cec5SDimitry Andric{
3060b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, _IsConst> _It;
3070b57cec5SDimitry Andric    typedef typename _It::__storage_type __storage_type;
3080b57cec5SDimitry Andric    typedef typename _It::difference_type difference_type;
3090b57cec5SDimitry Andric    const int __bits_per_word = _It::__bits_per_word;
3100b57cec5SDimitry Andric    difference_type __r = 0;
3110b57cec5SDimitry Andric    // do first partial word
3120b57cec5SDimitry Andric    if (__first.__ctz_ != 0)
3130b57cec5SDimitry Andric    {
3140b57cec5SDimitry Andric        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
3150b57cec5SDimitry Andric        __storage_type __dn = _VSTD::min(__clz_f, __n);
3160b57cec5SDimitry Andric        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
3170b57cec5SDimitry Andric        __r = _VSTD::__libcpp_popcount(~*__first.__seg_ & __m);
3180b57cec5SDimitry Andric        __n -= __dn;
3190b57cec5SDimitry Andric        ++__first.__seg_;
3200b57cec5SDimitry Andric    }
3210b57cec5SDimitry Andric    // do middle whole words
3220b57cec5SDimitry Andric    for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
3230b57cec5SDimitry Andric        __r += _VSTD::__libcpp_popcount(~*__first.__seg_);
3240b57cec5SDimitry Andric    // do last partial word
3250b57cec5SDimitry Andric    if (__n > 0)
3260b57cec5SDimitry Andric    {
3270b57cec5SDimitry Andric        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3280b57cec5SDimitry Andric        __r += _VSTD::__libcpp_popcount(~*__first.__seg_ & __m);
3290b57cec5SDimitry Andric    }
3300b57cec5SDimitry Andric    return __r;
3310b57cec5SDimitry Andric}
3320b57cec5SDimitry Andric
3330b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst, class _Tp>
3340b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY
3350b57cec5SDimitry Andrictypename __bit_iterator<_Cp, _IsConst>::difference_type
336753f127fSDimitry Andriccount(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value)
3370b57cec5SDimitry Andric{
338753f127fSDimitry Andric    if (static_cast<bool>(__value))
339e8d8bef9SDimitry Andric        return _VSTD::__count_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first));
340e8d8bef9SDimitry Andric    return _VSTD::__count_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first));
3410b57cec5SDimitry Andric}
3420b57cec5SDimitry Andric
3430b57cec5SDimitry Andric// fill_n
3440b57cec5SDimitry Andric
3450b57cec5SDimitry Andrictemplate <class _Cp>
346bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
3470b57cec5SDimitry Andric__fill_n_false(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n)
3480b57cec5SDimitry Andric{
3490b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, false> _It;
3500b57cec5SDimitry Andric    typedef typename _It::__storage_type __storage_type;
3510b57cec5SDimitry Andric    const int __bits_per_word = _It::__bits_per_word;
3520b57cec5SDimitry Andric    // do first partial word
3530b57cec5SDimitry Andric    if (__first.__ctz_ != 0)
3540b57cec5SDimitry Andric    {
3550b57cec5SDimitry Andric        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
3560b57cec5SDimitry Andric        __storage_type __dn = _VSTD::min(__clz_f, __n);
3570b57cec5SDimitry Andric        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
3580b57cec5SDimitry Andric        *__first.__seg_ &= ~__m;
3590b57cec5SDimitry Andric        __n -= __dn;
3600b57cec5SDimitry Andric        ++__first.__seg_;
3610b57cec5SDimitry Andric    }
3620b57cec5SDimitry Andric    // do middle whole words
3630b57cec5SDimitry Andric    __storage_type __nw = __n / __bits_per_word;
36461cfbce3SDimitry Andric    std::fill_n(std::__to_address(__first.__seg_), __nw, 0);
3650b57cec5SDimitry Andric    __n -= __nw * __bits_per_word;
3660b57cec5SDimitry Andric    // do last partial word
3670b57cec5SDimitry Andric    if (__n > 0)
3680b57cec5SDimitry Andric    {
3690b57cec5SDimitry Andric        __first.__seg_ += __nw;
3700b57cec5SDimitry Andric        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3710b57cec5SDimitry Andric        *__first.__seg_ &= ~__m;
3720b57cec5SDimitry Andric    }
3730b57cec5SDimitry Andric}
3740b57cec5SDimitry Andric
3750b57cec5SDimitry Andrictemplate <class _Cp>
376bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
3770b57cec5SDimitry Andric__fill_n_true(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n)
3780b57cec5SDimitry Andric{
3790b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, false> _It;
3800b57cec5SDimitry Andric    typedef typename _It::__storage_type __storage_type;
3810b57cec5SDimitry Andric    const int __bits_per_word = _It::__bits_per_word;
3820b57cec5SDimitry Andric    // do first partial word
3830b57cec5SDimitry Andric    if (__first.__ctz_ != 0)
3840b57cec5SDimitry Andric    {
3850b57cec5SDimitry Andric        __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
3860b57cec5SDimitry Andric        __storage_type __dn = _VSTD::min(__clz_f, __n);
3870b57cec5SDimitry Andric        __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
3880b57cec5SDimitry Andric        *__first.__seg_ |= __m;
3890b57cec5SDimitry Andric        __n -= __dn;
3900b57cec5SDimitry Andric        ++__first.__seg_;
3910b57cec5SDimitry Andric    }
3920b57cec5SDimitry Andric    // do middle whole words
3930b57cec5SDimitry Andric    __storage_type __nw = __n / __bits_per_word;
39461cfbce3SDimitry Andric    // __storage_type is always an unsigned type, so -1 sets all bits
39561cfbce3SDimitry Andric    std::fill_n(std::__to_address(__first.__seg_), __nw, static_cast<__storage_type>(-1));
3960b57cec5SDimitry Andric    __n -= __nw * __bits_per_word;
3970b57cec5SDimitry Andric    // do last partial word
3980b57cec5SDimitry Andric    if (__n > 0)
3990b57cec5SDimitry Andric    {
4000b57cec5SDimitry Andric        __first.__seg_ += __nw;
4010b57cec5SDimitry Andric        __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
4020b57cec5SDimitry Andric        *__first.__seg_ |= __m;
4030b57cec5SDimitry Andric    }
4040b57cec5SDimitry Andric}
4050b57cec5SDimitry Andric
4060b57cec5SDimitry Andrictemplate <class _Cp>
407bdd1243dSDimitry Andricinline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
4080b57cec5SDimitry Andricvoid
409753f127fSDimitry Andricfill_n(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n, bool __value)
4100b57cec5SDimitry Andric{
4110b57cec5SDimitry Andric    if (__n > 0)
4120b57cec5SDimitry Andric    {
413753f127fSDimitry Andric        if (__value)
414e8d8bef9SDimitry Andric            _VSTD::__fill_n_true(__first, __n);
4150b57cec5SDimitry Andric        else
416e8d8bef9SDimitry Andric            _VSTD::__fill_n_false(__first, __n);
4170b57cec5SDimitry Andric    }
4180b57cec5SDimitry Andric}
4190b57cec5SDimitry Andric
4200b57cec5SDimitry Andric// fill
4210b57cec5SDimitry Andric
4220b57cec5SDimitry Andrictemplate <class _Cp>
423bdd1243dSDimitry Andricinline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
4240b57cec5SDimitry Andricvoid
425753f127fSDimitry Andricfill(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __last, bool __value)
4260b57cec5SDimitry Andric{
427753f127fSDimitry Andric    _VSTD::fill_n(__first, static_cast<typename _Cp::size_type>(__last - __first), __value);
4280b57cec5SDimitry Andric}
4290b57cec5SDimitry Andric
4300b57cec5SDimitry Andric// copy
4310b57cec5SDimitry Andric
4320b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
433bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false>
4340b57cec5SDimitry Andric__copy_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
4350b57cec5SDimitry Andric                                                     __bit_iterator<_Cp, false> __result)
4360b57cec5SDimitry Andric{
4370b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, _IsConst> _In;
4380b57cec5SDimitry Andric    typedef  typename _In::difference_type difference_type;
4390b57cec5SDimitry Andric    typedef typename _In::__storage_type __storage_type;
4400b57cec5SDimitry Andric    const int __bits_per_word = _In::__bits_per_word;
4410b57cec5SDimitry Andric    difference_type __n = __last - __first;
4420b57cec5SDimitry Andric    if (__n > 0)
4430b57cec5SDimitry Andric    {
4440b57cec5SDimitry Andric        // do first word
4450b57cec5SDimitry Andric        if (__first.__ctz_ != 0)
4460b57cec5SDimitry Andric        {
4470b57cec5SDimitry Andric            unsigned __clz = __bits_per_word - __first.__ctz_;
4480b57cec5SDimitry Andric            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
4490b57cec5SDimitry Andric            __n -= __dn;
4500b57cec5SDimitry Andric            __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
4510b57cec5SDimitry Andric            __storage_type __b = *__first.__seg_ & __m;
4520b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
4530b57cec5SDimitry Andric            *__result.__seg_ |= __b;
4540b57cec5SDimitry Andric            __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
4550b57cec5SDimitry Andric            __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_)  % __bits_per_word);
4560b57cec5SDimitry Andric            ++__first.__seg_;
4570b57cec5SDimitry Andric            // __first.__ctz_ = 0;
4580b57cec5SDimitry Andric        }
4590b57cec5SDimitry Andric        // __first.__ctz_ == 0;
4600b57cec5SDimitry Andric        // do middle words
4610b57cec5SDimitry Andric        __storage_type __nw = __n / __bits_per_word;
46261cfbce3SDimitry Andric        std::copy_n(std::__to_address(__first.__seg_), __nw, std::__to_address(__result.__seg_));
4630b57cec5SDimitry Andric        __n -= __nw * __bits_per_word;
4640b57cec5SDimitry Andric        __result.__seg_ += __nw;
4650b57cec5SDimitry Andric        // do last word
4660b57cec5SDimitry Andric        if (__n > 0)
4670b57cec5SDimitry Andric        {
4680b57cec5SDimitry Andric            __first.__seg_ += __nw;
4690b57cec5SDimitry Andric            __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
4700b57cec5SDimitry Andric            __storage_type __b = *__first.__seg_ & __m;
4710b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
4720b57cec5SDimitry Andric            *__result.__seg_ |= __b;
4730b57cec5SDimitry Andric            __result.__ctz_ = static_cast<unsigned>(__n);
4740b57cec5SDimitry Andric        }
4750b57cec5SDimitry Andric    }
4760b57cec5SDimitry Andric    return __result;
4770b57cec5SDimitry Andric}
4780b57cec5SDimitry Andric
4790b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
480bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false>
4810b57cec5SDimitry Andric__copy_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
4820b57cec5SDimitry Andric                                                       __bit_iterator<_Cp, false> __result)
4830b57cec5SDimitry Andric{
4840b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, _IsConst> _In;
4850b57cec5SDimitry Andric    typedef  typename _In::difference_type difference_type;
4860b57cec5SDimitry Andric    typedef typename _In::__storage_type __storage_type;
48761cfbce3SDimitry Andric    const int __bits_per_word = _In::__bits_per_word;
4880b57cec5SDimitry Andric    difference_type __n = __last - __first;
4890b57cec5SDimitry Andric    if (__n > 0)
4900b57cec5SDimitry Andric    {
4910b57cec5SDimitry Andric        // do first word
4920b57cec5SDimitry Andric        if (__first.__ctz_ != 0)
4930b57cec5SDimitry Andric        {
4940b57cec5SDimitry Andric            unsigned __clz_f = __bits_per_word - __first.__ctz_;
4950b57cec5SDimitry Andric            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
4960b57cec5SDimitry Andric            __n -= __dn;
4970b57cec5SDimitry Andric            __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
4980b57cec5SDimitry Andric            __storage_type __b = *__first.__seg_ & __m;
4990b57cec5SDimitry Andric            unsigned __clz_r = __bits_per_word - __result.__ctz_;
5000b57cec5SDimitry Andric            __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
5010b57cec5SDimitry Andric            __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
5020b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
5030b57cec5SDimitry Andric            if (__result.__ctz_ > __first.__ctz_)
5040b57cec5SDimitry Andric                *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_);
5050b57cec5SDimitry Andric            else
5060b57cec5SDimitry Andric                *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_);
5070b57cec5SDimitry Andric            __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;
5080b57cec5SDimitry Andric            __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_)  % __bits_per_word);
5090b57cec5SDimitry Andric            __dn -= __ddn;
5100b57cec5SDimitry Andric            if (__dn > 0)
5110b57cec5SDimitry Andric            {
5120b57cec5SDimitry Andric                __m = ~__storage_type(0) >> (__bits_per_word - __dn);
5130b57cec5SDimitry Andric                *__result.__seg_ &= ~__m;
5140b57cec5SDimitry Andric                *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn);
5150b57cec5SDimitry Andric                __result.__ctz_ = static_cast<unsigned>(__dn);
5160b57cec5SDimitry Andric            }
5170b57cec5SDimitry Andric            ++__first.__seg_;
5180b57cec5SDimitry Andric            // __first.__ctz_ = 0;
5190b57cec5SDimitry Andric        }
5200b57cec5SDimitry Andric        // __first.__ctz_ == 0;
5210b57cec5SDimitry Andric        // do middle words
5220b57cec5SDimitry Andric        unsigned __clz_r = __bits_per_word - __result.__ctz_;
5230b57cec5SDimitry Andric        __storage_type __m = ~__storage_type(0) << __result.__ctz_;
5240b57cec5SDimitry Andric        for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_)
5250b57cec5SDimitry Andric        {
5260b57cec5SDimitry Andric            __storage_type __b = *__first.__seg_;
5270b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
5280b57cec5SDimitry Andric            *__result.__seg_ |= __b << __result.__ctz_;
5290b57cec5SDimitry Andric            ++__result.__seg_;
5300b57cec5SDimitry Andric            *__result.__seg_ &= __m;
5310b57cec5SDimitry Andric            *__result.__seg_ |= __b >> __clz_r;
5320b57cec5SDimitry Andric        }
5330b57cec5SDimitry Andric        // do last word
5340b57cec5SDimitry Andric        if (__n > 0)
5350b57cec5SDimitry Andric        {
5360b57cec5SDimitry Andric            __m = ~__storage_type(0) >> (__bits_per_word - __n);
5370b57cec5SDimitry Andric            __storage_type __b = *__first.__seg_ & __m;
5380b57cec5SDimitry Andric            __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r));
5390b57cec5SDimitry Andric            __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
5400b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
5410b57cec5SDimitry Andric            *__result.__seg_ |= __b << __result.__ctz_;
5420b57cec5SDimitry Andric            __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
5430b57cec5SDimitry Andric            __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_)  % __bits_per_word);
5440b57cec5SDimitry Andric            __n -= __dn;
5450b57cec5SDimitry Andric            if (__n > 0)
5460b57cec5SDimitry Andric            {
5470b57cec5SDimitry Andric                __m = ~__storage_type(0) >> (__bits_per_word - __n);
5480b57cec5SDimitry Andric                *__result.__seg_ &= ~__m;
5490b57cec5SDimitry Andric                *__result.__seg_ |= __b >> __dn;
5500b57cec5SDimitry Andric                __result.__ctz_ = static_cast<unsigned>(__n);
5510b57cec5SDimitry Andric            }
5520b57cec5SDimitry Andric        }
5530b57cec5SDimitry Andric    }
5540b57cec5SDimitry Andric    return __result;
5550b57cec5SDimitry Andric}
5560b57cec5SDimitry Andric
5570b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
558bdd1243dSDimitry Andricinline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
5590b57cec5SDimitry Andric__bit_iterator<_Cp, false>
5600b57cec5SDimitry Andriccopy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
5610b57cec5SDimitry Andric{
5620b57cec5SDimitry Andric    if (__first.__ctz_ == __result.__ctz_)
563e8d8bef9SDimitry Andric        return _VSTD::__copy_aligned(__first, __last, __result);
564e8d8bef9SDimitry Andric    return _VSTD::__copy_unaligned(__first, __last, __result);
5650b57cec5SDimitry Andric}
5660b57cec5SDimitry Andric
5670b57cec5SDimitry Andric// copy_backward
5680b57cec5SDimitry Andric
5690b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
570bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false>
5710b57cec5SDimitry Andric__copy_backward_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
5720b57cec5SDimitry Andric                                                     __bit_iterator<_Cp, false> __result)
5730b57cec5SDimitry Andric{
5740b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, _IsConst> _In;
5750b57cec5SDimitry Andric    typedef  typename _In::difference_type difference_type;
5760b57cec5SDimitry Andric    typedef typename _In::__storage_type __storage_type;
5770b57cec5SDimitry Andric    const int __bits_per_word = _In::__bits_per_word;
5780b57cec5SDimitry Andric    difference_type __n = __last - __first;
5790b57cec5SDimitry Andric    if (__n > 0)
5800b57cec5SDimitry Andric    {
5810b57cec5SDimitry Andric        // do first word
5820b57cec5SDimitry Andric        if (__last.__ctz_ != 0)
5830b57cec5SDimitry Andric        {
5840b57cec5SDimitry Andric            difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n);
5850b57cec5SDimitry Andric            __n -= __dn;
5860b57cec5SDimitry Andric            unsigned __clz = __bits_per_word - __last.__ctz_;
5870b57cec5SDimitry Andric            __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz);
5880b57cec5SDimitry Andric            __storage_type __b = *__last.__seg_ & __m;
5890b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
5900b57cec5SDimitry Andric            *__result.__seg_ |= __b;
5910b57cec5SDimitry Andric            __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) +
5920b57cec5SDimitry Andric                                                       __result.__ctz_)  % __bits_per_word);
5930b57cec5SDimitry Andric            // __last.__ctz_ = 0
5940b57cec5SDimitry Andric         }
5950b57cec5SDimitry Andric        // __last.__ctz_ == 0 || __n == 0
5960b57cec5SDimitry Andric        // __result.__ctz_ == 0 || __n == 0
5970b57cec5SDimitry Andric        // do middle words
5980b57cec5SDimitry Andric        __storage_type __nw = __n / __bits_per_word;
5990b57cec5SDimitry Andric        __result.__seg_ -= __nw;
6000b57cec5SDimitry Andric        __last.__seg_ -= __nw;
60161cfbce3SDimitry Andric        std::copy_n(std::__to_address(__last.__seg_), __nw, std::__to_address(__result.__seg_));
6020b57cec5SDimitry Andric        __n -= __nw * __bits_per_word;
6030b57cec5SDimitry Andric        // do last word
6040b57cec5SDimitry Andric        if (__n > 0)
6050b57cec5SDimitry Andric        {
6060b57cec5SDimitry Andric            __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n);
6070b57cec5SDimitry Andric            __storage_type __b = *--__last.__seg_ & __m;
6080b57cec5SDimitry Andric            *--__result.__seg_ &= ~__m;
6090b57cec5SDimitry Andric            *__result.__seg_ |= __b;
6100b57cec5SDimitry Andric            __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));
6110b57cec5SDimitry Andric        }
6120b57cec5SDimitry Andric    }
6130b57cec5SDimitry Andric    return __result;
6140b57cec5SDimitry Andric}
6150b57cec5SDimitry Andric
6160b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
617bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false>
6180b57cec5SDimitry Andric__copy_backward_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
6190b57cec5SDimitry Andric                                                       __bit_iterator<_Cp, false> __result)
6200b57cec5SDimitry Andric{
6210b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, _IsConst> _In;
6220b57cec5SDimitry Andric    typedef  typename _In::difference_type difference_type;
6230b57cec5SDimitry Andric    typedef typename _In::__storage_type __storage_type;
6240b57cec5SDimitry Andric    const int __bits_per_word = _In::__bits_per_word;
6250b57cec5SDimitry Andric    difference_type __n = __last - __first;
6260b57cec5SDimitry Andric    if (__n > 0)
6270b57cec5SDimitry Andric    {
6280b57cec5SDimitry Andric        // do first word
6290b57cec5SDimitry Andric        if (__last.__ctz_ != 0)
6300b57cec5SDimitry Andric        {
6310b57cec5SDimitry Andric            difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n);
6320b57cec5SDimitry Andric            __n -= __dn;
6330b57cec5SDimitry Andric            unsigned __clz_l = __bits_per_word - __last.__ctz_;
6340b57cec5SDimitry Andric            __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l);
6350b57cec5SDimitry Andric            __storage_type __b = *__last.__seg_ & __m;
6360b57cec5SDimitry Andric            unsigned __clz_r = __bits_per_word - __result.__ctz_;
6370b57cec5SDimitry Andric            __storage_type __ddn = _VSTD::min(__dn, static_cast<difference_type>(__result.__ctz_));
6380b57cec5SDimitry Andric            if (__ddn > 0)
6390b57cec5SDimitry Andric            {
6400b57cec5SDimitry Andric                __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r);
6410b57cec5SDimitry Andric                *__result.__seg_ &= ~__m;
6420b57cec5SDimitry Andric                if (__result.__ctz_ > __last.__ctz_)
6430b57cec5SDimitry Andric                    *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);
6440b57cec5SDimitry Andric                else
6450b57cec5SDimitry Andric                    *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_);
6460b57cec5SDimitry Andric                __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) +
6470b57cec5SDimitry Andric                                                         __result.__ctz_)  % __bits_per_word);
6480b57cec5SDimitry Andric                __dn -= __ddn;
6490b57cec5SDimitry Andric            }
6500b57cec5SDimitry Andric            if (__dn > 0)
6510b57cec5SDimitry Andric            {
6520b57cec5SDimitry Andric                // __result.__ctz_ == 0
6530b57cec5SDimitry Andric                --__result.__seg_;
6540b57cec5SDimitry Andric                __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1));
6550b57cec5SDimitry Andric                __m = ~__storage_type(0) << __result.__ctz_;
6560b57cec5SDimitry Andric                *__result.__seg_ &= ~__m;
6570b57cec5SDimitry Andric                __last.__ctz_ -= __dn + __ddn;
6580b57cec5SDimitry Andric                *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);
6590b57cec5SDimitry Andric            }
6600b57cec5SDimitry Andric            // __last.__ctz_ = 0
6610b57cec5SDimitry Andric         }
6620b57cec5SDimitry Andric        // __last.__ctz_ == 0 || __n == 0
6630b57cec5SDimitry Andric        // __result.__ctz_ != 0 || __n == 0
6640b57cec5SDimitry Andric        // do middle words
6650b57cec5SDimitry Andric        unsigned __clz_r = __bits_per_word - __result.__ctz_;
6660b57cec5SDimitry Andric        __storage_type __m = ~__storage_type(0) >> __clz_r;
6670b57cec5SDimitry Andric        for (; __n >= __bits_per_word; __n -= __bits_per_word)
6680b57cec5SDimitry Andric        {
6690b57cec5SDimitry Andric            __storage_type __b = *--__last.__seg_;
6700b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
6710b57cec5SDimitry Andric            *__result.__seg_ |= __b >> __clz_r;
6720b57cec5SDimitry Andric            *--__result.__seg_ &= __m;
6730b57cec5SDimitry Andric            *__result.__seg_ |= __b << __result.__ctz_;
6740b57cec5SDimitry Andric        }
6750b57cec5SDimitry Andric        // do last word
6760b57cec5SDimitry Andric        if (__n > 0)
6770b57cec5SDimitry Andric        {
6780b57cec5SDimitry Andric            __m = ~__storage_type(0) << (__bits_per_word - __n);
6790b57cec5SDimitry Andric            __storage_type __b = *--__last.__seg_ & __m;
6800b57cec5SDimitry Andric            __clz_r = __bits_per_word - __result.__ctz_;
6810b57cec5SDimitry Andric            __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__result.__ctz_));
6820b57cec5SDimitry Andric            __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r);
6830b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
6840b57cec5SDimitry Andric            *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_);
6850b57cec5SDimitry Andric            __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) +
6860b57cec5SDimitry Andric                                                     __result.__ctz_)  % __bits_per_word);
6870b57cec5SDimitry Andric            __n -= __dn;
6880b57cec5SDimitry Andric            if (__n > 0)
6890b57cec5SDimitry Andric            {
6900b57cec5SDimitry Andric                // __result.__ctz_ == 0
6910b57cec5SDimitry Andric                --__result.__seg_;
6920b57cec5SDimitry Andric                __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));
6930b57cec5SDimitry Andric                __m = ~__storage_type(0) << __result.__ctz_;
6940b57cec5SDimitry Andric                *__result.__seg_ &= ~__m;
6950b57cec5SDimitry Andric                *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn));
6960b57cec5SDimitry Andric            }
6970b57cec5SDimitry Andric        }
6980b57cec5SDimitry Andric    }
6990b57cec5SDimitry Andric    return __result;
7000b57cec5SDimitry Andric}
7010b57cec5SDimitry Andric
7020b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
703bdd1243dSDimitry Andricinline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
7040b57cec5SDimitry Andric__bit_iterator<_Cp, false>
7050b57cec5SDimitry Andriccopy_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
7060b57cec5SDimitry Andric{
7070b57cec5SDimitry Andric    if (__last.__ctz_ == __result.__ctz_)
708e8d8bef9SDimitry Andric        return _VSTD::__copy_backward_aligned(__first, __last, __result);
709e8d8bef9SDimitry Andric    return _VSTD::__copy_backward_unaligned(__first, __last, __result);
7100b57cec5SDimitry Andric}
7110b57cec5SDimitry Andric
7120b57cec5SDimitry Andric// move
7130b57cec5SDimitry Andric
7140b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
7150b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY
7160b57cec5SDimitry Andric__bit_iterator<_Cp, false>
7170b57cec5SDimitry Andricmove(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
7180b57cec5SDimitry Andric{
7190b57cec5SDimitry Andric    return _VSTD::copy(__first, __last, __result);
7200b57cec5SDimitry Andric}
7210b57cec5SDimitry Andric
7220b57cec5SDimitry Andric// move_backward
7230b57cec5SDimitry Andric
7240b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst>
7250b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY
7260b57cec5SDimitry Andric__bit_iterator<_Cp, false>
7270b57cec5SDimitry Andricmove_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
7280b57cec5SDimitry Andric{
7290b57cec5SDimitry Andric    return _VSTD::copy_backward(__first, __last, __result);
7300b57cec5SDimitry Andric}
7310b57cec5SDimitry Andric
7320b57cec5SDimitry Andric// swap_ranges
7330b57cec5SDimitry Andric
734*06c3fb27SDimitry Andrictemplate <class _Cl, class _Cr>
735*06c3fb27SDimitry Andric_LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cr, false>
736*06c3fb27SDimitry Andric__swap_ranges_aligned(__bit_iterator<_Cl, false> __first, __bit_iterator<_Cl, false> __last,
737*06c3fb27SDimitry Andric                      __bit_iterator<_Cr, false> __result)
7380b57cec5SDimitry Andric{
739*06c3fb27SDimitry Andric    typedef __bit_iterator<_Cl, false> _I1;
7400b57cec5SDimitry Andric    typedef  typename _I1::difference_type difference_type;
7410b57cec5SDimitry Andric    typedef typename _I1::__storage_type __storage_type;
7420b57cec5SDimitry Andric    const int __bits_per_word = _I1::__bits_per_word;
7430b57cec5SDimitry Andric    difference_type __n = __last - __first;
7440b57cec5SDimitry Andric    if (__n > 0)
7450b57cec5SDimitry Andric    {
7460b57cec5SDimitry Andric        // do first word
7470b57cec5SDimitry Andric        if (__first.__ctz_ != 0)
7480b57cec5SDimitry Andric        {
7490b57cec5SDimitry Andric            unsigned __clz = __bits_per_word - __first.__ctz_;
7500b57cec5SDimitry Andric            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
7510b57cec5SDimitry Andric            __n -= __dn;
7520b57cec5SDimitry Andric            __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
7530b57cec5SDimitry Andric            __storage_type __b1 = *__first.__seg_ & __m;
7540b57cec5SDimitry Andric            *__first.__seg_ &= ~__m;
7550b57cec5SDimitry Andric            __storage_type __b2 = *__result.__seg_ & __m;
7560b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
7570b57cec5SDimitry Andric            *__result.__seg_ |= __b1;
7580b57cec5SDimitry Andric            *__first.__seg_  |= __b2;
7590b57cec5SDimitry Andric            __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
7600b57cec5SDimitry Andric            __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_)  % __bits_per_word);
7610b57cec5SDimitry Andric            ++__first.__seg_;
7620b57cec5SDimitry Andric            // __first.__ctz_ = 0;
7630b57cec5SDimitry Andric        }
7640b57cec5SDimitry Andric        // __first.__ctz_ == 0;
7650b57cec5SDimitry Andric        // do middle words
7660b57cec5SDimitry Andric        for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_)
7670b57cec5SDimitry Andric            swap(*__first.__seg_, *__result.__seg_);
7680b57cec5SDimitry Andric        // do last word
7690b57cec5SDimitry Andric        if (__n > 0)
7700b57cec5SDimitry Andric        {
7710b57cec5SDimitry Andric            __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
7720b57cec5SDimitry Andric            __storage_type __b1 = *__first.__seg_ & __m;
7730b57cec5SDimitry Andric            *__first.__seg_ &= ~__m;
7740b57cec5SDimitry Andric            __storage_type __b2 = *__result.__seg_ & __m;
7750b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
7760b57cec5SDimitry Andric            *__result.__seg_ |= __b1;
7770b57cec5SDimitry Andric            *__first.__seg_  |= __b2;
7780b57cec5SDimitry Andric            __result.__ctz_ = static_cast<unsigned>(__n);
7790b57cec5SDimitry Andric        }
7800b57cec5SDimitry Andric    }
7810b57cec5SDimitry Andric    return __result;
7820b57cec5SDimitry Andric}
7830b57cec5SDimitry Andric
784*06c3fb27SDimitry Andrictemplate <class _Cl, class _Cr>
785*06c3fb27SDimitry Andric_LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cr, false>
786*06c3fb27SDimitry Andric__swap_ranges_unaligned(__bit_iterator<_Cl, false> __first, __bit_iterator<_Cl, false> __last,
787*06c3fb27SDimitry Andric                        __bit_iterator<_Cr, false> __result)
7880b57cec5SDimitry Andric{
789*06c3fb27SDimitry Andric    typedef __bit_iterator<_Cl, false> _I1;
7900b57cec5SDimitry Andric    typedef  typename _I1::difference_type difference_type;
7910b57cec5SDimitry Andric    typedef typename _I1::__storage_type __storage_type;
7920b57cec5SDimitry Andric    const int __bits_per_word = _I1::__bits_per_word;
7930b57cec5SDimitry Andric    difference_type __n = __last - __first;
7940b57cec5SDimitry Andric    if (__n > 0)
7950b57cec5SDimitry Andric    {
7960b57cec5SDimitry Andric        // do first word
7970b57cec5SDimitry Andric        if (__first.__ctz_ != 0)
7980b57cec5SDimitry Andric        {
7990b57cec5SDimitry Andric            unsigned __clz_f = __bits_per_word - __first.__ctz_;
8000b57cec5SDimitry Andric            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
8010b57cec5SDimitry Andric            __n -= __dn;
8020b57cec5SDimitry Andric            __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
8030b57cec5SDimitry Andric            __storage_type __b1 = *__first.__seg_ & __m;
8040b57cec5SDimitry Andric            *__first.__seg_ &= ~__m;
8050b57cec5SDimitry Andric            unsigned __clz_r = __bits_per_word - __result.__ctz_;
8060b57cec5SDimitry Andric            __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
8070b57cec5SDimitry Andric            __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
8080b57cec5SDimitry Andric            __storage_type __b2 = *__result.__seg_ & __m;
8090b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
8100b57cec5SDimitry Andric            if (__result.__ctz_ > __first.__ctz_)
8110b57cec5SDimitry Andric            {
8120b57cec5SDimitry Andric                unsigned __s = __result.__ctz_ - __first.__ctz_;
8130b57cec5SDimitry Andric                *__result.__seg_ |= __b1 << __s;
8140b57cec5SDimitry Andric                *__first.__seg_  |= __b2 >> __s;
8150b57cec5SDimitry Andric            }
8160b57cec5SDimitry Andric            else
8170b57cec5SDimitry Andric            {
8180b57cec5SDimitry Andric                unsigned __s = __first.__ctz_ - __result.__ctz_;
8190b57cec5SDimitry Andric                *__result.__seg_ |= __b1 >> __s;
8200b57cec5SDimitry Andric                *__first.__seg_  |= __b2 << __s;
8210b57cec5SDimitry Andric            }
8220b57cec5SDimitry Andric            __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;
8230b57cec5SDimitry Andric            __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_)  % __bits_per_word);
8240b57cec5SDimitry Andric            __dn -= __ddn;
8250b57cec5SDimitry Andric            if (__dn > 0)
8260b57cec5SDimitry Andric            {
8270b57cec5SDimitry Andric                __m = ~__storage_type(0) >> (__bits_per_word - __dn);
8280b57cec5SDimitry Andric                __b2 = *__result.__seg_ & __m;
8290b57cec5SDimitry Andric                *__result.__seg_ &= ~__m;
8300b57cec5SDimitry Andric                unsigned __s = __first.__ctz_ + __ddn;
8310b57cec5SDimitry Andric                *__result.__seg_ |= __b1 >> __s;
8320b57cec5SDimitry Andric                *__first.__seg_  |= __b2 << __s;
8330b57cec5SDimitry Andric                __result.__ctz_ = static_cast<unsigned>(__dn);
8340b57cec5SDimitry Andric            }
8350b57cec5SDimitry Andric            ++__first.__seg_;
8360b57cec5SDimitry Andric            // __first.__ctz_ = 0;
8370b57cec5SDimitry Andric        }
8380b57cec5SDimitry Andric        // __first.__ctz_ == 0;
8390b57cec5SDimitry Andric        // do middle words
8400b57cec5SDimitry Andric        __storage_type __m = ~__storage_type(0) << __result.__ctz_;
8410b57cec5SDimitry Andric        unsigned __clz_r = __bits_per_word - __result.__ctz_;
8420b57cec5SDimitry Andric        for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_)
8430b57cec5SDimitry Andric        {
8440b57cec5SDimitry Andric            __storage_type __b1 = *__first.__seg_;
8450b57cec5SDimitry Andric            __storage_type __b2 = *__result.__seg_ & __m;
8460b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
8470b57cec5SDimitry Andric            *__result.__seg_ |= __b1 << __result.__ctz_;
8480b57cec5SDimitry Andric            *__first.__seg_  = __b2 >> __result.__ctz_;
8490b57cec5SDimitry Andric            ++__result.__seg_;
8500b57cec5SDimitry Andric            __b2 = *__result.__seg_ & ~__m;
8510b57cec5SDimitry Andric            *__result.__seg_ &= __m;
8520b57cec5SDimitry Andric            *__result.__seg_ |= __b1 >> __clz_r;
8530b57cec5SDimitry Andric            *__first.__seg_  |= __b2 << __clz_r;
8540b57cec5SDimitry Andric        }
8550b57cec5SDimitry Andric        // do last word
8560b57cec5SDimitry Andric        if (__n > 0)
8570b57cec5SDimitry Andric        {
8580b57cec5SDimitry Andric            __m = ~__storage_type(0) >> (__bits_per_word - __n);
8590b57cec5SDimitry Andric            __storage_type __b1 = *__first.__seg_ & __m;
8600b57cec5SDimitry Andric            *__first.__seg_ &= ~__m;
8610b57cec5SDimitry Andric            __storage_type __dn = _VSTD::min<__storage_type>(__n, __clz_r);
8620b57cec5SDimitry Andric            __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
8630b57cec5SDimitry Andric            __storage_type __b2 = *__result.__seg_ & __m;
8640b57cec5SDimitry Andric            *__result.__seg_ &= ~__m;
8650b57cec5SDimitry Andric            *__result.__seg_ |= __b1 << __result.__ctz_;
8660b57cec5SDimitry Andric            *__first.__seg_  |= __b2 >> __result.__ctz_;
8670b57cec5SDimitry Andric            __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
8680b57cec5SDimitry Andric            __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_)  % __bits_per_word);
8690b57cec5SDimitry Andric            __n -= __dn;
8700b57cec5SDimitry Andric            if (__n > 0)
8710b57cec5SDimitry Andric            {
8720b57cec5SDimitry Andric                __m = ~__storage_type(0) >> (__bits_per_word - __n);
8730b57cec5SDimitry Andric                __b2 = *__result.__seg_ & __m;
8740b57cec5SDimitry Andric                *__result.__seg_ &= ~__m;
8750b57cec5SDimitry Andric                *__result.__seg_ |= __b1 >> __dn;
8760b57cec5SDimitry Andric                *__first.__seg_  |= __b2 << __dn;
8770b57cec5SDimitry Andric                __result.__ctz_ = static_cast<unsigned>(__n);
8780b57cec5SDimitry Andric            }
8790b57cec5SDimitry Andric        }
8800b57cec5SDimitry Andric    }
8810b57cec5SDimitry Andric    return __result;
8820b57cec5SDimitry Andric}
8830b57cec5SDimitry Andric
884*06c3fb27SDimitry Andrictemplate <class _Cl, class _Cr>
8850b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY
886*06c3fb27SDimitry Andric__bit_iterator<_Cr, false>
887*06c3fb27SDimitry Andricswap_ranges(__bit_iterator<_Cl, false> __first1, __bit_iterator<_Cl, false> __last1,
888*06c3fb27SDimitry Andric            __bit_iterator<_Cr, false> __first2)
8890b57cec5SDimitry Andric{
8900b57cec5SDimitry Andric    if (__first1.__ctz_ == __first2.__ctz_)
891e8d8bef9SDimitry Andric        return _VSTD::__swap_ranges_aligned(__first1, __last1, __first2);
892e8d8bef9SDimitry Andric    return _VSTD::__swap_ranges_unaligned(__first1, __last1, __first2);
8930b57cec5SDimitry Andric}
8940b57cec5SDimitry Andric
8950b57cec5SDimitry Andric// rotate
8960b57cec5SDimitry Andric
8970b57cec5SDimitry Andrictemplate <class _Cp>
8980b57cec5SDimitry Andricstruct __bit_array
8990b57cec5SDimitry Andric{
9000b57cec5SDimitry Andric    typedef typename _Cp::difference_type difference_type;
9010b57cec5SDimitry Andric    typedef typename _Cp::__storage_type  __storage_type;
9020b57cec5SDimitry Andric    typedef typename _Cp::__storage_pointer __storage_pointer;
9030b57cec5SDimitry Andric    typedef typename _Cp::iterator        iterator;
9040b57cec5SDimitry Andric    static const unsigned __bits_per_word = _Cp::__bits_per_word;
9050b57cec5SDimitry Andric    static const unsigned _Np = 4;
9060b57cec5SDimitry Andric
9070b57cec5SDimitry Andric    difference_type __size_;
9080b57cec5SDimitry Andric    __storage_type __word_[_Np];
9090b57cec5SDimitry Andric
910bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 static difference_type capacity()
9110b57cec5SDimitry Andric        {return static_cast<difference_type>(_Np * __bits_per_word);}
912bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit __bit_array(difference_type __s) : __size_(__s) {
91361cfbce3SDimitry Andric        if (__libcpp_is_constant_evaluated()) {
91461cfbce3SDimitry Andric            for (size_t __i = 0; __i != __bit_array<_Cp>::_Np; ++__i)
91561cfbce3SDimitry Andric                std::__construct_at(__word_ + __i, 0);
91661cfbce3SDimitry Andric        }
91761cfbce3SDimitry Andric    }
918bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator begin()
9190b57cec5SDimitry Andric    {
9200b57cec5SDimitry Andric        return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]), 0);
9210b57cec5SDimitry Andric    }
922bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator end()
9230b57cec5SDimitry Andric    {
9240b57cec5SDimitry Andric        return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]) + __size_ / __bits_per_word,
9250b57cec5SDimitry Andric                                                  static_cast<unsigned>(__size_ % __bits_per_word));
9260b57cec5SDimitry Andric    }
9270b57cec5SDimitry Andric};
9280b57cec5SDimitry Andric
9290b57cec5SDimitry Andrictemplate <class _Cp>
930bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false>
9310b57cec5SDimitry Andricrotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last)
9320b57cec5SDimitry Andric{
9330b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, false> _I1;
9340b57cec5SDimitry Andric    typedef  typename _I1::difference_type difference_type;
9350b57cec5SDimitry Andric    difference_type __d1 = __middle - __first;
9360b57cec5SDimitry Andric    difference_type __d2 = __last - __middle;
9370b57cec5SDimitry Andric    _I1 __r = __first + __d2;
9380b57cec5SDimitry Andric    while (__d1 != 0 && __d2 != 0)
9390b57cec5SDimitry Andric    {
9400b57cec5SDimitry Andric        if (__d1 <= __d2)
9410b57cec5SDimitry Andric        {
9420b57cec5SDimitry Andric            if (__d1 <= __bit_array<_Cp>::capacity())
9430b57cec5SDimitry Andric            {
9440b57cec5SDimitry Andric                __bit_array<_Cp> __b(__d1);
9450b57cec5SDimitry Andric                _VSTD::copy(__first, __middle, __b.begin());
9460b57cec5SDimitry Andric                _VSTD::copy(__b.begin(), __b.end(), _VSTD::copy(__middle, __last, __first));
9470b57cec5SDimitry Andric                break;
9480b57cec5SDimitry Andric            }
9490b57cec5SDimitry Andric            else
9500b57cec5SDimitry Andric            {
9510b57cec5SDimitry Andric                __bit_iterator<_Cp, false> __mp = _VSTD::swap_ranges(__first, __middle, __middle);
9520b57cec5SDimitry Andric                __first = __middle;
9530b57cec5SDimitry Andric                __middle = __mp;
9540b57cec5SDimitry Andric                __d2 -= __d1;
9550b57cec5SDimitry Andric            }
9560b57cec5SDimitry Andric        }
9570b57cec5SDimitry Andric        else
9580b57cec5SDimitry Andric        {
9590b57cec5SDimitry Andric            if (__d2 <= __bit_array<_Cp>::capacity())
9600b57cec5SDimitry Andric            {
9610b57cec5SDimitry Andric                __bit_array<_Cp> __b(__d2);
9620b57cec5SDimitry Andric                _VSTD::copy(__middle, __last, __b.begin());
9630b57cec5SDimitry Andric                _VSTD::copy_backward(__b.begin(), __b.end(), _VSTD::copy_backward(__first, __middle, __last));
9640b57cec5SDimitry Andric                break;
9650b57cec5SDimitry Andric            }
9660b57cec5SDimitry Andric            else
9670b57cec5SDimitry Andric            {
9680b57cec5SDimitry Andric                __bit_iterator<_Cp, false> __mp = __first + __d2;
9690b57cec5SDimitry Andric                _VSTD::swap_ranges(__first, __mp, __middle);
9700b57cec5SDimitry Andric                __first = __mp;
9710b57cec5SDimitry Andric                __d1 -= __d2;
9720b57cec5SDimitry Andric            }
9730b57cec5SDimitry Andric        }
9740b57cec5SDimitry Andric    }
9750b57cec5SDimitry Andric    return __r;
9760b57cec5SDimitry Andric}
9770b57cec5SDimitry Andric
9780b57cec5SDimitry Andric// equal
9790b57cec5SDimitry Andric
9800b57cec5SDimitry Andrictemplate <class _Cp, bool _IC1, bool _IC2>
981bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool
9820b57cec5SDimitry Andric__equal_unaligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1,
9830b57cec5SDimitry Andric                  __bit_iterator<_Cp, _IC2> __first2)
9840b57cec5SDimitry Andric{
9850b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, _IC1> _It;
9860b57cec5SDimitry Andric    typedef  typename _It::difference_type difference_type;
9870b57cec5SDimitry Andric    typedef typename _It::__storage_type __storage_type;
98861cfbce3SDimitry Andric    const int __bits_per_word = _It::__bits_per_word;
9890b57cec5SDimitry Andric    difference_type __n = __last1 - __first1;
9900b57cec5SDimitry Andric    if (__n > 0)
9910b57cec5SDimitry Andric    {
9920b57cec5SDimitry Andric        // do first word
9930b57cec5SDimitry Andric        if (__first1.__ctz_ != 0)
9940b57cec5SDimitry Andric        {
9950b57cec5SDimitry Andric            unsigned __clz_f = __bits_per_word - __first1.__ctz_;
9960b57cec5SDimitry Andric            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
9970b57cec5SDimitry Andric            __n -= __dn;
9980b57cec5SDimitry Andric            __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
9990b57cec5SDimitry Andric            __storage_type __b = *__first1.__seg_ & __m;
10000b57cec5SDimitry Andric            unsigned __clz_r = __bits_per_word - __first2.__ctz_;
10010b57cec5SDimitry Andric            __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
10020b57cec5SDimitry Andric            __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
10030b57cec5SDimitry Andric            if (__first2.__ctz_ > __first1.__ctz_)
10040b57cec5SDimitry Andric            {
10050b57cec5SDimitry Andric                if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_)))
10060b57cec5SDimitry Andric                    return false;
10070b57cec5SDimitry Andric            }
10080b57cec5SDimitry Andric            else
10090b57cec5SDimitry Andric            {
10100b57cec5SDimitry Andric                if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_)))
10110b57cec5SDimitry Andric                    return false;
10120b57cec5SDimitry Andric            }
10130b57cec5SDimitry Andric            __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word;
10140b57cec5SDimitry Andric            __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_)  % __bits_per_word);
10150b57cec5SDimitry Andric            __dn -= __ddn;
10160b57cec5SDimitry Andric            if (__dn > 0)
10170b57cec5SDimitry Andric            {
10180b57cec5SDimitry Andric                __m = ~__storage_type(0) >> (__bits_per_word - __dn);
10190b57cec5SDimitry Andric                if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn)))
10200b57cec5SDimitry Andric                    return false;
10210b57cec5SDimitry Andric                __first2.__ctz_ = static_cast<unsigned>(__dn);
10220b57cec5SDimitry Andric            }
10230b57cec5SDimitry Andric            ++__first1.__seg_;
10240b57cec5SDimitry Andric            // __first1.__ctz_ = 0;
10250b57cec5SDimitry Andric        }
10260b57cec5SDimitry Andric        // __first1.__ctz_ == 0;
10270b57cec5SDimitry Andric        // do middle words
10280b57cec5SDimitry Andric        unsigned __clz_r = __bits_per_word - __first2.__ctz_;
10290b57cec5SDimitry Andric        __storage_type __m = ~__storage_type(0) << __first2.__ctz_;
10300b57cec5SDimitry Andric        for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_)
10310b57cec5SDimitry Andric        {
10320b57cec5SDimitry Andric            __storage_type __b = *__first1.__seg_;
10330b57cec5SDimitry Andric            if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_))
10340b57cec5SDimitry Andric                return false;
10350b57cec5SDimitry Andric            ++__first2.__seg_;
10360b57cec5SDimitry Andric            if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r))
10370b57cec5SDimitry Andric                return false;
10380b57cec5SDimitry Andric        }
10390b57cec5SDimitry Andric        // do last word
10400b57cec5SDimitry Andric        if (__n > 0)
10410b57cec5SDimitry Andric        {
10420b57cec5SDimitry Andric            __m = ~__storage_type(0) >> (__bits_per_word - __n);
10430b57cec5SDimitry Andric            __storage_type __b = *__first1.__seg_ & __m;
10440b57cec5SDimitry Andric            __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r));
10450b57cec5SDimitry Andric            __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
10460b57cec5SDimitry Andric            if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_))
10470b57cec5SDimitry Andric                return false;
10480b57cec5SDimitry Andric            __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word;
10490b57cec5SDimitry Andric            __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_)  % __bits_per_word);
10500b57cec5SDimitry Andric            __n -= __dn;
10510b57cec5SDimitry Andric            if (__n > 0)
10520b57cec5SDimitry Andric            {
10530b57cec5SDimitry Andric                __m = ~__storage_type(0) >> (__bits_per_word - __n);
10540b57cec5SDimitry Andric                if ((*__first2.__seg_ & __m) != (__b >> __dn))
10550b57cec5SDimitry Andric                    return false;
10560b57cec5SDimitry Andric            }
10570b57cec5SDimitry Andric        }
10580b57cec5SDimitry Andric    }
10590b57cec5SDimitry Andric    return true;
10600b57cec5SDimitry Andric}
10610b57cec5SDimitry Andric
10620b57cec5SDimitry Andrictemplate <class _Cp, bool _IC1, bool _IC2>
1063bdd1243dSDimitry Andric_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool
10640b57cec5SDimitry Andric__equal_aligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1,
10650b57cec5SDimitry Andric                __bit_iterator<_Cp, _IC2> __first2)
10660b57cec5SDimitry Andric{
10670b57cec5SDimitry Andric    typedef __bit_iterator<_Cp, _IC1> _It;
10680b57cec5SDimitry Andric    typedef  typename _It::difference_type difference_type;
10690b57cec5SDimitry Andric    typedef typename _It::__storage_type __storage_type;
107061cfbce3SDimitry Andric    const int __bits_per_word = _It::__bits_per_word;
10710b57cec5SDimitry Andric    difference_type __n = __last1 - __first1;
10720b57cec5SDimitry Andric    if (__n > 0)
10730b57cec5SDimitry Andric    {
10740b57cec5SDimitry Andric        // do first word
10750b57cec5SDimitry Andric        if (__first1.__ctz_ != 0)
10760b57cec5SDimitry Andric        {
10770b57cec5SDimitry Andric            unsigned __clz = __bits_per_word - __first1.__ctz_;
10780b57cec5SDimitry Andric            difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
10790b57cec5SDimitry Andric            __n -= __dn;
10800b57cec5SDimitry Andric            __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
10810b57cec5SDimitry Andric            if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))
10820b57cec5SDimitry Andric                return false;
10830b57cec5SDimitry Andric            ++__first2.__seg_;
10840b57cec5SDimitry Andric            ++__first1.__seg_;
10850b57cec5SDimitry Andric            // __first1.__ctz_ = 0;
10860b57cec5SDimitry Andric            // __first2.__ctz_ = 0;
10870b57cec5SDimitry Andric        }
10880b57cec5SDimitry Andric        // __first1.__ctz_ == 0;
10890b57cec5SDimitry Andric        // __first2.__ctz_ == 0;
10900b57cec5SDimitry Andric        // do middle words
10910b57cec5SDimitry Andric        for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_)
10920b57cec5SDimitry Andric            if (*__first2.__seg_ != *__first1.__seg_)
10930b57cec5SDimitry Andric                return false;
10940b57cec5SDimitry Andric        // do last word
10950b57cec5SDimitry Andric        if (__n > 0)
10960b57cec5SDimitry Andric        {
10970b57cec5SDimitry Andric            __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
10980b57cec5SDimitry Andric            if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))
10990b57cec5SDimitry Andric                return false;
11000b57cec5SDimitry Andric        }
11010b57cec5SDimitry Andric    }
11020b57cec5SDimitry Andric    return true;
11030b57cec5SDimitry Andric}
11040b57cec5SDimitry Andric
11050b57cec5SDimitry Andrictemplate <class _Cp, bool _IC1, bool _IC2>
1106bdd1243dSDimitry Andricinline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
11070b57cec5SDimitry Andricbool
11080b57cec5SDimitry Andricequal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2)
11090b57cec5SDimitry Andric{
11100b57cec5SDimitry Andric    if (__first1.__ctz_ == __first2.__ctz_)
1111e8d8bef9SDimitry Andric        return _VSTD::__equal_aligned(__first1, __last1, __first2);
1112e8d8bef9SDimitry Andric    return _VSTD::__equal_unaligned(__first1, __last1, __first2);
11130b57cec5SDimitry Andric}
11140b57cec5SDimitry Andric
11150b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst,
11160b57cec5SDimitry Andric          typename _Cp::__storage_type>
11170b57cec5SDimitry Andricclass __bit_iterator
11180b57cec5SDimitry Andric{
11190b57cec5SDimitry Andricpublic:
11200b57cec5SDimitry Andric    typedef typename _Cp::difference_type                                                          difference_type;
11210b57cec5SDimitry Andric    typedef bool                                                                                  value_type;
11220b57cec5SDimitry Andric    typedef __bit_iterator                                                                        pointer;
112381ad6265SDimitry Andric#ifndef _LIBCPP_ABI_BITSET_VECTOR_BOOL_CONST_SUBSCRIPT_RETURN_BOOL
1124bdd1243dSDimitry Andric    typedef __conditional_t<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> > reference;
112581ad6265SDimitry Andric#else
1126bdd1243dSDimitry Andric    using reference = __conditional_t<_IsConst, bool, __bit_reference<_Cp> >;
112781ad6265SDimitry Andric#endif
11280b57cec5SDimitry Andric    typedef random_access_iterator_tag                                                            iterator_category;
11290b57cec5SDimitry Andric
11300b57cec5SDimitry Andricprivate:
11310b57cec5SDimitry Andric    typedef typename _Cp::__storage_type                                           __storage_type;
1132bdd1243dSDimitry Andric    typedef __conditional_t<_IsConst, typename _Cp::__const_storage_pointer, typename _Cp::__storage_pointer>
1133bdd1243dSDimitry Andric        __storage_pointer;
11340b57cec5SDimitry Andric    static const unsigned __bits_per_word = _Cp::__bits_per_word;
11350b57cec5SDimitry Andric
11360b57cec5SDimitry Andric    __storage_pointer __seg_;
11370b57cec5SDimitry Andric    unsigned          __ctz_;
11380b57cec5SDimitry Andric
11390b57cec5SDimitry Andricpublic:
1140bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator() _NOEXCEPT
1141*06c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14
11420b57cec5SDimitry Andric    : __seg_(nullptr), __ctz_(0)
11430b57cec5SDimitry Andric#endif
11440b57cec5SDimitry Andric    {}
11450b57cec5SDimitry Andric
11464652422eSDimitry Andric    // When _IsConst=false, this is the copy constructor.
11474652422eSDimitry Andric    // It is non-trivial. Making it trivial would break ABI.
11484652422eSDimitry Andric    // When _IsConst=true, this is a converting constructor;
11494652422eSDimitry Andric    // the copy and move constructors are implicitly generated
11504652422eSDimitry Andric    // and trivial.
1151bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
11524652422eSDimitry Andric    __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT
11530b57cec5SDimitry Andric        : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {}
11540b57cec5SDimitry Andric
11554652422eSDimitry Andric    // When _IsConst=false, we have a user-provided copy constructor,
11564652422eSDimitry Andric    // so we must also provide a copy assignment operator because
11574652422eSDimitry Andric    // the implicit generation of a defaulted one is deprecated.
11584652422eSDimitry Andric    // When _IsConst=true, the assignment operators are
11594652422eSDimitry Andric    // implicitly generated and trivial.
1160bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
11614652422eSDimitry Andric    __bit_iterator& operator=(const _If<_IsConst, struct __private_nat, __bit_iterator>& __it) {
11624652422eSDimitry Andric        __seg_ = __it.__seg_;
11634652422eSDimitry Andric        __ctz_ = __it.__ctz_;
11644652422eSDimitry Andric        return *this;
11654652422eSDimitry Andric    }
116647395794SDimitry Andric
1167bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 reference operator*() const _NOEXCEPT {
1168bdd1243dSDimitry Andric        return __conditional_t<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >(
1169bdd1243dSDimitry Andric            __seg_, __storage_type(1) << __ctz_);
117081ad6265SDimitry Andric    }
11710b57cec5SDimitry Andric
1172bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator++()
11730b57cec5SDimitry Andric    {
11740b57cec5SDimitry Andric        if (__ctz_ != __bits_per_word-1)
11750b57cec5SDimitry Andric            ++__ctz_;
11760b57cec5SDimitry Andric        else
11770b57cec5SDimitry Andric        {
11780b57cec5SDimitry Andric            __ctz_ = 0;
11790b57cec5SDimitry Andric            ++__seg_;
11800b57cec5SDimitry Andric        }
11810b57cec5SDimitry Andric        return *this;
11820b57cec5SDimitry Andric    }
11830b57cec5SDimitry Andric
1184bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator++(int)
11850b57cec5SDimitry Andric    {
11860b57cec5SDimitry Andric        __bit_iterator __tmp = *this;
11870b57cec5SDimitry Andric        ++(*this);
11880b57cec5SDimitry Andric        return __tmp;
11890b57cec5SDimitry Andric    }
11900b57cec5SDimitry Andric
1191bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator--()
11920b57cec5SDimitry Andric    {
11930b57cec5SDimitry Andric        if (__ctz_ != 0)
11940b57cec5SDimitry Andric            --__ctz_;
11950b57cec5SDimitry Andric        else
11960b57cec5SDimitry Andric        {
11970b57cec5SDimitry Andric            __ctz_ = __bits_per_word - 1;
11980b57cec5SDimitry Andric            --__seg_;
11990b57cec5SDimitry Andric        }
12000b57cec5SDimitry Andric        return *this;
12010b57cec5SDimitry Andric    }
12020b57cec5SDimitry Andric
1203bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator--(int)
12040b57cec5SDimitry Andric    {
12050b57cec5SDimitry Andric        __bit_iterator __tmp = *this;
12060b57cec5SDimitry Andric        --(*this);
12070b57cec5SDimitry Andric        return __tmp;
12080b57cec5SDimitry Andric    }
12090b57cec5SDimitry Andric
1210bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator+=(difference_type __n)
12110b57cec5SDimitry Andric    {
12120b57cec5SDimitry Andric        if (__n >= 0)
12130b57cec5SDimitry Andric            __seg_ += (__n + __ctz_) / __bits_per_word;
12140b57cec5SDimitry Andric        else
12150b57cec5SDimitry Andric            __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1)
12160b57cec5SDimitry Andric                    / static_cast<difference_type>(__bits_per_word);
12170b57cec5SDimitry Andric        __n &= (__bits_per_word - 1);
12180b57cec5SDimitry Andric        __ctz_ = static_cast<unsigned>((__n + __ctz_)  % __bits_per_word);
12190b57cec5SDimitry Andric        return *this;
12200b57cec5SDimitry Andric    }
12210b57cec5SDimitry Andric
1222bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator& operator-=(difference_type __n)
12230b57cec5SDimitry Andric    {
12240b57cec5SDimitry Andric        return *this += -__n;
12250b57cec5SDimitry Andric    }
12260b57cec5SDimitry Andric
1227bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator+(difference_type __n) const
12280b57cec5SDimitry Andric    {
12290b57cec5SDimitry Andric        __bit_iterator __t(*this);
12300b57cec5SDimitry Andric        __t += __n;
12310b57cec5SDimitry Andric        return __t;
12320b57cec5SDimitry Andric    }
12330b57cec5SDimitry Andric
1234bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator operator-(difference_type __n) const
12350b57cec5SDimitry Andric    {
12360b57cec5SDimitry Andric        __bit_iterator __t(*this);
12370b57cec5SDimitry Andric        __t -= __n;
12380b57cec5SDimitry Andric        return __t;
12390b57cec5SDimitry Andric    }
12400b57cec5SDimitry Andric
1241bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
12420b57cec5SDimitry Andric    friend __bit_iterator operator+(difference_type __n, const __bit_iterator& __it) {return __it + __n;}
12430b57cec5SDimitry Andric
1244bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
12450b57cec5SDimitry Andric    friend difference_type operator-(const __bit_iterator& __x, const __bit_iterator& __y)
12460b57cec5SDimitry Andric        {return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;}
12470b57cec5SDimitry Andric
1248bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 reference operator[](difference_type __n) const {return *(*this + __n);}
12490b57cec5SDimitry Andric
1250bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool operator==(const __bit_iterator& __x, const __bit_iterator& __y)
12510b57cec5SDimitry Andric        {return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;}
12520b57cec5SDimitry Andric
1253bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool operator!=(const __bit_iterator& __x, const __bit_iterator& __y)
12540b57cec5SDimitry Andric        {return !(__x == __y);}
12550b57cec5SDimitry Andric
1256bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool operator<(const __bit_iterator& __x, const __bit_iterator& __y)
12570b57cec5SDimitry Andric        {return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);}
12580b57cec5SDimitry Andric
1259bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool operator>(const __bit_iterator& __x, const __bit_iterator& __y)
12600b57cec5SDimitry Andric        {return __y < __x;}
12610b57cec5SDimitry Andric
1262bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y)
12630b57cec5SDimitry Andric        {return !(__y < __x);}
12640b57cec5SDimitry Andric
1265bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y)
12660b57cec5SDimitry Andric        {return !(__x < __y);}
12670b57cec5SDimitry Andric
12680b57cec5SDimitry Andricprivate:
1269bdd1243dSDimitry Andric    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
127081ad6265SDimitry Andric    explicit __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT
12710b57cec5SDimitry Andric        : __seg_(__s), __ctz_(__ctz) {}
12720b57cec5SDimitry Andric
12730b57cec5SDimitry Andric    friend typename _Cp::__self;
12740b57cec5SDimitry Andric
12750b57cec5SDimitry Andric    friend class __bit_reference<_Cp>;
12760b57cec5SDimitry Andric    friend class __bit_const_reference<_Cp>;
12770b57cec5SDimitry Andric    friend class __bit_iterator<_Cp, true>;
12780b57cec5SDimitry Andric    template <class _Dp> friend struct __bit_array;
127961cfbce3SDimitry Andric    template <class _Dp>
1280bdd1243dSDimitry Andric    _LIBCPP_CONSTEXPR_SINCE_CXX20
128161cfbce3SDimitry Andric    friend void __fill_n_false(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n);
128261cfbce3SDimitry Andric
128361cfbce3SDimitry Andric    template <class _Dp>
1284bdd1243dSDimitry Andric    _LIBCPP_CONSTEXPR_SINCE_CXX20
128561cfbce3SDimitry Andric    friend void __fill_n_true(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n);
128661cfbce3SDimitry Andric
128761cfbce3SDimitry Andric    template <class _Dp, bool _IC>
1288bdd1243dSDimitry Andric    _LIBCPP_CONSTEXPR_SINCE_CXX20
128961cfbce3SDimitry Andric    friend __bit_iterator<_Dp, false> __copy_aligned(__bit_iterator<_Dp, _IC> __first,
12900b57cec5SDimitry Andric                                                     __bit_iterator<_Dp, _IC> __last,
12910b57cec5SDimitry Andric                                                     __bit_iterator<_Dp, false> __result);
129261cfbce3SDimitry Andric    template <class _Dp, bool _IC>
1293bdd1243dSDimitry Andric    _LIBCPP_CONSTEXPR_SINCE_CXX20
129461cfbce3SDimitry Andric    friend __bit_iterator<_Dp, false> __copy_unaligned(__bit_iterator<_Dp, _IC> __first,
12950b57cec5SDimitry Andric                                                       __bit_iterator<_Dp, _IC> __last,
12960b57cec5SDimitry Andric                                                       __bit_iterator<_Dp, false> __result);
129761cfbce3SDimitry Andric    template <class _Dp, bool _IC>
1298bdd1243dSDimitry Andric    _LIBCPP_CONSTEXPR_SINCE_CXX20
129961cfbce3SDimitry Andric    friend __bit_iterator<_Dp, false> copy(__bit_iterator<_Dp, _IC> __first,
13000b57cec5SDimitry Andric                                           __bit_iterator<_Dp, _IC> __last,
13010b57cec5SDimitry Andric                                           __bit_iterator<_Dp, false> __result);
130261cfbce3SDimitry Andric    template <class _Dp, bool _IC>
1303bdd1243dSDimitry Andric    _LIBCPP_CONSTEXPR_SINCE_CXX20
130461cfbce3SDimitry Andric    friend __bit_iterator<_Dp, false> __copy_backward_aligned(__bit_iterator<_Dp, _IC> __first,
13050b57cec5SDimitry Andric                                                              __bit_iterator<_Dp, _IC> __last,
13060b57cec5SDimitry Andric                                                              __bit_iterator<_Dp, false> __result);
130761cfbce3SDimitry Andric    template <class _Dp, bool _IC>
1308bdd1243dSDimitry Andric    _LIBCPP_CONSTEXPR_SINCE_CXX20
130961cfbce3SDimitry Andric    friend __bit_iterator<_Dp, false> __copy_backward_unaligned(__bit_iterator<_Dp, _IC> __first,
13100b57cec5SDimitry Andric                                                                __bit_iterator<_Dp, _IC> __last,
13110b57cec5SDimitry Andric                                                                __bit_iterator<_Dp, false> __result);
131261cfbce3SDimitry Andric    template <class _Dp, bool _IC>
1313bdd1243dSDimitry Andric    _LIBCPP_CONSTEXPR_SINCE_CXX20
131461cfbce3SDimitry Andric    friend __bit_iterator<_Dp, false> copy_backward(__bit_iterator<_Dp, _IC> __first,
13150b57cec5SDimitry Andric                                                    __bit_iterator<_Dp, _IC> __last,
13160b57cec5SDimitry Andric                                                    __bit_iterator<_Dp, false> __result);
1317*06c3fb27SDimitry Andric    template <class _Cl, class _Cr>friend __bit_iterator<_Cr, false> __swap_ranges_aligned(__bit_iterator<_Cl, false>,
1318*06c3fb27SDimitry Andric                                                                                           __bit_iterator<_Cl, false>,
1319*06c3fb27SDimitry Andric                                                                                           __bit_iterator<_Cr, false>);
1320*06c3fb27SDimitry Andric    template <class _Cl, class _Cr>friend __bit_iterator<_Cr, false> __swap_ranges_unaligned(__bit_iterator<_Cl, false>,
1321*06c3fb27SDimitry Andric                                                                                             __bit_iterator<_Cl, false>,
1322*06c3fb27SDimitry Andric                                                                                             __bit_iterator<_Cr, false>);
1323*06c3fb27SDimitry Andric    template <class _Cl, class _Cr>friend __bit_iterator<_Cr, false> swap_ranges(__bit_iterator<_Cl, false>,
1324*06c3fb27SDimitry Andric                                                                                 __bit_iterator<_Cl, false>,
1325*06c3fb27SDimitry Andric                                                                                 __bit_iterator<_Cr, false>);
132661cfbce3SDimitry Andric    template <class _Dp>
1327bdd1243dSDimitry Andric    _LIBCPP_CONSTEXPR_SINCE_CXX20
132861cfbce3SDimitry Andric    friend __bit_iterator<_Dp, false> rotate(__bit_iterator<_Dp, false>,
13290b57cec5SDimitry Andric                                             __bit_iterator<_Dp, false>,
13300b57cec5SDimitry Andric                                             __bit_iterator<_Dp, false>);
133161cfbce3SDimitry Andric    template <class _Dp, bool _IC1, bool _IC2>
1332bdd1243dSDimitry Andric    _LIBCPP_CONSTEXPR_SINCE_CXX20
133361cfbce3SDimitry Andric    friend bool __equal_aligned(__bit_iterator<_Dp, _IC1>,
13340b57cec5SDimitry Andric                                __bit_iterator<_Dp, _IC1>,
13350b57cec5SDimitry Andric                                __bit_iterator<_Dp, _IC2>);
133661cfbce3SDimitry Andric    template <class _Dp, bool _IC1, bool _IC2>
1337bdd1243dSDimitry Andric    _LIBCPP_CONSTEXPR_SINCE_CXX20
133861cfbce3SDimitry Andric    friend bool __equal_unaligned(__bit_iterator<_Dp, _IC1>,
13390b57cec5SDimitry Andric                                  __bit_iterator<_Dp, _IC1>,
13400b57cec5SDimitry Andric                                  __bit_iterator<_Dp, _IC2>);
134161cfbce3SDimitry Andric    template <class _Dp, bool _IC1, bool _IC2>
1342bdd1243dSDimitry Andric    _LIBCPP_CONSTEXPR_SINCE_CXX20
134361cfbce3SDimitry Andric    friend bool equal(__bit_iterator<_Dp, _IC1>,
13440b57cec5SDimitry Andric                      __bit_iterator<_Dp, _IC1>,
13450b57cec5SDimitry Andric                      __bit_iterator<_Dp, _IC2>);
134661cfbce3SDimitry Andric    template <class _Dp, bool _IC>
1347bdd1243dSDimitry Andric    _LIBCPP_CONSTEXPR_SINCE_CXX20
134861cfbce3SDimitry Andric    friend __bit_iterator<_Dp, _IC> __find_bool_true(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
134961cfbce3SDimitry Andric    template <class _Dp, bool _IC>
1350bdd1243dSDimitry Andric    _LIBCPP_CONSTEXPR_SINCE_CXX20
135161cfbce3SDimitry Andric    friend __bit_iterator<_Dp, _IC> __find_bool_false(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
13520b57cec5SDimitry Andric    template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type
1353bdd1243dSDimitry Andric    _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23
13540b57cec5SDimitry Andric                   __count_bool_true(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
13550b57cec5SDimitry Andric    template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type
13560b57cec5SDimitry Andric                   __count_bool_false(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
13570b57cec5SDimitry Andric};
13580b57cec5SDimitry Andric
13590b57cec5SDimitry Andric_LIBCPP_END_NAMESPACE_STD
13600b57cec5SDimitry Andric
13610b57cec5SDimitry Andric_LIBCPP_POP_MACROS
13620b57cec5SDimitry Andric
13630b57cec5SDimitry Andric#endif // _LIBCPP___BIT_REFERENCE
1364