Keep track of current block position when pasting a range of cells.

This avoids re-starting the search for insertion position in the cell
text attribute array, on every single cell insertion. Instead of always
searching from the first position, it starts the seaarch from the previous
insertion position.

This reduces the paste time from the previous 3.5 seconds to 1.7 seconds
on my machine.

Here is the scenario.

1) Put =A1 in B1, and leave B2 empty.
2) Select B1:B2 and copy it via Ctrl-C.
3) Select B3:B50000, and paste via Ctrl-V.

Because of the empty cells interspersing the destination range, this makes
the data array highly partitioned, which makes the position lookup very
very expensive without the position hint.

Still, I was hoping the duration would become a fraction of a second. 1.7
seconds still seems a bit too slow...

Change-Id: I7742ce7e22935b6d0e082e4569d53dbd2072c4e5

5 files changed, 35 insertions, 1 deletions

diff --git a/sc/inc/clipcontext.hxx b/sc/inc/clipcontext.hxx
index ffe66b0f4951..8b1f26194316 100644
--- a/sc/inc/clipcontext.hxx
+++ b/sc/inc/clipcontext.hxx
@@ -13,12 +13,20 @@
 #include "address.hxx"
 #include "mtvelements.hxx"
 
+#include <vector>
+#include <boost/unordered_map.hpp>
+
 class ScDocument;
 
 namespace sc {
 
 class CopyFromClipContext
 {
+    typedef boost::unordered_map<SCCOL, ColumnBlockPosition> ColumnsType;
+    typedef std::vector<ColumnsType> TablesType;
+
+    TablesType maTables;
+
     ScDocument* mpRefUndoDoc;
     ScDocument* mpClipDoc;
     sal_uInt16  mnInsertFlag;
@@ -33,10 +41,13 @@ public:
         ScDocument* pRefUndoDoc, ScDocument* pClipDoc, sal_uInt16 nInsertFlag,
         bool bAsLink, bool bSkipAttrForEmptyCells);
 
+    bool initBlockPositions(ScDocument& rDoc, SCCOL nCol1, SCCOL nCol2);
     void setTabRange(SCTAB nStart, SCTAB nEnd);
 
     ~CopyFromClipContext();
 
+    ColumnBlockPosition* getBlockPosition(SCTAB nTab, SCCOL nCol);
+
     ScDocument* getUndoDoc();
     ScDocument* getClipDoc();
     sal_uInt16 getInsertFlag() const;
diff --git a/sc/inc/column.hxx b/sc/inc/column.hxx
index 60f766d1d3d3..edf362fb23ad 100644
--- a/sc/inc/column.hxx
+++ b/sc/inc/column.hxx
@@ -39,6 +39,7 @@ namespace sc {
     struct FormulaGroupContext;
     class EndListeningContext;
     class CopyFromClipContext;
+    struct ColumnBlockPosition;
 }
 
 class Fraction;
@@ -160,8 +161,10 @@ public:
     bool    Search( SCROW nRow, SCSIZE& nIndex ) const;
     ScBaseCell* GetCell( SCROW nRow ) const;
     ScRefCellValue GetCellValue( SCROW nRow ) const;
+    void Insert( sc::ColumnBlockPosition& rBlockPos, SCROW nRow, ScBaseCell* pCell );
     void        Insert( SCROW nRow, ScBaseCell* pCell );
     void        Insert( SCROW nRow, sal_uInt32 nFormatIndex, ScBaseCell* pCell );
+    void Append( sc::ColumnBlockPosition& rBlockPos, SCROW nRow, ScBaseCell* pCell );
     void        Append( SCROW nRow, ScBaseCell* pCell );
     void        Delete( SCROW nRow );
     void        DeleteAtIndex( SCSIZE nIndex );
@@ -215,6 +218,7 @@ public:
     void CopyToClip(SCROW nRow1, SCROW nRow2, ScColumn& rColumn, bool bKeepScenarioFlags) const;
     void CopyStaticToDocument(SCROW nRow1, SCROW nRow2, ScColumn& rDestCol);
     void CopyCellToDocument( SCROW nSrcRow, SCROW nDestRow, ScColumn& rDestCol );
+    bool InitBlockPosition( sc::ColumnBlockPosition& rBlockPos );
     void CopyFromClip(
         sc::CopyFromClipContext& rCxt, SCROW nRow1, SCROW nRow2, long nDy, ScColumn& rColumn );
 
@@ -480,7 +484,9 @@ private:
 
     void CopyCellTextAttrsToDocument(SCROW nRow1, SCROW nRow2, ScColumn& rDestCol) const;
 
-    void SetCell(SCROW nRow, ScBaseCell* pNewCell);
+    void SetCell( sc::ColumnBlockPosition& rBlockPos, SCROW nRow, ScBaseCell* pNewCell );
+    void SetCell( SCROW nRow, ScBaseCell* pNewCell );
+    void PostSetCell( SCROW nRow, ScBaseCell* pNewCell );
 };
 
 
diff --git a/sc/inc/document.hxx b/sc/inc/document.hxx
index 4d714714e7b7..c511cf04e3af 100644
--- a/sc/inc/document.hxx
+++ b/sc/inc/document.hxx
@@ -51,6 +51,7 @@ namespace sc {
     struct FormulaGroupContext;
     class EndListeningContext;
     class CopyFromClipContext;
+    struct ColumnBlockPosition;
 }
 class SvxFontItem;
 
@@ -1140,6 +1141,9 @@ public:
 
     void            CopyTabToClip(SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2,
                                 SCTAB nTab, ScDocument* pClipDoc = NULL);
+
+    bool InitColumnBlockPosition( sc::ColumnBlockPosition& rBlokPos, SCTAB nTab, SCCOL nCol );
+
     void CopyBlockFromClip(
         sc::CopyFromClipContext& rCxt, SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2,
         const ScMarkData& rMark, SCsCOL nDx, SCsROW nDy );
diff --git a/sc/inc/mtvelements.hxx b/sc/inc/mtvelements.hxx
index 16113d5bfe61..b21f7c7cc6ca 100644
--- a/sc/inc/mtvelements.hxx
+++ b/sc/inc/mtvelements.hxx
@@ -65,6 +65,15 @@ typedef mdds::multi_type_vector<BCBlkFunc> BroadcasterStoreType;
 typedef mdds::mtv::custom_block_func1<sc::element_type_celltextattr, sc::custom_celltextattr_block> CTAttrFunc;
 typedef mdds::multi_type_vector<CTAttrFunc> CellTextAttrStoreType;
 
+/**
+ * Store position data for column array storage.
+ */
+struct ColumnBlockPosition
+{
+    BroadcasterStoreType::iterator miBroadcasterPos;
+    CellTextAttrStoreType::iterator miCellTextAttrPos;
+};
+
 }
 
 #endif
diff --git a/sc/inc/table.hxx b/sc/inc/table.hxx
index 70fc1cf2ac2f..00255fe2c248 100644
--- a/sc/inc/table.hxx
+++ b/sc/inc/table.hxx
@@ -51,6 +51,7 @@ namespace sc {
     struct FormulaGroupContext;
     class EndListeningContext;
     class CopyFromClipContext;
+    struct ColumnBlockPosition;
 }
 
 class SfxItemSet;
@@ -384,6 +385,9 @@ public:
                            bool bKeepScenarioFlags, bool bCloneNoteCaptions);
     void CopyStaticToDocument(SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2, ScTable* pDestTab);
     void CopyCellToDocument( SCCOL nSrcCol, SCROW nSrcRow, SCCOL nDestCol, SCROW nDestRow, ScTable& rDestTab );
+
+    bool InitColumnBlockPosition( sc::ColumnBlockPosition& rBlockPos, SCCOL nCol );
+
     void CopyFromClip(
         sc::CopyFromClipContext& rCxt, SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2,
         SCsCOL nDx, SCsROW nDy, ScTable* pTable );