property_map.cpp

khtml在gtk上的移植版本

    _table->entries[i].value = value;
    _table->entries[i].attributes = attributes;
    _table->entries[i].index = index;
}

void PropertyMap::expand()
{
    checkConsistency();
    
    Table *oldTable = _table;
    int oldTableSize = oldTable ? oldTable->size : 0;
    int oldTableKeyCount = oldTable ? oldTable->keyCount : 0;
    
    int newTableSize = oldTableSize ? oldTableSize * 2 : 16;
    _table = (Table *)calloc(1, sizeof(Table) + (newTableSize - 1) * sizeof(Entry) );
    _table->size = newTableSize;
    _table->sizeMask = newTableSize - 1;
    _table->keyCount = oldTableKeyCount;

#if USE_SINGLE_ENTRY
    UString::Rep *key = _singleEntry.key;
    if (key) {
        insert(key, _singleEntry.value, _singleEntry.attributes, 0);
        _singleEntry.key = 0;
	// update the count, because single entries don't count towards
	// the table key count
	++_table->keyCount;
	assert(_table->keyCount == 1);
    }
#endif
    
    int lastIndexUsed = 0;
    for (int i = 0; i != oldTableSize; ++i) {
        Entry &entry = oldTable->entries[i];
        UString::Rep *key = entry.key;
        if (key) {
            // Don't copy deleted-element sentinels.
            if (key == &UString::Rep::null)
                key->deref();
            else {
                int index = entry.index;
                lastIndexUsed = MAX(index, lastIndexUsed);
                insert(key, entry.value, entry.attributes, index);
            }
        }
    }
    _table->lastIndexUsed = lastIndexUsed;

    free(oldTable);

    checkConsistency();
}

void PropertyMap::remove(const Identifier &name)
{
    assert(!name.isNull());
    
    checkConsistency();

    UString::Rep *rep = name._ustring.rep;

    UString::Rep *key;

    if (!_table) {
#if USE_SINGLE_ENTRY
        key = _singleEntry.key;
        if (rep == key) {
            key->deref();
            _singleEntry.key = 0;
            checkConsistency();
        }
#endif
        return;
    }

    // Find the thing to remove.
    unsigned h = rep->hash();
    int i = h & _table->sizeMask;
    int k = 0;
#if DUMP_STATISTICS
    ++numProbes;
    ++numRemoves;
    numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
#endif
    while ((key = _table->entries[i].key)) {
        if (rep == key)
            break;
        if (k == 0)
            k = 1 | (h % _table->sizeMask);
        i = (i + k) & _table->sizeMask;
#if DUMP_STATISTICS
        ++numRehashes;
#endif
    }
    if (!key)
        return;
    
    // Replace this one element with the deleted sentinel,
    // &UString::Rep::null; also set value to 0 and attributes to DontEnum
    // to help callers that iterate all keys not have to check for the sentinel.
    key->deref();
    key = &UString::Rep::null;
    key->ref();
    _table->entries[i].key = key;
    _table->entries[i].value = 0;
    _table->entries[i].attributes = DontEnum;
    assert(_table->keyCount >= 1);
    --_table->keyCount;
    
    checkConsistency();
}

void PropertyMap::mark() const
{
    if (!_table) {
#if USE_SINGLE_ENTRY
        if (_singleEntry.key) {
            ValueImp *v = _singleEntry.value;
            if (!v->marked())
                v->mark();
        }
#endif
        return;
    }

    for (int i = 0; i != _table->size; ++i) {
        UString::Rep *key = _table->entries[i].key;
        if (key) {
            ValueImp *v = _table->entries[i].value;
            // Check v against 0 to handle deleted elements
            // without comparing key to UString::Rep::null.
            if (v && !v->marked())
                v->mark();
        }
    }
}

static int comparePropertyMapEntryIndices(const void *a, const void *b)
{
    int ia = static_cast<PropertyMapHashTableEntry * const *>(a)[0]->index;
    int ib = static_cast<PropertyMapHashTableEntry * const *>(b)[0]->index;
    if (ia < ib)
        return -1;
    if (ia > ib)
        return +1;
    return 0;
}

void PropertyMap::addEnumerablesToReferenceList(ReferenceList &list, const Object &base) const
{
    if (!_table) {
#if USE_SINGLE_ENTRY
        UString::Rep *key = _singleEntry.key;
        if (key && !(_singleEntry.attributes & DontEnum))
            list.append(Reference(base, Identifier(key)));
#endif
        return;
    }

    // Allocate a buffer to use to sort the keys.
    Entry *fixedSizeBuffer[smallMapThreshold];
    Entry **sortedEnumerables;
    if (_table->keyCount <= smallMapThreshold)
        sortedEnumerables = fixedSizeBuffer;
    else
        sortedEnumerables = new Entry *[_table->keyCount];

    // Get pointers to the enumerable entries in the buffer.
    Entry **p = sortedEnumerables;
    for (int i = 0; i != _table->size; ++i) {
        Entry *e = &_table->entries[i];
        if (e->key && !(e->attributes & DontEnum))
            *p++ = e;
    }

    // Sort the entries by index.
    qsort(sortedEnumerables, p - sortedEnumerables, sizeof(sortedEnumerables[0]), comparePropertyMapEntryIndices);

    // Put the keys of the sorted entries into the reference list.
    Entry **q = sortedEnumerables;
    while (q != p)
        list.append(Reference(base, Identifier((*q++)->key)));

    // Deallocate the buffer.
    if (sortedEnumerables != fixedSizeBuffer)
        delete [] sortedEnumerables;
}

void PropertyMap::addSparseArrayPropertiesToReferenceList(ReferenceList &list, const Object &base) const
{
    if (!_table) {
#if USE_SINGLE_ENTRY
        UString::Rep *key = _singleEntry.key;
        if (key) {
            UString k(key);
            bool fitsInUInt32;
            k.toUInt32(&fitsInUInt32);
            if (fitsInUInt32)
                list.append(Reference(base, Identifier(key)));
        }
#endif
        return;
    }

    for (int i = 0; i != _table->size; ++i) {
        UString::Rep *key = _table->entries[i].key;
        if (key && key != &UString::Rep::null)
        {
            UString k(key);
            bool fitsInUInt32;
            k.toUInt32(&fitsInUInt32);
            if (fitsInUInt32)
                list.append(Reference(base, Identifier(key)));
        }
    }
}

void PropertyMap::save(SavedProperties &p) const
{
    int count = 0;

    if (!_table) {
#if USE_SINGLE_ENTRY
        if (_singleEntry.key && !(_singleEntry.attributes & (ReadOnly | Function)))
            ++count;
#endif
    } else {
        for (int i = 0; i != _table->size; ++i)
            if (_table->entries[i].key && !(_table->entries[i].attributes & (ReadOnly | Function)))
                ++count;
    }

    delete [] p._properties;

    p._count = count;

    if (count == 0) {
        p._properties = 0;
        return;
    }
    
    p._properties = new SavedProperty [count];
    
    SavedProperty *prop = p._properties;
    
    if (!_table) {
#if USE_SINGLE_ENTRY
        if (_singleEntry.key && !(_singleEntry.attributes & (ReadOnly | Function))) {
            prop->key = Identifier(_singleEntry.key);
            prop->value = Value(_singleEntry.value);
            prop->attributes = _singleEntry.attributes;
            ++prop;
        }
#endif
    } else {
        // Save in the right order so we don't lose the order.
        // Another possibility would be to save the indices.

        // Allocate a buffer to use to sort the keys.
        Entry *fixedSizeBuffer[smallMapThreshold];
        Entry **sortedEntries;
        if (count <= smallMapThreshold)
            sortedEntries = fixedSizeBuffer;
        else
            sortedEntries = new Entry *[count];

        // Get pointers to the entries in the buffer.
        Entry **p = sortedEntries;
        for (int i = 0; i != _table->size; ++i) {
            Entry *e = &_table->entries[i];
            if (e->key && !(e->attributes & (ReadOnly | Function)))
                *p++ = e;
        }
        assert(p - sortedEntries == count);

        // Sort the entries by index.
        qsort(sortedEntries, p - sortedEntries, sizeof(sortedEntries[0]), comparePropertyMapEntryIndices);

        // Put the sorted entries into the saved properties list.
        Entry **q = sortedEntries;
        while (q != p) {
            Entry *e = *q++;
            prop->key = Identifier(e->key);
            prop->value = Value(e->value);
            prop->attributes = e->attributes;
            ++prop;
        }

        // Deallocate the buffer.
        if (sortedEntries != fixedSizeBuffer)
            delete [] sortedEntries;
    }
}

void PropertyMap::restore(const SavedProperties &p)
{
    for (int i = 0; i != p._count; ++i)
        put(p._properties[i].key, p._properties[i].value.imp(), p._properties[i].attributes);
}

#if DO_CONSISTENCY_CHECK

void PropertyMap::checkConsistency()
{
    if (!_table)
        return;

    int count = 0;
    for (int j = 0; j != _table->size; ++j) {
        UString::Rep *rep = _table->entries[j].key;
        if (!rep || rep == &UString::Rep::null)
            continue;
        unsigned h = rep->hash();
        int i = h & _table->sizeMask;
	int k = 0;
        while (UString::Rep *key = _table->entries[i].key) {
            if (rep == key)
                break;
	    if (k == 0)
		k = 1 | (h % _table->sizeMask);
	    i = (i + k) & _table->sizeMask;
        }
        assert(i == j);
        count++;
    }
    assert(count == _table->keyCount);
    assert(_table->size >= 16);
    assert(_table->sizeMask);
    assert(_table->size == _table->sizeMask + 1);
}

#endif // DO_CONSISTENCY_CHECK

} // namespace KJS