qv4estable.cpp

Go to the documentation of this file.

// Copyright (C) 2018 Crimson AS <info@crimson.no>
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
// Qt-Security score:significant
 
#include "qv4estable_p.h"
#include "qv4object_p.h"
 
using namespace QV4;
 
// The ES spec requires that Map/Set be implemented using a data structure that
// is a little different from most; it requires nonlinear access, and must also
// preserve the order of insertion of items in a deterministic way.
//
// This class implements those requirements, except for fast access: that
// will be addressed in a followup patch.
 
ESTable::ESTable()
    : m_capacity(8)
{
    m_keys = (Value*)malloc(m_capacity * sizeof(Value));
    m_values = (Value*)malloc(m_capacity * sizeof(Value));
    memset(m_keys, 0, m_capacity);
    memset(m_values, 0, m_capacity);
}
 
ESTable::~ESTable()
{
    free(m_keys);
    free(m_values);
    m_size = 0;
    m_capacity = 0;
    m_keys = nullptr;
    m_values = nullptr;
}
 
void ESTable::markObjects(MarkStack *s, bool isWeakMap)
{
    for (uint i = 0; i < m_size; ++i) {
        if (!isWeakMap)
            m_keys[i].mark(s);
        m_values[i].mark(s);
    }
}
 
// Pretends that there's nothing in the table. Doesn't actually free memory, as
// it will almost certainly be reused again anyway.
void ESTable::clear()
{
    m_size = 0;
 
    std::for_each(m_observers.begin(), m_observers.end(), [](ShiftObserver* ob){
        Q_ASSERT(ob);
        ob->pivot = ShiftObserver::OUT_OF_TABLE;
    });
}
 
// Update the table to contain \a value for a given \a key. The key is
// normalized, as required by the ES spec.
void ESTable::set(const Value &key, const Value &value)
{
    for (uint i = 0; i < m_size; ++i) {
        if (m_keys[i].sameValueZero(key)) {
            m_values[i] = value;
            return;
        }
    }
 
    if (m_capacity == m_size) {
        uint oldCap = m_capacity;
        m_capacity *= 2;
        m_keys = (Value*)realloc(m_keys, m_capacity * sizeof(Value));
        m_values = (Value*)realloc(m_values, m_capacity * sizeof(Value));
        memset(m_keys + oldCap, 0, m_capacity - oldCap);
        memset(m_values + oldCap, 0, m_capacity - oldCap);
    }
 
    Value nk = key;
    if (nk.isDouble()) {
        if (nk.doubleValue() == 0 && std::signbit(nk.doubleValue()))
            nk = Value::fromDouble(+0);
    }
 
    m_keys[m_size] = nk;
    m_values[m_size] = value;
 
    m_size++;
}
 
// Returns true if the table contains \a key, false otherwise.
bool ESTable::has(const Value &key) const
{
    for (uint i = 0; i < m_size; ++i) {
        if (m_keys[i].sameValueZero(key))
            return true;
    }
 
    return false;
}
 
// Fetches the value for the given \a key, and if \a hasValue is passed in,
// it is set depending on whether or not the given key was found.
ReturnedValue ESTable::get(const Value &key, bool *hasValue) const
{
    for (uint i = 0; i < m_size; ++i) {
        if (m_keys[i].sameValueZero(key)) {
            if (hasValue)
                *hasValue = true;
            return m_values[i].asReturnedValue();
        }
    }
 
    if (hasValue)
        *hasValue = false;
    return Encode::undefined();
}
 
// Removes the given \a key from the table
bool ESTable::remove(const Value &key)
{
    for (uint index = 0; index < m_size; ++index) {
        if (m_keys[index].sameValueZero(key)) {
            // Remove the element at |index| by moving all elements to the right
            // of |index| one place to the left.
            size_t count = (m_size - (index + 1)) * sizeof(Value);
            memmove(m_keys + index, m_keys + index + 1, count);
            memmove(m_values + index, m_values + index + 1, count);
            m_size--;
 
            std::for_each(m_observers.begin(), m_observers.end(), [index](ShiftObserver* ob) {
                Q_ASSERT(ob);
                if (index <= ob->pivot && ob->pivot != ShiftObserver::OUT_OF_TABLE)
                    ob->pivot = ob->pivot == 0 ? ShiftObserver::OUT_OF_TABLE : ob->pivot - 1;
            });
 
            return true;
        }
    }
    return false;
}
 
// Returns the size of the table. Note that the size may not match the underlying allocation.
uint ESTable::size() const
{
    return m_size;
}
 
// Retrieves a key and value for a given \a idx, and places them in \a key and
// \a value. They must be valid pointers.
void ESTable::iterate(uint idx, Value *key, Value *value)
{
    Q_ASSERT(idx < m_size);
    Q_ASSERT(key);
    Q_ASSERT(value);
    *key = m_keys[idx];
    *value = m_values[idx];
}
 
void ESTable::removeUnmarkedKeys()
{
    uint idx = 0;
    uint toIdx = 0;
    for (; idx < m_size; ++idx) {
        Q_ASSERT(m_keys[idx].isObject());
        Object &o = static_cast<Object &>(m_keys[idx]);
        if (o.d()->isMarked()) {
            m_keys[toIdx] = m_keys[idx];
            m_values[toIdx] = m_values[idx];
            ++toIdx;
        }
    }
    m_size = toIdx;
}