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