1 files changed, 184 insertions, 89 deletions

diff --git a/src/analyse.c b/src/analyse.c
index 416b10a..e5d1cb9 100644
--- a/src/analyse.c
+++ b/src/analyse.c
@@ -1,149 +1,244 @@
-#include "err.h"
 #include "analyse.h"
 
+#include "err.h"
+
 #include <assert.h>
 #include <string.h>
 
-struct analyse_result_s analyse(struct parse_result_s pr)
+static void sub_trie_insert(struct analyse_trie_s *t,
+	const char *s, char *sv)
+{
+	const char *si = s;
+	struct analyse_trie_s *parent = NULL;
+	unsigned i;
+
+	/* walk down the trie, creating nodes when necessary */
+	for (; *si != '\0'; si++) {
+		for (i = 0; i < t->branch_count && *si != t->branch_chars[i]; i++);
+		if (t->branch_count == 0
+			|| i == t->branch_count
+		) {
+			t->branch_count++;
+			t->branch_chars[t->branch_count - 1] = *si;
+			TRYALLOC(t->branches[t->branch_count - 1], 1);
+			parent = t;
+			t = t->branches[t->branch_count - 1];
+			t->parent = parent;
+			t->branch_count = 0;
+			t->sval = NULL;
+		} else {
+			t = t->branches[i];
+		}
+	}
+
+	TRYALLOC(t->sval, strlen(sv) + 1);
+	strcpy(t->sval, sv);
+}
+
+/* tries used to generate static jump-based token matching */
+static inline void sub_build_tries(struct parse_result_s *pr,
+	struct analyse_result_s *ar)
 {
-	struct analyse_result_s ar = {
-		.uses_hash = false,
-		.uses_array = false,
-	};
 	struct parse_deftype_s *dcur, *dtmp;
 	struct parse_var_s *vcur, *vtmp;
-	struct analyse_tree_s *cur;
-	unsigned i;
+	unsigned i, j;
+	/* dtype sval == TOK_MAX_LEN
+	 * dtype member == TOK_MAX_LEN
+	 * suffix == TOK_MAX_LEN
+	 * 32 == padding for "CONFCONF_TYPE_" + "_" + "_" + "\0" */
+	char sbuf[TOK_MAX_LEN * 3 + 32];
+
+	/* variable trie */
+	ar->var_trie.branch_count = 0;
+	ar->var_trie.sval = NULL;
+	ar->var_trie.parent = NULL;
+
+	if (pr->vars != NULL) {
+		HASH_ITER(hh, pr->vars, vcur, vtmp) {
+			sprintf(sbuf, "%s", vcur->name);
+			sub_trie_insert(&(ar->var_trie), vcur->name, sbuf);
+		}
+	}
+
+	ar->deftype_mem_tries = NULL;
 
+	if (pr->deftypes != NULL) {
+		TRYALLOC(
+			ar->deftype_mem_tries,
+			HASH_COUNT(pr->deftypes)
+		);
 
-	/***************
-	 * BUILD TREES *
-	 ***************/
+		ar->deftype_mem_trie_count = HASH_COUNT(pr->deftypes);
 
-	ar.deftype_tree.branch_count = 0;
-	ar.deftype_tree.is_terminal = false;
+		i = 0;
+		HASH_ITER(hh, pr->deftypes, dcur, dtmp) {
+			ar->deftype_mem_tries[i].branch_count = 0;
+			ar->deftype_mem_tries[i].sval = NULL;
+			ar->deftype_mem_tries[i].parent = NULL;
 
-	if (pr.deftypes != NULL) {
-		HASH_ITER(hh, pr.deftypes, dcur, dtmp) {
-			if (!dcur->is_used)
+			if (!dcur->is_used) {
+				i++;
 				continue;
+			}
+
+			/* union types */
+			if (dcur->type == PARSE_DEFTYPE_UNION) {
+				for (j = 0; j < dcur->member_list_len; j++) {
+					sprintf(sbuf, "%u", j);
 
-			cur = &(ar.deftype_tree);
-
-			/* walk down the tree, creating nodes when necessary */
-			for (i = 0; dcur->name[i] != '\0'; i++) {
-				if (cur->branch_count == 0
-						|| cur->branch_chars[cur->branch_count - 1]
-						!= dcur->name[i]
-				) {
-					cur->branch_count++;
-					cur->branch_chars[cur->branch_count - 1] = dcur->name[i];
-					TRYALLOC(cur->branches[cur->branch_count - 1], 1);
-					cur = cur->branches[cur->branch_count - 1];
-					cur->branch_count = 0;
-					cur->is_terminal = false;
-				} else {
-					cur = cur->branches[cur->branch_count - 1];
+					sub_trie_insert(
+						&(ar->deftype_mem_tries[i]),
+						dcur->member_name_list[j],
+						sbuf
+					);
 				}
 			}
 
-			cur->is_terminal = true;
-			strcpy(cur->name, dcur->name);
-		}
-	}
-
-	ar.var_tree.branch_count = 0;
-	ar.var_tree.is_terminal = false;
-
-	if (pr.vars != NULL) {
-		HASH_ITER(hh, pr.vars, vcur, vtmp) {
-			cur = &(ar.var_tree);
-
-			/* walk down the tree, creating nodes when necessary */
-			for (i = 0; vcur->name[i] != '\0'; i++) {
-				if (cur->branch_count == 0
-						|| cur->branch_chars[cur->branch_count - 1]
-						!= vcur->name[i]
-				) {
-					cur->branch_count++;
-					cur->branch_chars[cur->branch_count - 1] = vcur->name[i];
-					TRYALLOC(cur->branches[cur->branch_count - 1], 1);
-					cur = cur->branches[cur->branch_count - 1];
-					cur->branch_count = 0;
-					cur->is_terminal = false;
-				} else {
-					cur = cur->branches[cur->branch_count - 1];
+			/* enum mems */
+			if (dcur->type == PARSE_DEFTYPE_ENUM) {
+				for (j = 0; j < dcur->member_list_len; j++) {
+					sprintf(sbuf,
+						"CONFCONF_TYPE_%s_%s_%s",
+						dcur->name,
+						dcur->member_name_list[j],
+						pr->suffix
+					);
+					sub_trie_insert(
+						&(ar->deftype_mem_tries[i]),
+						dcur->member_name_list[j],
+						sbuf
+					);
 				}
 			}
 
-			cur->is_terminal = true;
-			strcpy(cur->name, vcur->name);
+			i++;
 		}
 	}
+}
 
-
-	/************************
-	 * CALCULATE USED TYPES *
-	 ************************/
+static inline void sub_calculate_used_types(struct parse_result_s *pr,
+	struct analyse_result_s *ar)
+{
+	struct parse_deftype_s *dcur, *dtmp;
+	struct parse_var_s *vcur, *vtmp;
+	unsigned i;
 
 	for (i = PARSE_TYPE_BOOL; i < PARSE_TYPE_HASH_DEFTYPE; i++)
-		ar.uses_type[i] = false;
+		ar->uses_type[i] = false;
 
-	HASH_ITER(hh, pr.deftypes, dcur, dtmp) {
+	HASH_ITER(hh, pr->deftypes, dcur, dtmp) {
 		if (!dcur->is_used)
 			continue;
 
+		if (dcur->type == PARSE_DEFTYPE_ENUM)
+			continue;
+
 		for (i = 0; i < dcur->member_list_len; i++) {
 			if (dcur->member_type_list[i] >= PARSE_TYPE_HASH_BOOL) {
-				ar.uses_hash = true;
-				ar.uses_type[dcur->member_type_list[i]
+				ar->uses_hash = true;
+				ar->uses_type[dcur->member_type_list[i]
 					- PARSE_TYPE_HASH_BOOL] = true;
 			} else if (dcur->member_type_list[i] >= PARSE_TYPE_ARRAY_BOOL) {
-				ar.uses_array = true;
-				ar.uses_type[dcur->member_type_list[i]
+				ar->uses_array = true;
+				ar->uses_type[dcur->member_type_list[i]
 					- PARSE_TYPE_ARRAY_BOOL] = true;
 			}
 
-			ar.uses_type[dcur->member_type_list[i]] = true;
+			ar->uses_type[dcur->member_type_list[i]] = true;
 		}
 	}
 
-	HASH_ITER(hh, pr.vars, vcur, vtmp) {
+	HASH_ITER(hh, pr->vars, vcur, vtmp) {
 		if (vcur->type >= PARSE_TYPE_HASH_BOOL) {
-			ar.uses_hash = true;
-			ar.uses_type[vcur->type - PARSE_TYPE_HASH_BOOL] = true;
+			ar->uses_hash = true;
+			ar->uses_type[vcur->type - PARSE_TYPE_HASH_BOOL] = true;
 		} else if (vcur->type >= PARSE_TYPE_ARRAY_BOOL) {
-			ar.uses_array = true;
-			ar.uses_type[vcur->type - PARSE_TYPE_ARRAY_BOOL] = true;
+			ar->uses_array = true;
+			ar->uses_type[vcur->type - PARSE_TYPE_ARRAY_BOOL] = true;
 		}
 
 		if (vcur->type == PARSE_TYPE_DEFTYPE
-				|| vcur->type == PARSE_TYPE_ARRAY_DEFTYPE 
-				|| vcur->type == PARSE_TYPE_HASH_DEFTYPE
+			|| vcur->type == PARSE_TYPE_ARRAY_DEFTYPE
+			|| vcur->type == PARSE_TYPE_HASH_DEFTYPE
 		) {
 			continue;
 		}
 
-		ar.uses_type[vcur->type] = true;
+		ar->uses_type[vcur->type] = true;
 	}
+}
+
+struct analyse_result_s* analyse(struct parse_result_s *pr)
+{
+	struct analyse_result_s *ar;
+
+	assert(pr != NULL);
+
+	TRYALLOC(ar, 1);
+	ar->uses_hash = false;
+	ar->uses_array = false;
+
+	sub_build_tries(pr, ar);
+
+	sub_calculate_used_types(pr, ar);
 
 	return ar;
 }
 
-static void sub_recurse_free(struct analyse_tree_s *t)
+static void sub_wipe_trie(struct analyse_trie_s *t)
 {
-	unsigned i;
+	struct analyse_trie_s *cur = t, *prev = NULL;
 
-	for (i = 0; i < t->branch_count; i++) {
-		sub_recurse_free(t->branches[i]);
-		free(t->branches[i]);
-	}
+	assert(t != NULL);
+
+	t->parent = NULL;
+	t->idx = 0;
+
+	/* do nothing for an empty trie */
+	if (t->branch_count == 0)
+		return;
+
+	do {
+		/* drop into a branch to its tail */
+		if (cur->idx != cur->branch_count) {
+			prev = cur;
+			cur = cur->branches[cur->idx];
+			cur->idx = 0;
+			prev->idx++;
+			continue;
+		}
+
+		/* break at the head node */
+		if (cur->parent == NULL)
+			break;
+
+		/* at a tail. jump up to its parent */
+		prev = cur;
+		cur = cur->parent;
+
+		/* prev guaranteed to have no more children here */
+		if (prev->sval != NULL)
+			free(prev->sval);
+
+		free(prev);
+	} while (true);
 }
 
-void analyse_result_wipe(struct analyse_result_s *r)
+void analyse_result_free(struct analyse_result_s *ar)
 {
-	assert(r != NULL);
+	unsigned i;
+
+	assert(ar != NULL);
+
+	sub_wipe_trie(&(ar->var_trie));
+
+	if (ar->deftype_mem_tries != NULL) {
+		for (i = 0; i < ar->deftype_mem_trie_count; i++) {
+			sub_wipe_trie(&(ar->deftype_mem_tries[i]));
+		}
+
+		free(ar->deftype_mem_tries);
+	}
 
-	sub_recurse_free(&(r->deftype_tree));
-	sub_recurse_free(&(r->var_tree));
+	free(ar);
 }