Revision control
++ // 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;
++ }