structure.cpp

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

            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;
}

#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;