1*0b57cec5SDimitry Andric// -*- C++ -*- 2*0b57cec5SDimitry Andric//===----------------------------------------------------------------------===// 3*0b57cec5SDimitry Andric// 4*0b57cec5SDimitry Andric// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5*0b57cec5SDimitry Andric// See https://llvm.org/LICENSE.txt for license information. 6*0b57cec5SDimitry Andric// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7*0b57cec5SDimitry Andric// 8*0b57cec5SDimitry Andric//===----------------------------------------------------------------------===// 9*0b57cec5SDimitry Andric 10*0b57cec5SDimitry Andric#ifndef _LIBCPP___BIT_REFERENCE 11*0b57cec5SDimitry Andric#define _LIBCPP___BIT_REFERENCE 12*0b57cec5SDimitry Andric 13*0b57cec5SDimitry Andric#include <__config> 14*0b57cec5SDimitry Andric#include <bit> 15*0b57cec5SDimitry Andric#include <algorithm> 16*0b57cec5SDimitry Andric 17*0b57cec5SDimitry Andric#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 18*0b57cec5SDimitry Andric#pragma GCC system_header 19*0b57cec5SDimitry Andric#endif 20*0b57cec5SDimitry Andric 21*0b57cec5SDimitry Andric_LIBCPP_PUSH_MACROS 22*0b57cec5SDimitry Andric#include <__undef_macros> 23*0b57cec5SDimitry Andric 24*0b57cec5SDimitry Andric 25*0b57cec5SDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD 26*0b57cec5SDimitry Andric 27*0b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst, typename _Cp::__storage_type = 0> class __bit_iterator; 28*0b57cec5SDimitry Andrictemplate <class _Cp> class __bit_const_reference; 29*0b57cec5SDimitry Andric 30*0b57cec5SDimitry Andrictemplate <class _Tp> 31*0b57cec5SDimitry Andricstruct __has_storage_type 32*0b57cec5SDimitry Andric{ 33*0b57cec5SDimitry Andric static const bool value = false; 34*0b57cec5SDimitry Andric}; 35*0b57cec5SDimitry Andric 36*0b57cec5SDimitry Andrictemplate <class _Cp, bool = __has_storage_type<_Cp>::value> 37*0b57cec5SDimitry Andricclass __bit_reference 38*0b57cec5SDimitry Andric{ 39*0b57cec5SDimitry Andric typedef typename _Cp::__storage_type __storage_type; 40*0b57cec5SDimitry Andric typedef typename _Cp::__storage_pointer __storage_pointer; 41*0b57cec5SDimitry Andric 42*0b57cec5SDimitry Andric __storage_pointer __seg_; 43*0b57cec5SDimitry Andric __storage_type __mask_; 44*0b57cec5SDimitry Andric 45*0b57cec5SDimitry Andric friend typename _Cp::__self; 46*0b57cec5SDimitry Andric 47*0b57cec5SDimitry Andric friend class __bit_const_reference<_Cp>; 48*0b57cec5SDimitry Andric friend class __bit_iterator<_Cp, false>; 49*0b57cec5SDimitry Andricpublic: 50*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY operator bool() const _NOEXCEPT 51*0b57cec5SDimitry Andric {return static_cast<bool>(*__seg_ & __mask_);} 52*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY bool operator ~() const _NOEXCEPT 53*0b57cec5SDimitry Andric {return !static_cast<bool>(*this);} 54*0b57cec5SDimitry Andric 55*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 56*0b57cec5SDimitry Andric __bit_reference& operator=(bool __x) _NOEXCEPT 57*0b57cec5SDimitry Andric { 58*0b57cec5SDimitry Andric if (__x) 59*0b57cec5SDimitry Andric *__seg_ |= __mask_; 60*0b57cec5SDimitry Andric else 61*0b57cec5SDimitry Andric *__seg_ &= ~__mask_; 62*0b57cec5SDimitry Andric return *this; 63*0b57cec5SDimitry Andric } 64*0b57cec5SDimitry Andric 65*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 66*0b57cec5SDimitry Andric __bit_reference& operator=(const __bit_reference& __x) _NOEXCEPT 67*0b57cec5SDimitry Andric {return operator=(static_cast<bool>(__x));} 68*0b57cec5SDimitry Andric 69*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY void flip() _NOEXCEPT {*__seg_ ^= __mask_;} 70*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, false> operator&() const _NOEXCEPT 71*0b57cec5SDimitry Andric {return __bit_iterator<_Cp, false>(__seg_, static_cast<unsigned>(__libcpp_ctz(__mask_)));} 72*0b57cec5SDimitry Andricprivate: 73*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 74*0b57cec5SDimitry Andric __bit_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT 75*0b57cec5SDimitry Andric : __seg_(__s), __mask_(__m) {} 76*0b57cec5SDimitry Andric}; 77*0b57cec5SDimitry Andric 78*0b57cec5SDimitry Andrictemplate <class _Cp> 79*0b57cec5SDimitry Andricclass __bit_reference<_Cp, false> 80*0b57cec5SDimitry Andric{ 81*0b57cec5SDimitry Andric}; 82*0b57cec5SDimitry Andric 83*0b57cec5SDimitry Andrictemplate <class _Cp> 84*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 85*0b57cec5SDimitry Andricvoid 86*0b57cec5SDimitry Andricswap(__bit_reference<_Cp> __x, __bit_reference<_Cp> __y) _NOEXCEPT 87*0b57cec5SDimitry Andric{ 88*0b57cec5SDimitry Andric bool __t = __x; 89*0b57cec5SDimitry Andric __x = __y; 90*0b57cec5SDimitry Andric __y = __t; 91*0b57cec5SDimitry Andric} 92*0b57cec5SDimitry Andric 93*0b57cec5SDimitry Andrictemplate <class _Cp, class _Dp> 94*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 95*0b57cec5SDimitry Andricvoid 96*0b57cec5SDimitry Andricswap(__bit_reference<_Cp> __x, __bit_reference<_Dp> __y) _NOEXCEPT 97*0b57cec5SDimitry Andric{ 98*0b57cec5SDimitry Andric bool __t = __x; 99*0b57cec5SDimitry Andric __x = __y; 100*0b57cec5SDimitry Andric __y = __t; 101*0b57cec5SDimitry Andric} 102*0b57cec5SDimitry Andric 103*0b57cec5SDimitry Andrictemplate <class _Cp> 104*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 105*0b57cec5SDimitry Andricvoid 106*0b57cec5SDimitry Andricswap(__bit_reference<_Cp> __x, bool& __y) _NOEXCEPT 107*0b57cec5SDimitry Andric{ 108*0b57cec5SDimitry Andric bool __t = __x; 109*0b57cec5SDimitry Andric __x = __y; 110*0b57cec5SDimitry Andric __y = __t; 111*0b57cec5SDimitry Andric} 112*0b57cec5SDimitry Andric 113*0b57cec5SDimitry Andrictemplate <class _Cp> 114*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 115*0b57cec5SDimitry Andricvoid 116*0b57cec5SDimitry Andricswap(bool& __x, __bit_reference<_Cp> __y) _NOEXCEPT 117*0b57cec5SDimitry Andric{ 118*0b57cec5SDimitry Andric bool __t = __x; 119*0b57cec5SDimitry Andric __x = __y; 120*0b57cec5SDimitry Andric __y = __t; 121*0b57cec5SDimitry Andric} 122*0b57cec5SDimitry Andric 123*0b57cec5SDimitry Andrictemplate <class _Cp> 124*0b57cec5SDimitry Andricclass __bit_const_reference 125*0b57cec5SDimitry Andric{ 126*0b57cec5SDimitry Andric typedef typename _Cp::__storage_type __storage_type; 127*0b57cec5SDimitry Andric typedef typename _Cp::__const_storage_pointer __storage_pointer; 128*0b57cec5SDimitry Andric 129*0b57cec5SDimitry Andric __storage_pointer __seg_; 130*0b57cec5SDimitry Andric __storage_type __mask_; 131*0b57cec5SDimitry Andric 132*0b57cec5SDimitry Andric friend typename _Cp::__self; 133*0b57cec5SDimitry Andric friend class __bit_iterator<_Cp, true>; 134*0b57cec5SDimitry Andricpublic: 135*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 136*0b57cec5SDimitry Andric __bit_const_reference(const __bit_reference<_Cp>& __x) _NOEXCEPT 137*0b57cec5SDimitry Andric : __seg_(__x.__seg_), __mask_(__x.__mask_) {} 138*0b57cec5SDimitry Andric 139*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR operator bool() const _NOEXCEPT 140*0b57cec5SDimitry Andric {return static_cast<bool>(*__seg_ & __mask_);} 141*0b57cec5SDimitry Andric 142*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, true> operator&() const _NOEXCEPT 143*0b57cec5SDimitry Andric {return __bit_iterator<_Cp, true>(__seg_, static_cast<unsigned>(__libcpp_ctz(__mask_)));} 144*0b57cec5SDimitry Andricprivate: 145*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 146*0b57cec5SDimitry Andric _LIBCPP_CONSTEXPR 147*0b57cec5SDimitry Andric __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT 148*0b57cec5SDimitry Andric : __seg_(__s), __mask_(__m) {} 149*0b57cec5SDimitry Andric 150*0b57cec5SDimitry Andric __bit_const_reference& operator=(const __bit_const_reference& __x); 151*0b57cec5SDimitry Andric}; 152*0b57cec5SDimitry Andric 153*0b57cec5SDimitry Andric// find 154*0b57cec5SDimitry Andric 155*0b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 156*0b57cec5SDimitry Andric__bit_iterator<_Cp, _IsConst> 157*0b57cec5SDimitry Andric__find_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 158*0b57cec5SDimitry Andric{ 159*0b57cec5SDimitry Andric typedef __bit_iterator<_Cp, _IsConst> _It; 160*0b57cec5SDimitry Andric typedef typename _It::__storage_type __storage_type; 161*0b57cec5SDimitry Andric static const int __bits_per_word = _It::__bits_per_word; 162*0b57cec5SDimitry Andric // do first partial word 163*0b57cec5SDimitry Andric if (__first.__ctz_ != 0) 164*0b57cec5SDimitry Andric { 165*0b57cec5SDimitry Andric __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 166*0b57cec5SDimitry Andric __storage_type __dn = _VSTD::min(__clz_f, __n); 167*0b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 168*0b57cec5SDimitry Andric __storage_type __b = *__first.__seg_ & __m; 169*0b57cec5SDimitry Andric if (__b) 170*0b57cec5SDimitry Andric return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b))); 171*0b57cec5SDimitry Andric if (__n == __dn) 172*0b57cec5SDimitry Andric return __first + __n; 173*0b57cec5SDimitry Andric __n -= __dn; 174*0b57cec5SDimitry Andric ++__first.__seg_; 175*0b57cec5SDimitry Andric } 176*0b57cec5SDimitry Andric // do middle whole words 177*0b57cec5SDimitry Andric for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 178*0b57cec5SDimitry Andric if (*__first.__seg_) 179*0b57cec5SDimitry Andric return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(*__first.__seg_))); 180*0b57cec5SDimitry Andric // do last partial word 181*0b57cec5SDimitry Andric if (__n > 0) 182*0b57cec5SDimitry Andric { 183*0b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 184*0b57cec5SDimitry Andric __storage_type __b = *__first.__seg_ & __m; 185*0b57cec5SDimitry Andric if (__b) 186*0b57cec5SDimitry Andric return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b))); 187*0b57cec5SDimitry Andric } 188*0b57cec5SDimitry Andric return _It(__first.__seg_, static_cast<unsigned>(__n)); 189*0b57cec5SDimitry Andric} 190*0b57cec5SDimitry Andric 191*0b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 192*0b57cec5SDimitry Andric__bit_iterator<_Cp, _IsConst> 193*0b57cec5SDimitry Andric__find_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 194*0b57cec5SDimitry Andric{ 195*0b57cec5SDimitry Andric typedef __bit_iterator<_Cp, _IsConst> _It; 196*0b57cec5SDimitry Andric typedef typename _It::__storage_type __storage_type; 197*0b57cec5SDimitry Andric const int __bits_per_word = _It::__bits_per_word; 198*0b57cec5SDimitry Andric // do first partial word 199*0b57cec5SDimitry Andric if (__first.__ctz_ != 0) 200*0b57cec5SDimitry Andric { 201*0b57cec5SDimitry Andric __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 202*0b57cec5SDimitry Andric __storage_type __dn = _VSTD::min(__clz_f, __n); 203*0b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 204*0b57cec5SDimitry Andric __storage_type __b = ~*__first.__seg_ & __m; 205*0b57cec5SDimitry Andric if (__b) 206*0b57cec5SDimitry Andric return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b))); 207*0b57cec5SDimitry Andric if (__n == __dn) 208*0b57cec5SDimitry Andric return __first + __n; 209*0b57cec5SDimitry Andric __n -= __dn; 210*0b57cec5SDimitry Andric ++__first.__seg_; 211*0b57cec5SDimitry Andric } 212*0b57cec5SDimitry Andric // do middle whole words 213*0b57cec5SDimitry Andric for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 214*0b57cec5SDimitry Andric { 215*0b57cec5SDimitry Andric __storage_type __b = ~*__first.__seg_; 216*0b57cec5SDimitry Andric if (__b) 217*0b57cec5SDimitry Andric return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b))); 218*0b57cec5SDimitry Andric } 219*0b57cec5SDimitry Andric // do last partial word 220*0b57cec5SDimitry Andric if (__n > 0) 221*0b57cec5SDimitry Andric { 222*0b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 223*0b57cec5SDimitry Andric __storage_type __b = ~*__first.__seg_ & __m; 224*0b57cec5SDimitry Andric if (__b) 225*0b57cec5SDimitry Andric return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b))); 226*0b57cec5SDimitry Andric } 227*0b57cec5SDimitry Andric return _It(__first.__seg_, static_cast<unsigned>(__n)); 228*0b57cec5SDimitry Andric} 229*0b57cec5SDimitry Andric 230*0b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst, class _Tp> 231*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 232*0b57cec5SDimitry Andric__bit_iterator<_Cp, _IsConst> 233*0b57cec5SDimitry Andricfind(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_) 234*0b57cec5SDimitry Andric{ 235*0b57cec5SDimitry Andric if (static_cast<bool>(__value_)) 236*0b57cec5SDimitry Andric return __find_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first)); 237*0b57cec5SDimitry Andric return __find_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first)); 238*0b57cec5SDimitry Andric} 239*0b57cec5SDimitry Andric 240*0b57cec5SDimitry Andric// count 241*0b57cec5SDimitry Andric 242*0b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 243*0b57cec5SDimitry Andrictypename __bit_iterator<_Cp, _IsConst>::difference_type 244*0b57cec5SDimitry Andric__count_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 245*0b57cec5SDimitry Andric{ 246*0b57cec5SDimitry Andric typedef __bit_iterator<_Cp, _IsConst> _It; 247*0b57cec5SDimitry Andric typedef typename _It::__storage_type __storage_type; 248*0b57cec5SDimitry Andric typedef typename _It::difference_type difference_type; 249*0b57cec5SDimitry Andric const int __bits_per_word = _It::__bits_per_word; 250*0b57cec5SDimitry Andric difference_type __r = 0; 251*0b57cec5SDimitry Andric // do first partial word 252*0b57cec5SDimitry Andric if (__first.__ctz_ != 0) 253*0b57cec5SDimitry Andric { 254*0b57cec5SDimitry Andric __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 255*0b57cec5SDimitry Andric __storage_type __dn = _VSTD::min(__clz_f, __n); 256*0b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 257*0b57cec5SDimitry Andric __r = _VSTD::__libcpp_popcount(*__first.__seg_ & __m); 258*0b57cec5SDimitry Andric __n -= __dn; 259*0b57cec5SDimitry Andric ++__first.__seg_; 260*0b57cec5SDimitry Andric } 261*0b57cec5SDimitry Andric // do middle whole words 262*0b57cec5SDimitry Andric for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 263*0b57cec5SDimitry Andric __r += _VSTD::__libcpp_popcount(*__first.__seg_); 264*0b57cec5SDimitry Andric // do last partial word 265*0b57cec5SDimitry Andric if (__n > 0) 266*0b57cec5SDimitry Andric { 267*0b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 268*0b57cec5SDimitry Andric __r += _VSTD::__libcpp_popcount(*__first.__seg_ & __m); 269*0b57cec5SDimitry Andric } 270*0b57cec5SDimitry Andric return __r; 271*0b57cec5SDimitry Andric} 272*0b57cec5SDimitry Andric 273*0b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 274*0b57cec5SDimitry Andrictypename __bit_iterator<_Cp, _IsConst>::difference_type 275*0b57cec5SDimitry Andric__count_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) 276*0b57cec5SDimitry Andric{ 277*0b57cec5SDimitry Andric typedef __bit_iterator<_Cp, _IsConst> _It; 278*0b57cec5SDimitry Andric typedef typename _It::__storage_type __storage_type; 279*0b57cec5SDimitry Andric typedef typename _It::difference_type difference_type; 280*0b57cec5SDimitry Andric const int __bits_per_word = _It::__bits_per_word; 281*0b57cec5SDimitry Andric difference_type __r = 0; 282*0b57cec5SDimitry Andric // do first partial word 283*0b57cec5SDimitry Andric if (__first.__ctz_ != 0) 284*0b57cec5SDimitry Andric { 285*0b57cec5SDimitry Andric __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 286*0b57cec5SDimitry Andric __storage_type __dn = _VSTD::min(__clz_f, __n); 287*0b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 288*0b57cec5SDimitry Andric __r = _VSTD::__libcpp_popcount(~*__first.__seg_ & __m); 289*0b57cec5SDimitry Andric __n -= __dn; 290*0b57cec5SDimitry Andric ++__first.__seg_; 291*0b57cec5SDimitry Andric } 292*0b57cec5SDimitry Andric // do middle whole words 293*0b57cec5SDimitry Andric for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) 294*0b57cec5SDimitry Andric __r += _VSTD::__libcpp_popcount(~*__first.__seg_); 295*0b57cec5SDimitry Andric // do last partial word 296*0b57cec5SDimitry Andric if (__n > 0) 297*0b57cec5SDimitry Andric { 298*0b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 299*0b57cec5SDimitry Andric __r += _VSTD::__libcpp_popcount(~*__first.__seg_ & __m); 300*0b57cec5SDimitry Andric } 301*0b57cec5SDimitry Andric return __r; 302*0b57cec5SDimitry Andric} 303*0b57cec5SDimitry Andric 304*0b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst, class _Tp> 305*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 306*0b57cec5SDimitry Andrictypename __bit_iterator<_Cp, _IsConst>::difference_type 307*0b57cec5SDimitry Andriccount(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_) 308*0b57cec5SDimitry Andric{ 309*0b57cec5SDimitry Andric if (static_cast<bool>(__value_)) 310*0b57cec5SDimitry Andric return __count_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first)); 311*0b57cec5SDimitry Andric return __count_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first)); 312*0b57cec5SDimitry Andric} 313*0b57cec5SDimitry Andric 314*0b57cec5SDimitry Andric// fill_n 315*0b57cec5SDimitry Andric 316*0b57cec5SDimitry Andrictemplate <class _Cp> 317*0b57cec5SDimitry Andricvoid 318*0b57cec5SDimitry Andric__fill_n_false(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) 319*0b57cec5SDimitry Andric{ 320*0b57cec5SDimitry Andric typedef __bit_iterator<_Cp, false> _It; 321*0b57cec5SDimitry Andric typedef typename _It::__storage_type __storage_type; 322*0b57cec5SDimitry Andric const int __bits_per_word = _It::__bits_per_word; 323*0b57cec5SDimitry Andric // do first partial word 324*0b57cec5SDimitry Andric if (__first.__ctz_ != 0) 325*0b57cec5SDimitry Andric { 326*0b57cec5SDimitry Andric __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 327*0b57cec5SDimitry Andric __storage_type __dn = _VSTD::min(__clz_f, __n); 328*0b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 329*0b57cec5SDimitry Andric *__first.__seg_ &= ~__m; 330*0b57cec5SDimitry Andric __n -= __dn; 331*0b57cec5SDimitry Andric ++__first.__seg_; 332*0b57cec5SDimitry Andric } 333*0b57cec5SDimitry Andric // do middle whole words 334*0b57cec5SDimitry Andric __storage_type __nw = __n / __bits_per_word; 335*0b57cec5SDimitry Andric _VSTD::memset(_VSTD::__to_raw_pointer(__first.__seg_), 0, __nw * sizeof(__storage_type)); 336*0b57cec5SDimitry Andric __n -= __nw * __bits_per_word; 337*0b57cec5SDimitry Andric // do last partial word 338*0b57cec5SDimitry Andric if (__n > 0) 339*0b57cec5SDimitry Andric { 340*0b57cec5SDimitry Andric __first.__seg_ += __nw; 341*0b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 342*0b57cec5SDimitry Andric *__first.__seg_ &= ~__m; 343*0b57cec5SDimitry Andric } 344*0b57cec5SDimitry Andric} 345*0b57cec5SDimitry Andric 346*0b57cec5SDimitry Andrictemplate <class _Cp> 347*0b57cec5SDimitry Andricvoid 348*0b57cec5SDimitry Andric__fill_n_true(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) 349*0b57cec5SDimitry Andric{ 350*0b57cec5SDimitry Andric typedef __bit_iterator<_Cp, false> _It; 351*0b57cec5SDimitry Andric typedef typename _It::__storage_type __storage_type; 352*0b57cec5SDimitry Andric const int __bits_per_word = _It::__bits_per_word; 353*0b57cec5SDimitry Andric // do first partial word 354*0b57cec5SDimitry Andric if (__first.__ctz_ != 0) 355*0b57cec5SDimitry Andric { 356*0b57cec5SDimitry Andric __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); 357*0b57cec5SDimitry Andric __storage_type __dn = _VSTD::min(__clz_f, __n); 358*0b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 359*0b57cec5SDimitry Andric *__first.__seg_ |= __m; 360*0b57cec5SDimitry Andric __n -= __dn; 361*0b57cec5SDimitry Andric ++__first.__seg_; 362*0b57cec5SDimitry Andric } 363*0b57cec5SDimitry Andric // do middle whole words 364*0b57cec5SDimitry Andric __storage_type __nw = __n / __bits_per_word; 365*0b57cec5SDimitry Andric _VSTD::memset(_VSTD::__to_raw_pointer(__first.__seg_), -1, __nw * sizeof(__storage_type)); 366*0b57cec5SDimitry Andric __n -= __nw * __bits_per_word; 367*0b57cec5SDimitry Andric // do last partial word 368*0b57cec5SDimitry Andric if (__n > 0) 369*0b57cec5SDimitry Andric { 370*0b57cec5SDimitry Andric __first.__seg_ += __nw; 371*0b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 372*0b57cec5SDimitry Andric *__first.__seg_ |= __m; 373*0b57cec5SDimitry Andric } 374*0b57cec5SDimitry Andric} 375*0b57cec5SDimitry Andric 376*0b57cec5SDimitry Andrictemplate <class _Cp> 377*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 378*0b57cec5SDimitry Andricvoid 379*0b57cec5SDimitry Andricfill_n(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n, bool __value_) 380*0b57cec5SDimitry Andric{ 381*0b57cec5SDimitry Andric if (__n > 0) 382*0b57cec5SDimitry Andric { 383*0b57cec5SDimitry Andric if (__value_) 384*0b57cec5SDimitry Andric __fill_n_true(__first, __n); 385*0b57cec5SDimitry Andric else 386*0b57cec5SDimitry Andric __fill_n_false(__first, __n); 387*0b57cec5SDimitry Andric } 388*0b57cec5SDimitry Andric} 389*0b57cec5SDimitry Andric 390*0b57cec5SDimitry Andric// fill 391*0b57cec5SDimitry Andric 392*0b57cec5SDimitry Andrictemplate <class _Cp> 393*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 394*0b57cec5SDimitry Andricvoid 395*0b57cec5SDimitry Andricfill(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __last, bool __value_) 396*0b57cec5SDimitry Andric{ 397*0b57cec5SDimitry Andric _VSTD::fill_n(__first, static_cast<typename _Cp::size_type>(__last - __first), __value_); 398*0b57cec5SDimitry Andric} 399*0b57cec5SDimitry Andric 400*0b57cec5SDimitry Andric// copy 401*0b57cec5SDimitry Andric 402*0b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 403*0b57cec5SDimitry Andric__bit_iterator<_Cp, false> 404*0b57cec5SDimitry Andric__copy_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 405*0b57cec5SDimitry Andric __bit_iterator<_Cp, false> __result) 406*0b57cec5SDimitry Andric{ 407*0b57cec5SDimitry Andric typedef __bit_iterator<_Cp, _IsConst> _In; 408*0b57cec5SDimitry Andric typedef typename _In::difference_type difference_type; 409*0b57cec5SDimitry Andric typedef typename _In::__storage_type __storage_type; 410*0b57cec5SDimitry Andric const int __bits_per_word = _In::__bits_per_word; 411*0b57cec5SDimitry Andric difference_type __n = __last - __first; 412*0b57cec5SDimitry Andric if (__n > 0) 413*0b57cec5SDimitry Andric { 414*0b57cec5SDimitry Andric // do first word 415*0b57cec5SDimitry Andric if (__first.__ctz_ != 0) 416*0b57cec5SDimitry Andric { 417*0b57cec5SDimitry Andric unsigned __clz = __bits_per_word - __first.__ctz_; 418*0b57cec5SDimitry Andric difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 419*0b57cec5SDimitry Andric __n -= __dn; 420*0b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 421*0b57cec5SDimitry Andric __storage_type __b = *__first.__seg_ & __m; 422*0b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 423*0b57cec5SDimitry Andric *__result.__seg_ |= __b; 424*0b57cec5SDimitry Andric __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 425*0b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 426*0b57cec5SDimitry Andric ++__first.__seg_; 427*0b57cec5SDimitry Andric // __first.__ctz_ = 0; 428*0b57cec5SDimitry Andric } 429*0b57cec5SDimitry Andric // __first.__ctz_ == 0; 430*0b57cec5SDimitry Andric // do middle words 431*0b57cec5SDimitry Andric __storage_type __nw = __n / __bits_per_word; 432*0b57cec5SDimitry Andric _VSTD::memmove(_VSTD::__to_raw_pointer(__result.__seg_), 433*0b57cec5SDimitry Andric _VSTD::__to_raw_pointer(__first.__seg_), 434*0b57cec5SDimitry Andric __nw * sizeof(__storage_type)); 435*0b57cec5SDimitry Andric __n -= __nw * __bits_per_word; 436*0b57cec5SDimitry Andric __result.__seg_ += __nw; 437*0b57cec5SDimitry Andric // do last word 438*0b57cec5SDimitry Andric if (__n > 0) 439*0b57cec5SDimitry Andric { 440*0b57cec5SDimitry Andric __first.__seg_ += __nw; 441*0b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 442*0b57cec5SDimitry Andric __storage_type __b = *__first.__seg_ & __m; 443*0b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 444*0b57cec5SDimitry Andric *__result.__seg_ |= __b; 445*0b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(__n); 446*0b57cec5SDimitry Andric } 447*0b57cec5SDimitry Andric } 448*0b57cec5SDimitry Andric return __result; 449*0b57cec5SDimitry Andric} 450*0b57cec5SDimitry Andric 451*0b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 452*0b57cec5SDimitry Andric__bit_iterator<_Cp, false> 453*0b57cec5SDimitry Andric__copy_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 454*0b57cec5SDimitry Andric __bit_iterator<_Cp, false> __result) 455*0b57cec5SDimitry Andric{ 456*0b57cec5SDimitry Andric typedef __bit_iterator<_Cp, _IsConst> _In; 457*0b57cec5SDimitry Andric typedef typename _In::difference_type difference_type; 458*0b57cec5SDimitry Andric typedef typename _In::__storage_type __storage_type; 459*0b57cec5SDimitry Andric static const int __bits_per_word = _In::__bits_per_word; 460*0b57cec5SDimitry Andric difference_type __n = __last - __first; 461*0b57cec5SDimitry Andric if (__n > 0) 462*0b57cec5SDimitry Andric { 463*0b57cec5SDimitry Andric // do first word 464*0b57cec5SDimitry Andric if (__first.__ctz_ != 0) 465*0b57cec5SDimitry Andric { 466*0b57cec5SDimitry Andric unsigned __clz_f = __bits_per_word - __first.__ctz_; 467*0b57cec5SDimitry Andric difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 468*0b57cec5SDimitry Andric __n -= __dn; 469*0b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 470*0b57cec5SDimitry Andric __storage_type __b = *__first.__seg_ & __m; 471*0b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __result.__ctz_; 472*0b57cec5SDimitry Andric __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 473*0b57cec5SDimitry Andric __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 474*0b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 475*0b57cec5SDimitry Andric if (__result.__ctz_ > __first.__ctz_) 476*0b57cec5SDimitry Andric *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_); 477*0b57cec5SDimitry Andric else 478*0b57cec5SDimitry Andric *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_); 479*0b57cec5SDimitry Andric __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 480*0b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 481*0b57cec5SDimitry Andric __dn -= __ddn; 482*0b57cec5SDimitry Andric if (__dn > 0) 483*0b57cec5SDimitry Andric { 484*0b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __dn); 485*0b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 486*0b57cec5SDimitry Andric *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn); 487*0b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(__dn); 488*0b57cec5SDimitry Andric } 489*0b57cec5SDimitry Andric ++__first.__seg_; 490*0b57cec5SDimitry Andric // __first.__ctz_ = 0; 491*0b57cec5SDimitry Andric } 492*0b57cec5SDimitry Andric // __first.__ctz_ == 0; 493*0b57cec5SDimitry Andric // do middle words 494*0b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __result.__ctz_; 495*0b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) << __result.__ctz_; 496*0b57cec5SDimitry Andric for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 497*0b57cec5SDimitry Andric { 498*0b57cec5SDimitry Andric __storage_type __b = *__first.__seg_; 499*0b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 500*0b57cec5SDimitry Andric *__result.__seg_ |= __b << __result.__ctz_; 501*0b57cec5SDimitry Andric ++__result.__seg_; 502*0b57cec5SDimitry Andric *__result.__seg_ &= __m; 503*0b57cec5SDimitry Andric *__result.__seg_ |= __b >> __clz_r; 504*0b57cec5SDimitry Andric } 505*0b57cec5SDimitry Andric // do last word 506*0b57cec5SDimitry Andric if (__n > 0) 507*0b57cec5SDimitry Andric { 508*0b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __n); 509*0b57cec5SDimitry Andric __storage_type __b = *__first.__seg_ & __m; 510*0b57cec5SDimitry Andric __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); 511*0b57cec5SDimitry Andric __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 512*0b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 513*0b57cec5SDimitry Andric *__result.__seg_ |= __b << __result.__ctz_; 514*0b57cec5SDimitry Andric __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 515*0b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 516*0b57cec5SDimitry Andric __n -= __dn; 517*0b57cec5SDimitry Andric if (__n > 0) 518*0b57cec5SDimitry Andric { 519*0b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __n); 520*0b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 521*0b57cec5SDimitry Andric *__result.__seg_ |= __b >> __dn; 522*0b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(__n); 523*0b57cec5SDimitry Andric } 524*0b57cec5SDimitry Andric } 525*0b57cec5SDimitry Andric } 526*0b57cec5SDimitry Andric return __result; 527*0b57cec5SDimitry Andric} 528*0b57cec5SDimitry Andric 529*0b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 530*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 531*0b57cec5SDimitry Andric__bit_iterator<_Cp, false> 532*0b57cec5SDimitry Andriccopy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 533*0b57cec5SDimitry Andric{ 534*0b57cec5SDimitry Andric if (__first.__ctz_ == __result.__ctz_) 535*0b57cec5SDimitry Andric return __copy_aligned(__first, __last, __result); 536*0b57cec5SDimitry Andric return __copy_unaligned(__first, __last, __result); 537*0b57cec5SDimitry Andric} 538*0b57cec5SDimitry Andric 539*0b57cec5SDimitry Andric// copy_backward 540*0b57cec5SDimitry Andric 541*0b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 542*0b57cec5SDimitry Andric__bit_iterator<_Cp, false> 543*0b57cec5SDimitry Andric__copy_backward_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 544*0b57cec5SDimitry Andric __bit_iterator<_Cp, false> __result) 545*0b57cec5SDimitry Andric{ 546*0b57cec5SDimitry Andric typedef __bit_iterator<_Cp, _IsConst> _In; 547*0b57cec5SDimitry Andric typedef typename _In::difference_type difference_type; 548*0b57cec5SDimitry Andric typedef typename _In::__storage_type __storage_type; 549*0b57cec5SDimitry Andric const int __bits_per_word = _In::__bits_per_word; 550*0b57cec5SDimitry Andric difference_type __n = __last - __first; 551*0b57cec5SDimitry Andric if (__n > 0) 552*0b57cec5SDimitry Andric { 553*0b57cec5SDimitry Andric // do first word 554*0b57cec5SDimitry Andric if (__last.__ctz_ != 0) 555*0b57cec5SDimitry Andric { 556*0b57cec5SDimitry Andric difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); 557*0b57cec5SDimitry Andric __n -= __dn; 558*0b57cec5SDimitry Andric unsigned __clz = __bits_per_word - __last.__ctz_; 559*0b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz); 560*0b57cec5SDimitry Andric __storage_type __b = *__last.__seg_ & __m; 561*0b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 562*0b57cec5SDimitry Andric *__result.__seg_ |= __b; 563*0b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 564*0b57cec5SDimitry Andric __result.__ctz_) % __bits_per_word); 565*0b57cec5SDimitry Andric // __last.__ctz_ = 0 566*0b57cec5SDimitry Andric } 567*0b57cec5SDimitry Andric // __last.__ctz_ == 0 || __n == 0 568*0b57cec5SDimitry Andric // __result.__ctz_ == 0 || __n == 0 569*0b57cec5SDimitry Andric // do middle words 570*0b57cec5SDimitry Andric __storage_type __nw = __n / __bits_per_word; 571*0b57cec5SDimitry Andric __result.__seg_ -= __nw; 572*0b57cec5SDimitry Andric __last.__seg_ -= __nw; 573*0b57cec5SDimitry Andric _VSTD::memmove(_VSTD::__to_raw_pointer(__result.__seg_), 574*0b57cec5SDimitry Andric _VSTD::__to_raw_pointer(__last.__seg_), 575*0b57cec5SDimitry Andric __nw * sizeof(__storage_type)); 576*0b57cec5SDimitry Andric __n -= __nw * __bits_per_word; 577*0b57cec5SDimitry Andric // do last word 578*0b57cec5SDimitry Andric if (__n > 0) 579*0b57cec5SDimitry Andric { 580*0b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n); 581*0b57cec5SDimitry Andric __storage_type __b = *--__last.__seg_ & __m; 582*0b57cec5SDimitry Andric *--__result.__seg_ &= ~__m; 583*0b57cec5SDimitry Andric *__result.__seg_ |= __b; 584*0b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 585*0b57cec5SDimitry Andric } 586*0b57cec5SDimitry Andric } 587*0b57cec5SDimitry Andric return __result; 588*0b57cec5SDimitry Andric} 589*0b57cec5SDimitry Andric 590*0b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 591*0b57cec5SDimitry Andric__bit_iterator<_Cp, false> 592*0b57cec5SDimitry Andric__copy_backward_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, 593*0b57cec5SDimitry Andric __bit_iterator<_Cp, false> __result) 594*0b57cec5SDimitry Andric{ 595*0b57cec5SDimitry Andric typedef __bit_iterator<_Cp, _IsConst> _In; 596*0b57cec5SDimitry Andric typedef typename _In::difference_type difference_type; 597*0b57cec5SDimitry Andric typedef typename _In::__storage_type __storage_type; 598*0b57cec5SDimitry Andric const int __bits_per_word = _In::__bits_per_word; 599*0b57cec5SDimitry Andric difference_type __n = __last - __first; 600*0b57cec5SDimitry Andric if (__n > 0) 601*0b57cec5SDimitry Andric { 602*0b57cec5SDimitry Andric // do first word 603*0b57cec5SDimitry Andric if (__last.__ctz_ != 0) 604*0b57cec5SDimitry Andric { 605*0b57cec5SDimitry Andric difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); 606*0b57cec5SDimitry Andric __n -= __dn; 607*0b57cec5SDimitry Andric unsigned __clz_l = __bits_per_word - __last.__ctz_; 608*0b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l); 609*0b57cec5SDimitry Andric __storage_type __b = *__last.__seg_ & __m; 610*0b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __result.__ctz_; 611*0b57cec5SDimitry Andric __storage_type __ddn = _VSTD::min(__dn, static_cast<difference_type>(__result.__ctz_)); 612*0b57cec5SDimitry Andric if (__ddn > 0) 613*0b57cec5SDimitry Andric { 614*0b57cec5SDimitry Andric __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r); 615*0b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 616*0b57cec5SDimitry Andric if (__result.__ctz_ > __last.__ctz_) 617*0b57cec5SDimitry Andric *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 618*0b57cec5SDimitry Andric else 619*0b57cec5SDimitry Andric *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_); 620*0b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) + 621*0b57cec5SDimitry Andric __result.__ctz_) % __bits_per_word); 622*0b57cec5SDimitry Andric __dn -= __ddn; 623*0b57cec5SDimitry Andric } 624*0b57cec5SDimitry Andric if (__dn > 0) 625*0b57cec5SDimitry Andric { 626*0b57cec5SDimitry Andric // __result.__ctz_ == 0 627*0b57cec5SDimitry Andric --__result.__seg_; 628*0b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1)); 629*0b57cec5SDimitry Andric __m = ~__storage_type(0) << __result.__ctz_; 630*0b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 631*0b57cec5SDimitry Andric __last.__ctz_ -= __dn + __ddn; 632*0b57cec5SDimitry Andric *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); 633*0b57cec5SDimitry Andric } 634*0b57cec5SDimitry Andric // __last.__ctz_ = 0 635*0b57cec5SDimitry Andric } 636*0b57cec5SDimitry Andric // __last.__ctz_ == 0 || __n == 0 637*0b57cec5SDimitry Andric // __result.__ctz_ != 0 || __n == 0 638*0b57cec5SDimitry Andric // do middle words 639*0b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __result.__ctz_; 640*0b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> __clz_r; 641*0b57cec5SDimitry Andric for (; __n >= __bits_per_word; __n -= __bits_per_word) 642*0b57cec5SDimitry Andric { 643*0b57cec5SDimitry Andric __storage_type __b = *--__last.__seg_; 644*0b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 645*0b57cec5SDimitry Andric *__result.__seg_ |= __b >> __clz_r; 646*0b57cec5SDimitry Andric *--__result.__seg_ &= __m; 647*0b57cec5SDimitry Andric *__result.__seg_ |= __b << __result.__ctz_; 648*0b57cec5SDimitry Andric } 649*0b57cec5SDimitry Andric // do last word 650*0b57cec5SDimitry Andric if (__n > 0) 651*0b57cec5SDimitry Andric { 652*0b57cec5SDimitry Andric __m = ~__storage_type(0) << (__bits_per_word - __n); 653*0b57cec5SDimitry Andric __storage_type __b = *--__last.__seg_ & __m; 654*0b57cec5SDimitry Andric __clz_r = __bits_per_word - __result.__ctz_; 655*0b57cec5SDimitry Andric __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__result.__ctz_)); 656*0b57cec5SDimitry Andric __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r); 657*0b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 658*0b57cec5SDimitry Andric *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_); 659*0b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + 660*0b57cec5SDimitry Andric __result.__ctz_) % __bits_per_word); 661*0b57cec5SDimitry Andric __n -= __dn; 662*0b57cec5SDimitry Andric if (__n > 0) 663*0b57cec5SDimitry Andric { 664*0b57cec5SDimitry Andric // __result.__ctz_ == 0 665*0b57cec5SDimitry Andric --__result.__seg_; 666*0b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); 667*0b57cec5SDimitry Andric __m = ~__storage_type(0) << __result.__ctz_; 668*0b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 669*0b57cec5SDimitry Andric *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn)); 670*0b57cec5SDimitry Andric } 671*0b57cec5SDimitry Andric } 672*0b57cec5SDimitry Andric } 673*0b57cec5SDimitry Andric return __result; 674*0b57cec5SDimitry Andric} 675*0b57cec5SDimitry Andric 676*0b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 677*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 678*0b57cec5SDimitry Andric__bit_iterator<_Cp, false> 679*0b57cec5SDimitry Andriccopy_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 680*0b57cec5SDimitry Andric{ 681*0b57cec5SDimitry Andric if (__last.__ctz_ == __result.__ctz_) 682*0b57cec5SDimitry Andric return __copy_backward_aligned(__first, __last, __result); 683*0b57cec5SDimitry Andric return __copy_backward_unaligned(__first, __last, __result); 684*0b57cec5SDimitry Andric} 685*0b57cec5SDimitry Andric 686*0b57cec5SDimitry Andric// move 687*0b57cec5SDimitry Andric 688*0b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 689*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 690*0b57cec5SDimitry Andric__bit_iterator<_Cp, false> 691*0b57cec5SDimitry Andricmove(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 692*0b57cec5SDimitry Andric{ 693*0b57cec5SDimitry Andric return _VSTD::copy(__first, __last, __result); 694*0b57cec5SDimitry Andric} 695*0b57cec5SDimitry Andric 696*0b57cec5SDimitry Andric// move_backward 697*0b57cec5SDimitry Andric 698*0b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst> 699*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 700*0b57cec5SDimitry Andric__bit_iterator<_Cp, false> 701*0b57cec5SDimitry Andricmove_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) 702*0b57cec5SDimitry Andric{ 703*0b57cec5SDimitry Andric return _VSTD::copy_backward(__first, __last, __result); 704*0b57cec5SDimitry Andric} 705*0b57cec5SDimitry Andric 706*0b57cec5SDimitry Andric// swap_ranges 707*0b57cec5SDimitry Andric 708*0b57cec5SDimitry Andrictemplate <class __C1, class __C2> 709*0b57cec5SDimitry Andric__bit_iterator<__C2, false> 710*0b57cec5SDimitry Andric__swap_ranges_aligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, 711*0b57cec5SDimitry Andric __bit_iterator<__C2, false> __result) 712*0b57cec5SDimitry Andric{ 713*0b57cec5SDimitry Andric typedef __bit_iterator<__C1, false> _I1; 714*0b57cec5SDimitry Andric typedef typename _I1::difference_type difference_type; 715*0b57cec5SDimitry Andric typedef typename _I1::__storage_type __storage_type; 716*0b57cec5SDimitry Andric const int __bits_per_word = _I1::__bits_per_word; 717*0b57cec5SDimitry Andric difference_type __n = __last - __first; 718*0b57cec5SDimitry Andric if (__n > 0) 719*0b57cec5SDimitry Andric { 720*0b57cec5SDimitry Andric // do first word 721*0b57cec5SDimitry Andric if (__first.__ctz_ != 0) 722*0b57cec5SDimitry Andric { 723*0b57cec5SDimitry Andric unsigned __clz = __bits_per_word - __first.__ctz_; 724*0b57cec5SDimitry Andric difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 725*0b57cec5SDimitry Andric __n -= __dn; 726*0b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 727*0b57cec5SDimitry Andric __storage_type __b1 = *__first.__seg_ & __m; 728*0b57cec5SDimitry Andric *__first.__seg_ &= ~__m; 729*0b57cec5SDimitry Andric __storage_type __b2 = *__result.__seg_ & __m; 730*0b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 731*0b57cec5SDimitry Andric *__result.__seg_ |= __b1; 732*0b57cec5SDimitry Andric *__first.__seg_ |= __b2; 733*0b57cec5SDimitry Andric __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 734*0b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 735*0b57cec5SDimitry Andric ++__first.__seg_; 736*0b57cec5SDimitry Andric // __first.__ctz_ = 0; 737*0b57cec5SDimitry Andric } 738*0b57cec5SDimitry Andric // __first.__ctz_ == 0; 739*0b57cec5SDimitry Andric // do middle words 740*0b57cec5SDimitry Andric for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_) 741*0b57cec5SDimitry Andric swap(*__first.__seg_, *__result.__seg_); 742*0b57cec5SDimitry Andric // do last word 743*0b57cec5SDimitry Andric if (__n > 0) 744*0b57cec5SDimitry Andric { 745*0b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 746*0b57cec5SDimitry Andric __storage_type __b1 = *__first.__seg_ & __m; 747*0b57cec5SDimitry Andric *__first.__seg_ &= ~__m; 748*0b57cec5SDimitry Andric __storage_type __b2 = *__result.__seg_ & __m; 749*0b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 750*0b57cec5SDimitry Andric *__result.__seg_ |= __b1; 751*0b57cec5SDimitry Andric *__first.__seg_ |= __b2; 752*0b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(__n); 753*0b57cec5SDimitry Andric } 754*0b57cec5SDimitry Andric } 755*0b57cec5SDimitry Andric return __result; 756*0b57cec5SDimitry Andric} 757*0b57cec5SDimitry Andric 758*0b57cec5SDimitry Andrictemplate <class __C1, class __C2> 759*0b57cec5SDimitry Andric__bit_iterator<__C2, false> 760*0b57cec5SDimitry Andric__swap_ranges_unaligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, 761*0b57cec5SDimitry Andric __bit_iterator<__C2, false> __result) 762*0b57cec5SDimitry Andric{ 763*0b57cec5SDimitry Andric typedef __bit_iterator<__C1, false> _I1; 764*0b57cec5SDimitry Andric typedef typename _I1::difference_type difference_type; 765*0b57cec5SDimitry Andric typedef typename _I1::__storage_type __storage_type; 766*0b57cec5SDimitry Andric const int __bits_per_word = _I1::__bits_per_word; 767*0b57cec5SDimitry Andric difference_type __n = __last - __first; 768*0b57cec5SDimitry Andric if (__n > 0) 769*0b57cec5SDimitry Andric { 770*0b57cec5SDimitry Andric // do first word 771*0b57cec5SDimitry Andric if (__first.__ctz_ != 0) 772*0b57cec5SDimitry Andric { 773*0b57cec5SDimitry Andric unsigned __clz_f = __bits_per_word - __first.__ctz_; 774*0b57cec5SDimitry Andric difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 775*0b57cec5SDimitry Andric __n -= __dn; 776*0b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 777*0b57cec5SDimitry Andric __storage_type __b1 = *__first.__seg_ & __m; 778*0b57cec5SDimitry Andric *__first.__seg_ &= ~__m; 779*0b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __result.__ctz_; 780*0b57cec5SDimitry Andric __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 781*0b57cec5SDimitry Andric __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 782*0b57cec5SDimitry Andric __storage_type __b2 = *__result.__seg_ & __m; 783*0b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 784*0b57cec5SDimitry Andric if (__result.__ctz_ > __first.__ctz_) 785*0b57cec5SDimitry Andric { 786*0b57cec5SDimitry Andric unsigned __s = __result.__ctz_ - __first.__ctz_; 787*0b57cec5SDimitry Andric *__result.__seg_ |= __b1 << __s; 788*0b57cec5SDimitry Andric *__first.__seg_ |= __b2 >> __s; 789*0b57cec5SDimitry Andric } 790*0b57cec5SDimitry Andric else 791*0b57cec5SDimitry Andric { 792*0b57cec5SDimitry Andric unsigned __s = __first.__ctz_ - __result.__ctz_; 793*0b57cec5SDimitry Andric *__result.__seg_ |= __b1 >> __s; 794*0b57cec5SDimitry Andric *__first.__seg_ |= __b2 << __s; 795*0b57cec5SDimitry Andric } 796*0b57cec5SDimitry Andric __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; 797*0b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); 798*0b57cec5SDimitry Andric __dn -= __ddn; 799*0b57cec5SDimitry Andric if (__dn > 0) 800*0b57cec5SDimitry Andric { 801*0b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __dn); 802*0b57cec5SDimitry Andric __b2 = *__result.__seg_ & __m; 803*0b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 804*0b57cec5SDimitry Andric unsigned __s = __first.__ctz_ + __ddn; 805*0b57cec5SDimitry Andric *__result.__seg_ |= __b1 >> __s; 806*0b57cec5SDimitry Andric *__first.__seg_ |= __b2 << __s; 807*0b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(__dn); 808*0b57cec5SDimitry Andric } 809*0b57cec5SDimitry Andric ++__first.__seg_; 810*0b57cec5SDimitry Andric // __first.__ctz_ = 0; 811*0b57cec5SDimitry Andric } 812*0b57cec5SDimitry Andric // __first.__ctz_ == 0; 813*0b57cec5SDimitry Andric // do middle words 814*0b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) << __result.__ctz_; 815*0b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __result.__ctz_; 816*0b57cec5SDimitry Andric for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) 817*0b57cec5SDimitry Andric { 818*0b57cec5SDimitry Andric __storage_type __b1 = *__first.__seg_; 819*0b57cec5SDimitry Andric __storage_type __b2 = *__result.__seg_ & __m; 820*0b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 821*0b57cec5SDimitry Andric *__result.__seg_ |= __b1 << __result.__ctz_; 822*0b57cec5SDimitry Andric *__first.__seg_ = __b2 >> __result.__ctz_; 823*0b57cec5SDimitry Andric ++__result.__seg_; 824*0b57cec5SDimitry Andric __b2 = *__result.__seg_ & ~__m; 825*0b57cec5SDimitry Andric *__result.__seg_ &= __m; 826*0b57cec5SDimitry Andric *__result.__seg_ |= __b1 >> __clz_r; 827*0b57cec5SDimitry Andric *__first.__seg_ |= __b2 << __clz_r; 828*0b57cec5SDimitry Andric } 829*0b57cec5SDimitry Andric // do last word 830*0b57cec5SDimitry Andric if (__n > 0) 831*0b57cec5SDimitry Andric { 832*0b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __n); 833*0b57cec5SDimitry Andric __storage_type __b1 = *__first.__seg_ & __m; 834*0b57cec5SDimitry Andric *__first.__seg_ &= ~__m; 835*0b57cec5SDimitry Andric __storage_type __dn = _VSTD::min<__storage_type>(__n, __clz_r); 836*0b57cec5SDimitry Andric __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 837*0b57cec5SDimitry Andric __storage_type __b2 = *__result.__seg_ & __m; 838*0b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 839*0b57cec5SDimitry Andric *__result.__seg_ |= __b1 << __result.__ctz_; 840*0b57cec5SDimitry Andric *__first.__seg_ |= __b2 >> __result.__ctz_; 841*0b57cec5SDimitry Andric __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; 842*0b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); 843*0b57cec5SDimitry Andric __n -= __dn; 844*0b57cec5SDimitry Andric if (__n > 0) 845*0b57cec5SDimitry Andric { 846*0b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __n); 847*0b57cec5SDimitry Andric __b2 = *__result.__seg_ & __m; 848*0b57cec5SDimitry Andric *__result.__seg_ &= ~__m; 849*0b57cec5SDimitry Andric *__result.__seg_ |= __b1 >> __dn; 850*0b57cec5SDimitry Andric *__first.__seg_ |= __b2 << __dn; 851*0b57cec5SDimitry Andric __result.__ctz_ = static_cast<unsigned>(__n); 852*0b57cec5SDimitry Andric } 853*0b57cec5SDimitry Andric } 854*0b57cec5SDimitry Andric } 855*0b57cec5SDimitry Andric return __result; 856*0b57cec5SDimitry Andric} 857*0b57cec5SDimitry Andric 858*0b57cec5SDimitry Andrictemplate <class __C1, class __C2> 859*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 860*0b57cec5SDimitry Andric__bit_iterator<__C2, false> 861*0b57cec5SDimitry Andricswap_ranges(__bit_iterator<__C1, false> __first1, __bit_iterator<__C1, false> __last1, 862*0b57cec5SDimitry Andric __bit_iterator<__C2, false> __first2) 863*0b57cec5SDimitry Andric{ 864*0b57cec5SDimitry Andric if (__first1.__ctz_ == __first2.__ctz_) 865*0b57cec5SDimitry Andric return __swap_ranges_aligned(__first1, __last1, __first2); 866*0b57cec5SDimitry Andric return __swap_ranges_unaligned(__first1, __last1, __first2); 867*0b57cec5SDimitry Andric} 868*0b57cec5SDimitry Andric 869*0b57cec5SDimitry Andric// rotate 870*0b57cec5SDimitry Andric 871*0b57cec5SDimitry Andrictemplate <class _Cp> 872*0b57cec5SDimitry Andricstruct __bit_array 873*0b57cec5SDimitry Andric{ 874*0b57cec5SDimitry Andric typedef typename _Cp::difference_type difference_type; 875*0b57cec5SDimitry Andric typedef typename _Cp::__storage_type __storage_type; 876*0b57cec5SDimitry Andric typedef typename _Cp::__storage_pointer __storage_pointer; 877*0b57cec5SDimitry Andric typedef typename _Cp::iterator iterator; 878*0b57cec5SDimitry Andric static const unsigned __bits_per_word = _Cp::__bits_per_word; 879*0b57cec5SDimitry Andric static const unsigned _Np = 4; 880*0b57cec5SDimitry Andric 881*0b57cec5SDimitry Andric difference_type __size_; 882*0b57cec5SDimitry Andric __storage_type __word_[_Np]; 883*0b57cec5SDimitry Andric 884*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY static difference_type capacity() 885*0b57cec5SDimitry Andric {return static_cast<difference_type>(_Np * __bits_per_word);} 886*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY explicit __bit_array(difference_type __s) : __size_(__s) {} 887*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY iterator begin() 888*0b57cec5SDimitry Andric { 889*0b57cec5SDimitry Andric return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]), 0); 890*0b57cec5SDimitry Andric } 891*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY iterator end() 892*0b57cec5SDimitry Andric { 893*0b57cec5SDimitry Andric return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]) + __size_ / __bits_per_word, 894*0b57cec5SDimitry Andric static_cast<unsigned>(__size_ % __bits_per_word)); 895*0b57cec5SDimitry Andric } 896*0b57cec5SDimitry Andric}; 897*0b57cec5SDimitry Andric 898*0b57cec5SDimitry Andrictemplate <class _Cp> 899*0b57cec5SDimitry Andric__bit_iterator<_Cp, false> 900*0b57cec5SDimitry Andricrotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last) 901*0b57cec5SDimitry Andric{ 902*0b57cec5SDimitry Andric typedef __bit_iterator<_Cp, false> _I1; 903*0b57cec5SDimitry Andric typedef typename _I1::difference_type difference_type; 904*0b57cec5SDimitry Andric difference_type __d1 = __middle - __first; 905*0b57cec5SDimitry Andric difference_type __d2 = __last - __middle; 906*0b57cec5SDimitry Andric _I1 __r = __first + __d2; 907*0b57cec5SDimitry Andric while (__d1 != 0 && __d2 != 0) 908*0b57cec5SDimitry Andric { 909*0b57cec5SDimitry Andric if (__d1 <= __d2) 910*0b57cec5SDimitry Andric { 911*0b57cec5SDimitry Andric if (__d1 <= __bit_array<_Cp>::capacity()) 912*0b57cec5SDimitry Andric { 913*0b57cec5SDimitry Andric __bit_array<_Cp> __b(__d1); 914*0b57cec5SDimitry Andric _VSTD::copy(__first, __middle, __b.begin()); 915*0b57cec5SDimitry Andric _VSTD::copy(__b.begin(), __b.end(), _VSTD::copy(__middle, __last, __first)); 916*0b57cec5SDimitry Andric break; 917*0b57cec5SDimitry Andric } 918*0b57cec5SDimitry Andric else 919*0b57cec5SDimitry Andric { 920*0b57cec5SDimitry Andric __bit_iterator<_Cp, false> __mp = _VSTD::swap_ranges(__first, __middle, __middle); 921*0b57cec5SDimitry Andric __first = __middle; 922*0b57cec5SDimitry Andric __middle = __mp; 923*0b57cec5SDimitry Andric __d2 -= __d1; 924*0b57cec5SDimitry Andric } 925*0b57cec5SDimitry Andric } 926*0b57cec5SDimitry Andric else 927*0b57cec5SDimitry Andric { 928*0b57cec5SDimitry Andric if (__d2 <= __bit_array<_Cp>::capacity()) 929*0b57cec5SDimitry Andric { 930*0b57cec5SDimitry Andric __bit_array<_Cp> __b(__d2); 931*0b57cec5SDimitry Andric _VSTD::copy(__middle, __last, __b.begin()); 932*0b57cec5SDimitry Andric _VSTD::copy_backward(__b.begin(), __b.end(), _VSTD::copy_backward(__first, __middle, __last)); 933*0b57cec5SDimitry Andric break; 934*0b57cec5SDimitry Andric } 935*0b57cec5SDimitry Andric else 936*0b57cec5SDimitry Andric { 937*0b57cec5SDimitry Andric __bit_iterator<_Cp, false> __mp = __first + __d2; 938*0b57cec5SDimitry Andric _VSTD::swap_ranges(__first, __mp, __middle); 939*0b57cec5SDimitry Andric __first = __mp; 940*0b57cec5SDimitry Andric __d1 -= __d2; 941*0b57cec5SDimitry Andric } 942*0b57cec5SDimitry Andric } 943*0b57cec5SDimitry Andric } 944*0b57cec5SDimitry Andric return __r; 945*0b57cec5SDimitry Andric} 946*0b57cec5SDimitry Andric 947*0b57cec5SDimitry Andric// equal 948*0b57cec5SDimitry Andric 949*0b57cec5SDimitry Andrictemplate <class _Cp, bool _IC1, bool _IC2> 950*0b57cec5SDimitry Andricbool 951*0b57cec5SDimitry Andric__equal_unaligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, 952*0b57cec5SDimitry Andric __bit_iterator<_Cp, _IC2> __first2) 953*0b57cec5SDimitry Andric{ 954*0b57cec5SDimitry Andric typedef __bit_iterator<_Cp, _IC1> _It; 955*0b57cec5SDimitry Andric typedef typename _It::difference_type difference_type; 956*0b57cec5SDimitry Andric typedef typename _It::__storage_type __storage_type; 957*0b57cec5SDimitry Andric static const int __bits_per_word = _It::__bits_per_word; 958*0b57cec5SDimitry Andric difference_type __n = __last1 - __first1; 959*0b57cec5SDimitry Andric if (__n > 0) 960*0b57cec5SDimitry Andric { 961*0b57cec5SDimitry Andric // do first word 962*0b57cec5SDimitry Andric if (__first1.__ctz_ != 0) 963*0b57cec5SDimitry Andric { 964*0b57cec5SDimitry Andric unsigned __clz_f = __bits_per_word - __first1.__ctz_; 965*0b57cec5SDimitry Andric difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); 966*0b57cec5SDimitry Andric __n -= __dn; 967*0b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); 968*0b57cec5SDimitry Andric __storage_type __b = *__first1.__seg_ & __m; 969*0b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __first2.__ctz_; 970*0b57cec5SDimitry Andric __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); 971*0b57cec5SDimitry Andric __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); 972*0b57cec5SDimitry Andric if (__first2.__ctz_ > __first1.__ctz_) 973*0b57cec5SDimitry Andric { 974*0b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_))) 975*0b57cec5SDimitry Andric return false; 976*0b57cec5SDimitry Andric } 977*0b57cec5SDimitry Andric else 978*0b57cec5SDimitry Andric { 979*0b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_))) 980*0b57cec5SDimitry Andric return false; 981*0b57cec5SDimitry Andric } 982*0b57cec5SDimitry Andric __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word; 983*0b57cec5SDimitry Andric __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word); 984*0b57cec5SDimitry Andric __dn -= __ddn; 985*0b57cec5SDimitry Andric if (__dn > 0) 986*0b57cec5SDimitry Andric { 987*0b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __dn); 988*0b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn))) 989*0b57cec5SDimitry Andric return false; 990*0b57cec5SDimitry Andric __first2.__ctz_ = static_cast<unsigned>(__dn); 991*0b57cec5SDimitry Andric } 992*0b57cec5SDimitry Andric ++__first1.__seg_; 993*0b57cec5SDimitry Andric // __first1.__ctz_ = 0; 994*0b57cec5SDimitry Andric } 995*0b57cec5SDimitry Andric // __first1.__ctz_ == 0; 996*0b57cec5SDimitry Andric // do middle words 997*0b57cec5SDimitry Andric unsigned __clz_r = __bits_per_word - __first2.__ctz_; 998*0b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) << __first2.__ctz_; 999*0b57cec5SDimitry Andric for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_) 1000*0b57cec5SDimitry Andric { 1001*0b57cec5SDimitry Andric __storage_type __b = *__first1.__seg_; 1002*0b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 1003*0b57cec5SDimitry Andric return false; 1004*0b57cec5SDimitry Andric ++__first2.__seg_; 1005*0b57cec5SDimitry Andric if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r)) 1006*0b57cec5SDimitry Andric return false; 1007*0b57cec5SDimitry Andric } 1008*0b57cec5SDimitry Andric // do last word 1009*0b57cec5SDimitry Andric if (__n > 0) 1010*0b57cec5SDimitry Andric { 1011*0b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __n); 1012*0b57cec5SDimitry Andric __storage_type __b = *__first1.__seg_ & __m; 1013*0b57cec5SDimitry Andric __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); 1014*0b57cec5SDimitry Andric __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); 1015*0b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) 1016*0b57cec5SDimitry Andric return false; 1017*0b57cec5SDimitry Andric __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word; 1018*0b57cec5SDimitry Andric __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word); 1019*0b57cec5SDimitry Andric __n -= __dn; 1020*0b57cec5SDimitry Andric if (__n > 0) 1021*0b57cec5SDimitry Andric { 1022*0b57cec5SDimitry Andric __m = ~__storage_type(0) >> (__bits_per_word - __n); 1023*0b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (__b >> __dn)) 1024*0b57cec5SDimitry Andric return false; 1025*0b57cec5SDimitry Andric } 1026*0b57cec5SDimitry Andric } 1027*0b57cec5SDimitry Andric } 1028*0b57cec5SDimitry Andric return true; 1029*0b57cec5SDimitry Andric} 1030*0b57cec5SDimitry Andric 1031*0b57cec5SDimitry Andrictemplate <class _Cp, bool _IC1, bool _IC2> 1032*0b57cec5SDimitry Andricbool 1033*0b57cec5SDimitry Andric__equal_aligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, 1034*0b57cec5SDimitry Andric __bit_iterator<_Cp, _IC2> __first2) 1035*0b57cec5SDimitry Andric{ 1036*0b57cec5SDimitry Andric typedef __bit_iterator<_Cp, _IC1> _It; 1037*0b57cec5SDimitry Andric typedef typename _It::difference_type difference_type; 1038*0b57cec5SDimitry Andric typedef typename _It::__storage_type __storage_type; 1039*0b57cec5SDimitry Andric static const int __bits_per_word = _It::__bits_per_word; 1040*0b57cec5SDimitry Andric difference_type __n = __last1 - __first1; 1041*0b57cec5SDimitry Andric if (__n > 0) 1042*0b57cec5SDimitry Andric { 1043*0b57cec5SDimitry Andric // do first word 1044*0b57cec5SDimitry Andric if (__first1.__ctz_ != 0) 1045*0b57cec5SDimitry Andric { 1046*0b57cec5SDimitry Andric unsigned __clz = __bits_per_word - __first1.__ctz_; 1047*0b57cec5SDimitry Andric difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); 1048*0b57cec5SDimitry Andric __n -= __dn; 1049*0b57cec5SDimitry Andric __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); 1050*0b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 1051*0b57cec5SDimitry Andric return false; 1052*0b57cec5SDimitry Andric ++__first2.__seg_; 1053*0b57cec5SDimitry Andric ++__first1.__seg_; 1054*0b57cec5SDimitry Andric // __first1.__ctz_ = 0; 1055*0b57cec5SDimitry Andric // __first2.__ctz_ = 0; 1056*0b57cec5SDimitry Andric } 1057*0b57cec5SDimitry Andric // __first1.__ctz_ == 0; 1058*0b57cec5SDimitry Andric // __first2.__ctz_ == 0; 1059*0b57cec5SDimitry Andric // do middle words 1060*0b57cec5SDimitry Andric for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_) 1061*0b57cec5SDimitry Andric if (*__first2.__seg_ != *__first1.__seg_) 1062*0b57cec5SDimitry Andric return false; 1063*0b57cec5SDimitry Andric // do last word 1064*0b57cec5SDimitry Andric if (__n > 0) 1065*0b57cec5SDimitry Andric { 1066*0b57cec5SDimitry Andric __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 1067*0b57cec5SDimitry Andric if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 1068*0b57cec5SDimitry Andric return false; 1069*0b57cec5SDimitry Andric } 1070*0b57cec5SDimitry Andric } 1071*0b57cec5SDimitry Andric return true; 1072*0b57cec5SDimitry Andric} 1073*0b57cec5SDimitry Andric 1074*0b57cec5SDimitry Andrictemplate <class _Cp, bool _IC1, bool _IC2> 1075*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 1076*0b57cec5SDimitry Andricbool 1077*0b57cec5SDimitry Andricequal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) 1078*0b57cec5SDimitry Andric{ 1079*0b57cec5SDimitry Andric if (__first1.__ctz_ == __first2.__ctz_) 1080*0b57cec5SDimitry Andric return __equal_aligned(__first1, __last1, __first2); 1081*0b57cec5SDimitry Andric return __equal_unaligned(__first1, __last1, __first2); 1082*0b57cec5SDimitry Andric} 1083*0b57cec5SDimitry Andric 1084*0b57cec5SDimitry Andrictemplate <class _Cp, bool _IsConst, 1085*0b57cec5SDimitry Andric typename _Cp::__storage_type> 1086*0b57cec5SDimitry Andricclass __bit_iterator 1087*0b57cec5SDimitry Andric{ 1088*0b57cec5SDimitry Andricpublic: 1089*0b57cec5SDimitry Andric typedef typename _Cp::difference_type difference_type; 1090*0b57cec5SDimitry Andric typedef bool value_type; 1091*0b57cec5SDimitry Andric typedef __bit_iterator pointer; 1092*0b57cec5SDimitry Andric typedef typename conditional<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >::type reference; 1093*0b57cec5SDimitry Andric typedef random_access_iterator_tag iterator_category; 1094*0b57cec5SDimitry Andric 1095*0b57cec5SDimitry Andricprivate: 1096*0b57cec5SDimitry Andric typedef typename _Cp::__storage_type __storage_type; 1097*0b57cec5SDimitry Andric typedef typename conditional<_IsConst, typename _Cp::__const_storage_pointer, 1098*0b57cec5SDimitry Andric typename _Cp::__storage_pointer>::type __storage_pointer; 1099*0b57cec5SDimitry Andric static const unsigned __bits_per_word = _Cp::__bits_per_word; 1100*0b57cec5SDimitry Andric 1101*0b57cec5SDimitry Andric __storage_pointer __seg_; 1102*0b57cec5SDimitry Andric unsigned __ctz_; 1103*0b57cec5SDimitry Andric 1104*0b57cec5SDimitry Andricpublic: 1105*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY __bit_iterator() _NOEXCEPT 1106*0b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 1107*0b57cec5SDimitry Andric : __seg_(nullptr), __ctz_(0) 1108*0b57cec5SDimitry Andric#endif 1109*0b57cec5SDimitry Andric {} 1110*0b57cec5SDimitry Andric 1111*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 1112*0b57cec5SDimitry Andric __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT 1113*0b57cec5SDimitry Andric : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {} 1114*0b57cec5SDimitry Andric 1115*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT 1116*0b57cec5SDimitry Andric {return reference(__seg_, __storage_type(1) << __ctz_);} 1117*0b57cec5SDimitry Andric 1118*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator++() 1119*0b57cec5SDimitry Andric { 1120*0b57cec5SDimitry Andric if (__ctz_ != __bits_per_word-1) 1121*0b57cec5SDimitry Andric ++__ctz_; 1122*0b57cec5SDimitry Andric else 1123*0b57cec5SDimitry Andric { 1124*0b57cec5SDimitry Andric __ctz_ = 0; 1125*0b57cec5SDimitry Andric ++__seg_; 1126*0b57cec5SDimitry Andric } 1127*0b57cec5SDimitry Andric return *this; 1128*0b57cec5SDimitry Andric } 1129*0b57cec5SDimitry Andric 1130*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY __bit_iterator operator++(int) 1131*0b57cec5SDimitry Andric { 1132*0b57cec5SDimitry Andric __bit_iterator __tmp = *this; 1133*0b57cec5SDimitry Andric ++(*this); 1134*0b57cec5SDimitry Andric return __tmp; 1135*0b57cec5SDimitry Andric } 1136*0b57cec5SDimitry Andric 1137*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator--() 1138*0b57cec5SDimitry Andric { 1139*0b57cec5SDimitry Andric if (__ctz_ != 0) 1140*0b57cec5SDimitry Andric --__ctz_; 1141*0b57cec5SDimitry Andric else 1142*0b57cec5SDimitry Andric { 1143*0b57cec5SDimitry Andric __ctz_ = __bits_per_word - 1; 1144*0b57cec5SDimitry Andric --__seg_; 1145*0b57cec5SDimitry Andric } 1146*0b57cec5SDimitry Andric return *this; 1147*0b57cec5SDimitry Andric } 1148*0b57cec5SDimitry Andric 1149*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY __bit_iterator operator--(int) 1150*0b57cec5SDimitry Andric { 1151*0b57cec5SDimitry Andric __bit_iterator __tmp = *this; 1152*0b57cec5SDimitry Andric --(*this); 1153*0b57cec5SDimitry Andric return __tmp; 1154*0b57cec5SDimitry Andric } 1155*0b57cec5SDimitry Andric 1156*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator+=(difference_type __n) 1157*0b57cec5SDimitry Andric { 1158*0b57cec5SDimitry Andric if (__n >= 0) 1159*0b57cec5SDimitry Andric __seg_ += (__n + __ctz_) / __bits_per_word; 1160*0b57cec5SDimitry Andric else 1161*0b57cec5SDimitry Andric __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1) 1162*0b57cec5SDimitry Andric / static_cast<difference_type>(__bits_per_word); 1163*0b57cec5SDimitry Andric __n &= (__bits_per_word - 1); 1164*0b57cec5SDimitry Andric __ctz_ = static_cast<unsigned>((__n + __ctz_) % __bits_per_word); 1165*0b57cec5SDimitry Andric return *this; 1166*0b57cec5SDimitry Andric } 1167*0b57cec5SDimitry Andric 1168*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator-=(difference_type __n) 1169*0b57cec5SDimitry Andric { 1170*0b57cec5SDimitry Andric return *this += -__n; 1171*0b57cec5SDimitry Andric } 1172*0b57cec5SDimitry Andric 1173*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY __bit_iterator operator+(difference_type __n) const 1174*0b57cec5SDimitry Andric { 1175*0b57cec5SDimitry Andric __bit_iterator __t(*this); 1176*0b57cec5SDimitry Andric __t += __n; 1177*0b57cec5SDimitry Andric return __t; 1178*0b57cec5SDimitry Andric } 1179*0b57cec5SDimitry Andric 1180*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY __bit_iterator operator-(difference_type __n) const 1181*0b57cec5SDimitry Andric { 1182*0b57cec5SDimitry Andric __bit_iterator __t(*this); 1183*0b57cec5SDimitry Andric __t -= __n; 1184*0b57cec5SDimitry Andric return __t; 1185*0b57cec5SDimitry Andric } 1186*0b57cec5SDimitry Andric 1187*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 1188*0b57cec5SDimitry Andric friend __bit_iterator operator+(difference_type __n, const __bit_iterator& __it) {return __it + __n;} 1189*0b57cec5SDimitry Andric 1190*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 1191*0b57cec5SDimitry Andric friend difference_type operator-(const __bit_iterator& __x, const __bit_iterator& __y) 1192*0b57cec5SDimitry Andric {return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;} 1193*0b57cec5SDimitry Andric 1194*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const {return *(*this + __n);} 1195*0b57cec5SDimitry Andric 1196*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY friend bool operator==(const __bit_iterator& __x, const __bit_iterator& __y) 1197*0b57cec5SDimitry Andric {return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;} 1198*0b57cec5SDimitry Andric 1199*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY friend bool operator!=(const __bit_iterator& __x, const __bit_iterator& __y) 1200*0b57cec5SDimitry Andric {return !(__x == __y);} 1201*0b57cec5SDimitry Andric 1202*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY friend bool operator<(const __bit_iterator& __x, const __bit_iterator& __y) 1203*0b57cec5SDimitry Andric {return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);} 1204*0b57cec5SDimitry Andric 1205*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY friend bool operator>(const __bit_iterator& __x, const __bit_iterator& __y) 1206*0b57cec5SDimitry Andric {return __y < __x;} 1207*0b57cec5SDimitry Andric 1208*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y) 1209*0b57cec5SDimitry Andric {return !(__y < __x);} 1210*0b57cec5SDimitry Andric 1211*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y) 1212*0b57cec5SDimitry Andric {return !(__x < __y);} 1213*0b57cec5SDimitry Andric 1214*0b57cec5SDimitry Andricprivate: 1215*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 1216*0b57cec5SDimitry Andric __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT 1217*0b57cec5SDimitry Andric : __seg_(__s), __ctz_(__ctz) {} 1218*0b57cec5SDimitry Andric 1219*0b57cec5SDimitry Andric friend typename _Cp::__self; 1220*0b57cec5SDimitry Andric 1221*0b57cec5SDimitry Andric friend class __bit_reference<_Cp>; 1222*0b57cec5SDimitry Andric friend class __bit_const_reference<_Cp>; 1223*0b57cec5SDimitry Andric friend class __bit_iterator<_Cp, true>; 1224*0b57cec5SDimitry Andric template <class _Dp> friend struct __bit_array; 1225*0b57cec5SDimitry Andric template <class _Dp> friend void __fill_n_false(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); 1226*0b57cec5SDimitry Andric template <class _Dp> friend void __fill_n_true(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); 1227*0b57cec5SDimitry Andric template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_aligned(__bit_iterator<_Dp, _IC> __first, 1228*0b57cec5SDimitry Andric __bit_iterator<_Dp, _IC> __last, 1229*0b57cec5SDimitry Andric __bit_iterator<_Dp, false> __result); 1230*0b57cec5SDimitry Andric template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_unaligned(__bit_iterator<_Dp, _IC> __first, 1231*0b57cec5SDimitry Andric __bit_iterator<_Dp, _IC> __last, 1232*0b57cec5SDimitry Andric __bit_iterator<_Dp, false> __result); 1233*0b57cec5SDimitry Andric template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy(__bit_iterator<_Dp, _IC> __first, 1234*0b57cec5SDimitry Andric __bit_iterator<_Dp, _IC> __last, 1235*0b57cec5SDimitry Andric __bit_iterator<_Dp, false> __result); 1236*0b57cec5SDimitry Andric template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_aligned(__bit_iterator<_Dp, _IC> __first, 1237*0b57cec5SDimitry Andric __bit_iterator<_Dp, _IC> __last, 1238*0b57cec5SDimitry Andric __bit_iterator<_Dp, false> __result); 1239*0b57cec5SDimitry Andric template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_unaligned(__bit_iterator<_Dp, _IC> __first, 1240*0b57cec5SDimitry Andric __bit_iterator<_Dp, _IC> __last, 1241*0b57cec5SDimitry Andric __bit_iterator<_Dp, false> __result); 1242*0b57cec5SDimitry Andric template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy_backward(__bit_iterator<_Dp, _IC> __first, 1243*0b57cec5SDimitry Andric __bit_iterator<_Dp, _IC> __last, 1244*0b57cec5SDimitry Andric __bit_iterator<_Dp, false> __result); 1245*0b57cec5SDimitry Andric template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_aligned(__bit_iterator<__C1, false>, 1246*0b57cec5SDimitry Andric __bit_iterator<__C1, false>, 1247*0b57cec5SDimitry Andric __bit_iterator<__C2, false>); 1248*0b57cec5SDimitry Andric template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_unaligned(__bit_iterator<__C1, false>, 1249*0b57cec5SDimitry Andric __bit_iterator<__C1, false>, 1250*0b57cec5SDimitry Andric __bit_iterator<__C2, false>); 1251*0b57cec5SDimitry Andric template <class __C1, class __C2>friend __bit_iterator<__C2, false> swap_ranges(__bit_iterator<__C1, false>, 1252*0b57cec5SDimitry Andric __bit_iterator<__C1, false>, 1253*0b57cec5SDimitry Andric __bit_iterator<__C2, false>); 1254*0b57cec5SDimitry Andric template <class _Dp> friend __bit_iterator<_Dp, false> rotate(__bit_iterator<_Dp, false>, 1255*0b57cec5SDimitry Andric __bit_iterator<_Dp, false>, 1256*0b57cec5SDimitry Andric __bit_iterator<_Dp, false>); 1257*0b57cec5SDimitry Andric template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_aligned(__bit_iterator<_Dp, _IC1>, 1258*0b57cec5SDimitry Andric __bit_iterator<_Dp, _IC1>, 1259*0b57cec5SDimitry Andric __bit_iterator<_Dp, _IC2>); 1260*0b57cec5SDimitry Andric template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_unaligned(__bit_iterator<_Dp, _IC1>, 1261*0b57cec5SDimitry Andric __bit_iterator<_Dp, _IC1>, 1262*0b57cec5SDimitry Andric __bit_iterator<_Dp, _IC2>); 1263*0b57cec5SDimitry Andric template <class _Dp, bool _IC1, bool _IC2> friend bool equal(__bit_iterator<_Dp, _IC1>, 1264*0b57cec5SDimitry Andric __bit_iterator<_Dp, _IC1>, 1265*0b57cec5SDimitry Andric __bit_iterator<_Dp, _IC2>); 1266*0b57cec5SDimitry Andric template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_true(__bit_iterator<_Dp, _IC>, 1267*0b57cec5SDimitry Andric typename _Dp::size_type); 1268*0b57cec5SDimitry Andric template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_false(__bit_iterator<_Dp, _IC>, 1269*0b57cec5SDimitry Andric typename _Dp::size_type); 1270*0b57cec5SDimitry Andric template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type 1271*0b57cec5SDimitry Andric __count_bool_true(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 1272*0b57cec5SDimitry Andric template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type 1273*0b57cec5SDimitry Andric __count_bool_false(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 1274*0b57cec5SDimitry Andric}; 1275*0b57cec5SDimitry Andric 1276*0b57cec5SDimitry Andric_LIBCPP_END_NAMESPACE_STD 1277*0b57cec5SDimitry Andric 1278*0b57cec5SDimitry Andric_LIBCPP_POP_MACROS 1279*0b57cec5SDimitry Andric 1280*0b57cec5SDimitry Andric#endif // _LIBCPP___BIT_REFERENCE 1281