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 "libpspp/pool.h"
29 #include "output/render.h"
30 #include "output/tab.h"
31 #include "output/table-item.h"
32 #include "output/table.h"
34 #include "gl/minmax.h"
35 #include "gl/xalloc.h"
38 #define _(msgid) gettext (msgid)
40 /* This file uses TABLE_HORZ and TABLE_VERT enough to warrant abbreviating. */
44 /* A layout for rendering a specific table on a specific device.
46 May represent the layout of an entire table presented to
47 render_page_create(), or a rectangular subregion of a table broken out using
48 render_break_next() to allow a table to be broken across multiple pages.
50 A page's size is not limited to the size passed in as part of render_params.
51 render_pager breaks a render_page into smaller render_pages that will fit in
52 the available space. */
55 const struct render_params *params; /* Parameters of the target device. */
56 struct table *table; /* Table rendered. */
59 /* Local copies of table->n and table->h, for convenience. */
61 int h[TABLE_N_AXES][2];
65 cp[H] represents x positions within the table.
67 cp[H][1] = the width of the leftmost vertical rule.
68 cp[H][2] = cp[H][1] + the width of the leftmost column.
69 cp[H][3] = cp[H][2] + the width of the second-from-left vertical rule.
71 cp[H][2 * nc] = x position of the rightmost vertical rule.
72 cp[H][2 * nc + 1] = total table width including all rules.
74 Similarly, cp[V] represents y positions within the table.
76 cp[V][1] = the height of the topmost horizontal rule.
77 cp[V][2] = cp[V][1] + the height of the topmost row.
78 cp[V][3] = cp[V][2] + the height of the second-from-top horizontal rule.
80 cp[V][2 * nr] = y position of the bottommost horizontal rule.
81 cp[V][2 * nr + 1] = total table height including all rules.
83 Rules and columns can have width or height 0, in which case consecutive
84 values in this array are equal. */
85 int *cp[TABLE_N_AXES];
87 /* render_break_next() can break a table such that some cells are not fully
88 contained within a render_page. This will happen if a cell is too wide
89 or two tall to fit on a single page, or if a cell spans multiple rows or
90 columns and the page only includes some of those rows or columns.
92 This hash table contains "struct render_overflow"s that represents each
93 such cell that doesn't completely fit on this page.
95 Each overflow cell borders at least one header edge of the table and may
96 border more. (A single table cell that is so large that it fills the
97 entire page can overflow on all four sides!) */
98 struct hmap overflows;
100 /* If a single column (or row) is too wide (or tall) to fit on a page
101 reasonably, then render_break_next() will split a single row or column
102 across multiple render_pages. This member indicates when this has
105 is_edge_cutoff[H][0] is true if pixels have been cut off the left side
106 of the leftmost column in this page, and false otherwise.
108 is_edge_cutoff[H][1] is true if pixels have been cut off the right side
109 of the rightmost column in this page, and false otherwise.
111 is_edge_cutoff[V][0] and is_edge_cutoff[V][1] are similar for the top
112 and bottom of the table.
114 The effect of is_edge_cutoff is to prevent rules along the edge in
115 question from being rendered.
117 When is_edge_cutoff is true for a given edge, the 'overflows' hmap will
118 contain a node for each cell along that edge. */
119 bool is_edge_cutoff[TABLE_N_AXES][2];
121 /* If part of a joined cell would be cut off by breaking a table along
122 'axis' at the rule with offset 'z' (where 0 <= z <= n[axis]), then
123 join_crossing[axis][z] is the thickness of the rule that would be cut
126 This is used to know to allocate extra space for breaking at such a
127 position, so that part of the cell's content is not lost.
129 This affects breaking a table only when headers are present. When
130 headers are not present, the rule's thickness is used for cell content,
131 so no part of the cell's content is lost (and in fact it is duplicated
132 across both pages). */
133 int *join_crossing[TABLE_N_AXES];
136 static struct render_page *render_page_create (const struct render_params *,
137 struct table *, int min_width);
139 struct render_page *render_page_ref (const struct render_page *page_);
140 static void render_page_unref (struct render_page *);
142 /* Returns the offset in struct render_page's cp[axis] array of the rule with
143 index RULE_IDX. That is, if RULE_IDX is 0, then the offset is that of the
144 leftmost or topmost rule; if RULE_IDX is 1, then the offset is that of the
145 next rule to the right (or below); and so on. */
147 rule_ofs (int rule_idx)
152 /* Returns the offset in struct render_page's cp[axis] array of the rule with
153 index RULE_IDX_R, which counts from the right side (or bottom) of the page
154 left (or up), according to whether AXIS is H or V, respectively. That is,
155 if RULE_IDX_R is 0, then the offset is that of the rightmost or bottommost
156 rule; if RULE_IDX is 1, then the offset is that of the next rule to the left
157 (or above); and so on. */
159 rule_ofs_r (const struct render_page *page, int axis, int rule_idx_r)
161 return (page->n[axis] - rule_idx_r) * 2;
164 /* Returns the offset in struct render_page's cp[axis] array of the cell with
165 index CELL_IDX. That is, if CELL_IDX is 0, then the offset is that of the
166 leftmost or topmost cell; if CELL_IDX is 1, then the offset is that of the
167 next cell to the right (or below); and so on. */
169 cell_ofs (int cell_idx)
171 return cell_idx * 2 + 1;
174 /* Returns the width of PAGE along AXIS from OFS0 to OFS1, exclusive. */
176 axis_width (const struct render_page *page, int axis, int ofs0, int ofs1)
178 return page->cp[axis][ofs1] - page->cp[axis][ofs0];
181 /* Returns the width of the headers in PAGE along AXIS. */
183 headers_width (const struct render_page *page, int axis)
185 int h0 = page->h[axis][0];
186 int w0 = axis_width (page, axis, rule_ofs (0), cell_ofs (h0));
187 int n = page->n[axis];
188 int h1 = page->h[axis][1];
189 int w1 = axis_width (page, axis, rule_ofs_r (page, axis, h1), cell_ofs (n));
193 /* Returns the width of cell X along AXIS in PAGE. */
195 cell_width (const struct render_page *page, int axis, int x)
197 return axis_width (page, axis, cell_ofs (x), cell_ofs (x) + 1);
200 /* Returns the width of rule X along AXIS in PAGE. */
202 rule_width (const struct render_page *page, int axis, int x)
204 return axis_width (page, axis, rule_ofs (x), rule_ofs (x) + 1);
207 /* Returns the width of rule X along AXIS in PAGE. */
209 rule_width_r (const struct render_page *page, int axis, int x)
211 int ofs = rule_ofs_r (page, axis, x);
212 return axis_width (page, axis, ofs, ofs + 1);
215 /* Returns the width of cells X0 through X1, exclusive, along AXIS in PAGE. */
217 joined_width (const struct render_page *page, int axis, int x0, int x1)
219 return axis_width (page, axis, cell_ofs (x0), cell_ofs (x1) - 1);
222 /* Returns the width of the widest cell, excluding headers, along AXIS in
225 max_cell_width (const struct render_page *page, int axis)
227 int n = page->n[axis];
228 int x0 = page->h[axis][0];
229 int x1 = n - page->h[axis][1];
233 for (x = x0; x < x1; x++)
235 int w = cell_width (page, axis, x);
242 /* A cell that doesn't completely fit on the render_page. */
243 struct render_overflow
245 struct hmap_node node; /* In render_page's 'overflows' hmap. */
247 /* Occupied region of page.
249 d[H][0] is the leftmost column.
250 d[H][1] is the rightmost column, plus 1.
251 d[V][0] is the top row.
252 d[V][1] is the bottom row, plus 1.
254 The cell in its original table might occupy a larger region. This
255 member reflects the size of the cell in the current render_page, after
256 trimming off any rows or columns due to page-breaking. */
259 /* The space that has been trimmed off the cell:
261 overflow[H][0]: space trimmed off its left side.
262 overflow[H][1]: space trimmed off its right side.
263 overflow[V][0]: space trimmed off its top.
264 overflow[V][1]: space trimmed off its bottom.
266 During rendering, this information is used to position the rendered
267 portion of the cell within the available space.
269 When a cell is rendered, sometimes it is permitted to spill over into
270 space that is ordinarily reserved for rules. Either way, this space is
271 still included in overflow values.
273 Suppose, for example, that a cell that joins 2 columns has a width of 60
274 pixels and content "abcdef", that the 2 columns that it joins have
275 widths of 20 and 30 pixels, respectively, and that therefore the rule
276 between the two joined columns has a width of 10 (20 + 10 + 30 = 60).
277 It might render like this, if each character is 10x10, and showing a few
278 extra table cells for context:
286 If this render_page is broken at the rule that separates "gh" from
287 "ijk", then the page that contains the left side of the "abcdef" cell
288 will have overflow[H][1] of 10 + 30 = 40 for its portion of the cell,
289 and the page that contains the right side of the cell will have
290 overflow[H][0] of 20 + 10 = 30. The two resulting pages would look like
308 int overflow[TABLE_N_AXES][2];
311 /* Returns a hash value for (,Y). */
313 hash_cell (int x, int y)
315 return hash_int (x + (y << 16), 0);
318 /* Searches PAGE's set of render_overflow for one whose top-left cell is
319 (X,Y). Returns it, if there is one, otherwise a null pointer. */
320 static const struct render_overflow *
321 find_overflow (const struct render_page *page, int x, int y)
323 if (!hmap_is_empty (&page->overflows))
325 const struct render_overflow *of;
327 HMAP_FOR_EACH_WITH_HASH (of, struct render_overflow, node,
328 hash_cell (x, y), &page->overflows)
329 if (x == of->d[H] && y == of->d[V])
336 /* Row or column dimensions. Used to figure the size of a table in
337 render_page_create() and discarded after that. */
340 /* Width without considering rows (or columns) that span more than one (or
344 /* Width taking spanned rows (or columns) into consideration. */
348 /* Modifies the 'width' members of the N elements of ROWS so that their sum,
349 when added to rule widths RULES[1] through RULES[N - 1] inclusive, is at
352 distribute_spanned_width (int width,
353 struct render_row *rows, const int *rules, int n)
355 /* Sum up the unspanned widths of the N rows for use as weights. */
356 int total_unspanned = 0;
357 for (int x = 0; x < n; x++)
358 total_unspanned += rows[x].unspanned;
359 for (int x = 0; x < n - 1; x++)
360 total_unspanned += rules[x + 1];
361 if (total_unspanned >= width)
364 /* The algorithm used here is based on the following description from HTML 4:
366 For cells that span multiple columns, a simple approach consists of
367 apportioning the min/max widths evenly to each of the constituent
368 columns. A slightly more complex approach is to use the min/max
369 widths of unspanned cells to weight how spanned widths are
370 apportioned. Experiments suggest that a blend of the two approaches
371 gives good results for a wide range of tables.
373 We blend the two approaches half-and-half, except that we cannot use the
374 unspanned weights when 'total_unspanned' is 0 (because that would cause a
377 The calculation we want to do is this:
380 w1 = width * (column's unspanned width) / (total unspanned width)
381 (column's width) = (w0 + w1) / 2
383 We implement it as a precise calculation in integers by multiplying w0 and
384 w1 by the common denominator of all three calculations (d), dividing that
385 out in the column width calculation, and then keeping the remainder for
388 (We actually compute the unspanned width of a column as twice the
389 unspanned width, plus the width of the rule on the left, plus the width of
390 the rule on the right. That way each rule contributes to both the cell on
391 its left and on its right.)
393 long long int d0 = n;
394 long long int d1 = 2LL * MAX (total_unspanned, 1);
395 long long int d = d0 * d1;
396 if (total_unspanned > 0)
398 long long int w = d / 2;
399 for (int x = 0; x < n; x++)
402 if (total_unspanned > 0)
404 long long int unspanned = rows[x].unspanned * 2LL;
406 unspanned += rules[x + 1];
408 unspanned += rules[x];
409 w += width * unspanned * d0;
412 rows[x].width = MAX (rows[x].width, w / d);
413 w -= rows[x].width * d;
417 /* Initializes PAGE->cp[AXIS] from the row widths in ROWS and the rule widths
420 accumulate_row_widths (const struct render_page *page, enum table_axis axis,
421 const struct render_row *rows, const int *rules)
423 int n = page->n[axis];
429 for (z = 0; z < n; z++)
431 cp[1] = cp[0] + rules[z];
432 cp[2] = cp[1] + rows[z].width;
435 cp[1] = cp[0] + rules[n];
438 /* Returns the sum of widths of the N ROWS and N+1 RULES. */
440 calculate_table_width (int n, const struct render_row *rows, int *rules)
446 for (x = 0; x < n; x++)
447 width += rows[x].width;
448 for (x = 0; x <= n; x++)
454 /* Rendering utility functions. */
456 /* Returns the line style to use for drawing a rule of the given TYPE. */
457 static enum render_line_style
458 rule_to_render_type (unsigned char type)
463 return RENDER_LINE_NONE;
465 return RENDER_LINE_SINGLE;
467 return RENDER_LINE_DASHED;
469 return RENDER_LINE_THICK;
471 return RENDER_LINE_THIN;
473 return RENDER_LINE_DOUBLE;
479 /* Returns the width of the rule in TABLE that is at offset Z along axis A, if
480 rendered with PARAMS. */
482 measure_rule (const struct render_params *params, const struct table *table,
483 enum table_axis a, int z)
485 enum table_axis b = !a;
489 /* Determine all types of rules that are present, as a bitmap in 'rules'
490 where rule type 't' is present if bit 2**t is set. */
491 struct cell_color color;
494 for (d[b] = 0; d[b] < table->n[b]; d[b]++)
495 rules |= 1u << table_get_rule (table, a, d[H], d[V], &color);
497 /* Turn off TAL_NONE because it has width 0 and we needn't bother. However,
498 if the device doesn't support margins, make sure that there is at least a
499 small gap between cells (but we don't need any at the left or right edge
501 if (rules & (1u << TAL_NONE))
503 rules &= ~(1u << TAL_NONE);
504 if (z > 0 && z < table->n[a] && !params->supports_margins && a == H)
505 rules |= 1u << TAL_SOLID;
508 /* Calculate maximum width of the rules that are present. */
510 for (size_t i = 0; i < TABLE_N_STROKES; i++)
511 if (rules & (1u << i))
512 width = MAX (width, params->line_widths[a][rule_to_render_type (i)]);
516 /* Allocates and returns a new render_page using PARAMS and TABLE. Allocates
517 space for all of the members of the new page, but the caller must initialize
518 the 'cp' member itself. */
519 static struct render_page *
520 render_page_allocate (const struct render_params *params,
523 struct render_page *page;
526 page = xmalloc (sizeof *page);
527 page->params = params;
530 page->n[H] = table->n[H];
531 page->n[V] = table->n[V];
532 page->h[H][0] = table->h[H][0];
533 page->h[H][1] = table->h[H][1];
534 page->h[V][0] = table->h[V][0];
535 page->h[V][1] = table->h[V][1];
537 for (i = 0; i < TABLE_N_AXES; i++)
539 page->cp[i] = xmalloc ((2 * page->n[i] + 2) * sizeof *page->cp[i]);
540 page->join_crossing[i] = xzalloc ((page->n[i] + 1) * sizeof *page->join_crossing[i]);
543 hmap_init (&page->overflows);
544 memset (page->is_edge_cutoff, 0, sizeof page->is_edge_cutoff);
549 /* Allocates and returns a new render_page for PARAMS and TABLE, initializing
550 cp[H] in the new page from ROWS and RULES. The caller must still initialize
552 static struct render_page *
553 create_page_with_exact_widths (const struct render_params *params,
555 const struct render_row *rows, int *rules)
557 struct render_page *page = render_page_allocate (params, table);
558 accumulate_row_widths (page, H, rows, rules);
562 /* Allocates and returns a new render_page for PARAMS and TABLE.
564 Initializes cp[H] in the new page by setting the width of each row 'i' to
565 somewhere between the minimum cell width ROW_MIN[i].width and the maximum
566 ROW_MAX[i].width. Sets the width of rules to those in RULES.
568 W_MIN is the sum of ROWS_MIN[].width.
570 W_MAX is the sum of ROWS_MAX[].width.
572 The caller must still initialize cp[V]. */
573 static struct render_page *
574 create_page_with_interpolated_widths (const struct render_params *params,
576 const struct render_row *rows_min,
577 const struct render_row *rows_max,
578 int w_min, int w_max, const int *rules)
580 const int n = table->n[H];
581 const long long int avail = params->size[H] - w_min;
582 const long long int wanted = w_max - w_min;
586 struct render_page *page = render_page_allocate (params, table);
588 int *cph = page->cp[H];
590 long long int w = wanted / 2;
591 for (int x = 0; x < n; x++)
593 w += avail * (rows_max[x].width - rows_min[x].width);
594 int extra = w / wanted;
597 cph[1] = cph[0] + rules[x];
598 cph[2] = cph[1] + rows_min[x].width + extra;
601 cph[1] = cph[0] + rules[n];
603 assert (page->cp[H][n * 2 + 1] == params->size[H]);
609 set_join_crossings (struct render_page *page, enum table_axis axis,
610 const struct table_cell *cell, int *rules)
614 for (z = cell->d[axis][0] + 1; z <= cell->d[axis][1] - 1; z++)
615 page->join_crossing[axis][z] = rules[z];
618 /* Creates and returns a new render_page for rendering TABLE on a device
621 The new render_page will be suitable for rendering on a device whose page
622 size is PARAMS->size, but the caller is responsible for actually breaking it
623 up to fit on such a device, using the render_break abstraction. */
624 static struct render_page *
625 render_page_create (const struct render_params *params, struct table *table,
628 struct render_page *page;
630 struct render_row *columns[2];
631 struct render_row *rows;
633 int *rules[TABLE_N_AXES];
637 enum table_axis axis;
639 nc = table_nc (table);
640 nr = table_nr (table);
642 /* Figure out rule widths. */
643 for (axis = 0; axis < TABLE_N_AXES; axis++)
645 int n = table->n[axis] + 1;
648 rules[axis] = xnmalloc (n, sizeof *rules);
649 for (z = 0; z < n; z++)
650 rules[axis][z] = measure_rule (params, table, axis, z);
653 /* Calculate minimum and maximum widths of cells that do not
654 span multiple columns. */
655 for (i = 0; i < 2; i++)
656 columns[i] = xzalloc (nc * sizeof *columns[i]);
657 for (y = 0; y < nr; y++)
658 for (x = 0; x < nc; )
660 struct table_cell cell;
662 table_get_cell (table, x, y, &cell);
663 if (y == cell.d[V][0])
665 if (table_cell_colspan (&cell) == 1)
670 params->measure_cell_width (params->aux, &cell,
672 for (i = 0; i < 2; i++)
673 if (columns[i][x].unspanned < w[i])
674 columns[i][x].unspanned = w[i];
678 table_cell_free (&cell);
681 /* Distribute widths of spanned columns. */
682 for (i = 0; i < 2; i++)
683 for (x = 0; x < nc; x++)
684 columns[i][x].width = columns[i][x].unspanned;
685 for (y = 0; y < nr; y++)
686 for (x = 0; x < nc; )
688 struct table_cell cell;
690 table_get_cell (table, x, y, &cell);
691 if (y == cell.d[V][0] && table_cell_colspan (&cell) > 1)
695 params->measure_cell_width (params->aux, &cell, &w[MIN], &w[MAX]);
696 for (i = 0; i < 2; i++)
697 distribute_spanned_width (w[i], &columns[i][cell.d[H][0]],
698 rules[H], table_cell_colspan (&cell));
701 table_cell_free (&cell);
704 for (i = 0; i < 2; i++)
705 distribute_spanned_width (min_width, &columns[i][0], rules[H], nc);
707 /* In pathological cases, spans can cause the minimum width of a column to
708 exceed the maximum width. This bollixes our interpolation algorithm
709 later, so fix it up. */
710 for (i = 0; i < nc; i++)
711 if (columns[MIN][i].width > columns[MAX][i].width)
712 columns[MAX][i].width = columns[MIN][i].width;
714 /* Decide final column widths. */
715 for (i = 0; i < 2; i++)
716 table_widths[i] = calculate_table_width (table_nc (table),
717 columns[i], rules[H]);
718 if (table_widths[MAX] <= params->size[H])
720 /* Fits even with maximum widths. Use them. */
721 page = create_page_with_exact_widths (params, table, columns[MAX],
724 else if (table_widths[MIN] <= params->size[H])
726 /* Fits with minimum widths, so distribute the leftover space. */
727 page = create_page_with_interpolated_widths (
728 params, table, columns[MIN], columns[MAX],
729 table_widths[MIN], table_widths[MAX], rules[H]);
733 /* Doesn't fit even with minimum widths. Assign minimums for now, and
734 later we can break it horizontally into multiple pages. */
735 page = create_page_with_exact_widths (params, table, columns[MIN],
739 /* Calculate heights of cells that do not span multiple rows. */
740 rows = xzalloc (nr * sizeof *rows);
741 for (y = 0; y < nr; y++)
743 for (x = 0; x < nc; )
745 struct render_row *r = &rows[y];
746 struct table_cell cell;
748 table_get_cell (table, x, y, &cell);
749 if (y == cell.d[V][0])
751 if (table_cell_rowspan (&cell) == 1)
753 int w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
754 int h = params->measure_cell_height (params->aux, &cell, w);
755 if (h > r->unspanned)
756 r->unspanned = r->width = h;
759 set_join_crossings (page, V, &cell, rules[V]);
761 if (table_cell_colspan (&cell) > 1)
762 set_join_crossings (page, H, &cell, rules[H]);
765 table_cell_free (&cell);
768 for (i = 0; i < 2; i++)
771 /* Distribute heights of spanned rows. */
772 for (y = 0; y < nr; y++)
773 for (x = 0; x < nc; )
775 struct table_cell cell;
777 table_get_cell (table, x, y, &cell);
778 if (y == cell.d[V][0] && table_cell_rowspan (&cell) > 1)
780 int w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
781 int h = params->measure_cell_height (params->aux, &cell, w);
782 distribute_spanned_width (h, &rows[cell.d[V][0]], rules[V],
783 table_cell_rowspan (&cell));
786 table_cell_free (&cell);
789 /* Decide final row heights. */
790 accumulate_row_widths (page, V, rows, rules[V]);
793 /* Measure headers. If they are "too big", get rid of them. */
794 for (axis = 0; axis < TABLE_N_AXES; axis++)
796 int hw = headers_width (page, axis);
797 if (hw * 2 >= page->params->size[axis]
798 || hw + max_cell_width (page, axis) > page->params->size[axis])
800 page->table = table_unshare (page->table);
801 page->table->h[axis][0] = page->table->h[axis][1] = 0;
802 page->h[axis][0] = page->h[axis][1] = 0;
812 /* Increases PAGE's reference count. */
814 render_page_ref (const struct render_page *page_)
816 struct render_page *page = CONST_CAST (struct render_page *, page_);
821 /* Decreases PAGE's reference count and destroys PAGE if this causes the
822 reference count to fall to zero. */
824 render_page_unref (struct render_page *page)
826 if (page != NULL && --page->ref_cnt == 0)
829 struct render_overflow *overflow, *next;
831 HMAP_FOR_EACH_SAFE (overflow, next, struct render_overflow, node,
834 hmap_destroy (&page->overflows);
836 table_unref (page->table);
838 for (i = 0; i < TABLE_N_AXES; ++i)
840 free (page->join_crossing[i]);
848 /* Returns the size of PAGE along AXIS. (This might be larger than the page
849 size specified in the parameters passed to render_page_create(). Use a
850 render_break to break up a render_page into page-sized chunks.) */
852 render_page_get_size (const struct render_page *page, enum table_axis axis)
854 return page->cp[axis][page->n[axis] * 2 + 1];
858 render_page_get_best_breakpoint (const struct render_page *page, int height)
862 /* If there's no room for at least the top row and the rules above and below
863 it, don't include any of the table. */
864 if (page->cp[V][3] > height)
867 /* Otherwise include as many rows and rules as we can. */
868 for (y = 5; y <= 2 * page->n[V] + 1; y += 2)
869 if (page->cp[V][y] > height)
870 return page->cp[V][y - 2];
874 /* Drawing render_pages. */
876 static inline enum render_line_style
877 get_rule (const struct render_page *page, enum table_axis axis,
878 const int d[TABLE_N_AXES], struct cell_color *color)
880 return rule_to_render_type (table_get_rule (page->table,
881 axis, d[H] / 2, d[V] / 2,
892 render_direction_rtl (void)
894 /* TRANSLATORS: Do not translate this string. If the script of your language
895 reads from right to left (eg Persian, Arabic, Hebrew etc), then replace
896 this string with "output-direction-rtl". Otherwise either leave it
897 untranslated or copy it verbatim. */
898 const char *dir = _("output-direction-ltr");
899 if ( 0 == strcmp ("output-direction-rtl", dir))
902 if ( 0 != strcmp ("output-direction-ltr", dir))
903 fprintf (stderr, "This localisation has been incorrectly translated. Complain to the translator.\n");
909 render_rule (const struct render_page *page, const int ofs[TABLE_N_AXES],
910 const int d[TABLE_N_AXES])
912 enum render_line_style styles[TABLE_N_AXES][2];
913 struct cell_color colors[TABLE_N_AXES][2];
916 for (a = 0; a < TABLE_N_AXES; a++)
918 enum table_axis b = !a;
920 styles[a][0] = styles[a][1] = RENDER_LINE_NONE;
923 || (page->is_edge_cutoff[a][0] && d[a] == 0)
924 || (page->is_edge_cutoff[a][1] && d[a] == page->n[a] * 2))
935 styles[a][0] = get_rule (page, a, e, &colors[a][0]);
938 if (d[b] / 2 < page->table->n[b])
939 styles[a][1] = get_rule (page, a, d, &colors[a][1]);
943 styles[a][0] = styles[a][1] = get_rule (page, a, d, &colors[a][0]);
944 colors[a][1] = colors[a][0];
948 if (styles[H][0] != RENDER_LINE_NONE || styles[H][1] != RENDER_LINE_NONE
949 || styles[V][0] != RENDER_LINE_NONE || styles[V][1] != RENDER_LINE_NONE)
951 int bb[TABLE_N_AXES][2];
953 bb[H][0] = ofs[H] + page->cp[H][d[H]];
954 bb[H][1] = ofs[H] + page->cp[H][d[H] + 1];
955 if (page->params->rtl)
958 bb[H][0] = render_page_get_size (page, H) - bb[H][1];
959 bb[H][1] = render_page_get_size (page, H) - temp;
961 bb[V][0] = ofs[V] + page->cp[V][d[V]];
962 bb[V][1] = ofs[V] + page->cp[V][d[V] + 1];
963 page->params->draw_line (page->params->aux, bb, styles, colors);
968 render_cell (const struct render_page *page, const int ofs[TABLE_N_AXES],
969 const struct table_cell *cell)
971 const struct render_overflow *of;
972 int bb[TABLE_N_AXES][2];
973 int clip[TABLE_N_AXES][2];
975 bb[H][0] = clip[H][0] = ofs[H] + page->cp[H][cell->d[H][0] * 2 + 1];
976 bb[H][1] = clip[H][1] = ofs[H] + page->cp[H][cell->d[H][1] * 2];
977 if (page->params->rtl)
980 bb[H][0] = clip[H][0] = render_page_get_size (page, H) - bb[H][1];
981 bb[H][1] = clip[H][1] = render_page_get_size (page, H) - temp;
983 bb[V][0] = clip[V][0] = ofs[V] + page->cp[V][cell->d[V][0] * 2 + 1];
984 bb[V][1] = clip[V][1] = ofs[V] + page->cp[V][cell->d[V][1] * 2];
986 enum table_valign valign = cell->style->cell_style.valign;
987 if (valign != TABLE_VALIGN_TOP)
989 int height = page->params->measure_cell_height (
990 page->params->aux, cell, bb[H][1] - bb[H][0]);
991 int extra = bb[V][1] - bb[V][0] - height;
994 if (valign == TABLE_VALIGN_CENTER)
1000 of = find_overflow (page, cell->d[H][0], cell->d[V][0]);
1003 enum table_axis axis;
1005 for (axis = 0; axis < TABLE_N_AXES; axis++)
1007 if (of->overflow[axis][0])
1009 bb[axis][0] -= of->overflow[axis][0];
1010 if (cell->d[axis][0] == 0 && !page->is_edge_cutoff[axis][0])
1011 clip[axis][0] = ofs[axis] + page->cp[axis][cell->d[axis][0] * 2];
1013 if (of->overflow[axis][1])
1015 bb[axis][1] += of->overflow[axis][1];
1016 if (cell->d[axis][1] == page->n[axis] && !page->is_edge_cutoff[axis][1])
1017 clip[axis][1] = ofs[axis] + page->cp[axis][cell->d[axis][1] * 2 + 1];
1022 int spill[TABLE_N_AXES][2];
1023 for (enum table_axis axis = 0; axis < TABLE_N_AXES; axis++)
1025 spill[axis][0] = rule_width (page, axis, cell->d[axis][0]) / 2;
1026 spill[axis][1] = rule_width (page, axis, cell->d[axis][1]) / 2;
1029 int color_idx = (cell->d[V][0] < page->h[V][0]
1030 || page->n[V] - (cell->d[V][0] + 1) < page->h[V][1]
1032 : (cell->d[V][0] - page->h[V][0]) & 1);
1033 page->params->draw_cell (page->params->aux, cell, color_idx,
1037 /* Draws the cells of PAGE indicated in BB. */
1039 render_page_draw_cells (const struct render_page *page,
1040 int ofs[TABLE_N_AXES], int bb[TABLE_N_AXES][2])
1042 for (int y = bb[V][0]; y < bb[V][1]; y++)
1043 for (int x = bb[H][0]; x < bb[H][1]; )
1044 if (!is_rule (x) && !is_rule (y))
1046 struct table_cell cell;
1048 table_get_cell (page->table, x / 2, y / 2, &cell);
1049 if (y / 2 == bb[V][0] / 2 || y / 2 == cell.d[V][0])
1050 render_cell (page, ofs, &cell);
1051 x = rule_ofs (cell.d[H][1]);
1052 table_cell_free (&cell);
1057 for (int y = bb[V][0]; y < bb[V][1]; y++)
1058 for (int x = bb[H][0]; x < bb[H][1]; x++)
1059 if (is_rule (x) || is_rule (y))
1061 int d[TABLE_N_AXES];
1064 render_rule (page, ofs, d);
1068 /* Renders PAGE, by calling the 'draw_line' and 'draw_cell' functions from the
1069 render_params provided to render_page_create(). */
1071 render_page_draw (const struct render_page *page, int ofs[TABLE_N_AXES])
1073 int bb[TABLE_N_AXES][2];
1076 bb[H][1] = page->n[H] * 2 + 1;
1078 bb[V][1] = page->n[V] * 2 + 1;
1080 render_page_draw_cells (page, ofs, bb);
1083 /* Returns the greatest value i, 0 <= i < n, such that cp[i] <= x0. */
1085 get_clip_min_extent (int x0, const int cp[], int n)
1087 int low, high, best;
1094 int middle = low + (high - low) / 2;
1096 if (cp[middle] <= x0)
1108 /* Returns the least value i, 0 <= i < n, such that cp[i] >= x1. */
1110 get_clip_max_extent (int x1, const int cp[], int n)
1112 int low, high, best;
1119 int middle = low + (high - low) / 2;
1121 if (cp[middle] >= x1)
1122 best = high = middle;
1127 while (best > 0 && cp[best - 1] == cp[best])
1133 /* Renders the cells of PAGE that intersect (X,Y)-(X+W,Y+H), by calling the
1134 'draw_line' and 'draw_cell' functions from the render_params provided to
1135 render_page_create(). */
1137 render_page_draw_region (const struct render_page *page,
1138 int ofs[TABLE_N_AXES], int clip[TABLE_N_AXES][2])
1140 int bb[TABLE_N_AXES][2];
1142 bb[H][0] = get_clip_min_extent (clip[H][0], page->cp[H], page->n[H] * 2 + 1);
1143 bb[H][1] = get_clip_max_extent (clip[H][1], page->cp[H], page->n[H] * 2 + 1);
1144 bb[V][0] = get_clip_min_extent (clip[V][0], page->cp[V], page->n[V] * 2 + 1);
1145 bb[V][1] = get_clip_max_extent (clip[V][1], page->cp[V], page->n[V] * 2 + 1);
1147 render_page_draw_cells (page, ofs, bb);
1150 /* Breaking up tables to fit on a page. */
1152 /* An iterator for breaking render_pages into smaller chunks. */
1155 struct render_page *page; /* Page being broken up. */
1156 enum table_axis axis; /* Axis along which 'page' is being broken. */
1157 int z; /* Next cell along 'axis'. */
1158 int pixel; /* Pixel offset within cell 'z' (usually 0). */
1159 int hw; /* Width of headers of 'page' along 'axis'. */
1162 static int needed_size (const struct render_break *, int cell);
1163 static bool cell_is_breakable (const struct render_break *, int cell);
1164 static struct render_page *render_page_select (const struct render_page *,
1169 /* Initializes render_break B for breaking PAGE along AXIS.
1170 Takes ownership of PAGE. */
1172 render_break_init (struct render_break *b, struct render_page *page,
1173 enum table_axis axis)
1177 b->z = page->h[axis][0];
1179 b->hw = headers_width (page, axis);
1182 /* Initializes B as a render_break structure for which
1183 render_break_has_next() always returns false. */
1185 render_break_init_empty (struct render_break *b)
1188 b->axis = TABLE_HORZ;
1194 /* Frees B and unrefs the render_page that it owns. */
1196 render_break_destroy (struct render_break *b)
1200 render_page_unref (b->page);
1205 /* Returns true if B still has cells that are yet to be returned,
1206 false if all of B's page has been processed. */
1208 render_break_has_next (const struct render_break *b)
1210 const struct render_page *page = b->page;
1211 enum table_axis axis = b->axis;
1213 return page != NULL && b->z < page->n[axis] - page->h[axis][1];
1216 /* Returns a new render_page that is up to SIZE pixels wide along B's axis.
1217 Returns a null pointer if B has already been completely broken up, or if
1218 SIZE is too small to reasonably render any cells. The latter will never
1219 happen if SIZE is at least as large as the page size passed to
1220 render_page_create() along B's axis. */
1221 static struct render_page *
1222 render_break_next (struct render_break *b, int size)
1224 const struct render_page *page = b->page;
1225 enum table_axis axis = b->axis;
1226 struct render_page *subpage;
1229 if (!render_break_has_next (b))
1233 for (z = b->z; z < page->n[axis] - page->h[axis][1]; z++)
1235 int needed = needed_size (b, z + 1);
1238 if (cell_is_breakable (b, z))
1240 /* If there is no right header and we render a partial cell on
1241 the right side of the body, then we omit the rightmost rule of
1242 the body. Otherwise the rendering is deceptive because it
1243 looks like the whole cell is present instead of a partial
1246 This is similar to code for the left side in needed_size(). */
1247 int rule_allowance = (page->h[axis][1]
1249 : rule_width (page, axis, z));
1251 /* The amount that, if we added cell 'z', the rendering would
1252 overfill the allocated 'size'. */
1253 int overhang = needed - size - rule_allowance;
1255 /* The width of cell 'z'. */
1256 int cell_size = cell_width (page, axis, z);
1258 /* The amount trimmed off the left side of 'z',
1259 and the amount left to render. */
1260 int cell_ofs = z == b->z ? b->pixel : 0;
1261 int cell_left = cell_size - cell_ofs;
1263 /* A small but visible width. */
1264 int em = page->params->font_size[axis];
1266 /* If some of the cell remains to render,
1267 and there would still be some of the cell left afterward,
1268 then partially render that much of the cell. */
1269 pixel = (cell_left && cell_left > overhang
1270 ? cell_left - overhang + cell_ofs
1273 /* If there would be only a tiny amount of the cell left after
1274 rendering it partially, reduce the amount rendered slightly
1275 to make the output look a little better. */
1276 if (pixel + em > cell_size)
1277 pixel = MAX (pixel - em, 0);
1279 /* If we're breaking vertically, then consider whether the cells
1280 being broken have a better internal breakpoint than the exact
1281 number of pixels available, which might look bad e.g. because
1282 it breaks in the middle of a line of text. */
1283 if (axis == TABLE_VERT && page->params->adjust_break)
1287 for (x = 0; x < page->n[H]; )
1289 struct table_cell cell;
1293 table_get_cell (page->table, x, z, &cell);
1294 w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
1295 better_pixel = page->params->adjust_break (
1296 page->params->aux, &cell, w, pixel);
1298 table_cell_free (&cell);
1300 if (better_pixel < pixel)
1302 if (better_pixel > (z == b->z ? b->pixel : 0))
1304 pixel = better_pixel;
1307 else if (better_pixel == 0 && z != b->z)
1320 if (z == b->z && !pixel)
1323 subpage = render_page_select (page, axis, b->z, b->pixel,
1325 pixel ? cell_width (page, axis, z) - pixel
1332 /* Returns the width that would be required along B's axis to render a page
1333 from B's current position up to but not including CELL. */
1335 needed_size (const struct render_break *b, int cell)
1337 const struct render_page *page = b->page;
1338 enum table_axis axis = b->axis;
1341 /* Width of left header not including its rightmost rule. */
1342 size = axis_width (page, axis, 0, rule_ofs (page->h[axis][0]));
1344 /* If we have a pixel offset and there is no left header, then we omit the
1345 leftmost rule of the body. Otherwise the rendering is deceptive because
1346 it looks like the whole cell is present instead of a partial cell.
1348 Otherwise (if there are headers) we will be merging two rules: the
1349 rightmost rule in the header and the leftmost rule in the body. We assume
1350 that the width of a merged rule is the larger of the widths of either rule
1352 if (b->pixel == 0 || page->h[axis][0])
1353 size += MAX (rule_width (page, axis, page->h[axis][0]),
1354 rule_width (page, axis, b->z));
1356 /* Width of body, minus any pixel offset in the leftmost cell. */
1357 size += joined_width (page, axis, b->z, cell) - b->pixel;
1359 /* Width of rightmost rule in body merged with leftmost rule in headers. */
1360 size += MAX (rule_width_r (page, axis, page->h[axis][1]),
1361 rule_width (page, axis, cell));
1363 /* Width of right header not including its leftmost rule. */
1364 size += axis_width (page, axis, rule_ofs_r (page, axis, page->h[axis][1]),
1365 rule_ofs_r (page, axis, 0));
1367 /* Join crossing. */
1368 if (page->h[axis][0] && page->h[axis][1])
1369 size += page->join_crossing[axis][b->z];
1374 /* Returns true if CELL along B's axis may be broken across a page boundary.
1376 This is just a heuristic. Breaking cells across page boundaries can save
1377 space, but it looks ugly. */
1379 cell_is_breakable (const struct render_break *b, int cell)
1381 const struct render_page *page = b->page;
1382 enum table_axis axis = b->axis;
1384 return cell_width (page, axis, cell) >= page->params->min_break[axis];
1391 const struct render_params *params;
1393 struct render_page **pages;
1394 size_t n_pages, allocated_pages;
1397 struct render_break x_break;
1398 struct render_break y_break;
1401 static const struct render_page *
1402 render_pager_add_table (struct render_pager *p, struct table *table,
1405 struct render_page *page;
1407 if (p->n_pages >= p->allocated_pages)
1408 p->pages = x2nrealloc (p->pages, &p->allocated_pages, sizeof *p->pages);
1409 page = p->pages[p->n_pages++] = render_page_create (p->params, table,
1415 render_pager_start_page (struct render_pager *p)
1417 render_break_init (&p->x_break, render_page_ref (p->pages[p->cur_page++]),
1419 render_break_init_empty (&p->y_break);
1423 add_footnote_page (struct render_pager *p, const struct table_item *item)
1425 const struct footnote **f;
1426 size_t n_footnotes = table_collect_footnotes (item, &f);
1430 struct tab_table *t = tab_create (2, n_footnotes);
1432 for (size_t i = 0; i < n_footnotes; i++)
1435 tab_text_format (t, 0, i, TAB_LEFT, "%s.", f[i]->marker);
1436 tab_text (t, 1, i, TAB_LEFT, f[i]->content);
1439 tab_add_style (t, 0, i, f[i]->style);
1440 tab_add_style (t, 1, i, f[i]->style);
1443 render_pager_add_table (p, &t->table, 0);
1449 add_text_page (struct render_pager *p, const struct table_item_text *t,
1455 struct tab_table *tab = tab_create (1, 1);
1456 tab_text (tab, 0, 0, 0, t->content);
1457 for (size_t i = 0; i < t->n_footnotes; i++)
1458 tab_add_footnote (tab, 0, 0, t->footnotes[i]);
1460 tab->styles[0] = area_style_clone (tab->container, t->style);
1461 render_pager_add_table (p, &tab->table, min_width);
1464 /* Creates and returns a new render_pager for rendering TABLE_ITEM on the
1465 device with the given PARAMS. */
1466 struct render_pager *
1467 render_pager_create (const struct render_params *params,
1468 const struct table_item *table_item)
1470 const struct table *table = table_item_get_table (table_item);
1471 struct render_pager *p;
1473 p = xzalloc (sizeof *p);
1476 struct render_page *page = render_page_create (params, table_ref (table), 0);
1477 struct render_break b;
1478 render_break_init (&b, page, H);
1479 struct render_page *subpage = render_break_next (&b, p->params->size[H]);
1480 int title_width = subpage ? subpage->cp[H][2 * subpage->n[H] + 1] : 0;
1481 render_page_unref (subpage);
1482 render_break_destroy (&b);
1485 add_text_page (p, table_item_get_title (table_item), title_width);
1488 add_text_page (p, table_item_get_layers (table_item), title_width);
1491 render_pager_add_table (p, table_ref (table_item_get_table (table_item)), 0);
1494 add_text_page (p, table_item_get_caption (table_item), 0);
1497 add_footnote_page (p, table_item);
1499 render_pager_start_page (p);
1506 render_pager_destroy (struct render_pager *p)
1512 render_break_destroy (&p->x_break);
1513 render_break_destroy (&p->y_break);
1514 for (i = 0; i < p->n_pages; i++)
1515 render_page_unref (p->pages[i]);
1521 /* Returns true if P has content remaining to render, false if rendering is
1524 render_pager_has_next (const struct render_pager *p_)
1526 struct render_pager *p = CONST_CAST (struct render_pager *, p_);
1528 while (!render_break_has_next (&p->y_break))
1530 render_break_destroy (&p->y_break);
1531 if (!render_break_has_next (&p->x_break))
1533 render_break_destroy (&p->x_break);
1534 if (p->cur_page >= p->n_pages)
1536 render_break_init_empty (&p->x_break);
1537 render_break_init_empty (&p->y_break);
1540 render_pager_start_page (p);
1543 render_break_init (&p->y_break,
1544 render_break_next (&p->x_break, p->params->size[H]), V);
1549 /* Draws a chunk of content from P to fit in a space that has vertical size
1550 SPACE and the horizontal size specified in the render_params passed to
1551 render_page_create(). Returns the amount of space actually used by the
1552 rendered chunk, which will be 0 if SPACE is too small to render anything or
1553 if no content remains (use render_pager_has_next() to distinguish these
1556 render_pager_draw_next (struct render_pager *p, int space)
1558 int ofs[TABLE_N_AXES] = { 0, 0 };
1559 size_t start_page = SIZE_MAX;
1561 while (render_pager_has_next (p))
1563 struct render_page *page;
1565 if (start_page == p->cur_page)
1567 start_page = p->cur_page;
1569 page = render_break_next (&p->y_break, space - ofs[V]);
1573 render_page_draw (page, ofs);
1574 ofs[V] += render_page_get_size (page, V);
1575 render_page_unref (page);
1580 /* Draws all of P's content. */
1582 render_pager_draw (const struct render_pager *p)
1584 render_pager_draw_region (p, 0, 0, INT_MAX, INT_MAX);
1587 /* Draws the region of P's content that lies in the region (X,Y)-(X+W,Y+H).
1588 Some extra content might be drawn; the device should perform clipping as
1591 render_pager_draw_region (const struct render_pager *p,
1592 int x, int y, int w, int h)
1594 int ofs[TABLE_N_AXES] = { 0, 0 };
1595 int clip[TABLE_N_AXES][2];
1600 for (i = 0; i < p->n_pages; i++)
1602 const struct render_page *page = p->pages[i];
1603 int size = render_page_get_size (page, V);
1605 clip[V][0] = MAX (y, ofs[V]) - ofs[V];
1606 clip[V][1] = MIN (y + h, ofs[V] + size) - ofs[V];
1607 if (clip[V][1] > clip[V][0])
1608 render_page_draw_region (page, ofs, clip);
1614 /* Returns the size of P's content along AXIS; i.e. the content's width if AXIS
1615 is TABLE_HORZ and its length if AXIS is TABLE_VERT. */
1617 render_pager_get_size (const struct render_pager *p, enum table_axis axis)
1622 for (i = 0; i < p->n_pages; i++)
1624 int subsize = render_page_get_size (p->pages[i], axis);
1625 size = axis == H ? MAX (size, subsize) : size + subsize;
1632 render_pager_get_best_breakpoint (const struct render_pager *p, int height)
1637 for (i = 0; i < p->n_pages; i++)
1639 int size = render_page_get_size (p->pages[i], V);
1640 if (y + size >= height)
1641 return render_page_get_best_breakpoint (p->pages[i], height - y) + y;
1648 /* render_page_select() and helpers. */
1650 struct render_page_selection
1652 const struct render_page *page; /* Page whose slice we are selecting. */
1653 struct render_page *subpage; /* New page under construction. */
1654 enum table_axis a; /* Axis of 'page' along which 'subpage' is a slice. */
1655 enum table_axis b; /* The opposite of 'a'. */
1656 int z0; /* First cell along 'a' being selected. */
1657 int z1; /* Last cell being selected, plus 1. */
1658 int p0; /* Number of pixels to trim off left side of z0. */
1659 int p1; /* Number of pixels to trim off right side of z1-1. */
1662 static void cell_to_subpage (struct render_page_selection *,
1663 const struct table_cell *,
1664 int subcell[TABLE_N_AXES]);
1665 static const struct render_overflow *find_overflow_for_cell (
1666 struct render_page_selection *, const struct table_cell *);
1667 static struct render_overflow *insert_overflow (struct render_page_selection *,
1668 const struct table_cell *);
1670 /* Creates and returns a new render_page whose contents are a subregion of
1671 PAGE's contents. The new render_page includes cells Z0 through Z1
1672 (exclusive) along AXIS, plus any headers on AXIS.
1674 If P0 is nonzero, then it is a number of pixels to exclude from the left or
1675 top (according to AXIS) of cell Z0. Similarly, P1 is a number of pixels to
1676 exclude from the right or bottom of cell Z1 - 1. (P0 and P1 are used to
1677 render cells that are too large to fit on a single page.)
1679 The whole of axis !AXIS is included. (The caller may follow up with another
1680 call to render_page_select() to select on !AXIS to select on that axis as
1683 The caller retains ownership of PAGE, which is not modified. */
1684 static struct render_page *
1685 render_page_select (const struct render_page *page, enum table_axis axis,
1686 int z0, int p0, int z1, int p1)
1688 struct render_page_selection s;
1689 enum table_axis a = axis;
1690 enum table_axis b = !a;
1691 struct render_page *subpage;
1692 struct render_overflow *ro;
1698 /* Optimize case where all of PAGE is selected by just incrementing the
1700 if (z0 == page->h[a][0] && p0 == 0
1701 && z1 == page->n[a] - page->h[a][1] && p1 == 0)
1703 struct render_page *page_rw = CONST_CAST (struct render_page *, page);
1708 /* Allocate subpage. */
1709 subpage = render_page_allocate (page->params,
1710 table_select_slice (
1711 table_ref (page->table),
1714 /* An edge is cut off if it was cut off in PAGE or if we're trimming pixels
1715 off that side of the page and there are no headers. */
1716 subpage->is_edge_cutoff[a][0] =
1717 subpage->h[a][0] == 0 && (p0 || (z0 == 0 && page->is_edge_cutoff[a][0]));
1718 subpage->is_edge_cutoff[a][1] =
1719 subpage->h[a][1] == 0 && (p1 || (z1 == page->n[a]
1720 && page->is_edge_cutoff[a][1]));
1721 subpage->is_edge_cutoff[b][0] = page->is_edge_cutoff[b][0];
1722 subpage->is_edge_cutoff[b][1] = page->is_edge_cutoff[b][1];
1724 /* Select join crossings from PAGE into subpage. */
1725 jc = subpage->join_crossing[a];
1726 for (z = 0; z < page->h[a][0]; z++)
1727 *jc++ = page->join_crossing[a][z];
1728 for (z = z0; z <= z1; z++)
1729 *jc++ = page->join_crossing[a][z];
1730 for (z = page->n[a] - page->h[a][1]; z < page->n[a]; z++)
1731 *jc++ = page->join_crossing[a][z];
1732 assert (jc == &subpage->join_crossing[a][subpage->n[a] + 1]);
1734 memcpy (subpage->join_crossing[b], page->join_crossing[b],
1735 (subpage->n[b] + 1) * sizeof **subpage->join_crossing);
1737 /* Select widths from PAGE into subpage. */
1739 dcp = subpage->cp[a];
1741 for (z = 0; z <= rule_ofs (subpage->h[a][0]); z++, dcp++)
1743 if (z == 0 && subpage->is_edge_cutoff[a][0])
1746 dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1748 for (z = cell_ofs (z0); z <= cell_ofs (z1 - 1); z++, dcp++)
1750 dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1751 if (z == cell_ofs (z0))
1754 if (page->h[a][0] && page->h[a][1])
1755 dcp[1] += page->join_crossing[a][z / 2];
1757 if (z == cell_ofs (z1 - 1))
1760 for (z = rule_ofs_r (page, a, subpage->h[a][1]);
1761 z <= rule_ofs_r (page, a, 0); z++, dcp++)
1763 if (z == rule_ofs_r (page, a, 0) && subpage->is_edge_cutoff[a][1])
1766 dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1768 assert (dcp == &subpage->cp[a][2 * subpage->n[a] + 1]);
1770 for (z = 0; z < page->n[b] * 2 + 2; z++)
1771 subpage->cp[b][z] = page->cp[b][z];
1773 /* Add new overflows. */
1781 s.subpage = subpage;
1783 if (!page->h[a][0] || z0 > page->h[a][0] || p0)
1784 for (z = 0; z < page->n[b]; )
1786 struct table_cell cell;
1787 int d[TABLE_N_AXES];
1794 table_get_cell (page->table, d[H], d[V], &cell);
1795 overflow0 = p0 || cell.d[a][0] < z0;
1796 overflow1 = cell.d[a][1] > z1 || (cell.d[a][1] == z1 && p1);
1797 if (overflow0 || overflow1)
1799 ro = insert_overflow (&s, &cell);
1803 ro->overflow[a][0] += p0 + axis_width (
1804 page, a, cell_ofs (cell.d[a][0]), cell_ofs (z0));
1805 if (page->h[a][0] && page->h[a][1])
1806 ro->overflow[a][0] -= page->join_crossing[a][cell.d[a][0]
1812 ro->overflow[a][1] += p1 + axis_width (
1813 page, a, cell_ofs (z1), cell_ofs (cell.d[a][1]));
1814 if (page->h[a][0] && page->h[a][1])
1815 ro->overflow[a][1] -= page->join_crossing[a][cell.d[a][1]];
1819 table_cell_free (&cell);
1822 if (!page->h[a][1] || z1 < page->n[a] - page->h[a][1] || p1)
1823 for (z = 0; z < page->n[b]; )
1825 struct table_cell cell;
1826 int d[TABLE_N_AXES];
1830 table_get_cell (page->table, d[H], d[V], &cell);
1831 if ((cell.d[a][1] > z1 || (cell.d[a][1] == z1 && p1))
1832 && find_overflow_for_cell (&s, &cell) == NULL)
1834 ro = insert_overflow (&s, &cell);
1835 ro->overflow[a][1] += p1 + axis_width (page, a, cell_ofs (z1),
1836 cell_ofs (cell.d[a][1]));
1839 table_cell_free (&cell);
1842 /* Copy overflows from PAGE into subpage. */
1843 HMAP_FOR_EACH (ro, struct render_overflow, node, &page->overflows)
1845 struct table_cell cell;
1847 table_get_cell (page->table, ro->d[H], ro->d[V], &cell);
1848 if (cell.d[a][1] > z0 && cell.d[a][0] < z1
1849 && find_overflow_for_cell (&s, &cell) == NULL)
1850 insert_overflow (&s, &cell);
1851 table_cell_free (&cell);
1857 /* Given CELL, a table_cell within S->page, stores in SUBCELL the (x,y)
1858 coordinates of the top-left cell as it will appear in S->subpage.
1860 CELL must actually intersect the region of S->page that is being selected
1861 by render_page_select() or the results will not make any sense. */
1863 cell_to_subpage (struct render_page_selection *s,
1864 const struct table_cell *cell, int subcell[TABLE_N_AXES])
1866 enum table_axis a = s->a;
1867 enum table_axis b = s->b;
1868 int ha0 = s->subpage->h[a][0];
1870 subcell[a] = MAX (cell->d[a][0] - s->z0 + ha0, ha0);
1871 subcell[b] = cell->d[b][0];
1874 /* Given CELL, a table_cell within S->page, returns the render_overflow for
1875 that cell in S->subpage, if there is one, and a null pointer otherwise.
1877 CELL must actually intersect the region of S->page that is being selected
1878 by render_page_select() or the results will not make any sense. */
1879 static const struct render_overflow *
1880 find_overflow_for_cell (struct render_page_selection *s,
1881 const struct table_cell *cell)
1885 cell_to_subpage (s, cell, subcell);
1886 return find_overflow (s->subpage, subcell[H], subcell[V]);
1889 /* Given CELL, a table_cell within S->page, inserts a render_overflow for that
1890 cell in S->subpage (which must not already exist). Initializes the new
1891 render_overflow's 'overflow' member from the overflow for CELL in S->page,
1894 CELL must actually intersect the region of S->page that is being selected
1895 by render_page_select() or the results will not make any sense. */
1896 static struct render_overflow *
1897 insert_overflow (struct render_page_selection *s,
1898 const struct table_cell *cell)
1900 const struct render_overflow *old;
1901 struct render_overflow *of;
1903 of = xzalloc (sizeof *of);
1904 cell_to_subpage (s, cell, of->d);
1905 hmap_insert (&s->subpage->overflows, &of->node,
1906 hash_cell (of->d[H], of->d[V]));
1908 old = find_overflow (s->page, cell->d[H][0], cell->d[V][0]);
1910 memcpy (of->overflow, old->overflow, sizeof of->overflow);