diff options
Diffstat (limited to 'contrib/llvm-project/libcxx/include/__hash_table')
| -rw-r--r-- | contrib/llvm-project/libcxx/include/__hash_table | 500 |
1 files changed, 270 insertions, 230 deletions
diff --git a/contrib/llvm-project/libcxx/include/__hash_table b/contrib/llvm-project/libcxx/include/__hash_table index 2ae7afdc10de..fa950ac7e9b7 100644 --- a/contrib/llvm-project/libcxx/include/__hash_table +++ b/contrib/llvm-project/libcxx/include/__hash_table @@ -21,6 +21,7 @@ #include <__memory/addressof.h> #include <__memory/allocator_traits.h> #include <__memory/compressed_pair.h> +#include <__memory/construct_at.h> #include <__memory/pointer_traits.h> #include <__memory/swap_allocator.h> #include <__memory/unique_ptr.h> @@ -45,6 +46,7 @@ #include <cmath> #include <cstring> #include <initializer_list> +#include <new> // __launder #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -89,47 +91,72 @@ struct __hash_node_base __next_pointer __next_; - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI __next_pointer __ptr() _NOEXCEPT { return static_cast<__next_pointer>( pointer_traits<__node_base_pointer>::pointer_to(*this)); } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI __node_pointer __upcast() _NOEXCEPT { return static_cast<__node_pointer>( pointer_traits<__node_base_pointer>::pointer_to(*this)); } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_t __hash() const _NOEXCEPT { return static_cast<__node_type const&>(*this).__hash_; } - _LIBCPP_INLINE_VISIBILITY __hash_node_base() _NOEXCEPT : __next_(nullptr) {} + _LIBCPP_HIDE_FROM_ABI __hash_node_base() _NOEXCEPT : __next_(nullptr) {} + _LIBCPP_HIDE_FROM_ABI explicit __hash_node_base(__next_pointer __next) _NOEXCEPT : __next_(__next) {} }; template <class _Tp, class _VoidPtr> -struct _LIBCPP_STANDALONE_DEBUG __hash_node +struct __hash_node : public __hash_node_base < __rebind_pointer_t<_VoidPtr, __hash_node<_Tp, _VoidPtr> > > { typedef _Tp __node_value_type; + using _Base = __hash_node_base<__rebind_pointer_t<_VoidPtr, __hash_node<_Tp, _VoidPtr> > >; + using __next_pointer = typename _Base::__next_pointer; size_t __hash_; - __node_value_type __value_; + + // We allow starting the lifetime of nodes without initializing the value held by the node, + // since that is handled by the hash table itself in order to be allocator-aware. +#ifndef _LIBCPP_CXX03_LANG +private: + union { + _Tp __value_; + }; + +public: + _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return __value_; } +#else +private: + _ALIGNAS_TYPE(_Tp) char __buffer_[sizeof(_Tp)]; + +public: + _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { + return *std::__launder(reinterpret_cast<_Tp*>(&__buffer_)); + } +#endif + + _LIBCPP_HIDE_FROM_ABI explicit __hash_node(__next_pointer __next, size_t __hash) : _Base(__next), __hash_(__hash) {} + _LIBCPP_HIDE_FROM_ABI ~__hash_node() {} }; -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_HIDE_FROM_ABI bool __is_hash_power2(size_t __bc) { return __bc > 2 && !(__bc & (__bc - 1)); } -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_HIDE_FROM_ABI size_t __constrain_hash(size_t __h, size_t __bc) { @@ -137,7 +164,7 @@ __constrain_hash(size_t __h, size_t __bc) (__h < __bc ? __h : __h % __bc); } -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_HIDE_FROM_ABI size_t __next_hash_pow2(size_t __n) { @@ -162,21 +189,21 @@ struct __hash_key_value_types { typedef _Tp __container_value_type; static const bool __is_map = false; - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI static key_type const& __get_key(_Tp const& __v) { return __v; } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI static __container_value_type const& __get_value(__node_value_type const& __v) { return __v; } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI static __container_value_type* __get_ptr(__node_value_type& __n) { - return _VSTD::addressof(__n); + return std::addressof(__n); } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI static __container_value_type&& __move(__node_value_type& __v) { - return _VSTD::move(__v); + return std::move(__v); } }; @@ -189,30 +216,30 @@ struct __hash_key_value_types<__hash_value_type<_Key, _Tp> > { typedef __container_value_type __map_value_type; static const bool __is_map = true; - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI static key_type const& __get_key(__container_value_type const& __v) { return __v.first; } - template <class _Up> - _LIBCPP_INLINE_VISIBILITY - static __enable_if_t<__is_same_uncvref<_Up, __node_value_type>::value, __container_value_type const&> + template <class _Up, __enable_if_t<__is_same_uncvref<_Up, __node_value_type>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI + static __container_value_type const& __get_value(_Up& __t) { return __t.__get_value(); } - template <class _Up> - _LIBCPP_INLINE_VISIBILITY - static __enable_if_t<__is_same_uncvref<_Up, __container_value_type>::value, __container_value_type const&> + template <class _Up, __enable_if_t<__is_same_uncvref<_Up, __container_value_type>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI + static __container_value_type const& __get_value(_Up& __t) { return __t; } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI static __container_value_type* __get_ptr(__node_value_type& __n) { - return _VSTD::addressof(__n.__get_value()); + return std::addressof(__n.__get_value()); } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI static pair<key_type&&, mapped_type&&> __move(__node_value_type& __v) { return __v.__move(); } @@ -306,26 +333,26 @@ public: typedef value_type& reference; typedef typename _NodeTypes::__node_value_type_pointer pointer; - _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT : __node_(nullptr) { + _LIBCPP_HIDE_FROM_ABI __hash_iterator() _NOEXCEPT : __node_(nullptr) { } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI reference operator*() const { - return __node_->__upcast()->__value_; + return __node_->__upcast()->__get_value(); } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI pointer operator->() const { - return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_); + return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value()); } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI __hash_iterator& operator++() { __node_ = __node_->__next_; return *this; } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI __hash_iterator operator++(int) { __hash_iterator __t(*this); @@ -333,17 +360,17 @@ public: return __t; } - friend _LIBCPP_INLINE_VISIBILITY + friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_iterator& __x, const __hash_iterator& __y) { return __x.__node_ == __y.__node_; } - friend _LIBCPP_INLINE_VISIBILITY + friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y) {return !(__x == __y);} private: - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI explicit __hash_iterator(__next_pointer __node) _NOEXCEPT : __node_(__node) { @@ -376,31 +403,31 @@ public: typedef typename _NodeTypes::__const_node_value_type_pointer pointer; - _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT : __node_(nullptr) { + _LIBCPP_HIDE_FROM_ABI __hash_const_iterator() _NOEXCEPT : __node_(nullptr) { } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT : __node_(__x.__node_) { } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI reference operator*() const { - return __node_->__upcast()->__value_; + return __node_->__upcast()->__get_value(); } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI pointer operator->() const { - return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_); + return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value()); } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI __hash_const_iterator& operator++() { __node_ = __node_->__next_; return *this; } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI __hash_const_iterator operator++(int) { __hash_const_iterator __t(*this); @@ -408,17 +435,17 @@ public: return __t; } - friend _LIBCPP_INLINE_VISIBILITY + friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y) { return __x.__node_ == __y.__node_; } - friend _LIBCPP_INLINE_VISIBILITY + friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y) {return !(__x == __y);} private: - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI explicit __hash_const_iterator(__next_pointer __node) _NOEXCEPT : __node_(__node) { @@ -448,20 +475,20 @@ public: typedef value_type& reference; typedef typename _NodeTypes::__node_value_type_pointer pointer; - _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT : __node_(nullptr) { + _LIBCPP_HIDE_FROM_ABI __hash_local_iterator() _NOEXCEPT : __node_(nullptr) { } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI reference operator*() const { - return __node_->__upcast()->__value_; + return __node_->__upcast()->__get_value(); } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI pointer operator->() const { - return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_); + return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value()); } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI __hash_local_iterator& operator++() { __node_ = __node_->__next_; if (__node_ != nullptr && std::__constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_) @@ -469,7 +496,7 @@ public: return *this; } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI __hash_local_iterator operator++(int) { __hash_local_iterator __t(*this); @@ -477,17 +504,17 @@ public: return __t; } - friend _LIBCPP_INLINE_VISIBILITY + friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y) { return __x.__node_ == __y.__node_; } - friend _LIBCPP_INLINE_VISIBILITY + friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y) {return !(__x == __y);} private: - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI explicit __hash_local_iterator(__next_pointer __node, size_t __bucket, size_t __bucket_count) _NOEXCEPT : __node_(__node), @@ -530,10 +557,10 @@ public: typedef typename _NodeTypes::__const_node_value_type_pointer pointer; - _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT : __node_(nullptr) { + _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator() _NOEXCEPT : __node_(nullptr) { } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT : __node_(__x.__node_), __bucket_(__x.__bucket_), @@ -541,17 +568,17 @@ public: { } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI reference operator*() const { - return __node_->__upcast()->__value_; + return __node_->__upcast()->__get_value(); } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI pointer operator->() const { - return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_); + return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value()); } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator& operator++() { __node_ = __node_->__next_; if (__node_ != nullptr && std::__constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_) @@ -559,7 +586,7 @@ public: return *this; } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator operator++(int) { __hash_const_local_iterator __t(*this); @@ -567,17 +594,17 @@ public: return __t; } - friend _LIBCPP_INLINE_VISIBILITY + friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) { return __x.__node_ == __y.__node_; } - friend _LIBCPP_INLINE_VISIBILITY + friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) {return !(__x == __y);} private: - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI explicit __hash_const_local_iterator(__next_pointer __node_ptr, size_t __bucket, size_t __bucket_count) _NOEXCEPT : __node_(__node_ptr), @@ -603,35 +630,35 @@ class __bucket_list_deallocator public: typedef typename __alloc_traits::pointer pointer; - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI __bucket_list_deallocator() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) : __data_(0, __default_init_tag()) {} - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI __bucket_list_deallocator(const allocator_type& __a, size_type __size) _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value) : __data_(__size, __a) {} - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI __bucket_list_deallocator(__bucket_list_deallocator&& __x) _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) - : __data_(_VSTD::move(__x.__data_)) + : __data_(std::move(__x.__data_)) { __x.size() = 0; } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_type& size() _NOEXCEPT {return __data_.first();} - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT {return __data_.first();} - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI allocator_type& __alloc() _NOEXCEPT {return __data_.second();} - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI const allocator_type& __alloc() const _NOEXCEPT {return __data_.second();} - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT { __alloc_traits::deallocate(__alloc(), __p, size()); @@ -660,18 +687,20 @@ public: _LIBCPP_HIDE_FROM_ABI __hash_node_destructor& operator=(const __hash_node_destructor&) = delete; - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI explicit __hash_node_destructor(allocator_type& __na, bool __constructed = false) _NOEXCEPT : __na_(__na), __value_constructed(__constructed) {} - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT { - if (__value_constructed) - __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_)); + if (__value_constructed) { + __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__get_value())); + std::__destroy_at(std::addressof(*__p)); + } if (__p) __alloc_traits::deallocate(__na_, __p, 1); } @@ -786,30 +815,30 @@ private: __compressed_pair<float, key_equal> __p3_; // --- Member data end --- - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_type& size() _NOEXCEPT {return __p2_.first();} public: - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT {return __p2_.first();} - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI hasher& hash_function() _NOEXCEPT {return __p2_.second();} - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI const hasher& hash_function() const _NOEXCEPT {return __p2_.second();} - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI float& max_load_factor() _NOEXCEPT {return __p3_.first();} - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT {return __p3_.first();} - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI key_equal& key_eq() _NOEXCEPT {return __p3_.second();} - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();} - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();} - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI const __node_allocator& __node_alloc() const _NOEXCEPT {return __p1_.second();} @@ -819,7 +848,7 @@ public: typedef __hash_local_iterator<__node_pointer> local_iterator; typedef __hash_const_local_iterator<__node_pointer> const_local_iterator; - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI __hash_table() _NOEXCEPT_( is_nothrow_default_constructible<__bucket_list>::value && @@ -827,7 +856,7 @@ public: is_nothrow_default_constructible<__node_allocator>::value && is_nothrow_default_constructible<hasher>::value && is_nothrow_default_constructible<key_equal>::value); - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI __hash_table(const hasher& __hf, const key_equal& __eql); _LIBCPP_HIDE_FROM_ABI __hash_table(const hasher& __hf, const key_equal& __eql, const allocator_type& __a); @@ -845,7 +874,7 @@ public: _LIBCPP_HIDE_FROM_ABI ~__hash_table(); _LIBCPP_HIDE_FROM_ABI __hash_table& operator=(const __hash_table& __u); - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI __hash_table& operator=(__hash_table&& __u) _NOEXCEPT_( __node_traits::propagate_on_container_move_assignment::value && @@ -857,182 +886,183 @@ public: template <class _InputIterator> _LIBCPP_HIDE_FROM_ABI void __assign_multi(_InputIterator __first, _InputIterator __last); - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { - return _VSTD::min<size_type>( + return std::min<size_type>( __node_traits::max_size(__node_alloc()), numeric_limits<difference_type >::max() ); } private: - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI __next_pointer __node_insert_multi_prepare(size_t __cp_hash, value_type& __cp_val); - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI void __node_insert_multi_perform(__node_pointer __cp, __next_pointer __pn) _NOEXCEPT; - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI __next_pointer __node_insert_unique_prepare(size_t __nd_hash, value_type& __nd_val); - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI void __node_insert_unique_perform(__node_pointer __ptr) _NOEXCEPT; public: - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __node_insert_unique(__node_pointer __nd); - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(__node_pointer __nd); - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); template <class _Key, class ..._Args> - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_key_args(_Key const& __k, _Args&&... __args); template <class... _Args> - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_impl(_Args&&... __args); template <class _Pp> - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Pp&& __x) { - return __emplace_unique_extract_key(_VSTD::forward<_Pp>(__x), + return __emplace_unique_extract_key(std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>()); } - template <class _First, class _Second> - _LIBCPP_INLINE_VISIBILITY - __enable_if_t<__can_extract_map_key<_First, key_type, __container_value_type>::value, pair<iterator, bool> > + template <class _First, class _Second, + __enable_if_t<__can_extract_map_key<_First, key_type, __container_value_type>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI + pair<iterator, bool> __emplace_unique(_First&& __f, _Second&& __s) { - return __emplace_unique_key_args(__f, _VSTD::forward<_First>(__f), - _VSTD::forward<_Second>(__s)); + return __emplace_unique_key_args(__f, std::forward<_First>(__f), + std::forward<_Second>(__s)); } template <class... _Args> - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Args&&... __args) { - return __emplace_unique_impl(_VSTD::forward<_Args>(__args)...); + return __emplace_unique_impl(std::forward<_Args>(__args)...); } template <class _Pp> - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) { - return __emplace_unique_impl(_VSTD::forward<_Pp>(__x)); + return __emplace_unique_impl(std::forward<_Pp>(__x)); } template <class _Pp> - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) { - return __emplace_unique_key_args(__x, _VSTD::forward<_Pp>(__x)); + return __emplace_unique_key_args(__x, std::forward<_Pp>(__x)); } template <class _Pp> - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) { - return __emplace_unique_key_args(__x.first, _VSTD::forward<_Pp>(__x)); + return __emplace_unique_key_args(__x.first, std::forward<_Pp>(__x)); } template <class... _Args> - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI iterator __emplace_multi(_Args&&... __args); template <class... _Args> - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(__container_value_type&& __x) { - return __emplace_unique_key_args(_NodeTypes::__get_key(__x), _VSTD::move(__x)); + return __emplace_unique_key_args(_NodeTypes::__get_key(__x), std::move(__x)); } template <class _Pp, class = __enable_if_t<!__is_same_uncvref<_Pp, __container_value_type>::value> > - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(_Pp&& __x) { - return __emplace_unique(_VSTD::forward<_Pp>(__x)); + return __emplace_unique(std::forward<_Pp>(__x)); } template <class _Pp> - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI iterator __insert_multi(_Pp&& __x) { - return __emplace_multi(_VSTD::forward<_Pp>(__x)); + return __emplace_multi(std::forward<_Pp>(__x)); } template <class _Pp> - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI iterator __insert_multi(const_iterator __p, _Pp&& __x) { - return __emplace_hint_multi(__p, _VSTD::forward<_Pp>(__x)); + return __emplace_hint_multi(__p, std::forward<_Pp>(__x)); } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(const __container_value_type& __x) { return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x); } #if _LIBCPP_STD_VER >= 17 template <class _NodeHandle, class _InsertReturnType> - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI _InsertReturnType __node_handle_insert_unique(_NodeHandle&& __nh); template <class _NodeHandle> - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_unique(const_iterator __hint, _NodeHandle&& __nh); template <class _Table> - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_unique(_Table& __source); template <class _NodeHandle> - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(_NodeHandle&& __nh); template <class _NodeHandle> - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh); template <class _Table> - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_multi(_Table& __source); template <class _NodeHandle> - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI _NodeHandle __node_handle_extract(key_type const& __key); template <class _NodeHandle> - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI _NodeHandle __node_handle_extract(const_iterator __it); #endif _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT; - _LIBCPP_INLINE_VISIBILITY void __rehash_unique(size_type __n) { __rehash<true>(__n); } - _LIBCPP_INLINE_VISIBILITY void __rehash_multi(size_type __n) { __rehash<false>(__n); } - _LIBCPP_INLINE_VISIBILITY void __reserve_unique(size_type __n) + _LIBCPP_HIDE_FROM_ABI void __rehash_unique(size_type __n) { __rehash<true>(__n); } + _LIBCPP_HIDE_FROM_ABI void __rehash_multi(size_type __n) { __rehash<false>(__n); } + _LIBCPP_HIDE_FROM_ABI void __reserve_unique(size_type __n) { __rehash_unique(static_cast<size_type>(std::ceil(__n / max_load_factor()))); } - _LIBCPP_INLINE_VISIBILITY void __reserve_multi(size_type __n) + _LIBCPP_HIDE_FROM_ABI void __reserve_multi(size_type __n) { __rehash_multi(static_cast<size_type>(std::ceil(__n / max_load_factor()))); } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __bucket_list_.get_deleter().size(); } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT; - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT; - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT; - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT; template <class _Key> - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_type bucket(const _Key& __k) const { _LIBCPP_ASSERT_UNCATEGORIZED(bucket_count() > 0, @@ -1057,7 +1087,7 @@ public: _LIBCPP_HIDE_FROM_ABI __node_holder remove(const_iterator __p) _NOEXCEPT; template <class _Key> - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_type __count_unique(const _Key& __k) const; template <class _Key> _LIBCPP_HIDE_FROM_ABI size_type __count_multi(const _Key& __k) const; @@ -1089,23 +1119,23 @@ public: _NOEXCEPT_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value); #endif - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT {return max_size(); } _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const; - _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT + _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { size_type __bc = bucket_count(); return __bc != 0 ? (float)size() / __bc : 0.f; } - _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT + _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) _NOEXCEPT { _LIBCPP_ASSERT_UNCATEGORIZED(__mlf > 0, "unordered container::max_load_factor(lf) called with lf <= 0"); - max_load_factor() = _VSTD::max(__mlf, load_factor()); + max_load_factor() = std::max(__mlf, load_factor()); } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { @@ -1114,7 +1144,7 @@ public: return local_iterator(__bucket_list_[__n], __n, bucket_count()); } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { @@ -1123,7 +1153,7 @@ public: return local_iterator(nullptr, __n, bucket_count()); } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { @@ -1132,7 +1162,7 @@ public: return const_local_iterator(__bucket_list_[__n], __n, bucket_count()); } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { @@ -1154,12 +1184,12 @@ private: _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest); - _LIBCPP_INLINE_VISIBILITY + _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>());} _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table& __u, true_type); - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table&, false_type) {} _LIBCPP_HIDE_FROM_ABI void __move_assign(__hash_table& __u, false_type); @@ -1168,7 +1198,7 @@ private: is_nothrow_move_assignable<__node_allocator>::value && is_nothrow_move_assignable<hasher>::value && is_nothrow_move_assignable<key_equal>::value); - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table& __u) _NOEXCEPT_( !__node_traits::propagate_on_container_move_assignment::value || @@ -1176,17 +1206,17 @@ private: is_nothrow_move_assignable<__node_allocator>::value)) {__move_assign_alloc(__u, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());} - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table& __u, true_type) _NOEXCEPT_( is_nothrow_move_assignable<__pointer_allocator>::value && is_nothrow_move_assignable<__node_allocator>::value) { __bucket_list_.get_deleter().__alloc() = - _VSTD::move(__u.__bucket_list_.get_deleter().__alloc()); - __node_alloc() = _VSTD::move(__u.__node_alloc()); + std::move(__u.__bucket_list_.get_deleter().__alloc()); + __node_alloc() = std::move(__u.__node_alloc()); } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {} _LIBCPP_HIDE_FROM_ABI void __deallocate_node(__next_pointer __np) _NOEXCEPT; @@ -1272,10 +1302,10 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) is_nothrow_move_constructible<__node_allocator>::value && is_nothrow_move_constructible<hasher>::value && is_nothrow_move_constructible<key_equal>::value) - : __bucket_list_(_VSTD::move(__u.__bucket_list_)), - __p1_(_VSTD::move(__u.__p1_)), - __p2_(_VSTD::move(__u.__p2_)), - __p3_(_VSTD::move(__u.__p3_)) + : __bucket_list_(std::move(__u.__bucket_list_)), + __p1_(std::move(__u.__p1_)), + __p2_(std::move(__u.__p2_)), + __p3_(std::move(__u.__p3_)) { if (size() > 0) { @@ -1291,8 +1321,8 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, const allocator_type& __a) : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), __p1_(__default_init_tag(), __node_allocator(__a)), - __p2_(0, _VSTD::move(__u.hash_function())), - __p3_(_VSTD::move(__u.__p3_)) + __p2_(0, std::move(__u.hash_function())), + __p3_(std::move(__u.__p3_)) { if (__a == allocator_type(__u.__node_alloc())) { @@ -1343,7 +1373,7 @@ template <class _Tp, class _Hash, class _Equal, class _Alloc> __hash_table<_Tp, _Hash, _Equal, _Alloc>& __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u) { - if (this != _VSTD::addressof(__u)) + if (this != std::addressof(__u)) { __copy_assign_alloc(__u); hash_function() = __u.hash_function(); @@ -1364,7 +1394,8 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate_node(__next_pointer __np) { __next_pointer __next = __np->__next_; __node_pointer __real_np = __np->__upcast(); - __node_traits::destroy(__na, _NodeTypes::__get_ptr(__real_np->__value_)); + __node_traits::destroy(__na, _NodeTypes::__get_ptr(__real_np->__get_value())); + std::__destroy_at(std::addressof(*__real_np)); __node_traits::deallocate(__na, __real_np, 1); __np = __next; } @@ -1398,9 +1429,9 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( __u.__bucket_list_.get_deleter().size() = 0; __move_assign_alloc(__u); size() = __u.size(); - hash_function() = _VSTD::move(__u.hash_function()); + hash_function() = std::move(__u.hash_function()); max_load_factor() = __u.max_load_factor(); - key_eq() = _VSTD::move(__u.key_eq()); + key_eq() = std::move(__u.key_eq()); __p1_.first().__next_ = __u.__p1_.first().__next_; if (size() > 0) { @@ -1420,8 +1451,8 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( __move_assign(__u, true_type()); else { - hash_function() = _VSTD::move(__u.hash_function()); - key_eq() = _VSTD::move(__u.key_eq()); + hash_function() = std::move(__u.hash_function()); + key_eq() = std::move(__u.key_eq()); max_load_factor() = __u.max_load_factor(); if (bucket_count() != 0) { @@ -1433,8 +1464,8 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( const_iterator __i = __u.begin(); while (__cache != nullptr && __u.size() != 0) { - __cache->__upcast()->__value_ = - _VSTD::move(__u.remove(__i++)->__value_); + __cache->__upcast()->__get_value() = + std::move(__u.remove(__i++)->__get_value()); __next_pointer __next = __cache->__next_; __node_insert_multi(__cache->__upcast()); __cache = __next; @@ -1452,7 +1483,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( const_iterator __i = __u.begin(); while (__u.size() != 0) { - __node_holder __h = __construct_node(_NodeTypes::__move(__u.remove(__i++)->__value_)); + __node_holder __h = __construct_node(_NodeTypes::__move(__u.remove(__i++)->__get_value())); __node_insert_multi(__h.get()); __h.release(); } @@ -1494,7 +1525,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first #endif // _LIBCPP_HAS_NO_EXCEPTIONS for (; __cache != nullptr && __first != __last; ++__first) { - __cache->__upcast()->__value_ = *__first; + __cache->__upcast()->__get_value() = *__first; __next_pointer __next = __cache->__next_; __node_insert_unique(__cache->__upcast()); __cache = __next; @@ -1534,7 +1565,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first, #endif // _LIBCPP_HAS_NO_EXCEPTIONS for (; __cache != nullptr && __first != __last; ++__first) { - __cache->__upcast()->__value_ = *__first; + __cache->__upcast()->__get_value() = *__first; __next_pointer __next = __cache->__next_; __node_insert_multi(__cache->__upcast()); __cache = __next; @@ -1609,7 +1640,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT // Note that this function does forward exceptions if key_eq() throws, and never // mutates __value or actually inserts into the map. template <class _Tp, class _Hash, class _Equal, class _Alloc> -_LIBCPP_INLINE_VISIBILITY +_LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_prepare( size_t __hash, value_type& __value) @@ -1628,14 +1659,14 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_prepare( __ndptr = __ndptr->__next_) { if ((__ndptr->__hash() == __hash) && - key_eq()(__ndptr->__upcast()->__value_, __value)) + key_eq()(__ndptr->__upcast()->__get_value(), __value)) return __ndptr; } } } if (size()+1 > __bc * max_load_factor() || __bc == 0) { - __rehash_unique(_VSTD::max<size_type>(2 * __bc + !std::__is_hash_power2(__bc), + __rehash_unique(std::max<size_type>(2 * __bc + !std::__is_hash_power2(__bc), size_type(std::ceil(float(size() + 1) / max_load_factor())))); } return nullptr; @@ -1646,7 +1677,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_prepare( // rehashing has already occurred and that no element with the same key exists // in the map. template <class _Tp, class _Hash, class _Equal, class _Alloc> -_LIBCPP_INLINE_VISIBILITY +_LIBCPP_HIDE_FROM_ABI void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_perform( __node_pointer __nd) _NOEXCEPT @@ -1677,9 +1708,9 @@ template <class _Tp, class _Hash, class _Equal, class _Alloc> pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) { - __nd->__hash_ = hash_function()(__nd->__value_); + __nd->__hash_ = hash_function()(__nd->__get_value()); __next_pointer __existing_node = - __node_insert_unique_prepare(__nd->__hash(), __nd->__value_); + __node_insert_unique_prepare(__nd->__hash(), __nd->__get_value()); // Insert the node, unless it already exists in the container. bool __inserted = false; @@ -1707,7 +1738,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare( size_type __bc = bucket_count(); if (size()+1 > __bc * max_load_factor() || __bc == 0) { - __rehash_multi(_VSTD::max<size_type>(2 * __bc + !std::__is_hash_power2(__bc), + __rehash_multi(std::max<size_type>(2 * __bc + !std::__is_hash_power2(__bc), size_type(std::ceil(float(size() + 1) / max_load_factor())))); __bc = bucket_count(); } @@ -1725,7 +1756,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare( // false true set __found to true // true false break if (__found != (__pn->__next_->__hash() == __cp_hash && - key_eq()(__pn->__next_->__upcast()->__value_, __cp_val))) + key_eq()(__pn->__next_->__upcast()->__get_value(), __cp_val))) { if (!__found) __found = true; @@ -1779,8 +1810,8 @@ template <class _Tp, class _Hash, class _Equal, class _Alloc> typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) { - __cp->__hash_ = hash_function()(__cp->__value_); - __next_pointer __pn = __node_insert_multi_prepare(__cp->__hash(), __cp->__value_); + __cp->__hash_ = hash_function()(__cp->__get_value()); + __next_pointer __pn = __node_insert_multi_prepare(__cp->__hash(), __cp->__get_value()); __node_insert_multi_perform(__cp, __pn); return iterator(__cp->__ptr()); @@ -1791,14 +1822,14 @@ typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi( const_iterator __p, __node_pointer __cp) { - if (__p != end() && key_eq()(*__p, __cp->__value_)) + if (__p != end() && key_eq()(*__p, __cp->__get_value())) { __next_pointer __np = __p.__node_; __cp->__hash_ = __np->__hash(); size_type __bc = bucket_count(); if (size()+1 > __bc * max_load_factor() || __bc == 0) { - __rehash_multi(_VSTD::max<size_type>(2 * __bc + !std::__is_hash_power2(__bc), + __rehash_multi(std::max<size_type>(2 * __bc + !std::__is_hash_power2(__bc), size_type(std::ceil(float(size() + 1) / max_load_factor())))); __bc = bucket_count(); } @@ -1838,16 +1869,16 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __nd = __nd->__next_) { if ((__nd->__hash() == __hash) && - key_eq()(__nd->__upcast()->__value_, __k)) + key_eq()(__nd->__upcast()->__get_value(), __k)) goto __done; } } } { - __node_holder __h = __construct_node_hash(__hash, _VSTD::forward<_Args>(__args)...); + __node_holder __h = __construct_node_hash(__hash, std::forward<_Args>(__args)...); if (size()+1 > __bc * max_load_factor() || __bc == 0) { - __rehash_unique(_VSTD::max<size_type>(2 * __bc + !std::__is_hash_power2(__bc), + __rehash_unique(std::max<size_type>(2 * __bc + !std::__is_hash_power2(__bc), size_type(std::ceil(float(size() + 1) / max_load_factor())))); __bc = bucket_count(); __chash = std::__constrain_hash(__hash, __bc); @@ -1884,7 +1915,7 @@ 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(_VSTD::forward<_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(); @@ -1896,7 +1927,7 @@ template <class... _Args> typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) { - __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); + __node_holder __h = __construct_node(std::forward<_Args>(__args)...); iterator __r = __node_insert_multi(__h.get()); __h.release(); return __r; @@ -1908,7 +1939,7 @@ typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi( const_iterator __p, _Args&&... __args) { - __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); + __node_holder __h = __construct_node(std::forward<_Args>(__args)...); iterator __r = __node_insert_multi(__p, __h.get()); __h.release(); return __r; @@ -1917,7 +1948,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi( #if _LIBCPP_STD_VER >= 17 template <class _Tp, class _Hash, class _Equal, class _Alloc> template <class _NodeHandle, class _InsertReturnType> -_LIBCPP_INLINE_VISIBILITY +_LIBCPP_HIDE_FROM_ABI _InsertReturnType __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique( _NodeHandle&& __nh) @@ -1927,12 +1958,12 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique( pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_); if (__result.second) __nh.__release_ptr(); - return _InsertReturnType{__result.first, __result.second, _VSTD::move(__nh)}; + return _InsertReturnType{__result.first, __result.second, std::move(__nh)}; } template <class _Tp, class _Hash, class _Equal, class _Alloc> template <class _NodeHandle> -_LIBCPP_INLINE_VISIBILITY +_LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique( const_iterator, _NodeHandle&& __nh) @@ -1947,7 +1978,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique( template <class _Tp, class _Hash, class _Equal, class _Alloc> template <class _NodeHandle> -_LIBCPP_INLINE_VISIBILITY +_LIBCPP_HIDE_FROM_ABI _NodeHandle __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract( key_type const& __key) @@ -1960,7 +1991,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract( template <class _Tp, class _Hash, class _Equal, class _Alloc> template <class _NodeHandle> -_LIBCPP_INLINE_VISIBILITY +_LIBCPP_HIDE_FROM_ABI _NodeHandle __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract( const_iterator __p) @@ -1971,7 +2002,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract( template <class _Tp, class _Hash, class _Equal, class _Alloc> template <class _Table> -_LIBCPP_INLINE_VISIBILITY +_LIBCPP_HIDE_FROM_ABI void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique( _Table& __source) @@ -1982,9 +2013,9 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique( __it != __source.end();) { __node_pointer __src_ptr = __it.__node_->__upcast(); - size_t __hash = hash_function()(__src_ptr->__value_); + size_t __hash = hash_function()(__src_ptr->__get_value()); __next_pointer __existing_node = - __node_insert_unique_prepare(__hash, __src_ptr->__value_); + __node_insert_unique_prepare(__hash, __src_ptr->__get_value()); auto __prev_iter = __it++; if (__existing_node == nullptr) { @@ -1997,7 +2028,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique( template <class _Tp, class _Hash, class _Equal, class _Alloc> template <class _NodeHandle> -_LIBCPP_INLINE_VISIBILITY +_LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi( _NodeHandle&& __nh) @@ -2011,7 +2042,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi( template <class _Tp, class _Hash, class _Equal, class _Alloc> template <class _NodeHandle> -_LIBCPP_INLINE_VISIBILITY +_LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi( const_iterator __hint, _NodeHandle&& __nh) @@ -2025,7 +2056,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi( template <class _Tp, class _Hash, class _Equal, class _Alloc> template <class _Table> -_LIBCPP_INLINE_VISIBILITY +_LIBCPP_HIDE_FROM_ABI void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi( _Table& __source) @@ -2036,9 +2067,9 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi( __it != __source.end();) { __node_pointer __src_ptr = __it.__node_->__upcast(); - size_t __src_hash = hash_function()(__src_ptr->__value_); + size_t __src_hash = hash_function()(__src_ptr->__get_value()); __next_pointer __pn = - __node_insert_multi_prepare(__src_hash, __src_ptr->__value_); + __node_insert_multi_prepare(__src_hash, __src_ptr->__get_value()); (void)__source.remove(__it++).release(); __src_ptr->__hash_ = __src_hash; __node_insert_multi_perform(__src_ptr, __pn); @@ -2061,7 +2092,7 @@ _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK __do_rehash<_UniqueKeys>(__n); else if (__n < __bc) { - __n = _VSTD::max<size_type> + __n = std::max<size_type> ( __n, std::__is_hash_power2(__bc) ? std::__next_hash_pow2(size_t(std::ceil(float(size()) / max_load_factor()))) : @@ -2112,8 +2143,8 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__do_rehash(size_type __nbc) if _LIBCPP_CONSTEXPR_SINCE_CXX17 (!_UniqueKeys) { for (; __np->__next_ != nullptr && - key_eq()(__cp->__upcast()->__value_, - __np->__next_->__upcast()->__value_); + key_eq()(__cp->__upcast()->__get_value(), + __np->__next_->__upcast()->__get_value()); __np = __np->__next_) ; } @@ -2147,7 +2178,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) __nd = __nd->__next_) { if ((__nd->__hash() == __hash) - && key_eq()(__nd->__upcast()->__value_, __k)) + && key_eq()(__nd->__upcast()->__get_value(), __k)) return iterator(__nd); } } @@ -2174,7 +2205,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const __nd = __nd->__next_) { if ((__nd->__hash() == __hash) - && key_eq()(__nd->__upcast()->__value_, __k)) + && key_eq()(__nd->__upcast()->__get_value(), __k)) return const_iterator(__nd); } } @@ -2192,10 +2223,20 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args) "Construct cannot be called with a hash value type"); __node_allocator& __na = __node_alloc(); __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), _VSTD::forward<_Args>(__args)...); + + // Begin the lifetime of the node itself. Note that this doesn't begin the lifetime of the value + // held inside the node, since we need to use the allocator's construct() method for that. + // + // We don't use the allocator's construct() method to construct the node itself since the + // Cpp17FooInsertable named requirements don't require the allocator's construct() method + // to work on anything other than the value_type. + std::__construct_at(std::addressof(*__h), /* next = */nullptr, /* hash = */0); + + // Now construct the value_type using the allocator's construct() method. + __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__get_value()), std::forward<_Args>(__args)...); __h.get_deleter().__value_constructed = true; - __h->__hash_ = hash_function()(__h->__value_); - __h->__next_ = nullptr; + + __h->__hash_ = hash_function()(__h->__get_value()); return __h; } @@ -2209,12 +2250,11 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash( "Construct cannot be called with a hash value type"); __node_allocator& __na = __node_alloc(); __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), - _VSTD::forward<_First>(__f), - _VSTD::forward<_Rest>(__rest)...); + std::__construct_at(std::addressof(*__h), /* next = */nullptr, /* hash = */__hash); + __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__get_value()), + std::forward<_First>(__f), + std::forward<_Rest>(__rest)...); __h.get_deleter().__value_constructed = true; - __h->__hash_ = __hash; - __h->__next_ = nullptr; return __h; } @@ -2432,11 +2472,11 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u) __bucket_list_.reset(__u.__bucket_list_.release()); __u.__bucket_list_.reset(__npp); } - _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size()); - _VSTD::__swap_allocator(__bucket_list_.get_deleter().__alloc(), + std::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size()); + std::__swap_allocator(__bucket_list_.get_deleter().__alloc(), __u.__bucket_list_.get_deleter().__alloc()); - _VSTD::__swap_allocator(__node_alloc(), __u.__node_alloc()); - _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_); + std::__swap_allocator(__node_alloc(), __u.__node_alloc()); + std::swap(__p1_.first().__next_, __u.__p1_.first().__next_); __p2_.swap(__u.__p2_); __p3_.swap(__u.__p3_); if (size() > 0) @@ -2467,7 +2507,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const } template <class _Tp, class _Hash, class _Equal, class _Alloc> -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_HIDE_FROM_ABI void swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x, __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y) |