diff options
| -rw-r--r-- | src/qml/jsruntime/qv4identifiertable.cpp | 11 | ||||
| -rw-r--r-- | tests/auto/qml/qv4identifiertable/tst_qv4identifiertable.cpp | 58 |
2 files changed, 68 insertions, 1 deletions
diff --git a/src/qml/jsruntime/qv4identifiertable.cpp b/src/qml/jsruntime/qv4identifiertable.cpp index 0412695404..7124a0a949 100644 --- a/src/qml/jsruntime/qv4identifiertable.cpp +++ b/src/qml/jsruntime/qv4identifiertable.cpp @@ -265,6 +265,8 @@ int sweepTable(Heap::StringOrSymbol **table, int alloc, std::function<Key(Heap:: break; } + bool shiftWithinBucket = false; + for (int i = 0; i < alloc; ++i) { int idx = (i + start) % alloc; Heap::StringOrSymbol *entry = table[idx]; @@ -273,7 +275,7 @@ int sweepTable(Heap::StringOrSymbol **table, int alloc, std::function<Key(Heap:: continue; } if (entry->isMarked()) { - if (lastEntry >= 0 && lastKey == (f(entry) % alloc)) { + if (lastEntry >= 0 && ((lastKey == f(entry) % alloc) || shiftWithinBucket)) { Q_ASSERT(table[lastEntry] == nullptr); table[lastEntry] = entry; table[idx] = nullptr; @@ -282,9 +284,16 @@ int sweepTable(Heap::StringOrSymbol **table, int alloc, std::function<Key(Heap:: do { lastEntry = (lastEntry + 1) % alloc; } while (table[lastEntry] != nullptr); + + // Avoid gaps within a bucket by enabling shift mode + // if we've caught up to the current index. + shiftWithinBucket = lastEntry == idx; } continue; } + + shiftWithinBucket = false; + if (lastEntry == -1) { lastEntry = idx; lastKey = f(entry) % alloc; diff --git a/tests/auto/qml/qv4identifiertable/tst_qv4identifiertable.cpp b/tests/auto/qml/qv4identifiertable/tst_qv4identifiertable.cpp index b2908ac5bb..095943cdc7 100644 --- a/tests/auto/qml/qv4identifiertable/tst_qv4identifiertable.cpp +++ b/tests/auto/qml/qv4identifiertable/tst_qv4identifiertable.cpp @@ -41,6 +41,7 @@ private slots: void sweepFirstEntryInSameBucketWithDifferingHash(); void dontSweepAcrossBucketBoundaries(); void sweepAcrossBucketBoundariesIfFirstBucketFull(); + void sweepBucketGap(); }; void tst_qv4identifiertable::sweepFirstEntryInBucket() @@ -300,6 +301,63 @@ void tst_qv4identifiertable::sweepAcrossBucketBoundariesIfFirstBucketFull() QCOMPARE(table.entriesByHash[3], nullptr); } +void tst_qv4identifiertable::sweepBucketGap() +{ + QV4::ExecutionEngine engine; + QV4::IdentifierTable table(&engine, /*numBits*/3); + + auto entry1 = engine.newString(QStringLiteral("one")); + auto entry2 = engine.newString(QStringLiteral("two")); + auto entry3 = engine.newString(QStringLiteral("three")); + auto entry4 = engine.newString(QStringLiteral("four")); + + entry1->createHashValue(); + entry2->createHashValue(); + entry3->createHashValue(); + entry4->createHashValue(); + + // We have two buckets where the second entry in the first bucket + // flows into the second bucket. So insertion into the second bucket + // will shift by one and create + // [entry1][entry2 (would map to first but overflows into second), entry3, entry4] + // Garbage collecting the first entry should not only move the second entry + // into its own first bucket (where there is space now), it is also critical to + // not leave a gap but move the third and fourth entries to the beginning of + // their bucket: + // [entry2][entry3, entry4] + entry1->stringHash = 0; // % 11 -> 0 + entry2->stringHash = 11; // % 11 -> 0, but ends up at idx 1 because 0 taken + entry3->stringHash = 12; // % 11 -> 1, but ends up at idx 2 because 1 taken + entry4->stringHash = 12; // % 11 -> 1, but ends up at idx 3 because 1+2 taken + + // trigger insertion + table.asPropertyKey(entry1); + table.asPropertyKey(entry2); + table.asPropertyKey(entry3); + table.asPropertyKey(entry4); + + QCOMPARE(table.size, 4); + QCOMPARE(table.alloc, 11); + + QCOMPARE(table.entriesByHash[0], entry1); + QCOMPARE(table.entriesByHash[1], entry2); + QCOMPARE(table.entriesByHash[2], entry3); + QCOMPARE(table.entriesByHash[3], entry4); + QCOMPARE(table.entriesByHash[4], nullptr); + + // first entry not marked + entry2->setMarkBit(); + entry3->setMarkBit(); + entry4->setMarkBit(); + + table.sweep(); + + QCOMPARE(table.entriesByHash[0], entry2); + QCOMPARE(table.entriesByHash[1], entry3); + QCOMPARE(table.entriesByHash[2], entry4); + QCOMPARE(table.entriesByHash[3], nullptr); +} + QTEST_MAIN(tst_qv4identifiertable) #include "tst_qv4identifiertable.moc" |