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-exception 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef _LIBCPP___CXX03___BIT_REFERENCE 11#define _LIBCPP___CXX03___BIT_REFERENCE 12 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_header 30#endif 31 32_LIBCPP_PUSH_MACROS 33#include <__cxx03/__undef_macros> 34 35_LIBCPP_BEGIN_NAMESPACE_STD 36 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 else 70 *__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) _NOEXCEPT 85 : __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) _NOEXCEPT 138 : __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) _NOEXCEPT 149 : __seg_(__s), 150 __mask_(__m) {} 151}; 152 153// copy 154 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 word 166 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 words 181 __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 word 186 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 word 209 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 else 222 *__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 words 237 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 word 248 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_backward 278 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 word 290 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_ = 0 300 } 301 // __last.__ctz_ == 0 || __n == 0 302 // __result.__ctz_ == 0 || __n == 0 303 // do middle words 304 __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 word 310 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 word 332 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 else 346 *__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_ == 0 352 --__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_ = 0 360 } 361 // __last.__ctz_ == 0 || __n == 0 362 // __result.__ctz_ != 0 || __n == 0 363 // do middle words 364 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 word 374 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_ == 0 386 --__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// move 406 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_backward 414 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_ranges 422 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 word 434 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 words 452 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_) 453 swap(*__first.__seg_, *__result.__seg_); 454 // do last word 455 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 word 480 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 words 518 __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 word 533 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// rotate 568 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// equal 640 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 word 652 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 words 682 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 word 693 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 word 724 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 words 739 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 word 743 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 bool 754equal(__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_BOOL 767 using reference = __conditional_t<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >; 768#else 769 using reference = __conditional_t<_IsConst, bool, __bit_reference<_Cp> >; 770#endif 771 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 generated 790 // and trivial. 791 _LIBCPP_HIDE_FROM_ABI __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT 792 : __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 because 797 // the implicit generation of a defaulted one is deprecated. 798 // When _IsConst=true, the assignment operators are 799 // 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 else 847 __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) _NOEXCEPT 904 : __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_type 958 _LIBCPP_HIDE_FROM_ABI __count_bool(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); 959}; 960 961_LIBCPP_END_NAMESPACE_STD 962 963_LIBCPP_POP_MACROS 964 965#endif // _LIBCPP___CXX03___BIT_REFERENCE 966