Keep track of column block positions when mass-pasting formula cells.

This speeds up the following scenario:

1) type =B1 in A1. Leave A2 empty.
2) Select A1:A2 and Ctrl-C to copy.
3) Select A3:A50000 (or longer if you so wish), and ctrl-V to paste.

This causes the broadcaster storage array in column B to be heavily
partitioned due to the empty cells interspersed between formula cells
in column A.  Without tracking the column position this would cause a
O(n^2) complexity algorithm.

Change-Id: Ic2f23c2c2bea3353c517faa73fe5412c7528bd95

13 files changed, 165 insertions, 41 deletions

diff --git a/sc/inc/column.hxx b/sc/inc/column.hxx
index 46ffbd94af07..6db56d40a889 100644
--- a/sc/inc/column.hxx
+++ b/sc/inc/column.hxx
@@ -37,6 +37,7 @@ namespace editeng { class SvxBorderLine; }
 
 namespace sc {
     struct FormulaGroupContext;
+    class StartListeningContext;
     class EndListeningContext;
     class CopyFromClipContext;
     class CopyToClipContext;
@@ -226,7 +227,7 @@ public:
     void CopyFromClip(
         sc::CopyFromClipContext& rCxt, SCROW nRow1, SCROW nRow2, long nDy, ScColumn& rColumn );
 
-    void        StartListeningInArea( SCROW nRow1, SCROW nRow2 );
+    void StartListeningInArea( sc::StartListeningContext& rCxt, SCROW nRow1, SCROW nRow2 );
     void        BroadcastInArea( SCROW nRow1, SCROW nRow2 );
 
     void        RemoveEditAttribs( SCROW nStartRow, SCROW nEndRow );
@@ -433,6 +434,7 @@ public:
 
     void        StartListening( SvtListener& rLst, SCROW nRow );
     void        EndListening( SvtListener& rLst, SCROW nRow );
+    void StartListening( sc::StartListeningContext& rCxt, SCROW nRow, SvtListener& rListener );
     void EndListening( sc::EndListeningContext& rCxt, SCROW nRow, SvtListener& rListener );
     void        MoveListeners( SvtBroadcaster& rSource, SCROW nDestRow );
     void        StartAllListeners();
diff --git a/sc/inc/document.hxx b/sc/inc/document.hxx
index f01e811eb94e..544c9b50890b 100644
--- a/sc/inc/document.hxx
+++ b/sc/inc/document.hxx
@@ -49,6 +49,7 @@
 namespace editeng { class SvxBorderLine; }
 namespace sc {
     struct FormulaGroupContext;
+    class StartListeningContext;
     class EndListeningContext;
     class CopyFromClipContext;
     struct ColumnBlockPosition;
@@ -1765,6 +1766,7 @@ public:
     void                EndListeningCell( const ScAddress& rAddress,
                                             SvtListener* pListener );
 
+    void StartListeningCell( sc::StartListeningContext& rCxt, const ScAddress& rPos, SvtListener& rListener );
     void EndListeningCell( sc::EndListeningContext& rCxt, const ScAddress& rPos, SvtListener& rListener );
 
     void EndListeningFormulaCells( std::vector<ScFormulaCell*>& rCells );
diff --git a/sc/inc/formulacell.hxx b/sc/inc/formulacell.hxx
index e081353632de..4760062f4f8c 100644
--- a/sc/inc/formulacell.hxx
+++ b/sc/inc/formulacell.hxx
@@ -30,6 +30,7 @@
 
 namespace sc {
 
+class StartListeningContext;
 class EndListeningContext;
 
 }
@@ -313,6 +314,7 @@ public:
 
     // nOnlyNames may be one or more of SC_LISTENING_NAMES_*
     void StartListeningTo( ScDocument* pDoc );
+    void StartListeningTo( sc::StartListeningContext& rCxt );
     void EndListeningTo(
         ScDocument* pDoc, ScTokenArray* pArr = NULL, ScAddress aPos = ScAddress() );
     void EndListeningTo( sc::EndListeningContext& rCxt );
diff --git a/sc/inc/listenercontext.hxx b/sc/inc/listenercontext.hxx
index 36f26d82871e..2503e726408c 100644
--- a/sc/inc/listenercontext.hxx
+++ b/sc/inc/listenercontext.hxx
@@ -12,6 +12,7 @@
 
 #include "address.hxx"
 #include "columnspanset.hxx"
+#include "mtvelements.hxx"
 
 #include <boost/noncopyable.hpp>
 
@@ -19,6 +20,17 @@ class ScDocument;
 
 namespace sc {
 
+class StartListeningContext : boost::noncopyable
+{
+    ScDocument& mrDoc;
+    ColumnBlockPositionSet maSet;
+public:
+    StartListeningContext(ScDocument& rDoc);
+    ScDocument& getDoc();
+
+    ColumnBlockPosition* getBlockPosition(SCTAB nTab, SCCOL nCol);
+};
+
 class EndListeningContext : boost::noncopyable
 {
     ScDocument& mrDoc;
diff --git a/sc/inc/table.hxx b/sc/inc/table.hxx
index f04a9bbe0a47..48fca53a4eb5 100644
--- a/sc/inc/table.hxx
+++ b/sc/inc/table.hxx
@@ -49,6 +49,7 @@ namespace com { namespace sun { namespace star {
 
 namespace sc {
     struct FormulaGroupContext;
+    class StartListeningContext;
     class EndListeningContext;
     class CopyFromClipContext;
     class CopyToClipContext;
@@ -393,8 +394,9 @@ public:
         sc::CopyFromClipContext& rCxt, SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2,
         SCsCOL nDx, SCsROW nDy, ScTable* pTable );
 
-    void        StartListeningInArea( SCCOL nCol1, SCROW nRow1,
-                                        SCCOL nCol2, SCROW nRow2 );
+    void StartListeningInArea(
+        sc::StartListeningContext& rCxt, SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2 );
+
     void        BroadcastInArea( SCCOL nCol1, SCROW nRow1,
                                     SCCOL nCol2, SCROW nRow2 );
 
@@ -948,6 +950,7 @@ private:
 
     void        StartListening( const ScAddress& rAddress, SvtListener* pListener );
     void        EndListening( const ScAddress& rAddress, SvtListener* pListener );
+    void StartListening( sc::StartListeningContext& rCxt, SCCOL nCol, SCROW nRow, SvtListener& rListener );
     void EndListening( sc::EndListeningContext& rCxt, SCCOL nCol, SCROW nRow, SvtListener& rListener );
     void        StartAllListeners();
     void        StartNeededListeners(); // only for cells where NeedsListening()==TRUE
diff --git a/sc/source/core/data/column2.cxx b/sc/source/core/data/column2.cxx
index 3b28d61087a4..828dbe1259c7 100644
--- a/sc/source/core/data/column2.cxx
+++ b/sc/source/core/data/column2.cxx
@@ -2013,17 +2013,18 @@ void ScColumn::FindUsed( SCROW nStartRow, SCROW nEndRow, bool* pUsed ) const
     }
 }
 
-void ScColumn::StartListening( SvtListener& rLst, SCROW nRow )
+namespace {
+
+void startListening(
+    sc::BroadcasterStoreType& rStore, sc::BroadcasterStoreType::iterator& itBlockPos, size_t nElemPos,
+    SCROW nRow, SvtListener& rLst)
 {
-    std::pair<sc::BroadcasterStoreType::iterator,size_t> aPos = maBroadcasters.position(nRow);
-    sc::BroadcasterStoreType::iterator it = aPos.first; // block position.
-    size_t nElemPos = aPos.second; // element position within the block.
-    switch (it->type)
+    switch (itBlockPos->type)
     {
         case sc::element_type_broadcaster:
         {
             // Broadcaster already exists here.
-            SvtBroadcaster* pBC = sc::custom_broadcaster_block::at(*it->data, nElemPos);
+            SvtBroadcaster* pBC = sc::custom_broadcaster_block::at(*itBlockPos->data, nElemPos);
             rLst.StartListening(*pBC);
         }
         break;
@@ -2032,7 +2033,7 @@ void ScColumn::StartListening( SvtListener& rLst, SCROW nRow )
             // No broadcaster exists at this position yet.
             SvtBroadcaster* pBC = new SvtBroadcaster;
             rLst.StartListening(*pBC);
-            maBroadcasters.set(it, nRow, pBC);
+            itBlockPos = rStore.set(itBlockPos, nRow, pBC); // Store the block position for next iteration.
         }
         break;
         default:
@@ -2046,6 +2047,14 @@ void ScColumn::StartListening( SvtListener& rLst, SCROW nRow )
     }
 }
 
+}
+
+void ScColumn::StartListening( SvtListener& rLst, SCROW nRow )
+{
+    std::pair<sc::BroadcasterStoreType::iterator,size_t> aPos = maBroadcasters.position(nRow);
+    startListening(maBroadcasters, aPos.first, aPos.second, nRow, rLst);
+}
+
 void ScColumn::MoveListeners( SvtBroadcaster& rSource, SCROW nDestRow )
 {
     // Move listeners from the source position to the destination position.
@@ -2081,6 +2090,21 @@ void ScColumn::EndListening( SvtListener& rLst, SCROW nRow )
         maBroadcasters.set_empty(nRow, nRow);
 }
 
+void ScColumn::StartListening( sc::StartListeningContext& rCxt, SCROW nRow, SvtListener& rLst )
+{
+    if (!ValidRow(nRow))
+        return;
+
+    sc::ColumnBlockPosition* p = rCxt.getBlockPosition(nTab, nCol);
+    if (!p)
+        return;
+
+    sc::BroadcasterStoreType::iterator& it = p->miBroadcasterPos;
+    std::pair<sc::BroadcasterStoreType::iterator,size_t> aPos = maBroadcasters.position(it, nRow);
+    it = aPos.first; // store the block position for next iteration.
+    startListening(maBroadcasters, it, aPos.second, nRow, rLst);
+}
+
 void ScColumn::EndListening( sc::EndListeningContext& rCxt, SCROW nRow, SvtListener& rListener )
 {
     SvtBroadcaster* pBC = GetBroadcaster(nRow);
diff --git a/sc/source/core/data/column3.cxx b/sc/source/core/data/column3.cxx
index 70d007dca056..60eb8e3e4340 100644
--- a/sc/source/core/data/column3.cxx
+++ b/sc/source/core/data/column3.cxx
@@ -1166,7 +1166,7 @@ void ScColumn::BroadcastInArea( SCROW nRow1, SCROW nRow2 )
 }
 
 
-void ScColumn::StartListeningInArea( SCROW nRow1, SCROW nRow2 )
+void ScColumn::StartListeningInArea( sc::StartListeningContext& rCxt, SCROW nRow1, SCROW nRow2 )
 {
     if (maItems.empty())
         return;
@@ -1178,7 +1178,7 @@ void ScColumn::StartListeningInArea( SCROW nRow1, SCROW nRow2 )
     {
         ScBaseCell* pCell = maItems[nIndex].pCell;
         if ( pCell->GetCellType() == CELLTYPE_FORMULA )
-            ((ScFormulaCell*)pCell)->StartListeningTo( pDocument );
+            ((ScFormulaCell*)pCell)->StartListeningTo(rCxt);
         if ( nRow != maItems[nIndex].nRow )
             Search( nRow, nIndex ); // Inserted via Listening
 
diff --git a/sc/source/core/data/documen7.cxx b/sc/source/core/data/documen7.cxx
index b2406331891e..1c3f66545834 100644
--- a/sc/source/core/data/documen7.cxx
+++ b/sc/source/core/data/documen7.cxx
@@ -201,13 +201,24 @@ void ScDocument::EndListeningCell( const ScAddress& rAddress,
         maTabs[nTab]->EndListening( rAddress, pListener );
 }
 
+void ScDocument::StartListeningCell(
+    sc::StartListeningContext& rCxt, const ScAddress& rPos, SvtListener& rListener )
+{
+    ScTable* pTab = FetchTable(rPos.Tab());
+    if (!pTab)
+        return;
+
+    pTab->StartListening(rCxt, rPos.Col(), rPos.Row(), rListener);
+}
+
 void ScDocument::EndListeningCell(
     sc::EndListeningContext& rCxt, const ScAddress& rPos, SvtListener& rListener )
 {
-    if (!TableExists(rPos.Tab()))
+    ScTable* pTab = FetchTable(rPos.Tab());
+    if (!pTab)
         return;
 
-    maTabs[rPos.Tab()]->EndListening(rCxt, rPos.Col(), rPos.Row(), rListener);
+    pTab->EndListening(rCxt, rPos.Col(), rPos.Row(), rListener);
 }
 
 void ScDocument::EndListeningFormulaCells( std::vector<ScFormulaCell*>& rCells )
diff --git a/sc/source/core/data/document.cxx b/sc/source/core/data/document.cxx
index f41a71521df2..0535388cd4e3 100644
--- a/sc/source/core/data/document.cxx
+++ b/sc/source/core/data/document.cxx
@@ -91,6 +91,7 @@
 #include "formulaiter.hxx"
 #include "formulacell.hxx"
 #include "clipcontext.hxx"
+#include "listenercontext.hxx"
 
 #include <map>
 #include <limits>
@@ -2314,11 +2315,12 @@ void ScDocument::StartListeningFromClip( SCCOL nCol1, SCROW nRow1,
 {
     if (nInsFlag & IDF_CONTENTS)
     {
+        sc::StartListeningContext aCxt(*this);
         SCTAB nMax = static_cast<SCTAB>(maTabs.size());
         ScMarkData::const_iterator itr = rMark.begin(), itrEnd = rMark.end();
         for (; itr != itrEnd && *itr < nMax; ++itr)
             if (maTabs[*itr])
-                maTabs[*itr]->StartListeningInArea( nCol1, nRow1, nCol2, nRow2 );
+                maTabs[*itr]->StartListeningInArea(aCxt, nCol1, nRow1, nCol2, nRow2);
     }
 }
 
diff --git a/sc/source/core/data/formulacell.cxx b/sc/source/core/data/formulacell.cxx
index 30810dfabd72..98df69afe19a 100644
--- a/sc/source/core/data/formulacell.cxx
+++ b/sc/source/core/data/formulacell.cxx
@@ -3162,6 +3162,34 @@ bool ScFormulaCell::InterpretInvariantFormulaGroup()
     return true;
 }
 
+namespace {
+
+void startListeningArea(
+    ScFormulaCell* pCell, ScDocument& rDoc, const ScAddress& rPos, const ScToken& rToken)
+{
+    const ScSingleRefData& rRef1 = rToken.GetSingleRef();
+    const ScSingleRefData& rRef2 = rToken.GetSingleRef2();
+    ScAddress aCell1 = rRef1.toAbs(rPos);
+    ScAddress aCell2 = rRef2.toAbs(rPos);
+    if (aCell1.IsValid() && aCell2.IsValid())
+    {
+        if (rToken.GetOpCode() == ocColRowNameAuto)
+        {   // automagically
+            if ( rRef1.IsColRel() )
+            {   // ColName
+                aCell2.SetRow(MAXROW);
+            }
+            else
+            {   // RowName
+                aCell2.SetCol(MAXCOL);
+            }
+        }
+        rDoc.StartListeningArea(ScRange(aCell1, aCell2), pCell);
+    }
+}
+
+}
+
 void ScFormulaCell::StartListeningTo( ScDocument* pDoc )
 {
     if (pDoc->IsClipOrUndo() || pDoc->GetNoListening() || IsInChangeTrack())
@@ -3181,40 +3209,58 @@ void ScFormulaCell::StartListeningTo( ScDocument* pDoc )
     ScToken* t;
     while ( ( t = static_cast<ScToken*>(pArr->GetNextReferenceRPN()) ) != NULL )
     {
-        StackVar eType = t->GetType();
-        ScSingleRefData& rRef1 = t->GetSingleRef();
-        ScSingleRefData& rRef2 = (eType == svDoubleRef ?
-            t->GetDoubleRef().Ref2 : rRef1);
-        switch( eType )
+        switch (t->GetType())
         {
             case svSingleRef:
             {
-                ScAddress aCell = rRef1.toAbs(aPos);
+                ScAddress aCell =  t->GetSingleRef().toAbs(aPos);
                 if (aCell.IsValid())
                     pDoc->StartListeningCell(aCell, this);
             }
             break;
             case svDoubleRef:
+                startListeningArea(this, *pDoc, aPos, *t);
+            break;
+            default:
+                ;   // nothing
+        }
+    }
+    SetNeedsListening( false);
+}
+
+void ScFormulaCell::StartListeningTo( sc::StartListeningContext& rCxt )
+{
+    ScDocument& rDoc = rCxt.getDoc();
+
+    if (rDoc.IsClipOrUndo() || rDoc.GetNoListening() || IsInChangeTrack())
+        return;
+
+    rDoc.SetDetectiveDirty(true);  // It has changed something
+
+    ScTokenArray* pArr = GetCode();
+    if( pArr->IsRecalcModeAlways() )
+    {
+        rDoc.StartListeningArea(BCA_LISTEN_ALWAYS, this);
+        SetNeedsListening( false);
+        return;
+    }
+
+    pArr->Reset();
+    ScToken* t;
+    while ( ( t = static_cast<ScToken*>(pArr->GetNextReferenceRPN()) ) != NULL )
+    {
+        switch (t->GetType())
+        {
+            case svSingleRef:
             {
-                ScAddress aCell1 = rRef1.toAbs(aPos);
-                ScAddress aCell2 = rRef2.toAbs(aPos);
-                if (aCell1.IsValid() && aCell2.IsValid())
-                {
-                    if (t->GetOpCode() == ocColRowNameAuto)
-                    {   // automagically
-                        if ( rRef1.IsColRel() )
-                        {   // ColName
-                            aCell2.SetRow(MAXROW);
-                        }
-                        else
-                        {   // RowName
-                            aCell2.SetCol(MAXCOL);
-                        }
-                    }
-                    pDoc->StartListeningArea(ScRange(aCell1, aCell2), this);
-                }
+                ScAddress aCell = t->GetSingleRef().toAbs(aPos);
+                if (aCell.IsValid())
+                    rDoc.StartListeningCell(rCxt, aCell, *this);
             }
             break;
+            case svDoubleRef:
+                startListeningArea(this, rDoc, aPos, *t);
+            break;
             default:
                 ;   // nothing
         }
diff --git a/sc/source/core/data/listenercontext.cxx b/sc/source/core/data/listenercontext.cxx
index a288494ef163..7ab3799ad403 100644
--- a/sc/source/core/data/listenercontext.cxx
+++ b/sc/source/core/data/listenercontext.cxx
@@ -28,6 +28,18 @@ public:
 
 }
 
+StartListeningContext::StartListeningContext(ScDocument& rDoc) : mrDoc(rDoc), maSet(rDoc) {}
+
+ScDocument& StartListeningContext::getDoc()
+{
+    return mrDoc;
+}
+
+ColumnBlockPosition* StartListeningContext::getBlockPosition(SCTAB nTab, SCCOL nCol)
+{
+    return maSet.getBlockPosition(nTab, nCol);
+}
+
 EndListeningContext::EndListeningContext(ScDocument& rDoc) : mrDoc(rDoc) {}
 
 ScDocument& EndListeningContext::getDoc()
diff --git a/sc/source/core/data/table2.cxx b/sc/source/core/data/table2.cxx
index 51801afb0f65..0f5d458a38b2 100644
--- a/sc/source/core/data/table2.cxx
+++ b/sc/source/core/data/table2.cxx
@@ -1010,14 +1010,14 @@ void ScTable::BroadcastInArea( SCCOL nCol1, SCROW nRow1,
 }
 
 
-void ScTable::StartListeningInArea( SCCOL nCol1, SCROW nRow1,
-        SCCOL nCol2, SCROW nRow2 )
+void ScTable::StartListeningInArea(
+    sc::StartListeningContext& rCxt, SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2 )
 {
     if (nCol2 > MAXCOL) nCol2 = MAXCOL;
     if (nRow2 > MAXROW) nRow2 = MAXROW;
     if (ValidColRow(nCol1, nRow1) && ValidColRow(nCol2, nRow2))
         for (SCCOL i = nCol1; i <= nCol2; i++)
-            aCol[i].StartListeningInArea( nRow1, nRow2 );
+            aCol[i].StartListeningInArea(rCxt, nRow1, nRow2);
 }
 
 
diff --git a/sc/source/core/data/table5.cxx b/sc/source/core/data/table5.cxx
index 9468352febb0..ed150867ee6d 100644
--- a/sc/source/core/data/table5.cxx
+++ b/sc/source/core/data/table5.cxx
@@ -1097,6 +1097,14 @@ void ScTable::EndListening( const ScAddress& rAddress, SvtListener* pListener )
     aCol[rAddress.Col()].EndListening( *pListener, rAddress.Row() );
 }
 
+void ScTable::StartListening( sc::StartListeningContext& rCxt, SCCOL nCol, SCROW nRow, SvtListener& rListener )
+{
+    if (!ValidCol(nCol))
+        return;
+
+    aCol[nCol].StartListening(rCxt, nRow, rListener);
+}
+
 void ScTable::EndListening( sc::EndListeningContext& rCxt, SCCOL nCol, SCROW nRow, SvtListener& rListener )
 {
     if (!ValidCol(nCol))