diff options
Diffstat (limited to 'JavaScriptCore/runtime/StructureID.cpp')
-rw-r--r-- | JavaScriptCore/runtime/StructureID.cpp | 902 |
1 files changed, 0 insertions, 902 deletions
diff --git a/JavaScriptCore/runtime/StructureID.cpp b/JavaScriptCore/runtime/StructureID.cpp deleted file mode 100644 index 8333595..0000000 --- a/JavaScriptCore/runtime/StructureID.cpp +++ /dev/null @@ -1,902 +0,0 @@ -/* - * 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 |