auto import from //depot/cupcake/@136594

1 files changed, 1049 insertions, 0 deletions

diff --git a/JavaScriptCore/runtime/Structure.cpp b/JavaScriptCore/runtime/Structure.cpp
new file mode 100644
index 0000000..86ee76c
--- /dev/null
+++ b/JavaScriptCore/runtime/Structure.cpp
@@ -0,0 +1,1049 @@
+/*
+ * Copyright (C) 2008 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "config.h"
+#include "Structure.h"
+
+#include "Identifier.h"
+#include "JSObject.h"
+#include "PropertyNameArray.h"
+#include "StructureChain.h"
+#include "Lookup.h"
+#include <wtf/RefCountedLeakCounter.h>
+#include <wtf/RefPtr.h>
+
+#if ENABLE(JSC_MULTIPLE_THREADS)
+#include <wtf/Threading.h>
+#endif
+
+#define DUMP_STRUCTURE_ID_STATISTICS 0
+
+#ifndef NDEBUG
+#define DO_PROPERTYMAP_CONSTENCY_CHECK 0
+#else
+#define DO_PROPERTYMAP_CONSTENCY_CHECK 0
+#endif
+
+using namespace std;
+using namespace WTF;
+
+namespace JSC {
+
+// Choose a number for the following so that most property maps are smaller,
+// but it's not going to blow out the stack to allocate this number of pointers.
+static const int smallMapThreshold = 1024;
+
+// The point at which the function call overhead of the qsort implementation
+// becomes small compared to the inefficiency of insertion sort.
+static const unsigned tinyMapThreshold = 20;
+
+static const unsigned newTableSize = 16;
+
+#ifndef NDEBUG
+static WTF::RefCountedLeakCounter structureCounter("Structure");
+
+#if ENABLE(JSC_MULTIPLE_THREADS)
+static Mutex ignoreSetMutex;
+#endif
+
+static bool shouldIgnoreLeaks;
+static HashSet<Structure*> ignoreSet;
+#endif
+
+#if DUMP_STRUCTURE_ID_STATISTICS
+static HashSet<Structure*> liveStructureSet;
+#endif
+
+void Structure::dumpStatistics()
+{
+#if DUMP_STRUCTURE_ID_STATISTICS
+    unsigned numberLeaf = 0;
+    unsigned numberUsingSingleSlot = 0;
+    unsigned numberSingletons = 0;
+    unsigned numberWithPropertyMaps = 0;
+    unsigned totalPropertyMapsSize = 0;
+
+    HashSet<Structure*>::const_iterator end = liveStructureSet.end();
+    for (HashSet<Structure*>::const_iterator it = liveStructureSet.begin(); it != end; ++it) {
+        Structure* structure = *it;
+        if (structure->m_usingSingleTransitionSlot) {
+            if (!structure->m_transitions.singleTransition)
+                ++numberLeaf;
+            else
+                ++numberUsingSingleSlot;
+
+           if (!structure->m_previous && !structure->m_transitions.singleTransition)
+                ++numberSingletons;
+        }
+
+        if (structure->m_propertyTable) {
+            ++numberWithPropertyMaps;
+            totalPropertyMapsSize += PropertyMapHashTable::allocationSize(structure->m_propertyTable->size);
+            if (structure->m_propertyTable->deletedOffsets)
+                totalPropertyMapsSize += (structure->m_propertyTable->deletedOffsets->capacity() * sizeof(unsigned)); 
+        }
+    }
+
+    printf("Number of live Structures: %d\n", liveStructureSet.size());
+    printf("Number of Structures using the single item optimization for transition map: %d\n", numberUsingSingleSlot);
+    printf("Number of Structures that are leaf nodes: %d\n", numberLeaf);
+    printf("Number of Structures that singletons: %d\n", numberSingletons);
+    printf("Number of Structures with PropertyMaps: %d\n", numberWithPropertyMaps);
+
+    printf("Size of a single Structures: %d\n", static_cast<unsigned>(sizeof(Structure)));
+    printf("Size of sum of all property maps: %d\n", totalPropertyMapsSize);
+    printf("Size of average of all property maps: %f\n", static_cast<double>(totalPropertyMapsSize) / static_cast<double>(liveStructureSet.size()));
+#else
+    printf("Dumping Structure statistics is not enabled.\n");
+#endif
+}
+
+Structure::Structure(JSValuePtr prototype, const TypeInfo& typeInfo)
+    : m_typeInfo(typeInfo)
+    , m_prototype(prototype)
+    , m_cachedPrototypeChain(0)
+    , m_previous(0)
+    , m_nameInPrevious(0)
+    , m_propertyTable(0)
+    , m_propertyStorageCapacity(JSObject::inlineStorageCapacity)
+    , m_offset(noOffset)
+    , m_isDictionary(false)
+    , m_isPinnedPropertyTable(false)
+    , m_hasGetterSetterProperties(false)
+    , m_usingSingleTransitionSlot(true)
+    , m_attributesInPrevious(0)
+{
+    ASSERT(m_prototype);
+    ASSERT(m_prototype.isObject() || m_prototype.isNull());
+
+    m_transitions.singleTransition = 0;
+
+#ifndef NDEBUG
+#if ENABLE(JSC_MULTIPLE_THREADS)
+    MutexLocker protect(ignoreSetMutex);
+#endif
+    if (shouldIgnoreLeaks)
+        ignoreSet.add(this);
+    else
+        structureCounter.increment();
+#endif
+
+#if DUMP_STRUCTURE_ID_STATISTICS
+    liveStructureSet.add(this);
+#endif
+}
+
+Structure::~Structure()
+{
+    if (m_previous) {
+        if (m_previous->m_usingSingleTransitionSlot) {
+            m_previous->m_transitions.singleTransition = 0;
+        } else {
+            ASSERT(m_previous->m_transitions.table->contains(make_pair(m_nameInPrevious.get(), m_attributesInPrevious)));
+            m_previous->m_transitions.table->remove(make_pair(m_nameInPrevious.get(), m_attributesInPrevious));
+        }
+    }
+
+    if (m_cachedPropertyNameArrayData)
+        m_cachedPropertyNameArrayData->setCachedStructure(0);
+
+    if (!m_usingSingleTransitionSlot)
+        delete m_transitions.table;
+
+    if (m_propertyTable) {
+        unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;
+        for (unsigned i = 1; i <= entryCount; i++) {
+            if (UString::Rep* key = m_propertyTable->entries()[i].key)
+                key->deref();
+        }
+
+        delete m_propertyTable->deletedOffsets;
+        fastFree(m_propertyTable);
+    }
+
+#ifndef NDEBUG
+#if ENABLE(JSC_MULTIPLE_THREADS)
+    MutexLocker protect(ignoreSetMutex);
+#endif
+    HashSet<Structure*>::iterator it = ignoreSet.find(this);
+    if (it != ignoreSet.end())
+        ignoreSet.remove(it);
+    else
+        structureCounter.decrement();
+#endif
+
+#if DUMP_STRUCTURE_ID_STATISTICS
+    liveStructureSet.remove(this);
+#endif
+}
+
+void Structure::startIgnoringLeaks()
+{
+#ifndef NDEBUG
+    shouldIgnoreLeaks = true;
+#endif
+}
+
+void Structure::stopIgnoringLeaks()
+{
+#ifndef NDEBUG
+    shouldIgnoreLeaks = false;
+#endif
+}
+
+static bool isPowerOf2(unsigned v)
+{
+    // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html
+    
+    return !(v & (v - 1)) && v;
+}
+
+static unsigned nextPowerOf2(unsigned v)
+{
+    // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html
+    // Devised by Sean Anderson, Sepember 14, 2001
+
+    v--;
+    v |= v >> 1;
+    v |= v >> 2;
+    v |= v >> 4;
+    v |= v >> 8;
+    v |= v >> 16;
+    v++;
+
+    return v;
+}
+
+static unsigned sizeForKeyCount(size_t keyCount)
+{
+    if (keyCount == notFound)
+        return newTableSize;
+
+    if (keyCount < 8)
+        return newTableSize;
+
+    if (isPowerOf2(keyCount))
+        return keyCount * 4;
+
+    return nextPowerOf2(keyCount) * 2;
+}
+
+void Structure::materializePropertyMap()
+{
+    ASSERT(!m_propertyTable);
+
+    Vector<Structure*, 8> structures;
+    structures.append(this);
+
+    Structure* structure = this;
+
+    // Search for the last Structure with a property table. 
+    while ((structure = structure->previousID())) {
+        if (structure->m_isPinnedPropertyTable) {
+            ASSERT(structure->m_propertyTable);
+            ASSERT(!structure->m_previous);
+
+            m_propertyTable = structure->copyPropertyTable();
+            break;
+        }
+
+        structures.append(structure);
+    }
+
+    if (!m_propertyTable)
+        createPropertyMapHashTable(sizeForKeyCount(m_offset + 1));
+    else {
+        if (sizeForKeyCount(m_offset + 1) > m_propertyTable->size)
+            rehashPropertyMapHashTable(sizeForKeyCount(m_offset + 1)); // This could be made more efficient by combining with the copy above. 
+    }
+
+    for (ptrdiff_t i = structures.size() - 2; i >= 0; --i) {
+        structure = structures[i];
+        structure->m_nameInPrevious->ref();
+        PropertyMapEntry entry(structure->m_nameInPrevious.get(), structure->m_offset, structure->m_attributesInPrevious, ++m_propertyTable->lastIndexUsed); 
+        insertIntoPropertyMapHashTable(entry);
+    }
+}
+
+void Structure::getEnumerablePropertyNames(ExecState* exec, PropertyNameArray& propertyNames, JSObject* baseObject)
+{
+    bool shouldCache = propertyNames.cacheable() && !(propertyNames.size() || m_isDictionary);
+
+    if (shouldCache) {
+        if (m_cachedPropertyNameArrayData) {
+            if (structureChainsAreEqual(m_cachedPropertyNameArrayData->cachedPrototypeChain(), cachedPrototypeChain())) {
+                propertyNames.setData(m_cachedPropertyNameArrayData);
+                return;
+            }
+        }
+        propertyNames.setCacheable(false);
+    }
+
+    getEnumerablePropertyNamesInternal(propertyNames);
+
+    // Add properties from the static hashtables of properties
+    for (const ClassInfo* info = baseObject->classInfo(); info; info = info->parentClass) {
+        const HashTable* table = info->propHashTable(exec);
+        if (!table)
+            continue;
+        table->initializeIfNeeded(exec);
+        ASSERT(table->table);
+#if ENABLE(PERFECT_HASH_SIZE)
+        int hashSizeMask = table->hashSizeMask;
+#else
+        int hashSizeMask = table->compactSize - 1;
+#endif
+        const HashEntry* entry = table->table;
+        for (int i = 0; i <= hashSizeMask; ++i, ++entry) {
+            if (entry->key() && !(entry->attributes() & DontEnum))
+                propertyNames.add(entry->key());
+        }
+    }
+
+    if (m_prototype.isObject())
+        asObject(m_prototype)->getPropertyNames(exec, propertyNames);
+
+    if (shouldCache) {
+        if (m_cachedPropertyNameArrayData)
+            m_cachedPropertyNameArrayData->setCachedStructure(0);
+
+        m_cachedPropertyNameArrayData = propertyNames.data();
+
+        StructureChain* chain = cachedPrototypeChain();
+        if (!chain)
+            chain = createCachedPrototypeChain();
+        m_cachedPropertyNameArrayData->setCachedPrototypeChain(chain);
+        m_cachedPropertyNameArrayData->setCachedStructure(this);
+    }
+}
+
+void Structure::clearEnumerationCache()
+{
+    if (m_cachedPropertyNameArrayData)
+        m_cachedPropertyNameArrayData->setCachedStructure(0);
+    m_cachedPropertyNameArrayData.clear();
+}
+
+void Structure::growPropertyStorageCapacity()
+{
+    if (m_propertyStorageCapacity == JSObject::inlineStorageCapacity)
+        m_propertyStorageCapacity = JSObject::nonInlineBaseStorageCapacity;
+    else
+        m_propertyStorageCapacity *= 2;
+}
+
+PassRefPtr<Structure> Structure::addPropertyTransitionToExistingStructure(Structure* structure, const Identifier& propertyName, unsigned attributes, size_t& offset)
+{
+    ASSERT(!structure->m_isDictionary);
+    ASSERT(structure->typeInfo().type() == ObjectType);
+
+    if (structure->m_usingSingleTransitionSlot) {
+        Structure* existingTransition = structure->m_transitions.singleTransition;
+        if (existingTransition && existingTransition->m_nameInPrevious.get() == propertyName.ustring().rep() && existingTransition->m_attributesInPrevious == attributes) {
+            ASSERT(structure->m_transitions.singleTransition->m_offset != noOffset);
+            offset = structure->m_transitions.singleTransition->m_offset;
+            return existingTransition;
+        }
+    } else {
+        if (Structure* existingTransition = structure->m_transitions.table->get(make_pair(propertyName.ustring().rep(), attributes))) {
+            ASSERT(existingTransition->m_offset != noOffset);
+            offset = existingTransition->m_offset;
+            return existingTransition;
+        }
+    }
+
+    return 0;
+}
+
+PassRefPtr<Structure> Structure::addPropertyTransition(Structure* structure, const Identifier& propertyName, unsigned attributes, size_t& offset)
+{
+    ASSERT(!structure->m_isDictionary);
+    ASSERT(structure->typeInfo().type() == ObjectType);
+    ASSERT(!Structure::addPropertyTransitionToExistingStructure(structure, propertyName, attributes, offset));
+
+    if (structure->transitionCount() > s_maxTransitionLength) {
+        RefPtr<Structure> transition = toDictionaryTransition(structure);
+        offset = transition->put(propertyName, attributes);
+        if (transition->propertyStorageSize() > transition->propertyStorageCapacity())
+            transition->growPropertyStorageCapacity();
+        return transition.release();
+    }
+
+    RefPtr<Structure> transition = create(structure->m_prototype, structure->typeInfo());
+    transition->m_cachedPrototypeChain = structure->m_cachedPrototypeChain;
+    transition->m_previous = structure;
+    transition->m_nameInPrevious = propertyName.ustring().rep();
+    transition->m_attributesInPrevious = attributes;
+    transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;
+    transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties;
+
+    if (structure->m_propertyTable) {
+        if (structure->m_isPinnedPropertyTable)
+            transition->m_propertyTable = structure->copyPropertyTable();
+        else {
+            transition->m_propertyTable = structure->m_propertyTable;
+            structure->m_propertyTable = 0;
+        }
+    } else {
+        if (structure->m_previous)
+            transition->materializePropertyMap();
+        else
+            transition->createPropertyMapHashTable();
+    }
+
+    offset = transition->put(propertyName, attributes);
+    if (transition->propertyStorageSize() > transition->propertyStorageCapacity())
+        transition->growPropertyStorageCapacity();
+
+    transition->m_offset = offset;
+
+    if (structure->m_usingSingleTransitionSlot) {
+        if (!structure->m_transitions.singleTransition) {
+            structure->m_transitions.singleTransition = transition.get();
+            return transition.release();
+        }
+
+        Structure* existingTransition = structure->m_transitions.singleTransition;
+        structure->m_usingSingleTransitionSlot = false;
+        StructureTransitionTable* transitionTable = new StructureTransitionTable;
+        structure->m_transitions.table = transitionTable;
+        transitionTable->add(make_pair(existingTransition->m_nameInPrevious.get(), existingTransition->m_attributesInPrevious), existingTransition);
+    }
+    structure->m_transitions.table->add(make_pair(propertyName.ustring().rep(), attributes), transition.get());
+    return transition.release();
+}
+
+PassRefPtr<Structure> Structure::removePropertyTransition(Structure* structure, const Identifier& propertyName, size_t& offset)
+{
+    ASSERT(!structure->m_isDictionary);
+
+    RefPtr<Structure> transition = toDictionaryTransition(structure);
+
+    offset = transition->remove(propertyName);
+
+    return transition.release();
+}
+
+PassRefPtr<Structure> Structure::changePrototypeTransition(Structure* structure, JSValuePtr prototype)
+{
+    RefPtr<Structure> transition = create(prototype, structure->typeInfo());
+
+    transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;
+    transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties;
+
+    // Don't set m_offset, as one can not transition to this.
+
+    structure->materializePropertyMapIfNecessary();
+    transition->m_propertyTable = structure->copyPropertyTable();
+    transition->m_isPinnedPropertyTable = true;
+
+    return transition.release();
+}
+
+PassRefPtr<Structure> Structure::getterSetterTransition(Structure* structure)
+{
+    RefPtr<Structure> transition = create(structure->storedPrototype(), structure->typeInfo());
+    transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;
+    transition->m_hasGetterSetterProperties = transition->m_hasGetterSetterProperties;
+
+    // Don't set m_offset, as one can not transition to this.
+
+    structure->materializePropertyMapIfNecessary();
+    transition->m_propertyTable = structure->copyPropertyTable();
+    transition->m_isPinnedPropertyTable = true;
+
+    return transition.release();
+}
+
+PassRefPtr<Structure> Structure::toDictionaryTransition(Structure* structure)
+{
+    ASSERT(!structure->m_isDictionary);
+
+    RefPtr<Structure> transition = create(structure->m_prototype, structure->typeInfo());
+    transition->m_isDictionary = true;
+    transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;
+    transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties;
+
+    structure->materializePropertyMapIfNecessary();
+    transition->m_propertyTable = structure->copyPropertyTable();
+    transition->m_isPinnedPropertyTable = true;
+
+    return transition.release();
+}
+
+PassRefPtr<Structure> Structure::fromDictionaryTransition(Structure* structure)
+{
+    ASSERT(structure->m_isDictionary);
+
+    // Since dictionary Structures are not shared, and no opcodes specialize
+    // for them, we don't need to allocate a new Structure when transitioning
+    // to non-dictionary status.
+
+    // FIMXE: We can make this more efficient by canonicalizing the Structure (draining the
+    // deleted offsets vector) before transitioning from dictionary. 
+    if (!structure->m_propertyTable || !structure->m_propertyTable->deletedOffsets || structure->m_propertyTable->deletedOffsets->isEmpty())
+        structure->m_isDictionary = false;
+
+    return structure;
+}
+
+size_t Structure::addPropertyWithoutTransition(const Identifier& propertyName, unsigned attributes)
+{
+    ASSERT(!m_transitions.singleTransition);
+
+    materializePropertyMapIfNecessary();
+
+    m_isPinnedPropertyTable = true;
+    size_t offset = put(propertyName, attributes);
+    if (propertyStorageSize() > propertyStorageCapacity())
+        growPropertyStorageCapacity();
+    clearEnumerationCache();
+    return offset;
+}
+
+size_t Structure::removePropertyWithoutTransition(const Identifier& propertyName)
+{
+    ASSERT(!m_transitions.singleTransition);
+    ASSERT(m_isDictionary);
+
+    materializePropertyMapIfNecessary();
+
+    m_isPinnedPropertyTable = true;
+    size_t offset = remove(propertyName);
+    clearEnumerationCache();
+    return offset;
+}
+
+StructureChain* Structure::createCachedPrototypeChain()
+{
+    ASSERT(typeInfo().type() == ObjectType);
+    ASSERT(!m_cachedPrototypeChain);
+
+    JSValuePtr prototype = storedPrototype();
+    if (!prototype.isCell())
+        return 0;
+
+    RefPtr<StructureChain> chain = StructureChain::create(asObject(prototype)->structure());
+    setCachedPrototypeChain(chain.release());
+    return cachedPrototypeChain();
+}
+
+#if DUMP_PROPERTYMAP_STATS
+
+static int numProbes;
+static int numCollisions;
+static int numRehashes;
+static int numRemoves;
+
+struct PropertyMapStatisticsExitLogger {
+    ~PropertyMapStatisticsExitLogger();
+};
+
+static PropertyMapStatisticsExitLogger logger;
+
+PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
+{
+    printf("\nJSC::PropertyMap statistics\n\n");
+    printf("%d probes\n", numProbes);
+    printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
+    printf("%d rehashes\n", numRehashes);
+    printf("%d removes\n", numRemoves);
+}
+
+#endif
+
+static const unsigned deletedSentinelIndex = 1;
+
+#if !DO_PROPERTYMAP_CONSTENCY_CHECK
+
+inline void Structure::checkConsistency()
+{
+}
+
+#endif
+
+PropertyMapHashTable* Structure::copyPropertyTable()
+{
+    if (!m_propertyTable)
+        return 0;
+
+    size_t tableSize = PropertyMapHashTable::allocationSize(m_propertyTable->size);
+    PropertyMapHashTable* newTable = static_cast<PropertyMapHashTable*>(fastMalloc(tableSize));
+    memcpy(newTable, m_propertyTable, tableSize);
+
+    unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;
+    for (unsigned i = 1; i <= entryCount; ++i) {
+        if (UString::Rep* key = newTable->entries()[i].key)
+            key->ref();
+    }
+
+    // Copy the deletedOffsets vector.
+    if (m_propertyTable->deletedOffsets)
+        newTable->deletedOffsets = new Vector<unsigned>(*m_propertyTable->deletedOffsets);
+
+    return newTable;
+}
+
+size_t Structure::get(const Identifier& propertyName, unsigned& attributes)
+{
+    ASSERT(!propertyName.isNull());
+
+    materializePropertyMapIfNecessary();
+    if (!m_propertyTable)
+        return notFound;
+
+    UString::Rep* rep = propertyName._ustring.rep();
+
+    unsigned i = rep->computedHash();
+
+#if DUMP_PROPERTYMAP_STATS
+    ++numProbes;
+#endif
+
+    unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
+    if (entryIndex == emptyEntryIndex)
+        return notFound;
+
+    if (rep == m_propertyTable->entries()[entryIndex - 1].key) {
+        attributes = m_propertyTable->entries()[entryIndex - 1].attributes;
+        return m_propertyTable->entries()[entryIndex - 1].offset;
+    }
+
+#if DUMP_PROPERTYMAP_STATS
+    ++numCollisions;
+#endif
+
+    unsigned k = 1 | doubleHash(rep->computedHash());
+
+    while (1) {
+        i += k;
+
+#if DUMP_PROPERTYMAP_STATS
+        ++numRehashes;
+#endif
+
+        entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
+        if (entryIndex == emptyEntryIndex)
+            return notFound;
+
+        if (rep == m_propertyTable->entries()[entryIndex - 1].key) {
+            attributes = m_propertyTable->entries()[entryIndex - 1].attributes;
+            return m_propertyTable->entries()[entryIndex - 1].offset;
+        }
+    }
+}
+
+size_t Structure::put(const Identifier& propertyName, unsigned attributes)
+{
+    ASSERT(!propertyName.isNull());
+    ASSERT(get(propertyName) == notFound);
+
+    checkConsistency();
+
+    UString::Rep* rep = propertyName._ustring.rep();
+
+    if (!m_propertyTable)
+        createPropertyMapHashTable();
+
+    // FIXME: Consider a fast case for tables with no deleted sentinels.
+
+    unsigned i = rep->computedHash();
+    unsigned k = 0;
+    bool foundDeletedElement = false;
+    unsigned deletedElementIndex = 0; // initialize to make the compiler happy
+
+#if DUMP_PROPERTYMAP_STATS
+    ++numProbes;
+#endif
+
+    while (1) {
+        unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
+        if (entryIndex == emptyEntryIndex)
+            break;
+
+        if (entryIndex == deletedSentinelIndex) {
+            // If we find a deleted-element sentinel, remember it for use later.
+            if (!foundDeletedElement) {
+                foundDeletedElement = true;
+                deletedElementIndex = i;
+            }
+        }
+
+        if (k == 0) {
+            k = 1 | doubleHash(rep->computedHash());
+#if DUMP_PROPERTYMAP_STATS
+            ++numCollisions;
+#endif
+        }
+
+        i += k;
+
+#if DUMP_PROPERTYMAP_STATS
+        ++numRehashes;
+#endif
+    }
+
+    // Figure out which entry to use.
+    unsigned entryIndex = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount + 2;
+    if (foundDeletedElement) {
+        i = deletedElementIndex;
+        --m_propertyTable->deletedSentinelCount;
+
+        // Since we're not making the table bigger, we can't use the entry one past
+        // the end that we were planning on using, so search backwards for the empty
+        // slot that we can use. We know it will be there because we did at least one
+        // deletion in the past that left an entry empty.
+        while (m_propertyTable->entries()[--entryIndex - 1].key) { }
+    }
+
+    // Create a new hash table entry.
+    m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = entryIndex;
+
+    // Create a new hash table entry.
+    rep->ref();
+    m_propertyTable->entries()[entryIndex - 1].key = rep;
+    m_propertyTable->entries()[entryIndex - 1].attributes = attributes;
+    m_propertyTable->entries()[entryIndex - 1].index = ++m_propertyTable->lastIndexUsed;
+
+    unsigned newOffset;
+    if (m_propertyTable->deletedOffsets && !m_propertyTable->deletedOffsets->isEmpty()) {
+        newOffset = m_propertyTable->deletedOffsets->last();
+        m_propertyTable->deletedOffsets->removeLast();
+    } else
+        newOffset = m_propertyTable->keyCount;
+    m_propertyTable->entries()[entryIndex - 1].offset = newOffset;
+
+    ++m_propertyTable->keyCount;
+
+    if ((m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount) * 2 >= m_propertyTable->size)
+        expandPropertyMapHashTable();
+
+    checkConsistency();
+    return newOffset;
+}
+
+size_t Structure::remove(const Identifier& propertyName)
+{
+    ASSERT(!propertyName.isNull());
+
+    checkConsistency();
+
+    UString::Rep* rep = propertyName._ustring.rep();
+
+    if (!m_propertyTable)
+        return notFound;
+
+#if DUMP_PROPERTYMAP_STATS
+    ++numProbes;
+    ++numRemoves;
+#endif
+
+    // Find the thing to remove.
+    unsigned i = rep->computedHash();
+    unsigned k = 0;
+    unsigned entryIndex;
+    UString::Rep* key = 0;
+    while (1) {
+        entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
+        if (entryIndex == emptyEntryIndex)
+            return notFound;
+
+        key = m_propertyTable->entries()[entryIndex - 1].key;
+        if (rep == key)
+            break;
+
+        if (k == 0) {
+            k = 1 | doubleHash(rep->computedHash());
+#if DUMP_PROPERTYMAP_STATS
+            ++numCollisions;
+#endif
+        }
+
+        i += k;
+
+#if DUMP_PROPERTYMAP_STATS
+        ++numRehashes;
+#endif
+    }
+
+    // Replace this one element with the deleted sentinel. Also clear out
+    // the entry so we can iterate all the entries as needed.
+    m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = deletedSentinelIndex;
+
+    size_t offset = m_propertyTable->entries()[entryIndex - 1].offset;
+
+    key->deref();
+    m_propertyTable->entries()[entryIndex - 1].key = 0;
+    m_propertyTable->entries()[entryIndex - 1].attributes = 0;
+    m_propertyTable->entries()[entryIndex - 1].offset = 0;
+
+    if (!m_propertyTable->deletedOffsets)
+        m_propertyTable->deletedOffsets = new Vector<unsigned>;
+    m_propertyTable->deletedOffsets->append(offset);
+
+    ASSERT(m_propertyTable->keyCount >= 1);
+    --m_propertyTable->keyCount;
+    ++m_propertyTable->deletedSentinelCount;
+
+    if (m_propertyTable->deletedSentinelCount * 4 >= m_propertyTable->size)
+        rehashPropertyMapHashTable();
+
+    checkConsistency();
+    return offset;
+}
+
+void Structure::insertIntoPropertyMapHashTable(const PropertyMapEntry& entry)
+{
+    ASSERT(m_propertyTable);
+
+    unsigned i = entry.key->computedHash();
+    unsigned k = 0;
+
+#if DUMP_PROPERTYMAP_STATS
+    ++numProbes;
+#endif
+
+    while (1) {
+        unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
+        if (entryIndex == emptyEntryIndex)
+            break;
+
+        if (k == 0) {
+            k = 1 | doubleHash(entry.key->computedHash());
+#if DUMP_PROPERTYMAP_STATS
+            ++numCollisions;
+#endif
+        }
+
+        i += k;
+
+#if DUMP_PROPERTYMAP_STATS
+        ++numRehashes;
+#endif
+    }
+
+    unsigned entryIndex = m_propertyTable->keyCount + 2;
+    m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = entryIndex;
+    m_propertyTable->entries()[entryIndex - 1] = entry;
+
+    ++m_propertyTable->keyCount;
+}
+
+void Structure::createPropertyMapHashTable()
+{
+    ASSERT(sizeForKeyCount(7) == newTableSize);
+    createPropertyMapHashTable(newTableSize);
+}
+
+void Structure::createPropertyMapHashTable(unsigned newTableSize)
+{
+    ASSERT(!m_propertyTable);
+    ASSERT(isPowerOf2(newTableSize));
+
+    checkConsistency();
+
+    m_propertyTable = static_cast<PropertyMapHashTable*>(fastZeroedMalloc(PropertyMapHashTable::allocationSize(newTableSize)));
+    m_propertyTable->size = newTableSize;
+    m_propertyTable->sizeMask = newTableSize - 1;
+
+    checkConsistency();
+}
+
+void Structure::expandPropertyMapHashTable()
+{
+    ASSERT(m_propertyTable);
+    rehashPropertyMapHashTable(m_propertyTable->size * 2);
+}
+
+void Structure::rehashPropertyMapHashTable()
+{
+    ASSERT(m_propertyTable);
+    ASSERT(m_propertyTable->size);
+    rehashPropertyMapHashTable(m_propertyTable->size);
+}
+
+void Structure::rehashPropertyMapHashTable(unsigned newTableSize)
+{
+    ASSERT(m_propertyTable);
+    ASSERT(isPowerOf2(newTableSize));
+
+    checkConsistency();
+
+    PropertyMapHashTable* oldTable = m_propertyTable;
+
+    m_propertyTable = static_cast<PropertyMapHashTable*>(fastZeroedMalloc(PropertyMapHashTable::allocationSize(newTableSize)));
+    m_propertyTable->size = newTableSize;
+    m_propertyTable->sizeMask = newTableSize - 1;
+
+    unsigned lastIndexUsed = 0;
+    unsigned entryCount = oldTable->keyCount + oldTable->deletedSentinelCount;
+    for (unsigned i = 1; i <= entryCount; ++i) {
+        if (oldTable->entries()[i].key) {
+            lastIndexUsed = max(oldTable->entries()[i].index, lastIndexUsed);
+            insertIntoPropertyMapHashTable(oldTable->entries()[i]);
+        }
+    }
+    m_propertyTable->lastIndexUsed = lastIndexUsed;
+    m_propertyTable->deletedOffsets = oldTable->deletedOffsets;
+
+    fastFree(oldTable);
+
+    checkConsistency();
+}
+
+static int comparePropertyMapEntryIndices(const void* a, const void* b)
+{
+    unsigned ia = static_cast<PropertyMapEntry* const*>(a)[0]->index;
+    unsigned ib = static_cast<PropertyMapEntry* const*>(b)[0]->index;
+    if (ia < ib)
+        return -1;
+    if (ia > ib)
+        return +1;
+    return 0;
+}
+
+void Structure::getEnumerablePropertyNamesInternal(PropertyNameArray& propertyNames)
+{
+    materializePropertyMapIfNecessary();
+    if (!m_propertyTable)
+        return;
+
+    if (m_propertyTable->keyCount < tinyMapThreshold) {
+        PropertyMapEntry* a[tinyMapThreshold];
+        int i = 0;
+        unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;
+        for (unsigned k = 1; k <= entryCount; k++) {
+            if (m_propertyTable->entries()[k].key && !(m_propertyTable->entries()[k].attributes & DontEnum)) {
+                PropertyMapEntry* value = &m_propertyTable->entries()[k];
+                int j;
+                for (j = i - 1; j >= 0 && a[j]->index > value->index; --j)
+                    a[j + 1] = a[j];
+                a[j + 1] = value;
+                ++i;
+            }
+        }
+        if (!propertyNames.size()) {
+            for (int k = 0; k < i; ++k)
+                propertyNames.addKnownUnique(a[k]->key);
+        } else {
+            for (int k = 0; k < i; ++k)
+                propertyNames.add(a[k]->key);
+        }
+
+        return;
+    }
+
+    // Allocate a buffer to use to sort the keys.
+    Vector<PropertyMapEntry*, smallMapThreshold> sortedEnumerables(m_propertyTable->keyCount);
+
+    // Get pointers to the enumerable entries in the buffer.
+    PropertyMapEntry** p = sortedEnumerables.data();
+    unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;
+    for (unsigned i = 1; i <= entryCount; i++) {
+        if (m_propertyTable->entries()[i].key && !(m_propertyTable->entries()[i].attributes & DontEnum))
+            *p++ = &m_propertyTable->entries()[i];
+    }
+
+    size_t enumerableCount = p - sortedEnumerables.data();
+    // Sort the entries by index.
+    qsort(sortedEnumerables.data(), enumerableCount, sizeof(PropertyMapEntry*), comparePropertyMapEntryIndices);
+    sortedEnumerables.resize(enumerableCount);
+
+    // Put the keys of the sorted entries into the list.
+    if (!propertyNames.size()) {
+        for (size_t i = 0; i < sortedEnumerables.size(); ++i)
+            propertyNames.addKnownUnique(sortedEnumerables[i]->key);
+    } else {
+        for (size_t i = 0; i < sortedEnumerables.size(); ++i)
+            propertyNames.add(sortedEnumerables[i]->key);
+    }
+}
+
+#if DO_PROPERTYMAP_CONSTENCY_CHECK
+
+void Structure::checkConsistency()
+{
+    if (!m_propertyTable)
+        return;
+
+    ASSERT(m_propertyTable->size >= newTableSize);
+    ASSERT(m_propertyTable->sizeMask);
+    ASSERT(m_propertyTable->size == m_propertyTable->sizeMask + 1);
+    ASSERT(!(m_propertyTable->size & m_propertyTable->sizeMask));
+
+    ASSERT(m_propertyTable->keyCount <= m_propertyTable->size / 2);
+    ASSERT(m_propertyTable->deletedSentinelCount <= m_propertyTable->size / 4);
+
+    ASSERT(m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount <= m_propertyTable->size / 2);
+
+    unsigned indexCount = 0;
+    unsigned deletedIndexCount = 0;
+    for (unsigned a = 0; a != m_propertyTable->size; ++a) {
+        unsigned entryIndex = m_propertyTable->entryIndices[a];
+        if (entryIndex == emptyEntryIndex)
+            continue;
+        if (entryIndex == deletedSentinelIndex) {
+            ++deletedIndexCount;
+            continue;
+        }
+        ASSERT(entryIndex > deletedSentinelIndex);
+        ASSERT(entryIndex - 1 <= m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount);
+        ++indexCount;
+
+        for (unsigned b = a + 1; b != m_propertyTable->size; ++b)
+            ASSERT(m_propertyTable->entryIndices[b] != entryIndex);
+    }
+    ASSERT(indexCount == m_propertyTable->keyCount);
+    ASSERT(deletedIndexCount == m_propertyTable->deletedSentinelCount);
+
+    ASSERT(m_propertyTable->entries()[0].key == 0);
+
+    unsigned nonEmptyEntryCount = 0;
+    for (unsigned c = 1; c <= m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; ++c) {
+        UString::Rep* rep = m_propertyTable->entries()[c].key;
+        if (!rep)
+            continue;
+        ++nonEmptyEntryCount;
+        unsigned i = rep->computedHash();
+        unsigned k = 0;
+        unsigned entryIndex;
+        while (1) {
+            entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
+            ASSERT(entryIndex != emptyEntryIndex);
+            if (rep == m_propertyTable->entries()[entryIndex - 1].key)
+                break;
+            if (k == 0)
+                k = 1 | doubleHash(rep->computedHash());
+            i += k;
+        }
+        ASSERT(entryIndex == c + 1);
+    }
+
+    ASSERT(nonEmptyEntryCount == m_propertyTable->keyCount);
+}
+
+#endif // DO_PROPERTYMAP_CONSTENCY_CHECK
+
+} // namespace JSC