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