aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--driver-ti.c199
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;
}