From: Dan Carpenter <dan.carpenter@oracle.com>
Date: Fri, 14 Dec 2012 12:12:46 +0000 (+0300)
Subject: ranges: introduce rl_invert(), rl_filter() and rl_intersection()
X-Git-Tag: 1.57~116
X-Git-Url: https://repo.or.cz/w/smatch.git/commitdiff_plain/0c412610f0424adf21cf70ec0af4ec0217edf7e6

ranges: introduce rl_invert(), rl_filter() and rl_intersection()

Some new helper functions for manipulating range_lists.  I will use them in
a later patch.

rl_invert() takes a range list and gives you the opposite ranges.
rl_filter() takes two ranges lists and returns everything that is in the
            first but not in the second.
rl_intersection() takes two range lists and returns what ever is in both.

Signed-off-by: Dan Carpenter <dan.carpenter@oracle.com>
---

diff --git a/smatch_extra.h b/smatch_extra.h
index 0e14583d..76227ee5 100644
--- a/smatch_extra.h
+++ b/smatch_extra.h
@@ -61,6 +61,9 @@ char *show_ranges(struct range_list *list);
 void parse_value_ranges_type(struct symbol *type, char *value, struct range_list **rl);
 
 struct range_list *remove_range(struct range_list *list, sval_t min, sval_t max);
+struct range_list *rl_invert(struct range_list *orig);
+struct range_list *rl_filter(struct range_list *rl, struct range_list *filter);
+struct range_list *rl_intersection(struct range_list *one, struct range_list *two);
 
 /* used in smatch_slist.  implemented in smatch_extra.c */
 int implied_not_equal(struct expression *expr, long long val);
diff --git a/smatch_ranges.c b/smatch_ranges.c
index 7def4502..7067d874 100644
--- a/smatch_ranges.c
+++ b/smatch_ranges.c
@@ -709,6 +709,51 @@ struct range_list *cast_rl(struct symbol *type, struct range_list *rl)
 	return ret;
 }
 
+struct range_list *rl_invert(struct range_list *orig)
+{
+	struct range_list *ret = NULL;
+	struct data_range *tmp;
+	sval_t gap_min, abs_max, sval;
+
+	if (!orig)
+		return NULL;
+
+	gap_min = sval_type_min(rl_min(orig).type);
+	abs_max = sval_type_max(rl_max(orig).type);
+
+	FOR_EACH_PTR(orig, tmp) {
+		if (sval_cmp(tmp->min, gap_min) > 0) {
+			sval = sval_type_val(tmp->min.type, tmp->min.value - 1);
+			add_range(&ret, gap_min, sval);
+		}
+		gap_min = sval_type_val(tmp->max.type, tmp->max.value + 1);
+		if (sval_cmp(tmp->max, abs_max) == 0)
+			gap_min = abs_max;
+	} END_FOR_EACH_PTR(tmp);
+
+	if (sval_cmp(gap_min, abs_max) < 0)
+		add_range(&ret, gap_min, abs_max);
+
+	return ret;
+}
+
+struct range_list *rl_filter(struct range_list *rl, struct range_list *filter)
+{
+	struct data_range *tmp;
+
+	FOR_EACH_PTR(filter, tmp) {
+		rl = remove_range(rl, tmp->min, tmp->max);
+	} END_FOR_EACH_PTR(tmp);
+
+	return rl;
+}
+
+struct range_list *rl_intersection(struct range_list *one, struct range_list *two)
+{
+	two = rl_invert(two);
+	return rl_filter(one, two);
+}
+
 void free_range_list(struct range_list **rlist)
 {
 	__free_ptr_list((struct ptr_list **)rlist);