diff options
author | danlark <danlark@yandex-team.ru> | 2022-02-10 16:46:08 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:46:08 +0300 |
commit | 3426a9bc7f169ae9da54cef557ad2a33f6e8eee0 (patch) | |
tree | 26154e1e9990f1bb4525d3e3fb5b6dac2c2c1da2 /contrib/libs/cxxsupp/libcxx/include/__hash_table | |
parent | cb68f224c46a8ee52ac3fdd2a32534b8bb8dc134 (diff) | |
download | ydb-3426a9bc7f169ae9da54cef557ad2a33f6e8eee0.tar.gz |
Restoring authorship annotation for <danlark@yandex-team.ru>. Commit 1 of 2.
Diffstat (limited to 'contrib/libs/cxxsupp/libcxx/include/__hash_table')
-rw-r--r-- | contrib/libs/cxxsupp/libcxx/include/__hash_table | 672 |
1 files changed, 336 insertions, 336 deletions
diff --git a/contrib/libs/cxxsupp/libcxx/include/__hash_table b/contrib/libs/cxxsupp/libcxx/include/__hash_table index bd97027c1a..fe9ac1c619 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__hash_table +++ b/contrib/libs/cxxsupp/libcxx/include/__hash_table @@ -1,9 +1,9 @@ // -*- C++ -*- //===----------------------------------------------------------------------===// // -// 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 +// 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 // //===----------------------------------------------------------------------===// @@ -161,7 +161,7 @@ struct __hash_key_value_types { return _VSTD::addressof(__n); } _LIBCPP_INLINE_VISIBILITY - static __container_value_type&& __move(__node_value_type& __v) { + static __container_value_type&& __move(__node_value_type& __v) { return _VSTD::move(__v); } }; @@ -861,45 +861,45 @@ public: template <class> friend class __hash_map_node_destructor; }; -#if _LIBCPP_STD_VER > 14 -template <class _NodeType, class _Alloc> -struct __generic_container_node_destructor; - -template <class _Tp, class _VoidPtr, class _Alloc> -struct __generic_container_node_destructor<__hash_node<_Tp, _VoidPtr>, _Alloc> - : __hash_node_destructor<_Alloc> -{ - using __hash_node_destructor<_Alloc>::__hash_node_destructor; -}; -#endif - -template <class _Key, class _Hash, class _Equal> -struct __enforce_unordered_container_requirements { +#if _LIBCPP_STD_VER > 14 +template <class _NodeType, class _Alloc> +struct __generic_container_node_destructor; + +template <class _Tp, class _VoidPtr, class _Alloc> +struct __generic_container_node_destructor<__hash_node<_Tp, _VoidPtr>, _Alloc> + : __hash_node_destructor<_Alloc> +{ + using __hash_node_destructor<_Alloc>::__hash_node_destructor; +}; +#endif + +template <class _Key, class _Hash, class _Equal> +struct __enforce_unordered_container_requirements { #ifndef _LIBCPP_CXX03_LANG static_assert(__check_hash_requirements<_Key, _Hash>::value, - "the specified hash does not meet the Hash requirements"); + "the specified hash does not meet the Hash requirements"); static_assert(is_copy_constructible<_Equal>::value, - "the specified comparator is required to be copy constructible"); -#endif - typedef int type; + "the specified comparator is required to be copy constructible"); +#endif + typedef int type; }; -template <class _Key, class _Hash, class _Equal> -#ifndef _LIBCPP_CXX03_LANG - _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Equal const&, _Key const&, _Key const&>::value, +template <class _Key, class _Hash, class _Equal> +#ifndef _LIBCPP_CXX03_LANG + _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Equal const&, _Key const&, _Key const&>::value, "the specified comparator type does not provide a viable const call operator") - _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Hash const&, _Key const&>::value, + _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Hash const&, _Key const&>::value, "the specified hash functor does not provide a viable const call operator") -#endif -typename __enforce_unordered_container_requirements<_Key, _Hash, _Equal>::type -__diagnose_unordered_container_requirements(int); - -// This dummy overload is used so that the compiler won't emit a spurious -// "no matching function for call to __diagnose_unordered_xxx" diagnostic -// when the overload above causes a hard error. -template <class _Key, class _Hash, class _Equal> -int __diagnose_unordered_container_requirements(void*); +#endif +typename __enforce_unordered_container_requirements<_Key, _Hash, _Equal>::type +__diagnose_unordered_container_requirements(int); +// This dummy overload is used so that the compiler won't emit a spurious +// "no matching function for call to __diagnose_unordered_xxx" diagnostic +// when the overload above causes a hard error. +template <class _Key, class _Hash, class _Equal> +int __diagnose_unordered_container_requirements(void*); + template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table { @@ -1049,26 +1049,26 @@ public: ); } -private: - _LIBCPP_INLINE_VISIBILITY - __next_pointer __node_insert_multi_prepare(size_t __cp_hash, - value_type& __cp_val); - _LIBCPP_INLINE_VISIBILITY - void __node_insert_multi_perform(__node_pointer __cp, - __next_pointer __pn) _NOEXCEPT; - - _LIBCPP_INLINE_VISIBILITY - __next_pointer __node_insert_unique_prepare(size_t __nd_hash, - value_type& __nd_val); - _LIBCPP_INLINE_VISIBILITY - void __node_insert_unique_perform(__node_pointer __ptr) _NOEXCEPT; - -public: - _LIBCPP_INLINE_VISIBILITY +private: + _LIBCPP_INLINE_VISIBILITY + __next_pointer __node_insert_multi_prepare(size_t __cp_hash, + value_type& __cp_val); + _LIBCPP_INLINE_VISIBILITY + void __node_insert_multi_perform(__node_pointer __cp, + __next_pointer __pn) _NOEXCEPT; + + _LIBCPP_INLINE_VISIBILITY + __next_pointer __node_insert_unique_prepare(size_t __nd_hash, + value_type& __nd_val); + _LIBCPP_INLINE_VISIBILITY + void __node_insert_unique_perform(__node_pointer __ptr) _NOEXCEPT; + +public: + _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __node_insert_unique(__node_pointer __nd); - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_multi(__node_pointer __nd); - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); @@ -1161,36 +1161,36 @@ public: return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x); } -#if _LIBCPP_STD_VER > 14 - template <class _NodeHandle, class _InsertReturnType> - _LIBCPP_INLINE_VISIBILITY - _InsertReturnType __node_handle_insert_unique(_NodeHandle&& __nh); - template <class _NodeHandle> - _LIBCPP_INLINE_VISIBILITY - iterator __node_handle_insert_unique(const_iterator __hint, - _NodeHandle&& __nh); - template <class _Table> - _LIBCPP_INLINE_VISIBILITY - void __node_handle_merge_unique(_Table& __source); - - template <class _NodeHandle> - _LIBCPP_INLINE_VISIBILITY - iterator __node_handle_insert_multi(_NodeHandle&& __nh); - template <class _NodeHandle> - _LIBCPP_INLINE_VISIBILITY - iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh); - template <class _Table> - _LIBCPP_INLINE_VISIBILITY - void __node_handle_merge_multi(_Table& __source); - - template <class _NodeHandle> - _LIBCPP_INLINE_VISIBILITY - _NodeHandle __node_handle_extract(key_type const& __key); - template <class _NodeHandle> - _LIBCPP_INLINE_VISIBILITY - _NodeHandle __node_handle_extract(const_iterator __it); -#endif - +#if _LIBCPP_STD_VER > 14 + template <class _NodeHandle, class _InsertReturnType> + _LIBCPP_INLINE_VISIBILITY + _InsertReturnType __node_handle_insert_unique(_NodeHandle&& __nh); + template <class _NodeHandle> + _LIBCPP_INLINE_VISIBILITY + iterator __node_handle_insert_unique(const_iterator __hint, + _NodeHandle&& __nh); + template <class _Table> + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_unique(_Table& __source); + + template <class _NodeHandle> + _LIBCPP_INLINE_VISIBILITY + iterator __node_handle_insert_multi(_NodeHandle&& __nh); + template <class _NodeHandle> + _LIBCPP_INLINE_VISIBILITY + iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh); + template <class _Table> + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_multi(_Table& __source); + + template <class _NodeHandle> + _LIBCPP_INLINE_VISIBILITY + _NodeHandle __node_handle_extract(key_type const& __key); + template <class _NodeHandle> + _LIBCPP_INLINE_VISIBILITY + _NodeHandle __node_handle_extract(const_iterator __it); +#endif + void clear() _NOEXCEPT; void rehash(size_type __n); _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n) @@ -1839,111 +1839,111 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT } } - -// Prepare the container for an insertion of the value __value with the hash -// __hash. This does a lookup into the container to see if __value is already -// present, and performs a rehash if necessary. Returns a pointer to the -// existing element if it exists, otherwise nullptr. -// -// Note that this function does forward exceptions if key_eq() throws, and never -// mutates __value or actually inserts into the map. + +// Prepare the container for an insertion of the value __value with the hash +// __hash. This does a lookup into the container to see if __value is already +// present, and performs a rehash if necessary. Returns a pointer to the +// existing element if it exists, otherwise nullptr. +// +// 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 -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) +_LIBCPP_INLINE_VISIBILITY +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) { size_type __bc = bucket_count(); - + if (__bc != 0) { - size_t __chash = __constrain_hash(__hash, __bc); - __next_pointer __ndptr = __bucket_list_[__chash]; + size_t __chash = __constrain_hash(__hash, __bc); + __next_pointer __ndptr = __bucket_list_[__chash]; if (__ndptr != nullptr) { for (__ndptr = __ndptr->__next_; __ndptr != nullptr && __constrain_hash(__ndptr->__hash(), __bc) == __chash; __ndptr = __ndptr->__next_) { - if (key_eq()(__ndptr->__upcast()->__value_, __value)) - return __ndptr; + if (key_eq()(__ndptr->__upcast()->__value_, __value)) + return __ndptr; } } } - if (size()+1 > __bc * max_load_factor() || __bc == 0) - { - rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), - size_type(ceil(float(size() + 1) / max_load_factor())))); - } - return nullptr; -} - -// Insert the node __nd into the container by pushing it into the right bucket, -// and updating size(). Assumes that __nd->__hash is up-to-date, and that -// 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 -void -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_perform( - __node_pointer __nd) _NOEXCEPT -{ - size_type __bc = bucket_count(); - size_t __chash = __constrain_hash(__nd->__hash(), __bc); - // insert_after __bucket_list_[__chash], or __first_node if bucket is null - __next_pointer __pn = __bucket_list_[__chash]; - if (__pn == nullptr) - { - __pn =__p1_.first().__ptr(); - __nd->__next_ = __pn->__next_; - __pn->__next_ = __nd->__ptr(); - // fix up __bucket_list_ - __bucket_list_[__chash] = __pn; - if (__nd->__next_ != nullptr) - __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr(); - } - else - { - __nd->__next_ = __pn->__next_; - __pn->__next_ = __nd->__ptr(); - } - ++size(); -} - -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_); - __next_pointer __existing_node = - __node_insert_unique_prepare(__nd->__hash(), __nd->__value_); - - // Insert the node, unless it already exists in the container. - bool __inserted = false; - if (__existing_node == nullptr) - { - __node_insert_unique_perform(__nd); - __existing_node = __nd->__ptr(); + if (size()+1 > __bc * max_load_factor() || __bc == 0) + { + rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), + size_type(ceil(float(size() + 1) / max_load_factor())))); + } + return nullptr; +} + +// Insert the node __nd into the container by pushing it into the right bucket, +// and updating size(). Assumes that __nd->__hash is up-to-date, and that +// 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 +void +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_perform( + __node_pointer __nd) _NOEXCEPT +{ + size_type __bc = bucket_count(); + size_t __chash = __constrain_hash(__nd->__hash(), __bc); + // insert_after __bucket_list_[__chash], or __first_node if bucket is null + __next_pointer __pn = __bucket_list_[__chash]; + if (__pn == nullptr) + { + __pn =__p1_.first().__ptr(); + __nd->__next_ = __pn->__next_; + __pn->__next_ = __nd->__ptr(); + // fix up __bucket_list_ + __bucket_list_[__chash] = __pn; + if (__nd->__next_ != nullptr) + __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr(); + } + else + { + __nd->__next_ = __pn->__next_; + __pn->__next_ = __nd->__ptr(); + } + ++size(); +} + +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_); + __next_pointer __existing_node = + __node_insert_unique_prepare(__nd->__hash(), __nd->__value_); + + // Insert the node, unless it already exists in the container. + bool __inserted = false; + if (__existing_node == nullptr) + { + __node_insert_unique_perform(__nd); + __existing_node = __nd->__ptr(); __inserted = true; } #if _LIBCPP_DEBUG_LEVEL == 2 - return pair<iterator, bool>(iterator(__existing_node, this), __inserted); + return pair<iterator, bool>(iterator(__existing_node, this), __inserted); #else - return pair<iterator, bool>(iterator(__existing_node), __inserted); + return pair<iterator, bool>(iterator(__existing_node), __inserted); #endif } -// Prepare the container for an insertion of the value __cp_val with the hash -// __cp_hash. This does a lookup into the container to see if __cp_value is -// already present, and performs a rehash if necessary. Returns a pointer to the +// Prepare the container for an insertion of the value __cp_val with the hash +// __cp_hash. This does a lookup into the container to see if __cp_value is +// already present, and performs a rehash if necessary. Returns a pointer to the // last occurrence of __cp_val in the map. -// -// Note that this function does forward exceptions if key_eq() throws, and never -// mutates __value or actually inserts into the map. +// +// 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> -typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare( - size_t __cp_hash, value_type& __cp_val) +typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare( + size_t __cp_hash, value_type& __cp_val) { size_type __bc = bucket_count(); if (size()+1 > __bc * max_load_factor() || __bc == 0) @@ -1952,9 +1952,9 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare( size_type(ceil(float(size() + 1) / max_load_factor())))); __bc = bucket_count(); } - size_t __chash = __constrain_hash(__cp_hash, __bc); + size_t __chash = __constrain_hash(__cp_hash, __bc); __next_pointer __pn = __bucket_list_[__chash]; - if (__pn != nullptr) + if (__pn != nullptr) { for (bool __found = false; __pn->__next_ != nullptr && __constrain_hash(__pn->__next_->__hash(), __bc) == __chash; @@ -1965,8 +1965,8 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare( // true true loop // false true set __found to true // true false break - if (__found != (__pn->__next_->__hash() == __cp_hash && - key_eq()(__pn->__next_->__upcast()->__value_, __cp_val))) + if (__found != (__pn->__next_->__hash() == __cp_hash && + key_eq()(__pn->__next_->__upcast()->__value_, __cp_val))) { if (!__found) __found = true; @@ -1974,38 +1974,38 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare( break; } } - } - return __pn; -} - -// Insert the node __cp into the container after __pn (which is the last node in -// the bucket that compares equal to __cp). Rehashing, and checking for -// uniqueness has already been performed (in __node_insert_multi_prepare), so -// all we need to do is update the bucket and size(). Assumes that __cp->__hash -// is up-to-date. -template <class _Tp, class _Hash, class _Equal, class _Alloc> -void -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_perform( - __node_pointer __cp, __next_pointer __pn) _NOEXCEPT -{ - size_type __bc = bucket_count(); - size_t __chash = __constrain_hash(__cp->__hash_, __bc); - if (__pn == nullptr) - { - __pn =__p1_.first().__ptr(); - __cp->__next_ = __pn->__next_; - __pn->__next_ = __cp->__ptr(); - // fix up __bucket_list_ - __bucket_list_[__chash] = __pn; - if (__cp->__next_ != nullptr) - __bucket_list_[__constrain_hash(__cp->__next_->__hash(), __bc)] - = __cp->__ptr(); - } - else - { + } + return __pn; +} + +// Insert the node __cp into the container after __pn (which is the last node in +// the bucket that compares equal to __cp). Rehashing, and checking for +// uniqueness has already been performed (in __node_insert_multi_prepare), so +// all we need to do is update the bucket and size(). Assumes that __cp->__hash +// is up-to-date. +template <class _Tp, class _Hash, class _Equal, class _Alloc> +void +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_perform( + __node_pointer __cp, __next_pointer __pn) _NOEXCEPT +{ + size_type __bc = bucket_count(); + size_t __chash = __constrain_hash(__cp->__hash_, __bc); + if (__pn == nullptr) + { + __pn =__p1_.first().__ptr(); __cp->__next_ = __pn->__next_; __pn->__next_ = __cp->__ptr(); + // fix up __bucket_list_ + __bucket_list_[__chash] = __pn; if (__cp->__next_ != nullptr) + __bucket_list_[__constrain_hash(__cp->__next_->__hash(), __bc)] + = __cp->__ptr(); + } + else + { + __cp->__next_ = __pn->__next_; + __pn->__next_ = __cp->__ptr(); + if (__cp->__next_ != nullptr) { size_t __nhash = __constrain_hash(__cp->__next_->__hash(), __bc); if (__nhash != __chash) @@ -2013,17 +2013,17 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_perform( } } ++size(); -} - - -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_); - __node_insert_multi_perform(__cp, __pn); - +} + + +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_); + __node_insert_multi_perform(__cp, __pn); + #if _LIBCPP_DEBUG_LEVEL == 2 return iterator(__cp->__ptr(), this); #else @@ -2176,140 +2176,140 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi( return __r; } -#if _LIBCPP_STD_VER > 14 +#if _LIBCPP_STD_VER > 14 template <class _Tp, class _Hash, class _Equal, class _Alloc> -template <class _NodeHandle, class _InsertReturnType> -_LIBCPP_INLINE_VISIBILITY -_InsertReturnType -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique( - _NodeHandle&& __nh) -{ - if (__nh.empty()) - return _InsertReturnType{end(), false, _NodeHandle()}; - pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_); - if (__result.second) +template <class _NodeHandle, class _InsertReturnType> +_LIBCPP_INLINE_VISIBILITY +_InsertReturnType +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique( + _NodeHandle&& __nh) +{ + if (__nh.empty()) + return _InsertReturnType{end(), false, _NodeHandle()}; + pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_); + if (__result.second) __nh.__release_ptr(); - return _InsertReturnType{__result.first, __result.second, _VSTD::move(__nh)}; -} - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -template <class _NodeHandle> -_LIBCPP_INLINE_VISIBILITY -typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique( - const_iterator, _NodeHandle&& __nh) -{ - if (__nh.empty()) - return end(); - pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_); - if (__result.second) + return _InsertReturnType{__result.first, __result.second, _VSTD::move(__nh)}; +} + +template <class _Tp, class _Hash, class _Equal, class _Alloc> +template <class _NodeHandle> +_LIBCPP_INLINE_VISIBILITY +typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique( + const_iterator, _NodeHandle&& __nh) +{ + if (__nh.empty()) + return end(); + pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_); + if (__result.second) __nh.__release_ptr(); - return __result.first; -} - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -template <class _NodeHandle> -_LIBCPP_INLINE_VISIBILITY -_NodeHandle -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract( - key_type const& __key) -{ - iterator __i = find(__key); - if (__i == end()) - return _NodeHandle(); - return __node_handle_extract<_NodeHandle>(__i); -} - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -template <class _NodeHandle> -_LIBCPP_INLINE_VISIBILITY -_NodeHandle -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract( - const_iterator __p) -{ - allocator_type __alloc(__node_alloc()); - return _NodeHandle(remove(__p).release(), __alloc); -} - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -template <class _Table> -_LIBCPP_INLINE_VISIBILITY + return __result.first; +} + +template <class _Tp, class _Hash, class _Equal, class _Alloc> +template <class _NodeHandle> +_LIBCPP_INLINE_VISIBILITY +_NodeHandle +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract( + key_type const& __key) +{ + iterator __i = find(__key); + if (__i == end()) + return _NodeHandle(); + return __node_handle_extract<_NodeHandle>(__i); +} + +template <class _Tp, class _Hash, class _Equal, class _Alloc> +template <class _NodeHandle> +_LIBCPP_INLINE_VISIBILITY +_NodeHandle +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract( + const_iterator __p) +{ + allocator_type __alloc(__node_alloc()); + return _NodeHandle(remove(__p).release(), __alloc); +} + +template <class _Tp, class _Hash, class _Equal, class _Alloc> +template <class _Table> +_LIBCPP_INLINE_VISIBILITY void -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique( - _Table& __source) -{ - static_assert(is_same<__node, typename _Table::__node>::value, ""); - - for (typename _Table::iterator __it = __source.begin(); - __it != __source.end();) - { - __node_pointer __src_ptr = __it.__node_->__upcast(); - size_t __hash = hash_function()(__src_ptr->__value_); - __next_pointer __existing_node = - __node_insert_unique_prepare(__hash, __src_ptr->__value_); - auto __prev_iter = __it++; - if (__existing_node == nullptr) - { - (void)__source.remove(__prev_iter).release(); - __src_ptr->__hash_ = __hash; - __node_insert_unique_perform(__src_ptr); - } - } -} - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -template <class _NodeHandle> -_LIBCPP_INLINE_VISIBILITY -typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi( - _NodeHandle&& __nh) -{ - if (__nh.empty()) - return end(); - iterator __result = __node_insert_multi(__nh.__ptr_); +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique( + _Table& __source) +{ + static_assert(is_same<__node, typename _Table::__node>::value, ""); + + for (typename _Table::iterator __it = __source.begin(); + __it != __source.end();) + { + __node_pointer __src_ptr = __it.__node_->__upcast(); + size_t __hash = hash_function()(__src_ptr->__value_); + __next_pointer __existing_node = + __node_insert_unique_prepare(__hash, __src_ptr->__value_); + auto __prev_iter = __it++; + if (__existing_node == nullptr) + { + (void)__source.remove(__prev_iter).release(); + __src_ptr->__hash_ = __hash; + __node_insert_unique_perform(__src_ptr); + } + } +} + +template <class _Tp, class _Hash, class _Equal, class _Alloc> +template <class _NodeHandle> +_LIBCPP_INLINE_VISIBILITY +typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi( + _NodeHandle&& __nh) +{ + if (__nh.empty()) + return end(); + iterator __result = __node_insert_multi(__nh.__ptr_); __nh.__release_ptr(); - return __result; -} - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -template <class _NodeHandle> -_LIBCPP_INLINE_VISIBILITY -typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi( - const_iterator __hint, _NodeHandle&& __nh) -{ - if (__nh.empty()) - return end(); - iterator __result = __node_insert_multi(__hint, __nh.__ptr_); + return __result; +} + +template <class _Tp, class _Hash, class _Equal, class _Alloc> +template <class _NodeHandle> +_LIBCPP_INLINE_VISIBILITY +typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi( + const_iterator __hint, _NodeHandle&& __nh) +{ + if (__nh.empty()) + return end(); + iterator __result = __node_insert_multi(__hint, __nh.__ptr_); __nh.__release_ptr(); - return __result; -} - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -template <class _Table> -_LIBCPP_INLINE_VISIBILITY -void -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi( - _Table& __source) -{ - static_assert(is_same<typename _Table::__node, __node>::value, ""); - - for (typename _Table::iterator __it = __source.begin(); - __it != __source.end();) - { - __node_pointer __src_ptr = __it.__node_->__upcast(); - size_t __src_hash = hash_function()(__src_ptr->__value_); - __next_pointer __pn = - __node_insert_multi_prepare(__src_hash, __src_ptr->__value_); - (void)__source.remove(__it++).release(); - __src_ptr->__hash_ = __src_hash; - __node_insert_multi_perform(__src_ptr, __pn); - } -} + return __result; +} + +template <class _Tp, class _Hash, class _Equal, class _Alloc> +template <class _Table> +_LIBCPP_INLINE_VISIBILITY +void +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi( + _Table& __source) +{ + static_assert(is_same<typename _Table::__node, __node>::value, ""); + + for (typename _Table::iterator __it = __source.begin(); + __it != __source.end();) + { + __node_pointer __src_ptr = __it.__node_->__upcast(); + size_t __src_hash = hash_function()(__src_ptr->__value_); + __next_pointer __pn = + __node_insert_multi_prepare(__src_hash, __src_ptr->__value_); + (void)__source.remove(__it++).release(); + __src_ptr->__hash_ = __src_hash; + __node_insert_multi_perform(__src_ptr, __pn); + } +} #endif // _LIBCPP_STD_VER > 14 - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -void + +template <class _Tp, class _Hash, class _Equal, class _Alloc> +void __hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n) _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK { |