isl_point.c

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