diff options
author | Noel Grandin <noel.grandin@collabora.co.uk> | 2019-05-29 12:51:15 +0200 |
---|---|---|
committer | Noel Grandin <noel.grandin@collabora.co.uk> | 2019-05-30 09:40:08 +0200 |
commit | 799dac2e621bf14f613b3ee4f6a711b49c0c5e81 (patch) | |
tree | 58195809acf0d4299bad65095853952457193c70 /sw | |
parent | c329a1c11299b999152b45343961e79e66be405a (diff) |
tdf#125372 writer, file with lots of hints very slow to open, part5
Takes load time from 3m to 2m11
(*) Add a list sorted by which/start
(*) Use it in lcl_GetTextAttrs
(*) Fix GetLastPosSortedByEnd, previously we could potentially
static_cast the search item to something it is not
(*) Add assert to SwpHints::DeleteAtPos to verify that we don't need
sorting of the main list when deleting.
Change-Id: If82ea650172ca88486507f31b45cac8d22682451
Reviewed-on: https://gerrit.libreoffice.org/73152
Tested-by: Jenkins
Reviewed-by: Noel Grandin <noel.grandin@collabora.co.uk>
Diffstat (limited to 'sw')
-rw-r--r-- | sw/inc/ndhints.hxx | 32 | ||||
-rw-r--r-- | sw/source/core/txtnode/ndhints.cxx | 90 | ||||
-rw-r--r-- | sw/source/core/txtnode/ndtxt.cxx | 16 | ||||
-rw-r--r-- | sw/source/core/txtnode/thints.cxx | 12 |
4 files changed, 122 insertions, 28 deletions
diff --git a/sw/inc/ndhints.hxx b/sw/inc/ndhints.hxx index 299218a55399..a2b8a86be3c0 100644 --- a/sw/inc/ndhints.hxx +++ b/sw/inc/ndhints.hxx @@ -54,8 +54,16 @@ SwTextAttr* MakeRedlineTextAttr( SwDoc & rDoc, SfxPoolItem const & rAttr ); -bool CompareSwpHtEnd( const SwTextAttr* lhs, const SwTextAttr* rhs ); -bool CompareSwpHtWhichStart( const SwTextAttr* lhs, const SwTextAttr* rhs ); +struct CompareSwpHtEnd +{ + bool operator()( sal_Int32 nEndPos, const SwTextAttr* rhs ) const; + bool operator()( const SwTextAttr* lhs, const SwTextAttr* rhs ) const; +}; +struct CompareSwpHtWhichStart +{ + bool operator()( const SwTextAttr* lhs, const sal_uInt16 nWhich ) const; + bool operator()( const SwTextAttr* lhs, const SwTextAttr* rhs ) const; +}; /// An SwTextAttr container, stores all directly formatted text portions for a text node. class SwpHints @@ -69,6 +77,7 @@ private: std::vector<SwTextAttr*> m_HintsByStart; std::vector<SwTextAttr*> m_HintsByEnd; + std::vector<SwTextAttr*> m_HintsByWhichAndStart; SwRegHistory* m_pHistory; ///< for Undo @@ -84,6 +93,7 @@ private: // Sort on demand to avoid O(n^2) behaviour mutable bool m_bStartMapNeedsSorting : 1; mutable bool m_bEndMapNeedsSorting : 1; + mutable bool m_bWhichMapNeedsSorting : 1; /// records a new attribute in m_pHistory. void NoteInHistory( SwTextAttr *pAttr, const bool bNew = false ); @@ -120,6 +130,7 @@ private: SW_DLLPUBLIC void Resort() const; SW_DLLPUBLIC void ResortStartMap() const; SW_DLLPUBLIC void ResortEndMap() const; + SW_DLLPUBLIC void ResortWhichMap() const; size_t GetIndexOf( const SwTextAttr *pHt ) const; @@ -144,6 +155,7 @@ public: { return m_HintsByStart[nPos]; } + int GetLastPosSortedByEnd(sal_Int32 nEndPos) const; SwTextAttr * GetSortedByEnd( size_t nPos ) const { @@ -152,6 +164,16 @@ public: ResortEndMap(); return m_HintsByEnd[nPos]; } + + 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) + ResortWhichMap(); + return m_HintsByWhichAndStart[nPos]; + } + /// Trigger the sorting if necessary void SortIfNeedBe() const { @@ -159,6 +181,8 @@ public: ResortStartMap(); if (m_bEndMapNeedsSorting) ResortEndMap(); + if (m_bWhichMapNeedsSorting) + ResortWhichMap(); } SwTextAttr * Cut( const size_t nPosInStart ) { @@ -187,8 +211,8 @@ 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; } - void EndPosChanged() const { m_bStartMapNeedsSorting = true; m_bEndMapNeedsSorting = true; } + void StartPosChanged() const { m_bStartMapNeedsSorting = true; m_bEndMapNeedsSorting = true; m_bWhichMapNeedsSorting = true; } + void EndPosChanged() const { m_bStartMapNeedsSorting = true; m_bEndMapNeedsSorting = true; m_bWhichMapNeedsSorting = true; } }; #endif diff --git a/sw/source/core/txtnode/ndhints.cxx b/sw/source/core/txtnode/ndhints.cxx index 00647e23cd1f..c77d31e31a89 100644 --- a/sw/source/core/txtnode/ndhints.cxx +++ b/sw/source/core/txtnode/ndhints.cxx @@ -66,9 +66,50 @@ static bool CompareSwpHtStart( const SwTextAttr* lhs, const SwTextAttr* rhs ) return ( rHt1.GetStart() < rHt2.GetStart() ); } -/// sort order: End (reverse), Start, Which (reverse), -/// (char style: sort number), at last the pointer -bool CompareSwpHtEnd( const SwTextAttr* lhs, const SwTextAttr* rhs ) +/// sort order: Which, Start, End(reverse) at last the pointer +bool CompareSwpHtWhichStart::operator()( const SwTextAttr* lhs, const sal_uInt16 nWhich ) const +{ + return lhs->Which() < nWhich; +} +bool CompareSwpHtWhichStart::operator()( const SwTextAttr* lhs, const SwTextAttr* rhs ) const +{ + const SwTextAttr &rHt1 = *lhs; + const SwTextAttr &rHt2 = *rhs; + const sal_uInt16 nWhich1 = rHt1.Which(); + const sal_uInt16 nWhich2 = rHt2.Which(); + if ( nWhich1 < nWhich2 ) + return true; + if ( nWhich1 > nWhich2 ) + return false; + if (rHt1.GetStart() < rHt2.GetStart()) + return true; + if (rHt1.GetStart() > rHt2.GetStart()) + return false; + if ( RES_TXTATR_CHARFMT == nWhich1 ) + { + const sal_uInt16 nS1 = + static_txtattr_cast<const SwTextCharFormat&>(rHt1).GetSortNumber(); + const sal_uInt16 nS2 = + static_txtattr_cast<const SwTextCharFormat&>(rHt2).GetSortNumber(); + if ( nS1 != nS2 ) // robust + return nS1 < nS2; + } + const sal_Int32 nEnd1 = *rHt1.GetAnyEnd(); + const sal_Int32 nEnd2 = *rHt2.GetAnyEnd(); + if ( nEnd1 > nEnd2 ) + return true; + if ( nEnd1 < nEnd2 ) + return false; + return reinterpret_cast<sal_IntPtr>(&rHt1) < reinterpret_cast<sal_IntPtr>(&rHt2); +} + +/// sort order: End, Start(reverse), Which +/// (char style: sort number), at last the pointer(reverse) +bool CompareSwpHtEnd::operator()( sal_Int32 nEndPos, const SwTextAttr* rhs ) const +{ + return nEndPos < *rhs->GetAnyEnd(); +} +bool CompareSwpHtEnd::operator()( const SwTextAttr* lhs, const SwTextAttr* rhs ) const { const SwTextAttr &rHt1 = *lhs; const SwTextAttr &rHt2 = *rhs; @@ -85,9 +126,9 @@ bool CompareSwpHtEnd( const SwTextAttr* lhs, const SwTextAttr* rhs ) if ( RES_TXTATR_CHARFMT == nWhich1 ) { const sal_uInt16 nS1 = - static_txtattr_cast<const SwTextCharFormat&>(rHt1).GetSortNumber(); + static_txtattr_cast<const SwTextCharFormat&>(rHt1).GetSortNumber(); const sal_uInt16 nS2 = - static_txtattr_cast<const SwTextCharFormat&>(rHt2).GetSortNumber(); + static_txtattr_cast<const SwTextCharFormat&>(rHt2).GetSortNumber(); if ( nS1 != nS2 ) // robust return nS1 > nS2; } @@ -114,12 +155,17 @@ void SwpHints::Insert( const SwTextAttr *pHt ) ResortStartMap(); if (m_bEndMapNeedsSorting) ResortEndMap(); + if (m_bWhichMapNeedsSorting) + ResortWhichMap(); auto it1 = std::lower_bound(m_HintsByStart.begin(), m_HintsByStart.end(), const_cast<SwTextAttr*>(pHt), CompareSwpHtStart); m_HintsByStart.insert(it1, const_cast<SwTextAttr*>(pHt)); - auto it2 = std::lower_bound(m_HintsByEnd.begin(), m_HintsByEnd.end(), const_cast<SwTextAttr*>(pHt), CompareSwpHtEnd); + auto it2 = std::lower_bound(m_HintsByEnd.begin(), m_HintsByEnd.end(), const_cast<SwTextAttr*>(pHt), CompareSwpHtEnd()); m_HintsByEnd.insert(it2, const_cast<SwTextAttr*>(pHt)); + + auto it3 = std::lower_bound(m_HintsByWhichAndStart.begin(), m_HintsByWhichAndStart.end(), const_cast<SwTextAttr*>(pHt), CompareSwpHtWhichStart()); + m_HintsByWhichAndStart.insert(it3, const_cast<SwTextAttr*>(pHt)); } bool SwpHints::Contains( const SwTextAttr *pHt ) const @@ -200,7 +246,7 @@ bool SwpHints::Check(bool bPortionsMerged) const // 4b) IsLessEnd consistency if( pLastEnd ) - CHECK_ERR( CompareSwpHtEnd( pLastEnd, pHtEnd ), "HintsCheck: IsLastEnd" ); + CHECK_ERR( CompareSwpHtEnd()( pLastEnd, pHtEnd ), "HintsCheck: IsLastEnd" ); nLastEnd = nIdx; pLastEnd = pHtEnd; @@ -214,7 +260,7 @@ bool SwpHints::Check(bool bPortionsMerged) const CHECK_ERR( COMPLETE_STRING != nIdx, "HintsCheck: no GetStartOf" ); // 6) same pointers in both arrays - if (std::lower_bound(m_HintsByEnd.begin(), m_HintsByEnd.end(), const_cast<SwTextAttr*>(pHt), CompareSwpHtEnd) == m_HintsByEnd.end()) + if (std::lower_bound(m_HintsByEnd.begin(), m_HintsByEnd.end(), const_cast<SwTextAttr*>(pHt), CompareSwpHtEnd()) == m_HintsByEnd.end()) nIdx = COMPLETE_STRING; CHECK_ERR( COMPLETE_STRING != nIdx, "HintsCheck: no GetEndOf" ); @@ -370,9 +416,12 @@ void SwpHints::Resort() const auto & rStartMap = const_cast<SwpHints*>(this)->m_HintsByStart; std::sort(rStartMap.begin(), rStartMap.end(), CompareSwpHtStart); auto & rEndMap = const_cast<SwpHints*>(this)->m_HintsByEnd; - std::sort(rEndMap.begin(), rEndMap.end(), CompareSwpHtEnd); + std::sort(rEndMap.begin(), rEndMap.end(), CompareSwpHtEnd()); + auto & rWhichStartMap = const_cast<SwpHints*>(this)->m_HintsByWhichAndStart; + std::sort(rWhichStartMap.begin(), rWhichStartMap.end(), CompareSwpHtWhichStart()); m_bStartMapNeedsSorting = false; m_bEndMapNeedsSorting = false; + m_bWhichMapNeedsSorting = false; } void SwpHints::ResortStartMap() const @@ -385,17 +434,32 @@ void SwpHints::ResortStartMap() const void SwpHints::ResortEndMap() const { auto & rEndMap = const_cast<SwpHints*>(this)->m_HintsByEnd; - std::sort(rEndMap.begin(), rEndMap.end(), CompareSwpHtEnd); + std::sort(rEndMap.begin(), rEndMap.end(), CompareSwpHtEnd()); m_bEndMapNeedsSorting = false; } +void SwpHints::ResortWhichMap() const +{ + m_bWhichMapNeedsSorting = false; + auto & rWhichStartMap = const_cast<SwpHints*>(this)->m_HintsByWhichAndStart; + std::sort(rWhichStartMap.begin(), rWhichStartMap.end(), CompareSwpHtWhichStart()); +} + +size_t SwpHints::GetFirstPosSortedByWhichAndStart( sal_uInt16 nWhich ) const +{ + if (m_bWhichMapNeedsSorting) + ResortWhichMap(); + auto it = std::lower_bound(m_HintsByWhichAndStart.begin(), m_HintsByWhichAndStart.end(), nWhich, CompareSwpHtWhichStart()); + if ( it == m_HintsByWhichAndStart.end() ) + return SAL_MAX_SIZE; + return it - m_HintsByWhichAndStart.begin(); +} + int SwpHints::GetLastPosSortedByEnd( sal_Int32 nEndPos ) const { if (m_bEndMapNeedsSorting) ResortEndMap(); - SfxBoolItem aFindItem(0); - SwTextAttrEnd aTmp(aFindItem, nEndPos, nEndPos); - auto it = std::upper_bound(m_HintsByEnd.begin(), m_HintsByEnd.end(), &aTmp, CompareSwpHtEnd); + auto it = std::upper_bound(m_HintsByEnd.begin(), m_HintsByEnd.end(), nEndPos, CompareSwpHtEnd()); return it - m_HintsByEnd.begin() - 1; } diff --git a/sw/source/core/txtnode/ndtxt.cxx b/sw/source/core/txtnode/ndtxt.cxx index 4135b308fcc0..4a8ee16f7503 100644 --- a/sw/source/core/txtnode/ndtxt.cxx +++ b/sw/source/core/txtnode/ndtxt.cxx @@ -1672,19 +1672,15 @@ lcl_GetTextAttrs( default: assert(false); } - for( size_t i = 0; i < nSize; ++i ) + for( size_t i = pSwpHints->GetFirstPosSortedByWhichAndStart(nWhich); i < nSize; ++i ) { - SwTextAttr *const pHint = pSwpHints->Get(i); + SwTextAttr *const pHint = pSwpHints->GetSortedByWhichAndStart(i); + if (pHint->Which() != nWhich) + break; // hints are sorted by which&start, so we are done... + sal_Int32 const nHintStart = pHint->GetStart(); if (nIndex < nHintStart) - { - return; // hints are sorted by start, so we are done... - } - - if (pHint->Which() != nWhich) - { - continue; - } + break; // hints are sorted by which&start, so we are done... sal_Int32 const*const pEndIdx = pHint->GetEnd(); // cannot have hint with no end and no dummy char diff --git a/sw/source/core/txtnode/thints.cxx b/sw/source/core/txtnode/thints.cxx index 3a1584098813..a53ae1cf0593 100644 --- a/sw/source/core/txtnode/thints.cxx +++ b/sw/source/core/txtnode/thints.cxx @@ -102,6 +102,7 @@ SwpHints::SwpHints(const SwTextNode& rParent) , m_bDDEFields(false) , m_bStartMapNeedsSorting(false) , m_bEndMapNeedsSorting(false) + , m_bWhichMapNeedsSorting(false) { } @@ -3275,6 +3276,8 @@ bool SwpHints::TryInsertHint( void SwpHints::DeleteAtPos( const size_t nPos ) { + assert(!m_bStartMapNeedsSorting && "deleting at pos and the list needs sorting?"); + SwTextAttr *pHint = Get(nPos); assert( pHint->m_pHints == this ); // ChainDelete( pHint ); @@ -3288,10 +3291,17 @@ void SwpHints::DeleteAtPos( const size_t nPos ) ResortStartMap(); if (m_bEndMapNeedsSorting) ResortEndMap(); + if (m_bWhichMapNeedsSorting) + ResortWhichMap(); - auto findIt = std::lower_bound(m_HintsByEnd.begin(), m_HintsByEnd.end(), pHt, CompareSwpHtEnd); + auto findIt = std::lower_bound(m_HintsByEnd.begin(), m_HintsByEnd.end(), pHt, CompareSwpHtEnd()); assert(*findIt == pHt); m_HintsByEnd.erase(findIt); + + auto findIt2 = std::lower_bound(m_HintsByWhichAndStart.begin(), m_HintsByWhichAndStart.end(), pHt, CompareSwpHtWhichStart()); + assert(*findIt2 == pHt); + m_HintsByWhichAndStart.erase(findIt2); + pHt->m_pHints = nullptr; if( pHint->Which() == RES_TXTATR_FIELD ) |