sc/inc/column.hxx | 3
sc/inc/document.hxx | 3
sc/inc/queryiter.hxx | 105 ++++++++-----
sc/inc/table.hxx | 3
sc/inc/types.hxx | 6
sc/source/core/data/queryiter.cxx | 290 ++++++++++++++------------------------
sc/source/core/tool/interpr1.cxx | 2
7 files changed, 190 insertions(+), 222 deletions(-)
New commits:
commit d5986d1c5f639f21204412ebe4a2a9487088b2f3
Author: Luboš Luňák <l.lu...@collabora.com>
AuthorDate: Fri Apr 22 13:33:05 2022 +0200
Commit: Luboš Luňák <l.lu...@collabora.com>
CommitDate: Fri Apr 22 18:16:48 2022 +0200
do not duplicate code for ScCountIfCellIterator
d468958331f36310d11265ba55d7c27366ab58ab improved COUNTIF performance
by copy&pasting the generic query iterator and then basically removing
what was not necessary. Which is in general a good way to improve
the performance, except for the copy&paste part, as the code has
already started to diverge (e.g. fc3b904b671a71266db2e8b30cbeeef4f79).
So instead make the shared code into a template and reuse that from
specific code. This has exactly the same performance as the copy&paste
way.
Change-Id: I168319a1f4273bafc8c0742a114dafbf433968bb
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/133324
Tested-by: Jenkins
Reviewed-by: Luboš Luňák <l.lu...@collabora.com>
diff --git a/sc/inc/column.hxx b/sc/inc/column.hxx
index 812a2e6b5abc..ed9ce2e0c77c 100644
--- a/sc/inc/column.hxx
+++ b/sc/inc/column.hxx
@@ -208,8 +208,9 @@ friend class ScTable;
friend class ScValueIterator;
friend class ScHorizontalValueIterator;
friend class ScDBQueryDataIterator;
+template< ScQueryCellIteratorType >
+friend class ScQueryCellIteratorBase;
friend class ScQueryCellIterator;
-friend class ScCountIfCellIterator;
friend class ScFormulaGroupIterator;
friend class ScCellIterator;
friend class ScHorizontalCellIterator;
diff --git a/sc/inc/document.hxx b/sc/inc/document.hxx
index 3a19ffa02ffb..5fb616b0076b 100644
--- a/sc/inc/document.hxx
+++ b/sc/inc/document.hxx
@@ -323,8 +323,9 @@ friend class ScHorizontalValueIterator;
friend class ScDBQueryDataIterator;
friend class ScFormulaGroupIterator;
friend class ScCellIterator;
+template< ScQueryCellIteratorType >
+friend class ScQueryCellIteratorBase;
friend class ScQueryCellIterator;
-friend class ScCountIfCellIterator;
friend class ScHorizontalCellIterator;
friend class ScHorizontalAttrIterator;
friend class ScDocAttrIterator;
diff --git a/sc/inc/queryiter.hxx b/sc/inc/queryiter.hxx
index 70b8daaf4153..ae7b8066c57b 100644
--- a/sc/inc/queryiter.hxx
+++ b/sc/inc/queryiter.hxx
@@ -24,9 +24,24 @@
#include "scdllapi.h"
#include "queryparam.hxx"
#include "mtvelements.hxx"
+#include "types.hxx"
-class ScQueryCellIterator // walk through all non-empty cells in an
area
+// Query-related iterators. There is one template class ScQueryCellIteratorBase
+// that implements most of the shared functionality, specific parts are done
+// by specializing the templates and then subclassing as the actual class to
use.
+
+// Specific data should be in ScQueryCellIteratorSpecific (otherwise adding
data
+// members here would mean specializing the entire ScQueryCellIteratorBase).
+template< ScQueryCellIteratorType iteratorType >
+class ScQueryCellIteratorSpecific
+{
+};
+
+// Shared code for query-based iterators.
+template< ScQueryCellIteratorType iteratorType >
+class ScQueryCellIteratorBase : public ScQueryCellIteratorSpecific<
iteratorType >
{
+protected:
enum StopOnMismatchBits
{
nStopOnMismatchDisabled = 0x00,
@@ -61,28 +76,20 @@ class ScQueryCellIterator // walk through all
non-empty cells in an ar
void InitPos();
void IncPos();
void IncBlock();
- bool GetThis();
- /* Only works if no regular expression is involved, only
- searches for rows in one column, and only the first
- query entry is considered with simple conditions
- SC_LESS_EQUAL (sorted ascending) or SC_GREATER_EQUAL
- (sorted descending). Check these things before
- invocation! Delivers a starting point, continue with
- GetThis() and GetNext() afterwards. Introduced for
- FindEqualOrSortedLastInRange()
- */
- bool BinarySearch();
+ // The actual query function. It will call HandleItemFound() for any
matching type
+ // and return if HandleItemFound() returns true.
+ void PerformQuery();
+ bool HandleItemFound(); // not implemented, needs specialization
+
+ SCCOL GetCol() const { return nCol; }
+ SCROW GetRow() const { return nRow; }
public:
- ScQueryCellIterator(ScDocument& rDocument, const
ScInterpreterContext& rContext, SCTAB nTable,
- const ScQueryParam& aParam, bool bMod);
+ ScQueryCellIteratorBase(ScDocument& rDocument, const
ScInterpreterContext& rContext, SCTAB nTable,
+ const ScQueryParam& aParam, bool
bMod);
// when !bMod, the QueryParam has to
be filled
// (bIsString)
- bool GetFirst();
- bool GetNext();
- SCCOL GetCol() const { return nCol; }
- SCROW GetRow() const { return nRow; }
// increments all Entry.nField, if column
// changes, for ScInterpreter ScHLookup()
@@ -121,6 +128,37 @@ public:
}
bool IsEqualConditionFulfilled() const
{ return nTestEqualCondition ==
nTestEqualConditionFulfilled; }
+};
+
+template<>
+class ScQueryCellIteratorSpecific< ScQueryCellIteratorType::Generic >
+{
+protected:
+ bool getThisResult;
+};
+
+// The generic query iterator, used e.g. by VLOOKUP.
+class ScQueryCellIterator : public ScQueryCellIteratorBase<
ScQueryCellIteratorType::Generic >
+{
+ /* Only works if no regular expression is involved, only
+ searches for rows in one column, and only the first
+ query entry is considered with simple conditions
+ SC_LESS_EQUAL (sorted ascending) or SC_GREATER_EQUAL
+ (sorted descending). Check these things before
+ invocation! Delivers a starting point, continue with
+ GetThis() and GetNext() afterwards. Introduced for
+ FindEqualOrSortedLastInRange()
+ */
+ bool BinarySearch();
+
+ bool GetThis();
+
+public:
+ using ScQueryCellIteratorBase::ScQueryCellIteratorBase;
+ bool GetFirst();
+ bool GetNext();
+ using ScQueryCellIteratorBase::GetCol;
+ using ScQueryCellIteratorBase::GetRow;
/** In a range assumed to be sorted find either the last of
a sequence of equal entries or the last being less than
@@ -143,29 +181,20 @@ public:
bool FindEqualOrSortedLastInRange( SCCOL& nFoundCol, SCROW&
nFoundRow );
};
-// Used by ScInterpreter::ScCountIf.
-// Walk through all non-empty cells in an area.
-class ScCountIfCellIterator
-{
- typedef sc::CellStoreType::const_position_type PositionType;
- PositionType maCurPos;
- ScQueryParam maParam;
- ScDocument& rDoc;
- const ScInterpreterContext& mrContext;
- SCTAB nTab;
- SCCOL nCol;
- SCROW nRow;
- /** Initialize position for new column. */
- void InitPos();
- void IncPos();
- void IncBlock();
- void AdvanceQueryParamEntryField();
+template<>
+class ScQueryCellIteratorSpecific< ScQueryCellIteratorType::CountIf >
+{
+protected:
+ sal_uInt64 countIfCount;
+};
+// Used by ScInterpreter::ScCountIf.
+class ScCountIfCellIterator : public ScQueryCellIteratorBase<
ScQueryCellIteratorType::CountIf >
+{
public:
- ScCountIfCellIterator(ScDocument& rDocument, const
ScInterpreterContext& rContext, SCTAB nTable,
- const ScQueryParam& aParam);
- int GetCount();
+ using ScQueryCellIteratorBase::ScQueryCellIteratorBase;
+ sal_uInt64 GetCount();
};
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/inc/table.hxx b/sc/inc/table.hxx
index 2e2d78360e73..7e2d8576a1ee 100644
--- a/sc/inc/table.hxx
+++ b/sc/inc/table.hxx
@@ -260,8 +260,9 @@ friend class ScHorizontalValueIterator;
friend class ScDBQueryDataIterator;
friend class ScFormulaGroupIterator;
friend class ScCellIterator;
+template< ScQueryCellIteratorType >
+friend class ScQueryCellIteratorBase;
friend class ScQueryCellIterator;
-friend class ScCountIfCellIterator;
friend class ScHorizontalCellIterator;
friend class ScColumnTextWidthIterator;
friend class ScDocumentImport;
diff --git a/sc/inc/types.hxx b/sc/inc/types.hxx
index 3bb2db710f79..ef027058cec1 100644
--- a/sc/inc/types.hxx
+++ b/sc/inc/types.hxx
@@ -133,4 +133,10 @@ namespace o3tl{
template<> struct typed_flags<sc::MatrixEdge> :
o3tl::is_typed_flags<sc::MatrixEdge, 63> {};
}
+enum class ScQueryCellIteratorType
+{
+ Generic,
+ CountIf
+};
+
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/source/core/data/queryiter.cxx
b/sc/source/core/data/queryiter.cxx
index 27217b0a1eb2..9f0ada59a521 100644
--- a/sc/source/core/data/queryiter.cxx
+++ b/sc/source/core/data/queryiter.cxx
@@ -55,16 +55,17 @@
#include <limits>
#include <vector>
-ScQueryCellIterator::ScQueryCellIterator(ScDocument& rDocument, const
ScInterpreterContext& rContext, SCTAB nTable,
- const ScQueryParam& rParam, bool bMod ) :
- maParam(rParam),
- rDoc( rDocument ),
- mrContext( rContext ),
- nTab( nTable),
- nStopOnMismatch( nStopOnMismatchDisabled ),
- nTestEqualCondition( nTestEqualConditionDisabled ),
- bAdvanceQuery( false ),
- bIgnoreMismatchOnLeadingStrings( false )
+template< ScQueryCellIteratorType iteratorType >
+ScQueryCellIteratorBase< iteratorType >::ScQueryCellIteratorBase(ScDocument&
rDocument,
+ const ScInterpreterContext& rContext, SCTAB nTable, const ScQueryParam&
rParam, bool bMod )
+ : maParam(rParam)
+ , rDoc( rDocument )
+ , mrContext( rContext )
+ , nTab( nTable)
+ , nStopOnMismatch( nStopOnMismatchDisabled )
+ , nTestEqualCondition( nTestEqualConditionDisabled )
+ , bAdvanceQuery( false )
+ , bIgnoreMismatchOnLeadingStrings( false )
{
nCol = maParam.nCol1;
nRow = maParam.nRow1;
@@ -84,7 +85,8 @@ ScQueryCellIterator::ScQueryCellIterator(ScDocument&
rDocument, const ScInterpre
}
}
-void ScQueryCellIterator::InitPos()
+template< ScQueryCellIteratorType iteratorType >
+void ScQueryCellIteratorBase< iteratorType >::InitPos()
{
nRow = maParam.nRow1;
if (maParam.bHasHeader && maParam.bByRow)
@@ -93,7 +95,8 @@ void ScQueryCellIterator::InitPos()
maCurPos = rCol.maCells.position(nRow);
}
-void ScQueryCellIterator::IncPos()
+template< ScQueryCellIteratorType iteratorType >
+void ScQueryCellIteratorBase< iteratorType >::IncPos()
{
if (maCurPos.second + 1 < maCurPos.first->size)
{
@@ -106,7 +109,8 @@ void ScQueryCellIterator::IncPos()
IncBlock();
}
-void ScQueryCellIterator::IncBlock()
+template< ScQueryCellIteratorType iteratorType >
+void ScQueryCellIteratorBase< iteratorType >::IncBlock()
{
++maCurPos.first;
maCurPos.second = 0;
@@ -114,12 +118,14 @@ void ScQueryCellIterator::IncBlock()
nRow = maCurPos.first->position;
}
-bool ScQueryCellIterator::GetThis()
+template< ScQueryCellIteratorType iteratorType >
+void ScQueryCellIteratorBase< iteratorType >::PerformQuery()
{
assert(nTab < rDoc.GetTableCount() && "index out of bounds, FIX IT");
const ScQueryEntry& rEntry = maParam.GetEntry(0);
const ScQueryEntry::Item& rItem = rEntry.GetQueryItem();
+ const bool bSingleQueryItem = rEntry.GetQueryItems().size() == 1;
SCCOLROW nFirstQueryField = rEntry.nField;
bool bAllStringIgnore = bIgnoreMismatchOnLeadingStrings &&
rItem.meType != ScQueryEntry::ByString;
@@ -130,6 +136,22 @@ bool ScQueryCellIterator::GetThis()
bool bTestEqualCondition = false;
ScQueryEvaluator queryEvaluator(rDoc, *rDoc.maTabs[nTab], maParam,
&mrContext,
(nTestEqualCondition ? &bTestEqualCondition : nullptr));
+ if( iteratorType == ScQueryCellIteratorType::CountIf )
+ {
+ // These are not used for COUNTIF, so should not be set, make the
compiler
+ // explicitly aware of it so that the relevant parts are optimized
away.
+ assert( !bAllStringIgnore );
+ assert( !bIgnoreMismatchOnLeadingStrings );
+ assert( nStopOnMismatch == nStopOnMismatchDisabled );
+ assert( nTestEqualCondition == nTestEqualConditionDisabled );
+ bAllStringIgnore = false;
+ bIgnoreMismatchOnLeadingStrings = false;
+ nStopOnMismatch = nStopOnMismatchDisabled;
+ nTestEqualCondition = nTestEqualConditionDisabled;
+ // This one is always set.
+ assert( bAdvanceQuery );
+ bAdvanceQuery = true;
+ }
ScColumn* pCol = &(rDoc.maTabs[nTab])->aCol[nCol];
while (true)
@@ -147,7 +169,7 @@ bool ScQueryCellIterator::GetThis()
{
++nCol;
if (nCol > maParam.nCol2 || nCol >=
rDoc.maTabs[nTab]->GetAllocatedColumnsCount())
- return false;
+ return;
if ( bAdvanceQuery )
{
AdvanceQueryParamEntryField();
@@ -166,7 +188,7 @@ bool ScQueryCellIterator::GetThis()
if (maCurPos.first->type == sc::element_type_empty)
{
- if (rItem.mbMatchEmpty && rEntry.GetQueryItems().size() == 1)
+ if (rItem.mbMatchEmpty && bSingleQueryItem)
{
// This shortcut, instead of determining if any SC_OR query
// exists or this query is SC_AND'ed (which wouldn't make
@@ -177,7 +199,10 @@ bool ScQueryCellIterator::GetThis()
// XXX this would have to be reworked if other filters used it
// in different manners and evaluation would have to be done in
// ValidQuery().
- return true;
+ if(HandleItemFound())
+ return;
+ IncPos();
+ continue;
}
else
{
@@ -197,7 +222,12 @@ bool ScQueryCellIterator::GetThis()
{
if ( nTestEqualCondition && bTestEqualCondition )
nTestEqualCondition |= nTestEqualConditionMatched;
- return !aCell.isEmpty(); // Found it!
+ if ( aCell.isEmpty())
+ return;
+ if( HandleItemFound())
+ return;
+ IncPos();
+ continue;
}
else if ( nStopOnMismatch )
{
@@ -208,7 +238,7 @@ bool ScQueryCellIterator::GetThis()
{
nTestEqualCondition |= nTestEqualConditionMatched;
nStopOnMismatch |= nStopOnMismatchOccurred;
- return false;
+ return;
}
bool bStop;
if (bFirstStringIgnore)
@@ -226,7 +256,7 @@ bool ScQueryCellIterator::GetThis()
if (bStop)
{
nStopOnMismatch |= nStopOnMismatchOccurred;
- return false;
+ return;
}
}
else
@@ -236,25 +266,8 @@ bool ScQueryCellIterator::GetThis()
}
}
-bool ScQueryCellIterator::GetFirst()
-{
- assert(nTab < rDoc.GetTableCount() && "index out of bounds, FIX IT");
- nCol = maParam.nCol1;
- InitPos();
- return GetThis();
-}
-
-bool ScQueryCellIterator::GetNext()
-{
- IncPos();
- if ( nStopOnMismatch )
- nStopOnMismatch = nStopOnMismatchEnabled;
- if ( nTestEqualCondition )
- nTestEqualCondition = nTestEqualConditionEnabled;
- return GetThis();
-}
-
-void ScQueryCellIterator::AdvanceQueryParamEntryField()
+template< ScQueryCellIteratorType iteratorType >
+void ScQueryCellIteratorBase< iteratorType >::AdvanceQueryParamEntryField()
{
SCSIZE nEntries = maParam.GetEntryCount();
for ( SCSIZE j = 0; j < nEntries; j++ )
@@ -463,147 +476,6 @@ bool ScQueryCellIterator::FindEqualOrSortedLastInRange(
SCCOL& nFoundCol,
return (nFoundCol <= rDoc.MaxCol()) && (nFoundRow <= rDoc.MaxRow());
}
-ScCountIfCellIterator::ScCountIfCellIterator(ScDocument& rDocument, const
ScInterpreterContext& rContext, SCTAB nTable,
- const ScQueryParam& rParam ) :
- maParam(rParam),
- rDoc( rDocument ),
- mrContext( rContext ),
- nTab( nTable)
-{
- maParam.nCol1 =
rDoc.maTabs[nTable]->ClampToAllocatedColumns(maParam.nCol1);
- maParam.nCol2 =
rDoc.maTabs[nTable]->ClampToAllocatedColumns(maParam.nCol2);
- nCol = maParam.nCol1;
- nRow = maParam.nRow1;
-}
-
-void ScCountIfCellIterator::InitPos()
-{
- nRow = maParam.nRow1;
- if (maParam.bHasHeader && maParam.bByRow)
- ++nRow;
- ScColumn* pCol = &(rDoc.maTabs[nTab])->aCol[nCol];
- maCurPos = pCol->maCells.position(nRow);
-}
-
-void ScCountIfCellIterator::IncPos()
-{
- if (maCurPos.second + 1 < maCurPos.first->size)
- {
- // Move within the same block.
- ++maCurPos.second;
- ++nRow;
- }
- else
- // Move to the next block.
- IncBlock();
-}
-
-void ScCountIfCellIterator::IncBlock()
-{
- ++maCurPos.first;
- maCurPos.second = 0;
-
- nRow = maCurPos.first->position;
-}
-
-int ScCountIfCellIterator::GetCount()
-{
- assert(nTab < rDoc.GetTableCount() && "try to access index out of bounds,
FIX IT");
- nCol = maParam.nCol1;
- InitPos();
-
- const ScQueryEntry& rEntry = maParam.GetEntry(0);
- const ScQueryEntry::Item& rItem = rEntry.GetQueryItem();
- const bool bSingleQueryItem = rEntry.GetQueryItems().size() == 1;
- int count = 0;
- ScQueryEvaluator queryEvaluator(rDoc, *rDoc.maTabs[nTab], maParam,
&mrContext);
-
- ScColumn* pCol = &(rDoc.maTabs[nTab])->aCol[nCol];
- while (true)
- {
- bool bNextColumn = maCurPos.first == pCol->maCells.end();
- if (!bNextColumn)
- {
- if (nRow > maParam.nRow2)
- bNextColumn = true;
- }
-
- if (bNextColumn)
- {
- do
- {
- ++nCol;
- if (nCol > maParam.nCol2 || nCol >=
rDoc.maTabs[nTab]->GetAllocatedColumnsCount())
- return count;
- AdvanceQueryParamEntryField();
- pCol = &(rDoc.maTabs[nTab])->aCol[nCol];
- }
- while (!rItem.mbMatchEmpty && pCol->IsEmptyData());
-
- InitPos();
- }
-
- if (maCurPos.first->type == sc::element_type_empty)
- {
- if (rItem.mbMatchEmpty && bSingleQueryItem)
- {
- // This shortcut, instead of determining if any SC_OR query
- // exists or this query is SC_AND'ed (which wouldn't make
- // sense, but..) and evaluating them in ValidQuery(), is
- // possible only because the interpreter is the only caller
- // that sets mbMatchEmpty and there is only one item in those
- // cases.
- // XXX this would have to be reworked if other filters used it
- // in different manners and evaluation would have to be done in
- // ValidQuery().
- count++;
- IncPos();
- continue;
- }
- else
- {
- IncBlock();
- continue;
- }
- }
-
- ScRefCellValue aCell = sc::toRefCell(maCurPos.first, maCurPos.second);
-
- if ( queryEvaluator.ValidQuery( nRow,
- (nCol == static_cast<SCCOL>(rEntry.nField) ? &aCell :
nullptr)))
- {
- if (aCell.isEmpty())
- return count;
- count++;
- IncPos();
- continue;
- }
- else
- IncPos();
- }
- return count;
-}
-
-void ScCountIfCellIterator::AdvanceQueryParamEntryField()
-{
- SCSIZE nEntries = maParam.GetEntryCount();
- for ( SCSIZE j = 0; j < nEntries; j++ )
- {
- ScQueryEntry& rEntry = maParam.GetEntry( j );
- if ( rEntry.bDoQuery )
- {
- if ( rEntry.nField < rDoc.MaxCol() )
- rEntry.nField++;
- else
- {
- OSL_FAIL( "AdvanceQueryParamEntryField: ++rEntry.nField >
MAXCOL" );
- }
- }
- else
- break; // for
- }
-}
-
namespace {
template<typename Iter>
@@ -1087,4 +959,62 @@ bool ScQueryCellIterator::BinarySearch()
}
}
+
+template<>
+bool ScQueryCellIteratorBase< ScQueryCellIteratorType::Generic
>::HandleItemFound()
+{
+ getThisResult = true;
+ return true; // Return from PerformQuery().
+}
+
+bool ScQueryCellIterator::GetThis()
+{
+ getThisResult = false;
+ PerformQuery();
+ return getThisResult;
+}
+
+bool ScQueryCellIterator::GetFirst()
+{
+ assert(nTab < rDoc.GetTableCount() && "index out of bounds, FIX IT");
+ nCol = maParam.nCol1;
+ InitPos();
+ return GetThis();
+}
+
+bool ScQueryCellIterator::GetNext()
+{
+ IncPos();
+ if ( nStopOnMismatch )
+ nStopOnMismatch = nStopOnMismatchEnabled;
+ if ( nTestEqualCondition )
+ nTestEqualCondition = nTestEqualConditionEnabled;
+ return GetThis();
+}
+
+
+template<>
+bool ScQueryCellIteratorBase< ScQueryCellIteratorType::CountIf
>::HandleItemFound()
+{
+ ++countIfCount;
+ return false; // Continue searching.
+}
+
+sal_uInt64 ScCountIfCellIterator::GetCount()
+{
+ // Keep Entry.nField in iterator on column change
+ SetAdvanceQueryParamEntryField( true );
+ assert(nTab < rDoc.GetTableCount() && "try to access index out of bounds,
FIX IT");
+ maParam.nCol1 = rDoc.ClampToAllocatedColumns(nTab, maParam.nCol1);
+ maParam.nCol2 = rDoc.ClampToAllocatedColumns(nTab, maParam.nCol2);
+ nCol = maParam.nCol1;
+ InitPos();
+ countIfCount = 0;
+ PerformQuery();
+ return countIfCount;
+}
+
+template class ScQueryCellIteratorBase< ScQueryCellIteratorType::Generic >;
+template class ScQueryCellIteratorBase< ScQueryCellIteratorType::CountIf >;
+
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/source/core/tool/interpr1.cxx b/sc/source/core/tool/interpr1.cxx
index aacfa42ec8ea..c3f095cfa526 100644
--- a/sc/source/core/tool/interpr1.cxx
+++ b/sc/source/core/tool/interpr1.cxx
@@ -5786,7 +5786,7 @@ void ScInterpreter::ScCountIf()
}
else
{
- ScCountIfCellIterator aCellIter(mrDoc, mrContext, nTab1,
rParam);
+ ScCountIfCellIterator aCellIter(mrDoc, mrContext, nTab1,
rParam, false);
fCount += aCellIter.GetCount();
}
}
