From 4596a11b838abe619d531f9d1556fcb9b90202c1 Mon Sep 17 00:00:00 2001 From: Patrick McHardy Date: Fri, 7 Mar 2014 11:30:10 +0100 Subject: segtree: sort set elements before decomposition The decomposition phase currently depends on the kernel returning elements in sorted order. This is a fragile assumption, change the code to sort the elements itself. Signed-off-by: Patrick McHardy --- src/segtree.c | 28 ++++++++++++++++++++++------ 1 file changed, 22 insertions(+), 6 deletions(-) (limited to 'src/segtree.c') diff --git a/src/segtree.c b/src/segtree.c index c169f8d1..1785f640 100644 --- a/src/segtree.c +++ b/src/segtree.c @@ -516,23 +516,39 @@ static struct expr *expr_value(struct expr *expr) return expr; } +static int expr_value_cmp(const void *p1, const void *p2) +{ + struct expr *e1 = *(void * const *)p1; + struct expr *e2 = *(void * const *)p2; + + return mpz_cmp(expr_value(e1)->value, expr_value(e2)->value); +} + void interval_map_decompose(struct expr *set) { - struct expr *ranges[set->size * 2]; + struct expr *elements[set->size], *ranges[set->size * 2]; struct expr *i, *next, *low = NULL, *end; - unsigned int n, size; + unsigned int n, m, size; mpz_t range, p; bool interval; mpz_init(range); mpz_init(p); - size = set->size; + /* Sort elements */ n = 0; + list_for_each_entry_safe(i, next, &set->expressions, list) { + compound_expr_remove(set, i); + elements[n++] = i; + } + qsort(elements, n, sizeof(elements[0]), expr_value_cmp); + size = n; + /* Transform points (single values) into half-closed intervals */ + n = 0; interval = false; - list_for_each_entry_safe_reverse(i, next, &set->expressions, list) { - compound_expr_remove(set, i); + for (m = 0; m < size; m++) { + i = elements[m]; if (i->flags & EXPR_F_INTERVAL_END) interval = false; @@ -540,12 +556,12 @@ void interval_map_decompose(struct expr *set) end = expr_clone(expr_value(i)); end->flags |= EXPR_F_INTERVAL_END; ranges[n++] = end; - size++; } else interval = true; ranges[n++] = i; } + size = n; for (n = 0; n < size; n++) { i = ranges[n]; -- cgit v1.2.3