X-Git-Url: https://git.saurik.com/apple/javascriptcore.git/blobdiff_plain/6fe7ccc865dc7d7541b93c5bcaf6368d2c98a174..cb9aa2694aba0ae4f946ed34b8e0f6c99c1cfe44:/runtime/PropertyMapHashTable.h

diff --git a/runtime/PropertyMapHashTable.h b/runtime/PropertyMapHashTable.h
index 7c8cabb..5da5cf3 100644
--- a/runtime/PropertyMapHashTable.h
+++ b/runtime/PropertyMapHashTable.h
@@ -21,37 +21,45 @@
 #ifndef PropertyMapHashTable_h
 #define PropertyMapHashTable_h
 
-#include "UString.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>
 
 
-#ifndef NDEBUG
-#define DUMP_PROPERTYMAP_STATS 0
-#else
 #define DUMP_PROPERTYMAP_STATS 0
-#endif
+#define DUMP_PROPERTYMAP_COLLISIONS 0
 
-#if DUMP_PROPERTYMAP_STATS
+#define PROPERTY_MAP_DELETED_ENTRY_KEY ((StringImpl*)1)
 
-extern int numProbes;
-extern int numCollisions;
-extern int numRehashes;
-extern int numRemoves;
+namespace JSC {
 
-#endif
+#if DUMP_PROPERTYMAP_STATS
 
-#define PROPERTY_MAP_DELETED_ENTRY_KEY ((StringImpl*)1) 
+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;
+};
 
-namespace JSC {
+JS_EXPORTDATA extern PropertyMapHashTableStats* propertyMapHashTableStats;
+
+#endif
 
 inline bool isPowerOf2(unsigned v)
 {
-    // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html
-    
-    return !(v & (v - 1)) && v;
+    return hasOneBitSet(v);
 }
 
 inline unsigned nextPowerOf2(unsigned v)
@@ -72,21 +80,20 @@ inline unsigned nextPowerOf2(unsigned v)
 
 struct PropertyMapEntry {
     StringImpl* key;
-    unsigned offset;
+    PropertyOffset offset;
     unsigned attributes;
     WriteBarrier<JSCell> specificValue;
 
-    PropertyMapEntry(JSGlobalData& globalData, JSCell* owner, StringImpl* key, unsigned offset, unsigned attributes, JSCell* specificValue)
+    PropertyMapEntry(VM& vm, JSCell* owner, StringImpl* key, PropertyOffset offset, unsigned attributes, JSCell* specificValue)
         : key(key)
         , offset(offset)
         , attributes(attributes)
-        , specificValue(globalData, owner, specificValue, WriteBarrier<JSCell>::MayBeNull)
+        , specificValue(vm, owner, specificValue, WriteBarrier<JSCell>::MayBeNull)
     {
     }
 };
 
-class PropertyTable {
-    WTF_MAKE_FAST_ALLOCATED;
+class PropertyTable : public JSCell {
 
     // This is the implementation for 'iterator' and 'const_iterator',
     // used for iterating over the table in insertion order.
@@ -129,6 +136,19 @@ class PropertyTable {
     };
 
 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;
 
@@ -142,9 +162,9 @@ public:
     typedef std::pair<ValueType*, unsigned> find_iterator;
 
     // Constructor is passed an initial capacity, a PropertyTable to copy, or both.
-    explicit PropertyTable(unsigned initialCapacity);
-    PropertyTable(JSGlobalData&, JSCell*, const PropertyTable&);
-    PropertyTable(JSGlobalData&, JSCell*, unsigned initialCapacity, const PropertyTable&);
+    static PropertyTable* create(VM&, unsigned initialCapacity);
+    static PropertyTable* clone(VM&, const PropertyTable&);
+    static PropertyTable* clone(VM&, unsigned initialCapacity, const PropertyTable&);
     ~PropertyTable();
 
     // Ordered iteration methods.
@@ -156,8 +176,10 @@ public:
     // Find a value in the table.
     find_iterator find(const KeyType&);
     find_iterator findWithString(const KeyType&);
+    ValueType* get(const KeyType&);
     // Add a value to the table
-    std::pair<find_iterator, bool> add(const ValueType& entry);
+    enum EffectOnPropertyOffset { PropertyOffsetMayChange, PropertyOffsetMustNotChange };
+    std::pair<find_iterator, bool> add(const ValueType& entry, PropertyOffset&, EffectOnPropertyOffset);
     // Remove a value from the table.
     void remove(const find_iterator& iter);
     void remove(const KeyType& key);
@@ -174,18 +196,27 @@ public:
     // Used to maintain a list of unused entries in the property storage.
     void clearDeletedOffsets();
     bool hasDeletedOffset();
-    unsigned getDeletedOffset();
-    void addDeletedOffset(unsigned offset);
+    PropertyOffset getDeletedOffset();
+    void addDeletedOffset(PropertyOffset);
+    
+    PropertyOffset nextOffset(PropertyOffset inlineCapacity);
 
     // Copy this PropertyTable, ensuring the copy has at least the capacity provided.
-    PassOwnPtr<PropertyTable> copy(JSGlobalData&, JSCell* owner, unsigned newCapacity);
+    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&);
     // Used to insert a value known not to be in the table, and where we know capacity to be available.
     void reinsert(const ValueType& entry);
@@ -230,78 +261,12 @@ private:
     unsigned* m_index;
     unsigned m_keyCount;
     unsigned m_deletedCount;
-    OwnPtr< Vector<unsigned> > m_deletedOffsets;
+    OwnPtr< Vector<PropertyOffset>> m_deletedOffsets;
 
     static const unsigned MinimumTableSize = 16;
     static const unsigned EmptyEntryIndex = 0;
 };
 
-inline PropertyTable::PropertyTable(unsigned initialCapacity)
-    : m_indexSize(sizeForCapacity(initialCapacity))
-    , m_indexMask(m_indexSize - 1)
-    , m_index(static_cast<unsigned*>(fastZeroedMalloc(dataSize())))
-    , m_keyCount(0)
-    , m_deletedCount(0)
-{
-    ASSERT(isPowerOf2(m_indexSize));
-}
-
-inline PropertyTable::PropertyTable(JSGlobalData&, JSCell* owner, const PropertyTable& other)
-    : m_indexSize(other.m_indexSize)
-    , m_indexMask(other.m_indexMask)
-    , m_index(static_cast<unsigned*>(fastMalloc(dataSize())))
-    , m_keyCount(other.m_keyCount)
-    , m_deletedCount(other.m_deletedCount)
-{
-    ASSERT(isPowerOf2(m_indexSize));
-
-    memcpy(m_index, other.m_index, dataSize());
-
-    iterator end = this->end();
-    for (iterator iter = begin(); iter != end; ++iter) {
-        iter->key->ref();
-        Heap::writeBarrier(owner, iter->specificValue.get());
-    }
-
-    // Copy the m_deletedOffsets vector.
-    Vector<unsigned>* otherDeletedOffsets = other.m_deletedOffsets.get();
-    if (otherDeletedOffsets)
-        m_deletedOffsets = adoptPtr(new Vector<unsigned>(*otherDeletedOffsets));
-}
-
-inline PropertyTable::PropertyTable(JSGlobalData&, JSCell* owner, unsigned initialCapacity, const PropertyTable& other)
-    : m_indexSize(sizeForCapacity(initialCapacity))
-    , m_indexMask(m_indexSize - 1)
-    , m_index(static_cast<unsigned*>(fastZeroedMalloc(dataSize())))
-    , m_keyCount(0)
-    , m_deletedCount(0)
-{
-    ASSERT(isPowerOf2(m_indexSize));
-    ASSERT(initialCapacity >= other.m_keyCount);
-
-    const_iterator end = other.end();
-    for (const_iterator iter = other.begin(); iter != end; ++iter) {
-        ASSERT(canInsert());
-        reinsert(*iter);
-        iter->key->ref();
-        Heap::writeBarrier(owner, iter->specificValue.get());
-    }
-
-    // Copy the m_deletedOffsets vector.
-    Vector<unsigned>* otherDeletedOffsets = other.m_deletedOffsets.get();
-    if (otherDeletedOffsets)
-        m_deletedOffsets = adoptPtr(new Vector<unsigned>(*otherDeletedOffsets));
-}
-
-inline PropertyTable::~PropertyTable()
-{
-    iterator end = this->end();
-    for (iterator iter = begin(); iter != end; ++iter)
-        iter->key->deref();
-
-    fastFree(m_index);
-}
-
 inline PropertyTable::iterator PropertyTable::begin()
 {
     return iterator(skipDeletedEntries(table()));
@@ -325,12 +290,12 @@ inline PropertyTable::const_iterator PropertyTable::end() const
 inline PropertyTable::find_iterator PropertyTable::find(const KeyType& key)
 {
     ASSERT(key);
-    ASSERT(key->isIdentifier());
+    ASSERT(key->isAtomic() || key->isEmptyUnique());
     unsigned hash = key->existingHash();
     unsigned step = 0;
 
 #if DUMP_PROPERTYMAP_STATS
-    ++numProbes;
+    ++propertyMapHashTableStats->numFinds;
 #endif
 
     while (true) {
@@ -340,58 +305,95 @@ inline PropertyTable::find_iterator PropertyTable::find(const KeyType& key)
         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
-        ++numCollisions;
+        ++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
 
-        if (!step)
-            step = WTF::doubleHash(key->existingHash()) | 1;
         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
-        ++numRehashes;
+        ++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->isIdentifier() && !key->hasHash());
+    ASSERT(!key->isAtomic() && !key->hasHash());
     unsigned hash = key->hash();
     unsigned step = 0;
 
 #if DUMP_PROPERTYMAP_STATS
-    ++numProbes;
+    ++propertyMapHashTableStats->numLookups;
 #endif
 
     while (true) {
         unsigned entryIndex = m_index[hash & m_indexMask];
         if (entryIndex == EmptyEntryIndex)
             return std::make_pair((ValueType*)0, hash & m_indexMask);
-        if (equal(key, table()[entryIndex - 1].key))
+        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
-        ++numCollisions;
+        ++propertyMapHashTableStats->numLookupProbing;
 #endif
 
         if (!step)
             step = WTF::doubleHash(key->existingHash()) | 1;
         hash += step;
-
-#if DUMP_PROPERTYMAP_STATS
-        ++numRehashes;
-#endif
     }
 }
 
-inline std::pair<PropertyTable::find_iterator, bool> PropertyTable::add(const ValueType& entry)
+inline std::pair<PropertyTable::find_iterator, bool> PropertyTable::add(const ValueType& entry, PropertyOffset& offset, EffectOnPropertyOffset offsetEffect)
 {
     // Look for a value with a matching key already in the array.
     find_iterator iter = find(entry.key);
-    if (iter.first)
+    if (iter.first) {
+        RELEASE_ASSERT(iter.first->offset <= offset);
         return std::make_pair(iter, false);
+    }
+
+#if DUMP_PROPERTYMAP_STATS
+    ++propertyMapHashTableStats->numAdds;
+#endif
 
     // Ref the key
     entry.key->ref();
@@ -410,6 +412,12 @@ inline std::pair<PropertyTable::find_iterator, bool> PropertyTable::add(const Va
     *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);
 }
 
@@ -420,7 +428,7 @@ inline void PropertyTable::remove(const find_iterator& iter)
         return;
 
 #if DUMP_PROPERTYMAP_STATS
-    ++numRemoves;
+    ++propertyMapHashTableStats->numRemoves;
 #endif
 
     // Replace this one element with the deleted sentinel. Also clear out
@@ -468,29 +476,37 @@ inline bool PropertyTable::hasDeletedOffset()
     return m_deletedOffsets && !m_deletedOffsets->isEmpty();
 }
 
-inline unsigned PropertyTable::getDeletedOffset()
+inline PropertyOffset PropertyTable::getDeletedOffset()
 {
-    unsigned offset = m_deletedOffsets->last();
+    PropertyOffset offset = m_deletedOffsets->last();
     m_deletedOffsets->removeLast();
     return offset;
 }
 
-inline void PropertyTable::addDeletedOffset(unsigned offset)
+inline void PropertyTable::addDeletedOffset(PropertyOffset offset)
 {
     if (!m_deletedOffsets)
-        m_deletedOffsets = adoptPtr(new Vector<unsigned>);
+        m_deletedOffsets = adoptPtr(new Vector<PropertyOffset>);
     m_deletedOffsets->append(offset);
 }
 
-inline PassOwnPtr<PropertyTable> PropertyTable::copy(JSGlobalData& globalData, JSCell* owner, unsigned newCapacity)
+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);
 
     // Fast case; if the new table will be the same m_indexSize as this one, we can memcpy it,
     // save rehashing all keys.
     if (sizeForCapacity(newCapacity) == m_indexSize)
-        return adoptPtr(new PropertyTable(globalData, owner, *this));
-    return adoptPtr(new PropertyTable(globalData, owner, newCapacity, *this));
+        return PropertyTable::clone(vm, *this);
+    return PropertyTable::clone(vm, newCapacity, *this);
 }
 
 #ifndef NDEBUG
@@ -498,13 +514,17 @@ inline size_t PropertyTable::sizeInMemory()
 {
     size_t result = sizeof(PropertyTable) + dataSize();
     if (m_deletedOffsets)
-        result += (m_deletedOffsets->capacity() * sizeof(unsigned));
+        result += (m_deletedOffsets->capacity() * sizeof(PropertyOffset));
     return result;
 }
 #endif
 
 inline void PropertyTable::reinsert(const ValueType& entry)
 {
+#if DUMP_PROPERTYMAP_STATS
+    ++propertyMapHashTableStats->numReinserts;
+#endif
+
     // Used to insert a value known not to be in the table, and where
     // we know capacity to be available.
     ASSERT(canInsert());
@@ -520,6 +540,10 @@ inline void PropertyTable::reinsert(const ValueType& entry)
 
 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();
@@ -576,7 +600,7 @@ inline size_t PropertyTable::dataSize()
 
 inline unsigned PropertyTable::sizeForCapacity(unsigned capacity)
 {
-    if (capacity < 8)
+    if (capacity < MinimumTableSize / 2)
         return MinimumTableSize;
     return nextPowerOf2(capacity + 1) * 2;
 }