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>
diff --git a/sw/inc/docary.hxx b/sw/inc/docary.hxx
index 6463534..08e2d8b 100644
--- a/sw/inc/docary.hxx
+++ b/sw/inc/docary.hxx
@@ -224,6 +224,9 @@
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 @@
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 @@
// 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 f7b39e9..af2965f 100644
--- a/sw/source/core/doc/DocumentRedlineManager.cxx
+++ b/sw/source/core/doc/DocumentRedlineManager.cxx
@@ -76,7 +76,7 @@
// 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 @@
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 27fbb81..5e1cae4 100644
--- a/sw/source/core/doc/docredln.cxx
+++ b/sw/source/core/doc/docredln.cxx
@@ -436,11 +436,38 @@
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 @@
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 @@
LOKRedlineNotification(RedlineNotification::Remove, pRedline);
delete pRedline;
}
m_bHasOverlappingElements = false;
}
void SwRedlineTable::DeleteAndDestroy(size_type const nP)
