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 | |
34 | class tst_qv4identifiertable : public QObject |
35 | { |
36 | Q_OBJECT |
37 | |
38 | private slots: |
39 | void sweepFirstEntryInBucket(); |
40 | void sweepCenterEntryInBucket(); |
41 | void sweepLastEntryInBucket(); |
42 | void sweepFirstEntryInSameBucketWithDifferingHash(); |
43 | void dontSweepAcrossBucketBoundaries(); |
44 | void sweepAcrossBucketBoundariesIfFirstBucketFull(); |
45 | void sweepBucketGap(); |
46 | }; |
47 | |
48 | void 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 | |
91 | void 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 | |
134 | void 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 | |
177 | void 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 | |
214 | void 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 | |
252 | void 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 | |
305 | void 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 | |
362 | QTEST_MAIN(tst_qv4identifiertable) |
363 | |
364 | #include "tst_qv4identifiertable.moc" |
365 | |