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
);
20 static char *show_num(long long num
)
22 static char buff
[256];
24 if (num
== whole_range
.min
) {
25 snprintf(buff
, 255, "min");
26 } else if (num
== whole_range
.max
) {
27 snprintf(buff
, 255, "max");
29 snprintf(buff
, 255, "(%lld)", num
);
31 snprintf(buff
, 255, "%lld", num
);
37 char *show_ranges(struct range_list
*list
)
39 struct data_range
*tmp
;
45 FOR_EACH_PTR(list
, tmp
) {
47 strncat(full
, ",", 254 - strlen(full
));
48 if (tmp
->min
== tmp
->max
) {
49 strncat(full
, show_num(tmp
->min
), 254 - strlen(full
));
52 strncat(full
, show_num(tmp
->min
), 254 - strlen(full
));
53 strncat(full
, "-", 254 - strlen(full
));
54 strncat(full
, show_num(tmp
->max
), 254 - strlen(full
));
55 } END_FOR_EACH_PTR(tmp
);
56 return alloc_sname(full
);
59 static struct data_range range_zero
= {
64 static struct data_range range_one
= {
69 struct data_range
*alloc_range(long long min
, long long max
)
71 struct data_range
*ret
;
74 printf("Error invalid range %lld to %lld\n", min
, max
);
76 if (min
== whole_range
.min
&& max
== whole_range
.max
)
78 if (min
== 0 && max
== 0)
80 if (min
== 1 && max
== 1)
82 ret
= __alloc_data_range(0);
88 struct data_range
*alloc_range_perm(long long min
, long long max
)
90 struct data_range
*ret
;
93 printf("Error invalid range %lld to %lld\n", min
, max
);
95 if (min
== whole_range
.min
&& max
== whole_range
.max
)
97 if (min
== 0 && max
== 0)
99 if (min
== 1 && max
== 1)
101 ret
= __alloc_perm_data_range(0);
107 void add_range(struct range_list
**list
, long long min
, long long max
)
109 struct data_range
*tmp
= NULL
;
110 struct data_range
*new = NULL
;
113 FOR_EACH_PTR(*list
, tmp
) {
115 /* Sometimes we overlap with more than one range
116 so we have to delete or modify the next range. */
117 if (max
+ 1 == tmp
->min
) {
118 /* join 2 ranges here */
120 DELETE_CURRENT_PTR(tmp
);
124 /* Doesn't overlap with the next one. */
127 /* Partially overlaps with the next one. */
128 if (max
< tmp
->max
) {
132 /* Completely overlaps with the next one. */
133 if (max
>= tmp
->max
) {
134 DELETE_CURRENT_PTR(tmp
);
135 /* there could be more ranges to delete */
139 if (max
!= whole_range
.max
&& max
+ 1 == tmp
->min
) {
140 /* join 2 ranges into a big range */
141 new = alloc_range(min
, tmp
->max
);
142 REPLACE_CURRENT_PTR(tmp
, new);
145 if (max
< tmp
->min
) { /* new range entirely below */
146 new = alloc_range(min
, max
);
147 INSERT_CURRENT(new, tmp
);
150 if (min
< tmp
->min
) { /* new range partially below */
155 new = alloc_range(min
, max
);
156 REPLACE_CURRENT_PTR(tmp
, new);
161 if (max
<= tmp
->max
) /* new range already included */
163 if (min
<= tmp
->max
) { /* new range partially above */
165 new = alloc_range(min
, max
);
166 REPLACE_CURRENT_PTR(tmp
, new);
170 if (min
!= whole_range
.min
&& min
- 1 == tmp
->max
) {
171 /* join 2 ranges into a big range */
172 new = alloc_range(tmp
->min
, max
);
173 REPLACE_CURRENT_PTR(tmp
, new);
177 /* the new range is entirely above the existing ranges */
178 } END_FOR_EACH_PTR(tmp
);
181 new = alloc_range(min
, max
);
182 add_ptr_list(list
, new);
185 struct range_list
*clone_range_list(struct range_list
*list
)
187 struct data_range
*tmp
;
188 struct range_list
*ret
= NULL
;
190 FOR_EACH_PTR(list
, tmp
) {
191 add_ptr_list(&ret
, tmp
);
192 } END_FOR_EACH_PTR(tmp
);
196 struct range_list
*range_list_union(struct range_list
*one
, struct range_list
*two
)
198 struct data_range
*tmp
;
199 struct range_list
*ret
= NULL
;
201 FOR_EACH_PTR(one
, tmp
) {
202 add_range(&ret
, tmp
->min
, tmp
->max
);
203 } END_FOR_EACH_PTR(tmp
);
204 FOR_EACH_PTR(two
, tmp
) {
205 add_range(&ret
, tmp
->min
, tmp
->max
);
206 } END_FOR_EACH_PTR(tmp
);
210 struct range_list
*remove_range(struct range_list
*list
, long long min
, long long max
)
212 struct data_range
*tmp
;
213 struct range_list
*ret
= NULL
;
215 FOR_EACH_PTR(list
, tmp
) {
216 if (tmp
->max
< min
) {
217 add_range(&ret
, tmp
->min
, tmp
->max
);
220 if (tmp
->min
> max
) {
221 add_range(&ret
, tmp
->min
, tmp
->max
);
224 if (tmp
->min
>= min
&& tmp
->max
<= max
)
226 if (tmp
->min
>= min
) {
227 add_range(&ret
, max
+ 1, tmp
->max
);
228 } else if (tmp
->max
<= max
) {
229 add_range(&ret
, tmp
->min
, min
- 1);
231 add_range(&ret
, tmp
->min
, min
- 1);
232 add_range(&ret
, max
+ 1, tmp
->max
);
234 } END_FOR_EACH_PTR(tmp
);
238 long long get_dinfo_min(struct data_info
*dinfo
)
240 struct data_range
*drange
;
242 if (!dinfo
|| !dinfo
->value_ranges
)
243 return whole_range
.min
;
244 drange
= first_ptr_list((struct ptr_list
*)dinfo
->value_ranges
);
248 long long get_dinfo_max(struct data_info
*dinfo
)
250 struct data_range
*drange
;
252 if (!dinfo
|| !dinfo
->value_ranges
)
253 return whole_range
.max
;
254 drange
= last_ptr_list((struct ptr_list
*)dinfo
->value_ranges
);
259 * if it can be only one and only value return 1, else return 0
261 int get_single_value_from_dinfo(struct data_info
*dinfo
, long long *val
)
263 struct data_range
*tmp
;
266 if (dinfo
->type
!= DATA_RANGE
)
269 FOR_EACH_PTR(dinfo
->value_ranges
, tmp
) {
271 if (tmp
->min
!= tmp
->max
)
277 } END_FOR_EACH_PTR(tmp
);
281 int true_comparison_range(struct data_range
*left
, int comparison
, struct data_range
*right
)
283 switch (comparison
) {
285 case SPECIAL_UNSIGNED_LT
:
286 if (left
->min
< right
->max
)
289 case SPECIAL_UNSIGNED_LTE
:
291 if (left
->min
<= right
->max
)
295 if (left
->max
< right
->min
)
297 if (left
->min
> right
->max
)
300 case SPECIAL_UNSIGNED_GTE
:
302 if (left
->max
>= right
->min
)
306 case SPECIAL_UNSIGNED_GT
:
307 if (left
->max
> right
->min
)
310 case SPECIAL_NOTEQUAL
:
311 if (left
->min
!= left
->max
)
313 if (right
->min
!= right
->max
)
315 if (left
->min
!= right
->min
)
319 sm_msg("unhandled comparison %d\n", comparison
);
325 int true_comparison_range_lr(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
328 return true_comparison_range(var
, comparison
, val
);
330 return true_comparison_range(val
, comparison
, var
);
333 static int false_comparison_range(struct data_range
*left
, int comparison
, struct data_range
*right
)
335 switch (comparison
) {
337 case SPECIAL_UNSIGNED_LT
:
338 if (left
->max
>= right
->min
)
341 case SPECIAL_UNSIGNED_LTE
:
343 if (left
->max
> right
->min
)
347 if (left
->min
!= left
->max
)
349 if (right
->min
!= right
->max
)
351 if (left
->min
!= right
->min
)
354 case SPECIAL_UNSIGNED_GTE
:
356 if (left
->min
< right
->max
)
360 case SPECIAL_UNSIGNED_GT
:
361 if (left
->min
<= right
->max
)
364 case SPECIAL_NOTEQUAL
:
365 if (left
->max
< right
->min
)
367 if (left
->min
> right
->max
)
371 sm_msg("unhandled comparison %d\n", comparison
);
377 int false_comparison_range_lr(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
380 return false_comparison_range(var
, comparison
, val
);
382 return false_comparison_range(val
, comparison
, var
);
385 int possibly_true(int comparison
, struct data_info
*dinfo
, long long num
, int left
)
387 struct data_range
*tmp
;
388 struct data_range drange
;
396 FOR_EACH_PTR(dinfo
->value_ranges
, tmp
) {
397 if (true_comparison_range_lr(comparison
, tmp
, &drange
, left
))
399 } END_FOR_EACH_PTR(tmp
);
403 int possibly_false(int comparison
, struct data_info
*dinfo
, long long num
, int left
)
405 struct data_range
*tmp
;
406 struct data_range drange
;
414 FOR_EACH_PTR(dinfo
->value_ranges
, tmp
) {
415 if (false_comparison_range_lr(comparison
, tmp
, &drange
, left
))
417 } END_FOR_EACH_PTR(tmp
);
421 int possibly_true_range_lists(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
423 struct data_range
*left_tmp
, *right_tmp
;
425 if (!left_ranges
|| !right_ranges
)
428 FOR_EACH_PTR(left_ranges
, left_tmp
) {
429 FOR_EACH_PTR(right_ranges
, right_tmp
) {
430 if (true_comparison_range(left_tmp
, comparison
, right_tmp
))
432 } END_FOR_EACH_PTR(right_tmp
);
433 } END_FOR_EACH_PTR(left_tmp
);
437 int possibly_true_range_list_lr(int comparison
, struct data_info
*dinfo
, struct range_list
*values
, int left
)
439 struct data_range
*tmp
, *tmp2
;
441 FOR_EACH_PTR(dinfo
->value_ranges
, tmp
) {
442 FOR_EACH_PTR(values
, tmp2
) {
443 if (true_comparison_range_lr(comparison
, tmp
, tmp2
, left
))
445 } END_FOR_EACH_PTR(tmp2
);
446 } END_FOR_EACH_PTR(tmp
);
450 int possibly_false_range_lists(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
452 struct data_range
*left_tmp
, *right_tmp
;
454 if (!left_ranges
|| !right_ranges
)
457 FOR_EACH_PTR(left_ranges
, left_tmp
) {
458 FOR_EACH_PTR(right_ranges
, right_tmp
) {
459 if (false_comparison_range(left_tmp
, comparison
, right_tmp
))
461 } END_FOR_EACH_PTR(right_tmp
);
462 } END_FOR_EACH_PTR(left_tmp
);
466 int possibly_false_range_list_lr(int comparison
, struct data_info
*dinfo
, struct range_list
*values
, int left
)
468 struct data_range
*tmp
, *tmp2
;
470 FOR_EACH_PTR(dinfo
->value_ranges
, tmp
) {
471 FOR_EACH_PTR(values
, tmp2
) {
472 if (false_comparison_range_lr(comparison
, tmp
, tmp2
, left
))
474 } END_FOR_EACH_PTR(tmp2
);
475 } END_FOR_EACH_PTR(tmp
);
479 void tack_on(struct range_list
**list
, struct data_range
*drange
)
481 add_ptr_list(list
, drange
);
484 int in_list_exact(struct range_list
*list
, struct data_range
*drange
)
486 struct data_range
*tmp
;
488 FOR_EACH_PTR(list
, tmp
) {
489 if (tmp
->min
== drange
->min
&& tmp
->max
== drange
->max
)
491 } END_FOR_EACH_PTR(tmp
);
496 void push_range_list(struct range_list_stack
**rl_stack
, struct range_list
*rl
)
498 add_ptr_list(rl_stack
, rl
);
501 struct range_list
*pop_range_list(struct range_list_stack
**rl_stack
)
503 struct range_list
*rl
;
505 rl
= last_ptr_list((struct ptr_list
*)*rl_stack
);
506 delete_ptr_list_last((struct ptr_list
**)rl_stack
);
510 struct range_list
*top_range_list(struct range_list_stack
*rl_stack
)
512 struct range_list
*rl
;
514 rl
= last_ptr_list((struct ptr_list
*)rl_stack
);
518 void filter_top_range_list(struct range_list_stack
**rl_stack
, long long num
)
520 struct range_list
*rl
;
522 rl
= pop_range_list(rl_stack
);
523 rl
= remove_range(rl
, num
, num
);
524 push_range_list(rl_stack
, rl
);
527 void free_range_list(struct range_list
**rlist
)
529 __free_ptr_list((struct ptr_list
**)rlist
);
532 static void free_single_dinfo(struct data_info
*dinfo
)
534 if (dinfo
->type
== DATA_RANGE
)
535 free_range_list(&dinfo
->value_ranges
);
538 static void free_dinfos(struct allocation_blob
*blob
)
540 unsigned int size
= sizeof(struct data_info
);
541 unsigned int offset
= 0;
543 while (offset
< blob
->offset
) {
544 free_single_dinfo((struct data_info
*)(blob
->data
+ offset
));
549 void free_data_info_allocs(void)
551 struct allocator_struct
*desc
= &data_info_allocator
;
552 struct allocation_blob
*blob
= desc
->blobs
;
555 desc
->allocations
= 0;
556 desc
->total_bytes
= 0;
557 desc
->useful_bytes
= 0;
558 desc
->freelist
= NULL
;
560 struct allocation_blob
*next
= blob
->next
;
562 blob_free(blob
, desc
->chunking
);
565 clear_data_range_alloc();