Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(92)

Issue 1408403008: [Editing] Speed up PositionIterator::computePosition (Closed)

Created:
5 years, 1 month ago by yoichio
Modified:
5 years, 1 month ago
Reviewers:
CC:
chromium-reviews, blink-reviews, asanka, benjhayden+dwatch_chromium.org
Base URL:
https://chromium.googlesource.com/chromium/src.git@2526
Target Ref:
refs/pending/branch-heads/2526
Project:
chromium
Visibility:
Public.

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 #

Unified diffs Side-by-side diffs Delta from patch set Stats (+175 lines, -4 lines) Patch
M third_party/WebKit/Source/core/editing/PositionIterator.h View 3 chunks +19 lines, -2 lines 0 comments Download
M third_party/WebKit/Source/core/editing/PositionIterator.cpp View 8 chunks +156 lines, -2 lines 0 comments Download

Messages

Total messages: 1 (0 generated)
yoichio
5 years, 1 month ago (2015-10-30 05:55:25 UTC) #1
Message was sent while issue was closed.
Committed patchset #1 (id:1) manually as
acc72218010cbbd53251a10de58d8c7b31f12834 (tree was closed).

Powered by Google App Engine
This is Rietveld 408576698