summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorNoel Grandin <noel.grandin@collabora.co.uk>2022-09-05 09:06:10 +0200
committerNoel Grandin <noel.grandin@collabora.co.uk>2022-09-10 15:40:22 +0200
commit6af4ff17c131b01ea19a78d6963b72815bbb3103 (patch)
treeb399d7e3c3009cad3774c41ab719e6714dc8efcc
parent9b15e86c0a31926f0a5c0b5c5f6f0db639f60c3f (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.mk1
-rw-r--r--external/mdds/speedup-erase-2.patch18
-rw-r--r--sc/inc/document.hxx2
-rw-r--r--sc/inc/strings.hrc1
-rw-r--r--sc/inc/table.hxx4
-rw-r--r--sc/qa/unit/ucalc.cxx27
-rw-r--r--sc/source/core/data/documen3.cxx8
-rw-r--r--sc/source/core/data/table6.cxx13
-rw-r--r--sc/source/ui/dialogs/searchresults.cxx21
-rw-r--r--sc/source/ui/inc/searchresults.hxx4
-rw-r--r--sc/source/ui/unoobj/cellsuno.cxx9
-rw-r--r--sc/source/ui/view/viewfun2.cxx8
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 ) )
{