2 * sparse/smatch_ranges.c
4 * Copyright (C) 2009 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
12 #include "smatch_extra.h"
13 #include "smatch_slist.h"
15 ALLOCATOR(data_info
, "smatch extra data");
16 ALLOCATOR(data_range
, "data range");
17 __DO_ALLOCATOR(struct data_range
, sizeof(struct data_range
), __alignof__(struct data_range
),
18 "permanent ranges", perm_data_range
);
19 ALLOCATOR(data_range_sval
, "data range sval");
20 __DO_ALLOCATOR(struct data_range_sval
, sizeof(struct data_range_sval
), __alignof__(struct data_range_sval
),
21 "permanent ranges sval", perm_data_range_sval
);
23 struct data_range whole_range
= {
28 static char *show_num(long long num
)
30 static char buff
[256];
32 if (num
== whole_range
.min
)
33 snprintf(buff
, 255, "min");
34 else if (num
== whole_range
.max
)
35 snprintf(buff
, 255, "max");
37 snprintf(buff
, 255, "(%lld)", num
);
39 snprintf(buff
, 255, "%lld", num
);
45 char *show_ranges(struct range_list
*list
)
47 struct data_range
*tmp
;
53 FOR_EACH_PTR(list
, tmp
) {
55 strncat(full
, ",", 254 - strlen(full
));
56 if (tmp
->min
== tmp
->max
) {
57 strncat(full
, show_num(tmp
->min
), 254 - strlen(full
));
60 strncat(full
, show_num(tmp
->min
), 254 - strlen(full
));
61 strncat(full
, "-", 254 - strlen(full
));
62 strncat(full
, show_num(tmp
->max
), 254 - strlen(full
));
63 } END_FOR_EACH_PTR(tmp
);
64 return alloc_sname(full
);
67 char *show_ranges_sval(struct range_list_sval
*list
)
69 struct data_range_sval
*tmp
;
75 FOR_EACH_PTR(list
, tmp
) {
77 strncat(full
, ",", 254 - strlen(full
));
78 if (sval_cmp(tmp
->min
, tmp
->max
) == 0) {
79 strncat(full
, sval_to_str(tmp
->min
), 254 - strlen(full
));
82 strncat(full
, sval_to_str(tmp
->min
), 254 - strlen(full
));
83 strncat(full
, "-", 254 - strlen(full
));
84 strncat(full
, sval_to_str(tmp
->max
), 254 - strlen(full
));
85 } END_FOR_EACH_PTR(tmp
);
86 return alloc_sname(full
);
89 void get_value_ranges(char *value
, struct range_list
**rl
)
103 if (!strncmp(start
, "max", 3)) {
106 } else if (!strncmp(start
, "u64max", 6)) {
107 val1
= LLONG_MAX
; // FIXME
109 } else if (!strncmp(start
, "s64max", 6)) {
112 } else if (!strncmp(start
, "u32max", 6)) {
115 } else if (!strncmp(start
, "s32max", 6)) {
118 } else if (!strncmp(start
, "u16max", 6)) {
121 } else if (!strncmp(start
, "s16max", 6)) {
124 } else if (!strncmp(start
, "min", 3)) {
127 } else if (!strncmp(start
, "s64min", 6)) {
130 } else if (!strncmp(start
, "s32min", 6)) {
133 } else if (!strncmp(start
, "s16min", 6)) {
137 while (*c
&& *c
!= ',' && *c
!= '-')
139 val1
= strtoll(start
, &c
, 10);
144 add_range(rl
, val1
, val1
);
148 add_range(rl
, val1
, val1
);
153 c
++; /* skip the dash in eg. 4-5 */
157 if (!strncmp(start
, "max", 3)) {
162 while (*c
&& *c
!= ',' && *c
!= '-')
164 val2
= strtoll(start
, &c
, 10);
166 add_range(rl
, val1
, val2
);
171 c
++; /* skip the comma in eg: 4-5,7 */
175 void get_value_ranges_sval(char *value
, struct range_list_sval
**rl
)
177 struct range_list
*tmp_rl
= NULL
;
179 get_value_ranges(value
, &tmp_rl
);
180 *rl
= range_list_to_sval(tmp_rl
);
183 static struct data_range range_zero
= {
188 static struct data_range range_one
= {
193 int is_whole_range_rl(struct range_list
*rl
)
195 struct data_range
*drange
;
197 if (ptr_list_empty(rl
))
199 drange
= first_ptr_list((struct ptr_list
*)rl
);
200 if (drange
->min
== whole_range
.min
&& drange
->max
== whole_range
.max
)
205 int is_whole_range_rl_sval(struct range_list_sval
*rl
)
207 struct data_range_sval
*drange
;
209 if (ptr_list_empty(rl
))
211 drange
= first_ptr_list((struct ptr_list
*)rl
);
212 if (sval_is_min(drange
->min
) && sval_is_max(drange
->max
))
217 long long rl_min(struct range_list
*rl
)
219 struct data_range
*drange
;
221 if (ptr_list_empty(rl
))
222 return whole_range
.min
;
223 drange
= first_ptr_list((struct ptr_list
*)rl
);
227 sval_t
rl_min_sval(struct range_list_sval
*rl
)
229 struct data_range_sval
*drange
;
232 ret
.type
= &llong_ctype
;
233 ret
.value
= LLONG_MIN
;
234 if (ptr_list_empty(rl
))
236 drange
= first_ptr_list((struct ptr_list
*)rl
);
240 long long rl_max(struct range_list
*rl
)
242 struct data_range
*drange
;
244 if (ptr_list_empty(rl
))
245 return whole_range
.max
;
246 drange
= last_ptr_list((struct ptr_list
*)rl
);
250 sval_t
rl_max_sval(struct range_list_sval
*rl
)
252 struct data_range_sval
*drange
;
255 ret
.type
= &llong_ctype
;
256 ret
.value
= LLONG_MAX
;
257 if (ptr_list_empty(rl
))
259 drange
= last_ptr_list((struct ptr_list
*)rl
);
263 static struct data_range
*alloc_range_helper(long long min
, long long max
, int perm
)
265 struct data_range
*ret
;
268 // sm_msg("debug invalid range %lld to %lld", min, max);
269 min
= whole_range
.min
;
270 max
= whole_range
.max
;
272 if (min
== whole_range
.min
&& max
== whole_range
.max
)
274 if (min
== 0 && max
== 0)
276 if (min
== 1 && max
== 1)
280 ret
= __alloc_perm_data_range(0);
282 ret
= __alloc_data_range(0);
288 static struct data_range_sval
*alloc_range_helper_sval(sval_t min
, sval_t max
, int perm
)
290 struct data_range_sval
*ret
;
292 if (sval_cmp(min
, max
) > 0) {
293 // sm_msg("debug invalid range %lld to %lld", min, max);
294 min
.value
= LLONG_MIN
; /* fixme: need a way to represent unknown svals */
295 max
.value
= LLONG_MAX
;
299 ret
= __alloc_perm_data_range_sval(0);
301 ret
= __alloc_data_range_sval(0);
307 struct data_range
*alloc_range(long long min
, long long max
)
309 return alloc_range_helper(min
, max
, 0);
312 struct data_range_sval
*alloc_range_sval(sval_t min
, sval_t max
)
314 return alloc_range_helper_sval(min
, max
, 0);
317 struct data_range_sval
*drange_to_drange_sval(struct data_range
*drange
)
319 return alloc_range_helper_sval(ll_to_sval(drange
->min
), ll_to_sval(drange
->max
), 0);
322 struct data_range
*drange_sval_to_drange(struct data_range_sval
*drange
)
324 return alloc_range_helper(sval_to_ll(drange
->min
), sval_to_ll(drange
->max
), 0);
327 struct data_range
*alloc_range_perm(long long min
, long long max
)
329 return alloc_range_helper(min
, max
, 1);
332 struct data_range_sval
*alloc_range_perm_sval(sval_t min
, sval_t max
)
334 return alloc_range_helper_sval(min
, max
, 1);
337 struct range_list
*alloc_range_list(long long min
, long long max
)
339 struct range_list
*rl
= NULL
;
341 add_range(&rl
, min
, max
);
345 struct range_list_sval
*alloc_range_list_sval(sval_t min
, sval_t max
)
347 struct range_list_sval
*rl
= NULL
;
349 add_range_sval(&rl
, min
, max
);
353 struct range_list
*whole_range_list(void)
355 return alloc_range_list(whole_range
.min
, whole_range
.max
);
358 void add_range(struct range_list
**list
, long long min
, long long max
)
360 struct data_range
*tmp
= NULL
;
361 struct data_range
*new = NULL
;
365 * FIXME: This has a problem merging a range_list like: min-0,3-max
366 * with a range like 1-2. You end up with min-2,3-max instead of
369 FOR_EACH_PTR(*list
, tmp
) {
371 /* Sometimes we overlap with more than one range
372 so we have to delete or modify the next range. */
373 if (max
+ 1 == tmp
->min
) {
374 /* join 2 ranges here */
376 DELETE_CURRENT_PTR(tmp
);
380 /* Doesn't overlap with the next one. */
383 /* Partially overlaps with the next one. */
384 if (max
< tmp
->max
) {
388 /* Completely overlaps with the next one. */
389 if (max
>= tmp
->max
) {
390 DELETE_CURRENT_PTR(tmp
);
391 /* there could be more ranges to delete */
395 if (max
!= whole_range
.max
&& max
+ 1 == tmp
->min
) {
396 /* join 2 ranges into a big range */
397 new = alloc_range(min
, tmp
->max
);
398 REPLACE_CURRENT_PTR(tmp
, new);
401 if (max
< tmp
->min
) { /* new range entirely below */
402 new = alloc_range(min
, max
);
403 INSERT_CURRENT(new, tmp
);
406 if (min
< tmp
->min
) { /* new range partially below */
411 new = alloc_range(min
, max
);
412 REPLACE_CURRENT_PTR(tmp
, new);
417 if (max
<= tmp
->max
) /* new range already included */
419 if (min
<= tmp
->max
) { /* new range partially above */
421 new = alloc_range(min
, max
);
422 REPLACE_CURRENT_PTR(tmp
, new);
426 if (min
!= whole_range
.min
&& min
- 1 == tmp
->max
) {
427 /* join 2 ranges into a big range */
428 new = alloc_range(tmp
->min
, max
);
429 REPLACE_CURRENT_PTR(tmp
, new);
433 /* the new range is entirely above the existing ranges */
434 } END_FOR_EACH_PTR(tmp
);
437 new = alloc_range(min
, max
);
438 add_ptr_list(list
, new);
441 void add_range_sval(struct range_list_sval
**list
, sval_t min
, sval_t max
)
443 struct data_range_sval
*tmp
= NULL
;
444 struct data_range_sval
*new = NULL
;
448 * FIXME: This has a problem merging a range_list like: min-0,3-max
449 * with a range like 1-2. You end up with min-2,3-max instead of
452 FOR_EACH_PTR(*list
, tmp
) {
454 /* Sometimes we overlap with more than one range
455 so we have to delete or modify the next range. */
456 if (max
.value
+ 1 == tmp
->min
.value
) {
457 /* join 2 ranges here */
459 DELETE_CURRENT_PTR(tmp
);
463 /* Doesn't overlap with the next one. */
464 if (sval_cmp(max
, tmp
->min
) < 0)
466 /* Partially overlaps with the next one. */
467 if (sval_cmp(max
, tmp
->max
) < 0) {
468 tmp
->min
.value
= max
.value
+ 1;
471 /* Completely overlaps with the next one. */
472 if (sval_cmp(max
, tmp
->max
) >= 0) {
473 DELETE_CURRENT_PTR(tmp
);
474 /* there could be more ranges to delete */
478 if (!sval_is_max(max
) && max
.value
+ 1 == tmp
->min
.value
) {
479 /* join 2 ranges into a big range */
480 new = alloc_range_sval(min
, tmp
->max
);
481 REPLACE_CURRENT_PTR(tmp
, new);
484 if (sval_cmp(max
, tmp
->min
) < 0) { /* new range entirely below */
485 new = alloc_range_sval(min
, max
);
486 INSERT_CURRENT(new, tmp
);
489 if (sval_cmp(min
, tmp
->min
) < 0) { /* new range partially below */
490 if (sval_cmp(max
, tmp
->max
) < 0)
494 new = alloc_range_sval(min
, max
);
495 REPLACE_CURRENT_PTR(tmp
, new);
500 if (sval_cmp(max
, tmp
->max
) <= 0) /* new range already included */
502 if (sval_cmp(min
, tmp
->max
) <= 0) { /* new range partially above */
504 new = alloc_range_sval(min
, max
);
505 REPLACE_CURRENT_PTR(tmp
, new);
509 if (!sval_is_min(min
) && min
.value
- 1 == tmp
->max
.value
) {
510 /* join 2 ranges into a big range */
511 new = alloc_range_sval(tmp
->min
, max
);
512 REPLACE_CURRENT_PTR(tmp
, new);
516 /* the new range is entirely above the existing ranges */
517 } END_FOR_EACH_PTR(tmp
);
520 new = alloc_range_sval(min
, max
);
521 add_ptr_list(list
, new);
524 struct range_list
*clone_range_list(struct range_list
*list
)
526 struct data_range
*tmp
;
527 struct range_list
*ret
= NULL
;
529 FOR_EACH_PTR(list
, tmp
) {
530 add_ptr_list(&ret
, tmp
);
531 } END_FOR_EACH_PTR(tmp
);
535 struct range_list_sval
*clone_range_list_sval(struct range_list_sval
*list
)
537 struct data_range_sval
*tmp
;
538 struct range_list_sval
*ret
= NULL
;
540 FOR_EACH_PTR(list
, tmp
) {
541 add_ptr_list(&ret
, tmp
);
542 } END_FOR_EACH_PTR(tmp
);
546 struct range_list
*clone_permanent(struct range_list
*list
)
548 struct data_range
*tmp
;
549 struct data_range
*new;
550 struct range_list
*ret
= NULL
;
552 FOR_EACH_PTR(list
, tmp
) {
553 new = alloc_range_perm(tmp
->min
, tmp
->max
);
554 add_ptr_list(&ret
, new);
555 } END_FOR_EACH_PTR(tmp
);
559 struct range_list
*range_list_union(struct range_list
*one
, struct range_list
*two
)
561 struct data_range
*tmp
;
562 struct range_list
*ret
= NULL
;
564 FOR_EACH_PTR(one
, tmp
) {
565 add_range(&ret
, tmp
->min
, tmp
->max
);
566 } END_FOR_EACH_PTR(tmp
);
567 FOR_EACH_PTR(two
, tmp
) {
568 add_range(&ret
, tmp
->min
, tmp
->max
);
569 } END_FOR_EACH_PTR(tmp
);
573 struct range_list_sval
*range_list_union_sval(struct range_list_sval
*one
, struct range_list_sval
*two
)
575 struct data_range_sval
*tmp
;
576 struct range_list_sval
*ret
= NULL
;
578 FOR_EACH_PTR(one
, tmp
) {
579 add_range_sval(&ret
, tmp
->min
, tmp
->max
);
580 } END_FOR_EACH_PTR(tmp
);
581 FOR_EACH_PTR(two
, tmp
) {
582 add_range_sval(&ret
, tmp
->min
, tmp
->max
);
583 } END_FOR_EACH_PTR(tmp
);
587 struct range_list
*remove_range(struct range_list
*list
, long long min
, long long max
)
589 struct data_range
*tmp
;
590 struct range_list
*ret
= NULL
;
592 FOR_EACH_PTR(list
, tmp
) {
593 if (tmp
->max
< min
) {
594 add_range(&ret
, tmp
->min
, tmp
->max
);
597 if (tmp
->min
> max
) {
598 add_range(&ret
, tmp
->min
, tmp
->max
);
601 if (tmp
->min
>= min
&& tmp
->max
<= max
)
603 if (tmp
->min
>= min
) {
604 add_range(&ret
, max
+ 1, tmp
->max
);
605 } else if (tmp
->max
<= max
) {
606 add_range(&ret
, tmp
->min
, min
- 1);
608 add_range(&ret
, tmp
->min
, min
- 1);
609 add_range(&ret
, max
+ 1, tmp
->max
);
611 } END_FOR_EACH_PTR(tmp
);
615 struct range_list_sval
*remove_range_sval(struct range_list_sval
*list
, sval_t min
, sval_t max
)
617 struct data_range_sval
*tmp
;
618 struct range_list_sval
*ret
= NULL
;
620 FOR_EACH_PTR(list
, tmp
) {
621 if (sval_cmp(tmp
->max
, min
) < 0) {
622 add_range_sval(&ret
, tmp
->min
, tmp
->max
);
625 if (sval_cmp(tmp
->min
, max
) > 0) {
626 add_range_sval(&ret
, tmp
->min
, tmp
->max
);
629 if (sval_cmp(tmp
->min
, min
) >= 0 && sval_cmp(tmp
->max
, max
) <= 0)
631 if (sval_cmp(tmp
->min
, min
) >= 0) {
633 add_range_sval(&ret
, max
, tmp
->max
);
634 } else if (sval_cmp(tmp
->max
, max
) <= 0) {
636 add_range_sval(&ret
, tmp
->min
, min
);
640 add_range_sval(&ret
, tmp
->min
, min
);
641 add_range_sval(&ret
, max
, tmp
->max
);
643 } END_FOR_EACH_PTR(tmp
);
647 struct range_list
*invert_range_list(struct range_list
*orig
)
649 struct range_list
*ret
= NULL
;
650 struct data_range
*tmp
;
656 gap_min
= whole_range
.min
;
657 FOR_EACH_PTR(orig
, tmp
) {
658 if (tmp
->min
> gap_min
)
659 add_range(&ret
, gap_min
, tmp
->min
- 1);
660 gap_min
= tmp
->max
+ 1;
661 if (tmp
->max
== whole_range
.max
)
662 gap_min
= whole_range
.max
;
663 } END_FOR_EACH_PTR(tmp
);
665 if (gap_min
!= whole_range
.max
)
666 add_range(&ret
, gap_min
, whole_range
.max
);
672 * if it can be only one and only value return 1, else return 0
674 int estate_get_single_value(struct smatch_state
*state
, long long *val
)
676 struct data_info
*dinfo
;
677 struct data_range
*tmp
;
680 dinfo
= get_dinfo(state
);
681 if (!dinfo
|| dinfo
->type
!= DATA_RANGE
)
684 FOR_EACH_PTR(dinfo
->value_ranges
, tmp
) {
686 if (tmp
->min
!= tmp
->max
)
692 } END_FOR_EACH_PTR(tmp
);
696 int estate_get_single_value_sval(struct smatch_state
*state
, sval_t
*sval
)
698 struct data_info
*dinfo
;
701 dinfo
= get_dinfo(state
);
702 if (!dinfo
|| dinfo
->type
!= DATA_RANGE
)
705 min
= rl_min_sval(range_list_to_sval(dinfo
->value_ranges
));
706 max
= rl_max_sval(range_list_to_sval(dinfo
->value_ranges
));
707 if (sval_cmp(min
, max
) != 0)
713 int ranges_equiv_sval(struct data_range_sval
*one
, struct data_range_sval
*two
)
719 if (sval_cmp(one
->min
, two
->min
) != 0)
721 if (sval_cmp(one
->max
, two
->max
) != 0)
726 int range_lists_equiv_sval(struct range_list_sval
*one
, struct range_list_sval
*two
)
728 struct data_range_sval
*one_range
;
729 struct data_range_sval
*two_range
;
731 PREPARE_PTR_LIST(one
, one_range
);
732 PREPARE_PTR_LIST(two
, two_range
);
734 if (!one_range
&& !two_range
)
736 if (!ranges_equiv_sval(one_range
, two_range
))
738 NEXT_PTR_LIST(one_range
);
739 NEXT_PTR_LIST(two_range
);
741 FINISH_PTR_LIST(two_range
);
742 FINISH_PTR_LIST(one_range
);
747 int true_comparison_range(struct data_range
*left
, int comparison
, struct data_range
*right
)
749 struct data_range_sval
*tmp_left
, *tmp_right
;
751 tmp_left
= drange_to_drange_sval(left
);
752 tmp_right
= drange_to_drange_sval(right
);
753 return true_comparison_range_sval(tmp_left
, comparison
, tmp_right
);
756 int true_comparison_range_sval(struct data_range_sval
*left
, int comparison
, struct data_range_sval
*right
)
758 switch (comparison
) {
760 case SPECIAL_UNSIGNED_LT
:
761 if (sval_cmp(left
->min
, right
->max
) < 0)
764 case SPECIAL_UNSIGNED_LTE
:
766 if (sval_cmp(left
->min
, right
->max
) <= 0)
770 if (sval_cmp(left
->max
, right
->min
) < 0)
772 if (sval_cmp(left
->min
, right
->max
) > 0)
775 case SPECIAL_UNSIGNED_GTE
:
777 if (sval_cmp(left
->max
, right
->min
) >= 0)
781 case SPECIAL_UNSIGNED_GT
:
782 if (sval_cmp(left
->max
, right
->min
) > 0)
785 case SPECIAL_NOTEQUAL
:
786 if (sval_cmp(left
->min
, left
->max
) != 0)
788 if (sval_cmp(right
->min
, right
->max
) != 0)
790 if (sval_cmp(left
->min
, right
->min
) != 0)
794 sm_msg("unhandled comparison %d\n", comparison
);
800 int true_comparison_range_lr(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
803 return true_comparison_range(var
, comparison
, val
);
805 return true_comparison_range(val
, comparison
, var
);
808 int true_comparison_range_lr_sval(int comparison
, struct data_range_sval
*var
, struct data_range_sval
*val
, int left
)
811 return true_comparison_range_sval(var
, comparison
, val
);
813 return true_comparison_range_sval(val
, comparison
, var
);
816 static int false_comparison_range_sval(struct data_range_sval
*left
, int comparison
, struct data_range_sval
*right
)
818 switch (comparison
) {
820 case SPECIAL_UNSIGNED_LT
:
821 if (sval_cmp(left
->max
, right
->min
) >= 0)
824 case SPECIAL_UNSIGNED_LTE
:
826 if (sval_cmp(left
->max
, right
->min
) > 0)
830 if (sval_cmp(left
->min
, left
->max
) != 0)
832 if (sval_cmp(right
->min
, right
->max
) != 0)
834 if (sval_cmp(left
->min
, right
->min
) != 0)
837 case SPECIAL_UNSIGNED_GTE
:
839 if (sval_cmp(left
->min
, right
->max
) < 0)
843 case SPECIAL_UNSIGNED_GT
:
844 if (sval_cmp(left
->min
, right
->max
) <= 0)
847 case SPECIAL_NOTEQUAL
:
848 if (sval_cmp(left
->max
, right
->min
) < 0)
850 if (sval_cmp(left
->min
, right
->max
) > 0)
854 sm_msg("unhandled comparison %d\n", comparison
);
860 static int false_comparison_range(struct data_range
*left
, int comparison
, struct data_range
*right
)
862 struct data_range_sval
*tmp_left
, *tmp_right
;
864 tmp_left
= drange_to_drange_sval(left
);
865 tmp_right
= drange_to_drange_sval(right
);
866 return false_comparison_range_sval(tmp_left
, comparison
, tmp_right
);
869 int false_comparison_range_lr(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
872 return false_comparison_range(var
, comparison
, val
);
874 return false_comparison_range(val
, comparison
, var
);
877 int false_comparison_range_lr_sval(int comparison
, struct data_range_sval
*var
, struct data_range_sval
*val
, int left
)
880 return false_comparison_range_sval(var
, comparison
, val
);
882 return false_comparison_range_sval(val
, comparison
, var
);
885 int possibly_true(struct expression
*left
, int comparison
, struct expression
*right
)
887 struct range_list_sval
*rl_left
, *rl_right
;
888 struct data_range_sval
*tmp_left
, *tmp_right
;
890 if (!get_implied_range_list_sval(left
, &rl_left
))
892 if (!get_implied_range_list_sval(right
, &rl_right
))
895 FOR_EACH_PTR(rl_left
, tmp_left
) {
896 FOR_EACH_PTR(rl_right
, tmp_right
) {
897 if (true_comparison_range_sval(tmp_left
, comparison
, tmp_right
))
899 } END_FOR_EACH_PTR(tmp_right
);
900 } END_FOR_EACH_PTR(tmp_left
);
904 int possibly_false(struct expression
*left
, int comparison
, struct expression
*right
)
906 struct range_list_sval
*rl_left
, *rl_right
;
907 struct data_range_sval
*tmp_left
, *tmp_right
;
909 if (!get_implied_range_list_sval(left
, &rl_left
))
911 if (!get_implied_range_list_sval(right
, &rl_right
))
914 FOR_EACH_PTR(rl_left
, tmp_left
) {
915 FOR_EACH_PTR(rl_right
, tmp_right
) {
916 if (false_comparison_range_sval(tmp_left
, comparison
, tmp_right
))
918 } END_FOR_EACH_PTR(tmp_right
);
919 } END_FOR_EACH_PTR(tmp_left
);
923 int possibly_true_range_lists(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
925 struct data_range
*left_tmp
, *right_tmp
;
927 if (!left_ranges
|| !right_ranges
)
930 FOR_EACH_PTR(left_ranges
, left_tmp
) {
931 FOR_EACH_PTR(right_ranges
, right_tmp
) {
932 if (true_comparison_range(left_tmp
, comparison
, right_tmp
))
934 } END_FOR_EACH_PTR(right_tmp
);
935 } END_FOR_EACH_PTR(left_tmp
);
939 int possibly_true_range_lists_sval(struct range_list_sval
*left_ranges
, int comparison
, struct range_list_sval
*right_ranges
)
941 struct data_range_sval
*left_tmp
, *right_tmp
;
943 if (!left_ranges
|| !right_ranges
)
946 FOR_EACH_PTR(left_ranges
, left_tmp
) {
947 FOR_EACH_PTR(right_ranges
, right_tmp
) {
948 if (true_comparison_range_sval(left_tmp
, comparison
, right_tmp
))
950 } END_FOR_EACH_PTR(right_tmp
);
951 } END_FOR_EACH_PTR(left_tmp
);
955 int possibly_false_range_lists(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
957 struct data_range
*left_tmp
, *right_tmp
;
959 if (!left_ranges
|| !right_ranges
)
962 FOR_EACH_PTR(left_ranges
, left_tmp
) {
963 FOR_EACH_PTR(right_ranges
, right_tmp
) {
964 if (false_comparison_range(left_tmp
, comparison
, right_tmp
))
966 } END_FOR_EACH_PTR(right_tmp
);
967 } END_FOR_EACH_PTR(left_tmp
);
971 int possibly_false_range_lists_sval(struct range_list_sval
*left_ranges
, int comparison
, struct range_list_sval
*right_ranges
)
973 struct data_range_sval
*left_tmp
, *right_tmp
;
975 if (!left_ranges
|| !right_ranges
)
978 FOR_EACH_PTR(left_ranges
, left_tmp
) {
979 FOR_EACH_PTR(right_ranges
, right_tmp
) {
980 if (false_comparison_range_sval(left_tmp
, comparison
, right_tmp
))
982 } END_FOR_EACH_PTR(right_tmp
);
983 } END_FOR_EACH_PTR(left_tmp
);
987 int possibly_true_range_lists_rl(int comparison
, struct range_list
*a
, struct range_list
*b
, int left
)
990 return possibly_true_range_lists(a
, comparison
, b
);
992 return possibly_true_range_lists(b
, comparison
, a
);
995 /* FIXME: the _rl here stands for right left so really it should be _lr */
996 int possibly_true_range_lists_rl_sval(int comparison
, struct range_list_sval
*a
, struct range_list_sval
*b
, int left
)
999 return possibly_true_range_lists_sval(a
, comparison
, b
);
1001 return possibly_true_range_lists_sval(b
, comparison
, a
);
1004 int possibly_false_range_lists_rl(int comparison
, struct range_list
*a
, struct range_list
*b
, int left
)
1007 return possibly_false_range_lists(a
, comparison
, b
);
1009 return possibly_false_range_lists(b
, comparison
, a
);
1012 int possibly_false_range_lists_rl_sval(int comparison
, struct range_list_sval
*a
, struct range_list_sval
*b
, int left
)
1015 return possibly_false_range_lists_sval(a
, comparison
, b
);
1017 return possibly_false_range_lists_sval(b
, comparison
, a
);
1020 void tack_on(struct range_list
**list
, struct data_range
*drange
)
1022 add_ptr_list(list
, drange
);
1025 void tack_on_sval(struct range_list_sval
**list
, struct data_range_sval
*drange
)
1027 add_ptr_list(list
, drange
);
1030 void push_range_list(struct range_list_stack
**rl_stack
, struct range_list
*rl
)
1032 add_ptr_list(rl_stack
, rl
);
1035 void push_range_list_sval(struct range_list_stack_sval
**rl_stack
, struct range_list_sval
*rl
)
1037 add_ptr_list(rl_stack
, rl
);
1040 struct range_list
*pop_range_list(struct range_list_stack
**rl_stack
)
1042 struct range_list
*rl
;
1044 rl
= last_ptr_list((struct ptr_list
*)*rl_stack
);
1045 delete_ptr_list_last((struct ptr_list
**)rl_stack
);
1049 struct range_list_sval
*pop_range_list_sval(struct range_list_stack_sval
**rl_stack
)
1051 struct range_list_sval
*rl
;
1053 rl
= last_ptr_list((struct ptr_list
*)*rl_stack
);
1054 delete_ptr_list_last((struct ptr_list
**)rl_stack
);
1058 struct range_list
*top_range_list(struct range_list_stack
*rl_stack
)
1060 struct range_list
*rl
;
1062 rl
= last_ptr_list((struct ptr_list
*)rl_stack
);
1066 struct range_list_sval
*top_range_list_sval(struct range_list_stack_sval
*rl_stack
)
1068 struct range_list_sval
*rl
;
1070 rl
= last_ptr_list((struct ptr_list
*)rl_stack
);
1074 void filter_top_range_list(struct range_list_stack
**rl_stack
, long long num
)
1076 struct range_list
*rl
;
1078 rl
= pop_range_list(rl_stack
);
1079 rl
= remove_range(rl
, num
, num
);
1080 push_range_list(rl_stack
, rl
);
1083 void filter_top_range_list_sval(struct range_list_stack_sval
**rl_stack
, sval_t sval
)
1085 struct range_list_sval
*rl
;
1087 rl
= pop_range_list_sval(rl_stack
);
1088 rl
= remove_range_sval(rl
, sval
, sval
);
1089 push_range_list_sval(rl_stack
, rl
);
1092 void free_range_list(struct range_list
**rlist
)
1094 __free_ptr_list((struct ptr_list
**)rlist
);
1097 void free_range_list_sval(struct range_list_sval
**rlist
)
1099 __free_ptr_list((struct ptr_list
**)rlist
);
1102 static void free_single_dinfo(struct data_info
*dinfo
)
1104 if (dinfo
->type
== DATA_RANGE
)
1105 free_range_list(&dinfo
->value_ranges
);
1108 static void free_dinfos(struct allocation_blob
*blob
)
1110 unsigned int size
= sizeof(struct data_info
);
1111 unsigned int offset
= 0;
1113 while (offset
< blob
->offset
) {
1114 free_single_dinfo((struct data_info
*)(blob
->data
+ offset
));
1119 void free_data_info_allocs(void)
1121 struct allocator_struct
*desc
= &data_info_allocator
;
1122 struct allocation_blob
*blob
= desc
->blobs
;
1125 desc
->allocations
= 0;
1126 desc
->total_bytes
= 0;
1127 desc
->useful_bytes
= 0;
1128 desc
->freelist
= NULL
;
1130 struct allocation_blob
*next
= blob
->next
;
1132 blob_free(blob
, desc
->chunking
);
1135 clear_data_range_alloc();
1138 struct range_list_sval
*range_list_to_sval(struct range_list
*list
)
1140 struct data_range
*tmp
;
1141 struct data_range_sval
*tmp_sval
;
1142 struct range_list_sval
*ret
= NULL
;
1144 FOR_EACH_PTR(list
, tmp
) {
1145 tmp_sval
= drange_to_drange_sval(tmp
);
1146 add_ptr_list(&ret
, tmp_sval
);
1147 } END_FOR_EACH_PTR(tmp
);
1151 struct range_list
*rl_sval_to_rl(struct range_list_sval
*list
)
1153 struct data_range
*tmp
;
1154 struct data_range_sval
*tmp_sval
;
1155 struct range_list
*ret
= NULL
;
1157 FOR_EACH_PTR(list
, tmp_sval
) {
1158 tmp
= drange_sval_to_drange(tmp_sval
);
1159 add_ptr_list(&ret
, tmp
);
1160 } END_FOR_EACH_PTR(tmp_sval
);