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