sc/inc/column.hxx | 5
sc/inc/document.hxx | 5
sc/inc/queryiter.hxx | 172 +++++++++---
sc/inc/table.hxx | 5
sc/inc/types.hxx | 8
sc/source/core/data/queryiter.cxx | 530 +++++++++++++++++++-------------------
sc/source/core/tool/interpr1.cxx | 18 -
7 files changed, 432 insertions(+), 311 deletions(-)
New commits:
commit 80606b89bbd38f63423eccfac4d1b8e6732b9560
Author: Luboš Luňák <l.lu...@collabora.com>
AuthorDate: Wed May 4 19:46:57 2022 +0200
Commit: Luboš Luňák <l.lu...@collabora.com>
CommitDate: Tue May 10 16:23:32 2022 +0200
extend ScQueryCellIteratorBase for custom cell access
This moves code related to accessing cells to query to a template
base class. Creating more specialization of that class will allow
queries that use a cache of sort order for the cells.
Change-Id: I47d1bc2d038717ff64f1d11fa6c7dba2359fec11
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/134096
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 3f0785429ca9..feba105169e6 100644
--- a/sc/inc/column.hxx
+++ b/sc/inc/column.hxx
@@ -208,9 +208,10 @@ friend class ScTable;
friend class ScValueIterator;
friend class ScHorizontalValueIterator;
friend class ScDBQueryDataIterator;
-template< ScQueryCellIteratorType >
+template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType
queryType >
friend class ScQueryCellIteratorBase;
-friend class ScQueryCellIterator;
+template< ScQueryCellIteratorAccess accessType >
+friend class ScQueryCellIteratorAccessSpecific;
friend class ScFormulaGroupIterator;
friend class ScCellIterator;
friend class ScHorizontalCellIterator;
diff --git a/sc/inc/document.hxx b/sc/inc/document.hxx
index 2518acd63773..2242ba2450ac 100644
--- a/sc/inc/document.hxx
+++ b/sc/inc/document.hxx
@@ -323,9 +323,10 @@ friend class ScHorizontalValueIterator;
friend class ScDBQueryDataIterator;
friend class ScFormulaGroupIterator;
friend class ScCellIterator;
-template< ScQueryCellIteratorType >
+template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType
queryType >
friend class ScQueryCellIteratorBase;
-friend class ScQueryCellIterator;
+template< ScQueryCellIteratorAccess accessType >
+friend class ScQueryCellIteratorAccessSpecific;
friend class ScHorizontalCellIterator;
friend class ScHorizontalAttrIterator;
friend class ScDocAttrIterator;
diff --git a/sc/inc/queryiter.hxx b/sc/inc/queryiter.hxx
index f5cba350bff2..e247a471db65 100644
--- a/sc/inc/queryiter.hxx
+++ b/sc/inc/queryiter.hxx
@@ -26,21 +26,78 @@
#include "mtvelements.hxx"
#include "types.hxx"
-// 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.
+/*
+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.
+A template is used for maximum performance, as that allows fast code
specializing,
+inlining, etc.
+There are two template arguments:
+* ScQueryCellIteratorAccess specifies how cells are accessed:
+ + Direct - direct access to cells using mdds.
+ + SortedCache - for accessing unsorted cells in a sorted way using
ScSortedRangeCache.
+* ScQueryCellIteratorType specifies the type of the query operation:
+ + Generic - the generic lookup, used e.g. by VLOOKUP.
+ + CountIf - faster implementation for COUNTIF(S).
-// Specific data should be in ScQueryCellIteratorSpecific (otherwise adding
data
-// members here would mean specializing the entire ScQueryCellIteratorBase).
-template< ScQueryCellIteratorType iteratorType >
-class ScQueryCellIteratorSpecific
+Specific data should be in specific templated base classes, otherwise adding
data
+members would mean specializing the entire ScQueryCellIteratorBase. Some
specific
+functionality may also be implemented in the base classes or depending on the
template
+parameter.
+*/
+
+// Data and functionality for accessing cells in a specific way.
+// Needs specialization, see ScQueryCellIteratorAccess::Direct for what is
needed.
+template< ScQueryCellIteratorAccess accessType >
+class ScQueryCellIteratorAccessSpecific
{
};
-// Shared code for query-based iterators.
+// The implementation using linear direct mdds access.
+template<>
+class ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::Direct >
+{
+protected:
+ ScQueryCellIteratorAccessSpecific( ScDocument& rDocument, const
ScQueryParam& rParam );
+ // Initialize position for new column.
+ void InitPos();
+ // Increase position (next row).
+ void IncPos();
+ // Next mdds block. If access is not direct/linear, then
+ // should call IncPos().
+ void IncBlock();
+
+ // These members needs to be available already in the base class.
+ typedef sc::CellStoreType::const_position_type PositionType;
+ PositionType maCurPos;
+ ScQueryParam maParam;
+ ScDocument& rDoc;
+ SCTAB nTab;
+ SCCOL nCol;
+ SCROW nRow;
+
+ class NonEmptyCellIndexer;
+ typedef std::pair<ScRefCellValue, SCROW> BinarySearchCellType;
+ static NonEmptyCellIndexer MakeBinarySearchIndexer(const
sc::CellStoreType& rCells,
+ SCROW nStartRow, SCROW nEndRow);
+};
+
+// Data and functionality for specific types of query.
template< ScQueryCellIteratorType iteratorType >
-class ScQueryCellIteratorBase : public ScQueryCellIteratorSpecific<
iteratorType >
+class ScQueryCellIteratorTypeSpecific
{
+protected:
+ bool HandleItemFound(); // not implemented, needs specialization
+};
+
+// Shared code for query-based iterators. The main class.
+template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType
queryType >
+class ScQueryCellIteratorBase
+ : public ScQueryCellIteratorAccessSpecific< accessType >
+ , public ScQueryCellIteratorTypeSpecific< queryType >
+{
+ typedef ScQueryCellIteratorAccessSpecific< accessType > AccessBase;
+ typedef ScQueryCellIteratorTypeSpecific< queryType > TypeBase;
protected:
enum StopOnMismatchBits
{
@@ -58,32 +115,29 @@ protected:
nTestEqualConditionFulfilled = nTestEqualConditionEnabled |
nTestEqualConditionMatched
};
- typedef sc::CellStoreType::const_position_type PositionType;
- PositionType maCurPos;
-
- ScQueryParam maParam;
- ScDocument& rDoc;
const ScInterpreterContext& mrContext;
- SCTAB nTab;
- SCCOL nCol;
- SCROW nRow;
sal_uInt8 nStopOnMismatch;
sal_uInt8 nTestEqualCondition;
bool bAdvanceQuery;
bool bIgnoreMismatchOnLeadingStrings;
- /** Initialize position for new column. */
- void InitPos();
- void IncPos();
- void IncBlock();
+ // Make base members directly visible here (templated bases need 'this->').
+ using AccessBase::maCurPos;
+ using AccessBase::maParam;
+ using AccessBase::rDoc;
+ using AccessBase::nTab;
+ using AccessBase::nCol;
+ using AccessBase::nRow;
+ using AccessBase::InitPos;
+ using AccessBase::IncPos;
+ using AccessBase::IncBlock;
+ using typename AccessBase::BinarySearchCellType;
+ using AccessBase::MakeBinarySearchIndexer;
+ using TypeBase::HandleItemFound;
// 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; }
/* 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
@@ -137,24 +191,55 @@ public:
{ return nTestEqualCondition ==
nTestEqualConditionFulfilled; }
};
+
template<>
-class ScQueryCellIteratorSpecific< ScQueryCellIteratorType::Generic >
+class ScQueryCellIteratorTypeSpecific< ScQueryCellIteratorType::Generic >
{
protected:
+ bool HandleItemFound();
bool getThisResult;
};
// The generic query iterator, used e.g. by VLOOKUP.
-class ScQueryCellIterator : public ScQueryCellIteratorBase<
ScQueryCellIteratorType::Generic >
+template< ScQueryCellIteratorAccess accessType >
+class ScQueryCellIterator
+ : public ScQueryCellIteratorBase< accessType,
ScQueryCellIteratorType::Generic >
{
+ typedef ScQueryCellIteratorBase< accessType,
ScQueryCellIteratorType::Generic > Base;
+ // Make base members directly visible here (templated bases need 'this->').
+ using Base::maParam;
+ using Base::rDoc;
+ using Base::nTab;
+ using Base::nCol;
+ using Base::nRow;
+ using Base::InitPos;
+ using Base::IncPos;
+ using Base::bIgnoreMismatchOnLeadingStrings;
+ using Base::SetStopOnMismatch;
+ using Base::SetTestEqualCondition;
+ using Base::BinarySearch;
+ using typename Base::PositionType;
+ using Base::maCurPos;
+ using Base::IsEqualConditionFulfilled;
+ using Base::bAdvanceQuery;
+ using Base::StoppedOnMismatch;
+ using Base::nStopOnMismatch;
+ using Base::nStopOnMismatchEnabled;
+ using Base::nTestEqualCondition;
+ using Base::nTestEqualConditionEnabled;
+ using Base::PerformQuery;
+ using Base::getThisResult;
+
bool GetThis();
public:
- using ScQueryCellIteratorBase::ScQueryCellIteratorBase;
+ ScQueryCellIterator(ScDocument& rDocument, const ScInterpreterContext&
rContext, SCTAB nTable,
+ const ScQueryParam& aParam, bool bMod)
+ : Base( rDocument, rContext, nTable, aParam, bMod ) {}
bool GetFirst();
bool GetNext();
- using ScQueryCellIteratorBase::GetCol;
- using ScQueryCellIteratorBase::GetRow;
+ SCCOL GetCol() const { return nCol; }
+ SCROW GetRow() const { return nRow; }
/** In a range assumed to be sorted find either the last of
a sequence of equal entries or the last being less than
@@ -177,20 +262,41 @@ public:
bool FindEqualOrSortedLastInRange( SCCOL& nFoundCol, SCROW&
nFoundRow );
};
+typedef ScQueryCellIterator< ScQueryCellIteratorAccess::Direct >
ScQueryCellIteratorDirect;
+
template<>
-class ScQueryCellIteratorSpecific< ScQueryCellIteratorType::CountIf >
+class ScQueryCellIteratorTypeSpecific< ScQueryCellIteratorType::CountIf >
{
protected:
+ bool HandleItemFound();
sal_uInt64 countIfCount;
};
// Used by ScInterpreter::ScCountIf.
-class ScCountIfCellIterator : public ScQueryCellIteratorBase<
ScQueryCellIteratorType::CountIf >
+template< ScQueryCellIteratorAccess accessType >
+class ScCountIfCellIterator
+ : public ScQueryCellIteratorBase< accessType,
ScQueryCellIteratorType::CountIf >
{
+ typedef ScQueryCellIteratorBase< accessType,
ScQueryCellIteratorType::CountIf > Base;
+ // Make base members directly visible here (templated bases need 'this->').
+ using Base::maParam;
+ using Base::rDoc;
+ using Base::nTab;
+ using Base::nCol;
+ using Base::nRow;
+ using Base::InitPos;
+ using Base::PerformQuery;
+ using Base::SetAdvanceQueryParamEntryField;
+ using Base::countIfCount;
+
public:
- using ScQueryCellIteratorBase::ScQueryCellIteratorBase;
+ ScCountIfCellIterator(ScDocument& rDocument, const ScInterpreterContext&
rContext, SCTAB nTable,
+ const ScQueryParam& aParam, bool bMod)
+ : Base( rDocument, rContext, nTable, aParam, bMod ) {}
sal_uInt64 GetCount();
};
+typedef ScCountIfCellIterator< ScQueryCellIteratorAccess::Direct >
ScCountIfCellIteratorDirect;
+
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/inc/table.hxx b/sc/inc/table.hxx
index 64b94b0995f0..290dfcf74f3d 100644
--- a/sc/inc/table.hxx
+++ b/sc/inc/table.hxx
@@ -260,9 +260,10 @@ friend class ScHorizontalValueIterator;
friend class ScDBQueryDataIterator;
friend class ScFormulaGroupIterator;
friend class ScCellIterator;
-template< ScQueryCellIteratorType >
+template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType
queryType >
friend class ScQueryCellIteratorBase;
-friend class ScQueryCellIterator;
+template< ScQueryCellIteratorAccess accessType >
+friend class ScQueryCellIteratorAccessSpecific;
friend class ScHorizontalCellIterator;
friend class ScColumnTextWidthIterator;
friend class ScDocumentImport;
diff --git a/sc/inc/types.hxx b/sc/inc/types.hxx
index ef027058cec1..e3a019da5008 100644
--- a/sc/inc/types.hxx
+++ b/sc/inc/types.hxx
@@ -133,10 +133,18 @@ namespace o3tl{
template<> struct typed_flags<sc::MatrixEdge> :
o3tl::is_typed_flags<sc::MatrixEdge, 63> {};
}
+// Type of query done by ScQueryCellIteratorBase.
enum class ScQueryCellIteratorType
{
Generic,
CountIf
};
+// Type of cell access done by ScQueryCellIteratorBase.
+enum class ScQueryCellIteratorAccess
+{
+ Direct, // Accessing directly cells.
+ SortedCache // Using ScSortedRangeCache.
+};
+
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/source/core/data/queryiter.cxx
b/sc/source/core/data/queryiter.cxx
index cbdd83668920..ec88e35ff6a5 100644
--- a/sc/source/core/data/queryiter.cxx
+++ b/sc/source/core/data/queryiter.cxx
@@ -19,6 +19,7 @@
#include <queryiter.hxx>
+#include <comphelper/flagguard.hxx>
#include <svl/numformat.hxx>
#include <svl/zforlist.hxx>
@@ -55,18 +56,17 @@
#include <limits>
#include <vector>
-template< ScQueryCellIteratorType iteratorType >
-ScQueryCellIteratorBase< iteratorType >::ScQueryCellIteratorBase(ScDocument&
rDocument,
+template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType
queryType >
+ScQueryCellIteratorBase< accessType, queryType
>::ScQueryCellIteratorBase(ScDocument& rDocument,
const ScInterpreterContext& rContext, SCTAB nTable, const ScQueryParam&
rParam, bool bMod )
- : maParam(rParam)
- , rDoc( rDocument )
+ : AccessBase( rDocument, rParam )
, mrContext( rContext )
- , nTab( nTable)
, nStopOnMismatch( nStopOnMismatchDisabled )
, nTestEqualCondition( nTestEqualConditionDisabled )
, bAdvanceQuery( false )
, bIgnoreMismatchOnLeadingStrings( false )
{
+ nTab = nTable;
nCol = maParam.nCol1;
nRow = maParam.nRow1;
SCSIZE i;
@@ -85,41 +85,8 @@ ScQueryCellIteratorBase< iteratorType
>::ScQueryCellIteratorBase(ScDocument& rDo
}
}
-template< ScQueryCellIteratorType iteratorType >
-void ScQueryCellIteratorBase< iteratorType >::InitPos()
-{
- nRow = maParam.nRow1;
- if (maParam.bHasHeader && maParam.bByRow)
- ++nRow;
- const ScColumn& rCol = rDoc.maTabs[nTab]->CreateColumnIfNotExists(nCol);
- maCurPos = rCol.maCells.position(nRow);
-}
-
-template< ScQueryCellIteratorType iteratorType >
-void ScQueryCellIteratorBase< iteratorType >::IncPos()
-{
- if (maCurPos.second + 1 < maCurPos.first->size)
- {
- // Move within the same block.
- ++maCurPos.second;
- ++nRow;
- }
- else
- // Move to the next block.
- IncBlock();
-}
-
-template< ScQueryCellIteratorType iteratorType >
-void ScQueryCellIteratorBase< iteratorType >::IncBlock()
-{
- ++maCurPos.first;
- maCurPos.second = 0;
-
- nRow = maCurPos.first->position;
-}
-
-template< ScQueryCellIteratorType iteratorType >
-void ScQueryCellIteratorBase< iteratorType >::PerformQuery()
+template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType
queryType >
+void ScQueryCellIteratorBase< accessType, queryType >::PerformQuery()
{
assert(nTab < rDoc.GetTableCount() && "index out of bounds, FIX IT");
const ScQueryEntry& rEntry = maParam.GetEntry(0);
@@ -136,7 +103,7 @@ void ScQueryCellIteratorBase< iteratorType >::PerformQuery()
bool bTestEqualCondition = false;
ScQueryEvaluator queryEvaluator(rDoc, *rDoc.maTabs[nTab], maParam,
&mrContext,
(nTestEqualCondition ? &bTestEqualCondition : nullptr));
- if( iteratorType == ScQueryCellIteratorType::CountIf )
+ if( queryType == 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.
@@ -266,8 +233,8 @@ void ScQueryCellIteratorBase< iteratorType >::PerformQuery()
}
}
-template< ScQueryCellIteratorType iteratorType >
-void ScQueryCellIteratorBase< iteratorType >::AdvanceQueryParamEntryField()
+template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType
queryType >
+void ScQueryCellIteratorBase< accessType, queryType
>::AdvanceQueryParamEntryField()
{
SCSIZE nEntries = maParam.GetEntryCount();
for ( SCSIZE j = 0; j < nEntries; j++ )
@@ -305,205 +272,10 @@ void decBlock(std::pair<Iter, size_t>& rPos)
rPos.second = rPos.first->size - 1;
}
-/**
- * This class sequentially indexes non-empty cells in order, from the top of
- * the block where the start row position is, to the bottom of the block
- * where the end row position is. It skips all empty blocks that may be
- * present in between.
- *
- * The index value is an offset from the first element of the first block
- * disregarding all empty cell blocks.
- */
-class NonEmptyCellIndexer
-{
- typedef std::map<size_t, sc::CellStoreType::const_iterator> BlockMapType;
-
- BlockMapType maBlockMap;
-
- const sc::CellStoreType& mrCells;
-
- size_t mnLowIndex;
- size_t mnHighIndex;
-
- bool mbValid;
-
-public:
-
- typedef std::pair<ScRefCellValue, SCROW> CellType;
-
- /**
- * @param rCells cell storage container
- * @param nStartRow logical start row position
- * @param nEndRow logical end row position, inclusive.
- * @param bSkipTopStrBlock when true, skip all leading string cells.
- */
- NonEmptyCellIndexer(
- const sc::CellStoreType& rCells, SCROW nStartRow, SCROW nEndRow, bool
bSkipTopStrBlock ) :
- mrCells(rCells), mnLowIndex(0), mnHighIndex(0), mbValid(true)
- {
- if (nEndRow < nStartRow)
- {
- mbValid = false;
- return;
- }
-
- // Find the low position.
-
- sc::CellStoreType::const_position_type aLoPos =
mrCells.position(nStartRow);
- if (aLoPos.first->type == sc::element_type_empty)
- incBlock(aLoPos);
-
- if (aLoPos.first == rCells.end())
- {
- mbValid = false;
- return;
- }
-
- if (bSkipTopStrBlock)
- {
- // Skip all leading string or empty blocks.
- while (aLoPos.first->type == sc::element_type_string ||
- aLoPos.first->type == sc::element_type_edittext ||
- aLoPos.first->type == sc::element_type_empty)
- {
- incBlock(aLoPos);
- if (aLoPos.first == rCells.end())
- {
- mbValid = false;
- return;
- }
- }
- }
-
- SCROW nFirstRow = aLoPos.first->position;
- SCROW nLastRow = aLoPos.first->position + aLoPos.first->size - 1;
-
- if (nFirstRow > nEndRow)
- {
- // Both start and end row positions are within the leading skipped
- // blocks.
- mbValid = false;
- return;
- }
-
- // Calculate the index of the low position.
- if (nFirstRow < nStartRow)
- mnLowIndex = nStartRow - nFirstRow;
- else
- {
- // Start row is within the skipped block(s). Set it to the first
- // element of the low block.
- mnLowIndex = 0;
- }
-
- if (nEndRow < nLastRow)
- {
- assert(nEndRow >= nFirstRow);
- mnHighIndex = nEndRow - nFirstRow;
-
- maBlockMap.emplace(aLoPos.first->size, aLoPos.first);
- return;
- }
-
- // Find the high position.
-
- sc::CellStoreType::const_position_type aHiPos =
mrCells.position(aLoPos.first, nEndRow);
- if (aHiPos.first->type == sc::element_type_empty)
- {
- // Move to the last position of the previous block.
- decBlock(aHiPos);
-
- // Check the row position of the end of the previous block, and
make sure it's valid.
- SCROW nBlockEndRow = aHiPos.first->position + aHiPos.first->size -
1;
- if (nBlockEndRow < nStartRow)
- {
- mbValid = false;
- return;
- }
- }
-
- // Tag the start and end blocks, and all blocks in between in order
- // but skip all empty blocks.
-
- size_t nPos = 0;
- sc::CellStoreType::const_iterator itBlk = aLoPos.first;
- while (itBlk != aHiPos.first)
- {
- if (itBlk->type == sc::element_type_empty)
- {
- ++itBlk;
- continue;
- }
-
- nPos += itBlk->size;
- maBlockMap.emplace(nPos, itBlk);
- ++itBlk;
-
- if (itBlk->type == sc::element_type_empty)
- ++itBlk;
-
- assert(itBlk != mrCells.end());
- }
-
- assert(itBlk == aHiPos.first);
- nPos += itBlk->size;
- maBlockMap.emplace(nPos, itBlk);
-
- // Calculate the high index.
- BlockMapType::const_reverse_iterator ri = maBlockMap.rbegin();
- mnHighIndex = ri->first;
- mnHighIndex -= ri->second->size;
- mnHighIndex += aHiPos.second;
- }
-
- sc::CellStoreType::const_position_type getPosition( size_t nIndex ) const
- {
- assert(mbValid);
- assert(mnLowIndex <= nIndex);
- assert(nIndex <= mnHighIndex);
-
- sc::CellStoreType::const_position_type aRet(mrCells.end(), 0);
-
- BlockMapType::const_iterator it = maBlockMap.upper_bound(nIndex);
- if (it == maBlockMap.end())
- return aRet;
-
- sc::CellStoreType::const_iterator itBlk = it->second;
- size_t nBlkIndex = it->first - itBlk->size; // index of the first
element of the block.
- assert(nBlkIndex <= nIndex);
- assert(nIndex < it->first);
-
- size_t nOffset = nIndex - nBlkIndex;
- aRet.first = itBlk;
- aRet.second = nOffset;
- return aRet;
- }
-
- CellType getCell( size_t nIndex ) const
- {
- std::pair<ScRefCellValue, SCROW> aRet;
- aRet.second = -1;
-
- sc::CellStoreType::const_position_type aPos = getPosition(nIndex);
- if (aPos.first == mrCells.end())
- return aRet;
-
- aRet.first = sc::toRefCell(aPos.first, aPos.second);
- aRet.second = aPos.first->position + aPos.second;
- return aRet;
- }
-
- size_t getLowIndex() const { return mnLowIndex; }
-
- size_t getHighIndex() const { return mnHighIndex; }
-
- bool isValid() const { return mbValid; }
-};
-
}
-template< ScQueryCellIteratorType iteratorType >
-bool ScQueryCellIteratorBase< iteratorType >::BinarySearch()
+template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType
queryType >
+bool ScQueryCellIteratorBase< accessType, queryType >::BinarySearch()
{
assert(maParam.GetEntry(0).bDoQuery && !maParam.GetEntry(1).bDoQuery
&& maParam.GetEntry(0).GetQueryItems().size() == 1 );
@@ -556,13 +328,34 @@ bool ScQueryCellIteratorBase< iteratorType
>::BinarySearch()
}
}
- NonEmptyCellIndexer aIndexer(pCol->maCells, nRow, maParam.nRow2,
bAllStringIgnore);
+ // Skip leading empty block, if any.
+ sc::CellStoreType::const_position_type startPos =
pCol->maCells.position(nRow);
+ if (startPos.first->type == sc::element_type_empty)
+ incBlock(startPos);
+ if(bAllStringIgnore)
+ {
+ // Skip all leading string or empty blocks.
+ while (startPos.first != pCol->maCells.end()
+ && (startPos.first->type == sc::element_type_string ||
+ startPos.first->type == sc::element_type_edittext ||
+ startPos.first->type == sc::element_type_empty))
+ {
+ incBlock(startPos);
+ }
+ }
+ if(startPos.first == pCol->maCells.end())
+ return false;
+ nRow = startPos.first->position + startPos.second;
+ if (nRow > maParam.nRow2)
+ return false;
+
+ auto aIndexer = MakeBinarySearchIndexer(pCol->maCells, nRow,
maParam.nRow2);
if (!aIndexer.isValid())
return false;
size_t nLo = aIndexer.getLowIndex();
size_t nHi = aIndexer.getHighIndex();
- NonEmptyCellIndexer::CellType aCellData;
+ BinarySearchCellType aCellData;
// Bookkeeping values for breaking up the binary search in case the data
// range isn't strictly sorted.
@@ -780,19 +573,12 @@ bool ScQueryCellIteratorBase< iteratorType
>::BinarySearch()
}
-bool ScQueryCellIterator::FindEqualOrSortedLastInRange( SCCOL& nFoundCol,
+template< ScQueryCellIteratorAccess accessType >
+bool ScQueryCellIterator< accessType >::FindEqualOrSortedLastInRange( SCCOL&
nFoundCol,
SCROW& nFoundRow )
{
- // Set and automatically reset mpParam->mbRangeLookup when returning. We
- // could use comphelper::FlagRestorationGuard, but really, that one is
- // overengineered for this simple purpose here.
- struct BoolResetter
- {
- bool& mr;
- bool mb;
- BoolResetter( bool& r, bool b ) : mr(r), mb(r) { r = b; }
- ~BoolResetter() { mr = mb; }
- } aRangeLookupResetter( maParam.mbRangeLookup, true);
+ // Set and automatically reset mpParam->mbRangeLookup when returning.
+ comphelper::FlagRestorationGuard aRangeLookupResetter(
maParam.mbRangeLookup, true );
nFoundCol = rDoc.MaxCol()+1;
nFoundRow = rDoc.MaxRow()+1;
@@ -969,21 +755,233 @@ bool ScQueryCellIterator::FindEqualOrSortedLastInRange(
SCCOL& nFoundCol,
return (nFoundCol <= rDoc.MaxCol()) && (nFoundRow <= rDoc.MaxRow());
}
-template<>
-bool ScQueryCellIteratorBase< ScQueryCellIteratorType::Generic
>::HandleItemFound()
+// Direct linear cell access using mdds.
+
+ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::Direct >
+ ::ScQueryCellIteratorAccessSpecific( ScDocument& rDocument, const
ScQueryParam& rParam )
+ : maParam( rParam )
+ , rDoc( rDocument )
+{
+}
+
+void ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::Direct
>::InitPos()
+{
+ nRow = maParam.nRow1;
+ if (maParam.bHasHeader && maParam.bByRow)
+ ++nRow;
+ const ScColumn& rCol = rDoc.maTabs[nTab]->CreateColumnIfNotExists(nCol);
+ maCurPos = rCol.maCells.position(nRow);
+}
+
+void ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::Direct
>::IncPos()
+{
+ if (maCurPos.second + 1 < maCurPos.first->size)
+ {
+ // Move within the same block.
+ ++maCurPos.second;
+ ++nRow;
+ }
+ else
+ // Move to the next block.
+ IncBlock();
+}
+
+void ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::Direct
>::IncBlock()
+{
+ ++maCurPos.first;
+ maCurPos.second = 0;
+
+ nRow = maCurPos.first->position;
+}
+
+/**
+ * This class sequentially indexes non-empty cells in order, from the top of
+ * the block where the start row position is, to the bottom of the block
+ * where the end row position is. It skips all empty blocks that may be
+ * present in between.
+ *
+ * The index value is an offset from the first element of the first block
+ * disregarding all empty cell blocks.
+ */
+class ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::Direct
>::NonEmptyCellIndexer
+{
+ typedef std::map<size_t, sc::CellStoreType::const_iterator> BlockMapType;
+
+ BlockMapType maBlockMap;
+
+ const sc::CellStoreType& mrCells;
+
+ size_t mnLowIndex;
+ size_t mnHighIndex;
+
+ bool mbValid;
+
+public:
+ /**
+ * @param rCells cell storage container
+ * @param nStartRow logical start row position
+ * @param nEndRow logical end row position, inclusive.
+ */
+ NonEmptyCellIndexer(
+ const sc::CellStoreType& rCells, SCROW nStartRow, SCROW nEndRow) :
+ mrCells(rCells), mnLowIndex(0), mnHighIndex(0), mbValid(true)
+ {
+ // Find the low position.
+
+ sc::CellStoreType::const_position_type aLoPos =
mrCells.position(nStartRow);
+ assert(aLoPos.first->type != sc::element_type_empty);
+ assert(aLoPos.first != rCells.end());
+
+ SCROW nFirstRow = aLoPos.first->position;
+ SCROW nLastRow = aLoPos.first->position + aLoPos.first->size - 1;
+
+ if (nFirstRow > nEndRow)
+ {
+ // Both start and end row positions are within the leading skipped
+ // blocks.
+ mbValid = false;
+ return;
+ }
+
+ // Calculate the index of the low position.
+ if (nFirstRow < nStartRow)
+ mnLowIndex = nStartRow - nFirstRow;
+ else
+ {
+ // Start row is within the skipped block(s). Set it to the first
+ // element of the low block.
+ mnLowIndex = 0;
+ }
+
+ if (nEndRow < nLastRow)
+ {
+ assert(nEndRow >= nFirstRow);
+ mnHighIndex = nEndRow - nFirstRow;
+
+ maBlockMap.emplace(aLoPos.first->size, aLoPos.first);
+ return;
+ }
+
+ // Find the high position.
+
+ sc::CellStoreType::const_position_type aHiPos =
mrCells.position(aLoPos.first, nEndRow);
+ if (aHiPos.first->type == sc::element_type_empty)
+ {
+ // Move to the last position of the previous block.
+ decBlock(aHiPos);
+
+ // Check the row position of the end of the previous block, and
make sure it's valid.
+ SCROW nBlockEndRow = aHiPos.first->position + aHiPos.first->size -
1;
+ if (nBlockEndRow < nStartRow)
+ {
+ mbValid = false;
+ return;
+ }
+ }
+
+ // Tag the start and end blocks, and all blocks in between in order
+ // but skip all empty blocks.
+
+ size_t nPos = 0;
+ sc::CellStoreType::const_iterator itBlk = aLoPos.first;
+ while (itBlk != aHiPos.first)
+ {
+ if (itBlk->type == sc::element_type_empty)
+ {
+ ++itBlk;
+ continue;
+ }
+
+ nPos += itBlk->size;
+ maBlockMap.emplace(nPos, itBlk);
+ ++itBlk;
+
+ if (itBlk->type == sc::element_type_empty)
+ ++itBlk;
+
+ assert(itBlk != mrCells.end());
+ }
+
+ assert(itBlk == aHiPos.first);
+ nPos += itBlk->size;
+ maBlockMap.emplace(nPos, itBlk);
+
+ // Calculate the high index.
+ BlockMapType::const_reverse_iterator ri = maBlockMap.rbegin();
+ mnHighIndex = ri->first;
+ mnHighIndex -= ri->second->size;
+ mnHighIndex += aHiPos.second;
+ }
+
+ sc::CellStoreType::const_position_type getPosition( size_t nIndex ) const
+ {
+ assert(mbValid);
+ assert(mnLowIndex <= nIndex);
+ assert(nIndex <= mnHighIndex);
+
+ sc::CellStoreType::const_position_type aRet(mrCells.end(), 0);
+
+ BlockMapType::const_iterator it = maBlockMap.upper_bound(nIndex);
+ if (it == maBlockMap.end())
+ return aRet;
+
+ sc::CellStoreType::const_iterator itBlk = it->second;
+ size_t nBlkIndex = it->first - itBlk->size; // index of the first
element of the block.
+ assert(nBlkIndex <= nIndex);
+ assert(nIndex < it->first);
+
+ size_t nOffset = nIndex - nBlkIndex;
+ aRet.first = itBlk;
+ aRet.second = nOffset;
+ return aRet;
+ }
+
+ BinarySearchCellType getCell( size_t nIndex ) const
+ {
+ BinarySearchCellType aRet;
+ aRet.second = -1;
+
+ sc::CellStoreType::const_position_type aPos = getPosition(nIndex);
+ if (aPos.first == mrCells.end())
+ return aRet;
+
+ aRet.first = sc::toRefCell(aPos.first, aPos.second);
+ aRet.second = aPos.first->position + aPos.second;
+ return aRet;
+ }
+
+ size_t getLowIndex() const { return mnLowIndex; }
+
+ size_t getHighIndex() const { return mnHighIndex; }
+
+ bool isValid() const { return mbValid; }
+};
+
+ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::Direct
>::NonEmptyCellIndexer
+ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::Direct
>::MakeBinarySearchIndexer(
+ const sc::CellStoreType& rCells, SCROW nStartRow, SCROW nEndRow )
+{
+ return NonEmptyCellIndexer(rCells, nStartRow, nEndRow);
+}
+
+// Generic query implementation.
+
+bool ScQueryCellIteratorTypeSpecific< ScQueryCellIteratorType::Generic
>::HandleItemFound()
{
getThisResult = true;
return true; // Return from PerformQuery().
}
-bool ScQueryCellIterator::GetThis()
+template< ScQueryCellIteratorAccess accessType >
+bool ScQueryCellIterator< accessType >::GetThis()
{
getThisResult = false;
PerformQuery();
return getThisResult;
}
-bool ScQueryCellIterator::GetFirst()
+template< ScQueryCellIteratorAccess accessType >
+bool ScQueryCellIterator< accessType >::GetFirst()
{
assert(nTab < rDoc.GetTableCount() && "index out of bounds, FIX IT");
nCol = maParam.nCol1;
@@ -991,7 +989,8 @@ bool ScQueryCellIterator::GetFirst()
return GetThis();
}
-bool ScQueryCellIterator::GetNext()
+template< ScQueryCellIteratorAccess accessType >
+bool ScQueryCellIterator< accessType >::GetNext()
{
IncPos();
if ( nStopOnMismatch )
@@ -1001,15 +1000,16 @@ bool ScQueryCellIterator::GetNext()
return GetThis();
}
+// Countifs implementation.
-template<>
-bool ScQueryCellIteratorBase< ScQueryCellIteratorType::CountIf
>::HandleItemFound()
+bool ScQueryCellIteratorTypeSpecific< ScQueryCellIteratorType::CountIf
>::HandleItemFound()
{
++countIfCount;
return false; // Continue searching.
}
-sal_uInt64 ScCountIfCellIterator::GetCount()
+template< ScQueryCellIteratorAccess accessType >
+sal_uInt64 ScCountIfCellIterator< accessType >::GetCount()
{
// Keep Entry.nField in iterator on column change
SetAdvanceQueryParamEntryField( true );
@@ -1023,7 +1023,11 @@ sal_uInt64 ScCountIfCellIterator::GetCount()
return countIfCount;
}
-template class ScQueryCellIteratorBase< ScQueryCellIteratorType::Generic >;
-template class ScQueryCellIteratorBase< ScQueryCellIteratorType::CountIf >;
+template class ScQueryCellIterator< ScQueryCellIteratorAccess::Direct >;
+template class ScCountIfCellIterator< ScQueryCellIteratorAccess::Direct >;
+
+// gcc for some reason needs these too
+template class ScQueryCellIteratorBase< ScQueryCellIteratorAccess::Direct,
ScQueryCellIteratorType::Generic >;
+template class ScQueryCellIteratorBase< ScQueryCellIteratorAccess::Direct,
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 c3f095cfa526..f6dbbffa2d3f 100644
--- a/sc/source/core/tool/interpr1.cxx
+++ b/sc/source/core/tool/interpr1.cxx
@@ -5049,7 +5049,7 @@ void ScInterpreter::ScMatch()
rParam.bByRow = false;
rParam.nRow2 = nRow1;
rEntry.nField = nCol1;
- ScQueryCellIterator aCellIter(mrDoc, mrContext, nTab1, rParam,
false);
+ ScQueryCellIteratorDirect aCellIter(mrDoc, mrContext, nTab1,
rParam, false);
// Advance Entry.nField in Iterator if column changed
aCellIter.SetAdvanceQueryParamEntryField( true );
if (fTyp == 0.0)
@@ -5533,7 +5533,7 @@ void ScInterpreter::IterateParametersIf( ScIterFuncIf
eFunc )
}
else
{
- ScQueryCellIterator aCellIter(mrDoc, mrContext, nTab1, rParam,
false);
+ ScQueryCellIteratorDirect aCellIter(mrDoc, mrContext, nTab1,
rParam, false);
// Increment Entry.nField in iterator when switching to next
column.
aCellIter.SetAdvanceQueryParamEntryField( true );
if ( aCellIter.GetFirst() )
@@ -5786,7 +5786,7 @@ void ScInterpreter::ScCountIf()
}
else
{
- ScCountIfCellIterator aCellIter(mrDoc, mrContext, nTab1,
rParam, false);
+ ScCountIfCellIteratorDirect aCellIter(mrDoc, mrContext, nTab1,
rParam, false);
fCount += aCellIter.GetCount();
}
}
@@ -6140,7 +6140,7 @@ void ScInterpreter::IterateParametersIfs(
double(*ResultFunc)( const sc::ParamIf
}
else
{
- ScQueryCellIterator aCellIter(mrDoc, mrContext, nTab1, rParam,
false);
+ ScQueryCellIteratorDirect aCellIter(mrDoc, mrContext, nTab1,
rParam, false);
// Increment Entry.nField in iterator when switching to next
column.
aCellIter.SetAdvanceQueryParamEntryField( true );
if ( aCellIter.GetFirst() )
@@ -7074,7 +7074,7 @@ void ScInterpreter::ScLookup()
if (rItem.meType == ScQueryEntry::ByString)
aParam.eSearchType = DetectSearchType(rItem.maString.getString(),
mrDoc);
- ScQueryCellIterator aCellIter(mrDoc, mrContext, nTab1, aParam, false);
+ ScQueryCellIteratorDirect aCellIter(mrDoc, mrContext, nTab1, aParam,
false);
SCCOL nC;
SCROW nR;
// Advance Entry.nField in iterator upon switching columns if
@@ -7421,7 +7421,7 @@ void ScInterpreter::CalculateLookup(bool bHLookup)
rEntry.eOp = SC_LESS_EQUAL;
if ( bHLookup )
{
- ScQueryCellIterator aCellIter(mrDoc, mrContext, nTab1, aParam,
false);
+ ScQueryCellIteratorDirect aCellIter(mrDoc, mrContext, nTab1,
aParam, false);
// advance Entry.nField in Iterator upon switching columns
aCellIter.SetAdvanceQueryParamEntryField( true );
if ( bSorted )
@@ -7891,11 +7891,11 @@ void ScInterpreter::ScDBCount()
ScDBQueryParamInternal* p =
static_cast<ScDBQueryParamInternal*>(pQueryParam.get());
p->nCol2 = p->nCol1; // Don't forget to select only one column.
SCTAB nTab = p->nTab;
- // ScQueryCellIterator doesn't make use of
ScDBQueryParamBase::mnField,
+ // ScQueryCellIteratorDirect doesn't make use of
ScDBQueryParamBase::mnField,
// so the source range has to be restricted, like before the
introduction
// of ScDBQueryParamBase.
p->nCol1 = p->nCol2 = p->mnField;
- ScQueryCellIterator aCellIter(mrDoc, mrContext, nTab, *p, true);
+ ScQueryCellIteratorDirect aCellIter(mrDoc, mrContext, nTab, *p,
true);
if ( aCellIter.GetFirst() )
{
do
@@ -9942,7 +9942,7 @@ static bool lcl_LookupQuery( ScAddress & o_rResultPos,
ScDocument& rDoc, const S
const ScQueryParam & rParam, const ScQueryEntry & rEntry )
{
bool bFound = false;
- ScQueryCellIterator aCellIter( rDoc, rContext, rParam.nTab, rParam, false);
+ ScQueryCellIteratorDirect aCellIter( rDoc, rContext, rParam.nTab, rParam,
false);
if (rEntry.eOp != SC_EQUAL)
{
// range lookup <= or >=
