[Libreoffice-commits] core.git: sc/inc sc/source
Markus Mohrhard
markus.mohrhard at googlemail.com
Thu Aug 4 12:58:32 UTC 2016
sc/inc/rowheightcontext.hxx | 6 ++-
sc/inc/segmenttree.hxx | 1
sc/source/core/data/colorscale.cxx | 1
sc/source/core/data/column2.cxx | 23 ++++++-------
sc/source/core/data/rowheightcontext.cxx | 3 +
sc/source/core/data/segmenttree.cxx | 25 ++++++++++++++
sc/source/core/data/table1.cxx | 54 +++++++++++++++++--------------
7 files changed, 75 insertions(+), 38 deletions(-)
New commits:
commit ef3ca1da6b6d994ea8c39f28a49a599f5cf67915
Author: Markus Mohrhard <markus.mohrhard at googlemail.com>
Date: Thu Aug 4 02:41:14 2016 +0200
save about 50% of the import time for nearly empty ods documents
It seems that currently most of the time is spent iterating through all
the cells to get the optimal row height. We can easily optimize by using
mdds::flat_segment_tree.
Now we don't need to iterate through all cells and instead can work on
whole blocks.
Change-Id: Id9a0686490b0e91ad6552b428c38a9f6635a7938
Reviewed-on: https://gerrit.libreoffice.org/27856
Tested-by: Jenkins <ci at libreoffice.org>
Reviewed-by: Markus Mohrhard <markus.mohrhard at googlemail.com>
diff --git a/sc/inc/rowheightcontext.hxx b/sc/inc/rowheightcontext.hxx
index f801ee4..d1a8f8f 100644
--- a/sc/inc/rowheightcontext.hxx
+++ b/sc/inc/rowheightcontext.hxx
@@ -18,11 +18,13 @@
#include <vector>
+#include "segmenttree.hxx"
+
namespace sc {
class SC_DLLPUBLIC RowHeightContext
{
- std::vector<sal_uInt16> maHeights;
+ ScFlatUInt16RowSegments maHeights;
double mfPPTX;
double mfPPTY;
@@ -53,7 +55,7 @@ public:
void setForceAutoSize( bool b );
bool isForceAutoSize() const { return mbForceAutoSize;}
- std::vector<sal_uInt16>& getHeightArray();
+ ScFlatUInt16RowSegments& getHeightArray();
};
}
diff --git a/sc/inc/segmenttree.hxx b/sc/inc/segmenttree.hxx
index 25eecec..897b4db 100644
--- a/sc/inc/segmenttree.hxx
+++ b/sc/inc/segmenttree.hxx
@@ -135,6 +135,7 @@ public:
~ScFlatUInt16RowSegments();
void setValue(SCROW nRow1, SCROW nRow2, sal_uInt16 nValue);
+ void setValueIf(SCROW nRow1, SCROW nRow2, sal_uInt16 nValue, const std::function<bool(sal_uInt16)>& rPredicate);
sal_uInt16 getValue(SCROW nRow);
sal_uInt32 getSumValue(SCROW nRow1, SCROW nRow2);
bool getRangeData(SCROW nRow, RangeData& rData);
diff --git a/sc/source/core/data/colorscale.cxx b/sc/source/core/data/colorscale.cxx
index da7f42e6..cfd6acf 100644
--- a/sc/source/core/data/colorscale.cxx
+++ b/sc/source/core/data/colorscale.cxx
@@ -956,6 +956,7 @@ ScIconSetInfo* ScIconSetFormat::GetIconSetInfo(const ScAddress& rAddr) const
nValMax = CalcValue(nMin, nMax, itr);
++itr;
}
+
if(nVal >= nValMax)
++nIndex;
diff --git a/sc/source/core/data/column2.cxx b/sc/source/core/data/column2.cxx
index d3ed5e4..cae1ff5 100644
--- a/sc/source/core/data/column2.cxx
+++ b/sc/source/core/data/column2.cxx
@@ -785,7 +785,7 @@ static sal_uInt16 lcl_GetAttribHeight( const ScPatternAttr& rPattern, sal_uInt16
void ScColumn::GetOptimalHeight(
sc::RowHeightContext& rCxt, SCROW nStartRow, SCROW nEndRow, sal_uInt16 nMinHeight, SCROW nMinStart )
{
- std::vector<sal_uInt16>& rHeights = rCxt.getHeightArray();
+ ScFlatUInt16RowSegments& rHeights = rCxt.getHeightArray();
ScAttrIterator aIter( pAttrArray, nStartRow, nEndRow );
SCROW nStart = -1;
@@ -887,9 +887,8 @@ void ScColumn::GetOptimalHeight(
if ( nDefHeight <= nMinHeight && nStdEnd >= nMinStart )
nStdEnd = (nMinStart>0) ? nMinStart-1 : 0;
- for (SCROW nRow = nStart; nRow <= nStdEnd; ++nRow)
- if (nDefHeight > rHeights[nRow-nStartRow])
- rHeights[nRow-nStartRow] = nDefHeight;
+ if (nStart <= nStdEnd)
+ rHeights.setValueIf(nStart, nStdEnd, nDefHeight, [=](sal_uInt16 nRowHeight){ return nDefHeight > nRowHeight; });
if ( bStdOnly )
{
@@ -910,22 +909,22 @@ void ScColumn::GetOptimalHeight(
{
if ( nCjkHeight == 0 )
nCjkHeight = lcl_GetAttribHeight( *pPattern, ATTR_CJK_FONT_HEIGHT );
- if (nCjkHeight > rHeights[nRow-nStartRow])
- rHeights[nRow-nStartRow] = 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[nRow-nStartRow])
- rHeights[nRow-nStartRow] = 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[nRow-nStartRow])
- rHeights[nRow-nStartRow] = nLatHeight;
+ if (nLatHeight > rHeights.getValue(nRow))
+ rHeights.setValue(nRow, nRow, nLatHeight);
}
}
}
@@ -951,8 +950,8 @@ void ScColumn::GetOptimalHeight(
( GetNeededSize( nRow, rCxt.getOutputDevice(), rCxt.getPPTX(), rCxt.getPPTY(),
rCxt.getZoomX(), rCxt.getZoomY(), false, aOptions,
&pPattern) / rCxt.getPPTY() );
- if (nHeight > rHeights[nRow-nStartRow])
- rHeights[nRow-nStartRow] = 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/rowheightcontext.cxx b/sc/source/core/data/rowheightcontext.cxx
index 46f3c6d..4cba0b9 100644
--- a/sc/source/core/data/rowheightcontext.cxx
+++ b/sc/source/core/data/rowheightcontext.cxx
@@ -14,6 +14,7 @@ namespace sc {
RowHeightContext::RowHeightContext(
double fPPTX, double fPPTY, const Fraction& rZoomX, const Fraction& rZoomY,
OutputDevice* pOutDev ) :
+ maHeights(0),
mfPPTX(fPPTX), mfPPTY(fPPTY),
maZoomX(rZoomX), maZoomY(rZoomY),
mpOutDev(pOutDev),
@@ -32,7 +33,7 @@ void RowHeightContext::setForceAutoSize( bool b )
mbForceAutoSize = b;
}
-std::vector<sal_uInt16>& RowHeightContext::getHeightArray()
+ScFlatUInt16RowSegments& RowHeightContext::getHeightArray()
{
return maHeights;
}
diff --git a/sc/source/core/data/segmenttree.cxx b/sc/source/core/data/segmenttree.cxx
index 7159d9c..98b2929 100644
--- a/sc/source/core/data/segmenttree.cxx
+++ b/sc/source/core/data/segmenttree.cxx
@@ -45,6 +45,7 @@ public:
~ScFlatSegmentsImpl();
bool setValue(SCCOLROW nPos1, SCCOLROW nPos2, ValueType nValue);
+ void setValueIf(SCCOLROW nPos1, SCCOLROW nPos2, ValueType nValue, const std::function<bool(ValueType)>& rPredicate);
ValueType getValue(SCCOLROW nPos);
ExtValueType getSumValue(SCCOLROW nPos1, SCCOLROW nPos2);
bool getRangeData(SCCOLROW nPos, RangeData& rData);
@@ -100,6 +101,25 @@ bool ScFlatSegmentsImpl<ValueType_, ExtValueType_>::setValue(SCCOLROW nPos1, SCC
}
template<typename ValueType_, typename ExtValueType_>
+void ScFlatSegmentsImpl<ValueType_, ExtValueType_>::setValueIf(SCCOLROW nPos1, SCCOLROW nPos2,
+ ValueType nValue, const std::function<bool(ValueType)>& rPredicate)
+{
+ SCCOLROW nCurrentStartRow = nPos1;
+ while (nCurrentStartRow <= nPos2)
+ {
+ RangeData aRangeData;
+ getRangeData(nCurrentStartRow, aRangeData);
+ if (rPredicate(aRangeData.mnValue))
+ {
+ setValue(nPos1, std::min<SCCOLROW>(nPos2, aRangeData.mnPos2), nValue);
+ }
+
+ // even if nPos2 is bigger than nPos2 this should terminate the loop
+ nCurrentStartRow = aRangeData.mnPos2 + 1;
+ }
+}
+
+template<typename ValueType_, typename ExtValueType_>
typename ScFlatSegmentsImpl<ValueType_, ExtValueType_>::ValueType ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getValue(SCCOLROW nPos)
{
ValueType nValue = 0;
@@ -516,4 +536,9 @@ void ScFlatUInt16RowSegments::enableTreeSearch(bool bEnable)
mpImpl->enableTreeSearch(bEnable);
}
+void ScFlatUInt16RowSegments::setValueIf(SCROW nRow1, SCROW nRow2, sal_uInt16 nValue, const std::function<bool(sal_uInt16)>& rPredicate)
+{
+ mpImpl->setValueIf(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2), nValue, rPredicate);
+}
+
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/source/core/data/table1.cxx b/sc/source/core/data/table1.cxx
index 597901d..f884dc3 100644
--- a/sc/source/core/data/table1.cxx
+++ b/sc/source/core/data/table1.cxx
@@ -86,23 +86,28 @@ void GetOptimalHeightsInColumn(
{
assert(nStartRow <= nEndRow);
- SCSIZE nCount = static_cast<SCSIZE>(nEndRow-nStartRow+1);
-
// first, one time over the whole range
// (with the last column in the hope that they most likely still are
// on standard format)
- std::vector<sal_uInt16>& rHeights = rCxt.getHeightArray();
rCol[MAXCOL].GetOptimalHeight(rCxt, nStartRow, nEndRow, 0, 0);
// from there search for the standard height that is in use in the lower part
- sal_uInt16 nMinHeight = rHeights[nCount-1];
- SCSIZE nPos = nCount-1;
- while ( nPos && rHeights[nPos-1] >= nMinHeight )
- --nPos;
- SCROW nMinStart = nStartRow + nPos;
+ 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
+ break;
+ }
+
+ SCROW nMinStart = nPos;
sal_uLong nWeightedCount = 0;
for (SCCOL nCol=0; nCol<MAXCOL; nCol++) // MAXCOL already above
@@ -164,20 +169,19 @@ bool SetOptimalHeightsToRows(
OptimalHeightsFuncObjBase& rFuncObj,
ScBitMaskCompressedArray<SCROW, sal_uInt8>* pRowFlags, SCROW nStartRow, SCROW nEndRow )
{
- SCSIZE nCount = static_cast<SCSIZE>(nEndRow-nStartRow+1);
bool bChanged = false;
SCROW nRngStart = 0;
SCROW nRngEnd = 0;
sal_uInt16 nLast = 0;
sal_uInt16 nExtraHeight = rCxt.getExtraHeight();
- for (SCSIZE i=0; i<nCount; i++)
+ for (SCSIZE i = nStartRow; i <= static_cast<SCSIZE>(nEndRow); i++)
{
size_t nIndex;
SCROW nRegionEndRow;
- sal_uInt8 nRowFlag = pRowFlags->GetValue( nStartRow+i, nIndex, nRegionEndRow );
+ sal_uInt8 nRowFlag = pRowFlags->GetValue( i, nIndex, nRegionEndRow );
if ( nRegionEndRow > nEndRow )
nRegionEndRow = nEndRow;
- SCSIZE nMoreRows = nRegionEndRow - ( nStartRow+i ); // additional equal rows after first
+ SCSIZE nMoreRows = nRegionEndRow - i; // additional equal rows after first
bool bAutoSize = ((nRowFlag & CR_MANUALSIZE) == 0);
if (bAutoSize || rCxt.isForceAutoSize())
@@ -185,17 +189,22 @@ bool SetOptimalHeightsToRows(
if (nExtraHeight)
{
if (bAutoSize)
- pRowFlags->SetValue( nStartRow+i, nRegionEndRow, nRowFlag | CR_MANUALSIZE);
+ pRowFlags->SetValue( i, nRegionEndRow, nRowFlag | CR_MANUALSIZE);
}
else if (!bAutoSize)
- pRowFlags->SetValue( nStartRow+i, nRegionEndRow, nRowFlag & ~CR_MANUALSIZE);
+ pRowFlags->SetValue( i, nRegionEndRow, nRowFlag & ~CR_MANUALSIZE);
for (SCSIZE nInner = i; nInner <= i + nMoreRows; ++nInner)
{
if (nLast)
{
- if (rCxt.getHeightArray()[nInner] + nExtraHeight == nLast)
- nRngEnd = nStartRow+nInner;
+ ScFlatUInt16RowSegments::RangeData aRangeData;
+ rCxt.getHeightArray().getRangeData(nInner, aRangeData);
+ if (aRangeData.mnValue + nExtraHeight == nLast)
+ {
+ nRngEnd = std::min<SCSIZE>(i + nMoreRows, aRangeData.mnRow2);
+ nInner = aRangeData.mnRow2;
+ }
else
{
bChanged |= rFuncObj(nRngStart, nRngEnd, nLast);
@@ -204,9 +213,9 @@ bool SetOptimalHeightsToRows(
}
if (!nLast)
{
- nLast = rCxt.getHeightArray()[nInner] + rCxt.getExtraHeight();
- nRngStart = nStartRow+nInner;
- nRngEnd = nStartRow+nInner;
+ nLast = rCxt.getHeightArray().getValue(nInner) + rCxt.getExtraHeight();
+ nRngStart = nInner;
+ nRngEnd = nInner;
}
}
}
@@ -480,10 +489,9 @@ bool ScTable::SetOptimalHeight(
ScProgress* pProgress = GetProgressBar(nCount, GetWeightedCount(), pOuterProgress, pDocument);
- rCxt.getHeightArray().resize(nCount, 0);
-
GetOptimalHeightsInColumn(rCxt, aCol, nStartRow, nEndRow, pProgress, nProgressStart);
+ rCxt.getHeightArray().enableTreeSearch(true);
SetRowHeightRangeFunc aFunc(this, rCxt.getPPTX(), rCxt.getPPTY());
bool bChanged = SetOptimalHeightsToRows(rCxt, aFunc, pRowFlags, nStartRow, nEndRow);
@@ -507,11 +515,11 @@ void ScTable::SetOptimalHeightOnly(
ScProgress* pProgress = GetProgressBar(nCount, GetWeightedCount(), pOuterProgress, pDocument);
- rCxt.getHeightArray().resize(nCount, 0);
-
GetOptimalHeightsInColumn(rCxt, aCol, nStartRow, nEndRow, pProgress, nProgressStart);
SetRowHeightOnlyFunc aFunc(this);
+
+ rCxt.getHeightArray().enableTreeSearch(true);
SetOptimalHeightsToRows(rCxt, aFunc, pRowFlags, nStartRow, nEndRow);
if ( pProgress != pOuterProgress )
More information about the Libreoffice-commits
mailing list