diff options
Diffstat (limited to 'contrib/libc++/include/algorithm')
| -rw-r--r-- | contrib/libc++/include/algorithm | 141 |
1 files changed, 88 insertions, 53 deletions
diff --git a/contrib/libc++/include/algorithm b/contrib/libc++/include/algorithm index a89b9dd..f9c6843 100644 --- a/contrib/libc++/include/algorithm +++ b/contrib/libc++/include/algorithm @@ -595,6 +595,8 @@ template <class BidirectionalIterator, class Compare> #include <iterator> #include <cstdlib> +#include <__undef_min_max> + #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif @@ -695,14 +697,48 @@ struct __debug_less #endif // _LIBCPP_DEBUG2 // Precondition: __x != 0 -inline _LIBCPP_INLINE_VISIBILITY unsigned __ctz(unsigned __x) {return __builtin_ctz (__x);} -inline _LIBCPP_INLINE_VISIBILITY unsigned long __ctz(unsigned long __x) {return __builtin_ctzl (__x);} -inline _LIBCPP_INLINE_VISIBILITY unsigned long long __ctz(unsigned long long __x) {return __builtin_ctzll(__x);} +inline _LIBCPP_INLINE_VISIBILITY +unsigned +__ctz(unsigned __x) +{ + return static_cast<unsigned>(__builtin_ctz(__x)); +} + +inline _LIBCPP_INLINE_VISIBILITY +unsigned long +__ctz(unsigned long __x) +{ + return static_cast<unsigned long>(__builtin_ctzl(__x)); +} + +inline _LIBCPP_INLINE_VISIBILITY +unsigned long long +__ctz(unsigned long long __x) +{ + return static_cast<unsigned long long>(__builtin_ctzll(__x)); +} // Precondition: __x != 0 -inline _LIBCPP_INLINE_VISIBILITY unsigned __clz(unsigned __x) {return __builtin_clz (__x);} -inline _LIBCPP_INLINE_VISIBILITY unsigned long __clz(unsigned long __x) {return __builtin_clzl (__x);} -inline _LIBCPP_INLINE_VISIBILITY unsigned long long __clz(unsigned long long __x) {return __builtin_clzll(__x);} +inline _LIBCPP_INLINE_VISIBILITY +unsigned +__clz(unsigned __x) +{ + return static_cast<unsigned>(__builtin_clz(__x)); +} + +inline _LIBCPP_INLINE_VISIBILITY +unsigned long +__clz(unsigned long __x) +{ + return static_cast<unsigned long>(__builtin_clzl (__x)); +} + +inline _LIBCPP_INLINE_VISIBILITY +unsigned long long +__clz(unsigned long long __x) +{ + return static_cast<unsigned long long>(__builtin_clzll(__x)); +} inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned __x) {return __builtin_popcount (__x);} inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long __x) {return __builtin_popcountl (__x);} @@ -2328,10 +2364,7 @@ minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __com if (++__first != __last) { if (__comp(*__first, *__result.first)) - { - __result.second = __result.first; __result.first = __first; - } else __result.second = __first; while (++__first != __last) @@ -2423,29 +2456,29 @@ minmax(initializer_list<_Tp> __t, _Compare __comp) // __independent_bits_engine -template <unsigned long long _X, size_t _R> +template <unsigned long long _Xp, size_t _Rp> struct __log2_imp { - static const size_t value = _X & ((unsigned long long)(1) << _R) ? _R - : __log2_imp<_X, _R - 1>::value; + static const size_t value = _Xp & ((unsigned long long)(1) << _Rp) ? _Rp + : __log2_imp<_Xp, _Rp - 1>::value; }; -template <unsigned long long _X> -struct __log2_imp<_X, 0> +template <unsigned long long _Xp> +struct __log2_imp<_Xp, 0> { static const size_t value = 0; }; -template <size_t _R> -struct __log2_imp<0, _R> +template <size_t _Rp> +struct __log2_imp<0, _Rp> { - static const size_t value = _R + 1; + static const size_t value = _Rp + 1; }; -template <class _UI, _UI _X> +template <class _UI, _UI _Xp> struct __log2 { - static const size_t value = __log2_imp<_X, + static const size_t value = __log2_imp<_Xp, sizeof(_UI) * __CHAR_BIT__ - 1>::value; }; @@ -2475,9 +2508,9 @@ private: _Engine_result_type __mask0_; _Engine_result_type __mask1_; - static const _Working_result_type _R = _Engine::_Max - _Engine::_Min + static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min + _Working_result_type(1); - static const size_t __m = __log2<_Working_result_type, _R>::value; + static const size_t __m = __log2<_Working_result_type, _Rp>::value; static const size_t _WDt = numeric_limits<_Working_result_type>::digits; static const size_t _EDt = numeric_limits<_Engine_result_type>::digits; @@ -2486,7 +2519,7 @@ public: __independent_bits_engine(_Engine& __e, size_t __w); // generating functions - result_type operator()() {return __eval(integral_constant<bool, _R != 0>());} + result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());} private: result_type __eval(false_type); @@ -2501,24 +2534,24 @@ __independent_bits_engine<_Engine, _UIntType> { __n_ = __w_ / __m + (__w_ % __m != 0); __w0_ = __w_ / __n_; - if (_R == 0) - __y0_ = _R; + if (_Rp == 0) + __y0_ = _Rp; else if (__w0_ < _WDt) - __y0_ = (_R >> __w0_) << __w0_; + __y0_ = (_Rp >> __w0_) << __w0_; else __y0_ = 0; - if (_R - __y0_ > __y0_ / __n_) + if (_Rp - __y0_ > __y0_ / __n_) { ++__n_; __w0_ = __w_ / __n_; if (__w0_ < _WDt) - __y0_ = (_R >> __w0_) << __w0_; + __y0_ = (_Rp >> __w0_) << __w0_; else __y0_ = 0; } __n0_ = __n_ - __w_ % __n_; if (__w0_ < _WDt - 1) - __y1_ = (_R >> (__w0_ + 1)) << (__w0_ + 1); + __y1_ = (_Rp >> (__w0_ + 1)) << (__w0_ + 1); else __y1_ = 0; __mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) : @@ -2540,7 +2573,7 @@ template<class _Engine, class _UIntType> _UIntType __independent_bits_engine<_Engine, _UIntType>::__eval(true_type) { - result_type _S = 0; + result_type _Sp = 0; for (size_t __k = 0; __k < __n0_; ++__k) { _Engine_result_type __u; @@ -2549,10 +2582,10 @@ __independent_bits_engine<_Engine, _UIntType>::__eval(true_type) __u = __e_() - _Engine::min(); } while (__u >= __y0_); if (__w0_ < _WDt) - _S <<= __w0_; + _Sp <<= __w0_; else - _S = 0; - _S += __u & __mask0_; + _Sp = 0; + _Sp += __u & __mask0_; } for (size_t __k = __n0_; __k < __n_; ++__k) { @@ -2562,12 +2595,12 @@ __independent_bits_engine<_Engine, _UIntType>::__eval(true_type) __u = __e_() - _Engine::min(); } while (__u >= __y1_); if (__w0_ < _WDt - 1) - _S <<= __w0_ + 1; + _Sp <<= __w0_ + 1; else - _S = 0; - _S += __u & __mask1_; + _Sp = 0; + _Sp += __u & __mask1_; } - return _S; + return _Sp; } // uniform_int_distribution @@ -2640,22 +2673,22 @@ uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p { typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t), uint32_t, uint64_t>::type _UIntType; - const _UIntType _R = __p.b() - __p.a() + _UIntType(1); - if (_R == 1) + const _UIntType _Rp = __p.b() - __p.a() + _UIntType(1); + if (_Rp == 1) return __p.a(); const size_t _Dt = numeric_limits<_UIntType>::digits; typedef __independent_bits_engine<_URNG, _UIntType> _Eng; - if (_R == 0) + if (_Rp == 0) return static_cast<result_type>(_Eng(__g, _Dt)()); - size_t __w = _Dt - __clz(_R) - 1; - if ((_R & (_UIntType(~0) >> (_Dt - __w))) != 0) + size_t __w = _Dt - __clz(_Rp) - 1; + if ((_Rp & (_UIntType(~0) >> (_Dt - __w))) != 0) ++__w; _Eng __e(__g, __w); _UIntType __u; do { __u = __e(); - } while (__u >= _R); + } while (__u >= _Rp); return static_cast<result_type>(__u + __p.a()); } @@ -2679,8 +2712,8 @@ public: result_type operator()(); - static const/*expr*/ result_type min() {return _Min;} - static const/*expr*/ result_type max() {return _Max;} + static constexpr result_type min() {return _Min;} + static constexpr result_type max() {return _Max;} friend __rs_default __rs_get(); }; @@ -2692,16 +2725,16 @@ void random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) { typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; - typedef uniform_int_distribution<ptrdiff_t> _D; - typedef typename _D::param_type _P; + typedef uniform_int_distribution<ptrdiff_t> _Dp; + typedef typename _Dp::param_type _Pp; difference_type __d = __last - __first; if (__d > 1) { - _D __uid; + _Dp __uid; __rs_default __g = __rs_get(); for (--__last, --__d; __first < __last; ++__first, --__d) { - difference_type __i = __uid(__g, _P(0, __d)); + difference_type __i = __uid(__g, _Pp(0, __d)); if (__i != difference_type(0)) swap(*__first, *(__first + __i)); } @@ -2738,15 +2771,15 @@ template<class _RandomAccessIterator, class _UniformRandomNumberGenerator> #endif { typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; - typedef uniform_int_distribution<ptrdiff_t> _D; - typedef typename _D::param_type _P; + typedef uniform_int_distribution<ptrdiff_t> _Dp; + typedef typename _Dp::param_type _Pp; difference_type __d = __last - __first; if (__d > 1) { - _D __uid; + _Dp __uid; for (--__last, --__d; __first < __last; ++__first, --__d) { - difference_type __i = __uid(__g, _P(0, __d)); + difference_type __i = __uid(__g, _Pp(0, __d)); if (__i != difference_type(0)) swap(*__first, *(__first + __i)); } @@ -3722,7 +3755,7 @@ extern template bool __insertion_sort_incomplete<__less<long double>&, long doub extern template unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&); #ifdef _MSC_VER #pragma warning( pop ) -#endif _MSC_VER +#endif // _MSC_VER // lower_bound @@ -4718,6 +4751,8 @@ __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _Rando while (true) { __restart: + if (__nth == __last) + return; difference_type __len = __last - __first; switch (__len) { |
