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>

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 )