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