1 /****************************************************************************
2 **
3 ** Copyright (C) 2016 The Qt Company Ltd.
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 #include "qv4identifiertable_p.h"
40 #include "qv4symbol_p.h"
41 #include <private/qprimefornumbits_p.h>
42
43 QT_BEGIN_NAMESPACE
44
45 namespace QV4 {
46
IdentifierTable(ExecutionEngine * engine,int numBits)47 IdentifierTable::IdentifierTable(ExecutionEngine *engine, int numBits)
48 : engine(engine)
49 , size(0)
50 , numBits(numBits)
51 {
52 alloc = qPrimeForNumBits(numBits);
53 entriesByHash = (Heap::StringOrSymbol **)malloc(alloc*sizeof(Heap::StringOrSymbol *));
54 entriesById = (Heap::StringOrSymbol **)malloc(alloc*sizeof(Heap::StringOrSymbol *));
55 memset(entriesByHash, 0, alloc*sizeof(Heap::String *));
56 memset(entriesById, 0, alloc*sizeof(Heap::String *));
57 }
58
~IdentifierTable()59 IdentifierTable::~IdentifierTable()
60 {
61 free(entriesByHash);
62 free(entriesById);
63 for (const auto &h : qAsConst(idHashes))
64 h->identifierTable = nullptr;
65 }
66
addEntry(Heap::StringOrSymbol * str)67 void IdentifierTable::addEntry(Heap::StringOrSymbol *str)
68 {
69 uint hash = str->hashValue();
70
71 if (str->subtype == Heap::String::StringType_ArrayIndex)
72 return;
73
74 str->identifier = PropertyKey::fromStringOrSymbol(str);
75
76 bool grow = (alloc <= size*2);
77
78 if (grow) {
79 ++numBits;
80 int newAlloc = qPrimeForNumBits(numBits);
81 Heap::StringOrSymbol **newEntries = (Heap::StringOrSymbol **)malloc(newAlloc*sizeof(Heap::String *));
82 memset(newEntries, 0, newAlloc*sizeof(Heap::StringOrSymbol *));
83 for (uint i = 0; i < alloc; ++i) {
84 Heap::StringOrSymbol *e = entriesByHash[i];
85 if (!e)
86 continue;
87 uint idx = e->stringHash % newAlloc;
88 while (newEntries[idx]) {
89 ++idx;
90 idx %= newAlloc;
91 }
92 newEntries[idx] = e;
93 }
94 free(entriesByHash);
95 entriesByHash = newEntries;
96
97 newEntries = (Heap::StringOrSymbol **)malloc(newAlloc*sizeof(Heap::String *));
98 memset(newEntries, 0, newAlloc*sizeof(Heap::StringOrSymbol *));
99 for (uint i = 0; i < alloc; ++i) {
100 Heap::StringOrSymbol *e = entriesById[i];
101 if (!e)
102 continue;
103 uint idx = e->identifier.id() % newAlloc;
104 while (newEntries[idx]) {
105 ++idx;
106 idx %= newAlloc;
107 }
108 newEntries[idx] = e;
109 }
110 free(entriesById);
111 entriesById = newEntries;
112
113 alloc = newAlloc;
114 }
115
116 uint idx = hash % alloc;
117 while (entriesByHash[idx]) {
118 ++idx;
119 idx %= alloc;
120 }
121 entriesByHash[idx] = str;
122
123 idx = str->identifier.id() % alloc;
124 while (entriesById[idx]) {
125 ++idx;
126 idx %= alloc;
127 }
128 entriesById[idx] = str;
129
130 ++size;
131 }
132
133
134
insertString(const QString & s)135 Heap::String *IdentifierTable::insertString(const QString &s)
136 {
137 uint subtype;
138 uint hash = String::createHashValue(s.constData(), s.length(), &subtype);
139 if (subtype == Heap::String::StringType_ArrayIndex) {
140 Heap::String *str = engine->newString(s);
141 str->stringHash = hash;
142 str->subtype = subtype;
143 return str;
144 }
145 uint idx = hash % alloc;
146 while (Heap::StringOrSymbol *e = entriesByHash[idx]) {
147 if (e->stringHash == hash && e->toQString() == s)
148 return static_cast<Heap::String *>(e);
149 ++idx;
150 idx %= alloc;
151 }
152
153 Heap::String *str = engine->newString(s);
154 str->stringHash = hash;
155 str->subtype = subtype;
156 addEntry(str);
157 return str;
158 }
159
insertSymbol(const QString & s)160 Heap::Symbol *IdentifierTable::insertSymbol(const QString &s)
161 {
162 Q_ASSERT(s.at(0) == QLatin1Char('@'));
163
164 uint subtype;
165 uint hash = String::createHashValue(s.constData(), s.length(), &subtype);
166 uint idx = hash % alloc;
167 while (Heap::StringOrSymbol *e = entriesByHash[idx]) {
168 if (e->stringHash == hash && e->toQString() == s)
169 return static_cast<Heap::Symbol *>(e);
170 ++idx;
171 idx %= alloc;
172 }
173
174 Heap::Symbol *str = Symbol::create(engine, s);
175 str->stringHash = hash;
176 str->subtype = subtype;
177 addEntry(str);
178 return str;
179
180 }
181
182
asPropertyKeyImpl(const Heap::String * str)183 PropertyKey IdentifierTable::asPropertyKeyImpl(const Heap::String *str)
184 {
185 if (str->identifier.isValid())
186 return str->identifier;
187 uint hash = str->hashValue();
188 if (str->subtype == Heap::String::StringType_ArrayIndex) {
189 str->identifier = PropertyKey::fromArrayIndex(hash);
190 return str->identifier;
191 }
192
193 uint idx = hash % alloc;
194 while (Heap::StringOrSymbol *e = entriesByHash[idx]) {
195 if (e->stringHash == hash && e->toQString() == str->toQString()) {
196 str->identifier = e->identifier;
197 return e->identifier;
198 }
199 ++idx;
200 idx %= alloc;
201 }
202
203 addEntry(const_cast<QV4::Heap::String *>(str));
204 return str->identifier;
205 }
206
resolveId(PropertyKey i) const207 Heap::StringOrSymbol *IdentifierTable::resolveId(PropertyKey i) const
208 {
209 if (i.isArrayIndex())
210 return engine->newString(QString::number(i.asArrayIndex()));
211 if (!i.isValid())
212 return nullptr;
213
214 uint idx = i.id() % alloc;
215 while (1) {
216 Heap::StringOrSymbol *e = entriesById[idx];
217 if (!e || e->identifier == i)
218 return e;
219 ++idx;
220 idx %= alloc;
221 }
222 }
223
stringForId(PropertyKey i) const224 Heap::String *IdentifierTable::stringForId(PropertyKey i) const
225 {
226 Heap::StringOrSymbol *s = resolveId(i);
227 Q_ASSERT(s && s->internalClass->vtable->isString);
228 return static_cast<Heap::String *>(s);
229 }
230
symbolForId(PropertyKey i) const231 Heap::Symbol *IdentifierTable::symbolForId(PropertyKey i) const
232 {
233 Heap::StringOrSymbol *s = resolveId(i);
234 Q_ASSERT(!s || !s->internalClass->vtable->isString);
235 return static_cast<Heap::Symbol *>(s);
236 }
237
markObjects(MarkStack * markStack)238 void IdentifierTable::markObjects(MarkStack *markStack)
239 {
240 for (const auto &h : idHashes)
241 h->markObjects(markStack);
242 }
243
sweep()244 void IdentifierTable::sweep()
245 {
246 int freed = 0;
247
248 Heap::StringOrSymbol **newTable = (Heap::StringOrSymbol **)malloc(alloc*sizeof(Heap::String *));
249 memset(newTable, 0, alloc*sizeof(Heap::StringOrSymbol *));
250 memset(entriesById, 0, alloc*sizeof(Heap::StringOrSymbol *));
251 for (uint i = 0; i < alloc; ++i) {
252 Heap::StringOrSymbol *e = entriesByHash[i];
253 if (!e)
254 continue;
255 if (!e->isMarked()) {
256 ++freed;
257 continue;
258 }
259 uint idx = e->hashValue() % alloc;
260 while (newTable[idx]) {
261 ++idx;
262 if (idx == alloc)
263 idx = 0;
264 }
265 newTable[idx] = e;
266
267 idx = e->identifier.id() % alloc;
268 while (entriesById[idx]) {
269 ++idx;
270 if (idx == alloc)
271 idx = 0;
272 }
273 entriesById[idx] = e;
274 }
275 free(entriesByHash);
276 entriesByHash = newTable;
277
278 size -= freed;
279 }
280
asPropertyKey(const QString & s)281 PropertyKey IdentifierTable::asPropertyKey(const QString &s)
282 {
283 return insertString(s)->identifier;
284 }
285
asPropertyKey(const char * s,int len)286 PropertyKey IdentifierTable::asPropertyKey(const char *s, int len)
287 {
288 uint subtype;
289 uint hash = String::createHashValue(s, len, &subtype);
290 if (hash == UINT_MAX)
291 return asPropertyKey(QString::fromUtf8(s, len));
292
293 QLatin1String latin(s, len);
294 uint idx = hash % alloc;
295 while (Heap::StringOrSymbol *e = entriesByHash[idx]) {
296 if (e->stringHash == hash && e->toQString() == latin)
297 return e->identifier;
298 ++idx;
299 idx %= alloc;
300 }
301
302 Heap::String *str = engine->newString(QString::fromLatin1(s, len));
303 str->stringHash = hash;
304 str->subtype = subtype;
305 addEntry(str);
306 return str->identifier;
307 }
308
309 }
310
311 QT_END_NAMESPACE
312