2 * Copyright 2010 INRIA Saclay
4 * Use of this software is governed by the GNU LGPLv2.1 license
6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
15 #include <isl_dim_private.h>
16 #include <isl_union_map_private.h>
17 #include <isl_union_set.h>
19 static __isl_give isl_union_map *isl_union_map_alloc(__isl_take isl_dim *dim,
27 umap = isl_calloc_type(dim->ctx, isl_union_map);
33 if (isl_hash_table_init(dim->ctx, &umap->table, size) < 0)
39 isl_union_map_free(umap);
43 __isl_give isl_union_map *isl_union_map_empty(__isl_take isl_dim *dim)
45 return isl_union_map_alloc(dim, 16);
48 __isl_give isl_union_set *isl_union_set_empty(__isl_take isl_dim *dim)
50 return isl_union_map_empty(dim);
53 isl_ctx *isl_union_map_get_ctx(__isl_keep isl_union_map *umap)
55 return umap ? umap->dim->ctx : NULL;
58 __isl_give isl_dim *isl_union_map_get_dim(__isl_keep isl_union_map *umap)
62 return isl_dim_copy(umap->dim);
65 __isl_give isl_dim *isl_union_set_get_dim(__isl_keep isl_union_set *uset)
67 return isl_union_map_get_dim(uset);
70 static int free_umap_entry(void **entry, void *user)
72 isl_map *map = *entry;
77 static int add_map(__isl_take isl_map *map, void *user)
79 isl_union_map **umap = (isl_union_map **)user;
81 *umap = isl_union_map_add_map(*umap, map);
86 __isl_give isl_union_map *isl_union_map_dup(__isl_keep isl_union_map *umap)
93 dup = isl_union_map_empty(isl_dim_copy(umap->dim));
94 if (isl_union_map_foreach_map(umap, &add_map, &dup) < 0)
98 isl_union_map_free(dup);
102 __isl_give isl_union_map *isl_union_map_cow(__isl_take isl_union_map *umap)
110 return isl_union_map_dup(umap);
113 __isl_give isl_union_map *isl_union_map_union(__isl_take isl_union_map *umap1,
114 __isl_take isl_union_map *umap2)
116 umap1 = isl_union_map_cow(umap1);
118 if (!umap1 || !umap2)
121 if (isl_union_map_foreach_map(umap2, &add_map, &umap1) < 0)
124 isl_union_map_free(umap2);
128 isl_union_map_free(umap1);
129 isl_union_map_free(umap2);
133 __isl_give isl_union_set *isl_union_set_union(__isl_take isl_union_set *uset1,
134 __isl_take isl_union_set *uset2)
136 return isl_union_map_union(uset1, uset2);
139 __isl_give isl_union_map *isl_union_map_copy(__isl_keep isl_union_map *umap)
148 __isl_give isl_union_set *isl_union_set_copy(__isl_keep isl_union_set *uset)
150 return isl_union_map_copy(uset);
153 void isl_union_map_free(__isl_take isl_union_map *umap)
161 isl_hash_table_foreach(umap->dim->ctx, &umap->table,
162 &free_umap_entry, NULL);
163 isl_hash_table_clear(&umap->table);
164 isl_dim_free(umap->dim);
168 void isl_union_set_free(__isl_take isl_union_set *uset)
170 isl_union_map_free(uset);
173 static int has_dim(const void *entry, const void *val)
175 isl_map *map = (isl_map *)entry;
176 isl_dim *dim = (isl_dim *)val;
178 return isl_dim_equal(map->dim, dim);
181 __isl_give isl_union_map *isl_union_map_add_map(__isl_take isl_union_map *umap,
182 __isl_take isl_map *map)
185 struct isl_hash_table_entry *entry;
187 if (isl_map_fast_is_empty(map)) {
192 umap = isl_union_map_cow(umap);
197 isl_assert(map->ctx, isl_dim_match(map->dim, isl_dim_param, umap->dim,
198 isl_dim_param), goto error);
200 hash = isl_dim_get_hash(map->dim);
201 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
202 &has_dim, map->dim, 1);
209 entry->data = isl_map_union(entry->data, isl_map_copy(map));
218 isl_union_map_free(umap);
222 __isl_give isl_union_set *isl_union_set_add_set(__isl_take isl_union_set *uset,
223 __isl_take isl_set *set)
225 return isl_union_map_add_map(uset, (isl_map *)set);
228 __isl_give isl_union_map *isl_union_map_from_map(__isl_take isl_map *map)
236 dim = isl_map_get_dim(map);
237 dim = isl_dim_drop(dim, isl_dim_in, 0, isl_dim_size(dim, isl_dim_in));
238 dim = isl_dim_drop(dim, isl_dim_out, 0, isl_dim_size(dim, isl_dim_out));
239 umap = isl_union_map_empty(dim);
240 umap = isl_union_map_add_map(umap, map);
245 __isl_give isl_union_set *isl_union_set_from_set(__isl_take isl_set *set)
247 return isl_union_map_from_map((isl_map *)set);
250 struct isl_union_map_foreach_data
252 int (*fn)(__isl_take isl_map *map, void *user);
256 static int call_on_copy(void **entry, void *user)
258 isl_map *map = *entry;
259 struct isl_union_map_foreach_data *data;
260 data = (struct isl_union_map_foreach_data *)user;
262 return data->fn(isl_map_copy(map), data->user);
265 int isl_union_map_foreach_map(__isl_keep isl_union_map *umap,
266 int (*fn)(__isl_take isl_map *map, void *user), void *user)
268 struct isl_union_map_foreach_data data = { fn, user };
273 return isl_hash_table_foreach(umap->dim->ctx, &umap->table,
274 &call_on_copy, &data);
277 int isl_union_set_foreach_set(__isl_keep isl_union_set *uset,
278 int (*fn)(__isl_take isl_set *set, void *user), void *user)
280 return isl_union_map_foreach_map(uset,
281 (int(*)(__isl_take isl_map *, void*))fn, user);
284 struct isl_union_set_foreach_point_data {
285 int (*fn)(__isl_take isl_point *pnt, void *user);
289 static int foreach_point(__isl_take isl_set *set, void *user)
291 struct isl_union_set_foreach_point_data *data = user;
294 r = isl_set_foreach_point(set, data->fn, data->user);
300 int isl_union_set_foreach_point(__isl_keep isl_union_set *uset,
301 int (*fn)(__isl_take isl_point *pnt, void *user), void *user)
303 struct isl_union_set_foreach_point_data data = { fn, user };
304 return isl_union_set_foreach_set(uset, &foreach_point, &data);
307 struct isl_union_map_gen_bin_data {
308 isl_union_map *umap2;
312 static int subtract_entry(void **entry, void *user)
314 struct isl_union_map_gen_bin_data *data = user;
316 struct isl_hash_table_entry *entry2;
317 isl_map *map = *entry;
319 hash = isl_dim_get_hash(map->dim);
320 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
321 hash, &has_dim, map->dim, 0);
322 map = isl_map_copy(map);
325 map = isl_map_subtract(map, isl_map_copy(entry2->data));
327 empty = isl_map_is_empty(map);
337 data->res = isl_union_map_add_map(data->res, map);
342 static __isl_give isl_union_map *gen_bin_op(__isl_take isl_union_map *umap1,
343 __isl_take isl_union_map *umap2, int (*fn)(void **, void *))
345 struct isl_union_map_gen_bin_data data = { umap2, NULL };
347 if (!umap1 || !umap2)
350 data.res = isl_union_map_alloc(isl_dim_copy(umap1->dim),
352 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
356 isl_union_map_free(umap1);
357 isl_union_map_free(umap2);
360 isl_union_map_free(umap1);
361 isl_union_map_free(umap2);
362 isl_union_map_free(data.res);
366 __isl_give isl_union_map *isl_union_map_subtract(
367 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
369 return gen_bin_op(umap1, umap2, &subtract_entry);
372 __isl_give isl_union_set *isl_union_set_subtract(
373 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
375 return isl_union_map_subtract(uset1, uset2);
378 struct isl_union_map_match_bin_data {
379 isl_union_map *umap2;
381 __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*);
384 static int match_bin_entry(void **entry, void *user)
386 struct isl_union_map_match_bin_data *data = user;
388 struct isl_hash_table_entry *entry2;
389 isl_map *map = *entry;
392 hash = isl_dim_get_hash(map->dim);
393 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
394 hash, &has_dim, map->dim, 0);
398 map = isl_map_copy(map);
399 map = data->fn(map, isl_map_copy(entry2->data));
401 empty = isl_map_is_empty(map);
411 data->res = isl_union_map_add_map(data->res, map);
416 static __isl_give isl_union_map *match_bin_op(__isl_take isl_union_map *umap1,
417 __isl_take isl_union_map *umap2,
418 __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*))
420 struct isl_union_map_match_bin_data data = { umap2, NULL, fn };
422 if (!umap1 || !umap2)
425 data.res = isl_union_map_alloc(isl_dim_copy(umap1->dim),
427 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
428 &match_bin_entry, &data) < 0)
431 isl_union_map_free(umap1);
432 isl_union_map_free(umap2);
435 isl_union_map_free(umap1);
436 isl_union_map_free(umap2);
437 isl_union_map_free(data.res);
441 __isl_give isl_union_map *isl_union_map_intersect(
442 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
444 return match_bin_op(umap1, umap2, &isl_map_intersect);
447 __isl_give isl_union_set *isl_union_set_intersect(
448 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
450 return isl_union_map_intersect(uset1, uset2);
453 __isl_give isl_union_map *isl_union_map_gist(__isl_take isl_union_map *umap,
454 __isl_take isl_union_map *context)
456 return match_bin_op(umap, context, &isl_map_gist);
459 __isl_give isl_union_set *isl_union_set_gist(__isl_take isl_union_set *uset,
460 __isl_take isl_union_set *context)
462 return isl_union_map_gist(uset, context);
465 static int intersect_domain_entry(void **entry, void *user)
467 struct isl_union_map_gen_bin_data *data = user;
469 struct isl_hash_table_entry *entry2;
471 isl_map *map = *entry;
474 dim = isl_map_get_dim(map);
475 dim = isl_dim_domain(dim);
476 hash = isl_dim_get_hash(dim);
477 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
478 hash, &has_dim, dim, 0);
483 map = isl_map_copy(map);
484 map = isl_map_intersect_domain(map, isl_set_copy(entry2->data));
486 empty = isl_map_is_empty(map);
496 data->res = isl_union_map_add_map(data->res, map);
501 __isl_give isl_union_map *isl_union_map_intersect_domain(
502 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
504 return gen_bin_op(umap, uset, &intersect_domain_entry);
507 struct isl_union_map_bin_data {
508 isl_union_map *umap2;
511 int (*fn)(void **entry, void *user);
514 static int apply_range_entry(void **entry, void *user)
516 struct isl_union_map_bin_data *data = user;
517 isl_map *map2 = *entry;
520 if (!isl_dim_tuple_match(data->map->dim, isl_dim_out,
521 map2->dim, isl_dim_in))
524 map2 = isl_map_apply_range(isl_map_copy(data->map), isl_map_copy(map2));
526 empty = isl_map_is_empty(map2);
536 data->res = isl_union_map_add_map(data->res, map2);
541 static int bin_entry(void **entry, void *user)
543 struct isl_union_map_bin_data *data = user;
544 isl_map *map = *entry;
547 if (isl_hash_table_foreach(data->umap2->dim->ctx, &data->umap2->table,
554 static __isl_give isl_union_map *bin_op(__isl_take isl_union_map *umap1,
555 __isl_take isl_union_map *umap2, int (*fn)(void **entry, void *user))
557 struct isl_union_map_bin_data data = { umap2, NULL, NULL, fn };
559 if (!umap1 || !umap2)
562 data.res = isl_union_map_alloc(isl_dim_copy(umap1->dim),
564 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
565 &bin_entry, &data) < 0)
568 isl_union_map_free(umap1);
569 isl_union_map_free(umap2);
572 isl_union_map_free(umap1);
573 isl_union_map_free(umap2);
574 isl_union_map_free(data.res);
578 __isl_give isl_union_map *isl_union_map_apply_range(
579 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
581 return bin_op(umap1, umap2, &apply_range_entry);
584 __isl_give isl_union_set *isl_union_set_apply(
585 __isl_take isl_union_set *uset, __isl_take isl_union_map *umap)
587 return isl_union_map_apply_range(uset, umap);
590 static int product_entry(void **entry, void *user)
592 struct isl_union_map_bin_data *data = user;
593 isl_map *map2 = *entry;
595 map2 = isl_map_product(isl_map_copy(data->map), isl_map_copy(map2));
597 data->res = isl_union_map_add_map(data->res, map2);
602 __isl_give isl_union_map *isl_union_map_product(__isl_take isl_union_map *umap1,
603 __isl_take isl_union_map *umap2)
605 return bin_op(umap1, umap2, &product_entry);
608 __isl_give isl_union_set *isl_union_set_product(__isl_take isl_union_set *uset1,
609 __isl_take isl_union_set *uset2)
611 return isl_union_map_product(uset1, uset2);
614 __isl_give isl_union_map *isl_union_map_from_range(
615 __isl_take isl_union_set *uset)
620 __isl_give isl_union_map *isl_union_map_from_domain(
621 __isl_take isl_union_set *uset)
623 return isl_union_map_reverse(isl_union_map_from_range(uset));
626 __isl_give isl_union_map *isl_union_map_from_domain_and_range(
627 __isl_take isl_union_set *domain, __isl_take isl_union_set *range)
629 return isl_union_map_apply_range(isl_union_map_from_domain(domain),
630 isl_union_map_from_range(range));
633 static int reverse_entry(void **entry, void *user)
635 isl_map **map = (isl_map **)entry;
637 *map = isl_map_reverse(*map);
639 return *map ? 0 : -1;
642 static __isl_give isl_union_map *un_op(__isl_take isl_union_map *umap,
643 int (*fn)(void **, void *), int cow)
646 umap = isl_union_map_cow(umap);
650 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, NULL) < 0)
655 isl_union_map_free(umap);
659 __isl_give isl_union_map *isl_union_map_reverse(__isl_take isl_union_map *umap)
661 return un_op(umap, &reverse_entry, 1);
664 static int affine_entry(void **entry, void *user)
666 isl_map **map = (isl_map **)entry;
668 *map = isl_map_from_basic_map(isl_map_affine_hull(*map));
670 return *map ? 0 : -1;
673 __isl_give isl_union_map *isl_union_map_affine_hull(
674 __isl_take isl_union_map *umap)
676 return un_op(umap, &affine_entry, 1);
679 __isl_give isl_union_set *isl_union_set_affine_hull(
680 __isl_take isl_union_set *uset)
682 return isl_union_map_affine_hull(uset);
685 static int coalesce_entry(void **entry, void *user)
687 isl_map **map = (isl_map **)entry;
689 *map = isl_map_coalesce(*map);
691 return *map ? 0 : -1;
694 __isl_give isl_union_map *isl_union_map_coalesce(
695 __isl_take isl_union_map *umap)
697 return un_op(umap, &coalesce_entry, 0);
700 __isl_give isl_union_set *isl_union_set_coalesce(
701 __isl_take isl_union_set *uset)
703 return isl_union_map_coalesce(uset);
706 static int compute_divs_entry(void **entry, void *user)
708 isl_map **map = (isl_map **)entry;
710 *map = isl_map_compute_divs(*map);
712 return *map ? 0 : -1;
715 __isl_give isl_union_map *isl_union_map_compute_divs(
716 __isl_take isl_union_map *umap)
718 return un_op(umap, &compute_divs_entry, 0);
721 __isl_give isl_union_set *isl_union_set_compute_divs(
722 __isl_take isl_union_set *uset)
724 return isl_union_map_compute_divs(uset);
727 static int lexmin_entry(void **entry, void *user)
729 isl_map **map = (isl_map **)entry;
731 *map = isl_map_lexmin(*map);
733 return *map ? 0 : -1;
736 __isl_give isl_union_map *isl_union_map_lexmin(
737 __isl_take isl_union_map *umap)
739 return un_op(umap, &lexmin_entry, 1);
742 __isl_give isl_union_set *isl_union_set_lexmin(
743 __isl_take isl_union_set *uset)
745 return isl_union_map_lexmin(uset);
748 static int lexmax_entry(void **entry, void *user)
750 isl_map **map = (isl_map **)entry;
752 *map = isl_map_lexmax(*map);
754 return *map ? 0 : -1;
757 __isl_give isl_union_map *isl_union_map_lexmax(
758 __isl_take isl_union_map *umap)
760 return un_op(umap, &lexmax_entry, 1);
763 __isl_give isl_union_set *isl_union_set_lexmax(
764 __isl_take isl_union_set *uset)
766 return isl_union_map_lexmax(uset);
769 static int domain_entry(void **entry, void *user)
771 *entry = isl_map_domain(*entry);
773 return *entry ? 0 : -1;
776 __isl_give isl_union_set *isl_union_map_domain(__isl_take isl_union_map *umap)
778 return un_op(umap, &domain_entry, 1);
781 static int range_entry(void **entry, void *user)
783 *entry = isl_map_range(*entry);
785 return *entry ? 0 : -1;
788 __isl_give isl_union_set *isl_union_map_range(__isl_take isl_union_map *umap)
790 return un_op(umap, &range_entry, 1);
793 static __isl_give isl_union_set *cond_un_op(__isl_take isl_union_map *umap,
794 int (*fn)(void **, void *))
801 res = isl_union_map_alloc(isl_dim_copy(umap->dim), umap->table.n);
802 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, &res) < 0)
805 isl_union_map_free(umap);
808 isl_union_map_free(umap);
809 isl_union_set_free(res);
813 static int deltas_entry(void **entry, void *user)
815 isl_map *map = *entry;
816 isl_union_set **res = user;
818 if (!isl_dim_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
821 *res = isl_union_set_add_set(*res, isl_map_deltas(isl_map_copy(map)));
826 __isl_give isl_union_set *isl_union_map_deltas(__isl_take isl_union_map *umap)
828 return cond_un_op(umap, &deltas_entry);
831 static int unwrap_entry(void **entry, void *user)
833 isl_set *set = *entry;
834 isl_union_set **res = user;
836 if (!isl_set_is_wrapping(set))
839 *res = isl_union_map_add_map(*res, isl_set_unwrap(isl_set_copy(set)));
844 __isl_give isl_union_map *isl_union_set_unwrap(__isl_take isl_union_set *uset)
846 return cond_un_op(uset, &unwrap_entry);
849 static int wrap_entry(void **entry, void *user)
851 isl_map **map = (isl_map **)entry;
853 *map = (isl_map *)isl_map_wrap(*map);
855 return *map ? 0 : -1;
858 __isl_give isl_union_set *isl_union_map_wrap(__isl_take isl_union_map *umap)
860 return un_op(umap, &wrap_entry, 1);
863 struct isl_union_map_is_subset_data {
864 isl_union_map *umap2;
868 static int is_subset_entry(void **entry, void *user)
870 struct isl_union_map_is_subset_data *data = user;
872 struct isl_hash_table_entry *entry2;
873 isl_map *map = *entry;
875 hash = isl_dim_get_hash(map->dim);
876 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
877 hash, &has_dim, map->dim, 0);
883 data->is_subset = isl_map_is_subset(map, entry2->data);
884 if (data->is_subset < 0 || !data->is_subset)
890 int isl_union_map_is_subset(__isl_keep isl_union_map *umap1,
891 __isl_keep isl_union_map *umap2)
893 struct isl_union_map_is_subset_data data = { umap2, 1 };
895 if (!umap1 || !umap2)
898 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
899 &is_subset_entry, &data) < 0 &&
903 return data.is_subset;
906 int isl_union_map_is_equal(__isl_keep isl_union_map *umap1,
907 __isl_keep isl_union_map *umap2)
911 if (!umap1 || !umap2)
913 is_subset = isl_union_map_is_subset(umap1, umap2);
916 is_subset = isl_union_map_is_subset(umap2, umap1);
920 int isl_union_map_is_strict_subset(__isl_keep isl_union_map *umap1,
921 __isl_keep isl_union_map *umap2)
925 if (!umap1 || !umap2)
927 is_subset = isl_union_map_is_subset(umap1, umap2);
930 is_subset = isl_union_map_is_subset(umap2, umap1);
936 static int sample_entry(void **entry, void *user)
938 isl_basic_map **sample = (isl_basic_map **)user;
939 isl_map *map = *entry;
941 *sample = isl_map_sample(isl_map_copy(map));
944 if (!isl_basic_map_fast_is_empty(*sample))
949 __isl_give isl_basic_map *isl_union_map_sample(__isl_take isl_union_map *umap)
951 isl_basic_map *sample = NULL;
956 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
957 &sample_entry, &sample) < 0 &&
961 isl_union_map_free(umap);
965 isl_union_map_free(umap);
969 __isl_give isl_basic_set *isl_union_set_sample(__isl_take isl_union_set *uset)
971 return (isl_basic_set *)isl_union_map_sample(uset);
974 static int empty_entry(void **entry, void *user)
977 isl_map *map = *entry;
979 if (isl_map_is_empty(map))
987 __isl_give int isl_union_map_is_empty(__isl_keep isl_union_map *umap)
994 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
995 &sample_entry, &empty) < 0 && empty)
1001 int isl_union_set_is_empty(__isl_keep isl_union_set *uset)
1003 return isl_union_map_is_empty(uset);