Changeset 65539 in webkit


Ignore:
Timestamp:
Aug 17, 2010 1:57:15 PM (14 years ago)
Author:
jamesr@google.com
Message:

2010-08-17 Fady Samuel <​fsamuel@chromium.org>

Reviewed by David Hyatt.

Updated table cell hit testing and painting to use binary search instead of linear scan.

Improved Table Hit Testing and Painting Performance
​https://bugs.webkit.org/show_bug.cgi?id=43933

Tests: fast/table/simple_paint.html

tables/hittesting/filltable-emptycells.html
tables/hittesting/filltable-levels.html
tables/hittesting/filltable-outline.html
tables/hittesting/filltable-rtl.html
tables/hittesting/filltable-stress.html

  • rendering/RenderTableSection.cpp: (WebCore::RenderTableSection::paintObject): Dirty rect determined using binary search. (WebCore::RenderTableSection::nodeAtPoint): Cell hit determined using binary search

2010-08-17 Fady Samuel <​fsamuel@chromium.org>

Reviewed by David Hyatt.

Updated table cell hit testing and painting to use binary search instead of a linear scan.

Layout tests check that hit testing of empty cells, overlapping cells,
cells with outlines, right-to-left tables, and large
tables all work as expected.

Improved Table Hit Testing and Painting Performance
​https://bugs.webkit.org/show_bug.cgi?id=43933

  • fast/table/simple_paint.html: Added.
  • platform/chromium-linux/fast/table/simple_paint-expected.checksum: Added.
  • platform/chromium-linux/fast/table/simple_paint-expected.png: Added.
  • platform/chromium-linux/fast/table/simple_paint-expected.txt: Added.
  • platform/chromium-linux/tables/hittesting/filltable-emptycells-expected.txt: Added.
  • platform/chromium-linux/tables/hittesting/filltable-levels-expected.txt: Added.
  • platform/chromium-linux/tables/hittesting/filltable-outline-expected.txt: Added.
  • platform/chromium-linux/tables/hittesting/filltable-rtl-expected.txt: Added.
  • platform/chromium-linux/tables/hittesting/filltable-stress-expected.txt: Added.
  • platform/chromium/test_expectations.txt:
  • platform/gtk/tables/hittesting/filltable-emptycells-expected.txt: Added.
  • platform/gtk/tables/hittesting/filltable-levels-expected.txt: Added.
  • platform/gtk/tables/hittesting/filltable-outline-expected.txt: Added.
  • platform/gtk/tables/hittesting/filltable-rtl-expected.txt: Added.
  • platform/gtk/tables/hittesting/filltable-stress-expected.txt: Added.
  • tables/hittesting/filltable-emptycells.html: Added.
  • tables/hittesting/filltable-levels.html: Added.
  • tables/hittesting/filltable-outline.html: Added.
  • tables/hittesting/filltable-rtl.html: Added.
  • tables/hittesting/filltable-stress.html: Added.
Location:
trunk
Files:
25 added
4 edited

Legend:

Unmodified
Added
Removed

  • trunk/LayoutTests/ChangeLog

    r65538 r65539  
     12010-08-17  Fady Samuel  <fsamuel@chromium.org>
     2
     3        Reviewed by David Hyatt.
     4
     5        Updated table cell hit testing and painting to use binary search instead of a linear scan.
     6
     7        Layout tests check that hit testing of empty cells, overlapping cells,
     8        cells with outlines, right-to-left tables, and large
     9        tables all work as expected.
     10
     11        Improved Table Hit Testing and Painting Performance
     12        https://bugs.webkit.org/show_bug.cgi?id=43933
     13
     14        * fast/table/simple_paint.html: Added.
     15        * platform/chromium-linux/fast/table/simple_paint-expected.checksum: Added.
     16        * platform/chromium-linux/fast/table/simple_paint-expected.png: Added.
     17        * platform/chromium-linux/fast/table/simple_paint-expected.txt: Added.
     18        * platform/chromium-linux/tables/hittesting/filltable-emptycells-expected.txt: Added.
     19        * platform/chromium-linux/tables/hittesting/filltable-levels-expected.txt: Added.
     20        * platform/chromium-linux/tables/hittesting/filltable-outline-expected.txt: Added.
     21        * platform/chromium-linux/tables/hittesting/filltable-rtl-expected.txt: Added.
     22        * platform/chromium-linux/tables/hittesting/filltable-stress-expected.txt: Added.
     23        * platform/chromium/test_expectations.txt:
     24        * platform/gtk/tables/hittesting/filltable-emptycells-expected.txt: Added.
     25        * platform/gtk/tables/hittesting/filltable-levels-expected.txt: Added.
     26        * platform/gtk/tables/hittesting/filltable-outline-expected.txt: Added.
     27        * platform/gtk/tables/hittesting/filltable-rtl-expected.txt: Added.
     28        * platform/gtk/tables/hittesting/filltable-stress-expected.txt: Added.
     29        * tables/hittesting/filltable-emptycells.html: Added.
     30        * tables/hittesting/filltable-levels.html: Added.
     31        * tables/hittesting/filltable-outline.html: Added.
     32        * tables/hittesting/filltable-rtl.html: Added.
     33        * tables/hittesting/filltable-stress.html: Added.
     34
    1352010-08-17  Abhishek Arya  <inferno@chromium.org>
    236

  • trunk/LayoutTests/platform/chromium/test_expectations.txt

    r65535 r65539  
    31643164BUG51854 WIN SLOW : http/tests/storage/callbacks-are-called-in-correct-context.html = PASS
    31653165
     3166// Temporarily there until we baseline for Windows and Mac
     3167BUG43933 WIN MAC : tables/hittesting/filltable-stress.html = FAIL
     3168BUG43933 WIN MAC : tables/hittesting/filltable-rtl.html = FAIL
     3169BUG43933 WIN MAC : tables/hittesting/filltable-outline.html = FAIL
     3170BUG43933 WIN MAC : tables/hittesting/filltable-levels.html = FAIL
     3171BUG43933 WIN MAC : tables/hittesting/filltable-emptycells.html = FAIL
     3172BUG43933 WIN MAC : fast/table/simple_paint.html = FAIL
     3173
    31663174// Regressions from r65229
    31673175BUGWK43912 WIN LINUX : svg/W3C-SVG-1.1/masking-intro-01-f.svg = IMAGE
    … …  
    31833191BUGWK43912 WIN LINUX : svg/zoom/page/zoom-mask-with-percentages.svg = IMAGE
    31843192BUGWK43912 WIN LINUX : svg/custom/absolute-sized-content-with-resources.xhtml = IMAGE
     3193
    31853194// Same symptoms, failing as of r65449
    31863195BUGWK43912 : svg/W3C-SVG-1.1/filters-color-01-b.svg = IMAGE

  • trunk/WebCore/ChangeLog

    r65538 r65539  
     12010-08-17  Fady Samuel  <fsamuel@chromium.org>
     2
     3        Reviewed by David Hyatt.
     4
     5        Updated table cell hit testing and painting to use binary search instead of linear scan.
     6
     7        Improved Table Hit Testing and Painting Performance
     8        https://bugs.webkit.org/show_bug.cgi?id=43933
     9
     10        Tests: fast/table/simple_paint.html
     11               tables/hittesting/filltable-emptycells.html
     12               tables/hittesting/filltable-levels.html
     13               tables/hittesting/filltable-outline.html
     14               tables/hittesting/filltable-rtl.html
     15               tables/hittesting/filltable-stress.html
     16
     17        * rendering/RenderTableSection.cpp:
     18        (WebCore::RenderTableSection::paintObject): Dirty rect determined using binary search.
     19        (WebCore::RenderTableSection::nodeAtPoint): Cell hit determined using binary search
     20
    1212010-08-17  Abhishek Arya  <inferno@chromium.org>
    222

  • trunk/WebCore/rendering/RenderTableSection.cpp

    r64272 r65539  
    2626#include "config.h"
    2727#include "RenderTableSection.h"
    28 
    2928#include "CachedImage.h"
    3029#include "Document.h"
    … …  
    10131012    // If some cell overflows, just paint all of them.
    10141013    if (!m_hasOverflowingCell) {
    1015         for (; startrow < totalRows; startrow++) {
    1016             if (ty + m_rowPos[startrow + 1] >= y - os)
    1017                 break;
    1018         }
    1019         if (startrow == totalRows && ty + m_rowPos[totalRows] + table()->outerBorderBottom() >= y - os)
    1020             startrow--;
    1021 
    1022         for (; endrow > 0; endrow--) {
    1023             if (ty + m_rowPos[endrow - 1] <= y + h + os)
    1024                 break;
    1025         }
     1014        int relativeY = y - ty;
     1015        int top = relativeY - os;
     1016        // binary search to find a row
     1017        startrow = std::lower_bound(m_rowPos.begin(), m_rowPos.end(), top) - m_rowPos.begin();
     1018
     1019        // The binary search above gives us the first row with
     1020        // a y position >= the top of the paint rect. Thus, the previous
     1021        // may need to be repainted as well.
     1022        if (startrow == m_rowPos.size() || (startrow > 0 && (m_rowPos[startrow] >  top)))
     1023          --startrow;
     1024
     1025        int bottom = relativeY + h + os - 1;
     1026        endrow = std::lower_bound(m_rowPos.begin(), m_rowPos.end(), bottom) - m_rowPos.begin();
     1027        if ((endrow == m_rowPos.size()) || (endrow > 0 && m_rowPos[endrow - 1] == bottom))
     1028          --endrow;
     1029
    10261030        if (!endrow && ty + m_rowPos[0] - table()->outerBorderTop() <= y + h + os)
    1027             endrow++;
    1028     }
    1029 
     1031            ++endrow;
     1032    }
    10301033    unsigned startcol = 0;
    10311034    unsigned endcol = totalCols;
    10321035    // FIXME: Implement RTL.
    10331036    if (!m_hasOverflowingCell && style()->direction() == LTR) {
    1034         for (; startcol < totalCols; startcol++) {
    1035             if (tx + table()->columnPositions()[startcol + 1] >= x - os)
    1036                 break;
    1037         }
    1038         if (startcol == totalCols && tx + table()->columnPositions()[totalCols] + table()->outerBorderRight() >= x - os)
    1039             startcol--;
    1040 
    1041         for (; endcol > 0; endcol--) {
    1042             if (tx + table()->columnPositions()[endcol - 1] <= x + w + os)
    1043                 break;
    1044         }
     1037        int relativeX = x - tx;
     1038        int left = relativeX - os;
     1039        Vector<int>& columnPos = table()->columnPositions();
     1040        startcol = std::lower_bound(columnPos.begin(), columnPos.end(), left) - columnPos.begin();
     1041        if ((startcol == columnPos.size()) || (startcol > 0 && (columnPos[startcol] > left)))
     1042            --startcol;
     1043
     1044        int right = relativeX + w + os - 1;
     1045        endcol = std::lower_bound(columnPos.begin(), columnPos.end(), right) - columnPos.begin();
     1046        if (endcol == columnPos.size() || (endcol > 0 && (columnPos[endcol - 1] == right)))
     1047            --endcol;
     1048
    10451049        if (!endcol && tx + table()->columnPositions()[0] - table()->outerBorderLeft() <= y + w + os)
    1046             endcol++;
     1050            ++endcol;
    10471051    }
    10481052    if (startcol < endcol) {
    … …  
    11741178bool RenderTableSection::nodeAtPoint(const HitTestRequest& request, HitTestResult& result, int xPos, int yPos, int tx, int ty, HitTestAction action)
    11751179{
     1180    // If we have no children then we have nothing to do.
     1181    if (!firstChild())
     1182        return false;
     1183
    11761184    // Table sections cannot ever be hit tested.  Effectively they do not exist.
    11771185    // Just forward to our children always.
    … …  
    11821190        return false;
    11831191
    1184     for (RenderObject* child = lastChild(); child; child = child->previousSibling()) {
    1185         // FIXME: We have to skip over inline flows, since they can show up inside table rows
    1186         // at the moment (a demoted inline <form> for example). If we ever implement a
    1187         // table-specific hit-test method (which we should do for performance reasons anyway),
    1188         // then we can remove this check.
    1189         if (child->isBox() && !toRenderBox(child)->hasSelfPaintingLayer() && child->nodeAtPoint(request, result, xPos, yPos, tx, ty, action)) {
     1192    if (m_hasOverflowingCell) {
     1193        for (RenderObject* child = lastChild(); child; child = child->previousSibling()) {
     1194            // FIXME: We have to skip over inline flows, since they can show up inside table rows
     1195            // at the moment (a demoted inline <form> for example). If we ever implement a
     1196            // table-specific hit-test method (which we should do for performance reasons anyway),
     1197            // then we can remove this check.
     1198            if (child->isBox() && !toRenderBox(child)->hasSelfPaintingLayer() && child->nodeAtPoint(request, result, xPos, yPos, tx, ty, action)) {
     1199                updateHitTestResult(result, IntPoint(xPos - tx, yPos - ty));
     1200                return true;
     1201            }
     1202        }
     1203        return false;
     1204    }
     1205
     1206    int relativeY = yPos - ty;
     1207    // leftrow corresponds to the first row that starts after the y mouse position
     1208    unsigned leftrow = std::upper_bound(m_rowPos.begin(), m_rowPos.end(), relativeY) - m_rowPos.begin();
     1209    if (leftrow == m_rowPos.size())
     1210        return false;
     1211    // Grab the last row that starts before the y mouse position.
     1212    if (leftrow > 0)
     1213        --leftrow;
     1214
     1215    Vector<int>& columnPos = table()->columnPositions();
     1216    bool rtl = style()->direction() == RTL;
     1217    int relativeX = xPos - tx;
     1218    if (rtl)
     1219        relativeX = columnPos[columnPos.size() - 1] - relativeX;
     1220
     1221    unsigned leftcol = std::lower_bound(columnPos.begin(), columnPos.end(), relativeX) - columnPos.begin();
     1222    if (leftcol == columnPos.size())
     1223        return false;
     1224    if (leftcol > 0)
     1225        --leftcol;
     1226
     1227    CellStruct& current = cellAt(leftrow, leftcol);
     1228
     1229    // If the cell is empty, there's nothing to do
     1230    if (!current.hasCells())
     1231        return false;
     1232
     1233    for (int i = current.cells.size() - 1; i >= 0; --i) {
     1234        RenderTableCell* cell = current.cells[i];
     1235        if (static_cast<RenderObject*>(cell)->nodeAtPoint(request, result, xPos, yPos, tx, ty, action)) {
    11901236            updateHitTestResult(result, IntPoint(xPos - tx, yPos - ty));
    11911237            return true;
    … …  
    11931239    }
    11941240    return false;
     1241
    11951242}
    11961243
Note: See TracChangeset for help on using the changeset viewer.