tdf#130326 speed up XLSX load in ScFlatSegmentsImpl

since we are iterating over the tree, use an iterator to speed
up subsequent lookups.

Takes my load time from 26.2s to 24.3s

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

1 files changed, 80 insertions, 27 deletions

diff --git a/sc/source/core/data/segmenttree.cxx b/sc/source/core/data/segmenttree.cxx
index d73d233d894c..3233a074ac06 100644
--- a/sc/source/core/data/segmenttree.cxx
+++ b/sc/source/core/data/segmenttree.cxx
@@ -146,41 +146,93 @@ template<typename ValueType_, typename ExtValueType_>
 typename ScFlatSegmentsImpl<ValueType_, ExtValueType_>::ExtValueType
 ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getSumValue(SCCOLROW nPos1, SCCOLROW nPos2)
 {
-    RangeData aData;
-    if (!getRangeData(nPos1, aData))
-        return 0;
-
-    sal_uInt32 nValue = 0;
-
-    SCROW nCurPos = nPos1;
-    SCROW nEndPos = aData.mnPos2;
-    while (nEndPos <= nPos2)
+    if (mbTreeSearchEnabled)
     {
-        sal_uInt32 nRes;
-        if (o3tl::checked_multiply<sal_uInt32>(aData.mnValue, nEndPos - nCurPos + 1, nRes))
+
+        if (!maSegments.is_tree_valid())
         {
-            SAL_WARN("sc.core", "row height overflow");
-            nRes = SAL_MAX_INT32;
+            assert(!ScGlobal::bThreadedGroupCalcInProgress);
+            maSegments.build_tree();
         }
-        nValue = o3tl::saturating_add(nValue, nRes);
-        nCurPos = nEndPos + 1;
-        if (!getRangeData(nCurPos, aData))
-            break;
 
-        nEndPos = aData.mnPos2;
+        RangeData aData;
+        auto [it, found] = maSegments.search_tree(nPos1, aData.mnValue, &aData.mnPos1, &aData.mnPos2);
+        if (!found)
+            return 0;
+        aData.mnPos2 = aData.mnPos2-1; // end point is not inclusive.
+
+        sal_uInt32 nValue = 0;
+
+        SCROW nCurPos = nPos1;
+        SCROW nEndPos = aData.mnPos2;
+        while (nEndPos <= nPos2)
+        {
+            sal_uInt32 nRes;
+            if (o3tl::checked_multiply<sal_uInt32>(aData.mnValue, nEndPos - nCurPos + 1, nRes))
+            {
+                SAL_WARN("sc.core", "row height overflow");
+                nRes = SAL_MAX_INT32;
+            }
+            nValue = o3tl::saturating_add(nValue, nRes);
+            nCurPos = nEndPos + 1;
+            auto itPair = maSegments.search(it, nCurPos, aData.mnValue, &aData.mnPos1, &aData.mnPos2);
+            if (!itPair.second)
+                break;
+            it = itPair.first;
+            aData.mnPos2 = aData.mnPos2-1; // end point is not inclusive.
+            nEndPos = aData.mnPos2;
+        }
+        if (nCurPos <= nPos2)
+        {
+            nEndPos = ::std::min(nEndPos, nPos2);
+            sal_uInt32 nRes;
+            if (o3tl::checked_multiply<sal_uInt32>(aData.mnValue, nEndPos - nCurPos + 1, nRes))
+            {
+                SAL_WARN("sc.core", "row height overflow");
+                nRes = SAL_MAX_INT32;
+            }
+            nValue = o3tl::saturating_add(nValue, nRes);
+        }
+        return nValue;
     }
-    if (nCurPos <= nPos2)
+    else
     {
-        nEndPos = ::std::min(nEndPos, nPos2);
-        sal_uInt32 nRes;
-        if (o3tl::checked_multiply<sal_uInt32>(aData.mnValue, nEndPos - nCurPos + 1, nRes))
+        RangeData aData;
+        if (!getRangeDataLeaf(nPos1, aData))
+            return 0;
+
+        sal_uInt32 nValue = 0;
+
+        SCROW nCurPos = nPos1;
+        SCROW nEndPos = aData.mnPos2;
+        while (nEndPos <= nPos2)
         {
-            SAL_WARN("sc.core", "row height overflow");
-            nRes = SAL_MAX_INT32;
+            sal_uInt32 nRes;
+            if (o3tl::checked_multiply<sal_uInt32>(aData.mnValue, nEndPos - nCurPos + 1, nRes))
+            {
+                SAL_WARN("sc.core", "row height overflow");
+                nRes = SAL_MAX_INT32;
+            }
+            nValue = o3tl::saturating_add(nValue, nRes);
+            nCurPos = nEndPos + 1;
+            if (!getRangeDataLeaf(nCurPos, aData))
+                break;
+
+            nEndPos = aData.mnPos2;
         }
-        nValue = o3tl::saturating_add(nValue, nRes);
+        if (nCurPos <= nPos2)
+        {
+            nEndPos = ::std::min(nEndPos, nPos2);
+            sal_uInt32 nRes;
+            if (o3tl::checked_multiply<sal_uInt32>(aData.mnValue, nEndPos - nCurPos + 1, nRes))
+            {
+                SAL_WARN("sc.core", "row height overflow");
+                nRes = SAL_MAX_INT32;
+            }
+            nValue = o3tl::saturating_add(nValue, nRes);
+        }
+        return nValue;
     }
-    return nValue;
 }
 
 template<typename ValueType_, typename ExtValueType_>
@@ -195,7 +247,8 @@ bool ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getRangeData(SCCOLROW nPos,
         maSegments.build_tree();
     }
 
-    if (!maSegments.search_tree(nPos, rData.mnValue, &rData.mnPos1, &rData.mnPos2).second)
+    auto it = maSegments.search_tree(nPos, rData.mnValue, &rData.mnPos1, &rData.mnPos2);
+    if (!it.second)
         return false;
 
     rData.mnPos2 = rData.mnPos2-1; // end point is not inclusive.