Description[Editing] Speed up PositionIterator::computePosition
PositionIterator::computePosition is slow if position is before a node.
That is because |PositionTemplate<Strategy>::inParentBeforeNode(node)|
calculates index of |node| by counting siblings, which takes O(n) time.
To avoid that, this CL let PositionIterator to remember and count index within
increment() because the function usually moves position to next sibling.
Then, computePosition uses the index instead of inParentBeforeNode so it takes
O(1) time.
-- Implementation detail --
|Vector<int> m_offsetsInAnchorNode| stores indexes within each anchor node in
a path from root to position.
|m_depthToAnchorNode| is a current depth of anchor node.
To delay initialize each index(because we may not use all index value instantly),
we initialize |m_offsetsInAnchorNode| -1 and initialize if it needs in increment().
Since this implementation supposes DOM tree doesn't change in traversal, I
introduce |m_domTreeVersion| to check tree is not changed. This assumption works
because PositionIterator is used on stack and DOM mutaion must not happen in
traversal.
BUG=514193, 543779, 545170
Review URL: https://codereview.chromium.org/1372153007
Cr-Commit-Position: refs/heads/master@{#355517}
(cherry picked from commit b6d97fc86439a6a4d164ad8caf588d67d5f635e2)
Committed: https://chromium.googlesource.com/chromium/src/+/acc72218010cbbd53251a10de58d8c7b31f12834
Patch Set 1 #
Messages
Total messages: 1 (0 generated)
|