isl_union_map.c

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