llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-lldb Author: Nikolas Klauser (philnik777) <details> <summary>Changes</summary> This reverts commit 72c04bb882ad70230bce309c3013d9cc2c99e9a7. --- Patch is 45.64 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/155565.diff 16 Files Affected: - (modified) libcxx/include/CMakeLists.txt (+1-1) - (modified) libcxx/include/__fwd/tuple.h (+6) - (modified) libcxx/include/__hash_table (+65-103) - (modified) libcxx/include/__tree (+58-141) - (removed) libcxx/include/__type_traits/can_extract_key.h (-53) - (added) libcxx/include/__utility/try_key_extraction.h (+114) - (modified) libcxx/include/map (+13-25) - (modified) libcxx/include/module.modulemap.in (+1-1) - (modified) libcxx/include/set (+3-3) - (modified) libcxx/include/tuple (-6) - (modified) libcxx/include/unordered_map (+7-11) - (modified) libcxx/test/std/containers/associative/multiset/emplace.pass.cpp (+8-2) - (modified) libcxx/test/std/containers/associative/set/emplace.pass.cpp (+9-2) - (modified) libcxx/test/std/containers/unord/unord.multiset/emplace.pass.cpp (+11-2) - (modified) libcxx/test/std/containers/unord/unord.set/emplace.pass.cpp (+12-2) - (modified) lldb/test/API/lang/cpp/libcxx-internals-recognizer/TestLibcxxInternalsRecognizer.py (+1) ``````````diff diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt index c6b87a34a43e9..6fd16419f0c49 100644 --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -792,7 +792,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 @@ -933,6 +932,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/__fwd/tuple.h b/libcxx/include/__fwd/tuple.h index 39ed94d9806e5..b3cac4e2a633d 100644 --- a/libcxx/include/__fwd/tuple.h +++ b/libcxx/include/__fwd/tuple.h @@ -26,6 +26,12 @@ struct tuple_element; 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 f0f335a4d5cab..91f660d3491e8 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) @@ -797,40 +797,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 +1025,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>()); @@ -1614,69 +1640,6 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(const_iterator __p return __node_insert_multi(__cp); } -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 @@ -1928,15 +1891,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; } diff --git a/libcxx/include/__tree b/libcxx/include/__tree index 0f3640ef6a834..3ad2129ba9ddf 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> @@ -38,6 +37,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) @@ -900,88 +900,74 @@ 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) { + __end_node_pointer __parent; + __node_base_pointer& __child = __find_equal(__parent, __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)...); + __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); + }, + 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) { + __end_node_pointer __parent; + __node_base_pointer __dummy; + __node_base_pointer& __child = __find_equal(__p, __parent, __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)...); + __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 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> @@ -1801,42 +1787,6 @@ void __tree<_Tp, _Compare, _Allocator>::__insert_node_at( ++__size_; } -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.rele... [truncated] `````````` </details> https://github.com/llvm/llvm-project/pull/155565 _______________________________________________ lldb-commits mailing list lldb-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
