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