isl_point.c

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