Keep track of empty broadcaster segments, and delete them all in one go.

This massively speeds up the deletion of a large group of adjacent formula
cells. As an example, on machine, deletion of formula cells over B2:B109101
(109100 cells in total) got reduced from 4.7 seconds to 0.09 seconds).

Change-Id: Ib72da42a6644421601111907cf7c899d828c2996

5 files changed, 155 insertions, 0 deletions

diff --git a/sc/source/core/data/column2.cxx b/sc/source/core/data/column2.cxx
index 8b383841e05a..ea0aac3946ce 100644
--- a/sc/source/core/data/column2.cxx
+++ b/sc/source/core/data/column2.cxx
@@ -1518,6 +1518,11 @@ const SvtBroadcaster* ScColumn::GetBroadcaster(SCROW nRow) const
     return maBroadcasters.get<SvtBroadcaster*>(nRow);
 }
 
+void ScColumn::DeleteBroadcasters( SCROW nRow1, SCROW nRow2 )
+{
+    maBroadcasters.set_empty(nRow1, nRow2);
+}
+
 sal_uInt16 ScColumn::GetTextWidth(SCROW nRow) const
 {
     return maCellTextAttrs.get<sc::CellTextAttr>(nRow).mnTextWidth;
diff --git a/sc/source/core/data/columnspanset.cxx b/sc/source/core/data/columnspanset.cxx
new file mode 100644
index 000000000000..de785395e4c0
--- /dev/null
+++ b/sc/source/core/data/columnspanset.cxx
@@ -0,0 +1,115 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ */
+
+#include "columnspanset.hxx"
+#include "stlalgorithm.hxx"
+
+#include <algorithm>
+
+namespace sc {
+
+ColumnSpanSet::Action::~Action() {}
+
+ColumnSpanSet::~ColumnSpanSet()
+{
+    DocType::iterator itTab = maDoc.begin(), itTabEnd = maDoc.end();
+    for (; itTab != itTabEnd; ++itTab)
+    {
+        TableType* pTab = *itTab;
+        if (!pTab)
+            continue;
+
+        std::for_each(pTab->begin(), pTab->end(), ScDeleteObjectByPtr<ColumnSpansType>());
+        delete pTab;
+    }
+}
+
+void ColumnSpanSet::set(SCCOL nCol, SCROW nRow, SCTAB nTab, bool bVal)
+{
+    if (!ValidTab(nTab) || !ValidCol(nCol) || !ValidRow(nRow))
+        return;
+
+    if (static_cast<size_t>(nTab) >= maDoc.size())
+        maDoc.resize(nTab+1, NULL);
+
+    if (!maDoc[nTab])
+        maDoc[nTab] = new TableType;
+
+    TableType& rTab = *maDoc[nTab];
+    if (static_cast<size_t>(nCol) >= rTab.size())
+        rTab.resize(nCol+1, NULL);
+
+    if (!rTab[nCol])
+        rTab[nCol] = new ColumnSpansType(0, MAXROW+1, false);
+
+    ColumnSpansType& rCol = *rTab[nCol];
+    rCol.insert_back(nRow, nRow+1, bVal);
+}
+
+void ColumnSpanSet::executeFromTop(Action& ac) const
+{
+    for (size_t nTab = 0; nTab < maDoc.size(); ++nTab)
+    {
+        if (!maDoc[nTab])
+            continue;
+
+        const TableType& rTab = *maDoc[nTab];
+        for (size_t nCol = 0; nCol < rTab.size(); ++nCol)
+        {
+            if (!rTab[nCol])
+                continue;
+
+            ColumnSpansType& rCol = *rTab[nCol];
+            ColumnSpansType::const_iterator it = rCol.begin(), itEnd = rCol.end();
+            SCROW nRow1, nRow2;
+            nRow1 = it->first;
+            for (++it; it != itEnd; ++it)
+            {
+                nRow2 = it->first-1;
+                bool bVal = it->second;
+                ac.execute(ScAddress(nCol, nRow1, nTab), nRow2-nRow1+1, bVal);
+
+                nRow1 = nRow2+1; // for the next iteration.
+            }
+        }
+    }
+}
+
+void ColumnSpanSet::executeFromBottom(Action& ac) const
+{
+    for (size_t nTab = 0; nTab < maDoc.size(); ++nTab)
+    {
+        if (!maDoc[nTab])
+            continue;
+
+        const TableType& rTab = *maDoc[nTab];
+        for (size_t nCol = 0; nCol < rTab.size(); ++nCol)
+        {
+            if (!rTab[nCol])
+                continue;
+
+            ColumnSpansType& rCol = *rTab[nCol];
+            ColumnSpansType::const_reverse_iterator it = rCol.rbegin(), itEnd = rCol.rend();
+            SCROW nRow1, nRow2;
+            nRow2 = it->first-1;
+            for (++it; it != itEnd; ++it)
+            {
+                nRow1 = it->first;
+                bool bVal = it->second;
+                ac.execute(ScAddress(nCol, nRow1, nTab), nRow2-nRow1+1, bVal);
+
+                nRow2 = nRow1-1; // for the next iteration.
+            }
+        }
+    }
+}
+
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/source/core/data/document.cxx b/sc/source/core/data/document.cxx
index d0ec99d834f0..e265c917141c 100644
--- a/sc/source/core/data/document.cxx
+++ b/sc/source/core/data/document.cxx
@@ -2222,6 +2222,14 @@ const SvtBroadcaster* ScDocument::GetBroadcaster( const ScAddress& rPos ) const
     return maTabs[rPos.Tab()]->GetBroadcaster(rPos.Col(), rPos.Row());
 }
 
+void ScDocument::DeleteBroadcasters( const ScAddress& rTopPos, SCROW nLength )
+{
+    if (!TableExists(rTopPos.Tab()) || nLength <= 0)
+        return;
+
+    maTabs[rTopPos.Tab()]->DeleteBroadcasters(rTopPos.Col(), rTopPos.Row(), rTopPos.Row()+nLength-1);
+}
+
 bool ScDocument::TableExists( SCTAB nTab ) const
 {
     return ValidTab(nTab) && static_cast<size_t>(nTab) < maTabs.size() && maTabs[nTab];
diff --git a/sc/source/core/data/listenercontext.cxx b/sc/source/core/data/listenercontext.cxx
index 439f09b8ef9a..4d8afb3ddc08 100644
--- a/sc/source/core/data/listenercontext.cxx
+++ b/sc/source/core/data/listenercontext.cxx
@@ -12,6 +12,22 @@
 
 namespace sc {
 
+namespace {
+
+class PurgeAction : public ColumnSpanSet::Action
+{
+    ScDocument& mrDoc;
+public:
+    PurgeAction(ScDocument& rDoc) : mrDoc(rDoc) {}
+    virtual void execute(const ScAddress& rPos, SCROW nLength, bool bVal)
+    {
+        if (bVal)
+            mrDoc.DeleteBroadcasters(rPos, nLength);
+    };
+};
+
+}
+
 EndListeningContext::EndListeningContext(ScDocument& rDoc) : mrDoc(rDoc) {}
 
 ScDocument& EndListeningContext::getDoc()
@@ -21,10 +37,13 @@ ScDocument& EndListeningContext::getDoc()
 
 void EndListeningContext::addEmptyBroadcasterPosition(SCCOL nCol, SCROW nRow, SCTAB nTab)
 {
+    maSet.set(nCol, nRow, nTab, true);
 }
 
 void EndListeningContext::purgeEmptyBroadcasters()
 {
+    PurgeAction aAction(mrDoc);
+    maSet.executeFromBottom(aAction);
 }
 
 }
diff --git a/sc/source/core/data/table1.cxx b/sc/source/core/data/table1.cxx
index 57315b7ab712..4c50eaf6ddba 100644
--- a/sc/source/core/data/table1.cxx
+++ b/sc/source/core/data/table1.cxx
@@ -2168,6 +2168,14 @@ SvtBroadcaster* ScTable::GetBroadcaster( SCCOL nCol, SCROW nRow )
     return aCol[nCol].GetBroadcaster(nRow);
 }
 
+void ScTable::DeleteBroadcasters( SCCOL nCol, SCROW nRow1, SCROW nRow2 )
+{
+    if (!ValidCol(nCol))
+        return;
+
+    aCol[nCol].DeleteBroadcasters(nRow1, nRow2);
+}
+
 const SvtBroadcaster* ScTable::GetBroadcaster( SCCOL nCol, SCROW nRow ) const
 {
     if (!ValidColRow(nCol, nRow))