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