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