The table layout use the cellmap for two purposes:
The cellmap code is contained in nsCellMap.cpp and nsCellMap.h
This document does currently describe only the quick lookup part of the game, border collapse is still far away
The entries in the cellmap contain information about the table cell frame corresponding to a given row and column number (celldata.h). Further it contains info whether this entry is a row- or colspan.
79 // this union relies on the assumption that an object (not primitive type) does
80 // not start on an odd bit boundary. If mSpan is 0 then mOrigCell is in effect
81 // and the data does not represent a span. If mSpan is 1, then mBits is in
82 // effect and the data represents a span.
83 union {
84 nsTableCellFrame* mOrigCell;
85 long mBits;
86 };
The idea behind this construction is a entry in the cellmap can be either the origin of a row- or colspan (a cell cell without a defined row- or colspan attribute assumes 1 as a default value), or a entry which is only covered by a row- or colspan. Entries which are a origin have a direct corresponding TableCellFrame. Entries which are only spanned don't have that direct relationship. They belong to a entry which has a direct relationship to a TableCellFrame. Now that union uses the fact all addresses of real TableCellFrames are aligned at even boundaries, or in other words they cant have an odd address. If the address is odd then it holds some other info (mBits).
Just imagine a 2x2 table.
<table> <tr><td>cell 1</td><td>cell 2</td></tr> <tr><td>cell 3</td><td>cell 4</td></tr> </table>
This would create a cellmap with two rows and in each row 2 entries. Each entry in the cellmap wold have a direct link to the corresponding TableCellFrames.
Take the same table and adder a header
<table> <thead> <tr><td>head cell 1</td><td>head cell 2</td></tr> </thead> <tbody> <tr><td>cell 1</td><td>cell 2</td></tr> <tr><td>cell 3</td><td>cell 4</td></tr> </tbody> </table>
Now we have two different rowgroups and and the rowspans can not cross the borders between the different rowgroups. (ref XHTML-2.0). Further the table header and footer will be repeated on every page when printed out. Due to this behind the cellmap for the table we will find a cellmap for every rowgroup. In this low level cellmap the row count begins every time with 0.
A typical code segment to come from the table level down to the rowgroup level
nsCellMap* map = mFirstMap;
while (map) {
if (map->GetRowCount() > rowIndex) {
// Add your action here
}
rowIndex -= map->GetRowCount();
map = map->GetNextSibling();
}
The usual way to populate the cellmap is via nsTableFrame::InsertRows. Enabling the debug code at the function entrance and exit gives a quite complete picture of the cellmap structure. Below follows the dump for the 2x2 table.
insertRowsBefore firstRow=0 ***START TABLE DUMP*** mColWidths= row(0)=02763344 cell(0)=02763528 cell(0)=0276381C row(0)=02763940 cell(0)=02763990 cell(0)=02763AB4 ***** START TABLE CELL MAP DUMP ***** 023566B0 cols array orig/span-> 023566B0 ***** START GROUP CELL MAP DUMP ***** 023565B0 mapRowCount=0 tableRowCount=0 ***** END GROUP CELL MAP DUMP ***** ***** END TABLE CELL MAP DUMP ***** ***END TABLE DUMP*** insertRowsAfter ***START TABLE DUMP*** mColWidths=-1 -1 row(0)=02763344 cell(0)=02763528 cell(1)=0276381C row(1)=02763940 cell(0)=02763990 cell(1)=02763AB4 ***** START TABLE CELL MAP DUMP ***** 023566B0 cols array orig/span-> 023566B00=2/0 1=2/0 ***** START GROUP CELL MAP DUMP ***** 023565B0 mapRowCount=2 tableRowCount=2 row 0 : C0,0 C0,1 row 1 : C1,0 C1,1 C0,0=02763528(0) C0,1=0276381C(1) C1,0=02763990(0) C1,1=02763AB4(1) ***** END GROUP CELL MAP DUMP ***** ***** END TABLE CELL MAP DUMP ***** ***END TABLE DUMP***
One can imagine the cellmap as grid with equally wide rows and columns where the table cells are drawn. These cells can cover more than a grid cell if the row- or colspan attribute is different from 1.
Lets add a cell to the second row in the 2x2 table and let the second cell in the first row span over two cells.
<table> <tr><td>cell 1</td><td colspan="2">cell 2</td></tr> <tr><td>cell 3</td><td>cell 4</td><td>cell 5</td></tr> </table>
Table cell map would be:
row 0 : C0,0 C0,1 C row 1 : C1,0 C1,1 C1,2
While it is clear that in the cells that are the origin of a table cells one will find a address the more interesting question is, what will be the content in the upper right cell. The bitfield will hold a 0x00090001.
#define SPAN 0x00000001 // there a row or col span #define ROW_SPAN 0x00000002 // there is a row span #define ROW_SPAN_0 0x00000004 // the row span is 0 #define ROW_SPAN_OFFSET 0x0000FFF8 // the row offset to the data containing the original cell #define COL_SPAN 0x00010000 // there is a col span #define COL_SPAN_0 0x00020000 // the col span is 0 #define OVERLAP 0x00040000 // there is a row span and col span but no by same cell #define COL_SPAN_OFFSET 0xFFF80000 // the col offset to the data containing the original cell #define ROW_SPAN_SHIFT 3 // num bits to shift to get right justified row span #define COL_SPAN_SHIFT 19 // num bits to shift to get right justified col span
Showing that there is a span, this span is a colspan and the colspan origin is one cell away. This shows that the maximum handled row- or colspan value for a cell is 0xFFF8 >> 3 = 8191.
There is a special attribute for rowspan="0" and colspan="0", because html 4.0 did introduce a special handling of the 0 value.
The handling of zero spans introduces overhead as one can not mark in advance the corresponding cells as spanned by the zero spans. The current solution is to use nsCellmap::GetDataAt with a special argument aUpdateZeroSpan to repair the cellmap if it encounters a empty cell (nsnull), by looking for a origin of a zero row- or colspan that spans the queried place in the cellmap. This can produce enormous costs once the cellmap contains large holes that are not caused by zero spans, this is at least a O2(n) algorithm.
The following routines seem to be hot spots performance wise:
nsCellMap.cpp