isl_union_map.c

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