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