Another try at properly fixing IdentifierTable::sweep()

Sweeping the table in place is extremely tricky due to possible
holes and possible interleaving of identifiers with different
keys.

So do a straightforward algorithm instead, where we malloc a
new table and insert all marked identifiers into that new
table.

Change-Id: Id34f62f35408a505857d57d2e7e4811b335d5998
Task-number: QTBUG-70205
Reviewed-by: Erik Verbruggen <erik.verbruggen@qt.io>
Reviewed-by: Liang Qi <liang.qi@qt.io>

1 files changed, 15 insertions, 46 deletions

diff --git a/src/qml/jsruntime/qv4identifiertable.cpp b/src/qml/jsruntime/qv4identifiertable.cpp
index 7124a0a949..14a580462f 100644
--- a/src/qml/jsruntime/qv4identifiertable.cpp
+++ b/src/qml/jsruntime/qv4identifiertable.cpp
@@ -253,60 +253,29 @@ void IdentifierTable::markObjects(MarkStack *markStack)
 }
 
 template <typename Key>
-int sweepTable(Heap::StringOrSymbol **table, int alloc, std::function<Key(Heap::StringOrSymbol *)> f) {
+int sweepTable(Heap::StringOrSymbol **&table, int alloc, std::function<Key(Heap::StringOrSymbol *)> f) {
     int freed = 0;
-    uint lastKey = 0;
-
-    int lastEntry = -1;
-    int start = 0;
-    // start at an empty entry so we compress properly
-    for (; start < alloc; ++start) {
-        if (!table[start])
-            break;
-    }
-
-    bool shiftWithinBucket = false;
 
+    Heap::StringOrSymbol **newTable = (Heap::StringOrSymbol **)malloc(alloc*sizeof(Heap::String *));
+    memset(newTable, 0, alloc*sizeof(Heap::StringOrSymbol *));
     for (int i = 0; i < alloc; ++i) {
-        int idx = (i + start) % alloc;
-        Heap::StringOrSymbol *entry = table[idx];
-        if (!entry) {
-            lastEntry = -1;
+        Heap::StringOrSymbol *e = table[i];
+        if (!e)
             continue;
-        }
-        if (entry->isMarked()) {
-            if (lastEntry >= 0 && ((lastKey == f(entry) % alloc) || shiftWithinBucket)) {
-                Q_ASSERT(table[lastEntry] == nullptr);
-                table[lastEntry] = entry;
-                table[idx] = nullptr;
-
-                // find next free slot just like in addEntry()
-                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;
-            }
+        if (!e->isMarked()) {
+            ++freed;
             continue;
         }
-
-        shiftWithinBucket = false;
-
-        if (lastEntry == -1) {
-            lastEntry = idx;
-            lastKey = f(entry) % alloc;
+        uint idx = f(e) % alloc;
+        while (newTable[idx]) {
+            ++idx;
+            idx %= alloc;
         }
-        table[idx] = nullptr;
-        ++freed;
-    }
-    for (int i = 0; i < alloc; ++i) {
-        Heap::StringOrSymbol *entry = table[i];
-        if (!entry)
-            continue;
-        Q_ASSERT(entry->isMarked());
+        newTable[idx] = e;
     }
+    free(table);
+    table = newTable;
+
     return freed;
 }