From 1b6f0476837205932613ddb2b3429a55c26c409d Mon Sep 17 00:00:00 2001 From: =?utf8?q?Fran=C3=A7ois=20Dumont?= Date: Sun, 4 Oct 2020 18:06:11 +0200 Subject: [PATCH] libstdc++: Refactor _Hashtable to prepare for custom pointers Limit usage of node pointers in _Hashtable implementation details so that when we move to allocator custom pointer type we do not need to add an _Alloc template parameter everywhere which would impact abi. This is done by reviewing node type definition. It is now based on new basic types which are not pointer dependant. The _Hashtable helper types are now using those new node base types and do not receive node pointers. libstdc++-v3/ChangeLog * include/bits/hashtable_policy.h (_Hash_node_value_base<>): Remove _Hash_node_base inheritance. (_Hash_node_code_cache): New. (_Hash_node_value): New. (_Hash_node<>): Inherits _Hash_node_base<> and _Hash_node_value<>. (_Map_base<>::__node_type): Remove. (_Map_base<>::iterator): Remove. (_Insert_base<>::__hash_cached): New. (_Insert_base<>::__constant_iterators): New. (_Insert_base<>::__hashtable_alloc): New. (_Insert_base<>::__node_type): Remove. (_Insert_base<>::__node_ptr): New. (_Hash_code_base<>): Remove specializations. (_Hash_code_base<>::__node_type): Remove. (_Hash_code_base<>::_M_bucket_index(const __node_type*, size_t)): Replace by... (_Hash_code_base<>::_M_bucket_index(const _Hash_node_value<>&, size_t)): ...this. (_Hash_code_base<>::_M_store_code(__node_type*, __hash_code)): Replace by... (_Hash_code_base<>::_M_store_code(_Hash_node_code_cache<>&, __hash_code)): ...this. (_Hash_code_base<>::_M_copy_code(__node_type*, const __node_type*)): Replace by... (_Hash_code_base<>::_M_copy_code(_Hash_node_code_cache<>&, const _Hash_node_code_base<>&)): ...this. (_Hashtable_base<>::__constant_iterators): Remove. (_Hashtable_base<>::__unique_keys): Remove. (_Hashtable_base<>::__node_type): Remove. (_Hashtable_base<>::iterator): Remove. (_Hashtable_base<>::const_iterator): Remove. (_Hashtable_base<>::local_iterator): Remove. (_Hashtable_base<>::const_local_iterator): Remove. (_Hashtable_base<>::__ireturn_type): Remove. (_Hashtable_base<>::_Equal_hash_code<>::_S_equals): Replace by... (_Hashtable_base<>::_S_equals(__hash_code, const _Hash_node_code_hash<>&)): ...this. (_Hashtable_base<>::_Equal_hash_code<>::_S_node_equals): Replace by... (_Hashtable_base<>::_S_node_equals(__hash_code, const _Hash_node_code_hash<>&)): ...this. (_Hashtable_base<>::_Equal_hash_code<>): Remove. (_Hashtable_base<>::_M_equals): Adapt. (_Hashtable_baxe<>::_M_node_equals): Adapt. (_Equality<>::_M_equal): Adapt. (_Hashtable_alloc<>::__node_ptr): New. (_Hashtable_alloc<>::__bucket_type): Rename into... (_Hashtable_alloc<>::__node_base_ptr): ...this. (_Hashtable_alloc<>::__bucket_alloc_type): Rename into... (_Hashtable_alloc<>::__buckets_alloc_type): ...this. (_Hashtable_alloc<>::__bucket_alloc_traits): Rename into... (_Hashtable_alloc<>::__buckets_alloc_traits): ...this. (_Hashtable_alloc<>::__buckets_ptr): New. (_Hashtable_alloc<>::_M_allocate_node): Adapt. (_Hashtable_alloc<>::_M_deallocate_node): Adapt. (_Hashtable_alloc<>::_M_deallocate_node_ptr): Adapt. (_Hashtable_alloc<>::_M_deallocate_nodes): Adapt. (_Hashtable_alloc<>::_M_allocate_buckets): Adapt. (_Hashtable_alloc<>::_M_deallocate_buckets): Adapt. * include/bits/hashtable.h (_Hashtable<>): Adapt. --- libstdc++-v3/include/bits/hashtable.h | 251 ++++++----- libstdc++-v3/include/bits/hashtable_policy.h | 426 ++++++++----------- 2 files changed, 309 insertions(+), 368 deletions(-) diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 07a4abe5c33..6c6c5edde0b 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -101,7 +101,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * - size_type _M_bucket_count * - size_type _M_element_count * - * with _Bucket being _Hash_node* and _Hash_node containing: + * with _Bucket being _Hash_node_base* and _Hash_node containing: * * - _Hash_node* _M_next * - Tp _M_value @@ -194,17 +194,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION using __traits_type = _Traits; using __hash_cached = typename __traits_type::__hash_cached; + using __constant_iterators = typename __traits_type::__constant_iterators; using __node_type = __detail::_Hash_node<_Value, __hash_cached::value>; using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>; using __hashtable_alloc = __detail::_Hashtable_alloc<__node_alloc_type>; + using __node_value_type = + __detail::_Hash_node_value<_Value, __hash_cached::value>; + using __node_ptr = typename __hashtable_alloc::__node_ptr; using __value_alloc_traits = typename __hashtable_alloc::__value_alloc_traits; using __node_alloc_traits = typename __hashtable_alloc::__node_alloc_traits; using __node_base = typename __hashtable_alloc::__node_base; - using __bucket_type = typename __hashtable_alloc::__bucket_type; + using __node_base_ptr = typename __hashtable_alloc::__node_base_ptr; + using __buckets_ptr = typename __hashtable_alloc::__buckets_ptr; + + using __insert_base = __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, + _Equal, _Hash, + _RangeHash, _Unused, + _RehashPolicy, _Traits>; public: typedef _Key key_type; @@ -219,11 +229,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typedef value_type& reference; typedef const value_type& const_reference; + using iterator = typename __insert_base::iterator; + + using const_iterator = typename __insert_base::const_iterator; + + using local_iterator = __detail::_Local_iterator; + + using const_local_iterator = __detail::_Local_const_iterator< + key_type, _Value, + _ExtractKey, _Hash, _RangeHash, _Unused, + __constant_iterators::value, __hash_cached::value>; + private: using __rehash_type = _RehashPolicy; using __rehash_state = typename __rehash_type::_State; - using __constant_iterators = typename __traits_type::__constant_iterators; using __unique_keys = typename __traits_type::__unique_keys; using __hashtable_base = __detail:: @@ -232,7 +255,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION using __hash_code_base = typename __hashtable_base::__hash_code_base; using __hash_code = typename __hashtable_base::__hash_code; - using __ireturn_type = typename __hashtable_base::__ireturn_type; + using __ireturn_type = typename __insert_base::__ireturn_type; using __map_base = __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, @@ -256,7 +279,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION struct _Scoped_node { // Take ownership of a node with a constructed element. - _Scoped_node(__node_type* __n, __hashtable_alloc* __h) + _Scoped_node(__node_ptr __n, __hashtable_alloc* __h) : _M_h(__h), _M_node(__n) { } // Allocate a node and construct an element within it. @@ -273,7 +296,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Scoped_node& operator=(const _Scoped_node&) = delete; __hashtable_alloc* _M_h; - __node_type* _M_node; + __node_ptr _M_node; }; template @@ -293,8 +316,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Getting a bucket index from a node shall not throw because it is used // in methods (erase, swap...) that shall not throw. static_assert(noexcept(declval() - ._M_bucket_index((const __node_type*)nullptr, - (std::size_t)0)), + ._M_bucket_index(declval(), + (std::size_t)0)), "Cache the hash code or qualify your functors involved" " in hash code and bucket index computation with noexcept"); @@ -345,20 +368,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION using size_type = typename __hashtable_base::size_type; using difference_type = typename __hashtable_base::difference_type; - using iterator = typename __hashtable_base::iterator; - using const_iterator = typename __hashtable_base::const_iterator; - - using local_iterator = typename __hashtable_base::local_iterator; - using const_local_iterator = typename __hashtable_base:: - const_local_iterator; - #if __cplusplus > 201402L using node_type = _Node_handle<_Key, _Value, __node_alloc_type>; using insert_return_type = _Node_insert_return; #endif private: - __bucket_type* _M_buckets = &_M_single_bucket; + __buckets_ptr _M_buckets = &_M_single_bucket; size_type _M_bucket_count = 1; __node_base _M_before_begin; size_type _M_element_count = 0; @@ -370,24 +386,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // qualified. // Note that we can't leave hashtable with 0 bucket without adding // numerous checks in the code to avoid 0 modulus. - __bucket_type _M_single_bucket = nullptr; + __node_base_ptr _M_single_bucket = nullptr; void _M_update_bbegin() { if (_M_begin()) - _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; + _M_buckets[_M_bucket_index(*_M_begin())] = &_M_before_begin; } void - _M_update_bbegin(__node_type* __n) + _M_update_bbegin(__node_ptr __n) { _M_before_begin._M_nxt = __n; _M_update_bbegin(); } bool - _M_uses_single_bucket(__bucket_type* __bkts) const + _M_uses_single_bucket(__buckets_ptr __bkts) const { return __builtin_expect(__bkts == &_M_single_bucket, false); } bool @@ -397,7 +413,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __hashtable_alloc& _M_base_alloc() { return *this; } - __bucket_type* + __buckets_ptr _M_allocate_buckets(size_type __bkt_count) { if (__builtin_expect(__bkt_count == 1, false)) @@ -410,7 +426,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } void - _M_deallocate_buckets(__bucket_type* __bkts, size_type __bkt_count) + _M_deallocate_buckets(__buckets_ptr __bkts, size_type __bkt_count) { if (_M_uses_single_bucket(__bkts)) return; @@ -424,12 +440,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Gets bucket begin, deals with the fact that non-empty buckets contain // their before begin node. - __node_type* + __node_ptr _M_bucket_begin(size_type __bkt) const; - __node_type* + __node_ptr _M_begin() const - { return static_cast<__node_type*>(_M_before_begin._M_nxt); } + { return static_cast<__node_ptr>(_M_before_begin._M_nxt); } // Assign *this using another _Hashtable instance. Whether elements // are copied or moved depends on the _Ht reference. @@ -711,7 +727,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION private: // Bucket index computation helpers. size_type - _M_bucket_index(__node_type* __n) const noexcept + _M_bucket_index(const __node_value_type& __n) const noexcept { return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); } size_type @@ -720,44 +736,44 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Find and insert helper functions and types // Find the node before the one matching the criteria. - __node_base* + __node_base_ptr _M_find_before_node(size_type, const key_type&, __hash_code) const; - __node_type* + __node_ptr _M_find_node(size_type __bkt, const key_type& __key, __hash_code __c) const { - __node_base* __before_n = _M_find_before_node(__bkt, __key, __c); + __node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c); if (__before_n) - return static_cast<__node_type*>(__before_n->_M_nxt); + return static_cast<__node_ptr>(__before_n->_M_nxt); return nullptr; } // Insert a node at the beginning of a bucket. void - _M_insert_bucket_begin(size_type, __node_type*); + _M_insert_bucket_begin(size_type, __node_ptr); // Remove the bucket first node void - _M_remove_bucket_begin(size_type __bkt, __node_type* __next_n, + _M_remove_bucket_begin(size_type __bkt, __node_ptr __next_n, size_type __next_bkt); // Get the node before __n in the bucket __bkt - __node_base* - _M_get_previous_node(size_type __bkt, __node_base* __n); + __node_base_ptr + _M_get_previous_node(size_type __bkt, __node_ptr __n); // Insert node __n with hash code __code, in bucket __bkt if no // rehash (assumes no element with same key already present). // Takes ownership of __n if insertion succeeds, throws otherwise. iterator _M_insert_unique_node(size_type __bkt, __hash_code, - __node_type* __n, size_type __n_elt = 1); + __node_ptr __n, size_type __n_elt = 1); // Insert node __n with key __k and hash code __code. // Takes ownership of __n if insertion succeeds, throws otherwise. iterator - _M_insert_multi_node(__node_type* __hint, - __hash_code __code, __node_type* __n); + _M_insert_multi_node(__node_ptr __hint, + __hash_code __code, __node_ptr __n); template std::pair @@ -814,7 +830,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_erase(false_type __uks, const key_type&); iterator - _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n); + _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n); public: // Emplace @@ -874,7 +890,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION const key_type& __k = __nh._M_key(); __hash_code __code = this->_M_hash_code(__k); size_type __bkt = _M_bucket_index(__code); - if (__node_type* __n = _M_find_node(__bkt, __k, __code)) + if (__node_ptr __n = _M_find_node(__bkt, __k, __code)) { __ret.node = std::move(__nh); __ret.position = iterator(__n); @@ -910,15 +926,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION private: node_type - _M_extract_node(size_t __bkt, __node_base* __prev_n) + _M_extract_node(size_t __bkt, __node_base_ptr __prev_n) { - __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); + __node_ptr __n = static_cast<__node_ptr>(__prev_n->_M_nxt); if (__prev_n == _M_buckets[__bkt]) _M_remove_bucket_begin(__bkt, __n->_M_next(), - __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0); + __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0); else if (__n->_M_nxt) { - size_type __next_bkt = _M_bucket_index(__n->_M_next()); + size_type __next_bkt = _M_bucket_index(*__n->_M_next()); if (__next_bkt != __bkt) _M_buckets[__next_bkt] = __prev_n; } @@ -934,7 +950,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION node_type extract(const_iterator __pos) { - size_t __bkt = _M_bucket_index(__pos._M_cur); + size_t __bkt = _M_bucket_index(*__pos._M_cur); return _M_extract_node(__bkt, _M_get_previous_node(__bkt, __pos._M_cur)); } @@ -946,7 +962,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION node_type __nh; __hash_code __code = this->_M_hash_code(__k); std::size_t __bkt = _M_bucket_index(__code); - if (__node_base* __prev_node = _M_find_before_node(__bkt, __k, __code)) + if (__node_base_ptr __prev_node = _M_find_before_node(__bkt, __k, __code)) __nh = _M_extract_node(__bkt, __prev_node); return __nh; } @@ -1016,10 +1032,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_bucket_begin(size_type __bkt) const - -> __node_type* + -> __node_ptr { - __node_base* __n = _M_buckets[__bkt]; - return __n ? static_cast<__node_type*>(__n->_M_nxt) : nullptr; + __node_base_ptr __n = _M_buckets[__bkt]; + return __n ? static_cast<__node_ptr>(__n->_M_nxt) : nullptr; } template:: _M_assign_elements(_Ht&& __ht) { - __bucket_type* __former_buckets = nullptr; + __buckets_ptr __former_buckets = nullptr; std::size_t __former_bucket_count = _M_bucket_count; const __rehash_state& __former_state = _M_rehash_policy._M_state(); @@ -1160,7 +1176,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } else __builtin_memset(_M_buckets, 0, - _M_bucket_count * sizeof(__bucket_type)); + _M_bucket_count * sizeof(__node_base_ptr)); __try { @@ -1184,7 +1200,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_bucket_count = __former_bucket_count; } __builtin_memset(_M_buckets, 0, - _M_bucket_count * sizeof(__bucket_type)); + _M_bucket_count * sizeof(__node_base_ptr)); __throw_exception_again; } } @@ -1199,7 +1215,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_assign(_Ht&& __ht, const _NodeGenerator& __node_gen) { - __bucket_type* __buckets = nullptr; + __buckets_ptr __buckets = nullptr; if (!_M_buckets) _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count); @@ -1210,20 +1226,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // First deal with the special first node pointed to by // _M_before_begin. - __node_type* __ht_n = __ht._M_begin(); - __node_type* __this_n + __node_ptr __ht_n = __ht._M_begin(); + __node_ptr __this_n = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v())); - this->_M_copy_code(__this_n, __ht_n); + this->_M_copy_code(*__this_n, *__ht_n); _M_update_bbegin(__this_n); // Then deal with other nodes. - __node_base* __prev_n = __this_n; + __node_ptr __prev_n = __this_n; for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next()) { __this_n = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v())); __prev_n->_M_nxt = __this_n; - this->_M_copy_code(__this_n, __ht_n); - size_type __bkt = _M_bucket_index(__this_n); + this->_M_copy_code(*__this_n, *__ht_n); + size_type __bkt = _M_bucket_index(*__this_n); if (!_M_buckets[__bkt]) _M_buckets[__bkt] = __prev_n; __prev_n = __this_n; @@ -1538,7 +1554,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // find any new equivalent value. size_type __result = 1; for (auto __ref = __it++; - __it._M_cur && this->_M_node_equals(__ref._M_cur, __it._M_cur); + __it._M_cur && this->_M_node_equals(*__ref._M_cur, *__it._M_cur); ++__it) ++__result; @@ -1566,7 +1582,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // All equivalent values are next to each other, if we find a // non-equivalent value after an equivalent one it means that we won't // find any new equivalent value. - while (__ite._M_cur && this->_M_node_equals(__beg._M_cur, __ite._M_cur)) + while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur)) ++__ite; return { __beg, __ite }; @@ -1593,7 +1609,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // All equivalent values are next to each other, if we find a // non-equivalent value after an equivalent one it means that we won't // find any new equivalent value. - while (__ite._M_cur && this->_M_node_equals(__beg._M_cur, __ite._M_cur)) + while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur)) ++__ite; return { __beg, __ite }; @@ -1610,19 +1626,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_find_before_node(size_type __bkt, const key_type& __k, __hash_code __code) const - -> __node_base* + -> __node_base_ptr { - __node_base* __prev_p = _M_buckets[__bkt]; + __node_base_ptr __prev_p = _M_buckets[__bkt]; if (!__prev_p) return nullptr; - for (__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);; + for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);; __p = __p->_M_next()) { - if (this->_M_equals(__k, __code, __p)) + if (this->_M_equals(__k, __code, *__p)) return __prev_p; - if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __bkt) + if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt) break; __prev_p = __p; } @@ -1637,7 +1653,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_insert_bucket_begin(size_type __bkt, __node_type* __node) + _M_insert_bucket_begin(size_type __bkt, __node_ptr __node) { if (_M_buckets[__bkt]) { @@ -1657,7 +1673,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__node->_M_nxt) // We must update former begin bucket that is pointing to // _M_before_begin. - _M_buckets[_M_bucket_index(__node->_M_next())] = __node; + _M_buckets[_M_bucket_index(*__node->_M_next())] = __node; _M_buckets[__bkt] = &_M_before_begin; } @@ -1670,7 +1686,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_remove_bucket_begin(size_type __bkt, __node_type* __next, + _M_remove_bucket_begin(size_type __bkt, __node_ptr __next, size_type __next_bkt) { if (!__next || __next_bkt != __bkt) @@ -1694,10 +1710,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_get_previous_node(size_type __bkt, __node_base* __n) - -> __node_base* + _M_get_previous_node(size_type __bkt, __node_ptr __n) + -> __node_base_ptr { - __node_base* __prev_n = _M_buckets[__bkt]; + __node_base_ptr __prev_n = _M_buckets[__bkt]; while (__prev_n->_M_nxt != __n) __prev_n = __prev_n->_M_nxt; return __prev_n; @@ -1719,7 +1735,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION const key_type& __k = _ExtractKey{}(__node._M_node->_M_v()); __hash_code __code = this->_M_hash_code(__k); size_type __bkt = _M_bucket_index(__code); - if (__node_type* __p = _M_find_node(__bkt, __k, __code)) + if (__node_ptr __p = _M_find_node(__bkt, __k, __code)) // There is already an equivalent node, no insertion return std::make_pair(iterator(__p), false); @@ -1760,7 +1776,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_insert_unique_node(size_type __bkt, __hash_code __code, - __node_type* __node, size_type __n_elt) + __node_ptr __node, size_type __n_elt) -> iterator { const __rehash_state& __saved_state = _M_rehash_policy._M_state(); @@ -1774,7 +1790,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __bkt = _M_bucket_index(__code); } - this->_M_store_code(__node, __code); + this->_M_store_code(*__node, __code); // Always insert at the beginning of the bucket. _M_insert_bucket_begin(__bkt, __node); @@ -1789,8 +1805,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_insert_multi_node(__node_type* __hint, - __hash_code __code, __node_type* __node) + _M_insert_multi_node(__node_ptr __hint, + __hash_code __code, __node_ptr __node) -> iterator { const __rehash_state& __saved_state = _M_rehash_policy._M_state(); @@ -1800,17 +1816,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__do_rehash.first) _M_rehash(__do_rehash.second, __saved_state); - this->_M_store_code(__node, __code); + this->_M_store_code(*__node, __code); const key_type& __k = _ExtractKey{}(__node->_M_v()); size_type __bkt = _M_bucket_index(__code); // Find the node before an equivalent one or use hint if it exists and // if it is equivalent. - __node_base* __prev + __node_base_ptr __prev = __builtin_expect(__hint != nullptr, false) - && this->_M_equals(__k, __code, __hint) + && this->_M_equals(__k, __code, *__hint) ? __hint : _M_find_before_node(__bkt, __k, __code); + if (__prev) { // Insert after the node before the equivalent one. @@ -1820,9 +1837,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // hint might be the last bucket node, in this case we need to // update next bucket. if (__node->_M_nxt - && !this->_M_equals(__k, __code, __node->_M_next())) + && !this->_M_equals(__k, __code, *__node->_M_next())) { - size_type __next_bkt = _M_bucket_index(__node->_M_next()); + size_type __next_bkt = _M_bucket_index(*__node->_M_next()); if (__next_bkt != __bkt) _M_buckets[__next_bkt] = __node; } @@ -1853,7 +1870,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __hash_code __code = this->_M_hash_code(__k); size_type __bkt = _M_bucket_index(__code); - if (__node_type* __node = _M_find_node(__bkt, __k, __code)) + if (__node_ptr __node = _M_find_node(__bkt, __k, __code)) return { iterator(__node), false }; _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this }; @@ -1899,13 +1916,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION erase(const_iterator __it) -> iterator { - __node_type* __n = __it._M_cur; - std::size_t __bkt = _M_bucket_index(__n); + __node_ptr __n = __it._M_cur; + std::size_t __bkt = _M_bucket_index(*__n); // Look for previous node to unlink it from the erased one, this // is why we need buckets to contain the before begin to make // this search fast. - __node_base* __prev_n = _M_get_previous_node(__bkt, __n); + __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n); return _M_erase(__bkt, __prev_n, __n); } @@ -1916,15 +1933,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n) + _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n) -> iterator { if (__prev_n == _M_buckets[__bkt]) _M_remove_bucket_begin(__bkt, __n->_M_next(), - __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0); + __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0); else if (__n->_M_nxt) { - size_type __next_bkt = _M_bucket_index(__n->_M_next()); + size_type __next_bkt = _M_bucket_index(*__n->_M_next()); if (__next_bkt != __bkt) _M_buckets[__next_bkt] = __prev_n; } @@ -1951,12 +1968,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION std::size_t __bkt = _M_bucket_index(__code); // Look for the node before the first matching node. - __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); + __node_base_ptr __prev_n = _M_find_before_node(__bkt, __k, __code); if (!__prev_n) return 0; // We found a matching node, erase it. - __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); + __node_ptr __n = static_cast<__node_ptr>(__prev_n->_M_nxt); _M_erase(__bkt, __prev_n, __n); return 1; } @@ -1975,7 +1992,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION std::size_t __bkt = _M_bucket_index(__code); // Look for the node before the first matching node. - __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); + __node_base_ptr __prev_n = _M_find_before_node(__bkt, __k, __code); if (!__prev_n) return 0; @@ -1985,18 +2002,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // We use one loop to find all matching nodes and another to deallocate // them so that the key stays valid during the first loop. It might be // invalidated indirectly when destroying nodes. - __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); - __node_type* __n_last = __n->_M_next(); - while (__n_last && this->_M_node_equals(__n, __n_last)) + __node_ptr __n = static_cast<__node_ptr>(__prev_n->_M_nxt); + __node_ptr __n_last = __n->_M_next(); + while (__n_last && this->_M_node_equals(*__n, *__n_last)) __n_last = __n_last->_M_next(); - std::size_t __n_last_bkt = __n_last ? _M_bucket_index(__n_last) : __bkt; + std::size_t __n_last_bkt = __n_last ? _M_bucket_index(*__n_last) : __bkt; // Deallocate nodes. size_type __result = 0; do { - __node_type* __p = __n->_M_next(); + __node_ptr __p = __n->_M_next(); this->_M_deallocate_node(__n); __n = __p; ++__result; @@ -2022,27 +2039,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION erase(const_iterator __first, const_iterator __last) -> iterator { - __node_type* __n = __first._M_cur; - __node_type* __last_n = __last._M_cur; + __node_ptr __n = __first._M_cur; + __node_ptr __last_n = __last._M_cur; if (__n == __last_n) return iterator(__n); - std::size_t __bkt = _M_bucket_index(__n); + std::size_t __bkt = _M_bucket_index(*__n); - __node_base* __prev_n = _M_get_previous_node(__bkt, __n); + __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n); bool __is_bucket_begin = __n == _M_bucket_begin(__bkt); std::size_t __n_bkt = __bkt; for (;;) { do { - __node_type* __tmp = __n; + __node_ptr __tmp = __n; __n = __n->_M_next(); this->_M_deallocate_node(__tmp); --_M_element_count; if (!__n) break; - __n_bkt = _M_bucket_index(__n); + __n_bkt = _M_bucket_index(*__n); } while (__n != __last_n && __n_bkt == __bkt); if (__is_bucket_begin) @@ -2069,7 +2086,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION clear() noexcept { this->_M_deallocate_nodes(_M_begin()); - __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(__bucket_type)); + __builtin_memset(_M_buckets, 0, + _M_bucket_count * sizeof(__node_base_ptr)); _M_element_count = 0; _M_before_begin._M_nxt = nullptr; } @@ -2129,15 +2147,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_rehash_aux(size_type __bkt_count, true_type /* __uks */) { - __bucket_type* __new_buckets = _M_allocate_buckets(__bkt_count); - __node_type* __p = _M_begin(); + __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count); + __node_ptr __p = _M_begin(); _M_before_begin._M_nxt = nullptr; std::size_t __bbegin_bkt = 0; while (__p) { - __node_type* __next = __p->_M_next(); + __node_ptr __next = __p->_M_next(); std::size_t __bkt - = __hash_code_base::_M_bucket_index(__p, __bkt_count); + = __hash_code_base::_M_bucket_index(*__p, __bkt_count); if (!__new_buckets[__bkt]) { __p->_M_nxt = _M_before_begin._M_nxt; @@ -2172,20 +2190,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_rehash_aux(size_type __bkt_count, false_type /* __uks */) { - __bucket_type* __new_buckets = _M_allocate_buckets(__bkt_count); - - __node_type* __p = _M_begin(); + __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count); + __node_ptr __p = _M_begin(); _M_before_begin._M_nxt = nullptr; std::size_t __bbegin_bkt = 0; std::size_t __prev_bkt = 0; - __node_type* __prev_p = nullptr; + __node_ptr __prev_p = nullptr; bool __check_bucket = false; while (__p) { - __node_type* __next = __p->_M_next(); + __node_ptr __next = __p->_M_next(); std::size_t __bkt - = __hash_code_base::_M_bucket_index(__p, __bkt_count); + = __hash_code_base::_M_bucket_index(*__p, __bkt_count); if (__prev_p && __prev_bkt == __bkt) { @@ -2211,8 +2228,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__prev_p->_M_nxt) { std::size_t __next_bkt - = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), - __bkt_count); + = __hash_code_base::_M_bucket_index( + *__prev_p->_M_next(), __bkt_count); if (__next_bkt != __prev_bkt) __new_buckets[__next_bkt] = __prev_p; } @@ -2242,7 +2259,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__check_bucket && __prev_p->_M_nxt) { std::size_t __next_bkt - = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), + = __hash_code_base::_M_bucket_index(*__prev_p->_M_next(), __bkt_count); if (__next_bkt != __prev_bkt) __new_buckets[__next_bkt] = __prev_p; diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 31ff4f16579..f5ce7209957 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -226,7 +226,7 @@ namespace __detail * Node type with the value to store. */ template - struct _Hash_node_value_base : _Hash_node_base + struct _Hash_node_value_base { typedef _Value value_type; @@ -250,33 +250,32 @@ namespace __detail }; /** - * Primary template struct _Hash_node. + * Primary template struct _Hash_node_code_cache. */ - template - struct _Hash_node; + template + struct _Hash_node_code_cache + { }; /** - * Specialization for nodes with caches, struct _Hash_node. - * - * Base class is __detail::_Hash_node_value_base. + * Specialization for node with cache, struct _Hash_node_code_cache. */ - template - struct _Hash_node<_Value, true> : _Hash_node_value_base<_Value> - { - std::size_t _M_hash_code; + template<> + struct _Hash_node_code_cache + { std::size_t _M_hash_code; }; - _Hash_node* - _M_next() const noexcept - { return static_cast<_Hash_node*>(this->_M_nxt); } - }; + template + struct _Hash_node_value + : _Hash_node_value_base<_Value> + , _Hash_node_code_cache<_Cache_hash_code> + { }; /** - * Specialization for nodes without caches, struct _Hash_node. - * - * Base class is __detail::_Hash_node_value_base. + * Primary template struct _Hash_node. */ - template - struct _Hash_node<_Value, false> : _Hash_node_value_base<_Value> + template + struct _Hash_node + : _Hash_node_base + , _Hash_node_value<_Value, _Cache_hash_code> { _Hash_node* _M_next() const noexcept @@ -289,7 +288,7 @@ namespace __detail { using __node_type = _Hash_node<_Value, _Cache_hash_code>; - __node_type* _M_cur; + __node_type* _M_cur; _Node_iterator_base() = default; _Node_iterator_base(__node_type* __p) noexcept @@ -327,10 +326,10 @@ namespace __detail typedef std::forward_iterator_tag iterator_category; using pointer = typename std::conditional<__constant_iterators, - const _Value*, _Value*>::type; + const value_type*, value_type*>::type; using reference = typename std::conditional<__constant_iterators, - const _Value&, _Value&>::type; + const value_type&, value_type&>::type; _Node_iterator() noexcept : __base_type(nullptr) { } @@ -377,8 +376,8 @@ namespace __detail typedef std::ptrdiff_t difference_type; typedef std::forward_iterator_tag iterator_category; - typedef const _Value* pointer; - typedef const _Value& reference; + typedef const value_type* pointer; + typedef const value_type& reference; _Node_const_iterator() noexcept : __base_type(nullptr) { } @@ -671,11 +670,9 @@ namespace __detail _Unused, _RehashPolicy, _Traits>; using __hash_code = typename __hashtable_base::__hash_code; - using __node_type = typename __hashtable_base::__node_type; public: using key_type = typename __hashtable_base::key_type; - using iterator = typename __hashtable_base::iterator; using mapped_type = typename std::tuple_element<1, _Pair>::type; mapped_type& @@ -705,7 +702,7 @@ namespace __detail __hashtable* __h = static_cast<__hashtable*>(this); __hash_code __code = __h->_M_hash_code(__k); std::size_t __bkt = __h->_M_bucket_index(__code); - if (__node_type* __node = __h->_M_find_node(__bkt, __k, __code)) + if (auto __node = __h->_M_find_node(__bkt, __k, __code)) return __node->_M_v().second; typename __hashtable::_Scoped_node __node { @@ -732,7 +729,7 @@ namespace __detail __hashtable* __h = static_cast<__hashtable*>(this); __hash_code __code = __h->_M_hash_code(__k); std::size_t __bkt = __h->_M_bucket_index(__code); - if (__node_type* __node = __h->_M_find_node(__bkt, __k, __code)) + if (auto __node = __h->_M_find_node(__bkt, __k, __code)) return __node->_M_v().second; typename __hashtable::_Scoped_node __node { @@ -801,15 +798,18 @@ namespace __detail _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>; + using __hash_cached = typename _Traits::__hash_cached; + using __constant_iterators = typename _Traits::__constant_iterators; + + using __hashtable_alloc = _Hashtable_alloc< + __alloc_rebind<_Alloc, _Hash_node<_Value, + __hash_cached::value>>>; + using value_type = typename __hashtable_base::value_type; - using iterator = typename __hashtable_base::iterator; - using const_iterator = typename __hashtable_base::const_iterator; using size_type = typename __hashtable_base::size_type; - using __unique_keys = typename __hashtable_base::__unique_keys; - using __ireturn_type = typename __hashtable_base::__ireturn_type; - using __node_type = _Hash_node<_Value, _Traits::__hash_cached::value>; - using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>; + using __unique_keys = typename _Traits::__unique_keys; + using __node_alloc_type = typename __hashtable_alloc::__node_alloc_type; using __node_gen_type = _AllocNode<__node_alloc_type>; __hashtable& @@ -827,6 +827,16 @@ namespace __detail const _NodeGetter&, false_type __uks); public: + using iterator = _Node_iterator<_Value, __constant_iterators::value, + __hash_cached::value>; + + using const_iterator = _Node_const_iterator<_Value, __constant_iterators::value, + __hash_cached::value>; + + using __ireturn_type = typename std::conditional<__unique_keys::value, + std::pair, + iterator>::type; + __ireturn_type insert(const value_type& __v) { @@ -850,7 +860,7 @@ namespace __detail __hashtable& __h = _M_conjure_hashtable(); auto __code = __h._M_hash_code(__k); std::size_t __bkt = __h._M_bucket_index(__code); - if (__node_type* __node = __h._M_find_node(__bkt, __k, __code)) + if (auto __node = __h._M_find_node(__bkt, __k, __code)) return { iterator(__node), false }; typename __hashtable::_Scoped_node __node { @@ -958,16 +968,12 @@ namespace __detail _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>; - using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey, - _Equal, _Hash, _RangeHash, - _Unused, _Traits>; - using value_type = typename __base_type::value_type; using iterator = typename __base_type::iterator; using const_iterator = typename __base_type::const_iterator; + using __ireturn_type = typename __base_type::__ireturn_type; using __unique_keys = typename __base_type::__unique_keys; - using __ireturn_type = typename __hashtable_base::__ireturn_type; using __hashtable = typename __base_type::__hashtable; using __node_gen_type = typename __base_type::__node_gen_type; @@ -1176,21 +1182,11 @@ namespace __detail * is inherited in some cases by the _Local_iterator_base type used * to implement local_iterator and const_local_iterator. As with * any iterator type we prefer to make it as small as possible. - * - * Primary template is unused except as a hook for specializations. */ template - struct _Hash_code_base; - - /// Specialization: hash function and range-hashing function, no - /// caching of hash codes. - /// Provides typedef and accessor required by C++ 11. - template - struct _Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, - _Unused, false> + struct _Hash_code_base : private _Hashtable_ebo_helper<1, _Hash> { private: @@ -1209,7 +1205,6 @@ namespace __detail protected: typedef std::size_t __hash_code; - typedef _Hash_node<_Value, false> __node_type; // We need the default constructor for the local iterators and _Hashtable // default constructor. @@ -1229,83 +1224,40 @@ namespace __detail { return _RangeHash{}(__c, __bkt_count); } std::size_t - _M_bucket_index(const __node_type* __p, std::size_t __bkt_count) const + _M_bucket_index(const _Hash_node_value<_Value, false>& __n, + std::size_t __bkt_count) const noexcept( noexcept(declval()(declval())) && noexcept(declval()((__hash_code)0, (std::size_t)0)) ) { - return _RangeHash{}(_M_hash()(_ExtractKey{}(__p->_M_v())), + return _RangeHash{}(_M_hash_code(_ExtractKey{}(__n._M_v())), __bkt_count); } - void - _M_store_code(__node_type*, __hash_code) const - { } + std::size_t + _M_bucket_index(const _Hash_node_value<_Value, true>& __n, + std::size_t __bkt_count) const + noexcept( noexcept(declval()((__hash_code)0, + (std::size_t)0)) ) + { return _RangeHash{}(__n._M_hash_code, __bkt_count); } void - _M_copy_code(__node_type*, const __node_type*) const + _M_store_code(_Hash_node_code_cache&, __hash_code) const { } void - _M_swap(_Hash_code_base& __x) - { std::swap(__ebo_hash::_M_get(), __x.__ebo_hash::_M_get()); } - - const _Hash& - _M_hash() const { return __ebo_hash::_M_cget(); } - }; - - /// Specialization: hash function and range-hashing function, - /// caching hash codes. H is provided but ignored. Provides - /// typedef and accessor required by C++ 11. - template - struct _Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, - _Unused, true> - : private _Hashtable_ebo_helper<1, _Hash> - { - private: - using __ebo_hash = _Hashtable_ebo_helper<1, _Hash>; - - public: - typedef _Hash hasher; - - hasher - hash_function() const - { return _M_hash(); } - - protected: - typedef std::size_t __hash_code; - typedef _Hash_node<_Value, true> __node_type; - - // We need the default constructor for _Hashtable default constructor. - _Hash_code_base() = default; - _Hash_code_base(const _Hash& __hash) : __ebo_hash(__hash) { } - - __hash_code - _M_hash_code(const _Key& __k) const - { - static_assert(__is_invocable{}, - "hash function must be invocable with an argument of key type"); - return _M_hash()(__k); - } - - std::size_t - _M_bucket_index(__hash_code __c, std::size_t __bkt_count) const - { return _RangeHash{}(__c, __bkt_count); } - - std::size_t - _M_bucket_index(const __node_type* __p, std::size_t __bkt_count) const - noexcept( noexcept(declval()((__hash_code)0, - (std::size_t)0)) ) - { return _RangeHash{}(__p->_M_hash_code, __bkt_count); } + _M_copy_code(_Hash_node_code_cache&, + const _Hash_node_code_cache&) const + { } void - _M_store_code(__node_type* __n, __hash_code __c) const - { __n->_M_hash_code = __c; } + _M_store_code(_Hash_node_code_cache& __n, __hash_code __c) const + { __n._M_hash_code = __c; } void - _M_copy_code(__node_type* __to, const __node_type* __from) const - { __to->_M_hash_code = __from->_M_hash_code; } + _M_copy_code(_Hash_node_code_cache& __to, + const _Hash_node_code_cache& __from) const + { __to._M_hash_code = __from._M_hash_code; } void _M_swap(_Hash_code_base& __x) @@ -1421,7 +1373,7 @@ namespace __detail } _Local_iterator_base(const _Local_iterator_base& __iter) - : __node_iter_base(__iter), _M_bucket(__iter._M_bucket) + : __node_iter_base(__iter._M_cur), _M_bucket(__iter._M_bucket) , _M_bucket_count(__iter._M_bucket_count) { if (_M_bucket_count != -1) @@ -1447,7 +1399,7 @@ namespace __detail __node_iter_base::_M_incr(); if (this->_M_cur) { - std::size_t __bkt = this->_M_h()->_M_bucket_index(this->_M_cur, + std::size_t __bkt = this->_M_h()->_M_bucket_index(*this->_M_cur, _M_bucket_count); if (__bkt != _M_bucket) this->_M_cur = nullptr; @@ -1485,10 +1437,10 @@ namespace __detail public: typedef _Value value_type; typedef typename std::conditional<__constant_iterators, - const _Value*, _Value*>::type + const value_type*, value_type*>::type pointer; typedef typename std::conditional<__constant_iterators, - const _Value&, _Value&>::type + const value_type&, value_type&>::type reference; typedef std::ptrdiff_t difference_type; typedef std::forward_iterator_tag iterator_category; @@ -1540,8 +1492,8 @@ namespace __detail public: typedef _Value value_type; - typedef const _Value* pointer; - typedef const _Value& reference; + typedef const value_type* pointer; + typedef const value_type& reference; typedef std::ptrdiff_t difference_type; typedef std::forward_iterator_tag iterator_category; @@ -1600,110 +1552,80 @@ namespace __detail struct _Hashtable_base : public _Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, _Traits::__hash_cached::value>, - private _Hashtable_ebo_helper<0, _Equal> - { - public: - typedef _Key key_type; - typedef _Value value_type; - typedef _Equal key_equal; - typedef std::size_t size_type; - typedef std::ptrdiff_t difference_type; - - using __traits_type = _Traits; - using __hash_cached = typename __traits_type::__hash_cached; - using __constant_iterators = typename __traits_type::__constant_iterators; - using __unique_keys = typename __traits_type::__unique_keys; - - using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, - _Hash, _RangeHash, _Unused, - __hash_cached::value>; - - using __hash_code = typename __hash_code_base::__hash_code; - using __node_type = typename __hash_code_base::__node_type; - - using iterator = _Node_iterator; - - using const_iterator = _Node_const_iterator; - - using local_iterator = _Local_iterator; - - using const_local_iterator = _Local_const_iterator; - - using __ireturn_type = typename std::conditional<__unique_keys::value, - std::pair, - iterator>::type; - private: - using _EqualEBO = _Hashtable_ebo_helper<0, _Equal>; + private _Hashtable_ebo_helper<0, _Equal> + { + public: + typedef _Key key_type; + typedef _Value value_type; + typedef _Equal key_equal; + typedef std::size_t size_type; + typedef std::ptrdiff_t difference_type; - template - struct _Equal_hash_code - { - static bool - _S_equals(__hash_code, const _NodeT&) - { return true; } + using __traits_type = _Traits; + using __hash_cached = typename __traits_type::__hash_cached; - static bool - _S_node_equals(const _NodeT&, const _NodeT&) - { return true; } - }; + using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, + _Hash, _RangeHash, _Unused, + __hash_cached::value>; - template - struct _Equal_hash_code<_Hash_node<_Ptr2, true>> - { - static bool - _S_equals(__hash_code __c, const _Hash_node<_Ptr2, true>& __n) - { return __c == __n._M_hash_code; } - - static bool - _S_node_equals(const _Hash_node<_Ptr2, true>& __lhn, - const _Hash_node<_Ptr2, true>& __rhn) - { return __lhn._M_hash_code == __rhn._M_hash_code; } - }; + using __hash_code = typename __hash_code_base::__hash_code; - protected: - _Hashtable_base() = default; - _Hashtable_base(const _Hash& __hash, const _Equal& __eq) - : __hash_code_base(__hash), _EqualEBO(__eq) - { } + private: + using _EqualEBO = _Hashtable_ebo_helper<0, _Equal>; - bool - _M_equals(const _Key& __k, __hash_code __c, const __node_type* __n) const - { - static_assert(__is_invocable{}, + static bool + _S_equals(__hash_code, const _Hash_node_code_cache&) + { return true; } + + static bool + _S_node_equals(const _Hash_node_code_cache&, + const _Hash_node_code_cache&) + { return true; } + + static bool + _S_equals(__hash_code __c, const _Hash_node_code_cache& __n) + { return __c == __n._M_hash_code; } + + static bool + _S_node_equals(const _Hash_node_code_cache& __lhn, + const _Hash_node_code_cache& __rhn) + { return __lhn._M_hash_code == __rhn._M_hash_code; } + + protected: + _Hashtable_base() = default; + _Hashtable_base(const _Hash& __hash, const _Equal& __eq) + : __hash_code_base(__hash), _EqualEBO(__eq) + { } + + bool + _M_equals(const _Key& __k, __hash_code __c, + const _Hash_node_value<_Value, __hash_cached::value>& __n) const + { + static_assert(__is_invocable{}, "key equality predicate must be invocable with two arguments of " "key type"); - return _Equal_hash_code<__node_type>::_S_equals(__c, *__n) - && _M_eq()(__k, _ExtractKey{}(__n->_M_v())); - } + return _S_equals(__c, __n) && _M_eq()(__k, _ExtractKey{}(__n._M_v())); + } - bool - _M_node_equals(const __node_type* __lhn, const __node_type* __rhn) const - { - return _Equal_hash_code<__node_type>::_S_node_equals(*__lhn, *__rhn) - && _M_eq()(_ExtractKey{}(__lhn->_M_v()), - _ExtractKey{}(__rhn->_M_v())); - } + bool + _M_node_equals( + const _Hash_node_value<_Value, __hash_cached::value>& __lhn, + const _Hash_node_value<_Value, __hash_cached::value>& __rhn) const + { + return _S_node_equals(__lhn, __rhn) + && _M_eq()(_ExtractKey{}(__lhn._M_v()), _ExtractKey{}(__rhn._M_v())); + } - void - _M_swap(_Hashtable_base& __x) - { - __hash_code_base::_M_swap(__x); - std::swap(_EqualEBO::_M_get(), __x._EqualEBO::_M_get()); - } + void + _M_swap(_Hashtable_base& __x) + { + __hash_code_base::_M_swap(__x); + std::swap(_EqualEBO::_M_get(), __x._EqualEBO::_M_get()); + } - const _Equal& - _M_eq() const { return _EqualEBO::_M_cget(); } - }; + const _Equal& + _M_eq() const { return _EqualEBO::_M_cget(); } + }; /** * Primary class template _Equality. @@ -1745,7 +1667,6 @@ namespace __detail _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>:: _M_equal(const __hashtable& __other) const { - using __node_base = typename __hashtable::__node_base; using __node_type = typename __hashtable::__node_type; const __hashtable* __this = static_cast(this); if (__this->size() != __other.size()) @@ -1753,8 +1674,8 @@ namespace __detail for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx) { - std::size_t __ybkt = __other._M_bucket_index(__itx._M_cur); - __node_base* __prev_n = __other._M_buckets[__ybkt]; + std::size_t __ybkt = __other._M_bucket_index(*__itx._M_cur); + auto __prev_n = __other._M_buckets[__ybkt]; if (!__prev_n) return false; @@ -1765,7 +1686,7 @@ namespace __detail break; if (!__n->_M_nxt - || __other._M_bucket_index(__n->_M_next()) != __ybkt) + || __other._M_bucket_index(*__n->_M_next()) != __ybkt) return false; } } @@ -1798,7 +1719,6 @@ namespace __detail _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false>:: _M_equal(const __hashtable& __other) const { - using __node_base = typename __hashtable::__node_base; using __node_type = typename __hashtable::__node_type; const __hashtable* __this = static_cast(this); if (__this->size() != __other.size()) @@ -1814,8 +1734,8 @@ namespace __detail ++__itx_end) ++__x_count; - std::size_t __ybkt = __other._M_bucket_index(__itx._M_cur); - __node_base* __y_prev_n = __other._M_buckets[__ybkt]; + std::size_t __ybkt = __other._M_bucket_index(*__itx._M_cur); + auto __y_prev_n = __other._M_buckets[__ybkt]; if (!__y_prev_n) return false; @@ -1826,12 +1746,12 @@ namespace __detail _ExtractKey{}(*__itx))) break; - __node_type* __y_ref_n = __y_n; + auto __y_ref_n = __y_n; for (__y_n = __y_n->_M_next(); __y_n; __y_n = __y_n->_M_next()) - if (!__other._M_node_equals(__y_ref_n, __y_n)) + if (!__other._M_node_equals(*__y_ref_n, *__y_n)) break; - if (!__y_n || __other._M_bucket_index(__y_n) != __ybkt) + if (!__y_n || __other._M_bucket_index(*__y_n) != __ybkt) return false; } @@ -1869,11 +1789,13 @@ namespace __detail using __value_alloc_traits = typename __node_alloc_traits::template rebind_traits; - using __node_base = __detail::_Hash_node_base; - using __bucket_type = __node_base*; - using __bucket_alloc_type = - __alloc_rebind<__node_alloc_type, __bucket_type>; - using __bucket_alloc_traits = std::allocator_traits<__bucket_alloc_type>; + using __node_ptr = __node_type*; + using __node_base = _Hash_node_base; + using __node_base_ptr = __node_base*; + using __buckets_alloc_type = + __alloc_rebind<__node_alloc_type, __node_base_ptr>; + using __buckets_alloc_traits = std::allocator_traits<__buckets_alloc_type>; + using __buckets_ptr = __node_base_ptr*; _Hashtable_alloc() = default; _Hashtable_alloc(const _Hashtable_alloc&) = default; @@ -1894,27 +1816,27 @@ namespace __detail // Allocate a node and construct an element within it. template - __node_type* + __node_ptr _M_allocate_node(_Args&&... __args); // Destroy the element within a node and deallocate the node. void - _M_deallocate_node(__node_type* __n); + _M_deallocate_node(__node_ptr __n); // Deallocate a node. void - _M_deallocate_node_ptr(__node_type* __n); + _M_deallocate_node_ptr(__node_ptr __n); // Deallocate the linked list of nodes pointed to by __n. // The elements within the nodes are destroyed. void - _M_deallocate_nodes(__node_type* __n); + _M_deallocate_nodes(__node_ptr __n); - __bucket_type* + __buckets_ptr _M_allocate_buckets(std::size_t __bkt_count); void - _M_deallocate_buckets(__bucket_type*, std::size_t __bkt_count); + _M_deallocate_buckets(__buckets_ptr, std::size_t __bkt_count); }; // Definitions of class template _Hashtable_alloc's out-of-line member @@ -1923,10 +1845,10 @@ namespace __detail template auto _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(_Args&&... __args) - -> __node_type* + -> __node_ptr { auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1); - __node_type* __n = std::__to_address(__nptr); + __node_ptr __n = std::__to_address(__nptr); __try { ::new ((void*)__n) __node_type; @@ -1944,7 +1866,7 @@ namespace __detail template void - _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_type* __n) + _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_ptr __n) { __node_alloc_traits::destroy(_M_node_allocator(), __n->_M_valptr()); _M_deallocate_node_ptr(__n); @@ -1952,7 +1874,7 @@ namespace __detail template void - _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node_ptr(__node_type* __n) + _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node_ptr(__node_ptr __n) { typedef typename __node_alloc_traits::pointer _Ptr; auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__n); @@ -1962,37 +1884,39 @@ namespace __detail template void - _Hashtable_alloc<_NodeAlloc>::_M_deallocate_nodes(__node_type* __n) + _Hashtable_alloc<_NodeAlloc>::_M_deallocate_nodes(__node_ptr __n) { while (__n) { - __node_type* __tmp = __n; + __node_ptr __tmp = __n; __n = __n->_M_next(); _M_deallocate_node(__tmp); } } template - typename _Hashtable_alloc<_NodeAlloc>::__bucket_type* + auto _Hashtable_alloc<_NodeAlloc>::_M_allocate_buckets(std::size_t __bkt_count) + -> __buckets_ptr { - __bucket_alloc_type __alloc(_M_node_allocator()); + __buckets_alloc_type __alloc(_M_node_allocator()); - auto __ptr = __bucket_alloc_traits::allocate(__alloc, __bkt_count); - __bucket_type* __p = std::__to_address(__ptr); - __builtin_memset(__p, 0, __bkt_count * sizeof(__bucket_type)); + auto __ptr = __buckets_alloc_traits::allocate(__alloc, __bkt_count); + __buckets_ptr __p = std::__to_address(__ptr); + __builtin_memset(__p, 0, __bkt_count * sizeof(__node_base_ptr)); return __p; } template void - _Hashtable_alloc<_NodeAlloc>::_M_deallocate_buckets(__bucket_type* __bkts, - std::size_t __bkt_count) + _Hashtable_alloc<_NodeAlloc>:: + _M_deallocate_buckets(__buckets_ptr __bkts, + std::size_t __bkt_count) { - typedef typename __bucket_alloc_traits::pointer _Ptr; + typedef typename __buckets_alloc_traits::pointer _Ptr; auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__bkts); - __bucket_alloc_type __alloc(_M_node_allocator()); - __bucket_alloc_traits::deallocate(__alloc, __ptr, __bkt_count); + __buckets_alloc_type __alloc(_M_node_allocator()); + __buckets_alloc_traits::deallocate(__alloc, __ptr, __bkt_count); } //@} hashtable-detail -- 2.30.2