From 6af4ff17c131b01ea19a78d6963b72815bbb3103 Mon Sep 17 00:00:00 2001 From: Noel Grandin Date: Mon, 5 Sep 2022 09:06:10 +0200 Subject: 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 (cherry picked from commit 462053a26070db6e7c8ec818c816d64d1d82782b) Reviewed-on: https://gerrit.libreoffice.org/c/core/+/139424 Tested-by: Jenkins CollaboraOffice --- sc/source/core/data/table6.cxx | 13 +++++++++---- 1 file changed, 9 insertions(+), 4 deletions(-) (limited to 'sc/source/core/data/table6.cxx') diff --git a/sc/source/core/data/table6.cxx b/sc/source/core/data/table6.cxx index 0ced56900d6d..f5eb5b74cf85 100644 --- a/sc/source/core/data/table6.cxx +++ b/sc/source/core/data/table6.cxx @@ -579,7 +579,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; @@ -603,7 +603,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; @@ -793,7 +798,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; @@ -845,7 +850,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(); } -- cgit