isl_union_map.c

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