diff options
author | The Android Open Source Project <initial-contribution@android.com> | 2009-03-03 19:30:52 -0800 |
---|---|---|
committer | The Android Open Source Project <initial-contribution@android.com> | 2009-03-03 19:30:52 -0800 |
commit | 8e35f3cfc7fba1d1c829dc557ebad6409cbe16a2 (patch) | |
tree | 11425ea0b299d6fb89c6d3618a22d97d5bf68d0f /JavaScriptCore/runtime/StructureID.cpp | |
parent | 648161bb0edfc3d43db63caed5cc5213bc6cb78f (diff) | |
download | external_webkit-8e35f3cfc7fba1d1c829dc557ebad6409cbe16a2.zip external_webkit-8e35f3cfc7fba1d1c829dc557ebad6409cbe16a2.tar.gz external_webkit-8e35f3cfc7fba1d1c829dc557ebad6409cbe16a2.tar.bz2 |
auto import from //depot/cupcake/@135843
Diffstat (limited to 'JavaScriptCore/runtime/StructureID.cpp')
-rw-r--r-- | JavaScriptCore/runtime/StructureID.cpp | 902 |
1 files changed, 902 insertions, 0 deletions
diff --git a/JavaScriptCore/runtime/StructureID.cpp b/JavaScriptCore/runtime/StructureID.cpp new file mode 100644 index 0000000..8333595 --- /dev/null +++ b/JavaScriptCore/runtime/StructureID.cpp @@ -0,0 +1,902 @@ +/* + * 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 "StructureID.h" + +#include "JSObject.h" +#include "PropertyNameArray.h" +#include "StructureIDChain.h" +#include "identifier.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 WTF::doubleHash; + +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; + +#ifndef NDEBUG +static WTF::RefCountedLeakCounter structureIDCounter("StructureID"); + +#if ENABLE(JSC_MULTIPLE_THREADS) +static Mutex ignoreSetMutex; +#endif + +static bool shouldIgnoreLeaks; +static HashSet<StructureID*> ignoreSet; +#endif + +#if DUMP_STRUCTURE_ID_STATISTICS +static HashSet<StructureID*> liveStructureIDSet; +#endif + +void StructureID::dumpStatistics() +{ +#if DUMP_STRUCTURE_ID_STATISTICS + unsigned numberLeaf = 0; + unsigned numberUsingSingleSlot = 0; + unsigned numberSingletons = 0; + unsigned totalPropertyMapsSize = 0; + + HashSet<StructureID*>::const_iterator end = liveStructureIDSet.end(); + for (HashSet<StructureID*>::const_iterator it = liveStructureIDSet.begin(); it != end; ++it) { + StructureID* structureID = *it; + if (structureID->m_usingSingleTransitionSlot) { + if (!structureID->m_transitions.singleTransition) + ++numberLeaf; + else + ++numberUsingSingleSlot; + + if (!structureID->m_previous && !structureID->m_transitions.singleTransition) + ++numberSingletons; + } + + if (structureID->m_propertyTable) + totalPropertyMapsSize += PropertyMapHashTable::allocationSize(structureID->m_propertyTable->size); + } + + printf("Number of live StructureIDs: %d\n", liveStructureIDSet.size()); + printf("Number of StructureIDs using the single item optimization for transition map: %d\n", numberUsingSingleSlot); + printf("Number of StructureIDs that are leaf nodes: %d\n", numberLeaf); + printf("Number of StructureIDs that singletons: %d\n", numberSingletons); + + printf("Size of a single StructureIDs: %d\n", static_cast<unsigned>(sizeof(StructureID))); + 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>(liveStructureIDSet.size())); +#else + printf("Dumping StructureID statistics is not enabled.\n"); +#endif +} + +StructureID::StructureID(JSValue* prototype, const TypeInfo& typeInfo) + : m_typeInfo(typeInfo) + , m_prototype(prototype) + , m_cachedPrototypeChain(0) + , m_previous(0) + , m_nameInPrevious(0) + , m_transitionCount(0) + , m_propertyTable(0) + , m_propertyStorageCapacity(JSObject::inlineStorageCapacity) + , m_cachedTransistionOffset(WTF::notFound) + , m_isDictionary(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 + structureIDCounter.increment(); +#endif + +#if DUMP_STRUCTURE_ID_STATISTICS + liveStructureIDSet.add(this); +#endif +} + +StructureID::~StructureID() +{ + 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, m_attributesInPrevious))); + m_previous->m_transitions.table->remove(make_pair(m_nameInPrevious, m_attributesInPrevious)); + } + } + + if (m_cachedPropertyNameArrayData) + m_cachedPropertyNameArrayData->setCachedStructureID(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(); + } + fastFree(m_propertyTable); + } + +#ifndef NDEBUG +#if ENABLE(JSC_MULTIPLE_THREADS) + MutexLocker protect(ignoreSetMutex); +#endif + HashSet<StructureID*>::iterator it = ignoreSet.find(this); + if (it != ignoreSet.end()) + ignoreSet.remove(it); + else + structureIDCounter.decrement(); +#endif + +#if DUMP_STRUCTURE_ID_STATISTICS + liveStructureIDSet.remove(this); +#endif +} + +void StructureID::startIgnoringLeaks() +{ +#ifndef NDEBUG + shouldIgnoreLeaks = true; +#endif +} + +void StructureID::stopIgnoringLeaks() +{ +#ifndef NDEBUG + shouldIgnoreLeaks = false; +#endif +} + +void StructureID::getEnumerablePropertyNames(ExecState* exec, PropertyNameArray& propertyNames, JSObject* baseObject) +{ + bool shouldCache = propertyNames.cacheable() && !(propertyNames.size() || m_isDictionary); + + if (shouldCache) { + if (m_cachedPropertyNameArrayData) { + if (structureIDChainsAreEqual(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); + int hashSizeMask = table->hashSizeMask; + 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->setCachedStructureID(0); + + m_cachedPropertyNameArrayData = propertyNames.data(); + + StructureIDChain* chain = cachedPrototypeChain(); + if (!chain) + chain = createCachedPrototypeChain(); + m_cachedPropertyNameArrayData->setCachedPrototypeChain(chain); + m_cachedPropertyNameArrayData->setCachedStructureID(this); + } +} + +void StructureID::clearEnumerationCache() +{ + if (m_cachedPropertyNameArrayData) + m_cachedPropertyNameArrayData->setCachedStructureID(0); + m_cachedPropertyNameArrayData.clear(); +} + +void StructureID::growPropertyStorageCapacity() +{ + if (m_propertyStorageCapacity == JSObject::inlineStorageCapacity) + m_propertyStorageCapacity = JSObject::nonInlineBaseStorageCapacity; + else + m_propertyStorageCapacity *= 2; +} + +PassRefPtr<StructureID> StructureID::addPropertyTransition(StructureID* structureID, const Identifier& propertyName, unsigned attributes, size_t& offset) +{ + ASSERT(!structureID->m_isDictionary); + ASSERT(structureID->typeInfo().type() == ObjectType); + + if (structureID->m_usingSingleTransitionSlot) { + StructureID* existingTransition = structureID->m_transitions.singleTransition; + if (existingTransition && existingTransition->m_nameInPrevious == propertyName.ustring().rep() && existingTransition->m_attributesInPrevious == attributes) { + offset = structureID->m_transitions.singleTransition->cachedTransistionOffset(); + ASSERT(offset != WTF::notFound); + return existingTransition; + } + } else { + if (StructureID* existingTransition = structureID->m_transitions.table->get(make_pair(propertyName.ustring().rep(), attributes))) { + offset = existingTransition->cachedTransistionOffset(); + ASSERT(offset != WTF::notFound); + return existingTransition; + } + } + + if (structureID->m_transitionCount > s_maxTransitionLength) { + RefPtr<StructureID> transition = toDictionaryTransition(structureID); + offset = transition->put(propertyName, attributes); + if (transition->propertyStorageSize() > transition->propertyStorageCapacity()) + transition->growPropertyStorageCapacity(); + return transition.release(); + } + + RefPtr<StructureID> transition = create(structureID->m_prototype, structureID->typeInfo()); + transition->m_cachedPrototypeChain = structureID->m_cachedPrototypeChain; + transition->m_previous = structureID; + transition->m_nameInPrevious = propertyName.ustring().rep(); + transition->m_attributesInPrevious = attributes; + transition->m_transitionCount = structureID->m_transitionCount + 1; + transition->m_propertyTable = structureID->copyPropertyTable(); + transition->m_deletedOffsets = structureID->m_deletedOffsets; + transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity; + transition->m_hasGetterSetterProperties = structureID->m_hasGetterSetterProperties; + + offset = transition->put(propertyName, attributes); + if (transition->propertyStorageSize() > transition->propertyStorageCapacity()) + transition->growPropertyStorageCapacity(); + + transition->setCachedTransistionOffset(offset); + + if (structureID->m_usingSingleTransitionSlot) { + if (!structureID->m_transitions.singleTransition) { + structureID->m_transitions.singleTransition = transition.get(); + return transition.release(); + } + + StructureID* existingTransition = structureID->m_transitions.singleTransition; + structureID->m_usingSingleTransitionSlot = false; + StructureIDTransitionTable* transitionTable = new StructureIDTransitionTable; + structureID->m_transitions.table = transitionTable; + transitionTable->add(make_pair(existingTransition->m_nameInPrevious, existingTransition->m_attributesInPrevious), existingTransition); + } + structureID->m_transitions.table->add(make_pair(propertyName.ustring().rep(), attributes), transition.get()); + return transition.release(); +} + +PassRefPtr<StructureID> StructureID::removePropertyTransition(StructureID* structureID, const Identifier& propertyName, size_t& offset) +{ + ASSERT(!structureID->m_isDictionary); + + RefPtr<StructureID> transition = create(structureID->m_prototype, structureID->typeInfo()); + transition->m_isDictionary = true; + transition->m_propertyTable = structureID->copyPropertyTable(); + transition->m_deletedOffsets = structureID->m_deletedOffsets; + transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity; + transition->m_hasGetterSetterProperties = structureID->m_hasGetterSetterProperties; + + offset = transition->remove(propertyName); + + return transition.release(); +} + +PassRefPtr<StructureID> StructureID::toDictionaryTransition(StructureID* structureID) +{ + ASSERT(!structureID->m_isDictionary); + + RefPtr<StructureID> transition = create(structureID->m_prototype, structureID->typeInfo()); + transition->m_isDictionary = true; + transition->m_propertyTable = structureID->copyPropertyTable(); + transition->m_deletedOffsets = structureID->m_deletedOffsets; + transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity; + transition->m_hasGetterSetterProperties = structureID->m_hasGetterSetterProperties; + return transition.release(); +} + +PassRefPtr<StructureID> StructureID::fromDictionaryTransition(StructureID* structureID) +{ + ASSERT(structureID->m_isDictionary); + + // Since dictionary StructureIDs are not shared, and no opcodes specialize + // for them, we don't need to allocate a new StructureID when transitioning + // to non-dictionary status. + structureID->m_isDictionary = false; + return structureID; +} + +PassRefPtr<StructureID> StructureID::changePrototypeTransition(StructureID* structureID, JSValue* prototype) +{ + RefPtr<StructureID> transition = create(prototype, structureID->typeInfo()); + transition->m_transitionCount = structureID->m_transitionCount + 1; + transition->m_propertyTable = structureID->copyPropertyTable(); + transition->m_deletedOffsets = structureID->m_deletedOffsets; + transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity; + transition->m_hasGetterSetterProperties = structureID->m_hasGetterSetterProperties; + return transition.release(); +} + +PassRefPtr<StructureID> StructureID::getterSetterTransition(StructureID* structureID) +{ + RefPtr<StructureID> transition = create(structureID->storedPrototype(), structureID->typeInfo()); + transition->m_transitionCount = structureID->m_transitionCount + 1; + transition->m_propertyTable = structureID->copyPropertyTable(); + transition->m_deletedOffsets = structureID->m_deletedOffsets; + transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity; + transition->m_hasGetterSetterProperties = transition->m_hasGetterSetterProperties; + return transition.release(); +} + +size_t StructureID::addPropertyWithoutTransition(const Identifier& propertyName, unsigned attributes) +{ + size_t offset = put(propertyName, attributes); + if (propertyStorageSize() > propertyStorageCapacity()) + growPropertyStorageCapacity(); + clearEnumerationCache(); + return offset; +} + +size_t StructureID::removePropertyWithoutTransition(const Identifier& propertyName) +{ + size_t offset = remove(propertyName); + clearEnumerationCache(); + return offset; +} + +StructureIDChain* StructureID::createCachedPrototypeChain() +{ + ASSERT(typeInfo().type() == ObjectType); + ASSERT(!m_cachedPrototypeChain); + + JSValue* prototype = storedPrototype(); + if (JSImmediate::isImmediate(prototype)) + return 0; + + RefPtr<StructureIDChain> chain = StructureIDChain::create(asObject(prototype)->structureID()); + 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 StructureID::checkConsistency() +{ +} + +#endif + +PropertyMapHashTable* StructureID::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(); + } + + return newTable; +} + +size_t StructureID::get(const Identifier& propertyName, unsigned& attributes) const +{ + ASSERT(!propertyName.isNull()); + + if (!m_propertyTable) + return WTF::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 WTF::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 WTF::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 StructureID::put(const Identifier& propertyName, unsigned attributes) +{ + ASSERT(!propertyName.isNull()); + ASSERT(get(propertyName) == WTF::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_deletedOffsets.isEmpty()) { + newOffset = m_deletedOffsets.last(); + m_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 StructureID::remove(const Identifier& propertyName) +{ + ASSERT(!propertyName.isNull()); + + checkConsistency(); + + UString::Rep* rep = propertyName._ustring.rep(); + + if (!m_propertyTable) + return WTF::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 WTF::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; + m_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 StructureID::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 StructureID::expandPropertyMapHashTable() +{ + ASSERT(m_propertyTable); + rehashPropertyMapHashTable(m_propertyTable->size * 2); +} + +void StructureID::createPropertyMapHashTable() +{ + const unsigned newTableSize = 16; + + ASSERT(!m_propertyTable); + + checkConsistency(); + + m_propertyTable = static_cast<PropertyMapHashTable*>(fastZeroedMalloc(PropertyMapHashTable::allocationSize(newTableSize))); + m_propertyTable->size = newTableSize; + m_propertyTable->sizeMask = newTableSize - 1; + + checkConsistency(); +} + +void StructureID::rehashPropertyMapHashTable() +{ + ASSERT(m_propertyTable); + ASSERT(m_propertyTable->size); + rehashPropertyMapHashTable(m_propertyTable->size); +} + +void StructureID::rehashPropertyMapHashTable(unsigned newTableSize) +{ + ASSERT(m_propertyTable); + + 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; + + 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 StructureID::getEnumerablePropertyNamesInternal(PropertyNameArray& propertyNames) const +{ + 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 StructureID::checkConsistency() +{ + if (!m_propertyTable) + return; + + ASSERT(m_propertyTable->size >= 16); + 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 |