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