From b81004e95638da19cbcaa7a61f9edd094a9eac31 Mon Sep 17 00:00:00 2001 From: Luboš Luňák Date: Thu, 16 May 2019 17:50:09 +0200 Subject: cache mdds positions during ScDocument::CopyBlockFromClip() (tdf#112000) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Make RefUpdateContext and ScColumn::UpdateReferenceOnCopy() use the same sc::ColumnBlockPositionSet that CopyFromClipContext uses. Without it pathological cases like in tdf#112000 trigger quadratic cost because of repeated mdds searches from the start. Includes also an mdds patch that allows it to search backwards from a position hint. Without it, this would be very difficult to fix otherwise, as CopyFromClip() in ScDocument::CopyBlockFromClip() moves the position hint past the area that UpdateReferenceOnCopy() would use. It also just plain makes sense to try to go backwards in an std::vector. Change-Id: I985e3a40e4abf1a824e55c76d82579882fa75cc2 Reviewed-on: https://gerrit.libreoffice.org/72424 Tested-by: Jenkins Reviewed-by: Luboš Luňák --- sc/inc/clipcontext.hxx | 1 + sc/inc/column.hxx | 2 +- sc/inc/refupdatecontext.hxx | 8 ++++++++ sc/source/core/data/column.cxx | 8 ++++++-- sc/source/core/data/document.cxx | 1 + sc/source/core/data/refupdatecontext.cxx | 13 ++++++++++++- 6 files changed, 29 insertions(+), 4 deletions(-) (limited to 'sc') diff --git a/sc/inc/clipcontext.hxx b/sc/inc/clipcontext.hxx index f2a7af56818b..6752104fb34c 100644 --- a/sc/inc/clipcontext.hxx +++ b/sc/inc/clipcontext.hxx @@ -40,6 +40,7 @@ public: virtual ~ClipContextBase(); ColumnBlockPosition* getBlockPosition(SCTAB nTab, SCCOL nCol); + ColumnBlockPositionSet* getBlockPositionSet() { return mpSet.get(); } }; class CopyFromClipContext : public ClipContextBase diff --git a/sc/inc/column.hxx b/sc/inc/column.hxx index 340b5628faf6..e7e40fd528bf 100644 --- a/sc/inc/column.hxx +++ b/sc/inc/column.hxx @@ -417,7 +417,7 @@ public: void ResetChanged( SCROW nStartRow, SCROW nEndRow ); - bool UpdateReferenceOnCopy( const sc::RefUpdateContext& rCxt, ScDocument* pUndoDoc = nullptr ); + bool UpdateReferenceOnCopy( sc::RefUpdateContext& rCxt, ScDocument* pUndoDoc = nullptr ); /** * Update reference addresses in formula cell in response to mass cell diff --git a/sc/inc/refupdatecontext.hxx b/sc/inc/refupdatecontext.hxx index 7b5afe926e1a..bc86cb9e1afe 100644 --- a/sc/inc/refupdatecontext.hxx +++ b/sc/inc/refupdatecontext.hxx @@ -21,6 +21,9 @@ class ScDocument; namespace sc { +struct ColumnBlockPosition; +class ColumnBlockPositionSet; + /** * Keep track of all named expressions that have been updated during * reference update. @@ -76,10 +79,15 @@ struct RefUpdateContext UpdatedRangeNames maUpdatedNames; ColumnSet maRegroupCols; + ColumnBlockPositionSet* mpBlockPos; // not owning + RefUpdateContext(ScDocument& rDoc); bool isInserted() const; bool isDeleted() const; + + void setBlockPositionReference( ColumnBlockPositionSet* blockPos ); + ColumnBlockPosition* getBlockPosition(SCTAB nTab, SCCOL nCol); }; struct RefUpdateResult diff --git a/sc/source/core/data/column.cxx b/sc/source/core/data/column.cxx index 548e6403cc8b..18132d2fc454 100644 --- a/sc/source/core/data/column.cxx +++ b/sc/source/core/data/column.cxx @@ -42,6 +42,7 @@ #include #include #include +#include #include #include @@ -2424,14 +2425,17 @@ public: } -bool ScColumn::UpdateReferenceOnCopy( const sc::RefUpdateContext& rCxt, ScDocument* pUndoDoc ) +bool ScColumn::UpdateReferenceOnCopy( sc::RefUpdateContext& rCxt, ScDocument* pUndoDoc ) { // When copying, the range equals the destination range where cells // are pasted, and the dx, dy, dz refer to the distance from the // source range. UpdateRefOnCopy aHandler(rCxt, pUndoDoc); - sc::CellStoreType::position_type aPos = maCells.position(rCxt.maRange.aStart.Row()); + sc::ColumnBlockPosition* blockPos = rCxt.getBlockPosition(nTab, nCol); + sc::CellStoreType::position_type aPos = blockPos + ? maCells.position(blockPos->miCellPos, rCxt.maRange.aStart.Row()) + : maCells.position(rCxt.maRange.aStart.Row()); sc::ProcessBlock(aPos.first, maCells, aHandler, rCxt.maRange.aStart.Row(), rCxt.maRange.aEnd.Row()); // The formula groups at the top and bottom boundaries are expected to diff --git a/sc/source/core/data/document.cxx b/sc/source/core/data/document.cxx index 4e74fc8dbf56..106ca902534e 100644 --- a/sc/source/core/data/document.cxx +++ b/sc/source/core/data/document.cxx @@ -2675,6 +2675,7 @@ void ScDocument::CopyBlockFromClip( aRefCxt.mnColDelta = nDx; aRefCxt.mnRowDelta = nDy; aRefCxt.mnTabDelta = nDz; + aRefCxt.setBlockPositionReference(rCxt.getBlockPositionSet()); // share mdds position caching if (rCxt.getClipDoc()->GetClipParam().mbCutMode) { // Update references only if cut originates from the same diff --git a/sc/source/core/data/refupdatecontext.cxx b/sc/source/core/data/refupdatecontext.cxx index d4cce81dc680..c34ac6860ee1 100644 --- a/sc/source/core/data/refupdatecontext.cxx +++ b/sc/source/core/data/refupdatecontext.cxx @@ -9,6 +9,7 @@ #include #include +#include namespace sc { @@ -64,7 +65,7 @@ bool UpdatedRangeNames::isEmpty(SCTAB nTab) const RefUpdateContext::RefUpdateContext(ScDocument& rDoc) : - mrDoc(rDoc), meMode(URM_INSDEL), mnColDelta(0), mnRowDelta(0), mnTabDelta(0) {} + mrDoc(rDoc), meMode(URM_INSDEL), mnColDelta(0), mnRowDelta(0), mnTabDelta(0), mpBlockPos( nullptr ) {} bool RefUpdateContext::isInserted() const { @@ -76,6 +77,16 @@ bool RefUpdateContext::isDeleted() const return (meMode == URM_INSDEL) && (mnColDelta < 0 || mnRowDelta < 0 || mnTabDelta < 0); } +void RefUpdateContext::setBlockPositionReference( ColumnBlockPositionSet* blockPos ) +{ + mpBlockPos = blockPos; +} + +ColumnBlockPosition* RefUpdateContext::getBlockPosition(SCTAB nTab, SCCOL nCol) +{ + return mpBlockPos ? mpBlockPos->getBlockPosition(nTab, nCol) : nullptr; +} + RefUpdateResult::RefUpdateResult() : mbValueChanged(false), mbReferenceModified(false), mbNameModified(false) {} RefUpdateInsertTabContext::RefUpdateInsertTabContext(ScDocument& rDoc, SCTAB nInsertPos, SCTAB nSheets) : -- cgit