smatch_extra_helper.c

   1 /*
   2  * sparse/smatch_extra_helper.c
   3  *
   4  * Copyright (C) 2009 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 #include "parse.h"
  11 #include "smatch.h"
  12 #include "smatch_extra.h"
  13
  14 ALLOCATOR(data_info, "smatch extra data");
  15 __DO_ALLOCATOR(long long, sizeof(long long), __alignof__(long long), "numbers", sm_num);
  16
  17 void print_num_list(struct num_list *list)
  18 {
  19         long long *tmp;
  20         int i = 0;
  21
  22         printf("(");
  23         FOR_EACH_PTR(list, tmp) {
  24                 if (i++)
  25                         printf(", ");
  26                 printf("%lld", *tmp);
  27         } END_FOR_EACH_PTR(tmp);
  28         printf(")\n");
  29 }
  30
  31 struct data_info *alloc_data_info(long long num)
  32 {
  33         struct data_info *ret;
  34
  35         ret = __alloc_data_info(0);
  36         ret->type = DATA_NUM;
  37         ret->merged = 0;
  38         ret->values = NULL;
  39         if (num != UNDEFINED)
  40                 add_num(&ret->values, num);
  41         ret->filter = NULL;
  42         return ret;
  43 }
  44
  45 void add_num(struct num_list **list, long long num)
  46 {
  47         long long *tmp;
  48         long long *new;
  49
  50         FOR_EACH_PTR(*list, tmp) {
  51                 if (*tmp < num)
  52                         continue;
  53                 else if (*tmp == num) {
  54                         return;
  55                 } else {
  56                         new = __alloc_sm_num(0);
  57                         *new = num;
  58                         INSERT_CURRENT(new, tmp);
  59                         return;
  60                 }
  61         } END_FOR_EACH_PTR(tmp);
  62         new = __alloc_sm_num(0);
  63         *new = num;
  64         add_ptr_list(list, new);
  65 }
  66
  67 struct num_list *clone_num_list(struct num_list *list)
  68 {
  69         long long *tmp;
  70         struct num_list *ret = NULL;
  71
  72         FOR_EACH_PTR(list, tmp) {
  73                 add_ptr_list(&ret, tmp);
  74         } END_FOR_EACH_PTR(tmp);
  75         return ret;
  76 }
  77
  78 struct num_list *num_list_union(struct num_list *one, struct num_list *two)
  79 {
  80         long long *tmp;
  81         struct num_list *ret = NULL;
  82
  83         if (!one || !two)  /*having nothing in a list means everything is in */
  84                 return NULL;
  85
  86         FOR_EACH_PTR(one, tmp) {
  87                 add_num(&ret, *tmp);
  88         } END_FOR_EACH_PTR(tmp);
  89         FOR_EACH_PTR(two, tmp) {
  90                 add_num(&ret, *tmp);
  91         } END_FOR_EACH_PTR(tmp);
  92         return ret;
  93 }
  94
  95 struct num_list *num_list_intersection(struct num_list *one,
  96                                        struct num_list *two)
  97 {
  98         long long *one_val;
  99         long long *two_val;
 100         struct num_list *ret = NULL;
 101
 102         PREPARE_PTR_LIST(one, one_val);
 103         PREPARE_PTR_LIST(two, two_val);
 104         for (;;) {
 105                 if (!one_val || !two_val)
 106                         break;
 107                 if (*one_val < *two_val) {
 108                         NEXT_PTR_LIST(one_val);
 109                 } else if (*one_val == *two_val) {
 110                         add_ptr_list(&ret, one_val);
 111                         NEXT_PTR_LIST(one_val);
 112                         NEXT_PTR_LIST(two_val);
 113                 } else {
 114                         NEXT_PTR_LIST(two_val);
 115                 }
 116         }
 117         FINISH_PTR_LIST(two_val);
 118         FINISH_PTR_LIST(one_val);
 119         return ret;
 120 }
 121
 122 static int num_in_list(struct num_list *list, long long num)
 123 {
 124         long long *tmp;
 125
 126         FOR_EACH_PTR(list, tmp) {
 127                 if (*tmp == num)
 128                         return 1;
 129         } END_FOR_EACH_PTR(tmp);
 130         return 0;
 131 }
 132
 133 int num_matches(struct data_info *dinfo, long long num)
 134 {
 135         if (num_in_list(dinfo->values, num))
 136                 return 1;
 137         return 0;
 138 }
 139
 140 /*
 141  * if it can be only one value return that, else return UNDEFINED
 142  */
 143 long long get_single_value(struct data_info *dinfo)
 144 {
 145         long long *tmp;
 146         int count = 0;
 147         long long ret = UNDEFINED;
 148
 149         if (dinfo->type != DATA_NUM)
 150                 return UNDEFINED;
 151
 152         FOR_EACH_PTR(dinfo->values, tmp) {
 153                 if (!count++)
 154                         ret = *tmp;
 155                 else
 156                         return UNDEFINED;
 157         } END_FOR_EACH_PTR(tmp);
 158         return ret;
 159 }
 160
 161 int possibly_true(int comparison, struct data_info *dinfo, int num, int left)
 162 {
 163         long long *tmp;
 164         int ret = 0;
 165
 166         if (comparison == SPECIAL_EQUAL && num_in_list(dinfo->filter, num))
 167                 return 0;
 168         if (comparison == SPECIAL_NOTEQUAL && num_in_list(dinfo->filter, num))
 169                 return 1;
 170
 171         if (!dinfo->values)
 172                 return 1;
 173
 174         FOR_EACH_PTR(dinfo->values, tmp) {
 175                 if (left)
 176                         ret = true_comparison(*tmp, comparison, num);
 177                 else
 178                         ret = true_comparison(num,  comparison, *tmp);
 179                 if (ret)
 180                         return ret;
 181         } END_FOR_EACH_PTR(tmp);
 182         return ret;
 183 }
 184
 185 int possibly_false(int comparison, struct data_info *dinfo, int num, int left)
 186 {
 187         long long *tmp;
 188         int ret = 0;
 189
 190         if (comparison == SPECIAL_EQUAL && num_in_list(dinfo->filter, num))
 191                 return 1;
 192
 193         if (comparison == SPECIAL_NOTEQUAL && num_in_list(dinfo->filter, num))
 194                 return 0;
 195
 196         if (!dinfo->values)
 197                 return 1;
 198
 199         FOR_EACH_PTR(dinfo->values, tmp) {
 200                 if (left)
 201                         ret = !true_comparison(*tmp, comparison, num);
 202                 else
 203                         ret = !true_comparison(num,  comparison, *tmp);
 204                 if (ret)
 205                         return ret;
 206         } END_FOR_EACH_PTR(tmp);
 207         return ret;
 208 }
 209
 210 static void free_single_dinfo(struct data_info *dinfo)
 211 {
 212         __free_ptr_list((struct ptr_list **)&dinfo->values);
 213         __free_ptr_list((struct ptr_list **)&dinfo->filter);
 214 }
 215
 216 static void free_dinfos(struct allocation_blob *blob)
 217 {
 218         unsigned int size = sizeof(struct data_info);
 219         unsigned int offset = 0;
 220
 221         while (offset < blob->offset) {
 222                 free_single_dinfo((struct data_info *)(blob->data + offset));
 223                 offset += size;
 224         }
 225 }
 226
 227 void free_data_info_allocs(void)
 228 {
 229         struct allocator_struct *desc = &data_info_allocator;
 230         struct allocation_blob *blob = desc->blobs;
 231
 232         desc->blobs = NULL;
 233         desc->allocations = 0;
 234         desc->total_bytes = 0;
 235         desc->useful_bytes = 0;
 236         desc->freelist = NULL;
 237         while (blob) {
 238                 struct allocation_blob *next = blob->next;
 239                 free_dinfos(blob);
 240                 blob_free(blob, desc->chunking);
 241                 blob = next;
 242         }
 243         clear_sm_num_alloc();
 244 }
 245