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];
64 cp[H] represents x positions within the table.
66 cp[H][1] = the width of the leftmost vertical rule.
67 cp[H][2] = cp[H][1] + the width of the leftmost column.
68 cp[H][3] = cp[H][2] + the width of the second-from-left vertical rule.
70 cp[H][2 * nc] = x position of the rightmost vertical rule.
71 cp[H][2 * nc + 1] = total table width including all rules.
73 Similarly, cp[V] represents y positions within the table.
75 cp[V][1] = the height of the topmost horizontal rule.
76 cp[V][2] = cp[V][1] + the height of the topmost row.
77 cp[V][3] = cp[V][2] + the height of the second-from-top horizontal rule.
79 cp[V][2 * nr] = y position of the bottommost horizontal rule.
80 cp[V][2 * nr + 1] = total table height including all rules.
82 Rules and columns can have width or height 0, in which case consecutive
83 values in this array are equal. */
84 int *cp[TABLE_N_AXES];
86 /* render_break_next() can break a table such that some cells are not fully
87 contained within a render_page. This will happen if a cell is too wide
88 or two tall to fit on a single page, or if a cell spans multiple rows or
89 columns and the page only includes some of those rows or columns.
91 This hash table contains "struct render_overflow"s that represents each
92 such cell that doesn't completely fit on this page.
94 Each overflow cell borders at least one header edge of the table and may
95 border more. (A single table cell that is so large that it fills the
96 entire page can overflow on all four sides!) */
97 struct hmap overflows;
99 /* If a single column (or row) is too wide (or tall) to fit on a page
100 reasonably, then render_break_next() will split a single row or column
101 across multiple render_pages. This member indicates when this has
104 is_edge_cutoff[H][0] is true if pixels have been cut off the left side
105 of the leftmost column in this page, and false otherwise.
107 is_edge_cutoff[H][1] is true if pixels have been cut off the right side
108 of the rightmost column in this page, and false otherwise.
110 is_edge_cutoff[V][0] and is_edge_cutoff[V][1] are similar for the top
111 and bottom of the table.
113 The effect of is_edge_cutoff is to prevent rules along the edge in
114 question from being rendered.
116 When is_edge_cutoff is true for a given edge, the 'overflows' hmap will
117 contain a node for each cell along that edge. */
118 bool is_edge_cutoff[TABLE_N_AXES][2];
120 /* If part of a joined cell would be cut off by breaking a table along
121 'axis' at the rule with offset 'z' (where 0 <= z <= n[axis]), then
122 join_crossing[axis][z] is the thickness of the rule that would be cut
125 This is used to know to allocate extra space for breaking at such a
126 position, so that part of the cell's content is not lost.
128 This affects breaking a table only when headers are present. When
129 headers are not present, the rule's thickness is used for cell content,
130 so no part of the cell's content is lost (and in fact it is duplicated
131 across both pages). */
132 int *join_crossing[TABLE_N_AXES];
135 static struct render_page *render_page_create (const struct render_params *,
138 struct render_page *render_page_ref (const struct render_page *page_);
139 static void render_page_unref (struct render_page *);
141 /* Returns the offset in struct render_page's cp[axis] array of the rule with
142 index RULE_IDX. That is, if RULE_IDX is 0, then the offset is that of the
143 leftmost or topmost rule; if RULE_IDX is 1, then the offset is that of the
144 next rule to the right (or below); and so on. */
146 rule_ofs (int rule_idx)
151 /* Returns the offset in struct render_page's cp[axis] array of the rule with
152 index RULE_IDX_R, which counts from the right side (or bottom) of the page
153 left (or up), according to whether AXIS is H or V, respectively. That is,
154 if RULE_IDX_R is 0, then the offset is that of the rightmost or bottommost
155 rule; if RULE_IDX is 1, then the offset is that of the next rule to the left
156 (or above); and so on. */
158 rule_ofs_r (const struct render_page *page, int axis, int rule_idx_r)
160 return (page->n[axis] - rule_idx_r) * 2;
163 /* Returns the offset in struct render_page's cp[axis] array of the cell with
164 index CELL_IDX. That is, if CELL_IDX is 0, then the offset is that of the
165 leftmost or topmost cell; if CELL_IDX is 1, then the offset is that of the
166 next cell to the right (or below); and so on. */
168 cell_ofs (int cell_idx)
170 return cell_idx * 2 + 1;
173 /* Returns the width of PAGE along AXIS from OFS0 to OFS1, exclusive. */
175 axis_width (const struct render_page *page, int axis, int ofs0, int ofs1)
177 return page->cp[axis][ofs1] - page->cp[axis][ofs0];
180 /* Returns the width of the headers in PAGE along AXIS. */
182 headers_width (const struct render_page *page, int axis)
184 int h0 = page->h[axis][0];
185 int w0 = axis_width (page, axis, rule_ofs (0), cell_ofs (h0));
186 int n = page->n[axis];
187 int h1 = page->h[axis][1];
188 int w1 = axis_width (page, axis, rule_ofs_r (page, axis, h1), cell_ofs (n));
192 /* Returns the width of cell X along AXIS in PAGE. */
194 cell_width (const struct render_page *page, int axis, int x)
196 return axis_width (page, axis, cell_ofs (x), cell_ofs (x) + 1);
199 /* Returns the width of rule X along AXIS in PAGE. */
201 rule_width (const struct render_page *page, int axis, int x)
203 return axis_width (page, axis, rule_ofs (x), rule_ofs (x) + 1);
206 /* Returns the width of rule X along AXIS in PAGE. */
208 rule_width_r (const struct render_page *page, int axis, int x)
210 int ofs = rule_ofs_r (page, axis, x);
211 return axis_width (page, axis, ofs, ofs + 1);
214 /* Returns the width of cells X0 through X1, exclusive, along AXIS in PAGE. */
216 joined_width (const struct render_page *page, int axis, int x0, int x1)
218 return axis_width (page, axis, cell_ofs (x0), cell_ofs (x1) - 1);
221 /* Returns the width of the widest cell, excluding headers, along AXIS in
224 max_cell_width (const struct render_page *page, int axis)
226 int n = page->n[axis];
227 int x0 = page->h[axis][0];
228 int x1 = n - page->h[axis][1];
232 for (x = x0; x < x1; x++)
234 int w = cell_width (page, axis, x);
241 /* A cell that doesn't completely fit on the render_page. */
242 struct render_overflow
244 struct hmap_node node; /* In render_page's 'overflows' hmap. */
246 /* Occupied region of page.
248 d[H][0] is the leftmost column.
249 d[H][1] is the rightmost column, plus 1.
250 d[V][0] is the top row.
251 d[V][1] is the bottom row, plus 1.
253 The cell in its original table might occupy a larger region. This
254 member reflects the size of the cell in the current render_page, after
255 trimming off any rows or columns due to page-breaking. */
258 /* The space that has been trimmed off the cell:
260 overflow[H][0]: space trimmed off its left side.
261 overflow[H][1]: space trimmed off its right side.
262 overflow[V][0]: space trimmed off its top.
263 overflow[V][1]: space trimmed off its bottom.
265 During rendering, this information is used to position the rendered
266 portion of the cell within the available space.
268 When a cell is rendered, sometimes it is permitted to spill over into
269 space that is ordinarily reserved for rules. Either way, this space is
270 still included in overflow values.
272 Suppose, for example, that a cell that joins 2 columns has a width of 60
273 pixels and content "abcdef", that the 2 columns that it joins have
274 widths of 20 and 30 pixels, respectively, and that therefore the rule
275 between the two joined columns has a width of 10 (20 + 10 + 30 = 60).
276 It might render like this, if each character is 10x10, and showing a few
277 extra table cells for context:
285 If this render_page is broken at the rule that separates "gh" from
286 "ijk", then the page that contains the left side of the "abcdef" cell
287 will have overflow[H][1] of 10 + 30 = 40 for its portion of the cell,
288 and the page that contains the right side of the cell will have
289 overflow[H][0] of 20 + 10 = 30. The two resulting pages would look like
307 int overflow[TABLE_N_AXES][2];
310 /* Returns a hash value for (,Y). */
312 hash_cell (int x, int y)
314 return hash_int (x + (y << 16), 0);
317 /* Searches PAGE's set of render_overflow for one whose top-left cell is
318 (X,Y). Returns it, if there is one, otherwise a null pointer. */
319 static const struct render_overflow *
320 find_overflow (const struct render_page *page, int x, int y)
322 if (!hmap_is_empty (&page->overflows))
324 const struct render_overflow *of;
326 HMAP_FOR_EACH_WITH_HASH (of, struct render_overflow, node,
327 hash_cell (x, y), &page->overflows)
328 if (x == of->d[H] && y == of->d[V])
335 /* Row or column dimensions. Used to figure the size of a table in
336 render_page_create() and discarded after that. */
339 /* Width without considering rows (or columns) that span more than one (or
343 /* Width taking spanned rows (or columns) into consideration. */
347 /* Modifies the 'width' members of the N elements of ROWS so that their sum,
348 when added to rule widths RULES[1] through RULES[N - 1] inclusive, is at
351 distribute_spanned_width (int width,
352 struct render_row *rows, const int *rules, int n)
354 /* Sum up the unspanned widths of the N rows for use as weights. */
355 int total_unspanned = 0;
356 for (int x = 0; x < n; x++)
357 total_unspanned += rows[x].unspanned;
358 for (int x = 0; x < n - 1; x++)
359 total_unspanned += rules[x + 1];
360 if (total_unspanned >= width)
363 /* The algorithm used here is based on the following description from HTML 4:
365 For cells that span multiple columns, a simple approach consists of
366 apportioning the min/max widths evenly to each of the constituent
367 columns. A slightly more complex approach is to use the min/max
368 widths of unspanned cells to weight how spanned widths are
369 apportioned. Experiments suggest that a blend of the two approaches
370 gives good results for a wide range of tables.
372 We blend the two approaches half-and-half, except that we cannot use the
373 unspanned weights when 'total_unspanned' is 0 (because that would cause a
376 The calculation we want to do is this:
379 w1 = width * (column's unspanned width) / (total unspanned width)
380 (column's width) = (w0 + w1) / 2
382 We implement it as a precise calculation in integers by multiplying w0 and
383 w1 by the common denominator of all three calculations (d), dividing that
384 out in the column width calculation, and then keeping the remainder for
387 (We actually compute the unspanned width of a column as twice the
388 unspanned width, plus the width of the rule on the left, plus the width of
389 the rule on the right. That way each rule contributes to both the cell on
390 its left and on its right.)
392 long long int d0 = n;
393 long long int d1 = 2LL * MAX (total_unspanned, 1);
394 long long int d = d0 * d1;
395 if (total_unspanned > 0)
397 long long int w = d / 2;
398 for (int x = 0; x < n; x++)
401 if (total_unspanned > 0)
403 long long int unspanned = rows[x].unspanned * 2LL;
405 unspanned += rules[x + 1];
407 unspanned += rules[x];
408 w += width * unspanned * d0;
411 rows[x].width = MAX (rows[x].width, w / d);
412 w -= rows[x].width * d;
416 /* Initializes PAGE->cp[AXIS] from the row widths in ROWS and the rule widths
419 accumulate_row_widths (const struct render_page *page, enum table_axis axis,
420 const struct render_row *rows, const int *rules)
422 int n = page->n[axis];
428 for (z = 0; z < n; z++)
430 cp[1] = cp[0] + rules[z];
431 cp[2] = cp[1] + rows[z].width;
434 cp[1] = cp[0] + rules[n];
437 /* Returns the sum of widths of the N ROWS and N+1 RULES. */
439 calculate_table_width (int n, const struct render_row *rows, int *rules)
445 for (x = 0; x < n; x++)
446 width += rows[x].width;
447 for (x = 0; x <= n; x++)
453 /* Rendering utility functions. */
455 /* Returns the line style to use for drawing a rule of the given TYPE. */
456 static enum render_line_style
457 rule_to_render_type (unsigned char type)
462 return RENDER_LINE_NONE;
464 return RENDER_LINE_SINGLE;
466 return RENDER_LINE_DASHED;
468 return RENDER_LINE_THICK;
470 return RENDER_LINE_THIN;
472 return RENDER_LINE_DOUBLE;
478 /* Returns the width of the rule in TABLE that is at offset Z along axis A, if
479 rendered with PARAMS. */
481 measure_rule (const struct render_params *params, const struct table *table,
482 enum table_axis a, int z)
484 enum table_axis b = !a;
488 /* Determine all types of rules that are present, as a bitmap in 'rules'
489 where rule type 't' is present if bit 2**t is set. */
492 for (d[b] = 0; d[b] < table->n[b]; d[b]++)
493 rules |= 1u << table_get_rule (table, a, d[H], d[V]);
495 /* Turn off TAL_NONE because it has width 0 and we needn't bother. However,
496 if the device doesn't support margins, make sure that there is at least a
497 small gap between cells (but we don't need any at the left or right edge
499 if (rules & (1u << TAL_NONE))
501 rules &= ~(1u << TAL_NONE);
502 if (z > 0 && z < table->n[a] && !params->supports_margins && a == H)
503 rules |= 1u << TAL_SOLID;
506 /* Calculate maximum width of the rules that are present. */
508 for (size_t i = 0; i < N_LINES; i++)
509 if (rules & (1u << i))
510 width = MAX (width, params->line_widths[a][rule_to_render_type (i)]);
514 /* Allocates and returns a new render_page using PARAMS and TABLE. Allocates
515 space for all of the members of the new page, but the caller must initialize
516 the 'cp' member itself. */
517 static struct render_page *
518 render_page_allocate (const struct render_params *params,
521 struct render_page *page;
524 page = xmalloc (sizeof *page);
525 page->params = params;
528 page->n[H] = table->n[H];
529 page->n[V] = table->n[V];
530 page->h[H][0] = table->h[H][0];
531 page->h[H][1] = table->h[H][1];
532 page->h[V][0] = table->h[V][0];
533 page->h[V][1] = table->h[V][1];
535 for (i = 0; i < TABLE_N_AXES; i++)
537 page->cp[i] = xmalloc ((2 * page->n[i] + 2) * sizeof *page->cp[i]);
538 page->join_crossing[i] = xzalloc ((page->n[i] + 1) * sizeof *page->join_crossing[i]);
541 hmap_init (&page->overflows);
542 memset (page->is_edge_cutoff, 0, sizeof page->is_edge_cutoff);
547 /* Allocates and returns a new render_page for PARAMS and TABLE, initializing
548 cp[H] in the new page from ROWS and RULES. The caller must still initialize
550 static struct render_page *
551 create_page_with_exact_widths (const struct render_params *params,
553 const struct render_row *rows, int *rules)
555 struct render_page *page = render_page_allocate (params, table);
556 accumulate_row_widths (page, H, rows, rules);
560 /* Allocates and returns a new render_page for PARAMS and TABLE.
562 Initializes cp[H] in the new page by setting the width of each row 'i' to
563 somewhere between the minimum cell width ROW_MIN[i].width and the maximum
564 ROW_MAX[i].width. Sets the width of rules to those in RULES.
566 W_MIN is the sum of ROWS_MIN[].width.
568 W_MAX is the sum of ROWS_MAX[].width.
570 The caller must still initialize cp[V]. */
571 static struct render_page *
572 create_page_with_interpolated_widths (const struct render_params *params,
574 const struct render_row *rows_min,
575 const struct render_row *rows_max,
576 int w_min, int w_max, const int *rules)
578 const int n = table->n[H];
579 const long long int avail = params->size[H] - w_min;
580 const long long int wanted = w_max - w_min;
584 struct render_page *page = render_page_allocate (params, table);
586 int *cph = page->cp[H];
588 long long int w = wanted / 2;
589 for (int x = 0; x < n; x++)
591 w += avail * (rows_max[x].width - rows_min[x].width);
592 int extra = w / wanted;
595 cph[1] = cph[0] + rules[x];
596 cph[2] = cph[1] + rows_min[x].width + extra;
599 cph[1] = cph[0] + rules[n];
601 assert (page->cp[H][n * 2 + 1] == params->size[H]);
607 set_join_crossings (struct render_page *page, enum table_axis axis,
608 const struct table_cell *cell, int *rules)
612 for (z = cell->d[axis][0] + 1; z <= cell->d[axis][1] - 1; z++)
613 page->join_crossing[axis][z] = rules[z];
616 /* Creates and returns a new render_page for rendering TABLE on a device
619 The new render_page will be suitable for rendering on a device whose page
620 size is PARAMS->size, but the caller is responsible for actually breaking it
621 up to fit on such a device, using the render_break abstraction. */
622 static struct render_page *
623 render_page_create (const struct render_params *params, struct table *table)
625 struct render_page *page;
627 struct render_row *columns[2];
628 struct render_row *rows;
630 int *rules[TABLE_N_AXES];
634 enum table_axis axis;
636 nc = table_nc (table);
637 nr = table_nr (table);
639 /* Figure out rule widths. */
640 for (axis = 0; axis < TABLE_N_AXES; axis++)
642 int n = table->n[axis] + 1;
645 rules[axis] = xnmalloc (n, sizeof *rules);
646 for (z = 0; z < n; z++)
647 rules[axis][z] = measure_rule (params, table, axis, z);
650 /* Calculate minimum and maximum widths of cells that do not
651 span multiple columns. */
652 for (i = 0; i < 2; i++)
653 columns[i] = xzalloc (nc * sizeof *columns[i]);
654 for (y = 0; y < nr; y++)
655 for (x = 0; x < nc; )
657 struct table_cell cell;
659 table_get_cell (table, x, y, &cell);
660 if (y == cell.d[V][0])
662 if (table_cell_colspan (&cell) == 1)
667 params->measure_cell_width (params->aux, &cell,
669 for (i = 0; i < 2; i++)
670 if (columns[i][x].unspanned < w[i])
671 columns[i][x].unspanned = w[i];
675 table_cell_free (&cell);
678 /* Distribute widths of spanned columns. */
679 for (i = 0; i < 2; i++)
680 for (x = 0; x < nc; x++)
681 columns[i][x].width = columns[i][x].unspanned;
682 for (y = 0; y < nr; y++)
683 for (x = 0; x < nc; )
685 struct table_cell cell;
687 table_get_cell (table, x, y, &cell);
688 if (y == cell.d[V][0] && table_cell_colspan (&cell) > 1)
692 params->measure_cell_width (params->aux, &cell, &w[MIN], &w[MAX]);
693 for (i = 0; i < 2; i++)
694 distribute_spanned_width (w[i], &columns[i][cell.d[H][0]],
695 rules[H], table_cell_colspan (&cell));
698 table_cell_free (&cell);
701 /* In pathological cases, spans can cause the minimum width of a column to
702 exceed the maximum width. This bollixes our interpolation algorithm
703 later, so fix it up. */
704 for (i = 0; i < nc; i++)
705 if (columns[MIN][i].width > columns[MAX][i].width)
706 columns[MAX][i].width = columns[MIN][i].width;
708 /* Decide final column widths. */
709 for (i = 0; i < 2; i++)
710 table_widths[i] = calculate_table_width (table_nc (table),
711 columns[i], rules[H]);
712 if (table_widths[MAX] <= params->size[H])
714 /* Fits even with maximum widths. Use them. */
715 page = create_page_with_exact_widths (params, table, columns[MAX],
718 else if (table_widths[MIN] <= params->size[H])
720 /* Fits with minimum widths, so distribute the leftover space. */
721 page = create_page_with_interpolated_widths (
722 params, table, columns[MIN], columns[MAX],
723 table_widths[MIN], table_widths[MAX], rules[H]);
727 /* Doesn't fit even with minimum widths. Assign minimums for now, and
728 later we can break it horizontally into multiple pages. */
729 page = create_page_with_exact_widths (params, table, columns[MIN],
733 /* Calculate heights of cells that do not span multiple rows. */
734 rows = xzalloc (nr * sizeof *rows);
735 for (y = 0; y < nr; y++)
737 for (x = 0; x < nc; )
739 struct render_row *r = &rows[y];
740 struct table_cell cell;
742 table_get_cell (table, x, y, &cell);
743 if (y == cell.d[V][0])
745 if (table_cell_rowspan (&cell) == 1)
747 int w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
748 int h = params->measure_cell_height (params->aux, &cell, w);
749 if (h > r->unspanned)
750 r->unspanned = r->width = h;
753 set_join_crossings (page, V, &cell, rules[V]);
755 if (table_cell_colspan (&cell) > 1)
756 set_join_crossings (page, H, &cell, rules[H]);
759 table_cell_free (&cell);
762 for (i = 0; i < 2; i++)
765 /* Distribute heights of spanned rows. */
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_rowspan (&cell) > 1)
774 int w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
775 int h = params->measure_cell_height (params->aux, &cell, w);
776 distribute_spanned_width (h, &rows[cell.d[V][0]], rules[V],
777 table_cell_rowspan (&cell));
780 table_cell_free (&cell);
783 /* Decide final row heights. */
784 accumulate_row_widths (page, V, rows, rules[V]);
787 /* Measure headers. If they are "too big", get rid of them. */
788 for (axis = 0; axis < TABLE_N_AXES; axis++)
790 int hw = headers_width (page, axis);
791 if (hw * 2 >= page->params->size[axis]
792 || hw + max_cell_width (page, axis) > page->params->size[axis])
794 page->table = table_unshare (page->table);
795 page->table->h[axis][0] = page->table->h[axis][1] = 0;
796 page->h[axis][0] = page->h[axis][1] = 0;
806 /* Increases PAGE's reference count. */
808 render_page_ref (const struct render_page *page_)
810 struct render_page *page = CONST_CAST (struct render_page *, page_);
815 /* Decreases PAGE's reference count and destroys PAGE if this causes the
816 reference count to fall to zero. */
818 render_page_unref (struct render_page *page)
820 if (page != NULL && --page->ref_cnt == 0)
823 struct render_overflow *overflow, *next;
825 HMAP_FOR_EACH_SAFE (overflow, next, struct render_overflow, node,
828 hmap_destroy (&page->overflows);
830 table_unref (page->table);
832 for (i = 0; i < TABLE_N_AXES; ++i)
834 free (page->join_crossing[i]);
842 /* Returns the size of PAGE along AXIS. (This might be larger than the page
843 size specified in the parameters passed to render_page_create(). Use a
844 render_break to break up a render_page into page-sized chunks.) */
846 render_page_get_size (const struct render_page *page, enum table_axis axis)
848 return page->cp[axis][page->n[axis] * 2 + 1];
852 render_page_get_best_breakpoint (const struct render_page *page, int height)
856 /* If there's no room for at least the top row and the rules above and below
857 it, don't include any of the table. */
858 if (page->cp[V][3] > height)
861 /* Otherwise include as many rows and rules as we can. */
862 for (y = 5; y <= 2 * page->n[V] + 1; y += 2)
863 if (page->cp[V][y] > height)
864 return page->cp[V][y - 2];
868 /* Drawing render_pages. */
870 static inline enum render_line_style
871 get_rule (const struct render_page *page, enum table_axis axis,
872 const int d[TABLE_N_AXES])
874 return rule_to_render_type (table_get_rule (page->table,
875 axis, d[H] / 2, d[V] / 2));
885 render_direction_rtl (void)
887 /* TRANSLATORS: Do not translate this string. If the script of your language
888 reads from right to left (eg Persian, Arabic, Hebrew etc), then replace
889 this string with "output-direction-rtl". Otherwise either leave it
890 untranslated or copy it verbatim. */
891 const char *dir = _("output-direction-ltr");
892 if ( 0 == strcmp ("output-direction-rtl", dir))
895 if ( 0 != strcmp ("output-direction-ltr", dir))
896 fprintf (stderr, "This localisation has been incorrectly translated. Complain to the translator.\n");
902 render_rule (const struct render_page *page, const int ofs[TABLE_N_AXES],
903 const int d[TABLE_N_AXES])
905 enum render_line_style styles[TABLE_N_AXES][2];
908 for (a = 0; a < TABLE_N_AXES; a++)
910 enum table_axis b = !a;
912 styles[a][0] = styles[a][1] = RENDER_LINE_NONE;
915 || (page->is_edge_cutoff[a][0] && d[a] == 0)
916 || (page->is_edge_cutoff[a][1] && d[a] == page->n[a] * 2))
927 styles[a][0] = get_rule (page, a, e);
930 if (d[b] / 2 < page->table->n[b])
931 styles[a][1] = get_rule (page, a, d);
934 styles[a][0] = styles[a][1] = get_rule (page, a, d);
937 if (styles[H][0] != RENDER_LINE_NONE || styles[H][1] != RENDER_LINE_NONE
938 || styles[V][0] != RENDER_LINE_NONE || styles[V][1] != RENDER_LINE_NONE)
940 int bb[TABLE_N_AXES][2];
942 bb[H][0] = ofs[H] + page->cp[H][d[H]];
943 bb[H][1] = ofs[H] + page->cp[H][d[H] + 1];
944 if (render_direction_rtl ())
947 bb[H][0] = render_page_get_size (page, H) - bb[H][1];
948 bb[H][1] = render_page_get_size (page, H) - temp;
950 bb[V][0] = ofs[V] + page->cp[V][d[V]];
951 bb[V][1] = ofs[V] + page->cp[V][d[V] + 1];
952 page->params->draw_line (page->params->aux, bb, styles);
957 render_cell (const struct render_page *page, const int ofs[TABLE_N_AXES],
958 const struct table_cell *cell)
960 const struct render_overflow *of;
961 int bb[TABLE_N_AXES][2];
962 int clip[TABLE_N_AXES][2];
964 bb[H][0] = clip[H][0] = ofs[H] + page->cp[H][cell->d[H][0] * 2 + 1];
965 bb[H][1] = clip[H][1] = ofs[H] + page->cp[H][cell->d[H][1] * 2];
966 if (render_direction_rtl ())
969 bb[H][0] = clip[H][0] = render_page_get_size (page, H) - bb[H][1];
970 bb[H][1] = clip[H][1] = render_page_get_size (page, H) - temp;
972 bb[V][0] = clip[V][0] = ofs[V] + page->cp[V][cell->d[V][0] * 2 + 1];
973 bb[V][1] = clip[V][1] = ofs[V] + page->cp[V][cell->d[V][1] * 2];
975 int valign = (cell->n_contents
976 ? cell->contents->options & TAB_VALIGN
978 if (valign != TAB_TOP)
980 int height = page->params->measure_cell_height (
981 page->params->aux, cell, bb[H][1] - bb[H][0]);
982 int extra = bb[V][1] - bb[V][0] - height;
985 if (valign == TAB_MIDDLE)
991 of = find_overflow (page, cell->d[H][0], cell->d[V][0]);
994 enum table_axis axis;
996 for (axis = 0; axis < TABLE_N_AXES; axis++)
998 if (of->overflow[axis][0])
1000 bb[axis][0] -= of->overflow[axis][0];
1001 if (cell->d[axis][0] == 0 && !page->is_edge_cutoff[axis][0])
1002 clip[axis][0] = ofs[axis] + page->cp[axis][cell->d[axis][0] * 2];
1004 if (of->overflow[axis][1])
1006 bb[axis][1] += of->overflow[axis][1];
1007 if (cell->d[axis][1] == page->n[axis] && !page->is_edge_cutoff[axis][1])
1008 clip[axis][1] = ofs[axis] + page->cp[axis][cell->d[axis][1] * 2 + 1];
1013 int spill[TABLE_N_AXES][2];
1014 for (enum table_axis axis = 0; axis < TABLE_N_AXES; axis++)
1016 spill[axis][0] = rule_width (page, axis, cell->d[axis][0]) / 2;
1017 spill[axis][1] = rule_width (page, axis, cell->d[axis][1]) / 2;
1020 page->params->draw_cell (page->params->aux, cell, bb, spill, clip);
1023 /* Draws the cells of PAGE indicated in BB. */
1025 render_page_draw_cells (const struct render_page *page,
1026 int ofs[TABLE_N_AXES], int bb[TABLE_N_AXES][2])
1028 for (int y = bb[V][0]; y < bb[V][1]; y++)
1029 for (int x = bb[H][0]; x < bb[H][1]; )
1030 if (!is_rule (x) && !is_rule (y))
1032 struct table_cell cell;
1034 table_get_cell (page->table, x / 2, y / 2, &cell);
1035 if (y / 2 == bb[V][0] / 2 || y / 2 == cell.d[V][0])
1036 render_cell (page, ofs, &cell);
1037 x = rule_ofs (cell.d[H][1]);
1038 table_cell_free (&cell);
1043 for (int y = bb[V][0]; y < bb[V][1]; y++)
1044 for (int x = bb[H][0]; x < bb[H][1]; x++)
1045 if (is_rule (x) || is_rule (y))
1047 int d[TABLE_N_AXES];
1050 render_rule (page, ofs, d);
1054 /* Renders PAGE, by calling the 'draw_line' and 'draw_cell' functions from the
1055 render_params provided to render_page_create(). */
1057 render_page_draw (const struct render_page *page, int ofs[TABLE_N_AXES])
1059 int bb[TABLE_N_AXES][2];
1062 bb[H][1] = page->n[H] * 2 + 1;
1064 bb[V][1] = page->n[V] * 2 + 1;
1066 render_page_draw_cells (page, ofs, bb);
1069 /* Returns the greatest value i, 0 <= i < n, such that cp[i] <= x0. */
1071 get_clip_min_extent (int x0, const int cp[], int n)
1073 int low, high, best;
1080 int middle = low + (high - low) / 2;
1082 if (cp[middle] <= x0)
1094 /* Returns the least value i, 0 <= i < n, such that cp[i] >= x1. */
1096 get_clip_max_extent (int x1, const int cp[], int n)
1098 int low, high, best;
1105 int middle = low + (high - low) / 2;
1107 if (cp[middle] >= x1)
1108 best = high = middle;
1113 while (best > 0 && cp[best - 1] == cp[best])
1119 /* Renders the cells of PAGE that intersect (X,Y)-(X+W,Y+H), by calling the
1120 'draw_line' and 'draw_cell' functions from the render_params provided to
1121 render_page_create(). */
1123 render_page_draw_region (const struct render_page *page,
1124 int ofs[TABLE_N_AXES], int clip[TABLE_N_AXES][2])
1126 int bb[TABLE_N_AXES][2];
1128 bb[H][0] = get_clip_min_extent (clip[H][0], page->cp[H], page->n[H] * 2 + 1);
1129 bb[H][1] = get_clip_max_extent (clip[H][1], page->cp[H], page->n[H] * 2 + 1);
1130 bb[V][0] = get_clip_min_extent (clip[V][0], page->cp[V], page->n[V] * 2 + 1);
1131 bb[V][1] = get_clip_max_extent (clip[V][1], page->cp[V], page->n[V] * 2 + 1);
1133 render_page_draw_cells (page, ofs, bb);
1136 /* Breaking up tables to fit on a page. */
1138 /* An iterator for breaking render_pages into smaller chunks. */
1141 struct render_page *page; /* Page being broken up. */
1142 enum table_axis axis; /* Axis along which 'page' is being broken. */
1143 int z; /* Next cell along 'axis'. */
1144 int pixel; /* Pixel offset within cell 'z' (usually 0). */
1145 int hw; /* Width of headers of 'page' along 'axis'. */
1148 static int needed_size (const struct render_break *, int cell);
1149 static bool cell_is_breakable (const struct render_break *, int cell);
1150 static struct render_page *render_page_select (const struct render_page *,
1155 /* Initializes render_break B for breaking PAGE along AXIS.
1156 Takes ownership of PAGE. */
1158 render_break_init (struct render_break *b, struct render_page *page,
1159 enum table_axis axis)
1163 b->z = page->h[axis][0];
1165 b->hw = headers_width (page, axis);
1168 /* Initializes B as a render_break structure for which
1169 render_break_has_next() always returns false. */
1171 render_break_init_empty (struct render_break *b)
1174 b->axis = TABLE_HORZ;
1180 /* Frees B and unrefs the render_page that it owns. */
1182 render_break_destroy (struct render_break *b)
1186 render_page_unref (b->page);
1191 /* Returns true if B still has cells that are yet to be returned,
1192 false if all of B's page has been processed. */
1194 render_break_has_next (const struct render_break *b)
1196 const struct render_page *page = b->page;
1197 enum table_axis axis = b->axis;
1199 return page != NULL && b->z < page->n[axis] - page->h[axis][1];
1202 /* Returns a new render_page that is up to SIZE pixels wide along B's axis.
1203 Returns a null pointer if B has already been completely broken up, or if
1204 SIZE is too small to reasonably render any cells. The latter will never
1205 happen if SIZE is at least as large as the page size passed to
1206 render_page_create() along B's axis. */
1207 static struct render_page *
1208 render_break_next (struct render_break *b, int size)
1210 const struct render_page *page = b->page;
1211 enum table_axis axis = b->axis;
1212 struct render_page *subpage;
1215 if (!render_break_has_next (b))
1219 for (z = b->z; z < page->n[axis] - page->h[axis][1]; z++)
1221 int needed = needed_size (b, z + 1);
1224 if (cell_is_breakable (b, z))
1226 /* If there is no right header and we render a partial cell on
1227 the right side of the body, then we omit the rightmost rule of
1228 the body. Otherwise the rendering is deceptive because it
1229 looks like the whole cell is present instead of a partial
1232 This is similar to code for the left side in needed_size(). */
1233 int rule_allowance = (page->h[axis][1]
1235 : rule_width (page, axis, z));
1237 /* The amount that, if we added cell 'z', the rendering would
1238 overfill the allocated 'size'. */
1239 int overhang = needed - size - rule_allowance;
1241 /* The width of cell 'z'. */
1242 int cell_size = cell_width (page, axis, z);
1244 /* The amount trimmed off the left side of 'z',
1245 and the amount left to render. */
1246 int cell_ofs = z == b->z ? b->pixel : 0;
1247 int cell_left = cell_size - cell_ofs;
1249 /* A small but visible width. */
1250 int em = page->params->font_size[axis];
1252 /* If some of the cell remains to render,
1253 and there would still be some of the cell left afterward,
1254 then partially render that much of the cell. */
1255 pixel = (cell_left && cell_left > overhang
1256 ? cell_left - overhang + cell_ofs
1259 /* If there would be only a tiny amount of the cell left after
1260 rendering it partially, reduce the amount rendered slightly
1261 to make the output look a little better. */
1262 if (pixel + em > cell_size)
1263 pixel = MAX (pixel - em, 0);
1265 /* If we're breaking vertically, then consider whether the cells
1266 being broken have a better internal breakpoint than the exact
1267 number of pixels available, which might look bad e.g. because
1268 it breaks in the middle of a line of text. */
1269 if (axis == TABLE_VERT && page->params->adjust_break)
1273 for (x = 0; x < page->n[H]; )
1275 struct table_cell cell;
1279 table_get_cell (page->table, x, z, &cell);
1280 w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
1281 better_pixel = page->params->adjust_break (
1282 page->params->aux, &cell, w, pixel);
1284 table_cell_free (&cell);
1286 if (better_pixel < pixel)
1288 if (better_pixel > (z == b->z ? b->pixel : 0))
1290 pixel = better_pixel;
1293 else if (better_pixel == 0 && z != b->z)
1306 if (z == b->z && !pixel)
1309 subpage = render_page_select (page, axis, b->z, b->pixel,
1311 pixel ? cell_width (page, axis, z) - pixel
1318 /* Returns the width that would be required along B's axis to render a page
1319 from B's current position up to but not including CELL. */
1321 needed_size (const struct render_break *b, int cell)
1323 const struct render_page *page = b->page;
1324 enum table_axis axis = b->axis;
1327 /* Width of left header not including its rightmost rule. */
1328 size = axis_width (page, axis, 0, rule_ofs (page->h[axis][0]));
1330 /* If we have a pixel offset and there is no left header, then we omit the
1331 leftmost rule of the body. Otherwise the rendering is deceptive because
1332 it looks like the whole cell is present instead of a partial cell.
1334 Otherwise (if there are headers) we will be merging two rules: the
1335 rightmost rule in the header and the leftmost rule in the body. We assume
1336 that the width of a merged rule is the larger of the widths of either rule
1338 if (b->pixel == 0 || page->h[axis][0])
1339 size += MAX (rule_width (page, axis, page->h[axis][0]),
1340 rule_width (page, axis, b->z));
1342 /* Width of body, minus any pixel offset in the leftmost cell. */
1343 size += joined_width (page, axis, b->z, cell) - b->pixel;
1345 /* Width of rightmost rule in body merged with leftmost rule in headers. */
1346 size += MAX (rule_width_r (page, axis, page->h[axis][1]),
1347 rule_width (page, axis, cell));
1349 /* Width of right header not including its leftmost rule. */
1350 size += axis_width (page, axis, rule_ofs_r (page, axis, page->h[axis][1]),
1351 rule_ofs_r (page, axis, 0));
1353 /* Join crossing. */
1354 if (page->h[axis][0] && page->h[axis][1])
1355 size += page->join_crossing[axis][b->z];
1360 /* Returns true if CELL along B's axis may be broken across a page boundary.
1362 This is just a heuristic. Breaking cells across page boundaries can save
1363 space, but it looks ugly. */
1365 cell_is_breakable (const struct render_break *b, int cell)
1367 const struct render_page *page = b->page;
1368 enum table_axis axis = b->axis;
1370 return cell_width (page, axis, cell) >= page->params->min_break[axis];
1377 const struct render_params *params;
1379 struct render_page **pages;
1380 size_t n_pages, allocated_pages;
1383 struct render_break x_break;
1384 struct render_break y_break;
1387 static const struct render_page *
1388 render_pager_add_table (struct render_pager *p, struct table *table)
1390 struct render_page *page;
1392 if (p->n_pages >= p->allocated_pages)
1393 p->pages = x2nrealloc (p->pages, &p->allocated_pages, sizeof *p->pages);
1394 page = p->pages[p->n_pages++] = render_page_create (p->params, table);
1399 render_pager_start_page (struct render_pager *p)
1401 render_break_init (&p->x_break, render_page_ref (p->pages[p->cur_page++]),
1403 render_break_init_empty (&p->y_break);
1407 add_footnote_page (struct render_pager *p, const struct table_item *item)
1409 const struct footnote **f;
1410 size_t n_footnotes = table_collect_footnotes (item, &f);
1414 struct tab_table *t = tab_create (2, n_footnotes);
1416 for (size_t i = 0; i < n_footnotes; i++)
1419 tab_text_format (t, 0, i, TAB_LEFT, "%s.", f[i]->marker);
1420 tab_text (t, 1, i, TAB_LEFT, f[i]->content);
1422 render_pager_add_table (p, &t->table);
1428 add_text_page (struct render_pager *p, const struct table_item_text *t)
1433 struct tab_table *tab = tab_create (1, 1);
1434 tab_text (tab, 0, 0, TAB_LEFT, t->content);
1435 for (size_t i = 0; i < t->n_footnotes; i++)
1436 tab_add_footnote (tab, 0, 0, t->footnotes[i]);
1437 render_pager_add_table (p, &tab->table);
1440 /* Creates and returns a new render_pager for rendering TABLE_ITEM on the
1441 device with the given PARAMS. */
1442 struct render_pager *
1443 render_pager_create (const struct render_params *params,
1444 const struct table_item *table_item)
1446 struct render_pager *p;
1448 p = xzalloc (sizeof *p);
1452 add_text_page (p, table_item_get_title (table_item));
1455 render_pager_add_table (p, table_ref (table_item_get_table (table_item)));
1458 add_text_page (p, table_item_get_caption (table_item));
1461 add_footnote_page (p, table_item);
1463 render_pager_start_page (p);
1470 render_pager_destroy (struct render_pager *p)
1476 render_break_destroy (&p->x_break);
1477 render_break_destroy (&p->y_break);
1478 for (i = 0; i < p->n_pages; i++)
1479 render_page_unref (p->pages[i]);
1485 /* Returns true if P has content remaining to render, false if rendering is
1488 render_pager_has_next (const struct render_pager *p_)
1490 struct render_pager *p = CONST_CAST (struct render_pager *, p_);
1492 while (!render_break_has_next (&p->y_break))
1494 render_break_destroy (&p->y_break);
1495 if (!render_break_has_next (&p->x_break))
1497 render_break_destroy (&p->x_break);
1498 if (p->cur_page >= p->n_pages)
1500 render_break_init_empty (&p->x_break);
1501 render_break_init_empty (&p->y_break);
1504 render_pager_start_page (p);
1507 render_break_init (&p->y_break,
1508 render_break_next (&p->x_break, p->params->size[H]), V);
1513 /* Draws a chunk of content from P to fit in a space that has vertical size
1514 SPACE and the horizontal size specified in the render_params passed to
1515 render_page_create(). Returns the amount of space actually used by the
1516 rendered chunk, which will be 0 if SPACE is too small to render anything or
1517 if no content remains (use render_pager_has_next() to distinguish these
1520 render_pager_draw_next (struct render_pager *p, int space)
1522 int ofs[TABLE_N_AXES] = { 0, 0 };
1523 size_t start_page = SIZE_MAX;
1525 while (render_pager_has_next (p))
1527 struct render_page *page;
1529 if (start_page == p->cur_page)
1531 start_page = p->cur_page;
1533 page = render_break_next (&p->y_break, space - ofs[V]);
1537 render_page_draw (page, ofs);
1538 ofs[V] += render_page_get_size (page, V);
1539 render_page_unref (page);
1544 /* Draws all of P's content. */
1546 render_pager_draw (const struct render_pager *p)
1548 render_pager_draw_region (p, 0, 0, INT_MAX, INT_MAX);
1551 /* Draws the region of P's content that lies in the region (X,Y)-(X+W,Y+H).
1552 Some extra content might be drawn; the device should perform clipping as
1555 render_pager_draw_region (const struct render_pager *p,
1556 int x, int y, int w, int h)
1558 int ofs[TABLE_N_AXES] = { 0, 0 };
1559 int clip[TABLE_N_AXES][2];
1564 for (i = 0; i < p->n_pages; i++)
1566 const struct render_page *page = p->pages[i];
1567 int size = render_page_get_size (page, V);
1569 clip[V][0] = MAX (y, ofs[V]) - ofs[V];
1570 clip[V][1] = MIN (y + h, ofs[V] + size) - ofs[V];
1571 if (clip[V][1] > clip[V][0])
1572 render_page_draw_region (page, ofs, clip);
1578 /* Returns the size of P's content along AXIS; i.e. the content's width if AXIS
1579 is TABLE_HORZ and its length if AXIS is TABLE_VERT. */
1581 render_pager_get_size (const struct render_pager *p, enum table_axis axis)
1586 for (i = 0; i < p->n_pages; i++)
1588 int subsize = render_page_get_size (p->pages[i], axis);
1589 size = axis == H ? MAX (size, subsize) : size + subsize;
1596 render_pager_get_best_breakpoint (const struct render_pager *p, int height)
1601 for (i = 0; i < p->n_pages; i++)
1603 int size = render_page_get_size (p->pages[i], V);
1604 if (y + size >= height)
1605 return render_page_get_best_breakpoint (p->pages[i], height - y) + y;
1612 /* render_page_select() and helpers. */
1614 struct render_page_selection
1616 const struct render_page *page; /* Page whose slice we are selecting. */
1617 struct render_page *subpage; /* New page under construction. */
1618 enum table_axis a; /* Axis of 'page' along which 'subpage' is a slice. */
1619 enum table_axis b; /* The opposite of 'a'. */
1620 int z0; /* First cell along 'a' being selected. */
1621 int z1; /* Last cell being selected, plus 1. */
1622 int p0; /* Number of pixels to trim off left side of z0. */
1623 int p1; /* Number of pixels to trim off right side of z1-1. */
1626 static void cell_to_subpage (struct render_page_selection *,
1627 const struct table_cell *,
1628 int subcell[TABLE_N_AXES]);
1629 static const struct render_overflow *find_overflow_for_cell (
1630 struct render_page_selection *, const struct table_cell *);
1631 static struct render_overflow *insert_overflow (struct render_page_selection *,
1632 const struct table_cell *);
1634 /* Creates and returns a new render_page whose contents are a subregion of
1635 PAGE's contents. The new render_page includes cells Z0 through Z1
1636 (exclusive) along AXIS, plus any headers on AXIS.
1638 If P0 is nonzero, then it is a number of pixels to exclude from the left or
1639 top (according to AXIS) of cell Z0. Similarly, P1 is a number of pixels to
1640 exclude from the right or bottom of cell Z1 - 1. (P0 and P1 are used to
1641 render cells that are too large to fit on a single page.)
1643 The whole of axis !AXIS is included. (The caller may follow up with another
1644 call to render_page_select() to select on !AXIS to select on that axis as
1647 The caller retains ownership of PAGE, which is not modified. */
1648 static struct render_page *
1649 render_page_select (const struct render_page *page, enum table_axis axis,
1650 int z0, int p0, int z1, int p1)
1652 struct render_page_selection s;
1653 enum table_axis a = axis;
1654 enum table_axis b = !a;
1655 struct render_page *subpage;
1656 struct render_overflow *ro;
1662 /* Optimize case where all of PAGE is selected by just incrementing the
1664 if (z0 == page->h[a][0] && p0 == 0
1665 && z1 == page->n[a] - page->h[a][1] && p1 == 0)
1667 struct render_page *page_rw = CONST_CAST (struct render_page *, page);
1672 /* Allocate subpage. */
1673 subpage = render_page_allocate (page->params,
1674 table_select_slice (
1675 table_ref (page->table),
1678 /* An edge is cut off if it was cut off in PAGE or if we're trimming pixels
1679 off that side of the page and there are no headers. */
1680 subpage->is_edge_cutoff[a][0] =
1681 subpage->h[a][0] == 0 && (p0 || (z0 == 0 && page->is_edge_cutoff[a][0]));
1682 subpage->is_edge_cutoff[a][1] =
1683 subpage->h[a][1] == 0 && (p1 || (z1 == page->n[a]
1684 && page->is_edge_cutoff[a][1]));
1685 subpage->is_edge_cutoff[b][0] = page->is_edge_cutoff[b][0];
1686 subpage->is_edge_cutoff[b][1] = page->is_edge_cutoff[b][1];
1688 /* Select join crossings from PAGE into subpage. */
1689 jc = subpage->join_crossing[a];
1690 for (z = 0; z < page->h[a][0]; z++)
1691 *jc++ = page->join_crossing[a][z];
1692 for (z = z0; z <= z1; z++)
1693 *jc++ = page->join_crossing[a][z];
1694 for (z = page->n[a] - page->h[a][1]; z < page->n[a]; z++)
1695 *jc++ = page->join_crossing[a][z];
1696 assert (jc == &subpage->join_crossing[a][subpage->n[a] + 1]);
1698 memcpy (subpage->join_crossing[b], page->join_crossing[b],
1699 (subpage->n[b] + 1) * sizeof **subpage->join_crossing);
1701 /* Select widths from PAGE into subpage. */
1703 dcp = subpage->cp[a];
1705 for (z = 0; z <= rule_ofs (subpage->h[a][0]); z++, dcp++)
1707 if (z == 0 && subpage->is_edge_cutoff[a][0])
1710 dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1712 for (z = cell_ofs (z0); z <= cell_ofs (z1 - 1); z++, dcp++)
1714 dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1715 if (z == cell_ofs (z0))
1718 if (page->h[a][0] && page->h[a][1])
1719 dcp[1] += page->join_crossing[a][z / 2];
1721 if (z == cell_ofs (z1 - 1))
1724 for (z = rule_ofs_r (page, a, subpage->h[a][1]);
1725 z <= rule_ofs_r (page, a, 0); z++, dcp++)
1727 if (z == rule_ofs_r (page, a, 0) && subpage->is_edge_cutoff[a][1])
1730 dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1732 assert (dcp == &subpage->cp[a][2 * subpage->n[a] + 1]);
1734 for (z = 0; z < page->n[b] * 2 + 2; z++)
1735 subpage->cp[b][z] = page->cp[b][z];
1737 /* Add new overflows. */
1745 s.subpage = subpage;
1747 if (!page->h[a][0] || z0 > page->h[a][0] || p0)
1748 for (z = 0; z < page->n[b]; )
1750 struct table_cell cell;
1751 int d[TABLE_N_AXES];
1758 table_get_cell (page->table, d[H], d[V], &cell);
1759 overflow0 = p0 || cell.d[a][0] < z0;
1760 overflow1 = cell.d[a][1] > z1 || (cell.d[a][1] == z1 && p1);
1761 if (overflow0 || overflow1)
1763 ro = insert_overflow (&s, &cell);
1767 ro->overflow[a][0] += p0 + axis_width (
1768 page, a, cell_ofs (cell.d[a][0]), cell_ofs (z0));
1769 if (page->h[a][0] && page->h[a][1])
1770 ro->overflow[a][0] -= page->join_crossing[a][cell.d[a][0]
1776 ro->overflow[a][1] += p1 + axis_width (
1777 page, a, cell_ofs (z1), cell_ofs (cell.d[a][1]));
1778 if (page->h[a][0] && page->h[a][1])
1779 ro->overflow[a][1] -= page->join_crossing[a][cell.d[a][1]];
1783 table_cell_free (&cell);
1786 if (!page->h[a][1] || z1 < page->n[a] - page->h[a][1] || p1)
1787 for (z = 0; z < page->n[b]; )
1789 struct table_cell cell;
1790 int d[TABLE_N_AXES];
1794 table_get_cell (page->table, d[H], d[V], &cell);
1795 if ((cell.d[a][1] > z1 || (cell.d[a][1] == z1 && p1))
1796 && find_overflow_for_cell (&s, &cell) == NULL)
1798 ro = insert_overflow (&s, &cell);
1799 ro->overflow[a][1] += p1 + axis_width (page, a, cell_ofs (z1),
1800 cell_ofs (cell.d[a][1]));
1803 table_cell_free (&cell);
1806 /* Copy overflows from PAGE into subpage. */
1807 HMAP_FOR_EACH (ro, struct render_overflow, node, &page->overflows)
1809 struct table_cell cell;
1811 table_get_cell (page->table, ro->d[H], ro->d[V], &cell);
1812 if (cell.d[a][1] > z0 && cell.d[a][0] < z1
1813 && find_overflow_for_cell (&s, &cell) == NULL)
1814 insert_overflow (&s, &cell);
1815 table_cell_free (&cell);
1821 /* Given CELL, a table_cell within S->page, stores in SUBCELL the (x,y)
1822 coordinates of the top-left cell as it will appear in S->subpage.
1824 CELL must actually intersect the region of S->page that is being selected
1825 by render_page_select() or the results will not make any sense. */
1827 cell_to_subpage (struct render_page_selection *s,
1828 const struct table_cell *cell, int subcell[TABLE_N_AXES])
1830 enum table_axis a = s->a;
1831 enum table_axis b = s->b;
1832 int ha0 = s->subpage->h[a][0];
1834 subcell[a] = MAX (cell->d[a][0] - s->z0 + ha0, ha0);
1835 subcell[b] = cell->d[b][0];
1838 /* Given CELL, a table_cell within S->page, returns the render_overflow for
1839 that cell in S->subpage, if there is one, and a null pointer otherwise.
1841 CELL must actually intersect the region of S->page that is being selected
1842 by render_page_select() or the results will not make any sense. */
1843 static const struct render_overflow *
1844 find_overflow_for_cell (struct render_page_selection *s,
1845 const struct table_cell *cell)
1849 cell_to_subpage (s, cell, subcell);
1850 return find_overflow (s->subpage, subcell[H], subcell[V]);
1853 /* Given CELL, a table_cell within S->page, inserts a render_overflow for that
1854 cell in S->subpage (which must not already exist). Initializes the new
1855 render_overflow's 'overflow' member from the overflow for CELL in S->page,
1858 CELL must actually intersect the region of S->page that is being selected
1859 by render_page_select() or the results will not make any sense. */
1860 static struct render_overflow *
1861 insert_overflow (struct render_page_selection *s,
1862 const struct table_cell *cell)
1864 const struct render_overflow *old;
1865 struct render_overflow *of;
1867 of = xzalloc (sizeof *of);
1868 cell_to_subpage (s, cell, of->d);
1869 hmap_insert (&s->subpage->overflows, &of->node,
1870 hash_cell (of->d[H], of->d[V]));
1872 old = find_overflow (s->page, cell->d[H][0], cell->d[V][0]);
1874 memcpy (of->overflow, old->overflow, sizeof of->overflow);