isl_union_map.c

   1 /*
   2  * Copyright 2010      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_ctx.h>
  12 #include <isl_hash.h>
  13 #include <isl_map.h>
  14 #include <isl_set.h>
  15 #include <isl_dim_private.h>
  16 #include <isl_union_map_private.h>
  17 #include <isl_union_set.h>
  18
  19 static __isl_give isl_union_map *isl_union_map_alloc(__isl_take isl_dim *dim,
  20         int size)
  21 {
  22         isl_union_map *umap;
  23
  24         if (!dim)
  25                 return NULL;
  26
  27         umap = isl_calloc_type(dim->ctx, isl_union_map);
  28         if (!umap)
  29                 return NULL;
  30
  31         umap->ref = 1;
  32         umap->dim = dim;
  33         if (isl_hash_table_init(dim->ctx, &umap->table, size) < 0)
  34                 goto error;
  35
  36         return umap;
  37 error:
  38         isl_dim_free(dim);
  39         isl_union_map_free(umap);
  40         return NULL;
  41 }
  42
  43 __isl_give isl_union_map *isl_union_map_empty(__isl_take isl_dim *dim)
  44 {
  45         return isl_union_map_alloc(dim, 16);
  46 }
  47
  48 __isl_give isl_union_set *isl_union_set_empty(__isl_take isl_dim *dim)
  49 {
  50         return isl_union_map_empty(dim);
  51 }
  52
  53 isl_ctx *isl_union_map_get_ctx(__isl_keep isl_union_map *umap)
  54 {
  55         return umap ? umap->dim->ctx : NULL;
  56 }
  57
  58 isl_ctx *isl_union_set_get_ctx(__isl_keep isl_union_set *uset)
  59 {
  60         return uset ? uset->dim->ctx : NULL;
  61 }
  62
  63 __isl_give isl_dim *isl_union_map_get_dim(__isl_keep isl_union_map *umap)
  64 {
  65         if (!umap)
  66                 return NULL;
  67         return isl_dim_copy(umap->dim);
  68 }
  69
  70 __isl_give isl_dim *isl_union_set_get_dim(__isl_keep isl_union_set *uset)
  71 {
  72         return isl_union_map_get_dim(uset);
  73 }
  74
  75 static int free_umap_entry(void **entry, void *user)
  76 {
  77         isl_map *map = *entry;
  78         isl_map_free(map);
  79         return 0;
  80 }
  81
  82 static int add_map(__isl_take isl_map *map, void *user)
  83 {
  84         isl_union_map **umap = (isl_union_map **)user;
  85
  86         *umap = isl_union_map_add_map(*umap, map);
  87
  88         return 0;
  89 }
  90
  91 __isl_give isl_union_map *isl_union_map_dup(__isl_keep isl_union_map *umap)
  92 {
  93         isl_union_map *dup;
  94
  95         if (!umap)
  96                 return NULL;
  97
  98         dup = isl_union_map_empty(isl_dim_copy(umap->dim));
  99         if (isl_union_map_foreach_map(umap, &add_map, &dup) < 0)
 100                 goto error;
 101         return dup;
 102 error:
 103         isl_union_map_free(dup);
 104         return NULL;
 105 }
 106
 107 __isl_give isl_union_map *isl_union_map_cow(__isl_take isl_union_map *umap)
 108 {
 109         if (!umap)
 110                 return NULL;
 111
 112         if (umap->ref == 1)
 113                 return umap;
 114         umap->ref--;
 115         return isl_union_map_dup(umap);
 116 }
 117
 118 __isl_give isl_union_map *isl_union_map_union(__isl_take isl_union_map *umap1,
 119         __isl_take isl_union_map *umap2)
 120 {
 121         umap1 = isl_union_map_cow(umap1);
 122
 123         if (!umap1 || !umap2)
 124                 goto error;
 125
 126         if (isl_union_map_foreach_map(umap2, &add_map, &umap1) < 0)
 127                 goto error;
 128
 129         isl_union_map_free(umap2);
 130
 131         return umap1;
 132 error:
 133         isl_union_map_free(umap1);
 134         isl_union_map_free(umap2);
 135         return NULL;
 136 }
 137
 138 __isl_give isl_union_set *isl_union_set_union(__isl_take isl_union_set *uset1,
 139         __isl_take isl_union_set *uset2)
 140 {
 141         return isl_union_map_union(uset1, uset2);
 142 }
 143
 144 __isl_give isl_union_map *isl_union_map_copy(__isl_keep isl_union_map *umap)
 145 {
 146         if (!umap)
 147                 return NULL;
 148
 149         umap->ref++;
 150         return umap;
 151 }
 152
 153 __isl_give isl_union_set *isl_union_set_copy(__isl_keep isl_union_set *uset)
 154 {
 155         return isl_union_map_copy(uset);
 156 }
 157
 158 void isl_union_map_free(__isl_take isl_union_map *umap)
 159 {
 160         if (!umap)
 161                 return;
 162
 163         if (--umap->ref > 0)
 164                 return;
 165
 166         isl_hash_table_foreach(umap->dim->ctx, &umap->table,
 167                                &free_umap_entry, NULL);
 168         isl_hash_table_clear(&umap->table);
 169         isl_dim_free(umap->dim);
 170         free(umap);
 171 }
 172
 173 void isl_union_set_free(__isl_take isl_union_set *uset)
 174 {
 175         isl_union_map_free(uset);
 176 }
 177
 178 static int has_dim(const void *entry, const void *val)
 179 {
 180         isl_map *map = (isl_map *)entry;
 181         isl_dim *dim = (isl_dim *)val;
 182
 183         return isl_dim_equal(map->dim, dim);
 184 }
 185
 186 __isl_give isl_union_map *isl_union_map_add_map(__isl_take isl_union_map *umap,
 187         __isl_take isl_map *map)
 188 {
 189         uint32_t hash;
 190         struct isl_hash_table_entry *entry;
 191
 192         if (isl_map_fast_is_empty(map)) {
 193                 isl_map_free(map);
 194                 return umap;
 195         }
 196
 197         umap = isl_union_map_cow(umap);
 198
 199         if (!map || !umap)
 200                 goto error;
 201
 202         isl_assert(map->ctx, isl_dim_match(map->dim, isl_dim_param, umap->dim,
 203                                            isl_dim_param), goto error);
 204
 205         hash = isl_dim_get_hash(map->dim);
 206         entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
 207                                     &has_dim, map->dim, 1);
 208         if (!entry)
 209                 goto error;
 210
 211         if (!entry->data)
 212                 entry->data = map;
 213         else {
 214                 entry->data = isl_map_union(entry->data, isl_map_copy(map));
 215                 if (!entry->data)
 216                         goto error;
 217                 isl_map_free(map);
 218         }
 219
 220         return umap;
 221 error:
 222         isl_map_free(map);
 223         isl_union_map_free(umap);
 224         return NULL;
 225 }
 226
 227 __isl_give isl_union_set *isl_union_set_add_set(__isl_take isl_union_set *uset,
 228         __isl_take isl_set *set)
 229 {
 230         return isl_union_map_add_map(uset, (isl_map *)set);
 231 }
 232
 233 __isl_give isl_union_map *isl_union_map_from_map(__isl_take isl_map *map)
 234 {
 235         isl_dim *dim;
 236         isl_union_map *umap;
 237
 238         if (!map)
 239                 return NULL;
 240
 241         dim = isl_map_get_dim(map);
 242         dim = isl_dim_drop(dim, isl_dim_in, 0, isl_dim_size(dim, isl_dim_in));
 243         dim = isl_dim_drop(dim, isl_dim_out, 0, isl_dim_size(dim, isl_dim_out));
 244         umap = isl_union_map_empty(dim);
 245         umap = isl_union_map_add_map(umap, map);
 246
 247         return umap;
 248 }
 249
 250 __isl_give isl_union_set *isl_union_set_from_set(__isl_take isl_set *set)
 251 {
 252         return isl_union_map_from_map((isl_map *)set);
 253 }
 254
 255 struct isl_union_map_foreach_data
 256 {
 257         int (*fn)(__isl_take isl_map *map, void *user);
 258         void *user;
 259 };
 260
 261 static int call_on_copy(void **entry, void *user)
 262 {
 263         isl_map *map = *entry;
 264         struct isl_union_map_foreach_data *data;
 265         data = (struct isl_union_map_foreach_data *)user;
 266
 267         return data->fn(isl_map_copy(map), data->user);
 268 }
 269
 270 int isl_union_map_foreach_map(__isl_keep isl_union_map *umap,
 271         int (*fn)(__isl_take isl_map *map, void *user), void *user)
 272 {
 273         struct isl_union_map_foreach_data data = { fn, user };
 274
 275         if (!umap)
 276                 return -1;
 277
 278         return isl_hash_table_foreach(umap->dim->ctx, &umap->table,
 279                                       &call_on_copy, &data);
 280 }
 281
 282 int isl_union_set_foreach_set(__isl_keep isl_union_set *uset,
 283         int (*fn)(__isl_take isl_set *set, void *user), void *user)
 284 {
 285         return isl_union_map_foreach_map(uset,
 286                 (int(*)(__isl_take isl_map *, void*))fn, user);
 287 }
 288
 289 struct isl_union_set_foreach_point_data {
 290         int (*fn)(__isl_take isl_point *pnt, void *user);
 291         void *user;
 292 };
 293
 294 static int foreach_point(__isl_take isl_set *set, void *user)
 295 {
 296         struct isl_union_set_foreach_point_data *data = user;
 297         int r;
 298
 299         r = isl_set_foreach_point(set, data->fn, data->user);
 300         isl_set_free(set);
 301
 302         return r;
 303 }
 304
 305 int isl_union_set_foreach_point(__isl_keep isl_union_set *uset,
 306         int (*fn)(__isl_take isl_point *pnt, void *user), void *user)
 307 {
 308         struct isl_union_set_foreach_point_data data = { fn, user };
 309         return isl_union_set_foreach_set(uset, &foreach_point, &data);
 310 }
 311
 312 struct isl_union_map_gen_bin_data {
 313         isl_union_map *umap2;
 314         isl_union_map *res;
 315 };
 316
 317 static int subtract_entry(void **entry, void *user)
 318 {
 319         struct isl_union_map_gen_bin_data *data = user;
 320         uint32_t hash;
 321         struct isl_hash_table_entry *entry2;
 322         isl_map *map = *entry;
 323
 324         hash = isl_dim_get_hash(map->dim);
 325         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
 326                                      hash, &has_dim, map->dim, 0);
 327         map = isl_map_copy(map);
 328         if (entry2) {
 329                 int empty;
 330                 map = isl_map_subtract(map, isl_map_copy(entry2->data));
 331
 332                 empty = isl_map_is_empty(map);
 333                 if (empty < 0) {
 334                         isl_map_free(map);
 335                         return -1;
 336                 }
 337                 if (empty) {
 338                         isl_map_free(map);
 339                         return 0;
 340                 }
 341         }
 342         data->res = isl_union_map_add_map(data->res, map);
 343
 344         return 0;
 345 }
 346
 347 static __isl_give isl_union_map *gen_bin_op(__isl_take isl_union_map *umap1,
 348         __isl_take isl_union_map *umap2, int (*fn)(void **, void *))
 349 {
 350         struct isl_union_map_gen_bin_data data = { umap2, NULL };
 351
 352         if (!umap1 || !umap2)
 353                 goto error;
 354
 355         data.res = isl_union_map_alloc(isl_dim_copy(umap1->dim),
 356                                        umap1->table.n);
 357         if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
 358                                    fn, &data) < 0)
 359                 goto error;
 360
 361         isl_union_map_free(umap1);
 362         isl_union_map_free(umap2);
 363         return data.res;
 364 error:
 365         isl_union_map_free(umap1);
 366         isl_union_map_free(umap2);
 367         isl_union_map_free(data.res);
 368         return NULL;
 369 }
 370
 371 __isl_give isl_union_map *isl_union_map_subtract(
 372         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 373 {
 374         return gen_bin_op(umap1, umap2, &subtract_entry);
 375 }
 376
 377 __isl_give isl_union_set *isl_union_set_subtract(
 378         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
 379 {
 380         return isl_union_map_subtract(uset1, uset2);
 381 }
 382
 383 struct isl_union_map_match_bin_data {
 384         isl_union_map *umap2;
 385         isl_union_map *res;
 386         __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*);
 387 };
 388
 389 static int match_bin_entry(void **entry, void *user)
 390 {
 391         struct isl_union_map_match_bin_data *data = user;
 392         uint32_t hash;
 393         struct isl_hash_table_entry *entry2;
 394         isl_map *map = *entry;
 395         int empty;
 396
 397         hash = isl_dim_get_hash(map->dim);
 398         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
 399                                      hash, &has_dim, map->dim, 0);
 400         if (!entry2)
 401                 return 0;
 402
 403         map = isl_map_copy(map);
 404         map = data->fn(map, isl_map_copy(entry2->data));
 405
 406         empty = isl_map_is_empty(map);
 407         if (empty < 0) {
 408                 isl_map_free(map);
 409                 return -1;
 410         }
 411         if (empty) {
 412                 isl_map_free(map);
 413                 return 0;
 414         }
 415
 416         data->res = isl_union_map_add_map(data->res, map);
 417
 418         return 0;
 419 }
 420
 421 static __isl_give isl_union_map *match_bin_op(__isl_take isl_union_map *umap1,
 422         __isl_take isl_union_map *umap2,
 423         __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*))
 424 {
 425         struct isl_union_map_match_bin_data data = { umap2, NULL, fn };
 426
 427         if (!umap1 || !umap2)
 428                 goto error;
 429
 430         data.res = isl_union_map_alloc(isl_dim_copy(umap1->dim),
 431                                        umap1->table.n);
 432         if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
 433                                    &match_bin_entry, &data) < 0)
 434                 goto error;
 435
 436         isl_union_map_free(umap1);
 437         isl_union_map_free(umap2);
 438         return data.res;
 439 error:
 440         isl_union_map_free(umap1);
 441         isl_union_map_free(umap2);
 442         isl_union_map_free(data.res);
 443         return NULL;
 444 }
 445
 446 __isl_give isl_union_map *isl_union_map_intersect(
 447         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 448 {
 449         return match_bin_op(umap1, umap2, &isl_map_intersect);
 450 }
 451
 452 __isl_give isl_union_set *isl_union_set_intersect(
 453         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
 454 {
 455         return isl_union_map_intersect(uset1, uset2);
 456 }
 457
 458 __isl_give isl_union_map *isl_union_map_gist(__isl_take isl_union_map *umap,
 459         __isl_take isl_union_map *context)
 460 {
 461         return match_bin_op(umap, context, &isl_map_gist);
 462 }
 463
 464 __isl_give isl_union_set *isl_union_set_gist(__isl_take isl_union_set *uset,
 465         __isl_take isl_union_set *context)
 466 {
 467         return isl_union_map_gist(uset, context);
 468 }
 469
 470 static int intersect_domain_entry(void **entry, void *user)
 471 {
 472         struct isl_union_map_gen_bin_data *data = user;
 473         uint32_t hash;
 474         struct isl_hash_table_entry *entry2;
 475         isl_dim *dim;
 476         isl_map *map = *entry;
 477         int empty;
 478
 479         dim = isl_map_get_dim(map);
 480         dim = isl_dim_domain(dim);
 481         hash = isl_dim_get_hash(dim);
 482         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
 483                                      hash, &has_dim, dim, 0);
 484         isl_dim_free(dim);
 485         if (!entry2)
 486                 return 0;
 487
 488         map = isl_map_copy(map);
 489         map = isl_map_intersect_domain(map, isl_set_copy(entry2->data));
 490
 491         empty = isl_map_is_empty(map);
 492         if (empty < 0) {
 493                 isl_map_free(map);
 494                 return -1;
 495         }
 496         if (empty) {
 497                 isl_map_free(map);
 498                 return 0;
 499         }
 500
 501         data->res = isl_union_map_add_map(data->res, map);
 502
 503         return 0;
 504 }
 505
 506 __isl_give isl_union_map *isl_union_map_intersect_domain(
 507         __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
 508 {
 509         return gen_bin_op(umap, uset, &intersect_domain_entry);
 510 }
 511
 512 struct isl_union_map_bin_data {
 513         isl_union_map *umap2;
 514         isl_union_map *res;
 515         isl_map *map;
 516         int (*fn)(void **entry, void *user);
 517 };
 518
 519 static int apply_range_entry(void **entry, void *user)
 520 {
 521         struct isl_union_map_bin_data *data = user;
 522         isl_map *map2 = *entry;
 523         int empty;
 524
 525         if (!isl_dim_tuple_match(data->map->dim, isl_dim_out,
 526                                  map2->dim, isl_dim_in))
 527                 return 0;
 528
 529         map2 = isl_map_apply_range(isl_map_copy(data->map), isl_map_copy(map2));
 530
 531         empty = isl_map_is_empty(map2);
 532         if (empty < 0) {
 533                 isl_map_free(map2);
 534                 return -1;
 535         }
 536         if (empty) {
 537                 isl_map_free(map2);
 538                 return 0;
 539         }
 540
 541         data->res = isl_union_map_add_map(data->res, map2);
 542
 543         return 0;
 544 }
 545
 546 static int bin_entry(void **entry, void *user)
 547 {
 548         struct isl_union_map_bin_data *data = user;
 549         isl_map *map = *entry;
 550
 551         data->map = map;
 552         if (isl_hash_table_foreach(data->umap2->dim->ctx, &data->umap2->table,
 553                                    data->fn, data) < 0)
 554                 return -1;
 555
 556         return 0;
 557 }
 558
 559 static __isl_give isl_union_map *bin_op(__isl_take isl_union_map *umap1,
 560         __isl_take isl_union_map *umap2, int (*fn)(void **entry, void *user))
 561 {
 562         struct isl_union_map_bin_data data = { umap2, NULL, NULL, fn };
 563
 564         if (!umap1 || !umap2)
 565                 goto error;
 566
 567         data.res = isl_union_map_alloc(isl_dim_copy(umap1->dim),
 568                                        umap1->table.n);
 569         if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
 570                                    &bin_entry, &data) < 0)
 571                 goto error;
 572
 573         isl_union_map_free(umap1);
 574         isl_union_map_free(umap2);
 575         return data.res;
 576 error:
 577         isl_union_map_free(umap1);
 578         isl_union_map_free(umap2);
 579         isl_union_map_free(data.res);
 580         return NULL;
 581 }
 582
 583 __isl_give isl_union_map *isl_union_map_apply_range(
 584         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 585 {
 586         return bin_op(umap1, umap2, &apply_range_entry);
 587 }
 588
 589 __isl_give isl_union_set *isl_union_set_apply(
 590         __isl_take isl_union_set *uset, __isl_take isl_union_map *umap)
 591 {
 592         return isl_union_map_apply_range(uset, umap);
 593 }
 594
 595 static int product_entry(void **entry, void *user)
 596 {
 597         struct isl_union_map_bin_data *data = user;
 598         isl_map *map2 = *entry;
 599
 600         map2 = isl_map_product(isl_map_copy(data->map), isl_map_copy(map2));
 601
 602         data->res = isl_union_map_add_map(data->res, map2);
 603
 604         return 0;
 605 }
 606
 607 __isl_give isl_union_map *isl_union_map_product(__isl_take isl_union_map *umap1,
 608         __isl_take isl_union_map *umap2)
 609 {
 610         return bin_op(umap1, umap2, &product_entry);
 611 }
 612
 613 __isl_give isl_union_set *isl_union_set_product(__isl_take isl_union_set *uset1,
 614         __isl_take isl_union_set *uset2)
 615 {
 616         return isl_union_map_product(uset1, uset2);
 617 }
 618
 619 __isl_give isl_union_map *isl_union_map_from_range(
 620         __isl_take isl_union_set *uset)
 621 {
 622         return uset;
 623 }
 624
 625 __isl_give isl_union_map *isl_union_map_from_domain(
 626         __isl_take isl_union_set *uset)
 627 {
 628         return isl_union_map_reverse(isl_union_map_from_range(uset));
 629 }
 630
 631 __isl_give isl_union_map *isl_union_map_from_domain_and_range(
 632         __isl_take isl_union_set *domain, __isl_take isl_union_set *range)
 633 {
 634         return isl_union_map_apply_range(isl_union_map_from_domain(domain),
 635                                          isl_union_map_from_range(range));
 636 }
 637
 638 static __isl_give isl_union_map *un_op(__isl_take isl_union_map *umap,
 639         int (*fn)(void **, void *), int cow)
 640 {
 641         if (cow)
 642                 umap = isl_union_map_cow(umap);
 643         if (!umap)
 644                 return NULL;
 645
 646         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, NULL) < 0)
 647                 goto error;
 648
 649         return umap;
 650 error:
 651         isl_union_map_free(umap);
 652         return NULL;
 653 }
 654
 655 static int affine_entry(void **entry, void *user)
 656 {
 657         isl_map **map = (isl_map **)entry;
 658
 659         *map = isl_map_from_basic_map(isl_map_affine_hull(*map));
 660
 661         return *map ? 0 : -1;
 662 }
 663
 664 __isl_give isl_union_map *isl_union_map_affine_hull(
 665         __isl_take isl_union_map *umap)
 666 {
 667         return un_op(umap, &affine_entry, 1);
 668 }
 669
 670 __isl_give isl_union_set *isl_union_set_affine_hull(
 671         __isl_take isl_union_set *uset)
 672 {
 673         return isl_union_map_affine_hull(uset);
 674 }
 675
 676 static int coalesce_entry(void **entry, void *user)
 677 {
 678         isl_map **map = (isl_map **)entry;
 679
 680         *map = isl_map_coalesce(*map);
 681
 682         return *map ? 0 : -1;
 683 }
 684
 685 __isl_give isl_union_map *isl_union_map_coalesce(
 686         __isl_take isl_union_map *umap)
 687 {
 688         return un_op(umap, &coalesce_entry, 0);
 689 }
 690
 691 __isl_give isl_union_set *isl_union_set_coalesce(
 692         __isl_take isl_union_set *uset)
 693 {
 694         return isl_union_map_coalesce(uset);
 695 }
 696
 697 static int compute_divs_entry(void **entry, void *user)
 698 {
 699         isl_map **map = (isl_map **)entry;
 700
 701         *map = isl_map_compute_divs(*map);
 702
 703         return *map ? 0 : -1;
 704 }
 705
 706 __isl_give isl_union_map *isl_union_map_compute_divs(
 707         __isl_take isl_union_map *umap)
 708 {
 709         return un_op(umap, &compute_divs_entry, 0);
 710 }
 711
 712 __isl_give isl_union_set *isl_union_set_compute_divs(
 713         __isl_take isl_union_set *uset)
 714 {
 715         return isl_union_map_compute_divs(uset);
 716 }
 717
 718 static int lexmin_entry(void **entry, void *user)
 719 {
 720         isl_map **map = (isl_map **)entry;
 721
 722         *map = isl_map_lexmin(*map);
 723
 724         return *map ? 0 : -1;
 725 }
 726
 727 __isl_give isl_union_map *isl_union_map_lexmin(
 728         __isl_take isl_union_map *umap)
 729 {
 730         return un_op(umap, &lexmin_entry, 1);
 731 }
 732
 733 __isl_give isl_union_set *isl_union_set_lexmin(
 734         __isl_take isl_union_set *uset)
 735 {
 736         return isl_union_map_lexmin(uset);
 737 }
 738
 739 static int lexmax_entry(void **entry, void *user)
 740 {
 741         isl_map **map = (isl_map **)entry;
 742
 743         *map = isl_map_lexmax(*map);
 744
 745         return *map ? 0 : -1;
 746 }
 747
 748 __isl_give isl_union_map *isl_union_map_lexmax(
 749         __isl_take isl_union_map *umap)
 750 {
 751         return un_op(umap, &lexmax_entry, 1);
 752 }
 753
 754 __isl_give isl_union_set *isl_union_set_lexmax(
 755         __isl_take isl_union_set *uset)
 756 {
 757         return isl_union_map_lexmax(uset);
 758 }
 759
 760 static __isl_give isl_union_set *cond_un_op(__isl_take isl_union_map *umap,
 761         int (*fn)(void **, void *))
 762 {
 763         isl_union_set *res;
 764
 765         if (!umap)
 766                 return NULL;
 767
 768         res = isl_union_map_alloc(isl_dim_copy(umap->dim), umap->table.n);
 769         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, &res) < 0)
 770                 goto error;
 771
 772         isl_union_map_free(umap);
 773         return res;
 774 error:
 775         isl_union_map_free(umap);
 776         isl_union_set_free(res);
 777         return NULL;
 778 }
 779
 780 static int reverse_entry(void **entry, void *user)
 781 {
 782         isl_map *map = *entry;
 783         isl_union_map **res = user;
 784
 785         *res = isl_union_map_add_map(*res, isl_map_reverse(isl_map_copy(map)));
 786
 787         return 0;
 788 }
 789
 790 __isl_give isl_union_map *isl_union_map_reverse(__isl_take isl_union_map *umap)
 791 {
 792         return cond_un_op(umap, &reverse_entry);
 793 }
 794
 795 static int domain_entry(void **entry, void *user)
 796 {
 797         isl_map *map = *entry;
 798         isl_union_set **res = user;
 799
 800         *res = isl_union_set_add_set(*res, isl_map_domain(isl_map_copy(map)));
 801
 802         return 0;
 803 }
 804
 805 __isl_give isl_union_set *isl_union_map_domain(__isl_take isl_union_map *umap)
 806 {
 807         return cond_un_op(umap, &domain_entry);
 808 }
 809
 810 static int range_entry(void **entry, void *user)
 811 {
 812         isl_map *map = *entry;
 813         isl_union_set **res = user;
 814
 815         *res = isl_union_set_add_set(*res, isl_map_range(isl_map_copy(map)));
 816
 817         return 0;
 818 }
 819
 820 __isl_give isl_union_set *isl_union_map_range(__isl_take isl_union_map *umap)
 821 {
 822         return cond_un_op(umap, &range_entry);
 823 }
 824
 825 static int deltas_entry(void **entry, void *user)
 826 {
 827         isl_map *map = *entry;
 828         isl_union_set **res = user;
 829
 830         if (!isl_dim_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
 831                 return 0;
 832
 833         *res = isl_union_set_add_set(*res, isl_map_deltas(isl_map_copy(map)));
 834
 835         return 0;
 836 }
 837
 838 __isl_give isl_union_set *isl_union_map_deltas(__isl_take isl_union_map *umap)
 839 {
 840         return cond_un_op(umap, &deltas_entry);
 841 }
 842
 843 static int unwrap_entry(void **entry, void *user)
 844 {
 845         isl_set *set = *entry;
 846         isl_union_set **res = user;
 847
 848         if (!isl_set_is_wrapping(set))
 849                 return 0;
 850
 851         *res = isl_union_map_add_map(*res, isl_set_unwrap(isl_set_copy(set)));
 852
 853         return 0;
 854 }
 855
 856 __isl_give isl_union_map *isl_union_set_unwrap(__isl_take isl_union_set *uset)
 857 {
 858         return cond_un_op(uset, &unwrap_entry);
 859 }
 860
 861 static int wrap_entry(void **entry, void *user)
 862 {
 863         isl_map *map = *entry;
 864         isl_union_set **res = user;
 865
 866         *res = isl_union_set_add_set(*res, isl_map_wrap(isl_map_copy(map)));
 867
 868         return 0;
 869 }
 870
 871 __isl_give isl_union_set *isl_union_map_wrap(__isl_take isl_union_map *umap)
 872 {
 873         return cond_un_op(umap, &wrap_entry);
 874 }
 875
 876 struct isl_union_map_is_subset_data {
 877         isl_union_map *umap2;
 878         int is_subset;
 879 };
 880
 881 static int is_subset_entry(void **entry, void *user)
 882 {
 883         struct isl_union_map_is_subset_data *data = user;
 884         uint32_t hash;
 885         struct isl_hash_table_entry *entry2;
 886         isl_map *map = *entry;
 887
 888         hash = isl_dim_get_hash(map->dim);
 889         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
 890                                      hash, &has_dim, map->dim, 0);
 891         if (!entry2) {
 892                 data->is_subset = 0;
 893                 return -1;
 894         }
 895
 896         data->is_subset = isl_map_is_subset(map, entry2->data);
 897         if (data->is_subset < 0 || !data->is_subset)
 898                 return -1;
 899
 900         return 0;
 901 }
 902
 903 int isl_union_map_is_subset(__isl_keep isl_union_map *umap1,
 904         __isl_keep isl_union_map *umap2)
 905 {
 906         struct isl_union_map_is_subset_data data = { umap2, 1 };
 907
 908         if (!umap1 || !umap2)
 909                 return -1;
 910
 911         if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
 912                                    &is_subset_entry, &data) < 0 &&
 913             data.is_subset)
 914                 return -1;
 915
 916         return data.is_subset;
 917 }
 918
 919 int isl_union_map_is_equal(__isl_keep isl_union_map *umap1,
 920         __isl_keep isl_union_map *umap2)
 921 {
 922         int is_subset;
 923
 924         if (!umap1 || !umap2)
 925                 return -1;
 926         is_subset = isl_union_map_is_subset(umap1, umap2);
 927         if (is_subset != 1)
 928                 return is_subset;
 929         is_subset = isl_union_map_is_subset(umap2, umap1);
 930         return is_subset;
 931 }
 932
 933 int isl_union_map_is_strict_subset(__isl_keep isl_union_map *umap1,
 934         __isl_keep isl_union_map *umap2)
 935 {
 936         int is_subset;
 937
 938         if (!umap1 || !umap2)
 939                 return -1;
 940         is_subset = isl_union_map_is_subset(umap1, umap2);
 941         if (is_subset != 1)
 942                 return is_subset;
 943         is_subset = isl_union_map_is_subset(umap2, umap1);
 944         if (is_subset == -1)
 945                 return is_subset;
 946         return !is_subset;
 947 }
 948
 949 static int sample_entry(void **entry, void *user)
 950 {
 951         isl_basic_map **sample = (isl_basic_map **)user;
 952         isl_map *map = *entry;
 953
 954         *sample = isl_map_sample(isl_map_copy(map));
 955         if (!*sample)
 956                 return -1;
 957         if (!isl_basic_map_fast_is_empty(*sample))
 958                 return -1;
 959         return 0;
 960 }
 961
 962 __isl_give isl_basic_map *isl_union_map_sample(__isl_take isl_union_map *umap)
 963 {
 964         isl_basic_map *sample = NULL;
 965
 966         if (!umap)
 967                 return NULL;
 968
 969         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
 970                                    &sample_entry, &sample) < 0 &&
 971             !sample)
 972                 goto error;
 973
 974         isl_union_map_free(umap);
 975
 976         return sample;
 977 error:
 978         isl_union_map_free(umap);
 979         return NULL;
 980 }
 981
 982 __isl_give isl_basic_set *isl_union_set_sample(__isl_take isl_union_set *uset)
 983 {
 984         return (isl_basic_set *)isl_union_map_sample(uset);
 985 }
 986
 987 static int empty_entry(void **entry, void *user)
 988 {
 989         int *empty = user;
 990         isl_map *map = *entry;
 991
 992         if (isl_map_is_empty(map))
 993                 return 0;
 994
 995         *empty = 0;
 996
 997         return -1;
 998 }
 999
1000 __isl_give int isl_union_map_is_empty(__isl_keep isl_union_map *umap)
1001 {
1002         int empty = 1;
1003
1004         if (!umap)
1005                 return -1;
1006
1007         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1008                                    &empty_entry, &empty) < 0 && empty)
1009                 return -1;
1010
1011         return empty;
1012 }
1013
1014 int isl_union_set_is_empty(__isl_keep isl_union_set *uset)
1015 {
1016         return isl_union_map_is_empty(uset);
1017 }