aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDaniel Eklöf <daniel@ekloef.se>2021-05-16 16:48:19 +0000
committerDaniel Eklöf <daniel@ekloef.se>2021-05-16 16:48:19 +0000
commit3405a9c81c981e0da06ba52c790a4a42a5e5c0c5 (patch)
treeb416b5b6fe1df6c8296e31308fd3a3117644c43d
parentMerge branch 'vt-anywhere-fix2' (diff)
parentgrid: reflow: qsort_r() is not portable (diff)
Merge branch 'reflow-performance'
Part of #504
-rw-r--r--extract.c2
-rw-r--r--grid.c208
-rw-r--r--ime.c4
-rw-r--r--render.c12
-rw-r--r--search.c4
-rw-r--r--selection.c26
-rw-r--r--terminal.c8
-rw-r--r--terminal.h2
-rw-r--r--vt.c2
9 files changed, 171 insertions, 97 deletions
diff --git a/extract.c b/extract.c
index 145ef03f..ac5f3897 100644
--- a/extract.c
+++ b/extract.c
@@ -113,7 +113,7 @@ extract_one(const struct terminal *term, const struct row *row,
{
struct extraction_context *ctx = context;
- if (cell->wc == CELL_MULT_COL_SPACER)
+ if (cell->wc >= CELL_SPACER)
return true;
if (ctx->last_row != NULL && row != ctx->last_row) {
diff --git a/grid.c b/grid.c
index e92a3b01..eb923756 100644
--- a/grid.c
+++ b/grid.c
@@ -1,5 +1,6 @@
#include "grid.h"
+#include <stdlib.h>
#include <string.h>
#define LOG_MODULE "grid"
@@ -12,6 +13,8 @@
#include "util.h"
#include "xmalloc.h"
+#define TIME_REFLOW 1
+
struct grid *
grid_snapshot(const struct grid *grid)
{
@@ -382,6 +385,44 @@ _line_wrap(struct grid *old_grid, struct row **new_grid, struct row *row,
return new_row;
}
+static struct {
+ int scrollback_start;
+ int rows;
+} tp_cmp_ctx;
+
+static int
+tp_cmp(const void *_a, const void *_b)
+{
+ const struct coord *a = *(const struct coord **)_a;
+ const struct coord *b = *(const struct coord **)_b;
+
+ int scrollback_start = tp_cmp_ctx.scrollback_start;
+ int num_rows = tp_cmp_ctx.rows;
+
+ int a_row = (a->row - scrollback_start + num_rows) & (num_rows - 1);
+ int b_row = (b->row - scrollback_start + num_rows) & (num_rows - 1);
+
+ xassert(a_row >= 0);
+ xassert(a_row < num_rows || num_rows == 0);
+ xassert(b_row >= 0);
+ xassert(b_row < num_rows || num_rows == 0);
+
+ if (a_row < b_row)
+ return -1;
+ if (a_row > b_row)
+ return 1;
+
+ xassert(a_row == b_row);
+
+ if (a->col < b->col)
+ return -1;
+ if (a->col > b->col)
+ return 1;
+
+ xassert(a->col == b->col);
+ return 0;
+}
+
void
grid_resize_and_reflow(
struct grid *grid, int new_rows, int new_cols,
@@ -391,6 +432,11 @@ grid_resize_and_reflow(
size_t compose_count, const struct
composed composed[static compose_count])
{
+#if defined(TIME_REFLOW) && TIME_REFLOW
+ struct timeval start;
+ gettimeofday(&start, NULL);
+#endif
+
struct row *const *old_grid = grid->rows;
const int old_rows = grid->num_rows;
const int old_cols = grid->num_cols;
@@ -426,16 +472,38 @@ grid_resize_and_reflow(
saved_cursor.row += grid->offset;
saved_cursor.row &= old_rows - 1;
- tll(struct coord *) tracking_points = tll_init();
- tll_push_back(tracking_points, &cursor);
- tll_push_back(tracking_points, &saved_cursor);
+ size_t tp_count =
+ tracking_points_count +
+ 1 + /* cursor */
+ 1 + /* saved cursor */
+ !view_follows + /* viewport */
+ 1; /* terminator */
+
+ struct coord *tracking_points[tp_count];
+ memcpy(tracking_points, _tracking_points, tracking_points_count * sizeof(_tracking_points[0]));
+ tracking_points[tracking_points_count] = &cursor;
+ tracking_points[tracking_points_count + 1] = &saved_cursor;
struct coord viewport = {0, grid->view};
if (!view_follows)
- tll_push_back(tracking_points, &viewport);
+ tracking_points[tracking_points_count + 2] = &viewport;
- for (size_t i = 0; i < tracking_points_count; i++)
- tll_push_back(tracking_points, _tracking_points[i]);
+ /* Not thread safe! */
+ tp_cmp_ctx.scrollback_start = offset;
+ tp_cmp_ctx.rows = old_rows;
+ qsort(
+ tracking_points, tp_count - 1, sizeof(tracking_points[0]), &tp_cmp);
+
+ /* NULL terminate */
+ struct coord terminator = {-1, -1};
+ tracking_points[tp_count - 1] = &terminator;
+ struct coord **next_tp = &tracking_points[0];
+
+ LOG_DBG("scrollback-start=%d", offset);
+ for (size_t i = 0; i < tp_count - 1; i++) {
+ LOG_DBG("TP #%zu: row=%d, col=%d",
+ i, tracking_points[i]->row, tracking_points[i]->col);
+ }
/*
* Walk the old grid
@@ -466,11 +534,10 @@ grid_resize_and_reflow(
grid, new_grid, new_row, &new_row_idx, &new_col_idx, \
new_rows, new_cols)
-#define print_spacer() \
+#define print_spacer(remaining) \
do { \
- new_row->cells[new_col_idx].wc = CELL_MULT_COL_SPACER; \
+ new_row->cells[new_col_idx].wc = CELL_SPACER + (remaining); \
new_row->cells[new_col_idx].attrs = old_cell->attrs; \
- new_row->cells[new_col_idx].attrs.clean = 1; \
} while (0)
/*
@@ -484,28 +551,29 @@ grid_resize_and_reflow(
/* Walk current line of the old grid */
for (int c = 0; c < old_cols; c++) {
+ const struct cell *old_cell = &old_row->cells[c];
+ wchar_t wc = old_cell->wc;
/* Check if this cell is one of the tracked cells */
bool is_tracking_point = false;
- tll_foreach(tracking_points, it) {
- if (it->item->row == old_row_idx && it->item->col == c) {
- is_tracking_point = true;
- break;
- }
- }
+
+ struct coord *tp = *next_tp;
+ if (unlikely(tp->row == old_row_idx && tp->col == c))
+ is_tracking_point = true;
/* If there’s an URI start/end point here, we need to make
* sure we handle it */
+ bool on_uri = false;
if (old_row->extra != NULL) {
tll_foreach(old_row->extra->uri_ranges, it) {
- if (it->item.start == c || it->item.end == c) {
- is_tracking_point = true;
+ if (unlikely(it->item.start == c || it->item.end == c)) {
+ on_uri = true;
break;
}
}
}
- if (old_row->cells[c].wc == 0 && !is_tracking_point) {
+ if (wc == 0 && likely(!(is_tracking_point | on_uri))) {
empty_count++;
continue;
}
@@ -518,72 +586,66 @@ grid_resize_and_reflow(
if (new_cols_left < cols_needed && new_cols_left >= old_cols_left)
empty_count = max(0, empty_count - (cols_needed - new_cols_left));
- wchar_t wc = old_row->cells[c].wc;
- if (wc >= CELL_COMB_CHARS_LO &&
- wc < (CELL_COMB_CHARS_LO + compose_count))
- {
- wc = composed[wc - CELL_COMB_CHARS_LO].base;
- }
+ for (int i = 0; i < empty_count; i++) {
+ if (new_col_idx + 1 > new_cols)
+ line_wrap();
- int width = max(1, wcwidth(wc));
+ size_t idx = c - empty_count + i;
- /* Multi-column characters are never cut in half */
- xassert(c + width <= old_cols);
+ new_row->cells[new_col_idx].wc = 0;
+ new_row->cells[new_col_idx].attrs = old_row->cells[idx].attrs;
+ new_col_idx++;
+ }
- for (int i = 0; i < empty_count + 1; i++) {
- const struct cell *old_cell = &old_row->cells[c - empty_count + i];
- wc = old_cell->wc;
+ empty_count = 0;
- if (wc == CELL_MULT_COL_SPACER)
- continue;
+ if (wc == CELL_SPACER)
+ continue;
- if (wc >= CELL_COMB_CHARS_LO &&
- wc < (CELL_COMB_CHARS_LO + compose_count))
- {
- wc = composed[wc - CELL_COMB_CHARS_LO].base;
- }
+ if (unlikely(wc < CELL_SPACER &&
+ c + 1 < old_cols &&
+ old_row->cells[c + 1].wc > CELL_SPACER))
+ {
+ int width = old_row->cells[c + 1].wc - CELL_SPACER + 1;
+ assert(wcwidth(wc) == width);
/* Out of columns on current row in new grid? */
- if (new_col_idx + max(1, wcwidth(wc)) > new_cols) {
+ if (new_col_idx + width > new_cols) {
/* Pad to end-of-line with spacers, then line-wrap */
for (;new_col_idx < new_cols; new_col_idx++)
- print_spacer();
+ print_spacer(0);
line_wrap();
}
+ }
- xassert(new_row != NULL);
- xassert(new_col_idx >= 0);
- xassert(new_col_idx < new_cols);
+ if (new_col_idx + 1 > new_cols)
+ line_wrap();
- new_row->cells[new_col_idx] = *old_cell;
- new_row->cells[new_col_idx].attrs.clean = 1;
+ xassert(new_row != NULL);
+ xassert(new_col_idx >= 0);
+ xassert(new_col_idx < new_cols);
- /* Translate tracking point(s) */
- if (is_tracking_point && i >= empty_count) {
- tll_foreach(tracking_points, it) {
- if (it->item->row == old_row_idx && it->item->col == c) {
- it->item->row = new_row_idx;
- it->item->col = new_col_idx;
- tll_remove(tracking_points, it);
- }
- }
+ new_row->cells[new_col_idx] = *old_cell;
- reflow_uri_ranges(old_row, new_row, c, new_col_idx);
- }
- new_col_idx++;
- }
+ /* Translate tracking point(s) */
+ if (unlikely(is_tracking_point)) {
+ do {
+ xassert(tp != NULL);
+ xassert(tp->row == old_row_idx);
+ xassert(tp->col == c);
- /* For multi-column characters, insert spacers in the
- * subsequent cells */
- const struct cell *old_cell = &old_row->cells[c];
- for (size_t i = 0; i < width - 1; i++) {
- xassert(new_col_idx < new_cols);
- print_spacer();
- new_col_idx++;
+ tp->row = new_row_idx;
+ tp->col = new_col_idx;
+
+ next_tp++;
+ tp = *next_tp;
+ } while (tp->row == old_row_idx && tp->col == c);
}
- c += width - 1;
- empty_count = 0;
+ if (unlikely(on_uri))
+ reflow_uri_ranges(old_row, new_row, c, new_col_idx);
+
+ new_col_idx++;
}
if (old_row->linebreak) {
@@ -595,6 +657,8 @@ grid_resize_and_reflow(
#undef line_wrap
}
+ xassert(old_rows == 0 || *next_tp == &terminator);
+
#if defined(_DEBUG)
/* Verify all URI ranges have been “closed” */
for (int r = 0; r < new_rows; r++) {
@@ -675,7 +739,17 @@ grid_resize_and_reflow(
sixel_destroy(&it->item);
tll_free(untranslated_sixels);
- tll_free(tracking_points);
+#if defined(TIME_REFLOW) && TIME_REFLOW
+ struct timeval stop;
+ gettimeofday(&stop, NULL);
+
+ struct timeval diff;
+ timersub(&stop, &start, &diff);
+ LOG_INFO("reflowed %d -> %d rows in %llds %lldµs",
+ old_rows, new_rows,
+ (long long)diff.tv_sec,
+ (long long)diff.tv_usec);
+#endif
}
static void
diff --git a/ime.c b/ime.c
index b1852ed3..81e63884 100644
--- a/ime.c
+++ b/ime.c
@@ -199,7 +199,7 @@ done(void *data, struct zwp_text_input_v3 *zwp_text_input_v3,
for (int j = 1; j < width; j++) {
cell = &seat->ime.preedit.cells[cell_idx + j];
- cell->wc = CELL_MULT_COL_SPACER;
+ cell->wc = CELL_SPACER + width - j;
cell->attrs = (struct attributes){.clean = 1};
}
@@ -280,7 +280,7 @@ done(void *data, struct zwp_text_input_v3 *zwp_text_input_v3,
/* Expand cursor end to end of glyph */
while (cell_end > cell_begin && cell_end < cell_count &&
- seat->ime.preedit.cells[cell_end].wc == CELL_MULT_COL_SPACER)
+ seat->ime.preedit.cells[cell_end].wc >= CELL_SPACER)
{
cell_end++;
}
diff --git a/render.c b/render.c
index 8481d330..3f6e5637 100644
--- a/render.c
+++ b/render.c
@@ -594,7 +594,7 @@ render_cell(struct terminal *term, pixman_image_t *pix,
if (has_cursor && term->cursor_style == CURSOR_BLOCK && term->kbd_focus)
draw_cursor(term, cell, font, pix, &fg, &bg, x, y, cell_cols);
- if (cell->wc == 0 || cell->wc == CELL_MULT_COL_SPACER ||
+ if (cell->wc == 0 || cell->wc >= CELL_SPACER ||
(unlikely(cell->attrs.conceal) && !is_selected))
{
goto draw_cursor;
@@ -1237,7 +1237,7 @@ render_ime_preedit_for_seat(struct terminal *term, struct seat *seat,
/* Make sure we don't start in the middle of a character */
while (ime_ofs < cells_needed &&
- seat->ime.preedit.cells[ime_ofs].wc == CELL_MULT_COL_SPACER)
+ seat->ime.preedit.cells[ime_ofs].wc >= CELL_SPACER)
{
ime_ofs++;
}
@@ -1249,7 +1249,7 @@ render_ime_preedit_for_seat(struct terminal *term, struct seat *seat,
struct row *row = grid_row_in_view(term->grid, row_idx);
/* Don't start pre-edit text in the middle of a double-width character */
- while (col_idx > 0 && row->cells[col_idx].wc == CELL_MULT_COL_SPACER) {
+ while (col_idx > 0 && row->cells[col_idx].wc >= CELL_SPACER) {
cells_used++;
col_idx--;
}
@@ -1268,11 +1268,11 @@ render_ime_preedit_for_seat(struct terminal *term, struct seat *seat,
row->dirty = true;
/* Render pre-edit text */
- xassert(seat->ime.preedit.cells[ime_ofs].wc != CELL_MULT_COL_SPACER);
+ xassert(seat->ime.preedit.cells[ime_ofs].wc < CELL_SPACER);
for (int i = 0, idx = ime_ofs; idx < seat->ime.preedit.count; i++, idx++) {
const struct cell *cell = &seat->ime.preedit.cells[idx];
- if (cell->wc == CELL_MULT_COL_SPACER)
+ if (cell->wc >= CELL_SPACER)
continue;
int width = max(1, wcwidth(cell->wc));
@@ -3242,7 +3242,7 @@ maybe_resize(struct terminal *term, int width, int height, bool force)
/* Resize grids */
grid_resize_and_reflow(
&term->normal, new_normal_grid_rows, new_cols, old_rows, new_rows,
- ALEN(tracking_points), tracking_points,
+ term->selection.end.row >= 0 ? ALEN(tracking_points) : 0, tracking_points,
term->composed_count, term->composed);
grid_resize_without_reflow(
diff --git a/search.c b/search.c
index 02cea9e0..911b13c0 100644
--- a/search.c
+++ b/search.c
@@ -337,7 +337,7 @@ search_find_next(struct terminal *term)
row = term->grid->rows[end_row];
}
- if (row->cells[end_col].wc == CELL_MULT_COL_SPACER) {
+ if (row->cells[end_col].wc >= CELL_SPACER) {
end_col++;
continue;
}
@@ -461,7 +461,7 @@ search_match_to_end_of_word(struct terminal *term, bool spaces_only)
bool done = false;
for (; end_col < term->cols; end_col++) {
wchar_t wc = row->cells[end_col].wc;
- if (wc == CELL_MULT_COL_SPACER)
+ if (wc >= CELL_SPACER)
continue;
const struct composed *composed = NULL;
diff --git a/selection.c b/selection.c
index f5a114c8..5bb386ab 100644
--- a/selection.c
+++ b/selection.c
@@ -234,7 +234,7 @@ find_word_boundary_left(struct terminal *term, struct coord *pos,
const struct row *r = grid_row_in_view(term->grid, pos->row);
wchar_t c = r->cells[pos->col].wc;
- while (c == CELL_MULT_COL_SPACER) {
+ while (c >= CELL_SPACER) {
xassert(pos->col > 0);
if (pos->col == 0)
return;
@@ -268,7 +268,7 @@ find_word_boundary_left(struct terminal *term, struct coord *pos,
const struct row *row = grid_row_in_view(term->grid, next_row);
c = row->cells[next_col].wc;
- while (c == CELL_MULT_COL_SPACER) {
+ while (c >= CELL_SPACER) {
xassert(next_col > 0);
if (--next_col < 0)
return;
@@ -306,7 +306,7 @@ find_word_boundary_right(struct terminal *term, struct coord *pos,
const struct row *r = grid_row_in_view(term->grid, pos->row);
wchar_t c = r->cells[pos->col].wc;
- while (c == CELL_MULT_COL_SPACER) {
+ while (c >= CELL_SPACER) {
xassert(pos->col > 0);
if (pos->col == 0)
return;
@@ -340,7 +340,7 @@ find_word_boundary_right(struct terminal *term, struct coord *pos,
const struct row *row = grid_row_in_view(term->grid, next_row);
c = row->cells[next_col].wc;
- while (c == CELL_MULT_COL_SPACER) {
+ while (c >= CELL_SPACER) {
if (++next_col >= term->cols) {
next_col = 0;
if (++next_row >= term->rows)
@@ -554,7 +554,7 @@ set_pivot_point_for_block_and_char_wise(struct terminal *term,
const struct row *row = term->grid->rows[pivot_start->row & (term->grid->num_rows - 1)];
const struct cell *cell = &row->cells[pivot_start->col];
- if (cell->wc != CELL_MULT_COL_SPACER)
+ if (cell->wc < CELL_SPACER)
break;
/* Multi-column chars don’t cross rows */
@@ -579,7 +579,7 @@ set_pivot_point_for_block_and_char_wise(struct terminal *term,
const struct row *row = term->grid->rows[pivot_end->row & (term->grid->num_rows - 1)];
const wchar_t wc = row->cells[pivot_end->col].wc;
- keep_going = wc == CELL_MULT_COL_SPACER;
+ keep_going = wc >= CELL_SPACER;
if (pivot_end->col == 0) {
if (pivot_end->row - term->grid->view <= 0)
@@ -596,7 +596,7 @@ set_pivot_point_for_block_and_char_wise(struct terminal *term,
const wchar_t wc = pivot_start->col < term->cols - 1
? row->cells[pivot_start->col + 1].wc : 0;
- keep_going = wc == CELL_MULT_COL_SPACER;
+ keep_going = wc >= CELL_SPACER;
if (pivot_start->col >= term->cols - 1) {
if (pivot_start->row - term->grid->view >= term->rows - 1)
@@ -609,9 +609,9 @@ set_pivot_point_for_block_and_char_wise(struct terminal *term,
}
xassert(term->grid->rows[pivot_start->row & (term->grid->num_rows - 1)]->
- cells[pivot_start->col].wc != CELL_MULT_COL_SPACER);
+ cells[pivot_start->col].wc < CELL_SPACER);
xassert(term->grid->rows[pivot_end->row & (term->grid->num_rows - 1)]->
- cells[pivot_end->col].wc != CELL_MULT_COL_SPACER);
+ cells[pivot_end->col].wc < CELL_SPACER);
}
void
@@ -743,17 +743,17 @@ selection_update(struct terminal *term, int col, int row)
(new_start.row == new_end.row && new_start.col <= new_end.col))
{
while (new_start.col >= 1 &&
- row_start->cells[new_start.col].wc == CELL_MULT_COL_SPACER)
+ row_start->cells[new_start.col].wc >= CELL_SPACER)
new_start.col--;
while (new_end.col < term->cols - 1 &&
- row_end->cells[new_end.col + 1].wc == CELL_MULT_COL_SPACER)
+ row_end->cells[new_end.col + 1].wc >= CELL_SPACER)
new_end.col++;
} else {
while (new_end.col >= 1 &&
- row_end->cells[new_end.col].wc == CELL_MULT_COL_SPACER)
+ row_end->cells[new_end.col].wc >= CELL_SPACER)
new_end.col--;
while (new_start.col < term->cols - 1 &&
- row_start->cells[new_start.col + 1].wc == CELL_MULT_COL_SPACER)
+ row_start->cells[new_start.col + 1].wc >= CELL_SPACER)
new_start.col++;
}
diff --git a/terminal.c b/terminal.c
index a9712789..b4abbb0f 100644
--- a/terminal.c
+++ b/terminal.c
@@ -2764,12 +2764,12 @@ print_insert(struct terminal *term, int width)
}
static void
-print_spacer(struct terminal *term, int col)
+print_spacer(struct terminal *term, int col, int remaining)
{
struct row *row = term->grid->cur_row;
struct cell *cell = &row->cells[col];
- cell->wc = CELL_MULT_COL_SPACER;
+ cell->wc = CELL_SPACER + remaining;
cell->attrs = term->vt.attrs;
cell->attrs.clean = 0;
}
@@ -2803,7 +2803,7 @@ term_print(struct terminal *term, wchar_t wc, int width)
/* Multi-column character that doesn't fit on current line -
* pad with spacers */
for (size_t i = term->grid->cursor.point.col; i < term->cols; i++)
- print_spacer(term, i);
+ print_spacer(term, i, 0);
/* And force a line-wrap */
term->grid->cursor.lcf = 1;
@@ -2826,7 +2826,7 @@ term_print(struct terminal *term, wchar_t wc, int width)
/* Advance cursor the 'additional' columns while dirty:ing the cells */
for (int i = 1; i < width && term->grid->cursor.point.col < term->cols - 1; i++) {
term->grid->cursor.point.col++;
- print_spacer(term, term->grid->cursor.point.col);
+ print_spacer(term, term->grid->cursor.point.col, width - i);
}
/* Advance cursor */
diff --git a/terminal.h b/terminal.h
index 0f8f52da..85ba90eb 100644
--- a/terminal.h
+++ b/terminal.h
@@ -48,7 +48,7 @@ static_assert(sizeof(struct attributes) == 8, "VT attribute struct too large");
#define CELL_COMB_CHARS_LO 0x40000000ul
#define CELL_COMB_CHARS_HI 0x400ffffful
-#define CELL_MULT_COL_SPACER 0x40100000ul
+#define CELL_SPACER 0x40100000ul
struct cell {
wchar_t wc;
diff --git a/vt.c b/vt.c
index 8ec82dcf..669ba8c1 100644
--- a/vt.c
+++ b/vt.c
@@ -569,7 +569,7 @@ action_utf8_print(struct terminal *term, wchar_t wc)
if (!term->grid->cursor.lcf)
base_col--;
- while (row->cells[base_col].wc == CELL_MULT_COL_SPACER && base_col > 0)
+ while (row->cells[base_col].wc >= CELL_SPACER && base_col > 0)
base_col--;
xassert(base_col >= 0 && base_col < term->cols);