aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--composed.c76
-rw-r--r--composed.h18
-rw-r--r--extract.c7
-rw-r--r--grid.c4
-rw-r--r--grid.h4
-rw-r--r--meson.build1
-rw-r--r--render.c9
-rw-r--r--search.c5
-rw-r--r--selection.c28
-rw-r--r--terminal.c3
-rw-r--r--terminal.h7
-rw-r--r--vt.c90
12 files changed, 168 insertions, 84 deletions
diff --git a/composed.c b/composed.c
new file mode 100644
index 00000000..f969c8f1
--- /dev/null
+++ b/composed.c
@@ -0,0 +1,76 @@
+#include "composed.h"
+
+#include <stdlib.h>
+#include <stdbool.h>
+
+#include "debug.h"
+
+struct composed *
+composed_lookup(struct composed *root, uint32_t key)
+{
+ struct composed *node = root;
+
+ while (node != NULL) {
+ if (key == node->key)
+ return node;
+
+ node = key < node->key ? node->left : node->right;
+ }
+
+ return NULL;
+}
+
+uint32_t
+composed_insert(struct composed **root, struct composed *node)
+{
+ node->left = node->right = NULL;
+
+ if (*root == NULL) {
+ *root = node;
+ return node->key;
+ }
+
+ uint32_t key = node->key;
+
+ struct composed *prev = NULL;
+ struct composed *n = *root;
+
+ while (n != NULL) {
+ if (n->key == node->key) {
+ /* TODO: wrap around at (CELL_COMB_CHARS_HI - CELL_COMB_CHARS_LO) */
+ key++;
+ }
+
+ prev = n;
+ n = key < n->key ? n->left : n->right;
+ }
+
+ xassert(prev != NULL);
+ xassert(n == NULL);
+
+ /* May have been changed */
+ node->key = key;
+
+ if (key < prev->key) {
+ xassert(prev->left == NULL);
+ prev->left = node;
+ } else {
+ xassert(prev->right == NULL);
+ prev->right = node;
+ }
+
+ return key;
+}
+
+void
+composed_free(struct composed *root)
+{
+ if (root == NULL)
+ return;
+
+ composed_free(root->left);
+ composed_free(root->right);
+
+ free(root->chars);
+ free(root);
+}
diff --git a/composed.h b/composed.h
new file mode 100644
index 00000000..3511ad30
--- /dev/null
+++ b/composed.h
@@ -0,0 +1,18 @@
+#pragma once
+
+#include <stdint.h>
+#include <wchar.h>
+
+struct composed {
+ wchar_t *chars;
+ struct composed *left;
+ struct composed *right;
+ uint32_t key;
+ uint8_t count;
+ uint8_t width;
+};
+
+struct composed *composed_lookup(struct composed *root, uint32_t key);
+uint32_t composed_insert(struct composed **root, struct composed *node);
+
+void composed_free(struct composed *root);
diff --git a/extract.c b/extract.c
index 8aa1acf3..4acd481c 100644
--- a/extract.c
+++ b/extract.c
@@ -223,11 +223,10 @@ extract_one(const struct terminal *term, const struct row *row,
ctx->newline_count = 0;
ctx->empty_count = 0;
- if (cell->wc >= CELL_COMB_CHARS_LO &&
- cell->wc < (CELL_COMB_CHARS_LO + term->composed_count))
+ if (cell->wc >= CELL_COMB_CHARS_LO && cell->wc <= CELL_COMB_CHARS_HI)
{
- const struct composed *composed
- = &term->composed[cell->wc - CELL_COMB_CHARS_LO];
+ const struct composed *composed = composed_lookup(
+ term->composed, cell->wc - CELL_COMB_CHARS_LO);
if (!ensure_size(ctx, composed->count))
goto err;
diff --git a/grid.c b/grid.c
index 4419434c..733d8ded 100644
--- a/grid.c
+++ b/grid.c
@@ -416,9 +416,7 @@ grid_resize_and_reflow(
struct grid *grid, int new_rows, int new_cols,
int old_screen_rows, int new_screen_rows,
size_t tracking_points_count,
- struct coord *const _tracking_points[static tracking_points_count],
- size_t compose_count, const struct
- composed composed[static compose_count])
+ struct coord *const _tracking_points[static tracking_points_count])
{
#if defined(TIME_REFLOW) && TIME_REFLOW
struct timeval start;
diff --git a/grid.h b/grid.h
index c41a5ba5..3537ddb5 100644
--- a/grid.h
+++ b/grid.h
@@ -19,9 +19,7 @@ void grid_resize_and_reflow(
struct grid *grid, int new_rows, int new_cols,
int old_screen_rows, int new_screen_rows,
size_t tracking_points_count,
- struct coord *const _tracking_points[static tracking_points_count],
- size_t compose_count,
- const struct composed composed[static compose_count]);
+ struct coord *const _tracking_points[static tracking_points_count]);
static inline int
grid_row_absolute(const struct grid *grid, int row_no)
diff --git a/meson.build b/meson.build
index 107fd905..33b54c9c 100644
--- a/meson.build
+++ b/meson.build
@@ -147,6 +147,7 @@ misc = static_library(
vtlib = static_library(
'vtlib',
'base64.c', 'base64.h',
+ 'composed.c', 'composed.h',
'csi.c', 'csi.h',
'dcs.c', 'dcs.h',
'osc.c', 'osc.h',
diff --git a/render.c b/render.c
index 5bb1023e..d3e03b63 100644
--- a/render.c
+++ b/render.c
@@ -557,10 +557,9 @@ render_cell(struct terminal *term, pixman_image_t *pix,
cell_cols = single->cols;
}
- else if (base >= CELL_COMB_CHARS_LO &&
- base < (CELL_COMB_CHARS_LO + term->composed_count))
+ else if (base >= CELL_COMB_CHARS_LO && base <= CELL_COMB_CHARS_HI)
{
- composed = &term->composed[base - CELL_COMB_CHARS_LO];
+ composed = composed_lookup(term->composed, base - CELL_COMB_CHARS_LO);
base = composed->chars[0];
if (term->conf->can_shape_grapheme && term->conf->tweak.grapheme_shaping) {
@@ -3339,8 +3338,8 @@ maybe_resize(struct terminal *term, int width, int height, bool force)
/* Resize grids */
grid_resize_and_reflow(
&term->normal, new_normal_grid_rows, new_cols, old_rows, new_rows,
- term->selection.end.row >= 0 ? ALEN(tracking_points) : 0, tracking_points,
- term->composed_count, term->composed);
+ term->selection.end.row >= 0 ? ALEN(tracking_points) : 0,
+ tracking_points);
grid_resize_without_reflow(
&term->alt, new_alt_grid_rows, new_cols, old_rows, new_rows);
diff --git a/search.c b/search.c
index 859608f5..8f28a656 100644
--- a/search.c
+++ b/search.c
@@ -245,10 +245,9 @@ matches_cell(const struct terminal *term, const struct cell *cell, size_t search
wchar_t base = cell->wc;
const struct composed *composed = NULL;
- if (base >= CELL_COMB_CHARS_LO &&
- base < (CELL_COMB_CHARS_LO + term->composed_count))
+ if (base >= CELL_COMB_CHARS_LO && base <= CELL_COMB_CHARS_HI)
{
- composed = &term->composed[base - CELL_COMB_CHARS_LO];
+ composed = composed_lookup(term->composed, base - CELL_COMB_CHARS_LO);
base = composed->chars[0];
}
diff --git a/selection.c b/selection.c
index cafb161e..57ab8bf6 100644
--- a/selection.c
+++ b/selection.c
@@ -246,11 +246,8 @@ selection_find_word_boundary_left(struct terminal *term, struct coord *pos,
c = r->cells[pos->col].wc;
}
- if (c >= CELL_COMB_CHARS_LO &&
- c < (CELL_COMB_CHARS_LO + term->composed_count))
- {
- c = term->composed[c - CELL_COMB_CHARS_LO].chars[0];
- }
+ if (c >= CELL_COMB_CHARS_LO && c <= CELL_COMB_CHARS_HI)
+ c = composed_lookup(term->composed, c - CELL_COMB_CHARS_LO)->chars[0];
bool initial_is_space = c == 0 || iswspace(c);
bool initial_is_delim =
@@ -286,11 +283,8 @@ selection_find_word_boundary_left(struct terminal *term, struct coord *pos,
c = row->cells[next_col].wc;
}
- if (c >= CELL_COMB_CHARS_LO &&
- c < (CELL_COMB_CHARS_LO + term->composed_count))
- {
- c = term->composed[c - CELL_COMB_CHARS_LO].chars[0];
- }
+ if (c >= CELL_COMB_CHARS_LO && c <= CELL_COMB_CHARS_HI)
+ c = composed_lookup(term->composed, c - CELL_COMB_CHARS_LO)->chars[0];
bool is_space = c == 0 || iswspace(c);
bool is_delim =
@@ -325,11 +319,8 @@ selection_find_word_boundary_right(struct terminal *term, struct coord *pos,
c = r->cells[pos->col].wc;
}
- if (c >= CELL_COMB_CHARS_LO &&
- c < (CELL_COMB_CHARS_LO + term->composed_count))
- {
- c = term->composed[c - CELL_COMB_CHARS_LO].chars[0];
- }
+ if (c >= CELL_COMB_CHARS_LO && c <= CELL_COMB_CHARS_HI)
+ c = composed_lookup(term->composed, c - CELL_COMB_CHARS_LO)->chars[0];
bool initial_is_space = c == 0 || iswspace(c);
bool initial_is_delim =
@@ -367,11 +358,8 @@ selection_find_word_boundary_right(struct terminal *term, struct coord *pos,
c = row->cells[next_col].wc;
}
- if (c >= CELL_COMB_CHARS_LO &&
- c < (CELL_COMB_CHARS_LO + term->composed_count))
- {
- c = term->composed[c - CELL_COMB_CHARS_LO].chars[0];
- }
+ if (c >= CELL_COMB_CHARS_LO && c <= CELL_COMB_CHARS_HI)
+ c = composed_lookup(term->composed, c - CELL_COMB_CHARS_LO)->chars[0];
bool is_space = c == 0 || iswspace(c);
bool is_delim =
diff --git a/terminal.c b/terminal.c
index 9e0795a1..cb836fef 100644
--- a/terminal.c
+++ b/terminal.c
@@ -1132,7 +1132,6 @@ term_init(const struct config *conf, struct fdm *fdm, struct reaper *reaper,
.normal = {.scroll_damage = tll_init(), .sixel_images = tll_init()},
.alt = {.scroll_damage = tll_init(), .sixel_images = tll_init()},
.grid = &term->normal,
- .composed_count = 0,
.composed = NULL,
.alt_scrolling = conf->mouse.alternate_scroll_mode,
.meta = {
@@ -1431,7 +1430,7 @@ term_destroy(struct terminal *term)
grid_free(&term->normal);
grid_free(&term->alt);
- free(term->composed);
+ composed_free(term->composed);
free(term->window_title);
tll_free_and_free(term->window_title_stack, free);
diff --git a/terminal.h b/terminal.h
index c9f5aee8..00c4221f 100644
--- a/terminal.h
+++ b/terminal.h
@@ -16,6 +16,7 @@
#include <fcft/fcft.h>
//#include "config.h"
+#include "composed.h"
#include "debug.h"
#include "fdm.h"
#include "macros.h"
@@ -84,12 +85,6 @@ struct damage {
int lines;
};
-struct composed {
- wchar_t chars[10];
- uint8_t count;
- int width;
-};
-
struct row_uri_range {
int start;
int end;
diff --git a/vt.c b/vt.c
index bbe6fc9a..158ac539 100644
--- a/vt.c
+++ b/vt.c
@@ -611,21 +611,22 @@ action_utf8_print(struct terminal *term, wchar_t wc)
xassert(col >= 0 && col < term->cols);
wchar_t base = row->cells[col].wc;
wchar_t UNUSED last = base;
- size_t search_start_index = 0;
+ uint32_t key = base ^ wc;
/* Is base cell already a cluster? */
const struct composed *composed =
- (base >= CELL_COMB_CHARS_LO &&
- base < (CELL_COMB_CHARS_LO + term->composed_count))
- ? &term->composed[base - CELL_COMB_CHARS_LO]
+ (base >= CELL_COMB_CHARS_LO && base <= CELL_COMB_CHARS_HI)
+ ? composed_lookup(term->composed, base - CELL_COMB_CHARS_LO)
: NULL;
if (composed != NULL) {
- search_start_index = base - CELL_COMB_CHARS_LO;
base = composed->chars[0];
last = composed->chars[composed->count - 1];
+ key = composed->key ^ wc;
}
+ key &= CELL_COMB_CHARS_HI - CELL_COMB_CHARS_LO;
+
#if defined(FOOT_GRAPHEME_CLUSTERING)
if (grapheme_clustering) {
/* Check if we're on a grapheme cluster break */
@@ -677,7 +678,7 @@ action_utf8_print(struct terminal *term, wchar_t wc)
}
size_t wanted_count = composed != NULL ? composed->count + 1 : 2;
- if (wanted_count > ALEN(composed->chars)) {
+ if (wanted_count > 255) {
xassert(composed != NULL);
#if defined(LOG_ENABLE_DBG) && LOG_ENABLE_DBG
@@ -691,47 +692,46 @@ action_utf8_print(struct terminal *term, wchar_t wc)
wanted_count--;
}
- xassert(wanted_count <= ALEN(composed->chars));
+ xassert(wanted_count <= 255);
/* Look for existing combining chain */
- for (size_t i = search_start_index; i < term->composed_count; i++) {
- const struct composed *cc = &term->composed[i];
+ while (true) {
+ const struct composed *cc = composed_lookup(term->composed, key);
+ if (cc == NULL)
+ break;
- if (cc->chars[0] != base)
- continue;
+ /*
+ * We may have a key collisison, so need to check that
+ * it’s a true match. If not, bumb the key and try
+ * again.
+ */
- if (cc->count != wanted_count)
+ if (cc->chars[0] != base ||
+ cc->count != wanted_count ||
+ cc->chars[wanted_count - 1] != wc)
+ {
+ key++;
continue;
-
- bool match = true;
- for (size_t j = 1; j < wanted_count - 1; j++) {
- if (cc->chars[j] != composed->chars[j]) {
- match = false;
- break;
- }
}
- if (!match)
- continue;
- if (cc->chars[wanted_count - 1] != wc)
+ bool match = composed != NULL
+ ? memcmp(&cc->chars[1], &composed->chars[1],
+ (wanted_count - 2) * sizeof(cc->chars[0])) == 0
+ : true;
+
+ if (!match) {
+ key++;
continue;
+ }
- wc = CELL_COMB_CHARS_LO + i;
+ wc = CELL_COMB_CHARS_LO + cc->key;
width = cc->width;
goto out;
}
- /* Allocate new chain */
-
- struct composed new_cc;
- new_cc.count = wanted_count;
- new_cc.chars[0] = base;
-
- for (size_t i = 1; i < wanted_count - 1; i++)
- new_cc.chars[i] = composed->chars[i];
- new_cc.chars[wanted_count - 1] = wc;
-
- if (unlikely(term->composed_count >= CELL_COMB_CHARS_HI)) {
+ if (unlikely(term->composed_count >=
+ (CELL_COMB_CHARS_HI - CELL_COMB_CHARS_LO)))
+ {
/* We reached our maximum number of allowed composed
* character chains. Fall through here and print the
* current zero-width character to the current cell */
@@ -739,18 +739,32 @@ action_utf8_print(struct terminal *term, wchar_t wc)
goto out;
}
+ /* Allocate new chain */
+ struct composed *new_cc = xmalloc(sizeof(*new_cc));
+ new_cc->chars = xmalloc(wanted_count * sizeof(new_cc->chars[0]));
+ new_cc->key = key;
+ new_cc->count = wanted_count;
+ new_cc->chars[0] = base;
+ new_cc->chars[wanted_count - 1] = wc;
+
+ if (composed != NULL) {
+ memcpy(&new_cc->chars[1], &composed->chars[1],
+ (wanted_count - 2) * sizeof(new_cc->chars[0]));
+ }
+
int grapheme_width = composed != NULL ? composed->width : base_width;
+
if (wc == 0xfe0f && grapheme_width < 2)
grapheme_width = 2;
else
grapheme_width += width;
- new_cc.width = grapheme_width;
+ new_cc->width = grapheme_width;
term->composed_count++;
- term->composed = xrealloc(term->composed, term->composed_count * sizeof(term->composed[0]));
- term->composed[term->composed_count - 1] = new_cc;
+ key = composed_insert(&term->composed, new_cc);
+ wc = CELL_COMB_CHARS_LO + key;
+ xassert(wc <= CELL_COMB_CHARS_HI);
- wc = CELL_COMB_CHARS_LO + term->composed_count - 1;
width = grapheme_width;
goto out;
}