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
43QT_BEGIN_NAMESPACE
44
45namespace QV4 {
46
47IdentifierTable::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
59IdentifierTable::~IdentifierTable()
60{
61 free(ptr: entriesByHash);
62 free(ptr: entriesById);
63 for (const auto &h : qAsConst(t&: idHashes))
64 h->identifierTable = nullptr;
65}
66
67void 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
135Heap::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
160Heap::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
183PropertyKey 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
207Heap::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
224Heap::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
231Heap::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
238void IdentifierTable::markObjects(MarkStack *markStack)
239{
240 for (const auto &h : idHashes)
241 h->markObjects(markStack);
242}
243
244void 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
281PropertyKey IdentifierTable::asPropertyKey(const QString &s)
282{
283 return insertString(s)->identifier;
284}
285
286PropertyKey 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
311QT_END_NAMESPACE
312

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