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