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,
47 umap = isl_calloc_type(dim->ctx, isl_union_map);
53 if (isl_hash_table_init(dim->ctx, &umap->table, size) < 0)
59 isl_union_map_free(umap);
63 __isl_give isl_union_map *isl_union_map_empty(__isl_take isl_space *dim)
65 return isl_union_map_alloc(dim, 16);
68 __isl_give isl_union_set *isl_union_set_empty(__isl_take isl_space *dim)
70 return isl_union_map_empty(dim);
73 isl_ctx *isl_union_map_get_ctx(__isl_keep isl_union_map *umap)
75 return umap ? umap->dim->ctx : NULL;
78 isl_ctx *isl_union_set_get_ctx(__isl_keep isl_union_set *uset)
80 return uset ? uset->dim->ctx : NULL;
83 __isl_give isl_space *isl_union_map_get_space(__isl_keep isl_union_map *umap)
87 return isl_space_copy(umap->dim);
90 __isl_give isl_space *isl_union_set_get_space(__isl_keep isl_union_set *uset)
92 return isl_union_map_get_space(uset);
95 static int free_umap_entry(void **entry, void *user)
97 isl_map *map = *entry;
102 static int add_map(__isl_take isl_map *map, void *user)
104 isl_union_map **umap = (isl_union_map **)user;
106 *umap = isl_union_map_add_map(*umap, map);
111 __isl_give isl_union_map *isl_union_map_dup(__isl_keep isl_union_map *umap)
118 dup = isl_union_map_empty(isl_space_copy(umap->dim));
119 if (isl_union_map_foreach_map(umap, &add_map, &dup) < 0)
123 isl_union_map_free(dup);
127 __isl_give isl_union_map *isl_union_map_cow(__isl_take isl_union_map *umap)
135 return isl_union_map_dup(umap);
138 struct isl_union_align {
143 static int align_entry(void **entry, void *user)
145 isl_map *map = *entry;
147 struct isl_union_align *data = user;
149 exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
150 isl_map_get_space(map));
152 data->res = isl_union_map_add_map(data->res,
153 isl_map_realign(isl_map_copy(map), exp));
158 /* Align the parameters of umap along those of model.
159 * The result has the parameters of model first, in the same order
160 * as they appear in model, followed by any remaining parameters of
161 * umap that do not appear in model.
163 __isl_give isl_union_map *isl_union_map_align_params(
164 __isl_take isl_union_map *umap, __isl_take isl_space *model)
166 struct isl_union_align data = { NULL, NULL };
171 if (isl_space_match(umap->dim, isl_dim_param, model, isl_dim_param)) {
172 isl_space_free(model);
176 model = isl_space_params(model);
177 data.exp = isl_parameter_alignment_reordering(umap->dim, model);
181 data.res = isl_union_map_alloc(isl_space_copy(data.exp->dim),
183 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
184 &align_entry, &data) < 0)
187 isl_reordering_free(data.exp);
188 isl_union_map_free(umap);
189 isl_space_free(model);
192 isl_reordering_free(data.exp);
193 isl_union_map_free(umap);
194 isl_union_map_free(data.res);
195 isl_space_free(model);
199 __isl_give isl_union_set *isl_union_set_align_params(
200 __isl_take isl_union_set *uset, __isl_take isl_space *model)
202 return isl_union_map_align_params(uset, model);
205 __isl_give isl_union_map *isl_union_map_union(__isl_take isl_union_map *umap1,
206 __isl_take isl_union_map *umap2)
208 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
209 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
211 umap1 = isl_union_map_cow(umap1);
213 if (!umap1 || !umap2)
216 if (isl_union_map_foreach_map(umap2, &add_map, &umap1) < 0)
219 isl_union_map_free(umap2);
223 isl_union_map_free(umap1);
224 isl_union_map_free(umap2);
228 __isl_give isl_union_set *isl_union_set_union(__isl_take isl_union_set *uset1,
229 __isl_take isl_union_set *uset2)
231 return isl_union_map_union(uset1, uset2);
234 __isl_give isl_union_map *isl_union_map_copy(__isl_keep isl_union_map *umap)
243 __isl_give isl_union_set *isl_union_set_copy(__isl_keep isl_union_set *uset)
245 return isl_union_map_copy(uset);
248 void *isl_union_map_free(__isl_take isl_union_map *umap)
256 isl_hash_table_foreach(umap->dim->ctx, &umap->table,
257 &free_umap_entry, NULL);
258 isl_hash_table_clear(&umap->table);
259 isl_space_free(umap->dim);
264 void *isl_union_set_free(__isl_take isl_union_set *uset)
266 return isl_union_map_free(uset);
269 static int has_dim(const void *entry, const void *val)
271 isl_map *map = (isl_map *)entry;
272 isl_space *dim = (isl_space *)val;
274 return isl_space_is_equal(map->dim, dim);
277 __isl_give isl_union_map *isl_union_map_add_map(__isl_take isl_union_map *umap,
278 __isl_take isl_map *map)
281 struct isl_hash_table_entry *entry;
286 if (isl_map_plain_is_empty(map)) {
291 if (!isl_space_match(map->dim, isl_dim_param, umap->dim, isl_dim_param)) {
292 umap = isl_union_map_align_params(umap, isl_map_get_space(map));
293 map = isl_map_align_params(map, isl_union_map_get_space(umap));
296 umap = isl_union_map_cow(umap);
301 hash = isl_space_get_hash(map->dim);
302 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
303 &has_dim, map->dim, 1);
310 entry->data = isl_map_union(entry->data, isl_map_copy(map));
319 isl_union_map_free(umap);
323 __isl_give isl_union_set *isl_union_set_add_set(__isl_take isl_union_set *uset,
324 __isl_take isl_set *set)
326 return isl_union_map_add_map(uset, (isl_map *)set);
329 __isl_give isl_union_map *isl_union_map_from_map(__isl_take isl_map *map)
337 dim = isl_map_get_space(map);
338 dim = isl_space_params(dim);
339 umap = isl_union_map_empty(dim);
340 umap = isl_union_map_add_map(umap, map);
345 __isl_give isl_union_set *isl_union_set_from_set(__isl_take isl_set *set)
347 return isl_union_map_from_map((isl_map *)set);
350 __isl_give isl_union_map *isl_union_map_from_basic_map(
351 __isl_take isl_basic_map *bmap)
353 return isl_union_map_from_map(isl_map_from_basic_map(bmap));
356 __isl_give isl_union_set *isl_union_set_from_basic_set(
357 __isl_take isl_basic_set *bset)
359 return isl_union_map_from_basic_map(bset);
362 struct isl_union_map_foreach_data
364 int (*fn)(__isl_take isl_map *map, void *user);
368 static int call_on_copy(void **entry, void *user)
370 isl_map *map = *entry;
371 struct isl_union_map_foreach_data *data;
372 data = (struct isl_union_map_foreach_data *)user;
374 return data->fn(isl_map_copy(map), data->user);
377 int isl_union_map_n_map(__isl_keep isl_union_map *umap)
379 return umap ? umap->table.n : 0;
382 int isl_union_set_n_set(__isl_keep isl_union_set *uset)
384 return uset ? uset->table.n : 0;
387 int isl_union_map_foreach_map(__isl_keep isl_union_map *umap,
388 int (*fn)(__isl_take isl_map *map, void *user), void *user)
390 struct isl_union_map_foreach_data data = { fn, user };
395 return isl_hash_table_foreach(umap->dim->ctx, &umap->table,
396 &call_on_copy, &data);
399 static int copy_map(void **entry, void *user)
401 isl_map *map = *entry;
402 isl_map **map_p = user;
404 *map_p = isl_map_copy(map);
409 __isl_give isl_map *isl_map_from_union_map(__isl_take isl_union_map *umap)
416 ctx = isl_union_map_get_ctx(umap);
417 if (umap->table.n != 1)
418 isl_die(ctx, isl_error_invalid,
419 "union map needs to contain elements in exactly "
420 "one space", return isl_union_map_free(umap));
422 isl_hash_table_foreach(ctx, &umap->table, ©_map, &map);
424 isl_union_map_free(umap);
429 __isl_give isl_set *isl_set_from_union_set(__isl_take isl_union_set *uset)
431 return isl_map_from_union_map(uset);
434 /* Extract the map in "umap" that lives in the given space (ignoring
437 __isl_give isl_map *isl_union_map_extract_map(__isl_keep isl_union_map *umap,
438 __isl_take isl_space *space)
441 struct isl_hash_table_entry *entry;
443 space = isl_space_drop_dims(space, isl_dim_param,
444 0, isl_space_dim(space, isl_dim_param));
445 space = isl_space_align_params(space, isl_union_map_get_space(umap));
449 hash = isl_space_get_hash(space);
450 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
453 return isl_map_empty(space);
454 isl_space_free(space);
455 return isl_map_copy(entry->data);
457 isl_space_free(space);
461 __isl_give isl_set *isl_union_set_extract_set(__isl_keep isl_union_set *uset,
462 __isl_take isl_space *dim)
464 return (isl_set *)isl_union_map_extract_map(uset, dim);
467 /* Check if umap contains a map in the given space.
469 __isl_give int isl_union_map_contains(__isl_keep isl_union_map *umap,
470 __isl_keep isl_space *dim)
473 struct isl_hash_table_entry *entry;
478 hash = isl_space_get_hash(dim);
479 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
484 __isl_give int isl_union_set_contains(__isl_keep isl_union_set *uset,
485 __isl_keep isl_space *dim)
487 return isl_union_map_contains(uset, dim);
490 int isl_union_set_foreach_set(__isl_keep isl_union_set *uset,
491 int (*fn)(__isl_take isl_set *set, void *user), void *user)
493 return isl_union_map_foreach_map(uset,
494 (int(*)(__isl_take isl_map *, void*))fn, user);
497 struct isl_union_set_foreach_point_data {
498 int (*fn)(__isl_take isl_point *pnt, void *user);
502 static int foreach_point(__isl_take isl_set *set, void *user)
504 struct isl_union_set_foreach_point_data *data = user;
507 r = isl_set_foreach_point(set, data->fn, data->user);
513 int isl_union_set_foreach_point(__isl_keep isl_union_set *uset,
514 int (*fn)(__isl_take isl_point *pnt, void *user), void *user)
516 struct isl_union_set_foreach_point_data data = { fn, user };
517 return isl_union_set_foreach_set(uset, &foreach_point, &data);
520 struct isl_union_map_gen_bin_data {
521 isl_union_map *umap2;
525 static int subtract_entry(void **entry, void *user)
527 struct isl_union_map_gen_bin_data *data = user;
529 struct isl_hash_table_entry *entry2;
530 isl_map *map = *entry;
532 hash = isl_space_get_hash(map->dim);
533 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
534 hash, &has_dim, map->dim, 0);
535 map = isl_map_copy(map);
538 map = isl_map_subtract(map, isl_map_copy(entry2->data));
540 empty = isl_map_is_empty(map);
550 data->res = isl_union_map_add_map(data->res, map);
555 static __isl_give isl_union_map *gen_bin_op(__isl_take isl_union_map *umap1,
556 __isl_take isl_union_map *umap2, int (*fn)(void **, void *))
558 struct isl_union_map_gen_bin_data data = { NULL, NULL };
560 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
561 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
563 if (!umap1 || !umap2)
567 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
569 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
573 isl_union_map_free(umap1);
574 isl_union_map_free(umap2);
577 isl_union_map_free(umap1);
578 isl_union_map_free(umap2);
579 isl_union_map_free(data.res);
583 __isl_give isl_union_map *isl_union_map_subtract(
584 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
586 return gen_bin_op(umap1, umap2, &subtract_entry);
589 __isl_give isl_union_set *isl_union_set_subtract(
590 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
592 return isl_union_map_subtract(uset1, uset2);
595 struct isl_union_map_gen_bin_set_data {
600 static int intersect_params_entry(void **entry, void *user)
602 struct isl_union_map_gen_bin_set_data *data = user;
603 isl_map *map = *entry;
606 map = isl_map_copy(map);
607 map = isl_map_intersect_params(map, isl_set_copy(data->set));
609 empty = isl_map_is_empty(map);
615 data->res = isl_union_map_add_map(data->res, map);
620 static __isl_give isl_union_map *gen_bin_set_op(__isl_take isl_union_map *umap,
621 __isl_take isl_set *set, int (*fn)(void **, void *))
623 struct isl_union_map_gen_bin_set_data data = { NULL, NULL };
625 umap = isl_union_map_align_params(umap, isl_set_get_space(set));
626 set = isl_set_align_params(set, isl_union_map_get_space(umap));
632 data.res = isl_union_map_alloc(isl_space_copy(umap->dim),
634 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
638 isl_union_map_free(umap);
642 isl_union_map_free(umap);
644 isl_union_map_free(data.res);
648 __isl_give isl_union_map *isl_union_map_intersect_params(
649 __isl_take isl_union_map *umap, __isl_take isl_set *set)
651 return gen_bin_set_op(umap, set, &intersect_params_entry);
654 __isl_give isl_union_set *isl_union_set_intersect_params(
655 __isl_take isl_union_set *uset, __isl_take isl_set *set)
657 return isl_union_map_intersect_params(uset, set);
660 static __isl_give isl_union_map *union_map_intersect_params(
661 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
663 return isl_union_map_intersect_params(umap,
664 isl_set_from_union_set(uset));
667 static __isl_give isl_union_map *union_map_gist_params(
668 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
670 return isl_union_map_gist_params(umap, isl_set_from_union_set(uset));
673 struct isl_union_map_match_bin_data {
674 isl_union_map *umap2;
676 __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*);
679 static int match_bin_entry(void **entry, void *user)
681 struct isl_union_map_match_bin_data *data = user;
683 struct isl_hash_table_entry *entry2;
684 isl_map *map = *entry;
687 hash = isl_space_get_hash(map->dim);
688 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
689 hash, &has_dim, map->dim, 0);
693 map = isl_map_copy(map);
694 map = data->fn(map, isl_map_copy(entry2->data));
696 empty = isl_map_is_empty(map);
706 data->res = isl_union_map_add_map(data->res, map);
711 static __isl_give isl_union_map *match_bin_op(__isl_take isl_union_map *umap1,
712 __isl_take isl_union_map *umap2,
713 __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*))
715 struct isl_union_map_match_bin_data data = { NULL, NULL, fn };
717 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
718 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
720 if (!umap1 || !umap2)
724 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
726 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
727 &match_bin_entry, &data) < 0)
730 isl_union_map_free(umap1);
731 isl_union_map_free(umap2);
734 isl_union_map_free(umap1);
735 isl_union_map_free(umap2);
736 isl_union_map_free(data.res);
740 __isl_give isl_union_map *isl_union_map_intersect(
741 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
743 return match_bin_op(umap1, umap2, &isl_map_intersect);
746 /* Compute the intersection of the two union_sets.
747 * As a special case, if exactly one of the two union_sets
748 * is a parameter domain, then intersect the parameter domain
749 * of the other one with this set.
751 __isl_give isl_union_set *isl_union_set_intersect(
752 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
756 p1 = isl_union_set_is_params(uset1);
757 p2 = isl_union_set_is_params(uset2);
758 if (p1 < 0 || p2 < 0)
761 return union_map_intersect_params(uset1, uset2);
763 return union_map_intersect_params(uset2, uset1);
764 return isl_union_map_intersect(uset1, uset2);
766 isl_union_set_free(uset1);
767 isl_union_set_free(uset2);
771 static int gist_params_entry(void **entry, void *user)
773 struct isl_union_map_gen_bin_set_data *data = user;
774 isl_map *map = *entry;
777 map = isl_map_copy(map);
778 map = isl_map_gist_params(map, isl_set_copy(data->set));
780 empty = isl_map_is_empty(map);
786 data->res = isl_union_map_add_map(data->res, map);
791 __isl_give isl_union_map *isl_union_map_gist_params(
792 __isl_take isl_union_map *umap, __isl_take isl_set *set)
794 return gen_bin_set_op(umap, set, &gist_params_entry);
797 __isl_give isl_union_set *isl_union_set_gist_params(
798 __isl_take isl_union_set *uset, __isl_take isl_set *set)
800 return isl_union_map_gist_params(uset, set);
803 __isl_give isl_union_map *isl_union_map_gist(__isl_take isl_union_map *umap,
804 __isl_take isl_union_map *context)
806 return match_bin_op(umap, context, &isl_map_gist);
809 __isl_give isl_union_set *isl_union_set_gist(__isl_take isl_union_set *uset,
810 __isl_take isl_union_set *context)
812 if (isl_union_set_is_params(context))
813 return union_map_gist_params(uset, context);
814 return isl_union_map_gist(uset, context);
817 static __isl_give isl_map *lex_le_set(__isl_take isl_map *set1,
818 __isl_take isl_map *set2)
820 return isl_set_lex_le_set((isl_set *)set1, (isl_set *)set2);
823 static __isl_give isl_map *lex_lt_set(__isl_take isl_map *set1,
824 __isl_take isl_map *set2)
826 return isl_set_lex_lt_set((isl_set *)set1, (isl_set *)set2);
829 __isl_give isl_union_map *isl_union_set_lex_lt_union_set(
830 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
832 return match_bin_op(uset1, uset2, &lex_lt_set);
835 __isl_give isl_union_map *isl_union_set_lex_le_union_set(
836 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
838 return match_bin_op(uset1, uset2, &lex_le_set);
841 __isl_give isl_union_map *isl_union_set_lex_gt_union_set(
842 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
844 return isl_union_map_reverse(isl_union_set_lex_lt_union_set(uset2, uset1));
847 __isl_give isl_union_map *isl_union_set_lex_ge_union_set(
848 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
850 return isl_union_map_reverse(isl_union_set_lex_le_union_set(uset2, uset1));
853 __isl_give isl_union_map *isl_union_map_lex_gt_union_map(
854 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
856 return isl_union_map_reverse(isl_union_map_lex_lt_union_map(umap2, umap1));
859 __isl_give isl_union_map *isl_union_map_lex_ge_union_map(
860 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
862 return isl_union_map_reverse(isl_union_map_lex_le_union_map(umap2, umap1));
865 static int intersect_domain_entry(void **entry, void *user)
867 struct isl_union_map_gen_bin_data *data = user;
869 struct isl_hash_table_entry *entry2;
871 isl_map *map = *entry;
874 dim = isl_map_get_space(map);
875 dim = isl_space_domain(dim);
876 hash = isl_space_get_hash(dim);
877 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
878 hash, &has_dim, dim, 0);
883 map = isl_map_copy(map);
884 map = isl_map_intersect_domain(map, isl_set_copy(entry2->data));
886 empty = isl_map_is_empty(map);
896 data->res = isl_union_map_add_map(data->res, map);
901 /* Intersect the domain of "umap" with "uset".
902 * If "uset" is a parameters domain, then intersect the parameter
903 * domain of "umap" with this set.
905 __isl_give isl_union_map *isl_union_map_intersect_domain(
906 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
908 if (isl_union_set_is_params(uset))
909 return union_map_intersect_params(umap, uset);
910 return gen_bin_op(umap, uset, &intersect_domain_entry);
913 static int gist_domain_entry(void **entry, void *user)
915 struct isl_union_map_gen_bin_data *data = user;
917 struct isl_hash_table_entry *entry2;
919 isl_map *map = *entry;
922 dim = isl_map_get_space(map);
923 dim = isl_space_domain(dim);
924 hash = isl_space_get_hash(dim);
925 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
926 hash, &has_dim, dim, 0);
931 map = isl_map_copy(map);
932 map = isl_map_gist_domain(map, isl_set_copy(entry2->data));
934 empty = isl_map_is_empty(map);
940 data->res = isl_union_map_add_map(data->res, map);
945 /* Compute the gist of "umap" with respect to the domain "uset".
946 * If "uset" is a parameters domain, then compute the gist
947 * with respect to this parameter domain.
949 __isl_give isl_union_map *isl_union_map_gist_domain(
950 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
952 if (isl_union_set_is_params(uset))
953 return union_map_gist_params(umap, uset);
954 return gen_bin_op(umap, uset, &gist_domain_entry);
957 static int gist_range_entry(void **entry, void *user)
959 struct isl_union_map_gen_bin_data *data = user;
961 struct isl_hash_table_entry *entry2;
963 isl_map *map = *entry;
966 space = isl_map_get_space(map);
967 space = isl_space_range(space);
968 hash = isl_space_get_hash(space);
969 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
970 hash, &has_dim, space, 0);
971 isl_space_free(space);
975 map = isl_map_copy(map);
976 map = isl_map_gist_range(map, isl_set_copy(entry2->data));
978 empty = isl_map_is_empty(map);
984 data->res = isl_union_map_add_map(data->res, map);
989 /* Compute the gist of "umap" with respect to the range "uset".
991 __isl_give isl_union_map *isl_union_map_gist_range(
992 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
994 return gen_bin_op(umap, uset, &gist_range_entry);
997 static int intersect_range_entry(void **entry, void *user)
999 struct isl_union_map_gen_bin_data *data = user;
1001 struct isl_hash_table_entry *entry2;
1003 isl_map *map = *entry;
1006 dim = isl_map_get_space(map);
1007 dim = isl_space_range(dim);
1008 hash = isl_space_get_hash(dim);
1009 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1010 hash, &has_dim, dim, 0);
1011 isl_space_free(dim);
1015 map = isl_map_copy(map);
1016 map = isl_map_intersect_range(map, isl_set_copy(entry2->data));
1018 empty = isl_map_is_empty(map);
1028 data->res = isl_union_map_add_map(data->res, map);
1033 __isl_give isl_union_map *isl_union_map_intersect_range(
1034 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1036 return gen_bin_op(umap, uset, &intersect_range_entry);
1039 struct isl_union_map_bin_data {
1040 isl_union_map *umap2;
1043 int (*fn)(void **entry, void *user);
1046 static int apply_range_entry(void **entry, void *user)
1048 struct isl_union_map_bin_data *data = user;
1049 isl_map *map2 = *entry;
1052 if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1053 map2->dim, isl_dim_in))
1056 map2 = isl_map_apply_range(isl_map_copy(data->map), isl_map_copy(map2));
1058 empty = isl_map_is_empty(map2);
1068 data->res = isl_union_map_add_map(data->res, map2);
1073 static int bin_entry(void **entry, void *user)
1075 struct isl_union_map_bin_data *data = user;
1076 isl_map *map = *entry;
1079 if (isl_hash_table_foreach(data->umap2->dim->ctx, &data->umap2->table,
1080 data->fn, data) < 0)
1086 static __isl_give isl_union_map *bin_op(__isl_take isl_union_map *umap1,
1087 __isl_take isl_union_map *umap2, int (*fn)(void **entry, void *user))
1089 struct isl_union_map_bin_data data = { NULL, NULL, NULL, fn };
1091 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
1092 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
1094 if (!umap1 || !umap2)
1098 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
1100 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1101 &bin_entry, &data) < 0)
1104 isl_union_map_free(umap1);
1105 isl_union_map_free(umap2);
1108 isl_union_map_free(umap1);
1109 isl_union_map_free(umap2);
1110 isl_union_map_free(data.res);
1114 __isl_give isl_union_map *isl_union_map_apply_range(
1115 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1117 return bin_op(umap1, umap2, &apply_range_entry);
1120 __isl_give isl_union_map *isl_union_map_apply_domain(
1121 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1123 umap1 = isl_union_map_reverse(umap1);
1124 umap1 = isl_union_map_apply_range(umap1, umap2);
1125 return isl_union_map_reverse(umap1);
1128 __isl_give isl_union_set *isl_union_set_apply(
1129 __isl_take isl_union_set *uset, __isl_take isl_union_map *umap)
1131 return isl_union_map_apply_range(uset, umap);
1134 static int map_lex_lt_entry(void **entry, void *user)
1136 struct isl_union_map_bin_data *data = user;
1137 isl_map *map2 = *entry;
1139 if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1140 map2->dim, isl_dim_out))
1143 map2 = isl_map_lex_lt_map(isl_map_copy(data->map), isl_map_copy(map2));
1145 data->res = isl_union_map_add_map(data->res, map2);
1150 __isl_give isl_union_map *isl_union_map_lex_lt_union_map(
1151 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1153 return bin_op(umap1, umap2, &map_lex_lt_entry);
1156 static int map_lex_le_entry(void **entry, void *user)
1158 struct isl_union_map_bin_data *data = user;
1159 isl_map *map2 = *entry;
1161 if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1162 map2->dim, isl_dim_out))
1165 map2 = isl_map_lex_le_map(isl_map_copy(data->map), isl_map_copy(map2));
1167 data->res = isl_union_map_add_map(data->res, map2);
1172 __isl_give isl_union_map *isl_union_map_lex_le_union_map(
1173 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1175 return bin_op(umap1, umap2, &map_lex_le_entry);
1178 static int product_entry(void **entry, void *user)
1180 struct isl_union_map_bin_data *data = user;
1181 isl_map *map2 = *entry;
1183 map2 = isl_map_product(isl_map_copy(data->map), isl_map_copy(map2));
1185 data->res = isl_union_map_add_map(data->res, map2);
1190 __isl_give isl_union_map *isl_union_map_product(__isl_take isl_union_map *umap1,
1191 __isl_take isl_union_map *umap2)
1193 return bin_op(umap1, umap2, &product_entry);
1196 static int set_product_entry(void **entry, void *user)
1198 struct isl_union_map_bin_data *data = user;
1199 isl_set *set2 = *entry;
1201 set2 = isl_set_product(isl_set_copy(data->map), isl_set_copy(set2));
1203 data->res = isl_union_set_add_set(data->res, set2);
1208 __isl_give isl_union_set *isl_union_set_product(__isl_take isl_union_set *uset1,
1209 __isl_take isl_union_set *uset2)
1211 return bin_op(uset1, uset2, &set_product_entry);
1214 static int domain_product_entry(void **entry, void *user)
1216 struct isl_union_map_bin_data *data = user;
1217 isl_map *map2 = *entry;
1219 if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1220 map2->dim, isl_dim_out))
1223 map2 = isl_map_domain_product(isl_map_copy(data->map),
1224 isl_map_copy(map2));
1226 data->res = isl_union_map_add_map(data->res, map2);
1231 /* Given two maps A -> B and C -> D, construct a map [A -> C] -> (B * D)
1233 __isl_give isl_union_map *isl_union_map_domain_product(
1234 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1236 return bin_op(umap1, umap2, &domain_product_entry);
1239 static int range_product_entry(void **entry, void *user)
1241 struct isl_union_map_bin_data *data = user;
1242 isl_map *map2 = *entry;
1244 if (!isl_space_tuple_match(data->map->dim, isl_dim_in,
1245 map2->dim, isl_dim_in))
1248 map2 = isl_map_range_product(isl_map_copy(data->map),
1249 isl_map_copy(map2));
1251 data->res = isl_union_map_add_map(data->res, map2);
1256 __isl_give isl_union_map *isl_union_map_range_product(
1257 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1259 return bin_op(umap1, umap2, &range_product_entry);
1262 static int flat_range_product_entry(void **entry, void *user)
1264 struct isl_union_map_bin_data *data = user;
1265 isl_map *map2 = *entry;
1267 if (!isl_space_tuple_match(data->map->dim, isl_dim_in,
1268 map2->dim, isl_dim_in))
1271 map2 = isl_map_flat_range_product(isl_map_copy(data->map),
1272 isl_map_copy(map2));
1274 data->res = isl_union_map_add_map(data->res, map2);
1279 __isl_give isl_union_map *isl_union_map_flat_range_product(
1280 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1282 return bin_op(umap1, umap2, &flat_range_product_entry);
1285 static __isl_give isl_union_set *cond_un_op(__isl_take isl_union_map *umap,
1286 int (*fn)(void **, void *))
1293 res = isl_union_map_alloc(isl_space_copy(umap->dim), umap->table.n);
1294 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, &res) < 0)
1297 isl_union_map_free(umap);
1300 isl_union_map_free(umap);
1301 isl_union_set_free(res);
1305 static int from_range_entry(void **entry, void *user)
1307 isl_map *set = *entry;
1308 isl_union_set **res = user;
1310 *res = isl_union_map_add_map(*res,
1311 isl_map_from_range(isl_set_copy(set)));
1316 __isl_give isl_union_map *isl_union_map_from_range(
1317 __isl_take isl_union_set *uset)
1319 return cond_un_op(uset, &from_range_entry);
1322 __isl_give isl_union_map *isl_union_map_from_domain(
1323 __isl_take isl_union_set *uset)
1325 return isl_union_map_reverse(isl_union_map_from_range(uset));
1328 __isl_give isl_union_map *isl_union_map_from_domain_and_range(
1329 __isl_take isl_union_set *domain, __isl_take isl_union_set *range)
1331 return isl_union_map_apply_range(isl_union_map_from_domain(domain),
1332 isl_union_map_from_range(range));
1335 static __isl_give isl_union_map *un_op(__isl_take isl_union_map *umap,
1336 int (*fn)(void **, void *))
1338 umap = isl_union_map_cow(umap);
1342 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, NULL) < 0)
1347 isl_union_map_free(umap);
1351 static int affine_entry(void **entry, void *user)
1353 isl_map **map = (isl_map **)entry;
1355 *map = isl_map_from_basic_map(isl_map_affine_hull(*map));
1357 return *map ? 0 : -1;
1360 __isl_give isl_union_map *isl_union_map_affine_hull(
1361 __isl_take isl_union_map *umap)
1363 return un_op(umap, &affine_entry);
1366 __isl_give isl_union_set *isl_union_set_affine_hull(
1367 __isl_take isl_union_set *uset)
1369 return isl_union_map_affine_hull(uset);
1372 static int polyhedral_entry(void **entry, void *user)
1374 isl_map **map = (isl_map **)entry;
1376 *map = isl_map_from_basic_map(isl_map_polyhedral_hull(*map));
1378 return *map ? 0 : -1;
1381 __isl_give isl_union_map *isl_union_map_polyhedral_hull(
1382 __isl_take isl_union_map *umap)
1384 return un_op(umap, &polyhedral_entry);
1387 __isl_give isl_union_set *isl_union_set_polyhedral_hull(
1388 __isl_take isl_union_set *uset)
1390 return isl_union_map_polyhedral_hull(uset);
1393 static int simple_entry(void **entry, void *user)
1395 isl_map **map = (isl_map **)entry;
1397 *map = isl_map_from_basic_map(isl_map_simple_hull(*map));
1399 return *map ? 0 : -1;
1402 __isl_give isl_union_map *isl_union_map_simple_hull(
1403 __isl_take isl_union_map *umap)
1405 return un_op(umap, &simple_entry);
1408 __isl_give isl_union_set *isl_union_set_simple_hull(
1409 __isl_take isl_union_set *uset)
1411 return isl_union_map_simple_hull(uset);
1414 static int inplace_entry(void **entry, void *user)
1416 __isl_give isl_map *(*fn)(__isl_take isl_map *);
1417 isl_map **map = (isl_map **)entry;
1420 fn = *(__isl_give isl_map *(**)(__isl_take isl_map *)) user;
1421 copy = fn(isl_map_copy(*map));
1431 static __isl_give isl_union_map *inplace(__isl_take isl_union_map *umap,
1432 __isl_give isl_map *(*fn)(__isl_take isl_map *))
1437 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1438 &inplace_entry, &fn) < 0)
1443 isl_union_map_free(umap);
1447 __isl_give isl_union_map *isl_union_map_coalesce(
1448 __isl_take isl_union_map *umap)
1450 return inplace(umap, &isl_map_coalesce);
1453 __isl_give isl_union_set *isl_union_set_coalesce(
1454 __isl_take isl_union_set *uset)
1456 return isl_union_map_coalesce(uset);
1459 __isl_give isl_union_map *isl_union_map_detect_equalities(
1460 __isl_take isl_union_map *umap)
1462 return inplace(umap, &isl_map_detect_equalities);
1465 __isl_give isl_union_set *isl_union_set_detect_equalities(
1466 __isl_take isl_union_set *uset)
1468 return isl_union_map_detect_equalities(uset);
1471 __isl_give isl_union_map *isl_union_map_compute_divs(
1472 __isl_take isl_union_map *umap)
1474 return inplace(umap, &isl_map_compute_divs);
1477 __isl_give isl_union_set *isl_union_set_compute_divs(
1478 __isl_take isl_union_set *uset)
1480 return isl_union_map_compute_divs(uset);
1483 static int lexmin_entry(void **entry, void *user)
1485 isl_map **map = (isl_map **)entry;
1487 *map = isl_map_lexmin(*map);
1489 return *map ? 0 : -1;
1492 __isl_give isl_union_map *isl_union_map_lexmin(
1493 __isl_take isl_union_map *umap)
1495 return un_op(umap, &lexmin_entry);
1498 __isl_give isl_union_set *isl_union_set_lexmin(
1499 __isl_take isl_union_set *uset)
1501 return isl_union_map_lexmin(uset);
1504 static int lexmax_entry(void **entry, void *user)
1506 isl_map **map = (isl_map **)entry;
1508 *map = isl_map_lexmax(*map);
1510 return *map ? 0 : -1;
1513 __isl_give isl_union_map *isl_union_map_lexmax(
1514 __isl_take isl_union_map *umap)
1516 return un_op(umap, &lexmax_entry);
1519 __isl_give isl_union_set *isl_union_set_lexmax(
1520 __isl_take isl_union_set *uset)
1522 return isl_union_map_lexmax(uset);
1525 static int universe_entry(void **entry, void *user)
1527 isl_map *map = *entry;
1528 isl_union_map **res = user;
1530 map = isl_map_universe(isl_map_get_space(map));
1531 *res = isl_union_map_add_map(*res, map);
1536 __isl_give isl_union_map *isl_union_map_universe(__isl_take isl_union_map *umap)
1538 return cond_un_op(umap, &universe_entry);
1541 __isl_give isl_union_set *isl_union_set_universe(__isl_take isl_union_set *uset)
1543 return isl_union_map_universe(uset);
1546 static int reverse_entry(void **entry, void *user)
1548 isl_map *map = *entry;
1549 isl_union_map **res = user;
1551 *res = isl_union_map_add_map(*res, isl_map_reverse(isl_map_copy(map)));
1556 __isl_give isl_union_map *isl_union_map_reverse(__isl_take isl_union_map *umap)
1558 return cond_un_op(umap, &reverse_entry);
1561 static int params_entry(void **entry, void *user)
1563 isl_map *map = *entry;
1564 isl_union_set **res = user;
1566 *res = isl_union_set_add_set(*res, isl_map_params(isl_map_copy(map)));
1571 /* Compute the parameter domain of the given union map.
1573 __isl_give isl_set *isl_union_map_params(__isl_take isl_union_map *umap)
1577 empty = isl_union_map_is_empty(umap);
1579 return isl_union_map_free(umap);
1581 return isl_set_empty(isl_union_map_get_space(umap));
1582 return isl_set_from_union_set(cond_un_op(umap, ¶ms_entry));
1585 /* Compute the parameter domain of the given union set.
1587 __isl_give isl_set *isl_union_set_params(__isl_take isl_union_set *uset)
1589 return isl_union_map_params(uset);
1592 static int domain_entry(void **entry, void *user)
1594 isl_map *map = *entry;
1595 isl_union_set **res = user;
1597 *res = isl_union_set_add_set(*res, isl_map_domain(isl_map_copy(map)));
1602 __isl_give isl_union_set *isl_union_map_domain(__isl_take isl_union_map *umap)
1604 return cond_un_op(umap, &domain_entry);
1607 static int range_entry(void **entry, void *user)
1609 isl_map *map = *entry;
1610 isl_union_set **res = user;
1612 *res = isl_union_set_add_set(*res, isl_map_range(isl_map_copy(map)));
1617 __isl_give isl_union_set *isl_union_map_range(__isl_take isl_union_map *umap)
1619 return cond_un_op(umap, &range_entry);
1622 static int domain_map_entry(void **entry, void *user)
1624 isl_map *map = *entry;
1625 isl_union_set **res = user;
1627 *res = isl_union_map_add_map(*res,
1628 isl_map_domain_map(isl_map_copy(map)));
1633 __isl_give isl_union_map *isl_union_map_domain_map(
1634 __isl_take isl_union_map *umap)
1636 return cond_un_op(umap, &domain_map_entry);
1639 static int range_map_entry(void **entry, void *user)
1641 isl_map *map = *entry;
1642 isl_union_set **res = user;
1644 *res = isl_union_map_add_map(*res,
1645 isl_map_range_map(isl_map_copy(map)));
1650 __isl_give isl_union_map *isl_union_map_range_map(
1651 __isl_take isl_union_map *umap)
1653 return cond_un_op(umap, &range_map_entry);
1656 static int deltas_entry(void **entry, void *user)
1658 isl_map *map = *entry;
1659 isl_union_set **res = user;
1661 if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1664 *res = isl_union_set_add_set(*res, isl_map_deltas(isl_map_copy(map)));
1669 __isl_give isl_union_set *isl_union_map_deltas(__isl_take isl_union_map *umap)
1671 return cond_un_op(umap, &deltas_entry);
1674 static int deltas_map_entry(void **entry, void *user)
1676 isl_map *map = *entry;
1677 isl_union_map **res = user;
1679 if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1682 *res = isl_union_map_add_map(*res,
1683 isl_map_deltas_map(isl_map_copy(map)));
1688 __isl_give isl_union_map *isl_union_map_deltas_map(
1689 __isl_take isl_union_map *umap)
1691 return cond_un_op(umap, &deltas_map_entry);
1694 static int identity_entry(void **entry, void *user)
1696 isl_set *set = *entry;
1697 isl_union_map **res = user;
1699 *res = isl_union_map_add_map(*res, isl_set_identity(isl_set_copy(set)));
1704 __isl_give isl_union_map *isl_union_set_identity(__isl_take isl_union_set *uset)
1706 return cond_un_op(uset, &identity_entry);
1709 static int unwrap_entry(void **entry, void *user)
1711 isl_set *set = *entry;
1712 isl_union_set **res = user;
1714 if (!isl_set_is_wrapping(set))
1717 *res = isl_union_map_add_map(*res, isl_set_unwrap(isl_set_copy(set)));
1722 __isl_give isl_union_map *isl_union_set_unwrap(__isl_take isl_union_set *uset)
1724 return cond_un_op(uset, &unwrap_entry);
1727 static int wrap_entry(void **entry, void *user)
1729 isl_map *map = *entry;
1730 isl_union_set **res = user;
1732 *res = isl_union_set_add_set(*res, isl_map_wrap(isl_map_copy(map)));
1737 __isl_give isl_union_set *isl_union_map_wrap(__isl_take isl_union_map *umap)
1739 return cond_un_op(umap, &wrap_entry);
1742 struct isl_union_map_is_subset_data {
1743 isl_union_map *umap2;
1747 static int is_subset_entry(void **entry, void *user)
1749 struct isl_union_map_is_subset_data *data = user;
1751 struct isl_hash_table_entry *entry2;
1752 isl_map *map = *entry;
1754 hash = isl_space_get_hash(map->dim);
1755 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1756 hash, &has_dim, map->dim, 0);
1758 int empty = isl_map_is_empty(map);
1763 data->is_subset = 0;
1767 data->is_subset = isl_map_is_subset(map, entry2->data);
1768 if (data->is_subset < 0 || !data->is_subset)
1774 int isl_union_map_is_subset(__isl_keep isl_union_map *umap1,
1775 __isl_keep isl_union_map *umap2)
1777 struct isl_union_map_is_subset_data data = { NULL, 1 };
1779 umap1 = isl_union_map_copy(umap1);
1780 umap2 = isl_union_map_copy(umap2);
1781 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
1782 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
1784 if (!umap1 || !umap2)
1788 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1789 &is_subset_entry, &data) < 0 &&
1793 isl_union_map_free(umap1);
1794 isl_union_map_free(umap2);
1796 return data.is_subset;
1798 isl_union_map_free(umap1);
1799 isl_union_map_free(umap2);
1803 int isl_union_set_is_subset(__isl_keep isl_union_set *uset1,
1804 __isl_keep isl_union_set *uset2)
1806 return isl_union_map_is_subset(uset1, uset2);
1809 int isl_union_map_is_equal(__isl_keep isl_union_map *umap1,
1810 __isl_keep isl_union_map *umap2)
1814 if (!umap1 || !umap2)
1816 is_subset = isl_union_map_is_subset(umap1, umap2);
1819 is_subset = isl_union_map_is_subset(umap2, umap1);
1823 int isl_union_set_is_equal(__isl_keep isl_union_set *uset1,
1824 __isl_keep isl_union_set *uset2)
1826 return isl_union_map_is_equal(uset1, uset2);
1829 int isl_union_map_is_strict_subset(__isl_keep isl_union_map *umap1,
1830 __isl_keep isl_union_map *umap2)
1834 if (!umap1 || !umap2)
1836 is_subset = isl_union_map_is_subset(umap1, umap2);
1839 is_subset = isl_union_map_is_subset(umap2, umap1);
1840 if (is_subset == -1)
1845 int isl_union_set_is_strict_subset(__isl_keep isl_union_set *uset1,
1846 __isl_keep isl_union_set *uset2)
1848 return isl_union_map_is_strict_subset(uset1, uset2);
1851 static int sample_entry(void **entry, void *user)
1853 isl_basic_map **sample = (isl_basic_map **)user;
1854 isl_map *map = *entry;
1856 *sample = isl_map_sample(isl_map_copy(map));
1859 if (!isl_basic_map_plain_is_empty(*sample))
1864 __isl_give isl_basic_map *isl_union_map_sample(__isl_take isl_union_map *umap)
1866 isl_basic_map *sample = NULL;
1871 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1872 &sample_entry, &sample) < 0 &&
1877 sample = isl_basic_map_empty(isl_union_map_get_space(umap));
1879 isl_union_map_free(umap);
1883 isl_union_map_free(umap);
1887 __isl_give isl_basic_set *isl_union_set_sample(__isl_take isl_union_set *uset)
1889 return (isl_basic_set *)isl_union_map_sample(uset);
1892 struct isl_forall_data {
1894 int (*fn)(__isl_keep isl_map *map);
1897 static int forall_entry(void **entry, void *user)
1899 struct isl_forall_data *data = user;
1900 isl_map *map = *entry;
1902 data->res = data->fn(map);
1912 static int union_map_forall(__isl_keep isl_union_map *umap,
1913 int (*fn)(__isl_keep isl_map *map))
1915 struct isl_forall_data data = { 1, fn };
1920 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1921 &forall_entry, &data) < 0 && data.res)
1927 struct isl_forall_user_data {
1929 int (*fn)(__isl_keep isl_map *map, void *user);
1933 static int forall_user_entry(void **entry, void *user)
1935 struct isl_forall_user_data *data = user;
1936 isl_map *map = *entry;
1938 data->res = data->fn(map, data->user);
1948 /* Check if fn(map, user) returns true for all maps "map" in umap.
1950 static int union_map_forall_user(__isl_keep isl_union_map *umap,
1951 int (*fn)(__isl_keep isl_map *map, void *user), void *user)
1953 struct isl_forall_user_data data = { 1, fn, user };
1958 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1959 &forall_user_entry, &data) < 0 && data.res)
1965 int isl_union_map_is_empty(__isl_keep isl_union_map *umap)
1967 return union_map_forall(umap, &isl_map_is_empty);
1970 int isl_union_set_is_empty(__isl_keep isl_union_set *uset)
1972 return isl_union_map_is_empty(uset);
1975 static int is_subset_of_identity(__isl_keep isl_map *map)
1984 if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1987 dim = isl_map_get_space(map);
1988 id = isl_map_identity(dim);
1990 is_subset = isl_map_is_subset(map, id);
1997 /* Check if the given map is single-valued.
2002 * and check if the result is a subset of the identity mapping.
2004 int isl_union_map_is_single_valued(__isl_keep isl_union_map *umap)
2006 isl_union_map *test;
2009 if (isl_union_map_n_map(umap) == 1) {
2011 umap = isl_union_map_copy(umap);
2012 map = isl_map_from_union_map(umap);
2013 sv = isl_map_is_single_valued(map);
2018 test = isl_union_map_reverse(isl_union_map_copy(umap));
2019 test = isl_union_map_apply_range(test, isl_union_map_copy(umap));
2021 sv = union_map_forall(test, &is_subset_of_identity);
2023 isl_union_map_free(test);
2028 int isl_union_map_is_injective(__isl_keep isl_union_map *umap)
2032 umap = isl_union_map_copy(umap);
2033 umap = isl_union_map_reverse(umap);
2034 in = isl_union_map_is_single_valued(umap);
2035 isl_union_map_free(umap);
2040 /* Represents a map that has a fixed value (v) for one of its
2042 * The map in this structure is not reference counted, so it
2043 * is only valid while the isl_union_map from which it was
2044 * obtained is still alive.
2046 struct isl_fixed_map {
2051 static struct isl_fixed_map *alloc_isl_fixed_map_array(isl_ctx *ctx,
2055 struct isl_fixed_map *v;
2057 v = isl_calloc_array(ctx, struct isl_fixed_map, n);
2060 for (i = 0; i < n; ++i)
2061 isl_int_init(v[i].v);
2065 static void free_isl_fixed_map_array(struct isl_fixed_map *v, int n)
2071 for (i = 0; i < n; ++i)
2072 isl_int_clear(v[i].v);
2076 /* Compare the "v" field of two isl_fixed_map structs.
2078 static int qsort_fixed_map_cmp(const void *p1, const void *p2)
2080 const struct isl_fixed_map *e1 = (const struct isl_fixed_map *) p1;
2081 const struct isl_fixed_map *e2 = (const struct isl_fixed_map *) p2;
2083 return isl_int_cmp(e1->v, e2->v);
2086 /* Internal data structure used while checking whether all maps
2087 * in a union_map have a fixed value for a given output dimension.
2088 * v is the list of maps, with the fixed value for the dimension
2089 * n is the number of maps considered so far
2090 * pos is the output dimension under investigation
2092 struct isl_fixed_dim_data {
2093 struct isl_fixed_map *v;
2098 static int fixed_at_pos(__isl_keep isl_map *map, void *user)
2100 struct isl_fixed_dim_data *data = user;
2102 data->v[data->n].map = map;
2103 return isl_map_plain_is_fixed(map, isl_dim_out, data->pos,
2104 &data->v[data->n++].v);
2107 static int plain_injective_on_range(__isl_take isl_union_map *umap,
2108 int first, int n_range);
2110 /* Given a list of the maps, with their fixed values at output dimension "pos",
2111 * check whether the ranges of the maps form an obvious partition.
2113 * We first sort the maps according to their fixed values.
2114 * If all maps have a different value, then we know the ranges form
2116 * Otherwise, we collect the maps with the same fixed value and
2117 * check whether each such collection is obviously injective
2118 * based on later dimensions.
2120 static int separates(struct isl_fixed_map *v, int n,
2121 __isl_take isl_space *dim, int pos, int n_range)
2128 qsort(v, n, sizeof(*v), &qsort_fixed_map_cmp);
2130 for (i = 0; i + 1 < n; ++i) {
2132 isl_union_map *part;
2135 for (j = i + 1; j < n; ++j)
2136 if (isl_int_ne(v[i].v, v[j].v))
2142 part = isl_union_map_alloc(isl_space_copy(dim), j - i);
2143 for (k = i; k < j; ++k)
2144 part = isl_union_map_add_map(part,
2145 isl_map_copy(v[k].map));
2147 injective = plain_injective_on_range(part, pos + 1, n_range);
2156 isl_space_free(dim);
2157 free_isl_fixed_map_array(v, n);
2160 isl_space_free(dim);
2161 free_isl_fixed_map_array(v, n);
2165 /* Check whether the maps in umap have obviously distinct ranges.
2166 * In particular, check for an output dimension in the range
2167 * [first,n_range) for which all maps have a fixed value
2168 * and then check if these values, possibly along with fixed values
2169 * at later dimensions, entail distinct ranges.
2171 static int plain_injective_on_range(__isl_take isl_union_map *umap,
2172 int first, int n_range)
2176 struct isl_fixed_dim_data data = { NULL };
2178 ctx = isl_union_map_get_ctx(umap);
2183 n = isl_union_map_n_map(umap);
2185 isl_union_map_free(umap);
2189 if (first >= n_range) {
2190 isl_union_map_free(umap);
2194 data.v = alloc_isl_fixed_map_array(ctx, n);
2198 for (data.pos = first; data.pos < n_range; ++data.pos) {
2204 fixed = union_map_forall_user(umap, &fixed_at_pos, &data);
2209 dim = isl_union_map_get_space(umap);
2210 injective = separates(data.v, n, dim, data.pos, n_range);
2211 isl_union_map_free(umap);
2215 free_isl_fixed_map_array(data.v, n);
2216 isl_union_map_free(umap);
2220 free_isl_fixed_map_array(data.v, n);
2221 isl_union_map_free(umap);
2225 /* Check whether the maps in umap that map to subsets of "ran"
2226 * have obviously distinct ranges.
2228 static int plain_injective_on_range_wrap(__isl_keep isl_set *ran, void *user)
2230 isl_union_map *umap = user;
2232 umap = isl_union_map_copy(umap);
2233 umap = isl_union_map_intersect_range(umap,
2234 isl_union_set_from_set(isl_set_copy(ran)));
2235 return plain_injective_on_range(umap, 0, isl_set_dim(ran, isl_dim_set));
2238 /* Check if the given union_map is obviously injective.
2240 * In particular, we first check if all individual maps are obviously
2241 * injective and then check if all the ranges of these maps are
2242 * obviously disjoint.
2244 int isl_union_map_plain_is_injective(__isl_keep isl_union_map *umap)
2247 isl_union_map *univ;
2250 in = union_map_forall(umap, &isl_map_plain_is_injective);
2256 univ = isl_union_map_universe(isl_union_map_copy(umap));
2257 ran = isl_union_map_range(univ);
2259 in = union_map_forall_user(ran, &plain_injective_on_range_wrap, umap);
2261 isl_union_set_free(ran);
2266 int isl_union_map_is_bijective(__isl_keep isl_union_map *umap)
2270 sv = isl_union_map_is_single_valued(umap);
2274 return isl_union_map_is_injective(umap);
2277 static int zip_entry(void **entry, void *user)
2279 isl_map *map = *entry;
2280 isl_union_map **res = user;
2282 if (!isl_map_can_zip(map))
2285 *res = isl_union_map_add_map(*res, isl_map_zip(isl_map_copy(map)));
2290 __isl_give isl_union_map *isl_union_map_zip(__isl_take isl_union_map *umap)
2292 return cond_un_op(umap, &zip_entry);
2295 static int curry_entry(void **entry, void *user)
2297 isl_map *map = *entry;
2298 isl_union_map **res = user;
2300 if (!isl_map_can_curry(map))
2303 *res = isl_union_map_add_map(*res, isl_map_curry(isl_map_copy(map)));
2308 /* Given a union map, take the maps of the form (A -> B) -> C and
2309 * return the union of the corresponding maps A -> (B -> C).
2311 __isl_give isl_union_map *isl_union_map_curry(__isl_take isl_union_map *umap)
2313 return cond_un_op(umap, &curry_entry);
2316 static int lift_entry(void **entry, void *user)
2318 isl_set *set = *entry;
2319 isl_union_set **res = user;
2321 *res = isl_union_set_add_set(*res, isl_set_lift(isl_set_copy(set)));
2326 __isl_give isl_union_set *isl_union_set_lift(__isl_take isl_union_set *uset)
2328 return cond_un_op(uset, &lift_entry);
2331 static int coefficients_entry(void **entry, void *user)
2333 isl_set *set = *entry;
2334 isl_union_set **res = user;
2336 set = isl_set_copy(set);
2337 set = isl_set_from_basic_set(isl_set_coefficients(set));
2338 *res = isl_union_set_add_set(*res, set);
2343 __isl_give isl_union_set *isl_union_set_coefficients(
2344 __isl_take isl_union_set *uset)
2353 ctx = isl_union_set_get_ctx(uset);
2354 dim = isl_space_set_alloc(ctx, 0, 0);
2355 res = isl_union_map_alloc(dim, uset->table.n);
2356 if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
2357 &coefficients_entry, &res) < 0)
2360 isl_union_set_free(uset);
2363 isl_union_set_free(uset);
2364 isl_union_set_free(res);
2368 static int solutions_entry(void **entry, void *user)
2370 isl_set *set = *entry;
2371 isl_union_set **res = user;
2373 set = isl_set_copy(set);
2374 set = isl_set_from_basic_set(isl_set_solutions(set));
2376 *res = isl_union_set_from_set(set);
2378 *res = isl_union_set_add_set(*res, set);
2386 __isl_give isl_union_set *isl_union_set_solutions(
2387 __isl_take isl_union_set *uset)
2389 isl_union_set *res = NULL;
2394 if (uset->table.n == 0) {
2395 res = isl_union_set_empty(isl_union_set_get_space(uset));
2396 isl_union_set_free(uset);
2400 if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
2401 &solutions_entry, &res) < 0)
2404 isl_union_set_free(uset);
2407 isl_union_set_free(uset);
2408 isl_union_set_free(res);