sw/source/core/doc/docbm.cxx | 58 ++++++++++++++++++++++++++++++-------------
1 file changed, 41 insertions(+), 17 deletions(-)
New commits:
commit 5850b22e04a7a055e5b4c6b23a1d32d74270506d
Author: Bjoern Michaelsen <bjoern.michael...@libreoffice.org>
AuthorDate: Sat Aug 3 02:31:03 2024 +0200
Commit: Bjoern Michaelsen <bjoern.michael...@libreoffice.org>
CommitDate: Sun Aug 4 12:10:20 2024 +0200
speed up getInnerFieldmarkFor some more with bisectional and reverse search
prerequisites:
- the fieldmark vector is sorted by field start
- a fieldmark start and end either have to both be in any other
fieldmark, or both be outside of it
strategy:
- first we find the last fieldmark before our position (those behind it
will never cover the position)
- then iterate backwards to find the first that ends behind the position
(and thus covers it)
- the innermost fieldmark is now either the fieldmark found, or another
fieldmark starting at the same position:
* fieldmarks starting before the one we found will not be the innermost
* thus we only need to iterate check to the first fieldmark starting
earlier
There are further optimizations, that likely arent worth it, e.g.:
- sort the fieldmarks with the same start position by length or end
position (longest first), this would remove the need for the last step
Change-Id: I49164697a44ff0a5e11809dfba82029c160c5d2a
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/171442
Tested-by: Jenkins
Reviewed-by: Bjoern Michaelsen <bjoern.michael...@libreoffice.org>
diff --git a/sw/source/core/doc/docbm.cxx b/sw/source/core/doc/docbm.cxx
index 19661ad37ff0..dab51bb1d39a 100644
--- a/sw/source/core/doc/docbm.cxx
+++ b/sw/source/core/doc/docbm.cxx
@@ -324,6 +324,13 @@ namespace
}
};
+ struct CompareIMarkStartsAfterReverse
+ {
+ bool operator()(const sw::mark::IMark* pMark, SwPosition const& rPos)
+ {
+ return pMark->GetMarkStart() > rPos;
+ }
+ };
IMark* lcl_getMarkAfter(const MarkManager::container_t& rMarks, const
SwPosition& rPos,
bool bLoop)
@@ -1475,27 +1482,44 @@ namespace sw::mark
IFieldmark* MarkManager::getInnerFieldmarkFor(const SwPosition& rPos) const
{
- auto itFieldmark = find_if(
- m_vFieldmarks.begin(),
- m_vFieldmarks.end(),
- [&rPos] (const ::sw::mark::MarkBase *const pMark) { return
pMark->IsCoveringPosition(rPos); } );
- if (itFieldmark == m_vFieldmarks.end())
+ // find the first mark starting on or before the position in reverse
order
+ // (as we are reverse searching, this is the one closest to the
position)
+ // m_vFieldmarks should be ordered by mark start, so we can bisect
with lower_bound
+ auto itEnd = m_vFieldmarks.rend();
+ auto itStart = lower_bound(
+ m_vFieldmarks.rbegin(),
+ itEnd,
+ rPos,
+ CompareIMarkStartsAfterReverse());
+ // now continue a linear search for the first (still in reverse order)
ending behind the position
+ auto itCurrent = find_if(
+ itStart,
+ itEnd,
+ [&rPos](const sw::mark::MarkBase* const pMark) { return rPos <
pMark->GetMarkEnd(); });
+ // if we reached the end (in reverse order) there is no match
+ if(itCurrent == itEnd)
return nullptr;
- auto pFieldmark(*itFieldmark);
-
- // See if any fieldmarks after the first hit are closer to rPos.
- ++itFieldmark;
- for ( ; itFieldmark != m_vFieldmarks.end()
- && (**itFieldmark).GetMarkStart() <= rPos; ++itFieldmark)
- { // find the innermost fieldmark
- if (rPos < (**itFieldmark).GetMarkEnd()
- && (pFieldmark->GetMarkStart() < (**itFieldmark).GetMarkStart()
- || (**itFieldmark).GetMarkEnd() <
pFieldmark->GetMarkEnd()))
+ // we found our first candidate covering the position ...
+ auto pMark = *itCurrent;
+ const auto aMarkStart = pMark->GetMarkStart();
+ auto aMarkEnd = pMark->GetMarkEnd();
+ // ... however we still need to check if there is a smaller/'more
inner' one with the same start position
+ for(++itCurrent; itCurrent != itEnd; ++itCurrent)
+ {
+ if((*itCurrent)->GetMarkStart() < aMarkStart)
+ // any following mark (in reverse order) will have an earlier
+ // start and thus can not be more 'inner' than our previous
+ // match, so we are done.
+ break;
+ auto aCurrentMarkEnd = (*itCurrent)->GetMarkEnd();
+ if(rPos < aCurrentMarkEnd && aCurrentMarkEnd <= aMarkEnd)
{
- pFieldmark = *itFieldmark;
+ // both covering the position and more inner/smaller => use
this one instead
+ pMark = *itCurrent;
+ aMarkEnd = aCurrentMarkEnd;
}
}
- return dynamic_cast<IFieldmark*>(pFieldmark);
+ return dynamic_cast<IFieldmark*>(pMark);
}
IMark* MarkManager::getOneInnermostBookmarkFor(const SwPosition& rPos)
const
