aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/libs/cxxsupp/libcxx/include/__hash_table
diff options
context:
space:
mode:
authordanlark <danlark@yandex-team.ru>2022-02-10 16:46:08 +0300
committerDaniil Cherednik <dcherednik@yandex-team.ru>2022-02-10 16:46:08 +0300
commit3426a9bc7f169ae9da54cef557ad2a33f6e8eee0 (patch)
tree26154e1e9990f1bb4525d3e3fb5b6dac2c2c1da2 /contrib/libs/cxxsupp/libcxx/include/__hash_table
parentcb68f224c46a8ee52ac3fdd2a32534b8bb8dc134 (diff)
downloadydb-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_table672
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
{