From 24d851dcd2a140bf346343c5eb64d944cd1c1a87 Mon Sep 17 00:00:00 2001
From: Tobias Koenig <tobias.koenig@kdab.com>
Date: Tue, 19 Jan 2016 17:45:42 +0100
Subject: Avoid heap allocations in Median class

Create a MedianDouble class and V2 version of BlockSizeManager, which
use a fixed size array of double (since we always use 7 elements
to calculate the median anyway).

Change-Id: Ife90b90336a9a8c037b90726dee4cd2a1b8b6cd9
Reviewed-by: Marc Mutz <marc.mutz@kdab.com>
---
 src/concurrent/qtconcurrentmedian.h | 66 +++++++++++++++++++++++++++++++++++++
 1 file changed, 66 insertions(+)

(limited to 'src/concurrent/qtconcurrentmedian.h')

diff --git a/src/concurrent/qtconcurrentmedian.h b/src/concurrent/qtconcurrentmedian.h
index 2ae7954b7a..e35e2aec70 100644
--- a/src/concurrent/qtconcurrentmedian.h
+++ b/src/concurrent/qtconcurrentmedian.h
@@ -121,6 +121,72 @@ private:
     bool dirty;
 };
 
+// ### Qt6: Drop Median<double> in favor of this faster MedianDouble
+class MedianDouble
+{
+public:
+    enum { BufferSize = 7 };
+
+    MedianDouble()
+        : currentMedian(), currentIndex(0), valid(false), dirty(true)
+    {
+    }
+
+    void reset()
+    {
+        std::fill_n(values, static_cast<int>(BufferSize), 0.0);
+        currentIndex = 0;
+        valid = false;
+        dirty = true;
+    }
+
+    void addValue(double value)
+    {
+        ++currentIndex;
+        if (currentIndex == BufferSize) {
+            currentIndex = 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 double currentIndexValue = values[currentIndex];
+        if ((currentIndexValue > currentMedian && currentMedian > value)
+            || (currentMedian > currentIndexValue && value > currentMedian)) {
+            dirty = true;
+        }
+
+        values[currentIndex] = value;
+    }
+
+    bool isMedianValid() const
+    {
+        return valid;
+    }
+
+    double median()
+    {
+        if (dirty) {
+            dirty = false;
+
+            double sorted[BufferSize];
+            ::memcpy(&sorted, &values, sizeof(sorted));
+            std::sort(sorted, sorted + static_cast<int>(BufferSize));
+            currentMedian = sorted[BufferSize / 2];
+        }
+
+        return currentMedian;
+    }
+
+private:
+    double values[BufferSize];
+    double currentMedian;
+    int currentIndex;
+    bool valid;
+    bool dirty;
+};
+
 } // namespace QtConcurrent
 
 #endif //Q_QDOC
-- 
cgit v1.2.3