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