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(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 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
178Heap::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
195Heap::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
202Heap::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
209void IdentifierTable::markObjects(MarkStack *markStack)
210{
211 for (const auto &h : idHashes)
212 h->markObjects(markStack);
213}
214
215void 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
252PropertyKey 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
266PropertyKey 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
277QT_END_NAMESPACE
278

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