diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/hist.c | 133 | ||||
| -rw-r--r-- | src/hist_view.c | 63 |
2 files changed, 126 insertions, 70 deletions
@@ -123,9 +123,18 @@ static bool cont_push(struct hist *h, uint64_t seq) uint64_t *cont = malloc((size_t)cap * sizeof(*cont)); if (!cont) return false; - for (uint32_t i = 0; i < h->cont_count; i++) - cont[i] = cont_at(h, i); - free(h->cont); + if (h->cont) { + uint32_t count = h->cont_count; + uint32_t first = h->cont_first; + uint32_t old_cap = h->cont_mask + 1; + uint32_t chunk = old_cap - first; + if (chunk > count) + chunk = count; + memcpy(cont, h->cont + first, (size_t)chunk * sizeof(*cont)); + if (count > chunk) + memcpy(cont + chunk, h->cont, (size_t)(count - chunk) * sizeof(*cont)); + free(h->cont); + } h->cont = cont; h->cont_mask = cap - 1; h->cont_first = 0; @@ -165,6 +174,8 @@ static uint64_t line_first(const struct hist *h, uint64_t id) static inline uint64_t line_end(const struct hist *h, uint64_t first) { + if (!h->cont_count) + return first + 1; uint64_t s = first + 1; while (s < h->head && (part(h, s)->flags & HLINE_CONT)) s++; @@ -463,12 +474,12 @@ static uint64_t evict_simple_run(struct hist *h, uint64_t k) (t8 >> 24) != 255 && (t9 >> 24) != 255 && (t10 >> 24) != 255 && (t11 >> 24) != 255 && (t12 >> 24) != 255 && (t13 >> 24) != 255 && (t14 >> 24) != 255 && (t15 >> 24) != 255, 1)) { - uint32_t o0 = f[0].off, o15 = f[15].off; - if (have_page && (o0 >> 16) == page && (o15 >> 16) == page && - o0 != NO_TEXT && f[1].off != NO_TEXT && f[2].off != NO_TEXT && f[3].off != NO_TEXT && - f[4].off != NO_TEXT && f[5].off != NO_TEXT && f[6].off != NO_TEXT && f[7].off != NO_TEXT && - f[8].off != NO_TEXT && f[9].off != NO_TEXT && f[10].off != NO_TEXT && f[11].off != NO_TEXT && - f[12].off != NO_TEXT && f[13].off != NO_TEXT && f[14].off != NO_TEXT && o15 != NO_TEXT) { + uint32_t target = page << 16; + uint32_t off_diff = (f[0].off ^ target) | (f[1].off ^ target) | (f[2].off ^ target) | (f[3].off ^ target) | + (f[4].off ^ target) | (f[5].off ^ target) | (f[6].off ^ target) | (f[7].off ^ target) | + (f[8].off ^ target) | (f[9].off ^ target) | (f[10].off ^ target) | (f[11].off ^ target) | + (f[12].off ^ target) | (f[13].off ^ target) | (f[14].off ^ target) | (f[15].off ^ target); + if (have_page && (off_diff & 0xffff0000u) == 0) { run += 16; } else { for (int j = 0; j < 16; j++) { @@ -548,9 +559,17 @@ static inline void evict_for(struct hist *h, uint64_t n) if (have + n <= (uint64_t)h->line_limit) return; uint64_t need = have + n - h->line_limit; - uint64_t done = evict_simple_run(h, need); - for (uint64_t i = done; i < need; i++) + while (need > 0) { + uint64_t done = evict_simple_run(h, need); + if (done >= need) + break; + need -= done; + uint64_t old_lines = h->lines; evict_line(h); + if (h->lines == old_lines) + break; + need--; + } } /* Drop the oldest line with all its parts. It is never the open line. */ @@ -615,27 +634,57 @@ static inline int page_for(struct hist *h, size_t need) static inline int put_varint(uint8_t *p, uint32_t v) { - int n = 0; - while (v >= 0x80) { - p[n++] = (uint8_t)(v | 0x80); - v >>= 7; + if (TERM_EXPECT(v < 0x80, 1)) { + p[0] = (uint8_t)v; + return 1; } - p[n++] = (uint8_t)v; - return n; + p[0] = (uint8_t)(v | 0x80); + if (TERM_EXPECT(v < 0x4000, 1)) { + p[1] = (uint8_t)(v >> 7); + return 2; + } + p[1] = (uint8_t)((v >> 7) | 0x80); + if (v < 0x200000) { + p[2] = (uint8_t)(v >> 14); + return 3; + } + p[2] = (uint8_t)((v >> 14) | 0x80); + if (v < 0x10000000) { + p[3] = (uint8_t)(v >> 21); + return 4; + } + p[3] = (uint8_t)((v >> 21) | 0x80); + p[4] = (uint8_t)(v >> 28); + return 5; } static inline int get_varint(const uint8_t *p, uint32_t *v) { - uint32_t r = 0; - int shift = 0, n = 0; - uint8_t b; - do { - b = p[n++]; - r |= (uint32_t)(b & 0x7f) << shift; - shift += 7; - } while ((b & 0x80) && shift < 35); - *v = r; - return n; + uint8_t b0 = p[0]; + if (TERM_EXPECT((b0 & 0x80) == 0, 1)) { + *v = b0; + return 1; + } + uint8_t b1 = p[1]; + if (TERM_EXPECT((b1 & 0x80) == 0, 1)) { + *v = (uint32_t)(b0 & 0x7f) | ((uint32_t)b1 << 7); + return 2; + } + uint8_t b2 = p[2]; + if ((b2 & 0x80) == 0) { + *v = (uint32_t)(b0 & 0x7f) | ((uint32_t)(b1 & 0x7f) << 7) | ((uint32_t)b2 << 14); + return 3; + } + uint8_t b3 = p[3]; + if ((b3 & 0x80) == 0) { + *v = (uint32_t)(b0 & 0x7f) | ((uint32_t)(b1 & 0x7f) << 7) | + ((uint32_t)(b2 & 0x7f) << 14) | ((uint32_t)b3 << 21); + return 4; + } + *v = (uint32_t)(b0 & 0x7f) | ((uint32_t)(b1 & 0x7f) << 7) | + ((uint32_t)(b2 & 0x7f) << 14) | ((uint32_t)(b3 & 0x7f) << 21) | + ((uint32_t)(p[4] & 0x7f) << 28); + return 5; } static inline void put_u32(uint8_t *p, uint32_t v) { memcpy(p, &v, 4); } @@ -649,7 +698,7 @@ static inline uint8_t *emit_run(uint8_t *p, const struct pen_attr *base, const s /* Most runs change only colors and cover fewer than 128 cells. */ if (TERM_EXPECT(count < 0x80 && pen_sl(pen) == pen_sl(base), 1)) { uint32_t dfg = pen->fg != base->fg, dbg = pen->bg != base->bg; - p[0] = (uint8_t)(dfg * RUN_FG | dbg * RUN_BG); + p[0] = (uint8_t)(dfg | (dbg << 1)); p[1] = (uint8_t)count; p += 2; put_u32(p, pen->fg); @@ -685,9 +734,7 @@ static bool runs_reserve(struct hist_runs *r, size_t extra) { if (TERM_EXPECT(r->len + extra <= r->cap, 1)) return true; - size_t cap = r->cap ? r->cap : 256; - while (cap < r->len + extra) - cap *= 2; + size_t cap = term_grow_cap(r->cap ? r->cap : 256, (size_t)r->len + extra); uint8_t *data = realloc(r->data, cap); if (!data) return false; @@ -2381,7 +2428,7 @@ static void runs_iter_init(struct runs_iter *it, const struct hist *h, const str /* Take up to n cells of the current run. it->pen is their pen. */ static inline uint32_t runs_take(struct runs_iter *it, uint32_t n) { - while (it->left == 0) { + while (TERM_EXPECT(it->left == 0, 0)) { if (it->p < it->end) { it->p = read_run(it->p, &it->pen, &it->left); } else if (it->pending) { @@ -2488,7 +2535,10 @@ uint64_t term_hist_line_cells(const struct hist *h, uint64_t id) return 0; if (id == h->last_id && h->last_cells) return h->last_cells; - uint64_t first = line_first(h, id), end = line_end(h, first), cells = 0; + uint64_t first = line_first(h, id), end = line_end(h, first); + if (first + 1 == end) + return part(h, first)->cells; + uint64_t cells = 0; for (uint64_t s = first; s < end; s++) cells += part(h, s)->cells; return cells; @@ -2500,7 +2550,10 @@ uint64_t term_hist_line_wide(const struct hist *h, uint64_t id) return 0; if (id == h->last_id && h->last_cells) return h->last_wide; - uint64_t first = line_first(h, id), end = line_end(h, first), wide = 0; + uint64_t first = line_first(h, id), end = line_end(h, first); + if (first + 1 == end) + return part(h, first)->wide; + uint64_t wide = 0; for (uint64_t seq = first; seq < end; seq++) wide += part(h, seq)->wide; return wide; @@ -2512,6 +2565,8 @@ uint8_t term_hist_line_flags(const struct hist *h, uint64_t id) return 0; uint64_t first = line_first(h, id), end = line_end(h, first); uint8_t flags = part(h, first)->flags; + if (first + 1 == end) + return flags; for (uint64_t s = first + 1; s < end; s++) { uint8_t f = part(h, s)->flags; flags = (uint8_t)((flags | f) & ~HLINE_NARROW) | (flags & f & HLINE_NARROW); @@ -2639,7 +2694,7 @@ int term_hist_decode_segments(const struct hist *h, uint64_t id, int start_seg, struct runs_iter it; runs_iter_init(&it, h, p); for (uint64_t k = skip; k > 0;) - k -= runs_take(&it, k > UINT32_MAX ? UINT32_MAX : (uint32_t)k); + k -= runs_take(&it, (uint32_t)k); const char *src = (const char *)part_text(h, p) + skip; while (avail > 0 && seg_idx < count) { int need = cols - n; @@ -2722,7 +2777,7 @@ int term_hist_decode_segments(const struct hist *h, uint64_t id, int start_seg, runs_iter_init(&it, h, p); for (uint32_t k = skipped_cells; k > 0;) - k -= runs_take(&it, k > UINT32_MAX ? UINT32_MAX : k); + k -= runs_take(&it, k); } while (t < tend && row < end_seg) { @@ -3201,10 +3256,8 @@ bool term_hist_init(struct hist *h, int line_limit, size_t byte_cap) h->pages = calloc(h->max_pages, sizeof(*h->pages)); h->page_used = calloc(h->max_pages, sizeof(*h->page_used)); h->page_parts = calloc(h->max_pages, sizeof(*h->page_parts)); - h->page_rows = calloc(h->max_pages, sizeof(*h->page_rows)); - h->page_simple = calloc(h->max_pages, sizeof(*h->page_simple)); h->free_pages = malloc(h->max_pages * sizeof(*h->free_pages)); - if (!h->pages || !h->page_used || !h->page_parts || !h->page_rows || !h->page_simple || !h->free_pages || !ring_reserve(h)) { + if (!h->pages || !h->page_used || !h->page_parts || !h->free_pages || !ring_reserve(h)) { term_hist_free(h); return false; } @@ -3219,8 +3272,6 @@ void term_hist_free(struct hist *h) free(h->pages); free(h->page_used); free(h->page_parts); - free(h->page_rows); - free(h->page_simple); free(h->free_pages); term_aligned_free(h->ring); free(h->blocks); diff --git a/src/hist_view.c b/src/hist_view.c index d413c43..29eac35 100644 --- a/src/hist_view.c +++ b/src/hist_view.c @@ -40,6 +40,8 @@ static void set_count(struct hist_view *v, uint64_t id, uint32_t count) { uint32_t slot = (uint32_t)id & (v->cap - 1); int64_t delta = (int64_t)count - v->counts[slot]; + if (!delta) + return; v->counts[slot] = count; v->total_rows = (uint64_t)((int64_t)v->total_rows + delta); for (uint32_t i = slot + 1; i <= v->cap; i += i & -i) @@ -66,12 +68,11 @@ bool term_hist_view_sync(struct hist_view *v, const struct hist *h, int cols) rebuild = changed > v->cap / 4; } if (h->lines > v->cap || !v->cap) { - uint32_t cap = 16; - while (cap < h->lines) { - if (cap >= UINT32_MAX / 2) - return false; - cap *= 2; - } + if (h->lines > (UINT32_C(1) << 31)) + return false; + uint32_t cap = term_next_pow2_32(h->lines < 16 ? 16 : h->lines); + if (cap == UINT32_MAX) + return false; uint64_t *tree = calloc((size_t)cap + 1, sizeof(*tree)); uint32_t *counts = calloc(cap, sizeof(*counts)); if (!tree || !counts) { @@ -91,15 +92,14 @@ bool term_hist_view_sync(struct hist_view *v, const struct hist *h, int cols) memset(v->fenwick, 0, ((size_t)v->cap + 1) * sizeof(*v->fenwick)); for (uint64_t id = first; id < end; id++) v->counts[(uint32_t)id & (v->cap - 1)] = (uint32_t)term_hist_line_estimate(h, id, cols); - v->total_rows = 0; /* Build all tree nodes in one pass. */ for (uint32_t i = 1; i <= v->cap; i++) { v->fenwick[i] += v->counts[i - 1]; - v->total_rows += v->counts[i - 1]; uint32_t parent = i + (i & -i); if (parent <= v->cap) v->fenwick[parent] += v->fenwick[i]; } + v->total_rows = v->fenwick[v->cap]; } else { for (uint64_t id = v->first_id; id < first; id++) set_count(v, id, 0); @@ -140,25 +140,28 @@ uint64_t term_hist_view_rows(const struct hist_view *v, const struct hist *h, in /* Rows of the retained lines before id, in logical order. */ static uint64_t before(const struct hist_view *v, uint64_t id) { + if (id <= v->first_id) + return 0; uint32_t start = (uint32_t)v->first_id & (v->cap - 1); - uint64_t n = id - v->first_id; - uint32_t stop = start + (uint32_t)n; + uint32_t stop = start + (uint32_t)(id - v->first_id); + uint64_t p_start = prefix(v, start); if (stop <= v->cap) - return prefix(v, stop) - prefix(v, start); - return prefix(v, v->cap) - prefix(v, start) + prefix(v, stop - v->cap); + return prefix(v, stop) - p_start; + return v->total_rows - p_start + prefix(v, stop - v->cap); } /* Physical slot of a row in tree order. */ -static uint32_t select_slot(const struct hist_view *v, uint64_t row) +static uint32_t select_slot(const struct hist_view *v, uint64_t row, int *seg) { uint32_t slot = 0; - for (uint32_t bit = v->cap; bit; bit >>= 1) { + for (uint32_t bit = v->cap >> 1; bit; bit >>= 1) { uint32_t next = slot + bit; - if (next <= v->cap && v->fenwick[next] <= row) { + if (v->fenwick[next] <= row) { row -= v->fenwick[next]; slot = next; } } + *seg = (int)row; return slot; } @@ -186,9 +189,8 @@ bool term_hist_view_find_row(const struct hist_view *v, const struct hist *h, in uint32_t start = (uint32_t)v->first_id & (v->cap - 1); uint64_t low = prefix(v, start), high = total - low; uint64_t physical = (uint64_t)row < high ? low + row : (uint64_t)row - high; - uint32_t slot = select_slot(v, physical); + uint32_t slot = select_slot(v, physical, seg); *id = v->first_id + ((slot - start) & (v->cap - 1)); - *seg = (int)(physical - prefix(v, slot)); return true; } @@ -292,18 +294,21 @@ void term_hist_view_scroll(struct hist_view *v, const struct hist *h, int cols, seg = term_hist_line_rows(h, id, cols); } seg -= (int64_t)lines; - while (seg < 0 && id > hist_first_id(h)) - seg += term_hist_line_rows(h, --id, cols); - if (seg < 0) - seg = 0; - for (;;) { - int count = term_hist_line_rows(h, id, cols); - if (seg < count) - break; - seg -= count; - if (++id == hist_end_id(h)) { - term_hist_view_reset_bottom(v); - return; + if (lines > 0) { + while (seg < 0 && id > hist_first_id(h)) + seg += term_hist_line_rows(h, --id, cols); + if (seg < 0) + seg = 0; + } else { + for (;;) { + int count = term_hist_line_rows(h, id, cols); + if (seg < count) + break; + seg -= count; + if (++id == hist_end_id(h)) { + term_hist_view_reset_bottom(v); + return; + } } } v->anchor = (struct view_anchor){ .line_id = id, .seg = (uint32_t)seg, |