Modified: trunk/Source/WTF/wtf/HashTable.h (255610 => 255611)
--- trunk/Source/WTF/wtf/HashTable.h 2020-02-03 23:40:44 UTC (rev 255610)
+++ trunk/Source/WTF/wtf/HashTable.h 2020-02-03 23:48:29 UTC (rev 255611)
@@ -366,7 +366,7 @@
{
invalidateIterators();
if (m_table)
- deallocateTable(m_table, m_tableSize);
+ deallocateTable(m_table);
#if CHECK_HASHTABLE_USE_AFTER_DESTRUCTION
m_table = (ValueType*)(uintptr_t)0xbbadbeef;
#endif
@@ -383,9 +383,9 @@
// This is more efficient because we don't have to skip all the empty and deleted
// buckets, and iterating an empty table is a common case that's worth optimizing.
iterator begin() { return isEmpty() ? end() : makeIterator(m_table); }
- iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); }
+ iterator end() { return makeKnownGoodIterator(m_table + tableSize()); }
const_iterator begin() const { return isEmpty() ? end() : makeConstIterator(m_table); }
- const_iterator end() const { return makeKnownGoodConstIterator(m_table + m_tableSize); }
+ const_iterator end() const { return makeKnownGoodConstIterator(m_table + tableSize()); }
iterator random()
{
@@ -393,7 +393,7 @@
return end();
while (1) {
- auto& bucket = m_table[weakRandomUint32() & m_tableSizeMask];
+ auto& bucket = m_table[weakRandomUint32() & tableSizeMask()];
if (!isEmptyOrDeletedBucket(bucket))
return makeKnownGoodIterator(&bucket);
};
@@ -401,22 +401,23 @@
const_iterator random() const { return static_cast<const_iterator>(const_cast<HashTable*>(this)->random()); }
- unsigned size() const { return m_keyCount; }
- unsigned capacity() const { return m_tableSize; }
- bool isEmpty() const { return !m_keyCount; }
+ unsigned size() const { return keyCount(); }
+ unsigned capacity() const { return tableSize(); }
+ bool isEmpty() const { return !keyCount(); }
void reserveInitialCapacity(unsigned keyCount)
{
ASSERT(!m_table);
- ASSERT(!m_tableSize);
- ASSERT(!m_deletedCount);
+ ASSERT(!tableSize());
unsigned minimumTableSize = KeyTraits::minimumTableSize;
unsigned newTableSize = std::max(minimumTableSize, computeBestTableSize(keyCount));
- m_tableSize = newTableSize;
- m_tableSizeMask = newTableSize - 1;
m_table = allocateTable(newTableSize);
+ setTableSize(newTableSize);
+ setTableSizeMask(newTableSize - 1);
+ setDeletedCount(0);
+ setKeyCount(0);
}
AddResult add(const ValueType& value) { return add<IdentityTranslatorType>(Extractor::extract(value), value); }
@@ -468,7 +469,7 @@
private:
static ValueType* allocateTable(unsigned size);
- static void deallocateTable(ValueType* table, unsigned size);
+ static void deallocateTable(ValueType* table);
typedef std::pair<ValueType*, bool> LookupType;
typedef std::pair<LookupType, unsigned> FullLookupType;
@@ -486,11 +487,11 @@
void remove(ValueType*);
static constexpr unsigned computeBestTableSize(unsigned keyCount);
- bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; }
- bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; }
- bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > KeyTraits::minimumTableSize; }
+ bool shouldExpand() const { return (keyCount() + deletedCount()) * maxLoad >= tableSize(); }
+ bool mustRehashInPlace() const { return keyCount() * minLoad < tableSize() * 2; }
+ bool shouldShrink() const { return keyCount() * minLoad < tableSize() && tableSize() > KeyTraits::minimumTableSize; }
ValueType* expand(ValueType* entry = nullptr);
- void shrink() { rehash(m_tableSize / 2, nullptr); }
+ void shrink() { rehash(tableSize() / 2, nullptr); }
void shrinkToBestSize();
void deleteReleasedWeakBuckets();
@@ -504,10 +505,10 @@
FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash)
{ return FullLookupType(LookupType(position, found), hash); }
- iterator makeIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize); }
- const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize); }
- iterator makeKnownGoodIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
- const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
+ iterator makeIterator(ValueType* pos) { return iterator(this, pos, m_table + tableSize()); }
+ const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + tableSize()); }
+ iterator makeKnownGoodIterator(ValueType* pos) { return iterator(this, pos, m_table + tableSize(), HashItemKnownGood); }
+ const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + tableSize(), HashItemKnownGood); }
#if ASSERT_ENABLED
void checkTableConsistencyExceptSize() const;
@@ -521,15 +522,26 @@
static void invalidateIterators() { }
#endif
- static constexpr unsigned m_maxLoad = 2;
- static constexpr unsigned m_minLoad = 6;
+ static constexpr unsigned maxLoad = 2;
+ static constexpr unsigned minLoad = 6;
- ValueType* m_table;
- unsigned m_tableSize;
- unsigned m_tableSizeMask;
- unsigned m_keyCount;
- unsigned m_deletedCount;
+ static constexpr int tableSizeOffset = -1;
+ static constexpr int tableSizeMaskOffset = -2;
+ static constexpr int keyCountOffset = -3;
+ static constexpr int deletedCountOffset = -4;
+ static constexpr unsigned metadataSize = 4 * sizeof(unsigned);
+ unsigned tableSize() const { return m_table ? reinterpret_cast<unsigned*>(m_table)[tableSizeOffset] : 0; }
+ void setTableSize(unsigned size) const { ASSERT(m_table); reinterpret_cast<unsigned*>(m_table)[tableSizeOffset] = size; }
+ unsigned tableSizeMask() const { ASSERT(m_table); return m_table ? reinterpret_cast<unsigned*>(m_table)[tableSizeMaskOffset] : 0; }
+ void setTableSizeMask(unsigned mask) { ASSERT(m_table); reinterpret_cast<unsigned*>(m_table)[tableSizeMaskOffset] = mask; }
+ unsigned keyCount() const { return m_table ? reinterpret_cast<unsigned*>(m_table)[keyCountOffset] : 0; }
+ void setKeyCount(unsigned count) const { ASSERT(m_table); reinterpret_cast<unsigned*>(m_table)[keyCountOffset] = count; }
+ unsigned deletedCount() const { ASSERT(m_table); return reinterpret_cast<unsigned*>(m_table)[deletedCountOffset]; }
+ void setDeletedCount(unsigned count) const { ASSERT(m_table); reinterpret_cast<unsigned*>(m_table)[deletedCountOffset] = count; }
+
+ ValueType* m_table { nullptr };
+
#if CHECK_HASHTABLE_ITERATORS
public:
// All access to m_iterators should be guarded with m_mutex.
@@ -584,11 +596,7 @@
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable()
- : m_table(0)
- , m_tableSize(0)
- , m_tableSizeMask(0)
- , m_keyCount(0)
- , m_deletedCount(0)
+ : m_table(nullptr)
#if CHECK_HASHTABLE_ITERATORS
, m_iterators(0)
, m_mutex(makeUnique<Lock>())
@@ -649,14 +657,14 @@
checkKey<HashTranslator>(key);
unsigned k = 0;
- unsigned sizeMask = m_tableSizeMask;
ValueType* table = m_table;
+ if (!table)
+ return nullptr;
+
+ unsigned sizeMask = tableSizeMask();
unsigned h = HashTranslator::hash(key);
unsigned i = h & sizeMask;
- if (!table)
- return 0;
-
#if DUMP_HASHTABLE_STATS
++HashTableStats::numAccesses;
unsigned probeCount = 0;
@@ -707,7 +715,7 @@
unsigned k = 0;
ValueType* table = m_table;
- unsigned sizeMask = m_tableSizeMask;
+ unsigned sizeMask = tableSizeMask();
unsigned h = HashTranslator::hash(key);
unsigned i = h & sizeMask;
@@ -768,7 +776,7 @@
unsigned k = 0;
ValueType* table = m_table;
- unsigned sizeMask = m_tableSizeMask;
+ unsigned sizeMask = tableSizeMask();
unsigned h = HashTranslator::hash(key);
unsigned i = h & sizeMask;
@@ -834,7 +842,7 @@
unsigned k = 0;
ValueType* table = m_table;
- unsigned sizeMask = m_tableSizeMask;
+ unsigned sizeMask = tableSizeMask();
unsigned h = HashTranslator::hash(key);
unsigned i = h & sizeMask;
@@ -915,7 +923,7 @@
unsigned k = 0;
ValueType* table = m_table;
- unsigned sizeMask = m_tableSizeMask;
+ unsigned sizeMask = tableSizeMask();
unsigned h = HashTranslator::hash(key);
unsigned i = h & sizeMask;
@@ -969,11 +977,11 @@
if (deletedEntry) {
initializeBucket(*deletedEntry);
entry = deletedEntry;
- --m_deletedCount;
+ setDeletedCount(deletedCount() - 1);
}
HashTranslator::translate(*entry, std::forward<T>(key), std::forward<Extra>(extra));
- ++m_keyCount;
+ setKeyCount(keyCount() + 1);
if (shouldExpand())
entry = expand(entry);
@@ -1007,11 +1015,11 @@
if (isDeletedBucket(*entry)) {
initializeBucket(*entry);
- --m_deletedCount;
+ setDeletedCount(deletedCount() - 1);
}
HashTranslator::translate(*entry, std::forward<T>(key), std::forward<Extra>(extra), h);
- ++m_keyCount;
+ setKeyCount(keyCount() + 1);
if (shouldExpand())
entry = expand(entry);
@@ -1105,8 +1113,8 @@
#endif
deleteBucket(*pos);
- ++m_deletedCount;
- --m_keyCount;
+ setDeletedCount(deletedCount() + 1);
+ setKeyCount(keyCount() - 1);
if (shouldShrink())
shrink();
@@ -1157,7 +1165,7 @@
unsigned removedBucketCount = 0;
ValueType* table = m_table;
- for (unsigned i = m_tableSize; i--;) {
+ for (unsigned i = tableSize(); i--;) {
ValueType& bucket = table[i];
if (isEmptyOrDeletedBucket(bucket))
continue;
@@ -1168,8 +1176,10 @@
deleteBucket(bucket);
++removedBucketCount;
}
- m_deletedCount += removedBucketCount;
- m_keyCount -= removedBucketCount;
+ if (removedBucketCount) {
+ setDeletedCount(deletedCount() + removedBucketCount);
+ setKeyCount(keyCount() - removedBucketCount);
+ }
if (shouldShrink())
shrinkToBestSize();
@@ -1181,12 +1191,14 @@
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(unsigned size) -> ValueType*
{
+ static_assert(!(metadataSize % alignof(ValueType)));
+
// would use a template member function with explicit specializations here, but
// gcc doesn't appear to support that
if (Traits::emptyValueIsZero)
- return static_cast<ValueType*>(HashTableMalloc::zeroedMalloc(size * sizeof(ValueType)));
+ return reinterpret_cast<ValueType*>(static_cast<char*>(HashTableMalloc::zeroedMalloc(metadataSize + size * sizeof(ValueType))) + metadataSize);
- ValueType* result = static_cast<ValueType*>(HashTableMalloc::malloc(size * sizeof(ValueType)));
+ ValueType* result = reinterpret_cast<ValueType*>(static_cast<char*>(HashTableMalloc::malloc(metadataSize + size * sizeof(ValueType))) + metadataSize);
for (unsigned i = 0; i < size; i++)
initializeBucket(result[i]);
return result;
@@ -1193,13 +1205,14 @@
}
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
- void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType* table, unsigned size)
+ void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType* table)
{
+ unsigned size = reinterpret_cast<unsigned*>(table)[tableSizeOffset];
for (unsigned i = 0; i < size; ++i) {
if (!isDeletedBucket(table[i]))
table[i].~ValueType();
}
- HashTableMalloc::free(table);
+ HashTableMalloc::free(reinterpret_cast<char*>(table) - metadataSize);
}
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
@@ -1209,12 +1222,13 @@
deleteReleasedWeakBuckets();
unsigned newSize;
- if (m_tableSize == 0)
+ unsigned oldSize = tableSize();
+ if (!oldSize)
newSize = KeyTraits::minimumTableSize;
else if (mustRehashInPlace())
- newSize = m_tableSize;
+ newSize = oldSize;
else
- newSize = m_tableSize * 2;
+ newSize = oldSize * 2;
return rehash(newSize, entry);
}
@@ -1239,18 +1253,19 @@
void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::shrinkToBestSize()
{
unsigned minimumTableSize = KeyTraits::minimumTableSize;
- rehash(std::max(minimumTableSize, computeBestTableSize(m_keyCount)), nullptr);
+ rehash(std::max(minimumTableSize, computeBestTableSize(keyCount())), nullptr);
}
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deleteReleasedWeakBuckets()
{
- for (unsigned i = 0; i < m_tableSize; ++i) {
+ unsigned tableSize = this->tableSize();
+ for (unsigned i = 0; i < tableSize; ++i) {
auto& entry = m_table[i];
if (isReleasedWeakBucket(entry)) {
deleteBucket(entry);
- ++m_deletedCount;
- --m_keyCount;
+ setDeletedCount(deletedCount() + 1);
+ setKeyCount(keyCount() - 1);
}
}
}
@@ -1260,7 +1275,7 @@
{
internalCheckTableConsistencyExceptSize();
- unsigned oldTableSize = m_tableSize;
+ unsigned oldTableSize = tableSize();
ValueType* oldTable = m_table;
#if DUMP_HASHTABLE_STATS
@@ -1273,9 +1288,12 @@
++m_stats->numRehashes;
#endif
- m_tableSize = newTableSize;
- m_tableSizeMask = newTableSize - 1;
+ unsigned oldKeyCount = keyCount();
m_table = allocateTable(newTableSize);
+ setTableSize(newTableSize);
+ setTableSizeMask(newTableSize - 1);
+ setDeletedCount(0);
+ setKeyCount(oldKeyCount);
Value* newEntry = nullptr;
for (unsigned i = 0; i != oldTableSize; ++i) {
@@ -1294,7 +1312,7 @@
if (isReleasedWeakBucket(oldEntry)) {
ASSERT(std::addressof(oldEntry) != entry);
oldEntry.~ValueType();
- --m_keyCount;
+ setKeyCount(keyCount() - 1);
continue;
}
@@ -1306,10 +1324,9 @@
}
}
- m_deletedCount = 0;
+ if (oldTable)
+ HashTableMalloc::free(reinterpret_cast<char*>(oldTable) - metadataSize);
- HashTableMalloc::free(oldTable);
-
internalCheckTableConsistency();
return newEntry;
}
@@ -1321,21 +1338,13 @@
if (!m_table)
return;
- deallocateTable(m_table, m_tableSize);
- m_table = 0;
- m_tableSize = 0;
- m_tableSizeMask = 0;
- m_keyCount = 0;
- m_deletedCount = 0;
+ deallocateTable(m_table);
+ m_table = nullptr;
}
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(const HashTable& other)
: m_table(nullptr)
- , m_tableSize(0)
- , m_tableSizeMask(0)
- , m_keyCount(0)
- , m_deletedCount(0)
#if CHECK_HASHTABLE_ITERATORS
, m_iterators(nullptr)
, m_mutex(makeUnique<Lock>())
@@ -1348,10 +1357,12 @@
if (!otherKeyCount)
return;
- m_tableSize = computeBestTableSize(otherKeyCount);
- m_tableSizeMask = m_tableSize - 1;
- m_keyCount = otherKeyCount;
- m_table = allocateTable(m_tableSize);
+ unsigned bestTableSize = computeBestTableSize(otherKeyCount);
+ m_table = allocateTable(bestTableSize);
+ setTableSize(bestTableSize);
+ setTableSizeMask(bestTableSize - 1);
+ setKeyCount(otherKeyCount);
+ setDeletedCount(0);
for (const auto& otherValue : other)
addUniqueForInitialization<IdentityTranslatorType>(Extractor::extract(otherValue), otherValue);
@@ -1364,10 +1375,6 @@
other.invalidateIterators();
std::swap(m_table, other.m_table);
- std::swap(m_tableSize, other.m_tableSize);
- std::swap(m_tableSizeMask, other.m_tableSizeMask);
- std::swap(m_keyCount, other.m_keyCount);
- std::swap(m_deletedCount, other.m_deletedCount);
#if DUMP_HASHTABLE_STATS_PER_TABLE
m_stats.swap(other.m_stats);
@@ -1391,18 +1398,8 @@
{
other.invalidateIterators();
- m_table = other.m_table;
- m_tableSize = other.m_tableSize;
- m_tableSizeMask = other.m_tableSizeMask;
- m_keyCount = other.m_keyCount;
- m_deletedCount = other.m_deletedCount;
+ m_table = std::exchange(other.m_table, nullptr);
- other.m_table = nullptr;
- other.m_tableSize = 0;
- other.m_tableSizeMask = 0;
- other.m_keyCount = 0;
- other.m_deletedCount = 0;
-
#if DUMP_HASHTABLE_STATS_PER_TABLE
m_stats = WTFMove(other.m_stats);
other.m_stats = nullptr;
@@ -1435,7 +1432,8 @@
unsigned count = 0;
unsigned deletedCount = 0;
- for (unsigned j = 0; j < m_tableSize; ++j) {
+ unsigned tableSize = this->tableSize();
+ for (unsigned j = 0; j < tableSize; ++j) {
ValueType* entry = m_table + j;
if (isEmptyBucket(*entry))
continue;
@@ -1453,11 +1451,11 @@
ValueCheck<Key>::checkConsistency(key);
}
- ASSERT(count == m_keyCount);
- ASSERT(deletedCount == m_deletedCount);
- ASSERT(m_tableSize >= KeyTraits::minimumTableSize);
- ASSERT(m_tableSizeMask);
- ASSERT(m_tableSize == m_tableSizeMask + 1);
+ ASSERT(count == keyCount());
+ ASSERT(deletedCount == this->deletedCount());
+ ASSERT(this->tableSize() >= KeyTraits::minimumTableSize);
+ ASSERT(tableSizeMask());
+ ASSERT(this->tableSize() == tableSizeMask() + 1);
}
#endif // ASSERT_ENABLED
