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