isl_union_map.c

   1 /*
   2  * Copyright 2010      INRIA Saclay
   3  *
   4  * Use of this software is governed by the GNU LGPLv2.1 license
   5  *
   6  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   7  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   8  * 91893 Orsay, France
   9  */
  10
  11 #include <isl_ctx.h>
  12 #include <isl_hash.h>
  13 #include <isl_map.h>
  14 #include <isl_set.h>
  15 #include <isl_dim_private.h>
  16 #include <isl_map_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_foreach_map(__isl_keep isl_union_map *umap,
 341         int (*fn)(__isl_take isl_map *map, void *user), void *user)
 342 {
 343         struct isl_union_map_foreach_data data = { fn, user };
 344
 345         if (!umap)
 346                 return -1;
 347
 348         return isl_hash_table_foreach(umap->dim->ctx, &umap->table,
 349                                       &call_on_copy, &data);
 350 }
 351
 352 int isl_union_set_foreach_set(__isl_keep isl_union_set *uset,
 353         int (*fn)(__isl_take isl_set *set, void *user), void *user)
 354 {
 355         return isl_union_map_foreach_map(uset,
 356                 (int(*)(__isl_take isl_map *, void*))fn, user);
 357 }
 358
 359 struct isl_union_set_foreach_point_data {
 360         int (*fn)(__isl_take isl_point *pnt, void *user);
 361         void *user;
 362 };
 363
 364 static int foreach_point(__isl_take isl_set *set, void *user)
 365 {
 366         struct isl_union_set_foreach_point_data *data = user;
 367         int r;
 368
 369         r = isl_set_foreach_point(set, data->fn, data->user);
 370         isl_set_free(set);
 371
 372         return r;
 373 }
 374
 375 int isl_union_set_foreach_point(__isl_keep isl_union_set *uset,
 376         int (*fn)(__isl_take isl_point *pnt, void *user), void *user)
 377 {
 378         struct isl_union_set_foreach_point_data data = { fn, user };
 379         return isl_union_set_foreach_set(uset, &foreach_point, &data);
 380 }
 381
 382 struct isl_union_map_gen_bin_data {
 383         isl_union_map *umap2;
 384         isl_union_map *res;
 385 };
 386
 387 static int subtract_entry(void **entry, void *user)
 388 {
 389         struct isl_union_map_gen_bin_data *data = user;
 390         uint32_t hash;
 391         struct isl_hash_table_entry *entry2;
 392         isl_map *map = *entry;
 393
 394         hash = isl_dim_get_hash(map->dim);
 395         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
 396                                      hash, &has_dim, map->dim, 0);
 397         map = isl_map_copy(map);
 398         if (entry2) {
 399                 int empty;
 400                 map = isl_map_subtract(map, isl_map_copy(entry2->data));
 401
 402                 empty = isl_map_is_empty(map);
 403                 if (empty < 0) {
 404                         isl_map_free(map);
 405                         return -1;
 406                 }
 407                 if (empty) {
 408                         isl_map_free(map);
 409                         return 0;
 410                 }
 411         }
 412         data->res = isl_union_map_add_map(data->res, map);
 413
 414         return 0;
 415 }
 416
 417 static __isl_give isl_union_map *gen_bin_op(__isl_take isl_union_map *umap1,
 418         __isl_take isl_union_map *umap2, int (*fn)(void **, void *))
 419 {
 420         struct isl_union_map_gen_bin_data data = { NULL, NULL };
 421
 422         umap1 = isl_union_map_align_params(umap1, isl_union_map_get_dim(umap2));
 423         umap2 = isl_union_map_align_params(umap2, isl_union_map_get_dim(umap1));
 424
 425         if (!umap1 || !umap2)
 426                 goto error;
 427
 428         data.umap2 = umap2;
 429         data.res = isl_union_map_alloc(isl_dim_copy(umap1->dim),
 430                                        umap1->table.n);
 431         if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
 432                                    fn, &data) < 0)
 433                 goto error;
 434
 435         isl_union_map_free(umap1);
 436         isl_union_map_free(umap2);
 437         return data.res;
 438 error:
 439         isl_union_map_free(umap1);
 440         isl_union_map_free(umap2);
 441         isl_union_map_free(data.res);
 442         return NULL;
 443 }
 444
 445 __isl_give isl_union_map *isl_union_map_subtract(
 446         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 447 {
 448         return gen_bin_op(umap1, umap2, &subtract_entry);
 449 }
 450
 451 __isl_give isl_union_set *isl_union_set_subtract(
 452         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
 453 {
 454         return isl_union_map_subtract(uset1, uset2);
 455 }
 456
 457 struct isl_union_map_match_bin_data {
 458         isl_union_map *umap2;
 459         isl_union_map *res;
 460         __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*);
 461 };
 462
 463 static int match_bin_entry(void **entry, void *user)
 464 {
 465         struct isl_union_map_match_bin_data *data = user;
 466         uint32_t hash;
 467         struct isl_hash_table_entry *entry2;
 468         isl_map *map = *entry;
 469         int empty;
 470
 471         hash = isl_dim_get_hash(map->dim);
 472         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
 473                                      hash, &has_dim, map->dim, 0);
 474         if (!entry2)
 475                 return 0;
 476
 477         map = isl_map_copy(map);
 478         map = data->fn(map, isl_map_copy(entry2->data));
 479
 480         empty = isl_map_is_empty(map);
 481         if (empty < 0) {
 482                 isl_map_free(map);
 483                 return -1;
 484         }
 485         if (empty) {
 486                 isl_map_free(map);
 487                 return 0;
 488         }
 489
 490         data->res = isl_union_map_add_map(data->res, map);
 491
 492         return 0;
 493 }
 494
 495 static __isl_give isl_union_map *match_bin_op(__isl_take isl_union_map *umap1,
 496         __isl_take isl_union_map *umap2,
 497         __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*))
 498 {
 499         struct isl_union_map_match_bin_data data = { NULL, NULL, fn };
 500
 501         umap1 = isl_union_map_align_params(umap1, isl_union_map_get_dim(umap2));
 502         umap2 = isl_union_map_align_params(umap2, isl_union_map_get_dim(umap1));
 503
 504         if (!umap1 || !umap2)
 505                 goto error;
 506
 507         data.umap2 = umap2;
 508         data.res = isl_union_map_alloc(isl_dim_copy(umap1->dim),
 509                                        umap1->table.n);
 510         if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
 511                                    &match_bin_entry, &data) < 0)
 512                 goto error;
 513
 514         isl_union_map_free(umap1);
 515         isl_union_map_free(umap2);
 516         return data.res;
 517 error:
 518         isl_union_map_free(umap1);
 519         isl_union_map_free(umap2);
 520         isl_union_map_free(data.res);
 521         return NULL;
 522 }
 523
 524 __isl_give isl_union_map *isl_union_map_intersect(
 525         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 526 {
 527         return match_bin_op(umap1, umap2, &isl_map_intersect);
 528 }
 529
 530 __isl_give isl_union_set *isl_union_set_intersect(
 531         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
 532 {
 533         return isl_union_map_intersect(uset1, uset2);
 534 }
 535
 536 __isl_give isl_union_map *isl_union_map_gist(__isl_take isl_union_map *umap,
 537         __isl_take isl_union_map *context)
 538 {
 539         return match_bin_op(umap, context, &isl_map_gist);
 540 }
 541
 542 __isl_give isl_union_set *isl_union_set_gist(__isl_take isl_union_set *uset,
 543         __isl_take isl_union_set *context)
 544 {
 545         return isl_union_map_gist(uset, context);
 546 }
 547
 548 static __isl_give isl_map *lex_le_set(__isl_take isl_map *set1,
 549         __isl_take isl_map *set2)
 550 {
 551         return isl_set_lex_le_set((isl_set *)set1, (isl_set *)set2);
 552 }
 553
 554 static __isl_give isl_map *lex_lt_set(__isl_take isl_map *set1,
 555         __isl_take isl_map *set2)
 556 {
 557         return isl_set_lex_lt_set((isl_set *)set1, (isl_set *)set2);
 558 }
 559
 560 __isl_give isl_union_set *isl_union_set_lex_lt_union_set(
 561         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
 562 {
 563         return match_bin_op(uset1, uset2, &lex_lt_set);
 564 }
 565
 566 __isl_give isl_union_set *isl_union_set_lex_le_union_set(
 567         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
 568 {
 569         return match_bin_op(uset1, uset2, &lex_le_set);
 570 }
 571
 572 __isl_give isl_union_set *isl_union_set_lex_gt_union_set(
 573         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
 574 {
 575         return isl_union_set_lex_lt_union_set(uset2, uset1);
 576 }
 577
 578 __isl_give isl_union_set *isl_union_set_lex_ge_union_set(
 579         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
 580 {
 581         return isl_union_set_lex_le_union_set(uset2, uset1);
 582 }
 583
 584 __isl_give isl_union_map *isl_union_map_lex_gt_union_map(
 585         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 586 {
 587         return isl_union_map_lex_lt_union_map(umap2, umap1);
 588 }
 589
 590 __isl_give isl_union_map *isl_union_map_lex_ge_union_map(
 591         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 592 {
 593         return isl_union_map_lex_le_union_map(umap2, umap1);
 594 }
 595
 596 static int intersect_domain_entry(void **entry, void *user)
 597 {
 598         struct isl_union_map_gen_bin_data *data = user;
 599         uint32_t hash;
 600         struct isl_hash_table_entry *entry2;
 601         isl_dim *dim;
 602         isl_map *map = *entry;
 603         int empty;
 604
 605         dim = isl_map_get_dim(map);
 606         dim = isl_dim_domain(dim);
 607         hash = isl_dim_get_hash(dim);
 608         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
 609                                      hash, &has_dim, dim, 0);
 610         isl_dim_free(dim);
 611         if (!entry2)
 612                 return 0;
 613
 614         map = isl_map_copy(map);
 615         map = isl_map_intersect_domain(map, isl_set_copy(entry2->data));
 616
 617         empty = isl_map_is_empty(map);
 618         if (empty < 0) {
 619                 isl_map_free(map);
 620                 return -1;
 621         }
 622         if (empty) {
 623                 isl_map_free(map);
 624                 return 0;
 625         }
 626
 627         data->res = isl_union_map_add_map(data->res, map);
 628
 629         return 0;
 630 }
 631
 632 __isl_give isl_union_map *isl_union_map_intersect_domain(
 633         __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
 634 {
 635         return gen_bin_op(umap, uset, &intersect_domain_entry);
 636 }
 637
 638 struct isl_union_map_bin_data {
 639         isl_union_map *umap2;
 640         isl_union_map *res;
 641         isl_map *map;
 642         int (*fn)(void **entry, void *user);
 643 };
 644
 645 static int apply_range_entry(void **entry, void *user)
 646 {
 647         struct isl_union_map_bin_data *data = user;
 648         isl_map *map2 = *entry;
 649         int empty;
 650
 651         if (!isl_dim_tuple_match(data->map->dim, isl_dim_out,
 652                                  map2->dim, isl_dim_in))
 653                 return 0;
 654
 655         map2 = isl_map_apply_range(isl_map_copy(data->map), isl_map_copy(map2));
 656
 657         empty = isl_map_is_empty(map2);
 658         if (empty < 0) {
 659                 isl_map_free(map2);
 660                 return -1;
 661         }
 662         if (empty) {
 663                 isl_map_free(map2);
 664                 return 0;
 665         }
 666
 667         data->res = isl_union_map_add_map(data->res, map2);
 668
 669         return 0;
 670 }
 671
 672 static int bin_entry(void **entry, void *user)
 673 {
 674         struct isl_union_map_bin_data *data = user;
 675         isl_map *map = *entry;
 676
 677         data->map = map;
 678         if (isl_hash_table_foreach(data->umap2->dim->ctx, &data->umap2->table,
 679                                    data->fn, data) < 0)
 680                 return -1;
 681
 682         return 0;
 683 }
 684
 685 static __isl_give isl_union_map *bin_op(__isl_take isl_union_map *umap1,
 686         __isl_take isl_union_map *umap2, int (*fn)(void **entry, void *user))
 687 {
 688         struct isl_union_map_bin_data data = { NULL, NULL, NULL, fn };
 689
 690         umap1 = isl_union_map_align_params(umap1, isl_union_map_get_dim(umap2));
 691         umap2 = isl_union_map_align_params(umap2, isl_union_map_get_dim(umap1));
 692
 693         if (!umap1 || !umap2)
 694                 goto error;
 695
 696         data.umap2 = umap2;
 697         data.res = isl_union_map_alloc(isl_dim_copy(umap1->dim),
 698                                        umap1->table.n);
 699         if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
 700                                    &bin_entry, &data) < 0)
 701                 goto error;
 702
 703         isl_union_map_free(umap1);
 704         isl_union_map_free(umap2);
 705         return data.res;
 706 error:
 707         isl_union_map_free(umap1);
 708         isl_union_map_free(umap2);
 709         isl_union_map_free(data.res);
 710         return NULL;
 711 }
 712
 713 __isl_give isl_union_map *isl_union_map_apply_range(
 714         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 715 {
 716         return bin_op(umap1, umap2, &apply_range_entry);
 717 }
 718
 719 __isl_give isl_union_map *isl_union_map_apply_domain(
 720         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 721 {
 722         umap1 = isl_union_map_reverse(umap1);
 723         umap1 = isl_union_map_apply_range(umap1, umap2);
 724         return isl_union_map_reverse(umap1);
 725 }
 726
 727 __isl_give isl_union_set *isl_union_set_apply(
 728         __isl_take isl_union_set *uset, __isl_take isl_union_map *umap)
 729 {
 730         return isl_union_map_apply_range(uset, umap);
 731 }
 732
 733 static int map_lex_lt_entry(void **entry, void *user)
 734 {
 735         struct isl_union_map_bin_data *data = user;
 736         isl_map *map2 = *entry;
 737
 738         if (!isl_dim_tuple_match(data->map->dim, isl_dim_out,
 739                                  map2->dim, isl_dim_out))
 740                 return 0;
 741
 742         map2 = isl_map_lex_lt_map(isl_map_copy(data->map), isl_map_copy(map2));
 743
 744         data->res = isl_union_map_add_map(data->res, map2);
 745
 746         return 0;
 747 }
 748
 749 __isl_give isl_union_map *isl_union_map_lex_lt_union_map(
 750         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 751 {
 752         return bin_op(umap1, umap2, &map_lex_lt_entry);
 753 }
 754
 755 static int map_lex_le_entry(void **entry, void *user)
 756 {
 757         struct isl_union_map_bin_data *data = user;
 758         isl_map *map2 = *entry;
 759
 760         if (!isl_dim_tuple_match(data->map->dim, isl_dim_out,
 761                                  map2->dim, isl_dim_out))
 762                 return 0;
 763
 764         map2 = isl_map_lex_le_map(isl_map_copy(data->map), isl_map_copy(map2));
 765
 766         data->res = isl_union_map_add_map(data->res, map2);
 767
 768         return 0;
 769 }
 770
 771 __isl_give isl_union_map *isl_union_map_lex_le_union_map(
 772         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
 773 {
 774         return bin_op(umap1, umap2, &map_lex_le_entry);
 775 }
 776
 777 static int product_entry(void **entry, void *user)
 778 {
 779         struct isl_union_map_bin_data *data = user;
 780         isl_map *map2 = *entry;
 781
 782         map2 = isl_map_product(isl_map_copy(data->map), isl_map_copy(map2));
 783
 784         data->res = isl_union_map_add_map(data->res, map2);
 785
 786         return 0;
 787 }
 788
 789 __isl_give isl_union_map *isl_union_map_product(__isl_take isl_union_map *umap1,
 790         __isl_take isl_union_map *umap2)
 791 {
 792         return bin_op(umap1, umap2, &product_entry);
 793 }
 794
 795 __isl_give isl_union_set *isl_union_set_product(__isl_take isl_union_set *uset1,
 796         __isl_take isl_union_set *uset2)
 797 {
 798         return isl_union_map_product(uset1, uset2);
 799 }
 800
 801 __isl_give isl_union_map *isl_union_map_from_range(
 802         __isl_take isl_union_set *uset)
 803 {
 804         return uset;
 805 }
 806
 807 __isl_give isl_union_map *isl_union_map_from_domain(
 808         __isl_take isl_union_set *uset)
 809 {
 810         return isl_union_map_reverse(isl_union_map_from_range(uset));
 811 }
 812
 813 __isl_give isl_union_map *isl_union_map_from_domain_and_range(
 814         __isl_take isl_union_set *domain, __isl_take isl_union_set *range)
 815 {
 816         return isl_union_map_apply_range(isl_union_map_from_domain(domain),
 817                                          isl_union_map_from_range(range));
 818 }
 819
 820 static __isl_give isl_union_map *un_op(__isl_take isl_union_map *umap,
 821         int (*fn)(void **, void *), int cow)
 822 {
 823         if (cow)
 824                 umap = isl_union_map_cow(umap);
 825         if (!umap)
 826                 return NULL;
 827
 828         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, NULL) < 0)
 829                 goto error;
 830
 831         return umap;
 832 error:
 833         isl_union_map_free(umap);
 834         return NULL;
 835 }
 836
 837 static int affine_entry(void **entry, void *user)
 838 {
 839         isl_map **map = (isl_map **)entry;
 840
 841         *map = isl_map_from_basic_map(isl_map_affine_hull(*map));
 842
 843         return *map ? 0 : -1;
 844 }
 845
 846 __isl_give isl_union_map *isl_union_map_affine_hull(
 847         __isl_take isl_union_map *umap)
 848 {
 849         return un_op(umap, &affine_entry, 1);
 850 }
 851
 852 __isl_give isl_union_set *isl_union_set_affine_hull(
 853         __isl_take isl_union_set *uset)
 854 {
 855         return isl_union_map_affine_hull(uset);
 856 }
 857
 858 static int coalesce_entry(void **entry, void *user)
 859 {
 860         isl_map **map = (isl_map **)entry;
 861
 862         *map = isl_map_coalesce(*map);
 863
 864         return *map ? 0 : -1;
 865 }
 866
 867 __isl_give isl_union_map *isl_union_map_coalesce(
 868         __isl_take isl_union_map *umap)
 869 {
 870         return un_op(umap, &coalesce_entry, 0);
 871 }
 872
 873 __isl_give isl_union_set *isl_union_set_coalesce(
 874         __isl_take isl_union_set *uset)
 875 {
 876         return isl_union_map_coalesce(uset);
 877 }
 878
 879 static int compute_divs_entry(void **entry, void *user)
 880 {
 881         isl_map **map = (isl_map **)entry;
 882
 883         *map = isl_map_compute_divs(*map);
 884
 885         return *map ? 0 : -1;
 886 }
 887
 888 __isl_give isl_union_map *isl_union_map_compute_divs(
 889         __isl_take isl_union_map *umap)
 890 {
 891         return un_op(umap, &compute_divs_entry, 0);
 892 }
 893
 894 __isl_give isl_union_set *isl_union_set_compute_divs(
 895         __isl_take isl_union_set *uset)
 896 {
 897         return isl_union_map_compute_divs(uset);
 898 }
 899
 900 static int lexmin_entry(void **entry, void *user)
 901 {
 902         isl_map **map = (isl_map **)entry;
 903
 904         *map = isl_map_lexmin(*map);
 905
 906         return *map ? 0 : -1;
 907 }
 908
 909 __isl_give isl_union_map *isl_union_map_lexmin(
 910         __isl_take isl_union_map *umap)
 911 {
 912         return un_op(umap, &lexmin_entry, 1);
 913 }
 914
 915 __isl_give isl_union_set *isl_union_set_lexmin(
 916         __isl_take isl_union_set *uset)
 917 {
 918         return isl_union_map_lexmin(uset);
 919 }
 920
 921 static int lexmax_entry(void **entry, void *user)
 922 {
 923         isl_map **map = (isl_map **)entry;
 924
 925         *map = isl_map_lexmax(*map);
 926
 927         return *map ? 0 : -1;
 928 }
 929
 930 __isl_give isl_union_map *isl_union_map_lexmax(
 931         __isl_take isl_union_map *umap)
 932 {
 933         return un_op(umap, &lexmax_entry, 1);
 934 }
 935
 936 __isl_give isl_union_set *isl_union_set_lexmax(
 937         __isl_take isl_union_set *uset)
 938 {
 939         return isl_union_map_lexmax(uset);
 940 }
 941
 942 static __isl_give isl_union_set *cond_un_op(__isl_take isl_union_map *umap,
 943         int (*fn)(void **, void *))
 944 {
 945         isl_union_set *res;
 946
 947         if (!umap)
 948                 return NULL;
 949
 950         res = isl_union_map_alloc(isl_dim_copy(umap->dim), umap->table.n);
 951         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, &res) < 0)
 952                 goto error;
 953
 954         isl_union_map_free(umap);
 955         return res;
 956 error:
 957         isl_union_map_free(umap);
 958         isl_union_set_free(res);
 959         return NULL;
 960 }
 961
 962 static int reverse_entry(void **entry, void *user)
 963 {
 964         isl_map *map = *entry;
 965         isl_union_map **res = user;
 966
 967         *res = isl_union_map_add_map(*res, isl_map_reverse(isl_map_copy(map)));
 968
 969         return 0;
 970 }
 971
 972 __isl_give isl_union_map *isl_union_map_reverse(__isl_take isl_union_map *umap)
 973 {
 974         return cond_un_op(umap, &reverse_entry);
 975 }
 976
 977 static int domain_entry(void **entry, void *user)
 978 {
 979         isl_map *map = *entry;
 980         isl_union_set **res = user;
 981
 982         *res = isl_union_set_add_set(*res, isl_map_domain(isl_map_copy(map)));
 983
 984         return 0;
 985 }
 986
 987 __isl_give isl_union_set *isl_union_map_domain(__isl_take isl_union_map *umap)
 988 {
 989         return cond_un_op(umap, &domain_entry);
 990 }
 991
 992 static int range_entry(void **entry, void *user)
 993 {
 994         isl_map *map = *entry;
 995         isl_union_set **res = user;
 996
 997         *res = isl_union_set_add_set(*res, isl_map_range(isl_map_copy(map)));
 998
 999         return 0;
1000 }
1001
1002 __isl_give isl_union_set *isl_union_map_range(__isl_take isl_union_map *umap)
1003 {
1004         return cond_un_op(umap, &range_entry);
1005 }
1006
1007 static int domain_map_entry(void **entry, void *user)
1008 {
1009         isl_map *map = *entry;
1010         isl_union_set **res = user;
1011
1012         *res = isl_union_map_add_map(*res,
1013                                         isl_map_domain_map(isl_map_copy(map)));
1014
1015         return 0;
1016 }
1017
1018 __isl_give isl_union_map *isl_union_map_domain_map(
1019         __isl_take isl_union_map *umap)
1020 {
1021         return cond_un_op(umap, &domain_map_entry);
1022 }
1023
1024 static int range_map_entry(void **entry, void *user)
1025 {
1026         isl_map *map = *entry;
1027         isl_union_set **res = user;
1028
1029         *res = isl_union_map_add_map(*res,
1030                                         isl_map_range_map(isl_map_copy(map)));
1031
1032         return 0;
1033 }
1034
1035 __isl_give isl_union_map *isl_union_map_range_map(
1036         __isl_take isl_union_map *umap)
1037 {
1038         return cond_un_op(umap, &range_map_entry);
1039 }
1040
1041 static int deltas_entry(void **entry, void *user)
1042 {
1043         isl_map *map = *entry;
1044         isl_union_set **res = user;
1045
1046         if (!isl_dim_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1047                 return 0;
1048
1049         *res = isl_union_set_add_set(*res, isl_map_deltas(isl_map_copy(map)));
1050
1051         return 0;
1052 }
1053
1054 __isl_give isl_union_set *isl_union_map_deltas(__isl_take isl_union_map *umap)
1055 {
1056         return cond_un_op(umap, &deltas_entry);
1057 }
1058
1059 static int unwrap_entry(void **entry, void *user)
1060 {
1061         isl_set *set = *entry;
1062         isl_union_set **res = user;
1063
1064         if (!isl_set_is_wrapping(set))
1065                 return 0;
1066
1067         *res = isl_union_map_add_map(*res, isl_set_unwrap(isl_set_copy(set)));
1068
1069         return 0;
1070 }
1071
1072 __isl_give isl_union_map *isl_union_set_unwrap(__isl_take isl_union_set *uset)
1073 {
1074         return cond_un_op(uset, &unwrap_entry);
1075 }
1076
1077 static int wrap_entry(void **entry, void *user)
1078 {
1079         isl_map *map = *entry;
1080         isl_union_set **res = user;
1081
1082         *res = isl_union_set_add_set(*res, isl_map_wrap(isl_map_copy(map)));
1083
1084         return 0;
1085 }
1086
1087 __isl_give isl_union_set *isl_union_map_wrap(__isl_take isl_union_map *umap)
1088 {
1089         return cond_un_op(umap, &wrap_entry);
1090 }
1091
1092 struct isl_union_map_is_subset_data {
1093         isl_union_map *umap2;
1094         int is_subset;
1095 };
1096
1097 static int is_subset_entry(void **entry, void *user)
1098 {
1099         struct isl_union_map_is_subset_data *data = user;
1100         uint32_t hash;
1101         struct isl_hash_table_entry *entry2;
1102         isl_map *map = *entry;
1103
1104         hash = isl_dim_get_hash(map->dim);
1105         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1106                                      hash, &has_dim, map->dim, 0);
1107         if (!entry2) {
1108                 data->is_subset = 0;
1109                 return -1;
1110         }
1111
1112         data->is_subset = isl_map_is_subset(map, entry2->data);
1113         if (data->is_subset < 0 || !data->is_subset)
1114                 return -1;
1115
1116         return 0;
1117 }
1118
1119 int isl_union_map_is_subset(__isl_keep isl_union_map *umap1,
1120         __isl_keep isl_union_map *umap2)
1121 {
1122         struct isl_union_map_is_subset_data data = { NULL, 1 };
1123
1124         umap1 = isl_union_map_copy(umap1);
1125         umap2 = isl_union_map_copy(umap2);
1126         umap1 = isl_union_map_align_params(umap1, isl_union_map_get_dim(umap2));
1127         umap2 = isl_union_map_align_params(umap2, isl_union_map_get_dim(umap1));
1128
1129         if (!umap1 || !umap2)
1130                 goto error;
1131
1132         data.umap2 = umap2;
1133         if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1134                                    &is_subset_entry, &data) < 0 &&
1135             data.is_subset)
1136                 goto error;
1137
1138         isl_union_map_free(umap1);
1139         isl_union_map_free(umap2);
1140
1141         return data.is_subset;
1142 error:
1143         isl_union_map_free(umap1);
1144         isl_union_map_free(umap2);
1145         return -1;
1146 }
1147
1148 int isl_union_map_is_equal(__isl_keep isl_union_map *umap1,
1149         __isl_keep isl_union_map *umap2)
1150 {
1151         int is_subset;
1152
1153         if (!umap1 || !umap2)
1154                 return -1;
1155         is_subset = isl_union_map_is_subset(umap1, umap2);
1156         if (is_subset != 1)
1157                 return is_subset;
1158         is_subset = isl_union_map_is_subset(umap2, umap1);
1159         return is_subset;
1160 }
1161
1162 int isl_union_map_is_strict_subset(__isl_keep isl_union_map *umap1,
1163         __isl_keep isl_union_map *umap2)
1164 {
1165         int is_subset;
1166
1167         if (!umap1 || !umap2)
1168                 return -1;
1169         is_subset = isl_union_map_is_subset(umap1, umap2);
1170         if (is_subset != 1)
1171                 return is_subset;
1172         is_subset = isl_union_map_is_subset(umap2, umap1);
1173         if (is_subset == -1)
1174                 return is_subset;
1175         return !is_subset;
1176 }
1177
1178 static int sample_entry(void **entry, void *user)
1179 {
1180         isl_basic_map **sample = (isl_basic_map **)user;
1181         isl_map *map = *entry;
1182
1183         *sample = isl_map_sample(isl_map_copy(map));
1184         if (!*sample)
1185                 return -1;
1186         if (!isl_basic_map_fast_is_empty(*sample))
1187                 return -1;
1188         return 0;
1189 }
1190
1191 __isl_give isl_basic_map *isl_union_map_sample(__isl_take isl_union_map *umap)
1192 {
1193         isl_basic_map *sample = NULL;
1194
1195         if (!umap)
1196                 return NULL;
1197
1198         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1199                                    &sample_entry, &sample) < 0 &&
1200             !sample)
1201                 goto error;
1202
1203         isl_union_map_free(umap);
1204
1205         return sample;
1206 error:
1207         isl_union_map_free(umap);
1208         return NULL;
1209 }
1210
1211 __isl_give isl_basic_set *isl_union_set_sample(__isl_take isl_union_set *uset)
1212 {
1213         return (isl_basic_set *)isl_union_map_sample(uset);
1214 }
1215
1216 static int empty_entry(void **entry, void *user)
1217 {
1218         int *empty = user;
1219         isl_map *map = *entry;
1220
1221         if (isl_map_is_empty(map))
1222                 return 0;
1223
1224         *empty = 0;
1225
1226         return -1;
1227 }
1228
1229 __isl_give int isl_union_map_is_empty(__isl_keep isl_union_map *umap)
1230 {
1231         int empty = 1;
1232
1233         if (!umap)
1234                 return -1;
1235
1236         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1237                                    &empty_entry, &empty) < 0 && empty)
1238                 return -1;
1239
1240         return empty;
1241 }
1242
1243 int isl_union_set_is_empty(__isl_keep isl_union_set *uset)
1244 {
1245         return isl_union_map_is_empty(uset);
1246 }