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