QHash: fix GrowthPolicy::bucketsForCapacity

It was confusing entry capacity with the bucket capacity. The value
maxNumBuckets() returned was the maximum number of entries. This issue
was harmless: we would just fail to cap the maximum to an allocatable
size. But the array new[] in the Data constructors would have capped the
maximum anyway (by way of throwing std::bad_alloc).

So instead of trying to calculate what the maximum bucket count is so we
can cap at that, simplify the calculation of the next power of 2 while
preventing it from overflowing in our calculations. We continue to rely
on new[] throwing when we return count that is larger than the maximum
allocatable.

This commit changes the load factor for QHashes containing exactly a
number of elements that is exactly a power of two. Previously, it would
be loaded at 50%, now it's at 25%. For this reason, tst_QSet::squeeze
needed to be fixed to depend less on the implementation details.

Pick-to: 6.5
Change-Id: I9671dee8ceb64aa9b9cafffd17415f3856c358a0
Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>

1 files changed, 20 insertions, 8 deletions

diff --git a/tests/auto/corelib/tools/qset/tst_qset.cpp b/tests/auto/corelib/tools/qset/tst_qset.cpp
index 734d1d491b..391e00485c 100644
--- a/tests/auto/corelib/tools/qset/tst_qset.cpp
+++ b/tests/auto/corelib/tools/qset/tst_qset.cpp
@@ -232,27 +232,39 @@ void tst_QSet::squeeze()
     set.squeeze();
     QVERIFY(set.capacity() < 100);
 
-    for (int i = 0; i < 512; ++i)
+    for (int i = 0; i < 500; ++i)
         set.insert(i);
-    QVERIFY(set.capacity() == 512);
+    QCOMPARE(set.size(), 500);
+
+    // squeezed capacity for 500 elements
+    qsizetype capacity = set.capacity();    // current implementation: 512
+    QCOMPARE_GE(capacity, set.size());
 
     set.reserve(50000);
-    QVERIFY(set.capacity() >= 50000);
+    QVERIFY(set.capacity() >= 50000);       // current implementation: 65536
 
     set.squeeze();
-    QVERIFY(set.capacity() == 512);
+    QCOMPARE(set.capacity(), capacity);
 
+    // removing elements does not shed capacity
     set.remove(499);
-    QVERIFY(set.capacity() == 512);
+    QCOMPARE(set.capacity(), capacity);
 
     set.insert(499);
-    QVERIFY(set.capacity() == 512);
+    QCOMPARE(set.capacity(), capacity);
 
-    set.insert(1000);
-    QVERIFY(set.capacity() == 1024);
+    // grow it beyond the current capacity
+    for (int i = set.size(); i <= capacity; ++i)
+        set.insert(i);
+    QCOMPARE(set.size(), capacity + 1);
+    QCOMPARE_GT(set.capacity(), capacity + 1);// current implementation: 2 * capacity (1024)
 
     for (int i = 0; i < 500; ++i)
         set.remove(i);
+
+    // removing elements does not shed capacity
+    QCOMPARE_GT(set.capacity(), capacity + 1);
+
     set.squeeze();
     QVERIFY(set.capacity() < 100);
 }