966 lines · plain
1// -*- C++ -*-2//===----------------------------------------------------------------------===//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___CXX03___BIT_REFERENCE11#define _LIBCPP___CXX03___BIT_REFERENCE12 13#include <__cxx03/__algorithm/copy_n.h>14#include <__cxx03/__algorithm/fill_n.h>15#include <__cxx03/__algorithm/min.h>16#include <__cxx03/__bit/countr.h>17#include <__cxx03/__bit/invert_if.h>18#include <__cxx03/__bit/popcount.h>19#include <__cxx03/__config>20#include <__cxx03/__fwd/bit_reference.h>21#include <__cxx03/__iterator/iterator_traits.h>22#include <__cxx03/__memory/construct_at.h>23#include <__cxx03/__memory/pointer_traits.h>24#include <__cxx03/__type_traits/conditional.h>25#include <__cxx03/__utility/swap.h>26#include <__cxx03/cstring>27 28#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)29# pragma GCC system_header30#endif31 32_LIBCPP_PUSH_MACROS33#include <__cxx03/__undef_macros>34 35_LIBCPP_BEGIN_NAMESPACE_STD36 37template <class _Cp>38class __bit_const_reference;39 40template <class _Tp>41struct __has_storage_type {42 static const bool value = false;43};44 45template <class _Cp, bool = __has_storage_type<_Cp>::value>46class __bit_reference {47 using __storage_type = typename _Cp::__storage_type;48 using __storage_pointer = typename _Cp::__storage_pointer;49 50 __storage_pointer __seg_;51 __storage_type __mask_;52 53 friend typename _Cp::__self;54 55 friend class __bit_const_reference<_Cp>;56 friend class __bit_iterator<_Cp, false>;57 58public:59 using __container = typename _Cp::__self;60 61 _LIBCPP_HIDE_FROM_ABI __bit_reference(const __bit_reference&) = default;62 63 _LIBCPP_HIDE_FROM_ABI operator bool() const _NOEXCEPT { return static_cast<bool>(*__seg_ & __mask_); }64 _LIBCPP_HIDE_FROM_ABI bool operator~() const _NOEXCEPT { return !static_cast<bool>(*this); }65 66 _LIBCPP_HIDE_FROM_ABI __bit_reference& operator=(bool __x) _NOEXCEPT {67 if (__x)68 *__seg_ |= __mask_;69 else70 *__seg_ &= ~__mask_;71 return *this;72 }73 74 _LIBCPP_HIDE_FROM_ABI __bit_reference& operator=(const __bit_reference& __x) _NOEXCEPT {75 return operator=(static_cast<bool>(__x));76 }77 78 _LIBCPP_HIDE_FROM_ABI void flip() _NOEXCEPT { *__seg_ ^= __mask_; }79 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> operator&() const _NOEXCEPT {80 return __bit_iterator<_Cp, false>(__seg_, static_cast<unsigned>(std::__libcpp_ctz(__mask_)));81 }82 83private:84 _LIBCPP_HIDE_FROM_ABI explicit __bit_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT85 : __seg_(__s),86 __mask_(__m) {}87};88 89template <class _Cp>90class __bit_reference<_Cp, false> {};91 92template <class _Cp>93inline _LIBCPP_HIDE_FROM_ABI void swap(__bit_reference<_Cp> __x, __bit_reference<_Cp> __y) _NOEXCEPT {94 bool __t = __x;95 __x = __y;96 __y = __t;97}98 99template <class _Cp, class _Dp>100inline _LIBCPP_HIDE_FROM_ABI void swap(__bit_reference<_Cp> __x, __bit_reference<_Dp> __y) _NOEXCEPT {101 bool __t = __x;102 __x = __y;103 __y = __t;104}105 106template <class _Cp>107inline _LIBCPP_HIDE_FROM_ABI void swap(__bit_reference<_Cp> __x, bool& __y) _NOEXCEPT {108 bool __t = __x;109 __x = __y;110 __y = __t;111}112 113template <class _Cp>114inline _LIBCPP_HIDE_FROM_ABI void swap(bool& __x, __bit_reference<_Cp> __y) _NOEXCEPT {115 bool __t = __x;116 __x = __y;117 __y = __t;118}119 120template <class _Cp>121class __bit_const_reference {122 using __storage_type = typename _Cp::__storage_type;123 using __storage_pointer = typename _Cp::__const_storage_pointer;124 125 __storage_pointer __seg_;126 __storage_type __mask_;127 128 friend typename _Cp::__self;129 friend class __bit_iterator<_Cp, true>;130 131public:132 using __container = typename _Cp::__self;133 134 _LIBCPP_HIDE_FROM_ABI __bit_const_reference(const __bit_const_reference&) = default;135 __bit_const_reference& operator=(const __bit_const_reference&) = delete;136 137 _LIBCPP_HIDE_FROM_ABI __bit_const_reference(const __bit_reference<_Cp>& __x) _NOEXCEPT138 : __seg_(__x.__seg_),139 __mask_(__x.__mask_) {}140 141 _LIBCPP_HIDE_FROM_ABI operator bool() const _NOEXCEPT { return static_cast<bool>(*__seg_ & __mask_); }142 143 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, true> operator&() const _NOEXCEPT {144 return __bit_iterator<_Cp, true>(__seg_, static_cast<unsigned>(std::__libcpp_ctz(__mask_)));145 }146 147private:148 _LIBCPP_HIDE_FROM_ABI explicit __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT149 : __seg_(__s),150 __mask_(__m) {}151};152 153// copy154 155template <class _Cp, bool _IsConst>156_LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_aligned(157 __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {158 using _In = __bit_iterator<_Cp, _IsConst>;159 using difference_type = typename _In::difference_type;160 using __storage_type = typename _In::__storage_type;161 162 const int __bits_per_word = _In::__bits_per_word;163 difference_type __n = __last - __first;164 if (__n > 0) {165 // do first word166 if (__first.__ctz_ != 0) {167 unsigned __clz = __bits_per_word - __first.__ctz_;168 difference_type __dn = std::min(static_cast<difference_type>(__clz), __n);169 __n -= __dn;170 __storage_type __m = (__storage_type(~0) << __first.__ctz_) & (__storage_type(~0) >> (__clz - __dn));171 __storage_type __b = *__first.__seg_ & __m;172 *__result.__seg_ &= ~__m;173 *__result.__seg_ |= __b;174 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;175 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);176 ++__first.__seg_;177 // __first.__ctz_ = 0;178 }179 // __first.__ctz_ == 0;180 // do middle words181 __storage_type __nw = __n / __bits_per_word;182 std::copy_n(std::__to_address(__first.__seg_), __nw, std::__to_address(__result.__seg_));183 __n -= __nw * __bits_per_word;184 __result.__seg_ += __nw;185 // do last word186 if (__n > 0) {187 __first.__seg_ += __nw;188 __storage_type __m = __storage_type(~0) >> (__bits_per_word - __n);189 __storage_type __b = *__first.__seg_ & __m;190 *__result.__seg_ &= ~__m;191 *__result.__seg_ |= __b;192 __result.__ctz_ = static_cast<unsigned>(__n);193 }194 }195 return __result;196}197 198template <class _Cp, bool _IsConst>199_LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_unaligned(200 __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {201 using _In = __bit_iterator<_Cp, _IsConst>;202 using difference_type = typename _In::difference_type;203 using __storage_type = typename _In::__storage_type;204 205 const int __bits_per_word = _In::__bits_per_word;206 difference_type __n = __last - __first;207 if (__n > 0) {208 // do first word209 if (__first.__ctz_ != 0) {210 unsigned __clz_f = __bits_per_word - __first.__ctz_;211 difference_type __dn = std::min(static_cast<difference_type>(__clz_f), __n);212 __n -= __dn;213 __storage_type __m = (__storage_type(~0) << __first.__ctz_) & (__storage_type(~0) >> (__clz_f - __dn));214 __storage_type __b = *__first.__seg_ & __m;215 unsigned __clz_r = __bits_per_word - __result.__ctz_;216 __storage_type __ddn = std::min<__storage_type>(__dn, __clz_r);217 __m = (__storage_type(~0) << __result.__ctz_) & (__storage_type(~0) >> (__clz_r - __ddn));218 *__result.__seg_ &= ~__m;219 if (__result.__ctz_ > __first.__ctz_)220 *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_);221 else222 *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_);223 __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;224 __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word);225 __dn -= __ddn;226 if (__dn > 0) {227 __m = __storage_type(~0) >> (__bits_per_word - __dn);228 *__result.__seg_ &= ~__m;229 *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn);230 __result.__ctz_ = static_cast<unsigned>(__dn);231 }232 ++__first.__seg_;233 // __first.__ctz_ = 0;234 }235 // __first.__ctz_ == 0;236 // do middle words237 unsigned __clz_r = __bits_per_word - __result.__ctz_;238 __storage_type __m = __storage_type(~0) << __result.__ctz_;239 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) {240 __storage_type __b = *__first.__seg_;241 *__result.__seg_ &= ~__m;242 *__result.__seg_ |= __b << __result.__ctz_;243 ++__result.__seg_;244 *__result.__seg_ &= __m;245 *__result.__seg_ |= __b >> __clz_r;246 }247 // do last word248 if (__n > 0) {249 __m = __storage_type(~0) >> (__bits_per_word - __n);250 __storage_type __b = *__first.__seg_ & __m;251 __storage_type __dn = std::min(__n, static_cast<difference_type>(__clz_r));252 __m = (__storage_type(~0) << __result.__ctz_) & (__storage_type(~0) >> (__clz_r - __dn));253 *__result.__seg_ &= ~__m;254 *__result.__seg_ |= __b << __result.__ctz_;255 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;256 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);257 __n -= __dn;258 if (__n > 0) {259 __m = __storage_type(~0) >> (__bits_per_word - __n);260 *__result.__seg_ &= ~__m;261 *__result.__seg_ |= __b >> __dn;262 __result.__ctz_ = static_cast<unsigned>(__n);263 }264 }265 }266 return __result;267}268 269template <class _Cp, bool _IsConst>270inline _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false>271copy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {272 if (__first.__ctz_ == __result.__ctz_)273 return std::__copy_aligned(__first, __last, __result);274 return std::__copy_unaligned(__first, __last, __result);275}276 277// copy_backward278 279template <class _Cp, bool _IsConst>280_LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_backward_aligned(281 __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {282 using _In = __bit_iterator<_Cp, _IsConst>;283 using difference_type = typename _In::difference_type;284 using __storage_type = typename _In::__storage_type;285 286 const int __bits_per_word = _In::__bits_per_word;287 difference_type __n = __last - __first;288 if (__n > 0) {289 // do first word290 if (__last.__ctz_ != 0) {291 difference_type __dn = std::min(static_cast<difference_type>(__last.__ctz_), __n);292 __n -= __dn;293 unsigned __clz = __bits_per_word - __last.__ctz_;294 __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz);295 __storage_type __b = *__last.__seg_ & __m;296 *__result.__seg_ &= ~__m;297 *__result.__seg_ |= __b;298 __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + __result.__ctz_) % __bits_per_word);299 // __last.__ctz_ = 0300 }301 // __last.__ctz_ == 0 || __n == 0302 // __result.__ctz_ == 0 || __n == 0303 // do middle words304 __storage_type __nw = __n / __bits_per_word;305 __result.__seg_ -= __nw;306 __last.__seg_ -= __nw;307 std::copy_n(std::__to_address(__last.__seg_), __nw, std::__to_address(__result.__seg_));308 __n -= __nw * __bits_per_word;309 // do last word310 if (__n > 0) {311 __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n);312 __storage_type __b = *--__last.__seg_ & __m;313 *--__result.__seg_ &= ~__m;314 *__result.__seg_ |= __b;315 __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));316 }317 }318 return __result;319}320 321template <class _Cp, bool _IsConst>322_LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_backward_unaligned(323 __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {324 using _In = __bit_iterator<_Cp, _IsConst>;325 using difference_type = typename _In::difference_type;326 using __storage_type = typename _In::__storage_type;327 328 const int __bits_per_word = _In::__bits_per_word;329 difference_type __n = __last - __first;330 if (__n > 0) {331 // do first word332 if (__last.__ctz_ != 0) {333 difference_type __dn = std::min(static_cast<difference_type>(__last.__ctz_), __n);334 __n -= __dn;335 unsigned __clz_l = __bits_per_word - __last.__ctz_;336 __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l);337 __storage_type __b = *__last.__seg_ & __m;338 unsigned __clz_r = __bits_per_word - __result.__ctz_;339 __storage_type __ddn = std::min(__dn, static_cast<difference_type>(__result.__ctz_));340 if (__ddn > 0) {341 __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r);342 *__result.__seg_ &= ~__m;343 if (__result.__ctz_ > __last.__ctz_)344 *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);345 else346 *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_);347 __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) + __result.__ctz_) % __bits_per_word);348 __dn -= __ddn;349 }350 if (__dn > 0) {351 // __result.__ctz_ == 0352 --__result.__seg_;353 __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1));354 __m = ~__storage_type(0) << __result.__ctz_;355 *__result.__seg_ &= ~__m;356 __last.__ctz_ -= __dn + __ddn;357 *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);358 }359 // __last.__ctz_ = 0360 }361 // __last.__ctz_ == 0 || __n == 0362 // __result.__ctz_ != 0 || __n == 0363 // do middle words364 unsigned __clz_r = __bits_per_word - __result.__ctz_;365 __storage_type __m = ~__storage_type(0) >> __clz_r;366 for (; __n >= __bits_per_word; __n -= __bits_per_word) {367 __storage_type __b = *--__last.__seg_;368 *__result.__seg_ &= ~__m;369 *__result.__seg_ |= __b >> __clz_r;370 *--__result.__seg_ &= __m;371 *__result.__seg_ |= __b << __result.__ctz_;372 }373 // do last word374 if (__n > 0) {375 __m = ~__storage_type(0) << (__bits_per_word - __n);376 __storage_type __b = *--__last.__seg_ & __m;377 __clz_r = __bits_per_word - __result.__ctz_;378 __storage_type __dn = std::min(__n, static_cast<difference_type>(__result.__ctz_));379 __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r);380 *__result.__seg_ &= ~__m;381 *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_);382 __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + __result.__ctz_) % __bits_per_word);383 __n -= __dn;384 if (__n > 0) {385 // __result.__ctz_ == 0386 --__result.__seg_;387 __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));388 __m = ~__storage_type(0) << __result.__ctz_;389 *__result.__seg_ &= ~__m;390 *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn));391 }392 }393 }394 return __result;395}396 397template <class _Cp, bool _IsConst>398inline _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> copy_backward(399 __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {400 if (__last.__ctz_ == __result.__ctz_)401 return std::__copy_backward_aligned(__first, __last, __result);402 return std::__copy_backward_unaligned(__first, __last, __result);403}404 405// move406 407template <class _Cp, bool _IsConst>408inline _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false>409move(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {410 return std::copy(__first, __last, __result);411}412 413// move_backward414 415template <class _Cp, bool _IsConst>416inline _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> move_backward(417 __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {418 return std::copy_backward(__first, __last, __result);419}420 421// swap_ranges422 423template <class _Cl, class _Cr>424_LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cr, false> __swap_ranges_aligned(425 __bit_iterator<_Cl, false> __first, __bit_iterator<_Cl, false> __last, __bit_iterator<_Cr, false> __result) {426 using _I1 = __bit_iterator<_Cl, false>;427 using difference_type = typename _I1::difference_type;428 using __storage_type = typename _I1::__storage_type;429 430 const int __bits_per_word = _I1::__bits_per_word;431 difference_type __n = __last - __first;432 if (__n > 0) {433 // do first word434 if (__first.__ctz_ != 0) {435 unsigned __clz = __bits_per_word - __first.__ctz_;436 difference_type __dn = std::min(static_cast<difference_type>(__clz), __n);437 __n -= __dn;438 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn));439 __storage_type __b1 = *__first.__seg_ & __m;440 *__first.__seg_ &= ~__m;441 __storage_type __b2 = *__result.__seg_ & __m;442 *__result.__seg_ &= ~__m;443 *__result.__seg_ |= __b1;444 *__first.__seg_ |= __b2;445 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;446 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);447 ++__first.__seg_;448 // __first.__ctz_ = 0;449 }450 // __first.__ctz_ == 0;451 // do middle words452 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_)453 swap(*__first.__seg_, *__result.__seg_);454 // do last word455 if (__n > 0) {456 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);457 __storage_type __b1 = *__first.__seg_ & __m;458 *__first.__seg_ &= ~__m;459 __storage_type __b2 = *__result.__seg_ & __m;460 *__result.__seg_ &= ~__m;461 *__result.__seg_ |= __b1;462 *__first.__seg_ |= __b2;463 __result.__ctz_ = static_cast<unsigned>(__n);464 }465 }466 return __result;467}468 469template <class _Cl, class _Cr>470_LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cr, false> __swap_ranges_unaligned(471 __bit_iterator<_Cl, false> __first, __bit_iterator<_Cl, false> __last, __bit_iterator<_Cr, false> __result) {472 using _I1 = __bit_iterator<_Cl, false>;473 using difference_type = typename _I1::difference_type;474 using __storage_type = typename _I1::__storage_type;475 476 const int __bits_per_word = _I1::__bits_per_word;477 difference_type __n = __last - __first;478 if (__n > 0) {479 // do first word480 if (__first.__ctz_ != 0) {481 unsigned __clz_f = __bits_per_word - __first.__ctz_;482 difference_type __dn = std::min(static_cast<difference_type>(__clz_f), __n);483 __n -= __dn;484 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));485 __storage_type __b1 = *__first.__seg_ & __m;486 *__first.__seg_ &= ~__m;487 unsigned __clz_r = __bits_per_word - __result.__ctz_;488 __storage_type __ddn = std::min<__storage_type>(__dn, __clz_r);489 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));490 __storage_type __b2 = *__result.__seg_ & __m;491 *__result.__seg_ &= ~__m;492 if (__result.__ctz_ > __first.__ctz_) {493 unsigned __s = __result.__ctz_ - __first.__ctz_;494 *__result.__seg_ |= __b1 << __s;495 *__first.__seg_ |= __b2 >> __s;496 } else {497 unsigned __s = __first.__ctz_ - __result.__ctz_;498 *__result.__seg_ |= __b1 >> __s;499 *__first.__seg_ |= __b2 << __s;500 }501 __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;502 __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word);503 __dn -= __ddn;504 if (__dn > 0) {505 __m = ~__storage_type(0) >> (__bits_per_word - __dn);506 __b2 = *__result.__seg_ & __m;507 *__result.__seg_ &= ~__m;508 unsigned __s = __first.__ctz_ + __ddn;509 *__result.__seg_ |= __b1 >> __s;510 *__first.__seg_ |= __b2 << __s;511 __result.__ctz_ = static_cast<unsigned>(__dn);512 }513 ++__first.__seg_;514 // __first.__ctz_ = 0;515 }516 // __first.__ctz_ == 0;517 // do middle words518 __storage_type __m = ~__storage_type(0) << __result.__ctz_;519 unsigned __clz_r = __bits_per_word - __result.__ctz_;520 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) {521 __storage_type __b1 = *__first.__seg_;522 __storage_type __b2 = *__result.__seg_ & __m;523 *__result.__seg_ &= ~__m;524 *__result.__seg_ |= __b1 << __result.__ctz_;525 *__first.__seg_ = __b2 >> __result.__ctz_;526 ++__result.__seg_;527 __b2 = *__result.__seg_ & ~__m;528 *__result.__seg_ &= __m;529 *__result.__seg_ |= __b1 >> __clz_r;530 *__first.__seg_ |= __b2 << __clz_r;531 }532 // do last word533 if (__n > 0) {534 __m = ~__storage_type(0) >> (__bits_per_word - __n);535 __storage_type __b1 = *__first.__seg_ & __m;536 *__first.__seg_ &= ~__m;537 __storage_type __dn = std::min<__storage_type>(__n, __clz_r);538 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));539 __storage_type __b2 = *__result.__seg_ & __m;540 *__result.__seg_ &= ~__m;541 *__result.__seg_ |= __b1 << __result.__ctz_;542 *__first.__seg_ |= __b2 >> __result.__ctz_;543 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;544 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);545 __n -= __dn;546 if (__n > 0) {547 __m = ~__storage_type(0) >> (__bits_per_word - __n);548 __b2 = *__result.__seg_ & __m;549 *__result.__seg_ &= ~__m;550 *__result.__seg_ |= __b1 >> __dn;551 *__first.__seg_ |= __b2 << __dn;552 __result.__ctz_ = static_cast<unsigned>(__n);553 }554 }555 }556 return __result;557}558 559template <class _Cl, class _Cr>560inline _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cr, false> swap_ranges(561 __bit_iterator<_Cl, false> __first1, __bit_iterator<_Cl, false> __last1, __bit_iterator<_Cr, false> __first2) {562 if (__first1.__ctz_ == __first2.__ctz_)563 return std::__swap_ranges_aligned(__first1, __last1, __first2);564 return std::__swap_ranges_unaligned(__first1, __last1, __first2);565}566 567// rotate568 569template <class _Cp>570struct __bit_array {571 using difference_type = typename _Cp::difference_type;572 using __storage_type = typename _Cp::__storage_type;573 using __storage_pointer = typename _Cp::__storage_pointer;574 using iterator = typename _Cp::iterator;575 576 static const unsigned __bits_per_word = _Cp::__bits_per_word;577 static const unsigned _Np = 4;578 579 difference_type __size_;580 __storage_type __word_[_Np];581 582 _LIBCPP_HIDE_FROM_ABI static difference_type capacity() {583 return static_cast<difference_type>(_Np * __bits_per_word);584 }585 _LIBCPP_HIDE_FROM_ABI explicit __bit_array(difference_type __s) : __size_(__s) {586 if (__libcpp_is_constant_evaluated()) {587 for (size_t __i = 0; __i != __bit_array<_Cp>::_Np; ++__i)588 std::__construct_at(__word_ + __i, 0);589 }590 }591 _LIBCPP_HIDE_FROM_ABI iterator begin() {592 return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]), 0);593 }594 _LIBCPP_HIDE_FROM_ABI iterator end() {595 return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]) + __size_ / __bits_per_word,596 static_cast<unsigned>(__size_ % __bits_per_word));597 }598};599 600template <class _Cp>601_LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false>602rotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last) {603 using _I1 = __bit_iterator<_Cp, false>;604 using difference_type = typename _I1::difference_type;605 606 difference_type __d1 = __middle - __first;607 difference_type __d2 = __last - __middle;608 _I1 __r = __first + __d2;609 while (__d1 != 0 && __d2 != 0) {610 if (__d1 <= __d2) {611 if (__d1 <= __bit_array<_Cp>::capacity()) {612 __bit_array<_Cp> __b(__d1);613 std::copy(__first, __middle, __b.begin());614 std::copy(__b.begin(), __b.end(), std::copy(__middle, __last, __first));615 break;616 } else {617 __bit_iterator<_Cp, false> __mp = std::swap_ranges(__first, __middle, __middle);618 __first = __middle;619 __middle = __mp;620 __d2 -= __d1;621 }622 } else {623 if (__d2 <= __bit_array<_Cp>::capacity()) {624 __bit_array<_Cp> __b(__d2);625 std::copy(__middle, __last, __b.begin());626 std::copy_backward(__b.begin(), __b.end(), std::copy_backward(__first, __middle, __last));627 break;628 } else {629 __bit_iterator<_Cp, false> __mp = __first + __d2;630 std::swap_ranges(__first, __mp, __middle);631 __first = __mp;632 __d1 -= __d2;633 }634 }635 }636 return __r;637}638 639// equal640 641template <class _Cp, bool _IC1, bool _IC2>642_LIBCPP_HIDE_FROM_ABI bool __equal_unaligned(643 __bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) {644 using _It = __bit_iterator<_Cp, _IC1>;645 using difference_type = typename _It::difference_type;646 using __storage_type = typename _It::__storage_type;647 648 const int __bits_per_word = _It::__bits_per_word;649 difference_type __n = __last1 - __first1;650 if (__n > 0) {651 // do first word652 if (__first1.__ctz_ != 0) {653 unsigned __clz_f = __bits_per_word - __first1.__ctz_;654 difference_type __dn = std::min(static_cast<difference_type>(__clz_f), __n);655 __n -= __dn;656 __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));657 __storage_type __b = *__first1.__seg_ & __m;658 unsigned __clz_r = __bits_per_word - __first2.__ctz_;659 __storage_type __ddn = std::min<__storage_type>(__dn, __clz_r);660 __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));661 if (__first2.__ctz_ > __first1.__ctz_) {662 if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_)))663 return false;664 } else {665 if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_)))666 return false;667 }668 __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word;669 __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word);670 __dn -= __ddn;671 if (__dn > 0) {672 __m = ~__storage_type(0) >> (__bits_per_word - __dn);673 if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn)))674 return false;675 __first2.__ctz_ = static_cast<unsigned>(__dn);676 }677 ++__first1.__seg_;678 // __first1.__ctz_ = 0;679 }680 // __first1.__ctz_ == 0;681 // do middle words682 unsigned __clz_r = __bits_per_word - __first2.__ctz_;683 __storage_type __m = ~__storage_type(0) << __first2.__ctz_;684 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_) {685 __storage_type __b = *__first1.__seg_;686 if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_))687 return false;688 ++__first2.__seg_;689 if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r))690 return false;691 }692 // do last word693 if (__n > 0) {694 __m = ~__storage_type(0) >> (__bits_per_word - __n);695 __storage_type __b = *__first1.__seg_ & __m;696 __storage_type __dn = std::min(__n, static_cast<difference_type>(__clz_r));697 __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));698 if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_))699 return false;700 __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word;701 __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word);702 __n -= __dn;703 if (__n > 0) {704 __m = ~__storage_type(0) >> (__bits_per_word - __n);705 if ((*__first2.__seg_ & __m) != (__b >> __dn))706 return false;707 }708 }709 }710 return true;711}712 713template <class _Cp, bool _IC1, bool _IC2>714_LIBCPP_HIDE_FROM_ABI bool __equal_aligned(715 __bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) {716 using _It = __bit_iterator<_Cp, _IC1>;717 using difference_type = typename _It::difference_type;718 using __storage_type = typename _It::__storage_type;719 720 const int __bits_per_word = _It::__bits_per_word;721 difference_type __n = __last1 - __first1;722 if (__n > 0) {723 // do first word724 if (__first1.__ctz_ != 0) {725 unsigned __clz = __bits_per_word - __first1.__ctz_;726 difference_type __dn = std::min(static_cast<difference_type>(__clz), __n);727 __n -= __dn;728 __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn));729 if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))730 return false;731 ++__first2.__seg_;732 ++__first1.__seg_;733 // __first1.__ctz_ = 0;734 // __first2.__ctz_ = 0;735 }736 // __first1.__ctz_ == 0;737 // __first2.__ctz_ == 0;738 // do middle words739 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_)740 if (*__first2.__seg_ != *__first1.__seg_)741 return false;742 // do last word743 if (__n > 0) {744 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);745 if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))746 return false;747 }748 }749 return true;750}751 752template <class _Cp, bool _IC1, bool _IC2>753inline _LIBCPP_HIDE_FROM_ABI bool754equal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) {755 if (__first1.__ctz_ == __first2.__ctz_)756 return std::__equal_aligned(__first1, __last1, __first2);757 return std::__equal_unaligned(__first1, __last1, __first2);758}759 760template <class _Cp, bool _IsConst, typename _Cp::__storage_type>761class __bit_iterator {762public:763 using difference_type = typename _Cp::difference_type;764 using value_type = bool;765 using pointer = __bit_iterator;766#ifndef _LIBCPP_ABI_BITSET_VECTOR_BOOL_CONST_SUBSCRIPT_RETURN_BOOL767 using reference = __conditional_t<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >;768#else769 using reference = __conditional_t<_IsConst, bool, __bit_reference<_Cp> >;770#endif771 using iterator_category = random_access_iterator_tag;772 773private:774 using __storage_type = typename _Cp::__storage_type;775 using __storage_pointer =776 __conditional_t<_IsConst, typename _Cp::__const_storage_pointer, typename _Cp::__storage_pointer>;777 778 static const unsigned __bits_per_word = _Cp::__bits_per_word;779 780 __storage_pointer __seg_;781 unsigned __ctz_;782 783public:784 _LIBCPP_HIDE_FROM_ABI __bit_iterator() _NOEXCEPT {}785 786 // When _IsConst=false, this is the copy constructor.787 // It is non-trivial. Making it trivial would break ABI.788 // When _IsConst=true, this is a converting constructor;789 // the copy and move constructors are implicitly generated790 // and trivial.791 _LIBCPP_HIDE_FROM_ABI __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT792 : __seg_(__it.__seg_),793 __ctz_(__it.__ctz_) {}794 795 // When _IsConst=false, we have a user-provided copy constructor,796 // so we must also provide a copy assignment operator because797 // the implicit generation of a defaulted one is deprecated.798 // When _IsConst=true, the assignment operators are799 // implicitly generated and trivial.800 _LIBCPP_HIDE_FROM_ABI __bit_iterator& operator=(const _If<_IsConst, struct __private_nat, __bit_iterator>& __it) {801 __seg_ = __it.__seg_;802 __ctz_ = __it.__ctz_;803 return *this;804 }805 806 _LIBCPP_HIDE_FROM_ABI reference operator*() const _NOEXCEPT {807 return __conditional_t<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >(808 __seg_, __storage_type(1) << __ctz_);809 }810 811 _LIBCPP_HIDE_FROM_ABI __bit_iterator& operator++() {812 if (__ctz_ != __bits_per_word - 1)813 ++__ctz_;814 else {815 __ctz_ = 0;816 ++__seg_;817 }818 return *this;819 }820 821 _LIBCPP_HIDE_FROM_ABI __bit_iterator operator++(int) {822 __bit_iterator __tmp = *this;823 ++(*this);824 return __tmp;825 }826 827 _LIBCPP_HIDE_FROM_ABI __bit_iterator& operator--() {828 if (__ctz_ != 0)829 --__ctz_;830 else {831 __ctz_ = __bits_per_word - 1;832 --__seg_;833 }834 return *this;835 }836 837 _LIBCPP_HIDE_FROM_ABI __bit_iterator operator--(int) {838 __bit_iterator __tmp = *this;839 --(*this);840 return __tmp;841 }842 843 _LIBCPP_HIDE_FROM_ABI __bit_iterator& operator+=(difference_type __n) {844 if (__n >= 0)845 __seg_ += (__n + __ctz_) / __bits_per_word;846 else847 __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1) /848 static_cast<difference_type>(__bits_per_word);849 __n &= (__bits_per_word - 1);850 __ctz_ = static_cast<unsigned>((__n + __ctz_) % __bits_per_word);851 return *this;852 }853 854 _LIBCPP_HIDE_FROM_ABI __bit_iterator& operator-=(difference_type __n) { return *this += -__n; }855 856 _LIBCPP_HIDE_FROM_ABI __bit_iterator operator+(difference_type __n) const {857 __bit_iterator __t(*this);858 __t += __n;859 return __t;860 }861 862 _LIBCPP_HIDE_FROM_ABI __bit_iterator operator-(difference_type __n) const {863 __bit_iterator __t(*this);864 __t -= __n;865 return __t;866 }867 868 _LIBCPP_HIDE_FROM_ABI friend __bit_iterator operator+(difference_type __n, const __bit_iterator& __it) {869 return __it + __n;870 }871 872 _LIBCPP_HIDE_FROM_ABI friend difference_type operator-(const __bit_iterator& __x, const __bit_iterator& __y) {873 return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;874 }875 876 _LIBCPP_HIDE_FROM_ABI reference operator[](difference_type __n) const { return *(*this + __n); }877 878 _LIBCPP_HIDE_FROM_ABI friend bool operator==(const __bit_iterator& __x, const __bit_iterator& __y) {879 return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;880 }881 882 _LIBCPP_HIDE_FROM_ABI friend bool operator!=(const __bit_iterator& __x, const __bit_iterator& __y) {883 return !(__x == __y);884 }885 886 _LIBCPP_HIDE_FROM_ABI friend bool operator<(const __bit_iterator& __x, const __bit_iterator& __y) {887 return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);888 }889 890 _LIBCPP_HIDE_FROM_ABI friend bool operator>(const __bit_iterator& __x, const __bit_iterator& __y) {891 return __y < __x;892 }893 894 _LIBCPP_HIDE_FROM_ABI friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y) {895 return !(__y < __x);896 }897 898 _LIBCPP_HIDE_FROM_ABI friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y) {899 return !(__x < __y);900 }901 902private:903 _LIBCPP_HIDE_FROM_ABI explicit __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT904 : __seg_(__s),905 __ctz_(__ctz) {}906 907 friend typename _Cp::__self;908 909 friend class __bit_reference<_Cp>;910 friend class __bit_const_reference<_Cp>;911 friend class __bit_iterator<_Cp, true>;912 template <class _Dp>913 friend struct __bit_array;914 915 template <bool _FillVal, class _Dp>916 friend void __fill_n_bool(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n);917 918 template <class _Dp, bool _IC>919 friend __bit_iterator<_Dp, false> __copy_aligned(920 __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result);921 template <class _Dp, bool _IC>922 friend __bit_iterator<_Dp, false> __copy_unaligned(923 __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result);924 template <class _Dp, bool _IC>925 friend __bit_iterator<_Dp, false>926 copy(__bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result);927 template <class _Dp, bool _IC>928 friend __bit_iterator<_Dp, false> __copy_backward_aligned(929 __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result);930 template <class _Dp, bool _IC>931 friend __bit_iterator<_Dp, false> __copy_backward_unaligned(932 __bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result);933 template <class _Dp, bool _IC>934 friend __bit_iterator<_Dp, false>935 copy_backward(__bit_iterator<_Dp, _IC> __first, __bit_iterator<_Dp, _IC> __last, __bit_iterator<_Dp, false> __result);936 template <class _Cl, class _Cr>937 friend __bit_iterator<_Cr, false>938 __swap_ranges_aligned(__bit_iterator<_Cl, false>, __bit_iterator<_Cl, false>, __bit_iterator<_Cr, false>);939 template <class _Cl, class _Cr>940 friend __bit_iterator<_Cr, false>941 __swap_ranges_unaligned(__bit_iterator<_Cl, false>, __bit_iterator<_Cl, false>, __bit_iterator<_Cr, false>);942 template <class _Cl, class _Cr>943 friend __bit_iterator<_Cr, false>944 swap_ranges(__bit_iterator<_Cl, false>, __bit_iterator<_Cl, false>, __bit_iterator<_Cr, false>);945 template <class _Dp>946 friend __bit_iterator<_Dp, false>947 rotate(__bit_iterator<_Dp, false>, __bit_iterator<_Dp, false>, __bit_iterator<_Dp, false>);948 template <class _Dp, bool _IC1, bool _IC2>949 friend bool __equal_aligned(__bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC2>);950 template <class _Dp, bool _IC1, bool _IC2>951 friend bool __equal_unaligned(__bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC2>);952 template <class _Dp, bool _IC1, bool _IC2>953 friend bool equal(__bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC1>, __bit_iterator<_Dp, _IC2>);954 template <bool _ToFind, class _Dp, bool _IC>955 friend __bit_iterator<_Dp, _IC> __find_bool(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);956 template <bool _ToCount, class _Dp, bool _IC>957 friend typename __bit_iterator<_Dp, _IC>::difference_type958 _LIBCPP_HIDE_FROM_ABI __count_bool(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);959};960 961_LIBCPP_END_NAMESPACE_STD962 963_LIBCPP_POP_MACROS964 965#endif // _LIBCPP___CXX03___BIT_REFERENCE966