+ assert(trie->entries.len == 0 && "Trie already compiled");
+
+ int len = m_strlen(key) + 1;
+ array_add(trie->keys_offset, trie->keys.len);
+ array_append(trie->keys, key, len);
+}
+
+
+static inline void trie_compile_aux(trie_t *trie, uint32_t id,
+ uint32_t first_key, uint32_t last_key,
+ int offset, int initial_diff)
+{
+ uint32_t forks[256];
+ uint32_t fork_pos = 0;
+ char current = '\0';
+
+ for (int off_diff = initial_diff ; fork_pos == 0 ; ++off_diff, ++offset) {
+ current = array_elt(trie->keys, array_elt(trie->keys_offset, first_key) + offset);
+ for (uint32_t i = first_key + 1 ; i < last_key ; ++i) {
+ const char *str = array_ptr(trie->keys, array_elt(trie->keys_offset, i));
+ const char c = str[offset];
+ if (c != current) {
+ array_ensure_capacity_delta(trie->entries, 2);
+ if (fork_pos == 0) {
+ trie_entry_split(trie, array_ptr(trie->entries, id), off_diff);
+ }
+ trie_entry_insert_child(trie, array_ptr(trie->entries, id),
+ trie_add_leaf(trie, str + offset));
+ forks[fork_pos++] = i;
+ current = c;
+ }
+ }
+ if (fork_pos == 0 && current == '\0') {
+ return;
+ }
+ }
+ forks[fork_pos] = last_key;
+
+ const uint8_t children_len = array_elt(trie->entries, id).children_len;
+ for (uint16_t i = 0 ; i < children_len ; ++i) {
+ int child = array_elt(trie->entries, id).children_offset + i;
+ if (forks[i] - 1 > first_key) {
+ trie_compile_aux(trie, child, first_key, forks[i], offset, 1);
+ }
+ first_key = forks[i];
+ }
+}
+
+void trie_compile(trie_t *trie, bool memlock)
+{
+ assert(trie->entries.len == 0 && "Trie already compiled");
+ assert(trie->keys.len != 0 && "Trying to compile an empty trie");
+ {
+# define QSORT_TYPE int
+# define QSORT_BASE trie->keys_offset.data
+# define QSORT_NELT trie->keys_offset.len
+# define QSORT_LT(a,b) strcmp(trie->keys.data + *a, trie->keys.data + *b) < 0
+# include "qsort.c"
+ }
+
+ array_ensure_capacity(trie->entries, trie->keys.len);
+ trie_compile_aux(trie, trie_add_leaf(trie, trie->keys.data),
+ 0, trie->keys_offset.len, 0, 0);
+ trie_cleanup_build_data(trie);
+ array_adjust(trie->entries);
+ array_adjust(trie->c);
+ if (memlock) {
+ trie_lock(trie);
+ }
+}
+
+bool trie_lookup(const trie_t *trie, const char *key)
+{
+ assert(trie->keys.len == 0L && "Can't lookup: trie not compiled");
+ if (trie->entries.len == 0) {
+ return false;