structure.cpp

linux下开源浏览器WebKit的源码,市面上的很多商用浏览器都是移植自WebKit

    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::getEnumerableNamesFromPropertyTable(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);
    }
}

void Structure::getEnumerableNamesFromClassInfoTable(ExecState* exec, const ClassInfo* classInfo, PropertyNameArray& propertyNames)
{
    // Add properties from the static hashtables of properties
    for (; classInfo; classInfo = classInfo->parentClass) {
        const HashTable* table = classInfo->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 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