[Libreoffice-commits] core.git: 2 commits - sax/source sc/inc sc/qa sc/source
Michael Meeks
michael.meeks at collabora.com
Tue Jan 14 07:52:56 PST 2014
sax/source/fastparser/fastparser.cxx | 10 -
sc/inc/dociter.hxx | 7 -
sc/qa/unit/ucalc.cxx | 111 +++++++++++++++-
sc/source/core/data/dociter.cxx | 235 +++++++++++++++++++++++------------
4 files changed, 273 insertions(+), 90 deletions(-)
New commits:
commit bbdb7b43e639b0dd27377d104c59fea3f8481b2a
Author: Michael Meeks <michael.meeks at collabora.com>
Date: Mon Jan 6 14:03:45 2014 -0800
sc: re-work ScHorizontalCellIterator to try to improve performance.
Add more unit tests, reduce the number of rows that we know are empty
that we iterate over while saving by shrinking the column set that
we scan as we go along.
Change-Id: Iebd817d9a8a01fa6abeaa24c4aace92233313e0f
diff --git a/sc/inc/dociter.hxx b/sc/inc/dociter.hxx
index 846bb11..a777d44 100644
--- a/sc/inc/dociter.hxx
+++ b/sc/inc/dociter.hxx
@@ -413,8 +413,10 @@ class ScHorizontalCellIterator // walk through all non empty cells in an ar
{
sc::CellStoreType::const_iterator maPos;
sc::CellStoreType::const_iterator maEnd;
+ SCCOL mnCol;
};
+ std::vector<ColParam>::iterator maColPos;
std::vector<ColParam> maColPositions;
ScDocument* pDoc;
@@ -428,7 +430,7 @@ class ScHorizontalCellIterator // walk through all non empty cells in an ar
SCCOL mnCol;
SCROW mnRow;
ScRefCellValue maCurCell;
- bool bMore;
+ bool mbMore;
public:
ScHorizontalCellIterator(ScDocument* pDocument, SCTAB nTable,
@@ -442,6 +444,9 @@ public:
private:
void Advance();
+ void SkipInvalid();
+ bool SkipInvalidInRow();
+ SCROW FindNextNonEmptyRow();
};
diff --git a/sc/qa/unit/ucalc.cxx b/sc/qa/unit/ucalc.cxx
index 7c1d72d..5d7a3c4 100644
--- a/sc/qa/unit/ucalc.cxx
+++ b/sc/qa/unit/ucalc.cxx
@@ -942,16 +942,30 @@ bool checkHorizontalIterator(ScDocument* pDoc, const char* pData[][_Size], size_
for (ScRefCellValue* pCell = aIter.GetNext(nCol, nRow); pCell; pCell = aIter.GetNext(nCol, nRow), ++i)
{
if (i >= nCheckCount)
+ {
+ cerr << "hit invalid check " << i << " of " << nCheckCount << endl;
CPPUNIT_FAIL("Iterator claims there is more data than there should be.");
+ return false;
+ }
if (pChecks[i].nCol != nCol)
+ {
+ cerr << "Column mismatch " << pChecks[i].nCol << " vs. " << nCol << endl;
return false;
+ }
if (pChecks[i].nRow != nRow)
+ {
+ cerr << "Row mismatch " << pChecks[i].nRow << " vs. " << nRow << endl;
return false;
+ }
if (OUString::createFromAscii(pChecks[i].pVal) != pCell->getString(pDoc))
+ {
+ cerr << "String mismatch " << pChecks[i].pVal << " vs. " <<
+ OUStringToOString(pCell->getString(pDoc), RTL_TEXTENCODING_UTF8).getStr() << endl;
return false;
+ }
}
return true;
@@ -964,7 +978,7 @@ void Test::testHorizontalIterator()
m_pDoc->InsertTab(0, "test");
{
- // Raw data
+ // Raw data - mixed types
const char* aData[][2] = {
{ "A", "B" },
{ "C", "1" },
@@ -987,11 +1001,11 @@ void Test::testHorizontalIterator()
m_pDoc, aData, SAL_N_ELEMENTS(aData), aChecks, SAL_N_ELEMENTS(aChecks));
if (!bRes)
- CPPUNIT_FAIL("Failed on test 1.");
+ CPPUNIT_FAIL("Failed on test mixed.");
}
{
- // Raw data
+ // Raw data - 'hole' data
const char* aData[][2] = {
{ "A", "B" },
{ "C", 0 },
@@ -1010,7 +1024,96 @@ void Test::testHorizontalIterator()
m_pDoc, aData, SAL_N_ELEMENTS(aData), aChecks, SAL_N_ELEMENTS(aChecks));
if (!bRes)
- CPPUNIT_FAIL("Failed on test 2.");
+ CPPUNIT_FAIL("Failed on test hole.");
+ }
+
+ {
+ // Very holy data
+ const char* aData[][2] = {
+ { 0, "A" },
+ { 0, 0 },
+ { 0, "1" },
+ { "B", 0 },
+ { "C", "2" },
+ { "D", "3" },
+ { "E", 0 },
+ { 0, "G" },
+ { 0, 0 },
+ };
+
+ HoriIterCheck aChecks[] = {
+ { 1, 0, "A" },
+ { 1, 2, "1" },
+ { 0, 3, "B" },
+ { 0, 4, "C" },
+ { 1, 4, "2" },
+ { 0, 5, "D" },
+ { 1, 5, "3" },
+ { 0, 6, "E" },
+ { 1, 7, "G" },
+ };
+
+ bool bRes = checkHorizontalIterator(
+ m_pDoc, aData, SAL_N_ELEMENTS(aData), aChecks, SAL_N_ELEMENTS(aChecks));
+
+ if (!bRes)
+ CPPUNIT_FAIL("Failed on test holy.");
+ }
+
+ {
+ // Degenerate case
+ const char* aData[][2] = {
+ { 0, 0 },
+ { 0, 0 },
+ { 0, 0 },
+ };
+
+ bool bRes = checkHorizontalIterator(
+ m_pDoc, aData, SAL_N_ELEMENTS(aData), NULL, 0);
+
+ if (!bRes)
+ CPPUNIT_FAIL("Failed on test degenerate.");
+ }
+
+ {
+ // Data at end
+ const char* aData[][2] = {
+ { 0, 0 },
+ { 0, 0 },
+ { 0, "A" },
+ };
+
+ HoriIterCheck aChecks[] = {
+ { 1, 2, "A" },
+ };
+
+ bool bRes = checkHorizontalIterator(
+ m_pDoc, aData, SAL_N_ELEMENTS(aData), aChecks, SAL_N_ELEMENTS(aChecks));
+
+ if (!bRes)
+ CPPUNIT_FAIL("Failed on test at end.");
+ }
+
+ {
+ // Data in middle
+ const char* aData[][2] = {
+ { 0, 0 },
+ { 0, 0 },
+ { 0, "A" },
+ { 0, "1" },
+ { 0, 0 },
+ };
+
+ HoriIterCheck aChecks[] = {
+ { 1, 2, "A" },
+ { 1, 3, "1" },
+ };
+
+ bool bRes = checkHorizontalIterator(
+ m_pDoc, aData, SAL_N_ELEMENTS(aData), aChecks, SAL_N_ELEMENTS(aChecks));
+
+ if (!bRes)
+ CPPUNIT_FAIL("Failed on test in middle.");
}
m_pDoc->DeleteTab(0);
diff --git a/sc/source/core/data/dociter.cxx b/sc/source/core/data/dociter.cxx
index 0fd07c7..d06e009 100644
--- a/sc/source/core/data/dociter.cxx
+++ b/sc/source/core/data/dociter.cxx
@@ -49,6 +49,10 @@ using ::rtl::math::approxEqual;
using ::std::vector;
using ::std::set;
+// iterators have very high frequency use -> custom debug.
+// #define debugiter(...) fprintf(stderr, __VA_ARGS__)
+#define debugiter(...)
+
// STATIC DATA -----------------------------------------------------------
namespace {
@@ -1751,7 +1755,6 @@ bool ScQueryCellIterator::BinarySearch()
ScHorizontalCellIterator::ScHorizontalCellIterator(ScDocument* pDocument, SCTAB nTable,
SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2 ) :
- maColPositions(nCol2-nCol1+1),
pDoc( pDocument ),
mnTab( nTable ),
nStartCol( nCol1 ),
@@ -1760,13 +1763,14 @@ ScHorizontalCellIterator::ScHorizontalCellIterator(ScDocument* pDocument, SCTAB
nEndRow( nRow2 ),
mnCol( nCol1 ),
mnRow( nRow1 ),
- bMore(false)
+ mbMore( false )
{
if (mnTab >= pDoc->GetTableCount())
OSL_FAIL("try to access index out of bounds, FIX IT");
pNextRows = new SCROW[ nCol2-nCol1+1 ];
pNextIndices = new SCSIZE[ nCol2-nCol1+1 ];
+ maColPositions.reserve( nCol2-nCol1+1 );
SetTab( mnTab );
}
@@ -1779,44 +1783,60 @@ ScHorizontalCellIterator::~ScHorizontalCellIterator()
void ScHorizontalCellIterator::SetTab( SCTAB nTabP )
{
- bMore = false;
+ mbMore = false;
mnTab = nTabP;
mnRow = nStartRow;
mnCol = nStartCol;
+ maColPositions.resize(0);
// Set the start position in each column.
for (SCCOL i = nStartCol; i <= nEndCol; ++i)
{
ScColumn* pCol = &pDoc->maTabs[mnTab]->aCol[i];
- ColParam& rParam = maColPositions[i-nStartCol];
- rParam.maPos = pCol->maCells.position(nStartRow).first;
- rParam.maEnd = pCol->maCells.end();
- if (rParam.maPos != rParam.maEnd)
- bMore = true;
+ ColParam aParam;
+ aParam.maPos = pCol->maCells.position(nStartRow).first;
+ aParam.maEnd = pCol->maCells.end();
+ aParam.mnCol = i;
+
+ // find first non-empty element.
+ while (aParam.maPos != aParam.maEnd) {
+ if (aParam.maPos->type == sc::element_type_empty)
+ ++aParam.maPos;
+ else
+ {
+ maColPositions.push_back( aParam );
+ break;
+ }
+ }
}
- if (!bMore)
+ if (maColPositions.size() == 0)
return;
- ColParam& rParam = maColPositions[0];
- if (rParam.maPos == rParam.maEnd || rParam.maPos->type == sc::element_type_empty)
- // Skip to the first non-empty cell.
- Advance();
+ maColPos = maColPositions.begin();
+ mbMore = true;
+ SkipInvalid();
}
ScRefCellValue* ScHorizontalCellIterator::GetNext( SCCOL& rCol, SCROW& rRow )
{
- if (!bMore)
+ if (!mbMore)
+ {
+ debugiter("no more !\n");
return NULL;
+ }
// Return the current non-empty cell, and move the cursor to the next one.
- rCol = mnCol;
+ ColParam& r = *maColPos;
+
+ rCol = mnCol = r.mnCol;
rRow = mnRow;
+ debugiter("return col %d row %d\n", (int)rCol, (int)rRow);
- ColParam& r = maColPositions[mnCol-nStartCol];
size_t nOffset = static_cast<size_t>(mnRow) - r.maPos->position;
maCurCell = sc::toRefCell(r.maPos, nOffset);
Advance();
+ debugiter("advance to: col %d row %d\n", (int)maColPos->mnCol, (int)mnRow);
return &maCurCell;
}
@@ -1825,13 +1845,16 @@ bool ScHorizontalCellIterator::GetPos( SCCOL& rCol, SCROW& rRow )
{
rCol = mnCol;
rRow = mnRow;
- return bMore;
+ return mbMore;
}
namespace {
-bool advanceBlock(size_t nRow, sc::CellStoreType::const_iterator& rPos, const sc::CellStoreType::const_iterator& rEnd)
+inline bool advanceNonEmptyBlock(size_t nRow, sc::CellStoreType::const_iterator& rPos,
+ const sc::CellStoreType::const_iterator& rEnd)
{
+ assert (rPos->type != sc::element_type_empty);
+
if (nRow < rPos->position + rPos->size)
// Block already contains the specified row. Nothing to do.
return true;
@@ -1839,8 +1862,9 @@ bool advanceBlock(size_t nRow, sc::CellStoreType::const_iterator& rPos, const sc
// This block is behind the current row position. Advance the block.
for (++rPos; rPos != rEnd; ++rPos)
{
- if (nRow < rPos->position + rPos->size)
- // Found the block that contains the specified row.
+ if (nRow < rPos->position + rPos->size &&
+ rPos->type == sc::element_type_empty)
+ // Found a non-empty block that contains the specified row.
return true;
}
@@ -1850,89 +1874,140 @@ bool advanceBlock(size_t nRow, sc::CellStoreType::const_iterator& rPos, const sc
}
-void ScHorizontalCellIterator::Advance()
+// Skip any invalid / empty cells across the current row,
+// we only advance the cursor if the current entry is invalid.
+// if we return true we have a valid cursor (or hit the end)
+bool ScHorizontalCellIterator::SkipInvalidInRow()
{
+ assert (mbMore);
+ assert (maColPos != maColPositions.end());
+
// Find the next non-empty cell in the current row.
- for (SCCOL i = mnCol+1; i <= nEndCol; ++i)
+ while( maColPos != maColPositions.end() )
{
- ColParam& r = maColPositions[i-nStartCol];
- if (r.maPos == r.maEnd)
- continue;
+ ColParam& r = *maColPos;
+ assert (r.maPos != r.maEnd);
size_t nRow = static_cast<size_t>(mnRow);
- if (nRow < r.maPos->position)
- continue;
-
- if (!advanceBlock(nRow, r.maPos, r.maEnd))
- continue;
-
- if (r.maPos->type == sc::element_type_empty)
- continue;
- // Found in the current row.
- mnCol = i;
- bMore = true;
- return;
- }
-
- // Move to the next row that has at least one non-empty cell.
- ++mnRow;
- while (mnRow <= nEndRow)
- {
- size_t nRow = static_cast<size_t>(mnRow);
- size_t nNextRow = MAXROW+1;
- size_t nNextRowPos = 0;
- for (size_t i = nNextRowPos, n = maColPositions.size(); i < n; ++i)
+ if (nRow >= r.maPos->position)
{
- ColParam& r = maColPositions[i];
- if (r.maPos == r.maEnd)
- // This column has ended.
- continue;
-
- if (nRow < r.maPos->position)
+ if (nRow < r.maPos->position + r.maPos->size)
{
- // This block is ahread of the current row position. Skip it.
- if (r.maPos->position < nNextRow)
- {
- nNextRow = r.maPos->position;
- nNextRowPos = i;
- }
- continue;
+ mnCol = maColPos->mnCol;
+ debugiter("found valid cell at column %d, row %d\n",
+ (int)mnCol, (int)mnRow);
+ assert(r.maPos->type != sc::element_type_empty);
+ return true;
}
-
- if (!advanceBlock(nRow, r.maPos, r.maEnd))
- continue;
-
- if (r.maPos->type == sc::element_type_empty)
+ else
{
- // Empty block. Move to the next block and try next column.
- ++r.maPos;
- if (r.maPos->position < nNextRow)
+ bool bMoreBlocksInColumn = false;
+ // This block is behind the current row position. Advance the block.
+ for (++r.maPos; r.maPos != r.maEnd; ++r.maPos)
{
- nNextRow = r.maPos->position;
- nNextRowPos = i;
+ if (nRow < r.maPos->position + r.maPos->size &&
+ r.maPos->type != sc::element_type_empty)
+ {
+ bMoreBlocksInColumn = true;
+ break;
+ }
+ }
+ if (!bMoreBlocksInColumn)
+ {
+ debugiter("remove column %d at row %d\n",
+ (int)maColPos->mnCol, (int)nRow);
+ maColPos = maColPositions.erase(maColPos);
+ if (maColPositions.size() == 0)
+ {
+ debugiter("no more columns\n");
+ mbMore = false;
+ }
+ }
+ else
+ {
+ debugiter("advanced column %d to block starting row %d, retying\n",
+ (int)maColPos->mnCol, r.maPos->position);
}
- continue;
}
+ }
+ else
+ {
+ debugiter("skip empty cells at column %d, row %d\n",
+ (int)maColPos->mnCol, (int)nRow);
+ maColPos++;
+ }
+ }
+
+ // No more columns with anything interesting in them ?
+ if (maColPositions.size() == 0)
+ {
+ debugiter("no more live columns left - done\n");
+ mbMore = false;
+ return true;
+ }
+
+ return false;
+}
- // Found a non-empty cell block!
- mnCol = i + nStartCol;
- mnRow = nRow;
- bMore = true;
+/// Find the next row that has some real content in one of it's columns.
+SCROW ScHorizontalCellIterator::FindNextNonEmptyRow()
+{
+ size_t nNextRow = MAXROW+1;
+
+ for (std::vector<ColParam>::iterator it = maColPositions.begin();
+ it != maColPositions.end(); ++it)
+ {
+ ColParam& r = *it;
+
+ assert(static_cast<size_t>(mnRow) <= r.maPos->position);
+ nNextRow = std::min (nNextRow, static_cast<size_t>(r.maPos->position));
+ }
+
+ SCROW nRow = std::max(static_cast<SCROW>(nNextRow), mnRow);
+ debugiter("Next non empty row is %d\n", (int) nRow);
+ return nRow;
+}
+
+void ScHorizontalCellIterator::Advance()
+{
+ assert (mbMore);
+ assert (maColPos != maColPositions.end());
+
+ maColPos++;
+
+ SkipInvalid();
+}
+
+void ScHorizontalCellIterator::SkipInvalid()
+{
+ if (maColPos == maColPositions.end() ||
+ !SkipInvalidInRow())
+ {
+ mnRow++;
+
+ if (mnRow > nEndRow)
+ {
+ mbMore = false;
return;
}
- if (nNextRow > static_cast<size_t>(MAXROW))
+ maColPos = maColPositions.begin();
+ debugiter("moving to next row\n");
+ if (SkipInvalidInRow())
{
- // No more blocks to search.
- bMore = false;
+ debugiter("moved to valid cell in next row (or end)\n");
return;
}
- mnRow = nNextRow; // move to the next non-empty row.
+ mnRow = FindNextNonEmptyRow();
+ maColPos = maColPositions.begin();
+ bool bCorrect = SkipInvalidInRow();
+ assert (bCorrect); (void) bCorrect;
}
- bMore = false;
+ if (mnRow > nEndRow)
+ mbMore = false;
}
//------------------------------------------------------------------------
commit 91570fc3f37bedd66eb11b7fb585e207e51abeaa
Author: Michael Meeks <michael.meeks at collabora.com>
Date: Tue Dec 31 12:04:21 2013 +0000
fastparser: avoid boost::optional where it is un-necessary.
boost::optional appears to show up rather heavily on many profiles.
We already use mnElementToken == DONTKNOW to flag / use these guys.
Change-Id: Ibf2b0167f259cc601da2fb9703e880b78e60886e
diff --git a/sax/source/fastparser/fastparser.cxx b/sax/source/fastparser/fastparser.cxx
index 8f02e4f..8c8ab1b 100644
--- a/sax/source/fastparser/fastparser.cxx
+++ b/sax/source/fastparser/fastparser.cxx
@@ -96,10 +96,10 @@ struct NameWithToken
struct SaxContext
{
- ::com::sun::star::uno::Reference< ::com::sun::star::xml::sax::XFastContextHandler > mxContext;
- sal_Int32 mnElementToken;
- boost::optional< OUString > maNamespace;
- boost::optional< OUString > maElementName;
+ Reference< XFastContextHandler > mxContext;
+ sal_Int32 mnElementToken;
+ OUString maNamespace;
+ OUString maElementName;
SaxContext( sal_Int32 nElementToken, const OUString& aNamespace, const OUString& aElementName ):
mnElementToken(nElementToken)
@@ -488,7 +488,7 @@ void Entity::endElement()
if( nElementToken != FastToken::DONTKNOW )
xContext->endFastElement( nElementToken );
else
- xContext->endUnknownElement( aContext.maNamespace.get(), aContext.maElementName.get() );
+ xContext->endUnknownElement( aContext.maNamespace, aContext.maElementName );
}
catch (const Exception& e)
{
More information about the Libreoffice-commits
mailing list