@@ -801,6 +801,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__node_base_ptr
_M_find_before_node(const key_type&);
+ bool
+ _M_is_in_bucket(size_type __bkt, __node_ptr, __node_ptr __n,
+ true_type /* __uks */) const
+ { return _M_bucket_index(*__n) == __bkt; }
+
+ bool
+ _M_is_in_bucket(size_type __bkt, __node_ptr __prev_n, __node_ptr __n,
+ false_type /* __uks */) const
+ {
+ return this->_M_key_equals(_ExtractKey{}(__prev_n->_M_v()), *__n)
+ || _M_bucket_index(*__n) == __bkt;
+ }
+
+ bool
+ _M_is_nxt_in_bucket(size_type __bkt, __node_ptr __prev_n,
+ __node_base_ptr __nxt_bkt_n) const
+ {
+ if (__prev_n == __nxt_bkt_n)
+ return false;
+
+ __node_ptr __n = __prev_n->_M_next();
+ if (this->_S_hash_code_equals(*__prev_n, *__n))
+ return true;
+
+ return _M_is_in_bucket(__bkt, __prev_n, __n, __unique_keys{});
+ }
+
// Find and insert helper functions and types
// Find the node before the one matching the criteria.
__node_base_ptr
@@ -1999,13 +2026,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (!__prev_p)
return nullptr;
+ __node_base_ptr __nxt_bkt_n
+ = __bkt < _M_bucket_count - 1 ? _M_buckets[__bkt + 1] : nullptr;
for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);;
__p = __p->_M_next())
{
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_is_nxt_in_bucket(__bkt, __p, __nxt_bkt_n))
break;
__prev_p = __p;
}
@@ -2029,13 +2058,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (!__prev_p)
return nullptr;
+ __node_base_ptr __nxt_bkt_n
+ = __bkt < _M_bucket_count - 1 ? _M_buckets[__bkt + 1] : nullptr;
for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);;
__p = __p->_M_next())
{
if (this->_M_equals_tr(__k, __code, *__p))
return __prev_p;
- if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
+ if (!__p->_M_nxt || !_M_is_nxt_in_bucket(__bkt, __p, __nxt_bkt_n))
break;
__prev_p = __p;
}
@@ -1721,6 +1721,16 @@ namespace __detail
: __hash_code_base(__hash), _EqualEBO(__eq)
{ }
+ static bool
+ _S_hash_code_equals(const _Hash_node_code_cache<false>&,
+ const _Hash_node_code_cache<false>&)
+ { return false; }
+
+ static bool
+ _S_hash_code_equals(const _Hash_node_code_cache<true>& __lhn,
+ const _Hash_node_code_cache<true>& __rhn)
+ { return __lhn._M_hash_code == __rhn._M_hash_code; }
+
bool
_M_key_equals(const _Key& __k,
const _Hash_node_value<_Value,