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
);
671 int estate_get_single_value_sval(struct smatch_state
*state
, sval_t
*sval
)
675 min
= rl_min_sval(estate_ranges_sval(state
));
676 max
= rl_max_sval(estate_ranges_sval(state
));
677 if (sval_cmp(min
, max
) != 0)
683 int ranges_equiv_sval(struct data_range_sval
*one
, struct data_range_sval
*two
)
689 if (sval_cmp(one
->min
, two
->min
) != 0)
691 if (sval_cmp(one
->max
, two
->max
) != 0)
696 int range_lists_equiv_sval(struct range_list_sval
*one
, struct range_list_sval
*two
)
698 struct data_range_sval
*one_range
;
699 struct data_range_sval
*two_range
;
701 PREPARE_PTR_LIST(one
, one_range
);
702 PREPARE_PTR_LIST(two
, two_range
);
704 if (!one_range
&& !two_range
)
706 if (!ranges_equiv_sval(one_range
, two_range
))
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_sval
*rl_left
, *rl_right
;
858 struct data_range_sval
*tmp_left
, *tmp_right
;
860 if (!get_implied_range_list_sval(left
, &rl_left
))
862 if (!get_implied_range_list_sval(right
, &rl_right
))
865 FOR_EACH_PTR(rl_left
, tmp_left
) {
866 FOR_EACH_PTR(rl_right
, tmp_right
) {
867 if (true_comparison_range_sval(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_sval
*rl_left
, *rl_right
;
877 struct data_range_sval
*tmp_left
, *tmp_right
;
879 if (!get_implied_range_list_sval(left
, &rl_left
))
881 if (!get_implied_range_list_sval(right
, &rl_right
))
884 FOR_EACH_PTR(rl_left
, tmp_left
) {
885 FOR_EACH_PTR(rl_right
, tmp_right
) {
886 if (false_comparison_range_sval(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 void push_range_list_sval(struct range_list_stack_sval
**rl_stack
, struct range_list_sval
*rl
)
1007 add_ptr_list(rl_stack
, rl
);
1010 struct range_list
*pop_range_list(struct range_list_stack
**rl_stack
)
1012 struct range_list
*rl
;
1014 rl
= last_ptr_list((struct ptr_list
*)*rl_stack
);
1015 delete_ptr_list_last((struct ptr_list
**)rl_stack
);
1019 struct range_list_sval
*pop_range_list_sval(struct range_list_stack_sval
**rl_stack
)
1021 struct range_list_sval
*rl
;
1023 rl
= last_ptr_list((struct ptr_list
*)*rl_stack
);
1024 delete_ptr_list_last((struct ptr_list
**)rl_stack
);
1028 struct range_list
*top_range_list(struct range_list_stack
*rl_stack
)
1030 struct range_list
*rl
;
1032 rl
= last_ptr_list((struct ptr_list
*)rl_stack
);
1036 struct range_list_sval
*top_range_list_sval(struct range_list_stack_sval
*rl_stack
)
1038 struct range_list_sval
*rl
;
1040 rl
= last_ptr_list((struct ptr_list
*)rl_stack
);
1044 void filter_top_range_list(struct range_list_stack
**rl_stack
, long long num
)
1046 struct range_list
*rl
;
1048 rl
= pop_range_list(rl_stack
);
1049 rl
= remove_range(rl
, num
, num
);
1050 push_range_list(rl_stack
, rl
);
1053 void filter_top_range_list_sval(struct range_list_stack_sval
**rl_stack
, sval_t sval
)
1055 struct range_list_sval
*rl
;
1057 rl
= pop_range_list_sval(rl_stack
);
1058 rl
= remove_range_sval(rl
, sval
, sval
);
1059 push_range_list_sval(rl_stack
, rl
);
1062 void free_range_list(struct range_list
**rlist
)
1064 __free_ptr_list((struct ptr_list
**)rlist
);
1067 void free_range_list_sval(struct range_list_sval
**rlist
)
1069 __free_ptr_list((struct ptr_list
**)rlist
);
1072 static void free_single_dinfo(struct data_info
*dinfo
)
1074 if (dinfo
->type
== DATA_RANGE
)
1075 free_range_list(&dinfo
->value_ranges
);
1078 static void free_dinfos(struct allocation_blob
*blob
)
1080 unsigned int size
= sizeof(struct data_info
);
1081 unsigned int offset
= 0;
1083 while (offset
< blob
->offset
) {
1084 free_single_dinfo((struct data_info
*)(blob
->data
+ offset
));
1089 void free_data_info_allocs(void)
1091 struct allocator_struct
*desc
= &data_info_allocator
;
1092 struct allocation_blob
*blob
= desc
->blobs
;
1095 desc
->allocations
= 0;
1096 desc
->total_bytes
= 0;
1097 desc
->useful_bytes
= 0;
1098 desc
->freelist
= NULL
;
1100 struct allocation_blob
*next
= blob
->next
;
1102 blob_free(blob
, desc
->chunking
);
1105 clear_data_range_alloc();
1108 struct range_list_sval
*range_list_to_sval(struct range_list
*list
)
1110 struct data_range
*tmp
;
1111 struct data_range_sval
*tmp_sval
;
1112 struct range_list_sval
*ret
= NULL
;
1114 FOR_EACH_PTR(list
, tmp
) {
1115 tmp_sval
= drange_to_drange_sval(tmp
);
1116 add_ptr_list(&ret
, tmp_sval
);
1117 } END_FOR_EACH_PTR(tmp
);
1121 struct range_list
*rl_sval_to_rl(struct range_list_sval
*list
)
1123 struct data_range
*tmp
;
1124 struct data_range_sval
*tmp_sval
;
1125 struct range_list
*ret
= NULL
;
1127 FOR_EACH_PTR(list
, tmp_sval
) {
1128 tmp
= drange_sval_to_drange(tmp_sval
);
1129 add_ptr_list(&ret
, tmp
);
1130 } END_FOR_EACH_PTR(tmp_sval
);