HashPolicy documentation should clarify HashPolicy::match can be called with item with different hash
Categories
(Core :: MFBT, enhancement)
Tracking
()
| Tracking | Status | |
|---|---|---|
| firefox121 | --- | fixed |
People
(Reporter: arai, Assigned: arai)
References
Details
Attachments
(1 file)
(Derived from bug 1802568)
The hash policy document mentions the HashPolicy::match method, but it doesn't explain the underlying assumption (what holds, what doesn't hold) about the key vs lookup:
//---------------------------------------------------------------------------
// Hash Policy
//---------------------------------------------------------------------------
...
// A hash policy |HP| for a hash table with key-type |Key| must provide:
//
...
// - a static member function |HP::match| that tests equality of key and
// lookup values:
//
// static bool match(const Key&, const Lookup&);
In ParserAtom, we use HashTable for storing atomized strings, and the item contains hash (ParserAtom::hash_), and that value is used by HashPolicy.
struct ParserAtomLookupHasher {
...
static inline bool match(const ParserAtom* entry, const Lookup& l) {
return l.equalsEntry(entry);
template <typename CharT>
class SpecificParserAtomLookup : public ParserAtomLookup {
...
virtual bool equalsEntry(const ParserAtom* entry) const override {
return entry->equalsSeq<CharT>(hash_, seq_);
template <typename CharT>
inline bool ParserAtom::equalsSeq(HashNumber hash,
InflatedChar16Sequence<CharT> seq) const {
// Compare hashes first.
if (hash_ != hash) {
return false;
the hash of key and lookup are almost always same, that almost implies the hash comparison is unnecessary, but this is actually not true, because HashTable uses a different hash calculated from the original hash, and that can cause collision between two different hashes.
HashNumber keyHash = prepareHash(inputHash);
So, the above hash_ != hash comparison results in true only when the collision happens.
It's better mentioning that characteristics in the HashPolicy document, so that it's clear that the HashPolicy::match implementation shouldn't assume hash equality, even if it's almost always same in practice.
|
Assignee | |
Comment 1•2 years ago
|
||
|
||
Updated•2 years ago
|
|
||
Comment 3•2 years ago
|
||
| bugherder | ||
Description
•