PropertyMapHashTable.h [plain text]
#ifndef PropertyMapHashTable_h
#define PropertyMapHashTable_h
#include "JSExportMacros.h"
#include "PropertyOffset.h"
#include "Structure.h"
#include "WriteBarrier.h"
#include <wtf/CryptographicallyRandomNumber.h>
#include <wtf/HashTable.h>
#include <wtf/MathExtras.h>
#include <wtf/PassOwnPtr.h>
#include <wtf/Vector.h>
#include <wtf/text/StringImpl.h>
#define DUMP_PROPERTYMAP_STATS 0
#define DUMP_PROPERTYMAP_COLLISIONS 0
#define PROPERTY_MAP_DELETED_ENTRY_KEY ((StringImpl*)1)
namespace JSC {
#if DUMP_PROPERTYMAP_STATS
struct PropertyMapHashTableStats {
std::atomic<unsigned> numFinds;
std::atomic<unsigned> numCollisions;
std::atomic<unsigned> numLookups;
std::atomic<unsigned> numLookupProbing;
std::atomic<unsigned> numAdds;
std::atomic<unsigned> numRemoves;
std::atomic<unsigned> numRehashes;
std::atomic<unsigned> numReinserts;
};
JS_EXPORTDATA extern PropertyMapHashTableStats* propertyMapHashTableStats;
#endif
inline bool isPowerOf2(unsigned v)
{
return hasOneBitSet(v);
}
inline unsigned nextPowerOf2(unsigned v)
{
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;
return v;
}
struct PropertyMapEntry {
StringImpl* key;
PropertyOffset offset;
unsigned attributes;
WriteBarrier<JSCell> specificValue;
PropertyMapEntry(VM& vm, JSCell* owner, StringImpl* key, PropertyOffset offset, unsigned attributes, JSCell* specificValue)
: key(key)
, offset(offset)
, attributes(attributes)
, specificValue(vm, owner, specificValue, WriteBarrier<JSCell>::MayBeNull)
{
}
};
class PropertyTable : public JSCell {
template<typename T>
class ordered_iterator {
public:
ordered_iterator<T>& operator++()
{
m_valuePtr = skipDeletedEntries(m_valuePtr + 1);
return *this;
}
bool operator==(const ordered_iterator<T>& other)
{
return m_valuePtr == other.m_valuePtr;
}
bool operator!=(const ordered_iterator<T>& other)
{
return m_valuePtr != other.m_valuePtr;
}
T& operator*()
{
return *m_valuePtr;
}
T* operator->()
{
return m_valuePtr;
}
ordered_iterator(T* valuePtr)
: m_valuePtr(valuePtr)
{
}
private:
T* m_valuePtr;
};
public:
static const bool needsDestruction = true;
static const bool hasImmortalStructure = true;
static void destroy(JSCell*);
DECLARE_EXPORT_INFO;
static Structure* createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype)
{
return Structure::create(vm, globalObject, prototype, TypeInfo(CompoundType, StructureFlags), info());
}
static void visitChildren(JSCell*, SlotVisitor&);
typedef StringImpl* KeyType;
typedef PropertyMapEntry ValueType;
typedef ordered_iterator<ValueType> iterator;
typedef ordered_iterator<const ValueType> const_iterator;
typedef std::pair<ValueType*, unsigned> find_iterator;
static PropertyTable* create(VM&, unsigned initialCapacity);
static PropertyTable* clone(VM&, const PropertyTable&);
static PropertyTable* clone(VM&, unsigned initialCapacity, const PropertyTable&);
~PropertyTable();
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
find_iterator find(const KeyType&);
find_iterator findWithString(const KeyType&);
ValueType* get(const KeyType&);
enum EffectOnPropertyOffset { PropertyOffsetMayChange, PropertyOffsetMustNotChange };
std::pair<find_iterator, bool> add(const ValueType& entry, PropertyOffset&, EffectOnPropertyOffset);
void remove(const find_iterator& iter);
void remove(const KeyType& key);
unsigned size() const;
bool isEmpty() const;
unsigned propertyStorageSize() const;
void clearDeletedOffsets();
bool hasDeletedOffset();
PropertyOffset getDeletedOffset();
void addDeletedOffset(PropertyOffset);
PropertyOffset nextOffset(PropertyOffset inlineCapacity);
PropertyTable* copy(VM&, unsigned newCapacity);
#ifndef NDEBUG
size_t sizeInMemory();
void checkConsistency();
#endif
protected:
static const unsigned StructureFlags = OverridesVisitChildren | StructureIsImmortal;
private:
PropertyTable(VM&, unsigned initialCapacity);
PropertyTable(VM&, const PropertyTable&);
PropertyTable(VM&, unsigned initialCapacity, const PropertyTable&);
PropertyTable(const PropertyTable&);
void reinsert(const ValueType& entry);
void rehash(unsigned newCapacity);
unsigned tableCapacity() const;
unsigned deletedEntryIndex() const;
template<typename T>
static T* skipDeletedEntries(T* valuePtr);
ValueType* table();
const ValueType* table() const;
unsigned usedCount() const;
size_t dataSize();
static unsigned sizeForCapacity(unsigned capacity);
bool canInsert();
unsigned m_indexSize;
unsigned m_indexMask;
unsigned* m_index;
unsigned m_keyCount;
unsigned m_deletedCount;
OwnPtr< Vector<PropertyOffset>> m_deletedOffsets;
static const unsigned MinimumTableSize = 16;
static const unsigned EmptyEntryIndex = 0;
};
inline PropertyTable::iterator PropertyTable::begin()
{
return iterator(skipDeletedEntries(table()));
}
inline PropertyTable::iterator PropertyTable::end()
{
return iterator(table() + usedCount());
}
inline PropertyTable::const_iterator PropertyTable::begin() const
{
return const_iterator(skipDeletedEntries(table()));
}
inline PropertyTable::const_iterator PropertyTable::end() const
{
return const_iterator(table() + usedCount());
}
inline PropertyTable::find_iterator PropertyTable::find(const KeyType& key)
{
ASSERT(key);
ASSERT(key->isAtomic() || key->isEmptyUnique());
unsigned hash = key->existingHash();
unsigned step = 0;
#if DUMP_PROPERTYMAP_STATS
++propertyMapHashTableStats->numFinds;
#endif
while (true) {
unsigned entryIndex = m_index[hash & m_indexMask];
if (entryIndex == EmptyEntryIndex)
return std::make_pair((ValueType*)0, hash & m_indexMask);
if (key == table()[entryIndex - 1].key)
return std::make_pair(&table()[entryIndex - 1], hash & m_indexMask);
if (!step)
step = WTF::doubleHash(key->existingHash()) | 1;
#if DUMP_PROPERTYMAP_STATS
++propertyMapHashTableStats->numCollisions;
#endif
#if DUMP_PROPERTYMAP_COLLISIONS
dataLog("PropertyTable collision for ", key, " (", hash, ") with step ", step, "\n");
dataLog("Collided with ", table()[entryIndex - 1].key, "(", table()[entryIndex - 1].key->existingHash(), ")\n");
#endif
hash += step;
}
}
inline PropertyTable::ValueType* PropertyTable::get(const KeyType& key)
{
ASSERT(key);
ASSERT(key->isAtomic() || key->isEmptyUnique());
if (!m_keyCount)
return nullptr;
unsigned hash = key->existingHash();
unsigned step = 0;
#if DUMP_PROPERTYMAP_STATS
++propertyMapHashTableStats->numLookups;
#endif
while (true) {
unsigned entryIndex = m_index[hash & m_indexMask];
if (entryIndex == EmptyEntryIndex)
return nullptr;
if (key == table()[entryIndex - 1].key)
return &table()[entryIndex - 1];
#if DUMP_PROPERTYMAP_STATS
++propertyMapHashTableStats->numLookupProbing;
#endif
if (!step)
step = WTF::doubleHash(key->existingHash()) | 1;
hash += step;
}
}
inline PropertyTable::find_iterator PropertyTable::findWithString(const KeyType& key)
{
ASSERT(key);
ASSERT(!key->isAtomic() && !key->hasHash());
unsigned hash = key->hash();
unsigned step = 0;
#if DUMP_PROPERTYMAP_STATS
++propertyMapHashTableStats->numLookups;
#endif
while (true) {
unsigned entryIndex = m_index[hash & m_indexMask];
if (entryIndex == EmptyEntryIndex)
return std::make_pair((ValueType*)0, hash & m_indexMask);
const KeyType& keyInMap = table()[entryIndex - 1].key;
if (equal(key, keyInMap) && keyInMap->isAtomic())
return std::make_pair(&table()[entryIndex - 1], hash & m_indexMask);
#if DUMP_PROPERTYMAP_STATS
++propertyMapHashTableStats->numLookupProbing;
#endif
if (!step)
step = WTF::doubleHash(key->existingHash()) | 1;
hash += step;
}
}
inline std::pair<PropertyTable::find_iterator, bool> PropertyTable::add(const ValueType& entry, PropertyOffset& offset, EffectOnPropertyOffset offsetEffect)
{
find_iterator iter = find(entry.key);
if (iter.first) {
RELEASE_ASSERT(iter.first->offset <= offset);
return std::make_pair(iter, false);
}
#if DUMP_PROPERTYMAP_STATS
++propertyMapHashTableStats->numAdds;
#endif
entry.key->ref();
if (!canInsert()) {
rehash(m_keyCount + 1);
iter = find(entry.key);
ASSERT(!iter.first);
}
unsigned entryIndex = usedCount() + 1;
m_index[iter.second] = entryIndex;
iter.first = &table()[entryIndex - 1];
*iter.first = entry;
++m_keyCount;
if (offsetEffect == PropertyOffsetMayChange)
offset = std::max(offset, entry.offset);
else
RELEASE_ASSERT(offset >= entry.offset);
return std::make_pair(iter, true);
}
inline void PropertyTable::remove(const find_iterator& iter)
{
if (!iter.first)
return;
#if DUMP_PROPERTYMAP_STATS
++propertyMapHashTableStats->numRemoves;
#endif
m_index[iter.second] = deletedEntryIndex();
iter.first->key->deref();
iter.first->key = PROPERTY_MAP_DELETED_ENTRY_KEY;
ASSERT(m_keyCount >= 1);
--m_keyCount;
++m_deletedCount;
if (m_deletedCount * 4 >= m_indexSize)
rehash(m_keyCount);
}
inline void PropertyTable::remove(const KeyType& key)
{
remove(find(key));
}
inline unsigned PropertyTable::size() const
{
return m_keyCount;
}
inline bool PropertyTable::isEmpty() const
{
return !m_keyCount;
}
inline unsigned PropertyTable::propertyStorageSize() const
{
return size() + (m_deletedOffsets ? m_deletedOffsets->size() : 0);
}
inline void PropertyTable::clearDeletedOffsets()
{
m_deletedOffsets.clear();
}
inline bool PropertyTable::hasDeletedOffset()
{
return m_deletedOffsets && !m_deletedOffsets->isEmpty();
}
inline PropertyOffset PropertyTable::getDeletedOffset()
{
PropertyOffset offset = m_deletedOffsets->last();
m_deletedOffsets->removeLast();
return offset;
}
inline void PropertyTable::addDeletedOffset(PropertyOffset offset)
{
if (!m_deletedOffsets)
m_deletedOffsets = adoptPtr(new Vector<PropertyOffset>);
m_deletedOffsets->append(offset);
}
inline PropertyOffset PropertyTable::nextOffset(PropertyOffset inlineCapacity)
{
if (hasDeletedOffset())
return getDeletedOffset();
return offsetForPropertyNumber(size(), inlineCapacity);
}
inline PropertyTable* PropertyTable::copy(VM& vm, unsigned newCapacity)
{
ASSERT(newCapacity >= m_keyCount);
if (sizeForCapacity(newCapacity) == m_indexSize)
return PropertyTable::clone(vm, *this);
return PropertyTable::clone(vm, newCapacity, *this);
}
#ifndef NDEBUG
inline size_t PropertyTable::sizeInMemory()
{
size_t result = sizeof(PropertyTable) + dataSize();
if (m_deletedOffsets)
result += (m_deletedOffsets->capacity() * sizeof(PropertyOffset));
return result;
}
#endif
inline void PropertyTable::reinsert(const ValueType& entry)
{
#if DUMP_PROPERTYMAP_STATS
++propertyMapHashTableStats->numReinserts;
#endif
ASSERT(canInsert());
find_iterator iter = find(entry.key);
ASSERT(!iter.first);
unsigned entryIndex = usedCount() + 1;
m_index[iter.second] = entryIndex;
table()[entryIndex - 1] = entry;
++m_keyCount;
}
inline void PropertyTable::rehash(unsigned newCapacity)
{
#if DUMP_PROPERTYMAP_STATS
++propertyMapHashTableStats->numRehashes;
#endif
unsigned* oldEntryIndices = m_index;
iterator iter = this->begin();
iterator end = this->end();
m_indexSize = sizeForCapacity(newCapacity);
m_indexMask = m_indexSize - 1;
m_keyCount = 0;
m_deletedCount = 0;
m_index = static_cast<unsigned*>(fastZeroedMalloc(dataSize()));
for (; iter != end; ++iter) {
ASSERT(canInsert());
reinsert(*iter);
}
fastFree(oldEntryIndices);
}
inline unsigned PropertyTable::tableCapacity() const { return m_indexSize >> 1; }
inline unsigned PropertyTable::deletedEntryIndex() const { return tableCapacity() + 1; }
template<typename T>
inline T* PropertyTable::skipDeletedEntries(T* valuePtr)
{
while (valuePtr->key == PROPERTY_MAP_DELETED_ENTRY_KEY)
++valuePtr;
return valuePtr;
}
inline PropertyTable::ValueType* PropertyTable::table()
{
return reinterpret_cast<ValueType*>(m_index + m_indexSize);
}
inline const PropertyTable::ValueType* PropertyTable::table() const
{
return reinterpret_cast<const ValueType*>(m_index + m_indexSize);
}
inline unsigned PropertyTable::usedCount() const
{
return m_keyCount + m_deletedCount;
}
inline size_t PropertyTable::dataSize()
{
return m_indexSize * sizeof(unsigned) + ((tableCapacity()) + 1) * sizeof(ValueType);
}
inline unsigned PropertyTable::sizeForCapacity(unsigned capacity)
{
if (capacity < MinimumTableSize / 2)
return MinimumTableSize;
return nextPowerOf2(capacity + 1) * 2;
}
inline bool PropertyTable::canInsert()
{
return usedCount() < tableCapacity();
}
}
#endif // PropertyMapHashTable_h