1 files changed, 79 insertions, 75 deletions

diff --git a/Source/JavaScriptCore/runtime/PropertyMapHashTable.h b/Source/JavaScriptCore/runtime/PropertyMapHashTable.h
index 9ddb6997c..b068b991d 100644
--- a/Source/JavaScriptCore/runtime/PropertyMapHashTable.h
+++ b/Source/JavaScriptCore/runtime/PropertyMapHashTable.h
@@ -1,5 +1,5 @@
 /*
- *  Copyright (C) 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
+ *  Copyright (C) 2004, 2005, 2006, 2007, 2008, 2014 Apple Inc. All rights reserved.
  *
  *  This library is free software; you can redistribute it and/or
  *  modify it under the terms of the GNU Library General Public
@@ -21,34 +21,40 @@
 #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>
+#include <wtf/text/AtomicStringImpl.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 ((UniquedStringImpl*)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)
 {
@@ -71,22 +77,7 @@ inline unsigned nextPowerOf2(unsigned 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 {
+class PropertyTable final : public JSCell {
 
     // This is the implementation for 'iterator' and 'const_iterator',
     // used for iterating over the table in insertion order.
@@ -129,20 +120,20 @@ class PropertyTable : public JSCell {
     };
 
 public:
+    typedef JSCell Base;
+    static const unsigned StructureFlags = Base::StructureFlags | StructureIsImmortal;
+
     static const bool needsDestruction = true;
-    static const bool hasImmortalStructure = true;
     static void destroy(JSCell*);
 
-    static JS_EXPORTDATA const ClassInfo s_info;
+    DECLARE_EXPORT_INFO;
 
     static Structure* createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype)
     {
-        return Structure::create(vm, globalObject, prototype, TypeInfo(CompoundType, OverridesVisitChildren), &s_info);
+        return Structure::create(vm, globalObject, prototype, TypeInfo(CellType, StructureFlags), info());
     }
 
-    static void visitChildren(JSCell*, SlotVisitor&);
-
-    typedef StringImpl* KeyType;
+    typedef UniquedStringImpl* KeyType;
     typedef PropertyMapEntry ValueType;
 
     // The in order iterator provides overloaded * and -> to access the Value at the current position.
@@ -156,8 +147,8 @@ public:
 
     // Constructor is passed an initial capacity, a PropertyTable to copy, or both.
     static PropertyTable* create(VM&, unsigned initialCapacity);
-    static PropertyTable* clone(VM&, JSCell* owner, const PropertyTable&);
-    static PropertyTable* clone(VM&, JSCell* owner, unsigned initialCapacity, const PropertyTable&);
+    static PropertyTable* clone(VM&, const PropertyTable&);
+    static PropertyTable* clone(VM&, unsigned initialCapacity, const PropertyTable&);
     ~PropertyTable();
 
     // Ordered iteration methods.
@@ -168,7 +159,7 @@ 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
     enum EffectOnPropertyOffset { PropertyOffsetMayChange, PropertyOffsetMustNotChange };
     std::pair<find_iterator, bool> add(const ValueType& entry, PropertyOffset&, EffectOnPropertyOffset);
@@ -194,7 +185,7 @@ public:
     PropertyOffset nextOffset(PropertyOffset inlineCapacity);
 
     // Copy this PropertyTable, ensuring the copy has at least the capacity provided.
-    PropertyTable* copy(VM&, JSCell* owner, unsigned newCapacity);
+    PropertyTable* copy(VM&, unsigned newCapacity);
 
 #ifndef NDEBUG
     size_t sizeInMemory();
@@ -203,8 +194,8 @@ public:
 
 private:
     PropertyTable(VM&, unsigned initialCapacity);
-    PropertyTable(VM&, JSCell*, const PropertyTable&);
-    PropertyTable(VM&, JSCell*, unsigned initialCapacity, const PropertyTable&);
+    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.
@@ -250,9 +241,9 @@ private:
     unsigned* m_index;
     unsigned m_keyCount;
     unsigned m_deletedCount;
-    OwnPtr< Vector<PropertyOffset> > m_deletedOffsets;
+    std::unique_ptr<Vector<PropertyOffset>> m_deletedOffsets;
 
-    static const unsigned MinimumTableSize = 8;
+    static const unsigned MinimumTableSize = 16;
     static const unsigned EmptyEntryIndex = 0;
 };
 
@@ -279,12 +270,12 @@ inline PropertyTable::const_iterator PropertyTable::end() const
 inline PropertyTable::find_iterator PropertyTable::find(const KeyType& key)
 {
     ASSERT(key);
-    ASSERT(key->isIdentifier() || key->isEmptyUnique());
-    unsigned hash = key->existingHash();
+    ASSERT(key->isAtomic() || key->isSymbol());
+    unsigned hash = IdentifierRepHash::hash(key);
     unsigned step = 0;
 
 #if DUMP_PROPERTYMAP_STATS
-    ++numProbes;
+    ++propertyMapHashTableStats->numFinds;
 #endif
 
     while (true) {
@@ -294,50 +285,51 @@ 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 DUMP_PROPERTYMAP_STATS
-        ++numCollisions;
-#endif
-
         if (!step)
-            step = WTF::doubleHash(key->existingHash()) | 1;
-        hash += step;
+            step = WTF::doubleHash(IdentifierRepHash::hash(key)) | 1;
 
 #if DUMP_PROPERTYMAP_STATS
-        ++numRehashes;
+        ++propertyMapHashTableStats->numCollisions;
 #endif
+
+#if DUMP_PROPERTYMAP_COLLISIONS
+        dataLog("PropertyTable collision for ", key, " (", hash, ") with step ", step, "\n");
+        dataLog("Collided with ", table()[entryIndex - 1].key, "(", IdentifierRepHash::hash(table()[entryIndex - 1].key), ")\n");
+#endif
+
+        hash += step;
     }
 }
 
-inline PropertyTable::find_iterator PropertyTable::findWithString(const KeyType& key)
+inline PropertyTable::ValueType* PropertyTable::get(const KeyType& key)
 {
     ASSERT(key);
-    ASSERT(!key->isIdentifier() && !key->hasHash());
-    unsigned hash = key->hash();
+    ASSERT(key->isAtomic() || key->isSymbol());
+
+    if (!m_keyCount)
+        return nullptr;
+
+    unsigned hash = IdentifierRepHash::hash(key);
     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);
-        const KeyType& keyInMap = table()[entryIndex - 1].key;
-        if (equal(key, keyInMap) && keyInMap->isIdentifier())
-            return std::make_pair(&table()[entryIndex - 1], hash & m_indexMask);
+            return nullptr;
+        if (key == table()[entryIndex - 1].key)
+            return &table()[entryIndex - 1];
 
 #if DUMP_PROPERTYMAP_STATS
-        ++numCollisions;
+        ++propertyMapHashTableStats->numLookupProbing;
 #endif
 
         if (!step)
-            step = WTF::doubleHash(key->existingHash()) | 1;
+            step = WTF::doubleHash(IdentifierRepHash::hash(key)) | 1;
         hash += step;
-
-#if DUMP_PROPERTYMAP_STATS
-        ++numRehashes;
-#endif
     }
 }
 
@@ -350,6 +342,10 @@ inline std::pair<PropertyTable::find_iterator, bool> PropertyTable::add(const Va
         return std::make_pair(iter, false);
     }
 
+#if DUMP_PROPERTYMAP_STATS
+    ++propertyMapHashTableStats->numAdds;
+#endif
+
     // Ref the key
     entry.key->ref();
 
@@ -383,7 +379,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
@@ -423,7 +419,7 @@ inline unsigned PropertyTable::propertyStorageSize() const
 
 inline void PropertyTable::clearDeletedOffsets()
 {
-    m_deletedOffsets.clear();
+    m_deletedOffsets = nullptr;
 }
 
 inline bool PropertyTable::hasDeletedOffset()
@@ -441,7 +437,7 @@ inline PropertyOffset PropertyTable::getDeletedOffset()
 inline void PropertyTable::addDeletedOffset(PropertyOffset offset)
 {
     if (!m_deletedOffsets)
-        m_deletedOffsets = adoptPtr(new Vector<PropertyOffset>);
+        m_deletedOffsets = std::make_unique<Vector<PropertyOffset>>();
     m_deletedOffsets->append(offset);
 }
 
@@ -453,15 +449,15 @@ inline PropertyOffset PropertyTable::nextOffset(PropertyOffset inlineCapacity)
     return offsetForPropertyNumber(size(), inlineCapacity);
 }
 
-inline PropertyTable* PropertyTable::copy(VM& vm, JSCell* owner, unsigned newCapacity)
+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 PropertyTable::clone(vm, owner, *this);
-    return PropertyTable::clone(vm, owner, newCapacity, *this);
+        return PropertyTable::clone(vm, *this);
+    return PropertyTable::clone(vm, newCapacity, *this);
 }
 
 #ifndef NDEBUG
@@ -476,6 +472,10 @@ inline size_t PropertyTable::sizeInMemory()
 
 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());
@@ -491,6 +491,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();