Map/Set: Introduce QV4::ESTable

This removes the duplication of code between Map and Set by placing it
in a shared location, and will hopefully be a touch more efficient than
using ArrayObject.

In a followup patch, it will get faster, too.

Note: As a bonus, this also fixed a few more test failures: forEach
wasn't handling the object being changed during iteration.

Task-number: QTBUG-68545
Change-Id: I8bf6f9c5b2de030a02ce27a23b8c1da431ffeda4
Reviewed-by: Lars Knoll <lars.knoll@qt.io>

1 files changed, 181 insertions, 0 deletions

diff --git a/src/qml/jsruntime/qv4estable.cpp b/src/qml/jsruntime/qv4estable.cpp
new file mode 100644
index 0000000000..55b7407000
--- /dev/null
+++ b/src/qml/jsruntime/qv4estable.cpp
@@ -0,0 +1,181 @@
+/****************************************************************************
+**
+** Copyright (C) 2018 Crimson AS <info@crimson.no>
+** Contact: https://www.qt.io/licensing/
+**
+** This file is part of the QtQml module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and The Qt Company. For licensing terms
+** and conditions see https://www.qt.io/terms-conditions. For further
+** information use the contact form at https://www.qt.io/contact-us.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 3 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL3 included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 3 requirements
+** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 2.0 or (at your option) the GNU General
+** Public license version 3 or any later version approved by the KDE Free
+** Qt Foundation. The licenses are as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
+** included in the packaging of this file. Please review the following
+** information to ensure the GNU General Public License requirements will
+** be met: https://www.gnu.org/licenses/gpl-2.0.html and
+** https://www.gnu.org/licenses/gpl-3.0.html.
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "qv4estable_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)
+{
+    for (uint i = 0; i < m_size; ++i) {
+        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;
+}
+
+// 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 = Primitive::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)
+{
+    bool found = false;
+    uint idx = 0;
+    for (; idx < m_size; ++idx) {
+        if (m_keys[idx].sameValueZero(key)) {
+            found = true;
+            break;
+        }
+    }
+
+    if (found == true) {
+        memmove(m_keys + idx, m_keys + idx + 1, m_size - idx);
+        memmove(m_values + idx, m_values + idx + 1, m_size - idx);
+        m_size--;
+    }
+    return found;
+}
+
+// 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];
+}
+