structure.cpp

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

/*
 * 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 = *(new Mutex);
#endif

static bool shouldIgnoreLeaks;
static HashSet<Structure*>& ignoreSet = *(new HashSet<Structure*>);
#endif

#if DUMP_STRUCTURE_ID_STATISTICS
static HashSet<Structure*>& liveStructureSet = *(new HashSet<Structure*>);
#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_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();
        }

        delete m_propertyTable->deletedOffsets;
        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.shouldCache() && !(propertyNames.size() || m_isDictionary);

    if (shouldCache && m_cachedPropertyNameArrayData) {
        if (m_cachedPropertyNameArrayData->cachedPrototypeChain() == prototypeChain(exec)) {
            propertyNames.setData(m_cachedPropertyNameArrayData);
            return;
        }
        clearEnumerationCache();
    }

    getEnumerableNamesFromPropertyTable(propertyNames);
    getEnumerableNamesFromClassInfoTable(exec, baseObject->classInfo(), propertyNames);

    if (m_prototype.isObject()) {
        propertyNames.setShouldCache(false); // No need for our prototypes to waste memory on caching, since they're not being enumerated directly.
        asObject(m_prototype)->getPropertyNames(exec, propertyNames);
    }

    if (shouldCache) {
        m_cachedPropertyNameArrayData = propertyNames.data();
        m_cachedPropertyNameArrayData->setCachedPrototypeChain(prototypeChain(exec));
        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;