2 * Copyright 2010-2011 INRIA Saclay
4 * Use of this software is governed by the MIT license
6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
12 #include <isl_map_private.h>
17 #include <isl_space_private.h>
18 #include <isl_union_map_private.h>
19 #include <isl/union_set.h>
21 /* Is this union set a parameter domain?
23 int isl_union_set_is_params(__isl_keep isl_union_set *uset)
30 if (uset->table.n != 1)
33 set = isl_set_from_union_set(isl_union_set_copy(uset));
34 params = isl_set_is_params(set);
39 static __isl_give isl_union_map *isl_union_map_alloc(__isl_take isl_space *dim,
44 dim = isl_space_params(dim);
48 umap = isl_calloc_type(dim->ctx, isl_union_map);
54 if (isl_hash_table_init(dim->ctx, &umap->table, size) < 0)
60 isl_union_map_free(umap);
64 __isl_give isl_union_map *isl_union_map_empty(__isl_take isl_space *dim)
66 return isl_union_map_alloc(dim, 16);
69 __isl_give isl_union_set *isl_union_set_empty(__isl_take isl_space *dim)
71 return isl_union_map_empty(dim);
74 isl_ctx *isl_union_map_get_ctx(__isl_keep isl_union_map *umap)
76 return umap ? umap->dim->ctx : NULL;
79 isl_ctx *isl_union_set_get_ctx(__isl_keep isl_union_set *uset)
81 return uset ? uset->dim->ctx : NULL;
84 __isl_give isl_space *isl_union_map_get_space(__isl_keep isl_union_map *umap)
88 return isl_space_copy(umap->dim);
91 __isl_give isl_space *isl_union_set_get_space(__isl_keep isl_union_set *uset)
93 return isl_union_map_get_space(uset);
96 static int free_umap_entry(void **entry, void *user)
98 isl_map *map = *entry;
103 static int add_map(__isl_take isl_map *map, void *user)
105 isl_union_map **umap = (isl_union_map **)user;
107 *umap = isl_union_map_add_map(*umap, map);
112 __isl_give isl_union_map *isl_union_map_dup(__isl_keep isl_union_map *umap)
119 dup = isl_union_map_empty(isl_space_copy(umap->dim));
120 if (isl_union_map_foreach_map(umap, &add_map, &dup) < 0)
124 isl_union_map_free(dup);
128 __isl_give isl_union_map *isl_union_map_cow(__isl_take isl_union_map *umap)
136 return isl_union_map_dup(umap);
139 struct isl_union_align {
144 static int align_entry(void **entry, void *user)
146 isl_map *map = *entry;
148 struct isl_union_align *data = user;
150 exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
151 isl_map_get_space(map));
153 data->res = isl_union_map_add_map(data->res,
154 isl_map_realign(isl_map_copy(map), exp));
159 /* Align the parameters of umap along those of model.
160 * The result has the parameters of model first, in the same order
161 * as they appear in model, followed by any remaining parameters of
162 * umap that do not appear in model.
164 __isl_give isl_union_map *isl_union_map_align_params(
165 __isl_take isl_union_map *umap, __isl_take isl_space *model)
167 struct isl_union_align data = { NULL, NULL };
172 if (isl_space_match(umap->dim, isl_dim_param, model, isl_dim_param)) {
173 isl_space_free(model);
177 model = isl_space_params(model);
178 data.exp = isl_parameter_alignment_reordering(umap->dim, model);
182 data.res = isl_union_map_alloc(isl_space_copy(data.exp->dim),
184 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
185 &align_entry, &data) < 0)
188 isl_reordering_free(data.exp);
189 isl_union_map_free(umap);
190 isl_space_free(model);
193 isl_reordering_free(data.exp);
194 isl_union_map_free(umap);
195 isl_union_map_free(data.res);
196 isl_space_free(model);
200 __isl_give isl_union_set *isl_union_set_align_params(
201 __isl_take isl_union_set *uset, __isl_take isl_space *model)
203 return isl_union_map_align_params(uset, model);
206 __isl_give isl_union_map *isl_union_map_union(__isl_take isl_union_map *umap1,
207 __isl_take isl_union_map *umap2)
209 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
210 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
212 umap1 = isl_union_map_cow(umap1);
214 if (!umap1 || !umap2)
217 if (isl_union_map_foreach_map(umap2, &add_map, &umap1) < 0)
220 isl_union_map_free(umap2);
224 isl_union_map_free(umap1);
225 isl_union_map_free(umap2);
229 __isl_give isl_union_set *isl_union_set_union(__isl_take isl_union_set *uset1,
230 __isl_take isl_union_set *uset2)
232 return isl_union_map_union(uset1, uset2);
235 __isl_give isl_union_map *isl_union_map_copy(__isl_keep isl_union_map *umap)
244 __isl_give isl_union_set *isl_union_set_copy(__isl_keep isl_union_set *uset)
246 return isl_union_map_copy(uset);
249 void *isl_union_map_free(__isl_take isl_union_map *umap)
257 isl_hash_table_foreach(umap->dim->ctx, &umap->table,
258 &free_umap_entry, NULL);
259 isl_hash_table_clear(&umap->table);
260 isl_space_free(umap->dim);
265 void *isl_union_set_free(__isl_take isl_union_set *uset)
267 return isl_union_map_free(uset);
270 static int has_dim(const void *entry, const void *val)
272 isl_map *map = (isl_map *)entry;
273 isl_space *dim = (isl_space *)val;
275 return isl_space_is_equal(map->dim, dim);
278 __isl_give isl_union_map *isl_union_map_add_map(__isl_take isl_union_map *umap,
279 __isl_take isl_map *map)
282 struct isl_hash_table_entry *entry;
287 if (isl_map_plain_is_empty(map)) {
292 if (!isl_space_match(map->dim, isl_dim_param, umap->dim, isl_dim_param)) {
293 umap = isl_union_map_align_params(umap, isl_map_get_space(map));
294 map = isl_map_align_params(map, isl_union_map_get_space(umap));
297 umap = isl_union_map_cow(umap);
302 hash = isl_space_get_hash(map->dim);
303 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
304 &has_dim, map->dim, 1);
311 entry->data = isl_map_union(entry->data, isl_map_copy(map));
320 isl_union_map_free(umap);
324 __isl_give isl_union_set *isl_union_set_add_set(__isl_take isl_union_set *uset,
325 __isl_take isl_set *set)
327 return isl_union_map_add_map(uset, (isl_map *)set);
330 __isl_give isl_union_map *isl_union_map_from_map(__isl_take isl_map *map)
338 dim = isl_map_get_space(map);
339 dim = isl_space_params(dim);
340 umap = isl_union_map_empty(dim);
341 umap = isl_union_map_add_map(umap, map);
346 __isl_give isl_union_set *isl_union_set_from_set(__isl_take isl_set *set)
348 return isl_union_map_from_map((isl_map *)set);
351 __isl_give isl_union_map *isl_union_map_from_basic_map(
352 __isl_take isl_basic_map *bmap)
354 return isl_union_map_from_map(isl_map_from_basic_map(bmap));
357 __isl_give isl_union_set *isl_union_set_from_basic_set(
358 __isl_take isl_basic_set *bset)
360 return isl_union_map_from_basic_map(bset);
363 struct isl_union_map_foreach_data
365 int (*fn)(__isl_take isl_map *map, void *user);
369 static int call_on_copy(void **entry, void *user)
371 isl_map *map = *entry;
372 struct isl_union_map_foreach_data *data;
373 data = (struct isl_union_map_foreach_data *)user;
375 return data->fn(isl_map_copy(map), data->user);
378 int isl_union_map_n_map(__isl_keep isl_union_map *umap)
380 return umap ? umap->table.n : 0;
383 int isl_union_set_n_set(__isl_keep isl_union_set *uset)
385 return uset ? uset->table.n : 0;
388 int isl_union_map_foreach_map(__isl_keep isl_union_map *umap,
389 int (*fn)(__isl_take isl_map *map, void *user), void *user)
391 struct isl_union_map_foreach_data data = { fn, user };
396 return isl_hash_table_foreach(umap->dim->ctx, &umap->table,
397 &call_on_copy, &data);
400 static int copy_map(void **entry, void *user)
402 isl_map *map = *entry;
403 isl_map **map_p = user;
405 *map_p = isl_map_copy(map);
410 __isl_give isl_map *isl_map_from_union_map(__isl_take isl_union_map *umap)
417 ctx = isl_union_map_get_ctx(umap);
418 if (umap->table.n != 1)
419 isl_die(ctx, isl_error_invalid,
420 "union map needs to contain elements in exactly "
421 "one space", return isl_union_map_free(umap));
423 isl_hash_table_foreach(ctx, &umap->table, ©_map, &map);
425 isl_union_map_free(umap);
430 __isl_give isl_set *isl_set_from_union_set(__isl_take isl_union_set *uset)
432 return isl_map_from_union_map(uset);
435 /* Extract the map in "umap" that lives in the given space (ignoring
438 __isl_give isl_map *isl_union_map_extract_map(__isl_keep isl_union_map *umap,
439 __isl_take isl_space *space)
442 struct isl_hash_table_entry *entry;
444 space = isl_space_drop_dims(space, isl_dim_param,
445 0, isl_space_dim(space, isl_dim_param));
446 space = isl_space_align_params(space, isl_union_map_get_space(umap));
450 hash = isl_space_get_hash(space);
451 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
454 return isl_map_empty(space);
455 isl_space_free(space);
456 return isl_map_copy(entry->data);
458 isl_space_free(space);
462 __isl_give isl_set *isl_union_set_extract_set(__isl_keep isl_union_set *uset,
463 __isl_take isl_space *dim)
465 return (isl_set *)isl_union_map_extract_map(uset, dim);
468 /* Check if umap contains a map in the given space.
470 __isl_give int isl_union_map_contains(__isl_keep isl_union_map *umap,
471 __isl_keep isl_space *dim)
474 struct isl_hash_table_entry *entry;
479 hash = isl_space_get_hash(dim);
480 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
485 __isl_give int isl_union_set_contains(__isl_keep isl_union_set *uset,
486 __isl_keep isl_space *dim)
488 return isl_union_map_contains(uset, dim);
491 int isl_union_set_foreach_set(__isl_keep isl_union_set *uset,
492 int (*fn)(__isl_take isl_set *set, void *user), void *user)
494 return isl_union_map_foreach_map(uset,
495 (int(*)(__isl_take isl_map *, void*))fn, user);
498 struct isl_union_set_foreach_point_data {
499 int (*fn)(__isl_take isl_point *pnt, void *user);
503 static int foreach_point(__isl_take isl_set *set, void *user)
505 struct isl_union_set_foreach_point_data *data = user;
508 r = isl_set_foreach_point(set, data->fn, data->user);
514 int isl_union_set_foreach_point(__isl_keep isl_union_set *uset,
515 int (*fn)(__isl_take isl_point *pnt, void *user), void *user)
517 struct isl_union_set_foreach_point_data data = { fn, user };
518 return isl_union_set_foreach_set(uset, &foreach_point, &data);
521 struct isl_union_map_gen_bin_data {
522 isl_union_map *umap2;
526 static int subtract_entry(void **entry, void *user)
528 struct isl_union_map_gen_bin_data *data = user;
530 struct isl_hash_table_entry *entry2;
531 isl_map *map = *entry;
533 hash = isl_space_get_hash(map->dim);
534 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
535 hash, &has_dim, map->dim, 0);
536 map = isl_map_copy(map);
539 map = isl_map_subtract(map, isl_map_copy(entry2->data));
541 empty = isl_map_is_empty(map);
551 data->res = isl_union_map_add_map(data->res, map);
556 static __isl_give isl_union_map *gen_bin_op(__isl_take isl_union_map *umap1,
557 __isl_take isl_union_map *umap2, int (*fn)(void **, void *))
559 struct isl_union_map_gen_bin_data data = { NULL, NULL };
561 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
562 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
564 if (!umap1 || !umap2)
568 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
570 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
574 isl_union_map_free(umap1);
575 isl_union_map_free(umap2);
578 isl_union_map_free(umap1);
579 isl_union_map_free(umap2);
580 isl_union_map_free(data.res);
584 __isl_give isl_union_map *isl_union_map_subtract(
585 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
587 return gen_bin_op(umap1, umap2, &subtract_entry);
590 __isl_give isl_union_set *isl_union_set_subtract(
591 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
593 return isl_union_map_subtract(uset1, uset2);
596 struct isl_union_map_gen_bin_set_data {
601 static int intersect_params_entry(void **entry, void *user)
603 struct isl_union_map_gen_bin_set_data *data = user;
604 isl_map *map = *entry;
607 map = isl_map_copy(map);
608 map = isl_map_intersect_params(map, isl_set_copy(data->set));
610 empty = isl_map_is_empty(map);
616 data->res = isl_union_map_add_map(data->res, map);
621 static __isl_give isl_union_map *gen_bin_set_op(__isl_take isl_union_map *umap,
622 __isl_take isl_set *set, int (*fn)(void **, void *))
624 struct isl_union_map_gen_bin_set_data data = { NULL, NULL };
626 umap = isl_union_map_align_params(umap, isl_set_get_space(set));
627 set = isl_set_align_params(set, isl_union_map_get_space(umap));
633 data.res = isl_union_map_alloc(isl_space_copy(umap->dim),
635 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
639 isl_union_map_free(umap);
643 isl_union_map_free(umap);
645 isl_union_map_free(data.res);
649 __isl_give isl_union_map *isl_union_map_intersect_params(
650 __isl_take isl_union_map *umap, __isl_take isl_set *set)
652 return gen_bin_set_op(umap, set, &intersect_params_entry);
655 __isl_give isl_union_set *isl_union_set_intersect_params(
656 __isl_take isl_union_set *uset, __isl_take isl_set *set)
658 return isl_union_map_intersect_params(uset, set);
661 static __isl_give isl_union_map *union_map_intersect_params(
662 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
664 return isl_union_map_intersect_params(umap,
665 isl_set_from_union_set(uset));
668 static __isl_give isl_union_map *union_map_gist_params(
669 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
671 return isl_union_map_gist_params(umap, isl_set_from_union_set(uset));
674 struct isl_union_map_match_bin_data {
675 isl_union_map *umap2;
677 __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*);
680 static int match_bin_entry(void **entry, void *user)
682 struct isl_union_map_match_bin_data *data = user;
684 struct isl_hash_table_entry *entry2;
685 isl_map *map = *entry;
688 hash = isl_space_get_hash(map->dim);
689 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
690 hash, &has_dim, map->dim, 0);
694 map = isl_map_copy(map);
695 map = data->fn(map, isl_map_copy(entry2->data));
697 empty = isl_map_is_empty(map);
707 data->res = isl_union_map_add_map(data->res, map);
712 static __isl_give isl_union_map *match_bin_op(__isl_take isl_union_map *umap1,
713 __isl_take isl_union_map *umap2,
714 __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*))
716 struct isl_union_map_match_bin_data data = { NULL, NULL, fn };
718 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
719 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
721 if (!umap1 || !umap2)
725 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
727 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
728 &match_bin_entry, &data) < 0)
731 isl_union_map_free(umap1);
732 isl_union_map_free(umap2);
735 isl_union_map_free(umap1);
736 isl_union_map_free(umap2);
737 isl_union_map_free(data.res);
741 __isl_give isl_union_map *isl_union_map_intersect(
742 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
744 return match_bin_op(umap1, umap2, &isl_map_intersect);
747 /* Compute the intersection of the two union_sets.
748 * As a special case, if exactly one of the two union_sets
749 * is a parameter domain, then intersect the parameter domain
750 * of the other one with this set.
752 __isl_give isl_union_set *isl_union_set_intersect(
753 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
757 p1 = isl_union_set_is_params(uset1);
758 p2 = isl_union_set_is_params(uset2);
759 if (p1 < 0 || p2 < 0)
762 return union_map_intersect_params(uset1, uset2);
764 return union_map_intersect_params(uset2, uset1);
765 return isl_union_map_intersect(uset1, uset2);
767 isl_union_set_free(uset1);
768 isl_union_set_free(uset2);
772 static int gist_params_entry(void **entry, void *user)
774 struct isl_union_map_gen_bin_set_data *data = user;
775 isl_map *map = *entry;
778 map = isl_map_copy(map);
779 map = isl_map_gist_params(map, isl_set_copy(data->set));
781 empty = isl_map_is_empty(map);
787 data->res = isl_union_map_add_map(data->res, map);
792 __isl_give isl_union_map *isl_union_map_gist_params(
793 __isl_take isl_union_map *umap, __isl_take isl_set *set)
795 return gen_bin_set_op(umap, set, &gist_params_entry);
798 __isl_give isl_union_set *isl_union_set_gist_params(
799 __isl_take isl_union_set *uset, __isl_take isl_set *set)
801 return isl_union_map_gist_params(uset, set);
804 __isl_give isl_union_map *isl_union_map_gist(__isl_take isl_union_map *umap,
805 __isl_take isl_union_map *context)
807 return match_bin_op(umap, context, &isl_map_gist);
810 __isl_give isl_union_set *isl_union_set_gist(__isl_take isl_union_set *uset,
811 __isl_take isl_union_set *context)
813 if (isl_union_set_is_params(context))
814 return union_map_gist_params(uset, context);
815 return isl_union_map_gist(uset, context);
818 static __isl_give isl_map *lex_le_set(__isl_take isl_map *set1,
819 __isl_take isl_map *set2)
821 return isl_set_lex_le_set((isl_set *)set1, (isl_set *)set2);
824 static __isl_give isl_map *lex_lt_set(__isl_take isl_map *set1,
825 __isl_take isl_map *set2)
827 return isl_set_lex_lt_set((isl_set *)set1, (isl_set *)set2);
830 __isl_give isl_union_map *isl_union_set_lex_lt_union_set(
831 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
833 return match_bin_op(uset1, uset2, &lex_lt_set);
836 __isl_give isl_union_map *isl_union_set_lex_le_union_set(
837 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
839 return match_bin_op(uset1, uset2, &lex_le_set);
842 __isl_give isl_union_map *isl_union_set_lex_gt_union_set(
843 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
845 return isl_union_map_reverse(isl_union_set_lex_lt_union_set(uset2, uset1));
848 __isl_give isl_union_map *isl_union_set_lex_ge_union_set(
849 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
851 return isl_union_map_reverse(isl_union_set_lex_le_union_set(uset2, uset1));
854 __isl_give isl_union_map *isl_union_map_lex_gt_union_map(
855 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
857 return isl_union_map_reverse(isl_union_map_lex_lt_union_map(umap2, umap1));
860 __isl_give isl_union_map *isl_union_map_lex_ge_union_map(
861 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
863 return isl_union_map_reverse(isl_union_map_lex_le_union_map(umap2, umap1));
866 static int intersect_domain_entry(void **entry, void *user)
868 struct isl_union_map_gen_bin_data *data = user;
870 struct isl_hash_table_entry *entry2;
872 isl_map *map = *entry;
875 dim = isl_map_get_space(map);
876 dim = isl_space_domain(dim);
877 hash = isl_space_get_hash(dim);
878 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
879 hash, &has_dim, dim, 0);
884 map = isl_map_copy(map);
885 map = isl_map_intersect_domain(map, isl_set_copy(entry2->data));
887 empty = isl_map_is_empty(map);
897 data->res = isl_union_map_add_map(data->res, map);
902 /* Intersect the domain of "umap" with "uset".
903 * If "uset" is a parameters domain, then intersect the parameter
904 * domain of "umap" with this set.
906 __isl_give isl_union_map *isl_union_map_intersect_domain(
907 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
909 if (isl_union_set_is_params(uset))
910 return union_map_intersect_params(umap, uset);
911 return gen_bin_op(umap, uset, &intersect_domain_entry);
914 /* Remove the elements of data->umap2 from the domain of *entry
915 * and add the result to data->res.
917 static int subtract_domain_entry(void **entry, void *user)
919 struct isl_union_map_gen_bin_data *data = user;
921 struct isl_hash_table_entry *entry2;
923 isl_map *map = *entry;
926 dim = isl_map_get_space(map);
927 dim = isl_space_domain(dim);
928 hash = isl_space_get_hash(dim);
929 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
930 hash, &has_dim, dim, 0);
933 map = isl_map_copy(map);
936 data->res = isl_union_map_add_map(data->res, map);
940 map = isl_map_subtract_domain(map, isl_set_copy(entry2->data));
942 empty = isl_map_is_empty(map);
952 data->res = isl_union_map_add_map(data->res, map);
957 /* Remove the elements of "uset" from the domain of "umap".
959 __isl_give isl_union_map *isl_union_map_subtract_domain(
960 __isl_take isl_union_map *umap, __isl_take isl_union_set *dom)
962 return gen_bin_op(umap, dom, &subtract_domain_entry);
965 /* Remove the elements of data->umap2 from the range of *entry
966 * and add the result to data->res.
968 static int subtract_range_entry(void **entry, void *user)
970 struct isl_union_map_gen_bin_data *data = user;
972 struct isl_hash_table_entry *entry2;
974 isl_map *map = *entry;
977 space = isl_map_get_space(map);
978 space = isl_space_range(space);
979 hash = isl_space_get_hash(space);
980 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
981 hash, &has_dim, space, 0);
982 isl_space_free(space);
984 map = isl_map_copy(map);
987 data->res = isl_union_map_add_map(data->res, map);
991 map = isl_map_subtract_range(map, isl_set_copy(entry2->data));
993 empty = isl_map_is_empty(map);
1003 data->res = isl_union_map_add_map(data->res, map);
1008 /* Remove the elements of "uset" from the range of "umap".
1010 __isl_give isl_union_map *isl_union_map_subtract_range(
1011 __isl_take isl_union_map *umap, __isl_take isl_union_set *dom)
1013 return gen_bin_op(umap, dom, &subtract_range_entry);
1016 static int gist_domain_entry(void **entry, void *user)
1018 struct isl_union_map_gen_bin_data *data = user;
1020 struct isl_hash_table_entry *entry2;
1022 isl_map *map = *entry;
1025 dim = isl_map_get_space(map);
1026 dim = isl_space_domain(dim);
1027 hash = isl_space_get_hash(dim);
1028 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1029 hash, &has_dim, dim, 0);
1030 isl_space_free(dim);
1034 map = isl_map_copy(map);
1035 map = isl_map_gist_domain(map, isl_set_copy(entry2->data));
1037 empty = isl_map_is_empty(map);
1043 data->res = isl_union_map_add_map(data->res, map);
1048 /* Compute the gist of "umap" with respect to the domain "uset".
1049 * If "uset" is a parameters domain, then compute the gist
1050 * with respect to this parameter domain.
1052 __isl_give isl_union_map *isl_union_map_gist_domain(
1053 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1055 if (isl_union_set_is_params(uset))
1056 return union_map_gist_params(umap, uset);
1057 return gen_bin_op(umap, uset, &gist_domain_entry);
1060 static int gist_range_entry(void **entry, void *user)
1062 struct isl_union_map_gen_bin_data *data = user;
1064 struct isl_hash_table_entry *entry2;
1066 isl_map *map = *entry;
1069 space = isl_map_get_space(map);
1070 space = isl_space_range(space);
1071 hash = isl_space_get_hash(space);
1072 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1073 hash, &has_dim, space, 0);
1074 isl_space_free(space);
1078 map = isl_map_copy(map);
1079 map = isl_map_gist_range(map, isl_set_copy(entry2->data));
1081 empty = isl_map_is_empty(map);
1087 data->res = isl_union_map_add_map(data->res, map);
1092 /* Compute the gist of "umap" with respect to the range "uset".
1094 __isl_give isl_union_map *isl_union_map_gist_range(
1095 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1097 return gen_bin_op(umap, uset, &gist_range_entry);
1100 static int intersect_range_entry(void **entry, void *user)
1102 struct isl_union_map_gen_bin_data *data = user;
1104 struct isl_hash_table_entry *entry2;
1106 isl_map *map = *entry;
1109 dim = isl_map_get_space(map);
1110 dim = isl_space_range(dim);
1111 hash = isl_space_get_hash(dim);
1112 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1113 hash, &has_dim, dim, 0);
1114 isl_space_free(dim);
1118 map = isl_map_copy(map);
1119 map = isl_map_intersect_range(map, isl_set_copy(entry2->data));
1121 empty = isl_map_is_empty(map);
1131 data->res = isl_union_map_add_map(data->res, map);
1136 __isl_give isl_union_map *isl_union_map_intersect_range(
1137 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1139 return gen_bin_op(umap, uset, &intersect_range_entry);
1142 struct isl_union_map_bin_data {
1143 isl_union_map *umap2;
1146 int (*fn)(void **entry, void *user);
1149 static int apply_range_entry(void **entry, void *user)
1151 struct isl_union_map_bin_data *data = user;
1152 isl_map *map2 = *entry;
1155 if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1156 map2->dim, isl_dim_in))
1159 map2 = isl_map_apply_range(isl_map_copy(data->map), isl_map_copy(map2));
1161 empty = isl_map_is_empty(map2);
1171 data->res = isl_union_map_add_map(data->res, map2);
1176 static int bin_entry(void **entry, void *user)
1178 struct isl_union_map_bin_data *data = user;
1179 isl_map *map = *entry;
1182 if (isl_hash_table_foreach(data->umap2->dim->ctx, &data->umap2->table,
1183 data->fn, data) < 0)
1189 static __isl_give isl_union_map *bin_op(__isl_take isl_union_map *umap1,
1190 __isl_take isl_union_map *umap2, int (*fn)(void **entry, void *user))
1192 struct isl_union_map_bin_data data = { NULL, NULL, NULL, fn };
1194 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
1195 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
1197 if (!umap1 || !umap2)
1201 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
1203 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1204 &bin_entry, &data) < 0)
1207 isl_union_map_free(umap1);
1208 isl_union_map_free(umap2);
1211 isl_union_map_free(umap1);
1212 isl_union_map_free(umap2);
1213 isl_union_map_free(data.res);
1217 __isl_give isl_union_map *isl_union_map_apply_range(
1218 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1220 return bin_op(umap1, umap2, &apply_range_entry);
1223 __isl_give isl_union_map *isl_union_map_apply_domain(
1224 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1226 umap1 = isl_union_map_reverse(umap1);
1227 umap1 = isl_union_map_apply_range(umap1, umap2);
1228 return isl_union_map_reverse(umap1);
1231 __isl_give isl_union_set *isl_union_set_apply(
1232 __isl_take isl_union_set *uset, __isl_take isl_union_map *umap)
1234 return isl_union_map_apply_range(uset, umap);
1237 static int map_lex_lt_entry(void **entry, void *user)
1239 struct isl_union_map_bin_data *data = user;
1240 isl_map *map2 = *entry;
1242 if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1243 map2->dim, isl_dim_out))
1246 map2 = isl_map_lex_lt_map(isl_map_copy(data->map), isl_map_copy(map2));
1248 data->res = isl_union_map_add_map(data->res, map2);
1253 __isl_give isl_union_map *isl_union_map_lex_lt_union_map(
1254 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1256 return bin_op(umap1, umap2, &map_lex_lt_entry);
1259 static int map_lex_le_entry(void **entry, void *user)
1261 struct isl_union_map_bin_data *data = user;
1262 isl_map *map2 = *entry;
1264 if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1265 map2->dim, isl_dim_out))
1268 map2 = isl_map_lex_le_map(isl_map_copy(data->map), isl_map_copy(map2));
1270 data->res = isl_union_map_add_map(data->res, map2);
1275 __isl_give isl_union_map *isl_union_map_lex_le_union_map(
1276 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1278 return bin_op(umap1, umap2, &map_lex_le_entry);
1281 static int product_entry(void **entry, void *user)
1283 struct isl_union_map_bin_data *data = user;
1284 isl_map *map2 = *entry;
1286 map2 = isl_map_product(isl_map_copy(data->map), isl_map_copy(map2));
1288 data->res = isl_union_map_add_map(data->res, map2);
1293 __isl_give isl_union_map *isl_union_map_product(__isl_take isl_union_map *umap1,
1294 __isl_take isl_union_map *umap2)
1296 return bin_op(umap1, umap2, &product_entry);
1299 static int set_product_entry(void **entry, void *user)
1301 struct isl_union_map_bin_data *data = user;
1302 isl_set *set2 = *entry;
1304 set2 = isl_set_product(isl_set_copy(data->map), isl_set_copy(set2));
1306 data->res = isl_union_set_add_set(data->res, set2);
1311 __isl_give isl_union_set *isl_union_set_product(__isl_take isl_union_set *uset1,
1312 __isl_take isl_union_set *uset2)
1314 return bin_op(uset1, uset2, &set_product_entry);
1317 static int domain_product_entry(void **entry, void *user)
1319 struct isl_union_map_bin_data *data = user;
1320 isl_map *map2 = *entry;
1322 if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1323 map2->dim, isl_dim_out))
1326 map2 = isl_map_domain_product(isl_map_copy(data->map),
1327 isl_map_copy(map2));
1329 data->res = isl_union_map_add_map(data->res, map2);
1334 /* Given two maps A -> B and C -> D, construct a map [A -> C] -> (B * D)
1336 __isl_give isl_union_map *isl_union_map_domain_product(
1337 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1339 return bin_op(umap1, umap2, &domain_product_entry);
1342 static int range_product_entry(void **entry, void *user)
1344 struct isl_union_map_bin_data *data = user;
1345 isl_map *map2 = *entry;
1347 if (!isl_space_tuple_match(data->map->dim, isl_dim_in,
1348 map2->dim, isl_dim_in))
1351 map2 = isl_map_range_product(isl_map_copy(data->map),
1352 isl_map_copy(map2));
1354 data->res = isl_union_map_add_map(data->res, map2);
1359 __isl_give isl_union_map *isl_union_map_range_product(
1360 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1362 return bin_op(umap1, umap2, &range_product_entry);
1365 static int flat_range_product_entry(void **entry, void *user)
1367 struct isl_union_map_bin_data *data = user;
1368 isl_map *map2 = *entry;
1370 if (!isl_space_tuple_match(data->map->dim, isl_dim_in,
1371 map2->dim, isl_dim_in))
1374 map2 = isl_map_flat_range_product(isl_map_copy(data->map),
1375 isl_map_copy(map2));
1377 data->res = isl_union_map_add_map(data->res, map2);
1382 __isl_give isl_union_map *isl_union_map_flat_range_product(
1383 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1385 return bin_op(umap1, umap2, &flat_range_product_entry);
1388 static __isl_give isl_union_set *cond_un_op(__isl_take isl_union_map *umap,
1389 int (*fn)(void **, void *))
1396 res = isl_union_map_alloc(isl_space_copy(umap->dim), umap->table.n);
1397 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, &res) < 0)
1400 isl_union_map_free(umap);
1403 isl_union_map_free(umap);
1404 isl_union_set_free(res);
1408 static int from_range_entry(void **entry, void *user)
1410 isl_map *set = *entry;
1411 isl_union_set **res = user;
1413 *res = isl_union_map_add_map(*res,
1414 isl_map_from_range(isl_set_copy(set)));
1419 __isl_give isl_union_map *isl_union_map_from_range(
1420 __isl_take isl_union_set *uset)
1422 return cond_un_op(uset, &from_range_entry);
1425 __isl_give isl_union_map *isl_union_map_from_domain(
1426 __isl_take isl_union_set *uset)
1428 return isl_union_map_reverse(isl_union_map_from_range(uset));
1431 __isl_give isl_union_map *isl_union_map_from_domain_and_range(
1432 __isl_take isl_union_set *domain, __isl_take isl_union_set *range)
1434 return isl_union_map_apply_range(isl_union_map_from_domain(domain),
1435 isl_union_map_from_range(range));
1438 static __isl_give isl_union_map *un_op(__isl_take isl_union_map *umap,
1439 int (*fn)(void **, void *))
1441 umap = isl_union_map_cow(umap);
1445 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, NULL) < 0)
1450 isl_union_map_free(umap);
1454 static int affine_entry(void **entry, void *user)
1456 isl_map **map = (isl_map **)entry;
1458 *map = isl_map_from_basic_map(isl_map_affine_hull(*map));
1460 return *map ? 0 : -1;
1463 __isl_give isl_union_map *isl_union_map_affine_hull(
1464 __isl_take isl_union_map *umap)
1466 return un_op(umap, &affine_entry);
1469 __isl_give isl_union_set *isl_union_set_affine_hull(
1470 __isl_take isl_union_set *uset)
1472 return isl_union_map_affine_hull(uset);
1475 static int polyhedral_entry(void **entry, void *user)
1477 isl_map **map = (isl_map **)entry;
1479 *map = isl_map_from_basic_map(isl_map_polyhedral_hull(*map));
1481 return *map ? 0 : -1;
1484 __isl_give isl_union_map *isl_union_map_polyhedral_hull(
1485 __isl_take isl_union_map *umap)
1487 return un_op(umap, &polyhedral_entry);
1490 __isl_give isl_union_set *isl_union_set_polyhedral_hull(
1491 __isl_take isl_union_set *uset)
1493 return isl_union_map_polyhedral_hull(uset);
1496 static int simple_entry(void **entry, void *user)
1498 isl_map **map = (isl_map **)entry;
1500 *map = isl_map_from_basic_map(isl_map_simple_hull(*map));
1502 return *map ? 0 : -1;
1505 __isl_give isl_union_map *isl_union_map_simple_hull(
1506 __isl_take isl_union_map *umap)
1508 return un_op(umap, &simple_entry);
1511 __isl_give isl_union_set *isl_union_set_simple_hull(
1512 __isl_take isl_union_set *uset)
1514 return isl_union_map_simple_hull(uset);
1517 static int inplace_entry(void **entry, void *user)
1519 __isl_give isl_map *(*fn)(__isl_take isl_map *);
1520 isl_map **map = (isl_map **)entry;
1523 fn = *(__isl_give isl_map *(**)(__isl_take isl_map *)) user;
1524 copy = fn(isl_map_copy(*map));
1534 static __isl_give isl_union_map *inplace(__isl_take isl_union_map *umap,
1535 __isl_give isl_map *(*fn)(__isl_take isl_map *))
1540 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1541 &inplace_entry, &fn) < 0)
1546 isl_union_map_free(umap);
1550 __isl_give isl_union_map *isl_union_map_coalesce(
1551 __isl_take isl_union_map *umap)
1553 return inplace(umap, &isl_map_coalesce);
1556 __isl_give isl_union_set *isl_union_set_coalesce(
1557 __isl_take isl_union_set *uset)
1559 return isl_union_map_coalesce(uset);
1562 __isl_give isl_union_map *isl_union_map_detect_equalities(
1563 __isl_take isl_union_map *umap)
1565 return inplace(umap, &isl_map_detect_equalities);
1568 __isl_give isl_union_set *isl_union_set_detect_equalities(
1569 __isl_take isl_union_set *uset)
1571 return isl_union_map_detect_equalities(uset);
1574 __isl_give isl_union_map *isl_union_map_compute_divs(
1575 __isl_take isl_union_map *umap)
1577 return inplace(umap, &isl_map_compute_divs);
1580 __isl_give isl_union_set *isl_union_set_compute_divs(
1581 __isl_take isl_union_set *uset)
1583 return isl_union_map_compute_divs(uset);
1586 static int lexmin_entry(void **entry, void *user)
1588 isl_map **map = (isl_map **)entry;
1590 *map = isl_map_lexmin(*map);
1592 return *map ? 0 : -1;
1595 __isl_give isl_union_map *isl_union_map_lexmin(
1596 __isl_take isl_union_map *umap)
1598 return un_op(umap, &lexmin_entry);
1601 __isl_give isl_union_set *isl_union_set_lexmin(
1602 __isl_take isl_union_set *uset)
1604 return isl_union_map_lexmin(uset);
1607 static int lexmax_entry(void **entry, void *user)
1609 isl_map **map = (isl_map **)entry;
1611 *map = isl_map_lexmax(*map);
1613 return *map ? 0 : -1;
1616 __isl_give isl_union_map *isl_union_map_lexmax(
1617 __isl_take isl_union_map *umap)
1619 return un_op(umap, &lexmax_entry);
1622 __isl_give isl_union_set *isl_union_set_lexmax(
1623 __isl_take isl_union_set *uset)
1625 return isl_union_map_lexmax(uset);
1628 static int universe_entry(void **entry, void *user)
1630 isl_map *map = *entry;
1631 isl_union_map **res = user;
1633 map = isl_map_universe(isl_map_get_space(map));
1634 *res = isl_union_map_add_map(*res, map);
1639 __isl_give isl_union_map *isl_union_map_universe(__isl_take isl_union_map *umap)
1641 return cond_un_op(umap, &universe_entry);
1644 __isl_give isl_union_set *isl_union_set_universe(__isl_take isl_union_set *uset)
1646 return isl_union_map_universe(uset);
1649 static int reverse_entry(void **entry, void *user)
1651 isl_map *map = *entry;
1652 isl_union_map **res = user;
1654 *res = isl_union_map_add_map(*res, isl_map_reverse(isl_map_copy(map)));
1659 __isl_give isl_union_map *isl_union_map_reverse(__isl_take isl_union_map *umap)
1661 return cond_un_op(umap, &reverse_entry);
1664 static int params_entry(void **entry, void *user)
1666 isl_map *map = *entry;
1667 isl_union_set **res = user;
1669 *res = isl_union_set_add_set(*res, isl_map_params(isl_map_copy(map)));
1674 /* Compute the parameter domain of the given union map.
1676 __isl_give isl_set *isl_union_map_params(__isl_take isl_union_map *umap)
1680 empty = isl_union_map_is_empty(umap);
1682 return isl_union_map_free(umap);
1684 return isl_set_empty(isl_union_map_get_space(umap));
1685 return isl_set_from_union_set(cond_un_op(umap, ¶ms_entry));
1688 /* Compute the parameter domain of the given union set.
1690 __isl_give isl_set *isl_union_set_params(__isl_take isl_union_set *uset)
1692 return isl_union_map_params(uset);
1695 static int domain_entry(void **entry, void *user)
1697 isl_map *map = *entry;
1698 isl_union_set **res = user;
1700 *res = isl_union_set_add_set(*res, isl_map_domain(isl_map_copy(map)));
1705 __isl_give isl_union_set *isl_union_map_domain(__isl_take isl_union_map *umap)
1707 return cond_un_op(umap, &domain_entry);
1710 static int range_entry(void **entry, void *user)
1712 isl_map *map = *entry;
1713 isl_union_set **res = user;
1715 *res = isl_union_set_add_set(*res, isl_map_range(isl_map_copy(map)));
1720 __isl_give isl_union_set *isl_union_map_range(__isl_take isl_union_map *umap)
1722 return cond_un_op(umap, &range_entry);
1725 static int domain_map_entry(void **entry, void *user)
1727 isl_map *map = *entry;
1728 isl_union_set **res = user;
1730 *res = isl_union_map_add_map(*res,
1731 isl_map_domain_map(isl_map_copy(map)));
1736 __isl_give isl_union_map *isl_union_map_domain_map(
1737 __isl_take isl_union_map *umap)
1739 return cond_un_op(umap, &domain_map_entry);
1742 static int range_map_entry(void **entry, void *user)
1744 isl_map *map = *entry;
1745 isl_union_set **res = user;
1747 *res = isl_union_map_add_map(*res,
1748 isl_map_range_map(isl_map_copy(map)));
1753 __isl_give isl_union_map *isl_union_map_range_map(
1754 __isl_take isl_union_map *umap)
1756 return cond_un_op(umap, &range_map_entry);
1759 static int deltas_entry(void **entry, void *user)
1761 isl_map *map = *entry;
1762 isl_union_set **res = user;
1764 if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1767 *res = isl_union_set_add_set(*res, isl_map_deltas(isl_map_copy(map)));
1772 __isl_give isl_union_set *isl_union_map_deltas(__isl_take isl_union_map *umap)
1774 return cond_un_op(umap, &deltas_entry);
1777 static int deltas_map_entry(void **entry, void *user)
1779 isl_map *map = *entry;
1780 isl_union_map **res = user;
1782 if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1785 *res = isl_union_map_add_map(*res,
1786 isl_map_deltas_map(isl_map_copy(map)));
1791 __isl_give isl_union_map *isl_union_map_deltas_map(
1792 __isl_take isl_union_map *umap)
1794 return cond_un_op(umap, &deltas_map_entry);
1797 static int identity_entry(void **entry, void *user)
1799 isl_set *set = *entry;
1800 isl_union_map **res = user;
1802 *res = isl_union_map_add_map(*res, isl_set_identity(isl_set_copy(set)));
1807 __isl_give isl_union_map *isl_union_set_identity(__isl_take isl_union_set *uset)
1809 return cond_un_op(uset, &identity_entry);
1812 static int unwrap_entry(void **entry, void *user)
1814 isl_set *set = *entry;
1815 isl_union_set **res = user;
1817 if (!isl_set_is_wrapping(set))
1820 *res = isl_union_map_add_map(*res, isl_set_unwrap(isl_set_copy(set)));
1825 __isl_give isl_union_map *isl_union_set_unwrap(__isl_take isl_union_set *uset)
1827 return cond_un_op(uset, &unwrap_entry);
1830 static int wrap_entry(void **entry, void *user)
1832 isl_map *map = *entry;
1833 isl_union_set **res = user;
1835 *res = isl_union_set_add_set(*res, isl_map_wrap(isl_map_copy(map)));
1840 __isl_give isl_union_set *isl_union_map_wrap(__isl_take isl_union_map *umap)
1842 return cond_un_op(umap, &wrap_entry);
1845 struct isl_union_map_is_subset_data {
1846 isl_union_map *umap2;
1850 static int is_subset_entry(void **entry, void *user)
1852 struct isl_union_map_is_subset_data *data = user;
1854 struct isl_hash_table_entry *entry2;
1855 isl_map *map = *entry;
1857 hash = isl_space_get_hash(map->dim);
1858 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1859 hash, &has_dim, map->dim, 0);
1861 int empty = isl_map_is_empty(map);
1866 data->is_subset = 0;
1870 data->is_subset = isl_map_is_subset(map, entry2->data);
1871 if (data->is_subset < 0 || !data->is_subset)
1877 int isl_union_map_is_subset(__isl_keep isl_union_map *umap1,
1878 __isl_keep isl_union_map *umap2)
1880 struct isl_union_map_is_subset_data data = { NULL, 1 };
1882 umap1 = isl_union_map_copy(umap1);
1883 umap2 = isl_union_map_copy(umap2);
1884 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
1885 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
1887 if (!umap1 || !umap2)
1891 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1892 &is_subset_entry, &data) < 0 &&
1896 isl_union_map_free(umap1);
1897 isl_union_map_free(umap2);
1899 return data.is_subset;
1901 isl_union_map_free(umap1);
1902 isl_union_map_free(umap2);
1906 int isl_union_set_is_subset(__isl_keep isl_union_set *uset1,
1907 __isl_keep isl_union_set *uset2)
1909 return isl_union_map_is_subset(uset1, uset2);
1912 int isl_union_map_is_equal(__isl_keep isl_union_map *umap1,
1913 __isl_keep isl_union_map *umap2)
1917 if (!umap1 || !umap2)
1919 is_subset = isl_union_map_is_subset(umap1, umap2);
1922 is_subset = isl_union_map_is_subset(umap2, umap1);
1926 int isl_union_set_is_equal(__isl_keep isl_union_set *uset1,
1927 __isl_keep isl_union_set *uset2)
1929 return isl_union_map_is_equal(uset1, uset2);
1932 int isl_union_map_is_strict_subset(__isl_keep isl_union_map *umap1,
1933 __isl_keep isl_union_map *umap2)
1937 if (!umap1 || !umap2)
1939 is_subset = isl_union_map_is_subset(umap1, umap2);
1942 is_subset = isl_union_map_is_subset(umap2, umap1);
1943 if (is_subset == -1)
1948 int isl_union_set_is_strict_subset(__isl_keep isl_union_set *uset1,
1949 __isl_keep isl_union_set *uset2)
1951 return isl_union_map_is_strict_subset(uset1, uset2);
1954 static int sample_entry(void **entry, void *user)
1956 isl_basic_map **sample = (isl_basic_map **)user;
1957 isl_map *map = *entry;
1959 *sample = isl_map_sample(isl_map_copy(map));
1962 if (!isl_basic_map_plain_is_empty(*sample))
1967 __isl_give isl_basic_map *isl_union_map_sample(__isl_take isl_union_map *umap)
1969 isl_basic_map *sample = NULL;
1974 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1975 &sample_entry, &sample) < 0 &&
1980 sample = isl_basic_map_empty(isl_union_map_get_space(umap));
1982 isl_union_map_free(umap);
1986 isl_union_map_free(umap);
1990 __isl_give isl_basic_set *isl_union_set_sample(__isl_take isl_union_set *uset)
1992 return (isl_basic_set *)isl_union_map_sample(uset);
1995 struct isl_forall_data {
1997 int (*fn)(__isl_keep isl_map *map);
2000 static int forall_entry(void **entry, void *user)
2002 struct isl_forall_data *data = user;
2003 isl_map *map = *entry;
2005 data->res = data->fn(map);
2015 static int union_map_forall(__isl_keep isl_union_map *umap,
2016 int (*fn)(__isl_keep isl_map *map))
2018 struct isl_forall_data data = { 1, fn };
2023 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
2024 &forall_entry, &data) < 0 && data.res)
2030 struct isl_forall_user_data {
2032 int (*fn)(__isl_keep isl_map *map, void *user);
2036 static int forall_user_entry(void **entry, void *user)
2038 struct isl_forall_user_data *data = user;
2039 isl_map *map = *entry;
2041 data->res = data->fn(map, data->user);
2051 /* Check if fn(map, user) returns true for all maps "map" in umap.
2053 static int union_map_forall_user(__isl_keep isl_union_map *umap,
2054 int (*fn)(__isl_keep isl_map *map, void *user), void *user)
2056 struct isl_forall_user_data data = { 1, fn, user };
2061 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
2062 &forall_user_entry, &data) < 0 && data.res)
2068 int isl_union_map_is_empty(__isl_keep isl_union_map *umap)
2070 return union_map_forall(umap, &isl_map_is_empty);
2073 int isl_union_set_is_empty(__isl_keep isl_union_set *uset)
2075 return isl_union_map_is_empty(uset);
2078 static int is_subset_of_identity(__isl_keep isl_map *map)
2087 if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
2090 dim = isl_map_get_space(map);
2091 id = isl_map_identity(dim);
2093 is_subset = isl_map_is_subset(map, id);
2100 /* Check if the given map is single-valued.
2105 * and check if the result is a subset of the identity mapping.
2107 int isl_union_map_is_single_valued(__isl_keep isl_union_map *umap)
2109 isl_union_map *test;
2112 if (isl_union_map_n_map(umap) == 1) {
2114 umap = isl_union_map_copy(umap);
2115 map = isl_map_from_union_map(umap);
2116 sv = isl_map_is_single_valued(map);
2121 test = isl_union_map_reverse(isl_union_map_copy(umap));
2122 test = isl_union_map_apply_range(test, isl_union_map_copy(umap));
2124 sv = union_map_forall(test, &is_subset_of_identity);
2126 isl_union_map_free(test);
2131 int isl_union_map_is_injective(__isl_keep isl_union_map *umap)
2135 umap = isl_union_map_copy(umap);
2136 umap = isl_union_map_reverse(umap);
2137 in = isl_union_map_is_single_valued(umap);
2138 isl_union_map_free(umap);
2143 /* Represents a map that has a fixed value (v) for one of its
2145 * The map in this structure is not reference counted, so it
2146 * is only valid while the isl_union_map from which it was
2147 * obtained is still alive.
2149 struct isl_fixed_map {
2154 static struct isl_fixed_map *alloc_isl_fixed_map_array(isl_ctx *ctx,
2158 struct isl_fixed_map *v;
2160 v = isl_calloc_array(ctx, struct isl_fixed_map, n);
2163 for (i = 0; i < n; ++i)
2164 isl_int_init(v[i].v);
2168 static void free_isl_fixed_map_array(struct isl_fixed_map *v, int n)
2174 for (i = 0; i < n; ++i)
2175 isl_int_clear(v[i].v);
2179 /* Compare the "v" field of two isl_fixed_map structs.
2181 static int qsort_fixed_map_cmp(const void *p1, const void *p2)
2183 const struct isl_fixed_map *e1 = (const struct isl_fixed_map *) p1;
2184 const struct isl_fixed_map *e2 = (const struct isl_fixed_map *) p2;
2186 return isl_int_cmp(e1->v, e2->v);
2189 /* Internal data structure used while checking whether all maps
2190 * in a union_map have a fixed value for a given output dimension.
2191 * v is the list of maps, with the fixed value for the dimension
2192 * n is the number of maps considered so far
2193 * pos is the output dimension under investigation
2195 struct isl_fixed_dim_data {
2196 struct isl_fixed_map *v;
2201 static int fixed_at_pos(__isl_keep isl_map *map, void *user)
2203 struct isl_fixed_dim_data *data = user;
2205 data->v[data->n].map = map;
2206 return isl_map_plain_is_fixed(map, isl_dim_out, data->pos,
2207 &data->v[data->n++].v);
2210 static int plain_injective_on_range(__isl_take isl_union_map *umap,
2211 int first, int n_range);
2213 /* Given a list of the maps, with their fixed values at output dimension "pos",
2214 * check whether the ranges of the maps form an obvious partition.
2216 * We first sort the maps according to their fixed values.
2217 * If all maps have a different value, then we know the ranges form
2219 * Otherwise, we collect the maps with the same fixed value and
2220 * check whether each such collection is obviously injective
2221 * based on later dimensions.
2223 static int separates(struct isl_fixed_map *v, int n,
2224 __isl_take isl_space *dim, int pos, int n_range)
2231 qsort(v, n, sizeof(*v), &qsort_fixed_map_cmp);
2233 for (i = 0; i + 1 < n; ++i) {
2235 isl_union_map *part;
2238 for (j = i + 1; j < n; ++j)
2239 if (isl_int_ne(v[i].v, v[j].v))
2245 part = isl_union_map_alloc(isl_space_copy(dim), j - i);
2246 for (k = i; k < j; ++k)
2247 part = isl_union_map_add_map(part,
2248 isl_map_copy(v[k].map));
2250 injective = plain_injective_on_range(part, pos + 1, n_range);
2259 isl_space_free(dim);
2260 free_isl_fixed_map_array(v, n);
2263 isl_space_free(dim);
2264 free_isl_fixed_map_array(v, n);
2268 /* Check whether the maps in umap have obviously distinct ranges.
2269 * In particular, check for an output dimension in the range
2270 * [first,n_range) for which all maps have a fixed value
2271 * and then check if these values, possibly along with fixed values
2272 * at later dimensions, entail distinct ranges.
2274 static int plain_injective_on_range(__isl_take isl_union_map *umap,
2275 int first, int n_range)
2279 struct isl_fixed_dim_data data = { NULL };
2281 ctx = isl_union_map_get_ctx(umap);
2283 n = isl_union_map_n_map(umap);
2288 isl_union_map_free(umap);
2292 if (first >= n_range) {
2293 isl_union_map_free(umap);
2297 data.v = alloc_isl_fixed_map_array(ctx, n);
2301 for (data.pos = first; data.pos < n_range; ++data.pos) {
2307 fixed = union_map_forall_user(umap, &fixed_at_pos, &data);
2312 dim = isl_union_map_get_space(umap);
2313 injective = separates(data.v, n, dim, data.pos, n_range);
2314 isl_union_map_free(umap);
2318 free_isl_fixed_map_array(data.v, n);
2319 isl_union_map_free(umap);
2323 free_isl_fixed_map_array(data.v, n);
2324 isl_union_map_free(umap);
2328 /* Check whether the maps in umap that map to subsets of "ran"
2329 * have obviously distinct ranges.
2331 static int plain_injective_on_range_wrap(__isl_keep isl_set *ran, void *user)
2333 isl_union_map *umap = user;
2335 umap = isl_union_map_copy(umap);
2336 umap = isl_union_map_intersect_range(umap,
2337 isl_union_set_from_set(isl_set_copy(ran)));
2338 return plain_injective_on_range(umap, 0, isl_set_dim(ran, isl_dim_set));
2341 /* Check if the given union_map is obviously injective.
2343 * In particular, we first check if all individual maps are obviously
2344 * injective and then check if all the ranges of these maps are
2345 * obviously disjoint.
2347 int isl_union_map_plain_is_injective(__isl_keep isl_union_map *umap)
2350 isl_union_map *univ;
2353 in = union_map_forall(umap, &isl_map_plain_is_injective);
2359 univ = isl_union_map_universe(isl_union_map_copy(umap));
2360 ran = isl_union_map_range(univ);
2362 in = union_map_forall_user(ran, &plain_injective_on_range_wrap, umap);
2364 isl_union_set_free(ran);
2369 int isl_union_map_is_bijective(__isl_keep isl_union_map *umap)
2373 sv = isl_union_map_is_single_valued(umap);
2377 return isl_union_map_is_injective(umap);
2380 static int zip_entry(void **entry, void *user)
2382 isl_map *map = *entry;
2383 isl_union_map **res = user;
2385 if (!isl_map_can_zip(map))
2388 *res = isl_union_map_add_map(*res, isl_map_zip(isl_map_copy(map)));
2393 __isl_give isl_union_map *isl_union_map_zip(__isl_take isl_union_map *umap)
2395 return cond_un_op(umap, &zip_entry);
2398 static int uncurry_entry(void **entry, void *user)
2400 isl_map *map = *entry;
2401 isl_union_map **res = user;
2403 if (!isl_map_can_uncurry(map))
2406 *res = isl_union_map_add_map(*res, isl_map_uncurry(isl_map_copy(map)));
2411 /* Given a union map, take the maps of the form A -> (B -> C) and
2412 * return the union of the corresponding maps (A -> B) -> C.
2414 __isl_give isl_union_map *isl_union_map_uncurry(__isl_take isl_union_map *umap)
2416 return cond_un_op(umap, &uncurry_entry);
2419 static int curry_entry(void **entry, void *user)
2421 isl_map *map = *entry;
2422 isl_union_map **res = user;
2424 if (!isl_map_can_curry(map))
2427 *res = isl_union_map_add_map(*res, isl_map_curry(isl_map_copy(map)));
2432 /* Given a union map, take the maps of the form (A -> B) -> C and
2433 * return the union of the corresponding maps A -> (B -> C).
2435 __isl_give isl_union_map *isl_union_map_curry(__isl_take isl_union_map *umap)
2437 return cond_un_op(umap, &curry_entry);
2440 static int lift_entry(void **entry, void *user)
2442 isl_set *set = *entry;
2443 isl_union_set **res = user;
2445 *res = isl_union_set_add_set(*res, isl_set_lift(isl_set_copy(set)));
2450 __isl_give isl_union_set *isl_union_set_lift(__isl_take isl_union_set *uset)
2452 return cond_un_op(uset, &lift_entry);
2455 static int coefficients_entry(void **entry, void *user)
2457 isl_set *set = *entry;
2458 isl_union_set **res = user;
2460 set = isl_set_copy(set);
2461 set = isl_set_from_basic_set(isl_set_coefficients(set));
2462 *res = isl_union_set_add_set(*res, set);
2467 __isl_give isl_union_set *isl_union_set_coefficients(
2468 __isl_take isl_union_set *uset)
2477 ctx = isl_union_set_get_ctx(uset);
2478 dim = isl_space_set_alloc(ctx, 0, 0);
2479 res = isl_union_map_alloc(dim, uset->table.n);
2480 if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
2481 &coefficients_entry, &res) < 0)
2484 isl_union_set_free(uset);
2487 isl_union_set_free(uset);
2488 isl_union_set_free(res);
2492 static int solutions_entry(void **entry, void *user)
2494 isl_set *set = *entry;
2495 isl_union_set **res = user;
2497 set = isl_set_copy(set);
2498 set = isl_set_from_basic_set(isl_set_solutions(set));
2500 *res = isl_union_set_from_set(set);
2502 *res = isl_union_set_add_set(*res, set);
2510 __isl_give isl_union_set *isl_union_set_solutions(
2511 __isl_take isl_union_set *uset)
2513 isl_union_set *res = NULL;
2518 if (uset->table.n == 0) {
2519 res = isl_union_set_empty(isl_union_set_get_space(uset));
2520 isl_union_set_free(uset);
2524 if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
2525 &solutions_entry, &res) < 0)
2528 isl_union_set_free(uset);
2531 isl_union_set_free(uset);
2532 isl_union_set_free(res);