1/****************************************************************************
2**
3** Copyright (C) 2019 The Qt Company Ltd.
4** Copyright (C) 2016 basysKom GmbH.
5** Contact: https://www.qt.io/licensing/
6**
7** This file is part of the test suite of the Qt Toolkit.
8**
9** $QT_BEGIN_LICENSE:GPL-EXCEPT$
10** Commercial License Usage
11** Licensees holding valid commercial Qt licenses may use this file in
12** accordance with the commercial license agreement provided with the
13** Software or, alternatively, in accordance with the terms contained in
14** a written agreement between you and The Qt Company. For licensing terms
15** and conditions see https://www.qt.io/terms-conditions. For further
16** information use the contact form at https://www.qt.io/contact-us.
17**
18** GNU General Public License Usage
19** Alternatively, this file may be used under the terms of the GNU
20** General Public License version 3 as published by the Free Software
21** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT
22** included in the packaging of this file. Please review the following
23** information to ensure the GNU General Public License requirements will
24** be met: https://www.gnu.org/licenses/gpl-3.0.html.
25**
26** $QT_END_LICENSE$
27**
28****************************************************************************/
29
30#include <qtest.h>
31#include <QQmlEngine>
32#include <private/qv4identifiertable_p.h>
33
34class tst_qv4identifiertable : public QObject
35{
36 Q_OBJECT
37
38private slots:
39 void sweepFirstEntryInBucket();
40 void sweepCenterEntryInBucket();
41 void sweepLastEntryInBucket();
42 void sweepFirstEntryInSameBucketWithDifferingHash();
43 void dontSweepAcrossBucketBoundaries();
44 void sweepAcrossBucketBoundariesIfFirstBucketFull();
45 void sweepBucketGap();
46};
47
48void tst_qv4identifiertable::sweepFirstEntryInBucket()
49{
50 QV4::ExecutionEngine engine;
51 QV4::IdentifierTable table(&engine, /*numBits*/1);
52
53 auto entry1 = engine.newString(QStringLiteral("one"));
54 auto entry2 = engine.newString(QStringLiteral("two"));
55 auto entry3 = engine.newString(QStringLiteral("three"));
56
57 entry1->createHashValue();
58 entry2->createHashValue();
59 entry3->createHashValue();
60
61 // All strings go into the same bucket
62 entry1->stringHash = 0;
63 entry2->stringHash = 0;
64 entry3->stringHash = 0;
65
66 // trigger insertion
67 table.asPropertyKey(str: entry1);
68 table.asPropertyKey(str: entry2);
69 table.asPropertyKey(str: entry3);
70
71 QCOMPARE(table.size, 3u);
72 QCOMPARE(table.alloc, 5u);
73
74 QCOMPARE(table.entriesByHash[0], entry1);
75 QCOMPARE(table.entriesByHash[1], entry2);
76 QCOMPARE(table.entriesByHash[2], entry3);
77 QCOMPARE(table.entriesByHash[3], nullptr);
78
79 // first entry not marked
80 entry2->setMarkBit();
81 entry3->setMarkBit();
82
83 table.sweep();
84
85 QCOMPARE(table.entriesByHash[0], entry2);
86 QCOMPARE(table.entriesByHash[1], entry3);
87 QCOMPARE(table.entriesByHash[2], nullptr);
88 QCOMPARE(table.entriesByHash[3], nullptr);
89}
90
91void tst_qv4identifiertable::sweepCenterEntryInBucket()
92{
93 QV4::ExecutionEngine engine;
94 QV4::IdentifierTable table(&engine, /*numBits*/1);
95
96 auto entry1 = engine.newString(QStringLiteral("one"));
97 auto entry2 = engine.newString(QStringLiteral("two"));
98 auto entry3 = engine.newString(QStringLiteral("three"));
99
100 entry1->createHashValue();
101 entry2->createHashValue();
102 entry3->createHashValue();
103
104 // All strings go into the same bucket
105 entry1->stringHash = 0;
106 entry2->stringHash = 0;
107 entry3->stringHash = 0;
108
109 // trigger insertion
110 table.asPropertyKey(str: entry1);
111 table.asPropertyKey(str: entry2);
112 table.asPropertyKey(str: entry3);
113
114 QCOMPARE(table.size, 3u);
115 QCOMPARE(table.alloc, 5u);
116
117 QCOMPARE(table.entriesByHash[0], entry1);
118 QCOMPARE(table.entriesByHash[1], entry2);
119 QCOMPARE(table.entriesByHash[2], entry3);
120 QCOMPARE(table.entriesByHash[3], nullptr);
121
122 entry1->setMarkBit();
123 // second entry not marked
124 entry3->setMarkBit();
125
126 table.sweep();
127
128 QCOMPARE(table.entriesByHash[0], entry1);
129 QCOMPARE(table.entriesByHash[1], entry3);
130 QCOMPARE(table.entriesByHash[2], nullptr);
131 QCOMPARE(table.entriesByHash[3], nullptr);
132}
133
134void tst_qv4identifiertable::sweepLastEntryInBucket()
135{
136 QV4::ExecutionEngine engine;
137 QV4::IdentifierTable table(&engine, /*numBits*/1);
138
139 auto entry1 = engine.newString(QStringLiteral("one"));
140 auto entry2 = engine.newString(QStringLiteral("two"));
141 auto entry3 = engine.newString(QStringLiteral("three"));
142
143 entry1->createHashValue();
144 entry2->createHashValue();
145 entry3->createHashValue();
146
147 // All strings go into the same bucket
148 entry1->stringHash = 0;
149 entry2->stringHash = 0;
150 entry3->stringHash = 0;
151
152 // trigger insertion
153 table.asPropertyKey(str: entry1);
154 table.asPropertyKey(str: entry2);
155 table.asPropertyKey(str: entry3);
156
157 QCOMPARE(table.size, 3u);
158 QCOMPARE(table.alloc, 5u);
159
160 QCOMPARE(table.entriesByHash[0], entry1);
161 QCOMPARE(table.entriesByHash[1], entry2);
162 QCOMPARE(table.entriesByHash[2], entry3);
163 QCOMPARE(table.entriesByHash[3], nullptr);
164
165 entry1->setMarkBit();
166 entry2->setMarkBit();
167 // third entry not marked
168
169 table.sweep();
170
171 QCOMPARE(table.entriesByHash[0], entry1);
172 QCOMPARE(table.entriesByHash[1], entry2);
173 QCOMPARE(table.entriesByHash[2], nullptr);
174 QCOMPARE(table.entriesByHash[3], nullptr);
175}
176
177void tst_qv4identifiertable::sweepFirstEntryInSameBucketWithDifferingHash()
178{
179 QV4::ExecutionEngine engine;
180 QV4::IdentifierTable table(&engine, /*numBits*/1);
181
182 auto entry1 = engine.newString(QStringLiteral("one"));
183 auto entry2 = engine.newString(QStringLiteral("two"));
184
185 entry1->createHashValue();
186 entry2->createHashValue();
187
188 // First and second entry have differing hash but end up in the
189 // same bucket after modulo alloc.
190 entry1->stringHash = 0;
191 entry2->stringHash = 5;
192
193 // trigger insertion
194 table.asPropertyKey(str: entry1);
195 table.asPropertyKey(str: entry2);
196
197 QCOMPARE(table.size, 2u);
198 QCOMPARE(table.alloc, 5u);
199
200 QCOMPARE(table.entriesByHash[0], entry1);
201 QCOMPARE(table.entriesByHash[1], entry2);
202 QCOMPARE(table.entriesByHash[2], nullptr);
203
204 // first entry not marked
205 entry2->setMarkBit();
206
207 table.sweep();
208
209 QCOMPARE(table.entriesByHash[0], entry2);
210 QCOMPARE(table.entriesByHash[1], nullptr);
211 QCOMPARE(table.entriesByHash[2], nullptr);
212}
213
214void tst_qv4identifiertable::dontSweepAcrossBucketBoundaries()
215{
216 QV4::ExecutionEngine engine;
217 QV4::IdentifierTable table(&engine, /*numBits*/1);
218
219 auto entry1 = engine.newString(QStringLiteral("one"));
220 auto entry2 = engine.newString(QStringLiteral("two"));
221 auto entry3 = engine.newString(QStringLiteral("three"));
222
223 entry1->createHashValue();
224 entry2->createHashValue();
225 entry3->createHashValue();
226
227 // Different buckets for both entries.
228 entry1->stringHash = 0;
229 entry2->stringHash = 1;
230
231 // trigger insertion
232 table.asPropertyKey(str: entry1);
233 table.asPropertyKey(str: entry2);
234
235 QCOMPARE(table.size, 2u);
236 QCOMPARE(table.alloc, 5u);
237
238 QCOMPARE(table.entriesByHash[0], entry1);
239 QCOMPARE(table.entriesByHash[1], entry2);
240 QCOMPARE(table.entriesByHash[2], nullptr);
241
242 // first entry not marked
243 entry2->setMarkBit();
244
245 table.sweep();
246
247 QCOMPARE(table.entriesByHash[0], nullptr);
248 QCOMPARE(table.entriesByHash[1], entry2);
249 QCOMPARE(table.entriesByHash[2], nullptr);
250}
251
252void tst_qv4identifiertable::sweepAcrossBucketBoundariesIfFirstBucketFull()
253{
254 QV4::ExecutionEngine engine;
255 QV4::IdentifierTable table(&engine, /*numBits*/3);
256
257 auto entry1 = engine.newString(QStringLiteral("one"));
258 auto entry2 = engine.newString(QStringLiteral("two"));
259 auto entry3 = engine.newString(QStringLiteral("three"));
260 auto entry4 = engine.newString(QStringLiteral("four"));
261
262 entry1->createHashValue();
263 entry2->createHashValue();
264 entry3->createHashValue();
265 entry4->createHashValue();
266
267 // First, third and fourth entry have the same bucket (after modulo) and
268 // would typically end up in order [entry1, entry3, entry4, entry2]. However
269 // since null termination isn't guaranteed, an insertion order of
270 // entry1, entry2, entry3 and entry4 results in a
271 // table [entry1, entry2, entry3, entry4].
272 entry1->stringHash = 0;
273 entry2->stringHash = 1;
274 entry3->stringHash = 11;
275 entry4->stringHash = 11;
276
277 // trigger insertion
278 table.asPropertyKey(str: entry1);
279 table.asPropertyKey(str: entry2);
280 table.asPropertyKey(str: entry3);
281 table.asPropertyKey(str: entry4);
282
283 QCOMPARE(table.size, 4u);
284 QCOMPARE(table.alloc, 11u);
285
286 QCOMPARE(table.entriesByHash[0], entry1);
287 QCOMPARE(table.entriesByHash[1], entry2);
288 QCOMPARE(table.entriesByHash[2], entry3);
289 QCOMPARE(table.entriesByHash[3], entry4);
290 QCOMPARE(table.entriesByHash[4], nullptr);
291
292 // first entry not marked
293 entry2->setMarkBit();
294 entry3->setMarkBit();
295 entry4->setMarkBit();
296
297 table.sweep();
298
299 QCOMPARE(table.entriesByHash[0], entry3);
300 QCOMPARE(table.entriesByHash[1], entry2);
301 QCOMPARE(table.entriesByHash[2], entry4);
302 QCOMPARE(table.entriesByHash[3], nullptr);
303}
304
305void tst_qv4identifiertable::sweepBucketGap()
306{
307 QV4::ExecutionEngine engine;
308 QV4::IdentifierTable table(&engine, /*numBits*/3);
309
310 auto entry1 = engine.newString(QStringLiteral("one"));
311 auto entry2 = engine.newString(QStringLiteral("two"));
312 auto entry3 = engine.newString(QStringLiteral("three"));
313 auto entry4 = engine.newString(QStringLiteral("four"));
314
315 entry1->createHashValue();
316 entry2->createHashValue();
317 entry3->createHashValue();
318 entry4->createHashValue();
319
320 // We have two buckets where the second entry in the first bucket
321 // flows into the second bucket. So insertion into the second bucket
322 // will shift by one and create
323 // [entry1][entry2 (would map to first but overflows into second), entry3, entry4]
324 // Garbage collecting the first entry should not only move the second entry
325 // into its own first bucket (where there is space now), it is also critical to
326 // not leave a gap but move the third and fourth entries to the beginning of
327 // their bucket:
328 // [entry2][entry3, entry4]
329 entry1->stringHash = 0; // % 11 -> 0
330 entry2->stringHash = 11; // % 11 -> 0, but ends up at idx 1 because 0 taken
331 entry3->stringHash = 12; // % 11 -> 1, but ends up at idx 2 because 1 taken
332 entry4->stringHash = 12; // % 11 -> 1, but ends up at idx 3 because 1+2 taken
333
334 // trigger insertion
335 table.asPropertyKey(str: entry1);
336 table.asPropertyKey(str: entry2);
337 table.asPropertyKey(str: entry3);
338 table.asPropertyKey(str: entry4);
339
340 QCOMPARE(table.size, 4u);
341 QCOMPARE(table.alloc, 11u);
342
343 QCOMPARE(table.entriesByHash[0], entry1);
344 QCOMPARE(table.entriesByHash[1], entry2);
345 QCOMPARE(table.entriesByHash[2], entry3);
346 QCOMPARE(table.entriesByHash[3], entry4);
347 QCOMPARE(table.entriesByHash[4], nullptr);
348
349 // first entry not marked
350 entry2->setMarkBit();
351 entry3->setMarkBit();
352 entry4->setMarkBit();
353
354 table.sweep();
355
356 QCOMPARE(table.entriesByHash[0], entry2);
357 QCOMPARE(table.entriesByHash[1], entry3);
358 QCOMPARE(table.entriesByHash[2], entry4);
359 QCOMPARE(table.entriesByHash[3], nullptr);
360}
361
362QTEST_MAIN(tst_qv4identifiertable)
363
364#include "tst_qv4identifiertable.moc"
365

source code of qtdeclarative/tests/auto/qml/qv4identifiertable/tst_qv4identifiertable.cpp