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 _It(__first.__seg_, __first.__ctz_ + __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 _It(__first.__seg_, __first.__ctz_ + __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(__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     typedef typename _I1::__storage_type __storage_type;
 910     difference_type __d1 = __middle - __first;
 911     difference_type __d2 = __last - __middle;
 912     _I1 __r = __first + __d2;
 913     while (__d1 != 0 && __d2 != 0)
 914     {
 915         if (__d1 <= __d2)
 916         {
 917             if (__d1 <= __bit_array<_Cp>::capacity())
 918             {
 919                 __bit_array<_Cp> __b(__d1);
 920                 _VSTD::copy(__first, __middle, __b.begin());
 921                 _VSTD::copy(__b.begin(), __b.end(), _VSTD::copy(__middle, __last, __first));
 922                 break;
 923             }
 924             else
 925             {
 926                 __bit_iterator<_Cp, false> __mp = _VSTD::swap_ranges(__first, __middle, __middle);
 927                 __first = __middle;
 928                 __middle = __mp;
 929                 __d2 -= __d1;
 930             }
 931         }
 932         else
 933         {
 934             if (__d2 <= __bit_array<_Cp>::capacity())
 935             {
 936                 __bit_array<_Cp> __b(__d2);
 937                 _VSTD::copy(__middle, __last, __b.begin());
 938                 _VSTD::copy_backward(__b.begin(), __b.end(), _VSTD::copy_backward(__first, __middle, __last));
 939                 break;
 940             }
 941             else
 942             {
 943                 __bit_iterator<_Cp, false> __mp = __first + __d2;
 944                 _VSTD::swap_ranges(__first, __mp, __middle);
 945                 __first = __mp;
 946                 __d1 -= __d2;
 947             }
 948         }
 949     }
 950     return __r;
 951 }
 952
 953 // equal
 954
 955 template <class _Cp, bool _IC1, bool _IC2>
 956 bool
 957 __equal_unaligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1,
 958                   __bit_iterator<_Cp, _IC2> __first2)
 959 {
 960     typedef __bit_iterator<_Cp, _IC1> _It;
 961     typedef  typename _It::difference_type difference_type;
 962     typedef typename _It::__storage_type __storage_type;
 963     static const unsigned __bits_per_word = _It::__bits_per_word;
 964     difference_type __n = __last1 - __first1;
 965     if (__n > 0)
 966     {
 967         // do first word
 968         if (__first1.__ctz_ != 0)
 969         {
 970             unsigned __clz_f = __bits_per_word - __first1.__ctz_;
 971             difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
 972             __n -= __dn;
 973             __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
 974             __storage_type __b = *__first1.__seg_ & __m;
 975             unsigned __clz_r = __bits_per_word - __first2.__ctz_;
 976             __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
 977             __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
 978             if (__first2.__ctz_ > __first1.__ctz_)
 979             {
 980                 if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_)))
 981                     return false;
 982             }
 983             else
 984             {
 985                 if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_)))
 986                     return false;
 987             }
 988             __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word;
 989             __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_)  % __bits_per_word);
 990             __dn -= __ddn;
 991             if (__dn > 0)
 992             {
 993                 __m = ~__storage_type(0) >> (__bits_per_word - __dn);
 994                 if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn)))
 995                     return false;
 996                 __first2.__ctz_ = static_cast<unsigned>(__dn);
 997             }
 998             ++__first1.__seg_;
 999             // __first1.__ctz_ = 0;
1000         }
1001         // __first1.__ctz_ == 0;
1002         // do middle words
1003         unsigned __clz_r = __bits_per_word - __first2.__ctz_;
1004         __storage_type __m = ~__storage_type(0) << __first2.__ctz_;
1005         for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_)
1006         {
1007             __storage_type __b = *__first1.__seg_;
1008             if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_))
1009                 return false;
1010             ++__first2.__seg_;
1011             if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r))
1012                 return false;
1013         }
1014         // do last word
1015         if (__n > 0)
1016         {
1017             __m = ~__storage_type(0) >> (__bits_per_word - __n);
1018             __storage_type __b = *__first1.__seg_ & __m;
1019             __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r));
1020             __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
1021             if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_))
1022                 return false;
1023             __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word;
1024             __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_)  % __bits_per_word);
1025             __n -= __dn;
1026             if (__n > 0)
1027             {
1028                 __m = ~__storage_type(0) >> (__bits_per_word - __n);
1029                 if ((*__first2.__seg_ & __m) != (__b >> __dn))
1030                     return false;
1031             }
1032         }
1033     }
1034     return true;
1035 }
1036
1037 template <class _Cp, bool _IC1, bool _IC2>
1038 bool
1039 __equal_aligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1,
1040                 __bit_iterator<_Cp, _IC2> __first2)
1041 {
1042     typedef __bit_iterator<_Cp, _IC1> _It;
1043     typedef  typename _It::difference_type difference_type;
1044     typedef typename _It::__storage_type __storage_type;
1045     static const unsigned __bits_per_word = _It::__bits_per_word;
1046     difference_type __n = __last1 - __first1;
1047     if (__n > 0)
1048     {
1049         // do first word
1050         if (__first1.__ctz_ != 0)
1051         {
1052             unsigned __clz = __bits_per_word - __first1.__ctz_;
1053             difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
1054             __n -= __dn;
1055             __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
1056             if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))
1057                 return false;
1058             ++__first2.__seg_;
1059             ++__first1.__seg_;
1060             // __first1.__ctz_ = 0;
1061             // __first2.__ctz_ = 0;
1062         }
1063         // __first1.__ctz_ == 0;
1064         // __first2.__ctz_ == 0;
1065         // do middle words
1066         for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_)
1067             if (*__first2.__seg_ != *__first1.__seg_)
1068                 return false;
1069         // do last word
1070         if (__n > 0)
1071         {
1072             __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
1073             if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))
1074                 return false;
1075         }
1076     }
1077     return true;
1078 }
1079
1080 template <class _Cp, bool _IC1, bool _IC2>
1081 inline _LIBCPP_INLINE_VISIBILITY
1082 bool
1083 equal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2)
1084 {
1085     if (__first1.__ctz_ == __first2.__ctz_)
1086         return __equal_aligned(__first1, __last1, __first2);
1087     return __equal_unaligned(__first1, __last1, __first2);
1088 }
1089
1090 template <class _Cp, bool _IsConst,
1091           typename _Cp::__storage_type>
1092 class __bit_iterator
1093 {
1094 public:
1095     typedef typename _Cp::difference_type                                                          difference_type;
1096     typedef bool                                                                                  value_type;
1097     typedef __bit_iterator                                                                        pointer;
1098     typedef typename conditional<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >::type reference;
1099     typedef random_access_iterator_tag                                                            iterator_category;
1100
1101 private:
1102     typedef typename _Cp::__storage_type                                           __storage_type;
1103     typedef typename conditional<_IsConst, typename _Cp::__const_storage_pointer,
1104                                            typename _Cp::__storage_pointer>::type  __storage_pointer;
1105     static const unsigned __bits_per_word = _Cp::__bits_per_word;
1106
1107     __storage_pointer __seg_;
1108     unsigned          __ctz_;
1109
1110 public:
1111     _LIBCPP_INLINE_VISIBILITY __bit_iterator() _NOEXCEPT
1112 #if _LIBCPP_STD_VER > 11
1113     : __seg_(nullptr), __ctz_(0)
1114 #endif
1115     {}
1116
1117     _LIBCPP_INLINE_VISIBILITY
1118     __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT
1119         : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {}
1120
1121     _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT
1122         {return reference(__seg_, __storage_type(1) << __ctz_);}
1123
1124     _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator++()
1125     {
1126         if (__ctz_ != __bits_per_word-1)
1127             ++__ctz_;
1128         else
1129         {
1130             __ctz_ = 0;
1131             ++__seg_;
1132         }
1133         return *this;
1134     }
1135
1136     _LIBCPP_INLINE_VISIBILITY __bit_iterator operator++(int)
1137     {
1138         __bit_iterator __tmp = *this;
1139         ++(*this);
1140         return __tmp;
1141     }
1142
1143     _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator--()
1144     {
1145         if (__ctz_ != 0)
1146             --__ctz_;
1147         else
1148         {
1149             __ctz_ = __bits_per_word - 1;
1150             --__seg_;
1151         }
1152         return *this;
1153     }
1154
1155     _LIBCPP_INLINE_VISIBILITY __bit_iterator operator--(int)
1156     {
1157         __bit_iterator __tmp = *this;
1158         --(*this);
1159         return __tmp;
1160     }
1161
1162     _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator+=(difference_type __n)
1163     {
1164         if (__n >= 0)
1165             __seg_ += (__n + __ctz_) / __bits_per_word;
1166         else
1167             __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1)
1168                     / static_cast<difference_type>(__bits_per_word);
1169         __n &= (__bits_per_word - 1);
1170         __ctz_ = static_cast<unsigned>((__n + __ctz_)  % __bits_per_word);
1171         return *this;
1172     }
1173
1174     _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator-=(difference_type __n)
1175     {
1176         return *this += -__n;
1177     }
1178
1179     _LIBCPP_INLINE_VISIBILITY __bit_iterator operator+(difference_type __n) const
1180     {
1181         __bit_iterator __t(*this);
1182         __t += __n;
1183         return __t;
1184     }
1185
1186     _LIBCPP_INLINE_VISIBILITY __bit_iterator operator-(difference_type __n) const
1187     {
1188         __bit_iterator __t(*this);
1189         __t -= __n;
1190         return __t;
1191     }
1192
1193     _LIBCPP_INLINE_VISIBILITY
1194     friend __bit_iterator operator+(difference_type __n, const __bit_iterator& __it) {return __it + __n;}
1195
1196     _LIBCPP_INLINE_VISIBILITY
1197     friend difference_type operator-(const __bit_iterator& __x, const __bit_iterator& __y)
1198         {return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;}
1199
1200     _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const {return *(*this + __n);}
1201
1202     _LIBCPP_INLINE_VISIBILITY friend bool operator==(const __bit_iterator& __x, const __bit_iterator& __y)
1203         {return __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 !(__x == __y);}
1207
1208     _LIBCPP_INLINE_VISIBILITY friend bool operator<(const __bit_iterator& __x, const __bit_iterator& __y)
1209         {return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);}
1210
1211     _LIBCPP_INLINE_VISIBILITY friend bool operator>(const __bit_iterator& __x, const __bit_iterator& __y)
1212         {return __y < __x;}
1213
1214     _LIBCPP_INLINE_VISIBILITY friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y)
1215         {return !(__y < __x);}
1216
1217     _LIBCPP_INLINE_VISIBILITY friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y)
1218         {return !(__x < __y);}
1219
1220 private:
1221     _LIBCPP_INLINE_VISIBILITY
1222     __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT
1223         : __seg_(__s), __ctz_(__ctz) {}
1224
1225 #if defined(__clang__) || defined(__IBMCPP__) || defined(_LIBCPP_MSVC)
1226     friend typename _Cp::__self;
1227 #else
1228     friend class _Cp::__self;
1229 #endif
1230     friend class __bit_reference<_Cp>;
1231     friend class __bit_const_reference<_Cp>;
1232     friend class __bit_iterator<_Cp, true>;
1233     template <class _Dp> friend struct __bit_array;
1234     template <class _Dp> friend void __fill_n_false(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n);
1235     template <class _Dp> friend void __fill_n_true(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n);
1236     template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_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_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(__bit_iterator<_Dp, _IC> __first,
1243                                                                         __bit_iterator<_Dp, _IC> __last,
1244                                                                         __bit_iterator<_Dp, false> __result);
1245     template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_aligned(__bit_iterator<_Dp, _IC> __first,
1246                                                                                            __bit_iterator<_Dp, _IC> __last,
1247                                                                                            __bit_iterator<_Dp, false> __result);
1248     template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_unaligned(__bit_iterator<_Dp, _IC> __first,
1249                                                                                              __bit_iterator<_Dp, _IC> __last,
1250                                                                                              __bit_iterator<_Dp, false> __result);
1251     template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy_backward(__bit_iterator<_Dp, _IC> __first,
1252                                                                                  __bit_iterator<_Dp, _IC> __last,
1253                                                                                  __bit_iterator<_Dp, false> __result);
1254     template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_aligned(__bit_iterator<__C1, false>,
1255                                                                                            __bit_iterator<__C1, false>,
1256                                                                                            __bit_iterator<__C2, false>);
1257     template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_unaligned(__bit_iterator<__C1, false>,
1258                                                                                              __bit_iterator<__C1, false>,
1259                                                                                              __bit_iterator<__C2, false>);
1260     template <class __C1, class __C2>friend __bit_iterator<__C2, false> swap_ranges(__bit_iterator<__C1, false>,
1261                                                                                  __bit_iterator<__C1, false>,
1262                                                                                  __bit_iterator<__C2, false>);
1263     template <class _Dp> friend __bit_iterator<_Dp, false> rotate(__bit_iterator<_Dp, false>,
1264                                                                 __bit_iterator<_Dp, false>,
1265                                                                 __bit_iterator<_Dp, false>);
1266     template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_aligned(__bit_iterator<_Dp, _IC1>,
1267                                                     __bit_iterator<_Dp, _IC1>,
1268                                                     __bit_iterator<_Dp, _IC2>);
1269     template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_unaligned(__bit_iterator<_Dp, _IC1>,
1270                                                       __bit_iterator<_Dp, _IC1>,
1271                                                       __bit_iterator<_Dp, _IC2>);
1272     template <class _Dp, bool _IC1, bool _IC2> friend bool equal(__bit_iterator<_Dp, _IC1>,
1273                                                                 __bit_iterator<_Dp, _IC1>,
1274                                                                 __bit_iterator<_Dp, _IC2>);
1275     template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_true(__bit_iterator<_Dp, _IC>,
1276                                                                           typename _Dp::size_type);
1277     template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_false(__bit_iterator<_Dp, _IC>,
1278                                                                            typename _Dp::size_type);
1279     template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type
1280                    __count_bool_true(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
1281     template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type
1282                    __count_bool_false(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
1283 };
1284
1285 _LIBCPP_END_NAMESPACE_STD
1286
1287 #endif  // _LIBCPP___BIT_REFERENCE