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_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_fast_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 __isl_give isl_map *isl_union_map_extract_map(__isl_keep isl_union_map *umap,
 363         __isl_take isl_dim *dim)
 364 {
 365         uint32_t hash;
 366         struct isl_hash_table_entry *entry;
 367
 368         if (!umap || !dim)
 369                 goto error;
 370
 371         hash = isl_dim_get_hash(dim);
 372         entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
 373                                     &has_dim, dim, 0);
 374         if (!entry)
 375                 return isl_map_empty(dim);
 376         isl_dim_free(dim);
 377         return isl_map_copy(entry->data);
 378 error:
 379         isl_dim_free(dim);
 380         return NULL;
 381 }
 382
 383 __isl_give isl_set *isl_union_set_extract_set(__isl_keep isl_union_set *uset,
 384         __isl_take isl_dim *dim)
 385 {
 386         return (isl_set *)isl_union_map_extract_map(uset, dim);
 387 }
 388
 389 int isl_union_set_foreach_set(__isl_keep isl_union_set *uset,
 390         int (*fn)(__isl_take isl_set *set, void *user), void *user)
 391 {
 392         return isl_union_map_foreach_map(uset,
 393                 (int(*)(__isl_take isl_map *, void*))fn, user);
 394 }
 395
 396 struct isl_union_set_foreach_point_data {
 397         int (*fn)(__isl_take isl_point *pnt, void *user);
 398         void *user;
 399 };
 400
 401 static int foreach_point(__isl_take isl_set *set, void *user)
 402 {
 403         struct isl_union_set_foreach_point_data *data = user;
 404         int r;
 405
 406         r = isl_set_foreach_point(set, data->fn, data->user);
 407         isl_set_free(set);
 408
 409         return r;
 410 }
 411
 412 int isl_union_set_foreach_point(__isl_keep isl_union_set *uset,
 413         int (*fn)(__isl_take isl_point *pnt, void *user), void *user)
 414 {
 415         struct isl_union_set_foreach_point_data data = { fn, user };
 416         return isl_union_set_foreach_set(uset, &foreach_point, &data);
 417 }
 418
 419 struct isl_union_map_gen_bin_data {
 420         isl_union_map *umap2;
 421         isl_union_map *res;
 422 };
 423
 424 static int subtract_entry(void **entry, void *user)
 425 {
 426         struct isl_union_map_gen_bin_data *data = user;
 427         uint32_t hash;
 428         struct isl_hash_table_entry *entry2;
 429         isl_map *map = *entry;
 430
 431         hash = isl_dim_get_hash(map->dim);
 432         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
 433                                      hash, &has_dim, map->dim, 0);
 434         map = isl_map_copy(map);
 435         if (entry2) {
 436                 int empty;
 437                 map = isl_map_subtract(map, isl_map_copy(entry2->data));
 438
 439                 empty = isl_map_is_empty(map);
 440                 if (empty < 0) {
 441                         isl_map_free(map);
 442                         return -1;
 443                 }
 444                 if (empty) {
 445                         isl_map_free(map);
 446                         return 0;
 447                 }
 448         }
 449         data->res = isl_union_map_add_map(data->res, map);
 450
 451         return 0;
 452 }
 453
 454 static __isl_give isl_union_map *gen_bin_op(__isl_take isl_union_map *umap1,
 455         __isl_take isl_union_map *umap2, int (*fn)(void **, void *))
 456 {
 457         struct isl_union_map_gen_bin_data data = { NULL, NULL };
 458
 459         umap1 = isl_union_map_align_params(umap1, isl_union_map_get_dim(umap2));
 460         umap2 = isl_union_map_align_params(umap2, isl_union_map_get_dim(umap1));
 461
 462         if (!umap1 || !umap2)
 463                 goto error;
 464
 465         data.umap2 = umap2;
 466         data.res = isl_union_map_alloc(isl_dim_copy(umap1->dim),
 467                                        umap1->table.n);
 468         if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
 469                                    fn, &data) < 0)
 470                 goto error;
 471
 472         isl_union_map_free(umap1);
 473         isl_union_map_free(umap2);
 474         return data.res;
 475 error:
 476         isl_union_map_free(umap1);
 477         isl_union_map_free(umap2);
 478         isl_union_map_free(data.res);
 479         return NULL;
 480 }
 481
 482 __isl_give isl_union_map *isl_union_map_subtract(
 483         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 484 {
 485         return gen_bin_op(umap1, umap2, &subtract_entry);
 486 }
 487
 488 __isl_give isl_union_set *isl_union_set_subtract(
 489         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
 490 {
 491         return isl_union_map_subtract(uset1, uset2);
 492 }
 493
 494 struct isl_union_map_match_bin_data {
 495         isl_union_map *umap2;
 496         isl_union_map *res;
 497         __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*);
 498 };
 499
 500 static int match_bin_entry(void **entry, void *user)
 501 {
 502         struct isl_union_map_match_bin_data *data = user;
 503         uint32_t hash;
 504         struct isl_hash_table_entry *entry2;
 505         isl_map *map = *entry;
 506         int empty;
 507
 508         hash = isl_dim_get_hash(map->dim);
 509         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
 510                                      hash, &has_dim, map->dim, 0);
 511         if (!entry2)
 512                 return 0;
 513
 514         map = isl_map_copy(map);
 515         map = data->fn(map, isl_map_copy(entry2->data));
 516
 517         empty = isl_map_is_empty(map);
 518         if (empty < 0) {
 519                 isl_map_free(map);
 520                 return -1;
 521         }
 522         if (empty) {
 523                 isl_map_free(map);
 524                 return 0;
 525         }
 526
 527         data->res = isl_union_map_add_map(data->res, map);
 528
 529         return 0;
 530 }
 531
 532 static __isl_give isl_union_map *match_bin_op(__isl_take isl_union_map *umap1,
 533         __isl_take isl_union_map *umap2,
 534         __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*))
 535 {
 536         struct isl_union_map_match_bin_data data = { NULL, NULL, fn };
 537
 538         umap1 = isl_union_map_align_params(umap1, isl_union_map_get_dim(umap2));
 539         umap2 = isl_union_map_align_params(umap2, isl_union_map_get_dim(umap1));
 540
 541         if (!umap1 || !umap2)
 542                 goto error;
 543
 544         data.umap2 = umap2;
 545         data.res = isl_union_map_alloc(isl_dim_copy(umap1->dim),
 546                                        umap1->table.n);
 547         if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
 548                                    &match_bin_entry, &data) < 0)
 549                 goto error;
 550
 551         isl_union_map_free(umap1);
 552         isl_union_map_free(umap2);
 553         return data.res;
 554 error:
 555         isl_union_map_free(umap1);
 556         isl_union_map_free(umap2);
 557         isl_union_map_free(data.res);
 558         return NULL;
 559 }
 560
 561 __isl_give isl_union_map *isl_union_map_intersect(
 562         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 563 {
 564         return match_bin_op(umap1, umap2, &isl_map_intersect);
 565 }
 566
 567 __isl_give isl_union_set *isl_union_set_intersect(
 568         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
 569 {
 570         return isl_union_map_intersect(uset1, uset2);
 571 }
 572
 573 __isl_give isl_union_map *isl_union_map_gist(__isl_take isl_union_map *umap,
 574         __isl_take isl_union_map *context)
 575 {
 576         return match_bin_op(umap, context, &isl_map_gist);
 577 }
 578
 579 __isl_give isl_union_set *isl_union_set_gist(__isl_take isl_union_set *uset,
 580         __isl_take isl_union_set *context)
 581 {
 582         return isl_union_map_gist(uset, context);
 583 }
 584
 585 static __isl_give isl_map *lex_le_set(__isl_take isl_map *set1,
 586         __isl_take isl_map *set2)
 587 {
 588         return isl_set_lex_le_set((isl_set *)set1, (isl_set *)set2);
 589 }
 590
 591 static __isl_give isl_map *lex_lt_set(__isl_take isl_map *set1,
 592         __isl_take isl_map *set2)
 593 {
 594         return isl_set_lex_lt_set((isl_set *)set1, (isl_set *)set2);
 595 }
 596
 597 __isl_give isl_union_map *isl_union_set_lex_lt_union_set(
 598         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
 599 {
 600         return match_bin_op(uset1, uset2, &lex_lt_set);
 601 }
 602
 603 __isl_give isl_union_map *isl_union_set_lex_le_union_set(
 604         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
 605 {
 606         return match_bin_op(uset1, uset2, &lex_le_set);
 607 }
 608
 609 __isl_give isl_union_map *isl_union_set_lex_gt_union_set(
 610         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
 611 {
 612         return isl_union_map_reverse(isl_union_set_lex_lt_union_set(uset2, uset1));
 613 }
 614
 615 __isl_give isl_union_map *isl_union_set_lex_ge_union_set(
 616         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
 617 {
 618         return isl_union_map_reverse(isl_union_set_lex_le_union_set(uset2, uset1));
 619 }
 620
 621 __isl_give isl_union_map *isl_union_map_lex_gt_union_map(
 622         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 623 {
 624         return isl_union_map_reverse(isl_union_map_lex_lt_union_map(umap2, umap1));
 625 }
 626
 627 __isl_give isl_union_map *isl_union_map_lex_ge_union_map(
 628         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 629 {
 630         return isl_union_map_reverse(isl_union_map_lex_le_union_map(umap2, umap1));
 631 }
 632
 633 static int intersect_domain_entry(void **entry, void *user)
 634 {
 635         struct isl_union_map_gen_bin_data *data = user;
 636         uint32_t hash;
 637         struct isl_hash_table_entry *entry2;
 638         isl_dim *dim;
 639         isl_map *map = *entry;
 640         int empty;
 641
 642         dim = isl_map_get_dim(map);
 643         dim = isl_dim_domain(dim);
 644         hash = isl_dim_get_hash(dim);
 645         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
 646                                      hash, &has_dim, dim, 0);
 647         isl_dim_free(dim);
 648         if (!entry2)
 649                 return 0;
 650
 651         map = isl_map_copy(map);
 652         map = isl_map_intersect_domain(map, isl_set_copy(entry2->data));
 653
 654         empty = isl_map_is_empty(map);
 655         if (empty < 0) {
 656                 isl_map_free(map);
 657                 return -1;
 658         }
 659         if (empty) {
 660                 isl_map_free(map);
 661                 return 0;
 662         }
 663
 664         data->res = isl_union_map_add_map(data->res, map);
 665
 666         return 0;
 667 }
 668
 669 __isl_give isl_union_map *isl_union_map_intersect_domain(
 670         __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
 671 {
 672         return gen_bin_op(umap, uset, &intersect_domain_entry);
 673 }
 674
 675 static int intersect_range_entry(void **entry, void *user)
 676 {
 677         struct isl_union_map_gen_bin_data *data = user;
 678         uint32_t hash;
 679         struct isl_hash_table_entry *entry2;
 680         isl_dim *dim;
 681         isl_map *map = *entry;
 682         int empty;
 683
 684         dim = isl_map_get_dim(map);
 685         dim = isl_dim_range(dim);
 686         hash = isl_dim_get_hash(dim);
 687         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
 688                                      hash, &has_dim, dim, 0);
 689         isl_dim_free(dim);
 690         if (!entry2)
 691                 return 0;
 692
 693         map = isl_map_copy(map);
 694         map = isl_map_intersect_range(map, isl_set_copy(entry2->data));
 695
 696         empty = isl_map_is_empty(map);
 697         if (empty < 0) {
 698                 isl_map_free(map);
 699                 return -1;
 700         }
 701         if (empty) {
 702                 isl_map_free(map);
 703                 return 0;
 704         }
 705
 706         data->res = isl_union_map_add_map(data->res, map);
 707
 708         return 0;
 709 }
 710
 711 __isl_give isl_union_map *isl_union_map_intersect_range(
 712         __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
 713 {
 714         return gen_bin_op(umap, uset, &intersect_range_entry);
 715 }
 716
 717 struct isl_union_map_bin_data {
 718         isl_union_map *umap2;
 719         isl_union_map *res;
 720         isl_map *map;
 721         int (*fn)(void **entry, void *user);
 722 };
 723
 724 static int apply_range_entry(void **entry, void *user)
 725 {
 726         struct isl_union_map_bin_data *data = user;
 727         isl_map *map2 = *entry;
 728         int empty;
 729
 730         if (!isl_dim_tuple_match(data->map->dim, isl_dim_out,
 731                                  map2->dim, isl_dim_in))
 732                 return 0;
 733
 734         map2 = isl_map_apply_range(isl_map_copy(data->map), isl_map_copy(map2));
 735
 736         empty = isl_map_is_empty(map2);
 737         if (empty < 0) {
 738                 isl_map_free(map2);
 739                 return -1;
 740         }
 741         if (empty) {
 742                 isl_map_free(map2);
 743                 return 0;
 744         }
 745
 746         data->res = isl_union_map_add_map(data->res, map2);
 747
 748         return 0;
 749 }
 750
 751 static int bin_entry(void **entry, void *user)
 752 {
 753         struct isl_union_map_bin_data *data = user;
 754         isl_map *map = *entry;
 755
 756         data->map = map;
 757         if (isl_hash_table_foreach(data->umap2->dim->ctx, &data->umap2->table,
 758                                    data->fn, data) < 0)
 759                 return -1;
 760
 761         return 0;
 762 }
 763
 764 static __isl_give isl_union_map *bin_op(__isl_take isl_union_map *umap1,
 765         __isl_take isl_union_map *umap2, int (*fn)(void **entry, void *user))
 766 {
 767         struct isl_union_map_bin_data data = { NULL, NULL, NULL, fn };
 768
 769         umap1 = isl_union_map_align_params(umap1, isl_union_map_get_dim(umap2));
 770         umap2 = isl_union_map_align_params(umap2, isl_union_map_get_dim(umap1));
 771
 772         if (!umap1 || !umap2)
 773                 goto error;
 774
 775         data.umap2 = umap2;
 776         data.res = isl_union_map_alloc(isl_dim_copy(umap1->dim),
 777                                        umap1->table.n);
 778         if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
 779                                    &bin_entry, &data) < 0)
 780                 goto error;
 781
 782         isl_union_map_free(umap1);
 783         isl_union_map_free(umap2);
 784         return data.res;
 785 error:
 786         isl_union_map_free(umap1);
 787         isl_union_map_free(umap2);
 788         isl_union_map_free(data.res);
 789         return NULL;
 790 }
 791
 792 __isl_give isl_union_map *isl_union_map_apply_range(
 793         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 794 {
 795         return bin_op(umap1, umap2, &apply_range_entry);
 796 }
 797
 798 __isl_give isl_union_map *isl_union_map_apply_domain(
 799         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 800 {
 801         umap1 = isl_union_map_reverse(umap1);
 802         umap1 = isl_union_map_apply_range(umap1, umap2);
 803         return isl_union_map_reverse(umap1);
 804 }
 805
 806 __isl_give isl_union_set *isl_union_set_apply(
 807         __isl_take isl_union_set *uset, __isl_take isl_union_map *umap)
 808 {
 809         return isl_union_map_apply_range(uset, umap);
 810 }
 811
 812 static int map_lex_lt_entry(void **entry, void *user)
 813 {
 814         struct isl_union_map_bin_data *data = user;
 815         isl_map *map2 = *entry;
 816
 817         if (!isl_dim_tuple_match(data->map->dim, isl_dim_out,
 818                                  map2->dim, isl_dim_out))
 819                 return 0;
 820
 821         map2 = isl_map_lex_lt_map(isl_map_copy(data->map), isl_map_copy(map2));
 822
 823         data->res = isl_union_map_add_map(data->res, map2);
 824
 825         return 0;
 826 }
 827
 828 __isl_give isl_union_map *isl_union_map_lex_lt_union_map(
 829         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 830 {
 831         return bin_op(umap1, umap2, &map_lex_lt_entry);
 832 }
 833
 834 static int map_lex_le_entry(void **entry, void *user)
 835 {
 836         struct isl_union_map_bin_data *data = user;
 837         isl_map *map2 = *entry;
 838
 839         if (!isl_dim_tuple_match(data->map->dim, isl_dim_out,
 840                                  map2->dim, isl_dim_out))
 841                 return 0;
 842
 843         map2 = isl_map_lex_le_map(isl_map_copy(data->map), isl_map_copy(map2));
 844
 845         data->res = isl_union_map_add_map(data->res, map2);
 846
 847         return 0;
 848 }
 849
 850 __isl_give isl_union_map *isl_union_map_lex_le_union_map(
 851         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 852 {
 853         return bin_op(umap1, umap2, &map_lex_le_entry);
 854 }
 855
 856 static int product_entry(void **entry, void *user)
 857 {
 858         struct isl_union_map_bin_data *data = user;
 859         isl_map *map2 = *entry;
 860
 861         map2 = isl_map_product(isl_map_copy(data->map), isl_map_copy(map2));
 862
 863         data->res = isl_union_map_add_map(data->res, map2);
 864
 865         return 0;
 866 }
 867
 868 __isl_give isl_union_map *isl_union_map_product(__isl_take isl_union_map *umap1,
 869         __isl_take isl_union_map *umap2)
 870 {
 871         return bin_op(umap1, umap2, &product_entry);
 872 }
 873
 874 __isl_give isl_union_set *isl_union_set_product(__isl_take isl_union_set *uset1,
 875         __isl_take isl_union_set *uset2)
 876 {
 877         return isl_union_map_product(uset1, uset2);
 878 }
 879
 880 static int range_product_entry(void **entry, void *user)
 881 {
 882         struct isl_union_map_bin_data *data = user;
 883         isl_map *map2 = *entry;
 884
 885         if (!isl_dim_tuple_match(data->map->dim, isl_dim_in,
 886                                  map2->dim, isl_dim_in))
 887                 return 0;
 888
 889         map2 = isl_map_range_product(isl_map_copy(data->map),
 890                                      isl_map_copy(map2));
 891
 892         data->res = isl_union_map_add_map(data->res, map2);
 893
 894         return 0;
 895 }
 896
 897 __isl_give isl_union_map *isl_union_map_range_product(
 898         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 899 {
 900         return bin_op(umap1, umap2, &range_product_entry);
 901 }
 902
 903 __isl_give isl_union_map *isl_union_map_from_range(
 904         __isl_take isl_union_set *uset)
 905 {
 906         return uset;
 907 }
 908
 909 __isl_give isl_union_map *isl_union_map_from_domain(
 910         __isl_take isl_union_set *uset)
 911 {
 912         return isl_union_map_reverse(isl_union_map_from_range(uset));
 913 }
 914
 915 __isl_give isl_union_map *isl_union_map_from_domain_and_range(
 916         __isl_take isl_union_set *domain, __isl_take isl_union_set *range)
 917 {
 918         return isl_union_map_apply_range(isl_union_map_from_domain(domain),
 919                                          isl_union_map_from_range(range));
 920 }
 921
 922 static __isl_give isl_union_map *un_op(__isl_take isl_union_map *umap,
 923         int (*fn)(void **, void *))
 924 {
 925         umap = isl_union_map_cow(umap);
 926         if (!umap)
 927                 return NULL;
 928
 929         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, NULL) < 0)
 930                 goto error;
 931
 932         return umap;
 933 error:
 934         isl_union_map_free(umap);
 935         return NULL;
 936 }
 937
 938 static int affine_entry(void **entry, void *user)
 939 {
 940         isl_map **map = (isl_map **)entry;
 941
 942         *map = isl_map_from_basic_map(isl_map_affine_hull(*map));
 943
 944         return *map ? 0 : -1;
 945 }
 946
 947 __isl_give isl_union_map *isl_union_map_affine_hull(
 948         __isl_take isl_union_map *umap)
 949 {
 950         return un_op(umap, &affine_entry);
 951 }
 952
 953 __isl_give isl_union_set *isl_union_set_affine_hull(
 954         __isl_take isl_union_set *uset)
 955 {
 956         return isl_union_map_affine_hull(uset);
 957 }
 958
 959 static int polyhedral_entry(void **entry, void *user)
 960 {
 961         isl_map **map = (isl_map **)entry;
 962
 963         *map = isl_map_from_basic_map(isl_map_polyhedral_hull(*map));
 964
 965         return *map ? 0 : -1;
 966 }
 967
 968 __isl_give isl_union_map *isl_union_map_polyhedral_hull(
 969         __isl_take isl_union_map *umap)
 970 {
 971         return un_op(umap, &polyhedral_entry);
 972 }
 973
 974 __isl_give isl_union_set *isl_union_set_polyhedral_hull(
 975         __isl_take isl_union_set *uset)
 976 {
 977         return isl_union_map_polyhedral_hull(uset);
 978 }
 979
 980 static int simple_entry(void **entry, void *user)
 981 {
 982         isl_map **map = (isl_map **)entry;
 983
 984         *map = isl_map_from_basic_map(isl_map_simple_hull(*map));
 985
 986         return *map ? 0 : -1;
 987 }
 988
 989 __isl_give isl_union_map *isl_union_map_simple_hull(
 990         __isl_take isl_union_map *umap)
 991 {
 992         return un_op(umap, &simple_entry);
 993 }
 994
 995 __isl_give isl_union_set *isl_union_set_simple_hull(
 996         __isl_take isl_union_set *uset)
 997 {
 998         return isl_union_map_simple_hull(uset);
 999 }
1000
1001 static int inplace_entry(void **entry, void *user)
1002 {
1003         __isl_give isl_map *(*fn)(__isl_take isl_map *);
1004         isl_map **map = (isl_map **)entry;
1005         isl_map *copy;
1006
1007         fn = *(__isl_give isl_map *(**)(__isl_take isl_map *)) user;
1008         copy = fn(isl_map_copy(*map));
1009         if (!copy)
1010                 return -1;
1011
1012         isl_map_free(*map);
1013         *map = copy;
1014
1015         return 0;
1016 }
1017
1018 static __isl_give isl_union_map *inplace(__isl_take isl_union_map *umap,
1019         __isl_give isl_map *(*fn)(__isl_take isl_map *))
1020 {
1021         if (!umap)
1022                 return NULL;
1023
1024         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1025                                     &inplace_entry, &fn) < 0)
1026                 goto error;
1027
1028         return umap;
1029 error:
1030         isl_union_map_free(umap);
1031         return NULL;
1032 }
1033
1034 __isl_give isl_union_map *isl_union_map_coalesce(
1035         __isl_take isl_union_map *umap)
1036 {
1037         return inplace(umap, &isl_map_coalesce);
1038 }
1039
1040 __isl_give isl_union_set *isl_union_set_coalesce(
1041         __isl_take isl_union_set *uset)
1042 {
1043         return isl_union_map_coalesce(uset);
1044 }
1045
1046 __isl_give isl_union_map *isl_union_map_detect_equalities(
1047         __isl_take isl_union_map *umap)
1048 {
1049         return inplace(umap, &isl_map_detect_equalities);
1050 }
1051
1052 __isl_give isl_union_set *isl_union_set_detect_equalities(
1053         __isl_take isl_union_set *uset)
1054 {
1055         return isl_union_map_detect_equalities(uset);
1056 }
1057
1058 __isl_give isl_union_map *isl_union_map_compute_divs(
1059         __isl_take isl_union_map *umap)
1060 {
1061         return inplace(umap, &isl_map_compute_divs);
1062 }
1063
1064 __isl_give isl_union_set *isl_union_set_compute_divs(
1065         __isl_take isl_union_set *uset)
1066 {
1067         return isl_union_map_compute_divs(uset);
1068 }
1069
1070 static int lexmin_entry(void **entry, void *user)
1071 {
1072         isl_map **map = (isl_map **)entry;
1073
1074         *map = isl_map_lexmin(*map);
1075
1076         return *map ? 0 : -1;
1077 }
1078
1079 __isl_give isl_union_map *isl_union_map_lexmin(
1080         __isl_take isl_union_map *umap)
1081 {
1082         return un_op(umap, &lexmin_entry);
1083 }
1084
1085 __isl_give isl_union_set *isl_union_set_lexmin(
1086         __isl_take isl_union_set *uset)
1087 {
1088         return isl_union_map_lexmin(uset);
1089 }
1090
1091 static int lexmax_entry(void **entry, void *user)
1092 {
1093         isl_map **map = (isl_map **)entry;
1094
1095         *map = isl_map_lexmax(*map);
1096
1097         return *map ? 0 : -1;
1098 }
1099
1100 __isl_give isl_union_map *isl_union_map_lexmax(
1101         __isl_take isl_union_map *umap)
1102 {
1103         return un_op(umap, &lexmax_entry);
1104 }
1105
1106 __isl_give isl_union_set *isl_union_set_lexmax(
1107         __isl_take isl_union_set *uset)
1108 {
1109         return isl_union_map_lexmax(uset);
1110 }
1111
1112 static __isl_give isl_union_set *cond_un_op(__isl_take isl_union_map *umap,
1113         int (*fn)(void **, void *))
1114 {
1115         isl_union_set *res;
1116
1117         if (!umap)
1118                 return NULL;
1119
1120         res = isl_union_map_alloc(isl_dim_copy(umap->dim), umap->table.n);
1121         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, &res) < 0)
1122                 goto error;
1123
1124         isl_union_map_free(umap);
1125         return res;
1126 error:
1127         isl_union_map_free(umap);
1128         isl_union_set_free(res);
1129         return NULL;
1130 }
1131
1132 static int reverse_entry(void **entry, void *user)
1133 {
1134         isl_map *map = *entry;
1135         isl_union_map **res = user;
1136
1137         *res = isl_union_map_add_map(*res, isl_map_reverse(isl_map_copy(map)));
1138
1139         return 0;
1140 }
1141
1142 __isl_give isl_union_map *isl_union_map_reverse(__isl_take isl_union_map *umap)
1143 {
1144         return cond_un_op(umap, &reverse_entry);
1145 }
1146
1147 static int domain_entry(void **entry, void *user)
1148 {
1149         isl_map *map = *entry;
1150         isl_union_set **res = user;
1151
1152         *res = isl_union_set_add_set(*res, isl_map_domain(isl_map_copy(map)));
1153
1154         return 0;
1155 }
1156
1157 __isl_give isl_union_set *isl_union_map_domain(__isl_take isl_union_map *umap)
1158 {
1159         return cond_un_op(umap, &domain_entry);
1160 }
1161
1162 static int range_entry(void **entry, void *user)
1163 {
1164         isl_map *map = *entry;
1165         isl_union_set **res = user;
1166
1167         *res = isl_union_set_add_set(*res, isl_map_range(isl_map_copy(map)));
1168
1169         return 0;
1170 }
1171
1172 __isl_give isl_union_set *isl_union_map_range(__isl_take isl_union_map *umap)
1173 {
1174         return cond_un_op(umap, &range_entry);
1175 }
1176
1177 static int domain_map_entry(void **entry, void *user)
1178 {
1179         isl_map *map = *entry;
1180         isl_union_set **res = user;
1181
1182         *res = isl_union_map_add_map(*res,
1183                                         isl_map_domain_map(isl_map_copy(map)));
1184
1185         return 0;
1186 }
1187
1188 __isl_give isl_union_map *isl_union_map_domain_map(
1189         __isl_take isl_union_map *umap)
1190 {
1191         return cond_un_op(umap, &domain_map_entry);
1192 }
1193
1194 static int range_map_entry(void **entry, void *user)
1195 {
1196         isl_map *map = *entry;
1197         isl_union_set **res = user;
1198
1199         *res = isl_union_map_add_map(*res,
1200                                         isl_map_range_map(isl_map_copy(map)));
1201
1202         return 0;
1203 }
1204
1205 __isl_give isl_union_map *isl_union_map_range_map(
1206         __isl_take isl_union_map *umap)
1207 {
1208         return cond_un_op(umap, &range_map_entry);
1209 }
1210
1211 static int deltas_entry(void **entry, void *user)
1212 {
1213         isl_map *map = *entry;
1214         isl_union_set **res = user;
1215
1216         if (!isl_dim_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1217                 return 0;
1218
1219         *res = isl_union_set_add_set(*res, isl_map_deltas(isl_map_copy(map)));
1220
1221         return 0;
1222 }
1223
1224 __isl_give isl_union_set *isl_union_map_deltas(__isl_take isl_union_map *umap)
1225 {
1226         return cond_un_op(umap, &deltas_entry);
1227 }
1228
1229 static int deltas_map_entry(void **entry, void *user)
1230 {
1231         isl_map *map = *entry;
1232         isl_union_map **res = user;
1233
1234         if (!isl_dim_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1235                 return 0;
1236
1237         *res = isl_union_map_add_map(*res,
1238                                      isl_map_deltas_map(isl_map_copy(map)));
1239
1240         return 0;
1241 }
1242
1243 __isl_give isl_union_map *isl_union_map_deltas_map(
1244         __isl_take isl_union_map *umap)
1245 {
1246         return cond_un_op(umap, &deltas_map_entry);
1247 }
1248
1249 static int identity_entry(void **entry, void *user)
1250 {
1251         isl_set *set = *entry;
1252         isl_union_map **res = user;
1253
1254         *res = isl_union_map_add_map(*res, isl_set_identity(isl_set_copy(set)));
1255
1256         return 0;
1257 }
1258
1259 __isl_give isl_union_map *isl_union_set_identity(__isl_take isl_union_set *uset)
1260 {
1261         return cond_un_op(uset, &identity_entry);
1262 }
1263
1264 static int unwrap_entry(void **entry, void *user)
1265 {
1266         isl_set *set = *entry;
1267         isl_union_set **res = user;
1268
1269         if (!isl_set_is_wrapping(set))
1270                 return 0;
1271
1272         *res = isl_union_map_add_map(*res, isl_set_unwrap(isl_set_copy(set)));
1273
1274         return 0;
1275 }
1276
1277 __isl_give isl_union_map *isl_union_set_unwrap(__isl_take isl_union_set *uset)
1278 {
1279         return cond_un_op(uset, &unwrap_entry);
1280 }
1281
1282 static int wrap_entry(void **entry, void *user)
1283 {
1284         isl_map *map = *entry;
1285         isl_union_set **res = user;
1286
1287         *res = isl_union_set_add_set(*res, isl_map_wrap(isl_map_copy(map)));
1288
1289         return 0;
1290 }
1291
1292 __isl_give isl_union_set *isl_union_map_wrap(__isl_take isl_union_map *umap)
1293 {
1294         return cond_un_op(umap, &wrap_entry);
1295 }
1296
1297 struct isl_union_map_is_subset_data {
1298         isl_union_map *umap2;
1299         int is_subset;
1300 };
1301
1302 static int is_subset_entry(void **entry, void *user)
1303 {
1304         struct isl_union_map_is_subset_data *data = user;
1305         uint32_t hash;
1306         struct isl_hash_table_entry *entry2;
1307         isl_map *map = *entry;
1308
1309         hash = isl_dim_get_hash(map->dim);
1310         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1311                                      hash, &has_dim, map->dim, 0);
1312         if (!entry2) {
1313                 data->is_subset = 0;
1314                 return -1;
1315         }
1316
1317         data->is_subset = isl_map_is_subset(map, entry2->data);
1318         if (data->is_subset < 0 || !data->is_subset)
1319                 return -1;
1320
1321         return 0;
1322 }
1323
1324 int isl_union_map_is_subset(__isl_keep isl_union_map *umap1,
1325         __isl_keep isl_union_map *umap2)
1326 {
1327         struct isl_union_map_is_subset_data data = { NULL, 1 };
1328
1329         umap1 = isl_union_map_copy(umap1);
1330         umap2 = isl_union_map_copy(umap2);
1331         umap1 = isl_union_map_align_params(umap1, isl_union_map_get_dim(umap2));
1332         umap2 = isl_union_map_align_params(umap2, isl_union_map_get_dim(umap1));
1333
1334         if (!umap1 || !umap2)
1335                 goto error;
1336
1337         data.umap2 = umap2;
1338         if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1339                                    &is_subset_entry, &data) < 0 &&
1340             data.is_subset)
1341                 goto error;
1342
1343         isl_union_map_free(umap1);
1344         isl_union_map_free(umap2);
1345
1346         return data.is_subset;
1347 error:
1348         isl_union_map_free(umap1);
1349         isl_union_map_free(umap2);
1350         return -1;
1351 }
1352
1353 int isl_union_set_is_subset(__isl_keep isl_union_set *uset1,
1354         __isl_keep isl_union_set *uset2)
1355 {
1356         return isl_union_map_is_subset(uset1, uset2);
1357 }
1358
1359 int isl_union_map_is_equal(__isl_keep isl_union_map *umap1,
1360         __isl_keep isl_union_map *umap2)
1361 {
1362         int is_subset;
1363
1364         if (!umap1 || !umap2)
1365                 return -1;
1366         is_subset = isl_union_map_is_subset(umap1, umap2);
1367         if (is_subset != 1)
1368                 return is_subset;
1369         is_subset = isl_union_map_is_subset(umap2, umap1);
1370         return is_subset;
1371 }
1372
1373 int isl_union_set_is_equal(__isl_keep isl_union_set *uset1,
1374         __isl_keep isl_union_set *uset2)
1375 {
1376         return isl_union_map_is_equal(uset1, uset2);
1377 }
1378
1379 int isl_union_map_is_strict_subset(__isl_keep isl_union_map *umap1,
1380         __isl_keep isl_union_map *umap2)
1381 {
1382         int is_subset;
1383
1384         if (!umap1 || !umap2)
1385                 return -1;
1386         is_subset = isl_union_map_is_subset(umap1, umap2);
1387         if (is_subset != 1)
1388                 return is_subset;
1389         is_subset = isl_union_map_is_subset(umap2, umap1);
1390         if (is_subset == -1)
1391                 return is_subset;
1392         return !is_subset;
1393 }
1394
1395 int isl_union_set_is_strict_subset(__isl_keep isl_union_set *uset1,
1396         __isl_keep isl_union_set *uset2)
1397 {
1398         return isl_union_map_is_strict_subset(uset1, uset2);
1399 }
1400
1401 static int sample_entry(void **entry, void *user)
1402 {
1403         isl_basic_map **sample = (isl_basic_map **)user;
1404         isl_map *map = *entry;
1405
1406         *sample = isl_map_sample(isl_map_copy(map));
1407         if (!*sample)
1408                 return -1;
1409         if (!isl_basic_map_fast_is_empty(*sample))
1410                 return -1;
1411         return 0;
1412 }
1413
1414 __isl_give isl_basic_map *isl_union_map_sample(__isl_take isl_union_map *umap)
1415 {
1416         isl_basic_map *sample = NULL;
1417
1418         if (!umap)
1419                 return NULL;
1420
1421         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1422                                    &sample_entry, &sample) < 0 &&
1423             !sample)
1424                 goto error;
1425
1426         if (!sample)
1427                 sample = isl_basic_map_empty(isl_union_map_get_dim(umap));
1428
1429         isl_union_map_free(umap);
1430
1431         return sample;
1432 error:
1433         isl_union_map_free(umap);
1434         return NULL;
1435 }
1436
1437 __isl_give isl_basic_set *isl_union_set_sample(__isl_take isl_union_set *uset)
1438 {
1439         return (isl_basic_set *)isl_union_map_sample(uset);
1440 }
1441
1442 static int empty_entry(void **entry, void *user)
1443 {
1444         int *empty = user;
1445         isl_map *map = *entry;
1446
1447         if (isl_map_is_empty(map))
1448                 return 0;
1449
1450         *empty = 0;
1451
1452         return -1;
1453 }
1454
1455 __isl_give int isl_union_map_is_empty(__isl_keep isl_union_map *umap)
1456 {
1457         int empty = 1;
1458
1459         if (!umap)
1460                 return -1;
1461
1462         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1463                                    &empty_entry, &empty) < 0 && empty)
1464                 return -1;
1465
1466         return empty;
1467 }
1468
1469 int isl_union_set_is_empty(__isl_keep isl_union_set *uset)
1470 {
1471         return isl_union_map_is_empty(uset);
1472 }
1473
1474 static int zip_entry(void **entry, void *user)
1475 {
1476         isl_map *map = *entry;
1477         isl_union_map **res = user;
1478
1479         if (!isl_map_can_zip(map))
1480                 return 0;
1481
1482         *res = isl_union_map_add_map(*res, isl_map_zip(isl_map_copy(map)));
1483
1484         return 0;
1485 }
1486
1487 __isl_give isl_union_map *isl_union_map_zip(__isl_take isl_union_map *umap)
1488 {
1489         return cond_un_op(umap, &zip_entry);
1490 }