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

Issue 2410773006: Refactor NGLayoutOpportunityIterator to use 3-nodes spatial tree (Closed)

Created:
4 years, 2 months ago by Gleb Lanbin
Modified:
4 years, 2 months ago
Reviewers:
ikilpatrick, eae
CC:
chromium-reviews, cbiesinger, ojan+watch_chromium.org, szager+layoutwatch_chromium.org, glebl+reviews_chromium.org, zoltan1, blink-reviews-layout_chromium.org, pdr+renderingwatchlist_chromium.org, eae+blinkwatch, leviw+renderwatch, jchaffraix+rendering, blink-reviews
Target Ref:
refs/pending/heads/master
Project:
chromium
Visibility:
Public.

Description

Refactor NGLayoutOpportunityIterator to use 3-nodes spatial tree This patch introduces a new layout opportunity iterator algorithm which is based on 3-nodes spatial tree. The new approach has several benefits from the existing one: - improved runtime complexity to find layout opportunities: O(N log N) - ability to reuse the tree, e.g. just insert a new exclusion down into the tree. Insert operation shouldn't take longer than 2 x log N time. BUG=635619 Committed: https://crrev.com/e871b54f5e65f69b58ab4344f490f8d04faa06ab Cr-Commit-Position: refs/heads/master@{#425391}

Patch Set 1 #

Total comments: 6

Patch Set 2 : Update LayoutOpportunitiesTwoInMiddle tests expectations #

Total comments: 3

Patch Set 3 : add LayoutOpportunitiesWithOutOfBoundsExclusions test case #

Total comments: 7

Patch Set 4 : fix minor comments #

Messages

Total messages: 33 (21 generated)
Gleb Lanbin
Ian, this patch is for preview only. I want to clarify some details with you ...
4 years, 2 months ago (2016-10-12 17:04:37 UTC) #2
Gleb Lanbin
Ian, Emil, could you review the updated test expectations for the case with exclusions in ...
4 years, 2 months ago (2016-10-12 19:25:15 UTC) #5
eae
This is great! https://codereview.chromium.org/2410773006/diff/40001/third_party/WebKit/Source/core/layout/ng/ng_constraint_space_test.cc File third_party/WebKit/Source/core/layout/ng/ng_constraint_space_test.cc (right): https://codereview.chromium.org/2410773006/diff/40001/third_party/WebKit/Source/core/layout/ng/ng_constraint_space_test.cc#newcode151 third_party/WebKit/Source/core/layout/ng/ng_constraint_space_test.cc:151: EXPECT_EQ("250,0 350x350", OpportunityToString(iterator->Next())); This makes sense ...
4 years, 2 months ago (2016-10-12 21:07:39 UTC) #7
Gleb Lanbin
PTAL https://codereview.chromium.org/2410773006/diff/40001/third_party/WebKit/Source/core/layout/ng/ng_constraint_space_test.cc File third_party/WebKit/Source/core/layout/ng/ng_constraint_space_test.cc (right): https://codereview.chromium.org/2410773006/diff/40001/third_party/WebKit/Source/core/layout/ng/ng_constraint_space_test.cc#newcode151 third_party/WebKit/Source/core/layout/ng/ng_constraint_space_test.cc:151: EXPECT_EQ("250,0 350x350", OpportunityToString(iterator->Next())); On 2016/10/12 21:07:39, eae wrote: ...
4 years, 2 months ago (2016-10-12 23:08:30 UTC) #9
eae
LGTM w/suggestions Please allow Ian to take another look before landing. https://codereview.chromium.org/2410773006/diff/60001/third_party/WebKit/Source/core/layout/ng/ng_constraint_space_test.cc File third_party/WebKit/Source/core/layout/ng/ng_constraint_space_test.cc (right): ...
4 years, 2 months ago (2016-10-12 23:12:38 UTC) #10
Gleb Lanbin
thanks for the review https://codereview.chromium.org/2410773006/diff/60001/third_party/WebKit/Source/core/layout/ng/ng_layout_opportunity_iterator.cc File third_party/WebKit/Source/core/layout/ng/ng_layout_opportunity_iterator.cc (right): https://codereview.chromium.org/2410773006/diff/60001/third_party/WebKit/Source/core/layout/ng/ng_layout_opportunity_iterator.cc#newcode32 third_party/WebKit/Source/core/layout/ng/ng_layout_opportunity_iterator.cc:32: bool IsExclusionWithinSpace(const NGConstraintSpace& space, On ...
4 years, 2 months ago (2016-10-13 00:11:10 UTC) #11
eae
https://codereview.chromium.org/2410773006/diff/80001/third_party/WebKit/Source/core/layout/ng/ng_constraint_space_test.cc File third_party/WebKit/Source/core/layout/ng/ng_constraint_space_test.cc (right): https://codereview.chromium.org/2410773006/diff/80001/third_party/WebKit/Source/core/layout/ng/ng_constraint_space_test.cc#newcode190 third_party/WebKit/Source/core/layout/ng/ng_constraint_space_test.cc:190: TEST(NGConstraintSpaceTest, LayoutOpportunitiesWithOutOfBoundsExclusions) { This is great, thank you!
4 years, 2 months ago (2016-10-13 01:34:43 UTC) #18
ikilpatrick
lgtm https://codereview.chromium.org/2410773006/diff/80001/third_party/WebKit/Source/core/layout/ng/ng_constraint_space.cc File third_party/WebKit/Source/core/layout/ng/ng_constraint_space.cc (right): https://codereview.chromium.org/2410773006/diff/80001/third_party/WebKit/Source/core/layout/ng/ng_constraint_space.cc#newcode63 third_party/WebKit/Source/core/layout/ng/ng_constraint_space.cc:63: for (auto exclusion : other.PhysicalSpace()->Exclusions()) { const auto& ...
4 years, 2 months ago (2016-10-14 16:06:20 UTC) #21
Gleb Lanbin
thanks for the review https://codereview.chromium.org/2410773006/diff/80001/third_party/WebKit/Source/core/layout/ng/ng_constraint_space.cc File third_party/WebKit/Source/core/layout/ng/ng_constraint_space.cc (right): https://codereview.chromium.org/2410773006/diff/80001/third_party/WebKit/Source/core/layout/ng/ng_constraint_space.cc#newcode63 third_party/WebKit/Source/core/layout/ng/ng_constraint_space.cc:63: for (auto exclusion : other.PhysicalSpace()->Exclusions()) ...
4 years, 2 months ago (2016-10-14 16:25:03 UTC) #22
commit-bot: I haz the power
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.org/2410773006/100001
4 years, 2 months ago (2016-10-14 18:16:30 UTC) #29
commit-bot: I haz the power
Committed patchset #4 (id:100001)
4 years, 2 months ago (2016-10-14 18:24:40 UTC) #31
commit-bot: I haz the power
4 years, 2 months ago (2016-10-14 18:28:20 UTC) #33
Message was sent while issue was closed.
Patchset 4 (id:??) landed as
https://crrev.com/e871b54f5e65f69b58ab4344f490f8d04faa06ab
Cr-Commit-Position: refs/heads/master@{#425391}

Powered by Google App Engine
This is Rietveld 408576698