contrib/libc++/include/__bit_reference

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