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