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 | |
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(size: alloc*sizeof(Heap::StringOrSymbol *)); |
54 | entriesById = (Heap::StringOrSymbol **)malloc(size: alloc*sizeof(Heap::StringOrSymbol *)); |
55 | memset(s: entriesByHash, c: 0, n: alloc*sizeof(Heap::String *)); |
56 | memset(s: entriesById, c: 0, n: alloc*sizeof(Heap::String *)); |
57 | } |
58 | |
59 | IdentifierTable::~IdentifierTable() |
60 | { |
61 | free(ptr: entriesByHash); |
62 | free(ptr: entriesById); |
63 | for (const auto &h : qAsConst(t&: idHashes)) |
64 | h->identifierTable = nullptr; |
65 | } |
66 | |
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(b: 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(size: newAlloc*sizeof(Heap::String *)); |
82 | memset(s: newEntries, c: 0, n: 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(ptr: entriesByHash); |
95 | entriesByHash = newEntries; |
96 | |
97 | newEntries = (Heap::StringOrSymbol **)malloc(size: newAlloc*sizeof(Heap::String *)); |
98 | memset(s: newEntries, c: 0, n: 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(ptr: 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 | |
135 | Heap::String *IdentifierTable::insertString(const QString &s) |
136 | { |
137 | uint subtype; |
138 | uint hash = String::createHashValue(ch: s.constData(), length: s.length(), subtype: &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 | |
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(ch: s.constData(), length: s.length(), subtype: &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(e: engine, s); |
175 | str->stringHash = hash; |
176 | str->subtype = subtype; |
177 | addEntry(str); |
178 | return str; |
179 | |
180 | } |
181 | |
182 | |
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(idx: 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(str: const_cast<QV4::Heap::String *>(str)); |
204 | return str->identifier; |
205 | } |
206 | |
207 | Heap::StringOrSymbol *IdentifierTable::resolveId(PropertyKey i) const |
208 | { |
209 | if (i.isArrayIndex()) |
210 | return engine->newString(s: 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 | |
224 | 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 | |
231 | 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 | |
238 | void IdentifierTable::markObjects(MarkStack *markStack) |
239 | { |
240 | for (const auto &h : idHashes) |
241 | h->markObjects(markStack); |
242 | } |
243 | |
244 | void IdentifierTable::sweep() |
245 | { |
246 | int freed = 0; |
247 | |
248 | Heap::StringOrSymbol **newTable = (Heap::StringOrSymbol **)malloc(size: alloc*sizeof(Heap::String *)); |
249 | memset(s: newTable, c: 0, n: alloc*sizeof(Heap::StringOrSymbol *)); |
250 | memset(s: entriesById, c: 0, n: 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(ptr: entriesByHash); |
276 | entriesByHash = newTable; |
277 | |
278 | size -= freed; |
279 | } |
280 | |
281 | PropertyKey IdentifierTable::asPropertyKey(const QString &s) |
282 | { |
283 | return insertString(s)->identifier; |
284 | } |
285 | |
286 | PropertyKey IdentifierTable::asPropertyKey(const char *s, int len) |
287 | { |
288 | uint subtype; |
289 | uint hash = String::createHashValue(ch: s, length: len, subtype: &subtype); |
290 | if (hash == UINT_MAX) |
291 | return asPropertyKey(s: QString::fromUtf8(str: s, size: 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(s: QString::fromLatin1(str: s, size: 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 | |