diff options
| -rw-r--r-- | src/snapshot.c | 203 |
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; |