From 86b965bdab8dc8735c4a846ec09bfbbadfae780b Mon Sep 17 00:00:00 2001 From: Patrick McHardy Date: Thu, 16 Jan 2014 17:11:12 +0000 Subject: segtree: fix decomposition of unclosed intervals If intervals are directly adjacent or extend to the right end of the dimension, they are not closed by a EXPR_F_INTERVAL_END entry. This leads to multiple errors when decomposing the intervals: - the last unclosed interval is not shown at all. - if a range is unclosed and the set is a map, the starting point of the next interval is set to the data, not the key, leading to nonsensical output. - if a prefix is unclosed, the interval is assumed to be a prefix as well and the same starting point is kept. This makes sense for cases like 192.168.0.0/24, 192.168.0.0/16, but leads to hard to understand results if the next interval is not representable as a prefix. Fix this by doing two things: - add an EXPR_F_INTERVAL_END element for each unclosed interval during preprocessing. - process the final unclosed interval extending to the right end of the dimension, if present. Signed-off-by: Patrick McHardy --- src/segtree.c | 39 ++++++++++++++++++++++++++++++--------- 1 file changed, 30 insertions(+), 9 deletions(-) (limited to 'src/segtree.c') diff --git a/src/segtree.c b/src/segtree.c index e3bca4ca..1a21c6c1 100644 --- a/src/segtree.c +++ b/src/segtree.c @@ -509,10 +509,11 @@ static struct expr *expr_value(struct expr *expr) void interval_map_decompose(struct expr *set) { - struct expr *ranges[set->size]; - struct expr *i, *next, *low = NULL; + struct expr *ranges[set->size * 2]; + struct expr *i, *next, *low = NULL, *end; unsigned int n, size; mpz_t range, p; + bool interval; mpz_init(range); mpz_init(p); @@ -520,8 +521,20 @@ void interval_map_decompose(struct expr *set) size = set->size; n = 0; + interval = false; list_for_each_entry_safe_reverse(i, next, &set->expressions, list) { compound_expr_remove(set, i); + + if (i->flags & EXPR_F_INTERVAL_END) + interval = false; + else if (interval) { + end = expr_clone(expr_value(i)); + end->flags |= EXPR_F_INTERVAL_END; + ranges[n++] = end; + size++; + } else + interval = true; + ranges[n++] = i; } @@ -569,8 +582,6 @@ void interval_map_decompose(struct expr *set) tmp = mapping_expr_alloc(&tmp->location, tmp, low->right); compound_expr_add(set, tmp); - - low = expr_get(tmp->right); } else { struct expr *prefix; unsigned int prefix_len; @@ -578,13 +589,9 @@ void interval_map_decompose(struct expr *set) prefix_len = expr_value(i)->len - mpz_scan0(range, 0); prefix = prefix_expr_alloc(&low->location, expr_value(low), prefix_len); - - if (low->ops->type == EXPR_MAPPING) { + if (low->ops->type == EXPR_MAPPING) prefix = mapping_expr_alloc(&low->location, prefix, low->right); - /* Update mapping of "low" to the current mapping */ - low->right = expr_get(i->right); - } compound_expr_add(set, prefix); } @@ -595,4 +602,18 @@ void interval_map_decompose(struct expr *set) } expr_free(i); } + + /* Unclosed interval */ + if (low != NULL) { + i = constant_expr_alloc(&low->location, low->dtype, + low->byteorder, expr_value(low)->len, + NULL); + mpz_init_bitmask(i->value, i->len); + + i = range_expr_alloc(&low->location, expr_value(low), i); + if (low->ops->type == EXPR_MAPPING) + i = mapping_expr_alloc(&i->location, i, low->right); + + compound_expr_add(set, i); + } } -- cgit v1.2.3