Use a trie instead of a linear list of sequence strings in the terminfo driver - nicer lookup properties

1 files changed, 151 insertions, 48 deletions

diff --git a/driver-ti.c b/driver-ti.c
index f65f474..7043c8d 100644
--- a/driver-ti.c
+++ b/driver-ti.c
@@ -9,23 +9,104 @@
 #include <string.h>
 #include <unistd.h>
 
-struct ti_keyinfo {
-  const char *seq;
-  size_t seqlen; // cached strlen of seq since we'll use it lots
+/* To be efficient at lookups, we store the byte sequence => keyinfo mapping
+ * in a trie. This avoids a slow linear search though a flat list of sequences
+ */
+
+typedef enum {
+  TYPE_KEY,
+  TYPE_ARR
+} trie_nodetype;
+
+struct trie_node {
+  trie_nodetype type;
+};
+
+struct trie_node_key {
+  trie_nodetype type;
   struct keyinfo key;
 };
 
+struct trie_node_arr {
+  trie_nodetype type;
+  struct trie_node *arr[256];
+};
+
 typedef struct {
   termkey_t *tk;
 
-  int nseqs;
-  int alloced_seqs;
-  struct ti_keyinfo *seqs;
+  struct trie_node *root;
 } termkey_ti;
 
 static int funcname2keysym(const char *funcname, termkey_type *typep, termkey_keysym *symp, int *modmask, int *modsetp);
 static int register_seq(termkey_ti *ti, const char *seq, termkey_type type, termkey_keysym sym, int modmask, int modset);
 
+static struct trie_node *new_node_key(termkey_type type, termkey_keysym sym, int modmask, int modset)
+{
+  struct trie_node_key *n = malloc(sizeof(struct trie_node_key));
+  if(!n)
+    return NULL;
+
+  n->type = TYPE_KEY;
+
+  n->key.type = type;
+  n->key.sym  = sym;
+  n->key.modifier_mask = modmask;
+  n->key.modifier_set  = modset;
+
+  return (struct trie_node*)n;
+}
+
+static struct trie_node *new_node_arr(void)
+{
+  struct trie_node_arr *n = malloc(sizeof(struct trie_node_arr));
+  if(!n)
+    return NULL;
+
+  n->type = TYPE_ARR;
+
+  unsigned char b;
+  for(b = 0; b < 255; b++)
+    n->arr[b] = NULL;
+
+  return (struct trie_node*)n;
+}
+
+static struct trie_node *lookup_next(struct trie_node *n, unsigned char b)
+{
+  switch(n->type) {
+  case TYPE_KEY:
+    fprintf(stderr, "ABORT: lookup_next within a TYPE_KEY node\n");
+    abort();
+  case TYPE_ARR:
+    {
+      struct trie_node_arr *nar = (struct trie_node_arr*)n;
+      return nar->arr[b];
+    }
+  }
+
+  return NULL; // Never reached but keeps compiler happy
+}
+
+static void free_trie(struct trie_node *n)
+{
+  switch(n->type) {
+  case TYPE_KEY:
+    break;
+  case TYPE_ARR:
+    {
+      struct trie_node_arr *nar = (struct trie_node_arr*)n;
+      unsigned char b;
+      for(b = 0; b < 255; b++)
+        if(nar->arr[b])
+          free_trie(nar->arr[b]);
+      break;
+    }
+  }
+
+  free(n);
+}
+
 static void *new_driver(termkey_t *tk, const char *term)
 {
   int err;
@@ -39,11 +120,8 @@ static void *new_driver(termkey_t *tk, const char *term)
 
   ti->tk = tk;
 
-  ti->alloced_seqs = 32; // We'll allocate more space if we need
-  ti->nseqs = 0;
-
-  ti->seqs = malloc(ti->alloced_seqs * sizeof(ti->seqs[0]));
-  if(!ti->seqs)
+  ti->root = new_node_arr();
+  if(!ti->root)
     goto abort_free_ti;
 
   int i;
@@ -67,13 +145,13 @@ static void *new_driver(termkey_t *tk, const char *term)
 
     if(sym != TERMKEY_SYM_NONE)
       if(!register_seq(ti, value, type, sym, mask, set))
-        goto abort_free_seqs;
+        goto abort_free_trie;
   }
 
   return ti;
 
-abort_free_seqs:
-  free(ti->seqs);
+abort_free_trie:
+  free_trie(ti->root);
 
 abort_free_ti:
   free(ti);
@@ -104,7 +182,7 @@ static void free_driver(void *info)
 {
   termkey_ti *ti = info;
 
-  free(ti->seqs);
+  free_trie(ti->root);
 
   free(ti);
 }
@@ -118,32 +196,31 @@ static termkey_result getkey(termkey_t *tk, void *info, termkey_key *key, int fo
   if(tk->buffcount == 0)
     return tk->is_closed ? TERMKEY_RES_EOF : TERMKEY_RES_NONE;
 
-  // Now we're sure at least 1 byte is valid
-  unsigned char b0 = CHARAT(0);
+  struct trie_node *p = ti->root;
 
-  int i;
-  for(i = 0; i < ti->nseqs; i++) {
-    struct ti_keyinfo *s = &(ti->seqs[i]);
+  int pos = 0;
+  while(pos < tk->buffcount) {
+    p = lookup_next(p, CHARAT(pos));
+    if(!p)
+      break;
 
-    if(s->seq[0] != b0)
-      continue;
+    pos++;
 
-    if(tk->buffcount >= s->seqlen) {
-      if(strncmp(s->seq, (const char*)tk->buffer + tk->buffstart, s->seqlen) == 0) {
-        key->type      = s->key.type;
-        key->code.sym  = s->key.sym;
-        key->modifiers = s->key.modifier_set;
-        (*tk->method.eat_bytes)(tk, s->seqlen);
-        return TERMKEY_RES_KEY;
-      }
-    }
-    else if(!force) {
-      // Maybe we'd get a partial match
-      if(strncmp(s->seq, (const char*)tk->buffer + tk->buffstart, tk->buffcount) == 0)
-        return TERMKEY_RES_AGAIN;
+    if(p->type == TYPE_KEY) {
+      struct trie_node_key *nk = (struct trie_node_key*)p;
+      key->type      = nk->key.type;
+      key->code.sym  = nk->key.sym;
+      key->modifiers = nk->key.modifier_set;
+      (*tk->method.eat_bytes)(tk, pos);
+      return TERMKEY_RES_KEY;
     }
   }
 
+  // If p is not NULL then we hadn't walked off the end yet, so we have a
+  // partial match
+  if(p && !force)
+    return TERMKEY_RES_AGAIN;
+
   return TERMKEY_RES_NONE;
 }
 
@@ -246,21 +323,47 @@ static int funcname2keysym(const char *funcname, termkey_type *typep, termkey_ke
 
 static int register_seq(termkey_ti *ti, const char *seq, termkey_type type, termkey_keysym sym, int modmask, int modset)
 {
-  if(ti->nseqs == ti->alloced_seqs) {
-    ti->alloced_seqs *= 2;
-    void *newseqs = realloc(ti->seqs, ti->alloced_seqs * sizeof(ti->seqs[9]));
-    if(!newseqs)
-      return 0;
-    ti->seqs = newseqs;
+  int pos = 0;
+  struct trie_node *p = ti->root;
+
+  // Unsigned because we'll be using it as an array subscript
+  unsigned char b;
+
+  while((b = seq[pos])) {
+    struct trie_node *next = lookup_next(p, b);
+    if(!next)
+      break;
+    p = next;
+    pos++;
   }
 
-  int i = ti->nseqs++;
-  ti->seqs[i].seq = seq;
-  ti->seqs[i].seqlen = strlen(seq);
-  ti->seqs[i].key.type = type;
-  ti->seqs[i].key.sym = sym;
-  ti->seqs[i].key.modifier_mask = modmask;
-  ti->seqs[i].key.modifier_set  = modset;
+  while((b = seq[pos])) {
+    struct trie_node *next;
+    if(seq[pos+1])
+      // Intermediate node
+      next = new_node_arr();
+    else
+      // Final key node
+      next = new_node_key(type, sym, modmask, modset);
+
+    if(!next)
+      return 0;
+
+    switch(p->type) {
+    case TYPE_ARR:
+      {
+        struct trie_node_arr *nar = (struct trie_node_arr*)p;
+        nar->arr[b] = next;
+        p = next;
+        break;
+      }
+    case TYPE_KEY:
+      fprintf(stderr, "ASSERT FAIL: Tried to insert child node in TYPE_KEY\n");
+      abort();
+    }
+
+    pos++;
+  }
 
   return 1;
 }