diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 9dadc62e328..460f25affe4 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -48,6 +48,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Mandatory to have erase not throwing. __is_nothrow_invocable>>; + template + using __small_size_threshold_default + = typename conditional<__cache, + // No small size optimization if hash code is cached... + integral_constant, + _Small_size_threshold<_Hash>>::type; /** * Primary class template _Hashtable. * @@ -743,6 +749,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __node_base* _M_find_before_node(size_type, const key_type&, __hash_code) const; + __node_base* + _M_find_before_node(const key_type&); + __node_type* _M_find_node(size_type __bkt, const key_type& __key, __hash_code __c) const @@ -766,6 +775,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __node_base* _M_get_previous_node(size_type __bkt, __node_base* __n); + pair + _M_compute_hash_code(const_iterator __hint, const key_type& __k) const; + // 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. @@ -1490,6 +1502,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION find(const key_type& __k) -> iterator { + if (size() <= __traits_type::__small_size_threshold::value) + { + for (auto __it = begin(); __it != end(); ++__it) + if (this->_M_key_equals(__k, __it._M_cur)) + return __it; + return end(); + } + __hash_code __code = this->_M_hash_code(__k); std::size_t __bkt = _M_bucket_index(__code); return iterator(_M_find_node(__bkt, __k, __code)); @@ -1504,6 +1524,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION find(const key_type& __k) const -> const_iterator { + if (size() <= __traits_type::__small_size_threshold::value) + { + for (auto __it = begin(); __it != end(); ++__it) + if (this->_M_key_equals(__k, __it._M_cur)) + return __it; + return end(); + } + __hash_code __code = this->_M_hash_code(__k); std::size_t __bkt = _M_bucket_index(__code); return const_iterator(_M_find_node(__bkt, __k, __code)); @@ -1619,6 +1647,34 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return nullptr; } + // Find the node before the one whose key compares equal to k. + // Return nullptr if no node is found. + template + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RehashPolicy, _Traits>:: + _M_find_before_node(const key_type& __k) + -> __node_base* + { + __node_base* __prev_p = &_M_before_begin; + if (!__prev_p->_M_nxt) + return nullptr; + + for (__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt); + __p != nullptr; + __p = __p->_M_next()) + { + if (this->_M_key_equals(__k, __p)) + return __prev_p; + + __prev_p = __p; + } + + return nullptr; + } + template @@ -1702,11 +1758,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // First build the node to get access to the hash code _Scoped_node __node { this, std::forward<_Args>(__args)... }; const key_type& __k = this->_M_extract()(__node._M_node->_M_v()); + if (size() <= __traits_type::__small_size_threshold::value) + { + for (auto __it = begin(); __it != end(); ++__it) + if (this->_M_key_equals(__k, __it._M_cur)) + // There is already an equivalent node, no insertion + return { __it, false }; + } + __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)) - // There is already an equivalent node, no insertion - return std::make_pair(iterator(__p), false); + if (size() > __traits_type::__small_size_threshold::value) + if (__node_type* __p = _M_find_node(__bkt, __k, __code)) + // There is already an equivalent node, no insertion + return { iterator(__p), false }; // Insert the node auto __pos = _M_insert_node(__uks, __bkt, __code, __node._M_node); @@ -1728,13 +1793,40 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Scoped_node __node { this, std::forward<_Args>(__args)... }; const key_type& __k = this->_M_extract()(__node._M_node->_M_v()); - __hash_code __code = this->_M_hash_code(__k); + auto __res = this->_M_compute_hash_code(__hint, __k); auto __pos - = _M_insert_node(__mks, __hint._M_cur, __code, __node._M_node); + = _M_insert_node(__mks, __res.first._M_cur, __res.second, + __node._M_node); __node._M_node = nullptr; return __pos; } + template + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RehashPolicy, _Traits>:: + _M_compute_hash_code(const_iterator __hint, const key_type& __k) const + -> pair + { + if (size() <= __traits_type::__small_size_threshold::value) + { + if (__hint != cend()) + { + for (auto __it = __hint; __it != cend(); ++__it) + if (this->_M_key_equals(__k, __it._M_cur)) + return { __it, this->_M_hash_code(__it._M_cur) }; + } + + for (auto __it = cbegin(); __it != __hint; ++__it) + if (this->_M_key_equals(__k, __it._M_cur)) + return { __it, this->_M_hash_code(__it._M_cur) }; + } + + return { __hint, this->_M_hash_code(__k) }; + } + template @@ -1830,11 +1922,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION -> pair { const key_type& __k = this->_M_extract()(__v); + + if (size() <= __traits_type::__small_size_threshold::value) + for (auto __it = begin(); __it != end(); ++__it) + if (this->_M_key_equals(__k, __it._M_cur)) + return { __it, false }; + __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)) - return { iterator(__node), false }; + if (size() > __traits_type::__small_size_threshold::value) + if (__node_type* __node = _M_find_node(__bkt, __k, __code)) + return { iterator(__node), false }; _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this }; auto __pos = _M_insert_node(__uks, __bkt, __code, __node._M_node); @@ -1856,13 +1955,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { // First compute the hash code so that we don't do anything if it // throws. - __hash_code __code = this->_M_hash_code(this->_M_extract()(__v)); + auto __res + = this->_M_compute_hash_code(__hint, this->_M_extract()(__v)); // Second allocate new node so that we don't rehash if it throws. _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this }; - const key_type& __k = this->_M_extract()(__node._M_node->_M_v()); auto __pos - = _M_insert_node(__mks, __hint._M_cur, __code, __node._M_node); + = _M_insert_node(__mks, __res.first._M_cur, __res.second, + __node._M_node); __node._M_node = nullptr; return __pos; } @@ -1922,16 +2022,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_erase(__unique_keys_t, const key_type& __k) -> size_type { - __hash_code __code = this->_M_hash_code(__k); - std::size_t __bkt = _M_bucket_index(__code); + __node_base* __prev_n; + __node_type* __n; + std::size_t __bkt; + if (size() <= __traits_type::__small_size_threshold::value) + { + __prev_n = _M_find_before_node(__k); + if (!__prev_n) + return 0; - // Look for the node before the first matching node. - __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); - if (!__prev_n) - return 0; + // We found a matching node, erase it. + __n = static_cast<__node_type*>(__prev_n->_M_nxt); + __bkt = _M_bucket_index(__n); + } + else + { + __hash_code __code = this->_M_hash_code(__k); + __bkt = _M_bucket_index(__code); + + // Look for the node before the first matching node. + __prev_n = _M_find_before_node(__bkt, __k, __code); + if (!__prev_n) + return 0; + + // We found a matching node, erase it. + __n = static_cast<__node_type*>(__prev_n->_M_nxt); + } - // We found a matching node, erase it. - __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); _M_erase(__bkt, __prev_n, __n); return 1; } @@ -1945,13 +2062,31 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_erase(__multi_keys_t, const key_type& __k) -> size_type { - __hash_code __code = this->_M_hash_code(__k); - std::size_t __bkt = _M_bucket_index(__code); + std::size_t __bkt; + __node_base* __prev_n; + __node_type* __n; + if (size() <= __traits_type::__small_size_threshold::value) + { + __prev_n = _M_find_before_node(__k); + if (!__prev_n) + return 0; - // Look for the node before the first matching node. - __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); - if (!__prev_n) - return 0; + // We found a matching node, erase it. + __n = static_cast<__node_type*>(__prev_n->_M_nxt); + __bkt = _M_bucket_index(__n); + } + else + { + __hash_code __code = this->_M_hash_code(__k); + __bkt = _M_bucket_index(__code); + + // Look for the node before the first matching node. + __prev_n = _M_find_before_node(__bkt, __k, __code); + if (!__prev_n) + return 0; + + __n = static_cast<__node_type*>(__prev_n->_M_nxt); + } // _GLIBCXX_RESOLVE_LIB_DEFECTS // 526. Is it undefined if a function in the standard changes @@ -1959,7 +2094,6 @@ _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)) __n_last = __n_last->_M_next(); diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 11ea47b322e..6f329c82335 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -45,6 +45,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _Traits> class _Hashtable; + /** + * struct _Small_size_threshold + * + * Traits like type giving the threshold below which the hashtable will be + * considered as small. + * + * @tparam _Hash The hash functor. + */ + template + struct _Small_size_threshold + : public std::integral_constant::value ? 0 : 20> + { }; + namespace __detail { /** @@ -203,13 +216,22 @@ namespace __detail * be an arbitrary number. This is true for unordered_set and * unordered_map, false for unordered_multiset and * unordered_multimap. + * + * @tparam _Small_size_threshold Integer value. Threshold below which + * hashtable will be considered as small enough to perform linear + * lookup. */ - template + template struct _Hashtable_traits { using __hash_cached = __bool_constant<_Cache_hash_code>; using __constant_iterators = __bool_constant<_Constant_iterators>; using __unique_keys = __bool_constant<_Unique_keys>; + using __small_size_threshold + = integral_constant; }; /** @@ -1039,9 +1061,11 @@ namespace __detail struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RehashPolicy, _Traits, true_type> { + private: using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RehashPolicy, _Traits>; + public: float max_load_factor() const noexcept { @@ -1189,6 +1213,10 @@ namespace __detail return _M_hash()(__k); } + __hash_code + _M_hash_code(const __node_type* __n) const + { return _M_hash_code(_M_extract()(__n->_M_v())); } + std::size_t _M_bucket_index(__hash_code __c, std::size_t __bkt_count) const { return _RangedHash{}(__c, __bkt_count); } @@ -1198,9 +1226,7 @@ namespace __detail noexcept( noexcept(declval()(declval())) && noexcept(declval()((__hash_code)0, (std::size_t)0)) ) - { - return _RangedHash{}(_M_hash()(_M_extract()(__p->_M_v())), __bkt_count); - } + { return _RangedHash{}(_M_hash_code(__p), __bkt_count); } void _M_store_code(__node_type*, __hash_code) const @@ -1268,6 +1294,10 @@ namespace __detail return _M_hash()(__k); } + __hash_code + _M_hash_code(const __node_type* __n) const + { return __n->_M_hash_code; } + std::size_t _M_bucket_index(__hash_code __c, std::size_t __bkt_count) const { return _RangedHash{}(__c, __bkt_count); } @@ -1669,21 +1699,26 @@ namespace __detail { } bool - _M_equals(const _Key& __k, __hash_code __c, const __node_type* __n) const + _M_key_equals(const _Key& __k, const __node_type* __n) const { static_assert(__is_invocable{}, "key equality predicate must be invocable with two arguments of " "key type"); + return _M_eq()(__k, this->_M_extract()(__n->_M_v())); + } + + bool + _M_equals(const _Key& __k, __hash_code __c, const __node_type* __n) const + { return _Equal_hash_code<__node_type>::_S_equals(__c, *__n) - && _M_eq()(__k, this->_M_extract()(__n->_M_v())); + && _M_key_equals(__k, __n); } 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()(this->_M_extract()(__lhn->_M_v()), - this->_M_extract()(__rhn->_M_v())); + && _M_key_equals(this->_M_extract()(__lhn->_M_v()), __rhn); } void diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h index 310cfd39d79..5265020f608 100644 --- a/libstdc++-v3/include/bits/unordered_map.h +++ b/libstdc++-v3/include/bits/unordered_map.h @@ -36,30 +36,36 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _GLIBCXX_BEGIN_NAMESPACE_CONTAINER /// Base types for unordered_map. - template - using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>; + template + using __umap_traits + = __detail::_Hashtable_traits<_Cache, false, true, + __small_size_threshold_default<_Cache, _Hash>::value>; template, typename _Pred = std::equal_to<_Key>, typename _Alloc = std::allocator >, - typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value>> + typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value, + _Hash>> using __umap_hashtable = _Hashtable<_Key, std::pair, _Alloc, __detail::_Select1st, _Pred, _Hash, __detail::_Prime_rehash_policy, _Tr>; /// Base types for unordered_multimap. - template - using __ummap_traits = __detail::_Hashtable_traits<_Cache, false, false>; + template + using __ummap_traits + = __detail::_Hashtable_traits<_Cache, false, false, + __small_size_threshold_default<_Cache, _Hash>::value>; template, typename _Pred = std::equal_to<_Key>, typename _Alloc = std::allocator >, - typename _Tr = __ummap_traits<__cache_default<_Key, _Hash>::value>> + typename _Tr = __ummap_traits<__cache_default<_Key, _Hash>::value, + _Hash>> using __ummap_hashtable = _Hashtable<_Key, std::pair, _Alloc, __detail::_Select1st, _Pred, _Hash, diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h index 4319495f18b..9bfa8639faf 100644 --- a/libstdc++-v3/include/bits/unordered_set.h +++ b/libstdc++-v3/include/bits/unordered_set.h @@ -36,27 +36,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _GLIBCXX_BEGIN_NAMESPACE_CONTAINER /// Base types for unordered_set. - template - using __uset_traits = __detail::_Hashtable_traits<_Cache, true, true>; + template + using __uset_traits + = __detail::_Hashtable_traits<_Cache, true, true, + __small_size_threshold_default<_Cache, _Hash>::value>; template, typename _Pred = std::equal_to<_Value>, typename _Alloc = std::allocator<_Value>, - typename _Tr = __uset_traits<__cache_default<_Value, _Hash>::value>> + typename _Tr = __uset_traits<__cache_default<_Value, _Hash>::value, + _Hash>> using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc, __detail::_Identity, _Pred, _Hash, __detail::_Prime_rehash_policy, _Tr>; /// Base types for unordered_multiset. - template - using __umset_traits = __detail::_Hashtable_traits<_Cache, true, false>; + template + using __umset_traits + = __detail::_Hashtable_traits<_Cache, true, false, + __small_size_threshold_default<_Cache, _Hash>::value>; template, typename _Pred = std::equal_to<_Value>, typename _Alloc = std::allocator<_Value>, - typename _Tr = __umset_traits<__cache_default<_Value, _Hash>::value>> + typename _Tr = __umset_traits<__cache_default<_Value, _Hash>::value, + _Hash>> using __umset_hashtable = _Hashtable<_Value, _Value, _Alloc, __detail::_Identity, _Pred, _Hash, diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc b/libstdc++-v3/src/c++11/hashtable_c++0x.cc index de437d00b56..dcf8a81fc5e 100644 --- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc +++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc @@ -30,6 +30,7 @@ #include #include #include +#include #include namespace std _GLIBCXX_VISIBILITY(default)