summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/snapshot.c203
1 files changed, 140 insertions, 63 deletions
diff --git a/src/snapshot.c b/src/snapshot.c
index 78c66b0..6f396e2 100644
--- a/src/snapshot.c
+++ b/src/snapshot.c
@@ -16,6 +16,7 @@ struct term_snapshot {
uint64_t source; /* serial of the terminal it copied */
struct term_cell *cells; /* rows * cols */
+ struct term_cell *stage; /* rows * cols: changed rows, before apply() */
uint64_t *keys; /* per row */
uint32_t *row_clusters; /* arena records each row holds */
struct term_span *selection; /* per row */
@@ -24,6 +25,9 @@ struct term_snapshot {
uint32_t *arena;
uint32_t arena_len, arena_cap, arena_dead;
+ /* A rebuild writes its records here, then swaps it with arena. */
+ uint32_t *spare;
+ uint32_t spare_cap;
};
struct term_snapshot *term_snapshot_new(void)
@@ -39,10 +43,12 @@ void term_snapshot_free(struct term_snapshot *s)
if (!s)
return;
free(s->cells);
+ free(s->stage);
free(s->keys);
free(s->row_clusters);
free(s->selection);
free(s->arena);
+ free(s->spare);
free(s);
}
@@ -56,6 +62,10 @@ static bool reserve(struct term_snapshot *s, int cols, int rows)
if (!c)
return false;
s->cells = c;
+ struct term_cell *st = realloc(s->stage, cells * sizeof(*st));
+ if (!st)
+ return false;
+ s->stage = st;
s->cell_cap = cells;
}
if (rows > s->row_cap) {
@@ -75,50 +85,67 @@ static bool reserve(struct term_snapshot *s, int cols, int rows)
return true;
}
-/* Append a cluster record. The caller reserved room for it. */
-static uint32_t arena_add(struct term_snapshot *s, const struct gstore *g, uint32_t handle)
+/* The arena that phase 1 appends cluster records to: the live arena after
+ * its records, or the spare arena for a rebuild. Records past arena_len are
+ * not visible, so a failed update leaves nothing behind. */
+struct arena_out {
+ uint32_t **buf;
+ uint32_t *cap;
+ uint32_t len;
+};
+
+/* Make room for need words. False when memory runs out or an offset would not
+ * fit below TERM_TEXT_CLUSTER. */
+static bool arena_reserve(struct arena_out *a, uint64_t need)
{
- uint32_t cps[TERM_GRAPHEME_MAX_LEN];
- int n = term_gstore_expand(g, handle, cps, TERM_GRAPHEME_MAX_LEN);
- if (n <= 0)
- return ' ';
- uint32_t off = s->arena_len;
- s->arena[off] = (uint32_t)n;
- memcpy(&s->arena[off + 1], cps, (size_t)n * sizeof(*cps));
- s->arena_len += (uint32_t)n + 1;
- return TERM_TEXT_CLUSTER | off;
+ if (need > TERM_TEXT_CLUSTER)
+ return false;
+ if (need <= *a->cap)
+ return true;
+ uint32_t cap = term_grow_cap32(*a->cap ? *a->cap * 2 : 256, (uint32_t)need);
+ uint32_t *grown = realloc(*a->buf, cap * sizeof(*grown));
+ if (!grown)
+ return false;
+ *a->buf = grown;
+ *a->cap = cap;
+ return true;
}
-/* Arena words that converting src adds. Counts what arena_add() writes. */
-static uint64_t row_words(const struct gstore *g, const struct cell *src, int cols)
+/* Append a cluster record and set *text to it. False when arena_reserve()
+ * fails. */
+static bool arena_add(struct arena_out *a, const struct gstore *g, uint32_t handle,
+ uint32_t *text)
{
uint32_t cps[TERM_GRAPHEME_MAX_LEN];
- uint64_t words = 0;
- for (int x = 0; x < cols; x++) {
- uint32_t text = src[x].c;
- if (!term_grapheme_is_handle(text))
- continue;
- int n = term_gstore_expand(g, text, cps, TERM_GRAPHEME_MAX_LEN);
- if (n > 0)
- words += (uint64_t)n + 1;
+ int n = term_gstore_expand(g, handle, cps, TERM_GRAPHEME_MAX_LEN);
+ if (n <= 0) {
+ *text = ' ';
+ return true;
}
- return words;
+ uint64_t need = (uint64_t)a->len + (uint32_t)n + 1;
+ if (!arena_reserve(a, need))
+ return false;
+ uint32_t off = a->len;
+ (*a->buf)[off] = (uint32_t)n;
+ memcpy(&(*a->buf)[off + 1], cps, (size_t)n * sizeof(*cps));
+ a->len = (uint32_t)need;
+ *text = TERM_TEXT_CLUSTER | off;
+ return true;
}
-/* Convert one stored row; returns the number of arena words it added. */
-static uint32_t convert_row(struct term_snapshot *s, const struct gstore *g,
- struct term_cell *dst,
- const struct cell *src, int cols)
+/* Convert one stored row into dst. False when a cluster record does not fit. */
+static bool convert_row(struct arena_out *a, const struct gstore *g,
+ struct term_cell *dst, const struct cell *src, int cols)
{
- uint32_t before = s->arena_len;
for (int x = 0; x < cols; x++) {
const struct cell *c = &src[x];
uint16_t f = c->flags;
uint32_t text = c->c;
if (TERM_EXPECT(text < 0x20, 0))
text = text ? ' ' : 0;
- else if (TERM_EXPECT(term_grapheme_is_handle(text), 0))
- text = arena_add(s, g, text);
+ else if (TERM_EXPECT(term_grapheme_is_handle(text), 0) &&
+ !arena_add(a, g, text, &text))
+ return false;
dst[x] = (struct term_cell){
.text = text,
.fg = c->fg,
@@ -127,14 +154,23 @@ static uint32_t convert_row(struct term_snapshot *s, const struct gstore *g,
.width = (f & CELL_TRAIL) ? 0 : (f & CELL_WIDE) ? 2 : 1,
};
}
- return s->arena_len - before;
+ return true;
}
+/* A row that keeps its old copy. */
+#define ROW_KEPT UINT32_MAX
+/* The most arena words reserved so that apply() can convert rows directly. */
+#define DIRECT_MAX_WORDS (1u << 16)
+
/* What one update does. Phase 1 fills it in and changes no snapshot field. */
struct plan {
- bool all; /* rebuild every row and reset the arena */
+ bool all; /* rebuild every row and swap in the spare arena */
int scrolled; /* rows the content moved up */
+ uint32_t arena_len; /* arena length with the new records */
const uint64_t *keys; /* key of each new row */
+ const uint32_t *words; /* arena words of each staged row, or ROW_KEPT */
+ int staged; /* rows that are not ROW_KEPT */
+ bool direct; /* apply() converts the rows; the arena has room */
const int *c0, *c1; /* selected columns of each row */
};
@@ -144,16 +180,34 @@ static void apply(struct term_snapshot *s, const struct term *t, const struct pl
int cols = t->cols, rows = t->rows;
int k = p->scrolled;
if (p->all) {
- s->arena_len = 0;
+ uint32_t *arena = s->arena, cap = s->arena_cap;
+ s->arena = s->spare;
+ s->arena_cap = s->spare_cap;
+ s->spare = arena;
+ s->spare_cap = cap;
s->arena_dead = 0;
}
+ s->arena_len = p->arena_len;
bool changed = p->all;
+ size_t row_bytes = (size_t)cols * sizeof(struct term_cell);
+ /* Staged rows: copy the smaller part. Either the kept rows go into the
+ * stage, which then becomes the cells, or the staged rows go into the
+ * cells. A scroll moves every kept row anyway, so it swaps. */
+ bool swap = !p->direct && (k > 0 || p->staged * 2 > rows);
+ if (p->direct && k > 0)
+ memmove(s->cells, s->cells + (size_t)k * cols, (size_t)(rows - k) * row_bytes);
+ if (swap) {
+ for (int y = 0; y < rows; y++)
+ if (p->words[y] == ROW_KEPT)
+ memcpy(s->stage + (size_t)y * cols, s->cells + (size_t)(y + k) * cols, row_bytes);
+ struct term_cell *cells = s->cells;
+ s->cells = s->stage;
+ s->stage = cells;
+ }
if (k > 0) {
for (int y = 0; y < k; y++)
s->arena_dead += s->row_clusters[y];
- memmove(s->cells, s->cells + (size_t)k * cols,
- (size_t)(rows - k) * cols * sizeof(struct term_cell));
memmove(s->row_clusters, s->row_clusters + k,
(size_t)(rows - k) * sizeof(uint32_t));
memmove(s->keys, s->keys + k,
@@ -163,15 +217,23 @@ static void apply(struct term_snapshot *s, const struct term *t, const struct pl
}
for (int y = 0; y < rows; y++) {
- uint64_t key = p->keys[y];
- if (!p->all && s->keys[y] == key)
+ if (p->words[y] == ROW_KEPT)
continue;
if (!p->all)
s->arena_dead += s->row_clusters[y];
- const struct cell *src = term_screen_view_row(t, y);
- s->row_clusters[y] = convert_row(s, t->gstore, s->cells + (size_t)y * cols,
- src, cols);
- s->keys[y] = key;
+ if (p->direct) {
+ /* Phase 1 reserved room for the worst case, so this cannot fail. */
+ struct arena_out a = { &s->arena, &s->arena_cap, s->arena_len };
+ (void)convert_row(&a, t->gstore, s->cells + (size_t)y * cols,
+ term_screen_view_row(t, y), cols);
+ s->row_clusters[y] = a.len - s->arena_len;
+ s->arena_len = a.len;
+ } else {
+ if (!swap)
+ memcpy(s->cells + (size_t)y * cols, s->stage + (size_t)y * cols, row_bytes);
+ s->row_clusters[y] = p->words[y];
+ }
+ s->keys[y] = p->keys[y];
changed = true;
}
@@ -222,25 +284,28 @@ static bool term_snapshot_update_inner(struct term_snapshot *s, struct term *t)
bool resized = s->view.size.x != cols || s->view.size.y != rows;
bool all = resized || s->source != t->serial;
int scrolled = 0;
- uint64_t need = 0;
if (!reserve(s, cols, rows))
return false;
- /* Scratch for rows above 256: new keys, then the selection spans. */
+ /* Scratch for rows above 256: new keys, staged arena words, then the
+ * selection spans. */
uint64_t stack_keys[256];
+ uint32_t stack_words[256];
int stack[2][256];
uint64_t *new_keys = stack_keys;
+ uint32_t *words = stack_words;
int *c0 = stack[0], *c1 = stack[1];
void *heap = NULL;
if (rows > 256) {
- heap = malloc((size_t)rows * (sizeof(*new_keys) + 2 * sizeof(*c0)));
+ heap = malloc((size_t)rows * (sizeof(*new_keys) + sizeof(*words) + 2 * sizeof(*c0)));
if (!heap)
return false;
new_keys = heap;
- c0 = (int *)(new_keys + rows);
+ words = (uint32_t *)(new_keys + rows);
+ c0 = (int *)(words + rows);
c1 = c0 + rows;
}
- struct plan p = { .keys = new_keys, .c0 = c0, .c1 = c1 };
+ struct plan p = { .keys = new_keys, .words = words, .c0 = c0, .c1 = c1 };
/* Reclaim cluster records once most of the arena is garbage. */
if (s->arena_dead > 4096 && s->arena_dead * 2 > s->arena_len)
@@ -295,33 +360,45 @@ static bool term_snapshot_update_inner(struct term_snapshot *s, struct term *t)
}
}
- /* Arena words for the rows that apply() converts. Count them before
- * anything changes, then grow the arena once so apply() cannot fail. */
- need = all ? 0 : s->arena_len;
+ /* Mark the rows that change. A row that scrolled in from below has no
+ * old copy. */
for (int y = 0; y < rows; y++) {
- uint64_t kept = s->keys[y];
- if (scrolled)
- kept = y + scrolled < rows ? s->keys[y + scrolled] : 0;
- if (!all && kept == new_keys[y])
- continue;
- need += row_words(t->gstore, term_screen_view_row(t, y), cols);
+ if (!all && y + scrolled < rows && s->keys[y + scrolled] == new_keys[y]) {
+ words[y] = ROW_KEPT;
+ } else {
+ words[y] = 0;
+ p.staged++;
+ }
}
- /* Offsets must fit below TERM_TEXT_CLUSTER. */
- if (need > TERM_TEXT_CLUSTER)
- goto done;
- if (need > s->arena_cap) {
- uint32_t cap = term_grow_cap32(s->arena_cap ? s->arena_cap * 2 : 256, (uint32_t)need);
- uint32_t *a = realloc(s->arena, cap * sizeof(*a));
- if (!a)
+
+ /* Nothing a reader sees may change before apply(). A few rows convert in
+ * apply(), straight into the cells, once the arena has room for the most
+ * they can add. More rows convert here into the stage, with their cluster
+ * records after the live ones, or in the spare arena for a rebuild. */
+ struct arena_out a = all ? (struct arena_out){ &s->spare, &s->spare_cap, 0 }
+ : (struct arena_out){ &s->arena, &s->arena_cap, s->arena_len };
+ uint64_t worst = (uint64_t)p.staged * (uint64_t)cols * (1 + TERM_GRAPHEME_MAX_LEN);
+ if (!all && worst <= DIRECT_MAX_WORDS) {
+ if (!arena_reserve(&a, a.len + worst))
goto done;
- s->arena = a;
- s->arena_cap = cap;
+ p.direct = true;
+ } else {
+ for (int y = 0; y < rows; y++) {
+ if (words[y] == ROW_KEPT)
+ continue;
+ uint32_t before = a.len;
+ if (!convert_row(&a, t->gstore, s->stage + (size_t)y * cols,
+ term_screen_view_row(t, y), cols))
+ goto done;
+ words[y] = a.len - before;
+ }
}
if (!term_selection_view_spans(t, c0, c1))
goto done;
p.all = all;
p.scrolled = scrolled;
+ p.arena_len = a.len;
apply(s, t, &p);
ok = true;
generated by cgit v1.2.3 (git 2.39.1) at 2026-10-25 03:39:33 +0000