isl_union_map.c

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