tdf#88109 speed up calc autofill

switch from ScFlatUInt16RowSegments to ScCompressedArray

The problem with the underlying mdds::flat_segment_tree data structure
is that it is optimised for bulk-load and then frequent read.
But here we are interleaving reading and updating the data, which means
flat_segment_tree spends a lot of time in its build_tree code.

Change-Id: Ic0d46834a2449e4fa9f84343971417adb48ba2de
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/94694
Tested-by: Noel Grandin <noel.grandin@collabora.co.uk>
Reviewed-by: Noel Grandin <noel.grandin@collabora.co.uk>

6 files changed, 65 insertions, 35 deletions

diff --git a/sc/inc/compressedarray.hxx b/sc/inc/compressedarray.hxx
index 593aeb6e868d..91540d8391db 100644
--- a/sc/inc/compressedarray.hxx
+++ b/sc/inc/compressedarray.hxx
@@ -65,6 +65,11 @@ public:
         D   aValue;
             DataEntry() {}  //! uninitialized
     };
+    struct RangeData
+    {
+        A mnRow1, mnRow2;
+        D maValue;
+    };
 
     /** Construct with nMaxAccess=MAXROW, for example. */
                                 ScCompressedArray( A nMaxAccess,
@@ -82,6 +87,10 @@ public:
     [[nodiscard]]
     const D&                    GetValue( A nPos, size_t& nIndex, A& nEnd ) const;
 
+    /** Get range data for a row, i.e. value and start and end rows with that value */
+    [[nodiscard]]
+    RangeData                   GetRangeData( A nPos ) const;
+
     /** Get next value and it's region end row. If nIndex<nCount, nIndex is
         incremented first. If the resulting nIndex>=nCount, the value of the
         last entry is returned again. */
@@ -150,6 +159,17 @@ const D& ScCompressedArray<A,D>::GetValue( A nPos, size_t& nIndex, A& nEnd ) con
 }
 
 template< typename A, typename D >
+typename ScCompressedArray<A,D>::RangeData ScCompressedArray<A,D>::GetRangeData( A nPos ) const
+{
+    size_t nIndex = Search( nPos);
+    RangeData aData;
+    aData.mnRow1 = nIndex == 0 ? 0 : pData[nIndex - 1].nEnd + 1;
+    aData.mnRow2 = pData[nIndex].nEnd;
+    aData.maValue = pData[nIndex].aValue;
+    return aData;
+}
+
+template< typename A, typename D >
 const D& ScCompressedArray<A,D>::GetNextValue( size_t& nIndex, A& nEnd ) const
 {
     if (nIndex < nCount)
diff --git a/sc/inc/rowheightcontext.hxx b/sc/inc/rowheightcontext.hxx
index 06da424c444c..054360396306 100644
--- a/sc/inc/rowheightcontext.hxx
+++ b/sc/inc/rowheightcontext.hxx
@@ -16,13 +16,16 @@
 #include <vcl/vclptr.hxx>
 #include <vcl/outdev.hxx>
 
-#include "segmenttree.hxx"
+#include "compressedarray.hxx"
+#include "types.hxx"
+
+using RowHeightsArray = ScCompressedArray<SCROW, sal_uInt16>;
 
 namespace sc {
 
 class SC_DLLPUBLIC RowHeightContext
 {
-    ScFlatUInt16RowSegments maHeights;
+    RowHeightsArray maHeights;
 
     double mfPPTX;
     double mfPPTY;
@@ -53,7 +56,7 @@ public:
     void setForceAutoSize( bool b );
     bool isForceAutoSize() const { return mbForceAutoSize;}
 
-    ScFlatUInt16RowSegments& getHeightArray();
+    RowHeightsArray& getHeightArray() { return maHeights; }
 };
 
 }
diff --git a/sc/source/core/data/column2.cxx b/sc/source/core/data/column2.cxx
index 6d19daf40fa5..61a756699081 100644
--- a/sc/source/core/data/column2.cxx
+++ b/sc/source/core/data/column2.cxx
@@ -783,7 +783,7 @@ void ScColumn::GetOptimalHeight(
     sc::RowHeightContext& rCxt, SCROW nStartRow, SCROW nEndRow, sal_uInt16 nMinHeight, SCROW nMinStart )
 {
     ScDocument* pDocument = GetDoc();
-    ScFlatUInt16RowSegments& rHeights = rCxt.getHeightArray();
+    RowHeightsArray& rHeights = rCxt.getHeightArray();
     ScAttrIterator aIter( pAttrArray.get(), nStartRow, nEndRow, pDocument->GetDefPattern() );
 
     SCROW nStart = -1;
@@ -883,7 +883,20 @@ void ScColumn::GetOptimalHeight(
                     nStdEnd = (nMinStart>0) ? nMinStart-1 : 0;
 
                 if (nStart <= nStdEnd)
-                    rHeights.setValueIf(nStart, nStdEnd, nDefHeight, [=](sal_uInt16 nRowHeight){ return nDefHeight > nRowHeight; });
+                {
+                    SCROW nRow = nStart;
+                    for (;;)
+                    {
+                        size_t nIndex;
+                        SCROW nRangeEnd;
+                        sal_uInt16 nRangeHeight = rHeights.GetValue(nRow, nIndex, nRangeEnd);
+                        if (nRangeHeight < nDefHeight)
+                            rHeights.SetValue(nRow, std::min(nRangeEnd, nStdEnd), nDefHeight);
+                        nRow = nRangeEnd + 1;
+                        if (nRow > nStdEnd)
+                            break;
+                    }
+                }
 
                 if ( bStdOnly )
                 {
@@ -903,22 +916,22 @@ void ScColumn::GetOptimalHeight(
                             {
                                 if ( nCjkHeight == 0 )
                                     nCjkHeight = lcl_GetAttribHeight( *pPattern, ATTR_CJK_FONT_HEIGHT );
-                                if (nCjkHeight > rHeights.getValue(nRow))
-                                    rHeights.setValue(nRow, nRow, nCjkHeight);
+                                if (nCjkHeight > rHeights.GetValue(nRow))
+                                    rHeights.SetValue(nRow, nRow, nCjkHeight);
                             }
                             else if ( nScript == SvtScriptType::COMPLEX )
                             {
                                 if ( nCtlHeight == 0 )
                                     nCtlHeight = lcl_GetAttribHeight( *pPattern, ATTR_CTL_FONT_HEIGHT );
-                                if (nCtlHeight > rHeights.getValue(nRow))
-                                    rHeights.setValue(nRow, nRow, nCtlHeight);
+                                if (nCtlHeight > rHeights.GetValue(nRow))
+                                    rHeights.SetValue(nRow, nRow, nCtlHeight);
                             }
                             else
                             {
                                 if ( nLatHeight == 0 )
                                     nLatHeight = lcl_GetAttribHeight( *pPattern, ATTR_FONT_HEIGHT );
-                                if (nLatHeight > rHeights.getValue(nRow))
-                                    rHeights.setValue(nRow, nRow, nLatHeight);
+                                if (nLatHeight > rHeights.GetValue(nRow))
+                                    rHeights.SetValue(nRow, nRow, nLatHeight);
                             }
                         }
                     }
@@ -945,8 +958,8 @@ void ScColumn::GetOptimalHeight(
                                                    rCxt.getZoomX(), rCxt.getZoomY(), false, aOptions,
                                                    &pPattern) / rCxt.getPPTY(),
                                     double(std::numeric_limits<sal_uInt16>::max())));
-                            if (nHeight > rHeights.getValue(nRow))
-                                rHeights.setValue(nRow, nRow, nHeight);
+                            if (nHeight > rHeights.GetValue(nRow))
+                                rHeights.SetValue(nRow, nRow, nHeight);
                             // Pattern changed due to calculation? => sync.
                             if (pPattern != pOldPattern)
                             {
diff --git a/sc/source/core/data/compressedarray.cxx b/sc/source/core/data/compressedarray.cxx
index 2016478d9194..914a6c52eb1f 100644
--- a/sc/source/core/data/compressedarray.cxx
+++ b/sc/source/core/data/compressedarray.cxx
@@ -417,6 +417,7 @@ template class ScCompressedArray< SCROW, CRFlags>;             // flags, base cl
 template class ScBitMaskCompressedArray< SCROW, CRFlags>;      // flags
 template class ScCompressedArray< SCCOL, sal_uInt16>;
 template class ScCompressedArray< SCCOL, CRFlags>;
+template class ScCompressedArray< SCROW, sal_uInt16>;
 template class ScBitMaskCompressedArray< SCCOL, CRFlags>;
 
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/source/core/data/rowheightcontext.cxx b/sc/source/core/data/rowheightcontext.cxx
index 86d2ab1da082..c5f615c666c2 100644
--- a/sc/source/core/data/rowheightcontext.cxx
+++ b/sc/source/core/data/rowheightcontext.cxx
@@ -33,11 +33,6 @@ void RowHeightContext::setForceAutoSize( bool b )
     mbForceAutoSize = b;
 }
 
-ScFlatUInt16RowSegments& RowHeightContext::getHeightArray()
-{
-    return maHeights;
-}
-
 }
 
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/source/core/data/table1.cxx b/sc/source/core/data/table1.cxx
index c40ce2467724..022a57f2503f 100644
--- a/sc/source/core/data/table1.cxx
+++ b/sc/source/core/data/table1.cxx
@@ -94,16 +94,15 @@ void GetOptimalHeightsInColumn(
 
     //  from there search for the standard height that is in use in the lower part
 
-    ScFlatUInt16RowSegments& rHeights = rCxt.getHeightArray();
-    sal_uInt16 nMinHeight = rHeights.getValue(nEndRow);
-    SCSIZE nPos = nEndRow-1;
-    ScFlatUInt16RowSegments::RangeData aRangeData;
-    while ( nPos && rHeights.getRangeData(nPos-1, aRangeData) )
-    {
-        if (aRangeData.mnValue >= nMinHeight)
-            nPos = std::max<SCSIZE>(0, aRangeData.mnRow1);
-        else
+    RowHeightsArray& rHeights = rCxt.getHeightArray();
+    sal_uInt16 nMinHeight = rHeights.GetValue(nEndRow);
+    SCSIZE nPos = nEndRow - 1;
+    while ( nPos )
+    {
+        auto aRangeData = rHeights.GetRangeData(nPos-1);
+        if (aRangeData.maValue < nMinHeight)
             break;
+        nPos = std::max<SCSIZE>(0, aRangeData.mnRow1);
     }
 
     const SCROW nMinStart = nPos;
@@ -192,12 +191,13 @@ bool SetOptimalHeightsToRows(
             {
                 if (nLast)
                 {
-                    ScFlatUInt16RowSegments::RangeData aRangeData;
-                    (void)rCxt.getHeightArray().getRangeData(nInner, aRangeData);
-                    if (aRangeData.mnValue + nExtraHeight == nLast)
+                    SCROW nRangeRowEnd;
+                    size_t nTmp;
+                    sal_uInt16 nRangeValue = rCxt.getHeightArray().GetValue(nInner, nTmp, nRangeRowEnd);
+                    if (nRangeValue + nExtraHeight == nLast)
                     {
-                        nRngEnd = std::min<SCSIZE>(i + nMoreRows, aRangeData.mnRow2);
-                        nInner = aRangeData.mnRow2;
+                        nRngEnd = std::min<SCSIZE>(i + nMoreRows, nRangeRowEnd);
+                        nInner = nRangeRowEnd;
                     }
                     else
                     {
@@ -207,7 +207,7 @@ bool SetOptimalHeightsToRows(
                 }
                 if (!nLast)
                 {
-                    nLast = rCxt.getHeightArray().getValue(nInner) + rCxt.getExtraHeight();
+                    nLast = rCxt.getHeightArray().GetValue(nInner) + rCxt.getExtraHeight();
                     nRngStart = nInner;
                     nRngEnd = nInner;
                 }
@@ -466,7 +466,6 @@ bool ScTable::SetOptimalHeight(
 
     GetOptimalHeightsInColumn(rCxt, aCol, nStartRow, nEndRow, pProgress, nProgressStart);
 
-    rCxt.getHeightArray().enableTreeSearch(true);
     SetRowHeightRangeFunc aFunc(this, rCxt.getPPTY());
     bool bChanged = SetOptimalHeightsToRows(rCxt, aFunc, pRowFlags.get(), nStartRow, nEndRow);
 
@@ -494,7 +493,6 @@ void ScTable::SetOptimalHeightOnly(
 
     SetRowHeightOnlyFunc aFunc(this);
 
-    rCxt.getHeightArray().enableTreeSearch(true);
     SetOptimalHeightsToRows(rCxt, aFunc, pRowFlags.get(), nStartRow, nEndRow);
 
     if ( pProgress != pOuterProgress )