isl_union_map.c

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