cache cell positions when searching in calc (tdf#108347)

The document has a large number of rows, and mdds normally always searches
from the first item when looking up the container position, which leads
to a quadratic cost when searching the entire sheet. GetCellValue()
already has a variant that caches the last position, so just use it
(and make sure to invalidate if it's search&replace and something changes).

Change-Id: I26da60cebf641e10ed92e548fe5f9016900d3cf0
Reviewed-on: https://gerrit.libreoffice.org/72290
Tested-by: Jenkins
Reviewed-by: Luboš Luňák <l.lunak@collabora.com>

4 files changed, 29 insertions, 18 deletions

diff --git a/sc/source/core/data/cellvalue.cxx b/sc/source/core/data/cellvalue.cxx
index b131debdb7a2..7fffc669ee6c 100644
--- a/sc/source/core/data/cellvalue.cxx
+++ b/sc/source/core/data/cellvalue.cxx
@@ -491,7 +491,7 @@ void ScCellValue::release( ScColumn& rColumn, SCROW nRow, sc::StartListeningType
     mfValue = 0.0;
 }
 
-OUString ScCellValue::getString( const ScDocument* pDoc )
+OUString ScCellValue::getString( const ScDocument* pDoc ) const
 {
     return getStringImpl(*this, pDoc);
 }
@@ -647,7 +647,7 @@ double ScRefCellValue::getRawValue() const
     return 0.0;
 }
 
-OUString ScRefCellValue::getString( const ScDocument* pDoc )
+OUString ScRefCellValue::getString( const ScDocument* pDoc ) const
 {
     return getStringImpl(*this, pDoc);
 }
diff --git a/sc/source/core/data/column2.cxx b/sc/source/core/data/column2.cxx
index d1654ac7e49e..bea0497e4c84 100644
--- a/sc/source/core/data/column2.cxx
+++ b/sc/source/core/data/column2.cxx
@@ -1904,6 +1904,11 @@ const ScPostIt* ScColumn::GetCellNote( sc::ColumnBlockConstPosition& rBlockPos,
     return sc::cellnote_block::at(*aPos.first->data, aPos.second);
 }
 
+ScPostIt* ScColumn::GetCellNote( sc::ColumnBlockConstPosition& rBlockPos, SCROW nRow )
+{
+    return const_cast<ScPostIt*>(const_cast<const ScColumn*>(this)->GetCellNote( rBlockPos, nRow ));
+}
+
 void ScColumn::SetCellNote(SCROW nRow, std::unique_ptr<ScPostIt> pNote)
 {
     //pNote->UpdateCaptionPos(ScAddress(nCol, nRow, nTab)); // TODO notes useful ? slow import with many notes
diff --git a/sc/source/core/data/column3.cxx b/sc/source/core/data/column3.cxx
index a760f1428336..26847a3a6126 100644
--- a/sc/source/core/data/column3.cxx
+++ b/sc/source/core/data/column3.cxx
@@ -2822,10 +2822,8 @@ void ScColumn::SetValue(
         BroadcastNewCell(nRow);
 }
 
-void ScColumn::GetString( SCROW nRow, OUString& rString, const ScInterpreterContext* pContext ) const
+void ScColumn::GetString( const ScRefCellValue& aCell, SCROW nRow, OUString& rString, const ScInterpreterContext* pContext ) const
 {
-    ScRefCellValue aCell = GetCellValue(nRow);
-
     // ugly hack for ordering problem with GetNumberFormat and missing inherited formats
     if (aCell.meType == CELLTYPE_FORMULA)
         aCell.mpFormula->MaybeInterpret();
@@ -2849,9 +2847,8 @@ double* ScColumn::GetValueCell( SCROW nRow )
     return &sc::numeric_block::at(*it->data, aPos.second);
 }
 
-void ScColumn::GetInputString( SCROW nRow, OUString& rString ) const
+void ScColumn::GetInputString( const ScRefCellValue& aCell, SCROW nRow, OUString& rString ) const
 {
-    ScRefCellValue aCell = GetCellValue(nRow);
     sal_uLong nFormat = GetNumberFormat(GetDoc()->GetNonThreadedContext(), nRow);
     ScCellFormat::GetInputString(aCell, nFormat, rString, *(GetDoc()->GetFormatTable()), GetDoc());
 }
diff --git a/sc/source/core/data/table6.cxx b/sc/source/core/data/table6.cxx
index 728a86ee744b..4daeb308bfd7 100644
--- a/sc/source/core/data/table6.cxx
+++ b/sc/source/core/data/table6.cxx
@@ -47,7 +47,7 @@ bool lcl_GetTextWithBreaks( const EditTextObject& rData, ScDocument* pDoc, OUStr
 
 }
 
-bool ScTable::SearchCell(const SvxSearchItem& rSearchItem, SCCOL nCol, SCROW nRow,
+bool ScTable::SearchCell(const SvxSearchItem& rSearchItem, SCCOL nCol, sc::ColumnBlockConstPosition& rBlockPos, SCROW nRow,
                          const ScMarkData& rMark, OUString& rUndoStr, ScDocument* pUndoDoc)
 {
     if ( !IsColRowValid( nCol, nRow ) )
@@ -69,13 +69,13 @@ bool ScTable::SearchCell(const SvxSearchItem& rSearchItem, SCCOL nCol, SCROW nRo
     ScPostIt* pNote;
     if (rSearchItem.GetCellType() == SvxSearchCellType::NOTE)
     {
-        pNote = aCol[nCol].GetCellNote(nRow);
+        pNote = aCol[nCol].GetCellNote(rBlockPos, nRow);
         if (!pNote)
             return false;
     }
     else
     {
-        aCell = aCol[nCol].GetCellValue(nRow);
+        aCell = aCol[nCol].GetCellValue(rBlockPos, nRow);
         if (aCell.isEmpty())
             return false;
         pNote = nullptr;
@@ -94,9 +94,9 @@ bool ScTable::SearchCell(const SvxSearchItem& rSearchItem, SCCOL nCol, SCROW nRo
             else
             {
                 if( !bSearchFormatted )
-                    aCol[nCol].GetInputString( nRow, aString );
+                    aCol[nCol].GetInputString( rBlockPos, nRow, aString );
                 else
-                    aCol[nCol].GetString( nRow, aString );
+                    aCol[nCol].GetString( rBlockPos, nRow, aString );
             }
             break;
         }
@@ -106,9 +106,9 @@ bool ScTable::SearchCell(const SvxSearchItem& rSearchItem, SCCOL nCol, SCROW nRo
             else
             {
                 if( !bSearchFormatted )
-                    aCol[nCol].GetInputString( nRow, aString );
+                    aCol[nCol].GetInputString( rBlockPos, nRow, aString );
                 else
-                    aCol[nCol].GetString( nRow, aString );
+                    aCol[nCol].GetString( rBlockPos, nRow, aString );
             }
             break;
         case SvxSearchCellType::NOTE:
@@ -262,6 +262,7 @@ bool ScTable::SearchCell(const SvxSearchItem& rSearchItem, SCCOL nCol, SCROW nRo
         else
             aCol[nCol].SetString(nRow, nTab, aString, pDocument->GetAddressConvention());
         // pCell is invalid now (deleted)
+        aCol[nCol].InitBlockPosition( rBlockPos ); // invalidate also the cached position
     }
     return bFound;
 }
@@ -326,6 +327,10 @@ bool ScTable::Search(const SvxSearchItem& rSearchItem, SCCOL& rCol, SCROW& rRow,
 
     bool bSkipFiltered = !rSearchItem.IsSearchFiltered();
     bool bSearchNotes = (rSearchItem.GetCellType() == SvxSearchCellType::NOTE);
+    // We need to cache sc::ColumnBlockConstPosition per each column.
+    std::vector< sc::ColumnBlockConstPosition > blockPos( nLastCol + 1 );
+    for( SCCOL i = 0; i <= nLastCol; ++i )
+        aCol[ i ].InitBlockPosition( blockPos[ i ] );
     if (!bAll && rSearchItem.GetBackward())
     {
         SCROW nLastNonFilteredRow = MAXROW + 1;
@@ -341,7 +346,8 @@ bool ScTable::Search(const SvxSearchItem& rSearchItem, SCCOL& rCol, SCROW& rRow,
 
                 while (!bFound && (nCol >= 0))
                 {
-                    bFound = SearchCell(rSearchItem, nCol, nRow, rMark, rUndoStr, pUndoDoc);
+                    bFound = SearchCell(rSearchItem, nCol, blockPos[ nCol ], nRow,
+                                        rMark, rUndoStr, pUndoDoc);
                     if (!bFound)
                     {
                         bool bIsEmpty;
@@ -378,7 +384,8 @@ bool ScTable::Search(const SvxSearchItem& rSearchItem, SCCOL& rCol, SCROW& rRow,
                     if (bSkipFiltered)
                         SkipFilteredRows(nRow, nLastNonFilteredRow, false);
 
-                    bFound = SearchCell(rSearchItem, nCol, nRow, rMark, rUndoStr, pUndoDoc);
+                    bFound = SearchCell(rSearchItem, nCol, blockPos[ nCol ],
+                                        nRow, rMark, rUndoStr, pUndoDoc);
                     if (!bFound)
                     {
                         if (bSearchNotes)
@@ -430,7 +437,8 @@ bool ScTable::Search(const SvxSearchItem& rSearchItem, SCCOL& rCol, SCROW& rRow,
 
                 while (!bFound && (nCol <= nLastCol))
                 {
-                    bFound = SearchCell(rSearchItem, nCol, nRow, rMark, rUndoStr, pUndoDoc);
+                    bFound = SearchCell(rSearchItem, nCol, blockPos[ nCol ],
+                                        nRow, rMark, rUndoStr, pUndoDoc);
                     if (!bFound)
                     {
                         nCol++;
@@ -456,7 +464,8 @@ bool ScTable::Search(const SvxSearchItem& rSearchItem, SCCOL& rCol, SCROW& rRow,
                     if (bSkipFiltered)
                         SkipFilteredRows(nRow, nLastNonFilteredRow, true);
 
-                    bFound = SearchCell(rSearchItem, nCol, nRow, rMark, rUndoStr, pUndoDoc);
+                    bFound = SearchCell(rSearchItem, nCol, blockPos[ nCol ],
+                                        nRow, rMark, rUndoStr, pUndoDoc);
                     if (!bFound)
                     {
                         if (bSearchNotes)