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
  10 isl_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;
  44 error:
  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);
  62 error:
  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
 100 void 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
 121 int 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
 129 int 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;
 192 error:
 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;
 243 error:
 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;
 268 error:
 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;
 292 error:
 293         isl_point_free(pnt);
 294         return NULL;
 295 }
 296
 297 struct 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
 304 static 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
 314 int 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;
 343 error:
 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  */
 354 int 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
 387 int 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;
 410 error:
 411         isl_map_free(map);
 412         return -1;
 413 }
 414
 415 int 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;
 520 error:
 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 }