sw/inc/ndhints.hxx | 48 +++++++++++-----
sw/source/core/txtnode/atrref.cxx | 10 ++-
sw/source/core/txtnode/atrtox.cxx | 10 ++-
sw/source/core/txtnode/ndhints.cxx | 103 +++++++++++++++++++++++++++++-------
sw/source/core/txtnode/thints.cxx | 11 +--
sw/source/core/txtnode/txatbase.cxx | 10 ++-
6 files changed, 144 insertions(+), 48 deletions(-)
New commits:
commit 365e356b66ed98426ba06347ef29e58a02885579
Author: Noel Grandin <noel.gran...@collabora.co.uk>
AuthorDate: Fri Jun 14 11:09:51 2024 +0200
Commit: Noel Grandin <noel.gran...@collabora.co.uk>
CommitDate: Fri Jun 14 22:08:15 2024 +0200
tdf#144208 speedup doc with lots of redline (11)
reduce the amount of sorting work we need to do in the m_HintsBy*
maps, by storing the range of elements we need to resort
Change-Id: I93bd22c9bfcf41f7c02828e184ff1170700cdcc5
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/168857
Reviewed-by: Noel Grandin <noel.gran...@collabora.co.uk>
Tested-by: Jenkins
diff --git a/sw/inc/ndhints.hxx b/sw/inc/ndhints.hxx
index ceead82cecd9..e5d43d5973f7 100644
--- a/sw/inc/ndhints.hxx
+++ b/sw/inc/ndhints.hxx
@@ -57,10 +57,14 @@ struct CompareSwpHtEnd
bool operator()( sal_Int32 nEndPos, const SwTextAttr* rhs ) const;
bool operator()( const SwTextAttr* lhs, const SwTextAttr* rhs ) const;
};
+typedef std::pair<sal_Int32, sal_Int32> WhichStartPair;
struct CompareSwpHtWhichStart
{
bool operator()( const SwTextAttr* lhs, const sal_uInt16 nWhich ) const;
bool operator()( const SwTextAttr* lhs, const SwTextAttr* rhs ) const;
+ // used when we sort only a partial range of the map
+ bool operator()( const SwTextAttr* lhs, const WhichStartPair nWhich )
const;
+ bool operator()( const WhichStartPair nWhich, const SwTextAttr* lhs )
const;
};
/// An SwTextAttr container, stores all directly formatted text portions for a
text node.
@@ -89,9 +93,11 @@ private:
bool m_bFootnote : 1; ///< footnotes
bool m_bDDEFields : 1; ///< the TextNode has DDE
fields
// Sort on demand to avoid O(n^2) behaviour
- mutable bool m_bStartMapNeedsSorting : 1;
- mutable bool m_bEndMapNeedsSorting : 1;
- mutable bool m_bWhichMapNeedsSorting : 1;
+ // SAL_MAX_INT32 means nothing needs sorting, -1 means everything needs
sorting
+ mutable std::pair<sal_Int32, sal_Int32> m_StartMapNeedsSortingRange {
SAL_MAX_INT32, -1 };
+ mutable std::pair<sal_Int32, sal_Int32> m_EndMapNeedsSortingRange {
SAL_MAX_INT32, -1 };
+ // we are storing pairs of { Which, Start } here
+ mutable std::pair<WhichStartPair, WhichStartPair>
m_WhichMapNeedsSortingRange { { SAL_MAX_INT32, -1 }, { -1, -1 } };
/// records a new attribute in m_pHistory.
void NoteInHistory( SwTextAttr *pAttr, const bool bNew = false );
@@ -143,8 +149,8 @@ public:
bool Contains( const SwTextAttr *pHt ) const;
SwTextAttr * Get( size_t nPos ) const
{
- assert( !(nPos != 0 && m_bStartMapNeedsSorting) && "going to trigger a
resort in the middle of an iteration, that's bad" );
- if (m_bStartMapNeedsSorting)
+ assert( !(nPos != 0 && m_StartMapNeedsSortingRange.first !=
SAL_MAX_INT32) && "going to trigger a resort in the middle of an iteration,
that's bad" );
+ if (m_StartMapNeedsSortingRange.first != SAL_MAX_INT32)
ResortStartMap();
return m_HintsByStart[nPos];
}
@@ -157,8 +163,8 @@ public:
int GetLastPosSortedByEnd(sal_Int32 nEndPos) const;
SwTextAttr * GetSortedByEnd( size_t nPos ) const
{
- assert( !(nPos != 0 && m_bEndMapNeedsSorting) && "going to trigger a
resort in the middle of an iteration, that's bad" );
- if (m_bEndMapNeedsSorting)
+ assert( !(nPos != 0 && m_EndMapNeedsSortingRange.first !=
SAL_MAX_INT32) && "going to trigger a resort in the middle of an iteration,
that's bad" );
+ if (m_EndMapNeedsSortingRange.first != SAL_MAX_INT32)
ResortEndMap();
return m_HintsByEnd[nPos];
}
@@ -166,8 +172,8 @@ public:
size_t GetFirstPosSortedByWhichAndStart(sal_uInt16 nWhich) const;
SwTextAttr * GetSortedByWhichAndStart( size_t nPos ) const
{
- assert( !(nPos != 0 && m_bWhichMapNeedsSorting) && "going to trigger a
resort in the middle of an iteration, that's bad" );
- if (m_bWhichMapNeedsSorting)
+ assert( !(nPos != 0 && m_WhichMapNeedsSortingRange.first.first !=
SAL_MAX_INT32) && "going to trigger a resort in the middle of an iteration,
that's bad" );
+ if (m_WhichMapNeedsSortingRange.first.first != SAL_MAX_INT32)
ResortWhichMap();
return m_HintsByWhichAndStart[nPos];
}
@@ -175,11 +181,11 @@ public:
/// Trigger the sorting if necessary
void SortIfNeedBe() const
{
- if (m_bStartMapNeedsSorting)
+ if (m_StartMapNeedsSortingRange.first != SAL_MAX_INT32)
ResortStartMap();
- if (m_bEndMapNeedsSorting)
+ if (m_EndMapNeedsSortingRange.first != SAL_MAX_INT32)
ResortEndMap();
- if (m_bWhichMapNeedsSorting)
+ if (m_WhichMapNeedsSortingRange.first.first != SAL_MAX_INT32)
ResortWhichMap();
}
SwTextAttr * Cut( const size_t nPosInStart )
@@ -209,8 +215,22 @@ public:
bool CalcHiddenParaField() const; // changes mutable state
// Marks the hint-maps as needing sorting because the position of
something has changed
- void StartPosChanged() const { m_bStartMapNeedsSorting = true;
m_bEndMapNeedsSorting = true; m_bWhichMapNeedsSorting = true; }
- void EndPosChanged() const { m_bStartMapNeedsSorting = true;
m_bEndMapNeedsSorting = true; m_bWhichMapNeedsSorting = true; }
+ void StartPosChanged() const
+ {
+ m_StartMapNeedsSortingRange = { -1, -1 };
+ m_EndMapNeedsSortingRange = { -1, -1 };
+ m_WhichMapNeedsSortingRange = { { -1, -1 }, { -1, -1 } };
+ }
+ void EndPosChanged(sal_uInt16 nWhich, sal_Int32 nStartPos, sal_Int32
nOldEndPos, sal_Int32 nNewEndPos) const
+ {
+ m_StartMapNeedsSortingRange = { std::min(nStartPos,
m_StartMapNeedsSortingRange.first),
+ std::max(nStartPos,
m_StartMapNeedsSortingRange.second) };
+ m_EndMapNeedsSortingRange = { std::min(std::min(nOldEndPos,
nNewEndPos), m_EndMapNeedsSortingRange.first),
+ std::max(std::max(nOldEndPos,
nNewEndPos), m_EndMapNeedsSortingRange.second) };
+ WhichStartPair aPair { sal_Int32(nWhich), nStartPos };
+ m_WhichMapNeedsSortingRange = { std::min(aPair,
m_WhichMapNeedsSortingRange.first),
+ std::max(aPair,
m_WhichMapNeedsSortingRange.second) };
+ }
};
#endif
diff --git a/sw/source/core/txtnode/atrref.cxx
b/sw/source/core/txtnode/atrref.cxx
index 6800c40993eb..bfd932545496 100644
--- a/sw/source/core/txtnode/atrref.cxx
+++ b/sw/source/core/txtnode/atrref.cxx
@@ -162,9 +162,13 @@ const sal_Int32* SwTextRefMark::GetEnd() const
void SwTextRefMark::SetEnd(sal_Int32 n)
{
- *m_pEnd = n;
- if (m_pHints)
- m_pHints->EndPosChanged();
+ if (*m_pEnd != n)
+ {
+ sal_Int32 nOldEndPos = *m_pEnd;
+ *m_pEnd = n;
+ if (m_pHints)
+ m_pHints->EndPosChanged(Which(), GetStart(), nOldEndPos, *m_pEnd);
+ }
}
void SwTextRefMark::UpdateFieldContent(SwDoc* pDoc, SwWrtShell& rWrtSh,
OUString aContent)
diff --git a/sw/source/core/txtnode/atrtox.cxx
b/sw/source/core/txtnode/atrtox.cxx
index 17093db9be0b..b56e75c1a97f 100644
--- a/sw/source/core/txtnode/atrtox.cxx
+++ b/sw/source/core/txtnode/atrtox.cxx
@@ -56,9 +56,13 @@ const sal_Int32* SwTextTOXMark::GetEnd() const
void SwTextTOXMark::SetEnd(sal_Int32 n)
{
- *m_pEnd = n;
- if (m_pHints)
- m_pHints->EndPosChanged();
+ if (*m_pEnd != n)
+ {
+ sal_Int32 nOldEndPos = *m_pEnd;
+ *m_pEnd = n;
+ if (m_pHints)
+ m_pHints->EndPosChanged(Which(), GetStart(), nOldEndPos, *m_pEnd);
+ }
}
void SwTextTOXMark::CopyTOXMark( SwDoc& rDoc )
diff --git a/sw/source/core/txtnode/ndhints.cxx
b/sw/source/core/txtnode/ndhints.cxx
index f5f234d45e80..b7f82239a22e 100644
--- a/sw/source/core/txtnode/ndhints.cxx
+++ b/sw/source/core/txtnode/ndhints.cxx
@@ -64,6 +64,33 @@ static bool CompareSwpHtStart( const SwTextAttr* lhs, const
SwTextAttr* rhs )
return ( rHt1.GetStart() < rHt2.GetStart() );
}
+/// sort order: Start
+/// (char style: sort number), at last the pointer
+namespace {
+struct CompareSwpHtStartOnly
+{
+ bool operator()( const SwTextAttr* lhs, sal_Int32 rhs ) const
+ {
+ return lhs->GetStart() < rhs;
+ }
+ bool operator()( sal_Int32 lhs, const SwTextAttr* rhs ) const
+ {
+ return lhs < rhs->GetStart();
+ }
+};
+struct CompareSwpHtEndOnly
+{
+ bool operator()( const SwTextAttr* lhs, sal_Int32 rhs ) const
+ {
+ return lhs->GetAnyEnd() < rhs;
+ }
+ bool operator()( sal_Int32 lhs, const SwTextAttr* rhs ) const
+ {
+ return lhs < rhs->GetAnyEnd();
+ }
+};
+}
+
/// sort order: Which, Start, End(reverse) at last the pointer
bool CompareSwpHtWhichStart::operator()( const SwTextAttr* lhs, const
sal_uInt16 nWhich ) const
{
@@ -100,6 +127,22 @@ bool CompareSwpHtWhichStart::operator()( const SwTextAttr*
lhs, const SwTextAttr
return false;
return reinterpret_cast<sal_IntPtr>(&rHt1) <
reinterpret_cast<sal_IntPtr>(&rHt2);
}
+bool CompareSwpHtWhichStart::operator()( const SwTextAttr* lhs, const
WhichStartPair rhs ) const
+{
+ if ( lhs->Which() < rhs.first )
+ return true;
+ if ( lhs->Which() > rhs.first )
+ return false;
+ return lhs->GetStart() < rhs.second;
+}
+bool CompareSwpHtWhichStart::operator()( const WhichStartPair lhs, const
SwTextAttr* rhs ) const
+{
+ if ( lhs.first < rhs->Which() )
+ return true;
+ if ( lhs.first > rhs->Which() )
+ return false;
+ return lhs.second < rhs->GetStart();
+}
/// sort order: End, Start(reverse), Which
/// (char style: sort number), at last the pointer(reverse)
@@ -149,12 +192,9 @@ void SwpHints::Insert(SwTextAttr* pHt)
assert( pHt->m_pHints == nullptr );
pHt->m_pHints = this;
- if (m_bStartMapNeedsSorting)
- ResortStartMap();
- if (m_bEndMapNeedsSorting)
- ResortEndMap();
- if (m_bWhichMapNeedsSorting)
- ResortWhichMap();
+ ResortStartMap();
+ ResortEndMap();
+ ResortWhichMap();
auto it1 = std::lower_bound(m_HintsByStart.begin(), m_HintsByStart.end(),
pHt, CompareSwpHtStart);
m_HintsByStart.insert(it1, pHt);
@@ -412,37 +452,64 @@ void SwpHints::Resort() const
void SwpHints::ResortStartMap() const
{
- if (m_bStartMapNeedsSorting)
+ if (m_StartMapNeedsSortingRange.first != SAL_MAX_INT32)
{
auto & rStartMap = const_cast<SwpHints*>(this)->m_HintsByStart;
- std::sort(rStartMap.begin(), rStartMap.end(), CompareSwpHtStart);
- m_bStartMapNeedsSorting = false;
+ if (m_StartMapNeedsSortingRange.first == -1)
+ std::sort(rStartMap.begin(), rStartMap.end(), CompareSwpHtStart);
+ else
+ {
+ // only need to sort a partial range of the array
+ auto it1 = std::lower_bound(rStartMap.begin(), rStartMap.end(),
m_StartMapNeedsSortingRange.first, CompareSwpHtStartOnly());
+ auto it2 = std::upper_bound(rStartMap.begin(), rStartMap.end(),
m_StartMapNeedsSortingRange.second, CompareSwpHtStartOnly());
+ std::sort(rStartMap.begin() + std::distance(rStartMap.begin(),
it1),
+ rStartMap.begin() + std::distance(rStartMap.begin(),
it2), CompareSwpHtStart);
+ }
+ m_StartMapNeedsSortingRange = { SAL_MAX_INT32, -1 };
}
}
void SwpHints::ResortEndMap() const
{
- if (m_bEndMapNeedsSorting)
+ if (m_EndMapNeedsSortingRange.first != SAL_MAX_INT32)
{
auto & rEndMap = const_cast<SwpHints*>(this)->m_HintsByEnd;
- std::sort(rEndMap.begin(), rEndMap.end(), CompareSwpHtEnd());
- m_bEndMapNeedsSorting = false;
+ if (m_EndMapNeedsSortingRange.first == -1)
+ std::sort(rEndMap.begin(), rEndMap.end(), CompareSwpHtEnd());
+ else
+ {
+ // only need to sort a partial range of the array
+ auto it1 = std::lower_bound(rEndMap.begin(), rEndMap.end(),
m_EndMapNeedsSortingRange.first, CompareSwpHtEndOnly());
+ auto it2 = std::upper_bound(rEndMap.begin(), rEndMap.end(),
m_EndMapNeedsSortingRange.second, CompareSwpHtEndOnly());
+ std::sort(rEndMap.begin() + std::distance(rEndMap.begin(), it1),
+ rEndMap.begin() + std::distance(rEndMap.begin(), it2),
CompareSwpHtEnd());
+ }
+ m_EndMapNeedsSortingRange = { SAL_MAX_INT32, -1 };
}
}
void SwpHints::ResortWhichMap() const
{
- if (m_bWhichMapNeedsSorting)
+ if (m_WhichMapNeedsSortingRange.first.first != SAL_MAX_INT32)
{
auto & rWhichStartMap =
const_cast<SwpHints*>(this)->m_HintsByWhichAndStart;
- std::sort(rWhichStartMap.begin(), rWhichStartMap.end(),
CompareSwpHtWhichStart());
- m_bWhichMapNeedsSorting = false;
+ if (m_WhichMapNeedsSortingRange.first.first == -1)
+ std::sort(rWhichStartMap.begin(), rWhichStartMap.end(),
CompareSwpHtWhichStart());
+ else
+ {
+ // only need to sort a partial range of the array
+ auto it1 = std::lower_bound(rWhichStartMap.begin(),
rWhichStartMap.end(), m_WhichMapNeedsSortingRange.first,
CompareSwpHtWhichStart());
+ auto it2 = std::upper_bound(rWhichStartMap.begin(),
rWhichStartMap.end(), m_WhichMapNeedsSortingRange.second,
CompareSwpHtWhichStart());
+ std::sort(rWhichStartMap.begin() +
std::distance(rWhichStartMap.begin(), it1),
+ rWhichStartMap.begin() +
std::distance(rWhichStartMap.begin(), it2), CompareSwpHtWhichStart());
+ }
+ m_WhichMapNeedsSortingRange = { { SAL_MAX_INT32, -1 }, { -1, -1 } };
}
}
size_t SwpHints::GetFirstPosSortedByWhichAndStart( sal_uInt16 nWhich ) const
{
- if (m_bWhichMapNeedsSorting)
+ if (m_WhichMapNeedsSortingRange.first.first != SAL_MAX_INT32)
ResortWhichMap();
auto it = std::lower_bound(m_HintsByWhichAndStart.begin(),
m_HintsByWhichAndStart.end(), nWhich, CompareSwpHtWhichStart());
if ( it == m_HintsByWhichAndStart.end() )
@@ -452,7 +519,7 @@ size_t SwpHints::GetFirstPosSortedByWhichAndStart(
sal_uInt16 nWhich ) const
int SwpHints::GetLastPosSortedByEnd( sal_Int32 nEndPos ) const
{
- if (m_bEndMapNeedsSorting)
+ if (m_EndMapNeedsSortingRange.first != SAL_MAX_INT32)
ResortEndMap();
auto it = std::upper_bound(m_HintsByEnd.begin(), m_HintsByEnd.end(),
nEndPos, CompareSwpHtEnd());
return it - m_HintsByEnd.begin() - 1;
@@ -460,7 +527,7 @@ int SwpHints::GetLastPosSortedByEnd( sal_Int32 nEndPos )
const
size_t SwpHints::GetIndexOf( const SwTextAttr *pHt ) const
{
- if (m_bStartMapNeedsSorting)
+ if (m_StartMapNeedsSortingRange.first != SAL_MAX_INT32)
ResortStartMap();
auto it = std::lower_bound(m_HintsByStart.begin(), m_HintsByStart.end(),
const_cast<SwTextAttr*>(pHt), CompareSwpHtStart);
if ( it == m_HintsByStart.end() || *it != pHt )
diff --git a/sw/source/core/txtnode/thints.cxx
b/sw/source/core/txtnode/thints.cxx
index 4aae2af56eb8..9ab24d03af75 100644
--- a/sw/source/core/txtnode/thints.cxx
+++ b/sw/source/core/txtnode/thints.cxx
@@ -98,9 +98,6 @@ SwpHints::SwpHints(const SwTextNode& rParent)
, m_bHiddenByParaField(false)
, m_bFootnote(false)
, m_bDDEFields(false)
- , m_bStartMapNeedsSorting(false)
- , m_bEndMapNeedsSorting(false)
- , m_bWhichMapNeedsSorting(false)
{
}
@@ -3390,7 +3387,7 @@ bool SwpHints::TryInsertHint(
void SwpHints::DeleteAtPos( const size_t nPos )
{
- assert(!m_bStartMapNeedsSorting && "deleting at pos and the list needs
sorting?");
+ assert(m_StartMapNeedsSortingRange.first == SAL_MAX_INT32 && "deleting at
pos and the list needs sorting?");
SwTextAttr *pHint = Get(nPos);
assert( pHint->m_pHints == this );
@@ -3401,11 +3398,11 @@ void SwpHints::DeleteAtPos( const size_t nPos )
SwTextAttr *pHt = m_HintsByStart[ nPos ];
m_HintsByStart.erase( m_HintsByStart.begin() + nPos );
- if (m_bStartMapNeedsSorting)
+ if (m_StartMapNeedsSortingRange.first != SAL_MAX_INT32)
ResortStartMap();
- if (m_bEndMapNeedsSorting)
+ if (m_EndMapNeedsSortingRange.first != SAL_MAX_INT32)
ResortEndMap();
- if (m_bWhichMapNeedsSorting)
+ if (m_WhichMapNeedsSortingRange.first.first != SAL_MAX_INT32)
ResortWhichMap();
auto findIt = std::lower_bound(m_HintsByEnd.begin(), m_HintsByEnd.end(),
pHt, CompareSwpHtEnd());
diff --git a/sw/source/core/txtnode/txatbase.cxx
b/sw/source/core/txtnode/txatbase.cxx
index 968a7b2d2b77..7b10d29297d8 100644
--- a/sw/source/core/txtnode/txatbase.cxx
+++ b/sw/source/core/txtnode/txatbase.cxx
@@ -81,9 +81,13 @@ const sal_Int32* SwTextAttrEnd::GetEnd() const
void SwTextAttrEnd::SetEnd(sal_Int32 n)
{
- m_nEnd = n;
- if (m_pHints)
- m_pHints->EndPosChanged();
+ if (m_nEnd != n)
+ {
+ sal_Int32 nOldEndPos = m_nEnd;
+ m_nEnd = n;
+ if (m_pHints)
+ m_pHints->EndPosChanged(Which(), GetStart(), nOldEndPos, m_nEnd);
+ }
}
void SwTextAttr::dumpAsXml(xmlTextWriterPtr pWriter) const
