sc/Library_sc.mk | 1
sc/inc/document.hxx | 4
sc/inc/interpretercontext.hxx | 4
sc/inc/lookupcache.hxx | 4
sc/inc/queryiter.hxx | 56 +++++++-
sc/inc/rangecache.hxx | 109 +++++++++++++++
sc/qa/unit/ucalc_sort.cxx | 2
sc/source/core/data/documen2.cxx | 45 ++++++
sc/source/core/data/queryiter.cxx | 202 ++++++++++++++++++++++++++++-
sc/source/core/tool/interpr1.cxx | 15 +-
sc/source/core/tool/interpretercontext.cxx | 19 +-
sc/source/core/tool/lookupcache.cxx | 11 -
sc/source/core/tool/rangecache.cxx | 67 +++++++++
13 files changed, 508 insertions(+), 31 deletions(-)
New commits:
commit 122e676ce35b34c289cc4c91bb72e25398dc9e12
Author: Luboš Luňák <l.lu...@collabora.com>
AuthorDate: Thu May 5 14:56:52 2022 +0200
Commit: Luboš Luňák <l.lu...@collabora.com>
CommitDate: Wed May 11 11:46:30 2022 +0200
introduce Calc cache for sorted handling of unsorted cells
The idea is that there's a cache for a given range, which keeps
a vector of SCROW items, sorted by values of those cells. This
allows some specific cases of e.g. COUNTIF to simply use
BinarySearch() to find the range that matches and work only with
that. This commit implements using this cache for COUNTIF.
Change-Id: I5b36b289b4aecb3b8245bbb447fbb299371262e4
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/134120
Tested-by: Jenkins
Reviewed-by: Luboš Luňák <l.lu...@collabora.com>
diff --git a/sc/Library_sc.mk b/sc/Library_sc.mk
index c6f65d4ec495..f8e097d538a3 100644
--- a/sc/Library_sc.mk
+++ b/sc/Library_sc.mk
@@ -266,6 +266,7 @@ $(eval $(call gb_Library_add_exception_objects,sc,\
sc/source/core/tool/progress \
sc/source/core/tool/queryentry \
sc/source/core/tool/queryparam \
+ sc/source/core/tool/rangecache \
sc/source/core/tool/rangelst \
sc/source/core/tool/rangenam \
sc/source/core/tool/rangeseq \
diff --git a/sc/inc/document.hxx b/sc/inc/document.hxx
index 2242ba2450ac..2f79825979a9 100644
--- a/sc/inc/document.hxx
+++ b/sc/inc/document.hxx
@@ -182,6 +182,8 @@ class ScAutoNameCache;
class ScTemporaryChartLock;
class ScLookupCache;
struct ScLookupCacheMap;
+class ScSortedRangeCache;
+struct ScSortedRangeCacheMap;
class SfxUndoManager;
class ScFormulaParserPool;
struct ScClipParam;
@@ -1397,9 +1399,11 @@ public:
/** Creates a ScLookupCache cache for the range if it
doesn't already exist. */
ScLookupCache & GetLookupCache( const ScRange & rRange,
ScInterpreterContext* pContext );
+ ScSortedRangeCache & GetSortedRangeCache( const ScRange & rRange, bool
bDescending, ScInterpreterContext* pContext );
/** Only ScLookupCache dtor uses RemoveLookupCache(), do
not use elsewhere! */
void RemoveLookupCache( ScLookupCache & rCache );
+ void RemoveSortedRangeCache( ScSortedRangeCache & rCache );
/** Zap all caches. */
void ClearLookupCaches();
diff --git a/sc/inc/interpretercontext.hxx b/sc/inc/interpretercontext.hxx
index 78156b005af1..07e20f3a887e 100644
--- a/sc/inc/interpretercontext.hxx
+++ b/sc/inc/interpretercontext.hxx
@@ -23,6 +23,7 @@ class FormulaToken;
class ScDocument;
class SvNumberFormatter;
struct ScLookupCacheMap;
+struct ScSortedRangeCacheMap;
class ScInterpreter;
enum class SvNumFormatType : sal_Int16;
@@ -57,6 +58,7 @@ struct ScInterpreterContext
std::vector<formula::FormulaToken*> maTokens;
std::vector<DelayedSetNumberFormat> maDelayedSetNumberFormat;
std::unique_ptr<ScLookupCacheMap> mxScLookupCache; // cache for lookups
like VLOOKUP and MATCH
+ std::unique_ptr<ScSortedRangeCacheMap> mxScSortedRangeCache; // cache for
unsorted lookups
// Allocation cache for "aConditions" array in
ScInterpreter::IterateParameterIfs()
// This is populated/used only when formula-group threading is enabled.
std::vector<sal_uInt32> maConditions;
@@ -83,6 +85,7 @@ private:
void SetDocAndFormatter(const ScDocument& rDoc, SvNumberFormatter*
pFormatter);
void Cleanup();
void ClearLookupCache();
+ void ClearSortedRangeCache();
void initFormatTable();
SvNumberFormatter* mpFormatter;
mutable NFIndexAndFmtType maNFTypeCache;
@@ -136,6 +139,7 @@ class ScInterpreterContextPool
public:
// Only to be used to clear lookup cache in all pool elements
static void ClearLookupCaches();
+ static void ClearSortedRangeCaches();
};
class ScThreadedInterpreterContextGetterGuard
diff --git a/sc/inc/lookupcache.hxx b/sc/inc/lookupcache.hxx
index 57ee88a4fa28..ca1d333880fa 100644
--- a/sc/inc/lookupcache.hxx
+++ b/sc/inc/lookupcache.hxx
@@ -110,8 +110,8 @@ public:
};
/// MUST be new'd because Notify() deletes.
- ScLookupCache( ScDocument * pDoc, const ScRange &
rRange, ScLookupCacheMap & cacheMap );
- virtual ~ScLookupCache() override;
+ ScLookupCache( ScDocument * pDoc, const ScRange &
rRange, ScLookupCacheMap & cacheMap )
+ : maRange( rRange), mpDoc( pDoc),
mCacheMap(cacheMap) {}
/// Remove from document structure and delete (!) cache on modify hint.
virtual void Notify( const SfxHint& rHint ) override;
diff --git a/sc/inc/queryiter.hxx b/sc/inc/queryiter.hxx
index 5370dd0fb211..2993ba1c0167 100644
--- a/sc/inc/queryiter.hxx
+++ b/sc/inc/queryiter.hxx
@@ -26,6 +26,8 @@
#include "mtvelements.hxx"
#include "types.hxx"
+class ScSortedRangeCache;
+
/*
Query-related iterators. There is one template class ScQueryCellIteratorBase
that implements most of the shared functionality, specific parts are done
@@ -82,6 +84,39 @@ protected:
SCROW nStartRow, SCROW nEndRow);
};
+// The implementation using ScSortedRangeCache, which allows sorted iteration
+// of unsorted cells.
+template<>
+class ScQueryCellIteratorAccessSpecific<
ScQueryCellIteratorAccess::SortedCache >
+{
+public:
+ void SetSortedRangeCache( const ScSortedRangeCache& cache );
+protected:
+ ScQueryCellIteratorAccessSpecific( ScDocument& rDocument, const
ScQueryParam& rParam );
+ void InitPos();
+ void IncPos();
+ void IncBlock() { IncPos(); } // Cannot skip entire block, not linear.
+
+ // 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;
+
+ const ScSortedRangeCache* sortedCache;
+ size_t sortedCachePos;
+
+ class SortedCacheIndexer;
+ typedef std::pair<ScRefCellValue, SCROW> BinarySearchCellType;
+ SortedCacheIndexer MakeBinarySearchIndexer(const sc::CellStoreType& rCells,
+ SCROW nStartRow, SCROW nEndRow);
+private:
+ void UpdatePos();
+};
+
// Data and functionality for specific types of query.
template< ScQueryCellIteratorType iteratorType >
class ScQueryCellIteratorTypeSpecific
@@ -115,7 +150,7 @@ protected:
nTestEqualConditionFulfilled = nTestEqualConditionEnabled |
nTestEqualConditionMatched
};
- const ScInterpreterContext& mrContext;
+ ScInterpreterContext& mrContext;
sal_uInt8 nStopOnMismatch;
sal_uInt8 nTestEqualCondition;
bool bAdvanceQuery;
@@ -151,7 +186,7 @@ protected:
bool BinarySearch( SCCOL col );
public:
- ScQueryCellIteratorBase(ScDocument& rDocument, const
ScInterpreterContext& rContext, SCTAB nTable,
+ ScQueryCellIteratorBase(ScDocument& rDocument,
ScInterpreterContext& rContext, SCTAB nTable,
const ScQueryParam& aParam, bool
bMod);
// when !bMod, the QueryParam has to
be filled
// (bIsString)
@@ -237,7 +272,7 @@ class ScQueryCellIterator
bool GetThis();
public:
- ScQueryCellIterator(ScDocument& rDocument, const ScInterpreterContext&
rContext, SCTAB nTable,
+ ScQueryCellIterator(ScDocument& rDocument, ScInterpreterContext& rContext,
SCTAB nTable,
const ScQueryParam& aParam, bool bMod)
: Base( rDocument, rContext, nTable, aParam, bMod ) {}
bool GetFirst();
@@ -282,6 +317,7 @@ template< ScQueryCellIteratorAccess accessType >
class ScCountIfCellIterator
: public ScQueryCellIteratorBase< accessType,
ScQueryCellIteratorType::CountIf >
{
+protected:
typedef ScQueryCellIteratorBase< accessType,
ScQueryCellIteratorType::CountIf > Base;
// Make base members directly visible here (templated bases need 'this->').
using Base::maParam;
@@ -295,7 +331,7 @@ class ScCountIfCellIterator
using Base::countIfCount;
public:
- ScCountIfCellIterator(ScDocument& rDocument, const ScInterpreterContext&
rContext, SCTAB nTable,
+ ScCountIfCellIterator(ScDocument& rDocument, ScInterpreterContext&
rContext, SCTAB nTable,
const ScQueryParam& aParam, bool bMod)
: Base( rDocument, rContext, nTable, aParam, bMod ) {}
sal_uInt64 GetCount();
@@ -303,4 +339,16 @@ public:
typedef ScCountIfCellIterator< ScQueryCellIteratorAccess::Direct >
ScCountIfCellIteratorDirect;
+class ScCountIfCellIteratorSortedCache
+ : public ScCountIfCellIterator< ScQueryCellIteratorAccess::SortedCache >
+{
+ typedef ScCountIfCellIterator< ScQueryCellIteratorAccess::SortedCache >
Base;
+public:
+ ScCountIfCellIteratorSortedCache(ScDocument& rDocument,
ScInterpreterContext& rContext,
+ SCTAB nTable, const ScQueryParam& aParam, bool bMod)
+ : Base( rDocument, rContext, nTable, aParam, bMod ) {}
+ // Returns true if this iterator can be used for the given query.
+ static bool CanBeUsed(const ScQueryParam& aParam);
+};
+
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/inc/rangecache.hxx b/sc/inc/rangecache.hxx
new file mode 100644
index 000000000000..92e9ae69a766
--- /dev/null
+++ b/sc/inc/rangecache.hxx
@@ -0,0 +1,109 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ * This file incorporates work covered by the following license notice:
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed
+ * with this work for additional information regarding copyright
+ * ownership. The ASF licenses this file to you under the Apache
+ * License, Version 2.0 (the "License"); you may not use this file
+ * except in compliance with the License. You may obtain a copy of
+ * the License at http://www.apache.org/licenses/LICENSE-2.0 .
+ */
+
+#pragma once
+
+#include "address.hxx"
+#include <svl/listener.hxx>
+
+#include <memory>
+#include <unordered_map>
+
+class ScDocument;
+struct ScSortedRangeCacheMap;
+
+/** Sorted cache for one range used with interpreter functions such as VLOOKUP
+ and MATCH. Caches sorted order for cells in the given range, which must
+ be one column. This allows faster lookups when cells are not sorted.
+
+ The class has a vector of SCROW items, which is sorted according to values
+ of those cells. Therefore e.g. binary search of those cells can be done
+ by doing binary search of the vector while mapping the indexes to rows.
+ */
+
+class ScSortedRangeCache final : public SvtListener
+{
+public:
+ /// MUST be new'd because Notify() deletes.
+ ScSortedRangeCache(ScDocument* pDoc, const ScRange& rRange, bool
bDescending,
+ ScSortedRangeCacheMap& cacheMap);
+
+ /// Remove from document structure and delete (!) cache on modify hint.
+ virtual void Notify(const SfxHint& rHint) override;
+
+ const ScRange& getRange() const { return maRange; }
+ bool isDescending() const { return mDescending; }
+
+ ScSortedRangeCacheMap& getCacheMap() const { return mCacheMap; }
+
+ struct HashKey
+ {
+ ScRange range;
+ bool descending;
+ bool operator==(const HashKey& other) const
+ {
+ return range == other.range && descending == other.descending;
+ }
+ };
+ HashKey getHashKey() const { return { maRange, mDescending }; }
+
+ struct Hash
+ {
+ size_t operator()(const HashKey& key) const
+ {
+ // Range should be just one column.
+ size_t hash = key.range.hashStartColumn();
+ if (key.descending)
+ hash = ~hash;
+ return hash;
+ }
+ };
+
+ const std::vector<SCROW>& sortedRows() const { return mSortedRows; }
+ size_t size() const { return mSortedRows.size(); }
+ size_t indexForRow(SCROW row) const
+ {
+ std::vector<SCROW>::const_iterator pos
+ = std::find(mSortedRows.begin(), mSortedRows.end(), row);
+ assert(pos != mSortedRows.end());
+ return pos - mSortedRows.begin();
+ }
+ SCROW rowForIndex(size_t index) const { return mSortedRows[index]; }
+
+private:
+ // Rows sorted by their value.
+ std::vector<SCROW> mSortedRows;
+ ScRange maRange;
+ ScDocument* mpDoc;
+ ScSortedRangeCacheMap& mCacheMap;
+ bool mDescending;
+
+ ScSortedRangeCache(const ScSortedRangeCache&) = delete;
+ ScSortedRangeCache& operator=(const ScSortedRangeCache&) = delete;
+};
+
+// Struct because including lookupcache.hxx in document.hxx isn't wanted.
+struct ScSortedRangeCacheMap
+{
+ std::unordered_map<ScSortedRangeCache::HashKey,
std::unique_ptr<ScSortedRangeCache>,
+ ScSortedRangeCache::Hash>
+ aCacheMap;
+};
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/qa/unit/ucalc_sort.cxx b/sc/qa/unit/ucalc_sort.cxx
index 23b32e9a5b66..bdf2e82d2932 100644
--- a/sc/qa/unit/ucalc_sort.cxx
+++ b/sc/qa/unit/ucalc_sort.cxx
@@ -2030,7 +2030,7 @@ class TestQueryIterator
{
typedef ScQueryCellIteratorBase< ScQueryCellIteratorAccess::Direct,
ScQueryCellIteratorType::Generic > Base;
public:
- TestQueryIterator( ScDocument& rDocument, const ScInterpreterContext&
rContext, SCTAB nTable,
+ TestQueryIterator( ScDocument& rDocument, ScInterpreterContext& rContext,
SCTAB nTable,
const ScQueryParam& aParam, bool bMod )
: Base( rDocument, rContext, nTable, aParam, bMod )
{
diff --git a/sc/source/core/data/documen2.cxx b/sc/source/core/data/documen2.cxx
index 60dd807cdfd0..a352c3c34704 100644
--- a/sc/source/core/data/documen2.cxx
+++ b/sc/source/core/data/documen2.cxx
@@ -67,6 +67,7 @@
#include <listenercalls.hxx>
#include <recursionhelper.hxx>
#include <lookupcache.hxx>
+#include <rangecache.hxx>
#include <externalrefmgr.hxx>
#include <viewdata.hxx>
#include <viewutil.hxx>
@@ -1193,6 +1194,29 @@ ScLookupCache & ScDocument::GetLookupCache( const
ScRange & rRange, ScInterprete
return *pCache;
}
+ScSortedRangeCache& ScDocument::GetSortedRangeCache( const ScRange & rRange,
bool bDescending, ScInterpreterContext* pContext )
+{
+ ScSortedRangeCache* pCache = nullptr;
+ if (!pContext->mxScSortedRangeCache)
+ pContext->mxScSortedRangeCache.reset(new ScSortedRangeCacheMap);
+ ScSortedRangeCacheMap* pCacheMap = pContext->mxScSortedRangeCache.get();
+ // insert with temporary value to avoid doing two lookups
+ auto [findIt, bInserted] =
pCacheMap->aCacheMap.emplace(ScSortedRangeCache::HashKey{rRange, bDescending},
nullptr);
+ if (bInserted)
+ {
+ findIt->second = std::make_unique<ScSortedRangeCache>(this, rRange,
bDescending, *pCacheMap);
+ pCache = findIt->second.get();
+ // The StartListeningArea() call is not thread-safe, as all threads
+ // would access the same SvtBroadcaster.
+ std::unique_lock guard( mScLookupMutex );
+ StartListeningArea(rRange, false, pCache);
+ }
+ else
+ pCache = (*findIt).second.get();
+
+ return *pCache;
+}
+
void ScDocument::RemoveLookupCache( ScLookupCache & rCache )
{
// Data changes leading to this should never happen during calculation
(they are either
@@ -1212,12 +1236,33 @@ void ScDocument::RemoveLookupCache( ScLookupCache &
rCache )
OSL_FAIL( "ScDocument::RemoveLookupCache: range not found in hash map");
}
+void ScDocument::RemoveSortedRangeCache( ScSortedRangeCache & rCache )
+{
+ // Data changes leading to this should never happen during calculation
(they are either
+ // a result of user input or recalc). If it turns out this can be the
case, locking is needed
+ // here and also in ScSortedRangeCache::Notify().
+ assert(!IsThreadedGroupCalcInProgress());
+ auto & cacheMap = rCache.getCacheMap();
+ auto it(cacheMap.aCacheMap.find(rCache.getHashKey()));
+ if (it != cacheMap.aCacheMap.end())
+ {
+ ScSortedRangeCache* pCache = (*it).second.release();
+ cacheMap.aCacheMap.erase(it);
+ assert(!IsThreadedGroupCalcInProgress()); // EndListeningArea() is not
thread-safe
+ EndListeningArea(pCache->getRange(), false, &rCache);
+ return;
+ }
+ OSL_FAIL( "ScDocument::RemoveSortedRangeCache: range not found in hash
map");
+}
+
void ScDocument::ClearLookupCaches()
{
assert(!IsThreadedGroupCalcInProgress());
GetNonThreadedContext().mxScLookupCache.reset();
+ GetNonThreadedContext().mxScSortedRangeCache.reset();
// Clear lookup cache in all interpreter-contexts in the
(threaded/non-threaded) pools.
ScInterpreterContextPool::ClearLookupCaches();
+ ScInterpreterContextPool::ClearSortedRangeCaches();
}
bool ScDocument::IsCellInChangeTrack(const ScAddress &cell,Color
*pColCellBorder)
diff --git a/sc/source/core/data/queryiter.cxx
b/sc/source/core/data/queryiter.cxx
index deea08fd9b1f..7d2b980004d2 100644
--- a/sc/source/core/data/queryiter.cxx
+++ b/sc/source/core/data/queryiter.cxx
@@ -43,6 +43,7 @@
#include <scmatrix.hxx>
#include <rowheightcontext.hxx>
#include <queryevaluator.hxx>
+#include <rangecache.hxx>
#include <o3tl/safeint.hxx>
#include <tools/fract.hxx>
@@ -58,7 +59,7 @@
template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType
queryType >
ScQueryCellIteratorBase< accessType, queryType
>::ScQueryCellIteratorBase(ScDocument& rDocument,
- const ScInterpreterContext& rContext, SCTAB nTable, const ScQueryParam&
rParam, bool bMod )
+ ScInterpreterContext& rContext, SCTAB nTable, const ScQueryParam& rParam,
bool bMod )
: AccessBase( rDocument, rParam )
, mrContext( rContext )
, nStopOnMismatch( nStopOnMismatchDisabled )
@@ -313,13 +314,12 @@ bool ScQueryCellIteratorBase< accessType, queryType
>::BinarySearch( SCCOL col )
if (maParam.bHasHeader)
++nRow;
- ScRefCellValue aCell;
if (bFirstStringIgnore)
{
sc::CellStoreType::const_position_type aPos =
pCol->maCells.position(nRow);
if (aPos.first->type == sc::element_type_string || aPos.first->type ==
sc::element_type_edittext)
{
- aCell = sc::toRefCell(aPos.first, aPos.second);
+ ScRefCellValue aCell = sc::toRefCell(aPos.first, aPos.second);
sal_uInt32 nFormat = pCol->GetNumberFormat(mrContext, nRow);
OUString aCellStr = ScCellFormat::GetInputString(aCell, nFormat,
rFormatter, rDoc);
sal_Int32 nTmp = rCollator.compareString(aCellStr,
rEntry.GetQueryItem().maString.getString());
@@ -372,7 +372,7 @@ bool ScQueryCellIteratorBase< accessType, queryType
>::BinarySearch( SCCOL col )
aLastInRangeString = OUString(u'\xFFFF');
aCellData = aIndexer.getCell(nLastInRange);
- aCell = aCellData.first;
+ ScRefCellValue aCell = aCellData.first;
if (aCell.hasString())
{
sal_uInt32 nFormat = pCol->GetNumberFormat(mrContext,
aCellData.second);
@@ -1005,6 +1005,112 @@ ScQueryCellIteratorAccessSpecific<
ScQueryCellIteratorAccess::Direct >::MakeBina
return NonEmptyCellIndexer(rCells, nStartRow, nEndRow);
}
+// Sorted access using ScSortedRangeCache.
+
+ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache >
+ ::ScQueryCellIteratorAccessSpecific( ScDocument& rDocument, const
ScQueryParam& rParam )
+ : maParam( rParam )
+ , rDoc( rDocument )
+{
+}
+
+void ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache
>::SetSortedRangeCache(
+ const ScSortedRangeCache& cache)
+{
+ sortedCache = &cache;
+}
+
+void ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache
>::InitPos()
+{
+ assert(sortedCache->getRange().aStart.Row() == maParam.nRow1);
+ assert(!(maParam.bHasHeader && maParam.bByRow));
+ sortedCachePos = 0;
+ UpdatePos();
+}
+
+void ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache
>::IncPos()
+{
+ ++sortedCachePos;
+ UpdatePos();
+}
+
+void ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache
>::UpdatePos()
+{
+ // TODO optimize?
+ const ScColumn& rCol = rDoc.maTabs[nTab]->CreateColumnIfNotExists(nCol);
+ if(sortedCachePos < sortedCache->size())
+ {
+ nRow = sortedCache->rowForIndex(sortedCachePos);
+ maCurPos = rCol.maCells.position(nRow);
+ }
+ else
+ {
+ maCurPos.first = rCol.maCells.end();
+ maCurPos.second = 0;
+ }
+}
+
+// Helper that allows binary search of unsorted cells using ScSortedRangeCache.
+// Rows in the given range are kept in a sorted vector and that vector is
binary-searched.
+class ScQueryCellIteratorAccessSpecific<
ScQueryCellIteratorAccess::SortedCache >::SortedCacheIndexer
+{
+ std::vector<SCROW> mSortedRows;
+ const sc::CellStoreType& mCells;
+ size_t mLowIndex;
+ size_t mHighIndex;
+ bool mValid;
+public:
+ SortedCacheIndexer( const sc::CellStoreType& cells, SCROW startRow, SCROW
endRow,
+ const ScSortedRangeCache* cache )
+ : mCells( cells ), mValid( false )
+ {
+ mSortedRows.reserve( cache->sortedRows().size());
+ for( SCROW row : cache->sortedRows())
+ if( row >= startRow && row <= endRow )
+ mSortedRows.emplace_back( row );
+ if(mSortedRows.empty())
+ return;
+ mLowIndex = 0;
+ mHighIndex = mSortedRows.size() - 1;
+ mValid = true;
+ }
+
+ sc::CellStoreType::const_position_type getPosition( size_t nIndex ) const
+ {
+ // TODO optimize?
+ SCROW row = mSortedRows[ nIndex ];
+ return mCells.position(row);
+ }
+
+ BinarySearchCellType getCell( size_t nIndex ) const
+ {
+ BinarySearchCellType aRet;
+ aRet.second = -1;
+
+ sc::CellStoreType::const_position_type aPos = getPosition(nIndex);
+ if (aPos.first == mCells.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 mLowIndex; }
+
+ size_t getHighIndex() const { return mHighIndex; }
+
+ bool isValid() const { return mValid; }
+};
+
+ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache
>::SortedCacheIndexer
+ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache
>::MakeBinarySearchIndexer(
+ const sc::CellStoreType& rCells, SCROW nStartRow, SCROW nEndRow)
+{
+ return SortedCacheIndexer(rCells, nStartRow, nEndRow, sortedCache);
+}
+
+
// Generic query implementation.
bool ScQueryCellIteratorTypeSpecific< ScQueryCellIteratorType::Generic
>::HandleItemFound()
@@ -1064,11 +1170,99 @@ sal_uInt64 ScCountIfCellIterator< accessType
>::GetCount()
return countIfCount;
}
+
+bool ScCountIfCellIteratorSortedCache::CanBeUsed(const ScQueryParam& rParam)
+{
+ if(!rParam.GetEntry(0).bDoQuery || rParam.GetEntry(1).bDoQuery
+ || rParam.GetEntry(0).GetQueryItems().size() != 1 )
+ return false;
+ if(rParam.eSearchType != utl::SearchParam::SearchType::Normal)
+ return false;
+ if(rParam.GetEntry(0).GetQueryItem().meType != ScQueryEntry::ByValue)
+ return false;
+ if(!rParam.bByRow)
+ return false;
+ if(rParam.bHasHeader)
+ return false;
+ if(rParam.GetEntry(0).eOp != SC_LESS && rParam.GetEntry(0).eOp !=
SC_LESS_EQUAL
+ && rParam.GetEntry(0).eOp != SC_GREATER && rParam.GetEntry(0).eOp !=
SC_GREATER_EQUAL
+ && rParam.GetEntry(0).eOp != SC_EQUAL)
+ return false;
+ return true;
+}
+
+template<>
+sal_uInt64 ScCountIfCellIterator< ScQueryCellIteratorAccess::SortedCache
>::GetCount()
+{
+ // Keep Entry.nField in iterator on column change
+ SetAdvanceQueryParamEntryField( true );
+ assert(nTab < rDoc.GetTableCount() && "try to access index out of bounds,
FIX IT");
+ sal_uInt64 count = 0;
+ // Each column must be sorted separately.
+ for(SCCOL col : rDoc.GetAllocatedColumnsRange(nTab, maParam.nCol1,
maParam.nCol2))
+ {
+ nCol = col;
+ nRow = maParam.nRow1;
+ ScRange aSortedRangeRange( col, maParam.nRow1, nTab, col,
maParam.nRow2, nTab);
+ ScQueryOp& op = maParam.GetEntry(0).eOp;
+ // We want all matching values to start in the sort order.
+ bool descending = op == SC_GREATER || op == SC_GREATER_EQUAL;
+ SetSortedRangeCache( rDoc.GetSortedRangeCache( aSortedRangeRange,
descending, &mrContext ));
+ if( op == SC_EQUAL )
+ {
+ // BinarySearch() searches for the last item that matches.
Therefore first
+ // find the last non-matching position using SC_LESS and then find
the last
+ // matching position using SC_EQUAL.
+ ScQueryOp saveOp = op;
+ op = SC_LESS;
+ if( BinarySearch( nCol ))
+ {
+ op = saveOp; // back to SC_EQUAL
+ size_t lastNonMatching = sortedCache->indexForRow(nRow);
+ if( BinarySearch( nCol ))
+ {
+ size_t lastMatching = sortedCache->indexForRow(nRow);
+ assert(lastMatching >= lastNonMatching);
+ count += lastMatching - lastNonMatching;
+ }
+ else
+ {
+ // BinarySearch() should at least find the same result as
the SC_LESS
+ // call, so this should not happen.
+ assert(false);
+ }
+ }
+ else
+ {
+ // BinarySearch() returning false means that all values are
larger,
+ // so try to find matching ones and count those up to and
including
+ // the found one.
+ op = saveOp; // back to SC_EQUAL
+ if( BinarySearch( nCol ))
+ {
+ size_t lastMatching = sortedCache->indexForRow(nRow) + 1;
+ count += lastMatching;
+ }
+ }
+ }
+ else
+ {
+ // BinarySearch() searches for the last item that matches.
Therefore everything
+ // up to and including the found row matches the condition.
+ if( BinarySearch( nCol ))
+ count += sortedCache->indexForRow(nRow) + 1;
+ }
+ }
+ return count;
+}
+
template class ScQueryCellIterator< ScQueryCellIteratorAccess::Direct >;
template class ScCountIfCellIterator< ScQueryCellIteratorAccess::Direct >;
+template class ScCountIfCellIterator< ScQueryCellIteratorAccess::SortedCache >;
// gcc for some reason needs these too
template class ScQueryCellIteratorBase< ScQueryCellIteratorAccess::Direct,
ScQueryCellIteratorType::Generic >;
template class ScQueryCellIteratorBase< ScQueryCellIteratorAccess::Direct,
ScQueryCellIteratorType::CountIf >;
+template class ScQueryCellIteratorBase<
ScQueryCellIteratorAccess::SortedCache, 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 f71c1941b1a2..ec67766a26d1 100644
--- a/sc/source/core/tool/interpr1.cxx
+++ b/sc/source/core/tool/interpr1.cxx
@@ -5747,6 +5747,7 @@ void ScInterpreter::ScCountIf()
ScQueryParam rParam;
rParam.nRow1 = nRow1;
rParam.nRow2 = nRow2;
+ rParam.nTab = nTab1;
ScQueryEntry& rEntry = rParam.GetEntry(0);
ScQueryEntry::Item& rItem = rEntry.GetQueryItem();
@@ -5787,8 +5788,16 @@ void ScInterpreter::ScCountIf()
}
else
{
- ScCountIfCellIteratorDirect aCellIter(mrDoc, mrContext, nTab1,
rParam, false);
- fCount += aCellIter.GetCount();
+ if(ScCountIfCellIteratorSortedCache::CanBeUsed(rParam))
+ {
+ ScCountIfCellIteratorSortedCache aCellIter(mrDoc,
mrContext, nTab1, rParam, false);
+ fCount += aCellIter.GetCount();
+ }
+ else
+ {
+ ScCountIfCellIteratorDirect aCellIter(mrDoc, mrContext,
nTab1, rParam, false);
+ fCount += aCellIter.GetCount();
+ }
}
}
else
@@ -9939,7 +9948,7 @@ utl::SearchParam::SearchType
ScInterpreter::DetectSearchType( std::u16string_vie
return utl::SearchParam::SearchType::Normal;
}
-static bool lcl_LookupQuery( ScAddress & o_rResultPos, ScDocument& rDoc, const
ScInterpreterContext& rContext,
+static bool lcl_LookupQuery( ScAddress & o_rResultPos, ScDocument& rDoc,
ScInterpreterContext& rContext,
const ScQueryParam & rParam, const ScQueryEntry & rEntry )
{
bool bFound = false;
diff --git a/sc/source/core/tool/interpretercontext.cxx
b/sc/source/core/tool/interpretercontext.cxx
index b3ece9266f0d..c35b6a602fd2 100644
--- a/sc/source/core/tool/interpretercontext.cxx
+++ b/sc/source/core/tool/interpretercontext.cxx
@@ -24,6 +24,7 @@
#include <document.hxx>
#include <formula/token.hxx>
#include <lookupcache.hxx>
+#include <rangecache.hxx>
#include <algorithm>
ScInterpreterContextPool
ScInterpreterContextPool::aThreadedInterpreterPool(true);
@@ -38,11 +39,7 @@ ScInterpreterContext::ScInterpreterContext(const ScDocument&
rDoc, SvNumberForma
{
}
-ScInterpreterContext::~ScInterpreterContext()
-{
- ResetTokens();
- mxScLookupCache.reset();
-}
+ScInterpreterContext::~ScInterpreterContext() { ResetTokens(); }
void ScInterpreterContext::ResetTokens()
{
@@ -67,7 +64,7 @@ void ScInterpreterContext::initFormatTable()
void ScInterpreterContext::Cleanup()
{
- // Do not disturb mScLookupCache
+ // Do not disturb mxScLookupCache/mxScSortedRangeCache
maConditions.clear();
maDelayedSetNumberFormat.clear();
ResetTokens();
@@ -75,6 +72,8 @@ void ScInterpreterContext::Cleanup()
void ScInterpreterContext::ClearLookupCache() { mxScLookupCache.reset(); }
+void ScInterpreterContext::ClearSortedRangeCache() {
mxScSortedRangeCache.reset(); }
+
SvNumFormatType ScInterpreterContext::GetNumberFormatType(sal_uInt32 nFIndex)
const
{
if (!mpDoc->IsThreadedGroupCalcInProgress())
@@ -168,6 +167,14 @@ void ScInterpreterContextPool::ClearLookupCaches()
rPtr->ClearLookupCache();
}
+void ScInterpreterContextPool::ClearSortedRangeCaches()
+{
+ for (auto& rPtr : aThreadedInterpreterPool.maPool)
+ rPtr->ClearSortedRangeCache();
+ for (auto& rPtr : aNonThreadedInterpreterPool.maPool)
+ rPtr->ClearSortedRangeCache();
+}
+
/* ScThreadedInterpreterContextGetterGuard */
ScThreadedInterpreterContextGetterGuard::ScThreadedInterpreterContextGetterGuard(
diff --git a/sc/source/core/tool/lookupcache.cxx
b/sc/source/core/tool/lookupcache.cxx
index 9ce48fef696c..979eca0338ae 100644
--- a/sc/source/core/tool/lookupcache.cxx
+++ b/sc/source/core/tool/lookupcache.cxx
@@ -68,17 +68,6 @@ ScLookupCache::QueryCriteria::~QueryCriteria()
deleteString();
}
-ScLookupCache::ScLookupCache( ScDocument * pDoc, const ScRange & rRange,
ScLookupCacheMap & cacheMap ) :
- maRange( rRange),
- mpDoc( pDoc),
- mCacheMap(cacheMap)
-{
-}
-
-ScLookupCache::~ScLookupCache()
-{
-}
-
ScLookupCache::Result ScLookupCache::lookup( ScAddress & o_rResultAddress,
const QueryCriteria & rCriteria, const ScAddress & rQueryAddress )
const
{
diff --git a/sc/source/core/tool/rangecache.cxx
b/sc/source/core/tool/rangecache.cxx
new file mode 100644
index 000000000000..facd906a2f3e
--- /dev/null
+++ b/sc/source/core/tool/rangecache.cxx
@@ -0,0 +1,67 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ * This file incorporates work covered by the following license notice:
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed
+ * with this work for additional information regarding copyright
+ * ownership. The ASF licenses this file to you under the Apache
+ * License, Version 2.0 (the "License"); you may not use this file
+ * except in compliance with the License. You may obtain a copy of
+ * the License at http://www.apache.org/licenses/LICENSE-2.0 .
+ */
+
+#include <rangecache.hxx>
+#include <cellvalue.hxx>
+#include <document.hxx>
+#include <brdcst.hxx>
+
+#include <sal/log.hxx>
+
+ScSortedRangeCache::ScSortedRangeCache(ScDocument* pDoc, const ScRange&
rRange, bool bDescending,
+ ScSortedRangeCacheMap& cacheMap)
+ : maRange(rRange)
+ , mpDoc(pDoc)
+ , mCacheMap(cacheMap)
+ , mDescending(bDescending)
+{
+ assert(maRange.aStart.Col() == maRange.aEnd.Col());
+ assert(maRange.aStart.Tab() == maRange.aEnd.Tab());
+ SCTAB nTab = maRange.aStart.Tab();
+ SCTAB nCol = maRange.aStart.Col();
+ mSortedRows.reserve(maRange.aEnd.Row() - maRange.aStart.Row() + 1);
+ for (SCROW nRow = maRange.aStart.Row(); nRow <= maRange.aEnd.Row(); ++nRow)
+ {
+ ScRefCellValue cell(pDoc->GetRefCellValue(ScAddress(nCol, nRow,
nTab)));
+ if (!cell.hasError() && cell.hasNumeric())
+ mSortedRows.push_back(nRow);
+ }
+ std::stable_sort(
+ mSortedRows.begin(), mSortedRows.end(), [pDoc, nCol, nTab](SCROW
nRow1, SCROW nRow2) {
+ return pDoc->GetValue(nCol, nRow1, nTab) < pDoc->GetValue(nCol,
nRow2, nTab);
+ });
+ if (mDescending)
+ std::reverse(mSortedRows.begin(), mSortedRows.end());
+}
+
+void ScSortedRangeCache::Notify(const SfxHint& rHint)
+{
+ if (!mpDoc->IsInDtorClear())
+ {
+ const ScHint* p = dynamic_cast<const ScHint*>(&rHint);
+ if ((p && (p->GetId() == SfxHintId::ScDataChanged))
+ || dynamic_cast<const ScAreaChangedHint*>(&rHint))
+ {
+ mpDoc->RemoveSortedRangeCache(*this);
+ delete this;
+ }
+ }
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
