1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2009, 2010, 2011, 2013, 2014, 2016 Free Software Foundation, Inc.
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>. */
25 #include "libpspp/assertion.h"
26 #include "libpspp/hash-functions.h"
27 #include "libpspp/hmap.h"
28 #include "output/render.h"
29 #include "output/tab.h"
30 #include "output/table-item.h"
31 #include "output/table.h"
33 #include "gl/minmax.h"
34 #include "gl/xalloc.h"
37 #define _(msgid) gettext (msgid)
39 /* This file uses TABLE_HORZ and TABLE_VERT enough to warrant abbreviating. */
43 /* A layout for rendering a specific table on a specific device.
45 May represent the layout of an entire table presented to
46 render_page_create(), or a rectangular subregion of a table broken out using
47 render_break_next() to allow a table to be broken across multiple pages.
49 A page's size is not limited to the size passed in as part of render_params.
50 render_pager breaks a render_page into smaller render_pages that will fit in
51 the available space. */
54 const struct render_params *params; /* Parameters of the target device. */
55 struct table *table; /* Table rendered. */
58 /* Local copies of table->n and table->h, for convenience. */
60 int h[TABLE_N_AXES][2];
62 /* cp[H] represents x positions within the table.
64 cp[H][1] = the width of the leftmost vertical rule.
65 cp[H][2] = cp[H][1] + the width of the leftmost column.
66 cp[H][3] = cp[H][2] + the width of the second-from-left vertical rule.
68 cp[H][2 * nc] = x position of the rightmost vertical rule.
69 cp[H][2 * nc + 1] = total table width including all rules.
71 Similarly, cp[V] represents y positions within the table.
73 cp[V][1] = the height of the topmost horizontal rule.
74 cp[V][2] = cp[V][1] + the height of the topmost row.
75 cp[V][3] = cp[V][2] + the height of the second-from-top horizontal rule.
77 cp[V][2 * nr] = y position of the bottommost horizontal rule.
78 cp[V][2 * nr + 1] = total table height including all rules.
80 Rules and columns can have width or height 0, in which case consecutive
81 values in this array are equal. */
82 int *cp[TABLE_N_AXES];
84 /* render_break_next() can break a table such that some cells are not fully
85 contained within a render_page. This will happen if a cell is too wide
86 or two tall to fit on a single page, or if a cell spans multiple rows or
87 columns and the page only includes some of those rows or columns.
89 This hash table contains "struct render_overflow"s that represents each
90 such cell that doesn't completely fit on this page.
92 Each overflow cell borders at least one header edge of the table and may
93 border more. (A single table cell that is so large that it fills the
94 entire page can overflow on all four sides!) */
95 struct hmap overflows;
97 /* Contains "struct render_footnote"s, one for each cell with one or more
100 'n_footnotes' is the number of footnotes in the table. There might be
101 more than hmap_count(&page->footnotes) because there can be more than
102 one footnote in a cell. */
103 struct hmap footnotes;
106 /* If a single column (or row) is too wide (or tall) to fit on a page
107 reasonably, then render_break_next() will split a single row or column
108 across multiple render_pages. This member indicates when this has
111 is_edge_cutoff[H][0] is true if pixels have been cut off the left side
112 of the leftmost column in this page, and false otherwise.
114 is_edge_cutoff[H][1] is true if pixels have been cut off the right side
115 of the rightmost column in this page, and false otherwise.
117 is_edge_cutoff[V][0] and is_edge_cutoff[V][1] are similar for the top
118 and bottom of the table.
120 The effect of is_edge_cutoff is to prevent rules along the edge in
121 question from being rendered.
123 When is_edge_cutoff is true for a given edge, the 'overflows' hmap will
124 contain a node for each cell along that edge. */
125 bool is_edge_cutoff[TABLE_N_AXES][2];
127 /* If part of a joined cell would be cut off by breaking a table along
128 'axis' at the rule with offset 'z' (where 0 <= z <= n[axis]), then
129 join_crossing[axis][z] is the thickness of the rule that would be cut
132 This is used to know to allocate extra space for breaking at such a
133 position, so that part of the cell's content is not lost.
135 This affects breaking a table only when headers are present. When
136 headers are not present, the rule's thickness is used for cell content,
137 so no part of the cell's content is lost (and in fact it is duplicated
138 across both pages). */
139 int *join_crossing[TABLE_N_AXES];
142 static struct render_page *render_page_create (const struct render_params *,
145 struct render_page *render_page_ref (const struct render_page *page_);
146 static void render_page_unref (struct render_page *);
148 /* Returns the offset in struct render_page's cp[axis] array of the rule with
149 index RULE_IDX. That is, if RULE_IDX is 0, then the offset is that of the
150 leftmost or topmost rule; if RULE_IDX is 1, then the offset is that of the
151 next rule to the right (or below); and so on. */
153 rule_ofs (int rule_idx)
158 /* Returns the offset in struct render_page's cp[axis] array of the rule with
159 index RULE_IDX_R, which counts from the right side (or bottom) of the page
160 left (or up), according to whether AXIS is H or V, respectively. That is,
161 if RULE_IDX_R is 0, then the offset is that of the rightmost or bottommost
162 rule; if RULE_IDX is 1, then the offset is that of the next rule to the left
163 (or above); and so on. */
165 rule_ofs_r (const struct render_page *page, int axis, int rule_idx_r)
167 return (page->n[axis] - rule_idx_r) * 2;
170 /* Returns the offset in struct render_page's cp[axis] array of the cell with
171 index CELL_IDX. That is, if CELL_IDX is 0, then the offset is that of the
172 leftmost or topmost cell; if CELL_IDX is 1, then the offset is that of the
173 next cell to the right (or below); and so on. */
175 cell_ofs (int cell_idx)
177 return cell_idx * 2 + 1;
180 /* Returns the width of PAGE along AXIS from OFS0 to OFS1, exclusive. */
182 axis_width (const struct render_page *page, int axis, int ofs0, int ofs1)
184 return page->cp[axis][ofs1] - page->cp[axis][ofs0];
187 /* Returns the width of the headers in PAGE along AXIS. */
189 headers_width (const struct render_page *page, int axis)
191 int h0 = page->h[axis][0];
192 int w0 = axis_width (page, axis, rule_ofs (0), cell_ofs (h0));
193 int n = page->n[axis];
194 int h1 = page->h[axis][1];
195 int w1 = axis_width (page, axis, rule_ofs_r (page, axis, h1), cell_ofs (n));
199 /* Returns the width of cell X along AXIS in PAGE. */
201 cell_width (const struct render_page *page, int axis, int x)
203 return axis_width (page, axis, cell_ofs (x), cell_ofs (x) + 1);
206 /* Returns the width of rule X along AXIS in PAGE. */
208 rule_width (const struct render_page *page, int axis, int x)
210 return axis_width (page, axis, rule_ofs (x), rule_ofs (x) + 1);
213 /* Returns the width of rule X along AXIS in PAGE. */
215 rule_width_r (const struct render_page *page, int axis, int x)
217 int ofs = rule_ofs_r (page, axis, x);
218 return axis_width (page, axis, ofs, ofs + 1);
221 /* Returns the width of cells X0 through X1, exclusive, along AXIS in PAGE. */
223 joined_width (const struct render_page *page, int axis, int x0, int x1)
225 return axis_width (page, axis, cell_ofs (x0), cell_ofs (x1) - 1);
228 /* Returns the width of the widest cell, excluding headers, along AXIS in
231 max_cell_width (const struct render_page *page, int axis)
233 int n = page->n[axis];
234 int x0 = page->h[axis][0];
235 int x1 = n - page->h[axis][1];
239 for (x = x0; x < x1; x++)
241 int w = cell_width (page, axis, x);
248 /* A cell that doesn't completely fit on the render_page. */
249 struct render_overflow
251 struct hmap_node node; /* In render_page's 'overflows' hmap. */
253 /* Occupied region of page.
255 d[H][0] is the leftmost column.
256 d[H][1] is the rightmost column, plus 1.
257 d[V][0] is the top row.
258 d[V][1] is the bottom row, plus 1.
260 The cell in its original table might occupy a larger region. This
261 member reflects the size of the cell in the current render_page, after
262 trimming off any rows or columns due to page-breaking. */
265 /* The space that has been trimmed off the cell:
267 overflow[H][0]: space trimmed off its left side.
268 overflow[H][1]: space trimmed off its right side.
269 overflow[V][0]: space trimmed off its top.
270 overflow[V][1]: space trimmed off its bottom.
272 During rendering, this information is used to position the rendered
273 portion of the cell within the available space.
275 When a cell is rendered, sometimes it is permitted to spill over into
276 space that is ordinarily reserved for rules. Either way, this space is
277 still included in overflow values.
279 Suppose, for example, that a cell that joins 2 columns has a width of 60
280 pixels and content "abcdef", that the 2 columns that it joins have
281 widths of 20 and 30 pixels, respectively, and that therefore the rule
282 between the two joined columns has a width of 10 (20 + 10 + 30 = 60).
283 It might render like this, if each character is 10x10, and showing a few
284 extra table cells for context:
292 If this render_page is broken at the rule that separates "gh" from
293 "ijk", then the page that contains the left side of the "abcdef" cell
294 will have overflow[H][1] of 10 + 30 = 40 for its portion of the cell,
295 and the page that contains the right side of the cell will have
296 overflow[H][0] of 20 + 10 = 30. The two resulting pages would look like
314 int overflow[TABLE_N_AXES][2];
317 /* Returns a hash value for (,Y). */
319 hash_cell (int x, int y)
321 return hash_int (x + (y << 16), 0);
324 /* Searches PAGE's set of render_overflow for one whose top-left cell is
325 (X,Y). Returns it, if there is one, otherwise a null pointer. */
326 static const struct render_overflow *
327 find_overflow (const struct render_page *page, int x, int y)
329 if (!hmap_is_empty (&page->overflows))
331 const struct render_overflow *of;
333 HMAP_FOR_EACH_WITH_HASH (of, struct render_overflow, node,
334 hash_cell (x, y), &page->overflows)
335 if (x == of->d[H] && y == of->d[V])
343 struct render_footnote
345 struct hmap_node node;
347 /* The area of the table covered by the cell that has the footnote.
349 d[H][0] is the leftmost column.
350 d[H][1] is the rightmost column, plus 1.
351 d[V][0] is the top row.
352 d[V][1] is the bottom row, plus 1.
354 The cell in its original table might occupy a larger region. This
355 member reflects the size of the cell in the current render_page, after
356 trimming off any rows or columns due to page-breaking. */
357 int d[TABLE_N_AXES][2];
359 /* The index of the first footnote in the cell. */
364 count_footnotes (const struct table_cell *cell)
370 for (i = 0; i < cell->n_contents; i++)
371 n += cell->contents[i].n_footnotes;
376 find_footnote_idx (const struct table_cell *cell, const struct hmap *footnotes)
378 const struct render_footnote *f;
380 if (!count_footnotes (cell))
383 HMAP_FOR_EACH_WITH_HASH (f, struct render_footnote, node,
384 hash_cell (cell->d[H][0], cell->d[V][0]), footnotes)
385 if (f->d[H][0] == cell->d[H][0] && f->d[V][0] == cell->d[V][0])
391 /* Row or column dimensions. Used to figure the size of a table in
392 render_page_create() and discarded after that. */
395 /* Width without considering rows (or columns) that span more than one (or
399 /* Width taking spanned rows (or columns) into consideration. */
403 /* Modifies the 'width' members of the N elements of ROWS so that their sum,
404 when added to rule widths RULES[1] through RULES[N - 1] inclusive, is at
407 distribute_spanned_width (int width,
408 struct render_row *rows, const int *rules, int n)
414 /* Sum up the unspanned widths of the N rows for use as weights. */
416 for (x = 0; x < n; x++)
417 total_unspanned += rows[x].unspanned;
418 for (x = 0; x < n - 1; x++)
419 total_unspanned += rules[x + 1];
420 if (total_unspanned >= width)
423 /* The algorithm used here is based on the following description from HTML 4:
425 For cells that span multiple columns, a simple approach consists of
426 apportioning the min/max widths evenly to each of the constituent
427 columns. A slightly more complex approach is to use the min/max
428 widths of unspanned cells to weight how spanned widths are
429 apportioned. Experiments suggest that a blend of the two approaches
430 gives good results for a wide range of tables.
432 We blend the two approaches half-and-half, except that we cannot use the
433 unspanned weights when 'total_unspanned' is 0 (because that would cause a
436 This implementation uses floating-point types and operators, but all the
437 values involved are integers. For integers smaller than 53 bits, this
438 should not lose any precision, and it should degrade gracefully for larger
441 The calculation we want to do is this:
444 w1 = width * (column's unspanned width) / (total unspanned width)
445 (column's width) = (w0 + w1) / 2
447 We implement it as a precise calculation in integers by multiplying w0 and
448 w1 by the common denominator of all three calculations (d), dividing that
449 out in the column width calculation, and then keeping the remainder for
452 (We actually compute the unspanned width of a column as twice the
453 unspanned width, plus the width of the rule on the left, plus the width of
454 the rule on the right. That way each rule contributes to both the cell on
455 its left and on its right.)
458 d1 = 2.0 * (total_unspanned > 0 ? total_unspanned : 1.0);
460 if (total_unspanned > 0)
463 for (x = 0; x < n; x++)
466 if (total_unspanned > 0)
468 double unspanned = rows[x].unspanned * 2.0;
470 unspanned += rules[x + 1];
472 unspanned += rules[x];
473 w += width * unspanned * d0;
476 rows[x].width = MAX (rows[x].width, w / d);
477 w -= rows[x].width * d;
481 /* Initializes PAGE->cp[AXIS] from the row widths in ROWS and the rule widths
484 accumulate_row_widths (const struct render_page *page, enum table_axis axis,
485 const struct render_row *rows, const int *rules)
487 int n = page->n[axis];
493 for (z = 0; z < n; z++)
495 cp[1] = cp[0] + rules[z];
496 cp[2] = cp[1] + rows[z].width;
499 cp[1] = cp[0] + rules[n];
502 /* Returns the sum of widths of the N ROWS and N+1 RULES. */
504 calculate_table_width (int n, const struct render_row *rows, int *rules)
510 for (x = 0; x < n; x++)
511 width += rows[x].width;
512 for (x = 0; x <= n; x++)
518 /* Rendering utility functions. */
520 /* Returns the line style to use for drawing a rule of the given TYPE. */
521 static enum render_line_style
522 rule_to_render_type (unsigned char type)
528 return RENDER_LINE_NONE;
530 return RENDER_LINE_SINGLE;
532 return RENDER_LINE_DOUBLE;
538 /* Returns the width of the rule in TABLE that is at offset Z along axis A, if
539 rendered with PARAMS. */
541 measure_rule (const struct render_params *params, const struct table *table,
542 enum table_axis a, int z)
544 enum table_axis b = !a;
549 /* Determine all types of rules that are present, as a bitmap in 'rules'
550 where rule type 't' is present if bit 2**t is set. */
553 for (d[b] = 0; d[b] < table->n[b]; d[b]++)
554 rules |= 1u << table_get_rule (table, a, d[H], d[V]);
556 /* Calculate maximum width of the rules that are present. */
558 if (rules & (1u << TAL_1)
559 || (z > 0 && z < table->n[a] && rules & (1u << TAL_GAP)))
560 width = params->line_widths[a][RENDER_LINE_SINGLE];
561 if (rules & (1u << TAL_2))
562 width = MAX (width, params->line_widths[a][RENDER_LINE_DOUBLE]);
566 /* Allocates and returns a new render_page using PARAMS and TABLE. Allocates
567 space for all of the members of the new page, but the caller must initialize
568 the 'cp' member itself. */
569 static struct render_page *
570 render_page_allocate (const struct render_params *params,
573 struct render_page *page;
576 page = xmalloc (sizeof *page);
577 page->params = params;
580 page->n[H] = table->n[H];
581 page->n[V] = table->n[V];
582 page->h[H][0] = table->h[H][0];
583 page->h[H][1] = table->h[H][1];
584 page->h[V][0] = table->h[V][0];
585 page->h[V][1] = table->h[V][1];
587 for (i = 0; i < TABLE_N_AXES; i++)
589 page->cp[i] = xmalloc ((2 * page->n[i] + 2) * sizeof *page->cp[i]);
590 page->join_crossing[i] = xzalloc ((page->n[i] + 1) * sizeof *page->join_crossing[i]);
593 hmap_init (&page->overflows);
594 hmap_init (&page->footnotes);
595 page->n_footnotes = 0;
596 memset (page->is_edge_cutoff, 0, sizeof page->is_edge_cutoff);
601 /* Allocates and returns a new render_page for PARAMS and TABLE, initializing
602 cp[H] in the new page from ROWS and RULES. The caller must still initialize
604 static struct render_page *
605 create_page_with_exact_widths (const struct render_params *params,
607 const struct render_row *rows, int *rules)
609 struct render_page *page = render_page_allocate (params, table);
610 accumulate_row_widths (page, H, rows, rules);
614 /* Allocates and returns a new render_page for PARAMS and TABLE.
616 Initializes cp[H] in the new page by setting the width of each row 'i' to
617 somewhere between the minimum cell width ROW_MIN[i].width and the maximum
618 ROW_MAX[i].width. Sets the width of rules to those in RULES.
620 W_MIN is the sum of ROWS_MIN[].width.
622 W_MAX is the sum of ROWS_MAX[].width.
624 The caller must still initialize cp[V]. */
625 static struct render_page *
626 create_page_with_interpolated_widths (const struct render_params *params,
628 const struct render_row *rows_min,
629 const struct render_row *rows_max,
630 int w_min, int w_max, const int *rules)
632 /* This implementation uses floating-point types and operators, but all the
633 values involved are integers. For integers smaller than 53 bits, this
634 should not lose any precision, and it should degrade gracefully for larger
636 const int n = table->n[H];
637 const double avail = params->size[H] - w_min;
638 const double wanted = w_max - w_min;
639 struct render_page *page;
646 page = render_page_allocate (params, table);
650 w = (int) wanted / 2;
651 for (x = 0; x < n; x++)
655 w += avail * (rows_max[x].width - rows_min[x].width);
659 cph[1] = cph[0] + rules[x];
660 cph[2] = cph[1] + rows_min[x].width + extra;
663 cph[1] = cph[0] + rules[n];
665 assert (page->cp[H][n * 2 + 1] == params->size[H]);
671 set_join_crossings (struct render_page *page, enum table_axis axis,
672 const struct table_cell *cell, int *rules)
676 for (z = cell->d[axis][0] + 1; z <= cell->d[axis][1] - 1; z++)
677 page->join_crossing[axis][z] = rules[z];
680 /* Creates and returns a new render_page for rendering TABLE on a device
683 The new render_page will be suitable for rendering on a device whose page
684 size is PARAMS->size, but the caller is responsible for actually breaking it
685 up to fit on such a device, using the render_break abstraction. */
686 static struct render_page *
687 render_page_create (const struct render_params *params, struct table *table)
689 struct render_page *page;
691 struct render_row *columns[2];
692 struct render_row *rows;
694 int *rules[TABLE_N_AXES];
695 struct hmap footnotes;
700 enum table_axis axis;
702 nc = table_nc (table);
703 nr = table_nr (table);
705 /* Figure out rule widths. */
706 for (axis = 0; axis < TABLE_N_AXES; axis++)
708 int n = table->n[axis] + 1;
711 rules[axis] = xnmalloc (n, sizeof *rules);
712 for (z = 0; z < n; z++)
713 rules[axis][z] = measure_rule (params, table, axis, z);
716 /* Calculate minimum and maximum widths of cells that do not
717 span multiple columns. Assign footnote markers. */
718 hmap_init (&footnotes);
720 for (i = 0; i < 2; i++)
721 columns[i] = xzalloc (nc * sizeof *columns[i]);
722 for (y = 0; y < nr; y++)
723 for (x = 0; x < nc; )
725 struct table_cell cell;
727 table_get_cell (table, x, y, &cell);
728 if (y == cell.d[V][0])
732 if (table_cell_colspan (&cell) == 1)
737 params->measure_cell_width (params->aux, &cell, footnote_idx,
739 for (i = 0; i < 2; i++)
740 if (columns[i][x].unspanned < w[i])
741 columns[i][x].unspanned = w[i];
744 n = count_footnotes (&cell);
747 struct render_footnote *f = xmalloc (sizeof *f);
748 f->d[H][0] = cell.d[H][0];
749 f->d[H][1] = cell.d[H][1];
750 f->d[V][0] = cell.d[V][0];
751 f->d[V][1] = cell.d[V][1];
752 f->idx = footnote_idx;
753 hmap_insert (&footnotes, &f->node, hash_cell (x, y));
759 table_cell_free (&cell);
762 /* Distribute widths of spanned columns. */
763 for (i = 0; i < 2; i++)
764 for (x = 0; x < nc; x++)
765 columns[i][x].width = columns[i][x].unspanned;
766 for (y = 0; y < nr; y++)
767 for (x = 0; x < nc; )
769 struct table_cell cell;
771 table_get_cell (table, x, y, &cell);
772 if (y == cell.d[V][0] && table_cell_colspan (&cell) > 1)
776 params->measure_cell_width (params->aux, &cell,
777 find_footnote_idx (&cell, &footnotes),
779 for (i = 0; i < 2; i++)
780 distribute_spanned_width (w[i], &columns[i][cell.d[H][0]],
781 rules[H], table_cell_colspan (&cell));
784 table_cell_free (&cell);
787 /* In pathological cases, spans can cause the minimum width of a column to
788 exceed the maximum width. This bollixes our interpolation algorithm
789 later, so fix it up. */
790 for (i = 0; i < nc; i++)
791 if (columns[MIN][i].width > columns[MAX][i].width)
792 columns[MAX][i].width = columns[MIN][i].width;
794 /* Decide final column widths. */
795 for (i = 0; i < 2; i++)
796 table_widths[i] = calculate_table_width (table_nc (table),
797 columns[i], rules[H]);
798 if (table_widths[MAX] <= params->size[H])
800 /* Fits even with maximum widths. Use them. */
801 page = create_page_with_exact_widths (params, table, columns[MAX],
804 else if (table_widths[MIN] <= params->size[H])
806 /* Fits with minimum widths, so distribute the leftover space. */
807 page = create_page_with_interpolated_widths (
808 params, table, columns[MIN], columns[MAX],
809 table_widths[MIN], table_widths[MAX], rules[H]);
813 /* Doesn't fit even with minimum widths. Assign minimums for now, and
814 later we can break it horizontally into multiple pages. */
815 page = create_page_with_exact_widths (params, table, columns[MIN],
819 /* Calculate heights of cells that do not span multiple rows. */
820 rows = xzalloc (nr * sizeof *rows);
821 for (y = 0; y < nr; y++)
823 for (x = 0; x < nc; )
825 struct render_row *r = &rows[y];
826 struct table_cell cell;
828 table_get_cell (table, x, y, &cell);
829 if (y == cell.d[V][0])
831 if (table_cell_rowspan (&cell) == 1)
833 int w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
834 int h = params->measure_cell_height (
835 params->aux, &cell, find_footnote_idx (&cell, &footnotes), w);
836 if (h > r->unspanned)
837 r->unspanned = r->width = h;
840 set_join_crossings (page, V, &cell, rules[V]);
842 if (table_cell_colspan (&cell) > 1)
843 set_join_crossings (page, H, &cell, rules[H]);
846 table_cell_free (&cell);
849 for (i = 0; i < 2; i++)
852 /* Distribute heights of spanned rows. */
853 for (y = 0; y < nr; y++)
854 for (x = 0; x < nc; )
856 struct table_cell cell;
858 table_get_cell (table, x, y, &cell);
859 if (y == cell.d[V][0] && table_cell_rowspan (&cell) > 1)
861 int w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
862 int h = params->measure_cell_height (
863 params->aux, &cell, find_footnote_idx (&cell, &footnotes), w);
864 distribute_spanned_width (h, &rows[cell.d[V][0]], rules[V],
865 table_cell_rowspan (&cell));
868 table_cell_free (&cell);
871 /* Decide final row heights. */
872 accumulate_row_widths (page, V, rows, rules[V]);
875 /* Measure headers. If they are "too big", get rid of them. */
876 for (axis = 0; axis < TABLE_N_AXES; axis++)
878 int hw = headers_width (page, axis);
879 if (hw * 2 >= page->params->size[axis]
880 || hw + max_cell_width (page, axis) > page->params->size[axis])
882 page->table = table_unshare (page->table);
883 page->table->h[axis][0] = page->table->h[axis][1] = 0;
884 page->h[axis][0] = page->h[axis][1] = 0;
888 hmap_swap (&page->footnotes, &footnotes);
889 hmap_destroy (&footnotes);
890 page->n_footnotes = footnote_idx;
898 /* Increases PAGE's reference count. */
900 render_page_ref (const struct render_page *page_)
902 struct render_page *page = CONST_CAST (struct render_page *, page_);
907 /* Decreases PAGE's reference count and destroys PAGE if this causes the
908 reference count to fall to zero. */
910 render_page_unref (struct render_page *page)
912 if (page != NULL && --page->ref_cnt == 0)
915 struct render_overflow *overflow, *next;
917 HMAP_FOR_EACH_SAFE (overflow, next, struct render_overflow, node,
920 hmap_destroy (&page->overflows);
922 table_unref (page->table);
924 for (i = 0; i < TABLE_N_AXES; ++i)
926 free (page->join_crossing[i]);
934 /* Returns the size of PAGE along AXIS. (This might be larger than the page
935 size specified in the parameters passed to render_page_create(). Use a
936 render_break to break up a render_page into page-sized chunks.) */
938 render_page_get_size (const struct render_page *page, enum table_axis axis)
940 return page->cp[axis][page->n[axis] * 2 + 1];
944 render_page_get_best_breakpoint (const struct render_page *page, int height)
948 /* If there's no room for at least the top row and the rules above and below
949 it, don't include any of the table. */
950 if (page->cp[V][3] > height)
953 /* Otherwise include as many rows and rules as we can. */
954 for (y = 5; y <= 2 * page->n[V] + 1; y += 2)
955 if (page->cp[V][y] > height)
956 return page->cp[V][y - 2];
960 /* Drawing render_pages. */
962 static inline enum render_line_style
963 get_rule (const struct render_page *page, enum table_axis axis,
964 const int d[TABLE_N_AXES])
966 return rule_to_render_type (table_get_rule (page->table,
967 axis, d[H] / 2, d[V] / 2));
977 render_direction_rtl (void)
979 /* TRANSLATORS: Do not translate this string. If the script of your language
980 reads from right to left (eg Persian, Arabic, Hebrew etc), then replace
981 this string with "output-direction-rtl". Otherwise either leave it
982 untranslated or copy it verbatim. */
983 const char *dir = _("output-direction-ltr");
984 if ( 0 == strcmp ("output-direction-rtl", dir))
987 if ( 0 != strcmp ("output-direction-ltr", dir))
988 fprintf (stderr, "This localisation has been incorrectly translated. Complain to the translator.\n");
994 render_rule (const struct render_page *page, const int ofs[TABLE_N_AXES],
995 const int d[TABLE_N_AXES])
997 enum render_line_style styles[TABLE_N_AXES][2];
1000 for (a = 0; a < TABLE_N_AXES; a++)
1002 enum table_axis b = !a;
1004 styles[a][0] = styles[a][1] = RENDER_LINE_NONE;
1007 || (page->is_edge_cutoff[a][0] && d[a] == 0)
1008 || (page->is_edge_cutoff[a][1] && d[a] == page->n[a] * 2))
1015 int e[TABLE_N_AXES];
1019 styles[a][0] = get_rule (page, a, e);
1022 if (d[b] / 2 < page->table->n[b])
1023 styles[a][1] = get_rule (page, a, d);
1026 styles[a][0] = styles[a][1] = get_rule (page, a, d);
1029 if (styles[H][0] != RENDER_LINE_NONE || styles[H][1] != RENDER_LINE_NONE
1030 || styles[V][0] != RENDER_LINE_NONE || styles[V][1] != RENDER_LINE_NONE)
1032 int bb[TABLE_N_AXES][2];
1034 bb[H][0] = ofs[H] + page->cp[H][d[H]];
1035 bb[H][1] = ofs[H] + page->cp[H][d[H] + 1];
1036 if (render_direction_rtl ())
1038 int temp = bb[H][0];
1039 bb[H][0] = render_page_get_size (page, H) - bb[H][1];
1040 bb[H][1] = render_page_get_size (page, H) - temp;
1042 bb[V][0] = ofs[V] + page->cp[V][d[V]];
1043 bb[V][1] = ofs[V] + page->cp[V][d[V] + 1];
1044 page->params->draw_line (page->params->aux, bb, styles);
1049 render_cell (const struct render_page *page, const int ofs[TABLE_N_AXES],
1050 const struct table_cell *cell)
1052 const struct render_overflow *of;
1053 int bb[TABLE_N_AXES][2];
1054 int clip[TABLE_N_AXES][2];
1056 bb[H][0] = clip[H][0] = ofs[H] + page->cp[H][cell->d[H][0] * 2 + 1];
1057 bb[H][1] = clip[H][1] = ofs[H] + page->cp[H][cell->d[H][1] * 2];
1058 if (render_direction_rtl ())
1060 int temp = bb[H][0];
1061 bb[H][0] = clip[H][0] = render_page_get_size (page, H) - bb[H][1];
1062 bb[H][1] = clip[H][1] = render_page_get_size (page, H) - temp;
1064 bb[V][0] = clip[V][0] = ofs[V] + page->cp[V][cell->d[V][0] * 2 + 1];
1065 bb[V][1] = clip[V][1] = ofs[V] + page->cp[V][cell->d[V][1] * 2];
1067 of = find_overflow (page, cell->d[H][0], cell->d[V][0]);
1070 enum table_axis axis;
1072 for (axis = 0; axis < TABLE_N_AXES; axis++)
1074 if (of->overflow[axis][0])
1076 bb[axis][0] -= of->overflow[axis][0];
1077 if (cell->d[axis][0] == 0 && !page->is_edge_cutoff[axis][0])
1078 clip[axis][0] = ofs[axis] + page->cp[axis][cell->d[axis][0] * 2];
1080 if (of->overflow[axis][1])
1082 bb[axis][1] += of->overflow[axis][1];
1083 if (cell->d[axis][1] == page->n[axis] && !page->is_edge_cutoff[axis][1])
1084 clip[axis][1] = ofs[axis] + page->cp[axis][cell->d[axis][1] * 2 + 1];
1089 page->params->draw_cell (page->params->aux, cell,
1090 find_footnote_idx (cell, &page->footnotes), bb, clip);
1093 /* Draws the cells of PAGE indicated in BB. */
1095 render_page_draw_cells (const struct render_page *page,
1096 int ofs[TABLE_N_AXES], int bb[TABLE_N_AXES][2])
1100 for (y = bb[V][0]; y < bb[V][1]; y++)
1101 for (x = bb[H][0]; x < bb[H][1]; )
1102 if (is_rule (x) || is_rule (y))
1104 int d[TABLE_N_AXES];
1107 render_rule (page, ofs, d);
1112 struct table_cell cell;
1114 table_get_cell (page->table, x / 2, y / 2, &cell);
1115 if (y / 2 == bb[V][0] / 2 || y / 2 == cell.d[V][0])
1116 render_cell (page, ofs, &cell);
1117 x = rule_ofs (cell.d[H][1]);
1118 table_cell_free (&cell);
1122 /* Renders PAGE, by calling the 'draw_line' and 'draw_cell' functions from the
1123 render_params provided to render_page_create(). */
1125 render_page_draw (const struct render_page *page, int ofs[TABLE_N_AXES])
1127 int bb[TABLE_N_AXES][2];
1130 bb[H][1] = page->n[H] * 2 + 1;
1132 bb[V][1] = page->n[V] * 2 + 1;
1134 render_page_draw_cells (page, ofs, bb);
1137 /* Returns the greatest value i, 0 <= i < n, such that cp[i] <= x0. */
1139 get_clip_min_extent (int x0, const int cp[], int n)
1141 int low, high, best;
1148 int middle = low + (high - low) / 2;
1150 if (cp[middle] <= x0)
1162 /* Returns the least value i, 0 <= i < n, such that cp[i] >= x1. */
1164 get_clip_max_extent (int x1, const int cp[], int n)
1166 int low, high, best;
1173 int middle = low + (high - low) / 2;
1175 if (cp[middle] >= x1)
1176 best = high = middle;
1181 while (best > 0 && cp[best - 1] == cp[best])
1187 /* Renders the cells of PAGE that intersect (X,Y)-(X+W,Y+H), by calling the
1188 'draw_line' and 'draw_cell' functions from the render_params provided to
1189 render_page_create(). */
1191 render_page_draw_region (const struct render_page *page,
1192 int ofs[TABLE_N_AXES], int clip[TABLE_N_AXES][2])
1194 int bb[TABLE_N_AXES][2];
1196 bb[H][0] = get_clip_min_extent (clip[H][0], page->cp[H], page->n[H] * 2 + 1);
1197 bb[H][1] = get_clip_max_extent (clip[H][1], page->cp[H], page->n[H] * 2 + 1);
1198 bb[V][0] = get_clip_min_extent (clip[V][0], page->cp[V], page->n[V] * 2 + 1);
1199 bb[V][1] = get_clip_max_extent (clip[V][1], page->cp[V], page->n[V] * 2 + 1);
1201 render_page_draw_cells (page, ofs, bb);
1204 /* Breaking up tables to fit on a page. */
1206 /* An iterator for breaking render_pages into smaller chunks. */
1209 struct render_page *page; /* Page being broken up. */
1210 enum table_axis axis; /* Axis along which 'page' is being broken. */
1211 int z; /* Next cell along 'axis'. */
1212 int pixel; /* Pixel offset within cell 'z' (usually 0). */
1213 int hw; /* Width of headers of 'page' along 'axis'. */
1216 static int needed_size (const struct render_break *, int cell);
1217 static bool cell_is_breakable (const struct render_break *, int cell);
1218 static struct render_page *render_page_select (const struct render_page *,
1223 /* Initializes render_break B for breaking PAGE along AXIS.
1224 Takes ownership of PAGE. */
1226 render_break_init (struct render_break *b, struct render_page *page,
1227 enum table_axis axis)
1231 b->z = page->h[axis][0];
1233 b->hw = headers_width (page, axis);
1236 /* Initializes B as a render_break structure for which
1237 render_break_has_next() always returns false. */
1239 render_break_init_empty (struct render_break *b)
1242 b->axis = TABLE_HORZ;
1248 /* Frees B and unrefs the render_page that it owns. */
1250 render_break_destroy (struct render_break *b)
1254 render_page_unref (b->page);
1259 /* Returns true if B still has cells that are yet to be returned,
1260 false if all of B's page has been processed. */
1262 render_break_has_next (const struct render_break *b)
1264 const struct render_page *page = b->page;
1265 enum table_axis axis = b->axis;
1267 return page != NULL && b->z < page->n[axis] - page->h[axis][1];
1270 /* Returns a new render_page that is up to SIZE pixels wide along B's axis.
1271 Returns a null pointer if B has already been completely broken up, or if
1272 SIZE is too small to reasonably render any cells. The latter will never
1273 happen if SIZE is at least as large as the page size passed to
1274 render_page_create() along B's axis. */
1275 static struct render_page *
1276 render_break_next (struct render_break *b, int size)
1278 const struct render_page *page = b->page;
1279 enum table_axis axis = b->axis;
1280 struct render_page *subpage;
1283 if (!render_break_has_next (b))
1287 for (z = b->z; z < page->n[axis] - page->h[axis][1]; z++)
1289 int needed = needed_size (b, z + 1);
1292 if (cell_is_breakable (b, z))
1294 /* If there is no right header and we render a partial cell on
1295 the right side of the body, then we omit the rightmost rule of
1296 the body. Otherwise the rendering is deceptive because it
1297 looks like the whole cell is present instead of a partial
1300 This is similar to code for the left side in needed_size(). */
1301 int rule_allowance = (page->h[axis][1]
1303 : rule_width (page, axis, z));
1305 /* The amount that, if we added cell 'z', the rendering would
1306 overfill the allocated 'size'. */
1307 int overhang = needed - size - rule_allowance;
1309 /* The width of cell 'z'. */
1310 int cell_size = cell_width (page, axis, z);
1312 /* The amount trimmed off the left side of 'z',
1313 and the amount left to render. */
1314 int cell_ofs = z == b->z ? b->pixel : 0;
1315 int cell_left = cell_size - cell_ofs;
1317 /* A small but visible width. */
1318 int em = page->params->font_size[axis];
1320 /* If some of the cell remains to render,
1321 and there would still be some of the cell left afterward,
1322 then partially render that much of the cell. */
1323 pixel = (cell_left && cell_left > overhang
1324 ? cell_left - overhang + cell_ofs
1327 /* If there would be only a tiny amount of the cell left after
1328 rendering it partially, reduce the amount rendered slightly
1329 to make the output look a little better. */
1330 if (pixel + em > cell_size)
1331 pixel = MAX (pixel - em, 0);
1333 /* If we're breaking vertically, then consider whether the cells
1334 being broken have a better internal breakpoint than the exact
1335 number of pixels available, which might look bad e.g. because
1336 it breaks in the middle of a line of text. */
1337 if (axis == TABLE_VERT && page->params->adjust_break)
1341 for (x = 0; x < page->n[H]; )
1343 struct table_cell cell;
1347 table_get_cell (page->table, x, z, &cell);
1348 w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
1349 better_pixel = page->params->adjust_break (
1350 page->params->aux, &cell,
1351 find_footnote_idx (&cell, &page->footnotes), w, pixel);
1353 table_cell_free (&cell);
1355 if (better_pixel < pixel)
1357 if (better_pixel > (z == b->z ? b->pixel : 0))
1359 pixel = better_pixel;
1362 else if (better_pixel == 0 && z != b->z)
1375 if (z == b->z && !pixel)
1378 subpage = render_page_select (page, axis, b->z, b->pixel,
1380 pixel ? cell_width (page, axis, z) - pixel
1387 /* Returns the width that would be required along B's axis to render a page
1388 from B's current position up to but not including CELL. */
1390 needed_size (const struct render_break *b, int cell)
1392 const struct render_page *page = b->page;
1393 enum table_axis axis = b->axis;
1396 /* Width of left header not including its rightmost rule. */
1397 size = axis_width (page, axis, 0, rule_ofs (page->h[axis][0]));
1399 /* If we have a pixel offset and there is no left header, then we omit the
1400 leftmost rule of the body. Otherwise the rendering is deceptive because
1401 it looks like the whole cell is present instead of a partial cell.
1403 Otherwise (if there are headers) we will be merging two rules: the
1404 rightmost rule in the header and the leftmost rule in the body. We assume
1405 that the width of a merged rule is the larger of the widths of either rule
1407 if (b->pixel == 0 || page->h[axis][0])
1408 size += MAX (rule_width (page, axis, page->h[axis][0]),
1409 rule_width (page, axis, b->z));
1411 /* Width of body, minus any pixel offset in the leftmost cell. */
1412 size += joined_width (page, axis, b->z, cell) - b->pixel;
1414 /* Width of rightmost rule in body merged with leftmost rule in headers. */
1415 size += MAX (rule_width_r (page, axis, page->h[axis][1]),
1416 rule_width (page, axis, cell));
1418 /* Width of right header not including its leftmost rule. */
1419 size += axis_width (page, axis, rule_ofs_r (page, axis, page->h[axis][1]),
1420 rule_ofs_r (page, axis, 0));
1422 /* Join crossing. */
1423 if (page->h[axis][0] && page->h[axis][1])
1424 size += page->join_crossing[axis][b->z];
1429 /* Returns true if CELL along B's axis may be broken across a page boundary.
1431 This is just a heuristic. Breaking cells across page boundaries can save
1432 space, but it looks ugly. */
1434 cell_is_breakable (const struct render_break *b, int cell)
1436 const struct render_page *page = b->page;
1437 enum table_axis axis = b->axis;
1439 return cell_width (page, axis, cell) >= page->params->min_break[axis];
1446 const struct render_params *params;
1448 struct render_page **pages;
1449 size_t n_pages, allocated_pages;
1452 struct render_break x_break;
1453 struct render_break y_break;
1456 static const struct render_page *
1457 render_pager_add_table (struct render_pager *p, struct table *table)
1459 struct render_page *page;
1461 if (p->n_pages >= p->allocated_pages)
1462 p->pages = x2nrealloc (p->pages, &p->allocated_pages, sizeof *p->pages);
1463 page = p->pages[p->n_pages++] = render_page_create (p->params, table);
1468 render_pager_start_page (struct render_pager *p)
1470 render_break_init (&p->x_break, render_page_ref (p->pages[p->cur_page++]),
1472 render_break_init_empty (&p->y_break);
1476 add_footnote_page (struct render_pager *p, const struct render_page *body)
1478 const struct table *table = body->table;
1479 int nc = table_nc (table);
1480 int nr = table_nr (table);
1481 int footnote_idx = 0;
1482 struct tab_table *t;
1485 if (!body->n_footnotes)
1488 t = tab_create (2, body->n_footnotes);
1489 for (y = 0; y < nr; y++)
1490 for (x = 0; x < nc; )
1492 struct table_cell cell;
1494 table_get_cell (table, x, y, &cell);
1495 if (y == cell.d[V][0])
1499 for (i = 0; i < cell.n_contents; i++)
1501 const struct cell_contents *cc = &cell.contents[i];
1504 for (j = 0; j < cc->n_footnotes; j++)
1506 const char *f = cc->footnotes[j];
1508 tab_text (t, 0, footnote_idx, TAB_LEFT, "");
1509 tab_footnote (t, 0, footnote_idx, "(none)");
1510 tab_text (t, 1, footnote_idx, TAB_LEFT, f);
1516 table_cell_free (&cell);
1518 render_pager_add_table (p, &t->table);
1521 /* Creates and returns a new render_pager for rendering TABLE_ITEM on the
1522 device with the given PARAMS. */
1523 struct render_pager *
1524 render_pager_create (const struct render_params *params,
1525 const struct table_item *table_item)
1527 const char *caption = table_item_get_caption (table_item);
1528 const char *title = table_item_get_title (table_item);
1529 const struct render_page *body_page;
1530 struct render_pager *p;
1532 p = xzalloc (sizeof *p);
1537 render_pager_add_table (p, table_from_string (TAB_LEFT, title));
1540 body_page = render_pager_add_table (p, table_ref (table_item_get_table (
1545 render_pager_add_table (p, table_from_string (TAB_LEFT, caption));
1548 add_footnote_page (p, body_page);
1550 render_pager_start_page (p);
1557 render_pager_destroy (struct render_pager *p)
1563 render_break_destroy (&p->x_break);
1564 render_break_destroy (&p->y_break);
1565 for (i = 0; i < p->n_pages; i++)
1566 render_page_unref (p->pages[i]);
1572 /* Returns true if P has content remaining to render, false if rendering is
1575 render_pager_has_next (const struct render_pager *p_)
1577 struct render_pager *p = CONST_CAST (struct render_pager *, p_);
1579 while (!render_break_has_next (&p->y_break))
1581 render_break_destroy (&p->y_break);
1582 if (!render_break_has_next (&p->x_break))
1584 render_break_destroy (&p->x_break);
1585 if (p->cur_page >= p->n_pages)
1587 render_break_init_empty (&p->x_break);
1588 render_break_init_empty (&p->y_break);
1591 render_pager_start_page (p);
1594 render_break_init (&p->y_break,
1595 render_break_next (&p->x_break, p->params->size[H]), V);
1600 /* Draws a chunk of content from P to fit in a space that has vertical size
1601 SPACE and the horizontal size specified in the render_params passed to
1602 render_page_create(). Returns the amount of space actually used by the
1603 rendered chunk, which will be 0 if SPACE is too small to render anything or
1604 if no content remains (use render_pager_has_next() to distinguish these
1607 render_pager_draw_next (struct render_pager *p, int space)
1609 int ofs[TABLE_N_AXES] = { 0, 0 };
1610 size_t start_page = SIZE_MAX;
1612 while (render_pager_has_next (p))
1614 struct render_page *page;
1616 if (start_page == p->cur_page)
1618 start_page = p->cur_page;
1620 page = render_break_next (&p->y_break, space - ofs[V]);
1624 render_page_draw (page, ofs);
1625 ofs[V] += render_page_get_size (page, V);
1626 render_page_unref (page);
1631 /* Draws all of P's content. */
1633 render_pager_draw (const struct render_pager *p)
1635 render_pager_draw_region (p, 0, 0, INT_MAX, INT_MAX);
1638 /* Draws the region of P's content that lies in the region (X,Y)-(X+W,Y+H).
1639 Some extra content might be drawn; the device should perform clipping as
1642 render_pager_draw_region (const struct render_pager *p,
1643 int x, int y, int w, int h)
1645 int ofs[TABLE_N_AXES] = { 0, 0 };
1646 int clip[TABLE_N_AXES][2];
1651 for (i = 0; i < p->n_pages; i++)
1653 const struct render_page *page = p->pages[i];
1654 int size = render_page_get_size (page, V);
1656 clip[V][0] = MAX (y, ofs[V]) - ofs[V];
1657 clip[V][1] = MIN (y + h, ofs[V] + size) - ofs[V];
1658 if (clip[V][1] > clip[V][0])
1659 render_page_draw_region (page, ofs, clip);
1665 /* Returns the size of P's content along AXIS; i.e. the content's width if AXIS
1666 is TABLE_HORZ and its length if AXIS is TABLE_VERT. */
1668 render_pager_get_size (const struct render_pager *p, enum table_axis axis)
1673 for (i = 0; i < p->n_pages; i++)
1675 int subsize = render_page_get_size (p->pages[i], axis);
1676 size = axis == H ? MAX (size, subsize) : size + subsize;
1683 render_pager_get_best_breakpoint (const struct render_pager *p, int height)
1688 for (i = 0; i < p->n_pages; i++)
1690 int size = render_page_get_size (p->pages[i], V);
1691 if (y + size >= height)
1692 return render_page_get_best_breakpoint (p->pages[i], height - y) + y;
1699 /* render_page_select() and helpers. */
1701 struct render_page_selection
1703 const struct render_page *page; /* Page whose slice we are selecting. */
1704 struct render_page *subpage; /* New page under construction. */
1705 enum table_axis a; /* Axis of 'page' along which 'subpage' is a slice. */
1706 enum table_axis b; /* The opposite of 'a'. */
1707 int z0; /* First cell along 'a' being selected. */
1708 int z1; /* Last cell being selected, plus 1. */
1709 int p0; /* Number of pixels to trim off left side of z0. */
1710 int p1; /* Number of pixels to trim off right side of z1-1. */
1713 static void cell_to_subpage (struct render_page_selection *,
1714 const struct table_cell *,
1715 int subcell[TABLE_N_AXES]);
1716 static const struct render_overflow *find_overflow_for_cell (
1717 struct render_page_selection *, const struct table_cell *);
1718 static struct render_overflow *insert_overflow (struct render_page_selection *,
1719 const struct table_cell *);
1721 /* Creates and returns a new render_page whose contents are a subregion of
1722 PAGE's contents. The new render_page includes cells Z0 through Z1
1723 (exclusive) along AXIS, plus any headers on AXIS.
1725 If P0 is nonzero, then it is a number of pixels to exclude from the left or
1726 top (according to AXIS) of cell Z0. Similarly, P1 is a number of pixels to
1727 exclude from the right or bottom of cell Z1 - 1. (P0 and P1 are used to
1728 render cells that are too large to fit on a single page.)
1730 The whole of axis !AXIS is included. (The caller may follow up with another
1731 call to render_page_select() to select on !AXIS to select on that axis as
1734 The caller retains ownership of PAGE, which is not modified. */
1735 static struct render_page *
1736 render_page_select (const struct render_page *page, enum table_axis axis,
1737 int z0, int p0, int z1, int p1)
1739 const struct render_footnote *f;
1740 struct render_page_selection s;
1741 enum table_axis a = axis;
1742 enum table_axis b = !a;
1743 struct render_page *subpage;
1744 struct render_overflow *ro;
1750 /* Optimize case where all of PAGE is selected by just incrementing the
1752 if (z0 == page->h[a][0] && p0 == 0
1753 && z1 == page->n[a] - page->h[a][1] && p1 == 0)
1755 struct render_page *page_rw = CONST_CAST (struct render_page *, page);
1760 /* Allocate subpage. */
1761 subpage = render_page_allocate (page->params,
1762 table_select_slice (
1763 table_ref (page->table),
1766 /* An edge is cut off if it was cut off in PAGE or if we're trimming pixels
1767 off that side of the page and there are no headers. */
1768 subpage->is_edge_cutoff[a][0] =
1769 subpage->h[a][0] == 0 && (p0 || (z0 == 0 && page->is_edge_cutoff[a][0]));
1770 subpage->is_edge_cutoff[a][1] =
1771 subpage->h[a][1] == 0 && (p1 || (z1 == page->n[a]
1772 && page->is_edge_cutoff[a][1]));
1773 subpage->is_edge_cutoff[b][0] = page->is_edge_cutoff[b][0];
1774 subpage->is_edge_cutoff[b][1] = page->is_edge_cutoff[b][1];
1776 /* Select join crossings from PAGE into subpage. */
1777 jc = subpage->join_crossing[a];
1778 for (z = 0; z < page->h[a][0]; z++)
1779 *jc++ = page->join_crossing[a][z];
1780 for (z = z0; z <= z1; z++)
1781 *jc++ = page->join_crossing[a][z];
1782 for (z = page->n[a] - page->h[a][1]; z < page->n[a]; z++)
1783 *jc++ = page->join_crossing[a][z];
1784 assert (jc == &subpage->join_crossing[a][subpage->n[a] + 1]);
1786 memcpy (subpage->join_crossing[b], page->join_crossing[b],
1787 (subpage->n[b] + 1) * sizeof **subpage->join_crossing);
1789 /* Select widths from PAGE into subpage. */
1791 dcp = subpage->cp[a];
1793 for (z = 0; z <= rule_ofs (subpage->h[a][0]); z++, dcp++)
1795 if (z == 0 && subpage->is_edge_cutoff[a][0])
1798 dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1800 for (z = cell_ofs (z0); z <= cell_ofs (z1 - 1); z++, dcp++)
1802 dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1803 if (z == cell_ofs (z0))
1806 if (page->h[a][0] && page->h[a][1])
1807 dcp[1] += page->join_crossing[a][z / 2];
1809 if (z == cell_ofs (z1 - 1))
1812 for (z = rule_ofs_r (page, a, subpage->h[a][1]);
1813 z <= rule_ofs_r (page, a, 0); z++, dcp++)
1815 if (z == rule_ofs_r (page, a, 0) && subpage->is_edge_cutoff[a][1])
1818 dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1820 assert (dcp == &subpage->cp[a][2 * subpage->n[a] + 1]);
1822 for (z = 0; z < page->n[b] * 2 + 2; z++)
1823 subpage->cp[b][z] = page->cp[b][z];
1825 /* Add new overflows. */
1833 s.subpage = subpage;
1835 if (!page->h[a][0] || z0 > page->h[a][0] || p0)
1836 for (z = 0; z < page->n[b]; )
1838 struct table_cell cell;
1839 int d[TABLE_N_AXES];
1846 table_get_cell (page->table, d[H], d[V], &cell);
1847 overflow0 = p0 || cell.d[a][0] < z0;
1848 overflow1 = cell.d[a][1] > z1 || (cell.d[a][1] == z1 && p1);
1849 if (overflow0 || overflow1)
1851 ro = insert_overflow (&s, &cell);
1855 ro->overflow[a][0] += p0 + axis_width (
1856 page, a, cell_ofs (cell.d[a][0]), cell_ofs (z0));
1857 if (page->h[a][0] && page->h[a][1])
1858 ro->overflow[a][0] -= page->join_crossing[a][cell.d[a][0]
1864 ro->overflow[a][1] += p1 + axis_width (
1865 page, a, cell_ofs (z1), cell_ofs (cell.d[a][1]));
1866 if (page->h[a][0] && page->h[a][1])
1867 ro->overflow[a][1] -= page->join_crossing[a][cell.d[a][1]];
1871 table_cell_free (&cell);
1874 if (!page->h[a][1] || z1 < page->n[a] - page->h[a][1] || p1)
1875 for (z = 0; z < page->n[b]; )
1877 struct table_cell cell;
1878 int d[TABLE_N_AXES];
1882 table_get_cell (page->table, d[H], d[V], &cell);
1883 if ((cell.d[a][1] > z1 || (cell.d[a][1] == z1 && p1))
1884 && find_overflow_for_cell (&s, &cell) == NULL)
1886 ro = insert_overflow (&s, &cell);
1887 ro->overflow[a][1] += p1 + axis_width (page, a, cell_ofs (z1),
1888 cell_ofs (cell.d[a][1]));
1891 table_cell_free (&cell);
1894 /* Copy overflows from PAGE into subpage. */
1895 HMAP_FOR_EACH (ro, struct render_overflow, node, &page->overflows)
1897 struct table_cell cell;
1899 table_get_cell (page->table, ro->d[H], ro->d[V], &cell);
1900 if (cell.d[a][1] > z0 && cell.d[a][0] < z1
1901 && find_overflow_for_cell (&s, &cell) == NULL)
1902 insert_overflow (&s, &cell);
1903 table_cell_free (&cell);
1906 /* Copy footnotes from PAGE into subpage. */
1907 HMAP_FOR_EACH (f, struct render_footnote, node, &page->footnotes)
1908 if ((f->d[a][0] >= z0 && f->d[a][0] < z1)
1909 || (f->d[a][1] - 1 >= z0 && f->d[a][1] - 1 < z1))
1911 struct render_footnote *nf = xmalloc (sizeof *nf);
1912 nf->d[a][0] = MAX (z0, f->d[a][0]) - z0 + page->h[a][0];
1913 nf->d[a][1] = MIN (z1, f->d[a][1]) - z0 + page->h[a][0];
1914 nf->d[b][0] = f->d[b][0];
1915 nf->d[b][1] = f->d[b][1];
1917 hmap_insert (&subpage->footnotes, &nf->node,
1918 hash_cell (nf->d[H][0], nf->d[V][0]));
1924 /* Given CELL, a table_cell within S->page, stores in SUBCELL the (x,y)
1925 coordinates of the top-left cell as it will appear in S->subpage.
1927 CELL must actually intersect the region of S->page that is being selected
1928 by render_page_select() or the results will not make any sense. */
1930 cell_to_subpage (struct render_page_selection *s,
1931 const struct table_cell *cell, int subcell[TABLE_N_AXES])
1933 enum table_axis a = s->a;
1934 enum table_axis b = s->b;
1935 int ha0 = s->subpage->h[a][0];
1937 subcell[a] = MAX (cell->d[a][0] - s->z0 + ha0, ha0);
1938 subcell[b] = cell->d[b][0];
1941 /* Given CELL, a table_cell within S->page, returns the render_overflow for
1942 that cell in S->subpage, if there is one, and a null pointer otherwise.
1944 CELL must actually intersect the region of S->page that is being selected
1945 by render_page_select() or the results will not make any sense. */
1946 static const struct render_overflow *
1947 find_overflow_for_cell (struct render_page_selection *s,
1948 const struct table_cell *cell)
1952 cell_to_subpage (s, cell, subcell);
1953 return find_overflow (s->subpage, subcell[H], subcell[V]);
1956 /* Given CELL, a table_cell within S->page, inserts a render_overflow for that
1957 cell in S->subpage (which must not already exist). Initializes the new
1958 render_overflow's 'overflow' member from the overflow for CELL in S->page,
1961 CELL must actually intersect the region of S->page that is being selected
1962 by render_page_select() or the results will not make any sense. */
1963 static struct render_overflow *
1964 insert_overflow (struct render_page_selection *s,
1965 const struct table_cell *cell)
1967 const struct render_overflow *old;
1968 struct render_overflow *of;
1970 of = xzalloc (sizeof *of);
1971 cell_to_subpage (s, cell, of->d);
1972 hmap_insert (&s->subpage->overflows, &of->node,
1973 hash_cell (of->d[H], of->d[V]));
1975 old = find_overflow (s->page, cell->d[H][0], cell->d[V][0]);
1977 memcpy (of->overflow, old->overflow, sizeof of->overflow);