isl_union_map.c

   1 /*
   2  * Copyright 2010-2011 INRIA Saclay
   3  *
   4  * Use of this software is governed by the MIT license
   5  *
   6  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   7  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   8  * 91893 Orsay, France
   9  */
  10
  11 #define ISL_DIM_H
  12 #include <isl_map_private.h>
  13 #include <isl/ctx.h>
  14 #include <isl/hash.h>
  15 #include <isl/map.h>
  16 #include <isl/set.h>
  17 #include <isl_space_private.h>
  18 #include <isl_union_map_private.h>
  19 #include <isl/union_set.h>
  20
  21 /* Is this union set a parameter domain?
  22  */
  23 int isl_union_set_is_params(__isl_keep isl_union_set *uset)
  24 {
  25         isl_set *set;
  26         int params;
  27
  28         if (!uset)
  29                 return -1;
  30         if (uset->table.n != 1)
  31                 return 0;
  32
  33         set = isl_set_from_union_set(isl_union_set_copy(uset));
  34         params = isl_set_is_params(set);
  35         isl_set_free(set);
  36         return params;
  37 }
  38
  39 static __isl_give isl_union_map *isl_union_map_alloc(__isl_take isl_space *dim,
  40         int size)
  41 {
  42         isl_union_map *umap;
  43
  44         dim = isl_space_params(dim);
  45         if (!dim)
  46                 return NULL;
  47
  48         umap = isl_calloc_type(dim->ctx, isl_union_map);
  49         if (!umap)
  50                 return NULL;
  51
  52         umap->ref = 1;
  53         umap->dim = dim;
  54         if (isl_hash_table_init(dim->ctx, &umap->table, size) < 0)
  55                 goto error;
  56
  57         return umap;
  58 error:
  59         isl_space_free(dim);
  60         isl_union_map_free(umap);
  61         return NULL;
  62 }
  63
  64 __isl_give isl_union_map *isl_union_map_empty(__isl_take isl_space *dim)
  65 {
  66         return isl_union_map_alloc(dim, 16);
  67 }
  68
  69 __isl_give isl_union_set *isl_union_set_empty(__isl_take isl_space *dim)
  70 {
  71         return isl_union_map_empty(dim);
  72 }
  73
  74 isl_ctx *isl_union_map_get_ctx(__isl_keep isl_union_map *umap)
  75 {
  76         return umap ? umap->dim->ctx : NULL;
  77 }
  78
  79 isl_ctx *isl_union_set_get_ctx(__isl_keep isl_union_set *uset)
  80 {
  81         return uset ? uset->dim->ctx : NULL;
  82 }
  83
  84 __isl_give isl_space *isl_union_map_get_space(__isl_keep isl_union_map *umap)
  85 {
  86         if (!umap)
  87                 return NULL;
  88         return isl_space_copy(umap->dim);
  89 }
  90
  91 __isl_give isl_space *isl_union_set_get_space(__isl_keep isl_union_set *uset)
  92 {
  93         return isl_union_map_get_space(uset);
  94 }
  95
  96 static int free_umap_entry(void **entry, void *user)
  97 {
  98         isl_map *map = *entry;
  99         isl_map_free(map);
 100         return 0;
 101 }
 102
 103 static int add_map(__isl_take isl_map *map, void *user)
 104 {
 105         isl_union_map **umap = (isl_union_map **)user;
 106
 107         *umap = isl_union_map_add_map(*umap, map);
 108
 109         return 0;
 110 }
 111
 112 __isl_give isl_union_map *isl_union_map_dup(__isl_keep isl_union_map *umap)
 113 {
 114         isl_union_map *dup;
 115
 116         if (!umap)
 117                 return NULL;
 118
 119         dup = isl_union_map_empty(isl_space_copy(umap->dim));
 120         if (isl_union_map_foreach_map(umap, &add_map, &dup) < 0)
 121                 goto error;
 122         return dup;
 123 error:
 124         isl_union_map_free(dup);
 125         return NULL;
 126 }
 127
 128 __isl_give isl_union_map *isl_union_map_cow(__isl_take isl_union_map *umap)
 129 {
 130         if (!umap)
 131                 return NULL;
 132
 133         if (umap->ref == 1)
 134                 return umap;
 135         umap->ref--;
 136         return isl_union_map_dup(umap);
 137 }
 138
 139 struct isl_union_align {
 140         isl_reordering *exp;
 141         isl_union_map *res;
 142 };
 143
 144 static int align_entry(void **entry, void *user)
 145 {
 146         isl_map *map = *entry;
 147         isl_reordering *exp;
 148         struct isl_union_align *data = user;
 149
 150         exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
 151                                     isl_map_get_space(map));
 152
 153         data->res = isl_union_map_add_map(data->res,
 154                                         isl_map_realign(isl_map_copy(map), exp));
 155
 156         return 0;
 157 }
 158
 159 /* Align the parameters of umap along those of model.
 160  * The result has the parameters of model first, in the same order
 161  * as they appear in model, followed by any remaining parameters of
 162  * umap that do not appear in model.
 163  */
 164 __isl_give isl_union_map *isl_union_map_align_params(
 165         __isl_take isl_union_map *umap, __isl_take isl_space *model)
 166 {
 167         struct isl_union_align data = { NULL, NULL };
 168
 169         if (!umap || !model)
 170                 goto error;
 171
 172         if (isl_space_match(umap->dim, isl_dim_param, model, isl_dim_param)) {
 173                 isl_space_free(model);
 174                 return umap;
 175         }
 176
 177         model = isl_space_params(model);
 178         data.exp = isl_parameter_alignment_reordering(umap->dim, model);
 179         if (!data.exp)
 180                 goto error;
 181
 182         data.res = isl_union_map_alloc(isl_space_copy(data.exp->dim),
 183                                         umap->table.n);
 184         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
 185                                         &align_entry, &data) < 0)
 186                 goto error;
 187
 188         isl_reordering_free(data.exp);
 189         isl_union_map_free(umap);
 190         isl_space_free(model);
 191         return data.res;
 192 error:
 193         isl_reordering_free(data.exp);
 194         isl_union_map_free(umap);
 195         isl_union_map_free(data.res);
 196         isl_space_free(model);
 197         return NULL;
 198 }
 199
 200 __isl_give isl_union_set *isl_union_set_align_params(
 201         __isl_take isl_union_set *uset, __isl_take isl_space *model)
 202 {
 203         return isl_union_map_align_params(uset, model);
 204 }
 205
 206 __isl_give isl_union_map *isl_union_map_union(__isl_take isl_union_map *umap1,
 207         __isl_take isl_union_map *umap2)
 208 {
 209         umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
 210         umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
 211
 212         umap1 = isl_union_map_cow(umap1);
 213
 214         if (!umap1 || !umap2)
 215                 goto error;
 216
 217         if (isl_union_map_foreach_map(umap2, &add_map, &umap1) < 0)
 218                 goto error;
 219
 220         isl_union_map_free(umap2);
 221
 222         return umap1;
 223 error:
 224         isl_union_map_free(umap1);
 225         isl_union_map_free(umap2);
 226         return NULL;
 227 }
 228
 229 __isl_give isl_union_set *isl_union_set_union(__isl_take isl_union_set *uset1,
 230         __isl_take isl_union_set *uset2)
 231 {
 232         return isl_union_map_union(uset1, uset2);
 233 }
 234
 235 __isl_give isl_union_map *isl_union_map_copy(__isl_keep isl_union_map *umap)
 236 {
 237         if (!umap)
 238                 return NULL;
 239
 240         umap->ref++;
 241         return umap;
 242 }
 243
 244 __isl_give isl_union_set *isl_union_set_copy(__isl_keep isl_union_set *uset)
 245 {
 246         return isl_union_map_copy(uset);
 247 }
 248
 249 void *isl_union_map_free(__isl_take isl_union_map *umap)
 250 {
 251         if (!umap)
 252                 return NULL;
 253
 254         if (--umap->ref > 0)
 255                 return NULL;
 256
 257         isl_hash_table_foreach(umap->dim->ctx, &umap->table,
 258                                &free_umap_entry, NULL);
 259         isl_hash_table_clear(&umap->table);
 260         isl_space_free(umap->dim);
 261         free(umap);
 262         return NULL;
 263 }
 264
 265 void *isl_union_set_free(__isl_take isl_union_set *uset)
 266 {
 267         return isl_union_map_free(uset);
 268 }
 269
 270 static int has_dim(const void *entry, const void *val)
 271 {
 272         isl_map *map = (isl_map *)entry;
 273         isl_space *dim = (isl_space *)val;
 274
 275         return isl_space_is_equal(map->dim, dim);
 276 }
 277
 278 __isl_give isl_union_map *isl_union_map_add_map(__isl_take isl_union_map *umap,
 279         __isl_take isl_map *map)
 280 {
 281         uint32_t hash;
 282         struct isl_hash_table_entry *entry;
 283
 284         if (!map || !umap)
 285                 goto error;
 286
 287         if (isl_map_plain_is_empty(map)) {
 288                 isl_map_free(map);
 289                 return umap;
 290         }
 291
 292         if (!isl_space_match(map->dim, isl_dim_param, umap->dim, isl_dim_param)) {
 293                 umap = isl_union_map_align_params(umap, isl_map_get_space(map));
 294                 map = isl_map_align_params(map, isl_union_map_get_space(umap));
 295         }
 296
 297         umap = isl_union_map_cow(umap);
 298
 299         if (!map || !umap)
 300                 goto error;
 301
 302         hash = isl_space_get_hash(map->dim);
 303         entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
 304                                     &has_dim, map->dim, 1);
 305         if (!entry)
 306                 goto error;
 307
 308         if (!entry->data)
 309                 entry->data = map;
 310         else {
 311                 entry->data = isl_map_union(entry->data, isl_map_copy(map));
 312                 if (!entry->data)
 313                         goto error;
 314                 isl_map_free(map);
 315         }
 316
 317         return umap;
 318 error:
 319         isl_map_free(map);
 320         isl_union_map_free(umap);
 321         return NULL;
 322 }
 323
 324 __isl_give isl_union_set *isl_union_set_add_set(__isl_take isl_union_set *uset,
 325         __isl_take isl_set *set)
 326 {
 327         return isl_union_map_add_map(uset, (isl_map *)set);
 328 }
 329
 330 __isl_give isl_union_map *isl_union_map_from_map(__isl_take isl_map *map)
 331 {
 332         isl_space *dim;
 333         isl_union_map *umap;
 334
 335         if (!map)
 336                 return NULL;
 337
 338         dim = isl_map_get_space(map);
 339         dim = isl_space_params(dim);
 340         umap = isl_union_map_empty(dim);
 341         umap = isl_union_map_add_map(umap, map);
 342
 343         return umap;
 344 }
 345
 346 __isl_give isl_union_set *isl_union_set_from_set(__isl_take isl_set *set)
 347 {
 348         return isl_union_map_from_map((isl_map *)set);
 349 }
 350
 351 __isl_give isl_union_map *isl_union_map_from_basic_map(
 352         __isl_take isl_basic_map *bmap)
 353 {
 354         return isl_union_map_from_map(isl_map_from_basic_map(bmap));
 355 }
 356
 357 __isl_give isl_union_set *isl_union_set_from_basic_set(
 358         __isl_take isl_basic_set *bset)
 359 {
 360         return isl_union_map_from_basic_map(bset);
 361 }
 362
 363 struct isl_union_map_foreach_data
 364 {
 365         int (*fn)(__isl_take isl_map *map, void *user);
 366         void *user;
 367 };
 368
 369 static int call_on_copy(void **entry, void *user)
 370 {
 371         isl_map *map = *entry;
 372         struct isl_union_map_foreach_data *data;
 373         data = (struct isl_union_map_foreach_data *)user;
 374
 375         return data->fn(isl_map_copy(map), data->user);
 376 }
 377
 378 int isl_union_map_n_map(__isl_keep isl_union_map *umap)
 379 {
 380         return umap ? umap->table.n : 0;
 381 }
 382
 383 int isl_union_set_n_set(__isl_keep isl_union_set *uset)
 384 {
 385         return uset ? uset->table.n : 0;
 386 }
 387
 388 int isl_union_map_foreach_map(__isl_keep isl_union_map *umap,
 389         int (*fn)(__isl_take isl_map *map, void *user), void *user)
 390 {
 391         struct isl_union_map_foreach_data data = { fn, user };
 392
 393         if (!umap)
 394                 return -1;
 395
 396         return isl_hash_table_foreach(umap->dim->ctx, &umap->table,
 397                                       &call_on_copy, &data);
 398 }
 399
 400 static int copy_map(void **entry, void *user)
 401 {
 402         isl_map *map = *entry;
 403         isl_map **map_p = user;
 404
 405         *map_p = isl_map_copy(map);
 406
 407         return -1;
 408 }
 409
 410 __isl_give isl_map *isl_map_from_union_map(__isl_take isl_union_map *umap)
 411 {
 412         isl_ctx *ctx;
 413         isl_map *map = NULL;
 414
 415         if (!umap)
 416                 return NULL;
 417         ctx = isl_union_map_get_ctx(umap);
 418         if (umap->table.n != 1)
 419                 isl_die(ctx, isl_error_invalid,
 420                         "union map needs to contain elements in exactly "
 421                         "one space", return isl_union_map_free(umap));
 422
 423         isl_hash_table_foreach(ctx, &umap->table, &copy_map, &map);
 424
 425         isl_union_map_free(umap);
 426
 427         return map;
 428 }
 429
 430 __isl_give isl_set *isl_set_from_union_set(__isl_take isl_union_set *uset)
 431 {
 432         return isl_map_from_union_map(uset);
 433 }
 434
 435 /* Extract the map in "umap" that lives in the given space (ignoring
 436  * parameters).
 437  */
 438 __isl_give isl_map *isl_union_map_extract_map(__isl_keep isl_union_map *umap,
 439         __isl_take isl_space *space)
 440 {
 441         uint32_t hash;
 442         struct isl_hash_table_entry *entry;
 443
 444         space = isl_space_drop_dims(space, isl_dim_param,
 445                                         0, isl_space_dim(space, isl_dim_param));
 446         space = isl_space_align_params(space, isl_union_map_get_space(umap));
 447         if (!umap || !space)
 448                 goto error;
 449
 450         hash = isl_space_get_hash(space);
 451         entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
 452                                     &has_dim, space, 0);
 453         if (!entry)
 454                 return isl_map_empty(space);
 455         isl_space_free(space);
 456         return isl_map_copy(entry->data);
 457 error:
 458         isl_space_free(space);
 459         return NULL;
 460 }
 461
 462 __isl_give isl_set *isl_union_set_extract_set(__isl_keep isl_union_set *uset,
 463         __isl_take isl_space *dim)
 464 {
 465         return (isl_set *)isl_union_map_extract_map(uset, dim);
 466 }
 467
 468 /* Check if umap contains a map in the given space.
 469  */
 470 __isl_give int isl_union_map_contains(__isl_keep isl_union_map *umap,
 471         __isl_keep isl_space *dim)
 472 {
 473         uint32_t hash;
 474         struct isl_hash_table_entry *entry;
 475
 476         if (!umap || !dim)
 477                 return -1;
 478
 479         hash = isl_space_get_hash(dim);
 480         entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
 481                                     &has_dim, dim, 0);
 482         return !!entry;
 483 }
 484
 485 __isl_give int isl_union_set_contains(__isl_keep isl_union_set *uset,
 486         __isl_keep isl_space *dim)
 487 {
 488         return isl_union_map_contains(uset, dim);
 489 }
 490
 491 int isl_union_set_foreach_set(__isl_keep isl_union_set *uset,
 492         int (*fn)(__isl_take isl_set *set, void *user), void *user)
 493 {
 494         return isl_union_map_foreach_map(uset,
 495                 (int(*)(__isl_take isl_map *, void*))fn, user);
 496 }
 497
 498 struct isl_union_set_foreach_point_data {
 499         int (*fn)(__isl_take isl_point *pnt, void *user);
 500         void *user;
 501 };
 502
 503 static int foreach_point(__isl_take isl_set *set, void *user)
 504 {
 505         struct isl_union_set_foreach_point_data *data = user;
 506         int r;
 507
 508         r = isl_set_foreach_point(set, data->fn, data->user);
 509         isl_set_free(set);
 510
 511         return r;
 512 }
 513
 514 int isl_union_set_foreach_point(__isl_keep isl_union_set *uset,
 515         int (*fn)(__isl_take isl_point *pnt, void *user), void *user)
 516 {
 517         struct isl_union_set_foreach_point_data data = { fn, user };
 518         return isl_union_set_foreach_set(uset, &foreach_point, &data);
 519 }
 520
 521 struct isl_union_map_gen_bin_data {
 522         isl_union_map *umap2;
 523         isl_union_map *res;
 524 };
 525
 526 static int subtract_entry(void **entry, void *user)
 527 {
 528         struct isl_union_map_gen_bin_data *data = user;
 529         uint32_t hash;
 530         struct isl_hash_table_entry *entry2;
 531         isl_map *map = *entry;
 532
 533         hash = isl_space_get_hash(map->dim);
 534         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
 535                                      hash, &has_dim, map->dim, 0);
 536         map = isl_map_copy(map);
 537         if (entry2) {
 538                 int empty;
 539                 map = isl_map_subtract(map, isl_map_copy(entry2->data));
 540
 541                 empty = isl_map_is_empty(map);
 542                 if (empty < 0) {
 543                         isl_map_free(map);
 544                         return -1;
 545                 }
 546                 if (empty) {
 547                         isl_map_free(map);
 548                         return 0;
 549                 }
 550         }
 551         data->res = isl_union_map_add_map(data->res, map);
 552
 553         return 0;
 554 }
 555
 556 static __isl_give isl_union_map *gen_bin_op(__isl_take isl_union_map *umap1,
 557         __isl_take isl_union_map *umap2, int (*fn)(void **, void *))
 558 {
 559         struct isl_union_map_gen_bin_data data = { NULL, NULL };
 560
 561         umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
 562         umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
 563
 564         if (!umap1 || !umap2)
 565                 goto error;
 566
 567         data.umap2 = umap2;
 568         data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
 569                                        umap1->table.n);
 570         if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
 571                                    fn, &data) < 0)
 572                 goto error;
 573
 574         isl_union_map_free(umap1);
 575         isl_union_map_free(umap2);
 576         return data.res;
 577 error:
 578         isl_union_map_free(umap1);
 579         isl_union_map_free(umap2);
 580         isl_union_map_free(data.res);
 581         return NULL;
 582 }
 583
 584 __isl_give isl_union_map *isl_union_map_subtract(
 585         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 586 {
 587         return gen_bin_op(umap1, umap2, &subtract_entry);
 588 }
 589
 590 __isl_give isl_union_set *isl_union_set_subtract(
 591         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
 592 {
 593         return isl_union_map_subtract(uset1, uset2);
 594 }
 595
 596 struct isl_union_map_gen_bin_set_data {
 597         isl_set *set;
 598         isl_union_map *res;
 599 };
 600
 601 static int intersect_params_entry(void **entry, void *user)
 602 {
 603         struct isl_union_map_gen_bin_set_data *data = user;
 604         isl_map *map = *entry;
 605         int empty;
 606
 607         map = isl_map_copy(map);
 608         map = isl_map_intersect_params(map, isl_set_copy(data->set));
 609
 610         empty = isl_map_is_empty(map);
 611         if (empty < 0) {
 612                 isl_map_free(map);
 613                 return -1;
 614         }
 615
 616         data->res = isl_union_map_add_map(data->res, map);
 617
 618         return 0;
 619 }
 620
 621 static __isl_give isl_union_map *gen_bin_set_op(__isl_take isl_union_map *umap,
 622         __isl_take isl_set *set, int (*fn)(void **, void *))
 623 {
 624         struct isl_union_map_gen_bin_set_data data = { NULL, NULL };
 625
 626         umap = isl_union_map_align_params(umap, isl_set_get_space(set));
 627         set = isl_set_align_params(set, isl_union_map_get_space(umap));
 628
 629         if (!umap || !set)
 630                 goto error;
 631
 632         data.set = set;
 633         data.res = isl_union_map_alloc(isl_space_copy(umap->dim),
 634                                        umap->table.n);
 635         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
 636                                    fn, &data) < 0)
 637                 goto error;
 638
 639         isl_union_map_free(umap);
 640         isl_set_free(set);
 641         return data.res;
 642 error:
 643         isl_union_map_free(umap);
 644         isl_set_free(set);
 645         isl_union_map_free(data.res);
 646         return NULL;
 647 }
 648
 649 __isl_give isl_union_map *isl_union_map_intersect_params(
 650         __isl_take isl_union_map *umap, __isl_take isl_set *set)
 651 {
 652         return gen_bin_set_op(umap, set, &intersect_params_entry);
 653 }
 654
 655 __isl_give isl_union_set *isl_union_set_intersect_params(
 656         __isl_take isl_union_set *uset, __isl_take isl_set *set)
 657 {
 658         return isl_union_map_intersect_params(uset, set);
 659 }
 660
 661 static __isl_give isl_union_map *union_map_intersect_params(
 662         __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
 663 {
 664         return isl_union_map_intersect_params(umap,
 665                                                 isl_set_from_union_set(uset));
 666 }
 667
 668 static __isl_give isl_union_map *union_map_gist_params(
 669         __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
 670 {
 671         return isl_union_map_gist_params(umap, isl_set_from_union_set(uset));
 672 }
 673
 674 struct isl_union_map_match_bin_data {
 675         isl_union_map *umap2;
 676         isl_union_map *res;
 677         __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*);
 678 };
 679
 680 static int match_bin_entry(void **entry, void *user)
 681 {
 682         struct isl_union_map_match_bin_data *data = user;
 683         uint32_t hash;
 684         struct isl_hash_table_entry *entry2;
 685         isl_map *map = *entry;
 686         int empty;
 687
 688         hash = isl_space_get_hash(map->dim);
 689         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
 690                                      hash, &has_dim, map->dim, 0);
 691         if (!entry2)
 692                 return 0;
 693
 694         map = isl_map_copy(map);
 695         map = data->fn(map, isl_map_copy(entry2->data));
 696
 697         empty = isl_map_is_empty(map);
 698         if (empty < 0) {
 699                 isl_map_free(map);
 700                 return -1;
 701         }
 702         if (empty) {
 703                 isl_map_free(map);
 704                 return 0;
 705         }
 706
 707         data->res = isl_union_map_add_map(data->res, map);
 708
 709         return 0;
 710 }
 711
 712 static __isl_give isl_union_map *match_bin_op(__isl_take isl_union_map *umap1,
 713         __isl_take isl_union_map *umap2,
 714         __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*))
 715 {
 716         struct isl_union_map_match_bin_data data = { NULL, NULL, fn };
 717
 718         umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
 719         umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
 720
 721         if (!umap1 || !umap2)
 722                 goto error;
 723
 724         data.umap2 = umap2;
 725         data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
 726                                        umap1->table.n);
 727         if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
 728                                    &match_bin_entry, &data) < 0)
 729                 goto error;
 730
 731         isl_union_map_free(umap1);
 732         isl_union_map_free(umap2);
 733         return data.res;
 734 error:
 735         isl_union_map_free(umap1);
 736         isl_union_map_free(umap2);
 737         isl_union_map_free(data.res);
 738         return NULL;
 739 }
 740
 741 __isl_give isl_union_map *isl_union_map_intersect(
 742         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 743 {
 744         return match_bin_op(umap1, umap2, &isl_map_intersect);
 745 }
 746
 747 /* Compute the intersection of the two union_sets.
 748  * As a special case, if exactly one of the two union_sets
 749  * is a parameter domain, then intersect the parameter domain
 750  * of the other one with this set.
 751  */
 752 __isl_give isl_union_set *isl_union_set_intersect(
 753         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
 754 {
 755         int p1, p2;
 756
 757         p1 = isl_union_set_is_params(uset1);
 758         p2 = isl_union_set_is_params(uset2);
 759         if (p1 < 0 || p2 < 0)
 760                 goto error;
 761         if (!p1 && p2)
 762                 return union_map_intersect_params(uset1, uset2);
 763         if (p1 && !p2)
 764                 return union_map_intersect_params(uset2, uset1);
 765         return isl_union_map_intersect(uset1, uset2);
 766 error:
 767         isl_union_set_free(uset1);
 768         isl_union_set_free(uset2);
 769         return NULL;
 770 }
 771
 772 static int gist_params_entry(void **entry, void *user)
 773 {
 774         struct isl_union_map_gen_bin_set_data *data = user;
 775         isl_map *map = *entry;
 776         int empty;
 777
 778         map = isl_map_copy(map);
 779         map = isl_map_gist_params(map, isl_set_copy(data->set));
 780
 781         empty = isl_map_is_empty(map);
 782         if (empty < 0) {
 783                 isl_map_free(map);
 784                 return -1;
 785         }
 786
 787         data->res = isl_union_map_add_map(data->res, map);
 788
 789         return 0;
 790 }
 791
 792 __isl_give isl_union_map *isl_union_map_gist_params(
 793         __isl_take isl_union_map *umap, __isl_take isl_set *set)
 794 {
 795         return gen_bin_set_op(umap, set, &gist_params_entry);
 796 }
 797
 798 __isl_give isl_union_set *isl_union_set_gist_params(
 799         __isl_take isl_union_set *uset, __isl_take isl_set *set)
 800 {
 801         return isl_union_map_gist_params(uset, set);
 802 }
 803
 804 __isl_give isl_union_map *isl_union_map_gist(__isl_take isl_union_map *umap,
 805         __isl_take isl_union_map *context)
 806 {
 807         return match_bin_op(umap, context, &isl_map_gist);
 808 }
 809
 810 __isl_give isl_union_set *isl_union_set_gist(__isl_take isl_union_set *uset,
 811         __isl_take isl_union_set *context)
 812 {
 813         if (isl_union_set_is_params(context))
 814                 return union_map_gist_params(uset, context);
 815         return isl_union_map_gist(uset, context);
 816 }
 817
 818 static __isl_give isl_map *lex_le_set(__isl_take isl_map *set1,
 819         __isl_take isl_map *set2)
 820 {
 821         return isl_set_lex_le_set((isl_set *)set1, (isl_set *)set2);
 822 }
 823
 824 static __isl_give isl_map *lex_lt_set(__isl_take isl_map *set1,
 825         __isl_take isl_map *set2)
 826 {
 827         return isl_set_lex_lt_set((isl_set *)set1, (isl_set *)set2);
 828 }
 829
 830 __isl_give isl_union_map *isl_union_set_lex_lt_union_set(
 831         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
 832 {
 833         return match_bin_op(uset1, uset2, &lex_lt_set);
 834 }
 835
 836 __isl_give isl_union_map *isl_union_set_lex_le_union_set(
 837         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
 838 {
 839         return match_bin_op(uset1, uset2, &lex_le_set);
 840 }
 841
 842 __isl_give isl_union_map *isl_union_set_lex_gt_union_set(
 843         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
 844 {
 845         return isl_union_map_reverse(isl_union_set_lex_lt_union_set(uset2, uset1));
 846 }
 847
 848 __isl_give isl_union_map *isl_union_set_lex_ge_union_set(
 849         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
 850 {
 851         return isl_union_map_reverse(isl_union_set_lex_le_union_set(uset2, uset1));
 852 }
 853
 854 __isl_give isl_union_map *isl_union_map_lex_gt_union_map(
 855         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 856 {
 857         return isl_union_map_reverse(isl_union_map_lex_lt_union_map(umap2, umap1));
 858 }
 859
 860 __isl_give isl_union_map *isl_union_map_lex_ge_union_map(
 861         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 862 {
 863         return isl_union_map_reverse(isl_union_map_lex_le_union_map(umap2, umap1));
 864 }
 865
 866 static int intersect_domain_entry(void **entry, void *user)
 867 {
 868         struct isl_union_map_gen_bin_data *data = user;
 869         uint32_t hash;
 870         struct isl_hash_table_entry *entry2;
 871         isl_space *dim;
 872         isl_map *map = *entry;
 873         int empty;
 874
 875         dim = isl_map_get_space(map);
 876         dim = isl_space_domain(dim);
 877         hash = isl_space_get_hash(dim);
 878         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
 879                                      hash, &has_dim, dim, 0);
 880         isl_space_free(dim);
 881         if (!entry2)
 882                 return 0;
 883
 884         map = isl_map_copy(map);
 885         map = isl_map_intersect_domain(map, isl_set_copy(entry2->data));
 886
 887         empty = isl_map_is_empty(map);
 888         if (empty < 0) {
 889                 isl_map_free(map);
 890                 return -1;
 891         }
 892         if (empty) {
 893                 isl_map_free(map);
 894                 return 0;
 895         }
 896
 897         data->res = isl_union_map_add_map(data->res, map);
 898
 899         return 0;
 900 }
 901
 902 /* Intersect the domain of "umap" with "uset".
 903  * If "uset" is a parameters domain, then intersect the parameter
 904  * domain of "umap" with this set.
 905  */
 906 __isl_give isl_union_map *isl_union_map_intersect_domain(
 907         __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
 908 {
 909         if (isl_union_set_is_params(uset))
 910                 return union_map_intersect_params(umap, uset);
 911         return gen_bin_op(umap, uset, &intersect_domain_entry);
 912 }
 913
 914 /* Remove the elements of data->umap2 from the domain of *entry
 915  * and add the result to data->res.
 916  */
 917 static int subtract_domain_entry(void **entry, void *user)
 918 {
 919         struct isl_union_map_gen_bin_data *data = user;
 920         uint32_t hash;
 921         struct isl_hash_table_entry *entry2;
 922         isl_space *dim;
 923         isl_map *map = *entry;
 924         int empty;
 925
 926         dim = isl_map_get_space(map);
 927         dim = isl_space_domain(dim);
 928         hash = isl_space_get_hash(dim);
 929         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
 930                                      hash, &has_dim, dim, 0);
 931         isl_space_free(dim);
 932
 933         map = isl_map_copy(map);
 934
 935         if (!entry2) {
 936                 data->res = isl_union_map_add_map(data->res, map);
 937                 return 0;
 938         }
 939
 940         map = isl_map_subtract_domain(map, isl_set_copy(entry2->data));
 941
 942         empty = isl_map_is_empty(map);
 943         if (empty < 0) {
 944                 isl_map_free(map);
 945                 return -1;
 946         }
 947         if (empty) {
 948                 isl_map_free(map);
 949                 return 0;
 950         }
 951
 952         data->res = isl_union_map_add_map(data->res, map);
 953
 954         return 0;
 955 }
 956
 957 /* Remove the elements of "uset" from the domain of "umap".
 958  */
 959 __isl_give isl_union_map *isl_union_map_subtract_domain(
 960         __isl_take isl_union_map *umap, __isl_take isl_union_set *dom)
 961 {
 962         return gen_bin_op(umap, dom, &subtract_domain_entry);
 963 }
 964
 965 /* Remove the elements of data->umap2 from the range of *entry
 966  * and add the result to data->res.
 967  */
 968 static int subtract_range_entry(void **entry, void *user)
 969 {
 970         struct isl_union_map_gen_bin_data *data = user;
 971         uint32_t hash;
 972         struct isl_hash_table_entry *entry2;
 973         isl_space *space;
 974         isl_map *map = *entry;
 975         int empty;
 976
 977         space = isl_map_get_space(map);
 978         space = isl_space_range(space);
 979         hash = isl_space_get_hash(space);
 980         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
 981                                      hash, &has_dim, space, 0);
 982         isl_space_free(space);
 983
 984         map = isl_map_copy(map);
 985
 986         if (!entry2) {
 987                 data->res = isl_union_map_add_map(data->res, map);
 988                 return 0;
 989         }
 990
 991         map = isl_map_subtract_range(map, isl_set_copy(entry2->data));
 992
 993         empty = isl_map_is_empty(map);
 994         if (empty < 0) {
 995                 isl_map_free(map);
 996                 return -1;
 997         }
 998         if (empty) {
 999                 isl_map_free(map);
1000                 return 0;
1001         }
1002
1003         data->res = isl_union_map_add_map(data->res, map);
1004
1005         return 0;
1006 }
1007
1008 /* Remove the elements of "uset" from the range of "umap".
1009  */
1010 __isl_give isl_union_map *isl_union_map_subtract_range(
1011         __isl_take isl_union_map *umap, __isl_take isl_union_set *dom)
1012 {
1013         return gen_bin_op(umap, dom, &subtract_range_entry);
1014 }
1015
1016 static int gist_domain_entry(void **entry, void *user)
1017 {
1018         struct isl_union_map_gen_bin_data *data = user;
1019         uint32_t hash;
1020         struct isl_hash_table_entry *entry2;
1021         isl_space *dim;
1022         isl_map *map = *entry;
1023         int empty;
1024
1025         dim = isl_map_get_space(map);
1026         dim = isl_space_domain(dim);
1027         hash = isl_space_get_hash(dim);
1028         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1029                                      hash, &has_dim, dim, 0);
1030         isl_space_free(dim);
1031         if (!entry2)
1032                 return 0;
1033
1034         map = isl_map_copy(map);
1035         map = isl_map_gist_domain(map, isl_set_copy(entry2->data));
1036
1037         empty = isl_map_is_empty(map);
1038         if (empty < 0) {
1039                 isl_map_free(map);
1040                 return -1;
1041         }
1042
1043         data->res = isl_union_map_add_map(data->res, map);
1044
1045         return 0;
1046 }
1047
1048 /* Compute the gist of "umap" with respect to the domain "uset".
1049  * If "uset" is a parameters domain, then compute the gist
1050  * with respect to this parameter domain.
1051  */
1052 __isl_give isl_union_map *isl_union_map_gist_domain(
1053         __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1054 {
1055         if (isl_union_set_is_params(uset))
1056                 return union_map_gist_params(umap, uset);
1057         return gen_bin_op(umap, uset, &gist_domain_entry);
1058 }
1059
1060 static int gist_range_entry(void **entry, void *user)
1061 {
1062         struct isl_union_map_gen_bin_data *data = user;
1063         uint32_t hash;
1064         struct isl_hash_table_entry *entry2;
1065         isl_space *space;
1066         isl_map *map = *entry;
1067         int empty;
1068
1069         space = isl_map_get_space(map);
1070         space = isl_space_range(space);
1071         hash = isl_space_get_hash(space);
1072         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1073                                      hash, &has_dim, space, 0);
1074         isl_space_free(space);
1075         if (!entry2)
1076                 return 0;
1077
1078         map = isl_map_copy(map);
1079         map = isl_map_gist_range(map, isl_set_copy(entry2->data));
1080
1081         empty = isl_map_is_empty(map);
1082         if (empty < 0) {
1083                 isl_map_free(map);
1084                 return -1;
1085         }
1086
1087         data->res = isl_union_map_add_map(data->res, map);
1088
1089         return 0;
1090 }
1091
1092 /* Compute the gist of "umap" with respect to the range "uset".
1093  */
1094 __isl_give isl_union_map *isl_union_map_gist_range(
1095         __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1096 {
1097         return gen_bin_op(umap, uset, &gist_range_entry);
1098 }
1099
1100 static int intersect_range_entry(void **entry, void *user)
1101 {
1102         struct isl_union_map_gen_bin_data *data = user;
1103         uint32_t hash;
1104         struct isl_hash_table_entry *entry2;
1105         isl_space *dim;
1106         isl_map *map = *entry;
1107         int empty;
1108
1109         dim = isl_map_get_space(map);
1110         dim = isl_space_range(dim);
1111         hash = isl_space_get_hash(dim);
1112         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1113                                      hash, &has_dim, dim, 0);
1114         isl_space_free(dim);
1115         if (!entry2)
1116                 return 0;
1117
1118         map = isl_map_copy(map);
1119         map = isl_map_intersect_range(map, isl_set_copy(entry2->data));
1120
1121         empty = isl_map_is_empty(map);
1122         if (empty < 0) {
1123                 isl_map_free(map);
1124                 return -1;
1125         }
1126         if (empty) {
1127                 isl_map_free(map);
1128                 return 0;
1129         }
1130
1131         data->res = isl_union_map_add_map(data->res, map);
1132
1133         return 0;
1134 }
1135
1136 __isl_give isl_union_map *isl_union_map_intersect_range(
1137         __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1138 {
1139         return gen_bin_op(umap, uset, &intersect_range_entry);
1140 }
1141
1142 struct isl_union_map_bin_data {
1143         isl_union_map *umap2;
1144         isl_union_map *res;
1145         isl_map *map;
1146         int (*fn)(void **entry, void *user);
1147 };
1148
1149 static int apply_range_entry(void **entry, void *user)
1150 {
1151         struct isl_union_map_bin_data *data = user;
1152         isl_map *map2 = *entry;
1153         int empty;
1154
1155         if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1156                                  map2->dim, isl_dim_in))
1157                 return 0;
1158
1159         map2 = isl_map_apply_range(isl_map_copy(data->map), isl_map_copy(map2));
1160
1161         empty = isl_map_is_empty(map2);
1162         if (empty < 0) {
1163                 isl_map_free(map2);
1164                 return -1;
1165         }
1166         if (empty) {
1167                 isl_map_free(map2);
1168                 return 0;
1169         }
1170
1171         data->res = isl_union_map_add_map(data->res, map2);
1172
1173         return 0;
1174 }
1175
1176 static int bin_entry(void **entry, void *user)
1177 {
1178         struct isl_union_map_bin_data *data = user;
1179         isl_map *map = *entry;
1180
1181         data->map = map;
1182         if (isl_hash_table_foreach(data->umap2->dim->ctx, &data->umap2->table,
1183                                    data->fn, data) < 0)
1184                 return -1;
1185
1186         return 0;
1187 }
1188
1189 static __isl_give isl_union_map *bin_op(__isl_take isl_union_map *umap1,
1190         __isl_take isl_union_map *umap2, int (*fn)(void **entry, void *user))
1191 {
1192         struct isl_union_map_bin_data data = { NULL, NULL, NULL, fn };
1193
1194         umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
1195         umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
1196
1197         if (!umap1 || !umap2)
1198                 goto error;
1199
1200         data.umap2 = umap2;
1201         data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
1202                                        umap1->table.n);
1203         if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1204                                    &bin_entry, &data) < 0)
1205                 goto error;
1206
1207         isl_union_map_free(umap1);
1208         isl_union_map_free(umap2);
1209         return data.res;
1210 error:
1211         isl_union_map_free(umap1);
1212         isl_union_map_free(umap2);
1213         isl_union_map_free(data.res);
1214         return NULL;
1215 }
1216
1217 __isl_give isl_union_map *isl_union_map_apply_range(
1218         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1219 {
1220         return bin_op(umap1, umap2, &apply_range_entry);
1221 }
1222
1223 __isl_give isl_union_map *isl_union_map_apply_domain(
1224         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1225 {
1226         umap1 = isl_union_map_reverse(umap1);
1227         umap1 = isl_union_map_apply_range(umap1, umap2);
1228         return isl_union_map_reverse(umap1);
1229 }
1230
1231 __isl_give isl_union_set *isl_union_set_apply(
1232         __isl_take isl_union_set *uset, __isl_take isl_union_map *umap)
1233 {
1234         return isl_union_map_apply_range(uset, umap);
1235 }
1236
1237 static int map_lex_lt_entry(void **entry, void *user)
1238 {
1239         struct isl_union_map_bin_data *data = user;
1240         isl_map *map2 = *entry;
1241
1242         if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1243                                  map2->dim, isl_dim_out))
1244                 return 0;
1245
1246         map2 = isl_map_lex_lt_map(isl_map_copy(data->map), isl_map_copy(map2));
1247
1248         data->res = isl_union_map_add_map(data->res, map2);
1249
1250         return 0;
1251 }
1252
1253 __isl_give isl_union_map *isl_union_map_lex_lt_union_map(
1254         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1255 {
1256         return bin_op(umap1, umap2, &map_lex_lt_entry);
1257 }
1258
1259 static int map_lex_le_entry(void **entry, void *user)
1260 {
1261         struct isl_union_map_bin_data *data = user;
1262         isl_map *map2 = *entry;
1263
1264         if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1265                                  map2->dim, isl_dim_out))
1266                 return 0;
1267
1268         map2 = isl_map_lex_le_map(isl_map_copy(data->map), isl_map_copy(map2));
1269
1270         data->res = isl_union_map_add_map(data->res, map2);
1271
1272         return 0;
1273 }
1274
1275 __isl_give isl_union_map *isl_union_map_lex_le_union_map(
1276         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1277 {
1278         return bin_op(umap1, umap2, &map_lex_le_entry);
1279 }
1280
1281 static int product_entry(void **entry, void *user)
1282 {
1283         struct isl_union_map_bin_data *data = user;
1284         isl_map *map2 = *entry;
1285
1286         map2 = isl_map_product(isl_map_copy(data->map), isl_map_copy(map2));
1287
1288         data->res = isl_union_map_add_map(data->res, map2);
1289
1290         return 0;
1291 }
1292
1293 __isl_give isl_union_map *isl_union_map_product(__isl_take isl_union_map *umap1,
1294         __isl_take isl_union_map *umap2)
1295 {
1296         return bin_op(umap1, umap2, &product_entry);
1297 }
1298
1299 static int set_product_entry(void **entry, void *user)
1300 {
1301         struct isl_union_map_bin_data *data = user;
1302         isl_set *set2 = *entry;
1303
1304         set2 = isl_set_product(isl_set_copy(data->map), isl_set_copy(set2));
1305
1306         data->res = isl_union_set_add_set(data->res, set2);
1307
1308         return 0;
1309 }
1310
1311 __isl_give isl_union_set *isl_union_set_product(__isl_take isl_union_set *uset1,
1312         __isl_take isl_union_set *uset2)
1313 {
1314         return bin_op(uset1, uset2, &set_product_entry);
1315 }
1316
1317 static int domain_product_entry(void **entry, void *user)
1318 {
1319         struct isl_union_map_bin_data *data = user;
1320         isl_map *map2 = *entry;
1321
1322         if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1323                                  map2->dim, isl_dim_out))
1324                 return 0;
1325
1326         map2 = isl_map_domain_product(isl_map_copy(data->map),
1327                                      isl_map_copy(map2));
1328
1329         data->res = isl_union_map_add_map(data->res, map2);
1330
1331         return 0;
1332 }
1333
1334 /* Given two maps A -> B and C -> D, construct a map [A -> C] -> (B * D)
1335  */
1336 __isl_give isl_union_map *isl_union_map_domain_product(
1337         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1338 {
1339         return bin_op(umap1, umap2, &domain_product_entry);
1340 }
1341
1342 static int range_product_entry(void **entry, void *user)
1343 {
1344         struct isl_union_map_bin_data *data = user;
1345         isl_map *map2 = *entry;
1346
1347         if (!isl_space_tuple_match(data->map->dim, isl_dim_in,
1348                                  map2->dim, isl_dim_in))
1349                 return 0;
1350
1351         map2 = isl_map_range_product(isl_map_copy(data->map),
1352                                      isl_map_copy(map2));
1353
1354         data->res = isl_union_map_add_map(data->res, map2);
1355
1356         return 0;
1357 }
1358
1359 __isl_give isl_union_map *isl_union_map_range_product(
1360         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1361 {
1362         return bin_op(umap1, umap2, &range_product_entry);
1363 }
1364
1365 static int flat_range_product_entry(void **entry, void *user)
1366 {
1367         struct isl_union_map_bin_data *data = user;
1368         isl_map *map2 = *entry;
1369
1370         if (!isl_space_tuple_match(data->map->dim, isl_dim_in,
1371                                  map2->dim, isl_dim_in))
1372                 return 0;
1373
1374         map2 = isl_map_flat_range_product(isl_map_copy(data->map),
1375                                           isl_map_copy(map2));
1376
1377         data->res = isl_union_map_add_map(data->res, map2);
1378
1379         return 0;
1380 }
1381
1382 __isl_give isl_union_map *isl_union_map_flat_range_product(
1383         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1384 {
1385         return bin_op(umap1, umap2, &flat_range_product_entry);
1386 }
1387
1388 static __isl_give isl_union_set *cond_un_op(__isl_take isl_union_map *umap,
1389         int (*fn)(void **, void *))
1390 {
1391         isl_union_set *res;
1392
1393         if (!umap)
1394                 return NULL;
1395
1396         res = isl_union_map_alloc(isl_space_copy(umap->dim), umap->table.n);
1397         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, &res) < 0)
1398                 goto error;
1399
1400         isl_union_map_free(umap);
1401         return res;
1402 error:
1403         isl_union_map_free(umap);
1404         isl_union_set_free(res);
1405         return NULL;
1406 }
1407
1408 static int from_range_entry(void **entry, void *user)
1409 {
1410         isl_map *set = *entry;
1411         isl_union_set **res = user;
1412
1413         *res = isl_union_map_add_map(*res,
1414                                         isl_map_from_range(isl_set_copy(set)));
1415
1416         return 0;
1417 }
1418
1419 __isl_give isl_union_map *isl_union_map_from_range(
1420         __isl_take isl_union_set *uset)
1421 {
1422         return cond_un_op(uset, &from_range_entry);
1423 }
1424
1425 __isl_give isl_union_map *isl_union_map_from_domain(
1426         __isl_take isl_union_set *uset)
1427 {
1428         return isl_union_map_reverse(isl_union_map_from_range(uset));
1429 }
1430
1431 __isl_give isl_union_map *isl_union_map_from_domain_and_range(
1432         __isl_take isl_union_set *domain, __isl_take isl_union_set *range)
1433 {
1434         return isl_union_map_apply_range(isl_union_map_from_domain(domain),
1435                                          isl_union_map_from_range(range));
1436 }
1437
1438 static __isl_give isl_union_map *un_op(__isl_take isl_union_map *umap,
1439         int (*fn)(void **, void *))
1440 {
1441         umap = isl_union_map_cow(umap);
1442         if (!umap)
1443                 return NULL;
1444
1445         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, NULL) < 0)
1446                 goto error;
1447
1448         return umap;
1449 error:
1450         isl_union_map_free(umap);
1451         return NULL;
1452 }
1453
1454 static int affine_entry(void **entry, void *user)
1455 {
1456         isl_map **map = (isl_map **)entry;
1457
1458         *map = isl_map_from_basic_map(isl_map_affine_hull(*map));
1459
1460         return *map ? 0 : -1;
1461 }
1462
1463 __isl_give isl_union_map *isl_union_map_affine_hull(
1464         __isl_take isl_union_map *umap)
1465 {
1466         return un_op(umap, &affine_entry);
1467 }
1468
1469 __isl_give isl_union_set *isl_union_set_affine_hull(
1470         __isl_take isl_union_set *uset)
1471 {
1472         return isl_union_map_affine_hull(uset);
1473 }
1474
1475 static int polyhedral_entry(void **entry, void *user)
1476 {
1477         isl_map **map = (isl_map **)entry;
1478
1479         *map = isl_map_from_basic_map(isl_map_polyhedral_hull(*map));
1480
1481         return *map ? 0 : -1;
1482 }
1483
1484 __isl_give isl_union_map *isl_union_map_polyhedral_hull(
1485         __isl_take isl_union_map *umap)
1486 {
1487         return un_op(umap, &polyhedral_entry);
1488 }
1489
1490 __isl_give isl_union_set *isl_union_set_polyhedral_hull(
1491         __isl_take isl_union_set *uset)
1492 {
1493         return isl_union_map_polyhedral_hull(uset);
1494 }
1495
1496 static int simple_entry(void **entry, void *user)
1497 {
1498         isl_map **map = (isl_map **)entry;
1499
1500         *map = isl_map_from_basic_map(isl_map_simple_hull(*map));
1501
1502         return *map ? 0 : -1;
1503 }
1504
1505 __isl_give isl_union_map *isl_union_map_simple_hull(
1506         __isl_take isl_union_map *umap)
1507 {
1508         return un_op(umap, &simple_entry);
1509 }
1510
1511 __isl_give isl_union_set *isl_union_set_simple_hull(
1512         __isl_take isl_union_set *uset)
1513 {
1514         return isl_union_map_simple_hull(uset);
1515 }
1516
1517 static int inplace_entry(void **entry, void *user)
1518 {
1519         __isl_give isl_map *(*fn)(__isl_take isl_map *);
1520         isl_map **map = (isl_map **)entry;
1521         isl_map *copy;
1522
1523         fn = *(__isl_give isl_map *(**)(__isl_take isl_map *)) user;
1524         copy = fn(isl_map_copy(*map));
1525         if (!copy)
1526                 return -1;
1527
1528         isl_map_free(*map);
1529         *map = copy;
1530
1531         return 0;
1532 }
1533
1534 static __isl_give isl_union_map *inplace(__isl_take isl_union_map *umap,
1535         __isl_give isl_map *(*fn)(__isl_take isl_map *))
1536 {
1537         if (!umap)
1538                 return NULL;
1539
1540         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1541                                     &inplace_entry, &fn) < 0)
1542                 goto error;
1543
1544         return umap;
1545 error:
1546         isl_union_map_free(umap);
1547         return NULL;
1548 }
1549
1550 __isl_give isl_union_map *isl_union_map_coalesce(
1551         __isl_take isl_union_map *umap)
1552 {
1553         return inplace(umap, &isl_map_coalesce);
1554 }
1555
1556 __isl_give isl_union_set *isl_union_set_coalesce(
1557         __isl_take isl_union_set *uset)
1558 {
1559         return isl_union_map_coalesce(uset);
1560 }
1561
1562 __isl_give isl_union_map *isl_union_map_detect_equalities(
1563         __isl_take isl_union_map *umap)
1564 {
1565         return inplace(umap, &isl_map_detect_equalities);
1566 }
1567
1568 __isl_give isl_union_set *isl_union_set_detect_equalities(
1569         __isl_take isl_union_set *uset)
1570 {
1571         return isl_union_map_detect_equalities(uset);
1572 }
1573
1574 __isl_give isl_union_map *isl_union_map_compute_divs(
1575         __isl_take isl_union_map *umap)
1576 {
1577         return inplace(umap, &isl_map_compute_divs);
1578 }
1579
1580 __isl_give isl_union_set *isl_union_set_compute_divs(
1581         __isl_take isl_union_set *uset)
1582 {
1583         return isl_union_map_compute_divs(uset);
1584 }
1585
1586 static int lexmin_entry(void **entry, void *user)
1587 {
1588         isl_map **map = (isl_map **)entry;
1589
1590         *map = isl_map_lexmin(*map);
1591
1592         return *map ? 0 : -1;
1593 }
1594
1595 __isl_give isl_union_map *isl_union_map_lexmin(
1596         __isl_take isl_union_map *umap)
1597 {
1598         return un_op(umap, &lexmin_entry);
1599 }
1600
1601 __isl_give isl_union_set *isl_union_set_lexmin(
1602         __isl_take isl_union_set *uset)
1603 {
1604         return isl_union_map_lexmin(uset);
1605 }
1606
1607 static int lexmax_entry(void **entry, void *user)
1608 {
1609         isl_map **map = (isl_map **)entry;
1610
1611         *map = isl_map_lexmax(*map);
1612
1613         return *map ? 0 : -1;
1614 }
1615
1616 __isl_give isl_union_map *isl_union_map_lexmax(
1617         __isl_take isl_union_map *umap)
1618 {
1619         return un_op(umap, &lexmax_entry);
1620 }
1621
1622 __isl_give isl_union_set *isl_union_set_lexmax(
1623         __isl_take isl_union_set *uset)
1624 {
1625         return isl_union_map_lexmax(uset);
1626 }
1627
1628 static int universe_entry(void **entry, void *user)
1629 {
1630         isl_map *map = *entry;
1631         isl_union_map **res = user;
1632
1633         map = isl_map_universe(isl_map_get_space(map));
1634         *res = isl_union_map_add_map(*res, map);
1635
1636         return 0;
1637 }
1638
1639 __isl_give isl_union_map *isl_union_map_universe(__isl_take isl_union_map *umap)
1640 {
1641         return cond_un_op(umap, &universe_entry);
1642 }
1643
1644 __isl_give isl_union_set *isl_union_set_universe(__isl_take isl_union_set *uset)
1645 {
1646         return isl_union_map_universe(uset);
1647 }
1648
1649 static int reverse_entry(void **entry, void *user)
1650 {
1651         isl_map *map = *entry;
1652         isl_union_map **res = user;
1653
1654         *res = isl_union_map_add_map(*res, isl_map_reverse(isl_map_copy(map)));
1655
1656         return 0;
1657 }
1658
1659 __isl_give isl_union_map *isl_union_map_reverse(__isl_take isl_union_map *umap)
1660 {
1661         return cond_un_op(umap, &reverse_entry);
1662 }
1663
1664 static int params_entry(void **entry, void *user)
1665 {
1666         isl_map *map = *entry;
1667         isl_union_set **res = user;
1668
1669         *res = isl_union_set_add_set(*res, isl_map_params(isl_map_copy(map)));
1670
1671         return 0;
1672 }
1673
1674 /* Compute the parameter domain of the given union map.
1675  */
1676 __isl_give isl_set *isl_union_map_params(__isl_take isl_union_map *umap)
1677 {
1678         int empty;
1679
1680         empty = isl_union_map_is_empty(umap);
1681         if (empty < 0)
1682                 return isl_union_map_free(umap);
1683         if (empty)
1684                 return isl_set_empty(isl_union_map_get_space(umap));
1685         return isl_set_from_union_set(cond_un_op(umap, &params_entry));
1686 }
1687
1688 /* Compute the parameter domain of the given union set.
1689  */
1690 __isl_give isl_set *isl_union_set_params(__isl_take isl_union_set *uset)
1691 {
1692         return isl_union_map_params(uset);
1693 }
1694
1695 static int domain_entry(void **entry, void *user)
1696 {
1697         isl_map *map = *entry;
1698         isl_union_set **res = user;
1699
1700         *res = isl_union_set_add_set(*res, isl_map_domain(isl_map_copy(map)));
1701
1702         return 0;
1703 }
1704
1705 __isl_give isl_union_set *isl_union_map_domain(__isl_take isl_union_map *umap)
1706 {
1707         return cond_un_op(umap, &domain_entry);
1708 }
1709
1710 static int range_entry(void **entry, void *user)
1711 {
1712         isl_map *map = *entry;
1713         isl_union_set **res = user;
1714
1715         *res = isl_union_set_add_set(*res, isl_map_range(isl_map_copy(map)));
1716
1717         return 0;
1718 }
1719
1720 __isl_give isl_union_set *isl_union_map_range(__isl_take isl_union_map *umap)
1721 {
1722         return cond_un_op(umap, &range_entry);
1723 }
1724
1725 static int domain_map_entry(void **entry, void *user)
1726 {
1727         isl_map *map = *entry;
1728         isl_union_set **res = user;
1729
1730         *res = isl_union_map_add_map(*res,
1731                                         isl_map_domain_map(isl_map_copy(map)));
1732
1733         return 0;
1734 }
1735
1736 __isl_give isl_union_map *isl_union_map_domain_map(
1737         __isl_take isl_union_map *umap)
1738 {
1739         return cond_un_op(umap, &domain_map_entry);
1740 }
1741
1742 static int range_map_entry(void **entry, void *user)
1743 {
1744         isl_map *map = *entry;
1745         isl_union_set **res = user;
1746
1747         *res = isl_union_map_add_map(*res,
1748                                         isl_map_range_map(isl_map_copy(map)));
1749
1750         return 0;
1751 }
1752
1753 __isl_give isl_union_map *isl_union_map_range_map(
1754         __isl_take isl_union_map *umap)
1755 {
1756         return cond_un_op(umap, &range_map_entry);
1757 }
1758
1759 static int deltas_entry(void **entry, void *user)
1760 {
1761         isl_map *map = *entry;
1762         isl_union_set **res = user;
1763
1764         if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1765                 return 0;
1766
1767         *res = isl_union_set_add_set(*res, isl_map_deltas(isl_map_copy(map)));
1768
1769         return 0;
1770 }
1771
1772 __isl_give isl_union_set *isl_union_map_deltas(__isl_take isl_union_map *umap)
1773 {
1774         return cond_un_op(umap, &deltas_entry);
1775 }
1776
1777 static int deltas_map_entry(void **entry, void *user)
1778 {
1779         isl_map *map = *entry;
1780         isl_union_map **res = user;
1781
1782         if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1783                 return 0;
1784
1785         *res = isl_union_map_add_map(*res,
1786                                      isl_map_deltas_map(isl_map_copy(map)));
1787
1788         return 0;
1789 }
1790
1791 __isl_give isl_union_map *isl_union_map_deltas_map(
1792         __isl_take isl_union_map *umap)
1793 {
1794         return cond_un_op(umap, &deltas_map_entry);
1795 }
1796
1797 static int identity_entry(void **entry, void *user)
1798 {
1799         isl_set *set = *entry;
1800         isl_union_map **res = user;
1801
1802         *res = isl_union_map_add_map(*res, isl_set_identity(isl_set_copy(set)));
1803
1804         return 0;
1805 }
1806
1807 __isl_give isl_union_map *isl_union_set_identity(__isl_take isl_union_set *uset)
1808 {
1809         return cond_un_op(uset, &identity_entry);
1810 }
1811
1812 static int unwrap_entry(void **entry, void *user)
1813 {
1814         isl_set *set = *entry;
1815         isl_union_set **res = user;
1816
1817         if (!isl_set_is_wrapping(set))
1818                 return 0;
1819
1820         *res = isl_union_map_add_map(*res, isl_set_unwrap(isl_set_copy(set)));
1821
1822         return 0;
1823 }
1824
1825 __isl_give isl_union_map *isl_union_set_unwrap(__isl_take isl_union_set *uset)
1826 {
1827         return cond_un_op(uset, &unwrap_entry);
1828 }
1829
1830 static int wrap_entry(void **entry, void *user)
1831 {
1832         isl_map *map = *entry;
1833         isl_union_set **res = user;
1834
1835         *res = isl_union_set_add_set(*res, isl_map_wrap(isl_map_copy(map)));
1836
1837         return 0;
1838 }
1839
1840 __isl_give isl_union_set *isl_union_map_wrap(__isl_take isl_union_map *umap)
1841 {
1842         return cond_un_op(umap, &wrap_entry);
1843 }
1844
1845 struct isl_union_map_is_subset_data {
1846         isl_union_map *umap2;
1847         int is_subset;
1848 };
1849
1850 static int is_subset_entry(void **entry, void *user)
1851 {
1852         struct isl_union_map_is_subset_data *data = user;
1853         uint32_t hash;
1854         struct isl_hash_table_entry *entry2;
1855         isl_map *map = *entry;
1856
1857         hash = isl_space_get_hash(map->dim);
1858         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1859                                      hash, &has_dim, map->dim, 0);
1860         if (!entry2) {
1861                 int empty = isl_map_is_empty(map);
1862                 if (empty < 0)
1863                         return -1;
1864                 if (empty)
1865                         return 0;
1866                 data->is_subset = 0;
1867                 return -1;
1868         }
1869
1870         data->is_subset = isl_map_is_subset(map, entry2->data);
1871         if (data->is_subset < 0 || !data->is_subset)
1872                 return -1;
1873
1874         return 0;
1875 }
1876
1877 int isl_union_map_is_subset(__isl_keep isl_union_map *umap1,
1878         __isl_keep isl_union_map *umap2)
1879 {
1880         struct isl_union_map_is_subset_data data = { NULL, 1 };
1881
1882         umap1 = isl_union_map_copy(umap1);
1883         umap2 = isl_union_map_copy(umap2);
1884         umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
1885         umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
1886
1887         if (!umap1 || !umap2)
1888                 goto error;
1889
1890         data.umap2 = umap2;
1891         if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1892                                    &is_subset_entry, &data) < 0 &&
1893             data.is_subset)
1894                 goto error;
1895
1896         isl_union_map_free(umap1);
1897         isl_union_map_free(umap2);
1898
1899         return data.is_subset;
1900 error:
1901         isl_union_map_free(umap1);
1902         isl_union_map_free(umap2);
1903         return -1;
1904 }
1905
1906 int isl_union_set_is_subset(__isl_keep isl_union_set *uset1,
1907         __isl_keep isl_union_set *uset2)
1908 {
1909         return isl_union_map_is_subset(uset1, uset2);
1910 }
1911
1912 int isl_union_map_is_equal(__isl_keep isl_union_map *umap1,
1913         __isl_keep isl_union_map *umap2)
1914 {
1915         int is_subset;
1916
1917         if (!umap1 || !umap2)
1918                 return -1;
1919         is_subset = isl_union_map_is_subset(umap1, umap2);
1920         if (is_subset != 1)
1921                 return is_subset;
1922         is_subset = isl_union_map_is_subset(umap2, umap1);
1923         return is_subset;
1924 }
1925
1926 int isl_union_set_is_equal(__isl_keep isl_union_set *uset1,
1927         __isl_keep isl_union_set *uset2)
1928 {
1929         return isl_union_map_is_equal(uset1, uset2);
1930 }
1931
1932 int isl_union_map_is_strict_subset(__isl_keep isl_union_map *umap1,
1933         __isl_keep isl_union_map *umap2)
1934 {
1935         int is_subset;
1936
1937         if (!umap1 || !umap2)
1938                 return -1;
1939         is_subset = isl_union_map_is_subset(umap1, umap2);
1940         if (is_subset != 1)
1941                 return is_subset;
1942         is_subset = isl_union_map_is_subset(umap2, umap1);
1943         if (is_subset == -1)
1944                 return is_subset;
1945         return !is_subset;
1946 }
1947
1948 int isl_union_set_is_strict_subset(__isl_keep isl_union_set *uset1,
1949         __isl_keep isl_union_set *uset2)
1950 {
1951         return isl_union_map_is_strict_subset(uset1, uset2);
1952 }
1953
1954 static int sample_entry(void **entry, void *user)
1955 {
1956         isl_basic_map **sample = (isl_basic_map **)user;
1957         isl_map *map = *entry;
1958
1959         *sample = isl_map_sample(isl_map_copy(map));
1960         if (!*sample)
1961                 return -1;
1962         if (!isl_basic_map_plain_is_empty(*sample))
1963                 return -1;
1964         return 0;
1965 }
1966
1967 __isl_give isl_basic_map *isl_union_map_sample(__isl_take isl_union_map *umap)
1968 {
1969         isl_basic_map *sample = NULL;
1970
1971         if (!umap)
1972                 return NULL;
1973
1974         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1975                                    &sample_entry, &sample) < 0 &&
1976             !sample)
1977                 goto error;
1978
1979         if (!sample)
1980                 sample = isl_basic_map_empty(isl_union_map_get_space(umap));
1981
1982         isl_union_map_free(umap);
1983
1984         return sample;
1985 error:
1986         isl_union_map_free(umap);
1987         return NULL;
1988 }
1989
1990 __isl_give isl_basic_set *isl_union_set_sample(__isl_take isl_union_set *uset)
1991 {
1992         return (isl_basic_set *)isl_union_map_sample(uset);
1993 }
1994
1995 struct isl_forall_data {
1996         int res;
1997         int (*fn)(__isl_keep isl_map *map);
1998 };
1999
2000 static int forall_entry(void **entry, void *user)
2001 {
2002         struct isl_forall_data *data = user;
2003         isl_map *map = *entry;
2004
2005         data->res = data->fn(map);
2006         if (data->res < 0)
2007                 return -1;
2008
2009         if (!data->res)
2010                 return -1;
2011
2012         return 0;
2013 }
2014
2015 static int union_map_forall(__isl_keep isl_union_map *umap,
2016         int (*fn)(__isl_keep isl_map *map))
2017 {
2018         struct isl_forall_data data = { 1, fn };
2019
2020         if (!umap)
2021                 return -1;
2022
2023         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
2024                                    &forall_entry, &data) < 0 && data.res)
2025                 return -1;
2026
2027         return data.res;
2028 }
2029
2030 struct isl_forall_user_data {
2031         int res;
2032         int (*fn)(__isl_keep isl_map *map, void *user);
2033         void *user;
2034 };
2035
2036 static int forall_user_entry(void **entry, void *user)
2037 {
2038         struct isl_forall_user_data *data = user;
2039         isl_map *map = *entry;
2040
2041         data->res = data->fn(map, data->user);
2042         if (data->res < 0)
2043                 return -1;
2044
2045         if (!data->res)
2046                 return -1;
2047
2048         return 0;
2049 }
2050
2051 /* Check if fn(map, user) returns true for all maps "map" in umap.
2052  */
2053 static int union_map_forall_user(__isl_keep isl_union_map *umap,
2054         int (*fn)(__isl_keep isl_map *map, void *user), void *user)
2055 {
2056         struct isl_forall_user_data data = { 1, fn, user };
2057
2058         if (!umap)
2059                 return -1;
2060
2061         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
2062                                    &forall_user_entry, &data) < 0 && data.res)
2063                 return -1;
2064
2065         return data.res;
2066 }
2067
2068 int isl_union_map_is_empty(__isl_keep isl_union_map *umap)
2069 {
2070         return union_map_forall(umap, &isl_map_is_empty);
2071 }
2072
2073 int isl_union_set_is_empty(__isl_keep isl_union_set *uset)
2074 {
2075         return isl_union_map_is_empty(uset);
2076 }
2077
2078 static int is_subset_of_identity(__isl_keep isl_map *map)
2079 {
2080         int is_subset;
2081         isl_space *dim;
2082         isl_map *id;
2083
2084         if (!map)
2085                 return -1;
2086
2087         if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
2088                 return 0;
2089
2090         dim = isl_map_get_space(map);
2091         id = isl_map_identity(dim);
2092
2093         is_subset = isl_map_is_subset(map, id);
2094
2095         isl_map_free(id);
2096
2097         return is_subset;
2098 }
2099
2100 /* Check if the given map is single-valued.
2101  * We simply compute
2102  *
2103  *      M \circ M^-1
2104  *
2105  * and check if the result is a subset of the identity mapping.
2106  */
2107 int isl_union_map_is_single_valued(__isl_keep isl_union_map *umap)
2108 {
2109         isl_union_map *test;
2110         int sv;
2111
2112         if (isl_union_map_n_map(umap) == 1) {
2113                 isl_map *map;
2114                 umap = isl_union_map_copy(umap);
2115                 map = isl_map_from_union_map(umap);
2116                 sv = isl_map_is_single_valued(map);
2117                 isl_map_free(map);
2118                 return sv;
2119         }
2120
2121         test = isl_union_map_reverse(isl_union_map_copy(umap));
2122         test = isl_union_map_apply_range(test, isl_union_map_copy(umap));
2123
2124         sv = union_map_forall(test, &is_subset_of_identity);
2125
2126         isl_union_map_free(test);
2127
2128         return sv;
2129 }
2130
2131 int isl_union_map_is_injective(__isl_keep isl_union_map *umap)
2132 {
2133         int in;
2134
2135         umap = isl_union_map_copy(umap);
2136         umap = isl_union_map_reverse(umap);
2137         in = isl_union_map_is_single_valued(umap);
2138         isl_union_map_free(umap);
2139
2140         return in;
2141 }
2142
2143 /* Represents a map that has a fixed value (v) for one of its
2144  * range dimensions.
2145  * The map in this structure is not reference counted, so it
2146  * is only valid while the isl_union_map from which it was
2147  * obtained is still alive.
2148  */
2149 struct isl_fixed_map {
2150         isl_int v;
2151         isl_map *map;
2152 };
2153
2154 static struct isl_fixed_map *alloc_isl_fixed_map_array(isl_ctx *ctx,
2155         int n)
2156 {
2157         int i;
2158         struct isl_fixed_map *v;
2159
2160         v = isl_calloc_array(ctx, struct isl_fixed_map, n);
2161         if (!v)
2162                 return NULL;
2163         for (i = 0; i < n; ++i)
2164                 isl_int_init(v[i].v);
2165         return v;
2166 }
2167
2168 static void free_isl_fixed_map_array(struct isl_fixed_map *v, int n)
2169 {
2170         int i;
2171
2172         if (!v)
2173                 return;
2174         for (i = 0; i < n; ++i)
2175                 isl_int_clear(v[i].v);
2176         free(v);
2177 }
2178
2179 /* Compare the "v" field of two isl_fixed_map structs.
2180  */
2181 static int qsort_fixed_map_cmp(const void *p1, const void *p2)
2182 {
2183         const struct isl_fixed_map *e1 = (const struct isl_fixed_map *) p1;
2184         const struct isl_fixed_map *e2 = (const struct isl_fixed_map *) p2;
2185
2186         return isl_int_cmp(e1->v, e2->v);
2187 }
2188
2189 /* Internal data structure used while checking whether all maps
2190  * in a union_map have a fixed value for a given output dimension.
2191  * v is the list of maps, with the fixed value for the dimension
2192  * n is the number of maps considered so far
2193  * pos is the output dimension under investigation
2194  */
2195 struct isl_fixed_dim_data {
2196         struct isl_fixed_map *v;
2197         int n;
2198         int pos;
2199 };
2200
2201 static int fixed_at_pos(__isl_keep isl_map *map, void *user)
2202 {
2203         struct isl_fixed_dim_data *data = user;
2204
2205         data->v[data->n].map = map;
2206         return isl_map_plain_is_fixed(map, isl_dim_out, data->pos,
2207                                       &data->v[data->n++].v);
2208 }
2209
2210 static int plain_injective_on_range(__isl_take isl_union_map *umap,
2211         int first, int n_range);
2212
2213 /* Given a list of the maps, with their fixed values at output dimension "pos",
2214  * check whether the ranges of the maps form an obvious partition.
2215  *
2216  * We first sort the maps according to their fixed values.
2217  * If all maps have a different value, then we know the ranges form
2218  * a partition.
2219  * Otherwise, we collect the maps with the same fixed value and
2220  * check whether each such collection is obviously injective
2221  * based on later dimensions.
2222  */
2223 static int separates(struct isl_fixed_map *v, int n,
2224         __isl_take isl_space *dim, int pos, int n_range)
2225 {
2226         int i;
2227
2228         if (!v)
2229                 goto error;
2230
2231         qsort(v, n, sizeof(*v), &qsort_fixed_map_cmp);
2232
2233         for (i = 0; i + 1 < n; ++i) {
2234                 int j, k;
2235                 isl_union_map *part;
2236                 int injective;
2237
2238                 for (j = i + 1; j < n; ++j)
2239                         if (isl_int_ne(v[i].v, v[j].v))
2240                                 break;
2241
2242                 if (j == i + 1)
2243                         continue;
2244
2245                 part = isl_union_map_alloc(isl_space_copy(dim), j - i);
2246                 for (k = i; k < j; ++k)
2247                         part = isl_union_map_add_map(part,
2248                                                      isl_map_copy(v[k].map));
2249
2250                 injective = plain_injective_on_range(part, pos + 1, n_range);
2251                 if (injective < 0)
2252                         goto error;
2253                 if (!injective)
2254                         break;
2255
2256                 i = j - 1;
2257         }
2258
2259         isl_space_free(dim);
2260         free_isl_fixed_map_array(v, n);
2261         return i + 1 >= n;
2262 error:
2263         isl_space_free(dim);
2264         free_isl_fixed_map_array(v, n);
2265         return -1;
2266 }
2267
2268 /* Check whether the maps in umap have obviously distinct ranges.
2269  * In particular, check for an output dimension in the range
2270  * [first,n_range) for which all maps have a fixed value
2271  * and then check if these values, possibly along with fixed values
2272  * at later dimensions, entail distinct ranges.
2273  */
2274 static int plain_injective_on_range(__isl_take isl_union_map *umap,
2275         int first, int n_range)
2276 {
2277         isl_ctx *ctx;
2278         int n;
2279         struct isl_fixed_dim_data data = { NULL };
2280
2281         ctx = isl_union_map_get_ctx(umap);
2282
2283         n = isl_union_map_n_map(umap);
2284         if (!umap)
2285                 goto error;
2286
2287         if (n <= 1) {
2288                 isl_union_map_free(umap);
2289                 return 1;
2290         }
2291
2292         if (first >= n_range) {
2293                 isl_union_map_free(umap);
2294                 return 0;
2295         }
2296
2297         data.v = alloc_isl_fixed_map_array(ctx, n);
2298         if (!data.v)
2299                 goto error;
2300
2301         for (data.pos = first; data.pos < n_range; ++data.pos) {
2302                 int fixed;
2303                 int injective;
2304                 isl_space *dim;
2305
2306                 data.n = 0;
2307                 fixed = union_map_forall_user(umap, &fixed_at_pos, &data);
2308                 if (fixed < 0)
2309                         goto error;
2310                 if (!fixed)
2311                         continue;
2312                 dim = isl_union_map_get_space(umap);
2313                 injective = separates(data.v, n, dim, data.pos, n_range);
2314                 isl_union_map_free(umap);
2315                 return injective;
2316         }
2317
2318         free_isl_fixed_map_array(data.v, n);
2319         isl_union_map_free(umap);
2320
2321         return 0;
2322 error:
2323         free_isl_fixed_map_array(data.v, n);
2324         isl_union_map_free(umap);
2325         return -1;
2326 }
2327
2328 /* Check whether the maps in umap that map to subsets of "ran"
2329  * have obviously distinct ranges.
2330  */
2331 static int plain_injective_on_range_wrap(__isl_keep isl_set *ran, void *user)
2332 {
2333         isl_union_map *umap = user;
2334
2335         umap = isl_union_map_copy(umap);
2336         umap = isl_union_map_intersect_range(umap,
2337                         isl_union_set_from_set(isl_set_copy(ran)));
2338         return plain_injective_on_range(umap, 0, isl_set_dim(ran, isl_dim_set));
2339 }
2340
2341 /* Check if the given union_map is obviously injective.
2342  *
2343  * In particular, we first check if all individual maps are obviously
2344  * injective and then check if all the ranges of these maps are
2345  * obviously disjoint.
2346  */
2347 int isl_union_map_plain_is_injective(__isl_keep isl_union_map *umap)
2348 {
2349         int in;
2350         isl_union_map *univ;
2351         isl_union_set *ran;
2352
2353         in = union_map_forall(umap, &isl_map_plain_is_injective);
2354         if (in < 0)
2355                 return -1;
2356         if (!in)
2357                 return 0;
2358
2359         univ = isl_union_map_universe(isl_union_map_copy(umap));
2360         ran = isl_union_map_range(univ);
2361
2362         in = union_map_forall_user(ran, &plain_injective_on_range_wrap, umap);
2363
2364         isl_union_set_free(ran);
2365
2366         return in;
2367 }
2368
2369 int isl_union_map_is_bijective(__isl_keep isl_union_map *umap)
2370 {
2371         int sv;
2372
2373         sv = isl_union_map_is_single_valued(umap);
2374         if (sv < 0 || !sv)
2375                 return sv;
2376
2377         return isl_union_map_is_injective(umap);
2378 }
2379
2380 static int zip_entry(void **entry, void *user)
2381 {
2382         isl_map *map = *entry;
2383         isl_union_map **res = user;
2384
2385         if (!isl_map_can_zip(map))
2386                 return 0;
2387
2388         *res = isl_union_map_add_map(*res, isl_map_zip(isl_map_copy(map)));
2389
2390         return 0;
2391 }
2392
2393 __isl_give isl_union_map *isl_union_map_zip(__isl_take isl_union_map *umap)
2394 {
2395         return cond_un_op(umap, &zip_entry);
2396 }
2397
2398 static int uncurry_entry(void **entry, void *user)
2399 {
2400         isl_map *map = *entry;
2401         isl_union_map **res = user;
2402
2403         if (!isl_map_can_uncurry(map))
2404                 return 0;
2405
2406         *res = isl_union_map_add_map(*res, isl_map_uncurry(isl_map_copy(map)));
2407
2408         return 0;
2409 }
2410
2411 /* Given a union map, take the maps of the form A -> (B -> C) and
2412  * return the union of the corresponding maps (A -> B) -> C.
2413  */
2414 __isl_give isl_union_map *isl_union_map_uncurry(__isl_take isl_union_map *umap)
2415 {
2416         return cond_un_op(umap, &uncurry_entry);
2417 }
2418
2419 static int curry_entry(void **entry, void *user)
2420 {
2421         isl_map *map = *entry;
2422         isl_union_map **res = user;
2423
2424         if (!isl_map_can_curry(map))
2425                 return 0;
2426
2427         *res = isl_union_map_add_map(*res, isl_map_curry(isl_map_copy(map)));
2428
2429         return 0;
2430 }
2431
2432 /* Given a union map, take the maps of the form (A -> B) -> C and
2433  * return the union of the corresponding maps A -> (B -> C).
2434  */
2435 __isl_give isl_union_map *isl_union_map_curry(__isl_take isl_union_map *umap)
2436 {
2437         return cond_un_op(umap, &curry_entry);
2438 }
2439
2440 static int lift_entry(void **entry, void *user)
2441 {
2442         isl_set *set = *entry;
2443         isl_union_set **res = user;
2444
2445         *res = isl_union_set_add_set(*res, isl_set_lift(isl_set_copy(set)));
2446
2447         return 0;
2448 }
2449
2450 __isl_give isl_union_set *isl_union_set_lift(__isl_take isl_union_set *uset)
2451 {
2452         return cond_un_op(uset, &lift_entry);
2453 }
2454
2455 static int coefficients_entry(void **entry, void *user)
2456 {
2457         isl_set *set = *entry;
2458         isl_union_set **res = user;
2459
2460         set = isl_set_copy(set);
2461         set = isl_set_from_basic_set(isl_set_coefficients(set));
2462         *res = isl_union_set_add_set(*res, set);
2463
2464         return 0;
2465 }
2466
2467 __isl_give isl_union_set *isl_union_set_coefficients(
2468         __isl_take isl_union_set *uset)
2469 {
2470         isl_ctx *ctx;
2471         isl_space *dim;
2472         isl_union_set *res;
2473
2474         if (!uset)
2475                 return NULL;
2476
2477         ctx = isl_union_set_get_ctx(uset);
2478         dim = isl_space_set_alloc(ctx, 0, 0);
2479         res = isl_union_map_alloc(dim, uset->table.n);
2480         if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
2481                                    &coefficients_entry, &res) < 0)
2482                 goto error;
2483
2484         isl_union_set_free(uset);
2485         return res;
2486 error:
2487         isl_union_set_free(uset);
2488         isl_union_set_free(res);
2489         return NULL;
2490 }
2491
2492 static int solutions_entry(void **entry, void *user)
2493 {
2494         isl_set *set = *entry;
2495         isl_union_set **res = user;
2496
2497         set = isl_set_copy(set);
2498         set = isl_set_from_basic_set(isl_set_solutions(set));
2499         if (!*res)
2500                 *res = isl_union_set_from_set(set);
2501         else
2502                 *res = isl_union_set_add_set(*res, set);
2503
2504         if (!*res)
2505                 return -1;
2506
2507         return 0;
2508 }
2509
2510 __isl_give isl_union_set *isl_union_set_solutions(
2511         __isl_take isl_union_set *uset)
2512 {
2513         isl_union_set *res = NULL;
2514
2515         if (!uset)
2516                 return NULL;
2517
2518         if (uset->table.n == 0) {
2519                 res = isl_union_set_empty(isl_union_set_get_space(uset));
2520                 isl_union_set_free(uset);
2521                 return res;
2522         }
2523
2524         if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
2525                                    &solutions_entry, &res) < 0)
2526                 goto error;
2527
2528         isl_union_set_free(uset);
2529         return res;
2530 error:
2531         isl_union_set_free(uset);
2532         isl_union_set_free(res);
2533         return NULL;
2534 }