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
8QT_BEGIN_NAMESPACE
9
10namespace QV4 {
11
12IdentifierTable::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
24IdentifierTable::~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
32void 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(engine, 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
100Heap::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
114Heap::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
131Heap::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
154PropertyKey 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 QV4::WriteBarrier::markCustom(engine, markFunction: [&](QV4::MarkStack *stack) {
169 e->identifier.asStringOrSymbol()->mark(markStack: stack);
170 });
171 return e->identifier;
172 }
173 ++idx;
174 idx %= alloc;
175 }
176
177 addEntry(str: const_cast<QV4::Heap::String *>(str));
178 return str->identifier;
179}
180
181Heap::StringOrSymbol *IdentifierTable::resolveId(PropertyKey i) const
182{
183 if (i.isArrayIndex())
184 return engine->newString(s: QString::number(i.asArrayIndex()));
185 if (!i.isValid())
186 return nullptr;
187
188 uint idx = i.id() % alloc;
189 while (1) {
190 Heap::StringOrSymbol *e = entriesById[idx];
191 if (!e || e->identifier == i)
192 return e;
193 ++idx;
194 idx %= alloc;
195 }
196}
197
198Heap::String *IdentifierTable::stringForId(PropertyKey i) const
199{
200 Heap::StringOrSymbol *s = resolveId(i);
201 Q_ASSERT(s && s->internalClass->vtable->isString);
202 return static_cast<Heap::String *>(s);
203}
204
205Heap::Symbol *IdentifierTable::symbolForId(PropertyKey i) const
206{
207 Heap::StringOrSymbol *s = resolveId(i);
208 Q_ASSERT(!s || !s->internalClass->vtable->isString);
209 return static_cast<Heap::Symbol *>(s);
210}
211
212void IdentifierTable::markObjects(MarkStack *markStack)
213{
214 for (const auto &h : idHashes)
215 h->markObjects(markStack);
216}
217
218void IdentifierTable::sweep()
219{
220 int freed = 0;
221
222 Heap::StringOrSymbol **newTable = (Heap::StringOrSymbol **)malloc(size: alloc*sizeof(Heap::String *));
223 memset(s: newTable, c: 0, n: alloc*sizeof(Heap::StringOrSymbol *));
224 memset(s: entriesById, c: 0, n: alloc*sizeof(Heap::StringOrSymbol *));
225 for (uint i = 0; i < alloc; ++i) {
226 Heap::StringOrSymbol *e = entriesByHash[i];
227 if (!e)
228 continue;
229 if (!e->isMarked()) {
230 ++freed;
231 continue;
232 }
233 uint idx = e->hashValue() % alloc;
234 while (newTable[idx]) {
235 ++idx;
236 if (idx == alloc)
237 idx = 0;
238 }
239 newTable[idx] = e;
240
241 idx = e->identifier.id() % alloc;
242 while (entriesById[idx]) {
243 ++idx;
244 if (idx == alloc)
245 idx = 0;
246 }
247 entriesById[idx] = e;
248 }
249 free(ptr: entriesByHash);
250 entriesByHash = newTable;
251
252 size -= freed;
253}
254
255PropertyKey IdentifierTable::asPropertyKey(const QString &s,
256 IdentifierTable::KeyConversionBehavior conversionBehvior)
257{
258 uint subtype;
259 uint hash = String::createHashValue(ch: s.constData(), length: s.size(), subtype: &subtype);
260 if (subtype == Heap::String::StringType_ArrayIndex) {
261 if (Q_UNLIKELY(conversionBehvior == ForceConversionToId))
262 hash = String::createHashValueDisallowingArrayIndex(ch: s.constData(), length: s.size(), subtype: &subtype);
263 else
264 return PropertyKey::fromArrayIndex(idx: hash);
265 }
266 return resolveStringEntry(s, hash, subtype)->identifier;
267}
268
269}
270
271QT_END_NAMESPACE
272

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