tdf#135683 speedup DocumentRedlineManager::GetRedlinePos

use binary search

Change-Id: Icd442ba18cb27cdcb5955fa8bbce421b26d5ad44
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/121205
Tested-by: Jenkins
Reviewed-by: Noel Grandin <noel.grandin@collabora.co.uk>

3 files changed, 74 insertions, 11 deletions

diff --git a/sw/inc/docary.hxx b/sw/inc/docary.hxx
index 64635347f631..08e2d8b761dd 100644
--- a/sw/inc/docary.hxx
+++ b/sw/inc/docary.hxx
@@ -224,6 +224,9 @@ public:
     static constexpr size_type npos = SAL_MAX_INT32;
 private:
     vector_type maVector;
+    /// Sometimes we load bad data, and we need to know if we can use
+    /// fast binary search, or if we have to fall back to a linear search
+    bool m_bHasOverlappingElements;
 public:
     ~SwRedlineTable();
     bool Contains(const SwRangeRedline* p) const { return maVector.find(const_cast<SwRangeRedline*>(p)) != maVector.end(); }
@@ -232,6 +235,7 @@ public:
     bool Insert(SwRangeRedline*& p);
     bool Insert(SwRangeRedline*& p, size_type& rInsPos);
     bool InsertWithValidRanges(SwRangeRedline*& p, size_type* pInsPos = nullptr);
+    bool HasOverlappingElements() const { return m_bHasOverlappingElements; }
 
     void Remove( size_type nPos );
     void Remove( const SwRangeRedline* p );
@@ -266,6 +270,9 @@ public:
 
     // Notifies all LOK clients when redlines are added/modified/removed
     static void                 LOKRedlineNotification(RedlineNotification eType, SwRangeRedline* pRedline);
+
+private:
+    void CheckOverlapping(vector_type::const_iterator it);
 };
 
 /// Table that holds 'extra' redlines, such as 'table row insert/delete', 'paragraph moves' etc...
diff --git a/sw/source/core/doc/DocumentRedlineManager.cxx b/sw/source/core/doc/DocumentRedlineManager.cxx
index f7b39e9840d0..af2965f9d4bd 100644
--- a/sw/source/core/doc/DocumentRedlineManager.cxx
+++ b/sw/source/core/doc/DocumentRedlineManager.cxx
@@ -76,7 +76,7 @@ using namespace com::sun::star;
 
         // check validity of the redline table. Checks redline bounds, and make
         // sure the redlines are sorted and non-overlapping.
-        void lcl_CheckRedline( IDocumentRedlineAccess& redlineAccess )
+        void lcl_CheckRedline( const IDocumentRedlineAccess& redlineAccess )
         {
             const SwRedlineTable& rTable = redlineAccess.GetRedlineTable();
 
@@ -2620,19 +2620,45 @@ bool DocumentRedlineManager::DeleteRedline( const SwStartNode& rNode, bool bSave
 SwRedlineTable::size_type DocumentRedlineManager::GetRedlinePos( const SwNode& rNd, RedlineType nType ) const
 {
     const sal_uLong nNdIdx = rNd.GetIndex();
-    for( SwRedlineTable::size_type n = 0; n < maRedlineTable.size() ; ++n )
+    // if the table only contains good (i.e. non-overlapping) data, we can do a binary search
+    if (!maRedlineTable.HasOverlappingElements())
     {
-        const SwRangeRedline* pTmp = maRedlineTable[ n ];
-        sal_uLong nPt = pTmp->GetPoint()->nNode.GetIndex(),
-              nMk = pTmp->GetMark()->nNode.GetIndex();
-        if( nPt < nMk ) { tools::Long nTmp = nMk; nMk = nPt; nPt = nTmp; }
+        // binary search to the first redline with end >= the needle
+        auto it = std::lower_bound(maRedlineTable.begin(), maRedlineTable.end(), rNd,
+            [&nNdIdx](const SwRangeRedline* lhs, const SwNode& /*rhs*/)
+            {
+                return lhs->End()->nNode.GetIndex() < nNdIdx;
+            });
+        for( ; it != maRedlineTable.end(); ++it)
+        {
+            const SwRangeRedline* pTmp = *it;
+            sal_uLong nStart = pTmp->Start()->nNode.GetIndex(),
+                      nEnd = pTmp->End()->nNode.GetIndex();
 
-        if( ( RedlineType::Any == nType || nType == pTmp->GetType()) &&
-            nMk <= nNdIdx && nNdIdx <= nPt )
-            return n;
+            if( ( RedlineType::Any == nType || nType == pTmp->GetType()) &&
+                nStart <= nNdIdx && nNdIdx <= nEnd )
+                return std::distance(maRedlineTable.begin(), it);
 
-        if( nMk > nNdIdx )
-            break;
+            if( nStart > nNdIdx )
+                break;
+        }
+    }
+    else
+    {
+        for( SwRedlineTable::size_type n = 0; n < maRedlineTable.size() ; ++n )
+        {
+            const SwRangeRedline* pTmp = maRedlineTable[ n ];
+            sal_uLong nPt = pTmp->GetPoint()->nNode.GetIndex(),
+                  nMk = pTmp->GetMark()->nNode.GetIndex();
+            if( nPt < nMk ) { tools::Long nTmp = nMk; nMk = nPt; nPt = nTmp; }
+
+            if( ( RedlineType::Any == nType || nType == pTmp->GetType()) &&
+                nMk <= nNdIdx && nNdIdx <= nPt )
+                return n;
+
+            if( nMk > nNdIdx )
+                break;
+        }
     }
     return SwRedlineTable::npos;
 
diff --git a/sw/source/core/doc/docredln.cxx b/sw/source/core/doc/docredln.cxx
index 27fbb81534f5..5e1cae4132be 100644
--- a/sw/source/core/doc/docredln.cxx
+++ b/sw/source/core/doc/docredln.cxx
@@ -436,11 +436,38 @@ bool SwRedlineTable::Insert(SwRangeRedline*& p)
         size_type nP = rv.first - begin();
         LOKRedlineNotification(RedlineNotification::Add, p);
         p->CallDisplayFunc(nP);
+        if (rv.second)
+            CheckOverlapping(rv.first);
         return rv.second;
     }
     return InsertWithValidRanges( p );
 }
 
+void SwRedlineTable::CheckOverlapping(vector_type::const_iterator it)
+{
+    if (m_bHasOverlappingElements)
+        return;
+    if (maVector.size() <= 1) // a single element cannot be overlapping
+        return;
+    auto pCurr = *it;
+    auto itNext = it + 1;
+    if (itNext != maVector.end())
+    {
+        auto pNext = *itNext;
+        if (pCurr->End()->nNode.GetIndex() >= pNext->Start()->nNode.GetIndex())
+        {
+            m_bHasOverlappingElements = true;
+            return;
+        }
+    }
+    if (it != maVector.begin())
+    {
+        auto pPrev = *(it - 1);
+        if (pPrev->End()->nNode.GetIndex() >= pCurr->Start()->nNode.GetIndex())
+            m_bHasOverlappingElements = true;
+    }
+}
+
 bool SwRedlineTable::Insert(SwRangeRedline*& p, size_type& rP)
 {
     if( p->HasValidRange() )
@@ -448,6 +475,8 @@ bool SwRedlineTable::Insert(SwRangeRedline*& p, size_type& rP)
         std::pair<vector_type::const_iterator, bool> rv = maVector.insert( p );
         rP = rv.first - begin();
         p->CallDisplayFunc(rP);
+        if (rv.second)
+            CheckOverlapping(rv.first);
         return rv.second;
     }
     return InsertWithValidRanges( p, &rP );
@@ -640,6 +669,7 @@ void SwRedlineTable::DeleteAndDestroyAll()
         LOKRedlineNotification(RedlineNotification::Remove, pRedline);
         delete pRedline;
     }
+    m_bHasOverlappingElements = false;
 }
 
 void SwRedlineTable::DeleteAndDestroy(size_type const nP)