From 06cb82a8ccc3587dff728321dff5416b18090483 Mon Sep 17 00:00:00 2001 From: katherine Date: Wed, 10 Jul 2019 20:24:08 -0700 Subject: implement deftype get --- src/analyse.c | 273 +++++++++++++++++++++++++++++++++++++++------------------- 1 file changed, 184 insertions(+), 89 deletions(-) (limited to 'src/analyse.c') 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 #include -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); } -- cgit v1.2.3