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(-)
New commits:
commit d467cd0dd9e9cf3b018859a592e2638527bc7add
Author: Noel Grandin <n...@peralex.com>
AuthorDate: Sat Aug 28 16:51:33 2021 +0200
Commit: Noel Grandin <noel.gran...@collabora.co.uk>
CommitDate: Tue Sep 14 19:55:18 2021 +0200
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.gran...@collabora.co.uk>
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)
