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                 return isl_set_empty(isl_union_map_get_space(umap));
1683         return isl_set_from_union_set(cond_un_op(umap, &params_entry));
1684 }
1685
1686 /* Compute the parameter domain of the given union set.
1687  */
1688 __isl_give isl_set *isl_union_set_params(__isl_take isl_union_set *uset)
1689 {
1690         return isl_union_map_params(uset);
1691 }
1692
1693 static int domain_entry(void **entry, void *user)
1694 {
1695         isl_map *map = *entry;
1696         isl_union_set **res = user;
1697
1698         *res = isl_union_set_add_set(*res, isl_map_domain(isl_map_copy(map)));
1699
1700         return 0;
1701 }
1702
1703 __isl_give isl_union_set *isl_union_map_domain(__isl_take isl_union_map *umap)
1704 {
1705         return cond_un_op(umap, &domain_entry);
1706 }
1707
1708 static int range_entry(void **entry, void *user)
1709 {
1710         isl_map *map = *entry;
1711         isl_union_set **res = user;
1712
1713         *res = isl_union_set_add_set(*res, isl_map_range(isl_map_copy(map)));
1714
1715         return 0;
1716 }
1717
1718 __isl_give isl_union_set *isl_union_map_range(__isl_take isl_union_map *umap)
1719 {
1720         return cond_un_op(umap, &range_entry);
1721 }
1722
1723 static int domain_map_entry(void **entry, void *user)
1724 {
1725         isl_map *map = *entry;
1726         isl_union_set **res = user;
1727
1728         *res = isl_union_map_add_map(*res,
1729                                         isl_map_domain_map(isl_map_copy(map)));
1730
1731         return 0;
1732 }
1733
1734 __isl_give isl_union_map *isl_union_map_domain_map(
1735         __isl_take isl_union_map *umap)
1736 {
1737         return cond_un_op(umap, &domain_map_entry);
1738 }
1739
1740 static int range_map_entry(void **entry, void *user)
1741 {
1742         isl_map *map = *entry;
1743         isl_union_set **res = user;
1744
1745         *res = isl_union_map_add_map(*res,
1746                                         isl_map_range_map(isl_map_copy(map)));
1747
1748         return 0;
1749 }
1750
1751 __isl_give isl_union_map *isl_union_map_range_map(
1752         __isl_take isl_union_map *umap)
1753 {
1754         return cond_un_op(umap, &range_map_entry);
1755 }
1756
1757 static int deltas_entry(void **entry, void *user)
1758 {
1759         isl_map *map = *entry;
1760         isl_union_set **res = user;
1761
1762         if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1763                 return 0;
1764
1765         *res = isl_union_set_add_set(*res, isl_map_deltas(isl_map_copy(map)));
1766
1767         return 0;
1768 }
1769
1770 __isl_give isl_union_set *isl_union_map_deltas(__isl_take isl_union_map *umap)
1771 {
1772         return cond_un_op(umap, &deltas_entry);
1773 }
1774
1775 static int deltas_map_entry(void **entry, void *user)
1776 {
1777         isl_map *map = *entry;
1778         isl_union_map **res = user;
1779
1780         if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1781                 return 0;
1782
1783         *res = isl_union_map_add_map(*res,
1784                                      isl_map_deltas_map(isl_map_copy(map)));
1785
1786         return 0;
1787 }
1788
1789 __isl_give isl_union_map *isl_union_map_deltas_map(
1790         __isl_take isl_union_map *umap)
1791 {
1792         return cond_un_op(umap, &deltas_map_entry);
1793 }
1794
1795 static int identity_entry(void **entry, void *user)
1796 {
1797         isl_set *set = *entry;
1798         isl_union_map **res = user;
1799
1800         *res = isl_union_map_add_map(*res, isl_set_identity(isl_set_copy(set)));
1801
1802         return 0;
1803 }
1804
1805 __isl_give isl_union_map *isl_union_set_identity(__isl_take isl_union_set *uset)
1806 {
1807         return cond_un_op(uset, &identity_entry);
1808 }
1809
1810 static int unwrap_entry(void **entry, void *user)
1811 {
1812         isl_set *set = *entry;
1813         isl_union_set **res = user;
1814
1815         if (!isl_set_is_wrapping(set))
1816                 return 0;
1817
1818         *res = isl_union_map_add_map(*res, isl_set_unwrap(isl_set_copy(set)));
1819
1820         return 0;
1821 }
1822
1823 __isl_give isl_union_map *isl_union_set_unwrap(__isl_take isl_union_set *uset)
1824 {
1825         return cond_un_op(uset, &unwrap_entry);
1826 }
1827
1828 static int wrap_entry(void **entry, void *user)
1829 {
1830         isl_map *map = *entry;
1831         isl_union_set **res = user;
1832
1833         *res = isl_union_set_add_set(*res, isl_map_wrap(isl_map_copy(map)));
1834
1835         return 0;
1836 }
1837
1838 __isl_give isl_union_set *isl_union_map_wrap(__isl_take isl_union_map *umap)
1839 {
1840         return cond_un_op(umap, &wrap_entry);
1841 }
1842
1843 struct isl_union_map_is_subset_data {
1844         isl_union_map *umap2;
1845         int is_subset;
1846 };
1847
1848 static int is_subset_entry(void **entry, void *user)
1849 {
1850         struct isl_union_map_is_subset_data *data = user;
1851         uint32_t hash;
1852         struct isl_hash_table_entry *entry2;
1853         isl_map *map = *entry;
1854
1855         hash = isl_space_get_hash(map->dim);
1856         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1857                                      hash, &has_dim, map->dim, 0);
1858         if (!entry2) {
1859                 int empty = isl_map_is_empty(map);
1860                 if (empty < 0)
1861                         return -1;
1862                 if (empty)
1863                         return 0;
1864                 data->is_subset = 0;
1865                 return -1;
1866         }
1867
1868         data->is_subset = isl_map_is_subset(map, entry2->data);
1869         if (data->is_subset < 0 || !data->is_subset)
1870                 return -1;
1871
1872         return 0;
1873 }
1874
1875 int isl_union_map_is_subset(__isl_keep isl_union_map *umap1,
1876         __isl_keep isl_union_map *umap2)
1877 {
1878         struct isl_union_map_is_subset_data data = { NULL, 1 };
1879
1880         umap1 = isl_union_map_copy(umap1);
1881         umap2 = isl_union_map_copy(umap2);
1882         umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
1883         umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
1884
1885         if (!umap1 || !umap2)
1886                 goto error;
1887
1888         data.umap2 = umap2;
1889         if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1890                                    &is_subset_entry, &data) < 0 &&
1891             data.is_subset)
1892                 goto error;
1893
1894         isl_union_map_free(umap1);
1895         isl_union_map_free(umap2);
1896
1897         return data.is_subset;
1898 error:
1899         isl_union_map_free(umap1);
1900         isl_union_map_free(umap2);
1901         return -1;
1902 }
1903
1904 int isl_union_set_is_subset(__isl_keep isl_union_set *uset1,
1905         __isl_keep isl_union_set *uset2)
1906 {
1907         return isl_union_map_is_subset(uset1, uset2);
1908 }
1909
1910 int isl_union_map_is_equal(__isl_keep isl_union_map *umap1,
1911         __isl_keep isl_union_map *umap2)
1912 {
1913         int is_subset;
1914
1915         if (!umap1 || !umap2)
1916                 return -1;
1917         is_subset = isl_union_map_is_subset(umap1, umap2);
1918         if (is_subset != 1)
1919                 return is_subset;
1920         is_subset = isl_union_map_is_subset(umap2, umap1);
1921         return is_subset;
1922 }
1923
1924 int isl_union_set_is_equal(__isl_keep isl_union_set *uset1,
1925         __isl_keep isl_union_set *uset2)
1926 {
1927         return isl_union_map_is_equal(uset1, uset2);
1928 }
1929
1930 int isl_union_map_is_strict_subset(__isl_keep isl_union_map *umap1,
1931         __isl_keep isl_union_map *umap2)
1932 {
1933         int is_subset;
1934
1935         if (!umap1 || !umap2)
1936                 return -1;
1937         is_subset = isl_union_map_is_subset(umap1, umap2);
1938         if (is_subset != 1)
1939                 return is_subset;
1940         is_subset = isl_union_map_is_subset(umap2, umap1);
1941         if (is_subset == -1)
1942                 return is_subset;
1943         return !is_subset;
1944 }
1945
1946 int isl_union_set_is_strict_subset(__isl_keep isl_union_set *uset1,
1947         __isl_keep isl_union_set *uset2)
1948 {
1949         return isl_union_map_is_strict_subset(uset1, uset2);
1950 }
1951
1952 static int sample_entry(void **entry, void *user)
1953 {
1954         isl_basic_map **sample = (isl_basic_map **)user;
1955         isl_map *map = *entry;
1956
1957         *sample = isl_map_sample(isl_map_copy(map));
1958         if (!*sample)
1959                 return -1;
1960         if (!isl_basic_map_plain_is_empty(*sample))
1961                 return -1;
1962         return 0;
1963 }
1964
1965 __isl_give isl_basic_map *isl_union_map_sample(__isl_take isl_union_map *umap)
1966 {
1967         isl_basic_map *sample = NULL;
1968
1969         if (!umap)
1970                 return NULL;
1971
1972         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1973                                    &sample_entry, &sample) < 0 &&
1974             !sample)
1975                 goto error;
1976
1977         if (!sample)
1978                 sample = isl_basic_map_empty(isl_union_map_get_space(umap));
1979
1980         isl_union_map_free(umap);
1981
1982         return sample;
1983 error:
1984         isl_union_map_free(umap);
1985         return NULL;
1986 }
1987
1988 __isl_give isl_basic_set *isl_union_set_sample(__isl_take isl_union_set *uset)
1989 {
1990         return (isl_basic_set *)isl_union_map_sample(uset);
1991 }
1992
1993 struct isl_forall_data {
1994         int res;
1995         int (*fn)(__isl_keep isl_map *map);
1996 };
1997
1998 static int forall_entry(void **entry, void *user)
1999 {
2000         struct isl_forall_data *data = user;
2001         isl_map *map = *entry;
2002
2003         data->res = data->fn(map);
2004         if (data->res < 0)
2005                 return -1;
2006
2007         if (!data->res)
2008                 return -1;
2009
2010         return 0;
2011 }
2012
2013 static int union_map_forall(__isl_keep isl_union_map *umap,
2014         int (*fn)(__isl_keep isl_map *map))
2015 {
2016         struct isl_forall_data data = { 1, fn };
2017
2018         if (!umap)
2019                 return -1;
2020
2021         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
2022                                    &forall_entry, &data) < 0 && data.res)
2023                 return -1;
2024
2025         return data.res;
2026 }
2027
2028 struct isl_forall_user_data {
2029         int res;
2030         int (*fn)(__isl_keep isl_map *map, void *user);
2031         void *user;
2032 };
2033
2034 static int forall_user_entry(void **entry, void *user)
2035 {
2036         struct isl_forall_user_data *data = user;
2037         isl_map *map = *entry;
2038
2039         data->res = data->fn(map, data->user);
2040         if (data->res < 0)
2041                 return -1;
2042
2043         if (!data->res)
2044                 return -1;
2045
2046         return 0;
2047 }
2048
2049 /* Check if fn(map, user) returns true for all maps "map" in umap.
2050  */
2051 static int union_map_forall_user(__isl_keep isl_union_map *umap,
2052         int (*fn)(__isl_keep isl_map *map, void *user), void *user)
2053 {
2054         struct isl_forall_user_data data = { 1, fn, user };
2055
2056         if (!umap)
2057                 return -1;
2058
2059         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
2060                                    &forall_user_entry, &data) < 0 && data.res)
2061                 return -1;
2062
2063         return data.res;
2064 }
2065
2066 int isl_union_map_is_empty(__isl_keep isl_union_map *umap)
2067 {
2068         return union_map_forall(umap, &isl_map_is_empty);
2069 }
2070
2071 int isl_union_set_is_empty(__isl_keep isl_union_set *uset)
2072 {
2073         return isl_union_map_is_empty(uset);
2074 }
2075
2076 static int is_subset_of_identity(__isl_keep isl_map *map)
2077 {
2078         int is_subset;
2079         isl_space *dim;
2080         isl_map *id;
2081
2082         if (!map)
2083                 return -1;
2084
2085         if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
2086                 return 0;
2087
2088         dim = isl_map_get_space(map);
2089         id = isl_map_identity(dim);
2090
2091         is_subset = isl_map_is_subset(map, id);
2092
2093         isl_map_free(id);
2094
2095         return is_subset;
2096 }
2097
2098 /* Check if the given map is single-valued.
2099  * We simply compute
2100  *
2101  *      M \circ M^-1
2102  *
2103  * and check if the result is a subset of the identity mapping.
2104  */
2105 int isl_union_map_is_single_valued(__isl_keep isl_union_map *umap)
2106 {
2107         isl_union_map *test;
2108         int sv;
2109
2110         if (isl_union_map_n_map(umap) == 1) {
2111                 isl_map *map;
2112                 umap = isl_union_map_copy(umap);
2113                 map = isl_map_from_union_map(umap);
2114                 sv = isl_map_is_single_valued(map);
2115                 isl_map_free(map);
2116                 return sv;
2117         }
2118
2119         test = isl_union_map_reverse(isl_union_map_copy(umap));
2120         test = isl_union_map_apply_range(test, isl_union_map_copy(umap));
2121
2122         sv = union_map_forall(test, &is_subset_of_identity);
2123
2124         isl_union_map_free(test);
2125
2126         return sv;
2127 }
2128
2129 int isl_union_map_is_injective(__isl_keep isl_union_map *umap)
2130 {
2131         int in;
2132
2133         umap = isl_union_map_copy(umap);
2134         umap = isl_union_map_reverse(umap);
2135         in = isl_union_map_is_single_valued(umap);
2136         isl_union_map_free(umap);
2137
2138         return in;
2139 }
2140
2141 /* Represents a map that has a fixed value (v) for one of its
2142  * range dimensions.
2143  * The map in this structure is not reference counted, so it
2144  * is only valid while the isl_union_map from which it was
2145  * obtained is still alive.
2146  */
2147 struct isl_fixed_map {
2148         isl_int v;
2149         isl_map *map;
2150 };
2151
2152 static struct isl_fixed_map *alloc_isl_fixed_map_array(isl_ctx *ctx,
2153         int n)
2154 {
2155         int i;
2156         struct isl_fixed_map *v;
2157
2158         v = isl_calloc_array(ctx, struct isl_fixed_map, n);
2159         if (!v)
2160                 return NULL;
2161         for (i = 0; i < n; ++i)
2162                 isl_int_init(v[i].v);
2163         return v;
2164 }
2165
2166 static void free_isl_fixed_map_array(struct isl_fixed_map *v, int n)
2167 {
2168         int i;
2169
2170         if (!v)
2171                 return;
2172         for (i = 0; i < n; ++i)
2173                 isl_int_clear(v[i].v);
2174         free(v);
2175 }
2176
2177 /* Compare the "v" field of two isl_fixed_map structs.
2178  */
2179 static int qsort_fixed_map_cmp(const void *p1, const void *p2)
2180 {
2181         const struct isl_fixed_map *e1 = (const struct isl_fixed_map *) p1;
2182         const struct isl_fixed_map *e2 = (const struct isl_fixed_map *) p2;
2183
2184         return isl_int_cmp(e1->v, e2->v);
2185 }
2186
2187 /* Internal data structure used while checking whether all maps
2188  * in a union_map have a fixed value for a given output dimension.
2189  * v is the list of maps, with the fixed value for the dimension
2190  * n is the number of maps considered so far
2191  * pos is the output dimension under investigation
2192  */
2193 struct isl_fixed_dim_data {
2194         struct isl_fixed_map *v;
2195         int n;
2196         int pos;
2197 };
2198
2199 static int fixed_at_pos(__isl_keep isl_map *map, void *user)
2200 {
2201         struct isl_fixed_dim_data *data = user;
2202
2203         data->v[data->n].map = map;
2204         return isl_map_plain_is_fixed(map, isl_dim_out, data->pos,
2205                                       &data->v[data->n++].v);
2206 }
2207
2208 static int plain_injective_on_range(__isl_take isl_union_map *umap,
2209         int first, int n_range);
2210
2211 /* Given a list of the maps, with their fixed values at output dimension "pos",
2212  * check whether the ranges of the maps form an obvious partition.
2213  *
2214  * We first sort the maps according to their fixed values.
2215  * If all maps have a different value, then we know the ranges form
2216  * a partition.
2217  * Otherwise, we collect the maps with the same fixed value and
2218  * check whether each such collection is obviously injective
2219  * based on later dimensions.
2220  */
2221 static int separates(struct isl_fixed_map *v, int n,
2222         __isl_take isl_space *dim, int pos, int n_range)
2223 {
2224         int i;
2225
2226         if (!v)
2227                 goto error;
2228
2229         qsort(v, n, sizeof(*v), &qsort_fixed_map_cmp);
2230
2231         for (i = 0; i + 1 < n; ++i) {
2232                 int j, k;
2233                 isl_union_map *part;
2234                 int injective;
2235
2236                 for (j = i + 1; j < n; ++j)
2237                         if (isl_int_ne(v[i].v, v[j].v))
2238                                 break;
2239
2240                 if (j == i + 1)
2241                         continue;
2242
2243                 part = isl_union_map_alloc(isl_space_copy(dim), j - i);
2244                 for (k = i; k < j; ++k)
2245                         part = isl_union_map_add_map(part,
2246                                                      isl_map_copy(v[k].map));
2247
2248                 injective = plain_injective_on_range(part, pos + 1, n_range);
2249                 if (injective < 0)
2250                         goto error;
2251                 if (!injective)
2252                         break;
2253
2254                 i = j - 1;
2255         }
2256
2257         isl_space_free(dim);
2258         free_isl_fixed_map_array(v, n);
2259         return i + 1 >= n;
2260 error:
2261         isl_space_free(dim);
2262         free_isl_fixed_map_array(v, n);
2263         return -1;
2264 }
2265
2266 /* Check whether the maps in umap have obviously distinct ranges.
2267  * In particular, check for an output dimension in the range
2268  * [first,n_range) for which all maps have a fixed value
2269  * and then check if these values, possibly along with fixed values
2270  * at later dimensions, entail distinct ranges.
2271  */
2272 static int plain_injective_on_range(__isl_take isl_union_map *umap,
2273         int first, int n_range)
2274 {
2275         isl_ctx *ctx;
2276         int n;
2277         struct isl_fixed_dim_data data = { NULL };
2278
2279         ctx = isl_union_map_get_ctx(umap);
2280
2281         n = isl_union_map_n_map(umap);
2282         if (!umap)
2283                 goto error;
2284
2285         if (n <= 1) {
2286                 isl_union_map_free(umap);
2287                 return 1;
2288         }
2289
2290         if (first >= n_range) {
2291                 isl_union_map_free(umap);
2292                 return 0;
2293         }
2294
2295         data.v = alloc_isl_fixed_map_array(ctx, n);
2296         if (!data.v)
2297                 goto error;
2298
2299         for (data.pos = first; data.pos < n_range; ++data.pos) {
2300                 int fixed;
2301                 int injective;
2302                 isl_space *dim;
2303
2304                 data.n = 0;
2305                 fixed = union_map_forall_user(umap, &fixed_at_pos, &data);
2306                 if (fixed < 0)
2307                         goto error;
2308                 if (!fixed)
2309                         continue;
2310                 dim = isl_union_map_get_space(umap);
2311                 injective = separates(data.v, n, dim, data.pos, n_range);
2312                 isl_union_map_free(umap);
2313                 return injective;
2314         }
2315
2316         free_isl_fixed_map_array(data.v, n);
2317         isl_union_map_free(umap);
2318
2319         return 0;
2320 error:
2321         free_isl_fixed_map_array(data.v, n);
2322         isl_union_map_free(umap);
2323         return -1;
2324 }
2325
2326 /* Check whether the maps in umap that map to subsets of "ran"
2327  * have obviously distinct ranges.
2328  */
2329 static int plain_injective_on_range_wrap(__isl_keep isl_set *ran, void *user)
2330 {
2331         isl_union_map *umap = user;
2332
2333         umap = isl_union_map_copy(umap);
2334         umap = isl_union_map_intersect_range(umap,
2335                         isl_union_set_from_set(isl_set_copy(ran)));
2336         return plain_injective_on_range(umap, 0, isl_set_dim(ran, isl_dim_set));
2337 }
2338
2339 /* Check if the given union_map is obviously injective.
2340  *
2341  * In particular, we first check if all individual maps are obviously
2342  * injective and then check if all the ranges of these maps are
2343  * obviously disjoint.
2344  */
2345 int isl_union_map_plain_is_injective(__isl_keep isl_union_map *umap)
2346 {
2347         int in;
2348         isl_union_map *univ;
2349         isl_union_set *ran;
2350
2351         in = union_map_forall(umap, &isl_map_plain_is_injective);
2352         if (in < 0)
2353                 return -1;
2354         if (!in)
2355                 return 0;
2356
2357         univ = isl_union_map_universe(isl_union_map_copy(umap));
2358         ran = isl_union_map_range(univ);
2359
2360         in = union_map_forall_user(ran, &plain_injective_on_range_wrap, umap);
2361
2362         isl_union_set_free(ran);
2363
2364         return in;
2365 }
2366
2367 int isl_union_map_is_bijective(__isl_keep isl_union_map *umap)
2368 {
2369         int sv;
2370
2371         sv = isl_union_map_is_single_valued(umap);
2372         if (sv < 0 || !sv)
2373                 return sv;
2374
2375         return isl_union_map_is_injective(umap);
2376 }
2377
2378 static int zip_entry(void **entry, void *user)
2379 {
2380         isl_map *map = *entry;
2381         isl_union_map **res = user;
2382
2383         if (!isl_map_can_zip(map))
2384                 return 0;
2385
2386         *res = isl_union_map_add_map(*res, isl_map_zip(isl_map_copy(map)));
2387
2388         return 0;
2389 }
2390
2391 __isl_give isl_union_map *isl_union_map_zip(__isl_take isl_union_map *umap)
2392 {
2393         return cond_un_op(umap, &zip_entry);
2394 }
2395
2396 static int uncurry_entry(void **entry, void *user)
2397 {
2398         isl_map *map = *entry;
2399         isl_union_map **res = user;
2400
2401         if (!isl_map_can_uncurry(map))
2402                 return 0;
2403
2404         *res = isl_union_map_add_map(*res, isl_map_uncurry(isl_map_copy(map)));
2405
2406         return 0;
2407 }
2408
2409 /* Given a union map, take the maps of the form A -> (B -> C) and
2410  * return the union of the corresponding maps (A -> B) -> C.
2411  */
2412 __isl_give isl_union_map *isl_union_map_uncurry(__isl_take isl_union_map *umap)
2413 {
2414         return cond_un_op(umap, &uncurry_entry);
2415 }
2416
2417 static int curry_entry(void **entry, void *user)
2418 {
2419         isl_map *map = *entry;
2420         isl_union_map **res = user;
2421
2422         if (!isl_map_can_curry(map))
2423                 return 0;
2424
2425         *res = isl_union_map_add_map(*res, isl_map_curry(isl_map_copy(map)));
2426
2427         return 0;
2428 }
2429
2430 /* Given a union map, take the maps of the form (A -> B) -> C and
2431  * return the union of the corresponding maps A -> (B -> C).
2432  */
2433 __isl_give isl_union_map *isl_union_map_curry(__isl_take isl_union_map *umap)
2434 {
2435         return cond_un_op(umap, &curry_entry);
2436 }
2437
2438 static int lift_entry(void **entry, void *user)
2439 {
2440         isl_set *set = *entry;
2441         isl_union_set **res = user;
2442
2443         *res = isl_union_set_add_set(*res, isl_set_lift(isl_set_copy(set)));
2444
2445         return 0;
2446 }
2447
2448 __isl_give isl_union_set *isl_union_set_lift(__isl_take isl_union_set *uset)
2449 {
2450         return cond_un_op(uset, &lift_entry);
2451 }
2452
2453 static int coefficients_entry(void **entry, void *user)
2454 {
2455         isl_set *set = *entry;
2456         isl_union_set **res = user;
2457
2458         set = isl_set_copy(set);
2459         set = isl_set_from_basic_set(isl_set_coefficients(set));
2460         *res = isl_union_set_add_set(*res, set);
2461
2462         return 0;
2463 }
2464
2465 __isl_give isl_union_set *isl_union_set_coefficients(
2466         __isl_take isl_union_set *uset)
2467 {
2468         isl_ctx *ctx;
2469         isl_space *dim;
2470         isl_union_set *res;
2471
2472         if (!uset)
2473                 return NULL;
2474
2475         ctx = isl_union_set_get_ctx(uset);
2476         dim = isl_space_set_alloc(ctx, 0, 0);
2477         res = isl_union_map_alloc(dim, uset->table.n);
2478         if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
2479                                    &coefficients_entry, &res) < 0)
2480                 goto error;
2481
2482         isl_union_set_free(uset);
2483         return res;
2484 error:
2485         isl_union_set_free(uset);
2486         isl_union_set_free(res);
2487         return NULL;
2488 }
2489
2490 static int solutions_entry(void **entry, void *user)
2491 {
2492         isl_set *set = *entry;
2493         isl_union_set **res = user;
2494
2495         set = isl_set_copy(set);
2496         set = isl_set_from_basic_set(isl_set_solutions(set));
2497         if (!*res)
2498                 *res = isl_union_set_from_set(set);
2499         else
2500                 *res = isl_union_set_add_set(*res, set);
2501
2502         if (!*res)
2503                 return -1;
2504
2505         return 0;
2506 }
2507
2508 __isl_give isl_union_set *isl_union_set_solutions(
2509         __isl_take isl_union_set *uset)
2510 {
2511         isl_union_set *res = NULL;
2512
2513         if (!uset)
2514                 return NULL;
2515
2516         if (uset->table.n == 0) {
2517                 res = isl_union_set_empty(isl_union_set_get_space(uset));
2518                 isl_union_set_free(uset);
2519                 return res;
2520         }
2521
2522         if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
2523                                    &solutions_entry, &res) < 0)
2524                 goto error;
2525
2526         isl_union_set_free(uset);
2527         return res;
2528 error:
2529         isl_union_set_free(uset);
2530         isl_union_set_free(res);
2531         return NULL;
2532 }
2533
2534 /* Internal data structure for isl_union_map_preimage_domain_multi_aff.
2535  *
2536  * "ma" is the function under which the preimage should be taken.
2537  * "space" is the space of "ma".
2538  * "res" collects the results.
2539  */
2540 struct isl_union_map_preimage_domain_data {
2541         isl_space *space;
2542         isl_multi_aff *ma;
2543         isl_union_map *res;
2544 };
2545
2546 /* Compute the preimage of the domain of *entry under the function
2547  * represented by data->ma, provided the domain space of *entry
2548  * match the target space of data->ma, and add the result to data->res.
2549  */
2550 static int preimage_domain_entry(void **entry, void *user)
2551 {
2552         int m;
2553         isl_map *map = *entry;
2554         struct isl_union_map_preimage_domain_data *data = user;
2555         int empty;
2556
2557         m = isl_space_tuple_match(map->dim, isl_dim_in,
2558                                         data->space, isl_dim_out);
2559         if (m < 0)
2560                 return -1;
2561         if (!m)
2562                 return 0;
2563
2564         map = isl_map_copy(map);
2565         map = isl_map_preimage_domain_multi_aff(map,
2566                                                 isl_multi_aff_copy(data->ma));
2567
2568         empty = isl_map_is_empty(map);
2569         if (empty < 0 || empty) {
2570                 isl_map_free(map);
2571                 return empty < 0 ? -1 : 0;
2572         }
2573
2574         data->res = isl_union_map_add_map(data->res, map);
2575
2576         return 0;
2577 }
2578
2579 /* Compute the preimage of the domain of "umap" under the function
2580  * represented by "ma".
2581  * In other words, plug in "ma" in the domain of "umap".
2582  * The result contains maps that live in the same spaces as the maps of "umap"
2583  * with domain space equal to the target space of "ma",
2584  * except that the domain has been replaced by the domain space of "ma".
2585  */
2586 __isl_give isl_union_map *isl_union_map_preimage_domain_multi_aff(
2587         __isl_take isl_union_map *umap, __isl_take isl_multi_aff *ma)
2588 {
2589         isl_ctx *ctx;
2590         isl_space *space;
2591         struct isl_union_map_preimage_domain_data data;
2592
2593         if (!umap || !ma)
2594                 goto error;
2595
2596         ctx = isl_union_map_get_ctx(umap);
2597         space = isl_union_map_get_space(umap);
2598         data.space = isl_multi_aff_get_space(ma);
2599         data.ma = ma;
2600         data.res = isl_union_map_alloc(space, umap->table.n);
2601         if (isl_hash_table_foreach(ctx, &umap->table, &preimage_domain_entry,
2602                                         &data) < 0)
2603                 data.res = isl_union_map_free(data.res);
2604
2605         isl_space_free(data.space);
2606         isl_union_map_free(umap);
2607         isl_multi_aff_free(ma);
2608         return data.res;
2609 error:
2610         isl_union_map_free(umap);
2611         isl_multi_aff_free(ma);
2612         return NULL;
2613 }