summaryrefslogtreecommitdiff
path: root/filter
diff options
context:
space:
mode:
authorMaria Matejka <mq@ucw.cz>2023-01-23 19:46:26 +0100
committerMaria Matejka <mq@ucw.cz>2023-01-23 19:46:26 +0100
commit758aabd96c0f09709183dff4261ffbfdd72ae870 (patch)
tree75d17bb906331213d5107a6be6446f58f0251541 /filter
parent4821612c94f9e935a6e841f6bcace9465dd2ad78 (diff)
parent7fb23041a52d01754c53ba963e2282e524813364 (diff)
Merge commit '7fb23041a52d01754c53ba963e2282e524813364' into thread-next
Diffstat (limited to 'filter')
-rw-r--r--filter/config.Y7
-rw-r--r--filter/data.h1
-rw-r--r--filter/f-inst.c25
-rw-r--r--filter/tree.c20
4 files changed, 46 insertions, 7 deletions
diff --git a/filter/config.Y b/filter/config.Y
index 7f152659..e6264a83 100644
--- a/filter/config.Y
+++ b/filter/config.Y
@@ -701,16 +701,15 @@ switch_body: /* EMPTY */ { $$ = NULL; }
| switch_body switch_items ':' cmds_scoped {
/* Fill data fields */
struct f_tree *t;
- struct f_line *line = f_linearize($4, 0);
for (t = $2; t; t = t->left)
- t->data = line;
+ t->data = $4;
$$ = f_merge_items($1, $2);
}
| switch_body ELSECOL cmds_scoped {
struct f_tree *t = f_new_tree();
t->from.type = t->to.type = T_VOID;
t->right = t;
- t->data = f_linearize($3, 0);
+ t->data = $3;
$$ = f_merge_items($1, t);
}
;
@@ -994,7 +993,7 @@ cmd:
}
| function_call ';' { $$ = f_new_inst(FI_DROP_RESULT, $1); }
| CASE term '{' switch_body '}' {
- $$ = f_new_inst(FI_SWITCH, $2, build_tree($4));
+ $$ = f_new_inst(FI_SWITCH, $2, $4);
}
| symbol_known '.' EMPTY ';' { $$ = f_generate_empty($1); }
diff --git a/filter/data.h b/filter/data.h
index 6aa34d44..b5db4aec 100644
--- a/filter/data.h
+++ b/filter/data.h
@@ -125,6 +125,7 @@ struct f_trie_walk_state
struct f_tree *f_new_tree(void);
struct f_tree *build_tree(struct f_tree *);
const struct f_tree *find_tree(const struct f_tree *t, const struct f_val *val);
+const struct f_tree *find_tree_linear(const struct f_tree *t, const struct f_val *val);
int same_tree(const struct f_tree *t0, const struct f_tree *t2);
int tree_node_count(const struct f_tree *t);
void tree_format(const struct f_tree *t, buffer *buf);
diff --git a/filter/f-inst.c b/filter/f-inst.c
index 801eceec..caffc2b8 100644
--- a/filter/f-inst.c
+++ b/filter/f-inst.c
@@ -1265,14 +1265,33 @@
FID_MEMBER(struct f_tree *, tree, [[!same_tree(f1->tree, f2->tree)]], "tree %p", item->tree);
+ FID_LINEARIZE_BODY()
+ /* Linearize all branches in switch */
+ struct f_inst *last_inst = NULL;
+ struct f_line *last_line = NULL;
+ for (struct f_tree *t = whati->tree; t; t = t->left)
+ {
+ if (t->data != last_inst)
+ {
+ last_inst = t->data;
+ last_line = f_linearize(t->data, 0);
+ }
+
+ t->data = last_line;
+ }
+
+ /* Balance the tree */
+ item->tree = build_tree(whati->tree);
+
FID_ITERATE_BODY()
- tree_walk(whati->tree, f_add_tree_lines, fit);
+ tree_walk(whati->tree, f_add_tree_lines, fit);
FID_INTERPRET_BODY()
- const struct f_tree *t = find_tree(tree, &v1);
+ /* In parse-time use find_tree_linear(), in runtime use find_tree() */
+ const struct f_tree *t = FID_HIC(,find_tree,find_tree_linear)(tree, &v1);
if (!t) {
v1.type = T_VOID;
- t = find_tree(tree, &v1);
+ t = FID_HIC(,find_tree,find_tree_linear)(tree, &v1);
if (!t) {
debug( "No else statement?\n");
FID_HIC(,break,return NULL);
diff --git a/filter/tree.c b/filter/tree.c
index 97bf7dae..25cf93e4 100644
--- a/filter/tree.c
+++ b/filter/tree.c
@@ -38,6 +38,26 @@ find_tree(const struct f_tree *t, const struct f_val *val)
return find_tree(t->left, val);
}
+/**
+ * find_tree_linear
+ * @t: tree to search in
+ * @val: value to find
+ *
+ * Search for given value in the degenerated linear tree, which is generated by
+ * parser before build_tree() is applied. The tree is not sorted and all nodes
+ * are linked by left ptr.
+ */
+const struct f_tree *
+find_tree_linear(const struct f_tree *t, const struct f_val *val)
+{
+ for (; t; t = t->left)
+ if ((val_compare(&(t->from), val) != 1) &&
+ (val_compare(&(t->to), val) != -1))
+ return t;
+
+ return NULL;
+}
+
static struct f_tree *
build_tree_rec(struct f_tree **buf, int l, int h)
{