Resolve Qt6 TODO items, replace Median and BlockSizeManager

* Replaces the, only internaly used, implementation of template
  class Median with a fixed size none templated version.
* Replaces BlockSizeManager with an updated BlockSizeManager V2,
  but keeping the original name.
* adapt the auto-test to take the fixed size array into account

Change-Id: If76cb944676c4a06a7566ad0bc37ded25b81c70c
Reviewed-by: Sona Kurazyan <sona.kurazyan@qt.io>

4 files changed, 41 insertions, 196 deletions

diff --git a/src/concurrent/qtconcurrentiteratekernel.cpp b/src/concurrent/qtconcurrentiteratekernel.cpp
index b65f712547..45b54ecfdc 100644
--- a/src/concurrent/qtconcurrentiteratekernel.cpp
+++ b/src/concurrent/qtconcurrentiteratekernel.cpp
@@ -48,8 +48,7 @@
 QT_BEGIN_NAMESPACE
 
 enum {
-    TargetRatio = 100,
-    MedianSize = 7
+    TargetRatio = 100
 };
 
 static qint64 getticks()
@@ -71,24 +70,12 @@ namespace QtConcurrent {
  */
 
 /*!
-  \class QtConcurrent::MedianDouble
-  \inmodule QtConcurrent
-  \internal
- */
-
-/*!
   \class QtConcurrent::BlockSizeManager
   \inmodule QtConcurrent
   \internal
  */
 
 /*!
-  \class QtConcurrent::BlockSizeManagerV2
-  \inmodule QtConcurrent
-  \internal
- */
-
-/*!
   \class QtConcurrent::ResultReporter
   \inmodule QtConcurrent
   \internal
@@ -116,66 +103,13 @@ namespace QtConcurrent {
 
 */
 BlockSizeManager::BlockSizeManager(int iterationCount)
-: maxBlockSize(iterationCount / (QThreadPool::globalInstance()->maxThreadCount() * 2)),
-  beforeUser(0), afterUser(0),
-  controlPartElapsed(MedianSize), userPartElapsed(MedianSize),
-  m_blockSize(1)
-{ }
-
-// Records the time before user code.
-void BlockSizeManager::timeBeforeUser()
-{
-    if (blockSizeMaxed())
-        return;
-
-    beforeUser = getticks();
-    controlPartElapsed.addValue(elapsed(beforeUser, afterUser));
-}
-
- // Records the time after user code and adjust the block size if we are spending
- // to much time in the for control code compared with the user code.
-void BlockSizeManager::timeAfterUser()
-{
-    if (blockSizeMaxed())
-        return;
-
-    afterUser = getticks();
-    userPartElapsed.addValue(elapsed(afterUser, beforeUser));
-
-    if (controlPartElapsed.isMedianValid() == false)
-        return;
-
-    if (controlPartElapsed.median() * TargetRatio < userPartElapsed.median())
-        return;
-
-    m_blockSize = qMin(m_blockSize * 2,  maxBlockSize);
-
-#ifdef QTCONCURRENT_FOR_DEBUG
-    qDebug() << QThread::currentThread() << "adjusting block size" << controlPartElapsed.median() << userPartElapsed.median() << m_blockSize;
-#endif
-
-    // Reset the medians after adjusting the block size so we get
-    // new measurements with the new block size.
-    controlPartElapsed.reset();
-    userPartElapsed.reset();
-}
-
-int BlockSizeManager::blockSize()
-{
-    return m_blockSize;
-}
-
-/*! \internal
-
-*/
-BlockSizeManagerV2::BlockSizeManagerV2(int iterationCount)
     : maxBlockSize(iterationCount / (QThreadPool::globalInstance()->maxThreadCount() * 2)),
       beforeUser(0), afterUser(0),
       m_blockSize(1)
 { }
 
 // Records the time before user code.
-void BlockSizeManagerV2::timeBeforeUser()
+void BlockSizeManager::timeBeforeUser()
 {
     if (blockSizeMaxed())
         return;
@@ -186,7 +120,7 @@ void BlockSizeManagerV2::timeBeforeUser()
 
  // Records the time after user code and adjust the block size if we are spending
  // to much time in the for control code compared with the user code.
-void BlockSizeManagerV2::timeAfterUser()
+void BlockSizeManager::timeAfterUser()
 {
     if (blockSizeMaxed())
         return;
@@ -212,7 +146,7 @@ void BlockSizeManagerV2::timeAfterUser()
     userPartElapsed.reset();
 }
 
-int BlockSizeManagerV2::blockSize()
+int BlockSizeManager::blockSize()
 {
     return m_blockSize;
 }
diff --git a/src/concurrent/qtconcurrentiteratekernel.h b/src/concurrent/qtconcurrentiteratekernel.h
index 3095c9ff52..09009efedc 100644
--- a/src/concurrent/qtconcurrentiteratekernel.h
+++ b/src/concurrent/qtconcurrentiteratekernel.h
@@ -61,37 +61,13 @@ namespace QtConcurrent {
     reserve and process at a time. This is done by measuring the time spent
     in the user code versus the control part code, and then increasing
     the block size if the ratio between them is to small. The block size
-    management is done on the basis of the median of several timing measuremens,
-    and it is done induvidualy for each thread.
+    management is done on the basis of the median of several timing measurements,
+    and it is done individually for each thread.
 */
 class Q_CONCURRENT_EXPORT BlockSizeManager
 {
 public:
-    BlockSizeManager(int iterationCount);
-    void timeBeforeUser();
-    void timeAfterUser();
-    int blockSize();
-private:
-    inline bool blockSizeMaxed()
-    {
-        return (m_blockSize >= maxBlockSize);
-    }
-
-    const int maxBlockSize;
-    qint64 beforeUser;
-    qint64 afterUser;
-    Median<double> controlPartElapsed;
-    Median<double> userPartElapsed;
-    int m_blockSize;
-
-    Q_DISABLE_COPY(BlockSizeManager)
-};
-
-// ### Qt6: Replace BlockSizeManager with V2 implementation
-class Q_CONCURRENT_EXPORT BlockSizeManagerV2
-{
-public:
-    explicit BlockSizeManagerV2(int iterationCount);
+    explicit BlockSizeManager(int iterationCount);
 
     void timeBeforeUser();
     void timeAfterUser();
@@ -106,11 +82,11 @@ private:
     const int maxBlockSize;
     qint64 beforeUser;
     qint64 afterUser;
-    MedianDouble controlPartElapsed;
-    MedianDouble userPartElapsed;
+    Median controlPartElapsed;
+    Median userPartElapsed;
     int m_blockSize;
 
-    Q_DISABLE_COPY(BlockSizeManagerV2)
+    Q_DISABLE_COPY(BlockSizeManager)
 };
 
 template <typename T>
@@ -221,7 +197,7 @@ public:
 
     ThreadFunctionResult forThreadFunction()
     {
-        BlockSizeManagerV2 blockSizeManager(iterationCount);
+        BlockSizeManager blockSizeManager(iterationCount);
         ResultReporter<T> resultReporter(this);
 
         for(;;) {
diff --git a/src/concurrent/qtconcurrentmedian.h b/src/concurrent/qtconcurrentmedian.h
index cec2431d6f..aab80794d9 100644
--- a/src/concurrent/qtconcurrentmedian.h
+++ b/src/concurrent/qtconcurrentmedian.h
@@ -42,97 +42,21 @@
 
 #include <QtConcurrent/qtconcurrent_global.h>
 
-#if !defined(QT_NO_CONCURRENT) ||defined(Q_CLANG_QDOC)
-
-#include <QtCore/qvector.h>
+#if !defined(QT_NO_CONCURRENT) || defined(Q_CLANG_QDOC)
 
 #include <algorithm>
+#include <cstring>
 
 QT_BEGIN_NAMESPACE
 
-
-
 namespace QtConcurrent {
 
-template <typename T>
 class Median
 {
 public:
-    Median(int _bufferSize)
-        : currentMedian(), bufferSize(_bufferSize), currentIndex(0), valid(false), dirty(true)
-    {
-        values.resize(bufferSize);
-    }
-
-    void reset()
-    {
-        values.fill(0);
-        currentIndex = 0;
-        valid = false;
-        dirty = true;
-    }
-
-    void addValue(T value)
-    {
-        currentIndex = ((currentIndex + 1) % bufferSize);
-        if (valid == false && currentIndex % bufferSize == 0)
-            valid = true;
-
-        // Only update the cached median value when we have to, that
-        // is when the new value is on then other side of the median
-        // compared to the current value at the index.
-        const T currentIndexValue = values[currentIndex];
-        if ((currentIndexValue > currentMedian && currentMedian > value)
-            || (currentMedian > currentIndexValue && value > currentMedian)) {
-            dirty = true;
-        }
-
-        values[currentIndex] = value;
-    }
-
-    bool isMedianValid() const
-    {
-        return valid;
-    }
-
-    T median()
-    {
-        if (dirty) {
-            dirty = false;
-
-// This is a workaround for http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58800
-// Avoid using std::nth_element for the affected stdlibc++ releases 4.7.3 and 4.8.2.
-// Note that the official __GLIBCXX__ value of the releases is not used since that
-// one might be patched on some GNU/Linux distributions.
-#if defined(__GLIBCXX__) && __GLIBCXX__ <= 20140107
-            QVector<T> sorted = values;
-            std::sort(sorted.begin(), sorted.end());
-            currentMedian = sorted.at(bufferSize / 2);
-#else
-            QVector<T> copy = values;
-            typename QVector<T>::iterator begin = copy.begin(), mid = copy.begin() + bufferSize/2, end = copy.end();
-            std::nth_element(begin, mid, end);
-            currentMedian = *mid;
-#endif
-        }
-        return currentMedian;
-    }
-private:
-    QVector<T> values;
-    T currentMedian;
-    int bufferSize;
-    int currentIndex;
-    bool valid;
-    bool dirty;
-};
-
-// ### Qt6: Drop Median<double> in favor of this faster MedianDouble
-class MedianDouble
-{
-public:
     enum { BufferSize = 7 };
 
-    MedianDouble()
+    Median()
         : currentMedian(), currentIndex(0), valid(false), dirty(true)
     {
         std::fill_n(values, static_cast<int>(BufferSize), 0.0);
@@ -195,7 +119,6 @@ private:
 
 } // namespace QtConcurrent
 
-
 QT_END_NAMESPACE
 
 #endif // QT_NO_CONCURRENT
diff --git a/tests/auto/concurrent/qtconcurrentmedian/tst_qtconcurrentmedian.cpp b/tests/auto/concurrent/qtconcurrentmedian/tst_qtconcurrentmedian.cpp
index f5ae80dca5..22e555d2db 100644
--- a/tests/auto/concurrent/qtconcurrentmedian/tst_qtconcurrentmedian.cpp
+++ b/tests/auto/concurrent/qtconcurrentmedian/tst_qtconcurrentmedian.cpp
@@ -39,33 +39,45 @@ private slots:
 
 void tst_QtConcurrentMedian::median_data()
 {
-    QTest::addColumn<QList<int> >("values");
-    QTest::addColumn<int>("expectedMedian");
+    QTest::addColumn<QList<double> >("values");
+    QTest::addColumn<double>("expectedMedian");
 
     QTest::newRow("size=1")
-        << (QList<int>() << 1)
-        << 1;
+        << (QList<double>() << 1.0)
+        << 0.0; // six 0.0 in front of the actual value
 
     QTest::newRow("size=2")
-        << (QList<int>() << 3 << 2)
-        << 3;
+        << (QList<double>() << 3.0 << 2.0)
+        << 0.0; // five 0.0 in front of the actual value
 
     QTest::newRow("size=3")
-        << (QList<int>() << 3 << 1 << 2)
-        << 2;
+        << (QList<double>() << 3.0 << 1.0 << 2.0)
+        << 0.0; // four 0.0 in front of the actual value
 
-    QTest::newRow("gcc bug 58800 (nth_element)")
-        << (QList<int>() << 207089 << 202585 << 180067 << 157549 << 211592 << 216096 << 207089)
-        << 207089;
+    QTest::newRow("size=4")
+        << (QList<double>() << 3.0 << 1.0 << 2.0 << 4.0)
+        << 1.0; // three 0.0 in front of the first actual value, pick 1.0
+
+    QTest::newRow("size=5")
+        << (QList<double>() << 3.0 << 1.0 << 2.0 << 3.0 << 1.0)
+        << 1.0; // two 0.0 in front of the first actual value, pick 1.0
+
+    QTest::newRow("size=6")
+        << (QList<double>() << 3.0 << 1.0 << 2.0 << 3.0 << 1.0 << 2.0)
+        << 2.0; // one 0.0 in front of the first actual value, pick 2.0
+
+    QTest::newRow("size=7")
+        << QList<double> { 207089.0, 202585.0, 180067.0, 157549.0, 211592.0, 216096.0, 207089.0 }
+        << 207089.0;
 }
 
 void tst_QtConcurrentMedian::median()
 {
-    QFETCH(QList<int> , values);
-    QFETCH(int, expectedMedian);
+    QFETCH(QList<double> , values);
+    QFETCH(double, expectedMedian);
 
-    QtConcurrent::Median<int> m(values.size());
-    foreach (int value, values)
+    QtConcurrent::Median m;
+    foreach (double value, values)
         m.addValue(value);
     QCOMPARE(m.median(), expectedMedian);
 }