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