[Libreoffice-commits] core.git: sc/inc sc/source
Noel Grandin
noelgrandin at gmail.com
Tue Oct 17 06:55:38 UTC 2017
sc/inc/compressedarray.hxx | 29 ++++++++++-
sc/inc/table.hxx | 2
sc/source/core/data/compressedarray.cxx | 57 +++++++++++++++++++--
sc/source/core/data/table1.cxx | 4 -
sc/source/core/data/table2.cxx | 84 +++++++++++++++++---------------
sc/source/core/data/table5.cxx | 4 -
6 files changed, 127 insertions(+), 53 deletions(-)
New commits:
commit d6fb5ca5661195520ca7a7ca2d0145a1e11be099
Author: Noel Grandin <noelgrandin at gmail.com>
Date: Sat Oct 14 12:42:16 2017 +0200
dyncolcontainer: use ScCompressedArray for pColWidth
and enhance ScCompressedArray with an iterator to avoid
O(n^2) "for" loops.
Change-Id: I7d8fda8306b0a5c73bf373b3991e1c07271bc9d9
Reviewed-on: https://gerrit.libreoffice.org/43387
Tested-by: Jenkins <ci at libreoffice.org>
Reviewed-by: Noel Grandin <noel.grandin at collabora.co.uk>
diff --git a/sc/inc/compressedarray.hxx b/sc/inc/compressedarray.hxx
index e95c036991e7..86063049b774 100644
--- a/sc/inc/compressedarray.hxx
+++ b/sc/inc/compressedarray.hxx
@@ -29,7 +29,7 @@ const size_t nScCompressedArrayDelta = 4;
/** Compressed array of row (or column) entries, e.g. heights, flags, ...
- The array stores ranges of values such that consecutive values occupy only
+ The array stores ranges of values such that equal consecutive values occupy only
one entry. Initially it consists of one DataEntry with an implied start
row/column of 0 and an end row/column of access type maximum value.
@@ -48,6 +48,19 @@ const size_t nScCompressedArrayDelta = 4;
template< typename A, typename D > class ScCompressedArray
{
public:
+ class Iterator
+ {
+ friend ScCompressedArray;
+ const ScCompressedArray& mrArray;
+ size_t mnIndex = 0;
+ A mnRegion = 0;
+ Iterator(const ScCompressedArray& rArray) : mrArray(rArray) {}
+ Iterator(const ScCompressedArray& rArray, size_t nIndex, A nRegion) : mrArray(rArray), mnIndex(nIndex), mnRegion(nRegion) {}
+ public:
+ void operator++();
+ Iterator operator+(size_t) const;
+ const D & operator*() const { return mrArray.pData[mnIndex].aValue; }
+ };
struct DataEntry
{
A nEnd; // start is end of previous entry + 1
@@ -67,30 +80,42 @@ public:
void Reset( const D& rValue );
void SetValue( A nPos, const D& rValue );
void SetValue( A nStart, A nEnd, const D& rValue );
+ SAL_WARN_UNUSED_RESULT
const D& GetValue( A nPos ) const;
+ SAL_WARN_UNUSED_RESULT
+ A GetLastPos() const { return pData[nCount-1].nEnd; }
/** Get value for a row, and it's region end row */
+ SAL_WARN_UNUSED_RESULT
const D& GetValue( A nPos, size_t& nIndex, A& nEnd ) 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. */
+ SAL_WARN_UNUSED_RESULT
const D& GetNextValue( size_t& nIndex, A& nEnd ) const;
/** Insert rows before nStart and copy value for inserted rows from
nStart-1, return that value. */
const D& Insert( A nStart, size_t nCount );
+ void InsertPreservingSize( A nStart, size_t nCount, const D& rFillValue );
void Remove( A nStart, size_t nCount );
+ void RemovePreservingSize( A nStart, size_t nCount, const D& rFillValue );
/** Copy rArray.nStart+nSourceDy to this.nStart */
void CopyFrom( const ScCompressedArray& rArray,
- A nStart, A nEnd );
+ A nStart, A nEnd )
+ { CopyFrom(rArray, nStart, nEnd, nStart); }
+ void CopyFrom( const ScCompressedArray& rArray,
+ A nDestStart, A nDestEnd, A nSrcStart );
// methods public for the coupled array sum methods
/** Obtain index into entries for nPos */
SC_DLLPUBLIC size_t Search( A nPos ) const;
+ Iterator begin() const { return Iterator(*this); }
+
protected:
size_t nCount;
size_t nLimit;
diff --git a/sc/inc/table.hxx b/sc/inc/table.hxx
index 10974065d571..adf2a8743c2e 100644
--- a/sc/inc/table.hxx
+++ b/sc/inc/table.hxx
@@ -177,7 +177,7 @@ private:
std::unique_ptr<ScTableProtection> pTabProtection;
- std::unique_ptr<sal_uInt16[]> pColWidth;
+ std::unique_ptr<ScCompressedArray<SCCOL, sal_uInt16>> mpColWidth;
std::unique_ptr<ScFlatUInt16RowSegments> mpRowHeights;
std::unique_ptr<CRFlags[]> pColFlags;
diff --git a/sc/source/core/data/compressedarray.cxx b/sc/source/core/data/compressedarray.cxx
index 5cbcb6073bd7..0b5308a4fe26 100644
--- a/sc/source/core/data/compressedarray.cxx
+++ b/sc/source/core/data/compressedarray.cxx
@@ -238,18 +238,18 @@ void ScCompressedArray<A,D>::SetValue( A nStart, A nEnd, const D& rValue )
}
template< typename A, typename D >
-void ScCompressedArray<A,D>::CopyFrom( const ScCompressedArray<A,D>& rArray, A nStart,
- A nEnd )
+void ScCompressedArray<A,D>::CopyFrom( const ScCompressedArray<A,D>& rArray, A nDestStart,
+ A nDestEnd, A nSrcStart )
{
size_t nIndex = 0;
A nRegionEnd;
- for (A j=nStart; j<=nEnd; ++j)
+ for (A j=nDestStart; j<=nDestEnd; ++j)
{
- const D& rValue = (j==nStart ?
- rArray.GetValue( j, nIndex, nRegionEnd) :
+ const D& rValue = (j==nDestStart ?
+ rArray.GetValue( j - nDestStart + nSrcStart, nIndex, nRegionEnd) :
rArray.GetNextValue( nIndex, nRegionEnd));
- if (nRegionEnd > nEnd)
- nRegionEnd = nEnd;
+ if (nRegionEnd > nDestEnd)
+ nRegionEnd = nDestEnd;
this->SetValue( j, nRegionEnd, rValue);
j = nRegionEnd;
}
@@ -278,6 +278,19 @@ const D& ScCompressedArray<A,D>::Insert( A nStart, size_t nAccessCount )
}
template< typename A, typename D >
+void ScCompressedArray<A,D>::InsertPreservingSize( A nStart, size_t nAccessCount, const D& rFillValue )
+{
+ const A nPrevLastPos = GetLastPos();
+
+ Insert(nStart, nAccessCount);
+ for (A i = nStart; i < A(nStart + nAccessCount); ++i)
+ SetValue(i, rFillValue);
+
+ const A nNewLastPos = GetLastPos();
+ Remove(nPrevLastPos, nNewLastPos - nPrevLastPos);
+}
+
+template< typename A, typename D >
void ScCompressedArray<A,D>::Remove( A nStart, size_t nAccessCount )
{
A nEnd = nStart + nAccessCount - 1;
@@ -313,6 +326,35 @@ void ScCompressedArray<A,D>::Remove( A nStart, size_t nAccessCount )
pData[nCount-1].nEnd = nMaxAccess;
}
+template< typename A, typename D >
+void ScCompressedArray<A,D>::RemovePreservingSize( A nStart, size_t nAccessCount, const D& rFillValue )
+{
+ const A nPrevLastPos = GetLastPos();
+
+ Remove(nStart, nAccessCount);
+
+ const A nNewLastPos = GetLastPos();
+ InsertPreservingSize(nNewLastPos, nNewLastPos - nPrevLastPos, rFillValue);
+}
+
+template< typename A, typename D >
+void ScCompressedArray<A,D>::Iterator::operator++()
+{
+ ++mnRegion;
+ if (mnRegion > mrArray.pData[mnIndex].nEnd)
+ ++mnIndex;
+}
+
+template< typename A, typename D >
+typename ScCompressedArray<A,D>::Iterator ScCompressedArray<A,D>::Iterator::operator+(size_t nAccessCount) const
+{
+ A nRegion = mnRegion + nAccessCount;
+ auto nIndex = mnIndex;
+ while (nRegion > mrArray.pData[nIndex].nEnd)
+ ++nIndex;
+ return Iterator(mrArray, nIndex, nRegion);
+}
+
// === ScBitMaskCompressedArray ==============================================
template< typename A, typename D >
@@ -417,5 +459,6 @@ A ScBitMaskCompressedArray<A,D>::GetLastAnyBitAccess( const D& rBitMask ) const
template class ScCompressedArray< SCROW, CRFlags>; // flags, base class
template class ScBitMaskCompressedArray< SCROW, CRFlags>; // flags
+template class ScCompressedArray< SCCOL, sal_uInt16>;
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/source/core/data/table1.cxx b/sc/source/core/data/table1.cxx
index 876289faa95b..d99e2c7004e1 100644
--- a/sc/source/core/data/table1.cxx
+++ b/sc/source/core/data/table1.cxx
@@ -246,7 +246,6 @@ ScTable::ScTable( ScDocument* pDoc, SCTAB nNewTab, const OUString& rNewName,
nRepeatStartY( SCROW_REPEAT_NONE ),
nRepeatEndY( SCROW_REPEAT_NONE ),
pTabProtection( nullptr ),
- pColWidth( nullptr ),
mpRowHeights( static_cast<ScFlatUInt16RowSegments*>(nullptr) ),
pColFlags( nullptr ),
pRowFlags( nullptr ),
@@ -291,12 +290,11 @@ ScTable::ScTable( ScDocument* pDoc, SCTAB nNewTab, const OUString& rNewName,
if (bColInfo)
{
- pColWidth.reset( new sal_uInt16[ MAXCOL+1 ] );
+ mpColWidth.reset( new ScCompressedArray<SCCOL, sal_uInt16>( MAXCOL+1, STD_COL_WIDTH ) );
pColFlags.reset( new CRFlags[ MAXCOL+1 ] );
for (SCCOL i=0; i<=MAXCOL; i++)
{
- pColWidth[i] = STD_COL_WIDTH;
pColFlags[i] = CRFlags::NONE;
}
}
diff --git a/sc/source/core/data/table2.cxx b/sc/source/core/data/table2.cxx
index bf6ca8ffae94..6667aeaf213f 100644
--- a/sc/source/core/data/table2.cxx
+++ b/sc/source/core/data/table2.cxx
@@ -281,10 +281,9 @@ void ScTable::InsertCol(
{
if (nStartRow==0 && nEndRow==MAXROW)
{
- if (pColWidth && pColFlags)
+ if (mpColWidth && pColFlags)
{
- memmove( &pColWidth[nStartCol+nSize], &pColWidth[nStartCol],
- (MAXCOL - nStartCol + 1 - nSize) * sizeof(pColWidth[0]) );
+ mpColWidth->InsertPreservingSize(nStartCol, nSize, STD_COL_WIDTH);
memmove( &pColFlags[nStartCol+nSize], &pColFlags[nStartCol],
(MAXCOL - nStartCol + 1 - nSize) * sizeof(pColFlags[0]) );
}
@@ -357,11 +356,10 @@ void ScTable::DeleteCol(
{
if (nStartRow==0 && nEndRow==MAXROW)
{
- if (pColWidth && pColFlags)
+ if (mpColWidth && pColFlags)
{
assert( nStartCol + nSize <= MAXCOL+1 ); // moving 0 if ==MAXCOL+1 is correct
- memmove( &pColWidth[nStartCol], &pColWidth[nStartCol+nSize],
- (MAXCOL - nStartCol + 1 - nSize) * sizeof(pColWidth[0]) );
+ mpColWidth->RemovePreservingSize(nStartCol, nSize, STD_COL_WIDTH);
memmove( &pColFlags[nStartCol], &pColFlags[nStartCol+nSize],
(MAXCOL - nStartCol + 1 - nSize) * sizeof(pColFlags[0]) );
}
@@ -508,9 +506,8 @@ void ScTable::CopyToClip(
// copy widths/heights, and only "hidden", "filtered" and "manual" flags
// also for all preceding columns/rows, to have valid positions for drawing objects
- if (pColWidth && pTable->pColWidth)
- for (i=0; i<=nCol2; i++)
- pTable->pColWidth[i] = pColWidth[i];
+ if (mpColWidth && pTable->mpColWidth)
+ pTable->mpColWidth->CopyFrom(*mpColWidth, 0, nCol2);
pTable->CopyColHidden(*this, 0, nCol2);
pTable->CopyColFiltered(*this, 0, nCol2);
@@ -667,9 +664,8 @@ void ScTable::CopyFromClip(
if ((rCxt.getInsertFlag() & InsertDeleteFlags::ATTRIB) != InsertDeleteFlags::NONE)
{
- if (nRow1==0 && nRow2==MAXROW && pColWidth && pTable->pColWidth)
- for (SCCOL i=nCol1; i<=nCol2; i++)
- pColWidth[i] = pTable->pColWidth[i-nDx];
+ if (nRow1==0 && nRow2==MAXROW && mpColWidth && pTable->mpColWidth)
+ mpColWidth->CopyFrom(*pTable->mpColWidth, nCol1, nCol2, nCol1 - nDx);
if (nCol1==0 && nCol2==MAXCOL && mpRowHeights && pTable->mpRowHeights &&
pRowFlags && pTable->pRowFlags)
@@ -1124,19 +1120,21 @@ void ScTable::CopyToTable(
bool bFlagChange = false;
- bool bWidth = (nRow1==0 && nRow2==MAXROW && pColWidth && pDestTab->pColWidth);
+ bool bWidth = (nRow1==0 && nRow2==MAXROW && mpColWidth && pDestTab->mpColWidth);
bool bHeight = (nCol1==0 && nCol2==MAXCOL && mpRowHeights && pDestTab->mpRowHeights);
if (bWidth || bHeight)
{
if (bWidth)
{
+ auto destTabColWidthIt = pDestTab->mpColWidth->begin() + nCol1;
+ auto thisTabColWidthIt = mpColWidth->begin() + nCol1;
+ pDestTab->mpColWidth->CopyFrom(*mpColWidth, nCol1, nCol2);
for (SCCOL i = nCol1; i <= nCol2; ++i)
{
bool bThisHidden = ColHidden(i);
bool bHiddenChange = (pDestTab->ColHidden(i) != bThisHidden);
- bool bChange = bHiddenChange || (pDestTab->pColWidth[i] != pColWidth[i]);
- pDestTab->pColWidth[i] = pColWidth[i];
+ bool bChange = bHiddenChange || (*destTabColWidthIt != *thisTabColWidthIt);
pDestTab->pColFlags[i] = pColFlags[i];
pDestTab->SetColHidden(i, i, bThisHidden);
//TODO: collect changes?
@@ -1145,6 +1143,9 @@ void ScTable::CopyToTable(
if (bChange)
bFlagChange = true;
+
+ ++destTabColWidthIt;
+ ++thisTabColWidthIt;
}
pDestTab->SetColManualBreaks( maColManualBreaks);
}
@@ -1233,7 +1234,7 @@ void ScTable::UndoToTable(
{
if (ValidColRow(nCol1, nRow1) && ValidColRow(nCol2, nRow2))
{
- bool bWidth = (nRow1==0 && nRow2==MAXROW && pColWidth && pDestTab->pColWidth);
+ bool bWidth = (nRow1==0 && nRow2==MAXROW && mpColWidth && pDestTab->mpColWidth);
bool bHeight = (nCol1==0 && nCol2==MAXCOL && mpRowHeights && pDestTab->mpRowHeights);
for ( SCCOL i = 0; i < aCol.size(); i++)
@@ -1251,8 +1252,7 @@ void ScTable::UndoToTable(
{
if (bWidth)
{
- for (SCCOL i=nCol1; i<=nCol2; i++)
- pDestTab->pColWidth[i] = pColWidth[i];
+ pDestTab->mpColWidth->CopyFrom(*mpColWidth, nCol1, nCol2);
pDestTab->SetColManualBreaks( maColManualBreaks);
}
if (bHeight)
@@ -2091,7 +2091,7 @@ SCSIZE ScTable::FillMaxRot( RowInfo* pRowInfo, SCSIZE nArrCount, SCCOL nX1, SCCO
void ScTable::FindMaxRotCol( RowInfo* pRowInfo, SCSIZE nArrCount, SCCOL nX1, SCCOL nX2 )
{
- if ( !pColWidth || !mpRowHeights || !pColFlags || !pRowFlags )
+ if ( !mpColWidth || !mpRowHeights || !pColFlags || !pRowFlags )
{
OSL_FAIL( "Row/column info missing" );
return;
@@ -2762,16 +2762,16 @@ void ScTable::ClearSelectionItems( const sal_uInt16* pWhich, const ScMarkData& r
void ScTable::SetColWidth( SCCOL nCol, sal_uInt16 nNewWidth )
{
- if (ValidCol(nCol) && pColWidth)
+ if (ValidCol(nCol) && mpColWidth)
{
if (!nNewWidth)
{
nNewWidth = STD_COL_WIDTH;
}
- if ( nNewWidth != pColWidth[nCol] )
+ if ( nNewWidth != mpColWidth->GetValue(nCol) )
{
- pColWidth[nCol] = nNewWidth;
+ mpColWidth->SetValue(nCol, nNewWidth);
InvalidatePageBreaks();
}
}
@@ -2783,14 +2783,14 @@ void ScTable::SetColWidth( SCCOL nCol, sal_uInt16 nNewWidth )
void ScTable::SetColWidthOnly( SCCOL nCol, sal_uInt16 nNewWidth )
{
- if (!ValidCol(nCol) || !pColWidth)
+ if (!ValidCol(nCol) || !mpColWidth)
return;
if (!nNewWidth)
nNewWidth = STD_COL_WIDTH;
- if (nNewWidth != pColWidth[nCol])
- pColWidth[nCol] = nNewWidth;
+ if (nNewWidth != mpColWidth->GetValue(nCol))
+ mpColWidth->SetValue(nCol, nNewWidth);
}
void ScTable::SetRowHeight( SCROW nRow, sal_uInt16 nNewHeight )
@@ -2944,12 +2944,12 @@ sal_uInt16 ScTable::GetColWidth( SCCOL nCol, bool bHiddenAsZero ) const
{
OSL_ENSURE(ValidCol(nCol),"wrong column number");
- if (ValidCol(nCol) && pColFlags && pColWidth)
+ if (ValidCol(nCol) && pColFlags && mpColWidth)
{
if (bHiddenAsZero && ColHidden(nCol))
return 0;
else
- return pColWidth[nCol];
+ return mpColWidth->GetValue(nCol);
}
else
return (sal_uInt16) STD_COL_WIDTH;
@@ -2963,7 +2963,8 @@ sal_uLong ScTable::GetColWidth( SCCOL nStartCol, SCCOL nEndCol ) const
sal_uLong nW = 0;
bool bHidden = false;
SCCOL nLastHiddenCol = -1;
- for (SCCOL nCol = nStartCol; nCol <= nEndCol; ++nCol)
+ auto colWidthIt = mpColWidth->begin() + nStartCol;
+ for (SCCOL nCol = nStartCol; nCol <= nEndCol; ++nCol, ++colWidthIt)
{
if (nCol > nLastHiddenCol)
bHidden = ColHidden(nCol, nullptr, &nLastHiddenCol);
@@ -2971,7 +2972,7 @@ sal_uLong ScTable::GetColWidth( SCCOL nStartCol, SCCOL nEndCol ) const
if (bHidden)
continue;
- nW += pColWidth[nCol];
+ nW += *colWidthIt;
}
return nW;
}
@@ -2980,8 +2981,8 @@ sal_uInt16 ScTable::GetOriginalWidth( SCCOL nCol ) const // always the se
{
OSL_ENSURE(ValidCol(nCol),"wrong column number");
- if (ValidCol(nCol) && pColWidth)
- return pColWidth[nCol];
+ if (ValidCol(nCol) && mpColWidth)
+ return mpColWidth->GetValue(nCol);
else
return (sal_uInt16) STD_COL_WIDTH;
}
@@ -3007,16 +3008,21 @@ sal_uInt16 ScTable::GetCommonWidth( SCCOL nEndCol ) const
if ( nRangeStart <= nEndCol )
{
sal_uInt16 nThisCount = 0;
- sal_uInt16 nThisWidth = pColWidth[nRangeStart];
+ auto colWidthIt = mpColWidth->begin() + nRangeStart;
+ sal_uInt16 nThisWidth = *colWidthIt;
SCCOL nRangeEnd = nRangeStart;
- while ( nRangeEnd <= nEndCol && pColWidth[nRangeEnd] == nThisWidth )
+ while ( nRangeEnd <= nEndCol && *colWidthIt == nThisWidth )
{
++nThisCount;
++nRangeEnd;
+ ++colWidthIt;
// skip hidden columns
while ( nRangeEnd <= nEndCol && ColHidden(nRangeEnd) )
+ {
++nRangeEnd;
+ ++colWidthIt;
+ }
}
if ( nThisCount > nMaxCount )
@@ -3401,8 +3407,9 @@ SCCOL ScTable::GetLastChangedCol() const
return 0;
SCCOL nLastFound = 0;
- for ( SCCOL nCol = 1; nCol < aCol.size(); nCol++ )
- if ((pColFlags[nCol] & CRFlags::All) || (pColWidth[nCol] != STD_COL_WIDTH))
+ auto colWidthIt = mpColWidth->begin() + 1;
+ for ( SCCOL nCol = 1; nCol < aCol.size(); nCol++, ++colWidthIt )
+ if ((pColFlags[nCol] & CRFlags::All) || (*colWidthIt != STD_COL_WIDTH))
nLastFound = nCol;
return nLastFound;
@@ -3815,12 +3822,13 @@ SCROW ScTable::GetRowForHeight(sal_uLong nHeight) const
sal_uLong ScTable::GetColOffset( SCCOL nCol, bool bHiddenAsZero ) const
{
sal_uLong n = 0;
- if ( pColWidth )
+ if ( mpColWidth )
{
SCCOL i;
- for( i = 0; i < nCol; i++ )
+ auto colWidthIt = mpColWidth->begin();
+ for( i = 0; i < nCol; i++, ++colWidthIt )
if (!( bHiddenAsZero && ColHidden(i) ))
- n += pColWidth[i];
+ n += *colWidthIt;
}
else
{
diff --git a/sc/source/core/data/table5.cxx b/sc/source/core/data/table5.cxx
index 7d66956eef23..b224e6e2ea5e 100644
--- a/sc/source/core/data/table5.cxx
+++ b/sc/source/core/data/table5.cxx
@@ -166,7 +166,7 @@ void ScTable::UpdatePageBreaks( const ScRange* pUserArea )
for (SCCOL nX=nStartCol; nX<=nEndCol; nX++)
{
bool bStartOfPage = false;
- long nThisX = ColHidden(nX) ? 0 : pColWidth[nX];
+ long nThisX = ColHidden(nX) ? 0 : mpColWidth->GetValue(nX);
bool bManualBreak = HasColManualBreak(nX);
if ( (nSizeX+nThisX > nPageSizeX) || (bManualBreak && !bSkipColBreaks) )
{
@@ -183,7 +183,7 @@ void ScTable::UpdatePageBreaks( const ScRange* pUserArea )
{
// subtract size of repeat columns from page size
for (SCCOL i=nRepeatStartX; i<=nRepeatEndX; i++)
- nPageSizeX -= ColHidden(i) ? 0 : pColWidth[i];
+ nPageSizeX -= ColHidden(i) ? 0 : mpColWidth->GetValue(i);
while (nX<=nRepeatEndX)
RemoveColBreak(++nX, true, false);
bColFound = true;
More information about the Libreoffice-commits
mailing list