contrib/libc++/include/__bit_reference

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