2 * Copyright 2010-2011 INRIA Saclay
4 * Use of this software is governed by the GNU LGPLv2.1 license
6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
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 struct isl_union_map_foreach_data
352 int (*fn)(__isl_take isl_map *map, void *user);
356 static int call_on_copy(void **entry, void *user)
358 isl_map *map = *entry;
359 struct isl_union_map_foreach_data *data;
360 data = (struct isl_union_map_foreach_data *)user;
362 return data->fn(isl_map_copy(map), data->user);
365 int isl_union_map_n_map(__isl_keep isl_union_map *umap)
367 return umap ? umap->table.n : 0;
370 int isl_union_set_n_set(__isl_keep isl_union_set *uset)
372 return uset ? uset->table.n : 0;
375 int isl_union_map_foreach_map(__isl_keep isl_union_map *umap,
376 int (*fn)(__isl_take isl_map *map, void *user), void *user)
378 struct isl_union_map_foreach_data data = { fn, user };
383 return isl_hash_table_foreach(umap->dim->ctx, &umap->table,
384 &call_on_copy, &data);
387 static int copy_map(void **entry, void *user)
389 isl_map *map = *entry;
390 isl_map **map_p = user;
392 *map_p = isl_map_copy(map);
397 __isl_give isl_map *isl_map_from_union_map(__isl_take isl_union_map *umap)
404 ctx = isl_union_map_get_ctx(umap);
405 if (umap->table.n != 1)
406 isl_die(ctx, isl_error_invalid,
407 "union map needs to contain elements in exactly "
408 "one space", return isl_union_map_free(umap));
410 isl_hash_table_foreach(ctx, &umap->table, ©_map, &map);
412 isl_union_map_free(umap);
417 __isl_give isl_set *isl_set_from_union_set(__isl_take isl_union_set *uset)
419 return isl_map_from_union_map(uset);
422 __isl_give isl_map *isl_union_map_extract_map(__isl_keep isl_union_map *umap,
423 __isl_take isl_space *dim)
426 struct isl_hash_table_entry *entry;
431 hash = isl_space_get_hash(dim);
432 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
435 return isl_map_empty(dim);
437 return isl_map_copy(entry->data);
443 __isl_give isl_set *isl_union_set_extract_set(__isl_keep isl_union_set *uset,
444 __isl_take isl_space *dim)
446 return (isl_set *)isl_union_map_extract_map(uset, dim);
449 /* Check if umap contains a map in the given space.
451 __isl_give int isl_union_map_contains(__isl_keep isl_union_map *umap,
452 __isl_keep isl_space *dim)
455 struct isl_hash_table_entry *entry;
460 hash = isl_space_get_hash(dim);
461 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
466 __isl_give int isl_union_set_contains(__isl_keep isl_union_set *uset,
467 __isl_keep isl_space *dim)
469 return isl_union_map_contains(uset, dim);
472 int isl_union_set_foreach_set(__isl_keep isl_union_set *uset,
473 int (*fn)(__isl_take isl_set *set, void *user), void *user)
475 return isl_union_map_foreach_map(uset,
476 (int(*)(__isl_take isl_map *, void*))fn, user);
479 struct isl_union_set_foreach_point_data {
480 int (*fn)(__isl_take isl_point *pnt, void *user);
484 static int foreach_point(__isl_take isl_set *set, void *user)
486 struct isl_union_set_foreach_point_data *data = user;
489 r = isl_set_foreach_point(set, data->fn, data->user);
495 int isl_union_set_foreach_point(__isl_keep isl_union_set *uset,
496 int (*fn)(__isl_take isl_point *pnt, void *user), void *user)
498 struct isl_union_set_foreach_point_data data = { fn, user };
499 return isl_union_set_foreach_set(uset, &foreach_point, &data);
502 struct isl_union_map_gen_bin_data {
503 isl_union_map *umap2;
507 static int subtract_entry(void **entry, void *user)
509 struct isl_union_map_gen_bin_data *data = user;
511 struct isl_hash_table_entry *entry2;
512 isl_map *map = *entry;
514 hash = isl_space_get_hash(map->dim);
515 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
516 hash, &has_dim, map->dim, 0);
517 map = isl_map_copy(map);
520 map = isl_map_subtract(map, isl_map_copy(entry2->data));
522 empty = isl_map_is_empty(map);
532 data->res = isl_union_map_add_map(data->res, map);
537 static __isl_give isl_union_map *gen_bin_op(__isl_take isl_union_map *umap1,
538 __isl_take isl_union_map *umap2, int (*fn)(void **, void *))
540 struct isl_union_map_gen_bin_data data = { NULL, NULL };
542 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
543 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
545 if (!umap1 || !umap2)
549 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
551 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
555 isl_union_map_free(umap1);
556 isl_union_map_free(umap2);
559 isl_union_map_free(umap1);
560 isl_union_map_free(umap2);
561 isl_union_map_free(data.res);
565 __isl_give isl_union_map *isl_union_map_subtract(
566 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
568 return gen_bin_op(umap1, umap2, &subtract_entry);
571 __isl_give isl_union_set *isl_union_set_subtract(
572 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
574 return isl_union_map_subtract(uset1, uset2);
577 struct isl_union_map_gen_bin_set_data {
582 static int intersect_params_entry(void **entry, void *user)
584 struct isl_union_map_gen_bin_set_data *data = user;
585 isl_map *map = *entry;
588 map = isl_map_copy(map);
589 map = isl_map_intersect_params(map, isl_set_copy(data->set));
591 empty = isl_map_is_empty(map);
597 data->res = isl_union_map_add_map(data->res, map);
602 static __isl_give isl_union_map *gen_bin_set_op(__isl_take isl_union_map *umap,
603 __isl_take isl_set *set, int (*fn)(void **, void *))
605 struct isl_union_map_gen_bin_set_data data = { NULL, NULL };
607 umap = isl_union_map_align_params(umap, isl_set_get_space(set));
608 set = isl_set_align_params(set, isl_union_map_get_space(umap));
614 data.res = isl_union_map_alloc(isl_space_copy(umap->dim),
616 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
620 isl_union_map_free(umap);
624 isl_union_map_free(umap);
626 isl_union_map_free(data.res);
630 __isl_give isl_union_map *isl_union_map_intersect_params(
631 __isl_take isl_union_map *umap, __isl_take isl_set *set)
633 return gen_bin_set_op(umap, set, &intersect_params_entry);
636 __isl_give isl_union_set *isl_union_set_intersect_params(
637 __isl_take isl_union_set *uset, __isl_take isl_set *set)
639 return isl_union_map_intersect_params(uset, set);
642 static __isl_give isl_union_map *union_map_intersect_params(
643 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
645 return isl_union_map_intersect_params(umap,
646 isl_set_from_union_set(uset));
649 static __isl_give isl_union_map *union_map_gist_params(
650 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
652 return isl_union_map_gist_params(umap, isl_set_from_union_set(uset));
655 struct isl_union_map_match_bin_data {
656 isl_union_map *umap2;
658 __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*);
661 static int match_bin_entry(void **entry, void *user)
663 struct isl_union_map_match_bin_data *data = user;
665 struct isl_hash_table_entry *entry2;
666 isl_map *map = *entry;
669 hash = isl_space_get_hash(map->dim);
670 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
671 hash, &has_dim, map->dim, 0);
675 map = isl_map_copy(map);
676 map = data->fn(map, isl_map_copy(entry2->data));
678 empty = isl_map_is_empty(map);
688 data->res = isl_union_map_add_map(data->res, map);
693 static __isl_give isl_union_map *match_bin_op(__isl_take isl_union_map *umap1,
694 __isl_take isl_union_map *umap2,
695 __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*))
697 struct isl_union_map_match_bin_data data = { NULL, NULL, fn };
699 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
700 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
702 if (!umap1 || !umap2)
706 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
708 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
709 &match_bin_entry, &data) < 0)
712 isl_union_map_free(umap1);
713 isl_union_map_free(umap2);
716 isl_union_map_free(umap1);
717 isl_union_map_free(umap2);
718 isl_union_map_free(data.res);
722 __isl_give isl_union_map *isl_union_map_intersect(
723 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
725 return match_bin_op(umap1, umap2, &isl_map_intersect);
728 /* Compute the intersection of the two union_sets.
729 * As a special case, if exactly one of the two union_sets
730 * is a parameter domain, then intersect the parameter domain
731 * of the other one with this set.
733 __isl_give isl_union_set *isl_union_set_intersect(
734 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
738 p1 = isl_union_set_is_params(uset1);
739 p2 = isl_union_set_is_params(uset2);
740 if (p1 < 0 || p2 < 0)
743 return union_map_intersect_params(uset1, uset2);
745 return union_map_intersect_params(uset2, uset1);
746 return isl_union_map_intersect(uset1, uset2);
748 isl_union_set_free(uset1);
749 isl_union_set_free(uset2);
753 static int gist_params_entry(void **entry, void *user)
755 struct isl_union_map_gen_bin_set_data *data = user;
756 isl_map *map = *entry;
759 map = isl_map_copy(map);
760 map = isl_map_gist_params(map, isl_set_copy(data->set));
762 empty = isl_map_is_empty(map);
768 data->res = isl_union_map_add_map(data->res, map);
773 __isl_give isl_union_map *isl_union_map_gist_params(
774 __isl_take isl_union_map *umap, __isl_take isl_set *set)
776 return gen_bin_set_op(umap, set, &gist_params_entry);
779 __isl_give isl_union_set *isl_union_set_gist_params(
780 __isl_take isl_union_set *uset, __isl_take isl_set *set)
782 return isl_union_map_gist_params(uset, set);
785 __isl_give isl_union_map *isl_union_map_gist(__isl_take isl_union_map *umap,
786 __isl_take isl_union_map *context)
788 return match_bin_op(umap, context, &isl_map_gist);
791 __isl_give isl_union_set *isl_union_set_gist(__isl_take isl_union_set *uset,
792 __isl_take isl_union_set *context)
794 if (isl_union_set_is_params(context))
795 return union_map_gist_params(uset, context);
796 return isl_union_map_gist(uset, context);
799 static __isl_give isl_map *lex_le_set(__isl_take isl_map *set1,
800 __isl_take isl_map *set2)
802 return isl_set_lex_le_set((isl_set *)set1, (isl_set *)set2);
805 static __isl_give isl_map *lex_lt_set(__isl_take isl_map *set1,
806 __isl_take isl_map *set2)
808 return isl_set_lex_lt_set((isl_set *)set1, (isl_set *)set2);
811 __isl_give isl_union_map *isl_union_set_lex_lt_union_set(
812 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
814 return match_bin_op(uset1, uset2, &lex_lt_set);
817 __isl_give isl_union_map *isl_union_set_lex_le_union_set(
818 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
820 return match_bin_op(uset1, uset2, &lex_le_set);
823 __isl_give isl_union_map *isl_union_set_lex_gt_union_set(
824 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
826 return isl_union_map_reverse(isl_union_set_lex_lt_union_set(uset2, uset1));
829 __isl_give isl_union_map *isl_union_set_lex_ge_union_set(
830 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
832 return isl_union_map_reverse(isl_union_set_lex_le_union_set(uset2, uset1));
835 __isl_give isl_union_map *isl_union_map_lex_gt_union_map(
836 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
838 return isl_union_map_reverse(isl_union_map_lex_lt_union_map(umap2, umap1));
841 __isl_give isl_union_map *isl_union_map_lex_ge_union_map(
842 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
844 return isl_union_map_reverse(isl_union_map_lex_le_union_map(umap2, umap1));
847 static int intersect_domain_entry(void **entry, void *user)
849 struct isl_union_map_gen_bin_data *data = user;
851 struct isl_hash_table_entry *entry2;
853 isl_map *map = *entry;
856 dim = isl_map_get_space(map);
857 dim = isl_space_domain(dim);
858 hash = isl_space_get_hash(dim);
859 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
860 hash, &has_dim, dim, 0);
865 map = isl_map_copy(map);
866 map = isl_map_intersect_domain(map, isl_set_copy(entry2->data));
868 empty = isl_map_is_empty(map);
878 data->res = isl_union_map_add_map(data->res, map);
883 /* Intersect the domain of "umap" with "uset".
884 * If "uset" is a parameters domain, then intersect the parameter
885 * domain of "umap" with this set.
887 __isl_give isl_union_map *isl_union_map_intersect_domain(
888 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
890 if (isl_union_set_is_params(uset))
891 return union_map_intersect_params(umap, uset);
892 return gen_bin_op(umap, uset, &intersect_domain_entry);
895 static int gist_domain_entry(void **entry, void *user)
897 struct isl_union_map_gen_bin_data *data = user;
899 struct isl_hash_table_entry *entry2;
901 isl_map *map = *entry;
904 dim = isl_map_get_space(map);
905 dim = isl_space_domain(dim);
906 hash = isl_space_get_hash(dim);
907 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
908 hash, &has_dim, dim, 0);
913 map = isl_map_copy(map);
914 map = isl_map_gist_domain(map, isl_set_copy(entry2->data));
916 empty = isl_map_is_empty(map);
922 data->res = isl_union_map_add_map(data->res, map);
927 /* Compute the gist of "umap" with respect to the domain "uset".
928 * If "uset" is a parameters domain, then compute the gist
929 * with respect to this parameter domain.
931 __isl_give isl_union_map *isl_union_map_gist_domain(
932 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
934 if (isl_union_set_is_params(uset))
935 return union_map_gist_params(umap, uset);
936 return gen_bin_op(umap, uset, &gist_domain_entry);
939 static int intersect_range_entry(void **entry, void *user)
941 struct isl_union_map_gen_bin_data *data = user;
943 struct isl_hash_table_entry *entry2;
945 isl_map *map = *entry;
948 dim = isl_map_get_space(map);
949 dim = isl_space_range(dim);
950 hash = isl_space_get_hash(dim);
951 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
952 hash, &has_dim, dim, 0);
957 map = isl_map_copy(map);
958 map = isl_map_intersect_range(map, isl_set_copy(entry2->data));
960 empty = isl_map_is_empty(map);
970 data->res = isl_union_map_add_map(data->res, map);
975 __isl_give isl_union_map *isl_union_map_intersect_range(
976 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
978 return gen_bin_op(umap, uset, &intersect_range_entry);
981 struct isl_union_map_bin_data {
982 isl_union_map *umap2;
985 int (*fn)(void **entry, void *user);
988 static int apply_range_entry(void **entry, void *user)
990 struct isl_union_map_bin_data *data = user;
991 isl_map *map2 = *entry;
994 if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
995 map2->dim, isl_dim_in))
998 map2 = isl_map_apply_range(isl_map_copy(data->map), isl_map_copy(map2));
1000 empty = isl_map_is_empty(map2);
1010 data->res = isl_union_map_add_map(data->res, map2);
1015 static int bin_entry(void **entry, void *user)
1017 struct isl_union_map_bin_data *data = user;
1018 isl_map *map = *entry;
1021 if (isl_hash_table_foreach(data->umap2->dim->ctx, &data->umap2->table,
1022 data->fn, data) < 0)
1028 static __isl_give isl_union_map *bin_op(__isl_take isl_union_map *umap1,
1029 __isl_take isl_union_map *umap2, int (*fn)(void **entry, void *user))
1031 struct isl_union_map_bin_data data = { NULL, NULL, NULL, fn };
1033 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
1034 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
1036 if (!umap1 || !umap2)
1040 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
1042 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1043 &bin_entry, &data) < 0)
1046 isl_union_map_free(umap1);
1047 isl_union_map_free(umap2);
1050 isl_union_map_free(umap1);
1051 isl_union_map_free(umap2);
1052 isl_union_map_free(data.res);
1056 __isl_give isl_union_map *isl_union_map_apply_range(
1057 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1059 return bin_op(umap1, umap2, &apply_range_entry);
1062 __isl_give isl_union_map *isl_union_map_apply_domain(
1063 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1065 umap1 = isl_union_map_reverse(umap1);
1066 umap1 = isl_union_map_apply_range(umap1, umap2);
1067 return isl_union_map_reverse(umap1);
1070 __isl_give isl_union_set *isl_union_set_apply(
1071 __isl_take isl_union_set *uset, __isl_take isl_union_map *umap)
1073 return isl_union_map_apply_range(uset, umap);
1076 static int map_lex_lt_entry(void **entry, void *user)
1078 struct isl_union_map_bin_data *data = user;
1079 isl_map *map2 = *entry;
1081 if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1082 map2->dim, isl_dim_out))
1085 map2 = isl_map_lex_lt_map(isl_map_copy(data->map), isl_map_copy(map2));
1087 data->res = isl_union_map_add_map(data->res, map2);
1092 __isl_give isl_union_map *isl_union_map_lex_lt_union_map(
1093 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1095 return bin_op(umap1, umap2, &map_lex_lt_entry);
1098 static int map_lex_le_entry(void **entry, void *user)
1100 struct isl_union_map_bin_data *data = user;
1101 isl_map *map2 = *entry;
1103 if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1104 map2->dim, isl_dim_out))
1107 map2 = isl_map_lex_le_map(isl_map_copy(data->map), isl_map_copy(map2));
1109 data->res = isl_union_map_add_map(data->res, map2);
1114 __isl_give isl_union_map *isl_union_map_lex_le_union_map(
1115 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1117 return bin_op(umap1, umap2, &map_lex_le_entry);
1120 static int product_entry(void **entry, void *user)
1122 struct isl_union_map_bin_data *data = user;
1123 isl_map *map2 = *entry;
1125 map2 = isl_map_product(isl_map_copy(data->map), isl_map_copy(map2));
1127 data->res = isl_union_map_add_map(data->res, map2);
1132 __isl_give isl_union_map *isl_union_map_product(__isl_take isl_union_map *umap1,
1133 __isl_take isl_union_map *umap2)
1135 return bin_op(umap1, umap2, &product_entry);
1138 static int set_product_entry(void **entry, void *user)
1140 struct isl_union_map_bin_data *data = user;
1141 isl_set *set2 = *entry;
1143 set2 = isl_set_product(isl_set_copy(data->map), isl_set_copy(set2));
1145 data->res = isl_union_set_add_set(data->res, set2);
1150 __isl_give isl_union_set *isl_union_set_product(__isl_take isl_union_set *uset1,
1151 __isl_take isl_union_set *uset2)
1153 return bin_op(uset1, uset2, &set_product_entry);
1156 static int range_product_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_in,
1162 map2->dim, isl_dim_in))
1165 map2 = isl_map_range_product(isl_map_copy(data->map),
1166 isl_map_copy(map2));
1168 data->res = isl_union_map_add_map(data->res, map2);
1173 __isl_give isl_union_map *isl_union_map_range_product(
1174 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1176 return bin_op(umap1, umap2, &range_product_entry);
1179 static int flat_range_product_entry(void **entry, void *user)
1181 struct isl_union_map_bin_data *data = user;
1182 isl_map *map2 = *entry;
1184 if (!isl_space_tuple_match(data->map->dim, isl_dim_in,
1185 map2->dim, isl_dim_in))
1188 map2 = isl_map_flat_range_product(isl_map_copy(data->map),
1189 isl_map_copy(map2));
1191 data->res = isl_union_map_add_map(data->res, map2);
1196 __isl_give isl_union_map *isl_union_map_flat_range_product(
1197 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1199 return bin_op(umap1, umap2, &flat_range_product_entry);
1202 static __isl_give isl_union_set *cond_un_op(__isl_take isl_union_map *umap,
1203 int (*fn)(void **, void *))
1210 res = isl_union_map_alloc(isl_space_copy(umap->dim), umap->table.n);
1211 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, &res) < 0)
1214 isl_union_map_free(umap);
1217 isl_union_map_free(umap);
1218 isl_union_set_free(res);
1222 static int from_range_entry(void **entry, void *user)
1224 isl_map *set = *entry;
1225 isl_union_set **res = user;
1227 *res = isl_union_map_add_map(*res,
1228 isl_map_from_range(isl_set_copy(set)));
1233 __isl_give isl_union_map *isl_union_map_from_range(
1234 __isl_take isl_union_set *uset)
1236 return cond_un_op(uset, &from_range_entry);
1239 __isl_give isl_union_map *isl_union_map_from_domain(
1240 __isl_take isl_union_set *uset)
1242 return isl_union_map_reverse(isl_union_map_from_range(uset));
1245 __isl_give isl_union_map *isl_union_map_from_domain_and_range(
1246 __isl_take isl_union_set *domain, __isl_take isl_union_set *range)
1248 return isl_union_map_apply_range(isl_union_map_from_domain(domain),
1249 isl_union_map_from_range(range));
1252 static __isl_give isl_union_map *un_op(__isl_take isl_union_map *umap,
1253 int (*fn)(void **, void *))
1255 umap = isl_union_map_cow(umap);
1259 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, NULL) < 0)
1264 isl_union_map_free(umap);
1268 static int affine_entry(void **entry, void *user)
1270 isl_map **map = (isl_map **)entry;
1272 *map = isl_map_from_basic_map(isl_map_affine_hull(*map));
1274 return *map ? 0 : -1;
1277 __isl_give isl_union_map *isl_union_map_affine_hull(
1278 __isl_take isl_union_map *umap)
1280 return un_op(umap, &affine_entry);
1283 __isl_give isl_union_set *isl_union_set_affine_hull(
1284 __isl_take isl_union_set *uset)
1286 return isl_union_map_affine_hull(uset);
1289 static int polyhedral_entry(void **entry, void *user)
1291 isl_map **map = (isl_map **)entry;
1293 *map = isl_map_from_basic_map(isl_map_polyhedral_hull(*map));
1295 return *map ? 0 : -1;
1298 __isl_give isl_union_map *isl_union_map_polyhedral_hull(
1299 __isl_take isl_union_map *umap)
1301 return un_op(umap, &polyhedral_entry);
1304 __isl_give isl_union_set *isl_union_set_polyhedral_hull(
1305 __isl_take isl_union_set *uset)
1307 return isl_union_map_polyhedral_hull(uset);
1310 static int simple_entry(void **entry, void *user)
1312 isl_map **map = (isl_map **)entry;
1314 *map = isl_map_from_basic_map(isl_map_simple_hull(*map));
1316 return *map ? 0 : -1;
1319 __isl_give isl_union_map *isl_union_map_simple_hull(
1320 __isl_take isl_union_map *umap)
1322 return un_op(umap, &simple_entry);
1325 __isl_give isl_union_set *isl_union_set_simple_hull(
1326 __isl_take isl_union_set *uset)
1328 return isl_union_map_simple_hull(uset);
1331 static int inplace_entry(void **entry, void *user)
1333 __isl_give isl_map *(*fn)(__isl_take isl_map *);
1334 isl_map **map = (isl_map **)entry;
1337 fn = *(__isl_give isl_map *(**)(__isl_take isl_map *)) user;
1338 copy = fn(isl_map_copy(*map));
1348 static __isl_give isl_union_map *inplace(__isl_take isl_union_map *umap,
1349 __isl_give isl_map *(*fn)(__isl_take isl_map *))
1354 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1355 &inplace_entry, &fn) < 0)
1360 isl_union_map_free(umap);
1364 __isl_give isl_union_map *isl_union_map_coalesce(
1365 __isl_take isl_union_map *umap)
1367 return inplace(umap, &isl_map_coalesce);
1370 __isl_give isl_union_set *isl_union_set_coalesce(
1371 __isl_take isl_union_set *uset)
1373 return isl_union_map_coalesce(uset);
1376 __isl_give isl_union_map *isl_union_map_detect_equalities(
1377 __isl_take isl_union_map *umap)
1379 return inplace(umap, &isl_map_detect_equalities);
1382 __isl_give isl_union_set *isl_union_set_detect_equalities(
1383 __isl_take isl_union_set *uset)
1385 return isl_union_map_detect_equalities(uset);
1388 __isl_give isl_union_map *isl_union_map_compute_divs(
1389 __isl_take isl_union_map *umap)
1391 return inplace(umap, &isl_map_compute_divs);
1394 __isl_give isl_union_set *isl_union_set_compute_divs(
1395 __isl_take isl_union_set *uset)
1397 return isl_union_map_compute_divs(uset);
1400 static int lexmin_entry(void **entry, void *user)
1402 isl_map **map = (isl_map **)entry;
1404 *map = isl_map_lexmin(*map);
1406 return *map ? 0 : -1;
1409 __isl_give isl_union_map *isl_union_map_lexmin(
1410 __isl_take isl_union_map *umap)
1412 return un_op(umap, &lexmin_entry);
1415 __isl_give isl_union_set *isl_union_set_lexmin(
1416 __isl_take isl_union_set *uset)
1418 return isl_union_map_lexmin(uset);
1421 static int lexmax_entry(void **entry, void *user)
1423 isl_map **map = (isl_map **)entry;
1425 *map = isl_map_lexmax(*map);
1427 return *map ? 0 : -1;
1430 __isl_give isl_union_map *isl_union_map_lexmax(
1431 __isl_take isl_union_map *umap)
1433 return un_op(umap, &lexmax_entry);
1436 __isl_give isl_union_set *isl_union_set_lexmax(
1437 __isl_take isl_union_set *uset)
1439 return isl_union_map_lexmax(uset);
1442 static int universe_entry(void **entry, void *user)
1444 isl_map *map = *entry;
1445 isl_union_map **res = user;
1447 map = isl_map_universe(isl_map_get_space(map));
1448 *res = isl_union_map_add_map(*res, map);
1453 __isl_give isl_union_map *isl_union_map_universe(__isl_take isl_union_map *umap)
1455 return cond_un_op(umap, &universe_entry);
1458 __isl_give isl_union_set *isl_union_set_universe(__isl_take isl_union_set *uset)
1460 return isl_union_map_universe(uset);
1463 static int reverse_entry(void **entry, void *user)
1465 isl_map *map = *entry;
1466 isl_union_map **res = user;
1468 *res = isl_union_map_add_map(*res, isl_map_reverse(isl_map_copy(map)));
1473 __isl_give isl_union_map *isl_union_map_reverse(__isl_take isl_union_map *umap)
1475 return cond_un_op(umap, &reverse_entry);
1478 static int params_entry(void **entry, void *user)
1480 isl_map *map = *entry;
1481 isl_union_set **res = user;
1483 *res = isl_union_set_add_set(*res, isl_map_params(isl_map_copy(map)));
1488 /* Compute the parameter domain of the given union map.
1490 __isl_give isl_set *isl_union_map_params(__isl_take isl_union_map *umap)
1494 empty = isl_union_map_is_empty(umap);
1496 return isl_union_map_free(umap);
1498 return isl_set_empty(isl_union_map_get_space(umap));
1499 return isl_set_from_union_set(cond_un_op(umap, ¶ms_entry));
1502 /* Compute the parameter domain of the given union set.
1504 __isl_give isl_set *isl_union_set_params(__isl_take isl_union_set *uset)
1506 return isl_union_map_params(uset);
1509 static int domain_entry(void **entry, void *user)
1511 isl_map *map = *entry;
1512 isl_union_set **res = user;
1514 *res = isl_union_set_add_set(*res, isl_map_domain(isl_map_copy(map)));
1519 __isl_give isl_union_set *isl_union_map_domain(__isl_take isl_union_map *umap)
1521 return cond_un_op(umap, &domain_entry);
1524 static int range_entry(void **entry, void *user)
1526 isl_map *map = *entry;
1527 isl_union_set **res = user;
1529 *res = isl_union_set_add_set(*res, isl_map_range(isl_map_copy(map)));
1534 __isl_give isl_union_set *isl_union_map_range(__isl_take isl_union_map *umap)
1536 return cond_un_op(umap, &range_entry);
1539 static int domain_map_entry(void **entry, void *user)
1541 isl_map *map = *entry;
1542 isl_union_set **res = user;
1544 *res = isl_union_map_add_map(*res,
1545 isl_map_domain_map(isl_map_copy(map)));
1550 __isl_give isl_union_map *isl_union_map_domain_map(
1551 __isl_take isl_union_map *umap)
1553 return cond_un_op(umap, &domain_map_entry);
1556 static int range_map_entry(void **entry, void *user)
1558 isl_map *map = *entry;
1559 isl_union_set **res = user;
1561 *res = isl_union_map_add_map(*res,
1562 isl_map_range_map(isl_map_copy(map)));
1567 __isl_give isl_union_map *isl_union_map_range_map(
1568 __isl_take isl_union_map *umap)
1570 return cond_un_op(umap, &range_map_entry);
1573 static int deltas_entry(void **entry, void *user)
1575 isl_map *map = *entry;
1576 isl_union_set **res = user;
1578 if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1581 *res = isl_union_set_add_set(*res, isl_map_deltas(isl_map_copy(map)));
1586 __isl_give isl_union_set *isl_union_map_deltas(__isl_take isl_union_map *umap)
1588 return cond_un_op(umap, &deltas_entry);
1591 static int deltas_map_entry(void **entry, void *user)
1593 isl_map *map = *entry;
1594 isl_union_map **res = user;
1596 if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1599 *res = isl_union_map_add_map(*res,
1600 isl_map_deltas_map(isl_map_copy(map)));
1605 __isl_give isl_union_map *isl_union_map_deltas_map(
1606 __isl_take isl_union_map *umap)
1608 return cond_un_op(umap, &deltas_map_entry);
1611 static int identity_entry(void **entry, void *user)
1613 isl_set *set = *entry;
1614 isl_union_map **res = user;
1616 *res = isl_union_map_add_map(*res, isl_set_identity(isl_set_copy(set)));
1621 __isl_give isl_union_map *isl_union_set_identity(__isl_take isl_union_set *uset)
1623 return cond_un_op(uset, &identity_entry);
1626 static int unwrap_entry(void **entry, void *user)
1628 isl_set *set = *entry;
1629 isl_union_set **res = user;
1631 if (!isl_set_is_wrapping(set))
1634 *res = isl_union_map_add_map(*res, isl_set_unwrap(isl_set_copy(set)));
1639 __isl_give isl_union_map *isl_union_set_unwrap(__isl_take isl_union_set *uset)
1641 return cond_un_op(uset, &unwrap_entry);
1644 static int wrap_entry(void **entry, void *user)
1646 isl_map *map = *entry;
1647 isl_union_set **res = user;
1649 *res = isl_union_set_add_set(*res, isl_map_wrap(isl_map_copy(map)));
1654 __isl_give isl_union_set *isl_union_map_wrap(__isl_take isl_union_map *umap)
1656 return cond_un_op(umap, &wrap_entry);
1659 struct isl_union_map_is_subset_data {
1660 isl_union_map *umap2;
1664 static int is_subset_entry(void **entry, void *user)
1666 struct isl_union_map_is_subset_data *data = user;
1668 struct isl_hash_table_entry *entry2;
1669 isl_map *map = *entry;
1671 hash = isl_space_get_hash(map->dim);
1672 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1673 hash, &has_dim, map->dim, 0);
1675 data->is_subset = 0;
1679 data->is_subset = isl_map_is_subset(map, entry2->data);
1680 if (data->is_subset < 0 || !data->is_subset)
1686 int isl_union_map_is_subset(__isl_keep isl_union_map *umap1,
1687 __isl_keep isl_union_map *umap2)
1689 struct isl_union_map_is_subset_data data = { NULL, 1 };
1691 umap1 = isl_union_map_copy(umap1);
1692 umap2 = isl_union_map_copy(umap2);
1693 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
1694 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
1696 if (!umap1 || !umap2)
1700 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1701 &is_subset_entry, &data) < 0 &&
1705 isl_union_map_free(umap1);
1706 isl_union_map_free(umap2);
1708 return data.is_subset;
1710 isl_union_map_free(umap1);
1711 isl_union_map_free(umap2);
1715 int isl_union_set_is_subset(__isl_keep isl_union_set *uset1,
1716 __isl_keep isl_union_set *uset2)
1718 return isl_union_map_is_subset(uset1, uset2);
1721 int isl_union_map_is_equal(__isl_keep isl_union_map *umap1,
1722 __isl_keep isl_union_map *umap2)
1726 if (!umap1 || !umap2)
1728 is_subset = isl_union_map_is_subset(umap1, umap2);
1731 is_subset = isl_union_map_is_subset(umap2, umap1);
1735 int isl_union_set_is_equal(__isl_keep isl_union_set *uset1,
1736 __isl_keep isl_union_set *uset2)
1738 return isl_union_map_is_equal(uset1, uset2);
1741 int isl_union_map_is_strict_subset(__isl_keep isl_union_map *umap1,
1742 __isl_keep isl_union_map *umap2)
1746 if (!umap1 || !umap2)
1748 is_subset = isl_union_map_is_subset(umap1, umap2);
1751 is_subset = isl_union_map_is_subset(umap2, umap1);
1752 if (is_subset == -1)
1757 int isl_union_set_is_strict_subset(__isl_keep isl_union_set *uset1,
1758 __isl_keep isl_union_set *uset2)
1760 return isl_union_map_is_strict_subset(uset1, uset2);
1763 static int sample_entry(void **entry, void *user)
1765 isl_basic_map **sample = (isl_basic_map **)user;
1766 isl_map *map = *entry;
1768 *sample = isl_map_sample(isl_map_copy(map));
1771 if (!isl_basic_map_plain_is_empty(*sample))
1776 __isl_give isl_basic_map *isl_union_map_sample(__isl_take isl_union_map *umap)
1778 isl_basic_map *sample = NULL;
1783 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1784 &sample_entry, &sample) < 0 &&
1789 sample = isl_basic_map_empty(isl_union_map_get_space(umap));
1791 isl_union_map_free(umap);
1795 isl_union_map_free(umap);
1799 __isl_give isl_basic_set *isl_union_set_sample(__isl_take isl_union_set *uset)
1801 return (isl_basic_set *)isl_union_map_sample(uset);
1804 struct isl_forall_data {
1806 int (*fn)(__isl_keep isl_map *map);
1809 static int forall_entry(void **entry, void *user)
1811 struct isl_forall_data *data = user;
1812 isl_map *map = *entry;
1814 data->res = data->fn(map);
1824 static int union_map_forall(__isl_keep isl_union_map *umap,
1825 int (*fn)(__isl_keep isl_map *map))
1827 struct isl_forall_data data = { 1, fn };
1832 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1833 &forall_entry, &data) < 0 && data.res)
1839 struct isl_forall_user_data {
1841 int (*fn)(__isl_keep isl_map *map, void *user);
1845 static int forall_user_entry(void **entry, void *user)
1847 struct isl_forall_user_data *data = user;
1848 isl_map *map = *entry;
1850 data->res = data->fn(map, data->user);
1860 /* Check if fn(map, user) returns true for all maps "map" in umap.
1862 static int union_map_forall_user(__isl_keep isl_union_map *umap,
1863 int (*fn)(__isl_keep isl_map *map, void *user), void *user)
1865 struct isl_forall_user_data data = { 1, fn, user };
1870 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1871 &forall_user_entry, &data) < 0 && data.res)
1877 int isl_union_map_is_empty(__isl_keep isl_union_map *umap)
1879 return union_map_forall(umap, &isl_map_is_empty);
1882 int isl_union_set_is_empty(__isl_keep isl_union_set *uset)
1884 return isl_union_map_is_empty(uset);
1887 static int is_subset_of_identity(__isl_keep isl_map *map)
1896 if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1899 dim = isl_map_get_space(map);
1900 id = isl_map_identity(dim);
1902 is_subset = isl_map_is_subset(map, id);
1909 /* Check if the given map is single-valued.
1914 * and check if the result is a subset of the identity mapping.
1916 int isl_union_map_is_single_valued(__isl_keep isl_union_map *umap)
1918 isl_union_map *test;
1921 if (isl_union_map_n_map(umap) == 1) {
1923 umap = isl_union_map_copy(umap);
1924 map = isl_map_from_union_map(umap);
1925 sv = isl_map_is_single_valued(map);
1930 test = isl_union_map_reverse(isl_union_map_copy(umap));
1931 test = isl_union_map_apply_range(test, isl_union_map_copy(umap));
1933 sv = union_map_forall(test, &is_subset_of_identity);
1935 isl_union_map_free(test);
1940 int isl_union_map_is_injective(__isl_keep isl_union_map *umap)
1944 umap = isl_union_map_copy(umap);
1945 umap = isl_union_map_reverse(umap);
1946 in = isl_union_map_is_single_valued(umap);
1947 isl_union_map_free(umap);
1952 /* Represents a map that has a fixed value (v) for one of its
1954 * The map in this structure is not reference counted, so it
1955 * is only valid while the isl_union_map from which it was
1956 * obtained is still alive.
1958 struct isl_fixed_map {
1963 static struct isl_fixed_map *alloc_isl_fixed_map_array(isl_ctx *ctx,
1967 struct isl_fixed_map *v;
1969 v = isl_calloc_array(ctx, struct isl_fixed_map, n);
1972 for (i = 0; i < n; ++i)
1973 isl_int_init(v[i].v);
1977 static void free_isl_fixed_map_array(struct isl_fixed_map *v, int n)
1983 for (i = 0; i < n; ++i)
1984 isl_int_clear(v[i].v);
1988 /* Compare the "v" field of two isl_fixed_map structs.
1990 static int qsort_fixed_map_cmp(const void *p1, const void *p2)
1992 const struct isl_fixed_map *e1 = (const struct isl_fixed_map *) p1;
1993 const struct isl_fixed_map *e2 = (const struct isl_fixed_map *) p2;
1995 return isl_int_cmp(e1->v, e2->v);
1998 /* Internal data structure used while checking whether all maps
1999 * in a union_map have a fixed value for a given output dimension.
2000 * v is the list of maps, with the fixed value for the dimension
2001 * n is the number of maps considered so far
2002 * pos is the output dimension under investigation
2004 struct isl_fixed_dim_data {
2005 struct isl_fixed_map *v;
2010 static int fixed_at_pos(__isl_keep isl_map *map, void *user)
2012 struct isl_fixed_dim_data *data = user;
2014 data->v[data->n].map = map;
2015 return isl_map_plain_is_fixed(map, isl_dim_out, data->pos,
2016 &data->v[data->n++].v);
2019 static int plain_injective_on_range(__isl_take isl_union_map *umap,
2020 int first, int n_range);
2022 /* Given a list of the maps, with their fixed values at output dimension "pos",
2023 * check whether the ranges of the maps form an obvious partition.
2025 * We first sort the maps according to their fixed values.
2026 * If all maps have a different value, then we know the ranges form
2028 * Otherwise, we collect the maps with the same fixed value and
2029 * check whether each such collection is obviously injective
2030 * based on later dimensions.
2032 static int separates(struct isl_fixed_map *v, int n,
2033 __isl_take isl_space *dim, int pos, int n_range)
2040 qsort(v, n, sizeof(*v), &qsort_fixed_map_cmp);
2042 for (i = 0; i + 1 < n; ++i) {
2044 isl_union_map *part;
2047 for (j = i + 1; j < n; ++j)
2048 if (isl_int_ne(v[i].v, v[j].v))
2054 part = isl_union_map_alloc(isl_space_copy(dim), j - i);
2055 for (k = i; k < j; ++k)
2056 part = isl_union_map_add_map(part,
2057 isl_map_copy(v[k].map));
2059 injective = plain_injective_on_range(part, pos + 1, n_range);
2068 isl_space_free(dim);
2069 free_isl_fixed_map_array(v, n);
2072 isl_space_free(dim);
2073 free_isl_fixed_map_array(v, n);
2077 /* Check whether the maps in umap have obviously distinct ranges.
2078 * In particular, check for an output dimension in the range
2079 * [first,n_range) for which all maps have a fixed value
2080 * and then check if these values, possibly along with fixed values
2081 * at later dimensions, entail distinct ranges.
2083 static int plain_injective_on_range(__isl_take isl_union_map *umap,
2084 int first, int n_range)
2088 struct isl_fixed_dim_data data = { NULL };
2090 ctx = isl_union_map_get_ctx(umap);
2095 n = isl_union_map_n_map(umap);
2097 isl_union_map_free(umap);
2101 if (first >= n_range) {
2102 isl_union_map_free(umap);
2106 data.v = alloc_isl_fixed_map_array(ctx, n);
2110 for (data.pos = first; data.pos < n_range; ++data.pos) {
2116 fixed = union_map_forall_user(umap, &fixed_at_pos, &data);
2121 dim = isl_union_map_get_space(umap);
2122 injective = separates(data.v, n, dim, data.pos, n_range);
2123 isl_union_map_free(umap);
2127 free_isl_fixed_map_array(data.v, n);
2128 isl_union_map_free(umap);
2132 free_isl_fixed_map_array(data.v, n);
2133 isl_union_map_free(umap);
2137 /* Check whether the maps in umap that map to subsets of "ran"
2138 * have obviously distinct ranges.
2140 static int plain_injective_on_range_wrap(__isl_keep isl_set *ran, void *user)
2142 isl_union_map *umap = user;
2144 umap = isl_union_map_copy(umap);
2145 umap = isl_union_map_intersect_range(umap,
2146 isl_union_set_from_set(isl_set_copy(ran)));
2147 return plain_injective_on_range(umap, 0, isl_set_dim(ran, isl_dim_set));
2150 /* Check if the given union_map is obviously injective.
2152 * In particular, we first check if all individual maps are obviously
2153 * injective and then check if all the ranges of these maps are
2154 * obviously disjoint.
2156 int isl_union_map_plain_is_injective(__isl_keep isl_union_map *umap)
2159 isl_union_map *univ;
2162 in = union_map_forall(umap, &isl_map_plain_is_injective);
2168 univ = isl_union_map_universe(isl_union_map_copy(umap));
2169 ran = isl_union_map_range(univ);
2171 in = union_map_forall_user(ran, &plain_injective_on_range_wrap, umap);
2173 isl_union_set_free(ran);
2178 int isl_union_map_is_bijective(__isl_keep isl_union_map *umap)
2182 sv = isl_union_map_is_single_valued(umap);
2186 return isl_union_map_is_injective(umap);
2189 static int zip_entry(void **entry, void *user)
2191 isl_map *map = *entry;
2192 isl_union_map **res = user;
2194 if (!isl_map_can_zip(map))
2197 *res = isl_union_map_add_map(*res, isl_map_zip(isl_map_copy(map)));
2202 __isl_give isl_union_map *isl_union_map_zip(__isl_take isl_union_map *umap)
2204 return cond_un_op(umap, &zip_entry);
2207 static int lift_entry(void **entry, void *user)
2209 isl_set *set = *entry;
2210 isl_union_set **res = user;
2212 *res = isl_union_set_add_set(*res, isl_set_lift(isl_set_copy(set)));
2217 __isl_give isl_union_set *isl_union_set_lift(__isl_take isl_union_set *uset)
2219 return cond_un_op(uset, &lift_entry);
2222 static int coefficients_entry(void **entry, void *user)
2224 isl_set *set = *entry;
2225 isl_union_set **res = user;
2227 set = isl_set_copy(set);
2228 set = isl_set_from_basic_set(isl_set_coefficients(set));
2229 *res = isl_union_set_add_set(*res, set);
2234 __isl_give isl_union_set *isl_union_set_coefficients(
2235 __isl_take isl_union_set *uset)
2244 ctx = isl_union_set_get_ctx(uset);
2245 dim = isl_space_set_alloc(ctx, 0, 0);
2246 res = isl_union_map_alloc(dim, uset->table.n);
2247 if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
2248 &coefficients_entry, &res) < 0)
2251 isl_union_set_free(uset);
2254 isl_union_set_free(uset);
2255 isl_union_set_free(res);
2259 static int solutions_entry(void **entry, void *user)
2261 isl_set *set = *entry;
2262 isl_union_set **res = user;
2264 set = isl_set_copy(set);
2265 set = isl_set_from_basic_set(isl_set_solutions(set));
2267 *res = isl_union_set_from_set(set);
2269 *res = isl_union_set_add_set(*res, set);
2277 __isl_give isl_union_set *isl_union_set_solutions(
2278 __isl_take isl_union_set *uset)
2280 isl_union_set *res = NULL;
2285 if (uset->table.n == 0) {
2286 res = isl_union_set_empty(isl_union_set_get_space(uset));
2287 isl_union_set_free(uset);
2291 if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
2292 &solutions_entry, &res) < 0)
2295 isl_union_set_free(uset);
2298 isl_union_set_free(uset);
2299 isl_union_set_free(res);