diff options
Diffstat (limited to 'libcxx/include')
78 files changed, 1356 insertions, 1239 deletions
diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt index c6b87a34a43e..db918a16e9a6 100644 --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -778,7 +778,6 @@ set(files __tree __tuple/find_index.h __tuple/ignore.h - __tuple/make_tuple_types.h __tuple/sfinae_helpers.h __tuple/tuple_element.h __tuple/tuple_like.h @@ -792,7 +791,6 @@ set(files __type_traits/aligned_storage.h __type_traits/aligned_union.h __type_traits/alignment_of.h - __type_traits/can_extract_key.h __type_traits/common_reference.h __type_traits/common_type.h __type_traits/conditional.h @@ -873,6 +871,7 @@ set(files __type_traits/is_trivially_relocatable.h __type_traits/is_unbounded_array.h __type_traits/is_union.h + __type_traits/is_unqualified.h __type_traits/is_unsigned.h __type_traits/is_valid_expansion.h __type_traits/is_void.h @@ -912,6 +911,7 @@ set(files __utility/cmp.h __utility/convert_to_integral.h __utility/declval.h + __utility/default_three_way_comparator.h __utility/element_count.h __utility/empty.h __utility/exception_guard.h @@ -922,6 +922,7 @@ set(files __utility/integer_sequence.h __utility/is_pointer_in_range.h __utility/is_valid_range.h + __utility/lazy_synth_three_way_comparator.h __utility/move.h __utility/no_destroy.h __utility/pair.h @@ -933,6 +934,7 @@ set(files __utility/small_buffer.h __utility/swap.h __utility/to_underlying.h + __utility/try_key_extraction.h __utility/unreachable.h __variant/monostate.h __vector/comparison.h diff --git a/libcxx/include/__algorithm/make_heap.h b/libcxx/include/__algorithm/make_heap.h index e8f0cdb27333..8cfeda2b5981 100644 --- a/libcxx/include/__algorithm/make_heap.h +++ b/libcxx/include/__algorithm/make_heap.h @@ -12,9 +12,11 @@ #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/iterator_operations.h> +#include <__algorithm/push_heap.h> #include <__algorithm/sift_down.h> #include <__config> #include <__iterator/iterator_traits.h> +#include <__type_traits/is_arithmetic.h> #include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -31,13 +33,23 @@ inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare&& __comp) { __comp_ref_type<_Compare> __comp_ref = __comp; - using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type; - difference_type __n = __last - __first; + using __diff_t = __iter_diff_t<_RandomAccessIterator>; + const __diff_t __n = __last - __first; + + static const bool __assume_both_children = is_arithmetic<__iter_value_type<_RandomAccessIterator> >::value; + + // While it would be correct to always assume we have both children, in practice we observed this to be a performance + // improvement only for arithmetic types. + const __diff_t __sift_down_n = __assume_both_children ? ((__n & 1) ? __n : __n - 1) : __n; + if (__n > 1) { // start from the first parent, there is no need to consider children - for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start) { - std::__sift_down<_AlgPolicy>(__first, __comp_ref, __n, __first + __start); + + for (__diff_t __start = (__sift_down_n - 2) / 2; __start >= 0; --__start) { + std::__sift_down<_AlgPolicy, __assume_both_children>(__first, __comp_ref, __sift_down_n, __start); } + if _LIBCPP_CONSTEXPR (__assume_both_children) + std::__sift_up<_AlgPolicy>(__first, __last, __comp, __n); } } diff --git a/libcxx/include/__algorithm/partial_sort.h b/libcxx/include/__algorithm/partial_sort.h index 7f8d0c49147e..4b39ae0cf2df 100644 --- a/libcxx/include/__algorithm/partial_sort.h +++ b/libcxx/include/__algorithm/partial_sort.h @@ -45,7 +45,7 @@ _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _RandomAccessIterator __part for (; __i != __last; ++__i) { if (__comp(*__i, *__first)) { _IterOps<_AlgPolicy>::iter_swap(__i, __first); - std::__sift_down<_AlgPolicy>(__first, __comp, __len, __first); + std::__sift_down<_AlgPolicy, false>(__first, __comp, __len, 0); } } std::__sort_heap<_AlgPolicy>(std::move(__first), std::move(__middle), __comp); diff --git a/libcxx/include/__algorithm/partial_sort_copy.h b/libcxx/include/__algorithm/partial_sort_copy.h index 172f53b290d5..2230dfc9cc4a 100644 --- a/libcxx/include/__algorithm/partial_sort_copy.h +++ b/libcxx/include/__algorithm/partial_sort_copy.h @@ -60,7 +60,7 @@ _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_InputIterator, _Random for (; __first != __last; ++__first) if (std::__invoke(__comp, std::__invoke(__proj1, *__first), std::__invoke(__proj2, *__result_first))) { *__result_first = *__first; - std::__sift_down<_AlgPolicy>(__result_first, __projected_comp, __len, __result_first); + std::__sift_down<_AlgPolicy, false>(__result_first, __projected_comp, __len, 0); } std::__sort_heap<_AlgPolicy>(__result_first, __r, __projected_comp); } diff --git a/libcxx/include/__algorithm/sift_down.h b/libcxx/include/__algorithm/sift_down.h index 42803e30631f..e01c9b2b00f8 100644 --- a/libcxx/include/__algorithm/sift_down.h +++ b/libcxx/include/__algorithm/sift_down.h @@ -24,59 +24,60 @@ _LIBCPP_PUSH_MACROS _LIBCPP_BEGIN_NAMESPACE_STD -template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> +template <class _AlgPolicy, bool __assume_both_children, class _Compare, class _RandomAccessIterator> _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void __sift_down(_RandomAccessIterator __first, _Compare&& __comp, - typename iterator_traits<_RandomAccessIterator>::difference_type __len, - _RandomAccessIterator __start) { + __iter_diff_t<_RandomAccessIterator> __len, + __iter_diff_t<_RandomAccessIterator> __start) { using _Ops = _IterOps<_AlgPolicy>; 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; + difference_type __child = __start; if (__len < 2 || (__len - 2) / 2 < __child) return; - __child = 2 * __child + 1; - _RandomAccessIterator __child_i = __first + __child; + __child = 2 * __child + 1; - if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) { + if _LIBCPP_CONSTEXPR (__assume_both_children) { + // right-child exists and is greater than left-child + __child += __comp(__first[__child], __first[__child + 1]); + } else if ((__child + 1) < __len && __comp(__first[__child], __first[__child + 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)) + if (__comp(__first[__child], __first[__start])) // we are, __start is larger than its largest child return; - value_type __top(_Ops::__iter_move(__start)); + value_type __top(_Ops::__iter_move(__first + __start)); do { // we are not in heap-order, swap the parent with its largest child - *__start = _Ops::__iter_move(__child_i); - __start = __child_i; + __first[__start] = _Ops::__iter_move(__first + __child); + __start = __child; if ((__len - 2) / 2 < __child) break; // recompute the child based off of the updated parent - __child = 2 * __child + 1; - __child_i = __first + __child; + __child = 2 * __child + 1; - if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) { + if _LIBCPP_CONSTEXPR (__assume_both_children) { + __child += __comp(__first[__child], __first[__child + 1]); + } else if ((__child + 1) < __len && __comp(__first[__child], __first[__child + 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 = std::move(__top); + } while (!__comp(__first[__child], __top)); + __first[__start] = std::move(__top); } template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> diff --git a/libcxx/include/__algorithm/simd_utils.h b/libcxx/include/__algorithm/simd_utils.h index 07fef20f6166..96b074c063a5 100644 --- a/libcxx/include/__algorithm/simd_utils.h +++ b/libcxx/include/__algorithm/simd_utils.h @@ -123,7 +123,7 @@ template <class _Tp, size_t _Np> [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI size_t __find_first_set(__simd_vector<_Tp, _Np> __vec) noexcept { using __mask_vec = __simd_vector<bool, _Np>; - // This has MSan disabled du to https://github.com/llvm/llvm-project/issues/85876 + // This has MSan disabled du to https://llvm.org/PR85876 auto __impl = [&]<class _MaskT>(_MaskT) _LIBCPP_NO_SANITIZE("memory") noexcept { # if defined(_LIBCPP_BIG_ENDIAN) return std::min<size_t>( diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h index 06cb5b8ce705..8aa894e9228c 100644 --- a/libcxx/include/__algorithm/sort.h +++ b/libcxx/include/__algorithm/sort.h @@ -860,6 +860,9 @@ __sort<__less<long double>&, long double*>(long double*, long double*, __less<lo template <class _AlgPolicy, class _RandomAccessIterator, class _Comp> _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __sort_dispatch(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) { + if (__first == __last) // log(0) is undefined, so don't try computing the depth + return; + typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; difference_type __depth_limit = 2 * std::__bit_log2(std::__to_unsigned_like(__last - __first)); diff --git a/libcxx/include/__atomic/atomic.h b/libcxx/include/__atomic/atomic.h index eead49dde619..3554ff516995 100644 --- a/libcxx/include/__atomic/atomic.h +++ b/libcxx/include/__atomic/atomic.h @@ -350,7 +350,7 @@ private: // &Context.getTargetInfo().getLongDoubleFormat() == // &llvm::APFloat::x87DoubleExtended()) // For more info - // https://github.com/llvm/llvm-project/issues/68602 + // https://llvm.org/PR68602 // https://reviews.llvm.org/D53965 return !__is_fp80_long_double(); # endif @@ -367,7 +367,7 @@ private: while (!__self.compare_exchange_weak(__old, __new, __m, memory_order_relaxed)) { # ifdef _LIBCPP_COMPILER_CLANG_BASED if constexpr (__is_fp80_long_double()) { - // https://github.com/llvm/llvm-project/issues/47978 + // https://llvm.org/PR47978 // clang bug: __old is not updated on failure for atomic<long double>::compare_exchange_weak // Note __old = __self.load(memory_order_relaxed) will not work std::__cxx_atomic_load_inplace(std::addressof(__self.__a_), std::addressof(__old), memory_order_relaxed); diff --git a/libcxx/include/__bit/bit_log2.h b/libcxx/include/__bit/bit_log2.h index 8077cd91d6fd..9ceeec1b2bc9 100644 --- a/libcxx/include/__bit/bit_log2.h +++ b/libcxx/include/__bit/bit_log2.h @@ -9,6 +9,7 @@ #ifndef _LIBCPP___BIT_BIT_LOG2_H #define _LIBCPP___BIT_BIT_LOG2_H +#include <__assert> #include <__bit/countl.h> #include <__config> #include <__type_traits/integer_traits.h> @@ -23,6 +24,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _Tp> _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Tp __bit_log2(_Tp __t) _NOEXCEPT { static_assert(__is_unsigned_integer_v<_Tp>, "__bit_log2 requires an unsigned integer type"); + _LIBCPP_ASSERT_INTERNAL(__t != 0, "logarithm of 0 is undefined"); return numeric_limits<_Tp>::digits - 1 - std::__countl_zero(__t); } diff --git a/libcxx/include/__charconv/from_chars_result.h b/libcxx/include/__charconv/from_chars_result.h index a7bfd6530a8a..b4ecea3d1145 100644 --- a/libcxx/include/__charconv/from_chars_result.h +++ b/libcxx/include/__charconv/from_chars_result.h @@ -21,7 +21,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD #if _LIBCPP_STD_VER >= 17 -struct _LIBCPP_EXPORTED_FROM_ABI from_chars_result { +struct from_chars_result { const char* ptr; errc ec; # if _LIBCPP_STD_VER >= 20 diff --git a/libcxx/include/__charconv/to_chars_result.h b/libcxx/include/__charconv/to_chars_result.h index 41dea4ab1472..a3cd4e28d017 100644 --- a/libcxx/include/__charconv/to_chars_result.h +++ b/libcxx/include/__charconv/to_chars_result.h @@ -21,7 +21,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD #if _LIBCPP_STD_VER >= 17 -struct _LIBCPP_EXPORTED_FROM_ABI to_chars_result { +struct to_chars_result { char* ptr; errc ec; # if _LIBCPP_STD_VER >= 20 diff --git a/libcxx/include/__config b/libcxx/include/__config index 77a71b6cf1ca..23b9123fa691 100644 --- a/libcxx/include/__config +++ b/libcxx/include/__config @@ -934,7 +934,7 @@ typedef __char32_t char32_t; # endif # endif -# if defined(__FreeBSD__) && defined(__clang__) && __has_attribute(__no_thread_safety_analysis__) +# if __has_attribute(__no_thread_safety_analysis__) # define _LIBCPP_NO_THREAD_SAFETY_ANALYSIS __attribute__((__no_thread_safety_analysis__)) # else # define _LIBCPP_NO_THREAD_SAFETY_ANALYSIS @@ -1156,6 +1156,13 @@ typedef __char32_t char32_t; # define _LIBCPP_LIFETIMEBOUND # endif +// This is to work around https://llvm.org/PR156809 +# ifndef _LIBCPP_CXX03_LANG +# define _LIBCPP_CTOR_LIFETIMEBOUND _LIBCPP_LIFETIMEBOUND +# else +# define _LIBCPP_CTOR_LIFETIMEBOUND +# endif + # if __has_cpp_attribute(_Clang::__noescape__) # define _LIBCPP_NOESCAPE [[_Clang::__noescape__]] # else diff --git a/libcxx/include/__configuration/abi.h b/libcxx/include/__configuration/abi.h index a75cd0a67533..2d33b9c03090 100644 --- a/libcxx/include/__configuration/abi.h +++ b/libcxx/include/__configuration/abi.h @@ -72,6 +72,7 @@ # define _LIBCPP_ABI_NO_FILESYSTEM_INLINE_NAMESPACE # define _LIBCPP_ABI_NO_ITERATOR_BASES # define _LIBCPP_ABI_NO_RANDOM_DEVICE_COMPATIBILITY_LAYOUT +# define _LIBCPP_ABI_NO_REVERSE_ITERATOR_SECOND_MEMBER # define _LIBCPP_ABI_OPTIMIZED_FUNCTION # define _LIBCPP_ABI_REGEX_CONSTANTS_NONZERO # define _LIBCPP_ABI_STRING_OPTIMIZED_EXTERNAL_INSTANTIATION @@ -98,11 +99,20 @@ # endif #endif +// TODO(LLVM 22): Remove this check +#if defined(_LIBCPP_ABI_NO_ITERATOR_BASES) && !defined(_LIBCPP_ABI_NO_REVERSE_ITERATOR_SECOND_MEMBER) +# ifndef _LIBCPP_ONLY_NO_ITERATOR_BASES +# error "You probably want to define _LIBCPP_ABI_NO_REVERSE_ITERATOR_SECOND_MEMBER. This has been split out from" \ + " _LIBCPP_ABI_NO_ITERATOR_BASES to allow only removing the second iterator member, since they aren't really related." \ + "If you actually want this ABI configuration, please define _LIBCPP_ONLY_NO_ITERATOR_BASES instead." +# endif +#endif + // We had some bugs where we use [[no_unique_address]] together with construct_at, // which causes UB as the call on construct_at could write to overlapping subobjects // -// https://github.com/llvm/llvm-project/issues/70506 -// https://github.com/llvm/llvm-project/issues/70494 +// https://llvm.org/PR70506 +// https://llvm.org/PR70494 // // To fix the bug we had to change the ABI of some classes to remove [[no_unique_address]] under certain conditions. // The macro below is used for all classes whose ABI have changed as part of fixing these bugs. diff --git a/libcxx/include/__configuration/availability.h b/libcxx/include/__configuration/availability.h index ae58e36b508b..2fbc34a3cf8a 100644 --- a/libcxx/include/__configuration/availability.h +++ b/libcxx/include/__configuration/availability.h @@ -72,7 +72,7 @@ // // We also allow users to force-disable availability markup via the `_LIBCPP_DISABLE_AVAILABILITY` // macro because that is the only way to work around a Clang bug related to availability -// attributes: https://github.com/llvm/llvm-project/issues/134151. +// attributes: https://llvm.org/PR134151. // Once that bug has been fixed, we should remove the macro. #if defined(_LIBCPP_BUILDING_LIBRARY) || defined(_LIBCXXABI_BUILDING_LIBRARY) || \ !defined(_LIBCPP_COMPILER_CLANG_BASED) || defined(_LIBCPP_DISABLE_AVAILABILITY) @@ -307,7 +307,7 @@ // This controls the availability of the C++17 std::pmr library, // which is implemented in large part in the built library. // -// TODO: Enable std::pmr markup once https://github.com/llvm/llvm-project/issues/40340 has been fixed +// TODO: Enable std::pmr markup once https://llvm.org/PR40340 has been fixed // Until then, it is possible for folks to try to use `std::pmr` when back-deploying to targets that don't support // it and it'll be a load-time error, but we don't have a good alternative because the library won't compile if we // use availability annotations until that bug has been fixed. diff --git a/libcxx/include/__cxx03/__config b/libcxx/include/__cxx03/__config index 9b88a495055e..d574eab8a12b 100644 --- a/libcxx/include/__cxx03/__config +++ b/libcxx/include/__cxx03/__config @@ -622,18 +622,6 @@ typedef __char32_t char32_t; # define _LIBCPP_HAS_NO_ALIGNED_ALLOCATION # endif -// It is not yet possible to use aligned_alloc() on all Apple platforms since -// 10.15 was the first version to ship an implementation of aligned_alloc(). -# if defined(__APPLE__) -# if (defined(__ENVIRONMENT_MAC_OS_X_VERSION_MIN_REQUIRED__) && \ - __ENVIRONMENT_MAC_OS_X_VERSION_MIN_REQUIRED__ < 101500) -# define _LIBCPP_HAS_NO_C11_ALIGNED_ALLOC -# endif -# elif defined(__ANDROID__) && __ANDROID_API__ < 28 -// Android only provides aligned_alloc when targeting API 28 or higher. -# define _LIBCPP_HAS_NO_C11_ALIGNED_ALLOC -# endif - # if defined(__APPLE__) || defined(__FreeBSD__) # define _LIBCPP_HAS_DEFAULTRUNELOCALE # endif diff --git a/libcxx/include/__cxx03/__iterator/prev.h b/libcxx/include/__cxx03/__iterator/prev.h index dc1bdaf58402..32f6e66dac9a 100644 --- a/libcxx/include/__cxx03/__iterator/prev.h +++ b/libcxx/include/__cxx03/__iterator/prev.h @@ -15,16 +15,20 @@ #include <__cxx03/__iterator/advance.h> #include <__cxx03/__iterator/iterator_traits.h> #include <__cxx03/__type_traits/enable_if.h> +#include <__cxx03/__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header #endif +_LIBCPP_PUSH_MACROS +#include <__cxx03/__undef_macros> + _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0> inline _LIBCPP_HIDE_FROM_ABI _InputIter -prev(_InputIter __x, typename iterator_traits<_InputIter>::difference_type __n = 1) { +prev(_InputIter __x, typename iterator_traits<_InputIter>::difference_type __n) { // Calling `advance` with a negative value on a non-bidirectional iterator is a no-op in the current implementation. // Note that this check duplicates the similar check in `std::advance`. _LIBCPP_ASSERT_PEDANTIC(__n <= 0 || __has_bidirectional_iterator_category<_InputIter>::value, @@ -33,6 +37,18 @@ prev(_InputIter __x, typename iterator_traits<_InputIter>::difference_type __n = return __x; } +// LWG 3197 +// It is unclear what the implications of "BidirectionalIterator" in the standard are. +// However, calling std::prev(non-bidi-iterator) is obviously an error and we should catch it at compile time. +template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0> +[[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _InputIter prev(_InputIter __it) { + static_assert(__has_bidirectional_iterator_category<_InputIter>::value, + "Attempt to prev(it) with a non-bidirectional iterator"); + return std::prev(std::move(__it), 1); +} + +_LIBCPP_POP_MACROS + _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___CXX03___ITERATOR_PREV_H diff --git a/libcxx/include/__cxx03/__locale b/libcxx/include/__cxx03/__locale index d5faa89b99fc..86160bcdcbd5 100644 --- a/libcxx/include/__cxx03/__locale +++ b/libcxx/include/__cxx03/__locale @@ -582,18 +582,6 @@ public: #endif _LIBCPP_HIDE_FROM_ABI const mask* table() const _NOEXCEPT { return __tab_; } static const mask* classic_table() _NOEXCEPT; -#if defined(__GLIBC__) || defined(__EMSCRIPTEN__) - static const int* __classic_upper_table() _NOEXCEPT; - static const int* __classic_lower_table() _NOEXCEPT; -#endif -#if defined(__NetBSD__) - static const short* __classic_upper_table() _NOEXCEPT; - static const short* __classic_lower_table() _NOEXCEPT; -#endif -#if defined(__MVS__) - static const unsigned short* __classic_upper_table() _NOEXCEPT; - static const unsigned short* __classic_lower_table() _NOEXCEPT; -#endif protected: ~ctype() override; diff --git a/libcxx/include/__cxx03/__mutex/once_flag.h b/libcxx/include/__cxx03/__mutex/once_flag.h index eaeaa6121bff..529aa7707177 100644 --- a/libcxx/include/__cxx03/__mutex/once_flag.h +++ b/libcxx/include/__cxx03/__mutex/once_flag.h @@ -10,6 +10,7 @@ #define _LIBCPP___CXX03___MUTEX_ONCE_FLAG_H #include <__cxx03/__config> +#include <__cxx03/__memory/addressof.h> #include <__cxx03/__memory/shared_ptr.h> // __libcpp_acquire_load #include <__cxx03/__tuple/tuple_indices.h> #include <__cxx03/__tuple/tuple_size.h> @@ -82,7 +83,7 @@ template <class _Callable> inline _LIBCPP_HIDE_FROM_ABI void call_once(once_flag& __flag, _Callable& __func) { if (__libcpp_acquire_load(&__flag.__state_) != once_flag::_Complete) { __call_once_param<_Callable> __p(__func); - std::__call_once(__flag.__state_, &__p, &__call_once_proxy<_Callable>); + std::__call_once(__flag.__state_, std::addressof(__p), std::addressof(__call_once_proxy<_Callable>)); } } @@ -90,7 +91,7 @@ template <class _Callable> inline _LIBCPP_HIDE_FROM_ABI void call_once(once_flag& __flag, const _Callable& __func) { if (__libcpp_acquire_load(&__flag.__state_) != once_flag::_Complete) { __call_once_param<const _Callable> __p(__func); - std::__call_once(__flag.__state_, &__p, &__call_once_proxy<const _Callable>); + std::__call_once(__flag.__state_, std::addressof(__p), std::addressof(__call_once_proxy<const _Callable>)); } } diff --git a/libcxx/include/__cxx03/bitset b/libcxx/include/__cxx03/bitset index 63d2c23a73bd..37ad674686ba 100644 --- a/libcxx/include/__cxx03/bitset +++ b/libcxx/include/__cxx03/bitset @@ -185,9 +185,9 @@ protected: __storage_type __first_[_N_words]; typedef __bit_reference<__bitset> reference; - typedef __bit_const_reference<__bitset> const_reference; - typedef __bit_iterator<__bitset, false> iterator; - typedef __bit_iterator<__bitset, true> const_iterator; + typedef __bit_const_reference<__bitset> __const_reference; + typedef __bit_iterator<__bitset, false> __iterator; + typedef __bit_iterator<__bitset, true> __const_iterator; _LIBCPP_HIDE_FROM_ABI __bitset() _NOEXCEPT; _LIBCPP_HIDE_FROM_ABI explicit __bitset(unsigned long long __v) _NOEXCEPT; @@ -195,14 +195,14 @@ protected: _LIBCPP_HIDE_FROM_ABI reference __make_ref(size_t __pos) _NOEXCEPT { return reference(__first_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word); } - _LIBCPP_HIDE_FROM_ABI const_reference __make_ref(size_t __pos) const _NOEXCEPT { - return const_reference(__first_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word); + _LIBCPP_HIDE_FROM_ABI __const_reference __make_ref(size_t __pos) const _NOEXCEPT { + return __const_reference(__first_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word); } - _LIBCPP_HIDE_FROM_ABI iterator __make_iter(size_t __pos) _NOEXCEPT { - return iterator(__first_ + __pos / __bits_per_word, __pos % __bits_per_word); + _LIBCPP_HIDE_FROM_ABI __iterator __make_iter(size_t __pos) _NOEXCEPT { + return __iterator(__first_ + __pos / __bits_per_word, __pos % __bits_per_word); } - _LIBCPP_HIDE_FROM_ABI const_iterator __make_iter(size_t __pos) const _NOEXCEPT { - return const_iterator(__first_ + __pos / __bits_per_word, __pos % __bits_per_word); + _LIBCPP_HIDE_FROM_ABI __const_iterator __make_iter(size_t __pos) const _NOEXCEPT { + return __const_iterator(__first_ + __pos / __bits_per_word, __pos % __bits_per_word); } _LIBCPP_HIDE_FROM_ABI void operator&=(const __bitset& __v) _NOEXCEPT; @@ -302,8 +302,8 @@ _LIBCPP_HIDE_FROM_ABI void __bitset<_N_words, _Size>::flip() _NOEXCEPT { template <size_t _N_words, size_t _Size> _LIBCPP_HIDE_FROM_ABI unsigned long __bitset<_N_words, _Size>::to_ulong(false_type) const { - const_iterator __e = __make_iter(_Size); - const_iterator __i = std::find(__make_iter(sizeof(unsigned long) * CHAR_BIT), __e, true); + __const_iterator __e = __make_iter(_Size); + __const_iterator __i = std::find(__make_iter(sizeof(unsigned long) * CHAR_BIT), __e, true); if (__i != __e) __throw_overflow_error("bitset to_ulong overflow error"); @@ -317,8 +317,8 @@ inline _LIBCPP_HIDE_FROM_ABI unsigned long __bitset<_N_words, _Size>::to_ulong(t template <size_t _N_words, size_t _Size> _LIBCPP_HIDE_FROM_ABI unsigned long long __bitset<_N_words, _Size>::to_ullong(false_type) const { - const_iterator __e = __make_iter(_Size); - const_iterator __i = std::find(__make_iter(sizeof(unsigned long long) * CHAR_BIT), __e, true); + __const_iterator __e = __make_iter(_Size); + __const_iterator __i = std::find(__make_iter(sizeof(unsigned long long) * CHAR_BIT), __e, true); if (__i != __e) __throw_overflow_error("bitset to_ullong overflow error"); @@ -410,9 +410,9 @@ protected: __storage_type __first_; typedef __bit_reference<__bitset> reference; - typedef __bit_const_reference<__bitset> const_reference; - typedef __bit_iterator<__bitset, false> iterator; - typedef __bit_iterator<__bitset, true> const_iterator; + typedef __bit_const_reference<__bitset> __const_reference; + typedef __bit_iterator<__bitset, false> __iterator; + typedef __bit_iterator<__bitset, true> __const_iterator; _LIBCPP_HIDE_FROM_ABI __bitset() _NOEXCEPT; _LIBCPP_HIDE_FROM_ABI explicit __bitset(unsigned long long __v) _NOEXCEPT; @@ -420,14 +420,14 @@ protected: _LIBCPP_HIDE_FROM_ABI reference __make_ref(size_t __pos) _NOEXCEPT { return reference(&__first_, __storage_type(1) << __pos); } - _LIBCPP_HIDE_FROM_ABI const_reference __make_ref(size_t __pos) const _NOEXCEPT { - return const_reference(&__first_, __storage_type(1) << __pos); + _LIBCPP_HIDE_FROM_ABI __const_reference __make_ref(size_t __pos) const _NOEXCEPT { + return __const_reference(&__first_, __storage_type(1) << __pos); } - _LIBCPP_HIDE_FROM_ABI iterator __make_iter(size_t __pos) _NOEXCEPT { - return iterator(&__first_ + __pos / __bits_per_word, __pos % __bits_per_word); + _LIBCPP_HIDE_FROM_ABI __iterator __make_iter(size_t __pos) _NOEXCEPT { + return __iterator(&__first_ + __pos / __bits_per_word, __pos % __bits_per_word); } - _LIBCPP_HIDE_FROM_ABI const_iterator __make_iter(size_t __pos) const _NOEXCEPT { - return const_iterator(&__first_ + __pos / __bits_per_word, __pos % __bits_per_word); + _LIBCPP_HIDE_FROM_ABI __const_iterator __make_iter(size_t __pos) const _NOEXCEPT { + return __const_iterator(&__first_ + __pos / __bits_per_word, __pos % __bits_per_word); } _LIBCPP_HIDE_FROM_ABI void operator&=(const __bitset& __v) _NOEXCEPT; @@ -522,17 +522,17 @@ protected: friend struct __bit_array<__bitset>; typedef __bit_reference<__bitset> reference; - typedef __bit_const_reference<__bitset> const_reference; - typedef __bit_iterator<__bitset, false> iterator; - typedef __bit_iterator<__bitset, true> const_iterator; + typedef __bit_const_reference<__bitset> __const_reference; + typedef __bit_iterator<__bitset, false> __iterator; + typedef __bit_iterator<__bitset, true> __const_iterator; _LIBCPP_HIDE_FROM_ABI __bitset() _NOEXCEPT; _LIBCPP_HIDE_FROM_ABI explicit __bitset(unsigned long long) _NOEXCEPT; _LIBCPP_HIDE_FROM_ABI reference __make_ref(size_t) _NOEXCEPT { return reference(nullptr, 1); } - _LIBCPP_HIDE_FROM_ABI const_reference __make_ref(size_t) const _NOEXCEPT { return const_reference(nullptr, 1); } - _LIBCPP_HIDE_FROM_ABI iterator __make_iter(size_t) _NOEXCEPT { return iterator(nullptr, 0); } - _LIBCPP_HIDE_FROM_ABI const_iterator __make_iter(size_t) const _NOEXCEPT { return const_iterator(nullptr, 0); } + _LIBCPP_HIDE_FROM_ABI __const_reference __make_ref(size_t) const _NOEXCEPT { return __const_reference(nullptr, 1); } + _LIBCPP_HIDE_FROM_ABI __iterator __make_iter(size_t) _NOEXCEPT { return __iterator(nullptr, 0); } + _LIBCPP_HIDE_FROM_ABI __const_iterator __make_iter(size_t) const _NOEXCEPT { return __const_iterator(nullptr, 0); } _LIBCPP_HIDE_FROM_ABI void operator&=(const __bitset&) _NOEXCEPT {} _LIBCPP_HIDE_FROM_ABI void operator|=(const __bitset&) _NOEXCEPT {} @@ -563,15 +563,15 @@ class _LIBCPP_TEMPLATE_VIS bitset : private __bitset<_Size == 0 ? 0 : (_Size - 1) / (sizeof(size_t) * CHAR_BIT) + 1, _Size> { public: static const unsigned __n_words = _Size == 0 ? 0 : (_Size - 1) / (sizeof(size_t) * CHAR_BIT) + 1; - typedef __bitset<__n_words, _Size> base; + typedef __bitset<__n_words, _Size> __base; public: - typedef typename base::reference reference; - typedef typename base::const_reference const_reference; + typedef typename __base::reference reference; + typedef typename __base::__const_reference __const_reference; // 23.3.5.1 constructors: _LIBCPP_HIDE_FROM_ABI bitset() _NOEXCEPT {} - _LIBCPP_HIDE_FROM_ABI bitset(unsigned long long __v) _NOEXCEPT : base(__v) {} + _LIBCPP_HIDE_FROM_ABI bitset(unsigned long long __v) _NOEXCEPT : __base(__v) {} template <class _CharT, __enable_if_t<_IsCharLikeType<_CharT>::value, int> = 0> _LIBCPP_HIDE_FROM_ABI explicit bitset( const _CharT* __str, @@ -613,11 +613,11 @@ public: // element access: #ifdef _LIBCPP_ABI_BITSET_VECTOR_BOOL_CONST_SUBSCRIPT_RETURN_BOOL - _LIBCPP_HIDE_FROM_ABI bool operator[](size_t __p) const { return base::__make_ref(__p); } + _LIBCPP_HIDE_FROM_ABI bool operator[](size_t __p) const { return __base::__make_ref(__p); } #else - _LIBCPP_HIDE_FROM_ABI const_reference operator[](size_t __p) const { return base::__make_ref(__p); } + _LIBCPP_HIDE_FROM_ABI __const_reference operator[](size_t __p) const { return __base::__make_ref(__p); } #endif - _LIBCPP_HIDE_FROM_ABI reference operator[](size_t __p) { return base::__make_ref(__p); } + _LIBCPP_HIDE_FROM_ABI reference operator[](size_t __p) { return __base::__make_ref(__p); } _LIBCPP_HIDE_FROM_ABI unsigned long to_ulong() const; _LIBCPP_HIDE_FROM_ABI unsigned long long to_ullong() const; template <class _CharT, class _Traits, class _Allocator> @@ -656,51 +656,51 @@ private: _CharT __c = __str[__mp - 1 - __i]; (*this)[__i] = _Traits::eq(__c, __one); } - std::fill(base::__make_iter(__i), base::__make_iter(_Size), false); + std::fill(__base::__make_iter(__i), __base::__make_iter(_Size), false); } - _LIBCPP_HIDE_FROM_ABI size_t __hash_code() const _NOEXCEPT { return base::__hash_code(); } + _LIBCPP_HIDE_FROM_ABI size_t __hash_code() const _NOEXCEPT { return __base::__hash_code(); } friend struct hash<bitset>; }; template <size_t _Size> inline _LIBCPP_HIDE_FROM_ABI bitset<_Size>& bitset<_Size>::operator&=(const bitset& __rhs) _NOEXCEPT { - base::operator&=(__rhs); + __base::operator&=(__rhs); return *this; } template <size_t _Size> inline _LIBCPP_HIDE_FROM_ABI bitset<_Size>& bitset<_Size>::operator|=(const bitset& __rhs) _NOEXCEPT { - base::operator|=(__rhs); + __base::operator|=(__rhs); return *this; } template <size_t _Size> inline _LIBCPP_HIDE_FROM_ABI bitset<_Size>& bitset<_Size>::operator^=(const bitset& __rhs) _NOEXCEPT { - base::operator^=(__rhs); + __base::operator^=(__rhs); return *this; } template <size_t _Size> _LIBCPP_HIDE_FROM_ABI bitset<_Size>& bitset<_Size>::operator<<=(size_t __pos) _NOEXCEPT { __pos = std::min(__pos, _Size); - std::copy_backward(base::__make_iter(0), base::__make_iter(_Size - __pos), base::__make_iter(_Size)); - std::fill_n(base::__make_iter(0), __pos, false); + std::copy_backward(__base::__make_iter(0), __base::__make_iter(_Size - __pos), __base::__make_iter(_Size)); + std::fill_n(__base::__make_iter(0), __pos, false); return *this; } template <size_t _Size> _LIBCPP_HIDE_FROM_ABI bitset<_Size>& bitset<_Size>::operator>>=(size_t __pos) _NOEXCEPT { __pos = std::min(__pos, _Size); - std::copy(base::__make_iter(__pos), base::__make_iter(_Size), base::__make_iter(0)); - std::fill_n(base::__make_iter(_Size - __pos), __pos, false); + std::copy(__base::__make_iter(__pos), __base::__make_iter(_Size), __base::__make_iter(0)); + std::fill_n(__base::__make_iter(_Size - __pos), __pos, false); return *this; } template <size_t _Size> inline _LIBCPP_HIDE_FROM_ABI bitset<_Size>& bitset<_Size>::set() _NOEXCEPT { - std::fill_n(base::__make_iter(0), _Size, true); + std::fill_n(__base::__make_iter(0), _Size, true); return *this; } @@ -715,7 +715,7 @@ _LIBCPP_HIDE_FROM_ABI bitset<_Size>& bitset<_Size>::set(size_t __pos, bool __val template <size_t _Size> inline _LIBCPP_HIDE_FROM_ABI bitset<_Size>& bitset<_Size>::reset() _NOEXCEPT { - std::fill_n(base::__make_iter(0), _Size, false); + std::fill_n(__base::__make_iter(0), _Size, false); return *this; } @@ -737,7 +737,7 @@ inline _LIBCPP_HIDE_FROM_ABI bitset<_Size> bitset<_Size>::operator~() const _NOE template <size_t _Size> inline _LIBCPP_HIDE_FROM_ABI bitset<_Size>& bitset<_Size>::flip() _NOEXCEPT { - base::flip(); + __base::flip(); return *this; } @@ -746,19 +746,19 @@ _LIBCPP_HIDE_FROM_ABI bitset<_Size>& bitset<_Size>::flip(size_t __pos) { if (__pos >= _Size) __throw_out_of_range("bitset flip argument out of range"); - reference __r = base::__make_ref(__pos); + reference __r = __base::__make_ref(__pos); __r = ~__r; return *this; } template <size_t _Size> inline _LIBCPP_HIDE_FROM_ABI unsigned long bitset<_Size>::to_ulong() const { - return base::to_ulong(); + return __base::to_ulong(); } template <size_t _Size> inline _LIBCPP_HIDE_FROM_ABI unsigned long long bitset<_Size>::to_ullong() const { - return base::to_ullong(); + return __base::to_ullong(); } template <size_t _Size> @@ -795,12 +795,12 @@ bitset<_Size>::to_string(char __zero, char __one) const { template <size_t _Size> inline _LIBCPP_HIDE_FROM_ABI size_t bitset<_Size>::count() const _NOEXCEPT { - return static_cast<size_t>(std::count(base::__make_iter(0), base::__make_iter(_Size), true)); + return static_cast<size_t>(std::count(__base::__make_iter(0), __base::__make_iter(_Size), true)); } template <size_t _Size> inline _LIBCPP_HIDE_FROM_ABI bool bitset<_Size>::operator==(const bitset& __rhs) const _NOEXCEPT { - return std::equal(base::__make_iter(0), base::__make_iter(_Size), __rhs.__make_iter(0)); + return std::equal(__base::__make_iter(0), __base::__make_iter(_Size), __rhs.__make_iter(0)); } template <size_t _Size> @@ -818,12 +818,12 @@ _LIBCPP_HIDE_FROM_ABI bool bitset<_Size>::test(size_t __pos) const { template <size_t _Size> inline _LIBCPP_HIDE_FROM_ABI bool bitset<_Size>::all() const _NOEXCEPT { - return base::all(); + return __base::all(); } template <size_t _Size> inline _LIBCPP_HIDE_FROM_ABI bool bitset<_Size>::any() const _NOEXCEPT { - return base::any(); + return __base::any(); } template <size_t _Size> diff --git a/libcxx/include/__cxx03/forward_list b/libcxx/include/__cxx03/forward_list index 8a8b5f289e38..da7d9f18f0bc 100644 --- a/libcxx/include/__cxx03/forward_list +++ b/libcxx/include/__cxx03/forward_list @@ -572,12 +572,12 @@ void __forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT { template <class _Tp, class _Alloc /*= allocator<_Tp>*/> class _LIBCPP_TEMPLATE_VIS forward_list : private __forward_list_base<_Tp, _Alloc> { - typedef __forward_list_base<_Tp, _Alloc> base; - typedef typename base::__node_allocator __node_allocator; - typedef typename base::__node_type __node_type; - typedef typename base::__node_traits __node_traits; - typedef typename base::__node_pointer __node_pointer; - typedef typename base::__begin_node_pointer __begin_node_pointer; + typedef __forward_list_base<_Tp, _Alloc> __base; + typedef typename __base::__node_allocator __node_allocator; + typedef typename __base::__node_type __node_type; + typedef typename __base::__node_traits __node_traits; + typedef typename __base::__node_pointer __node_pointer; + typedef typename __base::__begin_node_pointer __begin_node_pointer; public: typedef _Tp value_type; @@ -598,8 +598,8 @@ public: typedef typename allocator_traits<allocator_type>::size_type size_type; typedef typename allocator_traits<allocator_type>::difference_type difference_type; - typedef typename base::iterator iterator; - typedef typename base::const_iterator const_iterator; + typedef typename __base::iterator iterator; + typedef typename __base::const_iterator const_iterator; typedef void __remove_return_type; _LIBCPP_HIDE_FROM_ABI forward_list() {} // = default; @@ -608,7 +608,7 @@ public: _LIBCPP_HIDE_FROM_ABI forward_list(size_type __n, const value_type& __v); template <__enable_if_t<__is_allocator<_Alloc>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI forward_list(size_type __n, const value_type& __v, const allocator_type& __a) : base(__a) { + _LIBCPP_HIDE_FROM_ABI forward_list(size_type __n, const value_type& __v, const allocator_type& __a) : __base(__a) { insert_after(cbefore_begin(), __n, __v); } @@ -630,35 +630,37 @@ public: _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const value_type& __v); - _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(base::__alloc()); } + _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(__base::__alloc()); } - _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return iterator(base::__before_begin()->__next_); } + _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return iterator(__base::__before_begin()->__next_); } _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { - return const_iterator(base::__before_begin()->__next_); + return const_iterator(__base::__before_begin()->__next_); } _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return iterator(nullptr); } _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return const_iterator(nullptr); } _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { - return const_iterator(base::__before_begin()->__next_); + return const_iterator(__base::__before_begin()->__next_); } _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return const_iterator(nullptr); } - _LIBCPP_HIDE_FROM_ABI iterator before_begin() _NOEXCEPT { return iterator(base::__before_begin()); } - _LIBCPP_HIDE_FROM_ABI const_iterator before_begin() const _NOEXCEPT { return const_iterator(base::__before_begin()); } + _LIBCPP_HIDE_FROM_ABI iterator before_begin() _NOEXCEPT { return iterator(__base::__before_begin()); } + _LIBCPP_HIDE_FROM_ABI const_iterator before_begin() const _NOEXCEPT { + return const_iterator(__base::__before_begin()); + } _LIBCPP_HIDE_FROM_ABI const_iterator cbefore_begin() const _NOEXCEPT { - return const_iterator(base::__before_begin()); + return const_iterator(__base::__before_begin()); } _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { - return base::__before_begin()->__next_ == nullptr; + return __base::__before_begin()->__next_ == nullptr; } _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { - return std::min<size_type>(__node_traits::max_size(base::__alloc()), numeric_limits<difference_type>::max()); + return std::min<size_type>(__node_traits::max_size(__base::__alloc()), numeric_limits<difference_type>::max()); } - _LIBCPP_HIDE_FROM_ABI reference front() { return base::__before_begin()->__next_->__get_value(); } - _LIBCPP_HIDE_FROM_ABI const_reference front() const { return base::__before_begin()->__next_->__get_value(); } + _LIBCPP_HIDE_FROM_ABI reference front() { return __base::__before_begin()->__next_->__get_value(); } + _LIBCPP_HIDE_FROM_ABI const_reference front() const { return __base::__before_begin()->__next_->__get_value(); } _LIBCPP_HIDE_FROM_ABI void push_front(const value_type& __v); @@ -675,11 +677,11 @@ public: _LIBCPP_HIDE_FROM_ABI iterator erase_after(const_iterator __p); _LIBCPP_HIDE_FROM_ABI iterator erase_after(const_iterator __f, const_iterator __l); - _LIBCPP_HIDE_FROM_ABI void swap(forward_list& __x) { base::swap(__x); } + _LIBCPP_HIDE_FROM_ABI void swap(forward_list& __x) { __base::swap(__x); } _LIBCPP_HIDE_FROM_ABI void resize(size_type __n); _LIBCPP_HIDE_FROM_ABI void resize(size_type __n, const value_type& __v); - _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { base::clear(); } + _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __base::clear(); } _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list&& __x); _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i); @@ -716,12 +718,12 @@ private: }; template <class _Tp, class _Alloc> -inline forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a) : base(__a) {} +inline forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a) : __base(__a) {} template <class _Tp, class _Alloc> forward_list<_Tp, _Alloc>::forward_list(size_type __n) { if (__n > 0) { - for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n, __p = __p->__next_as_begin()) { + for (__begin_node_pointer __p = __base::__before_begin(); __n > 0; --__n, __p = __p->__next_as_begin()) { __p->__next_ = this->__create_node(/* next = */ nullptr); } } @@ -740,26 +742,27 @@ forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l) template <class _Tp, class _Alloc> template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> > -forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, const allocator_type& __a) : base(__a) { +forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, const allocator_type& __a) + : __base(__a) { insert_after(cbefore_begin(), __f, __l); } template <class _Tp, class _Alloc> forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x) - : base(__node_traits::select_on_container_copy_construction(__x.__alloc())) { + : __base(__node_traits::select_on_container_copy_construction(__x.__alloc())) { insert_after(cbefore_begin(), __x.begin(), __x.end()); } template <class _Tp, class _Alloc> forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x, const __type_identity_t<allocator_type>& __a) - : base(__a) { + : __base(__a) { insert_after(cbefore_begin(), __x.begin(), __x.end()); } template <class _Tp, class _Alloc> forward_list<_Tp, _Alloc>& forward_list<_Tp, _Alloc>::operator=(const forward_list& __x) { if (this != std::addressof(__x)) { - base::__copy_assign_alloc(__x); + __base::__copy_assign_alloc(__x); assign(__x.begin(), __x.end()); } return *this; @@ -800,13 +803,13 @@ void forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v) { template <class _Tp, class _Alloc> void forward_list<_Tp, _Alloc>::push_front(const value_type& __v) { - base::__before_begin()->__next_ = this->__create_node(/* next = */ base::__before_begin()->__next_, __v); + __base::__before_begin()->__next_ = this->__create_node(/* next = */ __base::__before_begin()->__next_, __v); } template <class _Tp, class _Alloc> void forward_list<_Tp, _Alloc>::pop_front() { - __node_pointer __p = base::__before_begin()->__next_; - base::__before_begin()->__next_ = __p->__next_; + __node_pointer __p = __base::__before_begin()->__next_; + __base::__before_begin()->__next_ = __p->__next_; this->__delete_node(__p); } @@ -1082,8 +1085,9 @@ template <class _Tp, class _Alloc> template <class _Compare> void forward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp) { if (this != std::addressof(__x)) { - base::__before_begin()->__next_ = __merge(base::__before_begin()->__next_, __x.__before_begin()->__next_, __comp); - __x.__before_begin()->__next_ = nullptr; + __base::__before_begin()->__next_ = + __merge(__base::__before_begin()->__next_, __x.__before_begin()->__next_, __comp); + __x.__before_begin()->__next_ = nullptr; } } @@ -1127,7 +1131,7 @@ forward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2, _Co template <class _Tp, class _Alloc> template <class _Compare> inline void forward_list<_Tp, _Alloc>::sort(_Compare __comp) { - base::__before_begin()->__next_ = __sort(base::__before_begin()->__next_, std::distance(begin(), end()), __comp); + __base::__before_begin()->__next_ = __sort(__base::__before_begin()->__next_, std::distance(begin(), end()), __comp); } template <class _Tp, class _Alloc> @@ -1157,7 +1161,7 @@ forward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz, _Co template <class _Tp, class _Alloc> void forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT { - __node_pointer __p = base::__before_begin()->__next_; + __node_pointer __p = __base::__before_begin()->__next_; if (__p != nullptr) { __node_pointer __f = __p->__next_; __p->__next_ = nullptr; @@ -1167,7 +1171,7 @@ void forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT { __p = __f; __f = __t; } - base::__before_begin()->__next_ = __p; + __base::__before_begin()->__next_ = __p; } } diff --git a/libcxx/include/__cxx03/list b/libcxx/include/__cxx03/list index f863885fbcf9..25aff2f5ebb2 100644 --- a/libcxx/include/__cxx03/list +++ b/libcxx/include/__cxx03/list @@ -612,14 +612,14 @@ void __list_imp<_Tp, _Alloc>::swap(__list_imp& __c) { template <class _Tp, class _Alloc /*= allocator<_Tp>*/> class _LIBCPP_TEMPLATE_VIS list : private __list_imp<_Tp, _Alloc> { - typedef __list_imp<_Tp, _Alloc> base; - typedef typename base::__node_type __node_type; - typedef typename base::__node_allocator __node_allocator; - typedef typename base::__node_pointer __node_pointer; - typedef typename base::__node_alloc_traits __node_alloc_traits; - typedef typename base::__node_base __node_base; - typedef typename base::__node_base_pointer __node_base_pointer; - typedef typename base::__link_pointer __link_pointer; + typedef __list_imp<_Tp, _Alloc> __base; + typedef typename __base::__node_type __node_type; + typedef typename __base::__node_allocator __node_allocator; + typedef typename __base::__node_pointer __node_pointer; + typedef typename __base::__node_alloc_traits __node_alloc_traits; + typedef typename __base::__node_base __node_base; + typedef typename __base::__node_base_pointer __node_base_pointer; + typedef typename __base::__link_pointer __link_pointer; public: typedef _Tp value_type; @@ -629,22 +629,22 @@ public: "Allocator::value_type must be same type as value_type"); typedef value_type& reference; typedef const value_type& const_reference; - typedef typename base::pointer pointer; - typedef typename base::const_pointer const_pointer; - typedef typename base::size_type size_type; - typedef typename base::difference_type difference_type; - typedef typename base::iterator iterator; - typedef typename base::const_iterator const_iterator; + typedef typename __base::pointer pointer; + typedef typename __base::const_pointer const_pointer; + typedef typename __base::size_type size_type; + typedef typename __base::difference_type difference_type; + typedef typename __base::iterator iterator; + typedef typename __base::const_iterator const_iterator; typedef std::reverse_iterator<iterator> reverse_iterator; typedef std::reverse_iterator<const_iterator> const_reverse_iterator; typedef void __remove_return_type; _LIBCPP_HIDE_FROM_ABI list() {} - _LIBCPP_HIDE_FROM_ABI explicit list(const allocator_type& __a) : base(__a) {} + _LIBCPP_HIDE_FROM_ABI explicit list(const allocator_type& __a) : __base(__a) {} _LIBCPP_HIDE_FROM_ABI explicit list(size_type __n); _LIBCPP_HIDE_FROM_ABI list(size_type __n, const value_type& __x); template <__enable_if_t<__is_allocator<_Alloc>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI list(size_type __n, const value_type& __x, const allocator_type& __a) : base(__a) { + _LIBCPP_HIDE_FROM_ABI list(size_type __n, const value_type& __x, const allocator_type& __a) : __base(__a) { for (; __n > 0; --__n) push_back(__x); } @@ -666,18 +666,18 @@ public: _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT; - _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return base::__sz(); } - _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return base::empty(); } + _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __base::__sz(); } + _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __base::empty(); } _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { - return std::min<size_type>(base::__node_alloc_max_size(), numeric_limits<difference_type >::max()); + return std::min<size_type>(__base::__node_alloc_max_size(), numeric_limits<difference_type >::max()); } - _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return base::begin(); } - _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return base::begin(); } - _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return base::end(); } - _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return base::end(); } - _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return base::begin(); } - _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return base::end(); } + _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __base::begin(); } + _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __base::begin(); } + _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __base::end(); } + _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __base::end(); } + _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __base::begin(); } + _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __base::end(); } _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); } _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); } @@ -688,19 +688,19 @@ public: _LIBCPP_HIDE_FROM_ABI reference front() { _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::front called on empty list"); - return base::__end_.__next_->__as_node()->__get_value(); + return __base::__end_.__next_->__as_node()->__get_value(); } _LIBCPP_HIDE_FROM_ABI const_reference front() const { _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::front called on empty list"); - return base::__end_.__next_->__as_node()->__get_value(); + return __base::__end_.__next_->__as_node()->__get_value(); } _LIBCPP_HIDE_FROM_ABI reference back() { _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::back called on empty list"); - return base::__end_.__prev_->__as_node()->__get_value(); + return __base::__end_.__prev_->__as_node()->__get_value(); } _LIBCPP_HIDE_FROM_ABI const_reference back() const { _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::back called on empty list"); - return base::__end_.__prev_->__as_node()->__get_value(); + return __base::__end_.__prev_->__as_node()->__get_value(); } _LIBCPP_HIDE_FROM_ABI void push_front(const value_type& __x); @@ -714,8 +714,8 @@ public: template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> = 0> _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _InpIter __f, _InpIter __l); - _LIBCPP_HIDE_FROM_ABI void swap(list& __c) { base::swap(__c); } - _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { base::clear(); } + _LIBCPP_HIDE_FROM_ABI void swap(list& __c) { __base::swap(__c); } + _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __base::clear(); } _LIBCPP_HIDE_FROM_ABI void pop_front(); _LIBCPP_HIDE_FROM_ABI void pop_back(); @@ -779,24 +779,24 @@ inline void list<_Tp, _Alloc>::__link_nodes(__link_pointer __p, __link_pointer _ // Link in nodes [__f, __l] at the front of the list template <class _Tp, class _Alloc> inline void list<_Tp, _Alloc>::__link_nodes_at_front(__link_pointer __f, __link_pointer __l) { - __f->__prev_ = base::__end_as_link(); - __l->__next_ = base::__end_.__next_; - __l->__next_->__prev_ = __l; - base::__end_.__next_ = __f; + __f->__prev_ = __base::__end_as_link(); + __l->__next_ = __base::__end_.__next_; + __l->__next_->__prev_ = __l; + __base::__end_.__next_ = __f; } // Link in nodes [__f, __l] at the back of the list template <class _Tp, class _Alloc> inline void list<_Tp, _Alloc>::__link_nodes_at_back(__link_pointer __f, __link_pointer __l) { - __l->__next_ = base::__end_as_link(); - __f->__prev_ = base::__end_.__prev_; - __f->__prev_->__next_ = __f; - base::__end_.__prev_ = __l; + __l->__next_ = __base::__end_as_link(); + __f->__prev_ = __base::__end_.__prev_; + __f->__prev_->__next_ = __f; + __base::__end_.__prev_ = __l; } template <class _Tp, class _Alloc> inline typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::__iterator(size_type __n) { - return __n <= base::__sz() / 2 ? std::next(begin(), __n) : std::prev(end(), base::__sz() - __n); + return __n <= __base::__sz() / 2 ? std::next(begin(), __n) : std::prev(end(), __base::__sz() - __n); } template <class _Tp, class _Alloc> @@ -820,20 +820,20 @@ list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l) { template <class _Tp, class _Alloc> template <class _InpIter, __enable_if_t<__has_input_iterator_category<_InpIter>::value, int> > -list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a) : base(__a) { +list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a) : __base(__a) { for (; __f != __l; ++__f) __emplace_back(*__f); } template <class _Tp, class _Alloc> list<_Tp, _Alloc>::list(const list& __c) - : base(__node_alloc_traits::select_on_container_copy_construction(__c.__node_alloc())) { + : __base(__node_alloc_traits::select_on_container_copy_construction(__c.__node_alloc())) { for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i) push_back(*__i); } template <class _Tp, class _Alloc> -list<_Tp, _Alloc>::list(const list& __c, const __type_identity_t<allocator_type>& __a) : base(__a) { +list<_Tp, _Alloc>::list(const list& __c, const __type_identity_t<allocator_type>& __a) : __base(__a) { for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i) push_back(*__i); } @@ -841,7 +841,7 @@ list<_Tp, _Alloc>::list(const list& __c, const __type_identity_t<allocator_type> template <class _Tp, class _Alloc> inline list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(const list& __c) { if (this != std::addressof(__c)) { - base::__copy_assign_alloc(__c); + __base::__copy_assign_alloc(__c); assign(__c.begin(), __c.end()); } return *this; @@ -880,14 +880,14 @@ void list<_Tp, _Alloc>::assign(size_type __n, const value_type& __x) { template <class _Tp, class _Alloc> inline _Alloc list<_Tp, _Alloc>::get_allocator() const _NOEXCEPT { - return allocator_type(base::__node_alloc()); + return allocator_type(__base::__node_alloc()); } template <class _Tp, class _Alloc> typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x) { __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, __x); __link_nodes(__p.__ptr_, __node->__as_link(), __node->__as_link()); - ++base::__sz(); + ++__base::__sz(); return iterator(__node->__as_link()); } @@ -921,7 +921,7 @@ list<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& _ } #endif // _LIBCPP_HAS_NO_EXCEPTIONS __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_); - base::__sz() += __ds; + __base::__sz() += __ds; } return __r; } @@ -963,7 +963,7 @@ list<_Tp, _Alloc>::__insert_with_sentinel(const_iterator __p, _Iterator __f, _Se } #endif // _LIBCPP_HAS_NO_EXCEPTIONS __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_); - base::__sz() += __ds; + __base::__sz() += __ds; } return __r; } @@ -973,7 +973,7 @@ void list<_Tp, _Alloc>::push_front(const value_type& __x) { __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, __x); __link_pointer __nl = __node->__as_link(); __link_nodes_at_front(__nl, __nl); - ++base::__sz(); + ++__base::__sz(); } template <class _Tp, class _Alloc> @@ -981,24 +981,24 @@ void list<_Tp, _Alloc>::push_back(const value_type& __x) { __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, __x); __link_pointer __nl = __node->__as_link(); __link_nodes_at_back(__nl, __nl); - ++base::__sz(); + ++__base::__sz(); } template <class _Tp, class _Alloc> void list<_Tp, _Alloc>::pop_front() { _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::pop_front() called with empty list"); - __link_pointer __n = base::__end_.__next_; - base::__unlink_nodes(__n, __n); - --base::__sz(); + __link_pointer __n = __base::__end_.__next_; + __base::__unlink_nodes(__n, __n); + --__base::__sz(); this->__delete_node(__n->__as_node()); } template <class _Tp, class _Alloc> void list<_Tp, _Alloc>::pop_back() { _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "list::pop_back() called on an empty list"); - __link_pointer __n = base::__end_.__prev_; - base::__unlink_nodes(__n, __n); - --base::__sz(); + __link_pointer __n = __base::__end_.__prev_; + __base::__unlink_nodes(__n, __n); + --__base::__sz(); this->__delete_node(__n->__as_node()); } @@ -1007,8 +1007,8 @@ typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::erase(const_iterator __p _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__p != end(), "list::erase(iterator) called with a non-dereferenceable iterator"); __link_pointer __n = __p.__ptr_; __link_pointer __r = __n->__next_; - base::__unlink_nodes(__n, __n); - --base::__sz(); + __base::__unlink_nodes(__n, __n); + --__base::__sz(); this->__delete_node(__n->__as_node()); return iterator(__r); } @@ -1016,11 +1016,11 @@ typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::erase(const_iterator __p template <class _Tp, class _Alloc> typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l) { if (__f != __l) { - base::__unlink_nodes(__f.__ptr_, __l.__ptr_->__prev_); + __base::__unlink_nodes(__f.__ptr_, __l.__ptr_->__prev_); while (__f != __l) { __link_pointer __n = __f.__ptr_; ++__f; - --base::__sz(); + --__base::__sz(); this->__delete_node(__n->__as_node()); } } @@ -1029,10 +1029,10 @@ typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::erase(const_iterator __f template <class _Tp, class _Alloc> void list<_Tp, _Alloc>::resize(size_type __n) { - if (__n < base::__sz()) + if (__n < __base::__sz()) erase(__iterator(__n), end()); - else if (__n > base::__sz()) { - __n -= base::__sz(); + else if (__n > __base::__sz()) { + __n -= __base::__sz(); size_type __ds = 0; __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr); ++__ds; @@ -1058,16 +1058,16 @@ void list<_Tp, _Alloc>::resize(size_type __n) { } #endif // _LIBCPP_HAS_NO_EXCEPTIONS __link_nodes_at_back(__r.__ptr_, __e.__ptr_); - base::__sz() += __ds; + __base::__sz() += __ds; } } template <class _Tp, class _Alloc> void list<_Tp, _Alloc>::resize(size_type __n, const value_type& __x) { - if (__n < base::__sz()) + if (__n < __base::__sz()) erase(__iterator(__n), end()); - else if (__n > base::__sz()) { - __n -= base::__sz(); + else if (__n > __base::__sz()) { + __n -= __base::__sz(); size_type __ds = 0; __node_pointer __node = this->__create_node(/* prev = */ nullptr, /* next = */ nullptr, __x); ++__ds; @@ -1093,8 +1093,8 @@ void list<_Tp, _Alloc>::resize(size_type __n, const value_type& __x) { throw; } #endif // _LIBCPP_HAS_NO_EXCEPTIONS - __link_nodes(base::__end_as_link(), __r.__ptr_, __e.__ptr_); - base::__sz() += __ds; + __link_nodes(__base::__end_as_link(), __r.__ptr_, __e.__ptr_); + __base::__sz() += __ds; } } @@ -1105,9 +1105,9 @@ void list<_Tp, _Alloc>::splice(const_iterator __p, list& __c) { if (!__c.empty()) { __link_pointer __f = __c.__end_.__next_; __link_pointer __l = __c.__end_.__prev_; - base::__unlink_nodes(__f, __l); + __base::__unlink_nodes(__f, __l); __link_nodes(__p.__ptr_, __f, __l); - base::__sz() += __c.__sz(); + __base::__sz() += __c.__sz(); __c.__sz() = 0; } } @@ -1116,10 +1116,10 @@ template <class _Tp, class _Alloc> void list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __i) { if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_) { __link_pointer __f = __i.__ptr_; - base::__unlink_nodes(__f, __f); + __base::__unlink_nodes(__f, __f); __link_nodes(__p.__ptr_, __f, __f); --__c.__sz(); - ++base::__sz(); + ++__base::__sz(); } } @@ -1132,9 +1132,9 @@ void list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f if (this != std::addressof(__c)) { size_type __s = std::distance(__f, __l) + 1; __c.__sz() -= __s; - base::__sz() += __s; + __base::__sz() += __s; } - base::__unlink_nodes(__first, __last); + __base::__unlink_nodes(__first, __last); __link_nodes(__p.__ptr_, __first, __last); } } @@ -1214,12 +1214,12 @@ void list<_Tp, _Alloc>::merge(list& __c, _Comp __comp) { iterator __m2 = std::next(__f2); for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2, (void)++__ds) ; - base::__sz() += __ds; + __base::__sz() += __ds; __c.__sz() -= __ds; __link_pointer __f = __f2.__ptr_; __link_pointer __l = __m2.__ptr_->__prev_; __f2 = __m2; - base::__unlink_nodes(__f, __l); + __base::__unlink_nodes(__f, __l); __m2 = std::next(__f1); __link_nodes(__f1.__ptr_, __f, __l); __f1 = __m2; @@ -1238,7 +1238,7 @@ inline void list<_Tp, _Alloc>::sort() { template <class _Tp, class _Alloc> template <class _Comp> inline void list<_Tp, _Alloc>::sort(_Comp __comp) { - __sort(begin(), end(), base::__sz(), __comp); + __sort(begin(), end(), __base::__sz(), __comp); } template <class _Tp, class _Alloc> @@ -1252,7 +1252,7 @@ list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __ case 2: if (__comp(*--__e2, *__f1)) { __link_pointer __f = __e2.__ptr_; - base::__unlink_nodes(__f, __f); + __base::__unlink_nodes(__f, __f); __link_nodes(__f1.__ptr_, __f, __f); return __e2; } @@ -1270,7 +1270,7 @@ list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __ __link_pointer __l = __m2.__ptr_->__prev_; __r = __f2; __e1 = __f2 = __m2; - base::__unlink_nodes(__f, __l); + __base::__unlink_nodes(__f, __l); __m2 = std::next(__f1); __link_nodes(__f1.__ptr_, __f, __l); __f1 = __m2; @@ -1286,7 +1286,7 @@ list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __ if (__e1 == __f2) __e1 = __m2; __f2 = __m2; - base::__unlink_nodes(__f, __l); + __base::__unlink_nodes(__f, __l); __m2 = std::next(__f1); __link_nodes(__f1.__ptr_, __f, __l); __f1 = __m2; @@ -1298,7 +1298,7 @@ list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __ template <class _Tp, class _Alloc> void list<_Tp, _Alloc>::reverse() _NOEXCEPT { - if (base::__sz() > 1) { + if (__base::__sz() > 1) { iterator __e = end(); for (iterator __i = begin(); __i.__ptr_ != __e.__ptr_;) { std::swap(__i.__ptr_->__prev_, __i.__ptr_->__next_); diff --git a/libcxx/include/__cxx03/locale b/libcxx/include/__cxx03/locale index 64162f5a4ff2..57267ab39022 100644 --- a/libcxx/include/__cxx03/locale +++ b/libcxx/include/__cxx03/locale @@ -2460,6 +2460,8 @@ _LIBCPP_HIDE_FROM_ABI void __double_or_nothing(unique_ptr<_Tp, void (*)(void*)>& __throw_bad_alloc(); if (__owns) __b.release(); + else + std::memcpy(__t, __b.get(), __cur_cap); __b = unique_ptr<_Tp, void (*)(void*)>(__t, free); __new_cap /= sizeof(_Tp); __n = __b.get() + __n_off; @@ -2655,20 +2657,22 @@ _InputIterator money_get<_CharT, _InputIterator>::do_get( char_type __atoms[sizeof(__src) - 1]; __ct.widen(__src, __src + (sizeof(__src) - 1), __atoms); char __nbuf[__bz]; - char* __nc = __nbuf; + char* __nc = __nbuf; + const char* __nc_in = __nc; unique_ptr<char, void (*)(void*)> __h(nullptr, free); if (__wn - __wb.get() > __bz - 2) { __h.reset((char*)malloc(static_cast<size_t>(__wn - __wb.get() + 2))); if (__h.get() == nullptr) __throw_bad_alloc(); - __nc = __h.get(); + __nc = __h.get(); + __nc_in = __nc; } if (__neg) *__nc++ = '-'; for (const char_type* __w = __wb.get(); __w < __wn; ++__w, ++__nc) *__nc = __src[std::find(__atoms, std::end(__atoms), *__w) - __atoms]; *__nc = char(); - if (sscanf(__nbuf, "%Lf", &__v) != 1) + if (sscanf(__nc_in, "%Lf", &__v) != 1) __throw_runtime_error("money_get error"); } if (__b == __e) diff --git a/libcxx/include/__cxx03/string b/libcxx/include/__cxx03/string index 7d54030d0b66..178140486105 100644 --- a/libcxx/include/__cxx03/string +++ b/libcxx/include/__cxx03/string @@ -1101,12 +1101,20 @@ public: _LIBCPP_HIDE_FROM_ABI size_type length() const _NOEXCEPT { return size(); } _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { - size_type __m = __alloc_traits::max_size(__alloc()); - if (__m <= std::numeric_limits<size_type>::max() / 2) { - return __m - __alignment; + if (size_type __m = __alloc_traits::max_size(__alloc()); __m <= std::numeric_limits<size_type>::max() / 2) { + size_type __res = __m - __alignment; + + // When the __endian_factor == 2, our string representation assumes that the capacity + // (including the null terminator) is always even, so we have to make sure the lowest bit isn't set when the + // string grows to max_size() + if (__endian_factor == 2) + __res &= ~size_type(1); + + // We have to allocate space for the null terminator, but max_size() doesn't include it. + return __res - 1; } else { bool __uses_lsb = __endian_factor == 2; - return __uses_lsb ? __m - __alignment : (__m / 2) - __alignment; + return __uses_lsb ? __m - __alignment - 1 : (__m / 2) - __alignment - 1; } } @@ -1970,11 +1978,11 @@ void basic_string<_CharT, _Traits, _Allocator>::__grow_by_and_replace( size_type __n_add, const value_type* __p_new_stuff) { size_type __ms = max_size(); - if (__delta_cap > __ms - __old_cap - 1) + if (__delta_cap > __ms - __old_cap) __throw_length_error(); pointer __old_p = __get_pointer(); size_type __cap = - __old_cap < __ms / 2 - __alignment ? __recommend(std::max(__old_cap + __delta_cap, 2 * __old_cap)) : __ms - 1; + __old_cap < __ms / 2 - __alignment ? __recommend(std::max(__old_cap + __delta_cap, 2 * __old_cap)) : __ms; __annotate_delete(); auto __allocation = std::__allocate_at_least(__alloc(), __cap + 1); pointer __p = __allocation.ptr; @@ -2017,7 +2025,7 @@ void __throw_length_error(); pointer __old_p = __get_pointer(); size_type __cap = - __old_cap < __ms / 2 - __alignment ? __recommend(std::max(__old_cap + __delta_cap, 2 * __old_cap)) : __ms - 1; + __old_cap < __ms / 2 - __alignment ? __recommend(std::max(__old_cap + __delta_cap, 2 * __old_cap)) : __ms; __annotate_delete(); auto __allocation = std::__allocate_at_least(__alloc(), __cap + 1); pointer __p = __allocation.ptr; diff --git a/libcxx/include/__filesystem/file_status.h b/libcxx/include/__filesystem/file_status.h index da316c8b0274..eecaf3c492f0 100644 --- a/libcxx/include/__filesystem/file_status.h +++ b/libcxx/include/__filesystem/file_status.h @@ -22,7 +22,7 @@ _LIBCPP_BEGIN_NAMESPACE_FILESYSTEM -class _LIBCPP_EXPORTED_FROM_ABI file_status { +class file_status { public: // constructors _LIBCPP_HIDE_FROM_ABI file_status() noexcept : file_status(file_type::none) {} diff --git a/libcxx/include/__filesystem/path.h b/libcxx/include/__filesystem/path.h index 381e5678a585..7f5121020275 100644 --- a/libcxx/include/__filesystem/path.h +++ b/libcxx/include/__filesystem/path.h @@ -861,7 +861,7 @@ public: } // iterators - class _LIBCPP_EXPORTED_FROM_ABI iterator; + class iterator; typedef iterator const_iterator; iterator begin() const; diff --git a/libcxx/include/__filesystem/space_info.h b/libcxx/include/__filesystem/space_info.h index 3fa57d33096f..28f7ced40d27 100644 --- a/libcxx/include/__filesystem/space_info.h +++ b/libcxx/include/__filesystem/space_info.h @@ -21,7 +21,7 @@ _LIBCPP_BEGIN_NAMESPACE_FILESYSTEM -struct _LIBCPP_EXPORTED_FROM_ABI space_info { +struct space_info { uintmax_t capacity; uintmax_t free; uintmax_t available; diff --git a/libcxx/include/__format/formatter_output.h b/libcxx/include/__format/formatter_output.h index cc74e3858a40..d53b6cec707d 100644 --- a/libcxx/include/__format/formatter_output.h +++ b/libcxx/include/__format/formatter_output.h @@ -45,7 +45,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD namespace __formatter { -struct _LIBCPP_EXPORTED_FROM_ABI __padding_size_result { +struct __padding_size_result { size_t __before_; size_t __after_; }; diff --git a/libcxx/include/__functional/function.h b/libcxx/include/__functional/function.h index dc112ebfd0fa..c768fd90d01b 100644 --- a/libcxx/include/__functional/function.h +++ b/libcxx/include/__functional/function.h @@ -15,16 +15,14 @@ #include <__cstddef/nullptr_t.h> #include <__exception/exception.h> #include <__functional/binary_function.h> -#include <__functional/invoke.h> #include <__functional/unary_function.h> #include <__memory/addressof.h> #include <__type_traits/aligned_storage.h> #include <__type_traits/decay.h> -#include <__type_traits/is_core_convertible.h> +#include <__type_traits/invoke.h> #include <__type_traits/is_scalar.h> #include <__type_traits/is_trivially_constructible.h> #include <__type_traits/is_trivially_destructible.h> -#include <__type_traits/is_void.h> #include <__type_traits/strip_signature.h> #include <__utility/forward.h> #include <__utility/move.h> @@ -95,29 +93,29 @@ template <class _Rp, class _A1, class _A2> struct __maybe_derive_from_binary_function<_Rp(_A1, _A2)> : public __binary_function<_A1, _A2, _Rp> {}; template <class _Fp> -_LIBCPP_HIDE_FROM_ABI bool __not_null(_Fp const&) { - return true; +_LIBCPP_HIDE_FROM_ABI bool __is_null(_Fp const&) { + return false; } template <class _Fp> -_LIBCPP_HIDE_FROM_ABI bool __not_null(_Fp* __ptr) { - return __ptr; +_LIBCPP_HIDE_FROM_ABI bool __is_null(_Fp* __ptr) { + return !__ptr; } template <class _Ret, class _Class> -_LIBCPP_HIDE_FROM_ABI bool __not_null(_Ret _Class::*__ptr) { - return __ptr; +_LIBCPP_HIDE_FROM_ABI bool __is_null(_Ret _Class::* __ptr) { + return !__ptr; } template <class _Fp> -_LIBCPP_HIDE_FROM_ABI bool __not_null(function<_Fp> const& __f) { - return !!__f; +_LIBCPP_HIDE_FROM_ABI bool __is_null(function<_Fp> const& __f) { + return !__f; } # if __has_extension(blocks) template <class _Rp, class... _Args> -_LIBCPP_HIDE_FROM_ABI bool __not_null(_Rp (^__p)(_Args...)) { - return __p; +_LIBCPP_HIDE_FROM_ABI bool __is_null(_Rp (^__p)(_Args...)) { + return !__p; } # endif @@ -206,12 +204,13 @@ public: _LIBCPP_HIDE_FROM_ABI explicit __value_func(_Fp&& __f) : __f_(nullptr) { typedef __function::__func<_Fp, _Rp(_ArgTypes...)> _Fun; - if (__function::__not_null(__f)) { - if (sizeof(_Fun) <= sizeof(__buf_) && is_nothrow_copy_constructible<_Fp>::value) { - __f_ = ::new (std::addressof(__buf_)) _Fun(std::move(__f)); - } else { - __f_ = new _Fun(std::move(__f)); - } + if (__function::__is_null(__f)) + return; + + if (sizeof(_Fun) <= sizeof(__buf_) && is_nothrow_copy_constructible<_Fp>::value) { + __f_ = ::new (std::addressof(__buf_)) _Fun(std::move(__f)); + } else { + __f_ = new _Fun(std::move(__f)); } } @@ -356,7 +355,31 @@ struct __policy { // type. template <typename _Fun> _LIBCPP_HIDE_FROM_ABI static const __policy* __create() { - return __choose_policy<_Fun>(__use_small_storage<_Fun>()); + if constexpr (__use_small_storage<_Fun>::value) { + static constexpr __policy __policy = { + nullptr, + nullptr, + false, +# if _LIBCPP_HAS_RTTI + &typeid(_Fun) +# else + nullptr +# endif + }; + return &__policy; + } else { + static constexpr __policy __policy = { + std::addressof(__large_clone<_Fun>), + std::addressof(__large_destroy<_Fun>), + false, +# if _LIBCPP_HAS_RTTI + &typeid(_Fun) +# else + nullptr +# endif + }; + return &__policy; + } } _LIBCPP_HIDE_FROM_ABI static const __policy* __create_empty() { @@ -384,36 +407,6 @@ private: _LIBCPP_HIDE_FROM_ABI static void __large_destroy(void* __s) { delete static_cast<_Fun*>(__s); } - - template <typename _Fun> - _LIBCPP_HIDE_FROM_ABI static const __policy* __choose_policy(/* is_small = */ false_type) { - static constexpr __policy __policy = { - std::addressof(__large_clone<_Fun>), - std::addressof(__large_destroy<_Fun>), - false, -# if _LIBCPP_HAS_RTTI - &typeid(_Fun) -# else - nullptr -# endif - }; - return &__policy; - } - - template <typename _Fun> - _LIBCPP_HIDE_FROM_ABI static const __policy* __choose_policy(/* is_small = */ true_type) { - static constexpr __policy __policy = { - nullptr, - nullptr, - false, -# if _LIBCPP_HAS_RTTI - &typeid(_Fun) -# else - nullptr -# endif - }; - return &__policy; - } }; // Used to choose between perfect forwarding or pass-by-value. Pass-by-value is @@ -455,14 +448,15 @@ public: template <class _Fp, __enable_if_t<!is_same<__decay_t<_Fp>, __policy_func>::value, int> = 0> _LIBCPP_HIDE_FROM_ABI explicit __policy_func(_Fp&& __f) : __policy_(__policy::__create_empty()) { - if (__function::__not_null(__f)) { - __func_ = __call_func<_Fp>; - __policy_ = __policy::__create<_Fp>(); - if (__use_small_storage<_Fp>()) { - ::new ((void*)&__buf_.__small) _Fp(std::move(__f)); - } else { - __buf_.__large = ::new _Fp(std::move(__f)); - } + if (__function::__is_null(__f)) + return; + + __func_ = __call_func<_Fp>; + __policy_ = __policy::__create<_Fp>(); + if (__use_small_storage<_Fp>()) { + ::new ((void*)&__buf_.__small) _Fp(std::move(__f)); + } else { + __buf_.__large = ::new _Fp(std::move(__f)); } } @@ -615,21 +609,9 @@ class function<_Rp(_ArgTypes...)> __func __f_; - template <class _Fp, - bool = _And<_IsNotSame<__remove_cvref_t<_Fp>, function>, __is_invocable<_Fp, _ArgTypes...> >::value> - struct __callable; - template <class _Fp> - struct __callable<_Fp, true> { - static const bool value = - is_void<_Rp>::value || __is_core_convertible<__invoke_result_t<_Fp, _ArgTypes...>, _Rp>::value; - }; - template <class _Fp> - struct __callable<_Fp, false> { - static const bool value = false; - }; - template <class _Fp> - using _EnableIfLValueCallable _LIBCPP_NODEBUG = __enable_if_t<__callable<_Fp&>::value>; + using _EnableIfLValueCallable _LIBCPP_NODEBUG = __enable_if_t< + _And<_IsNotSame<__remove_cvref_t<_Fp>, function>, __is_invocable_r<_Rp, _Fp&, _ArgTypes...>>::value>; public: typedef _Rp result_type; diff --git a/libcxx/include/__functional/hash.h b/libcxx/include/__functional/hash.h index 489a6f00b8a3..83bbf1b5e26c 100644 --- a/libcxx/include/__functional/hash.h +++ b/libcxx/include/__functional/hash.h @@ -21,6 +21,7 @@ #include <__type_traits/is_enum.h> #include <__type_traits/is_floating_point.h> #include <__type_traits/is_integral.h> +#include <__type_traits/is_unqualified.h> #include <__type_traits/underlying_type.h> #include <__utility/pair.h> #include <__utility/swap.h> @@ -355,7 +356,8 @@ struct __hash_impl { }; template <class _Tp> -struct __hash_impl<_Tp, __enable_if_t<is_enum<_Tp>::value> > : __unary_function<_Tp, size_t> { +struct __hash_impl<_Tp, __enable_if_t<is_enum<_Tp>::value && __is_unqualified_v<_Tp> > > + : __unary_function<_Tp, size_t> { _LIBCPP_HIDE_FROM_ABI size_t operator()(_Tp __v) const _NOEXCEPT { using type = __underlying_type_t<_Tp>; return hash<type>()(static_cast<type>(__v)); @@ -363,17 +365,21 @@ struct __hash_impl<_Tp, __enable_if_t<is_enum<_Tp>::value> > : __unary_function< }; template <class _Tp> -struct __hash_impl<_Tp, __enable_if_t<is_integral<_Tp>::value && (sizeof(_Tp) <= sizeof(size_t))> > +struct __hash_impl< + _Tp, + __enable_if_t<is_integral<_Tp>::value && __is_unqualified_v<_Tp> && (sizeof(_Tp) <= sizeof(size_t))> > : __unary_function<_Tp, size_t> { _LIBCPP_HIDE_FROM_ABI size_t operator()(_Tp __v) const _NOEXCEPT { return static_cast<size_t>(__v); } }; template <class _Tp> -struct __hash_impl<_Tp, __enable_if_t<is_integral<_Tp>::value && (sizeof(_Tp) > sizeof(size_t))> > +struct __hash_impl<_Tp, + __enable_if_t<is_integral<_Tp>::value && __is_unqualified_v<_Tp> && (sizeof(_Tp) > sizeof(size_t))> > : __scalar_hash<_Tp> {}; template <class _Tp> -struct __hash_impl<_Tp, __enable_if_t<is_floating_point<_Tp>::value> > : __scalar_hash<_Tp> { +struct __hash_impl<_Tp, __enable_if_t<is_floating_point<_Tp>::value && __is_unqualified_v<_Tp> > > + : __scalar_hash<_Tp> { _LIBCPP_HIDE_FROM_ABI size_t operator()(_Tp __v) const _NOEXCEPT { // -0.0 and 0.0 should return same hash if (__v == 0.0f) diff --git a/libcxx/include/__fwd/tuple.h b/libcxx/include/__fwd/tuple.h index 39ed94d9806e..dc96c03e2024 100644 --- a/libcxx/include/__fwd/tuple.h +++ b/libcxx/include/__fwd/tuple.h @@ -21,11 +21,20 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <size_t, class> struct tuple_element; +template <size_t _Np, class _Tp> +using __tuple_element_t _LIBCPP_NODEBUG = typename tuple_element<_Np, _Tp>::type; + #ifndef _LIBCPP_CXX03_LANG template <class...> class tuple; +template <class> +inline const bool __is_tuple_v = false; + +template <class... _Tp> +inline const bool __is_tuple_v<tuple<_Tp...>> = true; + template <size_t _Ip, class... _Tp> struct tuple_element<_Ip, tuple<_Tp...> > { using type _LIBCPP_NODEBUG = __type_pack_element<_Ip, _Tp...>; diff --git a/libcxx/include/__hash_table b/libcxx/include/__hash_table index 996ec9fa31ac..f0e88bbf2bc3 100644 --- a/libcxx/include/__hash_table +++ b/libcxx/include/__hash_table @@ -29,7 +29,6 @@ #include <__memory/swap_allocator.h> #include <__memory/unique_ptr.h> #include <__new/launder.h> -#include <__type_traits/can_extract_key.h> #include <__type_traits/copy_cvref.h> #include <__type_traits/enable_if.h> #include <__type_traits/invoke.h> @@ -46,6 +45,7 @@ #include <__utility/move.h> #include <__utility/pair.h> #include <__utility/swap.h> +#include <__utility/try_key_extraction.h> #include <limits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -201,22 +201,11 @@ struct __hash_node_types; template <class _NodePtr, class _Tp, class _VoidPtr> struct __hash_node_types<_NodePtr, __hash_node<_Tp, _VoidPtr> > { - typedef ptrdiff_t difference_type; - typedef size_t size_type; - - typedef __rebind_pointer_t<_NodePtr, void> __void_pointer; - typedef typename pointer_traits<_NodePtr>::element_type __node_type; - typedef _NodePtr __node_pointer; - typedef __hash_node_base<__node_pointer> __node_base_type; - typedef __rebind_pointer_t<_NodePtr, __node_base_type> __node_base_pointer; - - typedef typename __node_base_type::__next_pointer __next_pointer; + typedef typename __hash_node_base<_NodePtr>::__next_pointer __next_pointer; using __node_value_type _LIBCPP_NODEBUG = __get_hash_node_value_type_t<_Tp>; - typedef __rebind_pointer_t<_VoidPtr, __node_value_type> __node_value_type_pointer; - typedef __rebind_pointer_t<_VoidPtr, const __node_value_type> __const_node_value_type_pointer; private: static_assert(!is_const<__node_type>::value, "_NodePtr should never be a pointer to const"); @@ -237,13 +226,6 @@ struct __hash_node_types_from_iterator<__hash_local_iterator<_NodePtr> > : __has template <class _NodePtr> struct __hash_node_types_from_iterator<__hash_const_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {}; -template <class _NodeValueTp, class _VoidPtr> -struct __make_hash_node_types { - typedef __hash_node<_NodeValueTp, _VoidPtr> _NodeTp; - typedef __rebind_pointer_t<_VoidPtr, _NodeTp> _NodePtr; - typedef __hash_node_types<_NodePtr> type; -}; - template <class _NodePtr> class __hash_iterator { typedef __hash_node_types<_NodePtr> _NodeTypes; @@ -255,9 +237,9 @@ class __hash_iterator { public: typedef forward_iterator_tag iterator_category; typedef typename _NodeTypes::__node_value_type value_type; - typedef typename _NodeTypes::difference_type difference_type; + using difference_type = ptrdiff_t; typedef value_type& reference; - typedef typename _NodeTypes::__node_value_type_pointer pointer; + using pointer = __rebind_pointer_t<_NodePtr, value_type>; _LIBCPP_HIDE_FROM_ABI __hash_iterator() _NOEXCEPT : __node_(nullptr) {} @@ -322,9 +304,9 @@ public: typedef forward_iterator_tag iterator_category; typedef typename _NodeTypes::__node_value_type value_type; - typedef typename _NodeTypes::difference_type difference_type; + using difference_type = ptrdiff_t; typedef const value_type& reference; - typedef typename _NodeTypes::__const_node_value_type_pointer pointer; + using pointer = __rebind_pointer_t<_NodePtr, const value_type>; _LIBCPP_HIDE_FROM_ABI __hash_const_iterator() _NOEXCEPT : __node_(nullptr) {} @@ -387,9 +369,9 @@ class __hash_local_iterator { public: typedef forward_iterator_tag iterator_category; typedef typename _NodeTypes::__node_value_type value_type; - typedef typename _NodeTypes::difference_type difference_type; + using difference_type = ptrdiff_t; typedef value_type& reference; - typedef typename _NodeTypes::__node_value_type_pointer pointer; + using pointer = __rebind_pointer_t<_NodePtr, value_type>; _LIBCPP_HIDE_FROM_ABI __hash_local_iterator() _NOEXCEPT : __node_(nullptr) {} @@ -465,9 +447,9 @@ public: typedef forward_iterator_tag iterator_category; typedef typename _NodeTypes::__node_value_type value_type; - typedef typename _NodeTypes::difference_type difference_type; + using difference_type = ptrdiff_t; typedef const value_type& reference; - typedef typename _NodeTypes::__const_node_value_type_pointer pointer; + using pointer = __rebind_pointer_t<_ConstNodePtr, const value_type>; _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator() _NOEXCEPT : __node_(nullptr) {} @@ -646,10 +628,8 @@ public: private: typedef allocator_traits<allocator_type> __alloc_traits; - typedef typename __make_hash_node_types<_Tp, typename __alloc_traits::void_pointer>::type _NodeTypes; public: - typedef typename _NodeTypes::__node_value_type __node_value_type; typedef value_type& reference; typedef const value_type& const_reference; typedef typename __alloc_traits::pointer pointer; @@ -657,22 +637,23 @@ public: #ifndef _LIBCPP_ABI_FIX_UNORDERED_CONTAINER_SIZE_TYPE typedef typename __alloc_traits::size_type size_type; #else - typedef typename _NodeTypes::size_type size_type; + using size_type = size_t; #endif - typedef typename _NodeTypes::difference_type difference_type; + using difference_type = ptrdiff_t; public: // Create __node - typedef typename _NodeTypes::__node_type __node; - typedef __rebind_alloc<__alloc_traits, __node> __node_allocator; - typedef allocator_traits<__node_allocator> __node_traits; - typedef typename _NodeTypes::__void_pointer __void_pointer; - typedef typename _NodeTypes::__node_pointer __node_pointer; - typedef typename _NodeTypes::__node_pointer __node_const_pointer; - typedef typename _NodeTypes::__node_base_type __first_node; - typedef typename _NodeTypes::__node_base_pointer __node_base_pointer; - typedef typename _NodeTypes::__next_pointer __next_pointer; + using __void_pointer _LIBCPP_NODEBUG = typename __alloc_traits::void_pointer; + + using __node _LIBCPP_NODEBUG = __hash_node<_Tp, __void_pointer>; + using __node_allocator _LIBCPP_NODEBUG = __rebind_alloc<__alloc_traits, __node>; + using __node_traits _LIBCPP_NODEBUG = allocator_traits<__node_allocator>; + using __node_pointer _LIBCPP_NODEBUG = __rebind_pointer_t<__void_pointer, __node>; + + using __first_node _LIBCPP_NODEBUG = __hash_node_base<__node_pointer>; + using __node_base_pointer _LIBCPP_NODEBUG = __rebind_pointer_t<__void_pointer, __first_node>; + using __next_pointer _LIBCPP_NODEBUG = __node_base_pointer; private: // check for sane allocator pointer rebinding semantics. Rebinding the @@ -797,40 +778,66 @@ public: _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(__node_pointer __nd); _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); - template <class _Key, class... _Args> - _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_key_args(_Key const& __k, _Args&&... __args); - - template <class... _Args> - _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_impl(_Args&&... __args); - - template <class _Pp> - _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Pp&& __x) { - return __emplace_unique_extract_key(std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>()); - } - - template <class _First, - class _Second, - __enable_if_t<__can_extract_map_key<_First, key_type, value_type>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_First&& __f, _Second&& __s) { - return __emplace_unique_key_args(__f, std::forward<_First>(__f), std::forward<_Second>(__s)); - } - template <class... _Args> _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Args&&... __args) { - return __emplace_unique_impl(std::forward<_Args>(__args)...); - } - - template <class _Pp> - _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) { - return __emplace_unique_impl(std::forward<_Pp>(__x)); - } - template <class _Pp> - _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) { - return __emplace_unique_key_args(__x, std::forward<_Pp>(__x)); - } - template <class _Pp> - _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) { - return __emplace_unique_key_args(__x.first, std::forward<_Pp>(__x)); + return std::__try_key_extraction<key_type>( + [this](const key_type& __key, _Args&&... __args2) { + size_t __hash = hash_function()(__key); + size_type __bc = bucket_count(); + bool __inserted = false; + __next_pointer __nd; + size_t __chash; + if (__bc != 0) { + __chash = std::__constrain_hash(__hash, __bc); + __nd = __bucket_list_[__chash]; + if (__nd != nullptr) { + for (__nd = __nd->__next_; + __nd != nullptr && + (__nd->__hash() == __hash || std::__constrain_hash(__nd->__hash(), __bc) == __chash); + __nd = __nd->__next_) { + if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __key)) + goto __done; + } + } + } + { + __node_holder __h = __construct_node_hash(__hash, std::forward<_Args>(__args2)...); + if (size() + 1 > __bc * max_load_factor() || __bc == 0) { + __rehash_unique(std::max<size_type>(2 * __bc + !std::__is_hash_power2(__bc), + size_type(__math::ceil(float(size() + 1) / max_load_factor())))); + __bc = bucket_count(); + __chash = std::__constrain_hash(__hash, __bc); + } + // insert_after __bucket_list_[__chash], or __first_node if bucket is null + __next_pointer __pn = __bucket_list_[__chash]; + if (__pn == nullptr) { + __pn = __first_node_.__ptr(); + __h->__next_ = __pn->__next_; + __pn->__next_ = __h.get()->__ptr(); + // fix up __bucket_list_ + __bucket_list_[__chash] = __pn; + if (__h->__next_ != nullptr) + __bucket_list_[std::__constrain_hash(__h->__next_->__hash(), __bc)] = __h.get()->__ptr(); + } else { + __h->__next_ = __pn->__next_; + __pn->__next_ = static_cast<__next_pointer>(__h.get()); + } + __nd = static_cast<__next_pointer>(__h.release()); + // increment size + ++size(); + __inserted = true; + } + __done: + return pair<iterator, bool>(iterator(__nd), __inserted); + }, + [this](_Args&&... __args2) { + __node_holder __h = __construct_node(std::forward<_Args>(__args2)...); + pair<iterator, bool> __r = __node_insert_unique(__h.get()); + if (__r.second) + __h.release(); + return __r; + }, + std::forward<_Args>(__args)...); } template <class... _Args> @@ -999,8 +1006,8 @@ private: template <class... _Args> _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(_Args&&... __args); - template <class _First, class... _Rest> - _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest); + template <class... _Args> + _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_hash(size_t __hash, _Args&&... __args); _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table& __u) { __copy_assign_alloc(__u, integral_constant<bool, __node_traits::propagate_on_container_copy_assignment::value>()); @@ -1024,7 +1031,21 @@ private: } _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {} - _LIBCPP_HIDE_FROM_ABI void __deallocate_node(__next_pointer __np) _NOEXCEPT; + _LIBCPP_HIDE_FROM_ABI void __deallocate_node(__node_pointer __nd) _NOEXCEPT { + auto& __alloc = __node_alloc(); + __node_traits::destroy(__alloc, std::addressof(__nd->__get_value())); + std::__destroy_at(std::__to_address(__nd)); + __node_traits::deallocate(__alloc, __nd, 1); + } + + _LIBCPP_HIDE_FROM_ABI void __deallocate_node_list(__next_pointer __np) _NOEXCEPT { + while (__np != nullptr) { + __next_pointer __next = __np->__next_; + __deallocate_node(__np->__upcast()); + __np = __next; + } + } + _LIBCPP_HIDE_FROM_ABI __next_pointer __detach() _NOEXCEPT; template <class _From, class _ValueT = _Tp, __enable_if_t<__is_hash_value_type<_ValueT>::value, int> = 0> @@ -1162,7 +1183,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() { static_assert(is_copy_constructible<hasher>::value, "Hasher must be copy-constructible."); #endif - __deallocate_node(__first_node_.__next_); + __deallocate_node_list(__first_node_.__next_); } template <class _Tp, class _Hash, class _Equal, class _Alloc> @@ -1238,7 +1259,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __other) // At this point we either have consumed the whole incoming hash table, or we don't have any more nodes to reuse in // the destination. Either continue with constructing new nodes, or deallocate the left over nodes. if (__own_iter->__next_) { - __deallocate_node(__own_iter->__next_); + __deallocate_node_list(__own_iter->__next_); __own_iter->__next_ = nullptr; } else { __copy_construct(__other_iter, __own_iter, __current_chash); @@ -1250,19 +1271,6 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __other) } template <class _Tp, class _Hash, class _Equal, class _Alloc> -void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate_node(__next_pointer __np) _NOEXCEPT { - __node_allocator& __na = __node_alloc(); - while (__np != nullptr) { - __next_pointer __next = __np->__next_; - __node_pointer __real_np = __np->__upcast(); - __node_traits::destroy(__na, std::addressof(__real_np->__get_value())); - std::__destroy_at(std::addressof(*__real_np)); - __node_traits::deallocate(__na, __real_np, 1); - __np = __next; - } -} - -template <class _Tp, class _Hash, class _Equal, class _Alloc> typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer __hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT { size_type __bc = bucket_count(); @@ -1317,11 +1325,11 @@ void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(__hash_table& __u, } #if _LIBCPP_HAS_EXCEPTIONS } catch (...) { - __deallocate_node(__cache); + __deallocate_node_list(__cache); throw; } #endif // _LIBCPP_HAS_EXCEPTIONS - __deallocate_node(__cache); + __deallocate_node_list(__cache); } const_iterator __i = __u.begin(); while (__u.size() != 0) @@ -1360,11 +1368,11 @@ void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __ } #if _LIBCPP_HAS_EXCEPTIONS } catch (...) { - __deallocate_node(__cache); + __deallocate_node_list(__cache); throw; } #endif // _LIBCPP_HAS_EXCEPTIONS - __deallocate_node(__cache); + __deallocate_node_list(__cache); } for (; __first != __last; ++__first) __emplace_unique(*__first); @@ -1390,11 +1398,11 @@ void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __f } #if _LIBCPP_HAS_EXCEPTIONS } catch (...) { - __deallocate_node(__cache); + __deallocate_node_list(__cache); throw; } #endif // _LIBCPP_HAS_EXCEPTIONS - __deallocate_node(__cache); + __deallocate_node_list(__cache); } for (; __first != __last; ++__first) __emplace_multi(*__first); @@ -1427,7 +1435,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT { template <class _Tp, class _Hash, class _Equal, class _Alloc> void __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT { if (size() > 0) { - __deallocate_node(__first_node_.__next_); + __deallocate_node_list(__first_node_.__next_); __first_node_.__next_ = nullptr; size_type __bc = bucket_count(); for (size_type __i = 0; __i < __bc; ++__i) @@ -1614,69 +1622,6 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(const_iterator __p } template <class _Tp, class _Hash, class _Equal, class _Alloc> -template <class _Key, class... _Args> -pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) { - size_t __hash = hash_function()(__k); - size_type __bc = bucket_count(); - bool __inserted = false; - __next_pointer __nd; - size_t __chash; - if (__bc != 0) { - __chash = std::__constrain_hash(__hash, __bc); - __nd = __bucket_list_[__chash]; - if (__nd != nullptr) { - for (__nd = __nd->__next_; - __nd != nullptr && (__nd->__hash() == __hash || std::__constrain_hash(__nd->__hash(), __bc) == __chash); - __nd = __nd->__next_) { - if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __k)) - goto __done; - } - } - } - { - __node_holder __h = __construct_node_hash(__hash, std::forward<_Args>(__args)...); - if (size() + 1 > __bc * max_load_factor() || __bc == 0) { - __rehash_unique(std::max<size_type>( - 2 * __bc + !std::__is_hash_power2(__bc), size_type(__math::ceil(float(size() + 1) / max_load_factor())))); - __bc = bucket_count(); - __chash = std::__constrain_hash(__hash, __bc); - } - // insert_after __bucket_list_[__chash], or __first_node if bucket is null - __next_pointer __pn = __bucket_list_[__chash]; - if (__pn == nullptr) { - __pn = __first_node_.__ptr(); - __h->__next_ = __pn->__next_; - __pn->__next_ = __h.get()->__ptr(); - // fix up __bucket_list_ - __bucket_list_[__chash] = __pn; - if (__h->__next_ != nullptr) - __bucket_list_[std::__constrain_hash(__h->__next_->__hash(), __bc)] = __h.get()->__ptr(); - } else { - __h->__next_ = __pn->__next_; - __pn->__next_ = static_cast<__next_pointer>(__h.get()); - } - __nd = static_cast<__next_pointer>(__h.release()); - // increment size - ++size(); - __inserted = true; - } -__done: - return pair<iterator, bool>(iterator(__nd), __inserted); -} - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -template <class... _Args> -pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_impl(_Args&&... __args) { - __node_holder __h = __construct_node(std::forward<_Args>(__args)...); - pair<iterator, bool> __r = __node_insert_unique(__h.get()); - if (__r.second) - __h.release(); - return __r; -} - -template <class _Tp, class _Hash, class _Equal, class _Alloc> template <class... _Args> typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) { @@ -1927,15 +1872,14 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&&... __args) { } template <class _Tp, class _Hash, class _Equal, class _Alloc> -template <class _First, class... _Rest> +template <class... _Args> typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest) { - static_assert(!__is_hash_value_type<_First, _Rest...>::value, "Construct cannot be called with a hash value type"); +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(size_t __hash, _Args&&... __args) { + static_assert(!__is_hash_value_type<_Args...>::value, "Construct cannot be called with a hash value type"); __node_allocator& __na = __node_alloc(); __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); std::__construct_at(std::addressof(*__h), /* next = */ nullptr, /* hash = */ __hash); - __node_traits::construct( - __na, std::addressof(__h->__get_value()), std::forward<_First>(__f), std::forward<_Rest>(__rest)...); + __node_traits::construct(__na, std::addressof(__h->__get_value()), std::forward<_Args>(__args)...); __h.get_deleter().__value_constructed = true; return __h; } @@ -1955,12 +1899,57 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) { template <class _Tp, class _Hash, class _Equal, class _Alloc> typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, const_iterator __last) { - for (const_iterator __p = __first; __first != __last; __p = __first) { - ++__first; - erase(__p); + if (__first == __last) + return iterator(__last.__node_); + + // current node + __next_pointer __current = __first.__node_; + size_type __bucket_count = bucket_count(); + size_t __chash = std::__constrain_hash(__current->__hash(), __bucket_count); + // find previous node + __next_pointer __before_first = __bucket_list_[__chash]; + for (; __before_first->__next_ != __current; __before_first = __before_first->__next_) + ; + + __next_pointer __last_node = __last.__node_; + + // If __before_first is in the same bucket (i.e. the first element we erase is not the first in the bucket), clear + // this bucket first without re-linking it + if (__before_first != __first_node_.__ptr() && + std::__constrain_hash(__before_first->__hash(), __bucket_count) == __chash) { + while (__current != __last_node) { + if (auto __next_chash = std::__constrain_hash(__current->__hash(), __bucket_count); __next_chash != __chash) { + __chash = __next_chash; + break; + } + auto __next = __current->__next_; + __deallocate_node(__current->__upcast()); + __current = __next; + --__size_; + } } - __next_pointer __np = __last.__node_; - return iterator(__np); + + while (__current != __last_node) { + auto __next = __current->__next_; + __deallocate_node(__current->__upcast()); + __current = __next; + --__size_; + + // When switching buckets, set the old bucket to be empty and update the next bucket to have __before_first as its + // before-first element + if (__next) { + if (auto __next_chash = std::__constrain_hash(__next->__hash(), __bucket_count); __next_chash != __chash) { + __bucket_list_[__chash] = nullptr; + __chash = __next_chash; + __bucket_list_[__chash] = __before_first; + } + } + } + + // re-link __before_first with __last + __before_first->__next_ = __current; + + return iterator(__last.__node_); } template <class _Tp, class _Hash, class _Equal, class _Alloc> diff --git a/libcxx/include/__iterator/back_insert_iterator.h b/libcxx/include/__iterator/back_insert_iterator.h index 3a11fae4cb87..d051c08751d3 100644 --- a/libcxx/include/__iterator/back_insert_iterator.h +++ b/libcxx/include/__iterator/back_insert_iterator.h @@ -26,15 +26,9 @@ _LIBCPP_PUSH_MACROS _LIBCPP_BEGIN_NAMESPACE_STD -_LIBCPP_SUPPRESS_DEPRECATED_PUSH template <class _Container> class back_insert_iterator -#if _LIBCPP_STD_VER <= 14 || !defined(_LIBCPP_ABI_NO_ITERATOR_BASES) - : public iterator<output_iterator_tag, void, void, void, void> -#endif -{ - _LIBCPP_SUPPRESS_DEPRECATED_POP - + : public __iterator_base<back_insert_iterator<_Container>, output_iterator_tag, void, void, void, void> { protected: _Container* container; diff --git a/libcxx/include/__iterator/bounded_iter.h b/libcxx/include/__iterator/bounded_iter.h index d12750d1f81a..26eae87917ea 100644 --- a/libcxx/include/__iterator/bounded_iter.h +++ b/libcxx/include/__iterator/bounded_iter.h @@ -116,8 +116,7 @@ public: // These operations check that the iterator is dereferenceable. Since the class invariant is // that the iterator is always within `[begin, end]`, we only need to check it's not pointing to // `end`. This is easier for the optimizer because it aligns with the `iter != container.end()` - // checks that typical callers already use (see - // https://github.com/llvm/llvm-project/issues/78829). + // checks that typical callers already use (see https://llvm.org/PR78829). _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 reference operator*() const _NOEXCEPT { _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( __current_ != __end_, "__bounded_iter::operator*: Attempt to dereference an iterator at the end"); diff --git a/libcxx/include/__iterator/concepts.h b/libcxx/include/__iterator/concepts.h index 20a1ab469110..f38688734b38 100644 --- a/libcxx/include/__iterator/concepts.h +++ b/libcxx/include/__iterator/concepts.h @@ -118,7 +118,7 @@ concept __signed_integer_like = signed_integral<_Tp>; template <class _Ip> concept weakly_incrementable = - // TODO: remove this once the clang bug is fixed (bugs.llvm.org/PR48173). + // TODO: remove this once the clang bug is fixed (https://llvm.org/PR48173). !same_as<_Ip, bool> && // Currently, clang does not handle bool correctly. movable<_Ip> && requires(_Ip __i) { typename iter_difference_t<_Ip>; diff --git a/libcxx/include/__iterator/front_insert_iterator.h b/libcxx/include/__iterator/front_insert_iterator.h index d79c4d78b636..2ab5383a1d91 100644 --- a/libcxx/include/__iterator/front_insert_iterator.h +++ b/libcxx/include/__iterator/front_insert_iterator.h @@ -26,15 +26,9 @@ _LIBCPP_PUSH_MACROS _LIBCPP_BEGIN_NAMESPACE_STD -_LIBCPP_SUPPRESS_DEPRECATED_PUSH template <class _Container> class front_insert_iterator -#if _LIBCPP_STD_VER <= 14 || !defined(_LIBCPP_ABI_NO_ITERATOR_BASES) - : public iterator<output_iterator_tag, void, void, void, void> -#endif -{ - _LIBCPP_SUPPRESS_DEPRECATED_POP - + : public __iterator_base<front_insert_iterator<_Container>, output_iterator_tag, void, void, void, void> { protected: _Container* container; diff --git a/libcxx/include/__iterator/insert_iterator.h b/libcxx/include/__iterator/insert_iterator.h index 95768cb8e036..6a5818b47877 100644 --- a/libcxx/include/__iterator/insert_iterator.h +++ b/libcxx/include/__iterator/insert_iterator.h @@ -35,15 +35,9 @@ template <class _Container> using __insert_iterator_iter_t _LIBCPP_NODEBUG = typename _Container::iterator; #endif -_LIBCPP_SUPPRESS_DEPRECATED_PUSH template <class _Container> class insert_iterator -#if _LIBCPP_STD_VER <= 14 || !defined(_LIBCPP_ABI_NO_ITERATOR_BASES) - : public iterator<output_iterator_tag, void, void, void, void> -#endif -{ - _LIBCPP_SUPPRESS_DEPRECATED_POP - + : public __iterator_base<insert_iterator<_Container>, output_iterator_tag, void, void, void, void> { protected: _Container* container; __insert_iterator_iter_t<_Container> iter; diff --git a/libcxx/include/__iterator/istream_iterator.h b/libcxx/include/__iterator/istream_iterator.h index cdb8056cfe98..f4b13f09c7e2 100644 --- a/libcxx/include/__iterator/istream_iterator.h +++ b/libcxx/include/__iterator/istream_iterator.h @@ -25,15 +25,14 @@ _LIBCPP_BEGIN_NAMESPACE_STD -_LIBCPP_SUPPRESS_DEPRECATED_PUSH template <class _Tp, class _CharT = char, class _Traits = char_traits<_CharT>, class _Distance = ptrdiff_t> class istream_iterator -#if _LIBCPP_STD_VER <= 14 || !defined(_LIBCPP_ABI_NO_ITERATOR_BASES) - : public iterator<input_iterator_tag, _Tp, _Distance, const _Tp*, const _Tp&> -#endif -{ - _LIBCPP_SUPPRESS_DEPRECATED_POP - + : public __iterator_base<istream_iterator<_Tp, _CharT, _Traits, _Distance>, + input_iterator_tag, + _Tp, + _Distance, + const _Tp*, + const _Tp&> { public: typedef input_iterator_tag iterator_category; typedef _Tp value_type; diff --git a/libcxx/include/__iterator/istreambuf_iterator.h b/libcxx/include/__iterator/istreambuf_iterator.h index b7b28cd1a0b7..4fc87a84f019 100644 --- a/libcxx/include/__iterator/istreambuf_iterator.h +++ b/libcxx/include/__iterator/istreambuf_iterator.h @@ -25,15 +25,14 @@ _LIBCPP_BEGIN_NAMESPACE_STD -_LIBCPP_SUPPRESS_DEPRECATED_PUSH template <class _CharT, class _Traits> class istreambuf_iterator -#if _LIBCPP_STD_VER <= 14 || !defined(_LIBCPP_ABI_NO_ITERATOR_BASES) - : public iterator<input_iterator_tag, _CharT, typename _Traits::off_type, _CharT*, _CharT> -#endif -{ - _LIBCPP_SUPPRESS_DEPRECATED_POP - + : public __iterator_base<istreambuf_iterator<_CharT, _Traits>, + input_iterator_tag, + _CharT, + typename _Traits::off_type, + _CharT*, + _CharT> { public: typedef input_iterator_tag iterator_category; typedef _CharT value_type; diff --git a/libcxx/include/__iterator/iterator.h b/libcxx/include/__iterator/iterator.h index d7fcd8c4dd73..c599f61797a7 100644 --- a/libcxx/include/__iterator/iterator.h +++ b/libcxx/include/__iterator/iterator.h @@ -28,6 +28,19 @@ struct _LIBCPP_DEPRECATED_IN_CXX17 iterator { typedef _Category iterator_category; }; +_LIBCPP_SUPPRESS_DEPRECATED_PUSH +#ifdef _LIBCPP_ABI_NO_ITERATOR_BASES +template <class _Derived> +struct __no_iterator_base {}; + +template <class _Derived, class _Category, class _Tp, class _Distance, class _Pointer, class _Reference> +using __iterator_base _LIBCPP_NODEBUG = __no_iterator_base<_Derived>; +#else +template <class _Derived, class _Category, class _Tp, class _Distance, class _Pointer, class _Reference> +using __iterator_base _LIBCPP_NODEBUG = iterator<_Category, _Tp, _Distance, _Pointer, _Reference>; +#endif +_LIBCPP_SUPPRESS_DEPRECATED_POP + _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___ITERATOR_ITERATOR_H diff --git a/libcxx/include/__iterator/ostream_iterator.h b/libcxx/include/__iterator/ostream_iterator.h index 2b459f462851..64e79f010f64 100644 --- a/libcxx/include/__iterator/ostream_iterator.h +++ b/libcxx/include/__iterator/ostream_iterator.h @@ -24,15 +24,9 @@ _LIBCPP_BEGIN_NAMESPACE_STD -_LIBCPP_SUPPRESS_DEPRECATED_PUSH template <class _Tp, class _CharT = char, class _Traits = char_traits<_CharT> > class ostream_iterator -#if _LIBCPP_STD_VER <= 14 || !defined(_LIBCPP_ABI_NO_ITERATOR_BASES) - : public iterator<output_iterator_tag, void, void, void, void> -#endif -{ - _LIBCPP_SUPPRESS_DEPRECATED_POP - + : public __iterator_base<ostream_iterator<_Tp, _CharT, _Traits>, output_iterator_tag, void, void, void, void> { public: typedef output_iterator_tag iterator_category; typedef void value_type; diff --git a/libcxx/include/__iterator/ostreambuf_iterator.h b/libcxx/include/__iterator/ostreambuf_iterator.h index 7133331a7bf6..4a3b2fa02449 100644 --- a/libcxx/include/__iterator/ostreambuf_iterator.h +++ b/libcxx/include/__iterator/ostreambuf_iterator.h @@ -25,15 +25,9 @@ _LIBCPP_BEGIN_NAMESPACE_STD -_LIBCPP_SUPPRESS_DEPRECATED_PUSH template <class _CharT, class _Traits> class ostreambuf_iterator -#if _LIBCPP_STD_VER <= 14 || !defined(_LIBCPP_ABI_NO_ITERATOR_BASES) - : public iterator<output_iterator_tag, void, void, void, void> -#endif -{ - _LIBCPP_SUPPRESS_DEPRECATED_POP - + : public __iterator_base<ostreambuf_iterator<_CharT, _Traits>, output_iterator_tag, void, void, void, void> { public: typedef output_iterator_tag iterator_category; typedef void value_type; diff --git a/libcxx/include/__iterator/reverse_iterator.h b/libcxx/include/__iterator/reverse_iterator.h index 8935e5a8ff7a..834695dd1670 100644 --- a/libcxx/include/__iterator/reverse_iterator.h +++ b/libcxx/include/__iterator/reverse_iterator.h @@ -46,21 +46,16 @@ _LIBCPP_BEGIN_NAMESPACE_STD -_LIBCPP_SUPPRESS_DEPRECATED_PUSH template <class _Iter> class reverse_iterator -#if _LIBCPP_STD_VER <= 14 || !defined(_LIBCPP_ABI_NO_ITERATOR_BASES) - : public iterator<typename iterator_traits<_Iter>::iterator_category, - typename iterator_traits<_Iter>::value_type, - typename iterator_traits<_Iter>::difference_type, - typename iterator_traits<_Iter>::pointer, - typename iterator_traits<_Iter>::reference> -#endif -{ - _LIBCPP_SUPPRESS_DEPRECATED_POP - + : public __iterator_base<reverse_iterator<_Iter>, + typename iterator_traits<_Iter>::iterator_category, + typename iterator_traits<_Iter>::value_type, + typename iterator_traits<_Iter>::difference_type, + typename iterator_traits<_Iter>::pointer, + typename iterator_traits<_Iter>::reference> { private: -#ifndef _LIBCPP_ABI_NO_ITERATOR_BASES +#ifndef _LIBCPP_ABI_NO_REVERSE_ITERATOR_SECOND_MEMBER _Iter __t_; // no longer used as of LWG #2360, not removed due to ABI break #endif @@ -91,7 +86,7 @@ public: using reference = typename iterator_traits<_Iter>::reference; #endif -#ifndef _LIBCPP_ABI_NO_ITERATOR_BASES +#ifndef _LIBCPP_ABI_NO_REVERSE_ITERATOR_SECOND_MEMBER _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 reverse_iterator() : __t_(), current() {} _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 explicit reverse_iterator(_Iter __x) : __t_(__x), current(__x) {} diff --git a/libcxx/include/__math/hypot.h b/libcxx/include/__math/hypot.h index 8e8c35b4a41c..2b12d7be2107 100644 --- a/libcxx/include/__math/hypot.h +++ b/libcxx/include/__math/hypot.h @@ -53,7 +53,7 @@ inline _LIBCPP_HIDE_FROM_ABI __promote_t<_A1, _A2> hypot(_A1 __x, _A2 __y) _NOEX // Computes the three-dimensional hypotenuse: `std::hypot(x,y,z)`. // The naive implementation might over-/underflow which is why this implementation is more involved: // If the square of an argument might run into issues, we scale the arguments appropriately. -// See https://github.com/llvm/llvm-project/issues/92782 for a detailed discussion and summary. +// See https://llvm.org/PR92782 for a detailed discussion and summary. template <class _Real> _LIBCPP_HIDE_FROM_ABI _Real __hypot(_Real __x, _Real __y, _Real __z) { // Factors needed to determine if over-/underflow might happen diff --git a/libcxx/include/__memory/compressed_pair.h b/libcxx/include/__memory/compressed_pair.h index 29e503931b0b..12163f4af61c 100644 --- a/libcxx/include/__memory/compressed_pair.h +++ b/libcxx/include/__memory/compressed_pair.h @@ -52,7 +52,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD // // Furthermore, that alignment must be the same as what was used in the old __compressed_pair layout, so we must // handle reference types specially since alignof(T&) == alignof(T). -// See https://github.com/llvm/llvm-project/issues/118559. +// See https://llvm.org/PR118559. #ifndef _LIBCPP_ABI_NO_COMPRESSED_PAIR_PADDING diff --git a/libcxx/include/__memory/pointer_traits.h b/libcxx/include/__memory/pointer_traits.h index 8c7f8dff1b76..62fcd93263b0 100644 --- a/libcxx/include/__memory/pointer_traits.h +++ b/libcxx/include/__memory/pointer_traits.h @@ -255,7 +255,7 @@ concept __resettable_smart_pointer_with_args = requires(_Smart __s, _Pointer __p // This function ensures safe conversions between fancy pointers at compile-time, where we avoid casts from/to // `__void_pointer` by obtaining the underlying raw pointer from the fancy pointer using `std::to_address`, // then dereferencing it to retrieve the pointed-to object, and finally constructing the target fancy pointer -// to that object using the `std::pointer_traits<>::pinter_to` function. +// to that object using the `std::pointer_traits<>::pointer_to` function. template <class _PtrTo, class _PtrFrom> _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI _PtrTo __static_fancy_pointer_cast(const _PtrFrom& __p) { using __ptr_traits = pointer_traits<_PtrTo>; diff --git a/libcxx/include/__memory/raw_storage_iterator.h b/libcxx/include/__memory/raw_storage_iterator.h index 0e8b9090704f..d98b3faf4846 100644 --- a/libcxx/include/__memory/raw_storage_iterator.h +++ b/libcxx/include/__memory/raw_storage_iterator.h @@ -28,15 +28,9 @@ _LIBCPP_BEGIN_NAMESPACE_STD #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_RAW_STORAGE_ITERATOR) -_LIBCPP_SUPPRESS_DEPRECATED_PUSH template <class _OutputIterator, class _Tp> class _LIBCPP_DEPRECATED_IN_CXX17 raw_storage_iterator -# if _LIBCPP_STD_VER <= 14 || !defined(_LIBCPP_ABI_NO_ITERATOR_BASES) - : public iterator<output_iterator_tag, void, void, void, void> -# endif -{ - _LIBCPP_SUPPRESS_DEPRECATED_POP - + : public __iterator_base<raw_storage_iterator<_OutputIterator, _Tp>, output_iterator_tag, void, void, void, void> { private: _OutputIterator __x_; diff --git a/libcxx/include/__memory_resource/pool_options.h b/libcxx/include/__memory_resource/pool_options.h index 324b8aaa8502..fd20ced56795 100644 --- a/libcxx/include/__memory_resource/pool_options.h +++ b/libcxx/include/__memory_resource/pool_options.h @@ -24,7 +24,7 @@ namespace pmr { // [mem.res.pool.options] -struct _LIBCPP_EXPORTED_FROM_ABI pool_options { +struct pool_options { size_t max_blocks_per_chunk = 0; size_t largest_required_pool_block = 0; }; diff --git a/libcxx/include/__mutex/tag_types.h b/libcxx/include/__mutex/tag_types.h index 2b2dd58ee4e8..36b1a3d92b14 100644 --- a/libcxx/include/__mutex/tag_types.h +++ b/libcxx/include/__mutex/tag_types.h @@ -17,15 +17,15 @@ _LIBCPP_BEGIN_NAMESPACE_STD -struct _LIBCPP_EXPORTED_FROM_ABI defer_lock_t { +struct defer_lock_t { explicit defer_lock_t() = default; }; -struct _LIBCPP_EXPORTED_FROM_ABI try_to_lock_t { +struct try_to_lock_t { explicit try_to_lock_t() = default; }; -struct _LIBCPP_EXPORTED_FROM_ABI adopt_lock_t { +struct adopt_lock_t { explicit adopt_lock_t() = default; }; diff --git a/libcxx/include/__new/nothrow_t.h b/libcxx/include/__new/nothrow_t.h index a286bf7af628..a09977212393 100644 --- a/libcxx/include/__new/nothrow_t.h +++ b/libcxx/include/__new/nothrow_t.h @@ -19,7 +19,7 @@ # include <new.h> #else _LIBCPP_BEGIN_UNVERSIONED_NAMESPACE_STD -struct _LIBCPP_EXPORTED_FROM_ABI nothrow_t { +struct nothrow_t { explicit nothrow_t() = default; }; extern _LIBCPP_EXPORTED_FROM_ABI const nothrow_t nothrow; diff --git a/libcxx/include/__random/binomial_distribution.h b/libcxx/include/__random/binomial_distribution.h index b4b434082776..bada8cfdd74a 100644 --- a/libcxx/include/__random/binomial_distribution.h +++ b/libcxx/include/__random/binomial_distribution.h @@ -97,13 +97,25 @@ public: } }; -// The LLVM C library provides this with conflicting `noexcept` attributes. -#if !defined(_LIBCPP_MSVCRT_LIKE) && !defined(__LLVM_LIBC__) -extern "C" double lgamma_r(double, int*); +// Some libc declares the math functions to be `noexcept`. +#if defined(_LIBCPP_GLIBC_PREREQ) +# if _LIBCPP_GLIBC_PREREQ(2, 8) +# define _LIBCPP_LGAMMA_R_NOEXCEPT _NOEXCEPT +# else +# define _LIBCPP_LGAMMA_R_NOEXCEPT +# endif +#elif defined(__LLVM_LIBC__) +# define _LIBCPP_LGAMMA_R_NOEXCEPT _NOEXCEPT +#else +# define _LIBCPP_LGAMMA_R_NOEXCEPT +#endif + +#if !defined(_LIBCPP_MSVCRT_LIKE) +extern "C" double lgamma_r(double, int*) _LIBCPP_LGAMMA_R_NOEXCEPT; #endif inline _LIBCPP_HIDE_FROM_ABI double __libcpp_lgamma(double __d) { -#if defined(_LIBCPP_MSVCRT_LIKE) || defined(__LLVM_LIBC__) +#if defined(_LIBCPP_MSVCRT_LIKE) return lgamma(__d); #else int __sign; diff --git a/libcxx/include/__ranges/as_rvalue_view.h b/libcxx/include/__ranges/as_rvalue_view.h index 5849a6c36839..08acf3d7736c 100644 --- a/libcxx/include/__ranges/as_rvalue_view.h +++ b/libcxx/include/__ranges/as_rvalue_view.h @@ -117,7 +117,7 @@ struct __fn : __range_adaptor_closure<__fn> { return /*---------------------------------*/ as_rvalue_view(std::forward<_Range>(__range)); } - template <class _Range> + template <input_range _Range> requires same_as<range_rvalue_reference_t<_Range>, range_reference_t<_Range>> [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Range&& __range) noexcept(noexcept(views::all(std::forward<_Range>(__range)))) diff --git a/libcxx/include/__string/constexpr_c_functions.h b/libcxx/include/__string/constexpr_c_functions.h index 119669e16bbc..160d2af10950 100644 --- a/libcxx/include/__string/constexpr_c_functions.h +++ b/libcxx/include/__string/constexpr_c_functions.h @@ -22,7 +22,6 @@ #include <__type_traits/is_equality_comparable.h> #include <__type_traits/is_integral.h> #include <__type_traits/is_same.h> -#include <__type_traits/is_trivially_copyable.h> #include <__type_traits/is_trivially_lexicographically_comparable.h> #include <__type_traits/remove_cv.h> #include <__utility/element_count.h> @@ -225,6 +224,8 @@ __constexpr_memmove(_Tp* __dest, _Up* __src, __element_count __n) { std::__assign_trivially_copyable(__dest[__i], __src[__i]); } } + } else if _LIBCPP_CONSTEXPR (sizeof(_Tp) == __datasizeof_v<_Tp>) { + ::__builtin_memmove(__dest, __src, __count * sizeof(_Tp)); } else if (__count > 0) { ::__builtin_memmove(__dest, __src, (__count - 1) * sizeof(_Tp) + __datasizeof_v<_Tp>); } diff --git a/libcxx/include/__system_error/error_category.h b/libcxx/include/__system_error/error_category.h index 7233e2211044..191f4d83a90c 100644 --- a/libcxx/include/__system_error/error_category.h +++ b/libcxx/include/__system_error/error_category.h @@ -20,7 +20,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD -class _LIBCPP_EXPORTED_FROM_ABI error_condition; +class error_condition; class _LIBCPP_EXPORTED_FROM_ABI error_code; class _LIBCPP_HIDDEN __do_message; diff --git a/libcxx/include/__thread/id.h b/libcxx/include/__thread/id.h index c9c86c80c859..14a51fc9ee88 100644 --- a/libcxx/include/__thread/id.h +++ b/libcxx/include/__thread/id.h @@ -23,7 +23,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD #if _LIBCPP_HAS_THREADS -class _LIBCPP_EXPORTED_FROM_ABI __thread_id; +class __thread_id; namespace this_thread { diff --git a/libcxx/include/__tree b/libcxx/include/__tree index 0f3640ef6a83..81a73342cc61 100644 --- a/libcxx/include/__tree +++ b/libcxx/include/__tree @@ -23,7 +23,6 @@ #include <__memory/pointer_traits.h> #include <__memory/swap_allocator.h> #include <__memory/unique_ptr.h> -#include <__type_traits/can_extract_key.h> #include <__type_traits/copy_cvref.h> #include <__type_traits/enable_if.h> #include <__type_traits/invoke.h> @@ -35,9 +34,11 @@ #include <__type_traits/is_swappable.h> #include <__type_traits/remove_const.h> #include <__utility/forward.h> +#include <__utility/lazy_synth_three_way_comparator.h> #include <__utility/move.h> #include <__utility/pair.h> #include <__utility/swap.h> +#include <__utility/try_key_extraction.h> #include <limits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -551,7 +552,7 @@ private: template <class _Pointer> class __tree_end_node { public: - typedef _Pointer pointer; + using pointer = _Pointer; pointer __left_; _LIBCPP_HIDE_FROM_ABI __tree_end_node() _NOEXCEPT : __left_() {} @@ -595,11 +596,11 @@ public: template <class _Allocator> class __tree_node_destructor { - typedef _Allocator allocator_type; - typedef allocator_traits<allocator_type> __alloc_traits; + using allocator_type = _Allocator; + using __alloc_traits _LIBCPP_NODEBUG = allocator_traits<allocator_type>; public: - typedef typename __alloc_traits::pointer pointer; + using pointer = typename __alloc_traits::pointer; private: allocator_type& __na_; @@ -636,10 +637,11 @@ struct __generic_container_node_destructor<__tree_node<_Tp, _VoidPtr>, _Alloc> : template <class _Tp, class _NodePtr, class _DiffType> class __tree_iterator { - typedef __tree_node_types<_NodePtr> _NodeTypes; - typedef _NodePtr __node_pointer; - typedef typename _NodeTypes::__node_base_pointer __node_base_pointer; - typedef typename _NodeTypes::__end_node_pointer __end_node_pointer; + using _NodeTypes _LIBCPP_NODEBUG = __tree_node_types<_NodePtr>; + // NOLINTNEXTLINE(libcpp-nodebug-on-aliases) lldb relies on this alias for pretty printing + using __node_pointer = _NodePtr; + using __node_base_pointer _LIBCPP_NODEBUG = typename _NodeTypes::__node_base_pointer; + using __end_node_pointer _LIBCPP_NODEBUG = typename _NodeTypes::__end_node_pointer; __end_node_pointer __ptr_; @@ -696,11 +698,11 @@ private: template <class _Tp, class _NodePtr, class _DiffType> class __tree_const_iterator { - typedef __tree_node_types<_NodePtr> _NodeTypes; + using _NodeTypes _LIBCPP_NODEBUG = __tree_node_types<_NodePtr>; // NOLINTNEXTLINE(libcpp-nodebug-on-aliases) lldb relies on this alias for pretty printing - using __node_pointer = _NodePtr; - typedef typename _NodeTypes::__node_base_pointer __node_base_pointer; - typedef typename _NodeTypes::__end_node_pointer __end_node_pointer; + using __node_pointer = _NodePtr; + using __node_base_pointer _LIBCPP_NODEBUG = typename _NodeTypes::__node_base_pointer; + using __end_node_pointer _LIBCPP_NODEBUG = typename _NodeTypes::__end_node_pointer; __end_node_pointer __ptr_; @@ -769,21 +771,20 @@ int __diagnose_non_const_comparator(); template <class _Tp, class _Compare, class _Allocator> class __tree { public: - using value_type = __get_node_value_type_t<_Tp>; - typedef _Compare value_compare; - typedef _Allocator allocator_type; + using value_type = __get_node_value_type_t<_Tp>; + using value_compare = _Compare; + using allocator_type = _Allocator; private: - typedef allocator_traits<allocator_type> __alloc_traits; - using key_type = __get_tree_key_type_t<_Tp>; + using __alloc_traits _LIBCPP_NODEBUG = allocator_traits<allocator_type>; + using key_type = __get_tree_key_type_t<_Tp>; public: - typedef typename __alloc_traits::pointer pointer; - typedef typename __alloc_traits::const_pointer const_pointer; - typedef typename __alloc_traits::size_type size_type; - typedef typename __alloc_traits::difference_type difference_type; + using pointer = typename __alloc_traits::pointer; + using const_pointer = typename __alloc_traits::const_pointer; + using size_type = typename __alloc_traits::size_type; + using difference_type = typename __alloc_traits::difference_type; -public: using __void_pointer _LIBCPP_NODEBUG = typename __alloc_traits::void_pointer; using __node _LIBCPP_NODEBUG = __tree_node<_Tp, __void_pointer>; @@ -798,8 +799,8 @@ public: using __parent_pointer _LIBCPP_NODEBUG = __end_node_pointer; // TODO: Remove this once the uses in <map> are removed - typedef __rebind_alloc<__alloc_traits, __node> __node_allocator; - typedef allocator_traits<__node_allocator> __node_traits; + using __node_allocator _LIBCPP_NODEBUG = __rebind_alloc<__alloc_traits, __node>; + using __node_traits _LIBCPP_NODEBUG = allocator_traits<__node_allocator>; // TODO(LLVM 22): Remove this check #ifndef _LIBCPP_ABI_TREE_REMOVE_NODE_POINTER_UB @@ -819,8 +820,8 @@ private: // the pointer using 'pointer_traits'. static_assert(is_same<__node_pointer, typename __node_traits::pointer>::value, "Allocator does not rebind pointers in a sane manner."); - typedef __rebind_alloc<__node_traits, __node_base> __node_base_allocator; - typedef allocator_traits<__node_base_allocator> __node_base_traits; + using __node_base_allocator _LIBCPP_NODEBUG = __rebind_alloc<__node_traits, __node_base>; + using __node_base_traits _LIBCPP_NODEBUG = allocator_traits<__node_base_allocator>; static_assert(is_same<__node_base_pointer, typename __node_base_traits::pointer>::value, "Allocator does not rebind pointers in a sane manner."); @@ -857,13 +858,25 @@ public: return std::addressof(__end_node()->__left_); } - typedef __tree_iterator<_Tp, __node_pointer, difference_type> iterator; - typedef __tree_const_iterator<_Tp, __node_pointer, difference_type> const_iterator; + using iterator = __tree_iterator<_Tp, __node_pointer, difference_type>; + using const_iterator = __tree_const_iterator<_Tp, __node_pointer, difference_type>; _LIBCPP_HIDE_FROM_ABI explicit __tree(const value_compare& __comp) _NOEXCEPT_( - is_nothrow_default_constructible<__node_allocator>::value&& is_nothrow_copy_constructible<value_compare>::value); - _LIBCPP_HIDE_FROM_ABI explicit __tree(const allocator_type& __a); - _LIBCPP_HIDE_FROM_ABI __tree(const value_compare& __comp, const allocator_type& __a); + is_nothrow_default_constructible<__node_allocator>::value&& is_nothrow_copy_constructible<value_compare>::value) + : __size_(0), __value_comp_(__comp) { + __begin_node_ = __end_node(); + } + + _LIBCPP_HIDE_FROM_ABI explicit __tree(const allocator_type& __a) + : __begin_node_(), __node_alloc_(__node_allocator(__a)), __size_(0) { + __begin_node_ = __end_node(); + } + + _LIBCPP_HIDE_FROM_ABI __tree(const value_compare& __comp, const allocator_type& __a) + : __begin_node_(), __node_alloc_(__node_allocator(__a)), __size_(0), __value_comp_(__comp) { + __begin_node_ = __end_node(); + } + _LIBCPP_HIDE_FROM_ABI __tree(const __tree& __t); _LIBCPP_HIDE_FROM_ABI __tree& operator=(const __tree& __t); template <class _ForwardIterator> @@ -873,13 +886,20 @@ public: _LIBCPP_HIDE_FROM_ABI __tree(__tree&& __t) _NOEXCEPT_( is_nothrow_move_constructible<__node_allocator>::value&& is_nothrow_move_constructible<value_compare>::value); _LIBCPP_HIDE_FROM_ABI __tree(__tree&& __t, const allocator_type& __a); + _LIBCPP_HIDE_FROM_ABI __tree& operator=(__tree&& __t) _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value && ((__node_traits::propagate_on_container_move_assignment::value && is_nothrow_move_assignable<__node_allocator>::value) || - allocator_traits<__node_allocator>::is_always_equal::value)); + allocator_traits<__node_allocator>::is_always_equal::value)) { + __move_assign(__t, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>()); + return *this; + } - _LIBCPP_HIDE_FROM_ABI ~__tree(); + _LIBCPP_HIDE_FROM_ABI ~__tree() { + static_assert(is_copy_constructible<value_compare>::value, "Comparator must be copy-constructible."); + destroy(__root()); + } _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return iterator(__begin_node_); } _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return const_iterator(__begin_node_); } @@ -900,88 +920,70 @@ public: _NOEXCEPT_(__is_nothrow_swappable_v<value_compare>); #endif - template <class _Key, class... _Args> - _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_key_args(_Key const&, _Args&&... __args); - template <class _Key, class... _Args> - _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&&...); - - template <class... _Args> - _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_impl(_Args&&... __args); - - template <class... _Args> - _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique_impl(const_iterator __p, _Args&&... __args); - template <class... _Args> _LIBCPP_HIDE_FROM_ABI iterator __emplace_multi(_Args&&... __args); template <class... _Args> _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); - template <class _Pp> - _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Pp&& __x) { - return __emplace_unique_extract_key(std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>()); - } - - template <class _First, - class _Second, - __enable_if_t<__can_extract_map_key<_First, key_type, value_type>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_First&& __f, _Second&& __s) { - return __emplace_unique_key_args(__f, std::forward<_First>(__f), std::forward<_Second>(__s)); - } - template <class... _Args> _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Args&&... __args) { - return __emplace_unique_impl(std::forward<_Args>(__args)...); - } - - template <class _Pp> - _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) { - return __emplace_unique_impl(std::forward<_Pp>(__x)); - } - - template <class _Pp> - _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) { - return __emplace_unique_key_args(__x, std::forward<_Pp>(__x)); - } - - template <class _Pp> - _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) { - return __emplace_unique_key_args(__x.first, std::forward<_Pp>(__x)); - } - - template <class _Pp> - _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _Pp&& __x) { - return __emplace_hint_unique_extract_key(__p, std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>()); - } - - template <class _First, - class _Second, - __enable_if_t<__can_extract_map_key<_First, key_type, value_type>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _First&& __f, _Second&& __s) { - return __emplace_hint_unique_key_args(__p, __f, std::forward<_First>(__f), std::forward<_Second>(__s)).first; + return std::__try_key_extraction<key_type>( + [this](const key_type& __key, _Args&&... __args2) { + auto [__parent, __child] = __find_equal(__key); + __node_pointer __r = static_cast<__node_pointer>(__child); + bool __inserted = false; + if (__child == nullptr) { + __node_holder __h = __construct_node(std::forward<_Args>(__args2)...); + __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); + __r = __h.release(); + __inserted = true; + } + return pair<iterator, bool>(iterator(__r), __inserted); + }, + [this](_Args&&... __args2) { + __node_holder __h = __construct_node(std::forward<_Args>(__args2)...); + auto [__parent, __child] = __find_equal(__h->__get_value()); + __node_pointer __r = static_cast<__node_pointer>(__child); + bool __inserted = false; + if (__child == nullptr) { + __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); + __r = __h.release(); + __inserted = true; + } + return pair<iterator, bool>(iterator(__r), __inserted); + }, + std::forward<_Args>(__args)...); } template <class... _Args> - _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _Args&&... __args) { - return __emplace_hint_unique_impl(__p, std::forward<_Args>(__args)...); - } - - template <class _Pp> - _LIBCPP_HIDE_FROM_ABI iterator - __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_fail_tag) { - return __emplace_hint_unique_impl(__p, std::forward<_Pp>(__x)); - } - - template <class _Pp> - _LIBCPP_HIDE_FROM_ABI iterator - __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_self_tag) { - return __emplace_hint_unique_key_args(__p, __x, std::forward<_Pp>(__x)).first; - } - - template <class _Pp> - _LIBCPP_HIDE_FROM_ABI iterator - __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_first_tag) { - return __emplace_hint_unique_key_args(__p, __x.first, std::forward<_Pp>(__x)).first; + _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_hint_unique(const_iterator __p, _Args&&... __args) { + return std::__try_key_extraction<key_type>( + [this, __p](const key_type& __key, _Args&&... __args2) { + __node_base_pointer __dummy; + auto [__parent, __child] = __find_equal(__p, __dummy, __key); + __node_pointer __r = static_cast<__node_pointer>(__child); + bool __inserted = false; + if (__child == nullptr) { + __node_holder __h = __construct_node(std::forward<_Args>(__args2)...); + __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); + __r = __h.release(); + __inserted = true; + } + return pair<iterator, bool>(iterator(__r), __inserted); + }, + [this, __p](_Args&&... __args2) { + __node_holder __h = __construct_node(std::forward<_Args>(__args2)...); + __node_base_pointer __dummy; + auto [__parent, __child] = __find_equal(__p, __dummy, __h->__get_value()); + __node_pointer __r = static_cast<__node_pointer>(__child); + if (__child == nullptr) { + __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); + __r = __h.release(); + } + return pair<iterator, bool>(iterator(__r), __child == nullptr); + }, + std::forward<_Args>(__args)...); } template <class _ValueT = _Tp, __enable_if_t<__is_tree_value_type_v<_ValueT>, int> = 0> @@ -1039,6 +1041,56 @@ public: _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(__node_pointer __nd); _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); + template <class _InIter, class _Sent> + _LIBCPP_HIDE_FROM_ABI void __insert_range_unique(_InIter __first, _Sent __last) { + if (__first == __last) + return; + + if (__root() == nullptr) { + __insert_node_at( + __end_node(), __end_node()->__left_, static_cast<__node_base_pointer>(__construct_node(*__first).release())); + ++__first; + } + + auto __max_node = static_cast<__node_pointer>(std::__tree_max(static_cast<__node_base_pointer>(__root()))); + + using __reference = decltype(*__first); + + for (; __first != __last; ++__first) { + std::__try_key_extraction<key_type>( + [this, &__max_node](const key_type& __key, __reference&& __val) { + if (value_comp()(__max_node->__get_value(), __key)) { // __key > __max_node + __node_holder __nd = __construct_node(std::forward<__reference>(__val)); + __insert_node_at(static_cast<__end_node_pointer>(__max_node), + __max_node->__right_, + static_cast<__node_base_pointer>(__nd.get())); + __max_node = __nd.release(); + } else { + auto [__parent, __child] = __find_equal(__key); + if (__child == nullptr) { + __node_holder __nd = __construct_node(std::forward<__reference>(__val)); + __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd.release())); + } + } + }, + [this, &__max_node](__reference&& __val) { + __node_holder __nd = __construct_node(std::forward<__reference>(__val)); + if (value_comp()(__max_node->__get_value(), __nd->__get_value())) { // __node > __max_node + __insert_node_at(static_cast<__end_node_pointer>(__max_node), + __max_node->__right_, + static_cast<__node_base_pointer>(__nd.get())); + __max_node = __nd.release(); + } else { + auto [__parent, __child] = __find_equal(__nd->__get_value()); + if (__child == nullptr) { + __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd.release())); + } + } + }, + *__first); + } + } + _LIBCPP_HIDE_FROM_ABI iterator __remove_node_pointer(__node_pointer) _NOEXCEPT; #if _LIBCPP_STD_VER >= 17 @@ -1074,8 +1126,7 @@ public: template <class _Key> _LIBCPP_HIDE_FROM_ABI iterator find(const _Key& __key) { - __end_node_pointer __parent; - __node_base_pointer __match = __find_equal(__parent, __key); + auto [__, __match] = __find_equal(__key); if (__match == nullptr) return end(); return iterator(static_cast<__node_pointer>(__match)); @@ -1083,8 +1134,7 @@ public: template <class _Key> _LIBCPP_HIDE_FROM_ABI const_iterator find(const _Key& __key) const { - __end_node_pointer __parent; - __node_base_pointer __match = __find_equal(__parent, __key); + auto [__, __match] = __find_equal(__key); if (__match == nullptr) return end(); return const_iterator(static_cast<__node_pointer>(__match)); @@ -1131,22 +1181,24 @@ public: template <class _Key> _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> __equal_range_multi(const _Key& __k) const; - typedef __tree_node_destructor<__node_allocator> _Dp; - typedef unique_ptr<__node, _Dp> __node_holder; + using _Dp _LIBCPP_NODEBUG = __tree_node_destructor<__node_allocator>; + using __node_holder _LIBCPP_NODEBUG = unique_ptr<__node, _Dp>; _LIBCPP_HIDE_FROM_ABI __node_holder remove(const_iterator __p) _NOEXCEPT; // FIXME: Make this function const qualified. Unfortunately doing so // breaks existing code which uses non-const callable comparators. template <class _Key> - _LIBCPP_HIDE_FROM_ABI __node_base_pointer& __find_equal(__end_node_pointer& __parent, const _Key& __v); + _LIBCPP_HIDE_FROM_ABI pair<__end_node_pointer, __node_base_pointer&> __find_equal(const _Key& __v); + template <class _Key> - _LIBCPP_HIDE_FROM_ABI __node_base_pointer& __find_equal(__end_node_pointer& __parent, const _Key& __v) const { - return const_cast<__tree*>(this)->__find_equal(__parent, __v); + _LIBCPP_HIDE_FROM_ABI pair<__end_node_pointer, __node_base_pointer&> __find_equal(const _Key& __v) const { + return const_cast<__tree*>(this)->__find_equal(__v); } + template <class _Key> - _LIBCPP_HIDE_FROM_ABI __node_base_pointer& - __find_equal(const_iterator __hint, __end_node_pointer& __parent, __node_base_pointer& __dummy, const _Key& __v); + _LIBCPP_HIDE_FROM_ABI pair<__end_node_pointer, __node_base_pointer&> + __find_equal(const_iterator __hint, __node_base_pointer& __dummy, const _Key& __v); _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __tree& __t) { __copy_assign_alloc(__t, integral_constant<bool, __node_traits::propagate_on_container_copy_assignment::value>()); @@ -1171,7 +1223,7 @@ private: _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(_Args&&... __args); // TODO: Make this _LIBCPP_HIDE_FROM_ABI - _LIBCPP_HIDDEN void destroy(__node_pointer __nd) _NOEXCEPT; + _LIBCPP_HIDDEN void destroy(__node_pointer __nd) _NOEXCEPT { (__tree_deleter(__node_alloc_))(__nd); } _LIBCPP_HIDE_FROM_ABI void __move_assign(__tree& __t, false_type); _LIBCPP_HIDE_FROM_ABI void __move_assign(__tree& __t, true_type) _NOEXCEPT_( @@ -1340,25 +1392,6 @@ private: } }; -template <class _Tp, class _Compare, class _Allocator> -__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp) _NOEXCEPT_( - is_nothrow_default_constructible<__node_allocator>::value&& is_nothrow_copy_constructible<value_compare>::value) - : __size_(0), __value_comp_(__comp) { - __begin_node_ = __end_node(); -} - -template <class _Tp, class _Compare, class _Allocator> -__tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a) - : __begin_node_(), __node_alloc_(__node_allocator(__a)), __size_(0) { - __begin_node_ = __end_node(); -} - -template <class _Tp, class _Compare, class _Allocator> -__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp, const allocator_type& __a) - : __begin_node_(), __node_alloc_(__node_allocator(__a)), __size_(0), __value_comp_(__comp) { - __begin_node_ = __end_node(); -} - // Precondition: __size_ != 0 template <class _Tp, class _Compare, class _Allocator> typename __tree<_Tp, _Compare, _Allocator>::__node_pointer @@ -1425,8 +1458,8 @@ __tree<_Tp, _Compare, _Allocator>& __tree<_Tp, _Compare, _Allocator>::operator=( template <class _Tp, class _Compare, class _Allocator> template <class _ForwardIterator> void __tree<_Tp, _Compare, _Allocator>::__assign_unique(_ForwardIterator __first, _ForwardIterator __last) { - typedef iterator_traits<_ForwardIterator> _ITraits; - typedef typename _ITraits::value_type _ItValueType; + using _ITraits = iterator_traits<_ForwardIterator>; + using _ItValueType = typename _ITraits::value_type; static_assert( is_same<_ItValueType, value_type>::value, "__assign_unique may only be called with the containers value type"); static_assert( @@ -1445,8 +1478,8 @@ void __tree<_Tp, _Compare, _Allocator>::__assign_unique(_ForwardIterator __first template <class _Tp, class _Compare, class _Allocator> template <class _InputIterator> void __tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last) { - typedef iterator_traits<_InputIterator> _ITraits; - typedef typename _ITraits::value_type _ItValueType; + using _ITraits = iterator_traits<_InputIterator>; + using _ItValueType = typename _ITraits::value_type; static_assert( is_same<_ItValueType, value_type>::value, "__assign_multi may only be called with the containers value_type"); if (__size_ != 0) { @@ -1556,27 +1589,6 @@ void __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type) { } template <class _Tp, class _Compare, class _Allocator> -__tree<_Tp, _Compare, _Allocator>& __tree<_Tp, _Compare, _Allocator>::operator=(__tree&& __t) - _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value && - ((__node_traits::propagate_on_container_move_assignment::value && - is_nothrow_move_assignable<__node_allocator>::value) || - allocator_traits<__node_allocator>::is_always_equal::value)) { - __move_assign(__t, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>()); - return *this; -} - -template <class _Tp, class _Compare, class _Allocator> -__tree<_Tp, _Compare, _Allocator>::~__tree() { - static_assert(is_copy_constructible<value_compare>::value, "Comparator must be copy-constructible."); - destroy(__root()); -} - -template <class _Tp, class _Compare, class _Allocator> -void __tree<_Tp, _Compare, _Allocator>::destroy(__node_pointer __nd) _NOEXCEPT { - (__tree_deleter(__node_alloc_))(__nd); -} - -template <class _Tp, class _Compare, class _Allocator> void __tree<_Tp, _Compare, _Allocator>::swap(__tree& __t) #if _LIBCPP_STD_VER <= 11 _NOEXCEPT_(__is_nothrow_swappable_v<value_compare> && @@ -1699,92 +1711,89 @@ typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& __tree<_Tp, _Co return __find_leaf_low(__parent, __v); } -// Find place to insert if __v doesn't exist -// Set __parent to parent of null leaf -// Return reference to null leaf -// If __v exists, set parent to node of __v and return reference to node of __v +// Find __v +// If __v exists, return the parent of the node of __v and a reference to the pointer to the node of __v. +// If __v doesn't exist, return the parent of the null leaf and a reference to the pointer to the null leaf. template <class _Tp, class _Compare, class _Allocator> template <class _Key> -typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& -__tree<_Tp, _Compare, _Allocator>::__find_equal(__end_node_pointer& __parent, const _Key& __v) { - __node_pointer __nd = __root(); - __node_base_pointer* __nd_ptr = __root_ptr(); - if (__nd != nullptr) { - while (true) { - if (value_comp()(__v, __nd->__get_value())) { - if (__nd->__left_ != nullptr) { - __nd_ptr = std::addressof(__nd->__left_); - __nd = static_cast<__node_pointer>(__nd->__left_); - } else { - __parent = static_cast<__end_node_pointer>(__nd); - return __parent->__left_; - } - } else if (value_comp()(__nd->__get_value(), __v)) { - if (__nd->__right_ != nullptr) { - __nd_ptr = std::addressof(__nd->__right_); - __nd = static_cast<__node_pointer>(__nd->__right_); - } else { - __parent = static_cast<__end_node_pointer>(__nd); - return __nd->__right_; - } - } else { - __parent = static_cast<__end_node_pointer>(__nd); - return *__nd_ptr; - } +_LIBCPP_HIDE_FROM_ABI pair<typename __tree<_Tp, _Compare, _Allocator>::__end_node_pointer, + typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&> +__tree<_Tp, _Compare, _Allocator>::__find_equal(const _Key& __v) { + using _Pair = pair<__end_node_pointer, __node_base_pointer&>; + + __node_pointer __nd = __root(); + + if (__nd == nullptr) { + auto __end = __end_node(); + return _Pair(__end, __end->__left_); + } + + __node_base_pointer* __node_ptr = __root_ptr(); + auto __comp = __lazy_synth_three_way_comparator<_Compare, _Key, value_type>(value_comp()); + + while (true) { + auto __comp_res = __comp(__v, __nd->__get_value()); + + if (__comp_res.__less()) { + if (__nd->__left_ == nullptr) + return _Pair(static_cast<__end_node_pointer>(__nd), __nd->__left_); + + __node_ptr = std::addressof(__nd->__left_); + __nd = static_cast<__node_pointer>(__nd->__left_); + } else if (__comp_res.__greater()) { + if (__nd->__right_ == nullptr) + return _Pair(static_cast<__end_node_pointer>(__nd), __nd->__right_); + + __node_ptr = std::addressof(__nd->__right_); + __nd = static_cast<__node_pointer>(__nd->__right_); + } else { + return _Pair(static_cast<__end_node_pointer>(__nd), *__node_ptr); } } - __parent = __end_node(); - return __parent->__left_; } -// Find place to insert if __v doesn't exist +// Find __v // First check prior to __hint. // Next check after __hint. // Next do O(log N) search. -// Set __parent to parent of null leaf -// Return reference to null leaf -// If __v exists, set parent to node of __v and return reference to node of __v +// If __v exists, return the parent of the node of __v and a reference to the pointer to the node of __v. +// If __v doesn't exist, return the parent of the null leaf and a reference to the pointer to the null leaf. template <class _Tp, class _Compare, class _Allocator> template <class _Key> -typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& __tree<_Tp, _Compare, _Allocator>::__find_equal( - const_iterator __hint, __end_node_pointer& __parent, __node_base_pointer& __dummy, const _Key& __v) { - if (__hint == end() || value_comp()(__v, *__hint)) // check before - { +_LIBCPP_HIDE_FROM_ABI pair<typename __tree<_Tp, _Compare, _Allocator>::__end_node_pointer, + typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&> +__tree<_Tp, _Compare, _Allocator>::__find_equal(const_iterator __hint, __node_base_pointer& __dummy, const _Key& __v) { + using _Pair = pair<__end_node_pointer, __node_base_pointer&>; + + if (__hint == end() || value_comp()(__v, *__hint)) { // check before // __v < *__hint const_iterator __prior = __hint; if (__prior == begin() || value_comp()(*--__prior, __v)) { // *prev(__hint) < __v < *__hint - if (__hint.__ptr_->__left_ == nullptr) { - __parent = __hint.__ptr_; - return __parent->__left_; - } else { - __parent = __prior.__ptr_; - return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_; - } + if (__hint.__ptr_->__left_ == nullptr) + return _Pair(__hint.__ptr_, __hint.__ptr_->__left_); + return _Pair(__prior.__ptr_, static_cast<__node_pointer>(__prior.__ptr_)->__right_); } // __v <= *prev(__hint) - return __find_equal(__parent, __v); - } else if (value_comp()(*__hint, __v)) // check after - { + return __find_equal(__v); + } + + if (value_comp()(*__hint, __v)) { // check after // *__hint < __v const_iterator __next = std::next(__hint); if (__next == end() || value_comp()(__v, *__next)) { // *__hint < __v < *std::next(__hint) - if (__hint.__get_np()->__right_ == nullptr) { - __parent = __hint.__ptr_; - return static_cast<__node_base_pointer>(__hint.__ptr_)->__right_; - } else { - __parent = __next.__ptr_; - return __parent->__left_; - } + if (__hint.__get_np()->__right_ == nullptr) + return _Pair(__hint.__ptr_, static_cast<__node_pointer>(__hint.__ptr_)->__right_); + return _Pair(__next.__ptr_, __next.__ptr_->__left_); } // *next(__hint) <= __v - return __find_equal(__parent, __v); + return __find_equal(__v); } + // else __v == *__hint - __parent = __hint.__ptr_; - __dummy = static_cast<__node_base_pointer>(__hint.__ptr_); - return __dummy; + __dummy = static_cast<__node_base_pointer>(__hint.__ptr_); + return _Pair(__hint.__ptr_, __dummy); } template <class _Tp, class _Compare, class _Allocator> @@ -1802,42 +1811,6 @@ void __tree<_Tp, _Compare, _Allocator>::__insert_node_at( } template <class _Tp, class _Compare, class _Allocator> -template <class _Key, class... _Args> -pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> -__tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) { - __end_node_pointer __parent; - __node_base_pointer& __child = __find_equal(__parent, __k); - __node_pointer __r = static_cast<__node_pointer>(__child); - bool __inserted = false; - if (__child == nullptr) { - __node_holder __h = __construct_node(std::forward<_Args>(__args)...); - __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); - __r = __h.release(); - __inserted = true; - } - return pair<iterator, bool>(iterator(__r), __inserted); -} - -template <class _Tp, class _Compare, class _Allocator> -template <class _Key, class... _Args> -pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> -__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args( - const_iterator __p, _Key const& __k, _Args&&... __args) { - __end_node_pointer __parent; - __node_base_pointer __dummy; - __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __k); - __node_pointer __r = static_cast<__node_pointer>(__child); - bool __inserted = false; - if (__child == nullptr) { - __node_holder __h = __construct_node(std::forward<_Args>(__args)...); - __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); - __r = __h.release(); - __inserted = true; - } - return pair<iterator, bool>(iterator(__r), __inserted); -} - -template <class _Tp, class _Compare, class _Allocator> template <class... _Args> typename __tree<_Tp, _Compare, _Allocator>::__node_holder __tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&&... __args) { @@ -1850,39 +1823,6 @@ __tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&&... __args) { template <class _Tp, class _Compare, class _Allocator> template <class... _Args> -pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> -__tree<_Tp, _Compare, _Allocator>::__emplace_unique_impl(_Args&&... __args) { - __node_holder __h = __construct_node(std::forward<_Args>(__args)...); - __end_node_pointer __parent; - __node_base_pointer& __child = __find_equal(__parent, __h->__get_value()); - __node_pointer __r = static_cast<__node_pointer>(__child); - bool __inserted = false; - if (__child == nullptr) { - __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); - __r = __h.release(); - __inserted = true; - } - return pair<iterator, bool>(iterator(__r), __inserted); -} - -template <class _Tp, class _Compare, class _Allocator> -template <class... _Args> -typename __tree<_Tp, _Compare, _Allocator>::iterator -__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_impl(const_iterator __p, _Args&&... __args) { - __node_holder __h = __construct_node(std::forward<_Args>(__args)...); - __end_node_pointer __parent; - __node_base_pointer __dummy; - __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __h->__get_value()); - __node_pointer __r = static_cast<__node_pointer>(__child); - if (__child == nullptr) { - __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); - __r = __h.release(); - } - return iterator(__r); -} - -template <class _Tp, class _Compare, class _Allocator> -template <class... _Args> typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args) { __node_holder __h = __construct_node(std::forward<_Args>(__args)...); @@ -1906,10 +1846,9 @@ __tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p, _Arg template <class _Tp, class _Compare, class _Allocator> pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> __tree<_Tp, _Compare, _Allocator>::__node_assign_unique(const value_type& __v, __node_pointer __nd) { - __end_node_pointer __parent; - __node_base_pointer& __child = __find_equal(__parent, __v); - __node_pointer __r = static_cast<__node_pointer>(__child); - bool __inserted = false; + auto [__parent, __child] = __find_equal(__v); + __node_pointer __r = static_cast<__node_pointer>(__child); + bool __inserted = false; if (__child == nullptr) { __assign_value(__nd->__get_value(), __v); __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); @@ -1958,8 +1897,7 @@ __tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(_NodeHandle&& __n return _InsertReturnType{end(), false, _NodeHandle()}; __node_pointer __ptr = __nh.__ptr_; - __end_node_pointer __parent; - __node_base_pointer& __child = __find_equal(__parent, __ptr->__get_value()); + auto [__parent, __child] = __find_equal(__ptr->__get_value()); if (__child != nullptr) return _InsertReturnType{iterator(static_cast<__node_pointer>(__child)), false, std::move(__nh)}; @@ -1976,10 +1914,9 @@ __tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(const_iterator __ return end(); __node_pointer __ptr = __nh.__ptr_; - __end_node_pointer __parent; __node_base_pointer __dummy; - __node_base_pointer& __child = __find_equal(__hint, __parent, __dummy, __ptr->__get_value()); - __node_pointer __r = static_cast<__node_pointer>(__child); + auto [__parent, __child] = __find_equal(__hint, __dummy, __ptr->__get_value()); + __node_pointer __r = static_cast<__node_pointer>(__child); if (__child == nullptr) { __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr)); __r = __ptr; @@ -2012,8 +1949,7 @@ _LIBCPP_HIDE_FROM_ABI void __tree<_Tp, _Compare, _Allocator>::__node_handle_merg for (typename _Tree::iterator __i = __source.begin(); __i != __source.end();) { __node_pointer __src_ptr = __i.__get_np(); - __end_node_pointer __parent; - __node_base_pointer& __child = __find_equal(__parent, __src_ptr->__get_value()); + auto [__parent, __child] = __find_equal(__src_ptr->__get_value()); ++__i; if (__child != nullptr) continue; @@ -2113,10 +2049,12 @@ template <class _Key> typename __tree<_Tp, _Compare, _Allocator>::size_type __tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const { __node_pointer __rt = __root(); + auto __comp = __lazy_synth_three_way_comparator<value_compare, _Key, value_type>(value_comp()); while (__rt != nullptr) { - if (value_comp()(__k, __rt->__get_value())) { + auto __comp_res = __comp(__k, __rt->__get_value()); + if (__comp_res.__less()) { __rt = static_cast<__node_pointer>(__rt->__left_); - } else if (value_comp()(__rt->__get_value(), __k)) + } else if (__comp_res.__greater()) __rt = static_cast<__node_pointer>(__rt->__right_); else return 1; @@ -2130,11 +2068,13 @@ typename __tree<_Tp, _Compare, _Allocator>::size_type __tree<_Tp, _Compare, _Allocator>::__count_multi(const _Key& __k) const { __end_node_pointer __result = __end_node(); __node_pointer __rt = __root(); + auto __comp = __lazy_synth_three_way_comparator<value_compare, _Key, value_type>(value_comp()); while (__rt != nullptr) { - if (value_comp()(__k, __rt->__get_value())) { + auto __comp_res = __comp(__k, __rt->__get_value()); + if (__comp_res.__less()) { __result = static_cast<__end_node_pointer>(__rt); __rt = static_cast<__node_pointer>(__rt->__left_); - } else if (value_comp()(__rt->__get_value(), __k)) + } else if (__comp_res.__greater()) __rt = static_cast<__node_pointer>(__rt->__right_); else return std::distance( @@ -2204,14 +2144,16 @@ template <class _Tp, class _Compare, class _Allocator> template <class _Key> pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, typename __tree<_Tp, _Compare, _Allocator>::iterator> __tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) { - typedef pair<iterator, iterator> _Pp; + using _Pp = pair<iterator, iterator>; __end_node_pointer __result = __end_node(); __node_pointer __rt = __root(); + auto __comp = __lazy_synth_three_way_comparator<value_compare, _Key, value_type>(value_comp()); while (__rt != nullptr) { - if (value_comp()(__k, __rt->__get_value())) { + auto __comp_res = __comp(__k, __rt->__get_value()); + if (__comp_res.__less()) { __result = static_cast<__end_node_pointer>(__rt); __rt = static_cast<__node_pointer>(__rt->__left_); - } else if (value_comp()(__rt->__get_value(), __k)) + } else if (__comp_res.__greater()) __rt = static_cast<__node_pointer>(__rt->__right_); else return _Pp(iterator(__rt), @@ -2226,14 +2168,16 @@ template <class _Key> pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator, typename __tree<_Tp, _Compare, _Allocator>::const_iterator> __tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const { - typedef pair<const_iterator, const_iterator> _Pp; + using _Pp = pair<const_iterator, const_iterator>; __end_node_pointer __result = __end_node(); __node_pointer __rt = __root(); + auto __comp = __lazy_synth_three_way_comparator<value_compare, _Key, value_type>(value_comp()); while (__rt != nullptr) { - if (value_comp()(__k, __rt->__get_value())) { + auto __comp_res = __comp(__k, __rt->__get_value()); + if (__comp_res.__less()) { __result = static_cast<__end_node_pointer>(__rt); __rt = static_cast<__node_pointer>(__rt->__left_); - } else if (value_comp()(__rt->__get_value(), __k)) + } else if (__comp_res.__greater()) __rt = static_cast<__node_pointer>(__rt->__right_); else return _Pp( @@ -2248,14 +2192,16 @@ template <class _Tp, class _Compare, class _Allocator> template <class _Key> pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, typename __tree<_Tp, _Compare, _Allocator>::iterator> __tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) { - typedef pair<iterator, iterator> _Pp; + using _Pp = pair<iterator, iterator>; __end_node_pointer __result = __end_node(); - __node_pointer __rt = __root(); + __node_pointer __rt = __root(); + auto __comp = __lazy_synth_three_way_comparator<value_compare, _Key, value_type>(value_comp()); while (__rt != nullptr) { - if (value_comp()(__k, __rt->__get_value())) { + auto __comp_res = __comp(__k, __rt->__get_value()); + if (__comp_res.__less()) { __result = static_cast<__end_node_pointer>(__rt); __rt = static_cast<__node_pointer>(__rt->__left_); - } else if (value_comp()(__rt->__get_value(), __k)) + } else if (__comp_res.__greater()) __rt = static_cast<__node_pointer>(__rt->__right_); else return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__end_node_pointer>(__rt)), @@ -2269,14 +2215,16 @@ template <class _Key> pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator, typename __tree<_Tp, _Compare, _Allocator>::const_iterator> __tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const { - typedef pair<const_iterator, const_iterator> _Pp; + using _Pp = pair<const_iterator, const_iterator>; __end_node_pointer __result = __end_node(); - __node_pointer __rt = __root(); + __node_pointer __rt = __root(); + auto __comp = __lazy_synth_three_way_comparator<value_compare, _Key, value_type>(value_comp()); while (__rt != nullptr) { - if (value_comp()(__k, __rt->__get_value())) { + auto __comp_res = __comp(__k, __rt->__get_value()); + if (__comp_res.__less()) { __result = static_cast<__end_node_pointer>(__rt); __rt = static_cast<__node_pointer>(__rt->__left_); - } else if (value_comp()(__rt->__get_value(), __k)) + } else if (__comp_res.__greater()) __rt = static_cast<__node_pointer>(__rt->__right_); else return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__end_node_pointer>(__rt)), diff --git a/libcxx/include/__tuple/make_tuple_types.h b/libcxx/include/__tuple/make_tuple_types.h deleted file mode 100644 index 3c22ec85dc9c..000000000000 --- a/libcxx/include/__tuple/make_tuple_types.h +++ /dev/null @@ -1,77 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___TUPLE_MAKE_TUPLE_TYPES_H -#define _LIBCPP___TUPLE_MAKE_TUPLE_TYPES_H - -#include <__config> -#include <__cstddef/size_t.h> -#include <__fwd/array.h> -#include <__fwd/tuple.h> -#include <__tuple/tuple_element.h> -#include <__tuple/tuple_size.h> -#include <__tuple/tuple_types.h> -#include <__type_traits/copy_cvref.h> -#include <__type_traits/remove_cvref.h> -#include <__type_traits/remove_reference.h> -#include <__utility/integer_sequence.h> - -#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -# pragma GCC system_header -#endif - -#ifndef _LIBCPP_CXX03_LANG - -_LIBCPP_BEGIN_NAMESPACE_STD - -// __make_tuple_types<_Tuple<_Types...>, _Ep, _Sp>::type is a -// __tuple_types<_Types...> using only those _Types in the range [_Sp, _Ep). -// _Sp defaults to 0 and _Ep defaults to tuple_size<_Tuple>. If _Tuple is a -// lvalue_reference type, then __tuple_types<_Types&...> is the result. - -template <class _TupleTypes, class _TupleIndices> -struct __make_tuple_types_flat; - -template <template <class...> class _Tuple, class... _Types, size_t... _Idx> -struct __make_tuple_types_flat<_Tuple<_Types...>, __index_sequence<_Idx...>> { - // Specialization for pair, tuple, and __tuple_types - template <class _Tp> - using __apply_quals _LIBCPP_NODEBUG = __tuple_types<__copy_cvref_t<_Tp, __type_pack_element<_Idx, _Types...>>...>; -}; - -template <class _Vt, size_t _Np, size_t... _Idx> -struct __make_tuple_types_flat<array<_Vt, _Np>, __index_sequence<_Idx...>> { - template <size_t> - using __value_type _LIBCPP_NODEBUG = _Vt; - template <class _Tp> - using __apply_quals _LIBCPP_NODEBUG = __tuple_types<__copy_cvref_t<_Tp, __value_type<_Idx>>...>; -}; - -template <class _Tp> -struct __make_tuple_types { - using _RawTp _LIBCPP_NODEBUG = __remove_cvref_t<_Tp>; - using _Maker _LIBCPP_NODEBUG = - __make_tuple_types_flat<_RawTp, __make_index_sequence<tuple_size<__libcpp_remove_reference_t<_Tp>>::value>>; - using type _LIBCPP_NODEBUG = typename _Maker::template __apply_quals<_Tp>; -}; - -template <class... _Types> -struct __make_tuple_types<tuple<_Types...>> { - using type _LIBCPP_NODEBUG = __tuple_types<_Types...>; -}; - -template <class... _Types> -struct __make_tuple_types<__tuple_types<_Types...>> { - using type _LIBCPP_NODEBUG = __tuple_types<_Types...>; -}; - -_LIBCPP_END_NAMESPACE_STD - -#endif // _LIBCPP_CXX03_LANG - -#endif // _LIBCPP___TUPLE_MAKE_TUPLE_TYPES_H diff --git a/libcxx/include/__tuple/sfinae_helpers.h b/libcxx/include/__tuple/sfinae_helpers.h index f314381d0a48..f81048f4062b 100644 --- a/libcxx/include/__tuple/sfinae_helpers.h +++ b/libcxx/include/__tuple/sfinae_helpers.h @@ -19,7 +19,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD #ifndef _LIBCPP_CXX03_LANG -struct _LIBCPP_EXPORTED_FROM_ABI __check_tuple_constructor_fail { +struct __check_tuple_constructor_fail { static _LIBCPP_HIDE_FROM_ABI constexpr bool __enable_explicit_default() { return false; } static _LIBCPP_HIDE_FROM_ABI constexpr bool __enable_implicit_default() { return false; } template <class...> diff --git a/libcxx/include/__tuple/tuple_element.h b/libcxx/include/__tuple/tuple_element.h index 607ac3a453de..50a98079ccf8 100644 --- a/libcxx/include/__tuple/tuple_element.h +++ b/libcxx/include/__tuple/tuple_element.h @@ -11,7 +11,6 @@ #include <__config> #include <__cstddef/size_t.h> -#include <__tuple/tuple_types.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -37,21 +36,11 @@ struct tuple_element<_Ip, const volatile _Tp> { using type _LIBCPP_NODEBUG = const volatile typename tuple_element<_Ip, _Tp>::type; }; -#ifndef _LIBCPP_CXX03_LANG - -template <size_t _Ip, class... _Types> -struct tuple_element<_Ip, __tuple_types<_Types...> > { - static_assert(_Ip < sizeof...(_Types), "tuple_element index out of range"); - using type _LIBCPP_NODEBUG = __type_pack_element<_Ip, _Types...>; -}; - # if _LIBCPP_STD_VER >= 14 template <size_t _Ip, class... _Tp> using tuple_element_t _LIBCPP_NODEBUG = typename tuple_element<_Ip, _Tp...>::type; # endif -#endif // _LIBCPP_CXX03_LANG - _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___TUPLE_TUPLE_ELEMENT_H diff --git a/libcxx/include/__tuple/tuple_like_ext.h b/libcxx/include/__tuple/tuple_like_ext.h index 45c0e65d62ff..5a6748a9cc79 100644 --- a/libcxx/include/__tuple/tuple_like_ext.h +++ b/libcxx/include/__tuple/tuple_like_ext.h @@ -14,7 +14,6 @@ #include <__fwd/array.h> #include <__fwd/pair.h> #include <__fwd/tuple.h> -#include <__tuple/tuple_types.h> #include <__type_traits/integral_constant.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -26,13 +25,6 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _Tp> struct __tuple_like_ext : false_type {}; -template <class _Tp> -struct __tuple_like_ext<const _Tp> : public __tuple_like_ext<_Tp> {}; -template <class _Tp> -struct __tuple_like_ext<volatile _Tp> : public __tuple_like_ext<_Tp> {}; -template <class _Tp> -struct __tuple_like_ext<const volatile _Tp> : public __tuple_like_ext<_Tp> {}; - #ifndef _LIBCPP_CXX03_LANG template <class... _Tp> struct __tuple_like_ext<tuple<_Tp...> > : true_type {}; @@ -44,9 +36,6 @@ struct __tuple_like_ext<pair<_T1, _T2> > : true_type {}; template <class _Tp, size_t _Size> struct __tuple_like_ext<array<_Tp, _Size> > : true_type {}; -template <class... _Tp> -struct __tuple_like_ext<__tuple_types<_Tp...> > : true_type {}; - _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___TUPLE_TUPLE_LIKE_EXT_H diff --git a/libcxx/include/__tuple/tuple_size.h b/libcxx/include/__tuple/tuple_size.h index 3308c000dc11..60f2a667a1ba 100644 --- a/libcxx/include/__tuple/tuple_size.h +++ b/libcxx/include/__tuple/tuple_size.h @@ -59,9 +59,6 @@ struct tuple_size<const volatile _Tp> : public tuple_size<_Tp> {}; template <class... _Tp> struct tuple_size<tuple<_Tp...> > : public integral_constant<size_t, sizeof...(_Tp)> {}; -template <class... _Tp> -struct tuple_size<__tuple_types<_Tp...> > : public integral_constant<size_t, sizeof...(_Tp)> {}; - # if _LIBCPP_STD_VER >= 17 template <class _Tp> inline constexpr size_t tuple_size_v = tuple_size<_Tp>::value; diff --git a/libcxx/include/__type_traits/can_extract_key.h b/libcxx/include/__type_traits/can_extract_key.h deleted file mode 100644 index b8359d070881..000000000000 --- a/libcxx/include/__type_traits/can_extract_key.h +++ /dev/null @@ -1,53 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___TYPE_TRAITS_CAN_EXTRACT_KEY_H -#define _LIBCPP___TYPE_TRAITS_CAN_EXTRACT_KEY_H - -#include <__config> -#include <__fwd/pair.h> -#include <__type_traits/conditional.h> -#include <__type_traits/integral_constant.h> -#include <__type_traits/is_same.h> -#include <__type_traits/remove_const.h> -#include <__type_traits/remove_const_ref.h> - -#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -# pragma GCC system_header -#endif - -_LIBCPP_BEGIN_NAMESPACE_STD - -// These traits are used in __tree and __hash_table -struct __extract_key_fail_tag {}; -struct __extract_key_self_tag {}; -struct __extract_key_first_tag {}; - -template <class _ValTy, class _Key, class _RawValTy = __remove_const_ref_t<_ValTy> > -struct __can_extract_key - : __conditional_t<_IsSame<_RawValTy, _Key>::value, __extract_key_self_tag, __extract_key_fail_tag> {}; - -template <class _Pair, class _Key, class _First, class _Second> -struct __can_extract_key<_Pair, _Key, pair<_First, _Second> > - : __conditional_t<_IsSame<__remove_const_t<_First>, _Key>::value, __extract_key_first_tag, __extract_key_fail_tag> { -}; - -// __can_extract_map_key uses true_type/false_type instead of the tags. -// It returns true if _Key != _ContainerValueTy (the container is a map not a set) -// and _ValTy == _Key. -template <class _ValTy, class _Key, class _ContainerValueTy, class _RawValTy = __remove_const_ref_t<_ValTy> > -struct __can_extract_map_key : integral_constant<bool, _IsSame<_RawValTy, _Key>::value> {}; - -// This specialization returns __extract_key_fail_tag for non-map containers -// because _Key == _ContainerValueTy -template <class _ValTy, class _Key, class _RawValTy> -struct __can_extract_map_key<_ValTy, _Key, _Key, _RawValTy> : false_type {}; - -_LIBCPP_END_NAMESPACE_STD - -#endif // _LIBCPP___TYPE_TRAITS_CAN_EXTRACT_KEY_H diff --git a/libcxx/include/__type_traits/invoke.h b/libcxx/include/__type_traits/invoke.h index 24702b6d5b52..ba8202576593 100644 --- a/libcxx/include/__type_traits/invoke.h +++ b/libcxx/include/__type_traits/invoke.h @@ -62,6 +62,9 @@ // // template <class Func, class... Args> // using __invoke_result_t = invoke_result_t<Func, Args...>; +// +// template <class Ret, class Func, class... Args> +// struct __is_invocable_r : is_invocable_r<Ret, Func, Args...> {}; _LIBCPP_BEGIN_NAMESPACE_STD @@ -329,6 +332,9 @@ using __invoke_result_t _LIBCPP_NODEBUG = typename __invoke_result<_Func, _Args. #endif // __has_builtin(__builtin_invoke_r) +template <class _Ret, class _Func, class... _Args> +struct __is_invocable_r : integral_constant<bool, __is_invocable_r_v<_Ret, _Func, _Args...> > {}; + template <class _Ret, bool = is_void<_Ret>::value> struct __invoke_void_return_wrapper { template <class... _Args> diff --git a/libcxx/include/__type_traits/is_unqualified.h b/libcxx/include/__type_traits/is_unqualified.h new file mode 100644 index 000000000000..7970b3611601 --- /dev/null +++ b/libcxx/include/__type_traits/is_unqualified.h @@ -0,0 +1,25 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___TYPE_TRAITS_IS_UNQUALIFIED_H +#define _LIBCPP___TYPE_TRAITS_IS_UNQUALIFIED_H + +#include <__config> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +template <class _Tp> +inline const bool __is_unqualified_v = __is_same(_Tp, __remove_cvref(_Tp)); + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___TYPE_TRAITS_IS_UNQUALIFIED_H diff --git a/libcxx/include/__utility/default_three_way_comparator.h b/libcxx/include/__utility/default_three_way_comparator.h new file mode 100644 index 000000000000..ce423c6ce98e --- /dev/null +++ b/libcxx/include/__utility/default_three_way_comparator.h @@ -0,0 +1,50 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___UTILITY_DEFAULT_THREE_WAY_COMPARATOR_H +#define _LIBCPP___UTILITY_DEFAULT_THREE_WAY_COMPARATOR_H + +#include <__config> +#include <__type_traits/enable_if.h> +#include <__type_traits/is_arithmetic.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +// This struct can be specialized to provide a three way comparator between _LHS and _RHS. +// The return value should be +// - less than zero if (lhs_val < rhs_val) +// - greater than zero if (rhs_val < lhs_val) +// - zero otherwise +template <class _LHS, class _RHS, class = void> +struct __default_three_way_comparator; + +template <class _Tp> +struct __default_three_way_comparator<_Tp, _Tp, __enable_if_t<is_arithmetic<_Tp>::value> > { + _LIBCPP_HIDE_FROM_ABI static int operator()(_Tp __lhs, _Tp __rhs) { + if (__lhs < __rhs) + return -1; + if (__lhs > __rhs) + return 1; + return 0; + } +}; + +template <class _LHS, class _RHS, bool = true> +inline const bool __has_default_three_way_comparator_v = false; + +template <class _LHS, class _RHS> +inline const bool + __has_default_three_way_comparator_v< _LHS, _RHS, sizeof(__default_three_way_comparator<_LHS, _RHS>) >= 0> = true; + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___UTILITY_DEFAULT_THREE_WAY_COMPARATOR_H diff --git a/libcxx/include/__utility/in_place.h b/libcxx/include/__utility/in_place.h index ade4b6685a11..c5bfa947058f 100644 --- a/libcxx/include/__utility/in_place.h +++ b/libcxx/include/__utility/in_place.h @@ -22,7 +22,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD #if _LIBCPP_STD_VER >= 17 -struct _LIBCPP_EXPORTED_FROM_ABI in_place_t { +struct in_place_t { explicit in_place_t() = default; }; inline constexpr in_place_t in_place{}; diff --git a/libcxx/include/__utility/lazy_synth_three_way_comparator.h b/libcxx/include/__utility/lazy_synth_three_way_comparator.h new file mode 100644 index 000000000000..ca98845f0419 --- /dev/null +++ b/libcxx/include/__utility/lazy_synth_three_way_comparator.h @@ -0,0 +1,90 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___UTILITY_LAZY_SYNTH_THREE_WAY_COMPARATOR_H +#define _LIBCPP___UTILITY_LAZY_SYNTH_THREE_WAY_COMPARATOR_H + +#include <__config> +#include <__type_traits/desugars_to.h> +#include <__type_traits/enable_if.h> +#include <__utility/default_three_way_comparator.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +// This file implements a __lazy_synth_three_way_comparator, which tries to build an efficient three way comparison from +// a binary comparator. That is done in multiple steps: +// 1) Check whether the comparator desugars to a less-than operator +// If that is the case, check whether there exists a specialization of `__default_three_way_comparator`, which +// can be specialized to implement a three way comparator for the specific types. +// 2) Fall back to doing a lazy less than/greater than comparison + +_LIBCPP_BEGIN_NAMESPACE_STD + +template <class _Comparator, class _LHS, class _RHS> +struct __lazy_compare_result { + const _Comparator& __comp_; + const _LHS& __lhs_; + const _RHS& __rhs_; + + _LIBCPP_HIDE_FROM_ABI + __lazy_compare_result(_LIBCPP_CTOR_LIFETIMEBOUND const _Comparator& __comp, + _LIBCPP_CTOR_LIFETIMEBOUND const _LHS& __lhs, + _LIBCPP_CTOR_LIFETIMEBOUND const _RHS& __rhs) + : __comp_(__comp), __lhs_(__lhs), __rhs_(__rhs) {} + + _LIBCPP_HIDE_FROM_ABI bool __less() const { return __comp_(__lhs_, __rhs_); } + _LIBCPP_HIDE_FROM_ABI bool __greater() const { return __comp_(__rhs_, __lhs_); } +}; + +// This class provides three way comparison between _LHS and _RHS as efficiently as possible. This can be specialized if +// a comparator only compares part of the object, potentially allowing an efficient three way comparison between the +// subobjects. The specialization should use the __lazy_synth_three_way_comparator for the subobjects to achieve this. +template <class _Comparator, class _LHS, class _RHS, class = void> +struct __lazy_synth_three_way_comparator { + const _Comparator& __comp_; + + _LIBCPP_HIDE_FROM_ABI __lazy_synth_three_way_comparator(_LIBCPP_CTOR_LIFETIMEBOUND const _Comparator& __comp) + : __comp_(__comp) {} + + _LIBCPP_HIDE_FROM_ABI __lazy_compare_result<_Comparator, _LHS, _RHS> + operator()(_LIBCPP_LIFETIMEBOUND const _LHS& __lhs, _LIBCPP_LIFETIMEBOUND const _RHS& __rhs) const { + return __lazy_compare_result<_Comparator, _LHS, _RHS>(__comp_, __lhs, __rhs); + } +}; + +struct __eager_compare_result { + int __res_; + + _LIBCPP_HIDE_FROM_ABI explicit __eager_compare_result(int __res) : __res_(__res) {} + + _LIBCPP_HIDE_FROM_ABI bool __less() const { return __res_ < 0; } + _LIBCPP_HIDE_FROM_ABI bool __greater() const { return __res_ > 0; } +}; + +template <class _Comparator, class _LHS, class _RHS> +struct __lazy_synth_three_way_comparator<_Comparator, + _LHS, + _RHS, + __enable_if_t<__desugars_to_v<__less_tag, _Comparator, _LHS, _RHS> && + __has_default_three_way_comparator_v<_LHS, _RHS> > > { + // This lifetimebound annotation is technically incorrect, but other specializations actually capture the lifetime of + // the comparator. + _LIBCPP_HIDE_FROM_ABI __lazy_synth_three_way_comparator(_LIBCPP_CTOR_LIFETIMEBOUND const _Comparator&) {} + + // Same comment as above. + _LIBCPP_HIDE_FROM_ABI static __eager_compare_result + operator()(_LIBCPP_LIFETIMEBOUND const _LHS& __lhs, _LIBCPP_LIFETIMEBOUND const _RHS& __rhs) { + return __eager_compare_result(__default_three_way_comparator<_LHS, _RHS>()(__lhs, __rhs)); + } +}; + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___UTILITY_LAZY_SYNTH_THREE_WAY_COMPARATOR_H diff --git a/libcxx/include/__utility/try_key_extraction.h b/libcxx/include/__utility/try_key_extraction.h new file mode 100644 index 000000000000..755c08214019 --- /dev/null +++ b/libcxx/include/__utility/try_key_extraction.h @@ -0,0 +1,114 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___UTILITY_TRY_EXTRACT_KEY_H +#define _LIBCPP___UTILITY_TRY_EXTRACT_KEY_H + +#include <__config> +#include <__fwd/pair.h> +#include <__fwd/tuple.h> +#include <__type_traits/enable_if.h> +#include <__type_traits/is_same.h> +#include <__type_traits/remove_const.h> +#include <__type_traits/remove_const_ref.h> +#include <__utility/declval.h> +#include <__utility/forward.h> +#include <__utility/piecewise_construct.h> +#include <__utility/priority_tag.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +template <class _KeyT, class _Ret, class _WithKey, class _WithoutKey, class... _Args> +_LIBCPP_HIDE_FROM_ABI _Ret +__try_key_extraction_impl(__priority_tag<0>, _WithKey, _WithoutKey __without_key, _Args&&... __args) { + return __without_key(std::forward<_Args>(__args)...); +} + +template <class _KeyT, + class _Ret, + class _WithKey, + class _WithoutKey, + class _Arg, + __enable_if_t<is_same<_KeyT, __remove_const_ref_t<_Arg> >::value, int> = 0> +_LIBCPP_HIDE_FROM_ABI _Ret +__try_key_extraction_impl(__priority_tag<1>, _WithKey __with_key, _WithoutKey, _Arg&& __arg) { + return __with_key(__arg, std::forward<_Arg>(__arg)); +} + +template <class _KeyT, + class _Ret, + class _WithKey, + class _WithoutKey, + class _Arg, + __enable_if_t<__is_pair_v<__remove_const_ref_t<_Arg> > && + is_same<__remove_const_t<typename __remove_const_ref_t<_Arg>::first_type>, _KeyT>::value, + int> = 0> +_LIBCPP_HIDE_FROM_ABI _Ret +__try_key_extraction_impl(__priority_tag<1>, _WithKey __with_key, _WithoutKey, _Arg&& __arg) { + return __with_key(__arg.first, std::forward<_Arg>(__arg)); +} + +template <class _KeyT, + class _Ret, + class _WithKey, + class _WithoutKey, + class _Arg1, + class _Arg2, + __enable_if_t<is_same<_KeyT, __remove_const_ref_t<_Arg1> >::value, int> = 0> +_LIBCPP_HIDE_FROM_ABI _Ret +__try_key_extraction_impl(__priority_tag<1>, _WithKey __with_key, _WithoutKey, _Arg1&& __arg1, _Arg2&& __arg2) { + return __with_key(__arg1, std::forward<_Arg1>(__arg1), std::forward<_Arg2>(__arg2)); +} + +#ifndef _LIBCPP_CXX03_LANG +template <class _KeyT, + class _Ret, + class _WithKey, + class _WithoutKey, + class _PiecewiseConstruct, + class _Tuple1, + class _Tuple2, + __enable_if_t<is_same<__remove_const_ref_t<_PiecewiseConstruct>, piecewise_construct_t>::value && + __is_tuple_v<_Tuple1> && tuple_size<_Tuple1>::value == 1 && + is_same<__remove_const_ref_t<typename tuple_element<0, _Tuple1>::type>, _KeyT>::value, + int> = 0> +_LIBCPP_HIDE_FROM_ABI _Ret __try_key_extraction_impl( + __priority_tag<1>, + _WithKey __with_key, + _WithoutKey, + _PiecewiseConstruct&& __pc, + _Tuple1&& __tuple1, + _Tuple2&& __tuple2) { + return __with_key( + std::get<0>(__tuple1), + std::forward<_PiecewiseConstruct>(__pc), + std::forward<_Tuple1>(__tuple1), + std::forward<_Tuple2>(__tuple2)); +} +#endif // _LIBCPP_CXX03_LANG + +// This function tries extracting the given _KeyT from _Args... +// If it succeeds to extract the key, it calls the `__with_key` function with the extracted key and all of the +// arguments. Otherwise it calls the `__without_key` function with all of the arguments. +// +// Both `__with_key` and `__without_key` must take all arguments by reference. +template <class _KeyT, class _WithKey, class _WithoutKey, class... _Args> +_LIBCPP_HIDE_FROM_ABI decltype(std::declval<_WithoutKey>()(std::declval<_Args>()...)) +__try_key_extraction(_WithKey __with_key, _WithoutKey __without_key, _Args&&... __args) { + using _Ret = decltype(__without_key(std::forward<_Args>(__args)...)); + return std::__try_key_extraction_impl<_KeyT, _Ret>( + __priority_tag<1>(), __with_key, __without_key, std::forward<_Args>(__args)...); +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___UTILITY_TRY_EXTRACT_KEY_H diff --git a/libcxx/include/__vector/vector_bool.h b/libcxx/include/__vector/vector_bool.h index bd7b28e517ad..7b8290676925 100644 --- a/libcxx/include/__vector/vector_bool.h +++ b/libcxx/include/__vector/vector_bool.h @@ -19,7 +19,7 @@ #include <__bit_reference> #include <__config> #include <__functional/unary_function.h> -#include <__fwd/bit_reference.h> // TODO: This is a workaround for https://github.com/llvm/llvm-project/issues/131814 +#include <__fwd/bit_reference.h> // TODO: This is a workaround for https://llvm.org/PR131814 #include <__fwd/functional.h> #include <__fwd/vector.h> #include <__iterator/distance.h> diff --git a/libcxx/include/ext/hash_map b/libcxx/include/ext/hash_map index 46815eaffa8b..ae4fb7ec01c9 100644 --- a/libcxx/include/ext/hash_map +++ b/libcxx/include/ext/hash_map @@ -467,8 +467,6 @@ private: __table __table_; - typedef typename __table::__node_pointer __node_pointer; - typedef typename __table::__node_const_pointer __node_const_pointer; typedef typename __table::__node_traits __node_traits; typedef typename __table::__node_allocator __node_allocator; typedef typename __table::__node __node; @@ -693,7 +691,6 @@ private: __table __table_; - typedef typename __table::__node_traits __node_traits; typedef typename __table::__node_allocator __node_allocator; typedef typename __table::__node __node; typedef __hash_map_node_destructor<__node_allocator> _Dp; diff --git a/libcxx/include/fstream b/libcxx/include/fstream index 6d3f20fff688..04cebdedc31d 100644 --- a/libcxx/include/fstream +++ b/libcxx/include/fstream @@ -299,6 +299,16 @@ protected: int sync() override; void imbue(const locale& __loc) override; + _LIBCPP_HIDE_FROM_ABI_VIRTUAL streamsize xsputn(const char_type* __str, streamsize __len) override { + if (__always_noconv_ && __len >= (this->epptr() - this->pbase())) { + if (traits_type::eq_int_type(overflow(), traits_type::eof())) + return 0; + + return std::fwrite(__str, sizeof(char_type), __len, __file_); + } + return basic_streambuf<_CharT, _Traits>::xsputn(__str, __len); + } + private: char* __extbuf_; const char* __extbufnext_; diff --git a/libcxx/include/map b/libcxx/include/map index 9bd2282e77a3..f428c781e503 100644 --- a/libcxx/include/map +++ b/libcxx/include/map @@ -603,6 +603,7 @@ erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred); // C++20 # include <__type_traits/remove_const.h> # include <__type_traits/type_identity.h> # include <__utility/forward.h> +# include <__utility/lazy_synth_three_way_comparator.h> # include <__utility/pair.h> # include <__utility/piecewise_construct.h> # include <__utility/swap.h> @@ -702,6 +703,50 @@ public: # endif }; +# if _LIBCPP_STD_VER >= 14 +template <class _MapValueT, class _Key, class _Compare> +struct __lazy_synth_three_way_comparator<__map_value_compare<_Key, _MapValueT, _Compare>, _MapValueT, _MapValueT> { + __lazy_synth_three_way_comparator<_Compare, _Key, _Key> __comp_; + + __lazy_synth_three_way_comparator( + _LIBCPP_CTOR_LIFETIMEBOUND const __map_value_compare<_Key, _MapValueT, _Compare>& __comp) + : __comp_(__comp.key_comp()) {} + + _LIBCPP_HIDE_FROM_ABI auto + operator()(_LIBCPP_LIFETIMEBOUND const _MapValueT& __lhs, _LIBCPP_LIFETIMEBOUND const _MapValueT& __rhs) const { + return __comp_(__lhs.first, __rhs.first); + } +}; + +template <class _MapValueT, class _Key, class _TransparentKey, class _Compare> +struct __lazy_synth_three_way_comparator<__map_value_compare<_Key, _MapValueT, _Compare>, _TransparentKey, _MapValueT> { + __lazy_synth_three_way_comparator<_Compare, _TransparentKey, _Key> __comp_; + + __lazy_synth_three_way_comparator( + _LIBCPP_CTOR_LIFETIMEBOUND const __map_value_compare<_Key, _MapValueT, _Compare>& __comp) + : __comp_(__comp.key_comp()) {} + + _LIBCPP_HIDE_FROM_ABI auto + operator()(_LIBCPP_LIFETIMEBOUND const _TransparentKey& __lhs, _LIBCPP_LIFETIMEBOUND const _MapValueT& __rhs) const { + return __comp_(__lhs, __rhs.first); + } +}; + +template <class _MapValueT, class _Key, class _TransparentKey, class _Compare> +struct __lazy_synth_three_way_comparator<__map_value_compare<_Key, _MapValueT, _Compare>, _MapValueT, _TransparentKey> { + __lazy_synth_three_way_comparator<_Compare, _Key, _TransparentKey> __comp_; + + __lazy_synth_three_way_comparator( + _LIBCPP_CTOR_LIFETIMEBOUND const __map_value_compare<_Key, _MapValueT, _Compare>& __comp) + : __comp_(__comp.key_comp()) {} + + _LIBCPP_HIDE_FROM_ABI auto + operator()(_LIBCPP_LIFETIMEBOUND const _MapValueT& __lhs, _LIBCPP_LIFETIMEBOUND const _TransparentKey& __rhs) const { + return __comp_(__lhs.first, __rhs); + } +}; +# endif // _LIBCPP_STD_VER >= 14 + template <class _Key, class _CP, class _Compare, bool __b> inline _LIBCPP_HIDE_FROM_ABI void swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x, __map_value_compare<_Key, _CP, _Compare, __b>& __y) @@ -1055,7 +1100,7 @@ public: template <class... _Args> _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) { - return __tree_.__emplace_hint_unique(__p.__i_, std::forward<_Args>(__args)...); + return __tree_.__emplace_hint_unique(__p.__i_, std::forward<_Args>(__args)...).first; } template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0> @@ -1065,7 +1110,7 @@ public: template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0> _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __pos, _Pp&& __p) { - return __tree_.__emplace_hint_unique(__pos.__i_, std::forward<_Pp>(__p)); + return __tree_.__emplace_hint_unique(__pos.__i_, std::forward<_Pp>(__p)).first; } # endif // _LIBCPP_CXX03_LANG @@ -1073,7 +1118,7 @@ public: _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__emplace_unique(__v); } _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) { - return __tree_.__emplace_hint_unique(__p.__i_, __v); + return __tree_.__emplace_hint_unique(__p.__i_, __v).first; } # ifndef _LIBCPP_CXX03_LANG @@ -1082,25 +1127,21 @@ public: } _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) { - return __tree_.__emplace_hint_unique(__p.__i_, std::move(__v)); + return __tree_.__emplace_hint_unique(__p.__i_, std::move(__v)).first; } _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); } # endif template <class _InputIterator> - _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) { - for (const_iterator __e = cend(); __f != __l; ++__f) - insert(__e.__i_, *__f); + _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last) { + __tree_.__insert_range_unique(__first, __last); } # if _LIBCPP_STD_VER >= 23 template <_ContainerCompatibleRange<value_type> _Range> _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) { - const_iterator __end = cend(); - for (auto&& __element : __range) { - insert(__end.__i_, std::forward<decltype(__element)>(__element)); - } + __tree_.__insert_range_unique(ranges::begin(__range), ranges::end(__range)); } # endif @@ -1108,17 +1149,13 @@ public: template <class... _Args> _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) { - return __tree_.__emplace_unique_key_args( - __k, - std::piecewise_construct, - std::forward_as_tuple(__k), - std::forward_as_tuple(std::forward<_Args>(__args)...)); + return __tree_.__emplace_unique( + std::piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple(std::forward<_Args>(__args)...)); } template <class... _Args> _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) { - return __tree_.__emplace_unique_key_args( - __k, + return __tree_.__emplace_unique( std::piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple(std::forward<_Args>(__args)...)); @@ -1127,9 +1164,8 @@ public: template <class... _Args> _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) { return __tree_ - .__emplace_hint_unique_key_args( + .__emplace_hint_unique( __h.__i_, - __k, std::piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple(std::forward<_Args>(__args)...)) @@ -1139,9 +1175,8 @@ public: template <class... _Args> _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) { return __tree_ - .__emplace_hint_unique_key_args( + .__emplace_hint_unique( __h.__i_, - __k, std::piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple(std::forward<_Args>(__args)...)) @@ -1150,27 +1185,25 @@ public: template <class _Vp> _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) { - iterator __p = lower_bound(__k); - if (__p != end() && !key_comp()(__k, __p->first)) { - __p->second = std::forward<_Vp>(__v); - return std::make_pair(__p, false); - } - return std::make_pair(emplace_hint(__p, __k, std::forward<_Vp>(__v)), true); + auto __result = __tree_.__emplace_unique(__k, std::forward<_Vp>(__v)); + auto& [__iter, __inserted] = __result; + if (!__inserted) + __iter->second = std::forward<_Vp>(__v); + return __result; } template <class _Vp> _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) { - iterator __p = lower_bound(__k); - if (__p != end() && !key_comp()(__k, __p->first)) { - __p->second = std::forward<_Vp>(__v); - return std::make_pair(__p, false); - } - return std::make_pair(emplace_hint(__p, std::move(__k), std::forward<_Vp>(__v)), true); + auto __result = __tree_.__emplace_unique(std::move(__k), std::forward<_Vp>(__v)); + auto& [__iter, __inserted] = __result; + if (!__inserted) + __iter->second = std::forward<_Vp>(__v); + return __result; } template <class _Vp> _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v) { - auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, __k, std::forward<_Vp>(__v)); + auto [__r, __inserted] = __tree_.__emplace_hint_unique(__h.__i_, __k, std::forward<_Vp>(__v)); if (!__inserted) __r->second = std::forward<_Vp>(__v); @@ -1180,8 +1213,7 @@ public: template <class _Vp> _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v) { - auto [__r, __inserted] = - __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, std::move(__k), std::forward<_Vp>(__v)); + auto [__r, __inserted] = __tree_.__emplace_hint_unique(__h.__i_, std::move(__k), std::forward<_Vp>(__v)); if (!__inserted) __r->second = std::forward<_Vp>(__v); @@ -1398,20 +1430,15 @@ map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a) template <class _Key, class _Tp, class _Compare, class _Allocator> _Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) { - return __tree_ - .__emplace_unique_key_args(__k, std::piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple()) + return __tree_.__emplace_unique(std::piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple()) .first->second; } template <class _Key, class _Tp, class _Compare, class _Allocator> _Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k) { - // TODO investigate this clang-tidy warning. - // NOLINTBEGIN(bugprone-use-after-move) return __tree_ - .__emplace_unique_key_args( - __k, std::piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple()) + .__emplace_unique(std::piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple()) .first->second; - // NOLINTEND(bugprone-use-after-move) } # else // _LIBCPP_CXX03_LANG @@ -1430,9 +1457,8 @@ map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& template <class _Key, class _Tp, class _Compare, class _Allocator> _Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) { - __parent_pointer __parent; - __node_base_pointer& __child = __tree_.__find_equal(__parent, __k); - __node_pointer __r = static_cast<__node_pointer>(__child); + auto [__parent, __child] = __tree_.__find_equal(__k); + __node_pointer __r = static_cast<__node_pointer>(__child); if (__child == nullptr) { __node_holder __h = __construct_node_with_key(__k); __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); @@ -1445,8 +1471,7 @@ _Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) { template <class _Key, class _Tp, class _Compare, class _Allocator> _Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) { - __parent_pointer __parent; - __node_base_pointer& __child = __tree_.__find_equal(__parent, __k); + auto [_, __child] = __tree_.__find_equal(__k); if (__child == nullptr) std::__throw_out_of_range("map::at: key not found"); return static_cast<__node_pointer>(__child)->__get_value().second; @@ -1454,8 +1479,7 @@ _Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) { template <class _Key, class _Tp, class _Compare, class _Allocator> const _Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const { - __parent_pointer __parent; - __node_base_pointer __child = __tree_.__find_equal(__parent, __k); + auto [_, __child] = __tree_.__find_equal(__k); if (__child == nullptr) std::__throw_out_of_range("map::at: key not found"); return static_cast<__node_pointer>(__child)->__get_value().second; diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in index c431c0cb407f..63cf8e847751 100644 --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -70,7 +70,6 @@ module std_core [system] { module aligned_storage { header "__type_traits/aligned_storage.h" } module aligned_union { header "__type_traits/aligned_union.h" } module alignment_of { header "__type_traits/alignment_of.h" } - module can_extract_key { header "__type_traits/can_extract_key.h" } module common_reference { header "__type_traits/common_reference.h" } module common_type { header "__type_traits/common_type.h" @@ -336,6 +335,7 @@ module std_core [system] { header "__type_traits/is_union.h" export std_core.type_traits.integral_constant } + module is_unqualified { header "__type_traits/is_unqualified.h" } module is_unsigned { header "__type_traits/is_unsigned.h" export std_core.type_traits.integral_constant @@ -842,7 +842,7 @@ module std [system] { module stable_partition { header "__algorithm/stable_partition.h" } module stable_sort { header "__algorithm/stable_sort.h" - export std.memory.unique_temporary_buffer // TODO: Workaround for https://github.com/llvm/llvm-project/issues/120108 + export std.memory.unique_temporary_buffer // TODO: Workaround for https://llvm.org/PR120108 } module swap_ranges { header "__algorithm/swap_ranges.h" } module three_way_comp_ref_type { header "__algorithm/three_way_comp_ref_type.h" } @@ -1260,7 +1260,7 @@ module std [system] { module directory_entry { header "__filesystem/directory_entry.h" } module directory_iterator { header "__filesystem/directory_iterator.h" - // This is a workaround for https://github.com/llvm/llvm-project/issues/120108. + // This is a workaround for https://llvm.org/PR120108. export * } module directory_options { header "__filesystem/directory_options.h" } @@ -1637,7 +1637,7 @@ module std [system] { module allocation_guard { header "__memory/allocation_guard.h" } module allocator { header "__memory/allocator.h" - export * // TODO: Workaround for https://github.com/llvm/llvm-project/issues/120108 + export * // TODO: Workaround for https://llvm.org/PR120108 } module allocator_arg_t { header "__memory/allocator_arg_t.h" } module allocator_destructor { header "__memory/allocator_destructor.h" } @@ -1682,7 +1682,7 @@ module std [system] { header "__memory/unique_temporary_buffer.h" export std.memory.unique_ptr export std_core.type_traits.is_constant_evaluated - export * // TODO: Workaround for https://github.com/llvm/llvm-project/issues/120108 + export * // TODO: Workaround for https://llvm.org/PR120108 } module uses_allocator { header "__memory/uses_allocator.h" } module uses_allocator_construction { header "__memory/uses_allocator_construction.h" } @@ -1721,7 +1721,7 @@ module std [system] { module allocate { header "__new/allocate.h" export std.utility.element_count // used as part of the API - export * // TODO: Workaround for https://github.com/llvm/llvm-project/issues/120108 + export * // TODO: Workaround for https://llvm.org/PR120108 } module destroying_delete_t { header "__new/destroying_delete_t.h" } module exceptions { header "__new/exceptions.h" } @@ -2109,7 +2109,6 @@ module std [system] { module tuple { module find_index { header "__tuple/find_index.h" } module ignore { header "__tuple/ignore.h" } - module make_tuple_types { header "__tuple/make_tuple_types.h" } module sfinae_helpers { header "__tuple/sfinae_helpers.h" } module tuple_element { header "__tuple/tuple_element.h" } module tuple_like_ext { header "__tuple/tuple_like_ext.h" } @@ -2145,40 +2144,43 @@ module std [system] { } module utility { - module as_const { header "__utility/as_const.h" } - module as_lvalue { header "__utility/as_lvalue.h" } - module auto_cast { + module as_const { header "__utility/as_const.h" } + module as_lvalue { header "__utility/as_lvalue.h" } + module auto_cast { header "__utility/auto_cast.h" export std_core.type_traits.decay // the macro expansion uses that trait } - module cmp { header "__utility/cmp.h" } - module convert_to_integral { header "__utility/convert_to_integral.h" } - module element_count { header "__utility/element_count.h" } - module exception_guard { header "__utility/exception_guard.h" } - module exchange { header "__utility/exchange.h" } - module forward_like { header "__utility/forward_like.h" } - module in_place { + module cmp { header "__utility/cmp.h" } + module convert_to_integral { header "__utility/convert_to_integral.h" } + module default_three_way_comparator { header "__utility/default_three_way_comparator.h" } + module element_count { header "__utility/element_count.h" } + module exception_guard { header "__utility/exception_guard.h" } + module exchange { header "__utility/exchange.h" } + module forward_like { header "__utility/forward_like.h" } + module in_place { header "__utility/in_place.h" export std_core.type_traits.integral_constant } - module integer_sequence { header "__utility/integer_sequence.h" } - module is_pointer_in_range { header "__utility/is_pointer_in_range.h" } - module is_valid_range { header "__utility/is_valid_range.h" } - module move { header "__utility/move.h" } - module no_destroy { header "__utility/no_destroy.h" } - module pair { + module integer_sequence { header "__utility/integer_sequence.h" } + module is_pointer_in_range { header "__utility/is_pointer_in_range.h" } + module is_valid_range { header "__utility/is_valid_range.h" } + module lazy_synth_three_way_comparator { header "__utility/lazy_synth_three_way_comparator.h" } + module move { header "__utility/move.h" } + module no_destroy { header "__utility/no_destroy.h" } + module pair { header "__utility/pair.h" export std.utility.piecewise_construct } - module piecewise_construct { header "__utility/piecewise_construct.h" } - module priority_tag { header "__utility/priority_tag.h" } - module private_constructor_tag { header "__utility/private_constructor_tag.h" } - module rel_ops { header "__utility/rel_ops.h" } - module scope_guard { header "__utility/scope_guard.h" } - module small_buffer { header "__utility/small_buffer.h" } - module swap { header "__utility/swap.h" } - module to_underlying { header "__utility/to_underlying.h" } - module unreachable { header "__utility/unreachable.h" } + module piecewise_construct { header "__utility/piecewise_construct.h" } + module priority_tag { header "__utility/priority_tag.h" } + module private_constructor_tag { header "__utility/private_constructor_tag.h" } + module rel_ops { header "__utility/rel_ops.h" } + module scope_guard { header "__utility/scope_guard.h" } + module small_buffer { header "__utility/small_buffer.h" } + module swap { header "__utility/swap.h" } + module to_underlying { header "__utility/to_underlying.h" } + module try_key_extraction { header "__utility/try_key_extraction.h" } + module unreachable { header "__utility/unreachable.h" } header "utility" export * diff --git a/libcxx/include/mutex b/libcxx/include/mutex index 78d8c8a9bcc6..58474e0ca2b7 100644 --- a/libcxx/include/mutex +++ b/libcxx/include/mutex @@ -320,7 +320,7 @@ public: }; template <class _L0, class _L1> -_LIBCPP_HIDE_FROM_ABI int try_lock(_L0& __l0, _L1& __l1) { +_LIBCPP_NO_THREAD_SAFETY_ANALYSIS _LIBCPP_HIDE_FROM_ABI int try_lock(_L0& __l0, _L1& __l1) { unique_lock<_L0> __u0(__l0, try_to_lock_t()); if (__u0.owns_lock()) { if (__l1.try_lock()) { @@ -335,7 +335,7 @@ _LIBCPP_HIDE_FROM_ABI int try_lock(_L0& __l0, _L1& __l1) { # ifndef _LIBCPP_CXX03_LANG template <class _L0, class _L1, class _L2, class... _L3> -_LIBCPP_HIDE_FROM_ABI int try_lock(_L0& __l0, _L1& __l1, _L2& __l2, _L3&... __l3) { +_LIBCPP_NO_THREAD_SAFETY_ANALYSIS _LIBCPP_HIDE_FROM_ABI int try_lock(_L0& __l0, _L1& __l1, _L2& __l2, _L3&... __l3) { int __r = 0; unique_lock<_L0> __u0(__l0, try_to_lock); if (__u0.owns_lock()) { @@ -350,8 +350,11 @@ _LIBCPP_HIDE_FROM_ABI int try_lock(_L0& __l0, _L1& __l1, _L2& __l2, _L3&... __l3 # endif // _LIBCPP_CXX03_LANG +// We're using unique_lock to implement the functions, which thread annotations don't support. So we have to disable +// the analysis inside the function. template <class _L0, class _L1> -_LIBCPP_HIDE_FROM_ABI void lock(_L0& __l0, _L1& __l1) { +_LIBCPP_NO_THREAD_SAFETY_ANALYSIS _LIBCPP_HIDE_FROM_ABI void lock(_L0& __l0, _L1& __l1) + _LIBCPP_ACQUIRE_CAPABILITY(__l0, __l1) { while (true) { { unique_lock<_L0> __u0(__l0); @@ -375,7 +378,7 @@ _LIBCPP_HIDE_FROM_ABI void lock(_L0& __l0, _L1& __l1) { # ifndef _LIBCPP_CXX03_LANG template <class _L0, class _L1, class _L2, class... _L3> -void __lock_first(int __i, _L0& __l0, _L1& __l1, _L2& __l2, _L3&... __l3) { +_LIBCPP_NO_THREAD_SAFETY_ANALYSIS void __lock_first(int __i, _L0& __l0, _L1& __l1, _L2& __l2, _L3&... __l3) { while (true) { switch (__i) { case 0: { @@ -410,8 +413,14 @@ void __lock_first(int __i, _L0& __l0, _L1& __l1, _L2& __l2, _L3&... __l3) { } } +// We're using unique_lock to implement the functions, which thread annotations don't support. So we have to disable +// the analysis inside the function. template <class _L0, class _L1, class _L2, class... _L3> -inline _LIBCPP_HIDE_FROM_ABI void lock(_L0& __l0, _L1& __l1, _L2& __l2, _L3&... __l3) { +_LIBCPP_NO_THREAD_SAFETY_ANALYSIS inline _LIBCPP_HIDE_FROM_ABI void lock(_L0& __l0, _L1& __l1, _L2& __l2, _L3&... __l3) +# if defined(_LIBCPP_CLANG_VER) && _LIBCPP_CLANG_VER >= 2101 + _LIBCPP_ACQUIRE_CAPABILITY(__l0, __l1, __l2, __l3...) +# endif +{ std::__lock_first(0, __l0, __l1, __l2, __l3...); } diff --git a/libcxx/include/set b/libcxx/include/set index 5190fc1f406b..6470894517fd 100644 --- a/libcxx/include/set +++ b/libcxx/include/set @@ -732,28 +732,24 @@ public: } template <class... _Args> _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) { - return __tree_.__emplace_hint_unique(__p, std::forward<_Args>(__args)...); + return __tree_.__emplace_hint_unique(__p, std::forward<_Args>(__args)...).first; } # endif // _LIBCPP_CXX03_LANG _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__emplace_unique(__v); } _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) { - return __tree_.__emplace_hint_unique(__p, __v); + return __tree_.__emplace_hint_unique(__p, __v).first; } template <class _InputIterator> - _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) { - for (const_iterator __e = cend(); __f != __l; ++__f) - __tree_.__emplace_hint_unique(__e, *__f); + _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last) { + __tree_.__insert_range_unique(__first, __last); } # if _LIBCPP_STD_VER >= 23 template <_ContainerCompatibleRange<value_type> _Range> _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) { - const_iterator __end = cend(); - for (auto&& __element : __range) { - __tree_.__emplace_hint_unique(__end, std::forward<decltype(__element)>(__element)); - } + __tree_.__insert_range_unique(ranges::begin(__range), ranges::end(__range)); } # endif @@ -763,7 +759,7 @@ public: } _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) { - return __tree_.__emplace_hint_unique(__p, std::move(__v)); + return __tree_.__emplace_hint_unique(__p, std::move(__v)).first; } _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); } diff --git a/libcxx/include/string b/libcxx/include/string index 1d197654b9fe..0abdfebcb863 100644 --- a/libcxx/include/string +++ b/libcxx/include/string @@ -639,13 +639,12 @@ basic_string<char32_t> operator""s( const char32_t *str, size_t len ); # include <__type_traits/remove_cvref.h> # include <__type_traits/void_t.h> # include <__utility/auto_cast.h> -# include <__utility/declval.h> +# include <__utility/default_three_way_comparator.h> # include <__utility/forward.h> # include <__utility/is_pointer_in_range.h> # include <__utility/move.h> # include <__utility/scope_guard.h> # include <__utility/swap.h> -# include <__utility/unreachable.h> # include <climits> # include <cstdio> // EOF # include <cstring> @@ -966,7 +965,7 @@ private: std::__wrap_iter<const_pointer>(__get_pointer() + size())); # else return const_iterator(__p); -# endif // _LIBCPP_ABI_BOUNDED_ITERATORS_IN_STRING +# endif // _LIBCPP_ABI_BOUNDED_ITERATORS_IN_STRING } public: @@ -2258,7 +2257,7 @@ private: (void)__new_mid; # if _LIBCPP_INSTRUMENTED_WITH_ASAN # if defined(__APPLE__) - // TODO: remove after addressing issue #96099 (https://github.com/llvm/llvm-project/issues/96099) + // TODO: remove after addressing issue #96099 (https://llvm.org/PR96099) if (!__is_long()) return; # endif @@ -2522,6 +2521,19 @@ _LIBCPP_STRING_V1_EXTERN_TEMPLATE_LIST(_LIBCPP_DECLARE, wchar_t) # endif # undef _LIBCPP_DECLARE +template <class _CharT, class _Traits, class _Alloc> +struct __default_three_way_comparator<basic_string<_CharT, _Traits, _Alloc>, basic_string<_CharT, _Traits, _Alloc> > { + using __string_t _LIBCPP_NODEBUG = basic_string<_CharT, _Traits, _Alloc>; + + _LIBCPP_HIDE_FROM_ABI static int operator()(const __string_t& __lhs, const __string_t& __rhs) { + auto __min_len = std::min(__lhs.size(), __rhs.size()); + auto __ret = _Traits::compare(__lhs.data(), __rhs.data(), __min_len); + if (__ret == 0) + return __lhs.size() == __rhs.size() ? 0 : __lhs.size() < __rhs.size() ? -1 : 1; + return __ret; + } +}; + # if _LIBCPP_STD_VER >= 17 template <class _InputIterator, class _CharT = __iter_value_type<_InputIterator>, diff --git a/libcxx/include/string_view b/libcxx/include/string_view index 9a20bb6f4a0b..983e5852015e 100644 --- a/libcxx/include/string_view +++ b/libcxx/include/string_view @@ -460,7 +460,7 @@ public: _LIBCPP_CONSTEXPR _LIBCPP_HIDE_FROM_ABI basic_string_view substr(size_type __pos = 0, size_type __n = npos) const { // Use the `__assume_valid` form of the constructor to avoid an unnecessary check. Any substring of a view is a // valid view. In particular, `size()` is known to be smaller than `numeric_limits<difference_type>::max()`, so the - // new size is also smaller. See also https://github.com/llvm/llvm-project/issues/91634. + // new size is also smaller. See also https://llvm.org/PR91634. return __pos > size() ? (__throw_out_of_range("string_view::substr"), basic_string_view()) : basic_string_view(__assume_valid(), data() + __pos, std::min(__n, size() - __pos)); } diff --git a/libcxx/include/tuple b/libcxx/include/tuple index 8cc061c70b89..b0d0c38b115a 100644 --- a/libcxx/include/tuple +++ b/libcxx/include/tuple @@ -232,7 +232,6 @@ template <class... Types> # include <__memory/uses_allocator.h> # include <__tuple/find_index.h> # include <__tuple/ignore.h> -# include <__tuple/make_tuple_types.h> # include <__tuple/tuple_element.h> # include <__tuple/tuple_like.h> # include <__tuple/tuple_like_ext.h> @@ -324,12 +323,6 @@ _LIBCPP_HIDE_FROM_ABI constexpr _Ret __tuple_compare_three_way(const _Tp& __x, c # endif // _LIBCPP_STD_VER >= 20 # if _LIBCPP_STD_VER >= 23 -template <class> -inline constexpr bool __is_tuple_v = false; - -template <class... _Tp> -inline constexpr bool __is_tuple_v<tuple<_Tp...>> = true; - template <class _Tp> concept __tuple_like_no_tuple = __tuple_like<_Tp> && !__is_tuple_v<_Tp>; @@ -540,11 +533,10 @@ struct _LIBCPP_DECLSPEC_EMPTY_BASES template <class _Tuple> _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __tuple_impl(__from_tuple, _Tuple&& __t) noexcept( - (__all<is_nothrow_constructible< - _Tp, - typename tuple_element<_Indx, typename __make_tuple_types<_Tuple>::type>::type>::value...>::value)) + (__all<is_nothrow_constructible<_Tp, __copy_cvref_t<_Tuple, __tuple_element_t<_Indx, __remove_cvref_t<_Tuple>>>>:: + value...>::value)) : __tuple_leaf<_Indx, _Tp>( - std::forward<typename tuple_element<_Indx, typename __make_tuple_types<_Tuple>::type>::type>( + std::forward<__copy_cvref_t<_Tuple, __tuple_element_t<_Indx, __remove_cvref_t<_Tuple>>>>( std::get<_Indx>(__t)))... {} template <class _Alloc, class _Tuple> @@ -553,9 +545,9 @@ struct _LIBCPP_DECLSPEC_EMPTY_BASES : __tuple_leaf<_Indx, _Tp>( __uses_alloc_ctor<_Tp, _Alloc, - typename tuple_element<_Indx, typename __make_tuple_types<_Tuple>::type>::type>(), + __copy_cvref_t<_Tuple, __tuple_element_t<_Indx, __remove_cvref_t<_Tuple>>>>(), __a, - std::forward<typename tuple_element<_Indx, typename __make_tuple_types<_Tuple>::type>::type>( + std::forward<__copy_cvref_t<_Tuple, __tuple_element_t<_Indx, __remove_cvref_t<_Tuple>>>>( std::get<_Indx>(__t)))... {} __tuple_impl(const __tuple_impl&) = default; @@ -1278,47 +1270,37 @@ operator<=(const tuple<_Tp...>& __x, const tuple<_Up...>& __y) { // tuple_cat -template <class _Tp, class _Up> -struct __tuple_cat_type; +template <class... _Tuples> +struct __tuple_cat_return_impl; -template <class... _Ttypes, class... _Utypes> -struct __tuple_cat_type<tuple<_Ttypes...>, __tuple_types<_Utypes...> > { - using type _LIBCPP_NODEBUG = tuple<_Ttypes..., _Utypes...>; +template <class _Tuple> +struct __tuple_cat_return_impl<_Tuple> { + using type _LIBCPP_NODEBUG = _Tuple; }; -template <class _ResultTuple, bool _Is_Tuple0TupleLike, class... _Tuples> -struct __tuple_cat_return_1 {}; +template <class... _Types0, template <class...> class _Tuple, class... _Types1, class... _Tuples> +struct __tuple_cat_return_impl<tuple<_Types0...>, _Tuple<_Types1...>, _Tuples...> + : __tuple_cat_return_impl<tuple<_Types0..., _Types1...>, _Tuples...> {}; -template <class... _Types, class _Tuple0> -struct __tuple_cat_return_1<tuple<_Types...>, true, _Tuple0> { - using type _LIBCPP_NODEBUG = - typename __tuple_cat_type< tuple<_Types...>, - typename __make_tuple_types<__remove_cvref_t<_Tuple0> >::type >::type; -}; +template <class, class, class> +struct __tuple_cat_array; -template <class... _Types, class _Tuple0, class _Tuple1, class... _Tuples> -struct __tuple_cat_return_1<tuple<_Types...>, true, _Tuple0, _Tuple1, _Tuples...> - : public __tuple_cat_return_1< - typename __tuple_cat_type< tuple<_Types...>, - typename __make_tuple_types<__remove_cvref_t<_Tuple0> >::type >::type, - __tuple_like_ext<__libcpp_remove_reference_t<_Tuple1> >::value, - _Tuple1, - _Tuples...> {}; +template <class... _Types, class _ValueT, size_t... _Indices> +struct __tuple_cat_array<tuple<_Types...>, _ValueT, __index_sequence<_Indices...>> { + template <size_t> + using __value_type _LIBCPP_NODEBUG = _ValueT; -template <class... _Tuples> -struct __tuple_cat_return; + using type _LIBCPP_NODEBUG = tuple<_Types..., __value_type<_Indices>...>; +}; -template <class _Tuple0, class... _Tuples> -struct __tuple_cat_return<_Tuple0, _Tuples...> - : public __tuple_cat_return_1<tuple<>, - __tuple_like_ext<__libcpp_remove_reference_t<_Tuple0> >::value, - _Tuple0, - _Tuples...> {}; +template <class... _Types, class _ValueT, size_t _Np, class... _Tuples> +struct __tuple_cat_return_impl<tuple<_Types...>, array<_ValueT, _Np>, _Tuples...> + : __tuple_cat_return_impl<typename __tuple_cat_array<tuple<_Types...>, _ValueT, __make_index_sequence<_Np>>::type, + _Tuples...> {}; -template <> -struct __tuple_cat_return<> { - using type _LIBCPP_NODEBUG = tuple<>; -}; +template <class... _Tuples> +using __tuple_cat_return_t _LIBCPP_NODEBUG = + typename __tuple_cat_return_impl<tuple<>, __remove_cvref_t<_Tuples>...>::type; inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 tuple<> tuple_cat() { return tuple<>(); } @@ -1387,11 +1369,15 @@ __tuple_cat_select_element_wise(_TupleSrc&& __src, __index_sequence<_Indices...> return _TupleDst(std::get<_Indices>(std::forward<_TupleSrc>(__src))...); } -template <class _Tuple0, class... _Tuples> -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 typename __tuple_cat_return<_Tuple0, _Tuples...>::type +template <class _Tuple0, + class... _Tuples, + __enable_if_t< + _And<__tuple_like_ext<__remove_cvref_t<_Tuple0>>, __tuple_like_ext<__remove_cvref_t<_Tuples>>...>::value, + int> = 0> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __tuple_cat_return_t<_Tuple0, _Tuples...> tuple_cat(_Tuple0&& __t0, _Tuples&&... __tpls) { using _T0 _LIBCPP_NODEBUG = __libcpp_remove_reference_t<_Tuple0>; - using _TRet _LIBCPP_NODEBUG = typename __tuple_cat_return<_Tuple0, _Tuples...>::type; + using _TRet _LIBCPP_NODEBUG = __tuple_cat_return_t<_Tuple0, _Tuples...>; using _T0Indices _LIBCPP_NODEBUG = __make_index_sequence<tuple_size<_T0>::value>; using _TRetIndices _LIBCPP_NODEBUG = __make_index_sequence<tuple_size<_TRet>::value>; return std::__tuple_cat_select_element_wise<_TRet>( diff --git a/libcxx/include/unordered_map b/libcxx/include/unordered_map index a93495367496..a38e5e0f1b94 100644 --- a/libcxx/include/unordered_map +++ b/libcxx/include/unordered_map @@ -844,8 +844,8 @@ class __hash_map_iterator { public: typedef forward_iterator_tag iterator_category; - using value_type = typename _HashIterator::value_type; - typedef typename _NodeTypes::difference_type difference_type; + using value_type = typename _HashIterator::value_type; + using difference_type = ptrdiff_t; typedef value_type& reference; using pointer = typename _HashIterator::pointer; @@ -895,8 +895,8 @@ class __hash_map_const_iterator { public: typedef forward_iterator_tag iterator_category; - using value_type = typename _HashIterator::value_type; - typedef typename _NodeTypes::difference_type difference_type; + using value_type = typename _HashIterator::value_type; + using difference_type = ptrdiff_t; typedef const value_type& reference; using pointer = typename _HashIterator::pointer; @@ -972,9 +972,6 @@ private: __table __table_; - typedef typename __table::_NodeTypes _NodeTypes; - typedef typename __table::__node_pointer __node_pointer; - typedef typename __table::__node_const_pointer __node_const_pointer; typedef typename __table::__node_traits __node_traits; typedef typename __table::__node_allocator __node_allocator; typedef typename __table::__node __node; @@ -1172,14 +1169,13 @@ public: # if _LIBCPP_STD_VER >= 17 template <class... _Args> _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) { - return __table_.__emplace_unique_key_args( - __k, piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple(std::forward<_Args>(__args)...)); + return __table_.__emplace_unique( + piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple(std::forward<_Args>(__args)...)); } template <class... _Args> _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) { - return __table_.__emplace_unique_key_args( - __k, + return __table_.__emplace_unique( piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple(std::forward<_Args>(__args)...)); @@ -1197,7 +1193,7 @@ public: template <class _Vp> _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) { - pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, __k, std::forward<_Vp>(__v)); + pair<iterator, bool> __res = __table_.__emplace_unique(__k, std::forward<_Vp>(__v)); if (!__res.second) { __res.first->second = std::forward<_Vp>(__v); } @@ -1206,7 +1202,7 @@ public: template <class _Vp> _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) { - pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, std::move(__k), std::forward<_Vp>(__v)); + pair<iterator, bool> __res = __table_.__emplace_unique(std::move(__k), std::forward<_Vp>(__v)); if (!__res.second) { __res.first->second = std::forward<_Vp>(__v); } @@ -1612,16 +1608,13 @@ inline void unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterato template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> _Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) { - return __table_ - .__emplace_unique_key_args(__k, piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple()) + return __table_.__emplace_unique(piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple()) .first->second; } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> _Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) { - return __table_ - .__emplace_unique_key_args( - __k, piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple()) + return __table_.__emplace_unique(piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple()) .first->second; } # else // _LIBCPP_CXX03_LANG @@ -1747,12 +1740,8 @@ private: __table __table_; - typedef typename __table::_NodeTypes _NodeTypes; typedef typename __table::__node_traits __node_traits; - typedef typename __table::__node_allocator __node_allocator; typedef typename __table::__node __node; - typedef __hash_map_node_destructor<__node_allocator> _Dp; - typedef unique_ptr<__node, _Dp> __node_holder; typedef allocator_traits<allocator_type> __alloc_traits; static_assert(is_same<typename __node_traits::size_type, typename __alloc_traits::size_type>::value, "Allocator uses different size_type for different types"); |