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, 7 insertions, 8 deletions

diff --git a/src/compose/table.c b/src/compose/table.c
index dbd255e..1691555 100644
--- a/src/compose/table.c
+++ b/src/compose/table.c
@@ -1,5 +1,5 @@
 /*
- * Copyright © 2013 Ran Benita <ran234@gmail.com>
+ * Copyright © 2013,2021 Ran Benita <ran234@gmail.com>
  *
  * Permission is hereby granted, free of charge, to any person obtaining a
  * copy of this software and associated documentation files (the "Software"),
@@ -36,7 +36,7 @@ xkb_compose_table_new(struct xkb_context *ctx,
 {
     char *resolved_locale;
     struct xkb_compose_table *table;
-    struct compose_node root;
+    struct compose_node dummy;
 
     resolved_locale = resolve_locale(locale);
     if (!resolved_locale)
@@ -58,12 +58,11 @@ xkb_compose_table_new(struct xkb_context *ctx,
     darray_init(table->nodes);
     darray_init(table->utf8);
 
-    root.keysym = XKB_KEY_NoSymbol;
-    root.next = 0;
-    root.is_leaf = true;
-    root.leaf.utf8 = 0;
-    root.leaf.keysym = XKB_KEY_NoSymbol;
-    darray_append(table->nodes, root);
+    dummy.keysym = XKB_KEY_NoSymbol;
+    dummy.leaf.is_leaf = true;
+    dummy.leaf.utf8 = 0;
+    dummy.leaf.keysym = XKB_KEY_NoSymbol;
+    darray_append(table->nodes, dummy);
 
     darray_append(table->utf8, '\0');