qAllocMore: Always grow exponentially

qAllocMore is used by growing containers to allocate additional memory
for future growth. The previous algorithm would grow linearly in
increments of 8 up to 64 and then progress exponentially in powers of
two.

The new (constant time) algorithm does away with the linear segment and
always progresses exponentially. It also has the nice benefit of cleanly
avoiding undefined behaviour that the old implementation tried hard to
circumvent.

Besides always progressing exponentially, the next-power-of-two
algorithm was tweaked to always include space for growth. Previously
queries at boundary values (powers of two) would return the same value.

The test was updated to verify sanity of results. As the algorithm is
well behaved, testing of bogus data was dropped. Whatever happens in
those cases is irrelevant, anyway: the bug lives elsewhere.

Change-Id: I4def473cce4b438734887084e3c3bd8da0ff466b
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
Reviewed-by: Lars Knoll <lars.knoll@nokia.com>

1 files changed, 19 insertions, 12 deletions

diff --git a/tests/auto/corelib/tools/qbytearray/tst_qbytearray.cpp b/tests/auto/corelib/tools/qbytearray/tst_qbytearray.cpp
index 585d6afa44..4fb74a2af5 100644
--- a/tests/auto/corelib/tools/qbytearray/tst_qbytearray.cpp
+++ b/tests/auto/corelib/tools/qbytearray/tst_qbytearray.cpp
@@ -1075,18 +1075,25 @@ void tst_QByteArray::toULongLong()
 // global function defined in qbytearray.cpp
 void tst_QByteArray::qAllocMore()
 {
-    static const int t[] = {
-        INT_MIN, INT_MIN + 1, -1234567, -66000, -1025,
-        -3, -1, 0, +1, +3, +1025, +66000, +1234567, INT_MAX - 1, INT_MAX,
-        INT_MAX/3
-    };
-    static const int N = sizeof(t)/sizeof(t[0]);
-
-    // make sure qAllocMore() doesn't loop infinitely on any input
-    for (int i = 0; i < N; ++i) {
-        for (int j = 0; j < N; ++j) {
-            ::qAllocMore(t[i], t[j]);
-        }
+    using QT_PREPEND_NAMESPACE(qAllocMore);
+
+    // Not very important, but please behave :-)
+    QVERIFY(qAllocMore(0, 0) >= 0);
+
+    for (int i = 1; i < 1 << 8; i <<= 1)
+        QVERIFY(qAllocMore(i, 0) >= i);
+
+    for (int i = 1 << 8; i < 1 << 30; i <<= 1) {
+        const int alloc = qAllocMore(i, 0);
+
+        QVERIFY(alloc >= i);
+        QCOMPARE(qAllocMore(i - 8, 8), alloc - 8);
+        QCOMPARE(qAllocMore(i - 16, 16), alloc - 16);
+        QCOMPARE(qAllocMore(i - 24, 24), alloc - 24);
+        QCOMPARE(qAllocMore(i - 32, 32), alloc - 32);
+
+        QVERIFY(qAllocMore(i - 1, 0) >= i - 1);
+        QVERIFY(qAllocMore(i + 1, 0) >= i + 1);
     }
 }