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