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