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, 43 insertions, 27 deletions

diff --git a/src/compose/table.h b/src/compose/table.h
index 467ccf7..6be4348 100644
--- a/src/compose/table.h
+++ b/src/compose/table.h
@@ -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"),
@@ -29,36 +29,43 @@
 #include "context.h"
 
 /*
- * The compose table data structure is a simple trie.  An example will
- * help.  Given these sequences:
+ * The compose table data structure is a ternary search tree.
  *
- *      <A> <B>        : "first"  dead_a
- *      <A> <C> <D>    : "second" dead_b
- *      <E> <F>        : "third"  dead_c
+ * Reference: https://www.drdobbs.com/database/ternary-search-trees/184410528
+ * Visualization: https://www.cs.usfca.edu/~galles/visualization/TST.html
  *
- * the trie would look like:
+ * Short example. Given these sequences:
+ *
+ *      <B> <C>        : "first"  dead_a
+ *      <B> <D> <E>    : "second" dead_b
+ *      <A> <F>        : "third"  dead_c
+ *
+ * the tree would look like:
+ *
+ *          -------- [<B>]---------
+ *          |          |          #
+ *          v          V
+ *     -- [<A>] --   [<C>] --------
+ *     #    |    #     |          |
+ *          v          #     -- [<D>] --
+ *     -- [<F>] --           #    |    #
+ *     #    |    #                v
+ *          #                -- [<E>] --
+ *                           #    |    #
+ *                                #
  *
- * [root] ---> [<A>] -----------------> [<E>] -#
- *   |           |                        |
- *   #           v                        v
- *             [<B>] ---> [<C>] -#      [<F>] -#
- *               |          |             -
- *               #          v             #
- *                        [<D>] -#
- *                          |
- *                          #
  * where:
- * - [root] is a special empty root node.
  * - [<X>] is a node for a sequence keysym <X>.
- * - right arrows are `next` pointers.
- * - down arrows are `successor` pointers.
+ * - right arrows are `hikid` pointers.
+ * - left arrows are `lokid` pointers.
+ * - down arrows are `eqkid` pointers.
  * - # is a nil pointer.
  *
  * The nodes are all kept in a contiguous array.  Pointers are represented
  * as integer offsets into this array.  A nil pointer is represented as 0
- * (which, helpfully, is the offset of the empty root node).
+ * (which, helpfully, is the offset of an empty dummy node).
  *
- * Nodes without a successor are leaf nodes.  Since a sequence cannot be a
+ * Nodes without an eqkid are leaf nodes.  Since a sequence cannot be a
  * prefix of another, these are exactly the nodes which terminate the
  * sequences (in a bijective manner).
  *
@@ -73,18 +80,27 @@
 
 struct compose_node {
     xkb_keysym_t keysym;
-    /* Offset into xkb_compose_table::nodes. */
-    uint16_t next;
-    bool is_leaf;
+
+    /* Offset into xkb_compose_table::nodes or 0. */
+    uint16_t lokid;
+    /* Offset into xkb_compose_table::nodes or 0. */
+    uint16_t hikid;
 
     union {
         struct {
-            /* Offset into xkb_compose_table::nodes. */
-            uint16_t successor;
+            uint32_t _pad:31;
+            bool is_leaf:1;
+        };
+        struct {
+            uint32_t _pad:31;
+            bool is_leaf:1;
+            /* Offset into xkb_compose_table::nodes or 0. */
+            uint16_t eqkid;
         } internal;
         struct {
             /* Offset into xkb_compose_table::utf8. */
-            uint32_t utf8;
+            uint32_t utf8:31;
+            bool is_leaf:1;
             xkb_keysym_t keysym;
         } leaf;
     };