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