1 | // Copyright (C) 2016 The Qt Company Ltd. |
2 | // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only |
3 | #include "qv4identifiertable_p.h" |
4 | #include "qv4symbol_p.h" |
5 | #include <private/qv4identifierhashdata_p.h> |
6 | #include <private/qprimefornumbits_p.h> |
7 | |
8 | QT_BEGIN_NAMESPACE |
9 | |
10 | namespace QV4 { |
11 | |
12 | IdentifierTable::IdentifierTable(ExecutionEngine *engine, int numBits) |
13 | : engine(engine) |
14 | , size(0) |
15 | , numBits(numBits) |
16 | { |
17 | alloc = qPrimeForNumBits(numBits); |
18 | entriesByHash = (Heap::StringOrSymbol **)malloc(size: alloc*sizeof(Heap::StringOrSymbol *)); |
19 | entriesById = (Heap::StringOrSymbol **)malloc(size: alloc*sizeof(Heap::StringOrSymbol *)); |
20 | memset(s: entriesByHash, c: 0, n: alloc*sizeof(Heap::String *)); |
21 | memset(s: entriesById, c: 0, n: alloc*sizeof(Heap::String *)); |
22 | } |
23 | |
24 | IdentifierTable::~IdentifierTable() |
25 | { |
26 | free(ptr: entriesByHash); |
27 | free(ptr: entriesById); |
28 | for (const auto &h : std::as_const(t&: idHashes)) |
29 | h->identifierTable = nullptr; |
30 | } |
31 | |
32 | void IdentifierTable::addEntry(Heap::StringOrSymbol *str) |
33 | { |
34 | uint hash = str->hashValue(); |
35 | |
36 | if (str->subtype == Heap::String::StringType_ArrayIndex) |
37 | return; |
38 | |
39 | str->identifier = PropertyKey::fromStringOrSymbol(b: str); |
40 | |
41 | bool grow = (alloc <= size*2); |
42 | |
43 | if (grow) { |
44 | ++numBits; |
45 | int newAlloc = qPrimeForNumBits(numBits); |
46 | Heap::StringOrSymbol **newEntries = (Heap::StringOrSymbol **)malloc(size: newAlloc*sizeof(Heap::String *)); |
47 | memset(s: newEntries, c: 0, n: newAlloc*sizeof(Heap::StringOrSymbol *)); |
48 | for (uint i = 0; i < alloc; ++i) { |
49 | Heap::StringOrSymbol *e = entriesByHash[i]; |
50 | if (!e) |
51 | continue; |
52 | uint idx = e->stringHash % newAlloc; |
53 | while (newEntries[idx]) { |
54 | ++idx; |
55 | idx %= newAlloc; |
56 | } |
57 | newEntries[idx] = e; |
58 | } |
59 | free(ptr: entriesByHash); |
60 | entriesByHash = newEntries; |
61 | |
62 | newEntries = (Heap::StringOrSymbol **)malloc(size: newAlloc*sizeof(Heap::String *)); |
63 | memset(s: newEntries, c: 0, n: newAlloc*sizeof(Heap::StringOrSymbol *)); |
64 | for (uint i = 0; i < alloc; ++i) { |
65 | Heap::StringOrSymbol *e = entriesById[i]; |
66 | if (!e) |
67 | continue; |
68 | uint idx = e->identifier.id() % newAlloc; |
69 | while (newEntries[idx]) { |
70 | ++idx; |
71 | idx %= newAlloc; |
72 | } |
73 | newEntries[idx] = e; |
74 | } |
75 | free(ptr: entriesById); |
76 | entriesById = newEntries; |
77 | |
78 | alloc = newAlloc; |
79 | } |
80 | |
81 | uint idx = hash % alloc; |
82 | while (entriesByHash[idx]) { |
83 | ++idx; |
84 | idx %= alloc; |
85 | } |
86 | entriesByHash[idx] = str; |
87 | |
88 | idx = str->identifier.id() % alloc; |
89 | while (entriesById[idx]) { |
90 | ++idx; |
91 | idx %= alloc; |
92 | } |
93 | entriesById[idx] = str; |
94 | |
95 | ++size; |
96 | } |
97 | |
98 | |
99 | |
100 | Heap::String *IdentifierTable::insertString(const QString &s) |
101 | { |
102 | uint subtype; |
103 | uint hash = String::createHashValue(ch: s.constData(), length: s.size(), subtype: &subtype); |
104 | if (subtype == Heap::String::StringType_ArrayIndex) { |
105 | Heap::String *str = engine->newString(s); |
106 | str->stringHash = hash; |
107 | str->subtype = subtype; |
108 | str->identifier = PropertyKey::fromArrayIndex(idx: hash); |
109 | return str; |
110 | } |
111 | return resolveStringEntry(s, hash, subtype); |
112 | } |
113 | |
114 | Heap::String *IdentifierTable::resolveStringEntry(const QString &s, uint hash, uint subtype) |
115 | { |
116 | uint idx = hash % alloc; |
117 | while (Heap::StringOrSymbol *e = entriesByHash[idx]) { |
118 | if (e->stringHash == hash && e->toQString() == s) |
119 | return static_cast<Heap::String *>(e); |
120 | ++idx; |
121 | idx %= alloc; |
122 | } |
123 | |
124 | Heap::String *str = engine->newString(s); |
125 | str->stringHash = hash; |
126 | str->subtype = subtype; |
127 | addEntry(str); |
128 | return str; |
129 | } |
130 | |
131 | Heap::Symbol *IdentifierTable::insertSymbol(const QString &s) |
132 | { |
133 | Q_ASSERT(s.at(0) == QLatin1Char('@')); |
134 | |
135 | uint subtype; |
136 | uint hash = String::createHashValue(ch: s.constData(), length: s.size(), subtype: &subtype); |
137 | uint idx = hash % alloc; |
138 | while (Heap::StringOrSymbol *e = entriesByHash[idx]) { |
139 | if (e->stringHash == hash && e->toQString() == s) |
140 | return static_cast<Heap::Symbol *>(e); |
141 | ++idx; |
142 | idx %= alloc; |
143 | } |
144 | |
145 | Heap::Symbol *str = Symbol::create(e: engine, s); |
146 | str->stringHash = hash; |
147 | str->subtype = subtype; |
148 | addEntry(str); |
149 | return str; |
150 | |
151 | } |
152 | |
153 | |
154 | PropertyKey IdentifierTable::asPropertyKeyImpl(const Heap::String *str) |
155 | { |
156 | if (str->identifier.isValid()) |
157 | return str->identifier; |
158 | uint hash = str->hashValue(); |
159 | if (str->subtype == Heap::String::StringType_ArrayIndex) { |
160 | str->identifier = PropertyKey::fromArrayIndex(idx: hash); |
161 | return str->identifier; |
162 | } |
163 | |
164 | uint idx = hash % alloc; |
165 | while (Heap::StringOrSymbol *e = entriesByHash[idx]) { |
166 | if (e->stringHash == hash && e->toQString() == str->toQString()) { |
167 | str->identifier = e->identifier; |
168 | return e->identifier; |
169 | } |
170 | ++idx; |
171 | idx %= alloc; |
172 | } |
173 | |
174 | addEntry(str: const_cast<QV4::Heap::String *>(str)); |
175 | return str->identifier; |
176 | } |
177 | |
178 | Heap::StringOrSymbol *IdentifierTable::resolveId(PropertyKey i) const |
179 | { |
180 | if (i.isArrayIndex()) |
181 | return engine->newString(s: QString::number(i.asArrayIndex())); |
182 | if (!i.isValid()) |
183 | return nullptr; |
184 | |
185 | uint idx = i.id() % alloc; |
186 | while (1) { |
187 | Heap::StringOrSymbol *e = entriesById[idx]; |
188 | if (!e || e->identifier == i) |
189 | return e; |
190 | ++idx; |
191 | idx %= alloc; |
192 | } |
193 | } |
194 | |
195 | Heap::String *IdentifierTable::stringForId(PropertyKey i) const |
196 | { |
197 | Heap::StringOrSymbol *s = resolveId(i); |
198 | Q_ASSERT(s && s->internalClass->vtable->isString); |
199 | return static_cast<Heap::String *>(s); |
200 | } |
201 | |
202 | Heap::Symbol *IdentifierTable::symbolForId(PropertyKey i) const |
203 | { |
204 | Heap::StringOrSymbol *s = resolveId(i); |
205 | Q_ASSERT(!s || !s->internalClass->vtable->isString); |
206 | return static_cast<Heap::Symbol *>(s); |
207 | } |
208 | |
209 | void IdentifierTable::markObjects(MarkStack *markStack) |
210 | { |
211 | for (const auto &h : idHashes) |
212 | h->markObjects(markStack); |
213 | } |
214 | |
215 | void IdentifierTable::sweep() |
216 | { |
217 | int freed = 0; |
218 | |
219 | Heap::StringOrSymbol **newTable = (Heap::StringOrSymbol **)malloc(size: alloc*sizeof(Heap::String *)); |
220 | memset(s: newTable, c: 0, n: alloc*sizeof(Heap::StringOrSymbol *)); |
221 | memset(s: entriesById, c: 0, n: alloc*sizeof(Heap::StringOrSymbol *)); |
222 | for (uint i = 0; i < alloc; ++i) { |
223 | Heap::StringOrSymbol *e = entriesByHash[i]; |
224 | if (!e) |
225 | continue; |
226 | if (!e->isMarked()) { |
227 | ++freed; |
228 | continue; |
229 | } |
230 | uint idx = e->hashValue() % alloc; |
231 | while (newTable[idx]) { |
232 | ++idx; |
233 | if (idx == alloc) |
234 | idx = 0; |
235 | } |
236 | newTable[idx] = e; |
237 | |
238 | idx = e->identifier.id() % alloc; |
239 | while (entriesById[idx]) { |
240 | ++idx; |
241 | if (idx == alloc) |
242 | idx = 0; |
243 | } |
244 | entriesById[idx] = e; |
245 | } |
246 | free(ptr: entriesByHash); |
247 | entriesByHash = newTable; |
248 | |
249 | size -= freed; |
250 | } |
251 | |
252 | PropertyKey IdentifierTable::asPropertyKey(const QString &s, |
253 | IdentifierTable::KeyConversionBehavior conversionBehvior) |
254 | { |
255 | uint subtype; |
256 | uint hash = String::createHashValue(ch: s.constData(), length: s.size(), subtype: &subtype); |
257 | if (subtype == Heap::String::StringType_ArrayIndex) { |
258 | if (Q_UNLIKELY(conversionBehvior == ForceConversionToId)) |
259 | hash = String::createHashValueDisallowingArrayIndex(ch: s.constData(), length: s.size(), subtype: &subtype); |
260 | else |
261 | return PropertyKey::fromArrayIndex(idx: hash); |
262 | } |
263 | return resolveStringEntry(s, hash, subtype)->identifier; |
264 | } |
265 | |
266 | PropertyKey IdentifierTable::asPropertyKey(const char *s, int len) |
267 | { |
268 | uint subtype; |
269 | uint hash = String::createHashValue(ch: s, length: len, subtype: &subtype); |
270 | if (subtype == Heap::String::StringType_ArrayIndex) |
271 | return PropertyKey::fromArrayIndex(idx: hash); |
272 | return resolveStringEntry(s: QString::fromLatin1(str: s, size: len), hash, subtype)->identifier; |
273 | } |
274 | |
275 | } |
276 | |
277 | QT_END_NAMESPACE |
278 | |