Q[Multi]Hash: fix squeeze()

When calling QHash::reserve(), or when creating the
internal QHashPrivate::Data structure, the value 0
for the size parameter is reserved for performing
the squeeze operation.

However commit 8a984ab772dd194e39094e728b869e65912912a7
broke it, by using the 0 value in QHashPrivate::Data
constructors as a mark that no resizing needs to be done.

This patch reverts the problematic commit (also applying
some later fixes to the code), and adds the missing
tests for Q[Multi]Hash::squeeze().

Change-Id: Id644df7b2beb008e6a37b2c89b709adfbd893e25
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
(cherry picked from commit 7c9afa8d00cc2bbc1b102eef6e76c23e07c7833f)
Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>

2 files changed, 123 insertions, 15 deletions

diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h
index 9b46fc5c0f..49d9d8f228 100644
--- a/src/corelib/tools/qhash.h
+++ b/src/corelib/tools/qhash.h
@@ -479,25 +479,16 @@ struct Data
         spans = new Span[nSpans];
         seed = QHashSeed::globalSeed();
     }
-    Data(const Data &other, size_t reserved = 0)
-        : size(other.size),
-          numBuckets(other.numBuckets),
-          seed(other.seed)
-    {
-        if (reserved)
-            numBuckets = GrowthPolicy::bucketsForCapacity(qMax(size, reserved));
-        bool resized = numBuckets != other.numBuckets;
-        size_t nSpans = (numBuckets + Span::LocalBucketMask) / Span::NEntries;
-        spans = new Span[nSpans];
-        size_t otherNSpans = (other.numBuckets + Span::LocalBucketMask) / Span::NEntries;
 
-        for (size_t s = 0; s < otherNSpans; ++s) {
+    void reallocationHelper(const Data &other, size_t nSpans, bool resized)
+    {
+        for (size_t s = 0; s < nSpans; ++s) {
             const Span &span = other.spans[s];
             for (size_t index = 0; index < Span::NEntries; ++index) {
                 if (!span.hasNode(index))
                     continue;
                 const Node &n = span.at(index);
-                iterator it = resized ? find(n.key) : iterator{ this, s*Span::NEntries + index };
+                iterator it = resized ? find(n.key) : iterator { this, s * Span::NEntries + index };
                 Q_ASSERT(it.isUnused());
                 Node *newNode = spans[it.span()].insert(it.index());
                 new (newNode) Node(n);
@@ -505,7 +496,31 @@ struct Data
         }
     }
 
-    static Data *detached(Data *d, size_t size = 0)
+    Data(const Data &other) : size(other.size), numBuckets(other.numBuckets), seed(other.seed)
+    {
+        size_t nSpans = (numBuckets + Span::LocalBucketMask) / Span::NEntries;
+        spans = new Span[nSpans];
+        reallocationHelper(other, nSpans, false);
+    }
+    Data(const Data &other, size_t reserved) : size(other.size), seed(other.seed)
+    {
+        numBuckets = GrowthPolicy::bucketsForCapacity(qMax(size, reserved));
+        size_t nSpans = (numBuckets + Span::LocalBucketMask) / Span::NEntries;
+        spans = new Span[nSpans];
+        size_t otherNSpans = (other.numBuckets + Span::LocalBucketMask) / Span::NEntries;
+        reallocationHelper(other, otherNSpans, true);
+    }
+
+    static Data *detached(Data *d)
+    {
+        if (!d)
+            return new Data;
+        Data *dd = new Data(*d);
+        if (!d->ref.deref())
+            delete d;
+        return dd;
+    }
+    static Data *detached(Data *d, size_t size)
     {
         if (!d)
             return new Data(size);
diff --git a/tests/auto/corelib/tools/qhash/tst_qhash.cpp b/tests/auto/corelib/tools/qhash/tst_qhash.cpp
index 9982c08392..d2b9174ddb 100644
--- a/tests/auto/corelib/tools/qhash/tst_qhash.cpp
+++ b/tests/auto/corelib/tools/qhash/tst_qhash.cpp
@@ -104,6 +104,9 @@ private slots:
     void detachAndReferences();
 
     void lookupUsingKeyIterator();
+
+    void squeeze();
+    void squeezeShared();
 };
 
 struct IdentityTracker {
@@ -2667,7 +2670,7 @@ void tst_QHash::reserveLessThanCurrentAmount()
 
         // Make sure that hash still has all elements
         for (int i = 0; i < 1000; ++i)
-            QCOMPARE(hash.values(i), QList<int>() << i * 10 + 1 << i * 10);
+            QCOMPARE(hash.values(i), QList<int>({ i * 10 + 1, i * 10 }));
     }
 }
 
@@ -2747,5 +2750,95 @@ void tst_QHash::lookupUsingKeyIterator()
         QVERIFY(!hash[*it].isEmpty());
 }
 
+void tst_QHash::squeeze()
+{
+    {
+        QHash<int, int> hash;
+        hash.reserve(1000);
+        for (int i = 0; i < 10; ++i)
+            hash.insert(i, i * 10);
+        QVERIFY(hash.isDetached());
+        const size_t buckets = hash.bucket_count();
+        const qsizetype size = hash.size();
+
+        hash.squeeze();
+
+        QVERIFY(hash.bucket_count() < buckets);
+        QCOMPARE(hash.size(), size);
+        for (int i = 0; i < size; ++i)
+            QCOMPARE(hash.value(i), i * 10);
+    }
+    {
+        QMultiHash<int, int> hash;
+        hash.reserve(1000);
+        for (int i = 0; i < 10; ++i) {
+            hash.insert(i, i * 10);
+            hash.insert(i, i * 10 + 1);
+        }
+        QVERIFY(hash.isDetached());
+        const size_t buckets = hash.bucket_count();
+        const qsizetype size = hash.size();
+
+        hash.squeeze();
+
+        QVERIFY(hash.bucket_count() < buckets);
+        QCOMPARE(hash.size(), size);
+        for (int i = 0; i < (size / 2); ++i)
+            QCOMPARE(hash.values(i), QList<int>({ i * 10 + 1, i * 10 }));
+    }
+}
+
+void tst_QHash::squeezeShared()
+{
+    {
+        QHash<int, int> hash;
+        hash.reserve(1000);
+        for (int i = 0; i < 10; ++i)
+            hash.insert(i, i * 10);
+
+        QHash<int, int> other = hash;
+
+        // Check that when squeezing a hash with shared d_ptr, the number of
+        // buckets actually decreases.
+        QVERIFY(!other.isDetached());
+        const size_t buckets = other.bucket_count();
+        const qsizetype size = other.size();
+
+        other.squeeze();
+
+        QCOMPARE(hash.bucket_count(), buckets);
+        QVERIFY(other.bucket_count() < buckets);
+
+        QCOMPARE(other.size(), size);
+        for (int i = 0; i < size; ++i)
+            QCOMPARE(other.value(i), i * 10);
+    }
+    {
+        QMultiHash<int, int> hash;
+        hash.reserve(1000);
+        for (int i = 0; i < 10; ++i) {
+            hash.insert(i, i * 10);
+            hash.insert(i, i * 10 + 1);
+        }
+
+        QMultiHash<int, int> other = hash;
+
+        // Check that when squeezing a hash with shared d_ptr, the number of
+        // buckets actually decreases.
+        QVERIFY(!other.isDetached());
+        const size_t buckets = other.bucket_count();
+        const qsizetype size = other.size();
+
+        other.squeeze();
+
+        QCOMPARE(hash.bucket_count(), buckets);
+        QVERIFY(other.bucket_count() < buckets);
+
+        QCOMPARE(other.size(), size);
+        for (int i = 0; i < (size / 2); ++i)
+            QCOMPARE(other.values(i), QList<int>({ i * 10 + 1, i * 10 }));
+    }
+}
+
 QTEST_APPLESS_MAIN(tst_QHash)
 #include "tst_qhash.moc"