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