isl_point.c

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