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