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 int rl_contiguous(struct range_list
*rl
)
219 if (first_ptr_list((struct ptr_list
*)rl
) == last_ptr_list((struct ptr_list
*)rl
))
224 long long rl_min(struct range_list
*rl
)
226 struct data_range
*drange
;
228 if (ptr_list_empty(rl
))
229 return whole_range
.min
;
230 drange
= first_ptr_list((struct ptr_list
*)rl
);
234 sval_t
rl_min_sval(struct range_list
*rl
)
236 struct data_range
*drange
;
239 ret
.type
= &llong_ctype
;
240 ret
.value
= LLONG_MIN
;
241 if (ptr_list_empty(rl
))
243 drange
= first_ptr_list((struct ptr_list
*)rl
);
244 ret
.value
= drange
->min
;
248 long long rl_max(struct range_list
*rl
)
250 struct data_range
*drange
;
252 if (ptr_list_empty(rl
))
253 return whole_range
.max
;
254 drange
= last_ptr_list((struct ptr_list
*)rl
);
258 sval_t
rl_max_sval(struct range_list
*rl
)
260 struct data_range
*drange
;
263 ret
.type
= &llong_ctype
;
264 ret
.value
= LLONG_MAX
;
265 if (ptr_list_empty(rl
))
267 drange
= last_ptr_list((struct ptr_list
*)rl
);
268 ret
.value
= drange
->max
;
272 static struct data_range
*alloc_range_helper(long long min
, long long max
, int perm
)
274 struct data_range
*ret
;
277 // sm_msg("debug invalid range %lld to %lld", min, max);
278 min
= whole_range
.min
;
279 max
= whole_range
.max
;
281 if (min
== whole_range
.min
&& max
== whole_range
.max
)
283 if (min
== 0 && max
== 0)
285 if (min
== 1 && max
== 1)
289 ret
= __alloc_perm_data_range(0);
291 ret
= __alloc_data_range(0);
297 static struct data_range_sval
*alloc_range_helper_sval(sval_t min
, sval_t max
, int perm
)
299 struct data_range_sval
*ret
;
301 if (sval_cmp(min
, max
) > 0) {
302 // sm_msg("debug invalid range %lld to %lld", min, max);
303 min
.value
= LLONG_MIN
; /* fixme: need a way to represent unknown svals */
304 max
.value
= LLONG_MAX
;
308 ret
= __alloc_perm_data_range_sval(0);
310 ret
= __alloc_data_range_sval(0);
316 struct data_range
*alloc_range(long long min
, long long max
)
318 return alloc_range_helper(min
, max
, 0);
321 struct data_range_sval
*alloc_range_sval(sval_t min
, sval_t max
)
323 return alloc_range_helper_sval(min
, max
, 0);
326 struct data_range_sval
*drange_to_drange_sval(struct data_range
*drange
)
328 return alloc_range_helper_sval(ll_to_sval(drange
->min
), ll_to_sval(drange
->max
), 0);
331 struct data_range
*drange_sval_to_drange(struct data_range_sval
*drange
)
333 return alloc_range_helper(sval_to_ll(drange
->min
), sval_to_ll(drange
->max
), 0);
336 struct data_range
*alloc_range_perm(long long min
, long long max
)
338 return alloc_range_helper(min
, max
, 1);
341 struct data_range_sval
*alloc_range_perm_sval(sval_t min
, sval_t max
)
343 return alloc_range_helper_sval(min
, max
, 1);
346 struct range_list
*alloc_range_list(long long min
, long long max
)
348 struct range_list
*rl
= NULL
;
350 add_range(&rl
, min
, max
);
354 struct range_list_sval
*alloc_range_list_sval(sval_t min
, sval_t max
)
356 struct range_list_sval
*rl
= NULL
;
358 add_range_sval(&rl
, min
, max
);
362 struct range_list
*whole_range_list(void)
364 return alloc_range_list(whole_range
.min
, whole_range
.max
);
367 void add_range(struct range_list
**list
, long long min
, long long max
)
369 struct data_range
*tmp
= NULL
;
370 struct data_range
*new = NULL
;
374 * FIXME: This has a problem merging a range_list like: min-0,3-max
375 * with a range like 1-2. You end up with min-2,3-max instead of
378 FOR_EACH_PTR(*list
, tmp
) {
380 /* Sometimes we overlap with more than one range
381 so we have to delete or modify the next range. */
382 if (max
+ 1 == tmp
->min
) {
383 /* join 2 ranges here */
385 DELETE_CURRENT_PTR(tmp
);
389 /* Doesn't overlap with the next one. */
392 /* Partially overlaps with the next one. */
393 if (max
< tmp
->max
) {
397 /* Completely overlaps with the next one. */
398 if (max
>= tmp
->max
) {
399 DELETE_CURRENT_PTR(tmp
);
400 /* there could be more ranges to delete */
404 if (max
!= whole_range
.max
&& max
+ 1 == tmp
->min
) {
405 /* join 2 ranges into a big range */
406 new = alloc_range(min
, tmp
->max
);
407 REPLACE_CURRENT_PTR(tmp
, new);
410 if (max
< tmp
->min
) { /* new range entirely below */
411 new = alloc_range(min
, max
);
412 INSERT_CURRENT(new, tmp
);
415 if (min
< tmp
->min
) { /* new range partially below */
420 new = alloc_range(min
, max
);
421 REPLACE_CURRENT_PTR(tmp
, new);
426 if (max
<= tmp
->max
) /* new range already included */
428 if (min
<= tmp
->max
) { /* new range partially above */
430 new = alloc_range(min
, max
);
431 REPLACE_CURRENT_PTR(tmp
, new);
435 if (min
!= whole_range
.min
&& min
- 1 == tmp
->max
) {
436 /* join 2 ranges into a big range */
437 new = alloc_range(tmp
->min
, max
);
438 REPLACE_CURRENT_PTR(tmp
, new);
442 /* the new range is entirely above the existing ranges */
443 } END_FOR_EACH_PTR(tmp
);
446 new = alloc_range(min
, max
);
447 add_ptr_list(list
, new);
450 void add_range_sval(struct range_list_sval
**list
, sval_t min
, sval_t max
)
452 struct data_range_sval
*tmp
= NULL
;
453 struct data_range_sval
*new = NULL
;
457 * FIXME: This has a problem merging a range_list like: min-0,3-max
458 * with a range like 1-2. You end up with min-2,3-max instead of
461 FOR_EACH_PTR(*list
, tmp
) {
463 /* Sometimes we overlap with more than one range
464 so we have to delete or modify the next range. */
465 if (max
.value
+ 1 == tmp
->min
.value
) {
466 /* join 2 ranges here */
468 DELETE_CURRENT_PTR(tmp
);
472 /* Doesn't overlap with the next one. */
473 if (sval_cmp(max
, tmp
->min
) < 0)
475 /* Partially overlaps with the next one. */
476 if (sval_cmp(max
, tmp
->max
) < 0) {
477 tmp
->min
.value
= max
.value
+ 1;
480 /* Completely overlaps with the next one. */
481 if (sval_cmp(max
, tmp
->max
) >= 0) {
482 DELETE_CURRENT_PTR(tmp
);
483 /* there could be more ranges to delete */
487 if (max
.value
+ 1 == tmp
->min
.value
) {
488 /* join 2 ranges into a big range */
489 new = alloc_range_sval(min
, tmp
->max
);
490 REPLACE_CURRENT_PTR(tmp
, new);
493 if (sval_cmp(max
, tmp
->min
)) { /* new range entirely below */
494 new = alloc_range_sval(min
, max
);
495 INSERT_CURRENT(new, tmp
);
498 if (sval_cmp(min
, tmp
->min
) < 0) { /* new range partially below */
499 if (sval_cmp(max
, tmp
->max
) < 0)
503 new = alloc_range_sval(min
, max
);
504 REPLACE_CURRENT_PTR(tmp
, new);
509 if (sval_cmp(max
, tmp
->max
) <= 0) /* new range already included */
511 if (sval_cmp(min
, tmp
->max
) <= 0) { /* new range partially above */
513 new = alloc_range_sval(min
, max
);
514 REPLACE_CURRENT_PTR(tmp
, new);
518 if (min
.value
- 1 == tmp
->max
.value
) {
519 /* join 2 ranges into a big range */
520 new = alloc_range_sval(tmp
->min
, max
);
521 REPLACE_CURRENT_PTR(tmp
, new);
525 /* the new range is entirely above the existing ranges */
526 } END_FOR_EACH_PTR(tmp
);
529 new = alloc_range_sval(min
, max
);
530 add_ptr_list(list
, new);
533 struct range_list
*clone_range_list(struct range_list
*list
)
535 struct data_range
*tmp
;
536 struct range_list
*ret
= NULL
;
538 FOR_EACH_PTR(list
, tmp
) {
539 add_ptr_list(&ret
, tmp
);
540 } END_FOR_EACH_PTR(tmp
);
544 struct range_list
*clone_permanent(struct range_list
*list
)
546 struct data_range
*tmp
;
547 struct data_range
*new;
548 struct range_list
*ret
= NULL
;
550 FOR_EACH_PTR(list
, tmp
) {
551 new = alloc_range_perm(tmp
->min
, tmp
->max
);
552 add_ptr_list(&ret
, new);
553 } END_FOR_EACH_PTR(tmp
);
557 struct range_list
*range_list_union(struct range_list
*one
, struct range_list
*two
)
559 struct data_range
*tmp
;
560 struct range_list
*ret
= NULL
;
562 FOR_EACH_PTR(one
, tmp
) {
563 add_range(&ret
, tmp
->min
, tmp
->max
);
564 } END_FOR_EACH_PTR(tmp
);
565 FOR_EACH_PTR(two
, tmp
) {
566 add_range(&ret
, tmp
->min
, tmp
->max
);
567 } END_FOR_EACH_PTR(tmp
);
571 struct range_list_sval
*range_list_union_sval(struct range_list_sval
*one
, struct range_list_sval
*two
)
573 struct data_range_sval
*tmp
;
574 struct range_list_sval
*ret
= NULL
;
576 FOR_EACH_PTR(one
, tmp
) {
577 add_range_sval(&ret
, tmp
->min
, tmp
->max
);
578 } END_FOR_EACH_PTR(tmp
);
579 FOR_EACH_PTR(two
, tmp
) {
580 add_range_sval(&ret
, tmp
->min
, tmp
->max
);
581 } END_FOR_EACH_PTR(tmp
);
585 struct range_list
*remove_range(struct range_list
*list
, long long min
, long long max
)
587 struct data_range
*tmp
;
588 struct range_list
*ret
= NULL
;
590 FOR_EACH_PTR(list
, tmp
) {
591 if (tmp
->max
< min
) {
592 add_range(&ret
, tmp
->min
, tmp
->max
);
595 if (tmp
->min
> max
) {
596 add_range(&ret
, tmp
->min
, tmp
->max
);
599 if (tmp
->min
>= min
&& tmp
->max
<= max
)
601 if (tmp
->min
>= min
) {
602 add_range(&ret
, max
+ 1, tmp
->max
);
603 } else if (tmp
->max
<= max
) {
604 add_range(&ret
, tmp
->min
, min
- 1);
606 add_range(&ret
, tmp
->min
, min
- 1);
607 add_range(&ret
, max
+ 1, tmp
->max
);
609 } END_FOR_EACH_PTR(tmp
);
613 struct range_list
*invert_range_list(struct range_list
*orig
)
615 struct range_list
*ret
= NULL
;
616 struct data_range
*tmp
;
622 gap_min
= whole_range
.min
;
623 FOR_EACH_PTR(orig
, tmp
) {
624 if (tmp
->min
> gap_min
)
625 add_range(&ret
, gap_min
, tmp
->min
- 1);
626 gap_min
= tmp
->max
+ 1;
627 if (tmp
->max
== whole_range
.max
)
628 gap_min
= whole_range
.max
;
629 } END_FOR_EACH_PTR(tmp
);
631 if (gap_min
!= whole_range
.max
)
632 add_range(&ret
, gap_min
, whole_range
.max
);
638 * if it can be only one and only value return 1, else return 0
640 int estate_get_single_value(struct smatch_state
*state
, long long *val
)
642 struct data_info
*dinfo
;
643 struct data_range
*tmp
;
646 dinfo
= get_dinfo(state
);
647 if (!dinfo
|| dinfo
->type
!= DATA_RANGE
)
650 FOR_EACH_PTR(dinfo
->value_ranges
, tmp
) {
652 if (tmp
->min
!= tmp
->max
)
658 } END_FOR_EACH_PTR(tmp
);
662 int estate_get_single_value_sval(struct smatch_state
*state
, sval_t
*sval
)
664 struct data_info
*dinfo
;
667 dinfo
= get_dinfo(state
);
668 if (!dinfo
|| dinfo
->type
!= DATA_RANGE
)
671 min
= rl_min_sval(dinfo
->value_ranges
);
672 max
= rl_max_sval(dinfo
->value_ranges
);
673 if (sval_cmp(min
, max
) != 0)
679 int ranges_equiv_sval(struct data_range_sval
*one
, struct data_range_sval
*two
)
685 if (sval_cmp(one
->min
, two
->min
) != 0)
687 if (sval_cmp(one
->max
, two
->max
) != 0)
692 int range_lists_equiv(struct range_list
*one
, struct range_list
*two
)
694 struct data_range
*one_range
;
695 struct data_range
*two_range
;
697 PREPARE_PTR_LIST(one
, one_range
);
698 PREPARE_PTR_LIST(two
, two_range
);
700 if (!one_range
&& !two_range
)
702 if (!one_range
|| !two_range
)
704 if (one_range
->min
!= two_range
->min
)
706 if (one_range
->max
!= two_range
->max
)
708 NEXT_PTR_LIST(one_range
);
709 NEXT_PTR_LIST(two_range
);
711 FINISH_PTR_LIST(two_range
);
712 FINISH_PTR_LIST(one_range
);
717 int true_comparison_range(struct data_range
*left
, int comparison
, struct data_range
*right
)
719 struct data_range_sval
*tmp_left
, *tmp_right
;
721 tmp_left
= drange_to_drange_sval(left
);
722 tmp_right
= drange_to_drange_sval(right
);
723 return true_comparison_range_sval(tmp_left
, comparison
, tmp_right
);
726 int true_comparison_range_sval(struct data_range_sval
*left
, int comparison
, struct data_range_sval
*right
)
728 switch (comparison
) {
730 case SPECIAL_UNSIGNED_LT
:
731 if (sval_cmp(left
->min
, right
->max
) < 0)
734 case SPECIAL_UNSIGNED_LTE
:
736 if (sval_cmp(left
->min
, right
->max
) <= 0)
740 if (sval_cmp(left
->max
, right
->min
) < 0)
742 if (sval_cmp(left
->min
, right
->max
) > 0)
745 case SPECIAL_UNSIGNED_GTE
:
747 if (sval_cmp(left
->max
, right
->min
) >= 0)
751 case SPECIAL_UNSIGNED_GT
:
752 if (sval_cmp(left
->max
, right
->min
) > 0)
755 case SPECIAL_NOTEQUAL
:
756 if (sval_cmp(left
->min
, left
->max
) != 0)
758 if (sval_cmp(right
->min
, right
->max
) != 0)
760 if (sval_cmp(left
->min
, right
->min
) != 0)
764 sm_msg("unhandled comparison %d\n", comparison
);
770 int true_comparison_range_lr(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
773 return true_comparison_range(var
, comparison
, val
);
775 return true_comparison_range(val
, comparison
, var
);
778 int true_comparison_range_lr_sval(int comparison
, struct data_range_sval
*var
, struct data_range_sval
*val
, int left
)
781 return true_comparison_range_sval(var
, comparison
, val
);
783 return true_comparison_range_sval(val
, comparison
, var
);
786 static int false_comparison_range_sval(struct data_range_sval
*left
, int comparison
, struct data_range_sval
*right
)
788 switch (comparison
) {
790 case SPECIAL_UNSIGNED_LT
:
791 if (sval_cmp(left
->max
, right
->min
) >= 0)
794 case SPECIAL_UNSIGNED_LTE
:
796 if (sval_cmp(left
->max
, right
->min
) > 0)
800 if (sval_cmp(left
->min
, left
->max
) != 0)
802 if (sval_cmp(right
->min
, right
->max
) != 0)
804 if (sval_cmp(left
->min
, right
->min
) != 0)
807 case SPECIAL_UNSIGNED_GTE
:
809 if (sval_cmp(left
->min
, right
->max
) < 0)
813 case SPECIAL_UNSIGNED_GT
:
814 if (sval_cmp(left
->min
, right
->max
) <= 0)
817 case SPECIAL_NOTEQUAL
:
818 if (sval_cmp(left
->max
, right
->min
) < 0)
820 if (sval_cmp(left
->min
, right
->max
) > 0)
824 sm_msg("unhandled comparison %d\n", comparison
);
830 static int false_comparison_range(struct data_range
*left
, int comparison
, struct data_range
*right
)
832 struct data_range_sval
*tmp_left
, *tmp_right
;
834 tmp_left
= drange_to_drange_sval(left
);
835 tmp_right
= drange_to_drange_sval(right
);
836 return false_comparison_range_sval(tmp_left
, comparison
, tmp_right
);
839 int false_comparison_range_lr(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
842 return false_comparison_range(var
, comparison
, val
);
844 return false_comparison_range(val
, comparison
, var
);
847 int false_comparison_range_lr_sval(int comparison
, struct data_range_sval
*var
, struct data_range_sval
*val
, int left
)
850 return false_comparison_range_sval(var
, comparison
, val
);
852 return false_comparison_range_sval(val
, comparison
, var
);
855 int possibly_true(struct expression
*left
, int comparison
, struct expression
*right
)
857 struct range_list
*rl_left
, *rl_right
;
858 struct data_range
*tmp_left
, *tmp_right
;
860 if (!get_implied_range_list(left
, &rl_left
))
862 if (!get_implied_range_list(right
, &rl_right
))
865 FOR_EACH_PTR(rl_left
, tmp_left
) {
866 FOR_EACH_PTR(rl_right
, tmp_right
) {
867 if (true_comparison_range(tmp_left
, comparison
, tmp_right
))
869 } END_FOR_EACH_PTR(tmp_right
);
870 } END_FOR_EACH_PTR(tmp_left
);
874 int possibly_false(struct expression
*left
, int comparison
, struct expression
*right
)
876 struct range_list
*rl_left
, *rl_right
;
877 struct data_range
*tmp_left
, *tmp_right
;
879 if (!get_implied_range_list(left
, &rl_left
))
881 if (!get_implied_range_list(right
, &rl_right
))
884 FOR_EACH_PTR(rl_left
, tmp_left
) {
885 FOR_EACH_PTR(rl_right
, tmp_right
) {
886 if (false_comparison_range(tmp_left
, comparison
, tmp_right
))
888 } END_FOR_EACH_PTR(tmp_right
);
889 } END_FOR_EACH_PTR(tmp_left
);
893 int possibly_true_range_lists(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
895 struct data_range
*left_tmp
, *right_tmp
;
897 if (!left_ranges
|| !right_ranges
)
900 FOR_EACH_PTR(left_ranges
, left_tmp
) {
901 FOR_EACH_PTR(right_ranges
, right_tmp
) {
902 if (true_comparison_range(left_tmp
, comparison
, right_tmp
))
904 } END_FOR_EACH_PTR(right_tmp
);
905 } END_FOR_EACH_PTR(left_tmp
);
909 int possibly_true_range_lists_sval(struct range_list_sval
*left_ranges
, int comparison
, struct range_list_sval
*right_ranges
)
911 struct data_range_sval
*left_tmp
, *right_tmp
;
913 if (!left_ranges
|| !right_ranges
)
916 FOR_EACH_PTR(left_ranges
, left_tmp
) {
917 FOR_EACH_PTR(right_ranges
, right_tmp
) {
918 if (true_comparison_range_sval(left_tmp
, comparison
, right_tmp
))
920 } END_FOR_EACH_PTR(right_tmp
);
921 } END_FOR_EACH_PTR(left_tmp
);
925 int possibly_false_range_lists(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
927 struct data_range
*left_tmp
, *right_tmp
;
929 if (!left_ranges
|| !right_ranges
)
932 FOR_EACH_PTR(left_ranges
, left_tmp
) {
933 FOR_EACH_PTR(right_ranges
, right_tmp
) {
934 if (false_comparison_range(left_tmp
, comparison
, right_tmp
))
936 } END_FOR_EACH_PTR(right_tmp
);
937 } END_FOR_EACH_PTR(left_tmp
);
941 int possibly_false_range_lists_sval(struct range_list_sval
*left_ranges
, int comparison
, struct range_list_sval
*right_ranges
)
943 struct data_range_sval
*left_tmp
, *right_tmp
;
945 if (!left_ranges
|| !right_ranges
)
948 FOR_EACH_PTR(left_ranges
, left_tmp
) {
949 FOR_EACH_PTR(right_ranges
, right_tmp
) {
950 if (false_comparison_range_sval(left_tmp
, comparison
, right_tmp
))
952 } END_FOR_EACH_PTR(right_tmp
);
953 } END_FOR_EACH_PTR(left_tmp
);
957 int possibly_true_range_lists_rl(int comparison
, struct range_list
*a
, struct range_list
*b
, int left
)
960 return possibly_true_range_lists(a
, comparison
, b
);
962 return possibly_true_range_lists(b
, comparison
, a
);
965 /* FIXME: the _rl here stands for right left so really it should be _lr */
966 int possibly_true_range_lists_rl_sval(int comparison
, struct range_list_sval
*a
, struct range_list_sval
*b
, int left
)
969 return possibly_true_range_lists_sval(a
, comparison
, b
);
971 return possibly_true_range_lists_sval(b
, comparison
, a
);
974 int possibly_false_range_lists_rl(int comparison
, struct range_list
*a
, struct range_list
*b
, int left
)
977 return possibly_false_range_lists(a
, comparison
, b
);
979 return possibly_false_range_lists(b
, comparison
, a
);
982 int possibly_false_range_lists_rl_sval(int comparison
, struct range_list_sval
*a
, struct range_list_sval
*b
, int left
)
985 return possibly_false_range_lists_sval(a
, comparison
, b
);
987 return possibly_false_range_lists_sval(b
, comparison
, a
);
990 void tack_on(struct range_list
**list
, struct data_range
*drange
)
992 add_ptr_list(list
, drange
);
995 void tack_on_sval(struct range_list_sval
**list
, struct data_range_sval
*drange
)
997 add_ptr_list(list
, drange
);
1000 void push_range_list(struct range_list_stack
**rl_stack
, struct range_list
*rl
)
1002 add_ptr_list(rl_stack
, rl
);
1005 struct range_list
*pop_range_list(struct range_list_stack
**rl_stack
)
1007 struct range_list
*rl
;
1009 rl
= last_ptr_list((struct ptr_list
*)*rl_stack
);
1010 delete_ptr_list_last((struct ptr_list
**)rl_stack
);
1014 struct range_list
*top_range_list(struct range_list_stack
*rl_stack
)
1016 struct range_list
*rl
;
1018 rl
= last_ptr_list((struct ptr_list
*)rl_stack
);
1022 void filter_top_range_list(struct range_list_stack
**rl_stack
, long long num
)
1024 struct range_list
*rl
;
1026 rl
= pop_range_list(rl_stack
);
1027 rl
= remove_range(rl
, num
, num
);
1028 push_range_list(rl_stack
, rl
);
1031 void free_range_list(struct range_list
**rlist
)
1033 __free_ptr_list((struct ptr_list
**)rlist
);
1036 static void free_single_dinfo(struct data_info
*dinfo
)
1038 if (dinfo
->type
== DATA_RANGE
)
1039 free_range_list(&dinfo
->value_ranges
);
1042 static void free_dinfos(struct allocation_blob
*blob
)
1044 unsigned int size
= sizeof(struct data_info
);
1045 unsigned int offset
= 0;
1047 while (offset
< blob
->offset
) {
1048 free_single_dinfo((struct data_info
*)(blob
->data
+ offset
));
1053 void free_data_info_allocs(void)
1055 struct allocator_struct
*desc
= &data_info_allocator
;
1056 struct allocation_blob
*blob
= desc
->blobs
;
1059 desc
->allocations
= 0;
1060 desc
->total_bytes
= 0;
1061 desc
->useful_bytes
= 0;
1062 desc
->freelist
= NULL
;
1064 struct allocation_blob
*next
= blob
->next
;
1066 blob_free(blob
, desc
->chunking
);
1069 clear_data_range_alloc();
1072 struct range_list_sval
*range_list_to_sval(struct range_list
*list
)
1074 struct data_range
*tmp
;
1075 struct data_range_sval
*tmp_sval
;
1076 struct range_list_sval
*ret
= NULL
;
1078 FOR_EACH_PTR(list
, tmp
) {
1079 tmp_sval
= drange_to_drange_sval(tmp
);
1080 add_ptr_list(&ret
, tmp_sval
);
1081 } END_FOR_EACH_PTR(tmp
);
1085 struct range_list
*rl_sval_to_rl(struct range_list_sval
*list
)
1087 struct data_range
*tmp
;
1088 struct data_range_sval
*tmp_sval
;
1089 struct range_list
*ret
= NULL
;
1091 FOR_EACH_PTR(list
, tmp_sval
) {
1092 tmp
= drange_sval_to_drange(tmp_sval
);
1093 add_ptr_list(&ret
, tmp
);
1094 } END_FOR_EACH_PTR(tmp_sval
);