isl_union_map.c

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