cpython.git - https://github.com/python/cpython.git

diff options

author	Steve Dower <steve.dower@microsoft.com>	2015-07-03 19:21:29 (GMT)
committer	Steve Dower <steve.dower@microsoft.com>	2015-07-03 19:21:29 (GMT)
commit	0a34c496039a2bdc3d48c2a062bb0fbffcffa491 (patch)
tree	31e97208263b34ad6767062d4f193a84c2025eae /Python/importdl.h
parent	d48fb485d9d6597b1048f6131a28cb14979349af (diff)
parent	ac2bd5b1e8c5d8ee04c12ef6f34f1c9f1f8338c0 (diff)
download	cpython-0a34c496039a2bdc3d48c2a062bb0fbffcffa491.zip cpython-0a34c496039a2bdc3d48c2a062bb0fbffcffa491.tar.gz cpython-0a34c496039a2bdc3d48c2a062bb0fbffcffa491.tar.bz2

Fixes warnings when building python3.dll due to the .def file accumulating multiple copies of each line.

Adds shebang line to prepare_ssl so it will run with py.exe.

Diffstat (limited to 'Python/importdl.h')

0 files changed, 0 insertions, 0 deletions

/* * 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(); } 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 (JSImmediate::isImmediate(prototype)) 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


context:
space:
mode: