contrib/libc++/include/__bit_reference

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