aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDaniel Eklöf <daniel@ekloef.se>2025-01-24 13:15:01 +0000
committerDaniel Eklöf <daniel@ekloef.se>2025-02-06 06:42:37 +0000
commite248e73753d61bfd24f1af8e824231434db63c53 (patch)
treeea691f1e970d04d7b8a1b45e68db589b1debeaba
parentcomposed: re-factor: break out key calculation from vt.c (diff)
composed: refactor: break out lookup with collision detection
-rw-r--r--composed.c37
-rw-r--r--composed.h6
-rw-r--r--vt.c64
3 files changed, 54 insertions, 53 deletions
diff --git a/composed.c b/composed.c
index 7a36275e..2d9ed47d 100644
--- a/composed.c
+++ b/composed.c
@@ -51,7 +51,7 @@ UNITTEST
xassert(k3 == k4);
}
-struct composed *
+const struct composed *
composed_lookup(struct composed *root, uint32_t key)
{
struct composed *node = root;
@@ -66,6 +66,41 @@ composed_lookup(struct composed *root, uint32_t key)
return NULL;
}
+const struct composed *
+composed_lookup_without_collision(struct composed *root, uint32_t *key,
+ const char32_t *prefix_text, size_t prefix_len,
+ char32_t wc, int forced_width)
+{
+ while (true) {
+ const struct composed *cc = composed_lookup(root, *key);
+ if (cc == NULL)
+ return NULL;
+
+ bool match = cc->count == prefix_len + 1 &&
+ cc->forced_width == forced_width &&
+ cc->chars[prefix_len] == wc;
+
+ if (match) {
+ for (size_t i = 0; i < prefix_len; i++) {
+ if (cc->chars[i] != prefix_text[i]) {
+ match = false;
+ break;
+ }
+ }
+ }
+
+ if (match)
+ return cc;
+
+ (*key)++;
+ *key &= CELL_COMB_CHARS_HI - CELL_COMB_CHARS_LO;
+
+ /* TODO: this will loop infinitly if the composed table is full */
+ }
+
+ return NULL;
+}
+
void
composed_insert(struct composed **root, struct composed *node)
{
diff --git a/composed.h b/composed.h
index fcaf87d4..18afb146 100644
--- a/composed.h
+++ b/composed.h
@@ -10,12 +10,16 @@ struct composed {
uint32_t key;
uint8_t count;
uint8_t width;
+ uint8_t forced_width;
};
uint32_t composed_key_from_chars(const uint32_t chars[], size_t count);
uint32_t composed_key_from_key(uint32_t prev_key, uint32_t next_char);
-struct composed *composed_lookup(struct composed *root, uint32_t key);
+const struct composed *composed_lookup(struct composed *root, uint32_t key);
+const struct composed *composed_lookup_without_collision(
+ struct composed *root, uint32_t *key,
+ const char32_t *prefix, size_t prefix_len, char32_t wc, int forced_width);
void composed_insert(struct composed **root, struct composed *node);
void composed_free(struct composed *root);
diff --git a/vt.c b/vt.c
index 8f5d27d9..5447493a 100644
--- a/vt.c
+++ b/vt.c
@@ -793,60 +793,21 @@ action_utf8_print(struct terminal *term, char32_t wc)
xassert(wanted_count <= 255);
- size_t collision_count = 0;
-
- /* Look for existing combining chain */
- while (true) {
- if (unlikely(collision_count > 128)) {
- static bool have_warned = false;
- if (!have_warned) {
- have_warned = true;
- LOG_WARN("ignoring composed character: "
- "too many collisions in hash table");
- }
- return;
- }
-
- const struct composed *cc = composed_lookup(term->composed, key);
- if (cc == NULL)
- break;
-
- /*
- * We may have a key collisison, so need to check that
- * it's a true match. If not, bump the key and try
- * again.
- */
-
- xassert(key == cc->key);
- if (cc->chars[0] != base ||
- cc->count != wanted_count ||
- cc->chars[wanted_count - 1] != wc)
- {
-#if 0
- LOG_WARN("COLLISION: base: %04x/%04x, count: %d/%zu, last: %04x/%04x",
- cc->chars[0], base, cc->count, wanted_count, cc->chars[wanted_count - 1], wc);
-#endif
- key++;
- key &= CELL_COMB_CHARS_HI - CELL_COMB_CHARS_LO;
- collision_count++;
- continue;
- }
-
- bool match = composed != NULL
- ? memcmp(&cc->chars[1], &composed->chars[1],
- (wanted_count - 2) * sizeof(cc->chars[0])) == 0
- : true;
-
- if (!match) {
- key++;
- key &= CELL_COMB_CHARS_HI - CELL_COMB_CHARS_LO;
- collision_count++;
- continue;
- }
+ /* Check if we already have a match for the entire compose chain */
+ const struct composed *cc =
+ composed_lookup_without_collision(
+ term->composed, &key,
+ composed != NULL ? composed->chars : &(char32_t){base},
+ composed != NULL ? composed->count : 1,
+ wc, 0);
+ if (cc != NULL) {
+ /* We *do* have a match! */
wc = CELL_COMB_CHARS_LO + cc->key;
width = cc->width;
goto out;
+ } else {
+ /* No match - allocate a new chain below */
}
if (unlikely(term->composed_count >=
@@ -867,6 +828,7 @@ action_utf8_print(struct terminal *term, char32_t wc)
new_cc->count = wanted_count;
new_cc->chars[0] = base;
new_cc->chars[wanted_count - 1] = wc;
+ new_cc->forced_width = 0;
if (composed != NULL) {
memcpy(&new_cc->chars[1], &composed->chars[1],
@@ -923,7 +885,7 @@ action_utf8_print(struct terminal *term, char32_t wc)
term->composed_count++;
composed_insert(&term->composed, new_cc);
- wc = CELL_COMB_CHARS_LO + key;
+ wc = CELL_COMB_CHARS_LO + new_cc->key;
width = new_cc->width;
xassert(wc >= CELL_COMB_CHARS_LO);