From ae70596a5034f9fd6bbca6b42e4fe52c42c70d34 Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Fri, 13 Aug 2021 17:45:09 +0200 Subject: selection: don’t require two cell attr bits for selection updating MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit 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). --- terminal.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'terminal.h') 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"); -- cgit v1.3