[CSS Grid Layout] Do log(n) search in the named line vectors when positioning named...
authorcommit-queue@webkit.org <commit-queue@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 31 Jan 2014 08:10:11 +0000 (08:10 +0000)
committercommit-queue@webkit.org <commit-queue@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 31 Jan 2014 08:10:11 +0000 (08:10 +0000)
https://bugs.webkit.org/show_bug.cgi?id=125396

Patch by László Langó <lango@inf.u-szeged.hu> on 2014-01-30
Reviewed by Andreas Kling.

Implement the suggested FIXMEs and do a log search in the named line
vectors. This maintains the previous (somewhat tricky) behavior by
using std::lower_bound and std::upper_bound. No difference in existing
performance tests, but should scale much better for big grids.

Backported from Blink:
https://chromium.googlesource.com/chromium/blink/+/9fc477af0be708c490a6b90e65e412b0c22b161f

No new tests, no behavior change.

* rendering/RenderGrid.cpp:
(WebCore::RenderGrid::resolveRowStartColumnStartNamedGridLinePositionAgainstOppositePosition):
(WebCore::RenderGrid::resolveRowEndColumnEndNamedGridLinePositionAgainstOppositePosition):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@163166 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WebCore/ChangeLog
Source/WebCore/rendering/RenderGrid.cpp

index b8034fb..e91326e 100644 (file)
@@ -1,3 +1,24 @@
+2014-01-30  László Langó  <lango@inf.u-szeged.hu>
+
+        [CSS Grid Layout] Do log(n) search in the named line vectors when positioning named line spans.
+        https://bugs.webkit.org/show_bug.cgi?id=125396
+
+        Reviewed by Andreas Kling.
+
+        Implement the suggested FIXMEs and do a log search in the named line
+        vectors. This maintains the previous (somewhat tricky) behavior by
+        using std::lower_bound and std::upper_bound. No difference in existing
+        performance tests, but should scale much better for big grids.
+
+        Backported from Blink:
+        https://chromium.googlesource.com/chromium/blink/+/9fc477af0be708c490a6b90e65e412b0c22b161f
+
+        No new tests, no behavior change.
+
+        * rendering/RenderGrid.cpp:
+        (WebCore::RenderGrid::resolveRowStartColumnStartNamedGridLinePositionAgainstOppositePosition):
+        (WebCore::RenderGrid::resolveRowEndColumnEndNamedGridLinePositionAgainstOppositePosition):
+
 2014-01-31  László Langó  <lango@inf.u-szeged.hu>
 
         Fix table sizing when 'max-width' is used.
index 8f2ff42..07791cd 100644 (file)
@@ -979,9 +979,10 @@ PassOwnPtr<GridSpan> RenderGrid::resolveRowStartColumnStartNamedGridLinePosition
 {
     // The grid line inequality needs to be strict (which doesn't match the after / end case) because |resolvedOppositePosition|
     // is already converted to an index in our grid representation (ie one was removed from the grid line to account for the side).
-    // FIXME: This could be a binary search as |gridLines| is ordered.
-    int firstLineBeforeOppositePositionIndex = gridLines.size() - 1;
-    for (; firstLineBeforeOppositePositionIndex >= 0 && gridLines[firstLineBeforeOppositePositionIndex] > resolvedOppositePosition; --firstLineBeforeOppositePositionIndex) { }
+    size_t firstLineBeforeOppositePositionIndex = 0;
+    const size_t* firstLineBeforeOppositePosition = std::lower_bound(gridLines.begin(), gridLines.end(), resolvedOppositePosition);
+    if (firstLineBeforeOppositePosition != gridLines.end())
+        firstLineBeforeOppositePositionIndex = firstLineBeforeOppositePosition - gridLines.begin();
 
     size_t gridLineIndex = std::max<int>(0, firstLineBeforeOppositePositionIndex - position.spanPosition() + 1);
     size_t resolvedGridLinePosition = gridLines[gridLineIndex];
@@ -992,9 +993,10 @@ PassOwnPtr<GridSpan> RenderGrid::resolveRowStartColumnStartNamedGridLinePosition
 
 PassOwnPtr<GridSpan> RenderGrid::resolveRowEndColumnEndNamedGridLinePositionAgainstOppositePosition(size_t resolvedOppositePosition, const GridPosition& position, const Vector<size_t>& gridLines) const
 {
-    // FIXME: This could be a binary search as |gridLines| is ordered.
-    size_t firstLineAfterOppositePositionIndex = 0;
-    for (; firstLineAfterOppositePositionIndex < gridLines.size() && gridLines[firstLineAfterOppositePositionIndex] <= resolvedOppositePosition; ++firstLineAfterOppositePositionIndex) { }
+    size_t firstLineAfterOppositePositionIndex = gridLines.size() - 1;
+    const size_t* firstLineAfterOppositePosition = std::upper_bound(gridLines.begin(), gridLines.end(), resolvedOppositePosition);
+    if (firstLineAfterOppositePosition != gridLines.end())
+        firstLineAfterOppositePositionIndex = firstLineAfterOppositePosition - gridLines.begin();
 
     size_t gridLineIndex = std::min(gridLines.size() - 1, firstLineAfterOppositePositionIndex + position.spanPosition() - 1);
     size_t resolvedGridLinePosition = adjustGridPositionForRowEndColumnEndSide(gridLines[gridLineIndex]);