1 files changed, 37 insertions, 11 deletions

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;