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 | |
43 | using 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 | |
52 | ESTable::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 | |
61 | ESTable::~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 | |
71 | void 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. |
82 | void 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. |
89 | void 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. |
120 | bool 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. |
132 | ReturnedValue 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 |
148 | bool 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. |
168 | uint 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. |
175 | void 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 | |
184 | void 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 | |