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
   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 }