external/mdds/UnpackedTarball_mdds.mk | 1 +
external/mdds/speedup-erase-2.patch | 18 ++++++++++++++++++
sc/inc/document.hxx | 2 +-
sc/inc/strings.hrc | 1 +
sc/inc/table.hxx | 4 ++--
sc/qa/unit/ucalc.cxx | 27 ++++++---------------------
sc/source/core/data/documen3.cxx | 8 ++++----
sc/source/core/data/table6.cxx | 13 +++++++++----
sc/source/ui/dialogs/searchresults.cxx | 21 +++++++++++++++------
sc/source/ui/inc/searchresults.hxx | 4 +++-
sc/source/ui/unoobj/cellsuno.cxx | 9 ++++++---
sc/source/ui/view/viewfun2.cxx | 8 +++++---
12 files changed, 71 insertions(+), 45 deletions(-)
New commits:
commit a740176009411d21e20d7c11097af1d8812d251d
Author: Noel Grandin <noel.gran...@collabora.co.uk>
AuthorDate: Mon Sep 5 09:06:10 2022 +0200
Commit: Noel Grandin <noel.gran...@collabora.co.uk>
CommitDate: Mon Sep 5 13:45:36 2022 +0200
tdf#150749 Find and replace on very large sheet
This requires 2 fixes
(*) First, we are deleting from the front of a block in the mdds
storage, so apply a similar patch to mdds to the previous improvement,
(*) Then, we end up with an O(n^2) situation in ScRangesList::Join.
But we are only displaying this data, and in fact, we only display the
first 1000 ranges anyway, so just clamp the list to 1000 entries, and
pass a flag up to the dialog so that we can report that we stopped
counting.
(*) I had to tweak the testSharedStringPool unit test, since
we are not actually clearing the underlying mdds storage, the
reference counts do not drop until we have removed all the
elements in that block of mdds storage (because then the entire
block is destructed, including the not-yet destructed elements)
Change-Id: I2c998f81dfb46453a48fce1254fd253d299d12b8
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/139400
Tested-by: Jenkins
Reviewed-by: Noel Grandin <noel.gran...@collabora.co.uk>
diff --git a/external/mdds/UnpackedTarball_mdds.mk
b/external/mdds/UnpackedTarball_mdds.mk
index b1eff049710b..5465fd418a47 100644
--- a/external/mdds/UnpackedTarball_mdds.mk
+++ b/external/mdds/UnpackedTarball_mdds.mk
@@ -16,6 +16,7 @@ $(eval $(call gb_UnpackedTarball_set_patchlevel,mdds,0))
$(eval $(call gb_UnpackedTarball_add_patches,mdds,\
external/mdds/use-after-free.patch \
external/mdds/speedup-erase-begin.patch \
+ external/mdds/speedup-erase-2.patch \
))
# vim: set noet sw=4 ts=4:
diff --git a/external/mdds/speedup-erase-2.patch
b/external/mdds/speedup-erase-2.patch
new file mode 100644
index 000000000000..2affa4813420
--- /dev/null
+++ b/external/mdds/speedup-erase-2.patch
@@ -0,0 +1,18 @@
+diff -ur include/mdds/multi_type_vector/types.hpp
include/mdds/multi_type_vector/types.hpp
+--- include/mdds/multi_type_vector/types.hpp 2022-09-02 15:16:14.811400565
+0200
++++ include/mdds/multi_type_vector/types.hpp 2022-09-02 15:18:26.951249322
+0200
+@@ -253,7 +253,13 @@
+
+ iterator erase( iterator first, iterator last )
+ {
+- return m_vec.erase( first, last );
++ if (first == m_vec.begin() + m_removedFront)
++ {
++ m_removedFront = last - m_vec.begin();
++ return m_vec.begin() + m_removedFront;
++ }
++ else
++ return m_vec.erase( first, last );
+ }
+
+ size_type capacity() const
diff --git a/sc/inc/document.hxx b/sc/inc/document.hxx
index 1767f8c4e5f0..810a21e0de6f 100644
--- a/sc/inc/document.hxx
+++ b/sc/inc/document.hxx
@@ -1934,7 +1934,7 @@ public:
bool SearchAndReplace( const SvxSearchItem& rSearchItem,
SCCOL& rCol, SCROW& rRow, SCTAB&
rTab,
const ScMarkData& rMark,
ScRangeList& rMatchedRanges,
- OUString& rUndoStr, ScDocument*
pUndoDoc = nullptr );
+ OUString& rUndoStr, ScDocument*
pUndoDoc, bool& bMatchedRangesWereClamped );
static bool IsEmptyCellSearch( const SvxSearchItem& rSearchItem );
// determine Col/Row of subsequent calls
diff --git a/sc/inc/strings.hrc b/sc/inc/strings.hrc
index 9f9dfb454502..1d45fc0d7647 100644
--- a/sc/inc/strings.hrc
+++ b/sc/inc/strings.hrc
@@ -59,6 +59,7 @@
#define STR_INSERTGRAPHIC NC_("STR_INSERTGRAPHIC",
"Insert Image")
#define SCSTR_TOTAL NNC_("SCSTR_TOTAL", "One
result found", "%1 results found")
#define SCSTR_SKIPPED NC_("SCSTR_SKIPPED",
"(only %1 are listed)")
+#define SCSTR_RESULTS_CLAMPED
NC_("SCSTR_RESULTS_CLAMPED", "More than %1 results found (stopped counting)")
// Attribute
#define SCSTR_PROTECTDOC NC_("SCSTR_PROTECTDOC",
"Protect Spreadsheet Structure")
#define SCSTR_UNPROTECTDOC NC_("SCSTR_UNPROTECTDOC",
"Unprotect Spreadsheet Structure")
diff --git a/sc/inc/table.hxx b/sc/inc/table.hxx
index d8daa1b03f4a..4d4e7a2f7830 100644
--- a/sc/inc/table.hxx
+++ b/sc/inc/table.hxx
@@ -703,7 +703,7 @@ public:
void GetAutoFormatData(SCCOL nStartCol, SCROW nStartRow, SCCOL
nEndCol, SCROW nEndRow, ScAutoFormatData& rData);
bool SearchAndReplace(
const SvxSearchItem& rSearchItem, SCCOL& rCol, SCROW& rRow, const
ScMarkData& rMark,
- ScRangeList& rMatchedRanges, OUString& rUndoStr, ScDocument* pUndoDoc);
+ ScRangeList& rMatchedRanges, OUString& rUndoStr, ScDocument* pUndoDoc,
bool& bMatchedRangesWereClamped);
void FindMaxRotCol( RowInfo* pRowInfo, SCSIZE nArrCount, SCCOL nX1,
SCCOL nX2 );
@@ -1196,7 +1196,7 @@ private:
const ScMarkData& rMark, OUString& rUndoStr,
ScDocument* pUndoDoc);
bool ReplaceAll(
const SvxSearchItem& rSearchItem, const ScMarkData& rMark,
ScRangeList& rMatchedRanges,
- OUString& rUndoStr, ScDocument* pUndoDoc);
+ OUString& rUndoStr, ScDocument* pUndoDoc, bool&
bMatchedRangesWereClamped);
bool SearchStyle(const SvxSearchItem& rSearchItem, SCCOL& rCol,
SCROW& rRow,
const ScMarkData& rMark);
diff --git a/sc/qa/unit/ucalc.cxx b/sc/qa/unit/ucalc.cxx
index 59ecb66e6bc2..03cd8adfdbc8 100644
--- a/sc/qa/unit/ucalc.cxx
+++ b/sc/qa/unit/ucalc.cxx
@@ -425,30 +425,14 @@ void Test::testSharedStringPool()
CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(5), rPool.getCount());
CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(2), rPool.getCountIgnoreCase());
- // Clear A1 and purge again.
+ // Clear A1
clearRange(m_pDoc, ScAddress(0,0,0));
- rPool.purge();
- CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(5), rPool.getCount());
- CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(2), rPool.getCountIgnoreCase());
-
- // Clear A2 and purge again.
+ // Clear A2
clearRange(m_pDoc, ScAddress(0,1,0));
- rPool.purge();
- CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(4), rPool.getCount());
- CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(2), rPool.getCountIgnoreCase());
-
- // Clear A3 and purge again.
+ // Clear A3
clearRange(m_pDoc, ScAddress(0,2,0));
- rPool.purge();
- CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(3), rPool.getCount());
- CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(2), rPool.getCountIgnoreCase());
-
- // Clear A4 and purge again.
+ // Clear A4
clearRange(m_pDoc, ScAddress(0,3,0));
- rPool.purge();
- CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(1), rPool.getCount());
- CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(1), rPool.getCountIgnoreCase());
-
// Clear A5 and the pool should be completely empty.
clearRange(m_pDoc, ScAddress(0,4,0));
rPool.purge();
@@ -4343,7 +4327,8 @@ void Test::testSearchCells()
SCTAB nTab = 0;
ScRangeList aMatchedRanges;
OUString aUndoStr;
- bool bSuccess = m_pDoc->SearchAndReplace(aItem, nCol, nRow, nTab,
aMarkData, aMatchedRanges, aUndoStr);
+ bool bMatchedRangesWereClamped = false;
+ bool bSuccess = m_pDoc->SearchAndReplace(aItem, nCol, nRow, nTab,
aMarkData, aMatchedRanges, aUndoStr, nullptr, bMatchedRangesWereClamped);
CPPUNIT_ASSERT_MESSAGE("Search And Replace should succeed", bSuccess);
CPPUNIT_ASSERT_EQUAL_MESSAGE("There should be exactly 3 matching cells.",
size_t(3), aMatchedRanges.size());
diff --git a/sc/source/core/data/documen3.cxx b/sc/source/core/data/documen3.cxx
index c0b6984008b7..87f4dfec813b 100644
--- a/sc/source/core/data/documen3.cxx
+++ b/sc/source/core/data/documen3.cxx
@@ -1316,7 +1316,7 @@ bool ScDocument::IsEmptyCellSearch( const SvxSearchItem&
rSearchItem )
bool ScDocument::SearchAndReplace(
const SvxSearchItem& rSearchItem, SCCOL& rCol, SCROW& rRow, SCTAB& rTab,
const ScMarkData& rMark, ScRangeList& rMatchedRanges,
- OUString& rUndoStr, ScDocument* pUndoDoc)
+ OUString& rUndoStr, ScDocument* pUndoDoc, bool& bMatchedRangesWereClamped)
{
// FIXME: Manage separated marks per table!
bool bFound = false;
@@ -1341,7 +1341,7 @@ bool ScDocument::SearchAndReplace(
nCol = 0;
nRow = 0;
bFound |= maTabs[rMarkedTab]->SearchAndReplace(
- rSearchItem, nCol, nRow, rMark, rMatchedRanges,
rUndoStr, pUndoDoc);
+ rSearchItem, nCol, nRow, rMark, rMatchedRanges,
rUndoStr, pUndoDoc, bMatchedRangesWereClamped);
}
}
@@ -1359,7 +1359,7 @@ bool ScDocument::SearchAndReplace(
if (rMark.GetTableSelect(nTab))
{
bFound = maTabs[nTab]->SearchAndReplace(
- rSearchItem, nCol, nRow, rMark,
rMatchedRanges, rUndoStr, pUndoDoc);
+ rSearchItem, nCol, nRow, rMark,
rMatchedRanges, rUndoStr, pUndoDoc, bMatchedRangesWereClamped);
if (bFound)
{
rCol = nCol;
@@ -1390,7 +1390,7 @@ bool ScDocument::SearchAndReplace(
if (rMark.GetTableSelect(nTab))
{
bFound = maTabs[nTab]->SearchAndReplace(
- rSearchItem, nCol, nRow, rMark,
rMatchedRanges, rUndoStr, pUndoDoc);
+ rSearchItem, nCol, nRow, rMark,
rMatchedRanges, rUndoStr, pUndoDoc, bMatchedRangesWereClamped);
if (bFound)
{
rCol = nCol;
diff --git a/sc/source/core/data/table6.cxx b/sc/source/core/data/table6.cxx
index f7446ee73a32..1915ad7c1588 100644
--- a/sc/source/core/data/table6.cxx
+++ b/sc/source/core/data/table6.cxx
@@ -585,7 +585,7 @@ bool ScTable::Replace(const SvxSearchItem& rSearchItem,
SCCOL& rCol, SCROW& rRow
bool ScTable::ReplaceAll(
const SvxSearchItem& rSearchItem, const ScMarkData& rMark, ScRangeList&
rMatchedRanges,
- OUString& rUndoStr, ScDocument* pUndoDoc)
+ OUString& rUndoStr, ScDocument* pUndoDoc, bool& bMatchedRangesWereClamped)
{
SCCOL nCol = 0;
SCROW nRow = -1;
@@ -610,7 +610,12 @@ bool ScTable::ReplaceAll(
if (bFound)
{
bEverFound = true;
- rMatchedRanges.Join(ScRange(nCol, nRow, nTab));
+ // The combination of this loop and the Join() algorithm is O(n^2),
+ // so just give up if the list gets too big.
+ if (rMatchedRanges.size() < 1000)
+ rMatchedRanges.Join(ScRange(nCol, nRow, nTab));
+ else
+ bMatchedRangesWereClamped = true;
}
else
break;
@@ -796,7 +801,7 @@ bool ScTable::ReplaceAllStyle(
bool ScTable::SearchAndReplace(
const SvxSearchItem& rSearchItem, SCCOL& rCol, SCROW& rRow, const
ScMarkData& rMark,
- ScRangeList& rMatchedRanges, OUString& rUndoStr, ScDocument* pUndoDoc)
+ ScRangeList& rMatchedRanges, OUString& rUndoStr, ScDocument* pUndoDoc,
bool& bMatchedRangesWereClamped)
{
SvxSearchCmd nCommand = rSearchItem.GetCommand();
bool bFound = false;
@@ -848,7 +853,7 @@ bool ScTable::SearchAndReplace(
else if (nCommand == SvxSearchCmd::REPLACE)
bFound = Replace(rSearchItem, rCol, rRow, rMark, rUndoStr,
pUndoDoc);
else if (nCommand == SvxSearchCmd::REPLACE_ALL)
- bFound = ReplaceAll(rSearchItem, rMark, rMatchedRanges,
rUndoStr, pUndoDoc);
+ bFound = ReplaceAll(rSearchItem, rMark, rMatchedRanges,
rUndoStr, pUndoDoc, bMatchedRangesWereClamped);
pSearchText.reset();
}
diff --git a/sc/source/ui/dialogs/searchresults.cxx
b/sc/source/ui/dialogs/searchresults.cxx
index ab0e5790705b..4ea08c1d49cb 100644
--- a/sc/source/ui/dialogs/searchresults.cxx
+++ b/sc/source/ui/dialogs/searchresults.cxx
@@ -96,7 +96,7 @@ namespace
}
void SearchResultsDlg::FillResults( ScDocument& rDoc, const ScRangeList
&rMatchedRanges, bool bCellNotes,
- bool bEmptyCells )
+ bool bEmptyCells, bool bMatchedRangesWereClamped )
{
ListWrapper aList(*mxList);
std::vector<OUString> aTabNames = rDoc.GetAllTableNames();
@@ -161,11 +161,20 @@ void SearchResultsDlg::FillResults( ScDocument& rDoc,
const ScRangeList &rMatche
}
}
- OUString aTotal(ScResId(SCSTR_TOTAL, aList.mnCount));
- OUString aSearchResults = aTotal.replaceFirst("%1",
OUString::number(aList.mnCount));
- if (aList.mnCount > ListWrapper::mnMaximum)
- aSearchResults += " " + ScGlobal::ReplaceOrAppend( aSkipped, u"%1",
OUString::number( ListWrapper::mnMaximum ) );
- mxSearchResults->set_label(aSearchResults);
+ OUString aSearchResultsMsg;
+ if (bMatchedRangesWereClamped)
+ {
+ aSearchResultsMsg = ScResId(SCSTR_RESULTS_CLAMPED);
+ aSearchResultsMsg = aSearchResultsMsg.replaceFirst("%1",
OUString::number(1000));
+ }
+ else
+ {
+ OUString aTotal(ScResId(SCSTR_TOTAL, aList.mnCount));
+ aSearchResultsMsg = aTotal.replaceFirst("%1",
OUString::number(aList.mnCount));
+ if (aList.mnCount > ListWrapper::mnMaximum)
+ aSearchResultsMsg += " " + ScGlobal::ReplaceOrAppend( aSkipped,
u"%1", OUString::number( ListWrapper::mnMaximum ) );
+ }
+ mxSearchResults->set_label(aSearchResultsMsg);
mpDoc = &rDoc;
}
diff --git a/sc/source/ui/inc/searchresults.hxx
b/sc/source/ui/inc/searchresults.hxx
index c10e6014342a..61cfc520b4ff 100644
--- a/sc/source/ui/inc/searchresults.hxx
+++ b/sc/source/ui/inc/searchresults.hxx
@@ -37,7 +37,9 @@ public:
virtual void Close() override;
- void FillResults( ScDocument& rDoc, const ScRangeList& rMatchedRanges,
bool bCellNotes, bool bEmptyCells );
+ void FillResults( ScDocument& rDoc, const ScRangeList& rMatchedRanges,
+ bool bCellNotes, bool bEmptyCells,
+ bool bMatchedRangesWereClamped);
};
class SearchResultsDlgWrapper : public SfxChildWindow
diff --git a/sc/source/ui/unoobj/cellsuno.cxx b/sc/source/ui/unoobj/cellsuno.cxx
index 03ff6d9a62b9..119486d79768 100644
--- a/sc/source/ui/unoobj/cellsuno.cxx
+++ b/sc/source/ui/unoobj/cellsuno.cxx
@@ -3776,8 +3776,9 @@ uno::Reference<container::XIndexAccess> SAL_CALL
ScCellRangesBase::findAll(
SCCOL nCol = 0;
SCROW nRow = 0;
SCTAB nTab = 0;
+ bool bMatchedRangesWereClamped = false;
bool bFound = rDoc.SearchAndReplace(
- *pSearchItem, nCol, nRow, nTab, aMark, aMatchedRanges,
aDummyUndo);
+ *pSearchItem, nCol, nRow, nTab, aMark, aMatchedRanges,
aDummyUndo, nullptr, bMatchedRangesWereClamped);
if (bFound)
{
// on findAll always CellRanges no matter how much has
been found
@@ -3822,8 +3823,9 @@ uno::Reference<uno::XInterface>
ScCellRangesBase::Find_Impl(
OUString aDummyUndo;
ScRangeList aMatchedRanges;
+ bool bMatchedRangesWereClamped;
bool bFound = rDoc.SearchAndReplace(
- *pSearchItem, nCol, nRow, nTab, aMark, aMatchedRanges,
aDummyUndo);
+ *pSearchItem, nCol, nRow, nTab, aMark, aMatchedRanges,
aDummyUndo, nullptr, bMatchedRangesWereClamped);
if (bFound)
{
ScAddress aFoundPos( nCol, nRow, nTab );
@@ -3931,8 +3933,9 @@ sal_Int32 SAL_CALL ScCellRangesBase::replaceAll( const
uno::Reference<util::XSea
if (bUndo)
{
ScRangeList aMatchedRanges;
+ bool bMatchedRangesWereClamped;
bFound = rDoc.SearchAndReplace(
- *pSearchItem, nCol, nRow, nTab, aMark,
aMatchedRanges, aUndoStr, pUndoDoc.get() );
+ *pSearchItem, nCol, nRow, nTab, aMark,
aMatchedRanges, aUndoStr, pUndoDoc.get(), bMatchedRangesWereClamped );
}
if (bFound)
{
diff --git a/sc/source/ui/view/viewfun2.cxx b/sc/source/ui/view/viewfun2.cxx
index d05ddad12c24..634d41f4df17 100644
--- a/sc/source/ui/view/viewfun2.cxx
+++ b/sc/source/ui/view/viewfun2.cxx
@@ -2031,7 +2031,8 @@ bool ScViewFunc::SearchAndReplace( const SvxSearchItem*
pSearchItem,
{
GetFrameWin()->EnterWait();
ScRangeList aMatchedRanges;
- if (rDoc.SearchAndReplace(*pSearchItem, nCol, nRow, nTab, rMark,
aMatchedRanges, aUndoStr, pUndoDoc.get()))
+ bool bMatchedRangesWereClamped;
+ if (rDoc.SearchAndReplace(*pSearchItem, nCol, nRow, nTab, rMark,
aMatchedRanges, aUndoStr, pUndoDoc.get(), bMatchedRangesWereClamped))
{
bFound = true;
if (bAddUndo)
@@ -2064,7 +2065,7 @@ bool ScViewFunc::SearchAndReplace( const SvxSearchItem*
pSearchItem,
&&
ScDocument::IsEmptyCellSearch(*pSearchItem))
|| (nCommand ==
SvxSearchCmd::REPLACE_ALL
&&
pSearchItem->GetReplaceString().isEmpty())));
- pDlg->FillResults(rDoc, aMatchedRanges,
bCellNotes, bEmptyCells);
+ pDlg->FillResults(rDoc, aMatchedRanges,
bCellNotes, bEmptyCells, bMatchedRangesWereClamped);
}
}
}
@@ -2219,8 +2220,9 @@ bool ScViewFunc::SearchAndReplace( const SvxSearchItem*
pSearchItem,
aSearchItem.SetWhich(SID_SEARCH_ITEM);
ScRangeList aMatchedRanges;
+ bool bMatchedRangesWereClamped;
ScTable::UpdateSearchItemAddressForReplace( aSearchItem,
nCol, nRow );
- if ( rDoc.SearchAndReplace( aSearchItem, nCol, nRow, nTab,
rMark, aMatchedRanges, aUndoStr ) &&
+ if ( rDoc.SearchAndReplace( aSearchItem, nCol, nRow, nTab,
rMark, aMatchedRanges, aUndoStr, nullptr, bMatchedRangesWereClamped ) &&
( nTab == nOldTab ) &&
( nCol != nOldCol || nRow != nOldRow ) )
{
