Bug 1481138 - Clarify that Hash{Map,Set}::putNew() can be used if elements have been removed. r=luke
Hash{Map,Set}::putNew() can be used on a table that has had elements removed,
despite some comments to the contrary.
This patch fixes those comments.
This patch also removes the !isRemoved() assertion in findFreeEntry(), which is
confusing -- !isLive() would be more precise, but also obvious from the
surrounding code.
MozReview-Commit-ID: q4qwKGBsHx
--- a/mfbt/HashTable.h
+++ b/mfbt/HashTable.h
@@ -268,17 +268,30 @@ public:
if (p) {
p->value() = std::forward<ValueInput>(aValue);
return true;
}
return add(
p, std::forward<KeyInput>(aKey), std::forward<ValueInput>(aValue));
}
- // Like put(), but asserts that the given key is not already present.
+ // Like put(), but slightly faster. Must only be used when the given key is
+ // not already present. (In debug builds, assertions check this.)
+ // Particularly suitable for populating a new map with known unique keys,
+ // e.g.:
+ //
+ // using HM = HashMap<int,char>;
+ // HM h;
+ // if (!h.init(3)) {
+ // MOZ_CRASH("OOM");
+ // }
+ // MOZ_ALWAYS_TRUE(h.putNew(1, 'a')); // unique key
+ // MOZ_ALWAYS_TRUE(h.putNew(2, 'b')); // unique key
+ // MOZ_ALWAYS_TRUE(h.putNew(3, 'c')); // unique key
+ //
template<typename KeyInput, typename ValueInput>
MOZ_MUST_USE bool putNew(KeyInput&& aKey, ValueInput&& aValue)
{
return mImpl.putNew(
aKey, std::forward<KeyInput>(aKey), std::forward<ValueInput>(aValue));
}
// Like |lookup(l)|, but on miss, |p = lookupForAdd(l)| allows efficient
@@ -556,17 +569,30 @@ public:
// Add |aU| if it is not present already. Returns false on OOM.
template<typename U>
MOZ_MUST_USE bool put(U&& aU)
{
AddPtr p = lookupForAdd(aU);
return p ? true : add(p, std::forward<U>(aU));
}
- // Like put(), but asserts that the given key is not already present.
+ // Like put(), but slightly faster. Must only be used when the given element
+ // is not already present. (In debug builds, assertions check this.)
+ // Particularly suitable for populating a new set with known unique elements,
+ // e.g.:
+ //
+ // using HS = HashMap<int>;
+ // HS h;
+ // if (!h.init(3)) {
+ // MOZ_CRASH("OOM");
+ // }
+ // MOZ_ALWAYS_TRUE(h.putNew(1)); // unique element
+ // MOZ_ALWAYS_TRUE(h.putNew(2)); // unique element
+ // MOZ_ALWAYS_TRUE(h.putNew(3)); // unique element
+ //
template<typename U>
MOZ_MUST_USE bool putNew(U&& aU)
{
return mImpl.putNew(aU, std::forward<U>(aU));
}
// Like the other putNew(), but for when |Lookup| is different to |T|.
template<typename U>
@@ -1754,22 +1780,19 @@ private:
}
if (entry->matchHash(aKeyHash) && match(*entry, aLookup)) {
return *entry;
}
}
}
- // This is a copy of lookup hardcoded to the assumptions:
- // 1. the lookup is a lookupForAdd
- // 2. the key, whose |keyHash| has been passed is not in the table,
- // 3. no entries have been removed from the table.
- // This specialized search avoids the need for recovering lookup values
- // from entries, which allows more flexible Lookup/Key types.
+ // This is a copy of lookup() hardcoded to the assumptions:
+ // 1. the lookup is for an add;
+ // 2. the key, whose |keyHash| has been passed is not in the table.
Entry& findFreeEntry(HashNumber aKeyHash)
{
MOZ_ASSERT(!(aKeyHash & sCollisionBit));
MOZ_ASSERT(mTable);
// We assume 'aKeyHash' has already been distributed.
// Compute the primary hash address.
@@ -1780,17 +1803,16 @@ private:
if (!entry->isLive()) {
return *entry;
}
// Collision: double hash.
DoubleHash dh = hash2(aKeyHash);
while (true) {
- MOZ_ASSERT(!entry->isRemoved());
entry->setCollision();
h1 = applyDoubleHash(h1, dh);
entry = &mTable[h1];
if (!entry->isLive()) {
return *entry;
}