ranges: introduce rl_invert(), rl_filter() and rl_intersection()
authorDan Carpenter <dan.carpenter@oracle.com>
Fri, 14 Dec 2012 12:12:46 +0000 (14 15:12 +0300)
committerDan Carpenter <dan.carpenter@oracle.com>
Fri, 14 Dec 2012 12:12:46 +0000 (14 15:12 +0300)
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>
smatch_extra.h
smatch_ranges.c

index 0e14583..76227ee 100644 (file)
@@ -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);
index 7def450..7067d87 100644 (file)
@@ -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);