1/****************************************************************************
2**
3** Copyright (C) 2018 Crimson AS <info@crimson.no>
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the QtQml module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39
40#include "qv4estable_p.h"
41#include "qv4object_p.h"
42
43using namespace QV4;
44
45// The ES spec requires that Map/Set be implemented using a data structure that
46// is a little different from most; it requires nonlinear access, and must also
47// preserve the order of insertion of items in a deterministic way.
48//
49// This class implements those requirements, except for fast access: that
50// will be addressed in a followup patch.
51
52ESTable::ESTable()
53 : m_capacity(8)
54{
55 m_keys = (Value*)malloc(size: m_capacity * sizeof(Value));
56 m_values = (Value*)malloc(size: m_capacity * sizeof(Value));
57 memset(s: m_keys, c: 0, n: m_capacity);
58 memset(s: m_values, c: 0, n: m_capacity);
59}
60
61ESTable::~ESTable()
62{
63 free(ptr: m_keys);
64 free(ptr: m_values);
65 m_size = 0;
66 m_capacity = 0;
67 m_keys = nullptr;
68 m_values = nullptr;
69}
70
71void ESTable::markObjects(MarkStack *s, bool isWeakMap)
72{
73 for (uint i = 0; i < m_size; ++i) {
74 if (!isWeakMap)
75 m_keys[i].mark(markStack: s);
76 m_values[i].mark(markStack: s);
77 }
78}
79
80// Pretends that there's nothing in the table. Doesn't actually free memory, as
81// it will almost certainly be reused again anyway.
82void ESTable::clear()
83{
84 m_size = 0;
85}
86
87// Update the table to contain \a value for a given \a key. The key is
88// normalized, as required by the ES spec.
89void ESTable::set(const Value &key, const Value &value)
90{
91 for (uint i = 0; i < m_size; ++i) {
92 if (m_keys[i].sameValueZero(other: key)) {
93 m_values[i] = value;
94 return;
95 }
96 }
97
98 if (m_capacity == m_size) {
99 uint oldCap = m_capacity;
100 m_capacity *= 2;
101 m_keys = (Value*)realloc(ptr: m_keys, size: m_capacity * sizeof(Value));
102 m_values = (Value*)realloc(ptr: m_values, size: m_capacity * sizeof(Value));
103 memset(s: m_keys + oldCap, c: 0, n: m_capacity - oldCap);
104 memset(s: m_values + oldCap, c: 0, n: m_capacity - oldCap);
105 }
106
107 Value nk = key;
108 if (nk.isDouble()) {
109 if (nk.doubleValue() == 0 && std::signbit(x: nk.doubleValue()))
110 nk = Value::fromDouble(d: +0);
111 }
112
113 m_keys[m_size] = nk;
114 m_values[m_size] = value;
115
116 m_size++;
117}
118
119// Returns true if the table contains \a key, false otherwise.
120bool ESTable::has(const Value &key) const
121{
122 for (uint i = 0; i < m_size; ++i) {
123 if (m_keys[i].sameValueZero(other: key))
124 return true;
125 }
126
127 return false;
128}
129
130// Fetches the value for the given \a key, and if \a hasValue is passed in,
131// it is set depending on whether or not the given key was found.
132ReturnedValue ESTable::get(const Value &key, bool *hasValue) const
133{
134 for (uint i = 0; i < m_size; ++i) {
135 if (m_keys[i].sameValueZero(other: key)) {
136 if (hasValue)
137 *hasValue = true;
138 return m_values[i].asReturnedValue();
139 }
140 }
141
142 if (hasValue)
143 *hasValue = false;
144 return Encode::undefined();
145}
146
147// Removes the given \a key from the table
148bool ESTable::remove(const Value &key)
149{
150 bool found = false;
151 uint idx = 0;
152 for (; idx < m_size; ++idx) {
153 if (m_keys[idx].sameValueZero(other: key)) {
154 found = true;
155 break;
156 }
157 }
158
159 if (found == true) {
160 memmove(dest: m_keys + idx, src: m_keys + idx + 1, n: (m_size - idx)*sizeof(Value));
161 memmove(dest: m_values + idx, src: m_values + idx + 1, n: (m_size - idx)*sizeof(Value));
162 m_size--;
163 }
164 return found;
165}
166
167// Returns the size of the table. Note that the size may not match the underlying allocation.
168uint ESTable::size() const
169{
170 return m_size;
171}
172
173// Retrieves a key and value for a given \a idx, and places them in \a key and
174// \a value. They must be valid pointers.
175void ESTable::iterate(uint idx, Value *key, Value *value)
176{
177 Q_ASSERT(idx < m_size);
178 Q_ASSERT(key);
179 Q_ASSERT(value);
180 *key = m_keys[idx];
181 *value = m_values[idx];
182}
183
184void ESTable::removeUnmarkedKeys()
185{
186 uint idx = 0;
187 uint toIdx = 0;
188 for (; idx < m_size; ++idx) {
189 Q_ASSERT(m_keys[idx].isObject());
190 Object &o = static_cast<Object &>(m_keys[idx]);
191 if (o.d()->isMarked()) {
192 m_keys[toIdx] = m_keys[idx];
193 m_values[toIdx] = m_values[idx];
194 ++toIdx;
195 }
196 }
197 m_size = toIdx;
198}
199
200

source code of qtdeclarative/src/qml/jsruntime/qv4estable.cpp