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