compose: use a ternary tree instead of a regular trie

Previously we used a simple trie with a linked list for each chain.
Unfortunately most compose files have very long chains which means the
constructions performs an almost quadratic number of comparisons.

Switch to using a ternary search tree instead. This is very similar to a
trie, only the linked list is essentially replaced with a binary tree.

On the en_US/Compose file, the perf diff is the following (the modified
function is `parse`):

  Event 'cycles:u'

  Baseline  Delta Abs  Shared Object     Symbol
  ........  .........  ................  .................................

    39.91%    -17.62%  bench-compose     [.] parse.constprop.0
    20.54%     +6.47%  bench-compose     [.] lex
    17.28%     +5.55%  libc-2.33.so      [.] __strcmp_avx2
    12.78%     +4.01%  bench-compose     [.] xkb_keysym_from_name
     2.30%     +0.83%  libc-2.33.so      [.] __GI_____strtoull_l_internal
     3.36%     +0.78%  bench-compose     [.] strcmp@plt

Thanks to some careful packing, the memory usage is pretty much the
same.

Signed-off-by: Ran Benita <ran@unusedvar.com>

1 files changed, 10 insertions, 7 deletions

diff --git a/src/compose/state.c b/src/compose/state.c
index de08a90..6ba0344 100644
--- a/src/compose/state.c
+++ b/src/compose/state.c
@@ -109,17 +109,20 @@ xkb_compose_state_feed(struct xkb_compose_state *state, xkb_keysym_t keysym)
 
     node = &darray_item(state->table->nodes, state->context);
 
-    context = (node->is_leaf ? 0 : node->internal.successor);
-    node = &darray_item(state->table->nodes, context);
+    context = (node->is_leaf ? 1 : node->internal.eqkid);
+    if (context == 1 && darray_size(state->table->nodes) == 1)
+        context = 0;
 
-    while (node->keysym != keysym && node->next != 0) {
-        context = node->next;
+    while (context != 0) {
         node = &darray_item(state->table->nodes, context);
+        if (keysym < node->keysym)
+            context = node->lokid;
+        else if (keysym > node->keysym)
+            context = node->hikid;
+        else
+            break;
     }
 
-    if (node->keysym != keysym)
-        context = 0;
-
     state->prev_context = state->context;
     state->context = context;
     return XKB_COMPOSE_FEED_ACCEPTED;