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(struct range_list
*one
, struct range_list
*two
)
728 struct data_range
*one_range
;
729 struct data_range
*two_range
;
731 PREPARE_PTR_LIST(one
, one_range
);
732 PREPARE_PTR_LIST(two
, two_range
);
734 if (!one_range
&& !two_range
)
736 if (!one_range
|| !two_range
)
738 if (one_range
->min
!= two_range
->min
)
740 if (one_range
->max
!= two_range
->max
)
742 NEXT_PTR_LIST(one_range
);
743 NEXT_PTR_LIST(two_range
);
745 FINISH_PTR_LIST(two_range
);
746 FINISH_PTR_LIST(one_range
);
751 int true_comparison_range(struct data_range
*left
, int comparison
, struct data_range
*right
)
753 struct data_range_sval
*tmp_left
, *tmp_right
;
755 tmp_left
= drange_to_drange_sval(left
);
756 tmp_right
= drange_to_drange_sval(right
);
757 return true_comparison_range_sval(tmp_left
, comparison
, tmp_right
);
760 int true_comparison_range_sval(struct data_range_sval
*left
, int comparison
, struct data_range_sval
*right
)
762 switch (comparison
) {
764 case SPECIAL_UNSIGNED_LT
:
765 if (sval_cmp(left
->min
, right
->max
) < 0)
768 case SPECIAL_UNSIGNED_LTE
:
770 if (sval_cmp(left
->min
, right
->max
) <= 0)
774 if (sval_cmp(left
->max
, right
->min
) < 0)
776 if (sval_cmp(left
->min
, right
->max
) > 0)
779 case SPECIAL_UNSIGNED_GTE
:
781 if (sval_cmp(left
->max
, right
->min
) >= 0)
785 case SPECIAL_UNSIGNED_GT
:
786 if (sval_cmp(left
->max
, right
->min
) > 0)
789 case SPECIAL_NOTEQUAL
:
790 if (sval_cmp(left
->min
, left
->max
) != 0)
792 if (sval_cmp(right
->min
, right
->max
) != 0)
794 if (sval_cmp(left
->min
, right
->min
) != 0)
798 sm_msg("unhandled comparison %d\n", comparison
);
804 int true_comparison_range_lr(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
807 return true_comparison_range(var
, comparison
, val
);
809 return true_comparison_range(val
, comparison
, var
);
812 int true_comparison_range_lr_sval(int comparison
, struct data_range_sval
*var
, struct data_range_sval
*val
, int left
)
815 return true_comparison_range_sval(var
, comparison
, val
);
817 return true_comparison_range_sval(val
, comparison
, var
);
820 static int false_comparison_range_sval(struct data_range_sval
*left
, int comparison
, struct data_range_sval
*right
)
822 switch (comparison
) {
824 case SPECIAL_UNSIGNED_LT
:
825 if (sval_cmp(left
->max
, right
->min
) >= 0)
828 case SPECIAL_UNSIGNED_LTE
:
830 if (sval_cmp(left
->max
, right
->min
) > 0)
834 if (sval_cmp(left
->min
, left
->max
) != 0)
836 if (sval_cmp(right
->min
, right
->max
) != 0)
838 if (sval_cmp(left
->min
, right
->min
) != 0)
841 case SPECIAL_UNSIGNED_GTE
:
843 if (sval_cmp(left
->min
, right
->max
) < 0)
847 case SPECIAL_UNSIGNED_GT
:
848 if (sval_cmp(left
->min
, right
->max
) <= 0)
851 case SPECIAL_NOTEQUAL
:
852 if (sval_cmp(left
->max
, right
->min
) < 0)
854 if (sval_cmp(left
->min
, right
->max
) > 0)
858 sm_msg("unhandled comparison %d\n", comparison
);
864 static int false_comparison_range(struct data_range
*left
, int comparison
, struct data_range
*right
)
866 struct data_range_sval
*tmp_left
, *tmp_right
;
868 tmp_left
= drange_to_drange_sval(left
);
869 tmp_right
= drange_to_drange_sval(right
);
870 return false_comparison_range_sval(tmp_left
, comparison
, tmp_right
);
873 int false_comparison_range_lr(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
876 return false_comparison_range(var
, comparison
, val
);
878 return false_comparison_range(val
, comparison
, var
);
881 int false_comparison_range_lr_sval(int comparison
, struct data_range_sval
*var
, struct data_range_sval
*val
, int left
)
884 return false_comparison_range_sval(var
, comparison
, val
);
886 return false_comparison_range_sval(val
, comparison
, var
);
889 int possibly_true(struct expression
*left
, int comparison
, struct expression
*right
)
891 struct range_list
*rl_left
, *rl_right
;
892 struct data_range
*tmp_left
, *tmp_right
;
894 if (!get_implied_range_list(left
, &rl_left
))
896 if (!get_implied_range_list(right
, &rl_right
))
899 FOR_EACH_PTR(rl_left
, tmp_left
) {
900 FOR_EACH_PTR(rl_right
, tmp_right
) {
901 if (true_comparison_range(tmp_left
, comparison
, tmp_right
))
903 } END_FOR_EACH_PTR(tmp_right
);
904 } END_FOR_EACH_PTR(tmp_left
);
908 int possibly_false(struct expression
*left
, int comparison
, struct expression
*right
)
910 struct range_list
*rl_left
, *rl_right
;
911 struct data_range
*tmp_left
, *tmp_right
;
913 if (!get_implied_range_list(left
, &rl_left
))
915 if (!get_implied_range_list(right
, &rl_right
))
918 FOR_EACH_PTR(rl_left
, tmp_left
) {
919 FOR_EACH_PTR(rl_right
, tmp_right
) {
920 if (false_comparison_range(tmp_left
, comparison
, tmp_right
))
922 } END_FOR_EACH_PTR(tmp_right
);
923 } END_FOR_EACH_PTR(tmp_left
);
927 int possibly_true_range_lists(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
929 struct data_range
*left_tmp
, *right_tmp
;
931 if (!left_ranges
|| !right_ranges
)
934 FOR_EACH_PTR(left_ranges
, left_tmp
) {
935 FOR_EACH_PTR(right_ranges
, right_tmp
) {
936 if (true_comparison_range(left_tmp
, comparison
, right_tmp
))
938 } END_FOR_EACH_PTR(right_tmp
);
939 } END_FOR_EACH_PTR(left_tmp
);
943 int possibly_true_range_lists_sval(struct range_list_sval
*left_ranges
, int comparison
, struct range_list_sval
*right_ranges
)
945 struct data_range_sval
*left_tmp
, *right_tmp
;
947 if (!left_ranges
|| !right_ranges
)
950 FOR_EACH_PTR(left_ranges
, left_tmp
) {
951 FOR_EACH_PTR(right_ranges
, right_tmp
) {
952 if (true_comparison_range_sval(left_tmp
, comparison
, right_tmp
))
954 } END_FOR_EACH_PTR(right_tmp
);
955 } END_FOR_EACH_PTR(left_tmp
);
959 int possibly_false_range_lists(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
961 struct data_range
*left_tmp
, *right_tmp
;
963 if (!left_ranges
|| !right_ranges
)
966 FOR_EACH_PTR(left_ranges
, left_tmp
) {
967 FOR_EACH_PTR(right_ranges
, right_tmp
) {
968 if (false_comparison_range(left_tmp
, comparison
, right_tmp
))
970 } END_FOR_EACH_PTR(right_tmp
);
971 } END_FOR_EACH_PTR(left_tmp
);
975 int possibly_false_range_lists_sval(struct range_list_sval
*left_ranges
, int comparison
, struct range_list_sval
*right_ranges
)
977 struct data_range_sval
*left_tmp
, *right_tmp
;
979 if (!left_ranges
|| !right_ranges
)
982 FOR_EACH_PTR(left_ranges
, left_tmp
) {
983 FOR_EACH_PTR(right_ranges
, right_tmp
) {
984 if (false_comparison_range_sval(left_tmp
, comparison
, right_tmp
))
986 } END_FOR_EACH_PTR(right_tmp
);
987 } END_FOR_EACH_PTR(left_tmp
);
991 int possibly_true_range_lists_rl(int comparison
, struct range_list
*a
, struct range_list
*b
, int left
)
994 return possibly_true_range_lists(a
, comparison
, b
);
996 return possibly_true_range_lists(b
, comparison
, a
);
999 /* FIXME: the _rl here stands for right left so really it should be _lr */
1000 int possibly_true_range_lists_rl_sval(int comparison
, struct range_list_sval
*a
, struct range_list_sval
*b
, int left
)
1003 return possibly_true_range_lists_sval(a
, comparison
, b
);
1005 return possibly_true_range_lists_sval(b
, comparison
, a
);
1008 int possibly_false_range_lists_rl(int comparison
, struct range_list
*a
, struct range_list
*b
, int left
)
1011 return possibly_false_range_lists(a
, comparison
, b
);
1013 return possibly_false_range_lists(b
, comparison
, a
);
1016 int possibly_false_range_lists_rl_sval(int comparison
, struct range_list_sval
*a
, struct range_list_sval
*b
, int left
)
1019 return possibly_false_range_lists_sval(a
, comparison
, b
);
1021 return possibly_false_range_lists_sval(b
, comparison
, a
);
1024 void tack_on(struct range_list
**list
, struct data_range
*drange
)
1026 add_ptr_list(list
, drange
);
1029 void tack_on_sval(struct range_list_sval
**list
, struct data_range_sval
*drange
)
1031 add_ptr_list(list
, drange
);
1034 void push_range_list(struct range_list_stack
**rl_stack
, struct range_list
*rl
)
1036 add_ptr_list(rl_stack
, rl
);
1039 void push_range_list_sval(struct range_list_stack_sval
**rl_stack
, struct range_list_sval
*rl
)
1041 add_ptr_list(rl_stack
, rl
);
1044 struct range_list
*pop_range_list(struct range_list_stack
**rl_stack
)
1046 struct range_list
*rl
;
1048 rl
= last_ptr_list((struct ptr_list
*)*rl_stack
);
1049 delete_ptr_list_last((struct ptr_list
**)rl_stack
);
1053 struct range_list_sval
*pop_range_list_sval(struct range_list_stack_sval
**rl_stack
)
1055 struct range_list_sval
*rl
;
1057 rl
= last_ptr_list((struct ptr_list
*)*rl_stack
);
1058 delete_ptr_list_last((struct ptr_list
**)rl_stack
);
1062 struct range_list
*top_range_list(struct range_list_stack
*rl_stack
)
1064 struct range_list
*rl
;
1066 rl
= last_ptr_list((struct ptr_list
*)rl_stack
);
1070 struct range_list_sval
*top_range_list_sval(struct range_list_stack_sval
*rl_stack
)
1072 struct range_list_sval
*rl
;
1074 rl
= last_ptr_list((struct ptr_list
*)rl_stack
);
1078 void filter_top_range_list(struct range_list_stack
**rl_stack
, long long num
)
1080 struct range_list
*rl
;
1082 rl
= pop_range_list(rl_stack
);
1083 rl
= remove_range(rl
, num
, num
);
1084 push_range_list(rl_stack
, rl
);
1087 void filter_top_range_list_sval(struct range_list_stack_sval
**rl_stack
, sval_t sval
)
1089 struct range_list_sval
*rl
;
1091 rl
= pop_range_list_sval(rl_stack
);
1092 rl
= remove_range_sval(rl
, sval
, sval
);
1093 push_range_list_sval(rl_stack
, rl
);
1096 void free_range_list(struct range_list
**rlist
)
1098 __free_ptr_list((struct ptr_list
**)rlist
);
1101 void free_range_list_sval(struct range_list_sval
**rlist
)
1103 __free_ptr_list((struct ptr_list
**)rlist
);
1106 static void free_single_dinfo(struct data_info
*dinfo
)
1108 if (dinfo
->type
== DATA_RANGE
)
1109 free_range_list(&dinfo
->value_ranges
);
1112 static void free_dinfos(struct allocation_blob
*blob
)
1114 unsigned int size
= sizeof(struct data_info
);
1115 unsigned int offset
= 0;
1117 while (offset
< blob
->offset
) {
1118 free_single_dinfo((struct data_info
*)(blob
->data
+ offset
));
1123 void free_data_info_allocs(void)
1125 struct allocator_struct
*desc
= &data_info_allocator
;
1126 struct allocation_blob
*blob
= desc
->blobs
;
1129 desc
->allocations
= 0;
1130 desc
->total_bytes
= 0;
1131 desc
->useful_bytes
= 0;
1132 desc
->freelist
= NULL
;
1134 struct allocation_blob
*next
= blob
->next
;
1136 blob_free(blob
, desc
->chunking
);
1139 clear_data_range_alloc();
1142 struct range_list_sval
*range_list_to_sval(struct range_list
*list
)
1144 struct data_range
*tmp
;
1145 struct data_range_sval
*tmp_sval
;
1146 struct range_list_sval
*ret
= NULL
;
1148 FOR_EACH_PTR(list
, tmp
) {
1149 tmp_sval
= drange_to_drange_sval(tmp
);
1150 add_ptr_list(&ret
, tmp_sval
);
1151 } END_FOR_EACH_PTR(tmp
);
1155 struct range_list
*rl_sval_to_rl(struct range_list_sval
*list
)
1157 struct data_range
*tmp
;
1158 struct data_range_sval
*tmp_sval
;
1159 struct range_list
*ret
= NULL
;
1161 FOR_EACH_PTR(list
, tmp_sval
) {
1162 tmp
= drange_sval_to_drange(tmp_sval
);
1163 add_ptr_list(&ret
, tmp
);
1164 } END_FOR_EACH_PTR(tmp_sval
);