diff options
author | Noel Grandin <noel.grandin@collabora.co.uk> | 2022-09-05 09:06:10 +0200 |
---|---|---|
committer | Noel Grandin <noel.grandin@collabora.co.uk> | 2022-09-10 15:40:22 +0200 |
commit | 6af4ff17c131b01ea19a78d6963b72815bbb3103 (patch) | |
tree | b399d7e3c3009cad3774c41ab719e6714dc8efcc | |
parent | 9b15e86c0a31926f0a5c0b5c5f6f0db639f60c3f (diff) |
tdf#150749 Find and replace on very large sheetcp-22.05.6-1
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.grandin@collabora.co.uk>
(cherry picked from commit 462053a26070db6e7c8ec818c816d64d1d82782b)
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/139424
Tested-by: Jenkins CollaboraOffice <jenkinscollaboraoffice@gmail.com>
-rw-r--r-- | external/mdds/UnpackedTarball_mdds.mk | 1 | ||||
-rw-r--r-- | external/mdds/speedup-erase-2.patch | 18 | ||||
-rw-r--r-- | sc/inc/document.hxx | 2 | ||||
-rw-r--r-- | sc/inc/strings.hrc | 1 | ||||
-rw-r--r-- | sc/inc/table.hxx | 4 | ||||
-rw-r--r-- | sc/qa/unit/ucalc.cxx | 27 | ||||
-rw-r--r-- | sc/source/core/data/documen3.cxx | 8 | ||||
-rw-r--r-- | sc/source/core/data/table6.cxx | 13 | ||||
-rw-r--r-- | sc/source/ui/dialogs/searchresults.cxx | 21 | ||||
-rw-r--r-- | sc/source/ui/inc/searchresults.hxx | 4 | ||||
-rw-r--r-- | sc/source/ui/unoobj/cellsuno.cxx | 9 | ||||
-rw-r--r-- | sc/source/ui/view/viewfun2.cxx | 8 |
12 files changed, 71 insertions, 45 deletions
diff --git a/external/mdds/UnpackedTarball_mdds.mk b/external/mdds/UnpackedTarball_mdds.mk index 22ba1d88785d..5f72853c6310 100644 --- a/external/mdds/UnpackedTarball_mdds.mk +++ b/external/mdds/UnpackedTarball_mdds.mk @@ -15,6 +15,7 @@ $(eval $(call gb_UnpackedTarball_set_patchlevel,mdds,0)) $(eval $(call gb_UnpackedTarball_add_patches,mdds,\ 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 bfa235581bd0..1c26604a4fb5 100644 --- a/sc/inc/document.hxx +++ b/sc/inc/document.hxx @@ -1925,7 +1925,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 2b94667d6d6f..2e225cead604 100644 --- a/sc/inc/strings.hrc +++ b/sc/inc/strings.hrc @@ -58,6 +58,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 302803966a58..6511c3405429 100644 --- a/sc/inc/table.hxx +++ b/sc/inc/table.hxx @@ -700,7 +700,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 ); @@ -1189,7 +1189,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 9c4d5810c78c..9b67fcdd8a4f 100644 --- a/sc/qa/unit/ucalc.cxx +++ b/sc/qa/unit/ucalc.cxx @@ -451,30 +451,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(); @@ -4336,7 +4320,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 cef949a14a7b..77517f5739e4 100644 --- a/sc/source/core/data/documen3.cxx +++ b/sc/source/core/data/documen3.cxx @@ -1306,7 +1306,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; @@ -1331,7 +1331,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); } } @@ -1349,7 +1349,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; @@ -1380,7 +1380,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 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(); } 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 6ee791bf7212..7649c4a6a9be 100644 --- a/sc/source/ui/unoobj/cellsuno.cxx +++ b/sc/source/ui/unoobj/cellsuno.cxx @@ -3783,8 +3783,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 @@ -3829,8 +3830,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 ); @@ -3939,8 +3941,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 d39405c9b89b..6dd9cae7d188 100644 --- a/sc/source/ui/view/viewfun2.cxx +++ b/sc/source/ui/view/viewfun2.cxx @@ -1998,7 +1998,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) @@ -2031,7 +2032,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); } } } @@ -2186,8 +2187,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 ) ) { |