From d467cd0dd9e9cf3b018859a592e2638527bc7add Mon Sep 17 00:00:00 2001 From: Noel Grandin Date: Sat, 28 Aug 2021 16:51:33 +0200 Subject: 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 --- sw/inc/docary.hxx | 7 ++++ sw/source/core/doc/DocumentRedlineManager.cxx | 48 +++++++++++++++++++++------ sw/source/core/doc/docredln.cxx | 30 +++++++++++++++++ 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(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 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) -- cgit