Ignore:
Timestamp:
Oct 30, 2008, 5:12:50 PM (17 years ago)
Author:
[email protected]
Message:

2008-10-30 Sam Weinig <​[email protected]>

Reviewed by Cameron Zwarich and Geoffrey Garen.

Fix for ​https://bugs.webkit.org/show_bug.cgi?id=21989
Merge PropertyMap and StructureID

  • Move PropertyMap code into StructureID in preparation for lazily creating the map on gets.
  • Make remove with transition explicit by adding removePropertyTransition.
  • Make the put/remove without transition explicit.
  • Make cache invalidation part of put/remove without transition.

1% speedup on SunSpider; 0.5% speedup on v8 suite.

  • GNUmakefile.am:
  • JavaScriptCore.exp:
  • JavaScriptCore.pri:
  • JavaScriptCore.vcproj/JavaScriptCore/JavaScriptCore.vcproj:
  • JavaScriptCore.xcodeproj/project.pbxproj:
  • JavaScriptCoreSources.bkl:
  • kjs/AllInOneFile.cpp:
  • kjs/identifier.h:
  • runtime/JSObject.cpp: (JSC::JSObject::removeDirect):
  • runtime/JSObject.h: (JSC::JSObject::putDirect):
  • runtime/PropertyMap.cpp: Removed.
  • runtime/PropertyMap.h: Removed.
  • runtime/PropertyMapHashTable.h: Copied from runtime/PropertyMap.h.
  • runtime/StructureID.cpp: (JSC::StructureID::dumpStatistics): (JSC::StructureID::StructureID): (JSC::StructureID::~StructureID): (JSC::StructureID::getEnumerablePropertyNames): (JSC::StructureID::addPropertyTransition): (JSC::StructureID::removePropertyTransition): (JSC::StructureID::toDictionaryTransition): (JSC::StructureID::changePrototypeTransition): (JSC::StructureID::getterSetterTransition): (JSC::StructureID::addPropertyWithoutTransition): (JSC::StructureID::removePropertyWithoutTransition): (JSC::PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger): (JSC::StructureID::checkConsistency): (JSC::StructureID::copyPropertyTable): (JSC::StructureID::get): (JSC::StructureID::put): (JSC::StructureID::remove): (JSC::StructureID::insertIntoPropertyMapHashTable): (JSC::StructureID::expandPropertyMapHashTable): (JSC::StructureID::createPropertyMapHashTable): (JSC::StructureID::rehashPropertyMapHashTable): (JSC::comparePropertyMapEntryIndices): (JSC::StructureID::getEnumerablePropertyNamesInternal):
  • runtime/StructureID.h: (JSC::StructureID::propertyStorageSize): (JSC::StructureID::isEmpty): (JSC::StructureID::get):
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/runtime/StructureID.cpp

    r37989 r38016  
    3838#endif
    3939
     40#ifndef NDEBUG
     41#define DO_PROPERTYMAP_CONSTENCY_CHECK 0
     42#else
     43#define DO_PROPERTYMAP_CONSTENCY_CHECK 0
     44#endif
     45
    4046using namespace std;
     47using WTF::doubleHash;
    4148
    4249namespace 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.
     53static 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.
     57static const unsigned tinyMapThreshold = 20;
    4358
    4459#ifndef NDEBUG
    … …  
    7691        }
    7792
    78         totalPropertyMapsSize += structureID->m_propertyMap.propertyMapSize();
     93        if (structureID->m_propertyTable)
     94            totalPropertyMapsSize += PropertyMapHashTable::allocationSize(m_propertyTable->size);;
    7995    }
    8096
    … …  
    97113    , m_nameInPrevious(0)
    98114    , m_transitionCount(0)
     115    , m_propertyTable(0)
    99116    , m_propertyStorageCapacity(JSObject::inlineStorageCapacity)
    100117    , m_cachedTransistionOffset(WTF::notFound)
    … …  
    141158        delete m_transitions.table;
    142159
     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
    143169#ifndef NDEBUG
    144170#if ENABLE(JSC_MULTIPLE_THREADS)
    … …  
    185211    }
    186212
    187     m_propertyMap.getEnumerablePropertyNames(propertyNames);
     213    getEnumerablePropertyNamesInternal(propertyNames);
    188214
    189215    // Add properties from the static hashtables of properties
    … …  
    256282    if (structureID->m_transitionCount > s_maxTransitionLength) {
    257283        RefPtr<StructureID> transition = toDictionaryTransition(structureID);
    258         offset = transition->m_propertyMap.put(propertyName, attributes);
    259         if (transition->m_propertyMap.storageSize() > transition->propertyStorageCapacity())
     284        offset = transition->put(propertyName, attributes);
     285        if (transition->propertyStorageSize() > transition->propertyStorageCapacity())
    260286            transition->growPropertyStorageCapacity();
    261287        return transition.release();
    … …  
    268294    transition->m_attributesInPrevious = attributes;
    269295    transition->m_transitionCount = structureID->m_transitionCount + 1;
    270     transition->m_propertyMap = structureID->m_propertyMap;
     296    transition->m_propertyTable = structureID->copyPropertyTable();
     297    transition->m_deletedOffsets = structureID->m_deletedOffsets;
    271298    transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity;
    272299    transition->m_hasGetterSetterProperties = structureID->m_hasGetterSetterProperties;
    273300
    274     offset = transition->m_propertyMap.put(propertyName, attributes);
    275     if (transition->m_propertyMap.storageSize() > transition->propertyStorageCapacity())
     301    offset = transition->put(propertyName, attributes);
     302    if (transition->propertyStorageSize() > transition->propertyStorageCapacity())
    276303        transition->growPropertyStorageCapacity();
    277304
    … …  
    294321}
    295322
    296 PassRefPtr<StructureID> StructureID::toDictionaryTransition(StructureID* structureID)
     323PassRefPtr<StructureID> StructureID::removePropertyTransition(StructureID* structureID, const Identifier& propertyName, size_t& offset)
    297324{
    298325    ASSERT(!structureID->m_isDictionary);
    … …  
    300327    RefPtr<StructureID> transition = create(structureID->m_prototype, structureID->typeInfo());
    301328    transition->m_isDictionary = true;
    302     transition->m_propertyMap = structureID->m_propertyMap;
     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
     339PassRefPtr<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;
    303347    transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity;
    304348    transition->m_hasGetterSetterProperties = structureID->m_hasGetterSetterProperties;
    … …  
    321365    RefPtr<StructureID> transition = create(prototype, structureID->typeInfo());
    322366    transition->m_transitionCount = structureID->m_transitionCount + 1;
    323     transition->m_propertyMap = structureID->m_propertyMap;
     367    transition->m_propertyTable = structureID->copyPropertyTable();
     368    transition->m_deletedOffsets = structureID->m_deletedOffsets;
    324369    transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity;
    325370    transition->m_hasGetterSetterProperties = structureID->m_hasGetterSetterProperties;
    … …  
    331376    RefPtr<StructureID> transition = create(structureID->storedPrototype(), structureID->typeInfo());
    332377    transition->m_transitionCount = structureID->m_transitionCount + 1;
    333     transition->m_propertyMap = structureID->m_propertyMap;
     378    transition->m_propertyTable = structureID->copyPropertyTable();
     379    transition->m_deletedOffsets = structureID->m_deletedOffsets;
    334380    transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity;
    335381    transition->m_hasGetterSetterProperties = transition->m_hasGetterSetterProperties;
    … …  
    339385size_t StructureID::addPropertyWithoutTransition(const Identifier& propertyName, unsigned attributes)
    340386{
    341     size_t offset = m_propertyMap.put(propertyName, attributes);
    342     if (m_propertyMap.storageSize() > propertyStorageCapacity())
     387    size_t offset = put(propertyName, attributes);
     388    if (propertyStorageSize() > propertyStorageCapacity())
    343389        growPropertyStorageCapacity();
     390    clearEnumerationCache();
     391    return offset;
     392}
     393
     394size_t StructureID::removePropertyWithoutTransition(const Identifier& propertyName)
     395{
     396    size_t offset = remove(propertyName);
     397    clearEnumerationCache();
    344398    return offset;
    345399}
    … …  
    358412    return cachedPrototypeChain();
    359413}
     414
     415#if DUMP_PROPERTYMAP_STATS
     416
     417static int numProbes;
     418static int numCollisions;
     419static int numRehashes;
     420static int numRemoves;
     421
     422struct PropertyMapStatisticsExitLogger {
     423    ~PropertyMapStatisticsExitLogger();
     424};
     425
     426static PropertyMapStatisticsExitLogger logger;
     427
     428PropertyMapStatisticsExitLogger::~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
     439static const unsigned deletedSentinelIndex = 1;
     440
     441#if !DO_PROPERTYMAP_CONSTENCY_CHECK
     442
     443inline void StructureID::checkConsistency()
     444{
     445}   
     446
     447#endif
     448
     449PropertyMapHashTable* 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
     467size_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
     515size_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
     604size_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
     671void 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
     708void StructureID::expandPropertyMapHashTable()
     709{
     710    ASSERT(m_propertyTable);
     711    rehashPropertyMapHashTable(m_propertyTable->size * 2);
     712}
     713
     714void 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
     729void StructureID::rehashPropertyMapHashTable()
     730{
     731    ASSERT(m_propertyTable);
     732    ASSERT(m_propertyTable->size);
     733    rehashPropertyMapHashTable(m_propertyTable->size);
     734}
     735
     736void 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
     763static 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
     774void 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
     832void 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
    360896
    361897StructureIDChain::StructureIDChain(StructureID* structureID)
Note: See TracChangeset for help on using the changeset viewer.