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