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