Ignore:
Timestamp:
Oct 31, 2008, 12:53:20 PM (17 years ago)
Author:
[email protected]
Message:

2008-10-31 Cameron Zwarich <​[email protected]>

Reviewed by Darin Adler.

Bug 22005: Move StructureIDChain into its own file
<​https://bugs.webkit.org/show_bug.cgi?id=22005>

  • GNUmakefile.am:
  • JavaScriptCore.pri:
  • JavaScriptCore.vcproj/JavaScriptCore/JavaScriptCore.vcproj:
  • JavaScriptCore.xcodeproj/project.pbxproj:
  • JavaScriptCoreSources.bkl:
  • runtime/StructureID.cpp:
  • runtime/StructureID.h:
  • runtime/StructureIDChain.cpp: Copied from runtime/StructureID.cpp.
  • runtime/StructureIDChain.h: Copied from runtime/StructureID.h.
File:
1 copied

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/runtime/StructureIDChain.cpp

    r38044 r38046  
    2525
    2626#include "config.h"
    27 #include "StructureID.h"
     27#include "StructureIDChain.h"
    2828
    2929#include "JSObject.h"
    30 #include "PropertyNameArray.h"
    31 #include "identifier.h"
    32 #include "lookup.h"
    33 #include <wtf/RefCountedLeakCounter.h>
     30#include "StructureID.h"
    3431#include <wtf/RefPtr.h>
    3532
    36 #if ENABLE(JSC_MULTIPLE_THREADS)
    37 #include <wtf/Threading.h>
    38 #endif
    39 
    40 #ifndef NDEBUG
    41 #define DO_PROPERTYMAP_CONSTENCY_CHECK 0
    42 #else
    43 #define DO_PROPERTYMAP_CONSTENCY_CHECK 0
    44 #endif
    45 
    46 using namespace std;
    47 using WTF::doubleHash;
    48 
    4933namespace JSC {
    50 
    51 // Choose a number for the following so that most property maps are smaller,
    52 // but it's not going to blow out the stack to allocate this number of pointers.
    53 static const int smallMapThreshold = 1024;
    54 
    55 // The point at which the function call overhead of the qsort implementation
    56 // becomes small compared to the inefficiency of insertion sort.
    57 static const unsigned tinyMapThreshold = 20;
    58 
    59 #ifndef NDEBUG
    60 static WTF::RefCountedLeakCounter structureIDCounter("StructureID");
    61 
    62 #if ENABLE(JSC_MULTIPLE_THREADS)
    63 static Mutex ignoreSetMutex;
    64 #endif
    65 
    66 static bool shouldIgnoreLeaks;
    67 static HashSet<StructureID*> ignoreSet;
    68 #endif
    69 
    70 #if DUMP_STRUCTURE_ID_STATISTICS
    71 static HashSet<StructureID*> liveStructureIDSet;
    72 
    73 void StructureID::dumpStatistics()
    74 {
    75     unsigned numberLeaf = 0;
    76     unsigned numberUsingSingleSlot = 0;
    77     unsigned numberSingletons = 0;
    78     unsigned totalPropertyMapsSize = 0;
    79 
    80     HashSet<StructureID*>::const_iterator end = liveStructureIDSet.end();
    81     for (HashSet<StructureID*>::const_iterator it = liveStructureIDSet.begin(); it != end; ++it) {
    82         StructureID* structureID = *it;
    83         if (structureID->m_usingSingleTransitionSlot) {
    84             if (!structureID->m_transitions.singleTransition)
    85                 ++numberLeaf;
    86             else
    87                 ++numberUsingSingleSlot;
    88 
    89            if (!structureID->m_previous && !structureID->m_transitions.singleTransition)
    90                 ++numberSingletons;
    91         }
    92 
    93         if (structureID->m_propertyTable)
    94             totalPropertyMapsSize += PropertyMapHashTable::allocationSize(m_propertyTable->size);;
    95     }
    96 
    97     printf("Number of live StructureIDs: %d\n", liveStructureIDSet.size());
    98     printf("Number of StructureIDs using the single item optimization for transition map: %d\n", numberUsingSingleSlot);
    99     printf("Number of StructureIDs that are leaf nodes: %d\n", numberLeaf);
    100     printf("Number of StructureIDs that singletons: %d\n", numberSingletons);
    101 
    102     printf("Size of a single StructureIDs: %d\n", static_cast<unsigned>(sizeof(StructureID)));
    103     printf("Size of sum of all property maps: %d\n", totalPropertyMapsSize);
    104     printf("Size of average of all property maps: %f\n", static_cast<double>(totalPropertyMapsSize) / static_cast<double>(liveStructureIDSet.size()));
    105 }
    106 #endif
    107 
    108 StructureID::StructureID(JSValue* prototype, const TypeInfo& typeInfo)
    109     : m_typeInfo(typeInfo)
    110     , m_prototype(prototype)
    111     , m_cachedPrototypeChain(0)
    112     , m_previous(0)
    113     , m_nameInPrevious(0)
    114     , m_transitionCount(0)
    115     , m_propertyTable(0)
    116     , m_propertyStorageCapacity(JSObject::inlineStorageCapacity)
    117     , m_cachedTransistionOffset(WTF::notFound)
    118     , m_isDictionary(false)
    119     , m_hasGetterSetterProperties(false)
    120     , m_usingSingleTransitionSlot(true)
    121     , m_attributesInPrevious(0)
    122 {
    123     ASSERT(m_prototype);
    124     ASSERT(m_prototype->isObject() || m_prototype->isNull());
    125 
    126     m_transitions.singleTransition = 0;
    127 
    128 #ifndef NDEBUG
    129 #if ENABLE(JSC_MULTIPLE_THREADS)
    130     MutexLocker protect(ignoreSetMutex);
    131 #endif
    132     if (shouldIgnoreLeaks)
    133         ignoreSet.add(this);
    134     else
    135         structureIDCounter.increment();
    136 #endif
    137 
    138 #if DUMP_STRUCTURE_ID_STATISTICS
    139     liveStructureIDSet.add(this);
    140 #endif
    141 }
    142 
    143 StructureID::~StructureID()
    144 {
    145     if (m_previous) {
    146         if (m_previous->m_usingSingleTransitionSlot) {
    147             m_previous->m_transitions.singleTransition = 0;
    148         } else {
    149             ASSERT(m_previous->m_transitions.table->contains(make_pair(m_nameInPrevious, m_attributesInPrevious)));
    150             m_previous->m_transitions.table->remove(make_pair(m_nameInPrevious, m_attributesInPrevious));
    151         }
    152     }
    153 
    154     if (m_cachedPropertyNameArrayData)
    155         m_cachedPropertyNameArrayData->setCachedStructureID(0);
    156 
    157     if (!m_usingSingleTransitionSlot)
    158         delete m_transitions.table;
    159 
    160     if (m_propertyTable) {
    161         unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;
    162         for (unsigned i = 1; i <= entryCount; i++) {
    163             if (UString::Rep* key = m_propertyTable->entries()[i].key)
    164                 key->deref();
    165         }
    166         fastFree(m_propertyTable);
    167     }
    168 
    169 #ifndef NDEBUG
    170 #if ENABLE(JSC_MULTIPLE_THREADS)
    171     MutexLocker protect(ignoreSetMutex);
    172 #endif
    173     HashSet<StructureID*>::iterator it = ignoreSet.find(this);
    174     if (it != ignoreSet.end())
    175         ignoreSet.remove(it);
    176     else
    177         structureIDCounter.decrement();
    178 #endif
    179 
    180 #if DUMP_STRUCTURE_ID_STATISTICS
    181     liveStructureIDSet.remove(this);
    182 #endif
    183 }
    184 
    185 void StructureID::startIgnoringLeaks()
    186 {
    187 #ifndef NDEBUG
    188     shouldIgnoreLeaks = true;
    189 #endif
    190 }
    191 
    192 void StructureID::stopIgnoringLeaks()
    193 {
    194 #ifndef NDEBUG
    195     shouldIgnoreLeaks = false;
    196 #endif
    197 }
    198 
    199 void StructureID::getEnumerablePropertyNames(ExecState* exec, PropertyNameArray& propertyNames, JSObject* baseObject)
    200 {
    201     bool shouldCache = propertyNames.cacheable() && !(propertyNames.size() || m_isDictionary);
    202 
    203     if (shouldCache) {
    204         if (m_cachedPropertyNameArrayData) {
    205             if (structureIDChainsAreEqual(m_cachedPropertyNameArrayData->cachedPrototypeChain(), cachedPrototypeChain())) {
    206                 propertyNames.setData(m_cachedPropertyNameArrayData);
    207                 return;
    208             }
    209         }
    210         propertyNames.setCacheable(false);
    211     }
    212 
    213     getEnumerablePropertyNamesInternal(propertyNames);
    214 
    215     // Add properties from the static hashtables of properties
    216     for (const ClassInfo* info = baseObject->classInfo(); info; info = info->parentClass) {
    217         const HashTable* table = info->propHashTable(exec);
    218         if (!table)
    219             continue;
    220         table->initializeIfNeeded(exec);
    221         ASSERT(table->table);
    222         int hashSizeMask = table->hashSizeMask;
    223         const HashEntry* entry = table->table;
    224         for (int i = 0; i <= hashSizeMask; ++i, ++entry) {
    225             if (entry->key() && !(entry->attributes() & DontEnum))
    226                 propertyNames.add(entry->key());
    227         }
    228     }
    229 
    230     if (m_prototype->isObject())
    231         asObject(m_prototype)->getPropertyNames(exec, propertyNames);
    232 
    233     if (shouldCache) {
    234         if (m_cachedPropertyNameArrayData)
    235             m_cachedPropertyNameArrayData->setCachedStructureID(0);
    236 
    237         m_cachedPropertyNameArrayData = propertyNames.data();
    238 
    239         StructureIDChain* chain = cachedPrototypeChain();
    240         if (!chain)
    241             chain = createCachedPrototypeChain();
    242         m_cachedPropertyNameArrayData->setCachedPrototypeChain(chain);
    243         m_cachedPropertyNameArrayData->setCachedStructureID(this);
    244     }
    245 }
    246 
    247 void StructureID::clearEnumerationCache()
    248 {
    249     if (m_cachedPropertyNameArrayData)
    250         m_cachedPropertyNameArrayData->setCachedStructureID(0);
    251     m_cachedPropertyNameArrayData.clear();
    252 }
    253 
    254 void StructureID::growPropertyStorageCapacity()
    255 {
    256     if (m_propertyStorageCapacity == JSObject::inlineStorageCapacity)
    257         m_propertyStorageCapacity = JSObject::nonInlineBaseStorageCapacity;
    258     else
    259         m_propertyStorageCapacity *= 2;
    260 }
    261 
    262 PassRefPtr<StructureID> StructureID::addPropertyTransition(StructureID* structureID, const Identifier& propertyName, unsigned attributes, size_t& offset)
    263 {
    264     ASSERT(!structureID->m_isDictionary);
    265     ASSERT(structureID->typeInfo().type() == ObjectType);
    266 
    267     if (structureID->m_usingSingleTransitionSlot) {
    268         StructureID* existingTransition = structureID->m_transitions.singleTransition;
    269         if (existingTransition && existingTransition->m_nameInPrevious == propertyName.ustring().rep() && existingTransition->m_attributesInPrevious == attributes) {
    270             offset = structureID->m_transitions.singleTransition->cachedTransistionOffset();
    271             ASSERT(offset != WTF::notFound);
    272             return existingTransition;
    273         }
    274     } else {
    275         if (StructureID* existingTransition = structureID->m_transitions.table->get(make_pair(propertyName.ustring().rep(), attributes))) {
    276             offset = existingTransition->cachedTransistionOffset();
    277             ASSERT(offset != WTF::notFound);
    278             return existingTransition;
    279         }       
    280     }
    281 
    282     if (structureID->m_transitionCount > s_maxTransitionLength) {
    283         RefPtr<StructureID> transition = toDictionaryTransition(structureID);
    284         offset = transition->put(propertyName, attributes);
    285         if (transition->propertyStorageSize() > transition->propertyStorageCapacity())
    286             transition->growPropertyStorageCapacity();
    287         return transition.release();
    288     }
    289 
    290     RefPtr<StructureID> transition = create(structureID->m_prototype, structureID->typeInfo());
    291     transition->m_cachedPrototypeChain = structureID->m_cachedPrototypeChain;
    292     transition->m_previous = structureID;
    293     transition->m_nameInPrevious = propertyName.ustring().rep();
    294     transition->m_attributesInPrevious = attributes;
    295     transition->m_transitionCount = structureID->m_transitionCount + 1;
    296     transition->m_propertyTable = structureID->copyPropertyTable();
    297     transition->m_deletedOffsets = structureID->m_deletedOffsets;
    298     transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity;
    299     transition->m_hasGetterSetterProperties = structureID->m_hasGetterSetterProperties;
    300 
    301     offset = transition->put(propertyName, attributes);
    302     if (transition->propertyStorageSize() > transition->propertyStorageCapacity())
    303         transition->growPropertyStorageCapacity();
    304 
    305     transition->setCachedTransistionOffset(offset);
    306 
    307     if (structureID->m_usingSingleTransitionSlot) {
    308         if (!structureID->m_transitions.singleTransition) {
    309             structureID->m_transitions.singleTransition = transition.get();
    310             return transition.release();
    311         }
    312 
    313         StructureID* existingTransition = structureID->m_transitions.singleTransition;
    314         structureID->m_usingSingleTransitionSlot = false;
    315         StructureIDTransitionTable* transitionTable = new StructureIDTransitionTable;
    316         structureID->m_transitions.table = transitionTable;
    317         transitionTable->add(make_pair(existingTransition->m_nameInPrevious, existingTransition->m_attributesInPrevious), existingTransition);
    318     }
    319     structureID->m_transitions.table->add(make_pair(propertyName.ustring().rep(), attributes), transition.get());
    320     return transition.release();
    321 }
    322 
    323 PassRefPtr<StructureID> StructureID::removePropertyTransition(StructureID* structureID, const Identifier& propertyName, size_t& offset)
    324 {
    325     ASSERT(!structureID->m_isDictionary);
    326 
    327     RefPtr<StructureID> transition = create(structureID->m_prototype, structureID->typeInfo());
    328     transition->m_isDictionary = true;
    329     transition->m_propertyTable = structureID->copyPropertyTable();
    330     transition->m_deletedOffsets = structureID->m_deletedOffsets;
    331     transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity;
    332     transition->m_hasGetterSetterProperties = structureID->m_hasGetterSetterProperties;
    333 
    334     offset = transition->remove(propertyName);
    335 
    336     return transition.release();
    337 }
    338 
    339 PassRefPtr<StructureID> StructureID::toDictionaryTransition(StructureID* structureID)
    340 {
    341     ASSERT(!structureID->m_isDictionary);
    342 
    343     RefPtr<StructureID> transition = create(structureID->m_prototype, structureID->typeInfo());
    344     transition->m_isDictionary = true;
    345     transition->m_propertyTable = structureID->copyPropertyTable();
    346     transition->m_deletedOffsets = structureID->m_deletedOffsets;
    347     transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity;
    348     transition->m_hasGetterSetterProperties = structureID->m_hasGetterSetterProperties;
    349     return transition.release();
    350 }
    351 
    352 PassRefPtr<StructureID> StructureID::fromDictionaryTransition(StructureID* structureID)
    353 {
    354     ASSERT(structureID->m_isDictionary);
    355 
    356     // Since dictionary StructureIDs are not shared, and no opcodes specialize
    357     // for them, we don't need to allocate a new StructureID when transitioning
    358     // to non-dictionary status.
    359     structureID->m_isDictionary = false;
    360     return structureID;
    361 }
    362 
    363 PassRefPtr<StructureID> StructureID::changePrototypeTransition(StructureID* structureID, JSValue* prototype)
    364 {
    365     RefPtr<StructureID> transition = create(prototype, structureID->typeInfo());
    366     transition->m_transitionCount = structureID->m_transitionCount + 1;
    367     transition->m_propertyTable = structureID->copyPropertyTable();
    368     transition->m_deletedOffsets = structureID->m_deletedOffsets;
    369     transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity;
    370     transition->m_hasGetterSetterProperties = structureID->m_hasGetterSetterProperties;
    371     return transition.release();
    372 }
    373 
    374 PassRefPtr<StructureID> StructureID::getterSetterTransition(StructureID* structureID)
    375 {
    376     RefPtr<StructureID> transition = create(structureID->storedPrototype(), structureID->typeInfo());
    377     transition->m_transitionCount = structureID->m_transitionCount + 1;
    378     transition->m_propertyTable = structureID->copyPropertyTable();
    379     transition->m_deletedOffsets = structureID->m_deletedOffsets;
    380     transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity;
    381     transition->m_hasGetterSetterProperties = transition->m_hasGetterSetterProperties;
    382     return transition.release();
    383 }
    384 
    385 size_t StructureID::addPropertyWithoutTransition(const Identifier& propertyName, unsigned attributes)
    386 {
    387     size_t offset = put(propertyName, attributes);
    388     if (propertyStorageSize() > propertyStorageCapacity())
    389         growPropertyStorageCapacity();
    390     clearEnumerationCache();
    391     return offset;
    392 }
    393 
    394 size_t StructureID::removePropertyWithoutTransition(const Identifier& propertyName)
    395 {
    396     size_t offset = remove(propertyName);
    397     clearEnumerationCache();
    398     return offset;
    399 }
    400 
    401 StructureIDChain* StructureID::createCachedPrototypeChain()
    402 {
    403     ASSERT(typeInfo().type() == ObjectType);
    404     ASSERT(!m_cachedPrototypeChain);
    405 
    406     JSValue* prototype = storedPrototype();
    407     if (JSImmediate::isImmediate(prototype))
    408         return 0;
    409 
    410     RefPtr<StructureIDChain> chain = StructureIDChain::create(asObject(prototype)->structureID());
    411     setCachedPrototypeChain(chain.release());
    412     return cachedPrototypeChain();
    413 }
    414 
    415 #if DUMP_PROPERTYMAP_STATS
    416 
    417 static int numProbes;
    418 static int numCollisions;
    419 static int numRehashes;
    420 static int numRemoves;
    421 
    422 struct PropertyMapStatisticsExitLogger {
    423     ~PropertyMapStatisticsExitLogger();
    424 };
    425 
    426 static PropertyMapStatisticsExitLogger logger;
    427 
    428 PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
    429 {
    430     printf("\nJSC::PropertyMap statistics\n\n");
    431     printf("%d probes\n", numProbes);
    432     printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
    433     printf("%d rehashes\n", numRehashes);
    434     printf("%d removes\n", numRemoves);
    435 }
    436 
    437 #endif
    438 
    439 static const unsigned deletedSentinelIndex = 1;
    440 
    441 #if !DO_PROPERTYMAP_CONSTENCY_CHECK
    442 
    443 inline void StructureID::checkConsistency()
    444 {
    445 }   
    446 
    447 #endif
    448 
    449 PropertyMapHashTable* StructureID::copyPropertyTable()
    450 {
    451     if (!m_propertyTable)
    452         return 0;
    453 
    454     size_t tableSize = PropertyMapHashTable::allocationSize(m_propertyTable->size);
    455     PropertyMapHashTable* newTable = static_cast<PropertyMapHashTable*>(fastMalloc(tableSize));
    456     memcpy(newTable, m_propertyTable, tableSize);
    457 
    458     unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;
    459     for (unsigned i = 1; i <= entryCount; ++i) {
    460         if (UString::Rep* key = newTable->entries()[i].key)
    461             key->ref();
    462     }
    463 
    464     return newTable;
    465 }
    466 
    467 size_t StructureID::get(const Identifier& propertyName, unsigned& attributes) const
    468 {
    469     ASSERT(!propertyName.isNull());
    470 
    471     if (!m_propertyTable)
    472         return WTF::notFound;
    473 
    474     UString::Rep* rep = propertyName._ustring.rep();
    475 
    476     unsigned i = rep->computedHash();
    477 
    478 #if DUMP_PROPERTYMAP_STATS
    479     ++numProbes;
    480 #endif
    481 
    482     unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
    483     if (entryIndex == emptyEntryIndex)
    484         return WTF::notFound;
    485 
    486     if (rep == m_propertyTable->entries()[entryIndex - 1].key) {
    487         attributes = m_propertyTable->entries()[entryIndex - 1].attributes;
    488         return m_propertyTable->entries()[entryIndex - 1].offset;
    489     }
    490 
    491 #if DUMP_PROPERTYMAP_STATS
    492     ++numCollisions;
    493 #endif
    494 
    495     unsigned k = 1 | doubleHash(rep->computedHash());
    496 
    497     while (1) {
    498         i += k;
    499 
    500 #if DUMP_PROPERTYMAP_STATS
    501         ++numRehashes;
    502 #endif
    503 
    504         entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
    505         if (entryIndex == emptyEntryIndex)
    506             return WTF::notFound;
    507 
    508         if (rep == m_propertyTable->entries()[entryIndex - 1].key) {
    509             attributes = m_propertyTable->entries()[entryIndex - 1].attributes;
    510             return m_propertyTable->entries()[entryIndex - 1].offset;
    511         }
    512     }
    513 }
    514 
    515 size_t StructureID::put(const Identifier& propertyName, unsigned attributes)
    516 {
    517     ASSERT(!propertyName.isNull());
    518     ASSERT(get(propertyName) == WTF::notFound);
    519 
    520     checkConsistency();
    521 
    522     UString::Rep* rep = propertyName._ustring.rep();
    523 
    524     if (!m_propertyTable)
    525         createPropertyMapHashTable();
    526 
    527     // FIXME: Consider a fast case for tables with no deleted sentinels.
    528 
    529     unsigned i = rep->computedHash();
    530     unsigned k = 0;
    531     bool foundDeletedElement = false;
    532     unsigned deletedElementIndex = 0; // initialize to make the compiler happy
    533 
    534 #if DUMP_PROPERTYMAP_STATS
    535     ++numProbes;
    536 #endif
    537 
    538     while (1) {
    539         unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
    540         if (entryIndex == emptyEntryIndex)
    541             break;
    542 
    543         if (entryIndex == deletedSentinelIndex) {
    544             // If we find a deleted-element sentinel, remember it for use later.
    545             if (!foundDeletedElement) {
    546                 foundDeletedElement = true;
    547                 deletedElementIndex = i;
    548             }
    549         }
    550 
    551         if (k == 0) {
    552             k = 1 | doubleHash(rep->computedHash());
    553 #if DUMP_PROPERTYMAP_STATS
    554             ++numCollisions;
    555 #endif
    556         }
    557 
    558         i += k;
    559 
    560 #if DUMP_PROPERTYMAP_STATS
    561         ++numRehashes;
    562 #endif
    563     }
    564 
    565     // Figure out which entry to use.
    566     unsigned entryIndex = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount + 2;
    567     if (foundDeletedElement) {
    568         i = deletedElementIndex;
    569         --m_propertyTable->deletedSentinelCount;
    570 
    571         // Since we're not making the table bigger, we can't use the entry one past
    572         // the end that we were planning on using, so search backwards for the empty
    573         // slot that we can use. We know it will be there because we did at least one
    574         // deletion in the past that left an entry empty.
    575         while (m_propertyTable->entries()[--entryIndex - 1].key) { }
    576     }
    577 
    578     // Create a new hash table entry.
    579     m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = entryIndex;
    580 
    581     // Create a new hash table entry.
    582     rep->ref();
    583     m_propertyTable->entries()[entryIndex - 1].key = rep;
    584     m_propertyTable->entries()[entryIndex - 1].attributes = attributes;
    585     m_propertyTable->entries()[entryIndex - 1].index = ++m_propertyTable->lastIndexUsed;
    586 
    587     unsigned newOffset;
    588     if (!m_deletedOffsets.isEmpty()) {
    589         newOffset = m_deletedOffsets.last();
    590         m_deletedOffsets.removeLast();
    591     } else
    592         newOffset = m_propertyTable->keyCount;
    593     m_propertyTable->entries()[entryIndex - 1].offset = newOffset;
    594 
    595     ++m_propertyTable->keyCount;
    596 
    597     if ((m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount) * 2 >= m_propertyTable->size)
    598         expandPropertyMapHashTable();
    599 
    600     checkConsistency();
    601     return newOffset;
    602 }
    603 
    604 size_t StructureID::remove(const Identifier& propertyName)
    605 {
    606     ASSERT(!propertyName.isNull());
    607 
    608     checkConsistency();
    609 
    610     UString::Rep* rep = propertyName._ustring.rep();
    611 
    612     if (!m_propertyTable)
    613         return WTF::notFound;
    614 
    615 #if DUMP_PROPERTYMAP_STATS
    616     ++numProbes;
    617     ++numRemoves;
    618 #endif
    619 
    620     // Find the thing to remove.
    621     unsigned i = rep->computedHash();
    622     unsigned k = 0;
    623     unsigned entryIndex;
    624     UString::Rep* key = 0;
    625     while (1) {
    626         entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
    627         if (entryIndex == emptyEntryIndex)
    628             return WTF::notFound;
    629 
    630         key = m_propertyTable->entries()[entryIndex - 1].key;
    631         if (rep == key)
    632             break;
    633 
    634         if (k == 0) {
    635             k = 1 | doubleHash(rep->computedHash());
    636 #if DUMP_PROPERTYMAP_STATS
    637             ++numCollisions;
    638 #endif
    639         }
    640 
    641         i += k;
    642 
    643 #if DUMP_PROPERTYMAP_STATS
    644         ++numRehashes;
    645 #endif
    646     }
    647 
    648     // Replace this one element with the deleted sentinel. Also clear out
    649     // the entry so we can iterate all the entries as needed.
    650     m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = deletedSentinelIndex;
    651 
    652     size_t offset = m_propertyTable->entries()[entryIndex - 1].offset;
    653 
    654     key->deref();
    655     m_propertyTable->entries()[entryIndex - 1].key = 0;
    656     m_propertyTable->entries()[entryIndex - 1].attributes = 0;
    657     m_propertyTable->entries()[entryIndex - 1].offset = 0;
    658     m_deletedOffsets.append(offset);
    659 
    660     ASSERT(m_propertyTable->keyCount >= 1);
    661     --m_propertyTable->keyCount;
    662     ++m_propertyTable->deletedSentinelCount;
    663 
    664     if (m_propertyTable->deletedSentinelCount * 4 >= m_propertyTable->size)
    665         rehashPropertyMapHashTable();
    666 
    667     checkConsistency();
    668     return offset;
    669 }
    670 
    671 void StructureID::insertIntoPropertyMapHashTable(const PropertyMapEntry& entry)
    672 {
    673     ASSERT(m_propertyTable);
    674 
    675     unsigned i = entry.key->computedHash();
    676     unsigned k = 0;
    677 
    678 #if DUMP_PROPERTYMAP_STATS
    679     ++numProbes;
    680 #endif
    681 
    682     while (1) {
    683         unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
    684         if (entryIndex == emptyEntryIndex)
    685             break;
    686 
    687         if (k == 0) {
    688             k = 1 | doubleHash(entry.key->computedHash());
    689 #if DUMP_PROPERTYMAP_STATS
    690             ++numCollisions;
    691 #endif
    692         }
    693 
    694         i += k;
    695 
    696 #if DUMP_PROPERTYMAP_STATS
    697         ++numRehashes;
    698 #endif
    699     }
    700 
    701     unsigned entryIndex = m_propertyTable->keyCount + 2;
    702     m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = entryIndex;
    703     m_propertyTable->entries()[entryIndex - 1] = entry;
    704 
    705     ++m_propertyTable->keyCount;
    706 }
    707 
    708 void StructureID::expandPropertyMapHashTable()
    709 {
    710     ASSERT(m_propertyTable);
    711     rehashPropertyMapHashTable(m_propertyTable->size * 2);
    712 }
    713 
    714 void StructureID::createPropertyMapHashTable()
    715 {
    716     const unsigned newTableSize = 16;
    717 
    718     ASSERT(!m_propertyTable);
    719 
    720     checkConsistency();
    721 
    722     m_propertyTable = static_cast<PropertyMapHashTable*>(fastZeroedMalloc(PropertyMapHashTable::allocationSize(newTableSize)));
    723     m_propertyTable->size = newTableSize;
    724     m_propertyTable->sizeMask = newTableSize - 1;
    725 
    726     checkConsistency();
    727 }
    728 
    729 void StructureID::rehashPropertyMapHashTable()
    730 {
    731     ASSERT(m_propertyTable);
    732     ASSERT(m_propertyTable->size);
    733     rehashPropertyMapHashTable(m_propertyTable->size);
    734 }
    735 
    736 void StructureID::rehashPropertyMapHashTable(unsigned newTableSize)
    737 {
    738     ASSERT(m_propertyTable);
    739 
    740     checkConsistency();
    741 
    742     PropertyMapHashTable* oldTable = m_propertyTable;
    743 
    744     m_propertyTable = static_cast<PropertyMapHashTable*>(fastZeroedMalloc(PropertyMapHashTable::allocationSize(newTableSize)));
    745     m_propertyTable->size = newTableSize;
    746     m_propertyTable->sizeMask = newTableSize - 1;
    747 
    748     unsigned lastIndexUsed = 0;
    749     unsigned entryCount = oldTable->keyCount + oldTable->deletedSentinelCount;
    750     for (unsigned i = 1; i <= entryCount; ++i) {
    751         if (oldTable->entries()[i].key) {
    752             lastIndexUsed = max(oldTable->entries()[i].index, lastIndexUsed);
    753             insertIntoPropertyMapHashTable(oldTable->entries()[i]);
    754         }
    755     }
    756     m_propertyTable->lastIndexUsed = lastIndexUsed;
    757 
    758     fastFree(oldTable);
    759 
    760     checkConsistency();
    761 }
    762 
    763 static int comparePropertyMapEntryIndices(const void* a, const void* b)
    764 {
    765     unsigned ia = static_cast<PropertyMapEntry* const*>(a)[0]->index;
    766     unsigned ib = static_cast<PropertyMapEntry* const*>(b)[0]->index;
    767     if (ia < ib)
    768         return -1;
    769     if (ia > ib)
    770         return +1;
    771     return 0;
    772 }
    773 
    774 void StructureID::getEnumerablePropertyNamesInternal(PropertyNameArray& propertyNames) const
    775 {
    776     if (!m_propertyTable)
    777         return;
    778 
    779     if (m_propertyTable->keyCount < tinyMapThreshold) {
    780         PropertyMapEntry* a[tinyMapThreshold];
    781         int i = 0;
    782         unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;
    783         for (unsigned k = 1; k <= entryCount; k++) {
    784             if (m_propertyTable->entries()[k].key && !(m_propertyTable->entries()[k].attributes & DontEnum)) {
    785                 PropertyMapEntry* value = &m_propertyTable->entries()[k];
    786                 int j;
    787                 for (j = i - 1; j >= 0 && a[j]->index > value->index; --j)
    788                     a[j + 1] = a[j];
    789                 a[j + 1] = value;
    790                 ++i;
    791             }
    792         }
    793         if (!propertyNames.size()) {
    794             for (int k = 0; k < i; ++k)
    795                 propertyNames.addKnownUnique(a[k]->key);
    796         } else {
    797             for (int k = 0; k < i; ++k)
    798                 propertyNames.add(a[k]->key);
    799         }
    800 
    801         return;
    802     }
    803 
    804     // Allocate a buffer to use to sort the keys.
    805     Vector<PropertyMapEntry*, smallMapThreshold> sortedEnumerables(m_propertyTable->keyCount);
    806 
    807     // Get pointers to the enumerable entries in the buffer.
    808     PropertyMapEntry** p = sortedEnumerables.data();
    809     unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;
    810     for (unsigned i = 1; i <= entryCount; i++) {
    811         if (m_propertyTable->entries()[i].key && !(m_propertyTable->entries()[i].attributes & DontEnum))
    812             *p++ = &m_propertyTable->entries()[i];
    813     }
    814 
    815     size_t enumerableCount = p - sortedEnumerables.data();
    816     // Sort the entries by index.
    817     qsort(sortedEnumerables.data(), enumerableCount, sizeof(PropertyMapEntry*), comparePropertyMapEntryIndices);
    818     sortedEnumerables.resize(enumerableCount);
    819 
    820     // Put the keys of the sorted entries into the list.
    821     if (!propertyNames.size()) {
    822         for (size_t i = 0; i < sortedEnumerables.size(); ++i)
    823             propertyNames.addKnownUnique(sortedEnumerables[i]->key);
    824     } else {
    825         for (size_t i = 0; i < sortedEnumerables.size(); ++i)
    826             propertyNames.add(sortedEnumerables[i]->key);
    827     }
    828 }
    829 
    830 #if DO_PROPERTYMAP_CONSTENCY_CHECK
    831 
    832 void StructureID::checkConsistency()
    833 {
    834     if (!m_propertyTable)
    835         return;
    836 
    837     ASSERT(m_propertyTable->size >= 16);
    838     ASSERT(m_propertyTable->sizeMask);
    839     ASSERT(m_propertyTable->size == m_propertyTable->sizeMask + 1);
    840     ASSERT(!(m_propertyTable->size & m_propertyTable->sizeMask));
    841 
    842     ASSERT(m_propertyTable->keyCount <= m_propertyTable->size / 2);
    843     ASSERT(m_propertyTable->deletedSentinelCount <= m_propertyTable->size / 4);
    844 
    845     ASSERT(m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount <= m_propertyTable->size / 2);
    846 
    847     unsigned indexCount = 0;
    848     unsigned deletedIndexCount = 0;
    849     for (unsigned a = 0; a != m_propertyTable->size; ++a) {
    850         unsigned entryIndex = m_propertyTable->entryIndices[a];
    851         if (entryIndex == emptyEntryIndex)
    852             continue;
    853         if (entryIndex == deletedSentinelIndex) {
    854             ++deletedIndexCount;
    855             continue;
    856         }
    857         ASSERT(entryIndex > deletedSentinelIndex);
    858         ASSERT(entryIndex - 1 <= m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount);
    859         ++indexCount;
    860 
    861         for (unsigned b = a + 1; b != m_propertyTable->size; ++b)
    862             ASSERT(m_propertyTable->entryIndices[b] != entryIndex);
    863     }
    864     ASSERT(indexCount == m_propertyTable->keyCount);
    865     ASSERT(deletedIndexCount == m_propertyTable->deletedSentinelCount);
    866 
    867     ASSERT(m_propertyTable->entries()[0].key == 0);
    868 
    869     unsigned nonEmptyEntryCount = 0;
    870     for (unsigned c = 1; c <= m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; ++c) {
    871         UString::Rep* rep = m_propertyTable->entries()[c].key;
    872         if (!rep)
    873             continue;
    874         ++nonEmptyEntryCount;
    875         unsigned i = rep->computedHash();
    876         unsigned k = 0;
    877         unsigned entryIndex;
    878         while (1) {
    879             entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
    880             ASSERT(entryIndex != emptyEntryIndex);
    881             if (rep == m_propertyTable->entries()[entryIndex - 1].key)
    882                 break;
    883             if (k == 0)
    884                 k = 1 | doubleHash(rep->computedHash());
    885             i += k;
    886         }
    887         ASSERT(entryIndex == c + 1);
    888     }
    889 
    890     ASSERT(nonEmptyEntryCount == m_propertyTable->keyCount);
    891 }
    892 
    893 #endif // DO_PROPERTYMAP_CONSTENCY_CHECK
    894 
    895 // StructureIDChain
    89634
    89735StructureIDChain::StructureIDChain(StructureID* structureID)
Note: See TracChangeset for help on using the changeset viewer.