aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--driver-ti.c74
1 files changed, 59 insertions, 15 deletions
diff --git a/driver-ti.c b/driver-ti.c
index 7043c8d..2470717 100644
--- a/driver-ti.c
+++ b/driver-ti.c
@@ -10,7 +10,9 @@
#include <unistd.h>
/* 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
+ * in a trie. This avoids a slow linear search through a flat list of
+ * sequences. Because it is likely most nodes will be very sparse, we optimise
+ * vector to store an extent map after the database is loaded.
*/
typedef enum {
@@ -29,7 +31,8 @@ struct trie_node_key {
struct trie_node_arr {
trie_nodetype type;
- struct trie_node *arr[256];
+ unsigned char min, max; /* INCLUSIVE endpoints of the extent range */
+ struct trie_node *arr[0];
};
typedef struct {
@@ -57,17 +60,18 @@ static struct trie_node *new_node_key(termkey_type type, termkey_keysym sym, int
return (struct trie_node*)n;
}
-static struct trie_node *new_node_arr(void)
+static struct trie_node *new_node_arr(unsigned char min, unsigned char max)
{
- struct trie_node_arr *n = malloc(sizeof(struct trie_node_arr));
+ struct trie_node_arr *n = malloc(sizeof(struct trie_node_arr) + ((int)max-min+1) * sizeof(void*));
if(!n)
return NULL;
n->type = TYPE_ARR;
+ n->min = min; n->max = max;
- unsigned char b;
- for(b = 0; b < 255; b++)
- n->arr[b] = NULL;
+ int i;
+ for(i = min; i <= max; i++)
+ n->arr[i-min] = NULL;
return (struct trie_node*)n;
}
@@ -81,7 +85,9 @@ static struct trie_node *lookup_next(struct trie_node *n, unsigned char b)
case TYPE_ARR:
{
struct trie_node_arr *nar = (struct trie_node_arr*)n;
- return nar->arr[b];
+ if(b < nar->min || b > nar->max)
+ return NULL;
+ return nar->arr[b - nar->min];
}
}
@@ -96,10 +102,10 @@ static void free_trie(struct trie_node *n)
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]);
+ int i;
+ for(i = nar->min; i <= nar->max; i++)
+ if(nar->arr[i - nar->min])
+ free_trie(nar->arr[i - nar->min]);
break;
}
}
@@ -107,6 +113,37 @@ static void free_trie(struct trie_node *n)
free(n);
}
+static struct trie_node *compress_trie(struct trie_node *n)
+{
+ if(!n)
+ return NULL;
+
+ switch(n->type) {
+ case TYPE_KEY:
+ return n;
+ case TYPE_ARR:
+ {
+ struct trie_node_arr *nar = (struct trie_node_arr*)n;
+ unsigned char min, max;
+ // Find the real bounds
+ for(min = 0; !nar->arr[min]; min++)
+ ;
+ for(max = 0xff; !nar->arr[max]; max--)
+ ;
+
+ struct trie_node_arr *new = (struct trie_node_arr*)new_node_arr(min, max);
+ int i;
+ for(i = min; i <= max; i++)
+ new->arr[i - min] = compress_trie(nar->arr[i]);
+
+ free(nar);
+ return (struct trie_node*)new;
+ }
+ }
+
+ return n;
+}
+
static void *new_driver(termkey_t *tk, const char *term)
{
int err;
@@ -120,7 +157,7 @@ static void *new_driver(termkey_t *tk, const char *term)
ti->tk = tk;
- ti->root = new_node_arr();
+ ti->root = new_node_arr(0, 0xff);
if(!ti->root)
goto abort_free_ti;
@@ -148,6 +185,8 @@ static void *new_driver(termkey_t *tk, const char *term)
goto abort_free_trie;
}
+ ti->root = compress_trie(ti->root);
+
return ti;
abort_free_trie:
@@ -341,7 +380,7 @@ static int register_seq(termkey_ti *ti, const char *seq, termkey_type type, term
struct trie_node *next;
if(seq[pos+1])
// Intermediate node
- next = new_node_arr();
+ next = new_node_arr(0, 0xff);
else
// Final key node
next = new_node_key(type, sym, modmask, modset);
@@ -353,7 +392,12 @@ static int register_seq(termkey_ti *ti, const char *seq, termkey_type type, term
case TYPE_ARR:
{
struct trie_node_arr *nar = (struct trie_node_arr*)p;
- nar->arr[b] = next;
+ if(b < nar->min || b > nar->max) {
+ fprintf(stderr, "ASSERT FAIL: Trie insert at 0x%02x is outside of extent bounds (0x%02x..0x%02x)\n",
+ b, nar->min, nar->max);
+ abort();
+ }
+ nar->arr[b - nar->min] = next;
p = next;
break;
}