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