aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDaniel Eklöf <daniel@ekloef.se>2021-08-13 15:45:09 +0000
committerDaniel Eklöf <daniel@ekloef.se>2021-08-16 17:15:41 +0000
commitae70596a5034f9fd6bbca6b42e4fe52c42c70d34 (patch)
treefe59d921504611299a112c1c5a86a8814dff2706
parentMerge branch 'tempus-themes' (diff)
selection: don’t require two cell attr bits for selection updating
When updating the selection (i.e when changing it - adding or removing cells to the selection), we need to do two things: * Unset the ‘selected’ bit on all cells that are no longer selected. * Set the ‘selected’ bit on all cells that *are* selected. Since it’s quite tricky to calculate the difference between the “old” and “new” selection, this is done by first un-selecting the old selection, and then selecting the new, updated selection. I.e. first we clear the ‘selected’ bit from *all* cells, and then we re-set it on those cells that are still selected. This process also dirties the cells, to make sure they are re-rendered (needed to reflect their new selected/un-selected status). To avoid dirtying *all* previously selected, and newly selected cells, we have used an algorithm that first runs a “pre-pass”, marking all cells that *will* be selected as such. The un-select pass would then skip (no dirty) cells that have been marked by the pre-pass. Finally, the select pass would only dirty cells that have *not* been marked by the pre-pass. In short, we only dirty cells whose selection state have *changed*. To do this, we used a second ‘selected’ bit in the cell attribute struct. Those bits are *scarce*. This patch implements an alternative algorithm, that frees up one of the two ‘selected’ bits. This is done by lazy allocating a bitmask for the entire grid. The pre-pass sets bits in the bitmask. Thus, after the pre-pass, the bitmask has set bits for all cells that *will* be selected. The un-select pass simply skips cells with a one-bit in the bitmask. Cells without a one-bit in the bitmask are dirtied, and their ‘selected’ bit is cleared. The select-pass doesn’t even have to look at the bitmask - if the cell already has its ‘selected’ bit set, it does nothing. Otherwise it sets it and dirties the cell. The bitmask is implemented as an array of arrays of 64-bit integers. Each outer element represents one row. These pointers are calloc():ed before starting the pre-pass. The pre-pass allocates the inner arrays on demand. The unselect pass is designed to handle both the complete absence of a bitmask, as well as row entries being NULL (both means the cell is *not* pre-marked, and will thus be dirtied).
-rw-r--r--render.c1
-rw-r--r--selection.c85
-rw-r--r--terminal.h4
3 files changed, 63 insertions, 27 deletions
diff --git a/render.c b/render.c
index 68a53082..23ad460f 100644
--- a/render.c
+++ b/render.c
@@ -455,7 +455,6 @@ render_cell(struct terminal *term, pixman_image_t *pix,
const int x = term->margins.left + col * width;
const int y = term->margins.top + row_no * height;
- xassert(cell->attrs.selected == 0 || cell->attrs.selected == 1);
bool is_selected = cell->attrs.selected;
uint32_t _fg = 0;
diff --git a/selection.c b/selection.c
index 95879445..365975f0 100644
--- a/selection.c
+++ b/selection.c
@@ -107,7 +107,7 @@ selection_view_down(struct terminal *term, int new_view)
static void
foreach_selected_normal(
struct terminal *term, struct coord _start, struct coord _end,
- bool (*cb)(struct terminal *term, struct row *row, struct cell *cell, int col, void *data),
+ bool (*cb)(struct terminal *term, struct row *row, struct cell *cell, int row_no, int col, void *data),
void *data)
{
const struct coord *start = &_start;
@@ -141,7 +141,7 @@ foreach_selected_normal(
c <= (r == end_row ? end_col : term->cols - 1);
c++)
{
- if (!cb(term, row, &row->cells[c], c, data))
+ if (!cb(term, row, &row->cells[c], real_r, c, data))
return;
}
@@ -152,7 +152,7 @@ foreach_selected_normal(
static void
foreach_selected_block(
struct terminal *term, struct coord _start, struct coord _end,
- bool (*cb)(struct terminal *term, struct row *row, struct cell *cell, int col, void *data),
+ bool (*cb)(struct terminal *term, struct row *row, struct cell *cell, int row_no, int col, void *data),
void *data)
{
const struct coord *start = &_start;
@@ -174,7 +174,7 @@ foreach_selected_block(
xassert(row != NULL);
for (int c = top_left.col; c <= bottom_right.col; c++) {
- if (!cb(term, row, &row->cells[c], c, data))
+ if (!cb(term, row, &row->cells[c], real_r, c, data))
return;
}
}
@@ -183,7 +183,7 @@ foreach_selected_block(
static void
foreach_selected(
struct terminal *term, struct coord start, struct coord end,
- bool (*cb)(struct terminal *term, struct row *row, struct cell *cell, int col, void *data),
+ bool (*cb)(struct terminal *term, struct row *row, struct cell *cell, int row_no, int col, void *data),
void *data)
{
switch (term->selection.kind) {
@@ -207,7 +207,7 @@ foreach_selected(
static bool
extract_one_const_wrapper(struct terminal *term,
struct row *row, struct cell *cell,
- int col, void *data)
+ int row_no, int col, void *data)
{
return extract_one(term, row, cell, col, data);
}
@@ -441,27 +441,40 @@ selection_start(struct terminal *term, int col, int row,
struct mark_context {
const struct row *last_row;
int empty_count;
+ uint64_t **keep_selection;
};
static bool
unmark_selected(struct terminal *term, struct row *row, struct cell *cell,
- int col, void *data)
+ int row_no, int col, void *data)
{
- if (cell->attrs.selected == 0 || (cell->attrs.selected & 2)) {
- /* Ignore if already deselected, or if premarked for updated selection */
+ if (!cell->attrs.selected)
return true;
+
+ struct mark_context *ctx = data;
+ const uint64_t *keep_selection =
+ ctx->keep_selection != NULL ? ctx->keep_selection[row_no] : NULL;
+
+ if (keep_selection != NULL) {
+ unsigned idx = (unsigned)col / 64;
+ unsigned ofs = (unsigned)col % 64;
+
+ if (keep_selection[idx] & (1ull << ofs)) {
+ /* We’re updating the selection, and this cell is still
+ * going to be selected */
+ return true;
+ }
}
row->dirty = true;
- cell->attrs.selected = 0;
- cell->attrs.clean = 0;
+ cell->attrs.selected = false;
+ cell->attrs.clean = false;
return true;
}
-
static bool
premark_selected(struct terminal *term, struct row *row, struct cell *cell,
- int col, void *data)
+ int row_no, int col, void *data)
{
struct mark_context *ctx = data;
xassert(ctx != NULL);
@@ -476,9 +489,18 @@ premark_selected(struct terminal *term, struct row *row, struct cell *cell,
return true;
}
+ uint64_t *keep_selection = ctx->keep_selection[row_no];
+ if (keep_selection == NULL) {
+ keep_selection = xcalloc((term->grid->num_cols + 63) / 64, sizeof(keep_selection[0]));
+ ctx->keep_selection[row_no] = keep_selection;
+ }
+
/* Tell unmark to leave this be */
- for (int i = 0; i < ctx->empty_count + 1; i++)
- row->cells[col - i].attrs.selected |= 2;
+ for (int i = 0; i < ctx->empty_count + 1; i++) {
+ unsigned idx = (unsigned)(col - i) / 64;
+ unsigned ofs = (unsigned)(col - i) % 64;
+ keep_selection[idx] |= 1ull << ofs;
+ }
ctx->empty_count = 0;
return true;
@@ -486,7 +508,7 @@ premark_selected(struct terminal *term, struct row *row, struct cell *cell,
static bool
mark_selected(struct terminal *term, struct row *row, struct cell *cell,
- int col, void *data)
+ int row_no, int col, void *data)
{
struct mark_context *ctx = data;
xassert(ctx != NULL);
@@ -503,12 +525,10 @@ mark_selected(struct terminal *term, struct row *row, struct cell *cell,
for (int i = 0; i < ctx->empty_count + 1; i++) {
struct cell *c = &row->cells[col - i];
- if (c->attrs.selected & 1)
- c->attrs.selected = 1; /* Clear the pre-mark bit */
- else {
+ if (!c->attrs.selected) {
row->dirty = true;
- c->attrs.selected = 1;
- c->attrs.clean = 0;
+ c->attrs.selected = true;
+ c->attrs.clean = false;
}
}
@@ -523,18 +543,26 @@ selection_modify(struct terminal *term, struct coord start, struct coord end)
xassert(start.row != -1 && start.col != -1);
xassert(end.row != -1 && end.col != -1);
- struct mark_context ctx = {0};
+#define reset_context() do { \
+ ctx.last_row = NULL; \
+ ctx.empty_count = 0; \
+ } while (0)
+
+ uint64_t **keep_selection =
+ xcalloc(term->grid->num_rows, sizeof(keep_selection[0]));
+
+ struct mark_context ctx = {.keep_selection = keep_selection};
/* Premark all cells that *will* be selected */
foreach_selected(term, start, end, &premark_selected, &ctx);
- memset(&ctx, 0, sizeof(ctx));
+ reset_context();
if (term->selection.end.row >= 0) {
/* Unmark previous selection, ignoring cells that are part of
* the new selection */
foreach_selected(term, term->selection.start, term->selection.end,
&unmark_selected, &ctx);
- memset(&ctx, 0, sizeof(ctx));
+ reset_context();
}
term->selection.start = start;
@@ -543,6 +571,15 @@ selection_modify(struct terminal *term, struct coord start, struct coord end)
/* Mark new selection */
foreach_selected(term, start, end, &mark_selected, &ctx);
render_refresh(term);
+
+ for (size_t i = 0; i < term->grid->num_rows; i++) {
+ if (keep_selection[i] == NULL)
+ continue;
+ free(keep_selection[i]);
+ }
+ free(keep_selection);
+
+#undef reset_context
}
static void
diff --git a/terminal.h b/terminal.h
index f394a5b0..df253434 100644
--- a/terminal.h
+++ b/terminal.h
@@ -46,9 +46,9 @@ struct attributes {
bool confined:1;
bool have_fg:1;
bool have_bg:1;
- uint32_t selected:2;
+ bool selected:1;
bool url:1;
- uint32_t reserved:1;
+ uint32_t reserved:2;
uint32_t bg:24;
};
static_assert(sizeof(struct attributes) == 8, "VT attribute struct too large");