nexmon – Blame information for rev 1
?pathlinks?
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 1 | office | 1 | #include <isl_map_private.h> |
| 2 | #include <isl_point_private.h> |
||
| 3 | #include <isl/set.h> |
||
| 4 | #include <isl_sample.h> |
||
| 5 | #include <isl_scan.h> |
||
| 6 | #include <isl/seq.h> |
||
| 7 | #include <isl_space_private.h> |
||
| 8 | |||
| 9 | isl_ctx *isl_point_get_ctx(__isl_keep isl_point *pnt) |
||
| 10 | { |
||
| 11 | return pnt ? isl_space_get_ctx(pnt->dim) : NULL; |
||
| 12 | } |
||
| 13 | |||
| 14 | __isl_give isl_space *isl_point_get_space(__isl_keep isl_point *pnt) |
||
| 15 | { |
||
| 16 | return pnt ? isl_space_copy(pnt->dim) : NULL; |
||
| 17 | } |
||
| 18 | |||
| 19 | __isl_give isl_point *isl_point_alloc(__isl_take isl_space *dim, |
||
| 20 | __isl_take isl_vec *vec) |
||
| 21 | { |
||
| 22 | struct isl_point *pnt; |
||
| 23 | |||
| 24 | if (!dim || !vec) |
||
| 25 | goto error; |
||
| 26 | |||
| 27 | if (vec->size > 1 + isl_space_dim(dim, isl_dim_all)) { |
||
| 28 | vec = isl_vec_cow(vec); |
||
| 29 | if (!vec) |
||
| 30 | goto error; |
||
| 31 | vec->size = 1 + isl_space_dim(dim, isl_dim_all); |
||
| 32 | } |
||
| 33 | |||
| 34 | pnt = isl_alloc_type(dim->ctx, struct isl_point); |
||
| 35 | if (!pnt) |
||
| 36 | goto error; |
||
| 37 | |||
| 38 | pnt->ref = 1; |
||
| 39 | pnt->dim = dim; |
||
| 40 | pnt->vec = vec; |
||
| 41 | |||
| 42 | return pnt; |
||
| 43 | error: |
||
| 44 | isl_space_free(dim); |
||
| 45 | isl_vec_free(vec); |
||
| 46 | return NULL; |
||
| 47 | } |
||
| 48 | |||
| 49 | __isl_give isl_point *isl_point_zero(__isl_take isl_space *dim) |
||
| 50 | { |
||
| 51 | isl_vec *vec; |
||
| 52 | |||
| 53 | if (!dim) |
||
| 54 | return NULL; |
||
| 55 | vec = isl_vec_alloc(dim->ctx, 1 + isl_space_dim(dim, isl_dim_all)); |
||
| 56 | if (!vec) |
||
| 57 | goto error; |
||
| 58 | isl_int_set_si(vec->el[0], 1); |
||
| 59 | isl_seq_clr(vec->el + 1, vec->size - 1); |
||
| 60 | return isl_point_alloc(dim, vec); |
||
| 61 | error: |
||
| 62 | isl_space_free(dim); |
||
| 63 | return NULL; |
||
| 64 | } |
||
| 65 | |||
| 66 | __isl_give isl_point *isl_point_dup(__isl_keep isl_point *pnt) |
||
| 67 | { |
||
| 68 | struct isl_point *pnt2; |
||
| 69 | |||
| 70 | if (!pnt) |
||
| 71 | return NULL; |
||
| 72 | pnt2 = isl_point_alloc(isl_space_copy(pnt->dim), isl_vec_copy(pnt->vec)); |
||
| 73 | return pnt2; |
||
| 74 | } |
||
| 75 | |||
| 76 | __isl_give isl_point *isl_point_cow(__isl_take isl_point *pnt) |
||
| 77 | { |
||
| 78 | struct isl_point *pnt2; |
||
| 79 | if (!pnt) |
||
| 80 | return NULL; |
||
| 81 | |||
| 82 | if (pnt->ref == 1) |
||
| 83 | return pnt; |
||
| 84 | |||
| 85 | pnt2 = isl_point_dup(pnt); |
||
| 86 | isl_point_free(pnt); |
||
| 87 | return pnt2; |
||
| 88 | } |
||
| 89 | |||
| 90 | __isl_give isl_point *isl_point_copy(__isl_keep isl_point *pnt) |
||
| 91 | { |
||
| 92 | if (!pnt) |
||
| 93 | return NULL; |
||
| 94 | |||
| 95 | pnt->ref++; |
||
| 96 | return pnt; |
||
| 97 | } |
||
| 98 | |||
| 99 | void isl_point_free(__isl_take isl_point *pnt) |
||
| 100 | { |
||
| 101 | if (!pnt) |
||
| 102 | return; |
||
| 103 | |||
| 104 | if (--pnt->ref > 0) |
||
| 105 | return; |
||
| 106 | |||
| 107 | isl_space_free(pnt->dim); |
||
| 108 | isl_vec_free(pnt->vec); |
||
| 109 | free(pnt); |
||
| 110 | } |
||
| 111 | |||
| 112 | __isl_give isl_point *isl_point_void(__isl_take isl_space *dim) |
||
| 113 | { |
||
| 114 | if (!dim) |
||
| 115 | return NULL; |
||
| 116 | |||
| 117 | return isl_point_alloc(dim, isl_vec_alloc(dim->ctx, 0)); |
||
| 118 | } |
||
| 119 | |||
| 120 | int isl_point_is_void(__isl_keep isl_point *pnt) |
||
| 121 | { |
||
| 122 | if (!pnt) |
||
| 123 | return -1; |
||
| 124 | |||
| 125 | return pnt->vec->size == 0; |
||
| 126 | } |
||
| 127 | |||
| 128 | int isl_point_get_coordinate(__isl_keep isl_point *pnt, |
||
| 129 | enum isl_dim_type type, int pos, isl_int *v) |
||
| 130 | { |
||
| 131 | if (!pnt || isl_point_is_void(pnt)) |
||
| 132 | return -1; |
||
| 133 | |||
| 134 | if (pos < 0 || pos >= isl_space_dim(pnt->dim, type)) |
||
| 135 | isl_die(isl_point_get_ctx(pnt), isl_error_invalid, |
||
| 136 | "position out of bounds", return -1); |
||
| 137 | |||
| 138 | if (type == isl_dim_set) |
||
| 139 | pos += isl_space_dim(pnt->dim, isl_dim_param); |
||
| 140 | isl_int_set(*v, pnt->vec->el[1 + pos]); |
||
| 141 | |||
| 142 | return 0; |
||
| 143 | } |
||
| 144 | |||
| 145 | __isl_give isl_point *isl_point_set_coordinate(__isl_take isl_point *pnt, |
||
| 146 | enum isl_dim_type type, int pos, isl_int v) |
||
| 147 | { |
||
| 148 | if (!pnt || isl_point_is_void(pnt)) |
||
| 149 | return pnt; |
||
| 150 | |||
| 151 | pnt = isl_point_cow(pnt); |
||
| 152 | if (!pnt) |
||
| 153 | return NULL; |
||
| 154 | pnt->vec = isl_vec_cow(pnt->vec); |
||
| 155 | if (!pnt->vec) |
||
| 156 | goto error; |
||
| 157 | |||
| 158 | if (type == isl_dim_set) |
||
| 159 | pos += isl_space_dim(pnt->dim, isl_dim_param); |
||
| 160 | |||
| 161 | isl_int_set(pnt->vec->el[1 + pos], v); |
||
| 162 | |||
| 163 | return pnt; |
||
| 164 | error: |
||
| 165 | isl_point_free(pnt); |
||
| 166 | return NULL; |
||
| 167 | } |
||
| 168 | |||
| 169 | __isl_give isl_point *isl_point_add_ui(__isl_take isl_point *pnt, |
||
| 170 | enum isl_dim_type type, int pos, unsigned val) |
||
| 171 | { |
||
| 172 | if (!pnt || isl_point_is_void(pnt)) |
||
| 173 | return pnt; |
||
| 174 | |||
| 175 | pnt = isl_point_cow(pnt); |
||
| 176 | if (!pnt) |
||
| 177 | return NULL; |
||
| 178 | pnt->vec = isl_vec_cow(pnt->vec); |
||
| 179 | if (!pnt->vec) |
||
| 180 | goto error; |
||
| 181 | |||
| 182 | if (type == isl_dim_set) |
||
| 183 | pos += isl_space_dim(pnt->dim, isl_dim_param); |
||
| 184 | |||
| 185 | isl_int_add_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val); |
||
| 186 | |||
| 187 | return pnt; |
||
| 188 | error: |
||
| 189 | isl_point_free(pnt); |
||
| 190 | return NULL; |
||
| 191 | } |
||
| 192 | |||
| 193 | __isl_give isl_point *isl_point_sub_ui(__isl_take isl_point *pnt, |
||
| 194 | enum isl_dim_type type, int pos, unsigned val) |
||
| 195 | { |
||
| 196 | if (!pnt || isl_point_is_void(pnt)) |
||
| 197 | return pnt; |
||
| 198 | |||
| 199 | pnt = isl_point_cow(pnt); |
||
| 200 | if (!pnt) |
||
| 201 | return NULL; |
||
| 202 | pnt->vec = isl_vec_cow(pnt->vec); |
||
| 203 | if (!pnt->vec) |
||
| 204 | goto error; |
||
| 205 | |||
| 206 | if (type == isl_dim_set) |
||
| 207 | pos += isl_space_dim(pnt->dim, isl_dim_param); |
||
| 208 | |||
| 209 | isl_int_sub_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val); |
||
| 210 | |||
| 211 | return pnt; |
||
| 212 | error: |
||
| 213 | isl_point_free(pnt); |
||
| 214 | return NULL; |
||
| 215 | } |
||
| 216 | |||
| 217 | struct isl_foreach_point { |
||
| 218 | struct isl_scan_callback callback; |
||
| 219 | int (*fn)(__isl_take isl_point *pnt, void *user); |
||
| 220 | void *user; |
||
| 221 | isl_space *dim; |
||
| 222 | }; |
||
| 223 | |||
| 224 | static int foreach_point(struct isl_scan_callback *cb, __isl_take isl_vec *sample) |
||
| 225 | { |
||
| 226 | struct isl_foreach_point *fp = (struct isl_foreach_point *)cb; |
||
| 227 | isl_point *pnt; |
||
| 228 | |||
| 229 | pnt = isl_point_alloc(isl_space_copy(fp->dim), sample); |
||
| 230 | |||
| 231 | return fp->fn(pnt, fp->user); |
||
| 232 | } |
||
| 233 | |||
| 234 | int isl_set_foreach_point(__isl_keep isl_set *set, |
||
| 235 | int (*fn)(__isl_take isl_point *pnt, void *user), void *user) |
||
| 236 | { |
||
| 237 | struct isl_foreach_point fp = { { &foreach_point }, fn, user }; |
||
| 238 | int i; |
||
| 239 | |||
| 240 | if (!set) |
||
| 241 | return -1; |
||
| 242 | |||
| 243 | fp.dim = isl_set_get_space(set); |
||
| 244 | if (!fp.dim) |
||
| 245 | return -1; |
||
| 246 | |||
| 247 | set = isl_set_copy(set); |
||
| 248 | set = isl_set_cow(set); |
||
| 249 | set = isl_set_make_disjoint(set); |
||
| 250 | set = isl_set_compute_divs(set); |
||
| 251 | if (!set) |
||
| 252 | goto error; |
||
| 253 | |||
| 254 | for (i = 0; i < set->n; ++i) |
||
| 255 | if (isl_basic_set_scan(isl_basic_set_copy(set->p[i]), |
||
| 256 | &fp.callback) < 0) |
||
| 257 | goto error; |
||
| 258 | |||
| 259 | isl_set_free(set); |
||
| 260 | isl_space_free(fp.dim); |
||
| 261 | |||
| 262 | return 0; |
||
| 263 | error: |
||
| 264 | isl_set_free(set); |
||
| 265 | isl_space_free(fp.dim); |
||
| 266 | return -1; |
||
| 267 | } |
||
| 268 | |||
| 269 | /* Return 1 if "bmap" contains the point "point". |
||
| 270 | * "bmap" is assumed to have known divs. |
||
| 271 | * The point is first extended with the divs and then passed |
||
| 272 | * to basic_map_contains. |
||
| 273 | */ |
||
| 274 | int isl_basic_map_contains_point(__isl_keep isl_basic_map *bmap, |
||
| 275 | __isl_keep isl_point *point) |
||
| 276 | { |
||
| 277 | int i; |
||
| 278 | struct isl_vec *vec; |
||
| 279 | unsigned dim; |
||
| 280 | int contains; |
||
| 281 | |||
| 282 | if (!bmap || !point) |
||
| 283 | return -1; |
||
| 284 | isl_assert(bmap->ctx, isl_space_is_equal(bmap->dim, point->dim), return -1); |
||
| 285 | if (bmap->n_div == 0) |
||
| 286 | return isl_basic_map_contains(bmap, point->vec); |
||
| 287 | |||
| 288 | dim = isl_basic_map_total_dim(bmap) - bmap->n_div; |
||
| 289 | vec = isl_vec_alloc(bmap->ctx, 1 + dim + bmap->n_div); |
||
| 290 | if (!vec) |
||
| 291 | return -1; |
||
| 292 | |||
| 293 | isl_seq_cpy(vec->el, point->vec->el, point->vec->size); |
||
| 294 | for (i = 0; i < bmap->n_div; ++i) { |
||
| 295 | isl_seq_inner_product(bmap->div[i] + 1, vec->el, |
||
| 296 | 1 + dim + i, &vec->el[1+dim+i]); |
||
| 297 | isl_int_fdiv_q(vec->el[1+dim+i], vec->el[1+dim+i], |
||
| 298 | bmap->div[i][0]); |
||
| 299 | } |
||
| 300 | |||
| 301 | contains = isl_basic_map_contains(bmap, vec); |
||
| 302 | |||
| 303 | isl_vec_free(vec); |
||
| 304 | return contains; |
||
| 305 | } |
||
| 306 | |||
| 307 | int isl_map_contains_point(__isl_keep isl_map *map, __isl_keep isl_point *point) |
||
| 308 | { |
||
| 309 | int i; |
||
| 310 | int found = 0; |
||
| 311 | |||
| 312 | if (!map || !point) |
||
| 313 | return -1; |
||
| 314 | |||
| 315 | map = isl_map_copy(map); |
||
| 316 | map = isl_map_compute_divs(map); |
||
| 317 | if (!map) |
||
| 318 | return -1; |
||
| 319 | |||
| 320 | for (i = 0; i < map->n; ++i) { |
||
| 321 | found = isl_basic_map_contains_point(map->p[i], point); |
||
| 322 | if (found < 0) |
||
| 323 | goto error; |
||
| 324 | if (found) |
||
| 325 | break; |
||
| 326 | } |
||
| 327 | isl_map_free(map); |
||
| 328 | |||
| 329 | return found; |
||
| 330 | error: |
||
| 331 | isl_map_free(map); |
||
| 332 | return -1; |
||
| 333 | } |
||
| 334 | |||
| 335 | int isl_set_contains_point(__isl_keep isl_set *set, __isl_keep isl_point *point) |
||
| 336 | { |
||
| 337 | return isl_map_contains_point((isl_map *)set, point); |
||
| 338 | } |
||
| 339 | |||
| 340 | __isl_give isl_basic_set *isl_basic_set_from_point(__isl_take isl_point *pnt) |
||
| 341 | { |
||
| 342 | isl_basic_set *bset; |
||
| 343 | isl_basic_set *model; |
||
| 344 | |||
| 345 | model = isl_basic_set_empty(isl_space_copy(pnt->dim)); |
||
| 346 | bset = isl_basic_set_from_vec(isl_vec_copy(pnt->vec)); |
||
| 347 | bset = isl_basic_set_from_underlying_set(bset, model); |
||
| 348 | isl_point_free(pnt); |
||
| 349 | |||
| 350 | return bset; |
||
| 351 | } |
||
| 352 | |||
| 353 | __isl_give isl_set *isl_set_from_point(__isl_take isl_point *pnt) |
||
| 354 | { |
||
| 355 | isl_basic_set *bset; |
||
| 356 | bset = isl_basic_set_from_point(pnt); |
||
| 357 | return isl_set_from_basic_set(bset); |
||
| 358 | } |
||
| 359 | |||
| 360 | __isl_give isl_basic_set *isl_basic_set_box_from_points( |
||
| 361 | __isl_take isl_point *pnt1, __isl_take isl_point *pnt2) |
||
| 362 | { |
||
| 363 | isl_basic_set *bset; |
||
| 364 | unsigned total; |
||
| 365 | int i; |
||
| 366 | int k; |
||
| 367 | isl_int t; |
||
| 368 | |||
| 369 | isl_int_init(t); |
||
| 370 | |||
| 371 | if (!pnt1 || !pnt2) |
||
| 372 | goto error; |
||
| 373 | |||
| 374 | isl_assert(pnt1->dim->ctx, |
||
| 375 | isl_space_is_equal(pnt1->dim, pnt2->dim), goto error); |
||
| 376 | |||
| 377 | if (isl_point_is_void(pnt1) && isl_point_is_void(pnt2)) { |
||
| 378 | isl_space *dim = isl_space_copy(pnt1->dim); |
||
| 379 | isl_point_free(pnt1); |
||
| 380 | isl_point_free(pnt2); |
||
| 381 | isl_int_clear(t); |
||
| 382 | return isl_basic_set_empty(dim); |
||
| 383 | } |
||
| 384 | if (isl_point_is_void(pnt1)) { |
||
| 385 | isl_point_free(pnt1); |
||
| 386 | isl_int_clear(t); |
||
| 387 | return isl_basic_set_from_point(pnt2); |
||
| 388 | } |
||
| 389 | if (isl_point_is_void(pnt2)) { |
||
| 390 | isl_point_free(pnt2); |
||
| 391 | isl_int_clear(t); |
||
| 392 | return isl_basic_set_from_point(pnt1); |
||
| 393 | } |
||
| 394 | |||
| 395 | total = isl_space_dim(pnt1->dim, isl_dim_all); |
||
| 396 | bset = isl_basic_set_alloc_space(isl_space_copy(pnt1->dim), 0, 0, 2 * total); |
||
| 397 | |||
| 398 | for (i = 0; i < total; ++i) { |
||
| 399 | isl_int_mul(t, pnt1->vec->el[1 + i], pnt2->vec->el[0]); |
||
| 400 | isl_int_submul(t, pnt2->vec->el[1 + i], pnt1->vec->el[0]); |
||
| 401 | |||
| 402 | k = isl_basic_set_alloc_inequality(bset); |
||
| 403 | if (k < 0) |
||
| 404 | goto error; |
||
| 405 | isl_seq_clr(bset->ineq[k] + 1, total); |
||
| 406 | if (isl_int_is_pos(t)) { |
||
| 407 | isl_int_set_si(bset->ineq[k][1 + i], -1); |
||
| 408 | isl_int_set(bset->ineq[k][0], pnt1->vec->el[1 + i]); |
||
| 409 | } else { |
||
| 410 | isl_int_set_si(bset->ineq[k][1 + i], 1); |
||
| 411 | isl_int_neg(bset->ineq[k][0], pnt1->vec->el[1 + i]); |
||
| 412 | } |
||
| 413 | isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt1->vec->el[0]); |
||
| 414 | |||
| 415 | k = isl_basic_set_alloc_inequality(bset); |
||
| 416 | if (k < 0) |
||
| 417 | goto error; |
||
| 418 | isl_seq_clr(bset->ineq[k] + 1, total); |
||
| 419 | if (isl_int_is_pos(t)) { |
||
| 420 | isl_int_set_si(bset->ineq[k][1 + i], 1); |
||
| 421 | isl_int_neg(bset->ineq[k][0], pnt2->vec->el[1 + i]); |
||
| 422 | } else { |
||
| 423 | isl_int_set_si(bset->ineq[k][1 + i], -1); |
||
| 424 | isl_int_set(bset->ineq[k][0], pnt2->vec->el[1 + i]); |
||
| 425 | } |
||
| 426 | isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt2->vec->el[0]); |
||
| 427 | } |
||
| 428 | |||
| 429 | bset = isl_basic_set_finalize(bset); |
||
| 430 | |||
| 431 | isl_point_free(pnt1); |
||
| 432 | isl_point_free(pnt2); |
||
| 433 | |||
| 434 | isl_int_clear(t); |
||
| 435 | |||
| 436 | return bset; |
||
| 437 | error: |
||
| 438 | isl_point_free(pnt1); |
||
| 439 | isl_point_free(pnt2); |
||
| 440 | isl_int_clear(t); |
||
| 441 | return NULL; |
||
| 442 | } |
||
| 443 | |||
| 444 | __isl_give isl_set *isl_set_box_from_points(__isl_take isl_point *pnt1, |
||
| 445 | __isl_take isl_point *pnt2) |
||
| 446 | { |
||
| 447 | isl_basic_set *bset; |
||
| 448 | bset = isl_basic_set_box_from_points(pnt1, pnt2); |
||
| 449 | return isl_set_from_basic_set(bset); |
||
| 450 | } |
||
| 451 | |||
| 452 | __isl_give isl_printer *isl_printer_print_point( |
||
| 453 | __isl_take isl_printer *p, __isl_keep isl_point *pnt) |
||
| 454 | { |
||
| 455 | int i; |
||
| 456 | unsigned nparam; |
||
| 457 | unsigned dim; |
||
| 458 | |||
| 459 | if (!pnt) |
||
| 460 | return p; |
||
| 461 | if (isl_point_is_void(pnt)) { |
||
| 462 | p = isl_printer_print_str(p, "void"); |
||
| 463 | return p; |
||
| 464 | } |
||
| 465 | |||
| 466 | nparam = isl_space_dim(pnt->dim, isl_dim_param); |
||
| 467 | dim = isl_space_dim(pnt->dim, isl_dim_set); |
||
| 468 | if (nparam > 0) { |
||
| 469 | p = isl_printer_print_str(p, "["); |
||
| 470 | for (i = 0; i < nparam; ++i) { |
||
| 471 | const char *name; |
||
| 472 | if (i) |
||
| 473 | p = isl_printer_print_str(p, ", "); |
||
| 474 | name = isl_space_get_dim_name(pnt->dim, isl_dim_param, i); |
||
| 475 | if (name) { |
||
| 476 | p = isl_printer_print_str(p, name); |
||
| 477 | p = isl_printer_print_str(p, " = "); |
||
| 478 | } |
||
| 479 | p = isl_printer_print_isl_int(p, pnt->vec->el[1 + i]); |
||
| 480 | if (!isl_int_is_one(pnt->vec->el[0])) { |
||
| 481 | p = isl_printer_print_str(p, "/"); |
||
| 482 | p = isl_printer_print_isl_int(p, pnt->vec->el[0]); |
||
| 483 | } |
||
| 484 | } |
||
| 485 | p = isl_printer_print_str(p, "]"); |
||
| 486 | p = isl_printer_print_str(p, " -> "); |
||
| 487 | } |
||
| 488 | p = isl_printer_print_str(p, "["); |
||
| 489 | for (i = 0; i < dim; ++i) { |
||
| 490 | if (i) |
||
| 491 | p = isl_printer_print_str(p, ", "); |
||
| 492 | p = isl_printer_print_isl_int(p, pnt->vec->el[1 + nparam + i]); |
||
| 493 | if (!isl_int_is_one(pnt->vec->el[0])) { |
||
| 494 | p = isl_printer_print_str(p, "/"); |
||
| 495 | p = isl_printer_print_isl_int(p, pnt->vec->el[0]); |
||
| 496 | } |
||
| 497 | } |
||
| 498 | p = isl_printer_print_str(p, "]"); |
||
| 499 | return p; |
||
| 500 | } |