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