From 3678f64ad386927abc67f2fa9c29e9d841865db8 Mon Sep 17 00:00:00 2001 From: dim Date: Fri, 13 Feb 2015 22:05:54 +0000 Subject: Synchronize the default C++ stack in stable/10 with head, by merging almost all recent changes to libc++ and libcxxrt. MFC r256642: Since C++ typeinfo objects are currently not guaranteed to be merged at runtime by the dynamic linker, check for their equality in libcxxrt by not only comparing the typeinfo's name pointers, but also comparing the full names, if necessary. (This is similar to what GNU libstdc++ does in its default configuration.) The 'deep' check can be turned off again by defining LIBCXXRT_MERGED_TYPEINFO, and recompiling libcxxrt. Reviewed by: theraven MFC r270522 (by rdivacky): The standard we compile libc++ with is called c++11 not c++0x. MFC r273066 (by bapt): Import patch from libc++ r197313 which allows using libc++ headers with gcc Differential Revision: https://reviews.freebsd.org/D942 Reviewed by: imp MFC r273381 (by bapt): Add support for __cxa_throw_bad_array_new_length in libcxxrt It is required for use with newer g++49 Differential Revision: https://reviews.freebsd.org/D982 Reviewed by: theraven Approved by: theraven MFC r273382 (by bapt): Fix build by marking the new functions as weak This is a temporary fix MFC r273407 (by bapt): When using an external gcc 4.8+ and not building libstdc++ then create in the objectdir a fake libstdc++.so and libstdc++.a which is a symlink on libc++ that allow g++ to satisfy its links dependencies in the least hackish way. Please note that this hacky libstds++ never get installed on the final system Reviewed by: imp MFC r273434 (by bapt): Do not define bad_array_new_length::bad_array_new_length in libc++ anymore when used in combinaison with libcxxrt since it is now defined there already. This fixes building world MFC r276417: Import libcxxrt master 00bc29eb6513624824a6d7db2ebc768a4216a604. Interesting fixes: 76584a0 Reorganize code to use only 32bit atomic ops for 32bit platforms 30d2ae5 Implement __cxa_throw_bad_array_new_length Reviewed by: bapt Differential Revision: https://reviews.freebsd.org/D1390 MFC r277217: Import libc++ trunk r224926. This fixes a number of bugs, completes C++14 support[1], adds more C++1z features[2], and fixes the following LWG issues[3]: 1450: Contradiction in regex_constants 2003: String exception inconsistency in erase. 2075: Progress guarantees, lock-free property, and scheduling assumptions 2104: unique_lock move-assignment should not be noexcept 2112: User-defined classes that cannot be derived from 2132: std::function ambiguity 2135: Unclear requirement for exceptions thrown in condition_variable::wait() 2142: packaged_task::operator() synchronization too broad? 2182: Container::[const_]reference types are misleadingly specified 2186: Incomplete action on async/launch::deferred 2188: Reverse iterator does not fully support targets that overload operator& 2193: Default constructors for standard library containers are explicit 2205: Problematic postconditions of regex_match and regex_search 2213: Return value of std::regex_replace 2240: Probable misuse of term "function scope" in [thread.condition] 2252: Strong guarantee on vector::push_back() still broken with C++11? 2257: Simplify container requirements with the new algorithms 2258: a.erase(q1, q2) unable to directly return q2 2263: Comparing iterators and allocator pointers with different const-character 2268: Setting a default argument in the declaration of a member function assign of std::basic_string 2271: regex_traits::lookup_classname specification unclear 2272: quoted should use char_traits::eq for character comparison 2278: User-defined literals for Standard Library types 2280: begin / end for arrays should be constexpr and noexcept 2285: make_reverse_iterator 2288: Inconsistent requirements for shared mutexes 2291: std::hash is vulnerable to collision DoS attack 2293: Wrong facet used by num_put::do_put 2299: Effects of inaccessible key_compare::is_transparent type are not clear 2301: Why is std::tie not constexpr? 2304: Complexity of count in unordered associative containers 2306: match_results::reference should be value_type&, not const value_type& 2308: Clarify container destructor requirements w.r.t. std::array 2313: tuple_size should always derive from integral_constant 2314: apply() should return decltype(auto) and use decay_t before tuple_size 2315: weak_ptr should be movable 2316: weak_ptr::lock() should be atomic 2317: The type property queries should be UnaryTypeTraits returning size_t 2320: select_on_container_copy_construction() takes allocators, not containers 2322: Associative(initializer_list, stuff) constructors are underspecified 2323: vector::resize(n, t)'s specification should be simplified 2324: Insert iterator constructors should use addressof() 2329: regex_match()/regex_search() with match_results should forbid temporary strings 2330: regex("meow", regex::icase) is technically forbidden but should be permitted 2332: regex_iterator/regex_token_iterator should forbid temporary regexes 2339: Wording issue in nth_element 2341: Inconsistency between basic_ostream::seekp(pos) and basic_ostream::seekp(off, dir) 2344: quoted()'s interaction with padding is unclear 2346: integral_constant's member functions should be marked noexcept 2350: min, max, and minmax should be constexpr 2356: Stability of erasure in unordered associative containers 2357: Remaining "Assignable" requirement 2359: How does regex_constants::nosubs affect basic_regex::mark_count()? 2360: reverse_iterator::operator*() is unimplementable [1] http://libcxx.llvm.org/cxx1y_status.html [2] http://libcxx.llvm.org/cxx1z_status.html [3] http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html Exp-run: antoine MFC r277944: Partially revert r273382, to reduce diffs against upstream. This was a temporary fix to solve a conflict with an older version of libc++, and it is no longer relevant. MFC r278010: Revert r256642, not only to reduce diffs against upstream libcxxrt, but also because it is the wrong approach: comparing typeinfo names deeply causes trouble if two loaded DSOs use independent types of the same name. In addition, this particular change was never merged to FreeBSD 10.x and 9.x, so let's get rid of it before it ends up in an 11.x release. Discussed with: theraven, joerg@netbsd MFC r278016: Import libcxxrt master 1cb607e89f6135bbc10f3d3b6fba1f983e258dcc. Interesting fixes: 1cb607e Correct gcc version check for __cxa_begin_catch() declaration with or without throw() --- contrib/libc++/include/algorithm | 354 ++++++++++++++++++++++++--------------- 1 file changed, 220 insertions(+), 134 deletions(-) (limited to 'contrib/libc++/include/algorithm') diff --git a/contrib/libc++/include/algorithm b/contrib/libc++/include/algorithm index 367489f..02cbc81 100644 --- a/contrib/libc++/include/algorithm +++ b/contrib/libc++/include/algorithm @@ -281,11 +281,12 @@ template template void - random_shuffle(RandomAccessIterator first, RandomAccessIterator last); + random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14 template void - random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand); + random_shuffle(RandomAccessIterator first, RandomAccessIterator last, + RandomNumberGenerator& rand); // deprecated in C++14 template void shuffle(RandomAccessIterator first, RandomAccessIterator last, @@ -528,19 +529,19 @@ template template const T& - min(const T& a, const T& b); + min(const T& a, const T& b); // constexpr in C++14 template const T& - min(const T& a, const T& b, Compare comp); + min(const T& a, const T& b, Compare comp); // constexpr in C++14 template T - min(initializer_list t); + min(initializer_list t); // constexpr in C++14 template T - min(initializer_list t, Compare comp); + min(initializer_list t, Compare comp); // constexpr in C++14 template ForwardIterator @@ -552,19 +553,19 @@ template template const T& - max(const T& a, const T& b); + max(const T& a, const T& b); // constexpr in C++14 template const T& - max(const T& a, const T& b, Compare comp); + max(const T& a, const T& b, Compare comp); // constexpr in C++14 template T - max(initializer_list t); + max(initializer_list t); // constexpr in C++14 template T - max(initializer_list t, Compare comp); + max(initializer_list t, Compare comp); // constexpr in C++14 template pair @@ -576,19 +577,19 @@ template template pair - minmax(const T& a, const T& b); + minmax(const T& a, const T& b); // constexpr in C++14 template pair - minmax(const T& a, const T& b, Compare comp); + minmax(const T& a, const T& b, Compare comp); // constexpr in C++14 template pair - minmax(initializer_list t); + minmax(initializer_list t); // constexpr in C++14 template pair - minmax(initializer_list t, Compare comp); + minmax(initializer_list t, Compare comp); // constexpr in C++14 template bool @@ -637,12 +638,17 @@ template #include <__undef_min_max> +#include <__debug> + #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD +// I'd like to replace these with _VSTD::equal_to, but can't because: +// * That only works with C++14 and later, and +// * We haven't included here. template struct __equal_to { @@ -655,46 +661,59 @@ struct __equal_to template struct __equal_to<_T1, _T1> { - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} }; template struct __equal_to { - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} }; template struct __equal_to<_T1, const _T1> { - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} }; template struct __less { - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;} - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;} - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;} + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} + + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;} + + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;} + + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;} }; template struct __less<_T1, _T1> { - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} }; template struct __less { - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} }; template struct __less<_T1, const _T1> { - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} }; template @@ -958,7 +977,7 @@ __find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, } template -_RandomAccessIterator1 +_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1 __find_end(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, random_access_iterator_tag) @@ -1024,8 +1043,8 @@ find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, // find_first_of template -_ForwardIterator1 -find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1, +_LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator1 +__find_first_of_ce(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred) { for (; __first1 != __last1; ++__first1) @@ -1035,6 +1054,16 @@ find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1, return __last1; } + +template +inline _LIBCPP_INLINE_VISIBILITY +_ForwardIterator1 +find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred) +{ + return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __pred); +} + template inline _LIBCPP_INLINE_VISIBILITY _ForwardIterator1 @@ -1043,7 +1072,7 @@ find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1, { typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; - return _VSTD::find_first_of(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); + return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); } // adjacent_find @@ -1111,7 +1140,7 @@ pair<_InputIterator1, _InputIterator2> mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred) { - for (; __first1 != __last1; ++__first1, ++__first2) + for (; __first1 != __last1; ++__first1, (void) ++__first2) if (!__pred(*__first1, *__first2)) break; return pair<_InputIterator1, _InputIterator2>(__first1, __first2); @@ -1135,7 +1164,7 @@ mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred) { - for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) + for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2) if (!__pred(*__first1, *__first2)) break; return pair<_InputIterator1, _InputIterator2>(__first1, __first2); @@ -1160,7 +1189,7 @@ inline _LIBCPP_INLINE_VISIBILITY bool equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred) { - for (; __first1 != __last1; ++__first1, ++__first2) + for (; __first1 != __last1; ++__first1, (void) ++__first2) if (!__pred(*__first1, *__first2)) return false; return true; @@ -1184,7 +1213,7 @@ __equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred, input_iterator_tag, input_iterator_tag ) { - for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) + for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2) if (!__pred(*__first1, *__first2)) return false; return __first1 == __last1 && __first2 == __last2; @@ -1238,7 +1267,7 @@ is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _BinaryPredicate __pred) { // shorten sequences as much as possible by lopping of any equal parts - for (; __first1 != __last1; ++__first1, ++__first2) + for (; __first1 != __last1; ++__first1, (void) ++__first2) if (!__pred(*__first1, *__first2)) goto __not_done; return true; @@ -1298,7 +1327,7 @@ __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, forward_iterator_tag, forward_iterator_tag ) { // shorten sequences as much as possible by lopping of any equal parts - for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) + for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2) if (!__pred(*__first1, *__first2)) goto __not_done; return __first1 == __last1 && __first2 == __last2; @@ -1423,7 +1452,7 @@ __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, } template -_RandomAccessIterator1 +_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1 __search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, random_access_iterator_tag) @@ -1716,7 +1745,7 @@ inline _LIBCPP_INLINE_VISIBILITY _OutputIterator __copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { - for (; __first != __last; ++__first, ++__result) + for (; __first != __last; ++__first, (void) ++__result) *__result = *__first; return __result; } @@ -1845,7 +1874,7 @@ inline _LIBCPP_INLINE_VISIBILITY _OutputIterator __move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { - for (; __first != __last; ++__first, ++__result) + for (; __first != __last; ++__first, (void) ++__result) *__result = _VSTD::move(*__first); return __result; } @@ -1921,7 +1950,7 @@ inline _LIBCPP_INLINE_VISIBILITY _OutputIterator transform(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _UnaryOperation __op) { - for (; __first != __last; ++__first, ++__result) + for (; __first != __last; ++__first, (void) ++__result) *__result = __op(*__first); return __result; } @@ -1932,7 +1961,7 @@ _OutputIterator transform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _OutputIterator __result, _BinaryOperation __binary_op) { - for (; __first1 != __last1; ++__first1, ++__first2, ++__result) + for (; __first1 != __last1; ++__first1, (void) ++__first2, ++__result) *__result = __binary_op(*__first1, *__first2); return __result; } @@ -1969,7 +1998,7 @@ _OutputIterator replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __old_value, const _Tp& __new_value) { - for (; __first != __last; ++__first, ++__result) + for (; __first != __last; ++__first, (void) ++__result) if (*__first == __old_value) *__result = __new_value; else @@ -1985,7 +2014,7 @@ _OutputIterator replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred, const _Tp& __new_value) { - for (; __first != __last; ++__first, ++__result) + for (; __first != __last; ++__first, (void) ++__result) if (__pred(*__first)) *__result = __new_value; else @@ -2000,7 +2029,7 @@ inline _LIBCPP_INLINE_VISIBILITY _OutputIterator __fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_) { - for (; __n > 0; ++__first, --__n) + for (; __n > 0; ++__first, (void) --__n) *__first = __value_; return __first; } @@ -2074,7 +2103,7 @@ inline _LIBCPP_INLINE_VISIBILITY _OutputIterator generate_n(_OutputIterator __first, _Size __n, _Generator __gen) { - for (; __n > 0; ++__first, --__n) + for (; __n > 0; ++__first, (void) --__n) *__first = __gen(); return __first; } @@ -2505,9 +2534,9 @@ rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterato // min_element template -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator -min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) +__min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) { if (__first != __last) { @@ -2519,19 +2548,27 @@ min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) return __first; } +template +inline _LIBCPP_INLINE_VISIBILITY +_ForwardIterator +min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) +{ + return __min_element(__first, __last, __comp); +} + template inline _LIBCPP_INLINE_VISIBILITY _ForwardIterator min_element(_ForwardIterator __first, _ForwardIterator __last) { - return _VSTD::min_element(__first, __last, + return __min_element(__first, __last, __less::value_type>()); } // min template -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 const _Tp& min(const _Tp& __a, const _Tp& __b, _Compare __comp) { @@ -2539,7 +2576,7 @@ min(const _Tp& __a, const _Tp& __b, _Compare __comp) } template -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 const _Tp& min(const _Tp& __a, const _Tp& __b) { @@ -2549,19 +2586,19 @@ min(const _Tp& __a, const _Tp& __b) #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS template -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 _Tp min(initializer_list<_Tp> __t, _Compare __comp) { - return *_VSTD::min_element(__t.begin(), __t.end(), __comp); + return *__min_element(__t.begin(), __t.end(), __comp); } template -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 _Tp min(initializer_list<_Tp> __t) { - return *_VSTD::min_element(__t.begin(), __t.end()); + return *__min_element(__t.begin(), __t.end(), __less<_Tp>()); } #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS @@ -2569,9 +2606,9 @@ min(initializer_list<_Tp> __t) // max_element template -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator -max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) +__max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) { if (__first != __last) { @@ -2583,19 +2620,28 @@ max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) return __first; } + +template +inline _LIBCPP_INLINE_VISIBILITY +_ForwardIterator +max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) +{ + return __max_element(__first, __last, __comp); +} + template inline _LIBCPP_INLINE_VISIBILITY _ForwardIterator max_element(_ForwardIterator __first, _ForwardIterator __last) { - return _VSTD::max_element(__first, __last, + return __max_element(__first, __last, __less::value_type>()); } // max template -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 const _Tp& max(const _Tp& __a, const _Tp& __b, _Compare __comp) { @@ -2603,7 +2649,7 @@ max(const _Tp& __a, const _Tp& __b, _Compare __comp) } template -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 const _Tp& max(const _Tp& __a, const _Tp& __b) { @@ -2613,19 +2659,19 @@ max(const _Tp& __a, const _Tp& __b) #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS template -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 _Tp max(initializer_list<_Tp> __t, _Compare __comp) { - return *_VSTD::max_element(__t.begin(), __t.end(), __comp); + return *__max_element(__t.begin(), __t.end(), __comp); } template -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 _Tp max(initializer_list<_Tp> __t) { - return *_VSTD::max_element(__t.begin(), __t.end()); + return *__max_element(__t.begin(), __t.end(), __less<_Tp>()); } #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS @@ -2684,13 +2730,14 @@ inline _LIBCPP_INLINE_VISIBILITY std::pair<_ForwardIterator, _ForwardIterator> minmax_element(_ForwardIterator __first, _ForwardIterator __last) { - return _VSTD::minmax_element(__first, __last, __less::value_type>()); + return _VSTD::minmax_element(__first, __last, + __less::value_type>()); } // minmax template -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 pair minmax(const _Tp& __a, const _Tp& __b, _Compare __comp) { @@ -2699,7 +2746,7 @@ minmax(const _Tp& __a, const _Tp& __b, _Compare __comp) } template -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 pair minmax(const _Tp& __a, const _Tp& __b) { @@ -2708,24 +2755,49 @@ minmax(const _Tp& __a, const _Tp& __b) #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS -template -inline _LIBCPP_INLINE_VISIBILITY +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_Tp, _Tp> -minmax(initializer_list<_Tp> __t) +minmax(initializer_list<_Tp> __t, _Compare __comp) { - pair __p = - _VSTD::minmax_element(__t.begin(), __t.end()); - return pair<_Tp, _Tp>(*__p.first, *__p.second); + typedef typename initializer_list<_Tp>::const_iterator _Iter; + _Iter __first = __t.begin(); + _Iter __last = __t.end(); + std::pair<_Tp, _Tp> __result ( *__first, *__first ); + + ++__first; + if (__t.size() % 2 == 0) + { + if (__comp(*__first, __result.first)) + __result.first = *__first; + else + __result.second = *__first; + ++__first; + } + + while (__first != __last) + { + _Tp __prev = *__first++; + if (__comp(__prev, *__first)) { + if (__comp(__prev, __result.first)) __result.first = __prev; + if (__comp(__result.second, *__first)) __result.second = *__first; + } + else { + if (__comp(*__first, __result.first)) __result.first = *__first; + if (__comp(__result.second, __prev)) __result.second = __prev; + } + + __first++; + } + return __result; } -template -inline _LIBCPP_INLINE_VISIBILITY +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_Tp, _Tp> -minmax(initializer_list<_Tp> __t, _Compare __comp) +minmax(initializer_list<_Tp> __t) { - pair __p = - _VSTD::minmax_element(__t.begin(), __t.end(), __comp); - return pair<_Tp, _Tp>(*__p.first, *__p.second); + return _VSTD::minmax(__t, __less<_Tp>()); } #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS @@ -4300,7 +4372,7 @@ __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator if (__len1 <= __len2) { value_type* __p = __buff; - for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), ++__i, ++__p) + for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), (void) ++__i, ++__p) ::new(__p) value_type(_VSTD::move(*__i)); __merge<_Compare>(move_iterator(__buff), move_iterator(__p), @@ -4311,7 +4383,7 @@ __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator else { value_type* __p = __buff; - for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), ++__i, ++__p) + for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), (void) ++__i, ++__p) ::new(__p) value_type(_VSTD::move(*__i)); typedef reverse_iterator<_BidirectionalIterator> _RBi; typedef reverse_iterator _Rv; @@ -4336,7 +4408,7 @@ __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, if (__len2 == 0) return; // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0 - for (; true; ++__first, --__len1) + for (; true; ++__first, (void) --__len1) { if (__len1 == 0) return; @@ -4724,49 +4796,8 @@ is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) template void -__push_heap_front(_RandomAccessIterator __first, _RandomAccessIterator, _Compare __comp, - typename iterator_traits<_RandomAccessIterator>::difference_type __len) -{ - typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; - typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; - if (__len > 1) - { - difference_type __p = 0; - _RandomAccessIterator __pp = __first; - difference_type __c = 2; - _RandomAccessIterator __cp = __first + __c; - if (__c == __len || __comp(*__cp, *(__cp - 1))) - { - --__c; - --__cp; - } - if (__comp(*__pp, *__cp)) - { - value_type __t(_VSTD::move(*__pp)); - do - { - *__pp = _VSTD::move(*__cp); - __pp = __cp; - __p = __c; - __c = (__p + 1) * 2; - if (__c > __len) - break; - __cp = __first + __c; - if (__c == __len || __comp(*__cp, *(__cp - 1))) - { - --__c; - --__cp; - } - } while (__comp(__t, *__cp)); - *__pp = _VSTD::move(__t); - } - } -} - -template -void -__push_heap_back(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, - typename iterator_traits<_RandomAccessIterator>::difference_type __len) +__sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, + typename iterator_traits<_RandomAccessIterator>::difference_type __len) { typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; @@ -4799,10 +4830,10 @@ push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare #ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); - __push_heap_back<_Comp_ref>(__first, __last, __c, __last - __first); + __sift_up<_Comp_ref>(__first, __last, __c, __last - __first); #else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; - __push_heap_back<_Comp_ref>(__first, __last, __comp, __last - __first); + __sift_up<_Comp_ref>(__first, __last, __comp, __last - __first); #endif // _LIBCPP_DEBUG } @@ -4817,6 +4848,60 @@ push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) // pop_heap template +void +__sift_down(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, + typename iterator_traits<_RandomAccessIterator>::difference_type __len, + _RandomAccessIterator __start) +{ + typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; + typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; + // left-child of __start is at 2 * __start + 1 + // right-child of __start is at 2 * __start + 2 + difference_type __child = __start - __first; + + if (__len < 2 || (__len - 2) / 2 < __child) + return; + + __child = 2 * __child + 1; + _RandomAccessIterator __child_i = __first + __child; + + if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) { + // right-child exists and is greater than left-child + ++__child_i; + ++__child; + } + + // check if we are in heap-order + if (__comp(*__child_i, *__start)) + // we are, __start is larger than it's largest child + return; + + value_type __top(_VSTD::move(*__start)); + do + { + // we are not in heap-order, swap the parent with it's largest child + *__start = _VSTD::move(*__child_i); + __start = __child_i; + + if ((__len - 2) / 2 < __child) + break; + + // recompute the child based off of the updated parent + __child = 2 * __child + 1; + __child_i = __first + __child; + + if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) { + // right-child exists and is greater than left-child + ++__child_i; + ++__child; + } + + // check if we are in heap-order + } while (!__comp(*__child_i, __top)); + *__start = _VSTD::move(__top); +} + +template inline _LIBCPP_INLINE_VISIBILITY void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, @@ -4825,7 +4910,7 @@ __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare if (__len > 1) { swap(*__first, *--__last); - __push_heap_front<_Compare>(__first, __last, __comp, __len-1); + __sift_down<_Compare>(__first, __last, __comp, __len - 1, __first); } } @@ -4862,10 +4947,11 @@ __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compar difference_type __n = __last - __first; if (__n > 1) { - __last = __first; - ++__last; - for (difference_type __i = 1; __i < __n;) - __push_heap_back<_Compare>(__first, ++__last, __comp, ++__i); + // start from the first parent, there is no need to consider children + for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start) + { + __sift_down<_Compare>(__first, __last, __comp, __n, __first + __start); + } } } @@ -4940,7 +5026,7 @@ __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _R if (__comp(*__i, *__first)) { swap(*__i, *__first); - __push_heap_front<_Compare>(__first, __middle, __comp, __len); + __sift_down<_Compare>(__first, __middle, __comp, __len, __first); } } __sort_heap<_Compare>(__first, __middle, __comp); @@ -4981,15 +5067,15 @@ __partial_sort_copy(_InputIterator __first, _InputIterator __last, _RandomAccessIterator __r = __result_first; if (__r != __result_last) { - typename iterator_traits<_RandomAccessIterator>::difference_type __len = 0; - for (; __first != __last && __r != __result_last; ++__first, ++__r, ++__len) + for (; __first != __last && __r != __result_last; (void) ++__first, ++__r) *__r = *__first; __make_heap<_Compare>(__result_first, __r, __comp); + typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first; for (; __first != __last; ++__first) if (__comp(*__first, *__result_first)) { *__result_first = *__first; - __push_heap_front<_Compare>(__result_first, __r, __comp, __len); + __sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first); } __sort_heap<_Compare>(__result_first, __r, __comp); } @@ -5503,7 +5589,7 @@ bool __lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp) { - for (; __first2 != __last2; ++__first1, ++__first2) + for (; __first2 != __last2; ++__first1, (void) ++__first2) { if (__first1 == __last1 || __comp(*__first1, *__first2)) return true; -- cgit v1.1