isl_union_map.c

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