diff options
Diffstat (limited to 'tests/libcxx/include/__bit_reference')
| -rw-r--r-- | tests/libcxx/include/__bit_reference | 1225 |
1 files changed, 0 insertions, 1225 deletions
diff --git a/tests/libcxx/include/__bit_reference b/tests/libcxx/include/__bit_reference deleted file mode 100644 index bef27625..00000000 --- a/tests/libcxx/include/__bit_reference +++ /dev/null @@ -1,1225 +0,0 @@ -// -*- C++ -*- -//===----------------------------------------------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is dual licensed under the MIT and the University of Illinois Open -// Source Licenses. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___BIT_REFERENCE -#define _LIBCPP___BIT_REFERENCE - -#include <__config> -#include <algorithm> - -#pragma GCC system_header - -_LIBCPP_BEGIN_NAMESPACE_STD - -template <class _C, bool _IsConst> class __bit_iterator; -template <class _C> class __bit_const_reference; - -template <class _C> -class __bit_reference -{ - typedef typename _C::__storage_type __storage_type; - typedef typename _C::__storage_pointer __storage_pointer; - - __storage_pointer __seg_; - __storage_type __mask_; - -#if defined(__clang__) - friend typename _C::__self; -#else - friend class _C::__self; -#endif - friend class __bit_const_reference<_C>; - friend class __bit_iterator<_C, false>; -public: - _LIBCPP_INLINE_VISIBILITY operator bool() const {return static_cast<bool>(*__seg_ & __mask_);} - _LIBCPP_INLINE_VISIBILITY bool operator ~() const {return !static_cast<bool>(*this);} - - _LIBCPP_INLINE_VISIBILITY - __bit_reference& operator=(bool __x) - { - if (__x) - *__seg_ |= __mask_; - else - *__seg_ &= ~__mask_; - return *this; - } - - _LIBCPP_INLINE_VISIBILITY - __bit_reference& operator=(const __bit_reference& __x) {return operator=(static_cast<bool>(__x));} - - _LIBCPP_INLINE_VISIBILITY void flip() {*__seg_ ^= __mask_;} - _LIBCPP_INLINE_VISIBILITY __bit_iterator<_C, false> operator&() const - {return __bit_iterator<_C, false>(__seg_, static_cast<unsigned>(__ctz(__mask_)));} -private: - _LIBCPP_INLINE_VISIBILITY - __bit_reference(__storage_pointer __s, __storage_type __m) : __seg_(__s), __mask_(__m) {} -}; - -template <class _C, class _D> -_LIBCPP_INLINE_VISIBILITY inline -void -swap(__bit_reference<_C> __x, __bit_reference<_D> __y) -{ - bool __t = __x; - __x = __y; - __y = __t; -} - -template <class _C> -_LIBCPP_INLINE_VISIBILITY inline -void -swap(__bit_reference<_C> __x, bool& __y) -{ - bool __t = __x; - __x = __y; - __y = __t; -} - -template <class _C> -_LIBCPP_INLINE_VISIBILITY inline -void -swap(bool& __x, __bit_reference<_C> __y) -{ - bool __t = __x; - __x = __y; - __y = __t; -} - -template <class _C> -class __bit_const_reference -{ - typedef typename _C::__storage_type __storage_type; - typedef typename _C::__const_storage_pointer __storage_pointer; - - __storage_pointer __seg_; - __storage_type __mask_; - -#if defined(__clang__) - friend typename _C::__self; -#else - friend class _C::__self; -#endif - friend class __bit_iterator<_C, true>; -public: - _LIBCPP_INLINE_VISIBILITY - __bit_const_reference(const __bit_reference<_C>& __x) - : __seg_(__x.__seg_), __mask_(__x.__mask_) {} - - _LIBCPP_INLINE_VISIBILITY operator bool() const {return static_cast<bool>(*__seg_ & __mask_);} - - _LIBCPP_INLINE_VISIBILITY __bit_iterator<_C, true> operator&() const - {return __bit_iterator<_C, true>(__seg_, static_cast<unsigned>(__ctz(__mask_)));} -private: - _LIBCPP_INLINE_VISIBILITY - __bit_const_reference(__storage_pointer __s, __storage_type __m) : __seg_(__s), __mask_(__m) {} - - __bit_const_reference& operator=(const __bit_const_reference& __x); -}; - -// find - -template <class _C> -__bit_iterator<_C, false> -__find_bool_true(__bit_iterator<_C, false> __first, typename _C::size_type __n) -{ - typedef __bit_iterator<_C, false> _It; - typedef typename _It::__storage_type __storage_type; - static const unsigned __bits_per_word = _It::__bits_per_word; - // do first partial word - if (__first.__ctz_ != 0) - { - __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); - __storage_type __dn = _STD::min(__clz_f, __n); - __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); - __storage_type __b = *__first.__seg_ & __m; - if (__b) - return _It(__first.__seg_, static_cast<unsigned>(_STD::__ctz(__b))); - __n -= __dn; - ++__first.__seg_; - } - // do middle whole words - for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) - if (*__first.__seg_) - return _It(__first.__seg_, static_cast<unsigned>(_STD::__ctz(*__first.__seg_))); - // do last partial word - if (__n > 0) - { - __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); - __storage_type __b = *__first.__seg_ & __m; - if (__b) - return _It(__first.__seg_, static_cast<unsigned>(_STD::__ctz(__b))); - } - return _It(__first.__seg_, static_cast<unsigned>(__n)); -} - -template <class _C> -__bit_iterator<_C, false> -__find_bool_false(__bit_iterator<_C, false> __first, typename _C::size_type __n) -{ - typedef __bit_iterator<_C, false> _It; - typedef typename _It::__storage_type __storage_type; - static const unsigned __bits_per_word = _It::__bits_per_word; - // do first partial word - if (__first.__ctz_ != 0) - { - __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); - __storage_type __dn = _STD::min(__clz_f, __n); - __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); - __storage_type __b = ~(*__first.__seg_ & __m); - if (__b) - return _It(__first.__seg_, static_cast<unsigned>(_STD::__ctz(__b))); - __n -= __dn; - ++__first.__seg_; - } - // do middle whole words - for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) - { - __storage_type __b = ~*__first.__seg_; - if (__b) - return _It(__first.__seg_, static_cast<unsigned>(_STD::__ctz(__b))); - } - // do last partial word - if (__n > 0) - { - __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); - __storage_type __b = ~(*__first.__seg_ & __m); - if (__b) - return _It(__first.__seg_, static_cast<unsigned>(_STD::__ctz(__b))); - } - return _It(__first.__seg_, static_cast<unsigned>(__n)); -} - -template <class _C, class _Tp> -inline _LIBCPP_INLINE_VISIBILITY -__bit_iterator<_C, false> -find(__bit_iterator<_C, false> __first, __bit_iterator<_C, false> __last, const _Tp& __value) -{ - if (static_cast<bool>(__value)) - return __find_bool_true(__first, static_cast<typename _C::size_type>(__last - __first)); - return __find_bool_false(__first, static_cast<typename _C::size_type>(__last - __first)); -} - -// count - -template <class _C> -typename __bit_iterator<_C, false>::difference_type -__count_bool_true(__bit_iterator<_C, false> __first, typename _C::size_type __n) -{ - typedef __bit_iterator<_C, false> _It; - typedef typename _It::__storage_type __storage_type; - typedef typename _It::difference_type difference_type; - static const unsigned __bits_per_word = _It::__bits_per_word; - difference_type __r = 0; - // do first partial word - if (__first.__ctz_ != 0) - { - __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); - __storage_type __dn = _STD::min(__clz_f, __n); - __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); - __r = _STD::__pop_count(*__first.__seg_ & __m); - __n -= __dn; - ++__first.__seg_; - } - // do middle whole words - for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) - __r += _STD::__pop_count(*__first.__seg_); - // do last partial word - if (__n > 0) - { - __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); - __r += _STD::__pop_count(*__first.__seg_ & __m); - } - return __r; -} - -template <class _C> -typename __bit_iterator<_C, false>::difference_type -__count_bool_false(__bit_iterator<_C, false> __first, typename _C::size_type __n) -{ - typedef __bit_iterator<_C, false> _It; - typedef typename _It::__storage_type __storage_type; - typedef typename _It::difference_type difference_type; - static const unsigned __bits_per_word = _It::__bits_per_word; - difference_type __r = 0; - // do first partial word - if (__first.__ctz_ != 0) - { - __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); - __storage_type __dn = _STD::min(__clz_f, __n); - __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); - __r = _STD::__pop_count(~(*__first.__seg_ & __m)); - __n -= __dn; - ++__first.__seg_; - } - // do middle whole words - for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) - __r += _STD::__pop_count(~*__first.__seg_); - // do last partial word - if (__n > 0) - { - __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); - __r += _STD::__pop_count(~(*__first.__seg_ & __m)); - } - return __r; -} - -template <class _C, class _Tp> -inline _LIBCPP_INLINE_VISIBILITY -typename __bit_iterator<_C, false>::difference_type -count(__bit_iterator<_C, false> __first, __bit_iterator<_C, false> __last, const _Tp& __value) -{ - if (static_cast<bool>(__value)) - return __count_bool_true(__first, static_cast<typename _C::size_type>(__last - __first)); - return __count_bool_false(__first, static_cast<typename _C::size_type>(__last - __first)); -} - -// fill_n - -template <class _C> -void -__fill_n_false(__bit_iterator<_C, false> __first, typename _C::size_type __n) -{ - typedef __bit_iterator<_C, false> _It; - typedef typename _It::__storage_type __storage_type; - static const unsigned __bits_per_word = _It::__bits_per_word; - // do first partial word - if (__first.__ctz_ != 0) - { - __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); - __storage_type __dn = _STD::min(__clz_f, __n); - __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); - *__first.__seg_ &= ~__m; - __n -= __dn; - ++__first.__seg_; - } - // do middle whole words - __storage_type __nw = __n / __bits_per_word; - _STD::memset(__first.__seg_, 0, __nw * sizeof(__storage_type)); - __n -= __nw * __bits_per_word; - // do last partial word - if (__n > 0) - { - __first.__seg_ += __nw; - __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); - *__first.__seg_ &= ~__m; - } -} - -template <class _C> -void -__fill_n_true(__bit_iterator<_C, false> __first, typename _C::size_type __n) -{ - typedef __bit_iterator<_C, false> _It; - typedef typename _It::__storage_type __storage_type; - static const unsigned __bits_per_word = _It::__bits_per_word; - // do first partial word - if (__first.__ctz_ != 0) - { - __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); - __storage_type __dn = _STD::min(__clz_f, __n); - __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); - *__first.__seg_ |= __m; - __n -= __dn; - ++__first.__seg_; - } - // do middle whole words - __storage_type __nw = __n / __bits_per_word; - _STD::memset(__first.__seg_, -1, __nw * sizeof(__storage_type)); - __n -= __nw * __bits_per_word; - // do last partial word - if (__n > 0) - { - __first.__seg_ += __nw; - __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); - *__first.__seg_ |= __m; - } -} - -template <class _C> -_LIBCPP_INLINE_VISIBILITY inline -void -fill_n(__bit_iterator<_C, false> __first, typename _C::size_type __n, bool __value) -{ - if (__n > 0) - { - if (__value) - __fill_n_true(__first, __n); - else - __fill_n_false(__first, __n); - } -} - -// fill - -template <class _C> -inline _LIBCPP_INLINE_VISIBILITY -void -fill(__bit_iterator<_C, false> __first, __bit_iterator<_C, false> __last, bool __value) -{ - _STD::fill_n(__first, static_cast<typename _C::size_type>(__last - __first), __value); -} - -// copy - -template <class _C, bool _IsConst> -__bit_iterator<_C, false> -__copy_aligned(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, - __bit_iterator<_C, false> __result) -{ - typedef __bit_iterator<_C, _IsConst> _In; - typedef typename _In::difference_type difference_type; - typedef typename _In::__storage_type __storage_type; - static const unsigned __bits_per_word = _In::__bits_per_word; - difference_type __n = __last - __first; - if (__n > 0) - { - // do first word - if (__first.__ctz_ != 0) - { - unsigned __clz = __bits_per_word - __first.__ctz_; - difference_type __dn = _STD::min(static_cast<difference_type>(__clz), __n); - __n -= __dn; - __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); - __storage_type __b = *__first.__seg_ & __m; - *__result.__seg_ &= ~__m; - *__result.__seg_ |= __b; - __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; - __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); - ++__first.__seg_; - // __first.__ctz_ = 0; - } - // __first.__ctz_ == 0; - // do middle words - __storage_type __nw = __n / __bits_per_word; - _STD::memmove(__result.__seg_, __first.__seg_, __nw * sizeof(__storage_type)); - __n -= __nw * __bits_per_word; - __result.__seg_ += __nw; - // do last word - if (__n > 0) - { - __first.__seg_ += __nw; - __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); - __storage_type __b = *__first.__seg_ & __m; - *__result.__seg_ &= ~__m; - *__result.__seg_ |= __b; - __result.__ctz_ = static_cast<unsigned>(__n); - } - } - return __result; -} - -template <class _C, bool _IsConst> -__bit_iterator<_C, false> -__copy_unaligned(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, - __bit_iterator<_C, false> __result) -{ - typedef __bit_iterator<_C, _IsConst> _In; - typedef typename _In::difference_type difference_type; - typedef typename _In::__storage_type __storage_type; - static const unsigned __bits_per_word = _In::__bits_per_word; - difference_type __n = __last - __first; - if (__n > 0) - { - // do first word - if (__first.__ctz_ != 0) - { - unsigned __clz_f = __bits_per_word - __first.__ctz_; - difference_type __dn = _STD::min(static_cast<difference_type>(__clz_f), __n); - __n -= __dn; - __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); - __storage_type __b = *__first.__seg_ & __m; - unsigned __clz_r = __bits_per_word - __result.__ctz_; - __storage_type __ddn = _STD::min<__storage_type>(__dn, __clz_r); - __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); - *__result.__seg_ &= ~__m; - if (__result.__ctz_ > __first.__ctz_) - *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_); - else - *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_); - __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; - __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); - __dn -= __ddn; - if (__dn > 0) - { - __m = ~__storage_type(0) >> (__bits_per_word - __dn); - *__result.__seg_ &= ~__m; - *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn); - __result.__ctz_ = static_cast<unsigned>(__dn); - } - ++__first.__seg_; - // __first.__ctz_ = 0; - } - // __first.__ctz_ == 0; - // do middle words - unsigned __clz_r = __bits_per_word - __result.__ctz_; - __storage_type __m = ~__storage_type(0) << __result.__ctz_; - for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) - { - __storage_type __b = *__first.__seg_; - *__result.__seg_ &= ~__m; - *__result.__seg_ |= __b << __result.__ctz_; - ++__result.__seg_; - *__result.__seg_ &= __m; - *__result.__seg_ |= __b >> __clz_r; - } - // do last word - if (__n > 0) - { - __m = ~__storage_type(0) >> (__bits_per_word - __n); - __storage_type __b = *__first.__seg_ & __m; - __storage_type __dn = _STD::min(__n, static_cast<difference_type>(__clz_r)); - __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); - *__result.__seg_ &= ~__m; - *__result.__seg_ |= __b << __result.__ctz_; - __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; - __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); - __n -= __dn; - if (__n > 0) - { - __m = ~__storage_type(0) >> (__bits_per_word - __n); - *__result.__seg_ &= ~__m; - *__result.__seg_ |= __b >> __dn; - __result.__ctz_ = static_cast<unsigned>(__n); - } - } - } - return __result; -} - -template <class _C, bool _IsConst> -inline _LIBCPP_INLINE_VISIBILITY -__bit_iterator<_C, false> -copy(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, __bit_iterator<_C, false> __result) -{ - if (__first.__ctz_ == __result.__ctz_) - return __copy_aligned(__first, __last, __result); - return __copy_unaligned(__first, __last, __result); -} - -// copy_backward - -template <class _C, bool _IsConst> -__bit_iterator<_C, false> -__copy_backward_aligned(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, - __bit_iterator<_C, false> __result) -{ - typedef __bit_iterator<_C, _IsConst> _In; - typedef typename _In::difference_type difference_type; - typedef typename _In::__storage_type __storage_type; - static const unsigned __bits_per_word = _In::__bits_per_word; - difference_type __n = __last - __first; - if (__n > 0) - { - // do first word - if (__last.__ctz_ != 0) - { - difference_type __dn = _STD::min(static_cast<difference_type>(__last.__ctz_), __n); - __n -= __dn; - unsigned __clz = __bits_per_word - __last.__ctz_; - __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz); - __storage_type __b = *__last.__seg_ & __m; - *__result.__seg_ &= ~__m; - *__result.__seg_ |= __b; - __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + - __result.__ctz_) % __bits_per_word); - // __last.__ctz_ = 0 - } - // __last.__ctz_ == 0 || __n == 0 - // __result.__ctz_ == 0 || __n == 0 - // do middle words - __storage_type __nw = __n / __bits_per_word; - __result.__seg_ -= __nw; - __last.__seg_ -= __nw; - _STD::memmove(__result.__seg_, __last.__seg_, __nw * sizeof(__storage_type)); - __n -= __nw * __bits_per_word; - // do last word - if (__n > 0) - { - __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n); - __storage_type __b = *--__last.__seg_ & __m; - *--__result.__seg_ &= ~__m; - *__result.__seg_ |= __b; - __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); - } - } - return __result; -} - -template <class _C, bool _IsConst> -__bit_iterator<_C, false> -__copy_backward_unaligned(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, - __bit_iterator<_C, false> __result) -{ - typedef __bit_iterator<_C, _IsConst> _In; - typedef typename _In::difference_type difference_type; - typedef typename _In::__storage_type __storage_type; - static const unsigned __bits_per_word = _In::__bits_per_word; - difference_type __n = __last - __first; - if (__n > 0) - { - // do first word - if (__last.__ctz_ != 0) - { - difference_type __dn = _STD::min(static_cast<difference_type>(__last.__ctz_), __n); - __n -= __dn; - unsigned __clz_l = __bits_per_word - __last.__ctz_; - __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l); - __storage_type __b = *__last.__seg_ & __m; - unsigned __clz_r = __bits_per_word - __result.__ctz_; - __storage_type __ddn = _STD::min(__dn, static_cast<difference_type>(__result.__ctz_)); - if (__ddn > 0) - { - __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r); - *__result.__seg_ &= ~__m; - if (__result.__ctz_ > __last.__ctz_) - *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); - else - *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_); - __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) + - __result.__ctz_) % __bits_per_word); - __dn -= __ddn; - } - if (__dn > 0) - { - // __result.__ctz_ == 0 - --__result.__seg_; - __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1)); - __m = ~__storage_type(0) << __result.__ctz_; - *__result.__seg_ &= ~__m; - __last.__ctz_ -= __dn + __ddn; - *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); - } - // __last.__ctz_ = 0 - } - // __last.__ctz_ == 0 || __n == 0 - // __result.__ctz_ != 0 || __n == 0 - // do middle words - unsigned __clz_r = __bits_per_word - __result.__ctz_; - __storage_type __m = ~__storage_type(0) >> __clz_r; - for (; __n >= __bits_per_word; __n -= __bits_per_word) - { - __storage_type __b = *--__last.__seg_; - *__result.__seg_ &= ~__m; - *__result.__seg_ |= __b >> __clz_r; - *--__result.__seg_ &= __m; - *__result.__seg_ |= __b << __result.__ctz_; - } - // do last word - if (__n > 0) - { - __m = ~__storage_type(0) << (__bits_per_word - __n); - __storage_type __b = *--__last.__seg_ & __m; - unsigned __clz_r = __bits_per_word - __result.__ctz_; - __storage_type __dn = _STD::min(__n, static_cast<difference_type>(__result.__ctz_)); - __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r); - *__result.__seg_ &= ~__m; - *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_); - __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + - __result.__ctz_) % __bits_per_word); - __n -= __dn; - if (__n > 0) - { - // __result.__ctz_ == 0 - --__result.__seg_; - __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); - __m = ~__storage_type(0) << __result.__ctz_; - *__result.__seg_ &= ~__m; - *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn)); - } - } - } - return __result; -} - -template <class _C, bool _IsConst> -inline _LIBCPP_INLINE_VISIBILITY -__bit_iterator<_C, false> -copy_backward(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, __bit_iterator<_C, false> __result) -{ - if (__last.__ctz_ == __result.__ctz_) - return __copy_backward_aligned(__first, __last, __result); - return __copy_backward_unaligned(__first, __last, __result); -} - -// move - -template <class _C, bool _IsConst> -inline _LIBCPP_INLINE_VISIBILITY -__bit_iterator<_C, false> -move(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, __bit_iterator<_C, false> __result) -{ - return _STD::copy(__first, __last, __result); -} - -// move_backward - -template <class _C, bool _IsConst> -inline _LIBCPP_INLINE_VISIBILITY -__bit_iterator<_C, false> -move_backward(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, __bit_iterator<_C, false> __result) -{ - return _STD::copy(__first, __last, __result); -} - -// swap_ranges - -template <class _C1, class _C2> -__bit_iterator<_C2, false> -__swap_ranges_aligned(__bit_iterator<_C1, false> __first, __bit_iterator<_C1, false> __last, - __bit_iterator<_C2, false> __result) -{ - typedef __bit_iterator<_C1, false> _I1; - typedef typename _I1::difference_type difference_type; - typedef typename _I1::__storage_type __storage_type; - static const unsigned __bits_per_word = _I1::__bits_per_word; - difference_type __n = __last - __first; - if (__n > 0) - { - // do first word - if (__first.__ctz_ != 0) - { - unsigned __clz = __bits_per_word - __first.__ctz_; - difference_type __dn = _STD::min(static_cast<difference_type>(__clz), __n); - __n -= __dn; - __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); - __storage_type __b1 = *__first.__seg_ & __m; - *__first.__seg_ &= ~__m; - __storage_type __b2 = *__result.__seg_ & __m; - *__result.__seg_ &= ~__m; - *__result.__seg_ |= __b1; - *__first.__seg_ |= __b2; - __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; - __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); - ++__first.__seg_; - // __first.__ctz_ = 0; - } - // __first.__ctz_ == 0; - // do middle words - for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_) - swap(*__first.__seg_, *__result.__seg_); - // do last word - if (__n > 0) - { - __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); - __storage_type __b1 = *__first.__seg_ & __m; - *__first.__seg_ &= ~__m; - __storage_type __b2 = *__result.__seg_ & __m; - *__result.__seg_ &= ~__m; - *__result.__seg_ |= __b1; - *__first.__seg_ |= __b2; - __result.__ctz_ = static_cast<unsigned>(__n); - } - } - return __result; -} - -template <class _C1, class _C2> -__bit_iterator<_C2, false> -__swap_ranges_unaligned(__bit_iterator<_C1, false> __first, __bit_iterator<_C1, false> __last, - __bit_iterator<_C2, false> __result) -{ - typedef __bit_iterator<_C1, false> _I1; - typedef typename _I1::difference_type difference_type; - typedef typename _I1::__storage_type __storage_type; - static const unsigned __bits_per_word = _I1::__bits_per_word; - difference_type __n = __last - __first; - if (__n > 0) - { - // do first word - if (__first.__ctz_ != 0) - { - unsigned __clz_f = __bits_per_word - __first.__ctz_; - difference_type __dn = _STD::min(static_cast<difference_type>(__clz_f), __n); - __n -= __dn; - __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); - __storage_type __b1 = *__first.__seg_ & __m; - *__first.__seg_ &= ~__m; - unsigned __clz_r = __bits_per_word - __result.__ctz_; - __storage_type __ddn = _STD::min<__storage_type>(__dn, __clz_r); - __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); - __storage_type __b2 = *__result.__seg_ & __m; - *__result.__seg_ &= ~__m; - if (__result.__ctz_ > __first.__ctz_) - { - unsigned __s = __result.__ctz_ - __first.__ctz_; - *__result.__seg_ |= __b1 << __s; - *__first.__seg_ |= __b2 >> __s; - } - else - { - unsigned __s = __first.__ctz_ - __result.__ctz_; - *__result.__seg_ |= __b1 >> __s; - *__first.__seg_ |= __b2 << __s; - } - __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; - __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); - __dn -= __ddn; - if (__dn > 0) - { - __m = ~__storage_type(0) >> (__bits_per_word - __dn); - __b2 = *__result.__seg_ & __m; - *__result.__seg_ &= ~__m; - unsigned __s = __first.__ctz_ + __ddn; - *__result.__seg_ |= __b1 >> __s; - *__first.__seg_ |= __b2 << __s; - __result.__ctz_ = static_cast<unsigned>(__dn); - } - ++__first.__seg_; - // __first.__ctz_ = 0; - } - // __first.__ctz_ == 0; - // do middle words - __storage_type __m = ~__storage_type(0) << __result.__ctz_; - unsigned __clz_r = __bits_per_word - __result.__ctz_; - for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) - { - __storage_type __b1 = *__first.__seg_; - __storage_type __b2 = *__result.__seg_ & __m; - *__result.__seg_ &= ~__m; - *__result.__seg_ |= __b1 << __result.__ctz_; - *__first.__seg_ = __b2 >> __result.__ctz_; - ++__result.__seg_; - __b2 = *__result.__seg_ & ~__m; - *__result.__seg_ &= __m; - *__result.__seg_ |= __b1 >> __clz_r; - *__first.__seg_ |= __b2 << __clz_r; - } - // do last word - if (__n > 0) - { - __m = ~__storage_type(0) >> (__bits_per_word - __n); - __storage_type __b1 = *__first.__seg_ & __m; - *__first.__seg_ &= ~__m; - __storage_type __dn = _STD::min<__storage_type>(__n, __clz_r); - __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); - __storage_type __b2 = *__result.__seg_ & __m; - *__result.__seg_ &= ~__m; - *__result.__seg_ |= __b1 << __result.__ctz_; - *__first.__seg_ |= __b2 >> __result.__ctz_; - __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; - __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); - __n -= __dn; - if (__n > 0) - { - __m = ~__storage_type(0) >> (__bits_per_word - __n); - __b2 = *__result.__seg_ & __m; - *__result.__seg_ &= ~__m; - *__result.__seg_ |= __b1 >> __dn; - *__first.__seg_ |= __b2 << __dn; - __result.__ctz_ = static_cast<unsigned>(__n); - } - } - } - return __result; -} - -template <class _C1, class _C2> -inline _LIBCPP_INLINE_VISIBILITY -__bit_iterator<_C2, false> -swap_ranges(__bit_iterator<_C1, false> __first1, __bit_iterator<_C1, false> __last1, - __bit_iterator<_C2, false> __first2) -{ - if (__first1.__ctz_ == __first2.__ctz_) - return __swap_ranges_aligned(__first1, __last1, __first2); - return __swap_ranges_unaligned(__first1, __last1, __first2); -} - -// rotate - -template <class _C> -struct __bit_array -{ - typedef typename _C::difference_type difference_type; - typedef typename _C::__storage_type __storage_type; - typedef typename _C::iterator iterator; - static const unsigned __bits_per_word = _C::__bits_per_word; - static const unsigned _N = 4; - - difference_type __size_; - __storage_type __word_[_N]; - - _LIBCPP_INLINE_VISIBILITY static difference_type capacity() - {return static_cast<difference_type>(_N * __bits_per_word);} - _LIBCPP_INLINE_VISIBILITY explicit __bit_array(difference_type __s) : __size_(__s) {} - _LIBCPP_INLINE_VISIBILITY iterator begin() {return iterator(__word_, 0);} - _LIBCPP_INLINE_VISIBILITY iterator end() {return iterator(__word_ + __size_ / __bits_per_word, - static_cast<unsigned>(__size_ % __bits_per_word));} -}; - -template <class _C> -__bit_iterator<_C, false> -rotate(__bit_iterator<_C, false> __first, __bit_iterator<_C, false> __middle, __bit_iterator<_C, false> __last) -{ - typedef __bit_iterator<_C, false> _I1; - typedef typename _I1::difference_type difference_type; - typedef typename _I1::__storage_type __storage_type; - static const unsigned __bits_per_word = _I1::__bits_per_word; - difference_type __d1 = __middle - __first; - difference_type __d2 = __last - __middle; - _I1 __r = __first + __d2; - while (__d1 != 0 && __d2 != 0) - { - if (__d1 <= __d2) - { - if (__d1 <= __bit_array<_C>::capacity()) - { - __bit_array<_C> __b(__d1); - _STD::copy(__first, __middle, __b.begin()); - _STD::copy(__b.begin(), __b.end(), _STD::copy(__middle, __last, __first)); - break; - } - else - { - __bit_iterator<_C, false> __mp = _STD::swap_ranges(__first, __middle, __middle); - __first = __middle; - __middle = __mp; - __d2 -= __d1; - } - } - else - { - if (__d2 <= __bit_array<_C>::capacity()) - { - __bit_array<_C> __b(__d2); - _STD::copy(__middle, __last, __b.begin()); - _STD::copy_backward(__b.begin(), __b.end(), _STD::copy_backward(__first, __middle, __last)); - break; - } - else - { - __bit_iterator<_C, false> __mp = __first + __d2; - _STD::swap_ranges(__first, __mp, __middle); - __first = __mp; - __d1 -= __d2; - } - } - } - return __r; -} - -// equal - -template <class _C> -bool -__equal_unaligned(__bit_iterator<_C, true> __first1, __bit_iterator<_C, true> __last1, - __bit_iterator<_C, true> __first2) -{ - typedef __bit_iterator<_C, true> _It; - typedef typename _It::difference_type difference_type; - typedef typename _It::__storage_type __storage_type; - static const unsigned __bits_per_word = _It::__bits_per_word; - difference_type __n = __last1 - __first1; - if (__n > 0) - { - // do first word - if (__first1.__ctz_ != 0) - { - unsigned __clz_f = __bits_per_word - __first1.__ctz_; - difference_type __dn = _STD::min(static_cast<difference_type>(__clz_f), __n); - __n -= __dn; - __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); - __storage_ty |