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 static __isl_give isl_union_set *cond_un_op(__isl_take isl_union_map *umap,
 992         int (*fn)(void **, void *))
 993 {
 994         isl_union_set *res;
 995
 996         if (!umap)
 997                 return NULL;
 998
 999         res = isl_union_map_alloc(isl_space_copy(umap->dim), umap->table.n);
1000         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, &res) < 0)
1001                 goto error;
1002
1003         isl_union_map_free(umap);
1004         return res;
1005 error:
1006         isl_union_map_free(umap);
1007         isl_union_set_free(res);
1008         return NULL;
1009 }
1010
1011 static int from_range_entry(void **entry, void *user)
1012 {
1013         isl_map *set = *entry;
1014         isl_union_set **res = user;
1015
1016         *res = isl_union_map_add_map(*res,
1017                                         isl_map_from_range(isl_set_copy(set)));
1018
1019         return 0;
1020 }
1021
1022 __isl_give isl_union_map *isl_union_map_from_range(
1023         __isl_take isl_union_set *uset)
1024 {
1025         return cond_un_op(uset, &from_range_entry);
1026 }
1027
1028 __isl_give isl_union_map *isl_union_map_from_domain(
1029         __isl_take isl_union_set *uset)
1030 {
1031         return isl_union_map_reverse(isl_union_map_from_range(uset));
1032 }
1033
1034 __isl_give isl_union_map *isl_union_map_from_domain_and_range(
1035         __isl_take isl_union_set *domain, __isl_take isl_union_set *range)
1036 {
1037         return isl_union_map_apply_range(isl_union_map_from_domain(domain),
1038                                          isl_union_map_from_range(range));
1039 }
1040
1041 static __isl_give isl_union_map *un_op(__isl_take isl_union_map *umap,
1042         int (*fn)(void **, void *))
1043 {
1044         umap = isl_union_map_cow(umap);
1045         if (!umap)
1046                 return NULL;
1047
1048         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, NULL) < 0)
1049                 goto error;
1050
1051         return umap;
1052 error:
1053         isl_union_map_free(umap);
1054         return NULL;
1055 }
1056
1057 static int affine_entry(void **entry, void *user)
1058 {
1059         isl_map **map = (isl_map **)entry;
1060
1061         *map = isl_map_from_basic_map(isl_map_affine_hull(*map));
1062
1063         return *map ? 0 : -1;
1064 }
1065
1066 __isl_give isl_union_map *isl_union_map_affine_hull(
1067         __isl_take isl_union_map *umap)
1068 {
1069         return un_op(umap, &affine_entry);
1070 }
1071
1072 __isl_give isl_union_set *isl_union_set_affine_hull(
1073         __isl_take isl_union_set *uset)
1074 {
1075         return isl_union_map_affine_hull(uset);
1076 }
1077
1078 static int polyhedral_entry(void **entry, void *user)
1079 {
1080         isl_map **map = (isl_map **)entry;
1081
1082         *map = isl_map_from_basic_map(isl_map_polyhedral_hull(*map));
1083
1084         return *map ? 0 : -1;
1085 }
1086
1087 __isl_give isl_union_map *isl_union_map_polyhedral_hull(
1088         __isl_take isl_union_map *umap)
1089 {
1090         return un_op(umap, &polyhedral_entry);
1091 }
1092
1093 __isl_give isl_union_set *isl_union_set_polyhedral_hull(
1094         __isl_take isl_union_set *uset)
1095 {
1096         return isl_union_map_polyhedral_hull(uset);
1097 }
1098
1099 static int simple_entry(void **entry, void *user)
1100 {
1101         isl_map **map = (isl_map **)entry;
1102
1103         *map = isl_map_from_basic_map(isl_map_simple_hull(*map));
1104
1105         return *map ? 0 : -1;
1106 }
1107
1108 __isl_give isl_union_map *isl_union_map_simple_hull(
1109         __isl_take isl_union_map *umap)
1110 {
1111         return un_op(umap, &simple_entry);
1112 }
1113
1114 __isl_give isl_union_set *isl_union_set_simple_hull(
1115         __isl_take isl_union_set *uset)
1116 {
1117         return isl_union_map_simple_hull(uset);
1118 }
1119
1120 static int inplace_entry(void **entry, void *user)
1121 {
1122         __isl_give isl_map *(*fn)(__isl_take isl_map *);
1123         isl_map **map = (isl_map **)entry;
1124         isl_map *copy;
1125
1126         fn = *(__isl_give isl_map *(**)(__isl_take isl_map *)) user;
1127         copy = fn(isl_map_copy(*map));
1128         if (!copy)
1129                 return -1;
1130
1131         isl_map_free(*map);
1132         *map = copy;
1133
1134         return 0;
1135 }
1136
1137 static __isl_give isl_union_map *inplace(__isl_take isl_union_map *umap,
1138         __isl_give isl_map *(*fn)(__isl_take isl_map *))
1139 {
1140         if (!umap)
1141                 return NULL;
1142
1143         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1144                                     &inplace_entry, &fn) < 0)
1145                 goto error;
1146
1147         return umap;
1148 error:
1149         isl_union_map_free(umap);
1150         return NULL;
1151 }
1152
1153 __isl_give isl_union_map *isl_union_map_coalesce(
1154         __isl_take isl_union_map *umap)
1155 {
1156         return inplace(umap, &isl_map_coalesce);
1157 }
1158
1159 __isl_give isl_union_set *isl_union_set_coalesce(
1160         __isl_take isl_union_set *uset)
1161 {
1162         return isl_union_map_coalesce(uset);
1163 }
1164
1165 __isl_give isl_union_map *isl_union_map_detect_equalities(
1166         __isl_take isl_union_map *umap)
1167 {
1168         return inplace(umap, &isl_map_detect_equalities);
1169 }
1170
1171 __isl_give isl_union_set *isl_union_set_detect_equalities(
1172         __isl_take isl_union_set *uset)
1173 {
1174         return isl_union_map_detect_equalities(uset);
1175 }
1176
1177 __isl_give isl_union_map *isl_union_map_compute_divs(
1178         __isl_take isl_union_map *umap)
1179 {
1180         return inplace(umap, &isl_map_compute_divs);
1181 }
1182
1183 __isl_give isl_union_set *isl_union_set_compute_divs(
1184         __isl_take isl_union_set *uset)
1185 {
1186         return isl_union_map_compute_divs(uset);
1187 }
1188
1189 static int lexmin_entry(void **entry, void *user)
1190 {
1191         isl_map **map = (isl_map **)entry;
1192
1193         *map = isl_map_lexmin(*map);
1194
1195         return *map ? 0 : -1;
1196 }
1197
1198 __isl_give isl_union_map *isl_union_map_lexmin(
1199         __isl_take isl_union_map *umap)
1200 {
1201         return un_op(umap, &lexmin_entry);
1202 }
1203
1204 __isl_give isl_union_set *isl_union_set_lexmin(
1205         __isl_take isl_union_set *uset)
1206 {
1207         return isl_union_map_lexmin(uset);
1208 }
1209
1210 static int lexmax_entry(void **entry, void *user)
1211 {
1212         isl_map **map = (isl_map **)entry;
1213
1214         *map = isl_map_lexmax(*map);
1215
1216         return *map ? 0 : -1;
1217 }
1218
1219 __isl_give isl_union_map *isl_union_map_lexmax(
1220         __isl_take isl_union_map *umap)
1221 {
1222         return un_op(umap, &lexmax_entry);
1223 }
1224
1225 __isl_give isl_union_set *isl_union_set_lexmax(
1226         __isl_take isl_union_set *uset)
1227 {
1228         return isl_union_map_lexmax(uset);
1229 }
1230
1231 static int universe_entry(void **entry, void *user)
1232 {
1233         isl_map *map = *entry;
1234         isl_union_map **res = user;
1235
1236         map = isl_map_universe(isl_map_get_space(map));
1237         *res = isl_union_map_add_map(*res, map);
1238
1239         return 0;
1240 }
1241
1242 __isl_give isl_union_map *isl_union_map_universe(__isl_take isl_union_map *umap)
1243 {
1244         return cond_un_op(umap, &universe_entry);
1245 }
1246
1247 __isl_give isl_union_set *isl_union_set_universe(__isl_take isl_union_set *uset)
1248 {
1249         return isl_union_map_universe(uset);
1250 }
1251
1252 static int reverse_entry(void **entry, void *user)
1253 {
1254         isl_map *map = *entry;
1255         isl_union_map **res = user;
1256
1257         *res = isl_union_map_add_map(*res, isl_map_reverse(isl_map_copy(map)));
1258
1259         return 0;
1260 }
1261
1262 __isl_give isl_union_map *isl_union_map_reverse(__isl_take isl_union_map *umap)
1263 {
1264         return cond_un_op(umap, &reverse_entry);
1265 }
1266
1267 static int domain_entry(void **entry, void *user)
1268 {
1269         isl_map *map = *entry;
1270         isl_union_set **res = user;
1271
1272         *res = isl_union_set_add_set(*res, isl_map_domain(isl_map_copy(map)));
1273
1274         return 0;
1275 }
1276
1277 __isl_give isl_union_set *isl_union_map_domain(__isl_take isl_union_map *umap)
1278 {
1279         return cond_un_op(umap, &domain_entry);
1280 }
1281
1282 static int range_entry(void **entry, void *user)
1283 {
1284         isl_map *map = *entry;
1285         isl_union_set **res = user;
1286
1287         *res = isl_union_set_add_set(*res, isl_map_range(isl_map_copy(map)));
1288
1289         return 0;
1290 }
1291
1292 __isl_give isl_union_set *isl_union_map_range(__isl_take isl_union_map *umap)
1293 {
1294         return cond_un_op(umap, &range_entry);
1295 }
1296
1297 static int domain_map_entry(void **entry, void *user)
1298 {
1299         isl_map *map = *entry;
1300         isl_union_set **res = user;
1301
1302         *res = isl_union_map_add_map(*res,
1303                                         isl_map_domain_map(isl_map_copy(map)));
1304
1305         return 0;
1306 }
1307
1308 __isl_give isl_union_map *isl_union_map_domain_map(
1309         __isl_take isl_union_map *umap)
1310 {
1311         return cond_un_op(umap, &domain_map_entry);
1312 }
1313
1314 static int range_map_entry(void **entry, void *user)
1315 {
1316         isl_map *map = *entry;
1317         isl_union_set **res = user;
1318
1319         *res = isl_union_map_add_map(*res,
1320                                         isl_map_range_map(isl_map_copy(map)));
1321
1322         return 0;
1323 }
1324
1325 __isl_give isl_union_map *isl_union_map_range_map(
1326         __isl_take isl_union_map *umap)
1327 {
1328         return cond_un_op(umap, &range_map_entry);
1329 }
1330
1331 static int deltas_entry(void **entry, void *user)
1332 {
1333         isl_map *map = *entry;
1334         isl_union_set **res = user;
1335
1336         if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1337                 return 0;
1338
1339         *res = isl_union_set_add_set(*res, isl_map_deltas(isl_map_copy(map)));
1340
1341         return 0;
1342 }
1343
1344 __isl_give isl_union_set *isl_union_map_deltas(__isl_take isl_union_map *umap)
1345 {
1346         return cond_un_op(umap, &deltas_entry);
1347 }
1348
1349 static int deltas_map_entry(void **entry, void *user)
1350 {
1351         isl_map *map = *entry;
1352         isl_union_map **res = user;
1353
1354         if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1355                 return 0;
1356
1357         *res = isl_union_map_add_map(*res,
1358                                      isl_map_deltas_map(isl_map_copy(map)));
1359
1360         return 0;
1361 }
1362
1363 __isl_give isl_union_map *isl_union_map_deltas_map(
1364         __isl_take isl_union_map *umap)
1365 {
1366         return cond_un_op(umap, &deltas_map_entry);
1367 }
1368
1369 static int identity_entry(void **entry, void *user)
1370 {
1371         isl_set *set = *entry;
1372         isl_union_map **res = user;
1373
1374         *res = isl_union_map_add_map(*res, isl_set_identity(isl_set_copy(set)));
1375
1376         return 0;
1377 }
1378
1379 __isl_give isl_union_map *isl_union_set_identity(__isl_take isl_union_set *uset)
1380 {
1381         return cond_un_op(uset, &identity_entry);
1382 }
1383
1384 static int unwrap_entry(void **entry, void *user)
1385 {
1386         isl_set *set = *entry;
1387         isl_union_set **res = user;
1388
1389         if (!isl_set_is_wrapping(set))
1390                 return 0;
1391
1392         *res = isl_union_map_add_map(*res, isl_set_unwrap(isl_set_copy(set)));
1393
1394         return 0;
1395 }
1396
1397 __isl_give isl_union_map *isl_union_set_unwrap(__isl_take isl_union_set *uset)
1398 {
1399         return cond_un_op(uset, &unwrap_entry);
1400 }
1401
1402 static int wrap_entry(void **entry, void *user)
1403 {
1404         isl_map *map = *entry;
1405         isl_union_set **res = user;
1406
1407         *res = isl_union_set_add_set(*res, isl_map_wrap(isl_map_copy(map)));
1408
1409         return 0;
1410 }
1411
1412 __isl_give isl_union_set *isl_union_map_wrap(__isl_take isl_union_map *umap)
1413 {
1414         return cond_un_op(umap, &wrap_entry);
1415 }
1416
1417 struct isl_union_map_is_subset_data {
1418         isl_union_map *umap2;
1419         int is_subset;
1420 };
1421
1422 static int is_subset_entry(void **entry, void *user)
1423 {
1424         struct isl_union_map_is_subset_data *data = user;
1425         uint32_t hash;
1426         struct isl_hash_table_entry *entry2;
1427         isl_map *map = *entry;
1428
1429         hash = isl_space_get_hash(map->dim);
1430         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1431                                      hash, &has_dim, map->dim, 0);
1432         if (!entry2) {
1433                 data->is_subset = 0;
1434                 return -1;
1435         }
1436
1437         data->is_subset = isl_map_is_subset(map, entry2->data);
1438         if (data->is_subset < 0 || !data->is_subset)
1439                 return -1;
1440
1441         return 0;
1442 }
1443
1444 int isl_union_map_is_subset(__isl_keep isl_union_map *umap1,
1445         __isl_keep isl_union_map *umap2)
1446 {
1447         struct isl_union_map_is_subset_data data = { NULL, 1 };
1448
1449         umap1 = isl_union_map_copy(umap1);
1450         umap2 = isl_union_map_copy(umap2);
1451         umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
1452         umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
1453
1454         if (!umap1 || !umap2)
1455                 goto error;
1456
1457         data.umap2 = umap2;
1458         if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1459                                    &is_subset_entry, &data) < 0 &&
1460             data.is_subset)
1461                 goto error;
1462
1463         isl_union_map_free(umap1);
1464         isl_union_map_free(umap2);
1465
1466         return data.is_subset;
1467 error:
1468         isl_union_map_free(umap1);
1469         isl_union_map_free(umap2);
1470         return -1;
1471 }
1472
1473 int isl_union_set_is_subset(__isl_keep isl_union_set *uset1,
1474         __isl_keep isl_union_set *uset2)
1475 {
1476         return isl_union_map_is_subset(uset1, uset2);
1477 }
1478
1479 int isl_union_map_is_equal(__isl_keep isl_union_map *umap1,
1480         __isl_keep isl_union_map *umap2)
1481 {
1482         int is_subset;
1483
1484         if (!umap1 || !umap2)
1485                 return -1;
1486         is_subset = isl_union_map_is_subset(umap1, umap2);
1487         if (is_subset != 1)
1488                 return is_subset;
1489         is_subset = isl_union_map_is_subset(umap2, umap1);
1490         return is_subset;
1491 }
1492
1493 int isl_union_set_is_equal(__isl_keep isl_union_set *uset1,
1494         __isl_keep isl_union_set *uset2)
1495 {
1496         return isl_union_map_is_equal(uset1, uset2);
1497 }
1498
1499 int isl_union_map_is_strict_subset(__isl_keep isl_union_map *umap1,
1500         __isl_keep isl_union_map *umap2)
1501 {
1502         int is_subset;
1503
1504         if (!umap1 || !umap2)
1505                 return -1;
1506         is_subset = isl_union_map_is_subset(umap1, umap2);
1507         if (is_subset != 1)
1508                 return is_subset;
1509         is_subset = isl_union_map_is_subset(umap2, umap1);
1510         if (is_subset == -1)
1511                 return is_subset;
1512         return !is_subset;
1513 }
1514
1515 int isl_union_set_is_strict_subset(__isl_keep isl_union_set *uset1,
1516         __isl_keep isl_union_set *uset2)
1517 {
1518         return isl_union_map_is_strict_subset(uset1, uset2);
1519 }
1520
1521 static int sample_entry(void **entry, void *user)
1522 {
1523         isl_basic_map **sample = (isl_basic_map **)user;
1524         isl_map *map = *entry;
1525
1526         *sample = isl_map_sample(isl_map_copy(map));
1527         if (!*sample)
1528                 return -1;
1529         if (!isl_basic_map_plain_is_empty(*sample))
1530                 return -1;
1531         return 0;
1532 }
1533
1534 __isl_give isl_basic_map *isl_union_map_sample(__isl_take isl_union_map *umap)
1535 {
1536         isl_basic_map *sample = NULL;
1537
1538         if (!umap)
1539                 return NULL;
1540
1541         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1542                                    &sample_entry, &sample) < 0 &&
1543             !sample)
1544                 goto error;
1545
1546         if (!sample)
1547                 sample = isl_basic_map_empty(isl_union_map_get_space(umap));
1548
1549         isl_union_map_free(umap);
1550
1551         return sample;
1552 error:
1553         isl_union_map_free(umap);
1554         return NULL;
1555 }
1556
1557 __isl_give isl_basic_set *isl_union_set_sample(__isl_take isl_union_set *uset)
1558 {
1559         return (isl_basic_set *)isl_union_map_sample(uset);
1560 }
1561
1562 struct isl_forall_data {
1563         int res;
1564         int (*fn)(__isl_keep isl_map *map);
1565 };
1566
1567 static int forall_entry(void **entry, void *user)
1568 {
1569         struct isl_forall_data *data = user;
1570         isl_map *map = *entry;
1571
1572         data->res = data->fn(map);
1573         if (data->res < 0)
1574                 return -1;
1575
1576         if (!data->res)
1577                 return -1;
1578
1579         return 0;
1580 }
1581
1582 static int union_map_forall(__isl_keep isl_union_map *umap,
1583         int (*fn)(__isl_keep isl_map *map))
1584 {
1585         struct isl_forall_data data = { 1, fn };
1586
1587         if (!umap)
1588                 return -1;
1589
1590         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1591                                    &forall_entry, &data) < 0 && data.res)
1592                 return -1;
1593
1594         return data.res;
1595 }
1596
1597 struct isl_forall_user_data {
1598         int res;
1599         int (*fn)(__isl_keep isl_map *map, void *user);
1600         void *user;
1601 };
1602
1603 static int forall_user_entry(void **entry, void *user)
1604 {
1605         struct isl_forall_user_data *data = user;
1606         isl_map *map = *entry;
1607
1608         data->res = data->fn(map, data->user);
1609         if (data->res < 0)
1610                 return -1;
1611
1612         if (!data->res)
1613                 return -1;
1614
1615         return 0;
1616 }
1617
1618 /* Check if fn(map, user) returns true for all maps "map" in umap.
1619  */
1620 static int union_map_forall_user(__isl_keep isl_union_map *umap,
1621         int (*fn)(__isl_keep isl_map *map, void *user), void *user)
1622 {
1623         struct isl_forall_user_data data = { 1, fn, user };
1624
1625         if (!umap)
1626                 return -1;
1627
1628         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1629                                    &forall_user_entry, &data) < 0 && data.res)
1630                 return -1;
1631
1632         return data.res;
1633 }
1634
1635 int isl_union_map_is_empty(__isl_keep isl_union_map *umap)
1636 {
1637         return union_map_forall(umap, &isl_map_is_empty);
1638 }
1639
1640 int isl_union_set_is_empty(__isl_keep isl_union_set *uset)
1641 {
1642         return isl_union_map_is_empty(uset);
1643 }
1644
1645 static int is_subset_of_identity(__isl_keep isl_map *map)
1646 {
1647         int is_subset;
1648         isl_space *dim;
1649         isl_map *id;
1650
1651         if (!map)
1652                 return -1;
1653
1654         if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1655                 return 0;
1656
1657         dim = isl_map_get_space(map);
1658         id = isl_map_identity(dim);
1659
1660         is_subset = isl_map_is_subset(map, id);
1661
1662         isl_map_free(id);
1663
1664         return is_subset;
1665 }
1666
1667 /* Check if the given map is single-valued.
1668  * We simply compute
1669  *
1670  *      M \circ M^-1
1671  *
1672  * and check if the result is a subset of the identity mapping.
1673  */
1674 int isl_union_map_is_single_valued(__isl_keep isl_union_map *umap)
1675 {
1676         isl_union_map *test;
1677         int sv;
1678
1679         if (isl_union_map_n_map(umap) == 1) {
1680                 isl_map *map;
1681                 umap = isl_union_map_copy(umap);
1682                 map = isl_map_from_union_map(umap);
1683                 sv = isl_map_is_single_valued(map);
1684                 isl_map_free(map);
1685                 return sv;
1686         }
1687
1688         test = isl_union_map_reverse(isl_union_map_copy(umap));
1689         test = isl_union_map_apply_range(test, isl_union_map_copy(umap));
1690
1691         sv = union_map_forall(test, &is_subset_of_identity);
1692
1693         isl_union_map_free(test);
1694
1695         return sv;
1696 }
1697
1698 int isl_union_map_is_injective(__isl_keep isl_union_map *umap)
1699 {
1700         int in;
1701
1702         umap = isl_union_map_copy(umap);
1703         umap = isl_union_map_reverse(umap);
1704         in = isl_union_map_is_single_valued(umap);
1705         isl_union_map_free(umap);
1706
1707         return in;
1708 }
1709
1710 /* Represents a map that has a fixed value (v) for one of its
1711  * range dimensions.
1712  * The map in this structure is not reference counted, so it
1713  * is only valid while the isl_union_map from which it was
1714  * obtained is still alive.
1715  */
1716 struct isl_fixed_map {
1717         isl_int v;
1718         isl_map *map;
1719 };
1720
1721 static struct isl_fixed_map *alloc_isl_fixed_map_array(isl_ctx *ctx,
1722         int n)
1723 {
1724         int i;
1725         struct isl_fixed_map *v;
1726
1727         v = isl_calloc_array(ctx, struct isl_fixed_map, n);
1728         if (!v)
1729                 return NULL;
1730         for (i = 0; i < n; ++i)
1731                 isl_int_init(v[i].v);
1732         return v;
1733 }
1734
1735 static void free_isl_fixed_map_array(struct isl_fixed_map *v, int n)
1736 {
1737         int i;
1738
1739         if (!v)
1740                 return;
1741         for (i = 0; i < n; ++i)
1742                 isl_int_clear(v[i].v);
1743         free(v);
1744 }
1745
1746 /* Compare the "v" field of two isl_fixed_map structs.
1747  */
1748 static int qsort_fixed_map_cmp(const void *p1, const void *p2)
1749 {
1750         const struct isl_fixed_map *e1 = (const struct isl_fixed_map *) p1;
1751         const struct isl_fixed_map *e2 = (const struct isl_fixed_map *) p2;
1752
1753         return isl_int_cmp(e1->v, e2->v);
1754 }
1755
1756 /* Internal data structure used while checking whether all maps
1757  * in a union_map have a fixed value for a given output dimension.
1758  * v is the list of maps, with the fixed value for the dimension
1759  * n is the number of maps considered so far
1760  * pos is the output dimension under investigation
1761  */
1762 struct isl_fixed_dim_data {
1763         struct isl_fixed_map *v;
1764         int n;
1765         int pos;
1766 };
1767
1768 static int fixed_at_pos(__isl_keep isl_map *map, void *user)
1769 {
1770         struct isl_fixed_dim_data *data = user;
1771
1772         data->v[data->n].map = map;
1773         return isl_map_plain_is_fixed(map, isl_dim_out, data->pos,
1774                                       &data->v[data->n++].v);
1775 }
1776
1777 static int plain_injective_on_range(__isl_take isl_union_map *umap,
1778         int first, int n_range);
1779
1780 /* Given a list of the maps, with their fixed values at output dimension "pos",
1781  * check whether the ranges of the maps form an obvious partition.
1782  *
1783  * We first sort the maps according to their fixed values.
1784  * If all maps have a different value, then we know the ranges form
1785  * a partition.
1786  * Otherwise, we collect the maps with the same fixed value and
1787  * check whether each such collection is obviously injective
1788  * based on later dimensions.
1789  */
1790 static int separates(struct isl_fixed_map *v, int n,
1791         __isl_take isl_space *dim, int pos, int n_range)
1792 {
1793         int i;
1794
1795         if (!v)
1796                 goto error;
1797
1798         qsort(v, n, sizeof(*v), &qsort_fixed_map_cmp);
1799
1800         for (i = 0; i + 1 < n; ++i) {
1801                 int j, k;
1802                 isl_union_map *part;
1803                 int injective;
1804
1805                 for (j = i + 1; j < n; ++j)
1806                         if (isl_int_ne(v[i].v, v[j].v))
1807                                 break;
1808
1809                 if (j == i + 1)
1810                         continue;
1811
1812                 part = isl_union_map_alloc(isl_space_copy(dim), j - i);
1813                 for (k = i; k < j; ++k)
1814                         part = isl_union_map_add_map(part,
1815                                                      isl_map_copy(v[k].map));
1816
1817                 injective = plain_injective_on_range(part, pos + 1, n_range);
1818                 if (injective < 0)
1819                         goto error;
1820                 if (!injective)
1821                         break;
1822
1823                 i = j - 1;
1824         }
1825
1826         isl_space_free(dim);
1827         free_isl_fixed_map_array(v, n);
1828         return i + 1 >= n;
1829 error:
1830         isl_space_free(dim);
1831         free_isl_fixed_map_array(v, n);
1832         return -1;
1833 }
1834
1835 /* Check whether the maps in umap have obviously distinct ranges.
1836  * In particular, check for an output dimension in the range
1837  * [first,n_range) for which all maps have a fixed value
1838  * and then check if these values, possibly along with fixed values
1839  * at later dimensions, entail distinct ranges.
1840  */
1841 static int plain_injective_on_range(__isl_take isl_union_map *umap,
1842         int first, int n_range)
1843 {
1844         isl_ctx *ctx;
1845         int n;
1846         struct isl_fixed_dim_data data = { NULL };
1847
1848         ctx = isl_union_map_get_ctx(umap);
1849
1850         if (!umap)
1851                 goto error;
1852
1853         n = isl_union_map_n_map(umap);
1854         if (n <= 1) {
1855                 isl_union_map_free(umap);
1856                 return 1;
1857         }
1858
1859         if (first >= n_range) {
1860                 isl_union_map_free(umap);
1861                 return 0;
1862         }
1863
1864         data.v = alloc_isl_fixed_map_array(ctx, n);
1865         if (!data.v)
1866                 goto error;
1867
1868         for (data.pos = first; data.pos < n_range; ++data.pos) {
1869                 int fixed;
1870                 int injective;
1871                 isl_space *dim;
1872
1873                 data.n = 0;
1874                 fixed = union_map_forall_user(umap, &fixed_at_pos, &data);
1875                 if (fixed < 0)
1876                         goto error;
1877                 if (!fixed)
1878                         continue;
1879                 dim = isl_union_map_get_space(umap);
1880                 injective = separates(data.v, n, dim, data.pos, n_range);
1881                 isl_union_map_free(umap);
1882                 return injective;
1883         }
1884
1885         free_isl_fixed_map_array(data.v, n);
1886         isl_union_map_free(umap);
1887
1888         return 0;
1889 error:
1890         free_isl_fixed_map_array(data.v, n);
1891         isl_union_map_free(umap);
1892         return -1;
1893 }
1894
1895 /* Check whether the maps in umap that map to subsets of "ran"
1896  * have obviously distinct ranges.
1897  */
1898 static int plain_injective_on_range_wrap(__isl_keep isl_set *ran, void *user)
1899 {
1900         isl_union_map *umap = user;
1901
1902         umap = isl_union_map_copy(umap);
1903         umap = isl_union_map_intersect_range(umap,
1904                         isl_union_set_from_set(isl_set_copy(ran)));
1905         return plain_injective_on_range(umap, 0, isl_set_dim(ran, isl_dim_set));
1906 }
1907
1908 /* Check if the given union_map is obviously injective.
1909  *
1910  * In particular, we first check if all individual maps are obviously
1911  * injective and then check if all the ranges of these maps are
1912  * obviously disjoint.
1913  */
1914 int isl_union_map_plain_is_injective(__isl_keep isl_union_map *umap)
1915 {
1916         int in;
1917         isl_union_map *univ;
1918         isl_union_set *ran;
1919
1920         in = union_map_forall(umap, &isl_map_plain_is_injective);
1921         if (in < 0)
1922                 return -1;
1923         if (!in)
1924                 return 0;
1925
1926         univ = isl_union_map_universe(isl_union_map_copy(umap));
1927         ran = isl_union_map_range(univ);
1928
1929         in = union_map_forall_user(ran, &plain_injective_on_range_wrap, umap);
1930
1931         isl_union_set_free(ran);
1932
1933         return in;
1934 }
1935
1936 int isl_union_map_is_bijective(__isl_keep isl_union_map *umap)
1937 {
1938         int sv;
1939
1940         sv = isl_union_map_is_single_valued(umap);
1941         if (sv < 0 || !sv)
1942                 return sv;
1943
1944         return isl_union_map_is_injective(umap);
1945 }
1946
1947 static int zip_entry(void **entry, void *user)
1948 {
1949         isl_map *map = *entry;
1950         isl_union_map **res = user;
1951
1952         if (!isl_map_can_zip(map))
1953                 return 0;
1954
1955         *res = isl_union_map_add_map(*res, isl_map_zip(isl_map_copy(map)));
1956
1957         return 0;
1958 }
1959
1960 __isl_give isl_union_map *isl_union_map_zip(__isl_take isl_union_map *umap)
1961 {
1962         return cond_un_op(umap, &zip_entry);
1963 }
1964
1965 static int lift_entry(void **entry, void *user)
1966 {
1967         isl_set *set = *entry;
1968         isl_union_set **res = user;
1969
1970         *res = isl_union_set_add_set(*res, isl_set_lift(isl_set_copy(set)));
1971
1972         return 0;
1973 }
1974
1975 __isl_give isl_union_set *isl_union_set_lift(__isl_take isl_union_set *uset)
1976 {
1977         return cond_un_op(uset, &lift_entry);
1978 }
1979
1980 static int coefficients_entry(void **entry, void *user)
1981 {
1982         isl_set *set = *entry;
1983         isl_union_set **res = user;
1984
1985         set = isl_set_copy(set);
1986         set = isl_set_from_basic_set(isl_set_coefficients(set));
1987         *res = isl_union_set_add_set(*res, set);
1988
1989         return 0;
1990 }
1991
1992 __isl_give isl_union_set *isl_union_set_coefficients(
1993         __isl_take isl_union_set *uset)
1994 {
1995         isl_ctx *ctx;
1996         isl_space *dim;
1997         isl_union_set *res;
1998
1999         if (!uset)
2000                 return NULL;
2001
2002         ctx = isl_union_set_get_ctx(uset);
2003         dim = isl_space_set_alloc(ctx, 0, 0);
2004         res = isl_union_map_alloc(dim, uset->table.n);
2005         if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
2006                                    &coefficients_entry, &res) < 0)
2007                 goto error;
2008
2009         isl_union_set_free(uset);
2010         return res;
2011 error:
2012         isl_union_set_free(uset);
2013         isl_union_set_free(res);
2014         return NULL;
2015 }
2016
2017 static int solutions_entry(void **entry, void *user)
2018 {
2019         isl_set *set = *entry;
2020         isl_union_set **res = user;
2021
2022         set = isl_set_copy(set);
2023         set = isl_set_from_basic_set(isl_set_solutions(set));
2024         if (!*res)
2025                 *res = isl_union_set_from_set(set);
2026         else
2027                 *res = isl_union_set_add_set(*res, set);
2028
2029         if (!*res)
2030                 return -1;
2031
2032         return 0;
2033 }
2034
2035 __isl_give isl_union_set *isl_union_set_solutions(
2036         __isl_take isl_union_set *uset)
2037 {
2038         isl_union_set *res = NULL;
2039
2040         if (!uset)
2041                 return NULL;
2042
2043         if (uset->table.n == 0) {
2044                 res = isl_union_set_empty(isl_union_set_get_space(uset));
2045                 isl_union_set_free(uset);
2046                 return res;
2047         }
2048
2049         if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
2050                                    &solutions_entry, &res) < 0)
2051                 goto error;
2052
2053         isl_union_set_free(uset);
2054         return res;
2055 error:
2056         isl_union_set_free(uset);
2057         isl_union_set_free(res);
2058         return NULL;
2059 }