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/pivot-output.h"
30 #include "output/pivot-table.h"
31 #include "output/render.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 /* Region of 'table' to render.
61 The horizontal cells rendered are the leftmost h[H][0], then
62 r[H][0] through r[H][1], exclusive, then the rightmost h[H][1].
64 The vertical cells rendered are the topmost h[V][0], then r[V][0]
65 through r[V][1], exclusive, then the bottommost h[V][1].
67 n[H] = h[H][0] + (r[H][1] - r[H][0]) + h[H][1]
68 n[V] = h[V][0] + (r[V][1] - r[V][0]) + h[V][1]
70 int h[TABLE_N_AXES][2];
71 int r[TABLE_N_AXES][2];
76 cp[H] represents x positions within the table.
78 cp[H][1] = the width of the leftmost vertical rule.
79 cp[H][2] = cp[H][1] + the width of the leftmost column.
80 cp[H][3] = cp[H][2] + the width of the second-from-left vertical rule.
82 cp[H][2 * n[H]] = x position of the rightmost vertical rule.
83 cp[H][2 * n[H] + 1] = total table width including all rules.
85 Similarly, cp[V] represents y positions within the table.
87 cp[V][1] = the height of the topmost horizontal rule.
88 cp[V][2] = cp[V][1] + the height of the topmost row.
89 cp[V][3] = cp[V][2] + the height of the second-from-top horizontal rule.
91 cp[V][2 * n[V]] = y position of the bottommost horizontal rule.
92 cp[V][2 * n[V] + 1] = total table height including all rules.
94 Rules and columns can have width or height 0, in which case consecutive
95 values in this array are equal. */
96 int *cp[TABLE_N_AXES];
98 /* render_break_next() can break a table such that some cells are not fully
99 contained within a render_page. This will happen if a cell is too wide
100 or two tall to fit on a single page, or if a cell spans multiple rows or
101 columns and the page only includes some of those rows or columns.
103 This hash table contains "struct render_overflow"s that represents each
104 such cell that doesn't completely fit on this page.
106 Each overflow cell borders at least one header edge of the table and may
107 border more. (A single table cell that is so large that it fills the
108 entire page can overflow on all four sides!) */
109 struct hmap overflows;
111 /* If a single column (or row) is too wide (or tall) to fit on a page
112 reasonably, then render_break_next() will split a single row or column
113 across multiple render_pages. This member indicates when this has
116 is_edge_cutoff[H][0] is true if pixels have been cut off the left side
117 of the leftmost column in this page, and false otherwise.
119 is_edge_cutoff[H][1] is true if pixels have been cut off the right side
120 of the rightmost column in this page, and false otherwise.
122 is_edge_cutoff[V][0] and is_edge_cutoff[V][1] are similar for the top
123 and bottom of the table.
125 The effect of is_edge_cutoff is to prevent rules along the edge in
126 question from being rendered.
128 When is_edge_cutoff is true for a given edge, the 'overflows' hmap will
129 contain a node for each cell along that edge. */
130 bool is_edge_cutoff[TABLE_N_AXES][2];
132 /* If part of a joined cell would be cut off by breaking a table along
133 'axis' at the rule with offset 'z' (where 0 <= z <= n[axis]), then
134 join_crossing[axis][z] is the thickness of the rule that would be cut
137 This is used to know to allocate extra space for breaking at such a
138 position, so that part of the cell's content is not lost.
140 This affects breaking a table only when headers are present. When
141 headers are not present, the rule's thickness is used for cell content,
142 so no part of the cell's content is lost (and in fact it is duplicated
143 across both pages). */
144 int *join_crossing[TABLE_N_AXES];
146 /* Minimum and maximum widths of columns based on headings.
148 For this purpose, a table has the following three regions:
150 +------------------+-------------------------------------------------+
151 | | column headings |
152 | +-------------------------------------------------+
155 | row headings | data |
158 +------------------+-------------------------------------------------+
160 - width_ranges[TABLE_HORZ] controls the minimum and maximum width that
161 columns in the column headings will be based on the column headings
162 themselves. That is, these columns will have width at least
163 width_ranges[TABLE_HORZ][0] wide, and no more than
164 width_ranges[TABLE_HORZ][1] unless the data requires it.
166 - width_ranges[TABLE_VERT] controls the minimum and maximum width that
167 columns in the corner and row headings will be based on the corner and
168 row headings themselves. That is, these columns will have width at
169 least width_ranges[TABLE_VERT][0] wide, and no more than
170 width_ranges[TABLE_VERT][1]. (The corner and row headings don't have
171 data in their columns so data can't affect their widths.)
173 int width_ranges[TABLE_N_AXES][2];
176 static struct render_page *render_page_create (const struct render_params *,
177 struct table *, int min_width,
178 const struct pivot_table_look *);
180 struct render_page *render_page_ref (const struct render_page *page_);
181 static void render_page_unref (struct render_page *);
183 /* Returns the offset in struct render_page's cp[axis] array of the rule with
184 index RULE_IDX. That is, if RULE_IDX is 0, then the offset is that of the
185 leftmost or topmost rule; if RULE_IDX is 1, then the offset is that of the
186 next rule to the right (or below); and so on. */
188 rule_ofs (int rule_idx)
193 /* Returns the offset in struct render_page's cp[axis] array of the rule with
194 index RULE_IDX_R, which counts from the right side (or bottom) of the page
195 left (or up), according to whether AXIS is H or V, respectively. That is,
196 if RULE_IDX_R is 0, then the offset is that of the rightmost or bottommost
197 rule; if RULE_IDX is 1, then the offset is that of the next rule to the left
198 (or above); and so on. */
200 rule_ofs_r (const struct render_page *page, int axis, int rule_idx_r)
202 return (page->n[axis] - rule_idx_r) * 2;
205 /* Returns the offset in struct render_page's cp[axis] array of the cell with
206 index CELL_IDX. That is, if CELL_IDX is 0, then the offset is that of the
207 leftmost or topmost cell; if CELL_IDX is 1, then the offset is that of the
208 next cell to the right (or below); and so on. */
210 cell_ofs (int cell_idx)
212 return cell_idx * 2 + 1;
215 /* Returns the width of PAGE along AXIS from OFS0 to OFS1, exclusive. */
217 axis_width (const struct render_page *page, int axis, int ofs0, int ofs1)
219 return page->cp[axis][ofs1] - page->cp[axis][ofs0];
222 /* Returns the total width of PAGE along AXIS. */
224 table_width (const struct render_page *page, int axis)
226 return page->cp[axis][2 * page->n[axis] + 1];
229 /* Returns the width of the headers in PAGE along AXIS. */
231 headers_width (const struct render_page *page, int axis)
233 int h0 = page->h[axis][0];
234 int w0 = axis_width (page, axis, rule_ofs (0), cell_ofs (h0));
235 int n = page->n[axis];
236 int h1 = page->h[axis][1];
237 int w1 = axis_width (page, axis, rule_ofs_r (page, axis, h1), cell_ofs (n));
241 /* Returns the width of cell X along AXIS in PAGE. */
243 cell_width (const struct render_page *page, int axis, int x)
245 return axis_width (page, axis, cell_ofs (x), cell_ofs (x) + 1);
248 /* Returns the width of rule X along AXIS in PAGE. */
250 rule_width (const struct render_page *page, int axis, int x)
252 return axis_width (page, axis, rule_ofs (x), rule_ofs (x) + 1);
255 /* Returns the width of rule X along AXIS in PAGE. */
257 rule_width_r (const struct render_page *page, int axis, int x)
259 int ofs = rule_ofs_r (page, axis, x);
260 return axis_width (page, axis, ofs, ofs + 1);
263 /* Returns the width of cells X0 through X1, exclusive, along AXIS in PAGE. */
265 joined_width (const struct render_page *page, int axis, int x0, int x1)
267 return axis_width (page, axis, cell_ofs (x0), cell_ofs (x1) - 1);
270 /* Returns the width of the widest cell, excluding headers, along AXIS in
273 max_cell_width (const struct render_page *page, int axis)
275 int n = page->n[axis];
276 int x0 = page->h[axis][0];
277 int x1 = n - page->h[axis][1];
280 for (int x = x0; x < x1; x++)
282 int w = cell_width (page, axis, x);
289 /* A cell that doesn't completely fit on the render_page. */
290 struct render_overflow
292 struct hmap_node node; /* In render_page's 'overflows' hmap. */
294 /* Occupied region of page.
296 d[H][0] is the leftmost column.
297 d[H][1] is the rightmost column, plus 1.
298 d[V][0] is the top row.
299 d[V][1] is the bottom row, plus 1.
301 The cell in its original table might occupy a larger region. This
302 member reflects the size of the cell in the current render_page, after
303 trimming off any rows or columns due to page-breaking. */
306 /* The space that has been trimmed off the cell:
308 overflow[H][0]: space trimmed off its left side.
309 overflow[H][1]: space trimmed off its right side.
310 overflow[V][0]: space trimmed off its top.
311 overflow[V][1]: space trimmed off its bottom.
313 During rendering, this information is used to position the rendered
314 portion of the cell within the available space.
316 When a cell is rendered, sometimes it is permitted to spill over into
317 space that is ordinarily reserved for rules. Either way, this space is
318 still included in overflow values.
320 Suppose, for example, that a cell that joins 2 columns has a width of 60
321 pixels and content "abcdef", that the 2 columns that it joins have
322 widths of 20 and 30 pixels, respectively, and that therefore the rule
323 between the two joined columns has a width of 10 (20 + 10 + 30 = 60).
324 It might render like this, if each character is 10x10, and showing a few
325 extra table cells for context:
333 If this render_page is broken at the rule that separates "gh" from
334 "ijk", then the page that contains the left side of the "abcdef" cell
335 will have overflow[H][1] of 10 + 30 = 40 for its portion of the cell,
336 and the page that contains the right side of the cell will have
337 overflow[H][0] of 20 + 10 = 30. The two resulting pages would look like
355 int overflow[TABLE_N_AXES][2];
358 /* Returns a hash value for (,Y). */
360 hash_cell (int x, int y)
362 return hash_int (x + (y << 16), 0);
365 /* Searches PAGE's set of render_overflow for one whose top-left cell is
366 (X,Y). Returns it, if there is one, otherwise a null pointer. */
367 static const struct render_overflow *
368 find_overflow (const struct render_page *page, int x, int y)
370 if (!hmap_is_empty (&page->overflows))
372 const struct render_overflow *of;
374 HMAP_FOR_EACH_WITH_HASH (of, struct render_overflow, node,
375 hash_cell (x, y), &page->overflows)
376 if (x == of->d[H] && y == of->d[V])
383 /* Row or column dimensions. Used to figure the size of a table in
384 render_page_create() and discarded after that. */
387 /* Width without considering rows (or columns) that span more than one (or
391 /* Width taking spanned rows (or columns) into consideration. */
395 /* Modifies the 'width' members of the N elements of ROWS so that their sum,
396 when added to rule widths RULES[1] through RULES[N - 1] inclusive, is at
399 distribute_spanned_width (int width,
400 struct render_row *rows, const int *rules, int n)
402 /* Sum up the unspanned widths of the N rows for use as weights. */
403 int total_unspanned = 0;
404 for (int x = 0; x < n; x++)
405 total_unspanned += rows[x].unspanned;
406 for (int x = 0; x < n - 1; x++)
407 total_unspanned += rules[x + 1];
408 if (total_unspanned >= width)
411 /* The algorithm used here is based on the following description from HTML 4:
413 For cells that span multiple columns, a simple approach consists of
414 apportioning the min/max widths evenly to each of the constituent
415 columns. A slightly more complex approach is to use the min/max
416 widths of unspanned cells to weight how spanned widths are
417 apportioned. Experiments suggest that a blend of the two approaches
418 gives good results for a wide range of tables.
420 We blend the two approaches half-and-half, except that we cannot use the
421 unspanned weights when 'total_unspanned' is 0 (because that would cause a
424 The calculation we want to do is this:
427 w1 = width * (column's unspanned width) / (total unspanned width)
428 (column's width) = (w0 + w1) / 2
430 We implement it as a precise calculation in integers by multiplying w0 and
431 w1 by the common denominator of all three calculations (d), dividing that
432 out in the column width calculation, and then keeping the remainder for
435 (We actually compute the unspanned width of a column as twice the
436 unspanned width, plus the width of the rule on the left, plus the width of
437 the rule on the right. That way each rule contributes to both the cell on
438 its left and on its right.)
440 long long int d0 = n;
441 long long int d1 = 2LL * MAX (total_unspanned, 1);
442 long long int d = d0 * d1;
443 if (total_unspanned > 0)
445 long long int w = d / 2;
446 for (int x = 0; x < n; x++)
449 if (total_unspanned > 0)
451 long long int unspanned = rows[x].unspanned * 2LL;
453 unspanned += rules[x + 1];
455 unspanned += rules[x];
456 w += width * unspanned * d0;
459 rows[x].width = MAX (rows[x].width, w / d);
460 w -= rows[x].width * d;
464 /* Initializes PAGE->cp[AXIS] from the row widths in ROWS and the rule widths
467 accumulate_row_widths (const struct render_page *page, enum table_axis axis,
468 const struct render_row *rows, const int *rules)
470 int n = page->n[axis];
471 int *cp = page->cp[axis];
473 for (int z = 0; z < n; z++)
475 cp[1] = cp[0] + rules[z];
476 cp[2] = cp[1] + rows[z].width;
479 cp[1] = cp[0] + rules[n];
482 /* Returns the sum of widths of the N ROWS and N+1 RULES. */
484 calculate_table_width (int n, const struct render_row *rows, int *rules)
487 for (int x = 0; x < n; x++)
488 width += rows[x].width;
489 for (int x = 0; x <= n; x++)
495 /* Rendering utility functions. */
497 /* Returns the width of the rule in TABLE that is at offset Z along axis A, if
498 rendered with PARAMS. */
500 measure_rule (const struct render_params *params, const struct table *table,
501 enum table_axis a, int z)
503 enum table_axis b = !a;
505 /* Determine all types of rules that are present, as a bitmap in 'rules'
506 where rule type 't' is present if bit 2**t is set. */
507 unsigned int rules = 0;
510 for (d[b] = 0; d[b] < table->n[b]; d[b]++)
511 rules |= 1u << table_get_rule (table, a, d[H], d[V]).stroke;
513 /* Turn off TABLE_STROKE_NONE because it has width 0 and we needn't bother.
514 However, if the device doesn't support margins, make sure that there is at
515 least a small gap between cells (but we don't need any at the left or
516 right edge of the table). */
517 if (rules & (1u << TABLE_STROKE_NONE))
519 rules &= ~(1u << TABLE_STROKE_NONE);
520 if (z > 0 && z < table->n[a] && !params->supports_margins && a == H)
521 rules |= 1u << TABLE_STROKE_SOLID;
524 /* Calculate maximum width of the rules that are present. */
526 for (size_t i = 0; i < TABLE_N_STROKES; i++)
527 if (rules & (1u << i))
528 width = MAX (width, params->line_widths[i]);
532 /* Allocates and returns a new render_page using PARAMS and TABLE. Allocates
533 space for rendering a table with dimensions given in N. The caller must
534 initialize most of the members itself. */
535 static struct render_page *
536 render_page_allocate__ (const struct render_params *params,
537 struct table *table, int n[TABLE_N_AXES])
539 struct render_page *page = xmalloc (sizeof *page);
540 page->params = params;
546 for (int i = 0; i < TABLE_N_AXES; i++)
548 page->cp[i] = xcalloc ((2 * n[i] + 2) , sizeof *page->cp[i]);
549 page->join_crossing[i] = xcalloc ((n[i] + 1) , sizeof *page->join_crossing[i]);
552 hmap_init (&page->overflows);
553 memset (page->is_edge_cutoff, 0, sizeof page->is_edge_cutoff);
558 /* Allocates and returns a new render_page using PARAMS and TABLE. Allocates
559 space for all of the members of the new page, but the caller must initialize
560 the 'cp' member itself. */
561 static struct render_page *
562 render_page_allocate (const struct render_params *params, struct table *table)
564 struct render_page *page = render_page_allocate__ (params, table, table->n);
565 for (enum table_axis a = 0; a < TABLE_N_AXES; a++)
567 page->h[a][0] = table->h[a][0];
568 page->h[a][1] = table->h[a][1];
569 page->r[a][0] = table->h[a][0];
570 page->r[a][1] = table->n[a] - table->h[a][1];
575 /* Allocates and returns a new render_page for PARAMS and TABLE, initializing
576 cp[H] in the new page from ROWS and RULES. The caller must still initialize
578 static struct render_page *
579 create_page_with_exact_widths (const struct render_params *params,
581 const struct render_row *rows, int *rules)
583 struct render_page *page = render_page_allocate (params, table);
584 accumulate_row_widths (page, H, rows, rules);
588 /* Allocates and returns a new render_page for PARAMS and TABLE.
590 Initializes cp[H] in the new page by setting the width of each row 'i' to
591 somewhere between the minimum cell width ROW_MIN[i].width and the maximum
592 ROW_MAX[i].width. Sets the width of rules to those in RULES.
594 W_MIN is the sum of ROWS_MIN[].width.
596 W_MAX is the sum of ROWS_MAX[].width.
598 The caller must still initialize cp[V]. */
599 static struct render_page *
600 create_page_with_interpolated_widths (const struct render_params *params,
602 const struct render_row *rows_min,
603 const struct render_row *rows_max,
604 int w_min, int w_max, const int *rules)
606 const int n = table->n[H];
607 const long long int avail = params->size[H] - w_min;
608 const long long int wanted = w_max - w_min;
612 struct render_page *page = render_page_allocate (params, table);
614 int *cph = page->cp[H];
616 long long int w = wanted / 2;
617 for (int x = 0; x < n; x++)
619 w += avail * (rows_max[x].width - rows_min[x].width);
620 int extra = w / wanted;
623 cph[1] = cph[0] + rules[x];
624 cph[2] = cph[1] + rows_min[x].width + extra;
627 cph[1] = cph[0] + rules[n];
629 assert (page->cp[H][n * 2 + 1] == params->size[H]);
634 set_join_crossings (struct render_page *page, enum table_axis axis,
635 const struct table_cell *cell, int *rules)
637 for (int z = cell->d[axis][0] + 1; z <= cell->d[axis][1] - 1; z++)
638 page->join_crossing[axis][z] = rules[z];
641 /* Maps a contiguous range of cells from a page to the underlying table along
642 the horizontal or vertical dimension. */
645 int p0; /* First ordinate in the page. */
646 int t0; /* First ordinate in the table. */
647 int n; /* Number of ordinates in page and table. */
650 /* Initializes M to a mapping from PAGE to PAGE->table along axis A. The
651 mapping includes ordinate Z (in PAGE). */
653 get_map (const struct render_page *page, enum table_axis a, int z,
656 if (z < page->h[a][0])
660 m->n = page->h[a][0];
662 else if (z < page->n[a] - page->h[a][1])
664 m->p0 = page->h[a][0];
665 m->t0 = page->r[a][0];
666 m->n = page->r[a][1] - page->r[a][0];
670 m->p0 = page->n[a] - page->h[a][1];
671 m->t0 = page->table->n[a] - page->table->h[a][1];
672 m->n = page->h[a][1];
676 /* Initializes CELL with the contents of the table cell at column X and row Y
677 within PAGE. When CELL is no longer needed, the caller is responsible for
678 freeing it by calling table_cell_free(CELL).
680 The caller must ensure that CELL is destroyed before TABLE is unref'ed.
682 This is equivalent to table_get_cell(), except X and Y are in terms of the
683 page's rows and columns rather than the underlying table's. */
685 render_get_cell (const struct render_page *page, int x, int y,
686 struct table_cell *cell)
688 int d[TABLE_N_AXES] = { [H] = x, [V] = y };
689 struct map map[TABLE_N_AXES];
691 for (enum table_axis a = 0; a < TABLE_N_AXES; a++)
693 struct map *m = &map[a];
694 get_map (page, a, d[a], m);
695 d[a] += m->t0 - m->p0;
697 table_get_cell (page->table, d[H], d[V], cell);
699 for (enum table_axis a = 0; a < TABLE_N_AXES; a++)
701 struct map *m = &map[a];
703 for (int i = 0; i < 2; i++)
704 cell->d[a][i] -= m->t0 - m->p0;
705 cell->d[a][0] = MAX (cell->d[a][0], m->p0);
706 cell->d[a][1] = MIN (cell->d[a][1], m->p0 + m->n);
710 /* Creates and returns a new render_page for rendering TABLE with the given
711 LOOK on a device described by PARAMS.
713 The new render_page will be suitable for rendering on a device whose page
714 size is PARAMS->size, but the caller is responsible for actually breaking it
715 up to fit on such a device, using the render_break abstraction. */
716 static struct render_page *
717 render_page_create (const struct render_params *params, struct table *table,
718 int min_width, const struct pivot_table_look *look)
722 int nc = table->n[H];
723 int nr = table->n[V];
725 /* Figure out rule widths. */
726 int *rules[TABLE_N_AXES];
727 for (enum table_axis axis = 0; axis < TABLE_N_AXES; axis++)
729 int n = table->n[axis] + 1;
731 rules[axis] = xnmalloc (n, sizeof *rules);
732 for (int z = 0; z < n; z++)
733 rules[axis][z] = measure_rule (params, table, axis, z);
736 int col_heading_width_range[2];
737 int row_heading_width_range[2];
738 for (int i = 0; i < 2; i++)
739 col_heading_width_range[i] = look->col_heading_width_range[i] * params->px_size;
740 for (int i = 0; i < 2; i++)
741 row_heading_width_range[i] = look->row_heading_width_range[i] * params->px_size;
743 /* Calculate minimum and maximum widths of cells that do not
744 span multiple columns. */
745 struct render_row *columns[2];
746 for (int i = 0; i < 2; i++)
747 columns[i] = xcalloc (nc, sizeof *columns[i]);
748 for (int y = 0; y < nr; y++)
749 for (int x = 0; x < nc;)
751 struct table_cell cell;
753 table_get_cell (table, x, y, &cell);
754 if (y == cell.d[V][0])
756 if (table_cell_colspan (&cell) == 1)
759 params->ops->measure_cell_width (params->aux, &cell,
764 const int *wr = (x < table->h[H][0] ? row_heading_width_range
765 : y < table->h[V][0] ? col_heading_width_range
775 else if (w[1] > wr[1])
784 for (int i = 0; i < 2; i++)
785 if (columns[i][x].unspanned < w[i])
786 columns[i][x].unspanned = w[i];
792 /* Distribute widths of spanned columns. */
793 for (int i = 0; i < 2; i++)
794 for (int x = 0; x < nc; x++)
795 columns[i][x].width = columns[i][x].unspanned;
796 for (int y = 0; y < nr; y++)
797 for (int x = 0; x < nc;)
799 struct table_cell cell;
801 table_get_cell (table, x, y, &cell);
802 if (y == cell.d[V][0] && table_cell_colspan (&cell) > 1)
806 params->ops->measure_cell_width (params->aux, &cell,
808 for (int i = 0; i < 2; i++)
809 distribute_spanned_width (w[i],
810 &columns[i][cell.d[H][0]],
811 &rules[H][cell.d[H][0]],
812 table_cell_colspan (&cell));
817 for (int i = 0; i < 2; i++)
818 distribute_spanned_width (min_width, &columns[i][0], rules[H], nc);
820 /* In pathological cases, spans can cause the minimum width of a column to
821 exceed the maximum width. This bollixes our interpolation algorithm
822 later, so fix it up. */
823 for (int i = 0; i < nc; i++)
824 if (columns[MIN][i].width > columns[MAX][i].width)
825 columns[MAX][i].width = columns[MIN][i].width;
827 /* Decide final column widths. */
829 for (int i = 0; i < 2; i++)
830 table_widths[i] = calculate_table_width (table->n[H],
831 columns[i], rules[H]);
833 struct render_page *page;
834 if (table_widths[MAX] <= params->size[H])
836 /* Fits even with maximum widths. Use them. */
837 page = create_page_with_exact_widths (params, table, columns[MAX],
840 else if (table_widths[MIN] <= params->size[H])
842 /* Fits with minimum widths, so distribute the leftover space. */
843 page = create_page_with_interpolated_widths (
844 params, table, columns[MIN], columns[MAX],
845 table_widths[MIN], table_widths[MAX], rules[H]);
849 /* Doesn't fit even with minimum widths. Assign minimums for now, and
850 later we can break it horizontally into multiple pages. */
851 page = create_page_with_exact_widths (params, table, columns[MIN],
855 /* Calculate heights of cells that do not span multiple rows. */
856 struct render_row *rows = XCALLOC (nr, struct render_row);
857 for (int y = 0; y < nr; y++)
858 for (int x = 0; x < nc;)
860 struct render_row *r = &rows[y];
861 struct table_cell cell;
863 render_get_cell (page, x, y, &cell);
864 if (y == cell.d[V][0])
866 if (table_cell_rowspan (&cell) == 1)
868 int w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
869 int h = params->ops->measure_cell_height (params->aux,
871 if (h > r->unspanned)
872 r->unspanned = r->width = h;
875 set_join_crossings (page, V, &cell, rules[V]);
877 if (table_cell_colspan (&cell) > 1)
878 set_join_crossings (page, H, &cell, rules[H]);
882 for (int i = 0; i < 2; i++)
885 /* Distribute heights of spanned rows. */
886 for (int y = 0; y < nr; y++)
887 for (int x = 0; x < nc;)
889 struct table_cell cell;
891 render_get_cell (page, x, y, &cell);
892 if (y == cell.d[V][0] && table_cell_rowspan (&cell) > 1)
894 int w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
895 int h = params->ops->measure_cell_height (params->aux, &cell, w);
896 distribute_spanned_width (h,
898 &rules[V][cell.d[V][0]],
899 table_cell_rowspan (&cell));
904 /* Decide final row heights. */
905 accumulate_row_widths (page, V, rows, rules[V]);
908 /* Measure headers. If they are "too big", get rid of them. */
909 for (enum table_axis axis = 0; axis < TABLE_N_AXES; axis++)
911 int hw = headers_width (page, axis);
912 if (hw * 2 >= page->params->size[axis]
913 || hw + max_cell_width (page, axis) > page->params->size[axis])
915 page->h[axis][0] = page->h[axis][1] = 0;
916 page->r[axis][0] = 0;
917 page->r[axis][1] = page->n[axis];
927 /* Increases PAGE's reference count. */
929 render_page_ref (const struct render_page *page_)
931 struct render_page *page = CONST_CAST (struct render_page *, page_);
936 /* Decreases PAGE's reference count and destroys PAGE if this causes the
937 reference count to fall to zero. */
939 render_page_unref (struct render_page *page)
941 if (page != NULL && --page->ref_cnt == 0)
943 struct render_overflow *overflow, *next;
944 HMAP_FOR_EACH_SAFE (overflow, next, struct render_overflow, node,
947 hmap_destroy (&page->overflows);
949 table_unref (page->table);
951 for (int i = 0; i < TABLE_N_AXES; ++i)
953 free (page->join_crossing[i]);
961 /* Returns the size of PAGE along AXIS. (This might be larger than the page
962 size specified in the parameters passed to render_page_create(). Use a
963 render_break to break up a render_page into page-sized chunks.) */
965 render_page_get_size (const struct render_page *page, enum table_axis axis)
967 return page->cp[axis][page->n[axis] * 2 + 1];
971 render_page_get_best_breakpoint (const struct render_page *page, int height)
973 /* If there's no room for at least the top row and the rules above and below
974 it, don't include any of the table. */
975 if (page->cp[V][3] > height)
978 /* Otherwise include as many rows and rules as we can. */
979 for (int y = 5; y <= 2 * page->n[V] + 1; y += 2)
980 if (page->cp[V][y] > height)
981 return page->cp[V][y - 2];
985 /* Drawing render_pages. */
987 /* This is like table_get_rule() except that D is in terms of the page's rows
988 and column rather than the underlying table's. */
989 static struct table_border_style
990 get_rule (const struct render_page *page, enum table_axis axis,
991 const int d_[TABLE_N_AXES])
993 int d[TABLE_N_AXES] = { d_[0] / 2, d_[1] / 2 };
996 enum table_axis a = axis;
997 if (d[a] < page->h[a][0])
999 else if (d[a] <= page->n[a] - page->h[a][1])
1001 if (page->h[a][0] && d[a] == page->h[a][0])
1003 else if (page->h[a][1] && d[a] == page->n[a] - page->h[a][1])
1004 d2 = page->table->n[a] - page->h[a][1];
1005 d[a] += page->r[a][0] - page->h[a][0];
1008 d[a] += ((page->table->n[a] - page->table->h[a][1])
1009 - (page->n[a] - page->h[a][1]));
1011 enum table_axis b = !axis;
1013 get_map (page, b, d[b], &m);
1014 d[b] += m.t0 - m.p0;
1016 struct table_border_style border
1017 = table_get_rule (page->table, axis, d[H], d[V]);
1021 struct table_border_style border2 = table_get_rule (page->table, axis,
1023 border.stroke = table_stroke_combine (border.stroke, border2.stroke);
1035 render_direction_rtl (void)
1037 /* TRANSLATORS: Do not translate this string. If the script of your language
1038 reads from right to left (eg Persian, Arabic, Hebrew etc), then replace
1039 this string with "output-direction-rtl". Otherwise either leave it
1040 untranslated or copy it verbatim. */
1041 const char *dir = _("output-direction-ltr");
1042 if (0 == strcmp ("output-direction-rtl", dir))
1045 if (0 != strcmp ("output-direction-ltr", dir))
1046 fprintf (stderr, "This localisation has been incorrectly translated. "
1047 "Complain to the translator.\n");
1053 render_rule (const struct render_page *page, const int ofs[TABLE_N_AXES],
1054 const int d[TABLE_N_AXES])
1056 const struct table_border_style none = { .stroke = TABLE_STROKE_NONE };
1057 struct table_border_style styles[TABLE_N_AXES][2];
1059 for (enum table_axis a = 0; a < TABLE_N_AXES; a++)
1061 enum table_axis b = !a;
1064 || (page->is_edge_cutoff[a][0] && d[a] == 0)
1065 || (page->is_edge_cutoff[a][1] && d[a] == page->n[a] * 2))
1066 styles[a][0] = styles[a][1] = none;
1067 else if (is_rule (d[b]))
1071 int e[TABLE_N_AXES];
1075 styles[a][0] = get_rule (page, a, e);
1078 styles[a][0] = none;
1080 if (d[b] / 2 < page->n[b])
1081 styles[a][1] = get_rule (page, a, d);
1083 styles[a][1] = none;
1086 styles[a][0] = styles[a][1] = get_rule (page, a, d);
1089 if (styles[H][0].stroke != TABLE_STROKE_NONE
1090 || styles[H][1].stroke != TABLE_STROKE_NONE
1091 || styles[V][0].stroke != TABLE_STROKE_NONE
1092 || styles[V][1].stroke != TABLE_STROKE_NONE)
1094 int bb[TABLE_N_AXES][2];
1096 bb[H][0] = ofs[H] + page->cp[H][d[H]];
1097 bb[H][1] = ofs[H] + page->cp[H][d[H] + 1];
1098 if (page->params->rtl)
1100 int temp = bb[H][0];
1101 bb[H][0] = render_page_get_size (page, H) - bb[H][1];
1102 bb[H][1] = render_page_get_size (page, H) - temp;
1104 bb[V][0] = ofs[V] + page->cp[V][d[V]];
1105 bb[V][1] = ofs[V] + page->cp[V][d[V] + 1];
1106 page->params->ops->draw_line (page->params->aux, bb, styles);
1111 render_cell (const struct render_page *page, const int ofs[TABLE_N_AXES],
1112 const struct table_cell *cell)
1114 const bool debugging = false;
1118 if (cell->d[H][0] + 1 == cell->d[H][1])
1119 printf ("%d", cell->d[H][0]);
1121 printf ("%d-%d", cell->d[H][0], cell->d[H][1] - 1);
1123 if (cell->d[V][0] + 1 == cell->d[V][1])
1124 printf ("%d", cell->d[V][0]);
1126 printf ("%d-%d", cell->d[V][0], cell->d[V][1] - 1);
1128 char *value = pivot_value_to_string (cell->value, NULL);
1129 printf (": \"%s\"\n", value);
1133 int bb[TABLE_N_AXES][2];
1134 int clip[TABLE_N_AXES][2];
1136 bb[H][0] = clip[H][0] = ofs[H] + page->cp[H][cell->d[H][0] * 2 + 1];
1137 bb[H][1] = clip[H][1] = ofs[H] + page->cp[H][cell->d[H][1] * 2];
1138 if (page->params->rtl)
1140 int temp = bb[H][0];
1141 bb[H][0] = clip[H][0] = render_page_get_size (page, H) - bb[H][1];
1142 bb[H][1] = clip[H][1] = render_page_get_size (page, H) - temp;
1144 bb[V][0] = clip[V][0] = ofs[V] + page->cp[V][cell->d[V][0] * 2 + 1];
1145 bb[V][1] = clip[V][1] = ofs[V] + page->cp[V][cell->d[V][1] * 2];
1147 enum table_valign valign = cell->cell_style->valign;
1148 int valign_offset = 0;
1149 if (valign != TABLE_VALIGN_TOP)
1151 int height = page->params->ops->measure_cell_height (
1152 page->params->aux, cell, bb[H][1] - bb[H][0]);
1153 int extra = bb[V][1] - bb[V][0] - height;
1156 if (valign == TABLE_VALIGN_CENTER)
1158 valign_offset += extra;
1162 const struct render_overflow *of = find_overflow (
1163 page, cell->d[H][0], cell->d[V][0]);
1165 for (enum table_axis axis = 0; axis < TABLE_N_AXES; axis++)
1167 if (of->overflow[axis][0])
1169 bb[axis][0] -= of->overflow[axis][0];
1170 if (cell->d[axis][0] == 0 && !page->is_edge_cutoff[axis][0])
1171 clip[axis][0] = ofs[axis] + page->cp[axis][cell->d[axis][0] * 2];
1173 if (of->overflow[axis][1])
1175 bb[axis][1] += of->overflow[axis][1];
1176 if (cell->d[axis][1] == page->n[axis]
1177 && !page->is_edge_cutoff[axis][1])
1178 clip[axis][1] = ofs[axis] + page->cp[axis][cell->d[axis][1] * 2
1183 int spill[TABLE_N_AXES][2];
1184 for (enum table_axis axis = 0; axis < TABLE_N_AXES; axis++)
1186 spill[axis][0] = rule_width (page, axis, cell->d[axis][0]) / 2;
1187 spill[axis][1] = rule_width (page, axis, cell->d[axis][1]) / 2;
1190 int color_idx = (cell->d[V][0] < page->h[V][0]
1191 || page->n[V] - (cell->d[V][0] + 1) < page->h[V][1]
1193 : (cell->d[V][0] - page->h[V][0]) & 1);
1194 page->params->ops->draw_cell (page->params->aux, cell, color_idx,
1195 bb, valign_offset, spill, clip);
1198 /* Draws the cells of PAGE indicated in BB. */
1200 render_page_draw_cells (const struct render_page *page,
1201 int ofs[TABLE_N_AXES], int bb[TABLE_N_AXES][2])
1203 for (int y = bb[V][0]; y < bb[V][1]; y++)
1204 for (int x = bb[H][0]; x < bb[H][1];)
1205 if (!is_rule (x) && !is_rule (y))
1207 struct table_cell cell;
1209 render_get_cell (page, x / 2, y / 2, &cell);
1210 if (y / 2 == bb[V][0] / 2 || y / 2 == cell.d[V][0])
1211 render_cell (page, ofs, &cell);
1212 x = rule_ofs (cell.d[H][1]);
1217 for (int y = bb[V][0]; y < bb[V][1]; y++)
1218 for (int x = bb[H][0]; x < bb[H][1]; x++)
1219 if (is_rule (x) || is_rule (y))
1221 int d[TABLE_N_AXES];
1224 render_rule (page, ofs, d);
1228 /* Renders PAGE, by calling the 'draw_line' and 'draw_cell' functions from the
1229 render_params provided to render_page_create(). */
1231 render_page_draw (const struct render_page *page, int ofs[TABLE_N_AXES])
1233 int bb[TABLE_N_AXES][2];
1236 bb[H][1] = page->n[H] * 2 + 1;
1238 bb[V][1] = page->n[V] * 2 + 1;
1240 render_page_draw_cells (page, ofs, bb);
1243 /* Returns the greatest value i, 0 <= i < n, such that cp[i] <= x0. */
1245 get_clip_min_extent (int x0, const int cp[], int n)
1252 int middle = low + (high - low) / 2;
1254 if (cp[middle] <= x0)
1266 /* Returns the least value i, 0 <= i < n, such that cp[i] >= x1. */
1268 get_clip_max_extent (int x1, const int cp[], int n)
1275 int middle = low + (high - low) / 2;
1277 if (cp[middle] >= x1)
1278 best = high = middle;
1283 while (best > 0 && cp[best - 1] == cp[best])
1289 /* Renders the cells of PAGE that intersect (X,Y)-(X+W,Y+H), by calling the
1290 'draw_line' and 'draw_cell' functions from the render_params provided to
1291 render_page_create(). */
1293 render_page_draw_region (const struct render_page *page,
1294 int ofs[TABLE_N_AXES], int clip[TABLE_N_AXES][2])
1296 int bb[TABLE_N_AXES][2];
1298 bb[H][0] = get_clip_min_extent (clip[H][0], page->cp[H], page->n[H] * 2 + 1);
1299 bb[H][1] = get_clip_max_extent (clip[H][1], page->cp[H], page->n[H] * 2 + 1);
1300 bb[V][0] = get_clip_min_extent (clip[V][0], page->cp[V], page->n[V] * 2 + 1);
1301 bb[V][1] = get_clip_max_extent (clip[V][1], page->cp[V], page->n[V] * 2 + 1);
1303 render_page_draw_cells (page, ofs, bb);
1306 /* Breaking up tables to fit on a page. */
1308 /* An iterator for breaking render_pages into smaller chunks. */
1311 struct render_page *page; /* Page being broken up. */
1312 enum table_axis axis; /* Axis along which 'page' is being broken. */
1313 int z; /* Next cell along 'axis'. */
1314 int pixel; /* Pixel offset within cell 'z' (usually 0). */
1315 int hw; /* Width of headers of 'page' along 'axis'. */
1318 static int needed_size (const struct render_break *, int cell);
1319 static bool cell_is_breakable (const struct render_break *, int cell);
1320 static struct render_page *render_page_select (const struct render_page *,
1325 /* Initializes render_break B for breaking PAGE along AXIS.
1326 Takes ownership of PAGE. */
1328 render_break_init (struct render_break *b, struct render_page *page,
1329 enum table_axis axis)
1333 b->z = page->h[axis][0];
1335 b->hw = headers_width (page, axis);
1338 /* Initializes B as a render_break structure for which
1339 render_break_has_next() always returns false. */
1341 render_break_init_empty (struct render_break *b)
1344 b->axis = TABLE_HORZ;
1350 /* Frees B and unrefs the render_page that it owns. */
1352 render_break_destroy (struct render_break *b)
1356 render_page_unref (b->page);
1361 /* Returns true if B still has cells that are yet to be returned,
1362 false if all of B's page has been processed. */
1364 render_break_has_next (const struct render_break *b)
1366 const struct render_page *page = b->page;
1367 enum table_axis axis = b->axis;
1369 return page != NULL && b->z < page->n[axis] - page->h[axis][1];
1372 /* Returns a new render_page that is up to SIZE pixels wide along B's axis.
1373 Returns a null pointer if B has already been completely broken up, or if
1374 SIZE is too small to reasonably render any cells. The latter will never
1375 happen if SIZE is at least as large as the page size passed to
1376 render_page_create() along B's axis. */
1377 static struct render_page *
1378 render_break_next (struct render_break *b, int size)
1380 const struct render_page *page = b->page;
1381 enum table_axis axis = b->axis;
1382 struct render_page *subpage;
1384 if (!render_break_has_next (b))
1389 for (z = b->z; z < page->n[axis] - page->h[axis][1]; z++)
1391 int needed = needed_size (b, z + 1);
1394 if (cell_is_breakable (b, z))
1396 /* If there is no right header and we render a partial cell on
1397 the right side of the body, then we omit the rightmost rule of
1398 the body. Otherwise the rendering is deceptive because it
1399 looks like the whole cell is present instead of a partial
1402 This is similar to code for the left side in needed_size(). */
1403 int rule_allowance = (page->h[axis][1]
1405 : rule_width (page, axis, z));
1407 /* The amount that, if we added cell 'z', the rendering would
1408 overfill the allocated 'size'. */
1409 int overhang = needed - size - rule_allowance;
1411 /* The width of cell 'z'. */
1412 int cell_size = cell_width (page, axis, z);
1414 /* The amount trimmed off the left side of 'z',
1415 and the amount left to render. */
1416 int cell_ofs = z == b->z ? b->pixel : 0;
1417 int cell_left = cell_size - cell_ofs;
1419 /* A small but visible width. */
1420 int em = page->params->font_size[axis];
1422 /* If some of the cell remains to render,
1423 and there would still be some of the cell left afterward,
1424 then partially render that much of the cell. */
1425 pixel = (cell_left && cell_left > overhang
1426 ? cell_left - overhang + cell_ofs
1429 /* If there would be only a tiny amount of the cell left after
1430 rendering it partially, reduce the amount rendered slightly
1431 to make the output look a little better. */
1432 if (pixel + em > cell_size)
1433 pixel = MAX (pixel - em, 0);
1435 /* If we're breaking vertically, then consider whether the cells
1436 being broken have a better internal breakpoint than the exact
1437 number of pixels available, which might look bad e.g. because
1438 it breaks in the middle of a line of text. */
1439 if (axis == TABLE_VERT && page->params->ops->adjust_break)
1440 for (int x = 0; x < page->n[H];)
1442 struct table_cell cell;
1444 render_get_cell (page, x, z, &cell);
1445 int w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
1446 int better_pixel = page->params->ops->adjust_break (
1447 page->params->aux, &cell, w, pixel);
1450 if (better_pixel < pixel)
1452 if (better_pixel > (z == b->z ? b->pixel : 0))
1454 pixel = better_pixel;
1457 else if (better_pixel == 0 && z != b->z)
1469 if (z == b->z && !pixel)
1472 subpage = render_page_select (page, axis, b->z, b->pixel,
1474 pixel ? cell_width (page, axis, z) - pixel
1481 /* Returns the width that would be required along B's axis to render a page
1482 from B's current position up to but not including CELL. */
1484 needed_size (const struct render_break *b, int cell)
1486 const struct render_page *page = b->page;
1487 enum table_axis axis = b->axis;
1489 /* Width of left header not including its rightmost rule. */
1490 int size = axis_width (page, axis, 0, rule_ofs (page->h[axis][0]));
1492 /* If we have a pixel offset and there is no left header, then we omit the
1493 leftmost rule of the body. Otherwise the rendering is deceptive because
1494 it looks like the whole cell is present instead of a partial cell.
1496 Otherwise (if there are headers) we will be merging two rules: the
1497 rightmost rule in the header and the leftmost rule in the body. We assume
1498 that the width of a merged rule is the larger of the widths of either rule
1500 if (b->pixel == 0 || page->h[axis][0])
1501 size += MAX (rule_width (page, axis, page->h[axis][0]),
1502 rule_width (page, axis, b->z));
1504 /* Width of body, minus any pixel offset in the leftmost cell. */
1505 size += joined_width (page, axis, b->z, cell) - b->pixel;
1507 /* Width of rightmost rule in body merged with leftmost rule in headers. */
1508 size += MAX (rule_width_r (page, axis, page->h[axis][1]),
1509 rule_width (page, axis, cell));
1511 /* Width of right header not including its leftmost rule. */
1512 size += axis_width (page, axis, rule_ofs_r (page, axis, page->h[axis][1]),
1513 rule_ofs_r (page, axis, 0));
1515 /* Join crossing. */
1516 if (page->h[axis][0] && page->h[axis][1])
1517 size += page->join_crossing[axis][b->z];
1522 /* Returns true if CELL along B's axis may be broken across a page boundary.
1524 This is just a heuristic. Breaking cells across page boundaries can save
1525 space, but it looks ugly. */
1527 cell_is_breakable (const struct render_break *b, int cell)
1529 const struct render_page *page = b->page;
1530 enum table_axis axis = b->axis;
1532 return cell_width (page, axis, cell) >= page->params->min_break[axis];
1539 const struct render_params *params;
1542 /* An array of "render_page"s to be rendered, in order, vertically. There
1543 may be up to 5 pages, for the pivot table's title, layers, body,
1544 captions, and footnotes. */
1545 struct render_page *pages[5];
1549 struct render_break x_break;
1550 struct render_break y_break;
1554 render_pager_add_table (struct render_pager *p, struct table *table,
1555 int min_width, const struct pivot_table_look *look)
1558 p->pages[p->n_pages++] = render_page_create (p->params, table, min_width,
1563 render_pager_start_page (struct render_pager *p)
1565 render_break_init (&p->x_break, render_page_ref (p->pages[p->cur_page++]),
1567 render_break_init_empty (&p->y_break);
1570 /* Creates and returns a new render_pager for rendering PT on the device
1571 with the given PARAMS. */
1572 struct render_pager *
1573 render_pager_create (const struct render_params *params,
1574 const struct pivot_table *pt,
1575 const size_t *layer_indexes)
1578 layer_indexes = pt->current_layer;
1580 struct table *title, *layers, *body, *caption, *footnotes;
1581 pivot_output (pt, layer_indexes, params->printing,
1582 &title, &layers, &body, &caption, &footnotes, NULL, NULL);
1584 /* Figure out the width of the body of the table. Use this to determine the
1586 struct render_page *body_page = render_page_create (params, body, 0, pt->look);
1587 int body_width = table_width (body_page, H);
1589 if (body_width > params->size[H])
1591 if (pt->look->shrink_to_fit[H] && params->ops->scale)
1592 scale = params->size[H] / (double) body_width;
1595 struct render_break b;
1596 render_break_init (&b, render_page_ref (body_page), H);
1597 struct render_page *subpage
1598 = render_break_next (&b, params->size[H]);
1599 body_width = subpage ? subpage->cp[H][2 * subpage->n[H] + 1] : 0;
1600 render_page_unref (subpage);
1601 render_break_destroy (&b);
1605 /* Create the pager. */
1606 struct render_pager *p = xmalloc (sizeof *p);
1607 *p = (struct render_pager) { .params = params, .scale = scale };
1608 render_pager_add_table (p, title, body_width, pt->look);
1609 render_pager_add_table (p, layers, body_width, pt->look);
1610 p->pages[p->n_pages++] = body_page;
1611 render_pager_add_table (p, caption, 0, pt->look);
1612 render_pager_add_table (p, footnotes, 0, pt->look);
1613 assert (p->n_pages <= sizeof p->pages / sizeof *p->pages);
1615 /* If we're shrinking tables to fit the page length, then adjust the scale
1618 XXX This will sometimes shrink more than needed, because adjusting the
1619 scale factor allows for cells to be "wider", which means that sometimes
1620 they won't break across as much vertical space, thus shrinking the table
1621 vertically more than the scale would imply. Shrinking only as much as
1622 necessary would require an iterative search. */
1623 if (pt->look->shrink_to_fit[V] && params->ops->scale)
1625 int total_height = 0;
1626 for (size_t i = 0; i < p->n_pages; i++)
1627 total_height += table_width (p->pages[i], V);
1628 if (total_height * p->scale >= params->size[V])
1629 p->scale *= params->size[V] / (double) total_height;
1632 render_pager_start_page (p);
1639 render_pager_destroy (struct render_pager *p)
1643 render_break_destroy (&p->x_break);
1644 render_break_destroy (&p->y_break);
1645 for (size_t i = 0; i < p->n_pages; i++)
1646 render_page_unref (p->pages[i]);
1651 /* Returns true if P has content remaining to render, false if rendering is
1654 render_pager_has_next (const struct render_pager *p_)
1656 struct render_pager *p = CONST_CAST (struct render_pager *, p_);
1658 while (!render_break_has_next (&p->y_break))
1660 render_break_destroy (&p->y_break);
1661 if (!render_break_has_next (&p->x_break))
1663 render_break_destroy (&p->x_break);
1664 if (p->cur_page >= p->n_pages)
1666 render_break_init_empty (&p->x_break);
1667 render_break_init_empty (&p->y_break);
1670 render_pager_start_page (p);
1674 &p->y_break, render_break_next (&p->x_break,
1675 p->params->size[H] / p->scale), V);
1680 /* Draws a chunk of content from P to fit in a space that has vertical size
1681 SPACE and the horizontal size specified in the render_params passed to
1682 render_page_create(). Returns the amount of space actually used by the
1683 rendered chunk, which will be 0 if SPACE is too small to render anything or
1684 if no content remains (use render_pager_has_next() to distinguish these
1687 render_pager_draw_next (struct render_pager *p, int space)
1689 if (p->scale != 1.0)
1691 p->params->ops->scale (p->params->aux, p->scale);
1695 int ofs[TABLE_N_AXES] = { 0, 0 };
1696 size_t start_page = SIZE_MAX;
1698 while (render_pager_has_next (p))
1700 if (start_page == p->cur_page)
1702 start_page = p->cur_page;
1704 struct render_page *page
1705 = render_break_next (&p->y_break, space - ofs[V]);
1709 render_page_draw (page, ofs);
1710 ofs[V] += render_page_get_size (page, V);
1711 render_page_unref (page);
1714 if (p->scale != 1.0)
1720 /* Draws all of P's content. */
1722 render_pager_draw (const struct render_pager *p)
1724 render_pager_draw_region (p, 0, 0, INT_MAX, INT_MAX);
1727 /* Draws the region of P's content that lies in the region (X,Y)-(X+W,Y+H).
1728 Some extra content might be drawn; the device should perform clipping as
1731 render_pager_draw_region (const struct render_pager *p,
1732 int x, int y, int w, int h)
1734 int ofs[TABLE_N_AXES] = { 0, 0 };
1735 int clip[TABLE_N_AXES][2];
1739 for (size_t i = 0; i < p->n_pages; i++)
1741 const struct render_page *page = p->pages[i];
1742 int size = render_page_get_size (page, V);
1744 clip[V][0] = MAX (y, ofs[V]) - ofs[V];
1745 clip[V][1] = MIN (y + h, ofs[V] + size) - ofs[V];
1746 if (clip[V][1] > clip[V][0])
1747 render_page_draw_region (page, ofs, clip);
1753 /* Returns the size of P's content along AXIS; i.e. the content's width if AXIS
1754 is TABLE_HORZ and its length if AXIS is TABLE_VERT. */
1756 render_pager_get_size (const struct render_pager *p, enum table_axis axis)
1760 for (size_t i = 0; i < p->n_pages; i++)
1762 int subsize = render_page_get_size (p->pages[i], axis);
1763 size = axis == H ? MAX (size, subsize) : size + subsize;
1770 render_pager_get_best_breakpoint (const struct render_pager *p, int height)
1775 for (i = 0; i < p->n_pages; i++)
1777 int size = render_page_get_size (p->pages[i], V);
1778 if (y + size >= height)
1779 return render_page_get_best_breakpoint (p->pages[i], height - y) + y;
1786 /* render_page_select() and helpers. */
1788 struct render_page_selection
1790 const struct render_page *page; /* Page whose slice we are selecting. */
1791 struct render_page *subpage; /* New page under construction. */
1792 enum table_axis a; /* Axis of 'page' along which 'subpage' is a slice. */
1793 enum table_axis b; /* The opposite of 'a'. */
1794 int z0; /* First cell along 'a' being selected. */
1795 int z1; /* Last cell being selected, plus 1. */
1796 int p0; /* Number of pixels to trim off left side of z0. */
1797 int p1; /* Number of pixels to trim off right side of z1-1. */
1800 static void cell_to_subpage (struct render_page_selection *,
1801 const struct table_cell *,
1802 int subcell[TABLE_N_AXES]);
1803 static const struct render_overflow *find_overflow_for_cell (
1804 struct render_page_selection *, const struct table_cell *);
1805 static struct render_overflow *insert_overflow (struct render_page_selection *,
1806 const struct table_cell *);
1808 /* Creates and returns a new render_page whose contents are a subregion of
1809 PAGE's contents. The new render_page includes cells Z0 through Z1
1810 (exclusive) along AXIS, plus any headers on AXIS.
1812 If P0 is nonzero, then it is a number of pixels to exclude from the left or
1813 top (according to AXIS) of cell Z0. Similarly, P1 is a number of pixels to
1814 exclude from the right or bottom of cell Z1 - 1. (P0 and P1 are used to
1815 render cells that are too large to fit on a single page.)
1817 The whole of axis !AXIS is included. (The caller may follow up with another
1818 call to render_page_select() to select on !AXIS to select on that axis as
1821 The caller retains ownership of PAGE, which is not modified. */
1822 static struct render_page *
1823 render_page_select (const struct render_page *page, enum table_axis axis,
1824 int z0, int p0, int z1, int p1)
1826 enum table_axis a = axis;
1827 enum table_axis b = !a;
1829 /* Optimize case where all of PAGE is selected by just incrementing the
1831 if (z0 == page->h[a][0] && p0 == 0
1832 && z1 == page->n[a] - page->h[a][1] && p1 == 0)
1834 struct render_page *page_rw = CONST_CAST (struct render_page *, page);
1839 /* Allocate subpage. */
1840 int trim[2] = { z0 - page->h[a][0], (page->n[a] - page->h[a][1]) - z1 };
1841 int n[TABLE_N_AXES] = { [H] = page->n[H], [V] = page->n[V] };
1842 n[a] -= trim[0] + trim[1];
1843 struct render_page *subpage = render_page_allocate__ (
1844 page->params, table_ref (page->table), n);
1845 for (enum table_axis k = 0; k < TABLE_N_AXES; k++)
1847 subpage->h[k][0] = page->h[k][0];
1848 subpage->h[k][1] = page->h[k][1];
1849 subpage->r[k][0] = page->r[k][0];
1850 subpage->r[k][1] = page->r[k][1];
1852 subpage->r[a][0] += trim[0];
1853 subpage->r[a][1] -= trim[1];
1855 /* An edge is cut off if it was cut off in PAGE or if we're trimming pixels
1856 off that side of the page and there are no headers. */
1857 subpage->is_edge_cutoff[a][0] =
1858 subpage->h[a][0] == 0 && (p0 || (z0 == 0 && page->is_edge_cutoff[a][0]));
1859 subpage->is_edge_cutoff[a][1] =
1860 subpage->h[a][1] == 0 && (p1 || (z1 == page->n[a]
1861 && page->is_edge_cutoff[a][1]));
1862 subpage->is_edge_cutoff[b][0] = page->is_edge_cutoff[b][0];
1863 subpage->is_edge_cutoff[b][1] = page->is_edge_cutoff[b][1];
1865 /* Select join crossings from PAGE into subpage. */
1866 int *jc = subpage->join_crossing[a];
1867 for (int z = 0; z < page->h[a][0]; z++)
1868 *jc++ = page->join_crossing[a][z];
1869 for (int z = z0; z <= z1; z++)
1870 *jc++ = page->join_crossing[a][z];
1871 for (int z = page->n[a] - page->h[a][1]; z < page->n[a]; z++)
1872 *jc++ = page->join_crossing[a][z];
1873 assert (jc == &subpage->join_crossing[a][subpage->n[a] + 1]);
1875 memcpy (subpage->join_crossing[b], page->join_crossing[b],
1876 (subpage->n[b] + 1) * sizeof **subpage->join_crossing);
1878 /* Select widths from PAGE into subpage. */
1879 int *scp = page->cp[a];
1880 int *dcp = subpage->cp[a];
1882 for (int z = 0; z <= rule_ofs (subpage->h[a][0]); z++, dcp++)
1884 int w = !z && subpage->is_edge_cutoff[a][0] ? 0 : scp[z + 1] - scp[z];
1885 dcp[1] = dcp[0] + w;
1887 for (int z = cell_ofs (z0); z <= cell_ofs (z1 - 1); z++, dcp++)
1889 dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1890 if (z == cell_ofs (z0))
1893 if (page->h[a][0] && page->h[a][1])
1894 dcp[1] += page->join_crossing[a][z / 2];
1896 if (z == cell_ofs (z1 - 1))
1899 for (int z = rule_ofs_r (page, a, subpage->h[a][1]);
1900 z <= rule_ofs_r (page, a, 0); z++, dcp++)
1902 if (z == rule_ofs_r (page, a, 0) && subpage->is_edge_cutoff[a][1])
1905 dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1907 assert (dcp == &subpage->cp[a][2 * subpage->n[a] + 1]);
1909 for (int z = 0; z < page->n[b] * 2 + 2; z++)
1910 subpage->cp[b][z] = page->cp[b][z];
1912 /* Add new overflows. */
1913 struct render_page_selection s = {
1924 if (!page->h[a][0] || z0 > page->h[a][0] || p0)
1925 for (int z = 0; z < page->n[b];)
1927 int d[TABLE_N_AXES];
1931 struct table_cell cell;
1932 render_get_cell (page, d[H], d[V], &cell);
1933 bool overflow0 = p0 || cell.d[a][0] < z0;
1934 bool overflow1 = cell.d[a][1] > z1 || (cell.d[a][1] == z1 && p1);
1935 if (overflow0 || overflow1)
1937 struct render_overflow *ro = insert_overflow (&s, &cell);
1941 ro->overflow[a][0] += p0 + axis_width (
1942 page, a, cell_ofs (cell.d[a][0]), cell_ofs (z0));
1943 if (page->h[a][0] && page->h[a][1])
1944 ro->overflow[a][0] -= page->join_crossing[a][cell.d[a][0]
1950 ro->overflow[a][1] += p1 + axis_width (
1951 page, a, cell_ofs (z1), cell_ofs (cell.d[a][1]));
1952 if (page->h[a][0] && page->h[a][1])
1953 ro->overflow[a][1] -= page->join_crossing[a][cell.d[a][1]];
1959 if (!page->h[a][1] || z1 < page->n[a] - page->h[a][1] || p1)
1960 for (int z = 0; z < page->n[b];)
1962 int d[TABLE_N_AXES];
1966 struct table_cell cell;
1967 render_get_cell (page, d[H], d[V], &cell);
1968 if ((cell.d[a][1] > z1 || (cell.d[a][1] == z1 && p1))
1969 && find_overflow_for_cell (&s, &cell) == NULL)
1971 struct render_overflow *ro = insert_overflow (&s, &cell);
1972 ro->overflow[a][1] += p1 + axis_width (page, a, cell_ofs (z1),
1973 cell_ofs (cell.d[a][1]));
1978 /* Copy overflows from PAGE into subpage. */
1979 struct render_overflow *ro;
1980 HMAP_FOR_EACH (ro, struct render_overflow, node, &page->overflows)
1982 struct table_cell cell;
1984 table_get_cell (page->table, ro->d[H], ro->d[V], &cell);
1985 if (cell.d[a][1] > z0 && cell.d[a][0] < z1
1986 && find_overflow_for_cell (&s, &cell) == NULL)
1987 insert_overflow (&s, &cell);
1993 /* Given CELL, a table_cell within S->page, stores in SUBCELL the (x,y)
1994 coordinates of the top-left cell as it will appear in S->subpage.
1996 CELL must actually intersect the region of S->page that is being selected
1997 by render_page_select() or the results will not make any sense. */
1999 cell_to_subpage (struct render_page_selection *s,
2000 const struct table_cell *cell, int subcell[TABLE_N_AXES])
2002 enum table_axis a = s->a;
2003 enum table_axis b = s->b;
2004 int ha0 = s->subpage->h[a][0];
2006 subcell[a] = MAX (cell->d[a][0] - s->z0 + ha0, ha0);
2007 subcell[b] = cell->d[b][0];
2010 /* Given CELL, a table_cell within S->page, returns the render_overflow for
2011 that cell in S->subpage, if there is one, and a null pointer otherwise.
2013 CELL must actually intersect the region of S->page that is being selected
2014 by render_page_select() or the results will not make any sense. */
2015 static const struct render_overflow *
2016 find_overflow_for_cell (struct render_page_selection *s,
2017 const struct table_cell *cell)
2021 cell_to_subpage (s, cell, subcell);
2022 return find_overflow (s->subpage, subcell[H], subcell[V]);
2025 /* Given CELL, a table_cell within S->page, inserts a render_overflow for that
2026 cell in S->subpage (which must not already exist). Initializes the new
2027 render_overflow's 'overflow' member from the overflow for CELL in S->page,
2030 CELL must actually intersect the region of S->page that is being selected
2031 by render_page_select() or the results will not make any sense. */
2032 static struct render_overflow *
2033 insert_overflow (struct render_page_selection *s,
2034 const struct table_cell *cell)
2036 struct render_overflow *of = XZALLOC (struct render_overflow);
2037 cell_to_subpage (s, cell, of->d);
2038 hmap_insert (&s->subpage->overflows, &of->node,
2039 hash_cell (of->d[H], of->d[V]));
2041 const struct render_overflow *old
2042 = find_overflow (s->page, cell->d[H][0], cell->d[V][0]);
2044 memcpy (of->overflow, old->overflow, sizeof of->overflow);